Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations

Andreas Göbel, Marcus Pappik, Leon Schiller · 2026

Read Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations by Andreas Göbel, Marcus Pappik, Leon Schiller (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-11129.txt.

Description

Can hidden shape be detected when only some edges carry signal? Andreas Göbel and two co-authors study bipartite random geometric graphs with Gaussian latent vectors and a random mask over edges. They pin down essentially tight finding thresholds in terms of dimension and mask density.

Known masks make finding far easier than hidden ones. The proof builds a new Fourier method for signed subgraph counts, using cancellations from power-series approximations of characteristic functions. Those bounds reach larger subgraphs than prior work allowed, closing computer-numerical gaps. The techniques also improve recent Fourier bounds for dense bipartite graphs and extend to sparser and non-bipartite cases.

Catalog record

CREATORAndreas Göbel, Marcus Pappik, Leon Schiller
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE154 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-11129

Browse the full library · About the Tower of Babel