Pith. sign in

REVIEW 2 major objections 4 minor 24 references

The paper proves that the balanced-load-versus-self-overlap comparison determines which vertices of two correlated sparse graphs can be aligned, and that the threshold is sharp across a wide class of inhomogeneous models.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

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.

T0 review reviewed 2026-08-02 challenge →

load-bearing objection A genuinely new alignment framework with a clean general lower bound, but the sharpness side is not as self-contained as the claims require—Theorem 3's condition (22) doesn't hold in the Chung–Lu and SBM corollaries, and the ER self-overlap value is proven using Du's theorem. the 2 major comments →

arxiv 2607.14948 v1 pith:A4AZ7LRB submitted 2026-07-16 math.PR math.STstat.TH

Graph alignment in sparse inhomogeneous models via self-overlap

Louis Vassaux This is my paper
classification math.PR math.STstat.TH MSC 62B1005C8005C60
keywords graph alignmentinhomogeneous random graphsbalanced loadself-overlapcorrelated random graphspartial recoverystochastic block modelChung–Lu model
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

Graph alignment asks which vertices of two correlated but unlabelled sparse graphs can be correctly matched. This paper's answer: in weakly inhomogeneous models, the recoverable vertices are exactly those whose balanced load in the true intersection graph exceeds a newly introduced parameter, the self-overlap, which measures how well the graph can imitate itself under a non-trivial relabelling. The main theorem gives an estimator that achieves this lower bound for any correlated graph system. In the weakly inhomogeneous class, the paper proves the matching converse — below the threshold no estimator can succeed — and derives sharp phase transitions for Chung–Lu graphs and stochastic block models. If correct, graph alignment is governed by local density rather than by global model parameters.

Core claim

The paper's central discovery is that the information-theoretic feasibility of partial graph alignment is controlled by a comparison between two graph-level quantities. For any correlated graph system, with ρ = SOV(U) the self-overlap of the union graph, there exists an estimator that recovers the planted matching on every vertex whose balanced load in the true intersection graph I is at least ρ+ε, up to o(n) errors. In the weakly inhomogeneous regime, where the self-overlap is at most 1, the paper proves that for any estimator there are at least x_sparse (n − o(n)) vertices, with x_sparse the limiting fraction of vertices with balanced load below 1−ε, on which it must fail — provided the ed

What carries the argument

The paper's machinery is a comparison between two quantities. The balanced load function, inherited from the classical load-balancing literature, assigns each vertex a 'local density' value; it is the unique load map of any balanced allocation on a graph. The self-overlap SOV(U) is a new parameter: it is the limiting value, over relabellings σ and large subsets A of moved vertices, of the minimum balanced load in U ∧ σU. The proof of the lower bound shows that any permutation that errs on many vertices of sufficiently high balanced load would force SOV(U) to be larger than its definition allows; the upper bound, in the weakly inhomogeneous case, shows that vertices in small tree components o

Load-bearing premise

The sharpness of the threshold depends on the noise-robustness condition min_e p_e ≥ (log n)^r / n; the author states it is unclear whether the impossibility theorem survives without it, and if it fails, non-edges in the intersection graph could leak enough information to align more than x_sparse vertices.

What would settle it

