푸른 하늘

 

 

GCN 논문을 review하고 난 후 이어서 바로 deep-dive를 했던 논문.

소개된 모델의 이름에 SAGE(현자)가 들어가있어서 좀 신기하기도 하고 피식했던 기억이 난다.

 

GCN과 마찬가지로 원본 코드가 tensorflow v1으로 작성되었던 터라 코드 분석과 실행에 다소 애를 먹었지만, 그래도 개인적으론 (appendix 부분을 제외하고) GCN에 비해 수학적 background가 많이 요구되었던 것 같지는 않았다.

 

논문에서 계속 GCN을 언급하면서 GCN을 확장했다, GCN보다 성능이 잘 나온다 라는 말이 나오는데, GCN paper review는 이전 포스팅에서 확인할 수 있다.

---

 

Published in NIPS(NeurIPS)2017

• paper
• official source code repo (tensorflow v1)
• commented source code repo (tensorflow v1)

Transductive한 방법으로 접근한 이전 연구들과는 다르게 Inductive한 방법으로 접근하는 방법을 소개.
지역적인 이웃(local neighborhood)들의 feature를 적절하게 sample & aggregate하여 node embedding을 생성하는 함수를 학습하는 방법을 소개.

random neighborhood sampling을 활용한 mini-batch training 방법을 소개.

 

 

Introduction

node2vec, DeepWalk, LINE과 같은 이전 representation learning 방법들은 large graph의 node를 low-dimensional embedding vector로 변환하여 여러 downstream task를 위한 입력을 준비하는데 사용되었다.

 

여기서의 핵심인 node embedding은 기본적으로 차원 축소(dimensionality reduction technique), 즉 high-dimensional인 node의 이웃 정보를 low-dimensional인 dense embedding vector로 압축하는 것.이를 통해 여러 downstream task(node classification, clustering, link prediction)을 수행할 수 있다.

 

(거의 모든 representation learning이 그렇듯이, 고 차원으로 표현된 데이터를 저 차원으로 변환/압축하여 downstream task를 위한 준비를 할 수 있다.)

 

이러한 작업은 고정된 graph에서 embedding을 생성하는 것에 초점을 맞추고 있지만, 실 세계 application들은 관측되지 않은(unseen) node에 대해 embedding을 빠르게 계산하는 작업이 필요하다.

 

즉, 이런 inductive한 능력은 변화(진화/성장)하는 graph에서 동작하거나 지속적으로 unseen node를 마주치게 되는 ML system에선 필수적이며, node embedding을 생성하는 inductive한 접근법은 graph 간의 generalization이 보다 간편해질 수 있다.

 

즉, 단백질-단백질 상호작용(protein-protein interaction, PPI) graph에 대한 embedding generator를 train한 후, trained model을 활용하여 새로운 PPI graph에 대한 node embedding을 손쉽게 생성할 수 있다.

(Inductive method가 왜 필요한지에 대한 설명. model을 먼저 train 한 뒤, 다른 data에 대해 빠르게 embedding을 생성할 수 있다.)

 

그렇다면 왜 Inductive method가 transductive method보다 어려울까?

관측되지 않은(unseen) node를 일반화(generalize)하는데 있어, 설계한 알고리즘이 이미 최적화가 진행된 node embedding에 sub-graph를 할당하기 때문이다.

즉, node의 local role과 global position을 모두 나타내는 structural property를 인식하는 방법을 학습해야 한다.

(node embedding을 생성함에 있어 해당 node가 global한 관점에서 어떤 역할을 담당하는지, local한 관점에서 어떤 역할을 담당하는지를 고려해 적절한 embedding을 생성하는 것이 필요. node2vec에서 return parameter에 따라 local에 초점을 맞춰 embedding을 생성할지, global에 초점을 맞춰 embedding을 생성할지를 결정하는게 필요하다는 점에서 기인한 듯 하다.)

 

node embedding을 생성하는 작업은 선천적으로 transductive한 작업인데, 이는 matrix factorization 기반의 목적 함수를 사용해 각 node마다 embedding을 직접적으로 최적화 한다.

하지만 이 방법은 single/fixed graph의 node에 대해 prediction을 수행하므로 unseen data의 일반화를 잘 하지 못하는 문제가 있다.

DeepWalk에서 소개한 방법 처럼 inductive한 작업으로 변환할 수 있지만, 새로운 예측을 수행하기 전 추가적인 gradient descent 단계가 필요하기에 이는 굉장히 computationally expensive한 작업이 된다.

 

GCN처럼 convolution 연산을 이용해 graph의 구조를 학습하는 접근 법도 있지만, GCN은 fixed graph를 사용하는 transductive method에서만 사용되고 있다.

 

따라서 본 논문에서는 GCN을 inductive unsupervised learning으로 확장하고, GCN의 접근 방식을 일반화하여 trainable한 aggregate function을 사용하는 framework를 제안한다.

 

Present work

 

Inductive node embedding을 위한 general framework인 GraphSAGE(SAmple and aggreGatE)를 소개한다.

 

unseen node를 일반화하기 위한 embedding function을 학습하기 위해 node feature를 활용하며, 학습 알고리즘에 node feature를 활용함으로써 각 node마다 이웃의 topological structure 뿐만이 아닌 이웃 node에 존재하는 node feature의 분포 또한 학습이 가능하다.

 

또한 각 node마다 구별되는 embedding vector를 학습하는 대신, node의 local 이웃에서 feature 정보를 집계하는 aggregator function을 학습하며, 이 함수는 주어진 node로부터 몇 hop(depth)까지의 정보를 집계한다.

