{"id":"a7dbfb89-9dfa-4c9d-b6b5-079a579d9f1c","arxiv_id":"2412.03008","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"GeneralACL and HyperACL find local clusters with conductance O(sqrt(optimal)) on weighted directed self-looped graphs and EDVW hypergraphs with probability at least 1/2 under two conditions.","lead":"This paper extends the classic ACL local clustering algorithm to weighted, directed, self-looped graphs and to hypergraphs with edge-dependent vertex weights, proving a quadratically optimal conductance guarantee under two conditions. The main value is a new provable guarantee for hypergraph local clustering, with experiments on citation hypergraphs.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8's condition (2), which requires the unknown optimal cluster S* to also be optimal for S*\\S, is a strong and unverifiable symmetry assumption; the claimed 1/2 success probability depends on it and can fail without it.","rationale":"The paper's central claim is that GeneralACL/HyperACL achieve quadratically optimal conductance with probability at least 1/2 under two conditions. The proof hinges on Theorem 22's symmetry lemma to transfer a 1/2 probability from uniform subsets of a fixed cluster to uniformly random seed sets. Condition (2) is the bridge that makes this transfer valid; without it, the pairing argument fails and no probability bound is available. This is more load-bearing than the presentation gaps around Lemma 10, because Lemma 10's inequality is true (it is a standard weighted-average bound) and can be repaired, whereas condition (2) imposes a real restriction on the input. The reader's weakest_assumption already identified condition (2); our analysis agrees and proposes an exhaustive experiment to verify that the guarantee indeed degrades when condition (2) fails. The conditional verdict remains appropriate: the hypergraph construction is novel and the proof is plausible, but the theorem should be restated with a prominent caveat about condition (2), or the condition should be relaxed. Therefore, no change to the reader's conditional verdict is needed.","tokens_in":32682,"tokens_out":18378,"duration_ms":163097,"concrete_test":"Construct a small graph designed to violate condition (2) for many seeds, e.g., two densely connected sets A and B joined by a single edge, with S*=A∪B the optimal cluster for most seeds that intersect both A and B. Enumerate all 2^|V| seeds S; for each, compute S*(S) by exhaustive search, check condition (2), run HyperACL with α=Φ(S*) and exact PageRank, and record whether the returned sweep cut satisfies Φ(S') ≤ sqrt(235·Φ(S*)). Compare the success rate over all S, over S satisfying condition (2), and over the complement. If the complement's success rate is below 1/2 while the conditional rate is at least 1/2, this confirms that condition (2) is the load-bearing assumption behind the probability guarantee and that the theorem does not apply when it fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 8's guarantee is conditional on condition (2): the unknown optimal cluster S* is also the optimal conductance set among all vertex sets containing S*\\S. This condition is data-dependent and unverifiable (finding S* is NP-hard), so it is not 'mild' as the abstract claims. It is exactly what lets the proof apply Theorem 22's symmetry argument to a seed set S that is uniform over all 2^V subsets rather than over subsets of S*. Theorem 22 holds for a fixed C and D uniform over subsets of C. But in Theorem 8, D=S is uniform over all of V, and C=S* is a random function of S. Without condition (2), the distribution of S over subsets of S* can be arbitrarily biased, and the pairing argument (the involution S ↔ S*\\S) breaks down. The proof asserts that 'the probabilities of sampling S or S*\\S are the same,' which only holds pointwise for fixed sets, not for the random pair (S, S*\\S) when S* depends on S. Condition (2) ensures that S and S*\\S have the same optimal cluster, restoring the involution on the set of seeds satisfying the condition. If condition (2) fails for a large fraction of seeds, the success probability can drop below 1/2, so the theorem's scope is much narrower than 'two mild conditions' suggests.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the Andersen–Chung–Lang (ACL) PageRank-based local clustering framework to weighted, directed, self-looped graphs and to hypergraphs with edge-dependent vertex weights. It proposes GeneralACL and HyperACL, defines conductance through the Markov chain induced by a random walk, and proves Theorem 8: if the seed set S is uniformly random and two conditions hold (vol(S*) ≤ 1/2 and S* also minimizes conductance among sets containing S* \\ S), then with probability at least 1/2 the best sweep cut of a lazy personalized PageRank vector with restart α = Φ(S*) has conductance O(√Φ(S*)); the special case vol(S*) ≤ 1/3 gives the constant √235. The paper also reports algorithm complexity and experiments on four citation hypergraphs.","tokens_in":32993,"tokens_out":20464,"duration_ms":193993,"significance":"The unification is attractive and the paper ships code and a concrete constant for one regime, which are strengths. If the proof can be made rigorous, the results would give the first quadratic-optimality guarantee for EDVW hypergraph local clustering and would subsume known directed-graph ACL results. However, the current manuscript has several load-bearing gaps: Lemma 10's exchange argument is not readable, the α = Φ(S*) setting is not implemented by the algorithms, and the O(√Φ*) claim for vol(S*) ≤ 1/2 is not supported by the displayed inequalities. These issues affect the central theorem, so the contribution is not yet established.","major_comments":[{"comment":"The algorithms as written do not execute the hypotheses of Theorem 8. The theorem fixes α = Φ(S*) and requires S to be drawn uniformly from all subsets of V, but Algorithm 1 and Algorithm 2 have no α parameter, no random seeding, and 'Compute the PageRank vector as in Theorem 8' is not an implementable instruction because Φ(S*) is unknown. The experiments in §6.2 first use α = Φ(S) and then α = Φ(S'), which is not the theorem's α. Thus the stated guarantee does not apply to the submitted algorithms or to the experimental protocol.","section":"§3.2 (Algorithms 1 and 2), Theorem 8"},{"comment":"Lemma 10 is load-bearing for Lemma 16 and hence for Lemmas 19 and Theorem 21, but its proof is not a valid proof as printed. The definitions of f and g are inconsistent (g(u) is a vertex function but is conditioned on (u,v) ∈ B_j), and the sums in equations (25)–(34) do not correspond to p(A) = Σ_{(u,v)∈A} p(u)P_{u,v} and |A| = Σ_{(u,v)∈A} φ(u)P_{u,v}. The iteration that removes edges is never precisely defined, and the final equality (34) is asserted rather than derived. This step must be rewritten before the main theorem can be evaluated.","section":"§4.1, Lemma 10"},{"comment":"The claimed O(√Φ(S*)) in the case vol(S*) ≤ 1/2 does not follow from the preceding bound. With δ = 1/2 − vol(S*), the bound in equation (104) is √(9Φ(S*) ln(1/z)/(δ − z)); for z ∈ (0, δ) the factor √(ln(1/z)/(δ − z)) is unbounded as δ → 0+, so no universal constant exists for the O. The explicit √(235Φ(S*)) bound is derived only under the additional assumption vol(S*) ≤ 1/3, where δ − 1/18 ≥ 1/9. Please either restrict condition (1) to a constant volume margin or supply a different argument for the stated O.","section":"§4.5, proof of Theorem 8"},{"comment":"The transition 'with probability at least 1/2' is too quick. The proof invokes Theorem 22, which is stated for a fixed C and D uniform over subsets of C, and then replaces D by a uniformly random S ⊆ V; the equality of marginal probabilities of S and S* \\ S only yields the pairing argument if S* is unique and the involution S ↔ S* \\ S is well defined on the event of interest. The manuscript neither states a uniqueness assumption nor handles ties among optimal-conductance sets. Condition (2) is also a strong, data-dependent, and unverifiable assumption on the unknown optimum; as a concrete correctness-risk test, consider a graph with two disjoint optimal clusters, where the condition can fail for a large fraction of seeds and no 1/2 bound follows. Please either formalize the probability argument with explicit tie-breaking and a measure-preserving involution, or weaken the claim; and describe a setting where condition (2) is known to hold.","section":"§4.5, proof of Theorem 8, condition (2)"}],"minor_comments":[{"comment":"The paper claims strong locality, but the complexity analysis in §5 is global (O(m² + |V|² + k²|V|)) and the early-stop mechanism mentioned in §3.2 is absent from Algorithms 1 and 2; please state the early-stop rule formally and analyze its effect, or soften the locality claim.","section":"§5 and §3.2"},{"comment":"The strict inequality α(8/σ² ln(1/z) + 1) < α(9/σ² ln(1/z)) can fail when σ = 1 and z = 1/e; use ≤ throughout to keep Theorem 18 valid.","section":"§4.5, Eq. (76)"},{"comment":"The experimental seeds are five authors sampled from one of a few organizations, not uniformly random subsets of V, and the α schedule is heuristic; these choices should be acknowledged as not matching Theorem 8's hypotheses.","section":"§6.1"},{"comment":"Table 2 and Figure 1 report averages without error bars or significance tests; 'significantly the lowest' is not supported by the displayed data. Also, Figure 2(d) is captioned DBLP-CV but the text refers to DBLP-IR.","section":"§6.2"},{"comment":"Theorems 1 and 2 in the introduction restate Theorem 8 with different numbering; please unify the numbering and ensure the duplicate statements match the formal statement exactly.","section":"§1.1 and §3"},{"comment":"In Theorem 8, α = Φ(S*) can be 0, but the proof divides by α in applying Theorem 21; please state α > 0 or handle the zero-conductance case separately.","section":"§4.5, Theorem 8"}],"recommendation":"major_revision","confidential_remarks":"The manuscript proposes a plausible and potentially useful extension of ACL, and it contains reproducible code. However, the central proof is not yet in a publishable state: Lemma 10 needs a clear rewrite, the relationship between the theorem's α and the algorithms/experiments must be fixed, and the O(√Φ*) claim for vol(S*) ≤ 1/2 needs either a corrected argument or a restriction to a constant volume margin. I recommend major revision rather than rejection, provided the authors can repair these points. The self-citations to [22] and [84] are directly relevant to the technique and are not a concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nThe thing to know: this paper gives the first quadratic-optimal local clustering guarantee for hypergraphs with edge-dependent vertex weights, via a random-walk definition of hypergraph conductance. That is a genuine gap and the main contribution. The general graph half is mostly the directed-graph ACL result from [37] with node weights folded in; it is a generalization, not a new framework.\n\nWhat is good: the Markov-chain unification is clean, and once you accept the Lovász–Simonovits setup the proof structure is the classic one. The hypergraph conductance definition is natural, and the authors provide code and experiments on real citation hypergraphs. The special-case constant sqrt(235) is derived, not fitted.\n\nThe soft spots, in order of size. First, condition (2) of Theorem 8 is not mild. It requires the unknown optimal cluster S* to also be optimal among all sets containing S*\\S. That is data-dependent, unverifiable (finding S* is NP-hard), and load-bearing: the proof's 1/2 probability rests on pairing S with S*\\S, which only works if both seeds have the same optimal cluster. The stress-test note is right. The theorem's scope is much narrower than 'two mild conditions' suggests. Second, the theorem sets α = Φ(S*), but the algorithms never say how α is set; in the experiments they run HyperACL once to get a cluster and then reuse that α for baselines, which is not the theorem and biases the comparison. Third, the proof of Lemma 10 is illegible as written and needs to be rewritten. Fourth, 'strongly local' is oversold: the algorithm computes the stationary distribution and a full PageRank vector, with worst-case O(|V|^2) and O(m^2) complexity; the early-stop is heuristic. None of these kill the core hypergraph claim, but they need to be fixed or stated honestly.\n\nBottom line: this deserves a serious referee and likely a major revision. The hypergraph result, if the proof is repaired, fills a real gap; the conditions must be stated as strong assumptions, not mild ones.","headline":"The first quadratic-optimal guarantee for EDVW hypergraph local clustering is genuinely new; the graph portion is known ACL, and the headline 'mild conditions' in Theorem 8 are stronger and less implementable than advertised.","tokens_in":33477,"tokens_out":2676,"would_cite":true,"duration_ms":27288,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C81","05C65","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The ACL local-clustering guarantee now covers weighted, directed, and hypergraph settings.","keywords":["Local clustering","General graphs","Hypergraphs","Andersen-Chung-Lang algorithm","PageRank and random walks","Quadratic optimality","Edge-dependent vertex weights","Lovasz-Simonovits curve"],"falsifier":"One could computationally search small weighted directed graphs or EDVW hypergraphs for a case where $S^*$ is the optimal cluster containing $S$ but fails to be optimal among sets containing $S^*\\setminus S$, then run GeneralACL or HyperACL from $S$ and check whether the returned conductance is actually larger than $O(\\sqrt{\\Phi(S^*)})$. The theorem predicts the guarantee should break exactly there, so finding an instance where the algorithm's output violates the bound would settle whether condition (2) is truly needed.","tokens_in":32467,"feed_emoji":"🕸️","tokens_out":8163,"duration_ms":119504,"temperature":0.7,"pith_summary":"The paper extends the classic Andersen-Chung-Lang (ACL) local-clustering guarantee to settings far beyond the discrete undirected graphs it was designed for: weighted, directed, and self-looped graphs, and hypergraphs with edge-dependent vertex weights. It proposes GeneralACL and HyperACL, two algorithms that run a seeded lazy personalized PageRank vector and sweep its cuts, and proves that under two conditions on the optimal cluster containing the seed set, the smallest sweep-cut conductance satisfies $\\Phi(S') < O(\\sqrt{\\Phi(S^*)})$ with probability at least $1/2$. The proof works by viewing both graphs and hypergraphs as Markov chains, so a single argument covers both settings and gives hypergraph local clustering its first quadratic-optimality result. If the theorem is right, local clustering can be applied directly to real-world weighted and directed networks and to group-interaction data without discarding the information in edge weights, directions, self-loops, or edge-dependent vertex weights.","feed_headline":"Quadratic optimality comes to weighted graphs and hypergraphs","feed_subtitle":"GeneralACL and HyperACL return clusters within a square root of optimal conductance, with probability at least 1/2.","key_machinery":"The load-bearing object is the Lovasz-Simonovits curve, a concave piecewise-linear function $p[k]$ built from the sweep sets of a distribution $p$, defined on $[0,1]$ with the stationary distribution as volume. Lemma 16 expresses the lazy PageRank mass of a set through curve values at $\\mathrm{vol}(S) \\pm |\\partial S|$; Theorem 17 converts that into an upper bound on the disagreement $p[k] - k$ controlled by the smallest sweep-cut conductance, and Theorem 18 turns a lower bound on the disagreement into a conductance bound. The $1/2$ probability comes from a linearity identity: $\\mathrm{pr}(\\alpha,\\psi_C)$ is a volume-weighted average of $\\mathrm{pr}(\\alpha,\\psi_D)$ and $\\mathrm{pr}(\\alpha,\\psi_{C\\setminus D})$, so at least one of $D$ or $C\\setminus D$ leaks no more mass out of $C$ than $C$ itself does. This is the step that lets a uniformly random seed subset $S$ serve as the seed set.","core_discovery":"The central claim is Theorem 8. For a seed set $S$ sampled uniformly at random, let $S^*$ be the vertex set of optimal conductance among all sets containing $S$. If (1) $\\mathrm{vol}(S^*) \\le 1/2$ and (2) $S^*$ is also optimal among all vertex sets that contain $S^* \\setminus S$, then with probability at least $1/2$ the sweep of the lazy personalized PageRank vector $\\mathrm{pr}(\\alpha, \\psi_S)$ with $\\alpha = \\Phi(S^*)$ returns a cluster $S'$ with $\\Phi(S') < O(\\sqrt{\\Phi(S^*)})$; in the special case $\\mathrm{vol}(S^*) \\le 1/3$ the constant is $\\sqrt{235}$. The theorem is stated in a unified form for arbitrary row-stochastic transition matrices, so it applies to weighted directed graphs with self-loops (GeneralACL) and to EDVW hypergraphs (HyperACL), using the paper's random-walk definition of hypergraph conductance.","pith_inferences":["Since condition (2) is data-dependent and unverifiable, a practical next step is to test how often it holds on real networks; one way is to compare, for each returned cluster, the optimal conductance of the set containing the seed set with the optimal conductance after deleting one seed vertex, and to correlate failures with the paper's probability-1/2 bound.","The symmetry argument suggests a cheap robustness improvement: run the algorithm with several independent random seed subsets and keep the best cut; the failure probability should drop exponentially, because all subsets would need to land on the same side of the volume-weighted average.","The random-walk definition of hypergraph conductance opens the door to a Cheeger-style global partitioning guarantee for EDVW hypergraphs, extending the local result to a global spectral bound."],"forward_implications":["GeneralACL becomes the first local-clustering algorithm with quadratic optimality for weighted, directed, and self-looped graphs, so such graphs can be clustered without discarding weights or directions.","HyperACL becomes the first hypergraph local-clustering algorithm with a quadratic optimality guarantee, for hypergraphs with edge-dependent vertex weights under the new random-walk conductance.","The early-stop mechanism makes both algorithms strongly local: the runtime is controlled by the size of the returned cluster rather than the full vertex set.","Because the theorem is proved for any row-stochastic transition matrix with a stationary distribution, any later local-clustering result proved in that Markov-chain language transfers to all these graph and hypergraph formats at once.","In the special case $\\mathrm{vol}(S^*) \\le 1/3$, the returned cluster satisfies the concrete bound $\\Phi(S') < \\sqrt{235\\,\\Phi(S^*)}$."],"supporting_citations":[{"why":"Supplies the original ACL algorithm and the quadratic-optimality proof on undirected unweighted graphs that this paper generalizes.","marker":"[1]"},{"why":"Extends ACL to directed graphs and gives the PageRank/conductance formulation that the paper adapts to weighted and self-looped graphs.","marker":"[37]"},{"why":"Defines random walks on hypergraphs with edge-dependent vertex weights, providing HyperACL's transition matrix and stationary distribution.","marker":"[59]"},{"why":"Gives the spectral treatment of hypergraphs as weighted directed self-looped graphs and the connectivity and stationary-distribution facts used in the proofs.","marker":"[22]"},{"why":"Provides the infinite-series characterization of lazy personalized PageRank used in the linear decomposition identity.","marker":"[84]"}],"fun_headline_variants":["GeneralACL and HyperACL: seed-based clustering with quadratic guarantee","Complex graphs and hypergraphs get ACL's quadratic optimality","With 50% probability, return a cluster within sqrt of optimal conductance","Seed to near-optimal cluster: new ACL variants for complex graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The second condition of Theorem 8 — that the optimal cluster $S^*$ containing the seed set must remain optimal when the seed vertices are removed from consideration — is the load-bearing premise; the proof applies the symmetry argument only through this assumption, and the paper gives no way to check it from the input.","fun_headline_variants_meta":{"raw":{"variants":["GeneralACL and HyperACL: seed-based clustering with quadratic guarantee","Complex graphs and hypergraphs get ACL's quadratic optimality","With 50% probability, return a cluster within sqrt of optimal conductance","Seed to near-optimal cluster: new ACL variants for complex graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001184,"raw_usage":{"total_tokens":4886,"prompt_tokens":935,"completion_tokens":3951,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":3876}},"tokens_in":551,"tokens_out":3951,"duration_ms":28949,"temperature":1.0,"reasoning_tokens":3876,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:52:26.101794+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One could computationally search small weighted directed graphs or EDVW hypergraphs for a case where $S^*$ is the optimal cluster containing $S$ but fails to be optimal among sets containing $S^*\\setminus S$, then run GeneralACL or HyperACL from $S$ and check whether the returned conductance is actually larger than $O(\\sqrt{\\Phi(S^*)})$. The theorem predicts the guarantee should break exactly there, so finding an instance where the algorithm's output violates the bound would settle whether condition (2) is truly needed.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends ACL to directed graphs and gives the PageRank/conductance formulation that the paper adapts to weighted and self-looped graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines random walks on hypergraphs with edge-dependent vertex weights, providing HyperACL's transition matrix and stationary distribution."},{"cited_title":"Everything evolves in personalized pagerank","cited_arxiv_id":null,"evidence_quote":"Provides the infinite-series characterization of lazy personalized PageRank used in the linear decomposition identity."}],"review_version":1}