CS Paper Radar

Tightness and Error Exponents of SDP with Logarithmically Many Communities

Shengtao Guo, Ethan X. Fang, Junwei Lu

cs.IT math.ST ·submitted 2026-10-07 02:02 UTC · v1
theory

Abstract

We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with $n=km$ vertices, we consider the regime $k/\log m\toγ>0$, with edge probabilities $α\log m/m$ within communities and $β\log m/m$ across them, for fixed $α>β>0$. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.

Comment
36 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Community Recovery in Bipartite Networks

cs.SI math.STstat.ML ·2026-09-11 ·Huan Qing
theory similarity 0.61
Abstract · 39 pages, 4 figures

Community detection in bipartite networks is a fundamental problem in modern data analysis, with applications in recommendation systems, biological networks, and social network analysis. Unlike conventional unipartite graphs, bipartite networks consist of two distinct types of nodes with edges only connecting across types, so recovering latent communities requires estimating labels on the two node types. The stochastic co-blockmodel is a classical probabilistic framework for such networks, yet theoretical guarantees for exact community recovery in this setting remain limited, especially when the number of communities grows, the community sizes are unbalanced, or the degrees are heterogeneous. In this work, we prove that a simple spectral clustering algorithm based on the diagonal-deleted Gram matrix achieves exact recovery with high probability under mild conditions on sparsity, community balance, and the number of clusters. We further extend the result to the degree-corrected stochastic co-blockmodel, where each node carries its own degree heterogeneity parameter, and show that a row-normalized version of the same algorithm maintains the exact recovery guarantee. Extensive experiments validate our theoretical findings.

0.15

Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models

cs.IT cs.LGmath.PRmath.ST+1 ·2026-10-06 ·Soroor Ghandali
similarity 0.58
Abstract · 36 pages, 4 figures, 6 tables

We study community recovery in the sparse symmetric stochastic block model with $q$ communities, average degree $d$ and signal strength $λ$ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold $dλ^2=1$ and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-$D$ polynomial rules is the trivial risk times $1-\mathrm{Corr}_D^2$. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for $q\ge 5$ there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability $1-o(1)$. Second, the Fisher information about $λ$ carried by cycle counts is a series with terms of order $k(dλ^2)^k$, convergent exactly when $dλ^2<1$; below the threshold the relative error of every unbiased cycle-based estimator of $λ^k$ stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by $|λ|\sqrt{d}$ per iteration, and one EM step taken there leaves $λ$ unchanged. A signal-to-noise computation recovers the condition $dλ^{1/χ}>1$ of Chin et al. for $q=n^χ$ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to $3\times 10^5$ vertices confirm the threshold for $q=2$, the hard window for $q=5$, and the many-community scaling.

0.37

Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses

cs.DS math.PR ·2026-09-13 ·Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao
theory similarity 0.57
Abstract · 79 pages

Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We determine how finite graph structure controls their sharp spectral growth. For every fixed simple graph shape in the dense Rademacher model, including overlapping or empty matrix boundaries, we prove $\mathbb E\|M_α\|=Θ_α(n^{(v+h-s)/2}(\log n)^{a_*/2})$, where $v$ counts vertices, $h$ isolated summation vertices, $s$ the minimum boundary-separator size, and $a_*$ maximizes an active-component count over minimum separators. Thus two finite cut optimizations determine both the polynomial and logarithmic exponents. The formula closes the polylogarithmic gap in separator bounds, and an infinite family with identical coarse parameters but different norms shows that the logarithmic exponent records genuinely new structure. The proof controls all defect layers in growing trace moments by converting label loss into separator excess; conditional flattening and synchronized fluctuations yield matching lower bounds. We extend the analysis to specified independent-factor chaoses, local weights, unequal dimensions, bounded asymmetric noise, Gaussian inputs, and fixed-degree Hermite inputs. Applications include degree-four clique SoS feasibility for $9\le k\le c\sqrt n$ without an asymptotic logarithmic loss, and Gaussian random tensor networks: deviation thresholds, sharp expected scales, entropy estimates, and, for connected loopless equal-dimensional networks, convergence of the rescaled largest output eigenvalue to the exact right edge of the limiting law. These results connect finite structure to sharp growth scales, and additional algebraic and spectral structure to full feasibility and exact limiting constants.

0.32

Smoothed Analysis for Distributed MIS

