Communities

Some state belongs to a group of nodes rather than to each node: a fraud ring’s total suspicion, a topic cluster’s centroid embedding, a department’s headcount. Keeping a copy on every member wastes memory and goes stale; pg_warren keeps it once per community instead, on a quotient graph with one node per community, and moves vectors between the two levels (DESIGN.md §6.6).

Call	What it does
`contract(graph, label_vector, out_graph)`	a new version of graph `out_graph`: one node per distinct label, the edges between communities aggregated
`project(graph, x, out_graph, y, agg := 'sum')`	`y` on the quotient: each community’s `sum`, `mean`, `max`, `min` or `count` of `x` over its members (`Pᵀ·x`)
`lift(out_graph, y, graph, x)`	`x` on the graph: each node gets its community’s row of `y` (`P·y`)
`louvain(graph, out)`, `leiden(graph, out)`	a label vector of communities that maximise modularity (below)

The examples continue those of compute.md, on the roads graph; they run as written in test/sql/docs_examples.sql.

Contracting a graph

A label vector names each node’s community. Any numeric vector of integers works (i64, or f64/f32 holding whole numbers), such as the output of components_vector or label_propagation, or one you load with vector_from_query:

SELECT warren.vector_from_query('roads', 'region',
  'SELECT id, CASE WHEN id <= 2 THEN 1 ELSE 2 END FROM city');
SELECT warren.contract('roads', 'region', 'regions');   -- returns the new version's id

regions is a graph like any other: its node ids (bigint) are the labels, so results join back to them; it has versions, retention, vectors, and every traversal and compute function works on it. Each label is one node; the weight of an edge between two communities is the sum of the weights of the edges joining their members (or their count, with weighted := false), and the edges inside a community make its self-loop (left out with drop_self_loops := true). An undirected graph gives an undirected quotient. The quotient is the matrix product PᵀAP of the stored adjacency, so an undirected edge inside a community counts twice in its self-loop (both its stored directions) and a self-loop once, as each counts in its nodes’ degrees: a community’s weighted degree is the sum of its members’, and the total edge weight is kept. Relations are kept, each contracted on its own, except that a count counts an edge in several relations once, in the first of them: the quotient’s relations then add up to the counts of distinct edges, as spmv counts such an edge once. With per_relation := true it counts in each of its relations (semantics.md).

So a relation-filtered read of a counting quotient sees a shared pair only in the first of its relations: if every edge of b is also in a, the quotient’s relation b has no edges, and has_edge(q, c, d, 'b'), spmv(..., rels := ARRAY['b']) and the traversals over b find none. To keep each relation’s own edges, contract with per_relation := true, or weighted (weights are summed in each relation either way).

SELECT warren.vector_const('regions', 'one', 1);
SELECT warren.spmv('regions', 'one', 'km_out');       -- each region's weighted degree
SELECT node_id AS region, value AS km FROM warren.vector_values('regions', 'km_out', NULL::bigint);
-- region 1: 54 (ash–birch, 10 km, inside: counted both ways, + 34 km to region 2);
-- region 2: 52 (9 km inside, twice, + 34): each region's members' summed degree

Contracting again into the same name adds a version (promote := false leaves it staged). A label seen before keeps its dense id, so vectors on two versions of the quotient compare by label. warren.refresh and warren.compact refuse a contraction: run the labelling again and contract again. So a quotient’s id space grows with every label it has ever seen (labels that disappear are tombstoned) and cannot be compacted: when labels change wholesale, as a fresh labelling’s usually do, contract into a new graph instead. Only versions of one parent graph can go into a quotient, and only while one of its versions is still linked to that graph: once the parent graph or every linked version is dropped, the quotient takes no new versions (22023), so contract into a new graph. Two crossed contractions in concurrent transactions (q1 into q2 and q2 into q1), or a contract and a refresh of the same parent in two concurrent transactions, can deadlock (40P01): retry the one Postgres cancels. A quotient can itself be contracted, which gives a hierarchy of communities.

Labels must be integers: a NaN, an infinity or a fraction is refused (22023), as is a bool vector (42804). Deleted (tombstoned) nodes belong to no community.

Moving vectors between the levels