(aggregator function을 통해 한 node로 부터 $k$ 거리 만큼 떨어진 node의 정보를 활용. $k$ 거리 == $k$-hop)

 

test(inference)시엔 학습된 aggregator function을 활용해 unseen node 전체에 대한 embedding을 생성할 수 있다.

 

(즉 aggregator function이 정해진 hop 수 만큼까지의 node 정보를 집계하여 model train을 하고, trained model(aggregator function)을 이용해 unseen data에 대한 embedding을 간단하게 생성할 수 있다는 의미이다.)

 

Citation network, Reddit, PPI 총 3개의 dataset을 이용했을 때 기존 GCN의 단순한 aggregate 방식 보단 본 논문에서 제안한 여러 종류의 aggregator function이 embedding 생성에 있어 월등한 성능을 보여준다.

 

 

 

Related Work

(언제나 보는 선행연구 소개 & 우리 paper가 이래서 더 좋다~ 하는 내용들)

Factorization-based embedding approaches

random walk approach와 matrix-factorization 기반의 목적 함수를 이용해 low-dimensional embedding을 학습하는 연구가 존재한다.

 

이 방법들은 전통적인 spectral clustering, multi-dimensional scaling, PageRank와 유사하며, 각 node마다 직접적으로 node embedding을 학습하기에 기본적으로 transductive한 방법이고, 새로운 node에 대한 예측을 생성하기 위해 추가적인 training이 필요하다.

 

또한 이 방법들은 목적 함수가 embedding의 orthogonal transformation(직교 변환)에 대해 불변(invariant)한데, 이는 즉 embedding space가 graph마다의 embedding space를 자연스럽게 일반화하지 못함을 의미하며 re-train 동안 embedding space가 변경될 수 있다.

(train 마다 embedding space가 변할 수 있음을 이야기하는 듯 하다.)

 

Planetoid-I 알고리즘은 inductive & semi-supervised learning의 embedding 기반 접근법이지만, inference를 하는 동안 graph의 구조적인 정보(structural information)을 활용하지 않는다.

 

앞서 언급한 접근 방식들과는 다르게, 본 논문에서는 unseen node에 대한 embedding을 생성할 수 있도록 model train에 있어 feature information을 사용한다.

 

Supervised-learning over graphs

graph data의 supervised learning에 대한 여러 연구가 존재하며, 대표적으로 kernel-based 접근이 포함된다.

(graph의 feature vector가 다양한 graph kernel에서 부터 생성된다는 의미.)

 

WL graph kernel에 관한 내용은 다른 블로그 포스팅을 참고하면 좋을 듯 하다:

블로그 포스팅

블로그 포스팅

 

이 외에도 neural network를 활용한 접근 방안(최초의 GNN(2009), Recurrent-GNN 등)도 있었고, 본 연구는 해당 몇몇 알고리즘들에 영감을 받았다.

 

하지만 선행된 연구들은 graph(또는 sub-graph) classification에 초점을 두었고, 본 연구는 node 개별마다의 representation을 생성하는 것에 초점을 둔다.

 

Graph convolutional networks

CNN 구조를 사용하는 이 방법들은 large graph로 확장되지 않거나, graph classification (또는 둘 다)를 위해 설계되었다.

 

본 연구는 기본적으로 GCN에 기반하지만, GCN은 train 동안 full graph Laplacian을 알고 있어야 하는 문제가 있다.

(각 node마다 연결된 모든 node의 feature를 aggregate할 때 어느 node가 어느 node와 연결되었는지에 대한 연결 정보를 알고 있어야하므로.)

 

따라서 본 연구가 GCN을 inductive한 방법으로 확장한 것으로도 생각할 수 있다.

 

 

 

Proposed method: GraphSAGE

Embedding Generation (i.e. forward propagation) algorithm

 

입력: 전체 graph $\mathcal{G}$, 모든 node의 feature vector인 $\mathrm{x}_v$, 미분 가능한 집계 함수
$\mathrm{AGGREGATE_k}$, 이웃 함수 $\mathcal{N}$
출력: 모든 node에 대한 vector representation $\mathrm{z_v}$

line 1: 초기 representation 초기화
line 2~8: 탐색 깊이 $k$ ($k$-hop) 만큼 loop
 line 3~6: 모든 node마다 loop
  line 4: 현재 layer의 이웃 node들의 정보는 이전 layer에서 존재했던 이웃 node들의 정보를 집계 (이웃 representation 집계)
  line 5: 현재 layer의 자기 자신 node의 정보는 이전 layer에서 존재했던 자신의 정보 & 현재 layer에서 앞서 계산한 이웃 node들의 정보를 집계 (이전 layer에서 계산된 자신의 representation & 현재 layer에서 계산된 이웃의 representation을 이용해 현재 layer에서의 자기 자신의 representation을 계산)
 line 7: L2 normalization

 

model이 이미 train 되었다 가정하고, model의 parameter는 고정된 상태임을 가정한다.

 

$K$개의 집계 함수($\mathrm{AGGREGATE}$)는 이웃 node들로부터 정보를 집계하며, 가중치 행렬인 $\mathbf{W}$는 다른 layer(또는 다른 search depth)간 정보를 전파하는 역할을 수행한다.

 

각 iteration(각기 다른 search depth, hop) 마다 이웃 node의 정보를 집계, 이 과정을 반복, 반복하며 점점 더 많은 이웃 node들의 정보를 집계한다.

 

핵심을 살펴보면...

 

