Global graph kernels using geometric embeddings

Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, Chiranjib Bhattacharyya
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):694-702, 2014.

Abstract

Applications of machine learning methods increasingly deal with graph structured data through kernels. Most existing graph kernels compare graphs in terms of features defined on small subgraphs such as walks, paths or graphlets, adopting an inherently local perspective. However, several interesting properties such as girth or chromatic number are global properties of the graph, and are not captured in local substructures. This paper presents two graph kernels defined on unlabeled graphs which capture global properties of graphs using the celebrated Lovász number and its associated orthonormal representation. We make progress towards theoretical results aiding kernel choice, proving a result about the separation margin of our kernel for classes of graphs. We give empirical results on classification of synthesized graphs with important global properties as well as established benchmark graph datasets, showing that the accuracy of our kernels is better than or competitive to existing graph kernels.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-johansson14, title = {Global graph kernels using geometric embeddings}, author = {Johansson, Fredrik and Jethava, Vinay and Dubhashi, Devdatt and Bhattacharyya, Chiranjib}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {694--702}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/johansson14.pdf}, url = {https://proceedings.mlr.press/v32/johansson14.html}, abstract = {Applications of machine learning methods increasingly deal with graph structured data through kernels. Most existing graph kernels compare graphs in terms of features defined on small subgraphs such as walks, paths or graphlets, adopting an inherently local perspective. However, several interesting properties such as girth or chromatic number are global properties of the graph, and are not captured in local substructures. This paper presents two graph kernels defined on unlabeled graphs which capture global properties of graphs using the celebrated Lovász number and its associated orthonormal representation. We make progress towards theoretical results aiding kernel choice, proving a result about the separation margin of our kernel for classes of graphs. We give empirical results on classification of synthesized graphs with important global properties as well as established benchmark graph datasets, showing that the accuracy of our kernels is better than or competitive to existing graph kernels.} }
Endnote
%0 Conference Paper %T Global graph kernels using geometric embeddings %A Fredrik Johansson %A Vinay Jethava %A Devdatt Dubhashi %A Chiranjib Bhattacharyya %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-johansson14 %I PMLR %P 694--702 %U https://proceedings.mlr.press/v32/johansson14.html %V 32 %N 2 %X Applications of machine learning methods increasingly deal with graph structured data through kernels. Most existing graph kernels compare graphs in terms of features defined on small subgraphs such as walks, paths or graphlets, adopting an inherently local perspective. However, several interesting properties such as girth or chromatic number are global properties of the graph, and are not captured in local substructures. This paper presents two graph kernels defined on unlabeled graphs which capture global properties of graphs using the celebrated Lovász number and its associated orthonormal representation. We make progress towards theoretical results aiding kernel choice, proving a result about the separation margin of our kernel for classes of graphs. We give empirical results on classification of synthesized graphs with important global properties as well as established benchmark graph datasets, showing that the accuracy of our kernels is better than or competitive to existing graph kernels.
RIS
TY - CPAPER TI - Global graph kernels using geometric embeddings AU - Fredrik Johansson AU - Vinay Jethava AU - Devdatt Dubhashi AU - Chiranjib Bhattacharyya BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-johansson14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 694 EP - 702 L1 - http://proceedings.mlr.press/v32/johansson14.pdf UR - https://proceedings.mlr.press/v32/johansson14.html AB - Applications of machine learning methods increasingly deal with graph structured data through kernels. Most existing graph kernels compare graphs in terms of features defined on small subgraphs such as walks, paths or graphlets, adopting an inherently local perspective. However, several interesting properties such as girth or chromatic number are global properties of the graph, and are not captured in local substructures. This paper presents two graph kernels defined on unlabeled graphs which capture global properties of graphs using the celebrated Lovász number and its associated orthonormal representation. We make progress towards theoretical results aiding kernel choice, proving a result about the separation margin of our kernel for classes of graphs. We give empirical results on classification of synthesized graphs with important global properties as well as established benchmark graph datasets, showing that the accuracy of our kernels is better than or competitive to existing graph kernels. ER -
APA
Johansson, F., Jethava, V., Dubhashi, D. & Bhattacharyya, C.. (2014). Global graph kernels using geometric embeddings. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):694-702 Available from https://proceedings.mlr.press/v32/johansson14.html.

Related Material