Generalized Shortest Path Kernel on Graphs
We consider the problem of classifying graphs using graph kernels. We define a new graph kernel, called the generalized shortest path kernel, based on the number and length of shortest paths between nodes. For our example classification problem, we consider the task of classifying random graphs from two well-known families, by the number of clusters they contain. We verify empirically that the generalized shortest path kernel outperforms the original shortest path kernel on a number of datasets. We give a theoretical analysis for explaining our experimental results. In particular, we estimate distributions of the expected feature vectors for the shortest path kernel and the generalized shortest path kernel, and we show some evidence explaining why our graph kernel outperforms the shortest path kernel for our graph classification problem.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationGraph ClassificationSimilar Papers 제목 키워드 기반
Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification
Graph kernels are conventional methods for computing graph similarities. However, the existing R-convolution graph kernels cannot resolve both of the two challenges: 1) Comparing graphs at multiple different scales, and …
Graph ClassificationA Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, wher…
Generalized Shortest-Paths Encoders for AMR-to-Text Generation
For text generation from semantic graphs, past neural models encoded input structure via gated convolutions along graph edges. Although these operations provide local context, the distance messages can travel is bounded …
AMR-to-Text GenerationDiversityText GenerationThe All-Paths and Cycles Graph Kernel
With the recent rise in the amount of structured data available, there has been considerable interest in methods for machine learning with graphs. Many of these approaches have been kernel methods, which focus on measuri…
AllScalable kernels for graphs with continuous attributes
While graphs with continuous node attributes arise in many applications, state-of-the-art graph kernels for comparing continuous-attributed graphs suffer from a high runtime complexity; for instance, the popular shortest…
General Classification