Choosing a Clustering Resolution from Graph Structure

Why Resolution Requires a Graph-Structure Check

A clustering resolution controls how readily a graph partition separates vertices into communities. A low resolution often favors fewer, larger communities; a high resolution often favors more, smaller ones. Neither direction is automatically better for a cell graph. A partition can be too coarse to distinguish densely connected groups, or so fragmented that many small communities have little structural support.

The Constant Potts Model (CPM) provides a direct way to relate resolution to graph structure: it rewards edges within communities and penalizes the possible vertex pairs assigned to the same community. This makes community sizes, internal densities, and between-community edge densities especially useful when comparing candidate resolutions. They are diagnostics, not a rule that identifies a universally correct resolution or proves that a graph community is a biological cell type.

Resolution and Community Density

Consider a fixed, undirected graph with no self-loops. For simplicity, first suppose it is unweighted, so an edge is either present or absent. For a community \(C\), let \(n_C\) be its number of vertices and let \(e_C\) be the number of edges whose two endpoints are both in \(C\). Its internal edge density is the fraction of possible within-community pairs that are edges.

Definition: For a community \(C\) with \(n_C \geq 2\), its size is \(n_C\), and its internal edge density is \(d_C = e_C / \binom{n_C}{2}\). The density ranges from 0 to 1. For a singleton community, there are no possible within-community pairs, so this density is undefined.

For a partition \(\mathcal{P}\), the unweighted CPM objective is the total number of within-community edges minus a resolution penalty for each possible within-community pair:

Q_{\mathrm{CPM}}(\mathcal{P};\gamma) = \sum_{C\in\mathcal{P}} \left[e_C-\gamma\binom{n_C}{2}\right].

Here \(\gamma\) is the resolution parameter, and the partition with the larger objective is preferred by this objective at that particular \(\gamma\). Because \(\binom{n_C}{2}\) grows with community size, the penalty is larger for a large community than for a small one at the same \(\gamma\). For \(n_C \geq 2\), a community’s contribution can also be written as \(\binom{n_C}{2}(d_C-\gamma)\). Thus, its internal density compared with \(\gamma\) helps describe its contribution, but does not by itself determine whether the whole partition is best.

If the graph is weighted, replace \(e_C\) with the sum of within-community edge weights. The objective then uses weight units, so \(\gamma\) must be on the same scale. If all weights are multiplied by a constant, \(\gamma\) must be multiplied by that constant to preserve the same trade-off. Density comparisons below refer to binary edges unless stated otherwise.

Worked Example: Interpreting Internal Density at a Fixed Resolution

Suppose a hypothetical unweighted cell graph has a community of 5 vertices and 7 internal edges. At \(\gamma=0.4\), calculate its density and its contribution to the CPM objective.

There are \(\binom{5}{2}=5(4)/2=10\) possible pairs within the community. Therefore,

d_C=\frac{7}{10}=0.70, \qquad Q_C=7-0.4(10)=3.0.

The density exceeds the resolution, and the contribution is positive. This describes the community’s contribution to this objective, not a guarantee that the community should remain intact: a different partition could have a larger total objective. For comparison, a community of 3 vertices with all 3 possible edges has density \(3/3=1\), but contributes only \(3-0.4(3)=1.8\). A smaller community can have higher density and still contribute less because it contains fewer possible pairs.

Using Between-Community Density to Assess Merges

Community sizes and internal densities do not fully describe the boundary between two groups. For communities \(A\) and \(B\), let \(n_A\) and \(n_B\) denote their sizes, and let \(e_{AB}\) be the number of edges with one endpoint in each. There are \(n_A n_B\) possible cross-community pairs. Their between-community density is \(e_{AB}/(n_A n_B)\). The CPM objective gives a precise merge comparison.

\begin{aligned} Q_{\mathrm{merged}}-Q_{\mathrm{separate}} &=e_{AB}-\gamma n_A n_B\\ &=n_A n_B\left(\frac{e_{AB}}{n_A n_B}-\gamma\right). \end{aligned}

