research-article

Search to Capture Long-range Dependency with Stacking GNNs for Graph Classification

Authors:

Quanming YaoAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 588 - 598

https://doi.org/10.1145/3543507.3583486

Published: 30 April 2023 Publication History

Abstract

In recent years, Graph Neural Networks (GNNs) have been popular in the graph classification task. Currently, shallow GNNs are more common due to the well-known over-smoothing problem facing deeper GNNs. However, they are sub-optimal without utilizing the information from distant nodes, i.e., the long-range dependencies. The mainstream methods in the graph classification task can extract the long-range dependencies either by designing the pooling operations or incorporating the higher-order neighbors, while they have evident drawbacks by modifying the original graph structure, which may result in information loss in graph structure learning. In this paper, by justifying the smaller influence of the over-smoothing problem in the graph classification task, we evoke the importance of stacking-based GNNs and then employ them to capture the long-range dependencies without modifying the original graph structure. To achieve this, two design needs are given for stacking-based GNNs, i.e., sufficient model depth and adaptive skip-connection schemes. By transforming the two design needs into designing data-specific inter-layer connections, we propose a novel approach with the help of neural architecture search (NAS), which is dubbed LRGNN (Long-Range Graph Neural Networks). Extensive experiments on five datasets show that the proposed LRGNN can achieve the best performance, and obtained data-specific GNNs with different depth and skip-connection schemes, which can better capture the long-range dependencies. 1

References

[1]

Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML. 21–29.

[2]

Uri Alon and Eran Yahav. 2021. On the bottleneck of graph neural networks and its practical implications. ICLR (2021).

[3]

Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. 2020. Spectral clustering with graph neural networks for graph pooling. In ICML. 874–883.

[4]

Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and deep graph convolutional networks. In ICML. 1725–1735.

[5]

Paul D Dobson and Andrew J Doig. 2003. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology (JMB) 330, 4 (2003), 771–783.

[6]

Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. 2022. Long Range Graph Benchmark. arXiv preprint arXiv:2206.08164 (2022).

[7]

Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. 2020. A fair comparison of graph neural networks for graph classification. ICLR.

[8]

Guosheng Feng, Chunnan Wang, and Hongzhi Wang. 2021. Search For Deep Graph Neural Networks. arXiv preprint arXiv:2109.10047 (2021).

[9]

Hongyang Gao and Shuiwang Ji. 2019. Graph u-nets. ICML, 2083–2092.

[10]

Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. 2020. Graphnas: Graph neural architecture search with reinforcement learning. In IJCAI.

[11]

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural Message Passing for Quantum Chemistry. In ICML. 1263–1272.

[12]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS. 1024–1034.

[13]

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In CVPR. 770–778.

[14]

Paras Jain, Zhanghao Wu, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. 2021. Representing Long-Range Context for Graph Neural Networks with Global Attention. NeurIPS 34 (2021).

[15]

Shengli Jiang and Prasanna Balaprakash. 2020. Graph neural network architecture search for molecular property prediction. In 2020 IEEE International Conference on Big Data (Big Data). IEEE, 1346–1353.

[16]

Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. ICLR (2016).

[17]

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. NIPS (2012).

[18]

Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. 2020. Policy-GNN: Aggregation Optimization for Graph Neural Networks. In KDD. 461–471.

[19]

Junhyun Lee, Inyeop Lee, and Jaewoo Kang. 2019. Self-Attention Graph Pooling. In ICML. 3734–3743.

[20]

Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. 2019. Deepgcns: Can gcns go as deep as cnns¿. In ICCV. 9267–9276.

[21]

Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI.

[22]

Yaoman Li and Irwin King. 2020. AutoGraph: Automated Graph Neural Network. In ICONIP. 189–201.

[23]

Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. 2016. Gated Graph Sequence Neural Networks. ICLR.

[24]

Hanxiao Liu, Karen Simonyan, and Yiming Yang. 2019. DARTS: Differentiable architecture search. ICLR.

[25]

Denis Lukovnikov and Asja Fischer. 2021. Improving Breadth-Wise Backpropagation in Graph Neural Networks Helps Learning Long-Range Dependencies. In ICML. 7180–7191.

[26]

Diego P. P. Mesquita, Amauri H. Souza Jr., and Samuel Kaski. 2020. Rethinking pooling in graph neural networks. In NeurIPS. 4800–4810.

