[논문 리뷰] Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (NeurIPS 2016)

지동환·2022년 10월 3일

AI CNN GNN Graph CNN paper-review

Paper-review

목록 보기

2/7

Graph CNN

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Papers with Code - ChebNet Explained

https://github.com/mdeff/cnn_graph

NIPS 2016

Introduction

CNN은 여러 분야에서 성공을 해 왔지만, Graph와 같은 비유클리드 공간에서 기존의 방법이 직접적으로 적용될 수 없다. 그래서 복잡한 기하학적 구조를 Spectral graph theory 같은 수학적 도구를 사용해 처리했다.

CNN을 그래프에 일반화 하기 위해서는 localized graph filter를 정의하는게 중요하다.

이 연구의 주요한 기여는 다음과 같다.
1. Spectral formulation - Graph 신호 처리 도구들에 기반한 Graph CNN의 이론 성립
2. Strictly localized filters - 반경 K에 엄격하게 들어오는 localized 가능
3. Low computational complexity
4. Efficient pooling
5. Experimental results

제안된 기술은 다음 세가지이다.

그래프에 대한 localized convolutional filter 디자인
유사한 vertices에 대한 graph coarsening 과정
spatial resolution를 낮추고 높은 filter resolution을 얻는 graph pooling

1. Learning Fast Localized Spectral Filters

Graph Fourier Transform

본 논문은 푸리에 변환의 문제점을 개선했다. 그 전에 푸리에 변환이 무엇인지 간략히 설명한다.

spectral graph analysis에서 중요한 분석은 graph Laplacian에 대한 분석이다.

이는 $L=D-W\in \mathbb{R}^{n\times n}$ 으로 정의된다.

여기서 $D\in\mathbb{R}^{n\times n}, D_ii = \sum_j W_{ij}$ 로 정의된다.

그리고 정규화 된 정의는 $L=I_n - D^{-1/2}WD^{-1/2}$ 이다.

Spectral filtering of graph signals

vertex domain에서는 의미 있는 translation operator를 정의할 수 없으므로, Fourier domain에서 이를 정의한다.

y=g_\theta(L)x = g_\theta (U\Lambda U^T)x=Ug_\theta (\Lambda) U^T x

여기서 non-parametric filter는 다음과 같이 정의된다.

g_{\theta}(\Lambda)=\mathrm{diag}(\theta)

$\theta \in \mathbb{R}^n$ 은 Fourier coefficients이다.

Polynomial parametrization for localized filters

non-parametric filter에는 두 가지 문제가 있다.

space에 대해 localized 되지 않았다.
학습 시간 복잡도가 $\mathcal O(n)$ - 데이터의 차원이다.

이러한 문제들은 polynomial filter를 사용함으로서 해소될 수 있다.

g_\theta(\Lambda) = \sum^{K-1}_{k=0} \theta_k \Lambda^k

Filter $g_\theta$ 에서 vertex $i$ 를 중심으로 하는 vetex $j$ 의 값은 $(g_\theta(L)\delta_i)_j = (g_\theta(L))_{i,j} = \sum_k \theta_k (L^k)_{i,j}$ 이고, kernel이 Kronecker delta function $\delta_i\in\mathbb{R}^n$ 에 따라 localized 된다.

Kronecker delta function이란? $\delta_{ij}\in\{0,1\} \\ \delta_{ij} = \begin{cases}1&i=j \\ 0 & i\neq j\end{cases}$ 로 정의되는 함수. 변수가 하나인 경우에는 일반적으로 다음과 같이 정의된다. $\delta_i = \delta_{i0}=\begin{cases}1&i=j \\ 0 & i\neq j\end{cases}$

$d_{\mathcal G}(i,j)>k$ 가 $(L^K)_{i,j}=0$ 을 의미하기에, ( $d_\mathcal{G}$ 는 최단 거리) Laplacian의 $K^{\mathrm{th}}$ -order 다항식은 정확히 K-localized 되어 있다.

이에 더해 학습의 시간 복잡도가 filter가 지원하는 크기인 $\mathcal O(K)$ 이고, 일반적인 CNN과 같다.

Recursive formulation for fast filtering

polynomial filter를 사용해서 localized filter를 학습했지만, 여전히 시간 복잡도가 ${O(n^2)}$ 로 높다. → Fourier Basis $U$ 를 곱해야 하기 때문에.

이런 문제를 해결하는 방법은 ${g_\theta(L)}$ 를 polynomial function으로 파라미터화 하는 방법이다.

GSP 문제에서 가장 전통적인 방법은 Chebyshev expansion을 사용하는 것이다.

그렇다면 시간 복잡도가 ${\mathcal O(K|\mathcal{E}|)}$ 가 된다. → L의 cost가 sparse 하기 때문에. (L이 재귀적으로 K번 계산되기 때문에 $K \times L$ 이다.)

g_\theta(\Lambda)=\sum^{K-1}_{k=0} \theta_k T_k (\tilde{\Lambda})

filtering 연산이 $y=g_\theta(L)x=\sum^{K-1}_{k=0} \theta_k T_k (\tilde{L})x$ 로 다시 작성되고, 전반적인 시간 복잡도는 ${\mathcal O(K|\mathcal{E}|)}$ 이 된다.

Learning filters

sample s의 $j^\mathrm{th}$ output feature map은 다음과 같다.