line 4: 각 node $v$는 근처 이웃 node의 representation을 단일 vector $\mathrm{h}^{k-1}_{\mathcal{N}_(v)}$로 집계한다.

이 과정은 이전 loop에서 생성된 representation에 의해 생성되며, $k=0$은 입력으로 전달된 초기 node feature를 의미한다.

 

line 5: 현재 자기 자신의 representation인 $\mathrm{h}^{k-1}_{v}$와 집계된 이웃 node들의 representation인  $\mathrm{h}^{k-1}_{\mathcal{N}_(v)}$을 CONCAT한다.

CONCAT한 vector를 non-linear activation function $\sigma$를 가진 fully-connected layer(FFN)로 전달한 후, 전달된 정보는 다음 step에서 사용될 representation이 된다.

 

---

놀랍게도 이게 전부다.

정해진 hop 수 $k$까지 각 node마다 이웃 node의 representation을 aggregate $\rightarrow$ 이전에 계산된 자신의 representation과 aggregate한 이웃 node의 representation을 CONCAT $\rightarrow$ 현재 자신의 representation을 계산

---

 

Relation to the Weisfeiler-Lehman Isomorphism Test

GraphSAGE는 기본적으로 graph 동형 테스트에 사용되는 classical한 알고리즘인 WL-test에 영감을 받았다.

위 Algorithm 1에서 다음의 가정을 한다면, 해당 알고리즘은 전형적인 WL-test의 예시가 된다.

1. $K = |\mathcal{V}|$: 탐색 깊이를 node 수와 동일하게 설정.
2. $\mathbf{W} = \mathbf{I}$: 가중치 행렬을 항등(Identity) 행렬로 설정.
3. non-linearity를 가지지 않은 적절한 hash function을 aggregator로 설정.

(WL kernel/WL-test는 상단 Supervised-learning over graphs 문단에서 hyperlink로 설정한 블로그 포스팅 참고)

 

서로 다른 2개의 sub-graph에서 생성된 representation set $\mathrm{z}_v$가 동일하다면, WL-test에 따라 이 2개의 sub-graph는 isomorphic하다.

(즉 2개의 sub-graph에서 생성된 representation이 동일하다면 2개의 sub-graph는 동형사상.)

 

GraphSAGE는 WL-test의 continuous approximation으로, hash function을 trainable한 neural network aggregator로 대체한 셈이다.

 

 

Neighborhood definition

고정된 크기의 batch에서 계산 공간(computational footprint)을 유지하기 위해, 전체 이웃이 아닌 고정된 크기의 이웃 집합을 uniform하게 sample 한다.

 

$\mathcal{N}_(v)$는 고정된 크기의 집합인 {$u \in \mathcal{V} : (u, v) \in \mathcal{E}$} 로 부터 uniform하게 생성된 집합이며, Algorithm 1에서 각 $k$번째 iteration마다 서로 다른 sample을 수집한다.

 

실험적으로 보았을 때, $K=2$, $S_1 \cdot S_2 \leq 500$일때 최상의 성능을 보여주었다.

(즉 2-hop에 걸쳐 representation 계산을 위해 aggregate하는 이웃 node의 수가 총 500개 이하일 때 성능이 좋았다 라는 의미. (e.g. 1-hop에서 50개의 node를 sample($S_1 = 50$), 2-hop에서 10개의 node를 sample ($S_2 = 10$)))

 

논문 Appendix 부분에 sampling을 활용한 mimibatch training의 pseudocode가 같이 기술되어 있다.

 

Appendices A: Minibatch pseudocode (일부)

 

 

Learning the parameters of GraphSAGE

output representation $\mathrm{z}_u$에 대해 graph-based loss function을 사용하며, SGD를 이용해 가중치 행렬 $\mathbf{W}$와 aggregator function의 parameter tuning을 진행한다:

 

식1과 같은 CE-like loss function은 인접한 node는 유사한 representation을 갖도록 하고, 이질적인 node (feature가 극히 다른 node)의 representation은 최대한 구별되도록 하는 역할을 수행한다.

 

즉 $\log (\sigma(\mathrm{z}^{\top}_{u} \mathrm{z}_{v}))$ 부분이 1에 가까워지도록(비슷한 node는 비슷한 representation을 갖도록), $\log (\sigma(- \mathrm{z}^{\top}_{u} \mathrm{z}_{v}))$ 부분이 0에 가까워지도록(이질적인 node는 representation이 최대한 달라지도록) 목적 함수를 설정한다.

 

 

Aggregator Architectures

기존 N-D lattices(e.g. 이미지, 문장 등...)들을 이용해 train하는 ML과는 달리 node의 이웃들은 자연적인 순서가 없으므로, 따라서 aggregator function은 순서가 없는 모든 vector 집합에 대해 동작해야 한다.

 

즉, 이상적인 aggregator function은 trainable하고, 높은 representational capacity를 유지하면서 symmetric(입력의 순서가 바뀌어도 결과가 불변, invariant to permutation of its inputs)이어야 한다.

 

 

Mean Aggregator

 

단순히 $\mathrm{h}^{k-1}_{\mathcal{N}_(u)}, \forall u \in \mathcal{N}_(v)$에 있는 모든 vector들에 대해 element-wise mean을 계산하는 방법으로, 기존 transductive GCN의 convolutional propagation rule과 동일하다.

 

위의 식2를 Algorithm1의 line 4,5에 대입함으로써 inductive한 GCN 연산을 구현할 수 있다.

(기존의 GCN은 Algorithm1의 line 5에 해당하는 CONCAT 연산이 없음)

 

 

