{"id":"957d0e0f-4747-4b61-9fd1-72a68c588358","arxiv_id":"2505.12411","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"REFine rewires a graph toward a label-driven reference graph to increase edge homophily, and standard GNNs trained on the rewired graph match or beat specialized heterophilic GNNs on several benchmarks.","lead":"This paper introduces REFine, a graph rewiring method that raises the homophily of a graph before training a graph neural network, which improves node classification on heterophilic graphs. It builds a reference graph from node features and training labels, then adds or deletes edges so connected nodes are more likely to share a class.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing comparison to DHGR, the closest homophily-rewiring method, leaves the abstract's 'outperforms existing rewiring techniques' claim unverified.","rationale":"The reader's CONDITIONAL verdict already captures the main weaknesses: overclaiming in the abstract, a fixable proof error in Theorem 1, conditional homophily guarantees, and the absent DHGR comparison. I agree with these, but I would rank the DHGR omission as the single most load-bearing concern because it is the only one that directly contradicts a literal reading of the abstract's superiority claim and because DHGR is, by the paper's own description in Section 2, the most notable prior work on homophily-enhancing rewiring. The feature-label alignment assumption is important but is a general limitation of feature-based methods, is tested indirectly in Table 9, and is acknowledged in Section 8. The Theorem 1 algebraic error is serious but does not sink the paper: replacing the false equality with the Cauchy-Schwarz inequality yields the same bound (up to a factor of two), so the result is salvageable. The best-of-three construction of ST+REFine in Table 2 is also worth disclosing, but Table 1 already shows REFine improves each backbone relative to its own None baseline, so the central empirical phenomenon is not an artifact of the selection. Since the missing DHGR comparison is a revision rather than a demonstrated failure, the reader's CONDITIONAL verdict should stand.","tokens_in":19229,"tokens_out":20327,"duration_ms":218925,"concrete_test":"Run DHGR (official code from Bi et al., TKDE 2024) on the datasets in Table 1 where it is tractable (Cornell, Texas, Wisconsin, Chameleon, Squirrel, BlogCatalog, Actor, BGP, Roman-empire), using the same five splits, clustering adaptation used for the other baselines, and a validation-based hyperparameter search. Compare test accuracy for GCN, GATv2, and APPNP backbones. If DHGR is within one SEM or better on most datasets, restrict the abstract's superiority claim to the tested baselines; if REFine wins by clear margins, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 identifies DHGR [23] as the most notable existing rewiring method for enhancing homophily, then excludes it from Tables 1 and 2 on the grounds that it is closer to Graph Structure Learning. This scope decision is defensible for a GSL benchmark, but the abstract's central claim is 'outperforms existing rewiring techniques and specialized GNNs.' The rewiring baselines actually run (SDRF, FoSR, BORF) target over-smoothing and over-squashing, not homophily; DHGR is the direct competitor for the paper's stated purpose. Without a head-to-head, a reader cannot tell whether REFine advances the state of the art or merely matches a method already published [23]. If DHGR is considered GSL and thus out of scope, the wording of the claim should be narrowed to 'outperforms SDRF/FoSR/BORF' to avoid overclaiming. The theoretical proof error in Theorem 1 is real but salvageable via Cauchy-Schwarz, and the feature-label alignment limitation is explicitly acknowledged in Section 8; the DHGR omission is the most direct unverified factual claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes REFine, a graph rewiring method that increases edge homophily by adding or deleting edges guided by a reference graph constructed from node features and training labels via label-driven diffusion. The authors prove that adding or removing random edges from or against a suitable reference graph improves expected homophily (Props. 1-2), and they prove a lower bound linking homophily to the Dirichlet energy of linearly separable embeddings (Thm. 1). The method clusters large graphs with METIS for scalability and is evaluated on 11 heterophilic datasets across GCN, GATv2, and APPNP, comparing favorably to several rewiring baselines and specialized GNNs. The paper includes code and reports extensive ablations, including the effect of cluster size and the homophily of the constructed reference graphs.","tokens_in":19348,"tokens_out":9389,"duration_ms":90134,"significance":"If the concerns below are addressed, the paper makes a useful contribution: it gives a clean expected-homophily monotonicity result for reference-guided rewiring, a scalable and practical algorithm, and strong empirical gains on several heterophilic benchmarks. The release of code and the use of standard benchmarks support reproducibility. The main conceptual novelty—using a feature- and label-driven reference graph to rewire for homophily—is well motivated. However, the strongest claims in the abstract and introduction are currently broader than what is actually verified, and one central proof contains an algebraic error that must be corrected.","major_comments":[{"comment":"The proof contains an algebraic error: the displayed equality \\sum_{(u,v)\\in E} A_{uv}\\|y_u - y_v\\|^2 = 2\\|W\\|^2\\operatorname{tr}(Z^T L Z) is false because \\|(z_u - z_v)W\\|^2 is not equal to \\|W\\|^2\\|z_u - z_v\\|^2 for a general matrix W. The correct step is an inequality \\|(z_u - z_v)W\\|^2 \\le \\|W\\|^2\\|z_u - z_v\\|^2, which still yields the stated lower bound after dividing by \\|W\\|^2. This must be corrected; as written, the proof does not establish Theorem 1, which is the paper's main theoretical motivation.","section":"Appendix A.1, proof of Theorem 1"},{"comment":"The abstract and Section 1 claim that REFine 'outperforms existing rewiring techniques,' but the only homophily-targeted rewiring method discussed in Section 2, DHGR [23], is excluded from all experiments on the basis that it is closer to graph structure learning. The baselines actually evaluated (SDRF, FoSR, BORF) are designed for over-smoothing and over-squashing, not homophily. As a result, the headline claim is not substantiated for the directly relevant competitor. The authors should either add a DHGR comparison (even on a subset of datasets) or narrow the claim to the evaluated baselines.","section":"Section 2 and Tables 1-2"},{"comment":"The theoretical guarantees of Props. 1 and 2 apply to a random rewiring process on the whole graph and require exact conditions on H(G_r\\setminus G) and H(G\\cap G_r^c). In the deployed method, rewiring is performed per METIS cluster, the conditions are checked only approximately using a sampled graph (Appendix C.3), and the choice of edge addition versus deletion is selected as a hyperparameter by validation accuracy rather than by whether the proposition's condition holds. The abstract's statement 'with theoretical guarantees on the homophily of the rewired graph' therefore overstates the connection between the theory and the actual algorithm. The gap should be made explicit and analyzed, or the guarantee should be limited to the idealized setting of Section 4.1.","section":"Section 5 and Props. 1-2"}],"minor_comments":[{"comment":"The text 'where n<n ' is missing a subscript, and 'Y =\\in \\mathbb{R}^{n\\times 1}' contains a typo; please fix both.","section":"Section 5, notation"},{"comment":"The text refers to '(4a)' and '(4b)' when discussing Figure 2; these should be '(2a)' and '(2b)'.","section":"Section 4.2, figure reference"},{"comment":"The proof models edge selection as i.i.d. Bernoulli draws, while Algorithm 1 samples a random subset without replacement. The expectation formula is unaffected by this distinction, but the proof should state the correct sampling model or justify the equivalence.","section":"Appendix A.2, sampling model"},{"comment":"The theorem says 'linearly separable embeddings,' but the proof assumes the exact equality Y = ZW, i.e., a zero-error linear classifier. This assumption is stronger than linear separability and should be stated explicitly in the theorem.","section":"Theorem 1 statement"},{"comment":"'T/0' should be 'T/O' (timeout).","section":"Appendix D"},{"comment":"The REFine Gain row uses upward and downward arrows without a definition; please add a note that they indicate positive and negative gains, respectively.","section":"Table 1 caption"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the empirical results are strong, but the abstract overclaims given the missing DHGR comparison and the negative gains on some datasets. The proof error in Theorem 1 is embarrassing but clearly fixable. If the authors add the direct comparison, correct the proof, and temper the claims, the paper could become acceptable. I would recommend a careful major revision rather than outright rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Headline first: REFine is a genuinely new and mostly well-executed rewiring recipe, and its core claim — that a homophilic reference graph can be used to rewire a heterophilic graph and help standard GNNs — is supported by the experiments. But the abstract is one sentence too brave. The closest existing homophily-rewiring method, DHGR, is identified in Section 2 and then never compared; 'outperforms existing rewiring techniques' is only verified against SDRF, FoSR, and BORF, which target over-smoothing and over-squashing rather than homophily.\n\nWhat's good. The framework is simple and the theory matches it. Props 1 and 2 are elementary but correct in expectation, and the simulations in Figures 1 and 2 show the mechanism actually working: when the homophily condition holds, rewiring raises homophily and, in the cases that matter, accuracy; when it fails, both drop. That clean validation makes the empirical section credible. METIS clustering keeps the method linear in n, and the runtime table (0.1s vs 4.7s on Wisconsin, 4.2s vs 380s on Roman-empire) is a real practical win over the baselines. Code is released, SEM is reported, and the gains are consistent across GCN, GATv2, and APPNP.\n\nSoft spots, in proportion. The DHGR omission is the main one. The authors' rationale (DHGR is closer to graph structure learning) is defensible for scoping the benchmark, but then the claim should be narrowed, or DHGR should be run. As written, the central claim is broader than the evidence. Table 2 also doesn't fully back 'outperforms specialized GNNs': on BlogCatalog, H2GCN is ahead; on Actor, GPRGNN and OrderedGNN are ahead; on BGP, the specialized models win. The honest phrasing is 'matches or beats on most datasets.' Theorem 1 has a genuine algebraic slip — pulling ||W||^2 out of a norm as if it were an equality — but the bound survives with Cauchy-Schwarz in the right direction, so it's a proof cleanup, not a broken result. The Y = ZW assumption is zero-error, which makes the theorem motivational; the prose should say that in so many words. Last, the method has five free hyperparameters (epsilon, k, kernel choice, rewiring direction, cluster size). The validation grid search is reasonable, but it's a lot of tuning surface.\n\nBottom line: this is a solid, practical paper with a reproducible empirical payoff, and the flaws are fixable. I'd send it out with a request to narrow the abstract, add or explicitly justify the missing DHGR comparison, and clean up the Theorem 1 proof. Worth a serious referee.","headline":"A clean, practical rewiring method whose empirical story holds up — but the abstract overclaims past what the experiments actually compare against.","tokens_in":19982,"tokens_out":4762,"would_cite":true,"duration_ms":39512,"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":"Rewiring with a label-aware reference graph beats specialized GNNs","keywords":["graph neural networks","heterophily","graph rewiring","homophily","reference graph","label-driven diffusion","node classification","edge homophily"],"falsifier":"On a heterophilic benchmark, corrupt the node features so they are independent of the class labels while keeping the original graph and label distribution fixed; REFine should then fail to produce a reference graph with $H(G_r) > H(G)$ and should show no accuracy gain over training on the original graph. A cleaner test: run the method on two synthetic graphs with identical structure and labels, one with label-aligned features and one with permuted features, and compare rewired homophily and test accuracy.","tokens_in":18919,"feed_emoji":"🕸️","tokens_out":6963,"duration_ms":61589,"temperature":0.7,"pith_summary":"This paper argues that graph rewiring, not just specialized architectures, can fix GNNs on heterophilic graphs, where connected nodes tend to have different labels. It proves that higher edge homophily relaxes the tension between the smoothness GNNs impose on embeddings and the linear separability needed for classification (Theorem 1), then shows that rewiring with a reference graph lifts homophily in expectation when the reference graph's residual edges are more homophilic than the original graph (Propositions 1 and 2). The proposed method, REFine, builds that reference graph by combining node features with training labels through label-driven diffusion, and treats edge addition or deletion as a scalable per-cluster preprocessing step. On 11 real-world datasets, standard GNNs trained on the rewired graph match or outperform both existing rewiring techniques and specialized heterophilic GNN architectures. The practical payoff is that homophily-enhancing rewiring is a viable alternative to designing new message-passing schemes.","feed_headline":"Rewiring with a label-aware reference graph beats specialized GNNs","feed_subtitle":"Adding or deleting edges chosen by a feature-label diffusion kernel improves node classification on low-homophily graphs.","key_machinery":"The load-bearing object is the reference graph $G_r$, a second graph on the same node set whose edge set is derived from a clipped label-driven diffusion kernel $\\Gamma = P D P$: first normalize a Gaussian feature-affinity matrix $W_D$ into a diffusion kernel $D$, define a label-propagation kernel $P$ from training labels, and multiply $P D P$ so labels are propagated onto unlabeled nodes through feature geometry. Row-wise clipping of $\\Gamma$ yields the binary adjacency of $G_r$. Two propositions carry the argument: edge addition improves expected homophily exactly when the reference graph's edges not already present are more homophilic than the original graph (Prop. 1), and edge deletion improves it when the common part of the original graph and the reference graph's complement is less homophilic than the original (Prop. 2). A corollary simplifies the addition condition to $H(G_r) > H(G)$ when the reference graph is much larger than the original, which is the condition used in practice. Scalability comes from partitioning the graph into balanced clusters, rewiring each cluster independently, and reattaching inter-cluster edges, giving per-cluster cost $O(c^3)$ and overall $O(c^2 n)$, effectively linear in the number of nodes when clusters are small.","core_discovery":"The central claim is that a graph's own structure can be improved for message passing by consulting a second graph, the reference graph, built from the same nodes, and that homophily-enhancing rewiring is provably effective when the reference graph is more homophilic than the original. Formally, the paper links edge homophily to a lower bound on the Dirichlet energy of any linearly separable embedding: $\\mathrm{tr}(Z^T L Z) \\geq \\frac{\\alpha_m |E|}{2\\|W\\|^2}(1-H(G))$, so low-homophily graphs force a trade-off between smoothing and separability. It then proves that adding random edges from the reference graph increases expected homophily if $H(G_r \\setminus G) > H(G)$, and deleting random edges shared with the reference graph's complement increases it if $H(G \\cap G_r^c) < H(G)$. The practical discovery is that a reference graph built from feature similarities and training labels via the label-driven diffusion kernel $\\Gamma = P D P$ is homophilic enough to trigger these conditions, and that rewiring with it improves node classification for standard GNNs across low-homophily benchmarks.","pith_inferences":["Because the reference graph is built from features and training labels only, the same construction could be applied inductively to unseen graphs in a trained model's deployment, provided the label-driven diffusion kernel can be estimated from a small labeled seed.","The homophily conditions in Propositions 1 and 2 could be used online: estimate $H(G_r \\setminus G)$ and $H(G \\cap G_r^c)$ from a validation sample, then choose edge addition, deletion, or no rewiring accordingly, turning $k$ from a fixed hyperparameter into an adaptive decision.","If feature similarity and label structure diverge, for example when features are noisy or dominated by a spurious signal, the method's own condition predicts failure; a test on a graph with deliberately label-uncorrelated features would sharpen the boundary of applicability.","The reference-graph idea could also be used to target properties other than homophily, such as preserving local clustering or reducing over-squashing, by choosing the reference graph to encode the desired structural prior."],"forward_implications":["Standard GNNs (GCN, GATv2, APPNP) can match or exceed specialized heterophilic architectures (MixHop, H2GCN, GPRGNN, OrderedGNN) simply by training on the rewired graph.","The larger the homophily gap between the original graph and the reference graph, the larger the expected accuracy gain; datasets with very low original homophily benefit most.","The method scales to graphs with hundreds of thousands of nodes because rewiring is performed independently on clusters, with complexity linear in node count when clusters are small.","Rewiring can be guided by a simple check: if the reference graph, or its residual edges, is not more homophilic than the original, edge addition should be avoided because it degrades both homophily and accuracy.","A reference graph constructed from features and training labels can be used to rewire larger graphs without requiring full label supervision, since only training labels enter the diffusion kernel."],"supporting_citations":[{"why":"Supplies the label-driven diffusion construction ($\\Gamma = P D P$) that generates the reference graph from features and training labels.","marker":"[14]"},{"why":"Provides the kernel normalization and diffusion-map basis that defines the data kernel $D$.","marker":"[15]"},{"why":"Provides balanced graph partitioning that makes rewiring per-cluster and therefore scalable.","marker":"[27]"},{"why":"Contributes the definition of linearly separable embeddings used in the proof of Theorem 1.","marker":"[33]"},{"why":"Supplies the cleaned Chameleon and Squirrel splits used to avoid train-test leakage in the benchmark evaluation.","marker":"[34]"},{"why":"Benchmark baseline: a specialized heterophilic GNN (H2GCN) that REFine must match or beat.","marker":"[6]"},{"why":"Benchmark baseline: MixHop, a specialized heterophilic GNN compared in the main results.","marker":"[8]"},{"why":"Baseline rewiring method (BORF) used in the comparison tables.","marker":"[21]"},{"why":"Baseline rewiring method (SDRF) used in the comparison tables.","marker":"[22]"},{"why":"Baseline rewiring method (FoSR) used in the comparison tables.","marker":"[28]"}],"fun_headline_variants":["Reference-graph rewiring beats specialized heterophilic GNNs","Rewire with a homophilic reference to lift GNN accuracy","Use a second graph to rewire the first for better GNNs","A reference graph guides rewiring for strong homophily gains"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes the feature space gives a meaningful similarity measure aligned with the labels; if it does not, the label-driven reference graph will not be more homophilic than the original graph, and the rewiring step can lower both homophily and accuracy.","fun_headline_variants_meta":{"raw":{"variants":["Reference-graph rewiring beats specialized heterophilic GNNs","Rewire with a homophilic reference to lift GNN accuracy","Use a second graph to rewire the first for better GNNs","A reference graph guides rewiring for strong homophily gains"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2873,"prompt_tokens":992,"completion_tokens":1881,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":608,"completion_tokens_details":{"reasoning_tokens":1808}},"tokens_in":608,"tokens_out":1881,"duration_ms":13475,"temperature":1.0,"reasoning_tokens":1808,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:35:03.650178+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a heterophilic benchmark, corrupt the node features so they are independent of the class labels while keeping the original graph and label distribution fixed; REFine should then fail to produce a reference graph with $H(G_r) > H(G)$ and should show no accuracy gain over training on the original graph. A cleaner test: run the method on two synthetic graphs with identical structure and labels, one with label-aligned features and one with permuted features, and compare rewired homophily and test accuracy.","supporting_citations":[{"cited_title":"Supervised and semi-supervised diffusion maps with label-driven diffusion","cited_arxiv_id":null,"evidence_quote":"Supplies the label-driven diffusion construction ($\\Gamma = P D P$) that generates the reference graph from features and training labels."},{"cited_title":"Be- yond homophily in graph neural networks: Current limitations and effective designs","cited_arxiv_id":null,"evidence_quote":"Benchmark baseline: a specialized heterophilic GNN (H2GCN) that REFine must match or beat."}],"review_version":1}