Matching Node Embeddings for Graph Similarity

By Giannis Nikolentzos, Polykarpos Meladianos, Michalis Vazirgiannis. 2017

219 citations recorded by the source corpus.

Graph kernels have emerged as a powerful tool for graph comparison. Most existing graph kernels focus on local properties of graphs and ignore global structure. In this paper, we compare graphs based on their global properties as these are captured by the eigenvectors of their adjacency matrices. We present two algorithms for both labeled and unlabeled graph comparison. These algorithms represent each graph as a set of vectors corresponding to the embeddings of its vertices. The similarity between two graphs is then determined using the Earth Mover's Distance metric. These similarities do not yield a positive semidefinite matrix. To address for this, we employ an algorithm for SVM classification using indefinite kernels. We also present a graph kernel based on the Pyramid Match kernel that finds an approximate correspondence between the sets of vectors of the two graphs. We further improve the proposed kernel using the Weisfeiler-Lehman framework. We evaluate the proposed methods on several benchmark datasets for graph classification and compare their performance to state-of-the-art graph kernels. In most cases, the proposed algorithms outperform the competing methods, while their time complexity remains very attractive.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

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 Statistical and Nonlinear Physics

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 (Niko-lentzos et al. 2018).”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, methodology): “[50] consider node labels and edge labels”
A Degeneracy Framework for Graph Similarity (2018, background): “(4) pyramid match graph kernel (PM) [ Nikolentzos et al. , 2017b ] : The pyramid match graph kernel ﬁrst embeds the vertices of the input graphs in a vector space.”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, background): “Moreover, recently graph kernels using matchings [27] and geometric embeddings [28], [29] have been proposed.”
DeepEMD: Differentiable Earth Mover's Distance for Few-Shot Learning (2020, methodology): “siﬁcation [68]. Wang and Chan [69] propose to represent the hand shapes and textures with superpixels and employ EMD to measure the dissimilarity between the hand gestures for gesture recognition. In [70], Nikolentzos et al. represent graph data as a set of vectors corresponding to the vertices and ”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, background): “Further recent works focus on approaches based on assignments (Kriege et al., 2016; Nikolentzos et al., 2017), spectral properties (Kondor & Pan, 2016), graph decomposition (Nikolentzos et al.”
Anonymous Walk Embeddings (2018, background): “Graph classification is a task to predict a class label of a whole graph and it has found applications in bioinformatics (Nikolentzos et al., 2017) and malware detection (Narayanan et al.”
RetGK: Graph Kernels based on Return Probabilities of Random Walks (2018, methodology): “In [21], a class of graph kernels are developed based on the eigenvector embeddings.”
Graph Classification using Structural Attention (2018, methodology): “One popular approach is to use a graph kernel to measure similarity between different graphs [20].”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “Other recent works focus on assignment-based (Johansson & 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…”
Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network (2018, background): “For example, in graph embedding, DeepWalk [27], LINE [32], node2vec [12], and many more [23, 25, 26] all try to learn an embedding vector for each node in the graph, which can preserve the graph structure.”
SimGNN: A Neural Network Approach to Fast Graph Similarity Computation (2018, background): “een shown to be equivalent to 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 a”
Optimal Transport for structured data with application on graphs (2018, background): “In (Nikolentzos et al., 2017), authors propose a graph similarity measure for discrete labeled graph with OT.”
A survey on graph kernels (2019, methodology): “[45] proposed a matching-based approach based on the Earth Mover’s Distance, which results in an indefinite kernel function.”
Distance-Aware DAG Embedding for Proximity Search on Heterogeneous Graphs (2018, unknown): “Recent work uses graph embedding to do link prediction and proximity search; e.g., Deepwork (Perozzi, Al-Rfou, and Skiena 2014), LINE (Tang et al. 2015), node2vec (Grover and Leskovec 2016), and more (Zheng et al. 2016; Nie, Zhu, and Li 2017; Nikolentzos, Meladianos, and Vazirgiannis 2017).”