Common Mistakes in Graph-Based Cell Clustering

Why Graph-Clustering Errors Are Easy to Miss

A graph-based clustering result depends on more than the name of the community-detection algorithm. It also depends on which cells are connected, whether connections have direction, what edge weights represent, and which objective and parameter settings are used. If these choices are changed or left undocumented, two partitions may differ for reasons that cannot be attributed to the clustering method alone.

The practical goal is to keep distinct decisions distinct: construct and describe the cell graph; choose how the clustering method uses that graph; then interpret the resulting groups as computational partitions. A cluster is a grouping produced under those choices. Biological interpretation requires evidence beyond the fact that an algorithm assigned the cells to the same group.

Definition: A cell graph is \(G=(V,E,A)\), where each vertex \(i\in V\) represents a cell, \(E\) is the set of edges, and \(A_{ij}\) records the connection from vertex \(i\) to vertex \(j\). The graph is directed if an edge from \(i\) to \(j\) need not imply an edge from \(j\) to \(i\). It is weighted if \(A_{ij}\) can take values beyond 0 and 1. A partition assigns every vertex to one cluster.

Do Not Silently Turn Directed Edges Into Undirected Ones

Direction can arise naturally in a graph construction. For example, a cell may select another cell among its nearest neighbors without the reverse selection also occurring. Treating such a graph as undirected changes its edge structure. There is no universal rule that makes this change harmless: the appropriate rule depends on what the directed edge represents and on the method that will use the graph.

Common choices include retaining an edge if either direction is present, requiring both directions, or combining the two directional weights by a specified function. These choices answer different questions. A union rule preserves one-sided neighbor selections; a mutual-neighbor rule retains only reciprocal selections. A numerical combination such as a sum or mean retains some information about directional weights, but changes their values. State the rule and apply it consistently. If the clustering method is designed for a directed graph, do not symmetrize merely because an undirected method is more familiar.

Worked Example: Making a Symmetrization Rule Explicit

Suppose a hypothetical directed graph has three cells, A, B, and C. Its nonzero directed edge weights are \(A_{AB}=4\), \(A_{BC}=2\), \(A_{CB}=2\), and \(A_{CA}=1\). All other directed weights are zero. Compare three possible undirected weights for each pair.

Under the sum rule, set the undirected weight for a pair \(i,j\) to \(A_{ij}+A_{ji}\). The resulting weights are AB: \(4+0=4\), BC: \(2+2=4\), and AC: \(0+1=1\).

Under the mean rule, set it to \((A_{ij}+A_{ji})/2\). The weights are AB: \(4/2=2\), BC: \(4/2=2\), and AC: \(1/2=0.5\).

Under the mutual rule, retain a pair only when both directions are present, with weight equal to the smaller directional weight. AB is omitted because \(A_{BA}=0\), BC has weight \(\min(2,2)=2\), and AC is omitted because \(A_{AC}=0\). Thus these are not three notations for the same graph: they produce different edge sets or weights. A result reported only as “undirected” is not reproducible without the rule.

Do Not Discard Edge Weights Without Saying So

An edge weight may encode the strength of an affinity, a similarity, or another quantity defined by the graph-construction procedure. Replacing each positive weight with 1 creates a binary graph: it preserves whether an edge exists but discards the distinction between stronger and weaker connections. A weighted method and an unweighted method can therefore respond differently to the same edge list.

For a concrete comparison, consider the undirected weighted modularity objective. In the following expression the graph is assumed to be undirected, nonnegative, and without self-loops; \(A_{ij}=A_{ji}\), \(k_i=\sum_j A_{ij}\), and \(m=\frac12\sum_{ij}A_{ij}\) is total edge weight. The cluster assignment of cell \(i\) is \(c_i\), and \(\gamma\) is the resolution parameter.

Q_\gamma=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\gamma\frac{k_i k_j}{2m}\right)\mathbf{1}(c_i=c_j)

Here \(\mathbf{1}(c_i=c_j)\) equals 1 when two cells share a cluster and 0 otherwise. This objective uses edge weights both in the observed within-cluster connection term and in the degree-based reference term. If weights are discarded, both terms are calculated from a different graph. The resulting value is not a weighted score with a minor adjustment; it is the score for another input graph.

