Research map / Graph learning / Graph algorithms and clustering
Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CMV-ND, a training-free preprocessing that turns attribute graphs into K+1 non-overlapping multi-hop views via recursive neighborhood search and differential hop neighborhoods, enabling scalable attribute-missing deep graph clustering.
Problem
Deep graph clustering on large-scale attribute graphs where node attributes are missing, a setting where sampling and message passing degrade structural information and existing methods run out of memory.
Approach
Preprocess graph structure into multiple complete but non-redundant views: each view is the set of nodes at exactly k hops (differential hop neighborhood), averaged in features and stacked with the node's own features, so any DGC or MVC method can be run on the views without sampling or propagation.
Key results
- With CMV-ND, Dink-Net reaches 72.54% ACC on Cora at a 0.6 missing rate, surpassing all baselines reported in the table.
- AMGC runs out of memory on Reddit, ogbn-arXiv and ogbn-products, while Dink-Net combined with CMV-ND completes all runs on these datasets.
- CMV-ND preprocessing on ogbn-products takes about 274.57 s and 672.84 MB CPU memory, per the reported preprocessing cost table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add CMV-ND preprocessing to DinkNet | DinkNet · Cora (0.6 missing rate) | ACC: 66.54±1.65 -> 72.54±1.29 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · CiteSeer (0.6 missing rate) | ACC: 58.34±1.27 -> 68.56±1.71 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · Amazon-Photo (0.6 missing rate) | ACC: 70.75±1.47 -> 77.75±1.34 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · Reddit (0.6 missing rate) | ACC: 66.54±2.14 -> 69.31±1.84 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · ogbn-arXiv (0.6 missing rate) | ACC: 33.74±1.47 -> 36.84±2.04 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · ogbn-products (0.6 missing rate) | ACC: 31.09±0.94 -> 35.91±0.43 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · Cora (0.6 missing rate) | F1: 60.57±1.98 -> 70.57±0.64 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · CiteSeer (0.6 missing rate) | F1: 53.41±1.15 -> 61.31±1.54 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · Amazon-Photo (0.6 missing rate) | F1: 63.91±1.24 -> 72.03±1.43 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · Reddit (0.6 missing rate) | F1: 57.98±2.22 -> 62.87±1.32 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · ogbn-arXiv (0.6 missing rate) | F1: 22.99±0.64 -> 25.91±1.67 | Helped |
| Add CMV-ND preprocessing to DinkNet | DinkNet · ogbn-products (0.6 missing rate) | F1: 15.34±1.43 -> 23.41±1.51 | Helped |
Surprising findings
- On attribute-complete graphs, K-means with CMV-ND gains large improvements (e.g., Cora ACC rises from 33.78% to 74.00%), surpassing many DGC methods.
- Ablation is not performed; the authors state CMV-ND's components are inherently indivisible.
Limitations
- No ablation study of RNS and NDS components.
- MVC implementation of CMV-ND is weaker than its DGC counterpart; no MVC method tailored to it yet.
- Complexity analysis assumes average degree approximation and the redundancy analysis is heuristic.
Experimental setup
Datasets: Cora CiteSeer Amazon-Photo Reddit ogbn-arXiv ogbn-products
Benchmarks: Cora CiteSeer Amazon-Photo Reddit ogbn-arXiv ogbn-products
Metrics: ACC NMI ARI F1
Baselines: K-means DGI MVGRL ProGCL AGC-DRR CCGC S3GC AMGC Dink-Net MFLVC MCMVC DIMVC
Builds on: Dink-Net AMGC feature propagation S3GC
Closest papers by meaning
- Attribute-Missing Multi-view Graph Clustering (CVPR 2025 · similarity 0.91)
- Discriminative Attribute Graph Clustering Through Topology-Guided Contrastive Learning (ICML 2026 · similarity 0.90)
- DGCBench: A Deep Graph Clustering Benchmark (NeurIPS 2025 · similarity 0.90)
- Attribute-Missing Graph Clustering Network (AAAI 2024 · similarity 0.89)
- DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization (AAAI 2024 · similarity 0.89)
- SURER: Structure-Adaptive Unified Graph Neural Network for Multi-View Clustering (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.