[BUG] BFS Returns Duplicate Edges with Swapped Source/Target Nodes

[paveljakov]

Bug Description

The BFS edge search returns duplicate relationships where the same edge UUID appears twice but with the source and target node UUIDs swapped. This occurs because the BFS implementation uses directed traversal but undirected relationship matching, causing each relationship to be found in both directions.

Steps to Reproduce

Provide a minimal code example that reproduces the issue:

from graphiti_core.search.search import search
from graphiti_core.search.search_config import SearchConfig, EdgeSearchConfig, EdgeSearchMethod
from graphiti_core.search.search_filters import SearchFilters

# Configure search to use BFS
config = SearchConfig(
    edge_config=EdgeSearchConfig(
        search_methods=[EdgeSearchMethod.bfs],
        bfs_max_depth=1
    )
)

# Perform search using Graphiti's native search method
results = await graphiti.search_(
    query="spare parts",
    group_ids=["inventory"],
    config=config,
    search_filter=SearchFilters(),
    bfs_origin_node_uuids=["766fb29e-7868-4430-bc0c-007572e0db57"]
)

# Check for duplicates with same UUID but swapped nodes
edge_uuids = {}
for edge in results.edges:
    key = f"{edge.source_node_uuid}->{edge.target_node_uuid}"
    
    if edge.uuid in edge_uuids:
        print(f"Duplicate found for UUID {edge.uuid}:")
        print(f"  Original: {edge_uuids[edge.uuid]}")
        print(f"  Duplicate: {key}")
    
    edge_uuids[edge.uuid] = key

# You'll see output like:
# Duplicate found for UUID 209e9060-530f-4e79-a5f2-d92691b711f3:
#   Original: 766fb29e-7868-4430-bc0c-007572e0db57->28db29b8-f08a-4061-8511-38903846caf4
#   Duplicate: 28db29b8-f08a-4061-8511-38903846caf4->766fb29e-7868-4430-bc0c-007572e0db57

Expected Behavior

Each relationship should appear only once in the BFS results, maintaining the directionality established during the path traversal. A relationship with UUID X should only appear once, either as A->B or B->A, not both.

Actual Behavior

The same relationship appears twice with the same UUID but with swapped source and target nodes:

[
  {
    "uuid": "209e9060-530f-4e79-a5f2-d92691b711f3",
    "source_node_uuid": "766fb29e-7868-4430-bc0c-007572e0db57",
    "target_node_uuid": "28db29b8-f08a-4061-8511-38903846caf4",
    "name": "IsSparePartFor"
  },
  {
    "uuid": "209e9060-530f-4e79-a5f2-d92691b711f3", 
    "source_node_uuid": "28db29b8-f08a-4061-8511-38903846caf4",
    "target_node_uuid": "766fb29e-7868-4430-bc0c-007572e0db57",
    "name": "IsSparePartFor"
  }
]

Environment

• Graphiti Version: 0.18.1
• Python Version: 3.13
• Operating System: macos
• Database Backend: neo4j
• LLM Provider & Model: OpenAI GPT-4.1-mini

Installation Method

• [ ] pip install
• [ ] uv add
• [x] poetry
• [ ] Development installation (git clone)

Error Messages/Traceback

No explicit errors, but results contain duplicate data with inconsistent directionality.

Configuration

# Affects any BFS search configuration
from graphiti_core.search.search_config import SearchConfig, EdgeSearchConfig, EdgeSearchMethod

config = SearchConfig(
    edge_config=EdgeSearchConfig(
        search_methods=[EdgeSearchMethod.bfs],
        bfs_max_depth=1
    )
)

Root Cause Analysis

The issue is in graphiti_core/search/search_utils.py in the edge_bfs_search function (lines 266-283). The query uses:

1. Directed BFS traversal (correct):

   MATCH path = (origin:Entity|Episodic {uuid: origin_uuid})-[:RELATES_TO|MENTIONS*1..{bfs_max_depth}]->(:Entity)
   

2. Undirected relationship matching (problematic):

   MATCH (n:Entity)-[e:RELATES_TO]-(m:Entity)  -- Note the undirected pattern
   

The undirected pattern -(m:Entity) matches the same relationship in both directions, causing duplicates.

Additional Context

• This happens consistently with all BFS edge searches
• Affects both edge_bfs_search and get_embeddings_for_edges functions
• The same issue exists in line 1063 of search_utils.py
• Performance impact: doubles the number of results and consumes extra memory
• Data integrity issue: same relationship appears with different source/target orientations

Possible Solution

Change the undirected relationship pattern to a directed one to preserve the directionality established during BFS traversal:

# Current (problematic):
MATCH (n:Entity)-[e:RELATES_TO]-(m:Entity)

# Fixed:
MATCH (n:Entity)-[e:RELATES_TO]->(m:Entity)

This ensures that each relationship found during BFS maintains consistent directionality and appears only once in the results.

[claude[bot]]

@paveljakov Is this still an issue? Please confirm within 14 days or this issue will be closed.

[claude[bot]]

@paveljakov Is this still an issue? Please confirm within 14 days or this issue will be closed.