A quotient version remembers the version it was contracted from and the membership of each node. project reads x on exactly that version of the parent and writes y on the quotient; lift does the reverse.

SELECT warren.vector_from_query('roads', 'pop', 'SELECT id, pop FROM city');
SELECT warren.project('roads', 'pop', 'regions', 'population');            -- sum
SELECT warren.project('roads', 'pop', 'regions', 'largest', agg := 'max');
SELECT warren.lift('regions', 'population', 'roads', 'region_population');
SELECT node_id, value FROM warren.vector_values('roads', 'region_population', NULL::int);
-- ash and birch: 150; cedar, dale and elm: 110

project reads x of any element type and width; the result is double precision (bigint for count, which counts each community’s members). On a matrix it works column by column, so agg := 'mean' of an embedding matrix gives each community’s centroid. lift keeps y’s type and width. Both take persist := false for a transient result, and version := to use an older version of the quotient.

Finding communities: Louvain and Leiden

louvain and leiden find communities that maximise modularity: how much more edge weight a partition keeps inside its communities than a random graph with the same degrees would. Each writes a label vector, so contract and project take its result directly.

Call	What it does
`louvain(graph, out, resolution := 1, seed := 0, max_levels := 100, tolerance := 1e-7, weighted, levels_prefix, version, per_relation := false)`	Louvain (Blondel et al. 2008); returns the partition’s modularity
`leiden(graph, out, resolution := 1, seed := 0, max_levels := 100, tolerance := 1e-7, randomness := 0.01, iterations := 2, weighted, levels_prefix, version, per_relation := false)`	Leiden (Traag et al. 2019): every community it finds is connected
`modularity(graph, labels, resolution := 1, weighted, version, per_relation := false)`	the modularity of any label vector’s partition

SELECT warren.louvain('roads', 'community');            -- 0.0397: the modularity
SELECT node_id, value FROM warren.vector_values('roads', 'community', NULL::int);
-- ash, dale and elm: 0; birch and cedar: 1
SELECT warren.modularity('roads', 'region');            -- the hand-made regions: -0.142

Both treat the graph as undirected (an edge and its reverse add up) and use edge weights if weighted (NULL: if the graph has them). A community is labelled by the smallest dense id among its members, so labels are stable for a given graph version and seed. resolution above 1 favours smaller communities, below 1 larger ones.

Both work in levels. A level moves nodes to the neighbouring community that most raises modularity, revisiting the neighbours of each node that moved until none moves (Traag et al.’s fast local moving), then contracts the level’s graph by the communities found, so the next level moves whole communities. Louvain stops when a level raises modularity by no more than tolerance, as NetworkX’s threshold does. Leiden refines each community into well-connected parts before it contracts, so no community it returns is split in two, or held together only through another community. It continues while the refinement still merges nodes, as Traag et al.’s does; tolerance ends each level’s moving instead. randomness is θ of the refinement’s random merges (0: always the best merge). levels_prefix := 'lv' also keeps each level’s partition, as vectors lv_1, lv_2, …, coarsest last: a hierarchy of communities.

Leiden runs its levels iterations times (2 by default, as igraph’s community_leiden): each pass after the first starts its first level’s moving from the partition the pass before found rather than from each node alone, so it can still move nodes the first pass’s coarse levels left in the wrong community. On 20 planted blocks of 1,000 nodes one pass scores 0.794 and two find the planted blocks (0.855). The run stops early after a pass that changes nothing, since the same start and seed would give the same pass again; a negative iterations runs until then (at most 100 passes, with a WARNING if it is still changing), and 0 is refused. With levels_prefix, every pass’s levels are kept in turn, so lv_1 is the first pass’s finest and the last one is out.

The result is the same for any number of threads (warren.threads), and for a given seed. Different seeds give different, comparably good partitions. Modularity counts an undirected self-loop once in its node’s degree, as contract does, so a partition scores the same on a graph and, as singletons, on its quotient. NetworkX counts it twice, so on an undirected graph pg_warren’s is NetworkX’s with each self-loop’s weight halved, and the two agree without self-loops. On a directed graph it is the modularity of the undirected view, not NetworkX’s directed (Leicht and Newman) one. The view’s edges are those spmv multiplies by: a pair linked in several relations is one edge, its weights summed, or weighing 1 when unweighted. With per_relation := true (on modularity, louvain, leiden, local_moving, leiden_refine and contract) it is an edge in each of its relations instead, so an unweighted pair in three relations weighs 3 (semantics.md).

