[geaflow/graph-algorithms] Implement Graph Traversal Recall Operator

[kitalkuyo-gita]

Priority: P1
Difficulty: Intermediate
Suggested labels: area:ai-memory, type:feature, difficulty:intermediate, phase:graph-memory-p1

Context

Graph Memory Phase 1 supports four retrieval modes (GM-AI-P1-023): Basic, Vector, Graph, Hybrid. The Graph and Hybrid modes require a graph traversal operator that can walk the property graph from anchor entities and discover related candidates through multi-hop associations.

Currently, the only graph traversal capability is the bounded traversal fallback (GM-AI-P1-033), which triggers passively when Text2GQL fails. There is no active traversal operator that proactively walks the graph to find candidates.

This issue implements a Personalized PageRank-style traversal that starts from anchor entities, performs bounded random walks, and returns scored candidates with traversal provenance. It is inspired by Twitter's UTEG (User-Tweet-Entity Graph) random walk with restart, adapted for GeaFlow-AI's property graph model.

Scope

• New GraphTraversalRecall class in geaflow-ai/src/main/java/org/apache/geaflow/ai/retrieval/traversal/
• Accepts anchor entities (from EntityAnchorService, GM-AI-P1-027) and a TraversalBudget (GM-AI-P1-032)
• Performs bounded random walk with restart from each anchor
• Returns List<TraversalHit> with candidate entity, score, and path
• Deterministic scoring (no randomness in tests; use fixed seed)
• Integration with TraversalBudget for hop/result/memory limits

Non-Goals

• This is NOT an ANN algorithm. It traverses the graph structure, not vector space.
• This does NOT implement learned ranking. Scoring is based on visit frequency and edge weights.
• This does NOT generate social proof text. That is Issue 2 (GM-AI-P1-051).
• This does NOT modify the graph. Read-only traversal.

Constraints

C-1: Must use GraphAccessor for graph access

The operator reads the graph through the GraphAccessor interface (or LocalMemoryGraphAccessor in Phase 1). It must not bypass the accessor layer to access MemoryGraph directly.

// Correct: through accessor
Iterator<GraphEdge> edges = accessor.expand(anchorEntity);

// Wrong: direct access
// MemoryGraph mg = ...; mg.entities.get(label);

C-2: Must respect TraversalBudget

Every traversal must check the budget before each step. Budget exhaustion must be reported, not silently ignored.

public class TraversalBudget {
    int maxHops;              // max edges traversed from anchor
    int maxVisitedVertices;   // total unique vertices visited
    int maxVisitedEdges;      // total edges traversed
    int maxResultRows;        // max candidates returned
    long timeoutMillis;       // wall-clock timeout
    boolean cancelled;        // external cancellation flag

    boolean canTraverse();    // returns false if any limit exceeded
    void recordStep();        // increments counters
}

C-3: Must produce deterministic results in tests

Tests must use a fixed random seed and a deterministic graph fixture. The same input must always produce the same output order and scores.

C-4: Must not return the anchor entity itself as a candidate

The traversal starts from anchor entities. The anchor should not appear in its own results (no self-loops in output).

C-5: Must report traversal path for each candidate

Each TraversalHit must include the path taken from anchor to candidate. This path is consumed by Issue 2 (social proof extraction) and by the retrieval trace (GM-AI-P1-046).

Data Structures

public class TraversalHit {
    /** The candidate entity reached by traversal. */
    private final GraphEntity candidate;

    /** Traversal score (higher = more relevant). */
    private final double score;

    /** The path from anchor to candidate. */
    private final List<GraphEdge> path;

    /** The anchor entity this candidate was reached from. */
    private final GraphEntity anchor;

    /** Number of hops from anchor to candidate. */
    private final int hops;

    /** Number of distinct paths that reached this candidate. */
    private final int visitCount;
}

public enum TraversalStrategy {
    RANDOM_WALK_RESTART,    // Personalized PageRank style
    BREADTH_FIRST,          // BFS up to maxHops
    DEPTH_FIRST             // DFS with depth limit
}

Algorithm: Random Walk with Restart

Input:
  - anchor: starting entity
  - budget: TraversalBudget
  - restartProbability: α (default 0.2)
  - maxSteps: N (default 1000)
  - strategy: RANDOM_WALK_RESTART

Output:
  - Map<GraphEntity, TraversalHit> candidates

Process:
  visitCount = Map<GraphEntity, Integer>
  current = anchor

  for i in 1..N:
    if not budget.canTraverse(): break
    budget.recordStep()

    if random() < restartProbability:
      current = anchor  // restart
      continue

    neighbors = expandViaAccessor(current)  // get adjacent entities
    if neighbors.isEmpty(): break

    next = weightedRandomSelect(neighbors, edgeWeights)
    visitCount[next] = visitCount.getOrDefault(next, 0) + 1
    current = next

  // Convert visit counts to scores
  candidates = []
  for (entity, count) in visitCount:
    if entity != anchor:  // exclude self
      score = count / maxSteps  // normalized visit frequency
      path = reconstructPath(entity, anchor)  // shortest path from anchor
      candidates.add(TraversalHit(entity, score, path, anchor, hops, count))

  return candidates sorted by score descending, truncated to budget.maxResultRows

Test Strategy

Test	Scenario	Expected
singleHopDiscovery	Anchor → edge → candidate	Candidate found with hop=1, score>0
twoHopDiscovery	Anchor → A → B → candidate	Candidate found with hop=3
budgetExhaustion	maxHops=1, graph depth=3	Traversal stops at hop=1, budget exhausted reported
selfExclusion	Anchor has self-loop edge	Anchor not in results
deterministicOrdering	Same graph, same seed, run twice	Identical output order and scores
emptyGraph	Anchor with no edges	Empty result list, no exception
multipleAnchors	Two anchors reach same candidate	Candidate appears once, with higher score
visitCountAccuracy	Simple linear graph, trace all paths	visitCount matches expected frequency
timeoutRespected	Large graph, tight timeout	Traversal stops within timeout
pathReconstruction	Anchor → A → B → candidate	Path contains correct edge sequence

Fixture:

geaflow-ai/src/test/resources/traversal/
├── simple-graph.json          // 5 nodes, 6 edges, linear structure
├── branching-graph.json       // anchor with 3 branches, different depths
├── cyclic-graph.json          // graph with cycles, tests restart behavior
└── budget-exhaustion.json     // deep graph for budget limit tests

Suggested Implementation Order

1. Define TraversalHit and TraversalBudget data structures
2. Implement GraphTraversalRecall with RANDOM_WALK_RESTART strategy
3. Implement path reconstruction logic
4. Write contract tests using InMemoryVectorStore + LocalMemoryGraphAccessor
5. Add golden fixture tests
6. Verify no regression on existing retrieval paths

Acceptance Criteria

• GraphTraversalRecall produces scored candidates from anchor entities
• Traversal respects TraversalBudget limits (hops, visited vertices, timeout)
• Each TraversalHit includes a valid path from anchor to candidate
• Anchor entity is excluded from its own results
• Tests are deterministic (fixed seed, no external dependencies)
• Existing retrieval paths (Vector, Basic) are not affected
• Traversal strategy is configurable (RANDOM_WALK_RESTART, BFS, DFS)