GNN(Graph Neural Network) - 11. SEAL (Subgraphs, Embeddings and Attributes for Link prediction)

SEAL은 그래프 구조 특성을 학습하여 링크 예측(Link Prediction)을 위한 그래프 신경망 모델입니다. 
기존의 GNN(Graph Neural Network) 기반 모델이 전체 그래프를 학습하는 방식과 달리, SEAL은 링크 주변의 서브그래프(subgraph)를 추출하여 학습하는 방식으로 동작합니다.

 

동작방식
1) 서브그래프 추출 (Subgraph Extraction)

• 예측하려는 링크(노드 쌍)를 중심으로 서브그래프를 추출합니다.
• 서브그래프는 특정 거리(k-hop) 내의 노드들로 구성됩니다.
• 노드 레이블링 기법을 활용해 각 노드에 상대적인 역할을 부여합니다.

2) GNN을 활용한 서브그래프 임베딩 (Subgraph Encoding)

• 서브그래프를 GCN, GIN, GAT 등의 GNN 모델을 이용해 임베딩합니다.
• 각 서브그래프는 개별적으로 처리되므로, 전체 그래프 크기와 무관하게 학습할 수 있습니다.

3) 링크 예측 수행 (Link Prediction)

• 서브그래프 임베딩을 활용해 두 노드가 연결될 확률을 예측합니다.
• 일반적으로 MLP 또는 분류기(classifier) 를 활용하여 최종 예측을 수행합니다.

SEAL논문

• 논문 제목: Link Prediction Based on Graph Neural Networks
• 저자: Muhan Zhang, Yixin Chen
• 발표 연도: 2018년
• 학회: NeurIPS (Neural Information Processing Systems)
• 논문 링크: https://papers.neurips.cc/paper/2018/file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf
• GitHub 저장소: https://github.com/muhanzhang/SEAL

GitHub - muhanzhang/SEAL: SEAL (learning from Subgraphs, Embeddings, and Attributes for Link prediction). "M. Zhang, Y. Chen, Li

 

 

전통적인 방법으로 링크 예측

링크 예측 문제들을 위해 휴리스틱 기법(heuristic techniques)기법이 많이 사용되었습니다.

휴리스틱 기법이란 문제를 해결하기 위해, 완벽한 최적해는 아니지만 경험적인 방법이나 발견적 접근법을 사용해서 근사적인 좋은 해를 찾는 방법입니다. 예를 들어, 인공신경망에서 ReLU를 사용하는 것이, 경험상 ReLU가 성능이 가장 잘 나온다는 경험적인 사실의 휴리스틱 기반의 선택입니다.

기존에는 그래프의 구조적인 속성만을 활용하여 노드 간 유사도를 측정하는 "score-based 휴리스틱 기법"이 많이 사용되었습니다. 기존 휴리스틱은 점수를 계산하는 데 필요한 이웃의 최대 hop의 수를 기준으로 분류할 수 있습니다. 1hop만 포함할 경우 일차 휴리스틱, 2hop을 이웃으로 계산할 경우 2차 휴리스틱, h차 휴리스틱은 h-hop까지 이웃을 가지는 휴리스틱으로 정의합니다. score-based 휴리스틱 기법에는 CN(Common Neighbors), Jaccard Cofficent, AA(Adamic-Acar), RA(Resource Allocation), PA(Preferential Attachment)등이 있습니다. 이중 몇가지를 살펴보겠습니다.

1) 공통이웃(Common Neighbors, CN)

두 노드 u, v 사이의 공통된 이웃의 수를 기반으로 연결 가능성을 평가하는 방식(1hop)

CN(u,v)=∣ Γ(u)∩Γ(v) ∣

• Γ(x) : 노드 x의 이웃 집합

공통의 이웃이 많을 수록 링크가 형성될 가능성이 높다고 가정하는 방식입니다.

2) 자카드 계수(Jaccard Coefficient)

공통 이웃을 전체 이웃의 개수로 정규화한 지표 (1hop)

 

