[CS224W] Node Degree & Node Centrality

GNN 공부를 위한 내용 정리입니다.
CS224W Winter 22/23 자료를 기준으로 내용을 정리했습니다.

 

이번에는 Node Feature 중 Node Degree와 Node Centrality에 대해 정리를 해보겠습니다.

 

 

전통적인 ML 파이프라인에서는 딥러닝과 달리 Task 를 수행하기 위해 Task 에 맞는 Feature를 설계해야 Modeling을 할 수 있었습니다.

 

 

즉, 그래프에 효과적인 Feature(x)를 사용하는 것이 모델의 좋은 성능을 달성할 수 있는 중요한 부분이었기 때문에 전통적인 ML 파이프라인에서 사람이 직접 Feature를 설계했습니다.

따라서 이번 포스팅에서는 전통적인 ML을 위해 Feature를 다루는 방법 중 Node Level Task를 위한 Node Degree와 Node Centrality에 대해 설명을 진행해 보겠습니다.

그리고 이해를 도울 수 있도록 Undirected Graph만 다뤄서 해당 내용을 진행합니다.

 

 

Node-level Feature를 알아보기 전에 Node-level Task에 대해 먼저 알아보면 대표적으로 Node Classification이 있습니다.

Node Classification은 가장 간단하게 위 그림에서 회색으로 된 노드가 초록색일지, 빨간색일지 맞추는 Task라고 생각하면 될 것 같습니다.

 

 

그럼 지금부터는 본격적으로 Node Feature를 다뤄보겠습니다.

Node Feature의 목적은 그래프 내 노드의 위치와 구조를 모델이 학습할 수 있도록 특징화(characterize)해주는 것입니다.

Node Feature는 대표적으로 Node degree, Node centrality, Clustering coefficient, Graphlets 4가지가 있습니다.

앞서 말씀드렸지만 오늘 포스팅에서는 4가지 중 Node Degree와 Node Centrality에 대해서만 설명을 진행해 보겠습니다.

 

 

먼저, Node degree입니다.

사실 Node degree는 1주차에서 다룬 내용과 동일합니다.

특정 노드에 연결된 Edge의 수를 의미하며 노드 A에 연결된 Edge의 수는 1이기 때문에 A에 대한 Node degree는 1이 되며, 마찬가지의 방법으로 B에 대한 Node degree는 2, C에 대한 Node degree는 3, ... 이 되는 것입니다.

Node degree는 가장 간단한 Node Feature 중에 하나로 모든 인접 노드(직접적으로 연결된 노드)를 동등하게 취급한다는 특징이 있습니다.

 

 

다음으로는 Node Centrality입니다.

앞서 설명한 것처럼 Node degree는 모든 인접 노드를 동등하게 취급하여 노드의 중요도를 고려하지 못합니다.

따라서 노드의 중요도를 고려하기 위해 Node centrality를 고려하게 되었습니다.

Node centrality는 다시 대표적으로 Eigenvector centrality, Betweeness centrality, Closeness centrality가 있으며, 그밖에 더 많은 centrality가 존재합니다.

CS224W에서는 Eigenvector centrality, Betweeness centrality, Closeness centrality 3가지 centrality만 다루고 있습니다.

 

 

첫 번째로 Eigenvector centrality입니다.

해당 파트를 공부하면서 '왜 Eigenvector 인가?'를 고민하는 데 시간을 많이 할애했습니다.

사실 Eigenvector와 Eigenvalue가 포함된 선형대수학 공부를 열심히 해야 알 수 있지만 시간이 많이 부족해서 일단 이번에는 centrality에 초점을 맞춰서 설명하고 넘어가려 합니다.

(Eigenvector와 Eigenvalue에 대한 꼼꼼한 설명은 언제가 될지 모르지만 추후 다른 포스팅으로 진행해 보겠습니다 :D)

따라서 먼저 의미론적으로 살펴보면 Eigenvector centrality는 이웃 노드의 중요도로 나의 중요도를 판단하겠다는 것입니다.

어떤 노드 A가 있을 때 노드 A의 이웃들의 중요도를 확인해서 이웃의 중요도가 높으면 노드 A 역시 중요도가 높은 것입니다.

저희 지도 교수님께서 GNN 수업을 진행해 주시는데 수업 당시 교수님께서는 '어떤 A라는 사람이 블랙핑크 제니를 알면 A라는 사람 역시 중요하다'라고 보는 것이 Eigenvector centrality라고 이해시켜주셨습니다.

그럼 지금까지는 의미론적으로 살펴봤다면 이제는 수식으로 살펴보겠습니다.

 

 

위 수식을 통해 어떤 노드 v의 centrality는 노드 v의 모든 이웃의 centrality를 합한 후 λ로 나눠준 값이 노드 v의 Eigenvector centrality 임을 보여줍니다.

그런데 이 식을 보면서 '그럼 초기 centrality는 어떻게 계산되는 거지?'라는 의문을 가지게 되었습니다.

해당 의문에 대한 답변은 GNN과 관련된 개념에 대해 자세히 설명해 주시는 '유니의 공부' 블로그를 통해 이해할 수 있었습니다.

GNN을 공부하시는 분들은 해당 블로그를 참고하시면 정말 큰 도움이 될 것 같습니다.

 

유니의 공부

 

node centrality 내용도 아래에 함께 링크를 남겨두겠습니다.

 

Node degree와 Node centrality 설명 (betweenness centrality, closeness centrality, eigenvector centrality)

 

다시 본론으로 돌아와서 '그럼 초기 centrality는 어떻게 계산되는 거지?'라는 의문에 대한 대답은 adjacency matrix의 Eigenvector가 centrality vector가 되는 것입니다.