LSTM Aggregator

LSTM 구조에 기반한 aggregator로서, mean aggregator에 비해 더욱 큰 표현력(larger expressive capability)를 가질 수 있다.

 

하지만 기본적으로 LSTM은 입력을 순차적으로 처리하기 때문에 not symmetric (not permutation invariant)한데, 본 연구에서는 LSTM을 이웃 node들의 random permutation에 적용하여 unordered set에서 동작할 수 있도록 적용했다.

(해당 부분에 대한 commented source code)

 

 

Pool Aggregator

 

이는 symmetric하고 trainable하며, 각 이웃 vector는 독립적으로 fully connected neural network의 입력으로 전달되어 이웃 집합의 정보 집계를 위해 element-wise pooling 연산을 적용한다.

(이 방법은 일반적인 point set을 neural network에 적용한 PointNet[C. R. Qi, et al., CVPR2017]에서 영감을 받음)

 

MLP를 이웃 집합의 각 node representation에 대한 feature를 계산하는 여러 개의 함수 집합(set)으로 간주할 수 있으며, 계산된 feature에 pooling operator를 적용함으로써 model은 효과적으로 이웃 집합의 각기 다른 측면(aspect)을 포착할 수 있다.

 

 

 

Experiments

3가지의 benchmark task.

• citation dataset에 대한 classification
• reddit dataset에 대한 classification
• PPI dataset에 대한 classification.

(PPI의 경우 작은 크기의 graph가 다수 포함되어 있으므로, 해당 dataset에선 unseen graph에 대한 test를 수행)

 

Experimental setup

4개의 baseline.

• random classifier
• feature 기반의 logistic regression
• DeepWalk
• raw feature와 DeepWalk에서 생성된 embedding을 결합한 classifier

GraphSAGE가 GCN의 inductive한 방법이기에, GCN을 GraphSAGE-GCN으로 명명하여 비교 실험에 기재.

 

또한 aggregator function을 각기 달리 변형하여 사용하였고, $K=2$, $S_1=25$, $S_2=10$으로 설정.

(1-hop에서는 25개의 이웃 node를 sample, 2-hop에서는 10개의 이웃 node를 sample)

 

 

Inductive learning on evolving graphs: Citation and Reddit data &
Generalizing across graphs: Protein-protein interactions

 

citation dataset에선 node degree를 feature로 사용하였고, abstract를 300-dimensional word vector로 변환하여 활용.

reddit dataset에서 node label은 subreddit(community)를 의미하며, 사전에 생성된 300-dimensional word vector를 feature로 활용.

PPI dataset에선 유전자의 위치 정보, 유전자의 생김새, 면역학적 특징(immunological signature)를 feature로 활용.

 

결과 table에서 볼 수 있듯이 inductive method인 GraphSAGE가 다른 baseline들에 비해 월등히 뛰어난 분류 성능을 보여줌을 알 수 있고, transductive method인 GCN(GraphSAGE-GCN)과 비교해도 대체적으로 좋은 분류 성능을 보여주는 것을 알 수 있다.

 

 

Runtime and parameter sensitivity

 

Deepwalk는 unseen node의 embedding을 계산하기 위해 SGD round를 새롭게 시작해야 하므로 속도가 많이 뒤쳐진다.

(Figure 2-A의 DW)

 

$K=1$로 설정한 경우에 비해 $K=2$로 설정한 경우가 10~15%의 성능 항상을 보이지만, $K=2$보다 크게 설정하는 경우 미미한 성능 차이(0~5%)를 보여준다.

(sample되는 이웃 node의 수 & hop 수를 적절하게 설정하는 경우 보편적으로 좋은 성능을 보인다.)

 

 

Summary comparison between the different aggregator architectures

LSTM, pool aggregator의 성능이 가장 좋게 나왔으며, 기존 GCN의 방법에 비해 대체적으로 논문에서 제안한 LSTM, pool, mean의 성능이 좋았다.

 

특이하게도 서로 다른 aggregator들을 사용한 결과에 대해 비모수 검정 기법인 Wilcoxon Signed-Rank Test를 진행하였고, T-통계량과 p-value가 applicable하였음을 확인하였다.

(또한 GCN 접근법에 비해 통계적으로 유의미한 gain을 얻었음을 한번 더 강조하였다.)

 

LSTM과 pool 간의 큰 성능 차이는 없었지만, 특성상 LSTM의 속도가 pool보다 (약 2배) 느렸음을 언급하였다.

 

 

 

Theoretical analysis &
Conclusion

GraphSAGE가 feature에 기반함에도 불구하고 graph의 구조를 학습할 수 있음을 소개하였고, 이웃 node의 sampling을 통해 runtime과 성능을 효율적으로 trade-off 할 수 있음을 보여주었다.

 

(Theoretical analysis와 Appendix 부분에 본 연구가 이론적으로 어떤 특징/강점이 있는지를 설명해주는데, 수학적인 background가 부족하여 별도로 기술하진 않았다😥)

 

 

 

---

 

개인적으로 GNN 연구를 할 때 GCN에 비해 여러 insight를 많이 가져다 준 논문이다.

 

neighborhood sampling을 소개하여 GNN의 mini-batch training이 가능함을 알려주기도 하였고, 이것이 발전하여 추후 layer-wise sampling, sub-graph sampling 등등 여러 sampler가 등장할 수 있게 하는 계기를 마련해주기도 했다는 생각이 든다.

 

실제로 PyG, DGL에서도 간단하게 sampler를 호출하여 random sampling을 수행할 수 있기도 하다.

 

