On Valid Optimal Assignment Kernels and Applications to Graph Classification

By Nils M. Kriege, Pierre-Louis Giscard, Richard C. Wilson. 2016

224 citations recorded by the source corpus.

The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity. In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods. We characterize a class of base kernels used to compare parts that guarantees positive semidefinite optimal assignment kernels. These base kernels give rise to hierarchies from which the optimal assignment kernels are computed in linear time by histogram intersection. We apply these results by developing the Weisfeiler-Lehman optimal assignment kernel for graphs. It provides high classification accuracy on widely-used benchmark data sets improving over the original Weisfeiler-Lehman kernel.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Graph Learning

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 Graph Learning

Citations in the corpus

Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “Moreover, for WL and WL-OA we additionally selected the number of iteration from {0, . . . , 5}.”
An End-to-End Deep Learning Architecture for Graph Classification (2018, background): “(Kriege, Giscard, and Wilson 2016) proposed the optimal assignment kernels for a type of hierarchy-induced kernels.”
Covariant Compositional Networks For Learning Graphs (2018, methodology): “For our own method, second order CCN, we initialized the base features of each vertex with computed histogram alignment kernel features (Kriege et al., 2016) of depth up to 10.”
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).”
Optimal Transport for structured data with application on graphs (2018, methodology): “MUTAG (Debnath et al., 1991), PTC-MR (Kriege et al., 2016) (Kersting et al., 2016).”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, unknown): “Moreover, recently graph kernels using matchings [27] and geometric embeddings [28], [29] have been proposed.”
Contrastive Multi-View Representation Learning on Graphs (2020, background): “Graph kernels (Borgwardt & Kriegel, 2005; Shervashidze et al., 2009; 2011; Yanardag & Vishwana, 2015; Kondor & Pan, 2016; Kriege et al., 2016) decompose graphs into sub-structures and use kernel functions to measure graph similarity between them.”
A survey on graph kernels (2019, background): “Instead of generating feature vectors from prototypes, Kriege et al. (2016) showed that Eq.”
InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization (2019, background): “Furthermore, deep graph kernels [63], graph invariant kernels [43], optimal assignment graph kernels [28] and multiscale laplacian graph kernels [27] have been proposed with the goal to redefine kernel functions to appropriately capture sub-structural”
Learning Graph Representations with Recurrent Neural Network Autoencoders (2018, methodology): “Some methods shown in Tables 1 and 2 also use Weisfeiler-Lehman (graph2vec, WLSK, PSCN, and WL-OA) yet our approach outperforms them on average.”
Graph Capsule Convolutional Neural Networks (2018, background): “Furthermore, deep graph kernels (Yanardag & Vishwanathan, 2015), graph invariant kernels (Orsini et al., 2015), optimal assignment graph kernels (Kriege et al., 2016) and multiscale laplacian graph kernel (Kondor & Pan, 2016) have been proposed with the goal to re-define kernel functions to…”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, methodology): “On the small-scale datasets, see Table 1, the WL-OA performs best overall.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “…compare our kernels to the Weisfeiler-Leman subtree kernel ( 1 - WL ) (Shervashidze et al., 2011), the Weisfeiler-Leman Optimal Assignment kernel ( WLOA ) (Kriege et al., 2016), the graphlet kernel (Shervashidze et al., 2009) ( GR ), and the shortest-path kernel (Borgwardt & Kriegel, 2005) ( SP ).”
GroupINN: Grouping-based Interpretable Neural Network for Classification of Limited, Noisy Brain Data (2019, methodology): “To apply WL_OA kernel [19] for classification, we first obtain unweighted functional brain networks by thresholding the correlations at 0.”