A concrete way to test the sharpness claim: simulate a correlated inhomogeneous system with most edge probabilities at 1/n but a small positive fraction of edges with probability n^{-2}, so condition (22) fails. Compute the balanced load in the true intersection graph and x_sparse from the model, then run an exhaustive-search maximum-likelihood estimator on small n. If the estimator succeeds on a positive fraction of vertices with balanced load below 1−ε, the claimed contrast between Theorem 1 and Theorem 3, and hence the sharp threshold, is false.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • In Erdős–Rényi graphs with edge probability λ/n^α, the framework recovers the known optimal threshold and gives SOV = 1/(2α−1).
  • For Chung–Lu graphs with degree law ν, partial alignment is feasible when s^2 > E[D^2]/E[D] and impossible when s^2 < E[D^2]/E[D] (under a boundedness condition on ν); the threshold is zero if E[D^2] is infinite.
  • For stochastic block models, partial alignment is feasible exactly when s^2 λ > 1, where λ is the Perron–Frobenius eigenvalue of the community matrix.
  • In any weakly inhomogeneous model satisfying the noise-robustness condition, the vertices that cannot be aligned are asymptotically exactly those in tree components of the intersection graph of size at most 1/ε — the vertices with balanced load below 1−ε.
  • The estimator from Theorem 1 needs no model-specific tuning; it selects a permutation maximizing the number of vertices with balanced load above ρ+ε.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the self-overlap is defined from a single graph, so in principle it could be estimated empirically from one observed network; this would turn the theorem into a checkable criterion for which vertices in a real pair of networks are matchable without knowing the generative model.
  • Editorial inference: the paper's Appendix F exhibits a system where the set of vertices the estimator can align is asymptotically disjoint from the set with high balanced load; this suggests that the 'recoverable set' may be estimator-dependent, and characterizing all attainable sets is a natural next problem.
  • Editorial inference: the author's stated uncertainty about condition (22) points to a concrete research program: proving or disproving Theorem 3 for models with very small edge probabilities, where non-edges may leak information about the matching.
  • Editorial inference: because SOV(K) ≤ 1 for all weakly inhomogeneous graphs, the framework predicts that in any sparse graph with a giant component there is always a positive fraction of alignable vertices; this is testable in simulations of scale-free networks.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper develops a model-agnostic framework for partial graph alignment in sparse inhomogeneous random graphs. It introduces a graph parameter, the self-overlap SOV(K), and combines it with the balanced load function w_K of Hajek. Theorem 1 states that for any correlated graph system, with ρ=SOV(U), there is an estimator recovering the planted matching on all vertices whose balanced load in the true intersection graph is at least ρ+ε, up to o(n) errors. Theorem 2 computes SOV for Erdős–Rényi graphs G(n,λ/n^α) as 1/(2α−1). Theorem 3 gives an infeasibility result: under a noise-robustness condition (min_e p_e ≥ (log n)^r/n whp), every estimator is wrong on at least x_sparse(n−o(n)) vertices. These results are used to derive sharp alignment thresholds for Chung–Lu graphs and stochastic block models, recovering known Erdős–Rényi phenomena and giving new thresholds in inhomogeneous settings.

Significance. The balanced-load/self-overlap comparison is an elegant and potentially useful organizing principle for graph alignment. The proof of Theorem 1 is short, clean, and genuinely model-agnostic, and it makes precise the intuition that alignability is governed by two separate ingredients: the local information in the intersection graph and the intrinsic self-similarity of the union graph. The paper also provides detailed proofs of the balanced-load properties and of the self-overlap computation for Erdős–Rényi graphs, and it gives explicit, falsifiable thresholds for Chung–Lu and stochastic block models. If the sharpness claims are established, this would be a significant conceptual contribution. However, two load-bearing points need attention: Theorem 3's hypotheses are not verified in the examples where it is invoked, and the parameter matching in the lower-bound proof of Theorem 2 contains an apparent inconsistency. Both appear locally repairable, but as written they leave the sharpness claims unsupported.