Worked Example: Weighted and Binary Graphs Can Rank Partitions Differently

Consider a hypothetical undirected graph on cells A, B, C, and D. Its edges and weights are AB: 5, CD: 5, AC: 4, BD: 1, and BC: 1. Compare partition P, \(\{A,B\},\{C,D\}\), with partition R, \(\{A,C\},\{B,D\}\), at \(\gamma=1\).

For an undirected graph, the same modularity can be calculated as \(Q_\gamma=\sum_C [L_C/m-\gamma(K_C/(2m))^2]\), where \(L_C\) is the total weight of edges internal to cluster \(C\), and \(K_C\) is the sum of the degrees of its cells. The degrees here are \(k_A=9\), \(k_B=7\), \(k_C=6\), and \(k_D=6\); thus \(m=16\) and \(2m=32\).

For the weighted graph, partition P has internal weight \(L_{AB}+L_{CD}=5+5=10\). Its cluster degree sums are \(K_{AB}=9+7=16\) and \(K_{CD}=6+6=12\). Therefore,

Q_1(P)=\frac{10}{16}-\left(\frac{16}{32}\right)^2-\left(\frac{12}{32}\right)^2 =0.625-0.25-0.140625=0.2344

For R, internal weight is \(4+1=5\), and its degree sums are \(K_{AC}=15\) and \(K_{BD}=13\). Thus,

Q_1(R)=\frac{5}{16}-\left(\frac{15}{32}\right)^2-\left(\frac{13}{32}\right)^2 =0.3125-0.2197-0.1650=-0.07227

On the weighted graph, P scores higher than R. Now replace every positive edge weight with 1. The binary graph has five edges, degrees \(2,3,3,2\), and \(m=5\). Each partition has two internal edges and cluster degree sums of 5 and 5, so each scores \(2/5-(5/10)^2-(5/10)^2=-0.1\). The binary graph erases P’s advantage over R in this comparison. This calculation does not claim that every clustering algorithm will return either partition; it shows exactly how binarizing can change information used to compare partitions.

Keep Resolution Separate From Graph Construction

For a fixed graph and fixed clustering objective, changing \(\gamma\) changes the objective’s relative weighting of observed within-cluster edges and its degree-based reference term. It does not, by definition, add or remove graph edges. By contrast, changing a neighbor count, a distance metric, a pruning threshold, or a symmetrization rule can alter the graph itself. If both types of settings change together, a difference in the partition cannot be attributed to resolution alone.

The distinction can be seen directly for the undirected modularity objective above. Grouping the terms for each cluster gives the community form

Q_\gamma=\sum_C\left(\frac{L_C}{m}-\gamma\left(\frac{K_C}{2m}\right)^2\right)

The observed internal weight \(L_C\), total weight \(m\), and degree sum \(K_C\) all come from the graph. Holding that graph fixed holds those quantities fixed; only the multiplier \(\gamma\) changes. This is why changing resolution and changing graph construction are analytically different operations.

Worked Example: Compare Resolutions on One Fixed Graph

Take a hypothetical undirected graph with edges AB: 3, CD: 3, and BC: 1. Keep this graph fixed. It has \(m=7\), degrees \(3,4,4,3\), and consider partition P, \(\{A,B\},\{C,D\}\), alongside the partition into four single-cell clusters.

For P, each two-cell cluster has internal weight 3 and degree sum 7. Its score at resolution \(\gamma\) is therefore

Q_\gamma(P)=2\left(\frac{3}{7}-\gamma\left(\frac{7}{14}\right)^2\right) =\frac{6}{7}-\frac{\gamma}{2}

At \(\gamma=1\), this is \(6/7-1/2=0.3571\). For four single-cell clusters, every \(L_C=0\), so

Q_\gamma(\text{singletons})=-\gamma\frac{3^2+4^2+4^2+3^2}{14^2} =-\gamma\frac{50}{196}

At \(\gamma=1\), the singleton score is \(-50/196=-0.2551\), so P scores higher among these two candidates. At \(\gamma=4\), P scores \(6/7-2=-1.1429\), while the singleton partition scores \(-200/196=-1.0204\). The ranking of these two candidate partitions reverses although the graph has not changed. This comparison illustrates the role of resolution; it does not establish that either candidate is the global optimum among all possible partitions.

