PaperlayerView exact revision on arXiv

Source-linked AI summary

Compactness and Consistency: A Conjoint Framework for Deep Graph Clustering

Wei Ju, Siyu Yi, Kangjie Zheng, Yifan Wang, Ziyue Qiao, Li Shen, Yongdao Zhou, Xiaochun Cao, Jiancheng Lv

arXiv:2610.11506v1cs.LGcs.AIcs.IRcs.SI

TL;DR

Deep graph clustering needs representations that capture global relationships despite local message-passing limits and graph redundancy and noise. CoCo combines local and global graph views with low-rank embeddings and consistency learning; experiments report that it outperforms state-of-the-art methods across graph types and tasks.

  • Problem

    GNN-based clustering can miss long-range relationships through local message passing, while graph redundancy and noise challenge compact, robust node representations.

    Source: §1 · p. 2

  • Method

    CoCo learns representations from local and global graph views, encodes them into low-rank embeddings, and applies consistency learning to node similarities.

    Source: §1 · p. 2

  • Results

    Experiments across homophilic, heterophilic, and noisy graphs and clustering and node-classification tasks report that CoCo outperforms state-of-the-art methods.

    Source: §4 · p. 10

  • Takeaways & Limitations

    CoCo’s spatiotemporal complexity comparison demonstrates efficiency alongside its reported performance across the evaluated graph types and tasks.

    Source: §4 · p. 10

    The low-rank representation approach assumes high-dimensional data points intrinsically lie on a low-dimensional subspace.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

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.

1 INTRODUCTION

Deep graph clustering uses learned representations to address the limits of traditional methods, but GNN-based approaches can miss long-range relationships and produce noisy, redundant embeddings. CoCo combines local and global views with compactness and consistency learning to address these challenges.

1 INTRODUCTION

  • Traditional feature-based and graph-partitioning methods have limited model capacity to exploit the graph’s structural information.Deep graph clustering instead automatically extracts informative graph features.Source: §1 · p. 1
  • GNN-based methods learn node representations from attributes and neighboring-node relations, offering a data-driven approach to deep graph clustering.Prior approaches include SDCN, MAGI, and DMGC-GTN.Source: §1 · p. 2
  • Local message passing can overlook long-range dependencies, while graph redundancy and noise hinder compact, discriminative node representations.These limitations can leave clusters short of the underlying community structure and obscure relationships and patterns.Source: §1 · p. 2
  • CoCo combines graph-convolutional representations from the original graph and diffusion matrix with low-rank embeddings and consistency learning.The framework aims to reduce redundancy and noise while transferring knowledge between local and global views.Source: §1 · p. 2

2 METHODOLOGY

CoCo combines local and global graph views, compresses their embeddings into a shared low-rank subspace, and aligns their semantics through consistency learning. Its pipeline uses graph diffusion, low-rank reconstruction, and cross-view similarity distributions to produce fused clustering representations.

2.1 LOCAL- AND GLOBAL-VIEW FEATURE EXTRACTION

  • Graph diffusion supplies soft long-range relationships alongside one-hop local structure, while graph convolutional filters denoise features from both views.The method uses a personalized-PageRank diffusion matrix, sparsifies and symmetrizes it, and applies separate view-specific filters and MLPs.Source: §2.1 · p. 3

2.2 COMPACTNESS LEARNING FOR REDUNDANCY ELIMINATION

  • A GMM trained with expectation-maximization learns a shared K-dimensional subspace for the concatenated local- and global-view embeddings.The model fixes mixture weights equally and uses isotropic covariances; the search converges theoretically and reportedly performs well within 10 iterations.Source: §2.2 · p. 4
  • Posterior-weighted reconstruction maps both views into rank-limited embeddings while preserving each individual's aggregated information and maximally retaining total variation.The reconstruction prioritizes dominant patterns, and the shared subspace is intended to reduce the semantic gap between views.Source: §2.2 · pp. 4–5
  • A residual connection returns the reconstructed representations to the gradient path while retaining original local details alongside low-rank global trends.The residual path supports gradient flow and is described as mitigating over-smoothing and model collapse.Source: §2.2 · p. 5

2.3 CONSISTENCY LEARNING FOR SEMANTIC ENHANCING

  • Consistency learning aligns local- and global-view similarity distributions over sampled anchors to facilitate knowledge transfer between the views.A dynamically updated memory bank diversifies anchors at low complexity; after training, the views are fused by averaging and clustered with K-means.Source: §2.3 · pp. 5–6

