그래프와 추천시스템 7910

정점 표현

정점표현학습
그래프의 정점을 벡터 형태로 표현. Node Embdding이라고도 함
$f: V \to \mathbb{R}^{d}$
그래프를 벡터 형태로 표현해야, 다양한 기계학습 기술들을 적용할 수 있다.
그래프의 정점간 유사도를 임베딩 공간에서도 정점 임베딩 값들간의 유사도가 보존되도록 하는 것이 목표이다.
임베딩 공간에서의 유사도는 내적(Inner Product)를 사용할 수 있다.
그래프에서 정점의 유사도는 인접서어, 거리/경로/중첩, 임의보행, 등으로 설정할 수 있다.

인접성 기반 접근법
인접행렬의 원소 $A_{u,v}$ 를 두 정점 u v의 유사도로 가정 (0 or 1)
- 인접성 기반의 node embedding 모형의 손실함수

인접성 기반 접근법의 한계
위와 같은 그래프에서 빨강-파랑, 초록-파랑의 경우 거리가 다름에도 불구하고 손실함수에서는 거리의 차이를 반영하지 않음(인접행렬에서의 유사도는 모두 0임)
군집의 측면에서 파랑-초록 정점음 같은 군집으로 볼 수 있지만, 인접행렬의 유사도는 0임

거리 기반 접근법
두 정점사이의 거리가 충분히 가까운 경우 유사하다고 간주
Ex. 충분히의 기준이 2인 경우: 2 이내의 거리의 정점 유사도를 1, 3이상의 거리의 정점 유사도를 0으로 설정

경로 기반 접근법
u, v의 경로: u에서 시작해 v에서 끝나야함. 순열에서 연속된 정점은 간선으로 연결되어있어야 함.
두 정점 사이의 경로가 많을 수록 유사하다고 간주
두 정점 u와 v의 경로중 거리가 k인 것의 수는 인접행렬 A의 k제곱의 u행 v열 원소와 같다

중첩 기반 접근법
두 정점이 많은 이웃을 공유할 수록 유사하다고 간주
아래 그림에서 빨강과 파랑의 정점의 중첩기반 유사도는 2
- 중첩행렬과 손실함수
- 중첩행렬 구성
  자카드 유사도로 중첩행렬 구성 가능. 이 때, u v는 [0,1]의 값을 갖게 됨
  아다믹 아다는 유명 연예인의 트위터계정을 동시에 팔로우 하고 있는 두 사람 u, v의 거리가 실제로 가깝지 않을 수 있음을 반영하여, 연결성을 고려한 유사도와 중첩행렬을 구성한 것임.

임의 보행 기반 접근법
한 정점에서 시작해 임의보행을 할 때, 다른 정점에 도달할 확률을 유사도로 간주
임의 보행을 사용하는 경우 시장 정점 주변의 지역적 정보와 그래프 전역 정보를 모두 고려한다는 장점이 있음. 거리기반의 접근법과 달리 거리의 기준을 정하지 않아 그래프 전역 정보를 고려한다 할 수 있음.
- 과정
  정점 u에서 시작하여 v에 도달할 확률을 임베딩 벡터로 표현
  → v와 u의 임베딩 내적값이 클수록 (유사도가 클 수록) 확률이 높다.
