The Constant Potts Model Objective

Why a Different Objective?

A weighted cell graph represents cells as vertices and similarities between cells as edge weights. Community detection seeks a partition of those vertices, but the partition depends on the objective being optimized. The Constant Potts Model (CPM) scores a partition by rewarding within-community edge weight while charging a penalty for putting pairs of vertices in the same community. Its merge rule makes the role of community size and the resolution parameter especially explicit.

This is useful when comparing CPM with modularity, whose resolution limit was the subject of the earlier material on the resolution limit of modularity. CPM has a direct pairwise threshold: a merge is favorable when the total weight between two communities exceeds the resolution penalty for their possible vertex pairs. That criterion is exact for the proposed merge, but it is not by itself a guarantee that the resulting partition is globally optimal or biologically meaningful.

Definition for an Undirected Weighted Graph

Let \(G=(V,E)\) be an undirected graph with \(n\) vertices. Write \(w_{ij}=w_{ji}\geq 0\) for the edge weight between distinct vertices \(i\) and \(j\), using \(w_{ij}=0\) when no edge is present. Assume there are no self-loops. A partition assigns every vertex to exactly one community. Let \(\delta(c_i,c_j)=1\) when vertices \(i\) and \(j\) are in the same community and \(0\) otherwise.

Definition: Under the unordered-pair convention used here, the Constant Potts Model objective for a partition is

Q_{\gamma}=\sum_{i<j}(w_{ij}-\gamma)\,\delta(c_i,c_j),

where \(\gamma\geq 0\) is the resolution parameter. CPM seeks a partition that maximizes \(Q_{\gamma}\).

Each pair placed together contributes its edge weight minus \(\gamma\). An edge with weight greater than \(\gamma\) contributes positively when its endpoints are grouped; a pair with weight below \(\gamma\), including a non-edge with weight zero, contributes negatively. Pairs in different communities contribute zero. The objective therefore evaluates both observed similarity and the number of vertex pairs grouped together.

For a community \(C\), let \(W_C=\sum_{i<j,\ i,j\in C}w_{ij}\) be its total internal edge weight. Its contribution to the objective is

Q_{\gamma}(C)=W_C-\gamma { |C| \choose 2}.

The full objective is the sum of these contributions over communities. A singleton has contribution zero because it contains no vertex pairs. The resolution parameter has the same units as an edge weight: if weights measure similarity on a zero-to-one scale, \(\gamma\) is on that scale too. If all edge weights and \(\gamma\) are multiplied by the same positive constant, every partition score is multiplied by that constant, so the maximizing partition does not change.

Deriving the Merge-versus-Split Rule

Consider two distinct communities \(A\) and \(B\), of sizes \(n_A\) and \(n_B\). Let \(W_{AB}=\sum_{i\in A}\sum_{j\in B}w_{ij}\) be their total cross-community edge weight. Compare the partition that keeps them separate with the partition that merges them, leaving all other communities unchanged.

Result: The change in CPM objective from merging \(A\) and \(B\) is

$$ \Delta Q_{\mathrm{merge}} =Q_{\mathrm{merged}}-Q_{\mathrm{separate}} =W_{AB}-\gamma n_A n_B. $$ A positive value favors merging; a negative value favors keeping these communities separate for this comparison; and zero means the two choices tie in objective value.

To justify the result, note that all pairs within \(A\), all pairs within \(B\), and all pairs belonging to other communities are grouped both before and after the merge. Their contributions cancel in the difference. Before merging, each of the \(n_A n_B\) cross-community pairs contributes zero. After merging, each contributes \(w_{ij}-\gamma\). Therefore

\Delta Q_{\mathrm{merge}} =\sum_{i\in A}\sum_{j\in B}(w_{ij}-\gamma) =\sum_{i\in A}\sum_{j\in B}w_{ij}-\gamma n_A n_B =W_{AB}-\gamma n_A n_B.

The merge is favorable precisely when the average cross-community weight, \(W_{AB}/(n_A n_B)\), exceeds \(\gamma\). The denominator counts all possible cross-community pairs, not only pairs connected by observed edges. Thus non-edges count as zero-weight pairs and still contribute to the resolution penalty.

Worked Example: A Merge That Loses Objective Value

Suppose community \(A\) contains 4 cells and community \(B\) contains 3 cells. Across the 12 possible cross-community pairs, three edges have weights \(0.40\), \(0.30\), and \(0.20\), while the other nine pairs have weight zero. Let \(\gamma=0.10\). Should the two communities be merged?

The total cross-community weight is \(W_{AB}=0.40+0.30+0.20=0.90\). There are \(n_A n_B=4\times 3=12\) possible pairs, so the merge penalty is \(\gamma n_A n_B=0.10\times 12=1.20\).

\Delta Q_{\mathrm{merge}}=0.90-1.20=-0.30.

The objective would decrease by \(0.30\) if these two communities were merged, so keeping them separate has the higher CPM score for this comparison. Equivalently, their average cross-pair weight is \(0.90/12=0.075\), below \(\gamma=0.10\). The fact that three observed edges connect the communities does not alone determine the decision; their total weight must be compared with the penalty across all 12 pairs.

Worked Example: A Merge That Improves the Objective

Now let \(A\) contain 2 cells and \(B\) contain 3 cells. Suppose the six cross-pair weights are \(0.35\), \(0.20\), \(0.15\), \(0.10\), \(0\), and \(0\), and let \(\gamma=0.10\). Calculate the objective change.

The total weight is \(W_{AB}=0.35+0.20+0.15+0.10=0.80\), and the penalty is \(0.10\times(2\times3)=0.60\). Thus

\Delta Q_{\mathrm{merge}}=0.80-0.60=0.20.

