Categorical approach to graph limits

This paper introduces a category of graph limits defined by vertex and edge distributions with morphisms as random maps, and utilizes category theory to establish the compactness of the space of all such limits under a newly defined convergence notion.

The Gist

Imagine you are trying to describe a massive, complex city to someone who has never seen it. You could list every single street and building, but that's impossible. Instead, you might describe the vibe of the city: how crowded the parks are, how many people are walking on the sidewalks, and how likely it is to find a coffee shop near a library.

This paper is about creating a universal language to describe not just cities, but any network of connections—from social media friendships to protein interactions in biology. The authors, Martin Doležal and Wiesław Kubiś, are building a new mathematical "dictionary" to handle these networks, even when they are infinitely large or fuzzy.

Here is the breakdown of their ideas using simple analogies:

1. The Problem: Describing the "Fuzzy" Network

In the past, mathematicians studied networks (graphs) by counting dots (vertices) and lines (edges). But what happens when the network is huge, or when the connections aren't just "yes/no" but have probabilities?

Think of a social network.

• Old way: "Alice is friends with Bob." (Yes/No).
• New way (Graph Limits): "There is a 70% chance Alice knows Bob, and a 30% chance she doesn't."

The authors realized that to handle these complex, probabilistic networks, they needed a new way to organize them. They decided to use Category Theory.

The Analogy: Imagine Category Theory as a "universal translator" for math. Instead of just looking at the objects (the networks), it looks at the relationships between them. It asks: "How can I transform Network A into Network B without losing the essential 'shape' of the connections?"

2. The New Object: The "Square-Graphon" (□-Graphon)

The authors define a new object called a □-graphon. Think of this as a "blueprint" for a network.

A blueprint usually has two parts:

1. The Population (Vertices): Who is in the city? (In their math, this is a probability measure $\pi$).
2. The Traffic (Edges): How do they connect? (In their math, this is a measure $\mu$).

The Twist: In previous theories, the "population" was often fixed (like assuming everyone in a city is equally likely to be picked). The authors say, "No, let's be flexible!" Their blueprint allows the population distribution to be anything. It's like saying, "This city might have 1 million people, or it might have 1 billion, and they might be clustered in one neighborhood or spread out."

3. The Movers: Random Maps (Morphisms)

How do we compare two different blueprints? In this new system, we don't just draw a line from one point to another. We use Random Maps (called Markov kernels).

The Analogy: Imagine you have two different maps of the same city, but one is drawn on a crumpled piece of paper and the other on a smooth tablet.

• A standard map says: "Point A on the paper is exactly Point B on the tablet."
• A Random Map says: "If you are at Point A on the paper, there is a 60% chance you are at Point B on the tablet, a 30% chance you are at Point C, and a 10% chance you are lost."

This flexibility is crucial. It allows the authors to say two very different-looking networks are actually "the same" if they can be transformed into each other using these probabilistic rules.

4. The Shape of Things: "k-shapes"

How do we know if two networks are converging (getting closer) to the same limit? The authors look at the k-shape.

The Analogy: Imagine you are trying to guess the shape of a giant, invisible cloud by looking at small shadows it casts on the ground.

• A 1-shape is a shadow of a single point (how dense is the crowd?).
• A 2-shape is a shadow of two points (how likely are two random people to know each other?).
• A k-shape is a shadow of a small group of $k$ people.

The authors define a network's "limit" by checking if all these small shadows (k-shapes) are stabilizing. If the shadows of groups of 1, 2, 3, 4... people stop changing as you look at bigger and bigger networks, then the whole network has a limit.

5. The Big Win: Compactness

The most important result of the paper is proving Compactness.

The Analogy: Imagine you have an infinite library of books, and you are reading them one by one. You want to know: "Does this sequence of books eventually settle on a specific story?"

In many mathematical worlds, a sequence of networks could run off into infinity and never settle. The authors proved that in their new system, every sequence of networks eventually settles down to a limit.

