Source-linked AI summary
Covariate-assisted spectral clustering
Norbert Binkiewicz, Joshua T. Vogelstein, Karl Rohe
TL;DR
Graph clustering often has access to node covariates, but few computationally feasible methods jointly use graph structure and these measurements with statistical guarantees. The paper develops covariate-assisted spectral clustering and a node-contextualized stochastic blockmodel, finding improved interpretability in simulations and brain graphs while identifying scope limits for perfect-clustering guarantees.
Problem
Few computationally feasible clustering methods incorporate both graph structure and node covariates, despite their availability in genomics, brain imaging, and social networks.
Method
The paper modifies spectral clustering to combine a regularized graph Laplacian with node covariates and analyzes the methods under a node-contextualized stochastic blockmodel.
Results
Covariate-assisted spectral clustering generally outperforms regularized spectral clustering and canonical-correlation-based clustering in simulations, while producing more interpretable brain-graph clusters.
Takeaways & Limitations
Node covariates can produce clusters that are more spatially coherent or more closely aligned with neurological regions while retaining patient-wise connectivity variability.
Takeaways & Limitations
The perfect-clustering condition for the method cannot be shown to hold when the number of covariates is fixed.
Abstract
from arXiv · showhide
Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications such as connectomics, social networks, and genomics, graph data are accompanied by contextualizing measures on each node. We utilize these node covariates to help uncover latent communities in a graph, using a modification of spectral clustering. Statistical guarantees are provided under a joint mixture model that we call the node-contextualized stochastic blockmodel, including a bound on the mis-clustering rate. The bound is used to derive conditions for achieving perfect clustering. For most simulated cases, covariate-assisted spectral clustering yields results superior to regularized spectral clustering without node covariates and to an adaptation of canonical correlation analysis. We apply our clustering method to large brain graphs derived from diffusion MRI data, using the node locations or neurological region membership as covariates. In both cases, covariate-assisted spectral clustering yields clusters that are easier to interpret neurologically.
1. INTRODUCTION
The paper addresses the limited availability of computationally feasible clustering methods that jointly use graph structure and node covariates. It develops covariate-assisted spectral approaches with theoretical guarantees and evaluates their performance on simulated and brain-graph data.
- Modern genomics and brain-imaging data contain relational structure and node-level measurements, but few feasible methods use both.
- Covariate-assisted spectral clustering combines graph and covariate information to uncover communities and contextualize their interpretation.
- The paper introduces one approach for assortative graphs and a more general approach intended to perform well on both assortative and non-assortative graphs.
- The node-contextualized stochastic blockmodel supports a mis-clustering bound, perfect-clustering conditions, and a lower-bound comparison for joint graph-and-covariate methods.
- An adaptation of canonical correlation analysis is used as an alternative comparison method for graph-and-covariate clustering.
- In brain graphs, spatial covariates produce more spatially coherent clusters, while neurological-region covariates yield partitions aligned with regions and patient-wise connectivity variation.
2. METHODOLOGY
The methodology applies spectral clustering to matrices that combine a regularized graph Laplacian with node-covariate information. It includes assortative and more general constructions, tuning procedures, and computational strategies for large graphs.
- Notation: The graph is represented by an adjacency matrix for an undirected, unweighted network, with regularized Laplacian L_τ used for sparse-graph spectral clustering.The regularization parameter is set to the average node degree.
- Covariate-assisted spectral clustering: The proposed methods use spectral clustering with input matrices that incorporate both graph structure and node covariates.
- Spectral clustering: Spectral clustering extracts the K largest-eigenvalue eigenvectors, row-normalizes them, and applies k-means to assign nodes to clusters.
- Assortative approach: Assortative covariate-assisted clustering adds αXX^T to L_τ, performs well for assortative graphs, and performs poorly for non-assortative graphs.Covariate scaling can help ensure that the leading eigenvectors contain block information.
- General approach: The general covariate-assisted method uses L_τL_τ + αXX^T and performs well for non-assortative graphs while nearly matching the assortative method on assortative graphs.
- Computational implementation: For large graphs, matrix-vector products exploit the sparsity of L_τ and low-rank structure of XX^T to compute leading eigenvectors efficiently.
- Tuning: The tuning parameter α balances graph and covariate information and is selected by minimizing a k-means within-cluster objective over a computed interval.Large α emphasizes XX^T, whereas small α emphasizes L_τ.
3. THEORY
The paper models graphs and node covariates jointly, then establishes consistency and mis-clustering guarantees for covariate-assisted spectral clustering. The theory relates error rates and perfect-clustering conditions to graph sparsity, covariate count, and their relative signal.
- Model: The node-contextualized stochastic blockmodel jointly represents block membership, graph edges, and node covariates.Covariate-assisted spectral clustering estimates the block membership matrix Z under this model.
- Consistency: The consistency proof combines concentration of the covariate-assisted Laplacian, eigenvector perturbation, and a mis-clustering bound.The argument uses Theorem 1, the Davis–Kahan theorem, and Theorem 3.
- Consistency: Under an eigengap condition, population eigenvector rows are equal exactly for nodes in the same block.This establishes the population-level correspondence between spectral embeddings and block membership.
- Rates: The asymptotic mis-clustering rate is governed by the balance between covariate growth and graph sparsity.The tuning parameter α is determined by that balance; when both contributions grow at the same rate, they contribute equally to the asymptotic rate.
- Perfect clustering: Perfect clustering under the simplifying assumptions requires R ≥ Θ(N log N) covariates.For a fixed number of covariates, the supplied theory cannot show perfect clustering.
- Lower bound: When neither the graph nor the covariates individually suffice, correct block recovery requires using both sources of information.The lower-bound result identifies conditions under which graph-only and covariate-only recovery are insufficient.
4. SIMULATIONS
Simulations vary graph signal, covariate signal, and alignment between graph and covariate block memberships. Covariate-assisted methods generally outperform single-source or canonical-correlation alternatives, with the assortative variant strongest for assortative graphs.
- Simulation design: The simulations compare five methods using graph edges, node covariates, or both.The methods include covariate-assisted spectral clustering, its assortative variant, canonical correlation analysis clustering, regularized spectral clustering, and covariate-only spectral clustering.
- Graph signal: As graph signal p − q varies, assortative covariate-assisted spectral clustering performs best on assortative graphs.Covariate-assisted spectral clustering performs slightly worse than the assortative variant but outperforms the other methods in that setting.
- Covariate signal: As covariate signal m1 − m2 varies, the assortative variant generally has the lowest mis-clustering rate.Regularized spectral clustering surpasses it only when covariate signal is very small and the covariates effectively become noise.
- Model misspecification: The assortative variant remains robust when covariate and graph block memberships are misaligned.The mis-clustering rate is evaluated relative to graph block membership in this misspecified setting.
- Model misspecification: For the non-assortative graph, covariate-assisted spectral clustering requires at least 0.8 agreement between covariate and graph block assignments in the reported simulation.This threshold is reported for the model-misspecification experiment.
5. CLUSTERING DIFFUSION MRI CONNECTOME GRAPHS
The brain-graph analysis uses spatial location and brain-atlas membership as node covariates to produce clusters that are more spatially coherent, uniform, consistent, and neurologically interpretable than baseline partitions.
- The analysis uses 42 diffusion-MRI brain graphs, with voxel connectivity defining edges and centered voxel locations serving as node covariates.
- Regularized spectral clustering produced spatially diffuse clusters, whereas adding spatial location produced densely connected, spatially coherent clusters with more uniform sizes.The baseline had two clusters of about 80,000 nodes and four with fewer than 1,000; the largest covariate-assisted cluster had fewer than 50,000 nodes and none had fewer than 1,000.
- Using brain-atlas membership yielded clusters highly aligned with neurological regions while preserving variation associated with brain-graph connectivity.Some clusters split, joined, or overlapped atlas regions, indicating alignment without complete overlap.
- Covariate-assisted clustering with spatial location produced more homogeneous partitions across and within individuals than regularized spectral clustering.Partitions were compared across all 42 graphs using adjusted Rand index after matching nodes by spatial location.
6. DISCUSSION
The discussion presents covariate-assisted spectral clustering as a flexible way to balance graph connectivity and covariate homogeneity, while emphasizing model deviation, tuning cost, and unresolved methodological questions.
- Covariate-assisted spectral clustering balances highly connected communities against relatively homogeneous covariates through an empirically or analytically selected tuning parameter.
- The method can contextualize clusters and support partitions aligned with covariates considered scientifically important.
- Data may deviate from the node-contextualized stochastic blockmodel assumptions used to study the method.
- Selecting an optimal tuning parameter remains computationally burdensome, although low-rank eigenvector updates may reduce the cost.
- Further work is needed to quantify graph-versus-covariate contributions and test which covariates are informative.
SUPPLEMENTARY MATERIAL
The supplementary analysis characterizes how the tuning parameter can cause discontinuous changes in the leading eigenspace and identifies an interval containing all possible transitions.
- Discontinuous changes in the leading eigenspace arise when eigenvalue ordering changes as α varies, even though some eigenvectors remain fixed.
- The covariate-assisted Laplacian can be decomposed using the eigenspaces of the regularized graph Laplacian and the covariate covariance structure.
- Transitions occur when the Kth eigengap vanishes, namely when λK(˜L) − λK+1(˜L) = 0.
- All discontinuous transitions in the leading eigenspace are confined to the interval [αmin, αmax].
Empirical Results for Choosing α
The empirical analysis evaluates tuning-parameter behavior and connects eigenspace conditions to population recovery, showing that an empirically useful α range can be identified while retaining theoretical clustering guarantees.
- Empirical Results for Choosing α: The minimum within-cluster sum of squares falls within [αmin, αmax] and tends to align with the minimum mis-clustering rate.
- The matrix Zµ contains eigenvectors equivalent to block membership, although they are not necessarily the top K eigenvectors without an additional eigengap condition.
- A positive eigengap separates the block-membership eigenvectors from orthogonal directions under the stated condition.
- The top K population eigenvectors recover block membership when λK(˜B˜P) > 2ακ.
- Theoretical concentration bounds control deviations between sample and population covariate-assisted Laplacians with high probability.
Proof of Theorem 2
The proof approximates the observed matrix by its optimal rank-K singular subspace, then applies Davis–Kahan to control the corresponding eigenspace error with high probability.
- The projection onto the first K left singular eigenvectors of ˜L is its optimal rank-K approximation.
- Choosing W = (λK/2, ∞) sets the spectral separation parameter to Λ = λK/2.
- The Davis–Kahan theorem yields the stated subspace perturbation bound with probability at least 1 −ǫ.
- Under δ{3 log(8N/ǫ)}1/2 ≤ λK/2, the Kth eigenvalue ωK lies in W and the relevant eigenspaces have the same dimension.
Proof of Theorem 3
The proof connects spectral-subspace error to k-means centroid separation, defining when nodes are mis-clustered and deriving a high-probability bound through geometric inequalities.
- A sufficient condition for correct assignment is that each observed centroid is closer to its population centroid than to centroids from other blocks.
- The k-means solution is compared with the population centroids using the triangle inequality to control rowwise clustering error.
- Combining this argument with Theorem 2 gives the mis-clustering result with probability at least 1 −ǫ.
Proof of Corollary 1
Under balanced-block assumptions, the corollary characterizes how the number of covariates, signal scaling, and tuning affect the mis-clustering rate and perfect-clustering conditions.
- When a > c, the bound includes terms O{(log N)−a}, O{(log N)−(3a+b)/2−3c}, and O{(log N)2(c−a)−b}.
- The mis-clustering rate is minimized at c = 0 when a > c, yielding |M|/N = O{(log N)−a}.
- When a ≤ c, the bound is minimized at c = a+b, while the displayed rate contains terms O{(log N)a−2c}, O{(log N)(a−b)/2−c}, and O{(log N)−b}.
- For a = 0 or R = Θ(log N) and b = 0 or d + τ = Θ(log N), the theoretical result suggests α = Θ{(N log N)−1}.
- Perfect clustering requires |M| < 1, corresponding under Theorem 3 to δ{c0KP log(8N/ǫ)}1/2 < λK.
Comparison of the General Lower Bound to Theorem 3
The comparison simplifies the general lower bound and contrasts its perfect-clustering requirement with the sufficient condition from Theorem 3.
- Theorem 3 instead requires δ{c0KP log(8N/ǫ)}1/2 < λK, and this condition requires R ≥ Θ(N log N).