"All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery

Abstract

We study how hidden structures can be uncovered from large, complex and noisy networks. Strikingly, in some settings, algorithms go from near-perfect accuracy to almost complete failure with only a slight change in network density. Prior work by Mossel, Niles-Weed, Sohn, Sun and Zadik has shown this “all-or-nothing” pattern under certain structural properties of the hidden structure such as sparsity. Our new result reveals that for some hidden structures, the story is richer: there exists an intermediate “something” regime where partial recovery is possible. In particular, we prove an “all-something-nothing” phase transition when the hidden structure is a k-factor.