The Spectral Barycentre of a Set of Graphs with Community Structure
This work addresses the challenge of summarizing graph-valued data for machine learning applications, but it is incremental as it builds on existing spectral methods with specific constraints.
The authors tackled the problem of constructing a barycentre graph that summarizes a dataset of graphs with community structure, using a multiscale spectral distance and structural constraints on eigenvectors, resulting in a barycentre that asymptotically converges to the population mean for stochastic block models and performs well in real-life experiments.
The notion of barycentre graph is of crucial importance for machine learning algorithms that process graph-valued data. The barycentre graph is a "summary graph" that captures the mean topology and connectivity structure of a training dataset of graphs. The construction of a barycentre requires the definition of a metric to quantify distances between pairs of graphs. In this work, we use a multiscale spectral distance that is defined using the eigenvalues of the normalized graph Laplacian. The eigenvalues -- but not the eigenvectors -- of the normalized Laplacian of the barycentre graph can be determined from the optimization problem that defines the barycentre. In this work, we propose a structural constraint on the eigenvectors of the normalized graph Laplacian of the barycentre graph that guarantees that the barycentre inherits the topological structure of the graphs in the sample dataset. The eigenvectors can be computed using an algorithm that explores the large library of Soules bases. When the graphs are random realizations of a balanced stochastic block model, then our algorithm returns a barycentre that converges asymptotically (in the limit of large graph size) almost-surely to the population mean of the graphs. We perform Monte Carlo simulations to validate the theoretical properties of the estimator; we conduct experiments on real-life graphs that suggest that our approach works beyond the controlled environment of stochastic block models.