GNN(Graph Neural Network) - 7. GraphSAGE

GraphSAGE는 대규모 그래프를 처리하기 위해 설계된 그래프 신경망입니다.

GraphSAGE는 2017년 'Inductive Representation Learning on Large Graphs' 논문으로 발표되었습니다.

https://arxiv.org/pdf/1706.02216

Inductive Representation Learning on Large Graphs

논문 코드 : http://snap.stanford.edu/graphsage/

 

추론적(transductive)학습 vs 귀납적(inductive)학습

GraphSAGE 논문에서는 그래프 학습의 기존 방법인 추론적(Transductive) 접근법과 귀납적(Inductive) 접근법의 차이를 강조하며, GraphSAGE가 귀납적 학습(Inductive Learning)을 수행할 수 있음을 주장합니다.

1. 추론적(Transductive) 학습 
학습 데이터와 테스트 데이터가 모두 주어진 상태에서, 테스트 데이터에 대한 정보까지 사용하여 모델을 학습하는 방식입니다.
그래프 전체 구조를 활용하여 특정 노드의 예측을 수행하며, 테스트 데이터의 이웃 노드 정보도 학습에 포함됩니다.
모델은 모든 노드와 엣지 정보를 학습 단계에서 사용할 수 있지만, 새로운 노드가 추가되면 모델을 다시 학습해야 하므로 새로운 데이터에 대한 일반화가 불가능합니다.
큰 그래프의 경우 계산 비용이 매우 크며, 확장성이 떨어집니다.
예: GCN, GAT은 Laplacian 특성을 학습하기 때문에 추론적 접근에 속합니다.

2. 귀납적(Inductive) 학습
학습 데이터와 테스트 데이터가 분리되어 있으며, 학습 데이터로부터 일반적인 규칙과 패턴을 학습하여 새로운 데이터에도 적용 가능한 일반화된 모델을 만드는 방식입니다.
GraphSAGE는 이웃 노드 특성을 샘플링하여 임베딩을 생성하는 접근법으로, 귀납적 학습을 지원합니다.
각 노드의 임베딩 벡터를 개별적으로 훈련하지 않고, 노드와 로컬 이웃의 특징 정보를 집계하는 함수를 학습합니다.
이를 통해 새로운 노드나 그래프에서도 일반화된 임베딩을 생성할 수 있습니다.
GraphSAGE는 기존GCN의 추론적 특성을 귀납적 비지도 학습으로 확장한 개념입니다.

추론적 학습은 학습과 테스트 데이터를 모두 포함하여 특정 데이터에 대해 최적화되지만, 새로운 데이터에 일반화할 수 없습니다.
귀납적 학습은 학습 데이터에서 일반화된 패턴을 학습하며, 새로운 데이터에도 적용 가능해 확장성이 뛰어납니다.
GraphSAGE는 귀납적 접근을 통해 대규모 그래프나 새로운 데이터에 대한 일반화 성능을 제공합니다.

그래서 논문의 제목도  'Inductive Representation Learning on Large Graphs' 대규모 그래프에서의 귀납적 학습으로 지어져있습니다.

 

Neighbor sampling. aggregation

GraphSAGE는 크게 두가지 주요 구성요소로 구성됩니다.

1. 이웃샘플링(neighbor sampling)

2. 집계(aggregation)

 

다음은 논문 노드 임베딩 생성과 이웃샘플링 집계의 알고리즘입니다.

 

1-hop layer에서, 각 노드는 이웃 노드의 특성을 집계한 후 자신의 특성과 결합하여 임베딩을 생성합니다. 
이 과정을 다음 hop layer에서도 반복하며, 마지막 레이어에서는 학습된 노드 임베딩을 반환합니다.
"집계(aggregate)": 이웃 노드의 특성을 Mean, Max-Pooling, LSTM 등의 방법으로 집계합니다.
"결합(combine)": 자기 노드의 특성과 집계된 이웃 노드의 특성을 CONCAT하거나 다른 방식으로 결합합니다.
"반복(repeat)": 각 레이어에서 위 과정을 반복하여 점진적으로 더 깊은 이웃 정보를 포함한 임베딩을 생성합니다.

