Implicit Subgraph Neural Network

Yongjian Zhong, Liao Zhu, Hieu Vu, Bijaya Adhikari
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:78602-78615, 2025.

Abstract

Subgraph neural networks have recently gained prominence for various subgraph-level predictive tasks. However, existing methods either 1) apply simple standard pooling over graph convolutional networks, failing to capture essential subgraph properties, or 2) rely on rigid subgraph definitions, leading to suboptimal performance. Moreover, these approaches fail to model long-range dependencies both between and within subgraphs—a critical limitation, as many real-world networks contain subgraphs of varying sizes and connectivity patterns. In this paper, we propose a novel implicit subgraph neural network, the first of its kind, designed to capture dependencies across subgraphs. Our approach also integrates label-aware subgraph-level information. We formulate implicit subgraph learning as a bilevel optimization problem and develop a provably convergent algorithm that requires fewer gradient estimations than standard bilevel optimization methods. We evaluate our approach on real-world networks against state-of-the-art baselines, demonstrating its effectiveness and superiority.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-zhong25g, title = {Implicit Subgraph Neural Network}, author = {Zhong, Yongjian and Zhu, Liao and Vu, Hieu and Adhikari, Bijaya}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {78602--78615}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/zhong25g/zhong25g.pdf}, url = {https://proceedings.mlr.press/v267/zhong25g.html}, abstract = {Subgraph neural networks have recently gained prominence for various subgraph-level predictive tasks. However, existing methods either 1) apply simple standard pooling over graph convolutional networks, failing to capture essential subgraph properties, or 2) rely on rigid subgraph definitions, leading to suboptimal performance. Moreover, these approaches fail to model long-range dependencies both between and within subgraphs—a critical limitation, as many real-world networks contain subgraphs of varying sizes and connectivity patterns. In this paper, we propose a novel implicit subgraph neural network, the first of its kind, designed to capture dependencies across subgraphs. Our approach also integrates label-aware subgraph-level information. We formulate implicit subgraph learning as a bilevel optimization problem and develop a provably convergent algorithm that requires fewer gradient estimations than standard bilevel optimization methods. We evaluate our approach on real-world networks against state-of-the-art baselines, demonstrating its effectiveness and superiority.} }
Endnote
%0 Conference Paper %T Implicit Subgraph Neural Network %A Yongjian Zhong %A Liao Zhu %A Hieu Vu %A Bijaya Adhikari %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-zhong25g %I PMLR %P 78602--78615 %U https://proceedings.mlr.press/v267/zhong25g.html %V 267 %X Subgraph neural networks have recently gained prominence for various subgraph-level predictive tasks. However, existing methods either 1) apply simple standard pooling over graph convolutional networks, failing to capture essential subgraph properties, or 2) rely on rigid subgraph definitions, leading to suboptimal performance. Moreover, these approaches fail to model long-range dependencies both between and within subgraphs—a critical limitation, as many real-world networks contain subgraphs of varying sizes and connectivity patterns. In this paper, we propose a novel implicit subgraph neural network, the first of its kind, designed to capture dependencies across subgraphs. Our approach also integrates label-aware subgraph-level information. We formulate implicit subgraph learning as a bilevel optimization problem and develop a provably convergent algorithm that requires fewer gradient estimations than standard bilevel optimization methods. We evaluate our approach on real-world networks against state-of-the-art baselines, demonstrating its effectiveness and superiority.
APA
Zhong, Y., Zhu, L., Vu, H. & Adhikari, B.. (2025). Implicit Subgraph Neural Network. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:78602-78615 Available from https://proceedings.mlr.press/v267/zhong25g.html.

Related Material