그런데 이 설명은 사실 다음의 수식을 보면 조금 더 명확해질 수 있습니다.

 

 

왼쪽의 수식을 오른쪽의 형태로 변환하면 A는 adjacency matrix가 되는 것이고, c는 adjacency matrix의 centrality vector가 되는데 이 부분이 바로 각 노드의 centrality 값을 vector로 표현한 것입니다.

그리고 오른쪽의 수식이 바로 Eigenvector 정의와 같습니다.

즉, 초기 centrality에 대한 고민 자체가 불필요한 고민이었던 것 같습니다.

​

여기까지 여러 자료를 통해 설명을 해보았지만 사실 저 역시도 깔끔하게 이해된 느낌은 아니었습니다.

그래서 직접 계산을 해보면 깔끔하지 않을까 생각하여 직접 계산을 해보았습니다.

계산을 위해선 고유값과 고유벡터의 수식을 먼저 보는 게 좋습니다.

 

&&Ax = λx​&&

&&$Ax-\lambda x=0$Ax−λx=0​&&

&&$\left(A-\normal{1}{I}\ \lambda \right)x=0$(A−I λ)x=0​&&

 

그럼 이제 위의 수식과 A, B, C, D 4개의 노드를 가지는 임의의 그래프를 활용해서 직접 계산을 해보겠습니다.

 

 

위 그림의 왼쪽은 4개의 노드를 가지는 임의의 그래프이고, 오른쪽 Matrix는 왼쪽 그래프의 Adjacency Matrix를 표현한 것입니다.

이를 활용해서 Eigenvalue와 Eigenvector를 계산해야 합니다.

직접 계산할 수도 있겠지만 3 x 3 이상의 정방행렬 고유값을 직접 계산하는 것은 생각보다 복잡하고, 시간이 꽤 걸리기 때문에 사이트를 이용하여 계산해 주겠습니다.

아래의 사이트를 참고하여 계산하면 됩니다.

 

고유 값과 고유 벡터

 

 

계산 결과 고유값이 가장 큰 네 번째의 Eigenvector가 Eigenvector centrality가 되며 B 노드와 D 노드의 값이 1로 가장 중요한 노드임을 알 수 있습니다.

직접 계산하는 부분에 대한 힌트는 '나의 큰 O는 log x야' 블로그를 통해 얻을 수 있었습니다.

역시 링크를 남겨두겠습니다.

 

[네트워크 이론] 다양한 중심성(Centrality) 척도들

 

두서없이 설명했지만 결국 중요한 것은 이웃의 중요도를 고려하기 위해 Eigenvector centrality를 활용한다는 것입니다.

앞선 여러 설명을 기억하기보단 이웃의 중요도를 고려한다는 큰 개념만 가지고 넘어가면 될 것 같습니다.

 

 

사실 Eigenvector centrality가 가장 어렵고, 이제부터는 비교적 간단합니다.

또한 CS224W 자료에 예시도 포함되어 있기 때문에 가볍게 생각하고봐주시면 됩니다.

그래서 Betweenness centrality에 대해서 설명드리면 서로 다른 노드 간의 shortest path 위에 자주 있으면 중요한 노드라고 보는 centrality입니다.

즉, 노드와 노드의 경로 사이에 특정 노드를 많이 거쳐가면 그 특정 노드가 중요할 것이라고 생각하는 것입니다.

그럼 모든 shortest path를 고려해 보겠습니다.

A-C-B, A-C-D, A-C-D-E, B-D-E, C-D-E

노드 A는 거쳐가는 경우가 없기 때문에 centrality가 0이 되고, B와 E 역시 마찬가지로 centrality는 0입니다.

하지만 노드 C는 총 3번 거쳐가기 때문에(A-C-B, A-C-D, A-C-D-E) 노드 C의 centrality는 3이 됩니다.

마찬가지로 노드 D 역시 총 3번 거쳐가기 때문에(A-C-D-E, B-D-E, C-D-E) 노드 C와 마찬가지로 centrality가 3이 됩니다.

 

 

마지막 순서인 Closeness centrality입니다.

앞선 Betweenness centrality와 같이 쉽기 때문에 가볍게 보시면 될 것 같습니다.

노드가 다른 모든 노드와의 거리가 짧을수록 중요도가 높다고 보는 centrality입니다.

CS224W의 예시로 보면 먼저, 노드 A는 A-C(1), A-C-B(2), A-C-D(2), A-C-D-E(3)으로 모든 노드와의 거리를 계산할 수 있고 이를 활용하여 centrality를 계산해 보면 아래와 같습니다.

 

&&$c_A=\frac{1}{1+2+2+3}=\frac{1}{8}$cA​=11+2+2+3​=18​&&

 

---

이번 포스팅에서는 Node-level Feature로 활용되는 Node Degree와 Node Centrality에 대해 알아봤습니다.

마지막으로 요약하면 아래와 같습니다.

 

Node Degree	노드에 연결된 Edge의 수를 의미하며 직접적으로 연결된 노드를 동등하게 취급하여 이웃 노드의 중요도를 고려할 수 없다.
Node Centrality	Node Degree의 이웃 노드의 중요도를 고려할 수 없는 단점을 극복하기 위해 활용된다.
	Eigenvector Centrality	이웃 노드의 중요도가 높으면 중요한 노드이다.
	Betweenness Centrality	거쳐가는 노드가 많을수록 중요한 노드이다.
	Closeness Centrality	모든 노드와의 거리의 합이 작을수록 중요한 노드이다.

 

틀린 부분 혹은 설명이 잘못된 부분은 가감 없이 알려주세요!

감사합니다:D