acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Progress in Attribute-Missing Graph Clustering: A Benchmark and a Simple Scalable Framework

Abstract

Graph clustering aims to uncover latent communities by jointly exploiting graph structure and node attributes in an unsupervised manner. In real-world applications, however, some nodes may have completely missing attributes due to privacy constraints, data acquisition failures, and cold-start nodes. Missing semantic information makes learning discriminative representations for clustering more challenging. Despite substantial recent efforts on attribute-missing graph clustering, it remains unclear how much genuine progress has been made and how much model complexity is actually needed. Current evaluations are often too narrow to establish generality, while increasingly elaborate pipelines obscure which mechanisms are actually necessary for effective clustering. To systematically revisit these questions, we establish a comprehensive and reproducible benchmark covering 22 graph datasets and 32 baselines from four method families across diverse graph scales. The benchmark reveals that specialized attribute-missing methods can even underperform conventional graph clustering methods. Moreover, we propose VISTA, a lightweight and scalable framework. By performing bounded sparse topology propagation, VISTA recovers missing semantics from locally observed attributes without a learnable imputer. By adopting topology-conditioned cross-view prototype learning, it learns clustering-oriented representations without graph reconstruction or dense node-pair modeling. Extensive experiments demonstrate that VISTA achieves competitive clustering performance, remains robust under high attribute-missing rates, and scales efficiently to large graphs.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Clustering, Attribute-Missing Graphs, Graph Clustering Benchmark;Prototype Learning, Scalable Graph Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Bm67OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper revisits attribute-missing graph clustering through a benchmark covering 22 datasets and 32 baselines. It proposes VISTA, a lightweight framework combining bounded attribute recovery, graph smoothing, and cross-view prototype learning. Extensive experiments demonstrate competitive clustering performance, robustness, and scalability.

Critical strengths
  1. The paper is generally well written and easy to follow, with a clear overall structure.
  2. The experiments are comprehensive, covering different datasets, missing rates, missingness mechanisms, ablations, and computational efficiency.
  3. The supplementary material includes code for VISTA and the baselines, supporting reproducibility and inspection of the experimental settings.
Critical weaknesses
  1. Figure clarity. Some visual details need attention. In particular, the feedback arrows on the right side of Figure 2 have unclear endpoints and directions. Their meaning should be made explicit.
  2. Limited methodological explanation. Section 4 presents the main equations but provides insufficient discussion of the design motivations and connections between stages. A step-by-step algorithm or pseudocode would improve clarity.
  3. Benchmark protocol needs clarification. Section 5.1 uses published configurations or default settings for baselines without specifying comparable tuning budgets and model selection criteria. These details matter for interpreting the central finding that specialized methods do not necessarily outperform conventional alternatives.
Questions for authors

Please see weaknesses.

2 comments

We sincerely thank the reviewer for the positive assessment and the concrete suggestions.

W1. Clarity of Figure 2

Figure 2 now shows every step of the feedback loop explicitly. We redrew the iterative-feedback panel of Figure 2. Every arrow now connects two stages directly, and a labeled Feedback arrow from Refinement back to Imputation closes the imputation–clustering loop. A new sentence in the caption, marked in blue, states what the loop means.

The framework figure now presents VISTA as one connected pipeline. We also redesigned the framework figure (Figure 3). It is now organized into four numbered stages, and each stage is split into sub-modules annotated with their equations. Labeled arrows trace the data flow from the observed attributes to the final clustering, and the parameter-free and trainable parts are marked explicitly.

W2. Design motivation in Section 4 and pseudocode

Section 4 now explains how each stage feeds the next and why it is built this way. We added the design motivation of each stage and the connections between stages to Section 4, and Algorithm 1 to the new Appendix K. All additions are marked in blue.

Each stage supplies what the next one needs. Section 4 now opens with an overview of the four stages. Recovery gives missing nodes attribute evidence without a learnable imputer. Smoothing places observed and recovered nodes in a common neighborhood-aggregated space and supplies the topology source of the second view. Cross-view prototype learning turns the two views into clustering-oriented embeddings, and KMeans partitions their fusion.