The steps are SQL functions too, for programs of your own: local_moving(graph, out, initial, keys, resolution, seed, max_sweeps, tolerance, weighted, persist, version, per_relation) (one level’s moving, from the partition initial or from each node alone; returns the number of communities) and leiden_refine(graph, communities, out, keys, resolution, seed, randomness, weighted, persist, version, per_relation). louvain is PL/pgSQL over them, contract, project and lift (crates/pg_warren/src/community_sql/library/louvain.sql), a template for programs of your own. leiden runs the same steps natively, in the same order with the same seeds, so it finds the partitions 0.7.0’s PL/pgSQL leiden found (to the last bit on unweighted and integer-weighted graphs), but holds its levels in memory: each level’s graph is contracted from the level below, and nothing but out and the levels levels_prefix asks for is written. Graph names beginning with _warren_ are reserved for the library’s levels (42939): contract(graph, labels, NULL) makes a new graph of the caller’s named _warren_level_<version id>, after the id it returns. A level graph stores each relation’s forward CSR only, whatever the input’s layout (no reverse or merged CSR): the levels read nothing else, and on a directed graph that halves what each level writes.

Since 0.8.0 leiden writes no level and needs no disk beyond out’s vector (and the levels it is asked to keep); its levels are charged to warren.max_compute_memory. On the head-to-head’s real graphs it is 1.3–21× faster than before, and within 0.76–1.6× of igraph’s community_leiden on the medium ones (bench/results/corpus/head_to_head/README.md, “Leiden in 0.8.0”). The 0.4.0 figures below are leiden’s before it.

At 1M nodes and 5M undirected edges on 4 vCPUs, louvain takes 5.8 s and leiden 8.3 s for one iteration; at 10M nodes, 93 s and 119 s. The default two iterations take about twice one (20.9 s at 1M, measured on a slower day; 246.5 s at 10M, 18 levels, against 115.4 s for louvain in the same run) and raise modularity from 0.837 to 0.898 at 1M and from 0.840 to 0.900 at 10M, where the planted blocks score 0.8995 (limits.md). Each level writes its graph as a version (segments and WAL), and the rows of a level’s graph dropped during the run are reclaimed only by VACUUM after its transaction ends, so a run needs free disk for every level: on that 1M-node graph, whose own segments take 75 MB, louvain wrote 166 MB of segments and about as much WAL, leiden (one iteration, 7 levels) 294 MB and 323 MB, and its second iteration about as much again. At 10M nodes (0.72 GB of segments) louvain wrote 2.5 GB of segments and 2.6 GB of WAL, and leiden with its two iterations 7.8 GB and 8.2 GB. On a graph with little community structure it is far more, because each level’s graph stays nearly as large as the input: on a uniform random graph of 10M nodes and 100M directed edges louvain had written 7.5 GB of segments when it was stopped for disk, before level graphs stored forward CSRs only (at 1M nodes that halved its level segments, 536 MB to 293 MB), and leiden was refused there at the default limits (53400), before its refinement charged its real peak (see limits.md). The planned fix for louvain’s disk is for contract to keep a quotient in memory for the rest of the statement (DESIGN.md §6.7, §13); leiden no longer writes any. A failed or cancelled louvain rolls its level graphs back, but their segment rows, already written, also stay as dead tuples until VACUUM.

Lineage, retention and access

warren.info(out_graph) reports "source": "contraction" and, for each version, parent_version, parent_graph and label_vector (the label vector’s id; NULL once that vector is gone, or if it was transient).
A version of the parent that a quotient version was contracted from is kept beyond retain_versions, with a NOTICE, so project and lift keep working. Dropping it anyway (drop_version, or drop_graph of the parent) keeps the quotient but unlinks it: project and lift then fail with 55000.
To contract, a role must be able to read the parent graph. The quotient it creates is its own (it may grant it). Contracting into an existing quotient needs membership in that quotient’s owner role. project and lift need read access to both graphs, and the usual rules for replacing a vector (DESIGN.md §7).