Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Authors: Yaowenhu
Wenxuan Tu
Yue Liu
Xinhang Wan
Junyi Yan
Taichun Zhou
Xinwang Liu
Venue: ICML 2025 poster (2025)
Keywords: Deep Graph Clustering，Multi-view clustering，Graph Neighborhood Difference，Information Redundancy
Primary area: general_machine_learning->clustering
TL;DR: We address large-scale deep graph clustering under missing attributes and bridge the gap between Multi-View Clustering and Deep Graph Clustering.

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 ($\textit{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$ complementary views from the $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.

Scalable Attribute-Mising Graph Clustering via Neighborhood Differentiation
Yaowen Hu"
Wenxuan Tu
Yue Liu
Xinhang Wan
Junyi Yan
Taichun Zhou' Xinwang Liu
Abstract
1. Introduction
Deep graph clustering (DGC) aims to partition the nodes of attributed graph into distinct groups (Liu et al., 2022a; Gong et al., 2024; Guan et al., 2025; Liu et al., 2025; Yu et al., 2024b). Typically, DGC first embed nodes into a latent space before performing clustering. Existing DGC approaches commonly rely on contrastive learning (Wan et al., 2024b; Tu et al., 2024c; Yang et al., 2024; 2023b) or reconstruction-based models (Li al., 2023), either max- imizing intra-cluster similarity or reconstructing node fea- tures 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).
Deep graph clustering (DGC), which aims to unsu- pervisedly separate the nodes in an attribute graph into different clusters, has seen substantial poten- tial in various industrial scenarios like commu- nity 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 Complementary Multi Multi-View Neighborhood Differentiation (CMV- ND), which preprocesses graph structural infor- mation into multiple views in complete but non- redundant manner. First, to ensure completeness of the structural information, we propose re- cursive neighborhood search that recursively ex- plores the local structure of the graph by com- pletely expanding node neighborhoods across dif- ferent hop distances. Second, to eliminate the redundancy between neighborhoods different hops, we introduce a neighborhood differential strategy that ensures no overlapping nodes be- tween the differential hop representations. Then, we construct K + 1 complementary views from the K differential hop representations and the features of the target node. Last, we apply ex- isting vulti-view clustering DGC methods to the views. Experimental results on six widely used graph datasets demonstrate that CMV-ND significantly improves the performance of various methods.
Despite their demonstrated effectiveness, most DGC meth- ods are evaluated under conditions that have limited prac- tical relevance. On one hand, they typically tested on small-scale datasets, whereas real-world industrial and com- mercial applications often involve graphs containing hun- dreds of thousands or even millions of nodes (Ding et al., 2019), making it infcasible to apply standard Graph Neural Networks (GNNs) (Yin al., 2024; 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 assump- tion that all graph samples are complete, frequently violated in practice (Huo et al., 2023). In many real-world scenarios, data collection is subject to privacy policies, copyright restrictions, or equipment failures, re- sulting in partially or completely missing attributes that significantly degrade overall clustering performance.
assumption
Although recent efforts have addressed DGC methods for large-scale graphs and missing attributes separately, the more realistic scenario, where both challenges coexist, re- mains underexplored. Notably, these problems are not or- thogonal: missing attributes in large-scale graphs often give rise to additional complexities. graphs tend to be more sparse. For example. the ogbn- papers dataset contains around 1.11 x 10 nodes and 1.6 x 10 edges, edge density of only about 2.6 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
'Equal contribution 'College of Computer Science and Tech- nology, National University of Defense Technology, Changsha 410073, China "School of Computer Science and Technology, Hainan University, Haikou 570228, China. Correspondence to: Xinwang Liu i <xinwangliu nudt.edu.cn">
particular, large-scale
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
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.
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 superior- ity, sensitivity, efficiency, robustness, and effectiveness. Even a simple concatenation of the views generated by CMV-ND followed by direct application of K K-means achieves superior performance compared to most exist- ing DGC methods.
As described above, the key to addressing atrriiutemmssing large-scale DGC lies in preserving graph structural infor- mation as completely as possible. Inspired by the selective attention theory (Dayan et al., 2000) in cognitive psychol- ogy, where human memory filters out redundant information and retains only the most critical incremental data for mem- ory and cognition, we propose a novel paradigm called Complementary Multi- Neighborhood Differentiation (CMV-ND). The core idea is to preserve graph structural information in multiple views in 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 infor- mation 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.
2. Relate Work
In this section we focus on the two most relevant areas to this work- autribute-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 re- quire the model to estimate the entire sample distribution at once. When the node count reaches the order of hundreds of millions, this often leads to memory shortages or excessive runtime. Recently, only two papers have attempted to scale DGC to large-scale graphs. Scalable self-supervised graph clustering GSC (Devvrit et al., 2022) uses lightweight encoders and simple random walk-based samplers to en- sure that the embedding of a node is close to its "nearby" nodes while being far from all other nodes. Although its effectiveness has been validated, this method separates rep- resentation learning from clustering optimization, leading to suboptimal overall performance. Dilation shrink net- work (Dink-Net) (Liu et al., 2023b) proposes a new scalable method that unifies embedding learning and clustering into an end-to-end framework, which not only scales to large graph data but also learns elustering-friendly representa- tions. However, all of the above methods rely on sampling, and as mentioned earlier, structural information is critical for large-scale graph clustering under attribute-missin missunt con- ditions. Therefore, due to the disruptive effects of sampling on graph structure, these methods cannot be directly applied to large graphs in such scenarios.
With the above designs, CMV-ND achieves the goal of pre- serving graph structural information in multiple views in a complete and rod-rrdundant manner. Unlike the tradi- tional pagrregte-eeccdd-preeeee predict" pipeline of GNNs, CMV- ND does not leverage graph structure through propagation operations. Instead, it directly stores graph structural in- formation in the views through differential neighborhoods, enabling it to process large-scale graph data without sam- pling. Additionally, the complementary multi-view differen- tial hop representations generated by CMV-ND offer high flexibility. On one hand, they can be fused (Wan al., 2022) 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) (Wan et al., 2024a;c; Yu et al., 2024a; 2023). 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.
2.2. Attribute-Missing Graph Clustering
We propose novel graph clustering paradigm, CMV- ND, which preemptively includes graph structural in- formation in multiple views in a complete and non- redundant manner, aiming to address the challenge of attribute- miisingesssss in large graphs.
In the domain of attribute-nissing graph clustering, one rep- resentative approach is the attribute-missing graph cluster- ing network (AMGC) (Tu et al., 2024a). AMGC addresses the dual challenge of clustering and attribute imputation by adopting an iterative framework that alternates between
2

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
the two. Specifically, it leverages the current clustering assignments identify clustering-enhanced nearest neigh- bors, which are then used to refine the imputed attributes. This feedback mechanism allows the model to progressively enhance the feature quality of attribute-missing nodes and align the latent representations with the underlying cluster structure.
complete nodes and V denotes the set of attribute-missing nodes, where V Vo U vm and Vo n V 0. Let Nc = [ and N = | then the total number of nodes is N= = N +
3.2. Challenge Analyses
This section analyzes the challenges faced by DGC in the context of large-scale graphs with missing attributes. Since clustering is an unsupervised task, a graph can be fully de- scribed using two sources of information, i.c., the feature view and the structural view. Specifically, let 9 = represent the graph, where Vm denotes the feature view and & represents the structural view. In the case of attribute- missing graphs, the feature view is inherently incomplete. As a result, effectively leveraging the structural view be- comes critical for improving clustering performance.
By integrating clustering signals into the imputation pro- cess, AMGC achieves competitive performance. However, the framework relies heavily on GNN encoder, which performs full-graph message propagation across iterations. This reliance introduces significant memory and computa- tional overhead, as the entire graph must be loaded into memory and processed in holistic fashion. As a con- sequence, AMGC exhibits poor scalability and cannot be directly applied to large-scale graphs with millions of nodes and edges, where full-batch training becomes infeasible.
However, existing large-scale graph clustering paradigms often end up further compromising the structural view. On one hand, sampling commonly used handle large graphs, disrupt the graph structure. On the other hand, the message- weessag-ppssinng passing mechanism inherently introduces redun- dancy in node representations, as information from neigh- boring nodes is repeatedly aggregated during the process.
3. Method
3.1. Notations and Problem Definition
Basic Notations. Let = (V, E, H. denote an undirected graph, where V= =w J.N is the set of vertex with N nodes, E is the set of edges, H E Nx is the node attribute matrix where d denotes the feature dimension of the node, N A E N is the adjacency matrix that represents the relationships between nodes. Specifically, 0ij = 1 if there an edge between nodes vs and Vg. and diş = 0 otherwise.
3.3. Proposed Solution
Based on the analysis in the previous section, the key to addressing attribute-missing large-scale DGC lies in pre- serving graph structural information as completely as pos- sible. To tackle this challenge, we propose a novel graph clustering paradigm called CMV-ND. Intuitively, CMV-ND stores graph structural information in multiple views in complete and non-redundant manner through preprocessing. CMV-ND consists primarily of two components, i.e., RNS and NDS. We provide a detailed explanation of these com- ponents in the following sections, including an overview of the overall architecture shown in Figure 1.
Definition 1 (k-hop neighborhood). For a node v, its k-hop neighborhood, denoted by (v), is defined as the set of nodes whose shortest path distance to is less than or equal to k. Formally.A (c) = {u e V dis(v, u) S k), where dis(v, u) denotes the length of the shortest path between nodes v and u. Note that (v) includes node v itself, since dis(e, u) =.
Definition 2 (k-differential hop neighborhood). The k- differential hop neighborhood of node v. denoted by D* (v), refers to the set of nodes thut are exactly k hops away from {u E V dis(v, u) k). This definition captures the "differ- ence" between the k-hop neighborhood and the (k-1))hhop neighborhood: D (u) = ^²(rv) \ (V--((v). For exam- ple, consider graph with edges (v, a), (v, b), ca. Then: (v) {v, a, b), (v) {u, a, b, c). The corre- sponding difffrrnniaal hop neighborhoods are: (v) {a, b), D2 (x) = {c}.
3. RECURSIVE NEIGHBORHOOD SEARCH
The RNS aims explore the neighborhood structure of the graph by recursively expanding the set of nodes at increasing hop distances. This process can be viewed as breadth-fire traversal, where in each step the neighborhood is extended by adding nodes that are exactly one hop away from the current set.
u, excluding nodes that are closer. Formally, D*
The recursive expansion of the neighborhood is defined by setting (v(v)) v, i.e., the node itself, and recursively applying the following relation to determine N**
Definition (atriibut-missingg graph). An attribute- missing graph is graph where certain nodes lack feature representations. The node set V is divided into two disjoint subsets: y and Vmn, i.e., vo denotes the set of attribute-
N++ (+)
U N(l)., (EA*(())
(1)
where (u() denotes the set of neighbors of node u. At each
3

---

Scalable Attribute-Missig Graph Clustering via Neighborhood Differentiation
MM
P'M
D'(M)
View
View
View 3
View 4
Figure Overall workflow the CMV-ND algorithm. The algorithm recursively searches neighborhood of each node, treating each neighborhood a distinct view. Each view contains complete nodes that do not overlap with other views.
step, nodes added the neighborhood by exploring all neighbors of the previously discovered nodes, ensuring that nodes are processed layer by layer. The search halts once the k-hop neighborhood fully determined, and no further neighbors are added.
(RNS) is employed to efficiently locate multi-hop neighbors, while the Neighborhood Differential Strategy (NDS) iso- lates the structural information at each k-differential hop. The representation of the k -differential hop neighborhood is computed by aggregating the features of all nodes in:
3.3.2. NEIGHBORHOOD DIFFERENTIAL. STRATEGY
h
Σ
h
NED
Through the RNS, obtain the k-hop neighborhoods of nodes in a non-ooonneeeee ponppppaagttie manner. However, observe that the resulting neighborhoods are highly redundant, as the (k + 1)-hop neighborhood contains all nodes in the k-hop neighborhood. To address this redundancy, we propose a simple but effective NDS to separate distinct neighborhood information between different hops.
where Took is the number k-hop neighbors of o, h, Rd is the feature vector of the neighboring node u, and h Rd is the aggregated representation of the k-hop neighborhood of node
Next, for each node we define its multi-view represen- tation as H. E [k++))xd which contains the following components:
Formally, let the k-hop neighborhood of node be denoted as (v), which includes all nodes whose shortest path distance is less than or equal to ht We define the k- differential hop neighborhood, (v),,, as:
(4) where he denotes the original feature of node and h is the aggregated representation of the k-differential hop neighborhood. Therefore, the multi-view representation H, captures both local and progressively expanded structural information, forming (k+1) matrix.
H. (h:: h.]
Dd = (v) (w)-
(2)
which contains only the nodes whose shortest path distance to is exactly k. This formulation isolates the structural information at each hop and avoids redundancy across dif- ferent neighborhood levels.
To construct the graph-level multi-view representation, stack the (k 1)-view representations of all nodes along the view dimension. This results in 3D tensor H. ((+++))NNx where N is the number of nodes and d is the feature dimension. Formally, is written as:
The resulting differential hop neighborhoods, (*),), satisfy the definition provided Definition 2. where each differ- ential hop neighborhood contains only nodes that are at an exact distance of k: from the node v. with no overlap with nodes from the previous hop. As shown in Algorithm 1, the full procedure of CMV-ND is presented.
H = HH; :Ny]
We describe how the above nilti-view representations utilized in Appendix B.
3.3.3. CONSTRUCT MULTI- VIEW REPRESENTATION
3.3.4. WHY CMV-ND REDUCES REDUNDANCY?
To enable graph clustering, we propose to construct multi- view node representations based on the structural granular- ity of neighborhoods. The Recursive Neighhorhood Search
Let (v) denote the set of nodes at exactly é hops from e, and let be the average node degree. Then we approximate

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Algorithm 1 CMV-ND
3.4. Complexity Analysis
1: Input: Graph G. target node v and hop distance &
The overall time complexity of CMV-ND is ((n where is the number of nodes. This arises from performing the RNS for each node, expanding its neighborhood up to & hops. The NDS has a time complexity of (k) per node. Regarding memory, CMV-ND requires ((n) space to store the visited nodes and the priority queue, leading to an overall memory complexity of (nn). Given that large-scale graphs are typically sparse, with A < n, and CMV-ND only requires one-time preprocessing, it is highly scalable for large graphs
2: Output: Set of k-differential hop neighborhood (*)
3: Initialize visited set: Vvisited 0
4: Initialize priority queue: PQ 6-1
5: Push (0,v) into PQ
6: Initialize differential hop set: (+)) t- 0
7: while priority queue PQ is not empty do
8: Pop (hops, u) from PQ
9: if hops then
10: break
11: end if
12: if hops = k and u o u then
3.4.1. 1. TIME COMPLEXITY
13:
Add node to (v)
14:
end if
Recursive Neighborhood Search. The algorithm starts from each node a and recursively expands its neighborhood by incorporating nodes that are exactly k hops away at each step. At each hop, the number of newly encountered nodes is determined by the degrees of the nodes reached at the previous hop. Specifically, the number of nodes added at each hop is bounded by the average degree A', where A is the maximum degree of any node in the graph. Thus, the total number of nodes explored for each node e up to the k-th hop is Σ A' = 1+ A + + + + A = (A))). Since the search is performed for each of the n nodes in the graph, the overall time complexity of the RNS for the entire graph is (n
15:
if hops < k then
16:
for each neighbor w of u do
17:
if not in Visited then
18:
Add to Visited
19:
Push (hops + 1, w.) into PQ
20:
end if
21:
end for
22:
end if
23:
end while
Return the set of differential hop neighbors D (*())
(D)()) = A'. In a k-layer GNN, each (v)) contributes to all layers up to k, leading to repeated accesses. The total number of feature accesses is:
Neighborhood Differential Strategy. The k-differential hop neighborhood for each node is computed D D*()) ~ (W)- Since set differences can be calculated in constant time for each pair of neighborhoods, the time complexity for this step is O(n)).
Σ Ck-i+ ())(())
~ Σ (k- (k-i+1)44
(6)
1=1
where A' denotes the number of i-hop neighbors accessed per node. In contrast, CMV-ND accesses each differential hop neighborhood exactly once, resulting in:
3.4.2. MEMORY COMPLEXITY
The memory complexity of CMV-ND is O(n), which arises from maintaining two primary data structures: set of visited nodes, which tracks the nodes that have already been explored to avoid redundant computations and consumes (n) memory; 2) a priority queue used to manage the fron- tier nodes during neighborhood expansion. Since each node is added at most once, the memory usage of the priority queue also (()).
Σ (D)l AA.
We define the redundancy ratio Ried as the ratio between the total number of feature accesses in traditional GNN and the number of neighbor nodes actually used in CMV-ND:
Rist Ei (k- i 1)A'
(8)
4. Experiment
Σx A
In this section, we provide comprehensive evaluation of our proposed CMV-ND by addressing the following ques- tions. We do not conduct an ablation study, as CMV-ND is a plug-an and-play paradigm whose components are inherently indivisible.
The ratio is always greater than for A 2 and A 1, indicating that traditional GNNs repeatedly access neighbor features across layers, while CMV-ND avoids such redun- dancy. Moreover, the redundancy ratio increases with larger and A, illustrating that the inefficiency of traditional mes- sage passing becomes more pronounced in deeper networks or denser graphs.
Q1: Superiority. Does the CMV-ND paradigm out- perform existing state-of-the-art DGC under attribute-
5

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Table Clustering performance comparison among various DGC methods attrihate-missing graphs. The reported results the average clustering outcomes over ten runs six graph datasets with 0.6 missing rate. "OOM" means out-of-memon on a 24 GB RTX 3090 GPU, ""woo" and w/" denote the method without and with CMV-ND preprocessing. respectively.
Dataset
CMV-ND Metric
K-means
DGI
MVGRI.
ProGCI.
AGC-DRR
CCGC
SCGC
AMGC
DinkNet
ACC
31.55:2.23
53.74:12.1
61.26:1..1
1.254
34.92:11.23
36.35
64.53:2.544
67.26:1165
66.541.1.65
NMI
1..9
41.37:11.34
48.43:1..57
35.10=1113
15.63-1167
18.4410.68
4..30:1.47
50.23:11.32
48,23:11.57
wlo
ART
9.12=1115
44.25+40.72
4..74++.94
22.86=1.08
11.51:00.88
1..3441.63
49.32.2..11
44.32+:143
41.5442.21
32.25.1..67
54.20.11.10
59.46.12.09
4..27.1009
23.48.1.97
34.6112.13
61.3711.54
61.9912445
6..57.1..8
ACC
45.55=22.5
61.74+1993
66.3411.11
$1.14=1.24
48.41:1299
43.48
7..34
69.26+1145
12.54+1.29
NMI
21.94:11112
48.37:11.65
67.43-:2.57
43.10=1.51
31.73:11.74
27.441:.34
53.144:.122
54,23:4:.32
54,29-1.77
w/
ARI
25.12:11.15
$6.34
21.51110778
29.34.1.511
48.12.1143
51.54
FI
47.19422.23
60.57++1.49
67.78+1194
11.61=151
54,48+1447
44.72+1883
69.77
62.32+1145
70.57=00.64
ACC
38.27=1.33
53.60=1..31
57.20
08.85=0.33
53.40:11:05
44,80:22.13
17.61
61,23:1877
18.34
17.95:22.28
35.54::1224
34.1242.440
31.4742885
29.1100.56
34.02+11.27
12.87=141
w/o
ARI
14.32:12.91
36.78.1167
27.62.10.78
30.11:1.226
34.48:12.26
28.07.0.577
35.1441..12
35.47:1..88
13,96.1..22
CiteSeer
1.32
49.98
53.85
42.97-2.07
57.2111065
16.96.0.544
58.9111.311
57.34:1.344
ACC
49.27-11.32
60.60
57.20
02.19
57.11:151
13.98
17.17
65.71
68.56
NMI
29.15:22.28
36.54: 84
16.12+1440
19.64=1344
36.412285
08.1
1.
18.14
1..87=1.111
w/
ARI
27.32:#
43.65+1141
29.98+1.21
36.77=1147
37.48:1:.26
34.45
40.5
39.37::1.68
1.77
42.31:12.04
44.96.1..31
60.94:24444
59.64:1:..34
ACC
1.929.1..94
3..06
1.18
35.55
70.48:12.10
54.2310.61
69.9910.43
72.37.10.94
1..77
NMI
1..44
28.64
22.87
28.43-2.37
59.63 40
19.42
63.4411411
66.53:1.811
64.361 1.28
wio
ARI
4.52=1.03
18.46+2.113
1..21=1.26
25.92=1.200
52.42+1333
1.547
1..93
58.13+ 60.15+143
F1
22.96:12.06
29.78:1..11
27.14
26.51=0.62
66.87:11466
$1.277:1.288
62.34
68.03+11.44
1.291
AmizonnPPhote
ACC
16.29:11.25
43.26:12..4
15.45=11.39
40.51=1.19
73,18+1004
61,23+00.88
76.41
75.37++1.67
17.75+1.34
NMI
27.13.11.31
29.87 1..64
1.343
64.4
11.32.11.74
69.3311477
70.53
1.654
w/
ART
1.97
1.8
34.21-2.26
1..27=1.27
16.42211223
1.5
1..43
64.3742.43
26.51 1.71
FI
34.96=1..22
16.54
1..24
36.41=0.57
68.47:1.39
$7.65=1477
71.34
70.03=00.84
72.03+1145
ACC
8.45
18.8
6.623-1662
66.7811.94
26.44.2.144
NMI
12.30:1..76
26.41:1-004
6..17=1113
1.739.1.74
68.95
wko
ART
1.90
15.34.10.74
60.24=1147
OOM
OOM
62.34111.22
61,341 1.46
Reddit
6.80=2.61
48:
47.73=1.88
1.4
$7.98
ACC
28.4511.15
23.9811411
65.23
NMI
1..40=#1.36
33.45=+1477
67.17=1.31
1.34
71.95 1.01
OUM
OOM
ARI
14.111145
24.35:10.84
63.24=1.97
6..37:1:.17
15.41:1:1.62
26.40
23445
1..77
60.97 1.771.1.55
62,87 1.32
ACC
18.11:22.31
23.88:11.79
24.94=1.16
3.99
33.7411 1.47
21.32.12.54
15.4
30.37
32.74 1.24
wko
ART
1.67=1145
1..34:2:.94
OOM
23.03-2.61
OOM
OOM
24.71 1.31
OOM
25.43-100.97
FI
13.94.1..4
23,48
14.61 2.98
21.33.1.14
22.99110.64
agbn-arXiv
ACC
1..11=1.34
27.81
19.94=1.27
35.77 1.07
36.84 2.04
27.32:#1.94
16.21:+1.57
41.74::1007
w/
ARI
20.67.12.43
14.54.12.14
OOM
27.07 1.41
OOM
OOM
28.71 1.47
OOM
30.43:1 1.84
F1
19.94=1.84
1.99
19.81=1998
24.83
1.691+11677
ACC
19:23=1.64
19
26.30=2.43
30.98
31,09=00.04
NMI
22.41=00.86
40.41
41.37=1.03
41.51 2.224
42.71=20.75
w/o
ARI
10.34:12.07
0OM
OOM
OOM
OOM
oghn-products
F1
6.52.12.43
1..61
13.43-22.55
17.51 1.34
15.341: 1.43
ACC.
2..21:11.42
33.54.11.64
21.30
34.57.0.04
35.41
NMI
21.91
42.41+2.74
41.37=2.03
44.31 22337
45.71
w/
ARI
15.41=1.599
19.34
0OM
13.41=2.366
OOM
0OM
1.46
OOM
20.05=0044
F1
14.52:11443
22.87-L1.77
18.53=1.37
22.93 1.64
1.551::.551
missing graph?
Q1-Q3 discussed in Section 4.2-4.4. Due space limitations, we provide the answers to Q4 and Q5 in Appendix D.2 and Appendix D.3.
Q2: Sensitivity. How sensitive is CMV-ND the hyperparameter K, the number of views?
Q3: Efficiency. What are the time and memory costs of CMV-ND on large-scale graphs?
4.1. Experimental Setup
Datasets. To evaluate clustering performance, we use six attribute-based graph datasets, including three small graphs: Cora, CiteSeer, and Amazon-Phoo and three large graphs: Reddit, ogbn-arXiv, and ogbn-products.
Q4: Robustness, Although CMV-ND is designed un- der the assumption of attribute missingness, how does it perform in clustering when the attributes are com- plete?
Implementation Details. To ensure a fair comparison, we conduct 10 experimental iterations under identical condi- tions and report the average results. All experiments are performed on system equipped with 24GB RTX 3090
Q5: Effectiveness. How does the performance of using hop representations derived from propagation methods as milti-view?
6

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
2022), AMGC (Tu et al., 2024a), and Dink-Net (Liu et al.,
Table 2. The performance comparison of six MVC methods attribute- attribueemissing graphs is presented. The reported results are the average clustering outcomes over ten runs on six graph datasets. We use the K 1 views obtained by CMV-ND input. The experiment conducted on graphs with a 0.6 missing rate, after leveraging FP imputation. "OOM" means the out-of-memory failure on 24GB RTX 3090 GPU.
2023b). The MVC methods exploit both consistency and complementarity in view group nodes, including MFLVC (Xu et al., 2022c), MCMVC (Geng et al., 2024), DIMVC (Xu et al., 2022a), and SDMVC (Xu et al., 2022b).
4.2. Clustering Performance Comparation (Q1)
Datasel
Metric
MFLVC
MCMVC
DIMVC
SDMVC
ACC
48.37.1.775
54,7411133
61.26:1..1
48.23 1.54
Since our method does not involve feature imputation for attrbbute-issing nodes, we preprocess all methods with FP (Park et al., 2022) for feature completion to evaluate clustering performance on attribute-missing graphs. The clustering performance of methods based on the CMV-ND paradigm and the comparison methods is summarized in Tables I and Table 2. The missing rate design follows the setting of the method AMGC (Tu et al., 2024a), which uses missing rate of 0.6. From the results, we can draw the following conclusions.
33.2311.67
333371133
55.4322.57
39.06=1.67
Cora
ARI
35.4111.21
41.1411.54
50.74.1.94
25.78_1..75
F1
45.29:2.19
53.20+2.31
63.46=2.09
48.51=1.89
ACC
51.37111.33
1.760
57.20=0.58
61.45=1.34
CiteSeer
31.2511.38
33.4411.77
34.12.1.44
1.06
ARI
29.55+2.34
34.51+1884
27.62=0.78
33.54=1.89
FI
47.57+:1.67
15.48+1.37
53.85-2.33
44.84=1.88 1.87
ACC
42.49:22.25
18.00=1.774
69.85=2.19
38.05=1.33
Amazon
30.23:1.51
24.4421.31
64.87=1.50
31.51=1,46
-Photo
ARI
24.12+2.17
19.31+1664
58.21=1.20 26
27.41=1,45
FI
32.961:1.61
27.89 1.39
60.14:0.93
28.45 1.45
ACC
31.55:22.11
15.54:11.69
64.23=2.13
62.31=1.93
NMI
17.20+11.6
1..
66.35=1.71
63.25=1.04
Reddit
ART
29.91++2.45
13.41
59.23-11466
58.26 1.26
FI
18.80+1141
19.46+0.67
54.28-1442 42
51.33=1.65
The previous state-of-the-art method for attribute- missing graph clustering, AMGC, suffers from out-of- memory (OOM) failures when applied to large graphs, limiting its scalability. Specifically, AMGC fails to complete training on Reddit, ogbn-arXiv, and ogbn- products, while DinkNet combined with CMV-ND com- pletes all runs on these datasets with stable memory usage.
ACC
47.21=1178
25.87=1.89 89
28.44:1.44
27. 27.84=0.56
oghn
NMI
29.124-1.64
1447
27.78-1.56
25.37-0.98
-arXiv
ART
19.47+11.3
14.54+1.76
28.67=0.73
24. 13-1311
FI
23.74.1..64
2
23.15
1,98
ACC
23.21+1.33
26.86+1.54
28.09-0041
24.30-1.33
ogbn
NMI
27.41.10.56
37.4111444
39.71.0.32
38.37-1.31
-products
ART
13.51
L..2
16.15:11667
1.41
F1
18.42:11.75
25.9621.79
13.58=1.75
14.79=1.46
GPU and 64GB RAM. We evaluate clustering performance using four widely adopted metrics (Liu et al., 2023b), in- cluding Accuracy (ACC), Normalized Mutual Information (NMI), Adjusted Rand Index (ARD), and Fl- Fl-score (F1). No- tably, ARI ranges from -1 to 1, while the other metrics range from to 1. All experiments are implemented using Python 3.9 and PyTorch 1.. Unless otherwise specified, we set the number of propagation hops to K and the missing attribute rate to 0.6. For fair comparison, all down- stream clustering methods follow the default hyperparam- eter configurations used in their original implementations. The number of clusters is set to the ground-truth number of classes for each dataset. Additional dataset statistics and descriptions are provided in Table 4.
When our CMV-ND combined with Dink-Net, it not only achieves superior performance on large graphs with missing attributes but also outperforms existing SOTA methods smaller graphs. For example, on Cora, it yields ACC 72.54% and F1 70.57%, surpass- ing all baselines; on Reddit, it achieves the best ACC 69.31% and F1 62.87% among all methods that do not encounter OOM
Comparing the performance of CMV-ND before and after leveraging it to DGC shows that our approach does not result in any negative impact under any cir- cumstance. Across all datasets and metrics, the in- corporation of CMV-ND either improves or maintains performance. Notably, the average ACC improves by 13.8% on Cora and 5.8% on Amazon-Photo.
To demonstrate the superiority of the CMV. ND paradigm, we construct a set of clustering methods based on CMV-ND, which includes a series of DGC and MVC methods. The implementation details can be found in Appendix B. Specifically, for classical clustering, we employ K-Means, which utilizes the concept of anomaly maximization to separate samples. DGC methods leverage GNNs to uncover graph structures, followed by grouping nodes into distinct clusters. These methods include DGI (Velickovic et al., 2019), MVGRL (Hassani & Khasahmadi, 2020), ProGCL (Xia et al., 2022), AGC-DRR (Gong et al., 2022), CCGC (Yang et al., 2023a), S3GC (Devvrit et al.,
Baselines.
While the MVC implementation of CMV-ND is weaker than its DGC counterpart, all MVC methods can be applied to large graphs. For instance, DIMVC reaches 69.85% ACC and 60. Fl on Amazon-Phooke and 64.23% ACC on Reddit, while maintaining feasibility on ogbn-arXiv and ogbn-products. In the future, we plan to design an MVC method specifically tailored for CMV-ND to further enhance its performance in MVC.
In addition, to intuitively illustrate the clustering quality improvements brought by CMV-ND, we employ 2D t-SNE
7

---

Scalable Attribute-Mising Graph Clustering via Neighborhood Differentiation
DGC
CMV-ND+D6C
DGI
MVGRL
CC6C
SI6C
AMGC
Dink-Net
Figure 2. T-SNE visualization of node representations generated by six methods the Co.CS dataset.
(Van der Maaten Hinton, 2008) to visualize node representations generated by six baseline algorithms before and after leveraging CMV-ND. As shown in Figure 2, CMV-ND substantially improves the latent space structure: the orange cluster becomes more compact and coherent, while the purple cluster exhibits fewer cross-class intrusions.
As shown Figure 3, We observe that for all datasets, the method is insensitive the value of K. In all cases, CMV-ND consistently provides positive gain to Dink-Net. Moreover, the highest performance is achieved when K is around (5, 7). Larger values of K do not significantly degrade performance, indicating that our CMV-ND does not suffer from the over-smoothing issue commonly observed in traditional graph propagation paradigms.
4.3. Hyper-Pane Parameerrs Analysis (Q2)
To further evaluate the performance of CMV-ND, we specif- ically investigate the effect of the hyperparameter K on model results. The experimental setup follows Section 4.2, where clustering performance evaluated using the state- of af-the-art combination of CMV-ND and Dink-Net.
4.4. Time and Memory Consumption (Q3)
This section is used to answer the time and memory costs of CMV-ND, Since CMV-ND a preprocessing step, we do not compare with other methods but instead report time and memory usage. As shown Table 3, the preprocessing time and memory consumption of CMV-ND vary across datasets. The costs remain acceptable across all datasets. Since CMV- ND is preprocessing step, it only needs to be executed once, making its computational overhead negligible the long run. Moreover, CMV-ND can be performed on CPUs and memory without relying on GPU resources, ensuring its scalability to large-scale graphs
Cora
Citeseer
70-
02
40-
30
10
Amazon-Photo
Reddit
ACC
NM
ARI
Table 3. Preprocessing time and memory consumption of CMV-ND on different datasets. table reports time cost (in seconds) and CPU memory consumption (in MB) for the preprocessing step of CMV-ND.
02-
66-
60-
62-
Dataset
Time Cost (s)
CPU Memory Cost (MB)
ogbn-product
Cora
5.585
84,59
CiteSeer 3.311
183.3
ACC
NMI
ARI
Amazon-Photo
13.445
247.67
Reddit
189.34
446.64
35-
ogbn-arXiv
144.23
270.46
38-
69
ogbn-products
274.57
672.84
26-
40-
5. Conclusion and Future Work
Figure 3. The hyperparameter analysis of CMV-ND, where the horizontal axis denotes the number differential hops K. Notably, K = 0 corresponds to the original Dink-Nct without CMV-ND.
In this work, we propose a novel paradigm, CMV-ND, to address the challenges of large-scale graph clustering un- der attribute-miset misuue conditions. Our analysis reveals that
8

---

Scalable Attribute-Missng Graph Clustering via Neighborhood Differentiation
the key tackling this challenge lies in effectively lever- aging the graph structure. Unlike the typical "aggregate- encode-predict" pipeline of GNNs, CMV-ND does not rely on propagation operations to utilize the graph structure. In- stead, it directly encodes graph structure information into the views through differential neighborhoods, enabling effi- cient handling large-scale graph data without the need for sampling. Experimental results on six widely-used graph datasets demonstrate that CMV-ND significantly improves the clustering performance of various DGC methods on attribute- attribute-missing graphs. Moreover, CMV-ND naturally bridges the gap between DGC and MVC. While the method achieves promising results, its current implementation in the MVC setting shows slightly weaker performance. As part of future work, we aim develop MVC methods tailored for CMV-ND, with the goal of further enhancing its adapt- ability, model complexity, and performance in real-world applications.
self-supervised graph clustering. Advances in Neural Information Processing Systems, 35:3248-333 0201,,2611111 2022.
Ding, X., Wang. C., Choo, K.-K. R., and Jin, H. A novel
privacy preserving framework for large scale graph data publishing. IEEE transactions on knowledge and data engineering. 33(2):331-343 2019.
Geng. C., Han, A., and Chen, S. Explicit view-labels mat- ter: A multifacet complementarity study of multi-view clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Gong, L.,, Zhou, S., Tu, W., and Liu, X. Attributed graph clustering with dual redundancy reduction. In Pruceed- ings of the International Joint Conference on Artificial Intelligence, pp. 3015-3021, 2022.
Gong, L., Tu, W., Zhou, S., Zhao, L.,, Liu, Z., and Liu, X. Deep fusion clustering network with reliable structure preservation. IFFE Transactions on Neural Networks and Learning Systems, 35(6):7722-7803, 2024.
Acknowledgments
This work is supported by the National Natural Science Foundation of China (No. 62441618, No. 62325604, and No. 62276271), the Natural Science Foundation of Hainan University (No. XI2400009401).
Grill, J.-B., Strub, F., Altché, F,, Tallec, C., Richemond, P., Buchatskaya, E., Doersch, C., Avila Pires, B., Guo, Z., Gheshlaghi Azar, M., et al. Bootstrap your own latent-a new approach self-supervised learning. Advances in neural information processing systems, 33:21271-21284, 2020.
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning.
Guan, R., Tu, W., Wang, S., Liu, J., Hu, D., Tang, C., Feng, Y., Li, J.. Xiao, B., and Liu, X. pructure-adaptiin multi-view graph clustering for remote sensing data. In Proceedings of the AAAI Conference Artificial Intelli- gence, pp. 16933-16941, 2025.
References
Chen, J., Ma, T., and Xiao, C. Fastgen: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the International Conference Learn- ing Representations, 2018
Hamilton, W., Ying. Z., and Leskovee, Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Hassani, K. and Khasahmadi, A. H. Contrastive multi-view representation learning on graphs. In Proceedings of the International Conference on Machine Learning, pp. 41 4116-4126, 2020.
Chen, X., Chen, S., Yao, J., Zheng, H., Zhang, Y., and Tsang, I. W. Learning on attribute-missing graphs. IEEE transactions on pattern analysis and machine intelligence, 44(2):740-757, 2020.
Huo, C., Jin, D., Li, He, D., Yang. Y.-B., and Wu, L. T2-gnn: Graph neural networks for graphs with incom- plete features and structure via teacher-student distillation. Proceedingy of the AAAI Conference on Artificial Intelli- gence, 37(4):4339 4346, 2023.
Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.J. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Pro- ceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Jiang, B. and Zhang, 7. Incomplete graph representation and learning via partial graph neural networks. arXiv preprint arXiv:2003. 10130, 30, 2020.
Dayan, P., Kakade, S., and Montague, R. Learning and selective attention. Nature neuroscience, 3(11):1218- 1223, 2000.
Ju, W., Yi, S., Wang, Y., Xiao, Z., Mao, Z., Li, H., Gu, Y., Qin, Y., Yin, N., Wang, S., et al. A survey of graph neural networks in real world: Imbalance, noise, privacy
Devvrit, F., Sinha, A., Dhillon, I., and Jain, P. S3ge: scalable

---

Scalable Attribute-Missnng Graph Clustering via Neighborhood Differentiation
and ood challenges. In arXiv preprint arXiv:2403.04468, 2024.
Liu, Y., Zhou, S., Yang. X., Liu, X., Tu, W., Li, L.,, Xu, X., and Sun, F. Improved dual correlation reduction network. IEEE Transactions on Neural Networks and Learning Systems, 2024a.
Li, M., Zhang, Y., Zhang, W., Zhao, S., Piao, X., and Yin, B. Csat: Contrastive sampling- aggrrggttnn transformer for community detection in attribute-missin networks. IEEE Transactions on Computational Social Systems, 11 (2):2277-2290, 2023.
Liu, Y., Thu, S., Xia, J., Ma, Y., Ma, J., Zhong, W., Liu, X., Yu, S., and Zhang, K. End-to-end learnable clustering for intent learning in recommendation. In Advances in Neural Information Processing Systems, 2024b.
Lim, D., Hohne, F, Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S. N. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Pro-
Liu, Y. Zhu, S., Yang, T., Ma, J., and Zhong, W. Identify then recommend: Towards unsupervised group recom- mendation. In Advances in Neural Information Process- ing Systems, 2024c.
cessing Systems, 34:20887-20902 2021.
Liu, J., Cheng, J., Han, R., Tu, W. Wang, J., and Peng, X. Federated graph-level clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 18870-18878, 2025.
Pan, S., Hu, R., Fung, S.-f., Long, G., Jiang, J., and Zhang, C. Learning graph embedding with adversarial training methods. IEEE transactions cybernetics, 50(6): 2487,20 2019.
Liu, Y., Tu, W. Zhou, S., Liu, X., Song, L., Yang, X., and Zhu, E. Deep graph clustering via dual correlation reduc- tion. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):7603- 7611,,7761222000 2022a.
Park, J., Lee, M., Chang, H. J., Lee, K., and Choi, J. Y. Symmetric graph convolutional autoencoder for unsuper- vised graph representation learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6519-6528, 2019.
Liu, Y., Xia, J., Zhou, S., Yang, X., Liang, K., Fan, C., Zhuang. Y. Li, S. Z., Liu, X., and Hc, K. A survey of deep graph clustering: Taxonomy, challenge, application, and open resource. arXiv preprint 12X17:2211.12875. 2022b.
Park, N., Rossi, R., Koh, E., Burhanuddin, I. A., Kim, S., Du, F., Ahmed, N., and Faloutsos, C. Cge: Contrastive graph clustering forcommunity detection and tracking. In Proceedings of the ACM Web Conference, pp. 1115-1126, 2022.
Liu, Y., Zheng, Y., Zhang, D., Chen, H., Peng, H., and Pan, S. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference, pp. 1392- 1403, 2022c.
Sun, F-Y.,, Hoffmann, J., Verma, V., and Tang, J. Infograph: Unsupervised and semi-supervised graph-level represen- tation learning via mutual information maximization. In arXiv preprint arXiv: 1e00.01000,00 2019.
Liu, Y., Liang, K., Xia, J., Yang, X., Zhou, S., Liu, M., Liu, X., and Li, S. Z. Reinforcement graph clustering with unknown cluster number. In Proceedings of the ACM International Conference on Multimedia, pp. 3528-3537, 2023a.
Sun, Q., Li, J., Peng, H., Wu, J., Fu, X., Ji, C., and Yu, P. S. Graph structure learning with variational informa- tion bottleneck. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):4165 4174, 2022.
Liu, Y., Liang, K., Xia, J., Zhou, S., Yang, X., Liu, X., and Zi S. Dink-net: Neural clustering on large graphs. In Proceedings of the International Conference Machine Learning, 2023b.
Taguchi, H., Liu, X., and Murata, T. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021.
Thakoor, S., Tallec, C., Azar, M. G., Azabou, M., Dyer, E. L.,, Munos, R., Veličkovié, P., and Valko, M. Large- scale representation learning graphs via bootstrapping. In Proceedings of the International Conference on Learn- ing Representations, 2022.
Liu, Y., Yang, X., Zhou, S., and Liu, X. Simple contrastive graph clustering. IEEE Transactions Neural Networks and Learning Systems, 2023c.
Liu, Y., Yang, X., Zhou, S., Liu, X., Wang, Z., Liang, K., Tu, W., Li, L., Duan, J., and Chen, C. Hard sample aware network for contrastive deep graph clustering. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2023d.
Tu, W., Zhou, S., Liu, X., Guo, X., Cai, Z., Zhu, E., and Cheng, J. Deep fusion clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 9978 9778-998,,00 2021.
10

