Wavelet transformation (WT)에 대해서 알아보았으면, 이제부터는 본격적으로 WT를 graph에 어떻게 적용하는지 알아보자. 결국 signal processing을 graph에 대해서 수행하는지 알아보고자 한다. Graph는 위와 같이 여러개의 node로 구성되어 있으며, 이 node들이 임의의 edge를 통해서 다른 node들과 연결되어 있다. 이러한 domain이 주어졌을 때 signal이라는 것을 어떻게 정의할 수 있을까? 결국 WT을 하기 위해서는 transformation에 사용되는 basis를 설계할 필요가 있다. 그래서 graph를 signal로 이해하고 transformation을 적용하기 위해서는 가장 먼저 basis를 설계하고 이후에 transformation을 수행해야 한다. Basis는 우리가 하고자 하는 특정 task에 따라 서로 다르게 설계할 수 있다. 어떠한 task를 하든간에 basis를 미리 정의하는 일은 필수적이다.

그러나 우리가 실제로 다뤄야하는 signal은 time space나 image space와 같은 Euclidean space이다. 이는 곧 지금까지의 domain들은 전부 regular한 structure를 포함하고 있었다는 의미이다. 모든 것이 직선으로 설명이 가능했었다. 2차원의 image만 하더라도 $x$축과 $y$축을 기준으로 설명할 수가 있었다. 우리가 이번에 사용하는 graph domain은 이러한 규칙적인 구조를 지니고 있지 않다. 기본적으로 graph의 node가 여기서는 특정 domain이 될 것이다. 이러한 구조에서 scale과 translation을 어떻게 정의할 수 있을까? 우리가 Haar wavelet을 정의해서 사용한다고 하더라도 어디가 center가 될 수 있는 것일까?

결국 graph와 같이 non-Euclidean space에서 wavelet을 어떻게 정의하고, scale과 translation을 어떻게 정의할 수 있는지가 이번 내용의 핵심이라고 볼 수 있다. 위의 예시와 같이 어떠한 도시의 지도가 graph처럼 되어있다고 생각해보자. 각 node는 어떠한 대도시 속 작은 도시에 해당하고 이를 연결하는 길을 edge라고 생각하면 된다. 각 node는 결국 어떠한 signal을 가지고 있을 것이고, 우리는 Fourier transformation (FT)나 WT 등을 통해서 이러한 signal을 분석하기를 원한다. 가장 먼저 우리는 graph의 node에 대한 mother wavelet의 모양을 미리 정하고 정의해야 한다.

Mother wavelet은 center 영역에서 증가하고 감소하는 부분이 있고 나머지는 0으로 수렴하는 것이 일반적인 형태이다. 여기서 scale을 증가시키게 되면 frequency 상에서 basis는 더 줄어들게 될 것이다. Wavelet의 특징 중 또 다른 하나는 어디든 이동시킬 수 있다는 것이다. 만약 이러한 basis function을 우선순위로 정의할 수 있다면, 즉, 만약 graph에서 shape을 정의할 수 있다면, 결국에는 WT를 정의할 수 있게 된다. 그러나 graph의 node에는 어떠한 regularity도 존재하지 않기 때문에 이는 현실적으로 불가능하다. 이렇게 graph의 shape을 몰라 미리 정의해야하는 wavelet을 정의하기 어렵기 때문에 정말 혼란스러운 상황이 된다. 물론 이렇게 할 수 있는 방법이 존재하기는 하다.

Vertex set $V$와 edge set $E$, 그리고 edge가 가지는 signal $\omega$를 통해 표현되는 $G$라는 domain이 주어졌다고 해보자. 여기서 $\omega$는 vertex를 연결하는 edge weight를 나타낸다. 이제 우리는 time도 image도 아닌 graph라는 domain을 다루고 있고, 특히 이는 vertex set $V$에 의해 정의된다. 앞서 이야기 했듯이 graph space에서 basis를 구성하는 일은 feasible하지 못하다. 우리가 하고자하는 것은 frequency space에서 filter를 구성하는 것이고, 이 filter의 inverse transformation을 통해서 원래 space로 돌아오고 싶은 것이다. 이렇게 되면 결국 우리가 원하던 WT을 성공하는 것이다. WT은 frequency space에서 적용할 수 있는 filter에 의해서 정의가 되어 inverse transformation까지 수행할 수 있어야 한다. 이는 continuous space에서 정의되는 WT이고, 이를 graph space에서까지 정의하고자 한다. 실질적으로 graph space를 직접 다루는 것보다 frequency space에서 filter를 설계하고 inversion을 하는 것이 graph에서 WT을 수행할 수 있는 방법이 된다. 여기서의 filter는 band-pass filter이고, 우리는 filter의 모양을 frequency space에서 설계할 수 있다.

Signal은 기본적으로 time space에서 정의된다. 그리고 이를 이용해 문제를 풀기 어렵기 때문에 또 다른 space인 frequency space로 보내서 문제를 해결하고자 하는 것이다. Frequency space에서 문제를 해결하는 것이 더 쉽기 때문에 여기서 문제를 해결하고 다시 원래의 space로 transformation시키면 되는 것이다. 이때 wavelet을 구성하는 것은 time space에서 하는 것이 아니다. 특히, graph space에서는 더욱 어려울 것이다. Wavelet $\psi$는 frequency space에서 만들어지는 것이 더 쉬운 일이다. 나중에 이를 inversion 시키면 되기 때문에 원하는대로 filter를 만들기 위해서는 frequency space에서 $\psi$를 만들면 된다. 결국, graph에서 문제를 풀기 어렵기 때문에 다른 space에서 이를 해결하고 다시 graph space로 돌아오고자 하는 것이고, 이를 위해 graph에서 WT을 하기 위한 핵심은 바로 freuqency space에서 wavelet을 어떻게 구성할지이다.

그렇다면 가장 먼저 어떻게 graph를 frequency space로 보낼 수 있을까? 기존의 signal을 Fourier transform (FT)를 통해서 보냈듯이, 우리는 graph에서도 FT를 이용해서 frequency space로 보낼 수 있다. 우리는 이를 graph FT라고 부르고자 하며, 이를 위해서는 graph에서 정의되는 orthonormal basis가 필요하다. 기존의 FT에서는 $e^{j\omega t}$라는 Fourier basis를 이용해서 transformation을 수행했다. 여기서 $e^{j\omega t}$는 서로 orthogonal한 성질을 지니고 있다. 그렇다면 이러한 basis를 graph에서 어떻게 정의할 수 있을까?

Graph에서의 basis를 정의하기 이전에 graph에 대해서 조금 더 알아보고 넘어가도록 하자. 일반적으로 graph는 adjacency matrix $A$로 나타낼 수 있다. $A$는 square matrix이고 각 element $a_{m,n}$은 connectivity information을 나타낸고, $a_{m,n}$은 $E$ 혹은 $\omega$에 해당한다. 일반적으로 각 entry는 0 아니면 1을 나타내어 binary adjacency matrix를 구성하며, 만약 $\omega$에 대응하게 된다면 각 edge weight 값이 0과 1 대신에 표기될 것이다. 어느 경우든 간에 adjacency matrix $A$를 통해서 graph를 나타낼 수 있다.

또 다른 matrix로 degree matrix $D$가 존재한다. $D$ 또한 square matrix로 각 diagonal은 edge weight의 sum으로 구성되어 있다. 우리는 $A$와 $D$를 이용해서 또 다른 operator인 graph Laplacian $L$을 구성할 수 있다. $L$은 두 matrix의 차이로 만들 수 있으며, graph Laplacian에서 Laplacian이라고 불리는 이유는 $L$을 graph의 node에서 정의된 signal $f(m)$에 곱했을 때 이웃하는 node간 차이가 구해지게 되고, 여기에 weight를 곱하고 전부 더하게 되면 이러한 결과가 이웃간 차이를 계산하는 기존의 Laplacian 수식과 매우 유사하게 되기 때문이다.

위의 a와 같이 별 모양의 graph가 주어지게 되면 adjacency matrix는 b처럼 주어지게 된다. 연결된 edge를 노란색으로 표기한다고 하면 첫번째 node의 경우 3번째와 4번째 node와 연결되어 있음을 matrix $A$를 통해서 확인할 수 있다. 첫번째 row가 첫번째 node에 해당하고 3번째, 4번째 column이 0이 아니기 때문에 3번째, 4번째 node와 연결되었음을 의미한다. (1,3), (1,4)로 해석할 수 있고, 각각의 index에 대응하는 node가 연결되어 있는 것이다. 이런식으로 두번째 node가 4번째와 5번째 node와 연결되어 있음을 확인할 수 있다. 따라서 adjacency matrix는 connectivity 정보를 담고 있으며, 여기서 각 row를 전부 더해서 diagonal matrix로 구성하면 이것이 바로 degree matrix $D$이다. 현재 예시를 들고 있는 별 모양의 graph는 모든 node가 2개의 node만을 연결하고 있기 때문에 $D$의 diagonal entry는 모두 2가 될 것이다.

마지막으로 $D$에서 $A$를 빼주면 graph Laplacian matrix $L$이 위와 같이 만들어지게 되고, 위의 그림에서 보다시피 square하고 symmetric matrix임을 확인할 수 있다. 그래서 여기에 우리는 eigen deocmposition을 수행해서 eigenvalue $\lambda$와 orthonormal한 eigenvector $\chi$를 얻고자 한다. $L$이 positive semi-definite한 matrix이기 때문에 eigen decomposition을 했을 때 모든 eigenvalue들이 음수인 경우는 생기지 않게 된다. 그리고 각 eigenvalue에는 이와 대응되는 eigenvector가 존재한다. 그래서 graph가 주어지면 우리는 orthonormal basis를 찾을 수 있고, 여기에 대응하는 음수가 아닌 eigenvalue들을 얻게 된다.

이제 우리는 이렇게 얻어진 eigenvector를 이용해서 graph Fourier transformation (GFT)을 정의할 수 있다. GFT를 정의하기 위해서는 graph $G$에서 정의되는 orthonormal basis가 필요하다. 그래서 우리는 $L$의 eigenvector $\chi$를 basis로 사용해서 GFT를 정의할 것이다. GFT도 결국에는 transformation이기 때문에 inner product로 정의할 수 있다. Node에서 정의되는 signal $f$가 주어지면 $f$와 $\chi$간 inner product를 구할 수 있고, 계산을 하게 되면 graph Fourier coefficient $\hat f$를 얻을 수 있다.

그리고 이렇게 얻어진 coefficient $\hat f$를 이용하면 inverse graph Fourier transform (IGFT)를 정의할 수 있다. IGFT는 원래의 $f(n)$을 reconstruction할 수 있으며, 이는 다시 coefficient와 basis간 linear combination으로 계산이 된다. GFT와 IGFT 모두 $L$의 eigenvector $\chi$를 이용해서 transformation이 수행이 되는 것을 볼 수 있다.

이제 GFT를 알았기 때문에 우리는 한발 더 나아가 graph wavelet transformation (GWT)를 정의할 수 있다. 우리가 GWT를 정의하기 위해서 해야하는 것은 frequency space 상에서 band-pass filter로서 역할을 하는 kernel function $g$를 정의하는 것이다. Wavelet transformation은 요약하면 Fourier coefficient를 filtering하고 inverse transformation을 하는 과정이었다. 우리는 GWT을 이러한 식으로 정의할 수 있으며, 이는 마찬가지로 정확히 WT가 band-pass filtering과 동일하게 정의가 된다.

GWT를 하기 위해서 우리는 먼저 delta function $\delta$에 WT를 수행해서 wavelet basis를 만들 수 있다. Graph의 경우에는 $\delta_n$이 node $n$에서 정의가 되며, $\delta_n$과 eigenvector $\chi_l$간 inner product를 계산해주면 $\sum_{m=1}^N\delta_n(m)\chi_l^(m)=\chi_l^(n)$이라는 결과를 얻을 수 있다. 이 식에서 $\delta_n(m)$은 $m=n$인 경우에만 1이 될 것이라서 간단하게 $\chi_l^(n)$을 이끌어낼 수 있게 된다. Graph space에서 delta signal도 time space와 마찬가지로 graph frequency space 상에서 특정 값을 나타내게 된다. 우리는 time space에서의 delta signal이 frequency space 상에서 특정 constant로 표현되는 것을 알고 있다. 따라서, $\chi_l^(n)$도 GFT를 이용해서 $\delta_n$을 frequency space로 transformation 시킨 결과이다. 우리는 delta signal을 frequency space로 transformation함으로써 wavelet basis를 만든 것이고, 이는 band-pass filtering을 수행하는 것과 완전히 동일하다.

이제 우리는 식 20에서 구한 mother wavelet $\psi_{s,n}(m)$을 이용해서 GWT를 수행할 수 있다. Continuous WT을 생각해보면 원래의 signal과 basis간 inner product를 수행하면 된다. Node $n$에서 $f(n)$이 주어졌을 때 우리는 $f$와 $\psi$간 inner product를 통해서 위와 같이 spectral GWT (SGWT)를 수행할 수 있고, 이를 통해서 node $n$에 대한 wavelet coefficient $W_f(s,n)$을 얻을 수 있다. $W_f(s,n)$은 filter $g(s\lambda_l)$과 graph Fourier coefficient $\hat f(l)$, 그리고 basis $\chi_l(n)$을 모든 N개의 eigenvector에 대해서 inner product를 취해서 구할 수가 있다.

Summary

Interpretation

우리는 이렇게 WT를 통해서 얻은 wavelet coefficient를 어떻게하면 쉽게 이해할 수 있는지 생각해볼 필요가 있다. 우리가 transformation에 사용하는 filter의 경우 low frequency를 통과시킬 수도 있고, 반대로 high frequency를 통과시킬 수도 있다. 그리고 이러한 filter에 사용되는 scale의 크기에 따라서도 어떠한 결과를 얻을지 정할 수가 있을 것이다. 결국 어떠한 frequency를 포착하고 어떠한 scale을 사용해서 얻어진 wavelet coefficient가 어떠한 의미를 가지는지 알아야 우리가 원하는대로 filter를 설계해서 분석할 것이다. 우선 기본적으로 scale의 경우 클수로 넓은 영역을 분석한다고 생각하면 된다.

Low-pass filter

Low-pass filter의 경우 graph에서 low frequency를 강조하며, 이는 global한 information이나 전반적인 flow를 반영하게 된다. 이러한 filter를 사용하면 graph에서 넓은 범위의 전체적인 패턴을 잡아내고, node간 전반적인 similarity를 강조할 수 있다. Low-pass filter를 사용하는데 scale이 큰 경우에는 graph 전체에 걸친 매우 넓은 영역의 signal 변화를 분석하게 된다. 반대로 작은 scale의 경우에는 부분적인 signal을 포착하게 되어, 국소적으로 여러 이웃과 비슷한 성향을 가지는지 여부를 분석하게 된다. 요약하면 graph에서 전역적인 흐름이나 평균적인 signal의 특성을 포착하는 데 유용하며, 큰 scale에서 중요한 노드는 전체적인 패턴을 반영하고, 작은 scale에서는 국소적인 평균적 흐름을 분석한다.

High-pass filter

High-pass filter는 graph에서 high frequency를 강조하며, 이는 local한 information이나 부분적인 변화를 포착하게 된다. 이러한 filter는 node간 급격하게 변하는 신호를 포착해서 graph의 미세한 구조나 경계 영역을 분석하는데 유용하다. High-pass filter에서 scale이 큰 경우에는 넓은 범위에서 발생하는 부분적인 변화를 포착하며, 이는 주로 graph에서 크고 중요한 경계부분이나 급격하게 변동하는 signal을 보이는 node를 찾게 된다. 반대로 작은 scale의 경우에는 이웃 간의 급격한 signal의 차이를 포착하게 되는데, 이는 이웃 node간 미세한 경계나 세부적인 signal의 변동을 분석할 수 있다. 요약하면 graph에서 세부적인 경계나 국소적인 변화를 포착하는 데 적합하며, 큰 scale에서는 넓은 범위의 변화 지점을, 작은 scale에서는 미세한 경계를 잡아낸다. 그리고 wavelet coefficient의 크기는 해당 node가 filter에 의해 강조된 frequency에서 얼마나 중요한 역할을 하는지를 나타낸다. 그 값이 크면 해당 frequency에서 중요한 signal의 변화를 반영하며, 그 값이 작으면 상대적으로 덜 중요하며 안정적인 영역에 해당하게 된다.

Graph Convolutional Network (GCN)

WT에서 비롯된 filtering idea로부터 graph convolutional network (GCN)이 등장했다. Graph convolution은 filter $g$와 signal $x$ 사이에서 수행되며, 위와 같이 $U((U^Tg)\circ(U^T)x))$와 같이 계산될 수 있다. $g$와 $x$ 사이에서 convolution을 수행하는 것은 $x$에 filter $g$를 이용해서 filtering하는 것과 동일하게 볼 수 있다. 이러한 graph 상에서의 filtering으로부터 2017년에 kipf는 graph convolution이 위와 같이 동작할 수 있음을 수식화하였다.

일반적인 AI에 대해서 어느정도 알고 있다면 conventional neural network가 위와 같이 계산되는 것을 쉽게 이해할 수 있을 것이다. Input이 있다면 weight와 linear하게 combine 되고 summation까지 취해서 activation을 거치는 것까지가 일반적으로 동작하는 방식일 것이다. 위의 식에선 input이 $H$이고 weight가 $W$인 것이고, 이들간 linear combination 이후 activation function $\sigma$를 거쳐서 다음 layer에 input으로 들어갈 output을 만들어낸다.

Graph convolution layer의 경우에는 위와 같이 식이 정리될 수 있는데, 이는 기존의 neural network와 거의 유사한 것을 알 수 있다. 차이점이라고 한다면 기존의 input 앞에 adjacency matrix가 곱해진다는 것이다. 기존의 linear combination은 동일하지만, 앞에 graph adjacency가 곱해지면 이를 graph convolution layer라고 부르게 된다. 앞에 곱해지는 $A$의 역할은 오로지 연결된 node에 대해서만 식이 계산되도록 만들어지고, 나머지 node에 대해서는 지워버리게 된다. 일종의 feature selection을 하는 operation으로 이해해도 된다. 이렇게 하면 모든 variable을 고려하지 않고 local linear combination을 할 수 있다. 이는 graph의 connectivity 정보를 고려한 convolution으로 해석이 되는 것이다.

Filtering via Kernel

하지만 이러한 operation에는 큰 문제가 존재한다. 이렇게 단순히 adjacency matrix를 곱해주게 되면 1-hop distance만을 고려하는 convolution이 수행된다. 여기서 1-hop distance라는 것은 바로 이웃한 node를 가리키기도 하며, 1번 점프를 했을 때 바로 옆의 node로 이동함을 의미하게 된다. 그래서 2-hop 이상 멀리 떨어진 node에 접근하기 위해서는 점프를 여러번 해야하며, 이는 layer를 깊게 쌓아야 하는 문제를 발생시킨다. 그렇다면 layer를 깊게 쌓는 것이 왜 문제가 되는 것일까? Layer를 깊게 쌓는 것은 그만큼 $A$를 여러번 곱하게 되는 것을 의미한다. 이는 모든 node에 대해서 각각 이상적인 hop distance가 있을텐데 이를 무시하고 여러번 점프를 진행시키게 만들고, 이렇게 정보가 계쏙해서 누적이 되다보면 oversmoothing 문제가 발생하게 되어 모든 node들이 특징적이지 않고 비슷한 정보를 가지도록 평균화가 진행될 것이다.

이러한 문제를 해결하기 위해서 각 node마다 동일한 hop distance 대신에 특정한 range를 볼 수 있도록 만들 수가 있다. 여기서 range는 kernel function $e^{-s\lambda}$로 정의될 수 있고, 이는 heat diffusion equation으로 물리학에서 비롯된 개념 중 하나이다. Kernel $h_s(p,q)$는 location $p$에 있는 경우 diffusion distance가 무엇이며, $p$에서 scale $s$로 energy를 퍼트리면 $q$까지 얼마나 걸리는지를 나타낸다. 우리는 이를 random walker distance라고 표현하기도 한다. 만약 술을 많이 마셔서 취한 사람의 경우 본인조차 어디로 갈지 잘 모르는 것이 대부분일 것이다. 이렇듯 임의로 걷고 있는 것과 유사한 상황임을 알 수 있다. 그리고 이러한 상황에서는 어디로 걷는지 모르면서 동시에 몇분동안 얼마나 걸을지도 모를 것이다. 어디로 얼마만큼의 시간동안 갈지를 우리는 정의할 수 있고 이것이 $h_s(p,q)$의 행동을 설명하게 된다. 현재 위치 $p$에서 얼마만큼의 $s$ 시간이 흐른 뒤에 $q$에 도착할지를 설명하는 개념인 것이다. $h_s$를 통해서 negiborhood의 local range를 정의할 수 있고, 이러한 range를 통해서 기존의 hop distance를 재정의할 수 있는 것이다.

Graph signal processing 기법 중 graph wavelet transformation을 제대로 이해하기 위해서 우리는 graph domain이 아닌 signal에서의 wavelet transformation (WT)에 대해서 알아볼 것이고, 그전에 앞서 Fourier transformation (FT)부터 자세히 알아보고자 한다. WT는 결국 FT에서 시작하게 되며, FT는 모든 signal processing 기법의 기초가 되는 개념이다. FT를 이야기 하기 위해서는 period signal을 다루는 Fourier serires를 먼저 이야기해야 한다. 우리는 어떠한 period signal을 특정 sinusoidal basis를 사용해서 이를 더하는 식으로 표현할 수 있다. Period라는 개념을 finite에서 infinite로 확장하게 된다면, 우리는 이를 FT라고 부를 수 있게 된다.

$x$에 따라 정의되는 1D signal $f(x)$가 있다고 해보자. 만약 $f(x)$에 FT를 취하게 된다면 위와 같이 inner product를 구할 수가 있다. Transformation은 inner product를 하는 것과 같다고 생각하면 된다. Inner product를 통해서 $f(x)$를 sinusoidal function $e^{j\omega x}$를 basis로 하여 projection 시킬 수 있다. 여기서 $e^{j\omega x}$는 purely imaginary complex exponential로 FT의 basis로 사용이 된다. 이렇게 $f(x)$와 $e^{j\omega x}$ 사이의 inner product를 취하게 됨으로써 Fourier coefficient $\hat f(\omega)$를 얻을 수 있다. 정확한 표현이 아닐 수 있지만 여기서 integral 안에 inner product를 element-wise multiplication을 구한 뒤 summation 한다고 생각할 수 있다. 그러나 이러한 과정을 우리는 continuous space에서 하고 있어서 $x$의 space 전체에 걸쳐 $f(x)$를 $e^{-j\omega x}$와 곱하고 이를 전부 $x$에 대해서 더하게 된다. 이는 $x$에 대해서 marginalization을 하여 결과적으로 $\hat f(\omega)$를 얻을 수 있게 된다. 여기서 $\omega$는 frequency space를 설명하게 되고, Fourier coefficient에서 $f(x)$는 얼만큼의 static한 $\omega$의 frequency component가 포함되는지 정량화하는 일종의 weight로 여길 수 있다.

이제 이렇게 Fourier coefficient가 주어진다면 우리는 inver Fourier transformation (IFT)를 수행할 수 있다. IFT는 FT와는 다른 transformation이다. IFT는 $\hat f(\omega)$를 다시 반대로 $x$로 projection하게 된다. 이 과정이 아무래도 FT의 inverse이기 때문에 동일한 basis로 $e^{j\omega x}$를 사용하고, 이를 $\hat f(\omega)$과 inner product를 구함으로써 역으로 transformation을 수행할 수 있다. 이러한 수식을 통해서 다시 $\hat f(\omega)$을 $x$ space에 projection 시킬 수 있다. 앞에 $1/2\pi$는 normalization term으로, 분모의 $2\pi$는 $e^{j\omega x}$에 내재된 scaling 값으로 생각할 수 있다. 이 식에서는 $\hat f(\omega)$와 $e^{j\omega x}$의 inner product를 coefficient와 basis간 linear combination으로 생각할 수 있고, 이를 통해서 $f(x)$를 표현한다고 생각할 수 있다. 얼만큼의 frequency component를 가지고 있는지 생각할 수 있으며, 이를 각각의 basis와 곱한 뒤 모두 더해서 $f(x)$를 구성하게 되는 것이다.

그리고 FT에는 scaling property라는 것이 존재한다. 만약 $h(x)=f(sx)$일 때, 우리는 $s$를 통해서 function을 줄이거나 늘릴 수가 있을 것이다. $s$ 값에 따라서 function $h(x)$가 좌우로 더 넓어질 수도 있고 반대로 더 얇아질 수도 있을 것이다. 이제 여기서 우리가 $h(x)$에 FT를 취하게 된다면 Fourier coefficient $\hat h(\omega)$를 얻게 됨과 동시에 우변의 $f(sx)$는 $1/s\hat f(\omega/s)$로 변환이 된다. 그렇다면 이것은 무엇을 의미할까? $x$라는 space 상에서 $s$에 의해서 줄어들게 되는 signal에 대해서 FT를 취했을 때 $\omega$라는 space 상에서는 반대로 $s$에 의해서 늘어나게 되는 것이다. 이와 동시에 signal의 전체적인 magnitude도 $s$에 의해서 scaling 된다. $s$가 1보다 크다면 $\hat h(\omega)$는 작아지게 될 것이고, 반대로 $s$가 1보다 작으면 $\hat h(\omega)$는 커지게 될 것이다. 이는 $\hat h(\omega)$에서 $\hat f$ 앞의 $1/s$에 의해서 수행된다. 그리고 $s$가 scaling factor이기에 일반적으로 양수의 범위를 고려하게 된다. 그렇다면 만약 $s$가 음수가 된다면 어떠한 일이 생길까? 우리는 이 범위가 양수가 되도록 제한해야할 것이다. 물론 이 범위가 음수가 된다고 하더라도 위의 수식은 여전히 만족하게 된다. $s$가 음수라면 integral의 범위가 바뀌게 되는데, 결국에는 동일한 범위가 설정이 되어 위와 같은 결과에 도달할 것이다. 그래서 사실 $s$를 절대값으로 생각해도 괜찮을 것이고, 여기까지가 FT의 대표적인 scalining property에 대한 설명이다. 결국 요약하자면 time space에서 줄어드는 signal은 frequency space에서 늘어날 것이고, 반대로 time space에서 늘어나는 signal은 frequency space에서 줄어들게 될 것이다.

위는 FT의 간단한 예시를 보여준다. 위와 같이 1D signal $f(t)$는 한눈에 봐도 2개의 sin function으로 쉽게 합쳐져서 구성된 것을 볼 수 있다. 식을 자세히보면 첫번째 sin에서 50이라는 일종의 scale이 포함되어 있고 이는 0.7의 coefficient가 곱해져 있으며, 두번째 sin에서는 120의 scale이 1의 coefficient와 곱해져 있다. 이러한 $f(t)$에 FT를 적용하게 된다면 frequency 50과 120에서 각각 coefficient 0.7과 1을 얻게 될 것이다. 그러나 문제는 항상 signal에는 특정 high frequency를 포함하는 noise가 존재하기 마련이다. 그래서 원래의 signal이 좌측과 같을 것이라면, noise가 포함이 되면 중앙과 같이 signal이 좀 더 흔들리는 모양을 보이게 된다. 그리고 여기에 FT를 취하면 우측과 같은 결과를 얻을 수 있다. FT가 우리에게 말해주는 것은 비록 원래의 signal이 noise component를 가지고 있더라도 대부분의 component는 0에 가까운 coefficient를 가지고 있으며 위의 예시에서 2개의 peak 지점의 경우에만 sin component에 해당하게 된다. 이렇게 signal이 어떻게 구성되는지 분석할 수 있기 때문에 FT는 유용하게 사용이 되는 것이다.

Limit of Fourier Transform

