Proceedings

LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity

Download BibTeX Cite

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. Main Track. Pages 3550-3558.

https://doi.org/10.24963/ijcai.2023/395

Abstract

Heterophily has been considered as an issue that hurts the performance of Graph Neural Networks (GNNs). To address this issue, some existing work uses a graph-level weighted fusion of the information of multi-hop neighbors to include more nodes with homophily. However, the heterophily might differ among nodes, which requires to consider the local topology. Motivated by it, we propose to use the local similarity (LocalSim) to learn node-level weighted fusion, which can also serve as a plug-and-play module. For better fusion, we propose a novel and efficient Initial Residual Difference Connection (IRDC) to extract more informative multi-hop information. Moreover, we provide theoretical analysis on the effectiveness of LocalSim representing node homophily on synthetic graphs. Extensive evaluations over real benchmark datasets show that our proposed method, namely Local Similarity Graph Neural Network (LSGNN), can offer comparable or superior state-of-the-art performance on both homophilic and heterophilic graphs. Meanwhile, the plug-and-play model can significantly boost the performance of existing GNNs.

  1. [Abu-El-Haija et al., 2019] Sami Abu-El-Haija, Bryan Per- ozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Ler- man, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Gal- styan. Mixhop: Higher-order graph convolutional archi- tectures via sparsified neighborhood mixing. In Inter- national Conference on Machine Learning, pages 21-29. PMLR, 2019.
  2. [Battaglia et al., 2018] Peter W Battaglia, Jessica B Ham- rick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
  3. [Bo et al., 2021] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00797, 2021.
  4. [Chanpuriya and Musco, 2022] Sudhanshu Chanpuriya and Cameron N Musco. Simplified graph convolution with heterophily. In Alice H. Oh, Alekh Agarwal, Danielle Bel- grave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  5. [Chen et al., 2020] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Confer- ence on Machine Learning, pages 1725-1735. PMLR, 2020.
  6. [Chien et al., 2021] Eli Chien, Jianhao Peng, Pan Li, and Ol- gica Milenkovic. Adaptive universal generalized pager- ank graph neural network. In International Conference on Learning Representations, 2021.
  7. [Defferrard et al., 2016] Michaël Defferrard, Xavier Bres- son, and Pierre Vandergheynst. Convolutional neural net- works on graphs with fast localized spectral filtering. Ad- vances in Neural Information Processing Systems, 29, 2016.
  8. [Errica et al., 2020] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Interna- tional Conference on Learning Representations. OpenRe- view.net, 2020.
  9. [Hamilton et al., 2017] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv, abs/1706.02216, 2017.
  10. [Hamilton, 2020] William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
  11. [He et al., 2021] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 2021.
  12. [Hu et al., 2020] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Informa- tion Processing Systems, 33:22118-22133, 2020.
  13. [Jiang et al., 2013] Yuexin Jiang, Daniel I Bolnick, and Mark Kirkpatrick. Assortative mating in animals. The American Naturalist, 181(6):E125-E138, 2013.
  14. [Kipf and Welling, 2016] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv, abs/1609.02907, 2016.
  15. [Li et al., 2022] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Ma- chine Learning, pages 13242-13256. PMLR, 2022.
  16. [Lim et al., 2021] Derek Lim, Felix Hohne, Xiuyu Li, Si- jia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
  17. [Liu et al., 2020] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 338-348, 2020.
  18. [Luan et al., 2022] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. arXiv preprint arXiv:2210.07606, 2022.
  19. [McPherson et al., 2001] Miller McPherson, Lynn Smith- Lovin, and James M Cook. Birds of a feather: Ho- mophily in social networks. Annual Review of Sociology, 27(1):415-444, 2001.
  20. [Namata et al., 2012] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active sur- veying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, page 1, 2012.
  21. [Pei et al., 2020] Hongbin Pei, Bingzhe Wei, Kevin Chen- Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Ge- ometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
  22. [Rozemberczki et al., 2021] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Em- bedding. Journal of Complex Networks, 9(2), 2021.
  23. [Scarselli et al., 2009] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
  24. [Sen et al., 2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Ai Magazine, 2008.
  25. [Velickovic et al., 2017] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv, abs/1710.10903, 2017.
  26. [Wu et al., 2019] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv:1902.07153, 2019.
  27. [Zhang and Chen, 2018] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31, 2018.
  28. [Zhu et al., 2020a] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. arXiv preprint arXiv:2009.13566, 2020.
  29. [Zhu et al., 2020b] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limita- tions and effective designs. Advances in Neural Informa- tion Processing Systems, 33, 2020.

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

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