Graph Kernels based on Linear Patterns: Theoretical and Experimental Comparisons. Jia, L., Gaüzère, B., & Honeine, P. In Poster presented at the Machine Learning Summer School, Universidad Autonoma de Madrid, Madrid, Spain, 27~August–7~September, 2018.
abstract   bibtex   
Graph kernel is a powerful tool to bridge the gap between machine learning and data encoded as graphs. Most graph kernels are based on a decomposition of graphs into a set of patterns. The similarity between graphs is then deduced from the similarity of corresponding patterns. Among different possible sets of patterns, linear patterns based kernels often constitute a good trade off between time consumption and accuracy performance. In this work, we propose a thorough study and comparison of the existing graph kernels based on different linear patterns, namely walks and paths. This work leads to a clear comparison of pros and cons of different proposed kernels. First, all graph kernels are studied in detail, including their mathematical foundation, structures of patterns and time complexity. Relationships among these kernels are studied with respect to their development history and mathematical representations. Then, experiments are performed on various datasets exhibiting different kinds of graphs, including labeled and unlabeled graphs, graphs with different numbers of nodes, graphs with different average degrees, cyclic and acyclic graphs, planar and non-planar graphs. Finally, performance and time complexity of kernels are compared and analyzed on these graphs, and suggestions are proposed to choose kernels according to the type of graph data. An open source python library containing an implementation of all discussed kernels is publicly available on Github to the community, so as to promote and facilitate the use of graph kernels in machine learning problems.
@INPROCEEDINGS{18.mlss,
   author =  "Linlin Jia and Benoit Gaüzère and Paul Honeine",
   title =  "Graph Kernels based on Linear Patterns: Theoretical and Experimental Comparisons",
   booktitle =  "Poster presented at the Machine Learning Summer School, Universidad Autonoma de Madrid",
   address =  "Madrid, Spain",
   year =  "2018",
   month =  "27~" # aug # "--" # "7~" # sep,
   keywords =  "machine learning, graphs, graph data",
   acronym =  "MLSS",
   abstract = "Graph kernel is a powerful tool to bridge the gap between machine learning and data encoded as graphs. Most graph kernels are based on a decomposition of graphs into a set of patterns. The similarity between graphs is then deduced from the similarity of corresponding patterns. Among different possible sets of patterns, linear patterns based kernels often constitute a good trade off between time consumption and accuracy performance. In this work, we propose a thorough study and comparison of the existing graph kernels based on different linear patterns, namely walks and paths. This work leads to a clear comparison of pros and cons of different proposed kernels. First, all graph kernels are studied in detail, including their mathematical foundation, structures of patterns and time complexity. Relationships among these kernels are studied with respect to their development history and mathematical representations. Then, experiments are performed on various datasets exhibiting different kinds of graphs, including labeled and unlabeled graphs, graphs with different numbers of nodes, graphs with different average degrees, cyclic and acyclic graphs, planar and non-planar graphs. Finally, performance and time complexity of kernels are compared and analyzed on these graphs, and suggestions are proposed to choose kernels according to the type of graph data. An open source python library containing an implementation of all discussed kernels is publicly available on Github to the community, so as to promote and facilitate the use of graph kernels in machine learning problems.",
}%misc{

Downloads: 0