research-article

HGK-GNN: Heterogeneous Graph Kernel based Graph Neural Networks

Authors:

Guojie SongAuthors Info & Claims

KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Pages 1129 - 1138

https://doi.org/10.1145/3447548.3467429

Published: 14 August 2021 Publication History

Abstract

While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture heterogeneous structures and attributes of an underlying graph. Furthermore, though many Heterogeneous GNN (HGNN) variants have been proposed and have achieved state-of-the-art results, there are limited theoretical understandings of their properties. To this end, we introduce graph kernel to HGNNs and develop a Heterogeneous Graph Kernel-based Graph Neural Networks (HGK-GNN). Specifically, we incorporate the Mahalanobis distance (MD) to build a Heterogeneous Graph Kernel (HGK), and incorporating it into deep neural architectures, thus leveraging a heterogeneous GNN with a heterogeneous aggregation scheme. Also, we mathematically bridge HGK-GNN to metapath-based HGNNs, which are the most popular and effective variants of HGNNs. We theoretically analyze HGK-GNN with the indispensable Encoder and Aggregator component in metapath-based HGNNs, through which we provide a theoretical perspective to understand the most popular HGNNs. To the best of our knowledge, we are the first to introduce HGK into the field of HGNNs, and mark a first step in the direction of theoretically understanding and analyzing HGNNs. Correspondingly, both graph and node classification experiments are leveraged to evaluate HGK-GNN, where HGK-GNN outperforms a wide range of baselines on six real-world datasets, endorsing the analysis.

References

[1]

Shigeo Abe. 2005. Training of support vector machines with Mahalanobis kernels. In International Conference on Artificial Neural Networks. Springer, 571--576.

[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]

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

[4]

Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. 2019. Representation learning for attributed multiplex heterogeneous network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1358--1368.

Digital Library

[5]

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

[6]

Hongxu Chen, Hongzhi Yin, Weiqing Wang, Hao Wang, Quoc Viet Hung Nguyen, and Xue Li. 2018. PME: projected metric embedding on heterogeneous networks for link prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1177--1186.

Digital Library

[7]

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

[8]

Taylor Denouden, Rick Salay, Krzysztof Czarnecki, Vahdat Abdelzad, Buu Phan, and Sachin Vernekar. 2018. Improving reconstruction autoencoder out-of-distribution detection with mahalanobis distance. arXiv preprint arXiv:1812.02765 (2018).

[9]

Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 135--144.

Digital Library

[10]

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.

[11]

Mathieu Fauvel, Jocelyn Chanussot, Jon Atli Benediktsson, and Alberto Villa. 2013. Parsimonious Mahalanobis kernel for the classification of high dimensional data. Pattern Recognition, Vol. 46, 3 (2013), 845--854.

Digital Library

[12]

Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. 2020. MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding. In Proceedings of The Web Conference 2020. 2331--2341.

Digital Library

[13]

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

[14]

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

[15]

Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020. 2704--2710.

Digital Library

[16]

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.

[17]

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

[18]

Nils Kriege and Petra Mutzel. 2012. Subgraph matching kernels for attributed graphs. arXiv preprint arXiv:1206.6483 (2012).

[19]

Nils M. Kriege, Matthias Fey, Denis Fisseler, Petra Mutzel, and Frank Weichert. [n.d.]. Recognizing Cuneiform Signs Using Graph Based Methods. In Proceedings of The International Workshop on Cost-Sensitive Learning. 31--44.

[20]

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.

[21]

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.

[22]

Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. 2020. Neural subgraph isomorphism counting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1959--1969.

Digital Library

[23]

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

[24]

Qingqing Long, Yilun Jin, Yi Wu, and Guojie Song. 2021. Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels. arXiv preprint arXiv:2104.02995 (2021).

[25]

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

[26]

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

[27]

Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. 2016. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, Vol. 102, 2 (2016), 209--245.

Digital Library

[28]

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

Digital Library

[29]

Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 1532--1543.

[30]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 701--710.

Digital Library

[31]

Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolutional networks. In European Semantic Web Conference. Springer, 593--607.

Digital Library

[32]

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

[33]

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

[34]

Feroz Ahmed Siddiky, Mohammed Shamsul Alam, Tanveer Ahsan, and Mohammed Saifur Rahim. 2007. An efficient approach to rotation invariant face detection using PCA, generalized regression neural network and Mahalanobis distance by reducing search space. In 2007 10th international conference on computer and information technology. IEEE, 1--6.

[35]

