Spectral Graph Convolutianl Network
그래프는 노드와 간선으로 이뤄져있으며 개체간의 관계에 대한 정보를 다루는 데이터 구조를 말합니다. 위 이미지에서 보이는 점을 node혹은 vertex라고도 부르고 node를 연결시키는 선을 edge라고 부릅니다. 개체는 node로 표현되고 개체간의 관계는 edge로 표현되는 것입니다. Graph Convolutional연산은 기존에 이미지에 적용했던 CNN 연산을 Graph데이터에 확장해서 graph에서 다양한 크기의 지역적인 정보를 추출해 나가는 연산을 의미합니다. 하지만 이미지에서 적용되었던 CNN과 달리 graph에 Convolutional 연산을 직접 적용하는 것은 매우 어려운 일 입니다. 어떤 점이 어려운 지 이미지에 대한 Convoltuon 연산과 비교해 보겠습니다.
Covolutional 연산
합성곱 연산은 두 함수의 곱을 이용하여 신호와 이미지 데이터를 특정 패턴에 맞게 필터링 하거나 변환하는 연산을 의미합니다.
연속 신호에서
신호 f(t)와 필터 g(t)가 있을 때, 이 두 신호의 컨볼루션 (f∗g)(t)는 아래와 같이 계산됩니다.
이는 시간 축을 따라 움직이며 겹치는 값을 모두 더한 것이 컨볼루션의 결과입니다.
여기서 g(t)는 특정한 패턴을 나타내는데 필터를 축(τ)을 따라 움직이면 서 원래 신호 f(t)와 겹치는 부분의 값들을 곱하여 모두 더하면 두 신호 사이 유사한 부분이 있는 지 평가할 수 있게 됩니다. 필터와 유사한 신호의 특정 부분을 강조해서 볼 수 있게 되는 것이죠.
이산 데이터(이미지)
예를 들어 이미지 같은 경우에는 신호와 필터가 이산적으로 정의되며, 컨볼루션은 보통 합성곱으로 불립니다.(f∗g)
는 입력 데이터, g는 필터 또는 커널이라고 합니다. 이미지에 대해 g는 작은 크기의 행렬(3×)로 표현됩니다.
컨볼루션 연산은 필터가 축을 따라 움직이면서 데이터의 특정 범위에 대해 필터와 유사한 특징을 강조해서 보는 연산이라고할 수 있는 것입니다.
CNN
이미지에 대한 Convolution 연산은 이해하기 굉장히 쉽습니다. 이미지 데이터는 격자에 있는 숫자로 이뤄져 있기 때문에 격자의 순서에 따라 왼쪽 위에서 오른 쪽 아래 방향으로 filter를 움직여가며 특징을 추출하면 됩니다. 위 그림에서 추출된 feature의 하나의 원소들은 3x3 크기의 필터와 image의 부분 간에 내적 값이라고 할 수 있습니다.
convolution 연산에 대한 이미지의 첫 부분을 벡터로 표현하면 [1, 1, 1, 0, 1, 1, 0, 0, 1] filter는 같은 크기의 벡터 [1, 0, 1, 0, 1, 0, 1, 0, 1] 이어서 두 벡터에 대한 내적 값은 1 + 0 + 1 + 0 + 1 + 0 + 0 + 0 + 1 = 4 임을 알 수 있고 추출된 feature map을 보면 filter와 유사한 형태를 가진 부분에서 더 큰 값을 가지고 있습니다. Convolution 연산에서 말씀드렸듯이 filter와 비슷한 값을 가진 부분을 내적을 통해 강조해서 이미지의 특징을 추출하는 것입니다.
Graph에서 Convolutional 연산의 적용이 어려운 이유
graph는 이미지와 달리 격자형태 (Grid-like data) 의 데이터가 아닙니다. 격자 형태(Grid-like data)의 데이터가 아니라는 말은 정형화된 배열이 되지 않은 상태를 말합니다. 먼저 이미지 데이터를 살펴보면, 픽셀이 2차원 격자로 '고정된' 위치에 있으며 일정한 규칙에 따라 연결되어 있습니다. 이미지는 어느 부분을 먼저 보느냐에 따라 상화 좌우의 픽셀 값이 변하지 않으므로 컨볼루션 연산의 시작점에 따라 얻어지는 지역적인 정보가 달라지지 않습니다. 이는 시작점에 상관없이 동일한 방식으로 컨볼루션 연산이 진행되는 것, 이미지 컨볼루션 연산의 Shift Invariance라고 합니다.
예를 들어 이미지 오른 쪽 하단에 동일한 패턴의 무늬가 있을 때 필터가 있을 때 왼 쪽위에서 시작하든 오른 쪽 아래에서 시작하든 동일한 패턴을 감지할 수 있은 것입니다. 이는 본질적으로 필터가 어디에서 시작하든 픽셀 값의 상하 좌우의 연결성이 변하지 않기 때문입니다.
하지만 이미지와 달리 그래프는 정형화된 격자 구조가 아니며, 노드 간 연결이 다양한 형태로 이뤄져 있습니다.
격자 구조가 아니라서 이미지의 픽셀과 달리 노드의 상하좌우가 명확히 정의되지 않아 시작점이 불분명하고 시작점에 따라 컨볼루션 연산도 달라지게 됩니다. 어느 노드를 중심으로 이웃 노드들로부터 정보를 집계하는 지 결과가 달라질 수 있음을 의미합니다.
Graph에서 Convolution의 직접적인 적용이 힘드므로 Fourier Transform을 통해 주파수 도메인에서 graph convolution을 진행하자는 아이디어가 spectral graph convolution입니다.
Fourier Transform
푸리에 변환을 수식적으로 이해하는 것 보다 의미상으로 이해하는 것이 GCN을 이해하는데 중요하므로 의미적인 부분만 다뤄보겠습니다.
푸리에 변환은 신호를 삼각함수들의 합으로 분해하는 방법입니다. 위 그림은 시간축에 정의된 신호를 푸리에 변환을 통해 주파수들의 합으로 분해한 후 분해된 주파수들의 크기를 좌표에 나타낸 것입니다. 신호에 포함된 가장 낮은 주파수는100이며 가장 큰 크기를 갖습니다. 주파수 300은 그 다음으로 신호에서 큰 크기를 갖습니다. (주파수는 초당 진동 횟수를 의미하며 주파수의 크기라는 것은 해당 주파수의 진폭, 주파수가 들리는 소리의 크기를 의미합니다. 주파수는 소리의 높낮이를 의미하지 소리의 크기를 의미하지는 않습니다.)
여기서 중요한 점은 한 신호를 푸리에 변환을 하면 그 결괏값은 항상 유일하게 결정된다는 것입니다. 이는 frequency domain을 구성하는 기저 함수(삼각함수)들이 서로 직교하기 때문입니다. https://m.blog.naver.com/sagala_soske/220983389992
삼각함수들의 직교성을 다룬 포스팅입니다.
삼각함수 끼리는 서로 직교를 이루므로 기저 함수가 되고 기저 함수가 되므로 이를 통해 모든 신호나 주기적 함수를 선형 결합하여 표현할 수 있습니다.
Graph Fourier Transform
그래프 푸리에 변환은 푸리에 변환을 그래프에 확장한 개념입니다. 푸리에 변환과 완전히 같다기 보다는 푸리에 변환이 기저 함수들의 linear combination으로 신호를 나타내 듯이 그래프의 구조를 다음 행렬(라플라시안 행렬, 인접 행렬..) 을 고윳값 분해를 하여 주파수 성분들(고유 벡터들)의 합으로 그래프의 신호들을 나타내는 것 이라 할 수 있습니다.
여기서 그래프의 신호들은 node에 담긴 feature를 말합니다. 그래프에서 주파수는 그래프 내에서 신호가 얼마나 빠르게 변하는 지를 의미합니다. 원래 신호에서 주파수와 고주파수가 있듯이 그래프 내에서도 신호의 변화 속도에 따라 저주파 성분과 고주파 성분이 있습니다. 저주파 성분은 신호가 그래프 전체의 구조적 패턴에 따라 느리게 변하는 성분을 의미하며
저주파수 성분은 그래프의 전체적인 연결 패턴을 의미합니다. 고주파수 성분은 신호가 그래프의 세부적인 구조에 따라 빠르게 변화하는 성분입니다. 고주파수 성분은 그래프의 미세한 변화나 국소적인 부분의 변화를 나타냅니다. 해당 주파수 성분(고유 벡터)이 고주파수인지 저주 파수인지는 고유값을 보면 알 수 있습니다. 고유벡터에 대응되는 고윳값이 크다면 고주파수 성분(고주파수 고유벡터) 고유벡터에 대응되는 고윳값이 작다면 저주파수(성분)가 되는 것입니다.
그래프 마다 정의되는 주파수 성분들(고유벡터들)은 모두 다릅니다. 이는 그래프의 크기에 의해 정해지는 것이 아니고 그래프의 구조적 특성에 의해 정의됩니다. 따라서 그래프의 구조적 특성을 담은 행렬에 대해 고윳값 분해를 해야하는데 이때 가장 많이 사용하는 것은 라플라시안 행렬입니다.
라플라시안 행렬은 Degree Matrix에서 Adjacency Matrix를 뺀 행렬입니다. Degree는 한 개의 노드에 연결된 다른 노드들의 수를 의미하고 Degree Matrix는 각 노드의 degreee들이 대각 원소로 나열된 대각행렬입니다. Adjacency Matrix는 노드 간 연결 상태를 표현한 Matrix입니다.
라플라시안 행렬이 그래프 푸리에 변환에서 자주 사용되는 이유는 다음과 같습니다.
라플라시안 행렬은 대칭행렬
라플라시안 행렬은 대칭 행렬로 고유값 분해를 통해 쉽게 분석할 수 있습니다. 고유값 분해에서 대칭 행렬의 좋은 성질 은 고윳값이 항상 실수이고, 라플라시안 행렬이 nxn 크기에서 정의되었을 때 n개의 실수인 고윳값이 항상 존재하는데 서로 다른 고윳값에서 정의된 고유벡터들은 대칭행렬의 성질에 의해 항상 직교가 되고 서로 같은 고유값에 대응되는 고유벡터들은 그람 슈미트 직교화 과정을 통해 서로 직교하도록 만들 수 있습니다. 결론적으로 직교 대각화가 가능하게 되는 것입니다. n개의 고유벡터에 대해 직교 대각화가 가능하다면 n개의 고유벡터가 서로 일차 독립이 되게 됩니다. 이로써 대칭 행렬은 일차 독립인 고유벡터가 항상 n개가 존재하게 되므로 항상 고윳값 분해가 가능하게 됩니다.
라플라시안 행렬은 신호의 이동을 나타냄
라플라시안 행렬은 그래프에서 신호가 어떻게 이동하는 지 나타냅니다.
f를 5개의 노드에 대한 feature가 담긴 행렬로 보면 각 행이 하나의 node의 feature를 나타낸다고 보면 오른 쪽과 같이 나타낼 수 있습니다. 첫 번 째 행에 대해 분해 해보면 f1 - f2 + f1 - f4로 연결된 노드의 feature간 차이의 합을 나타낸다고 할 수 있을 것 입니다. 이렇게 함으로써 주변 노드간 정보의 차이가 큰 지 적은 지, 즉 그래프 내의 정보의 흐름을 알 수 있게 되는 것입니다. 신호의 차이가 크다는 것은 신호가 노드들 간에 잘 전달되지 않고 있다는 것을 의미하고 신호의 차이가 적다는 것은 노드들 간의 신호 전달이 원활하게 이뤄진다는 것을 의미합니다. 부드러운 신호들로 이뤄진 그래프 라면 Lf의 값이 작을 것이고 변동이 큰 신호라면 Lf의 값이 클 것입니다. 이제 그래프 구조를 담은 라플라시안 행렬의 고윳 갑 분해를 하는 것입니다.
고윳값 분해의 의미
A가 대칭행렬을 만족할 때 A의 고윳값 분해의 결과에 대해 살펴보겠습니다.
고윳값 분해의 의미는 정의역의 기저와 공역의 기저를 서로 같은 것으로 두고 행렬 A에 대해 기저(새로운 축)을 기준으로 행렬이 어떻게 작용하는 지를 나타냅니다. λ_1의 경우 행렬 A가 고유벡터 q1에 대해 λ_1만큼의 선형 변환을 적용한다는 의미를 가집니다.
이를 참고하여 대칭행렬에 대한 대각화 결과 직교행렬과 고윳값 행렬의 곱으로 A를 나타낼 수 있게 됩니다. q1.. qn을 직교 행렬을 이루는 고유벡터, 기저라고 보면
Ax에 대해 고유벡터들의 일차 결합으로 나타낼 수 있습니다. (qi^{T}x는 내적을 의미하므로 λ와 같이 스칼라가 됨)
위와 같은 과정을 통해 Ax를 직교하는 기저들의 일차 결합으로 나타낼 수 있게 된 것입니다.
이는 푸리에 변환이 주기함수를 기저 함수들의 일차 결합으로 나타낸 것과 같다고 할 수 있습니다.
라플라시안 행렬의 고윳값 분해
라플라시안 행렬은 그래프의 구조와 그래프 내의 정보 전달을 나타냅니다. 라플라시안 행렬의 고유벡터는 그래프 내 정보 전달을 직교를 이루며 설명하는 기저들로 이뤄진 것이라 할 수 있습니다. 이 그래프 내의 정보 전달을 표현하는 벡터들로 그래프의 신호 전달 즉, 주파수를 기준으로 표현하는 과정을 아래와 같이 표현할 수 있습니다.
푸리에 변환과 같이 고유벡터와의 유사도로 신호들을 표현한 것이죠.
푸리에 역 변환의 과정은 다음과 같습니다. U^T와 U는 직교 행렬이므로 서로 역함수 관계라는 것을 통해 쉽게 증명될 수있습니다.
Spectal Graph Convolution
위는 Graph에 spectral convolution을 적용하는 수식입니다.
먼저 Notation에 대해 간단히 설명하자면 g()는 컨볼루션을 적용할 필터를 말하고 g(·G)f 는그래프 상에서 신호 f에 대해 필터 g를 적용하는 그래프 컨볼루션을 나타냅니다. F와 F^(-1)은 푸리에 변환과 푸리에 역변환을 의미하고 F를 행렬로 나타내자면 U^T, F(-1)은 U라고 할 수 있습니다. 그래프 컨볼루션 오퍼레이터 g에 U^T를 곱한 것이 gθ(Λ)가 됨을 의미합니다. gθ(Λ)는 라플라시안 행렬의 고윳값에 의존하는 필터를 말합니다. gθ(Λ) = diag(U^T g) 주파수 도메인에서 정의된 대각행렬 형태의 필터 입니다. hadamard product가 아닌 행렬 곱의 형태를 유지하기 위해 대각행렬의 형태로 표한 것입니다.
두 번째 식은 필터와 주파수에 각각 푸리에 변환을 한 후 필터를 주파수에 적용한 값을 역 푸리에 변환을 하면 신호에 바로 필터를 적용하는 것과 같은 결과가 나온다는 것을 의미합니다.
세 번째 식은 U^T와 U가 각각 푸리에 변환과 푸리에 역변환임을 의미합니다.
네 번째 식은 U^Tg가 gθ(Λ)가 되는 것을 의미합니다. 그래프 푸리에 변환에서 신호 f를 필터링하려면, 필터도 푸리에 도메인으로 변환된 상태에서 적용됩니다. 푸리에 도메인에서 필터 g는 U^Tg로 변환되며, 이 과정에서 필터는 라플라시안의 고유값에 의존하는 형태로 표현됩니다.
가장 처음에 제시된 spectral graph convolution 논문 Spectral networks and locally connected networks on graphs에서 제안한 모델은 주파수 도메인에서의 스펙트럴 필터를 학습 시킵니다. 위에서 정의된 식은 필터를 안다는 가정하에 작성된 식이고 실제로는 그래프에서 적용되어야할 필터는 알지 못하는 상태입니다.
그래프이 특징을 잘 찾아내는 필터는 처음부터 알 수 없었습니다. 심지어 그래프에 직접적으로 적용할 수 있는 필터는 적용하기 조차 어려웠죠 하지만 graph fourier transform을 통해서 그래프의 주파수마다 넓은 지역의 정보를(저주파수) 국소적인 정보를(고주파수) 다루기 때문에 지역적인 정보를 학습하는 필터를 학습할 수 있게 된 것입니다.
Spectral convolution은 Convolution연산을 그래프에 적용했다는 점에서 의의가 있지만 학습해야할 파라미터가 n개 노드의 개수만큼 존재한다는 점과 그래프의 구조마다 달라지는 고유벡터에 의해 다른 그래프에 대해 직접적인 적용이 어렵다는 점에서 한계가 있고 이러한 점들을 극복하며 Graph Convolution Network가 발전했다고 할 수 있습니다.