Traversal-Based Search

Topics

• Overview
• Example
• Enable chunk indexes(#enable-chunk-indexes)
• Basic concepts
  • Connectivity types
  • Entity network contexts
• Retrievers
• Search results

Overview

The recommended method for query and retrieval is to used the traversal-based search operation. While the lexical-graph does include support for semantic-guided search, this alternative approach has several significant drawbacks:

• High storage costs due to requiring an embedding for each statement
• Poor performance with large datasets, with queries often taking minutes to complete
• Expected to be removed in future releases

For optimal results, users should use traversal-based search in their applications.

Traversal-based search can be used in two ways: retrieval and querying. When you perform a retrieval operation, the system searches the graph and vector stores to find the most relevant information related to your query. It then returns these raw search results directly to you. With a query operation, the system takes an extra step. After finding the relevant information, it passes these results to a Large Language Model (LLM). The LLM processes this information and generates a natural language response that answers your query.

Enable chunk indexes

Traversal-based search requires chunk-level vector indexes. By default, the VectorStoreFactory will enable both a statement index and a chunk index. If you plan to only use traversal-based search in your application (recommended), then you should disable the creation of statement indexes, thereby saving storage space and embedding costs. Use the index_names argument to enable just the chunk index. The examples throughout this documentation explicitly configure only the chunk index using the index_names argument.

Example

The following example performs a traversal-based search using the default settings:

from graphrag_toolkit.lexical_graph import LexicalGraphQueryEngine
from graphrag_toolkit.lexical_graph.storage import GraphStoreFactory
from graphrag_toolkit.lexical_graph.storage import VectorStoreFactory

with (
    GraphStoreFactory.for_graph_store(
        'neptune-db://my-graph.cluster-abcdefghijkl.us-east-1.neptune.amazonaws.com'
    ) as graph_store,
    VectorStoreFactory.for_vector_store(
        'aoss://https://abcdefghijkl.us-east-1.aoss.amazonaws.com',
        index_names=['chunk']
    ) as vector_store
):

    query_engine = LexicalGraphQueryEngine.for_traversal_based_search(
        graph_store,
        vector_store,
        streaming=True
    )

    response = query_engine.query("What are the differences between Neptune Database and Neptune Analytics?")

print(response.print_response_stream())

The parameters used to configure traversal-based search are described in Traversal-Based Search Configuration.

Basic concepts

Traversal-based search is a method that employs one or more retrievers to locate information within a lexical graph. This approach leverages two key features of the lexical graph structure: connectivity (both local and global) and entity network contexts.

Connectivity types

The lexical graph provides both local and global connectivity:

• Local Connectivity Local connectivity enables traversal within a localized network, typically within a single source. This is primarily facilitated by topics, which connect relevant chunks of information within the same source material.
• Global Connectivity Global connectivity allows navigation to related components that may be more distant in the graph structure. This is achieved through facts, which create connections across different sources.

Different retrievers emphasize these connectivity types in varying ways:

• The ChunkBasedSearch retriever primarily utilizes local connectivity
• The EntityBasedSearch retriever focuses more on global connectivity
  • The EntityNetworkSearch retriever balances local and global connectivity

Entity network contexts

An entity network context consists of a filtered and ranked network of entities that relate to search terms found in the user’s query. These contexts serve multiple important functions:

• Search Initialization Provides starting points for entity-based searches in the EntityBasedSearch retriever
• Similarity Searching Entity network transcriptions – textual representations of the entity network contexts – help find content that differs from but relates to the original query in the EntityNetworkSearch retriever
• Reranking Entity network transcriptions can be used to enhance the original search terms when reranking statements in search results
• LLM Integration Entity network transcriptions can also be provided to Large Language Models (LLMs) during query operations to help focus responses on the most relevant search results

Retrievers

Traversal-based search provides four different retrievers:

• The ChunkBasedSearch retriever uses a vector similarity search to find information that is similar to the original query. The retriever first finds relevant chunks using vector similarity search. From these chunks, the retriever traverses topics, statements, and facts. Chunk-based search tends to return a narrowly-scoped set of results based on the statement and fact neighbourhoods of chunks that match the original query.
  • The EntityBasedSearch retriever uses as its starting points the entities in an entity network context. From these entities, the retriever traverses facts, statements and topics. Entity-based search tends to return a broadly-scoped set of results, based on the neighbourhoods of individual entities and the facts that connect entities.
  • The EntityNetworkSearch retriever uses textual transcriptions of an entity network context to drive vector searches for information that is dissimilar to the original query but nonetheless structurally relevant for creating an accurate and full response. These vector searches return chunks that are similar to ‘something different from the question being asked’. From these chunks, the retriever traverses topics, statements, and facts to explore the structurally relevant space of dissimilar content.
  • The TopicBeamSearch retriever starts from the most relevant topics (found by a vector similarity search over the topic index) and then performs a beam search across the topic graph to gather additional related topics, before expanding the winning topics into their statements. Because it is topic-first, it tends to assemble a focused, topic-coherent set of statements and works well on multi-hop, legal, and temporal questions.

By default, the traversal-based search is configured to use a combination of ChunkBasedSearch and EntityNetworkSearch. Together, these two retrievers provide access to content that is similar to the question being asked, plus content that is similar to ‘something different from the question being asked’. TopicBeamSearch is used as a standalone, topic-first alternative.

TopicBeamSearch options

TopicBeamSearch accepts a notable option:

• topic_reranker (default 'none'): optionally reranks the gathered topics by relevance to the query before their statements are collected, keeping the top max_topics. It mirrors the statement reranker option and accepts 'tfidf' or 'bedrock' (Cohere). Topic reranking is an opt-in, per-corpus tuning lever: it can help when answers are concentrated in a few topics, but is not enabled by default.

The beam’s neighbour-edge strategy and other tuning are configured through ProcessorArgs (mirroring the chunk_beam_* parameters), so they can be passed to for_traversal_based_search(...):

• use_same_chunk_neighbors (default True) and use_adjacent_chunk_neighbors (default True): expand the beam to topics co-occurring in the same chunk and in the adjacent (next) chunk. Adjacent-chunk expansion is on by default because it improved accuracy across datasets with no regressions in our benchmarks.
• use_entity_neighbors (default False): expand to topics linked through shared entities. This has a large fan-out and tends to add noise, so it is off by default; when enabled, max_entity_neighbors (default 100) caps the neighbours per topic, ranked by entity-connection strength.
• topic_beam_width (default 100), topic_beam_max_depth (default 6), topic_top_k (default 50): beam breadth, walk depth, and number of seed topics.

Search results

When used with traversal-based search, the retrieve() operation of the LexicalGraphQueryEngine returns a collection of LlamaIndex scored nodes (NodeWithScore). Each node contains a single search result, comprising a source, topic, and a set of statements. For example,

response = query_engine.query("What are the differences between Neptune Database and Neptune Analytics?")

for n in response.source_nodes:
    print(n.text)

– returns the following output:

{
  "source": "https://docs.aws.amazon.com/neptune-analytics/latest/userguide/neptune-analytics-features.html",
  "topic": "Neptune Analytics Features",
  "statements": [
    "Neptune Analytics allows loading graph data from a Neptune Database endpoint.",
    "Neptune Analytics enables running graph analytics queries.",
    "Neptune Analytics allows loading graph data from Amazon S3.",
    "Neptune Analytics supports custom graph queries.",
    "Neptune Analytics supports pre-built graph queries."
  ]
}
{
  ...
}

The metadata property of each node contains a dictionary with a far more detailed breakdown of the search result. This includes the score for each statement, the facts that support each statement, the retrievers used to fetch each statement, and the entity network contexts used in the query. For example,

import json
for n in response.source_nodes:
    print(json.dumps(n.metadata, indent=2))

– returns the following output:

{
  "result": {
    "source": {
      "sourceId": "aws::4510583f:e412",
      "metadata": {
        "url": "https://docs.aws.amazon.com/neptune-analytics/latest/userguide/neptune-analytics-features.html"
      }
    },
    "topics": [
      {
        "topic": "Neptune Analytics Features",
        "topicId": "fbbde2f69acd195da90e578d0f9eeefe",
        "statements": [
          {
            "statementId": "810a8ac6943708e1584662b32431eb67",
            "statement": "Neptune Analytics allows loading graph data from a Neptune Database endpoint.",
            "facts": [
              "Neptune Analytics FEATURE loading graph data",
              "Neptune Analytics SUPPORTS LOADING FROM Neptune Database"
            ],
            "details": "",
            "chunkId": "aws::4510583f:e412:9f69cb6f",
            "score": 0.3187,
            "statement_str": "Neptune Analytics allows loading graph data from a Neptune Database endpoint. (details: Neptune Analytics FEATURE loading graph data, Neptune Analytics SUPPORTS LOADING FROM Neptune Database)",
            "retrievers": [
              "ChunkBasedSearch (3.12.0)"
            ]
          },
          {
            "statementId": "797021c7c33db8674fa0be42a1cdd9a6",
            "statement": "Neptune Analytics enables running graph analytics queries.",
            "facts": [
              "Neptune Analytics FEATURE running graph analytics queries"
            ],
            "details": "",
            "chunkId": "aws::4510583f:e412:9f69cb6f",
            "score": 0.2233,
            "statement_str": "Neptune Analytics enables running graph analytics queries. (details: Neptune Analytics FEATURE running graph analytics queries)",
            "retrievers": [
              "ChunkBasedSearch (3.12.0)"
            ]
          },
          {
            "statementId": "23deac383344021ed50e1c78448408a8",
            "statement": "Neptune Analytics allows loading graph data from Amazon S3.",
            "facts": [
              "Neptune Analytics FEATURE loading graph data",
              "Neptune Analytics SUPPORTS LOADING FROM Amazon S3"
            ],
            "details": "",
            "chunkId": "aws::4510583f:e412:9f69cb6f",
            "score": 0.2197,
            "statement_str": "Neptune Analytics allows loading graph data from Amazon S3. (details: Neptune Analytics FEATURE loading graph data, Neptune Analytics SUPPORTS LOADING FROM Amazon S3)",
            "retrievers": [
              "ChunkBasedSearch (3.12.0)"
            ]
          },
          {
            "statementId": "85a4ea712a9a83fb4ac7f441be72e694",
            "statement": "Neptune Analytics supports custom graph queries.",
            "facts": [
              "Neptune Analytics FEATURE custom graph queries"
            ],
            "details": "",
            "chunkId": "aws::4510583f:e412:9f69cb6f",
            "score": 0.199,
            "statement_str": "Neptune Analytics supports custom graph queries. (details: Neptune Analytics FEATURE custom graph queries)",
            "retrievers": [
              "ChunkBasedSearch (3.12.0)"
            ]
          },
          {
            "statementId": "3a480d6a686748a628009de3cd8238ed",
            "statement": "Neptune Analytics supports pre-built graph queries.",
            "facts": [
              "Neptune Analytics FEATURE pre-built graph queries"
            ],
            "details": "",
            "chunkId": "aws::4510583f:e412:9f69cb6f",
            "score": 0.1857,
            "statement_str": "Neptune Analytics supports pre-built graph queries. (details: Neptune Analytics FEATURE pre-built graph queries)",
            "retrievers": [
              "ChunkBasedSearch (3.12.0)"
            ]
          }
        ]
      }
    ]
  },
  "entity_contexts": {
    "contexts": [
      {
        "entities": [
          {
            "entity": {
              "entityId": "19ad98dc563a3a3c935d93723d3c9029",
              "value": "Neptune Analytics",
              "classification": "Software"
            },
            "score": 37.0,
            "reranking_score": 0.5025
          },
          {
            "entity": {
              "entityId": "ecc28e0aba278f8803bfbc5ae162831a",
              "value": "Neptune",
              "classification": "Software"
            },
            "score": 10.0,
            "reranking_score": 0.0
          }
        ]
      },
      {
        "entities": [
          {
            "entity": {
              "entityId": "51874c430e9cb1f5b09d790049d5380d",
              "value": "Neptune Database",
              "classification": "Software"
            },
            "score": 5.0,
            "reranking_score": 0.5025
          }
        ]
      }
    ]
  }
}
{
  ...
}