Sign in Subscribe
GraphOmakase

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

Simplicial Complex Representation Learning

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

배지훈

Index

  • Geometric Message Passing Schemes (GMPS) : AMPS, CMPS, HCMPS
  • Entire Simplicial Complex Learning : Simplicial Complex Autoencoders (SCAs), Learning Embedding
  • Simplicial complex 상의 복합적인 요소들을 한번에 집계하여 학습을 가능하게 한 신경망 모델, SNNs의 등장 이래로 수많은 학습 모델들이 많이 제안되어져 왔으며 자연스럽게 임베딩 메커니즘 연구까지 발전해오고 있습니다.
  • 그 흐름을 쉽게 파악해볼 수 있는 아래의 깃허브 링크를 확인해보시면 좋을 것 같아 추가해두었습니다. (해당 논문들을 모두 읽어보고 가능하다면 하나씩 오마카세로 다루어보고 싶은 마음이 있습니다.)
GitHub - Pseudomanifold/awesome-topological-deep-learning: A curated list of topological deep learning (TDL) resources and links.
A curated list of topological deep learning (TDL) resources and links. - GitHub - Pseudomanifold/awesome-topological-deep-learning: A curated list of topological deep learning (TDL) resources and…
GitHubPseudomanifold
  • 이번 논문에서는 Simplex complex 상 요소들 간의 Proximity를 잘 보존하고 있는 universial embedding space 상에 맵핑하는 함수 및 방법을 학습하는 메커니즘을 제안합니다.
  • 노드 및 엣지를 기반으로 하는 그래프 표현 학습와 달리, 추가적인 면(triangle), 사면체(tetrahedron) 등등의 확장된 요소들로부터 만들어지는 구조정보 및 차원 복잡도의 이유들 때문에 이 모든 것들을 아울러 표현 학습을 가능하게 하는 방법론을 쉽게 제안할 수 없었습니다.
  • 다음 저자들은 이 모든 것들을 맵핑할 수 있는 동일한 universial space를 찾는 Geomteric Message Passing Schemes (GMPS)을 정의하고,각각의 방식에 따라 모든 요소들을 임베딩하여 학습시킬 수 있는 autoencoder 모델을 제안합니다.
    • 구체적으로, Cell Complex networks(CXN)의 3가지 메세지 전달 방법 (AMPS, CMPS, HCMPS)을 주어진 Simplicial complex에 적용하여 각각 임베딩 벡터를 얻어내고, 그로부터 추출된 표현 정보 전체를 학습하는 Simplicial complex autoencoder (SCA) 신경망 모델을 제안합니다.

Geometric Message Passing Schemes (GMPS)

  • Fig 4에서 보이는 Cell complex networks (CXN)의 Cell complex 상에서 동작하는 학습 알고리즘 3가지 (AMPS, CMPS, HCMPS)를 simplicial complex에 적용할 수 있는 방법을 보입니다.
  • 여기에서 Cell complex은 Simplicial complex의 일반화 형태로써, triangulation으로만 표현되는 simplex 면의 제약성을 완화하여 cell이라는 다양한 형태의 면들로 표현할 수 있다는 장점을 갖습니다.
  • 각각의 알고리즘은 타겟으로 하는 Simplex 요소에 따라 다르게 선택될 수 있으며 (Fig 4의 초록색 표기 참고), 결과적으로 이는 단체 복합체의 최종 표현에 영향을 미칩니다.
  1. ADJACENCY MESSAGE PASSING SCHEME (AMPS)
Definition of AMPS
  • Fig 1은 초록색 타겟 노드를 업데이트 하기 위하여 해당 Simplicial complex의 인접 요소들을 모두 집계하는 방법을 보여주고 있습니다.
  • Simplicial complex에서 정의되는 Co-face 개념을 기반으로 {노드 - 엣지, 엣지 - 면} 사이의 Boundary operator (∂)를 활용하여 메세지 전달 과정이 있음을 확인할 수 있습니다. 여기에서 A_adj는 Simplicial complex를 표현할 수 있는 k-Hodge Laplacian이 사용될 수 있으며, M은 집계 함수를 나타냅니다.
  • 중요한 사실은 다음 AMPS은 저차원 요소로부터 고차원 요소로의 정보 흐름을 공통적으로 보이고 있다는 것입니다. 즉, 하나의 노드를 업데이트 하기 위해 주변 노드 및 연결된 엣지(co-face)를 모두 통합하며 그 엣지를 업데이트 하기 위해 주변 엣지 및 포함하는 면 (co-face)를 모두 통합하는 형식으로 반복적으로 수행됩니다.
    • 다음은 Boundary operator의 역할에 해당하므로, 위의 식을 통해서 쉽게 이해할 수 있는 부분이라 생각합니다.

" the information flow using AMPS (Equation 1) on the complex from the lower dimensional cells to the higher ones (= Boundary operator)"

  1. CO-ADJACENCY MESSAGE PASSING SCHEME (CMPS)
Definition of CMPS
  • 위의 AMPS와 매우 유사하게 정의되며, Face 개념을 기반으로 Co-boundary operator (∂T) 및 Co-adj matrix 을 활용하여 타겟 면 (triangle)을 업데이트 하는 방법을 정의하는 것으로 이해해볼 수 있습니다.
  • CMPS은 AMPS와 반대로, 고차원 요소로부터 저차원 요소로의 정보 흐름을 공통적으로 보이고 있다는 것 정도로 생각하면 좋을 것 같습니다.
  1. HOMOLOGY AND COHOMOLOGY MESSAGE PASSING SCHEME (HCMPS)
