24년 8월 1주차 그래프 오마카세

Signal processing on simplicial complexes (3)

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

배지훈

• 안녕하세요 ! 정말 무더운 여름인 것 같은데, 다들 건강하게 지내시고 계신가요? 제가 현재 지내고 있는 일본의 날씨는 밖에 잠깐 서있기만 해도 땀이 주루룩 날 정도로 상당히 무더운데, 한국 날씨는 어떠할 지 궁금하네요.
• 이런 더위를 좀 식혀드릴 수 있는 오마카세의 식후 음료로써, 7월 3~4주 오마카세로 전달해드렸던 내용을 어떻게 활용해볼 수 있는지 다음 논문의 마지막 챕터를 통해 가볍게 살펴보고자 합니다.
• 마찬가지로 그 전에, 간략하게 이전 포스트 내용(Hodge Laplacian & Decomposition) 을 살펴보면서 상기시켜보면 좋을 것 같습니다.

Recaps to previous post

Hodge Laplacian matrix as a shift opertor for simplicial complexes

• 7월 3주차 오마카세에서 전달해드린 바운더리 연산자 (Boundary operator, B_k)를 먼저 상기시켜보면, 다음 연산자는 다른 차수의 Simplicial complexes (0-simplex : Node, 1-simplex : Edge, 2-simplex : Triangle ..) 간의 포함 관계 (Incidence relationship)를 인코딩하고 있으며, 그 원소 부호 및 값들은 방향성 여부를 포함하여 얼마나 서로에게 기여하고 있는지를 나타내는 것으로 설명드렸습니다.
• 다음 바운더리 연산자를 조합하여, 그래프 신호 처리 (GSP)의 shift operator (e.g. graph Laplacian)를 Simplicial complexes로 확장시킨 Hodge Laplacian matrix를 정의하였습니다. 엣지 신호의 경우 (1-Simplicial complex), 다음 행렬은 아래와 같이 정의해볼 수 있었습니다.

• 다음 식에서 얻을 수 있는 정보는 앞의 항은 해당 Simplicial complex의 노드(0-simplex)와 엣지(1-simplex) 간의 포함 관계를 나타내며(=일반 그래프의 경우와 동일함), 추가적으로 후자 항을 통해 엣지(1-simplex)와 삼각형(2-simplex) 간의 포함 관계를 나타내는 것입니다.

Hodge Decomposition

• graph Laplacian (= 0-Hodge Laplacian)과 동일하게, 다음 행렬도 고유분해를 통해 스펙트럼 관점에서 다양한 특징들을 얻어낼 수 있었습니다. 다음 고유분해는Hodge Decomposition으로 정의되며, 호지 이론(Hodge Theory)에 근거하여 1-simplex의 신호를 3가지 직교 하위공간으로 분해할 수 있었습니다. 각각의 공간은 'Gradient space', 'Curl space', 그리고 'Harmonic space'로 칭해지며 이들 내부에서 고유하게 해당 신호를 다양하게 해석해볼 수 있었습니다. k=1의 엣지 신호에 대해 고려해보았습니다.

• Gradient space : Im(B_1^T) –> 두 노드 사이의 Potential difference에 따라 이들을 연결하는 엣지 상으로 흘러가는 Gradient flow가 존재하는 공간이었습니다. 노드로부터 엣지로 흘러간다는 개념을 생각해보면 non-cyclic한 관계이기 때문에, non-cyclic space로도 생각해볼 수 있습니다.
• Curl space : Im(B_2) –> 노드 및 엣지로 구성되는 삼각형 상의 local circulated flowing하는 신호들이 존재하는 공간이었습니다. 이로부터 Curl space는 cyclic space에 해당하며, Gradient space와 직교하는 공간입니다.
• Harmonic space : Ker(L_1) –> Gradient & Curl space에 존재하지 않는, 해당 Simplicial complex 상에서 모든 엣지를 따라 Global circulated flowing하는 신호들이 존재하는 공간이었습니다. 마찬가지로 cyclic space에 속하지만 Curl space와 직교하는 공간입니다.
• 중요한 포인트로, 다음 3가지 하위 공간들은 모두 1-Hodge Laplacian의 고유벡터 (Eigenvectors) 하위 집합들로부터 스팬(span)됩니다.
• 위의 직교 공간들로부터 파생되는 엣지 신호에는 당연하게 High-frequency (or high variation, e.g. noise)이 존재할 수 밖에 없을 것입니다. 하지만 여러 어플리케이션 (signal classification & detection) 상에서, 우리가 주로 관심 있는 것은 서로 유사한 신호 (혹은 smooth signal)를 포착하는 것일 수 있습니다.
• 이러한 관점으로부터, 다음 논문에서는 Simplicial complexes 상의 signal smoothing 및 denoising 방법에 대해 소개해주고 있습니다.

