[Paper] GCN

“semi-supervised classification with graph convolutional networks”이란 논문에 대한 리뷰입니다.

원문은 링크에서 확인할 수 있습니다.

Key 1. Semi-supervised

모든 data를 사용할 수 있는 것도 아니고, label이 다 있지도 않기에 label 정보를 사용하는 supervised loss만 사용하면 manifold가 nonlinear한 형태로 휘어있습니다. 이걸 manifold regularization을 하게 해주고 이 때 unlabeled data도 사용하게 되어서 semi supervised 프레임워크를 사용하게 됩니다.

key 2. GCN

단순히 node의 feature dim만을 바꾸는 것에서, convolution과정이 추가됩니다. Convolution의 filter를 생각하면 local area에 대해서만 연산이 진행되고, 이 때 사용된 weight param은 어디에서든 동일한 것처럼, GCN에서 사용되는 filter는 graph의 local information을 반영하여 node의 latent repre.를 조정하게 되어서 Convolution이란 특징이 부각됩니다.

local information

Adjacency matrix에 Identity Matrix를 추가하는 등 일종의 변환을 거친 Matrix는 local한 지역에서 connectedness를 알려주게 됩니다. 이것이 바로 convolution의 역할을 하는데 왜 그런 역할을 하는지를 설명하고 있습니다.

Key 3. Spectral Graph Convolution

graph Laplacian을 spectral decomposition을 하게 된다면 node간의 local환 관계중 의미 있는 값을 기준으로 설명하는 graph Fourier가 진행이 됩니다.

단 decomposition의 time complexity가 문제가 되어 해결하는 것이 Chebyshev polynomial입니다. 이 때 polynomial의 order을 1로 정한다면 결과적으로 localized information을 알려주는 형태로 estimate이 가능하게 되고, 이 때의 order는 central node에서 maximum step값으로 생각해도 됩ㄴ디ㅏ.

그리고 몇가지 (free) parameter에 대한 가정을 하는데 이 때 e.value의 최대값이 2라는 가정으로 scaling이 되어 gradient가 unstable하게 됩니다. 그래서 여기에 대해 조정해주는 값을 사용하면 궁극적으로 convolved signal을 안정적으로 반환하게 되는 것