GNN

GNN(Graph Neural Network) - 1. 그래프 개념

jsmak 2025. 1. 4. 17:16

 

GNN(Graph Neural Network, 그래프 신경망)은 데이터와 그 관계를 그래프 구조로 표현하고 이를 처리하기 위한 기계 학습 모델입니다.
그래프는 노드(Node == 정점 vertex)와 그들을 연결하는 엣지(Edge, 간선)로 구성된 데이터 구조입니다.
GNN은 딥러닝에서 그래프 구조 데이터를 학습할 수 있도록 설계된 신경망입니다.
실제 세계에는 그래프로 표현되는 데이터가 많아 GNN에 대한 관심이 높아지고 있습니다.
예를 들어, 소셜 네트워크, 물리학에서의 상호작용 네트워크, 화학 분자의 구조 등이 그래프로 표현될 수 있습니다.

GNN은 합성곱 신경망(CNN)을 그래프 데이터에 맞게 일반화한 것으로 볼 수 있습니다.
CNN은 주로 격자 구조(예: 이미지 데이터)를 처리하는 데 사용되지만, GNN은 다양한 비정형 데이터(예: 그래프 데이터)를 처리할 수 있는 더 범용적인 기술로 여겨집니다.

 

1. Node와 Edge

1) Node (노드)
정의: 그래프에서 하나의 데이터 단위를 나타내는 객체로, 정점(Vertex)이라고도 합니다.
예시: SNS를 그래프로 나타낼 때, 한 명의 유저가 Node로 표현됩니다.
     그림에서 A, B, C, D와 같은 파란색 원이 노드를 나타냅니다.

2) Edge (간선)
정의: 그래프에서 두 노드 간의 직접적인 연결 관계를 나타냅니다.
예시: SNS 상의 친구 관계는 Edge로 표현됩니다.
     그림에서 표현: A와 B 사이의 선이 Edge를 의미합니다.
     두 노드가 Edge로 연결되어 있을 때, 이를 "두 노드는 인접(Adjacent)해 있다"라고 표현합니다.

 

그래프는 다음과 같은 수식으로 표현할 수 있습니다:
G = ( V, E, u )

  • G: 그래프 자체를 나타냅니다.
  • V (Vertex): 그래프의 노드(Node)를 나타내는 집합입니다.
    • 예: SNS에서 각각의 유저를 노드로 표현.
  • E (Edge): 그래프의 간선(Edge)을 나타내는 집합으로, 노드 간의 연결 관계를 의미합니다.
    • 예: SNS에서 유저 간의 친구 관계를 표현.
  • u (Feature vector): 각 노드가 가지는 특징량 벡터로, 노드에 대한 추가적인 정보를 포함합니다.
    • 예: SNS의 경우, 각 유저의 나이, 성별, 국적 등을 나타냄.

 

2.그래프의 유형


1. 방향성 그래프 (Directed Graph), 방향성 없는 그래프 (Undirected Graph)
   (1) 방향성 그래프: 엣지가 방향을 가지며, 관계가 일방적임.(digraph라로 합니다)
       예: 트위터 팔로우 관계 (A → B).
   (2) 방향성 없는 그래프: 엣지가 방향을 가지지 않으며, 관계가 상호적임.
       예: 페이스북 친구 관계 (A ↔ B).

2. 가중치 그래프 (Weighted Graph), 가중치 없는 그래프 (Unweighted Graph)
   (1) 가중치 그래프: 엣지가 숫자 값을 가지며, 관계의 강도나 중요도를 나타냄.
       예: 도로 네트워크에서 거리 또는 비용.
   (2) 가중치 없는 그래프: 엣지가 단순히 존재 여부만 나타냄.
       예: 단순 연결 관계.

3.연결된 그래프 (Connected Graph)
  그래프의 모든 노드가 경로를 통해 서로 연결되어 있음.
  부분 연결 그래프: 그래프 내에 연결되지 않은 컴포넌트가 존재함.
   예: 소셜 네트워크에서 연결되지 않은 사용자 그룹.

4. 동적 그래프 (Dynamic Graph), 정적 그래프 (Static Graph)
   (1) 동적 그래프: 시간에 따라 노드와 엣지가 추가되거나 제거되는 그래프.
       예: 네트워크 트래픽, 실시간 소셜 네트워크.
   (2) 정적 그래프: 그래프 구조가 고정되어 변하지 않는 그래프.
       예: 화학 분자의 구조.

 

3. NetworkX

networkx는 파이썬에서 그래프(Graph)네트워크 데이터를 생성하고, 시작화 할 수 있는 라이브러리입니다.

각 그래프를 하나씩 시각화 해보겠습니다.

 

(1) 방향성 없는 그래프(Undirected graph)

방향성 없는 그래프는 nx.Graph()를 사용하여 정의할 수 있고, nx.draw_networkx()로 시각화 할 수 있습니다.

import networkx as nx
g = nx.Graph()
g.add_edges_from( [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'B')])
nx.draw_networkx(g)

(2) 방향성 있는 그래프(Directed graph)

방향성 있는 그래프 코드도 유사합니다. nx.Graph() 대신 nx.DiGraph()를 사용합니다.

A,B가 양방향일 경우는 (A,B)와 (B,A) 2개를 입력하면 됩니다.

import networkx as nx

g = nx.DiGraph()
g.add_edges_from( [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'B'), ('B', 'A')])
nx.draw_networkx(g)

(3) 가중치가 있는 그래프(weighted graph)

세계의 공항을 나타내는 그래프를 그릴 때 (서울, 도쿄)와 (서울, 뉴욕) 공항을 단순히 선으로 연결할 때 비행시간을 가중치로 표시할 수 있습니다. 시작과 종료 노드에 dictionary 추가하여 가중치를 나타낼 수 있습니다.

import networkx as nx
wg = nx.Graph()
wg.add_edges_from( [('A', 'B', {'w':10}), ('A', 'C', {'w':10}), ('B', 'D', {'w':30}), ('C', 'B', {'w':20})])
label = nx.get_edge_attributes(wg,'w')
pos = nx.spring_layout(wg) 
nx.draw_networkx(wg, pos = pos)
nx.draw_networkx_edge_labels(wg, pos=pos, edge_labels=label);

 

(4) 연결된 그래프(Connected Graph)

경로(path) : 한 노드에서 다른 노드 까지 인접해 있지 않지만 다른 노드들을 경유에 연결되어있을 경우, 이를 경로라고 합니다.

알로리즘에서 그래프의 두 노드들 간에 거리가 가장 짭은 경로를 찾는 문제를 최단경로 찾기 문제들도 있습니다.

 

그래프틑 여러개의 노드와 엣지를 갖는데, 그래프 안의 모든 노드들이 경로를 통해 연결되지는 않습니다.

몇개의 그룹으로 연결되어있거나, 연결이 없이 고립된 노드가 있는 그래프도 있습니다.

networkx에서는 그래프가 연결되어있는지를 확인하기 위한 내장함수를 제공합니다.

import networkx as nx
g = nx.Graph()
g.add_edges_from( [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'B')])
print(nx.is_connected(g))
nx.draw_networkx(g)

import networkx as nx
g = nx.Graph()
g.add_edges_from( [('A', 'B'), ('A', 'C'), ('E', 'D'), ('C', 'B')])
print(nx.is_connected(g))
nx.draw_networkx(g)