More Web Proxy on the site http://driver.im/

research-article

Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels

Authors:

Guojie SongAuthors Info & Claims

WWW '21: Proceedings of the Web Conference 2021

Pages 1204 - 1214

https://doi.org/10.1145/3442381.3449951

Published: 03 June 2021 Publication History

Abstract

Graph neural networks (GNNs) have achieved tremendous success in graph mining. However, the inability of GNNs to model substructures in graphs remains a significant drawback. Specifically, message-passing GNNs (MPGNNs), as the prevailing type of GNNs, have been theoretically shown unable to distinguish, detect or count many graph substructures. While efforts have been paid to complement the inability, existing works either rely on pre-defined substructure sets, thus being less flexible, or are lacking in theoretical insights. In this paper, we propose GSKN1, a GNN model with a theoretically stronger ability to distinguish graph structures. Specifically, we design GSKN based on anonymous walks (AWs), flexible substructure units, and derive it upon feature mappings of graph kernels (GKs). We theoretically show that GSKN provably extends the 1-WL test, and hence the maximally powerful MPGNNs from both graph-level and node-level viewpoints. Correspondingly, various experiments are leveraged to evaluate GSKN, where GSKN outperforms a wide range of baselines, endorsing the analysis.

References

[1]

Rami Al-Rfou, Bryan Perozzi, and Dustin Zelle. 2019. Ddgk: Learning graph representations for deep divergence graph kernels. In The World Wide Web Conference. 37–48.

Digital Library

[2]

Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. 2020. On Weisfeiler-Leman invariance: subgraph counts and related graph properties. J. Comput. System Sci.(2020).

[3]

Mohsen Bayati and Andrea Montanari. 2011. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory 57, 2 (2011), 764–785.

Digital Library

[4]

Karsten M Borgwardt and Hans-Peter Kriegel. 2005. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM). IEEE, 8–pp.

Digital Library

[5]

Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. 2020. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. arXiv preprint arXiv:2006.09252(2020).

[6]

Chen Cai and Yusu Wang. 2018. A simple yet effective baseline for non-attributed graph classification. arXiv preprint arXiv:1811.03508(2018).

[7]

Dexiong Chen, Laurent Jacob, and Julien Mairal. 2019. Biological sequence modeling with convolutional kernel networks. Bioinformatics 35, 18 (2019), 3294–3302.

[8]

Dexiong Chen, Laurent Jacob, and Julien Mairal. 2020. Convolutional Kernel Networks for Graph-Structured Data. arXiv preprint arXiv:2003.05189(2020).

[9]

Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. 2020. Can graph neural networks count substructures?arXiv preprint arXiv:2002.04025(2020).

[10]

Fan RK Chung and Fan Chung Graham. 1997. Spectral graph theory. Number 92. American Mathematical Soc.

[11]

Clemens Damke, Vitalik Melnikov, and Eyke Hüllermeier. 2020. A Novel Higher-order Weisfeiler-Lehman Graph Convolution. In Asian Conference on Machine Learning. PMLR, 49–64.

[12]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems. 3844–3852.

[13]

Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. 2019. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems. 5723–5733.

[14]

David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. 2015. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems. 2224–2232.

[15]

Thomas Gärtner, Peter Flach, and Stefan Wrobel. 2003. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines. Springer, 129–143.

[16]

Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for Quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. 1263–1272.

Digital Library

[17]

Mark S Granovetter. 1973. The strength of weak ties. American journal of sociology 78, 6 (1973), 1360–1380.

[18]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in neural information processing systems. 1024–1034.

[19]

Sergey Ivanov and Evgeny Burnaev. 2018. Anonymous Walk Embeddings. In International Conference on Machine Learning. 2186–2195.

[20]

Yilun Jin, Guojie Song, and Chuan Shi. 2020. GraLSP: Graph Neural Networks with Local Structural Patterns. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, New York, NY, USA. AAAI Press, 4361–4368.

[21]

Krzysztof Juszczyszyn, Przemysław Kazienko, and Katarzyna Musiał. 2008. Local topology of social network based on motif analysis. In International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. Springer, 97–105.

Digital Library

[22]

U Kang, Hanghang Tong, and Jimeng Sun. 2012. Fast random walk graph kernel. In Proceedings of the SIAM international conference on data mining. SIAM, 828–838.

[23]

Thomas Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference of Learning Representations.

[24]

Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. 2018. A Property Testing Framework for the Theoretical Expressivity of Graph Kernels. In IJCAI. 2348–2354.

