{"id":"470c2e6f-7fee-49a9-b232-7586eecf39c7","arxiv_id":"2411.17062","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"GSEBO learns edge strengths in graph neural networks via bi-level optimization, using validation loss as the outer objective, and reports improved node classification on four graphs.","lead":"This paper proposes GSEBO, a way to learn edge weights in graph neural networks by optimizing them on a validation set through bi-level optimization. It reports modest accuracy gains over several structure-learning baselines on four datasets, but lacks code and a direct comparison to the most related prior method.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 as printed may not compute the gradient of Eq. (2): the reverse-mode adjoint is initialized with the Z-gradient rather than the W-gradient, so the claimed outer update is not the gradient of the stated objective.","rationale":"The central claim is that validation-driven bi-level optimization of edge strengths improves node classification. That requires the algorithm in Section 3.2 to optimize Eq. (2). The Algorithm 1 pseudocode appears to initialize the reverse-mode adjoint with the Z-gradient rather than the W-gradient, making the subsequent chain-rule products invalid. If this is not a typo, the reported results are not evidence for the proposed method; they are evidence for some other update. This is more load-bearing than the reader's validation-overfitting concern: even a perfectly representative validation set would not save a method that does not compute the stated objective. The lack of code and the placement of the derivation in an unavailable appendix make the issue impossible to verify from the preprint. If Appendix B has the correct grad_W initialization, the concern reduces to a fixable typo; if not, the main algorithmic contribution is unsubstantiated. I thus keep the verdict conditional, with the condition being a corrected, verified gradient computation. The reader's weakest assumption (validation loss as proxy) is related but secondary; the algorithmic gradient check should come first.","tokens_in":125,"tokens_out":14112,"duration_ms":258792,"concrete_test":"Reimplement Algorithm 1 verbatim on a small graph (e.g., Cora's 140/500/1000 split or a synthetic 100-node graph) and compare the resulting outer update P against a finite-difference estimate of d/dZ of Eq. (2). If P and the finite-difference gradient disagree, the published algorithm does not optimize the claimed objective. Alternatively, check the Appendix B derivation: if alpha_tau is initialized as grad_{W^tau} F, the issue is a pseudocode typo; if it is initialized as grad_Z F, the method should be rejected as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2's Algorithm 1 does not, as printed, compute the gradient of the outer objective Eq. (2). Line 6 initializes alpha_tau = grad_Z sum_{v in Vval} l(f(A,X)_v, y_v; W^tau), i.e. the derivative of the validation loss with respect to the structure matrix Z. The reverse-mode recursion then sets alpha_t = alpha_{t+1} partial W^{t+1} / partial W^t and accumulates P += alpha_{t+1} partial W^{t+1} / partial Z. This recursion is only valid if alpha_t is the adjoint of the loss with respect to the inner parameters W^t (a vector in W-space); with alpha_tau being a Z-space gradient, the products are dimensionally incompatible and the final P is not dF/dZ of Eq. (2). The manuscript defers the derivation to Appendix B and provides no code, so this cannot be dismissed as a typo without checking. If the appendix or code initializes alpha_tau as grad_{W^tau} F, the pseudocode must be corrected; if it initializes as grad_Z F, the experiments solve a different optimization than the claimed bi-level structure learning.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GSEBO, a graph structure learning method that represents edge connection strengths as a learnable matrix Z and optimizes it together with GNN weights W through a bi-level formulation: an inner loop trains W on the labeled training nodes, and an outer loop updates Z by minimizing a validation loss. The method is instantiated on GCN, GAT, GraphSAGE, and JK-Net and evaluated on Cora, Citeseer, Terrorist, and Air-USA against several GSL baselines, including a synthetic robustness study with added inter-class edges. The stated motivation is to replace local, edge-sharing structure learning with a global, edge-specific objective.","tokens_in":12567,"tokens_out":6477,"duration_ms":59004,"significance":"If the bi-level derivation were correct and the empirical gains were robust, GSEBO would be a useful addition to the GSL literature: the generic structure extractor is a clean way to parameterize edge strengths, and the idea of optimizing structure on a validation objective is worth exploring. The paper also has strengths: it evaluates against external baselines rather than only self-comparisons, covers four GNN backbones, and includes a robustness analysis under synthetic noise. However, the central training algorithm as printed is dimensionally inconsistent and does not compute the gradient of the stated objective; no code or appendix is available to resolve the discrepancy. Several empirical claims are also stronger than the confidence intervals justify. These issues currently prevent the paper from being accepted.","major_comments":[{"comment":"Algorithm 1 does not, as printed, compute the gradient of the outer objective in Eq. (2). Line 6 sets alpha_tau = grad_Z of the validation loss, but the reverse-mode recursion in lines 9-11 treats alpha as an adjoint in W-space: alpha_t = alpha_{t+1} * (partial W^{t+1} / partial W^t), and P accumulates alpha_{t+1} * (partial W^{t+1} / partial Z). Unless the dimensions of W and Z coincide, the products are undefined; more fundamentally, the direct dependence of F on Z in the forward model f(A,X; W^tau, Z) is never accumulated. The text defers the derivation to Appendix B, but that appendix is not present in the reviewed version, and no code is provided. The initialization must be alpha_tau = grad_{W^tau} F (with P initialized by the direct grad_Z term), or the experiments solve a different optimization than the claimed bi-level structure learning. This is load-bearing and must be fixed and verified.","section":"Section 3.2, Algorithm 1"},{"comment":"The text states that 'GSEBO achieves better performance than the vanilla version in all cases', but Table 1 contains a counterexample: for GraphSAGE on Cora, GSEBO reports 80.4 ± 0.9 while Vanilla reports 81.3 ± 0.5. The reported per-architecture average improvements (4.2%, 4.4%, 4.0%, 5.74%) appear to be per-dataset relative improvements averaged, which is not stated; if a different aggregation is used it should be specified. The claim of universal improvement over vanilla backbones is not supported by the table as presented.","section":"Table 1, Section 4.2"},{"comment":"Several of the headline improvements are within one standard deviation of the baseline or of a competing method. For example, on Cora with GCN, GSEBO (84.0 ± 0.4) vs. GAUG (83.2 ± 0.7) and vs. PTDNet (82.8 ± 2.6); on GAT with Terrorist, GSEBO (69.7 ± 1.6) vs. DropEdge (69.9 ± 1.1) is not an improvement. No significance tests or effect-size measures are reported. The conclusion that GSEBO 'outperforms the baselines in most cases' is too strong without statistical support, especially for the small-margin results.","section":"Section 4.2 and Tables 1-2"},{"comment":"The central motivation is that validation loss approximates the ideal global objective and that the common parameters W carry 'global information' useful for structure optimization. The paper asserts this but provides no theoretical analysis or ablation in the main text; Figure 3 and Appendices C-E are referenced but are not available in the reviewed version. Because the method tunes Z on a validation set, the risk of overfitting the validation split and the degree to which the learned structure transfers to test nodes must be addressed explicitly. At minimum, the deferred appendices need to be included and the claims supported by validation/test gap measurements or a sensitivity analysis over split choices.","section":"Section 3.2 and Section 4"}],"minor_comments":[{"comment":"Line 4 says 'Update W w.r.t. Eq. (1)', but the inner objective is defined in Eq. (3); Algorithm 1 should refer to Eq. (3).","section":"Algorithm 1, line 4"},{"comment":"The initialization line reads 'Initialize W and Z2', which appears to be a typo for 'Z' (or 'Z^0'); please correct it.","section":"Algorithm 1, line 2"},{"comment":"There are several typographical and copy-editing issues: 'Tabel' should be 'Table', 'mehtods' should be 'methods', 'a a universal' should be 'a universal', and 'cons' is informal.","section":"Throughout"},{"comment":"The reference list contains many self-citations, including some to unpublished or tangential works; please ensure each citation is necessary and relevant to the corresponding claim.","section":"References"},{"comment":"The paper repeatedly refers to Appendices B-F for the gradient derivation, convergence discussion, and additional experiments, but these appendices are not included in the arXiv v1 text. All appendices referenced in the main body must be included in the submitted version.","section":"Appendices"}],"recommendation":"major_revision","confidential_remarks":"The key issue is the Algorithm 1 gradient computation. If the actual implementation follows the printed pseudocode, the experiments may not be optimizing Eq. (2); if it follows a corrected derivation, the pseudocode needs to be fixed. I strongly recommend asking the authors for the code and the missing appendices before any final decision. The empirical section also needs a significance analysis, and the statement that GSEBO beats vanilla in all cases is directly contradicted by the GraphSAGE/Cora row. The paper is not ready in its current form, but the core idea is plausible enough to warrant a major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is LDS with per-edge scalar strengths instead of N^2 sampled distributions. That is a legitimate incremental idea, and the paper does some things well: the structure extractor is simple and applicable to GCN, GAT, GraphSAGE, and JK-Net; the synthetic-noise robustness experiments are useful; and the authors state the scalability limitation up front. The framing about a \"global view\" is asserted rather than demonstrated, but the core motivation is not crazy.\n\nThe soft spots are substantial. First, Algorithm 1 as printed does not compute the gradient of Eq. (2). Line 6 sets alpha_tau = grad_Z of the validation loss, then the reverse loop multiplies alpha by dW^{t+1}/dW^t and accumulates against dW^{t+1}/dZ. That recursion only works if alpha_tau is the gradient with respect to W^tau; initialized with a Z-gradient, the dimensions do not match. The derivation is deferred to Appendix B, and no appendix is included in the arXiv version. No code is provided. So the experiments may be solving a different optimization problem than the one claimed. This is not a cosmetic issue.\n\nSecond, the most relevant baseline, LDS, is cited in related work but never run. Since GSEBO is essentially a boundary modification of LDS, omitting it makes the comparison incomplete.\n\nThird, some experimental claims overreach. GSEBO on GraphSAGE/Cora is worse than vanilla (80.4 vs 81.3), which contradicts the claim that GSEBO beats vanilla in all cases, and several reported gains are within one standard deviation. The appendices that are supposed to contain ablation and inter-class analysis are also missing.\n\nIf a corrected derivation and code appear, this could be a reasonable short paper for a GSL audience. As printed, I would not send it to a serious referee: the central algorithm is unverifiable and the one baseline that would calibrate the contribution is absent. Desk reject with an invitation to resubmit after fixing these issues.","headline":"A reasonable incremental extension of LDS, but as printed the core algorithm does not compute the stated gradient and the derivation lives in a missing appendix.","tokens_in":13000,"tokens_out":4132,"would_cite":false,"duration_ms":40572,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-level optimization that fits each edge with its own learnable strength improves node classification over local attention and noise-detection baselines.","keywords":["graph structure learning","bi-level optimization","graph neural networks","node classification","edge strength learning","validation loss","graph robustness","generic structure extractor"],"falsifier":"Run GSEBO on Cora with two different validation splits of equal size drawn from opposite regions of the graph, keeping all hyperparameters fixed. If test accuracy shifts by more than a few points or the learned edge weights $\\sigma(Z)$ differ substantially on shared edges, the claim that validation loss approximates the ideal global objective fails a direct test.","tokens_in":12124,"feed_emoji":"📈","tokens_out":7648,"duration_ms":67993,"temperature":0.7,"pith_summary":"Most graph structure learning methods reweight or prune edges using local information, which struggles when different nodes sit in very different local structures. This paper argues that edge strength should instead be a learnable parameter of the model and that it should be optimized globally: first train the GNN's feature-mapping weights on labeled training nodes, then adjust each edge's strength to reduce classification loss on validation nodes. The proposed GSEBO wraps this in a bi-level optimization and applies it to four standard GNN architectures. On Cora, Citeseer, Terrorist, and Air-USA it reports consistent accuracy gains over vanilla GNNs and over established structure-learning baselines, with the largest gains on the densest graph. If correct, the paper shows that global, validation-driven edge learning is a viable route to GNN robustness against inter-class edges.","feed_headline":"Validation-driven edge weights beat graph structure baselines","feed_subtitle":"GSEBO optimizes each edge against a global objective, gaining up to 8% over vanilla GNNs and staying robust under injected noise.","key_machinery":"The generic structure extractor (GSE) turns a graph convolution into a learnable structure: the adjacency matrix $\\tilde{A}$ is multiplied entry-wise by $\\sigma(Z)$, where $Z$ is a parameter matrix of the same shape as $A$ and $\\sigma$ clips values into $[0,1]$. This gives each existing edge its own strength instead of a shared attention or noise-detection mechanism. Around this extractor, the paper builds a bi-level optimization: an inner loop updates the common parameters $W$ (the feature-mapping weights) over training nodes, and an outer loop differentiates through the inner gradient steps to update $Z$ against the validation loss. The load-bearing idea is that $W$ carries global information about the feature-to-label mapping, so optimizing $Z$ with $W$'s global information and a validation objective avoids both the locality of attention methods and the prior assumptions of probabilistic methods.","core_discovery":"The paper's central claim is that the graph structure can be extracted from a GNN as a learnable edge-strength matrix $Z$ and learned together with the network's feature-mapping weights by a two-level process. In the lower level, standard training minimizes the inner loss $L(W,Z)$ over the training nodes to obtain $W^*(Z)$; in the upper level, the graph structure is updated to minimize the validation classification loss $F(W^*(Z))$ over the validation nodes. Because the outer objective is a global classification target rather than a local edge-quality target, the learned edge strengths down-weight harmful inter-class edges while keeping useful connections that local rules would remove. The paper instantiates this generic structure extractor, $\\sigma(Z)\\odot\\tilde{A}$, on GCN, GAT, GraphSAGE, and JK-Net, and reports that GSEBO beats vanilla versions of all four backbones and outperforms GAUG, AdaEdge, DropEdge, BGCN, VGCN, PTDNet, and MAGNA on four datasets, with robustness gains when inter-class edges are injected.","pith_inferences":["I would expect the validation-driven outer loop to carry over to heterophilic graphs, where inter-class edges are the norm rather than noise; the paper's injected-noise experiments point in that direction but do not test it directly.","Because the outer objective uses only validation nodes, I would test how sensitive GSEBO is to the choice and size of the validation split; the authors do not report this, and the claimed gains could narrow under a different split.","The authors note that GSEBO cannot handle large graphs without minibatching and must retrain when new nodes arrive; a sampled or inductive variant would be the natural next step, and the same bi-level gradient machinery should carry over, though the validation-loss approximation would need re-checking under distribution shift.","The large gains on JK-Net point to long-range propagation as the biggest beneficiary of learned edge strengths; varying the number of layers while holding the training budget fixed would isolate that effect."],"forward_implications":["Any graph convolution that can be written with an aggregation step can inherit learnable edge strengths by plugging in the GSE extractor, so the benefit is not tied to one architecture.","On graphs with many inter-class edges, GSEBO's gains over vanilla models grow, so the method offers a robustness route when homophily is weak or the graph is noisy.","Because the outer objective is validation classification rather than edge reconstruction, GSEBO avoids the gap that the paper identifies in earlier bilevel structure learning such as LDS.","The densest dataset (Air-USA) shows the largest average gain, suggesting that learning connection strength matters more as neighborhoods become larger and noisier.","The paper reports empirical convergence and stable losses for GSEBO, with early stopping used because bilevel optimization lacks a convergence guarantee."],"supporting_citations":[{"why":"Supplies the GCN architecture that GSEBO is instantiated on and the Cora/Citeseer data splits used in experiments.","marker":"[Kipf and Welling, 2017]"},{"why":"Supplies the GAT attention baseline; GSEBO's improvement over it supports the claim that global edge learning beats local attention.","marker":"[Veličković et al., 2018]"},{"why":"Supplies the GraphSAGE backbone used for GSEBO instantiation.","marker":"[Hamilton et al., 2017]"},{"why":"Supplies the JK-Net backbone and the observation on local structure heterogeneity that motivates edge-specific modeling.","marker":"[Xu et al., 2018]"},{"why":"Prior bilevel graph structure learning that GSEBO extends, with GSEBO's validation-classification objective positioned against LDS's edge-generation objective.","marker":"[Franceschi et al., 2019]"},{"why":"Provides the bilevel optimization machinery used to differentiate through inner optimization steps.","marker":"[Domke, 2012]"},{"why":"Supplies the reverse-mode gradient-through-training method the outer loop uses to update Z.","marker":"[Maclaurin et al., 2015]"},{"why":"GAUG baseline for data-augmentation-based structure learning, a central comparison in the experiments.","marker":"[Zhao et al., 2021b]"},{"why":"PTDNet baseline and the protocol for injecting inter-class edges in the robustness experiments.","marker":"[Luo et al., 2021]"},{"why":"DropEdge baseline whose failure on noisy synthetic graphs contrasts with GSEBO's robustness.","marker":"[Rong et al., 2020]"}],"fun_headline_variants":["Bi-level optimization learns better graph structures","GSEBO: global edge learning beats local graph rules","Two-level training optimizes graph edges for GNNs","Jointly learn graph structure and weights for GNNs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that minimizing the classification loss on validation nodes is a reliable stand-in for classifying every node, and the authors themselves note that the bilevel optimization cannot guarantee convergence, so an unrepresentative validation set or an early stop can send the learned edge strengths in the wrong direction.","fun_headline_variants_meta":{"raw":{"variants":["Bi-level optimization learns better graph structures","GSEBO: global edge learning beats local graph rules","Two-level training optimizes graph edges for GNNs","Jointly learn graph structure and weights for GNNs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000204,"raw_usage":{"total_tokens":1429,"prompt_tokens":1021,"completion_tokens":408,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":345}},"tokens_in":637,"tokens_out":408,"duration_ms":4816,"temperature":1.0,"reasoning_tokens":345,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:33:27.737031+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run GSEBO on Cora with two different validation splits of equal size drawn from opposite regions of the graph, keeping all hyperparameters fixed. If test accuracy shifts by more than a few points or the learned edge weights $\\sigma(Z)$ differ substantially on shared edges, the claim that validation loss approximates the ideal global objective fails a direct test.","supporting_citations":[{"cited_title":"Hamilton, Rex Ying, and Jure Leskovec","cited_arxiv_id":null,"evidence_quote":"Supplies the GraphSAGE backbone used for GSEBO instantiation."},{"cited_title":"Learning discrete structures for graph neural networks","cited_arxiv_id":null,"evidence_quote":"Prior bilevel graph structure learning that GSEBO extends, with GSEBO's validation-classification objective positioned against LDS's edge-generation objective."},{"cited_title":"Generic methods for optimization-based modeling","cited_arxiv_id":null,"evidence_quote":"Provides the bilevel optimization machinery used to differentiate through inner optimization steps."},{"cited_title":"Gradient-based hyperparameter optimization through reversible learning","cited_arxiv_id":null,"evidence_quote":"Supplies the reverse-mode gradient-through-training method the outer loop uses to update Z."},{"cited_title":"Dropedge: Towards deep graph con- volutional networks on node classification","cited_arxiv_id":null,"evidence_quote":"DropEdge baseline whose failure on noisy synthetic graphs contrasts with GSEBO's robustness."}],"review_version":1}