[27]

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, 2019. Pytorch: An imperative style, high-performance deep learning library. In NeurIPS. 8026–8037.

[28]

Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. 2018. Efficient Neural Architecture Search via Parameter Sharing. In ICML. 4092–4101.

[29]

Trang Pham, Truyen Tran, Hoa Dam, and Svetha Venkatesh. 2017. Graph classification via deep learning with virtual nodes. arXiv preprint arXiv:1708.04357 (2017).

[30]

Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 (2014).

[31]

Mingxing Tan and Quoc Le. 2019. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning. PMLR, 6105–6114.

[32]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. NeurIPS 30 (2017).

[33]

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph attention networks. ICLR.

[34]

Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. 2016. Order Matters: Sequence to sequence for sets. ICLR (2016).

[35]

N Wale and G Karypis. 2006. Comparison of Descriptor Spaces for Chemical Compound Retrieval and Classification. In ICDM. 678–689.

[36]

Xin Wang, Ziwei Zhang, and Wenwu Zhu. 2022. Automated Graph Machine Learning: Approaches, Libraries and Directions. arXiv preprint arXiv:2201.01288 (2022).

[37]

Xu Wang, Huan Zhao, Lanning Wei, and Quanming Yao. 2022. Graph Property Prediction on Open Graph Benchmark: A Winning Solution by Graph Neural Architecture Search. arXiv preprint arXiv:2207.06027 (2022).

[38]

Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. 2021. Curgraph: Curriculum learning for graph classification. In The WebConf. 1238–1248.

[39]

Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. 2021. Mixup for node and graph classification. In The WebConf. 3663–3674.

[40]

Zhili Wang, Shimin Di, and Lei Chen. 2021. Autogel: An automated graph neural network with explicit link information. NeurIPS 34 (2021), 24509–24522.

[41]

Zhen Wang, Zhewei Wei, Yaliang Li, Weirui Kuang, and Bolin Ding. 2022. Graph Neural Networks with Node-wise Architecture. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1949–1958.

[42]

Zhenyi Wang, Huan Zhao, and Chuan Shi. 2022. Profiling the Design Space for Graph Neural Networks based Collaborative Filtering. In WSDM. 1109–1119.

[43]

Lanning Wei, Huan Zhao, and Zhiqiang He. 2022. Designing the Topology of Graph Neural Networks: A Novel Feature Fusion Perspective. In The WebConf. 1381–1391.

[44]

Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. 2021. Pooling architecture search for graph classification. In CIKM. 2091–2100.

[45]

Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. 2018. SNAS: stochastic neural architecture search. ICLR (2018).

[46]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks¿ICLR.

[47]

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation learning on graphs with jumping knowledge networks. In ICML. 5453–5462.

[48]

Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. In KDD. 1365–1374.

[49]

Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. 2021. Do transformers really perform badly for graph representation¿NeurIPS 34 (2021), 28877–28888.

[50]

Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differentiable pooling. In NeurIPS. 4800–4810.

[51]

Jaemin Yoo, Sooyeon Shim, and U Kang. 2022. Model-agnostic augmentation for accurate graph classification. In The WebConf. 1281–1291.

[52]

Jiaxuan You, Rex Ying, and Jure Leskovec. 2020. Design Space for Graph Neural Networks. In NeurIPS.

[53]

Hao Yuan and Shuiwang Ji. 2020. StructPool: Structured graph pooling via conditional random fields. ICLR (2020).

[54]

Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. 2018. An end-to-end deep learning architecture for graph classification. In AAAI.

[55]

Yufeng Zhang, Xueli Yu, Zeyu Cui, Shu Wu, Zhongzhen Wen, and Liang Wang. 2020. Every document owns its structure: Inductive text classification via graph neural networks. In ACL. Association for Computational Linguistics, 334–339.

[56]

Ziwei Zhang, Xin Wang, and Wenwu Zhu. 2021. Automated Machine Learning on Graphs: A Survey. arXiv preprint arXiv:2103.00742 (2021).

[57]

Huan Zhao, Lanning Wei, and Quanming Yao. 2020. Simplifying Architecture Search for Graph Neural Network.

[58]

Huan Zhao, Quanming Yao, and Weiwei Tu. 2021. Search to aggregate neighborhood for graph neural network. In ICDE.

Cited By