Each design choice follows from what the stage needs to provide. Recovery writes each missing row once, so the row stays anchored to the nearest observed evidence, and the bound SS limits how far recovered evidence travels. H\mathbf H and T\mathbf T contain no learnable parameters, so both are precomputed and training involves no graph propagation. At inference the second view is built without dropout, so the fused embedding combines the base evidence of H\mathbf H with the topology-enriched evidence of T\mathbf T.

Algorithm 1 lists the full procedure, from the normalized adjacency and bounded recovery to training and the final KMeans:

Algorithm 1  VISTA
Require: adjacency A; observed attributes X_obs on node set O; clusters K;
  recovery/smoothing steps S, L; dropout rate ρ; topology weight β;
  temperature τ; epochs E
Ensure: cluster assignments ŷ_1, ..., ŷ_N
 1: Â ← D^{-1/2} (A + I) D^{-1/2};  d(i, O) ← BFS distance from O
 2: X^(0) ← X_obs
 3: for s = 1, ..., S do
 4:     X^(s) ← (I − M^(s)) X^(s−1) + M^(s) Â X^(s−1)
 5: end for
 6: X̄ ← X^(S)
 7: H ← Â^L X̄;   T ← Â H
 8: initialize W, b and P
 9: for e = 1, ..., E do
10:     H̃ ← (1 − β) D_ρ(H) + β T
11:     z_i ← W h_i + b,   z̃_i ← W h̃_i + b   for every node i
12:     q_i ← softmax(P z_i / τ),   q̃_i ← softmax(P z̃_i / τ)
13:     update W, b, P with one Adam step on L_VISTA (Eq. 6)
14: end for
15: H̃ ← (1 − β) H + β T
16: Z* ← (Z + Z̃) / 2
17: ŷ ← KMeans(Z*, K)

W3. Benchmark protocol: tuning budget and model selection

The central finding compares baseline families under one protocol, so it does not depend on how any single family is configured. All baselines run their official code with the per-dataset configurations released by their authors, or with default settings when none are released. Iterative baselines use the checkpoint rule of their official code, and all methods share the same missing masks and seeds 41-45. No family receives a larger tuning budget than another. We added this protocol to Section 5.1 of the revised paper.

No baseline is reported in a failed state. When a baseline collapsed on a dataset that its original paper does not cover, we gave it an extended tuning budget and reported its best configuration instead of the collapsed run. This step can only favor the baselines, and the specialized methods still do not outperform the conventional ones.

The finding also holds without model selection. We evaluated every iterative method at the final epoch of its training schedule, with no label-based selection (new Appendix I). The results in Table 1 show that the best attribute-missing method remains below the best conventional and scalable methods, as in the main results.

Table 1. Average final-epoch ACC (%) over the 17 datasets, two representative methods per family.

FamilyMethodACC (%)MethodACC (%)
Attribute-missingMVCG46.58HCN-PAI46.76
ConventionalTHESAURUS49.37CoCo43.24
ScalableSAGSC50.27Dink-Net41.86
Attribute completionPCFI36.58AMER46.43
OursVISTA61.46

We thank the reviewer again and would be glad to clarify anything further.

Reviewer_Bm67OpenReview ↗

Response

Thanks for your comment, I maintain my positive score.

Reviewer_avM9OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3(+1)
Soundness
2(+1)
Read review
Paper summary

This paper studies node clustering in graphs with missing node attributes. It provides a fairly systematic evaluation of existing methods, strengthening the evidence that simple attribute imputation followed by a general-purpose clustering method can be highly effective (Figure 1; Tables 9–10).

The paper also introduces a scalable algorithm, VISTA, which outperforms most competing methods with relatively low computational cost (Table 2; Tables 9–10; Table 6), and finds that its BAR+LS procedure benefits a range of general-purpose methods (Figure 5; Appendix D.1).

Critical strengths
  1. The paper provides systematic support for a conclusion that previously had only partial empirical backing: for node clustering in graphs with missing node attributes, simple attribute imputation followed by a general-purpose method often performs comparably to or better than methods that reconstruct attributes through more elaborate procedures.

  2. The VISTA pipeline offers efficiency advantages across a relatively broad range of the evaluated settings.

