1.광고

안녕하세요 정이태입니다.오랜만에 10월 23일 목요일 저녁에 GUG 온라인 세미나가 예정되어 있습니다. 카이스트 김재철AI대학원 신기정 교수님 연구실 소속 김선우 연구원님과 하이퍼 그래프 이론부터 응용까지 라는 주제로 진행할 예정이며, 저또한 모더레이터 겸 요새 GraphRAG 트랜드부터 왜 HyperGraphRAG가 나오고 있는지 산업계 관점에서 생각을 공유드릴 예정이오니 관심있는 분들은 참여하셔서 본인 연구나 실무에 적용할 인사이트들을 얻어가셨으면 합니다.

** 이벤트 링크 : https://luma.com/lim37fh3

2.HyperGraphRAG: Retrieval-Augmented Generation via Hypergraph-Structured Knowledge Representation

https://arxiv.org/pdf/2503.21322

시작​

오늘 이야기할 논문의 전반적인 프로세스입니다. 기존에 알던 GraphRAG와 유사합니다. Text에서 Entity 추출해서 Knowledge base에 저장해둔뒤 유저 쿼리 발생시 Entity 추출하여 Knowledge base에 있는 데이터와 유사도를 비교하여 LLM Generation stage의 Prompt Context에 주입하여 활용한다는 것. 다만, Retrieval 대상이 Hypergraph 라는게 차이점이라고 할 수 있습니다.

Hypergraph? 이 개념에 대해 낯선 분들을 위해 Graph와 Hypergraph의 차이점을 간략하게 이야기하는 것으로부터 오늘 오마카세 시작해보겠습니다. 우선 두 개념의 차이를 단어로 각각 표현해보면, Bi-partite 와 Group-wise 라고 할 수 있습니다.

Graph는 단일 노드간의 관계를 1:1로 매핑하는 형태이고 HyperGraph는 다중 노드간 관계를 1:N으로 매핑하는 형태입니다. 즉, 공통된 엣지나 특성이 있는 경우 HyperGraph 의 HyperEdge로 Grouping되어 지식그래프 형태로 변환됩니다.

때문에 데이터를 살펴봤을시, 전반적으로 공통된 데이터 집합들이 많거나 그래프 관점에서는 Entity Link 타입 종류가 다양하며, 이 타입에 속해있는 공통된 노드가 많은 분포를 띄고 있을시 데이터 관리 관점에서 효율성이 증가할 가능성이 높아집니다.

오마카세 주방장이 생각하기에 논문에서 중점적으로 보면 좋을 부분 세 가지

이제, 제가 바라보는 본 논문의 핵심 그리고 타 논문 대비 차별점을 언급하면 다음 세 가지로 압축할 수 있을거 같습니다.

1)Hyperedge construction Proof Notation
Entity Resolution에서 많이들 고민하는 부분이죠. '삼성' 과 '(주)삼성'이 동일한 맥락을 띄는 엔티티이지만, 누군가의 관점에서는 '(주)삼성'으로 표현하는게 맞을것이고 누군가 관점에서는 '삼성'이 적절한 표현이라고 생각할 수 있습니다. 다시말해, 누군가의 '주관' 기준에 의해 엔티티가 통합되고 누락되는 문제가 발생하는데요. 본 논문에서는 이를 '객관적인' 기준을 설계하는데 도움이 될만한 수학적 증명을 다룹니다.

앞서 언급한 '주관'으로 발생하는 human-error를 줄일 수 있는 요소로써 Domain specific measurement for Entity Build가 중요하기에, 총 정보량 관점에서 무엇을 injective 할지 functionality 설계 과정 그리고 shannon entropy 를 활용해서 이를 어떻게 측정하는지 등을 살펴보시면 좋을거 같습니다. ChatGPT와 같은 보조 도구를 적극 활용하여 본인만의 아이디어를 디벨롭해보시기에 좋은 부분입니다.

2)GraphRAG expansion. Why hypergraph?

이 그림이 Standard RAG 부터 GraphRAG 그리고 HyperGraphRAG 계보를 잘 설명한 거 같네요. 기존 Standard RAG에서 GraphRAG로 넘어갈시, 특정 청크에서 정보를 '추출'하여 표현할 때 부득이하게 정보 손실이 발생합니다.

데이터들간 무슨 '연관성'이 있는지 Semantic을 적재하여 활용할 수 있고 이를 LLM에게 제공하여 데이터 해석 근거를 명확하게 제공한다는 부분에서 LLM 관점에서는 Hallucination 을 방지하고 사람 관점에서는 데이터 결과에 대한 '왜?'를 해석할 수 있는 여지가 생깁니다.

하지만, 앞서 언급한 바와 같이 '추출'에서 발생하는 정보 손실을 피할수 없기에 이를 보완하기 위한 용도인 즉, Multi-entity 로 접근한다는게 HyeprGraphRAG의 핵심인거죠.

위 그림의 예시를 한 번 해석해볼까요 ?
Vector view : Male hypertensive patients with serum creatinine levels between 115–133 μmol/L are diagnosed with mild serum creatinine elevation.

Graph view : Gender:(Hypertensive patient, Male) and Diagnosed_with:(Hypertensive patient, Mild serum creatinine elevation)

Hypergraph view : (Hypertensive patient, Male, Serum creatinine levels between 115–133 µmol/L, Mild serum creatinine elevation)

Vector view는 어떤 맥락 없이 텍스트만 정보로 표현이 되어있고, Graph는 Gender, Diagnosed_with 와 같이 Semantic이 입력되어 데이터간 맥락이 그래프로 표현되어 있습니다. Hypergraph는 단일 Hyperedge에 엔티티가 모두 포함이 되어 있구요.

