[BoostCamp] DAY25 Graph#5

[BoostCamp] DAY25 Graph#5

---

1. 그래프를 이용한 기계학습

1.1 그래프 신경망 기본

그래프 신경망의 구조

• 그래프 신경망은 그래프와 정점의 속성 정보를 입력으로 받는다.
  • 그래프의 인접행렬을 A라고 할때,
  • 인접행렬은 |V| * |V|의 이진 행렬이다.
  • 각 정점u의 속성 벡터를 Xu라고 할때, 정점 속성 벡터 Xu는 m차원 벡터이고 m은 속성의 수를 말한다.
  • 정점 속성의 예
    • 온라인 소셜 네트워크에서 사용자의 지역, 성별, 연령, 프로필 사진 등
    • 논문 인용 그래프에서 논문에 사용된 키워드에 대한 원-핫 벡터
    • pagerank 등의 정점 중심성, 군집 계수등
• 그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.
  • 각 집계단계를 층(layer)라고 부르고 각 층마다 임베딩을 얻는다.
  • 각 층에서는 이웃들의 이전층 임베딩을 집계하여 새로운 임베딩을 얻는다.
  • 즉, 0번층 그러니까 입력층의 임베딩으로는 정점의 속성 벡터를 사용한다.
  • 
• 대상 정점 (임베딩을 얻고자하는 정점) 마다 집계되는 정보가 상이하다.
  • 대상 정점 별 집계되는 구조를 계산 그래프라고 부른다.
• 서로 다른 대산 정점간에도 층별 집계 함수는 공유한다.
  • 층별 집계 함수는 동일하다. *
    * 입력의 크기가 가변적이어도 처리를 할 수 있어야한다.
• 집계함수의 구조
  • 이웃들의 정보 평균을 계산
  • 신경망에 적용하는 단계
  • 
  • 

그래프 신경망의 학습

• 그래프 신경망의 학습 변수는 층별 신경망의 가중치다.
  • 
• 먼저, 손실함수를 결정하자. 정점간 거리를 보전하는 것을 목표로한다.
  • 변환식 정점 임베딩에서 처럼 그래프에서의 정점간 거리를 보존하는 것을 목표로한다.
  • 만약 인접성을 기반으로 유사도를 정의한다면 손실함수는 아래와 같다.
  • 
• 후속 과제의 손실함수를 이용한 end to end 학습도 가능하다.
  • 정점 분류가 최종 목표인 경우를 예로 들어보자.
    • 그래프 신경망을 이용하여 정점의 임베딩을 얻고
    • 이를 분류기의 입력으로 사용하여
    • 각 정점의 유형을 분류해보자.
    • 해당 경우, 분류기의 손실함수, 예를 들어 교차 엔트로피를 전체 프로세스의 손실함수로 사용하여 end to end 학습을 할 수 있다.
    • 
• 그래프 신경망과 변환적 정점 임베딩을 이용한 정점 분류
  • 그래프 신경망의 end to end 학습을 통한 분류는
  • 변환적 정점 임베딩 이후에 별도의 분류기를 학습하는 것보다 정확도가 대체로 높다.
  • 
• 그다음, 학습에 사용할 대상 정점을 결정하여 학습데이터를 구성
  • 선택한 대상 정점들에 대한 계산 그래프 구성
• 마지막으로 오차역전파를 이용하여손실함수를 최소화한다.
  • 구체적으로 오차역전파를 통해 신경망의 학습 변수들을 학습한다.

그래프 신경망의 활용

• 학습된 신경망을 적용하여, 학습에 사용되지 않은 정점의 임베딩을 얻을 수 있다.
• 마찬가지로 학습 이후에 추가된 정점의 임베딩도 얻을 수 있다.
• 학습된 신경망을 새로운 그래프에 적용할 수 있다.

1.2 그래프 신경망 변형

그래프 합성곱 신경망

• 소개한 것 이외에도 다양한 형태의 집계함수를 사용할 수 있다.
• 그래프 합성곱 신경망의 집계함수이다.
• 
  • 기존의 집계함수에서는 현재 집계가 되고 있는 이전 layer에서 임베딩을 별도의 신경망을 이용했으나,
  • GCN은 별도의 신경망을 사용하지 않고, 동일 신경망을 사용하여 연산한다.
  • 기존의 집계함수에서는 v의 연결성을 사용하지만,
  • GCN은 u와 v의 연결성의 기하 평균을 사용한다.

GraphSAGE

• GraphSAGE의 집계함수를 확인해보자.
  • 이웃들의 임베딩을 AGG함수를 이용해 합친 후, 자신의 임베딩과 연결하는 점이 독특하다.
  • 
  • 해당 AGG함수로는 다양한 함수들이 활용될 수 있다.
  • Mean, Pool, LSTM 등

1.3 합성곱 신경망과의 비교

합성곱 신경망과 그래프 신경망의 유사성

• 합성곱 신경망과 그래프 신경망은 모두 이웃의 정보를 집계하는 과정을 반복한다.
  • 구체적으로 합성곱 신경망은 이웃 픽셀의 정보를 집계하는 과정을 반복한다.

