24년 10월 4주차 그래프 오마카세

On the Expressivity of Persistent Homology in Graph Learning

paper link : https://arxiv.org/pdf/2302.09826

Index

  • Properties of Filtrations
  • The Weisfeiler-Leman Hierarchy
Graph filtration from degree info
  • 이전에는 단순 데이터의 Statistical analysis의 descriptor로만 사용되었던 토폴로지 기법들은 딥러닝 시대에 들어서면서 일명 토폴로지 딥러닝 (TDL) 이라는 도메인이 정의될 정도로 그 잠재성을 크게 인정받고 최근 많은 연구들에서 데이터 속의 내재된 토폴로지 특성을 최대한 활용하려는 움직임이 보이고 있습니다.
    • 지속성 호몰로지의 핵심 모듈인 필트레이션을 통해 다중 스케일에서의 토폴로지 특성의 변화를 추적하고, 긴 지속성을 갖는 특징 포인트를 벡터화(Vectorization) 기법을 통해 추가 정보 혹은 제약 조건 등으로 다양하게 활용함으로써 성능 개선 방법들을 쉽게 찾아볼 수 있습니다.
    • 단독으로 토폴로지 기법을 활용하기에는 파라미터 튜닝의 어려움, 연산량, 접근성 등의 해결해야 할 문제점들이 많이 남아있지만 앞으로의 활용 가능성이 나아질 것이며, 특히 그래프 신경망과 통합되었을 때 그 시너지가 정말 좋아질 것으로 생각합니다.
  • "Computational algebraic topology라는 두터운 수학적 이론을 기반하는 호몰로지는 어떻게 그래프 이론을 기반으로 정의되는 그래프 컨볼루션 신경망 모델들과 잘 통합될 수 있을까? 우연의 일치인가?" 라는 궁금증이 남아있었습니다. 하지만, 그 답변을 명쾌하게 밝혀낸 논문을 찾는 것은 어려울 뿐더러, 찾아낸 기존 논문들의 디테일한 설명을 완벽하게 이해하는 것 또한 정말 많이 어려웠습니다.
  • 이번 주 오마카세에서 전달해드릴 논문의 내용은 그래프 학습 문제들에서 지속성 토폴로지의 표현력(Expressivity)을 중심으로 자세한 이론적 논의 및 실험 결과 분석을 통해 위의 질문에 대한 답변을 제공합니다.
    • 해당 논문의 3, 4번째 섹션 ('Properties of Filtration', 'The Weisfeiler-Leman Hierarchy')을 중심으로 전달해드리고자 합니다만, 관심이 있으신 독자분들께서는 Appendix에서 제공하는 친절한 설명들을 꼭 읽어보시는 것을 추천드립니다.
💡
This paper intends to bridge the gap between computational topology and graph machine learning by providing a brief introduction to persistent homology in the context of graphs, as well as a theoretical discussion and empirical analysis of its expressivity for graph learning tasks.

Properties of Filtration

  • 토폴로지 표현력이라는 관점에서 본 논문에서는 크게 핵심적인 2가지 필트레이션의 속성, Stability, Functoriality,에 대한 이론적 논의를 제공합니다. 다음 속성이 만족되지 않는 경우 토폴로지 표현력이 크게 저하된다는 사실을 입증한 논문을 해당 링크로 걸어두었습니다.
  • Stability properties of filtration이란, 동일한 그래프 G에 대한 2가지 필트레이션 함수 f, g으로 뽑아낸 다른 결과의 지속성 다이어그램 (D_f, D_g)에 대하여, 두 다이어그램 상의 포인트 간 측정 거리의 상한으로 정의됩니다.
Stability of filtration
    • 다음 거리 메트릭으로 Bottleneck distance 및 Wasserstein distance을 활용합니다. 두 개념에 대한 자세한 설명 및 예시는 아래 링크를 확인해주세요.
Bottleneck and Wasserstein Distance · PersistenceDiagrams.jl
    • 즉, 지속성 다이어그램 상에 표현된 토폴로지 포인트(Topological quantity) 간의 기하학적 속성인 거리(distance)를 측정하여 Stability를 결정한다는 개념으로부터, 해당 속성의 중요한 키포인트를 아래 설명과 같이 확인해볼 수 있겠습니다.
💡
These stability properties are remarkable because they link a topological quantity with a geometrical one, thus underscoring how persistent homology itself incorporates both geometrical and topological aspects of input data.
  • Functoriality of filtration이란, 임의적인 필트레이션 함수 f를 선택하더라도 두 isomorphic한 그래프 G, G'에 대하여 동일한 지속성 다이어그램이 얻어진다는 사실을 나타냅니다. (증명 - Appendix D. Thoerem 2. 참고)
    • 이러한 사실로부터 얻을 수 있는 키포인트는 Isomorphic한 그래프 상에서의 다른 구조적 속성을 어떠한 필트레이션 함수를 사용하여 뽑아낸 결과 (지속성 다이어그램)은 항상 동일하다는 사실입니다. 이러한 필트레이션의 equivariant functionality와 지속성 호몰로지는 서로 호환 가능한 점을 논문에서 밑줄로 강조하고 있습니다.