Critical weaknesses
  1. Both the findings and the method offer limited novelty, primarily strengthening or more broadly validating existing results. Examples include the effectiveness of simple attribute recovery [1, 2] and of Laplacian smoothing for attribute aggregation: Simple Contrastive Graph Clustering already uses low-pass graph filtering as an independent preprocessing step before MLP-based representation learning [3, Section III-C, Eqs. (3)–(4), and Section IV-E1]. Moreover, the paper's ablation study identifies LS as the largest contributor among the ablated components (Table 4; Appendix B). This makes it difficult to identify substantive new findings that could guide future research and applications; the contribution appears to consist mainly of systematic empirical evidence and a reusable pipeline.

  2. Although the experimental comparisons are extensive, there are potential technical issues. For example, the supplied VISTA training script selects the best evaluation epoch using ground-truth-label-based NMI + ARI (Code reference C1). If this selection procedure was used to generate the reported results, it would introduce evaluation-label leakage into model selection. This further weakens confidence in the claimed broad superiority of the VISTA pipeline.

Questions for authors
  1. An AI-assisted code review identified that the supplied VISTA training script selects the best evaluation epoch using NMI + ARI computed against data.y (Code reference C1). Was this procedure used for the reported results? If so, could you instead select checkpoints using a separate validation set with the use of validation labels explicitly disclosed, or report results at a predetermined training step for each fixed random seed, to provide a fairer assessment of the VISTA pipeline's advantages?

  2. Table 5 and Appendix D compare variants such as FP-CMV-KMeans, FP-CMV-VISTA, and BAR-CMV-VISTA. How much of an advantage does VISTA offer over the original complete CMV-ND-based pipeline, including its downstream clustering learner—for example, the CMV-ND + Dink-Net combination evaluated in [2]? Are there direct comparisons under the same missingness and evaluation protocol?

8 comments

We sincerely thank the reviewer for the detailed comments.

W1. Novelty of the findings and the method

The simplicity of VISTA is the finding itself. The paper asks how much progress attribute-missing graph clustering has actually made and how much model complexity it needs. Our benchmark (22 datasets, 32 baselines, four method families) shows that specialized attribute-missing designs do not reliably outperform conventional graph clustering. VISTA is built to test this directly. It has no learnable imputer, no graph reconstruction and no dense node-pair modeling, yet it achieves results competitive with the strongest methods at a small fraction of their cost.

The value of VISTA does not lie in any single component, such as attribute recovery or low-pass smoothing. We ablate each stage on the 17 datasets. The results in Table 1 show that removing BAR changes the results only marginally, and that clustering the smoothed features directly falls well behind VISTA, while the VISTA learner closes most of that gap. SSGC, which applies a low-pass filter followed by KMeans, also trails VISTA on average in the benchmark (Table 10 of the paper).

Table 1. Ablation of VISTA, macro averages over the 17 datasets (Table 4 of the paper).

VariantACCNMIARI
VISTA w/o BAR70.5853.1149.71
LS + KMeans57.9343.6936.60
LS + VISTA learner69.5852.2748.45
VISTA71.1253.8350.10

VISTA differs from SCGC in both setting and cost. SCGC also filters the features before an MLP, but it targets complete attributes, and its objective matches an N x N cross-view similarity matrix to the adjacency (Eqs. 7-8 of the SCGC paper), so its cost grows quadratically with the number of nodes. The objective of VISTA is linear in N per epoch (Appendix G), and VISTA scales to million-node graphs.

W2 / Q1. Label-based checkpoint selection

The advantage of VISTA holds without checkpoint selection. We added an experiment in which no label information is used to select results (new Appendix I): every iterative method is evaluated directly at the final epoch of its training schedule, without any selection, not even by training loss. The results in Table 1 show that VISTA still achieves the highest ACC on 14 of the 17 datasets, the highest NMI on 16 and the highest ARI on 15. The complete results with NMI, ARI, Macro-F1 and standard deviations are in Table 20 of the revised paper.

Table 1. ACC (%) at the final epoch without label-based selection, mean over seeds 41-45; best in bold, second best in italics.