• $Jaccard(u, v) = \frac{| \Gamma(u) \cap \Gamma(v) |}{| \Gamma(u) \cup \Gamma(v) |}$
• 공통 이웃 수가 많지만 전체 이웃 수도 많다면, 두 노드 간 유사도가 낮아지도록 보정.

3) 아다믹-아다르 계수(Adamic-Adar Index, AA)

 

• 공통 이웃 중 희귀한 이웃(즉, 적은 연결을 가진 노드)에 더 높은 가중치를 부여.(2hop)
• $AA(u, v) = \sum_{w \in \Gamma(u) \cap \Gamma(v)} \frac{1}{\log |\Gamma(w)|}$
• 네트워크에서 희귀한 이웃이 중요한 정보라고 가정하여 CN보다 더 정교한 유사도 제공.

4) 우선 연결 유사도(Preferential Attachment, PA)

 

• "인기 있는 노드는 새로운 링크를 더 쉽게 획득한다"는 우선 연결(preferential attachment) 이론을 기반으로 함.(전체)
• $PA(u, v) = |\Gamma(u)| \cdot |\Gamma(v)|$
• 노드의 전체 연결수를 이용하며 특정 노드가 과도하게 연결되는 허브(hub) 현상을 보정하지 않음.

5) 카츠 인덱스(Katz index)

Katz Index는 두 노드 간 존재하는 모든 경로의 가중합을 기반으로 링크 가능성을 측정하는 휴리스틱 기법입니다.
즉, 두 노드가 직접 연결되지 않더라도 여러 단계를 거쳐 연결될 가능성이 크다면 높은 점수를 부여합니다.

$Katz(u, v) = \sum_{l=1}^{\infty} \beta^l \cdot |\text{paths of length } l \text{ between } u \text{ and } v|$

• l: 경로의 길이 (1-hop, 2-hop, 3-hop, ...)
• β: 감쇠 계수 (Damping Factor, $/λmax⁡0 < \beta < 1/\lambda_{\max}$​은 인접행렬의 최대 고유값)
• ∣paths of length l: 노드 u와 v 사이의 길이 l인 경로의 개수

두 노드 사이의 모든 경로의 가중합을 계산하고, discount factor β(0.8~0.9)로 더 긴 경로에 대한 패널치를 주는 방식입니다. 두 노드 사이에 많은 짧은 경로가 있으면 연결될 가능성이 높다는 이론입니다.

 

SEAL(Subgraph Embedding-based Link prediction)

SEAL은 링크 존재 여부를 예측하는 그래프 모델입니다.

그래프 학습을 위해 그래프 구조를 휴리스틱 기법으로 근사화할 때, 전체 그래프 구조 A가 반드시 필요하지는 않습니다.
특정 노드를 중심으로 h-hop 서브그래프를 구성하여 근사화하면, μ-감쇠 이론에 의해 hop 수가 증가할수록 근사화 오차가 기하급수적으로 감소합니다.
즉, 작은 h-hop 범위만으로도 큰 그래프의 구조적 특징을 효과적으로 학습할 수 있다는 의미입니다.

이를 바탕으로, 링크 예측을 위한 휴리스틱 학습 기법에서는 전체 그래프 네트워크가 아닌 지역적인 서브그래프(local sub-graph)만을 이용하여 학습이 가능합니다.

 

SEAL에서 링크를 예측할 2개의 대상 노드 (x,y)와 그들을 둘러싼 k-hop의 이웃으로 형성된 서브 그래프를 enclosing subgraph라고 합니다.

논문에서 SEAL은 다음의 3단계로 구성됩니다.

1) enclosing subgraph 추출

학습데이터를 생성할때 실제 link가 존재하는 positive link data와 link가 없는 negative link data를 추출합니다.

2) node information matrix 생성

노드 정보 행렬을 3개의 구성요소를 가지고 있습니다.

nodel label(노드 레이블), node embedding(노드 임베딩), node features(노드 특징량)

3) GNN 학습 

GNN은 일반적으로 인접행렬 A와 노드의 특징량 X를 사용하는데, SEAL에서는 node information matrix를 X로 사용합니다. 즉 node information matrix를 바탕으로, link 여부를 판단합니다.