cs.DC ·2026-11-12 ·Dipan Dey, Fabien Dufoulon, William K. Moses, Gopal Pandurangan
theory similarity 0.57
Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $Ω(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability $p$. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph $G$, when $p=β\ln n/n$ for a sufficiently large constant $β$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if $p\le(1/2-δ)\ln n/n$ for a fixed constant $δ>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $Ω(\log n/\log\log n)$ rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

0.10

A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability

cs.DS ·2026-10-30 ·Zhijie Zheng
similarity 0.56
Abstract · 19 pages

We give a fully polynomial randomized approximation scheme for all-terminal unreliability in explicitly represented undirected hypergraphs of arbitrary rank. The algorithm estimates the probability that independent hyperedge failures disconnect the hypergraph, allowing a different rational failure probability for every edge. For a common failure probability, this improves the quasi-polynomial approximation schemes of Cen, Li, and Panigrahi to polynomial time and answers the polynomial-time approximation question reiterated in their subsequent work on graphs. The construction turns their representative-survival bound into an importance sampler whose relative second moment is bounded solely in terms of the number of vertices. We protect one randomly chosen representative pair during contraction, correct the path likelihood, and divide by the number of pairs surviving at the end. The resulting unbiased estimator has relative second moment at most $\binom n2$, even when unreliability is exponentially small. A minimum-cut normalization makes this estimator implementable with polynomially bounded precision: the residual likelihood becomes a survival probability in an auxiliary absorbing process, which admits rational discretization with a fixed random-bit budget. Logarithmic rate rounding and an exact weighted minimum cut extend the construction to unequal rational failure probabilities. The algorithm's worst-case running time and random-bit usage are polynomial in the input length, the inverse relative error, and $\log(1/δ)$ for confidence $1-δ$.

0.18

How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports

cs.LG ·2026-11-16 ·Alisina Bayati, Srinivasa Salapaka, Shahriar Talebi
unusual similarity 0.56
Abstract

In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.

0.27

Graph Spectral Sparsification is in Catalytic Logspace

cs.DS cs.CC ·2026-08-21 ·Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld
similarity 0.56
Abstract · 29 pages

We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph $G$ on $n$ vertices and $\varepsilon>0$, our algorithm outputs an $\varepsilon$-spectral sparsifier of $G$ with $O(n\varepsilon^{-2}\log n)$ edges, matching the effective resistance sampling of Spielman and Srivastava (STOC 2008). This gives a new, natural problem in catalytic logspace that is not known to be in deterministic $\mathbf{NC}$ or $\mathbf{SC}$. Our main contribution is an entirely new technique in the compress--or--random paradigm for catalytic logspace that we believe will have further applications. We first analyze effective-resistance sparsification using a pessimistic estimator that can itself be computed in catalytic logspace. The estimator is motivated by the viewpoint of graph quasirandomness and immediately gives a simple, deterministic greedy algorithm for graph sparsification. Subsequently, we show that such a pessimistic estimator can be transformed into an algorithm that performs an in-place compression of a string with bad potential. Our algorithm is based on using the potential function to define a measure over strings, and implementing arithmetic coding using this measure in-place. This compression technique is substantially distinct from all prior tools in the field of catalytic computation.

0.20

Randomized Matvec Lower Bounds for Simplex-Based Matrix Games

cs.DS math.OC ·2026-10-01 ·Wendao Wu, Cong Fang
theory similarity 0.56
Abstract

We prove randomized matrix-vector query lower bounds for two normalized matrix-game geometries: a Euclidean unit ball against a probability simplex, with row norms at most one, and two probability simplices, with entries of absolute value at most one. Each query returns $(Ax,A^\top y)$ for arbitrary real vectors. The algorithm must return a feasible pair with full saddle-point gap at most $\varepsilon$, with probability at least $2/3$ on every admissible matrix. For sufficiently small $\varepsilon$, the worst-case query complexities are $Ω(\varepsilon^{-2/3}/(\log^2(1/\varepsilon)\log\log(1/\varepsilon)))$ for ball-simplex games and $Ω(\varepsilon^{-2/3}/(\log^{7/3}(1/\varepsilon)\log\log(1/\varepsilon)))$ for simplex-simplex games. The hard instances have dimensions of order $\varepsilon^{-2/3}$ and $\varepsilon^{-2/3}/\log^{1/3}(1/\varepsilon)$, respectively, and the bounds extend to larger dimensions. These lower bounds match the deterministic upper bounds of Karmarkar, O'Carroll, and Sidford up to logarithmic factors. The proof extracts a fresh Gaussian core after adaptive two-sided queries and uses uncertainty in its smallest singular value to establish linear-system solve hardness. Two reductions transfer this hardness to matrix games by converting a small full gap into a small residual, with an additional logarithmic normalization loss only for simplex-simplex games.

0.13