DatasetMVCGHCN-PAITHESAURUSCoCoDink-NetSAGSCPCFIAMERVISTA
Cora57.9759.6658.1546.6443.2054.7048.0355.5060.50
CiteSeer48.1346.3949.4033.7726.4049.8343.0737.1352.97
DBLP56.3351.5453.9339.3556.0646.0147.9644.8662.35
PubMed48.0261.0737.4443.0147.5868.4561.7654.2166.47
Photo64.8750.0567.6844.1459.3268.2328.9966.8270.67
BlogCatalog35.0734.5133.9127.5928.8135.7532.8128.6249.16
USPS53.4669.7146.4656.4540.2345.0834.7345.4374.88
HHAR34.1049.9541.8437.7933.8655.8730.5865.2463.08
EAT31.7335.4949.0249.1242.1645.2628.7247.7753.38
BAT34.0543.9756.3457.2541.3750.8431.9157.7174.96
CoraFull30.2221.7831.5528.1616.1438.3625.3111.3939.93
Computers54.0937.5143.1432.4939.1931.5624.8941.8652.04
CS56.3560.7358.1760.0556.3864.8530.9859.2468.27
Physics65.6658.0459.8261.8764.1258.1648.2554.5376.83
Wiki27.4822.7541.1937.6732.2739.0928.0826.9446.96
UAT42.0541.4348.3443.3938.6746.5932.4940.1053.23
ACM52.2450.2962.9736.2945.8456.0343.2151.9779.11

The main results follow the standard protocol of deep graph clustering. For each run, the evaluation with the best clustering score against the ground-truth labels is reported. Table 2 shows that the released code of many methods, including several of our baselines, follows this protocol. In our benchmark, the same rule is applied to the iterative baselines that select checkpoints, so VISTA and these baselines are compared under one protocol.

Table 2. What the released code of representative deep graph clustering methods selects with the labels.

MethodVenueWhat the released code selects with the labels
DFCNAAAI 2021epoch with the highest ACC
GDCLIJCAI 2021epoch with the highest ACC
AGCNACM MM 2021maximum of each metric over epochs
DCRNAAAI 2022epoch with the highest ACC
HSANAAAI 2023epoch with the highest ACC
CCGCAAAI 2023epoch with the highest ACC
SCGCIEEE TNNLS 2023epoch with the highest ACC
Dink-NetICML 2023epoch with the highest ACC
CONVERTACM MM 2023epoch with the highest ACC
DGACWWW 2025epoch with the highest ACC
RAGCNeurIPS 2025epoch with the highest ACC
MVCGICASSP 2025KMeans run with the highest ACC
CoCoICLR 2026epoch with the highest ACC
HyperAEICASSP 2026KMeans run with the highest ACC

Q2. Comparison with the complete CMV-ND + Dink-Net pipeline

The advantage of VISTA does not depend on which learner is placed on top of the front-end. We ran CMV-ND and DTRGC as complete pipelines, combining each with four downstream clustering methods, PMAGC, Dink-Net, GGD and SDCN (new Appendix J). As in the two papers, both front-ends operate on the raw attributes and pass their concatenated multi-hop views to the downstream method, which keeps its main-table settings. The results in Table 1 show that VISTA achieves the best results on 16 of the 17 datasets, and no pairing of front-end and downstream learner closes the gap. The complete results are in Table 21 of the revised paper.

Table 1. ACC and NMI (%) of the complete front-end pipelines and VISTA. C: CMV-ND; D: DTRGC.

