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

research-article

DDGK: Learning Graph Representations for Deep Divergence Graph Kernels

Authors:

Dustin ZelleAuthors Info & Claims

WWW '19: The World Wide Web Conference

Pages 37 - 48

https://doi.org/10.1145/3308558.3313668

Published: 13 May 2019 Publication History

Abstract

Can neural networks learn to compare graphs without feature engineering? In this paper, we show that it is possible to learn representations for graph similarity with neither domain knowledge nor supervision (i.e. feature engineering or labeled graphs). We propose Deep Divergence Graph Kernels, an unsupervised method for learning representations over graphs that encodes a relaxed notion of graph isomorphism. Our method consists of three parts. First, we learn an encoder for each anchor graph to capture its structure. Second, for each pair of graphs, we train a cross-graph attention network which uses the node representations of an anchor graph to reconstruct another graph. This approach, which we call isomorphism attention, captures how well the representations of one graph can encode another. We use the attention-augmented encoder's predictions to define a divergence score for each pair of graphs. Finally, we construct an embedding space for all graphs using these pair-wise divergence scores.

Unlike previous work, much of which relies on 1) supervision, 2) domain specific knowledge (e.g. a reliance on Weisfeiler-Lehman kernels), and 3) known node alignment, our unsupervised method jointly learns node representations, graph representations, and an attention-based alignment between graphs.

Our experimental results show that Deep Divergence Graph Kernels can learn an unsupervised alignment between graphs, and that the learned representations achieve competitive results when used as features on a number of challenging graph classification tasks. Furthermore, we illustrate how the learned attention allows insight into the the alignment of sub-structures across graphs.

References

[1]

