{"id":"34a3aaee-6106-4c30-805b-9a440384b615","arxiv_id":"2412.00261","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Under unbiased all-pairs evaluation, GNN link prediction performance drops sharply, and the proposed Gelato method, which learns attribute-weighted Autocovariance ranking, outperforms GNN baselines on most datasets.","lead":"Standard link prediction benchmarks sample an equal number of negative pairs, which paints an overly flattering picture of graph neural network performance. This paper shows that under a more realistic all-pairs evaluation, simple topology heuristics often beat GNNs, and presents Gelato, a similarity-based method that combines node attributes with the Autocovariance heuristic.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The partitioned negative sampling that makes Gelato scalable is justified by flawed lemmas and is validated on only one dataset, leaving the ogbl-collab result unverified under unbiased evaluation.","rationale":"The paper makes a valuable empirical point: standard balanced negative sampling overstates GNN link prediction performance, and simple topological heuristics are competitive under all-pairs evaluation. The experiments on Cora, CiteSeer, PubMed, and ogbl-ddi support this fairly clearly, and the Gelato method shows consistent gains on four of five datasets. However, the central claim's strength rests on the negative sampling scheme being harmless when moving to unbiased evaluation. The reader's weakest assumption correctly identifies that this scheme is justified by lemmas whose proofs are flawed. I agree with that diagnosis. The proof error in Lemma 3 is concrete: the inter-block edge probability is set to 1-p rather than q, which is algebraically inconsistent with the SBM definition. Lemma 4 is a hand-waving inequality that does not establish monotonicity. Even if both conclusions are eventually shown to be true, the paper currently lacks a valid theory for why partitioning cannot hurt. The additional gap is that the lemmas apply to the original graph, not the graph learned by the MLP, yet the method's training and inference use the enhanced graph. On the empirical side, the only direct test of partitioned versus unbiased training is on CiteSeer, so the ogbl-collab result, which relies on partitioned training for the largest dataset, is not verified under the unbiased regime that the paper argues is the realistic one. These issues do not undermine the core empirical observation about biased testing, but they do undermine the completeness of the claim that Gelato's advantages extend to unbiased testing on large graphs. Therefore I would keep the reader's CONDITIONAL verdict: the main finding is sound and important, but the theoretical support and the ogbl-collab evidence need to be strengthened before the paper's broad claims are accepted.","tokens_in":25967,"tokens_out":9458,"duration_ms":83757,"concrete_test":"On PubMed (19,717 nodes), train Gelato under partitioned negative sampling and under full unbiased negative sampling (all O(n^2) negatives) with identical hyperparameters, then evaluate both on the same all-pairs test set. If partitioned training's hits@1000 falls below about 95% of the unbiased-training value, the negative-sampling assumption fails and the ogbl-collab result cannot be treated as evidence for unbiased-testing performance. Additionally, re-derive Lemma 3 with q instead of 1-p to confirm the correct bound, and run a small SBM simulation with varying partition counts to test Lemma 4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that Gelato outperforms GNNs under unbiased testing depends critically on the partitioned negative sampling scheme, which removes inter-partition negatives from training. The theoretical support for this scheme is Lemma 3 and Lemma 4. Lemma 3's proof in Appendix D uses 1-p instead of q as the inter-block edge probability (Eq. 13-15), making the derivation invalid as written; the conclusion may be repairable, but the proof as given is incorrect. Lemma 4's proof in Appendix E is non-rigorous: the claim that increading partitions increases E[R_intra] is asserted from an inequality whose direction is not established, and the notion of 'positive pairs we can lose' is ill-defined. Moreover, these lemmas concern Autocovariance on the original topology, whereas Gelato computes Autocovariance on the attribute-enhanced graph, so the theoretical guarantee does not directly transfer to the learned graph. The only direct empirical validation that partitioned training matches unbiased training is on CiteSeer (Appendix I). For ogbl-collab, the largest dataset, partitioned training is used for scalability, and the reported hits@1000 of 30.92 is a single run without error bars. If the negative-sampling assumption fails on ogbl-collab, the claim that Gelato outperforms GNNs under unbiased testing loses its strongest large-graph evidence, and the paper's headline conclusion would be significantly weakened.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper argues that standard GNN link-prediction evaluation, which balances positive and negative test pairs (termed \"biased testing\"), overstates performance relative to \"unbiased testing,\" where positive edges are ranked against all disconnected pairs. It proposes Gelato, a similarity-based link-prediction method that learns edge weights from node attributes via an MLP, feeds the attribute-enhanced adjacency matrix into the Autocovariance topological heuristic, trains with an N-pair ranking loss, and uses METIS-partition-based negative sampling for scalability. Experiments on Cora, CiteSeer, PubMed, ogbl-ddi, and ogbl-collab report hits@1000, AP, MRR, and prec@k, showing that Gelato outperforms GNN-based baselines on most datasets while also providing ablations, sensitivity analyses, and training-time comparisons.","tokens_in":26193,"tokens_out":12271,"duration_ms":105491,"significance":"If the results hold, the paper makes a valuable contribution by challenging the dominant evaluation protocol for GNN link prediction and by showing that a simple heuristic-based method can be both accurate and scalable under unbiased testing. The empirical finding that Autocovariance and Gelato outperform strong GNN baselines on several datasets is credible and consistently demonstrated on Cora, CiteSeer, and PubMed. The paper's strengths include a clearly defined unbiased evaluation setting, code release, per-component ablations, hyperparameter sensitivity analyses, and wall-clock training-time comparisons. The main weaknesses are theoretical: Lemmas 3 and 4, which justify the partitioned negative sampling used for ogbl-collab, are not rigorously proven as written, and only one dataset validates the equivalence of partitioned and unbiased training. These issues are repairable but need to be addressed before the paper's central claims are fully supported.","major_comments":[{"comment":"The proof of Lemma 3 contains a demonstrable error. In Eq. (13)-(15), the expected Autocovariance for an inter-cluster pair is written as (1/2m)(1-p - d_i d_j/2m) and then set equal to (1/2m)(q - d_i d_j/2m). This equates 1-p with q, but q is the inter-block edge probability and is not 1-p in general. The lemma's statement is true if Eq. (13) is replaced with the correct expression (1/2m)(q - d_i d_j/2m), so the conclusion is repairable, but the proof as printed is invalid. Because Lemma 3 is the stated justification for discarding inter-partition negative pairs in training, the corrected proof should appear in the revision.","section":"Appendix D, Lemma 3"},{"comment":"The proof of Lemma 4 does not establish the claimed monotonicity. The argument defines p as an estimate |E_ik|/|V_ik|^2 and derives the inequality |V_i^k|^2 - |V_i^{k+1}|^2 >= |E_i^k| - |E_i^{k+1}|; this inequality is not sufficient to conclude that the ratio |E_i^{k+1}|/|V_i^{k+1}|^2 is larger than |E_i^k|/|V_i^k|^2, and the notion of \"positive pairs we can lose\" is not rigorously quantified. Moreover, Lemmas 3 and 4 are stated for Autocovariance on the original graph, whereas Gelato computes Autocovariance on the attribute-enhanced graph eA (Eq. 4-5), so the theoretical justification does not directly transfer. The only empirical check of partitioned-versus-unbiased training is on CiteSeer (Appendix I, Fig. 7). Since ogbl-collab relies on partitioned training, this is a load-bearing gap; the revision should either prove the lemmas for the enhanced graph or provide partitioned-versus-unbiased comparisons on at least one additional dataset, ideally PubMed.","section":"Appendix E, Lemma 4 and Section 3.4"},{"comment":"The ogbl-collab result, which provides the largest-graph evidence for the headline claim, is reported as a single run (30.92*) without standard deviation, and Section 4.1 states that hyperparameters were not tuned on ogbl-collab. Combined with the unvalidated partitioned-training assumption, the claimed 11% improvement over the best GNN baseline (BUDDY 27.66 +/- 0.24) is not yet established. Please provide multiple seeds with error bars and, if possible, a tuned baseline set for ogbl-collab.","section":"Table 2 and Section 4.3"}],"minor_comments":[{"comment":"The classifier 2 and 3 tables swap the roles of FP and FN for classifier 2 and set FP=(n-1)p for classifier 3; the final accuracy difference is correct, but the intermediate labels should be fixed to avoid confusion.","section":"Appendix B"},{"comment":"The biased-training results are referenced as 'Table ??' and 'Table ??' but no such tables appear in the manuscript; either include the tables or remove the references.","section":"Appendix N"},{"comment":"The phrase 'unbiased training without downsampling' is not fully specified: it is unclear how many negative pairs N(u,v) are used per positive pair in the N-pair loss and how the O(V^2) negative set is materialized for Cora, CiteSeer, and PubMed; please clarify the implementation.","section":"Section 4.1 and Eq. (9)"},{"comment":"The statement that Gelato 'outperforms existing GNN-based alternatives' is too strong, since Table 2 shows NCNC is better on ogbl-ddi; please qualify by 'most datasets'.","section":"Abstract and Section 4.3"},{"comment":"The last sentence says 'we experimented with different values of p' but the parameter being varied is k (the number of partitions); please correct the notation.","section":"Appendix I"},{"comment":"The SEAL rows contain stray asterisks and misaligned column entries; please clean the table formatting.","section":"Tables 7 and 8"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for a top applied machine learning venue and the evaluation critique is timely. The main risk is that the theoretical support for partitioned sampling is weaker than the empirical results suggest; if the authors correct the proofs or reframe Lemmas 3 and 4 as empirical motivations, and add error bars for ogbl-collab, the paper would be acceptable. I would not reject on the basis of disagreement with the community's current evaluation practices."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zexi/Arlei (or whoever),\n\nThe headline result is worth taking seriously: when you rank positive edges against all disconnected pairs instead of a balanced negative sample, the GNN link-prediction baselines fall apart and a simple topological heuristic—Autocovariance—beats them on most datasets. The paper documents this carefully across four small datasets and ogbl-collab, and it extends the critique in Li et al. 2024 in a useful direction. That alone is a real contribution.\n\nGelato is a reasonable engineering contribution: augment the graph with attribute-similarity edges, weight them with an MLP, feed the result into Autocovariance, train with an N-pair loss, and use METIS to sample hard negatives within partitions. The ablations show each piece earns its keep, and the method wins on Cora, CiteSeer, PubMed, and ogbl-collab, with most runs reporting means and stds. I don't hold the self-citation against it—Autocovariance is public and reproducible.\n\nThe soft spots are concentrated where the paper reaches for theory. Lemma 3's proof in Appendix D writes the inter-block edge probability as 1-p instead of q (Eq. 13–15), so the derivation is invalid as written. It may be repairable, but it is not a mere typo—the wrong quantity is used in the expectation. Lemma 4 in Appendix E is non-rigorous: it asserts that E[R_intra] increases with more partitions from an inequality whose direction is never established, and the notion of 'positive pairs we can lose' is fuzzy. More importantly, both lemmas are about Autocovariance on the original topology, whereas Gelato computes Autocovariance on the attribute-enhanced graph, so the theoretical justification does not directly transfer to the learned graph.\n\nThe empirical support for partitioned training is also thinner than the paper's rhetoric. The only direct comparison of partitioned vs. unbiased training is on CiteSeer (Appendix I, Figure 7). On ogbl-collab, the largest dataset, Gelato is trained with partitioned sampling, and the headline 30.92 hits@1000 is a single run with no error bars. If the negative-sampling assumption fails there, the paper loses its strongest large-graph evidence. And the abstract's claim that Gelato 'outperforms existing GNN-based alternatives' is not literally true: on ogbl-ddi it ties Autocovariance and NCNC wins.\n\nBottom line: the core empirical finding is solid and important; the method is clever; the theory and the ogbl-collab evidence are not. This deserves a serious referee, not a desk reject. Ask for repaired lemmas, error bars on the big run, and a more qualified abstract.","headline":"A real negative result about GNN link prediction, a sensible method, but shaky theory and a single-run large-graph result.","tokens_in":26765,"tokens_out":3802,"would_cite":true,"duration_ms":32198,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Under unbiased evaluation, GNN link predictors are beaten by a simple heuristic that adds node attributes.","keywords":["link prediction","graph neural networks","unbiased evaluation","Autocovariance","negative sampling","graph partitioning","class imbalance","node attributes"],"falsifier":"Take a sparse attributed graph with no community structure, such as a random geometric graph or a planted attribute correlation without modularity, and run Gelato plus the GNN baselines under unbiased testing; if Gelato no longer outperforms either plain Autocovariance or the best GNN baseline, the claim that within-partition sampling suffices would be refuted.","tokens_in":25737,"feed_emoji":"🔗","tokens_out":6527,"duration_ms":57322,"temperature":0.7,"pith_summary":"Link prediction is usually tested by ranking each true edge against an equal sample of random non-edges, a setting this paper calls biased testing. The paper shows that on sparse attributed graphs this protocol flatters graph neural networks: when every disconnected pair is included in evaluation (unbiased testing), basic topological heuristics such as Autocovariance often beat state-of-the-art GNN methods. To address the sparse regime the authors propose Gelato, which uses a small MLP to fold node attributes into edge weights, scores pairs with Autocovariance, and trains with an N-pair ranking loss over hard negatives selected inside graph partitions. On Cora, CiteSeer, PubMed, and ogbl-collab, Gelato reports higher hits-at-1000 than the GNN baselines it is compared with, and it remains competitive on a dense dataset where attributes are absent. The paper's point is that sparse link prediction is a needle-in-a-haystack ranking problem, not a balanced binary classification problem, and that the field's evaluation should be changed accordingly.","feed_headline":"Under honest tests, a plain heuristic beats GNN link predictors","feed_subtitle":"Balanced test sets flatter graph neural nets. Gelato's similarity ranking wins on sparse graphs.","key_machinery":"The load-bearing object is Gelato's pipeline rather than any single layer: an MLP computing edge weights from node attributes, an enhanced adjacency matrix, Autocovariance as the differentiable scoring heuristic, an N-pair ranking loss, and partition-based negative sampling. Autocovariance measures the difference between co-visiting probabilities in a truncated random walk and in a stationary walk, and at $t=1$ it specializes to Modularity, which lets the score separate hard same-community negatives from easy cross-community ones. The N-pair loss contrasts each positive edge against a set of negative pairs, and partition-based sampling restricts negatives to pairs inside the same partition, which the authors justify with stochastic-block-model lemmas showing that intra-block pairs have higher expected Autocovariance.","core_discovery":"The paper's central claim is that reported GNN link-prediction performance in the balanced setting does not transfer to the realistic imbalanced setting. Concretely, with unbiased testing — ranking a held-out positive edge against all disconnected pairs — recent GNN-based methods are often outperformed by Autocovariance, a random-walk heuristic that uses no node attributes and no training. Gelato is the authors' proposed remedy: it modifies the topology by adding attribute-similarity edges and learned MLP edge weights, then applies Autocovariance to the resulting graph, optimizes an N-pair ranking loss, and draws negative pairs from within graph partitions so that training concentrates on hard, same-community negatives. In experiments, Gelato reports the best hits@1000 on Cora, CiteSeer, PubMed, and ogbl-collab, outperforming the best GNN baseline by 138%, 125%, 156%, and 11% respectively, and gains 48%, 39%, 10%, and 139% over its own base Autocovariance heuristic.","pith_inferences":["If unbiased evaluation became the default, many published GNN link-prediction rankings would likely change; the paper's stochastic-block-model example shows that a model knowing block structure can look strong under biased testing while being useless in practice.","The same design — attribute-enhanced graph plus random-walk scoring — could be applied to knowledge-graph completion or recommendation, where hard negatives also dominate; the partitioning idea would need an analogue of communities, such as item categories.","On graphs without community structure, the theoretical justification collapses; a testable prediction is that Gelato's margin over Autocovariance shrinks on non-modular sparse graphs with strong attribute signal.","The paper leaves open whether a more powerful differentiable scorer than Autocovariance would push the gains further while keeping unbiased training tractable."],"forward_implications":["Results reported on balanced test sets overstate GNN link prediction, so comparisons should include unsupervised topological baselines under unbiased evaluation.","A ranking loss with hard negatives is a better training objective than cross-entropy for sparse link prediction.","Node attributes can be injected into the graph structure and scored by a topological heuristic, an alternative to learning node embeddings.","Partition-based negative sampling cuts training cost from $O(|V|^2)$ to $O(\\sum_i |V_i|^2)$ without losing much accuracy on graphs with community structure.","On dense graphs with no attributes, such as ogbl-ddi, Gelato matches rather than beats its base heuristic, indicating that the gains are tied to sparse attributed graphs."],"supporting_citations":[{"why":"It is the early GNN subgraph classifier used as a baseline whose reported balanced-setting performance is re-evaluated under unbiased testing.","marker":"[95]"},{"why":"It is a hashing-based GNN link predictor that supplies a contemporary baseline underperforming under unbiased testing.","marker":"[10]"},{"why":"It is the strongest GNN baseline in the comparisons, generalizing Common Neighbors through message passing, and is the main competitor Gelato must beat.","marker":"[81]"},{"why":"It introduces Autocovariance as a random-walk similarity metric, and Gelato's scoring and postprocessing build directly on this heuristic.","marker":"[30]"},{"why":"It defines the standard benchmark datasets and the balanced evaluation protocol that the paper argues is misleading.","marker":"[28]"},{"why":"It supplies the scalable graph partitioning algorithm used to generate hard negative pairs within partitions.","marker":"[36]"},{"why":"It defines the N-pair loss that Gelato adopts to contrast each positive edge against multiple negative pairs.","marker":"[72]"},{"why":"It relates Modularity to community structure, and the paper shows Autocovariance at $t=1$ specializes to Modularity, motivating the heuristic.","marker":"[57]"},{"why":"It supplies the data-perspective argument that local structural heuristics degrade in sparse networks, motivating the choice of a random-walk heuristic.","marker":"[49]"}],"fun_headline_variants":["GNN link predictors flop on sparse graphs; Gelato reorders the rankings","Simple heuristic beats GNNs on sparse graphs until Gelato steps in","Sparse link prediction: ranking beats classification, Gelato exploits it","GNNs overrated on sparse graphs: ranking heuristic wins with Gelato","Gelato: attribute-aware ranking turns sparse link prediction on its head"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Gelato's partitioned negative sampling presupposes that the graph has community structure, so that within-partition node pairs are the hard negatives that matter; if a real graph lacks such structure, training on intra-partition negatives may not transfer to all-pairs evaluation.","fun_headline_variants_meta":{"raw":{"variants":["GNN link predictors flop on sparse graphs; Gelato reorders the rankings","Simple heuristic beats GNNs on sparse graphs until Gelato steps in","Sparse link prediction: ranking beats classification, Gelato exploits it","GNNs overrated on sparse graphs: ranking heuristic wins with Gelato","Gelato: attribute-aware ranking turns sparse link prediction on its head"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000835,"raw_usage":{"total_tokens":3644,"prompt_tokens":945,"completion_tokens":2699,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":2601}},"tokens_in":561,"tokens_out":2699,"duration_ms":15850,"temperature":1.0,"reasoning_tokens":2601,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:33:15.377899+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a sparse attributed graph with no community structure, such as a random geometric graph or a planted attribute correlation without modularity, and run Gelato plus the GNN baselines under unbiased testing; if Gelato no longer outperforms either plain Autocovariance or the best GNN baseline, the claim that within-partition sampling suffices would be refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It is the early GNN subgraph classifier used as a baseline whose reported balanced-setting performance is re-evaluated under unbiased testing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the scalable graph partitioning algorithm used to generate hard negative pairs within partitions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It relates Modularity to community structure, and the paper shows Autocovariance at $t=1$ specializes to Modularity, motivating the heuristic."}],"review_version":1}