그러나 이러한 FT도 완벽하지는 않다. 바로 ringing artifact 혹은 Gibbs penonmenon 때문이다. 갑자기 증가했다가 갑자기 감소하는 위와 같은 signal은 sin과 cos으로 표현하기 어려울 수 있다. 이상적으로 생각하면 가능한 경우가 존재할 수는 있다. 여기서 이상적이라는 표현은 basis의 수가 infinite한 경우를 이야기한다. 이렇게 sharp하게 변하는 function의 경우에는 FT가 최선의 transformation 방법이라고 할 수는 없을 것이다. Fourier basis들을 무한히 사용하여 원하는 function의 급격한 변화를 표현할 수 없기 때문에 발생하는 현상이 바로 ringing artifact이다. 위와 같이 basis를 무한히 사용하게 되면 원래의 signal을 비슷하게 표현할 수는 있겠지만, 현실적으로는 불가능하며 flat한 부분을 자세히보면 조금씩 벗어나는 것을 확인할 수 있다.

FT는 infinite support를 가지는 Fourier basis를 이용하며, 이는 어떠한 범위에서도 continuous한 성질을 지니고 있다. Fourier basis를 사용하게 되면 효과적으로 원래의 signal을 나타낼 수는 있지만, infinite support를 지녔기 때문에 ringing artifact를 보여준다는 한계가 분명하게 존재한다. 이러한 한계점 때문에 우리는 wavelet transformation에 대해서 알아보고자 한다.

Wavelet Transform

Wavelet transformation (WT)은 sin과 같은 sinusoidal basis 대신에 이와 비슷하지만 다른 function을 basis로 사용하게 되며, 이를 wavelet basis라고 부를 수 있다. 좌측의 Fourier basis 대신에 중앙의 Haar wavelet basis와 우측의 Mexican hat wavelet basis는 WT에서 사용되는 대표적인 basis들이다. Fourier basis와 나머지 wavelet basis의 주된 차이점은 전자는 infinite support를 가져서 동일한 패턴이 계속해서 반복되는 반면에 후자는 highly localize 되었다는 것이다. 여기서 highly localize 되었다는 표현은 우리가 basis의 중앙이 어디인지 알 수 있다는 것이다. 중앙에서 벗어나 좌우로 이동하게 되면 그 값이 0으로 수렴하는 것이 특징이다. 이러한 특징들이 wavelet basis가 time space에서 localize 되었다는 것이고, 사람들은 또한 frequency space에서도 localize 되었다고 말하기도 한다. 그 이유는 사람들이 wavelet basis를 설계할 때 이들이 frequency space 상에서 band-pass filter가 되도록 한다. 그렇다면 band-pass filter는 무엇을 의미할까? 우리는 흔히 low-pass filter와 high-pass filter를 사용하는데, band-pass filter는 이 둘의 중간 정도로 생각할 수 있다. 즉, freuqency space에서 중간 frequency 부분들을 커버하면서 smooth하게 변하는 filter를 이야기한다. 사람들은 이렇게 bell-shaped curve 모양으로 band-pass filter를 설계해서 사용하고, 이는 frequency space 상에서 0에서 출발해서 천천히 증가하면서 큰 weight로 특정 범위를 커버한 뒤에 천천히 내려오는 형태를 보여준다. 결국 핵심은 frequency space에서 smooth하게 변하는 이러한 signal이 time space로 transformation 되면 highly localized 된 형태로 존재해야 wavelet basis가 된다는 것이다. 그래서 time space와 frequency space에서 localize 된다는 것은 time space 상에서 중앙을 특정할 수 있는 signal이 frequency space 상에서는 특정 freuency 범위를 커버하고 있다는 것과 같은 이야기인 셈이다. 이러한 점을 제외하고 FT와 WT에서 수행되는 일련이 과정에는 큰 차이가 없다.

Continuous Wavelet Transform

FT에서는 우리가 알고 있는 sin function 등으로 basis를 사용했지만, WT에서는 wavelet basis를 미리 정의해서 사용해야만 한다. Haar wavelet이나 Mexican hat wavelet과 같이 대표적인 basis를 wavelet으로 사용해도 된다. 어떠한 wavelet을 선택해서 사용할지는 오로지 사용하는 사람에게 달려있다. 하지만, 우리가 어떠한 wavelet을 선택하더라도 위와 같이 2개의 parameter $s$와 $a$를 포함해야 한다. Mother wavelet $\psi$은 이렇게 $s$와 $a$를 포함해야 하는데, 여기서 $s$는 $\psi$의 scale을 조절할 수 있는 parameter이고, $a$는 $\psi$의 center location을 조절할 수 있는 parameter이다. 어떠한 function도 mother wavelet이 될 수 있지만, $s$를 통해서 scaling이 되어야 함과 동시에 $a$를 통해서 translation 될 수 있어야 한다.

Haar wavelet의 경우에도 dilation을 조절하는 $s$와 translation을 담당하는 $a$를 통해서 원하는대로 정의할 수가 있다. 결국 WT에서 basis로 사용이 되는 mother wavelet의 성질로는 이렇게 $s$와 $a$를 통해서 function 자체를 통제할 수 있어야 함과 동시에 frequency domain 상에서 band-pass filter의 역할을 수행해야만 한다.

그렇다면 이제 앞서 말한 parameter를 바꿔가면서 Harr wavelet이 어떻게 변화하는지 살펴보자. 먼저 dialation을 담담하는 scale parameter $s$를 바꿔보고자 한다. $s$를 바꾸게 되면 위와 같이 wavelet의 width가 바뀌는 것을 확인할 수 있다. 이러한 과정은 FT에서 sinusoidal function의 scalining과 같은 것이라고 볼 수 있고, 이를 WT에서는 scale parameter를 통해서 수행하는 것이다.

$a$를 조절하게 되면 위와 같이 좌우로 center가 이동하는 것을 볼 수 있다.

위의 그림은 하나의 band-pass filter를 서로 다른 scale을 가지고 표현된 것이다. Scale parameter에 변화를 준다는 것은 FT를 각각에 대응해서 수행하는 것을 의미하며, 이는 frequency space 상에서 서로 다른 band-width를 커버하게 된다. 이렇게 band-pass filter의 scale parameter를 단순히 바꾸기만 하더라도 location 또한 달라지게 된다. 그리고 여기서 반드시 알아야하는 부분으로 band-pass filter를 보면 원점에서 시작하게 된다. 그렇기 때문에 band-pass filter는 frequency component가 0인 부분은 커버할 수 없게 된다. 그래서 우리는 추가로 filter 1개를 도입시켜 이 부분을 커버할 수 있다. Scalining function으로 불리는 low-pass filter 1개를 통해서 frequency space 상에서 frequency가 0인 부분을 포착하게 된다. 사실 scalining function $\phi$는 band-pass filter와 다르게 추가적인 부분으로 사용하는 사람이 선택을 할 수 있는 부분이다. Wavelet을 어떻게 선택하는지에 따라 scaling function을 가져야하는지가 결정될 수 있지만, mother wavelet의 경우에는 transformation의 기반이 되는 basis로서 항상 존재해야 한다.

이제 WT의 기반이 되는 wavelet에 대해서 어느정도 알아보았으므로, 이제는 WT가 어떻게 동작되는지 수식적으로 알아보자. Signal $f(x)$에 WT를 적용하는 것은 FT와 마찬가지로 inner product를 수행하게 된다. $f(x)$가 주어졌을 때 우리는 추가로 미리 정의했거나 선택한 mother wavelet $\psi$를 사용해서 이들간 inner product를 통해서 WT를 수행하고 wavelet coefficient $W_f(s,a)$를 얻을 수 있다. FT에서는 Fourier coefficient를 얻었지만, WT에서는 이와 마찬가지로 wavelet coefficient를 얻게되는 것이다. $\psi$에는 기본적으로 2개의 scalining과 translation parameter를 가지고 있기 때문에 $W_f(s,a)$에도 2개의 variable $s,a$를 가지게 된다. 따라서 $W_f(s,a)$는 결국 scalining variable $s$와 translation variable $a$에 의해서 결정이 될 것이다.

FT의 수식을 보면 basis로 $e^{j\omega t}$의 conjugate를 사용하여 signal과 곱한뒤 summation을 취하는 식으로 동작한다. 우리는 mother wavelet $\psi$에 FT를 수행하고 싶고, 이는 wavelet basis의 basis를 바꾸는 것과 같다.

우리는 wavelet coefficient $W_f(s,a)$를 얻게되면 이를 이용해서 inverse transformation 또한 정의할 수 있어야 한다. Inverse wavelet transformation (IWT)는 IFT와 마찬가지로 coefficient과 basis를 곱한뒤 2개의 integral을 취하게 된다. 여기서 integral이 2개인 이유는 coefficient가 2개의 parameter가 $s$와 $a$를 가지기 때문이다. 그래서 integral을 할 때 전체 $s$와 전체 $a$에 걸쳐서 marginalization을 해줘야 한다. 이렇게 IWT를 통해서 원래의 signal $f(x)$를 reconstruction할 수 있다.

이제 중요한 것은 그렇다면 항상 IWT를 정의할 수 있는지이다. 정답은 No이다. 이를 설명하기 위해서 IFT을 다시 생각해볼 필요가 있다. IFT에는 scalining factor로 $1/2\pi$가 존재한다. 여기서 $2\pi$는 complex sinusoidal signal의 property로부터 비롯된 값이다. 즉, $2\pi$라는 값은 transformation하고자 하는 basis로부터 계산이 된 결과이다. IWT에도 scaling factor가존재하며, 우리는 이를 $C_\psi$로 notation하여 basis로부터 얻고자하며, 이는 위와 같이 Admissibility condition을 만족하여 구해지게 된다. Frequency space 상에서 우리가 사용하는 basis의 power가 finite해야한다는 것이 Admissibility condition이다. 우리는 이러한 조건에서만 IWT을 정의할 수 있다. $C_\psi$가 infinity로 발산한다고 생각해보면, 즉, mother wavelet에 FT을 취하여 얻어진 basis $\Psi$의 power가 값이 infinity로 커지게 되면 IWT에서 우변의 값이 항상 0으로 수렴하게 되어 IWT가 제대로 정의되지 못할 것이다. 그렇기 때문에 $C_\psi$는 항상 infinity보다는 작아야 우리가 transformation에 사용하고자하는 basis로부터 frequency space에서 이들의 power가 summable하게 되는 것이고, 우리는 이러한 조건을 Admissibility condition이라고 한다. 요약하자면 Admissibility condition을 만족해야만 IWT를 정의할 수 있게 된다. 그리고 IWT를 $f(x)$의 reconstruction이라고 표현하기도 한다.

Scale and Translation of CWT

지금부터는 이러한 WT가 convolution이 되는 과정을 설명하고자 한다. 먼저 WT를 $T^s$라는 operator로 정의해보자. 어려워보이지만 우리는 operator $T^s$를 $f(a)$에 곱했을 때 wavelet coefficient $W_f(s,a)$를 얻게 될 것이다. 즉, $T^s$는 signal을 wavelet cofficient로 mapping해주는 operator인 것이다.

다음으로 mother wavelet $\psi_{s,a}(x)=\frac{1}{s}\psi(\frac{x-a}{s})$에서부터 parameter $a$를 날려서 간단하게 $\bar {\psi}s(x)=\frac{1}{s}\psi^*(\frac{-x}{s})$를 정의할 수 있을 것이다. 원래 $\psi{s,a}(x)$는 $x$에 대한 function이지만 또한 $a$에 대한 function으로 생각해볼 수 있어서 위와 같이 $T^s$를 $f(a)$에 적용한 $(T^sf)(a)$를 구할 수 있을 것이다. 이것이 괜찮은 이유는 나와 상대방 사이의 거리나 상대방과 나 사이의 거리가 동일하기 때문이다. 관점의 차이일 뿐 결과에는 차이가 없을 것이다.

$T^sf(x)$는 결국 wavelet coefficient $W(s,a)$이고, 이는 $\int\frac{1}{s}\psi^* (\frac{x-a}{s})f(x)dx$로 구해질 수 있다. 우리는 여기서 basis를 $x$에 대한 function 혹은 $a$에 대한 function 둘다로 고려할 수 있다. 그러면 우리는 이제 $T^sf(a)$를 구할 수 있고, 이는 마찬가지로 $W(s,a)$가 되면서 $\int\frac{1}{s}\psi^* (\frac{x-a}{s})f(x)dx$가 $\int\bar\psi_s(a-x)f(x)dx$와 같이 계산되어 진다. 여기서 중요한 것은 wavelet 부분이 우리가 정의한 새로운 wavelet $\bar\psi_s$로 대체가 된 것이다. 간단하게 $x$ 대신에 $a-x$를 넣으면 위와 같은 결과가 도출될 것이다. 그리고 식을 자세히 보면 굉장히 익숙한 convolution 형태의 식으로 만들어진 것을 볼 수 있다. 이는 결국 $f(x)$와 $\bar\psi_s(x)$ 사이의 convolution으로 해석이 된 것이고, 따라서 우리는 WT가 convolution임을 이렇게 증명해온 것이다. WT가 convolution이 될 수 있음을 간단하게 basis의 변경을 통해서 유도하였다. 정확히 이야기하면 여전히 동일한 basis $\psi$를 사용하지만 간단하게 식을 재정의해서 얻어진 $\bar \psi$를 통해서 WT가 convolution임을 설명할 수 있다. 알아야할건 $x$에 걸쳐서 integration을 해서 결국 parameter $a$를 갖게된 것이다.

그렇다면 우리가 이러한 것들을 왜 했을까? 우리가 결국 하고자 하는 것은 위의 operation에 FT을 취하는 것이다. 중요한 성질 중 하나로 time space에서 convolution은 frequency space에서 multiplication이다. 이는 잊어서는 안되는 정말 중요한 내용이다. Time space에서 mother wavelet과 signal의 convolution을 FT를 통해서 frequency space로 보내면 filter에 해당하는 mother wavelet과 Fourier coefficient에 해당하는 signal의 multiplication으로 표현이 된다. $a$와 $x$의 space 상에서의 convolution이 frequency space에서 multiplication이 되는 것은 위의 식을 통해서 확인할 수 있다.

이러한 내용은 지금부터 알아가는 내용을 위해서 중요한 역할을 한다. 다시 FT의 scalining property를 생각해보자. Time space에서 scale $s$가 FT를 통해서 frequency space로 가면 기존과 반대로 동작했었다.

이러한 FT의 scalining property를 사용해서 우리는 위와 같은 수식을 논할 수 있게 된다. $\hat{\bar\psi_s}(\omega)$가 $\hat\psi^(s\omega)$로 대체될 수 있다. 어떻게 이러한 식이 가능한 것일까? 우리는 $\bar\psi_s(x)=\frac{1}{s}\psi^(\frac{-x}{s})$로 정할 수 있음을 앞에서 확인했었다. 우리는 양변에 FT를 취하게 되면 좌변은 $\hat{\bar\psi_s}(\omega)$가 되며, 우변은 $\frac{1}{s}\hat{\psi}^(\frac{-\omega}{s})$가 될 것이다. 다시 이 우변을 scalining property를 통해서 정리하면 $\hat{\psi^}(s\omega)$가 될 것이다. 결국 위와 같은 식이 성립하게 되는 것이다.

마지막으로 식 11과 12를 종합해보면, 우리는 먼저 $T^sf(a)=f(x)\psi_{s,a}(x)$로부터 FT을 통해서 $\widehat{T^sf}(\omega)=\hat f(\omega)\hat{\bar \psi_s}(\omega)$와 같이 frequency space에서 multiplication으로 구해지는 것을 확인하고, 이제 $\hat{\bar \psi_s}(\omega)$을 $\hat{\psi_s^}(s\omega)$로 대체할 수 있게 되었다. 결과적으로 $\widehat{T^sf}(\omega)=\hat f(\omega)\hat{\psi_s^}(s\omega)$에서 $\hat f(\omega)$은 Fourier coefficient가 되고 $\hat{\psi_s^}(s\omega)$은 frequency space에서 band-pass filter의 역할을 하는 wavelet $\psi$에 의해 결정된 band-pass filter function의 역할을 하게 될 것이다. 즉, frequency space에서 특정 frequency component들을 wavelet basis로부터 주어진 filter function으로 filtering하는 과정으로 이해할 수 있다. 지금까지 우리는 WT의 과정을 convolution으로 증명하였고, 여기에 FT를 수행해서 wavelet basis로부터 filter를 구해 filtering하는 과정까지 흐름이 이어져오고 있다. 이제 FT를 이미 적용했기 때문에 여기에 다시 IFT를 적용할 수 있을 것이다. IFT는 Fourier coefficient과 Fourier basis를 곱해주기 때문에 우리는 앞서 구해진 WT의 결과에 FT를 수행한 $\hat f(\omega)\hat{\psi_s^*}(s\omega)$을 coefficient로 간주해서 Fourier basis $e^{j\omega x}$를 곱하고 integral을 취해서 위와같은 filtering을 수행한 reconstructed signal $f(x)$를 만들 수 있다. 전체적으로 식 13은 IFT의 형태를 보이고 있다. 하지만 중요한 점은 기존의 IFT와는 다르게 $\hat f(\omega)$를 wavelet basis를 이용해서 filtering을 했다는 것이다. $f(x)$가 완벽하게 복원되었다고 이야기하기는 어렵다. 다만, 원하는대로 filtering된 결과의 reconstruction이라는 의미가 존재한다.

우리가 계속해서 사용하는 wavelet basis $\psi_{a,s}(x)$는 delta function $\delta$에 wavelet operation을 수행하여 얻은 것과 같다. $\delta$에 FT를 적용하게 되면 1이라는 사실은 알아두면 좋다. Time space 상에서 $\delta$ function은 frequency space 상에서는 constant function으로 그 값이 전부 1이 된다. 이것이 의미하는 것은 Fourier coefficient $\hat f(\omega)$ 자체가 1이 되는 것이고, 결과적으로는 wavelet basis를 IFT를 통해서 reconstruction하는 것과 같아지게 된다. 그래서 mother wavelet을 delta signal의 WT으로 이해하면 된다.

Summary

정리를 해보면 우리는 FT부터 WT까지 그 흐름을 이어오면서 알아보았다. 먼저, FT는 basis로 $e^{j\omega t}$를 사용하고 이는 infinite support라는 특징이 있다. WT는 새로운 basis로 mother wavelet $\psi_{s,a}(x)$를 사용하고 이는 finite support라는 대조되는 특징이 있다. 우리는 origianl signal $f(x)$와 2개의 parameter를 지닌 $\psi_{s,a}(x)$간 inner product와 integration을 통해서 WT를 수행하고 wavelet coefficient $W_f(s,a)$를 얻을 수 있다. IWT 또한 wavelet coefficient과 wavelet의 inner product와 integration을 통해서 $f(x)$를 구성할 수 있었다. 여기에는 basis로부터 나온 Admissibility condition이 존재하며, 이는 $C_\psi$가 frequency space 상에서 finite power를 보이기만 한다면 우리는 IWT를 정의할 수 있게 된다. 모든 흐름이 직관적이고 간단해 보일 수 있지만, 가장 중요한 핵심으로는 이러한 WT이 "band-pass filtering"으로 설명될 수 있다는 점이다. 그리고 WT은 Fourier coefficient가 있을 때 여기에 mother wavelet에 따라 결정되는 filtering을 적용하는 과정으로 볼 수 있다. 여기에는 convolution이 frequency space에서 multiplication으로 동작한다는 성질이 중요하게 작용한다. WT는 또한 finite support이기에 FT의 큰 문제 중 하나인 ringing artifact가 없다는 장점도 존재한다.

3D geometric GNN은 3D graph data를 설명하는 framework로 가장 대표적인 data가 바로 3D point cloud이다. 3D 좌표에서 node vertex들이 표현되어 있는 graph를 3D point cloud라고 하고, 가장 대표적인 예시로 molecule data가 존재한다. Molecule은 실제로 굉장히 중요한 data로 3D 공간 상에서 정의될 수 있다.

3D 공간 상에 표현되는 molecule은 geometric graph로 정의되며, 이는 Euclidean space 상에서 3D point cloud data와 관련이 있다. 이는 permutation symmetry도 중요하지만 3D space 상에서 roation 등의 Euclidean symmetry도 고려해야 한다. Molecule을 3D 상에서 회전을 시켜도 identity는 보존되어야 한다. 그래서 이러한 data는 vertex들이 3D space 상에서 정의가 되며, 각 vertex는 3D space 좌표 정보와 각 vertex가 어떠한 타입인지 등에 관한 정보를 node feature로 가지게 된다. 그리고 이러한 graph 구조는 cut-off radius에 의해 결정이 되는데, 이는 곧 vertex 사이의 Euclidean distance가 얼마나 작은지와 관련이 있다.

E(3) Transformation

이전에 살펴본 permutation symmetry와는 좀 다르게 3D graph에 대해서 Euclidean group transformation을 가지게 되고, 우리는 이를 E(3) Transformation이라 부른다. 여기서 E는 Euclidean을 의미하게 된다. Euclidean group은 또한 transformation들의 set으로, E(n)이라는 것은 Euclidean-distance를 보존하는 transformation들을 $N$ 차원에서 정의하는 Euclidean group을 나타낸다. 아무래도 3차원에서 graph를 표현하기 때문에 E(3) transformation이라 하는 것이다. Rotation, translation, reflection으로 transformation을 구성할 수 있으며, 이들의 조합으로도 구성할 수 있다.

추가로 special Euclidean group SE(n)을 정의할 수 있다. 이는 handedness를 보존하는 E(n)의 subgroup을 의미한다. Euclidean group에서 단순히 reflection을 제외시킬 수 있다. 왜냐하면 손을 움직인다고 했을 때, 우리가 왼손과 오른손을 서로 바꿀 수가 없을 것이다. 실제로 object를 reflecting 시키는 것은 불가능하기 때문이다. 그래서 오로지 translation과 rotation만 가능한 group을 정의한 것이다. 현실을 반영한 SE(3) group은 중요한 개념인 셈이다. 우리는 앞으로 다루기 쉬운 E(3) group을 더 이야기해볼 것이다.

Designing DNNs for E(3) Transformations

우리는 $f(X,H)$에 의해 표현되는 DNN을 설계해볼 것이고, 여기에 invariant function과 equivariant function까지 설계해볼 수 있다. Invariant function의 경우에는 input $X$에 rotation matrix $R$을 곱하고 translation matrix $b$를 더해도 그 결과가 변하지 않으면 된다. 반대로 equivariant function의 경우 대응되는 output이 나오면 되는 것이다.

Main Applications

Drug Discovery

지금부터는 이러한 3D graph를 활용한 여러 적용 분야들에 대해서 알아볼 것이다. Durg는 우리의 몸과 마음을 바꿔주는 chemical substance이다. 우리가 어떠한 목적에 맞는 drug를 발견하도록 하는 분야가 drug discovery이다. 하나의 neural network가 모든 drug를 발견하기를 원치는 않는다. 아무래도 속도적인 측면과 신뢰의 관점에서 하나의 network는 이 분야에서 한계가 존재한다.

How Drugs Work?

만약 우리가 GNN을 drug discovery에 활용하고 싶다면, drug가 실제로 어떻게 동작하는지 이해할 필요가 있다. Drug는 사람의 몸에서 반응을 하고, 사람의 몸은 protein으로 구성되어져 있다. 여기서 protein은 molecule로 구성되며 많은 수의 atom으로 이루어져 있다. 각 atom은 다양한 기능을 가지고 있다. 그래서 특정 protein에 연결되는 drug를 찾아야하는 것이다. 작은 molecule이 transporter 앞에 멈춰서 특정 protein에 연결되도록 한다. 우리는 GNN을 molecule이 연결되는 과정으로 생각하고 설계하면 된다.

Drug Types

우리는 2가지 종류의 drug를 생각할 수 있다. 하나는 small molecule이고 다른 하나는 biologic이다. 전자는 Aspirin과 같은 low weight를 가지는 organic compound이다. 그래서 protein에 비해서 적은 수의 atom을 가지고 있다. 후자는 반대로 더 큰 molecule로 구성될 수 있다. 그래서 이는 protein 기반의 drug들에 해당한다.

Small Molecule drugs

Small molecule은 ligand와 같은 역할을 한다. 사람들이 지금까지 대체로 small drug들에 관한 발견과 연구를 진행했기 때문에, 사람들은 더이상 발견될 small molecule drug가 없다고 생각한다. 즉, 사람들의 발견이 힘들기 때문에 인공지능 모델이 도움을 줄 수 있다는 것이다.

Biologics

Protein이 오히려 최근에 사람들이 찾고자 하는 drug에 해당한다. 대표적으로 antibody가 있을 수 있다.

Accelerating Molecular Simulation

그렇다면 GNN이 어떻게 drug discovery를 가속화하는데 이용될 수 있을까? 이는 molecular simulation으로 충분히 활용될 수 있다. 우리는 GNN을 이용해서 computer simulation으로부터 구해지는 property나 dynamic들을 예측할 수 있다. 이는 현실에서 실험되는 것과는 다르다. 현실에서 실험되는 부분과 관련해서는 density functional theory (DFT)라는 또다른 computer simulation을 이용하게 된다. 이는 super computer를 이용하며 cost가 많이 들고 속도가 많이 느리다. 이를 neural network로 대체하면 좋을 수 있지만, 아직 많은 한계점들이 존재한다.

Molecular Property Prediction

Molecular property prediction에 이용되는 대표적인 dataset으로 Quantum Machines 9 (QM9)이 있다. 이는 CHONF 원자들로 구성된 안정된 organic molecule들로 구성되어 있다.

Molecular Dynamics Simulation

진공 속에서 어떻게 molecule이 이동하는지 예측하는 molecular dynamics simulation에 사용되는 dataset으로는 Molecule Dynamics 17 (MD17)이 있다.

Material Property Prediction

현실과 그래도 밀접한 material property prediction에 사용되는 dataset으로 Open Catalysts 20 (OC20)이 있다. 위에서 빨간 공들이 catalyst이고 여기서 어떻게 작은 molecule이 동작하는지 예측하는 것이다.

Crystal과 관련해서는 Material Projects (MP) dataset이 존재한다.

Protein Structure Prediction

Protein이 주어졌을 때 3D 좌표를 예측하는 task도 존재한다.

Protein Docking

Protein docking은 주어진 protein이 어떻게 연결이 될지를 예측하는 것으로 사람의 몸에서 일어나는 반응을 simulation할 수 있다. 어떠한 drug가 protein을 활성화 시킬지 확인할 수 있다. 하나의 drug molecule과 protein이 어떻게 연결되는지 simulation을 할 수 있다.

위와 같이 두 protein이 docking되는지도 simulation을 통해서 확인할 수 있다.

이번에는 geometric deep learning (GDL)과 관련하여 blueprint를 설명하려고 한다. 여기서 blueprint라는 것은 우리가 CNN, GNN 등을 표현하는데 있어서 중요한 formula를 설명하려고 하는 것이다. 우리가 GDL을 설명할 때마다 group과 symmetry라는 개념을 빼놓을 수는 없다. 이는 group theory라고 하는 분야에서 주로 등장하는 개념들이다. Group theory는 다소 어려울 수 있지만 그 아래에 놓여있는 개념들은 다소 간단하게 설명될 수 있다. 이들은 실제로 transformation으로 인하여 자연스럽게 등장한 개념들이다.

그렇다면 여기서 group과 symmetry가 의미하는 것은 무엇일까? 앞으로 symmetry에 관하여 정말 많이 이야기를 할 것이고, symmetry를 어떤 object를 보존하는 transformation으로서 여길 것이다. 여기서 object를 보존한다는 것은 어떠한 의미가 정해져있다기 보다는 우리가 정하기 나름이다. 이는 언제든지 정하기에 따라 달라질 수 있는 것이다. Image에서 symetry는 translation, rotation, squashing 등에 해당할 수 있다. 즉, transformation의 composition을 symmetry로 생각할 수 있다는 것이다.

