[Graph Neural Networks] Graph in Traditional ML scheme

Graph Neural Network에 대해 본격적으로 알아보기에 앞서, GNNs가 등장하기 전에는 그래프 구조를 어떤 방식으로 기계학습에 활용했는지 간단히 살펴보겠습니다. 그리고 문제를 쉽게 이해하기 위해서 directed graph는 배제하고 undirected graph에서 생각하도록 하겠습니다. 

 

전통적인 관점에서 그래프를 활용한다는 것은 결국, 노드/링크/그래프 구조에서 특징(feature)을 추출하여 기계학습 모형에 적용한다는 개념입니다. 우리가 풀고자 하는 문제가 어떤 문제냐에 따라 크게 3가지 측면에서 접근할 수 있습니다. 

 

1) 노드 레벨(Node-Level Tasks): 

Node degree: 노드 \(v\)의 차수 \(k_v\)는 해당 노드가 가지는 엣지(이웃 노드)의 수입니다.

Node centrality: 노드 중심성(Node centrality)은 그래프에서 노드의 중요도를 반영합니다.

• Eigenvector centrality: 노드 \(v\)는 중요한 이웃 노드들로 둘러싸여 있을 때 중요한 노드로 간주됩니다: \[ \sum_{u \in N(v)} C_u \rightarrow C_v \quad (\text{A: normalization constant, largest eigenvalue of } A) \]

       Recursive equation을 행렬꼴로 변형:

       \[ A \cdot c = \lambda \cdot c \]

       여기서 \(A\)는 인접 행렬(Adjacency Matrix), \(c\)는 중심성 벡터(centrality vector),

       \(\lambda\)는 고유값(eigenvalue)입니다.

       가장 큰 고유값 \(\lambda_{\max}\)는 항상 양수이며 유일합니다 (Perron-Frobenius 정리에 의하여).

       가장 큰 고유값 \(\lambda_{\max}\)에 대응하는 고유벡터 \(c_{\max}\)가 중심성 계산에 사용됩니다.

• Betweenness centrality: 노드가 많은 최단 경로의 중간에 위치해 있을 때 중요한 노드가 됩니다: \[ C_B(v) = \frac{\# \text{(shortest paths between } s \text{ and } t \text{ that contain } v)}{\# \text{(shortest paths between } s \text{ and } t)} \ \]
• Closeness centrality: 노드는 모든 다른 노드까지의 최단 경로가 짧을 때 중요합니다: \[ C_C(v) = \frac{1}{\sum_{u} \text{(shortest paths length between } u \text{ and } v)} \]

• 클러스터링 계수(Clustering Coefficient): 노드 \(v\)의 이웃 노드들이 얼마나 서로 연결되어 있는지를 나타냅니다: \[ e_v = \frac{\# \text{(edges among neighboring nodes)}}{\# \text{(node pairs among } k \text{ neighboring nodes)}} \]

 

Graphlet : Clustering coefficient는 triangle을 세는 것으로 볼 수 있습니다. 그러면 이것을 일반화 할 수는 없을까요?

그것이 graphlet입니다. graphlet의 정의는 아래와 같습니다. "Small subgraphs that describe the structure of node u’s network nationhood."

 

2) 엣지 레벨(Edge level Tasks)

• 임의로 누락된 link
• 시간의 흐름에 따른 link의 변화

 

3) 그래프 레벨(Graph level Tasks)

그래프 전체 또는 부분 그래프(sub graph)에 대한 예측

 

 

feature를 뽑아내면 이것을 다른 ML모델의 input으로 활용한다는 것이지요. 사실 저도 석사학위 때 degree centrality를 계산해서 논문에 적었던 적이 있습니다. 이렇게 graph의 metric을 계산해서 feature 로서 포함하는 방법은 아무래도 한계가 있겠죠? 그럼 어떻게 그래프 구조를 충분히 활용할 수 있는지는 다음 포스팅에서 차차 설명하겠습니다.