Statistical and Machine Learning Approaches for Network Analysis

8.4 Path-Based Graph Kernels

Path-based graph kernels are similar to random walk kernels, but use paths instead of walks. A path is a walk that contains each vertex at most once. Path kernels therefore do not suffer from either tottering (by definition) or halting, as the number of paths is finite and paths thus do not have to be downweighted to ensure convergence. Through this, path-based kernels have one free parameter less than random walk graph kernels.

8.4.1 Definition and Computation

Let P(G) denote the set of all paths in G, and let k_z be a kernel defined on the corresponding label sequences as in Equation 8.7. The all-paths graph kernel

(8.12)

is an R-convolution kernel [1], and therefore positive definite. However, enumerating all paths in a graph is NP-hard, as it would allow to decide whether a graph contains a Hamiltonian path (a path that visits each vertex once), a known NP-complete problem [1]. The same reasoning holds for the restriction to longest paths.

Shortest paths, however, can be computed in polynomial time [68], for example, by the Floyd–Warshall algorithm, which solves the all-pairs-shortest path problem in time O(|V|³). Let G = (V, E) denote an edge-weighted graph. Its shortest-path graph has an edge between two vertices if and only if there is a path between ...