Pith. sign in

REVIEW 2 major objections 6 minor 67 references

Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm

T0 review · 2 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a vector approximate message passing algorithm recovers the exact latent matching between two correlated Gaussian Wigner matrices in polynomial time even when an adversary corrupts an unknown principal minor of size…

desk verdict First robust dense graph matching guarantee that looks new, but the proof's central conditional Gaussian claim is delegated to prior work and needs verification before I'd trust the main theorem. read the letter →

arxiv 2412.16457 v3 pith:C3SWRGSU submitted 2024-12-21 stat.ML cs.DScs.LGmath.PRmath.STstat.TH

Zhangsong Li This is my paper · ORCID
classification stat.MLcs.DScs.LGmath.PRmath.STstat.TH MSC 05C8060B2068Q25
keywords randomgraphmatchingGaussianWignermodelvectorapproximatemessagepassingadversarialrobustnessspectralcleaningrecoverydensegraphspolynomial-timealgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to establish that the exact latent matching between two correlated Gaussian Wigner matrices can be recovered in polynomial time even when both observed matrices have been adversarially corrupted on an unknown $\epsilon n \times \epsilon n$ principal minor, for any fixed correlation $\rho \in (0,1)$ and any $\epsilon = o((\log n)^{-20})$. The proposed algorithm combines a spectral-cleaning preprocessing step with a vector approximate message passing iteration whose time-dependent matrix multiplication grows the feature dimension and cancels correlation across steps. If the main theorem is correct, it is the first efficient random-graph-matching-style algorithm that is robust to adversarial perturbations of size $n^{1-o(1)}$, a regime in which earlier spectral and subgraph-enumeration methods can be derailed by planted structure. A seeded refinement step then upgrades the almost exact output to the exact permutation with probability tending to one.

What carries the argument

The load-bearing object is a vector approximate message passing (vector AMP) iteration with a smooth, bounded, mean-zero denoiser $\varphi$, together with the Gram matrices $\Phi^{(t)}$ and $\Psi^{(t)}$ that track $\langle f^{(t)}, f^{(t)}\rangle$ and $\langle f^{(t)}, g^{(t)}\rangle$. At each step a random near-orthogonal matrix $\beta^{(t)}$ expands the feature dimension from $K_t$ to $K_{t+1} \approx K_t^2$, and a spectral subroutine builds $\Xi^{(t)}$ that approximately diagonalizes both $\Phi^{(t)}$ and $\Psi^{(t)}$, which cancels the correlations between successive iterations and makes the Onsager correction vanish. The iteration is designed so that the signal-to-noise ratio $K_t \varepsilon_t^2$ doubles at each step; the proof controls the clean iteration by a concentration lemma and bounds the corruption effect by a comparison lemma between the corrupted and clean outputs.

What would settle it

Run the AMP iteration on simulated correlated Gaussian Wigner matrices with $n$ around $10^4$, fix one past iterate, and test whether each row of $h^{(t)}$ and $\ell^{(t)}$ is conditionally Gaussian with variance $1 + O(K_t^{20}\Delta_t)$ and perturbations of size $O(K_t^{40}\Delta_t^2)$; a statistically significant deviation in the conditional tails or variances would break Lemma 14 and with it the polynomial-time guarantee.

Watch

Extended reading notes

Core claim

The central discovery, stated as Theorem 1.3 and Theorem 2.1, is that for constant $\rho \in (0,1)$ and $\epsilon = o((\log n)^{-20})$, Algorithm 3 runs in $O(n^C)$ time with $C = C(\rho)$ and outputs $\pi^*$ with probability $1-o(1)$ under $\epsilon$-corrupted Gaussian Wigner observations. The algorithm first symmetrizes the observations and zeroes out at most $4\epsilon n$ rows and columns by spectral cleaning, then runs a vector-AMP iteration from $K_0$ seed vertices. The iteration maintains Gram matrices $\Phi^{(t)}$ and $\Psi^{(t)}$ that track the covariance of the message features and their cross-covariance; the signal-to-noise ratio $K_t \varepsilon_t^2$ is shown to grow doubly exponentially and reach $\gg (\log n)^{1.01}$ by time $t_*$. At that point the linear assignment step matches all but $O(n/\log n)$ vertices, and a seeded graph matching routine finishes the exact recovery.