Application 1 - Flow smoothing and denoising

• 단순하게 가우시안 노이즈가 존재하는 Noise signal (f, Fig 4 참고)을 고려해보도록 하겠습니다.
• 결국 우리가 하고자 하는 것은 이러한 노이즈 신호 가운데 참 신호 (true signal, f^hat)를 복원하는 것입니다. 따라서 일반화를 위해 일반적인 그래프 최적화 식에 정규자 (Regularization)를 추가하여 아래와 같은 목적 함수를 정의합니다.

여기에서 Q matrix는 shift operator로 선택되어지며, alpha 파라미터는 정규자의 기여도를 조절하는 역할을 담당합니다.

다음의 최적 해는 (I + alpha*Q)^-1f로 주어집니다.

• 결국, 우리에게 주어진 일은 "얼마나 적절한 Q matrix (as shift operator)를 선택하는 가?"에 달려있습니다. 본 논문에서는 3가지 경우의 Q matrix를 고려합니다. (graph Laplacian : L_{LG} = B_0B_0^T / edge Laplacian : L_{e} = B_1^TB_1 / 1-Hodge Laplacian : L_1 = B_1^TB_1+B_2*B_2^T).
  • Fig 4와 같이, 결론적으로 1-Hodge Laplacian이 가장 좋은 성능을 달성합니다.
  • graph Laplacian for Line graph, L_{LG} : 그래프의 노드 간 유사도 (smoothness)를 포착하는 데 적합한 shift operator. 하지만, Simplicial complex 상에 존재하는 방향성 (orientation)을 고려하지 못함. 또한 Fig 4의 Line graph (unweighted)의 경우, 각 엣지로 흘러들어가는 다른 flowing signal의 relative weight 경우를 포착할 수 없음
  • Edge Laplacian, L_{e} : 해당 라플라시안의 정규자 형태를 통해 분석해봅시다.
    • Quadratic form as regularizer : f^T L_{e} f = f^TB_1^TB_1 f = ||B_1*f||² .
    • {B_1*f}를 바라보면, 한 엣지로부터 다른 엣지로 넘어가는 노드에 흘러가는 Divergence flow, 한 노드에 대한 inflow & outflow, 를 나타내며 이들만 peneralized하게됩니다. 즉, Gradient flow와 마찬가지로 non-cyclic하기 때문에 모든 cyclic flow (e.g. curl & harmonic flow)는 무시되며, 이로부터 Simplicial complex의 일정 특성을 추출하지 못합니다.

• 1-Hodge Laplacian, L_1 : 바운더리 연산자를 통해 L_{LG}의 방향성 문제도 해결하고, 추가 정규자 (||B_2^T f||²)가 존재하기 때문에 L_{e}의 penalized error를 해결함으로부터 위의 두 shift operator보다 더 좋은 결과를 얻어낼 수 있습니다. 즉, 1-simplex에 대한 smoothing & denoising signal을 얻어내기 위한 최적의 shift operator로 고려될 수 있습니다.
• 위의 설명을 간략하게 정리해보면, Simplicial complex의 엣지 신호를 잘 추출할 수 있는 L_1 기반 필터는 "전체 Simplicial complex의 방향성 정보 및 2-simplices와의 관계성"을 모두 고려할 수 있는 장점을 가지고 있습니다. 적절한 2-simplices가 구축되었을 경우, 엣지 신호의 주파수 응답 (frequency response)을 형성하는 추가적인 모델링의 flexibilty를 가질 수 있기 때문에 결국 필터링 성능 향상의 효과는 Hodge Laplacian의 고유값으로부터 많은 영향을 받는다는 사실을 알 수 있습니다.
• 본 논문에서는 Interpolation & Semi-supervised learning 관련한 설명도 제공하고 있습니다. 관련 주제에 대해 관심이 있으신 독자분들께서는 해당 세션을 꼭 참고해주시기 바랍니다 !

Simplicial neural networks

