Covariance and Correlation Kernels on a Graph in the Generalized Bag-of-Paths Formalism
This work provides a new method for computing node similarity in graphs, which is incremental as it builds on existing bag-of-paths formalisms to offer competitive results for applications like classification.
The paper tackles the problem of measuring similarity between nodes in a network by deriving closed-form expressions for covariance and correlation kernels based on co-occurrence expectations in a generalized bag-of-paths model, resulting in competitive performance in semi-supervised classification tasks.
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.