[GNN] MixHop architecture

https://arxiv.org/abs/1905.00067

MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing

Summary

MixHop은 기존의 GCN의 문제점을 보여주고 그를 개선하는 방법을 제시하는 논문이다. multi-hop feature represention을 power of adjacency matrix를 통해서 aggregate한다는 점이 특징이다. 

 

---

기존 GCN의 문제점

기존 GCN 논문(Kipf & Welling, 2017)은 효율적인 graph convolution 방법을 제시하지만 문제점이 존재했다. 첫 번째로, GCN 모델에서는 계산량을 줄이기 위해 Chevyshev approximation을 사용하는데, 이것이 model의 representational capacity를 낮춘다. 이를 특히 Gabor 형태의 filter를 학습할 수 없는 문제에서 잘 드러난다.

Gabor filter

Gabor filter는 image processing에서 사용하는 linear filter 중 하나이다. 이미지에 적용하여 외곽선, 패턴이나 질감을 추출하는 데에 사용한다. 이는 인간의 시각 처리 방식과 유사하다고 여겨져 널리 사용된다. Gabor filter는 Gaussian wave에 의해 변조된 형태의 sine 곡선으로 볼 수 있다. 따라서 특정 방향과 frequency에 대해 강하게 나타날 수 있다.

Figure 1. Gabor filter의 예 [4]

이런 Gabor 형태의 filter는 hierarchical한 형태로 object representation을 하는 데 중요하다. 실제로 CNN에서 activation을 확인해 보면 앞 layer의 경우 Gabor filter와 비슷한 형태로 활성화 되어 있는 것을 알 수 있다. Graph와 같이 데이터 형태에서 Gabor 형태의 filter를 구성하는 것은 중요하다.

---

Contribution of this Paper

이 paper에서 다루고 있는 method인 MixHop 모델은 neighborhood information을 각 message passing step에서 full linear mixing할 수 있도록 한다. 

 

Figure 2 [1]

위 Figure 2를 보면, 기존 GCN은 한 번 message passing을 할 때 immediate neighbor의 feature만 aggregate한다. 반면 MixHop model에서는 feature vector가 여러 hop 떨어져 있는 neighbor의 feature로 concatenate하는 방식으로 aggregate하는 것을 볼 수 있다. 

 

즉, 다음과 같다. 

 

1. Delta Operator를 formalize하고 이의 general한 형태인 Neighborhood Mixing의 expressiveness를 분석했다.
2. MixHop model을 제안한다. 
3. 다양한 형태의 MixHop model을 학습하는 방식을 제안하여 compact한 GCN architecture를 만들 수 있게 한다. 

---

MixHop model

MixHop model의 형태는 아주 간단하므로 먼저 소개하고 이 모델의 의미를 풀어보자. 

 

일반적으로 message passing에서는 한 번에 immediate neighbor(first-degree neighbor)에게서만 latent representation을 받아서 aggregate한다. 하지만 MixHop에서는 한 번에 여러 degree의 neighbor들의 representation을 받을 수 있다. 이는 다음 형태로 가능하게 된다.

 

$$  H^{(i+1)} = \bigg| \bigg|_{j\in P} \sigma\left(\hat A ^j H^{(i)}W_j^{(i)} \right) $$

 

여기서의 $||$는 column wise로 concatenation한 것을 의미하고, $\hat A^j$는 adjacency matrix $\hat A$가 $j$ 번 곱해진 것을 의미한다. 즉, 만약 $P = \{ 0, 1, 2\}$로 되어 있다면 기존 GCN과 같은 형태에서 adjacency matrix의 0승, 1승, 2승을 계산한 것을 단순히 concatenation한 것 뿐이다. 

 

adjacency matrix를 $n$번 곱하면, 총 $n$ hop 떨어져 있는 node까지도 결과인 power of adjacency matrix에서 연결된다. $j$가 3이라면 거리가 3인 node까지도 연결된 상태로 반영되는 것이다. 이를 concate시키면 $P$ 안의 $j$ hop 떨어진 feature representation까지 모두 반영하게 되는 것이다. 

 

Figure 3 : GCN layer와 MixHop layer [1]

