{"id":"f395a056-5189-413d-ad54-901697227620","arxiv_id":"2505.15842","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"AH-UGC produces multiple coarsened graphs from one sorted hashed list and keeps heterogeneous node types pure by coarsening each type separately.","lead":"This paper introduces AH-UGC, a graph coarsening method that produces multiple reduced graphs from one hashing pass and preserves node type boundaries in heterogeneous graphs. It matters because fast multi-scale graph compression could lower the cost of training graph neural networks on very large graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Coarsening quality rests on an unproven locality assumption: pairwise LSH closeness does not imply contiguity in the sorted list, and Lemma 1's weak bound does not establish that random clockwise merges group similar nodes.","rationale":"The reader's weakest_assumption identifies the same load-bearing point: the sorted order of aggregate LSH scores must place nodes that should be merged adjacently. I agree. The paper's experiments demonstrate runtime advantages and competitive accuracy, but they do not isolate whether the LSH-based ordering is responsible for coarsening quality. The theoretical support is insufficient because Theorem 3.1 covers only pairwise projection closeness, and Lemma 1, which would address contiguity, is unproved and, as stated, too weak to imply that distant nodes rarely fall between close pairs. The random rightward merge rule makes this concern concrete: the final blocks are random contiguous intervals of the sorted list, so all quality hinges on the list being a good one-dimensional embedding. The proposed permutation-control ablation would settle the question empirically. I would keep the conditional verdict rather than reject, because the runtime claim and constructional adaptivity are sound and the empirical results, while not isolating the mechanism, are broadly positive.","tokens_in":22905,"tokens_out":12049,"duration_ms":122667,"concrete_test":"Run the exact AH-UGC pipeline (same projections, same merge loop, same coarsening matrices) on Cora, Chameleon, and IMDB, but replace the score-sorted list with a random permutation before the clockwise merges. Compare node classification accuracy and relative eigen error at R=0.5 against the real AH-UGC. If the random-permutation control matches AH-UGC within one standard deviation, then the LSH ordering is not doing the work and the locality assumption is not load-bearing; if AH-UGC is clearly better, the concern is answered empirically. A useful secondary check is the mean rank distance of original-graph edges in L versus a random permutation, which directly tests contiguity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central mechanism of AH-UGC is that after sorting nodes by the aggregate LSH score s_i, 'similar nodes are positioned adjacently' (Section 3.1), so merging each node with its clockwise neighbor groups similar nodes. Theorem 3.1 only proves that two fixed points x,y have close projected scores with probability erf(...); it says nothing about whether other points' scores lie between them. Lemma 1 is the missing piece, but it is stated without proof, and the stated bound is too weak: when ||x-y|| is much smaller than ||x-z||, Phi(||x-y|| sqrt(l)/||x-z||) is about 1/2 + O(||x-y||/||x-z||), so it does not establish that a distant point rarely interrupts a close pair. Moreover, the merge rule selects a uniformly random supernode and merges it with its right neighbor, so the final partition is a random contiguous partition of the original list. Whether such random blocks are internally similar depends entirely on whether the 1D score order is a good locality embedding of the feature-plus-adjacency space; no evidence of this is provided. The adaptive and heterogeneous claims are largely constructional, but the claim that AH-UGC 'groups similar nodes' and preserves structural and semantic integrity depends on this unverified locality property.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AH-UGC, a graph-coarsening framework that combines LSH projections with consistent hashing to produce multiple coarsening resolutions from a single sorted hash-score list, together with a type-isolated variant for heterogeneous graphs. Nodes are assigned scalar scores by averaging l random projections of an augmented feature-adjacency vector, sorted by those scores, and coarsened by repeatedly selecting a supernode uniformly at random and merging it with its clockwise neighbor. Heterogeneous graphs are processed separately per node type, with per-type coarsening matrices and per-edge-type adjacency aggregation. The authors claim adaptive multi-resolution coarsening, balanced supernodes, semantic purity, and superior scalability, and support these claims with runtime, spectral, and node-classification experiments on up to 23 datasets.","tokens_in":23185,"tokens_out":7033,"duration_ms":74555,"significance":"AH-UGC addresses two genuine gaps: no existing coarsening method provides ratio-adaptive multi-resolution output in a single pass, and homogeneous coarsening methods violate type semantics on heterogeneous graphs. The consistent-hashing construction is simple and fast, and the runtime results in Table 1 are striking, with AH-UGC often an order of magnitude faster than UGC on large graphs. The type-isolation strategy is a clean, credible mechanism for heterogeneous semantic preservation, and Tables 3 and 4 show consistent gains over the included baselines. The main weakness is that the theoretical support for the central locality claim (Lemma 1) is incomplete and likely too weak, and the load-balance theorem rests on an unsubstantiated uniform-spacing model. The heterogeneous comparison also omits the only dedicated heterogeneous baseline, HGCond. These issues are fixable, but they currently leave the central 'groups similar nodes' claim unproven.","major_comments":[{"comment":"The claim that 'similar nodes are positioned adjacently' depends entirely on Lemma 1, yet the lemma is stated without proof and its bound cannot deliver the conclusion. For ||x-y|| much smaller than ||x-z||, the bound Phi(||x-y|| sqrt(l) / ||x-z||) is approximately 1/2 + O(||x-y||/||x-z||), i.e., an upper bound near 1/2, so it does not establish that a distant point 'rarely interrupts' a close pair. Moreover, Theorem 3.1 gives only a pairwise projection probability and says nothing about whether other points' scores lie between two close points, so the sorted-list contiguity assumption is unsupported. Because random clockwise merges create arbitrary contiguous blocks of the sorted list, the quality guarantee of the coarsening is not established. Please supply a rigorous contiguity or block-similarity bound, or re-frame the claim as a heuristic and add empirical validation, such as measuring intra-block similarity versus random partitions on the real datasets.","section":"Section 3.1 (Lemma 1)"},{"comment":"The load-balance proof models the sorted node positions as k-1 i.i.d. Uniform(0,1) order statistics and then states that the sorted list 'can be modeled as uniformly spaced over [0,1]'. Neither step follows from Algorithm 1: the actual process selects a supernode uniformly at random among the current supernodes and merges it with its right neighbor, which is a different stochastic process from placing k-1 uniform cuts, and the uniform-spacing assumption on the aggregate LSH scores is unverified. The claimed bound Pr[max_i |S_i| <= n/k + n(log k + c)/k] >= 1 - e^{-c} is therefore not proven for the algorithm as written. Please provide a proof that directly analyzes the merge process, or clearly state the uniform-spacing assumption as an additional hypothesis and validate it empirically.","section":"Appendix C (Theorem 3.2)"},{"comment":"The heterogeneous-graph evaluation omits HGCond, which the Related Work section identifies as 'the only approach designed for heterogeneous graphs.' Without this baseline, the claim that AH-UGC consistently outperforms existing methods on heterogeneous graphs is incomplete, and the large margins over type-blind baselines could mainly reflect the type-isolation mechanism rather than the adaptive LSH contribution. Please add HGCond to Table 4 and, where feasible, report standard deviations over multiple runs for the key comparisons.","section":"Section 4.3 and Table 4"}],"minor_comments":[{"comment":"The orientation of the coarsening matrix C is inconsistent: Definition 2.3 defines C in R^{N x n} with eX = C^T X, while Section 3.1 and Algorithm 1 define C as an n_c x N matrix with eF = C F and eA = C A C^T. Please fix the notation so all formulas are dimensionally consistent.","section":"Definition 2.3 / Section 3.1 / Algorithm 1"},{"comment":"The expression erf(epsilon sqrt(2 l ||x-y||)) appears to be missing a division bar; the standard form is erf(epsilon / (sqrt(2 l) ||x-y||)). Please clarify the formula.","section":"Theorem 3.1 and Appendix D"},{"comment":"Lines 3 and 5 both compute S <- F * W + b; remove the duplicate.","section":"Algorithm 1"},{"comment":"Figure 2 labels the method 'HA-UGC' instead of 'AH-UGC', the abstract says 23 datasets while Appendix A says 24, and Table 5 lists 'Penn49' while the text uses 'Penn94'. Please correct these inconsistencies.","section":"Figures and dataset counts"},{"comment":"Table 1 reports total time for ten target ratios, so baseline times include ten independent runs while AH-UGC performs one pass. Please state this explicitly and consider adding a single-ratio runtime comparison to separate the adaptivity gain from raw per-run speed.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one-liner: AH-UGC is a practical extension of the authors' own UGC that adds adaptive multi-ratio coarsening and type-isolated heterogeneous coarsening. The empirical results are strong; the theoretical claims need work.\n\nWhat is actually new: replacing UGC's bin-width tuning with a sorted-list and random adjacent-merge construction is a clever trick. It lets you generate coarsened graphs at any target ratio from a single sorted list, and the runtime tables show real wins on large graphs (ogbn-arxiv, Reddit, Yelp) where other methods fall over. The per-type coarsening for heterogeneous graphs is simple and effective: Table 4 shows large accuracy gains on IMDB, DBLP, and ACM over baselines that mix node types. The experimental breadth is genuinely commendable: 23 datasets, multiple GNN backbones, spectral error metrics, and a clear impurity analysis.\n\nNow the soft spots, in proportion. The central locality assumption is not proven. Lemma 1 is stated without proof, and Theorem 3.1 only shows pairwise projection closeness, not that the sorted list places similar nodes in contiguous blocks. The stress-test note is right that pairwise closeness does not guarantee contiguity. That said, the extensive empirical success suggests the heuristic works in practice on these datasets, so I would call this a theory gap rather than a fatal flaw. Second, Theorem 3.2's load-balance proof assumes the sorted list is uniformly spaced over [0,1]; that is an unjustified modeling assumption, and the proof is hand-wavy as written. The bound may be true, but the argument needs to be fixed or the claim softened. Third, the paper cites HGCond as the only prior heterogeneous method but never compares against it. For a paper whose headline claim is heterogeneous coarsening, that omission undercuts the experimental story. Finally, no code or data is released, which limits reproducibility.\n\nWho this is for: anyone working on graph coarsening, multi-scale graph analysis, or GNN preprocessing. It is a solid incremental contribution, not a reorientation. The adaptive and heterogeneous pieces are genuinely useful, and the experiments support the main practical claims against the included baselines.\n\nMy recommendation: this deserves a serious referee, not a desk reject. I would send it to review with a clear request to either prove or properly state Lemma 1, fix the uniform-spacing assumption in Theorem 3.2, add the HGCond comparison, and release code. With those revisions it could be a respectable paper.","headline":"A useful incremental extension of UGC with strong experiments, but the theory is thinner than claimed and a key baseline is missing.","tokens_in":23697,"tokens_out":2774,"would_cite":true,"duration_ms":31552,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A hash-sorted list yields every coarsening ratio in one pass.","keywords":["graph coarsening","locality-sensitive hashing","consistent hashing","adaptive multi-resolution","heterogeneous graphs","type-isolated coarsening","graph reduction","node classification"],"falsifier":"Compute, on a labeled graph with two well-separated feature clusters, the fraction of AH-UGC merges that join nodes whose feature distance exceeds the median pairwise feature distance. If that fraction approaches the random-pair baseline, the sorted-list adjacency that LSH is supposed to provide is not materializing.","tokens_in":22674,"feed_emoji":"🕸️","tokens_out":7131,"duration_ms":69168,"temperature":0.7,"pith_summary":"AH-UGC claims that graph coarsening can be made adaptive and type-aware by replacing per-ratio recomputation with a single sorted list of locality-sensitive hash scores. Each merge on that list joins a randomly chosen node with its clockwise neighbor, so different coarsening ratios are only successive merges on the same list, and moving from ratio $R$ to ratio $T$ requires no reprocessing. For heterogeneous graphs, nodes are grouped by type and each type is coarsened independently, so a supernode never mixes semantically different node types. If the claims hold, graph coarsening becomes a one-pass, multi-resolution operation that scales to graphs with millions of edges while preserving both spectral structure and heterogeneous semantics.","feed_headline":"A hash-sorted list yields all coarsening ratios in one pass","feed_subtitle":"A unified hashing framework coarsens homogeneous and heterogeneous graphs in one pass, preserving node-type semantics.","key_machinery":"The mechanism is a sorted list of aggregate LSH scores operated on by consistent-hashing clockwise merges. For each node $v_i$, the augmented feature vector $F_i=(1-\\alpha)X_i\\oplus\\alpha A_i$ is projected $l$ times and averaged to a scalar $s_i$; sorting these scores gives an ordered list in which each super-node initially contains one node, and each coarsening step picks a super-node at random and merges it with its immediate right neighbor. LSH is what makes similar nodes land near each other (Theorem 3.1 and Lemma 1), consistent hashing is what allows any ratio to be read off the same list, and the per-type partition of the heterogeneous procedure is what keeps supernodes type-pure.","core_discovery":"The central claim is that combining locality-sensitive hashing (LSH) with consistent hashing produces a single-pass, multi-resolution coarsening procedure. Node features and adjacency rows are blended by a heterophily factor $\\alpha$, projected with random Gaussian vectors, and the mean projection score per node is sorted; repeated clockwise merges in that sorted list then produce coarsened graphs at any target ratio $R=|V_c|/|V|$, with transitions from one ratio to another obtained by continuing or reversing the merge history. The paper further claims that restricting merges to nodes of the same type preserves the heterogeneous schema, and that the coarsened features and adjacency $\\tilde X = C^\\top X$, $\\tilde A = C^\\top A C$ retain enough structure for downstream GNN training on the coarsened graph to match or beat baseline coarsening methods on node classification and spectral fidelity.","pith_inferences":["If the locality premise holds, the quality gap between AH-UGC and an exact similarity-based coarsening could be measured by comparing each actual merge against the nearest-neighbor merge from the same sorted list; a small gap would support using the shortcut in practice.","Adaptivity makes the coarsening ratio a tunable parameter of multi-scale GNN training rather than a preprocessing decision: one could coarsen the same graph at several ratios and train a shared model on all resolutions in a single run.","The load-balance bound suggests a concrete extension: use AH-UGC supernodes as balanced partitions for distributed graph computation, since the expected supernode sizes hover near $n/k$ with high probability."],"forward_implications":["Multiple coarsening ratios, such as 55% down to 10%, are produced from one sorted list, so interactive visualization and real-time recommendation systems can switch resolutions without recomputing.","New nodes arriving in a streaming graph can be inserted into the existing sorted list and coarsened incrementally rather than restarting from scratch.","Type-isolated coarsening ensures that supernodes in heterogeneous graphs remain single-type, which avoids semantic drift and keeps node-classification accuracy close to the uncoarsened baseline.","The method scales to datasets where optimization-based coarseners run out of time or memory; on large graphs like ogbn-arxiv and Reddit it is the only tested method to finish.","Because de-coarsening reverses the merge history, the framework enables coarse-to-fine reconstruction of graph representations."],"supporting_citations":[{"why":"Provides the LSH-based UGC pipeline, including augmented features and random projections, that AH-UGC extends with consistent hashing.","marker":"[4]"},{"why":"Introduces consistent hashing with clockwise successor assignment, the operation AH-UGC repurposes as a merge rule for adaptive coarsening.","marker":"[23]"},{"why":"Supplies the p-stable LSH theory and the projection-based hash functions used to order nodes by similarity.","marker":"[32]"},{"why":"Revisits consistent hashing with bounded loads, the basis for the paper's load-balance guarantee on supernode sizes.","marker":"[24]"},{"why":"Defines the feature-aware coarsening formulation and coarsening matrix constraints that AH-UGC inherits.","marker":"[19]"},{"why":"Establishes the spectral coarsening objectives and baselines used to measure the structural fidelity of coarsened graphs.","marker":"[20]"},{"why":"Provides the heterogeneous graph condensation baseline and the heterogeneous GNN models used to evaluate type-preserving coarsening.","marker":"[25]"}],"fun_headline_variants":["Hash once, coarsen at any ratio, all types","All coarsening ratios from one sorted hash","Single-pass adaptive coarsening for any graph","Type-aware hashing coarsens at every ratio","One hash order yields all coarsening scales"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that sorting nodes by an average of random projection scores places mutually similar nodes adjacent in the sorted list, so that each clockwise merge joins two nodes that belong together; this adjacency is asserted by Lemma 1, which is stated without proof, while Theorem 3.1 only bounds pairwise projection distance and does not guarantee contiguous blocks.","fun_headline_variants_meta":{"raw":{"variants":["Hash once, coarsen at any ratio, all types","All coarsening ratios from one sorted hash","Single-pass adaptive coarsening for any graph","Type-aware hashing coarsens at every ratio","One hash order yields all coarsening scales"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000692,"raw_usage":{"total_tokens":3128,"prompt_tokens":937,"completion_tokens":2191,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":2116}},"tokens_in":553,"tokens_out":2191,"duration_ms":15616,"temperature":1.0,"reasoning_tokens":2116,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:37:53.735269+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, on a labeled graph with two well-separated feature clusters, the fraction of AH-UGC merges that join nodes whose feature distance exceeds the median pairwise feature distance. If that fraction approaches the random-pair baseline, the sorted-list adjacency that LSH is supposed to provide is not materializing.","supporting_citations":[{"cited_title":"Ugc: Universal graph coarsening,","cited_arxiv_id":null,"evidence_quote":"Provides the LSH-based UGC pipeline, including augmented features and random projections, that AH-UGC extends with consistent hashing."},{"cited_title":"Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web,","cited_arxiv_id":null,"evidence_quote":"Introduces consistent hashing with clockwise successor assignment, the operation AH-UGC repurposes as a merge rule for adaptive coarsening."},{"cited_title":"Approximate nearest neighbors: Towards removing the curse of dimensionality,","cited_arxiv_id":null,"evidence_quote":"Supplies the p-stable LSH theory and the projection-based hash functions used to order nodes by similarity."},{"cited_title":"Revisiting consistent hashing with bounded loads,","cited_arxiv_id":null,"evidence_quote":"Revisits consistent hashing with bounded loads, the basis for the paper's load-balance guarantee on supernode sizes."},{"cited_title":"A unified framework for optimization-based graph coarsening,","cited_arxiv_id":null,"evidence_quote":"Defines the feature-aware coarsening formulation and coarsening matrix constraints that AH-UGC inherits."},{"cited_title":"Graph reduction with spectral and cut guarantees.,","cited_arxiv_id":null,"evidence_quote":"Establishes the spectral coarsening objectives and baselines used to measure the structural fidelity of coarsened graphs."},{"cited_title":"Heterogeneous graph condensation,","cited_arxiv_id":null,"evidence_quote":"Provides the heterogeneous graph condensation baseline and the heterogeneous GNN models used to evaluate type-preserving coarsening."}],"review_version":1}