Sami Abu-El-Haija, Bryan Perozzi, and Rami Al-Rfou. 2017. Learning Edge Representations via Low-Rank Asymmetric Projections. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management(CIKM '17). ACM, New York, NY, USA, 1787-1796.

Digital Library

[2]

Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alexander A Alemi. 2018. Watch Your Step: Learning Node Embeddings via Graph Attention. In Advances in Neural Information Processing Systems. 9198-9208.

Digital Library

[3]

Mikel Artetxe, Gorka Labaka, and Eneko Agirre. 2016. Learning principled bilingual mappings of word embeddings while preserving monolingual invariance. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2289-2294.

[4]

Yunsheng Bai, Hao Ding, Song Bian, Yizhou Sun, and Wei Wang. 2018. Graph Edit Distance Computation via Graph Neural Networks. arXiv preprint arXiv:1808.05689(2018).

[5]

Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, 2018. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261(2018).

[6]

Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, and Christos Faloutsos. 2012. Netsimile: A scalable approach to size-independent network similarity. arXiv preprint arXiv:1209.2684(2012).

[7]

Aleksandar Bojchevski and Stephan Günnemann. 2017. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv:1707.03815(2017).

[8]

Karsten M Borgwardt and Hans-Peter Kriegel. 2005. Shortest-path kernels on graphs. In Data Mining, Fifth IEEE International Conference on. IEEE, 8-pp.

Digital Library

[9]

Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel. 2005. Protein function prediction via graph kernels. Bioinformatics21, suppl_1 (2005), i47-i56.

Digital Library

[10]

Karsten M Borgwardt, Nicol N Schraudolph, and SVN Vishwanathan. 2007. Fast computation of graph kernels. In Advances in neural information processing systems. 1449-1456.

Digital Library

[11]

Horst Bunke, Pasquale Foggia, Corrado Guidobaldi, Carlo Sansone, and Mario Vento. 2002. A comparison of algorithms for maximum common subgraph on randomly connected graphs. In SSPR. Springer, 123-132.

Digital Library

[12]

Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2016. Deep Neural Networks for Learning Graph Representations. In Proceedings of the Association for the Advancement of Artificial Intelligence.

Digital Library

[13]

Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. 2017. Learning community embedding with community detection and node embedding on graphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM, 377-386.

Digital Library

[14]

Haochen Chen, Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2018. A Tutorial on Network Embeddings. arXiv preprint arXiv:1808.02590(2018).

[15]

Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. 2018. Harp: Hierarchical representation learning for networks. (2018).

[16]

Jan K Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, and Yoshua Bengio. 2015. Attention-Based Models for Speech Recognition. In Advances in Neural Information Processing Systems 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (Eds.). Curran Associates, Inc., 577-585. http://papers.nips.cc/paper/5847-attention-based-models-for-speech-recognition.pdf

Digital Library

[17]

Fan Chung, Fan RK Chung, Fan Chung Graham, Linyuan Lu, Kian Fan Chung, 2006. A Generative Model - the Preferential Attachment Scheme. In Complex graphs and networks. Number 107. American Mathematical Soc., Chapter 3.

[18]

Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. 2018. A survey on network embedding. IEEE Transactions on Knowledge and Data Engineering (2018).

[19]

Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Hansch. 1991. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry34, 2 (1991), 786-797. arXiv:https://doi.org/10.1021/jm00106a046

[20]

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

[21]

Alessandro Epasto and Bryan Perozzi. 2019. Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts. WWW (2019).

Digital Library

[22]

Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. 2010. A survey of graph edit distance. Pattern Analysis and applications13, 1 (2010), 113-129.

[23]

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. JMLR. org, 1263-1272.

Digital Library

[24]

A. Grover and J. Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[25]

Bernard Haasdonk and Claus Bahlmann. 2004. Learning with distance substitution kernels. In Joint Pattern Recognition Symposium. Springer, 220-227.

[26]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. 1024-1034.

Digital Library

[27]

U Kang, Hanghang Tong, and Jimeng Sun. 2012. Fast random walk graph kernel. In Proceedings of the 2012 SIAM International Conference on Data Mining. SIAM, 828-838.

[28]

Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. 2003. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference on machine learning (ICML-03). 321-328.

Digital Library

[29]

Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980(2014).

[30]

T. Kipf and M. Welling. 2016. Semi-Supervised Classification with Graph Convolutional Networks. arXiv preprint arXiv:1609.02907.

[31]

Danai Koutra, Joshua T Vogelstein, and Christos Faloutsos. 2013. Deltacon: A principled massive-graph similarity function. In Proceedings of the 2013 SIAM International Conference on Data Mining. SIAM, 162-170.

[32]

Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. 2016. On valid optimal assignment kernels and applications to graph classification. In Advances in Neural Information Processing Systems. 1623-1631.

Digital Library

[33]

Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2018. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. arXiv preprint arXiv:1810.02244(2018).

[34]

Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. 2017. graph2vec: Learning Distributed Representations of Graphs. CoRRabs/1707.05005(2017). arxiv:1707.05005http://arxiv.org/abs/1707.05005

[35]

M. E. J. Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E74 (Sep 2006), 036104. Issue 3.

[36]

M. Niepert, M. Ahmed, and K. Kutzkov. 2016. Learning Convolutional Neural Networks for Graphs. In International Conference on Machine Learning (ICML).

Digital Library

[37]

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

Digital Library

[38]

Panagiotis Papadimitriou, Ali Dasdan, and Hector Garcia-Molina. 2010. Web graph similarity for anomaly detection. Journal of Internet Services and Applications1, 1(2010), 19-30.

[39]

Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, 2011. Scikit-learn: Machine learning in Python. Journal of machine learning research12, Oct (2011), 2825-2830.

Digital Library

[40]

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. ACM, 701-710.

Digital Library

[41]

Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. 2017. Don't Walk, Skip!: Online Learning of Multi-scale Network Embeddings. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017. ACM, 258-265.

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 Research12, Sep (2011), 2539-2561.

Digital Library

[43]

Aynaz Taheri, Kevin Gimpel, and Tanya Berger-Wolf. 2018. Learning Graph Representations with Recurrent Neural Network Autoencoders. In KDD'18 Deep Learning Day.

[44]

TensorflowTeam. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. http://tensorflow.org/Software available from tensorflow.org.

[45]

Antoine J-P Tixier, Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2018. Graph Classification with 2D Convolutional Neural Networks. (2018).

[46]

Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. 2003. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics19, 10 (2003), 1183-1193.

[47]

Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alex Bronstein, and Emmanuel Müller. 2018. NetLSD: Hearing the Shape of a Graph. KDD (2018).

Digital Library

[48]

Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. 2017. VERSE: Versatile Graph Embeddings from Similarity Measures. (2017).

Digital Library

[49]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems. 5998-6008.

Digital Library

[50]

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.109031, 2 (2017).

[51]

Nikil Wale and George Karypis. 2006. Comparison of descriptor spaces for chemical compound retrieval and classification. In Proceedings - Sixth International Conference on Data Mining, ICDM 2006. 678-689.

Digital Library

[52]

Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. 2017. Community Preserving Network Embedding. In AAAI. 203-209.

Digital Library

[53]

Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'small-world'networks. nature393, 6684 (1998), 440.

[54]

Lingfei Wu, Ian En-Hsu Yen, Fangli Xu, Pradeep Ravikuma, and Michael Witbrock. 2018. D2KE: From Distance to Kernel and Embedding. arXiv preprint arXiv:1802.04956(2018).

[55]

Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. 2015. Show, attend and tell: Neural image caption generation with visual attention. In International conference on machine learning. 2048-2057.

Digital Library

[56]

Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1365-1374.

Digital Library

[57]

Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. 2016. Hierarchical attention networks for document classification. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 1480-1489.

[58]

Zi Yin and Yuanyuan Shen. 2018. On the Dimensionality of Word Embedding. In Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc., 887-898. http://papers.nips.cc/paper/7368-on-the-dimensionality-of-word-embedding.pdf

Digital Library

[59]

Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. 2018. Hierarchical Graph Representation Learning with Differentiable Pooling. arXiv preprint arXiv:1806.08804(2018).

[60]

Wayne W. Zachary. 1977. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research33, 4 (1977), 452-473.

[61]

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

[62]

Vincent W Zheng, Sandro Cavallari, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. 2016. From node embedding to community embedding. arXiv preprint arXiv:1610.09950(2016).

[63]

Dingyuan Zhu, Peng Cui, Daixin Wang, and Wenwu Zhu. 2018. Deep Variational Network Embedding in Wasserstein Space. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2827-2836.

Digital Library

Cited By

KAWANO KKOIDE SSHIOKAWA HAMAGASA T(2024)Multi-Dimensional Fused Gromov Wasserstein Discrepancy for Edge-Attributed GraphsIEICE Transactions on Information and Systems10.1587/transinf.2023DAP0014E107.D:5(683-693)Online publication date: 1-May-2024
https://doi.org/10.1587/transinf.2023DAP0014
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
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
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 ...
Graph kernels based on linear patterns: Theoretical and experimental comparisons▪
Abstract
Graph kernels are powerful tools to bridge the gap between machine learning and data encoded as graphs. Most graph kernels are based on the decomposition of graphs into a set of patterns. The similarity between two graphs is then ...
Highlights
- Graph kernels are powerful to bridge the gap between machine learning and graphs.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '19: The World Wide Web Conference

May 2019

3620 pages

ISBN:9781450366748

DOI:10.1145/3308558

Editors:
Ling Liu
Georgia Tech, USA
,
Ryen White
Microsoft Research, USA

Copyright © 2019 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]