Figure 3을 보면, 구조는 완전히 동일한데 GC layer에서 결과값이었던 $H^{(i)} \in \mathbb R^{n\times s_i}$가 $|P|$만큼 나오므로 그를 concatenation한 것이 전부이다. 이때 weight matrix $W$는 각 $|P|$마다 다르다. 크기도 다를 수 있지만, default setting에서는 모두 같게 설정하고, 이를 L2 Group Lasso를 이용해 optimize할 수 있다. 

 

위의 MixHop layer를 BatchNorm, element-wise activation, Dropout과 함께 쌓아 MixHop CGN을 구성할 수 있다. 이때 논문에서 learning에 대해 discuss한 점들을 먼저 살펴보고, MixHop이 왜 강력한지 확인해보도록 하자.

---

Output Layer

GCN의 마지막 layer은 latent space를 학습하므로 가장 중요하다. MixHop도 여러 정보를 mix하므로 output layer를 constraining하는 것이 효과가 있을 것이라고 보고 output layer를 다음과 같이 정의하였다 : 

 

$$ \tilde Y_O = \sum _{k=1} ^{s_l/c} q_k H_{*, (id_l/c\ :\ (i+1)s_l/c)} ^{(l)}  $$

 

위 수식은 논문에 나온 형태를 그대로 서술한 것이나, 오타가 있는 것으로 보인다. 다음과 같이 수정해야 의미가 올바르게 전달될 것이다.

 

$$\begin{align} &let\ C = s_l / c  \\  &\tilde Y_O = \sum _{k=1}^C H^{(l)}_{*, ((k-1)C:kC)}\end{align} $$

 

위 수식 작성에는 MLV 김현우 교수님과 랩 선배들께서 감사하게도 도움을 주셨다. 

 

의미를 살펴보면, 마지막 layer의 latent representation $H^{(l)}$는 다음과 같은 형태일 것이다. 

 

Figure 4 : 마지막 latent representation matrix

implementation을 살펴보면, 저 column 크기는 단순히 임의의 값은 아니고, classification task에서는 class의 개수가 된다. 즉, 그 전의 $s_l$의 크기가 class의 개수의 배수가 되어야 한다. 

 

각설, 이 matrix를 모두 더해준다. 이때 곱해주는 scalar $q_k \in [0,1]$은 output of softmax인 distribution으로, weighted sum을 만드는 역할을 한다. 이것은 model이 더 가중치를 두고 싶은 feature에 weight를 부과하도록 만든다. 

---

Learning Adjacency Power Architectures

각 layer와 power에 따라 사용되는 weight matrix는 다른 값이다. 이때 $W_j^{(i)}$는 dataset과 task에 따라서 다른 크기가 더 적합할 수 있다. 이를 자동으로 조절할 수 있는 방식을 제안한다. 

 

직접 architecture를 search하는 것은 이 모델에서는 expensive하다. 따라서 Group Lasso regularization을 이용하여 architecture를 train한다. 

 

Group Lasso

나의 경우 Group Lasso는 생소한 개념이었으므로 추가로 정리한다. 

 

먼저 Lasso는 다음과 같이 정의된다 : 

 

$$ \begin{align} &\text{minimize}_{\beta_0 , \beta } \left \{ \sum_{i=1}^N (y_i - \beta_0 - x_i^\top \beta)^2\right \} \\ & \text{subject to }  \sum^p_{j=1} |\beta_j | \le t \end{align}$$

 

이를 Lagrangian으로 쓰면 $ L = || \sum_{i=1}^N (y_i - \beta_0 - x_i^\top \beta)^2 ||^2 + \lambda \sum^p_{j=1} |\beta_j | $ 이 되고 이를 minimize하면 일반적인 Lasso가 된다. vector를 이용해서 표기하면 더 간단하게 다음과 같이 표기할 수 있다. $\hat \beta ^{\text{LASSO}} (\lambda) = \arg \min_\beta (||Y-X\beta||^2+\lambda||p||_{l_1})$

 

