For unaligned graph samples under an Erdos-Renyi null with a degree-preserving planted difference, m about t to the minus third power graphs per group are necessary and sufficient, and signed triangles achieve this rate.
and Hajek, B
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
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.
representative citing papers
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.
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.
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.
A last-matching reduction converts two-graph converse bounds into converse bounds for aligning and detecting correlation among m correlated Gaussian and Erdős-Rényi graphs.
The optimal induced-subgraph sample size for detecting correlation in the Gaussian Wigner model is s ≈ sqrt(max(n log n / log(1/(1-ρ^2)), n)).
citing papers explorer
-
Two-Sample Testing for Random Graphs without Vertex Correspondence
For unaligned graph samples under an Erdos-Renyi null with a degree-preserving planted difference, m about t to the minus third power graphs per group are necessary and sufficient, and signed triangles achieve this rate.
-
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
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.
-
Converse bounds for multiple graph alignment and correlation detection based on last matching
A last-matching reduction converts two-graph converse bounds into converse bounds for aligning and detecting correlation among m correlated Gaussian and Erdős-Rényi graphs.
-
Sample Complexity of Correlation Detection in the Gaussian Wigner Model
The optimal induced-subgraph sample size for detecting correlation in the Gaussian Wigner model is s ≈ sqrt(max(n log n / log(1/(1-ρ^2)), n)).