Input:
    - Graph G(V, E) with features {x_v, ∀v ∈ V}
    - Depth K (number of layers)
    - Weight matrices {W_k, ∀k ∈ {1, ..., K}}
    - Non-linearity σ
    - Neighborhood function N(v): returns neighbors of node v
    - Aggregator functions {AGG_k, ∀k ∈ {1, ..., K}}

Output:
    - Vector representations {z_v, ∀v ∈ V}

1. Initialize h_v^0 ← x_v, ∀v ∈ V
2. for k = 1 to K do
3.     for v ∈ V do
4.         h_N(v)^(k) ← AGG_k({h_u^(k-1), ∀u ∈ N(v)})
5.         h_v^(k) ← σ(W_k · CONCAT(h_v^(k-1), h_N(v)^(k)))
6.     end for
7. end for
8. z_v ← h_v^(K), ∀v ∈ V
9. Return {z_v, ∀v ∈ V}

x_v	입력노드 v의 특성(input)
N(v)	이웃 샘플링 , 노드v의 이웃 집합을 반환하는 함수
K	GraphSAGE 레이어 수 (또는 홉 수)
AGG_K	이웃노드의 특성을 집계하는 함수. Mean, Sum, Max, LSTM등
σ	활성화 함수
h_N(v)^(k)	노드 v의 이웃에서 집계된 특성
h_v^(k)	노드 v의 현재 레이어 k에서 계산된 특성
z_v	노드 v 최종 임베딩 (마지막 레이어의 특성 h_v^(K)​)

 

이웃샘플링(Neighbor sample)

GraphSAGE에서 데이터셋은 자신과 이웃 노드를 임베딩하여 사용합니다.

노드에 직접적으로 연결된 이웃노드를 1홉 이라하고, 이웃의 이웃은2홉이라고 합니다.

이웃이 많거나, 홉수가 많아지면 그래프가 지수적으로 커집니다.

그래서 GraphSAGE에서는 그래프의 모든 이웃을 추가하는 대신, 미리 정의된 수의 이웃을 샘플링 합니다.

예를 들어 1hop에서는 5, 2hop에서는 7의 이웃만 제한할 수 있습니다. (5*7=35)

모든 이웃노드가 학습되는 대신, 각 epoch마다 랜덤으로 이웃노드가 선택되어 랜덤워크(random walk) 기법으로 그래프구조가 학습됩니다.

이웃샘플링은 torch_geometric의 NeighborLoader 클래스에서 수행됩니다.

loader = NeighborLoader(
    data,
    num_neighbors=[5, 7],  # 2-hop에서 각각 최대 5, 7개의 이웃 샘플링
    batch_size=128,
    input_nodes=data.train_mask
)

 

집계함수(Aggregation)

집계 함수(Aggregation Function)는 각 노드의 이웃 노드 특성(neighbor features)을 집계(aggregate)하여 임베딩을 생성하는 역할을 합니다. 
집계 함수는 이웃 노드들의 정보를 하나로 통합하고, 이 결과를 자기 노드의 특성과 결합(combine)하여 노드의 임베딩을 업데이트하는 데 사용됩니다.

 

집계 함수의 요구 사항
1.불변성(Invariance):이웃 노드의 순서에 영향을 받지 않아야 함.
그래프는 정렬된 데이터가 아니기 때문에, 집계 함수는 입력 순서에 관계없이 동일한 결과를 반환해야 함.
2. 확장성(Scalability):대규모 그래프에서도 효율적으로 계산 가능해야 함.
따라서, 집계 함수는 모든 이웃 노드 정보를 사용하는 대신 샘플링된 이웃만을 기반으로 계산.
3.표현력(Expressiveness):다양한 그래프 구조와 노드 관계를 학습할 수 있는 충분한 표현력을 가져야 함.

 

