node들은 feature $X$로 표현됨. 차원은 $N$(노드 개수) x $D$(feature 차원)
adjacency matrix $A$는 edge로 연결되어 있으면 1, 아니면 0인 matrix임. 차원은 $N$x$N$
우리 결국 하고자 하는 것은 feature $X$와 $A$를 받고 강화된 node 표현 $H$를 만드는 것이다. 이때 함수는 보통 이렇게 정의된다.
$f$는 그래프를 인코딩 하는 함수다.
여기서 loss는 node 분류 태스크와 같은 걸 한다면 cross entropy loss가 걸리게 된다
결국 GNN의 다양한 variants들은 $f$를 어떻게 구성할까?가 문제다.
Neighbor Aggregation Methods
graph learning을 할 때 가장 효율적인 방법 중 하나가 neighbor aggregation mechanism인데, feature vector $x_i$와 그 neighbor인 j들에 대해서 feature vector를 aggregate하는 것이다.
가령 Graph Convolution Network(GCN)도 그 종류들 중 하난데, 식을 아래와 같이 쓸 수 있다.
이걸 조금 더 general 하게 쓰면 아래와 같이 쓸 수 있다.
하지만 GCN은 transductive 하게 밖에 못쓰는데, 그래프 구조가 바뀌면 새로 학습을 해줘야한다.
Graph Attention Networks(GAT)
GCN과 유사하게 neighborhood를 aggregate하는데, attention 을 사용해서 어떤 ege에 집중할지를 attention score를 구하게 되면 GAT가 된다.
그런데 이 경우에, attention score를 각 edge별 중요도라고 볼 수 있는데 layer마다 attention score가 달라지기 때문에 해석은 어렵다.
그래프를 만들 때 noisy/task-irrevalent한 edge들을 정리하기 위해 SGAT를 제안한다!
SparseGAT(SGAT)
중요한 edge만 남기기 위해서 binary gate $z{ij}$를 각 ege 별로 추가한다. 이 $z{ij}$는 edge $e_{ij}$를 사용할지 말지에 대한 bianry masking을 하게 된다.
최대한 적은 edge를 남기기 위해 loss term에 L0 loss를 추가한다. $z_{ij}$ 가 1이면 1 아니면 0인걸 sum하는 term이다.(edge 개수에 대한 loss)
attention based aggregation function은 아래와 같이 쓸 수 있는데 (GAT)와 다른 게 없음
이때 attention score를 아래와 같이 구한다.
-> $z_{ij}$는 어떻게 학습이 되는건지?
이렇게 sparse 하게 구성하게 된 시작은 attention score에 대한 head별 layer 별 분산을 구해봤는데 아래와 같이 거의 0에 가까웠기 때문임.
paper, code
TL;DR
Details
GNN in general
$G$ = ( $V$, $E$ ) 그래프는 node( $V$ )와 edge ( $E$ )로 구성
node들은 feature $X$로 표현됨. 차원은 $N$(노드 개수) x $D$(feature 차원)
adjacency matrix $A$는 edge로 연결되어 있으면 1, 아니면 0인 matrix임. 차원은 $N$x$N$ 우리 결국 하고자 하는 것은 feature $X$와 $A$를 받고 강화된 node 표현 $H$를 만드는 것이다. 이때 함수는 보통 이렇게 정의된다.
$f$는 그래프를 인코딩 하는 함수다.
여기서 loss는 node 분류 태스크와 같은 걸 한다면 cross entropy loss가 걸리게 된다
결국 GNN의 다양한 variants들은 $f$를 어떻게 구성할까?가 문제다.
Neighbor Aggregation Methods
graph learning을 할 때 가장 효율적인 방법 중 하나가 neighbor aggregation mechanism인데, feature vector $x_i$와 그 neighbor인 j들에 대해서 feature vector를 aggregate하는 것이다. 가령 Graph Convolution Network(GCN)도 그 종류들 중 하난데, 식을 아래와 같이 쓸 수 있다.
이걸 조금 더 general 하게 쓰면 아래와 같이 쓸 수 있다.
하지만 GCN은 transductive 하게 밖에 못쓰는데, 그래프 구조가 바뀌면 새로 학습을 해줘야한다.
Graph Attention Networks(GAT)
GCN과 유사하게 neighborhood를 aggregate하는데, attention 을 사용해서 어떤 ege에 집중할지를 attention score를 구하게 되면 GAT가 된다.
그런데 이 경우에, attention score를 각 edge별 중요도라고 볼 수 있는데 layer마다 attention score가 달라지기 때문에 해석은 어렵다. 그래프를 만들 때 noisy/task-irrevalent한 edge들을 정리하기 위해 SGAT를 제안한다!
SparseGAT(SGAT)
중요한 edge만 남기기 위해서 binary gate $z{ij}$를 각 ege 별로 추가한다. 이 $z{ij}$는 edge $e_{ij}$를 사용할지 말지에 대한 bianry masking을 하게 된다.
최대한 적은 edge를 남기기 위해 loss term에 L0 loss를 추가한다. $z_{ij}$ 가 1이면 1 아니면 0인걸 sum하는 term이다.(edge 개수에 대한 loss)
attention based aggregation function은 아래와 같이 쓸 수 있는데 (GAT)와 다른 게 없음
이때 attention score를 아래와 같이 구한다.
-> $z_{ij}$는 어떻게 학습이 되는건지?
이렇게 sparse 하게 구성하게 된 시작은 attention score에 대한 head별 layer 별 분산을 구해봤는데 아래와 같이 거의 0에 가까웠기 때문임.