In-Cooperation

IW3C2: International World Wide Web Conference Committee

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 May 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '19

WWW '19: The Web Conference

May 13 - 17, 2019

CA, San Francisco, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
1,016
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)4

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

KAWANO KKOIDE SSHIOKAWA HAMAGASA T(2024)Multi-Dimensional Fused Gromov Wasserstein Discrepancy for Edge-Attributed GraphsIEICE Transactions on Information and Systems10.1587/transinf.2023DAP0014E107.D:5(683-693)Online publication date: 1-May-2024
https://doi.org/10.1587/transinf.2023DAP0014
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
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
Wang LZheng YJin DLi FQiao YPan S(2024)Contrastive Graph Similarity NetworksACM Transactions on the Web10.1145/358051118:2(1-20)Online publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1145/3580511
Yang PWang HYang JQian ZZhang YLin X(2024)Deep Learning Approaches for Similarity Computation: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.342248436:12(7893-7912)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3422484
Xu LLiu HYuan XChen ETang Y(2024)GraKerformer: A Transformer With Graph Kernel for Unsupervised Graph Representation LearningIEEE Transactions on Cybernetics10.1109/TCYB.2024.346521354:12(7320-7332)Online publication date: Dec-2024
https://doi.org/10.1109/TCYB.2024.3465213
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
Leonardi FRiesen K(2024)Dissimilarity-Based Graph Embedding: An Efficient GAT-based ApproachPattern Recognition10.1007/978-3-031-78192-6_24(361-374)Online publication date: 4-Dec-2024
https://doi.org/10.1007/978-3-031-78192-6_24
Liao NLuo SLi XShi JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)LD2Proceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666568(10197-10209)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666568
Elnaggar SElsemman ISoliman T(2023)Embedding-Based Deep Neural Network and Convolutional Neural Network Graph ClassifiersElectronics10.3390/electronics1212271512:12(2715)Online publication date: 17-Jun-2023
https://doi.org/10.3390/electronics12122715
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