GraphSAGE논문에서는 세가지 방법이 제안되었습니다.

1. Mean Aggregation (평균 집계)
이웃 노드의 특성을 단순히 평균(mean)하여 집계.
가장 간단한 집계 방식.
계산 비용이 낮으며, 효율적으로 작동.
복잡한 이웃 관계를 학습하기에는 한계가 있을 수 있음.

2. Pooling Aggregation (Max Pooling)
이웃 노드의 특성에 비선형 변환σ(W⋅h)을 적용한 뒤, 각 차원별로 최댓값(max)을 집계.
비선형 변환을 통해 더 풍부한 정보를 학습 가능.
특정 이웃 노드의 중요한 특성이 강조될 수 있음.F.nll_loss는 예측된 로그 확률(logP(y∣x))과 실제 레이블 사이의 손실을 계산합니다.

3. LSTM Aggregation
이웃 노드의 특성을 입력 시퀀스로 간주하고, LSTM 셀에 입력하여 집계.
순서 의존적인 집계를 수행하며, 이웃 노드 간의 관계를 더 복잡하게 학습 가능.
계산 비용이 높고, 이웃 노드 순서를 정렬해야 하므로 효율성 문제가 있을 수 있음.

 

손실함수 

논문에서 지도학습에서는 cross-entropy loss를 사용했습니다.

F.nll_loss는 예측된 로그 확률(logP(y∣x))과 실제 레이블 사이의 손실을 계산합니다.

 

비지도학습의 손실함수입니다.

노드 u와 이웃 노드 v의 임베딩 관계를 강화(positive pair)하고, u와 무관한 노드(negative sample) 간의 관계를 약화시켜 그래프 구조를 반영한 임베딩을 학습합니다.

네거티브 샘플링(Negative Sampling)은 그래프의 비지도 학습(unsupervised learning) 설정에서 사용되는 방법으로, 노드 간의 관계를 학습하기 위해 사용됩니다.

positive pair(연결된 노드)와 negative pair(연결되지 않은 노드)를 구분하는 방식으로 동작합니다.

v는 랜덤워크에서의 u의 이웃을 나타냅니다.

Pn(v)는 v의 네거티브 샘플링 분포(negative sampling distribution)분포입니다.

Q는 네거티브 샘플 개수입니다.

Positive pair에 대해 노드 u와 v가 가까워지도록 학습(-log() 첫번째항)

Negative pair에 대해 노드 u와 v_n​이 멀어지도록 학습.(-QE.. 두번째항)

GraphSAGE코드 구현

논문의 내용을 간략화하여 구현해본 내용으로 실제 논문 동작과는 다를 수 있으며, 내용 오류가 있을수 있습니다.

논문의 동작을 이해하기 위한 참고용으로 확인해주세요.

실제 GarphSAGE의 구현은 이미 잘 만들어진 라이브러리를 사용하면 됩니다. (아래 비교 코드 참고)

집계함수는 torch_geometric의 scatter함수의 mean를 사용했습니다.

scatter는 주어진 텐서를 특정 축에 따라 집계(reduce)할 때 사용됩니다.

import torch
import torch.nn as nn
import torch.nn.functional as F
import torch_sparse
from torch_geometric.datasets import Planetoid
from torch_geometric.data import DataLoader
from torch_geometric.loader import NeighborLoader
from torch_geometric.utils import scatter

