{"id":"b1002709-b443-4775-85ca-963d8c823d28","arxiv_id":"2507.13368","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"CMV-ND builds one feature view per exact hop distance and then runs existing clustering methods on those views, improving attribute-missing large-scale graph clustering in experiments.","lead":"The paper proposes a preprocessing recipe, CMV-ND, that turns each node's neighborhood into several 'views' based on how many hops away neighbors are, then feeds these views to existing graph or multi-view clustering algorithms. On six graphs with 60% of node features deleted, the preprocessed versions usually cluster better, especially on graphs too large for full-batch methods.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper never specifies whether downstream DGC methods receive the original adjacency alongside the fused CMV-ND views, so the central no-propagation claim and the Table 1 improvements are under-specified.","rationale":"The reader's CONDITIONAL verdict is appropriate, and the reader did flag the unspecified downstream DGC integration as a secondary premise. However, I regard this ambiguity as the single most load-bearing issue rather than the FP imputation quality: the paper's central conceptual claim is that CMV-ND constitutes a new propagation-free paradigm for large-scale attribute-missing graph clustering, and that claim cannot be evaluated until the paper states whether the original adjacency is supplied to the downstream GNN-based DGC methods. The empirical gains in Table 1 might survive clarification, so rejection is not warranted on this basis alone; the correct disposition is to require the authors to specify and verify the exact input pipeline, ideally with code. The memory-complexity concern (O(n) vs. O(K N d)) is real but secondary, since it affects the scalability narrative rather than the validity of the clustering comparisons. I therefore keep the reader's CONDITIONAL verdict unchanged.","tokens_in":26091,"tokens_out":6699,"duration_ms":69633,"concrete_test":"Obtain or reconstruct the implementation and run three configurations on Cora and Reddit at 60% missing attributes with K=7: (a) Dink-Net with original features and original adjacency, reproducing the w/o row; (b) Dink-Net with h_fuse and original adjacency; (c) Dink-Net with h_fuse and identity adjacency, so no message passing occurs. If ACC and NMI of (b) are close to (c), then downstream propagation is not contributing and the no-propagation claim is consistent, but the comparison against (a) is not a controlled test of the same DGC method because the with-CMV-ND variant no longer uses graph structure. If (b) clearly exceeds (c), then propagation remains essential downstream and the no-propagation claim is false. Report ACC and NMI for all three configurations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"CMV-ND is presented as a DGC method that does not leverage graph structure through propagation operations (Sec. 1, Conclusion), yet Section 4.2 combines it with Dink-Net, S3GC, DGI, and other GNN-based methods whose encoders require an adjacency matrix. Appendix B only states that the concatenated feature h_fuse_v can be directly used as input for DGC (Eq. 9) and never says whether the original edge set is also passed to the downstream model. If the original adjacency A is passed, then CMV-ND is a feature-augmentation preprocessing layer and the no-propagation/no-sampling claims are false. If A is withheld, the with-CMV-ND rows are not the same DGC methods as the without-CMV-ND rows, so the comparison is confounded by the availability of graph topology. Either way, the abstract's strongest claim that CMV-ND preprocesses structural information into multiple views and improves performance without propagation is not well defined. This ambiguity directly affects the headline results in Table 1, such as Dink-Net plus CMV-ND reaching ACC 72.54 on Cora and 69.31 on Reddit, because those numbers could be driven by the fused features, by the original adjacency, or by an unstated combination of both.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CMV-ND, a preprocessing paradigm for deep graph clustering on large attribute-missing graphs. For each node, CMV-ND performs a recursive neighborhood search to identify exact-hop shells (differential neighborhoods), mean-pools node features within each shell, and stacks these K+1 views together with the node's original features. The views can either be concatenated into a fused feature vector for a downstream DGC method or fed directly to multi-view clustering (MVC) methods. Experiments on six datasets at a 60% missing rate, after FP imputation, report consistent ACC/NMI/ARI/F1 improvements over DGC baselines and show that K-means on the fused features outperforms most DGC baselines. Appendix D.3 provides a control experiment with propagation-based views, and Appendix D.1 reports gains on three additional attribute-missing baselines.","tokens_in":26354,"tokens_out":7738,"duration_ms":92412,"significance":"If the reported gains hold, the core idea is simple and practically useful: it converts graph structure into view features, allowing methods that either ignore topology or cannot scale to large graphs to benefit from structural signals under attribute missingness. The paper also bridges DGC and MVC, and the plug-and-play design means the contribution could be adopted by many existing pipelines. Credit is due for the breadth of the empirical evaluation (six datasets, four metrics, ten runs), the appendices with additional baselines and propagation-view controls, and the fact that the only hand-set hyperparameter K is fixed after sensitivity analysis rather than tuned per dataset. The significance is tempered, however, by ambiguity about the experimental protocol, apparent inconsistencies in the complexity analysis, and a few suspicious duplicated numbers that call for verification.","major_comments":[{"comment":"The paper never states whether downstream DGC methods receive the original adjacency matrix alongside the fused CMV-ND features. Appendix B only says that h_fuse_v (Eq. 9) can be directly used as input for DGC. This ambiguity makes the central no-propagation claim and the Table 1 comparisons under-specified: if the original adjacency A is also passed, the overall pipeline still uses GNN propagation and the 'without propagation' claim is false; if A is withheld, the with-CMV-ND rows are not the same DGC methods as the without-CMV-ND rows, confounding the comparison by the availability of graph topology. Please specify the exact inputs to each downstream method and re-frame the claims accordingly.","section":"Appendix B / Section 4.2"},{"comment":"The abstract's claim that CMV-ND preserves structural information 'in a complete but non-redundant manner' is too strong for the actual construction. Eq. (3) collapses every node in D^k(v) to a single mean vector, discarding intra-shell structure such as node identities, degrees, and pairwise connections. What is complete is the coverage of hop shells, not the structural information itself. Please either define 'completeness' formally as shell coverage or soften the claim to avoid overstating what the view representation encodes.","section":"Section 3.3.3, Eq. (3)"},{"comment":"The memory complexity claim of O(n) is inconsistent with the actual output of CMV-ND. Equation (5) stores a tensor H of size (K+1) x N x d, which is Θ(KNd) memory. For Reddit (N=232,965, d=602, K=7), this is approximately 4.5 GB in float32, yet Table 3 reports a CPU memory cost of only 446.64 MB. Please clarify what is being measured (e.g., peak incremental memory vs. total storage), correct the asymptotic memory analysis, and reconcile the reported numbers with the tensor dimensions.","section":"Section 3.4.2 / Table 3"},{"comment":"The time complexity analysis O(nΔ^k) understates the practical cost of per-node BFS on the large datasets. In a graph like Reddit or ogbn-products, a 7-hop BFS from a high-degree node can cover a large fraction of the graph, making the per-source cost Θ(N+E) and the total cost superlinear/quadratic in N. The reported preprocessing times (189 s for Reddit, 274 s for ogbn-products) are difficult to reconcile with an interpreted per-node BFS implementation. Please describe the actual implementation (e.g., global visited sets, early stopping, C++/numba acceleration) and report scaling behavior with N or with K.","section":"Section 3.4.1 / Algorithm 1 / Table 3"},{"comment":"The CiteSeer MVGRL row in Table 1 reports exactly identical values with and without CMV-ND (ACC 57.20, NMI 34.12, ARI 27.62, F1 53.85), and the same four values also appear for DIMVC in Table 2. Since CMV-ND changes the input features, identical results across different inputs cannot arise by chance and indicate a reporting error. Please verify these entries and correct any transcription mistakes, as these values directly affect the claim that CMV-ND never hurts performance.","section":"Table 1 / Table 2"}],"minor_comments":[{"comment":"Equation (3) divides by n_v^k, which is undefined when a node has no k-hop neighbors (e.g., disconnected components or k=0). The pseudocode in Appendix F uses a zero vector for empty shells; this should be stated explicitly in the main text.","section":"Section 3.3.3, Eq. (3)"},{"comment":"The notation Δ is defined as the maximum degree in Table 4 but as the average degree in Section 3.4. Please use a consistent definition, since the complexity expression O(nΔ^k) is sensitive to this distinction.","section":"Section 3.4 / Table 4"},{"comment":"The hyperparameter analysis in Section 4.3 references Figure 3, but the figure is not included in the submitted text. Please include the plot with labeled axes and a clear description of which metric (ACC or F1) is shown.","section":"Section 4.3 / Figure 3"},{"comment":"The caption of Table 7 says 'attribute-missing graphs,' but the table reports experiments on attribute-complete graphs (Q4). Please correct the caption.","section":"Table 7 caption"},{"comment":"The baseline 'FP' is cited as (Park et al., 2022), but the listed Park et al. 2022 reference appears to be the CGC contrastive clustering paper, not a feature-propagation method. Please verify and correct the citation for the feature propagation baseline.","section":"References"},{"comment":"The heading 'Relate Work' should be 'Related Work'.","section":"Section 2 heading"}],"recommendation":"major_revision","confidential_remarks":"The contribution is modest but plausibly useful as a preprocessing layer. The main risks are not circularity—no parameters are fit to test labels—but under-specification of the experimental protocol (whether adjacency is passed downstream), inconsistencies in the complexity/memory analysis, and a few suspicious duplicated table entries. These are fixable in revision. I would not recommend rejection at this stage, but the authors need to clarify the protocol and verify the reported numbers before the claims can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the empirical core of this paper — that exact-hop neighborhood mean features, concatenated as extra views, give a cheap and consistent boost to clustering on 60% attribute-missing graphs — looks real and useful. The packaging around it is overpromised. I'd send it to review, but the authors owe some clarifications.\n\nWhat's actually new: combining differential (exact-hop) neighborhoods with mean feature aggregation as a model-agnostic preprocessing for the large-scale-plus-missing-attributes setting. The ingredients are standard, but the specific combination and the evaluation are new. The paper does a few things well: it tests across six datasets including two OGB-scale graphs; it checks sensitivity to K; and it runs a control experiment (Appendix D.3) showing propagation-based multi-hop views also help but less. That control gives some confidence the differential-hop construction is doing real work rather than just adding multi-scale features. K is fixed after sensitivity analysis, not tuned to test labels, and no parameters are fitted to ground truth. That is honest.\n\nSoft spots, in rough order of real significance:\n\n1. The 'complete but non-redundant' claim does not survive contact with the method. Mean pooling at each hop discards most structural detail, and K=7 truncates. Non-overlapping node sets is not the same as non-redundant information, since the same cluster signal can recur in different views. Advise softening this in the abstract.\n\n2. The memory complexity statement, O(n), ignores the output: a (K+1) x N x d tensor. That is O(Knd). The numbers reported in Table 3 are fine, but the asymptotic claim is wrong.\n\n3. The no-propagation claim is under-specified. CMV-ND itself does not propagate, but the downstream DGC methods in Table 1 are GNNs that need an adjacency. The paper never says whether the original edge set is also passed. I suspect it is, and that the comparison is fair — same adjacency on both sides — but then the 'without propagation' framing applies only to the preprocessing step, and should be said explicitly. If the adjacency is withheld, the comparison would be confounded. That ambiguity needs one clarifying sentence.\n\n4. 'No negative impact under any circumstance' is too strong: Appendix D.2, on complete graphs, shows small drops for several methods (e.g., DGI on Cora ACC 72.61 → 71.69). Limit the claim to the missing-attribute setting.\n\n5. No code release. For a preprocessing method, code is the deliverable; without it, the precise protocol — how the fused features are fed to each baseline, whether FP features are imputed before or after hop aggregation — remains unclear.\n\nThe redundancy-ratio derivation in Sec 3.3.4 is decorative; I would not lean on it. The citations look fine, and self-citation overlaps with the authors' own prior work are not inflated.\n\nWho it's for: practitioners working on attribute-missing graph clustering who want a cheap plug-in, and researchers studying when multi-scale structural features help. It deserves a serious referee. My recommendation: accept the approach, require the above clarifications and the code, and cut the overclaims.","headline":"Useful and believable preprocessing result, but the paper's completeness, memory, and no-propagation claims overreach; worth a serious referee with revisions.","tokens_in":26860,"tokens_out":3867,"would_cite":true,"duration_ms":42635,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"On large attribute-missing graphs, storing exact-hop neighborhood shells as non-overlapping views lets existing clustering methods perform best or near-best at a 60% missing rate.","keywords":["deep graph clustering","attribute-missing graphs","multi-view clustering","neighborhood differentiation","feature propagation","large-scale graphs","graph preprocessing","unsupervised learning"],"falsifier":"Take a large graph whose edges deliberately violate homophily, or construct one by rewiring Cora or Amazon-Photo to connect nodes from different classes, mask 60% of features, run feature propagation, and compare Dink-Net with and without CMV-ND; the paper's claim predicts CMV-ND still improves accuracy, whereas the homophily-dependent consistency argument would predict the gain shrinks or reverses.","tokens_in":25911,"feed_emoji":"🕸️","tokens_out":6690,"duration_ms":70792,"temperature":0.7,"pith_summary":"Large real-world graphs often arrive with many node attributes missing, and deep graph clustering methods either assume complete features or run out of memory when the graph is too big. This paper claims that the real problem is not the missing numbers but how graph structure is used: message passing rereads the same neighbors at every layer, and sampling for scalability destroys topology. CMV-ND is a preprocessing recipe that replaces both with K+1 complementary views: the node's own features plus the averaged features of nodes at exactly one, two, and up to K hops away, with shells that never overlap. Any existing clustering method can take these views as input, and the paper shows that combining CMV-ND with Dink-Net yields the best or near-best accuracy on six standard graphs at a 60% missing rate, including graphs where the previous attribute-missing specialist cannot run. Because the views are built once and stored, the approach scales to millions of nodes without sampling or propagation.","feed_headline":"Exact-hop shells carry clustering when 60% of features are missing","feed_subtitle":"Turns graph structure into non-overlapping hop views, letting existing clustering methods run accurately when 60% of features are missing.","key_machinery":"The load-bearing object is the k-differential hop neighborhood, D^k(v)=N^k(v)\\$N^{{k-1}}$(v), the set of nodes whose shortest-path distance from v is exactly k. The method computes these shells by recursive neighborhood search, a breadth-first expansion bounded by K, and then forms view k as the mean feature vector of the nodes in D^k(v); view 0 is the target node's own feature vector. The construction isolates each layer of structure so that no node appears in more than one view, which is the mechanism behind the paper's redundancy argument and the claim that the K+1 views are complete but non-redundant.","core_discovery":"The paper's central claim is that a graph's structural information can be preserved completely and without redundancy by partitioning each node's neighborhood into exact-hop shells. For each node v it defines the k-differential hop neighborhood D^k(v)=N^k(v)\\$N^{{k-1}}$(v), the nodes at distance exactly k, and represents that shell by the mean feature vector of its members. Stacking these K shell means with the node's own feature vector gives K+1 views. Since recursive neighborhood search finds each node once and the differential rule removes overlaps, the views are complete and non-redundant, and any downstream deep graph clustering or multi-view clustering method can consume them. The empirical assertion is that this preprocessing significantly improves clustering on attribute-missing graphs: paired with Dink-Net, CMV-ND achieves the best or near-best ACC, NMI, ARI, and F1 across Cora, CiteSeer, Amazon-Photo, Reddit, ogbn-arXiv, and ogbn-products at a 60% missing rate, without hurting any tested method on any dataset.","pith_inferences":["Beyond the paper, if the benefit comes from explicit structure rather than propagation, the same preprocessing should carry over to other unsupervised node tasks, such as community detection or unsupervised node ranking, on attribute-missing graphs; the paper does not test these.","On non-homophilous graphs the mean-over-shell view may smear clusters, so a useful stress test is to apply CMV-ND to datasets whose edges connect unlike classes and measure whether the Dink-Net gain disappears.","The frozen mean pooling over each shell is a simple choice; weighting nodes inside a shell or learning a per-hop fusion could plausibly improve on the reported numbers, since the paper only concatenates or directly feeds the views."],"forward_implications":["Any existing deep graph clustering method can be upgraded by CMV-ND preprocessing alone, without retraining or modifying its loss, and in the paper's experiments the upgrade never reduces performance on any dataset.","At a 60% missing rate, CMV-ND plus Dink-Net completes runs on Reddit, ogbn-arXiv, and ogbn-products, where the previous state-of-the-art attribute-missing method exhausts a 24 GB GPU.","Because the views are built once and stored, the preprocessing cost is one-time and CPU-only, with memory linear in the number of nodes.","The same K+1 views can be fed to multi-view clustering algorithms, so the paradigm turns a graph-clustering problem into a multi-view clustering problem.","Simply concatenating the views and running K-means outperforms most existing deep graph clustering baselines, indicating that the structure stored in the shells carries most of the clustering signal."],"supporting_citations":[{"why":"Dink-Net, the scalable deep graph clustering backbone that CMV-ND is paired with and that produces the paper's headline results.","marker":"Liu et al., 2023b"},{"why":"AMGC, the attribute-missing graph clustering baseline whose 0.6 missing-rate setting the experiments adopt and which runs out of memory on large graphs.","marker":"Tu et al., 2024a"},{"why":"Feature propagation, the imputation preprocessing applied to all methods before clustering under missing attributes.","marker":"Park et al., 2022"},{"why":"S3GC, the prior scalable deep graph clustering baseline that CMV-ND must beat on large graphs.","marker":"Devvrit et al., 2022"},{"why":"DIMVC, a multi-view clustering method used to show that CMV-ND's views transfer to multi-view clustering algorithms.","marker":"Xu et al., 2022a"}],"fun_headline_variants":["Hop-shell views keep clustering alive at 60% missing features","Exact-hop neighborhoods rescue graph clustering from missing data","Non-redundant hop views handle 60% feature loss in graphs","Differentiating neighborhoods makes clustering robust to missing attributes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The approach assumes the features that fill the missing attributes, delivered by feature propagation before any clustering runs, are accurate enough that averaging them within a hop shell still encodes cluster identity; if imputation is noisy or the graph is not homophilous, the shell averages may add blur instead of structure.","fun_headline_variants_meta":{"raw":{"variants":["Hop-shell views keep clustering alive at 60% missing features","Exact-hop neighborhoods rescue graph clustering from missing data","Non-redundant hop views handle 60% feature loss in graphs","Differentiating neighborhoods makes clustering robust to missing attributes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000249,"raw_usage":{"total_tokens":1584,"prompt_tokens":1010,"completion_tokens":574,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":505}},"tokens_in":626,"tokens_out":574,"duration_ms":6773,"temperature":1.0,"reasoning_tokens":505,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:52:57.020031+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a large graph whose edges deliberately violate homophily, or construct one by rewiring Cora or Amazon-Photo to connect nodes from different classes, mask 60% of features, run feature propagation, and compare Dink-Net with and without CMV-ND; the paper's claim predicts CMV-ND still improves accuracy, whereas the homophily-dependent consistency argument would predict the gain shrinks or reverses.","supporting_citations":[{"cited_title":"A., Kim, S., Du, F., Ahmed, N., and Faloutsos, C","cited_arxiv_id":null,"evidence_quote":"Feature propagation, the imputation preprocessing applied to all methods before clustering under missing attributes."},{"cited_title":"S3gc: scalable self-supervised graph clustering","cited_arxiv_id":null,"evidence_quote":"S3GC, the prior scalable deep graph clustering baseline that CMV-ND must beat on large graphs."}],"review_version":1}