Pith. sign in

REVIEW 4 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 2306.00266 v2 pith:5K4ZHCDR submitted 2023-06-01 cs.DS math.PRmath.STstat.MLstat.TH

Jian Ding , Zhangsong Li This is my paper · ORCID
classification cs.DSmath.PRmath.STstat.MLstat.TH
keywords algorithmcorrelationmatchingedgenon-vanishingpolynomial-timealphaconstant
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We propose an efficient algorithm for matching two correlated Erd\H{o}s--R\'enyi graphs with $n$ vertices whose edges are correlated through a latent vertex correspondence. When the edge density $q= n^{- \alpha+o(1)}$ for a constant $\alpha \in [0,1)$, we show that our algorithm has polynomial running time and succeeds to recover the latent matching as long as the edge correlation is non-vanishing. This is closely related to our previous work on a polynomial-time algorithm that matches two Gaussian Wigner matrices with non-vanishing correlation, and provides the first polynomial-time random graph matching algorithm (regardless of the regime of $q$) when the edge correlation is below the square root of the Otter's constant (which is $\approx 0.338$).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Chaining 2-FWL GNNs for Combinatorial Graph Alignment

    cs.LG 2025-10 conditional novelty 7.0 of 10

    A chain of ranking-refined 2-FWL GNNs with FAQ post-processing reaches 85% accuracy on sparse Erdos-Renyi graph alignment at noise 0.25, beating FAQ's 13% and prior GNNs' ~0%.

  2. Strong Detection Threshold for Correlated Erd\H{o}s-R\'enyi Graphs with Constant Average Degree

    math.PR 2025-06 conditional novelty 7.0 of 10

    For correlated Erdős-Rényi graphs with constant average degree, strong detection is information-theoretically possible if and only if the subsampling probability s exceeds min{1/√λ, √α}, with α≈0.338.

  3. Sample Complexity of Correlation Detection in the Gaussian Wigner Model

    math.ST 2025-05 conditional novelty 6.0 of 10

    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)).

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

    stat.ML 2024-12 conditional novelty 6.0 of 10

    An approximate message passing algorithm provably recovers the latent matching between correlated Gaussian matrices under adversarial principal-minor corruption of size n/(log n)^20.

Pith tools