Load-bearing premise

The whole concentration argument depends on the assertion in Claim G.1 that, after conditioning on the past iterates, the rows of the message matrices are independent Gaussians with variance $1 + O(K_t^{20}\Delta_t)$ plus tiny Gaussian perturbations; the paper does not prove this for the correlated two-matrix iteration and instead refers to a companion work that it says 'can be easily adapted'.

Editorial extensions

If this is right

  • Exact matching recovery holds in $O(n^C)$ time whenever the correlation is a fixed constant and the adversarial block has size $n/(\log n)^{20}$ or smaller.
  • This is the first efficient random graph matching type algorithm robust to adversarial perturbations of size $n^{1-o(1)}$; previous efficient methods relied on spectral or subgraph-counting tools that planted cliques can destabilize.
  • The AMP iteration has a vanishing Onsager correction, so the standard message-passing state evolution applies despite the correlated two-matrix setting.
  • The output of the AMP phase is an almost exact matching, and the seeded matching algorithm upgrades it to exact matching with probability tending to one.
  • The robustness guarantee holds for dense Gaussian Wigner observations; the accompanying scoring statistic selects the true permutation among all candidate seed pairs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One direction the paper leaves open is whether the corruption tolerance can be raised to a constant fraction $\epsilon$; since the bottlenecks are logarithmic factors, a sharper concentration induction on the same architecture would be the natural route.
  • A testable extension is to dense correlated Erdős–Rényi graphs with constant edge density: the smooth-denoiser AMP and spectral cleaning may transfer once the Bernoulli observation noise is handled in the comparison lemma.
  • The proof's concentration argument rests on a deferred conditional-Gaussianity claim; if that claim holds, the same analysis should apply to other bilinear AMP iterations with correlated random matrices, while if it fails, the entire induction would need replacement.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies exact matching recovery for a pair of correlated Gaussian Wigner matrices (A,B) with latent permutation pi*, under adversarial perturbations E,F supported on an unknown epsilon n by epsilon n principal minor of each matrix. The main result (Theorems 1.3 and 2.1) states that for constant rho in (0,1) and epsilon = o((log n)^{-20}), there is an O(n^C) algorithm that outputs pi* with probability 1-o(1). The algorithm combines a preprocessing and spectral cleaning step (Ivkov-Schramm), a spectral subroutine that constructs matrices Phi(t), Psi(t) and random beta(t), a vector AMP iteration with a smooth denoiser phi, and a seeded graph matching finishing step. The proof proceeds by comparing the corrupted iterates (hat f, hat g) to clean iterates (f, g) through Lemmas 4 and 5, where Lemma 4 is a concentration estimate for the clean AMP iterates driven by a conditional Gaussian claim (Claim G.1).

Significance. If the main theorem is correct, the paper gives the first polynomial-time random graph matching algorithm robust to n^{1-o(1)} adversarial principal-minor perturbations in the correlated Gaussian Wigner model, a qualitative improvement over prior non-robust algorithms. The spectral cleaning lemma, the seeded matching step, and the clean-vs-corrupted comparison framework are presented in substantial detail, and the running time analysis is concrete. The central caveat is that the proof rests on a conditional Gaussian characterization that is not proved in this manuscript and, as stated, appears internally inconsistent; the significance is therefore conditional on repairing that argument.