DatasetMetricC+PMAGCC+Dink-NetC+GGDC+SDCND+PMAGCD+Dink-NetD+GGDD+SDCNVISTA
CoraACC67.6758.6035.0356.5067.1356.8434.3753.8372.70
NMI49.0241.4314.3841.7249.1341.0711.2435.0054.97
CiteSeerACC43.9631.5844.0150.0752.3233.0346.3152.7765.37
NMI20.368.6320.3126.7125.3810.5223.5628.0037.67
DBLPACC64.8852.4447.7974.0765.0952.0146.9865.8178.26
NMI31.9627.267.1240.0833.3524.723.8731.0447.03
PubMedACC56.4847.4760.6965.5060.6254.7868.0065.9570.70
NMI10.257.2819.2924.0015.2713.6528.8425.5032.29
PhotoACC72.7648.1035.6253.9373.8666.7629.1854.2078.61
NMI61.9039.9026.1144.5263.9559.6417.5145.3971.40
BlogCatalogACC46.2144.6934.1134.5645.4046.0731.0436.6362.49
NMI27.0325.0219.6514.7127.1026.3015.4216.0738.02
USPSACC74.9455.6770.0479.2871.0343.2367.1177.3891.81
NMI71.0456.0669.1981.5067.8343.5165.5079.6883.68
HHARACC72.3043.9250.7868.9978.5335.1450.1571.4979.70
NMI68.0248.2155.9173.3471.7337.0552.8270.9774.91
EATACC45.7142.7647.3740.9046.8238.6544.6649.0758.25
NMI23.5716.9424.2110.0225.0213.8121.1724.5934.38
BATACC52.9843.5152.3743.5154.0543.5149.9259.8580.61
NMI35.0718.5531.8814.5535.7323.2030.2035.0856.77
CoraFullACC38.1036.9517.1732.1539.5037.1115.2226.0342.42
NMI52.6052.0227.3647.3853.0451.8923.5041.6854.48
ComputersACC55.4034.7833.1450.0057.3440.1036.6550.8164.02
NMI45.991.5518.9227.9951.346.2027.3630.3554.07
CSACC66.8467.2148.8168.5368.9262.2748.6764.0381.54
NMI67.7869.5745.7065.6370.2466.0444.8365.6975.34
PhysicsACC64.6763.2638.0083.0063.5561.0148.7585.7492.31
NMI58.7458.4030.3863.2359.2259.4232.7365.9476.06
WikiACC29.5726.3731.9936.8337.2633.4634.3541.5952.68
NMI22.8017.5928.3628.5331.3229.7634.5035.7747.22
UATACC57.1443.7144.9744.5557.1946.9148.2740.9654.69
NMI26.1412.5818.1913.2425.9419.2020.689.7125.92
ACMACC57.1037.4237.5152.5970.5460.3558.2558.9082.84
NMI24.141.111.2922.8834.8927.8338.4229.7650.84
AverageACC56.8745.7942.9155.0059.3647.7244.5856.1871.12
NMI40.9729.5426.9637.6543.5632.5828.9539.4253.83

We thank the reviewer again and would be glad to clarify anything further.

Reviewer_xaZPOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper systematically investigates attribute-missing graph clustering methods, and it develops a simple and scalable but effective framework. The proposed VISTA introduces feature propagation for missing attributes and employs a simple Laplacian smoothing operation with a two-view consistency module to achieve superior performance. The work compares the work with a wide range of methods and demosntrate its effectiveness.

Critical strengths
  1. The paper systematically investigates attribute-missing graph clustering methods, and it develops a simple and scalable but effective framework.

  2. The work compares the work with a wide range of methods on several datasets.

Critical weaknesses
  1. Leveraging feature propagation for feature imputation is not a novel idea, which has been proposed by the paper "On the Unreasonable Effectiveness of Feature Propagation". Though the paper is significant, the method design lacks novelty. The effectiveness of aplacian smoothing and cross-view alignment has also been validated by several works.

  2. Though the work achieves superior performance, its application might be limited. To be specific, both the feature propagation and Laplacian smoothing rely on the homophily assumption and might not be suitable for heterophilic graphs. This work also lacks experimental evaluation on heterophilic datasets.

  3. A main problem of the work is that it lacks careful design for clustering. All the components are designed for feature imputation but does not consider the clustering tasks. Employing GNN or cross-view alignment cannot ensure the model output is with clear clustering structure. If the clustering structure is not clear, the following clustering will be greatly affected. Of course, the effectiveness is validated by a number of experiments, but what is the potentail reasons explaining it?

  4. It is significant that the authors employ a simple and scalable framework that achieves superior performance. However, the work does not provide a sound theoretical analysis about it.

Questions for authors

Refer to the weaknesses.

4 comments

We sincerely thank the reviewer for the constructive comments.

W1. Novelty: feature propagation, Laplacian smoothing and cross-view alignment

