$D^{-1/2}$는 어떤 방법으로 구해야 할까? np.ndarray와 np.matrix의 차이
Graph Convolutional Network를 사용하면 아래와 같은 수식을 이용하게 된다.
$$
Z=\tilde D^{-{1\over2}}\tilde A\tilde D^{-{1\over2}}X\Theta
$$
이때, 인접행렬 $A$에 대해 $\tilde A=A+I$이고, $D$는 의 차수 행렬로 다음과 같다.
D = np.diag(np.sum(A, axis=0))그냥 $A$의 행벡터의 합으로 나타나는 열벡터를 대각성분으로 한 행렬로 보면 된다.
$\tilde D$는 $\tilde A$의 차수행렬로, 크게 다르지 않다. 다음과 같이 구할 수 있다.
D_tilde = np.diag(np.sum(A + np.eye(A.shape[0]), axis=0)앞으로 코드상에선 편하게 $\tilde A, \tilde D$를 A, D로 표현하겠다.
그렇다면 문제는, $\tilde D^{-{1\over2}}$를 어떻게 구할 것이냐이다. np.ndarray로는 정상적인 결과가 나오지 않는다.
예시 그래프는 아래 그림과 같다.
그래프 구조만 가져왔다. 레이어에 대한 건 모른다.
>>> import numpy as np
>>> A=np.array([[1, 1, 0, 0], [1, 1, 1, 1], [0, 1, 1, 0], [0, 1, 0, 1]])
>>> D = np.diag(np.sum(A, axis=0))
>>> D
array([[2, 0, 0, 0],
[0, 4, 0, 0],
[0, 0, 2, 0],
[0, 0, 0, 2]])
>>> D ** -0.5
__main__:1: RuntimeWarning: divide by zero encountered in power
array([[0.70710678, inf, inf, inf],
[ inf, 0.5 , inf, inf],
[ inf, inf, 0.70710678, inf],
[ inf, inf, inf, 0.70710678]])RuntimeWarning이 뜨며 대각 성분을 제외하고는 np.inf로 채워진다. 당연한 일이다.
그러나 np.matrix를 이용하면 다르다.
>>> D_mat = np.matrix(D)
>>> D_mat ** -0.5
Traceback (most recent call last):
...
TypeError: 'float' object cannot be interpreted as an integer
...
TypeError: exponent must be an integer
>>> np.sqrt(D_mat ** -1)
matrix([[0.70710678, 0. , 0. , 0. ],
[0. , 0.5 , 0. , 0. ],
[0. , 0. , 0.70710678, 0. ],
[0. , 0. , 0. , 0.70710678]])np.matrix는 실수 제곱이 안되나보다. 그래도 np.sqrt를 통해 깔끔하게 구할 수 있다.
애초에 np.array([[ ... ]]) 선언처럼 np.matrix([[ ...]])도 가능하니까, 차수행렬은 np.matrix로 사용하는 게 낫지 않을까? 생각할 수 있다. 근데 여러모로 해보니 아니더라. 여러 방법을 실험해봤다.
>>> import time
>>> def calc_time(func, iter_count):
... start_time = time.time()
... for _ in range(iter_count):
... func()
... return time.time() - start_time
...
>>> def f1():
... D = np.matrix([[2, 0, 0, 0], [0, 4, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]], dtype=float)
... return D ** -1
...
>>> def f2():
... D = np.matrix([[2, 0, 0, 0], [0, 4, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]], dtype=float)
... return np.sqrt(D ** -1)
...
>>> def f3():
... D = np.array([[2, 0, 0, 0], [0, 4, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]], dtype=float)
... D = D ** -0.5
... D[D == np.inf] = 0
... return D
...
>>> def f4():
... D = np.array([[2, 0, 0, 0], [0, 4, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]], dtype=float)
... return np.diag(np.diag(D) ** -0.5)
...
>>> calc_time(f1, 100000)
4.86509108543396
>>> calc_time(f2, 100000)
5.1881632804870605
>>> calc_time(f3, 100000)
__main__:3: RuntimeWarning: divide by zero encountered in power
1.0402328968048096
>>> calc_time(f4, 100000)
1.1342542171478271matrix는 $D^{-1}$을 구하는 것조차도 매우 느리다. array가 5배 가량 빠른 걸 확인할 수 있다.
왜 그런 걸까? 검색해서 찾아본 결과를 대충 요약하자면 np.matrix는 Matlab의 matrix를 억지로 numpy로 옮겨온 경향이 강하다고 한다. numpy는 ndarray에 가장 최적화되어 있다고 한다.
그런 이유도 있겠지만, 한가지 의심이 드는 게 있다.
위 코드를 보면 f3에서는 zero division이라 뭔가 스킵되면서 매우 빨랐을 것이고(뇌피셜), f4는 대각 성분만 연산하여 빨랐을 것 같은 느낌이 든다. 그렇다면 matrix는 zero division에 대응하면서 모든 요소를 다 연산해서 느린 건 아닐까? 하는 생각이 든다. 그래서 실험해봤다.
>>> def f5():
... D = np.matrix([[2, 0, 0, 0], [0, 4, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2]], dtype=float)
... return np.diag(np.diag(D) ** -0.5)
...
>>> calc_time(f5, 100000)
1.7843999862670898예상이 맞았다. 분명 ndarray가 matrix보다 빠르다. 그러나 matrix도 스마트하게 쓰면 충분히 빠르게 쓸 수 있을 거라 생각한다.
물론 난 앞으로 matrix를 굳이 쓸 일이 없을 것이다.
나라면 f4를 쓰겠다. RuntimeWarning도 없으며 코드가 간결하고, f3에 비해 속도차이가 그리 크지 않기 때문이다.
비슷한 글들