major comments (2)
  1. [§8, Eq. (22); Corollaries 5–6] Theorem 3 is stated under condition (22), min_e p_e ≥ (log n)^r/n whp. The intractability parts of Corollaries 5 and 6 invoke this theorem, but their hypotheses do not imply (22). In the Chung–Lu model of Corollary 5, if ν is supported on [ε,∞), then min_e p_e = Θ(1/n) with constant ε^2/E[D]; for r=0 condition (22) requires that constant to be at least 1, which is not guaranteed and can fail even while s^2<1/d*. In the stochastic block model of Corollary 6, min_e p_e = q_min/n, and q_min may be less than 1, again violating (22). Thus Theorem 3, as stated, does not apply to the very settings where it is used to prove sharpness. The proof of Lemma 6 appears to require only a fixed lower bound p_e ≥ c/n for some c>0, because the additive log c contributes O(n)=o(n log n) in the estimates (81)–(83). If so, the theorem is repairable by weakening (22), but the manuscript does not state or prov
  2. [§7.2, Eq. (43)] In the lower-bound proof of Theorem 2, the parameter choices in Eq. (43) do not yield the claimed comparison with Theorem 4 and Proposition 6. With β=2α−1, Theorem 4 requires λ1λ2^2=c(κ) so that I∼G(n,c(κ)/n), and λ1λ2=λ/2 so that U∼G(n,λ/n^α). Substituting λ1=λ2/(4c(κ)) and λ2=2c(κ)/λ gives λ1λ2^2=2c(κ)^2/λ^3 and λ1λ2=c(κ)/λ^2, not c(κ) and λ/2. The correct choice appears to be λ1=λ^2/(4c(κ)) and λ2=2c(κ)/λ. As written, the displayed contradiction involving SOV(U)<ρ_m(I)−2ε<κ<ρ_m(I)+2ε<1/β is not implied by the equations. Since this step is the core of the SOV(K)≥1/(2α−1) bound, it needs to be fixed before the theorem is fully supported.
minor comments (4)
  1. [§2, Proposition 1] The statement 'there exists K∼G(n,λ_n/n) such that K≲K' uses the same symbol K for two different graphs. This is confusing and should be restated with distinct names, e.g., K'∼G(n,λ_n/n) and K'≲K.
  2. [§3.2, Theorem 4 and surrounding text] In the statement of Theorem 4 and the discussion after Eq. (40), expressions like 'β−1' and 'β−1±ε' should presumably be 'β^{-1}' or '1/β'. Please fix the notation for readability.
  3. [§4, Corollary 5] The assertion that the intersection graph I is a Chung–Lu graph 'with law μ=s^2ν' is correct only if the weights are rescaled as d'_v=s^2 d_v, not s d_v. This rescaling is worth stating explicitly, since a naive degree rescaling by s gives edge probability sp_e rather than s^2p_e.
  4. [§6.2, Proposition 5] The reduction 'Without loss of generality, we may assume that K is a tree' is terse. A sentence explaining why the presence of cycles does not decrease the relevant balanced-load lower bound would help the reader.

Circularity Check

0 steps flagged

No significant circularity: Theorem 1 is a genuine reduction to the self-overlap definition, Theorem 3 is proved with included lemmas, and the ER self-overlap value is benchmarked against an external theorem rather than derived from the paper's own conclusion.

full rationale

I find no load-bearing circular step. Theorem 1 derives alignability from the definition of SOV: if the maximizer estimator made many errors, the misaligned set would give a self-overlap exceeding rho, contradicting the definition of SOV(U). This is a direct but valid reduction; SOV is defined on the union graph U, not on the alignable set, so the result is not self-definitional in the prohibited sense. Theorem 3's infeasibility proof is internally supported: Lemma 5 is stated as an adaptation of the authors' earlier Lemma 1, but a proof is supplied in Appendix D, and Lemmas 6-7 are proved in the paper; thus the self-citation is not the sole justification and does not make the argument circular. The ER computation of SOV in Section 7.2 uses Du's external Theorem 4 as a benchmark; since Du's theorem does not mention SOV, this is independent external evidence rather than a circular import. The paper's own flagged limitation on condition (22) ('It is unclear to the author whether or not this theorem still holds if we remove condition (22)') is a real hypothesis-support concern, and the critic's observation that the Chung-Lu/SBM corollaries may not verify (22) is a correctness gap, not a circularity. The Appendix F passage noting LLM assistance is not load-bearing. Overall, the derivation chain is not equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 10 axioms · 1 invented entities

