# The Spectral Barycentre of a Set of Graphs with Community Structure

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 82 references that are in the map.
- First posted on arXiv 26 Jan 2025.

## Builds on (most cited first, 30 of 30)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Fr'echet Regression for Random Objects with Euclidean Predictors](https://mlsanity.com/paper/1608.03012/) (2016)
- [Stochastic blockmodel approximation of a graphon: Theory and consistent estimation](https://mlsanity.com/paper/1311.1731/) (2013)
- [Metrics for Graph Comparison: A Practitioner's Guide](https://mlsanity.com/paper/1904.07414/) (2019)
- [Learning Graphons via Structured Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2012.05644/) (2020)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [A network approach to topic models](https://mlsanity.com/paper/1708.01677/) (2017)
- [Strong Consistency, Graph Laplacians, and the Stochastic Block Model](https://mlsanity.com/paper/2004.09780/) (2020)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [Hypothesis Testing For Network Data in Functional Neuroimaging](https://mlsanity.com/paper/1407.5525/) (2014)
- [Permutation Invariant Representations with Applications to Graph Deep Learning](https://mlsanity.com/paper/2203.07546/) (2022)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Two-sample Hypothesis Testing for Inhomogeneous Random Graphs](https://mlsanity.com/paper/1707.00833/) (2017)
- [Can co-location be used as a proxy for face-to-face contacts?](https://mlsanity.com/paper/1712.06346/) (2017)
- [Modeling Network Populations via Graph Distances](https://mlsanity.com/paper/1904.07367/) (2019)
- [Inference of hyperedges and overlapping communities in hypergraphs](https://mlsanity.com/paper/2204.05646/) (2022)
- [Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach](https://mlsanity.com/paper/1308.0723/) (2013)
- [How Many Communities Are There?](https://mlsanity.com/paper/1412.1684/) (2014)
- [Flow stability for dynamic community detection](https://mlsanity.com/paper/2101.06131/) (2021)
- [The eigenvalues of stochastic blockmodel graphs](https://mlsanity.com/paper/1803.11551/) (2018)
- [Provable Estimation of the Number of Blocks in Block Models](https://mlsanity.com/paper/1705.08580/) (2017)
- [Bures-Wasserstein Means of Graphs](https://mlsanity.com/paper/2305.19738/) (2023)
- [Universality of the stochastic block model](https://mlsanity.com/paper/1806.04214/) (2018)
- [Change Point Methods on a Sequence of Graphs](https://mlsanity.com/paper/1805.07113/) (2018)
- [Spectra of random graphs with community structure and arbitrary degrees](https://mlsanity.com/paper/1310.0046/) (2013)
- [Fr'echet Mean Set Estimation in the Hausdorff Metric, via Relaxation](https://mlsanity.com/paper/2212.12057/) (2022)
- [Spectrally Constrained Optimization](https://mlsanity.com/paper/2307.04069/) (2023)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)

## Abstract (arXiv)

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.