# SAGEConv 정의
class SAGEConv(nn.Module):
    def __init__(self, in_channels, out_channels):
        super().__init__()
        # CONCAT으로 입력 차원이 2배가 됩니다.
        # 자기 노드의 특성과 "이웃 노드들의 집계된 특성"을 병합*
        self.linear = nn.Linear(in_channels * 2, out_channels)  

    def forward(self, x, edge_index):
        """
        x: Node feature matrix (num_nodes x in_channels)
        edge_index: Graph edge indices (2 x num_edges)
        """
        # #1. Initialize h_v^0 ← x_v, ∀v ∈ V
        # 입력 x는 초기 노드 특성 h_v^0에 해당        
        
        row, col = edge_index # edge_index에서 row(출발 노드)와 col(도착 노드) 분리

        # #2. for k = 1 to K do
        # 단일 레이어이므로 K=1 SAGEConV에서 레이어 수만큼 중첩

        # 4. h_N(v)^(k) ← AGG_k({h_u^(k-1), ∀u ∈ N(v)})
        # Mean Aggregation: 이웃 노드(row)의 특성을 col 기준으로 평균 집계        
        neighbor_features = scatter(x[row], col, dim=0, reduce='mean', dim_size=x.size(0))  # h_N(v)^(k)

        # #5. h_v^(k) ← σ(W_k · CONCAT(h_v^(k-1), h_N(v)^(k)))
        # 노드 자신의 특성(h_v^(k-1))과 이웃의 집계 특성(h_N(v)^(k))을 CONCAT
        out = torch.cat([x, neighbor_features], dim=1)  # CONCAT(h_v^(k-1), h_N(v)^(k))
        
        # 선형 변환과 비선형 활성화(σ)를 적용합니다.
        # σ(W_k · CONCAT(h_v^(k-1), h_N(v)^(k)))
        out = self.linear(out)

        # #6. end for
        # for loop는 단일 레이어이므로 여기서 종료

        # #8. z_v ← h_v^(K), ∀v ∈ V
        # 출력된 특성 out은 h_v^(K)에 해당합니다.

        # #9. Return {z_v, ∀v ∈ V}
        # 최종 노드 임베딩 z_v를 반환합니다.
        return out

# 2-layer GraphSAGE 정의
class GraphSAGE(nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, dropout=0.2):
        super(GraphSAGE, self).__init__()
        self.conv1 = SAGEConv(in_channels, hidden_channels)        
        self.conv2 = SAGEConv(hidden_channels, out_channels)
        self.dropout = nn.Dropout(p=dropout)  

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)        
        x = F.relu(x)
        x = self.dropout(x)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

# Cora 데이터셋 로드
dataset = Planetoid(root='./data', name='Cora')
data = dataset[0]

# NeighborLoader 설정
loader = NeighborLoader(
    data,
    num_neighbors=[15, 10],  #  1-hop에서 15개, 2-hop에서 10개 이웃 샘플링
    batch_size=128,
    input_nodes=data.train_mask
)

# 모델 학습 설정
model = GraphSAGE(dataset.num_node_features, 16, dataset.num_classes, dropout=0.2)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

# 학습 루프
def train():
    model.train()
    total_loss = 0
    for batch in loader:
        optimizer.zero_grad()
        out = model(batch.x, batch.edge_index)
        loss = F.nll_loss(out[batch.train_mask], batch.y[batch.train_mask])
        loss.backward()
        optimizer.step()
        total_loss += loss.item()
    return total_loss / len(loader)

def test():
    model.eval()
    out = model(data.x, data.edge_index)
    pred = out.argmax(dim=1)
    accs = []
    for mask in [data.train_mask, data.val_mask, data.test_mask]:
        correct = (pred[mask] == data.y[mask]).sum()
        accs.append(int(correct) / int(mask.sum()))
    return accs

# 학습 및 평가
for epoch in range(1, 201):
    loss = train()
    train_acc, val_acc, test_acc = test()
    if epoch % 10 == 0:
        print(f"Epoch: {epoch:03d}, Loss: {loss:.4f}, Train Acc: {train_acc:.4f}, Val Acc: {val_acc:.4f}, Test Acc: {test_acc:.4f}")

print("Final Test Accuracy:", test()[2])

