Reproduce “Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jiale Cheng, Ziao Wang, Lei Ying
The authors develop a local-neighborhood method for matching nodes across anonymized, structurally similar networks. It approximates costly tree-likelihood calculations and requires five independent neighbor witnesses, rather than three, before accepting a match. Under stated polylogarithmic-degree conditions, it matches n-o(n) nodes with no incorrect matches in n^{2+o(1)} time with high probability; full recovery requires the additional condition λs≥(1+ε)log n.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.