하지만 이렇게 단순하면서도 편리하고 어떻게 보면 획기적인 neighborhood sampling의 (어떻게 보면 고질적인) 문제점이 있는데, 이는 추후 포스팅 할 글들에서 다시 언급하고자 한다.

 

22년 당시 review 후에 작성하였던 슬라이드도 함께 첨부하였다.

 

GraphSAGE review.pdf

0.95MB

 

 

E.O.D.

석사과정을 시작하던 시절, 본격적으로 논문들을 review하던 중 deep-dive를 했던 논문 중 하나.

당시엔 notion의 존재를 모르기도 했고, (현재까지) 태블릿이 없기도 해서 프린트로 출력 후 논문에 직접 써가며 review를 했었던 기억이 난다.

(notion의 존재를 좀 더 빨리 알았더라면 re-posting도 수월했을텐데..)

 

tensorflow v1으로 작성된 코드를 논문과 비교하면서 해석해보고, 어찌저찌 실행도 해보고, 원 저자의 pytorch 구현을 참고해서 pytorch로 다시 작성해보고...

여러모로 추억이 많은 논문인 듯 하다.

 

 

 

---

Published in ICLR2017

• paper: https://arxiv.org/abs/1609.02907
• official source code repo (tensorflow v1): https://github.com/tkipf/gcn
• commented source code repo (tensorflow v1)
• re-built source code repo (pytorch)

graph의 edge 수에 따라 선형적으로 확장 가능한 semi-supervised learning 방법(GCN)을 소개.
hidden layer는 node의 feature와 그래프의 지역적인(local) 구조를 encode하여 그에 해당하는 representation을 학습하는 것이 가능.

 

 

Introduction

graph-based semi-supervised learning을 언급한다.

 

graph-based semi-supervised learning이 무엇일까?

graph의 모든 node마다 label 정보가 포함되어 있지 않고 일부의 node만이 label 정보를 가지고 있어, 해당 node들을 통해 node representation을 학습하여 label이 없는 node들에 대한 generalization(일반화)을 하는 것이 주 목적이라고 생각할 수 있을 것이다.

 

이를 하게 되면 뭐가 좋을까?

대표적으로 학습된 representation들을 통해 주어진 node가 어떤 label에 속하는 지를 판단하는 node classification task를 수행할 수가 있고, 논문의 첫 문장에서도 "classifying nodes (such as documents) in a graph (such as a citation network)." 를 언급하여 node classification task를 고려하기로 한다.

 

물론 과거에도 node classificaiton task를 해결하기 위한 여러 시도들이 있었고, 해당 연구들은 주로 graph Laplacian regularization term을 loss function에 추가하여 학습을 진행했다.

 

$\mathcal{L_{reg}}$의 몇몇 부분을 보자.

$f(\cdot)$ 이 미분 가능한 함수(e.g. neural network), $\lambda$는 단순 factor, $X$는 node feature vector 로 구성된 feature matrix, 그리고 $\Delta$는 $\Delta = D - A$로 이뤄지는 unnormalized graph Laplacian이다.

 

여기서 $D$는 각 node들의 차수(degree)를 나타내는 차수 행렬(degree matrix) 이고, $A$는 각 node들 간의 연결 정보를 binary하게 표현한 인접 행렬(adjacency matrix) 이다.

 

unnormalized graph Laplacian 이 무엇일까?

식을 보면 말 그대로 인접 행렬과 차수 행렬을 이용하여, graph의 구조적인 정보를 조금이나마 더 담아낸 행렬로 생각할 수 있다.

 

여기서 문제점이 발생한다.

 

식1은 연결된 node끼리는 같은 label을 공유한다 라는 가정을 전제 하에 두고 있다는 점이다.

이는 graph의 edge가 node 간의 유사성을 직접적으로 encode하지는 않지만, node간의 유사성은 추가적인 정보를 포함할 수 있기에 modeling capacity를 제한할 수 있다.

 

이게 무슨 의미 일까?

label은 동일하지만, 거리가 멀리 떨어진 두 node간의 유사성 정보를 반영하지 못할 수 있다.

즉 이러한 가정을 갖고 modeling을 수행할 경우, 복잡한 graph 또는 다양한 label을 가진 graph에서 모델의 학습 성능이 저하될 수 있다는 의미일 것이다.

 

따라서 본 논문에서는 graph의 구조를 곧바로 encode할 수 있는 방법과 더불어 크게 2개의 contribution을 소개한다.

 

1. graph에 바로 적용될 수 있는 neural network를 위한 간단한 layer-wise propagation rule을 소개.
2. 제안한 graph-based neural network 모델이 semi-supervised node classification task를 빠르고 scalable하게 수행 가능하다는 점을 소개.

 

 

 

Fast Approximate Convolutions on Graphs

논문에서 소개하는 GCN(Graph Convolutional Network)을 간단하게 소개하고, 관련된 이전 연구와 spectral convolution에 대한 background를 언급한다.

 

논문에서 소개하는 핵심인 layer-wise propagation rule은 다음과 같다.

 

$\tilde{A}$는 $A + I_N$으로 표현되는 undirected graph의 수정된 인접 행렬.

이때 $I_N$은 항등 행렬(identity matrix)이고 각 node가 자기 자신의 정보를 활용하기 위해 self-connection을 추가 한 형태라고 볼 수 있다.

$\tilde{D_{ij}}$는 $\tilde{A}$의 차수 행렬이고, $W^{(l)}$은 layer-specific weight matrix이다.

