Hidden community problems, such as community detection in the Stochastic Block Model (SBM), submatrix localization, and $\mathbb{Z}_2$ synchronization, have received considerable attention in the probability, statistics, and information-theory literature. Motivated by transitive behavior in social networks, which tend to exhibit high triangle density, recent works have considered hidden community models in spatially-embedded networks. In particular, Baccelli and Sankararaman proposed the Geometric SBM, a spatially-embedded analogue of the standard SBM with dramatically more triangles. In this paper, we consider the problem of exact recovery for the Geometric Hidden Community Model (GHCM) of Gaudio, Guan, Niu, and Wei, which generalizes the Geometric SBM to allow for arbitrary pairwise observation distributions. Under mild technical assumptions, we find the information-theoretic threshold for exact recovery in the ``distance-dependent'' GHCM, which allows the pairwise distributions to depend on distance as well as community labels, thus completing the picture of exact recovery in spatially-embedded hidden community models.

This paper studies the problem of inferring a $k$-factor, specifically a spanning $k$-regular graph, planted within an Erdős–Rényi random graph $\mathcal{G}(n,\lambda/n)$. We uncover an interesting “all-something-nothing” phase transition. Specifically, we show that as the average degree $\lambda$ surpasses the critical threshold of $1/k$, the inference problem undergoes a transition from almost exact recovery (“all” phase) to partial recovery (“something” phase). Moreover, as $\lambda$ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the “nothing” phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an “all-or-nothing” phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when $\lambda < 1/k$. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct $\Theta(n)$ many small trees of size $\Theta(1)$, whereas for establishing the algorithmic lower bound, a single large tree of size $\Theta(\sqrt{n\log n})$ suffices.

We study the problem of exact community recovery in general, two-community block models, in the presence of node-attributed *side information*. We allow for a very general side information channel for node attributes, and for pairwise (edge) observations, consider both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, Submatrix Localization, and $\mathbb{Z}_2$-Synchronization as special cases. A recent work of Dreveton et al. 2024 characterized the information-theoretic limit of a very general exact recovery problem with side information. In this paper, we show algorithmic achievability in the above important cases by designing a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the pairwise observation matrix. Using the powerful tool of entrywise eigenvector analysis [Abbe et al. 2020], we show that our spectral algorithm can mimic the so called *genie-aided estimators*, where the $i^{\mathrm{th}}$ genie-aided estimator optimally computes the estimate of the $i^{\mathrm{th}}$ label, when all remaining labels are revealed by a genie. This perspective provides a unified understanding of the optimality of spectral algorithms for various exact recovery problems in a recent line of work.

This paper considers the problem of label recovery in random graphs and matrices. Motivated by transitive behavior in real-world networks (i.e., “the friend of my friend is my friend”), a recent line of work considers spatially-embedded networks, which exhibit transitive behavior. In particular, the Geometric Hidden Community Model (GHCM), introduced by Gaudio, Guan, Niu, and Wei, models a network as a labeled Poisson point process where every pair of vertices is associated with a pairwise observation whose distribution depends on the labels and positions of the vertices. The GHCM is in turn a generalization of the Geometric SBM (proposed by Baccelli and Sankararaman). Gaudio et al. provided a threshold below which exact recovery is information-theoretically impossible. Above the threshold, they provided a linear-time algorithm that succeeds in exact recovery under a certain “distinctness-of-distributions” assumption, which they conjectured to be unnecessary. In this paper, we partially resolve the conjecture by showing that the threshold is indeed tight for the two-community GHCM. We provide a two-phase, linear-time algorithm that explores the spatial graph in a data-driven manner in Phase I to yield an almost exact labeling, which is refined to achieve exact recovery in Phase II. Our results extend achievability to geometric formulations of well-known inference problems, such as the planted dense subgraph problem and submatrix localization, in which the distinctness-of-distributions assumption does not hold.

We consider the problem of exact community recovery in the Labeled Stochastic Block Model (LSBM) with$k$communities, where each pair of vertices is associated with a label from the set$\{0,1, \ldots, L\}$. A pair of vertices from communities$i, j$is given label$\ell$with probability$p_{i j}^{(\ell)}$, and the goal is to recover the community partition. We propose a simple spectral algorithm for exact community recovery, and show that it achieves the information-theoretic threshold in the logarithmic-degree regime, under the assumption that the eigenvalues of certain parameter matrices are distinct and nonzero. Our results generalize recent work of Dhara, Gaudio, Mossel, and Sandon (2023), who showed that a spectral algorithm achieves the information-theoretic threshold in the Censored SBM, which is equivalent to the LSBM with$L=2$. Interestingly, their algorithm uses eigenvectors from two matrix representations of the graph, while our algorithm uses eigenvectors from$L$matrices.

