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

Andreas Göbel, Marcus Pappik, Leon Schiller
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2803-2803, 2026.

Abstract

We study information-theoretic phase transitions for the detectability of latent geometry in bipartite random geometric graphs (RGGs) with Gaussian $d$-dimensional latent vectors, while only a subset of edges carries latent information, determined by a random mask with i.i.d. $\mathsf{Bern}(q)$ entries. For any fixed edge density $p \in (0,1)$, we determine essentially tight thresholds for this problem as a function of $d$ and $q$. Our results show that the detection problem is substantially easier if the mask is known up-front, compared to the case where the mask is hidden. Our analysis is built upon a novel Fourier-analytic framework for bounding signed subgraph counts in Gaussian random geometric graphs that exploits cancellations. The resulting bounds are applicable to much larger sub-graphs, which enables tight information-theoretic bounds for all noise levels instead, while the bounds considered in previous works only lead to lower bounds from the lens of low-degree polynomials. As a consequence, we identify the optimal information-theoretic thresholds and rule out computational–statistical gaps. Our bounds further improve upon the bounds on Fourier coefficients of random geometric graphs recently given by Bangachev and Bresler [STOC’24] in the dense bipartite case. We believe the techniques to extend to sparser and non-bipartite settings as well, at least if the considered sub-graphs are sufficiently small, and that they might help resolve open questions in related sparse or noisy detection problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-gobel26b, title = {Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations}, author = {G{\"o}bel, Andreas and Pappik, Marcus and Schiller, Leon}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2803--2803}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/gobel26b/gobel26b.pdf}, url = {https://proceedings.mlr.press/v336/gobel26b.html}, abstract = {We study information-theoretic phase transitions for the detectability of latent geometry in bipartite random geometric graphs (RGGs) with Gaussian $d$-dimensional latent vectors, while only a subset of edges carries latent information, determined by a random mask with i.i.d. $\mathsf{Bern}(q)$ entries. For any fixed edge density $p \in (0,1)$, we determine essentially tight thresholds for this problem as a function of $d$ and $q$. Our results show that the detection problem is substantially easier if the mask is known up-front, compared to the case where the mask is hidden. Our analysis is built upon a novel Fourier-analytic framework for bounding signed subgraph counts in Gaussian random geometric graphs that exploits cancellations. The resulting bounds are applicable to much larger sub-graphs, which enables tight information-theoretic bounds for all noise levels instead, while the bounds considered in previous works only lead to lower bounds from the lens of low-degree polynomials. As a consequence, we identify the optimal information-theoretic thresholds and rule out computational–statistical gaps. Our bounds further improve upon the bounds on Fourier coefficients of random geometric graphs recently given by Bangachev and Bresler [STOC’24] in the dense bipartite case. We believe the techniques to extend to sparser and non-bipartite settings as well, at least if the considered sub-graphs are sufficiently small, and that they might help resolve open questions in related sparse or noisy detection problems.} }
Endnote
%0 Conference Paper %T Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations %A Andreas Göbel %A Marcus Pappik %A Leon Schiller %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-gobel26b %I PMLR %P 2803--2803 %U https://proceedings.mlr.press/v336/gobel26b.html %V 336 %X We study information-theoretic phase transitions for the detectability of latent geometry in bipartite random geometric graphs (RGGs) with Gaussian $d$-dimensional latent vectors, while only a subset of edges carries latent information, determined by a random mask with i.i.d. $\mathsf{Bern}(q)$ entries. For any fixed edge density $p \in (0,1)$, we determine essentially tight thresholds for this problem as a function of $d$ and $q$. Our results show that the detection problem is substantially easier if the mask is known up-front, compared to the case where the mask is hidden. Our analysis is built upon a novel Fourier-analytic framework for bounding signed subgraph counts in Gaussian random geometric graphs that exploits cancellations. The resulting bounds are applicable to much larger sub-graphs, which enables tight information-theoretic bounds for all noise levels instead, while the bounds considered in previous works only lead to lower bounds from the lens of low-degree polynomials. As a consequence, we identify the optimal information-theoretic thresholds and rule out computational–statistical gaps. Our bounds further improve upon the bounds on Fourier coefficients of random geometric graphs recently given by Bangachev and Bresler [STOC’24] in the dense bipartite case. We believe the techniques to extend to sparser and non-bipartite settings as well, at least if the considered sub-graphs are sufficiently small, and that they might help resolve open questions in related sparse or noisy detection problems.
APA
Göbel, A., Pappik, M. & Schiller, L.. (2026). Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2803-2803 Available from https://proceedings.mlr.press/v336/gobel26b.html.

Related Material