5. Graph-Based Indexing
여러 형태의 데이터 소스를 이용해 그래프 데이터를 구축
⇒ 구축한 그래프 데이터를 저장하고 효율적으로 검색하기 위해 인덱싱을 수행
⇒ 인덱싱이 완료된 데이터는 그래프 데이터베이스에 저장됨
(그래프 데이터베이스는 그래프 데이터를 효율적으로 저장하고 검색할 수 있는 데이터베이스 시스템으로, 지식 그래프의 정보를 활용하기 위한 최종 저장소 역할을 함)
5.1 Graph Data
5.1.1 Open Knowledge Graphs
(1) General Knowlege Graphs
- 주로 일반적이고 구조화된 지식을 저장함
- 전 세계 커뮤니티의 협업과 지속적인 업데이트를 바탕으로 정보를 갱신
- Encyclopedic knowledge graphs
- 전문가와 백과사전에서 수집한 대규모의 현실 세계 지식을 포함
- ex) Freebase, DBpedia, YAGO, Wikimedia 프로젝트의 구조화된 데이터가 저장된 Wikidata
- Co mmonsense knowledge graphs
- 개념 간의 의미적 연관성이나 사건 간의 인과관계와 같은 추상적인 상식 지식을 포함
- ex) 사건 간의 인과 관계를 모델링하는 ATOMIC, 단어/구를 나타내는 노드와 이들 간의 의미적 관계를 나타내는 엣지로 구성된 ConeptNet
(2) Domain Knowledge Graphs
특정 분야의 전문 지식을 제공하여 모델이 복잡한 관계에 대해 깊이 있는 통찰과 이해를 갖추도록 도움
ex) GraphQA
- 여러 도메인에 걸친 일반적/보편적 지식과 추론을 요구하는 데이터셋으로, 도메인 지식 그래프가 다양한 전문 분야에서 활용될 수 있도록 설계됨
- ExplaGraphs, SceneGraphs, WebQSP와 같은 다양한 소스에서 데이터를 표준 그래프 형식으로 변환하여 다중 단계 추론이 필요한 질문에 답할 수 있는 모델을 평가함
- GraphRAG 시스템의 성능을 테스트하고, 다양한 도메인에서 추론 능력을 향상시키는 데 사용됨
- ExplaGraphs: 상식 추론을 지원하기 위해 사용됨. 특정 신념을 지지/반대하는 주장을 상식이 보강된 그래프로 표현.
- WebQSP: 2단계 추론 질문을 포함하며, hit@1 지표로 답변 정확도를 평가하는 대규모 지식 그래프 QA 데이터셋
- SceneGraphs: 시각적 질문 응답을 위한 데이터셋. 이미지의 객체, 속성, 관계를 상세히 설명하는 100,000개의 장면 그래프를 포함
5.1.2 Self-Constructed Graph Data
특징
- 특정 도메인이나 독점적 지식을 검색 과정에 맞게 커스터마이즈하고 통합할 수 있도록 연구자들이 구성한 그래프 데이터
- 그래프 데이터가 포함되지 않은 다운스트림 작업에서도 문서, 테이블, 데이터베이스 등 여러 출처로부터 데이터를 가져와 새로운 그래프를 구성하여 활용할 수 있음
적용 사례
- 문서 간 관계를 모델링하기 위해 다양한 연결 방식을 갖는 문서 간의 그래프(이질적 문서 그래프)를 구성
- 문단 간 공유 키워드를 바탕으로 관계를 설정하여 관련성을 높임
- 문서 내 엔티티 간의 관계를 포착하기 위해 개체명 인식(Named Entity Recognition)를 사용해 문서에서 엔티티를 추출하고, 언어 모델을 활용해 엔티티 간의 관계를 추출하여, 검색된 엔티티와 관계로 지식 그래프를 형성함
5.2 Indexing
5.2.1 Graph Indexing
- 가장 일반적으로 사용되는 접근 방식으로, 그래프 전체 구조를 보존
- 특정 노드에 대해 모든 엣지와 인접 노드에 쉽게 접근할 수 있도록 보장함
- 이후의 검색 단계에서는 BFS(Best First Search)와 최단 경로 알고리즘과 같은 그래프 검색 알고리즘을 활용하여 검색 진행
- cf) QA-GNN 모델에서는 그래프 상의 연결 구조와 노드 간의 attention 가중치를 이용해 질문에 대한 답변을 도출함. 이 과정에서 BFS를 사용해 높은 attention 가중치를 가진 경로를 우선적으로 추적하며, 연결된 엔티티들을 통해 모델의 추론 과정을 이해할 수 있음.
5.2.2 Text Indexing
개념
- 그래프 데이터를 텍스트로 변환하여 검색을 최적화하는 방법
특징
- 변환된 텍스트는 텍스트 코퍼스에 저장되며, 희소 검색과 밀집 검색 같은 다양한 텍스트 기반 검색 기법을 적용할 수 있음
- 희소 검색(sparse retrieval) vs. 밀집 검색(dense retrieval)
- 사전 정의된 규칙이나 템플릿을 사용하여, 사람이 읽을 수 있는 자연어로 그래프 데이터를 표현함
- 서브그래프 수준의 정보도 요약 및 변환하여 보다 큰 단위의 정보를 텍스트로 제공할 수 있음
5.2.3 Vector Indexing
개념
- 그래프 데이터를 벡터 표현으로 변환하여 검색 효율성을 향상시키는 방법
특징
-
그래프를 벡터화함으로써 빠른 검색과 효율적인 쿼리 처리가 가능해짐
-
쿼리 임베딩을 통해 엔티티 링크와 같은 작업을 원활하게 수행할 수 있음.
-
고차원 공간에서 유사한 벡터를 빠르게 찾을 수 있음.
적용 사례
- G-Retriever: 언어 모델을 활용하여 그래프 내 각 노드와 엣지에 연결된 텍스트 정보를 벡터 형태로 변환
G-Retriever에서의 Indexing
- 노드와 엣지의 임베딩 생성
- 텍스트 데이터(노드와 엣지에 포함된 텍스트 속성)를 고정된 크기의 벡터로 변환
- Pretrained LM을 사용하여 각 노드와 엣지의 텍스트 의미를 반영한 벡터로 변환
- Step1: 노드의 텍스트 속성 인코딩
- Step2: 엣지의 텍스트 속성 인코딩
- Step3: 임베딩 저장
- 생성된 노드와 엣지의 벡터는 최근접 이웃 데이터 구조(nearest neighbor data structure)에 저장됨
5.2.4 Hybrid Indexing
특징
- 하나의 인덱싱 방법에 의존하기 보다는 인덱싱 방식을 결합한 하이브리드 접근법이 더 선호됨
- Graph Indexing: 구조적 정보를 쉽게 접근할 수 있게 함
- Text Indexing: 텍스트 콘텐츠 검색을 간소화함
- Vector Indexing: 빠르고 효율적인 검색을 가능하게 함
적용 사례
- HybirdRAG: 벡터와 그래프 데이터를 동시에 검색하여 더 풍부한 콘텐츠를 제공함
- EWEK-QA: 텍스트와 지식 그래프를 동시에 활용
REFERENCE
Xiaoxin He et al. 2024. G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering. arXiv:2402.07630 [cs.LG]
Michihiro Yasunaga et al. 2021. QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering. In *Proceedings of NAACL-HLT 2021*, Online, June 6-11, 2021, pp. 535–546.