Because the change is positive, merging raises the CPM objective by \(0.20\). The average cross-pair weight is \(0.80/6\approx0.1333\), which exceeds the resolution parameter. The two zero-weight pairs are included in the average and penalty calculation.

How Resolution Changes the Decision

For fixed communities and edge weights, \(\Delta Q_{\mathrm{merge}}=W_{AB}-\gamma n_A n_B\) decreases linearly as \(\gamma\) increases. The exact tie occurs at

\gamma^{*}=\frac{W_{AB}}{n_A n_B}.

Below this threshold, the merge improves the objective; above it, the split scores better. Increasing \(\gamma\) therefore makes merges less favorable and generally encourages finer partitions. Decreasing \(\gamma\) makes it easier for communities to merge. This describes the direction of the effect, not a guarantee that every higher-\(\gamma\) partition is a simple refinement of every lower-\(\gamma\) partition.

Worked Example: Finding the Merge Threshold

Suppose \(A\) has 3 vertices, \(B\) has 2 vertices, and the total weight of their six possible cross-pairs is \(0.40\). Find the resolution value at which merging ties with keeping them separate, then evaluate the decision at \(\gamma=0.05\) and \(\gamma=0.08\).

There are \(3\times2=6\) cross-pairs. The tie threshold is

\gamma^{*}=\frac{0.40}{6}\approx0.06667.

At \(\gamma=0.05\), the merge change is \(0.40-(0.05\times6)=0.10\), so merging improves the objective by \(0.10\). At \(\gamma=0.08\), it is \(0.40-(0.08\times6)=-0.08\), so keeping the communities separate scores higher by \(0.08\). At \(\gamma\approx0.06667\), the two choices tie, up to rounding.

Assumptions, Diagnostics, and Alternatives

The formula assumes an undirected graph with nonnegative edge weights and no self-loops, and it uses the stated convention of counting each unordered pair once. Other software may express the objective by summing over ordered pairs, which can introduce a factor of two. Such a factor does not change the maximizing partition if the entire objective is scaled consistently, but the definition of \(\gamma\) must match the implementation. A resolution value should not be transferred blindly between implementations with different conventions or differently scaled edge weights.

A useful diagnostic is to inspect candidate merges through the ratio \(W_{AB}/(n_A n_B)\). If proposed merges occur despite ratios below \(\gamma\), check whether the implementation uses the same weight scale, graph direction, and objective convention. Also check whether self-loops or edge transformations are present, since they can alter a software implementation’s score. A reported partition should be evaluated using the objective actually specified by the method, not inferred from the number of edges alone.

CPM’s merge criterion is local to the two communities being compared: it depends on their cross-weight, sizes, and \(\gamma\), not on the total weight of the entire graph. This avoids the particular global-size dependence in modularity’s merge comparison. But CPM still depends on a meaningful weight scale and a chosen \(\gamma\). If weights are rescaled without rescaling \(\gamma\), merge decisions can change. Moreover, maximizing CPM does not establish that communities correspond to cell types, and a heuristic optimization algorithm may fail to find the global maximum.

Approach	What drives the comparison	Practical distinction
Constant Potts Model	Cross-community weight compared with \(\gamma n_A n_B\)	Uses an explicit threshold on average cross-pair weight.
Modularity	Observed within-community weight compared with a degree-based null expectation	Its resolution and merge comparison depend on graph-wide quantities.
Graph cut objectives	Weight of edges crossing community boundaries, often with a size normalization	Focus on boundary edges rather than the CPM pairwise reward-and-penalty score.

These objectives answer related but different questions. CPM is appropriate when a constant edge-weight threshold is a useful description of within-community structure. It may be less suitable if weights have no stable scale or if a constant threshold is scientifically implausible. In single-cell analysis, it is an objective for grouping vertices in a constructed graph; it is not a model of gene expression counts or a direct test of biological identity.

Common Pitfall

A common error is to compare the total cross-community weight with \(\gamma\) alone: “There are edges between the communities, and their total weight is greater than \(0.10\), so merge them.” That reasoning omits the number of possible cross-pairs. The correct comparison is \(W_{AB}\) versus \(\gamma n_A n_B\). For example, a total weight of \(0.90\) supports merging at \(\gamma=0.10\) when there are 6 possible cross-pairs, but not when there are 12: the corresponding penalties are \(0.60\) and \(1.20\). Always state the community sizes as well as the cross-edge weights.

Key takeaway: Under the unordered-pair CPM convention, merge \(A\) and \(B\) when \(W_{AB}>\gamma n_A n_B\). The threshold is the average weight over all possible cross-community pairs, and \(\gamma\) must be interpreted on the graph’s edge-weight scale.

Check Your Understanding

Work each problem using the CPM convention defined above. Solutions follow the questions.

Two communities have sizes 2 and 4, total cross-community weight \(0.50\), and \(\gamma=0.05\). What is the objective change from merging?
For two communities with 5 and 2 vertices, \(W_{AB}=0.70\). What is the tie value of \(\gamma\)?
Explain why zero-weight non-edges are included when calculating the merge penalty.
If all edge weights and \(\gamma\) are multiplied by 3, does the CPM maximizing partition change? Explain.

Solutions. (1) There are \(2\times4=8\) cross-pairs, so \(\Delta Q=0.50-(0.05\times8)=0.10\); merging improves the objective by \(0.10\). (2) There are \(5\times2=10\) pairs, so \(\gamma^{*}=0.70/10=0.07\); at this value the alternatives tie. (3) Every pair placed in the same community incurs the \(\gamma\) penalty, whether or not an edge is observed; a non-edge has weight zero but still contributes \(-\gamma\). (4) No. Every partition score is multiplied by 3, preserving the ordering of scores and thus the maximizing partition.