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

• URL: http://arxiv.org/abs/2507.10595v2
• Date: Tue, 05 Aug 2025 09:10:42 GMT
• Title: Divide-Then-Rule: A Cluster-Driven Hierarchical Interpolator for Attribute-Missing Graphs
• Authors: Yaowen Hu, Wenxuan Tu, Yue Liu, Miaomiao Li, Wenpeng Lu, Zhigang Luo, Xinwang Liu, Ping Chen,
• Abstract summary: Deep graph clustering is an unsupervised task aimed at partitioning nodes with incomplete attributes into distinct clusters.<n>Existing imputation methods for attribute-missing graphs often fail to account for the varying amounts of information available across node neighborhoods.<n>We propose Divide-Then-Rule Graph Completion (DTRGC) to address this issue.
• Score: 51.13363550716544
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Clustering-Oriented Generative Attribute Graph Imputation [46.388653923121566]
  We propose a Clustering-oriented Generative Imputation with reliable Refinement (CGIR) model for attribute-missing graph clustering.<n>We show that CGIR splits attribute-missing graph clustering into the search and mergence of subclusters, which guides to implement node imputation and refinement within a unified framework.
  arXiv  Detail & Related papers  (2025-07-25T09:11:38Z)
• Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation [46.17999216122895]
  We propose a novel DGC method termed underlinetextbfComplementary underlinetextbfMulti-underlinetextbfView.<n> CMV-ND preprocesses graph structural information into multiple views in a complete but non-redundant manner.<n> Experimental results on six widely used graph datasets demonstrate that CMV-ND significantly improves the performance of various methods.
  arXiv  Detail & Related papers  (2025-07-09T13:42:43Z)
• One Node One Model: Featuring the Missing-Half for Graph Clustering [10.316522132109354]
  Feature selection in graph clustering is difficult because it requires simultaneously discovering clusters and identifying the relevant features for these clusters.<n>We introduce a novel paradigm called one node one model", which builds an exclusive model for each node and defines the node label as a combination of predictions for node groups.<n>Specifically, the proposed Feature Personalized Graph Clustering (FPGC)" method identifies cluster-relevant features for each node using a squeeze-and-excitation block, integrating these features into each model to form the final representations.
  arXiv  Detail & Related papers  (2024-12-13T06:42:36Z)
• Cluster-based Graph Collaborative Filtering [55.929052969825825]
  Graph Convolution Networks (GCNs) have succeeded in learning user and item representations for recommendation systems. Most existing GCN-based methods overlook the multiple interests of users while performing high-order graph convolution. We propose a novel GCN-based recommendation model, termed Cluster-based Graph Collaborative Filtering (ClusterGCF)
  arXiv  Detail & Related papers  (2024-04-16T07:05:16Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  We propose a novel attributed graph clustering network, namely Self-supervised Contrastive Attributed Graph Clustering (SCAGC) In SCAGC, by leveraging inaccurate clustering labels, a self-supervised contrastive loss, are designed for node representation learning. For the OOS nodes, SCAGC can directly calculate their clustering labels.
  arXiv  Detail & Related papers  (2021-10-15T03:25:28Z)
• Attention-driven Graph Clustering Network [49.040136530379094]
  We propose a novel deep clustering method named Attention-driven Graph Clustering Network (AGCN) AGCN exploits a heterogeneous-wise fusion module to dynamically fuse the node attribute feature and the topological graph feature. AGCN can jointly perform feature learning and cluster assignment in an unsupervised fashion.
  arXiv  Detail & Related papers  (2021-08-12T02:30:38Z)
• Graph InfoClust: Leveraging cluster-level node information for unsupervised graph representation learning [12.592903558338444]
  We propose a graph representation learning method called Graph InfoClust. It seeks to additionally capture cluster-level information content. This optimization leads the node representations to capture richer information and nodal interactions, which improves their quality.
  arXiv  Detail & Related papers  (2020-09-15T09:33:20Z)
• CAGNN: Cluster-Aware Graph Neural Networks for Unsupervised Graph Representation Learning [19.432449825536423]
  Unsupervised graph representation learning aims to learn low-dimensional node embeddings without supervision. We present a novel cluster-aware graph neural network (CAGNN) model for unsupervised graph representation learning using self-supervised techniques.
  arXiv  Detail & Related papers  (2020-09-03T13:57:18Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  We propose a Graph Inference Learning framework to boost the performance of semi-supervised node classification. For learning the inference process, we introduce meta-optimization on structure relations from training nodes to validation nodes. Comprehensive evaluations on four benchmark datasets demonstrate the superiority of our proposed GIL when compared against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-17T02:52:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.