# Propagation Kernels

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

## Key facts

- Cited by 88 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2014.

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

- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation](https://mlsanity.com/paper/2112.10063/) (2021)
- [KerGNNs: Interpretable Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/2201.00491/) (2022)
- [GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection](https://mlsanity.com/paper/2211.04208/) (2022)
- [CoCo: A Coupled Contrastive Framework for Unsupervised Domain Adaptive Graph Classification](https://mlsanity.com/paper/2306.04979/) (2023)
- [Raising the Bar in Graph-level Anomaly Detection](https://mlsanity.com/paper/2205.13845/) (2022)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Cell Attention Networks](https://mlsanity.com/paper/2209.08179/) (2022)
- [Probabilistically Rewired Message-Passing Neural Networks](https://mlsanity.com/paper/2310.02156/) (2023)
- [A New Perspective on the Effects of Spectrum in Graph Neural Networks](https://mlsanity.com/paper/2112.07160/) (2021)
- [Improving Graph Neural Networks with Learnable Propagation Operators](https://mlsanity.com/paper/2210.17224/) (2022)
- [Unifying Unsupervised Graph-Level Anomaly Detection and Out-of-Distribution Detection: A Benchmark](https://mlsanity.com/paper/2406.15523/) (2024)
- [GOODAT: Towards Test-time Graph Out-of-Distribution Detection](https://mlsanity.com/paper/2401.06176/) (2024)
- [Graph-level Anomaly Detection via Hierarchical Memory Networks](https://mlsanity.com/paper/2307.00755/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes](https://mlsanity.com/paper/2309.12971/) (2023)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [CIN++: Enhancing Topological Message Passing](https://mlsanity.com/paper/2306.03561/) (2023)
- [Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks](https://mlsanity.com/paper/2311.01038/) (2023)
- [Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedy](https://mlsanity.com/paper/2410.20366/) (2024)
- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes](https://mlsanity.com/paper/2308.06838/) (2023)
- [CVTGAD: Simplified Transformer with Cross-View Attention for Unsupervised Graph-level Anomaly Detection](https://mlsanity.com/paper/2405.02359/) (2024)
- [Graph Anomaly Detection with Unsupervised GNNs](https://mlsanity.com/paper/2210.09535/) (2022)
- [Graph Neural Networks based Log Anomaly Detection and Explanation](https://mlsanity.com/paper/2307.00527/) (2023)
- [Hypergraph-enhanced Dual Semi-supervised Graph Classification](https://mlsanity.com/paper/2405.04773/) (2024)

## Abstract (arXiv)

We introduce propagation kernels, a general graph-kernel framework for efficiently measuring the similarity of structured data. Propagation kernels are based on monitoring how information spreads through a set of given graphs. They leverage early-stage distributions from propagation schemes such as random walks to capture structural information encoded in node labels, attributes, and edge information. This has two benefits. First, off-the-shelf propagation schemes can be used to naturally construct kernels for many graph types, including labeled, partially labeled, unlabeled, directed, and attributed graphs. Second, by leveraging existing efficient and informative propagation schemes, propagation kernels can be considerably faster than state-of-the-art approaches without sacrificing predictive performance. We will also show that if the graphs at hand have a regular structure, for instance when modeling image or video data, one can exploit this regularity to scale the kernel computation to large databases of graphs with thousands of nodes. We support our contributions by exhaustive experiments on a number of real-world graphs from a variety of application domains.