It's like saying, "No matter how chaotic the traffic gets in our city, if you watch it long enough, it will eventually settle into a predictable pattern."

They proved this by building a "super-network" out of an infinite product of smaller, finite networks. It's like building a giant mosaic where every tile is a tiny, simple network, and together they form the perfect, infinite limit.

6. Why Does This Matter?

• Flexibility: It handles weighted, directed, and probabilistic networks better than before.
• Unification: It brings together different ways of studying graphs (like "s-graphons" and standard "graphons") under one roof.
• Future Applications: The authors hope this framework will help classify different types of networks, perhaps revealing hidden connections between social media, biology, and physics that we couldn't see before.

Summary

The authors built a new mathematical lens (a category) to look at giant, fuzzy networks. They introduced a flexible blueprint (□-graphon) and a way to transform them (random maps). By checking the "shadows" of small groups (k-shapes), they proved that any sequence of these networks eventually settles into a stable, predictable limit. It's a powerful new tool for understanding the hidden structure of complex systems.

Technical Summary

1. Problem Statement

The paper addresses the theoretical foundations of graph limits, specifically aiming to generalize existing frameworks (such as graphons and $s$-graphons) using category theory.

• Context: Traditional graph limit theory often relies on fixed measurable spaces (e.g., the unit interval $[0,1]$) and specific definitions of convergence (like $s$-convergence). While powerful, these approaches can introduce technical difficulties when dealing with complex structures or when the underlying space is not naturally isomorphic to the unit interval.
• Gap: There was no established natural notion of a morphism between two general graph limit objects. In category theory, morphisms are as important as objects; the lack of a robust morphism definition limits the ability to apply categorical tools (like limits, colimits, and compactness arguments) to the space of graph limits.
• Goal: To define a category of graph limits where objects are abstract measure-theoretic structures and morphisms are random maps (Markov kernels) that preserve vertex and edge distributions. The authors aim to use this structure to prove the compactness of the space of all graph limits without restricting the underlying measurable spaces to fixed domains.

2. Methodology

The authors employ a blend of measure theory, probability theory, and category theory.

A. Definition of Objects: $\square$-Graphons

The authors introduce $\square$-graphons as the fundamental objects. A $\square$-graphon is defined as a pair $(\pi, \mu)$ on a measurable space $(X, \mathcal{A})$:

• $\pi$: A probability measure on $X$ (representing the distribution of vertices).
• $\mu$: A finite measure on $X^2$ (representing the distribution of edges).
• Note: This generalizes standard graphons (where $\pi$ is usually fixed as Lebesgue measure) and allows for weighted vertices and edges.

B. Definition of Morphisms

Morphisms between $\square$-graphons $(\pi_X, \mu_X)$ and $(\pi_Y, \mu_Y)$ are defined as Markov kernels $\kappa: X \times \mathcal{B} \to [0, 1]$.

• A Markov kernel represents a "random map" where the image of a point is a probability distribution rather than a deterministic point.
• Preservation Condition: $\kappa$ is a morphism if it preserves the distributions:
  1. $\pi_Y = \kappa_* \pi_X$ (Pushforward of vertex measure).
  2. $\mu_Y = \kappa^{\otimes 2}_* \mu_X$ (Pushforward of edge measure via the product kernel).
• This forms a category where composition is the standard composition of Markov kernels.

C. Convergence via $k$-Shapes

