그래프는 adjacency matrix로 표현될 수 있는데, 이 adjacency matrix는 node의 순서 (ordering)가 바뀜에 따라 같은 그래프를 표현하더라도 다르게 표현될 수 있다. Permutation invariance와 permutation equivariance는 그래프에서 노드의 ordering이 바뀔 때 function의 output이 어떻게 바뀌는지를 설명한다. 이번 글에서는 permutation invariance와 permutation equivariance가 각각 무엇이고, 둘의 차이점이 무엇인지에 대해 알아보겠다.
Permutation invariance
Permutation invariance는 adjacency matrix의 순서가 바뀌더라도 그 output이 변하지 않는 함수의 특성을 말한다. 이를 식으로 표현하면 다음과 같다.
위 식에서 A는 adjacency matrix, P는 행과 열의 순서를 바꾸는 permutation matrix이다. 위 식은 위에서 설명한 것처럼 adjacency matrix 내의 노드의 순서가 바뀌어도 함수의 결과가 바뀌지 않는다.
이에 해당하는 예시로는 그래프 내 노드들의 degree 합이 있을 것이다. f가 그래프 내 노드들의 degree의 합을 나타내는 함수라고 하자. 노드들의 degree의 합은 adjacency matrix 내의 행과 열의 순서가 바뀌더라도 항상 같을 것이다. 그러므로 이 함수는 permutation invariant하다고 할 수 있다.
Permutation equivariance
Permutation equivariance는 adjacency matrix의 순서가 바뀌는대로 output의 순서도 바뀌는 함수의 특성을 말한다. 이를 식으로 표현하면 다음과 같다.
예를 들어, f가 각 노드의 degree를 나타내는 함수라고 하자. 각 노드의 degree는 adjacency matrix 내의 노드 순서가 바뀜에 따라 그 순서가 바뀐 그대로 노드의 degree는 유지하며 출력될 것이다. 그러므로 이 함수는 permutation equivariant하다고 할 수 있다.
이번 글에서는 permutation invariance와 permutation equivariance에 대해 알아보았다. 이를 보장하는 것은 graph neural network를 학습할 때에 중요한 요소로 활용된다. 예를 들어, 어떤 노드의 특성을 학습하는데 노드의 순서가 바뀐다고 해서 해당 노드의 학습되는 특성이 달라져서는 안 될 것이기 때문이다.
References
1. Hamilton. William L., Graph Representation Learning.
최근댓글