• 우리에게 주어진 데이터로부터 필요로 하는 부분을 잘 추출할 수 있는 Hodge Laplacian 기반 linear filtering을 정의할 수 있었기에, 자연스럽게 다음 필터에 비선형성을 추가하여 Convolutional operation을 구축하는 쪽으로 주제를 옮겨볼 수 있을 것입니다.
• Graph Convolution operation의 정의로부터, k-simplex의 신호에 대한 단순한 Simplicial Convolutional operation 은 아래와 같이 recursively하게 정의할 수 있습니다.

여기에서 H는 Y_k 입력 신호에 대한 적절한 shift operator의 다항식 행렬이 해당되며, W 및 \sigma 표기는 각각 학습 가능한 가중치 행렬 및 비선형성 함수를 나타냅니다.

• 모든 Simplicial complex는 방향성을 가지고 있기 때문에, 다음 속성을 반드시 고려하는 것이 중요합니다. 다행히, Hodge Laplacian의 기저가 되는 바운더리 연산자 속에 다음 방향성 정보를 잘 인코딩하고 있기 때문에 자연스럽게 H = Hodge Laplacian 선택은 다음 문제점을 쉽게 해결할 수 있습니다.
• 하지만 비선형성 함수를 통과할 때 다음 방향성 정보가 손실될 수 있으며 성능 하락의 원인이 될 수 있습니다. 따라서, 정의된 방향성에 적합한 비선형성 함수 (e.g. Odd function)를 선택하는 것이 중요하며, 그로부터 해당 아키텍처의 비선형성이 부여된 방향성에 대한 Equivariant 속성을 부여할 수 있습니다.
• 위의 기본 Simplicial neural network의 변형은 Hodge Laplacian matrix의 2가지 항 (B_k^TB_k , B_(k+1)B_(k+1)^T) 각각에 대한 다른 가중치를 허용하거나 (e.g. Simplicial Attention networks), 모든 k차원 상에서 연산되는 신호 각각에 대한 가중치를 계산하여 다르게 집계하는 방법 등이 있습니다. (e.g. 'Simplicial 2-complex convolutional neural networks')

Further relations to dynamical systems on graphs and simplicial complexes

• GSP의 관점에서, graph Laplacian은 네트워크 정보 및 트래픽의 흐름, 확산 과정을 잘 표현할 수 있는, linear dynamic systems과 깊은 연관을 가지고 있습니다. 대표적으로 Graph Heat Kernel 개념이 존재하죠.
  • 예를 들어, 소셜 네트워크의 어떤 사용자가 올린 게시글이 너무 좋아서 많은 주변 지인들 혹은 관련 사람들로부터 공유될 수 있고, 그 글이 그 주변 사람들에게 또 공유되는 동적 시스템을 생각해볼 수 있습니다.
  • 즉, 한 명의 사람이 source point가 되고 그 게시글을 energy라고 생각한다면 다음 energy가 주변 사람들 (neighbor points)로 쭉 퍼진다고 상상해보면 좋을 것 같습니다.

소셜 네트워크의 각 사람을 노드, 이웃 관계를 엣지로 정의하여 그래프를 표현해본다면, 다음은 그래프 상에서 흘러가는 flow 간의 dynamic operation이 구축되는 것이며, 아래와 같이 수학적으로 모델링할 수 있습니다.

• 다음 식을 보고, 저는 바로 Graph Heat Kernel 개념을 떠올렸습니다. 즉, 식 29의 벡터를 필터링된 그래프 신호로 동등하게 해석할 수 있고, 좀 더 구체적으로, 모든 양의 실수 시간 t에 대하여 현재 신호 벡터를 초기 신호 벡터의 Low-pass filtering 버전으로 해석해볼 수 있습니다.
• 일반 그래프 상에서의 graph Laplacian을 너머, 더욱 복잡한 higher-ordered Complex의 신호를 Hodge Laplacian으로 모델링해볼 수 없을까요? 다음 논문에서는 L = Hodge Laplacian으로 설정하였을 때, 특정 조건 하에서 다음의 Hodge decomposition으로부터 주어진 Harmonic space 상으로 해당 신호가 맵핑되었을 경우 가능함을 입증하였습니다.

" In particular, if the simplicial complex has exactly one hole, then for any initial condition, the system will converges to a vector that spans the harmonic subspace."

• 저자들은 다음 사실을 Simplicial complex가 오직 1개의 구멍(H_1 = 1)을 가지고 있을 경우, 임의의 초기 신호에 대하여 해당 Harmonic space를 스팬(span)하는 벡터로 수렴하게 된다고 설명해주고 있습니다.
• 즉, Simplicial complex의 dynamic system은 Hodge Laplacian으로부터 파생되는 Harmonic space 상의 신호로 맵핑되는 Low-pass filter으로부터 추출되는 low-frequency의 조합으로 표현될 수 있음을 이해해볼 수 있습니다. 다음은 graph Laplacian의 Low-pass Graph Heat Kernel의 속성을 그대로 유지하면서 확장된 차원에서 적용 가능함을 암시하고 있습니다.
  • Harmonic signal이 임베딩하고 있는 Simplicial complex의 Global information에서 Similarty 속성이 적합하게 적용 가능한 사례 활용을 고려해볼 수 있을 것 같습니다. 대표적으로 Simplicial Clustering 방법에 활용되고 있습니다.
  • 하지만, 논문에서 설명한 것과 같이 해당 Complex 상에 구멍이 1개 존재하는 등의 특정 조건을 만족하는 사전 정보 (Prior information)가 요구될 수 있다는 점을 고려해주셔야 합니다.

• 이번주 오마카세의 내용까지 해서, 전반적인 Simplicial complex의 개념과 중요한 속성, 그리고 엣지 신호 관점에서 적용해볼 수 있는 사례들을 위 논문의 설명을 기반으로 전달해드렸습니다. 기존 노드만의 관계성을 고려하는 방법을 확장하여 더 많은 요소들과의 관계정보를 추출함으로써 많은 적용 사례들로부터 활용해볼 수 있는 특징을 풍부하게 제공할 수 있다는 장점이 상당히 인상깊었던 것 같습니다.
• 실제 수많은 네트워크 상에서 고려될 수 있는 엣지 상으로 흘러가는 정보의 흐름을 기준으로 설명을 드렸으나, 물론 노드 뿐만 아니라 2-simplex 상의 복합적 구조정보를 기준으로 접근해볼 수 있을 것이며 (3D Graphics - Mesh, Polygon shape object etc..) 그로부터 데이터 상의 발견하지 못했던 새로운 인사이트들을 얻어갈 수 있지 않을까 라는 생각을 가지고 있습니다 !
• Topological Data Analysis (TDA)이 기존 머신러닝/딥러닝 관점에서 상대적으로 가질 수 있는 이점은, 지속성 다이어그램 (Persistence Diagram) 등의 다양한 핵심 도구를 통해서 토폴로지 관점에서 그래프 데이터 및 모델 동작을 직접적으로 해석이 가능하고(Interpretable), 그래프 뿐만 아니라 이미지 & 포인트 클라우드와 같은 다양한 데이터 타입도 커버할 수 있는 유연성(Flexiblity)를 가지고 있습니다.
• 특정 한 도메인에 국한되어 전달해드리지 않고, 최대한 다양한 관점에서 주어진 데이터에 접근할 수 있고 여러가지 관점에서 해석해볼 수 있는 재밌는 다양한 내용을 담아서 전달해드릴 수 있도록 하겠습니다!
• 글을 마무리하기에 앞서, 그래프 오마카세를 함께 만들어나갈 마음이 있으신 분들을 구하고 있습니다. 그래프 주제로 글 연재하는 것에 관심이 있으신 분들께서는 언제든지 제 메일주소로 편하게 연락주시면 감사하겠습니다 !

[Contact Info]

Gmail : jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn

Llama3.1 , NIM 그리고 Neo4j full-text search 를 활용해 GraphRAG agent 만들기.

원글 : https://bratanic-tomaz.medium.com/build-a-knowledge-graph-based-agent-with-llama-3-1-nvidia-nim-and-langchain-feb65788e637

코드 : https://github.com/tomasonjo/blogs/blob/master/llm/nvidia_neo4j_langchain.ipynb

정이태

KG-based agent , Llama 3.1 , Nvidia NIM 그리고 Langchain 을 활용해 FDA Adverse Event Reporting System (FAERS) 데이터를 기반으로 GraphRAG 를 구현한 내용이 주요골자인 포스팅입니다.

주목하실 부분은 chatbot 을 구현하기 위해 GraphRAG 의 Retrieval 를 어떻게 설계했는가 인데요. 제가 평소에 좋아하는 '왜?' , '그래서 무엇을?' 논리가 포스팅에 담겨있어 더더욱 재밌게 봤네요.

또한, 기존 GraphRAG 게시물에서 주로 다룬 vector , cypher search 가 아닌, full-text search를 활용한 GraphRAG Agent 디자인 그리고 설계하는 방식을 다룹니다.