The simplicity of VISTA is intended. The work cited by the reviewer, On the Unreasonable Effectiveness of Feature Propagation (Rossi et al., 2022), is valuable precisely because it showed that a simple, parameter-free propagation matches far more elaborate methods for node classification with missing features. SGC (Wu et al., 2019) made the same point for graph convolution. We establish this for attribute-missing graph clustering, where methods have moved toward learnable imputers, graph reconstruction and dense node-pair modeling. VISTA therefore builds on established operations by design, and the paper cites them as such.

Specialized attribute-missing methods do not reliably outperform conventional graph clustering. We benchmark 32 baselines from four method families on 22 datasets under one protocol. Figure 1 and Tables 8-11 of the paper show that specialized methods lead on only 7 of the 17 comparable datasets. This finding is new to the field, and it motivates a simple design.

The performance of VISTA comes from how its components are combined, not from any single component. We compare each component on its own with the same component inside VISTA. The results in Table 1 show that neither recovery nor smoothing alone accounts for the performance, and that VISTA performs cross-view alignment at linear cost.

Table 1. Each component on its own versus within VISTA. Each row compares two settings under the same protocol (average ACC, %).

ComponentOn its ownWith VISTASource
RecoveryFP + KMeans: 41.81FP + VISTA learner: 58.84Table 5
Recovery front-endBest CMV-ND / DTRGC pipeline: 59.36VISTA: 71.12Appendix J
SmoothingLS + KMeans: 57.93VISTA: 71.12Table 4
Cross-view alignmentSCGC, HSAN: N x N similarity, O(N²)Node-to-prototype, O(N), 2.4M-node ProductsAppendix G

The contribution is therefore a benchmark that recalibrates the progress of the field and a simple, scalable method for attribute-missing graph clustering.

W4. Theoretical analysis

Every stage of VISTA before training is a fixed sparse operator, so its behavior can be analyzed directly. We added this analysis to the revised paper (new Appendix N), with full proofs.

Recovery uses only the nearest observed evidence. Let O\mathcal O be the observed nodes and s=d(i,O)≤Ss=d(i,\mathcal O)\le S for a missing node ii.

Proposition 1. xˉi=∑j∈Oicijxj\bar{\mathbf x}_ i=\sum_ {j\in\mathcal O_ i} c_ {ij}\mathbf x_ j with cij>0c_ {ij}>0, where Oi={j∈O:dist⁡(i,j)=s}\mathcal O_ i=\lbrace j\in\mathcal O:\operatorname{dist}(i,j)=s\rbrace is the set of nearest observed nodes of ii, and cijc_{ij} sums the products of A^\hat A along the shortest paths from ii to jj.

Proof sketch. By Eq. 1, row ii is written once, at step ss, as ∑kA^ikxk(s−1)\sum_ k \hat A_ {ik}\mathbf x^{(s-1)}_ k. The only nonzero rows among its neighbors belong to nodes with d(k,O)=s−1d(k,\mathcal O)=s-1. By induction, each of them is a nonnegative combination of observed rows at distance s−1s-1 from kk, which are at distance exactly ss from ii.

Corollary. If xj=μyj+ϵj\mathbf x_ j=\boldsymbol\mu_ {y_ j}+\boldsymbol\epsilon_ j and πi\pi_ i is the weight share of same-class nodes in Oi\mathcal O_ i, then up to a positive scale ∥xˉi−μyi∥≤(1−πi)max⁡c∥μc−μyi∥+max⁡j∥ϵj∥\Vert\bar{\mathbf x}_ i-\boldsymbol\mu_ {y_ i}\Vert\le(1-\pi_ i)\max_ c\Vert\boldsymbol\mu_ c-\boldsymbol\mu_ {y_ i}\Vert+\max_ j\Vert\boldsymbol\epsilon_ j\Vert. Recovery error is therefore governed by the class purity of the nearest observed nodes, not by global homophily. This also separates BAR from FP. FP iterates to the fixed point that minimizes the Dirichlet energy with observed rows clamped (Rossi et al., 2022), so observed nodes far beyond the nearest ones also enter each recovered row.

