딥 러닝의 데이터 처리에는 아주 많은 입력 데이터가 아주 깊고 복잡한 연산들을 수행하게 된다. 그래프 구조 데이터는 단순하게 노드와 엣지로 이루어진 관계를 나타내는 데이터로써, 쉬운 예로 SNS 친구 목록의 "알 수도 있는 친구"와 같은 관계를 정의한다. 이때, 입력 데이터를 이와 같은 그래프 구조 데이터로 처리한다면, 벡터로 처리했을 때보다 중복 정보를 깔끔하게 정리하고 효과적으로 처리할 수 있다.
• Feed-forward Neural Networks (FNN) - An FNN is a stack of fully-connected layers. - 앞 장에서 이미지 및 Multi-Dimensional Array 형태의 입력을 처리하는 CNN, Sequantial Data 형태의 입력을 처리하는 RNN 등이 존재하였다면, 이번에는 Graph-Structured Data 형태의 입력을 처리하는 GNN 이 있다. Feed-forward Neural Networks • Comparison of FNN and GNN - Learning from Conventional Data : Scalar, Vector, Matrix, Multi-Dimensional Array, ... (Fixed-size inputs) - Learning from Graph-Structured Data : Graph Data (Variable-size graphs inputs) -. Each graph has different numbers of nodes and edges (각 그래프 별 다른 수의 node/edge 가짐) Graph-Structured Data - Graph isomorphism: (그래프 동형) → Prediction must to be invariant to graph isomorphism ① Graph-Structured Data 형태는 node (객체) 와 edge (관계) 으로 이루어져 있음 (direction 유/무) ② 관계만을 명시하며, 순서가 중요하지 않기 때문에 엄연히 다른 벡터일지라도 상동일 수 있음 ③ 각 그래프는 모두 다른 수의 nodes 와 edges 를 가질 수 있다. -. 아래는 그래프 동형을 통한 벡터 정보의 중복을 줄이는 예시이다.
Graph isomorphism
Message Passing Neural Networks (MPNN) : 메시지 전달 신경망
GNN 그래프 데이터를 처리하기 위해 설계된 대표적인 아키텍처로 메시지 전달 신경망의 구조에 대해 알아보도록 한다.
• Message Passing Neural Networks (MPNN) : 대표적으로 좋은 프레임워크이다. - A graph 𝑮 = (𝑽,𝑬) comprises ... - 𝑽 : a set of nodes (a.k.a., vertices) -. \(𝒗^𝑖 = (𝑣^{𝑖,1},…,𝑣^{𝑣_{𝑖,𝑝}}) \) - 𝑬 : a set of edges (an edge is associated with two distinct nodes) -. \(𝒆^{𝑖,𝑗} = (𝑒^{𝑖,𝑗,1},…,𝑒^{𝑖,𝑗,𝑞}) \) -. undirected vs directed : \(𝑒^{𝑖,𝑗} ＝ 𝑒^{𝑗,𝑖}\) (undirected edge) if 𝑮 is an undirected graph : \(𝑒^{𝑖,𝑗} ≠ 𝑒^{𝑗,𝑖}\) (directed edge) if 𝑮 is a directed graph
- This is a general framework of graph neural networks by abstracting the commonalities of existing variants Given a gragh 𝑮 = (𝑽,𝑬) with node vectors \(𝒗^𝑖\) ∈ 𝑽 and edge vectors \(𝒆^{𝑖,𝑗}\) ∈ 𝑬 (Phase 1: Message Passing) 노드 표현하는 벡터들을 계속 업데이트 해나가는 과정 the representation vector of each node is recursively updated by aggregating and transforming representation vectors of its neighboring nodes with the corresponding edges. -. Initial embedding (d-dim.) of each node vector with a embedding function 𝜙 \(𝒉^{(0),𝑖} = 𝜙(𝒗^𝑖), ∀𝒗^𝑖 ∈ 𝑽\) -. Update of each node vector \(𝒉^{(𝑡),𝑖}\) (𝑡 = 1,…,𝑙), * 𝑙= no. massage passing steps ↠ 각 고정된 크기의 노드를 할당하고 이웃 정보를 통해 업데이트 한다. (이웃, 이웃의 이웃, 이웃의 이웃의 이웃…) message function M and update function U 아래 예시를 보면 𝑣³ 이웃한 노드는 𝑣¹, 𝑣² ,𝑣⁴ 이므로, ⒧ \(𝒎^{(1),3}\) 메시지 함수를 사용해서 벡터를 얻고, ⑵ \(𝒉^{(1),3}\) 히든 벡터를 잘 결합하여 결과를 얻는다. (반복)
(Phase 2: Readout) 최종적인 예측을 얻는 과정 a graph-level representation is obtained by combining the representation vectors of all nodes in the graph. -. Aggregation of node vectors with a readout function : 𝑅 outputs the graph-level representation vector 𝒓 (fixed, higher dimension) : It must be invariant to permutations of the nodes in order for the MPNN to be invariant to graph isomorphism 𝒓 = 𝑅( {\(𝒉^{𝑙,𝑖}\),\(𝒉^{0,𝑖\)} | \(𝒗^𝑖\)∈𝑽} ) -. Final graph-level prediction with a function \(𝑔_𝑓\) (a neural network) ↠ 앞에서 얻은 노드 벡터들에 대하여 𝑙 번의 Message Passing 을 통해 고차원 맵핑 후 더하게 되면 순서가 중요해지지 않아 Isomorphism 문제를 해결할 수 있다. Node-Level / Edge-Level Prediction • 그래프 데이터가 주어지면 모델 구성은 다음과 같고, 비용 함수 구해서 일반적인 최적화 방법을 적용하면 된다.
• Relation to CNN : CNN 과 상당히 유사한 관계가 있다. 1) Sparse Interactions: fully connected 가 아니고 local connectivity ! (이웃된 정보만 본다) 2) Parameter sharing: Message function 과 Update function (파라미터 쉐어링) 3) Equivariance to transition: (1), (2) 로 인해 자연스럽게 얻어지는 상호 치환 동일