만약 symmetry가 존재한다면, object를 보존하는 transformation을 가지는 element가 있다는 것이다. 그렇다면 여기서 object를 보존하는 transformation을 나타내는 set $\mathfrak{G}$는 무엇일까? 우리는 symmetry들의 set인 $\mathfrak{G}$를 group으로 부를 것이다. Group이라는 것은 결국 4가지 성질들(associativity, identity, inverse, closure)을 만족하는 symmetry 혹은 transformation들의 set을 의미하게 된다. 가장 먼저 associativity는 순서와 관련된 성질로, $\mathfrak{gh}$를 먼저 구하고 $\mathfrak{f}$을 나중에 구하나, 반대로 $\mathfrak{hf}$를 먼저 구하고 $\mathfrak{g}$를 나중에 구하나 결과는 같아야한다는 것이다. 우리가 object를 보존하는 transformation을 이야기하고 있기 때문에 identity를 만족하는 성질은 항상 만족해야 하는 것이다. Identity transformation $\mathfrak{e}$를 곱하는 것이 어떠한 영향도 존재해서는 안되는 것이다. Identity를 보존하는 것이기 때문에 어떠한 정보를 얻거나 잃어서도 안되는 것이다. Inverse transformation을 하여도 group $\mathfrak{G}$에 포함되어야 하고, 마지막으로 두개의 object transformation을 동시에 하더라도 그 결과가 그대로 $\mathfrak{G}$에 포함되어야 할 것이다. 결국 이러한 성질들을 모두 만족해야 group이 될 수 있고, 반대로 group에 해당하는 각 element들은 4가지 성질을 그대로 만족하게 된다.

이러한 transformation은 특정 data 혹은 signal에 대해서 $\mathfrak{g}\cdot x$ 혹은 $\rho(\mathfrak{g})x$ 와 같이 동작하게 되고, 여기서 $\rho(\mathfrak{g})$는 group representation으로 불리게 된다. 각 data에 대해서 group이 존재하는데, 예를 들어 GNN의 경우에는 $\mathfrak{g}$가 permutation이 되고 $x$는 node feature가 될 것이다. 여기서 node feature에 대해서 group representation $\rho(\cdot)$은 permutation matrix가 되는 것이다. $x$가 adjacency matrix가 된다면 $\rho(\cdot)$은 다르게 정의될 것이다. $\rho(\cdot)$는 결국 특정 data에 맞는 transformation이 될 것이다. 예를 들어, 정말 유명한 symmetry로 rotation symmetry를 생각해보자. 32x32 크기 혹인 256x256 크기의 image에 대해서 서로 다른 linear operator가 존재할 것이다. 아무래도 input data의 dimension이 다르기 때문에 서로 다른 $\rho(\cdot)$가 정의될 것이다.

Permutation Group and Symmetry

이번에는 가장 유면한 group과 symmetry로 permutation에 대해서 알아보고자 한다. 또한 우리가 지금 초점을 두고 있는 것이 GNN이기 때문에 여기에 대응되는 permutation은 우리에게 반드시 필요한 내용 중 하나이다. 그리고 graph는 매우 symmetric한 object로 이들은 vertex들의 permutation에 대해서 항상 identity를 보존하고 있기에 GNN은 GDL을 설명하는데 있어 가장 적합한 framework이다. 예를 들어, permutation은 vertex 1,2,3,4,5를 3,2,4,5,1 등의 순서로 바꿀 수가 있다. 이는 실제로 permutation matrix에 의해 수행될 수 있다. 여기서 permutation이 다소 추상적인 개념일 수 있다는 것이다. 그래서 group representation은 명시적으로 symmetric을 다룰 수 있는 쉬운 방법을 제공해준다.

간단하게 이해해보기 위해서 1,2,3,4로 구성된 graph가 주어졌다고 해보자. 그리고 이를 설명하는 adjacency matrix와 node feature matrix가 위와 같이 주어졌다. 여기서 하고자하는 것은 permutation symmetry를 실제로 적용해보는 것이다. 우리는 group element $P$를 adjacency matrix $A$에 적용할 것이다. 우리가 permutation을 adjacency에 적용하는 것은 $PAP^T$를 구하는 것과 같다. 그리고 이러한 과정은 $A$를 flatten한 것에 group representation $\rho$를 곱하는 것과 같다. Node feature의 경우에는 간단하게 permutation matrix $P$를 좌측에 곱해주면 된다. 이러한 결과는 동일한 group element $\mathfrak{g}_P$를 가지지만 이들의 group representation $\rho$가 다른 특별한 경우에 해당한다. Adjacency matrix에 대해서는 다소 큰 permutation matrix를 사용해야하지만, node feature matrix에 대해서는 단순히 원래의 permuation matrix를 사용하게 된다. 그래서 representation이 서로 다른 경우에 해당한다.

Invariant Graph Network

이번에는 invariant graph network (IGN)에 대해서 symmetry를 설명하고자 할 것이고, IGN은 여러 subgraph들로 구성될 수 있다. Subgraph는 작은 adjacency matrix로 설명할 수 있으며 이들을 여러개 쌓을 수가 있다. 여러개를 쌓기 때문에 이에 따라 high-order로 여겨지며 column, row, subgraph 관점에서 permutation이 이뤄질 수 있다. 그래서 하나의 column, 하나의 row, 하나의 subgraph에 permutation matrix를 곱할 수 있는 상황이 나오는 것이다. 그렇기 때문에 우리는 permutation symmetry를 high-order tensor로도 확장시킬 수 있는 것이다. IGN 논문을 읽어보면 실제로 group theory와 관련하여 글이 적혀 있기 때문에 밀접한 관련이 있음을 알 수 있다.

1. Invariance and Equivariance

Symmetry가 있으면 우리는 black-box function이 요구되는 행동들을 정의할 수 있다. 우리가 cat을 예측해야 한다면, transformation에 따라서 object가 보존되지 않음을 알고 있다. 고양이를 예측하는 것은 image prediction으로 invariance가 강조되는 분야이다. 그러나, segmentation의 경우에는 pixel-wise prediction을 해야하기에 equivariant task에 해당하게 된다. 즉, 고양이가 움직임에 따라서 그 결과도 달라진다는 것이다. 그렇다면 이를 어떻게 수식으로 정리할 수 있을까?

Group symmetry를 적용하는 순서를 바꿈으로써 invariance와 equivariance를 쉽게 정의할 수 있게 된다. Invariance는 data $x$가 있으면 group 혹은 symmetry를 적용했을 때 output이 바뀌면 안된다. 반대로 equivariance는 input에 transformation을 적용했을 때 대응되는 output이 달라져야 한다.

Invariance from Equivariance

Equivraiant function에 pooling을 적용해서 invariant function을 만들 수가 있다. 우리는 equivariant function을 어떻게 만드는지 알기 때문에 invariant function을 만드는 것은 다소 trivial한 것이다. 그렇기 때문에 equivariance가 invariance보다 더 큰 개념으로 생각할 수 있다.

2. Deformation Stability

우리가 지금까지 invariant와 equivariant를 이야기 했으면, 추가적으로 approximately invariant와 equivariant도 이야기해볼 수 있다. Invariance를 이야기 할때마다 우리는 object를 보존하는 transformation 하에서 얼마나 function이 바뀌는지 생각해볼 수 있다. 이로부터 결국 우리는 domain의 약간의 변형에도 안정적인 구조를 설계해야 한다.

사람들은 특정 signal이 약간의 domain 변형에도 안정적이게 만들기 위해서 Fourier representation이라는 개념을 도입하게 되었다. 여기서 Fourier representation이라는 것은 주어진 signal을 여러 signal로 표현하는 것을 이야기한다. 그리고 이들은 scale의 변형에 robust하다. 이것이 의미하는 것은 위에서 red signal이 green signal로 바뀌거나 green signal이 blue signal로 바뀌게 된다면 signal의 변화적인 측면에서는 굉장히 클 것이다. 하지만 Fourier domain에서 그 변화는 굉장히 작다는 것이다. 만약 우리가 이러한 Fourier representation을 사용하게 된다면 scale에서의 변화는 매우 작음을 의미하게 될 것이다.

3. Scale Separation Prior

여기서 우리는 scale speration prior를 가지게 되는데, 이는 data가 주어지게 되면 input의 global하거나 local한 정보 또한 주어진다는 것을 의미한다. 예를 들어, image가 있을 때 바다, 산 등이 있는데 여기에 blur 처리가 되면 이러한 detail들이 smooth해지게 될 것이다. 그럼에도 우리는 흐릿한 image에서도 산과 바다가 있다는 것 정도는 파악할 수 있게 된다. 이러한 identity를 coarse scael dominate라고 하는 것이고, 이는 global context에 해당하게 된다. 반대로 가끔은 local한 정보가 필요할 때도 있을 것이다. Image의 texture를 분류해야하는 문제를 풀 때 blur가 된다면 texture를 파악할 수 없을 것이다.

만약 우리가 global & local context를 모두 필요하게 된다면 우리는 pooling으로부터 좋은 아이디어를 얻을 수가 있다. 우리는 어떤 signal이 있을 때 coarse graining 방식으로 이를 transformation을 시킬 수 있고, 이로부터 global하고 local한 정보를 동시에 처리해볼 수 있게 된다.

Summary: Blueprint for Geometric Deep Learning

요약하면 만약 equivariance와 invariance를 가지고 있다면 symmetry에다가 특정 function을 적용해볼 수 있을 것이다. 만약 deformation stability를 가지고 있다면 approximately equivariant function을 적용해볼 수 있을 것이고, 대표적인 것이 convolution이다. 마지막으로 scale speration prior를 가지고 있다면 우리가 local & global context를 얻기 위해서 pooling operation 등을 적용해볼 수 있을 것이다. 사람들은 이와 같이 3가지 요구사항들을 GDL에서 필요한 요소들로 생각하고 있으며, 어떠한 deep learning 구조에서도 이러한 부분들을 설명할 수 있어야 한다. GNN에서는 equivariance와 invariance는 이미 집중적으로 연구가 되고 있으며 이 부분이 정말 중요한 것을 알 수가 있다.

Graph neural network (GNN)을 공부하다가 보면 한번쯤은 GNN이 geometric deep learning의 일부분이라는 것을 들어볼 수 있고, GNN에 대해서 이미 친숙하다면 geometric deep learning (GDL)에 대해서 어렵지 않게 이해할 수 있을 것이다. GNN에 대해서 어느정도 알았다면 순차적으로 다음에는 GDL이라는 거대한 파트에 대해서 알아볼 차례이다. 특히, geometric GNN에 대해서 이번에 알아볼 것이다. Geometric GNN은 3D graph에 대해서 정의되는 GNN으로, 이에 대해서는 다음에 조금 더 자세하게 알아볼 것이고, 이번에는 GDL에 대해서 간단하게 이해해보고자 한다. GDL은 3D grid 구조에 대해서 관련이 있으며, 여기에는 3D voxel, surface, graph 등이 포함될 수 있다.

What is Geometric Deep Learning?

GDL이란 무엇일까? Geometric이라는 단어를 사람들에게 물어보았을 때 원이나 삼각형 등의 도형과 관련지어 대답할 수도 있고, Euclidean 공간과 같은 개념을 언급할 수도 있을 것이다. 모두 틀린 대답은 아니지만 우리가 여기서 이야기하고자 하는 GDL에서의 geometric은 조금 다를 수가 있고, 우리는 이에 대해서 알아보고자 할 것이다.

Machine learning은 black-box function을 어떻게 골라야하는지에 대한 방법으로, GDL은 또한 이러한 질문에 대한 답변이 될 수도 있다. 예를 들어, 위와 같이 이미지가 주어졌을 때 cat, dog와 같이 이미지에 특정 단어를 mapping시켜야 한다고 해보자. 여기서 model $f$는 주어진 이미지에 대해 cat과 dog를 binary label로 mapping 시켜주는 역할을 할 것이다.

결국 model $f$의 입장에서는 단순히 input $x$가 들어오면 output $y$로 mapping시켜주기만 하면 된다. 그리고 여기서 deep neural network (DNN)은 model의 역할을 할 수 있는 하나의 선택지가 되는 것이다.

Deep Neural Networks (DNNs)

DNN을 통해서 우리가 제안하는 어떠한 machine learning algorithm을 설명할 수 있는 $f$를 선택할 수 있는 것이다.

우리는 DNN이 정말로 강력하다는 사실을 알고 있다. 충분히 많은 parameter가 주어진다면 2-layer의 DNN으로 어떠한 continuous function을 표현할 수 있다는 universal approximation theorem을 통해서도 DNN의 강력함을 설명할 수 있다. Expressive power의 관점에서 충분히 많은 parameter를 통해 DNN은 어떠한 function도 표현이 가능하기 때문에 좋은 선택지가 되는 것은 맞지만, GDL은 모든 상황에서 이러한 expressive power가 해결책이 된다고 이야기하지는 않는다.

The Problem of Overfitting

이러한 점은 바로 overfitting과 관련이 있다. DNN이 정말로 표현하는 측면에서는 강력한 수단이지만, 고차원의 data에 있어서는 쉽게 overfitting되는 문제가 존재한다. Data의 차원이 올라갈수록 더 좋은 성능을 얻기 위해 필요한 data의 수가 기하급수적으로 많이 요구되어진다. 이는 data의 개수와 overfitting 사이에서의 trade-off 관계가 된다. Parameter의 수가 많아지게 되면 그만큼의 data 수도 추가로 요구되어지는게 사실이다. 그래서 사람들은 이러한 문제를 해결하기 위해서 모델에 domain knowledge를 추가하려는 시도를 하곤한다. 이러한 domain-specific information을 이용해서 DNN을 설계한 결과가 CNN, RNN, GNN 등의 모델들이다.

Zoo of DNN Architectures

GDL은 결국 이러한 부분과 관련이 있는 것으로, GDL은 우리가 특정 상황에 맞게 domain-specific information을 모델에 주입시켜야함을 이야기한다. DNN의 구조가 특정 domain에 맞게 설계가 되어오고 있으며, 위와 같이 image에는 CNN이 어울리고 text에는 RNN이 어울리는 식으로 발전해오고 있다. 우리가 주목하고 있는 GNN의 경우에는 graph domain에 특화되었다고 이야기할 수 있다.

결국 DNN을 설계하는데 있어서 주어진 dataset에서의 characteristic이 상당히 중요한 부분으로 작용하는 것이다. 어떠한 dataset이 들어오는지에 따라 DNN의 구조를 바꿀 수 있는 것이 어떻게 보면 가장 신경써야하는 부분인 것이다. 이러한 생각이 결국 GDL의 아이디어로 연결이 된 것이다.

구체적으로 GDL이 말하고자 하는 것은 이러한 dataset의 characteristic이 우리가 geometry라고 부르는 것으로 설명될 수 있다는 것이다. Dataset의 서로 다른 geometry가 주어졌을 때, 어떻게 이러한 geometry를 DNN 구조에 통합시킬 수 있는지가 우리에게 주어진 과제인 것이다.

Why is a Geometry?

그렇다면 geometry라는 것은 구체적으로 어떠한 것을 말하는 것일까? Geometry는 여러가지로 정의가 될 수 있다. 형식적인 정의로 wikipedia에서의 geometry 정의는 "Mathmatics about measurement, properties, and relationships of points, lines, angles, surfaces, and solid."이다. 이러한 정의가 어떻게 보면 가장 informal한 정의일 수 있다. 그리고 geometry가 Euclidean geometry, hyperbolic geometry, elliptic geometry 등으로 구분될 수 있다고 하는데, 이는 어떻게보면 우리 입장에서는 조금 어울리지 않다고 생각될 수 있다. 이러한 개념들을 정의할 때는 일반적으로 역사적인 배경을 가지고 있기 때문이다. 수백년 전에 정의가 되는 이러한 개념들의 문제는 컴퓨터 공학이나 AI를 전공하는 사람들 입장에서는 그러한 의미보다는 실제로 적용하고 활용하기 위해서 이들을 refactoring이나 organizing을 거쳐 geometry를 통해 우리가 실제로 전달하고자 하는 바를 이야기해야 하기 때문이다.

Geometry

그래서 시간이 흘러 사람들이 생각을 모아 합의점에 도달한 내용이 geometry를 invariance로 이야기하고자 하는 것이다. 따라서 geometry는 특정 object의 고유한 특성과 관련된 학문이 되었고, 이러한 특성은 symmetry라고 하는 어떠한 transformation 하에서도 변하지 않는 성질을 설명하게 되었다. 어떻게 보면 이러한 것들이 철학적인 질문으로 여겨질 수 있다. 이러한 성질이 의미하는 것은 무엇이며, 여기서 transformation이 의미하는 것은 또한 무엇인지 생각해볼 수 있기 때문이다.

예를 들어, Euclidean geometry는 rotation과 translation에 invariant한 geometry이다. 이러한 transformation을 우리는 Euclidean transformation이라 부를 수 있다. 결국 Euclidean geometry는 Euclidean transformation과 관련이 있다는 것이고, 여기서 object가 rotation과 translation에 invariant하다는 것은 length와 angle에 직접적인 관련이 있기에 Euclidean geometry는 결국 length와 angle에 대해서 연구하는 것으로 정리될 수 있다. Affine geometry는 parallelism과 관련이 있으며, 이는 affine transformation에 invariant함을 설명하게 된다.

Geometry of Data

이러한 내용들을 보면 결국 geometry라는 것은 object의 identity에 관해서 연구하는 것으로 생각해볼 수 있다. 어떠한 transformation에도 변하지 않는 object의 성질이 있고 이를 identity라고 정의할 수 있으면 이를 우리는 invaraince로도 생각할 수 있는 것이다. 여기서 identity를 바꾸지 않는 transformation을 우리는 symmetry라고 부르게 된다. 예를 들어 원이나 삼각형과 같은 것은 rotation을 통해서 원래의 identity를 바꿀 수 없기 때문에 이들을 symmetry로 정의할 수 있는 것이다.

그렇다면 data의 geometry는 무엇일까? 매우 유명한 예시로 data augmentation이 있다. 우리가 data의 geometry를 이야기할 때마다 transformation에 대해서 변하지 않는 data의 identity에 대해서 말할 필요가 있다. 기본적으로 이러한 transformation은 항상 image classification 등에 대해서 이야기할 때 등장하곤 한다. 우리가 cat이라는 image가 주어졌을 때, 이를 이동시키거나 회전시키거나 아니면 크기를 바꾸더라도 identity가 바뀌는 것이 아니기 때문에 classification의 결과가 바뀌어서는 안되는 것이다.

Geometric Deep Learning

GDL은 data 특유의 symmetry를 통합하여 deep neural network를 설계하는데 필요한 아이디어이다. 그리고 이를 우리는 geometri prior라고 부를 것이다. CNN은 대표적인 GDL의 구조로, image가 가지고 있는 translation symmetry를 고려하였다.

Examples of Geometric Priors

이러한 식으로 GDL을 이용하여 다양한 framework가 등장하게 되었다. 예를 들어, 2D image에서의 symmetry를 이용하여 설계된 것이 CNN이고, text에서의 translation symmetry를 이용하여 설계된 것이 RNN이며, graph에서의 symmetry를 이용하여 설계된 것이 GNN이다. 이렇게 대표적인 3개의 neural network 외에도 3D physical data에 맞게 설계된 Euclidean neural network가 존재한다. 이러한 3D data는 3D Euclidean space에서 정의가 되며, 기존의 다른 data와는 다르게 조금 더 섬세하게 정의가 되는 부분이 존재한다.

GDL은 매우 큰 framework이며, 이는 deep learning의 핵심으로 생각해볼 수 있다. 왜냐하면 우리가 어떻게하면 자동적으로 deep learing이라는 것을 얻을 수 있는지 말하고 있으며, 지금까지도 어떻게 deep learning framework를 설계해야하는지를 알려주고 있기 때문이다. 위의 예시들은 대표적인 geometric prior들로 어떠한 invariance가 요구되어지는지를 간략하게 이야기하고 있다. 여기까지가 간단하게 GDL이 무엇인지에 대해서 알아보았다.

Research Direction 1: Generative Grammar

첫번재로 어떻게 generative grammar를 찾을 수 있는지, 어떻게 연속적으로 graph를 만들 수 있는지에 대해서 알아볼 것이다.

Graph Generation Grammar

기존의 adjacency matrix가 graph를 표현하기에 좋은 수단임에는 틀림이 없다. 하지만 adjacency matrix 외에도 graph를 표현할 수 있는 다양한 좋은 수단들이 존재할 수 있다. 이렇듯 상황에 맞게 grammar를 사용하는 방법이 deep graph generative model로 하여금 좋은 graph representation을 나타낼 수 있게 해주고, 대표적인 예시 중 하나가 adjacency matrix에서 각각의 element를 명시하는 것이다.

Adjacency matrix가 좋은 방법이지만 graph type을 명시하는데 있어서는 좋지 않다고 말하곤한다. 만약 graph의 크기가 크다면 adjacency matrix로 graph를 나타내는 것은 어려움이 존재할 수 있다. Molecule의 경우 의미있는 chemical fragment로 분해가 되어 motif와 같은 수단으로 표현이 가능할 것이다. 우리는 상황에 맞게 graph를 표현할 수 있는 방법을 찾아서 graph를 효율적으로 명시하고 생성해야할 필요가 있다.

1) Adjacency Matrix-based Graph Generation

Graph를 표현하는 가장 유명하고 쉬운 방법은 앞서 이야기한 adjacency matrix를 사용하는 것이다. 하지만 adjacency matrix를 사용하게 되면 generation을 하는데 있어서 complexity적인 문제가 발생하게 된다. Vertex 개수의 제곱만큼의 complexity가 생기기 때문에 graph의 크기가 큰 경우에는 사용하기 적합하지 못할 것이다.

만약 5,000개의 vertex가 있는 graph를 가지고 adjacency matrix를 만들어 GraphRNN을 사용하게 된다면, 25,000,000번 가량의 edge generation step이 필요하게 될 것이다.

2) {Motif, Fragment}-based Graph Generation

그래서 사람들은 molecule과 같은 특정 type의 graph 대해서는 adjacency matrix 대신에 motif와 fragment 등을 사용해서 이를 나타내기로 했다. Molecule을 보면 ring이라고 불리는 의미있는 fragment들로 구성된 것을 볼 수 있다. Ring은 cycle과는 좀 다른 구조로 atom들의 집합으로 구성된다. 위의 그림에서 ring은 5개 혹은 6개의 atom으로 구성되어 있는 것을 볼 수 있다.

우리는 이제 어떠한 fragment가 정말로 의미있는지를 확인할 수 있다. Text dataset에서 sequence로부터 어떠한 word가 의미있는지를 파악하는 것과 같은 맥락이다. 여러 의미있는 chemical fragment들이 이어져서 하나의 molecule을 구성할 수 있고, 우리는 이를 functional group으로 여기게 된다.

위와 같이 초기의 molecule 상태에서 fragment들을 이어 붙이면서 graph를 update하게 된다. 우리는 큰 chunk 단위로 하나씩 이어붙이기 때문에 node 단위로 이어 붙이던 방식과 비교했을 때 graph의 규모를 더 빠르게 키워나갈 수 있게 된다. 하지만, 이러한 방식은 전혀 보지 못한 motif를 만들어낼 수가 없다는 단점이 있다. 그래서 우리가 motif를 추출하고 생성하기 위해서는 domain knowledge가 부가적으로 필요하다는 것이 이 방식의 문제점 중 하나이다. 이렇듯 chemical knowledge를 generative model에 포함시키는 부분이 굉장히 중요한 요소이다. 사실 우리가 fragment를 가지고 있다고 하더라도 실제로 어디에 붙여야하는지가 상당히 어려운 문제이고, 또한 이어 붙인다고 하더라도 하나의 edge로 연결해야하는지 2개의 edge로 연결해야하는지 등의 다양한 문제에 직면하곤 한다.

3) String-based Graph Generation

그래서 molecule의 목적에 맞는 generation 방식으로 string-based graph generation이 존재하며, 사람들은 이를 SMILES (simplified molecular-input line-entry system)이라 부른다. 우리가 auto-regressive model을 이용해서 graph를 generation한다고 했을 때, 이미 다른 사람들이 text로부터 만들어 놓은 molecule을 이용할 수 있다. 여기서부터 SMILE의 아이디어는 시작되며 이는 매우 간단하다.

우리가 tree를 나타내고자 할 때 S-expression을 이용해서 표현할 수가 있다. 이는 tree를 표현할 때 bracket을 이용해서 sub-tree를 나타내는 등 tree 구조를 설명할 수 있는 대표적인 표현법 중 하나이다. SMILES은 어떻게 보면 S-expression의 수정된 버전으로 생각할 수 있다. 표현하고자 하는 molecule이 주어졌을 때, 사람들은 우선 spanning tree를 graph로부터 찾고자 할 것이다. 이러한 점에서 molecule을 생성한다고 하면 위와 같이 우선 spanning tree를 만들고나서 남은 residual edge들을 이어붙이는 식으로 graph를 완성하게 된다. 그리고 만약 indicator 1~4를 제거한다고하면 우리는 tree representation을 얻게 된다. 반대로 indicator를 남기게 된다면 전체 graph를 얻게되는 식이다.

Molecule은 특수한 형태의 graph이고, molecule 안에는 약간의 ring 구조를 포함하게 될 것이다. 약간의 ring 구조를 가진다는 것은 molecule graph를 tree를 사용해서 근사하려고 한다면, 약간의 edge가 남아있게 될 것이다. 왜냐하면 ring은 edge의 전체 숫자에서 spanning tree의 edge와의 차이만큼 존재하기 때문이다.

지금까지 본 SMILES 표기법이 deep learning의 관점에서 조금 이상해보일 수 있다. 아무래도 이러한 방식은 화학쪽 분야에서 molecule을 표현하는 방식이기 때문이다. 그래서 실제로 SMILES 표기법으로 molecule을 생성한다고 했을 때, text generative model을 이용해서 text를 만들어내는 식으로 molecule을 만들게 된다. Language 기반의 model로 molecule을 text 형태로 만들어냈다면 이후에는 특수한 decoder를 활용하여 이를 graph 형태의 molecule로 만들어내면 된다. String 기반의 generative model은 molecule을 만들어내기에 최적화 된 쉬운 방법 중 하나이다.

4) Tree-based Graph Generation

지금까지 본 SMILES는 graph가 주어졌을 때 linear string으로 graph를 나타내는 방법이었다. 이를 좀 더 자세히 살펴보면 결국에는 graph를 일종의 tree로 변환하는 작업을 수행하게 된다. 특히 이러한 tree가 결국에는 text나 string으로 변환이 되었던 것이고, 이번에 살펴볼 tree-based graph generation에서는 tree 구조로부터 graph를 연속적으로 만들기 위한 grammar를 설계한다고 생각하면 된다. 여기서 tree는 원래의 molecular graph의 근사된 버전으로 볼 수가 있다. 결국 molecule graph와 tree를 양방향으로 변환할 수 있도록 grammar를 잘 설계해야하는 것이 tree-based graph generation의 핵심인 것이다. 기존의 text generation model보다 tree generation model이 원래의 graph 구조에 대한 더 많은 insight를 제공해줄 수 있다.

5) $K^2$ Tree-based Graph Generation

Tree 기반의 방법이지만 graph의 특성들을 좀 더 clustering하는데 중점을 두는 $K^2$ Tree-based graph generation 방법도 존재한다. 예를 들어, 우리는 community나 social network는 하나의 큰 graph 속에 커다란 여러 sub-graph들이 존재한다는 prior knowledge를 어느정도 가지고 있다. 그리고 이렇게 큰 sub-graph들로 구성된 cluster 사이에는 edge가 거의 없다는 것도 어느정도 가정할 수 있다. 그래서 여기서 하고자 하는 방법은 이러한 사전지식들을 이용해서 더 효과적으로 graph를 생성하고자 하는 것이다.