major comments (2)
  1. [Appendix G.1, Claim G.1 and Section G.2] As stated in (G.7), the claim asserts that, conditional on F_t, (h(t), l(t)) has the law of (G+delta, H+kappa) with G and H independent Gaussians of variance 1+O(K_t^{20} Delta_t) and with delta, kappa of variance O(K_t^{40} Delta_t^2). Under this statement the cross-covariance between h_i and l_i is O(K_t^{40} Delta_t^2), which cannot account for the signal <h_i^{(t*)}, l_i^{(t*)}> >= 0.9 K_{t*} epsilon_{t*} used in Lemma 4, nor for the expectation Psi^{(t+1)} in the proof of Item (3) of Lemma 14, since E[phi(Sigma G beta_i) phi(Sigma H beta_j)] would be O(K_t^{20} Delta_t) rather than Psi^{(t+1)}_{ij}. The claim needs a precise statement of the joint covariance of G and H, or an explicit cross term, together with a proof of that statement. The current text delegates the proof to Ding and Li (2025+) for a step-function denoiser and says it can be easily adapted to the smooth phi of Definition B.1, but no adaptation is given. Since Lemma 14, Lemma 4, and Proposition 2 all rest on this assertion, this is a load-bearing gap.
  2. [Appendix C, Lemma 10] The four concentration estimates (C.7)-(C.10) are asserted to follow from (Ding and Li, 2025+, Proposition 2.4), and no proof is provided in this manuscript. These estimates are used in the proof of Lemma 9 to control Phi^{(t+1)} and Psi^{(t+1)} and to ensure that the spectral recursion (2.7) holds with positive probability, which is what makes Algorithm 3 well-defined. Please include the full argument or, at minimum, a precise statement of the cited proposition and a verification that its constants match the choices in (2.8)-(2.9).
minor comments (6)
  1. [Abstract and Definition 1.2] The text repeatedly uses 'principle minor' where 'principal minor' is intended; please correct throughout.
  2. [Appendix A, proof of Lemma 6] The proof says each I_t is 'stochastically dominated by a Bernoulli random variable with parameter 1/2', but the argument shows P(I_t=1) >= 1/2 on the high-probability event, so I_t stochastically dominates a Bernoulli(1/2). The subsequent binomial bound is correct, but the wording should be fixed.
  3. [Algorithm 3, line 10] The loop condition 'while K_t <= exp{(log log n)^2}' is inconsistent with the stopping time t* defined in (2.12) as the first t with K_t >= (log n)^{1.1}, since exp{(log log n)^2} is much larger than (log n)^{1.1}. As written, the algorithm continues beyond t*, while all proofs in Appendices G-I are only for t <= t*. The condition should presumably be 'while K_t < (log n)^{1.1}'.
  4. [Appendix G.1.4] In the proof of Item (5) of Lemma 14, the notation f^{(t+1)}_{W x [K_t]} should be f^{(t+1)}_{W x [K_{t+1}]}; the subsequent sum is over i <= K_{t+1}, and the same notational slip appears for g^{(t+1)}.
  5. [Appendix B, Definition B.1] The existence of a smooth phi satisfying all the listed properties is asserted but no construction is given. A short example, such as a suitably rescaled cosine, would make the definition self-contained.
  6. [Section 1.2] The sentence 'involves solving certain linear equations with coefficients depends on depend on all prior AMP iterations' contains duplicated text and should be edited.

Circularity Check

2 steps flagged · score 4.0 of 10

Central concentration proof relies on an unproved, “easily adapted” two-matrix conditional Gaussianity claim delegated to the author’s own Ding-Li 2025+; the theorem is not reduced to its inputs by construction, but the proof as written is not self-contained.

  1. self citation load bearing [Appendix G.1, immediately after Eq. (G.7) (Claim G.1)]
    "The proof of Claim G.1 is established Ding and Li (2025+) in which they take φ(x) = 1{|x|≥10} − P(|N (0, 1)| ≥10) ; their proof can be easily adapted to the case of all symmetric, mean-zero and bounded φ and thus we omit further details here for simplicity."

    Claim G.1 is the conditional-Gaussianity input that drives the induction for Lemma 14, and through Lemma 14 supports Lemma 4, Lemma 5, Proposition 2, and Theorem 2.1. The paper does not prove this claim for the correlated two-matrix iteration; it delegates the proof to Ding and Li (2025+), a paper by the present author with a coauthor, and merely asserts that the proof “can be easily adapted” to the smooth denoiser φ. Because the cited proof is stated for a different, step-function denoiser and the current φ is smooth (Definition B.1), the adaptation requires re-deriving the Gaussian-perturbation and Taylor-expansion steps; the manuscript supplies none of that. The load-bearing premise is therefore imported from the authors’ own cited chain rather than demonstrated in this paper.

  2. self citation load bearing [Appendix G, proof of Lemma 14, before Appendix G.1.1]
    "In fact, it has been shown in (Ding and Li, 2025+, Proposition 3.4) that Items (1)–(4) hold for all 0 ≤ t ≤ t∗ with probability 1−o(1) (although we need to make some slight modifications since we slightly simplified the iteration process). The main effort in this paper is to establish Items (5)–(7)."

    Items (1)–(4) of Lemma 14 are the concentration bounds on (f(s))⊤f(s) − Φ(s), (f(s))⊤g(s) − Ψ(s), and cross-time inner products. These are asserted to follow from the author’s own prior work, with only “slight modifications” that are not shown. Since these items are part of the event E_t used in the proof of Lemma 4 and Proposition 2, the central concentration induction is still completed by citation to the authors’ own chain rather than by a self-contained argument. The paper’s genuinely new contribution is restricted to Items (5)–(7), so the proof of the main theorem inherits its core from the self-cited prior work.

