keywords: Paper Review, Graph Neural Network, Spectral Graph Convolution
categories: [Paper]
title : Introduction to Graph Neural Networks_Spectral Graph Convolution

---

YOUTUBE LINK : https://youtu.be/YsyIXqdhreo
PRESENTER : ‍김상민[ 대학원석사과정재학 / 산업경영공학과 ]
DURATION : 01:00:48
PUBLISHED : 2022-07-15

---

FULL SCRIPT

안녕하세요 DMQA 7월 15일 오픈 세미나를 진행하겠습니다.

그래프 뉴럴 네트워크, 특히 스펙트럴 그래프 컨볼루션에 관해서 소개 드리겠습니다.

발표자 소개를 먼저 하도록 하겠습니다.

저는 데이터 마이닝 퀄리티 앤널리틱스 랩에서 석사과정으로 재학 중에 있고, 관심 연구 분야는 그래프 뉴럴 네트워크, 그리고 히몬포지 이스티메이션입니다.

아래 메일로 세미나 관련 문의사항을 주시면 되겠습니다.

세미나에서 다루고자 하는 부분은 스펙트럴 GNN인데요.

스펙트럴 GNN을 알기 위해서는 몇 가지 백그라운드가 필요합니다.

그래프에 대한 기본적인 특징 및 구조도 알아야 하는데요.

이 과정을 최대한 쉽고 빠짐없이 담아보고자 영상이 매우 길어졌습니다.

그래서 청취자 분들께서 그래프 분야에 대한 기본적인 이해가 있다면, 백그라운드에 있으신 분들은 챕터 1을 생략하시고, 2부터 들으셔도 될 것 같습니다.

먼저 그래프 뉴럴 네트워크에 대한 간단한 소개인데요.

그래프 뉴럴 네트워크라고 하는 것은 그래프 구조로 작동되는 뉴럴 네트워크, 인공신경망이라고 보시면 됩니다.

그래서 컴퓨터 과학에서 그래프라는 것은 두 가지, 하나는 노드, 벌텍스와 노드는 같은 말인데요.

노드와 엣지로 구성되어 있는 데이터 구조라고 그래프를 정의하고 있습니다.

그래서 이런식의 일반적으로 그래프라고 생각하시면 됩니다.

그래서 GNN의 계층도를 잠깐 살펴보면, GNN은 펀더멘털 아키텍처, 익스텐디드 아키텍처와 응용 분야, 어플리케이션 쪽으로 나눌 수 있습니다.

본 세미나에서 다루고자 하는 부분은 GCN 중에서 스페이셜 컨볼루션으로 나아가는 과정을 담아보고자 했고, 실제로는 그래프 뉴럴 네트워크가 연구되고 있는 분야는 무척이나 다양하다고 보여주고 있습니다.

실제로 GNN은 유명한 학계입니다.

올해 ICLR에 썸밋된 페이퍼 3,400개의 페이퍼에서 Top Keyword를 추려보았을 때, 강화학습이 첫번째로 많고, 그래프 뉴럴 네트워크도 무방할 정도로 많이 연구가 되고 있습니다.

그래서 GNN이 많이 연구가 되고 있는 이유 중 하나가 다양한 어플리케이션, 다양한 분야에 활용을 할 수 있다는 점입니다.

추천 시스템을 비롯해서 활용이 되지 않은 분야가 없을 정도로 여러 분야에 접목이 되고 있습니다.

대표적으로 몇 가지 분야에서 GNN의 쓰임을 살펴볼텐데요.

대표적으로 몇 가지 분야에서 GNN의 쓰임을 살펴볼텐데요.

이미지에서 Object 객체를 추출하고 객체 간의 관계를 반영하는 Scene Graph를 추론할 수 있습니다.

그리고 정확히 반대입니다.

Scene Graph에서 객체 간의 특징을 통해 이미지를 상상하는 Scene Graph로부터 이미지 상상 쪽도 GNN이 응용되고 있는 분야입니다.

다음으로는 생명과학 및 화학 도메인에서 활용된 사례인데요.

여기서는 물질을 이루는 가장 작은 단위인 야통, 원자를 node로 보고 원자 간의 결합을 edge로 정의한 Graph를 분자입니다.

그래프의 특징, 즉, 분자의 특징을 분석하는 것을 GNN을 통해서 하게 되고, 최종 그래프의 분자가 효능이 있는 약이 될 수 있는지를 예측하게 됩니다.

실제로 앞선 분자 구조 예측은 연구 성과도 이어지고 있는데요.

현재까지 GNN을 활용한 연구 중 가장 위대한 업적이라고 꼽힌다고 합니다.

AI로 내성견을 잡는 강력한 할리신이라는 항생제를 발견했다고 합니다.

그리고 유명한 학술지인 CERE에도 게재가 되었다고 합니다.

이렇게 많은 분야에서 GNN의 쓰임이 넓고 활용 가치가 매우 높은데요.

그래프의 구조와 특징을 살펴보도록 하겠습니다.

먼저 그래프 구조에 관해서입니다.

그래프는 정점이라고 하는 vertex, node와 간선이라고 하는 edge로 구성되어 있습니다.

점과 선이라고 이해해도 되는데요.

앞으로는 vertex 대신 node라고 부르겠습니다.

그래프는 node 간의 연결관계를 표현하는 방법인 adjacent symmetrics, 인접행렬을 사용하게 됩니다.

이 각각에 대해서 살펴보도록 하겠습니다.

앞서서 node를 이야기 했었죠.

edge는 방향성이 있는 directed graph 혹은 방향성이 없는 undirected graph로 나눌 수 있습니다.

아래 그림에서 볼 수 있듯이, 하나의 node에서 다른 node로 향하는 방향이 있으면 directed graph, edge가 서로 bidirectional, 양방향일 때 방향을 화살표로 나타내지 않는 undirected graph로 표현을 합니다.

다음으로는 edge에 가중치가 있으면 weighted graph, weight가 없으면 unweighted graph로 나타납니다.

그리고 너무너무 중요한 adjacent symmetrics, 인접행렬이라고도 하는데요.

node 간의 연결관계를 나타내는 matrix입니다.

node의 개수만큼 행과 열을 이루게 되는데요.

그래서 m by n 정방행렬로 표현이 됩니다.

node 간의 연결이 있으면 1로 표현을 하고, 없으면 0으로 표현하는 행렬입니다.

예시호 node1에 연결된 node2와 node5에 대해서는 1로 표기가 되어있고, node4는 표기가 안되어 있기 때문에 0으로 표시가 되어있습니다.

여기까지가 그래프를 이루는 3요소, node, edge, 그리고 이를 활용한 adjacent symmetrics라고 보시면 됩니다.

계속해서 degree matrix라는 것도 있는데요.

마찬가지로 간단한 개념입니다.

degree는 각 node에 연결된 edge의 개수를 의미합니다.

1번 node로 보면 2번 node와 5번 node에 연결되어 있기 때문에 degree 값은 2가 됩니다.

마찬가지로 다른 node도 edge의 개수를 확인할 수 있습니다.

그래서 이 degree를 matrix form으로 나타내게 되면 대각 행렬의 degree 값이 표현되고, 나머지 부분은 0으로 나타나게 됩니다.

이러한 matrix가 degree matrix가 됩니다.

그리고 degree matrix에서 adjacent symmetrics를 뺀 것이 laplacian matrix라고 합니다.

laplacian matrix가 의미하는 파가 너무 중요하고, 앞으로도 laplacian matrix가 GNN을 하는 데 있어서 핵심이 되는 부분입니다.

laplacian 행렬이 주는 정보는 중심 node와 이은 node 사이에 관계 정보를 알려주는데요.

예시를 보겠습니다.

node value에 해당하는 x1부터 x5까지 있다고 했을 때, 이게 두 번째 column과 곱해진다고 봤을 때, 그러면 결과 값이 이렇게 나타나게 됩니다.

