Pith. sign in

REVIEW 4 cited by

Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery

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 2405.12293 v2 pith:Y4TBY7Y3 submitted 2024-05-20 cs.DS cs.DMmath.STstat.TH

Taha Ameen , Bruce Hajek This is my paper · ORCID
classification cs.DScs.DMmath.STstat.TH
keywords graphsinhomogeneousexactmatchingrandomsettingalgorithmcondition
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

This work studies fundamental limits for recovering the underlying correspondence among multiple correlated graphs. In the setting of inhomogeneous random graphs, we present and analyze a matching algorithm: first partially match the graphs pairwise and then combine the partial matchings by transitivity. Our analysis yields a sufficient condition on the problem parameters to exactly match all nodes across all the graphs. In the setting of homogeneous (Erd\H{o}s-R\'enyi) graphs, we show that this condition is also necessary, i.e. the algorithm works down to the information theoretic threshold. This reveals a scenario where exact matching between two graphs alone is impossible, but leveraging more than two graphs allows exact matching among all the graphs. Converse results are also given in the inhomogeneous setting and transitivity again plays a role. Along the way, we derive independent results about the k-core of inhomogeneous random graphs.

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. Graph alignment in sparse inhomogeneous models via self-overlap

    math.PR 2026-07 conditional novelty 7.0 of 10

    Partial graph alignment is feasible exactly on vertices whose balanced load in the intersection graph exceeds the self-overlap of the union graph, giving sharp thresholds for Chung–Lu and stochastic block-model graphs.

  2. Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests

    cs.DS 2026-07 unverdicted novelty 7.0 of 10

    A rank-based local tree correlation test almost exactly matches vertices of correlated Erdős-Rényi graphs in n^{2+o(1)} time when average degree is polylog and edge correlation exceeds Otter's constant.

  3. Harnessing Multiple Correlated Networks for Exact Community Recovery

    math.ST 2024-12 conditional novelty 7.0 of 10

    For any fixed K, exact community recovery from K edge-correlated stochastic block models is characterized by a two-part inequality combining graph matchability and single-graph community signal.

  4. Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery

    cs.SI 2025-01 conditional novelty 6.0 of 10

    Exact node matching and community recovery in correlated stochastic block models with correlated attributes are possible when the edge-correlation SNR plus the attribute-correlation SNR exceeds a logarithmic threshold.

Pith tools