# Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison](https://mlsanity.com/paper/2108.10004/) (2021)
- [Dissecting graph measure performance for node clustering in LFR parameter space](https://mlsanity.com/paper/2202.09827/) (2022)

## Abstract (arXiv)

This work derives closed-form expressions computing the expectation of co-presence and of number of co-occurrences of nodes on paths sampled from a network according to general path weights (a bag of paths). The underlying idea is that two nodes are considered as similar when they often appear together on (preferably short) paths of the network. The different expressions are obtained for both regular and hitting paths and serve as a basis for computing new covariance and correlation measures between nodes, which are valid positive semi-definite kernels on a graph. Experiments on semi-supervised classification problems show that the introduced similarity measures provide competitive results compared to other state-of-the-art distance and similarity measures between nodes.