Community Detection as a Graph Partitioning Problem

From a Cell Graph to a Partition

A cell-neighborhood graph represents cells as vertices and relationships between cells as edges. Community detection asks whether the graph can be divided into groups whose members are more strongly connected to one another than to vertices outside their group. This is a graph-partitioning problem: the data being grouped are vertices, and the edges describe their relationships.

The graph does not, by itself, say that a group is a cell type or biological state. A partition is a grouping supported by a chosen graph and objective. Its interpretation depends on how the graph was constructed, what its edge weights represent, and whether the proposed groups are stable and biologically meaningful.

Definition: Let $G=(V,E)$ be an undirected graph, where $V$ is the set of $n$ cell vertices and $E$ is the set of edges. Each edge $\{i,j\}$ has a nonnegative weight $w_{ij}=w_{ji}$; a larger weight represents a stronger graph connection. Assume there are no self-edges. A partition into $K$ groups is a collection $\mathcal{P}=\{C_1,\ldots,C_K\}$ of nonempty, disjoint subsets of $V$ whose union is $V$. Equivalently, each vertex $i$ has a group label $z_i\in\{1,\ldots,K\}$.

This tutorial uses weighted, undirected graphs. For an unweighted graph, take every existing edge to have weight 1. We count each undirected edge once when summing over edges. The partition must assign every included vertex to one group; allowing a vertex to remain unassigned would be a different problem.

Within-Group and Between-Group Connections

For a proposed partition, an edge is within-group if its two endpoints have the same label, and between-group if its endpoints have different labels. These categories are determined by the partition, not by an intrinsic label on the edge. Write $m$ for the total edge weight, $W_{\mathrm{in}}(\mathcal{P})$ for the total within-group weight, and $W_{\mathrm{between}}(\mathcal{P})$ for the total between-group weight.

m=\sum_{\{i,j\}\in E}w_{ij} =W_{\mathrm{in}}(\mathcal{P})+W_{\mathrm{between}}(\mathcal{P}).

The identity holds because every edge belongs to exactly one of the two categories. It is useful for checking calculations. A partition with high within-group weight may look attractive, but that quantity alone cannot define a useful clustering: putting every vertex in one group makes all edge weight within-group. A meaningful objective needs to account for the between-group structure, the sizes of groups, or both.

Worked Example: Sorting Edges by Group Assignment

Consider four cell vertices with edge weights $w_{12}=2$, $w_{23}=1$, $w_{34}=3$, and $w_{24}=0.5$, and no other edges. For the partition $C_1=\{1,2\}$, $C_2=\{3,4\}$, identify the within-group and between-group edges and calculate their total weights.

The edge $\{1,2\}$ lies within $C_1$, and $\{3,4\}$ lies within $C_2$. Thus $W_{\mathrm{in}}=2+3=5$. The edges $\{2,3\}$ and $\{2,4\}$ cross from $C_1$ to $C_2$, so $W_{\mathrm{between}}=1+0.5=1.5$.

The total weight is $m=2+1+3+0.5=6.5$, and $W_{\mathrm{in}}+W_{\mathrm{between}}=5+1.5=6.5$, as required. Notice that the partition determines which category each edge enters: changing the group labels could change the within- and between-group totals without changing the graph.

A Partition Objective: Normalized Cut

One way to formalize a graph partition is to measure how much edge weight crosses group boundaries. For a subset $C\subset V$, define its cut as the total weight of edges with one endpoint in $C$ and the other outside $C$. Define the degree of vertex $i$ as the sum of weights incident to it, and define the volume of a group as the sum of its vertices’ degrees.

\operatorname{cut}(C,V\setminus C) =\sum_{\substack{\{i,j\}\in E\\ i\in C,\ j\notin C}}w_{ij}, \qquad d_i=\sum_{j:\{i,j\}\in E}w_{ij}, \qquad \operatorname{vol}(C)=\sum_{i\in C}d_i.

The cut counts each crossing edge once. The volume counts edge weight incident to a group: an internal edge contributes twice to that group’s volume, once at each endpoint, while a crossing edge contributes once. In particular, $\operatorname{vol}(V)=2m$.

Definition: For a partition $\mathcal{P}=\{C_1,\ldots,C_K\}$ in which every group has positive volume, the normalized-cut objective is $$ \operatorname{Ncut}(\mathcal{P}) =\sum_{r=1}^{K} \frac{\operatorname{cut}(C_r,V\setminus C_r)} {\operatorname{vol}(C_r)}. $$ For a specified $K$, minimizing this objective seeks partitions with relatively little boundary weight compared with the volumes of their groups.

An edge between two groups contributes to the cut term for each of those groups, so it enters the sum twice. That is intentional: each group is assessed by its own boundary relative to its own volume. The objective is dimensionless because each numerator and denominator is measured in the same units of edge weight.

Why Normalize the Cut?

A raw cut objective sums the weight crossing group boundaries. It is simple, but can favor a partition that separates a small group with a small boundary, even if that group is tiny compared with the rest of the graph. Normalizing each group’s boundary by its volume makes the boundary relative to the amount of graph connection associated with that group. It discourages treating a very small-volume group as satisfactory merely because its absolute cut weight is small.

The objective also avoids rewarding the one-group partition: the definition applies to partitions with $K\geq 2$, and each group is evaluated relative to its complement. In practice, $K$ is specified or selected as part of a broader analysis; normalized cut alone does not determine the scientifically appropriate number of cell groups.

Worked Example: Comparing Two Two-Group Partitions

Take a four-vertex path with edges $\{1,2\}$, $\{2,3\}$, and $\{3,4\}$, with weights 3, 1, and 3, respectively. Compare the partition $\mathcal{P}_A=\{\{1,2\},\{3,4\}\}$ with $\mathcal{P}_B=\{\{1\},\{2,3,4\}\}$ using normalized cut.

