From Cell Profiles to a Partition
Graph clustering is a sequence of connected decisions. Cell profiles are represented in a feature space; distances define local neighbors; a graph records those relationships; and a community-detection method partitions the graph. A cluster label therefore depends not only on the community algorithm, but also on the distance, neighbor rule, symmetrization, and edge weights used to construct its input.
The following hypothetical example uses six cells and two coordinates. The coordinates can be understood as scores for two features after an earlier representation step; they are not raw gene counts. The aim is to make every graph choice and calculation visible, not to suggest that two features or six cells are adequate for biological discovery.
State the Graph Construction Before Calculating
Let cell \(i\) have profile vector \(z_i\). For this example, use Euclidean distance, \(d(i,j)=\sqrt{\sum_r(z_{ir}-z_{jr})^2}\). This choice treats the two coordinates as measured on comparable scales and gives straight-line distance in the feature plane. More generally, Euclidean distance is only meaningful when the chosen representation and feature scaling make that geometry appropriate.
We select \(k=2\) neighbors for each cell. We then use union symmetrization: an undirected edge joins \(i\) and \(j\) if either cell selected the other. Each undirected edge is included once, and there are no self-loops. Finally, we weight each edge using the Gaussian rule \(w_{ij}=\exp[-d(i,j)^2/(2\sigma^2)]\), with bandwidth \(\sigma=0.2\) in the same distance units. This assigns positive, larger weights to closer selected pairs. These are fixed illustrative choices, not universal defaults.
| Cell | Coordinate 1 | Coordinate 2 |
|---|---|---|
| A | 0.0 | 0.0 |
| B | 0.1 | 0.0 |
| C | 0.2 | 0.0 |
| D | 2.0 | 0.0 |
| E | 2.1 | 0.0 |
| F | 2.2 | 0.0 |
Worked Example: Calculate Distances and Select Neighbors
All cells lie on the first coordinate axis, so their Euclidean distances are absolute differences in that coordinate. For example, \(d(A,C)=\sqrt{(0.0-0.2)^2+(0.0-0.0)^2}=0.2\), while \(d(C,D)=\sqrt{(0.2-2.0)^2}=1.8\).
For A, the two closest cells are B at distance 0.1 and C at distance 0.2. For B, A and C are both at distance 0.1, so both are selected when \(k=2\). For C, the closest are B at 0.1 and A at 0.2. The corresponding choices on the other side are: D selects E at 0.1 and F at 0.2; E selects D and F, both at 0.1; and F selects E at 0.1 and D at 0.2.
Distances tie for B and E, but both tied neighbors in each case are selected when \(k=2\), so tie-breaking does not affect the graph. This detail matters: a tie at the cutoff can change a graph if only some of the tied cells can be selected.
After union symmetrization, the edges among A, B, and C are AB, BC, and AC. Among D, E, and F they are DE, EF, and DF. No cross-group pair is selected, so there are no edges between the two triples. The graph consists of two disconnected triangles.
Weight the Edges and Calculate Modularity
The edge-weight formula requires a distance and the stated bandwidth. For a distance of 0.1, \(w=\exp[-0.1^2/(2(0.2)^2)]=\exp(-0.125)\approx0.8825\). For a distance of 0.2, \(w=\exp[-0.2^2/(2(0.2)^2)]=\exp(-0.5)\approx0.6065\). Thus, each triangle has two edges of weight 0.8825 and one edge of weight 0.6065. The weight table records the complete undirected edge list.
| Edge | Distance | Weight |
|---|---|---|
| AB, BC, DE, EF | 0.1 | 0.8825 each |
| AC, DF | 0.2 | 0.6065 each |
Worked Example: Evaluate the Two-Triangle Partition
For the proposed partition \(\{A,B,C\}\) and \(\{D,E,F\}\), each triangle’s internal edge weight is \(W=2(0.8825)+0.6065=2.3715\). The total edge weight is \(m=2W=4.743\). Every edge is internal to one of the two communities, so \(l_c=2.3715\) for each. The sum of weighted degrees in either triangle is \(K_c=2W=4.743\), because each internal edge contributes to the degree of both endpoints.
Substitution gives
The result is a modularity of 0.5000 for this partition under the specified graph and \(\gamma=1\). It is not a probability, a percentage of correctly classified cells, or evidence that the two groups are known cell types.
Community Detection and a Direct Check
Here the community-detection target is the modularity partition with \(\gamma=1\). In larger graphs, an algorithm typically searches for a high-modularity partition using a heuristic, so different initializations or random seeds can yield different results. In this tiny graph, the proposed partition can be checked directly against alternatives.
Each disconnected triangle has total weight \(W=2.3715\). Keeping it as one community contributes \(W/m-(W/m)^2=0.5-0.25=0.25\) to \(Q\). Splitting a triangle into a pair and a singleton gives a smaller contribution. If the pair is connected by a weight-0.8825 edge, its contribution plus that of the singleton is approximately 0.0438; if the pair is joined by the 0.6065 edge, the combined contribution is approximately -0.0053. Three singleton communities contribute a negative amount because they have no internal edges but retain positive degrees. The same calculations apply to the other triangle. Also, merging the two intact triangles leaves internal weight unchanged but increases the squared degree penalty, so it lowers \(Q\). Thus, for this graph and objective, retaining each triangle as a community gives the best of these partitions.
This direct check illustrates what the algorithm is trying to optimize; it does not establish that modularity is the only reasonable objective. The resolution parameter changes the balance between within-community edge weight and the degree-based penalty. Other community-detection approaches covered in earlier material, including label propagation, Walktrap, Infomap, spectral clustering, and the Constant Potts Model, use different procedures or objectives. They need not return the same partition, even when given the same graph.
Worked Example: Recheck the Partition With \(k=1\)
To see why the neighbor setting must be reported, suppose we construct a second graph with \(k=1\), retaining union symmetrization and the same distance. At the tie for B, choose A; at the tie for E, choose D. The directed selections are A to B, B to A, C to B, D to E, E to D, and F to E. After symmetrization, the edges are AB, BC, DE, and EF. Each is a distance-0.1 edge with weight 0.8825. The graph is now two paths rather than two triangles.
For the partition \(\{A,B,C\}\), \(\{D,E,F\}\), the total weight is \(m=4(0.8825)=3.530\). Each path has internal weight \(l_c=2(0.8825)=1.765\), and its degree sum is \(K_c=3.530\). Therefore,
This setting gives the same two-group partition and the same modularity value, but it does not give the same graph: the distance-0.2 edges have disappeared. Equal objective values here should not be taken as a general guarantee that changing \(k\) leaves clustering unchanged.
Diagnostics, Choices, and Limits
An end-to-end analysis is reproducible only if it reports enough information to rebuild the graph and identify the community objective. For this example, that means reporting the input representation and distance, \(k=2\), how ties are handled, union symmetrization, no self-loops, the Gaussian weighting formula and \(\sigma=0.2\), and the community method and resolution. For a randomized method, report the random seed or describe how variability across runs was assessed.
Several checks can reveal construction problems before interpreting labels:
- Check distances and scales. Confirm that profile coordinates are on comparable scales and that the chosen distance reflects the intended notion of similarity. A coordinate with an unintended larger scale can dominate Euclidean distance.
- Inspect neighbor ties and edge counts. State a deterministic tie rule when ties occur at the selection boundary. Confirm that symmetrization is applied as described and that each undirected edge is counted once.
- Look for isolated cells or unexpected components. The toy graph has two connected components because the triples are far apart under the selected distance and \(k\). In real data, an isolated vertex or a large unexpected component can signal a construction choice that deserves inspection; disconnection alone does not establish a biological boundary.
- Check weights and settings. Weights should follow the stated formula, be positive here, and decrease as distance increases. A bandwidth that is too small can make many weights nearly zero; one that is too large can make distances contribute little to weight differences.
- Compare plausible settings. As the \(k=1\) calculation showed, similar partitions can arise from different edge sets. Conversely, a modest change in \(k\), distance, symmetrization, or weighting may alter connectivity and the resulting partition.
These checks diagnose the construction and interpretation of this worked graph; they do not validate a clustering as a biological classification. The example’s clean separation was built into the coordinates, and its small size makes exhaustive checking possible. Real single-cell graphs are larger, often have uneven density and ambiguous community boundaries, and may produce multiple high-scoring partitions. Community assignments summarize relationships under specified choices; they are not direct measurements of cell identity.
Check Your Understanding
Try each question, then compare your reasoning with the solutions below.
- With \(k=2\), why does the tie for cell B not make the neighbor set ambiguous in the six-cell example?
- Using \(\sigma=0.2\), calculate the Gaussian weight for a selected edge of distance 0.2.
- In the \(k=1\) graph, what are the total edge weight and the internal weight of each of the two path communities?
- Does modularity \(Q=0.5000\) mean that 50% of the cells were correctly assigned? Explain.
Solutions. (1) B’s two tied nearest cells, A and C, both fit within the two available neighbor positions, so both are selected. (2) \(w=\exp[-0.2^2/(2(0.2)^2)]=\exp(-0.5)\approx0.6065\). (3) There are four edges, each of weight 0.8825, so \(m=4(0.8825)=3.530\); each path has two edges, giving internal weight \(2(0.8825)=1.765\). (4) No. Modularity is an objective value comparing within-community edge weight with a degree-based expectation for the specified graph; it is not an accuracy rate or a proportion of correctly labeled cells.