Memory Graph Traversal

Breadth-First Search (BFS) is a traversal algorithm that explores a graph level by level. Starting from a root node, it visits all neighboring nodes at the present depth before moving to nodes at the next depth level. This is ideal for finding the shortest path in an unweighted graph or discovering all nodes within a certain relationship distance.

• Mechanism: Uses a queue data structure (First-In-First-Out).
• Agentic Use Case: An agent exploring a knowledge graph of company documents to find all direct connections (e.g., 'reports to', 'works with') of a person before looking at their secondary connections.
• Key Property: Guarantees the shortest path in terms of the number of edges.

Depth-First Search (DFS) is a traversal algorithm that explores a graph by moving as far as possible along each branch before backtracking. It prioritizes exploring a single path to its conclusion, which is useful for exploring deep relationship chains or checking for the existence of a path.

• Mechanism: Uses a stack data structure (Last-In-First-Out), often implemented via recursion.
• Agentic Use Case: An agent traversing a taxonomy or ontology to understand a deep hierarchical chain (e.g., Product -> Category -> Department -> Division) to fully comprehend a concept's lineage.
• Key Property: Memory efficient for deep graphs but does not guarantee the shortest path.

Dijkstra's Algorithm is a pathfinding algorithm that finds the shortest paths between nodes in a graph with non-negative edge weights. It is fundamental for navigating graphs where relationships have associated costs, distances, or confidence scores.

• Mechanism: Uses a priority queue to greedily select the node with the smallest known distance from the source.
• Agentic Use Case: An agent planning a sequence of API calls or tool uses where each 'edge' has a latency or monetary cost, aiming to find the most efficient execution path.
• Key Distinction: Operates on weighted graphs, unlike BFS. Variants like A Search* use heuristics to improve performance for single-target search.

A Random Walk is a stochastic traversal process where the next node is chosen randomly from the current node's neighbors. This technique is less deterministic but powerful for sampling large graphs and discovering serendipitous connections.

• Mechanism: At each step, selects a neighboring edge uniformly at random or based on edge weights (biased random walk).
• Agentic Use Case: Used in graph embedding algorithms like Node2Vec to generate node sequences for training. An agent could use it for exploratory memory retrieval, potentially discovering novel, non-obvious relationships between entities.
• Key Property: Useful for approximate computation and generating training data for machine learning on graphs.

Bidirectional Search is an optimization technique that runs two simultaneous searches: one forward from the initial node and one backward from the goal node. The search terminates when the two frontiers meet. This dramatically reduces the search space for pathfinding in large graphs.

• Mechanism: Typically implements two BFS or Dijkstra searches concurrently.
• Agentic Use Case: An agent trying to find a connection between two distant entities in a massive enterprise knowledge graph (e.g., 'How is Project Alpha related to Vendor Beta?'). Starting from both ends makes the search feasible.
• Performance: Can reduce time complexity from O(b^d) to O(b^{d/2}) for a branching factor b and depth d.

In Retrieval-Augmented Generation (RAG), graph traversal moves beyond simple vector similarity. It enables multi-hop reasoning where an agent retrieves a set of relevant nodes and then traverses their relationships to gather connected context, leading to more precise and explainable answers.

• Process: 1. Retrieve seed nodes via vector search. 2. Traverse connected nodes (e.g., 1-2 hops) via relationships. 3. Aggregate context from this subgraph for the LLM.
• Example: Query: 'What projects did the manager of the developer who built the authentication service work on?'
  • Step 1 (Vector): Find node for 'authentication service'.
  • Step 2 (Traverse): Follow 'built_by' to developer, then 'reports_to' to manager.
  • Step 3 (Traverse): Follow 'manages' to project nodes.
• Benefit: Provides chain-of-thought evidence directly from the knowledge structure.

A Knowledge Graph is a structured semantic network that represents real-world entities (nodes) and their interrelationships (edges) using a formal ontology. It is the primary data structure traversed during memory graph traversal.

• Nodes represent entities like people, places, events, or concepts.
• Edges define the typed relationships between them (e.g., worksFor, locatedIn, causedBy).
• Properties are key-value pairs attached to nodes or edges, storing attributes.

This structured format enables deterministic, logic-based querying (e.g., via SPARQL or Cypher) and complex relational reasoning that complements vector-based semantic search.

A Graph Query Language is a domain-specific language used to declaratively read and manipulate graph-structured data. It provides the syntax for specifying traversal patterns.

• Cypher (Neo4j): Uses an intuitive ASCII-art pattern matching syntax (e.g., (a:Person)-[:WORKS_AT]->(b:Company)).
• SPARQL: The W3C standard for querying RDF knowledge graphs, using triple patterns.
• Gremlin (Apache TinkerPop): An imperative, step-based traversal language for property graphs.

These languages allow an agent to programmatically navigate paths, filter nodes by properties, and aggregate results during memory retrieval.

A Graph Neural Network is a class of deep learning models designed to perform inference on graph-structured data. GNNs learn by propagating and transforming node, edge, and graph-level information through neural message-passing layers.

• Message Passing: Nodes aggregate feature vectors from their neighbors to update their own representation.
• Use in Memory: GNNs can be used to learn embeddings for graph nodes that encode both their features and topological context, enabling semantic similarity search within the graph.
• Reasoning: They can perform predictive tasks on the graph, such as inferring missing relationships (link prediction) or classifying nodes, which enhances an agent's ability to reason during traversal.

A Pathfinding Algorithm is a graph algorithm that finds the optimal or shortest sequence of edges (a path) between two or more nodes in a graph. It is a fundamental subroutine for goal-directed memory traversal.

• Breadth-First Search (BFS): Explores all neighbors at the present depth before moving deeper. Ideal for finding the shortest path in unweighted graphs.
• Dijkstra's Algorithm: Finds the shortest path in weighted graphs with non-negative edge weights.
• A Search*: Uses a heuristic to guide search towards the goal, optimizing performance for known graph structures.

Agents use these algorithms to discover causal chains, narrative sequences, or dependency links stored in memory.

A Graph Traversal Algorithm systematically explores the nodes and edges of a graph. Unlike pathfinding, traversal may aim to visit all reachable nodes or discover the graph's structure, not just find a single path.

• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Useful for exploring deep causal chains or hierarchical structures.
• Breadth-First Search (BFS): Explores all nodes at the present depth level before moving deeper. Effective for exploring local neighborhoods.
• Random Walk: A stochastic traversal that selects the next node at random, useful for sampling or discovering latent community structures in memory.

These algorithms underpin an agent's ability to explore its memory space for relevant context or novel connections.

Hybrid Search is a retrieval strategy that combines multiple search techniques to improve recall and precision. In memory systems, this most commonly refers to the fusion of graph-based traversal with vector similarity search.

• Graph for Structure: Executes a precise Cypher query to find entities connected by specific relationship types (e.g., all Product nodes manufactured by SupplierX).
• Vector for Semantics: Performs a nearest-neighbor search in embedding space to find nodes with similar semantic meaning to a natural language query.
• Fusion: Results are combined via techniques like reciprocal rank fusion (RRF) or weighted scoring, allowing an agent to retrieve information that is both relationally correct and semantically relevant.