full rationale

No pattern 1, 2, 5, or 6 circularity is present: the theorem’s conclusion is not encoded in the definition of an input, no fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors, and no known result is merely relabeled. The robust matching claim is an independent new statement, and the spectral cleaning (Algorithm 1), comparison bound (Lemma 5), seeded matching step (Lemma 11), and final permutation selection (Lemma 3) are argued in the paper with their own proofs. However, the proof is not self-contained at its most load-bearing point. Claim G.1, the conditional Gaussianity of h(t) and ℓ(t) given the past iterates, is the engine of the induction proving Lemma 14; the paper states that its proof is in Ding and Li (2025+) for a step-function denoiser and that it “can be easily adapted” to the smooth φ of Definition B.1, but the adaptation is omitted. Ding and Li (2025+) is authored by the present author and a coauthor, is not machine-checked or code-reproduced within the manuscript, and is not an external benchmark independent of the present paper’s argument. Likewise, Items (1)–(4) of Lemma 14 are attributed to Proposition 3.4 of the same self-cited work with only “slight modifications.” These are not construction-level reductions of the theorem to its inputs, so a high circularity score such as 8 or 10 would be disproportionate. But they are load-bearing self-citations at the center of the concentration proof, so a score of 4 reflects that the central claim still has independent content while the proof as written relies on the authors’ own cited chain for its key lemma.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The proof rests on standard random-matrix bounds, on two technical lemmas imported from the author's prior work (Claim G.1, Lemma 10), and on hand-chosen algorithmic constants (phi, K_0). The constants are design choices rather than fits to data. The robustness claim itself is not assumed from any cited result.

free parameters (2)
  • Denoiser phi = existence asserted, coefficients a_i, b_i unspecified
    Smooth function in Definition B.1 chosen by hand to satisfy derivative and moment conditions; not fitted to data. It determines the correlation function phi(u) and the SNR recursion.
  • Seed length K_0 = sufficiently large constant satisfying (2.4)
    Hand-chosen integer depending on rho and phi; governs the number of enumerated seed sequences M approximately n^{K_0} and the runtime O(n^{2K_0+3+o(1)}). Its size is chosen to force K_t epsilon_t^2 to grow (3.6).
assumptions (6)
  • domain assumption Claim G.1: conditional distribution (h(t), l(t)) given F_t is a pair of independent Gaussians plus small Gaussian perturbations.
    Load-bearing for the induction in Lemma 14. Proof delegated to Ding and Li (2025+) with 'can be easily adapted'; not proved in this paper (Appendix G.1).
  • standard math Lemma 10: concentration bounds (C.7)-(C.10) for random sign matrix beta(t) and its Psi(t)-weighted products.
    Proof omitted; cited to Ding and Li (2025+), Proposition 2.4 (Appendix C).
  • standard math Spectral norm bound ||A_hat||_op <= (2+o(1)) sqrt(n) for i.i.d. sub-Gaussian matrices.
    Used in Algorithm 1 and Lemma 7; from Vershynin (2018), Theorem 4.4.5.
  • ad hoc to paper Existence of a smooth denoiser phi with E[phi(X)] = 0, E[phi(X)^2] = 1, bounded derivatives, and expansion coefficients |c_k| <= Lambda * 2^k with c_0 = c_1 = 0.
    Definition B.1 asserts existence of phi with these properties; no explicit construction or proof of existence is given. phi is used in initialization (2.5) and iteration (2.11).
  • domain assumption The correlation rho can be reduced to any desired small constant by adding i.i.d. Gaussian noise (2.1).
    Standard dithering trick; dithering preserves the information-theoretic setting.
  • domain assumption Technical restriction 1/(log n)^{100} <= epsilon = o(1/(log n)^{20}) (G.1).
    The paper assumes this range 'without loss of generality'; for smaller epsilon the corruption is even easier and the proof still applies.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm." pith.science (2026). https://pith.science/paper/C3SWRGSU