다음 그림은 논문의 3개 단계의 과정입니다.

 

node information matrix 구성요소

다음은 node information matrix의 구성요소입니다.

1) node labeling

sub-graph의 모든 노드에 라벨링, 즉 특정 번호를 할당합니다. 노드 각각의 역할을 표시하기 위해 라벨링을 합니다.

라벨링을 하지 않으면, 링크를 예측해야할 노드가 어디인지 알수 없습니다. 라벨링은 중심에 대한 상대적 위치를 표시해 구조적 중요성을 설명합니다. 즉, 구조적 중요성에 대한 거리를 나타냅니다.

 

SEAL저자들은 이중 반지름 노드 라벨링(DRNL, Double-Radius Node Labeling)알고리즘으로 노드 라벨링 방법을 제안했습니다.

 

노드 라벨링 기준

(1) 두 대상 노드 x와 y는 항상 "1"의 고유 레이블을 할당 받습니다.

(2) d(i, x) = d(j, x) 및 d(i, y) = d(j, y)인 경우 노드 i와 j는 동일할 레이블을 갖습니다.

      이를 두 중심에 대한 반지름 (d(i,x), d(i,y))로 설명하여 이중 반지름 거리로 설명합니다.

 

노드 라벨링 절차

(1) 두 대상 노드 x와 y에 레이블 "1"할당

(2) (d(i,x), d(i,y)) = (1,1)을 가지는노드에 대해 레이블 "2"를 할당

(3) (d(i,x), d(i,y)) = (1,2) 또는 (d(i,x), d(i,y)) = (2,1) 를 가지는 노드에 대해 레이블 "3"을 할당

(4) (d(i,x), d(i,y)) = (1,3) 또는 (d(i,x), d(i,y)) = (2,1) 를 가지는 노드에 대해 레이블 "4"를 할당

(5) 반복

 

이를 일반화 하면 DRNL함수를 다음과 같이 작성될 수 있습니다.

$f(i)=1+min(d(i,x),d(i,y))+ (d/2) [ (d/2)+(d\text{%}2)-1]$

라벨링을 완료한 후 one-hot encoding으로 X를 구성합니다.

 

2) 노드 임베딩

Node2Vec등의 알고리즘으로 계산될 수 있는데, 노드 임베딩은 선택사항입니다.

 

3) 노드 특징량

마지막으로 각 노드의 특징량 X가 구성됩니다.

 

onehot encoding된 노드 라벨링과, 노드 임베딩, 노드 특징량을 행르로 연결하여 최종 학습데이터 X를 구성합니다.

 

GNN 학습

최종학습데이터 X를 이용해, 링크를 예측하기 위해 GNN이 사용됩니다.

SEAL에서는 DGCNN(Deep Graph Convolutional Neural Network)를 사용했습니다.

링크 존재여부를 예측하고 결과는 AUC와 AP로 성능을 평가했습니다.

 

SEAL에서 사용한 DGCNN(Deep Graph Convolutional Neural Network)은 링크 예측(Link Prediction)을 위해 수정된 모델로, 
기존의 GCN(Graph Convolutional Network)을 확장한 방식입니다.

여러 개의 GCNConv 레이어를 사용하여 서브그래프의 노드 임베딩을 학습하고 여러 GCN 레이어의 출력을 Concat합니다.
Sort Pooling을 활용하여 노드 순서를 정렬합니다.
1D CNN을 사용하여 정렬된 임베딩에서 추가적인 특징 추출하고 Fully Connected Layer를 거쳐 링크 존재 확률 예측합니다.

 

코드작성

출처

https://github.com/PacktPublishing/Hands-On-Graph-Neural-Networks-Using-Python/tree/main/Chapter10

Hands-On-Graph-Neural-Networks-Using-Python/Chapter10 at main · PacktPublishing/Hands-On-Graph-Neural-Networks-Using-Python

1) 데이터셋 로드 및 링크 예측을 위한 데이터 분할
Cora 데이터셋을 로드 (논문 데이터셋, 논문 간의 인용 관계를 그래프로 표현)
RandomLinkSplit을 사용해 훈련, 검증, 테스트 데이터로 분할(5%를 검증, 10%를 테스트)
링크 예측 문제를 위한 Posit(링크존재)/음성(링크 미존재) 샘플링 수행

