A Degeneracy Framework for Graph Similarity

By Giannis Nikolentzos, Polykarpos Meladianos, Stratis Limnios, Michalis Vazirgiannis. 2018

80 citations recorded by the source corpus.

The problem of accurately measuring the similarity between graphs is at the core of many applications in a variety of disciplines. Most existing methods for graph similarity focus either on local or on global properties of graphs. However, even if graphs seem very similar from a local or a global perspective, they may exhibit different structure at different scales. In this paper, we present a general framework for graph similarity which takes into account structure at multiple different scales. The proposed framework capitalizes on the well-known k-core decomposition of graphs in order to build a hierarchy of nested subgraphs. We apply the framework to derive variants of four graph kernels, namely graphlet kernel, shortest-path kernel, Weisfeiler-Lehman subtree kernel, and pyramid match graph kernel. The framework is not limited to graph kernels, but can be applied to any graph comparison algorithm. The proposed framework is evaluated on several benchmark datasets for graph classification. In most cases, the core-based kernels achieve significant improvements in terms of classification accuracy over the base kernels, while their time complexity remains very attractive.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Molecular Biology

Citations in the corpus

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “Recent works focus on assignment-based approaches (Kriege, Giscard, and Wilson 2016; Nikolentzos, Meladianos, and Vazirgiannis 2017; Johansson and Dubhashi 2015), spectral approaches (Kondor and Pan 2016), and graph decomposition approaches (Nikolentzos et al. 2018).”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “…& Dubhashi, 2015; Kriege et al., 2016; Nikolentzos et al., 2017), spectral (Kondor & Pan, 2016; Verma & Zhang, 2017), graph decomposition (Nikolentzos et al., 2018), randomized binning approaches (Heimann et al., 2019), and the extension of kernels based on the 1 - WL (Togninalli et al.,…”
SimGNN: A Neural Network Approach to Fast Graph Similarity Computation (2018, methodology): “o GED undera certain costfunction[5]. Graphkernels canbeconsidered asa familyofdiﬀerent graphsimilaritymetrics,usedprimarilyfor graph classiﬁcation. Numerous graph kernels [13, 20, 36] and extensions [35, 53] have been proposed across the years. Pairwise GED computation algorithms. A ﬂurry of approx”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, methodology): “…on approaches based on assignments (Kriege et al., 2016; Nikolentzos et al., 2017), spectral properties (Kondor & Pan, 2016), graph decomposition (Nikolentzos et al., 2018), randomized binning (Heimann et al., 2019), and the extension of kernels based on the Weisfeiler-Leman algorithm…”
A survey on graph kernels (2019, background): “Nikolentzos et al. (2018) proposed to first build the k -core decomposition of graphs to obtain a hierarchy of nested subgraphs, which are then individually compared by a graph similarity measure.”