의미적으로 보면 이 식을 아래와 같이 전개를 할 수 있는데요.

x2가 중심 node, column이 두 번째 column이기 때문에, x2가 중심 node가 되고, 중심 node와 이은 node와의 관계를 보여주고 있게 되는 거죠.

그래프로 수행하는 task는 크게 세 가지 종류로 나눌 수 있는데요.

첫 번째가 그래프 단계에서 예측을 하는 겁니다.

이게 어떤 그래프인지.

옆에 보면 이 선수들을 보면 이 node의 값과 이 edge를 파악할 수 있게 되면, 우리는 이 그래프는 Manchester United 되었다 라고

구분 지을 수 있겠죠.

대표적으로 아까 분자 구조, 분자를 예측하는, 분류하는 그런 task가 있을 수 있습니다.

다음으로는 edge 단계, edge를 예측하는 건데요.

대표적으로는 추천 시스템이 있고요.

같은 예시도 보면 퍼거슨 감독 입장에서 선수들은 지도 선수라는 관계가 형성이 되고요.

박지성 선수랑 호날두 선수는 동료라는 edge의 특징을 갖게 되겠죠.

이렇게 관계를 표현하는 그런 edge 단계에서의 예측이 있습니다.

그리고 다음으로 node 단계에서 prediction을 하는데요.

이게 가장 전형적인 GNN에서 연구가 되고 있는 분야입니다.

node classification 입니다.

같은 예시도 한 번 더 보면 퍼거슨 감독은 디덕터, 나머지는 플레이어들인데, 이 edge와 그래프의 특징을 잘 파악하면 no node의 label이 없다고 하더라도 node가 어떤 node인지 알 수 있게 되는 거죠.

여기까지 그래프가 어떤 것이고, 그래프의 구조와 구성 요소에 대해서 살펴보았습니다.

그래프 구조를 가진 그래프 데이터들의 특징에 대해서 살펴보도록 하겠습니다.

일반적으로 이미지나 비디오 데이터를 생각해보면 2차원, 3차원, Euclidean domain에서 표현할 수 있습니다.

격자, 그리드에 나타날 수 있는 건데요.

이미지 같은 경우는 이렇게 격자 형태로 나타날 수 있고, 여기서 하나의 픽셀은 RGB 값을 가지게 되죠.

그래서 3차원으로 나타날 수 있는 겁니다.

문장이나 단어, 음성 데이터도 마찬가지로 1D 격자의 데이터를 표현할 수 있고, 3차원을 가지게 되는데요.

이렇게 규칙적인 공간, 격자 구조로 표현이 가능하기 때문에 우리가 알고 있는 컨볼루션 연산이나 풀링 연산을 할 수 있게 됩니다.

그렇다면 그래프 데이터도 이렇게 격자로 나타내서 컨볼루션 연산을 할 수 있을까?

생각해볼 수 있습니다.

얼핏 생각해보면 그래프도 격자에 나타날 수 있지 않느냐고 생각할 수 있는데요.

실제로 그래프의 대형을 생각해보면 쉽지가 않습니다.

그러면 격자로 나타내면 컨볼루션 연산이 어떻게 진행되는지 살펴보겠습니다.

우리가 알고 있는 CNN에서 컨볼루션 연산이 진행되는 과정인데요.

이렇게 필터 크기만큼 이미지 패치의 연산이 되는 과정을 거치면서 최종적으로 하나의 이미지가 연산이 되는데요.

이런 컨볼루션 연산을 템플릿, 필터와 매칭이 된다고 해서 템플릿 매칭이라고도 합니다.

우리가 알고 있는 2D 컨볼루션은 이미지 1부분에 해당하는 이미지 패치의 템플릿, 필터, 우리가 학습하는 필터를 매칭하는 것이라고 이해할 수 있습니다.

그래서 이미지 패치와 필터를 다 프로덕트 하기 때문에 이 부분을 커릴레이션이라고도 이해할 수 있죠.

아래 그림 예시에서 배경에 해당하는 이미지 패치원에서 필터와 다 프로덕트하는 과정을 커릴레이션으로 보면 1, 상대적으로 낮은 값이 나오지만, 이 부분을 커릴레이션으로 보면 3이 나오게 됩니다.

1보다 높은 값이 나오게 되면서 이렇게 이미지 특징을 요약하는 과정을 수행하게 되는 거죠.

이것을 템플릿 매칭, 커릴레이션하는 과정으로 볼 수 있습니다.

여기서 중요한 특징이 있는데요.

이미지 패치가 3x3이고 필터도 3x3이라고 할 때 무작위로 매칭을 시키는 것이 아니라 정확하게 같은 위치에 있는 값끼리 매칭을 시키게 됩니다.

그래서 이미지 패치가 달라지더라도 같은 위치에 있는 값끼리 필터와 매칭을 시키는데요.

이 같은 위치를 같은 노드 라고 볼 수가 있게 되는 거죠.

그래서 이 필터, 템플릿 내에 있는 이 노드의 위치는 변하지 않기 때문에 템플릿 내에 동일한 정보를 다른 이미지 패치에 매칭을 할 수 있게 되는 거죠.

여기까지가 우리가 격자 상태에서 데이터를 나타낼 수 있었을 때 컨볼루션 연산 즉 템플릿 매칭을 수행하는 과정이었는데요.

그러면 이 과정을 그래프에도 동일하게 적용할 수 있냐 라고 생각을 해보면 당연히 잘 안되겠죠.

왜냐하면 두 가지 이슈가 있습니다.

첫 번째는 노드의 인덱스 혹은 포지션, 위치 정보가 없기 때문에 그리면서 템플릿에 노드 하나가 있는데 이 노드가 그래프에서 어떤 노드에 매칭이 되는지 전혀 알 수가 없는 거죠.

왜냐하면 포지션 정보, 위치 정보가 없기 때문에 매칭이 어디에 되는지 알 수가 없다는 점이 있고요.

두 번째가 템플릿에 있는 하나의 노드는 이웃 사이즈가 두 개인데 그래프에서 매칭되는 노드의 이웃의 수는 또 세 개, 이런 경우가 있겠죠.

이랬을 때 어떻게 템플릿 매칭을 할 것이냐 이런 문제가 생기곤 합니다.

그래서 그래프에 알맞게 템플릿 매칭을 정의해야 하는데요.

우리가 알고 있는 CNN에서 하는 템플릿 매칭은 할 수가 없죠.

그래서 신호처리 분야에서 쓰이는 컨볼루션 정리를 활용하게 됩니다.

두 함수의 컨볼루션을 해서 풀이의 변환을 하는 것은 각각의 함수의 풀이의 변환을 해서 포인트 바이즈 프로덕트를 하는 것과 동일하다는 내용인데요.

수직으로 보면 조금 더 이해가 편할 것 같습니다.

두 함수를 풀이의 변환을 하는 것은 각각의 함수에서 풀이의 변환을 해서 포인트 바이즈 프로덕트를 하는 것과 동일하다는 내용입니다.

그래서 우리가 컨볼루션 연산을 하고 싶으면 앞선 수직에서 풀이의 역변환을 해서 이 부분을 벗겨내게 되는 것이죠.

그래서 최종 수직이 이렇게 되는데요.

그러면 이 개념만 그래프에 접목시킬 수 있으면 그래프에서도 컨볼루션을 할 수 있게 되는 것이죠.

이미지에서 공간 도메인이라든지 아니면 신호에서 시간 도메인에서 이렇게 컨볼루션을 하는 것은 풀이의 도메인에서 풀이의 도메인에서 멀티플리케이션을 하는 것과 동등하다는 얘기가 나오게 됩니다.

우리가 일반적으로 이미지에서는 컨볼루션 하는 과정이 익숙한데 신호에서 컨볼루션 하는 과정을 그림에서 보여주고 있습니다.

