{"id":"dfa53a67-165d-43de-8cf4-c249e906642b","arxiv_id":"2412.08128","paper_version":4,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"EPAGCL derives degree-based edge augmentation probabilities from a new Error Passing Rate metric and reports state-of-the-art accuracy on seven graph datasets, while its core theoretical claim rests on a uniform per-node error assumption.","lead":"The paper introduces a new metric, Error Passing Rate, to explain why removing edges usually helps graph contrastive learning more than adding them, and it proposes an algorithm, EPAGCL, that uses degree-based probabilities to add and remove edges. The experiments show EPAGCL outperforms several graph contrastive baselines, but the theory relies on assumptions that are not met by the benchmark datasets.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central theorem rests on Eq. (5), but the derivation assumes e1 = k m1 for edge subsets not incident to the modified pair; Assumption 3.4 does not imply this, so Theorem 3.5 is unsupported even granting the uniformity assumption.","rationale":"The reader's weakest_assumption correctly identifies Assumption 3.4 as load-bearing, but the more severe problem is internal: even granting Assumption 3.4, the derivation of Eq. (5) in Appendix B is not valid. The per-node error fraction does not imply e1 = k m1 for the set of edges disjoint from {vi,vj}; a cross-edge correction term appears that is unconstrained by the assumption. This gap undermines Theorem 3.5 and the paper's central theoretical explanation. The degree-ratio issue raised by the reader is real but secondary, as it affects Theorem 3.3 rather than the derivation of Eq. (5). I credit the paper for a clear presentation, a reasonable heuristic, and a reproducible algorithm with solid empirical results; the proposed EPAGCL may still be effective. The theoretical claim, however, should be accepted only conditionally on either proving e1 = k m1 from a stronger assumption (e.g., each edge has the same error probability k) or bounding the cross-edge correction and showing the qualitative conclusion survives.","tokens_in":18105,"tokens_out":8684,"duration_ms":88340,"concrete_test":"Construct a small graph that satisfies Assumption 3.4 exactly (e.g., a regular graph with class labels assigned so that every node has the same incoming error fraction k). For a non-edge (vi,vj), compute δ_{G,G'} directly from Definition 3.1 and Eq. (4), and compare it to the value predicted by Eq. (5). If they differ for any such pair, the derivation of Eq. (5) is falsified and Theorem 3.5 lacks support.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 3.5, which explains why dropping edges is more stable than adding edges, follows from Eq. (5): δ_{G,G'} = (k−ξ)·α_{i,j}·m. In Appendix B, this is derived from Assumption 3.4 via the step \"e1 = k·m1, e2 = k·m2, e3 = k·m3\". For l=2 and l=3, the sets are exactly the edges incident to vi or vj, so the per-node assumption gives e_l/m_l = k. For l=1, the edges have neither vi nor vj as endpoints. Summing the per-node constraints over all nodes except vi and vj yields 2e1 + C_err = k(2m1 + C_tot), where C_err and C_tot are the error and total message masses on cross edges between {vi,vj} and the remaining nodes. Thus e1 = k m1 holds only if the cross edges also have error fraction k, which Assumption 3.4 does not state or imply. The proof of Eq. (5) therefore contains a hidden assumption not covered by the stated assumption. Since the paper's central explanation (Section 3.3, Theorem 3.5) relies entirely on Eq. (5), the theoretical claim is not established even for graphs satisfying the stated uniformity assumption. The reader's degree-ratio condition (d_max ≤ 4d_min − 1) affects Theorem 3.3, but the derivation of Eq. (5) does not use that condition, so the e1 = k m1 gap is more fundamental.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper asks why dropping edges is usually a more stable graph augmentation than adding edges in graph contrastive learning. It introduces a metric called Error Passing Rate (EPR), which measures the fraction of message-passing mass that flows along edges connecting different classes in a GCN. The authors derive formulas for the change in EPR when an edge is added or dropped, concluding that, under an assumption of uniform per-node error rates, the change is proportional to alpha_ij = 2/sqrt((d_i+1)(d_j+1)) or 2/sqrt(d_i d_j), and that for graphs with EPR below 0.5 dropping edges is more stable. Based on this analysis they propose EPAGCL, an augmentation method that adds and drops edges with probabilities derived from alpha_ij. Experiments on seven benchmark datasets report competitive or improved accuracy relative to several GCL baselines, together with ablation and efficiency studies.","tokens_in":18467,"tokens_out":9352,"duration_ms":97556,"significance":"The question addressed is relevant and the proposed EPR viewpoint is interpretable: it gives a concrete, label-free-in-principle measure of how well a graph structure matches a GNN's message-passing scheme. If the theoretical derivation were sound, the paper would provide a useful explanation for a widely observed empirical phenomenon and a principled basis for designing augmentations. The paper also ships code and includes a reasonably broad experimental comparison, ablations, efficiency measurements, and appendices with EPR values for real datasets. The main weakness is that the central theorem supporting the paper's explanation contains a derivation gap that is not fixed by the stated assumptions, and the key uniformity assumption is neither justified nor empirically checked. Until these points are repaired, the paper's contribution is primarily an empirical augmentation method rather than an established theoretical explanation.","major_comments":[{"comment":"The derivation of Eq. (5) from Assumption 3.4 is incomplete. Assumption 3.4 states Mwp,i/Mi = k for every node, which gives e2 = k m2 and e3 = k m3 for the edge sets incident to vi and vj, but for the set E1 (edges with neither endpoint equal to vi or vj) it gives only the aggregate constraint 2e1 + C_err = k(2m1 + C_tot), where C_err and C_tot are the error and total message masses on the cut between {vi,vj} and the remaining nodes. The equality e1 = k m1 used in Appendix B therefore requires the additional, unstated condition C_err = k C_tot. Since Eq. (5) and hence Theorem 3.5 are derived entirely from this step, the paper's central explanation for why dropping edges is more stable than adding edges is not established even under Assumption 3.4.","section":"Appendix B / Eq. (5)"},{"comment":"Assumption 3.4 is load-bearing for Theorem 3.5 but is never justified or tested. Table 6 reports only the global EPR rG for benchmark graphs; a global value below 0.5 is compatible with arbitrarily large per-node variation in Mwp,i/Mi, so it does not support the uniformity assumption or the inference that 'k < 0.5 for most graphs' in the sense required by Theorem 3.5. The authors should report the empirical distribution of per-node error fractions on the datasets used in Section 4, or replace Assumption 3.4 with a condition that can actually be checked on real graphs.","section":"Section 3.3 / Appendix F"},{"comment":"Theorem 3.3.2 as stated is false without an additional assumption. The proof introduces Assumption A.2 (at least one same-class edge) only in the appendix and uses it to rule out the equality case t1 = t2 = t3 = 1. If every edge of G connects different classes, then adding a different-class edge leaves rG unchanged, so delta_G,G' = 0 rather than < 0. The theorem statement in Section 3.3 must include this condition or a replacement, and the main text should state it explicitly rather than burying it in the proof.","section":"Theorem 3.3 / Appendix A"},{"comment":"The benchmark datasets used in the experiments do not satisfy the degree condition dmax <= 4 dmin - 1 assumed by Theorem 3.3. For example, Cora has a maximum degree far above 4 dmin - 1, so the experiments in Section 4 cannot be said to validate Theorem 3.3 on these graphs. If the intended validation target is instead Theorem 3.5, this should be stated explicitly, since Theorem 3.5 does not inherit the degree condition from Theorem 3.3.","section":"Section 4 / Theorem 3.3"}],"minor_comments":[{"comment":"In Eq. (2) the numerator and denominator are written with the same symbol E, which is confusing: the numerator should be the sum over the error edge set (edges connecting different classes), while the denominator is the sum over all edges. Please use distinct notation, e.g. an overline or a calligraphic symbol for the error edge set, throughout the paper.","section":"Proposition 3.2 / Eq. (2)"},{"comment":"The Wilcoxon signed-rank test is applied after repeating each of the 5 runs five times to obtain 25 observations. This pseudo-replication violates the independence assumption of the test and inflates the reported significance levels. The test should be run on the original 5 paired observations, or a different procedure should be used.","section":"Appendix E / Table 5"},{"comment":"The symbol for the class-indicator term is xi in Eq. (5) in the main text but becomes s in Appendix B; please standardize the notation.","section":"Section 3.3 / Appendix B"},{"comment":"There are several typographical errors, including 'recursivly' in Section 3.2, 'summarzied' before Theorem 3.3, and 'Memroy' in Table 3; a careful proofread is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is best viewed at present as an empirical augmentation method with an interesting but not yet established theoretical framing. The derivation gap in Eq. (5) is the main obstacle; if it cannot be repaired within the manuscript's scope, the authors should reframe the contribution as empirical rather than as a proof of why dropping edges outperforms adding edges."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort version: this paper asks a genuinely good question — why does dropping edges beat adding edges in graph contrastive learning? — and ships a working algorithm. But the headline theoretical answer is not actually derived. The proof of Theorem 3.5 depends on an extra assumption that isn't stated, so the main claim is unsupported in the current form.\n\nWhat's new: the EPR metric and the attempt to quantify how an edge perturbation changes error passing is a reasonable way to frame the problem. The proposed EPAGCL algorithm, which adds edges between high-degree candidate nodes and drops low-impact edges, performs well on several benchmarks and the code is public. The ablation showing adaptive adding beats random adding is useful practical evidence.\n\nThe soft spots are serious. First, Eq. (5) is derived in Appendix B by setting e1 = k m1 for edges that touch neither vi nor vj. Assumption 3.4 only gives a per-node error fraction. Summing that assumption over all nodes except the modified pair gives an additional term involving cross edges between {vi, vj} and the rest of the graph; you only get e1 = k m1 if those cross edges also have error fraction k. That is a new, untested assumption. Since Theorem 3.5 and the central 'k < 0.5' explanation ride entirely on Eq. (5), the theoretical story is not established even granting the stated uniformity. Second, Theorem 3.3 requires d_max <= 4 d_min - 1, and the benchmark graphs violate that badly; so the formal results don't cover the experiments. Third, the Wilcoxon test in Appendix E duplicates five runs to get a sample size of 25, which is invalid pseudo-replication.\n\nNone of this makes the algorithm useless — the empirical comparison and the ablation are credible — but the paper's central theoretical contribution is not ready. The authors need to either prove e1 = k m1 from a clearly stated stronger assumption, test that assumption on real data, or soften the claims to a heuristic justification.\n\nMy recommendation: if this crosses your desk, send it to review. A serious referee should see the gap; the question is important enough that a revision could make the theory sound, and the empirical part is worth publishing on its own. I'd be skeptical of the current proof, but I'd engage with it.\n\nBest,","headline":"A genuinely good question and a working algorithm, but the central theoretical explanation rests on an unstated extra assumption, so the main claim is not established in the current form.","tokens_in":18992,"tokens_out":3386,"would_cite":true,"duration_ms":35250,"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 claims that the relative stability of edge dropping versus edge adding in graph contrastive learning is governed by the Error Passing Rate, with the change proportional to a degree-based coefficient and the threshold set by an…","keywords":["graph contrastive learning","edge dropping","edge adding","Error Passing Rate","graph augmentation","graph neural network","message passing","self-supervised learning"],"falsifier":"Use ground-truth labels on a benchmark graph to compute each node's error fraction $M_{\\mathrm{wp},i}/M_i$ and check whether the values are nearly constant; if they vary widely, the uniform-$k$ assumption behind Theorem 3.5 does not hold. Alternatively, measure EPR after adding and dropping edges with known $\\alpha$ values and test whether the change is proportional to $\\alpha$ as predicted.","tokens_in":17885,"feed_emoji":"📉","tokens_out":16603,"duration_ms":160064,"temperature":0.7,"pith_summary":"Graph contrastive learning usually augments a graph by dropping edges; adding edges is empirically unstable, and the paper's question is why. It defines the Error Passing Rate (EPR), the fraction of message-passing traffic in a GCN that crosses class boundaries, and proves that the EPR change caused by adding or dropping one edge is proportional to a degree-based coefficient $\\alpha_{ij}$. Under the paper's uniformity assumption, adding an edge between same-class nodes lowers EPR by $k\\alpha/m'$, adding a cross-class edge raises it by $(1-k)\\alpha/m'$, and dropping an edge has the mirror-image magnitudes. Since real graphs have $k<0.5$ and most candidate non-edges are cross-class, a random added edge injects the larger error term while a random dropped edge carries the smaller one, which is the paper's explanation for the empirical preference for dropping. The paper then turns this into an augmentation algorithm, EPAGCL, that weights edge additions and drops by EPR-derived coefficients and reports gains over existing contrastive baselines.","feed_headline":"Dropping edges beats adding: new formula explains why","feed_subtitle":"An error-passing rate ties augmentation stability to node degrees and predicts when adding edges should win.","key_machinery":"The central object is the Error Passing Rate (EPR), $r_G=M_{\\mathrm{wp}}/M$, the proportion of messages in GCN aggregation that travel along error edges, i.e. edges linking different classes. The load-bearing identity is $\\delta_{G,G'}=m\\,m'\\,(r_G-r_{G'})=(k-\\xi)\\,\\alpha_{ij}\\,m$ under Assumption 3.4, where $\\alpha_{ij}$ is the degree-normalized coefficient $2/\\sqrt{(d_i+1)(d_j+1)}$ for an added edge and $2/\\sqrt{d_i d_j}$ for a dropped edge. This identity reduces the effect of a single edge perturbation to a product of a universal error fraction, a class-concordance indicator, and a degree factor, which is what lets the paper compare the stability of adding and dropping without labels. It also supplies the algorithmic pre-screening criterion: candidate edges can be ranked by $\\alpha$ and perturbed only when the EPR impact is small.","core_discovery":"The paper's central claim is that the relative stability of edge dropping versus edge adding in graph contrastive learning is governed by an Error Passing Rate (EPR), defined as the ratio of GCN message-passing traffic that flows between different classes. For a graph $G$ and a graph $G'$ obtained by adding edge $(v_i,v_j)$, the paper proves the identity $\\delta_{G,G'} = m\\,m'\\,(r_G - r_{G'}) = (k-\\xi)\\,\\alpha_{ij}\\,m$, where $k$ is the assumed uniform per-node error fraction, $\\xi=1$ exactly when the endpoints have different classes, and $\\alpha_{ij}=2/\\sqrt{(d_i+1)(d_j+1)}$. For dropping the same edge the sign reverses, $\\delta_{G',G}=(\\xi-k)\\alpha_{ij}m$, with $\\alpha_{ij}=2/\\sqrt{d_i d_j}$ in the original graph. The magnitudes are therefore $k\\alpha/m'$ for a same-class addition, $(1-k)\\alpha/m'$ for a cross-class addition, and the mirror image for drops. Because most real graphs have $k<0.5$ and because almost all non-edges are cross-class, this explains why dropping edges usually hurts less than adding edges; the paper goes on to construct an augmentation method that samples edges according to these $\\alpha$ weights.","pith_inferences":["If Assumption 3.4 is replaced by node-dependent error fractions $k_i$, the clean proportionality in the paper's Eq. (5) should become a weighted average; a per-node version of the theorem could predict which local neighborhoods benefit from drops versus adds.","The predicted reversal at $k=0.5$ is directly testable: on a heterophilic or dense graph with EPR above one half, the theory says edge adding should become the stable augmentation, turning EPR into a practical guide for augmentation choice.","The analysis treats one edge perturbation at a time; an extension to simultaneous perturbations or deeper GNNs would show whether the $\\alpha$-based edge ranking survives interactions, which is the assumption the EPAGCL sampling procedure effectively makes."],"forward_implications":["Under $k<0.5$ in homophilic graphs, the expected EPR damage of a random edge addition ($(1-k)\\alpha/m'$ for the typical cross-class non-edge) exceeds that of a random edge drop ($k\\alpha/m$ for the typical same-class edge), which is the paper's quantitative explanation for the empirical rule.","Because non-edges vastly outnumber edges, blind edge adding is almost always a cross-class move and therefore raises EPR; limiting additions to non-edges with small $\\alpha$ should make adding competitive with dropping.","Low-degree node pairs have larger $\\alpha$, so their perturbation changes EPR more; augmentation policies that frequently drop low-degree edges are predicted to be higher-variance, a prediction the paper verifies against importance-based edge dropping.","A symmetric use of added edges is beneficial in only one of the two contrastive views; the paper's EPAGCL uses add-and-drop for one view and drop-only for the other, and reports lower standard deviation as well as higher accuracy."],"supporting_citations":[{"why":"Supplies the GCN propagation rule whose normalized adjacency matrix defines the EPR calculation.","marker":"Kipf and Welling 2017"},{"why":"Provides the contrastive objective and the random edge-dropping sampling that the proposed method builds on.","marker":"Zhu et al. 2020"},{"why":"Supplies the adaptive augmentation baseline and the probability-normalization step used to convert weights into edge-drop probabilities.","marker":"Zhu et al. 2021"},{"why":"Supplies the InfoNCE objective used for training the contrastive model.","marker":"van den Oord, Li, and Vinyals 2018"},{"why":"Provides the positive-incentive-noise idea that motivates turning EPR-derived weights into deliberate augmentation noise.","marker":"Li 2022"}],"fun_headline_variants":["Why edge dropping beats adding in graph contrastive learning","New metric explains graph augmentation: drop beats add","Error Passing Rate reveals why edge dropping wins","Graph contrastive learning: why drop edges, not add them","EPR formula predicts edge augmentation success"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire quantitative comparison rests on the assumption that every node receives the same fraction $k$ of erroneous messages during aggregation, a condition real graphs will only approximate.","fun_headline_variants_meta":{"raw":{"variants":["Why edge dropping beats adding in graph contrastive learning","New metric explains graph augmentation: drop beats add","Error Passing Rate reveals why edge dropping wins","Graph contrastive learning: why drop edges, not add them","EPR formula predicts edge augmentation success"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000477,"raw_usage":{"total_tokens":2414,"prompt_tokens":1041,"completion_tokens":1373,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":657,"completion_tokens_details":{"reasoning_tokens":1311}},"tokens_in":657,"tokens_out":1373,"duration_ms":11343,"temperature":1.0,"reasoning_tokens":1311,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:12:03.388429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Use ground-truth labels on a benchmark graph to compute each node's error fraction $M_{\\mathrm{wp},i}/M_i$ and check whether the values are nearly constant; if they vary widely, the uniform-$k$ assumption behind Theorem 3.5 does not hold. Alternatively, measure EPR after adding and dropping edges with known $\\alpha$ values and test whether the change is proportional to $\\alpha$ as predicted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the contrastive objective and the random edge-dropping sampling that the proposed method builds on."}],"review_version":1}