Sharp threshold for alignment of graph databases with Gaussian weights
- URL: http://arxiv.org/abs/2010.16295v2
- Date: Tue, 18 May 2021 14:46:09 GMT
- Title: Sharp threshold for alignment of graph databases with Gaussian weights
- Authors: Luca Ganassali
- Abstract summary: We study the fundamental limits for reconstruction in weighted graph (or matrix) database alignment.
We prove that there is a sharp threshold for exact recovery of $pi*$.
- Score: 1.6752182911522522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fundamental limits for reconstruction in weighted graph (or
matrix) database alignment. We consider a model of two graphs where $\pi^*$ is
a planted uniform permutation and all pairs of edge weights $(A_{i,j},
B_{\pi^*(i),\pi^*(j)})_{1 \leq i<j \leq n}$ are i.i.d. pairs of Gaussian
variables with zero mean, unit variance and correlation parameter $\rho \in
[0,1]$. We prove that there is a sharp threshold for exact recovery of $\pi^*$:
if $n \rho^2 \geq (4+\epsilon) \log n + \omega(1)$ for some $\epsilon>0$, there
is an estimator $\hat{\pi}$ -- namely the MAP estimator -- based on the
observation of databases $A,B$ that achieves exact reconstruction with high
probability. Conversely, if $n \rho^2 \leq 4 \log n - \log \log n - \omega(1)$,
then any estimator $\hat{\pi}$ verifies $\hat{\pi}=\pi$ with probability
$o(1)$.
This result shows that the information-theoretic threshold for exact recovery
is the same as the one obtained for detection in a recent work by Wu et al.
(2020): in other words, for Gaussian weighted graph alignment, the problem of
reconstruction is not more difficult than that of detection. Though the
reconstruction task was already well understood for vector-shaped database
alignment (that is taking signal of the form $(u_i, v_{\pi^*(i)})_{1 \leq i\leq
n}$ where $(u_i, v_{\pi^*(i)})$ are i.i.d. pairs in $\mathbb{R}^{d_u} \times
\mathbb{R}^{d_v}$), its formulation for graph (or matrix) databases brings a
drastically different problem for which the hard phase is conjectured to be
wide.
The proofs build upon the analysis of the MAP estimator and the second moment
method, together with the study of the correlation structure of energies of
permutations.
Related papers
- The Umeyama algorithm for matching correlated Gaussian geometric models
in the low-dimensional regime [0.0]
Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permutation.
We consider two types of (correlated) weighted complete graphs with edge weights given by $A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$.
arXiv Detail & Related papers (2024-02-23T04:58:54Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights.
We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs.
Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
arXiv Detail & Related papers (2022-08-18T09:19:01Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
This paper considers learning of the graphical structure of a $p$-dimensional random vector $X in Rp$ using both parametric and non-parametric methods.
Under mild conditions, we show that our graph-structure estimator can obtain the correct structure.
arXiv Detail & Related papers (2022-05-06T19:24:44Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries.
We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$.
As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
arXiv Detail & Related papers (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs.
It can be viewed as a noisy average-case version of the graph isomorphism problem.
arXiv Detail & Related papers (2021-10-11T05:07:50Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms.
We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling"
We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
arXiv Detail & Related papers (2020-06-02T16:38:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.