Topology Based Scalable Graph Kernels
This method addresses graph analysis for domains lacking node attributes, but it appears incremental as it builds on existing curvature concepts.
The authors tackled the problem of graph classification and comparison by proposing a new graph kernel based on Ollivier Ricci curvature, which uses edge curvature distributions derived from graph topology, and they reported that it works effectively in settings without node attributes.
We propose a new graph kernel for graph classification and comparison using Ollivier Ricci curvature. The Ricci curvature of an edge in a graph describes the connectivity in the local neighborhood. An edge in a densely connected neighborhood has positive curvature and an edge serving as a local bridge has negative curvature. We use the edge curvature distribution to form a graph kernel which is then used to compare and cluster graphs. The curvature kernel uses purely the graph topology and thereby works for settings when node attributes are not available.