mlsanityData to 7 Oct 2026

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

arXiv 2201.05923 ↗First posted 15 Jan 2022stat.ML cs.LG cs.SIcited by 2

Not on the map. Why?

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.

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

Builds on

22 of 63 references.

References · 22

  1. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  2. 2017Community Detection and Stochastic Block Modelscited by 317
  3. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  4. 2019GraphZoom: A multi-level spectral approach for accurate and scalable graph embeddingcited by 58
  5. 2016Fr'echet Regression for Random Objects with Euclidean Predictorscited by 57
  6. 2018Graph Coarsening with Preserved Spectral Propertiescited by 41
  7. 2019Metrics for Graph Comparison: A Practitioner's Guidecited by 37
  8. 2019A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarseningcited by 31
  9. 2021Graph coarsening: From scientific computing to machine learningcited by 21
  10. 2013Network histograms and universality of blockmodel approximationcited by 20
  11. 2014Hypothesis Testing For Network Data in Functional Neuroimagingcited by 20
  12. 2013Belief propagation, robust reconstruction and optimal recovery of block modelscited by 18
10 more
  1. 2014Accurate Community Detection in the Stochastic Block Model via Spectral Algorithmscited by 13
  2. 2019Modeling Network Populations via Graph Distancescited by 13
  3. 2018The eigenvalues of stochastic blockmodel graphscited by 7
  4. 2013Spectral community detection in sparse networkscited by 5
  5. 2018Spectral Graph Forge: Graph Generation Targeting Modularitycited by 5
  6. 2013Spectra of random graphs with community structure and arbitrary degreescited by 3
  7. 2019Generalized Median Graph via Iterative Alternate Minimizationscited by 3
  8. 2019Spectral Representations of Graphons in Very Large Network Systems Controlcited by 3
  9. 2015Finding communities in sparse networkscited by 2
  10. 2021On the Number of Edges of the Frechet Mean and Median Graphscited by 1

Built on by

Cited by year

Citing papers per year: 2022: 2.

2 papers.

  1. 2022Probability density estimation for sets of large graphs with respect to spectral information using stochastic block modelscited by 0
  2. 2022Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approachcited by 0