# On Valid Optimal Assignment Kernels and Applications to Graph Classification

arXiv: https://arxiv.org/abs/1606.01141 · HTML: https://mlsanity.com/paper/1606.01141/

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2016.

## Built on by (most cited first, 30 of 49)

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Multiresolution Equivariant Graph Variational Autoencoder](https://mlsanity.com/paper/2106.00967/) (2021)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022)
- [Boosting Graph Structure Learning with Dummy Nodes](https://mlsanity.com/paper/2206.08561/) (2022)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [A Unified View of Evaluation Metrics for Structured Prediction](https://mlsanity.com/paper/2310.13793/) (2023)
- [A Generalized Weisfeiler-Lehman Graph Kernel](https://mlsanity.com/paper/2101.08104/) (2021)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Topological Pooling on Graphs](https://mlsanity.com/paper/2303.14543/) (2023)
- [Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Information](https://mlsanity.com/paper/2406.19244/) (2024)
- [Learning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels](https://mlsanity.com/paper/2106.04739/) (2021)
- [Graph Filtration Kernels](https://mlsanity.com/paper/2110.11862/) (2021)
- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)
- [Fast Attributed Graph Embedding via Density of States](https://mlsanity.com/paper/2110.05228/) (2021)
- [Wasserstein Graph Distance Based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees](https://mlsanity.com/paper/2207.04216/) (2022)
- [On the Two Sides of Redundancy in Graph Neural Networks](https://mlsanity.com/paper/2310.04190/) (2023)
- [EMP: Effective Multidimensional Persistence for Graph Representation Learning](https://mlsanity.com/paper/2401.13713/) (2024)
- [Subsampling Graphs with GNN Performance Guarantees](https://mlsanity.com/paper/2502.16703/) (2025)
- [Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information Maximization Network](https://mlsanity.com/paper/2302.02369/) (2023)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [A Stein Goodness of fit Test for Exponential Random Graph Models](https://mlsanity.com/paper/2103.00580/) (2021)
- [On RKHS Choices for Assessing Graph Generators via Kernel Stein Statistics](https://mlsanity.com/paper/2210.05746/) (2022)
- [Pattern Mining for Anomaly Detection in Graphs: Application to Fraud in Public Procurement](https://mlsanity.com/paper/2306.10857/) (2023)
- [Evaluating machine learning models for predicting pesticide toxicity to honey bees](https://mlsanity.com/paper/2503.24305/) (2025)
- [Global optimization of graph acquisition functions for neural architecture search](https://mlsanity.com/paper/2505.23640/) (2025)

## Abstract (arXiv)

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.