{"id":"90b2388e-2076-47a3-b594-31b47b6b7f16","arxiv_id":"2509.05129","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"TreeIndex builds a tree-decomposition labelling that computes exact resistance distances in O(h) time per query with O(n·h) size, and scales to the 23.9M-node US road network.","lead":"This paper presents TreeIndex, an index that answers exact electrical-distance (resistance distance) queries on huge road networks in about a millisecond, instead of minutes. It is the first exact method demonstrated on the full US road network, and could make robust routing, network analysis, and graph-neural-network diagnostics practical at national scale.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.9's support conjecture is the linchpin of Lemma 3.10 and the query algorithms, but its proof is not established; any violation of the predicted zero/nonzero pattern changes the computed resistance distance.","rationale":"The reader's weakest_assumption is exactly Lemma 3.9's support conjecture, and my reading agrees that this is the most load-bearing unproved step. If the support pattern is wrong, Lemma 3.10's path-only decomposition is wrong and both query algorithms return incorrect distances; the entire exactness claim collapses. The proof's language about connectivity is not a proof: for an inverse M-matrix, strict positivity of off-diagonal entries requires the induced grounded network on U to be connected, and the paper never shows this for SubTree(v) using original graph edges. The zero-outside-subtree part is also asserted rather than derived. Lemma 4.4 is an additional red flag: its statement is false in general, even though the algorithm might only need the weaker ancestor property. These issues are addressable—the linear algebra machinery (Lemmas 3.4-3.7, 4.3) is standard, and the paper has supporting experiments with precision checks—so a conditional accept is appropriate rather than a rejection. I therefore leave the reader's verdict unchanged.","tokens_in":34895,"tokens_out":37135,"duration_ms":408053,"concrete_test":"Write an exact rational-arithmetic verifier for all graphs up to n=8: enumerate minimum-degree elimination trees with all tie-breakings; build labels exactly as in Algorithm 1 / Lemma 4.3; for every pair (s,t) compare Lemma 3.10's sum against the resistance distance computed by inverting L with one row/column removed (or using the pseudoinverse). Also record the support matrix and test whether S[v,u]≠0 iff u∈SubTree(v). One mismatch on any tie-breaking disproves the central claim; if all small graphs pass, Lemma 3.9 becomes an expository gap rather than a correctness risk.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.9's support claim is load-bearing: Lemma 3.10 and Algorithms 2-3 sum only over path nodes and set every other term to zero. The proof does not establish that, for U=SubTree(v), the inverse of the principal submatrix L_UU has nonzero off-diagonal entries exactly for descendants of v. Nonzero off-diagonals of an inverse M-matrix require the network induced by U to be connected; this connectivity is asserted ('connectivity between v and nodes in its subtree') but not proven using original edges, and MDE fill-in/tie-breaking make it non-obvious. The 'all other entries are zero' clause is likewise asserted from vertex cuts without a formal argument. A second, concrete gap: Lemma 4.4 says every w in N(v_i)∩U is a child of v_i, which is false in general (e.g., a 3-cycle can produce an edge from v_i to a grandchild); the algorithm's while-loop may only require ancestorhood, but the stated lemma and the complexity proof rely on the stronger claim. Any violation of the support pattern changes the Lemma 3.10 sum by an omitted squared term, so the central exactness claim is not yet secured.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TreeIndex, an exact indexing method for resistance-distance queries on graphs with small treewidth. The central idea is to combine the cut property of resistance distance (expressed via Schur complements and a rank-1 decomposition of the inverse Laplacian) with a minimum-degree-elimination (MDE) tree decomposition. The authors claim that the resistance distance r(s,t) depends only on labels stored along the paths from s and t to the root of the tree decomposition (Lemma 3.10), that a labelling of size O(n·h_G) can be built in O(n·h_G^2·d_max) time, and that single-pair and single-source queries take O(h_G) and O(n·h_G) time, respectively. Experiments on road and social networks, including the full USA road network, are reported, and the method is compared with random-walk, Laplacian-solver, and index-based baselines.","tokens_in":35227,"tokens_out":25964,"duration_ms":274776,"significance":"If the correctness arguments are completed, this would be a notable contribution: it is, to my knowledge, the first resistance-distance labelling scheme with sublinear query time for small-treewidth graphs, and the experiments suggest practical scalability to graphs with tens of millions of nodes. The paper also makes a useful conceptual connection between the Cholesky/Schur-complement structure of the inverse Laplacian and the elimination-tree hierarchy of an MDE tree decomposition. The claimed complexity bounds, O(n·h_G) space and O(h_G) query time, are attractive and, if realized, bring resistance-distance queries close to the performance of shortest-path hierarchical labelling. The authors provide source code and extensive experiments, which strengthens the practical claims. However, the central correctness proof currently rests on an insufficiently justified support-structure lemma, and the construction pseudocode contains a concrete normalization error; these issues must be resolved before the exactness claim can be accepted.","major_comments":[{"comment":"Lemma 3.9 is the load-bearing support claim: it asserts that S[v,u] is nonzero exactly when u is in the subtree of v in the MDE tree decomposition. The proof does not establish this. The sentence 'due to the connectivity between v and nodes in its subtree' asserts the needed connectivity of the processed subgraph induced by {v} ∪ SubTree(v), but no proof is given that this induced subgraph is connected, nor that every processed node outside SubTree(v) is disconnected from v in that subgraph. Both the dependency property (Lemma 3.10) and Algorithms 2 and 3 rely on setting all non-path terms to zero; any violation of this pattern changes the computed resistance distance by an omitted squared term. A rigorous proof must be supplied, using the MDE elimination-tree structure (e.g., showing that original edges only join ancestor-descendant pairs and that descendants of v form the connected com","section":"§3.2, Lemma 3.9"},{"comment":"The normalization step is written incorrectly. Line 12 sets S[v_i,v_i] = 1/δ, where δ = d_{v_i} − Σ_{w∈N(v_i)∩U} S[v_i,w]. Line 14 then divides every u in SubTree(v_i) by the same δ. Since SubTree(v_i) includes v_i under the paper's own convention (see Example 9 and Lemma 4.1), the diagonal entry is divided by δ twice. For the first processed node in a triangle, d=2 and U∩N(v)=∅, so δ=2; line 12 gives S[v_i,v_i]=1/2, then line 14 changes it to 1/4, whereas the 1×1 principal submatrix [d] has inverse 1/2. The update loop must be over SubTree(v_i)\\{v_i}, or the off-diagonal entries must be normalized differently (e.g., multiplied by S[v_i,v_i]). This is a concrete correctness bug in the construction algorithm.","section":"§4.2, Algorithm 1, lines 12–14"},{"comment":"Lemma 4.4 states that for every w ∈ N(v_i)∩U, v_i is the parent of w in T_min. This is false. In a 3-cycle with MDE elimination order 1,2,3, the elimination tree is the path 1→2→3. When processing v_i=3, U contains {1,2} and N(3)∩U contains 1; but 1 is a grandchild of 3, not a child. The while-loop in Algorithm 1 still terminates because v_i is an ancestor of w, but the lemma as stated is incorrect. The proof of Lemma 4.6 cites Lemma 4.4 to bound the work; if the ancestor relation is weaker than parent, the nested-subtree argument needs to be restated (the stated O(n·d_max·h_G^2) bound may still hold, but the current proof does not show it). This lemma should be corrected or replaced with a precise ancestor-statement and the complexity proof adjusted accordingly.","section":"§4.2, Lemma 4.4"},{"comment":"Lemma 3.10 sums over 'P_{LCA→root}', which is ambiguous: Algorithm 2 stops at the root (line 12: while w ≠ T_min.root), and the root's label S[root,·] is not constructed by Algorithm 1 because the root is never added to U. Example 10 also excludes the root. The statement should explicitly define the path ranges used in Lemma 3.10, and the proof should make clear why the root term is absent. As written, a reader could conclude that the sum includes a nonexistent label.","section":"§3.2, Lemma 3.10 / Algorithm 2 path range"}],"minor_comments":[{"comment":"The indexing formula appears to have u and v swapped. The text says 'S[v,u] can be visited via S[u].res[DFSOrder[u]−DFSOrder[v]]', but Example 11 correctly uses S[v].res[DFSOrder[u]−DFSOrder[v]]. Please correct the lemma statement.","section":"§4.1, Lemma 4.1"},{"comment":"The proof says S[u].res stores values for all nodes in the path from u to the root, but the labelling structure (Lemma 4.1 and Figure 5) stores values for the subtree rooted at u. This discrepancy should be fixed.","section":"§4.2, Lemma 4.2"},{"comment":"The experiments set ground truth using TreeIndex itself. Exp III provides an independent check against LapSolver on two datasets, but the manuscript should qualify that the ground-truth statement in §6.1 is only a self-consistency reference and that independent verification was performed separately.","section":"§6.1"},{"comment":"There are several typos and notation inconsistencies (e.g., 'qery' in Problem 1, 'eletrical flow' in Lemma 5.1, 'Defiend' in Definition 2, and the unresolved subscripts in the statement of Lemma 3.10). A careful proofreading pass is recommended.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The central idea is plausible and the experiments are impressive, but the exactness claim is not yet proven. In particular, Lemma 3.9's support conjecture is asserted rather than proved, and the construction algorithm's pseudocode has a normalization bug. Both are within the scope of a revision, and I would expect the authors to supply a rigorous proof of the support structure and correct the pseudocode before the paper can be accepted. The fit with SIGMOD is good if these issues are resolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: TreeIndex is the first tree-decomposition labelling for exact resistance distance, and on the Full-USA road network it answers exact single-pair queries in under a millisecond and single-source queries in ~190 seconds—orders of magnitude faster than the exact and approximate baselines they compare against. That result is worth taking seriously even though the correctness proof has two real gaps.\n\nWhat the paper does well: the linear algebra core is standard Schur complement / rank-1 update material (Lemmas 3.4-3.7, 4.3), and the dependency property (Lemma 3.10) is a genuinely new closed form: r(s,t) as a sum of squared label differences along the s-to-root and t-to-root paths. The construction algorithm is a clever bottom-up rank-1 update that matches the tree structure, and the complexity bounds (label size O(n*h), query O(h)) are credible. The experiments are extensive and the precision check against LapSolver on NewYork and Road-PA (absolute error <1e-11) is good evidence the method is computing the right numbers on real inputs.\n\nThe soft spots, in order of importance. First, Lemma 3.9—the zero/nonzero support structure of the labelling—is doing all the work in Lemma 3.10 and in the query algorithms, but its proof is a few sentences asserting connectivity rather than a demonstration. If the true support is any larger or smaller than the paths-to-root, every query result changes. The paper never shows that the induced subgraph on the subtree of v is connected in the original graph (as opposed to the filled graph). I believe the claim is likely true, but it is not proven, and it is the linchpin.\n\nSecond, Lemma 4.4 is simply false as stated: a processed neighbor of v_i can be a grandchild, not only a child—a 3-cycle is a counterexample. The algorithm's while loop probably still works under the weaker 'ancestor' property, but the lemma needs to be corrected and the complexity proof re-examined.\n\nThird, the pseudocode has a garbled variable (v_w on line 8 should be w), and the experimental 'ground truth' on large graphs is TreeIndex itself, which is self-referential; the small-graph validation mitigates this but should be stated more transparently.\n\nBottom line: the gaps are in the proof, not in the core idea. The paper is for the graph-data-management audience and anyone who needs exact resistance distance on road-scale networks. It deserves a serious referee and, after the structural lemmas are tightened, likely acceptance. Send it out.","headline":"TreeIndex is the first exact tree-decomposition labelling for resistance distance and shows dramatic speedups on road networks, but the correctness proof has two real gaps (Lemma 3.9's support claim and a false Lemma 4.4) that are fixable rather than fatal.","tokens_in":35688,"tokens_out":15966,"would_cite":true,"duration_ms":153695,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact resistance distance becomes a tree-path sum.","keywords":["resistance distance","tree decomposition","graph labelling","Laplacian","effective resistance","small treewidth","road networks","exact queries"],"falsifier":"Take a small graph (4-8 nodes), compute the full pseudo-inverse of its Laplacian directly with exact arithmetic, build the MDE tree decomposition and the TreeIndex labels, then check every pair (v,u) to see whether S[v,u]=0 matches the ancestor relation in the tree. A single mismatch on a pair along a root path breaks the claim.","tokens_in":34773,"feed_emoji":"⚡","tokens_out":3725,"duration_ms":34376,"temperature":0.7,"pith_summary":"The paper claims that resistance distance—a graph metric that accounts for all paths, not just the shortest—can be computed exactly by storing a small label per vertex derived from a tree decomposition. The central identity expresses r(s,t) as a sum of squared label ratios along the paths from s and t to the root of the decomposition. If true, this reduces single-pair query time to O(tree height) and enables exact single-source queries in O(n·tree height), making resistance distance practical on road networks with millions of nodes. The paper backs this with a construction algorithm that builds the labels in O(n·h²·d_max) time using rank-1 updates, and reports experiments where queries on the full USA road network take about 10⁻³ seconds.","feed_headline":"Exact resistance distance becomes a tree-path sum","feed_subtitle":"A labelling along tree-decomposition paths answers exact queries on the full USA road network in milliseconds.","key_machinery":"The resistance distance labelling S[v,u], defined as the u-th element of the v-th column of the inverse Laplacian submatrix L⁻¹_UU at the moment vertex v is eliminated in the MDE tree decomposition. The key identity is Lemma 3.10: the three-term sum above. The mechanism is Gaussian elimination on the inverse Laplacian, which decomposes it into rank-1 outer products indexed by elimination order; the tree decomposition's vertex hierarchy guarantees the labelling's support matches root paths, so only O(tree height) labels per query are needed.","core_discovery":"The core claim is that in a minimum-degree-elimination (MDE) tree decomposition, the resistance distance r(s,t) equals a sum over labels along the paths from s and t to the root: r(s,t) = Σ_{v∈P_s\\LCA} (S[v,s])²/S[v,v] + Σ_{v∈P_t\\LCA} (S[v,t])²/S[v,v] + Σ_{v∈P_{LCA→root}} (S[v,s]-S[v,t])²/S[v,v]. This follows from expanding the pseudo-inverse of the Laplacian as a sum of rank-1 outer products (inverse Cholesky), and observing, via the cut property of resistance distance, that the labelling S[v,u] is non-zero precisely when v is an ancestor of u in the decomposition tree. Consequently, only labels along the two root paths and the LCA-to-root path are needed, which is what makes compact labell","pith_inferences":["The dependency property likely extends beyond MDE decompositions to any elimination ordering that yields a tree decomposition with the vertex hierarchy property; if so, the method could be paired with balanced decompositions to reduce label size on non-road graphs.","The support conjecture (Lemma 3.9) is the fragile point: if the MDE process can disconnect a subtree before elimination, the formula silently drops terms and returns the wrong resistance; a small counterexample or proof patch would settle it.","The same rank-1/labelling logic might transfer to other matrix functions of the Laplacian (hitting times, currents), possibly yielding similar tree-path formulas.","The reported exactness relies on floating-point arithmetic in practice; the paper's own precision analysis bounds errors below 10⁻¹¹ on tested graphs, but adversarial or ill-conditioned graphs could amplify this."],"forward_implications":["If true, exact single-pair resistance distance queries on small-treewidth graphs (road networks) become O(tree height), comparable to shortest-path labelling methods.","Single-source exact queries become O(n·tree height), enabling applications like electrical-flow-based robust routing on country-scale road networks.","Index construction time O(n·h²·d_max) is practical for graphs where h and d_max are small constants, with a reported 7-hour build for a 24-million-node graph.","The labelling size O(n·h) is large but loadable in memory on commodity servers (405 GB for Full-USA).","Existing random-walk approximate methods become unnecessary for such graphs; exact answers are reported faster than approximations."],"supporting_citations":[{"why":"Supplies the L⁻¹_v formulation of resistance distance and the random-walk interpretation used in the cut-property proof.","marker":"[48]"},{"why":"The Schur-complement theorem (Theorem 2.1) that the cut property generalizes; also the index-based method TreeIndex competes against.","marker":"[49]"},{"why":"H2H's tree-decomposition hierarchy (vertex hierarchy, LCA-based queries) is the structural model for the labelling.","marker":"[54]"},{"why":"MDE (minimum degree elimination) tree decomposition heuristic and its vertex hierarchy property that the labelling relies on.","marker":"[13]"},{"why":"Gaussian elimination / Cholesky decomposition of the inverse Laplacian, the mechanism behind the rank-1 updates and the cut property.","marker":"[35]"}],"fun_headline_variants":["Exact resistance distance from tree-path labels","Tree labelling makes exact resistance distance fast","Exact queries on USA road network in milliseconds","TreeIndex: exact resistance distance via labelling"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The labelling entries are non-zero exactly when one vertex is an ancestor of the other in the decomposition tree; if that fails—extra non-zeros or missing path entries—the query sums no longer equal the true resistance distance.","fun_headline_variants_meta":{"raw":{"variants":["Exact resistance distance from tree-path labels","Tree labelling makes exact resistance distance fast","Exact queries on USA road network in milliseconds","TreeIndex: exact resistance distance via labelling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000483,"raw_usage":{"total_tokens":2302,"prompt_tokens":906,"completion_tokens":1396,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":650,"completion_tokens_details":{"reasoning_tokens":1353}},"tokens_in":650,"tokens_out":1396,"duration_ms":11053,"temperature":1.0,"reasoning_tokens":1353,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:35:18.616249+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small graph (4-8 nodes), compute the full pseudo-inverse of its Laplacian directly with exact arithmetic, build the MDE tree decomposition and the TreeIndex labels, then check every pair (v,u) to see whether S[v,u]=0 matches the ancestor relation in the tree. A single mismatch on a pair along a root path breaks the claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the L⁻¹_v formulation of resistance distance and the random-walk interpretation used in the cut-property proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Schur-complement theorem (Theorem 2.1) that the cut property generalizes; also the index-based method TreeIndex competes against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"H2H's tree-decomposition hierarchy (vertex hierarchy, LCA-based queries) is the structural model for the labelling."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"MDE (minimum degree elimination) tree decomposition heuristic and its vertex hierarchy property that the labelling relies on."}],"review_version":1}