Network Cluster-Robust Inference
A cluster test needs group scores that are approximately independent. Dividing a network into named groups does not ensure this: links crossing a boundary may transmit dependence between their averages. (Leung 2023) gives conditions connecting the geometry of a partition to the stochastic independence needed for inference.
1. The inferential requirement
Let \(g(W_i,\theta_0)\) be a centered moment function on an observed network, and let \(\mathcal C_1,\ldots,\mathcal C_L\) be a partition. Define \(\widehat G_\ell=n_\ell^{-1}\sum_{i\in\mathcal C_\ell}g(W_i,\theta_0)\).
Theorem 1. Under the paper’s network dependence, moment, and neighborhood-growth conditions, the vector of normalized cluster moments has a joint Gaussian limit. The additional conductance and summability conditions make its off-diagonal covariance blocks vanish. With nondegenerate cluster variances and the other requirements of the chosen few-cluster procedure, this supplies the asymptotic independence needed for inference.
A joint Gaussian approximation is only the first step. If its off-diagonal covariances remain nonzero, changing one cluster’s sign need not preserve the joint law required by a few-cluster randomization test.
2. Conductance measures the boundary
For a set \(C\) with positive volume, write
Low conductance means that relatively few edges leave the group. One condition in the paper combines the largest cluster conductance with average graph degree: \(\max_\ell\phi(\mathcal C_\ell)\delta(A)\to0\). Additional restrictions control neighborhood growth and the decay of dependence with network distance.
The reason for controlling both graph geometry and dependence decay is visible in the cross-cluster covariance:
Split this sum into pairs near and far from the boundary. Nearby pairs may have large covariance, so their number must be small. Farther pairs may be numerous, so their covariance must decay sufficiently fast. Edges alone count only distance-one connections; the neighborhood bounds also account for longer paths.
3. Can suitable clusters exist?
The normalized graph Laplacian is \(\mathcal L=I-D^{-1/2}AD^{-1/2}\), with isolated vertices handled separately. Its small eigenvalues indicate weak connections between large pieces of the graph. For fixed \(L\), higher-order Cheeger inequalities relate the \(L\)th eigenvalue to the best achievable multiway conductance.
Small eigenvalues can guide the search for a low-conductance partition. The selected partition must still have suitable sizes and actual conductances, and the outcome model must satisfy the dependence and moment assumptions. The spectral calculation addresses only the graph part.
Some graphs have no suitable separation into the required number of substantial groups. A community algorithm will still return labels, but those labels do not establish independent cluster scores. In that setting the dependence and resampling notes discuss other approaches, each with its own dependence assumptions.
4. A concrete boundary calculation
Consider a simple special case: centered scalar \(g_i\) with uniformly bounded variances, maximum graph degree at most \(D\), and covariance zero whenever graph distance exceeds a fixed integer \(r\). Let \(B_r\) bound the number of vertices within distance \(r\) of any vertex; for bounded degree and fixed \(r\), \(B_r\) is bounded uniformly in \(n\).
If \(i\in C\), \(j\notin C\), and their distance is at most \(r\), a connecting path crosses an edge in \(\partial C\). Both endpoints of the pair lie within distance \(r\) of an endpoint of that edge. A crude but sufficient count is therefore
Cauchy–Schwarz bounds each covariance by a constant \(K\). If \(|C|,|D|\geq cn\), the normalized cross-cluster covariance satisfies
Thus \(|\partial C|=o(n)\) is enough in this special case. It captures the argument’s geometry: strong cross-cluster dependence is confined to a negligible boundary region. A separate CLT is still required to conclude that the limiting vectors are independent Gaussian variables.
For dependence that decays rather than vanishes, choose a radius \(r_n\) and split the covariance sum into near and far pairs. A crude far-pair bound, if \(|\operatorname{Cov}(g_i,g_j)|\leq\beta(r_n)\) beyond that radius, is of order \(n\beta(r_n)\) after normalization. One sufficient condition is therefore
This bound is deliberately coarser than the paper’s summability conditions. It displays the choice of radius: a larger radius reduces the far-pair covariance bound and increases the number of pairs counted near the boundary. Both terms must vanish.
The near/far split can be made quantitative on a graph with polynomial ball growth. Suppose \(B_r\leq C(1+r)^d\), \(|\partial C|\leq Cn^a\) with \(0\leq a<1\), and covariance decays exponentially, \(\beta(r)\leq Ce^{-cr}\). Choose \(r_n=K\log n\) with \(K>1/c\). The sufficient bound becomes
For a rectangular cluster in a \(d\)-dimensional lattice, its volume is of order \(n\) and its boundary is of order \(n^{(d-1)/d}\), so this argument applies. The logarithmic neighborhood around the boundary still occupies a negligible fraction of the cluster. It gives an explicit route from local dependence to vanishing cross-cluster covariance.
If the balls instead grow exponentially, \(B_r\leq Ce^{\gamma r}\), this same bound requires both \(K>1/c\) and \(a-1+2\gamma K<0\). Such a \(K\) exists only when \(c>2\gamma/(1-a)\). This is a sufficient condition from a deliberately coarse count, not a necessary condition from the paper. It shows why the rate at which neighborhoods grow must be compared with the rate at which dependence decays. Community labels and a small conductance number cannot make that comparison on their own.
These calculations identify the step needed before applying a cluster test: show that the proposed averages have asymptotically independent limits. The graph must permit a partition for which the dependence bounds actually give that conclusion.
5. Why average degree appears with conductance
The identity \(|\partial C|=\phi(C)\operatorname{vol}(C)\) connects the graph partition to the covariance count. Summing over a fixed number of clusters,
The average degree is \(\delta(A)=n^{-1}\sum_i d_i\). When it grows, even a small fraction of crossing edges can be a large number. The conductance-degree product controls that count; moment and neighborhood restrictions then bound the covariance it can produce.
6. The spectral calculation behind a graph cut
For an undirected graph without isolated vertices, let \(v=D^{1/2}h\). Then the normalized-Laplacian quadratic form is
Take \(h=\mathbf1_C\). Only crossing edges contribute, and the Rayleigh quotient is \(|\partial C|/\operatorname{vol}(C)=\phi(C)\). To compare with the second eigenvalue, remove the constant direction by taking
Then \(\sum_i d_ih_i=0\), so \(v\) is orthogonal to the zero-eigenvalue vector \(D^{1/2}\mathbf1\). Substitution gives
The variational characterization of \(\lambda_2\) therefore bounds it above by this quotient. A good two-way cut produces a small eigenvalue. The converse, and the extension to several clusters, require Cheeger-type inequalities rather than this one calculation alone.
7. Two graph sequences with different implications
A path split into a fixed number of contiguous segments has only a bounded number of crossing edges per segment and segment volumes of order \(n\). Its conductances vanish. Under finite-range dependence and suitable moment conditions, the preceding covariance bound also vanishes.
For a bounded-degree expander, every substantial subset has conductance bounded below. The required partition cannot exist. An algorithm’s choice of cluster labels does not alter this obstruction.
Conversely, disconnected graph components could still share an unobserved common shock. The graph supports the inference argument only when the stochastic model links graph distance to decay of dependence. That assumption, together with the partition bounds, is needed for the few-cluster sign argument.
Why zero limiting covariance is enough only after the CLT
Suppose the normalized cluster vector converges jointly to a centered Gaussian vector \(Z=(Z_1',\ldots,Z_L')'\) with block covariance \(\Sigma\). If the boundary calculation makes every off-diagonal block zero, its characteristic function factorizes:
This factorization proves independence of the limiting blocks. Centered Gaussian blocks are separately invariant under sign changes, giving the limiting symmetry required by a cluster sign test. Without joint Gaussian convergence, covariance zero alone is insufficient: if \(U\) is standard normal, \(U\) and \(U^2-1\) are uncorrelated but dependent. The partition argument must therefore be combined with the joint CLT, not substituted for it.