Compactness and Consistency: A Conjoint Framework for Deep Graph Clustering

AI summary

Overview

Research area: Deep graph clustering (unsupervised node grouping on attributed graphs), combining graph neural network representation learning, low-rank subspace modelling, and self-supervised consistency learning.

Technical level: Advanced. The paper assumes familiarity with graph Laplacians, graph diffusion / personalized PageRank, Gaussian mixture models and expectation-maximization, low-rank factorization, and Kullback-Leibler divergence.

Scope: The paper proposes CoCo, a framework that learns node representations from a local view (original adjacency) and a global view (graph diffusion), compresses them into low-rank compact embeddings to remove redundancy and noise, and aligns the two views through a consistency loss before K-means clustering.

What This Paper Is About

Existing graph-neural-network clustering methods propagate information only through a few layers of local message passing, so they miss long-range relationships between nodes; the redundancy and noise in graph data also make learned representations less compact and less robust. CoCo addresses both problems by encoding the graph from local and global views, projecting those representations into a shared low-rank subspace to strip out noise and redundancy, and then enforcing agreement between the two views' similarity distributions. The goal is more discriminative, noise-resistant node embeddings that yield better clusters without using any labels.

Key Contributions

1. A conjoint compactness-and-consistency framework (CoCo) that learns node representations from a local view over the adjacency matrix and a global view over a graph diffusion matrix, using disentangled graph convolutional filters rather than entangling the filter with a weight matrix.
2. A compactness learning module that fits a Gaussian mixture model via expectation-maximization to learn a shared low-dimensional subspace for both views, reconstructs the embeddings in that subspace, and re-injects them through a residual connection so gradients still flow.
3. Two theoretical results: a theorem stating that setting the filter parameters to the maximal eigenvalues of the local and global normalized graph Laplacians is optimal for low-pass filtering, and a theorem showing the low-rank reconstruction preserves each node's total signal mass ("individual mass conservation") while maximally preserving total variation among all low-rank factorizations.
4. A consistency learning strategy that samples anchors from a memory bank, computes cosine-similarity distributions for each node in both views, and minimizes a symmetric KL divergence between them, followed by averaging the two view representations and applying K-means.

Main Findings

• Best overall clustering accuracy: CoCo reports 79.36 ACC on Cora, 79.27 on AMAP, 78.85 on BAT, 58.87 on EAT, and 59.68 on UAT. It also reports 60.71 NMI / 58.76 ARI / 77.95 F1 on Cora, 68.85 NMI / 60.94 ARI / 72.36 F1 on AMAP, 55.00 NMI / 53.52 ARI / 78.56 F1 on BAT, 34.10 NMI / 27.91 ARI / 58.06 F1 on EAT, and 30.12 NMI / 29.46 ARI / 58.03 F1 on UAT.
• Margins over runner-ups are stated explicitly: on Cora and BAT the paper reports CoCo surpassing the runner-ups by {4.13, 1.45, 2.00, 5.23} and {4.16, 8.74, 12.79, 4.19} respectively across the four evaluation metrics. The paper notes CoCo achieves "almost the best results on all five datasets" — for example, on AMAP F1, CoCo's 72.36 is below MAGI's 73.03 and GraphLearner's 73.02.
• Contrastive methods beat autoencoder methods: the paper observes that the contrastive learning-based baselines outperform the autoencoder-based baselines (DEC, IDEC, DAEGC, ARGA, SDCN, DFCN) because they exploit graph semantics more effectively.
• Compactness learning matters: in the ablation, mapping raw features to low-rank embeddings improved results both locally (M3 vs M1) and globally (M4 vs M2), and removing compactness learning from the full model (M5) degraded performance.
• Two-view fusion matters more than either view alone: the gap between M5/CoCo and M1–M4 is described as significant, attributed to consistency learning integrating semantics from both views.
• Consistency loss beats MSE and InfoNCE: on Cora, MSE gives 77.84 ACC and InfoNCE 75.57 ACC versus 79.36 for the consistency loss; on AMAP, 77.62 and 77.25 versus 79.27; on UAT, 57.18 and 56.72 versus 59.68. InfoNCE performed worse than MSE in most cases.
• Noise robustness: on BAT corrupted with Gaussian attribute noise N(0,5), edge noise at probability 0.3, and both combined, CoCo obtained accuracies of 64.12, 55.57, and 48.78, versus GraphLearner (52.52, 36.79, 38.63) and MAGI (36.26, 38.70, 35.19). All methods degrade under noise relative to their clean-data scores.
• Heterophilic graphs: on Cornell, CoCo reports 59.68 ACC / 24.34 NMI versus GraphLearner's 43.00 / 14.17 and MAGI's 34.26 / 7.63; on Wisconsin, 56.39 / 17.04 versus GraphLearner's 46.06 / 19.38 and MAGI's 33.39 / 8.40. Wisconsin NMI for CoCo (17.04) is lower than GraphLearner's (19.38).
• Homophilic comparison: CoCo reports 79.36 ACC / 60.71 NMI on Cora and 79.27 / 68.85 on AMAP versus DGCN's 72.89 / 56.82 and 76.06 / 65.36.
• Hyperparameter sensitivity: performance rises slowly as subspace dimension K goes from 32 to 128, then declines beyond that; small anchor counts (M = 64) hurt performance and larger M is stable; teleport probability α of 0.1 or 0.2 is stable while performance drops noticeably at α = 0.8.
• Fast subspace search: the subspace searching algorithm is reported to achieve good performance within 10 iterations across datasets, with negligible additional computational cost.
• Visualization: t-SNE plots (compared against SDCN, AutoSSL, ProGCL, CCGC, GraphLearner, and MAGI on Cora and AMAP) show lower inter-cluster confusion on Cora and better separability on AMAP.

