Hodge-Compositional Edge Gaussian Processes

paper link : https://arxiv.org/abs/2310.19450

official code : https://github.com/cookbook-ms/Hodge-Edge-GP

• '왜 그래프에 가우시안 프로세스를 적용하려 했을까? 어떠한 방식으로 정의하였는가? 그래서 핵심은 뭔가?' 최근 그래프 가우시안 프로세스 (graph GPs) 논문들을 쭉 짚어보면서 들었던 의문들이었습니다. 그리고 다음 의문들을 해결하는 연구 흐름이 나름 재밌습니다.
  • 가우시안 분포에 베이지안 분류기를 접목하기 위해 학습 데이터에 대한 유클리드 공간에서의 가우시안 분포를 좀 더 불확정성이 높은 비유클리드 공간, 즉 그래프와 같은 복잡한 데이터 상의 가우시안 분포를 가정할 수 있는 방법을 찾아내고자 합니다.
  • 저번 주 오마카세에서 말씀드린 것 처럼, 공분산 커널 설계의 중요성이 더욱 중요해지면서 이를 위한 (그 어렵다는) 확률편미분방정식(Stochastic Partial Differential Equation, SPDEs)에서 파생된 Mat'ern family kernel을 그래프 노드 모델링 함수로써 활용하였습니다. 다음 함수의 특성을 활용하여 그래프 분류와 같은 다운태스크에 적용해보려는 시도도 등장했습니다.
  • 그래프 가우시안 프로세스의 핵심은 결국 그래프 상의 확산 (Diffusion) 혹은 랜덤워크와 같이 노드 사이의 의존성을 인코딩하는 구조화된 공분산 커널을 설계하는 것으로 생각됩니다.
  • 개인적으로 '우물 안 개구리'의 마인드에서 벗어나려는 노력의 발전으로 느껴졌습니다. 또한 그래프의 강점을 많이 느꼈던 것 같기도 합니다.
• 여기에서 새롭게 든 의문점은 '노드에서만? 엣지에서는?' 그리고 '단순 그래프에서만? 복합 네트워크를 표현할 수 있는 그 이상의 Complex으로 확장될 수 있을 것 같은데?', 그리고 동일한 질문에 대한 답변을 제공하는 논문을 이번 주 오마카세로 전달해드리고자 합니다.
  • 2-dim Simplicial Complex 상 엣지 흐름 (Edge flow)에 대한 가우시안 프로세스 (GP)를 정의하고, 그래프 확장 도메인 상에서의 그 효과를 폭넓게 입증한 논문입니다.

Edge Functions on Simplicial Complexes

• 이전 오마카세 글에서 계속적으로 다루어왔던 Simplicial complexes 상의 엣지 흐름을 시각적으로 Fig 1에 표현하였습니다. 직관적으로 Simplicial complex의 3가지 고유 공간(Gradient, Curl, Harmonic space) 상에서 포착되는 노드-엣지 사이의 흐름, 엣지-면 사이의 흐름 등을 확인해볼 수 있을 것 같습니다.
• Hodge Laplacian & Decomposition에 대한 설명은 이번 오마카세에서는 생략하겠습니다. 동일한 개념이니 이전 오마카세 글을 참고해주시기 바랍니다.
• 다음 세션에서 짚고 넘어갈 부분이 있습니다. Edge Gaussian Process을 정의하는 데 활용되는 정보들이기에 한번 더 Recap하고 가볍게 넘어가겠습니다.
  • Gradient flow f_G=B₁^Tf₀는 삼각형 면 상에서 흘러가는 순환 흐름의 총 합이 0을 만족하는 curl-free 특징을 갖습니다. Fig 1(c)에서 표현된 다음 정보는 예를 들어 t₁ 상의 엣지 신호 합은 -2.30 + 0.24 - (-2.07) = 0을 만족합니다. 여기에서 방향성 (Orientation) 정보까지 모두 고려해야 합니다.
  • Curl flow f_C=B₂f₂는 각 노드로부터 들어오고 나가는 엣지 흐름의 합이 0을 만족하는 div-free 특징을 갖습니다. Fig 1(d)에서 표현된 다음 정보는 예를 들어 노드 2(n₂)의 경우 (+)들어오는 엣지 + (-)나가는 엣지 흐름의 총합 = 1.0 - (1.5 - 0.5) = 0을 만족합니다.
  • Harmonic flow f_H는 curl-free, div-free를 모두 만족하는 경우에 해당합니다. 즉, 삼각형 면 상에서의 모든 엣지 흐름 합 및 각 노드의 들어가고 나오는 엣지 흐름의 총합 모두 0을 만족합니다. 결론적으로 Fig 1(e)에서 노드 1,3,4로 구성된 Hole 상의 엣지 흐름만 포착됩니다.

Edge Gaussian Processes

• Boroviskiy et al. 의 선구적인 연구에서 그래프 상의 가우시안 프로세스는 (Cov) Matérn kernel 및 Diffusion kernel로써 정의할 수 있음을 입증하였습니다. 다음을 기반으로 하여, 엣지 흐름에 대한 가우시안 프로세스를 edge (1-dim) Hodge Laplacian (L₁)을 기반으로 식 6과 같이 정의합니다.

• 각각의 이름을 본따 edge Matérn GPs 및 edge Diffusion GPs라고 명칭합니다.
• 기존 Hodge Laplacian(-based) kernel (L₁^TL₁)의 속성을 그대로 상속받아 단순 L₁의 인접한 1-hop 엣지 관계성 뿐만 아니라 그 이상의 엣지 관계성까지 인코딩할 수 있는 flexibility를 활용할 수 있음을 언급합니다.

• 식 6으로 정의되는 Edge Gaussian Process (edge GPs)를 Edge Function on Simplicial complex에 어떻게 정의할 수 있을까요? 위에서 Recaps한 내용을 기반으로 Div-free & Curl-free edge GPs를 정의합니다.
  • 삼각형 면에 순환하는 Curl flows의 Div-free한 엣지 흐름 (Fig 1(d) 참고)과 각 노드를 들락날락하는 Gradient flows의 curl-free한 엣지 흐름 (Fig(c) 참고)을 생각해보면 이들은 서로 독립적 흐름 관계를 가지고 있음을 알 수 있습니다.
  • 다음 흐름을 포착하는 각 고유 공간 Curl space & Gradient space는 Hodge decomposition을 통해 얻어진 직교 공간이라는 사실로부터 쉽게 이해해볼 수 있습니다.
  • 다음 사실을 기반으로, Div-free edge GPs 및 Curl-free edge GPs를 각각 개별적으로 정의합니다. 즉, 서로 간의 어떠한 영향을 주고받지 않는 독립적인 가우시안 프로세스이며 파라미터 공유도 하지 않습니다.
• 위의 사실로부터, 저자들은 식 14와 같이 각 GPs를 정의합니다.

• 다음 공분산 커널 함수를 식 15와 같이, Gradient space의 기저 벡터 U_G 및 Curl space의 기저 벡터 U_C을 활용하여 정의합니다. 형태가 Hodge Laplacian의 고유분해 꼴과 비슷한데 해당 고유값 함수(Tau 기호)가 개별적으로 정의됩니다.
• 다음 Tau 함수 선택에 따라 위의 독립적 GPs를 정의할 수 있게 됩니다. 마찬가지로 Harmonic GPs도 식 14,15와 동일한 형태로 정의합니다.
• 식 6에서의 Matérn kernels에 대한 독립적인 G(radient), C(url), H(armonic) GPs를 통합적으로 아래 식 16과 같이 표기합니다. 여기에서 Sigma 기호는 분산 파라미터입니다.

• Div-free, Curl-free한 Harmonic GPs의 경우 고유값 벡터 = 0 이기 때문에 공분산 커널이 항상 0이 되는 것을 방지하기 위해, 특별히 Harmonic 고유값 함수는 Sigma² 로써 고려합니다.
• 개별적인 G-, C-, H-Matérn kernels의 고유값 함수 형태를 Fig 2와 같이 시각화하여 제공합니다.

Hodge-compositional Edge GPs (HC edge GPs)

• 엣지 함수 f₁ = f_G + f_C + f_H의 정의로부터 위의 독립적인 함수들의 총 합으로 (: Hodge-compositional) 전체 Edge GPs를 식 20과 같이 정의합니다. 즉, K₁ = K_G+K_C+K_H의 관계를 만족하는 전체 Edge GPs f₁ ~ GP (0, K₁)은 f_G ~ GP(0, K_G), f_C ~ GP(0, K_C), f_H ~ GP(0, K_H)로부터 독립적으로 포착된 모든 속성들을 중첩없이 활용 가능하다는 장점을 가지게 됩니다.
• 다음 사실은 Fig 2의 시각화와 같이, 위의 과정을 따르지 않는 non-HC의 경우보다 더욱 폭넓은 정보를 기반으로 정교한 Edge GPs를 모델링할 수 있게 됩니다. 여기에서 Hodge Decomposition의 강점이 느껴졌던 부분입니다.
  • 다음 부분에 대한 자세한 논의는 Comparision to non-HC GPs를 참고해주시기 바랍니다.
• 마지막으로 노드-엣지-삼각형 구성의 전체 Simplicial complexes 상의 가우시안 프로세스를 어떻게 정리해볼 수 있을까요?

Node-Edge-Triangle GP Interactions

• Simplicial complex 상에서는 노드-엣지 및 엣지-삼각형 면 상의 흐름들을 동시에 포착해내는 것이 중요합니다.
• 앞의 설명들은 각각의 경우를 독립적으로 바라보고 개별적인 GPs를 정의했었는데 (div-free & curl-free edge GPs), 이들을 한번에 통합할 수 있는 방법을 마지막 세션에서 설명합니다.
• 기존 연구들은 그래프 노드 상에서의 GPs를 다루었습니다. 하지만 다음 사실은 edge GPs의 f_G 상에서 포착되는 정보와 유사하며, 정확하게는 해당 노드를 지나가는 엣지 흐름 상에서 얻어낼 수 있습니다. (Corallary 6) 마찬가지로 f_C상에서 포착되는 삼각형 면의 순환 흐름 상에서 삼각형 면 GPs의 정보를 얻어낼 수 있습니다.

• 정리하자면 Edge GPs의 div-free f_G 함수로부터 기존 연구들의 내용을 모두 커버할 수 있으며, 추가적으로 curl-free f_C 함수로부터 고차수 정보까지 포착할 수 있음을 주장합니다. 이 놀라운 사실을 Appendix B.9에서 증명하고 있습니다.

• 그렇다면 Harmonic function f_H는 어떻게 사용될까요? 다음은 노드 및 삼각형 함수 f₀ ~ GP(0, K₀) , f₂ ~ GP(0, K₂) 에 대한 사전 정보 (prior)가 뚜렷할 때 식 23과 같이 엣지 함수 f₁의 공분산 커널 K₁을 정의하는 데 사용됩니다. 다음 사실은 Appendix B.10에서 증명하고 있습니다.

• 실험적으로 Hodge-compositional(HC) Matérn & Diffusion kernel edge GPs으로 모델링한 화폐 거래, 해수 흐름 등의 다양한 도메인에서, 해당 시스템 상의 물리적 사전 정보를 예측한 결과가 실제와 거의 유사한 결과를 얻어냈음을 보여줍니다. 자세한 논의는 해당 실험 파트를 확인해주세요.

• 핵심 포인트를 가볍게 정리해보면, Simplicial complex의 가우시안 프로세스는 토폴로지 신호 처리의 핵심 Hodge Decomposition의 직교 공간들 상에서 포착될 수 있는 엣지 흐름 정보들을 개별적으로 커널링하여 조합한 Hodge-compositional edge GPs를 정의하였습니다. 기존 Hodge theory 및 그래프 노드 상의 GPs 특성들을 모두 활용할 수 있다는 장점을 갖습니다.
• 새로운 인사이트로 Gradient GP 모델링을 통한 기존 노드 상의 graph GPs를 일반화할 수 있으며, Curl GP 모델링을 통한 그 이상의 추가적인 GPs 정보들까지 한번에 활용할 수 있다는 점입니다. 그리고 최종 Edge GPs의 공분산 커널을 정의할 때 Harmonic GP 모델링을 활용할 수 있다는 부분도 보여주었습니다. Appendix에서의 자세한 증명 및 동적 엣지 네트워크 실험 환경에서의 성능을 입증함으로써 주장의 신빙성을 높혀주었습니다.
• 개인적으로 아이디어 노벨티에 반해 성능과 복잡도 사이의 trade-off가 존재할 것 같은 느낌이 들었고, 따라서 현실적인 효율성에 대한 의문이 남긴 합니다. 하지만 앞선 graph GPs 연구의 일반화 가능성 및 확장성을 보여준 부분에서 그 의의가 더욱 크게 느껴졌던 것 같습니다.

[Contact Info]

Gmail : jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn

Don’t Forget to Connect! Improving RAG with Graph-based Reranking

paper link : https://arxiv.org/abs/2405.18414

정이태

문서를 구문 , 객체로 분리해 지식베이스를 구축한 뒤, RAG 기술을 적용하려는 분들에게 도움이 될 논문입니다. 현업에서 차용할만한 부분이 많아보여서 가져왔습니다. 시간이 없으신 분들은 문제 정의(ODQA task) , 그래프 모델링 그리고 Reranker파이프라인만 한 번 가볍게 살펴보셔도 좋을거 같아요.

적용하는 부분좋은 파싱 도구 , 좋은 리랭킹 도구가 있다한들 부족한 틈새가 있기마련인데요. 바로, 문서들간 관계가 틈새 중 하나가 되지 않을까 싶네요.최근 진행된 ifkakao24 에서도 이 틈새에 대해 이야기합니다. 문서 Chunking 시 발생하는 맥락 유실 보완방식 중 하나로 지식그래프가 언급되었습니다.

유저 질의에 기반해 답변에 도움이 될만한 메타(문서)들을 가져온다한들 그 문서들간 중복되는 메타들이 있기 마련입니다. 이는 곧 답변 생성에 노이즈로 작용할 가능성이 있기에, 문서들간 공통 개념들을 추출해 직접적으로 관련이 없는 문서라 할지라도 간접적으로 연결한 뒤 만들어진 문서 그래프를 리랭킹 과정에 활용한다는게 본 논문의 핵심입니다.

** 문서들간 관계를 만드는 방식을 본 포스팅에서 다루기엔 양이 방대하여, 이를 다룬 글을 첨부합니다. (https://inblog.ai/graphwoody/graphrag-with-document)

이번 오마카세 요리는 원문과 제 관점 한 스푼을 함께하는 형태로 음미해보겠습니다.

Even though it is successful in fetching relevant documents, RAG is not able to utilize connections between documents. In the ODQA setting, this leads to the model disregarding documents containing answers, a.k.a. positive documents, with less apparent connections to the question context. We can identify these documents if we connect them with positive documents whose context is strongly relevant to the question context.

질의와 관련된 문서들을 가져왔을때, 메타를 자세히 살펴보면 중복되어 있는 문장 그리고 단어들의 비율이 높다면 이를 어떻게 하면 좋을까요? 직관적으로 떠오르는건 해당 메타(문서)의 타이틀을 확인해서 질의와 얼마나 관련있는지 등 추가적인 검증부터 고려하실텐데요. 여러 검증 수단 중 하나로 본 논문은 그래프를 활용합니다. '어떻게?' 라는 호기심을 유지한채 조금 더 읽어볼게요.

Figure 1이 이 논문의 핵심입니다. G-retrieval(https://arxiv.org/abs/2402.07630) 논문 읽으신 분들은 다른 부분 몇몇을 볼 수 있으실텐데요. 1.Data flow의 처음이 Q&P 라는 점 2. AMRs 를 활용해 그래프를 만들었다는 점 3. Reranker 가 추가되었다는 점입니다. 동일하게 Graph 관점을 활용해 GNN retrieval 한다는 공통점이 있지만, 그래프 모델링과 Reranker라는 관점이 다른데요. 이 차이점을 잘 기억해두시면 좋을거 같습니다.

To address these challenges and limitations, we propose a method based on document graphs, where each node represents a document, and each edge represents that there are common concepts between two documents. We incorporate the connection information between different documents into the edge features and update the edge features through the message-passing mechanism. For node features, even though we aim to add AMR information to compose a richer understanding of complex semantics, we won’t overwhelmingly add all AMR-related tokens as node-level features. Instead, we investigate the determining factor that facilitates the reranker to identify more relevant documents and encode this key factor to node features

그렇다면 결국 그래프 생성이 중요할텐데, 여기에선 AMR (Abstract Meaning Representation) 방식을 활용해 그래프를 만듭니다. 간단하게 말해보자면, 문서 내 구문 분석을 한 뒤 분석 결과인 의미들을 활용해 그래프를 만듭니다.

저희가 흔히 아닌 문장 내 개체를 추출해서 그래프를 만드는 NER(Named entity recognition) 과 유사한데요. 큰 차이는 "NER extracts entities, while AMR models the deeper meaning and relationships within the entire sentence." 라고 할 수 있습니다. 객체를 추출하고 객체들간 연결을 만드는 것이 아닌, 구문 분석을 통해 계층을 만드는 게 핵심입니다.

To improve RAG for ODQA, we propose a document-graph-based reranker that leverages connections between different documents. When the documents share similar information with their neighbor nodes, it helps the reranker to successfully identify the documents containing answer context that is only weakly connected to the question. 2. We introduce new metrics to assess a wide range of ranking scenarios, including those with tied ranking scores. The metrics effectively evaluate this scenario by diminishing the optimistic effect brought by tied rankings. Based on these metrics, our proposed method outperforms state-of-the-art and requires fewer computational resources. 3. We assess the performance of a publicly available LLM (PaLM 2 [9]) as a reranker, exploring variations across different model sizes. We find that excessive ties within the generated ranking scores hinder the effectiveness of pre-trained large language models in improving RAG through reranking.

위 원문에도 볼드체로 표시를 해놓았지만, 중요한 문장이기에 한 번 더 짚고 넘어갈게요. 문서들간 유사한 정보들을 가지고 있다면 당연히 연결이 되어있을것이고, 이 연결을 기반으로 reranker 가 답변 생성에 도움이 될 만한 문서인지를 판별합니다. reranker 를 활용하기 위해선 정량화가 되어야할텐데, 이때 GNN을 활용하는거죠.

1) Path Identification: Firstly, the shortest single source paths (SSSPs) are determined starting from the node labeled "question" in the AMR graph Gqpi . Each path identified should not be a subset of another. For instance, consider the following paths composed of node concepts: [‘question’, ‘cross’, ‘world-region’, ‘crucifix’, ‘number’, ‘belocated-at’, ‘country’, ‘Spain’], [‘question’, ‘cross’, ‘religion’, ‘Catholicism’, ‘belief’, ‘worship’]; 2) Node Concept Extraction: Subsequently, the node concepts along these identified paths are extracted to construct ai . In the example provided, ai is formed as follows: "question cross world-region crucifix number be-located-at country Spain religion Catholicism belief worship". X ∈ R n×d (2) will be the initial node representation of graph neural networks.

GNN는 다들 잘 아시다시피 노드들간 정보 교류를 통해 그래프 내 노드의 고유성이 숫자로 표현되는 기법인데요. 이때 정보 교류에 크게 영향을 주는 요소들은 node feature , edge feature 입니다. 정보 교류마다 어떤 노드로 부터 왔고 이 노드와 정보 교류가 발생하는 노드는 어떤 관계인가가 중요하기 때문이고, 이 정보를 node , edge feature 라고 보시면 됩니다.

