Detection of L∞ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion

Kiril Bangachev, Guy Bresler
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:427-497, 2024.

Abstract

In this paper we study the random geometric graph RGG(n,Td,Unif,σqp,p) with Lq distance where each vertex is sampled uniformly from the d-dimensional torus and where the connection radius is chosen so that the marginal edge probability is p. In addition to results addressing other questions, we make progress on determining when it is possible to distinguish RGG(n,Td,Unif,σqp,p) from the Erdős-Rényi graph \ergraph. Our strongest result is in the setting q=∞, in which case RGG(n,Td,Unif,σqp,p) is the \textsf{AND} of d 1-dimensional random geometric graphs. We derive a formula similar to the \emph{cluster-expansion} from statistical physics, capturing the compatibility of subgraphs from each of the d 1-dimensional copies, and use it to bound the signed expectations of small subgraphs. We show that counting signed 4-cycles is optimal among all low-degree tests, succeeding with high probability if and only if d=˜o(np). In contrast, the signed triangle test is suboptimal and only succeeds when d=˜o((np)3/4). Our result stands in sharp contrast to the existing literature on random geometric graphs (mostly focused on L2 geometry) where the signed triangle statistic is optimal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-bangachev24a, title = {{Detection of $L_∞$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion}}, author = {Bangachev, Kiril and Bresler, Guy}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {427--497}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/bangachev24a/bangachev24a.pdf}, url = {https://proceedings.mlr.press/v247/bangachev24a.html}, abstract = {In this paper we study the random geometric graph $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ with $L_q$ distance where each vertex is sampled uniformly from the $d$-dimensional torus and where the connection radius is chosen so that the marginal edge probability is $p$. In addition to results addressing other questions, we make progress on determining when it is possible to distinguish $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ from the Erdős-Rényi graph $\ergraph$. Our strongest result is in the setting $q = \infty$, in which case $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ is the \textsf{AND} of $d$ 1-dimensional random geometric graphs. We derive a formula similar to the \emph{cluster-expansion} from statistical physics, capturing the compatibility of subgraphs from each of the $d$ 1-dimensional copies, and use it to bound the signed expectations of small subgraphs. We show that counting signed 4-cycles is optimal among all low-degree tests, succeeding with high probability if and only if $d = \tilde{o}(np).$ In contrast, the signed triangle test is suboptimal and only succeeds when $d = \tilde{o}((np)^{3/4}).$ Our result stands in sharp contrast to the existing literature on random geometric graphs (mostly focused on $L_2$ geometry) where the signed triangle statistic is optimal.} }
Endnote
%0 Conference Paper %T Detection of $L_∞$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion %A Kiril Bangachev %A Guy Bresler %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-bangachev24a %I PMLR %P 427--497 %U https://proceedings.mlr.press/v247/bangachev24a.html %V 247 %X In this paper we study the random geometric graph $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ with $L_q$ distance where each vertex is sampled uniformly from the $d$-dimensional torus and where the connection radius is chosen so that the marginal edge probability is $p$. In addition to results addressing other questions, we make progress on determining when it is possible to distinguish $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ from the Erdős-Rényi graph $\ergraph$. Our strongest result is in the setting $q = \infty$, in which case $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ is the \textsf{AND} of $d$ 1-dimensional random geometric graphs. We derive a formula similar to the \emph{cluster-expansion} from statistical physics, capturing the compatibility of subgraphs from each of the $d$ 1-dimensional copies, and use it to bound the signed expectations of small subgraphs. We show that counting signed 4-cycles is optimal among all low-degree tests, succeeding with high probability if and only if $d = \tilde{o}(np).$ In contrast, the signed triangle test is suboptimal and only succeeds when $d = \tilde{o}((np)^{3/4}).$ Our result stands in sharp contrast to the existing literature on random geometric graphs (mostly focused on $L_2$ geometry) where the signed triangle statistic is optimal.
APA
Bangachev, K. & Bresler, G.. (2024). Detection of $L_∞$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:427-497 Available from https://proceedings.mlr.press/v247/bangachev24a.html.

Related Material