Convergent sequences of sparse graphs: A large deviations approach

Christian Borgs, Jennifer T. Chayes, David GamarnikRandom Struct. Algorithms 2017 · DOI

TL;DR

This paper introduces a new framework called "Large Deviations Convergence" (LD-convergence) for analyzing sequences of sparse graphs. This novel approach leverages large deviation theory to provide a unified way to understand graph convergence, implying several previously established notions and offering new insights into their relationships.

What Problem Does This Paper Address?

The study of convergent graph sequences has been well-developed for dense graphs, where various convergence notions have been shown to be equivalent. However, for sparse graphs (graphs with bounded degrees), the landscape is much less clear. Several existing notions of convergence, such as left-convergence and right-convergence, have been introduced, but their relationships and implications have remained largely unknown or uncertain. This paper aims to bridge this gap by introducing a new, powerful notion of convergence, LD-convergence, and demonstrating how it relates to and unifies existing concepts, ultimately providing a more coherent understanding of sparse graph convergence.

Methods

The core of this paper is the introduction of Large Deviations Convergence (LD-convergence). This is achieved by "decorating" the nodes of sparse graphs with independent random weights from [0,1] and constructing random measures on [0,1] and [0,1]². A graph sequence is defined as LD-convergent if these random measures satisfy a Large Deviations Principle (LDP) with respect to the weak convergence topology. The authors then establish that LD-convergence implies several previously defined notions of convergence, including right-convergence, left-convergence, and partition-convergence. They also introduce a related concept, k-LD-convergence, which involves analyzing random k-quotients of graphs and show its equivalence to LD-convergence. The paper also utilizes concepts from statistical physics, such as free energies and partition functions, to interpret and relate these convergence notions.

Datasets

Not discussed in the paper. The paper focuses on theoretical concepts and definitions related to graph sequences rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unifying Framework: LD-convergence provides a powerful new lens through which to view and unify various existing notions of sparse graph convergence, suggesting a deeper underlying structure.
  • Large Deviations as a Bridge: The application of large deviation theory proves to be a natural and effective tool for understanding the limiting behavior of sparse graph sequences, connecting probabilistic phenomena to deterministic limits.
  • Implications and Relationships: The paper rigorously establishes that LD-convergence implies right-convergence, left-convergence, and partition-convergence, offering a clear hierarchy of these concepts.
  • New Relationships: Crucially, the paper demonstrates that partition-convergence does not imply left or right-convergence, and right-convergence does not imply partition-convergence, clarifying previously ambiguous relationships.
  • Statistical Physics Connection: The interpretation of convergence in terms of free energies and the connection to spin glass theory highlights the broader applicability and significance of this work.

Key Results

  • LD-convergence implies Right, Left, and Partition-convergence: This is a central result, establishing LD-convergence as a strong unifying notion.
  • Equivalence of LD and k-LD-convergence: The paper proves that LD-convergence is equivalent to k-LD-convergence for all k, providing alternative perspectives on the definition.
  • Clarification of Non-Implications: The paper provides counterexamples to show that partition-convergence does not imply left-convergence, and right-convergence does not imply partition-convergence.
  • Robustness of LD-convergence: The paper demonstrates that LD-convergence is robust with respect to graph equivalency (differing by a small number of edges).
  • Relationship to Free Energy: A key result (Theorem 5) shows that LD-convergence implies right-convergence and provides an explicit formula for the limiting free energy in terms of the LD rate function.

Limitations and Future Work

  • Colored-Neighborhood-Convergence: The relationship between LD-convergence and colored-neighborhood-convergence remains an open question. The authors conjecture that LD-convergence implies colored-neighborhood-convergence, but do not prove it. They also conjecture that colored-neighborhood-convergence does not imply right-convergence.
  • Random Graph Sequences: The paper discusses the open problem of whether random graph sequences like Erdös-Rényi graphs G(n, c/n) and random regular graphs G(n, Δ) are right-convergent. They conjecture that these sequences are almost surely LD-convergent, which would imply convergence for other notions as well.
  • Spin Glass Theory: The connection to spin glass theory is highlighted as an area where these results could have significant implications, particularly concerning the existence of thermodynamic limits.
  • Computational Aspects: While the paper provides theoretical frameworks, the practical computation of rate functions for specific graph sequences remains a challenge.

Summary updated

BibTeX
@article{borgs2017convergent,
  author = {Christian Borgs and Jennifer T. Chayes and David Gamarnik},
  title = {{Convergent sequences of sparse graphs: A large deviations approach}},
  journal = {Random Struct. Algorithms},
  year = {2017},
  doi = {10.1002/rsa.20694},
}
Figure