dataset = Planetoid(root='.', name='Cora', transform=RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True, split_labels=True))
train_data, val_data, test_data = dataset[0]

 

2) SEAL subgraph 추출 함수

def seal_processing(dataset, edge_label_index, y):

각 (src, dst) 노드 쌍에 대해 k-hop 서브그래프(기본적으로 k=2)를 추출
이중 반지름 노드 라벨링(DRNL, Double-Radius Node Labeling)을 수행하여 두 중심 노드로부터의 거리에 따라 라벨을 할당
원-핫 인코딩 후, 기존 노드 임베딩과 결합하여 "node information matrix" 생성
Data 객체로 변환하여 리스트로 연결

(1) k-hop subgraph 추출

k=2로 서브그래프를 생성 

sub_nodes, sub_edge_index, mapping, _ = k_hop_subgraph([src, dst], 2, dataset.edge_index, relabel_nodes=True)

(2) 이중 반지름 노드 라벨링(DRNL, Double-Radius Node Labeling)

src, dst를 제외한 서브그래프에서 각각의 노드에 대한 최단 거리(shortest path)를 계산
두 노드 간의 거리를 기반으로 DRNL 라벨링 수행

d_src = shortest_path(adj_wo_dst, directed=False, unweighted=True, indices=src)
d_dst = shortest_path(adj_wo_src, directed=False, unweighted=True, indices=dst-1)

(3) node information matrix 생성

노드의 라벨을 원-핫 인코딩하여 추가 특징으로 사용
기존 노드 임베딩(dataset.x[sub_nodes])과 결합

 

(4) DGCNN (Deep Graph Convolutional Neural Network) 모델

 

• GCN 레이어 4개를 쌓아서 노드 임베딩을 학습
• SortPooling을 활용하여 서브그래프 수준의 특징을 생성
• 1D CNN을 사용해 임베딩을 추가 처리 후, 선형 계층을 통해 최종 분류

class DGCNN(torch.nn.Module):
    def __init__(self, dim_in, k=30):

 

전체 코드

 

import numpy as np
from sklearn.metrics import roc_auc_score, average_precision_score
from scipy.sparse.csgraph import shortest_path

import torch
import torch.nn.functional as F
from torch.nn import Conv1d, MaxPool1d, Linear, Dropout, BCEWithLogitsLoss

from torch_geometric.datasets import Planetoid
from torch_geometric.transforms import RandomLinkSplit
from torch_geometric.data import Data
from torch_geometric.loader import DataLoader
from torch_geometric.nn import GCNConv, aggr
from torch_geometric.utils import k_hop_subgraph, to_scipy_sparse_matrix

# 1️⃣ 데이터셋 로드 및 랜덤 링크 분할 (train, val, test)
dataset = Planetoid(root='.', name='Cora', transform=RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True, split_labels=True))
train_data, val_data, test_data = dataset[0]