Epoch: 010, Loss: 0.0618, Train Acc: 1.0000, Val Acc: 0.7360, Test Acc: 0.7420
Epoch: 020, Loss: 0.0045, Train Acc: 1.0000, Val Acc: 0.7340, Test Acc: 0.7530
Epoch: 030, Loss: 0.0048, Train Acc: 1.0000, Val Acc: 0.7240, Test Acc: 0.7340
Epoch: 040, Loss: 0.0070, Train Acc: 1.0000, Val Acc: 0.7260, Test Acc: 0.7530
Epoch: 050, Loss: 0.0068, Train Acc: 1.0000, Val Acc: 0.7300, Test Acc: 0.7690
Epoch: 060, Loss: 0.0062, Train Acc: 1.0000, Val Acc: 0.7360, Test Acc: 0.7750
Epoch: 070, Loss: 0.0062, Train Acc: 1.0000, Val Acc: 0.7380, Test Acc: 0.7740
Epoch: 080, Loss: 0.0056, Train Acc: 1.0000, Val Acc: 0.7400, Test Acc: 0.7740
Epoch: 090, Loss: 0.0056, Train Acc: 1.0000, Val Acc: 0.7360, Test Acc: 0.7740
Epoch: 100, Loss: 0.0050, Train Acc: 1.0000, Val Acc: 0.7380, Test Acc: 0.7760
Epoch: 110, Loss: 0.0044, Train Acc: 1.0000, Val Acc: 0.7420, Test Acc: 0.7770
Epoch: 120, Loss: 0.0050, Train Acc: 1.0000, Val Acc: 0.7420, Test Acc: 0.7790
Epoch: 130, Loss: 0.0043, Train Acc: 1.0000, Val Acc: 0.7440, Test Acc: 0.7800
Epoch: 140, Loss: 0.0041, Train Acc: 1.0000, Val Acc: 0.7440, Test Acc: 0.7800
Epoch: 150, Loss: 0.0041, Train Acc: 1.0000, Val Acc: 0.7440, Test Acc: 0.7760
Epoch: 160, Loss: 0.0039, Train Acc: 1.0000, Val Acc: 0.7440, Test Acc: 0.7760
Epoch: 170, Loss: 0.0037, Train Acc: 1.0000, Val Acc: 0.7480, Test Acc: 0.7750
Epoch: 180, Loss: 0.0036, Train Acc: 1.0000, Val Acc: 0.7480, Test Acc: 0.7750
Epoch: 190, Loss: 0.0036, Train Acc: 1.0000, Val Acc: 0.7500, Test Acc: 0.7760
Epoch: 200, Loss: 0.0035, Train Acc: 1.0000, Val Acc: 0.7500, Test Acc: 0.7770
Final Test Accuracy: 0.777

 

 

이미 구현된 라이브러리로 작성하여 결과를 비교해보겠습니다.

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import SAGEConv
from torch_geometric.datasets import Planetoid
from torch_geometric.loader import NeighborLoader

# 2-layer GraphSAGE 정의
class GraphSAGE(nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, dropout=0.2):
        super(GraphSAGE, self).__init__()
        self.conv1 = SAGEConv(in_channels, hidden_channels)
        self.conv2 = SAGEConv(hidden_channels, out_channels)
        self.dropout = nn.Dropout(p=dropout)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = self.dropout(x)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

# Cora 데이터셋 로드
dataset = Planetoid(root='./data', name='Cora')
data = dataset[0]

# NeighborLoader 설정
loader = NeighborLoader(
    data,
    num_neighbors=[15, 10],  # 1-hop에서 15개, 2-hop에서 10개 이웃 샘플링
    batch_size=128,
    input_nodes=data.train_mask
)

# 모델 학습 설정
model = GraphSAGE(dataset.num_node_features, 16, dataset.num_classes, dropout=0.2)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

# 학습 루프
def train():
    model.train()
    total_loss = 0
    for batch in loader:
        optimizer.zero_grad()
        out = model(batch.x, batch.edge_index)
        loss = F.nll_loss(out[batch.train_mask], batch.y[batch.train_mask])
        loss.backward()
        optimizer.step()
        total_loss += loss.item()
    return total_loss / len(loader)

