Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information
This work addresses the challenge of statistical analysis for graph-valued data, which is incremental as it builds on existing Fréchet mean concepts with a new pseudometric.
The authors tackled the problem of characterizing the location (mean) of a set of graphs by defining a pseudometric based on spectral information and developing an algorithm to approximate the sample Fréchet mean for undirected unweighted graphs of fixed size.
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.