GFQL polars chain: undirected bounded varlen (-[:T*1..k]-) silently diverges from pandas — missing backtrack avoidance includes the seed

[lmeyerov]

Summary

On master (c355660), the native polars chain executes undirected bounded variable-length hops (`-[:KNOWS*1..2]-`) natively but with wrong results: it includes nodes reachable only by immediately re-traversing the same undirected edge (seed bounce-back), which pandas (the parity oracle) correctly excludes via relationship-uniqueness (trail) semantics. This violates the parity-or-honest-NIE contract — the shape should either match pandas or decline.

Repro (master c355660, polars 1.42)

import polars as pl, graphistry
nodes = pl.DataFrame({"id": [f"p{i}" for i in range(6)], "label__Person": [True]*6})
edges = pl.DataFrame({"s": ["p0","p1","p2","p0","p3"], "d": ["p1","p2","p3","p4","p5"], "type": ["KNOWS"]*5})
g  = graphistry.nodes(nodes, "id").edges(edges, "s", "d")
gp = graphistry.nodes(nodes.to_pandas(), "id").edges(edges.to_pandas(), "s", "d")
q = "MATCH (p:Person {id: 'p0'})-[:KNOWS*1..2]-(f:Person) RETURN f.id AS fid ORDER BY fid"
print(gp.gfql(q, engine="pandas")._nodes.to_dict("records"))
# [{'fid': 'p1'}, {'fid': 'p2'}, {'fid': 'p4'}]
print(g.gfql(q, engine="polars")._nodes.to_pandas().to_dict("records"))
# [{'fid': 'p0'}, {'fid': 'p1'}, {'fid': 'p2'}, {'fid': 'p4'}]   <-- p0 = seed via edge backtrack

The path p0-[e]-p1-[same e]-p0 reuses one undirected edge, so p0 must not appear at *1..2 (pandas agrees; Cypher trail semantics).

Impact

• LDBC IC6/IC11 shapes (`-[:KNOWS*1..2]-`) — the official texts currently decline later at the rows op, so benchmark numbers are honest NIE, but any user query of the bare shape returns silently wrong rows on engine="polars"/"polars-gpu".
• The undirected multihop path is marked native in `_is_native_multihop` (lazy/engine/polars/chain.py); the forward re-exec recompute does not exclude same-edge backtracking for undirected traversal.

Fix directions

Either port pandas' backtrack-avoidance to the polars undirected multihop recompute, or narrow `_is_native_multihop` to decline undirected bounded varlen until ported (honest NIE). Differential fuzz over undirected varlen shapes should gate the port.

Found while probing IC6/IC11 coverage for the GFQL benchmark campaign (plans/gfql-benchmark-numbers/plan.md).

[lmeyerov]

Root cause narrowed (probe on c355660): the final node SETS agree between engines — the divergence is the named-alias flag on nodes following an undirected varlen edge. With [n({'id':'p0'}), e_undirected(min_hops=1, max_hops=2), n(name='f')]:

• pandas: p0 → f=False (seed reachable only by same-edge bounce-back is not a valid *1..2 endpoint)
• polars: p0 → f=True

Cypher's RETURN f.id projects the flag, hence the wrong extra row. Also: polars NIEs label_node_hops on undirected varlen (pandas supports it) — that's the existing honest decline; the named path slips through with wrong flags.

Interim integrity fix (PR incoming): decline (NotImplementedError) undirected non-single-hop edges in chains that carry node aliases, until the backtrack-avoidance port lands. The real port remains the IC6/IC11 unlock tracked in plans/gfql-benchmark-numbers.

[lmeyerov]

Corrected root cause (supersedes my earlier comment)

My earlier comment on this issue attributed the bug to "missing backtrack avoidance". That is wrong and I've corrected it in PR #1742's thread and in the campaign plan. Actual finding:

• pandas and polars produce identical hop wavefronts and identical final _nodes for -[:KNOWS*1..2]- from a seed — both include the seed reached by bouncing back over one edge. Neither implements trail semantics in the traversal.
• The divergence is purely the node-alias flag. pandas gates it with a hop-distance mask (compute/chain.py ~452-503): for a named node preceded by an edge op, label_mask &= hop_col >= min_hop & hop_col <= max_hop. The seed is hop 0, fails >= 1, loses the alias.
• The polars _apply_node_names has no hop gating, so every wavefront node keeps the alias.

Real fix = emit label_node_hops for undirected bounded varlen in the polars hop (the layered BFS already knows the distance per layer), then port the gate — which also closes an existing polars NIE for hop labels. Filed here so the next person doesn't re-derive it.

[lmeyerov]

Fix is up: #1746 (native label_node_hops in the polars hop) + #1747 (the hop-distance alias gate, stacked on it). The repro matches pandas now — {p1, p2} on both engines.

Note the root cause in the original write-up was wrong: it is not missing backtrack avoidance. Both engines return identical node sets and identical final _nodes; only the alias flag diverged. pandas gates aliases by hop distance (chain.py:456-501) and polars had no hop labels to gate on.

Residual gap kept on this issue: min_hops > 1 chains get no gate, because requesting labels there would turn a currently-native chain into an NIE (those labels come from the layered backward walk, hop.py:676-778, not yet ported).