FT가 필터가 되고요.

파란색이 필터고 GT가 시그널이 되게 됩니다.

신호가 변화하면서 필터와 중첩이 되면서 생기는 값이라고 보면 됩니다.

컨볼루션 정리는 시공간 도메인에서 풀이의 도메인으로 바꿔서 계산한다는 것인데요.

풀이의 변화, 풀이의 도메인은 뭔가가 다음 질문이 되겠죠.

풀이의 변화는 이미 입력신호를 다양한 주파수를 갖는 주기함수들의 합으로 분해하는 과정인데요.

그림을 통해 보면 입력신호 FT가 사인코사인으로 표현되는 함수가 되고요.

이를 여러 주기함수로 분해하게 됩니다.

분해한 주기함수들을 주파수 도메인에서 표현하는 것이 풀이의 변환이라고 볼 수 있습니다.

이렇게 주파수 도메인에서 다시 타임도메인으로 바꿔서 FT로 나타내는 과정을 풀이의 역변화, Inverse Pre-Transformation이라고 합니다.

그래서 입력신호가 어떤 신호든 상관없이 사인코사인 주기함수들의 합으로 분해할 수 있습니다.

입력신호가 이미지에서는 공간축에 대한 정의된 신호가 되고, 전판음성신호에서는 시간축에 대한 정의된 신호라고 볼 수 있습니다.

영상처리 분야에서는 이미지를 스페이셜 도메인에서 Frequency 도메인으로 변환을 해서 컨볼루션 연산을 하게 되고요.

아래 예시를 통해서 보면 원본 이미지가 풀이의 변환을 하게 됩니다.

육안으로는 풀이의 변환을 통해서 나온 결과값, 필터에도 풀이의 변환을 해서 두가지, 두개를 곱하 멀티플리케이션 해서 나온 결과값을 풀이의 역변환을 하면 실제로 필터로 바로 컨볼루션을 하는 것과 동일한 결과를 갖게 됩니다.

앞서 얘기한 컨볼루션 띄어리업이 됩니다.

풀이의 변환에 대한 개념은 여기까지 살펴봤고, 직관적인 이해나 수직적인 이해를 위해서는 해당 영상들을 참고하시면 많은 정보들을 추가적으로 이해할 수 있을 것 같습니다.

여태 컨볼루션은 템플릿 매칭을 그래프 데이터에 적용하지 못했습니다.

그래서 조금 다른 방식으로 컨볼루션 띄어리업을 가지고 와서 풀이의 변환을 하려고 했는데요.

이 과정을 똑같이 이미지나 시간에서 할 수 있던 것처럼 그래프에도 적용을 해보려고 합니다.

그래프의 스페셜한 도메인에서 프리퀀시, 스펙트럴, 풀이의 다 같은 영역을 의미합니다.

도메인을 바꿔서 최종적으로 컨볼루션 연산을 진행하고자 합니다.

여기까지 문제 상황을 제기하는 서론에 해당이 되었고요.

길고 긴 서론 끝에 본론의 시작은 그래프에 풀이의 변환을 어떻게 할 것인가 입니다.

그래서 사실 이 부분이 본 세미나를 준비하는데 계기가 되었던 부분이기도 하고, 이 부분을 조금 더 디테일하게 이해를 하고 싶었습니다.

창고문언을 찾아보니 두 가지 방향으로 소개를 하는데, 본 세미나에서 한 가지 방향은 구두로 설명을 드리고, 나머지 한 가지는 어펜딕스에 남겨두었으니 살펴봐 주시면 될 듯 합니다.

풀이의 변환은 간단하게 다시 말하면 이미의 입력신호, 이 시그널을 다양한 주파수를 갖는 주기함수의 합으로 분해하는 과정이라고 했는데요.

그래프에서 입력신호는 뭐냐?

그래프 노드가 갖는 값이라고 보시면 됩니다.

이미지에서는 하나의 픽셀이 갖고 있는 RGB, 3차원 값이라고 보면 되고요.

그래프에서는 노드가 갖는 값인데, 이게 1차원으로 된 값도 있고, 여러 차원으로 구성된 Feature Matrix로 구성된 값이 될 수도 있습니다.

다음으로 입력신호에 풀이의 변환은 어떤 식으로 진행이 되는지를 살펴보겠습니다.

가정을 순환하는 격자 그래프라고 가정을 하고요.

이런 상황에서 컨볼리션을 한번 해본다고 생각을 해보겠습니다.

참고로 격자 그래프라는 것은 그래프 이론에 있는 개념인데요.

지금은 1차원 격자 그래프에서 순환하는 구조로 나타낸 것입니다.

순환하는 격자 그래프에서 컨볼리션을 한다는 것은 각 노드의 특정 웨이트가 곱해지는 것입니다.

그래서 최종 어그리게이션을 해서 새로운 Feature 값이 나오게 됩니다.

그리고 한 칸을 움직여서 3개의 노드에 동일한 웨이트, ABC가 되겠죠.

곱해져서 더해지면 H2라는 새로운 Feature 값이 나오게 되겠죠.

그리고 또 한 칸을 이동해서 X2, X3, X4에 ABC가 곱해져서 H3가 나오면서 이런 컨볼리션 과정이 계속 진행이 됩니다.

이걸 이제 횡렬로 나타내면 우리가 곱한 웨이트를 이렇게 표현할 수 있겠죠.

아까 그림으로 살펴보면 X0, X1, X2에 곱해지기 때문에 각각의 곱해지는 부분에 ABC가 있고 나머지 X3와 X4에는 제로 값이 곱해지는 상황으로 볼 수 있습니다.

그리고 두 번째 한 칸 움직였을 때 X1, X2, X3에 곱해지기 때문에 필터에서도 오른쪽으로 한 칸 움직인 ABC가 곱해지게 되는 상황입니다.

그래서 이 과정을 좀 더 일반화해서 횡렬로 표현을 하게 되면 이렇게 나타낼 수 있을 것 같은데요.

각각의 노드를 Signal로 보고 그리고 아까 필터라고 했던 부분을 특징을 생각해보면 이렇게 한 칸씩 움직이기 때문에 회전하는 횡렬로 표현을 할 수 있습니다.

그래서 ABC라는 웨이트를 가지는 회전 횡렬로 나타낼 수 있습니다.

그래서 수직적으로 X라는 Signal에 회전 횡렬이 곱해져서 FX가 나오게 되고 이게 새로운 Feature 값이 됩니다.

회전 횡렬에 대해서 소개를 드렸고요.

이것은 이제 컨볼루션을 하는 것이다.

그러면 이제 본격적으로 풀이의 변화는 어떻게 하는지에 대한 유도를 해보겠습니다.

먼저 회전 횡렬의 중요한 특징인데요.

회전 횡렬은 교환법칙이 성립을 합니다.

그래서 어떠한 두 종류의 회전 횡렬을 교환해서 곱하더라도 동일한 값을 가진다.

즉 교환법칙을 만족을 하는데요.

이로써 컨볼루션 연산은 교환법칙이 성립하는 연산이다.

라고 정리를 할 수가 있습니다.

다음으로 선형대수로 넘어가서 잠깐 이런 성질을 기억할 수 있습니다.

교환법칙을 만족하는 각각의 횡렬은 동일한 Eigenvector를 가집니다.

그러면 이런 결론을 유출할 수 있습니다.

모든 회전 횡렬이 교환법칙을 만족했기 때문에 모든 회전 횡렬은 동일한 Eigenvector를 가지게 됩니다.

모든 회전 횡렬은 동일한 Eigenvector를 가지기 때문에 대표적으로 가장 간단한 회전 횡렬인 오른쪽으로 한 칸 만큼 이동하는 회전 횡렬을 고유값 분해를 하게 되면 이렇게 Eigenvector가 나오게 됩니다.

