Potts model shows robust root label reconstruction despite noise
Robust Reconstruction on Trees with a Growing Alphabet
Information Theory
Summary
This paper studies how to figure out the original label at the root of a complex tree structure when the number of possible labels becomes very large. The authors find that even when the labels observed at the edges are heavily corrupted by noise, the original label’s prediction remains accurate under certain conditions. This means the system can tolerate a lot of uncertainty or errors at the boundary without losing important information about the root. Their work applies mathematical tools to understand how information survives in noisy hierarchical settings.
What this means in practice
- •For network designers: Design communication protocols in trees that preserve root signal despite heavy boundary noise when many signal states exist.
- •For data scientists: Improve inference methods on hierarchical data where large label sets and noise at edges occur, ensuring robust root-level predictions.
A theory result. No direct application yet.
Authors
Heon Lee
Abstract
We study robust reconstruction for the \(q\)-state Potts broadcast process on a Galton-Watson tree in the growing-alphabet regime \(q\to\infty\), with boundary depth growing sufficiently quickly in relation to \(q\). We show that, in the regime \(dλ>1\), where \(d\) is the expected number of offspring and \(λ\) is the nontrivial eigenvalue of the Potts transition matrix, the root posterior is asymptotically unchanged by a broad class of noise channels applied independently to the boundary labels. This remains true even when the probability of retaining the true label at an individual boundary vertex tends to zero as \(q\to\infty\). More precisely, under suitable moment and noise assumptions, the noiseless and noisy root posteriors converge to one another in expected total variation, and hence have the same asymptotic Bayes-optimal reconstruction accuracy.