합성곱 신경망과 그래프 신경망의 차이

• 합성곱 신경망에서는 이웃의 수가 균일하지만, 그래프 신경망에서는 그렇지 않다.
  • 그래프 신경망에서는 정점별로 집계하는 이웃의 수가 다르다.
• 그래프의 인접 행렬에 합성곱 신경망을 적용하면 효과 적일까?
  • 그래프에는 합성곱 신경망이 아닌 그래프 신경망을 적용하여야한다.
  • 합성곱 신경망이 주로 쓰이는 이미지에서는 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높다.
  • 하지만 그래프의 인접 행렬에서의 인점 원소는 제한된 정보를 가진다.
  • 특히 인접 행렬의 행과 열의 순서는 임의로 결정되는 경우가 많다.

2. 그래프 신경망이란 무엇일까? (심화)

2.1 그래프 신경망에서의 어텐션

기본 그래프 신경망의 한계

• 기본 그래프 신경망 : 이웃들의 정보를 동일한 가중치로 평균을 낸다.

• 그래프 합성곱 신경망 : 단순히 연결성을 고려한 가중치로 평균을 낸다.

• 문제점 : 실생활에서 모든 이웃들과 똑같이 친한것이 아닌데 이런 것들에 대한 고려가 없다.

그래프 어텐션 신경망

• 그래프 어텐션 신경망에서는 가중치 자체도 학습한다.
  • 실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있기 때문이다.
  • 가중치를 학습하지 위해서 self-attention이 사용된다.
• 각 층에서 정점 i로부터 이웃 j로의 가중치 aij는 세 단계를 통해 계산한다.
  1. 해당 층의 정점 i의 임베딩 hi에 신경망 W를 곱해 새로운 임베딩을 얻는다.
     • 
  2. 정점 i와 정점 j의 새로운 임베딩을 연결한 후, 어텐션 계수 a를 내적한다.
     • 어텐션 계수 a는 모든 정점이 공유하는 학습 변수이다.
     • 
  3. 2의 결과에 softmax를 적용한다.
     • 
• 여러개의 어텐션을 동시에 학습한 뒤, 결과를 연결하여 사용한다.
  • 멀티헤드 어텐션이라고 부른다.
  • 

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

그래프 표현 학습

• 그래프 표현 학습, 혹은 그래프 임베딩이랑 그래프 전체를 벡터의 형태로 표현하는 것이다.
  • 개별 정점을 벡터의 형태로 표현하는 정점 표현 학습과 구분된다.
  • 그래프 임베딩은 벡터의 형태로 표현된 그래프 자체를 의미하기도 한다.
  • 그래프 임베딩은 그래프 분류등에 활용된다.
  • 그래프 형태로 표현된 화합물의 분자 구조로부터 특성을 예측하는 것이 한가지 예시이다.

그래프 풀링

• 그래프 풀링이란 정점 임베딩들로부터 그래프 임베딩을 얻는 과정이다.
  • 평균 등 단순한 방법보다 그래프의 구조를 고려한 방법을 사용할 경우
  • 그래프 분류등의 후속과제에서 더 높은 성능을 얻는 것으로 알려져 있다.
  • 
  • 위의 그림의 미분 가능한 풀링은 군집 구조를 활용하여 임베딩을 계층적으로 집계한다.

2.3 지나친 획일화 문제

지나친 획일화 문제

• 지나친 획일화 문제란 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상을 의미한다.
  • 지나친 획일화 문제는 작은 세상 효과와 관련이 있다.
  • 적은 수의 층으로도 다수의 정점에 의해 영향을 받게 된다.
• 지나친 획일화의 결과로 그래프 신경망의 층수를 늘렸을 때, 후속과제에서의 정확도가 감소하는 현상이 발견되었다.
  • 
  • 이를 해결하기 위해 잔차항을 넣는 것을 생각 할 수 있다.
  • 하지만 이러한 조치만으로는 효과가 제한적인것을 알 수 있다.

지나친 획일화 문제에 대한 대응

• 획일화 문제에 대한 대응으로 JK 네트워크는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용한다.
• APPNP는 0번째 층을 제외하고는 신경망 없이 집계함수를 단순화 하였다.
  • APPNP의 경우, 층의 수 증가에 따른 정확도 감소 효과가 없는 것을 확인할 수 있었다.
  • 

2.4 그래프 데이터 증강

그래프 데이터 증강

• 데이터 증강은 다양한 기계학습 문제에서 효과적이다.
  • 그래프에도 누락되거나 부정확한 간선이 있을 수 있고, 데이터 증강을 통해 보완할 수 있다,
  • 임의 보행을 통해 정점간 유사도를 계산하고
  • 유사도가 높은 정점 간의 간선을 추가하는 방법이 제안 되었다.

그래프 데이터 증강에 따른 효과

• 데이터 증강의 결과 정점 분류의 정확도가 개선 되는 것을 확인할 수 있다.
  • HEAT와 PPR은 데이터 증강 기법을 의미한다.
  •