• CS224W의 8주차 강의, Graph Neural Networks를 보고 정리한 글입니다.
  1. Graph Neural Networks
  2. Basics of Deep Learning for Graphs
  3. Graph Convolutional Networks and GraphSAGE
  4. Graph Attention Networks
  5. Example Application

---

Graph Neural Networks

• Node Embedding

  • Intuition

    ‘Input graph를 d-dimension의 embedding space로 mapping 시켰을 때, Original Network 상에서의 Similar한 두 노드들이, embedding space에서 가까이에 위치했으면 좋겠다.’

  • 목표

    ‘Embedding Space’에서의 similarity가 ‘Original Network’에서의 similarity를 잘 근사했으면 좋겠다!

    • 이 때 이 ‘similarity’라는 것에 대해 정의해야 할 필요성이 생김
      
  • Node Embedding의 두 가지 Components
    1. Encoder: Node를 Low-dimensinal vector로 Mapping
       
       • Chap7에서는 Shallow Encoder에 집중했음. (Using Embedding Lookup)
         
       • 하지만 Shallow Encoder에는 몇 가지 문제점이 존재

       ---

       1. 추정해야할 Parameter의 수 = 노드의 개수
       2. 학습한 적이 없는 네트워크에 대해서는 모든 것을 다시 re-embed 해야.
       3. Node features를 고려하지 않는다.
          —

    • Chap8: Deep Encoder에 대한 소개가 될 것.
      

      • 이 Deep Encoder는 어떤 node similarity function과도 결합될 수 있다.
      • 아래의 Deep Graph Encoders라는 제목 하에 계속 이어서 서술!
    1. Similarity Function: Input Network에서의 relationship이 어떻게 embedding space에서의 relationship으로 mapping 되는지에 대해 정의
       

Deep Graph Encoders

• 아래의 그림처럼 그래프를 받고, Deep NN으로 보내서, 결국에는 어떤 Prediction task에 대해 사용할 수 있는 node embedding을 얻어내면 참 좋을텐데, 사실 이 과정은 굉장히 어려움
  
• 왜냐하면, 현재 존재하는 ML/DL Toolbox는 simple data types에 특화되어 있기 때문에. (ex. 이미지, 텍스트)
• 하지만 Graph는 Not simple
  • 사이즈도 뒤죽박죽, 위상학적인 구조도 매우 복잡 (grid와 같은 어떤 공간적인 locality도 존재하지 않음.)
  • 노드들 간의 순서라든지, reference point가 존재하지 않음.

  • 종종 dynamic & multomodal feature들을 가지기도.

  • 그래프는, 여타 다른 데이터들과 성격자체가 다르다고 할 수 있겠다.

  • Graph를 Represent하기 위한 한 가지 Naive한 방법은, Adjacency matrix와 features를 함께 Join해서 이를 NN의 input으로 넣는 것.
    

  • 그다지 좋은 idea는 아님
    • Parameter의 수가 많다.
      • 이 경우, 이미 첫번째 layer에서 Node의 개수인 5개보다 많은, 7개의 parameter를 사용 -> network를 깊게 만들수록 결과는 더 나빠질 것
    • 다른 size의 그래프에는 not applicable
      • 노드 6개짜리 graph에서는 working하지 x
    • Node의 순서에 invariant하지 않다.
      • 예를 들어, A B C D E 순서로 adjacency matrix를 정리했을 때와, D C A B E 로 adjacency matrix를 정리했을 때 이는 network 상에서의 input이 달라지는 것이고, 얻게될 결과도 달라진다.

---

Basics of Deep Learning for Graphs

• 갖고 있는 정보에 대한 가정
  • V: Vertex set
  • A: Adjacency Matrix
  • X: Node features
    

Graph Convolutional Networks

• 어떤 node가 주어지면, 그 노드에 대한 prediction을 진행하고 싶을 때,
  1. 먼저, 무엇이 Computational graph가 되어야할지를 결정하고
  2. (prediction task를 위해) 이 computational graph를 사용해서 neighbors 혹은 neighbors의 neighbors들로부터 Propagate & Aggregate Info!
  • 오, 여기서 ‘Neighors를 Aggregate한다는 것이 무엇이지?’

Aggregate Neighbors

• Key Idea: Local Network Neighborhoods에 근거해서 node embedding을 generate하겠다.
  
  • 단 Graph 도메인에서는 4,5 Layer 이상으로 잘 가지 않는다
    ∵ MSN 예시에서 보았듯, 그래프 Domain에서는 Depth 6 정도면 그래프 내의 거의 모든 노드들을 방문할 수 있음.
    (이런 의미에서 그래프 도메인에서는, Computer Vision에서 Layer를 깊게 쌓는 것과, Depth에 대한 관점 차이가 확연)
• Intuition1
  • 노드들은 주변 neighbor들로부터 NN을 사용하여 정보를 aggregate한다.
    (단, 이 aggregation은 order invariant할 것)
    
• Intuition2
  • Network neighborhood들이 computation graph를 정의한다.
    (모든 노드들은 자기 자신의 NN 아키텍쳐를 갖고 있으며, 각자의 neighborhood에 근거하여 computation graph를 정의)
    