이 Eigenvector를 보니 우리가 알고 있는 Discrete Fourier Transformation, 이상 Fourier 변환에서 Fourier basis와 동일하게 됩니다.

이 Fourier 변환에서 Fourier basis와 회전 횡렬의 Eigenvector와 정확하게 동일하게 됩니다.

그래서 이 네 번째 이야기, 우리가 방금 얘기한 부분을 찾기 위해서 앞서 컨볼루션 연산은 회전 횡렬로 표현을 해서 얘기를 해 왔습니다.

그래서 정리를 해보면 컨볼루션 연산은 회전 횡렬로 표현을 할 수 있고요.

회전 횡렬은 교환법칙이 성립을 합니다.

교환법칙을 성립하는 두 횡렬은 동일한 Eigenvector를 가지기 때문에 회전 횡렬의 가장 간단한 form을 Eigen decomposition을 해보니 그 때 Eigenvector가 이상 Fourier 변환에서 basis와 동일하게 됩니다.

그래서 회전 횡렬을 고유가 분해를 해서 이런 식으로 표현을 할 수 있고 이런 식의 form을 우리가 살펴보자니 앞서 컨볼루션에서 나왔던 수식과 대응이 됩니다.

회전 횡렬이 x가 signal이 되고 두 개를 컨볼루션 하는 것은 Eigenvector에 transpose한 것과 입력 신호를 곱한 것이 Fourier basis가 되잖아요.

그래서 두 개 곱한 것이 Fourier 변환을 한 것과 동일하고 필터에 Fourier 변환을 씌운 것이 abc라는 weight를 가진 회전 횡렬의 Eigenvalue가 됩니다.

이것과 대응이 되고, 마지막으로 이것을 Eigenvector를 곱함으로써 Fourier 역변화를 한다고 볼 수 있습니다.

정확하게 대응이 되는데요.

우리가 결론 지을 수 있는 부분은 입력 신호에 Fourier 변화를 하는 것은 입력 신호에 Fourier basis를 곱하는 것인데 이것은 회전 횡렬의 Eigenvector와 동일하다.

그래서 Eigen decomposition해서 Eigenvector를 곱해버리면 됩니다.

라는 결론을 도출할 수 있습니다.

그래서 Fourier 변환을 의미적으로 살펴보면 입력 신호의 검은색 축이라고 생각해보겠습니다.

입력 신호에 basis가 검은색 축이면 여기에 phi transpose를 곱한다는 것은 세타만큼, 특정 각도만큼 이동해 기절을 바꾸는 것이라고 이해할 수 있습니다.

그래서 convolution을 한다는 개념이 회전한다는 것입니다.

그래서 세타만큼 회전한다는 의미와 동일하게 됩니다.

Fourier 변환을 한다는 것은 Eigen decomposition을 해서 회전 횡렬의 Eigenvector로 곱한다는 것과 동일한 의미를 가지는데요.

그 사실을 바탕으로 스펙트럴 컨볼루션을 드디어 할 수 있게 됩니다.

지금까지 지난 과정을 왜 거쳐왔는지를 다시 말씀드리면 Fourier 변환을 한다는 것은 Eigenvector의 transpose를 곱하는 것과 동일하다.

실제로 우리가 회전 횡렬, weight가 포함된 회전 횡렬을 모르기 때문에 우리가 알고 있는 값은 신호 x 값, 그리고 이상 Fourier 변환에서 Fourier basis는 고정된 값이기 때문에 알고 있는 값으로 볼 수가 있죠.

그래서 모르는 것은 딱 하나, Eigenvalue 값이 됩니다.

회전 횡렬의 Eigenvalue 값을 모르기 때문에 이 부분을 우리가 학습해서 찾아내면 되는 거고요.

이것을 최종적으로 학습할 파라미터로 삼게 되는 거죠.

그래서 weight가 포함된 회전 횡렬을 우리가 모르기 때문에 이런 식으로 둘러간다고 보시면 됩니다.

이 값을 알고 이것을 학습해서 찾아내게 되면 되고 그 다음 다시 Fourier 변환을 Eigenvector를 곱하면서 최종 fx를 구할 수 있게 되는 거죠.

거의 다 왔는데요.

8분의 1을 넘었고요.

그러면 우리가 회전 횡렬은 순환하는 1차원 격자 그래프에서 표현을 했는데요.

일반적인 격자가 아닌 그래프에서는 어떤 식으로 적용이 가능한지에 대해서만 해결을 하면 됩니다.

Non-grid 그래프에서만 이 상황을 적용을 시키면 됩니다.

순환하는 격자 그래프에서는 회전 횡렬에 해당하는 부분이 일반적인 Non-grid 그래프에서는 Adjacency Matrix에 해당이 됩니다.

왜 Adjacency Matrix에 해당이 되는지는 아래 논문에서 얘기를 하고 있는데요.

참고를 하시면 될 것 같고요.

Non-grid 그래프에서는 그래프의 위상이 다 다르기 때문에 그래프 형태가 다 다르기 때문에 그래프 별로 다른 Adjacency Matrix를 가지고 그렇기 때문에 이것의 Eigenvector가 다 다르기 때문에 각각의 그래프에 대한 Phi가 존재하게 됩니다.

회전 횡렬에서 Eigenvector를 찾는 것처럼 Non-grid 그래프에서는 Adjacency Matrix를 Eigenvector를 찾아야 되는데요.

찾으려고 하다 보니까 Adjacency Matrix가 Eigen decomposition이 항상 되는 것은 아니라는 점입니다.

그래서 Adjacency Matrix의 모든 특징을 잘 담고 수학적으로 더 편리한 Laplacian Matrix를 사용하게 됩니다.

앞서 Laplacian Matrix가 의미적으로도 중요하고 앞으로 GNN의 핵심이 된다고 말씀을 드렸는데요.

Laplacian Matrix는 중심 노드와 이웃 노드 사이의 관계 정보를 파악할 수 있고 대칭을 하기 때문에 Eigen decomposition이 됩니다.

Laplacian Matrix를 Eigen decomposition 해보니까 Phi, Eigenvector, Eigenvalue가 나오고 다시 Eigenvector transpose로 표현이 됩니다.

그래서 Eigenvector transpose한 Laplacian Eigenvector를 풀의 function이라고 볼 수 있게 됩니다.

이것을 곱해 주면 입력신호에 풀의 변환을 할 수 있게 됩니다.

그래프 도마인에서 풀의 basis, Phi0부터 Phi3까지 곱해 주면 그래프 이상이 변한다는 것을 볼 수 있습니다.

Adjacency Matrix를 안 쓰고 Laplacian Matrix를 쓴다고 했는데요.

Laplacian Matrix를 쓰긴 하는데 정교화된 Laplacian Matrix를 사용하게 됩니다.

우리가 앞서 배운 것은 정교화되지 않은 Laplacian이고요.

Laplacian

Matrix를 정교화했을 때는 최종적으로 이렇게 나타낼 수 있습니다.

그러면 이제 Spectral Convolution을 최종 정리를 할 수 있게 됩니다.

우리가 Phi transpose를 한다는 것은 Laplacian Matrix에서 Eigenvector를 transpose해서 곱한다는 의미입니다.

이렇게 하면 길고 긴 설명 끝에 그래프 풀의 트랜스포메이션을 할 수 있게 됩니다.

그래프 풀의 트랜스포메이션을 필터, 커널, W에도 동일하게 하겠는데요.

이것을 우리가 학습을 하게 됩니다.

이것을 우리가 학습한다고 볼 수 있고 이 두 가지를 Multiplication해서 최종적으로 Eigenvector를 곱하면 풀의 역변환을 하게 됩니다.

우리가 이 가운데 있는 값을 학습해야 할 파라미터라고 보게 되는 거죠.