---

Scalable Attribute-Mising Graph Clustering via Neighborhood Differentiation
Tu, W., Zhou, S., Liu, X., Liu, Y., Cai, Z., Zhu, E., Zhang, C., and Cheng, J. Initializing then refining: A simple graph attribute imputation network. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 3494 3500, 2022.
Transactions on Neural Networks and Learning Systems, 2024b.
Wan, X., Xiao, B., Liu, X., Liu, J., Liang, W., and Zhu, E. Fast continual multi-view clustering with incomplete views. IEEE Transactions on Image Processing, 33:2995- 3008, 2024c.
Tu, W. Guan, R., Zhou, S., Ma, C., Peng, X., Cai, Z Liu, Z., Cheng, J., and Liu, X. Attribute-missing graph clustering network. Proceedings of the AAAI Conference on Artificial Intelligence, 38(1
Wu, F., Souza, A., Zhang. T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In Proceedings of the International Conference on Machine Learning, pp. 6861 6861-6871, 1,66,67722 2019.
2024a.
Tu, W., Liao, Q.. Zhou, S., Peng, X., Ma, C., Liu, Z.,, Liu, X.. Cai, Z., and He, K. Rare: Robust masked graph autoencoder. IEEE Transactions on Knowledge and Data Engineering, 36(10):5300-3355 2024b.
Wu, Q., Zhao, W., Li, 7.,, Wipf, D., and Yan, Nodeformer: A scalable graph structure learning transformer for node classification. In Advances in Neural Information Pro- cessing Systems, volume 35, pp. 22239,, 2022.
Tu, W., Zhou, S., Liu, X., Ge, C., Cai, Z., and Liu, Y. Hier- archically contrastive hard sample mining for graph self- supervised pre-training. IEEE Transactions on Neural Networks and Learning Systems, 2024c.
Xia, J., Wu, L.., Wang, G., Chen, J., and Li, S. Z. Progel: Rethinking hard negative mining in graph contrastive learning. In Proceedings of the International Conference on Machine Learning, pp. -2332.24346. PMLR, 2022.
167611,
Tu, W., Xiao, B., Liu, X., Zhou, S., Cai, Z., and Cheng, J. Revisiting initializing then refining: An incomplete and missing graph imputation network. IEEE Transactions on Neural Networks and Learning Systems, 36(3):3244- 3257, 2025a.
Xu, J., Li, C., Ren, Y., Peng, L., Mo, Y., Shi, X.,, and Zhu, X. Deep incomplete multi-view clustering via mining cluster complementarity. Proceedings of the AAAI conference on artificial intelligence, 36(8):8761-8766 2022a.
Tu, W., Zhou, S., Liu, X., Cai, Z., Zhao, Y., Liu, Y., and He, K. Wage: Weight-sharing attribute-missing graph autoencoder. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-18, 2025b.
Xu, J., Ren, Y., Tang, H., Yang. Z., Pan, L.,, Yang. Y., Pu. X., Philip, S. Y., and He, L. Self-supervised discriminative feature learning for deep multi-view clustering. IEEE Transactions Knowledge and Data Engineering, 35 (7)74470-7482, 2022b.
Um, D., Park, J., Park, S., and young Choi, J. Confidence- based feature imputation for graphs with partially known features. In Proceedings of the International Conference on Learning Representations, 2023.
Xu, J., Tang. H., Ren, Y., Peng, I.., Zhu, X., and He, Multi-level feature learning for contrastive multi-view clustering. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 16051- 16060, 2022c.
Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 9(1)), 2008.
Xue, H., Mallawaarachchi, V., Zhang, Y., Rajan, V., and Lin, Y. Repbin: constraint-based graph representation learning for metagenomic binning. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):4637- 4645, 2022.
Velickovic, P., Fedus, W., Hamilton, W. L., Liò, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Wan, X., Liu, J., Liang, W., Liu, X., Wen, Y., and Zhu,
E. Continual multi view clustering. In Proceedings of the ACM International Conference on Multimedia, pp- 3676-3684, 2022.
Yang, X., Liu, Y., Zhou, S., Wang, S., Tu, W., Zheng, Q. Liu, X., Fang, I.., and Zhu, F. Cluster-guided con- trastive graph clustering network. Proceedings of the AAAI conference on artificial intelligence, 37(9):00834- 10842, 2023a.
Wan, X., Liu, J., Gan, X., Liu, X., Wang, S., Wen, Y., Wan, T., and Zhu, F., One-step multi-view clustering with diverse representation. IEEE Transactions on Neural Networks and Learning Systems, 36(3):1-13, 2024a.
Yang, X., Tan, C., Liu, Y., Liang, K., Wang. S., Zhou, S., Xia, J., Li, S. Z., Liu, X., and Zhu, E. Convert: Contrastive graph clustering with reliable augmentation. Proceedings of the ACM International Conference on Multimedia, pp. 1199-27,,40 2023b.
Wan, X., Liu, J., Yu, H., Qu, Q. Li, A., Liu, X., Liang, K., Dong. Z., and Zhu, E. Contrastive continual mul- tiview clustering with filtered structural fusion. IEEE

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Yang, X., Wang, Y., Liu, Y., Wen, Y., Meng, L.,, Zhou, S., Liu, X., and Zhu, E. Mixed graph contrastive network for semi-supervised node classification. ACM Transactions on Knowledge Discovery from Data, 2024.
Yin, N., Wang, M., Chen, Z., De Masi, G., Xiong, H., and Gu, B. Dynamic spiking graph neural networks. Proceed- ings of the AAAI Conference on Artificial Intelligence, 38 (15):14495- 2024.
Yoo, J., Jeon, H., Jung, J., and Kang, U. Accurate node feature estimation with structured variational graph toencoder. In Proceedings of the ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, Pp. 2336-2346, 2022.
Yu, S., Liu, S., Wang, S., Tang, C., al. Sparse low-rank multi multi-view subspace clustering with consensus anchors and unified bipartite graph. IEKE Transactions on Neural Networks and Learming Systems, 2023.
Yu, S., Dong, Z., Wang, S., Wan, X., Liu, Y., Liang, W., Zhang, P., Tu, W., and Liu, X. Towards resource- friendly, extensible and stable incomplete multi-view clustering. In Proceedings of the International Conference on Machine Learning, 2024a.
resource-friendlyy
Yu, S., Wang, S., Dong, Z., Tu, W., Liu, S., Lv, Z., Li, P., Wang, M., and Zhu, E. A non-parametric graph clus- tering framework for multi-view data. Proceedings of the AAAI conference on artificial intelligence, 38(15):
16558-16567, 2024b.
Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arviv: 1907.0493,, 2019.
Zhu, Y., XI, Y., Yu, F., Liu, Q., Wu, S., and Wang, I.. Deep graph contrastive representation learning, arXiv preprint 04131,, 2020.
12

