Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation

Response to Reviewer 69Ph

We thank the reviewer for the careful reading and constructive feedback. Below, we address each concern in detail.

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.

We 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.

The results on Cora and Citeseer are summarized below:

W2: Limited MVC baselines and overly general claim.

We 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:

• SCMVC (Self-Weighted Contrastive Fusion for Deep Multi-View Clustering, TMM 2024)
• DCMVC (Dual Contrast-Driven Deep Multi-View Clustering, TIP 2024)

We evaluated these methods under the same CMV-ND paradigm with a missing rate of 0.6. The updated experimental results are summarized below:

We will revise the manuscript to include these results and will accordingly moderate the original claim about the superiority of DGC methods.

W3: Missing evaluation under varying attribute missing rates.

We 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.

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.

We 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.

C1: Lack of quantitative analysis in experiments.

We 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.

C2: Delayed definition of "differential hop."

We 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.

Q1–Q6: Problems that have been solved

These questions correspond to the concerns in W1–W4 and C1–C2, which we have addressed above with additional experiments and clarifications.

Q7: Release of CMV-ND processed datasets.

We will make these processed datasets publicly available along with our source code in the final release.

Response to Reviewer WHi9

We thank the reviewer for the thoughtful comments and helpful suggestions. Below, we address each point in detail.

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.

We 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.

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).

We apologize for the incorrect citation. We have corrected it to:

Tu, 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).

We have also rechecked the references throughout the manuscript to ensure accuracy in the final version.

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.

We 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.

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.

Thank you for pointing out the typographical and formatting issues. We have carefully reviewed the manuscript and addressed the specific items you mentioned:

• 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.
• The unnecessary period at the end of line 326 has been removed.
• The missing period in the caption of Table 2 has been added to maintain punctuation consistency across all table and figure captions.
• 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.

In 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.

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?

We 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.

We 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.

Response to Reviewer 7mCA

We thank the reviewer for the thoughtful comments and constructive suggestions. Below, we address each concern raised.

W1: Lack of comparison with SAT, ITR, and SVGA.

We 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: (https://anonymous.4open.science/r/icml2025_CMV-ND-2211/sat_itr_svga_results.md)

W2: Similarity to GraphSAGE and novelty concerns.

We respectfully clarify the fundamental differences between CMV-ND and GraphSAGE:

• 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.
• GraphSAGE requires training with learnable aggregation. CMV-ND is a non-parametric, training-free preprocessing strategy.
• GraphSAGE fuses multi-hop signals into a single embedding. CMV-ND preserves non-overlapping differential-hop views for downstream clustering.

For 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 (https://anonymous.4open.science/r/icml2025_CMV-ND-2211/graphsage_node2vec_comparison.md)

W3: Notation inconsistency in equations.

We have carefully reviewed the notations and corrected the inconsistencies. Specifically:

• Equation (1) has been revised to:
  $N_{i+1}(v) = N_i(v) \cup \left( \bigcup_{u \in N_i(v)} N(u) \right)$
• The redundant use of the symbol $a$ in line 246 has been removed.
• Equations (6) and (7) have been revised to:
  • $S_v^{(k)} = S_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} S_u^{(k-1)}$
  • $S_v^{(k)} = S_v^{(0)} + \sum_{t=1}^{k} \sum_{u \in \mathcal{N}(v)} S_u^{(t-1)}$
• The expression in line 243 has been revised to: $\sum_{i=0}^{k} \Delta^i = 1 + \Delta + \Delta^2 + \dots + \Delta^k = \mathcal{O}(\Delta^k)$

We confirm that Equation (4) is correct and does not require modification.

W4: Lack of attention mechanism to weigh hop-level importance.

CMV-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.

W5: Memory complexity concern.

We 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.

W6: Dense formatting of tables.

We 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.

W7: Scalability claim not convincingly demonstrated.

The 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.

W8: Ineffectiveness of t-SNE visualization.

We 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).

Response to Reviewer CDeb

We thank the reviewer for the careful reading and valuable feedback. Below, we address each concern raised.

W1: Lack of discussion on structure learning/search methods.

We 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.

W2: Definitions 1 and 2 are unclear; need example.

We 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.

“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\}.$”

W3: Insufficient discussion on how RNS and NDS contribute to multi-view clustering.

This 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:

“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.”

W4: Lack of analysis on redundancy reduction.

We 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.

W5: Similarity to PageRank-based GNNs.

We clarify that CMV-ND differs from these methods in several key aspects:

• 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.
• 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.
• PageRank-based GNNs require end-to-end training. CMV-ND is a non-parametric, training-free preprocessing strategy.

The 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.

W6: Whether cross-view redundancy, consistency, or conflicts are considered.

We 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.

W7: Lack of detailed experimental settings. Section 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:

• Python 3.9 and PyTorch 1.12.
• Number of propagation hops $K=7$, missing rate = 0.6, FP iterations = 40.
• Default hyperparameters for downstream clustering methods.

Q1–Q6:

These questions correspond to the concerns in W1–W7, and have been addressed above.