Methodology in Plain English

The graph is treated in two ways. The "local" view uses the standard normalized adjacency matrix, capturing one-hop neighborhood structure. The "global" view replaces the adjacency matrix with a diffusion matrix derived from personalized PageRank, which encodes soft, long-range relationships between all pairs of nodes and avoids the over-smoothing that comes from stacking many convolution layers. Each view's node attributes are passed through a Laplacian smoothing filter and then through its own multi-layer perceptron, producing two separate embedding sets.

To remove redundancy and noise, both embedding sets are stacked together and modelled with a Gaussian mixture model, which is fit by alternately estimating posterior membership probabilities (E step) and updating the subspace means (M step). Because only the principal, cluster-level directions survive in this K-dimensional subspace (with K much smaller than the embedding dimension D), noise and unstable fluctuations cannot be represented and effectively vanish when the embeddings are reconstructed back to their original dimension. The reconstruction is then added back to the original embeddings via a residual connection, keeping the pipeline inside the gradient flow while combining low-rank global trends with local detail.

Finally, the two views are made to agree. A memory bank of randomly sampled anchor nodes is maintained, each node's cosine similarity to those anchors is turned into a probability distribution via softmax with a temperature parameter, and the symmetric KL divergence between the local-view and global-view distributions is minimized. The two view-specific representations are averaged, and K-means is applied to the fused representation to produce the final clusters. The paper's Section 3.8 and Appendix E discuss time and space complexity, and the provided content is truncated before the full complexity figures and before any dataset size (node/edge count) or cluster-count values are reported.

Why This Matters

Impact on research. The paper argues that cross-view consistency learning between a local and a global view is a more effective self-supervised objective than contrastive losses such as InfoNCE for graph clustering, and it supplies theoretical guarantees (optimal filter parameters, mass conservation, maximal variation preservation) for the low-rank compression step — moving subspace-based denoising from a heuristic to an analysed component.

Real-world applications (as described or implied by the paper's stated application areas):

• Social network analysis, where communities must be found among users with noisy profile attributes and incomplete friendship links.
• Biological networks, where nodes represent entities such as genes or proteins and clusters correspond to functional groups.
• Recommender systems, where grouping users or items with related patterns supports more effective suggestions.
• General relational data analysis, where organizing large graphs into cohesive groups supports knowledge extraction and decision-making.

Industry relevance. Graph clustering pipelines frequently run on graphs with attribute noise and spurious edges; CoCo's reported behaviour under Gaussian attribute noise and random edge insertion/deletion (0.3 probability) targets exactly this condition, and the paper reports comparatively low runtime and memory cost relative to CCGC, Dink-Net, GraphLearner, and MAGI (the specific runtime/memory values are truncated in the provided content). The code is released at https://github.com/juweipku/CoCo.

Future Directions

• Scaling the anchor-based consistency loss: the paper frames anchor count as a trade-off between neighbourhood coverage and per-iteration cost; how the memory-bank size should scale with graph size is left open.
• Extending the noise robustness study: noise experiments are reported only on BAT with one setting each of Gaussian attribute noise N(0,5) and 0.3 edge perturbation; whether the compactness mechanism holds under other noise types or intensities is untested.
• Explaining the heterophilic trade-off: CoCo improves accuracy but reports lower NMI than GraphLearner on Wisconsin (17.04 versus 19.38), suggesting the cluster-structure quality on heterophilic graphs is not uniformly better and merits further study.
• Broadening beyond the evaluated benchmarks: the comparisons cover five standard datasets plus Cornell and Wisconsin; performance on larger or differently structured graphs is not reported.

Target Audience

Researchers and graduate students working on graph neural networks, deep clustering, and self-supervised learning; practitioners building unsupervised node-grouping pipelines on attributed graphs; and readers interested in the theoretical links between low-rank subspace learning, graph diffusion, and cross-view consistency objectives. Some background in spectral graph theory and probabilistic modelling is needed to follow the derivations in the appendices.

Authors’ abstract

Graph clustering is a fundamental task in data analysis, aiming at grouping nodes with similar characteristics in the graph into clusters. This problem has been widely explored using graph neural networks (GNNs) due to their ability to leverage node attributes and graph topology for effective cluster assignments. However, representations learned through GNNs typically struggle to capture global relationships between nodes via local message-passing mechanisms. Moreover, the redundancy and noise inherently present in graph data may easily result in node representations lacking compactness and robustness. To address these issues, we propose a conjoint framework CoCo, which captures compactness and consistency in the learned node representations for deep graph clustering. Technically, our CoCo leverages graph convolutional filters to learn robust node representations from both local and global views, and then encodes them into low-rank compact embeddings, thus effectively removing the redundancy and noise as well as uncovering the intrinsic underlying structure. To further enrich the node semantics, we develop a consistency learning strategy based on compact embeddings to facilitate knowledge transfer from the two perspectives. Our experimental results indicate that our CoCo outperforms state-of-the-art counterparts on various datasets.