Proceedings

HA-SCN: Learning Hierarchical Aligned Subtree Convolutional Networks for Graph Classification

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3245-3253.

https://doi.org/10.24963/ijcai.2025/361

Abstract

In this paper, we propose a Hierarchical Aligned Subtree Convolutional Network (HA-SCN) for graph classification. Our idea is to transform graphs of arbitrary sizes into fixed-sized aligned graphs and construct a normalized K-layer m-ary subtree for each node in the aligned graphs. By sliding convolutional filters over the entire subtree at each node, we define a novel subtree convolution and pooling operation that hierarchically abstracts node-level information. We demonstrate that the proposed HA-SCN model not only realizes the convolution mechanism similar to the Convolutional Neural Networks (CNNs), which have the characteristics of weight sharing and fixed-sized receptive fields, but also effectively mitigates the over-squashing problem. Meanwhile, it establishes the correspondence information between nodes, alleviating the information loss issue. Experimental results on various benchmark graph datasets show that our approach achieves state-of-the-art performance in graph classification tasks.

  1. [Alon and Yahav, 2021] Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Im- plications. In Proceedings of ICLR, 2021.
  2. [Bai and Hancock, 2014] Lu Bai and Edwin R. Hancock. Depth-Based Complexity Traces of Graphs. PR, pages 1172-1186, 2014.
  3. [Bai et al., 2014] Lu Bai, Luca Rossi, Horst Bunke, and Ed- win R. Hancock. Attributed Graph Kernels Using the Jensen-Tsallis q-Differences. In Proceedings of ECML- PKDD, pages 99-114, 2014.
  4. [Bai et al., 2015] Lu Bai, Luca Rossi, Zhihong Zhang, and Edwin R. Hancock. An Aligned Subtree Kernel for Weighted Graphs. In Proceedings of ICML, pages 30-39, 2015.
  5. [Bai et al., 2019] Lu Bai, Yuhang Jiao, Lixin Cui, and Ed- win R. Hancock. Learning Aligned-Spatial Graph Convo- lutional Networks for Graph Classification. In Proceed- ings of ECML-PKDD, pages 464-482, 2019.
  6. [Bai et al., 2022a] Lu Bai, Lixin Cui, and Edwin R. Han- cock. A Hierarchical Transitive-Aligned Graph Kernel for Un-Attributed Graphs. In Proceedings of ICML, pages 1327-1336, 2022.
  7. [Bai et al., 2022b] Lu Bai, Lixin Cui, Yuhang Jiao, Luca Rossi, and Edwin R. Hancock. Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification. TPAMI, pages 783-798, 2022.
  8. [Bai et al., 2023] Lu Bai, Yuhang Jiao, Lixin Cui, Luca Rossi, Yue Wang, Philip S. Yu, and Edwin R. Hancock. Learning Graph Convolutional Networks Based on Quan- tum Vertex Information Propagation. TKDE, pages 1747- 1760, 2023.
  9. [Bai et al., 2024] Lu Bai, Lixin Cui, Ming Li, Yue Wang, and Edwin Hancock. QBMK: Quantum-based Matching Ker- nels for Un-attributed Graphs. In Proceedings of ICML, pages 2364-2374, 2024.
  10. [Black et al., 2023] Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding Oversquashing in GNNs through the Lens of Effective Resistance. In Pro- ceedings of ICML, pages 2528-2547, 2023.
  11. [Bruna et al., 2013] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral Networks and Lo- cally Connected Networks on Graphs. arXiv preprint arXiv:1312.6203, 2013.
  12. [Chen et al., 2022] Huiyuan Chen, Chin-Chia Michael Yeh, Fei Wang, and Hao Yang. Graph Neural Transport Net- works with Non-Local Attentions for Recommender Sys- tems. In Proceedings of WWW, 2022.
  13. [Cosmo et al., 2024] Luca Cosmo, Giorgia Minello, Alessandro Bicciato, Michael M. Bronstein, Emanuele Rodolà, Luca Rossi, and Andrea Torsello. Graph kernel neural networks. TNNLS, pages 1-14, 2024.
  14. [Cui et al., 2024] Lixin Cui, Lu Bai, Xiao Bai, Yue Wang, and Edwin R. Hancock. Learning Aligned Vertex Convo- lutional Networks for Graph Classification. TNNLS, pages 4423-4437, 2024.
  15. [Dai et al., 2023] Shi Dai, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao. Exposition on Over-Squashing Problem on GNNs: Current Methods, Benchmarks and Challenges. arXiv preprint arXiv: 2311.07073, 2023.
  16. [Defferrard et al., 2016] Michaël Defferrard, Xavier Bres- son, and Pierre Vandergheynst. Convolutional Neural Net- works on Graphs with Fast Localized Spectral Filtering. In Proceedings of NeurIPS, pages 3844-3852, 2016.
  17. [Errica et al., 2020] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. In Proceedings of ICLR, 2020.
  18. [Gartner et al., 2003] Thomas Gartner, Peter A. Flach, and Stefan Wrobel. On Graph Kernels: Hardness Results and Efficient Alternatives. In Proceedings of COLT, pages 129-143, 2003.
  19. [Hamilton et al., 2017] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In Proceedings of NeurIPS, pages 1025- 1035, 2017.
  20. [Jing et al., 2021] Bowen Jing, Stephan Eismann, Pratham N. Soni, and Ron O. Dror. Equivariant Graph Neural Networks for 3D Macromolecular Structure. arXiv preprint arXiv:2106.03843, 2021.
  21. [Karhadkar et al., 2023] Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. FoSR: First-Order Spec- tral Rewiring for Addressing Oversquashing in GNNs. In Proceedings of ICLR, 2023.
  22. [Kingma and Ba, 2014] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. arXiv preprint arXiv:1412.6980, 2014.
  23. [Kipf and Welling, 2017] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of ICLR, 2017.
  24. [McAuley and Leskovec, 2012] Julian McAuley and Jure Leskovec. Learning to Discover Social Circles in Ego Net- works. In Proceedings of NeurIPS, pages 539-547, 2012.
  25. [Min et al., 2021] Shengjie Min, Zhan Gao, Jing Peng, Liang Wang, Ke Qin, and Bo Fang. STGSN -a Spatial-Temporal Graph Neural Network Framework for Time-Evolving Social Networks. KBS, 2021.
  26. [Niepert et al., 2016] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning Convolutional Neu- ral Networks for Graphs. In Proceedings of ICML, page 2014-2023, 2016.
  27. [Nikolentzos and Vazirgiannis, 2020] Giannis Nikolent- zos and Michalis Vazirgiannis. Random Walk Graph Neural Networks. In Proceedings of NeurIPS, pages 16211-16222, 2020.
  28. [Shervashidze et al., 2009] Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient Graphlet Kernels for Large Graph Comparison. In Proceedings of AISTATS, pages 488-495, 2009.
  29. [Shervashidze et al., 2011] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman Graph Kernels. JMLR, pages 2539-2561, 2011.
  30. [Simonovsky and Komodakis, 2017] Martin Simonovsky and Nikos Komodakis. Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs. In Proceedings of CVPR, pages 29-38, 2017.
  31. [Singh, 2023] Akansha Singh. Over-Squashing in Graph Neural Networks: A Comprehensive Survey. arXiv preprint arXiv: 2308.15568, 2023.
  32. [Topping et al., 2022] Jake Topping, Francesco Di Gio- vanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding Over-Squashing and Bottlenecks on Graphs via Curvature. In Proceedings of ICLR, 2022.
  33. [Wang et al., 2023] Yu Wang, Yuying Zhao, Yi Zhang, and Tyler Derr. Collaboration-Aware Graph Convolutional Networks for Recommendation Systems. In Proceedings of WWW, pages 91-101, 2023.
  34. [Witten et al., 2011] Ian H. Witten, Eibe Frank, and Mark A. Hall. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Publishers Inc., 3rd edition, 2011.
  35. [Wu et al., 2021] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A Com- prehensive Survey on Graph Neural Networks. TNNLS, pages 4-24, 2021.
  36. [Xu et al., 2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Net- works? In Proceedings of ICLR, 2019.
  37. [Xu et al., 2021] Lixiang Xu, Lu Bai, Xiaoyi Jiang, Ming Tan, Daoqiang Zhang, and Bin Luo. Deep Rényi Entropy Graph Kernel. PR, 2021.
  38. [Yan et al., 2023] Yujun Yan, Gao Li, and Danai Koutra. Size Generalizability of Graph Neural Networks on Bio- logical Data: Insights and Practices from the Spectral Per- spective. arXiv preprint arXiv:2305.15611, 2023.
  39. [Yanardag and Vishwanathan, 2015] Pinar Yanardag and S.V.N. Vishwanathan. Deep Graph Kernels. In Proceed- ings of KDD, pages 1365-1374, 2015.
  40. [Ying et al., 2018] Rex Ying, Jiaxuan You, Christopher Mor- ris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical Graph Representation Learning with Dif- ferentiable Pooling. In Proceedings of NeurIPS, page 4805-4815, 2018.
  41. [Zhang et al., 2019] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An End-to-End Deep Learn- ing Architecture for Graph Classification. In Proceedings of AAAI, pages 4438-4445, 2019.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards