Graph neural network review(2)

4. Variants considering graph type and scale

4.2 Heterogeneous graphs

Node와 edge가 다른 타입인 경우

4.2.1 Meta-path-based methods

Meta-path가 path에 있는 각 노드의 type을 결정, 학습 과정에서 meta path는 node의 sequence로 이용. 

직접적으로 연결되어있지 않더라도 두 노드간의 유사도를 구할 수 있음.

∴ One heterogeneous graph → Several homogeneous graph

 

HAN - Hierarchical Attention Network : Meta-path-based neighbors를 이용하여 graph attention을 적용하고 최종 representation을 위해 output embedding에서 semantic attention을 이용

 

GTN - Graph transformer network : Transformer를 이용하여 연결되지 않은 노드들 간의 관계도 학습, 학습된 새로운 관계는 meta-path의 역할을 함.

[Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs, Yun et al. (2019, NIPS)]

 

4.2.2 Edge-based methods

Meta path를 사용하지 않고 다른 종류의 node와 edge에 따라서 다른 sampling, aggregation function을 사용하는 방식

 

4.2.3 Methods for relational graphs

Type 보다 edge에 대한 정보가 더 중요한 경우 또는 type이 너무 많을 경우 관계가 더 중요하다. 이와 관련한 그래프를 relational graph라고 부른다.

 

R-GCN - 원래 그래프의 형태를 바꾸지 않고 다른 종류의 edge에 대해서 다른 weight matrix를 사용.

그러나 relation이 너무 크면 파라미터가 너무 많아지므로 2가지 방법의 regularization을 도입.

1. Basis
2. Block-diagonal-decomposition

위 식 - Basis decomposition, 아래 식 - Block decomposition

The basis function decomposition can be seen as a form of effective weight sharing between different relation types, while the block decomposition can be seen as a sparsity constraint on the weight matrices for each relation type.(논문 인용)

[Modeling Relational Data with Graph Convolutional Networks, Schlichtkrull et al. (2018, ESWC)]

 

4.3 Dynamic graphs

Edge나 node의 존재가 시간에 따라 변화하는 그래프

Structural-RNN, ST-GCN은 spatial과 temporal message를 함께 고려. Static graph를 temporal connection을 통해서 연장시키고 이 그래프를 가지고 전통적인 GNN 적용

[Structural-RNN: Deep Learning on Spatio-Temporal Graphs, Jain et al. (2016, CVPR)]

EvolveGCN - Node representation의 변화를 모델링하는 것은 성능에 방해가 됨 → Node feature를 RNN의 input으로 하는 대신 interaction을 포착하기 위해 GCN의 가중치를 RNN의 input으로 설정 → Capture intrinsic dynamics

[EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs, Pareja et al. (2020, AAAI)]

 

4.5 Large graphs

Pagerank [Predict then Propagate: Graph Neural Networks meet Personalized PageRank, Klicpera et al. (2019, ICLR)]

 

5. Variants for different training settings

학습을 어떻게 시킬 것인지에 대한 내용. Label이 있는 경우는 loss function을 label을 이용해 설계하면 되기 때문에 편리하지만 Label이 없는 경우는 input feature나 graph topology와 같은 그래프 자체로부터 얻는 정보들을 이용해 loss function을 설계해야함. 이는 Auto-encoder나 contrastive learning과 관련

 

5.1 Graph auto-encoders

GAE - Graph Auto encoder : Node를 encode하기 위해서 GCN을 사용함. Encoding된 node의 representation을 가지고 decoder를 이용해 adjacency matrix를 복원 → 원래 adjacency matrix와의 유사도를 기반으로한 loss function설계

[Variational Graph Auto-Encoders, Kipf and Welling et al. (2016, NIPS)]

 

이 외에도 GAN을 도입한 ARGA, Adjacency matrix를 복원하는 것 대신에 feature matrix를 복원하는 MGAE, GALA, Node 유사도 측정을 위해 adaptive learning(단순히 복원하는 것이 아닌 목적에 따른 학습)을 도입한 AGE등이 있다.

 

5.2 Contrastive learning

Auto encoder와는 다른 방식의 unsupervised learning.

 

DGI - Deep graph infomax : 노드와 그래프의 representation간의 mutual infomation을 최대화하는 방식

 

Infograph - 그래프의 representation과 node, edge와 같은 하위 구조의 representation간 Mutual information의 최대화하는 방식으로 graph의 representation을 학습하는 것이 목적. 

[InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization, Sun et al. (2020, ICLR)]

 

7. Analyses of GNNs

7.1 Theoretical aspect

7.1.1 Graph signal processing

GNN에서의 Graph convolution은 가까운 node의 hidden representation을 비슷하게 만드는 feature matrix를 생성 → Laplacian smoothing

신호 관점에서 비슷한 시간의 신호나 거리가 가까운 pixel값들은 일반적으로 높은 연관관계가 있음. 사회적 관계를 나타낸 그래프에서도 이웃한 노드끼리 비슷한 특성을 가지고 있을 것

