Measuring Graph Similarity Using Transfer Cost of Forster Distributions

Abstract

In recent years, optimal transport-based distance metrics have shown to be effective similarity and dissimilarity measures for tackling learning problems involving network data. Prominent examples range from graph classification and community detection to object matching. However, the high computational complexity of calculating optimal transport costs substantially confines their applications to large-scale networks. To address this challenge, in this paper, we introduce a probability distribution on the set of edges of a graph, referred to as the Foster distribution of the graph, by extending Foster's theorem from electrical to general networks. Then, we represent Foster distributions as probability measures on the real line and estimate the Wasserstein metric between the corresponding probability measures to quantify graph similarity. The applicability of the proposed approach is corroborated on diverse graph-structured datasets, through which we particularly demonstrate the high efficiency of computing the proposed graph distance for sparse graphs.