Peer Session Badge

그래프 신경망

  • 귀납식 정점 표현 학습

    • 정점 표현 학습
      • 정점 임베딩(node embedding)
      • 그래프의 정점들을 벡터의 형태로 표현
      • 그래프에서의 정점간 유사도를 임베딩 공간에서도 보존
    • 귀납식정점 표현 학습
      • 학습의 결과로 정점 임베딩 자체를 얻는 변환식(transductive) 방법들과 대조됨

      • 학습의 결과로 인코더, 즉 정점을 임베딩으로 변화시키는 함수를 얻음

        $ENC(v) = Z_v$

        • $ENC(v)$: 그래프 구조와 정점의 부가 정보를 활용하는 복잡한 함수
      • 장점
        • 학습 후 새로 추가된 정점에 대해서도 임베딩 얻을 수 있음
        • 모든 정점에 대한 임베딩을 미리 계산해 저장할 필요 x
        • 정점이 속성(attribute) 정보를 가진 경우 활용 가능

  • 그래프 신경망의 구조

    • 입력
      • 그래프
        • 인접 행렬 $A$: $\vert V \vert \times \vert V \vert$
      • 정점의 속성 정보
        • 각 정점 $u$의 속성 벡터 $X_u$: m차원 (속성의 수)
        • ex. sns 사용자의 지역, 성별, 연령, 사진; PageRank 등에서 정점 중심성, 군집 계수
    • 과정
      • 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻음
      • 각 집계 단계를 층(layer)이라고 함
      • 입력 층의 임베딩: 정점의 속성 벡터
      • 각 층의 임베딩: 이웃들의 이전 층 임베딩 집계하여 얻음
      • 계산 그래프(computational graph)
        • 대상 정점 마다 집계되는 정보 상이
        • 대상 정점 별 집계되는 구조
        • 층 별 집계 함수는 동일 (공유함)
    • 집계 함수

      • 이웃들 정보의 평균을 계산 후 신경망에 적용

        $h_v^0 = X_v$ (0번 층에서 정점 $v$의 임베딩을 $v$의 속성 벡터로 초기화)

        $h_v^k = \sigma \Big( W_k \sum_{u \in N(v)} \frac{h_u^{k-1}}{\vert N(v) \vert} + B_k h_v^{k-1} \Big), \forall k > 0$

        $z_v = h_v^k$ (마지막 층에서의 임베딩 = 출력 임베딩)

        • $h_v^k$: $k$ 층에서 $v$의 임베딩
        • $\sum_{u \in N(v)} \frac{h_u^{k-1}}{\vert N(v) \vert}$: 이전 층에서 이웃들의 임베딩에 대한 평균 계산
        • $h_v^{k-1}$: 이전 층에서 $v$의 임베딩
    • 학습
      • 학습 변수(trainable parameter)
        • 층 별 신경망의 가중치
        • $W_k, B_k$
      • 손실함수

        • 정점간 거리를 보존하는 것을 목표로 함

          $L = \sum_{(u,v) \in V \times V} \Vert z_u^T z_v - A_{u,v} \Vert^2$

      • End-to-End 학습도 가능
        • 후속 과제(downstream task)의 손실함수를 이용 (ex. Cross Entropy)
        • “변환적 정점 임베딩 + 별도의 분류기 학습”보다 대체로 높은 정확도 얻을 수 있음

그래프 신경망 변형

  • 그래프 합성곱 신경망(GCN)

    • 집계 함수

      $h_v^k = \sigma \Big( W_k \sum_{u \in N(v) \cup v} \frac{h_u^{k-1}}{\sqrt{\vert N(u) \vert \vert N(v) \vert}} \Big), \forall k \in { 1, \dots, K }$

    • 이웃 픽셀의 정보를 집계하는 과정을 반복
    • 이웃의 수가 균일
    • 인접 행렬의 경우 행과 열의 순서가 임의로 결정되는 경우가 많기 때문에, 합성곱 신경망이 아닌 그래프 신경망이 적합함

  • GraphSAGE

    • 집계 함수

      $h_v^k = \sigma \big( [ W_k \cdot AGG ( { h_u^{k-1}, \forall u \in N(v) }), B_k h_v^{k-1} ] \big)$

    • 이웃들의 임베딩을 AGG 함수를 이용해 합친 후, 자신의 임베딩과 연결(concatenation)
    • AGG(Aggregation)
      • mean
      • pool
      • LSTM

그래프 신경망에서의 Attention

  • Graph Attention Network (GAT)

    • 기본 그래프 신경망의 한계
      • 이웃들의 정보를 동일한 가중치로 평균을 냄
      • GCN 역시 단순히 연결성만 고려한 가중치로 평균을 냄
    • GAT

      • Self-attention을 사용해 가중치 자체도 학습함

        1. 해당 층의 정점 $i$의 임베딩 $h_i$에 신경망 $W$를 곱해 새로운 임베딩 얻음

          $\tilde{h_i} = h_i W$

        2. 정점 $i$와 정점 $j$의 새로운 임베딩을 연결한 후, 어텐션 계수 $a$(모든 정점이 공유하는 학습 변수)를 내적함

          $e_{ij} = a^T [ \text{concat}(\tilde{h_i},\tilde{h_j}) ]$

        3. 소프트맥스 적용

          $\alpha_{ij} = \text{softmax}j (e{ij}) = \frac{exp(e_{ij})}{\sum_{k \in N_i} exp(e_{ik})}$

    • Multi-head attention

      • 여러 개의 어텐션을 동시에 학습 후 연결해 사용

        $h’i = \text{concat}{i \le k \le K} \sigma \big( \sum_{j \in N_i} \alpha_{ij}^k h_j W_k \big)$

  • 그래프 표현 학습과 그래프 풀링

    • 그래프 표현 학습
      • 그래프 임베딩
      • 그래프 전체를 벡터의 형태로 표현하는 것
      • $\ne$ 정점 표현 학습(개별 정점 $\rightarrow$ 벡터)
    • 그래프 풀링(pooling)
      • 정점 임베딩들로부터 그래프 임베딩을 얻는 과정
      • DiffPool(Differentiable Pooling) 등 그래프 구조를 고려한 방법이 높은 성능을 냄

  • Over-smoothing 문제

    • 지나친 획일화(over-smoothing)
      • 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상
      • 작은 세상 효과와 관련이 있음
      • 후속 과제에서의 정확도 역시 감소함
      • 잔차항(residual)을 넣을 수도 있지만, 이전 층 임베딩을 한 번 더해주는 것만으로는 효과가 제한적임
    • 대응
      • JK 네트워크(Jumping Knowledge Network)
        • 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용
      • APPNP
        • 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화

  • 그래프 데이터 증강

    • Data augmentation
      • 누락되거나 부정확한 간선이 있을 수 있고, 데이터 증강으로 보완 가능
      • 임의 보행을 통해 정점간 유사도를 계산하고, 유사도가 높은 정점 간의 간선을 추가하는 방법 제안됨