Genyun Sun, Xueqian Rong, Aizhu Zhang, Hui Huang, Jun Rong, and Xuming Zhang. 2019. Multi-scale mahalanobis kernel-based support vector machine for classification of high-resolution remote sensing images. Cognitive Computation (2019), 1--8.

[36]

Thanh Tran, Renee Sweeney, and Kyumin Lee. 2019. Adversarial Mahalanobis Distance-Based Attentive Song Recommender for Automatic Playlist Continuation. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. 245--254.

Digital Library

[37]

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

[38]

Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019. Heterogeneous graph attention network. In The World Wide Web Conference. 2022--2032.

Digital Library

[39]

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.

[40]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations.

[41]

Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. 2020. Heterogeneous Network Representation Learning: Survey, Benchmark, Evaluation, and Beyond. arXiv preprint arXiv:2004.00216 (2020).

[42]

Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. 2019. Graph transformer networks. In Advances in Neural Information Processing Systems. 11983--11993.

[43]

Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. 2019. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 793--803.

Digital Library

[44]

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

Ma SWang W(2024)Proactive Return Prediction in Online Fashion Retail Using Heterogeneous Graph Neural NetworksElectronics10.3390/electronics1307139813:7(1398)Online publication date: 8-Apr-2024
https://doi.org/10.3390/electronics13071398
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
Show More Cited By

Index Terms

HGK-GNN: Heterogeneous Graph Kernel based Graph Neural Networks
1. Information systems
  1. Information systems applications
    1. Collaborative and social computing systems and tools
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

HGCN: A Heterogeneous Graph Convolutional Network-Based Deep Learning Model Toward Collective Classification
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Collective classification, as an important technique to study networked data, aims to exploit the label autocorrelation for a group of inter-connected entities with complex dependencies. As the emergence of various heterogeneous information networks (...
KGNN: Harnessing Kernel-based Networks for Semi-supervised Graph Classification
WSDM '22: Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining

This paper studies semi-supervised graph classification, which is an important problem with various applications in social network analysis and bioinformatics. This problem is typically solved by using graph neural networks (GNNs), which yet rely on a ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

August 2021

4259 pages

ISBN:9781450383325

DOI:10.1145/3447548

General Chairs:
Feida Zhu
Singapore Management University
,
Beng Chin Ooi
National University of Singapore
,
Chunyan Miao
Nanyang Technology University
,
Program Chairs:
Haixun Wang,
Iryna Skrypnyk,
Wynne Hsu,
Sanjay Chawla

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 August 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China

Conference

KDD '21

Sponsor:

KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 14 - 18, 2021

Virtual Event, Singapore

Acceptance Rates

Overall Acceptance Rate 66 of 1,115 submissions, 6%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
1,149
Total Downloads

Downloads (Last 12 months)150
Downloads (Last 6 weeks)23

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma SWang W(2024)Proactive Return Prediction in Online Fashion Retail Using Heterogeneous Graph Neural NetworksElectronics10.3390/electronics1307139813:7(1398)Online publication date: 8-Apr-2024
https://doi.org/10.3390/electronics13071398
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
Lin GZhen MWang DLong QZhou YXiao MSerra ESpezzano F(2024)GUME: Graphs and User Modalities Enhancement for Long-Tail Multimodal RecommendationProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679620(1400-1409)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679620
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
Zhang PLi CKang LHuang FWang SXie XKim SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)High-Frequency-aware Hierarchical Contrastive Selective Coding for Representation Learning on Text Attributed GraphsProceedings of the ACM Web Conference 202410.1145/3589334.3645614(4316-4327)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645614
Peng TLuo YLi YYang CLiu AWeng Z(2024)Style Factorization: Explore Diverse Style Variation for Domain GeneralizationICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10447540(7330-7334)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10447540
Cui WLong QXiao MWang XFeng GLi XWang PZhou Y(2024)Refining computational inference of gene regulatory networks: integrating knockout data within a multi-task frameworkBriefings in Bioinformatics10.1093/bib/bbae36125:5Online publication date: 31-Jul-2024
https://doi.org/10.1093/bib/bbae361
Ju WFang ZGu YLiu ZLong QQiao ZQin YShen JSun FXiao ZYang JYuan JZhao YWang YLuo XZhang M(2024)A Comprehensive Survey on Deep Graph Representation LearningNeural Networks10.1016/j.neunet.2024.106207173(106207)Online publication date: May-2024
https://doi.org/10.1016/j.neunet.2024.106207
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.

Media

Figures

Other

Tables

View Table of Contents