여기까지가 일반적으로 알고 있는 Lasso의 개념이다. Lasso는 여러 parameter가 골고루 작아지는 것 보다는 파라미터를 선택하는 형태로 작용하여 sparse한 solution이 나오도록 유도한다. 

 

Group Lasso의 식은 위와 유사하다. 

 

$$ {1\over 2} \bigg |\bigg |  Y-\sum ^J_{j=1} X_j \beta_j \bigg|\bigg|  ^2 + \lambda \sum^J _{j=1} \sqrt{p_j} || \beta_j ||$$

 

weight vector의 값들을 묶어서 몇 개의 group으로 만들 수 있다. 이 때의 group은 특별히 어떤 의미를 가지는 것으로 설정해야 하는 것은 아니며, 자유롭게 만들 수 있다. 이렇게 만든 각각의 group들을 $\beta_1, \beta_2 , \cdots, \beta_J$라고 하자. 이때 constraint만 한 beta의 group에 대해서 설정할 수 있다. 이 경우 $\sqrt {p_l}$은 $\beta_j$의 weight의 개수를 의미한다. 

 

만약 하나의 group만 존재할 경우에는, Ridge가 되고, 각 group에 하나의 원소만 존재할 경우에는 Lasso가 된다. 

 

Figure 5 : (a-d) : Lasso, (e-h) Group Lasso (i-l) Ridge [5]

위 그림을 살펴보면, 왼쪽 column이 Lasso고 오른쪽 column이 Ridge이며 가운데가 Group Lasso이다. 가운데 column을 살펴보면 group인 $\beta_{11}$과 $\beta_{12}$ 사이에서는 Ridge처럼 전체적인 값을 줄여주는 방식으로 동작하지만, $\beta_1$과 \beta_2$의 다른 그룹 간에서는 sparsifying하는 방식으로 동작하는 것을 볼 수 있다. 

 

이를 $\beta$ plane에 매핑시켜 보면 위와 같은 형태가 된다. 

 

Figure 6 [6]

Figure 6처럼 Lasso는 주로 하나의 parameter를 없애는 방식(sparsify)으로 동작할 가능성이 높다. 반면 Ridge에서 그럴 가능성은 희박하다. 

 

architecture 학습 방식으로 돌아가 보자.

 

1. depth만 설정하여 wide network를 설정한다. (200 dimension 등으로 설정한다)
2. L2 Group Lasso regularization을 적용한다. 이때 각 group은 $W_j^{(l)}$의 각 column이다. 이 경우 대부분의 W column이 0에 가깝게 된다.
3. validation accuracy가 가장 높을 때 L2 norm을 측정한다. threshold를 설정하여 이보다 높은 column만 count한다. 
4. k th percentile보다 낮은 것을 제거한다.
5. L2 Group Lasso를 L2 regularization으로 바꾸고 training을 다시 한다. 

즉, 처음 regularizer를 L2 Group Lasso로 적용한다. 그리고 특정 weight 이하인 weight column들을 제거한다. threshold는 마음대로 조절할 수 있지만, 논문에서는 GCN 모델과 같은 크기가 될 때까지 조절하였다. 

 

이렇게 학습할 경우 다음과 같은 형태가 된다 : 

 

Figure 7 [1]

Group Lasso Regularization에 따라서 각 dataset이 어떻게 weight의 크기를 조절했는지 볼 수 있다. 각 dataset에 따라 다른 크기의 weight가 선택된 것을 볼 수 있다. 특히 Cora 데이터셋에서는 second GC layer의 0-power of adjacency matrix에 zero-capacity를 부여한 것을 볼 수 있다. 이는 다른 형태의 graph dataset에 다른 형태의 architecture가 optimal하다는 것을 보여준다. 

---

Analysis

저자들이 기존 GCN에 비해서 MixHop이 개선되었다고 주장한 부분은 representational capacity에 관한 것이다. [2]에서 제안된 GCN을 vanilla GCN이라고 하자. vanilla GCN을 생각해 보면, spectral graph convolution을 하는데 matrix multiplication과 eigenvalue decomposition이 포함되어 있어 computation complexity가 지나치게 증가해서, Chebyshev rank-2 approximation으로 계산량을 줄인다. 또한 Chebyshev polynomial에서도 두 coefficient의 곱이 -1이라는 가정, renormalization trick으로 계산을 simplify하고 exploding/vanishing gradient 문제를 해결한다. 자세한 내용은 이전에 내가 정리해 놓은 것을 참고하면 좋다. 

 

