In this work, we investigate the fundamental problem of detecting a faint geometric signal hidden within an otherwise random graph. We formulate this task as a hypothesis testing problem: under the null hypothesis, the observed graph is an Erdős–Rényi random graph $\mathcal{G}(n,q)$ with edge density $q\in(0,1)$; under the alternative, a high-dimensional geometric structure is clandestinely embedded. Specifically, a random geometric graph $\mathcal{G}(k,q,d)$ on $k\le n$ vertices is planted inside $\mathcal{G}(n,q)$, where each of the $k$ vertices corresponds to an independent random point drawn uniformly from the unit sphere $\mathbb{S}^{d-1}$, and edges are formed according to latent proximity, resulting in the same edge probability $q$. Our objective is to characterize the limits of detectability of this hidden geometry, from both statistical and computational perspectives. We derive sharp information-theoretic lower bounds that characterize the regimes in which detection is fundamentally impossible, expressed explicitly in terms of the problem parameters. Complementing these impossibility results, we propose and analyze several algorithms that provably attain these limits whenever detection is feasible. We also explore the algorithmic landscape of the problem and investigate which regimes admit efficient, polynomial-time testing procedures. As in many other structured high-dimensional inference problems, our model exhibits a pronounced \emph{easy–hard–impossible} phase transition: there exist regimes in which detection is statistically possible yet computationally prohibitive, as well as regimes in which detection is impossible even with unbounded computational resources. As concrete evidence of this computational barrier, we show that the entire class of low-degree polynomial algorithms fails in the conjecturally hard regime, highlighting a sharp separation between statistical possibility and algorithmic feasibility.

Modern social media platforms play an important role in facilitating rapid dissemination of information through their massive user networks. Fake news, misinformation, and unverifiable facts on social media platforms propagate disharmony and affect society. In this paper, we consider the problem of misinformation detection. Specifically, driven by experiential studies on real-world social media platforms, we propose a probabilistic Markovian information spread model over networks modeled by graphs. We then formulate our inference task as a certain sequential detection problem with the goal of minimizing the combination of the error probability and the time it takes to achieve correct decision. For this model, we find the optimal detection algorithm minimizing the aforementioned risk and prove several statistical guarantees. We then test our algorithm over real-world datasets. To that end, we first construct an offline algorithm for learning the probabilistic information spreading model, and then apply our optimal detection algorithm. Our experimental study show that our algorithm outperforms state-of-the-art misinformation detection algorithms in terms of accuracy and detection time.

In this paper, we study the problem of testing for edge dependence between two weighted random graphs observed up to vertex relabeling. We formulate it as a binary hypothesis testing problem: under the null hypothesis, the two observed graphs are statistically independent, whereas under the alternative, the edges of one graph are correlated with the edges of a randomly vertex-permuted version of the other graph. For general edge-weight distributions, we establish thresholds at which optimal testing is information-theoretically impossible and possible, in terms of the number of vertices and the underlying weight distributions. Finally, we exhibit a statistical– computational gap for this problem and provide evidence that it is fundamental, using the low-degree polynomial framework.