The merged community includes all the cross-community edges and incurs a penalty for all \(n_A n_B\) newly co-assigned pairs. Therefore, merging improves the objective exactly when \(e_{AB}/(n_A n_B)>\gamma\); separating is preferred in this two-community comparison when the inequality is reversed. Equality gives a tie. This is a local comparison between the two specified choices, not proof that either choice is globally optimal among all partitions.

Worked Example: Checking Whether Two Communities Should Merge

Suppose two hypothetical groups have sizes \(n_A=4\) and \(n_B=3\), with 4 edges between them. The cross-community density is \(4/(4\cdot3)=4/12=0.3333\). Compare keeping them separate with merging them at two resolutions.

At \(\gamma=0.25\), the change in objective from merging is

\Delta Q=4-0.25(4)(3)=4-3=1.

Merging increases the objective by 1, consistent with the cross-community density \(0.3333\) being greater than \(0.25\). At \(\gamma=0.40\),

\Delta Q=4-0.40(4)(3)=4-4.8=-0.8.

Now the objective favors keeping the groups separate in this comparison. The same graph boundary can therefore support a merge at one resolution and a split at another; the resolution is part of the clustering decision.

Using Internal Structure to Assess Splits

The merge comparison also gives a direct split comparison. Suppose a community of size \(n\) is divided into two nonempty parts of sizes \(n_1\) and \(n_2\). Let \(e_{\mathrm{cross}}\) count edges between those parts. The split removes those edges from the within-community total, but avoids the CPM penalty on the \(n_1n_2\) pairs that are no longer co-assigned. Subtracting the unsplit objective from the split objective gives

Q_{\mathrm{split}}-Q_{\mathrm{unsplit}} = -e_{\mathrm{cross}}+\gamma n_1n_2.

Thus, this split improves the objective when the density across the proposed boundary, \(e_{\mathrm{cross}}/(n_1n_2)\), is below \(\gamma\). The calculation depends on the proposed split: a community may have several possible internal divisions with different cross densities.

Worked Example: Testing a Proposed Split

A hypothetical community of 6 vertices is proposed to split into two groups of 3. There are 2 edges between the groups, out of \(3\cdot3=9\) possible cross pairs. There are 6 edges within the two groups combined. Compare the split and unsplit objective values at \(\gamma=0.30\), then at \(\gamma=0.20\).

The cross density is \(2/9=0.2222\). At \(\gamma=0.30\), the split’s objective advantage is

Q_{\mathrm{split}}-Q_{\mathrm{unsplit}} =-2+0.30(3)(3)=-2+2.7=0.7.

For a direct check, the unsplit community has 8 total edges and 15 possible pairs, so its contribution is \(8-0.30(15)=3.5\). The split has 6 within-group edges and \(3+3=6\) possible within-group pairs, so its contribution is \(6-0.30(6)=4.2\). The difference is \(4.2-3.5=0.7\), as calculated.

At \(\gamma=0.20\), the split advantage is \(-2+0.20(9)=-0.2\). The unsplit contribution is \(8-0.20(15)=5.0\), while the split contribution is \(6-0.20(6)=4.8\). For this proposed division, the objective now favors leaving the community intact.

A Practical Resolution Diagnostic

A useful resolution check compares a small set of candidate values on the same graph, with the same edge construction and weights. For each resulting partition, examine community-size distributions, internal densities, and densities between communities that appear to be merge or split candidates. The calculations above help connect those summaries to the CPM trade-off. Use them to identify plausible ranges and warning signs, not to choose a value by a mechanical threshold alone.

Fix the graph and its edge scale.
Keep the vertices, edges, weights, and preprocessing constant across candidate resolutions. Otherwise, a change in the partition cannot be attributed to resolution alone.

Summarize community sizes.
Record the number of communities and their sizes. Many tiny groups or one exceptionally large group may prompt investigation, but neither pattern alone establishes that the resolution is wrong.