이러한 가정 속에서 하나의 커다란 adjacency matrix 속에 0으로 이루어진 커다란 집단과 1이 어느정도 포함된 여러 집단들로 나눌 수가 있을 것이다. 그래서 하나의 element를 만들기보다는 조금 큰 단위의 집단을 한번에 생성할 수 있을 것이고, 이를 위해서 우리는 $K^2$-Tree라는 것을 만들 수가 있다.

$K^2$-Tree는 matrix의 0으로부터 계층적 구조를 표현할 수 있다. 위와 같이 우측의 adjacency matrix와 같은 결과로 좌측과 같은 hierarchical tree를 구성할 수 있게 된다. 이러한 식으로 하나의 chunck를 만들게 되면 하나의 element를 만드는 과정보다 더욱 효과적으로 graph를 생성할 수 있게 된다.

Summary

지금까지 살펴본 여러 graph generation에 대한 grammer를 어떻게 얻을 수 있는지 알아보았다. 상황에 맞는 generation 방법을 적용하는 것이 더 나은 결과로 이어질 수 있을 것이다.

Research Direction 2: Probabilistic Frameworks

이번에 살펴볼 probabilistic framework는 이전에 보았던 auto-regressive model과는 다소 방향성이 좀 다르다. 하지만, 이러한 방법들도 최근에 사람들이 많은 관심을 가지고 연구되어지고 있다. 흔히 diffusion model이 여러 영역에서 성공적으로 결과물을 만들었기 때문에 graph 영역에서 또한 diffusion 연구가 활발히 진행되어지고 있다. 기본적으로 graph는 discrete한 구조를 가지고 있기 때문에 continuous한 framework인 diffusion이 graph에 잘 동작하도록 만드는 과정은 정말 최근에 와서야 조금씩 성공을 보이고 있다.

Autoregressive Models for Graphs

Auto-regressive model들이 최근에 graph generation에서 상당히 좋은 결과들을 보여주고 있었지만, 한번에 하나의 element를 만든다는 점은 이 모델들이 느릴 수 밖에 없음을 보여주게 된다. 그래서 한번에 여러개의 element를 생성하는 과정이 있어야 더 빠르고 효과적으로 graph generation을 성공할 수 있도록 해준다.

처음부터 graph generation을 하고자 한다면, autoregressive model을 사용하는 것이 나쁜 선택이 아닐 것이다. 아무래도 tuning하는 과정이 어렵지도 않으며, 이에 따른 성능도 어느정도는 보장되어 있기 때문이다. 이 model들의 흥미로운 부분 중 하나로 graph의 permutation symmetry를 보장하지 않는다는 것이다. 예를 들어, 위와 같이 C-N-C 구조의 graph를 만든다고 했을 때, 똑같은 결과를 만들기 위해서 다양한 방법이 존재할 수 있다. 이렇게 auto-regressive model을 이용해서 graph를 생성하게 되면 만드는 순서에 따라 확률이 달라지게 된다.

Diffusion Models

이번에 알아볼 diffusion model의 경우 graph를 생성하는데 있어 node ordering과 관련이 없어 autoregressive model과는 다르게 permutation symmetry를 보장할 수 있게 된다. Diffusion model은 동시에 data의 모든 element를 generate할 수 있다. Image에서의 diffusion model은 image가 주어지면 noise를 조금씩 추가해서 완전한 noise distribution을 만들어주게 된다. 그리고 generative model을 이용해서 이로부터 다시 image를 만드는 과정을 학습하게 된다.

Diffusion Models for Graphs

Graph에서도 마찬가지로 adjacency matrix를 image와 같다고 생각하면 이해하기 쉬울 것이다. Noise distributino에서 시작해서 완전한 graph가 될 때까지 diffusion model을 학습시켜서 만들 수 있다.

Continuous Diffusion Models

Vertex의 크기만큼 adjacency matrix를 구성할 수 있고, continuous diffusion model을 이용하면 edge가 연속된 값으로 만들어지게 되는데 아무래도 원래 edge의 경우 binary 숫자로 존재성을 나타내기 때문에 thresholding을 거쳐서 graph를 만들 수 있게 된다.

Discrete Diffusion Models

이후에 사람들은 diffusion model을 discrete data에 적용하고자 많은 연구들을 진행해왔다. Diffusion model은 임의의 categorical data에 동작하도록 설계가 되어 있기 때문에 graph에 더 적합하도록 수정할 필요가 있었다.

Summary

요약하면 autoregressive model은 꽤 robust하면서 괜찮은 성능을 보여주었고, diffusion model은 autoregressive model에 비해서 성능적으로 아쉬운 부분이 많지만 얼마 안가서 분명 괜찮은 결과를 보여줄 것이다. 이 두가지 방법을 언제 활용하냐고 물어본다면 graph data가 text data와 같이 생겼다면 autoregressive model이 더 잘 동작할 것이고, graph data가 image data와 비슷하다면 diffusion model이 더 잘 동작할 것이다. 상황에 맞게 적절한 방법을 선택하고 적용해보면 될 것이다.

이번에 알아볼 deep graph generative model은 이전까지 알아보았던 graph representation learning과는 조금 다르다. Graph와 더불어 최근에는 굉장히 쉽게 고화질의 image와 괜찮은 text를 deep generative model로부터 만들 수가 있다. 대표적으로 ChatGPT는 우리가 물어보는 것에 대해서 굉장히 좋은 답변들을 제시해주고 있다. 예를들어 "An illustation of an avocado sitting in a therapist's chair, ..."과 같은 프롬프트를 입력했을 때 위와 같은 결과를 얻을 수가 있는 것이다. 또한, ChatGPT는 일반적인 답변 이외에도 유머러스하고 독창적인 답변들을 많이 제공해주기도 한다.

우리가 deep generative model로부터 얻을 수 있는 가장 중요한 부분은 우리가 ChatGPT와 같은 플랫폼에 science와 관련된 질문을 했을 때 믿을 수 있는 답변들을 제공받을 수 있다는 것이다. Science는 아무래도 현실 세계를 가장 잘 반영할 수 있는 영역이기에 이와 관련되어 신뢰할 수 있는 답변은 우리에게 굉장히 중요한 요소로 다가오게 된다. 가령, deep generative model을 기반으로 하는 ChatGPT와 같은 플랫폼은 슈뢰딩거 방정식을 어떻게 푸는지나 특정 시스템의 규칙이 무엇인지 등과 같은 질문에도 믿을 수 있는 답변을 제시해야 한다.

하지만, 모두가 알듯이 ChatGPT는 science 관련 문제를 제대로 풀지는 못한다. 위와 같은 ChatGPT에 "Moledcule that cures cancer"가 무엇이고 "Room-temperature superconductor"를 어떻게 설계하는지 물어보았을 때, 우리가 얻는 것은 의미가 없는 결과들일 것이다. 왜냐하면 image data나 text data는 위와 같은 질문들에 대한 답변을 하기에는 적합하지 않기 때문이다. Image나 text는 이와 같은 중요한 scientific object와 관련해서 제대로 표현하기 어렵기 때문이다. Science 저널 등을 보게되면 수많은 diagram과 graph 기반의 구조물들을 많이 볼 수가 있을 것이다. 특히 3D와 관련해서는 voxel과 같은 여러 building block들로 연결되어 있기 때문에 이를 image나 text로 생성한다는 것에는 한계가 존재하기 마련이다. 그렇기 때문에 graph를 생성할 수 있는 deep generative model이 필요한 것이다.

Deep Generative Models for Graphs

이렇듯 최근에는 deep generative model을 이용하여 여러 graph를 만들고 있다. 대표적인 graph 기반의 generation task로는 molecular graph generation, morphology graph generation, 그리고 polygon graph generation 등이 있으며, 이렇게 만들어진 graph들은 신약 개발에 사용되거나 새로운 로봇을 만들거나 등에 활용될 수가 있을 것이다.

Molecule이나 robot과 같은 topological data를 만들어내기 위해서 결국에는 이에 적합한 generative model을 설계하는 것이 중요하다. 결국, 우리가 deep graph generative model을 이용하여 여러 목적에 맞는 graph를 만들어 추후에 과학과 산업에 도움이 되는 것이 최종 목표라고 할 수 있다.

결국 우리가 왜 graph generative model을 설계해야하는지 묻는다면 이는 중요한 과학과 산업에서 여러 문제들을 해결하기 위해서라고 대답할 수 있다. 그리고 이와 관련하여 2가지 challenge들을 해결하는 방법들에 대해서 살펴볼 것이다.

Promise: Industry & Science

Generating Molecules

가장 먼저 알아볼 것은 molecule generation이다. Graph generative model은 새로운 약과 물질들을 만들 수 있는 molecule들을 생성할 수가 있다. 우리가 어떻게 약을 발견하고 어떻게 물질들을 발견할 수 있는지와 관련해서 여러 산업에 도움을 줄 수 있다.

특히 이와 관련된 산업들의 규모는 실제로 굉장히 크다. Comuputer science에서 지원받는 자금들과 비교해서 medical/life science가 지원받는 금액들을 살펴보면 실제로 규모가 얼마나 큰지 확인할 수 있다. 그리고 실제 하나의 신약을 개발하는데 들어가는 시간은 약 10년 정도로 그 기간이 상당한 것을 알 수 있다. 우리가 인공지능 모델을 이용해서 이러한 문제를 직접적으로 해결할 수는 없겠지만, 신약을 개발하는 이러한 과정을 가속화시키는데 도움을 줄 수는 있을 것이다.

Insilico Medicine은 신약 발굴을 위한 AI 플랫폼을 개발한 회사로 위와 같이 특정 protein structure들을 엮을 수 있는 molecule들을 설계할 수 있는 플랫폼을 개발하기도 하였다.

Reaction and Retrosynthesis Prediction

Graph generation model은 또한 reaction prediction이나 retrosynthesis prediction에도 사용될 수 있다. Reaction prediction은 반응물로부터 어떠한 화학 반응이 일어날지 예측하는 것이고, retrosynthesis prediction은 기존의 화학 반응으로부터 어떠한 반응물들이 필요하는지를 예측하는 것이다.

IBM은 실제로 이러한 반응들을 예측할 수 있는 platform을 개발하기도 하였다.

Robot Morphology Graph Generation

Robot morphology는 로봇의 형태와 관련한 분야로, 이는 graph로 표현될 수 있어서 gerative model로 이 또한 생성할 수가 있다. 그래서 어떠한 로봇이 계단을 오른다고 했을 때 이 로봇이 어떠한 형태로 되어있어야 하는지를 generative model이 예측해서 만들 수가 있다.

Scene Graph Generation

Computer vision 분야에도 graph와 관련해서 유명한 task가 존재한다. 바로 각각의 object를 graph로 표현하여 해당 장면을 예측해야하는 scene graph generation이다. 하나의 image를 graph로 표현하여 각각의 물체와 이 물체간의 관계를 설명할 수 있는 것이다.

Polygon Generation

Polygon generation은 3D shape을 설계하는 것이 목적이다. Mesh의 face가 graph에서의 node가 되고, mesh의 boundary가 graph에서의 edge가 되는 것이다. 따라서 3D polygon을 생성한다는 것은 graph를 만드는 것과 동일하게 볼 수 있다.

Basics: Graph Generative Models

Graph generative model에 대해서 본격적으로 알아볼 것이고, 가장 먼저 어떻게 문제 정의를 하는지 보고자 한다. 우리는 graph dataset에 초점을 두고 각 graph $G$는 data distribution $p_{data}(G)$로부터 sampling된다고 가정하자. 이러한 distribution을 기반으로 model이 새로운 model distribution $p_{model}(G;\theta)$ 학습할 것이고, 새로운 graph가 이로부터 sampling 될 것이다.

우리는 가장 직관적인 방법 중 하나인 autoregressive model에 대해서 먼저 알아볼 것이다. Autoregressive model은 distribution을 chain rule로써 표현할 수 있고, graph를 sequence로 parameterization하여 표현하게 된다. 그래서 autoregressive model은 model distribution $p_{model}$을 만들어 density estimation과 sampling에 사용하는데, 이때 chain rule을 사용하여 위와 같이 joint distribution을 각각의 conditional distribution들의 곱으로 표현하게 된다. 여기서 각 $x$는 특정 graph에 해당하고, $x_t$는 이전의 graph를 기반으로 특정 $t$번째 action을 설명하게 된다. 아무것도 없는 공간에 vertex를 추가하고 edge를 추가하고 또 vertex를 추가하는 등의 행동을 반복해서 최종 graph를 구성하게 되는 것이다. 그래서 각 시점의 graph에 대한 conditional graph를 모두 곱하여 model distribution을 나타내는 것이고, autoregressive model은 이러한 action 하나하나를 예측하게 되는 것이다.

GraphRNN Idea

가장 유명한 graph generative model 중 하나는 GraphRNN로, 연속적으로 vertex와 edge를 연결시켜서 graph를 만들게 된다. 이를 위해서 가장 먼저 vertex에 ordering을 해야한다. 1번 vertex를 만들고 2번 vertex를 만든 다음에 이를 연결하는 edge를 추가해준다. 그다음에 3번 vertex를 만든 다음에 1번 vertex와 연결하는 edge를 추가한다. 이러한 식으로 각 vertex에 특정 순서를 매겨서 graph를 만들어나가는 것이 GraphRNN의 아이디어이다.

Model Graphs as Sequences

개념적으로는 정말 간단하나 실제로 어떻게 vertex를 추가해서 graph를 만들어나가는지 알아보고자 한다. 이는 text generation model과 비슷한 맥락에서 이해할 수 있다. 각각의 action을 vertex를 추가하는 것으로 본다면 이러한 action들의 sequence $S^\pi$를 우리는 구할 수 있을 것이다. 즉, 첫번째 vertex를 추가하는 action을 sequence $S^\pi_1$로 보고, 두번째 vertex를 추가하는 action을 sequence $S^\pi_2$로 생각할 수 있을 것이다. 각각의 action들을 전부 모아서 sequence $S^\pi$를 만들게 되면 마지막에 우리는 하나의 완성된 graph를 얻게되는 것과 같아진다. 여기서 $S^\pi_1, S^\pi_2, ...$를 우리는 discrete word, vocabulary, text 등으로 간주할 수 있다.

이러한 식으로 만들어지는 graph는 node ordering으로 정의되어진 것이다. 각 node에 숫자를 부여하게 되면 순서에 맞게 node가 추가되는 식으로 graph를 만들 수 있는 것이다. 그렇다면 컴퓨터는 이러한 ordering을 어떻게 이해해서 쉽게 graph를 만들 수 있는 것일까? 지금까지는 하나의 node를 한번씩 추가하는 방식으로 graph를 만들었지만, 이외에도 edge를 추가해서 graph를 만드는 방법도 존재하게 된다. 실제로 node ordering에서는 vertex를 추가할 때마다 연결되는 edge도 자동으로 추가되고 있는 것이다.

Edge-level에서 4번째 vertex를 추가하는 sequence $S^\pi_4$를 보면 순서대로 해당 vertex와 edge가 연결되어 있는지를 binary 숫자를 이용해서 나타낼 수가 있다. 예를 들어, 위의 그림에서 4번 vertex는 1번과는 연결되어 있지 않고 2,3번과 연결되어 있기 때문에 $S^\pi_4$가 0,1,1이 되는 것이다. 그래서 만약 특정 sequence가 011로 표현되어 있다면, 이는 4번째 vertex를 추가하는데 있어 2번째와 3번째 vertex와 연결되어 있음을 해석할 수가 있다.

정리하자면 우리가 어떤 graph와 node ordering이 주어졌을 때, 우리는 이를 sequence들의 sequence로 해석할 수가 있게 된다. 각각의 vertex에 대응하는 sequence가 존재하고, 이들을 전부 모아놓은 sequence가 graph가 되기 때문이다. $S_2$의 경우에는 1번과 연결되어 있어서 1이고 $S_3$의 경우에는 1번과 연결되어 있고 2번과 연결되어 있지 않아서 10이고 $S_4$의 경우에는 1번과 연결되어 있지 않고 2,3번과 연결되어 있어 011인 것이다. 이들을 잘 모아서 adjacency matrix로 해석하면 upper traingle이 바로 graph가 어떻게 구성되어 있는지를 나타내고 있는 것이다. 따라서 GraphRNN은 이러한 graph를 sequence로 만들고자 하는 방법이고, 각 sequence를 하나의 column으로 하는 adjacency matrix를 구성해야 하는 것이다.

GraphRNN: Two Levels of RNNs

이렇듯 GraphRNN은 node level과 edge level로 구성되어 two level로 볼 수 있다. 특히 RNN구조가 node level에서 먼저 이루어지고 이후에 edge level에서 이루어져 two level RNN으로 설명이 가능한 것이다.

Issue: Tractability

이렇게 graph 하나를 만드는데 two level로 만들다보면 다소 복잡하다고 생각할 수 있다. GraphRNN은 정말로 유명한 baseline 중 하나이기 때문에 어떻게 보면 문제점이 다수 존재하는 모델로 파악될 수 있다. 가장 대표적으로 graph의 tractability가 문제점 중 하나이다. 이것이 의미하는 바는 우리가 GraphRNN을 실행시켰을 때 complexity가 높다는 것을 의미하게 되어 edge generation을 하는데 있어서 너무 많은 step이 필요하게 된다. 우리가 1,000개의 vertex가 있을 때 1,000,000개의 edge를 만들어야 하는 상황이 생길 수도 있게 된다. 이렇듯 random node ordering의 경우 edge generation시 이전의 모든 vertex들을 고려해야해서 complexity가 증가하게 된다.

그래서 사람들은 이러한 complexity를 어떻게 하면 줄일지 생각하게 되었다. 사실 대부분의 graph는 굉장히 sparse한 형태로 존재하게 된다. 우리가 이러한 sparsity만 가정하고 보장할 수 있다면 평소보다 빠르게 graph를 만들어낼 수 있을 것이다.

Solution: Tractability via BFS

이러한 sparsity를 가정하고 사람들은 Breadth-First Search(BFS)를 이용해서 실질적으로 기존의 tractability 문제를 해결하려고 했다. 그렇다면 왜 BFS일까? 바로 BFS가 가지는 powerful한 가정때문이다. 만약 우리가 BFS를 graph에 적용하게 된다면 random ordering과는 다르게 tree가 만들어지고, 이 tree는 width의 크기가 제한될 것이다. 이를 adjacency matrix의 관점에서 본다면 0으로 채워지는 공간이 생겨 결과적으로 연산량이 크게 줄어들게 될 것이다.

쉽게 생각해보면 BFS에 따라 인접한 vertex들에 따라 node ordering을 진행하게 되면 해당 경우의 수가 상당히 줄어들고, 인접한 vertex들과의 관계만 고려할 수 있기 때문에 기존의 문제중 하나였던 long-term dependency 문제도 해결할 수 있게 된다. 위의 예시에서 node 5를 만든다고 해보자. 이미 node 1~4까지는 추가가 된 상태이다. 여기서 우리는 BFS를 사용했기 때문에 node 5가 node 4 이전에 만들어졌다는 가정을 없애도 되는 것이다. 그렇다면 node 4번보다 더 먼저 추가가 되어지고 이후에 node 4가 추가되어야 되기 때문에 BFS를 사용하는 순간부터 강력한 조건을 달고 graph를 만들어나갈 수 있는 것이다.

만약 node 4가 node 1과 연결되어 있지 않고 node 5가 node 4와 연결되어 있다면 node 5는 자연스럽게 node 1과 연결되어 있지 않음을 파악할 수도 있다. 이렇듯 BFS를 사용하면 node ordering의 경우를 줄일 수 있음과 동시에 edge generation의 step도 줄일 수 있게 된다.

마지막으로 over-squashing 현상을 해결하는 방법으로 cooperative graph neural network에 대해서 알아보자. 이 방법은 기존의 graph rewiring을 manual하게 하는 것이 아니라 이 과정을 학습하고자 한다. 먼저 각 vertex의 state를 부여해준다. 여기서 state는 각 vertex가 이웃과 연결되어 정보를 주고 받을 수 있는지 아니면 고립되어 있는지를 나타낸다. 각 vertex를 하나의 player로 설정해서 'listen', 'broadcast', 'listen and broadcast', 'isolate'와 같은 상태를 할당받게 되는 것이다. 기존의 message propagation의 경우 모든 node가 이웃들에게 'listen and broadcast'를 하는 상태를 부여받은 특수한 경우에 해당하게 된다. 이와 다르게 저자들은 좀더 flexible하고 dynamic한 message passing을 위해서 모든 node가 주어진 state에 맞게 propagation 전략을 세울 수 있도록 만들었다. 이렇게해서 network의 각 layer마다 message passing 구조를 조절할 수 있도록 만들었고, 이를 통해 over-squashing 현상을 해결하고자 하였다.

제목이 cooperative graph neural network인 이유가 각 vertex가 다른 vertex와 서로 협력하여 squashed된 정보를 피하고자 하기 위해서이다.

각 layer마다 node들은 discrete한 결정을 취하게 되며, 어떻게보면 이러한 방식이 reinforcement learning과 유사해보일 수 있다. 각 vertex마다 확률적으로 특정 행동을 취해야하는 점은 reinforcement learning의 방식을 따르고 있다. STANDARD는 동시에 message를 처리하여 정보를 만들어 전달하는 것을 의미한다. LISTEN은 오로지 input으로 listen만 받게 된다. 반대로 BROADCAST는 listen을 밖으로 보내는 것을 말한다. 마지막으로 ISOLATE는 이웃들과 어떠한 행동도 취하지 않는 것을 의미한다.

Input으로 node feature가 주어졌을 때 policy network가 각 state에 따른 확률들을 각 node에 할당하게 된다. 각 state의 확률로부터 해당 node가 어떠한 state를 가지게 되는지 결정할 수 있다. Message passing이 BROADCAST나 ISOLATE의 경우에는 끊어지게 되며, 반대로 STANDARD나 LISTEN일 때에는 연결되어 정보를 aggregation하게 된다. 만약 여기서 network를 학습시키고 싶으면 discrete optimization을 수행해주면 된다. 이는 위와 같이 straight-through Gumbel-softmax estimator를 사용해주면 되는데, 이는 discrete variable들을 학습해준다. Cooperative graph neural network는 실험 결과도 굉장히 흥미롭지만 아이디어 자체만으로도 충분히 재미있는 방법이다.

이 논문에서는 universal approximation theorem을 위와같이 이야기하고 있다. 이는 expressiveness power를 정량화하는데, 만약 충분하게 전체 graph를 평균화시키면 어떠한 graph function도 approximation할 수 있음을 이야기한다. 이러한 아이디어는 GNN에서 random augmentation과 비슷하다. 만약 무작위로 graph를 augment한다면 GNN의 expressiveness power가 올라가게 된다.

이번에는 over-squashing 현상과 관련하여 expander graph의 개념을 기반으로 해결하려는 expander graph propagation에 대해서 알아보고자 한다. 이는 negatively curved graph에 대한 이론적인 분석을 중심으로 구성되어 있어 흥미로운 부분이 많다. Over-squashing 현상은 graph의 toplogy에 따라 발생한다. 특히 negatively curved edge나 graph는 Cheeger constant와 관련이 있다. 여기서 graph의 bottleneck 현상을 수학적으로 정의한 이 constant 값이 작을수록 over-squashing 현상과 밀접한 연관성이 존재한다. 그렇다면 message passing을 위한 최적의 graph가 어떠한 상태여야하는지 궁금해하였다. 그것은 Cheeger constant 값이 큰 graph로, 이를 expander graph라고 정의하게 되었다.

만약 expander graph가 message passing을 위한 최적의 graph라고 한다면, 어떻게 이것을 사용해야 좋은 결과를 얻을 수 있을지를 저자들은 설명했다. 아이디어는 굉장히 단순하다. 주어진 graph에서 시작해서 message passing을 적용하기 위해서 expander graph를 사용하고 다시 원래의 graph로 돌아오고 다시 expander graph를 사용하는 식의 방식으로 동작하게 된다. 이들은 가상의 message passing 기법을 추가한 것이다. 여기서 이들은 Cheeger constant 값이 큰 expander graph인 Cayley graph를 사용했다. 이 graph는 node들이 상당히 interconnected 되어 있기 때문에 어떠한 vertex 쌍을 선택하더라도 이들을 연결하는 path가 존재하게 될 것이다. 전체적으로 graph 상에서 path의 분포가 고르게 존재하게 되는 것이다. 이러한 graph는 interconnection이 잘 되어 있지만, 아직 sparse하고 이웃들간 지역적으로 tree의 구조를 보이는 것이 이 graph의 특징이다.

Expander Graph Propagation

다시 아이디어를 살펴보면 매우 간단하다. 주어진 input graph가 over-squashing 현상을 가지고 있는 상태에서 원래의 GNN을 가지고 첫번째 layer를 update한 다음에 두번째 layer의 경우에는 expander graph를 이용해서 update하는 것이다. 이러한 과정을 계속해서 반복하면 expander graph propagation이 된다. Expander graph를 사용해서 vertex 쌍의 정보를 모두 가지게 되어 over-squashing 현상을 완화할 수 있다.

원래의 graph와 Cayley graph를 번갈아 사용하는 것이 결국 이 방식의 전부인 것이다.

이번에는 over-squashing 현상을 해결할 수 있는 graph rewiring의 알고리즘적 접근법에 대해서 알아볼 것이다. 이전에는 이론적인 접근법들을 살펴보았는데, 이번에는 알고리즘적으로 어떻게 접근해서 over-squashing 현상을 완화할 수 있는지 알아보자. ICML 2023에 나온 방법에 대해서 알아볼 것이며, 이는 graph rewiring을 단순히 수행하기보다는 dynamic graph rewiring을 수행하는 것이 더 효과적이라 이야기했다. 이 방법은 over-squashing 문제를 해결하는 방법으로 edge를 아무 곳이나 추가해도 된다고 한다. 만약 정보가 잘 흐르지 않는 vertex 쌍이 있다고 하면 여기에 edge를 추가할 수 있을 것이다. 하지만 over-squashing과 over-smoothing 사이에는 고유한 trade-off가 존재한다. Graph에 edge를 추가하게 되면 graph가 전체적으로 더 평균화가 되어 over-smoothing 현상에 더 민감해질 것이다. Graph의 크기가 커짐에 따라 학습 시간도 증가할 것이다. 그리고 rewiring task를 하게 되면 input graph를 수정하게 되는데, 이에 따라 기존의 정보들을 잃을 수도 있다.

Dynamic Edge-Addition and Delay

Graph rewiring algorithm이 graph가 주어졌을 때 over-squashing 현상을 해결하기 위해서 어떻게 graph를 수정해야하는지와 관련이 있다. 그러나 이 dynamic graph rewiring을 제안한 저자들은 graph rewiring을 단순히 수행하기보다는 GNN의 서로 다른 layer 사이에 edge를 추가하자는 것이었다. 그래서 layer마다 graph 사이에 connection을 추가할 수 있다. 0번째 layer에서 1번째 layer에 edge를 추가하기도 하고, 0번째 layer에서 2번째 layer로 edge를 추가하기도 한다. 이는 어떻게 보면 residucal connection과 비슷한 방법이지만, 이 방법은 동일한 vertex 사이가 아닌 다른 vertex와 connection을 추가하는 방법이다.

$\nu$-DREW in Equations

그래서 정보를 aggregation할 때 이전 layer뿐만 아니라 $k$만큼 떨어진 이웃들에 대해서 $\tau_\nu(k)$ layer에도 수행하게 된다. 만약 3개의 layer 이전부터 정보를 모은다고 하면 결국 3-hop 떨어진 이웃들로부터 정보를 모으는 것과 같아지게 된다. 여기서 $\nu$ factor를 infinity로 하면 원래의 rewiring 기술과 같아지게 된다. 결국 이러한 방법은 기존의 rewiring 방법의 generalization 버전인 것이다.

Advantages of $\nu$-DREW