The vertex degrees are $d_1=3$, $d_2=4$, $d_3=4$, and $d_4=3$. For $\mathcal{P}_A$, the only crossing edge has weight 1. Each group has volume $3+4=7$, so

\operatorname{Ncut}(\mathcal{P}_A) =\frac{1}{7}+\frac{1}{7} =\frac{2}{7} \approx 0.2857.

For $\mathcal{P}_B$, the crossing edge has weight 3. The singleton group has volume 3, and the other group has volume $4+4+3=11$. Therefore

\operatorname{Ncut}(\mathcal{P}_B) =\frac{3}{3}+\frac{3}{11} =1+0.2727 \approx 1.273.

Among these two candidate partitions, $\mathcal{P}_A$ has the lower normalized cut. This is a comparison of the stated graph objective, not evidence by itself that its two groups correspond to distinct biological populations.

Justification and a Useful Identity

The volume definition gives a direct relationship between a group’s internal weight and its boundary. Let $W_{\mathrm{in}}(C)$ be the total weight of edges with both endpoints in $C$. Each such edge contributes twice to $\operatorname{vol}(C)$; each edge crossing from $C$ contributes once. Hence

\operatorname{vol}(C) =2W_{\mathrm{in}}(C)+\operatorname{cut}(C,V\setminus C).

This identity justifies interpreting cut relative to volume as a boundary-to-connection measure. A group with substantial internal connectivity and a small boundary tends to have a smaller normalized boundary term than a group whose boundary is large relative to its volume. The statement is a structural interpretation of the objective, not a guarantee that every group will have a particular biological meaning.

For the four-vertex example above, $C=\{1,2\}$ has internal weight 3 and cut weight 1. Its volume is $2(3)+1=7$, matching the sum of degrees $d_1+d_2=3+4=7$. This provides an independent check on the arithmetic.

Worked Example: Diagnosing an Isolated Vertex

Suppose a graph has edges $\{1,2\}$ of weight 2, $\{2,3\}$ of weight 0.5, and $\{3,4\}$ of weight 2; vertex 5 has no edges. Consider $C_1=\{1,2,5\}$ and $C_2=\{3,4\}$. Calculate the normalized cut and explain what it can and cannot say about vertex 5.

The degrees of vertices 1 through 4 are $2, 2.5, 2.5,$ and $2$; the degree of vertex 5 is 0. The boundary between the two groups is the edge $\{2,3\}$, so its weight is 0.5. The group volumes are $\operatorname{vol}(C_1)=2+2.5+0=4.5$ and $\operatorname{vol}(C_2)=2.5+2=4.5$. Thus

\operatorname{Ncut}(\{C_1,C_2\}) =\frac{0.5}{4.5}+\frac{0.5}{4.5} \approx 0.2222.

If vertex 5 were placed in $C_2$ instead, both group volumes and the cut would remain unchanged, so the objective value would also remain 0.2222. If vertex 5 formed a group by itself, its volume would be zero and the normalized-cut term would be undefined. The calculation therefore cannot determine a meaningful placement for the isolated vertex; the graph has no edges carrying information about its relationship to other cells.

Assumptions, Diagnostics, and Alternatives

The normalized-cut definition assumes nonnegative edge weights, an undirected graph, and positive volume for each group being scored. These conditions matter in cell graphs: a directed neighborhood graph must first be represented under an explicit undirected convention if this objective is to be used as defined here. An isolated vertex has zero volume, making a group containing only that vertex invalid for the formula. Check the graph’s degree and connectivity summaries before interpreting an objective value.

For a fixed graph and a fixed $K$, normalized cut can compare candidate partitions, but it does not ensure a unique optimum, biological validity, or robustness to changes in graph construction. Different partitions can have similar scores. A low score is meaningful only relative to the graph and the candidate partitions being compared; it is not a p-value, a measure of statistical significance, or proof of cell-type separation.

Alternative objectives encode different preferences. Minimizing the raw cut focuses on total crossing weight and can favor small groups. Ratio cut normalizes boundary weight by group size rather than graph volume. Other community objectives compare observed connections with a baseline expectation. These approaches need not rank partitions in the same order. The appropriate choice depends on the graph representation and the clustering question; no objective is a neutral definition of a community.

Common warning signs include a score dominated by a very small-volume group, many zero-degree vertices, and a partition that changes substantially under modest changes to edge weights or graph construction. These are reasons to inspect the graph and assess the partition’s stability, not reasons to assign a biological interpretation from the objective alone.

Key takeaway: A graph partition assigns every vertex to a group. Within-group and between-group weights describe the edges under that assignment; normalized cut compares each group’s crossing weight with its graph volume. The objective is a tool for comparing partitions, not a biological conclusion.

Check Your Understanding

Try each problem, then check the solutions below.

A graph has total edge weight 12. A partition has within-group weight 8. What is its between-group weight?
In an undirected graph, an edge of weight 2 joins two different groups. How many times does it contribute to the sum of normalized-cut numerators across the groups?
A group has internal edge weight 4 and boundary weight 3. Find its volume.
Why is normalized cut undefined for a group consisting only of an isolated vertex?

Solutions. (1) By $m=W_{\mathrm{in}}+W_{\mathrm{between}}$, the between-group weight is $12-8=4$. (2) It contributes once to the cut of each endpoint group, hence twice to the sum of group cut numerators. (3) The volume is $2(4)+3=11$, since internal edges are counted at both endpoints and boundary edges once. (4) The isolated vertex has degree zero, so the group volume is zero and its normalized-cut term would divide by zero.