이것을 학습하는 것이 Spectral Convolution입니다.

그리고 이것을 Spectrum이라고도 합니다.

그래서 쭉 정리를 해보면 Signal이 있는데 입력신호가 Node의 Feature라고 했죠.

이것을 Laplacian의 Eigen decomposition을 해서 Eigenvector를 곱하는 과정을 그래프 풀의 트랜스포메이션이라고 하고 곱했습니다.

곱하고 나서 필터를 학습을 시킵니다.

이 부분이 되겠고요.

필터를 곱하고 나서 다시 Inverse Graph Freight Transformation을 하게 됩니다.

그때 곱해지는 것이 Eigenvector가 됩니다.

그래서 최종적으로 이 수식이 필터된 입력신호라고 보시면 됩니다.

그래프 풀의 트랜스포메이션을 설명하고 Spectral Convolution을 설명하기 위해서 정말 많은 과정을 거쳐왔는데요.

한번 정리를 해보겠습니다.

문제상은 그래프 데이터가 그리드 형태로 구성이 안된다는 점에서 출발했습니다.

그리드 형태로 구성이 되지 않기 때문에 일반적으로 템플릿 매칭이라고 하는 다프로덕트하는 컨볼루션 연산이 할 수 없게 되는 것입니다.

그래서 그래프에서는 특별한 컨볼루션 과정이 필요했고 해결책으로 컨볼루션의 Theorem, 신호처리 분야에서 활용되는 컨볼루션 정리를 사용하게 되었습니다.

그래서 스페셜 도메인, 타임도메인, 프리컨시 도메인, 스펙트럴 도메인으로 변환해서 컨볼루션을 수행하게 되었습니다.

그래서 풀의 도메인에 대해서 생소하니까 풀의 트랜스포메이션에 대해서 알아보았고 풀의 트랜스포메이션을 어떻게 하냐고 봤을 때 회전행렬의 Eigenvector를 곱하는 것과 동일하다.

그래서 회전행렬의 Eigenvector는 곧 풀의 베이시스 라는 것을 알아보았습니다.

이것을 알아보았을 때는 그리드 그래프에서 알아보았는데요.

넌 그리드 그래프에서는 회전행렬 매트릭스가 라플라이시안 매트릭스가 되고 라플라이시안 매트릭스의 Eigenvector를 곱하는 것이 곧 그래프, Eigenvector가 곧 그래프 풀의 베이시스에 해당이 됩니다.

그래서 그래프 풀의 변화는 라플라이시안 행렬의 Eigenvector를 곱하는 것과 동일하다는 결론이 이르렀고 최종적으로 입력신호에 컨볼루션, Theorem을 적용하는 것이 Spectral Graph Convolution이라는 것을 살펴보았습니다.

이제 마지막 챕터인데요.

Spectral Graph Convolution 개념을 활용한 네트워크 방법론을 살펴보겠습니다.

총 세 가지 논문에 대해서 소개를 드리겠습니다.

첫번째가 Spectral Graph Convolution 네트워크의 시작이 되는 논문이고요.

두번째가 Spectral Graph Convolution의 연산량을 줄이고 한계점을 극복하고자 제시됐던 논문인데요.

이 논문은 실제로 Spectral Graph Convolution의 한계점을 극복하고자 스페이셜한 컨볼루션 개념이 도입되는 논문이라고 보시면 됩니다.

그리고 마지막으로 우리가 GNN, GCN 공부를 하면 가장 많이 접하는 논문에 대해서 최종적으로 살펴보겠습니다.

첫번째 논문의 핵심은 컨볼루션, Theorem을 그래프에 적용시킨 것인데요.

L 같은 경우는 Layer, Set 같은 경우는 Nonlinear Activation Function이라고 보시면 됩니다.

컨볼루션, Theorem에서 아까 살펴봤던 것이 필터의 풀이의 변환을 한 것을 학습시키기 때문에 M by N, 대각행렬을 우리가 학습해야 할 파라미터라고 봅니다.

그리고 여기서 나온 Lambda0에서 Lambda n-1이 n계가 학습해야 할 파라미터 동시에 스펙트럼이라고 볼 수 있고 그러면서 이런 식으로 확인할 수 있습니다.

지금은 입력신호가 1차원일 때가 나타났고요.

그래서 차원을 계산하게 되면 M by 1이 되고 필터가 M by N 그리고 풀이의 Eigenvector가 M by N이 됩니다.

그래서 정리를 하면 이 필터가 스페셜 필터였는데 여기서 컨볼루션 계산을 못하기 때문에 우리가 프리의 도메인 혹은 스펙트럼 도메인으로 넘겨서 연산을 진행한다고 볼 수 있습니다.

그런데 몇 가지 한계점이 있는데요.

첫 번째가 스페셜 필터가 과연 특정 지역에 대한 특징을 추출하느냐 로컬라이제이션을 잘 하느냐의 문제인데요.

이미지 같은 경우는 여러 컨볼루션을 거치면서 스케일이 달라지는 멀티 스케일에 해당하는 퓨처를 뽑아내게 됩니다.

그래서 다른 리세티브 필드를 가지게 되고 특징을 추출할 수 있게 되는데요.

지금은 M by N에 해당하는 필터를 학습시키는데 이 필터만 여러 레이어를 거쳐서 학습시킨다고 로컬라이제이션이 잘 되느냐는 보장이 없다는 말이죠.

그리고 두 번째가 학습해야 할 파라미터가 너무 많다는 점인데요.

M by N의 대각행렬인 이 부분이 N계가 되겠죠.

N계, lambda0부터 lambdaN-1, N계의 파라미터를 학습하면 되는데 N계가 뭐가 맞냐고 물을 수도 있지만 실제 그래프의 경우 웹상이라든지 페이스북에서는 노드의 개수가 수억 개가 되기 때문에 각각의 레이어를 거치면서 여러 번 학습을 한다면 엄청난 양의 파라미터가 되게됩니다.

그래서 일단 N계를 줄이고 싶은 부분이 있고요.

두 번째가 프리에 변환을 하기 위해서 아이겐 벡터를 곱하는 데 일단은 아이젠 디컴포리션을 해야 하는 것도 상당히 연산 복잡도를 높이는 것이고 M by N을 곱하는 연산량도 상당하기 때문에 지금 N2만큼의 개선 복잡도를 유발하고 있습니다.

그래서 이것도 상당한 양의 개선 복잡도이고 학습해야 할 파라미터도 많다는 점이 심각한 문제점으로 꼽히고 있습니다.

그래서 두 번째 논문은 아까 언급한 라플라시안을 아이겐 디컴포지션에서 아이젠 벡터를 사용하는 문제점을 개선하고자 했습니다.

그래서 아이겐 디컴포지션을 하지 않고 학습할 수 없을까?

라는 물음에서 나온 것이 폴리너미얼 파라미터 리제이션인데요.

이 학습할 파라미터의 형태가 이런 식으로 바뀌게 되는 거죠.

이 부분에 대해서는 뒤에 좀 더 구현을 하도록 하겠습니다.

그래서 결국 해답을 찾았는데 폴리너미얼 파라미터 리제이션이라는 방법을 썼다.

그래서 이 학습할 파라미터를 폴리너미얼 파라미터 리제이션으로 바꿔놓고 이런 포뮬레이션으로 바꿔놓고 나서 식을 좀 전개해보니까 이 부분을 참고해서 살펴보시면 최종적으로 식이 이렇게 간추려집니다.

결론은 아이젠 디컴포지션을 하지 않아도 된다.

수식을 한번 보면 h는 입력신호, l은 라플라시아 메추르트 라플라시아 메추르트를 k번 만큼 제곱하고 앞에 세타 k만큼 곱하게 되는 건데요.

이 세타 k가 당연히 학습해야 할 파라미터이고요.