@misc{pith2026241216457,
  author       = {Pith},
  title        = {Pith review of: Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C3SWRGSU}},
  note         = {Machine review of arXiv:2412.16457}
}
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 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$ principal minor of $A,B$, respectively. We propose an approximate message passing (AMP) type iterative algorithm that succeeds in polynomial time as long as the correlation $\rho$ between $(A,B)$ is a non-vanishing constant and $\epsilon = o\big( \tfrac{1}{(\log n)^{20}} \big)$. A key distinction from standard AMP is the introduction of a time-dependent matrix multiplication step within the iteration, which simultaneously enlarges the feature dimension and cancels the correlation during the iteration. The main methodological inputs for our result are the iterative random graph matching algorithm proposed in \cite{DL22+, DL23+} and the spectral preprocessing 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 58 canonical work pages

  1. [1]

    Robust graph matching when nodes are corrupt

    Taha Ameen and Bruce Hajek. Robust graph matching when nodes are corrupt. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 1276--1305. PMLR, 2024

    work page 2024

  2. [2]

    Graph isomorphism in quasi-polynomial time

    L\' a szl\' o Babai. Graph isomorphism in quasi-polynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 684--697. ACM, 2016

    work page 2016

  3. [3]

    Robust linear regression: optimal rates in polynomial time

    Ainesh Bakshi and Adarsh Prasad. Robust linear regression: optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 102--115. ACM, 2021

    work page 2021

  4. [4]

    ( N early) efficient algorithms for the graph matching problem on correlated random graphs

    Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi Sheng. ( N early) efficient algorithms for the graph matching problem on correlated random graphs. In Advances in Neural Information Processing Systems (NIPS), volume 32. Curran Associates, Inc., 2019

    work page 2019

  5. [5]

    The dynamics of message passing on dense graphs, with applications to compressed sensing

    Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory, 57 0 (2): 0 764--785, 2011

    2011

  6. [6]

    Berg, Tamara L

    Alexander C. Berg, Tamara L. Berg, and Jitendra Malik. Shape matching and object recognition using low distortion correspondences. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pages 26--33. IEEE, 2005

    work page 2005

  7. [7]

    An iterative construction of solutions of the TAP equations for the S herrington- K irkpatrick model

    Erwin Bolthausen. An iterative construction of solutions of the TAP equations for the S herrington- K irkpatrick model. Communications in Mathematical Physics, 325 0 (1): 0 333--366, 2014

    work page 2014

  8. [8]

    Gardner formula for I sing perceptron models at small densities

    Erwin Bolthausen, Shuta Nakajima, Nike Sun, and Changji Xu. Gardner formula for I sing perceptron models at small densities. In Proceedings of 35th Conference on Learning Theory (COLT), pages 1787--1911. PMLR, 2022

    work page 1911

