Predict then Propagate: Graph Neural Networks meet Personalized PageRank 라는 논문을 읽다가 흥미로운 technique 이 있어서 포스팅하게 되었습니다.
위의 논문에서는 graph 의 scaled down 된 normalized weighted adjacency matrix $A$ 에 대하여 $(I - A)^{-1}v$ 를 계산하는 phase 를 모델의 학습과정에서 포함하게 됩니다.
$(I - A)^{-1}v$ 는 $(I - A)$ 의 inversion 을 계산한 뒤 $v$를 곱하는 naive 한 방법으로 구하게 되면 $O(N^3)$ ($N$ 은 그래프 정점의 개수) 시간이 걸립니다.
또한, matrix 의 inversion 을 구하는 과정에서 dense matrix 를 관리 해야 하기 때문에 $O(N^2)$ 의 공간 복잡도를 소비하게 됩니다.
이는 현실에 존재하는 많은 graph에 대해서 비현실적인 계산량을 요구하게 됨을 의미합니다.
하지만 만약 $A$가 sparse matrix 라면(주어진 graph가 sparse graph 라면) $A$의 sparse함을 이용하여 복잡도의 개선을 가져 올 수 있을 것입니다.
논문에서는 Neumann Series 의 성질을 이용해 아주 획기적으로 시간 복잡도와 공간 복잡도를 개선하여 현실적으로 사용할 수 있는 모델을 완성합니다.
Neumann Series 란, 행렬 $T$에 대해 $\sum_{k=0}^{\infty}{T^k}$ 를 의미합니다.
만약, Neumann Series 가 수렴하면, $(I - T)^{-1} = \sum_{k=0}^{\infty}{T^k}$ 를 만족합니다.
이러한 성질을 이용하면 적당히 큰 $K$ 에 대해, $\sum_{k=0}^{K}{T^k}$ 를 $(I - T)^{-1}$ 의 근사값으로 사용할 수 있다는 것을 알 수 있고 이러한 이유로 논문에서는 $\sum_{k=0}^{K}{A^k}v$ 를 구하고자 하는 값인 $(I - A)^{-1}v$ 의 근사값으로 사용하기로 합니다.
한편, $\sum_{k=0}^{K}{A^k}v$ 의 값은 아래와 같은 점화식의 $K$번째 항을 계산함으로써 빠르게 구할 수 있습니다.
$h_0 = v$
$h_k = Ah_{k-1} + v$
이 점화 관계를 계산하는 시간 복잡도는 $O(M)$ 이므로 총 시간복잡도는 $O(MK)$ 가 됩니다. ($M$ 은 $A$의 nonzero element 의 개수이고 sparse함을 가정했으므로 $M << N^2$ 를 만족. $K$는 실험적으로 10정도만 되어도 오차가 적다고 함.)
또한, 계산 과정에서 dense matrix 를 다루는 상황이 전혀 생기지 않으므로 공간 복잡도 또한 $O(M)$ 으로 굉장히 합리적임을 알 수 있습니다.