3 EXPERIMENT

The evaluation spans five graph-clustering benchmarks and competitive baselines, then probes model variants, visualization, sensitivity, robustness, efficiency, and node-classification transfer.

3.2 EXPERIMENTAL RESULTS

  • CoCo achieves almost the best results on all five datasets and significantly outperforms runner-ups on many.The reported margins on Cora and BAT cover four evaluation metrics.Source: §3.2 · pp. 6–7

3.3 ABLATION STUDY

  • Consistency learning significantly outperforms MSE and InfoNCE by aligning similarity distributions from local and global perspectives.InfoNCE performs worse than MSE in most cases.Source: §3.3 · p. 7, Table 2 · p. 7

3.4 VISUALIZATION ANALYSIS

  • On Cora, CoCo shows less inter-cluster confusion, while on AMAP it shows better cluster separability than competitive methods.Figure 3 presents t-SNE results for both datasets, with Cora in the first row and AMAP in the second.Source: §3.4 · p. 8, Figure 3 · p. 8

3.5 SENSITIVITY ANALYSIS

  • Performance rises slowly as K increases from 32 to 128, then declines; very small M=64 performs poorly, while larger M is stable.A larger α also degrades performance, especially at α=0.8; α=0.1 or 0.2 is relatively stable because less-localized diffusion preserves complementary views.Source: §3.5 · p. 8, Figure 4 · p. 8

3.6 ROBUSTNESS ANALYSIS ON NOISY GRAPHS

  • Under attribute noise, edge noise, or both on BAT, CoCo consistently outperforms GraphLearner and MAGI, although noise degrades all methods.The settings add Gaussian attribute noise N(0, 5), randomly add or delete edges with probability 0.3, or apply both.Source: §3.6 · pp. 8–9, Table 3 · p. 9

3.7 PERFORMANCE COMPARISON ON HETEROPHILIC GRAPHS

  • CoCo mostly outperforms GraphLearner and MAGI on heterophilic graphs and surpasses DGCN on homophilic graphs.The comparison covers Cornell and Wisconsin for heterophilic graphs and homophilic graphs for the DGCN comparison.Source: §3.7 · p. 9, Table 4 · p. 9, Table 5 · p. 9

3.8 TIME AND SPACE COMPLEXITY COMPARISON

  • CoCo achieves the best clustering performance on Cora and AMAP while maintaining relatively low time and space complexity.Performance stabilizes after 10 EM iterations, which account for about 4% of total training time.Source: §3.8 · p. 9, Figure 5 · p. 9, Table 6 · p. 9

3.9 EVALUATION ON NODE CLASSIFICATION TASK

  • After unsupervised pretraining and supervised fine-tuning, CoCo outperforms all baselines on node classification across five datasets.The evaluated datasets are WikiCS, Computers, Photo, Coauthor CS, and Coauthor Physics.Source: §3.9 · p. 10, Table 7 · p. 10

4 CONCLUSION

CoCo combines local- and global-view representations, low-rank embeddings, and consistency learning for deep graph clustering. The paper reports strong results across several graph types and tasks, and identifies temporal graph clustering and single-cell genomics as future directions.

4 CONCLUSION

  • CoCo combines local- and global-view encodings with GMM-based low-rank embeddings and consistency learning, and reports outperforming state-of-the-art methods across varied graph types and tasks.The conclusion also reports a comparison of spatiotemporal complexity as evidence of efficiency.Source: §4 · p. 10

A EXPECTATION-MAXIMIZATION ALGORITHM FOR GAUSSIAN MIXTURE MODEL

  • GMM represents data as a mixture of Gaussian components, while EM introduces latent variables to indicate sample-component membership.The appendix describes the model for K Gaussians and introduces latent variables Y for the membership assignments.Source: A EXPECTATION-MAXIMIZATION ALGORITHM… · p. 17

B.1 PROOF OF THEOREM 1.

  • The filter proof relates graph-signal smoothness to a Rayleigh quotient and sets the filter parameter to retain low-frequency signals while filtering high-frequency noise.The passages state that a smaller parameter supports the low-pass property and identify the optimum as the maximum eigenvalue.Source: §B.1 · p. 17

B.2 PROOF OF REMARK 1.

  • The EM proof uses Q-function maximization and Jensen’s inequality to establish the stated condition on the H-function.The proof frames the argument around nondecrease of Q and the corresponding inequality for H.Source: §B.2 · p. 18