1차적으로 AMR이 총체적인 구조를 디자인해서 정보 교류를 위한 다리를 놓았다면, 2차는 다리에 어떤 자동차들이 무슨 짐을 실으면서 운반하는지를 디자인하는 단계입니다. 본 논문에서는 Question 정보와 Document text를 가공해서 “question:<question text><document text>” 형태로 만들어주고 이를 node feature로 활용합니다. 그렇다면 GNN 정보 교류 단계에서는 자연스레 question 정보와 document 정보를 모두 반영됨을 짐작할 수 있겠네요.

이렇게 완성된 GNN 임베딩 값을 이제 학습합니다. question <-> document GNN 결과물 방식을 cross entropy loss 방식으로 학습하면 좋겠으나, 아쉽게도 어느 곳에서나 발견할 수 있듯이 ground truth (labeled) 데이터가 불균형 분포를 띄고 있기에 pair-wise ranking loss 를 활용합니다.

이렇게 잘 학습된 모델을 활용해 문서들을 retrieval 하게된다면, 이제 문서들간 필터링 하는 작업(리랭킹)을 해야합니다.

서두에서 언급한 새로운 reranker 는 tied ranker 를 개선하기 위해 Optimistic {r_p^(t)} 와 Pessimistic {r_p ^(t) +t-1} 가 반영된 버전입니다. 여러 문서들을 가져온 뒤 LLM을 활용해 관련성 점수를 측정할텐데, 이때 tie ranking이 문제가 된다는거죠.

여기까지 정리 한 번 해보겠습니다.

유저의 질의와 문서를 파싱하여 AMR 그래프를 생성한 뒤, 문서 내 연관된 객체들을 탐지하고 문서 간 그래프를 연결합니다. 이 과정에서 <question, question-related document>를 노드 특성(node feature)으로 활용합니다.

또한, GNN 학습을 위해 pair-wise loss 함수를 손실 함수로 사용하여 질의와 문서 간의 연관성이 임베딩에 반영되도록 학습합니다. 마지막으로, 학습된 tied reranking을 위해 개선된 reranker 함수를 사용하여 최종 결과를 도출합니다.

예를 들어 위 Question과 같이 Ol' Blue Eyes is the nickname of?라는 유저 질의가 들어온다면, Number of Positive documents 의 숫자와 같이 관련있는 문서들이 도출될 것이고, 이때 각 문서들간 관련성을 엄밀하게 확인하기 위해 개선된 reranker를 활용할 겁니다.

가장 상위로 등장하는 문서를 살펴보면 question에 있는 내역들과 관련있는 문서가 어느 문단에 존재하며 구체적으로 AMR graph 에서는 어떤 노드 , 엣지로부터 발생했는지 확인할 수 있습니다.

오늘은 문서 데이터를 RAG에 적용할 때 발생하는 문제 중 하나인 Chunk 정보 유실에 대한 대안으로 GraphRAG 방법론을 살펴보았습니다. 이 방법론은 AMR을 활용해 문서 내 구문을 그래프로 1차 표현한 뒤, 문서 간 공통되거나 유사한 요소들을 발견해 연결하고, GNN을 활용해 임베딩하는 방식입니다.

특히, question과 document text를 결합해 이를 경로(path)로 간주하고, text encoder를 사용해 정량화한 뒤 노드 특성(node feature)으로 활용한다는 점이 인상적이었습니다. 또한, LLM을 reranker로 활용할 때 여러 문서 간 발생하는 tie ranking 문제를 개선한 새로운 metric도 참신한 접근이었습니다.

평소라면 놓쳤거나 생각치 못했을 법한 가려운 부분들을 다뤄주었기에 여러분들에게도 도움이 되지않을까 하는 생각에 다뤄봤는데요. 어떠실지 궁금하네요. 인사이트가 있는 시간이였기를 기원합니다. 그럼 이번 한주도 고생많으셨고, 다음 한주도 화이팅입니다.