{"id":"0d641099-3124-408f-ae8c-dc371313cb96","arxiv_id":"2505.05533","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A hop-ordering contrastive loss for graphs outperforms existing self-supervised baselines on node classification, but the accompanying random-walk proof of universal label-consistency decay is misaligned with the empirical measure.","lead":"Graph self-supervised learning usually asks whether two augmented views of the same graph are similar. This paper instead ranks neighbors by hop distance, claiming labels consistently fade with distance and that preserving this ordering beats 20 prior methods; however, the random-walk proof offered for the fade does not match the measured quantity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The §2.2 random-walk theory governs LC_prob, a degree-weighted walk-return probability with self-loops, not LC_emp from Eq. 1; convergence to a stationary value does not prove the claimed decay, and the heterophily model can predict upward convergence.","rationale":"The reader's weakest assumption identifies the same central flaw: the theoretical object LC_prob is not the empirical label consistency LC_emp, and convergence to a stationary distribution is not decay. My stress test confirms and sharpens this: even under the paper's own two-label heterophily approximation, LC_prob can converge upward from k=1, so Theorem 1 and Corollary 1 cannot be the stated theoretical guarantees for the observed 'oscillatory decay.' The empirical benchmark results are plausible and the method may be practically useful, but the central claim that random walk theory justifies the universal relative-similarity pattern is broken. This does not move the reader's REJECT verdict; it strengthens the same basis for it.","tokens_in":23627,"tokens_out":5435,"duration_ms":61685,"concrete_test":"On all 11 graphs used in Figure 2, compute two curves for k=1..5: (a) LC_emp(k) from Eq. (1) using exact shortest-path neighborhoods; (b) LC_prob(k)=(T^k)_{ii} with T defined by Eq. (16), both with and without self-loops on the adjacency. Report whether LC_prob(k) reproduces LC_emp(k), whether LC_prob(k) is nonincreasing from k=1, and whether LC_prob(1)>π_i on Chameleon, Squirrel, and Actor. If the random-walk curve mismatches the empirical curve or increases on the heterophily graphs, then Theorem 1 and Corollary 1 do not establish the claimed universal decay, and Eq. (7) is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is the identification of LC_emp(k) in Eq. (1) with LC_prob(k) in Theorem 1 and Corollary 1. Eq. (1) averages, uniformly over anchors, the fraction of exact shortest-path k-hop neighbors sharing the anchor's label; the theory tracks (T^k)_{ii} for a degree-weighted label-level Markov chain (Appendix A.2, Eq. 16), which counts walks that may revisit nodes and is not restricted to shortest paths. No step in Section 2.2 or Appendix A connects the two measures, and the self-loop assumption used for aperiodicity in Lemma 1 is absent from the empirical construction. Even granting the identification, Corollary 1 only proves convergence from LC_prob(0)=1 to π_i<1 with an exponential bound; it does not establish monotone or overall decay from k=1 onward. In the paper's own two-label heterophily model (Proposition 1), T≈[[1-p,p],[p,1-p]] with p>0.5, so LC_prob(1)=1-p<0.5 while π_i=0.5 for balanced classes: the random-walk quantity increases toward its limit, the opposite of the claimed diminishing pattern. Section 3.1 then builds RELGCL on Eq. (7), E[simstat(v,n)] > E[simstat(v,>n)], presenting this as if it were established by Section 2.2; it is an additional empirical assumption. The empirical decay pattern may be real, but the paper's theoretical guarantees do not support it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies label consistency in graphs, defined as the average fraction of k-hop neighbors sharing the anchor's label. It claims to discover a universal pattern: label consistency systematically decays with structural distance in both homophily and heterophily graphs, manifesting as smooth decay in the former and oscillatory decay in the latter. The authors propose a random-walk convergence theorem as a theoretical guarantee for this pattern, and then introduce RELGCL, a graph contrastive learning framework that preserves the relative similarity between different hop neighborhoods via pairwise and listwise collective-similarity objectives. Experiments on 11 datasets compare against 20 baselines and report consistent improvements.","tokens_in":23963,"tokens_out":6458,"duration_ms":65753,"significance":"If the central claims were correct, the paper would offer a principled alternative to the absolute-similarity paradigm in graph contrastive learning, replacing augmented views with structural-proximity-based relative similarity. The empirical study is broad, the method is clearly described, and the comparison with 20 baselines is extensive. However, the theoretical guarantees do not apply to the empirical quantity they are claimed to explain, and the method strongly resembles the authors' own earlier neighborhood-ranking work. As it stands, the paper's main novelty—the claimed theoretical foundation—is not established, and the incremental contribution over prior work is not clearly delineated.","major_comments":[{"comment":"The random-walk theory governs LC_prob(k), a degree-weighted label-level return probability with self-loops, whereas the empirical measure LC_emp(k) in Eq. (1) is a uniform average over anchors of the fraction of exact shortest-path k-hop neighbors sharing the anchor's label. No argument in Section 2.2 or Appendix A identifies these two quantities: walks may revisit nodes, are not restricted to shortest paths, and are degree-weighted, and the self-loop assumption in Lemma 1 has no counterpart in Eq. (1). Therefore Theorem 1 and Corollary 1 do not establish the claimed decay of LC_emp.","section":"§2.2 and Appendix A.2"},{"comment":"Even for LC_prob, the stated result is only exponential convergence to π_i < 1; convergence does not imply monotone or overall decay. In the paper's own two-label heterophily model T ≈ [[1−p, p], [p, 1−p]] with p > 0.5, LC_prob(1) = 1−p < 0.5 while π_i = 0.5 for balanced classes, so the quantity increases toward its limit. The 'oscillatory decay' claim is thus not a consequence of the theorem, and the proof of Corollary 1 only bounds |LC_prob(k) − π_i|.","section":"§2.2, Corollary 1 and Proposition 1"},{"comment":"The inequality E[simstat(v,n)] > E[simstat(v,>n)] is asserted as a proven consequence of Section 2, but it is neither proven by the random-walk theorems (which concern a different quantity and only convergence) nor derived from the definitions in Eqs. (5)-(6). The RELGCL objectives are then built on this unproven inequality, so the claimed principled foundation for the method is not established; Eq. (7) is an additional empirical assumption.","section":"§3.1, Eq. (7)"},{"comment":"The appendix states that 'a complete theoretical characterization accounting for multiple labels, arbitrary graph structures, and varying degrees of homophily/heterophily remains an open challenge.' This limitation statement directly contradicts the abstract's claim that the paper establishes 'theoretical guarantees' for the universal decay pattern. The manuscript is internally inconsistent about the strength of its theoretical contribution.","section":"Appendix A.6"},{"comment":"The proposed RELGCL objectives—comparing the collective similarity of one hop against further hops using ratio-based InfoNCE-style losses—closely resemble the authors' own 'Graph soft-contrastive learning via neighborhood ranking' [Ning et al., 2022], which is cited only in passing and is not included as a baseline. The paper does not discuss the differences from this prior work, so the claimed novelty and the conclusion that RELGCL outperforms '20 existing approaches' are overstated without a direct comparison against the most relevant predecessor.","section":"§3.3 and Related Work"}],"minor_comments":[{"comment":"The notation N(vi)[k] is defined as a set of sets {N(vi)[1], ..., N(vi)[k], N(vi)[k+1]}, but in Eq. (1) it is used as a set of nodes; please clarify the intended meaning and use distinct notation for the union of the first k hops.","section":"§2.1, Eq. (1)"},{"comment":"There is a typo in the table header: 'Homophiliy' should be 'Homophily'.","section":"Table 7"},{"comment":"The paper does not report the per-dataset hyperparameter values (k, α, τ, τ spacing, embedding dimension) that were selected by grid search; providing a supplementary table would substantially improve reproducibility.","section":"Appendix C.4"},{"comment":"The figure shows point estimates without error bars or standard deviations; given that the 'oscillatory decay' for heterophily graphs rests on small differences between hops, confidence intervals would help assess the robustness of the pattern.","section":"Figure 2"},{"comment":"Several improvements over the best baseline are within one standard deviation (e.g., Chameleon in Table 2: 69.25±0.89 vs 69.12±0.24); reporting confidence intervals or statistical significance tests would strengthen the claim of consistent superiority.","section":"Tables 1-3"}],"recommendation":"reject","confidential_remarks":"The overlap between RELGCL and the authors' own arXiv:2209.13964 is substantial and should be examined by the editor if a revised version is submitted. The empirical study is extensive, but the theoretical core of the paper is not sound as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I just read arXiv:2505.05533. Short version: the empirical observation that label consistency decays with hop distance, and the RELGCL losses built on it, are interesting enough to warrant referee time, but the theoretical guarantee the paper leans on does not hold up. The random walk theorem applies to a label-level walk-return probability, not to the empirical exact-hop neighbor fraction in Eq. 1; the two are not the same object. And convergence to a stationary value is not decay. In the paper's own heterophily model, the theoretical quantity actually increases toward its limit. So Section 3.1's claim that Eq. (7) is \"proven\" is not supported.\n\nWhat's genuinely new: the systematic multi-dataset analysis of exact-hop label consistency (Figure 2), and the collective pairwise/listwise objectives (Eqs. 11-14). The ablation showing that inside-log summation helps over outside-log is a nice result. The benchmark coverage is broad: 20 baselines, ogbn-arxiv, clustering and similarity tasks, structured enough to be reproduced.\n\nThe gap between LC_emp and LC_prob is load-bearing. No step connects them. Self-loops are assumed in the theory but absent in the empirical measure. Even if you fixed that, Corollary 1 is a mixing bound, not a monotone decay statement. The heterophily toy matrix gives λ2 < 0, which predicts oscillation around the stationary value, not net decline. The authors also don't benchmark their own prior GSCL (Ning et al. 2022), which is closely related to the relative-ranking idea; that's a novelty problem worth raising in review.\n\nI don't think the empirical pattern is fake; it's plausible and shown across 11 datasets. The method appears to work. The paper just does not provide the theoretical justification it claims. A revised version that either reframes the theory as a mixing result or actually connects the empirical measure to a walk-based one, and that adds the missing baselines, could be a solid empirical contribution.\n\nFor peer review, I'd send it out. The empirical core deserves scrutiny, and the theoretical overclaim is exactly the kind of thing referees should catch. For me personally, I wouldn't cite it until the gap is closed. Reading group: maybe — it makes for a good discussion about what \"theory\" buys us in graph SSL.","headline":"The empirical decay pattern and RELGCL losses are worth a look, but the random-walk theory is presented as proving something it does not prove, and the paper never connects the theoretical quantity to the measured one.","tokens_in":24480,"tokens_out":2674,"would_cite":false,"duration_ms":28702,"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":"The paper establishes that label consistency in graphs decays systematically with structural distance, and builds a contrastive learning method that preserves this relative similarity instead of enforcing similarity between artificial…","keywords":["graph contrastive learning","relative similarity","label consistency decay","random walk theory","homophily and heterophily","collective similarity objective","node classification","self-supervised learning"],"falsifier":"Compute LC_emp(k) from Eq. (1) on a connected even cycle whose labels alternate A,B,A,B,...: hop-1 neighbors are all different-label (LC=0), but hop-2 neighbors are all same-label (LC=1), so the averaged label consistency rises rather than falls with distance; that graph would refute the claimed universal decay if it appears as a counterexample or is reproducible synthetically. A milder test: any real graph where the graph-averaged LC_emp sequence over k=1..5 is not non-increasing overall.","tokens_in":23396,"feed_emoji":"📉","tokens_out":6251,"duration_ms":57692,"temperature":0.7,"pith_summary":"Across 11 real-world graphs, the paper finds a universal statistical pattern: the fraction of k-hop neighbors sharing a node's label shrinks as k grows, decaying smoothly in homophily graphs and with oscillations in heterophily graphs. It argues this ordered decay is the natural similarity signal graphs encode, and that graph contrastive learning (GCL) should preserve it rather than force absolute similarity between augmented views. To ground the pattern, the paper proves via random walk theory that the same-label return probability of a degree-weighted walk converges exponentially to the edge-proportion of the anchor's label. On this basis it builds RELGCL, whose pairwise and listwise objectives keep near-hop neighbors collectively more similar to the anchor than farther hops. If the pattern holds, structural proximity can replace view augmentation as the organizing principle for GCL.","feed_headline":"Label similarity decays with distance in all 11 graphs","feed_subtitle":"A contrastive learner that preserves this relative ordering beats 20 prior methods on homophily and heterophily graphs.","key_machinery":"The carrying object is label consistency as a function of hop distance. Empirically it is LC_emp(k) from Eq. (1), the graph-averaged fraction of exact k-hop neighbors sharing the anchor's label; theoretically it is LC_prob(k) = p_k(i|i), the same-label return probability of a degree-weighted random walk with self-loops, aggregated to a label-level transition matrix T. The load-bearing identities are Theorem 1, which gives exponential convergence of label probabilities to the stationary edge-proportion distribution π, and Corollary 1, which turns that convergence into a decay statement for LC_prob(k); Proposition 1 uses the sign of the second eigenvalue of T in a two-label model to explain smooth versus oscillatory decay. The method side is the collective similarity ratio: summing exponentials inside the logarithm (Lin) so optimization acts on aggregate similarity of a group of near neighbors versus a group of farther neighbors, capped by threshold α, with RELGCL-PAIR comparing individual hop pairs and RELGCL-LIST comparing each hop against all later hops.","core_discovery":"The paper's central claim is that label consistency — the average proportion of same-labeled nodes at each structural distance — diminishes systematically with distance in both homophily and heterophily graphs, and that this decay is a theorem-level consequence of random walk mixing. The theoretical object is LC_prob(k), the probability that a random walk with self-loops returns to the anchor's label after k steps: with one self-loop per node and a connected graph, the label-level transition matrix is irreducible and aperiodic, so LC_prob(k) converges exponentially to π_i, the degree-weighted share of label i, and π_i < 1 whenever other labels exist. The sign of the second eigenvalue of the label transition matrix then distinguishes smooth decay (homophily, λ2 > 0) from oscillatory decay (heterophily, λ2 < 0). RELGCL translates this statistical ordering into representation space by maximizing collective similarity ratios between nearer and farther hop-neighbor groups, in pairwise and listwise forms, and the paper reports that both outperform 20 baselines on homophily, heterophily, and large-scale graphs. The intended conclusion is that relative similarity, not absolute augmented-view similarity, is the signal GCL should learn.","pith_inferences":["The same decay law could be tested as a theory of oversmoothing in GNNs: layer-wise message passing approximates random-walk mixing, so representation similarity should converge to label edge-proportions, predicting when deeper models lose discriminability.","The two objectives are ranking losses over hop groups; they should transfer to link prediction or graph-level classification, but the paper only evaluates node-level tasks, so that extension is untested.","Spectral computation of the label transition matrix's second eigenvalue on any given graph would let practitioners predict smooth versus oscillatory decay and choose between the pairwise and listwise variants before training.","If LC_prob and LC_emp diverge on specific graphs, the method's motivation would still stand on the empirical pattern, but the theorem would need replacement by a concentration argument over hop neighborhoods."],"forward_implications":["If the claim is right, graph contrastive learning does not need augmentation views: preserving ordered collective similarity across hops is a sufficient self-supervised objective.","The random walk guarantee implies that in any connected graph with self-loops and at least two labels, same-label return probability eventually tracks the degree-weighted label share, so relative similarity is a universal structural signal rather than a homophily artifact.","The eigenvalue explanation predicts heterophily graphs need a wider hop range for their oscillatory pattern to be modeled, which the paper's k-sensitivity results support.","Collective (sum-inside-log) objectives should beat individual positive-pair objectives whenever the semantic relation is statistical, as the paper's ablation on Lout versus Lin shows."],"supporting_citations":[{"why":"supplies the random walk framework used to model label propagation through graph structure.","marker":"[Lovász, 1993]"},{"why":"provides Perron-Frobenius, spectral decomposition, and the convergence-rate theorem behind Theorem 1 and Corollary 1.","marker":"[Levin and Peres, 2017]"},{"why":"supplies Cora, CiteSeer, and PubMed, the citation graphs whose LC_emp decay is measured and used for evaluation.","marker":"[Sen et al., 2008]"},{"why":"supplies Chameleon, Squirrel, and Actor with public splits, the heterophily testbeds showing oscillatory decay.","marker":"[Pei et al., 2020]"},{"why":"defines GRACE, the canonical augmentation-based absolute-similarity GCL method that RELGCL is designed to beat.","marker":"[Zhu et al., 2020b]"},{"why":"GraphACL is the strongest prior baseline on both homophily and heterophily graphs and the main comparison point in Tables 1-2.","marker":"[Xiao et al., 2024]"},{"why":"BGRL provides the large-scale self-supervised baseline on ogbn-arxiv for the extensibility comparison.","marker":"[Thakoor et al., 2021]"},{"why":"AFGRL is the augmentation-free baseline that assumes local homophily and fails on heterophily, sharpening the contrast with RELGCL.","marker":"[Lee et al., 2022]"}],"fun_headline_variants":["Label similarity decays with distance: RELGCL exploits that pattern","Stop forcing absolute similarity: learn graph labels by relative order","Random-walk proof: label proximity falls with distance in all graphs","Relative similarity, not augmented views, powers graph contrastive learning","Preserve relative label similarity to beat 20 baselines on graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the empirical quantity LC_emp(k), computed from exact shortest-path hop neighborhoods, behaves like the theoretical quantity LC_prob(k), computed from a degree-weighted random walk with self-loops; the paper does not show the two measures coincide or decay identically.","fun_headline_variants_meta":{"raw":{"variants":["Label similarity decays with distance: RELGCL exploits that pattern","Stop forcing absolute similarity: learn graph labels by relative order","Random-walk proof: label proximity falls with distance in all graphs","Relative similarity, not augmented views, powers graph contrastive learning","Preserve relative label similarity to beat 20 baselines on graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1547,"prompt_tokens":988,"completion_tokens":559,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":472}},"tokens_in":604,"tokens_out":559,"duration_ms":6081,"temperature":1.0,"reasoning_tokens":472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:07:39.835227+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute LC_emp(k) from Eq. (1) on a connected even cycle whose labels alternate A,B,A,B,...: hop-1 neighbors are all different-label (LC=0), but hop-2 neighbors are all same-label (LC=1), so the averaged label consistency rises rather than falls with distance; that graph would refute the claimed universal decay if it appears as a counterexample or is reproducible synthetically. A milder test: any real graph where the graph-averaged LC_emp sequence over k=1..5 is not non-increasing overall.","supporting_citations":[{"cited_title":"Markov chains and mixing times , volume","cited_arxiv_id":null,"evidence_quote":"provides Perron-Frobenius, spectral decomposition, and the convergence-rate theorem behind Theorem 1 and Corollary 1."},{"cited_title":"Simple and asymmetric graph contrastive learning without augmentations","cited_arxiv_id":null,"evidence_quote":"GraphACL is the strongest prior baseline on both homophily and heterophily graphs and the main comparison point in Tables 1-2."},{"cited_title":"Augmentation-free self-supervised learning on graphs","cited_arxiv_id":null,"evidence_quote":"AFGRL is the augmentation-free baseline that assumes local homophily and fails on heterophily, sharpening the contrast with RELGCL."}],"review_version":1}