Introduction
Classical statistical learning theory typically focuses on learning unknown functions. This research shifts the paradigm toward learning structures, specifically countably infinite graphs. The central question is: given the structural "blueprint" of a graph $G$ but not its specific vertex labeling, can an observer predict the edges of an isomorphic copy of $G$ after seeing a finite number of samples? This paper bridges statistical learning theory and mathematical logic to characterize which countably infinite graphs can be "learned" from their isomorphic copies.
The Learning-Logic Connection
A fundamental contribution of this work is bridging statistical learning properties with deep structural properties from mathematical logic. The authors demonstrate that for the full isomorphism type of a graph, PAC learnability, Online learnability, and automorphic triviality are equivalent. Automorphic triviality refers to a property where fixing a finite set of vertices "locks" the remaining automorphisms of the graph.
This connection implies that the ability to learn a graph is not just a statistical fluke but is rooted in the graph's inherent symmetry (or lack thereof). Specifically, the VC-dimension and Littlestone dimension of the hypothesis class formed by all isomorphic copies of $G$ are finite if and only if $G$ is automorphically trivial. This links a statistical property (learning) directly to a deep structural property from model theory.
The Hierarchy of Learnability
The paper establishes a four-tier hierarchy of learnability based on the complexity of vertex permutations. These classes are nested, ranging from the most restrictive (fully learnable) to the most chaotic (absolutely non-learnable).
- Online Learnable: The entire isomorphism type can be learned with a bounded number of mistakes.
- Weakly Online Learnable: Any relabeling that permutes only a finite number $k$ of vertices is learnable in the online sense.
- Weakly PAC Learnable: Similar to the above, but within the PAC framework (high probability learning from finite samples).
- Absolutely Non-Learnable: Graphs where even swapping just two vertices makes the structure unlearnable.
A key "boil down" theorem reveals that for any $k > 2$, being able to learn permutations of $k$ vertices is equivalent to being able to learn permutations of just 2 vertices, highlighting $k=2$ as a critical threshold in structural complexity.
Randomness as a Barrier
The research identifies "almost random" graphs as the antithesis of learnable structures. These graphs satisfy a relaxation of the extension property found in the Rado (Random) graph. If a graph looks locally like a random graph, it "shatters" all possible edge configurations, making it impossible for any learner to achieve a low error rate. Theorem 4.3 formally characterizes absolute non-learnability as being equivalent to this "almost random" property.
Complexity and Future Directions
Beyond characterization, the authors quantify the "hardness" of identifying these graphs using descriptive set theory. They show that the set of (weakly) online/PAC learnable graphs is $\Sigma^0_2$-complete, while the set of absolutely non-learnable graphs is $\Pi^0_2$-complete. This measures how difficult it is to determine if a given graph belongs to a certain learnability class within the space of all possible graphs.
Future work aims to move from qualitative questions ("Is it learnable?") to quantitative ones, such as studying the growth rate of VC and Littlestone dimensions as the number of permuted vertices increases. Additionally, exploring learnability under more general groups of automorphisms (beyond finite-support permutations) remains an open challenge.