Graph Conductance as a Cluster Diagnostic

Why Measure a Cluster’s Boundary in the Graph?

A cell-neighbor graph represents cells as vertices and their neighborhood relationships as edges. A clustering assigns each cell to a group, but a cluster’s membership alone does not reveal how it sits in that graph. A group may have many edges connecting it to other cells, or only a few relative to its size and connectivity. Conductance summarizes this boundary-to-volume relationship.

Conductance is a diagnostic of how tightly a set of vertices is separated from the rest of a particular graph. In single-cell analysis, that graph is constructed from choices such as the representation of cells, the neighborhood rule, and any edge weighting. Consequently, conductance describes the cluster in the graph that was supplied; it does not independently establish that the cluster represents a biologically meaningful cell type.

Definition: Let $G=(V,E,w)$ be an undirected graph with nonnegative edge weights $w_{ij}$, where vertices represent cells. For a set of vertices $S$, its cut weight is the total weight of edges with one endpoint in $S$ and one in its complement $V\setminus S$: $$ \operatorname{cut}(S,V\setminus S)=\sum_{\substack{i\in S,\ j\in V\setminus S\\ \{i,j\}\in E}} w_{ij}. $$ The weighted degree of a vertex is the sum of weights of its incident edges, and the volume $\operatorname{vol}(S)$ is the sum of weighted degrees over vertices in $S$. The conductance of $S$ is $$ \phi(S)=\frac{\operatorname{cut}(S,V\setminus S)} {\min\{\operatorname{vol}(S),\operatorname{vol}(V\setminus S)\}}. $$

For an unweighted graph, each edge has weight 1, so volume is the sum of ordinary degrees and cut weight is the number of crossing edges. Throughout, assume the graph is undirected, edge weights are nonnegative, and self-loops have been removed or excluded from both cut and volume calculations. If either side has zero volume, this formula is undefined; report that case rather than assigning a conductance value. An empty cluster and a cluster containing every vertex also have an empty side and therefore no defined conductance.

The minimum in the denominator makes the definition symmetric: $\phi(S)=\phi(V\setminus S)$. A cluster with a small boundary relative to the volume of the smaller side has low conductance. A large value indicates that the smaller side has comparatively many connections across its boundary. Neither description is a statement about biological identity.

How Volume and Boundary Work Together

The volume of a cluster includes both the weight of edges inside it and the weight of edges leaving it. In an undirected graph, each internal edge contributes to the degree of both endpoints in the cluster, whereas a crossing edge contributes once to the volume on each side. Thus, if $W_{\mathrm{in}}(S)$ is the total weight of edges internal to $S$, then $$ \operatorname{vol}(S)=2W_{\mathrm{in}}(S)+\operatorname{cut}(S,V\setminus S). $$ This identity is useful for checking a calculation, but it also highlights why counting only cluster members is not enough: two clusters of the same size can have different volumes because their cells have different numbers or weights of graph connections.

There is a direct interpretation for a weighted random walk on the graph. From a vertex, the walk chooses a neighbor with probability proportional to the edge weight. If the starting vertex is sampled from $S$ with probability proportional to its weighted degree, then the probability that the next step exits $S$ is $$ \frac{\operatorname{cut}(S,V\setminus S)}{\operatorname{vol}(S)}. $$ When $S$ is the smaller-volume side, this quantity is $\phi(S)$. Conductance therefore measures the one-step escape probability from the smaller side under this particular degree-weighted starting distribution. It is not the escape probability from a uniformly sampled cell unless the degrees are equal.

The range follows from the definition. The cut weight is nonnegative and cannot exceed the volume on either side, since every crossing edge contributes to each side’s volume. Therefore $$ 0\leq \operatorname{cut}(S,V\setminus S) \leq \min\{\operatorname{vol}(S),\operatorname{vol}(V\setminus S)\}, \qquad 0\leq\phi(S)\leq 1. $$ A zero value occurs when there are no crossing edges and both sides have positive volume. A value of 1 means the cut weight equals the smaller side’s full volume; it does not mean that every possible edge between the two sides exists.