Smoothing increases class separation. Laplacian smoothing is a low-pass filter (Wu et al., 2019; NT and Maehara, 2019). Under the contextual stochastic block model, graph convolution provably enlarges the regime in which classes are linearly separable when intra-class edges dominate (Baranwal et al., 2021). This explains the large gain from smoothing in the ablation (Table 4) and the stage-wise analysis (W3).

W2. Homophily assumption and heterophilic graphs

VISTA does not require a homophilic graph, and our benchmark already contains heterophilic graphs. We added the edge homophily h, the fraction of edges whose endpoints share a class, to Table 7 of the revised paper. The results in Table 1 show that eight datasets have h below 0.7, and on four of them most edges connect nodes of different classes.

Table 1. Statistics and edge homophily h of the 22 benchmark datasets.

DatasetNodesEdgesDim.Classesh
Cora2,70810,5561,43370.81
CiteSeer3,3279,1043,70360.74
DBLP17,716105,7341,63940.83
PubMed19,71788,64850030.80
Photo7,650238,16274580.83
Flickr89,250899,75650070.32
BlogCatalog5,196343,4868,18960.40
USPS9,29827,894256100.96
HHAR10,29930,89756160.94
EAT39911,98820340.41
BAT1312,0778140.43
CoraFull19,793126,8428,710700.57
Computers13,752491,722767100.78
CS18,333163,7886,805150.81
Physics34,493495,9248,41550.93
Wiki2,40517,9814,973170.61
UAT1,19027,19823940.70
ACM3,02526,2561,87030.82
TwitchGamers168,11413,595,114720.55
Arxiv169,3432,315,598128400.65
Reddit232,965114,615,892602410.76
Products2,449,029123,718,152100470.81

VISTA remains the strongest method on strongly heterophilic graphs. We added six graphs with h from 0.05 to 0.23 in the new Appendix M (Table 2). The results in Tables 3 and 4 show that VISTA achieves the highest average ACC and NMI, and the complete results in Table 24 of the revised paper show the same for all four metrics. VISTA therefore remains effective when homophily is low.

Table 2. Statistics of the six added heterophilic graphs.

DatasetNodesEdgesDim.ClassesMajority class (%)h
Roman-empire22,66232,9273001814.00.05
Texas1832791,703555.20.06
Cornell1832771,703544.80.12
Wisconsin2514501,703547.00.18
Squirrel5,201198,3532,089520.00.22
Chameleon2,27731,3712,325522.90.23

Table 3. ACC (%) on the six heterophilic graphs; best in bold, second best in italics.

DatasethPMAGCAMMGCCoCoS3GCDink-NetPCFISVGAVISTA
Roman-empire0.0513.9613.2618.8013.1715.3817.6920.6323.29
Texas0.0641.7540.0038.4738.5836.7241.9742.0846.89
Cornell0.1235.1935.6338.1432.1331.1537.7037.7039.56
Wisconsin0.1835.9334.5835.8631.1629.8037.1341.5945.66
Squirrel0.2226.5529.3526.9024.3925.5724.3827.0333.09
Chameleon0.2333.1736.6034.7732.7431.2427.3129.9037.50
Average31.0931.5732.1628.7028.3131.0333.1637.66

Table 4. NMI (%) on the six heterophilic graphs; best in bold, second best in italics.

DatasethPMAGCAMMGCCoCoS3GCDink-NetPCFISVGAVISTA
Roman-empire0.054.952.5910.014.136.998.6818.5217.49
Texas0.067.598.4010.467.816.006.5817.7721.31
Cornell0.1210.059.7712.667.776.256.4212.7914.21
Wisconsin0.1810.3410.4611.576.334.927.1019.0124.12
Squirrel0.222.434.352.880.752.292.143.836.92
Chameleon0.238.559.779.658.368.035.076.4110.26
Average7.327.569.545.865.756.0013.0515.72

W3. Clustering-specific design and why it works

The clustering structure of VISTA is formed by its clustering-oriented stages, not by attribute recovery. We added a stage-wise analysis (new Appendix L): the representation after each stage, X̄, H and Z*, is clustered with the same KMeans on the 17 datasets, together with two label-free measures, the cosine silhouette (Sil.) and the Davies-Bouldin index (DBI). The results in Table 1 show that from X̄ to Z* all six measures improve on 17/17 datasets, and that prototype learning brings the largest gain: from H to Z*, ACC and Macro-F1 improve on 17/17 and NMI and ARI on 16/17.

