{"id":"37833816-843b-4b37-85ee-ecf47412408f","arxiv_id":"2502.03663","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"Greedy routing and diameter bounds for small-world graphs are generalized from lattices to fixed-growth graphs of any dimensionality alpha, with an empirical application to U.S. road networks.","lead":"This paper extends a randomized 'highway' small-world routing model from square lattices to a broad class of graphs with controlled growth, proving greedy routing and diameter bounds. The authors then argue that U.S. road networks are better modeled by this more flexible framework than by lattices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's shell-size cancellation is invalid: subtracting Theta ball sizes with different constants does not yield Theta(b^{alpha-1} w^alpha), so the normalization, high-probability routing, and diameter bounds collapse.","rationale":"The central claim is that randomized highway graphs on fixed-growth graphs admit tight Theta(log n) (or Theta(alpha-root(log^2 n))) greedy routing and diameter. For that to be true, the shell-count bounds in Lemma 2 must hold, since they underlie the normalization constant z(u) (Lemma 3), the fresh-node probability (Lemma 7), and the diameter set-growth argument (Lemma 8). The proof of Lemma 2 subtracts two Theta bounds as if the hidden constants were equal; they are not. The fixed-growth definition quantifies c1, c2 uniformly but allows any c2/c1, and no argument in Section 3 controls this ratio. Thus the shell size lower bound can fail, and the chain of results built on shells has no foundation. This is an internal inconsistency in the proof, not merely a disagreement with prior consensus. The secondary issue in Theorem 2—assuming z(u) = Theta(1) when Lemma 3 gives O(log log n)—is also real and would independently break the high-probability lower bound for alpha >= 2, but the shell problem is more fundamental because it also invalidates the expectation and diameter claims. The authors are careful to flag the finite-graph limitation in Section 4, and they provide code for the experiments; that is to their credit. Yet the empirical comparison (Figures 3-5) depends on the heuristic dimensionality estimate, which is explicitly acknowledged not to be meaningful for finite graphs, so it cannot rescue the theory. The reader's weakest_assumption identified the same shell-cancellation problem; I agree. Since the reader's REJECT verdict is supported by this analysis, no verdict adjustment is needed.","tokens_in":19297,"tokens_out":6448,"duration_ms":58288,"concrete_test":"Analytical check: instantiate the fixed-growth definition with alpha = 2, c1 = 1, c2 = 5. For any node u with |B_2(u)| >= 1 and |B_1(u)| <= 5, the shell S_1^1(u) = B_2(u) \\ B_1(u) may be empty. Lemma 2's b=1 claim predicts Theta(w^alpha) = Theta(1) nodes. Since the paper imposes no constraint c2/c1 < 2^alpha, a graph family realizing these constants (e.g., a comb graph with long teeth) is admissible and violates Lemma 2. Determine whether such a family exists; if yes, Lemma 2 is false as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing flaw is Lemma 2. The fixed-growth definition only asserts |B_l(u)| = Theta(l^alpha), i.e. there exist family-wide constants c1 <= c2 with c1 l^alpha <= |B_l(u)| <= c2 l^alpha. Lemma 2 claims the shell S_b^{(w)}(u) = B_{(b+1)w}(u) \\ B_{bw}(u) has Theta(b^{alpha-1} w^alpha) nodes because the width constants can be chosen 'such that the constants in this theta notation are the same.' This is not a quantity the construction may choose: c1 and c2 are fixed by the graph family. The shell size is at least c1((b+1)w)^alpha - c2(bw)^alpha, which for b=1 equals (2^alpha c1 - c2)w^alpha. Nothing in the fixed-growth definition prevents c2/c1 >= 2^alpha, in which case the lower bound is non-positive and the shell can be empty. Every subsequent use of shell sums—Lemma 3's normalization constant, Lemma 7's fresh-node argument, Lemma 8's diameter growth—inherits this failure, so Theorems 1-3 are not established. Separately, the high-probability lower bound in Theorem 2 for alpha >= 2 assumes z(u) = Theta(1) ('we assume generously'), but Lemma 3 only proves z(u) = O(log n/k + log log n) = O(log log n) when k = Theta(log n). With z(u) up to log log n, the integral bounding E[log x] becomes O(log log n), so the claimed Omega(log n) hop lower bound does not follow.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper generalizes the randomized highway model of Gila, Ozel, and Goodrich from lattices to 'fixed-growth graphs' of dimensionality alpha, in which every ball of radius ell contains Theta(ell^alpha) nodes with family-wide constants. It claims tight Theta(log n) bounds on greedy routing and diameter (Theorems 1-3) when the highway constant k = Theta(log n), including high-probability results, and it presents experiments on all 50 U.S. state road networks plus DC arguing that the optimal clustering exponent is better predicted by the estimated dimensionality alpha than by the lattice value 2 or by network size. The theoretical analysis is built on shell-size bounds (Lemma 2), normalization-constant bounds (Lemma 3), and fresh-node arguments (Lemmas 7-8).","tokens_in":19745,"tokens_out":12123,"duration_ms":100262,"significance":"If the theorems were established, the paper would provide a clean, tight extension of Kleinberg-style greedy routing to a broad class of growth-restricted graphs with possibly non-integral dimensionality, including high-probability routing and diameter bounds; the empirical comparison across 50 states and DC, with released code, is a valuable addition. However, the key lemma underpinning the proofs is not a consequence of the fixed-growth definition, so the theoretical contribution is not presently established; the empirical findings must then be read as a heuristic study rather than as a validation of the model.","major_comments":[{"comment":"The shell-size bound is not justified by the fixed-growth definition. From |B_ell(u)| = Theta(ell^alpha) with family-wide constants c1 and c2, the shell S_b^{(w)}(u) has at least c1((b+1)w)^alpha - c2(bw)^alpha nodes, which is non-positive for b = 1 whenever c2/c1 >= 2^alpha; the definition permits such constants. The proof's statement that shell widths are chosen so that 'the constants in this theta notation are the same' is not an operation the construction can perform, because c1 and c2 are fixed by the graph family and not by the choice of w. Consequently, Lemma 2's Theta(b^{alpha-1} log n) highway-node shell bound is unproven, and Lemma 3, Lemma 7, Lemma 8, and Theorems 1-3, all of which rely on this shell count, do not follow.","section":"Section 3.1, Lemma 2"},{"comment":"The lower-bound half of Theorem 2 for alpha >= 2 assumes z(u) = Theta(1), justified in the text as 'we assume generously.' This is not supported by Lemma 3.1, which only gives z(u) = O(log n/k + log log n) = O(log log n) with high probability when k = Theta(log n). Under that bound, Corollary 1 yields Pr(x >= c) = O(z(u) c^{-alpha}) rather than O(c^{-alpha}); the integral used to bound E[log x] then evaluates to O(log log n), not O(1). The Chernoff argument therefore cannot produce the claimed Omega(log n) lower bound on the number of highway hops, and the tight high-probability bound for alpha >= 2 is not established.","section":"Section 3.3, Theorem 2 proof"},{"comment":"The condition stated for the limit to vanish, log ell + c'_1 ell^alpha/(k-1) = O(log n), is not sufficient. The expression to be shown to diverge is log c2 + log n - alpha log ell - c'_1 ell^alpha/(k-1); for this to tend to infinity one needs alpha log ell + c'_1 ell^alpha/(k-1) <= (1 - epsilon) log n for some epsilon > 0. For ell = c (k log n)^{1/alpha}, this requires choosing c with c_1 c^alpha < 1, a choice the proof neither states nor justifies. The lemma may be repairable, but as written the lower bound Theta(alpha-root(k log n)) on the distance to the nearest highway is not proven.","section":"Section 3.1, Lemma 4 proof"},{"comment":"The empirical evaluation is in-sample: the dimensionality alpha is estimated from each state's road network, and the same network is used to measure greedy routing performance and to determine the empirically optimal clustering exponent s; no held-out validation or cross-validation is reported, and no statistical significance is given for the correlations in Figures 4 and 5. Because Section 4 itself notes that for finite graphs the fixed-growth constants can be chosen to make any dimensionality alpha work, the estimated alpha is a heuristic curve-fit rather than an established intrinsic parameter, so the causal claim that dimensionality predicts the optimal clustering exponent is not supported.","section":"Section 4 and Appendix C"}],"minor_comments":[{"comment":"The text reads 'we have have no guarantees'; this is a typo for 'we have no guarantees.'","section":"Section 3.1, Shells paragraph"},{"comment":"The sentence 'The probability that all balls contain at least one highway node is at most 1 - e^{-...} by a union bound' is not a union bound; it should be a product bound over independent balls, and the leading '1 -' is inconsistent with the subsequent paragraph, which correctly works with e^{-...}.","section":"Section 3.1, Lemma 4 proof"},{"comment":"The notation Theta(alpha-root(log^2 n)) is ambiguous; it should be written as (log n)^{2/alpha} or as Theta((log n)^{2/alpha}) to avoid confusion about the order of the root and the logarithm.","section":"Theorem 2 statement"},{"comment":"The description of the estimator would benefit from specifying exactly how the ratio c2/c1 is computed from the sampled balls and how the per-node alpha values are aggregated into the reported median; the current description is underspecified regarding the number of samples and the minimization procedure.","section":"Appendix C, Dimensionality estimation"}],"recommendation":"reject","confidential_remarks":"The rejection is driven by Lemma 2, which is not a local typo but a missing assumption in the model: the shell-size bound Theta(b^{alpha-1} w^alpha) does not follow from the fixed-growth ball-growth condition, and the subsequent normalization, routing, and diameter proofs inherit this failure. The empirical section is interesting, but it does not compensate for the unsound theoretical core. If the authors can identify a natural additional shell-growth axiom under which the shell bound holds and re-prove the results, a resubmission may be warranted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is a serious and clearly written attempt to extend the randomized highway model from 2D lattices to fixed-growth graphs with arbitrary dimension alpha. That's a natural question, and the paper is honest about its own limitations — it explicitly notes that fixed-growth dimensionality is not directly meaningful for finite graphs, which is more than many empirical papers do. The empirical comparison across all 50 states plus DC is a nice data point, and the code is available.\n\nThe problem is the proof of Lemma 2. The shell size is computed as the difference of two Theta bounds. The fixed-growth definition only gives constants c1 <= c2 that are fixed by the family. The paper says the widths wi can be chosen so that 'the constants in this theta notation are the same' — but that's not a choice the construction gets to make. The difference |B_{(b+1)w}| - |B_{bw}| could be anything from nonnegative to a large positive value depending on c2/c1. For b=1, the lower bound is (2^alpha c1 - c2) w^alpha, which is not guaranteed to be positive unless c2 < 2^alpha c1. Nothing in the fixed-growth definition prevents c2 from being much larger. So the claimed Theta(b^{alpha-1} log n) shell bound is not proven, and since Lemma 3, Lemma 7, and Lemma 8 all build on that shell bound, Theorems 1-3 don't go through as written.\n\nThere is also a second issue in Theorem 2. The proof of the lower bound assumes 'generously' that z(u) = Theta(1), but the only high-probability bound proven for z(u) in Lemma 3 is O(log n/k + log log n) = O(log log n). With z(u) that large, the integral bounding E[log x] gives O(log log n), not O(1), and the Omega(log n) lower bound on highway hops doesn't follow. This is a smaller issue than Lemma 2, but it confirms the pattern: the high-probability statements are asserted beyond what the lemmas support.\n\nWhat is genuinely good here: the paper identifies a real gap in prior work, the fixed-growth class is a sensible way to talk about graph dimensionality, and the empirical result that alpha beats 2 as a clustering exponent on road networks is worth reporting. The authors also provide reproducible code. But the central theoretical engine is not running. This is not a desk-reject-quality paper — it deserves a serious referee and a chance for major revision. I'd send it out, and I'd tell the authors to fix the shell argument or add an assumption that pinches the constants (e.g., c2/c1 < 2^alpha, or a stronger definition of fixed-growth that controls shell sizes directly).","headline":"The generalization to fixed-growth graphs is the right kind of step, but the shell-size cancellation at the heart of the proof does not hold as written, so the routing and diameter bounds are not established.","tokens_in":20234,"tokens_out":2776,"would_cite":false,"duration_ms":24554,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","68W20","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper extends the randomized highway model to any fixed-growth graph and proves tight greedy-routing and diameter bounds, then shows that matching the clustering exponent to the graph's dimensionality improves routing on U.S.","keywords":["small-world networks","greedy routing","fixed-growth graphs","randomized highway model","graph dimensionality","diameter bounds","road networks","bounded-growth graphs"],"falsifier":"Take a road network or a synthetic fixed-growth graph with estimated $\\alpha$, set $k=c\\log n$, and count highway nodes inside shells at several shell-distances $b$; if the counts do not scale as $\\Theta(b^{\\alpha-1}\\log n)$ with high probability, the normalization-constant bounds and the theorems built on them fail. A sharper test is to construct a graph whose ball sizes satisfy $|B_\\ell(u)|=\\Theta(\\ell^\\alpha)$ but whose shell sizes oscillate so the polynomial cancellation does not hold, simulate greedy routing with $k=\\Theta(\\log n)$, and check whether the hop count exceeds the Theorem 2 bound with high probability.","tokens_in":19066,"feed_emoji":"🧭","tokens_out":10184,"duration_ms":81633,"temperature":0.7,"pith_summary":"This paper establishes that the randomized highway model for small-world networks works on any fixed-growth graph, a bounded-growth family in which every ball of radius $\\ell$ contains $\\Theta(\\ell^\\alpha)$ nodes, rather than only on two-dimensional lattices. With highway constant $k\\in\\Theta(\\log n)$ and the clustering exponent set to the graph's dimensionality $\\alpha$, greedy routing between nodes at distance $\\Theta(\\alpha\\sqrt{n})$ is shown to take $\\Theta(\\log n)$ hops with high probability when $\\alpha\\geq 2$, and $\\Theta(\\alpha\\sqrt{\\log^2 n})$ hops when $\\alpha\\leq 2$; the diameter is $\\Theta(\\log n/\\log\\log n)$ for $\\alpha>2$ and $\\Theta(\\alpha\\sqrt{\\log^2 n})$ for $\\alpha\\leq 2$. The paper also reports experiments on all 50 U.S. state road networks and DC in which using the estimated $\\alpha$ as the clustering exponent beats the lattice value $2$ for every state, and in which $\\alpha$ predicts the empirically optimal exponent better than network size does. A sympathetic reader would care because it replaces a rigid geometric assumption with a measurable growth property, making the small-world routing guarantee applicable to real spatial networks.","feed_headline":"Greedy routing hits log n hops on any fixed-growth graph","feed_subtitle":"Setting the clustering exponent to a network's measured dimensionality beats the lattice choice on all 50 U.S. road networks.","key_machinery":"The load-bearing object is the shell partition of a fixed-growth graph. For a node $u$, the shell $S_b^{(w)}(u)$ is the annulus between balls of radii proportional to $(b+1)w$ and $bw$, with width $w\\in\\Theta(\\alpha\\sqrt{k\\log n})$; shells partition the graph even though balls may overlap, which the lattice tiling used by earlier work cannot do. Lemma 2 shows that, with high probability, a shell at shell-distance $b$ contains $\\Theta(b^{\\alpha-1}\\log n)$ highway nodes, because the ball-count difference $\\Theta(((b+1)^\\alpha-b^\\alpha)w^\\alpha)$ cancels to $\\Theta(b^{\\alpha-1}w^\\alpha)$. Shells supply the estimates needed to bound the normalization constant $z(u)=\\sum_{h\\in H} d(u,h)^{-\\alpha}$, and that bound gives the probability that a long-range contact improves the distance to the destination, which in turn drives the greedy-routing and diameter theorems.","core_discovery":"The paper's central claim is that the randomized highway model achieves tight greedy-routing and diameter bounds on every fixed-growth graph of dimensionality $\\alpha$, not just lattices. In this model each node independently becomes a highway node with probability $1/k$, highway nodes receive $\\Theta(k)$ long-range contacts to other highway nodes with probability proportional to $d(u,v)^{-\\alpha}$, and each non-highway node stores a pointer to the neighbor closest to the highway. Theorem 2 states that for $k\\in\\Theta(\\log n)$ and $d(s,t)=\\Theta(\\alpha\\sqrt{n})$, greedy routing succeeds in $\\Theta(\\log n)$ hops with high probability in $\\log n$ if $\\alpha\\geq 2$, and in $\\Theta(\\alpha\\sqrt{\\log^2 n})$ hops if $\\alpha\\leq 2$; Theorem 3 states the diameter is $\\Theta(\\log n/\\log\\log n)$ for $\\alpha>2$ and $\\Theta(\\alpha\\sqrt{\\log^2 n})$ for $\\alpha\\leq 2$. The empirical half of the paper claims that modeling the U.S. road network as fixed-growth and choosing the clustering exponent equal to the estimated dimensionality gives better greedy-routing performance than the lattice exponent $2$ on every state, and that the estimated dimensionality is a better predictor of the optimal exponent than the network's size.","pith_inferences":["One testable extension: the shell technique should also yield bounds when dimensionality varies by radius or location, since the paper's proofs use only local shell counts; this is the paper's own stated future direction, not a result of this paper.","A direct validation of the empirical claim would be to measure shell highway counts at many radii on real road networks and compare them with the $\\Theta(b^{\\alpha-1}\\log n)$ prediction, which the paper does not report.","If the fixed-growth model transfers to other spatial networks such as flight or neural graphs, the same recipe, estimate $\\alpha$ and set the clustering exponent to $\\alpha$, would give an immediate routing prescription, but that transfer is untested.","The threshold at $\\alpha=2$ in Theorem 2 is a crisp prediction: synthetic fixed-growth graphs just above and below $\\alpha=2$ should show a hop-count switch from $O(\\log n)$ to $O((\\log n)^{2/\\alpha})$, an experiment that would separate the model's substance from its proof artifacts."],"forward_implications":["The $\\Theta(\\log n)$ greedy-routing guarantee no longer requires a square-lattice substrate; any fixed-growth graph with dimensionality $\\alpha$ admits the same tight bound when the clustering exponent is set to $\\alpha$.","The greedy-routing bound is tight: for $\\alpha\\geq 2$ the high-probability hop count is $\\Theta(\\log n)$, and for $\\alpha\\leq 2$ it is $\\Theta(\\alpha\\sqrt{\\log^2 n})$, so the earlier lattice analysis left no slack in the expected case either.","The diameter is $\\Theta(\\log n/\\log\\log n)$ for $\\alpha>2$, meaning the highway subgraph is navigable almost as quickly as its diameter allows, while for $\\alpha\\leq 2$ the distance to the highway becomes the bottleneck.","Practitioners can set the clustering exponent by measuring a network's growth dimensionality; on the 50 U.S. state road networks and DC this choice outperforms the universal lattice value $2$.","The estimated dimensionality $\\alpha$, not the network size, is the better predictor of the empirically optimal clustering exponent, contradicting the size-based conjecture from prior work."],"supporting_citations":[{"why":"Establishes the lattice small-world model and the $O(\\log^2 n)$ greedy-routing guarantee that this paper generalizes.","marker":"[28]"},{"why":"Provides the tight lower bound for greedy routing in the lattice model and the highway-expansion lower-bound style used for the diameter.","marker":"[38]"},{"why":"Introduces the randomized highway model and proves $O(\\log n)$ expected greedy routing on two-dimensional lattices, the starting point extended here.","marker":"[21]"},{"why":"Supplies the U.S. road-network dataset, the empirical clustering-exponent methodology, and the size-based conjecture this paper tests and refines.","marker":"[22]"},{"why":"Earlier generalization of small-world routing to growth-bounded graphs that achieved only an unspecified polylogarithmic bound, which this paper improves to tight bounds.","marker":"[14]"},{"why":"Provides the simplified Chernoff bounds used in every high-probability highway-count and normalization-constant argument.","marker":"[12]"}],"fun_headline_variants":["Fixed-growth graphs get tight greedy routing bounds","Road networks route better with true dimensionality","Beyond lattices: log n routing on fixed-growth graphs","Dimensionality beats lattice choice for US roads"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that every ball in every graph of the family has size $\\Theta(\\ell^\\alpha)$ with the same hidden constants, so that the difference between consecutive ball sizes really is $\\Theta(b^{\\alpha-1}w^\\alpha)$; the paper itself notes that on a single finite graph the constants can be chosen to make any dimensionality $\\alpha$ fit, so the road-network application rests on an unvalidated heuristic.","fun_headline_variants_meta":{"raw":{"variants":["Fixed-growth graphs get tight greedy routing bounds","Road networks route better with true dimensionality","Beyond lattices: log n routing on fixed-growth graphs","Dimensionality beats lattice choice for US roads"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000286,"raw_usage":{"total_tokens":1789,"prompt_tokens":1158,"completion_tokens":631,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":774,"completion_tokens_details":{"reasoning_tokens":573}},"tokens_in":774,"tokens_out":631,"duration_ms":6405,"temperature":1.0,"reasoning_tokens":573,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T04:12:47.788622+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a road network or a synthetic fixed-growth graph with estimated $\\alpha$, set $k=c\\log n$, and count highway nodes inside shells at several shell-distances $b$; if the counts do not scale as $\\Theta(b^{\\alpha-1}\\log n)$ with high probability, the normalization-constant bounds and the theorems built on them fail. A sharper test is to construct a graph whose ball sizes satisfy $|B_\\ell(u)|=\\Theta(\\ell^\\alpha)$ but whose shell sizes oscillate so the polynomial cancellation does not hold, simulate greedy routing with $k=\\Theta(\\log n)$, and check whether the hop count exceeds the Theorem 2 bound with high probability.","supporting_citations":[{"cited_title":"In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing","cited_arxiv_id":null,"evidence_quote":"Establishes the lattice small-world model and the $O(\\log^2 n)$ greedy-routing guarantee that this paper generalizes."},{"cited_title":"In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing","cited_arxiv_id":null,"evidence_quote":"Provides the tight lower bound for greedy routing in the lattice model and the highway-expansion lower-bound style used for the diameter."},{"cited_title":"In: Combinatorial Optimization and Applications: 16th International Conference, COCOA 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II","cited_arxiv_id":null,"evidence_quote":"Introduces the randomized highway model and proves $O(\\log n)$ expected greedy routing on two-dimensional lattices, the starting point extended here."},{"cited_title":"In: Proceedings of the 30th International Conference on Advances in Geographic Information Systems","cited_arxiv_id":null,"evidence_quote":"Supplies the U.S. road-network dataset, the empirical clustering-exponent methodology, and the size-based conjecture this paper tests and refines."},{"cited_title":"https: //doi.org/10.1016/j.tcs.2005.12.008, complex Networks","cited_arxiv_id":null,"evidence_quote":"Earlier generalization of small-world routing to growth-bounded graphs that achieved only an unspecified polylogarithmic bound, which this paper improves to tight bounds."}],"review_version":1}