Graph space: using both geometric and probabilistic structure to evaluate statistical graph models

Louis Duvivier, Rémy Cazabet, Céline Robardet

Abstract

Statistical graph models aim at modeling graphs as random realization among a set of possible graphs. One issue is to evaluate whether or not a graph is likely to have been generated by one particular model. In this paper we introduce the edit distance expected value (EDEV) and compare it with other methods such as entropy and distance to the barycenter. We show that contrary to them, EDEV is able to distinguish between graphs that have a typical structure with respect to a model, and those that do not. Finally we introduce a statistical hypothesis testing methodology based on this distance to evaluate the relevance of a candidate model with respect to an observed graph.

Introduction

Traditional methods for evaluating statistical graph models, such as the Stochastic Blockmodel (SBM) or Configuration Model (CFM), often rely on probabilistic metrics like Maximum Likelihood or Minimum Description Length. These approaches are fundamentally rooted in entropy—a measure of the variety of graphs a model can generate. However, entropy fails to capture the topological similarity between generated graphs and the observed network. A model might assign a high probability to an observed graph while simultaneously being capable of generating millions of topologically distinct realizations. This paper proposes a shift toward considering the geometric structure of "graph space" to more accurately evaluate model fit.

Methodology: The Edit Distance Expected Value (EDEV)

The core contribution of this research is the Edit Distance Expected Value (EDEV). This metric integrates geometric distance with probabilistic modeling:

  1. Edit Distance: A geometric measure defined by the number of edge additions or removals required to transform one graph into another.
  2. EDEV Calculation: Rather than comparing an observed graph $G$ to a single "average" graph (the barycenter), EDEV computes the expected edit distance between $G$ and the entire ensemble of graphs generated by a candidate model $M$.
  3. Statistical Hypothesis Testing: To determine if an observed graph is a typical realization of a model, the authors employ a bootstrapping approach combined with Fisher’s permutation test. If the observed graph's EDEV is a statistical outlier relative to the model's internal distance distribution, the model is rejected, even if it appears likely under traditional entropy-based metrics.

Key Insights: Geometry and Concentration of Measure

A significant finding is the "concentration of measure" effect in high-dimensional graph spaces. Realizations of a model are rarely near the "average" graph (the barycenter); instead, they concentrate on a "shell" at a specific characteristic distance.

Distribution of normalized edit distances to the barycenter for various graph models, illustrating the concentration of measure.

As shown in the figure above, different models exhibit distinct distributions of distances to their respective barycenters. This "hollow" nature of graph space means that the barycenter is often a poor representative of the model's actual output, particularly for the sparse graphs common in real-world applications.

Furthermore, the research highlights the distinction between entropy and geometry. A model with high entropy is not necessarily "vague" in its topological output; it may still produce graphs that are geometrically similar to one another. EDEV captures this concentration, providing a more nuanced view than entropy alone.

Comparison of characteristic distance and entropy across different statistical models.

Experimental Results

The framework was tested using synthetic datasets including Erdős-Rényi (ER), Configuration Models (CFM), and Stochastic Blockmodels (SBM). Key results include:

  • Model Rejection: In tests involving spatial (Waxman) graphs, the EDEV-based hypothesis test consistently rejected the SBM as a valid model. This is notable because the SBM was the "maximum likelihood" fit, demonstrating that traditional methods can be misled by structural artifacts.
  • Discriminatory Power: The EDEV method successfully distinguished between models that possessed nearly identical entropy but different topological "spread" in graph space.
  • Convergence: While the authors prove that edit distance to the barycenter converges to zero for very dense graphs, they demonstrate that for sparse networks, this distance remains significant, validating the necessity of the EDEV approach.

Conclusion and Future Work

The EDEV framework provides a robust tool for model selection by accounting for the geometric distribution of graphs. While the current implementation uses edit distance for its mathematical tractability, future work could explore more complex metrics such as spectral distances or perturbation-resistance distances to capture global topological properties. Additionally, addressing the computational cost of bootstrapping for massive networks remains an area for optimization.

Summary updated

Abstract

Statistical graph models aim at modeling graphs as random realization among a set of possible graphs. One issue is to evaluate whether or not a graph is likely to have been generated by one particular model. In this paper we introduce the edit distance expected value (EDEV) and compare it with other methods such as entropy and distance to the barycenter. We show that contrary to them, EDEV is able to distinguish between graphs that have a typical structure with respect to a model, and those that do not. Finally we introduce a statistical hypothesis testing methodology based on this distance to evaluate the relevance of a candidate model with respect to an observed graph.
BibTeX
@article{duvivier2021graph,
  author = {Louis Duvivier and Rémy Cazabet and Céline Robardet},
  title = {{Graph space: using both geometric and probabilistic structure to evaluate statistical graph models}},
  journal = {J. Complex Networks},
  year = {2021},
  doi = {10.1093/comnet/cnac006},
}
Figure