💡
The theorem thus guarantees that persistent homology is compatible with equivariant function learning, pointing towards the utility of hybrid models that leverage different types of structural properties of graphs.
  • Theorem 1, 2와 그로부터 얻을 수 있는 키포인트들로부터 왜 토폴로지 특징이 수많은 다운스트림 태스크에서 중요하게 사용될 수 있는지를 알아볼 수 있었습니다. 다음 이론들에 대한 자세한 설명 및 증명은 Appendix D.에서 확인해볼 수 있습니다.

The Weisfeiler-Leman Hierarchy

  • 그래프의 표현력을 측정하는 데 널리 사용되는 1-WL test의 맥락에서 토폴로지의 표현력을 분석해봅시다.
  • 그래프 토폴로지를 분석하는 데 1-WL은 효과적이지 않습니다. 왜냐하면 그래프 상의 연결 요소 및 사이클 (0, 1-dim betti number, β_0,1) 차이를 구별하지 못하기 때문에 토폴로지 표현력 측면에서 non-isomorphic함을 포착해내지 못합니다.
    • 그 예시로, Appendix E.의 예시를 살펴봅시다.
      • 왼쪽 그래프 토폴로지 정보는 (β_0 = 2, β_1 = 2), 오른쪽 그래프 토폴로지 정보는 ( β_0 = 1, β_1 =1)이기 때문에 토폴로지 관점에서 non-isomorphic합니다.
      • 하지만 degree-based 1-WL로는 구별할 수 없습니다.
  • 그로부터, 본 논문의 저자들은 단일 노드에만 레이블링하는 알고리즘으로부터 계층적으로 k-node tuple (혹은 하위그래프)에 대한 레이블링 정보를 포함하는 WL-hierarchy로의 변형 알고리즘인 folklore WL test (k-FWL)을 활용합니다.
    • 식 2로 정의되는 k-FWL 알고리즘의 RELABEL 함수는 색상 튜플 중 특정 색상 값으로 맵핑해주는 단사함수이며, \phi는 k-node tuples (v)의 k번째 요소를 u로 바꾸는 함수로서 하위그래프 상의 노드 간 이웃 관계정보를 인코딩하는 역할을 수행합니다.
  • k-FWL 알고리즘이 특정 필트레이션 과정을 통해 일반화될 수 있는 사실을 Theorem 3과 같이 보임으로써, 결론적으로 지속성 호몰로지가 최소 k-FWL만큼의 표현력을 갖는다는 사실을 입증합니다. (증명 - Appendix D. Thoerem 3. 참고)
💡
Appendix E. shows examples of graphs that can only be distinguished via their topological features, thus proving that a topological perspective is strictly more expressive than 1-WL.
    • 차후 연구에서 Theorem 3를 확장하여 k-FWL보다 더욱 강력한 표현력을 갖는 지속성 호몰로지를 증명하는 것을 목표하고 있다고 합니다.
      • 더욱 강력한 토폴로지 표현력을 얻어내기 위한 확장을 위해, 일반적인 0 & 1-dim의 토폴로지 구별을 너머 (k+1)-dim의 토폴로지 (e.g. voids) 정보까지 구별할 수 있는 (k+1)-FWL을 정할 필요가 있습니다.
      • 이러한 인사이트는 해당 논문의 Tables 및 Appendix F. 'Additional Epxressivity Experiments'에서 잘 보여주고 있습니다.
💡
Overall, these results experiments underscore the high expressivity of persistent homology, making it a strong baseline for graph-learning tasks.

These results complement prior work on predicting properties of point clouds [16, 73], showing that topology-based graph-learning approaches carry a large degree of additional information about graphs.

  • 토폴로지 표현력을 측정하는, 1-WL의 hierarchical variant 알고리즘인 k-FWL을 통해 필트레이션의 내재적 중요도 및 가치와 지속성 호몰로지의 강력한 표현력을 이론적 증명과 실험적 결과로써 입증하였습니다. 그로부터 토폴로지 정보가 추가되었을 때, 다양한 태스크 문제에서 성능 향상에 도움이 되는 뒷받침 이유들로 충분히 커버할 수 있을 것 같습니다.
  • 본 논문에서는 강력한 표현력을 얻어내기 위한 몇가지 필수적인 요구사항들이 존재합니다. 그리고 만족해야 하는 조건들의 기준이 꽤 까다롭습니다.
    • (저자들이 차후 연구로 밝혔던,) k=2 이상의 더 복합적 토폴로지 정보에서의 표현력을 확인하기 위한 셋팅의 어려움 및 그 이론적 증거 부족. (실험적으로는 확인, Tables 참고)
    • 증명된 이론 상에서 반드시 미분 가능한 지속성 다이어그램의 결과로 이어지지 않음. 즉, 이러한 강력한 표현력의 장담이 end-to-end한 학습 기반 TDL에서 보장되지 않을 수 있음.
    • 논문에서 제시한 이론들을 통해 필트레이션의 중요한 속성들만 보여줄 뿐, 그 표현력에 대한 깊은 탐구가 이루어지지 않음. 이 역시 보장된다고 말할 수 없음.
  • 이러한 부분들은 점차 개선될 사항들이 될 수 있겠으나, 다음 논문에서 입증해준 저차원 지속성 호몰로지 (0-dim, 1-dim := β_0,1)에서의 보장된 표현력은 지금까지 제안되어져온, 그리고 앞으로 제안되어질 토폴로지 정보 활용 방법들을 충분히 뒷받침할 수 있는 이유로 바라볼 수 있을 것 같습니다.

[Contact Info]

Gmail : jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn

Subscribe for daily recipes. No spam, just food.