def test():
    model.eval()
    out = model(data.x, data.edge_index)
    pred = out.argmax(dim=1)
    accs = []
    for mask in [data.train_mask, data.val_mask, data.test_mask]:
        correct = (pred[mask] == data.y[mask]).sum()
        accs.append(int(correct) / int(mask.sum()))
    return accs

# 학습 및 평가
for epoch in range(1, 201):
    loss = train()
    train_acc, val_acc, test_acc = test()
    if epoch % 10 == 0:
        print(f"Epoch: {epoch:03d}, Loss: {loss:.4f}, Train Acc: {train_acc:.4f}, Val Acc: {val_acc:.4f}, Test Acc: {test_acc:.4f}")

print("Final Test Accuracy:", test()[2])

Epoch: 010, Loss: 0.0788, Train Acc: 1.0000, Val Acc: 0.7420, Test Acc: 0.7470
Epoch: 020, Loss: 0.0139, Train Acc: 1.0000, Val Acc: 0.7100, Test Acc: 0.7370
Epoch: 030, Loss: 0.0111, Train Acc: 1.0000, Val Acc: 0.7180, Test Acc: 0.7190
Epoch: 040, Loss: 0.0116, Train Acc: 1.0000, Val Acc: 0.7300, Test Acc: 0.7450
Epoch: 050, Loss: 0.0169, Train Acc: 1.0000, Val Acc: 0.7400, Test Acc: 0.7640
Epoch: 060, Loss: 0.0133, Train Acc: 1.0000, Val Acc: 0.7440, Test Acc: 0.7630
Epoch: 070, Loss: 0.0062, Train Acc: 1.0000, Val Acc: 0.7420, Test Acc: 0.7730
Epoch: 080, Loss: 0.0099, Train Acc: 1.0000, Val Acc: 0.7540, Test Acc: 0.7520
Epoch: 090, Loss: 0.0084, Train Acc: 1.0000, Val Acc: 0.7500, Test Acc: 0.7890
Epoch: 100, Loss: 0.0052, Train Acc: 1.0000, Val Acc: 0.7520, Test Acc: 0.7790
Epoch: 110, Loss: 0.0079, Train Acc: 1.0000, Val Acc: 0.7360, Test Acc: 0.7860
Epoch: 120, Loss: 0.0084, Train Acc: 1.0000, Val Acc: 0.7520, Test Acc: 0.8050
Epoch: 130, Loss: 0.0062, Train Acc: 1.0000, Val Acc: 0.7460, Test Acc: 0.8020
Epoch: 140, Loss: 0.0084, Train Acc: 1.0000, Val Acc: 0.7580, Test Acc: 0.7930
Epoch: 150, Loss: 0.0124, Train Acc: 1.0000, Val Acc: 0.7500, Test Acc: 0.7860
Epoch: 160, Loss: 0.0078, Train Acc: 1.0000, Val Acc: 0.7480, Test Acc: 0.7950
Epoch: 170, Loss: 0.0041, Train Acc: 1.0000, Val Acc: 0.7440, Test Acc: 0.7900
Epoch: 180, Loss: 0.0054, Train Acc: 1.0000, Val Acc: 0.7560, Test Acc: 0.7940
Epoch: 190, Loss: 0.0049, Train Acc: 1.0000, Val Acc: 0.7520, Test Acc: 0.7870
Epoch: 200, Loss: 0.0054, Train Acc: 1.0000, Val Acc: 0.7520, Test Acc: 0.8050
Final Test Accuracy: 0.805

구현된 라이브러리를 사용하는 것이 성능이 역시 더 높습니다.

 

GraphSAGE의 가장 큰 장점은 속도입니다. 하나의 CPU에서 GCN의 4배, GAT보다 88배 빠르다고 합니다.

GraphSAGE는 나와 이웃으로 집계하여, 그래프 전체 구조를 더 강하게 반영하는 GCN이나 GAT만큼 정확하지는 않지만 대량의 데이터를 짧은 시간에 처리하는데 효과적인 방법입니다.