[25]

John Boaz Lee, Ryan Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. 2019. Graph convolutional networks with motif-based attention. In ACM International Conference on Information and Knowledge Management (CIKM).

Digital Library

[26]

Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. 2017. Deriving Neural Architectures from Sequence and Graph Kernels. In International Conference on Machine Learning. 2024–2033.

[27]

Pan Li, Hoang Dau, Gregory Puleo, and Olgica Milenkovic. 2017. Motif clustering and overlapping clustering for social network analysis. In IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 1–9.

[28]

Zhichang Liu, Siva Krishna Mohan Nalluri, and J Fraser Stoddart. 2017. Surveying macrocyclic chemistry: from flexible crown ethers to rigid cyclophanes. Chemical Society Reviews 46, 9 (2017), 2459–2478.

[29]

Qingqing Long, Yilun Jin, Guojie Song, Yi Li, and Wei Lin. 2020. Graph Structural-topic Neural Network. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1065–1073.

Digital Library

[30]

Qingqing Long, Yiming Wang, Lun Du, Guojie Song, Yilun Jin, and Wei Lin. 2019. Hierarchical Community Structure Preserving Network Embedding: A Subspace Approach. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 409–418.

Digital Library

[31]

Silvio Micali and Zeyuan Allen Zhu. 2016. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics 200 (2016), 108–122.

Digital Library

[32]

Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science 298, 5594 (2002), 824–827.

[33]

Christopher Morris, Nils M Kriege, Kristian Kersting, and Petra Mutzel. 2016. Faster kernels for graphs with continuous attributes via hashing. In 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 1095–1100.

[34]

Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 4602–4609.

Digital Library

[35]

Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. 2017. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05005(2017).

[36]

Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016. Learning convolutional neural networks for graphs. In International conference on machine learning. 2014–2023.

Digital Library

[37]

Ashwin Paranjape, Austin R Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. 601–610.

Digital Library

[38]

Nataša Pržulj. 2007. Biological network comparison using graphlet degree distribution. Bioinformatics 23, 2 (2007), e177–e183.

Digital Library

[39]

Ryoma Sato. 2020. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078(2020).

[40]

Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008. The graph neural network model. IEEE Transactions on Neural Networks 20, 1 (2008), 61–80.

Digital Library

[41]

John Shawe-Taylor, Nello Cristianini, 2004. Kernel methods for pattern analysis. Cambridge university press.

Digital Library

[42]

Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. 2011. Weisfeiler-lehman graph kernels.Journal of Machine Learning Research 12, 9 (2011).

[43]

Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics. 488–495.

[44]

Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. 2019. Wasserstein weisfeiler-lehman graph kernels. In Advances in Neural Information Processing Systems. 6439–6449.

[45]

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint:1710.10903(2017).

[46]

Christopher KI Williams and Matthias Seeger. 2001. Using the Nyström method to speed up kernel machines. In Advances in neural information processing systems. 682–688.

[47]

Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. In International Conference on Machine Learning. 6861–6871.

[48]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems (2020).

[49]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful are graph neural networks?arXiv preprint arXiv:1810.00826(2018).

[50]

Kai Zhang, Ivor W Tsang, and James T Kwok. 2008. Improved Nyström low-rank approximation and error analysis. In Proceedings of the 25th international conference on Machine learning. 1232–1239.

Digital Library

[51]

Luming Zhang, Mingli Song, Zicheng Liu, Xiao Liu, Jiajun Bu, and Chun Chen. 2013. Probabilistic graphlet cut: Exploiting spatial structure cue for weakly supervised image segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition. 1908–1915.

Digital Library

[52]

Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. 2018. Retgk: Graph kernels based on return probabilities of random walks. In Advances in Neural Information Processing Systems. 3964–3974.

Cited By

Li DLi XGan ZLi QQu BWang J(2025)Rethinking the impact of noisy labels in graph classification: A utility and privacy perspectiveNeural Networks10.1016/j.neunet.2024.106919182(106919)Online publication date: Feb-2025
https://doi.org/10.1016/j.neunet.2024.106919
Yang ZZhang GWu JYang JSheng QXue SZhou CAggarwal CPeng HHu WHancock ELiò P(2024)State of the Art and Potentialities of Graph-level LearningACM Computing Surveys10.1145/3695863Online publication date: 12-Sep-2024
https://dl.acm.org/doi/10.1145/3695863
Dan JLiu WLiu MXie CDong SMa GTan YXing JCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)HOGDA: Boosting Semi-supervised Graph Domain Adaptation via High-Order Structure-Guided Adaptive Feature AlignmentProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3680765(11109-11118)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3680765
Show More Cited By