To define convergence, the authors adapt the concept of $k$-shapes (inspired by Lovász and Szegedy's $s$-convergence):

• For a fixed $k$, the $k$-shape $S_k(\pi, \mu)$ is the topological closure (in the Vietoris topology) of the set of all $\square$-graphons on a finite space $F_k = \{1, \dots, k\}$ that can be obtained from $(\pi, \mu)$ via a morphism.
• A sequence of $\square$-graphons converges if the sequence of their $k$-shapes converges in the space of compact sets (hyperspace) for every $k$.

D. Proof Strategy for Compactness

To prove that every convergent sequence has a limit (Theorem 4.5), the authors utilize inverse systems of measures:

1. They construct a countable dense subset of the limit $k$-shapes.
2. They build two inverse systems of measures: one for the vertex distributions and one for the edge distributions, indexed by finite subsets of the dense set.
3. They apply the Kolmogorov Extension Theorem to construct the inverse limits of these systems.
4. The resulting pair of measures forms the limit $\square$-graphon on an infinite product space.

3. Key Contributions

1. Categorical Framework for Graph Limits:
   The paper establishes a rigorous category where objects are $\square$-graphons and morphisms are measure-preserving Markov kernels. This unifies deterministic graph homomorphisms and probabilistic mappings under a single algebraic structure.

2. Generalization of Graphons:
   By allowing the underlying measurable space $(X, \mathcal{A})$ to be abstract (not necessarily $[0,1]$), the framework handles complex structures (e.g., products of spaces) without forcing them into a unit interval representation, which often causes technical artifacts.

3. Proof of Compactness (Theorem 4.5):
   The authors prove that the space of all $\square$-graphons is compact under the defined convergence.

   • Significance: This is a fundamental result in graph limit theory, ensuring that limits of convergent sequences always exist within the class. The proof is notable for constructing the limit on an infinite product space and then showing it can be mapped to a standard Borel space.

4. Equivalence of Convergence Notions:
   The paper demonstrates that their definition of convergence (based on $k$-shapes with variable vertex distributions) is equivalent to the classical $s$-convergence (where vertex distribution is fixed to the normalized counting measure).

   • This is achieved via Lemma 5.1 and Corollary 5.2, showing that any $k$-shape can be approximated by elements with a fixed vertex distribution.
   • This result re-proves the compactness of $s$-graphons as a corollary.

5. Characterization of Isomorphisms:
   The paper characterizes isomorphisms in this category. For "reasonable" spaces (where singletons are measurable), an isomorphism corresponds to a measurable bijection that preserves both vertex and edge measures. The authors also provide counter-examples (Example 6.2) showing that without measurability of singletons, the structure of isomorphisms can be trivial and counter-intuitive.

4. Key Results

• Theorem 4.5 (Compactness): Every convergent sequence of $\square$-graphons has a limit. The limit can be constructed on a standard Borel space (e.g., the unit interval with Lebesgue measure).
• Theorem 5.5 (Equivalence of Topologies): The topology of convergence defined by $k$-shapes $S_k$ (variable vertex measure) is identical to the topology defined by $\tilde{S}_k$ (fixed vertex measure, i.e., $s$-convergence).
• Proposition 6.1: Isomorphisms in the category of $\square$-graphons (on spaces with measurable singletons) are exactly the measure-preserving isomorphisms of the underlying measurable spaces.
• Example 6.3: Demonstrates that the topological closure in the definition of $k$-shapes is necessary; there exist limits that are not directly reachable via a single morphism but are limits of a sequence of morphisms.

5. Significance and Impact

• Theoretical Unification: The paper successfully bridges the gap between abstract category theory and combinatorial graph theory. It shows that category theory is not just a linguistic tool but provides a functional framework for proving deep structural results (like compactness) in graph limit theory.
• Flexibility: By decoupling the graph limit from a fixed domain (like $[0,1]$), the framework is more adaptable to applications in probability theory and statistical physics where natural state spaces may be products or infinite-dimensional.
• Methodological Innovation: The use of inverse limits of measure spaces combined with the Kolmogorov Extension Theorem offers a novel and robust method for constructing limits of graph sequences, avoiding some of the analytic complexities associated with weak convergence on fixed spaces.
• Future Directions: The authors suggest this framework could aid in the classification of graph limits and discovering new relationships between different types of graphons (e.g., directed, weighted, or hypergraph limits), potentially leading to new invariants and structural theorems.

In summary, Doležal and Kubiś provide a rigorous, category-theoretic foundation for graph limits that generalizes existing theories, proves compactness through constructive measure-theoretic arguments, and establishes the equivalence of different convergence paradigms.