Definition of HCMPS
  • HCMPS는 이전 오마카세에서 다루어드렸던 것과 비슷하게, 엣지 업데이트를 대상으로 Face & Co-Face 요소들 (노드 및 면) 모두 고려하는 방법으로 이해할 수 있습니다. 즉, (Co-)Boundary operators 모두를 사용하여 정의되며, Fig 3을 통해서도 직관적으로 동작을 이해해볼 수 있을 것 같습니다.

Entire Simplicial complex Learning

  • 다음 논문에서 제안하는 Simplicial complex learning의 목적은 AMPS 방법을 활용하여 노드 레벨의 표현정보를 통해 전체 Simplicial complex 표현 정보를 얻어내는 것에 있습니다.
  • 그로부터 저자들은 AMPS-simplicial complex autoencoder (SCA) 구조의 새로운 학습 모델을 제안하였으며, 먼저 SCA의 3가지 구성 요소 (Enc-Dec , user-defined similiarity measure & loss function)에 대하여 설명합니다.
  1. Encoder - Decoder
  • 일반적인 인코더 - 디코더의 역할과 비슷하게, 다음 인코더는 잠재 공간에서의 모든 simplex (노드, 엣지, 면)의 표현 벡터 혹은 임베딩을 얻어내고 다음 디코더는 다른 요소들 사이 {노드 - 엣지, 엣지 - 면}의 유사도를 계산하여 그 연관성을 정량화합니다.
  • 다음 두 함수 (enc, dec)는 학습 가능한 함수입니다.
  1. A user-defined similarity measure
  • Enc-Dec 으로부터 정량화된 다른 simplex 요소들 사이의 학습된 유사도 관계를 평가하기 위한 지표 (sim(a,c))가 필요합니다.
  • 단순하게, 다음 user-defined similarity measure 함수는 인접한 요소들 사이의 유사도가 높음을 인코딩하는 인접 행렬 A_adj로 선택할 수 있습니다.
  1. A user-defined loss function
Loss function
  • CO[a,c]는 simplex a, c 각각의 Co-face 관계에 있는 요소들 집합들 간 교집합 요소들을 모은 집합으로 정의됩니다. (자세한 설명은 다음 글에서 생략한 Sec 2. SIMPLICIAL COMPLEX NEIGHBORHOOD MATRICES 부분을 참고해주시기 바랍니다.)
  • 모든 co-face 교집합 요소들에 대하여, 각각의 요소 a, c의 표현 벡터 및 user-defined similarity 간의 loss를 계산합니다. 다음 loss 함수 (l)은 아래의 다양한 SCA 방법에 대한 선택으로 결정되며, 전체 Loss는 다음 L_k의 합산 형태로 정의합니다.
  • 인코더 Enc 함수로부터 구해진 표현 벡터 z를 학습하여 표현 임베딩 h_X을 얻어내는 방법에 대하여 가중 합 형태로 아래와 같이 정의합니다.
Simplicial embedding h_X
    • 가중치로 정의되는 w_m은 Simplicial embedding (U_X)과 학습 파라미터 행렬 W로써 정의됩니다. 구체적으로, 다음 가중치는 아래와 같이 정의합니다.
weight function based on Bai et al.
    • 학습 과정에서 최소화 되는 목표함수는 두 요소의 임베딩 벡터 간 절대 거리와 Hausdorff distance와 같은 Simplicial complex 상의 거리 지표값을 정규화요소로 추가하여 아래와 같이 정의합니다.
Loss function for training h_X
  • 이번 오마카세로는 Simplicial complex을 잘 표현하는 임베딩 벡터를 학습하는 데 기존 그래프 표현 학습에서의 메세지 전달 메커니즘을 활용하는 방법을 직관적으로 이해하기 쉽게 제안한 논문을 소개해드렸습니다.
    • 간략하게, Fig 4에서와 같이 노드, 엣지, 그 이상의 Simplex 요소들을 Face & Co-Face 관계를 인코딩하는 (C0-)Boundary operator로부터 메세지를 전파하고, 순차적으로 타겟 요소를 업데이트하는 방법을 정의합니다. 구체적인 3가지 알고리즘 (AMPS, CMPS, HCMPS)들은 기존 CXN (Cell complex networks)의 알고리즘을 Simplicial complex에 맞추어 변형하여 사용합니다.
    • 다음 메커니즘을 기반으로 동작하는 SCA 모델을 제안하였으며, SCA의 인코더 단에서 거리 지표를 기반으로 임베딩 학습을 진행한 이후 유사도 함수 간의 차이를 최소화하는 방향으로 Fig 5와 같은 최적의 표현 벡터를 얻어낼 수 있습니다.
Experiment results of simplicial embedding learning
  • 기본적인 Complex 개념들 (Face, boundary) 및 그래프 표현 학습의 메세지 전달 메커니즘 정도만 이해하고 계시면 Figures의 그림을 통해서 직관적으로 쉽게 제안 알고리즘 및 모델 동작을 이해할 수 있을 것으로 생각됩니다. 또한 그래프 표현 학습에 관심이 많으신 독자분들께서 가볍게 짚고 넘어가기에 좋은 논문이라 생각합니다.

[Contact Info]

Gmail : jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn

Subscribe for daily recipes. No spam, just food.