$H^{(l)}$은 $l$번째 layer의 activation matrix, 즉 $H^{(0)} = X$ (node feature matrix)가 된다.

 

논문에서는 식2의 propagation rule이 선행 연구인 [Hammond et al., 2011]과 [Defferrard et al., 2016](ChebNet)과 같이 localized 된 spectral filter의 1차 근사(first order approximation)를 통해 이뤄질 수 있음을 이야기 하고 있다.

 

---

선행되었던 두 연구 뿐만이 아니라 Chebyshev polynomials, spectral convolution 등등 알아햐 할 내용이 좀 많은 듯 한데, 이후로는 최대한 내가 이해했던 대로 기술하고자 한다.

 

review를 하던 당시 내용이 이해가 가질 않아 (조금이나마 이해하는데 도움이 되었 던) 자료를 다시 봐도 좋을 듯 하다:

블로그 포스팅

UCLA 자료

---

 

 

Spectral Graph Convolutions

Fourier domain에서 정의되며 filter $g_{\theta} = diag(\theta)$를 통한 spectral convolution은 다음과 같이 정의가 가능:

이때 $U$는 대각 성분이 자기 자신의 eigenvalue인 $\Lambda$로 구성된 normalized graph Laplacian $L = I_N - D^{-\frac{1}{2}}A D^{-\frac{1}{2}} = U{\Lambda}U^T$의 eigenvector로 이뤄진 행렬이고, $U^{T}x$는 $x$의 graph Fourier transform이다.

(벌써 어지럽다)

 

여하튼, 논문에서는 식3의 문제점을 지적하고 있다.

1. 이 식을 바로 계산하는 것은 computationally expensive.
   ($\because$ $D$는 sparse한 eigen matrix)
2. large graph의 Laplacian $L$을 eigen decomposition하는 것은 expensive.

이처럼 sparse matrix의 직접적인 이용이 힘들었기에, [Hammond et al., 2011]가 다음과 같이 $g_{\theta}(\Lambda)$에 대해 Chebyshev polynomials $T_k(x)$를 $K^{th}$차 까지 확장한다면 적절하게 근사(approximate)할 수 있음을 제안했다.

 

Chebyshev polynomials는 $T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$와 같이 recursive한 형태로 정의된다.

(자세한 내용은 [Hammond et al., 2011]의 논문을 참고하라고도 저자가 이야기 하고 있다.)

 

위의 식4을 이용해 식3을 다시 표현한다면 다음과 같이 근사(approximate)할 수 있다:

 

이때 $\tilde{L} = \frac{2}{\lambda_{max}}L - I_N$.

이 표현 식은 Laplacian에서 $K$차수 polynomial이기 때문에 $K$-localized된 식 이며, 즉 graph의 한 중심 node에서부터 최대 $K$ step만큼 떨어진 node에만 집중할 수 있으며, 계산 복잡도는 edge 수에 linear한 $\mathcal{O}(|\delta|)$가 된다.

 

역시 어렵다.

깊게 생각하기 보단, 단순히 기존 spectral convolution on graph의 식3 을 위와 같이 Chebyshev polynomials를 이용해 식5와 같이 approximate 하게 된다면 복잡도를 linear하게 줄일 수 있다는 점을 짚고 가면 될 듯 하다.

 

[Defferrard et al., 2016](ChebNet)가 선행적으로 이 식을 사용해 graph에 대해 convolutional neural network를 적용하는 방법을 정의하기도 하였다.

 

 

 

Layer-wise Linear Model

식5 형태의 convolutional layer를 여러 층 쌓아 graph convolution에 기반한 neural network model을 설계할 수 있고, 이때 $K=1$로 제한하게 된다면 식5는 선형함수가 된다.

 

$K=1$이어도 식5의 layer를 여러 층 쌓아서 convolutional filter를 여전히 근사할 수 있지만, Chebyshev polynomials로부터 주어진 명시적 파라미터화(explicit parameterization)의 제약을 받지 않게 된다.

이런 $K=1$인 모델은 wide node degree distribution을 가진 graph(e.g. social network, citation network, 실 세계 graph data 등...)에서 지역적인 이웃 구조(local neighborhood structure)에 overfit하는 문제를 완화할 수 있으며, layer-wise한 선형 연산으로 인해 neural network의 층을 더욱 깊게(deep) 할 수 있다.

 

neural network의 파라미터가 train하는 동안 적응 및 변화할 것으로 기대하기에 $\lambda_{max} \approx 2$로 근사하게 되면, 식5는 2개의 free parameter $\theta'_0$, $\theta'_1$ 를 이용해 다음과 같이 전개될 수 있다:

 

filter parameter는 전체 graph에서 공유 가능하며, 이 형태의 filter를 연속적으로($k$번) 적용하게 되면 한 node로 부터 $k$ 거리 만큼 떨어진 이웃까지 잘 convolve할 수 있다.

 

Chebyshev polynomials
$T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$를 이용해 $K=1$인 경우를 전개를 해 보면 다음처럼 간단히 전개할 수 있다:

$T_0(\tilde{L}) = 1$
$T_1(\tilde{L}) = \tilde{L}$

그리고 $\tilde{L} = \frac{2}{\lambda_{max}}(L - I_N)$로 정의되었고,
이때 $\lambda_{max} \approx 2$를 적용하면,
$\tilde{L} = L - I_N$ 이므로
$L = I_N - D^{-\frac{1}{2}}A D^{-\frac{1}{2}}$가 된다.

이 결과들을 식5에 적용($K=1$)하면 식6의 형태를 구할 수 있다.

 