# 2️⃣ SEAL 데이터 전처리 함수 (k-hop 서브그래프 추출 및 노드 라벨링)
def seal_processing(dataset, edge_label_index, y):
    data_list = []

    for src, dst in edge_label_index.t().tolist():
        # k-hop 서브그래프 추출 (k=2)
        sub_nodes, sub_edge_index, mapping, _ = k_hop_subgraph([src, dst], 2, dataset.edge_index, relabel_nodes=True)
        src, dst = mapping.tolist()

        mask1 = (sub_edge_index[0] != src) | (sub_edge_index[1] != dst)
        mask2 = (sub_edge_index[0] != dst) | (sub_edge_index[1] != src)
        sub_edge_index = sub_edge_index[:, mask1&mask2]

        src, dst = (dst, src) if src > dst else (src, dst)
        adj = to_scipy_sparse_matrix(sub_edge_index, num_nodes=sub_nodes.size(0)).tocsr()

        idx = list(range(src)) + list(range(src+1, adj.shape[0]))
        adj_wo_src = adj[idx,:][:, idx]

        idx = list(range(dst)) + list(range(dst+1, adj.shape[0]))
        adj_wo_dst = adj[idx,:][:, idx]

	# Shortest Path Distance (DRNL 노드 재레이블링)
        d_src = shortest_path(adj_wo_dst, directed=False, unweighted=True, indices=src)
        d_src = np.insert(d_src, dst, 0, axis=0)
        d_src = torch.from_numpy(d_src)

        d_dst = shortest_path(adj_wo_src, directed=False, unweighted=True, indices=dst-1)
        d_dst = np.insert(d_dst, src, 0, axis=0)
        d_dst = torch.from_numpy(d_dst)

        dist = d_src + d_dst
	
	# DRNL (Double-Radius Node Labeling)
        z = 1 + torch.min(d_src, d_dst) + dist //2 * (dist // 2 + dist %2 -1)

	# NaN 값은 0으로, src와 dst는 1로 설정
        z[src], z[dst], z[torch.isnan(z)] = 1., 1., 0.
        z = z.to(torch.long)

        # 원-핫 인코딩 (중심과의 거리를 라벨링 후 결과를 one-hot encoding 
        node_labels = F.one_hot(z, num_classes = 200).to(torch.float)
	# 노드 임베딩과 원핫 인코딩된 라벨을 결합(노드 임베딩은 사용하지 않음)
        node_emb = dataset.x[sub_nodes]
        node_x = torch.cat([node_emb,node_labels], dim=1)

	# PyG의 Data 객체로 변환
        data = Data(x = node_x, z=z, edge_index=sub_edge_index, y=y)
        data_list.append(data)

    return data_list

# 3️⃣ 훈련, 검증, 테스트 데이터 생성
train_pos_data_list = seal_processing(train_data, train_data.pos_edge_label_index, 1)    
train_neg_data_list = seal_processing(train_data, train_data.neg_edge_label_index, 0)

val_pos_data_list = seal_processing(val_data, val_data.pos_edge_label_index, 1)    
val_neg_data_list = seal_processing(val_data, val_data.neg_edge_label_index, 0)

test_pos_data_list = seal_processing(test_data, test_data.pos_edge_label_index, 1)    
test_neg_data_list = seal_processing(test_data, test_data.neg_edge_label_index, 0)

# 4️⃣ PyG DataLoader 생성
train_dataset = train_pos_data_list + train_neg_data_list
val_dataset = val_pos_data_list + val_neg_data_list
test_dataset = test_pos_data_list + test_neg_data_list

train_loader = DataLoader(train_dataset, batch_size=32, shuffle=True)
val_loader = DataLoader(val_dataset, batch_size=32)
test_loader = DataLoader(test_dataset, batch_size=32)

# 5️⃣  DGCNN 모델 구현
class DGCNN(torch.nn.Module):
    def __init__(self, dim_in, k=30):
        super().__init__()

        # GCN 레이어 
        self.gcn1 = GCNConv(dim_in, 32)
        self.gcn2 = GCNConv(32, 32)
        self.gcn3 = GCNConv(32, 32)
        self.gcn4 = GCNConv(32, 1)

        # SortPooling
        self.global_pool = aggr.SortAggregation(k=k)

        # 1D CNN 기반의 최종 분류기
        self.conv1 = Conv1d(1, 16, 97, 97)
        self.conv2 = Conv1d(16, 32, 5, 1)
        self.maxpool = MaxPool1d(2, 2)

        self.linear1 = Linear(352, 128)
        self.dropout = Dropout(0.5)
        self.linear2 = Linear(128, 1)

    def forward(self, x, edge_index, batch):
        h1 = self.gcn1(x, edge_index).tanh()
        h2 = self.gcn2(h1, edge_index).tanh()
        h3 = self.gcn3(h2, edge_index).tanh()
        h4 = self.gcn4(h3, edge_index).tanh()
        h = torch.cat([h1, h2, h3, h4], dim=-1)

        h = self.global_pool(h, batch)

        h = h.view(h.size(0), 1, h.size(-1))
        h = self.conv1(h).relu()
        h = self.maxpool(h)
        h = self.conv2(h).relu()
        h = h.view(h.size(0), -1)
        h = self.linear1(h).relu()
        h = self.dropout(h)
        h = self.linear2(h).sigmoid()
        return h