B.3 PROOF OF THEOREM 2.

The proof characterizes the reconstructed embedding as retaining important variation from the original while suppressing redundant or noisy components. It also states that reconstruction preserves each node’s aggregated information.

B.3 PROOF OF THEOREM 2.

  • Reconstruction preserves each row’s total mass, so the aggregated information associated with each individual remains unchanged.The passage also states that the individual-level signal encoded in the original embedding is retained.Source: §B.3 · p. 18
  • The proof states that maximizing the Q-function in the M step is equivalent to minimizing the objective in Equation 8.The supplied passage does not specify the objective’s expression.Source: §B.3 · pp. 18–19
  • The minimized objective yields a reconstruction that preserves as much of the original embedding’s total variation as possible while suppressing redundant or noisy components.The proof emphasizes the cross-correlation between original and reconstructed embeddings as measuring alignment with the original signal.Source: §B.3 · p. 19

C MORE DISCUSSIONS ON THE PROPOSED COCO

The discussion motivates GMM for low-rank representation learning by its complexity and probabilistic soft-clustering properties. It distinguishes CoCo’s consistency learning from contrastive learning and reports a considerable performance margin over InfoNCE.

C MORE DISCUSSIONS ON THE PROPOSED COCO

  • GMM is selected for low-rank representation learning because it has linear modeling complexity, is a probabilistic soft-clustering method robust to outliers, and has fewer parameters and lower complexity than autoencoders.The passage gives GMM time and space complexities of O(NDK) and O(ND), respectively, and notes that PCA complexity rises when feature counts are high.Source: C MORE DISCUSSIONS ON THE PROPOSED COCO · p. 19
  • CoCo’s consistency learning aligns local- and global-view relational information without negative samples, unlike contrastive learning’s instance-level discriminability objective.The discussion describes its target as relationships among non-iid nodes and argues that the alignment supports more semantically rich representations for clustering.Source: C MORE DISCUSSIONS ON THE PROPOSED COCO · pp. 19–20
  • The paper reports that CoCo’s consistency loss outperforms InfoNCE by a considerable margin in the reported comparisons.The authors interpret this result as evidence that distribution-based consistency captures intrinsic node dependencies at a higher semantic level.Source: C MORE DISCUSSIONS ON THE PROPOSED COCO · p. 20

D TRAINING PROCEDURE

CoCo’s training loop filters local and global views, updates embeddings and their compact reconstructions, and optimizes a loss before producing clusters with K-means.

D TRAINING PROCEDURE

  • The procedure takes a graph and cluster count as input and returns a clustering result.The algorithm lists graph G, cluster number C, and clustering result c as its input and output.Source: D TRAINING PROCEDURE · p. 20
  • Each iteration filters local and global attribute views, encodes them into embeddings, and updates the low-rank subspace and reconstructed embeddings.The encoders are unshared, and the procedure repeats these updates until convergence.Source: D TRAINING PROCEDURE · p. 20
  • Each iteration updates similarity distributions, minimizes the framework loss by backpropagation, and finally applies K-means to fused representations.K-means is applied after the training loop converges.Source: D TRAINING PROCEDURE · p. 20

E COMPLEXITY ANALYSIS

CoCo’s complexity analysis reports linear preprocessing and training costs expressed in terms of graph size and model dimensions. It also contrasts CoCo’s scaling with quadratic-time baselines.

E COMPLEXITY ANALYSIS

  • Each training epoch has time complexity O(NDK + NMD) and space complexity O(ND + NM).The reported preprocessing time and space complexities are O(N) and O(E), respectively.Source: E COMPLEXITY ANALYSIS · p. 20
  • The graph convolutional filters have complexity O(nnz(Ŝ) * N), and the sparse diffusion matrix is computed once at the beginning of training.The sparse diffusion matrix is approximately calculated in O(N) time and space.Source: E COMPLEXITY ANALYSIS · p. 20
  • CoCo scales linearly with the number of samples, making it more suitable for large-scale datasets where computational efficiency is crucial.Table 8 presents the theoretical complexity comparison.Source: Table 8 · p. 20, E COMPLEXITY ANALYSIS · p. 21

F DETAILS OF EXPERIMENTAL SETUP

The experiments evaluate CoCo on five benchmark datasets against a broad set of deep graph clustering and unsupervised learning methods. They report four clustering metrics averaged over 10 runs.