Worked Example: Conductance in a Weighted Cell Graph

Suppose a hypothetical neighbor graph has cells 1 through 5. Its edges and weights are: $1\!-\!2$ with weight 2, $2\!-\!3$ with weight 1, $1\!-\!3$ with weight 1, $2\!-\!4$ with weight 0.5, $3\!-\!4$ with weight 0.5, $3\!-\!5$ with weight 1, and $4\!-\!5$ with weight 2. Calculate conductance for cluster $S=\{1,2,3\}$.

The internal edges have total weight $2+1+1=4$. The crossing edges have total weight $0.5+0.5+1=2$, so the cut weight is 2. The cluster volume is $$ \operatorname{vol}(S)=2(4)+2=10. $$ The complement $\{4,5\}$ has one internal edge of weight 2, so its volume is $$ \operatorname{vol}(V\setminus S)=2(2)+2=6. $$ The smaller volume is 6. Hence $$ \phi(S)=\frac{2}{\min\{10,6\}}=\frac{2}{6}=0.3333. $$

The boundary weight is one-third of the smaller side’s volume. This indicates some separation in this graph, but it is not an absolute rating: the value depends on the graph and on the convention used to construct its weights.

Calculating Conductance for a Partition

A clustering usually divides the full vertex set into several clusters. To calculate conductance for one cluster, put every other cluster together as its complement. Count all edges from the selected cluster to any cell outside it, not just edges to one particular neighboring cluster. The complement’s volume likewise includes all its internal edges, including edges between different clusters within that complement.

Worked Example: An Unweighted Cluster With Several Boundary Edges

Consider a hypothetical unweighted graph with $S=\{1,2,3,4\}$ and complement $\{5,6,7,8\}$. The five internal edges of $S$ are $(1,2),(2,3),(3,4),(4,1),(1,3)$. The five internal edges of the complement are $(5,6),(6,7),(7,8),(8,5),(5,7)$. There are three crossing edges: $(2,5),(3,6),(4,7)$. Find the conductance of $S$.

Because the graph is unweighted, each edge has weight 1. The cut weight is the number of crossing edges, which is 3. The volume of $S$ is twice its five internal edges plus the three crossing edges: $$ \operatorname{vol}(S)=2(5)+3=13. $$ The complement has the same calculation, $\operatorname{vol}(V\setminus S)=2(5)+3=13$. Thus $$ \phi(S)=\frac{3}{\min\{13,13\}}=\frac{3}{13}=0.2308. $$

The calculation uses three crossing edges in the numerator, not the number of cells in $S$ or the number of edges from $S$ to just one selected cluster. Conductance is low here because the cut weight is modest relative to either side’s volume.

The denominator is important when comparing clusters. Dividing by the smaller volume prevents a large complement from making the same boundary appear artificially small. It also makes the score unchanged if the two sides are swapped. However, the denominator is volume, not cell count. If cells have very different degrees, two clusters with the same number of cells can have substantially different conductance.

Worked Example: Combining All Other Clusters Into the Complement

Suppose a hypothetical unweighted graph has three clusters, $A=\{1,2\}$, $B=\{3,4\}$, and $C=\{5,6\}$. Each cluster contains one internal edge: $(1,2)$, $(3,4)$, and $(5,6)$. There are also crossing edges $(2,3)$ and $(4,5)$. Calculate conductance for $B$.

Both crossing edges touch $B$, so $\operatorname{cut}(B,V\setminus B)=2$. The two vertices in $B$ each have degree 2, giving $\operatorname{vol}(B)=4$. The complement $A\cup C$ has vertex degrees $1,2,2,1$, so its volume is 6. Equivalently, it contains two internal edges and the two crossing edges, giving $2(2)+2=6$. Therefore $$ \phi(B)=\frac{2}{\min\{4,6\}}=\frac{2}{4}=0.5000. $$

