[paper reivew] Dynamic Hypergraph Neural Networks

date

Apr 29, 2023

slug

Dynamic-Hypergraph-Neural-Networks

author

status

Public

Introduction

hypergraph는 relation modeling의 일반화된 버전이다. 일반적인 그래프는 pairwise relation밖에 표현할 수 없지만, hypergraph 같은 경우 2개 이상의 노드를 한 hyperedge로 연결 가능하기 때문에 한 hyperedge 간 속한 노드들 간의 상관관계를 보일 수 있다. hypergraph는 node (hypernode라고도 한다)의 집합과 hyperedge의 집합으로 구성되어 있다. 하나의 hyperedge는 위에서 말했듯 여러 개의 노드를 포함할 수 있다. hyperedge가 포함하는 정점이 2인 경우에, 이 hyperedge와 정점의 셋은 simple graph를 구성한다고 볼 수 있다. 따라서 simple graph는 hypergraph의 부분집합이다.

기존에 hypergraph를 보델링하는 HGNN, HGCN등의 방법들이 있었지만, 이들은 초기의 hypergraph structure를 사용하여 모델링을 한다. 이는 hypergraph structure이 학습에 따라 다양하게 변형될 수 있음을 무시한다. 이 논문에서는 단 한번의 hypergraph embedding을 초기 단계에서 수행하는 것이 아닌 다른 방법을 제안하는데, 이를 dynamic hypergraph neural networks(DHGNN)이라고 한다. 이 모델은 Dynamic Hypergarph Construction (DHG) 모듈과 Hypergraph Convolution (HGC) 모듈로 이루어져 있다.

Dynamic Hypergraph Neural Networks (DHGNN)

Dynamic Hypergraph Construction (DHG)

Hypergraph Convolution (HGC)

DHG 부분에서는 k-NN method, k-means clustering method를 사용해서 hypergraph structure를 업데이트한다. HGC에서는 hypergraph convolution을 진행하기 위해 vertex convolution 이후 hyperedge convolution을 진행하는 메커니즘을 제안했다.

Hypergraph Construction

hypergraph 데이터셋은 구축이 복잡하기 때문에 공개된 데이터셋이 거의 없다. 따라서 이 논문과 선행 논문에서는 일반적인 graph에 k-nn method, k-means clustering 등을 사용하여 hypergraph를 구성하는 방법을 사용한다. 최근 hypergraph learning 방법에서는 hyperedge weight를 사용하여 더 높은 중요도를 가진 hyperedge에 더 높은 weight를 준다. HGNN에서는 Hypergraph Laplacian을 소개함으로써 hypergraph에 deep learning을 소개한 논문이 되었다.

Model (DHGNN)

DHC (Dynamic Hypergraph Construction)

주어진 feature embedding matrix X에 대해서,

Con(e)를 hyperedge e가 포함하는 vertex set이라고 정의한다.

Adj(u)는 vertex u를 포함하는 모든 hyperedge set이라고 정의한다.

이렇게 정의했을 때 hyperedge를 잡기 위해 k-nn, k-means clustering 알고리즘을 사용하여 k-1개의 neighborhood와 root vertex를 묶어 하나의 hyperedge로 정의한다. 이렇게 만든 hyperedge는 Adj(u)로 표현할 수 있다. k-nn 알고리즘을 사용할때 vertex의 input feature embedding을 사용하는데, 학습하면서 input feature embedding이 변화함에 따라 hyperedge가 달라지는 것을 이 논문에서는 Dynamic Hypergraph Construction이라고 한다. deep neural network을 통해 더 좋은 hypergraph structure를 얻을 수 있다는 것이다.

Algorithm 1. Hypergraph Construction

Input : Input embedding X; hyperedge size k; adjacent hyperedge set size S

Output: Hyperedge set G

Function: kMeans, knn, dis (distance function), smallest distance index selecction topK

C = kMeans(X)

for u in range(len(X)) do

e_b = knn(X[u], X, k)

G[u].insert(e_b)

D = dis(C.center, u)

D = sort(D)

ind = topK(D, S-1)

for i in ind do

G[u].insert(C[i])

end for

HGC (Hypergraph Convolution)

HGC는 vertex convolution과 hyperedge convolution 두 개의 서브모듈로 이루어져 있다. vertex convolution은 vertex feature를 hyperedge로 aggregate하고, hyperedge convolution은 adjacent hyperedge feature를 centroid vertex로 aggregate한다.

vertex convolution은 MLP로 만들어진 learnable transform matrix T로 수행된다.

이후 hyperedge convolution을 수행하는데, 이 단계에서는 hyperedge feature x_e를 centroid vertex feature로 aggregate한다. 다음과 같은 식으로 수행된다:

DHGNN (Dynamic Hypergraph Neural Networks)

위의 두 서브모듈을 종합하여 DHGNN 모델을 완성한다. 먼저 각각의 hyperedge e 에서 k개의 vertex를 sample하면 d-dimensional한 k개의 정점에 대한 embedding을 얻을 수 있다. k개의 정점에 대해 vertex convolution을 수행한다면 각각의 hyperedge에 대해 d-dimensional한 hyperedge embedding을 얻을 수 있다. 그 뒤 우리는 u에 인접한 hyperedge Adj(u)개의 hyperedge embedding을 concat하여 hyperedge embedding matrix X_e를 얻는다. 그 이후 hyperedge convolution을 수행하여 vertex u로 hyperedge feature를 aggregate 시킨 뒤 downstream task를 진행한다.

Algorithm 2. Hypergraph Convolution

Input: Input sample x_u; hypergraph structure G

Output: Output sample y_u

xlist = []

for e in Adj(u) do

X_v = VertexSample(XG)

x_e = VertexConv(X_v)

xlist.insert(x_e)

end for

X_e = stack(xlist)

x_u = EdgeConv(X_e)

y_u = activation(x_uW+b)