Graph의 Spectral Filtering에 대해 알아보자. loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $G$의 normalized Laplacian matrix를 $L^{norm}$ 이것의 대각화 표현을 $L^{norm}=U \Lambda U^T$이라고 하자 (참고글: Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유). 지난 글 (Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의)에서 봤듯이 $L^{norm}$의 eigen value는 인접한 vertex들의 차이가 얼마나 인지 (변화정도)를 나타내는 frequency 역할을 한다고 하였고 이러한 변화정도를 파악하기 위하여 vertex를 표현하는 vector를 spectral domain 상으로 옮겨서 분석하는 Graph Fourier Transform에 대해 알아보았다. 각각의 frequency $\lambda$에 대응하는 성분이 있을 텐데 특정 frequency $\lambda$에 대하여 집중하는 정도를 달리하기 위하여 Spectral Filtering을 정의한다.
Graph의 Spectral Filtering
Spectral Filtering에 대해 알기 위해서는 Graph convolution (Graph Convolution (그래프 컨볼루션)에 대하여)에 대해 알고 있어야 겠다. 길이가 $|V|$인 두 벡터 $k,x$가 있을 때 $k$와 $x$의 graph convolution 은 아래와 같이 정의 한다.
$$k *_{G} x = U\left(U^T k \odot U^T x\right) = UKU^Tx, \text{ 여기서 } K=diag(U^Tk)$$
만약에 위에서 $k$를 고정하고 $k$와의 convolution을 이용해서 $x$에 대한 함수를 만들고 싶다면 $K=diag(U^Tk)$만 잘 정의하면 된다. $x$를 각각의 원소가 vertex를 표현하는 숫자인 벡터라면 $K$에 의한 Convolution을 아래와 같이 정의한다.
$$K *_{C} x = UKU^T x \tag{spectral filtering}\label{spectral filtering}$$
위의 $K$에 대한 convolution을 이용해 vertex들의 표현 $x$을 입력하는 함수( 혹은 시스템)이 만들어지고 이것을 Graph의 Spectral Filtering 이라고 부르고 $K$를 kernel이라고 부른다. 주의할점은 여기서 $K$가 diagonal matrix라는 것이다. ($\ref{spectral filtering}$)에서 보듯 vertex를 표현하는 vector $x$를 Fourier Transform에 의해 spectral domain으로 옮기고 spectral domain에서 행렬을 곱해서 조작을 한 이후 다시 graph의 표현으로 inverse fourier transform을 하기 때문에 spectral filtering이라고 부르는 것 같다.
Spectral Filtering의 효과
위에서 spectral filtering을 이용하면 어떤 효과가 나타날까? 결론부터 말하면 각각의 주파수 성분이 달라질 수 있다. Kernel $K=diag(k_i)$를 사용한 spectral filtering이 있다고 하자. $L^{norm}$의 eigen value를 $\lambda_i$라 하고 이것에 대응되는 orthonormal eigen vector들을 $u_i$라고 표현하자. $x$를 각각의 원소가 각각의 vertex를 표현하는 숫자로 구성된 길이 $|V|$짜리 벡터라고 하자. $u_i$는 orthonormal basis이므로 $x = \sum_{i} c_i u_i$를 만드는 $c_i$가 존재한다. $x$를 입력으로 넣을 때 $K$에 의한 spectral filtering 결과를 $y= K*_{C} x $라고 표현하자. 약간의 계산을 이용하면 아래와 같은 결과를 얻을 수 있다.
$$y=\sum_{i} k_i c_i u_i$$
위에서 보듯이 각각의 주파수 $\lambda_i$의 성분 $c_i$가 spectral filtering 에 의해 $k_i c_i$로 변경된 것을 확인할 수 있다. 인접한 vertex간의 변화정도를 측정한 $y^TL^{norm}y$를 측정하면 아래와 같아진다.
$$x^T L^{norm} x = \sum_{i} c_i^2 \lambda_i \to y^T L^{norm} y = \sum_{i} (k_i c_i)^2 \lambda_i $$
위에서 보듯이 $K$에 의한 spectral filtering을 지나면 인접한 vertex간의 변화정도가 달라지는 것도 알 수 있다.