이들이 제안한 방식의 장점은 graph가 더 효율적인 framework를 만들기 위해서 각 layer에 점진적으로 채워진다는 것이다. 그리고 더 가까운 node는 일찍부터 상호작용하기 때문에 input graph로부터 inductive bias를 보존할 수 있다. 이는 단순히 멀리 떨어진 vertex 사이에 임의의 edge를 추가하는 것과는 다르다. 이전에는 사람들이 멀리 떨어진 vertex 쌍을 선택해서 이들 사이를 연결하려는 시도를 하였지만, 이번에 살펴보는 이 방법은 $k$-hop neighbor connection을 기반으로 이루어지기에 기존의 정보를 더욱 잘 보존하게 된다. 이러한 방식은 결국 over-smoothing 현상 또한 완화하는데 이점을 가지게 된다. 비록 멀리 떨어진 vertex를 연결한다고 하더라도 서로 다른 layer를 통해서 연결하기 때문에 smoothing 현상이 발생할 가능성이 낮아지게 된다.

Long-Range Graph Benchmarks

이 방법은 또한 long-range dependency를 가지는 새로운 graph benchmark를 소개하여 유명해지기도 했다. 이 dataset은 GNN이 long-range dependency를 인지할 수 있는 능력을 가지는데 확인할 수 있는 좋은 benchmark이다. 이는 peptide나 protein을 나타내는 molecule들로 구성되어 있다. PASCALVOC는 image의 super-pixel을 기반으로 하는데, 이는 image의 graph representation과 같다. PCQM은 또다른 molecule dataset이다.

이러한 실험들을 통해서 long-range dependency와 관련해서는 graph transformer가 기존의 GNN보다 좋은 성능을 보여주었다. 아무래도 graph transformer가 long-range dependency를 잘 파악할 수 있는 구조를 지니고 있다. 하지만 저자들은 graph transformer가 없어도 long-range dependency를 잘 파악할 수 있으며 graph rewiring을 제안하는 방식대로 하는게 transformer보다 더 좋다고 주장했다. 왜냐하면 이들이 제안한 방식은 parameter의 수가 적어서 over-squashing 문제를 크게 겪지 않기 때문이다.

이 논문에서 위의 그림은 다소 흥미로운 부분이 있다. 기존의 GCN이나 rewiring 방식의 DRew-GCN의 경우 lyer의 수를 증가시킴에 따라 over-squashing 현상을 겪는 것을 보여주고 있다. Layer를 쌓기 시작하면 expressive power가 강력해져 성능이 오르는 것을 확인할 수 있지만, 점점 많이 쌓기 시작하면 over-squashing 현상 때문에 성능이 오르지 않는 것을 볼 수 있다. 하지만, 이들이 제안하는 방식을 사용한 GCN의 경우 layer를 쌓을수록 성능이 계속해서 오르는 것을 확인할 수 있다. 이러한 실험적 결과로부터 이들은 over-squashing 문제를 극복했다고 이야기했다.

오늘 알아볼 내용은 GNN의 이론적인 분석에서 꽤 비중이 있는 paradiam에 대해서 알아볼 것이다. 바로 over-squashing 문제이다. GNN을 어떻게 설계하고 GNN의 expressive power를 어떻게하면 올릴지도 중요한 내용들이다. 이러분 부분 외에도 이번에 살펴볼 몇몇 방법들은 GNN에서의 over-squashing 문제를 해결하기 위해서 초점을 두고 있다. 약 2022년까지 사람들은 GNN의 expressive power를 올리는데 정말 많은 노력을 기울였다. 최근에 특히 이론을 주로 다루는 사람들은 over-squashing 문제에 집중하여 해결하려고 했다. 기존의 over-smoothing 문제도 중요한 문제이지만 이번에 알아볼 over-squashing 문제 또한 GNN에 있어 중요하다.

우리는 message passing neural network(MPNN)으로부터 이야기를 시작하려고 한다. 기존의 notation과 다르게 update function 대신에 이번에 우리는 combination function으로 사용하려고 한다. Message passing network를 사용하기 때문에 message passing aggregation step이 vertex들의 이웃들을 기반으로 한다는 가정이 존재한다.

Common Problems in MPNNs

우리가 MPNN에서 발생하는 문제들을 이야기할 때 물론 expressive power에 대해서 이야기해볼 수 있지만 이를 제외하고 사람들은 가장 먼저 over-smoothing 문제를 언급할 것이다. 이렇든 over-smoothing 문제도 중요하지만 under-reaching 문제와 over-squashing 문제 또한 중요한 부분이기에 차례대로 살펴보고자 한다. 하지만 over-smoothing 문제는 자세하게 이야기하지 않으려고 한다. 아무래도 over-squashing 문제 보다 사람들이 덜 형식적으로 정리해놓은면이 존재하기 때문이다. 그래서 이번에 over-squashing 문제를 자세하게 살펴보려고 하는 것이다.

Under-Reaching Problem

가장 먼저 under-reaching 문제이고, 이는 상당히 간단한 문제이다. 특정 정보가 MPNN의 여러 layer들 중에서 어느 layer 이상으로 전달되지 않는 현상을 under-reaching이라고 한다. 여기서 우리는 위의 예시에서 노란 vertex와 초록 vertex 사이의 상호 작용에 관심을 가질 것이다. 노란 vertex와 초록 vertex 사이의 정보를 주고받기 위해서는 둘 사이에 어느정도 거리가 존재하기 때문에 GNN의 관점에서 여러 layer을 쌓을 필요가 있다. 위의 예시에서는 둘 사이에 4개의 vertex가 존재하기 때문에 GNN을 설계할 때 적어도 5개의 layer을 쌓아야 서로 정보를 주고 받을 수 있을 것이다. 물론, 더 적은 layer만으로도 가능할 수 있다. 중간 vertex 기준으로 2.5개의 layer만 있으면 노란 vertex와 초록 vertex를 상호 작용하도록 만들 수 있을지도 모른다. 하지만 이는 다른 vertex가 update된다는 기준인 것이고 실제로 노란 vertex와 초록 vertex 사이의 정보를 주고받으려면 5개의 layer는 있어야할 것이다.

Over-Smoothing Problem

Over-smoothing 문제는 GNN의 layer을 많이 쌓음으로써 발생하게 된다. Long-range 정보를 주고받기 위해서라도 GNN의 layer를 깊게 쌓는 것은 불가피하다. 하지만 그렇다고 너무 깊게 쌓다보면 GNN이나 MPNN에서는 over-smoothing 문제가 발생하게 되는 것이다. Over-smoothing 문제는 GNN layer을 여러번 지나고 나면 node representation이 서로 비슷해지는 현상을 말한다. 우리는 이를 node의 정보들이 smooth out 된다고 이야기하기도 한다. 이렇게되면 문제가 graph의 구조를 약화시키게 되면서 모두 비슷한 label이나 prediction을 하게되는 문제로 이어지게 될 것이다. 사람들은 이러한 현상을 GNN에서의 low-pass filter와 같은 동작을 한다고 이야기하기도 한다. 이러한 문제를 해결하기 위해서 사람들은 다양한 방법을 시도하곤 했다. Graph signal processing으로부터 다양한 filter를 디자인할수도 있으며, batch normalization과 같은 기법을 적용할수도 있을 것이다.

Over-Squashing Problem

Over-squasing 문제는 over-smoothing 문제보다 더 중요하고 최근들어 더욱 관심을 가지게 된 문제 중 하나이다. 위와 같이 GNN의 computational graph에서 각 message passing step에서 많은 양의 정보들이 모아지게 될 것이다. 그리고 이는 layer를 지날때마다 기하급수적으로 정보량이 많아지게 될 것이다. 위와 같이 layer를 3개 쌓고 degree가 전부 2라고 가정하기만해도 초록 vertex의 입장에서는 많은 양의 정보들을 받아들이게 된다. Degree가 2만 해도 2의 제곱으로 정보량이 많아지게 되는데, 실제로 graph에서는 이보다 많은 degree를 가지고 있는 상황이 대부분일 것이기에 상당히 많은 양의 정보를 하나의 vertex가 받아들이게 된다. GNN은 graph를 tree로서 computational graph를 만들고 long-range 정보를 받아들이는 효율적인 path를 찾아야 한다. 결국 우리는 노란 vertex에서 초록 vertex로 가는 가장 효율적인 path를 찾아서 정보를 전달하도록 만들어야 한다. 하지만 tree의 크기가 기하급수적으로 커지기 때문에 실제로 굉장히 어려운 문제에 해당한다.

간단하게 max pooling이나 sum pooling으로 문제를 해결해볼 수 있다고 생각할 수 있지만, 이러한 방법은 나머지 정보들을 상당히 버리는 형태가 되어 실질적인 해결이라고는 볼 수 없다. Comutational tree에서 max aggregation은 하나의 path를 선택하는 방법이기는 하지마 이것이 꼭 정답이 아닐 수도 있다. 단순히 이렇게 aggregation을 고정시키는 행동은 over-squashing 문제를 해결하지 못한다. Graph의 topology에 따라서 over-squashing 문제는 쉽게 해결하기 어려운 문제가 되었다. Over-squashing을 해결하는 방법들에 대해서 이번에 알아볼 것이고 대표적인 사례로 graph transformer나 graph rewiring의 방법들이 존재한다.

Understanding Over-Squashing 1

가장 먼저 ICLR 2022에 나왔던 "Understanding Over-Squashing and Bottlenecks on Graphs via Curvature"라는 논문을 통해서 어떻게 GNN의 over-squashing 문제를 해결했는지 알아보자. 저자들은 사람들이 GNN에 over-squashing 문제가 발생하고 있음을 알고 있었지만, 그동안 어떠한 이론적 해석도 없었다고 이야기한다. 이들은 sensitivity analysis를 통해서 over-squashing 현상을 정량화하고자 했다. 만약 다시 이전의 예시에서 초록 vertex가 어떠한 representation도 없다고 한다면 노란 vertex에 대해서 초록 vertex가 얼마나 sensitive한지를 이야기하고 싶었다. 이들은 또한 over-squashing 문제가 어떠한 model을 선택하는지와는 독립적으로 발생한다는 것을 증명하였으며, 이 현상은 graph 자체에 high negative curvature를 가지는 edge를 가질 때 발생한다고 주장했다. 여기서 high negative curvature라는 것은 수학적으로 다소 복잡한 개념으로, MPNN에서 정보의 bottleneck을 표현하는 방법이라고 생각하면 된다. 추가로 이들은 처음으로 rewiring method를 제안하였다. 만약 message passing 구조에서 bottleneck이 존재한다면 이는 graph의 edge에서 발생하는 것이기에 추가로 edge를 더하는 것은 bottleneck을 완화할 수 있을 것이라고 이야기했다.

Sensitivity Analysis

우선 저자들이 주장하는 sensitivity analysis를 통해서 over-squashing 현상이 해석된다는 부분을 볼 것이다. Output feature $h_v$와 input feature $h_u^0$ 사이의 interaction에 관해서 살펴본다고 해보자. 우리가 궁금한 것은 얼만큼 $h_v$가 $h_u^0$에 대해서 sensitve한지이다. Over-squashing 현상은 멀리 떨어진 vertex에 대해서 interaction을 학습할 수 없다는 것이다. 여기서 interaction이 위와 같이 수식으로 표현될 수 있으며, 위의 식은 2개의 vertex간 intercation을 수식으로 모델링할 수 있음을 말하고 있다. $r$번째 layer의 $h_v$와 input $h_u^0$간 interaction이 Jacobian norm으로 표현이 될 수 있는 것이다. 만약 이 norm 값이 크다는 것은 $h_v$가 $h_u$에 의해서 상당히 많은 영향을 받고 있다고 해석할 수 있다. 반대로 norm이 작아지면 그만큼 영향을 덜 받고 있음을 의미한다.

만약 combination function의 gradient와 message aggregation function의 gradient가 각각 $\alpha$와 $\beta$에 의해 bounded 되어 있다면, 이들간 sensitivity가 $\alpha,\beta$의 $r$ 제곱과 더불어 adjacency matrix의 $u,v$에 해당하는 element의 $r$제곱에 bounded된다는 주장을 하였다. 여기서 $A^r_{vu}$는 length $r$만큼의 $u$와 $v$ 사이의 walk를 의미하며, 이들이 강하게 연결되어 있다면 sensitivity는 클 것이고, 약하게 연결되어 있다면 sensitivity는 작아질 것이다.

Example: Binary Tree

이를 이해하기 위해서 간단하게 binary tree 예시로 알아보자. $A^r_{vu}$ 값이 위와 같이 $1/2\cdot3^{-(r-1)}$이고, 이는 $r$에 비례하여 값이 작아지는 것을 볼 수 있다. 각 leaf로부터 root까지의 path가 오로지 하나만 존재하는 것이 bianry tree이다. 이는 실제로 over-squashing 현상을 측정하는 유명한 실험 중 하나이다. 이 실험에서는 GNN을 사용해서 tree를 처리하면서 leaf로부터 root의 color를 검출하기를 원한다. Sensitivity analysis는 over-squashing 현상을 모니터링하기에 적합하면 지금은 표준적인 접근법 중 하나로 여겨진다. 이러한 분석은 tree에 적합하기에 이러한 식으로 정량화하는 것이 가능했다.

Edges with High Negative Curvature

이 논문에서 주요 아이디어는 high negative curvature를 가지는 edge들이 over-squashing 문제를 더 높은 확률로 유도한다는 점에서 비롯되었다. 디테일적인 부분까지 이해하려면 많은 내용과 시간이 동반되기에 간단하게 살펴보고 넘어가도록 할 것이다. Over-squashing이 특정 edge를 통해 발생한다는 것을 발견했다. 그리고 이러한 edge를 저자들은 Ricci curvature와 관련이 있다고 말한다. 이는 differential geometry와 관련된 개념으로, 만약 이 값이 -1보다 작은 아주 작은 음수인 경우에 high negative curvature를 가지는 edge에 해당하여 over-squashing을 발생시킨다고 이야기한다.

이러한 Ricci curvature는 어떠한 graph에서도 구할 수가 있으며, 대표적으로 cycle의 Ricci curvature 값을 구하면 0이 된다. Grid의 경우도 마찬가지로 0이지만, clique와 tree는 0이 아닌 값들로 구해질 수 있다. 여기서 주목할 부분은 clique로 이는 양의 범위로 curvature를 가지게 된다는 점이고, tree는 음의 범위로 curvature를 가진다는 점이다. Over-squashing 현상이 주로 tree에서 발생하는 것을 알 수 있는데, tree는 기하급수적으로 이웃이 늘어날 수 있다는 특징을 지니고 있다. 그래서 이러한 구조가 over-squashing 문제를 더욱 잘 유발하게 되는 것이다.

What is Curvature?

Ricci curvature는 사실 Riemannian manifold을 위한 개념인데, 이를 저자들은 graph로 근사하려는 시도하였다. 이 개념은 graph의 triangle이나 cycle의 개수를 세는 개념을 기반으로 한다. 그래서 이번에는 curvature가 무엇인지 간단하게 살펴보고 이를 differential geometry의 개념과 어떻게 관련이 있는지 알아볼 것이다.

위와 같은 종류들의 curvature를 이해하기 위해서 manifold 상에서 Ricci curvature가 무엇인지를 먼저 알아보고자 한다. 이러한 개념은 사실 Riemannian manifold에서 더 정의가 되며, 우리는 Riemannian manifold를 locally Euclidean point set으로 생각할 수 있다. 이웃한 point를 몇개 선택하게 되면 이로부터 만들어지는 Euclidean plane을 찾을 수가 있는데, 이는 ball에서 존재하는 point set과 locally similar하다는 것을 의미한다.

그래서 다시 우리는 Spherical, Euclidean, Hyperbolic manifold에 대해서 알아볼 것이고, 이러한 manifold는 어떤 object를 표현하기 위해서 적절히 사용될 수 있다. 사람들은 curvature를 각 manifold에서 정의했을 때, Spherical curvature는 양수, Euclidean curvature는 0, 그리고 Hyperbolic curvature는 음수를 보여주는 것을 발견했다.

Ricci Curvature Intuition

Ricci curvature를 직관적으로 이해해보자. 어떤 ball에서 하나의 point를 다른 point로 움직인다는 가정하에 geodescis로 불리는 shortest path가 생기게 되고, ball의 부피가 geodescis를 따라서 증가하거나 감소한다는 사실을 알 수가 있다. 어떤 point로부터 geodesics를 그린다고 했을 때 우리가 관심있는 것은 두 geodesics가 발산하지는 아니면 수렴하는지이다. 사람들은 2개의 geodescis로부터 도착한 두개의 point의 차이나 2차 미분값에 관심을 가졌다. Spehrical의 경우에는 2개의 geodesics를 어떻게 선택하더라도 서로 수렴하게 될 것이고, Hyperbolic의 경우에는 반대로 발산하게 된다. 즉, Spherical의 경우 curvature가 양수가 되는 것이고, Hyperbolic의 경우 반대로 음수가 되는 것이다. 이렇듯 geodesics의 수렴과 발산에 따라 curvature를 정의할 수 있다.

Surgical Analysis: Graph-Rewiring

그러면 이번에는 graph의 관점에서 geodesics를 생각해보자. Graph에서 geodesics는 edge를 따라 횡당하는 것과 같은 개념이다. Edge와 geodesics의 개념을 바꿔서 생각해보면 curvature를 이해할 수 있게 된다. 만약 graph 상에서 random walk를 한다고하면, 이는 되돌아오는 확률에 해당하게 될 것이다. 시작 vertex로부터 도착 vertex까지의 확률과 같으며, 이는 위에서 보았던 $A_{vu}$의 element와 관련이 있게 된다. 이러한 분석에 따르면, negatively curved edge는 over-squashing의 원인이 되는 bottleneck을 유도하게 된다. 저자들은 graph에서 잘못된 부분을 고치려는 시도를 하였고, negatively curved edge가 over-squashing을 유도하는 현상을 완화하기 위해서 edge를 추가해주었다. 위와 같이 negatively curved edge가 graph 상에서 존재하면 전반적인 curvature를 올려줄 수 있는 edge를 찾아서 추가했다. 그래서 전체적으로 graph에 우측과 같이 edge가 추가되면 curvature가 작아져 negatively curved edge의 영향력을 없애주게 된다.

Example: Graph Rewiring

예를 들어서 이들이 하고자 하는 것은 graph 상에서 전체적으로 curvature를 증가시킬 수 있는 새로운 edge를 sampling하는 것이다. 그렇게 해서 추가될 수 있는 edge들을 실제로 추가하여 graph의 curvature를 증가시켜주는 것이다.

또한 graph 상에 존재하는 기존의 edge들 중에서 curvature가 가장 큰 edge를 골라서 제거해주는 방법도 over-squashing 현상을 완화할 수 있다. Curvature가 가장 큰 edge는 graph의 clique로 존재할 가능성이 큰 edge이다. 결국 bottleneck을 유발할 수 있는 edge를 제거하여 over-squashing 현상을 개선하는 것도 해결책이 될 수 있는 것이다.

Understanding Over-Squashing 2

첫번째 살펴본 논문은 over-squashing 현상을 curvature를 통해서 정량화하여 분석하고 제안하는 알고리즘을 통해서 over-squashing 현상을 완화하는데에 contribution이 존재한다. 이후에 더욱 해석하기 용이한 두번째 논문 "On Over-Squashing in Message Passing Neural Network: The Impact of Width, Depth, and Topology"가 ICML 2023에 등장하였다. 첫번째 논문은 over-squashing을 분석하고 완화시키는 좋은 논문이었지만, 몇가지 질문들이 아직 남아있었다. Over-squashing을 완화시키는데 있어서 model의 width 등의 영향력이 어떠한지, over-squashing 현상이 충분히 깊은 model들에 의해서 완화될 수 있는지 등의 다양한 관점의 질문들이 아직 해결되지 못했었다. 이번에 살펴볼 논문을 통해서 첫번째 논문과 다른 관점에서 over-squashing 현상을 분석하고 이해해볼 것이며, 특히 message passing neural network의 구조를 주목해서 볼 필요가 있다.

Setting

이 논문은 결국 GNN의 width를 증가시켜주게 되면 over-squashing 현상이 완화될 수 있음을 주장했다. 이는 꽤 직관적이다. GNN의 width가 증가하면 결국 GNN이 저장할 수 있는 양도 함께 늘어나기 때문이다.

Impact of Width

앞서 over-squashing을 sensitivity를 통해서 정량화할 수 있음을 이야기했다. 이 논문에서도 마찬가지로 두 vertex간 영향력을 gradient norm을 이용해서 bound하였고, 이들의 크기를 통해서 서로의 영향력을 정량화하였다. 다만, 기존과 다른 부분은 GNN의 width의 영향력을 분석하기 위해서 network의 residual term이나 aggregation term의 coefficient로 sensitivity를 bound시킨 것을 볼 수 있다. 결국 MPNN과 같은 GNN의 width, depth, topology 정보를 기반으로 vertex 사이의 영향력을 정량화 시켰고, 이를 통해서 over-squashing 문제를 완화시키고자 시도했다.

저자들은 over-squashing이 일어날 수 있는 환경을 만들어서 실험을 통해서 증명했다. 더욱 어려운 환경 속에서 network의 hidden dimension을 늘려가면서 실험을 통해 문제를 풀고자했다. GNN의 width의 영향력을 보기 위한 이러한 실험 세팅은 꽤 흥미로운 부분이라고 할 수 있다.

What Does It Mean 'Long-Range'?

이들은 source vertex S와 target vertex T 사이의 interaction에 관심을 가졌고, ring, crossedring, cliquepath라는 이름으로 graph transfer task를 만들어 sensitivity의 우변의 값들을 각기 다르게 얻을 수 있었다.

그리고 source vertex와 target vertex 사이의 거리를 늘리게 되면 GNN의 성능이 저하되는 것은 실험적으로 증명했다.

Random Walk

저자들은 또한 random walk를 기반으로 하는 이론을 제시하였다. Message는 graph가 주어졌을 때 random walk를 수행하는 것이라고 이야기했다. 저자들은 node $v$에서 이웃한 node들로 일정한 확률 $1/d_v$로 이동하는 특정 random walk를 고려하였다. 그리고 over-squashing을 commute time에 관해서 분석하였다. Commute time은 node $v$에서부터 $u$로 갔다가 되돌아오는 random walk에서 예상되는 step의 수를 의미한다. 위의 예시에서는 별로 표기된 node에서 노란 node로 갔다가 다시 별 모양의 node로 돌아오는 step 수를 나타낼 것이다.

만약 tail vertex에서 출발하여 clique에 들어가게 된다면 빠져나오지 못할 가능성이 크다. 이러한 경우에는 commute time이 굉장히 커질 것이다. 그래서 graph connectivity를 개선하여 over-squashing을 완화하는 rewiring을 가이드해주기 위해서 effective resistance가 정의되었다.

Over-Squashing and Commute Time

만약 commute time이 굉장히 크다면 over-squashing 현상을 해결하기 어렵다. 그래서 저자들이 결국 말하고자 하는 것은 highly negative curvature edge라는 것이 수학적으로 어려운 개념이자 도구이기 때문에 vertex 쌍으로부터 effective resistance를 구해서 graph rewiring을 쉽게 시도할 수 있다는 것이다. 결론적으로 저자들은 over-squashing 현상에 있어서 GNN의 width, depth와 더불어 graph의 topology가 중요한 역할을 한다는 것을 발견하였으며, width의 영향력을 통해서 이 현상을 어느정도 완화할 수 있음을 실험적으로 보여주었다. Graph의 topology 정보의 경우 commute time이 이러한 현상을 발생시킬지와 관련한 중요한 정보라는 것을 발견하였으며, commute time에 비례하여 over-squashing 현상이 심해진다는 것을 이야기했다.

Weisfeiler-Lehman (WL) test는 원래 neural network와 관련된 개념이 아니라 graph theory에서 사용되는 개념이다. 이는 graph isomorphism에 관심을 두며, graph isomorphism 문제는 polynomial time에 해결되지 않는 NP intermediate라고 한다. Polynomial time 안에 해결되는 알고리즘을 우리는 모르며 또한 NP complete인지도 잘 모른다. WL test는 이 문제를 해결하기 위해서 사람들이 heuristic하게 만든 알고리즘 중 하나이다. Graph isomorphim 문제를 시험해보고 싶으며, 두 graph가 isomorphism을 만족하는지 결론을 내고자 한다. WL test가 polynomial time에 해당하기 때문에 graph isomorphism 문제를 풀지는 못할 것이다. 그러나 만약 두 graph가 WL test에 의해서 구분이 된다면, 두 graph가 non-isomorphic하다고 결론지을 수가 있다. WL test는 두 graph가 non-isomoprhic하여 다르다는 것을 보장을 해주는 수단이다. 한편, WL test가 두 graph를 구분하는데 실패할 수 있을 것이다. 이때는 어떠한 결론도 낼 수 없게 된다. 두 graph가 isomorphic한지 non-isomorphic한지 그거는 아무도 모른다는 것이다.

그렇다면 WL test는 어떻게 동작할까? 우리는 이를 수식적으로 설명할 수도 있지만 직관적으로 그림을 통해서 보는게 이해하기는 더 쉬울 것이다. GNN과 유사하도록 heuristic하게 동작하게 된다. WL test는 GNN처럼 message propagation을 하고 이를 여러 layer에서 반복하게 된다. 주어진 graph에 대해서 가장 첫번째 iteration을 거치면 모든 vertex가 동일하다고 판별될 것이다. 모든 node에 초기의 color를 할당하게 될 것이다. 위의 예시를 보면 2개의 graph에 대해서 모든 node에 보라색이 할당된 것을 볼 수 있다. 그리고 GNN과 비슷하게 각 layer마다 각 node에 할당된 color를 update하게 된다. 다시 위의 예시를 보면 좌측 graph는 각 node가 2개의 node와 연결되어 있기 때문에 모두 주황색을 할당받게 되었다. 반면 오른쪽 graph에서는 2개의 node와 연결되어 있는 node가 2개 있고, 나머지는 각각 3개와 1개가 연결되어 있다. 3개가 연결된 node는 파란색을, 1개가 연결된 node는 초록색을 할당받게 되었다. 이러한 과정이 두번째 iteration에서 수행되었다. 만약 두 graph가 isomorphic하다면 이러한 상황이 발생하지 않았을 것이다. 따라서 우리는 위의 예시에서 제시된 2개의 graph가 non-isomorphic하다는 결론을 낼 수 있다.

이번에는 다른 예시를 보도록 하자. 위의 2개의 graph에 대해서 WL test를 수행하게 되면 첫번째 iteration에서는 모두 보라색을 할당받지만, 두번째 iteration에서는 degree에 따라 주황색과 파란색을 할당받게 외었다. 그 결과 두 graph 모두 4개의 주황 vertex와 2개의 파란 vertex를 할당받은 것을 볼 수 있다. 첫번째 예시와 다르게 두번째 예시에서는 두번의 iteration 후에 두 graph가 isomorphic한 것을 확인할 수 있었다.

세번째 iteration을 해보면 1개의 주황 vertex와 1개의 파랑 vertex와 연결된 vertex에는 초록색을, 2개의 주황 vertex와 1개의 파란 vertex와 연결된 vertex에는 빨간색을 할당했다. 그 결과 두 graph가 동일한 결과를 만들었고, 따라서 두 graph가 isomorphic하다고 이야기할 수 있게 되었다.

WL test는 이웃 vertex의 color를 통해서 해당 vertex의 color를 update할 수 있다. 그리고 계속해서 반복하다보면 안정된 상태로 수렴하는 것을 확인할 수 있고, color의 distribution이 동일해지는 것도 확인할 수 있게 된다. 이러한 상황이 오게 되면 WL test를 통해서 두 graph를 구분하는 것에 실패했다고 볼 수 있다. WL test를 했음에도 두 graph가 동일해보이기 때문이다.