Both links leaving $B$ count, even though one connects it to $A$ and the other to $C$. Conductance does not separately describe the boundary with each other cluster; it summarizes the boundary between $B$ and the union of everything outside $B$.

Assumptions, Diagnostics, and Limitations

Conductance is a descriptive graph statistic, not a hypothesis test. It has no p-value or confidence interval by itself, and a conventional threshold does not certify that a cluster is correct. The interpretation assumes the graph and its edge weights are meaningful for the question at hand. It also assumes the graph has been treated as undirected. If a neighbor construction initially produces directed edges, the analyst must use a specified symmetrization rule before applying this definition; different rules can yield different conductance values.

Inspect the graph and calculation when a value seems surprising. Check that:

Each crossing edge is counted once in the cut, and its weight is included once in each side’s volume.
Internal edges contribute twice to a side’s volume, as required by the degree sum.
Weights are nonnegative and correspond to the chosen graph convention; changing or rescaling weights can alter relative contributions.
The cluster and its complement are defined over the same vertex set used to build the graph.
The graph’s connectivity, degree distribution, and edge-weight distribution do not make the result hard to interpret.

Multiplying every edge weight by the same positive constant leaves conductance unchanged, because it multiplies both the numerator and denominator by that constant. Changing weights unequally, removing edges, or changing which cells count as neighbors can change the score. In particular, conductance cannot correct for a poor or inappropriate graph construction.

A small group can have low conductance if it has substantial internal connectivity and few connections out. A low value is therefore not, on its own, proof of a well-defined biological population. Conversely, a biologically meaningful gradient or transition may produce many cross-boundary edges and a higher conductance. Uneven density and bridge cells can also affect boundary structure; conductance compresses that structure into one number and does not identify which cells or edges are responsible.

Conductance answers a different question from the feature-space indices discussed in the earlier material on silhouette widths and the Calinski-Harabasz and Davies-Bouldin indices. Those indices summarize geometric separation or compactness in a chosen feature representation; conductance summarizes connectivity in a chosen graph. Agreement among diagnostics can be informative, but none substitutes for checking whether the representation, graph, and scientific interpretation are appropriate. Conductance also does not compare cluster assignments to reference labels or establish biological validity.

Common Mistake

Wrong reasoning: “This cluster has only two edges crossing its boundary, so its conductance must be low.” The number of boundary edges alone is insufficient. Conductance divides cut weight by the smaller of the two volumes, which depends on internal connections and edge weights as well as the boundary.

Correction: Calculate the cut weight and both volumes from the same graph, then divide by the smaller volume. State the graph and cluster being assessed, and interpret the resulting value as a connectivity diagnostic—not as a probability that the clustering is biologically correct.

Key takeaway: Conductance compares a cluster’s total boundary weight with the smaller volume on either side of that boundary. Low conductance indicates relatively few cross-boundary connections in the specified graph; it does not establish biological validity, and its interpretation depends on graph construction.

Check Your Understanding

Try each question, then compare your reasoning with the solutions.

An unweighted graph has a cluster with 4 internal edges and 2 crossing edges. Its complement has 5 internal edges. Calculate both volumes and conductance.
Why does an edge crossing from a cluster to its complement contribute to the volume of both sides?
A cluster has cut weight 3, volume 12, and its complement has volume 8. What is its conductance, and which side determines the denominator?
Can a low conductance value establish that a cluster is a biologically meaningful cell type? Explain.
What happens to conductance if all edge weights are multiplied by the same positive constant?

Solutions. (1) The cluster volume is $2(4)+2=10$; the complement volume is $2(5)+2=12$. Thus conductance is $2/\min\{10,12\}=0.2000$. (2) A crossing edge has one endpoint on each side, so it contributes to the weighted degree sum on each side. (3) The conductance is $3/\min\{12,8\}=3/8=0.3750$; the complement determines the denominator because its volume is smaller. (4) No. Low conductance describes separation in the specified graph, not biological identity; the graph construction and biological evidence must be considered separately. (5) It is unchanged: the same positive factor multiplies the cut weight and both volumes, and cancels in the ratio.