• 모델은 어떤 Depth를 가져도 상관 없음. (Layers 수 ↑ → Deep model)
  

Neighboor Aggregation

• 도대체 네모박스에는 어떤 것이 들어있을까?
• Basic Approach:
  1. Neighbors로 부터의 message를 average
     (이론적으로는 Summation이 가장 Powerful하기는 하며, 합이든 평균이든 둘 다 Order Invariant)
  2. NN 적용
     
• 수식적인 이해
  

Training the Model

• 위 모델을 어떻게 훈련할 것인가?

  • 위의 수식에서, 결국 Train의 대상은 Weight Matrix W, B!! (Trainable weight matrices)
    

    • W=0 : Neighbor의 정보를 이용하지 않고 학습하겠다는 것
    • W↑: 해당 노드가 가진 Features를 무시하는 정도를 높이겠다는 것
      => 결국, 이 둘을 어떻게 잘 조합할 것인지가 문제가 되겠다!

  • 이 수식을 다음과 같이 Recursive하게 적어볼 수도 있겠다.
    

  • 지도, 비지도학습 둘 다 학습 가능

  -> 이를 훈련하기 위해서는 Embedding에 대한 Loss Function이 필요함

  • 이 Embedding들을 어떤 Loss Function에도 투입가능하며, 궁극적으로는 Weight parameter를 훈련하기 위해 SGD를 사용할 것
  • 여기서는 Binary Classification 상황을 가정하고, Cross Entropy Loss Function을 씀. (Toxic? Safe?)
    

Model Design

• Process

  1. Neighborhood Aggregation function 정의  
  2. Embedding에 대한 Loss Funciton 정의  
  3. Node set들을 학습 (A batch of compute graphs)
  4. 필요한대로 노드에 대한 embedding들을 generate  
  

  • 본적이 없는 그래프에도 훈련된 모델을 적용하는 것이 가능하다.

    이는 해당 아키텍쳐가 Parameter를 Sharing하기 때문!

  
  
  

• Parameter Sharing
  

---

Graph Convolutional Networks and GraphSAGE

• 앞에서, Neighbor들의 message를 평균냄으로써 aggregated.
  -> 이보다 더 잘할 수 없을까? 에 대한 의문

• 다음과 같은 Message Passing 수식을 고안
  

  • (앞에서의) 단순한 Neighborhood Aggregation와 GraphSAGE의 Aggregation차이!
    

    • 이 때, AGG function도 다양한 형태로 활용 가능
      ex) Mean, Pool, LSTM
      

      • cf. 한 가지 발견 중의 하나는 LSTM도 Random Ordering으로 학습을 하면 order invariant하게 만들 수도 있다는 것

• GCN, GraphSAGE에 대한 Recap
  

---

Graph Attention Networks

• Simple neighborhood aggregation을 다시 한 번 언급하며 시작
  
  • 기존의 GCN은 각 Layer에서의 노드의 개수에 따라, Take avering. (모든 노드들의 가중치가 같았음)
  • 즉 Weighting factor는 그냥, 외부에서 아키텍쳐를 보면 알 수 있는 굉장히 명시적인(Explicit) 형태!
  • 모든 노드들이 동등하게 중요! (과연 그럴까..?)
• (위의) Simple Neighborhood Aggregation 보다 더 잘할 순 없을까?

• Weight α_vu를 좀 더 implicit하게 정의할 수는 없을까?

  -> Graph Attention Network 도입!

Graph Attention Network

• 목표: 그래프 상 각 노드의 neighbor들에 Arbitrary Importances 구체화

• 아이디어: Attention strategy 에 따라 각 노드의 embedding() 계산

• 매커니즘
  • 는 attention mechanism a 의 Byproduct로서 계산!

  ---

  1. a로 하여금 Attention coefficients 를 계산하게 함
     
     (: node u가 node v에게 전송하는 메시지의 중요성)

  2. Neighborhoods들 간의 비교를 가능하기 위해 Softmax 적용
     
     —

  • 아, 그럼 a 는 어떤 형태? (어떻게 학습하지?)

    Multi-head attention
    (특정 레이어의 Attention 연산은 R번 독립적으로 연산됨)

• Attention 매커니즘 사용의 이점
  • Main: 다른 neighbor들에 다른 Importance value를 구체화
  • 연산의 효율성
  • 저장공간의 효율성
  • Localized!
  • Inductive!
• 논문 Citation Network를 통해 효용성을 알 수 있음
  

---

Example Application

• Pinterest

  Graph를 이용해서 더 나은 Recommendation을 도출한 모델!

  • 예를 들어,
    
    을 두고, Computer Vision은 (인간의 눈에서 너무나 명백해 보이는데도) 이 둘을 잘 구분하지 못하는 Silly Mistakes를 저지름
    하지만 Bipartite graph를 사용해서, node로 부터 information을 빌려오고, 이를 잘 활용하면 성능 훨씬 좋아지더라!

  • 결과 일례
    

---

References

CS224W: Graph Neural Networks