Graph Neural Network, Convolutional GNN
Published on December 17, 2022 by JunYoung
AI deep learning graph neural networks
18 min READ
우리가 지금까지 봐왔던 전반적인 모델들의 특징은, 따로 설명하지는 않았지만 데이터셋 전체에 대해 i.i.d(independent and identically distribution)을 가정한다. 즉 어떠한 modality에 대해 얻어진 데이터셋 각각은 서로 독립적으로 존재하며, 어떠한 추론 과정에서도 다른 데이터셋에 의한 영향을 받지 않는다는 의미가 된다. 이번에 살펴볼 graph를 통한 neural network의 접근은 이와 차이가 있다.
위의 그림에서 보이는 것과 같이 Graph란 개별적인 vertices 혹은 nodes(점)과 각각을 잇는 edges(선)으로 이루어져있다. Node/Vertex는 각각의 item이나 entity를 나타내고 edge는 그들 간의 관계를 나타낸다.
어떠한 domain $R$ 위에 정의된 유클리드 함수 $f : R \rightarrow \mathbb{N}$은 다음과 같은 성질을 만족해야한다. [ \begin{aligned} \text{임의의 }&a\in R \text{ 및 }b \in R \text{에 대하여,} \newline &a = bq+r \newline \text{이며, }&r = 0 \text{ 또는 }f(r) < f(b)>인 q, r \in R \text{가 존재한다.} \end{aligned} ] 여기서 유클리드 정역은 위와 같은 유클리드 함수가 적어도 하나 존재하는 정역이라고 생각하면 된다. 사실 위의 내용만 보면 어려운 말이 많아서 바로 이해가 가질 않는데, 유클리드 정역에 놓일 수 있는 데이터셋의 예시를 보면 크게 어렵지 않다.
위와 같은 이미지는 2D grid 상의 데이터로 표현될 수 있다. 2D grid는 유클리드 정역의 대표적인 예시이므로(우리가 흔히 볼 수 있는 좌표계는 모두 해당된다고 생각하면 된다) 유클리드 정역의 데이터라고 말할 수 있다. 마찬가지로 어떠한 문장이나 음성 신호를 token화하고 이를 embedding으로 처리하는 것 모두를 1D grid 상에서의 유클리드 정역이라고 볼 수 있다.
그러나 그래프 구조는 유클리드 정역이 될 수 없다. 이를테면 각 face의 vertex와 edge로 이어지는 3D mesh 구조도 이러한 비유클리드 정역의 데이터 중 하나며, SNS와 같이 유저와 유저와의 관계로서 정의되는 network 구조도 마찬가지이다. 인스타그램을 예로 든다면, 유저 A, B, C, … 등등에 대해 ‘서로 친구인 관계’, ‘친한 친구인 관계’, ‘DM을 자주 보내는 사이’, ‘친구도 아닌데 DM을 보내는 사이’ 등등 서로간의 관계로 정의가 되며, 각 유저에 대해서는 ‘비공개 계정’, ‘공개 계정’, ‘스토리를 자주 올리는 계정’ 등등 다양한 property를 가질 수 있다.
다른 데이터로는 pose estimation에서 사용되는 structure를 예시로 들 수 있다. 이렇듯 grid에 놓일 수 없는 비-유클리드 데이터의 특징으로는 각 점들간의 관계로 정의되는 모든 modality를 상상해볼 수 있다.
앞으로 이런저런 내용들을 설명함에 있어 짚고 넘어가야할 여러 notation 정의들에 대해 먼저 살펴보도록 하자.
Vertex의 특징 벡터란, 해당 노드가 가지고 있는 property를 의미한다. 특징 벡터에는 vertex의 번호(인덱스), 사람에 대한 정보를 예시로 들게 되면 해당 노드가 가지는 이름이나 국적 그리고 나이를 포함할 수 있다.
그래프에 대한 또다른 사전 정의로는 연결성에 대한 representation이 될 수 있다.
[ D = \begin{bmatrix} 2 & 0 & 0 & 0 & 0 & 0 \newline 0 & 3 & 0 & 0 & 0 & 0 \newline 0 & 0 & 2 & 0 & 0 & 0 \newline 0 & 0 & 0 & 3 & 0 & 0 \newline 0 & 0 & 0 & 0 & 3 & 0 \newline 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}
] 우선 $D$의 경우에는 $d_{i, j},~(i = j)$ 요소만 있는 diagonal matrix로, 각 요소들의 의미하는 것은 각 노드와 연결되어있는 다른 노드의 개수가 된다.
[ A = \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 \newline 1 & 0 & 1 & 0 & 1 & 0 \newline 0 & 1 & 0 & 1 & 0 & 0 \newline 0 & 0 & 1 & 0 & 1 & 1 \newline 1 & 1 & 0 & 1 & 0 & 0 \newline 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix}
] 그리고 $A$의 경우에는 $a_{i,j}$ 요소가 의미하는 바가 $i$번째 vertex와 $j$번째 vertex의 연결성 유무$(0/1)$이다. 따라서 위의 matrix는 보는 바와 같이 대칭 구조(symmetric matrix)를 가진다. [ L = \begin{bmatrix} 2 & -1 & 0 & 0 & -1 & 0 \newline -1 & 3 & -1 & 0 & -1 & 0 \newline 0 & -1 & 2 & -1 & 0 & 0 \newline 0 & 0 & -1 & 3 & -1 & -1 \newline -1 & -1 & 0 & -1 & 3 & 0 \newline 0 & 0 & 0 & -1 & 0 & 1 \end{bmatrix}
] edge가 weighted되지 않은 graph에 대해서 non-normalized Laplacian은 단순히 degree 행렬에서 adjacent 행렬을 빼면 된다. 이외에도 다양한 형태의 라플라시안 행렬이 정의될 수 있다.
Graph neural network(GNN)이란 그래프를 처리하기 위한 학습 구조이며, training 및 evaluation 과정에서 그래프 구조가 neural network에 들어가게 된다. 이때, 그래프의 vertices나 edges가 가변적이므로 구조적으로 이를 제한하지 않으며, 가장 중요한 건 GNN 구조는 structured, Euclidean domain의 데이터를 처리할 수 있으면서도 동시에 non-Euclidean domain의 데이터를 처리할 수 있다는 것이다.
GNN은 기존 Neural Network에서의 MLP(Multilayer Perceptron)와 동일하며, GNN이 하고자 하는 것인 여러 번의 feature extraction를 통해 그래프로부터 유의미한 high level feature representation을 얻고자하는 것이다. 이렇게 획득된 high level feature representation은 우리가 흔히 알고있는 deep learning framework의 decoder output과 같다.
즉 다시 말해서 GNN의 목표는 크게 두 가지로 정의될 수 있다.
각 vertex $v_i$의 인접 노드를 생각해보자. 이를 위에서 언급하기로 $ne(v_i)$로 나타내었다. 이러한 neighborhoods를 가지고 타겟이 되는 노드의 hidden representation을 구해야 한다. 물론 각 vertex마다 neighbor의 개수가 다르기 때문에, transition process는 neighbors of vertex $ne(v_i)$의 aggregation(요약본)을 구하는 것과 같다. 이렇게 하면 각 vertex에 대해 동일한 크기의 hidden feature vector를 구할 수 있다. Vertex $v_i$의 $k$번째 state에서의 hidden state $h$ 혹은 embedding은 다음과 같이 formulation된다.
[ h_i^k = \sum_{j \in ne(v_i)} f(v_i^F, e_{i,j}^F, v_j^F, h_j^{k-1}), \text{Where all }h_i^0 \text{ are defined upon initiallization}
]
위의 식을 보면 알 수 있듯이 formulation에서의 aggregation은 summation으로 나타내어지고, 함수는 ‘hidden state를 구하고 싶은 vertex의 feature’, ‘hidden state를 구하고 싶은 vertex와 인접한 vertex의 feature’, ‘그 사이의 관계를 나타내는 edge feature’, ‘인접한 vertex의 hidden state’를 input으로 삼는다. 식을 천천히 보다보면 왜 Vertex 자기 자신의 이전 hidden state를 input으로 가지지 않을까라는 의문이 생겼는데, 그건 formulation을 단순히 위와 같이 했기 때문이라고 한다. 아마 구체적인 formulation은 각 상황에 맞게 달라질 수 있지 않을까 생각했다. 위에서의 $f$는 non-linear transformation 구조를 가진다. Activation function을 가지는 단순하게 구성된 MLP를 생각하면 된다.
이렇게 정의된 transition 과정에서의 $k^{th}$ state란,
노드들은 각 레이어에서 $v_i^F$를 가지고 있을 것이고, $0^{th}$ state란 0번째 레이어에서 각각의 vertex $A = v_A^F$가 가지는 hidden state $h_A^0$가 된다. 이런 맥락으로 쭉 이어가다보면, $n$번째 state에서는 타겟이 되는 vertex와 $n$ 만큼 가까운 vertex들의 정보들을 aggregation(요약)한 형태가 된다. 따라서 GNN transition에서의 stage는 곧 '얼마나 멀리 있는 vertex의 정보까지 활용하여 현재 vertex의 state를 나타내었는가'에 대한 지표가 된다.
여기서 $k$는 임의의 큰 숫자도 가능하며, 일반적으로 transition function $f$를 반복적으로 적용하여 $k^{th}$ state가 안정적인 상태에 들어갈 때까지 연산하게 된다.
안정적인 상태에 접어들 때까지 $k$번 function $f$를 적용하고 나면 graph에는 연산된 feature vector가 implicit하게 존재하게 된다. Output function은 이렇게 수렴된 hidden state를 사용하여 유의미한 output을 뽑아내는 연산 과정이다.
유의미한 output은 vertex-level, edge-level 그리고 graph-level 이렇게 세가지로 구분될 수 있다. 각각이 적용될 수 있는 task가 조금씩 다르다고 보면 된다.
가장 먼저 vertex level framework는 output value를 내보내기 위해 오직 vertex 정보만 사용하게 된다. 따라서 해당 구조에 요구되는 인자는 오직 vertex의 feature vector($v_i^F$)와 hidden state information($h_i^{kmax}$)가 된다. [ o_i = g(v_i^F,~h_i^{kmax})
]
주로 활용될 수 있는 task는 몇몇 노드에 labeling이 되어있지 않은 경우 주변 노드들을 활용하여 labeling을 하는 node classification이나 regression이다.
두번째로 edge level framework에서는 output value를 내보내기 위한 input으로 총 다섯 개의 정보가 필요하다. 하나의 Edge는 우선 두 개의 vertex와 연결되어있기 때문에 두 개의 vertex에 대한 feature vector($v_i^F$, $v_j^F$) 그리고 hidden state($h_i^{kmax}$, $h_j^{kmax}$)가 필요하며, 그와 함께 edge 자체의 feature vector($e_{ij}^F$)도 필요하다. [ o_i = g(v_i^F,~h_i^{kmax},~v_j^F,~h_j^{kmax},~e_{ij}^F) ]
주로 활용될 수 있는 task로는 각 edge를 분류하는 작업(edge classification)이 될 수도 있고(관계에 대한 분류라고도 볼 수 있음), 이를 보다 확장시켜 생각하면 link prediction에도 활용될 수 있다. Link prediction이란 두 node가 미래에 유의미한 관계를 가질 수 있을지에 대한 내용으로 흔히 Amazon과 같은 온라인 마켓에서 물건을 구매하기 시작하면 이후에 내가 관심가질만한 품목들을 추천해주는 것과 같다. 이외에도 컨텐츠 추천이 가능한 다양한 플랫폼에서 활용될 수 있다.
세번째로 graph level framework에서는 output value를 내보내기 위한 input으로 네트워크 전반에 대한 정보를 활용한다. 물론 그래프의 모든 정보를 가질 필요는 없지만 final hidden state of vertices or edges 혹은 initial state도 선택에 따라 활용할 수 있다.
주로 활용되는 task로는 위와 같이 서로 다른 그래프에 대해 어떠한 집단인지 분류하는 graph classification이 될수도 있으며,
Euclidean domain의 데이터인 이미지의 각 픽셀에 대한 graph를 학습한 뒤에 이를 토대로 분류할 수도 있다.
앞서 보았던 식은 단순히 $f$, $g$로 각 transition 및 output에 대한 함수를 표현했고, 구체적으로 neural network에서는 이를 어떠한 방식으로 수식전개를 했는지 나타내지는 않았다.
Neural network에서는 preceptron의 정의에 따라 학습 가능한 parameter를 가지는 weight와 bias를 통해 next state에 대한 affine을 연산하고, 이 결과에 non linear activation을 통해 여러 layer를 통과했을 때 연산의 complexity를 높이는 방식이다. [ \begin{aligned} h_v^0 =& x_v \newline h_v^k =& \sigma\left( W_k \sum_{u \in N(v)} \frac{h_u^{k-1}}{\vert N(v) \vert} \right),~\forall k \in (1, \cdots, K) \newline z_v =& h_v^K \end{aligned} ] 위의 수식에서 볼 수 있듯, $k$번째 state($h_v^k$)를 구하고 싶은 vertex($v$)의 인접한 vertex($u$)의 $k-1$번째 hidden state($h_u^{k-1}$)를 평균을 통해 aggregation을 하고, 이를 k번째 weight term $W_k$에 곱한다. 그리고 나서 vertex $v$의 $k-1$번째 hidden state $h_v^{k-1}$에 k번째 bias term $B_k$를 곱해서 더하고, 이 전체 연산 결과에 activation function을 적용하는 구조가 된다. [ \begin{aligned} H^{(l+1)} =& \sigma(H^{(l)}W_0^{(l)}+\tilde{A}H^{(l)}W_1^{(l)}) \newline \text{with } \tilde{A} =& D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \end{aligned}
] 위와 같이 vector form으로도 표현 가능하다. 이렇게 구해진 hidden state 혹은 embedding을 loss function을 활용하여 학습 가능한 weight 및 bias parameter에 대해 gradient based optimization이 가능하다.
이렇게 학습된 neural network를 통해 embedding space로의 변환이 가능하다. Node를 vector로 보내는 변환이 될 수도 있고 graph의 일부 구조(substructure)를 vector로 보내는 변환이 될 수도 있으며 graph structure 자체를 vector로 변환할 수도 있다. Embedding mapping의 퀄리티를 측정하는 주요 방법은 기존에 그래프 구조에서 가지고 있는 similarity(node간의 유사성 등)을 $d$ dimensional embedding space에서 유지할 수 있는지 보는 것이다. 추출된 embedding은 다양한 downstream task에서 활용될 수 있다.
앞서 계속 풀었던 내용은 Graph 구조를 어떤 방식으로 neural network를 통해 inference할 수 있는지에 대한 부분이고, 지금부터 살펴볼 내용은 이를 어떤 방식으로 convolutional 구조를 사용하여 해결할 수 있는지에 대한 부분이다. CGNNs라 불리는 convolutional GANN은 두 가지의 type으로 정의할 수 있는데, 첫번째는 spatial domain, 그리고 두번째는 spectral(frequency) domain이다.
예를 들어 다음과 같은 그래프 구조를 가지는 숫자 이미지를 생각해보자,
이미지는 graph를 특별하게 구성한 형태로 가정하고, 여기에 convolution 연산을 하는 것은 정해진 크기의 filter($3 \times 3$)를 input에 대해 곱한 뒤 aggregation을 하는 것과 같다. 그런 뒤 filter를 shift하여 같은 과정을 반복한다.
여기서 알 수 있는 사실은 단순히 convolution 연산을 image와 같은 modality에 적용할 수 있지만 spatial order를 가지는 다른 graph를 적용하기 힘들다는 문제와, Grid 구조에 맞게 설계가 된 이미지와는 다르게 vertex neighbors가 달라질 수 있는 non-Euclidean domain dataset에는 균일한 형태로 aggregation이 힘들다는 것이다.
위의 그림을 예시로 보면, R, G, B의 색을 가지는 target vertex와 각각의 neighborhoods로 정의된 dotted box가 있다. Spatial convolution에서는 neighborhood가 선택되고 해당 vertices들의 feature vector가 aggregate된다. 그리고 이렇게 aggregate된 value는 target vertex의 다음 embedding을 결정하는 요소로 사용된다. 이러한 process는 graph의 모든 neighborhoods에 대해서 반복된다. 이렇게 구해진 embeddings는 다음 layer의 spatial convolution에 활용될 수 있는 value가 된다. 따라서 hierarchical feature extraction이 가능하다. 이를 정리해서 순서로 나타내면,
GraphSAGE 논문에서는 node에 대한 embedding을 추출하고, node attribute information이 풍부한 경우에 사용되었다.
결국 GNN에서의 aggregation식과 거의 유사하게 작동하는 것을 확인할 수 있다. Sptial CGNN에서 활용되는 다양한 aggregator는 다음과 같다.
| Variant | Aggregator | Updator |
|---|---|---|
| Neural FPs | $h_{\mathcal{N_v}}^t = h_v^{t-1}+\sum_{k=1}^{\mathcal{N_v}}h_k^{t-1}$ | $h_v^t = \sigma(h_{\mathcal{N_v}}^t W_L^{\mathcal{N_v}})$ |
| DCNN | Node classification: $N = P*X$ Graph classification: $N = 1_N^T P*X/N$ | $H = f(W^c \odot N)$ |
| GraphSAGE | $h_{\mathcal{N_v}^t} = \text{AGGREGATE}_t(h_u^{t-1}, \forall u \in \mathcal{N_v})$ | $h_v^t = \sigma(W^t \cdot (h_v^{t-1} \parallel h_{\mathcal{N_v}}^t))$ |
이러한 CGNN이 기존 GNN과 비교해서 다른 점은 다음과 같다. GNN의 경우 embedding이 stable한 value를 가질 때까지 transition function $f$를 반복해서 적용하였다. 따라서 앞서 표현했던 바와 같이 $h_v^{kmax}$까지 최적화가 진행된다. 그와는 다르게 CGNN은 고정된 수의 layer를 가지게 되고, 보통 간단하게 업데이트될 때 단일 layer를 가지게 된다($k = 2$).
Spectral domain이란 주파수를 의미한다. 흔히 시간에 대한 temporal information이 주어진 음성과 같은 신호에 대해서는 주파수를 생각해보기가 쉽다. 왜냐하면 소리가 들리는 방식이 흔히 우리가 알고 있는 것과 같이 공기(매질)의 진동을 통한 정보 전달이며, 이를 주파수 영역에서 분석하기 위해 fourier transform($\mathcal{F}$)을 하는 것이 일반적이다. 그러나 이미지에서도 이처럼 convolution을 적용한 형태의 spectral을 활용할 수 있다.
이미지를 fourier transform하게 되면 주파수 영역에서는 convolution 연산이 multiplication이 된다. [ \mathcal{F}(f * g) = \mathcal{F}(f) \times \mathcal{F}(g)
] 이러한 background를 기반으로 그래프 신호에 대해 논의해보도록 하자.
그래프에서의 신호는 곧 모든 vertex에 대해 매핑된 embedding이 real value를 가질 경우에 정의될 수 있다. 여기서 함수 $f$가 특정 vertex를 기준으로 $f: V \rightarrow \mathbb{R},~\forall V \in G$라면, 곧 이 함수가 신호가 된다. 해당 함수를 통해 모든 vertex는 $N$ 크기의 vector(여기서 $N$은 vertex의 개수를 의미)로 표현되며, $i^{th}$ 요소는 곧 vertex $v_i$의 signal value이다. 여기서 $f$는 앞서 말했던 것과 같은 neural network는 아니고 단순히 각 vertex에 대한 feature map이라고 보면 된다.
라플라시안 연산자($\Delta$)는 2차 gradient($\nabla^2$)를 의미한다. graph signal $f$가 있고, 여기서 구할 수 있는 gradient는 다음과 같다. [ \nabla f(i) = (f(i+1)-f(i))/\delta
] 여기서의 $\delta$와 $i$는 각각 vertex의 index($i,~j$)와 edge weight(w)로 바꿀 수 있다. [ \nabla f(i,~j) = (f(i)-f(j))w(i,~j) ] 그렇게 되면 Laplacian은 다음과 같이 정의될 수 있다. [ \begin{aligned} \Delta f(i,~j) =& \sum_j \frac{\partial^2 f(i)}{\partial j^2} \newline \Delta f(i,~j) \simeq& \sum_{j \in \Omega_i} (f(i)-f(j))w(i,~j) \end{aligned} ] 이를 조금 더 전개해서 matrix form에 대해서 나타내면, [ \begin{aligned} \Delta f(i,~j) =& \sum_j \frac{\partial^2 f(i)}{\partial j^2} \newline \simeq& \sum_{j \in \Omega_i} (f(i)-f(j))w(i,~j) \newline =& (\sum_j w_{ij})f(i) - \sum_j w_{ij}f(j) \newline =& (Df)_i - (Wf)_i = ((D-W)f)_i \end{aligned} ] 앞서 notation에서 설명했던 Laplacian operator에 대해서 graph Laplacian이 degree matrix와 adjacency(혹은 weight) matrix로 표현될 수 있는 이유가 된다.
위에서 얻은 $L$에 대해 eigendecomposition을 진행하면 $L = U\Lambda U^\top$로 표현되며, 여기서 eigenvectors $u_i,~i=0,\cdots,N$은 graph $G$의 fourier bases가 되고 eigenvalues $\lambda_i,~i=0,\cdots,N$은 graph의 frequency components가 된다. 이렇게 표현할 수 있게 되면 graph signal $f$에 대한 푸리에 변환($f \rightarrow \hat{f}$)과 그 역변환($\hat{f} \rightarrow f$)은 각각,
[ \begin{aligned} \hat{f} =& U^\top f \newline f =& U\hat{f}
\end{aligned} ]
위와 같이 표현 가능하고 해당 내적을 각각의 fourier bases에 대해 표현하면,
[ \begin{aligned} \hat{f} =& U^\top f = \sum_{i=1}^N f(i) u_k^*(i) \newline f =& U\hat{f} = \sum_{k=1}^N \hat{f}(k) u_k(i)
\end{aligned} ] 위와 같다. 그리고 앞서 background로 짚고 넘어온 내용 중에, vertex에서의 multiplication은 frequency domain에서 convolution과 같다는 것이 있었다. 원래는 spatial domain에서의 convolution이 frequency domain에서의 multiplication이 된다는 내용인데, duality에 의해 반대도 성립하는 것이다.
[ (\hat(f) * \hat{g})(i) = \sum_{k=1}^N \hat{f}(k) \hat{g}(k) u_k(i)
] 이를 이용하여 임의의 filter $g$를 정의만 할 수 있다면, 다음과 같이 hidden channel 연산이 가능해진다. Filter $g$ 대신 학습 가능한 weight $\Theta$로 생각한다면,
[ \begin{aligned} H_j^k =& \sigma(\sum_{i=1}^{f_{k-1}} U(\Theta^k(U^\top H_i^{k-1}))), \newline \text{where }j =& 1,2, \cdots, f_k \end{aligned}
]
해당 식을 다음과 같은 그래프에 대해서 적용해보도록 하자.
총 vertex의 개수 $N = 5$, edge의 개수 $M = 5$이며 각 vertex에서 처리할 graph signal의 개수 $f_k = 2$이다. 여기서 $k$는 레이어 인덱스이다. 위의 그림에서 보이는 feature vector는 초기 상태를 의미한다. 따라서,
[ H^0 = \begin{bmatrix} 0.2 & 8 \newline 0.4 & 6 \newline 0.3 & 7 \newline 0.3 & 12 \newline 0.1 & 4 \end{bmatrix} ] 위와 같이 나타낼 수 있다. 업데이트할 각각의 column $H^k_1$ 그리고 $H^k_2$에 대해서,
[ H^0_1 = \begin{bmatrix} 0.2 & 0.4 & 0.3 & 0.3 & 0.1 \end{bmatrix}^\top ]
[ H^0_2 = \begin{bmatrix} 8 & 6 & 7 & 12 & 4 \end{bmatrix}^\top ]
[ \begin{aligned} H_j^k =& \sigma(\sum_{i=1}^2 U(\Theta^k(U^\top H_i^{k-1}))), \newline \text{where }j =& 1,2 \end{aligned} ] 위와 같이 표현된다.그러나 위의 식을 보면 알 수 있듯이, graph의 구조에 따라 eigen-system을 계산해야한다는 문제가 있다. 그렇기 때문에 $1^{st}$ generation of spectral CGNN이었던 모델에서는 노드의 개수인 $N$이 커지면 그에 따라 연산해야할 eigen-system이 커진다는 문제가 있었다. 이를 계속 해결하기 위한 연구가 이후에 진행되었고, $2^{nd}$ generation인 ChebNet 그리고 $3^{rd}$ generation인 GCN이 연구되었다.
| Variant | Aggregator | Updator |
|---|---|---|
| ChebNet | $N_k = T_k(\tilde{L})X$ | $H = \sum_{k=0}^K N_k \Theta_k$ |
| $1^{st}$ order model | $N_0 = X$ $N_1 = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}X$ | $H = N_0 \Theta_0 + N_1 \Theta_1$ |
| Single parameter | $N = (I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}})X$ | $H = N\Theta$ |
| GCN | $N = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X$ | $H = N\Theta$ |
위에서 언급했던 GCN이 spectral domain에서의 convolutional GNN에서 가장 유명한 형태가 된다. GCN은 $l$-layer network로, 보다 우리에게 친숙한 neural network 구조를 가진다. 위의 표에서도 언급했지만 Hidden layer는 Aggregator $\hat{A}$에 대해서,
[ \begin{aligned} H^{(l+1)} =& \sigma(\hat{A}H^{(l)}W^{(l)}), \newline \text{with }\hat{A} =& \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X \newline \tilde{D_{ij}} =& \begin{cases} \sum_{k=1} \tilde{A_{ik}} & \text{if }i = j \newline 0 & \text{otherwise} \end{cases} \end{aligned} ]
위와 같이 나타낼 수 있다. 이렇게 연산된 각 hidden embedding에 대해서 output layer는,
[ Z = f(X, A) = softmax(\hat{A}\text{ReLU}(\hat{A}XW^{(0)})W^{(1)})
] 위와 같이 나타낼 수 있다.
그래프 관련 네트워크에 대해서는 아직 이해를 완전히 하지 못했다. 나중에 기회가 된다면 더 공부해볼 수도 있겠지만 아쉽게도 아직까지는 나한텐 딥하게 다뤄보기가 애매한 분야인 것 같다.