---

Appendix of "Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation"
A. Notations & Datasets
The basic notations are outlined in Table 4. These notations provide formal foundation for our study, ensuring clarity and consistency in the subsequent discussions.
Table 4. The notations.
Notation
Meaning
A
Adjacency Matrix
V
Set of Vertex
E
Set of Edges
d
Feature Dimension
G
Attribute-missing Graph
A
Maximum degree of any node in the graph
(v)
k-differential hop neighhorhood
(*)
k-hop neighborhood
s(
State at the k-th hop
H E Rd h²(w) E Rdd
Node Attribute Matrix
k-differential hop neighborhood representation
Table 5 summarizes the key statisties of the six datasets used in this study. These datasets span a wide range sizes and characteristics. For instance, CiteSeer includes 3,327 nodes and 4,614 edges, while Amazon-Photo consists of 7,650 nodes and 119,081 edges. Furthermore, the graph densities also differ significantly. As an example, Cora has density of 0.07%, whereas Amazon-Photo exhibits density of 0.25%.
Table 5. Statistics of six datasets.
Dataset
Type
Nodes
# Edges
# Feature Dims
# Classes
Cora CiteSeer
Citation Graph
2,708
5,278
1,433
7
Citation Graph
3,327
4,614
3,703
6
Amazon-Photo
Co-Purchase Graph
7,650
119,081
745
8
ogbn-arxiv
Citation Graph
169,343
1,166,243
128
40
Reddit
Social Network Graph
232,965
23,213,838
602
41
ogbn-produce
Co-Purchase Graph
2,449,029
61,859.140
100
47
B. How to Leverage Multi-View Representations for Graph Clustering?
In this section, we demonstrate how multi-view representations be applied to graph clustering methods: DGC and MVC. We focus proving the consistency and complementarity of multi-view representations in these tasks.
DGC. The multi-view representations be directly fused to form unified node representation for clustering. For example, we concatenate the feature vectors from each view, resulting in a combined representation. Let h, be the feature vector for node the k-hopp neighborhood. The fused representation huse can be written as:
13

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
h concat(h! ( h!
(1)
where h² E _d represents the feature vector of node in the i-th neighborhood view. This fused representation can then be directly used as input for DGC.
MVC. MVC algorithms typically rely on the assumption that different views provide complementary information while maintaining consistency. Our multi-view representations naturally satisfy these conditions.
Consisteney. The consistency of the multi-view representation is grounded in the homophily assumption, which posits that nodes with similar attributes tend to be connected in the graph. Given this assumption, nodes that are close in the graph, i.e., those with similar local structures, will have similar representations across different views. Formally, for nodes e and u, if DD (v) D (u) for some k; then the multi-view representations h. and ha across different views will be close:
- h = for alli {0, kk..
k).
(10)
Complementarity. The complementarity of the multi-view representations arises from two key aspects. On the one hand, different hops neighborhood, such as the k-hop neighborhood, capture node relationships from different perspectives. Specifically, the k-differrnnial hop neighborhood captures local structural information, while the (k 1)-differential hop neighborhood helps understand the global relationships between nodes. On the other hand, Eq. (2) ensures that each neighborhood view contributes non-overlapping information to the multi-view representation, thereby providing complementary insights into the position of the node within the graph.
C. Additional Relate Work
C.1. Deep Graph Clustering
This section discusses recent advances in deep graph clustering (DGC) for attribute-complet graphs, where existing methods can be broadly categorized into two main paradigms: (1) graph autoencoder- based methods (reconstruction models) and (2) contrastive Learning- bbann methods.
Graph Autoencoder-basee Methods. To effectively utilize both graph structure and node attributes, many cxisting approaches employ autoencoder- based architectures (Tu et al., 2024b; 2025b). These methods typically use GNNs to encode node representations, aiming to reconstruct the graph structure via the inner product of the learned embeddings. Notable examples include graph auto-encoder (GAF) and variational graph auto-encoder (VGAH), which learn low-dimensional representations to capture latent graph structures, thereby improving clustering performance. Building upon the autoencoder framework, graph adversarial learning approaches (GALA) (Park et al., 2019), adversarially regularized graph autoencoder (ARGA), and adversarially regularized variational graph autoencoder (ARVGA) (Pan al., 2019) introduce Laplacian sharpening and generative adversarial learning to enhance representation learning. Further extending this paradigm, deep fusion clustering network (DFCN) (Tu et al., 2021) integrates representations learned from both autoencoders and graph autoencoders for more robust consensus representation learning.
Contrastive Learning-basee based Methods. Contrastive learning has emerged as powerful paradigm for graph clustering, deep graph infomax (DGI) (Velickovic et al., 2019) improves embedding representations by maximizing mutual information between global and local graph structures. InfoGraph (Sun et al., 2019) extends DGI by learning unsupervised representations at the graph level. Multi-view graph representation Learning (MVGRL) (Hassani & Khasahmadi, 2020) further enhances these ideas by leveraging node diffusion and contrasting node representations across augmented graph views. More recent advancements include graph contrastive learning and enhanced (GRACE) (Zhu al., 2020), which maximizes node embedding consistency between corrupted graph views. Bootstrapped graph latents (BGRL) (Thakoor al., 2022) builds upon the bootstrap your own latent (B YOL) (Grill et al., 2020) framework, introducing self-supervised learning the graph domain while eliminating the need for negative sampling. Moreover, Liu et al. (2022a; 2024a) design the dual correlation reduction strategy the DCRN model to alleviate the representation collapse problem. Besides, HSAN (Liu et al., 2023d) mines the hard sample pairs via the dynamic weighting strategy. And SCGC (Liu et al., 2023c) simplifies the graph augmentation with parameter-und unnhardd Siamese encoders and embedding disturbance, Despite effectiveness, contrastive
14

---

Scalable Attribute-Misiing Graph Clustering via Neighborhood Differentiation
learning-based methods are computationally expensive due to their reliance on graph augmentations and complex objective functions, making them difficult to scale to large datasets. A scalable method termed Dink-Net (Liu et al., 2023b) is proposed to solve this problem. Besides, (Liu et al., 2023a) is presented to solve the problem of the unknown number of clusters via reinforcement learning. Benefiting from these, deep graph clustering methods are applied to practical applications like recommendations (Liu et al., 2024b;c). More details can be found in this survey paper (Liu et al., 2022b).
C.2. Large-Scale Graph Learning
In recent years, numerous scalable GNN methods have been developed to address the challenges of large-scale graph data processing. Graph sample and aggregation (GraphSAGE) (Hamilton et al., 2017) introduces an inductive learning framework that efficiently processes large graphs by sampling and aggregating node features from local neighborhoods. Fast graph convolutional network (FastGCN) (Chen et al., 2018) further improves efficiency by performing node sampling independently at each layer, effectively reducing computational and memory overhead. To enhance scalability, simplified graph convolution (SGC) (Wu et al., 2019) decouples transformation and propagation in graph convolutional network (GCN), significantly improving computational efficiency. GraphSaint (Zeng et al., 2019) and clustered graph convolutional network (Cluster-GCN) (Chiang et al., 2019) maintain graph structure integrity through subgraph sampling, enabling more effective large-scale graph processing.
C.3. Attribute-Missing Graph Completion
The objective of suribute-misssng graph completion is to enable effective learning on graphs where node attributes are partially or entirely missing. This problem has garnered significant attention, and existing approaches can be broadly categorized into two paradigms: (1) gen-based models and (2) feature completion methods.
GCN-based Models. GCN-based models aim to directly encode graphs with missing attributes while simultaneously restoring the missing information during the learning process. These methods typically leverage GCNs to handle incomplete attribute data (Tu et al., 2022; 2025a). GCN for Missing Features (GCNMF) (Taguchi et al., 2021) introduces a Gaussian Mixture Model (GMM) to adjust GCNs for attribute-missing graphs. Similarly, Partial GNN (PaGNN) (Jiang & Zhang, 2020) employs a partial message passing (MP) scheme that integrates known features during propagation. While these methods perform well in semi-supervised settings, they rely on label supervision to implicitly restore missing attributes. As result, they are not applicable to unsupervised tasks such as graph clustering, where label information is unavailable.
Feature Completion Methods. Feature completion methods restore missing node attributes as a preprocessing step. without relying GCN encoding or parameterized learning. To eliminate label dependence, methods such as feature propagation (FP) (Park et al., 2022) and pseudo-confidence feature imputation (PCFT) (Um et al., 2023) leverage the graph topology to reconstruct missing attributes. FP propagates known features across the graph to impute missing values, while PCFI introduces channel confidence, assigning reliability scores to inferred features to improve robustness.
C.4. Graph Structure Learning and Search Methods
Graph structure learning (GSL) and structure refinement have emerged as promising directions for enhancing graph learning tasks by optimizing or inferring the adjacency matrix. Recent works such as SUBLIME (Liu et al., 2022c), Nodeer (Wu et al., 2022), and VIB-GSL (Sun et al., 2022) explore this avenue from different perspectives. SUBLIME adopts an unsupervised self-supervised contrastive learning framework to jointly learn graph structure and node embeddings for clustering tasks. NodeFormer designs a kernerlized gumbel-softmax operator for edge prediction, enabling structure refinement through pairwise node correlations. VIB-GSL introduces variational inference and information bottleneck principles to learn robust and generalizable graph structures.
Despite their effectivenesss, these methods generally assume access to complete node attribute information to either guide similarity estimation or construct informative graph structures. In contrast, our work specifically targets the attribute-min -missing setting, where many nodes lack features entirely. Under such conditions, structure learning methods depending on pairwise feature similarity or global embedding consistency become unreliable or even infeasible.
15

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
D. Additional Experimental Result
D.I. Comparison with SAT, ITR, and SVGA
To further verify the generality and compatibility of CMV-ND, we conduct additional experiments comparing it with three representative methods tailored for attribute miseeig graphs: SAT (Chen al., 2020). ITR (Tu et al., 2022), and SVGA (Yoo al., 2022). We evaluate their original performance well their variants enhanced with CMV-ND as preprocessing step. As shown in Table CMV-ND consistently improves clustering performance across all three hase methods Cora, Citeseer, and Amazon-Photo under 60% feature missing rate. In particular, notable gains are observed in both clustering accuracy and stability.
Table Clustering performance (%) of SAT, ITR, and SVGA on attribute- mesbbbtte-mssingg graphs. All experiments use 0.6 missing rate. Reported results averages 10 runs. OOM denotes out-of memorry failure scale graphs
Dataset
Metrie
SAT
SAT + CMV-ND
ITR
ITR CMV-ND
SVGA
SVGA + CMV-ND
ACC
1.07
1.142::1.11
1.18
52.13
45.56 1.94
55.41 1.29
NMI
34.05=10.84
16.95
22.86=100.5
30.47:10.94
29.94412.32
39.36 1.27
Cora
ARI
27.14+10.92
1.14
8.41
18.87
18.72::..22
29.34
53.68:10.91
1.108
35.07=11003
46.07:11.02
41.84:1.441
$1.49:
ACC
38.44:10.82
48.79:::109
1..54
4..68
18.41
$7.29::1.22
NMI
14.01
25.85=+0..8
19.58
29.01
26,91
33.14
Citeseer
ARI
12.2441.006
20.81=1.221
7.03
14.67
17.03=11116
24.53++1.28
FL
36.89:10.76
1.06
34.64:11.29
46.32:t1.19
45.41
56.88:11.35
ACC
42.91
13.05
36.27-11116
4..69
6..74
19.02-+1.31
NMI
13.65
56.23-10.93
1..2
1..58
64.89
12.19
Amazon-Photo
ARI
30.11
1.066=11.02
22.31
34.12::1.18
34.9611..21
49.21
FI
36.04-10.94
1..92
31.75=11002
42.41
52.91
13.82-:1.29
D.2. Clustering Performance Attribute-Complete Graphs (Q4)
To evaluate the robustness of our paradigm, we also conduct experiments attribute-complete graphs As shown in Table 7, the results indicate that when node attributes fully available, DGC methods incorporating CMV-ND exhibit nearly identical performance to their original counterparts. This suggests that our approach is non-intrusive and does not negatively impact clustering in strriute-compledd settings. An exciting finding is that the classic K-means algorithm exhibits a remarkable performance improvement, even surpassing many DGC methods. We hypothesize that this hecause conventional K-means does not leverage graph structures, whereas our CMV-ND effectively compensates for this limitation.
D.3. Evaluating Multi-View Representations Derived from Propagation -Based Hops (Q5)
The proposed CMV-ND constructs multiple views for graph clustering by leveraging differential hop representations. Naturally, one might consider whether graph propagation paradigms can also generate multi-view representations in a similar manner. Specifically, we construct views using the multiplication of the adjacency matrix and the feature matrix:
Formally, given graph G (V,E) with adjacency matrix and node attribute matrix H, derive series of views by leveraging the propagation operation iteratively:
H 1H with H H.
(11)
where (k) represents the propagated node features after iiterations. In this setup, each (k) can be regarded as separate view, akin the multi-view representations generated by CMV-ND.
Subsequently, we utilize these views as inputs to various DGC methods and evaluate their clustering performance. The experimental setup follows that of Section 4.2 to ensure consistency. As shown in Table 8, compared to the baseline results in Table 1, the propagation- inferior to CMV-ND. This observation further substantiates the effectiveness of modeling node hop representations as milti-views.
multi-view representations generally outperform the original DGC methods but remain
16

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Table Clustering performance comparison among various DGC methods attribate- graphs. The reported results the average clustering outcomes over ten runs six graph datasets, "OOM" means out-of mem-ory 24 GB RTX 3090 GPU. ""wo" and denote method without and with CMV-ND preprocessing, respectively.
Dataset
CMV-ND Metrie
K-means
DGI
MYGRL.
ProGCL
AGC-DRR
SCGC
DinkNet
ACC
33.781138
72.61:1003
7.44
56.96:11:25
40.6711.60
74.2910.83
76.171:990
NMI
14.89.10.70 5..16:1.64
60.75-1.49
40.84:10.00
18.63
58.7841.60
60.25:1:10 1.63
w/o
ART
8.58+1800
51,15+0.88
56.77=0.71
30.5841.755
14.76:00.8
14.3721466
1.773
F1
30.29.10.86 69.1711800
7..66.1.00
45.7411447
1,95
1.92441944
10.50.11.87
ACC
14.00:1:46
71.69+1.24
75.31=1.59
57
41.25+1.89
73.98
15.86+1993
NMI
57.10:10.73 1..76:11.59
61.42=1.24
40.64:1..19
18.93119.7
58.65
59.96-11.48
w/
ARI
14.12.11.27
59.68.1.588
F1
72.50++-133
69.2242..04
72.48=1.08
44,86+11449
31.45+1.70
22.21+2.15
70.95+1994
ACC
39.3340.76
68.7420998
02.67=1.22
66.10:11:99
68.3
08.74
68.30=11177
NMI
16.76+181 43.4611.44
39.43-0.88
13.1441.63
44.27=0.95
43.95:11.39
w/o
ARI
13.35.11333
44.41110.2
34.31
36.22.11.74
45.40:1
44,9411411
45.99111.266
CiteSeer
36.25.1.17
04.45
1.76
57.7541.775
64.87.0.75
6..40
65.12:1:.42
ACC
68.11
68.04 1.08
63.00
65.90 88
18.00.33
6..92.11.87
67.82.1
NMI
43.45:00.67
1.307=1.30
1..17=1.22
40. 80.12:00:00
1.5
1.158
12.12
w/
ARI
43.47:20.35
44.63=20994
34.82=1.09
36.29::1.57
43.40:21.17
45.30=1..44
46.35
ACC
2..25.11.06
13.1
40.99
51.58.1087
1.22
7..16
79.72.11.84
NMI
13.43:1 96
33.51
30.27=0.93
66 66.74 19.66::1.76
19.78
74.56:t
w/o
ARI
5.60=0.89
1.797
1.76
34.29:+0.80
60.26++0.94
1.61
67.43+0771
FI
23.84:20.84
1.91
1.183=1.111
31.91:11011
1..03:1..59
72.95=1.56
71.80:1441
Amazon-Phute
ACC
67.21=-1.74
42.82+1881
41.42=1.99
1.98
51.42:10.79
76. 1.19
7..51
79.39:1:.97
NMI
41433114
34,47
31,15
1.01
39.26.111.70
1.16
5..91
74.8911.88
w/
ART
3.
11.51
19.05
1,80
34.27-10.78
1.22
1.555
67.58.1083
FI
13.93
15.3
31.86=111
31.23:::126
1.77
1.52
41
9.06:E1.74
1.62
65.39.10.4
73,70
72.90-10.84
NMI
11.55:10.91
46.76:11110
1..30:11.73
80.67
76.79111.13
ARI
3.06:11.75
1.32
63.32.11.75
74.53-11001
70.39:1
Reddit
FI
6.78:20772
1.17
1.739
66.93 1.111
37.59.10.97
NMI
21 2.004:11099
07.69=0.97
69.42-
80.66:0.87
16
0OM
ARI
15:10:1:150
17.51
63.08:1:2.00
7.152:11.18
10.12:1:.110
36 1.
1.17
50.67-1.
55.29
66.74.11.9
ACC
18.15:11.00
02.39:11..88
29. 29.72:1:1.17
3.902211.44
41.57:11.78
w/o
ART
22.29.11.70
7.48:10.92
63.60-10884
0OM
25.78 1 1.05
OOM
46.36
26.80 1.30
34.35:11.39
13.07.11.66
11.99
21.74.1...57
1.22
26.10.1..000
ogbn-arXiv
ACC
44.59++1.63
23.07=11772
29. 29.25=t:1.37
14.55
41.72
36.90-1:1.95
37.61:12.002
w/
ARI
30.41.12.37
63.83110.22
0OM
25.14.1.1.21
OOM
2..13
34.78.11.51
F1
30.31:11.56
51.10=11.44
21.77::1.50
1..61#1.144
26.49:11.12
ACC
18.24:21.76 11.30:1..00
15.39771.07
40.07=1.022 13.65$1.117
39.01E1
NMI
22.24=11441
41.14:0..2
46.50:1:0.90
18.77::1.16
w/o
12.13
0OM
19.91111.75
OOM
10.95:11.30
oghn-products
FI
12.77-1147
22.98
21.57:11.90
25.01 1 1.02
24,14:11.00
ACC
36.07-11.30
31.41
35.41-11.17
39.68 10.94
39.30-1163
NMI
31 4595
01.22:10.77
46 46.24-1:0.2
53.78
48 15
w/
ARI
24.50=L1.61
21.26=:1006
0OM
20.13:+:.55
OOM
2..92
20.
F1
24.81:1146
23.45
20.69:12.007
24.25
24.45-1-.08
E. URLs of Used Datasets
This section gives the URLs of the used benchmark datasets in Table5.
Cora: https///bccs.gglaaa//oonnnnaaaa
CiteSeer http:///ccs..gg.aaggggg.aacaaact
Amazon-Photo: htw.:///ww.ooooooo.././..oa/aaaa
ogbn-arxiv: htpp:///ggsasaiiotttllccoooooenn
Reddit: http:///bo..q...jigg/ddddaaddddt
egbn-products: htwp:///g...aanniauuuooooooooooo
17

---

Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation
Table Clustering performance of various DGC methods using multi-view representations derived from propagation based hops. The reported results are averaged over ten runs on six benchmark datasets. All experiments are conducted under 60% missing rate. "OOM"
indicates an memoory failure on a 24GB RTX 3090 GPU.
Dataset
Metric
K-meams
DGI
MVGRI.
ProGCI.
AGC-DRR
CCGC
GC
AMGC
Dink-Net
ACC
1
2.39
44.73
1.57
1:
1.65
NMI
18.78 1 1.32
44.90
1: 1.69
64.53
1: 2.85
40.35
1 143
28.45
1: 1.94
24.19 1 1.36
49.37 1 1.62
52.57 1 1.48
51.57
= 1.57
Cora
ART
21.40
+ 1.71
18.38
25.48
50.02
46,75
- 1.68
48.56
44.87
1: 2.05
58.47
1.44
65,78
2.37
48.47
1.53
50.75
1: 2.05
41.22
1 2.30
66.80
1 1.77
62.90
1: 2.57
67.27
1,98
ACC
46.34
56.93
+: 1.67
57.35
= 0.68
59.57
+ 0.96
54.05
+ 1.63
51.88
2.21
64.31
+ 1.53
63.41
+ 2.70
65.28 = 1.55
CiteSeer
37.85
ART
25.10 3.01
40.16 +: 1.73
28.13
+ 1.43
33.61
+ 48
34.74
+ 2.51
31.93 - 0.67
37.23
4: 2.27
37.67
+ 2.57
38.17 1.59
39.46
55.65
55.31
2.42
53.67
+
57,50
42.30
58.57
58.21
58.53
1.41
ACC
33.26
1.99
39.53 1. 2.67
38,66
1.45
38.03
2.34
70.83
2.26
55.22
1.14
73.73 1: 0.53
72.85
1.71
75.41
1.47
Amuzon-Phuute Photo
NMI
23.80
1.54
40.94
1: 1.61
26.90
1: 1.77
40.19
+: 2.62
62.24
+ 1.68
47.77
= 195
67.08
+ 1.50
69.00
+: 2,88
68.63 = 1.81
61.78
63.31
FI
31.63
- 2.34
34.45
+ 1.83
39.78
1.95
33.69 + 80
67,82 + 1.69
54.09
=
1.42
67.55 + 1.87
69.00 + 1.86
68.85 1.45
ACC
24.76
1. 2.26
21.58
2.03
62.83 1. 1.78
67.54 1: 2.18
66.96 2.14
NMT
10.82.
1.95
30.32 1.39
64.46 + 1.40
68.34 +: 2.00
68.95 1.70
ARI
12.90 = 2.24
21.87
1.02
61.07 + 2.17
62,90 + 1.38
61.78 1.76
+:
56.98 +:
60.53
ACC
30.62
2.51
29.16
2.01
26.80 1: 1.18
33.72 1: 2.04
34,37 2.14
oghn-arXiv
NM1
2.84 23.38
35.66
1,87
OOM
30.48 1: 1.19
OOM
COM
37.16 1: 1.34
OOM
38.78 1.24
ARI
17.96
2.25
12.24
+ 2.23
23.89 2.71
24.90 + 1.44
26.68 1.86
F1
13.94 2.08
23.58
+ 2.11
16.17 + 3.12
21.39 + 1.49
22.99 1.77
13 1.72
30.21
32.33 :
32.17
oghn-products
NMI
22.72
1.09
40.83
2.55
41,90 1: 1.80
41.80 1 2.49
42.71 0.75
ART
12.45
1.47
15.78
2.29
12.56 +: 2.29
18.64 + 1.49
18.05 1.11
12.03
2.60
17.38
1.07
15.50
19.14 +
19.67 1.69
F. Py Ttrch Pseudocode
We provide the PyTorch-ttyle pseudocode for our CMV-ND in Algorithm 2.
18

---

Scalable Attribute-Missin Graph Clustering via Neighborhood Differentiation
Algorithm 2 PyTorch-style pseudocode for CMV-ND
Finds differential k-hop neighbors using a priority queue. 2 graph: adjacency list representation of the graph.
3 node: target node.
4 k: hop distance.
def h
(graph, node, k)
7
visited = set () # Track visited nodes pq [] # Priority queue storing (hop count, node)
9
heappush (pq, (0, node)) Push the starting node into the queue
10
diff hop = () # Set to store differential k-hop nodes
while pq:
13
hops, curr_ curr_node node = heappop (pq) Process nodes based on hop count
priority
if hops
break
16
if hops == k and curr_node != node: # Only record differential nodes diff_hop.. add
17
if hops < # Expand neighborhood for neighbor in [curr__cu__oool if neighbor not in visited:
19
20
visited. add (neighbor) heappush (pq, (hops 1, neighbor)
22
23
return diff_hop
24
puppute_aumenterr features: Computes differential hop mean features.
26
graph: adjacency list representation of the graph.
27
fode_features: feature matrix of nodes.
28
max_hop: maximum hop distance
consider.
30
def seaatt__aymeetedefettueeee (graph, node features, max_ :
31
jum_nodes feature dim node feteeeffaturssseee shape augmented features forch.zeree (max_hoe 1, num noden, feature_dimi Initialize augmented feature tensor
33
Step 1: Assign original features as 0-hop representations
augmented_features [0] node_features
36
37
# Step 2: Compute differential hop features from 1-hop to max_hop
for node in range poum_nodes)>
Iterate over all nodes
39
for k in range (1, max_hop 1): # Iterate over each hop distance # Get differential k-hop neighborhood
40
41
diff hop diff k hop hop_priority_guee (graph, node, k) if len (diff_hop)
0:
43
# Compute mean feature of neighboring nodes node_featured (list (diff_hop)
44
hop_mean neighbor_ mean (dim=0) e else:
47
# If the differential neighborhood is empty, use zero vector hop_mean torch. (feature dim)
48
Store hop_mean in the corresponding position
50
srggentted_fatture [k, node] = mea_
51
return augmented_features
19


Reviews:
[{"review_id": "Ijdsg0DWOy", "reviewer": "Reviewer_CDeB", "summary": "This paper presents a deep clustering method, namely Complementary Multi-View Neighborhood Differentiation (CMV-ND), to conduct clustering tasks in large-scale and attribute-missing graphs. CMV-ND adopts the Recursive Neighborhood Search to capture the complete local structure and the Neighborhood Differential Strategy to prevent redundancy among different hop representations. These presented strategies can well be integrated into existing clustering approaches to learning representations for various downstream tasks. Experimental results may validate the effectiveness of the proposed CMV-ND.\n\n## Update after rebuttal\n\nThe authors have addressed most of my concerns. Still, there are issues regarding method design and unstable performances after authors’ rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer CDeb\n\nWe thank the reviewer for the careful reading and valuable feedback. Below, we address each concern raised.\n\n---\n\n**W1:** *Lack of discussion on structure learning/search methods.*\n\nWe have considered structure learning and structure search methods, such as SUBLIME (WWW 2022), NodeFormer (NeurIPS 2022), and VIB-GSL (AAAI 2022). However, these methods rely heavily on complete node attributes to guide structure refinement or similarity estimation, making them inapplicable to the attribute-missing scenario targeted by our work. We will clarify this point and include a discussion of these works in the related work section of the final version.\n\n---\n\n**W2:** *Definitions 1 and 2 are unclear; need example.*\n\nWe have revised *Definitions 1 and 2* to improve clarity. Specifically, we now explain that the $k$-hop neighborhood $\\mathcal{N}^k(v)$ includes all nodes within distance $k$, while the $k$-differential hop neighborhood $\\mathcal{D}^k(v)$ includes nodes at exactly distance $k$. Additionally, we provide a concrete example to illustrate the difference between these definitions.\n\n> “For example, consider a graph with edges $\\{(v,a), (v,b), (a,c)\\}$. Then: $ \\mathcal{N}^1(v) = \\{v, a, b\\}, \\quad \\mathcal{N}^2(v) = \\{v, a, b, c\\}$. The corresponding differential hop neighborhoods are: $\\mathcal{D}^1(v) = \\{a, b\\}, \\quad \\mathcal{D}^2(v) = \\{c\\}.$”\n\n---\n\n**W3:** *Insufficient discussion on how RNS and NDS contribute to multi-view clustering.*\n\nThis connection is discussed in **Section 3.3.3** and **Appendix B**. We will make this connection more explicit in Section 3.3.3 by adding the following clarification:\n\n> “To enable graph clustering, we propose to construct multi-view node representations based on the structural granularity of neighborhoods. Specifically, the RNS is used to efficiently locate multi-hop neighbors, while the NDS allows us to isolate information from each exact $k$-hop, thus forming multi-view node representations.”\n\n---\n\n**W4:** *Lack of analysis on redundancy reduction.*\n\nWe have conducted a theoretical analysis to quantify the redundancy reduction of CMV-ND compared to message-passing GNNs. In a $k$-layer GNN, the total number of neighbor feature accesses is $\\sum_{i=1}^k (k - i + 1) \\cdot \\Delta^i$, where $\\Delta$ is the average node degree. In contrast, CMV-ND accesses each differential hop neighborhood only once: $\\sum_{i=1}^k \\Delta^i$. The redundancy ratio is therefore $\\frac{\\sum_{i=1}^k (k - i + 1) \\cdot \\Delta^i}{\\sum_{i=1}^k \\Delta^i}$. This ratio increases with larger $k$ and higher $\\Delta$, highlighting that message-passing GNNs involve significant redundancy, while CMV-ND avoids it by design. We will include this analysis in the final version.\n\n---\n**W5:** *Similarity to PageRank-based GNNs.*\n\nWe clarify that CMV-ND differs from these methods in several key aspects:\n\n- PageRank-based GNNs fuse multi-hop information into a single representation via propagation, while CMV-ND retains non-overlapping differential-hop representations as distinct views.\n- PageRank-based GNNs assign decaying weights to distant neighbors, leading to incomplete structural coverage. In contrast, CMV-ND deterministically collects the complete, non-redundant differential-hop neighborhoods.\n- PageRank-based GNNs require end-to-end training. CMV-ND is a non-parametric, training-free preprocessing strategy.\n\nThe use of multi-hop information is a common practice in GNNs (e.g., JK-Net aggregates features from multiple hop levels) and does not, by itself, imply novelty concerns.\n\n---\n\n**W6:** *Whether cross-view redundancy, consistency, or conflicts are considered.*\n\nWe would like to clarify that we have discussed the consideration of cross-view redundancy and consistency in **Appendix B**. Specifically, the NDS ensures that each $k$-differential hop neighborhood is non-overlapping, inherently avoiding redundancy across views. Consistency is supported under the homophily assumption, where nearby nodes exhibit similar representations across views. Complementarity arises from the structural granularity, as each hop-level view captures distinct topological information. Furthermore, CMV-ND retains multi-view representations and delegates the task of weighting or combining views to downstream clustering models, which can adaptively handle potential conflicts.\n\n---\n\n**W7:** *Lack of detailed experimental settings.*\nSection 4.1 of the manuscript introduces the experimental setup, including datasets, metrics, environment, and baselines. Since CMV-ND is non-parametric and training-free, it has no learnable components. Nevertheless, we will supplement the final version with the following details:\n- Python 3.9 and PyTorch 1.12.\n- Number of propagation hops $K=7$, missing rate = 0.6, FP iterations = 40.\n- Default hyperparameters for downstream clustering methods.\n\n---\n\n**Q1–Q6:** \n\nThese questions correspond to the concerns in **W1–W7**, and have been addressed above.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "NIL.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The approach proposed in this paper may potentially advance large-scale graph clustering, which is an important topic in machine learning and data mining.", "essential_references_not_discussed": "The authors are suggested to discuss works related to structure search or learning in graph neural networks/deep graph clustering to better show the novelty of the proposed method.", "other_strengths_and_weaknesses": "Strengths:\n1. The problem tackled in this paper is essential for deep graph clustering.\n2. The method proposed in this paper is effective in standard graph clustering tasks.\n\nWeaknesses:\n1. Some definitions (e.g., Definitions 1 and 2) are not well explained, which makes this paper not very readable.\n2. How the proposed strategies, i.e., Recursive Neighborhood Search and the Neighborhood Differential Strategy may contribute/connect to multi-view graph clustering is not clearly discussed in the paper.\n3. To what extent the proposed approach can reduce the redundancy of the neighboring aggregation process is not analyzed.\n4. The proposed approach is also similar to GNNs based on (PageRank), which aggregates different orders/hops neighbors to learn representations. How is the proposed approach different from these GNNs?\n5. Do authors consider cross-view redundancy, consistency, or conflicts when constructing the output representations for downstream tasks?\n6. The detailed experimental settings are not introduced in the manuscript/appendix.", "other_comments_or_suggestions": "NIL.", "questions_for_authors": "1. Some definitions (e.g., Definitions 1 and 2) are not well explained. Can authors use a clear example to explain these definitions?\n2. How do the proposed strategies, i.e., Recursive Neighborhood Search and the Neighborhood Differential Strategy, contribute/connect to multi-view graph clustering?\n3. Have the authors conducted any theoretical analysis showing to what extent the proposed approach can reduce the redundancy of the neighboring aggregation process?\n4. The proposed approach is also similar to GNNs based on PageRank, which aggregate different orders/hops neighbors to learn representations. How is the proposed approach different from these GNNs?\n5. Do authors consider cross-view redundancy, consistency, or conflicts when constructing the output representations for downstream tasks?\n6. How are those clustering approaches configured in the experiments?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NIL."}}, {"review_id": "RHgUT2haCU", "reviewer": "Reviewer_7mCA", "summary": "The paper addresses the challenge of clustering nodes in large-scale graphs that often suffer from missing attributes, a common scenario in real-world applications such as social networks and recommendation systems. To tackle this, the authors propose the Complementary Multi-View Neighborhood Differentiation (CMV-ND) paradigm. The key components of CMV-ND include: Recursive Neighborhood Search (RNS) and Neighborhood Differential Strategy (NDS). By combining the original node features with the aggregated representations from each differential hop, the method constructs a multi-view representation. These multi-view representations can then be seamlessly integrated with existing deep graph clustering (DGC) or multi-view clustering (MVC) methods. Experimental results on six widely used graph datasets demonstrate that CMV-ND significantly enhances clustering performance.\n\n## update after rebuttal\nAfter the rebuttal, I want to keep the original rating, mainly due to the novelty issues.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer 7mCA\n\nWe thank the reviewer for the thoughtful comments and constructive suggestions. Below, we address each concern raised.\n\n---\n\n**W1:** *Lack of comparison with SAT, ITR, and SVGA.*\n\nWe have conducted additional experiments comparing CMV-ND with three representative methods for attribute-missing graphs: SAT (TPAMI 2020), ITR (IJCAI 2022), and SVGA (KDD 2022). For the reviewer’s convenience, we temporarily provide the results via the following anonymous link:\n(https://anonymous.4open.science/r/icml2025_CMV-ND-2211/sat_itr_svga_results.md)\n\n---\n\n**W2:** *Similarity to GraphSAGE and novelty concerns.*\n\nWe respectfully clarify the fundamental differences between CMV-ND and GraphSAGE:\n\n- GraphSAGE is a parameterized, end-to-end GNN that samples neighbors at each hop to reduce cost. CMV-ND deterministically retrieves the complete differential-hop neighborhoods without sampling.\n- GraphSAGE requires training with learnable aggregation. CMV-ND is a non-parametric, training-free preprocessing strategy.\n- GraphSAGE fuses multi-hop signals into a single embedding. CMV-ND preserves non-overlapping differential-hop views for downstream clustering.\n\nFor fair comparison, we implemented a preprocessing variant of GraphSAGE that averages sampled neighbors at each hop, keeping the rest identical to CMV-ND. We also included Node2Vec as a baseline. Results show that CMV-ND consistently outperforms both under attribute-missing settings. For the reviewer’s convenience, we provide these results in\n(https://anonymous.4open.science/r/icml2025_CMV-ND-2211/graphsage_node2vec_comparison.md)\n\n---\n\n**W3:** *Notation inconsistency in equations.*\n\nWe have carefully reviewed the notations and corrected the inconsistencies. Specifically:\n- Equation (1) has been revised to:  \n  $N_{i+1}(v) = N_i(v) \\cup \\left( \\bigcup_{u \\in N_i(v)} N(u) \\right)$\n- The redundant use of the symbol $a$ in line 246 has been removed.\n- Equations (6) and (7) have been revised to:\n  - $S_v^{(k)} = S_v^{(k-1)} + \\sum_{u \\in \\mathcal{N}(v)} S_u^{(k-1)}$\n  - $S_v^{(k)} = S_v^{(0)} + \\sum_{t=1}^{k} \\sum_{u \\in \\mathcal{N}(v)} S_u^{(t-1)}$\n- The expression in line 243 has been revised to:\n  $\\sum_{i=0}^{k} \\Delta^i = 1 + \\Delta + \\Delta^2 + \\dots + \\Delta^k = \\mathcal{O}(\\Delta^k)$\n\nWe confirm that Equation (4) is correct and does not require modification.\n\n---\n\n**W4:** *Lack of attention mechanism to weigh hop-level importance.*\n\nCMV-ND intentionally avoids attention mechanisms to preserve its non-parametric and training-free nature. Introducing attention would require trainable components, contrary to CMV-ND’s design goal. Moreover, early fusion across hop-level representations would obscure structural diversity. Instead, CMV-ND leaves view-level weighting to downstream clustering models, following standard practice in multi-view clustering. In future work, we plan to develop a dedicated clustering model with view-level attention to adaptively fuse differential-hop representations.\n\n---\n\n**W5:** *Memory complexity concern.*\n\nWe respectfully clarify that the memory complexity in Algorithm 1 does not accumulate across all nodes in practice. CMV-ND processes nodes in mini-batches, and memory is released after each batch. Section 4.4 further reports empirical memory usage, showing linear scalability with the number of nodes. We also note that Reviewers 69Ph and WHi9 have confirmed the reasonableness of the memory complexity.\n\n---\n\n**W6:** *Dense formatting of tables.*\n\nWe acknowledge the readability issue and will improve the formatting of Tables 1, 6, 7, and 8 in the final version by adding clearer separations between methods and datasets.\n\n---\n\n**W7:** *Scalability claim not convincingly demonstrated.*\n\nThe scalability emphasized in our work refers to CMV-ND itself. The OOM issues in Table 1 stem from downstream DGC models, not from CMV-ND. This is not unique to our method—Node2Vec, despite its title claiming scalability (“node2vec: Scalable Feature Learning for Networks”), also causes OOM when paired with AMGC. Thus, the scalability of preprocessing should be evaluated independently of downstream model limitations.\n\n---\n\n**W8:** *Ineffectiveness of t-SNE visualization.*\n\nWe agree that the t-SNE visualization in Figure 2 does not clearly demonstrate CMV-ND’s effectiveness, primarily because the small number of nodes in Cora makes cluster structures less distinguishable in low-dimensional projections. To address this, we have replaced the visualization with results on the larger Co-CS dataset. In the updated figure, CMV-ND yields clearer cluster boundaries: the orange cluster is no longer split into two parts, and the purple cluster contains fewer intrusions from other classes. For convenience, we provide the updated visualization at (https://anonymous.4open.science/r/icml2025_CMV-ND-2211/tsne_cocs_visualization.png).", "claims_and_evidence": "Overall, many of the submission’s claims are supported by extensive empirical results on multiple datasets. For example, the claims about improved clustering performance on attribute‐missing graphs and scalability are backed by comprehensive experiments, including performance tables, T-SNE visualizations, and time/memory usage data.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are well-aligned with the challenges of clustering on large-scale, attribute-missing graphs. The use of standard clustering metrics (Accuracy, NMI, ARI, F1) along with datasets provides a robust framework for evaluation.", "theoretical_claims": "The paper does not include formal proofs for its theoretical claims. In essence, the experimental results are presented without corresponding rigorous theoretical proofs that would further substantiate the claimed benefits of CMV-ND.", "experimental_designs_or_analyses": "The experimental design is sound and well-aligned with the problem, but there are a few aspects that warrant further discussion:\n\n- Comparing alternative feature preprocessing methods such as node2vec and GraphSage would help assess whether the improvements are inherent to the CMV-ND paradigm.\n- Incorporating more baselines, especially those specifically designed for attribute-missing graphs, would provide a more comprehensive evaluation of the method’s performance in realistic settings.", "relation_to_broader_scientific_literature": "- It extends deep graph clustering (DGC) research, which includes methods like DGI, MVGRL, and Dink-Net, by addressing two critical challenges simultaneously: scaling to large graphs and handling missing node attributes. Prior work has typically tackled these issues in isolation, so combining them fills a notable gap in the literature.\n- Since CMV-ND constructs multi-view representations of nodes within the graph, it naturally bridges the gap between graph clustering and Multi-View Clustering (MVC).", "essential_references_not_discussed": "The paper cites an extensive set of related works spanning deep graph clustering, attribute-missing graph clustering, and scalable graph learning.", "other_strengths_and_weaknesses": "**Strengths**\n\n1. The paper presents a well-motivated approach for clustering large-scale, attribute-missing graphs.\n2. The experimental evaluation is extensive, covering multiple datasets and metrics.\n\n**Weaknesses**\n\n1. While the experiments are thorough, the paper would benefit from additional comparisons with related works, particularly:\n    \n    Chen, X., Chen, S., Yao, J., Zheng, H., Zhang, Y., and Tsang, I. W. Learning on attribute-missing graphs. IEEE transactions on pattern analysis and machine intelligence, 44(2):740–757, 2020.\n    \n    Tu, W., Zhou, S., Liu, X., Liu, Y., Cai, Z., Zhu, E., Zhang, C., and Cheng, J. Initializing then refining: A simple graph attribute imputation network. In IJCAI, pp. 3494–3500, 2022.\n    \n    Yoo, J., Jeon, H., Jung, J., and Kang, U. Accurate node feature estimation with structured variational graph autoencoder. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2336–2346, 2022.\n    \n2. CMV-ND shares similarities with GraphSAGE in its neighborhood aggregation approach, which raises concerns about novelty. Conducting experiments where GraphSAGE is used for feature propagation could help clarify CMV-ND’s unique advantages.\n3. Equation (1) should be revised to: $N_{i+1}(v) = N_i(v) \\cup \\left( \\bigcup_{u \\in N_i(v)} N(u) \\right)$?, the notation $\\mathcal{N}^i(a)$ appears on line 246 but is missing from Equation (4), which might indicate an inconsistency or typo.\n4. CMV-ND treats each hop’s neighborhood embeddings separately, effectively severing connections between different hop levels. This assumes all hop-distance information is equally important, which may not always be the case. Introducing an attention mechanism could help weigh the contributions of different hop distances more adaptively.\n5. The memory complexity analysis in Algorithm 1 is given per node. However, for the entire graph, the worst-case complexity is $O(n^2)$, which is infeasible for large-scale graphs.\n6. Tables 1, 6, 7, and 8 are difficult to read due to their dense formatting. Improved formatting, such as clearer separations between methods and datasets, would make comparisons more intuitive.\n7. Despite the paper’s title emphasizing scalability, the experimental results do not convincingly demonstrate scalability. Some deep graph clustering (DGC) methods still encounter out-of-memory (OOM) errors after applying CMV-ND, as seen in Table 1.\n8. The T-SNE visualization in Figure 2 does not clearly demonstrate CMV-ND’s effectiveness.", "other_comments_or_suggestions": "None", "questions_for_authors": "See Other Strengths And Weaknesses*", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZKbbyk2T61", "reviewer": "Reviewer_WHi9", "summary": "This paper proposes a method called Complementary Multi-View Neighborhood Differentiation (CMV-ND) to address deep graph clustering (DGC) on large-scale graphs with missing node attributes. CMV-ND captures multi-hop local structures using a Recursive Neighborhood Search (RNS) and eliminates redundancy with a Neighborhood Differential Strategy (NDS), generating K+1 complementary views for each node. The key contributions are: (1) bypassing the \"aggregate-encode-predict\" paradigm of GNNs by directly storing differential neighborhood information; (2) encoding graph structure in a non-redundant multi-view format to mitigate the effects of attribute missingness; and (3) offering a flexible framework for existing graph or multi-view clustering methods. Experimental results on six benchmark datasets demonstrate improvements, especially in large-scale graphs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer WHi9\n\nWe thank the reviewer for the thoughtful comments and helpful suggestions. Below, we address each point in detail.\n\n---\n\n**W1:** *By treating graph data as two views—attribute view and structural view—it is natural to frame the graph clustering problem as a multi-view clustering problem. Therefore, the experiments should include comparisons between this two-view setup and the multi-view setup of CMV-ND in terms of MVC methods.*\n\nWe agree that comparing the traditional two-view setup (attribute view + structural view) with the multi-view setup generated by CMV-ND can provide valuable insights. To this end, we have conducted an additional experiment in which we construct two views: (1) the original attribute (with missing entries), and (2) a structural view based on the adjacency matrix. These are then input into standard MVC methods such as MFLVC and DIMVC. We compare the results against the same methods using the $k{+}1$ views generated by CMV-ND. These comparisons will be included in the final version. \n\n---\n\n**W2:** *There seems to be an error in the citation for AMGC. The correct reference should be: Tu, W., Guan, R., Zhou, S., Ma, C., Peng, X., Cai, Z., ... & Liu, X. (2024, March). Attribute-missing graph clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 14, pp. 15392-15401).*\n\nWe apologize for the incorrect citation. We have corrected it to:\n\nTu, W., Guan, R., Zhou, S., Ma, C., Peng, X., Cai, Z., ... & Liu, X. (2024). *Attribute-missing graph clustering network*. In AAAI (Vol. 38, No. 14, pp. 15392–15401).\n\nWe have also rechecked the references throughout the manuscript to ensure accuracy in the final version.\n\n---\n\n**W3:** *It would be beneficial to explicitly clarify that AMGC represents the state-of-the-art for attribute-missing graph clustering, while Dink-Net is the prior state-of-the-art for large-scale graph clustering. This distinction would offer a clearer context for evaluating the contributions of the paper.*\n\nWe agree with the suggestion. In the revised version, we will explicitly state that **AMGC** represents the state-of-the-art for **attribute-missing graph clustering**, while **Dink-Net** is a recent state-of-the-art method for **large-scale graph clustering**. This distinction will help contextualize our contributions more clearly.\n\n---\n\n**C1:** *There are several typographical and formatting inconsistencies in the manuscript that should be addressed. In Figure 1, the font size of the symbol v is too small and may hinder readability. Additionally, there is an unnecessary period at the end of line 326, while the caption for Table 2 is missing a period. Lastly, in line 243, two different styles of the O notation are used for the time complexity of RNS, which should be made consistent.*\n\nThank you for pointing out the typographical and formatting issues. We have carefully reviewed the manuscript and addressed the specific items you mentioned:\n\n- In **Figure 1**, we have increased the font size of the node label $v$ to improve readability and ensure consistency with other text elements in the figure.\n- The **unnecessary period at the end of line 326** has been removed.\n- The **missing period in the caption of Table 2** has been added to maintain punctuation consistency across all table and figure captions.\n- For the **time complexity notation in line 243**, we had previously used both $\\mathcal{O}(\\cdot)$ and $\\mathbf{O(\\cdot)}$ styles. We have revised all instances to consistently use the standard O notation $\\mathcal{O}(\\cdot)$ throughout the manuscript.\n\nIn addition to correcting these specific issues, we will perform a thorough proofreading pass to eliminate any remaining inconsistencies or formatting errors in the final version.\n\n---\n\n**Q1:** *The writing in Section 3.3.4 is somewhat unclear. The authors seem to argue that the \"aggregate-encode-predict\" paradigm introduces redundancy in utilizing graph structure, whereas the proposed CMV-ND method does not. However, the term \"Graph Propagation\" has not been mentioned earlier in the paper. Would it be more appropriate to use \"message-passing paradigm\" instead for consistency and clarity?*\n\nWe agree that “message-passing paradigm” is more accurate and consistent than “graph propagation.” We will revise Section 3.3.4 accordingly to use the standard term and rephrase the paragraph for improved clarity.\n\n---\n\nWe greatly appreciate your careful review and insightful comments. They have been invaluable in helping us refine the presentation and deepen the discussion of our contributions. We will incorporate all necessary revisions in the final version, and we remain open to any further suggestions you may have.", "claims_and_evidence": "The manuscript claims that effective large-scale deep graph clustering with missing attributes relies on leveraging graph structure, as it is the only available information in such scenarios. The authors support this claim through strategies like differential hops, which address key challenges in attribute-missing graph clustering. Empirical results show notable performance improvements over existing methods. Additionally, the paper asserts the method’s scalability, supported by complexity analysis (Section 3.4) and evaluations of time and memory consumption (Section 4.4).", "methods_and_evaluation_criteria": "The evaluation framework adopted in this paper aligns well with standard practices in deep graph clustering research. The authors employ ACC, NMI, ARI, and F1 scores, which are widely recognized and appropriate metrics for clustering tasks, ensuring comparability with prior work. In terms of benchmark datasets, the selection includes Cora, Citeseer, Amazon-Photo, Reddit, ogbn-arXiv, and ogbn-products, covering both small-scale and large-scale graphs.", "theoretical_claims": "I have reviewed the theoretical aspects of the manuscript and found no apparent issues. The key equations are logically consistent with the proposed framework, and the complexity analysis in Section 3.4 provides a reasonable estimate of the computational demands.", "experimental_designs_or_analyses": "The experimental design is based on a well-established setup, following the \"Attribute-Missing Graph Clustering Network\" (AAAI 2024), which ensures that the results are comparable with previous work.", "relation_to_broader_scientific_literature": "The paper aims to extend the \"Attribute-Missing Graph Clustering Network\" (AAAI 24) problem, as defined in previous work, to large-scale graphs. While the motivation centers on addressing the challenge of deep graph clustering under attribute-missing conditions, the proposed methodology appears to have broader applicability. Specifically, the approach offers a novel utilization of graph structure, which can be viewed as an alternative to existing message-passing paradigms in graph clustering.", "essential_references_not_discussed": "No essential related works are missing in the current manuscript.", "other_strengths_and_weaknesses": "Strength\n(1) The motivation behind the paper, which addresses the challenge of large-scale deep graph clustering with missing attributes, is clearly articulated. The proposed solution effectively addresses the challenges of large-scale deep graph clustering with missing attributes by enhancing the utilization of graph structural information, which aligns well with the motivation behind the paper.\n(2) The proposed method introduces a novel paradigm for utilizing graph structure, which differs from conventional message-passing paradigms.\n(3) The approach presented in the paper enables the use of multi-view clustering for graph data, effectively bridging the gap between multi-view clustering and graph clustering.\n\nWeakness\n(1) By treating graph data as two views—attribute view and structural view—it is natural to frame the graph clustering problem as a multi-view clustering problem. Therefore, the experiments should include comparisons between this two-view setup and the multi-view setup of CMV-ND in terms of MVC methods.\n\n(2) There seems to be an error in the citation for AMGC. The correct reference should be: \n\tTu, W., Guan, R., Zhou, S., Ma, C., Peng, X., Cai, Z., ... & Liu, X. (2024, March). Attribute-missing graph clustering network. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 14, pp. 15392-15401).\n\n(3) It would be beneficial to explicitly clarify that AMGC represents the state-of-the-art for attribute-missing graph clustering, while Dink-Net is the prior state-of-the-art for large-scale graph clustering. This distinction would offer a clearer context for evaluating the contributions of the paper.", "other_comments_or_suggestions": "There are several typographical and formatting inconsistencies in the manuscript that should be addressed. In Figure 1, the font size of the symbol v is too small and may hinder readability. Additionally, there is an unnecessary period at the end of line 326, while the caption for Table 2 is missing a period. Lastly, in line 243, two different styles of the O notation are used for the time complexity of RNS, which should be made consistent.", "questions_for_authors": "Q1: The writing in Section 3.3.4 is somewhat unclear. The authors seem to argue that the \"aggregate-encode-predict\" paradigm introduces redundancy in utilizing graph structure, whereas the proposed CMV-ND method does not. However, the term \"Graph Propagation\" has not been mentioned earlier in the paper. Would it be more appropriate to use \"message-passing paradigm\" instead for consistency and clarity?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZW6ovXtXxE", "reviewer": "Reviewer_69Ph", "summary": "This paper presents a novel approach for deep graph clustering (DGC) in the presence of missing node attributes and large-scale graph structures, termed Complementary Multi-View Neighborhood Differentiation (CMV-ND). CMV-ND achieves this by pre-processing graph structural information into multiple views in a non-redundant manner. The authors introduce a Recursive Neighborhood Search (RNS) to explore the local structure of the graph across different hop distances and a Neighborhood Differential Strategy (NDS) to ensure non-overlapping node representations across different hops. The resulting multiple views are then fed into existing multi-view clustering or DGC methods. The paper demonstrates the effectiveness of CMV-ND through extensive experiments on six widely-used graph datasets, where it shows significant improvements over various baselines in terms of clustering performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer 69Ph\n\nWe thank the reviewer for the careful reading and constructive feedback. Below, we address each concern in detail.\n\n---\n\n**W1:** *The experimental results omit comparisons with some recent state-of-the-art methods in Deep Graph Clustering (DGC). It would be beneficial to include performance results for the following methods.*\n\nWe appreciate the suggestion to include additional recent DGC methods. Following your recommendation, we have added **HSAN** (Hard Sample Aware Network, AAAI 2023) as an additional baseline in our experiments. We report its performance with and without CMV-ND preprocessing on small-scale datasets. For large-scale datasets (Reddit and ogbn-products), HSAN encounters OOM (Out-Of-Memory) errors both before and after applying CMV-ND, due to its intrinsic memory consumption.\n\nThe results on Cora and Citeseer are summarized below:\n\n| Dataset   | Metric | HSAN (Original)    | HSAN + CMV-ND      |\n|:---------:|:-----:|:------------------:|:------------------:|\n| **Cora** | ACC   | 57.86 ± 1.34      | 65.42 ± 1.09      |\n|         | NMI   | 41.92 ± 1.31      | 51.18 ± 1.22      |\n|         | ARI   | 33.09 ± 1.71      | 43.74 ± 1.38      |\n|         | F1    | 58.65 ± 0.95      | 66.12 ± 1.07      |\n| **Citeseer** | ACC   | 44.35 ± 0.61      | 50.38 ± 1.02      |\n|         | NMI   | 22.17 ± 1.32      | 27.25 ± 1.29      |\n|         | ARI   | 13.26 ± 1.02      | 17.94 ± 1.21      |\n|         | F1    | 42.06 ± 2.41      | 49.15 ± 2.04      |\n\n---\n\n**W2:** *Limited MVC baselines and overly general claim.*\n\nWe agree that the MVC baselines in the current version can be further expanded. Following your recommendation, we have additionally included two recently published state-of-the-art MVC methods:\n\n- **SCMVC** (Self-Weighted Contrastive Fusion for Deep Multi-View Clustering, TMM 2024)\n- **DCMVC** (Dual Contrast-Driven Deep Multi-View Clustering, TIP 2024)\n\nWe evaluated these methods under the same CMV-ND paradigm with a missing rate of 0.6. The updated experimental results are summarized below:\n\n|Dataset|Metric|SCMVC|DCMVC|\n|:-:|:-:|:-:|:-:|\n|**Cora**|ACC|61.74±1.12|60.29±1.24|\n||NMI|45.62±1.48|44.13±1.57|\n||ARI|43.82±1.26|41.06±1.34|\n||F1|58.34±1.35|57.01±1.49|\n|**CiteSeer**|ACC|57.21±1.33|55.96±1.46|\n||NMI|37.35±1.29|35.71±1.53|\n||ARI|32.84±1.48|31.56±1.65|\n||F1|52.68±1.44|51.12±1.52|\n|**Reddit**|ACC|63.27±1.14|62.03±1.25|\n||NMI|61.35±1.03|60.41±1.14|\n||ARI|54.29±1.25|53.11±1.31|\n||F1|61.47±1.19|60.82±1.27|\n|**ogbn-products**|ACC|27.84±0.97|27.13±1.04|\n||NMI|35.24±0.85|34.12±0.94|\n||ARI|18.03±0.93|17.42±1.05|\n||F1|22.84±0.89|21.95±0.92|\n\nWe will revise the manuscript to include these results and will accordingly moderate the original claim about the superiority of DGC methods.\n\n---\n\n**W3:** *Missing evaluation under varying attribute missing rates.*\n\nWe agree with this suggestion and have conducted additional experiments by varying the attribute missing rate from 0.1 to 0.9. Instead of reporting nine separate tables, we summarize these results using line charts to clearly illustrate the performance trends. These plots will be included in the final version. \n\n---\n\n**W4:** *The role of the priority queue in Algorithm 1 is not clearly explained, and there is a lack of sufficient explanation about its purpose and function within the algorithm.*\n\nWe clarify that the priority queue in Algorithm 1 serves as a control mechanism for incrementally expanding the neighborhood of a target node in order of increasing graph distance. We will revise the text in Algorithm 1 and its accompanying explanation to more clearly articulate this role and improve overall readability.\n\n---\n\n**C1:** *Lack of quantitative analysis in experiments.*\n\nWe agree with your suggestion and will include key quantitative metrics in the final version. For example, we will report the relative performance improvement of CMV-ND over AMGC on Cora and other datasets to provide a clearer picture of the effectiveness of our method.\n\n---\n\n**C2:** *Delayed definition of \"differential hop.\"*\n\nWe agree that the concept of \"differential hop\" plays a central role in our method and that improving its visibility can help readers better follow the paper. We will make the formal definition in Section 3.1 more prominent by explicitly referencing it when \"differential hop\" is first introduced, ensuring a smoother connection between the introductory mentions and the formal exposition.\n\n---\n\n**Q1–Q6:** *Problems that have been solved*\n\nThese questions correspond to the concerns in **W1–W4** and **C1–C2**, which we have addressed above with additional experiments and clarifications.\n\n---\n\n**Q7:** *Release of CMV-ND processed datasets.*\n\nWe will make these processed datasets publicly available along with our source code in the final release.", "claims_and_evidence": "The main claim of the manuscript is that the key to effective large-scale deep graph clustering with missing attributes lies in the efficient utilization of graph structural information. This claim is intuitively supported, as for a graph, the available view information typically includes three aspects: node attributes, graph structure, and labels. In the scenario of attribute-missing clustering, the only available information is the graph structure, making this claim reasonable and intuitive. Furthermore, the experimental results, which show significant improvements in clustering performance compared to prior methods, provide robust empirical evidence to substantiate the claim.\n\nThe secondary claim is that existing message-passing paradigms for large-scale graphs suffer from redundancy and omission when utilizing graph structural information. The authors explain the redundancy issue in Section 3.3.4, and it is also pointed out that current large-scale graph clustering methods often involve sampling steps that disrupt the graph structure. This claim appears to be well-supported and valid.", "methods_and_evaluation_criteria": "The authors use ACC, NMI, ARI, and F1 scores to evaluate clustering performance, which are standard and commonly used metrics in the field. Similarly, the datasets Cora, Citeseer, Amazon-Photo, Reddit, ogbn-arXiv, and ogbn-products are appropriate benchmarks for assessing the proposed method's performance on large-scale graphs.", "theoretical_claims": "I have reviewed the correctness of the theoretical claims and did not identify any apparent errors in the manuscript's theoretical aspects. Specifically, I have verified the key formulas in the methodology section, namely Eq. (1) through (8), and reviewed the complexity analysis in Section 3.4. Additionally, Appendix B provides an explanation of why the proposed method is applicable to multi-view clustering (MVC).", "experimental_designs_or_analyses": "The experimental design follows the setup of the AMGC algorithm (published at AAAI 2024, titled \"Attribute-Missing Graph Clustering Network\"). The primary experiments are conducted with a 0.6 missing rate, which allows for a meaningful comparison with AMGC. Therefore, the experimental setup is reasonable. Additionally, the manuscript also reports results for a 0.9 missing rate, providing further insight into the performance of the proposed method under more challenging conditions.", "relation_to_broader_scientific_literature": "The paper builds upon the work presented in the AAAI 2024 paper titled \"Attribute-Missing Graph Clustering Network,\" which defines the problem of attribute-missing graph clustering. This manuscript extends the problem to large-scale graphs through a preprocessing approach. Furthermore, it bridges the fields of multi-view clustering and deep graph clustering, enabling the use of multi-view methods for graph data.", "essential_references_not_discussed": "To the best of our knowledge, the manuscript has provided a thorough discussion of the related work. No essential related works appear to be missing in the current version of the paper.", "other_strengths_and_weaknesses": "**Strength**\n\n(1) The proposed method introduces a new paradigm for leveraging graph structure by preserving it across multiple views through search and differential techniques. This approach is not a combination of existing methods, but rather presents a novel strategy to address the challenges of large-scale graphs with missing attributes.\n\n(2) The idea of leveraging multi-view clustering for graph data is a novel and interesting contribution. This perspective opens up new possibilities for graph clustering, particularly in the context of missing node attributes.\n\n(3) The authors provide clear pseudocode, Overall workflow, and PyTorch-style code to illustrate the methodology presented in the paper.\n\n(4) The role of the priority queue in Algorithm 1 is not clearly explained, and there is a lack of sufficient explanation about its purpose and function within the algorithm.\n\n**Weakness**\n\n(1) The experimental results omit comparisons with some recent state-of-the-art methods in Deep Graph Clustering (DGC). It would be beneficial to include performance results for the following methods:\n\nLiu, Y., Yang, X., Zhou, S., Liu, X., Wang, Z., Liang, K., ... & Chen, C. (2023, June). Hard sample aware network for contrastive deep graph clustering. In Proceedings of the AAAI conference on artificial intelligence (Vol. 37, No. 7, pp. 8914-8922).\n\n(2) The experiment includes too few MVC methods, and the selection does not cover the most recent advancements. The claim in the paper that MVC methods are inferior to DGC methods in the CMV-ND paradigm appears overly simplistic. I recommend adding the following MVC methods to Table 2 for comparison and reconsidering the conclusions:\n\nWu, S., Zheng, Y., Ren, Y., He, J., Pu, X., Huang, S., ... & He, L. (2024). Self-Weighted Contrastive Fusion for Deep Multi-View Clustering. IEEE Transactions on Multimedia.\n\nCui, J., Li, Y., Huang, H., & Wen, J. (2024). Dual contrast-driven deep multi-view clustering. IEEE Transactions on Image Processing.\n(3) The paper lacks performance evaluation of CMV-ND under different attribute missing rates. I suggest demonstrating CMV-ND's clustering performance across a range of missing rates (from 0.1 to 0.9) and comparing it to other DGC methods.\n\n(4) The role of the priority queue in Algorithm 1 is not clearly explained, and there is a lack of sufficient explanation about its purpose and function within the algorithm.", "other_comments_or_suggestions": "(1) The experimental section primarily provides qualitative descriptions of the results, without presenting a detailed quantitative analysis. While I understand that this may be due to page limitations in the initial submission, I recommend adding key quantitative metrics in the final version. For example, the paper could include performance improvements, such as the percentage gain over AMGC on the Cora dataset, to give readers a clearer sense of the method's effectiveness.\n\n(2) The concept of \"differential hop\" is mentioned in both the introduction and abstract but is formally defined only in Section 3.1. To avoid potential confusion for readers, I suggest revising the paper to either introduce the concept earlier or make sure the definition is more prominent and clearly connected to its initial mention in the introduction and abstract.", "questions_for_authors": "Q1: The experimental results omit comparisons with some recent state-of-the-art methods in Deep Graph Clustering (DGC). Would it be possible to include performance results for the following methods?\n\nLiu, Y., Yang, X., Zhou, S., Liu, X., Wang, Z., Liang, K., ... & Chen, C. (2023, June). Hard sample aware network for contrastive deep graph clustering. In Proceedings of the AAAI conference on artificial intelligence (Vol. 37, No. 7, pp. 8914-8922).\n\nQ2: The experiment includes too few MVC methods, and the selection does not cover the most recent advancements. The paper claims that MVC methods are inferior to DGC methods in the CMV-ND paradigm. Would it be possible to include the following MVC methods in Table 2 for comparison and reconsider the conclusions?\n\nWu, S., Zheng, Y., Ren, Y., He, J., Pu, X., Huang, S., ... & He, L. (2024). Self-Weighted Contrastive Fusion for Deep Multi-View Clustering. IEEE Transactions on Multimedia.\n\nCui, J., Li, Y., Huang, H., & Wen, J. (2024). Dual contrast-driven deep multi-view clustering. IEEE Transactions on Image Processing.\n\nQ3: The paper lacks performance evaluation of CMV-ND under different attribute missing rates. Would it be possible to demonstrate CMV-ND's clustering performance across a range of missing rates (from 0.1 to 0.9) and compare it to other DGC methods?\n\nQ4: Could you clarify the role of the priority queue in Algorithm 1? A more detailed explanation of how it contributes to the overall algorithm would help improve the understanding of the method.\n\nQ5: The experimental section primarily provides qualitative descriptions of the results, without presenting detailed quantitative analysis. While I understand that this might be due to initial submission page limitations, would it be possible to include key quantitative metrics in the final version? For example, could you report performance improvements, such as the percentage gain over AMGC on the Cora dataset, to give readers a clearer sense of the method’s effectiveness?\n\nQ6: The concept of \"differential hop\" is mentioned in both the introduction and abstract but is formally defined only in Section 3.1. To avoid potential confusion for readers, would it be possible to introduce this concept earlier in the paper, or ensure that the definition is more prominently connected to its initial mention in the introduction and abstract?\n\nQ7: Would it be possible to release the multi-view version of the graph datasets constructed by CMV-ND? This would be of significant value to the MVC community and could facilitate further research and comparison across different methods.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In the initial submission, the reviewers held slightly differing attitudes regarding the content and quality of this manuscript. After the authors' detailed responses, the overall attitude of the reviewers tended to shift in a more positive direction, with some reviewers even raising their scores accordingly. I believe this manuscript holds a certain level of contribution to the community. After careful evaluation and consideration, I am inclined to accept this paper.
Decision: Accept (poster)