y_{s,j}=\sum^{F_{in}}_{i=1} g_{\theta_{i,j}} (L) x_{s,i} \in \mathbb{R}^n

$x_{s,i}$ 는 input feautre maps이고, Chebyshev coefficients $\theta_{i,j}\in\mathbb{R}^k$ 의 vector $F_{in}\times F_{out}$ 은 layer의 학습 가능한 parameter이다.

back propagation 학습을 할 때 계산해야 하는 Gradient는 다음 두 가지이다.

\frac{\partial E}{\partial \theta_{i,j}} = \sum^S_{s=1}[\bar{x}_{s,i,0},...,\bar{x}_{s,i,K-1}]^T \frac{\partial E}{\partial y_{s,j}} \quad\quad \mathrm{and} \quad\quad \frac{\partial E}{\partial x_{s,i}} g_{\theta_{i,j}}(L) \frac{\partial E}{\partial y_{s,j}} \quad\quad\quad\quad\quad

$E$ 는 $S$ samples의 mini-batch의 loss energy이다.

이 계산들은 $\mathcal O (K|\mathcal{E}| F_{in} F_{out}S)$ 의 비용으로, $K$ spare matrix-vector multiplications과 하나의 dense matrix-vector multiplication으로 나눠질 수 있고, tensor 연산으로 병렬 처리가 가능하다. 결국 $[\bar{x}_{s,i,0},...,\bar{x}_{s,i,K-1}]$ 은 한 번만 계산되면 된다.

2. Graph Coarsening

pooling 연산을 위해서 그래프에서 유사한 vertices를 cluster 하는 과정이 필요하다.

이를 여러 층에 행하는 것은 local 기하학적 구조를 보존하면서 multi-scale clustering을 하는 것과 동일하다. 그렇지만 이는 NP-hard 문제로 알려져 있어서, approximation이 사용되어야 한다.

여러 Clustering 기법들이 있지만 우리는 Graclus multilevel clustering algorithm을 사용하겠다.

3. Fast Pooling of Graph SIgnals

Pooling 연산은 많이 실행되고, 효율적이어야 한다.

coarser graph는 원래 그래프와 어떤 의미 있는 연관도 없다. (정렬이 제대로 안 되어 있어서)

그렇기 때문에 이 둘을 서로 짝 지어주는 테이블이 필요하다. 이는 메모리를 잡아먹고, 비효율적이고, 느리고, 병렬화 되기 어렵다.

그렇지만 1D pooling 만큼 효과적으로 graph pooling이 작동할 수 있게 하는 정렬 방법이 있다.

두 가지 단계로 진행되는데,

balanced binary tree를 만들고
vertices를 rearrange한다.

Conclusion

GSP에서 사용되는 도구들을 바탕으로 효율적이고 일반화된 grph에 대한 CNN을 도입했다.

이전에 비해 filter가 더 엄격하게 local하게 적용될 수 있고, 이는 Graph Fourier basis의 직접적인 사용을 피해 계산상 더 효율적이고, 실험적으로 더 나은 정확도를 보였다.

제기되는 세 가지 우려

데이터의 차원에 선형적인 계산 복잡도를 가지는 모델을 도입했다.
input graph의 질이 매우 중요하다는 점을 확인했다.
그래프가 잘 설계되어 있다면, 모델에 의해 만들어진 local stationarity (정상성)와 compositionality (구상성)에 대한 통계적인 추론이 text 문서를 위해 검증되었다.

Futer work

GSP에서 새롭게 개발된 도구를 바탕으로 개선
자연스럽게 그래프의 형태로 만들어지는 데이터에 적용
CNN 파라미터와 graph 대한 학습을 대체

저자가 뭘 해내고 싶어했는가?

Spectral GCN (https://arxiv.org/abs/1312.6203)의 fourier coefficient의 polynomial식을 더 stable하게 개조했다.

CNN은 유클리드 공간에 있는 데이터에 대해서는 매우 좋은 성과를 냈다.

그렇지만 Graph 공간에서 적절한 localize graph filter를 정의하는 방법이 없었기에 Graph에 CNN을 적용하기에는 어려움을 겪었다.

저자는 Chebyshev expansion을 사용해 빠르고 localized된 필터를 만들어 낼 수 있었다.

이 연구의 접근에서 중요한 요소는 무엇인가?

Chebyshev polynominal를 사용해 시간이 오래 걸리는 연산을 효율적으로 근사했다.

연산이 오래 걸리는 Fourier basis에 대한 직접적인 계산을 피해 갔다.

이해가 안 된 부분은 무엇인가?

Digital Signal Processing 분야에 배경 지식이 없어서 이해하는데 어려움이 있었다.

Applied and Computational Harmonic Analysis 에서 Laplacian이 정확히 K-localized 된다는 부분이 잘 이해가 되지 않는다. 어째서?

마지막 Learning filters 부분도 잘 이해되지 않는다.

내가 참고하고 싶은 다른 레퍼런스에는 어떤 것이 있는가?

Spectral Networks and Locally Connected Networks on Graphs

Deep Convolutional Networks on Graph-Structured Data

F. R. K. Chung. Spectral Graph Theory, volume 92. American Mathematical Society, 1997
I. Dhillon, Y. Guan, and B. Kulis. Weighted Graph Cuts Without Eigenvectors: A Multilevel Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 29(11):1944–1957, 2007