비슷한 위치에서의 노드가 비슷하기 때문에 Laplacian matrix는 입력 특성에 대해서 low-pass filter의 역할을 한다.

 

다른 관점 - x를 그래프 신호라고 할 때, Lx 연산은 인접 노드에 대한 노드의 신호값의 가중된 차이를 유지한다. 따라서 그래프에서 정의된 신호 x에 대해 high pass operator의 역할을 한다. 

출처 : https://digitalassets.lib.berkeley.edu/techreports/ucb/text/EECS-2013-209.pdf

 

Graph convolution은 입력 특성에 대한 denoising process를 수행하며 모델의 성능이 feature matrix에 존재하는 noise의 정도에 따라 크게 달라진다. Over-smoothing의 중요한 요소는 information-to-noise의 비율이다.

 

7.1.2 Generalization

GNN의 안정성은 filter의 가장 큰 eigenvalue에 의존한다는 연구가 있었음.

Attention 기법이 크고 noisy한 그래프의 generalization에 도움이 되었다.

 

7.1.3 Expressivity

그래프 isomorphism testing 알고리즘인 Weisfeiler-Leman(WL) test보다 GCN, GraphSAGE의 표현력이 떨어짐 → GIN - [How Powerful are Graph Neural Networks?, Xu et al. (2020, ICLR)]

기존에는 Layer와 Unit을 고려한 GNN의 expressivity에 대한 연구도 진행되었음.

GNN 모델이 깊어짐에 따른 변화에 대한 연구 [GRAPH NEURAL NETWORKS EXPONENTIALLY LOSE EXPRESSIVE POWER FOR NODE CLASSIFICATION, Oono et al. (2020, ICLR)]

 

7.1.4 Invariance

일반적인 경우 Graph에는 node의 순서가 없기 때문에 GNN은 permutation invariant 해야하며 input feature에 따라 equivariant 해야한다. 

 

이 외에도 transferability, Label efficiency, Empirical aspect에 대한 분석이 존재

9 -10. Problem and conclusion

Graph 모델이 해결해야할 문제들

1. Robustness - Noise에 취약, 새로운 구조의 정보에 대해 어떻게 할 것인가?
2. Interpretability - Black box
3. Pre-training - NLP분야의 BERT처럼 pre-train → fine tuning의 과정이 확립되어 있지 않음.
4. Complex Graph Structure - Dynamic이나 heterogeneous와 같은 복잡한 graph 구조에 대한 방법론

 

읽어볼만한 논문 정리

[Geometric deep learning, Bronstein et al.(2017, ieee SPM)]

[A Survey on Network Embedding, Cui et al(2018, ieee TKDE)]

[Deep learning on Graphs : A Survey, Zhang et al.(2018, ieee TKDE)]

[Semi-Supervised Classification with Graph Convolutional Networks, Kipf et al. (2017, ICLR)]

[Graph Wavelet Neural Network, Xu et al.(2019, ICLR)]

[Inductive Representation Learning on Large Graphs, Hamilton et al. (2017, NIPS)]

[Graph Attention Networks, Velickovic et al. (2018, ICLR)]

[Geometric deep learning on graphs and manifolds using mixture model CNNs, Monti et al. (2017, CVPR)]

[Neural Message Passing for Quantum Chemistry, Gilmer et al. (2017, ICML)]

[Interaction Networks for Learning about Objects, Relations and Physics, Battaglia et al. (2017, NIPS)]

[A simple neural network module for relational reasoning, Santoro et al. (2017, NIPS)]

[Gated Graph Sequence Neural Networks, Li et al. (2016, ICLR)]

[Representation Learning on Graphs with Jumping Knowledge Networks, Xu et al. (2018, ICML)]

[FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling, Chen et al. (2018, ICLR)]

[Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks, Zou et al. (2019, NIPS)]

[GraphSAINT: Graph Sampling Based Inductive Learning Method, Zeng et al. (2020, ICLR)]

[Hierarchical Graph Representation Learning with Differentiable Pooling, Ying et al. (2017, NIPS)]

[Self-Attention Graph Pooling, Lee et al. (2019, ICML)]

[Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs, Yun et al. (2019, NIPS)]

[Modeling Relational Data with Graph Convolutional Networks, Schlichtkrull et al. (2018, ESWC)]

[Structural-RNN: Deep Learning on Spatio-Temporal Graphs, Jain et al. (2016, CVPR)]

[EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs, Pareja et al. (2020, AAAI)]

[Predict then Propagate: Graph Neural Networks meet Personalized PageRank, Klicpera et al. (2019, ICLR)]

[Variational Graph Auto-Encoders, Kipf and Welling et al. (2016, NIPS)]

[InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization, Sun et al. (2020, ICLR)]

[How Powerful are Graph Neural Networks?, Xu et al. (2020, ICLR)]

[GRAPH NEURAL NETWORKS EXPONENTIALLY LOSE EXPRESSIVE POWER FOR NODE CLASSIFICATION, Oono et al. (2020, ICLR)]