Inspect internal and boundary densities.
Look for small groups with weak internal support, or proposed splits whose cross densities are low relative to \(\gamma\). For possible merges, compare between-community density with \(\gamma\).

Compare partitions at nearby values.
Determine whether small resolution changes cause a striking shift in sizes or boundaries. Treat such transitions as a reason to inspect the graph and modelling choices, not as automatic evidence for one value.

Report the choice and its limits.
State the graph, objective, resolution, and structural evidence used. Explain that the result is a graph partition whose biological interpretation requires evidence beyond these diagnostics.

An important comparison rule follows from the objective’s definition: raw CPM objective values at different resolutions are not directly comparable as if they were scores from one fixed criterion. Changing \(\gamma\) changes the penalty and therefore changes the objective being optimized. Instead, compare the structures of the resulting partitions and use the merge and split calculations at each stated resolution.

Alternatives, Failure Modes, and Limits

Resolution-parameter modularity clustering also allows a resolution choice, but it uses a different objective and its resolution scale does not have the CPM density interpretation given here. Do not transfer a numerical value of \(\gamma\) between objectives as though it represented the same cutoff. CPM’s advantage for this diagnostic is that its merge and split comparisons reduce to edge density versus resolution. Its limitation is that the result still depends on the chosen graph and objective.

Structural summaries can also mislead if treated as standalone quality scores. High internal density does not prove that a community is biologically coherent; low density may reflect graph construction or heterogeneous connectivity rather than an inappropriate resolution. Size is not a substitute for density or boundary inspection: a large community can be well supported, and a small one can be structurally distinct. The introductory material on the Constant Potts Model objective establishes the objective being optimized; here, the key use is to interpret candidate resolutions in relation to observed graph structure.

Mistake: “The largest CPM objective across resolution values identifies the best resolution.” The penalty changes with \(\gamma\), so these are different objective functions. Compare partition structure at each value instead.
Mistake: “Every community must have internal density above \(\gamma\), so all others are invalid.” That comparison describes an individual community’s contribution, not whether the entire partition is globally optimal. Alternative partitions and their total contributions matter.
Mistake: “A high-resolution partition with many communities is necessarily overfragmented.” A large community may contain weakly connected subgroups, and a small community may have strong graph support. Inspect boundaries and sizes together.
Mistake: “The resolution with the most balanced community sizes is best.” Balance is not part of the CPM objective. Prefer neither equal sizes nor a particular number of communities without a substantive reason.

Finally, graph structure alone cannot establish the correct biological granularity. A resolution is a modelling choice, and several values may yield partitions that are useful for different analyses. Report the choice transparently, including the edge scale and the structural checks, rather than presenting one value as universally correct.

Check Your Understanding

Answer each question using the CPM objective and the stated graph quantities. Complete solutions follow.

A community has 4 vertices and 4 internal edges. What is its internal density, and what is its CPM contribution at \(\gamma=0.50\)?
Two groups have sizes 2 and 5, with 3 edges between them. At what cross-density threshold does the merge comparison change preference?
A proposed split separates groups of sizes 2 and 4, with 2 cross edges. Does the CPM objective favor this split at \(\gamma=0.20\)?
Why should raw CPM objective values from two different resolutions not be treated as directly comparable model-selection scores?

Solutions. (1) There are \(\binom{4}{2}=6\) possible pairs, so \(d=4/6=0.6667\). The contribution is \(4-0.50(6)=1.0\). (2) There are \(2\cdot5=10\) possible cross pairs, so the threshold is \(3/10=0.30\). The merge is favored above this density threshold in the sense that the between-community density must exceed \(\gamma\); at \(\gamma=0.30\), this comparison is a tie. (3) The split advantage is \(-2+0.20(2)(4)=-2+1.6=-0.4\), so this proposed split is not favored over leaving the group intact. (4) Changing resolution changes the penalty term and therefore changes the objective function; compare the resulting partitions and their graph structure rather than ranking the raw values as though they measured the same criterion.