이제 이를 수식으로 정리해보자. 우선 2개의 graph $G_1,G_2$가 주어지면 모든 node에 동일한 color $c_1$를 가장 먼저 할당하게 된다. Color가 안정될 때까지 color를 update하는 과정이 반복되는데, 이때 위와 같이 강력한 hashing function HASH에 의해 vertex의 color는 update하게 된다. Vertex $v$의 color $c_v$가 현재 iteration $t$에서 update되기 위해서는 본인의 color $c_v$와 이전 단계의 neighbor vertex $w$의 color $c_w$를 이용해서 진행된다. 우리는 2개의 set function에 대해서 hash하려고 할 것이고, 따라서 우리는 2개의 set을 비교할 수 있다는 것을 가정할 수 있다. 만약 두 set이 서로 다르다고 한다면, 즉 distribution이 서로 다르다고 한다면, 두 graph가 non-isomorphic하다고 결론낼 수 있다. 만약 color들이 동일한 distribution으로 수렴하게 된다면, 우리는 어떠한 결론도 낼 수 없다.

Are All GNNs Made Equal?

이러한 WL test는 GNN과 매우 흡사하기 때문에 우리에게 있어 매우 유용하게 사용된다. WL test가 어떠한 상황에서는 GNN보다도 강력하게 동작할 수 있다. WL test가 강력한 HASH function을 평가한다고 가정하기 때문에 어떠한 set도 구분할 수 있게 된다. 예를 들어 2개의 주황색과 1개의 파란색을 빨간색으로 대응시키는 것은 아주 강력한 function이 된다. GNN이나 어떠한 MLP도 이러한 function을 학습할 수 없다. 그래서 HASH function은 상당한 힘을 지니고 있다.

MPNN이 WL test와 유사하게 동작할 수 있을까? WL test와 유사하게 동작한다는 것은 WL test는 구분할 수 있는 graph를 MPNN이 구분할 수 있는지를 의미한다. 그리고 사람들은 WL test가 graph convolution을 사용하는 MPNN에 의해 나타낼 수 없다는 것을 알아냈다. 여기서 우리는 실제로 WL test처럼 동작하고자 한다면 graph isomorphism network (GIN)이라고 불리는 모델이 필요하다는 것을 알게 되었다. GIN은 WL test를 동작시키기 위해서 설계된 모델이다. 이 방법의 아이디어는 color를 셀 수 있는 SUM aggregator가 필요하다는 것이다. GCN은 이웃들의 정보를 average화 시키기 때문이다. 또 다른 아이디어는 update function에 MLP를 사용해야 한다는 것이다. 왜냐하면 MLP가 보편적으로 강력하기 때문에 HASH function처럼 동작할 수 있다. 이렇게 SUM aggregator를 사용하고 linear operator를 MLP로 대체함으로써 GIN이 나타나게 되었다. 그리고 GIN이 WL test만큼 강력하다는 것을 이론적으로 보였으며, GCN이 WL test보다 덜 강력하다는 것을 이야기했다. 놀랍게도 GIN이 실제로 더 강력한 경우가 다수 존재했다.

Graph neural network(GNN)의 expressive power를 이야기하기 위해서 결론적으로 WL test를 알아야한다. 우리가 GNN1, GNN2, GNN3가 있다고 했을 때 어느 GNN이 더 좋은지 비교를 하고 싶으며, 이는 expressive power를 통해서 비교가 가능할 것이다. 이를 위해서 GNN의 expressive power를 정량화할 필요가 있고, WL test라는 특정 수단을 통해서 이것이 가능한 것이다. 그전에 graph가 무엇인지부터 알아보도록 하자. Graph $G$를 우리는 vertex set $V$와 edge set $E$, 그리고 node feature $X$로 표현할 수 있다.

Graph Representation

Graph의 representation은 adjacency matrix $A$와 feature matrix $X$를 가지고 나타낼 수 있다.

Graph Isomorphism

Graph에 대해서 알아보는데 있어서 흥미로운 개념 중 하나가 graph isomorphism이다. 이는 2개의 graph가 형식적으로 동일할 때 사용되는 표현이다. 비록 2개의 graph가 1-2-3과 1-3-2의 형태로 있을지라도 실제로 그 값은 다르지만 graph isomorphism 혹은 adjacency matrix를 보존하는 vertex간 bijection이 있다면 이 둘은 같다고 이야기할 수 있다.

위와 같이 adjacency preserving의 경우와 feature preserving의 경우를 볼 수 있다. 즉, vertex들의 순서 차이로 인해 다르게 표현되었지만 완전히 같은 구조를 가지고 있으면 graph isomorphism이라고 할 수 있다. 각 vertex가 연결된 구조를 살펴보면 2개의 graph가 정확히 동일하기 때문이다.

Graph Neural Networks (GNNs)

GNN은 graph에 대해서 parameterized된 function이라고 말할 수 있다. 만약 2개의 graph에 대해서 graph isomorphism이 있다면, function $f$의 output은 항상 동일해야 할 것이다. 하지만 반대로 2개의 graph가 isomorphic하지 않다면 $f$의 output도 isomorphic하지 않을 것이다. GNN은 이러한 개념으로 설명될 수 있다.

Message Passing Neural Networks (MPNNs)

Message passing neural network(MPNN)에서는 각 node마다 node feature가 있을 것이고, 이는 message function과 update function에 의해서 update될 것이다. 여기서 update function은 layer 사이에 non-linearity를 부여하는 역할을 한다.

Equivariance and Invariance

Equivariance와 invariance는 permutation matrix와 관련이 있다. Adjacency matrix 앞뒤로 permutation matrix를 곱할 수 있고, node feature matrix 앞에 permutation matrix를 곱할 수 있다. 이때 output이 permutation matrix에 의해 바뀐다면 equivariance이고, output이 그대로 나오게 된다며 invariance이다.

MPNNs and Isomorphic Graphs

MPNN과 isomorphic graph간 연관성은 흥미로운 부분이 있다. 만약 2개의 graph가 isomorphic하다면, MPNN은 isomorphic graph에 대해서 항상 동일한 representation을 할당하게 된다. 이는 input과 output이 동일하기 때문이다. 하지만, MPNN의 주된 문제점은 혹은 expressive measure를 측정하는데 있어서 만약 2개의 input graph에 대해서 isomorphism이 존재하지 않는다면, output이 여전히 다르다는 것을 보장할 수 없다는 것이다.

Representation of Non-Isomorphic Graphs

MPNN은 non-isomorphic graph에 대해 고유한 representation을 할당할까? 그 대답은 No이다. 여기에는 어떤 MPNN으로도 구별할 수 없는 non-isomorphic graph의 pair가 존재하기 때문이다. MPNN은 non-isomorphic graph들을 구분할 수 없기에 expressive power를 가지고 있지 않고, 이는 중요한 문제로 남아있다. 위의 그림에서 dash로 연결된 cluster들은 isomorphic graph들의 set이다. 3개의 isomorphic graph 중에서 위의 2개는 서로 다른 graph임에도 MPNN에 의해 동일한 representation으로 mapping된 것을 볼 수 있다.

An abstract Example

더 유명한 예시 중 하나로 MPNN에 의해 구별될 수 없는 isomorphic graph로 regular graph가 있다. 위의 regular graph 예시에서 좌측의 graph는 옆의 node 하나를 건너 뛰어서 edge를 생성하였지만 우측의 graph는 2개의 node를 건너 뛰어서 edge를 생성하였다. 즉, 좌측의 graph는 cycle이 3이고, 우측의 graph는 cycle이 4이다. 우리는 이러한 graph들을 circular skip link (CSL) graph라고 부르며, GNN이 쉽게 구분하지 못하는 대표적인 graph 중 하나이다. GNN의 첫번째 layer에서 모든 vertex를 구분할 수 없을 것이다. 두번째 layer에서는 4개의 vertex에 대한 message를 모을 것이다. 좌측의 graph와 마찬가지로 우측의 graph도 두번째 layer에서 4개의 vertex에 대한 정보를 얻게 된다. 이렇듯 양쪽 graph 모두로부터 local neighbor structure가 동일해서 GNN이 쉽게 구분하기 어려울 것이다. Message passing이 얼마나 복잡하거나 non-linearity가 어떻든 상관없이 두 graph의 output은 동일하게 나올 수 있다. 또한, MLP를 깊게 쌓더라도 두 graph를 구분하는 것은 쉽지 않을 것이다.

두번째 유명한 예시는 화학에서의 molecule graph로 decalin과 bicyclopentil이 있다. 두 graph 모두 degree가 2인 vertex가 8개 있고 degree가 3인 vertex가 2개 있다. 그리고 degree가 3인 vertex 중 2개는 degree가 2인 vertex들과 연결되어 있고, 나머지 1개는 degree가 3인 vertex와 연결되어 있다. 지역적인 관점에서 이 2가지 graph를 구분하는건 불가능할 것이다.

Universal Approximation

우리는 이를 universal approximation theorem과 관련해서 볼 수 있다. Universal approximation theorem은 MLP와 같은 neural network의 expressive power를 정량화할 수 있다. 만약 function이 존재한다면 만약 충분한 수의 neuron을 사용할 수 있다면, $\epsilon$ 값에 따라 function $f$를 근사하는 MLP를 만들 수 있다.

Function Approximation and Graph Discrimination

그러나 이전의 GNN의 결과는 universal approximation theorem과 같이 function을 근사했을 때 그 결과가 일치하지 않았다. 왜냐하면 2개의 graph가 isomorphic하지 않을 때 GNN을 얼마나 복잡하게 만드는 것과 상관없이 특정 constraint를 넘지 못하기 때문이다. 그리고 이는 참일 필요는 없다. 여기서 주된 문제점은 GNN이 MLP와는 다르다는 것이다. 여기서 우리가 해야하는 것은 expressive power를 측정하는 또 다른 축을 정의하는 것이다.

그래서 GNN의 expressive power를 어떻게 정량화하여 측정해야 하는 것일까? Graph를 input으로 가지는 GNN이 있을 때 function의 class는 non-isomorphic graph의 pair를 구별할 수 있는 경우에만 보편적으로 근사될 것이다. 만약 우리의 GNN이 보편적으로 근사시키고자 한다면 GNN이 non-isomorphic graph의 pair를 구별하는 추가적인 constraint를 통합시켜야 할 것이다.

MPNNs and Function Approximation

Permutation에 invariant한 function들의 class가 존재한다고 해보자. 이는 graph에 대해서 동작하는 operation이기 때문이 이러한 가정이 가능하다. 그러나 이 function들의 class가 neuron을 얼마나 많이 사용하는지와 상관없이 MPNN에 의해 근사되는 function들과 완전히 일치하지는 않는다. 위에서 $\mathcal{M}$은 function $\mathcal{F}$의 strict subset이다. 이것이 의미하는 것은 $\mathcal{M}$이 보편적으로 근사되지 않는다는 것이다.

Substructure-Counting is Not in $\mathcal{M}$

MPNN은 graph에서 유도되는 subgraph들을 셀 수 없다. Induced subgraph는 vertex 중 일부와 이들과 연결되는 edge들이 선택된 graph이다. 만약 graph $G$의 ring 개수에 graph $G$를 대응시키는 function이 있다면, 이 function들이 존재한다는 것을 증명할 수 있을 것이다.

Expressive Power of GNNs

기존의 MPNN은 $\mathcal{M}$ 안에 존재하는 class들을 가지고 있다. 하지만 GNN의 expressive power를 수치화할 수 있다면 expressive power의 위계를 세울 수 있을 것이다. 우리는 새로운 architecture를 설계함으로써 GNN이 표현할 수 있는 function의 class를 증가시킬 수 있다.

이러한 부분은 transformer에서 주로 사용되었는데, transformer가 각 vertex의 position을 파악할 수 없기 때문이다. Input embedding에 positional encoding 정보를 추가해줘서 transformer가 input vertex들의 position을 파악하도록 하는 것이다. 위의 식에서 $w$에 따라 서로 다른 frequency를 가지는 Fourier basis $sin(wi)$를 선택할 수 있는 것이다. 좌측 아래는 positional encoding이 어떻게 이루어지는지 visualization한 결과이다.

Laplacian eigenvector가 graph signal에서의 Fourier basis라는 사실로부터 graph transformer는 node $i$에 대해서 Laplacian positional encoding $v_i$를 사용해왔다. 이러한 방식이 graph data에 대해서 transformer를 일반화할 수 있도록 하였다.

하지만, 이렇게 Laplacian positional encoding을 사용했을 때 한가지 문제점이 존재한다. 바로 sign ambiguity problem이다. Eigenvector $v$와 $-v$에 대해서 동일한 eigenvalue가 존재하게 된다. 하지만 eigenvector의 부호가 다르기 때문에 두 종류의 representation이 존재하는 것이다. 두 vector에 따라 서로 다른 output으로 연결이 되는데, 비록 동일한 position을 가지고 있더라도 GNN의 output은 각 vector에 따라 다르게 정의되어야 한다. 하지만 우리가 원하는 것은 부호와 관련없이 동일한 output을 얻고싶은 것이다. 즉, eigenvector로부터 sign invariance를 가지기를 원한다.

Graph transformer가 나온 이후로 사람들은 sign invaraince를 가지는 network를 연구하기 시작했고, 2022년도에 sign invariant network가 등장하게 된 것이다. 단순히 하나의 eigenvector를 input으로 넣어주는 것이 아니라 서로 다른 부호를 가지는 2개의 eigenvector를 input으로 넣어주는 것이 이들의 아이디어였다. Permutation invariant한 방식으로 2개의 eigenvector를 network 내에서 처리하도록 하였다. 이렇게 간단한 아이디어로도 sign invariance를 만족시킬 수가 있었다.

Graph attention network (GAT)를 이해하기 위해서 우리는 GCN의 message-passing update로부터 시작하고자 한다. 결론부터 이야기하자면 GCN에서의 aggregation step을 attention pooling으로 대체한다면 GAT가 될 수 있다.

GAT의 aggregation step에서 $\alpha$가 attention이라 불리는 가중치이고, summation은 오로지 이웃 node들에 대해서만 이루어진다. $\alpha_{uv}$는 일종의 softmax function으로, query $Q$와 key $K$들에 적용되는 가중치이다. 여기서 softmax function은 attention score를 normalization하여 각각의 이웃들에 대한 일종의 확률 벡터로 만들어준다. 예를 들어 두 노드에 대해서 적용한다고 하면 0.5 / 0.5와 같이 확률로 해당 score를 표현하게 만드는 것이다. 만약 우리가 graph를 fully connected network로 되어있다고 가정한다면 GAT는 Graph Transformer가 될 것이다.

원래의 GAT 논문에서는 $e_{uv}$를 더 나은 parametrization 방법으로 강조하고 있다. 2개의 hidden feature를 concat해서 linear layer를 통과시켜서 softmax를 적용시키는 것을 attention layer를 normalization하는 것이라고 설명한다. 이렇게 concat하고 linear layer를 통해 구해진 $e_{uv}$는 matrix product를 사용하는 원래의 transformer과는 약간의 차이가 있지만, 그들은 실제로 이렇게 하는 방법이 더 나은 성능을 보였다고 설명했다.

Graph transformer는 matrix multiplication을 통해서 fully connected된 graph에서 모든 node간 attention score를 구할 수 있다. 하지만, GAT에서는 connection이 매우 sparse하기 때문에 각 edge에 대해서 attention score를 matrix multiplication 없이 구해야 한다. Dense한 가정이 있는 transformer와 sparse하게 adjacency matrix를 사용하는 GNN에서는 실제로 implementation에서는 차이가 있을 수 밖에 없다.

GAT를 사용하는데서 오는 이점이라고 한다면, 서로 다른 이웃한 node들로부터 다른 값이 오기 때문에 서로 다른 중요도를 $\alpha$라는 가중치로 특정할 수 있다는 것이다. 또 다른 이점은 GCN, Graphsage와 다르게 GAT를 구하는 과정에서 상대적으로 조금 느릴 수는 있지만, 그래도 operation의 complexity를 고려했을 때 효율적인 계산이 가능하다는 점이다.

Graph Transformers

GAT에 대해서 어느정도 알았다면, 이번에는 graph transformer에 대해서 알아보고자 한다.

New Design Landscape for Graph Transformers

Graph transformer는 기존의 transformer 구조와는 조금 다르지만 graph의 구조를 파악하기 위해서 살짝 변형되어 사용되었다. Graph transformer의 아이디어는 GNN을 생각해보았을 때 가장 먼저 이웃한 node를 파악하고 이 node들의 feature를 확인해야 한다. 그러면 이러한 이웃들로부터 정보들을 모아서 자신을 업데이트하는 구조로 message를 보내고 수정하게 된다. 하지만 graph transformer는 이러한 방법에서부터 다른 관점으로 접근하게 된다. 이웃들을 파악하는 것은 adjacency matrix를 파악하는 방법 중 하나일 뿐이며, graph transformer는 조금 다른 방법으로 이웃들을 파악하는데 초점을 두고 있다.

Processing Graphs with Transformers

그래서 기존의 message passing neural network의 관점이 아닌 transformer의 구조를 가지고 input으로 graph를 넣어 이를 파악하고자 모델을 설계하게 된다. Transformer는 graph를 설명할 수 있는 adjacency matrix로 부터 attention matrix를 만들어야 한다. 이렇게 만드는 방법이 graph transformer를 설계하는 간단한 방법 중 하나이다.

Components of a Transformer

만약 graph에 대한 transformer를 설계하고 싶다면, 가장 먼저 생각해야하는 것은 원래 transformer가 set value에 대해서 설계된 모델이라는 점이다. 그렇기 때문에 모든 node에 대해서 input의 position을 고려해야 한다. 물론 우리는 node feature로부터 시작하게 된다. Text data의 경우에는 원래라면 transformer 자체에서 단어들의 순서를 알 수가 없다. 하지만 이후에 설명하겠지만 transformer에서는 단어의 순서를 추가로 정보로 넣어주게 된다. 우리가 graph를 처리하고 파악하기 위해서 transformer는 graph를 input token으로 받아서 attention score를 구하고, 이를 바탕으로 원하는 output을 만들 것이다.

Final Key Piece: Token Ordering

기본적으로 token의 순서는 사실 transformer에서는 중요한 문제가 아니다. 만약 $x_1$과 $x_2$의 위치를 바꾸더라도 output $z_1$과 $z_2$가 permutation equivariance를 만족하기 때문에 마찬가지로 위치가 바뀌게 될 것이다. 그 이유는 우리는 aggregation step에서 permutation equivariant 혹은 invariant를 미리 node feature에 정의했기 때문이다. 이러한 성질을 transformer 구조는 그대로 따라갈 수 있다. token의 순서에 맞게 output의 순서가 달라지게 될 것이다.

이렇게 input의 위치에 따라 output의 순서가 달라지는 것은 transformer에서 중요한 성질이다. 하지만 단순히 input으로 text data나 node feature를 넣어주게 되면 넣어준 순서를 기반으로 이후에 정보를 모아주지만, 이 과정에서 문제가 생긴다. 순서가 중요하여 순서를 바꿔줌에 따라 바뀐 결과가 모아지게 되는데, 진짜 문제는 마지막에 수합하는 과정에서 sum pooling과 같은 연산을 하게 되면 결국 같은 output으로 결정이 될 것이다.

Positional Encoding

그래서 사람들이 text data에서 해왔던 것은 input에 positional encoding을 추가로 설정해주는 것이었다. Graph에서는 추가로 node마다 feature가 생긴다고 생각하면 된다. Positional encoding은 결국 text data에서 중요한 문장에서의 순서를 각 단어마다 부여하는 것이고, 이렇게 추가된 정보를 기반으로 transformer는 input의 순서를 기억하게 될 것이다.

그래서 결국 transformer를 설계할 때는 단순히 input feature를 모델에 넣어주는 것이 아니라 positional encoding을 이용해서 위치 정보를 추가해서 넣어줘야 한다. 이렇게 input의 tokenization을 시작으로 positional encoding을 거쳐 attention score를 구하게 되는 과정을 text data에서는 sequence로 자연스럽게 연결되는데, 그렇다면 graph에서는 정확히 어떻게 수행이 되는 것인지 알아보고자 한다.

