1. 개요
최근에 그래프 구조 데이터와 관련된 연구들이 많은 관심을 받고 있다.
Graph neural networks 중에서도 특히 Graph convolutional networks가 node classification, link prediction, clustering task에 우수한 성능을 보여주고 있다. 하지만 이러한 모델들의 대부분은 오직 2~3개의 층으로만 구성된 얕은 모델 구조를 가지고 있다. (shallow model architetures with only 2~3 layers)
GCN 층을 깊게 쌓을수록 원칙적으로 더 많은 정보에 접근할 수 있지만 성능이 더 떨어지는 이유가 GCN의 얕은 설계의 이유이다.
Oversmooting (Li et al., 2018) 은 Deep GCN이 실패하는 이유를 설명하기 위해 제안되어 졌다.
이는 Laplacian smooting을 반복적으로 적용함으로써 GCN이 다른 클러스터의 node features를 혼합하여 구별할 수 없게 한다는 것을 보여준다. 이것은 또한 너무 많은 graph convolutional layers가 쌓여지면서, GCN에서 각 노드의 임베딩이 특정 값으로 수렴하는 경향이 있어 분류를 더 어렵게 만든다. (li et al., 2018)
Oversmooting issue로 제한된 얕은 모델 아키텍처는 고차 이웃(high-oreder neighbors)이부터 정보를 추출하는 기능을 제한한다. 따라서 더 좋은 예측을 위해서는 고차 이웃 정보를 효과적으로 집계할 수 있도록 deep graph model을 설계하는 것이 중요하다.
본 논문에서는 심층 그래프 모델을 구성하는 핵심 방향으로 이웃들의 다른 순서로부터 얻어진 정보의 효율적인 탐색과 효과적인 조합에 있다고 주장한다. 이웃들의 서로 다른 순서들 사이에는 명백한 순차적 관계(suquential relationship)가 존재하기 때문에, 부스팅 알고리즘을 심층 그래프 모델 설계에 통합하는 것은 자연스러운 선택이다.
부스팅 모델 중, AdaBoost(Freund et al., 1999)는 구현이 매우 쉽고 실제 성능과 계산 비용 측면에서 좋은 퍼포먼스를 보이는 알고리즘이다. (Hastie et al.,2009)
본 논문에서는 AdaBoost를 Deep GCN model 에 통합하는 데 중점을 둔다.
첫째, AdaBoost 프레임워크의 도입을 통해, AdaGCN이라는 새로운 RNN 유사 GCN 아키텍처를 얻을 것이다.
서로 다른 이웃 순서에서 정보를 효율적으로 추출한 다음 AdaBoost 방식(반복적 노드 가중치 업데이트)으로 이러한 정보를 결합할 수 있다.
둘째, architectural difference & feature representation power 관점에서 AdaGCN을 기존 방법과 비교할 것이다.
셋째, 일관된 state-of-the-art performance 입증을 위해 광범위한 실험을 수행할 것이다.
2. Our Approach: ADAGCN
2-1. Establishment of ADAGCN
- undirected graph :: G = (V, E)
- N nodes \( v_{i} \) ∈ V
- edges \( (v_{i},v_{j}) \) ∈ E
- A ∈ \( R^{NXN} \) adjacency matrix
- \( D_{ii} \) = \( \sum_{j}A_{ij} \) degree matrix
semi-supervised node classification을 위한 vanila GCN (Kipf & Welling, 2017)에서, 2개의 convolutional layer를 가진 노드의 그래프 임베딩을 아래(1)와 같이 공식화 했다.
$$ Z = {\hat{A}ReLU(\hat{A}XW^{(0)})W^{(1)}} ...................(1)$$
- Z ∈ \( R^{NXK} \) final embedding matrix (output logits) of nodes before softmax
- X ∈ \( R^{NXC} \) feature matrix where C is the input dimension
- \( W^{(0)} \) ∈ \( R^{CXH} \) input-to-hidden weight matrix for a hidden layer H feature maps
- \( W^{(1)} \) ∈ \( R^{HXK} \) hidden-to-output weight matrix
딥 그래프 모델을 구성하는 우리의 핵심 동기는 고차 이웃의 정보를 효율적으로 탐색한 다음 AdaBoost 방식으로 다른 이웃의 메시지들을 결합하는 것이다. 만약 우리가 기존 GCN을 기반으로 고차 이웃으로부터 정보를 추출한다면, 우리는 각층의 레이어의 매개 변수 행렬 \( W^{(i)} , i = 0,1,...,l-1 \) 을 계산해야 되며, 이는 비용적으로 비효율적이다.
또한, Multi-Scale Deep Graph Convolutional Networks(Luan et al., 2019)는 이론적으로 우리가 단순히 GCN을 deep하게 쌓으면 출력값이 그래프 구조의 stationary information만 포함시킬 수 있고 노드의 모든 local information을 잃을 수 있음을 증명했다. 직관적으로 node features을 표현하는데 있어서 너무 많은 비선형 변환을 적용시킬 필요가 없다. 이는 각각의 node features이 다차원 데이터 구조 (ex. 이미지)가 아닌 1차원 희소 벡터이기 때문이다. 다차원 데이터 구조의 경우 비전 작업에 대해서 높은 수준의 표현을 추출하기 위해서 좀 더 심층적인 컨볼루션 네트워크를 필요로 한다. 하지만 node features 같은 경우는 다차원 데이터 구조가 아니기 때문에 표현하는 데 있어서 너무 많은 비선형 변환이 필요없는 것이다. 이러한 인사이트는 최근 많은 연구에서 (Wu et al., 2019; Klicpera et al., 2018; Xu et al., 2018a) 경험적으로 증명됐다.
a two-layer-fully-connected neural networks 이 구현에서 좋은 선택임을 보여주었다. 마찬가지로 본 논문의 AdaGCN 또한 GCN layer를 직접적으로 심층시키는 대신 각 layer에서 적절한 변혼 함수 f를 선택하는 방향으로 가려고 한다.
따라서, 우리는 expensive joint optimization of multiple parameter matrices 를 피하기 위해 ReLU 함수를 제거할 것이다.
마찬가지로, Simplified Graph Convolution (SGC) (Wu et al., 2019) 또한 GCN layers 간의 비선형성은 중요하지 않으며 이익의 대부분은 neighboring features의 local weighting으로 부터 발생한다고 주장한다.
SGC는 아래(2)와 같다:
$$ Z = {\hat{A^{l}}XW^{(0)}W^{(1)}...W^{(l-1)} = \hat{A^{l}}X\tilde{W}} ...................(2)$$
GCN에서 ReLU의 중요한 영향은 ReLU가 직관적으로 수축 매핑이기 때문에 행렬 곱셈의 수렴을 가속화해준다.
따라서 ReLU 작업을 제거하면 앞서 언급했던 Oversmooting도 완화될 수 있다(Li et al., 2018).
또한 ReLU가 없으면 SGC는 앞서 언급한 joint optimization over multiple parameter matrics 문제를 피할 수 있어 계산상의 이점을 얻을 수 있다. 그럼에도 불구하고, 본 논문에서는 그래프 컨볼루션에서 이러한 유형의 선형 변환을 쌓는 것은 고차 이웃의 정보를 나타내는 데 충분한 힘을 가지고 있지 않다는 것을 발견했으며 이는 부록 A.2에 설명된 실험을 참고바란다. 따라서 적절한 비선형 함수 fα, 예를 들어 two-layer fully-connected neural network을 활용하여 (2)의 선형 변환 \( \tilde{W} \)를 대체하고 AdaGCN에서 각 기본 분류기의 표현 능력을 다음(3)과 같이 향상시킬 것을 제안한다.
$$ Z^{(l)} = f_{\theta}(\hat{A^{l}}X) ...................(3)$$
- \(Z^{(l)} \) final embedding matrix (output logits before softmax) after the l-th base classifier in AdaGCN
(3) 공식은 AdaGCN의 l번째 base 분류기가 현재 노드와 그 노드의 이웃들의 l-th hop 의 features로부터 정보를 추출함을 의미한다. AdaGCN에서 l번째 base classifier의 함수는 기존 전통적인 GCN 모델에서 l-th layer과 유사하기 때문에, 본 논문에서는 l-th base classifier의 전체 부분을 AdaGCN이 l-th layer로 간주할 것이다.
다중 클래스 AdaBoost의 실현을 위해 우리는 SAMME (Stagewise Additive Modeling using a Multi-class Exponentialloss function) 알고리즘(Hastie et al., 2009)을 적용할 것이다.
Figure1에서 볼 수 있듯이,
우리는 현재 node feature와 l-th hop neighbors의 정보를 추출하기 위해 현재 weighted loss를 최소화함으로써 base classifier \( f_{\theta}^{(l)} \) 적용시킬 것이다. weighted error rate \( err^{(l)} \) 와 현재 base classifier \( f_{\theta}^{(l)} \)의 대응되는 weight \( \alpha^{(l)} \) 는 아래(4,5)와 같다.
$$ err^{(l)} = \sum_{i=1}^{n} w_{i}I(c_{i} \neq f_{\theta}^{(l)} (x_{i})) / \sum_{i=1}^{n} w_{i} ...................(4)$$
$$ \alpha^{(l)} = log(\frac{1- err^{(l)}}{err^{(l)}}) + log(K-1) ...................(5)$$
(4)... 오분류된 관측값들의 가중치들의 합 / 전체 가중치들의 합 => 오분류 가중치 비율 (5)...
(4),(5) 계산으로 나온 값은 가중치가 올바른 방향으로 업데이트가 될 수 있도록 해준다.
(4),(5) 계산 후, 잘못 분류된 노드의 가중치는 up, 옳게 분류된 노드의 가중치는 down 시켜 아래(6)와 같이 업데이트 시킨다.
$$ w_{i} \leftarrow w_{i} \cdot exp(\alpha^{(l)} \cdot I(c^{i} \neq f_{\theta}^{(l)}(x_i))), i= 1,2,...,n ...................(6)$$
우리는 가중치들을 정규화 시킨 후, 다음의 base classigier \( f_{\theta}^{(l+1)}\) 의 이웃들의 l+1th hop 정보들을 순차적으로 추출하기 위해 \( \hat{A}^{l+1}X = \hat{A}\cdot(\hat{A}^{l}X) \) 를 계산할 것이다
기존 AdaBoost와는 다르게 AdaGCN은 오직 하나의 \( f_{\theta} 를 정의하며 예를 들어 two-layer fully 연결된 신경망이다. 이는 실제로 RNN과 비슷하게 재귀적으로 각각의 base classifier를 최적화한다.
즉, 마지막 base classifier의 매개 변수가 다음 base classifier의 초기화에 활용되며 이는 이웃의 l+1 hop이 직접적으로 이웃의 l th hop과 연결되어 있다는 우리의 직관과 일치한다.
또한 우리는 AdaBoost 방식으로 이웃들의 다른 차수로부터의 예측을 결합하여 최종 예측 C(A,X)를 얻는다. (7)
$$ C(A,X) = \underset{k}{argmax} \sum_{l=0}^L \alpha^{(l)}f_\theta^{(l)}( \hat{A}^{l}X)...................(7)$$
마침내, 우리는 아래에서 AdaGCN의 간결한 형태를 얻는다.
$$ \hat{A}^{l}X = \hat{A} \bullet (\hat{A}^{l-1}X) $$
$$ Z^{(l)} = f_\theta^{(l)}(\hat{A}^{l}X) $$
$$ Z = AdaBoost(Z^{(l)} $$
명심할 것은 \(f_{\theta} \) 는 선형함수를 사용한 SGC에서 비선형함수를 사용해 표현력을 높였다.
Figure1을 보면 알 수 있듯이, AdaGCN은 동시에 발생하는 일련의 input과 output을 가진 RNN의 변형이다.
2.2 Comparison with existing methods
Architextural Difference
Figure1,2를 보면 GCN과 SGC, AdaGCN 의 아키텍쳐가 어떻게 다른지 확인할 수 있다.
\( Z_{l} \) 를 순차적으로 전달하여 최종 예측을 계산하는 기존 GCN 방식과 비교했을 때,
우리의 AdaGCN은 이웃들의 다른 hop들의 features \(\hat{A}^{l}X \) 통합한 노드들이 가중치 \( w_{i} \)을 전송한다.
더 중요한 것은, AdaGCN에서 \( Z_{l} \) 임베딩은 네트워크의 계산 flow와 독립적이며, 희소 인접 행렬 \( \hat{A} \) 또한 직접적으로 개별 네트워크 계산에 관여하지 않는다는 것이다. 왜냐하면 우리는 \( \hat{A}^{l+1}X \) 를 미리 계산한 다음 \( \hat{A} \) 대신에 f_\theta^{(l+1)} classifier에 넣을 것이기 때문이다. 그러면 계산 시간을 상당 시간 감소시킬 수 있다. 이는 Section3에서 자세히 언급할 것이다.
Connection with PPNP and APPNP
크고 조정 가능한 이웃의 정보를 사용하기 위한 그래프 컨볼루션을 재구성하고자 개인화
AdaGCN과 PPNP(Personalized Propagation of Nueral Predictions), APPNP(Approximate PPNP)
댓글