We consider semidefinite programming (SDP) for the binary stochastic block model with equal-sized communities. Prior work of Hajek, Wu, and Xu proposed an SDP (symSDP) for the symmetric case where the intra-community edge probabilities are equal, and showed that the SDP achieves the information-theoretic threshold for exact recovery under the symmetry assumption. A key open question is whether SDPs can be used to achieve exact recovery for non-symmetric block models. In order to inform the design of a new SDP for the nonsymmetric setting, we investigate the failure of sym-SDP when it is applied to non-symmetric settings. We formally show that symSDP fails to return the correct labeling of the vertices in some information-theoretically feasible, asymmetric cases. In addition, we give an intuitive geometric interpretation of the failure of sym-SDP in asymmetric settings, which in turn suggests an SDP formulation to handle the asymmetric setting. Still, this new SDP cannot be readily analyzed by existing techniques, suggesting a fundamental limitation in the design of SDPs for community detection.

We study the problem of exact community recovery in the Geometric Stochastic Block Model (GSBM), where each vertex has an unknown community label as well as a known position, generated according to a Poisson point process in ℝd. Edges are formed independently conditioned on the community labels and positions, where vertices may only be connected by an edge if they are within a prescribed distance of each other. The GSBM thus favors the formation of dense local subgraphs, which commonly occur in real-world networks, a property that makes the GSBM qualitatively very different from the standard Stochastic Block Model (SBM). We propose a linear-time algorithm for exact community recovery, which succeeds down to the information-theoretic threshold, confirming a conjecture of Abbe, Baccelli, and Sankararaman. The algorithm involves two phases. The first phase exploits the density of local subgraphs to propagate estimated community labels among sufficiently occupied subregions, and produces an almost-exact vertex labeling. The second phase then refines the initial labels using a Poisson testing procedure. Thus, the GSBM enjoys local to global amplification just as the SBM, with the advantage of admitting an information-theoretically optimal, linear-time algorithm.

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been successfully used for graph partitioning, hidden clique recovery and graph coloring. In this paper, we study the power of spectral algorithms using two matrices in a graph partitioning problem. We use two different matrices resulting from two different encodings of the same graph and then combine the spectral information coming from these two matrices. We analyze a two-matrix spectral algorithm for the problem of identifying latent community structure in large random graphs. In particular, we consider the problem of recovering community assignments exactly in the censored stochastic block model, where each edge status is revealed independently with some probability. We show that spectral algorithms based on two matrices are optimal and succeed in recovering communities up to the information theoretic threshold. Further, we show that for most choices of the parameters, any spectral algorithm based on one matrix is suboptimal. The latter observation is in contrast to our prior works (2022a, 2022b) which showed that for the symmetric Stochastic Block Model and the Planted Dense Subgraph problem, a spectral algorithm based on one matrix achieves the information theoretic threshold. We additionally provide more general geometric conditions for the (sub)-optimality of spectral algorithms.

We consider the problem of learning latent community structure from multiple correlated networks. We study edge-correlated stochastic block models with two balanced communities, focusing on the regime where the average degree is logarithmic in the number of vertices. Our main result derives the precise information-theoretic threshold for exact community recovery using multiple correlated graphs. This threshold captures the interplay between the community recovery and graph matching tasks. In particular, we uncover and characterize a region of the parameter space where exact community recovery is possible using multiple correlated graphs, even though (1) this is information-theoretically impossible using a single graph and (2) exact graph matching is also information-theoretically impossible. In this regime, we develop a novel algorithm that carefully synthesizes algorithms from the community recovery and graph matching literatures.

Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are connected by an edge depends on the communities of those vertices. In this paper, we consider a model of censored community detection with two communities, where most of the data is missing as the status of only a small fraction of the potential edges is revealed. In this model, vertices in the same community are connected with probability p while vertices in opposite communities are connected with probability q. The connectivity status of a given pair of vertices {u, v} is revealed with probability α, independently across all pairs, where α = t log(n)/n. We establish the information-theoretic threshold tc(p, q), such that no algorithm succeeds in recovering the communities exactly when t < tc(p, q). We show that when t > tc(p, q), a simple spectral algorithm based on a weighted, signed adjacency matrix succeeds in recovering the communities exactly. While spectral algorithms are shown to have near-optimal performance in the symmetric case, we show that they may fail in the asymmetric case where the connection probabilities inside the two communities are allowed to be different. In particular, we show the existence of a parameter regime where a simple two-phase algorithm succeeds but any algorithm based on the top two eigenvectors of the weighted, signed adjacency matrix fails.

We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of the features affects the output. This motivates the sparse isotonic regression setting, which we consider here. We provide an upper bound on the expected VC entropy of the space of sparse coordinate-wise monotone functions, and identify the regime of statistical consistency of our estimator. We also propose a linear program to recover the active coordinates, and provide theoretical recovery guarantees. We close with experiments on cancer classification, and show that our method significantly outperforms several standard methods.