Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu, Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu · 2025
Read Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation by Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu, Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13368.txt.
Introduction
Yaowen Hu and six co-authors present a scalable deep graph clustering method for large graphs whose node traits are partly missing. Such gaps and scale plague real networks like social graphs. Their work came out in twenty twenty-five.
The method first turns graph structure into many views with no overlap or loss. A recursive search walks node neighborhoods hop by hop for full coverage. A differentiation step then strips repeat nodes between hops. The views, plus the node's own traits, feed standard view fusion and grouping. The aim is sound groups at scale even when traits are absent, the authors report.
Catalog record
| CREATOR | Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu, Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13368
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu, Yaowen Hu, Wenxuan Tu, Yue Liu, Xinhang Wan, Junyi Yan, Taichun Zhou, Xinwang Liu Abstract Deep graph clustering (DGC), which aims to unsupervisedly separate the nodes in an attribute graph into different clusters, has seen substantial potential in various industrial scenarios like community detection and recommendation. However, the real-world attribute graphs, e.g., social networks interactions, are usually large-scale and attribute-missing. To solve these two problems, we propose a novel DGC method termed C omplementary M ulti- V iew N eighborhood D ifferentiation ( CMV-ND ), which preprocesses graph structural information into multiple views in a complete but non-redundant manner. First, to ensure completeness of the structural information, we propose a recursive neighborhood search that recursively explores the local structure of the graph by completely expanding node neighborhoods across different hop distances. Second, to eliminate the redundancy between neighborhoods at different hops, we introduce a neighborhood differential strategy that ensures no overlapping nodes between the differential hop representations. Then, we construct K + 1 K+1 complementary views from the K K differential hop representations and the features of the target node. Last, we apply existing multi-view clustering or DGC methods to the views. Experimental results on six widely used graph datasets demonstrate that CMV-ND significantly improves the performance of various methods. † † affiliationnotice: Equal contribution 1 Introduction Deep graph clustering (DGC) aims to partition the nodes of an attributed graph into distinct groups ( Liu et al. 2022a ; Gong et al. 2024 ; Yin et al. 2024b ; Yin et al. 2024a ; Yu et al. 2024b ) . Typically, DGC first embed nodes into a latent space before performing clustering. Existing DGC approaches commonly rely on contrastive learning ( Ju et al. 2024 ; Tu et al. 2024c ; Yin et al. 2023d ; Yin et al. 2023b ) or reconstruction-based models ( Li et al. 2023 ) , either maximizing intra-cluster similarity or reconstructing node features to enhance clustering performance. In recent years, DGC has achieved remarkable success in various real-world applications, including community detection, metagenomic binning, and recommendation systems ( Xue et al. 2022 ; Yin et al. 2023c ) . Despite their demonstrated effectiveness, most DGC methods are evaluated under conditions that have limited practical relevance. On one hand, they are typically tested on small-scale datasets, whereas real-world industrial and commercial applications often involve graphs containing hundreds of thousands or even millions of nodes ( Ding et al. 2019 ; Pang et al. 2023 ) , making it infeasible to apply standard Graph Neural Networks (GNNs) ( Yin et al. 2024b ; Ju et al. 2024 ) directly at such scales ( Lim et al. 2021 ) . On the other hand, the success of existing DGC approaches hinges on the assumption that all graph samples are complete, an assumption frequently violated in practice ( Huo et al. 2023 ; Yin et al. 2023a ) . In many real-world scenarios, data collection is subject to privacy policies, copyright restrictions, or equipment failures, resulting in partially or completely missing attributes that significantly degrade overall clustering performance. Although recent efforts have addressed DGC methods for large-scale graphs and missing attributes separately, the more realistic scenario, where both challenges coexist, remains underexplored. Notably, these problems are not orthogonal: missing attributes in large-scale graphs often give rise to additional complexities. In particular, large-scale graphs tend to be more sparse. For example, the ogbn-papers100M dataset contains around 1.11\times 10^{8} nodes and 1.6\times 10^{9} edges, edge density of only about 2.6\times 10^{-4} . In such highly sparse graphs, existing attribute completion methods become weak at inferring missing attributes, as they primarily rely on graph structure. Moreover, to scale to large graphs, DGC models typically rely on subgraph sampling for mini-batch training. This strategy inevitably alters the original topology and further weakens the limited structural cues, leading to degraded clustering results under missing attributes. As described above, the key to addressing attribute-missing large-scale DGC lies in preserving graph structural information as completely as possible. Inspired by the selective attention theory ( Dayan et al. 2000 ; Yin et al. 2022b ) in cognitive psychology, where human memory filters out redundant information and retains only the most critical incremental data for memory and cognition, we propose a novel paradigm called C omplementary M ulti- V iew N eighborhood D ifferentiation ( CMV-ND ). The core idea is to preserve graph structural information in multiple views in a complete and non-redundant manner. Specifically, CMV-ND consists of the following steps. First, we perform recursive neighborhood search (RNS) on each node to capture neighborhood information at various hop distances. To eliminate redundancy, we introduce a neighborhood differential strategy (NDS) that ensures there are no overlapping nodes between the differential representations of each hop, thereby achieving information redundancy reduction. Finally, the resulting K differential hop representations, along with the original node features, form K+1 complementary views, which are then used for the clustering. With the above designs, CMV-ND achieves the goal of preserving graph structural information in multiple views in a complete and non-redundant manner. Unlike the traditional “aggregate-encode-predict” pipeline of GNNs, CMV-ND does not leverage graph structure through propagation operations. Instead, it directly stores graph structural information in the views through differential neighborhoods, enabling it to process large-scale graph data without sampling. Additionally, the complementary multi-view differential hop representations generated by CMV-ND offer high flexibility. On one hand, they can be fused ( Wan et al. 2022 ; Zhang et al. 2023 ; Meng et al. 2024 ) and input into any existing graph clustering method. On the other hand, they can also be directly applied to various methods in the multi-view clustering (MVC) ( Zhang et al. 2022 ; Yin et al. 2022a ; Yu et al. 2024a ; Yin & Luo 2022 ) . The main contributions are summarized as follows. • This is the first attempt to perform DGC on large-scale graphs with missing attributes. Unlike approaches that focus solely on either attribute-missing graphs or large-scale graph clustering, our method addresses a more realistic and challenging scenario. • We propose a novel graph clustering paradigm, CMV-ND , which preemptively includes graph structural information in multiple views in a complete and non-redundant manner, aiming to address the challenge of attribute-missingness in large graphs. • Since CMV-ND constructs multi-view representations of nodes within the graph, it naturally bridges the gap between graph clustering and MVC. • We validate CMV-ND through experiments on six widely used graph datasets, evaluating its superiority, sensitivity, efficiency, robustness, and effectiveness. Even a simple concatenation of the views generated by CMV-ND followed by direct application of K -means achieves superior performance compared to most existing DGC methods. 2 Relate Work In this section we focus on the two most relevant areas to this work—attribute-missing graph clustering and large-scale deep graph clustering. Other related areas including deep graph clustering, large-scale graph learning, and attribute-missing graph completion are discussed in Appendix C for brevity. 2.1 Large-Scale Deep Graph Clustering Scalable GNNs specifically tailored for clustering tasks are still limited. This is primarily because clustering tasks require the model to estimate the entire