Table 1. Stage-wise clustering quality (Table 22 of the revised paper).

DatasetRep.ACCNMIARIF1Sil. ↑DBI ↓
CoraX̄37.2817.0511.0536.980.1228.574
H63.4947.8640.3160.650.1593.330
Z*72.7054.9750.9870.230.1793.015
CiteSeerX̄53.3726.3524.3449.270.0217.284
H57.8732.2730.8652.240.0594.870
Z*65.3737.6739.6960.220.1083.178
DBLPX̄39.937.242.4234.320.1065.507
H62.8035.8636.6155.940.2042.674
Z*78.2647.0352.0673.950.1832.918
PubMedX̄54.0215.8313.0853.760.0385.130
H70.6632.5133.1869.860.4861.382
Z*70.7032.2933.1069.860.4591.467
PhotoX̄62.8251.9139.2560.150.0024.316
H69.3663.0350.5960.530.2271.586
Z*78.6171.4061.4773.560.2961.524
BlogCatalogX̄28.8613.424.9128.040.2024.047
H55.6629.8628.1853.640.1193.326
Z*62.4938.0233.1960.100.2222.381
USPSX̄55.1949.8533.9353.890.1922.293
H78.1880.6674.1175.380.7080.750
Z*91.8183.6884.4291.130.7350.721
HHARX̄55.7753.7139.6153.840.0972.114
H59.2466.6249.8253.450.5760.941
Z*79.7074.9166.3278.910.5021.252
EATX̄38.908.216.4536.560.0734.162
H29.024.320.4818.990.8820.416
Z*58.2534.3827.8358.420.6260.614
BATX̄41.6812.738.5640.900.1123.074
H39.0811.527.4433.050.5970.599
Z*80.6156.7755.7680.650.6740.634
CoraFullX̄32.6444.5519.2427.390.0804.183
H39.7654.0528.0431.940.2342.293
Z*42.4254.4829.4733.620.2641.957
ComputersX̄34.5326.7014.0221.16-0.0494.783
H54.2148.6135.4440.620.2941.759
Z*64.0254.0745.0753.620.3721.642
CSX̄52.1155.6433.4949.070.1522.963
H62.9168.7453.3754.520.3112.084
Z*81.5475.3476.5274.360.4451.559
PhysicsX̄48.2436.1921.8445.610.1293.798
H74.1564.2562.0365.390.5641.178
Z*92.3176.0685.3289.370.7130.915
WikiX̄41.4037.6421.0734.730.1153.677
H48.3243.6127.1838.360.2142.550
Z*52.6847.2231.1142.970.2352.527
UATX̄43.3111.7711.0039.270.1123.748
H38.349.376.0130.760.6951.077
Z*54.6925.9224.0352.560.3800.920
ACMX̄78.9245.3446.5179.150.0198.352
H80.5648.1650.3680.680.0475.532
Z*82.8450.8455.3282.690.0945.119
AverageX̄47.0030.2420.6343.770.0904.589
H57.8643.6136.1251.530.3752.138
Z*71.1253.8350.1067.420.3821.903

The prototype objective turns smoothed evidence into class-consistent clusters. On EAT, BAT and UAT, smoothing alone yields very compact clusters with a lower ACC than X̄, and prototype learning restores the class structure. The prototype objective (Eq. 6) requires each node to keep the same affinities to K shared prototypes under feature and neighborhood perturbations, which places nodes with consistent evidence close together.

We thank the reviewer again and would be glad to clarify anything further.

Dear Reviewer xaZP,

Thank you again for your valuable comments. We have responded to each point and revised the paper accordingly: the positioning of VISTA's simplicity (W1), results on heterophilic graphs (W2, Appendix M), the stage-wise analysis of the clustering-specific design (W3, Appendix L), and the theoretical analysis (W4, Appendix N).

We would be grateful to know whether our responses address your concerns, or whether you have any new concerns after reading them. We would be glad to discuss them in the remaining time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.