Abstract
It is becoming increasingly common to see large collections of network data objects—data sets in which a network is viewed as a fundamental unit of observation. As a result, there is a pressing need to develop network-based analogues of standard statistical tools for scalar and vector data. This paper focuses on averages of unlabeled, undirected networks with edge weights. We characterize the space of all such networks, describe key topological and geometric properties relevant to probability and statistics, and establish the asymptotic behavior of a generalized empirical mean under sampling. Our results rely on tools from geometry, probability theory, and statistical shape analysis. The lack of vertex labeling necessitates working with a quotient space modding out permutations of labels, resulting in a nontrivial geometry for the space of unlabeled networks with important implications for statistical results.
Introduction
In the era of big data, researchers frequently encounter collections of network data objects, such as functional brain connectivity maps (fMRI) or social ego-networks. Unlike traditional scalar or vector data, these networks are often unlabeled, meaning the correspondence between nodes across different samples is unknown. To perform statistical inference, one must treat all permutations of node labels as representing the same underlying structure. This requirement transforms the space of networks into a complex geometric object known as an orbifold. This paper addresses the fundamental challenge of defining and calculating averages within such non-Euclidean spaces.
Geometric Framework for Unlabeled Networks
The authors characterize the space of unlabeled, undirected networks with edge weights by modding out the permutation group of node labels. Specifically, the space of unlabeled networks $\mathcal{U}_d$ is defined as the quotient of the space of weighted graphs by the permutation group $\Sigma_d$.
To handle the lack of vertex labeling, the study employs several key geometric tools:
- Procrustean Distance: A metric that compares two unlabeled networks by finding the permutation that minimizes the Euclidean distance between their edge-weight vectors.
- Fréchet Means: A generalization of the arithmetic mean for metric spaces, defined as the point that minimizes the sum of squared distances to all observations in a sample.
- Fundamental Domains: By identifying a "fundamental domain" (like the region $F$ in the figure above), the complex orbifold can be "unfolded" into a more manageable geometric cone. This allows for a rigorous study of the mean's location and uniqueness.
Asymptotic Behavior and Statistical Guarantees
The core contribution of this work is establishing the asymptotic behavior of empirical means in the space of unlabeled networks. The authors prove several key theorems:
- Strong Law of Large Numbers (LLN): Theorem 3.2 demonstrates that as the sample size increases, the empirical Fréchet mean converges almost surely to the true population mean.
- Central Limit Theorem (CLT): Theorem 3.4 establishes that fluctuations of the empirical mean follow a Gaussian distribution when appropriately mapped, providing a basis for hypothesis testing and confidence intervals.
- Uniqueness and the "Safe Zone": The geometry of the space is non-flat, resembling a multi-dimensional cone. If a distribution is too dispersed, the mean might not be unique. However, the authors identify a "safe zone" (a sub-cone $F_{a/4}$) where the mean is guaranteed to be unique and statistically well-behaved.
Discussion and Limitations
While providing a robust theoretical foundation, the practical application of these methods faces computational hurdles. Calculating Procrustean distances is NP-hard due to the combinatorial nature of permutations. Furthermore, the current framework focuses on weighted networks with a fixed number of nodes. Future research is needed to extend these results to binary graphs and populations of networks with varying sizes.
Summary updated