Conductance

Compute per-community conductance for a fixed node-to-community partition

Category: community-detection

Syntax

SELECT * FROM graph_conductance(table_name, community_property)

Description

Conductance quantifies how cleanly a community is separated from the rest of the graph. For a community c with vertex set S, the engine reports phi(c) = cut(c) / vol(c), where cut(c) is the sum of edge weights crossing the boundary of S (one endpoint in S, the other outside) and vol(c) is the sum of incident edge weights of vertices in S. Smaller phi means a more isolated, internally cohesive community; phi near 1 means most of the community's incident weight points outward. This function evaluates conductance for a partition the caller supplies; it does not search for communities itself. The partition is a comma-separated string of integer community ids, one per node, in the engine's internal node-id order (the order other graph_* table functions emit on the same edge table). The list length must exactly match the node count of the loaded graph. The engine follows Neo4j GDS gds.conductance.stream and uses the community's own volume as the denominator. This is intentional: GDS reports asymmetric conductance values for the two sides of a cut, because each side's volume differs. On Zachary's karate-club split with cut = 11, mr_hi (vol 81) returns 0.136 and officer (vol 75) returns 0.147. Some textbook formulations use min(vol(c), vol(V \ c)) instead; this engine does not. The CPU implementation walks the doubled-CSR adjacency once, accumulating cut[c] and vol[c] in two hash maps, and emits one row per community in O(E) time and O(C) memory, where C is the number of distinct communities. Communities that appear in the partition but have zero cut are still reported as 0.0 rather than omitted, so the result row count equals the number of distinct community ids in the input. The GPU implementation reuses the modularity reduction kernel with a mode flag set to conductance. It dense-remaps the partition to u32, scales edge weights into u32 fixed-point (2^20 scale, ~6 decimal digits of precision for weights in [0, 4096)), and runs a single per-vertex compute pass that atomicAdds cut and vol into per-community buckets. The host divides on f64 after readback. The dispatch refuses inputs that would overflow the u32 fixed-point envelope and falls back to CPU rather than returning corrupted values. Rows are returned in ascending raw community_id order on both paths. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology across calls, so scoring multiple partitions for the same edge table reuses a single load.

Parameters

Name	Type	Description
`table_name`		Specify the name of the registered Delta table containing edge data. The table must include source and target columns (auto-detected as src/source/src_id and dst/target/dst_id). If a weight column is present, its values are used for both the cut and volume sums. The graph is loaded as undirected for the conductance computation.
`community_property`		Provide a comma-separated list of integer community ids, one per node, in the engine's internal node-id order. The list length must equal the node count of the loaded graph; mismatched lengths surface as 'conductance: partition length N != node count M'. Community ids may be any i64 values and are densely remapped internally.

Examples

CREATE TABLE friendships AS
SELECT * FROM VALUES
  (1, 2, 1.0), (1, 3, 1.0), (2, 3, 1.0),
  (4, 5, 1.0), (4, 6, 1.0), (5, 6, 1.0),
  (3, 4, 0.5)
AS t(src, dst, weight);

SELECT community_id, conductance
FROM graph_conductance('friendships', '0,0,0,1,1,1')
ORDER BY conductance;

WITH partition AS (
  SELECT node_id, community_id
  FROM graph_louvain('friendships')
)
SELECT community_id, conductance
FROM graph_conductance(
  'friendships',
  (SELECT string_agg(CAST(community_id AS VARCHAR), ',' ORDER BY node_id) FROM partition)
)
ORDER BY conductance;

WITH partition AS (
  SELECT node_id, community_id
  FROM graph_louvain('friendships')
)
SELECT community_id, conductance
FROM graph_conductance(
  'friendships',
  (SELECT string_agg(CAST(community_id AS VARCHAR), ',' ORDER BY node_id) FROM partition)
)
ORDER BY conductance ASC
LIMIT 1;

Pitfalls

An isolated community (one whose only edges live entirely inside it, no cross-community edges) has conductance 0, the best possible value. This is mathematically correct but operationally misleading: a partition that places every singleton into its own community trivially achieves zero conductance everywhere. Combine conductance with community size and modularity when evaluating partitions; do not optimise on conductance alone.
A community whose members have zero incident weight (isolated vertices or all-zero-weight incident edges) is reported as 0.0 by convention. This collides with the value of a perfectly isolated community, so do not treat conductance = 0 as an unambiguous signal without checking the underlying community size and degree.
The engine uses the community's own volume as the denominator (Neo4j GDS convention), not min(vol(c), vol(V \ c)). The two sides of a cut therefore report different conductance values even when the cut weight is identical between them. Compare against GDS, not against textbook definitions, when validating.
The community_property argument must list ids in the engine's internal node-id order. Use ORDER BY node_id in the string_agg over a partition table; an out-of-order list scores a different (effectively scrambled) partition.
Edge weights enter both the cut and volume sums. Duplicate (src, dst) rows in the edge table inflate both terms and shift phi; deduplicate or sum weights before scoring if parallel edges are not semantically meaningful.
The graph is loaded as undirected, matching gds.conductance.stream. Directed asymmetries are collapsed. If direction matters, evaluate the directed cut manually with a SQL join over the edge table.
The GPU path declines silently when the fixed-point envelope is exceeded (per-edge weight at or above 4096, or aggregate edge weight large enough to overflow a single u32 community bucket). The CPU fallback still returns the correct values, but the latency profile changes. Verify with EXPLAIN when GPU dispatch is a latency requirement.