그러나 이러한 simplying은 convolution이 단순한 neighborhood averaging operator가 되도록 만들었다. 즉, $H^{(i+1)} = \sigma(\hat A H^{(i)} W^{(i)}$에서 볼 수 있듯이 단순히 normalized adjacency matrix로부터 새로운 feature를 계산하는 것이다. 이런 형태는 Delta Operator를 표현할 수 없다는 문제가 있다. Delta operator의 정의는 다음과 같다 : 

 

Definition 1 Representing Two-hop Delta Operator 

model은 다음과 같은 injective mapping $f$와 parameter 세팅이 존재할 때 two-hop Delta Operator를 표현할 수 있다. 

$$f (\sigma(\hat A X) - \sigma (\hat A^2 X)) $$

given any adjacency matrix $\hat A$, features $X$, and activation function $\sigma$. 

 

즉, model이 이 operator를 학습할 수 있다는 것은 neighbor간 feature의 difference를 표현할 수 있음을 의미한다. 예컨대, 소셜 네트워크에서 social circle의 boundary에 있는 사용자들을 표현할 수 있다. [7] 인기 많은 독일인 친구를 둔 미국인을 생각해보면, immediate friend 중에는 영어 화자가 많을 것이다. 하지만 friends-of-friends에는 독일어 화자가 많을 것이다. 이런 사용자는 영어와 독일어를 대조하는 filter를 사용함으로써 표현할 수 있을 것이다. 

 

Representational Complexity

저자들이 주장하는 것은, MixHop 모델은 Delta Operator를 학습할 수 있지만, Vanilla GCN은 여러 layer로 쌓아도 이런 class의 operation을 학습할 수 없다는 것이다. 이를 Theorem 1과 Theorem 2로 쓰고 증명한다.

 

Theorem 1 The vanilla GCN defined by Equation 2 is not capable of representing two-hop Delta Operators.

 

Theorem 2 MixHop GCN can represent two-hop Delta Operators.

 

자세한 증명과정은 논문을 참조하기 바란다. 간단히 이야기하자면, Theorem 1은 vanilla GCN을 여러 layer로 stack했을 때의 수식을 $\hat A W^*$로 reduce한다. 이때 injective mapping $\hat A W^* = f(\hat A - \hat A^2)$가 존재한다고 가정하자. 그러면 identity matrix가 adjacency matrix인 경우 $IW^* = f(0)$이고, power해도 값이 변하지 않는 특정 matrix $\hat C_{1,2}$의 경우에도 $\hat C_{1,2} W^* = f(0)$이다. 이를 통해 모든 row들이 동일함을 보이고, $f$가 rank 1 이하의 matrix임을 보인다. 따라서 $f$는 injective mapping이 아니므로 two-hop Delta Operator를 represent할 수 없다. 

 

Theorem 2의 경우에는 적절한 weight의 조합으로 두 layer 이후의 feature representation에서 two-hop Delta Operator를 represent할 수 있음을 보여준다. 

 

General Neighborhood Mixing

이는 Delta Operator의 좀 더 general한 버전을 학습할 수 있는가에 대한 discussion이다. 즉, 임의의 $\alpha_0, \alpha_1, \cdots , \alpha_m$와 injective mapping $f$에 대해서 output of the network가 $f(\sum^m_{j=0} \alpha_j \sigma(\hat A^j X))$와 같으면 표현할 수 있는 것이다. 

 

이것도 GCN은 representation이 가능하지 않고 MixHop은 capable하다. GCN의 경우에는 위의 증명이 반례가 되어 자동으로 증명되고, MixHop의 경우에도 위와 비슷하게 적절한 weight의 조합으로 증명할 수 있다. 

 

Computational Complexity

한 가지 주목할 점은 위의 representational한 특성에도 불구하고 computational complexity가 vanilla GCN에 비해서 커지지 않았다는 것이다. 매번 새로운 $\hat A^j$를 계산할 필요가 없다. 이것은 어찌 보면 당연한데, $P=\{ 1, 2, 3, 4\}$인 경우, 이 power of matrix들을 계속 직접 계산할 것이 아니라 가장 큰 값인 $j_\max$를 계산하는 과정에서 얻어지는 것이기 때문이다. 자세한 것은 아래 pseudocode를 보면 이해가 갈 것이다.

 

Algorithm 1

위 알고리즘은 간단한데, 그냥 $j_\max$가 될 때까지 left side에 matrix multiplication을 해 주고, 필요한 경우 저장한 뒤 마지막에 concatenation하는 것을 의미한다. 이렇게 할 경우 time complexity가 $O(j_{\max } \times m \times s_i )$가 되는데, 논문에서는 $j_{\max } \ll m$ 이고 $s_l \ll m$ 인 현실적인 setting 하에서는 $O(m)$으로 쓸 수 있고, 따라서 $l$ layer를 돌릴 때 $O(lm)$가 된다고 하고 있다. 이는 vanilla GCN과 동일한 time complexity이다. 

 

 

---

Experiemental Results

실험은 두 종류의 데이터에 대해서 semi-supervised node classification task에 대해 진행했다. 

 

Synthetic Graph Results

 

Figure 8 [1]

위 결과는 Synthetic dataset에 대해서 수행된 결과이다. homophily는 같은 label neighbor끼리 연결된 edge의 비율을 의미한다. MixHop이 모든 homophily에서 가장 성능이 좋고, 특히 homophily가 낮을 때 좋은 성능을 보여준다. 

 

Figure 9 [1]

homophily에 따라서도 Delta Operator가 학습되었다. 특히 homophily가 낮을 수록 Delta Operator를 학습하는 데에 많은 model capacity를 사용하였다. 이는 Figure 8에서 낮은 homophily에 MixHop이 좋은 성능을 보인 이유를 설명한다. 

 

Node Classification Results

Table 1 [1]

Tble 1은 common split에 대한 결과를 보여준다. P = {1}인 경우는 vanilla GCN과 동일한 architecture이므로 결과도 같다. capacity는 동일하게 설정했는데, 모든 데이터셋에서 SOTA 성능을 보여준다. 

 

Table 2 [1]

Table 2는 random partition의 경우를 보여준다. 이 경우에도 SOTA 성능을 보여준다. 

 

---

Conclusion

MixHop은 architecture도 있지만, 기존 GCN의 한계를 보여주었다는 점에서 의미가 있다. 또한 adjacency matrix의 power를 통해 multi hop neighbor를 파악하는 형태의 architecture였다. 

 

L2 Group Lasso regularization을 사용하여 graph마다 다른 architecture를 사용한 것도 중요한 포인트로 생각된다. 

 

이후의 논문에서도 이렇게 multi-hop neighbor의 feature representation을 aggregate하여 좋은 성능을 낼 수 있음의 가능성을 열어준 데에 의미가 있다. 

---

References

[1] Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., ... & Galstyan, A. (2019, May). Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning (pp. 21-29). PMLR.

 

[2] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.

[3] Wikipedia contributors. (2023). Gabor filter. Wikipedia. https://en.wikipedia.org/wiki/Gabor_filter

 

[4] Shah, A. (2023, April 23). Through The Eyes of Gabor Filter - Anuj shah (Exploring Neurons) - Medium. Medium. https://medium.com/@anuj_shah/through-the-eyes-of-gabor-filter-17d1fdb3ac97

 

[5] Yuan, M., & Lin, Y. (2006). Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B-statistical Methodology, 68(1), 49–67. https://doi.org/10.1111/j.1467-9868.2005.00532.x 

 

[6] Wikipedia contributors. (2023b). Lasso (statistics). Wikipedia. https://en.wikipedia.org/wiki/Lasso_(statistics)

 

[7] Perozzi, B., & Akoglu, L. (2018). Discovering communities and anomalies in attributed graphs. ACM Transactions on Knowledge Discovery From Data, 12(2), 1–40. https://doi.org/10.1145/3139241

 

 

 

 

Footnotes