여기서 연산량을 줄이거나 overfitting을 방지하기 위해서 filter parameter를 $\theta$ $=$ $\theta'_0$ $=$ $- \theta'_1$와 같이 간소화 한다면 식6은 다음과 같이 표현될 수 있다:

 

(단순히 $\theta$를 풀어서 전개하면 이 형태가 나온다.)

하지만 deep neural network에서 이 연산을 반복적으로 수행하는 경우, 수치적으로 불안정할 수 있으며 exploding/vanishing gradient 문제가 발생할 수 있다.

 

따라서 이를 방지하기 위해 다음과 같은 renormalization trick을 사용한다:

$$I_N + D^{-\frac{1}{2}}A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$$

$$where \ \tilde{A} = A + I_N, \ \tilde{D}_{ij} = \sum_{j} \tilde{A}_{ij}$$

 

이 trick을 이용해 $C$ input channel을 가진 signal $X \in \mathbb{R}^{N \times C}$ (graph의 각 node마다 $C$ 차원의 feature vector를 가지고 있는 경우)에 일반화를 하면 다음과 같은 형태의 수식을 구할 수 있다:

$\Theta \in \mathbb{R}^{C \times F}$는 filter parameter로 구성된 행렬, $Z \in \mathbb{R}^{N \times F}$는 convolution이 진행 된 signal의 행렬이다.

(즉 $\Theta$가 learnable weight, $Z$가 1번의 layer propagation을 거치고 non-linear activation을 적용하기 이전의 representation이 된다.)

 

이 filtering operation은 $\mathcal{O}(|\delta|FC)$의 복잡도를 가지며, 인접 행렬(adjacency matrix)과 특징 행렬(feature matrix)의 곱 연산($AX$)은 sparse matrix dense matrix multiplication (SpMM)과 같은 연산을 통해 효율적인 계산이 가능하다.

 

(몇몇 자료들을 보면 $\sum$ 기호를 이용해 node-level에서 representation을 계산하는 식을 소개하는데(vector-level), 

결국 이 vector들을 stack하여 식8과 같이 matrix로 표현한 것일 뿐이다.)

 

 

 

Semi-Supervised Node Classfication

앞서 소개한 내용을 바탕으로 이제 본 논문에서 target으로 잡았던 node classification을 어떻게 handle할 것인지를 소개한다.

 

논문에서는 graph의 구조적인 정보를 담은 $A$와 주어진 데이터인 $X$에 기반하여 식8 기반의 모델 $f(X, A)$를 conditioning하여 graph-based semi-supervised learning이 가능함을 이야기하고 있다.

 

semi-supervised learning을 위한 multi-layer GCN의 구조를 그림으로 보면 다음과 같다:

 

 

Example

2-layer GCN을 생각해보자.

 

먼저, 주어진 인접 행렬 $A$를 이용해 $\hat{A} = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$와 같은 전 처리(pre-process) 과정을 거친 후, 다음의 forward pass를 거치면 된다:

($\tilde{A} = A + I_N, \ \tilde{D}_{ij} = \sum_{j} \tilde{A}_{ij}$)

 

여기서 $W^{(0)} \in \mathbb{R}^{C \times H}$는 input-hidden 간의 가중치 행렬(weight matrix)이고, $W^{(1)} \in \mathbb{R}^{H \times F}$는 hidden-output 간의 가중치 행렬이다.

 

그리고 $\mathrm{softmax}$는 $\mathrm{softmax}(x_i) = \frac{1}{\sum_i exp(x_i)}exp(x_i)$인 row-wise로 적용되는 활성화 함수(activation function)이다.

 

학습을 위한 손실 함수(loss function)는 classification task에서 자주 사용되는 cross-entropy error를 사용하며, label이 포함된 모든 데이터에 대해 계산을 한다면 다음과 같다:

 

실험에 있어 모든 training iteration마다 full-batch gradient descent를 수행하였고, dropout을 사용하였으며, $A$는 sparse representation을 이용했기에 edge 수 만큼의 공간 복잡도를 가지게 된다.

 

---

어떻게 보면 단순하다.

2-layer를 가진다는 의미는 node representation을 계산 할 때 하나의 node로 부터 거리 2(2-hop)만큼 떨어진 노드의 representation을 활용한다는 의미일 것이다.

graph theory에 따르면 인접 행렬 $A$를 여러 번($n$번) 곱한다는 의미가 곱한 수 만큼의 거리($n$)까지를 고려한다(?)는 의미로 알고있는데, 자세한 내용은 graph theory를 자세히 공부한 적이 없어서 아직은 잘 모르겠다😥

---

 

 

Implementation

상단 repo link 참고

tf-v1이라 코드 해석 및 실행이 많이 힘들었던 기억이 새록새록 난다.

 

 

Related Work

Graph-based Semi-Supervised Learning

크게 2가지 접근법이 존재.

• 명시적으로 graph Laplacian regularization 형태를 사용하는 방법
  : label propagation [Zhu et al., 2003], manifold regularization [Belkin et al., 2006], deep semi-supervised embedding [Weston et al., 2012]
• graph embedding에 기반한 방법
  : DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], node2vec [Grover & Leskovec, 2016], Planetoid [Yang et al., 2016]

graph embedding 방법 중 DeepWalk, LINE, node2vec은 모두 random walk를 생성한 후 semi-supervised learning을 진행하는 2-step pipeline이 필요하여 두 step이 분리되어 최적화가 되어야 하지만, Planetoid는 embedding 학습 중 label 정보가 주입되어 그런 별도의 작업이 필요하지 않다.

 

 