Recommendations

An Empirical Study of the Expressiveness of Graph Kernels and Graph Neural Networks
Artificial Neural Networks and Machine Learning – ICANN 2021
Abstract
Graph neural networks and graph kernels have achieved great success in solving machine learning problems on graphs. Recently, there has been considerable interest in determining the expressive power mainly of graph neural networks and of graph ...
Enhancing Shortest-Path Graph Kernels via Graph Augmentation
Machine Learning and Knowledge Discovery in Databases. Research Track and Demo Track
Abstract
The conventional shortest-path graph kernel (SP) decomposes graphs into shortest paths and computes their frequencies in each graph. However, SP cannot compare graphs with variable scales of the graph structure well and cannot compare attributed ...
Random walk graph neural networks
NIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems

In recent years, graph neural networks (GNNs) have become the de facto tool for performing machine learning tasks on graphs. Most GNNs belong to the family of message passing neural networks (MPNNs). These models employ an iterative neighborhood ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '21: Proceedings of the Web Conference 2021

April 2021

4054 pages

ISBN:9781450383127

DOI:10.1145/3442381

Editors:
Jure Leskovec
Stanford
,
Marko Grobelnik
Jožef Stefan Institute
,
Marc Najork
Google
,
Jie Tang
Tsinghua University
,
Leila Zia
Wikimedia Foundation

Copyright © 2021 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 ACM 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: 03 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '21

Sponsor:

SIGWEB

WWW '21: The Web Conference 2021

April 19 - 23, 2021

Ljubljana, Slovenia

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
341
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li DLi XGan ZLi QQu BWang J(2025)Rethinking the impact of noisy labels in graph classification: A utility and privacy perspectiveNeural Networks10.1016/j.neunet.2024.106919182(106919)Online publication date: Feb-2025
https://doi.org/10.1016/j.neunet.2024.106919
Yang ZZhang GWu JYang JSheng QXue SZhou CAggarwal CPeng HHu WHancock ELiò P(2024)State of the Art and Potentialities of Graph-level LearningACM Computing Surveys10.1145/3695863Online publication date: 12-Sep-2024
https://dl.acm.org/doi/10.1145/3695863
Dan JLiu WLiu MXie CDong SMa GTan YXing JCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)HOGDA: Boosting Semi-supervised Graph Domain Adaptation via High-Order Structure-Guided Adaptive Feature AlignmentProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3680765(11109-11118)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3680765
Khoshraftar SAn A(2024)A Survey on Graph Representation Learning MethodsACM Transactions on Intelligent Systems and Technology10.1145/363351815:1(1-55)Online publication date: 16-Jan-2024
https://dl.acm.org/doi/10.1145/3633518
Dong ZLong QZhou YWang PZhu ZLuo XWang YWang PZhou YSerra ESpezzano F(2024)PIXEL: Prompt-based Zero-shot Hashing via Visual and Textual Semantic AlignmentProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679747(487-496)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679747
Long QYan YCui WJu WZhu ZZhou YWang XXiao MSerra ESpezzano F(2024)MOAT: Graph Prompting for 3D Molecular GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679628(1586-1596)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679628
Long QFang ZFang CChen CWang PZhou YChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Unveiling Delay Effects in Traffic Forecasting: A Perspective from Spatial-Temporal Delay Differential EquationsProceedings of the ACM Web Conference 202410.1145/3589334.3645688(1035-1044)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645688
Yan YZhang PFang ZLong QChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Inductive Graph Alignment Prompt: Bridging the Gap between Graph Pre-training and Inductive Fine-tuning From Spectral PerspectiveProceedings of the ACM Web Conference 202410.1145/3589334.3645620(4328-4339)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645620
Lee MZhao LAkoglu LChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Descriptive Kernel Convolution Network with Improved Random Walk KernelProceedings of the ACM Web Conference 202410.1145/3589334.3645405(457-468)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645405
Guo XJiao PZhang WPan TJia MShi DWang W(2024)Representation Learning on Heterostructures via Heterogeneous Anonymous WalksIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.323400535:7(9538-9552)Online publication date: Jul-2024
https://doi.org/10.1109/TNNLS.2023.3234005
Show More Cited By

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