You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@geaflow.apache.org by "kitalkuyo-gita (via GitHub)" <gi...@apache.org> on 2026/09/01 04:04:31 UTC

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

kitalkuyo-gita opened a new issue, #861:
URL: https://github.com/apache/geaflow/issues/861

   
   **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.
   
   ```java
   // 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.
   
   ```java
   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
   
   ```java
   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)
   
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@geaflow.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@geaflow.apache.org
For additional commands, e-mail: issues-help@geaflow.apache.org