What is graph traversal?
Graph traversal follows the relationships in a graph index, starting from the entities named in a question and moving outward along defined edges. It reaches material that is connected to the question without resembling it, such as the owner of a policy or the systems a process depends upon. The traversal is deterministic, so the same question over the same graph follows the same path.
Also called: Graph walk
Why some answers are reached by connection and not by similarity
Questions that span several documents cannot be answered by any single retrieved passage. The link between a regulation and the internal team accountable for implementing it exists only as a chain of references across several documents. Traversal follows that chain explicitly and returns each step with its source. Because the path is recorded, a reviewer can see exactly how the system moved from the question to the answer.
- Multi-document questions are common in enterprise work and fail under similarity search.
- A recorded path makes the reasoning behind an answer inspectable.
- Traversal is deterministic and needs no model call at each step.
- Edge permissions stop the walk at material the user may not read.
How graph traversal works
- Entities extracted from the question are matched to starting nodes in the graph.
- The traversal follows permitted edge types out to a defined number of steps.
- Each node reached is checked against the access rights of the requesting user.
- Passages attached to the reached nodes are collected as candidates.
- Candidates are combined with similarity results and passed to reranking.
- The path taken is stored with the answer as part of its evidence.
How graph traversal is evaluated
Graph traversal is evaluated on relationship questions where the correct path is known in advance. Compare its results with that path:
- share of questions where the traversal reached the correct node
- unnecessary nodes collected along the way
- questions where a permission check correctly stopped the walk
- accuracy of final answers with and without traversal results
- latency of traversal at the configured depth
Limitations, risks and common failure modes
- A traversal allowed too many steps returns most of the graph.
- A missing edge ends the path before it reaches the answer.
- Highly connected nodes such as a common department flood the candidate set.
- Errors in the graph are followed faithfully and presented as evidence.