Neural Networks on Graphs

Gori et al. (2005)에 의해 graph에 동작하는 neural network가 처음 소개되었고, Scarselli et al. (2009)에 의해 RNN을 이용한 방법이 소개되었다. 

RNN을 이용한 방법엔 여러 제약점이 존재했고, 이를 해결하기 위해 Li et al. (2016)에 의해 개선된 연구를 소개되었고, Duvenaud et al. (2015)에 의해 graph-level classification task에 convolution-like propagation rule이 소개되었다.

 

하지만 이 방법들은 node degree에 특정된 weight matrix가 필요했고, 이는 large graph에는 적용되기 힘든 문제가 있었다.

 

앞선 연구들과는 다르게 본 논문에서는 layer 당 1개의 weight matrix를 가지며, $A$를 적절하게 정규화하여 여러 node마다 다른 degree를 다룰 수 있도록 하였다.

 

spectral graph convolutional neural network는 Bruna et al. (2014)에 의해 소개가 되었고, Defferrad et al. (2016)가 fast localized convolution을 이용해 앞선 연구를 개선하였다.

 

본 연구에서는 조금 더 큰 규모의 network(graph)에서 node classification을 하는 방법을 고안하였고, 기존 framewortk에 몇가지 단순화(simplification)를 진행하여 large scale network(graph)에서 더 나은 scability와 classification performance를 달성할 수 있었다.

 

(단순히 related work 소개 + 우리 paper가 이래서 더 좋다~ 하는 내용들.)

 

 

 

Experiments

Datasets

Planetoid [Yang et al., 2016]에서 사용한 Citeseer, Cora, Pubmed, NELL을 사용.

 

Citation, Cora, Pubmed와 같은 Citation network에 대해선 citation link를 undirected edge로 판단하여 binary, symmetric adjacency matrix $A$를 생성하였다.

 

Knowledge graph인 NELL에 대해선 $(e_1, r, e_2)$와 같은 entity relation을 $(e_1, r_1), \ (e_2, r_2)$와 같이 분리하였고, 모든 relation node마다 one-hot representaion을 할당하였으며, Citation network와 마찬가지로 binary, symmetric adjacency matrix $A$를 생성하였다. (두 node 사이에 1개 이상의 edge가 연결되어 있다면 1, 아니라면 0)

 

Experimental Setup

• 2-layer GCN
• Planetoid [Yang et al., 2016]과 동일한 dataset split 진행
• 200 epoch
• Adam with learning rate 0.01
• early stopping with window size 10
• Glorot & Bengio weight initialization (Xavier initialization)
• input feature에 대해 row normalize 진행
• hidden layer size 32

 

Baselines

Planetoid [Yang et al., 2016]과 동일한 baseline 사용, 추가적으로 Planetoid와 비교 실험 진행.

 

 

Results

 

table에서 볼 수 있듯이, 기존 method들에 비해 significant한 성능 향상을 달성했다.

 

Planetoid와 제안한 GCN에 대해 wall-clock training time(실제 train에 소요된 시간)을 측정하였는데, 대부분의 경우 Planetoid에 비해 시간이 단축된 점을 확인할 수 있다.

 

 

특이하다고 느꼈던 점은 기존의 propagation 방법들에 대한 비교 실험도 진행한 것인데, 논문에서 제안했던 renormalization trick을 적용한 경우의 perfomance가 가장 좋은 결과를 보여주고 있다.

 

앞서 언급했었던 기존 방법(수식)들의 한계점을 결과로서 직접 보여주고자 했던 것이지 않았을까 라는 생각이 들었었다.

 

 

Discussion & Conclusion

graph Laplacian regularization에 기반한 방법은 edge가 단순히 node의 유사성(similarity)을 encode한다고 가정하기에 제한점이 많을 수 있다.

Skip-gram(embedding) based method에 기반한 방법은 최적화하기가 어려운 multi-step pipeline에 기반한다는 점에서 한계점이 존재한다.

 

본 논문에서 제안한 방법은 두 가지의 한계점을 모두 극복할 수 있으며, 각 layer에서 이웃 node들의 feature information의 propagation을 통해 classification performance를 높일 수 있다.

 

하지만 본 논문에서는 edge feature를 고려하지 않았고, undirected graph만을 고려하였다.

또한 암묵적으로 locality ($K$개의 layer를 가진 GCN에서 $K^{th}$ 차수의 이웃에 의존적)를 가정하였고, 몇몇 데이터 셋에 있어서는 self-connection과 이웃 node와의 edge에 대한 가중치를 조절할 수 있는 파라미터 $\lambda$를 이용해 $\tilde{A} = A + \lambda I_N$와 같이 이용하는 것이 바람직할 수 도 있다.

 

 

결과적으로 graph 데이터에 대해 semi-supervised classification을 수행하는 novel approach를 소개하였고, 소개하였던 first order approximation of spectral convolution에 기반한 layer-wise propagation rule이 효과적임을 보여주었다.

 

 

---

 

실제로 GCN code를 실행해보면 상당히 빠르게 동작하는 것을 볼 수 있다.

 

Graph Neural Network 연구를 시작할 때 Jure Leskovec 교수님의 강의 CS224W, pytorch geometric 공식 tutorial, DeepFindr 채널 등 인터넷에 공개된 좋은 자료들의 도움을 정말 많이 받았었다.

 

22년 당시 review 후에 작성하였던 슬라이드도 함께 첨부하였다.

GCN_review.pdf

0.64MB

 

E.O.D.