The paper's central claim rests on the balanced-load formalism, the subsampling model for correlated graphs, external sharp-recovery theorems for ER, and an ad hoc noise-robustness assumption whose necessity is explicitly left open. No empirical parameters are fitted to data, but the proof of the ER value of SOV uses a known sharp threshold as a calibration input.

free parameters (1)
  • κ and c(κ) in the proof of Theorem 2 lower bound = κ ∈ (SOV(K), 1/(2α−1)); c(κ) from [3]
    Chosen by hand to run the contradiction with Du's theorem; the paper does not show that the resulting constants make the coupled graphs have the required parameters (U with constant λ and I with balanced-load maximum κ).
axioms (10)
  • standard math Balanced allocations on any graph exist and yield a unique load function w_K (Hajek 1990).
    Definition 4 and Section 5 rest on this; existence/uniqueness is cited to [14] and not re-proved.
  • domain assumption The correlated system is produced by independently subsampling a mother inhomogeneous graph with probability s; conditional on edge probabilities, edges are independent Bernoulli.
    Definition 3; this is the generative model for all corollaries.
  • domain assumption Weak inhomogeneity: the sequence (n p_e) is uniformly integrable over uniformly random edges.
    Definition 2; used in Proposition 1 and Corollary 1 to get SOV ≤ 1.
  • standard math Monotonicity and stability of w_K under sub/supergraph changes (Prop. 4).
    Proved in Appendix A; heavily used in Theorem 1 and Lemma 1.
  • domain assumption Du's sharp ER recovery theorem (Thm 4): estimators recover V^{≥β^{-1}+ε} and fail on V^{≤β^{-1}−ε} in correlated ER with parameters λ1, λ2, β.
    Used in Section 7.2 to prove the lower bound SOV ≥ 1/(2α−1); not re-derived.
  • domain assumption For every κ > 1 there is c(κ) > 1 such that the maximal balanced load of G(n, c(κ)/n) converges in probability to κ (Prop. 6, Anantharam–Salez [3]).
    Used in the contradiction proof of Theorem 2 lower bound.
  • ad hoc to paper Noise-robustness condition min_e p_e ≥ (log n)^r / n with high probability for Theorem 3.
    Eq. (22); the author explicitly says it is unclear whether Theorem 3 holds without it. It ensures absent edges carry no usable information.
  • domain assumption Bayesian indistinguishability lemma (Lemma 5), adapted from Vassaux–Massoulié [20].
    Proved in Appendix D, but the framework is taken from the author's own prior work; used to convert posterior ratios into estimator lower bounds.
  • domain assumption Giant-component and 2-core facts for Chung–Lu and stochastic block models (Thm 5 from van der Hofstad [19]).
    Used in Corollaries 5 and 6; not re-derived.
  • domain assumption For CL infeasibility, the degree law ν is supported on [ε, ∞) for some fixed ε > 0.
    Corollary 5 second bullet; excludes degree distributions with arbitrarily small degrees, where the statement is not proven.
invented entities (1)
  • self-overlap SOV(K) no independent evidence
    purpose: Benchmark ρ in the alignment criterion: vertices with balanced load above SOV(U) are alignable, below are not (Theorem 1).
    A new graph parameter defined in Def. 5. Unlike a physical entity it has no direct external observable; its value is computed via Theorems 2–3, one side of which (the ER lower bound) relies on Du's known threshold rather than an independent measurement.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph alignment in sparse inhomogeneous models via self-overlap." pith.science (2026). https://pith.science/paper/A4AZ7LRB

