GraphOmakase

1월 4주차 그래프 오마카세

Static and dynamic robustness

오늘 다루어볼 네트워크 지식은 ‘robustness’ 입니다. 딥러닝 분야에서와 복잡계 네트워크 분야에서의 ‘robustness’는 모델의 강건함을 측정한다는 동일한 목적이 있으나, 어떤식으로 측정할지 기준치 사전분포 측정과 같은 요소들 때문에 약간 결이 다르다고 볼 수 있습니다.
‘robustness’ , 딥러닝 분야에서는 training 데이터셋에 존재치않은 out-of-distribution 데이터를 inference 할 때 퍼포먼스가 얼마만큼 적게 떨어지는지에 대한 지표로 쓰이곤하죠.
복잡계 네트워크에서는 ‘static’ , ‘dynamic’ 관점으로 robustness 가 나뉩니다. 차이를 간단하게 말해보자면 특정 노드사이의 엣지가 끊겼을 때, 다시 엣지가 복구가 되는지 안되는지로 보시면 될 것 같아요.
static → 복구 안됨. dynamic → 복구 됨.
robustness 의 높고 낮음에 따라 결국 네트워크의 탄력성(reslience) 이 높고 낮음이 결정된다고 볼 수 있습니다. 자주 활용되는 분야인 cybersecurity 예로 들어보자면, reslience가 높다면 특정 컴퓨터에 문제가 발생할 시 그 컴퓨터를 차단하고 그 컴퓨터를 대체할 수단을 찾는 딜레이가 짧다. 라고 보시면 될 것 같습니다.
디테일하게 해석해보면 해당 네트워크의 분포부터 power-law , scale-free 인지 그리고 correlated network 인지 여러 condition 을 기반으로 해석을 하곤합니다. 해석시에 사용되는 수치 또한 존재하구요.
‘percolation’이라는 수치를 자주 활용하는데요. ‘percolation’에 대해 알려주세요! 라고 chatGPT에 물어보니 The percolation threshold is the point at which a giant connected component, spanning across the network, first appears. A high value of percolation in a network means that there is a high probability for a giant connected component to form, i.e., there is a large connected cluster of nodes in the network. This property has important implications in various fields, including epidemiology, material science, and information dissemination. 라고 답을 해주네요 :)

출처 : Boccaletti, Stefano, et al. "Complex networks: Structure and dynamics." Physics reports 424.4-5 (2006): 175-308.APA

The End of Programming

