# Divide-Then-Rule: A Cluster-Driven Hierarchical Interpolator for Attribute-Missing Graphs

arXiv: https://arxiv.org/abs/2507.10595 · HTML: https://mlsanity.com/paper/2507.10595/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 72 references that are in the map.
- First posted on arXiv 12 Jul 2025.

## Builds on (most cited first, 30 of 35)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Merging Multi-Task Models via Weight-Ensembling Mixture of Experts](https://mlsanity.com/paper/2402.00433/) (2024)
- [Learning Graph Embedding with Adversarial Training Methods](https://mlsanity.com/paper/1901.01250/) (2019)
- [How would Stance Detection Techniques Evolve after the Launch of ChatGPT?](https://mlsanity.com/paper/2212.14548/) (2022)
- [Deep Fusion Clustering Network](https://mlsanity.com/paper/2012.09600/) (2020)
- [On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features](https://mlsanity.com/paper/2111.12128/) (2021)
- [Hard Sample Aware Network for Contrastive Deep Graph Clustering](https://mlsanity.com/paper/2212.08665/) (2022)
- [Cluster-guided Contrastive Graph Clustering Network](https://mlsanity.com/paper/2301.01098/) (2023)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Graph Convolutional Networks for Graphs Containing Missing Features](https://mlsanity.com/paper/2007.04583/) (2020)
- [Deep Imbalanced Learning for Multimodal Emotion Recognition in Conversations](https://mlsanity.com/paper/2312.06337/) (2023)
- [CoCo: A Coupled Contrastive Framework for Unsupervised Domain Adaptive Graph Classification](https://mlsanity.com/paper/2306.04979/) (2023)
- [Learning on Attribute-Missing Graphs](https://mlsanity.com/paper/2011.01623/) (2020)
- [Attention-driven Graph Clustering Network](https://mlsanity.com/paper/2108.05499/) (2021)
- [Dink-Net: Neural Clustering on Large Graphs](https://mlsanity.com/paper/2305.18405/) (2023)
- [Rethinking Graph Auto-Encoder Models for Attributed Graph Clustering](https://mlsanity.com/paper/2107.08562/) (2021)
- [T2-GNN: Graph Neural Networks for Graphs with Incomplete Features and Structure via Teacher-Student Distillation](https://mlsanity.com/paper/2212.12738/) (2022)
- [A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource](https://mlsanity.com/paper/2211.12875/) (2022)
- [CONVERT:Contrastive Graph Clustering with Reliable Augmentation](https://mlsanity.com/paper/2308.08963/) (2023)
- [DER-GCN: Dialogue and Event Relation-Aware Graph Convolutional Neural Network for Multimodal Dialogue Emotion Recognition](https://mlsanity.com/paper/2312.10579/) (2023)
- [CGC: Contrastive Graph Clustering for Community Detection and Tracking](https://mlsanity.com/paper/2204.08504/) (2022)
- [Fast Continual Multi-View Clustering with Incomplete Views](https://mlsanity.com/paper/2306.02389/) (2023)
- [Self-supervised Contrastive Attributed Graph Clustering](https://mlsanity.com/paper/2110.08264/) (2021)
- [Incomplete Graph Representation and Learning via Partial Graph Neural Networks](https://mlsanity.com/paper/2003.10130/) (2020)
- [Ada-NETS: Face Clustering via Adaptive Neighbour Discovery in the Structure Space](https://mlsanity.com/paper/2202.03800/) (2022)
- [Dual Test-time Training for Out-of-distribution Recommender System](https://mlsanity.com/paper/2407.15620/) (2024)
- [SA-GDA: Spectral Augmentation for Graph Domain Adaptation](https://mlsanity.com/paper/2408.09189/) (2024)
- [Confidence-Based Feature Imputation for Graphs with Partially Known Features](https://mlsanity.com/paper/2305.16618/) (2023)
- [Accurate Node Feature Estimation with Structured Variational Graph Autoencoder](https://mlsanity.com/paper/2206.04516/) (2022)

## Abstract (arXiv)

Deep graph clustering (DGC) for attribute-missing graphs is an unsupervised task aimed at partitioning nodes with incomplete attributes into distinct clusters. Addressing this challenging issue is vital for practical applications. However, research in this area remains underexplored. Existing imputation methods for attribute-missing graphs often fail to account for the varying amounts of information available across node neighborhoods, leading to unreliable results, especially for nodes with insufficient known neighborhood. To address this issue, we propose a novel method named Divide-Then-Rule Graph Completion (DTRGC). This method first addresses nodes with sufficient known neighborhood information and treats the imputed results as new knowledge to iteratively impute more challenging nodes, while leveraging clustering information to correct imputation errors. Specifically, Dynamic Cluster-Aware Feature Propagation (DCFP) initializes missing node attributes by adjusting propagation weights based on the clustering structure. Subsequently, Hierarchical Neighborhood-aware Imputation (HNAI) categorizes attribute-missing nodes into three groups based on the completeness of their neighborhood attributes. The imputation is performed hierarchically, prioritizing the groups with nodes that have the most available neighborhood information. The cluster structure is then used to refine the imputation and correct potential errors. Finally, Hop-wise Representation Enhancement (HRE) integrates information across multiple hops, thereby enriching the expressiveness of node representations. Experimental results on six widely used graph datasets show that DTRGC significantly improves the clustering performance of various DGC methods under attribute-missing graphs.