Clustering Graphs Using Minimum Factorization Distance.

Abstract

Clustering graphs into different groups is a challenging problem due to the difficulty in quantifying the similarity or distance between graphs, especially when the graphs are large. In this work, we propose a novel approach by treating the adjacency matrices of two graphs as kernel matrices derived from some unknown indefinite kernel function applied to two discrete distributions. Based on this view, we define a measure called MMFD to quantify the dissimilarity between graphs via the distance between their underlying distributions. We prove that MMFD is a pseudo-metric. Although the initial formulation of MMFD appears complex, we demonstrate that it admits a computationally simple closed-form solution. To enhance efficiency in large-scale clustering tasks, we further propose MMFD-KM, a method with linear time and space complexity relative to the number of graphs. Additionally, we introduce a generalized version named MFD and its variant MFD$_{\rm{OT}}$, with theoretical guarantees, which more effectively leverage factor information from adjacency matrices. Based on MFD, an efficient graph clustering algorithm called MFD-KD is established. Experiments on synthetic graphs visually confirm the effectiveness of our methods in graph comparison. Results on 18 real-world datasets show that our approaches significantly outperform competing methods in clustering performance across three evaluation metrics, while also reducing computational time.