수식적으로 보면 우리가 앞서서는 nxn n개가 의미하는 것은 로드의 개수인데요.

k로 바뀌었다는 점도 눈여겨볼 만합니다.

그래서 앞서서 간추려진 최종 수식 포뮬레이션을 보면 k에 주목을 해야 하는데요.

k가 앞서서 우리가 n개의 파라미터를 학습을 했어야 했다면 우리가 설정한 k개 만큼만 학습을 하게 되면 됩니다.

그러면 예시로 만약에 k가 3이라고 하면 k는 0부터 2까지가 되기 때문에 이런 식으로 식을 펼쳐볼 수 있죠.

그러면 라플라시안이 있고 라플라시안의 스케어 한 개가 해당이 됩니다.

의미적으로 보면 라플라시안은 하나의 호프의 이웃을 이야기하는데요.

어떤 의미냐면 여기서 1번 노드에서 하나의 호프는 2번 노드와 5번 노드인 거죠.

한 번에 닿을 수 있는 노드를 의미합니다.

그리고 라플라시안에 제곱을 하면 첫 번째 노드 기준에서 보면 2번 노드와 5번 노드에서 하나씩 더 뻗어 나간 거죠.

그래서 2호프만큼 볼 수 있게 되고 그 노드가 4번과 3번이 해당이 되는 거죠.

그래서 이런 식으로 만약에 호프가 3개라고 하면 그래프가 여기 좀 더 확장되어 있다고 하면 첫 번째 거리에 있는 호프에 있는 이웃까지 특징을 살펴볼 수 있게 되는 거죠.

이런 특징이 더 이상 스펙트럴 도메인, 주파수, 스펙트럼을 이야기하는 것이 아니라 스페이셜 도메인에 왔다고 보고 있습니다.

수직적으로도 알젠 디컴포지션을 하지도 않고 알젠 벡터를 곱하지도 않기 때문에 완전히 스페이셜 도메인이라고 볼 수 있게 되는 거죠.

그리고 K호프만큼 특징을 잡아내기 때문에 K호프만큼 로컬라이제이션을 할 수 있게 되는 것이고 이 부분은 앞서서 로컬라이제이션에 대한 개런티가 없다고 했는데 그 부분도 해결을 할 수 있게 되는 거죠.

정리를 하면 첫 번째는 연산량을 N개에서 K개 만큼만 학습을 하면 된다.

학습해야 할 파라미터가 줄게 되고 두 번째가 줄어든 만큼만 로컬라이제이션을 할 수 있기 때문에 인근 노드의 피처를 학습할 수 있다고 생각하시면 됩니다.

의미적으로 살펴봤고 앞서 X 대신 L의 K만큼 된 포뮬레이션을 봤는데 이걸 학습하게 되면 좀 언스테이블하다는 문제점이 있었습니다.

그래서 이것을 안정적으로 학습하기 위해서 체비샤프 폴리노미얼을 바꾸게 되는데요.

이렇게 바꾸면서 이 논문이 체비샤프 랫으로 분리 되었습니다.

그래서 좀 더 안정적으로 학습하기 위해서 체비샤프 폴리노미얼을 바꾸었습니다.

바꿔서 최종적으로 연산을 하게 됩니다.

그래서 이 골이 체비샤프 익스펜션을 통해서 최종적으로 이렇게 표현이 되고 이런 조건을 가지는 포뮬레이션이 됩니다.

그리고 최종적으로 요약된 수식인데요.

이렇게 보시게 되면 아까 봤던 Spectral GCN에서 이 부분, Eigenvector를 곱하는 부분이 사라졌습니다.

사라졌고 학습해야 할 파라미터가 n by n에서 n개의 파라미터였다면 여기서는 k개만큼은 학습을 해야 한다는 특징을 살필 수 있습니다.

앞서 살펴보았던 최종 수식이 체비샤프 랫이고 이것을 간소화한 것이 우리가 알고 있는 일반적인 GCN이라고 보시면 됩니다.

그래서 이 논문에서는 간소화할 때 k, 우리가 n개가 아니라 k개를 보겠다고 한 k를 2로 설정했습니다.

2로 가정을 했고 이런 제약 조건을 추가해서 최종적으로 수식을 쭉 정리를 해보면 이런 수식이 도출이 되는데요.

여기서 한 번 더 가운데 있는 부분을 학습을 안정적으로 하기 위해서 발산하지 않고 잘 수렴시키기 위해서 Renormalization Trick을 썼는데요.

디테일한 부분은 이제 생략을 하고 결론적으로 말씀을 드리면 이걸로 나타나게 됩니다.

이 수식에 대해서 잠깐 살펴보면 입력신호구요.

그 다음 Degree Matrix, Merged Adjacent Matrix, Filter, 학습해야 할 파라미터, 그 다음 Nonlinear Activation Function으로 구성이 되어 있고 앞선 부분과 비교하자면 알젠 벡터가 들어가 있지 않습니다.

그래서 스펙트럴 도메인이 아니라 우리는 스페이셜 도메인에서 연산을 하는 것을 볼 수가 있습니다.

짧게 핵심 위주로 살펴보았는데요.

스펙트럴 도메인에서 스페이셜 도메인으로 넘어가는 과정을 보았습니다.

알젠 벡터를 사용하는 것이 아니라 폴리노미아를 바꾸고 그걸 간소화해서 스페이셜 도메인으로 우리가 계산을 하게 되었다.

정리를 하면 H라는 그래프 입력신호가 있으면 이것을 처음에는 알젠 디컴포지션을 했더라면 하고 필터를 곱해서 풀의 역변환을 했더라면 우리는 이것을 스페이셜 도메인으로 요약할 수가 있다.

더 이상 이 과정을 안해도 된다.

이것만 알게 되면 된다.

라는 결론에 이르렀습니다.

정말 마지막 부분입니다.

앞서 살펴보았던 것은 그래프 시그널이 싱글 채널일 때 1차원일 때를 이야기한 것인데 1차원일 때 수식을 봤을 때는 이렇게 되지만 실제로는 이 노드 피처가 다차원으로 형성이 되어 있기 때문에 대부분은 예를 들어서 4차원이라고 해보겠습니다.

그리고 노드의 개수는 10개라고 하면 이 부분 H 입력신호는 10x4라고 표현할 수가 있습니다.

그리고 이 4차원이 아웃풋 디멘션이 다르기 때문에 예를 들어서 3차원이라고 해본다면 우리가 학습해야 할 파라미터는 4x3 골의 웨이트 매트리스가 됩니다.

그래서 이 부분을 계산을 하면 되는데 지금 이렇게 매트리스 연산을 하게 되면 이 과정 연산하면 10x4가 되는데 10x4와 4x3이 연산이 안됩니다.

그래서 연산을 할 수 있게 이 웨이트가 앞에 있었던 것을 뒤로 넘기면서 m, m 사라지고 n, n, n 사라져서 최종적으로 nxn로 차원으로 나타나게 됩니다.

그래서 입력신호가 다차원일 때를 연산을 하는 행렬폼으로 나타낸 식이라고 보시면 되고요.

아까 얘기했다시피 우리는 k를 2로 쓰기 때문에 두 개의 레이어를 거친 네트워크 스트럭처라고 볼 수 있고 이 식을 최종적으로 요약을 하면 그렇게 나타날 수 있습니다.

이 식에 대해서 어펜딕스의 그림자로 풀이를 해두었는데요.

참고를 하시면 이에 도움이 될 것 같습니다.

이제 정리를 하고 마무리 하겠습니다.

Spectral GCN, Chebyshev Net, Simplified Chebyshev Net까지 총 3개의 논문에 대한 핵심적인 부분을 다뤄보았고요.

각각의 특징은 이렇게 되는데요.

본 슬라이드에 나와있는 수식을 많이 상략하고 설명을 드렸습니다.