# 6️⃣ 모델 학습 및 평가
model = DGCNN(train_dataset[0].num_features)        
optimizer = torch.optim.Adam(params=model.parameters(), lr=0.001)  # 학습률 증가 (논문 기준)
criterion = BCEWithLogitsLoss()

@torch.no_grad()
def test(loader):
    model.eval()
    y_pred, y_true = [], []

    for data in loader:
        out = model(data.x, data.edge_index, data.batch)
        y_pred.append(out.view(-1))
        y_true.append(data.y.to(torch.float))

    auc = roc_auc_score(torch.cat(y_true), torch.cat(y_pred))    
    ap = average_precision_score(torch.cat(y_true), torch.cat(y_pred))
    return auc, ap

# 7️⃣ 모델 훈련 루프
for epoch in range(21):
    model.train()
    total_loss = 0

    for data in train_loader:
        optimizer.zero_grad()
        out = model(data.x, data.edge_index, data.batch)
        loss = criterion(out.view(-1), data.y.to(torch.float))
        loss.backward()
        optimizer.step()
        total_loss += float(loss) * data.num_graphs
        
    loss = total_loss / len(train_dataset)
    val_auc, val_ap = test(val_loader)
    print(f'Epoch {epoch:>2} | Loss: {loss:.4f} | Val AUC: {val_auc:.4f} | Val AP: {val_ap:.4f}')

test_auc, test_ap = test(test_loader)    
print(f'Test AUC: {test_auc:.4f} | Test AP: {test_ap:.4f}')

Epoch  0 | Loss: 0.6505 | Val AUC: 0.7779 | Val AP: 0.8056
Epoch  1 | Loss: 0.6174 | Val AUC: 0.7620 | Val AP: 0.7948
Epoch  2 | Loss: 0.6207 | Val AUC: 0.7505 | Val AP: 0.7854
Epoch  3 | Loss: 0.6151 | Val AUC: 0.7442 | Val AP: 0.7524
Epoch  4 | Loss: 0.6157 | Val AUC: 0.7176 | Val AP: 0.7468
Epoch  5 | Loss: 0.6182 | Val AUC: 0.7375 | Val AP: 0.7592
Epoch  6 | Loss: 0.6102 | Val AUC: 0.7426 | Val AP: 0.7664
Epoch  7 | Loss: 0.6124 | Val AUC: 0.7354 | Val AP: 0.7593
Epoch  8 | Loss: 0.6114 | Val AUC: 0.7423 | Val AP: 0.7785
Epoch  9 | Loss: 0.6163 | Val AUC: 0.7347 | Val AP: 0.7385
Epoch 10 | Loss: 0.6299 | Val AUC: 0.7291 | Val AP: 0.7653
Epoch 11 | Loss: 0.6229 | Val AUC: 0.6943 | Val AP: 0.7445
Epoch 12 | Loss: 0.6144 | Val AUC: 0.7197 | Val AP: 0.7648
Epoch 13 | Loss: 0.6084 | Val AUC: 0.7172 | Val AP: 0.7559
Epoch 14 | Loss: 0.6131 | Val AUC: 0.7627 | Val AP: 0.7365
Epoch 15 | Loss: 0.6226 | Val AUC: 0.7512 | Val AP: 0.7404
Epoch 16 | Loss: 0.6153 | Val AUC: 0.7400 | Val AP: 0.7490
Epoch 17 | Loss: 0.6129 | Val AUC: 0.7577 | Val AP: 0.7555
Epoch 18 | Loss: 0.6104 | Val AUC: 0.7369 | Val AP: 0.7478
Epoch 19 | Loss: 0.6173 | Val AUC: 0.7354 | Val AP: 0.7432
Epoch 20 | Loss: 0.6121 | Val AUC: 0.7662 | Val AP: 0.7630
Test AUC: 0.7513 | Test AP: 0.7470