REVIEW 4 cited by
Sharp Detection Threshold for Correlation among Multiple Unlabeled Gaussian Networks
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Sharp Detection Threshold for Correlation among Multiple Unlabeled Gaussian Networks
abstract
This paper studies the hypothesis testing problem of deciding whether $m \geq 2$ complete weighted graphs with Gaussian edge weights are mutually correlated after unknown relabelings of their vertices. Under the null model all edge weights are independent standard Gaussians, whereas under the planted model the graphs share a latent vertex alignment and each pair of corresponding edge weights has correlation $\rho$. For fixed $m$, we identify the sharp information-theoretic threshold for detection. Above the threshold, a generalized likelihood-ratio test achieves strong detection, whereas even weak detection is impossible below the threshold. The result extends the two-graph detection threshold of Wu, Xu, and Yu to any fixed number of graphs, exhibits a side-information regime in which two graphs alone are insufficient but multiple graphs enable detection, and, together with the recovery threshold of Vassaux and Massouli\'e, shows that this Gaussian multi-graph model has no detection--recovery gap.
Forward citations
Cited by 4 Pith papers
-
Graph alignment in sparse inhomogeneous models via self-overlap
Partial graph alignment is feasible exactly on vertices whose balanced load in the intersection graph exceeds the self-overlap of the union graph, giving sharp thresholds for Chung–Lu and stochastic block-model graphs.
-
Attributed Network Alignment: Statistical Limits and Efficient Algorithm
The paper characterizes exact and partial recovery thresholds in the featured correlated Gaussian Wigner model and proposes the QPAlign quadratic programming algorithm with theoretical guarantees.
-
The feasibility of multi-graph alignment: a Bayesian approach
Establishes an all-or-nothing threshold for exact multi-graph alignment in the Gaussian model and a partial-alignment threshold in the sparse Erdős-Rényi model using a general Bayesian estimation framework over metric spaces.
-
The feasibility of multi-graph alignment: a Bayesian approach
Proves all-or-nothing exact alignment threshold in Gaussian multi-graph model and partial alignment impossibility threshold in sparse ER model, via a Bayesian estimation framework over metric spaces.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.