- 임의 보행의 방법
  임의 보행의 방법에 따라 DeepWalk와 Node2Vec으로 구분됨
  - DeepWalk [https://arxiv.org/pdf/1403.6652.pdf]
    기본적인 임의보행을 사용. 현재 정점의 이웃 중 하나를 균일한 확률로 선택하는 이동 과정을 반복
  - Node2Vec [https://arxiv.org/pdf/1607.00653.pdf]
    Second-order Biased Random Walk를 사용.
    u → v로 간 뒤에, a,b,c의 방향으로 볼 수 있다. 이 때마다 각각 다른 확률을 사용자가 줄 수 있다.
    node2vec임베딩 이후 k-means를 수행 결과
    멀어지는 방향에 높은 확률을 부여한 경우: 다리 역할/변두리/군집을 형성하는 정점 등으로 군집이 형성되는 것을 확인할 수 있다.
    가까워지는 방향에 높은 확률을 부여한 경우: 같은 군집에 속하는 경우 임베딩이 유사하게 된다.
  - 손실함수근사
    임의보행기법의 손실함수는 계산이 정점의 수에 제곱에 비례하는 시간이 소요됨
    모든 정점에 대해 정규화 대신에 몇 개의 정점을 뽑아 비교한다. 이때 뽑힌 정점을 Negative Sample이라 함. Negative sample은 연결성에 비례하는 확률로 뽑으며, Negative sample이 많을 수록 안정적인 학습을 한다.

변환식 정점 표현 학습과 귀납식 정점 표현 학습
- 변환식 방법(Transductive)
  학습의 결과로 정점의 임베딩 자체를 얻음. 지금까지 배운 방법들은 모두 변환식 방법이다.
  - 단점
    학습 진행 이우 정점에 대해 임베딩을 얻을 수 없음
    모든 정점에 대한 임베딩을 미리 계산해 저장해야 함
    정점이 속성정보를 가진 경우에 활용하기 어려움
- 귀납식 방법(Inductive)
  정점을 인베딩으로 변화시키는 함수인 인코더를 얻음
  ex. GNN

GNN

그래프 신경망
- 입력: 그래프(인접행렬)와 정점의 속성 정보
- 그래프의 속성 정보:
  u의 속성 벡터: $X_{u}$ m차원 벡터로 m은 속성의 수
  정점 속성은 데이터로 얻을 수 있고 그래프로부터 만들 수도 있음
  ex. SNS의 데모그라픽 정보, 논문 인용 그래프에서 키워드의 원핫벡터, 페이지 랭크 값 등
- 과정
  이웃 정점들의 정보를 집계하는 과정을 반복해 임베딩을 얻는다
  대상 정점의 임베딩을 얻기 위해 이웃들과 이웃들의 정보를 집계함
  각 집계 단계를 층(Layer)라고 부르고 각 층마다 임베딩을 얻는다
  0번층(입력)의 임베딩으로는 정점 속성벡터를 사용한다. 1번층은 0번층의 임베딩을 사용해서 그림에서 B, C, D의 임베딩 값을 얻은 뒤에, 1번층의 임베딩을 통해 대상정점의 표현을 얻는다.
  대상 정점마다 집계되는 정보는 아래와 같이 다른 것을 알 수 있다. 대상정점 별로 집계되는 구조를 계산그래프(computation graph)라 한다.
  서로 다른 대상 정점간에도, 층별 집계함수는 공유한다
  집계함수는 이웃들의 수가 달라도, 적용가능해야 하기 때문에 이웃 정보를 평균을 계산하고, 신경망에 적용하는 2가지 단계를 거친다. 평균을 통해 동일한 차원으로 만들어준다. 학습하는 파라미터는 아래 식에서 W와 B임을 알 수 있다.
  - 손실함수
    유사도를 인접성으로 정의하면 손실함수는 아래와 같고, 다른 유사도로 정의할 수도 있음
    Downstream task(후속과제)에 따라 End-to-end 학습도 가능하다
    정점분류, 군집화 등의 downstream task를 정의할 수 있음
    ex. 정점분류
  - 결과 비교
  - 학습 이후에 추가된 정점 임베딩이나, 학습에 사용하지 않은 정점의 임베딩도 얻을 수 있음. 또한 학습된 그래프 신경망을 새로운 그래프의 임베딩도 얻을 수 있음.

변형
평균 이후 신경망에 적용하는 것 이외에 다양한 집계함수를 사용할 수 있다.
- GCN
  이전 신경망(이웃 임베딩)의 출력인 $h_{v}^{k-1}$ 을 별도의 신경망이 아닌 동일한 신경망을 사용한다
  정규화 방안을 u와 v의 연결성의 기하평균을 사용
- GraphSAGE
  이웃의 임베딩은 AGG함수를 이용하고, 이전의 임베딩을 concat한다.
  lstm에서 파이는 이웃의 임베딩을 가져와 순서를 섞는 것을 의미한다.
- CNN과 GCN 비교
  합성곱 신경망은 이웃 픽셀의 정보를 집계하는 과정을 반복.
  합성곱 신경망에서는 이웃의 수 가 균일하지만, 그래프 신경망에서는 아니다.
  그래프 신경망에서는 정점 별로 집계하는 이웃의 수가 다르다.
  그래프의 인접행렬에 합성공 신경망을 적용하면 효과적인가?
  아니다. 그래프 인접행렬에서의 인접원소의 순서는 임의로 결정되고, 제한된 정보를 갖는다.

기존 그래프 신경망의 한계
GNN, GCN 등은 단순히 연결성을 고려한 가중치로 평균을 낸다.
이웃 별로 미치는 영향이 다를 수 있기 때문에 이러한 가중치를 학습하기 위해 Self Attention을 사용한다.

GAT (Graph Attention Network)
- 정점 i에서 이웃 j로의 가중치 $\alpha_{ij}$ 는 3단계를 통해 계산한다.
  W와 a벡터는 학습 파라미터이다.
- Multi-Head Attention
  여러 개의 attention을 동시에 학습한뒤 결과를 concat해 사용할 수 있다.
- GAT 결과

그래프 표현학습
그래프 전체를 벡터의 형태로 표현
그래프 임베딩은 벡터의 형태로 표현된 그래프 자체를 의미
그래프 임베딩은 그래프 분류 등에 활용
ex. 그래프 형태로 표현된 화합물의 분자 구조로부터 특성을 예측
- 그래프 풀링(graph pooling)
  정점 임베딩으로 부터 그래프 임베딩을 얻는 과정
  그래프의 구조를 고려한 방법을 사용할 경우 그래프 분류 등의 후속 과제에서 더 높은 성능을 얻는 것으로 알려져 있음
  - DiffPool
    군집 구조를 활용해 임베딩을 계층적으로 집계
    정점 임베딩으로부터 군집을 만들고, 해당 군집을 통해 군집의 군집을 만들고 최종적으로 그래프 임베딩 값을 얻은 뒤에 분류기에 넣는다. 노드임베딩 군집의 군집 등에는 GNN이 사용된다.

지나친 획일화 문제 (Over Smoothing)
위 그림처럼, GNN의 층이 깊어짐에 따라 정점 임베딩이 서로 유사해지는 현상
over smoothing은 작은 세상 효과와 관련이 있다. 5-layer정도가 되면 지역적인 정보뿐만 아니라 그래프 전반의 정보를 사용하게 되어 표현이 비슷해짐. → 분류 등의성능이 떨어짐
- JK Network(Jumping Knowledge Network) & APPNP
  JKNet에서는 모든 층의 임베딩을 함께 사용
  APPNP에서는 0번째 층을 제외하고는 신경망을 구성하지 않아 집계함수를 단순화. (W를 0번째 층만 사용)
  APPNP의 경우 layer 수의 증가에 따른 정확도 감소가 없었다.