Wu ZChen JAl-Sabri ROloulade BGao J(2025)Asymmetric augmented paradigm-based graph neural architecture searchInformation Processing & Management10.1016/j.ipm.2024.10389762:1(103897)Online publication date: Jan-2025
https://doi.org/10.1016/j.ipm.2024.103897
Gao JWu ZAl-Sabri ROloulade BChen J(2024)AutoDDI: Drug–Drug Interaction Prediction With Automated Graph Neural NetworkIEEE Journal of Biomedical and Health Informatics10.1109/JBHI.2024.334957028:3(1773-1784)Online publication date: Mar-2024
https://doi.org/10.1109/JBHI.2024.3349570
WANG ZDI SCHEN LZHOU X(2024)Search to Fine-Tune Pre-Trained Graph Neural Networks for Graph-Level Tasks2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00219(2805-2819)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00219
Show More Cited By

Index Terms

Search to Capture Long-range Dependency with Stacking GNNs for Graph Classification
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Neural networks
2. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Pooling Architecture Search for Graph Classification
CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

Graph classification is an important problem with applications across many domains, like chemistry and bioinformatics, for which graph neural networks (GNNs) have been state-of-the-art (SOTA) methods. GNNs are designed to learn node-level representation ...
Alleviating over-smoothing via graph sparsification based on vertex feature similarity
Abstract
In recent years, graph neural networks (GNNs) have developed rapidly. However, GNNs are difficult to deepen because of over-smoothing. This limits their applications. Starting from the relationship between graph sparsification and over-smoothing, ...
MuGSI: Distilling GNNs with Multi-Granularity Structural Information for Graph Classification
WWW '24: Proceedings of the ACM Web Conference 2024

Recent works have introduced GNN-to-MLP knowledge distillation (KD) frameworks to combine both GNN's superior performance and MLP's fast inference speed. However, existing KD frameworks are primarily designed for node classification within single graphs, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Artifacts Available / v1.1

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Natural Science Foundation of China

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
179
Total Downloads

Downloads (Last 12 months)80
Downloads (Last 6 weeks)5

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu ZChen JAl-Sabri ROloulade BGao J(2025)Asymmetric augmented paradigm-based graph neural architecture searchInformation Processing & Management10.1016/j.ipm.2024.10389762:1(103897)Online publication date: Jan-2025
https://doi.org/10.1016/j.ipm.2024.103897
Gao JWu ZAl-Sabri ROloulade BChen J(2024)AutoDDI: Drug–Drug Interaction Prediction With Automated Graph Neural NetworkIEEE Journal of Biomedical and Health Informatics10.1109/JBHI.2024.334957028:3(1773-1784)Online publication date: Mar-2024
https://doi.org/10.1109/JBHI.2024.3349570
WANG ZDI SCHEN LZHOU X(2024)Search to Fine-Tune Pre-Trained Graph Neural Networks for Graph-Level Tasks2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00219(2805-2819)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00219
Wu ZChen JAl-Sabri ROloulade BGao J(2024)Depth-adaptive graph neural architecture search for graph classificationKnowledge-Based Systems10.1016/j.knosys.2024.112321301(112321)Online publication date: Oct-2024
https://doi.org/10.1016/j.knosys.2024.112321
Chen XKong YChang HGao YLiu ZCoatrieux JShu H(2024)MGSN: Depression EEG lightweight detection based on multiscale DGCN and SNN for multichannel topologyBiomedical Signal Processing and Control10.1016/j.bspc.2024.10605192(106051)Online publication date: Jun-2024
https://doi.org/10.1016/j.bspc.2024.106051
Liang FZhao HWang ZFang WShi CFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Retrieving GNN Architecture for Collaborative FilteringProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615035(1379-1388)Online publication date: 21-Oct-2023
https://doi.org/10.1145/3583780.3615035
Wang ZZhao HLiang FShi CFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Node-dependent Semantic Search over Heterogeneous Graph Neural NetworksProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3614989(2646-2655)Online publication date: 21-Oct-2023
https://doi.org/10.1145/3583780.3614989
Han BWei YWang QCollibus FTessone C(2023)MT$$^2$$AD: multi-layer temporal transaction anomaly detection in ethereum networks with GNNComplex & Intelligent Systems10.1007/s40747-023-01126-z10:1(613-626)Online publication date: 31-Jul-2023
https://doi.org/10.1007/s40747-023-01126-z

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents