{"id":790,"date":"2024-12-24T07:02:44","date_gmt":"2024-12-24T07:02:44","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2024\/12\/24\/2412-16457\/"},"modified":"2024-12-24T07:02:44","modified_gmt":"2024-12-24T07:02:44","slug":"2412-16457","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2024\/12\/24\/2412-16457\/","title":{"rendered":"Robust random graph matching in dense graphs via vector approximate message passing"},"content":{"rendered":"

Robust random graph matching in dense graphs via vector approximate message passing
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2412.16457v1 Announce Type: new
\nAbstract: In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested in a robust version of this problem such that our observation is a perturbed input $(A+E,B+F)$ where $(A,B)$ is a pair of correlated Gaussian Wigner matrices and $E,F$ are adversarially chosen matrices supported on an unknown $epsilon n * epsilon n$ principle minor of $A,B$, respectively. We propose a vector-approximate message passing (vector-AMP) algorithm that succeeds in polynomial time as long as the correlation $rho$ between $(A,B)$ is a non-vanishing constant and $epsilon = obig( tfrac{1}{(log n)^{20}} big)$.
\n The main methodological inputs for our result are the iterative random graph matching algorithm proposed in cite{DL22+, DL23+} and the spectral cleaning procedure proposed in cite{IS24+}. To the best of our knowledge, our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n^{1-o(1)}$ size.<\/div>\n

\t

\n
<\/BR>
\n Zhangsong Li
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Robust random graph matching in dense graphs via vector approximate message passing arXiv:2412.16457v1 Announce Type: new Abstract: In this paper, we focus on the matching recovery problem between a pair of correlated Gaussian Wigner matrices with a latent vertex correspondence. We are particularly interested in a robust version of this problem such that our observation […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,413,113,420,190,112,191],"tags":[857,902,764],"class_list":["post-790","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-ds","category-cs-lg","category-math-pr","category-math-st","category-stat-ml","category-stat-th","tag-matching","tag-random","tag-robust"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/790"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=790"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/790\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=790"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=790"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=790"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}