Wasserstein Embedding for Graph Learning
arXiv:2006.09430
Abstract
We present Wasserstein Embedding for Graph Learning (WEGL), a novel and fast framework for embedding entire graphs in a vector space, in which various machine learning models are applicable for graph-level prediction tasks. We leverage new insights on defining similarity between graphs as a function of the similarity between their node embedding distributions. Specifically, we use the Wasserstein distance to measure the dissimilarity between node embeddings of different graphs. Unlike prior work, we avoid pairwise calculation of distances between graphs and reduce the computational complexity from quadratic to linear in the number of graphs. WEGL calculates Monge maps from a reference distribution to each node embedding and, based on these maps, creates a fixed-sized vector representation of the graph. We evaluate our new graph embedding approach on various benchmark graph-property prediction tasks, showing state-of-the-art classification performance while having superior computational efficiency. The code is available at https://github.com/navid-naderi/WEGL.
arXiv commentFinal version to be presented at the Ninth International Conference on Learning Representations (ICLR 2021)
References in corpus (24)
- Semi-Supervised Classification with Graph Convolutional Networks
- Fast Graph Representation Learning with PyTorch Geometric
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Fast Computation of Wasserstein Barycenters
- A Survey on Graph Kernels
- DeeperGCN: All You Need to Train Deeper GCNs
- Predicting Organic Reaction Outcomes with Weisfeiler-Lehman Network
- Strategies for Pre-training Graph Neural Networks
- Optimal Transport for structured data with application on graphs
- Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
- Anonymous Walk Embeddings
- On Valid Optimal Assignment Kernels and Applications to Graph Classification
- A Fair Comparison of Graph Neural Networks for Graph Classification
- The Multiscale Laplacian Graph Kernel
- Machine Learning on Graphs: A Model and Comprehensive Taxonomy
- Measuring the Algorithmic Efficiency of Neural Networks
- GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
- GOT: An Optimal Transport framework for Graph comparison
- Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings
- RetGK: Graph Kernels based on Return Probabilities of Random Walks
- Hierarchical Inter-Message Passing for Learning on Molecular Graphs
- Principal Geodesic Analysis for Probability Measures under the Optimal Transport Metric
- Optimal Transport Graph Neural Networks
- A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention