Wasserstein Weisfeiler-Lehman Graph Kernels

Abstract

Most graph kernels are an instance of the class of $\mathcal{R}$-Convolution kernels, which measure the similarity of objects by comparing their substructures. Despite their empirical success, most graph kernels use a naive aggregation of the final set of substructures, usually a sum or average, thereby potentially discarding valuable information about the distribution of individual components. Furthermore, only a limited instance of these approaches can be extended to continuously attributed graphs. We propose a novel method that relies on the Wasserstein distance between the node feature vector distributions of two graphs, which allows to find subtler differences in data sets by considering graphs as high-dimensional objects, rather than simple means. We further propose a Weisfeiler-Lehman inspired embedding scheme for graphs with continuous node attributes and weighted edges, enhance it with the computed Wasserstein distance, and thus improve the state-of-the-art prediction performance on several graph classification tasks.

arXiv commentAccepted as a Spotlight talk at the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019)

References in corpus (7)

• Learning with a Wasserstein Loss
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Subgraph Matching Kernels for Attributed Graphs
• On Valid Optimal Assignment Kernels and Applications to Graph Classification
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• The optimal assignment kernel is not positive definite
• On the Definiteness of Earth Mover's Distance and Its Relation to Set Intersection

Cited by in corpus (16)

• Graph Kernels: A Survey
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
• Graph Kernels: State-of-the-Art and Future Challenges
• Predicting binding motifs of complex adsorbates using machine learning with a physics-inspired graph representation
• A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
• Graph Similarity Description: How Are These Graphs Similar?
• On a linear fused Gromov-Wasserstein distance for graph structured data
• Revisiting 2D Convolutional Neural Networks for Graph-based Applications
• Adversarial Attacks on Graph Classification via Bayesian Optimisation
• Graph Homomorphism Convolution
• SMATCH++: Standardized and Extended Evaluation of Semantic Graphs
• Unsupervised Neighborhood Propagation Kernel Layers for Semi-supervised Node Classification
• Transition States Energies from Machine Learning: An Application to Reverse Water-Gas Shift on Single-Atom Alloys
• Interpretable machine learned predictions of adsorption energies at the metal--oxide interface
• Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations