12. Graph neural networks

 

대학원 수업 'Deep Learning', 교재 'Understanding Deep Learning', 그리고 직접 찾아서 공부한 내용들을 토대로 작성하였습니다.

---

 

이전에 우리는 규칙적인 배열의 data를 처리하는 데에 특화된 convolutional network와, 다양한 길이의 sequence를 처리하는 데에 특화된 transformer에 대해 알아봤습니다. 이번 chapter에선 'graph neural network'에 대해 알아보겠습니다. 이름에서 알 수 있듯, graph를 처리하는 neural architecuture입니다.

 

graph를 다루는 데엔 3가지의 challenge가 있습니다.

1. topology가 다양하고, 이 variation을 다루면서도 충분히 표현할 수 있는 network를 설계하는 것이 어렵습니다.

2. graph는 보통 거대합니다. social network에서 user들기리의 connection을 표현하는 graph엔 billion node가 존재합니다.

3. 오직 가능한 single nomolithic graph가 있어서, 많은 data example에 대해 training의 protocol과 새로운 data에 대해 testing하는 것은 항상 적절하진 않습니다.

 

이 chapter는 현실에 존재하는 graph의 예시들에 대해 알아보며 시작합니다. 

그 다음엔 graph를 어떻게 encoder하고 graph에 대해 어떻게 supervised learning problem을 formulate하는지 설명합니다. 

 

 

What is a graph?

"A graph consists of a set of nodes or vertices, where pairs of nodes are connected by edges or links"

graph는 매우 일반적인 구조이고 node의 set으로 이루어져 있습니다. 이 때 node의 pair는 edge로 이어져 있습니다. graph는 보통 sparse하고, 가능한 edge 중 작은 subset만 존재합니다.

현실에 있는 다양한 상황들을 우리는 graph의 형태로 바꿀 수 있습니다. 도로 network는 node가 물리적인 위치로, 그 위치사이를 표현하는 것을 edge로 graph를 표현할 수 있습니다. 

게다가, 이게 명백한 surface form이 아니여도 많은 dataset은 graph에 의해 표현될 수 있습니다. 

 

Some objects, such as a) road networks, b)molecules, and c) electrical circuits, are naturally structured as graphs

 

 

게다가, 'set'도 모든 member를 node로 두고 그들을 잇는 것을 edge로 둬서 graph로 다룰 수 있습니다. image도 regular topology를 이용해 graph로 다룰 수 있습니다. 이 때 각 pixel은 node가 되고, edge는 adjacent pixel이 됩니다.

 

 

Types of graphs 

graph는 다양한 방식으로 분류할 수 있습니다. 보통 social network는 'undirected edge'를 포함합니다. connection을 갖는 각각의 pair는 서로 친구이고, 관계에서 방향이 있는 것은 적절하지 않습니다. 반대로, citation network는 'directed edge'를 포함합니다. 각 paper는 다른 paper를 인용하고 이 관계는 한 방향으로 흐릅니다.

 

a) undirected graph (e.g., social network - connections betweenn people are symmetric)

b) directed graph (e.g., citation network - one publication cites another, so the relationshipp is asymmetric)

c) heterogeneous multigraph (e.g., knowledge graph - the nodes are heterogeneous in that they represent different object types and multiple edges may represent different relations between each node) 

 

figure c는 'knowledge graph'를 묘사하니다. 이는 어떤 object끼리의 관계를 정의함으로써 fact의 set을 encode합니다. 엄밀히 말하자면, 이는 'directed heterogeneous multigraph'입니다. 여기선 node가 각 다른 종류의 entity를 표현하기 때문에 heterogeneous입니다. 또 두 node사이에 다양한 type의 여러 edge를 포함하기 때문에 multigraph입니다. 

 

figure d는 airplane을 point set으로 표현한 것으로 K nearest neighbor에 해당하는 각 point를 연결함으로써 graph로 표현할 수 있습니다. 결과는 3D 공간에서 각 point들의 위치와 관련되게 geometric graph 형태가 됩니다. 

d) geometric graph - a point set can be converted to a graph by forming edges between nearby points. each node has an associated position in 3D space 

 

figure e는 hierarchical graph입니다. table,light,room는 각각 그들의 component의 adjacency를 포함하는 graph에 의해 묘사됩니다. 이 3개의 graph는 그 자체로 또 다른 graph node가 됩니다.

graph의 모든 type은 deep learning을 이용해서 처리될 수 있습니다. 그러나, 이번 챕터에선 social network와 같이 undirected graph에 초점을 맞춰 알아보겠습니다.

e) hierarchical graph - topology of the room, and light are all represented by graphs. these graphs form nodes in a larger graph representing object adjacency 

 

All types of graphs can be processed using deep learning

Howerver, this chapter focuses on undirected graphs like the social network 

 

 

Graph representation

graph structure 그 자체 뿐만 아니라, 각 node에 대해 information이 연관될 수 있습니다. social network에서 각 individual은 그들의 interect를 표현하는 고정된 길이의 vector를 이용해 characterize 될 수 있습니다. 가끔, edge도 information을 퐆함할 수 있습니다. road network에서 각 edge는 그들의 length, lane의 수, 사고 발생 수, 속도 제한등의 정보가 포함될 수 있습니다.  node에서 정보는 node embedding에 저장되고 edge의 정보는 edge embedding에 저장됩니다.

더 공식적으로 얘기하자면, graph는 E edge들의 set으로 연결된 N nodes의 set으로 이루어져 있습니다. graph는 3개의 matrix A,X,E에 의해 encoding되어 있고, 이는 graph structure, node embedding, edge embedding 각각을 표현합니다.  

이 graph 구조는 adjacency matrix A에 의해 표현됩니다. 이는 N x N matrix로 만약 m node와 n node 사이에 edge가 있다면 entry (m,n)는 하나의 set이고 그렇지 않다면 모두 0이 됩니다. undirected graph에서, matrix는 항상 symmetric합니다. 큰 sparse graph에서 memory를 절약하기 위해 connection (m,n)의 list로 저장할 수도 있습니다.

n번째 node는 길이 D의 node embedding x^(n)를 갖습니다. 이 embedding은 concat되고 DXN node data matrix X에 저장됩니다. 비슷하게, e번째 edge는 길이 D(e)의 edge embedding e^(e)를 갖습니다. 

 

In addition to the graph structure itself, information is typically associated with each node

The information at a node is stored in a node embedding, and the information at an edge is stored in an edge embeddings 

 

Graph representation

a) 6 nodes, 7 edges. 각 node는 길이가 5인 embedding을 가집니다 (brown vector). 각 edge는 길이가 4인 embedding을 가집니다 (blue vecotr). 이 graph는 3개의 matrix로 표현됩니다.

b) adjacency matrix A(NxN)는 element (m,n)에 node m이 node n과 연결되어 있으면 1로 설정하는 binary matrix입니다.

c) node data matrix X(DxN)는 concatenated node embedding을 포함합니다. (n번째 column은 D 길이의 node embedding x(n)을 저장합니다)

d) edge data matrix E(DexE)는 edge embedding을 포함합니다. (e번째 colu,n은 De길이의 edge embedding e(e)을 저장합니다)

 

 

Properties of the adjacency matrix 

 

adjacency matrix는 linear algebra를 사용해 이웃 node들을 찾는 데에 사용할 수 있습니다. 

n번째 node를 one-hot column vector로 encoding한다고 생각해봅시다. 이 vector를 adjacency matrix에 pre-multiply 하면, 이는 adjacency matrix의 n번째 column을 추출하고 이웃들의 위치를 포함하는 vector를 반환합니다. 이 과정을 반복하면, 결과 vector에는 node n으로부터 모든 node까지 길이가 2인 walk 수가 포함됩니다. 

일반적으로, adjacency matrix를 L번 거듭제곱하면, A^L의 (m,n) 위치에 있는 entry는 node n에서 node m까지 길이가 L인 unique한 walk 수를 포함합니다. 이 값은 같은 node를 한 번 이상 방문하는 route를 포함하기 때문에 unique한 path의 수는 아닙니다. 그럼에도 불구하고, A^L은 graph connectivity에 대한 정보를 포함합니다. position (m,n)에 있는 non-zero entity는 L보다 작거나 같은 m에서 n까지의 거리를 나타냅니다. 

 

즉, graph의 6번째 node를 나타내는 vector x가 주어졌을 때, (A^L)x믐 length L의 unique walk의 수를 타나냅니다. ?

 

 

 

Permutation of node indices 

"Though permutation of node indices doesn't change the underlying graph, it permutates the node data matrix X and adjacency matrix A"

graph에서 node indexing은 임시적입니다. node indexing을 permuting하면 node data matrix X의 column이 permute되고 adjacency matrix A의 row와 column vector모두 permute됩니다. 그러나 graph는 변하지 않습니다. 이는 image와 반대되는 것으로, image에선 pixel을 permuting하면 다른 image를 만들었습니다.

"One can construct a permutation matrix P. when position (m,n) oof the permutation matrix is set to one, it indiccates that node m will become node n after the permutation"

 

node index를 교환하는 작업은 수학적으로 'permutation matrix P'에 의해 표현될 수 있습니다. 이는 각 row와 column이 정확히 하나의 entry에서 value 1의 값을 갖고 나머지는 value 0을 갖습니다. permutation matrix의 position (m,n)이 1로 set될 때, 이는 permutation 이후에 node m이 node n이 되는 것을 의미합니다. 하나를 또 다른 하나로 mapping 하기 위해 다음과 같은 작업을 합니다 ( "To map from one indexing to another, we use the operations : ")

X'=XP

A'=P^(T)AP

(where post-multiplying by P permutes the columns and pre-multiplying by P^T permutes the rows)

 

 

permutation of node indices

a) example graph

b) associated adiacency matrix, c) node embeddings

d) index의 순서가 다른 같은 graph

e) adjacency matrix, f) node matrix 는 바뀌었습니다. 

결과적으로 , graph에서 동작하는 어떤 network layer도 node의 순서에 무관해야 합니다. 

 

 

 

Graph neural networks, tasks, and loss functions

graph neural network는 node embedding X와 adjacency matrix A는 input으로 갖고 K개의 layer를 통해 지나는 model이ㅣㅂ니다. node embedding은 최종 output embeddings HK를 계산하기 전에 중간의 "hidden" representation H(k)를 만들기 위해 update됩니다. ( The node embeddings are updated at each layer to create intermediate “hidden” representations Hk before finally computing output embeddings HK.)

이 network 시작할 때, input node embedding X의 각 column은 그 node 자체의 정보에 대해 갖고 있습니다. 마지막엔, model output Hk의 각 column엔 node와 graph에서의 context에 대한 정보를 포함합니다.

( At the start of this network, each column of the input node embeddings X just contains information about the node itself. At the end, each column of the model output HK includes information about the node and its context within the graph)

이는 transformer를 통해 지난 word embedding과 비슷한 구조입니다. 

 

 

Tasks and loss functions

supervised graph problem은 보통 3가지의 category로 이뤄집니다.

 

Graph-level tasks 

이 network는 structure와 node embedding 모두를 이용해 전체 graph에 대해 1개 이상의 label 혹은 estimate을 할당합니다. ( The network assigns a label or estimates one or more values from the entire graph, exploiting both the structure and node embeddings. )

<loss for graph-level tasks> 

graph-level task에서 output node embedding은 합쳐지고, 결과 vector는 linear transformation이나 neural network를 통해 정해진 size의 vector로 mapping 됩니다. regression에선, 결과와 ground truth value의 mismatch는 least square loss를 사용해 계산됩니다. binary classificaiton에선, output이 sigmoid function을 지나고 mismatxh는 binary cross-entropy loss를 이용해 계산됩니다. graph가 class 하나에 속할 확률은 다음과 같습니다. ( the output node embeddings are combined (e.g., by averaging), and the resulting vector is mapped via a linear transformation or neural network to a fixed-size vector. For regression, the mismatch between the result and the ground truth values is computed using the least squares loss. For binary classification, the output is passed through a sigmoid function, and the mismatch is calculated using the binary cross-entropy loss. Here, the probability that the graph belongs to class one might be given by:)

여기서 beta와 w는 learned parameter입니다.

output embedding matrix Hk에 column vector 1를 post-multiplying하는 것은 모든 embedding을 더하고 node N의 수로 나누는 것은 average를 계산하는 것을 의미합니다. (mean pooling을 의미)

 

 

Node-level tasks 

이 network는 graph의 각 node에 label이 할당되고, graph structure와 node embedding 모두 사용합니다. 예를 들어, 3D point cloud로부터 만들어진 graph가 있을 때, goal은 각 node가 wings에 속하는지 fuselage에 속하는지에 따라 분류하는 것입니다. loss function은 graph-level과 같은 방식으로 정의되고 각 node n에 대해선 다음과 같습니다.

 

Edge prediction tasks 

이 network는 node n과 m 사이에 edge가 있는지 없는지를 예측합니다. social network setting에서, network는 두 사람이 서로 아는지 예측합니다. 이는 binary classification task로 두 node embedding이 edge가 존재하는지에 대한 확률을 나타내는 single number에 두 개의 node embedding이 mapping되어 있어야 합니다. possibility를 얻는 방법은 node embedding에 dot product를 하고 probability를 만들기 위해 그 결과를 sigmoid function에 통과시키는 것입니다.

( This is a binary classification task where the two node embeddings must be mapped to a single number representing the probability that the edge is present. One possibility is to take the dot product of the node embeddings and pass the result through a sigmoid function to create the probability:)

 

 

 

 

Graph convolutional networks 

gnn에는 다양한 종류가 있지만, 여기서 우리는 'spatial-base convolutional graph neural networks' GCN에 대해 자세히 알아볼 것입니다. 이 model은 주변 node로부터 얻은 정보를 aggregate하면서 각 node를 update하기 때문에 convolutional 합니다.  이와 같이, 이는 'relational inductive bias'를 유발합니다. 그리고 original graph structure를 사용하기 때문에 spatial-based입니다. 이는 'spectra-based method'와 반대되고,이는 Fourier domain에서 convolution을 적용합니다.

( they update each node by aggregating information from nearby nodes. As such, they induce a relational inductive bias (i.e., a bias toward prioritizing information from neighbors). They are spatial-based because they use the original graph structure. This contrasts with spectral-based methods, which apply convolutions in the Fourier domain. )

 

GCN의 각 layer는 parameter에 대한 function F[]이고 이는 node embedding과 adjacency matrix를 받고 output으로 새로운 node embedding을 뱉습니다. 수식은 다음과 같이 작성합니다.

( Each layer of the GCN is a function F[•] with parameters Φ that takes the node embeddings and adjacency matrix and outputs new node embeddings. The network can hence be written as:)

여기서 X는 input, A는 adjacency matrix, Hk는 k번째 layer에서 수정된 node embedding을 포함합니다. Φk는 layer k에서 layer k+1로 mapping하는 parameter를 나타냅니다. ( where X is the input, A is the adjacency matrix, Hk contains the modified node embeddings at the k th layer, and ϕk denotes the parameters that map from layer k to layer k+1.)

 

 

Equivariance and invariance

graph에서 node의 indexing은 arbitrary하고, node index의 어떤 permutation을 해도 graph가 바뀌지 않는다고 했습니다. 그렇기 때문에 어떤 model이든 이 property를 고려해야 합니다. 각 layer는 node index들의 permutation에 대해 equivariant해야합니다. 즉, 만약 우리가 node index를 permute하면, 각 단계에서 node embedding은 같은 방식으로 permute될 것입니다. mathematical term에서, P가 permutation matrix면, 우리는 다음과 같은 식을 얻습니다.

( Each layer of GCN is equivariant with respect to permutations of the node indices, .i.e, the node embeddings at each stage will permute in the same way)

node classification과 edge prediction task에서, output도 node index의 permutation에 대해 equivariant해야 합니다.

 

그러나, graph-level task에서, 마지막 layer는 graph를 가로지르는 정보를 aggregate하고, output은 각 node 순서에 대해 invariant합니다. 이 사실을 통해, ( However, for graph-level tasks, the final layer aggregates information from across the graph, so the output is invariant Problem 13.6 to the node order. In fact, the output layer from equation 13.2 achieves this because)

for any permutation matrix P)

 

이를 알 수 있고, 그래서 어떤 permutation matrix P가 와도 위에서 본 다음 식을 만족합니다. 

 

 

해당 경우를 image와 비교했을 때, segmentationm은 geometric transformation에 대해서 equivariant 해야 하고, image classification은 invariant 해야 합니다. 여기서 convolutional과 pooling layer는 부분적으로 이 translation을 만족하지만, 더 일반적은 transfomation에 대해 이 property를 보장한다는 것을 알 방법은 없습니다.

그러나 graph 에선, permutation에 대해 equivariance, invariance 모두 보장하는 network를 정의할 수 있습니다.

 

 

 

Parameter sharing 

("As with convolutional networks for images, instead of learning a model with separate parameters associated with each node, we can use the same parameters at every node. This reduces the number of parameters and shares what the network learns at each node across the entire graph")

image에선 network가 각 image 위치마다 object를 개별적으로 인식하는 방법에 대해 학습해야하기 때문에 fully connected network를 적용하는 것이 적절한 선택은 아니라는 것을 알았습니다. 대신 image에 있는 모든 position에서 동일하게 적용되는 convolutional layer를 사용했습니다. 이는 parameter에 갯수도 줄여주고 model이 image의 모든 부분을  같은 방식으로 다룰 수 있도록 하는 inductive bias가 있었습니다.

graph의 node에 대해서도 동일합니다. 물론 각 node와 연관된 분리된 parameter로 model을 학습할 수 있습니다. 그러나 network는 graph의 connection의 의미를 독립적으로 학습해야 하고, training은 same topology에서 많은 graph를 필요로 할 것입니다. 대신, 우리는 각 node에 대해 동일한 parameter를 사용하는 model을 만들고, parameter의 수를 줄이면서 전체 graph에 걸친 각 node에 대해서 network가 학습할 수 있습니다.

convolution은 주변 정보로부터 weighted sum을 통해 variable을 update합니다.  각 neighbor가 message를 보내고, update하기 위해 이 message를 aggregate한다고 볼 수 있습니다. image 관점에서 보면 이웃은 현재 position 주변의 고정된 크기의 사각지역에 있는 pixel이 되고, 각 position의 spatial relationship은 같습니다.

그러나, graph에서, 각 node가 갖고있는 이웃의 수는 다 다르고, consistent relationship은 없습니다. 

관심 노드의 "위"에 있는 노드의 정보를 "아래"에 있는 노드의 정보와 다르게 가중치를 부여할 수 있다는 것은 의미가 없습니다

 

 

 

simple graph CNN layer

a) input graph는 어떤 structure(graph adjacency matrix A에 표시되지 않음)와 node embedding(X의 column에 저장)으로 구성됩니다. 

b) 첫번째 hidden layer의 각 node는 다음 과정을 거칩니다.

1. single vector 표현하기 위해 주변 node를 aggregate

2. aggregated node에 linear transformation Ω0 적용 

3. original node에도 똑같이 linear transformation Ω0 적용

4. β0와 같이 더함

5. 마지막으론 ReLU와 같은 nonlinear activation function a[] 적용 

c) 이 과정은 network의 끝 부분의 마지막 embedding을 만들때까지 subsequent layer에서 반복됩니다. 

 

 

 

Example GCN layer

이런 이유로 simple GCN layer가 탄생했습니다. layer k에 있는 각 node n에서, 우리는 node embedding h를 합쳐서 주변 node들로부터 정보를 aggregate합니다. 

이 때 ne[n]은 node n의 이웃 index의 set를 반환합니다. 그 다음 우리는 현재 node에서 embedding hk^(n)과 aggregated value에 linear transformation Ωk를 적용하고, bias term β를 더해주고, 그 다음 nonlinear activation function a[]를 지나 결과를 얻습니다. 이 때 각 vector argument에 독립적으로 적용됩니다. (we can consider a simple GCN where the neighboring node embedding is aggregated before each layer :)

 

vector에 의한 matrix의 post-multiplication은 column의 weighted sum을 return한다는 점을 알면 이것을 더 간결하게 쓸 수 있습니다. ( We can write this more succinctly by noting that post-multiplication of a matrix by a vector returns a weighted sum of its columns ).  adjacency matrix A의 n번재 column은 neighbor의 position을 포함합니다. 그러므로, DxN matrix Hk에서 node embedding을 얻고 adjacency matrix A에 의해 post-multiply를 하면, n번째 column의 결과는 agg[n,k]가 됩니다.

node의 update는 다음과 같습니다.  (1은 1을 포함한 Nx1 vector입니다)

 

여기서 nonlinear activation function a[]는 matrix argument의 각각 member에 독립적으로 적용됩니다.

이 layer는 다음의 고려사항을 만족합니다

: node index의 permutation에 대해 equivariant, neighbor의 수와 상관없이 처리 가능, relational inductive bias 제공하도록 graph structure 이용, graph에서 parameter 공유

 

 

Example : graph classification

지금까지 알아본 내용을 이제 molecule에 독성이 있는지, 혹은 해로운지에 대해 분류하는 network를 설계해봅시다. network input은 adjacency matrix와 node embedding matrix X입니다. adjacency matrix A ∈R^(NxN)는 분자 구조에서 유래합니다. node embedding matrix X ∈R^(118xN)의 column은 one-hot vector로 주기율표의 118개 원소 중 어떤 원소에 속하는지 나타냅니다. 즉, 그들은 관련된 element에 일치하는 position에서만 1이고 이를 제외하고 모든 position은 0인 길이가 118인 vector입니다. node embedding은 first weight matrix Ω0 ∈R^(Dx118)에 의해 arbitrary size D로 바뀔 수 있습니다. 

network equation은 다음과 같습니다.

network output f[X,A, Ω]는 분자가 toxic인지에 대한 probability를 나타내는 singe value입니다.

 

 

Training with batches

training graphs {Xi,Ai}와 label yi가 주어졌을 때, parameter Φ = {βk , Ωk}(k=0~K) 는 SGD와 binary cross-entropy loss를 사용해 학습됩니다. Fully connected networks, convolutional networks, transformer는 모두 요즘 hardware의 parallelism을 사용할 수 있어서 training example의 전채 batch를 동시에 진행시킬 수 있습니다. 이를 위해, batch element는 더 높은 dimensional tensor로 concate됩니다. 그러나 각 graph는 각각 node의 개수가 다릅니다. 그래서, matrix Xi와 Ai는 다른 크기를 갖기 때문에 3D tensor로 concat할 방법이 존재하지 않습니다.다행히도, 전체 batch를 parallel하게 다룬 simple trick이 존재합니다. batch의 graph는 하나의 큰 graph의 disjoint component로 다룰 수 있습니다. 그 다음 network는 network equation의 single instance로 실행될 수 있습니다. mean pooling은 loss function에 입력할 수 있는 graph 당 single representation을 만들기 위해 개별 graph에 대해서만 수행됩니다.

("Most architecures process batchs of data in parallel, where each batch element is concatenated into a higher-dimensional tensor. Howerver, this can't be done for GNNs due to each graph having a different number of nodes, making them hard to concatenate. Luckily, a simple trick is to treat graphs in the batch as disjoint components of a single large graph. Then we carry out mean pooling over the individual graphs to make a single representation per graph that can be fed into the loss function.")

 

 

Inductive vs transductive models

지금까지 이 책의 모든 model은 inductive였습니다. 우리는 input과 output사이의 관계를 학습하기 위해 labeled data set을 훈련에 사용했습니다. 그 다음 이를 새로운 test data에 적용했습니다. 다시 말하자면 input이 output에 mapping되는 rule을 학습하고 그다음 이를 적용해왔습니다. 

반대로, 'transductive' model은 동시에 labeled, unlabeled data 모두 고려합니다. rule을 제공하진 않고 그냥 unknown output에 대해 labeling을 합니다. 보통 'semi-supervised learning'이라 불립니다. 이는 결정을 할 때 도움을 주도록 unlabeled data에 있는 pattern을 사용할 수 있다는 장점이 있습니다. 그러나, 추가적으로 unlabeled data가 더해졌을 때 model이 다시 train되어야 한다는 단점이 있습니다.

이 문제는 graph에서도 자주 발생합니다. 가끔, 우리는 많은 labeled graph를 갖고 graph와 label사이의 관계를 mapping하도록 학습됩니다. 예를 들어, 우리는 많은 molecule를 갖고 각각은 독성이 있는지에 대해 labeling됩니다. 우리는 graph가 toxic/ non--toxic 중 어떤 label에 mapping되는지 학습하고 이 rule을 새로운 molecule에 적용합니다. 그러나 가끔은 single monolithic graph가 있습니다. 과학 논문 인용에 대한 graph가 있을 때, 우리는 몇 node에 대해 각 field를 나타내는 label을 가지고 남아있는 node에 대해서도 label을 붙이고 싶을 것입니다. 여기서 training과 test data는 되돌릴 수 없이 연결되어 있습니다. 

graph-level task는 오직 training과 test graph가 있는 inductive setting일 때만 발생합니다. 그러나, node-level task와 edge prediction은 transductive setting에서도 가능합니다. transductive case에서, loss function은 model output과 알려져 있는 ground truth간의 mismatch를 최소화합니다. 새로운 prediction은 forward pass를 진행하고 ground truth가 알려져 있지 않은 곳에서 결과를 되찾으면서 계산됩니다.

 

- iuductive model

: model trained from a set of fully labeled graphs, to label a set of unlabeled graph correctly. Until this point, all of the models in this chapter have been 'inductive')

- transductive model

: model trained from a single partially-labeled graph, to label the unlabeled parts of the graph. It utilizes patterns and embeddings of unlabeled data to help make its decisions. However, the model must be retrained when extra unlabeled data are added)

 

Example : node classification

두번째 예시로, transductive setting에서 binary node classification task를 고려해봅시다. million node에 대한 commercial-sized graph가 있다고 해봅시다. 몇 node는 ground truth binary label이 있고, goal은 label되지 않은 남아 있는 node에 label하는 것입니다. network의 본체는 이전 예시와 동일하지만 final layer가 다릅니다. final layer는 size가 1XN인 output vector를 제공합니다. 

여기서 sig는 row vector input의 각 element에 독립적으로 sigmoid function이 적용되는 것입니다. 보통, 우리는 binary cross-entropy loss를 사용하지만, 지금은 우리가 아는 ground truth label y를 아는 node에 대해서만 합니다. 위의 식은 그냥 node classification loss의 vectorized version입니다.

 

<Batch in transductive setting>

이렇게 (transductive setting) network를 훈련하면 2가지 문제가 있습니다.

1. Usually the network is huge, which involves both storing and processing a structure several times the size of the entire graph

2. It is not obvious how to perform stochastic gradient descent with only a single graph

만약 single object만 있다면, batch를 어떻게 형성할 수 있을까요?

 

Choosing batches 

 

receptive field

batch를 형성하는 방법 중 하나는 각 training step에서 labeled nodes의 random subset을 선택하는 것입니다. 각 node는 이전 layer의 그 노드의 이웃들에 depend합니다. 이들은 이전 layer의 이웃들에 의존하고, 그래서 각 node는 receptive filed의 에 equivalent합니다.

receptive field의 size는 'k-hop neighborhood'라고 합니다. 그렇기 때문에 graph를 사용해 gradient descent step을 실행합니다. 이 때 batch node의 k-hop neighborhood의 union을 형성하게 됩니다. 남아있는 input은 기여하지 않습니다. 

 

receptive fields in graph neural networks

hidden layer 2의 orange node를 생각해봅시다. 이는 hidden layer 1의 1-hop neighborhood에 있는 node로부터 input을 ㅂ받습니다. hidden layer1에 있는 이런 node들은 그 전의 input에서 그들의 neighbor로부터 받습니다. 그리고 layer 2의 orange node는 2-hop neighborhood의 input node로 부터 모두 input을 받습니다. 주어진 node에 기여하는 graph의 region은 cnn에서의 receptive field의 개념과 동일합니다. 

 

<problem with the receptive field approach>

불행하게도, 많은 layer가 있고 graph가 빽빽하게 연결되어 있으면, 모든 input node는 모든 output의 receptive field일 것이고, 이는 graph size를 줄이지 못할 것입니다. 이런 문제를 'graph expansion problem'이라 부릅니다. 이런 문제를 다루기 위해 두 가지 방법이 존재합니다.

 

 

Neighborhood sampling

node들의 batch에 들어가는 full graph가 sampling되고, 그렇기 때문에 각 network layer에서 connection이 줄어듭니다. 

예를 들어, 우리는 batch node로 시작하고 이전 layer의 고정된 수의 그들의 이웃들을 랜덤하게 sample합니다. 그 다음, 이전 layer에 있는 고정된 수의 그들의 이웃을 랜덤하게 sample합니다. (As we work back from the final layer, we select a subset of neighbors in the layer before and a subset of the neighbors of these in the layer before that. This restrics the size of the graph for training the batch") 이 과정을 반복합니다. graph는 여전히 각 layer를 지날수록 size가 커지지만 훨씬 더 통제된 방식으로 표시됩니다. 이 과정은 각 batch에서 다시 진행되고, 같은 batch가 두 번 나온다 해도 기여하는 이웃들은 달라지게 됩니다. 이는 dropout을 연상시키고 몇 regularization을 추가합니다 

Neighborhood sampling

a) large graph에서 batch 형성하는 방법 중 하나는 output layer에서 labeled node의 subset을 선택하는 것입니다. (여기선 오른쪽 output graph를 보면 그냥 하나의 node를 선택) 그리고 K-hop neighborhood에서 찾은 모든 node를 다시 똑같이 동작시킵니다. 오직 이 sub-graph만 이번 batch를 훈련하는 데 필요합니다. 불행하게도, 만약 graph가 빽빽하게 연결되어 있으면 여전히 graph의 많은 부분을 차지할 것입니다.

b) 하나의 해결책은 neighborhood sampling입니다. 마지막 layer에서 다시 진행하고,그 전 layer의 neighbor의 subset과 지금 layer의 neighbor의 subset을 선택합니다. 이는 훈련하는 batch에 대해 graph의 size를 제한합니다. 모든 패널에서 밝기는 원래 node로부터의 거리를 나타냅니다 (3)

 

 

Graph partitioning 

두 번째 방법은 processing 하기 전에 node의 disjoint subset에 대해 original graph를 cluster합니다. (cluster the original graph into disjoint subsets of nodes(o.e., smaller graphs that are not conncected to one another) before processing) (각자 연결되어 있지 않은 smaller graph) internal link의 수를 최대화하는 subset을 선택하도록 하는 standard algorithm이 존재합니다. 이런 smaller graph는 각 batch로 다뤄질 수 있거나, 그들이 random subset이 batch 형성하도록 결합될 수 있습니다. (These smaller graphs can each be treated as batches, or a random subset of them can be combined to form a batch)

graph partitionaing

a) input graph

b) input graph는 가장 적은 edge를 제거하는 principled method를 사용해 더 작은 subgraph로 나눕니다.

c-d) 이 subgraph들을 transductive setting에서 훈련할 수 있도록 batch로 사용할 수 있고,여기선 4개의 batch가 존재합니다. 

e) 대신, subgraph의 combination을 batch로 사용할 수 있고, 그들 사이에 존재하는 edge는 다시 원상태로 돌려놓습니다. 우리가 subgraph의 pair를 사용한다면 6개의 가능한 batch가 존재합니다. 

 

 

batch 형성하는 위의 방법 중 하나가 주어졌을 때, 우리는 inductive setting과 같은 방법으로 network parameter를 훈련할 수 있고, labeled node를 원하는 대로 train, test, validation set으로 나눌 수 있습니다. 우리는 효과적으로 transductive problem을 inductive problem으로 바꿀 수 있습니다. inference할 땐, 그들의 k-hop neighborhood에 기반에 모르는 node에 대해 prediction을 합니다. training과 다르게, 중간 representation을 저장할 필요 없기 때문에, 훨씬 memory 관점에서 효율적입니다.

 

 

Layers for graph convolutional networks 

이전의 예시에서, 우리는 변형된 현재 node를 같이 합함으로써  adjacent node로부터 message를 합칩니다.  

이전엔 adjacebcy matrix와 identity matrix A+I에 node embedding matrix H를 post-multiplying를 하며 message를 합쳤습니다. 지금은 (1) 합쳐진 neighbor과 현재 embedding의 combination (2) 그 자체로 aggregation process 이 두가지 접근 방법에 대해 알아보겠습니다. 

( In the previous examples, we combined messages from adjacent nodes by summing them together with the transformed current node. This was accomplished by post-multiplying the node embedding matrix H by the adjacency matrix plus the identity A +I. We now consider different approaches to both (i) the combination of the current embedding with the aggregated neighbors and (ii) the aggregation process itself.)

 

 

Combining current node and aggregated neighbors 

위의 GCN example에서, aggregated neighbor HA를 current node H와 그냥 더함으로써 합칩니다. 

( In the example GCN layer above, we combined the aggregated neighbors HA with the current nodes H by just summing them:)

 

 

다른 variation으로, sum하기 전에 현재 node가 (1+epsilon)이라는 factor에 의해 곱해집니다.

( In another variation, the current node is multiplied by a factor of (1 + ϵk) before contributing to the sum, where ϵk is a learned scalar that is different for each layer:)

이 방법을 'diagonal enhancement'라고 합니다.

 

 

다른 linear transform을 적용하는 또 다른 variation은 다음과 같습니다.

( A related variation applies a different linear transform Ψk to the current node:)

 

 

 

Residual connection

residual connection을 사용해, neighbor로부터 합쳐진 representation은 현재 node와 합쳐지거나 concat되기 전에 변형되고 activation function을 통과합니다.

( With residual connections, the aggregated representation from the neighbors is transformed and passed through the activation function before summation or concatenation with the current node. For the latter case, the associated network equations are:)

 

 

Mean aggregation

위의 방법은 node embedding을 다 더해서 neighbor을 합치는 방법입니다. 그러나, 또 다른 방법으로 embedding을 결합할 수도 있습니다. 그냥 sum을 하는 것보다 neighbor의 average를 구하는 것이 훨씬 좋을 수도 있습니다. 만약 embedding information이 structural information보다 중요해서 neighborhood의 기여의 정보가 neighbor의 이웃에 의존하지 않기 때문에 훨씬 이런 경우엔 average가 좋을 것입니다. 

이 때 ne[n]은 n번째 node의 neighbor의 index를 포함하는 set을 의미합니다. 위의 식은 diagonal NxN matrix D에 의해 matrix form으로 계산될 수 잇습니다. 

( this can be superior if the embedding information is more important and the structural information less so since the magnitude of the neighborhood contributions will not depend on the number of neighbors)

 

(This can be expressed in the following matrix form by introducing the diagonal NxN degree matrix D where each contains the number of neighbors for the associated node: )

 

Kipf normalization

mean aggergation을 기본으로 gnn에는 많은 variation이 있습니다. 가끔 current node가 각각 다뤄지기보단 mean computation에서 neighbor에 포함되는 경우가 있습니다. Kipf normalization에선, node representation의 sum을 다음과 같이 normalize합니다 :

아주 많은 이웃이 있는 node에 대한 정보가 올 땐 아주 많은 connection이 있고 unique한 정보를 적게 전달하기 때문에 'down-weighted'해야 합니다. 이는 다음과 같이 degree matrix를 사용해 matrix form으로 표현될 수도 있습니다. 

 

 

Max pooling aggregation

permutation에 invariant한 또 다른 대체 operation은 object의 set의 maximmu을 계산하는 것입니다. 

'max pooling' aggregation operator는 다음과 같습니다 :

이 때 operator max[.]는 vector hm의 element-wise maximum을 반환하고, 이 vector는 current node n의 neighbor입니다. 

 

 

Aggregation by attention

지금까지 aggregation method는 neighbor의 contribution에 똑같이 weight을 주거나 graph topology에 따라 weight을 줬습니다. 반대로, 'graph attention layer'에선, weight가 node에 있는 data에 따라 정해집니다. linear transform은 현재 node embedding에 적용되고 이는 다음과 같습니다 :

각 transform된 node embedding h'(m)과 h'(n)의 similarity s(mn)은 pair를 concat하고 학습된 parameter인 column vector фk에 dot product를 하고 activation function을 취함으로써 계산됩니다. 

이 variable들은 NxN matrix A에 저장되고, 각 element는 모든 node들끼리의 similarity를 표현합니다. dot-product self-attention에서, 각 output embedding에 contribute한 attention weight은 양수로 정규화되고 softmax operation을 이용해 하나로 합해집니다. 그러나 current node와 그 이웃에 해당하는 value만 기여해야 합니다. attention weight는 transformed embedding에 적용됩니다:

(finally, softmask[.,] is applied to matrix S which zeros out entries in S corresponding to non-neighboring nodes. This is then used to sompute the next hidden state:)

 

 

여기서 a[]는 2번째 activation function입니다. function softmask[,]는 각각 column의 첫번째 argument s에 대해 softmax를 취함으로써 attention value를 계산하지만, 두 번째 argument  'A + I'가 0에서 음의 무한대까지이므로 contribute 하지않는 값을 설정한 후에만 가능합니다. 이는 nonneighboring node가 attention이 0이되는 것을 보장합니다.

 

 

 

 

 

이 과정은 다음과 같은 점만 빼곤 transformer의 self-attentionn computation과 매우 비슷합니다.

1. keys, queries, and values are all the same

2. measure of similarity is different 

3. attentions are masked so that each node only attends to iteself and its neighbors 

 

transformer에선, 이 system이 동시에 계산하고 합쳐질수있는 multiple head를 사용해 확장됩니다. 

 

 

 

Edge graph

지금까지 node embedding을 methods에 대해 집중했는데, 이 방법들은 'edge graph'나 'adjoint graph'를 이용해 edge embedding에 적용하기 쉽습니다. 

edge grapph는 모든 edge들이 node가 되고, 공통된 node에 대한 모든 2개의 edge는 새로운 graph에 새로운 edge가 되는 complementary graph입니다.

edge embedding을 진행하기 위해, 우리는 node embedding에 대한 method를 transformed edge graph에 적용합니다. 

 

 

Summary

- graph은 node의 set으로 구성되고, node들의 pair는 edge에 의해 연결되어 있습니다. node와 edge는 모두 data를 가질 수 있고, 각각은 node embedding, edge embedding이라 불립니다. 현실의 많은 문제는 graph로 여겨질 수 있고, 여기서 goal은 전체 graph의 특징, node 혹은 edge, 혹은 graph에서 추가적인 edge의 존재와 같은 특징을 설립할 수 있습니다.

- gnn은 graph에 적용하는 deep learning model입니다. graph의 node order는 임의적이기 때문에, gnn의 layer는 node index의 permutation에 대해 equivariant해야 합니다. spatial-based convoluional network는 node의 이웃들로부터 정보를 취합하는 graph neural network의 family이고 이는 node embedding을 update하는 데에 사용합니다.

- graph를 처리하는 과정에서 어려운 점 중 하나는 이런 과정은 자주 transductive setting에서 발생하고, 이는 각 training graph와 test graph의 set으로 이루어지기 보단 부분적으로 labeling된 graph가 하나 존재합니다. 이 그래프는 매우 클 수 있고, 이는 training 과정에서 문제를 야기하고 sampling과 partitioning algorithm으로 해결해줘야 합니다. edge graph는 original graph의 모든 edge의 node를 가집니다. 이 표현을 변형함으로써, graph는 edge embedding을 update하는 데에 사용할 수 있습니다.