Multi-Hop Relationship Traversal¶

Overview¶

The Graffold now supports multi-hop relationship traversal, allowing queries to discover indirect connections between entities through intermediate nodes. This enables answering questions like "What pathways connect BRCA1 to breast cancer?" by traversing protein → pathway → disease relationships.

Features¶

Configurable Hop Depth: Traverse 1-3 relationship hops (default: 1)
Path Context: Results include the full relationship path (e.g., "BRCA1 → DNA Repair → Breast Cancer")
Mode-Aware: Works with all query modes (local, global, hybrid, mix)
Streaming Support: Compatible with SSE streaming responses

API Usage¶

REST API¶

Add the hop_depth parameter to your query request:

curl -X POST "http://localhost:8000/v1/sessions/{session_id}/query" \
  -H "Authorization: Bearer $API_AUTH_TOKEN" \
  -H "Content-Type: application/json" \
  -d '{
    "question": "What pathways connect BRCA1 to breast cancer?",
    "mode": "local",
    "hop_depth": 2
  }'

Python Client¶

import requests

BASE = "http://localhost:8000"
HEADERS = {"Authorization": "Bearer your_token", "Content-Type": "application/json"}

# Create session
session_data = {
    "llm_service": "llama3-instruct",
    "database_name": "neo4j",
    "database_type": "neo4j",
    "agent_type": "graph_rag_agent",
    "connection_details": {
        "uri": "bolt://localhost:7687",
        "user": "neo4j",
        "password": "your_password"
    }
}

response = requests.post(f"{BASE}/v1/sessions", headers=HEADERS, json=session_data)
session_id = response.json()["session_id"]

# Query with multi-hop traversal
query_data = {
    "question": "What pathways connect BRCA1 to breast cancer?",
    "mode": "local",
    "hop_depth": 2  # Traverse up to 2 hops
}

response = requests.post(
    f"{BASE}/v1/sessions/{session_id}/query",
    headers=HEADERS,
    json=query_data
)

result = response.json()
print(result["answer"])

Streaming Queries¶

Multi-hop traversal works with SSE streaming:

response = requests.post(
    f"{BASE}/v1/sessions/{session_id}/query",
    headers=HEADERS,
    json={
        "question": "What pathways connect BRCA1 to breast cancer?",
        "stream": True,
        "mode": "local",
        "hop_depth": 3
    },
    stream=True
)

for line in response.iter_lines(decode_unicode=True):
    if line.startswith("data: "):
        print(line[6:])

Response Format¶

Multi-hop results include path context for each relationship:

{
  "answer": "BRCA1 connects to breast cancer through DNA repair pathways...",
  "sources": [...],
  "detailed_results": [
    {
      "name": "BRCA1",
      "id": "P38398",
      "labels": ["Protein"],
      "neighbors": [
        {
          "target": "Breast Cancer",
          "target_id": "MONDO:0007254",
          "target_labels": ["Disease"],
          "path_length": 1,
          "path_context": ["BRCA1 → ASSOCIATES_WITH → Breast Cancer"]
        },
        {
          "target": "DNA Repair",
          "target_id": "GO:0006281",
          "target_labels": ["Pathway"],
          "path_length": 2,
          "path_context": [
            "BRCA1 → PARTICIPATES_IN → DNA Repair Pathway",
            "DNA Repair Pathway → REGULATES → DNA Repair"
          ]
        }
      ]
    }
  ]
}

Hop Depth Guidelines¶

hop_depth=1 (default): Direct relationships only (fastest, most precise)
hop_depth=2: Includes one intermediate node (e.g., protein → pathway → disease)
hop_depth=3: Includes two intermediate nodes (slower, broader context)

Recommendation: Start with hop_depth=1 for specific queries, increase to 2-3 for exploratory questions about indirect connections.

Query Mode Compatibility¶

Multi-hop traversal is supported in the following modes:

local: Entity neighborhood search with multi-hop expansion
hybrid: Combines local multi-hop with global community summaries
mix: Weighted blend of vector and graph retrieval with multi-hop support
global: Uses community summaries (hop_depth not applicable)
naive: Direct LLM answer (hop_depth not applicable)

Implementation Details¶

Cypher Query Pattern¶

The system uses variable-length path patterns (Cypher is supported by both Neo4j and Memgraph):

MATCH path = (n)-[*1..{hop_depth}]-(m:Entity)
WHERE m.id <> n.id
WITH path, m, 
     [rel in relationships(path) | type(rel)] as rel_types,
     [node in nodes(path) | {name: node.name, labels: labels(node)}] as path_nodes,
     length(path) as path_length

Path Context Generation¶

For each multi-hop relationship, the system constructs a human-readable path:

BRCA1 → PARTICIPATES_IN → DNA Repair Pathway → REGULATES → DNA Repair

This provides full provenance for indirect connections.

Performance Considerations¶

Query Time: Increases with hop depth (1-hop: ~100ms, 2-hop: ~300ms, 3-hop: ~1s)
Result Size: More hops = more neighbors (limited to 30 per seed entity)
Recommendation: Use hop_depth=1 for production queries, higher values for exploration

Example Use Cases¶

1. Pathway Discovery¶

{
  "question": "What pathways connect BRCA1 to breast cancer?",
  "hop_depth": 2
}

2. Indirect Protein Associations¶

{
  "question": "Which proteins are indirectly associated with Alzheimer's disease?",
  "hop_depth": 3
}

3. Disease Mechanism Exploration¶

{
  "question": "How does TP53 relate to cardiovascular disease?",
  "hop_depth": 2
}

Validation¶

The implementation includes:

✅ Hop depth parameter validation (1-3 range)
✅ Path context generation for all multi-hop relationships
✅ Integration with all query modes
✅ Streaming support via SSE
✅ Backward compatibility (defaults to 1-hop)

Future Enhancements¶

Potential improvements for future iterations:

Weighted path scoring based on relationship types
Path filtering by relationship type (e.g., only "ASSOCIATES_WITH" paths)
Shortest path prioritization
Path visualization in the frontend