F DETAILS OF EXPERIMENTAL SETUP

  • The evaluation uses Cora, AMAP, BAT, EAT, and UAT as its five benchmark datasets.The dataset selection follows Yang et al. (2023).Source: F DETAILS OF EXPERIMENTAL SETUP · p. 21
  • Baselines span autoencoder-based methods, including SDCN and DFCN, and contrastive methods, including MVGRL, CCGC, GraphLearner, and MAGI.The benchmark also includes DEC, IDEC, DAEGC, ARGA, AGE, GDCL, AutoSSL, AGC-DRR, AFGRL, ProGCL, RGC, and Dink-Net.Source: F DETAILS OF EXPERIMENTAL SETUP · p. 21
  • Performance is reported with ACC, NMI, ARI, and Macro F1-score as mean and standard deviation across 10 runs.Larger metric values indicate better clustering results.Source: F DETAILS OF EXPERIMENTAL SETUP · p. 21

G ADDITIONAL MAIN EXPERIMENTAL RESULTS

Across the additional comparisons, CoCo achieves the best performance on most datasets, although RGC leads on some metrics in AMAP and EAT. The paper relates CoCo’s performance to complementary local and global semantics, compact embeddings, and consistency learning.

G ADDITIONAL MAIN EXPERIMENTAL RESULTS

  • CoCo achieves the best performance on most datasets, while RGC outperforms it on certain metrics in AMAP and EAT.Table 9 reports clustering performance on five benchmark datasets as mean ± standard deviation.Source: G ADDITIONAL MAIN EXPERIMENTAL RESULTS · p. 21, Table 9 · p. 21
  • RGC’s stronger results on some AMAP and EAT metrics may reflect its ability to automatically learn the number of clusters.The authors state this may better approximate the true data distribution.Source: G ADDITIONAL MAIN EXPERIMENTAL RESULTS · p. 21
  • The paper attributes CoCo’s performance to complementary local and global semantic information, low-rank embeddings that remove redundancy and noise, and consistency learning that enriches node representations.The authors state that the modules complement one another in producing clustering assignments.Source: G ADDITIONAL MAIN EXPERIMENTAL RESULTS · pp. 21–22

H ADDITIONAL RESULTS ON INFLUENCE OF CONSISTENCY LEARNING

Additional experiments report that CoCo’s consistency learning outperforms MSE and InfoNCE across all evaluated datasets. The paper attributes this result to distribution-based alignment of high-order semantic similarity.

H ADDITIONAL RESULTS ON INFLUENCE OF CONSISTENCY LEARNING

I ADDITIONAL SENSITIVITY ANALYSIS

The additional analysis finds consistent hyperparameter sensitivity trends across datasets. The related-work subsections frame CoCo around long-range dependencies and redundant or noisy graph information, and distinguish its diffusion and low-rank approaches.

J GRAPH CONVOLUTIONAL FILTER v.s. GCN

  • Comparative experiments test whether disentangling graph convolutional filters and weight matrices enhances model robustness.The passage identifies GCF+MLP as part of the comparison.Source: J GRAPH CONVOLUTIONAL FILTER v.s. GCN · p. 22

I ADDITIONAL SENSITIVITY ANALYSIS

  • Across datasets, performance rises slowly as K increases from 32 to 128 before declining when K becomes too large; small M performs poorly, while larger M stabilizes performance.Performance also deteriorates as teleport probability α increases, with a marked decline at α=0.8.Source: I ADDITIONAL SENSITIVITY ANALYSIS · p. 22, Figure 6 · p. 23

K.1 DEEP GRAPH CLUSTERING

  • Despite diverse deep graph clustering methods, long-range dependencies and inherent redundant information and noise remain common challenges.The related work describes approaches targeting dynamic feature aggregation, noise filtering, scalability, and adaptive cluster counts.Source: §K.1 · pp. 23–24

K.2 GLOBAL DEPENDENCIES IN GNNS

  • CoCo follows explicit structural augmentation by constructing a graph diffusion matrix to model indirect connections and capture global dependencies.This is presented as a way to help clusters represent underlying community structures.Source: §K.2 · p. 24

K.3 NOISE-RESILIENT LEARNING IN GNNS

  • CoCo uses low-rank learning to model underlying low-dimensional structure and separate noise and redundancy at the data-distribution level.The passage presents this as producing robust, clustering-friendly representations.Source: §K.3 · p. 24

Related papers

Loading 2610.11506v1…