[https://cacm.acm.org/magazines/2023/1/267976-the-end-of-programming/fulltext?s=09]

오마카세 주방장 역시 대중들과 동일한 고민을 하고 있었습니다..! 그래프 오마카세가 chatGPT 에게 대체되면 어쩌지? 라는 고민을요..!
그 고민에 대해 견해를 밝힌 글인데요. 상당히 설득력 있습니다. 일단 CS 분야에서의 binary-tree 를 c++로 구현하는 등의 구현 공부들은 이제 가치가 이전대비 적어보인다. 이젠 large model 의 결과물이 왜 그렇게 나왔는지에 대해 우리가 알아가야할 것이다. 라며 parameter 가 4조개가 넘어가고 있는 이 파라미터들을 어떻게 해석하는지가 중요해질것이다. 근데 도전해보는거 좋다 허나 조심해라 상당히 복잡할테니 라는 말을 남깁니다.
유명 대가들 또한 chatGPT 에 대해 자신들의 의견들을 남기곤하는데요 최근 podcast 에서 ‘이건 모델이 직접 계산한게 아니라 1+1 = 2 라는 텍스트를 학습한것이고 그에 대한 답을 가져온것이다’ 라는 식으로 언급하며 ‘symbolic ai’ 의 중요성을 다시 이야기합니다.
또한 , chatGPT가 쓴글인지 아닌지를 판별하기 위한 모델도 나왔는데요. DetectGPT 입니다. 간단히 말해보자면, 분포가 인간답냐 , 기계답냐 의 차이를 구별해주는 모델이라 보시면 될 것 같습니다.
알파고 이 후 AI로 다시 한 번 세계가 들썩이고 있습니다. 이 때 오히려 유행을 따라가기보다 필요할 때 활용하시고, 기본기에 매진하여 자신만의 개성 + 기본기 를 결합한 인재로 거듭나셨으면 합니다.

PODCAST ; [https://open.spotify.com/episode/7xAUMohar0AcKToIBXmgqr]

Graph Fusion in Reciprocal Recommender Systems

[https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10025747]

reciprocal recommender system 이라는 분야를 처음 접했습니다..! 그래프 오마카세 덕분에 또 공부하게 되네요 :) 간단히 말씀드려보자면 이커머스에서의 추천시스템은 유저-아이템 간의 ‘클릭’ 여부를 label로 두고 prediction 했다면, reciprocal recommender system 는 유저-유저 간의 ‘matching’ 여부를 label 로 둡니다. 상호작용이 발생하느냐 아니냐 로 구별하실수 있을거 같네요. 아서왕 전설검처럼 아이템이 유저를 간택한다는 일이 발생한다면 모르겠으나 실제로 거의 불가에 가까운일이니깐요.
유저간의 상호작용에 집중한다! 라는 측면에서 ‘job hunting’ , ‘date matching’ 산업에서 주로 쓰인다고 합니다. pair matching 이 핵심인거죠.
task 는 2가지로 나뉜다고합니다. ‘send’ ,’reply’ 즉, 승낙 거절과 같은 정보들이 추가되어 prediction 된다고 보시면 될 것 같네요. 눈치가 빠르신분들은 아시겠지만 승낙이 positive link , 거절이 negative link 로 간주되어 진행됩니다.
graph construction 또한 흥미롭습니다. 기존에는 user(male)-user(female) 를 bipartite graph 로 만드는것은 비슷합니다. 여기에서 edge 의 label 이 총 3개인데요. ‘send’, ‘reply’, ’unconnected’ 반응이 있고 없고 만약 있었다면, 승낙인지 거절인지가 포함된거죠.
아이디어가 심플하고 흥미로워서 소개시켜 드립니다. 특히, negative sampling 을 여기에선 어떻게 했을지 유념하시면서 논문 보시는걸 추천드립니다.

Feature selection: Key to enhance node classification with graph neural networks

[https://ietresearch.onlinelibrary.wiley.com/doi/pdf/10.1049/cit2.12166]

GNN의 성능을 높이고자 selector 과 classifier model 를 joint learning 하는 아키텍쳐를 제안합니다.
굉장히 어려워보이지만 selector 라는게 결국 GNN 의 aggregation function 을 combination , permutation 한다고 보시면 될 것 같습니다. 심플하게본다면 , 노드 엣지의 정보가 왔을때 더할지 뺄지 세제곱할지와 같은 형태를 조정해주며 optimal performance 를 찾는다는게 논문의 핵심 아이디어 입니다.
저도 늘 상상만해보던 task 를 본 논문에서는 명쾌하게 풀어주었네요. pseudo-code 도 논문에 있어서 대략적인 Overview 도 따라가며 볼 수 있습니다.
본 논문의 재미 포인트는 머신러닝 입문에서 주로 배우는 lasso RFE 등을 feature selection baseline 으로 두고 실험비교를 하는 파트라고 볼 수 있겠네요. 참고로 future work 에서 저자가 한계점을 언급하는 부분이 있는데, 한 번 재미삼아 구현해보시는걸 추천드립니다 :)

Everything is Connected: Graph Neural Networks

[https://arxiv.org/pdf/2301.08210.pdf]

GNN 의 핵심을 담아놓은 논문입니다. 평소 주변분들에게 GNN이 무엇인지 설명하고 싶으셨던 분들이 참고하시면 너무나도 좋을 리소스입니다.
GNN의 한계점부터 왜 graph data 인지 그리고 gnn 을 공부하고 있는데 자꾸 expressive power 라는 단어가 나오는지 의문이 있으셨던 분들이시라면 그 호기심을 단번에 해소해줄 논문이라 단언합니다. 역시 고수답게 어려운 개념들을 명쾌하고 간결하고 무엇보다도 쉽게 설명되어 있어 두고 두고 되새김할 논문이라 생각되네요.

Understanding Graph based similarity: Simrank, Simrank++

[https://medium.com/@ksdave/understanding-graph-based-similarity-simrank-simrank-91619c88c336]

structural similarity 의 대명사 Simrank 가 업그레이드 되었네요! Simrank 에 대해 익숙치않으신분들을 위해 잠시 설명드리자면, 노드간 neighbor/connection 가 얼마나 비슷한지 측정하는거라고 보시면 되겠습니다.
여기 포스팅에 따르면 기존 simrank 은 단순하게 그래프 유사도 즉, 비슷한 이웃 혹은 연결 구조만 있다면 두 노드가 비슷하다고 측정해버립니다. 이 때 한계점이 두 노드간의 context 를 반영하지 못한다는거죠.
그 context 를 반영하기 위해 ‘evidence’라는 아이디어를 도입해 weight를 줌으로써 그 context를 보완한다 라는게 핵심 아이디어 입니다.
link analysis 하실때, pagerank 를 baseline 으로 importance 측정하셨던 분들에게 재미난 소식이 될 수 도 있겠네요! Simrank 한 번 적용해보시는걸 추천드립니다!

conference

WWW2023 tutorial

[https://www2023.thewebconf.org/program/tutorials/]

너무나도 재밌는 튜토리얼들이 한가득인 WWW2023 소식입니다! 특히, 카이스트 신기정 교수 연구실에서 tutorial을 accepted ! 축하드립니다! 그것도 제가 좋아하는 하이퍼그래프 definition 부터 application 까지 broadly 한 범위를 다룹니다 :)
추가로 , Continual graph learning. , Lifelong learning Cross-domain Recommender Systems. Towards Out-of-Distiribution Generalization on Graphs. 튜토리얼까지 !! 다소 생소했던 Continual learning + GNN 등 재밌는 요소들이 많아보이네요.

시즌한정메뉴 . BIG GRAPH DATA with PyG

data

CSV load

대다수 분들이 활용하고 계실 방법으로 추측됩니다. 2가지 csv 파일만 있으면 가능하죠.
노드와 노드가 어떻게 연결되어있는지 src, dst 2가지 컬럼으로 구성되어있는 edge csv 파일
노드가 어떤 feature 을 가지고 있는지 node csv 파일
간단하지만, 대용량 파일을 한꺼번에 올리려고 시도하실때 OOM 오류와 만나게 됩니다.
[https://pytorch-geometric.readthedocs.io/en/latest/tutorial/load_csv.html]

InMemoryDataset

def process(self):
    # Read data into huge `Data` list.
    data_list = [...]

    if self.pre_filter is not None:
        data_list = [data for data in data_list if self.pre_filter(data)]

    if self.pre_transform is not None:
        data_list = [self.pre_transform(data) for data in data_list]
		########################## point 	########################## 

    data, slices = self.collate(data_list)
    torch.save((data, slices), self.processed_paths[0])

핵심은 collate 함수입니다. python list 형태로 데이터를 받아와 torch_geometric.data.Data 형태로 바꿔주는 역할을 합니다. 즉 collate 함수 네이밍 그대로 합쳐주는 역할을 합니다.
이전 load csv 에서는 load 해주고 Data 형태로 바꿔주는 과정에서 OOM이 발생하는데요. 그 과정을 효율적으로 진행하기 위해 InMemoryDataset방식을 활용합니다.
[https://pytorch-geometric.readthedocs.io/en/latest/tutorial/create_dataset.html]

Dataset

def process(self):
		idx = 0
		for raw_path in self.raw_paths:
		    # Read data from `raw_path`.
		    data = Data(...)
		
		    if self.pre_filter is not None and not self.pre_filter(data):
		        continue
		
		    if self.pre_transform is not None:
		        data = self.pre_transform(data)
		##########################  here ! save 	########################## 

		    torch.save(data, osp.join(self.processed_dir, f'data_{idx}.pt'))
		    idx += 1
		
		##########################  here ! save 	########################## 
		def len(self):
		return len(self.processed_file_names)
		
		##########################  here ! load 	########################## 

		def get(self, idx):
		data = torch.load(osp.join(self.processed_dir, f'data_{idx}.pt'))
		return data

위 Inmemorydataset 다른점을 눈치채셨겠지만, process function에서 slicing 해준것을 바로 save 해주고 manually save , load 해줍니다. 이 과정은 심플하게 말씀드리자면 용량이 크니 샘플링을 해주고 그 샘플링 해준 데이터들을 iterative 해준다는 의미입니다.
customized dataset 이 이해가 잘 안된다 싶으시면 이 블로그를 추천드립니다. 특히 Dataset , Dataloader 이 뭐가 다르며, 무슨 요소때문에 memory efficient 가 되는지 유념하시면서 보시는걸 추천드립니다.

[https://towardsdatascience.com/building-efficient-custom-datasets-in-pytorch-2563b946fd9f]

Sparse tensor

from torch_sparse import coalesce

# Pre-compute graph representations and node features
data.edge_index = coalesce(data.edge_index, data.num_nodes, data.num_nodes)
data.x = data.x.to(device)
data.edge_index = data.edge_index.to(device)

#example
import torch
from torch_sparse import coalesce

index = torch.tensor([[1, 0, 1, 0, 2, 1],
                      [0, 1, 1, 1, 0, 0]])
value = torch.Tensor([[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7]])

index, value = coalesce(index, value, m=3, n=2)

torch_sparse function을 활용합니다. 간단하게 말씀드리자면 , numpy 의 csr , csc와 같은 형태로 row-wise compresssion technique 을 활용한다고 보시면 되겠습니다.
생소하실분들을 위해 깃헙 코드를 가져왔는데요, csr csc 형태와 거의 동일합니다. 익숙하신분들은 감이 오시겠으나 그래도 혹시모르니 활용하시기 전에 모듈 official example 과 주요 function을 보시는걸 추천드립니다.
[https://github.com/rusty1s/pytorch_sparse/tree/e55e8331ef2881b934036054cbcd39f8efcd4725]

Mini-batching

# Set the mini-batch size
batch_size = 32

# Split the data into mini-batches
num_batches = len(data) // batch_size
data_split = torch.split(data, batch_size)

# Train the network
for epoch in range(200):
    total_loss = 0
    for batch in data_split:
        optimizer.zero_grad()
        out = model(batch.x, batch.edge_index)
        loss = criterion(out[batch.train_mask], batch.y[batch.train_mask])
        total_loss += loss.item()
        loss.backward()
        optimizer.step()
    if epoch % 20 == 0:
        print("Epoch: {:03d}, Loss: {:.4f}".format(epoch, total_loss / num_batches))

mini-batch size를 선언해주고 data 의 length 로 나누어줍니다. 그리고 torch split 로 나누어줍니다. 간단하게 생각하면 그래프 하나를 여러 서브그래프로 나누어준다고 보시면 될 거 같아요. 그렇다면 바로 한가지 문제가 떠오를텐데요! 바로 중요한 엣지를 나누어줘서 학습에 성능저하를 줄수도 있겠네? 라는 문제입니다.

그 문제에 관해서는 [cs224w-08gnnapplication] 에서 transductive vs. inductive learning 이라는 항목으로 잘 설명되어 있습니다 :) 혹시보고 이해가 되지 않으시다면 이메일로 문의주세요!

Backend

대망의 마지막입니다. 코드부터 보겠습니다.

############### graph structure informatioin ###############

graph_store = CustomGraphStore()

edge_index = torch.tensor([[0, 1, 1, 2], [1, 0, 2, 1]])

# Put edges:
graph_store['edge', 'coo'] = coo

# Access edges:
row, col = graph_store['edge', 'coo']
assert torch.equal(row, edge_index[0])
assert torch.equal(col, edge_index[1])

############### graph feature informatioin ###############

feature_store = CustomFeatureStore()

paper_features = ...  # [num_papers, num_paper_features]
author_features = ...  # [num_authors, num_author_features]

# Add features:
feature_store['paper', 'x', None] = paper_features
feature_store['author', 'x', None] = author_features

# Access features:
assert torch.equal(feature_store['paper', 'x'], paper_features)
assert torch.equal(feature_store['paper'].x, paper_features)
assert torch.equal(feature_store['author', 'x', 0:20], author_features[0:20])

# `CustomGraphSampler` knows how to sample on `CustomGraphStore`:
node_sampler = CustomGraphSampler(
    graph_store=graph_store,
    num_neighbors=[10, 20],
    ...
)

[https://pytorch-geometric.readthedocs.io/en/latest/advanced/remote.html]

되게 심플해보이지만 내부를 보면 어지럽습니다. 심플하게 말씀드리자면 , 그래프 node, edge feature 정보는 key-value DB 에 적재, 그래프 structure 정보는 graph DB 에 적재한 뒤 샘플링하며 training 하는 방법입니다.
그래프 오마카세 구독자분들은 익숙하실거라 생각되네요. 제가 3주 가까이 large graph dataset 관련 논문들을 리뷰했었는데 그 과정들이 그대로 반영되어 있습니다. 아마존에서는 training 후 발생하는 embedding 값을 neptune 에 적재해서 DB inference 하는데 난이도가 어마무시해보이더라구요.
마지막 항목은 사실 올해 제 숙제 중 하나입니다. DB tunning 에 대해서도 알아야한다는 점이 부담되어 지금 구현을 망설이고 있네요. 그래도 빨리 구현해서 오마카세 구독자 분들에게 좋은 그래프 정보를 전달한다는 사명이 있기에 상반기내로 추진해보도록 하겠습니다 …!