Giannis Nikolentzos
ABSTRACT
Graph kernels have recently emerged as a promising approach to perform machine learning on graph-structured data. A graph kernel implicitly embedds graphs in a Hilbert space and computes the inner product between these representations. However, the inner product operation greatly limits the representational power of kernels between graphs. In this paper, we propose to perform a series of successive embeddings in order to improve the performance of existing graph kernels and derive more expressive kernels. We first embed the input graphs in a Hilbert space using a graph kernel and then we embed them into another space by employing popular kernels for vector data (e.g., gaussian kernel). Our experiments on several datasets show that by composing kernels, we can achieve significant improvements in classification accuracy.
- Karsten M Borgwardt and Hans-Peter Kriegel. 2005. Shortest-path kernels on graphs. In Proceedings of the 5th International Conference on Data Mining. 74--81. Google Scholar
Digital Library
- Thomas G"artner, Peter Flach, and Stefan Wrobel. 2003. On Graph Kernels: Hardness Results and Efficient Alternatives . In Learning Theory and Kernel Machines . 129--143.Google Scholar
- Tamás Horváth, Thomas G"artner, and Stefan Wrobel. 2004. Cyclic Pattern Kernels for Predictive Graph Mining. In Proceedings of the 10th International Conference on Knowledge Discovery and Data Mining . 158--167. Google ScholarDigital Library
- Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhattacharyya. 2014. Global graph kernels using geometric embeddings. In Proceedings of the 31st International Conference on Machine Learning. 694--702. Google ScholarDigital Library
- Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. 2003. Marginalized Kernels Between Labeled Graphs. In Proceedings of the 20th Conference in Machine Learning. 321--328. Google ScholarDigital Library
- Risi Kondor and Horace Pan. 2016. The Multiscale Laplacian Graph Kernel. In Advances in Neural Information Processing Systems. 2982--2990. Google ScholarDigital Library
- Giannis Nikolentzos, Polykarpos Meladianos, Stratis Limnios, and Michalis Vazirgiannis. 2018. A Degeneracy Framework for Graph Similarity. In Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2595--2601.Google ScholarCross Ref
- Giannis Nikolentzos, Polykarpos Meladianos, Francc ois Rousseau, Yannis Stavrakas, and Michalis Vazirgiannis. 2017b. Shortest-Path Graph Kernels for Document Similarity. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing . 1890--1900.Google ScholarCross Ref
- Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2017a. Matching Node Embeddings for Graph Similarity . In Proceedings of the 31st Conference on Artificial Intelligence. 2429--2435.Google Scholar
- Jan Ramon and Thomas G"artner. 2003. Expressivity versus efficiency of graph kernels. In Proceedings of the 1st International Workshop on Mining Graphs, Trees and Sequences. 65--74.Google Scholar
- Bernhard Schölkopf, Koji Tsuda, and Jean-Philippe Vert. 2004. Kernel Methods in Computational Biology .MIT press.Google Scholar
- John Shawe-Taylor and Nello Cristianini. 2004. Kernel Methods for Pattern Analysis. Cambridge University Press. Google ScholarDigital Library
- 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, Sep (2011), 2539--2561. Google ScholarDigital Library
- Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M Borgwardt. 2009. Efficient Graphlet Kernels for Large Graph Comparison. In Proceedings of the International Conference on Artificial Intelligence and Statistics . 488--495.Google Scholar
- Mahito Sugiyama and Karsten Borgwardt. 2015. Halting in Random Walk Kernels. In Advances in Neural Information Processing Systems. 1639--1647. Google ScholarDigital Library
- Pinar Yanardag and SVN Vishwanathan. 2015a. A Structural Smoothing Framework For Robust Graph-Comparison. In Advances in Neural Information Processing Systems. 2134--2142. Google ScholarDigital Library
- Pinar Yanardag and SVN Vishwanathan. 2015b. Deep Graph Kernels. In Proceedings of the 21th International Conference on Knowledge Discovery and Data Mining. 1365--1374. Google ScholarDigital Library
Index Terms
- Enhancing Graph Kernels via Successive Embeddings
Recommendations
DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
WWW '19: The World Wide Web ConferenceCan 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). ...
Machine Learning on Graphs with Kernels
CIKM '19: Proceedings of the 28th ACM International Conference on Information and Knowledge ManagementGraphs are becoming a dominant structure in current information management with many domains involved, including social networks, chemistry, biology, etc. Many real-world problems require applying machine learning tasks to graph-structured data. Graph ...
A Truss-Based Framework for Graph Similarity Computation
The study of graph kernels has been an important area of graph analysis, which is widely used to solve the similarity problems between graphs. Most of the existing graph kernels consider either local or global properties of the graph, and there are ...
Comments