The planted k-factor problem

Gabriele Sicuro, Lenka ZdeborováarXiv 2020 · OpenReview

Abstract: This paper investigates the planted $k$-factor problem, where a $k$-regular subgraph is hidden within a larger weighted graph. Using tools from statistical physics, specifically Belief Propagation and the cavity method, the authors identify a continuous, infinite-order phase transition between partial and full recovery. They derive a universal criterion for perfect reconstruction based on the overlap of weight distributions and demonstrate the framework's utility in solving relaxations of the Traveling Salesman Problem.

Introduction: Finding Order in Noise

In statistical inference and network science, a recurring challenge is detecting a "signal" buried under "noise." The authors, Gabriele Sicuro and Lenka Zdeborová, formalize this through the planted $k$-factor problem. A $k$-factor is a spanning subgraph where every node has exactly $k$ connections. Common instances include the planted matching problem ($k=1$) and the planted Traveling Salesman Problem ($k=2$, finding a hidden Hamiltonian cycle).

The central question is identifying the threshold at which the noise becomes so significant that perfect recovery of the hidden structure is no longer possible. The paper investigates the phase transition between a regime of partial recovery and one of full, perfect reconstruction.

The initial noisy graph $\mathscr{G}_0$ containing a planted 2-factor.

Methodology: A Physics-Inspired Approach

To analyze the recovery process, the researchers employ a toolkit from the physics of disordered systems:

  1. Bayesian Inference & Belief Propagation (BP): Recovery is treated as a statistical estimation problem. BP serves as the local algorithm to estimate the probability of an edge belonging to the hidden $k$-factor.
  2. The Cavity Method: This is used to derive Recursive Distributional Equations (RDEs) that describe the average behavior of BP messages on large graphs.
  3. Factor Graph Mapping: The problem is mapped onto a factor graph, where nodes represent variables and constraints, facilitating the application of BP algorithms.
Mapping the $k$-factor problem to a factor graph for Belief Propagation.
  1. Front Propagation Analysis: By treating the transition to full recovery as a wave of information propagating through the graph, the authors derive a heuristic but highly accurate threshold criterion based on FKPP-type equations.

Key Insights: The Universal Criterion

A major contribution of the paper is the derivation of a simple, universal condition for full recovery:

$$\int \sqrt{\hat{p}(w) p(w)} dw = \frac{1}{\sqrt{ck}}$$

This formula relates the overlap of weight distributions (the Bhattacharyya coefficient) to the noise density ($c$) and the hidden structure's degree ($k$). If the overlap is below this threshold, perfect recovery is achievable.

The transition to full recovery is found to be of infinite order. Unlike typical phase transitions where error jumps abruptly, here the error vanishes exponentially fast as the threshold is crossed. This "drift" in the BP messages locks the algorithm into the unique, correct solution.

Results and Implications

Numerical simulations confirm the theoretical threshold for various noise levels and $k$ values. For the exponential weight model, the threshold converges to $\lambda^*_+ = 4k$ in dense graphs. The paper confirms that the Block MAP estimator is the most effective for reaching full recovery, outperforming the Symbol MAP.

Furthermore, the study demonstrates that the 2-factor problem is an excellent relaxation for the Traveling Salesman Problem (TSP). In the full recovery phase, the identified 2-factor is almost always the unique Hamiltonian cycle, suggesting that the $k$-factor framework has broad applications in combinatorial optimization.

Limitations and Future Directions

While the "front propagation" argument is physically intuitive and matches data, it currently lacks a rigorous mathematical proof. The analysis also assumes "replica symmetry," which may not hold for more complex weight distributions that lead to replica symmetry breaking. Future work could explore the impact of non-random topologies, such as small-world or clustered graphs, on recovery thresholds.

Reference: Sicuro, G., & Zdeborová, L. (2021). The planted $k$-factor problem. arXiv:2010.13700v2.

Summary updated

BibTeX
@misc{sicuro2020planted,
  author = {Gabriele Sicuro and Lenka Zdeborová},
  title = {{The planted k-factor problem}},
  year = {2020},
  url = {https://openreview.net/forum?id=YRuokVDKfg},
}
Figure