JYP Garden

Multi-hop Search (다중 홉 검색)

Properties1
tagsmulti-hop, graph-traversal, graphrag, relationship-inference, knowledge-graph, knowledge

5 min read

Multi-hop Search (다중 홉 검색)

정의: 그래프에서 여러 단계의 관계를 따라가며 정보를 수집하는 검색 기법. 1-hop → 2-hop → n-hop 순서로 직간접 관계를 모두 활용.

기본 개념

Hop의 의미

1-hop: 직접 연결된 이웃
    Alice --WORKS_AT--> Google

2-hop: 중간 노드를 거친 관계
    Alice --WORKS_AT--> Google --MANUFACTURES--> Chrome

3-hop: 더 깊은 관계
    Alice --WORKS_AT--> Google --MANUFACTURES--> Chrome --USED_BY--> User123

실제 예시

추천 시스템

1-hop: 직접 유사도

사용자 A가 본 영화
    A --WATCHED--> Movie1, Movie2, Movie3

2-hop: 카테고리 기반 추천

A --WATCHED--> Movie1 --BELONGS_TO--> Drama --HAS_SIMILAR--> Movie4
    → Movie4 추천

3-hop: 협업 필터링

A --WATCHED--> Movie1 --RATED_BY--> User B --WATCHED--> Movie5
    → Movie5 추천 (유사 사용자가 본 영화)

사기 탐지

1-hop: 직접 거래

계정 A --TRANSFERS_TO--> 계정 B (금액 큼)

2-hop: 의심 패턴

A --TRANSFERS_TO--> B --TRANSFERS_TO--> C --WITHDRAWS_FROM--> 환전소
    → 의심 거래 체인 감지

3-hop: 네트워크 분석

A --SHARES_IP--> X --SHARES_EMAIL--> Y --OPENS_NEW_ACCOUNT--> Z
    → 조직된 사기 탐지

Cypher에서의 구현

1-hop 검색

MATCH (a:Person {name: "Alice"})-[r1]->(b)
RETURN a, r1, b

2-hop 검색

MATCH (a:Person {name: "Alice"})-[r1]->(b)-[r2]->(c)
RETURN a, b, c

3-hop 검색

MATCH (a:Person {name: "Alice"})-[r1]->(b)-[r2]->(c)-[r3]->(d)
WHERE d.risk_level > 0.8
RETURN a, b, c, d

가변 길이 경로 (1~5 hop)

MATCH (a:Person {name: "Alice"})-[*1..5]->(result)
RETURN DISTINCT result

Vector RAG vs Graph RAG에서의 역할

Vector RAG의 한계

Q: "Alice가 선호할 만한 상품은?"

검색 결과:
→ "Alice, 구매, 책" (청크 1)
→ "사용자, 추천, 영화" (청크 2)

문제: 관계가 단절됨. Alice의 구매 이력과 추천의 연결고리 없음

Graph RAG의 장점 (Multi-hop)

Q: "Alice가 선호할 만한 상품은?"

탐색 경로 (3-hop):
1. Alice --PURCHASED--> Book1, Book2
2. Book1 --BELONGS_TO--> ScienceFiction
3. ScienceFiction --HAS_SIMILAR--> Book3, Book4

결과: Book3, Book4 추천 (깊이 있는 추론)

Multi-hop Search의 특징

장점

✅ 깊이 있는 컨텍스트 — 직접 관계만으로는 알 수 없는 정보 발굴 ✅ 관계 추론 — 간접적 연결고리 발견 ✅ 정확도 향상 — 더 많은 증거 수집 ✅ 이상 탐지 — 비정상 패턴의 깊은 체인 발견

단점

❌ 계산 복잡도 — hop 깊이에 따라 지수적 증가 ❌ 성능 저하 — 깊은 탐색은 느림 ❌ 노이즈 — 너무 깊으면 무관한 정보 포함 가능 ❌ 최적화 필요 — 가중치, 필터링 필요

최적 Hop 깊이 결정

도메인최적 깊이사유
추천시스템2~3사용자→아이템→카테고리
사기탐지3~4거래망 분석
그래프RAG1~2컨텍스트 관련성
소셜분석2~5영향력 범위
네트워크분석5+중심성(centrality) 계산

성능 최적화 전략

1. 필터링 (Filtering)

MATCH (a:Person {name: "Alice"})-[*1..3]->(result:Product)
WHERE result.price < 100
RETURN result

2. 가중치 제한 (Weight Constraints)

MATCH (a:Person {name: "Alice"})-[r1*1..3]->(result)
WHERE all(rel IN r1 WHERE rel.weight > 0.5)
RETURN result

3. 경로 제한 (Path Constraints)

MATCH (a:Person)-[*1..3]->(result)
WHERE length(path) <= 3  # 정확히 3 hop 이하
RETURN result

4. 샘플링 (Sampling)

MATCH (a:Person {name: "Alice"})-[*1..3]->(result)
RETURN result
LIMIT 100  # 상위 100개만

실제 GraphRAG 파이프라인에서의 역할

1. 사용자 쿼리: "Alice의 선호도 프로필은?"
   ↓
2. 시맨틱 매칭: Alice 노드 식별
   ↓
3. Multi-hop 탐색:
   - 1-hop: Alice의 직접 구매
   - 2-hop: 구매 상품의 카테고리
   - 3-hop: 유사 카테고리의 상품
   ↓
4. 컨텍스트 수집: [Alice, 구매, 책, SF, Book3]
   ↓
5. LLM에 전달: "Alice는 과학소설을 좋아하고..."
   ↓
6. 최종 답변 생성

관련 개념

출처: graphrag-performance — Multi-hop Search의 성능 실증

그래프 뷰