@misc{pith2026260714948,
  author       = {Pith},
  title        = {Pith review of: Graph alignment in sparse inhomogeneous models via self-overlap},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A4AZ7LRB}},
  note         = {Machine review of arXiv:2607.14948}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We develop a general framework for understanding when graph alignment is information-theoretically feasible in sparse inhomogeneous random graph models, by studying the set of vertices on which the underlying matching can be recovered. Our main theorem gives a general lower bound on this set by leveraging the balanced load function introduced by Hajek (1990). The corresponding obstruction is captured by a new graph parameter, the self-overlap, which measures the extent to which a graph can imitate itself under a non-trivial relabelling. We then show that this criterion is sharp in a broad class of sparse inhomogeneous models, recovering known Erd\H{o}s--R\'enyi phenomena and yielding sharp thresholds for Chung--Lu graphs and stochastic block models.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 9 canonical work pages

  1. [1]

    and HAJEK, B

    AMEEN, T. and HAJEK, B. (2025).Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery. arXiv:2405.12293

    Pith/arXiv arXiv 2025

  2. [2]

    and HAJEK, B

    AMEEN, T. and HAJEK, B. (2026).Sharp detection threshold for correlation among multiple unlabeled Gaussian networks. arXiv:2504.16279

    Pith/arXiv arXiv 2026

  3. [3]

    and SALEZ, J

    ANANTHARAM, V. and SALEZ, J. (2016).The densest subgraph problem in sparse random graphs. The Annals of Applied Probability26(1), 305–327. doi:10.1214/14-AAP1091

    work page doi:10.1214/14-aap1091 2016

  4. [4]

    S., BRESLER, G., HOPKINS, S., LI, J

    BRENNAN, M. S., BRESLER, G., HOPKINS, S., LI, J. and SCHRAMM, T. (2021).Statistical query al- gorithms and low degree tests are almost equivalent. Proceedings of the Thirty Fourth Conference on Learning Theory, Proceedings of Machine Learning Research134, 774. GRAPH ALIGNMENT IN SPARSE INHOMOGENEOUS MODELS VIA SELF-OVERLAP31

    2021

  5. [5]

    and DU, H

    DING, J. and DU, H. (2023).Matching recovery threshold for correlated random graphs. The Annals of Statistics51(4), 1718–1743. doi:10.1214/23-AOS2305

    work page doi:10.1214/23-aos2305 2023

  6. [6]

    and DU, H

    DING, J. and DU, H. (2023).Detection threshold for correlated Erd˝ os–R’enyi graphs via densest subgraph. IEEE Transactions on Information Theory69(8), 5289–5298. doi:10.1109/TIT.2023.3265009

    arXiv 2023

  7. [7]

    and LI, Z

    DING, J., DU, H. and LI, Z. (2025).Low-degree hardness of detection for correlated Erd˝ os–R’enyi graphs. The Annals of Statistics53(5), 1833–1856. doi:10.1214/25-AOS2517

    work page doi:10.1214/25-aos2517 2025

  8. [8]

    (2025).Optimal recovery of correlated Erd˝ os-R’enyi graphs

    DU, H. (2025).Optimal recovery of correlated Erd˝ os-R’enyi graphs. arXiv:2502.12077

    Pith/arXiv arXiv 2025

  9. [9]

    and GANASSALI, L

    EVEN, B. and GANASSALI, L. (2025).Statistical-computational gap in multiple Gaussian graph alignment. arXiv:2512.00610

    arXiv 2025

  10. [10]

    and MASSOULIÉ, L

    EVEN, M., GANASSALI, L., MAIER, J. and MASSOULIÉ, L. (2024).Aligning embeddings and geometric random graphs: Informational results and computational approaches for the Procrustes–Wasserstein problem. Advances in Neural Information Processing Systems37. doi:10.52202/079017-2260

    work page doi:10.52202/079017-2260 2024

  11. [11]

    and XU, J

    FAN, Z., MAO, C., WU, Y. and XU, J. (2023).Spectral graph matching and regularized quadratic relax- ations I: Algorithm and Gaussian analysis. Foundations of Computational Mathematics23, 1511–1565. doi:10.1007/s10208-022-09570-y

    work page doi:10.1007/s10208-022-09570-y 2023

  12. [12]

    (2022).Sharp threshold for alignment of graph databases with Gaussian weights

    GANASSALI, L. (2022).Sharp threshold for alignment of graph databases with Gaussian weights. Pro- ceedings of the 2nd Mathematical and Scientific Machine Learning Conference, Proceedings of Machine Learning Research145, 314–335

    2022

  13. [13]

    and MASSOULIÉ, L

    GANASSALI, L. and MASSOULIÉ, L. (2020).From tree matching to sparse graph alignment. Proceedings of the Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research125, 1633–1665

    2020

  14. [14]

    (1990).Performance of global load balancing by local adjustment

    HAJEK, B. (1990).Performance of global load balancing by local adjustment. IEEE Transactions on Infor- mation Theory36(6), 1398–1414. doi:10.1109/18.59935

    work page doi:10.1109/18.59935 1990

  15. [15]

    and MASSOULIÉ, L

    MAIER, J. and MASSOULIÉ, L. (2026).Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing. Mathematical Statistics and Learning, published online first. doi:10.4171/MSL/58

    work page doi:10.4171/msl/58 2026

  16. [16]

    M., VASSAUX, L

    MASSOULIÉ, L., VARMA, S. M., VASSAUX, L. and WALDSPURGER, I. (2026).Phase transition in convex relaxations for graph alignment. arXiv:2606.15581

    arXiv 2026

  17. [17]

    RÁCZ, M. Z. and SRIDHAR, A. (2021).Correlated stochastic block models: Exact graph matching with applications to recovering communities. Advances in Neural Information Processing Systems34, 22259– 22273

    2021

  18. [18]

    RÁCZ, M. Z. and SRIDHAR, A. (2023).Matching correlated inhomogeneous random graphs using the k-core estimator. 2023 IEEE International Symposium on Information Theory (ISIT), 2499–2504. doi:10.1109/ISIT54713.2023.10206932. [19]VAN DERHOFSTAD, R. (2024).Random Graphs and Complex Networks. Cambridge Series in Statistical and Probabilistic Mathematics. Cambr...

    arXiv 2023

  19. [20]

    and MASSOULIÉ, L

    VASSAUX, L. and MASSOULIÉ, L. (2026).The feasibility of multi-graph alignment: a Bayesian approach. arXiv:2502.17142

    Pith/arXiv arXiv 2026

  20. [21]

    and YOLOU, I

    WANG, H., WU, Y., XU, J. and YOLOU, I. (2022).Random graph matching in geometric models: The case of complete graphs. Proceedings of the Thirty Fifth Conference on Learning Theory, Proceedings of Machine Learning Research178, 3441–3488

    2022

  21. [22]

    and YU, S

    WU, Y., XU, J. and YU, S. H. (2022).Settling the sharp reconstruction thresholds of random graph match- ing. IEEE Transactions on Information Theory68(8), 5391–5417. doi:10.1109/TIT.2022.3169005

    arXiv 2022

  22. [23]

    and YU, S

    WU, Y., XU, J. and YU, S. H. (2023).Testing correlation of unlabeled random graphs. The Annals of Applied Probability33(4), 2519–2558. doi:10.1214/22-AAP1786

    work page doi:10.1214/22-aap1786 2023

  23. [24]

    YARANDI, M. H. A. and GANASSALI, L. (2026).Contextual graph matching with correlated Gaussian features. arXiv:2603.23305

    arXiv 2026

  24. [25]

    and LIN, X

    YU, L., XU, J. and LIN, X. (2021).The power ofD-hops in matching power-law graphs. Proceed- ings of the ACM on Measurement and Analysis of Computing Systems5(2), Article 27, 43 pp. doi:10.1145/3460094

    work page doi:10.1145/3460094 2021

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.