Processing Graphs with Transformers (con't)

Graph data를 transformer가 처리하는 방식은 NLP와 다르지 않다. Graph transformer는 각 node feature를 각각의 token으로 하여 input으로 사용하면서 각각에 positional encoding을 추가해주게 된다. 이들을 이용해서 transformer는 self-attention을 통해서 attention score를 node별로 구할 수 있게 된다. 이러한 기본적인 구조는 다양하게 변형되어질 수는 있다.

결국, node feature를 text data에서 word와 같다고 생각하면 node feature를 input token으로 해석하게 된다. 하지만 단순히 node feature를 token으로 넣어주기만 한다면 text에서와 처럼 단어들의 위치 정보를 잃어버리는 큰 문제로 연결될 것이다.

그래서 graph를 transformer에 넣기 위해서 node별 feature를 넣어주는 것 외에도 edge feature인 adjacency 정보를 추가로 넣어주기도 한다. 이렇게 정보들을 모델에 넣어주는 방법들이 최근 많이 연구되어지고 있다.

How to Add Back Adjacency Information?

여기까지 정리해보면 우선 node feature를 transformer에 사용하기 위해서 positional encoding을 추가함으로써 input feature를 바꿔줘야 한다. 이렇게 여기에 adjacency information을 추가로 넣어주고 싶은 것이다. 만약에 graph를 sequential data와 같이 보자면 각 node마다 하나의 위치 정보를 부여받을 것이다. 이러한 방법이 sequential data에 positional encoding을 하는 간단한 방법일 것이며, 각 숫자가 결국 각 node의 위치가 되는 것이다.

여기까지 봤으면 한가지 이상한 점을 생각할 수 있을 것이다. Graph에서 어떻게 순서를 정의하는지가 문제가 될 것이다. 그러나 위치가 고정된 graph라면 node들은 고정된 순서가 있을 것이다. 그렇기 때문에 각 node마다 graph 안에서 어떻게 위치 정보를 가질 수 있는지 표현할 수 있는 방법을 생각해야 한다. 사실 positional encoding이라고 하면 결국 node를 embedding으로 바꿔주는 하나의 방법일 수는 있다. 결국 positional encoding이 되었다면 우리는 graph 안에서 각 node들의 위치를 알 수 있을 것이고, 이로부터 각 node들을 전부 구분할 수 있게 될 것이다. 이는 결국 node embedding 알고리즘으로 정의된다고 볼 수 있다. 사실 가장 흥미로운 정보를 담고 있는 순서대로 positional encoding을 해도 상관이 없다.

Laplacian Eigenvector Positional Encodings

사람들은 결국 graph에서 node의 위치 정보를 반영시키는 하나의 방법으로 Laplacian eigenvector positional encoding을 생각했었다. Laplacian matrix는 결국 하나의 graph를 설명할 수 있고, 해당 graph의 구조를 encoding할 수 있다. 그렇기 때문에 graph마다 존재하는 Laplacian matrix는 각각의 graph의 다른 점을 설명할 수 있게 된다.

만약 Laplacian matrix $L$로부터 eigen-decomposition을 통해서 eigenvector를 구하게 된다면, 이는 node embedding algorithm이 될 수가 있다. $L$로부터 얻은 eigenvector와 eigenvalue의 개수는 총 node의 개수와 동일할 것이고, 각각의 eigenvector는 모든 node에 대응되어 존재하게 된다. 여기서 $L$의 eigenvalue는 node embedding algorithm으로 사용되어 주어진 graph에 대해서 positional encoding이 가능해진다.

Adjacency matrix를 제곱하여 분해하여 얻은 eigenvector는 node feature로 사용될 수 있다. 마찬가지로 Laplacian eigenvector positional encoding도 마찬가지로 node feature를 얻는 방법으로 볼 수 있다. 그리고 우리는 이를 이용해서 graph transformer의 positional encoding으로 사용할 수 있다. 흥미로운 부분은 각 eigenvector에 대응되는 eigenvalue에 따라서 graph 구조를 파악할 수 있다는 것이다. 여기서 다룰 내용은 아니지만 간단하게 이야기하면 eigenvalue가 작은 경우에는 graph의 local한 정보에 더 초점을 맞추고, 반대로 eigenvalue가 큰 경우에는 graph의 global한 정보에 더 초점을 맞출 수 있다.

우리는 총 $k$개의 eigenvector가 있다면, 이들을 전부 stacking하여 하나의 matrix를 구성하고 동일한 위치에 있는 값들로부터 새로운 벡터를 형성하여 각 node별 feature로 만들 수 있다. 이렇게 eigenvector를 이용한 positional encoding 방법이 처음으로 graph transformer를 변형시킨 사례가 되었다.

Shortest Path Encoding

이외에도 하나의 사례를 더 살펴보면 shortest path encoding이 있다. 이 방법의 아이디어는 모든 transformer가 값들을 mixing하는데서 시작하게 된다. 이 과정에는 node-wise feature transformation이 동반되는데, 이 방법이 하고자하는 것은 attention matrix를 adjacency matrix를 기반으로 해서 만들고자 하는 것이다. $Q$와 $K$의 matrix multiplication 과정에서 graph의 구조를 통합하고자 했을 떄, 이들의 multiplication 결과와 graph의 구조 정보를 담고 있는 특정 matrix를 더해서 attention matrix를 구해주는 것이다. 가령, 각 node 사이의 shortest path 결과를 담고 있는 matrix를 더할 수 있을 것이다. 이렇게 graph의 구조 정보를 통합하여 attention matrix를 설계하는 것이 좋은 성능으로 연결된다는 것을 사람들을 발견했다.

우리는 time signal에 대한 shift operator로 여겨지는 adjacency matrix에 대해서 알아보았고, degree matrix에서 adjaency matrix를 빼서 만들 수 있는 Laplacian matirx $L$에 대해서 살펴보았다. 그리고 Fourier basis가 $A$ 혹은 $L$의 eigenvector로 유도가 되는 것을 알 수 있었으며, 2가지 경우의 eigenvector가 모두 유효한 signal processing을 정의할 수 있었다. 사람들은 $A$의 eigenvector가 Fourier basis element로 사용해야 하며, $L$의 eigenvector는 graph signal의 Fourier basis로 사용해야한다고 말하며 구분해야 한다고 하지만 아니라고 할 수도 있다. 사실 우리는 특정 time signal line graph에서는 두가지 정의가 같을 수 있지만, 일반적인 graph에서는 두가지 정의가 다름을 입증할 수 있다. 사람들은 $A$의 eigenvector를 graph signal에서 Fourier basis로 사용하기도 하며, 그렇지 않은 경우에는 $L$의 eigenvector를 graph signal에서 Fourier basis로 사용한다. 우리가 하고자 하는 것은 결국 eigen decomposition을 통해서 eigenvector를 얻고, 이로부터 basis를 바꾸고자 하며, vector $f$는 coefficient와 eigenvector들의 곱들의 summation과 같도록 표현하고자 한다. 이는 이후에 설명할 Fourier transformation과 관련이 있다.

Smoothness

마지막으로 Graph Laplacian은 특정 function $f$의 smoothness라는 것을 측정하는 도구로서 사용이 될 수 있다. 만약 우리가 $L$에 $f$를 양옆으로 곱하게 된다면, 위와같이 $f(i)-f(j)$의 제곱의 summation으로 표현이 되고, 이로부터 우리가 smoothness를 측정할 수 있게 될 것이다. 이는 이웃한 vertex들과의 차이를 측정할 수 있어서, 이로부터 smoothness를 구하게 되는 것이다. 이 식이 이상해보일 수 있지만, 여기서 $W_{ij}$는 0 아니면 1이 된다. 1이라는 것은 $i$와 $j$ 사이에 edge가 존재한다는 것이다.

또 다른 흥미로운 부분은 Laplacian matrix의 eigenvector를 통해서 smoothness를 구할 수 있다. 우리는 위와 같이 $f^TLf$에서 $\lambda f^Tf$를 얻게 된다. 결국 우리는 smoothness를 구하기 위해서 $f^TLf$를 구했지만, 여기서 최종적으로 frequency term $\lambda$와 관련된 식을 유도하게 된다. 그리고 이 $\lambda$는 eigenvector의 norm인 $|f|$와 곱한 형태가 된다. 우리는 function이 심하게 파동을 일으키면 smooth하지 않음을 알고있다. 여기서 얻을 수 있는 relationship으로는 $\lambda$가 커지면 커질수록 $f$가 더 심하게 요동치게 된다. 가장 작은 frequency term으로 $\lambda$가 가장 작은 경우에는 대응되는 eigenvector가 굉장히 smooth하지만, 그 값이 커지면 커직수록 대응되는 eigenvector가 심하게 파동을 보여주게 된다.

정리해보면 우리는 $f$를 $L$의 2번 곱해서 node feature간 difference를 제곱한 값을 얻게 되었다. 이 결과가 작으면 작을수록 이웃한 node와의 유사도가 올라가는 의미를 갖게 되기 때문에 연결된 node까리 유사하게 만들고 싶으면 $f^TLf$를 최소로 만드는 $f$를 구하면 될 것이다. 여기서 $f^TLf$이 결과적으로는 $f$의 smoothness 혹은 frequency를 의미하게 되는데, 이 값이 커지게 되면 signal간 difference가 커져 결국 high frequency를 지니고 있다고 해석할 수 있고, 반대로 difference가 작아지면 low frequency를 지니고 있다고 볼 수 있다. 우리는 low frequency의 영역이 중요함을 알기에 $f^TLf$를 최소로 하는 $f$를 구하고자 하며, 결과적으로 최적의 $f$를 구해보면 $L$의 eigenspace에 속하는 eigenvector가 여기에 해당하게 될 것이다. 결과적으로 eigenvalue $\lambda$는 이에 대응하는 eigenvector $f$의 smoothness를 의미하게 되고, 가장 작은 $\lambda$에 대응하는 eigenvector가 가장 smooth한 vector가 될 것이다. 우리는 결국 smoothness를 eigenvalue로 측정할 수 있는 것까지 알게 되었다.

Fourier Transformation

Fourier transform은 어떠한 function $f$를 Fourier series로 분해하기 위한 coefficient들을 구하는 과정을 일컫는다. 우리는 $f$로부터 coefficient와 이에 대응되는 basis function 혹은 eigen function을 구해 분해하고자 하는 것이다. 한편, Fourier transformation이 있다면 역과정인 inverse Fourier transformation도 존재한다. Fourier transformation이 기존의 function을 coefficient의 set 혹은 새로운 basis에 관한 새로운 coordinate로 분해하는 과정이라면, inverse Fourier transformation은 Fourier series element와 곱해지는 coefficient 분해했던 Fourier transformation을 역으로 수행하여 다시 원래의 function을 구성하는 과정이다. 요약하면 Fourier transformation은 signal에서 coefficient로, inverse Fourier transformation은 coefficient에서 signal로 전환하게 된다.

우리가 Fourier transformation과 inverse 과정을 matrix의 관점에서 이야기하게 되면 vector $f$를 eigen vector를 모아놓은 matrix $U$를 basis로하여 분해할 수 있다. Basis matrix를 바꿔주도록 matrix multiplication을 통해서 수행할 수 있다는 것이다. Fourier coefficient들을 모아놓은 $\hat f$를 다시 $U$와 곱해주면 원래의 signal $f$를 만들 수 있다. $f$에 $U$를 곱해주면 Fourier transformation이 되고, $\hat f$에 $U^T$를 곱해주면 inverse Fourier transformation이 되는 것이다.

Continuous한 경우에서 Fourier transformation와 graph Fourier transformation은 흥미로운 연관성이 존재한다. Continuous한 경우에는 Laplace operator가 존재하는 반면에 graph Fourier transformation에는 graph Laplacian $L$이 존재한다. Eigenfunction의 경우 $e^{j\omega x}$로 정의가 되며, 여기서 $\omega$는 $2\pi nk$로 정의될 수 있고, eigenvector의 경우에는 graph Laplacian matrix를 eigen decomposition을 통해서 얻을 수가 있다. Eigenvector의 경우 graph에 따라서 다르게 존재할 것이다. 아무래도 graph가 다르면 서로 다른 graph Laplacian이 존재하기 마련이다. 원래의 Fourier transformation이 좌측과 같이 구해진다면, graph Fourier transformation은 signal에 eigenvector를 곱해주면 된다.

간단한 예시를 보도록 하자. 위와 같은 graph가 주어졌다고 가정했을 때, orthogonal Laplacian eigenvector를 위와 같이 구성해서 discrete Fourier transform matrix를 만들 수 있을 것이다.

Non-cyclic line graph에 대해서도 eigenvector를 위와 같이 구성하여 matrix $U$를 만들 수 있을 것이고, 우리는 이를 discrete cosine transform matrix라고 한다.

지금까지 우리는 graph Fourier transformation에 대해서 알아보았다. 이는 matrix $U$를 signal $x$에 곱해줌으로써 수행할 수 있고, $U$는 graph Laplacian을 eigen decomposition을 하여 얻어진 eigenvector들로 구성할 수 있다.

Filtering

Fourier transformation까지 알아봤으면 이제는 이를 기반으로 filtering을 할 수가 있다. Filtering의 경우 signal processing에서 가장 기본이 되는 개념 중 하나이다. Filtering operation의 주된 목적은 특정 frequency를 찾아내는 것이다. Filtering의 대표적인 예시 중 하나는 signal을 smooth하게 만드는 것이다. 왜냐하면 signal을 smooth하게 한다는 것은 높은 frequency component를 제거하는 것과 동일하기 때문이다. Signal $f$에 Fourier transformation을 하게 되면 coefficient set을 얻게 된다. Filtering을 하는 것은 frequency domain에서 특정 filter를 곱해주는 것과 같다. $\hat h(k)$에서 $k$가 높은 경우에는 이 값을 0으로 만들면 high frequency component를 없앨 수 있을 것이다. 반대로 $k$가 낮은 경우에는 이 값을 1로 설정해서 low frequency component들을 살림으로써 결국에는 signal을 smooth하게 만들 수가 있다. 이를 matrix 형태로 구해보면 Fourier coefficient $\hat f$에 filter $\hat h$를 element-wise product를 통해서 구해줄 수 있게 된다. 여기서 $\hat h$는 diagonal matrix로 생각하고 matrix multiplication을 $\hat f$와 하면 된다.

Convolution and Convolution Theorem

우리는 이러한 filtering 과정을 또한 convolution으로 해석할 수 있다. Convolution이 정확히 어떠한 수식으로 구성되는지 보다는 여기서는 convolution이 frequency space 상에서 element-wise product로 수행되는 점이 더 중요하다. 그리고 우리는 convolution을 matrix의 형태로 표현하기를 원한다.

가장 먼저 function $f$를 Fourier transformation을 통해서 frequency space로 보낸다. 이는 eigenvector를 모아놓은 matrix $U^T$를 곱하면 된다. 그리고 element-wise product를 통해서 filter를 적용시킬 수 있다. 그리고 마지막으로 inverse Fourier transformation을 수행해준다. 이는 다시 matrix $U$를 곱해주면 된다.

Convolution theorem에서 convolution은 frequency space 상에서 element-wise product에 의해 유도된다. Convolution theorem은 두 signal 사이의 convolution을 이야기하는데, 이는 실제로 frequency space에서 element-wise product에 의해 수행이 된 다음에 inverse Fourier trnasformation을 적용하여 원래의 space로 돌아오게 된다. 이러한 과정은 matrix $U^T$를 곱하고 frequency-wise multiplication을 한 후에 inverse 변환을 위해 다시 $U$를 곱하는 과정과 동일하다.

이제 우리는 이로부터 graph convolution을 정의할 수 있게 된다. Graph convolution은 matrix $C$를 곱해주면 되는데, 여기서 $C$는 $U\text{Diag}(\hat h)U^T$로 parametrization 된 것을 볼 수 있다. 그리고 이 $C$는 graph Laplacian $L$과 eigenvector를 공유하게 된다.

Deriving 1D Convolution from First Principles

지금부터 adjacency matrix $A$로부터 eigenvector $U$를 사용하여 정의되는 alternative convolution에 대해서 알아보고자 한다. 지금까지 Laplacian matrix $L$을 가지고 graph convolution을 정의했다면, 이번에는 $A$를 가지고 정의할 것이다. Convolution을 matrix로 정의하여 $Cf$ 형태는 동일하지만 $C$를 구성하는 $U$는 $A$를 eigen decomposition을 통해서 얻어진 eigenvector들로 구성이 되어져 있다. 1D time series graph의 경우에는 $A$와 $L$의 eigenvector가 동일할 것이다. 이는 여기서는 중요한 내용은 아니며, 흥미로운 점은 $C$와 $A$가 invertible하다는 것이다. 그래서 $CA$와 $AC$가 동일한 결과를 만들어낼 수 있다. 이전에 1D signal에 관한 matrix multiplication은 time-shift operator와 같다고 했다. 그래서 1D convolution의 경우 shift-equivariance 성질을 만족하게 된다. Convolution을 먼저하고 signal을 shifting하는 것과 signal을 shifting하고 convolution을 수행하는 것이 결과적으로는 동일한 행위인 것이다. 이러한 점으로부터 중요하고 흥미로운 성질이 생기고, 이는 convolution이라는 것이 shift-equivariant한 operator이기 때문이다. 실제로 어떠한 shift-equivariant한 matrix multiplication도 convolution이 될 수 있다.

Time-shift operator와 순서를 바꿀 수 있는 matrix를 우리는 circulant matrix라고 하며, 이는 위와같이 각 column에서 순서가 하나씩 이동되는 row들의 집합이다. 이는 matrix multiplication과 같은 linear operator가 shift-equivariant하다면, 이는 곧 convolution임을 의미하게 된다.

ChebNet and GCN

이제 마지막으로 GCN이라 불리는 graph convolution network가 어떻게 정의되었는지에 대해서 알아보고자 한다. 실제로 GCN 논문을 보게되면 이번에 알아본 graph convolution의 정의를 기반으로 설명되어져 있다. 여기서 graph convolution은 단지 adjacency matrix를 곱하는 것이 전부가 아니라, frequency filtering process를 수행하는 것과 같다고 한다.

ChebNet과 GCN은 2016년도에 동시에 등장했으며, 서로를 언급하지 않은 상태로 논문이 작성되었다. 근본적으로 이들은 동일한 방법론을 제시하였다. GCN은 우리가 convolution matrix를 $U\text{diag}(\theta)U^T$로 어떠한 matrix로도 정의할 수 있기 때문에 graph convolution 과정을 diagonal matrix의 $\theta$로 parameterization할 수 있다고 이야기한다. 각 diagonal에 parameter를 할당하여 graph convolution을 하면 된다고 하고, 이는 각 filter를 조절하는 것과 동일하게 볼 수 있다. $\theta_1$은 $\lambda_1$에 해당하는 signal을 조절하는 식이다.

Signal이 있을 때 $U$를 곱하고 다시 filter를 곱하고 다시 $U$를 곱하는 이러한 과정이 비효율적으로 여겨진다. 무엇보다도 adjacency matrix를 eigen decomposition을 하는 과정부터 사실 cost가 많이 든다고 볼 수 있다. 그리고 parameter의 숫자가 vertex의 수의 비례해서 증가하는 부분도 문제가 될 수 있으며, 그래프가 변하게 되면 우리는 새로운 parameter를 할당해야하는 번거로움도 존재한다. 즉, 모든 graph에 일반적으로 접근할 수 없다는 것이다. 어찌됐든 graph가 커지기만 하더라도 이러한 식의 parameterization은 비효율적이게 된다.

ChebNet은 결국 이러한 비효율적인 과정을 Chebyshev polynomial을 사용해서 근사할 수 있음을 보여주었다. 이는 polynomial을 여러번 더하게 되면 임의의 function으로 근사시킬 수 있게 된다. 그리고 이는 polynomial이 여러번 더해지면서 coefficient가 $\theta_k$로 parameterization 되었음을 위의 식을 통해서 볼 수 있다. GCN은 first-order Chebyshev polynomial만으로도 동일하게 동작할 수 있음을 설명하였다. 그리고 이를 수식으로 정리해보면 그저 adjacency matrix를 곱하는 것과 동일함을 알 수 있다. 즉, first-order Chebyshev polynomial을 사용하는 것이 adjacency matrix를 곱하는 것과 동일하다는 것이다. GCN이 이름에서 보았듯이 graph convolution network일지라도 graph convolution을 first-order Chebyshev polynomial로 근사한 것임을 알아두자.

이번에는 GNN을 signal processing의 관점에서 다시 끌어내보려고 한다. 새로운 GNN 구조를 만든다고 했을 때 사람들은 CNN에서 이미지 상에 잘 동작했던 것을 어떻게 하면 GNN에 가져다가 사용할 수 있을지를 주로 고민하곤 한다. 그래서 사람들은 항상 GNN 구조를 generalization하는 것에 관심이 많으며 이는 signal processing 분야와 관련해서 중요한 부분이다. 실제로는 signal processing 자체는 굉장히 오래된 분야이지만, 아직 graph signal processing 분야는 많이 확립되었다고 보기 어렵다.

Signal processing은 전기전자 분야에서 굉장히 널리 알려진 개념 중 하나이다. 대표적인 예시로 time singal을 생각해볼 수 있으며, time signal은 time $t$에 정의되는 function이다. 가령 time series data에서는 기본적으로 time signal이 고려되었다. 또한 이미지도 signal data로 볼 수 있다. 대신 Euclidean coordinate에서 $x$와 $y$에 의해 정의되는 2d signal인 셈이다. Image signal processing의 대표적인 사례로는 blurring된 image를 떠올릴 수 있을 것이다. 여기서 blur를 지워 원래의 image를 복원하는 것도 signal processing의 관점에서 해결할 수 있는 문제이다. 결국 CNN이나 이미지를 다루는 neural network도 signal을 processing하기 위해서 만드는 것과 다름이 없다. 우리가 data를 vector로 표현하지만, 이러한 vector에는 index로 mapping 되는 특정 위치가 존재하고 이로부터 signal로 표현이 되기 때문에 결국 어떠한 data도 signal로 표현이 가능하다. 대표적으로 input으로 image의 $x$와 $y$의 coordinate를 넣어주면 이에 대응되는 RGB color를 output으로 내는 function을 구할 수 있을 것이다.

Signal processing에서 중심이 되는 operation은 바로 convolution이다. 우리는 이번에 얼마나 convolution이 흥미로운지 알아볼 것이고, 이 개념을 확장해서 graph convolution까지 어떻게 연결이 되는지 알아보고자 한다. CNN이라는 개념이 image data에 대해서 존재하기에 이를 확장해서 graph CNN, 즉 graph convolution에 대해서 알아볼 것이다. 결국 graph convolution을 이해하기 위해서는 graph signal processing (GSP) 분야를 확실히 하고 가야한다.

The Big Picture

딱 한가지만 기억해야 한다면 결국 우리는 graph domain에 convolution을 generalization할 수 있다는 것이다. 이를 위해서 간단한 directed line graph를 이용해서 설명하고자 한다. Time signal은 1차원에서 정의되는 1D signal인데, 이를 graph domain에서 directe line graph에 적용해보면 vertex마다 연결되는 방향성이 존재하는 edge가 있기에 이를 따라서 vertex를 discrete time으로 보고 같은 1D signal로 해석해볼 수 있게 된다. Time $n$에 따른 discrete-time signal $f(n)$이 $v$개의 vertex를 가지는 graph signal $f(v)$로 확장될 수 있다는 것이다.

우리는 line graph에서 GSP를 정의할 것이고, line graph에서의 GSP는 결국 time signal에서의 signal processing이 될 것이다. 그래서 우리는 GSP와 signal processing 사이에서의 connection을 만들고자 하며, 이를 위해 먼저 frequency와 같은 signal processing에서 이미 알고있는 용어들을 다시 정의하고 시작할 필요가 있다. GSP에서 조금 더 직관적으로 이해하기 위해서 이러한 과정들이 필요할 것이다.

우리는 signal processing에서 여러 근간이 되는 개념들을 알아볼 것이고, 비록 signal processing 자체가 engineering의 영역이라고는 할지라도 개념 자체는 꽤 직관적이고 수학적으로도 많이 알려져있기 때문에 그렇게 어렵지는 않다. Shift, frequency, lapalcian operator, convolution, filtering, fourier transformation 등 여러 개념들이 등장하기에 이를 하나씩 살펴볼 것이고, signal processing에서의 개념으로부터 시작해서 GSP까지 연결시켜볼 것이다.

Time Signal as Graph Signal

Time signal의 특징 중 하나는 이것이 여러개의 function으로 분해될 수 있다는 것이다. 즉, time signal이 여러 작은 periodic signal로 분해되어 summation의 형태로 표현될 수 있다. 이로부터 signal processing이 분해된 function $f(1),f(2),\dots,f(T)$들을 다루고, 여기서 각 function $f$는 constant frequency로서 정의 될 수 있다. 예를 들어 $f(1)$은 느리게 흔들리는 frequency이고 $f(2)$는 이보다 빠르게 흔들리는 frequency로 정의할 수 있다는 것이다. 우리는 결국 전체 signal로부터 infitine하거나 finite한 여러 signal들로 분해할 수 있다.

이러한 시간에 대한 function인 time signal이 graph signal로서 표현될 수 있게 된다. 이를 이해하기 위해서 먼저 discrete signal processing에서부터 시작해서 시간이 discrete하다는 가정을 할 것이다. 물론 이러한 discrete한 시간을 합치면 전체 시간이 될 것이다. 그리고 time signal이 period $T$에 따른 periodic function이라는 또 하나의 가정을 해볼 것이다. 그러면 우리는 time signal을 시간으로부터 어떠한 output으로 매핑되는 vector ${\bf f}$로 표현할 수 있을 것이다. 사실 time signal이 graph signal로 정의가 되는 것은 굉장히 흥미로운 부분이다. Time이라는 개념은 어떠한 integer는 아니지만 integer들이 set을 이루고 방향성을 가지게 되면 성립이 되는 구조이다.

그렇다면 시간 사이에 sequential relationship과 같은 이러한 개념을 어떻게 정의하면 될까? 우리는 adjacency matrix $A$와 같은 linear operator를 이용해서 정의할 수 있다. 여기서 $A$를 우리는 shift operator라고도 부를 수 있다. 이는 시간의 흐름에 따라 어떻게 signal이 행동하는지에 대해서 설명할 수 있다. 예를 들어, periodic function $f(T)$와 $f(T+1)$이라는 2개의 함수가 있다고 했을 때, 뒤의 함수는 linear operator $A$를 앞의 function에 적용시켜서 만들 수가 있다. $A$를 1과 0으로 잘 구성하면 $f$의 원소 순서를 바꾸는 shift 연산이 적용되는 효과가 발생해서 결국 같아지게 만들 수 있다는 것이다. 우리는 이렇게 $f$라는 function을 graph signal로도 볼 수 있으며, time에 mapping된 function이 아닌 vertex에 mapping된 function으로 볼 수 있고, $f(1)$부터 $f(T)$까지 shift 연산이 adjacency matrix를 곱하는 것과 일관성이 있게 된다. 따라서 시간으로부터 real number로 mapping되는 time signal이 같은 맥락으로 vertex에서 real number로 mapping되는 graph signal로 정의될 수 있다는 것이 중요하다. 그리고 $f(T)$와 $f(T+1)$ 사이의 progression이나 relationship은 matrix multiplication으로 표현될 수 있다. 여기서 matrix는 directed graph에서의 adjacency matrix가 될 것이다.

Frequency

우리는 지금까지 time signal이 무엇인지와 time signal의 progression을 정의 했다. 2개의 function 사이의 relationship을 예로 들어 progression을 설명했었다. 지금부터는 signal의 frequency가 무엇인지를 알아보고자 한다. Signal processing에서는 만약 특정 signal이 periodic하다면, 우리는 frequency를 period의 inverse로 정의할 수 있다. 하지만 signal이 불규칙한 모양을 가지고 있을 때도 많을 것이다. 이러한 경우에는 전체 signal의 frequency를 정의하기 어려워진다. 그래서 signal의 파동으로 frequency를 정의하고 싶다면, 우리는 signal이 특정한 형태를 가진다고 가정할 필요가 생긴다.

우리는 frequency를 정의하기 위해서 distcrete Fourier series가 무엇인지 알아야하며, discrete Fourier series element 혹은 discrete Fourier bases에 대해서 알아야 한다. Discrete Fourier series element는 $f(n)=e^{i\frac{2\pi kn}{N}}$으로 정의할 수 있다. 그리고 Euler's formula에 의해서 exponential function을 cosine function으로 생각할 수 있다. 이렇게 정의된 element는 단지 규칙적으로 파동을 형성하는 성질을 지니고 있다.

만약 이렇게 특별한 형태를 가정하게 되면 우리는 $f(n)$과 frequency사이에 흥미로운 관계를 찾을 수 있다. Cosine의 period는 $2\pi$이기 때문에 위와 같이 $f(n)$을 가정하게 된다면 $kn$을 $N$으로 나누는 최소 $n$이 해당 function의 period가 된다. 그러면 우리는 여기서 $k$를 frequency로 부를 수 있다. 왜냐하면 $cos(kx)$를 생각해보면 $k$가 증가함에 따라 훨씬 많이 파동을 일으킬 것이기 때문이다. 따라서 discrete time signal에서 $k$를 frequency으로 볼 수 있게 되었고, 적어도 $k$ 자체가 frequency와 관련이 있는 부분이 될 것이다.

한가지 더 흥미로운 점은 우리가 만약 위와 같이 signal을 특별한 형태로 가정하게 된다면 $n$을 time $T$라고 했을 때 time의 progression을 $Af$로 볼 수 있게 된다. 또다른 relationship으로 우리가 특수한 Fourier series element를 가정하게 된다면, 우리는 $f(n+1)$을 $f(n)$에 어떠한 constant를 곱한 형태로 표현할 수 있게 된다. 여기서 constant는 $k$값에 의존하게 될 것이다. 이러한 Fourier series element에 따라서, time의 progression은 어떠한 값들의 곱의 형태로 표현될 수 있으며, 여기서 어떠한 값들은 frequency $k$에 따라 달라지게 된다. 만약 $k$가 커진다면 time progression에 따라 function이 더 빠르게 변할 것이다.

우리는 이러한 relationship에 대해서 알아보았는데, 이와 더불어서 어떠한 constant와 vector $f$를 곱한 결과가 time의 progression을 나타내는 shift operator 혹은 adjacency matrix $A$와 $f$를 곱한 결과와 같다는 관계도 얻을 수 있다. 여기서 흥미로운 점은 $k$에 따라 달라지는 frequency term $e^{i\frac{2\pi k}{N}}$이 adjacency matrix $A$의 eigenvalue라는 것이다. 그리고 Fourier series element $e^{i\frac{2\pi kn}{N}}$은 shift matrix $A$의 eigenvector에 해당하게 된다. 이는 graph의 관점에서 Fourier transform을 생각했을때 흥미로운 부분이다. 여기서 eigenvector와 eigenvalue로 연결되는 점이 의미하는 것은 무엇일까? $A$의 eigenvector는 어떠한 matrix를 생각해보면 우리가 $A$를 여기에 적용했을 때 방향이 변하지 않는 vector를 의미한다. $A$를 $f$에 적용했을 때 identity가 변하지 않아야 eigenvector인 것이다. $A$는 shift operator으로 time을 shifting하거나 vertex를 permuting하게 만들 것이다. 따라서 eigenvector의 개념은 equivariance의 개념과 관련이 있는 것이다. 다시 정리해보면 $A$를 곱하는 것은 time을 shifting 하겠다는 것이고, Fourier series element에 대해서 frequency term은 특정 signal $f$의 eigenvalue로 볼 수 있다.

Laplace Operator

우리는 Fourier series element $e^{i\frac{2\pi k}{N}}$를 특정 function으로 선택했었다. 그렇다면 이러한 fucntion이 왜 특별할까? 우리는 다른 basis 혹은 다른 element로부터 frequency를 정의할 수 있다. 그리고 이로부터 또한 흥미로운 relationship을 마찬가지로 얻을 수 있을 것이다. 하지만 우리가 이러한 fucntion을 선택했던 것은 이는 Laplace operator와 직접적인 관련이 있고, 이는 추후에 graph Laplacian과 연결될 것이기 때문이다. 사람들은 이러한 Fourier series로부터 1차원 Laplace operator의 eigenfunction으로 얻어지게 된다는 것을 발견했다. 위의 식에서 $\Delta$가 Laplace operator이다. Fourier series는 이후에 harmonic function으로서 일반화되며, harmonic function은 eigenvalue가 0에 대응되는 Laplace operator의 eigenfunction에 해당하게 된다. 여기서 harmonic function은 Laplace operator를 적용했을 때 그 결과가 항상 0이되는 function을 의미한다. 디테일한 내용은 생략하고 여기서 알아야하는 것은 바로 사람들이 Fourier series를 Laplace operator의 eigenfunction으로 얻었다는 것이다. 이후에 이러한 graph Laplacian으로 어떻게 연결되는지 설명할 것이다.

Graph Laplacian

Graph Laplacian은 degree matrix $D$에서 adjacency matirx $A$를 뺀 $L$로서 정의가 된다. $L$의 특징은 symmetirc하고 off-diagonal entry들이 non-positive하며, row를 전부 더하면 0이 된다는 것이다. 그리고 사람들은 degree에 대해서 normalization을 한 normalized graph Laplacian $\hat L$을 사용하기도 한다.

여기서 주목해야하는 점은 어떻게 function $f$에 graph Laplacian $L$을 곱한 $Lf$가 Laplace operator를 function에 곱한 $\Delta f$와 연결이 되는지이다. Laplacian matrix $L$을 어떠한 vector $x$에 곱했을 때 생기는 relationship으로 얻어진 새로운 signal $y$의 $i$번째 element $y_i$는 $x_i$와 이웃한 $x_j$를 뺀 것의 합으로 만들어진다는 것이다. 예시로 $x_1,x_2,x_3$의 line graph에서 $(x_2-x_1)-(x_3-x_2)$는 결국 시간에 대한 derivative로 직관적으로 이해될 수 있을 것이다.

이런식으로 Laplacian은 결국 neighbor에 대해서 "deviation from average"로 볼 수 있다. Vertex $i$가 있다고 하면 이에 대응하는 neighbor들이 있을 것이고, 이들의 평균을 구하고 이를 neighbor들과 비교해서 더해볼 수 있을 것이다. 이러한 정의가 결국에는 더 일반적인 경우에 대해서도 사람들이 흔히 부르는 Laplacian이 될 것이다. 그렇다면 어떻게 구할 수 있을까? 사람들은 Laplacian operator를 Euclidean space에서 curvature로 부르기도 한다. 우리는 time signal 혹은 1D signal에서 Laplacian을 구할 수 있을 것이고, 만약 Laplace value가 0보다 작으면, derivative가 positive에서 negative로 바뀌기 때문에 signal이 볼록한 형태를 보일 것이다. 반대로 derivative가 negative에서 positive로 바뀌게 된다면 Laplace value는 0보다 크게 될 것이다.

이러한 현상을 보는 다른 관점은 우리가 하나의 값을 선택하고, 아주 작은 $\epsilon$을 더하고 빼서 선택한 값의 주변을 보는 것이다. Laplace value 혹은 Laplace operator를 적용한 결과는 만약 이웃들의 평균을 내어 그 값이 선택된 지점보다 크게 된다면 positive일 것이다. 주변 neighbor로부터 선택한 지점과의 차이를 평균내다보면 대략적으로 curvature 혹은 continuous signal에서 정의되는 Laplace operator에 근사하게 될 것이다. 결국, Laplacian value를 이와같이 "deviation from average"로 생각하는 것이 이해하기에는 더 쉬울 것이다.

위의 사진은 Laplacian function의 general한 경우를 보여주고 있다. 여기서 function $u$의 Laplacian을 특정 point $x_0$와 $x_0$ 주변의 작은 sphere의 평균 사이의 difference로 생각할 수 있는 것이다. 이 값이 positive인지 negative인지에 따라 curvature가 결정되는 것이다.

이는 $u$의 Laplacian opreator가 0이 되는 harmonic function과 관련해서 흥미로운 점을 제공해준다. Harmonic function에서 하나의 지점을 선택했을 때, 이는 대략적으로 주변과 비슷할 것이다.

우리가 3D 물체를 descretization을 한다고 했을 때, $D-A$로 정의되는 graph Laplacian operator $L$은 limit를 infinity로 취한다면 실제 continuous Laplace operator과 일치할 것이다.

정리해보면 결국 Fourier basis가 Laplace operator의 eigenfunction으로 유도되어 져서 $\Delta f = \lambda f$로 정의가 된다. 여기서 $f$는 discrete time의 경우에 대해서 eigenfunction 혹은 eigenvector가 될 것이다. 이로부터 우리는 Laplace matrix의 eigenvector를 비슷하게 정의할 수 있었고, 이는 $Lf=\lambda f$로 정의가 된다. 그리고 여기서의 $f$는 graph Laplacian의 eigenvector가 될 것이고, 이는 graph signal processing에서 새로운 Fourier basis가 될 것이다.

사람들이 여러 GNN을 만들기 위해서 어떠한 것들을 고려하는지 알아보고자 한다. 이를 설명하기 위해서 위와 같은 레퍼런스로부터 미로라는 metaphor를 이용해서 알아볼 것이다. 이미 존재하는 GNN들을 나누는데 있어 최적의 metaphor가 바로 미로인 셈이다. 여기에는 어떻게 GNN을 적용하는지는 내용이 없으며, 이는 오로지 어떠한 방향으로 GNN 구조에 디자인해야하는지를 설명하고 있다. 총 7가지의 카테고리가 있으며, 대부분 이미 이전에 다 이야기한 내용들이다.

Walk and Look Around

첫번째로는 message-passing과 관련된 전략으로 walk and look around에 대해서 알아보고자 한다. 우리가 미로를 통과하고자 할 때 가장 먼저 하는 일은 일반적으로는 임의로 걸어보는 것이고, 이러한 과정을 message-passing 전략으로 볼 수 있다. 흔히 고전적인 GNN들에서 주로 사용되는 방식이다. 하지만 walk and look around 전략은 흔히 잘 알려진 over-smoothing과 over-squashing 문제로 연결된다.

Over-Smoothing Problem

Over-smoothing 문제는 이전에 이야기했던 homophily와 관련이 있다. GNN이 있을 때 여러번의 message-passing layer를 통과한 후에 output node의 representation이 이웃간에 서로 비슷하게 보이는 현상을 이야기한다. 어떠한 node든 간에 위와 같이 computational graph에서 message-passing이 끝난 후에는 모두 비슷한 성질을 지니게 될 것이다. 근처에 있는 node라고 한다면 2-hop, 3-hop neighbor node 정보를 모은 후에는 거의 동일하게 만들어지게 된다. 아무래도 각 node가 1-hop distance라는 동일한 거리로 떨어져 정의되어 있기 때문이다. 결국 모든 node가 평균화되기 때문에 서로가 비슷한 representation을 만들게 되는 것이고, 이를 우리는 over-smoothing이라고 한다.

Over-Squashing Problem

다음으로 over-squashing 문제는 LSTM에서 흔히 발생할 수 있는 문제이다. 만약 여러 time step으로부터 정보를 모아야한다면 실제로 굉장히 많은 정보들이 모이게 될 것이다. 그리고 이는 hidden layer에 전부 담지 못하게 될 것이다. 이러한 현상이 GNN에서도 발생하는 것이다. 너무 많은 정보들을 GNN으로 모으려고 한다면 각 GNN step마다 기하급수적으로 정보량이 폭발하게 될 것이다. Layer의 수가 많아지면 많아질수록 이웃 node간 degree에 따라서 많은 정보들을 서로 가지게 될 것이다. 따라서 각 vertex가 우리가 필요한 만큼 이상의 정보를 모으게 되는 것을 over-squashing이라고 한다.

이렇게 살펴본 2가지 문제가 지금까지도 사람들이 GNN에서 풀고자 하는 대표적인 문제들이다. 그렇다면 이러한 문제들을 어떻게 해결할 수 있을까?

Color Your Way

첫번째 방법으로는 color your way로, 임의로 random walk나 position에 색을 칠하는 과정이다. 만약 걷는 길을 따라 색을 칠하게 된다면 message-passing update를 위한 기록이 남게 될 것이고, 이에 따라 미로에서 길을 잃지 않게 될 것이다. Message-passing update를 할 때마다 각 vertex에 색을 칠하게 되면 결국에는 GNN에 expressive power를 얻게되는 것과 같아지게 된다.

이와 비슷한 또 다른 예시로는 cycle counting augmentation이 있다. 전체 graph에 대해서 sub-graph를 기록하게 되면 expressive power를 얻게 되는 것이다.

Squeeze Through Narrow Path

이번에는 over-squashing 문제와 관련이 있는 상황을 생각해보고자 한다. 때로는 미로에 우리가 빈번히 지나야만 하는 bottleneck이 존재할 수도 있다. Over-squashing 문제와 관련해서 정보에 bottleneck이 존재한다면 이 문제를 처리하기 위해서 추가적으로 capacity를 늘려주면 될 것이다. GNN 구조로부터 information bottleneck을 확인하기 위한 시도들을 할 것이고, 여기에 hidden dimension을 추가해주게 된다면 over-squashing 문제를 해결할 수 있을 것이다.

여기 expander graph라는 개념이 있다. 만약 많은 정보들이 전체 graph에 대해서 제대로 전파 되지 않는다면, 우리는 여기에 auxilary edge들을 추가함으로써 message-passing을 원활하게 만들 수 있다. 위에서 직선들로 연결된 graph가 expander graph이고, 이는 GNN의 message-passing 구조의 최적화된 결과를 나타낸다. 우리는 이러한 auxilary structure를 추가함으로써 message-passing을 augmentation할 수 있게 된다.

Listen to the Echo

다음으로는 spectral 방법들을 이용한 listen to the echo가 있다. 이는 전체 adjacency matrix로부터 얻어진 eigenvector들을 이용한 spectral한 접근법으로 graph를 파악하고자 하는 것이다.

Use a Map

Use a map은 각 vertex에 positional encoding을 해주는 것이다. 각 vertex에 색을 칠하거나 feature를 더하는 식으로 모든 vertex에 unique한 식별자를 할당해주는 식으로 할 수 있다. Labeling scheme으로 인하여 local position이나 global position을 쉽게 파악하고자 하는 것이고, 이는 흔히 transformer에서 주로 사용되는 방법 중 하나이다.

Destroy Some Walls

Destroy some walls는 auxilary edge를 추가해서 멀리 떨어진 vertex를 가깝게 만들고자 하는 것이다. 우리는 이를 graph rewiring이라고 부를 수 있다.

여러 고전적인 message-passing neural network에는 그들만의 message-passing structure가 있는데, 여기에 GNN의 computational graph를 수정함으로써 더 나은 propagation 결과를 얻고자 하는 것이다.

Fly Above

마지막으로 graph transformer에서 사용되는 개념으로 fly above가 있다. Graph transformer를 이용해서 모든 vertex를 연결해서 graph를 파악하고자 하는 것이다.

이번에는 GNN을 평가하는데 있어 사용되는 여러 benchmark들에 대해서 알아보고자 한다. 이번에 살펴볼 benchmark들은 여러 machine learning 학회에서 볼 수 있는 논문들에 기반한 것들이다.

TUDataset

가장 먼저 가장 유명하고 많이 사용되었던 TUDataset에 대해서 알아보고자 한다. 이해하기 쉽게 이 dataset은 GNN의 MNIST라고 생각하면 된다. 해당 dataset은 vertex가 약 20개에서 100개로 구성된 small-scale graph들로 구성되어 있으며, feature도 상대적으로 적다. 이들은 chemical, biological, social network 등으로 구성되어 있으며, GNN의 초기 모델들을 평가하는데 주로 사용되었다. 그러나 요즘에 이 dataset으로 GNN 연구를 평가하고자 한다면 풀고자하는 문제는 좀 더 어려워야할 것이다. 왜냐하면 사람들이 이 dataset은 variance가 매우 크기에 이전에 논문들에서는 cross validation을 이용하여 평균결과를 보여주곤 했다. 아무래도 data의 분포의 variance가 상당히 크다면, 하나의 실험으로는 그 결과가 의미가 없을 것이기에 여러번의 실험 결과를 보여주는 것이 좀 더 타당할 것이다. 따라서 graph dataset에서 high variance인 경우에는 조심해서 평가할 필요가 있다.

CiteSeer, Cora, Pubmed (Node-wise) Datasets

다음은 좀 더 유명한 node-wise dataset이다. 여기에는 cora, citeseer, pubmed 등의 social network가 포함되어 있다. 해당 dataset은 정말로 널리 사용되었기 때문에 새로운 GNN을 만들었다면 이 dataset으로 평가해볼 필요가 있다. 이러한 node-wise dataset을 이야기할 때 흥미로운 부분 중 하나는 사람들이 이 dataset을 이용할 때 고려하는 문제 중 하나가 homophily 관련 문제라는 것이다. GNN은 기본적으로 neighbor 사이의 정보를 모으고자 한다. 그렇기 때문에 만약 GNN이 주변의 비슷한 정보를 모으게 된다면 아무래도 주변의 vertex에 비슷한 label을 부여하는 식으로 prediction을 하게 될 것이다. 그래서 사람들은 각 dataset을 homophily ratio에 따라서 분류해놓곤 했다. 가령 Texas dataset은 homophily ratio가 매우 작아서 대부분 이웃간 다른 label이 부여되었을 것이고, 반대로 Cora는 homophily ratio가 매우 커서 이웃간 비슷한 label이 대부분 할당되었을 것이다. GNN은 기본적으로 homophily dataset에 대한 성능이 heterophily dataset보다 크다. 그래서 GCN만 보더라도 Texas보다 Cora에서 훨씬 좋은 성능을 보여준 것을 확인할 수 있다.

MoleculeNet, ZINK250k, PCQMv2

이외에도 small molecular dataset으로 MoleculeNet, ZINC250k, PCQMv2 등이 있다.

Large-Scale Graphs

최근 들어서는 large-scale graph들로 구성된 dataset도 많이 등장했다. 이러한 dataset을 평가하기 위해서 많은 scalable GNN이 등장했다. 이전의 dataset과는 다르게 large graph에 동작하는 GNN을 만들어서 평가하곤 한다.

Long-Range Graph Benchmark

또한 long-range graph benchmark들도 많이 등장하는데, 이 dataset들이 정말로 중요하다. 기본적으로 GNN은 매우 먼 vertex사이의 interaction을 포착하는 것이 쉽지가 않다. 따라서 우리는 특별한 GNN을 사용해서 거리가 먼 vertex간 long-range interaction을 포착할 필요가 있는 것이다.

Temporal Graph Benchmark

Temporal graph benchmark에서는 각각의 time step에 따라서 graph들이 변하게 된다. 따라서 우리는 temporal graph를 파악할 수 있는 GNN을 만들어야 한다. 실제로 temproal graph의 예시로 bitcoin이 있으며 실제 세계를 반영한 dataset에 가깝다고 볼 수 있다.

Algorithm Reasoning

Algorithm reasoning이라는 흥미로분 task가 있다. 이 task가 하는 것은 유명한 algorithm들이 위와 같이 있을 때 해당 알고리즘의 output을 예측하는 능력을 기반으로 해서 GNN의 expressive power를 정량화하는 것이다. 위의 결과를 보면 대부분의 GNN이 shortest path 알고리즘이나 bubble sort 알고리즘 등에 강력한 것을 볼 수 있다.

Knowledg Graph Reasoning

마지막으로 또다른 유명한 task로 knowledge graph reasoning이 있다. 이는 knowledge와 관련된 매우 큰 graph들이 있는 dataset을 기반으로 한다. 예를 들어 Michael Jackson이 있고 thriller, disco, Quincy Jones와 같은 관련 키워드가 있을 때, Michael Jackson이 어떠한 장르와 관련이 있는지 맞추는 task이다. 즉, 우리는 어떠한 특정 query를 통해서 원하는 결과를 도출해내야 하는 것이다. 그래서 사람들은 이러한 knowledge graph를 처리하는 GNN을 개발하려고 시도해오고 있고, 이는 실제로 datamining community에서 굉장히 중요하게 여겨지고 있다. 최근에 이 문제를 풀기 위해서 language model이 GNN과 함께 사용되어 개발되어지고 있다. 그리고 사실 language model이 너무 강력해서 knowledge graph model이 필요없을 정도로 발전해오고 있다.

이번에는 2021년도까지 약 10년 동안 중요하다고 생각되는 몇몇 GNN들에 대해서 알아보고자 한다.

Generalization of CNN to Graphs

가장 먼저 우리는 GNN의 역사에 대해서 알고싶기 때문에 사람들이 알게 된 맨 처음 GNN이 무엇인지에 대해서 알아볼 필요가 있다. 사람들이 흔히 알게 되는 GNN은 2016년부터라고 생각할 수 있지만, 그 이전에 2013년도에 Yann LeCun 그룹에서 위와 같은 논문을 제공했다. 이들은 GNN으로부터 receptive field를 늘리거나 각 layer에서 vertex의 수를 줄이는 과정을 위해서 여러 vertex들을 가지고 cluster를 형성하고 이들을 새로운 neuron으로 처리했다. 이렇게 얻어진 coarse grained graph를 가지고 계속해서 propagation을 해나가면 유사하지만 작은 graph를 만들 수가 있게 된다. 이들은 사람들이 "spectral graph convolution"이라 불리는 방식 또한 제안했으며, 이는 graph signal processing에서 가져온 개념이다. 이렇게 이들은 GNN의 첫번째 접근법을 제안했었다. 이후에도 약 3년간 여러 방식들이 제안되어 왔지만, 이들은 대부분 3d mesh data 등에 적용된 방법들이기 때문에 더 중요한 다음 논문을 보고자 한다.

ChebNet

NeurIPS 2016년도에 ChebNet이라고 하는 GNN의 새로운 접근 방식이 제안되었다. 이 논문은 graph signal의 spectral filtering의 대표적인 예시 중 하나이기 때문에 매우 중요하다고 이야기할 수 있다. 먼저 hidden feature matrix가 주어졌다고 가정해보자. 여기서 하고자하는 것은 degree matrix와 adjacency matrix를 이용하여 $D-A$로 계산되는 laplacian matrix $L$을 구하고, 이를 $k$번 곱하는 것이었다. 각각의 $L$에 weight vector $\theta_k$를 곱하고 $k$번 더함으로써 이를 parameterization하고자 한다. 저자들은 graph signal processing community에 속한 사람들이 말하는 graph convolution이 이 논문에서 말하는 과정과 같기 때문에 이와 같은 과정들이 매우 중요하다고 이야기했다.

Spectral Graph Convolution

그렇다면 spectral graph convolution이 무엇일까? 먼저 spectral이라고 말하는 것은 matrix의 eigen-decomposition과 관련이 있다. 따라서 spectral graph convolution은 laplacian matrix의 eigen-decomposition을 기반으로 한다. $L$에 eigen-decomposition을 하면 $U\Lambda U^{-1}$로 만들 수 있고, spectral graph convolution은 실제로 $U(\sum\Lambda^{k}) U^{-1}$에 의해 정의된다. 우리는 이 과정을 $L$을 $k$번 곱하는 과정으로 생각할 수 있어서, 결국 중간의 $U$와 $U^{-1}$는 지워지기 때문에 $L^k=U\Lambda^{k} U^{-1}$가 된다. 결국 위와 같은 식은 eigen-decomposition의 parameterization을 한 것으로, 사람들은 이 과정을 spectral graph convoltuion으로 표현될 수 있다고는 것을 알았고 이 과정은 또한 time signal의 Fourier transformation과 연결되게 된다.

결국 지금까지 소개되었던 두 논문은 spectral graph convolution을 spatial graph convolution으로 정의하여 neural network를 만들게 된 것이다. 실제로 GNN community에서도 GNN의 역사를 크게 spectral GNN과 spatial GNN으로 나누었으며, spectral GNN에서는 message-passing을 통해 얻는 일련의 과정을 signal processing community에서 말하는 것을 따라갔었다. Fourier transformation으로부터 사람들은 graph signal processing을 따라 convolution을 얻는다고 생각했기에 결국 graph Fourier transformation과 graph convolution은 이러한 원칙적인 방법으로부터 얻게 되었다.

Graph Convolutional Network (GCN)

이후에 사람들은 또 다른 접근 법으로 GNN을 표현하게 되었고, 대표적인 예시가 바로 graph convolutional network (GCN)이다. 이 논문은 아마 GNN 연구에 있어 가장 많은 인용수를 기록하는 논문일 것이고, 사람들이 GCN이라고 흔히 불리는 논문이다. 이는 매우 유명한 message-passing update 과정으로 laplacian matrix와 feature matrix, weight matrix를 곱한 결과에 non-linearity를 주었다. 이 논문을 보면 알겠지만, 단순히 이러한 message passing 과정이 main contribution이 아닐 것이다. 이 논문의 main contribution은 이러한 message-passing update가 있는데, 이러한 과정이 우리가 이전 논문들에서 언급되었던 spectral graph convolution이라 불리는 과정의 first-order approximation으로 얻어지게 된다는 것이다. 이 논문 이후로 사람들은 spectral한 접근 보다는 이러한 방식의 message passing 과정을 선호하게 되었다.

Message Passing Neural Network (MPNN)

GCN은 ICLR 논문으로 봄에 출판되었으며, 사람들은 이 논문을 빠르게 읽은 뒤에 GNN 연구들을 계속해서 제안했다. 대표적으로 quantum chemistry에 대한 neural message passing 방법을 새로 제안하게 되었다. 사람들은 분자 구조를 파악할 수 있는 GNN 연구를 했으며, 이러한 유명한 message passing 방법들을 적용해서 분자의 quantum chemical property를 approximation하려고 시도했다. 그렇게 등장한 GNN이 바로 message passing neural network (MPNN)이다.

GraphSAGE

뒤이어 해당년도 NeurIPS에는 GraphSAGE라는 방법이 제안되었고, 이 저자들은 큰 knowledge graph나 database에 초점을 맞췄다. 저자들이 제안한 GraphSAGE는 large graph를 처리하기 위한 방법으로 message-passing update를 더욱 시스템적인 방법으로 접근한다. 따라서 이들은 다양한 조합의 aggregation과 message update를 수행하게 된다. 또한 이들은 scalability를 위해서 neighbor들을 drop하는 것도 제안했으며, 지금까지 사람들이 많이 사용하는 고전적인 Weisfeiler-Lehman (WL) isomorphism test라고 불리는 방법에서 영감을 얻어 만들어지게 되었다.

Relational GCN

Edge에 relation이 있는 graph에 대한 방법으로 Relational GCN이 등장하기도 했다. 각 edge type 혹은 relation에 따라 서로 다른 adjacency matrix를 이용해서 message-passing update를 하는 것이 이 방법의 핵심이다. 예를 들어 우리가 $N$ relation이 있다고 가정했을 때 $N$개의 graph를 만들 수 있으며 각각의 $N$개의 graph마다 message-passing update를 수행할 수 있고, 마지막으로 이들을 합쳐서 결과를 만들 수 있게 된다. 이때 흥미로운 부분은 $N$개의 adjacency matrix가 있는 만큼 $N$개의 weight matrix도 있다는 것이다.

GatedGCN

또 다른 GNN으로 GatedGCN이 있다. 여기서 저자들이 하고자 했던 것은 message-passing update를 할 때 두 node 쌍 사이의 hidden feature에서 gating mechanism을 수행하는 것이다. 두 node의 hidden feature와 edge 사이의 gating mechanism을 통해서 조건을 주는 것이다. 이러한 방법이 graph attention network에서의 attention mechanism과 유사하게 보일 수 있다.

Graph Attention Network (GAT)

GatedGCN과 동일한 년도에 동일한 학회에는 유사하지만 유명한 graph attention network (GAT)가 제안되었다. Message-passing update시 $\alpha$가 두 node 쌍에 일종의 attention을 부여하게 된다. 이들이 제안한 vertex들을 concat하고 linear layer와 뒤따르는 softmax function을 처리하여 attention matrix를 얻는 방식은 전통적인 attention mechanism 방식과는 약간의 차이가 있다. 전통적인 방식에서는 vector간 dot product를 계산하지만, 여기서는 concatenation이 필요하다고 제안했다.

Jumping Knowledge Network (JK-Net)

2018년도에는 jumping knowledge network (JK-Net)이 등장하였다. 아이디어는 residual layer를 GNN에 이용하기 것이기 때문에 매우 간단하다. 비록 아이디어가 상대적으로 간단해보일 수 있지만, 사람들인 이 방법이 놀랍도록 강력하다는 것을 알게 되었다. 연속되는 layer에 residual layer를 연결하는 것 대신에 가장 마지막에 있는 layer에 모든 residual을 연결하는 것이 이 논문의 아이디어이다. 이렇게 얻어진 결과로부터 concat, max pooling 등의 layer aggregation을 하게된다. Random walk에 기반한 추가적인 이론 해석이 있기 때문에 사람들은 이 방법이 얼마나 중요한지 알게되었다. Vertex들 사이에 local information이 message-passing을 거치는 동안 사라지기 때문에 이러한 정보들을 보존하기 위한 residual connection이 상당히 중요해지는 것이다.

Graph Isomorphism Network (GIN)

다음으로는 GNN을 분석하는데 있어 가장 중요한 방법인 graph isomorphism network (GIN)이 등장하였다. 여기서 저자들은 얼마나 GNN의 expressive power가 얼마나 강력한지에 대한 분석을 적어놨다. 이를 위해서 graph isomporphism test에 의해서 GNN의 expressive power를 정량화할 필요가 있다고 주장했다. 예를 들어 2개의 이웃한 vertex를 가지는 서로 다른 2개의 graph가 있다고 해보자. 만약 GNN이 두 graph가 다르다고 주장하게 된다면 해당 GNN은 강력하다고 할 수 있다. 반대로 두 graph가 다르지 않다고 말하는 GNN도 존재할 것이다. 이러한 test를 graph isomporphism test라고 하며, 이 논문은 GNN이 이러한 test를 통과할 수 있는 능력을 정량화했다.

더불어 이 논문의 흥미로운 아이디어는 aggregation step에서 linear update를 하기 이전에 aggregation을 위한 mean pooling을 해왔다는 것에서 시작한다. 실제로는 이웃들의 aggregation을 위하여 sum operator를 사용하기 때문에 message를 update하기 위해서는 MLP를 사용해야 한다고 주장했다. 그리고 GNN과 WL test 사이의 connetction에 의해서 이 방법이 GNN에 더 강력한 expressive power를 제공하게 된다. 그렇다면 이 방법이 왜 더욱 강력함을 보장해줄 수 있는지 생각해보자. 예를 들어 이웃간 mean과 max pooing을 한다고 했을 때 만약 2개 혹은 3개의 동일한 vertex가 있다면 여기에 mean pooling을 했을 때 단지 같은 값을 가져오게 될 것이다. 하지만 반대로 sum pooling을 한다고 해보자. 그러면 우리는 이웃한 vertex들이 2개든 3개든간에 다른 vertex가 있다는 것을 확인할 수 있게 된다. 이렇게 mean pooling과 sum pooling의 차이로 부터 우리는 서로 다른 vertex가 존재함을 파악할 수 있는 것이다. 이 논문은 처음부터 끝까지 WL관련 test로 분석되어 있기 때문에 GNN 논문을 작성할 때 일종의 레시피로서 역할을 할 수 있고, 그에 따라 굉장한 영향력을 행사할 수 있었다.

Simplifying Graph Convolution (SGC)

다음은 simplifying graph convolution (SGC)라는 논문으로 2019년도에 ICML에 제안되었다. 지금까지 사람들이 GNN의 expressive power를 높이기 위해서 matrix multiplication을 이용한 여러 message-passing 방법들을 제안해왔다면, 이 논문에서 저자들은 실제로 데이터셋을 살펴보았을 때 많은 GNN layer가 필요하지 않다는 것을 주장했다. 사람들은 GNN을 더욱 복잡하게 만들거나 정교하게 만들려고 노력해왔었지만, 이 논문에서는 데이터셋이 그만큼 복잡하지 않고 간단하기 때문에 GNN을 복잡하게 만들 필요가 없다는 이야기를 했다. 여러개의 non-linearity를 적용할 필요 없이 하나의 non-linearity만 적용하면 된다고 주장했고, 여기에 adjacency matrix는 여러번 곱하는 것을 이야기했다. 이전의 GCN이 feature propagation, linear transformation, non-linearity를 부여하는 과정을 여러번 수행했다면, SGC의 아이디어는 $k$번의 feature propagation을 한번만 수행하고 마지막에 non-linearity도 한번만 주면 된다는 것이다. 이 방법은 매우 간단하지만 GCN이나 다른 복잡한 방법들보다도 매우 강력한 결과를 만들었다.

여기서 혼란스러워하면 안되는 부분으로 GIN은 linear-message-linear-message에서 message passing을 스킵하는 식으로 동작하고 여기에 MLP를 이용해서 더 많은 non-linearity를 부여하는 식으로 GNN을 더욱 강력하게 만든다면, SGC는 non-linearity를 지움으로써 overfitting을 방지하고 더 빠르게 동작할 수 있음을 이야기하는 것이다.

Principal Neighbourhood Aggregation (PNA)

NeurIPS 2020년도에 제안된 principal neighbourhood aggregation (PNA)는 어떻게 aggregation function을 선택해야 하는지를 이야기하고 있다. 이들은 하나의 aggregation을 사용하기 보다는 mean aggregation operator와 max aggregation operator 사이에서 선택할 수 있다고 말했다. 또한 분산이나 표준편차도 permutation에 invariant하기 때문에 이러한 것들도 aggregation의 방법으로 선택할 수 있다고 했다. 우리는 vertex의 degree로부터 function을 만들 수 있어서, aggregation 결과에 아무것도 하지 않거나 exponential을 곱하거나 하는 식으로 최종 aggregation 결과를 만들어 MLP에 통과시킬 수 있다. 이렇게 하나의 aggregation 방식이 아닌 여러 aggregation 방식을 통해서 성능을 올릴 수 있다는 것이 PNA가 주장하는 바이다.

GCNII

해당 년도에 ICML에는 simple and deep graph convolutional networks라는 GCNII가 발표되었다. 대부분의 경우에 GCN layer를 많이 쌓더라도 성능을 크게 향상시킬 수 없다는 문제를 해결하고자 했다. 그래서 저자들은 간단한 trick으로 매우 깊게 쌓은 GCN에서도 좋은 성능을 낼 수 있도록 제안하였다.

Graph Trnasformer (GT)

이번에는 graph에 transformer를 처음으로 적용한 논문을 살펴보고자 한다. 이 논문의 핵심은 laplacian의 eigenvector를 이용해서 각 node의 positional information을 부여하자는 것이다.

Graphormer

그리고 graphormer의 등장으로부터 encoding 부분을 더욱 추가 함으로써 transformer를 더욱 powerful하게 만들었다. 각 vertex 쌍으로부터 shortest path distance를 이용한 spatial encoding, edge type encoding, 그리고 node degree를 이용한 centrality encoding을 이용하여 transformer 구조를 만들었다. 여기서 centrality encoding은 각 vertex가 얼마나 중심에 있는지를 나타낸다.