# Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 63 references that are in the map.
- First posted on arXiv 15 Jan 2022.

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

- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Fr'echet Regression for Random Objects with Euclidean Predictors](https://mlsanity.com/paper/1608.03012/) (2016)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [Metrics for Graph Comparison: A Practitioner's Guide](https://mlsanity.com/paper/1904.07414/) (2019)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [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)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014)
- [Modeling Network Populations via Graph Distances](https://mlsanity.com/paper/1904.07367/) (2019)
- [The eigenvalues of stochastic blockmodel graphs](https://mlsanity.com/paper/1803.11551/) (2018)
- [Spectral community detection in sparse networks](https://mlsanity.com/paper/1308.6494/) (2013)
- [Spectral Graph Forge: Graph Generation Targeting Modularity](https://mlsanity.com/paper/1801.01715/) (2018)
- [Spectra of random graphs with community structure and arbitrary degrees](https://mlsanity.com/paper/1310.0046/) (2013)
- [Generalized Median Graph via Iterative Alternate Minimizations](https://mlsanity.com/paper/1906.11009/) (2019)
- [Spectral Representations of Graphons in Very Large Network Systems Control](https://mlsanity.com/paper/1911.01536/) (2019)
- [Finding communities in sparse networks](https://mlsanity.com/paper/1509.06633/) (2015)
- [On the Number of Edges of the Frechet Mean and Median Graphs](https://mlsanity.com/paper/2105.14397/) (2021)

## Built on by (most cited first, 2 of 2)

- [Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models](https://mlsanity.com/paper/2207.02168/) (2022)
- [Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approach](https://mlsanity.com/paper/2210.07401/) (2022)

## Abstract (arXiv)

To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that is adapted to metric spaces, since graph sets are not Euclidean spaces. A standard approach is to consider the Frechet mean. In this work, we equip a set of graphs with the pseudometric defined by the norm between the eigenvalues of their respective adjacency matrix. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems for graph-valued data. We describe an algorithm to compute an approximation to the sample Frechet mean of a set of undirected unweighted graphs with a fixed size using this pseudometric.