{"id":"72ac748a-59ce-425a-93d5-4ce5332774f8","arxiv_id":"2607.07934","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Two relational structures are indistinguishable by k-RCR if and only if they receive identical homomorphism counts from every structure of generalised hypertreewidth ≤ k.","lead":"The paper defines k-RCR, a relational colour-refinement algorithm whose distinguishing power exactly matches homomorphism counts from structures of generalised hypertreewidth at most k. It also gives a direct HyperOWL algorithm that realises the same power and supports constructive homomorphism counting on higher-arity structures.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claim (Theorem 1.2) rests on two directions. Direction (1)⇒(2) reduces to the pure case via the print construction and is covered by the classical 1-WL characterisation of Dell–Grohe–Rattan. Direction (2)⇒(1) is proved by contraposition: k-RCR equivalence implies equal homomorphism counts from every connected structure of GHW ≤ k. The only non-routine step is the handling of ε-entries that appear when bags are not pure. The paper partitions Hom(A_D,B(B,k)) into exactly #Hom(A,B) classes of D-extensions (Lemma 3.14) and then builds an explicit bijection between the unique natural representatives by matching colour-class indices along a BFS traversal of the decomposition tree (Lemma 3.17). The construction preserves both unary profiles and the binary equality patterns that encode bag intersections; the two short claims that verify this preservation are local and self-contained. The same pattern is repeated, with only notational changes, for the fractional variant. Because the full manuscript supplies every intermediate claim and the techniques stay inside standard finite-model theory, the equivalence stands. The reader's identification of the non-pure case as the weakest link is accurate, yet that link holds under the stated hypotheses. No adjustment of the ACCEPT verdict is warranted.","tokens_in":60482,"tokens_out":598,"duration_ms":6522,"concrete_test":"Independently re-derive the injectivity of the map π constructed in the last two paragraphs of Lemma 3.17 (the two cases u = r and u ≠ r) without appealing to the multiset equality of colour multiplicities; if the same contradiction is obtained solely from the definition of natural D-extensions and the BFS order, the bijection is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly flags the non-pure case (Lemma 3.14 + BFS construction of Lemma 3.17) as the most delicate step, but the manuscript already resolves it. Full GHDs are obtained without increasing width (Remark 2.4). Natural D-extensions exist and are unique for structures without isolated elements (Lemma 3.13 + uniqueness argument after Claim 3.16). The BFS matching of colour-class indices preserves both the profile predicates and the equality patterns stp (Claims 3.18–3.19), so the induced map on natural extensions is a bijection. Consequently #Hom(A,B) = #Hom(A,B') whenever A ≡_k-RCR B'. The pure direction is handled separately by the exact equality of Lemma 3.20 and the print construction of Lemma 3.22. No hidden inconsistency appears in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces k-RCR, a k-dimensional relational colour-refinement algorithm on multi-coloured tuples, and proves that two σ-structures are k-RCR-indistinguishable if and only if they admit the same homomorphism counts from all connected structures of generalised hypertreewidth at most k (Theorem 1.2). An analogous characterisation is obtained for a fractional variant (k-frac-RCR) with respect to semi-pure fractional hypertreewidth (Theorem 1.3). The proofs reduce both algorithms to ordinary 1-WL on carefully defined k-exploded binary encodings, invoke the known tree characterisation of 1-WL, and lift the counts back via pure and non-pure (full) generalised/fractional hypertree decompositions. A third algorithm, k-HyperOWL, is defined that works directly on k-coverable rk-tuples of the input structure; it is shown to be at least as expressive as k-RCR, to run in time O(t |A|^{k+1}), and to yield a constructive dynamic-programming routine for counting homomorphisms from structures of GHW ≤ k.","tokens_in":60754,"tokens_out":728,"duration_ms":6952,"significance":"The work cleanly closes the open problem posed by Scheidt for all k ≥ 1 and supplies the first direct relational WL algorithm that does not route through a rank-2 encoding. The equivalences link an algorithmic width measure (GHW / fractional hypertreewidth) that is central to CSP and database theory with a colour-refinement procedure, thereby generalising the Dell–Grohe–Rattan theorem beyond graphs. The HyperOWL colouring further yields a practical preprocessing step for homomorphism counting that extends the recent Lanzinger–Barceló result from arity 2 to arbitrary rank. The technical development is self-contained, the reductions are explicit, and the running-time bound is tight enough for algorithmic use.","major_comments":[],"minor_comments":[{"comment":"Several typographical slips appear in the abstract and introduction (“insdistinguishable”, “hypertreewdith”, “indistinguishabily”). A global spell-check would remove them.","section":null},{"comment":"Definition 1.8 / 3.4: the multiset notation {{·}} is used both for ordinary multisets and for the colour-update rule; a short clarifying sentence would help readers unfamiliar with the Scheidt–Schweikardt convention.","section":null},{"comment":"Lemma 5.10: the factor (rk)^{rk} is written without parentheses in one place; the asymptotic claim is clear but the typesetting should be uniform.","section":null},{"comment":"The relationship between pure, semi-pure and ordinary fractional hypertreewidth is stated correctly, yet a one-sentence remark on whether the semi-pure restriction is known to be without loss of generality for the homomorphism-counting problem would be welcome.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is long and technically dense; the journal may wish to ask the authors whether an extended abstract plus a full arXiv version would better serve the readership. No other editorial concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper finishes the job Scheidt posed: a natural k-dimensional relational colour refinement whose power is exactly homomorphism indistinguishability from structures of generalised hypertreewidth ≤ k. They also give the fractional analogue (semi-pure FHW) and, more usefully for algorithms, HyperOWL that works directly on the relational structure rather than an exploded graph encoding.\n\nWhat is new is not just the k > 1 lift. The non-pure bags force a genuine technical detour: they partition Hom(A_D, B(B,k)) into #Hom(A,B) many D-extension classes and then build a BFS matching of colour-class indices that preserves profiles and equality patterns. That construction (Lemmas 3.14 and 3.17) is the load-bearing step; the pure direction is cleaner via the exact equality of Lemma 3.20. HyperOWL is the first algorithm that stays on k-coverable rk-tuples, runs in O(t |A|^{k+1}), and immediately yields a constructive counting routine that generalises Lanzinger–Barceló from arity 2. The reduction to 1-WL on the exploded encodings is clean and re-uses Dell–Grohe–Rattan correctly.\n\nSoft spots are minor. The fractional result is only for semi-pure FHW, which they flag. HyperOWL is shown ≥ k-RCR, not necessarily equal, but that is enough for the counting application. The manuscript is long and dense; a referee will want the non-pure matching written even more carefully, but the stress-test note is right that the argument already closes the gap (full GHDs free of charge, natural extensions unique without isolates, stp preserved). Citations are appropriate; self-cites are black-box algorithmic results.\n\nThis is for people who care about homomorphism indistinguishability, hypertreewidth algorithms, or higher-arity GNN expressivity. The math is standard finite-model / decomposition machinery done carefully; no free parameters, no circularity. I would send it to peer review and would cite the equivalences and HyperOWL myself.","headline":"They close Scheidt's open problem for every k and ship a direct HyperOWL that also gives constructive GHW-k counting; the non-pure case is handled carefully and the proofs look solid.","tokens_in":61381,"tokens_out":558,"would_cite":true,"duration_ms":8798,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68R10","05C60","03B70"],"pacs":[],"model":"grok-4.5","headline":"Two relational structures are k-RCR-indistinguishable exactly when they agree on all homomorphism counts from structures of generalised hypertreewidth at most k.","keywords":["Weisfeiler-Leman","homomorphism indistinguishability","generalised hypertreewidth","relational colour refinement","HyperOWL","fractional hypertreewidth","relational structures"],"falsifier":"Exhibit a concrete pair of small-signature structures that receive identical stable k-RCR colour multiplicities yet differ by at least one homomorphism count from a connected structure whose generalised hypertreewidth is known to be exactly k (or vice versa).","tokens_in":61395,"feed_emoji":"🔄","tokens_out":981,"duration_ms":26820,"temperature":0.7,"pith_summary":"The paper lifts the classic equivalence between the k-dimensional Weisfeiler–Leman algorithm and homomorphism counts from treewidth-k graphs to the setting of higher-arity relational structures. It defines k-RCR, a natural colour-refinement procedure on multi-coloured tuples of length at most k, and proves that two structures are distinguished by k-RCR if and only if some connected structure of generalised hypertreewidth ≤ k has different homomorphism numbers into them. A fractional analogue does the same for a pure variant of fractional hypertreewidth. The authors also introduce k-HyperOWL, the first WL-style algorithm that works directly on the relational structure (without first reducing to a binary graph), runs in time linear in |A|^{k+1} per iteration, matches the distinguishing power of k-RCR, and yields a constructive counting algorithm for homomorphisms from any GHW-≤k source. The result matters because generalised hypertreewidth is the central tractability parameter for constraint satisfaction and database query evaluation; the paper therefore supplies a uniform combinatorial, logical and algorithmic dictionary between colour refinement, width measures and counting for arbitrary-arity data.","feed_headline":"Relational WL matches GHW homomorphism counts for all k","feed_subtitle":"A direct algorithm on higher-arity structures also counts the homomorphisms themselves","key_machinery":"k-RCR together with the binary structures induced by generalised hypertree decompositions (and the associated k-exploded encodings). These binary structures translate both the colour-refinement process and the homomorphism counts into ordinary 1-WL and tree-homomorphism counts, so the classical Dell–Grohe–Rattan theorem applies.","core_discovery":"For every fixed signature and every k ≥ 1, two structures are indistinguishable by the k-dimensional relational colour-refinement algorithm if and only if they receive the same number of homomorphisms from every connected structure of generalised hypertreewidth at most k. The same equivalence holds for a fractional version of the algorithm with respect to pure fractional hypertreewidth.","pith_inferences":["The direct HyperOWL colouring suggests a natural higher-arity message-passing architecture whose expressivity is governed by generalised hypertreewidth rather than Gaifman-treewidth.","The equivalence supplies a concrete route to a counting-logic characterisation of GHW-bounded formulas, analogous to the known C^{k+1} characterisation of ordinary k-WL.","The same technique may yield analogous equivalences for other covering-based width measures (e.g., fractional edge-cover width of the whole structure) once suitable “pure” or “semi-pure” restrictions are identified."],"forward_implications":["The stable colouring of k-HyperOWL can be used as a preprocessing step that reduces homomorphism counting from any GHW-≤k source to a simple sum over colour classes.","k-HyperOWL itself runs in O(t·|A|^{k+1}) time and is at least as expressive as k-RCR, giving a practical direct algorithm on relational data.","The same correspondence holds for the fractional variant with pure fractional hypertreewidth, linking colour refinement to the current frontier of polynomial-time CSP algorithms.","Any future logical or machine-learning characterisation of k-RCR automatically inherits an exact characterisation in terms of GHW-bounded homomorphism counts."],"fun_headline_variants":["k-RCR matches GHW ≤k homomorphism counts for all k","Relational colour refinement equals GHW-k hom indistinguishability","k-HyperOWL runs in O(n^{k+1}) and matches k-RCR expressiveness","Fractional k-RCR characterises pure fractional hypertreewidth homs","From graphs to relations: WL now meets generalised hypertreewidth"],"cache_read_input_tokens":49280,"weakest_assumption_plain":"The bijection between natural extensions of homomorphisms continues to hold for non-pure decompositions even after dummy symbols mark elements that are covered by a bag but lie outside it.","fun_headline_variants_meta":{"raw":{"variants":["k-RCR matches GHW ≤k homomorphism counts for all k","Relational colour refinement equals GHW-k hom indistinguishability","k-HyperOWL runs in O(n^{k+1}) and matches k-RCR expressiveness","Fractional k-RCR characterises pure fractional hypertreewidth homs","From graphs to relations: WL now meets generalised hypertreewidth"]},"model":"grok-4.5","effort":"low","cost_usd":0.00553,"raw_usage":{"total_tokens":1607,"prompt_tokens":932,"num_sources_used":0,"completion_tokens":102,"cost_in_usd_ticks":55300000,"prompt_tokens_details":{"text_tokens":932,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":573,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":932,"tokens_out":102,"duration_ms":5347,"temperature":1.0,"reasoning_tokens":573,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T15:08:19.899018+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a concrete pair of small-signature structures that receive identical stable k-RCR colour multiplicities yet differ by at least one homomorphism count from a connected structure whose generalised hypertreewidth is known to be exactly k (or vice versa).","supporting_citations":[],"review_version":1}