그렇기 때문에 수식적으로 이해를 꼼꼼하게 하고 싶으신 분들은 본 슬라이드를 참고하고 뒤에 레퍼런스를 적성을 해두었으니 관련 자료를 좀 찾아보시면서 이해를 해주시면 될 것 같습니다.

Spectral Filtering에 이러한 논문의 핵심 방법론을 거쳐서 우리가 Spatial Filtering까지 오게 되었고요.

Spatial Filtering이 많이 연구가 되고 있고요.

지금은 Graph Sage, Message Passing Neural Network, Graph Attention Network까지 다양한 방법론이 나왔으니까 논문을 살펴보시면 도움이 될 것 같습니다.

그래서 최종 결론입니다.

3가지 챕터를 나눠서 설명을 드렸는데요.

첫번째가 Graph Neural Network와 Graph Data에 대한 특징을 살펴봤습니다.

그래서 Graph Data에 문제점이 있었고 그 문제점을 해결하고자 Chapter 2의 Convolutional Theorem 그리고 Convolutional Theorem에 나오는 Fourier Transformation, 그리고 Fourier Transformation을 Graph에 접목시키기 위해서 라플라시안 아이겐 벡터가 나왔고 그 아이겐 벡터를 곱해 주는 것이 Spectral Graph Convolution의 내용에 해당이 된다.

그래서 최종적으로 Graph Convolution을 어떻게 하는지를 Spectral Graph Convolution 관점에서 이해를 할 수 있었고요.

마지막으로 Chapter 3에서 Spectral Graph Convolution을 적용한 다양한 네트워크에 대해서, 메소러지에 대해서 살펴봤습니다.

3개를 말씀드렸는데요.

이 부분에 대해서는 정말 심플하게 설명을 하고 넘어갔습니다.

그래서 이 논문의 핵심 개념에 대해서 디테일하게 알고 싶은 분들은 뒤에 레퍼런스라든지 어펜딕스, 그리고 본 세미나 슬라이드도 참고를 해주시면 될 것 같습니다.

우리가 여기까지 걸어온 길은 Spectral에서 Spatial로 넘어왔을 뿐이고요.

본격적으로 GNN을 학습한다고 하면 Spatial에서 험난한 여정을 시작해야 합니다.

이 점점점에 해당이 되는데요.

관심 있으신 분들은 뒷단어 공부도 한번 해보시면 좋을 것 같습니다.

세미나가 너무 길어져 버렸는데요.

끝까지 경청해주셔서 대단히 감사합니다.

---

SUMMARY

DMQA 7월 15일 세미나는 그래프 뉴럴 네트워크 스펙트럴 그래프 컨볼루션의 기본 개념 및 응용 분야를 다룹니다.

발표자는 데이터 마이닝 퀄리티 앤널리틱스 랩 석사과정 재학생이며, 관심 연구 분야는 그래프 뉴럴 네트워크와 히몬포지 이스티메이션입니다.

세미나 내용은 스펙트럴 GNN을 알기 위한 기본적인 백그라운드 및 그래프 구조, 그리고 다양한 응용 분야를 다룹니다.

DMQA 7월 15일 오픈 세미나는 그래프 뉴럴 네트워크의 스펙트럴 그래프 컨볼루션의 기본 개념과 응용 분야를 다룰 예정이며, 발표자는 데이터 마이닝 퀄리티 앤널리틱스 랩 석사과정 재학생이며, 관심 연구 분야는 그래프 뉴럴 네트워크와 히몬포지 이스티메이션입니다.

세미나는 기본 개념 및 응용 분야를 다룰 예정이며, 다양한 응용 분야로 활용되고 있는 그래프 뉴럴 네트워크를 소개합니다.

생명과학 및 화학 도메인에서 그래프 신경망(GNN)을 활용하여 분자 구조를 예측하고, 그 분자가 효능이 있는 약이 될 수 있는지를 예측하는 연구가 이루어지고 있습니다.

이를 위해 그래프는 노드와 엣지로 구성되고, 인접행렬을 통해 노드 간 연결관계를 표현하고, 방향성이 있는 directed graph 혹은 방향성이 없는 undirected graph로 나타내고, 가중치가 있으면 weighted graph, weight가 없으면 unweighted graph로 나타내며, 각 노드의 degree를 통해 노드 간 연결관계를 나타내고 있습니다.

그래프 데이터는 이러한 Euclidean domain에서 나타날 수 없는 것들입니다.

따라서 그래프 데이터는 degree, laplacian matrix를 기반으로 표현됩니다.

Degree matrix는 대각 행렬로 나타내며, 나머지 부분은 0으로 나타나며, degree matrix에서 adjacent symmetrics를 뺀 값이 laplacian matrix가 됩니다.

Laplacian matrix는 중심 node와 이은 node 사이의 관계를 나타냅니다.

그래프로 수행하는 task는 그래프 단계, edge 단계, node 단계로 나눌 수 있습니다.

그래프 데이터는 Euclidean domain에서 표현할 수 없기 때문에 degree, laplacian matrix를 기반으로 표현됩니다.

Degree matrix는 대각 행렬로 표현되고, laplacian matrix는 중심 node와 이은 node 사이의 관계를 나타냅니다.

그래프로 수행하는 task는 그래프 단계, edge 단계, node 단계로 나눌 수 있습니다.

그래프 데이터는 Euclidean domain에서 표현할 수 없기 때문에 degree, laplacian matrix를 기반으로 표현됩니다.

Degree matrix는 대각 행렬로 표현되고, laplacian matrix는 중심 node와 이은 node 사이의 관계를 나타냅니다.

그래프로 수행하는 task는 그래프 단계, edge 단계, node 단계로 나눌 수 있으며, 각 단계에서 예측을 하는 것이 목적입니다.

이러한 그래프 데이터

격자로 나타낼 수 있는 데이터는 이미지, 문장, 단어, 음성 데이터 등이 있으며, 이 데이터는 필터 크기만큼 이미지 패치의 연산을 거치면서 컨볼루션 연산을 할 수 있게 됩니다.

이때 필터, 템플릿 내에 있는 노드의 위치는 변하지 않고 같은 정보를 다른 이미지 패치에 매칭할 수 있게 됩니다.

이미지와 신호에서 공통적으로 사용하는 컨볼루션 정리는 두 함수의 컨볼루션을 해서 풀이의 변환을 하는 것과 동일하다는 내용이다.

그래프에 이 컨볼루션 정리를 접목시키면 그래프에서도 컨볼루션을 할 수 있게 된다.

풀이의 변환은 입력 신호를 다양한 주파수를 갖는 주기함수들의 합으로 분해하는 과정이다.

FT가 필터가 되고, GT가 시그널이 되는데, 이를 중첩하면 생기는 값이 컨볼루션 연산의 결과값이 된다.

풀이의 변환을 통해서 이 값들을 다양한 주파수를 갖는 주기함수들의 합으로 분해하고, 그 다음에 다시 역변환을 해서 다시 컨볼루션을 하는 방식으로 그래프에서 컨볼루션 연산을 가능하게 하는 방법에 대해 설명하는 것입니다.

풀이의 변환은 입력신호를 사인코사인 주기함수의 합으로 분해하는 과정으로, 이미지는 공간축, 전판음성신호는 시간축의 정의된 신호로 볼 수 있고, 그래프에서는 노드가 갖는 값으로 볼 수 있습니다.

이를 통해 다양한 주파수를 갖는 주기함수들의 합으로 분해하고, 역변환을 해서 컨볼루션 연산을 할 수 있게 하는 방법에 대해 설명합니다.

컨볼루션 연산은 교환법칙을 만족하는 연산으로 동일한 Eigenvector를 가지는 것이다.

이렇게 컨볼루션 연산은 특정 입력 신호에 대해 회전 횡렬을 곱하고 교환법칙을 만족하며 동일한 Eigenvector를 가지는 연산으로 새로운 Feature 값을 얻는 것이다.

