Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding

ABSTRACT

Graph kernels are widely used for measuring the similarity between graphs. Many existing graph kernels, which focus on local patterns within graphs rather than their global properties, suffer from significant structure information loss when representing graphs. Some recent global graph kernels, which utilizes the alignment of geometric node embeddings of graphs, yield state-of-the-art performance. However, these graph kernels are not necessarily positive-definite. More importantly, computing the graph kernel matrix will have at least quadratic time complexity in terms of the number and the size of the graphs. In this paper, we propose a new family of global alignment graph kernels, which take into account the global properties of graphs by using geometric node embeddings and an associated node transportation based on earth mover's distance. Compared to existing global kernels, the proposed kernel is positive-definite. Our graph kernel is obtained by defining a distribution over random graphs, which can naturally yield random feature approximations. The random feature approximations lead to our graph embeddings, which is named as "random graph embeddings" (RGE). In particular, RGE is shown to achieve (quasi-)linear scalability with respect to the number and the size of the graphs. The experimental results on nine benchmark datasets demonstrate that RGE outperforms or matches twelve state-of-the-art graph classification algorithms.

References

1. Rami Al-Rfou, Dustin Zelle, and Bryan Perozzi. 2019. DDGK: Learning Graph Representations for Deep Divergence Graph Kernels. arXiv:1904.09671 (2019).
2. James Atwood, Siddharth Pal, Don Towsley, and Ananthram Swami. 2016. Sparse Diffusion-Convolutional Neural Networks. In NIPS.
3. Francis Bach. 2017. On the equivalence between kernel quadrature rules and random feature expansions. Journal of Machine Learning Research 18, 21 (2017), 1--38.
4. Karsten M Borgwardt and Hans-Peter Kriegel. 2005. Shortest-path kernels on graphs. In Data Mining, Fifth IEEE International Conference on. IEEE, 8--pp.
5. Francois Bourgeois and Jean-Claude Lassalle. 1971. An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Commun. ACM 14, 12 (1971), 802--804.
6. Pin-Yu Chen and Lingfei Wu. 2017. Revisiting spectral graph clustering with generative community models. In ICDM. 51--60.
7. Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. 2008. LIBLINEAR: A library for large linear classification. Journal of machine learning research 9, Aug (2008), 1871--1874.
8. Matthew Fisher, Manolis Savva, and Pat Hanrahan. 2011. Characterizing struc- tural relationships in scenes using graph kernels. ACM Transactions on Graphics (TOG) 30, 4 (2011), 34.
9. Thomas Gartner, Peter Flach, and Stefan Wrobel. 2003. On graph kernels: Hard- ness results and efficient alternatives. In Learning Theory and Kernel Machines. Springer, 129--143.
10. David Haussler. 1999. Convolution kernels on discrete structures. Technical Report. Department of Computer Science, University of California at Santa Cruz.
11. Frank L Hitchcock. 1941. The distribution of a product from several sources to numerous localities. Studies in Applied Mathematics 20, 1--4 (1941), 224--230.
12. Tama's Horvath, Thomas Gartner, and Stefan Wrobel. 2004. Cyclic pattern kernels for predictive graph mining. In KDD. ACM, 158--167.
13. Catalin Ionescu, Alin Popa, and Cristian Sminchisescu. 2017. Large-scale data- dependent kernel approximation. In Artificial Intelligence and Statistics. 19--27.
14. Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhat- tacharyya. 2014. Global graph kernels using geometric embeddings. In ICML.
15. Fredrik D Johansson and Devdatt Dubhashi. 2015. Learning with similarity functions on graphs using matchings of geometric embeddings. In KDD. ACM, 467--476.
16. Risi Kondor and Horace Pan. 2016. The multiscale laplacian graph kernel. In NIPS. 2990--2998.
17. Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. 2016. On valid optimal assignment kernels and applications to graph classification. In NIPS. 1623--1631. {18} Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. 2015. From word embeddings to document distances. In ICML. 957--966.
18. Quoc Le, Tama's Sarlo's, and Alex Smola. 2013. Fastfood-approximating kernel expansions in loglinear time. In ICML, Vol. 85.
19. La'szlo Lova'sz. 1979. On the Shannon capacity of a graph. IEEE Transactions on Information theory 25, 1 (1979), 1--7.
20. Fatemeh Mokhtari and Gholam-Ali Hossein-Zadeh. 2013. Decoding brain states using backward edge elimination and graph kernels in fMRI connectivity net- works. Journal of neuroscience methods 212, 2 (2013), 259--268.
21. Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016. Learning convolutional neural networks for graphs. In ICML. 2014--2023.
22. Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2017. Matching Node Embeddings for Graph Similarity.. In AAAI. 2429--2435.
23. Ali Rahimi and Benjamin Recht. 2008. Random features for large-scale kernel machines. In NIPS. 1177--1184.
24. Liva Ralaivola, Sanjay J Swamidass, Hiroto Saigo, and Pierre Baldi. 2005. Graph kernels for chemical informatics. Neural networks 18, 8 (2005), 1093--1110.
25. Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. 2000. The earth mover's distance as a metric for image retrieval. International journal of computer vision 40, 2 (2000), 99--121.
26. Alessandro Rudi and Lorenzo Rosasco. 2017. Generalization properties of learning with random features. In NIPS. 3218--3228.
27. Nino Shervashidze and Karsten M Borgwardt. 2009. Fast subtree kernels on graphs. In NIPS. 1660--1668.
28. 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, Sep (2011), 2539--2561.
29. NinoShervashidze,SVNVishwanathan,TobiasPetri,KurtMehlhorn,andKarsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In AIStats. 488--495.
30. Aman Sinha and John C Duchi. 2016. Learning kernels with random features. In NIPS. 1298--1306.
31. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. 2016. Continuous-flow graph transportation distances. arXiv:1603.06927 (2016).
32. Andreas Stathopoulos and James R McCombs. 2010. PRIMME: preconditioned iterative multimethod eigensolveraATmethods and software description. ACM Transactions on Mathematical Software (TOMS) 37, 2 (2010), 21.
33. S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. 2010. Graph kernels. Journal of Machine Learning Research 11 (2010), 1201--1242.
34. Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing 17, 4 (2007), 395--416.
35. Cynthia Wagner, Gerard Wagener, Radu State, and Thomas Engel. 2009. Malware analysis with graph kernels and support vector machines. In Malicious and Unwanted Software, 2009 4th International Conference on. IEEE, 63--68.
36. Ling Wang and Hichem Sahbi. 2013. Directed acyclic graph kernels for action recognition. In ICCV. IEEE, 3168--3175.
37. Bo Wu, Yang Liu, Bo Lang, and Lei Huang. 2017. DGCNN: Disordered Graph Convolutional Neural Network Based on the Gaussian Mixture Model. arXiv:1712.03563 (2017).
38. Lingfei Wu, Pin-Yu Chen, Ian En-Hsu Yen, Fangli Xu, Yinglong Xia, and Charu Aggarwal. 2018. Scalable spectral clustering using random binning features. In KDD. ACM, 2506--2515.
39. Lingfei Wu, Eloy Romero, and Andreas Stathopoulos. 2017. PRIMME_SVDS: A high-performance preconditioned SVD solver for accurate large-scale computa- tions. SIAM Journal on Scientific Computing 39, 5 (2017), S248--S271.
40. Lingfei Wu, Ian EH Yen, Jie Chen, and Rui Yan. 2016. Revisiting random binning features: Fast convergence and strong parallelizability. In KDD. ACM, 1265--1274.
41. Lingfei Wu, Ian En-Hsu Yen, Fangli Xu, Pradeep Ravikuma, and Michael Wit- brock. 2018. D2KE: From Distance to Kernel and Embedding. arXiv preprint arXiv:1802.04956 (2018).
42. Lingfei Wu, Ian En-Hsu Yen, Jinfeng Yi, Fangli Xu, Qi Lei, and Michael Witbrock. 2018. Random Warping Series: A Random Features Method for Time-Series Embedding. In International Conference on Artificial Intelligence and Statistics. 793--802.
43. Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. In KDD. ACM, 1365--1374.
44. Pinar Yanardag and SVN Vishwanathan. 2015. A structural smoothing framework for robust graph comparison. In NIPS. 2134--2142.
45. Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. 2018. RetGK: Graph Kernels based on Return Probabilities of Random Walks. In NIPS. 3968--3978.

Index Terms

• Computing methodologies

  • Machine learning

    • Machine learning approaches

      • Kernel methods