[geaflow/graph-algorithms] Implement Path-Based Social Proof Extraction

[kitalkuyo-gita]

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

Context

When graph traversal recall discovers a candidate, the user (or downstream answer synthesizer) needs to understand why this candidate was recommended. In Twitter's UTEG system, this is called "social proof" — "User A, whom you follow, liked this tweet."

In Graph Memory Phase 1, social proof answers questions like:

• "Why was this chunk recommended?" → "Because entity X (which you anchored on) is mentioned in this chunk's source document"
• "Why was this entity suggested?" → "Because it shares a 'related_to' edge with entity Y, which appeared in your query"

This issue extracts human-readable social proof from traversal paths. It is a pure data transformation — no graph traversal, no scoring, no natural language generation.

Scope

• New SocialProofExtractor class in geaflow-ai/src/main/java/org/apache/geaflow/ai/retrieval/traversal/
• Accepts List<TraversalHit> (from GM-AI-P1-050) and produces List<SocialProof>
• Each SocialProof describes the relationship chain from anchor to candidate
• Supports configurable edge-type-to-verb mapping (e.g., Like → "liked", Follow → "follows")
• Deterministic output (same input → same social proof text)

Non-Goals

• This does NOT generate natural language answers. It produces structured social proof objects.
• This does NOT call any LLM or text generation model.
• This does NOT modify the traversal results. Pure transformation.
• This does NOT handle answer citation. That is GM-AI-P1-038 (AnswerSynthesizer).

Constraints

C-1: Must not include raw document text in social proof

Social proof describes relationships, not content. "User A liked this tweet" is valid. "User A liked this tweet which says 'the latest AI research shows...'" is not — that leaks raw text into the social proof object.

C-2: Must handle cycles gracefully

If the traversal path contains a cycle (A → B → C → A), the social proof must not produce an infinite description. Cycles should be detected and the path truncated with a "[...]" marker.

C-3: Must be configurable for different edge types

The mapping from edge types to human-readable verbs must be configurable, not hardcoded. Different graph schemas will use different edge type names.

Map<String, String> edgeVerbMapping = Map.of(
    "like",        "liked",
    "follow",      "follows",
    "retweet",     "retweeted",
    "reply",       "replied to",
    "contains",    "contains",
    "related_to",  "is related to",
    "authored_by", "was authored by"
);

C-4: Must preserve edge direction in social proof

"A liked B" is different from "B liked A". The social proof must reflect the actual direction of the edge in the path.

Data Structures

public class SocialProof {
    /** The candidate entity this proof explains. */
    private final GraphEntity candidate;

    /** The anchor entity the traversal started from. */
    private final GraphEntity anchor;

    /** Human-readable description of the relationship chain. */
    private final String description;

    /** Structured steps in the proof. */
    private final List<SocialProofStep> steps;

    /** Confidence in this social proof (0.0 - 1.0). */
    private final double confidence;
}

public class SocialProofStep {
    /** Source entity in this step. */
    private final GraphEntity source;

    /** Edge type (e.g., "like", "follow", "contains"). */
    private final String edgeType;

    /** Human-readable verb for this edge (e.g., "liked"). */
    private final String verb;

    /** Target entity in this step. */
    private final GraphEntity target;
}

Example

Given a traversal hit:

Anchor: User_A
Candidate: Tweet_Z
Path: User_A --[follow]--> User_B --[like]--> Tweet_Y --[contains]--> #AI --[contains]--> Tweet_Z

The social proof extraction produces:

{
  "candidate": "Tweet_Z",
  "anchor": "User_A",
  "description": "User_A follows User_B, who liked content about #AI, which also contains Tweet_Z",
  "steps": [
    {"source": "User_A", "edgeType": "follow", "verb": "follows", "target": "User_B"},
    {"source": "User_B", "edgeType": "like", "verb": "liked", "target": "Tweet_Y"},
    {"source": "Tweet_Y", "edgeType": "contains", "verb": "contains", "target": "#AI"},
    {"source": "#AI", "edgeType": "contains", "verb": "contains", "target": "Tweet_Z"}
  ],
  "confidence": 0.85
}

Test Strategy

Test	Scenario	Expected
singleHopProof	Anchor --[like]--> candidate	Proof with 1 step, verb "liked"
multiHopProof	Anchor → A → B → candidate	Proof with 3 steps, correct verbs
cycleTruncation	Path with cycle A→B→C→A	Description truncated, no infinite loop
unknownEdgeType	Edge type not in mapping	Edge type used as-is, no verb mapping
directionPreserved	A→B vs B→A with same edge type	Different descriptions
emptyPath	Traversal hit with empty path	Minimal proof: "directly related"
edgeVerbConfigurable	Custom edge mapping provided	Verbs match custom mapping
descriptionConsistency	Verify description matches steps	Description is a valid concatenation of steps

Fixture:

geaflow-ai/src/test/resources/traversal/social-proof/
├── single-hop.json
├── multi-hop.json
├── cycle-path.json
├── custom-edge-mapping.json
└── empty-path.json

Suggested Implementation Order

1. Define SocialProof and SocialProofStep data structures
2. Implement SocialProofExtractor with edge-verb mapping
3. Implement cycle detection (path deduplication)
4. Write unit tests
5. Write golden fixture tests

Acceptance Criteria

• SocialProofExtractor produces valid SocialProof from TraversalHit paths
• Edge direction is correctly reflected in descriptions
• Cycles in paths are truncated, not infinite-looped
• Unknown edge types are handled gracefully (used as-is)
• Edge-verb mapping is configurable
• Social proof does not include raw document text
• Same input always produces same output (deterministic)