REVIEW 4 major objections 5 minor 31 references
Graph Structure Learning with Bi-level Optimization
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read A two-level optimization that fits each edge with its own learnable strength improves node classification over local attention and noise-detection baselines.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section 3.2, Algorithm 1] 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.
- [Table 1, Section 4.2] 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 4.2 and Tables 1-2] 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 3.2 and Section 4] 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.
minor comments (5)
- [Algorithm 1, line 4] 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).
- [Algorithm 1, line 2] The initialization line reads 'Initialize W and Z2', which appears to be a typo for 'Z' (or 'Z^0'); please correct it.
- [Throughout] 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.
- [References] 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.
- [Appendices] 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.
Circularity Check
No significant circularity: the central bi-level structure-learning claim is empirically validated against external baselines and does not reduce to its own inputs.
full rationale
The paper's central claim is that optimizing an edge-strength matrix Z through a bi-level objective with a validation-loss outer loop improves node classification. This claim is tested against external baselines (GCN, GAT, GraphSAGE, JK-Net, AdaEdge, DropEdge, GAUG, BGCN, VGCN, PTDNet, MAGNA) on four real-world datasets, so the result is not derived from itself. The bi-level formulation in Eqs. (2) and (3) is a standard mathematical definition: the outer objective depends on the inner optimizer's solution, and the inner objective is a supervised training loss; neither is defined in terms of the reported test accuracy. Using a validation set for the outer optimization is a training/model-selection procedure, not a 'prediction' of the validation labels masquerading as a result. The numerous self-citations (Yin et al.) appear in related-work and motivation contexts and are not load-bearing for the main derivation. The asserted role of 'global information' in the common parameters is an interpretive argument rather than a circular step, since the paper does not define that global information in terms of the learned structure or the experimental outcome. The main technical concern, that Algorithm 1's reverse-mode initialization may not compute the exact gradient of Eq. (2), is a correctness issue and not a circularity: even if the printed pseudocode is flawed, the claim would be wrong or unverified rather than tautological. Therefore no specific reduction of a claimed prediction to its inputs is exhibited, and the paper is not circular.
Assumptions & free parameters
free parameters (4)
- inner optimization steps tau =
searched over [5,10,15,20,25]
- regularization coefficient lambda =
5e-4
- inner and outer learning rates =
0.01
- dropout ratio =
0.5
assumptions (4)
- domain assumption Validation loss is an unbiased proxy for the ideal global classification objective.
- domain assumption The form sigma(Z) elementwise multiplied with A, with sigma clipped to [0,1], is expressive enough to capture beneficial connection strengths.
- standard math Unrolled differentiation of W through tau inner gradient descent steps gives a correct gradient for Z.
- domain assumption Early stopping prevents overfitting of Z to the validation set.
Cite this review
Pith. "Pith review of Graph Structure Learning with Bi-level Optimization." pith.science (2026). https://pith.science/paper/XD3FBT5H
@misc{pith2026241117062,
author = {Pith},
title = {Pith review of: Graph Structure Learning with Bi-level Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/XD3FBT5H}},
note = {Machine review of arXiv:2411.17062}
}
read the original abstract
Currently, most Graph Structure Learning (GSL) methods, as a means of learning graph structure, improve the robustness of GNN merely from a local view by considering the local information related to each edge and indiscriminately applying the mechanism across edges, which may suffer from the local structure heterogeneity of the graph (\ie the uneven distribution of inter-class connections over nodes). To overcome the cons, we extract the graph structure as a learnable parameter and jointly learn the structure and common parameters of GNN from the global view. Excitingly, the common parameters contain the global information for nodes features mapping, which is also crucial for structure optimization (\ie optimizing the structure relies on global mapping information). Mathematically, we apply a generic structure extractor to abstract the graph structure and transform GNNs in the form of learning structure and common parameters. Then, we model the learning process as a novel bi-level optimization, \ie \textit{Generic Structure Extraction with Bi-level Optimization for Graph Structure Learning (GSEBO)}, which optimizes GNN parameters in the upper level to obtain the global mapping information and graph structure is optimized in the lower level with the global information learned from the upper level. We instantiate the proposed GSEBO on classical GNNs and compare it with the state-of-the-art GSL methods. Extensive experiments validate the effectiveness of the proposed GSEBO on four real-world datasets.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[3]
Forward and reverse gradient-based hyperparameter optimization
[Franceschi et al., 2017] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In ICML,
work page 2017
-
[6]
Semi-supervised learning with graph learning-convolutional networks
[Jiang et al., 2019] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning-convolutional networks. In CVPR,
work page 2019
-
[7]
A survey of graph neural net- works in real world: Imbalance, noise, privacy and ood challenges
[Ju et al., 2024] Wei Ju, Siyu Yi, Yifan Wang, Zhiping Xiao, Zhengyang Mao, Hourun Li, Yiyang Gu, Yifang Qin, Nan Yin, Senzhang Wang, et al. A survey of graph neural net- works in real world: Imbalance, noise, privacy and ood challenges. arXiv preprint arXiv:2403.04468,
arXiv 2024
-
[9]
[Kingma and Ba, 2015] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980,
arXiv 2015
-
[11]
Understanding attention and gen- eralization in graph neural networks
[Knyazev et al., 2019] Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and gen- eralization in graph neural networks. In NeurIPS,
work page 2019
-
[12]
Adaptive graph convolutional neural net- works
[Li et al., 2018] Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural net- works. In AAAI,
work page 2018
-
[15]
[McPherson et al., 2001] M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a feather: Homophily in social net- works. Review of Sociology, 27:415–444,
work page 2001
-
[19]
The graph neural network model
[Scarselli et al., 2009] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61–80,
work page 2009
Show all 31 references
-
[21]
Graph Attention Networks
[Veliˇckovi´c et al., 2018] Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li `o, and Yoshua Bengio. Graph Attention Networks. In ICLR,
2018
-
[22]
Learn- ing node representations from noisy graph structures
[Wang et al., 2020] Junshan Wang, Ziyao Li, Qingqing Long, Weiyu Zhang, Guojie Song, and Chuan Shi. Learn- ing node representations from noisy graph structures. In ICDM,
2020
-
[23]
Multi-hop attention graph neu- ral network
[Wang et al., 2021] Guangtao Wang, Zhitao Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neu- ral network. In IJCAI,
2021
-
[24]
Demo- net: Degree-specific graph neural networks for node and graph classification
[Wu et al., 2019] Jun Wu, Jingrui He, and Jiejun Xu. Demo- net: Degree-specific graph neural networks for node and graph classification. In KDD,
2019
-
[25]
Graph information bottleneck
[Wu et al., 2020] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. In NeurIPS,
2020
-
[26]
Representation learning on graphs with jumping knowledge networks
[Xu et al., 2018] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML,
2018
-
[27]
Sport: A subgraph perspective on graph classification with label noise
[Yin et al., ] Nan Yin, Li Shen, Chong Chen, Xian-Sheng Hua, and Xiao Luo. Sport: A subgraph perspective on graph classification with label noise. ACM Transactions on Knowledge Discovery from Data. [Yin et al., 2022a] Nan Yin, Fuli Feng, Zhigang Luo, Xiang Zhang, Wenjie Wang, ...
2022
-
[28]
Continuous spiking graph neural networks
[Yin et al., 2024a] Nan Yin, Mengzhu Wan, Li Shen, Hitesh Laxmichand Patel, Baopu Li, Bin Gu, and Huan Xiong. Continuous spiking graph neural networks. arXiv preprint arXiv:2404.01897,
-
[29]
Bayesian graph con- volutional neural networks for semi-supervised classifica- tion
[Zhang et al., 2019] Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph con- volutional neural networks for semi-supervised classifica- tion. In AAAI,
2019
-
[30]
Sen, and L
[Zhao et al., 2006] Binglei Zhao, P. Sen, and L. Getoor. En- tity and relationship labeling in affiliation networks. In ICML Workshop,
2006
-
[31]
Robust graph representation learning via neural sparsification
[Zheng et al., 2020] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In ICML, 2020
2020
-
[2001]
Faloutsos
[Pandit et al., 2007] Shashank Pandit, Duen Horng Chau, Samuel Wang, and C. Faloutsos. Netprobe: a fast and scal- able system for fraud detection in online auction networks. In WWW,
2007
-
[2007]
Sa-gda: Spectral augmen- tation for graph domain adaptation
[Pang et al., 2023] Jinhui Pang, Zixuan Wang, Jiliang Tang, Mingyan Xiao, and Nan Yin. Sa-gda: Spectral augmen- tation for graph domain adaptation. In Proceedings of the 31st ACM International Conference on Multimedia, pages 309–318,
2023
-
[2009]
Adversarial representation with intra-modal and inter-modal graph contrastive learning for multimodal emotion recognition
[Shou et al., 2023] Yuntao Shou, Tao Meng, Wei Ai, Nan Yin, and Keqin Li. Adversarial representation with intra-modal and inter-modal graph contrastive learning for multimodal emotion recognition. arXiv preprint arXiv:2312.16778,
2023 arXiv
-
[2012]
Variational inference for graph convolutional networks in the absence of graph data and adversarial set- tings
[Elinas et al., 2020] Pantelis Elinas, Edwin V Bonilla, and Louis Tiao. Variational inference for graph convolutional networks in the absence of graph data and adversarial set- tings. In NeurIPS,
2020
-
[2015]
Kipf and Max Welling
[Kipf and Welling, 2017] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR,
2017
-
[2017]
Learning discrete structures for graph neural networks
[Franceschi et al., 2019] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML,
2019
-
[2018]
Learning to drop: Robust graph neural network via topological denoising
[Luo et al., 2021] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In WSDM,
2021
-
[2019]
Hamilton, Rex Ying, and Jure Leskovec
[Hamilton et al., 2017] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS,
2017
-
[2020]
Generic methods for optimization-based modeling
[Domke, 2012] Justin Domke. Generic methods for optimization-based modeling. In AISTATS,
2012
-
[2021]
Gradient-based hyperparameter optimization through reversible learning
[Maclaurin et al., 2015] Dougal Maclaurin, David Duve- naud, and Ryan Adams. Gradient-based hyperparameter optimization through reversible learning. In ICML,
2015
-
[2023]
Dropedge: Towards deep graph con- volutional networks on node classification
[Rong et al., 2020] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph con- volutional networks on node classification. InICLR,
2020
-
[2024]
Differentiable graph module (dgm) for graph convolutional networks,
[Kazi et al., 2020] Anees Kazi, Luca Cosmo, Nassir Navab, and Michael Bronstein. Differentiable graph module (dgm) for graph convolutional networks,
2020
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.