이걸 GraphRAG 관점에서 접근해볼게요. Vanilla Graph를 조회하기 위해 Vector 에서 Gender 혹은 Diagnosed_with가 모두 필요한 상황이지만 Vector Search에서 각각의 Edge semantic embedding을 조회해오지 못하거나 혹은 카탈로그가 부족하거나 Text2Cypher를 맡고 있는 LLM이나 prompt에서 이 guidance가 적용되어 있지 않다면, Graph miss가 발생하게 됩니다. 하지만, Hypergraph는 Hyperedge라는 데이터로 Grouping 되어 있기에, 앞선 상황이 발생할 확률을 줄여줍니다.

이 내용이 제가 생각하는 본 논문에서 가져가면 좋을 두 번째 인사이트라고 생각하네요.

3)Optimal graph query efficiency
"thereby benefiting the optimized query efficiency of an ordinary graph database, as well as preserving the complete hypergraph-structured knowledge representation." 라고 이야기를 합니다.

위 Ablation study(Analysis of Hypergraph Retrieval Efficiency (RQ4)) 의 결과를 살펴보면, 그 이점을 살펴볼 수 있습니다. (a)는 top-k hyperedge에 따라 얼마나 성능이 향상되는지를 비교한 결과 60이상부터는 별 차이를 볼 수 없으나, 그 전까지는 선형적으로 성능이 증가함을 볼 수 있네요.

이어서, (b)는 타 GraphRAG baseline 대비 동일한 Knowledge Length 를 기준으로 실험해볼시 F1-score 차이가 적게는 6, 크게는 20까지 격차가 벌어짐을 확인할 수 있습니다. 결과적으로 HyperGraph 활용시 Retrieval token 측면에서 타 GraphRAG 대비 적은 token 활용하면서 높은 정확도를 보인다를 말할 수 있는 근거를 위 두 실험결과를 통해 알 수 있습니다.

하지만, Graphdatabase 에 적재를 한다곤하는데 Bipartite graph 구조가 아닌 Hypergraph 구조로 적재했을때 정작 얼마나 빨라졌는지 latency 관점은 언급되어 있지 않습니다. 과연 Hypergraph로 정보를 모두 종합해서 가져오는데 이게 정말 빠르게 조회할 수 있을것인가? 라는 의문이 당연하게 들거든요. 이를 위해 제가 예전에 연구했던 내용을 첨부합니다. 3여년전에 진행한 연구입니다.

Optimal graph query efficiency 레퍼런스가 궁금한 분들. https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE11705013, 하이퍼그래프 데이터베이스의 쿼리 성능 비교와 향상

논문에선 Postgresql extension AGE 를 활용해서 위에 나온 맥락을 실험해봤는데요. 내용이 기억이 안나서 다시 살펴보니 "실험 결과, JOIN 연산 수가 '5' 이상일 때 HGDB가 일반 RDB에 비해 우수한 쿼리 성능을 나타내었습니다. " 라고 요약이 되어 있네요.

내용이 자세히 기억이 나진 않지만 가장 어려웠던 부분이 데이터간 '공통' 집합 요소를 추출하고 이를 어떤 기준에 의해서 나누고 Hyperedge로 표현할지 였던거 같네요. Graph Mental modeling 하는 부분은 똑같았던거 같네요.

끝으로

산업계 및 실무 차원에서 GraphRAG 도입은 여전히 안정화되어 있지않고, 갈길이 멉니다. 하지만, 본 논문을 보면서 학계 관점에서는 개선해볼만한 부분이 많다고 생각했는데요. 리뷰를 위해 떠오르는 부분을 생각해보면 다음 이것저것이 생각나네요.

1. Group-wise graph format이 유의미한 도메인이 무엇인지 탐구하는 데이터 거버넌스 설계
-> 마냥 Entity 와 Link가 많다고하여 GraphRAG 성능 개선까지 이어진다는 보장은 없음. 논문에 수치로 증빙이 되어있기에 cornerstone 및 reference로 활용할 수 있어서 처음 스타트하기에 좋음.

2. 논문에 기재된 바와 같이 Query Search efficiency 에 Hypergraph를 활용해서 그래프 데이터 베이스 성능 개선

3 GraphRAG의 가장 큰 허들인 Entity Extraction & Resolution 의 한계를 극복하기 위한 요소로써 Hypergraph와 정보량 대조를 통한 최적 로 접근한다던지와 같이요.
-> Appendix의 Entity 관련 prompt를 보면 그렇게 특별한 내용은 없습니다. 여러 GraphRAG 엔진들을 봐오셨던 분들이라면 오히려 너무 심플해서 놀랄 정도이죠. 하지만,요새 GraphRAG를 잘 활용하기 위해 다양한 프롬프트와 이 프롬프트를 선별하고 선택하는 라우팅 모델이 중요해짐을 서서히 확인할 수 있을 겁니다. 이런 관점에서 Hypergraph도 그 프롬프트 중 하나로써 기여할 수 있는 역할이 분명히 있을거란 생각에 작성해봅니다.

배지훈님께서 든든하게 그래프 오마카세를 맡아주신 덕분에 저도 오마카세를 통해 정보를 습득하곤 하는데,오랜만에 관점을 바꿔 정보 습득자가 아닌, 정보 전달자 관점에서 오마카세 작성하니 감회가 또 다르네요. 종종 와서 저또한 기여할 수 있도록 부지런히 공부해야겠습니다.

이번주 그래프 오마카세도 맛있으셨을까요? 다음주엔 더더욱 맛있는 그래프 소식으로 찾아뵙겠습니다. 즐거운 주말 되세요.