{"id":"70f98f80-3ef1-4c6c-a684-b13b9f22b279","arxiv_id":"2607.14948","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"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.","lead":"An INRIA researcher proposes that graph alignment in sparse random graphs is governed by comparing each vertex's \"balanced load\" in the intersection graph with a new \"self-overlap\" parameter of the union graph. The framework recovers known Erdős–Rényi thresholds and claims sharp partial-alignment thresholds for Chung–Lu and stochastic block-model graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's condition (22) is not satisfied by the Chung–Lu/SBM corollaries it is used to prove, so the sharpness statements are unsupported as written.","rationale":"The positive framework in Theorem 1 is convincing: the proof by contradiction against SOV(U) is short and does not rely on hidden model assumptions. The genuinely load-bearing step is the infeasibility side, Theorem 3, because without it the balanced-load/self-overlap criterion is only a sufficient condition, not a sharp threshold. The reader's verdict identifies condition (22) as the weakest assumption, and I agree. My reading sharpens the concern: it is not just that removing (22) is mathematically open; the theorem is applied to Chung–Lu and SBM corollaries where (22) is actually false. For Chung–Lu with ν supported on [ε,∞), the minimum edge probability is Θ(1/n) with a constant ε²/E[D] that is not guaranteed to be at least 1; for SBM with constant q_ij, it is q_min/n with q_min not assumed ≥ 1. Thus even the r=0 form of (22) fails. The proof of Lemma 6 suggests the theorem could be repaired by replacing (22) with the weaker min_e p_e ≥ c/n, since the additive O(n) contribution from log c is absorbed into the o(n log n) error. This is a concrete, fixable gap rather than a fatal flaw, so the appropriate verdict remains the reader's CONDITIONAL: the framework is valuable, but the sharpness claims, as written, are not fully supported. I also noted a likely typo in the constant definitions in Section 7.2 (λ1 appears to need λ²/(4c(κ)) rather than λ2/(4c(κ))), but this appears typographical and does not change the primary objection.","tokens_in":24565,"tokens_out":17514,"duration_ms":170327,"concrete_test":"Instantiate Corollary 5 with ν = Uniform([0.5,1]) and s = 1: then E[D] = 0.75, d* = E[D²]/E[D] ≈ 0.778 < 1, and min_e p_e ≈ (0.5²)/(0.75n) = 1/(3n), violating (22) for every r ≥ 0. Then check whether the proof of Lemma 6 still yields the e^{o(n log n)} likelihood-ratio bound when p_e = c/n with c = 1/3. If it does, condition (22) should be weakened to min_e p_e ≥ c/n and the corollary proof rechecked; if it does not, the claimed intractability for this example is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Theorem 3, which supplies the matching lower bound that makes the criterion 'sharp'. As stated, its condition (22) requires min_e p_e ≥ (log n)^r/n whp. The paper's flagship applications fail this condition: in a Chung–Lu graph with degree law supported on [ε,∞), min_e p_e ≈ ε²/(E[D]n), i.e. c/n with c = ε²/E[D], which can be < 1; in an SBM with constant q_ij, min_e p_e = q_min/n, and q_min may also be < 1. Even taking r=0, condition (22) demands c ≥ 1. Thus Theorem 3, as stated, does not apply to Corollaries 5 and 6 in these regimes. The author explicitly notes uncertainty about removing (22), but the more immediate problem is that the theorem's hypotheses are not verified in the very models where it is invoked. The proof of Lemma 6 appears to only need a fixed lower bound p_e ≥ c/n — the additive log c term is O(n), which is o(n log n) — so the theorem is likely repairable, but the manuscript as written does not provide that argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24863,"tokens_out":21271,"duration_ms":190743,"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":[{"comment":"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","section":"§8, Eq. (22); Corollaries 5–6"},{"comment":"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.","section":"§7.2, Eq. (43)"}],"minor_comments":[{"comment":"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.","section":"§2, Proposition 1"},{"comment":"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.","section":"§3.2, Theorem 4 and surrounding text"},{"comment":"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.","section":"§4, Corollary 5"},{"comment":"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.","section":"§6.2, Proposition 5"}],"recommendation":"major_revision","confidential_remarks":"The sharpness of the framework in the Erdős–Rényi case is established by invoking Du's sharp recovery theorem (Theorem 4) as a black box; thus the ER computation of SOV is a calibration against a known result rather than an independent derivation. This is acceptable for a framework paper, but it is worth the editor's awareness when evaluating novelty. The two major issues above are local and appear fixable; if the author corrects the Eq. (43) constants and weakens condition (22) to the c/n condition that the proof actually uses, the central claims would be substantially supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is worth your time. Self-overlap as a graph parameter is new, and Theorem 1 is a model-agnostic lower bound that is short, clean, and convincing: if a vertex's balanced load in the intersection graph exceeds the self-overlap of the union graph, it can be aligned up to o(n) errors. That is a real contribution, and the connections to k-core estimators and the alignable-set perspective are well explained. The sharp thresholds claimed for Chung–Lu and SBM (Corollaries 5 and 6) are plausible and not in the existing literature.\n\nThe soft spots are on the sharpness side, and they are not minor. Theorem 3, which supplies the matching lower bound that makes the criterion \"sharp,\" assumes min_e p_e ≥ (log n)^r/n whp. The paper then uses Theorem 3 to prove intractability in Chung–Lu and SBM models where the edge probabilities are c/n with c possibly below 1—condition (22) is simply not satisfied there. The author explicitly notes uncertainty about removing (22), but the more immediate problem is that the theorem's hypotheses are not verified in the flagship applications. That said, the proof of Lemma 6 only seems to need a fixed lower bound p_e ≥ c/n, so the gap is likely repairable; the manuscript as written just doesn't provide the argument.\n\nSecond, the lower bound on SOV for Erdős–Rényi graphs (Theorem 2) relies directly on Du's sharp recovery theorem (Theorem 4) and on Proposition 6, and the constant choices in Eq. (43) are not checked—there is an undefined λ, and the products don't obviously line up with what Proposition 6 requires. This weakens the claim that the paper \"recovers\" the ER phenomenon independently. It is benchmarking against a known result rather than deriving it. The reader's circularity concern is fair, though I'd stop short of calling it a flaw in Theorem 1, which stands on its own.\n\nOn the positive side, the paper is honest about its own limitations: it flags the (22) issue, acknowledges the weight-1 ambiguity, and includes a substantial appendix with a constructed example showing the alignable set is not simply the level set. The balanced-load exposition is solid, and Proposition 7 is a nice addition.\n\nWho is this for? Researchers in graph matching and sparse random graphs. It deserves a serious referee: the framework is interesting enough to warrant revision, and the flaws are fixable. I'd send it out, with the expectation that the author either proves Theorem 3 under weaker hypotheses or restricts the corollaries to regimes where (22) holds, and cleans up the constant bookkeeping in Section 7.2.","headline":"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.","tokens_in":25352,"tokens_out":2624,"would_cite":true,"duration_ms":25379,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62B10","05C80","05C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["graph alignment","inhomogeneous random graphs","balanced load","self-overlap","correlated random graphs","partial recovery","stochastic block model","Chung–Lu model"],"falsifier":"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.","tokens_in":24399,"feed_emoji":"🔗","tokens_out":8544,"duration_ms":72357,"temperature":0.7,"pith_summary":"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.","feed_headline":"Self-overlap sets the sharp line for sparse graph alignment","feed_subtitle":"A single comparison tells which vertices of two correlated networks can be matched.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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 ρ+ε."],"fun_headline_variants":["Self-overlap defines the edge of graph alignment","Sparse graph matching hinges on self-overlap","Self-overlap sets limits on vertex recovery in networks","Graph alignment thresholds from self-overlap"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Self-overlap defines the edge of graph alignment","Sparse graph matching hinges on self-overlap","Self-overlap sets limits on vertex recovery in networks","Graph alignment thresholds from self-overlap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000156,"raw_usage":{"total_tokens":1003,"prompt_tokens":644,"completion_tokens":359,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":388,"completion_tokens_details":{"reasoning_tokens":301}},"tokens_in":388,"tokens_out":359,"duration_ms":3881,"temperature":1.0,"reasoning_tokens":301,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T00:37:11.788953+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}