핵심을 말씀드리자면,

1.유저의 질의는 시시각각 달라진다. 때문에, 이 유연성을 잘 감지하여 좋은 답변을 내놓는게 chatbot 의 핵심이다. 그럼 이 유연성을 무엇으로 감지할 것인가? 바로 'full-text search'를 활용한 pre-defined rule이다.

2.query generation의 핵심은 context , constraint 조화이다. 이를 위해 input parameter마다 각각의 logic을 설계한 Logic layer 를 활용한다. 이때, function calling 특성을 잘 활용하기 위해 구현된 open-source(llama3.1) & NIM 를 사용한다.

3.drug, min_age, max_age, manufacture 4가지 input을 받아서 이에 따라 filter rule을 적용하는 함수인 get_side_effects 기반으로 search criteria를 판단하고 이를 retrieval 하여 LLM context로 주입하여 답변을 얻는다.

Filter rule code

@tool
def get_side_effects(
    drug: Optional[str] = Field(
        description="disease mentioned in the question. Return None if no mentioned."
    ),
    min_age: Optional[int] = Field(
        description="Minimum age of the patient. Return None if no mentioned."
    ),
    max_age: Optional[int] = Field(
        description="Maximum age of the patient. Return None if no mentioned."
    ),
    manufacturer: Optional[str] = Field(
        description="manufacturer of the drug. Return None if no mentioned."
    ),
):
    """Useful for when you need to find common side effects."""
    params = {}
    filters = []
    side_effects_base_query = """
    MATCH (c:Case)-[:HAS_REACTION]->(r:Reaction), (c)-[:IS_PRIMARY_SUSPECT]->(d:Drug)
    """
    if drug and isinstance(drug, str):
        candidate_drugs = [el["candidate"] for el in get_candidates(drug, "drug")]
        if not candidate_drugs:
            return "The mentioned drug was not found"
        filters.append("d.name IN $drugs")
        params["drugs"] = candidate_drugs

    if min_age and isinstance(min_age, int):
        filters.append("c.age > $min_age ")
        params["min_age"] = min_age
    if max_age and isinstance(max_age, int):
        filters.append("c.age < $max_age ")
        params["max_age"] = max_age
    if manufacturer and isinstance(manufacturer, str):
        candidate_manufacturers = [
            el["candidate"] for el in get_candidates(manufacturer, "manufacturer")
        ]
        if not candidate_manufacturers:
            return "The mentioned manufacturer was not found"
        filters.append(
            "EXISTS {(c)<-[:REGISTERED]-(:Manufacturer {manufacturerName: $manufacturer})}"
        )
        params["manufacturer"] = candidate_manufacturers[0]

    if filters:
        side_effects_base_query += " WHERE "
        side_effects_base_query += " AND ".join(filters)
    side_effects_base_query += """
    RETURN d.name AS drug, r.description AS side_effect, count(*) AS count
    ORDER BY count DESC
    LIMIT 10
    """
    print(f"Using parameters: {params}")
    data = graph.query(side_effects_base_query, params=params)
    return data

이외에도 NVIDIA Gen AI example 을 보시면 다양한 오픈소스 예제와 Enterprise RAG 예제 , Developer RAG 예제 등이 있습니다. 인프라에 대해 지식이 해박하신 분들은 example 를 클론코딩해보시면서 감을 익히시고, 속해있는 조직에 바로 적용해도 무리가 없을만큼 굉장히 친절하게 잘 되어 있습니다.
https://github.com/NVIDIA/GenerativeAIExamples?tab=readme-ov-file#open-source-integrations

기술들이 하루가 멀다하고 너무 빨리 발전하고 있네요. 새로이 나온 기술들을 모두 살펴보기엔 저희의 시간은 유한합니다. 때문에, 대략적인 흐름을 살펴보고 무슨 기술이 나에게 그리고 내가 속한 조직에 유의미할 것인가를 신속하게 분별하고 적용해야합니다.

저는 이를 위해 주로 빅테크 기업들의 블로그, 컨퍼런스 등을 살펴보는데요, 오늘은 그 중 nvidia NIM과 neo4j application 가 결합된 게시물에 대해 다뤘습니다. 다음에는 nvidia cugraph 생태계와 GraphRAG연관성에 대해 분석해보고 공유드리겠습니다. 긴 글 읽어주심에 감사드립니다.