{"id":"c18ccb28-a5b8-45e5-96fe-5daaba904cec","arxiv_id":"2508.19071","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A learned triangle-selection module rewires graphs for GNNs, improving node classification over prior rewiring methods on 9 of 10 benchmarks.","lead":"TRIGON is a graph rewiring method that trains a network to select useful triangles from the original edges, a feature-based nearest-neighbor graph, and a Delaunay triangulation. On ten node classification benchmarks it beats eight earlier rewiring methods on nine datasets, with the largest gains on heterophilic graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lcontr may use validation/test labels to supervise triangle selection, which would make the reported SOTA accuracy gains an artifact of label leakage rather than rewiring.","rationale":"The reader's weakest assumption was that the candidate triangle set T might lack useful cross-community triangles. That is a real limitation of the method, but the ablations in Figure 4 partially address it by showing that random selection of all triangles underperforms TRIGON, and the method can still be useful even if T is incomplete. The label-leakage concern is more directly threatening: if Lcontr uses all node labels, the selector is explicitly trained with test labels, and the reported gains may not reflect genuine rewiring quality. This concern is concrete, tied to a specific equation (Section 4.2), and testable with the released code. I therefore disagree with the reader's choice of weakest assumption and recommend keeping the verdict CONDITIONAL: the paper should be accepted only if the authors confirm Lcontr is restricted to training labels or rerun the experiments with a training-only mask.","tokens_in":27564,"tokens_out":4507,"duration_ms":55241,"concrete_test":"Inspect the released code to see whether Lcontr is masked to training nodes. Concretely, rerun the experiments with y^triangle_ijk computed only for triangles whose three vertices are all in Vtrain (or, at minimum, with no test/validation labels used), keeping everything else fixed. If average accuracy drops materially or TRIGON no longer beats DR/JDR on 9/10 benchmarks, the central SOTA claim is unsupported. Also rerun with validation labels masked to verify the result is robust.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central empirical claim is that TRIGON outperforms prior rewiring methods on 9/10 benchmarks. The auxiliary contrastive loss in Section 4.2, Lcontr, is defined over all candidate triangles T with a binary label y^triangle_ijk = 1 if at least two of the three nodes share the same class label, 0 otherwise. Unlike LGNN, which is explicitly averaged over Vtrain, Lcontr has no Vtrain mask and is summed over |T|. Under the 60/20/20 split described in Section 5.2, this means the triangle selector is trained with validation and test labels. Because the selector directly determines which edges are added to the rewired graph, test labels can leak into the topology used by the GNN. This is not a minor implementation detail: the reported improvements over DR, JDR, and other baselines could be largely due to peeking at test labels rather than to the triangle-selection mechanism itself. The paper also claims joint optimization of selection and classification, but the GNN loss does not actually flow into the selector because the graph is reconstructed by thresholding p_ijk at 0.5; the selector is trained only by Lcontr, Lstruct, and Lpart. While this weakens the 'joint' framing, the label-leakage issue is the more serious threat to the main accuracy claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TRIGON, a graph rewiring method that constructs a new graph by selecting triangles from a candidate set obtained from the original graph, a k-NN graph over raw features, and a Delaunay triangulation over learned embeddings. Triangle selection is trained with a Gumbel-Softmax relaxation and a multi-part loss, and the resulting graph is used to train a GNN (GCN or GAT) for node classification. The authors report performance gains over eight rewiring baselines on nine of ten benchmarks, improved structural metrics such as reduced diameter and higher spectral gap, and greater robustness to oversmoothing at increased depth.","tokens_in":27892,"tokens_out":4519,"duration_ms":51956,"significance":"If the empirical claims are valid, TRIGON would be a practically useful rewiring method: it combines explicit higher-order (triangle) structure with a learned, feature-aware selection mechanism, and it is evaluated on a broad set of homophilic and heterophilic graphs under two backbone architectures. The paper also releases code and includes ablations of the loss components and triangle sources. The central concern is whether the reported accuracy gains are attributable to the rewiring mechanism itself or to leakage of validation/test labels into the triangle selector through Lcontr; this must be resolved before the contribution can be assessed.","major_comments":[{"comment":"The contrastive loss Lcontr is summed over all candidate triangles T and uses y^triangle_ijk = 1 if at least two of the three nodes share the same class label. Under the 60/20/20 split in Section 5.2, T includes triangles containing validation and test nodes, so the selector is trained with validation and test labels. Because the selected triangles determine E* used for GNN training and evaluation, test labels can leak into the topology and inflate the reported accuracies in Tables 2 and 3. This directly affects the paper's central 9/10 claim. Please restrict Lcontr to triangles whose vertices are all in Vtrain (or otherwise remove any dependence on non-training labels), rerun the experiments, and report whether the accuracy gains persist.","section":"Section 4.2, Lcontr definition"},{"comment":"The paper claims 'joint optimization of triangle selection and downstream classification', but the described pipeline does not support this. The rewired graph is reconstructed by thresholding p_ijk at 0.5 (Section 4.1), so the GNN loss LGNN cannot backpropagate into the selector. The selector loss Lselector = Lcontr + Lpart + Lstruct (Eq. 5) contains no classification term. Moreover, Lstruct and Lpart are computed over the discrete set Tsel and appear non-differentiable with respect to p_ijk unless a straight-through or soft-count estimator is used, which is not specified. The only differentiable supervision for the selector is Lcontr, which is the same loss that uses test/validation labels. Please clarify the actual optimization path, or implement a differentiable relaxation (e.g., soft edge weights from p_ijk) and state explicitly whether LGNN updates the selector.","section":"Section 4.2, Eq. (5) and graph reconstruction"},{"comment":"The JDR baseline is reported as 71.23±0.18 with GCN (Table 2) but 62.09±0.18 with GAT (Table 3) on Roman-Empire, a difference of 9.14 accuracy points for the same upstream rewiring method. TRIGON itself changes from 66.52 to 64.36 between the same two tables. This large inconsistency needs explanation; if JDR is retrained per backbone, the protocol should be stated, otherwise the comparison is not reliable. The claim of 9/10 wins 'regardless of backbone' depends on this point being resolved.","section":"Tables 2 and 3, Roman-Empire row"},{"comment":"Structural properties are reported without any measure of variability. TRIGON's triangle selection is stochastic (Gumbel-Softmax) and depends on training runs, so the diameter, spectral gap, and effective resistance values in Table 1 and Fig. 2 should be accompanied by means and standard deviations over the same number of seeds used for accuracy, with the exact protocol (which epoch's graph is analyzed) stated. This is necessary to support the 'markedly improved structural properties' claim.","section":"Table 1 and Fig. 2"}],"minor_comments":[{"comment":"The notation is inconsistent: the paper first writes diam(G) = Ω(√N), then remarks 'writing diam(G) ∈ Ω(N) indicates...'. The latter should refer to Ω(√N). Please correct.","section":"Section 3.1, Eq. (3)"},{"comment":"The sentence 'classification accuracy improvement exceeding 25% compared to the original graph' is ambiguous (relative vs. absolute improvement). Since several baselines are within a few points of TRIGON, please state whether 25% is relative or absolute and give the supporting numbers.","section":"Section 5.3"},{"comment":"The ablation plots do not show error bars or significance information. Given the small accuracy differences in some panels (e.g., Cora), please add runs/error bars or state that differences are within noise.","section":"Figures 4 and 5"},{"comment":"There are several typographical issues in the bibliography (e.g., 'Fan rk chung' in [48], duplicated [12]/[13]). Please clean up the reference list.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The label-leakage issue in Lcontr is the most serious threat to the paper's main claim. If the authors can rerun with a train-only version of Lcontr and the 9/10 result holds, the paper is likely acceptable after revision. The JDR discrepancy between Tables 2 and 3 should also be checked carefully, as it raises doubts about the baseline reporting. I would ask the editor to request the revised experiments before making a final decision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a good idea with a probable experimental leak. TRIGON selects triangles from the original graph, a k-NN graph, and a Delaunay triangulation, using a Gumbel-Softmax selector, then rebuilds the graph from the selected triangles. That is a natural extension of the authors' own Delaunay rewiring, and I'm not aware of prior work doing learned triangle selection. The ablation checks (random selection vs. learned selection, removing each loss term) are the right kind of experiment, and the code is public. So there is real substance here.\n\nThe problem is Lcontr. It defines a binary triangle label from whether any two of the three nodes share a class label, and it sums over all candidate triangles T. Unlike LGNN and Lpart, which explicitly average over Vtrain, Lcontr has no training mask. With a 60/20/20 split, the selector is trained with validation and test labels. Since the selected triangles determine the graph topology fed to the GNN, test labels leak into the training process through the structure. That is not a minor detail; it can plausibly account for a large share of the reported gains over DR and JDR, which do not peek at test labels. The 'joint optimization' claim is also too strong: the selector receives no gradient from the classification loss, because the graph is reconstructed by thresholding p at 0.5, so only the auxiliary losses train it.\n\nThe other issues are minor by comparison. Table 1 and Figure 2 have no error bars despite Gumbel-Softmax stochasticity, and the paper does not say whether baselines were re-tuned on the same splits. On the positive side, the theory (effective resistance bound for triangles, planar spectral gap limits) is used correctly to motivate non-planar rewiring, and the paper is readable.\n\nBottom line: the core empirical claim is not trustworthy until Lcontr is masked to training nodes and the experiments are re-run. I would still send this to peer review, because the flaw is fixable and the idea deserves referee time; but I'd ask reviewers to demand that re-run before accepting.","headline":"Likely label leakage in the contrastive loss undermines the headline results, but the triangle-selection idea is worth a closer look.","tokens_in":28378,"tokens_out":3435,"would_cite":false,"duration_ms":35421,"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":"A new rewiring method, TRIGON, learns which triangles to add to a graph and beats eight baselines on 9 of 10 node-classification benchmarks.","keywords":["graph neural networks","graph rewiring","triangle selection","oversquashing","oversmoothing","heterophily","node classification","Delaunay triangulation"],"falsifier":"On a held-out heterophilic benchmark, run TRIGON against a variant whose candidate triangle set also includes triangles from the 2-hop or random-walk closure of the original graph; if the enlarged candidate set lifts accuracy by a non-trivial margin, or if TRIGON no longer beats random selection of the same number of triangles, the claim that the three fixed views supply all useful rewiring vocabulary fails.","tokens_in":27483,"feed_emoji":"🔺","tokens_out":5712,"duration_ms":49025,"temperature":0.7,"pith_summary":"This paper tries to establish that the best way to rewire a graph for a message-passing GNN is to learn which triples of nodes, or triangles, deserve to be connected, rather than to fix edges by a static rule. The proposed method, TRIGON, collects candidate triangles from the original graph, a feature-based k-nearest-neighbor graph, and a Delaunay triangulation, scores each triangle with a learned encoder, and selects a subset through a differentiable Gumbel-Softmax gate while jointly training the downstream classifier. On ten node-classification benchmarks spanning homophilic and heterophilic regimes, and with both GCN and GAT backbones, TRIGON reports the best accuracy on nine of them, with structural diagnostics showing lower effective resistance on critical edges, smaller diameter, and a larger spectral gap than existing rewiring methods. The finding matters because it suggests that oversquashing and oversmoothing can be addressed at the level of which higher-order motifs to add, not only which individual edges to add or remove.","feed_headline":"Learn to pick triangles and rewired graphs win 9 of 10 benchmarks","feed_subtitle":"A learned triangle gate rewires graphs with non-planar shortcuts, improving GNN accuracy on nine of ten benchmarks.","key_machinery":"The central object is the candidate triangle set and the differentiable selection gate. Each triangle is represented by concatenated node features, embedded by a shared MLP, scored by a second MLP into binary logits, then relaxed with Gumbel-Softmax; selected triangles' edges form the rewired graph. Its work is to convert graph rewiring from a heuristic edge-edit problem into a learned higher-order motif-selection problem in which structural objectives (resistance, diameter, spectral gap, class balance) are optimized together with classification.","core_discovery":"The central claim is that a graph rewired by task-selected triangles is structurally better for GNN message passing than graphs rewired by curvature, spectral, diffusion, or static triangulation heuristics. TRIGON scores each candidate triangle—drawn from three complementary views: existing edges, feature-space proximity via k-NN, and Delaunay triangulation of learned embeddings—and keeps those whose selection helps classification, using Gumbel-Softmax to make the choice differentiable. The selected triangles are reassembled into a new edge set at every training step, so the topology co-evolves with the GNN. The paper supports the claim with an upper bound on effective resistance in terms of","pith_inferences":["The same triangle-selection gate could be reused for link prediction or graph generation: a model that already learns which triples are task-relevant can emit them as predicted higher-order structure. This is an extension, not something the paper tests.","Because Delaunay triangles in the paper are computed over learned embeddings, a natural variant is to rebuild the k-NN view from current embeddings too, instead of only raw features; the paper's dynamic argument suggests this could further enlarge the useful candidate set.","The effective-resistance bound suggests a cheap ablation: count triangles per edge in the final rewired graph and correlate that count with per-edge resistance; if the correlation is weak, the selection losses, not the triangle count, are doing the work.","The method's ceiling is set by the three fixed candidate views; on graphs where useful shortcuts are non-local in both topology and feature space, adding a fourth view (e.g., random-walk proximity or spectral embedding coordinates) would directly test that ceiling."],"forward_implications":["Rewiring can be formulated as learning over triples rather than pairs, so any method that ranks missing edges can be upgraded to rank the triangles that contain them.","Because the rewired graph is rebuilt every epoch, the topology adapts as embeddings change; this dynamic property is what lets the method preserve discriminability at much greater depth.","Adding non-local triangles is enough to improve global connectivity: diameter drops and spectral gap rises on all datasets tested, so shortcuts between distant nodes are a sufficient mechanism for better propagation.","The gains transfer across backbone architectures: a standard GCN or GAT benefits without changing the message-passing rule.","Features are essential: ablating k-NN or original-graph triangles hurts, so rewiring should use both topology and feature views."],"supporting_citations":[{"why":"Supplies Delaunay triangulation as the feature-based candidate view and the DR baseline that TRIGON must beat.","marker":"[2]"},{"why":"Gumbel-Softmax is the mechanism that makes discrete triangle selection differentiable.","marker":"[31]"},{"why":"Gives the effective-resistance upper bound in terms of triangle count that motivates triangle-based rewiring.","marker":"[53]"},{"why":"Defines balanced Forman-Ricci curvature and the SDRF baseline; its 4-cycle analysis motivates non-planarity.","marker":"[55]"},{"why":"Defines effective-resistance rewiring (GTR) and supplies the notion of high-resistance edges used in diagnostics.","marker":"[7]"},{"why":"Identifies oversquashing as the bottleneck problem and supplies the FA baseline.","marker":"[1]"},{"why":"First-order spectral rewiring baseline FOSR, the nearest spectral-gap competitor.","marker":"[33]"},{"why":"Joint rewiring and denoising method JDR, the strongest non-Delaunay baseline on several datasets.","marker":"[36]"},{"why":"GCN backbone used in the main experiments.","marker":"[34]"},{"why":"GAT backbone used in the main experiments.","marker":"[56]"}],"fun_headline_variants":["Triangles picked for GNNs beat curvature rewiring on 9 of 10","TRIGON rewires graphs with learned triangles, wins 9 of 10 tasks","GNN rewiring via learned triangle gates tops benchmarks","Select triangles, not curvature: TRIGON rewires for GNN wins","Non-planar triangle rewiring improves GNNs on 9 of 10 benchmarks"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"For TRIGON to find a useful shortcut, that shortcut must already be an edge of at least one candidate triangle in the union of three starting views; if the only triangles that would help a given graph lie outside those views, TRIGON cannot create them.","fun_headline_variants_meta":{"raw":{"variants":["Triangles picked for GNNs beat curvature rewiring on 9 of 10","TRIGON rewires graphs with learned triangles, wins 9 of 10 tasks","GNN rewiring via learned triangle gates tops benchmarks","Select triangles, not curvature: TRIGON rewires for GNN wins","Non-planar triangle rewiring improves GNNs on 9 of 10 benchmarks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000162,"raw_usage":{"total_tokens":1040,"prompt_tokens":673,"completion_tokens":367,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":417,"completion_tokens_details":{"reasoning_tokens":265}},"tokens_in":417,"tokens_out":367,"duration_ms":4128,"temperature":1.0,"reasoning_tokens":265,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T15:56:38.829918+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a held-out heterophilic benchmark, run TRIGON against a variant whose candidate triangle set also includes triangles from the 2-hop or random-walk closure of the original graph; if the enlarged candidate set lifts accuracy by a non-trivial margin, or if TRIGON no longer beats random selection of the same number of triangles, the claim that the three fixed views supply all useful rewiring vocabulary fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Delaunay triangulation as the feature-based candidate view and the DR baseline that TRIGON must beat."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the effective-resistance upper bound in terms of triangle count that motivates triangle-based rewiring."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines balanced Forman-Ricci curvature and the SDRF baseline; its 4-cycle analysis motivates non-planarity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines effective-resistance rewiring (GTR) and supplies the notion of high-resistance edges used in diagnostics."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Identifies oversquashing as the bottleneck problem and supplies the FA baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"First-order spectral rewiring baseline FOSR, the nearest spectral-gap competitor."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Joint rewiring and denoising method JDR, the strongest non-Delaunay baseline on several datasets."},{"cited_title":"Kipf and Max Welling","cited_arxiv_id":null,"evidence_quote":"GCN backbone used in the main experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GAT backbone used in the main experiments."}],"review_version":1}