Show all 67 references
  1. [9]

    Seedless graph matching via tail of degree distribution for correlated Erd o s-R\' e nyi graphs

    Mahdi Bozorg, Saber Salehkaleybar, and Matin Hashemi. Seedless graph matching via tail of degree distribution for correlated Erd o s-R\' e nyi graphs. arXiv preprint, arXiv:1907.06334, 2019

    1907 arXiv

  2. [10]

    Burkard, Eranda Cela, Panos M

    Rainer E. Burkard, Eranda Cela, Panos M. Pardalos, and Leonidas S. Pitsoulis. The quadratic assignment problem. Handbook of combinatorial optimization, pages 1713--1809, 1998

    1998

  3. [11]

    Shuwen Chai and Miklos Z. Racz. Efficient graph matching for correlated stochastic block models. In Advances in Neural Information Processing Systems (NIPS), volume 37. Curran Associates, Inc., 2024

    2024

  4. [12]

    A computational transition for detecting correlated stochastic block models by low-degree polynomials

    Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. A computational transition for detecting correlated stochastic block models by low-degree polynomials. arXiv preprint, arXiv:2409.00966, 2024

    2024

  5. [13]

    Balanced graph matching

    Timothee Cour, Praveen Srinivasan, and Jianbo Shi. Balanced graph matching. In Advances in Neural Information Processing Systems (NIPS), volume 19. MIT Press, 2006

    2006

  6. [14]

    Improved achievability and converse bounds for Erd o s-R\' e nyi graph matching

    Daniel Cullina and Negar Kiyavash. Improved achievability and converse bounds for Erd o s-R\' e nyi graph matching. In Proceedings of the 2016 ACM International Conference on Measurement and Modeling of Computer Science, pages 63--72. ACM, 2016

    2016

  7. [15]

    Exact alignment recovery for correlated Erd o s-R\' e nyi graphs

    Daniel Cullina and Negar Kiyavash. Exact alignment recovery for correlated Erd o s-R\' e nyi graphs. arXiv preprint, arXiv:1711.06783, 2017

    2017 arXiv

  8. [16]

    Vincent Poor

    Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H. Vincent Poor. Partial recovery of Erd o s-R\' e nyi graph alignment via k -core alignment. In Proceedings of the 2020 ACM International Conference on Measurement and Modeling of Computer Science, pages 99--100. ACM, 2020

    2020

  9. [17]

    Information-theoretically optimal sparse PCA

    Yash Deshpande and Andrea Montanari. Information-theoretically optimal sparse PCA . In IEEE International Symposium on Information Theory (ISIT), pages 2197--2201. IEEE, 2014

    2014

  10. [18]

    Detection threshold for correlated Erd o s-R\' e nyi graphs via densest subgraph

    Jian Ding and Hang Du. Detection threshold for correlated Erd o s-R\' e nyi graphs via densest subgraph. IEEE Transactions on Information Theory, 69 0 (8): 0 5289--5298, 2023 a

    2023

  11. [19]

    Matching recovery threshold for correlated random graphs

    Jian Ding and Hang Du. Matching recovery threshold for correlated random graphs. Annals of Statistics, 51 0 (4): 0 1718--1743, 2023 b

    2023

  12. [20]

    A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation

    Jian Ding and Zhangsong Li. A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation. arXiv preprint, arXiv:2306.00266, 2023

    2023 arXiv

  13. [21]

    A polynomial time iterative algorithm for matching G aussian matrices with non-vanishing correlation

    Jian Ding and Zhangsong Li. A polynomial time iterative algorithm for matching G aussian matrices with non-vanishing correlation. Foundations of Computational Mathematics, 2025+

    2025

  14. [22]

    Capacity lower bound for the I sing perceptron

    Jian Ding and Nike Sun. Capacity lower bound for the I sing perceptron. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 816--827. ACM, 2019

    2019

  15. [23]

    Efficient random graph matching via degree profiles

    Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 179 0 (1-2): 0 29--115, 2021

    2021

  16. [24]

    Efficiently matching random inhomogeneous graphs via degree profiles

    Jian Ding, Yumou Fei, and Yuanzheng Wang. Efficiently matching random inhomogeneous graphs via degree profiles. arXiv preprint, arXiv:2310.10441, 2023

    2023 arXiv

  17. [25]

    Low-degree hardness of detection for correlated Erd o s-R\' e nyi graphs

    Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for correlated Erd o s-R\' e nyi graphs. Annals of Statistics, 2025+

    2025

  18. [26]

    Robust recovery for stochastic block models

    Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, and David Steurer. Robust recovery for stochastic block models. In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 387--394. IEEE, 2022

    2022

  19. [27]

    Donoho, Arian Maleki, and Andrea Montanari

    David L. Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences of the United State of America, 106 0 (45), 2009

    2009

  20. [28]

    Optimal recovery of correlated graphs

    Hang Du. Optimal recovery of correlated graphs. arXiv preprint, arXiv:2502.12077, 2025

    2025 arXiv

  21. [29]

    Dubhashi and Alessandro Panconesi

    Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge, 2009

    2009

  22. [30]

    The replica-symmetric free energy for I sing spin glasses with orthogonally invariant couplings

    Zhou Fan and Yihong Wu. The replica-symmetric free energy for I sing spin glasses with orthogonally invariant couplings. Probability Theory and Related Fields, 190 0 (1-2): 0 1--77, 2024

    2024

  23. [31]

    Spectral graph matching and regularized quadratic relaxations I : The G aussian model

    Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations I : The G aussian model. Foundations of Computational Mathematics, 23 0 (5): 0 1511--1565, 2023 a

    2023

  24. [32]

    Spectral graph matching and regularized quadratic relaxations II : Erd o s-R\' e nyi graphs and universality

    Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations II : Erd o s-R\' e nyi graphs and universality. Foundations of Computational Mathematics, 23 0 (5): 0 1567--1617, 2023 b

    2023

  25. [33]

    TAP equations for orthogonally invariant spin glasses at high temperature

    Zhou Fan, Yufan Li, and Subhabrata Sen. TAP equations for orthogonally invariant spin glasses at high temperature. Annales de l’IHP Probabilit\' e s et Statistiques , 2025+

    2025

  26. [34]

    Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J

    Oliver Y. Feng, Ramji Venkataramanan, Cynthia Rush, and Richard J. Samworth. A unifying tutorial on approximate message passing. Foundations and Trends in Machine Learning, 15 0 (4): 0 335--536, 2022

    2022

  27. [35]

    From tree matching to sparse graph alignment

    Luca Ganassali and Laurent Massouli\'e. From tree matching to sparse graph alignment. In Proceedings of 33rd Conference on Learning Theory (COLT), pages 1633--1665. PMLR, 2020

    2020

  28. [36]

    Impossibility of partial recovery in the graph alignment problem

    Luca Ganassali, Laurent Massoulie, and Marc Lelarge. Impossibility of partial recovery in the graph alignment problem. In Proceedings of 34th Conference on Learning Theory (COLT), pages 2080--2102. PMLR, 2021

    2021

  29. [37]

    Correlation detection in trees for planted graph alignment

    Luca Ganassali, Laurent Massouli\' e , and Marc Lelarge. Correlation detection in trees for planted graph alignment. Annals of Applied Probability, 34 0 (3): 0 2799--2843, 2024 a

    2024

  30. [38]

    Statistical limits of correlation detection in trees

    Luca Ganassali, Laurent Massouli\' e , and Guilhem Semerjian. Statistical limits of correlation detection in trees. Annals of Applied Probability, 34 0 (4): 0 3701--3734, 2024 b

    2024

  31. [39]

    The U meyama algorithm for matching correlated G aussian geometric models in the low-dimensional regime

    Shuyang Gong and Zhangsong Li. The U meyama algorithm for matching correlated G aussian geometric models in the low-dimensional regime. arXiv preprint, arXiv:2402.15095, 2024

    2024 arXiv

  32. [40]

    Robust textual inference via graph matching

    Aria Haghighi, Andrew Ng, and Christopher Manning. Robust textual inference via graph matching. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 387--394, 2005

    2005

  33. [41]

    Partial recovery in the graph alignment problem

    Georgina Hall and Laurent Massouli\'e. Partial recovery in the graph alignment problem. Operations Research, 71 0 (1): 0 259--272, 2022

    2022

  34. [42]

    Semidefinite programs simulate approximate message passing robustly

    Misha Ivkov and Tselil Schramm. Semidefinite programs simulate approximate message passing robustly. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 348--357. ACM, 2024

    2024

  35. [43]

    Fast, robust approximate message passing

    Misha Ivkov and Tselil Schramm. Fast, robust approximate message passing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC). ACM, 2025

    2025

  36. [44]

    Probabilistic graphical models: principles and techniques

    Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT Press, 2009

    2009

  37. [45]

    Kothari, Jacob Steinhardt, and David Steurer

    Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1035--1046. ACM, 2018

    2018

  38. [46]

    Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

    Florent Krzakala, Marc M\'ezard, Francois Sausset, Yifan Sun, and Lenka Zdeborov\' a . Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices. Journal of Statistical Mechanics: Theory and Experiment, 2012 0 (08), 2012

    2012

  39. [47]

    Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 0 (1-2): 0 83--97, 1955

    1955

  40. [48]

    Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm

    Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm. International Colloquium on Automata, Languages, and Programming, pages 594--604, 2010

    2010

  41. [49]

    Random graph matching with improved noise robustness

    Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. Random graph matching with improved noise robustness. In Proceedings of 34th Conference on Learning Theory (COLT), pages 3296--3329. PMLR, 2021

    2021

  42. [50]

    Exact matching of random graphs with constant correlation

    Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. Exact matching of random graphs with constant correlation. Probability Theory and Related Fields, 186 0 (1-2): 0 327--389, 2023 a

    2023

  43. [51]

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Random graph matching at O tter's threshold via counting chandeliers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1345--1356. ACM, 2023 b

    2023

  44. [52]

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Testing network correlation efficiently via counting trees. Annals of Statistics, 52 0 (6): 0 2483--2505, 2024

    2024

  45. [53]

    Sidhanth Mohanty, Prasad Raghavendra, and David X. Wu. Robust recovery for stochastic block models, simplified and generalized. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 367--374. ACM, 2024

    2024

  46. [54]

    Graphical models concepts in compressed sensing

    Andrea Montanari. Graphical models concepts in compressed sensing. Compress Sensing, pages 394--438, 2012

    2012

  47. [55]

    Non-negative principal component analysis: Message passing algorithms and sharp asymptotics

    Andrea Montanari and Emile Richard. Non-negative principal component analysis: Message passing algorithms and sharp asymptotics. IEEE Transactions on Information Theory, 62 0 (3): 0 1458--1484, 2015

    2015

  48. [56]

    Semidefinite programs on sparse random graphs and their application to community detection

    Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 814--827. ACM, 2016

    2016

  49. [57]

    Seeded graph matching via large neighborhood statistics

    Elchanan Mossel and Jiaming Xu. Seeded graph matching via large neighborhood statistics. Random Structures and Algorithms, 57 0 (3): 0 570--611, 2020

    2020

  50. [58]

    Robust de-anonymization of large sparse datasets

    Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In 29th IEEE Symposium on Security and Privacy, pages 111--125. IEEE, 2008

    2008

  51. [59]

    De-anonymizing social networks

    Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In 30th IEEE Symposium on Security and Privacy, pages 173--187. IEEE, 2009

    2009

  52. [60]

    Racz and Anirudh Sridhar

    Miklos Z. Racz and Anirudh Sridhar. Correlated stochastic block models: Exact graph matching with applications to recovering communities. In Advances in Neural Information Processing Systems (NIPS), volume 34. Curran Associates, Inc., 2021

    2021

  53. [61]

    Global alignment of multiple protein interaction networks with application to functional orthology detection

    Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences of the United States of America, 105: 0 12763--12768, 2008

    2008

  54. [62]

    Thouless, Philip W

    David J. Thouless, Philip W. Anderson, and Richard G. Palmer. Solution of ‘solvable model of a spin glass’. Philosophical Magazine, 35 0 (3): 0 593--601, 1977

    1977

  55. [63]

    High-dimensional probability: An introduction with applications in data science

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, 2018

    2018

  56. [64]

    Random graph matching in geometric models: the case of complete graphs

    Haoyu Wang, Yihong Wu, Jiaming Xu, and Israel Yolou. Random graph matching in geometric models: the case of complete graphs. In Proceedings of 35th Conference on Learning Theory (COLT), pages 3441--3488. PMLR, 2022

    2022

  57. [65]

    Yihong Wu, Jiaming Xu, and Sophie H. Yu. Settling the sharp reconstruction thresholds of random graph matching. IEEE Transactions on Information Theory, 68 0 (8): 0 5391--5417, 2022

    2022

  58. [66]

    Yihong Wu, Jiaming Xu, and Sophie H. Yu. Testing correlation of unlabeled random graphs. Annals of Applied Probability, 33 0 (4): 0 2519--2558, 2023

    2023

  59. [67]

    On the performance of percolation graph matching

    Lyudmila Yartseva and Matthias Grossglauser. On the performance of percolation graph matching. In Proceedings of the 1st ACM Conference on Online Social Networks, pages 119--130. ACM, 2013

    2013

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.