Phase transition in noisy high-dimensional random geometric graphs

Suqi Liu, Miklós Z. RáczarXiv 2021 · OpenReview

TL;DR

This paper investigates how "noise" (represented by parameter $q$) affects our ability to detect underlying geometric structure in random graphs. They introduce a "soft" random geometric graph model that smoothly interpolates between a purely geometric graph and a standard Erdős-Rényi graph. The key finding is that increasing noise ($q$) lowers the dimensional threshold at which geometric structure becomes undetectable, and conversely, allows for detection in higher dimensions.

What Problem Does This Paper Address?

In many real-world networks (like social networks or communication systems), the observed connections between entities might be influenced by an underlying, unobserved geometric structure. Detecting this hidden geometry is crucial for understanding network formation and function. Previous work focused on "hard" random geometric graphs where connections are strictly determined by distance. However, real-world connections are often more nuanced and can be influenced by factors that introduce "noise." This paper addresses how this noise, quantified by a parameter $q$, impacts the detectability of geometric structure, particularly in high-dimensional settings. They aim to precisely characterize the phase transitions where geometry is either lost or detectable, and how this depends on dimensionality ($d$), graph density ($p$), and the noise level ($q$).

Methods

The authors introduce a "soft" random geometric graph model, $\mathcal{G}(n, p, d, q)$, which interpolates between the hard random geometric graph $\mathcal{G}(n, p, d)$ (where $q=1$) and the Erdős-Rényi graph $\mathcal{G}(n, p)$ (where $q=0$). The parameter $q$ controls the level of "noise" or the strength of the geometric influence.

Their core methodology involves:

  • Hypothesis Testing: They frame the problem as a hypothesis test: is the observed graph from a purely random $\mathcal{G}(n,p)$ model or a structured $\mathcal{G}(n,p,d,q)$ model?
  • Total Variation Distance: They use the total variation distance between the distributions of these two graph models as a measure of distinguishability. A distance close to 0 means they are indistinguishable, while a distance close to 1 means they are easily distinguishable.
  • Signed Triangle Statistic: For the "possibility" side (when detection is feasible), they leverage the "signed triangle statistic," a method previously shown to be effective for detecting geometry in hard random geometric graphs.
  • Information-Theoretic Tools: They employ tools like KL-divergence and Pinsker's inequality to derive bounds on the total variation distance.
  • Concentration Inequalities and Probabilistic Arguments: Various inequalities and probabilistic arguments are used to bound expectations and variances of graph statistics, particularly for the signed triangle statistic.
  • Generalizations: They also consider a variant with standard normal distributions instead of uniform on the sphere and explore generalizations of the signed triangle statistic (signed cliques and cycles) to understand if they offer better detection capabilities.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on analyzing random graph models.

Key Insights and Ideas

  • Noise Lowers Dimensionality Threshold: The most significant insight is that increasing the noise parameter $q$ (making the graph "softer" and more like an Erdős-Rényi graph) lowers the critical dimension $d$ at which geometric structure becomes undetectable. This is counter-intuitive at first glance, as one might expect more noise to obscure structure, but here it means that for a fixed dimension, more noise makes it harder to detect geometry. Conversely, for a fixed noise level, higher dimensions lead to loss of geometry.
  • Smooth Transition: The paper quantifies a smooth phase transition. Instead of a sharp boundary, there's a regime where detection becomes increasingly difficult as parameters change.
  • Signed Triangles as a Powerful Tool: The signed triangle statistic, while simple, is shown to be asymptotically powerful for detecting geometry in the soft random geometric graph model, generalizing previous results.
  • Generalization to Standard Normal: The core results about phase transitions hold even when the underlying points are drawn from standard normal distributions, suggesting robustness.
  • Signed Cliques/Cycles Don't Improve Detection Boundary: Exploring generalizations like signed cliques and cycles suggests that they don't fundamentally improve the detection boundary compared to signed triangles, although they might offer different trade-offs or insights.

Key Results

  • Impossibility of Detection: Geometry is lost (i.e., $\mathcal{G}(n,p,d,q)$ is indistinguishable from $\mathcal{G}(n,p)$) if $nq \to 0$ or $d \gg n^3 q^2$. This means that if the noise is high ($nq \to 0$) or the dimension is very large relative to the noise and graph size ($d \gg n^3 q^2$), detecting geometry is impossible.
  • Possibility of Detection: Geometry can be detected if $d \ll n^3 q^6$. This means that if the dimension is sufficiently small relative to the noise and graph size, there exists a powerful test (the signed triangle statistic) to distinguish the models.
  • Phase Diagram: These results are visualized in a phase diagram with parameters $\alpha$ and $\beta$, where $d=n^\alpha$ and $q=n^{-\beta}$. Detection is impossible if $\beta > 1$ or $\alpha + 2\beta > 3$, and possible if $\alpha + 6\beta < 3$.
  • Generalization: Similar results hold for random dot product graphs where points are i.i.d. standard normal.

Limitations and Future Work

  • Intermediate Regime: The paper explicitly identifies an "intermediate region" between the impossibility and possibility bounds where the exact phase transition boundary is not determined. This is highlighted as a key open problem.
  • Other Connection Functions/Latent Spaces: The authors suggest exploring other types of connection functions and latent spaces to understand how dimension thresholds for losing geometry depend on these choices.
  • Efficient Algorithms: While the signed triangle statistic is computationally efficient, the paper notes that the existence of an intermediate phase where detection is information-theoretically possible but no efficient algorithm exists is worth studying.
  • Tightness of Bounds: For generalizations like signed cliques and cycles, the authors suggest that the derived bounds might not be tight, particularly concerning the dependence on dimension $d$. They conjecture that the expected value of signed cliques decays faster with $d$ than their current bounds suggest.

Summary updated

Abstract

We study the problem of detecting latent geometric structure in random graphs. To this end, we consider the soft high-dimensional random geometric graph $\mathcal{G}(n,p,d,q)$, where each of the $n$ vertices corresponds to an independent random point distributed uniformly on the sphere $\mathbb{S}^{d-1}$, and the probability that two vertices are connected by an edge is a decreasing function of the Euclidean distance between the points. The probability of connection is parametrized by $q \in [0,1]$, with smaller $q$ corresponding to weaker dependence on the geometry; this can also be interpreted as the level of noise in the geometric graph. In particular, the model smoothly interpolates between the spherical hard random geometric graph $\mathcal{G}(n,p,d)$ (corresponding to $q = 1$) and the Erd\H{o}s-R\'enyi model $\mathcal{G}(n,p)$ (corresponding to $q = 0$). We focus on the dense regime (i.e., $p$ is a constant). We show that if $nq \to 0$ or $d \gg n^{3} q^{2}$, then geometry is lost: $\mathcal{G}(n,p,d,q)$ is asymptotically indistinguishable from $\mathcal{G}(n,p)$. On the other hand, if $d \ll n^{3} q^{6}$, then the signed triangle statistic provides an asymptotically powerful test for detecting geometry. These results generalize those of Bubeck, Ding, Eldan, and R\'acz (2016) for $\mathcal{G}(n,p,d)$, and give quantitative bounds on how the noise level affects the dimension threshold for losing geometry. We also prove analogous results under a related but different distributional assumption, and we further explore generalizations of signed triangles in order to understand the intermediate regime left open by our results.
BibTeX
@misc{liu2021phase,
  author = {Suqi Liu and Miklós Z. Rácz},
  title = {{Phase transition in noisy high-dimensional random geometric graphs}},
  year = {2021},
  eprint = {2103.15249},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.15249},
}
Figure