모든 회전 횡렬은 교환법칙을 만족하기 때문에 동일한 Eigenvector를 가지고 고유값 분해를 하면 이상 Fourier 변환에서 basis와 동일한 결과가 나오며, 이를 통해 컨볼루션 연산은 회전 횡렬로 표현이 가능하며, 그리고 입력 신호에 Fourier 변환은 회전 횡렬의 Eigenvector와 동일하다는 것을 알 수 있습니다.

All rotation matrices satisfy the exchange law, thus all have the same Eigenvectors.

Therefore, for the simplest rotation matrix, a rotation of one space to the right, Eigen decomposition yields the same Eigenvectors as the Discrete Fourier Transformation and the Fourier transform.

This implies that convolution can be represented by rotation matrices, and that Fourier transforming an input signal is the same as multiplying the input signal by the Eigenvectors of the rotation matrix.

Multiplying two of these together is the same as a Fourier transform and applying a filter with weights abc is the same as the Eigenvalue of a rotation matrix.

Multiplying the Eigenvectors together yields the inverse Fourier transform.

This implies that Fourier transforming an input signal is the same as rotating the input signal's black axis by theta, and convolving is the same as rotating.

Therefore, Fourier transforming an input signal is the same as multiplying the input signal by the Eigenvectors of the rotation matrix. Fourier 변환을 한다는 것은 Eigen decomposition을 해서 회전 횡렬의 Eigenvector로 곱하는 것과 동일한 의미를 가지는데, 그 사실을 바탕으로 스펙트럴 컨볼루션을 할 수 있게 됩니다.

모르는 값은 회전 횡렬의 Eigenvalue 값이고, 이것을 최종적으로 학습할 파라미터로 삼고, Fourier 변환에서 Fourier basis는 고정된 값이라는 것을 알고 있으면 됩니다.

Non-grid 그래프에서는 Adjacency Matrix를 Eigenvector로 찾고, 이것의 Eigen decomposition이 되지 않으면 Laplacian Matrix를 사용하여 해결할 수 있습니다.

Fourier 변환은 Eigen decomposition을 해서 회전 횡렬의 Eigenvector로 곱하는 것과 동일한 의미를 가지며, 이를 바탕으로 스펙트럴 컨볼루션을 할 수 있게 됩니다.

모르는 값은 회전 횡렬의 Eigenvalue 값이며, 이것을 최종적으로 학습할 파라미터로 삼고, Fourier 변환에서 Fourier basis는 고정된 값입니다.

Non-grid 그래프에서는 Adjacency Matrix를 Eigenvector로 찾고, 이것의 Eigen decomposition이 되지 않으면 Laplacian Matrix를 사용하여 해결할 수 있습니다.

Laplacian Matrix를 Eigen decomposition하여 Eigenvector를 곱하는 과정을 거쳐 그래프 풀의 트랜스포메이션을 하고 필터를 학습하여 입력신호를 스펙트럴 도메인으로 변환하여 컨볼루션을 수행하는 Spectral Convolution을 이용하여 그래프 데이터에서 컨볼루션 연산을 수행할 수 있게 되었습니다.

Laplacian Matrix를 Eigen decomposition하여 Eigenvector를 곱하는 과정을 거쳐 그래프 풀의 트랜스포메이션을 하고 필터를 학습하여 입력신호를 스펙트럴 도메인으로 변환하여 컨볼루션을 수행하는 Spectral Convolution을 이용하여 그래프 데이터에서 컨볼루션 연산을 수행할 수 있게 되었습니다.

일반적인 템플릿 매칭이라고 하는 다프로덕트하는 컨볼루션 연산이 그래프 데이터에서 할 수 없기 때문에, 컨볼루션 정리를 사용하여 Laplacian Matrix를 Eigen decomposition하고 필터를 학습하고 스펙트럴 도메인으로 변환하여 컨볼루션을 수행하는 과정을 거쳐 그래프 데이터에서 컨볼루션 연산을 수행할 수 있게 되었습니다.

Spectral Graph Convolution은 풀의 변화를 라플라이시안 행렬의 Eigenvector를 곱하는 것과 동일하게 계산하여 도메인 변환을 통한 로컬라이제이션을 수행하고 연산량을 줄이고 한계점을 극복하기 위해 논문이 제시됐으며, GNN, GCN 공부를 하면 가장 많이 접하는 논문으로 필터의 풀이의 변환을 학습하는 것이 핵심이다.

Spectral Graph Convolution은 풀의 변화를 라플라이시안 행렬의 Eigenvector를 곱하는 것과 동일하게 계산하여 도메인 변환을 통한 로컬라이제이션을 수행한다.

이를 통해 연산량을 줄이고 한계점을 극복하기 위해 논문이 제시되었으며, 필터의 풀이의 변환을 학습하는 것이 핵심이다.

그리고 GNN, GCN 공부를 하면 가장 많이 접하는 논문이다.

즉, M by N의 필터를 학습시키는데 여러 레이어를 거치면서 학습하는 대신, 폴리너미얼 파라미터 리제이션을 사용하여 학습할 파라미터를 줄이고, 아이젠 디컴포지션 없이도 학습할 수 있는 방법을 찾았다는 것.

M by N의 필터를 학습시키기 위해 로컬라이제이션이 잘 되는지 보장할 수 없고, 그리고 학습해야 할 파라미터가 너무 많은 문제가 있었다.

그래서 폴리너미얼 파라미터 리제이션을 사용하여 파라미터를 줄이고, 아이젠 디컴포지션 없이도 학습할 수 있는 방법을 찾았다.

라플라시안은 인근 노드의 피처를 학습할 수 있는 스페이셜 도메인을 뜻합니다.

K호프만큼 특징을 잡아내고 이를 통해 로컬라이제이션을 할 수 있게 됩니다.

이 부분은 체비샤프 폴리노미얼을 바꾸게 되어 안정적으로 학습할 수 있게 되고, 학습해야 할 파라미터는 n개에서 k개로 줄어들게 됩니다.

이것은 스펙트럼 도메인 대신 스페이셜 도메인으로 변화하고 알젠 디컴포지션을 하지도 않고 알젠 벡터를 곱하지도 않기 때문에 완전히 스페이셜 도메인이라고 볼 수 있습니다.

이 논문에서는 GCN을 간소화하기 위해 k개의 제약 조건을 추가하고, Renormalization Trick을 사용하여 학습을 안정적으로 하고 스펙트럴 도메인에서 스페이셜 도메인으로 연산하는 과정을 보았다.

H라는 그래프 입력신호가 있으면 이것을 알젠 디컴포지션과 필터를 곱하고 스페이셜 도메인으로 요약할 수 있다.

노드 피처가 다차원으로 형성되어 있기 때문에 앞에 있는 값이 뒤로 넘기면서 m, m 사라지고 n, n, n 사라져서 최종적으로 nxn로 차원으로 나타난다.

Spectral GCN, Chebyshev Net, Simplified Chebyshev Net이라는 3개의 논문에 대한 핵심적인 부분을 설명하였습니다.

각각의 특징은 이렇게 되는데, 이 식을 최종적으로 요약하면 그렇게 나타날 수 있습니다.

이 논문의 핵심 개념에 대해서 디테일하게 알고 싶은 분들은 뒤에 레퍼런스라든지 어펜딕스, 그리고 본 세미나 슬라이드도 참고해주시면 될 것 같습니다.

Spectral GCN, Chebyshev Net, Simplified Chebyshev Net이라는 3개의 논문에 대한 핵심적인 부분을 설명하였고, 이 논문의 핵심 개념에 대해서 디테일하게 알고 싶은 분들은 뒤에 레퍼런스라든지 어펜딕스, 그리고 본 세미나 슬라이드도 참고해주시면 될 것 같습니다.