Clusters Are Not Proven Cell Types

A graph-clustering algorithm assigns cells to groups according to graph structure and its objective. It does not directly test whether each group corresponds to a distinct biological cell type. A cluster may be a useful candidate population, but its interpretation depends on the data, preprocessing, graph construction, clustering settings, and supporting biological evidence.

For example, suppose a hypothetical cluster contains 12 cells and 9 have detectable expression of a marker gene. That observation can motivate an annotation, but it does not establish that all 12 cells belong to a known cell type. Marker detection can be affected by measurement depth and other technical and biological factors; a marker may also be shared across populations. An annotation should therefore be described as supported, tentative, or unresolved in proportion to the evidence. Do not write that clustering “proves” a cell identity.

This distinction also prevents a circular argument: a group is not a validated type merely because its cells were grouped together and then given a type name. Cluster membership is an algorithmic result; a biological label is an interpretation that needs independent support and careful qualification.

A Practical Diagnostic Checklist

Record the graph definition.
State how cells became vertices, how edges were constructed, whether the graph is directed, and what weights represent.

Make transformations explicit.
For symmetrization, pruning, or binarization, specify the rule and distinguish the transformed graph from the original.

Separate graph settings from clustering settings.
When examining resolution, hold the graph and objective fixed. When changing graph construction, describe that as a separate analysis choice.

Check for mismatches and report them.
Confirm that the algorithm accepts the graph’s direction and weight structure, and that the reported settings match those actually used.

Use appropriately cautious labels.
Report clusters as computational groups first; state the evidence and uncertainty behind any biological annotation.

Useful warning signs include a graph described as directed but passed to a method that assumes undirected input without a stated conversion; non-binary weights that disappear from the analysis without explanation; a resolution comparison in which the neighbor graph also changes; and cell-type labels presented as direct algorithmic outputs. These are not necessarily proof that the results are unusable, but they make the analysis difficult to interpret or reproduce until clarified.

Common Mistakes and Their Corrections

Wrong: “The graph was made undirected because the clustering method needs an undirected graph.” Correction: Name the conversion rule and explain what it retains or discards.
Wrong: “Weights are just stronger versions of edges, so replacing them with 1 cannot matter.” Correction: Binarization changes the graph values used by weighted procedures and can change comparisons between partitions.
Wrong: “The clusters changed when resolution changed, so resolution changed the neighborhood graph.” Correction: Resolution changes an objective parameter; check separately whether graph-construction settings were also changed.
Wrong: “The algorithm found a cluster, therefore it found a cell type.” Correction: A cluster is an algorithmic grouping. Treat a cell-type label as an interpretation requiring supporting evidence.

The central limitation is that careful reporting cannot make a graph a complete representation of biology. Graph-based partitions depend on the graph and method supplied to the algorithm, and different reasonable choices can yield different groupings. The purpose of these checks is not to declare one partition biologically correct; it is to make clear what was analyzed, what the result means, and what it does not establish.

Check Your Understanding

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

A directed neighbor graph contains an edge from cell X to cell Y but not from Y to X. What must be specified before describing an analysis as using an undirected graph?
In the four-cell weighted example, why did binarization change the comparison between partitions P and R?
For the fixed graph in the resolution example, what changed between \(\gamma=1\) and \(\gamma=4\): the graph or the objective parameter?
A cluster has high expression of one marker gene. Why is that not, on its own, proof of a cell-type identity?
Name one graph-construction setting and one clustering-objective setting. Explain why changing both at once complicates interpretation.

Solutions. (1) Specify a symmetrization rule, such as retaining either-direction edges, requiring mutual edges, or combining directional weights by a stated function. (2) In the weighted graph, P scored 0.2344 and R scored −0.07227; after replacing positive weights by 1, both scored −0.1. Binarization removed distinctions among edge strengths used by the weighted calculation. (3) The graph was held fixed; \(\gamma\), the objective’s resolution parameter, changed. (4) Marker expression can support an annotation, but a clustering algorithm assigns graph-based groups rather than testing cell-type identity; one marker alone is not sufficient proof. (5) A neighbor count is a graph-construction setting, while \(\gamma\) in the stated modularity objective is an objective setting. Changing both prevents attributing a partition change to either decision alone.