13. Graph Transformer Part2 CS224W: Machine Learning with Graphs 정리

 

https://web.stanford.edu/class/cs224w

목차

1. Part1

-  Transformer 소개
-  메시지 패싱 GNN과의 관계

2. Part2

-  Transformer GNN을 위한 새로운 디자인

 

 

 

 

👉 1. Part2

-  Transformer GNN을 위한 새로운 디자인

기존 GNN과 다르게 Graph Transformer를 위한 디자인 공간은 어떻게 설계를 해야할까?

 

Transformer로 그래프를 처리하는 방법을 이해하려면 Part1에서 본 Transformer의 주요 구성 요소를 이해한다.

1. 토큰화(Tokenizing): 입력 데이터의 각 부분을 벡터로 변환한다.
2. 자기 주목(Self-attention): 입력 시퀀스의 각 부분이 다른 부분에 얼마나 집중해야 하는지 결정한다.
3. 위치 인코딩(Positional Encoding): 시퀀스의 순서를 모델에 알려주는 역할을 한다.

Graph Transformer는 노드 특징, 인접 정보, 엣지 특징을 입력으로 받아야 하며 이를 통해 변환기가 그래프 구조를 이해할 수 있다.

 

 

Graph Input과 Transformer Input를 일치시키기

 

Graph는 반드시 다음 3개의 inputs이 있어야한다.

1. 노드 특징들 -> 토큰화
2. 인접 정보 -> 위치 인코딩
3. 엣지 특징들 -> Self Attention

 

 

 

1. 노드 특징을 입력 토큰으로 사용하기

노드 특징을 입력 토큰으로 사용하면 그래프의 인접 정보가 사라질 수 있다. 따라서 인접 정보를 위치 인코딩에 포함시켜야 한다.

 

2. 위치 인코딩에 인접 정보 포함하기

 

위치 인코딩은 각 노드가 그래프에서 어디에 위치하는지를 설명한다. 예를 들어, 노드 간의 상대적 거리를 기반으로 위치 인코딩을 설계할 수 있다. 그렇다면 좋은 위치 인코딩을 설계하는 방법은 무엇일까?

1. 상대적 거리 기반 위치 인코딩 :
   • 노드 간의 상대적 거리를 사용하여 위치 인코딩을 생성할 수 있다. 이는 위치 인식이 중요한 작업에서 유용하다.

 

2. 다른 위치 인코딩 방법

 

• 라플라시안 행렬(Laplacian Matrix): 각 그래프의 구조를 인코딩하는 데 사용된다. 라플라시안 행렬의 고유 벡터는 변환기에 입력할 수 있는 벡터이다.
• 고유 벡터(Eigenvector): 고유 벡터는 그래프의 구조를 반영하며, 변환기 모델에 입력으로 사용할 수 있다.

라플라시안 행렬 LLL을 고유값 분해하여 고유값(eigenvalues)과 고유벡터(eigenvectors)를 구한 후 라플라시안 행렬의 고유벡터 중 가장 작은 k개의 고유값에 대응하는 고유벡터를 선택하여 각 노드의 위치 인코딩으로 사용한다. 이 고유벡터들은 그래프의 구조적 정보를 담고 있다.예를 들어, k=2인 경우, 두 개의 고유벡터를 선택한다. 이렇게 선택된 고유벡터들은 각 노드의 위치를 나타내는 벡터로 사용된다.

 

3. 엣지 특징을 Transforemr Self Attention에 포함시키기

 

엣지 특징을 토큰이나 위치 인코딩에 포함시키는 것은 어렵다. 대신, Attention Score에 엣지 특징을 포함시킬 수 있다. 예를 들어, 엣지 특징을 기반으로 Attention Score를 조정할 수 있다.

 

 

• 엣지가 있는 경우:
  • 노드 i와 j 사이에 직접적인 엣지가 있고, 그 엣지의 특징이 hij=[1,0.5]라면, eij=[1,0.5]가 된다.
• 엣지가 없는 경우:
  • 노드 i와 j 사이에 직접적인 엣지가 없고, 최단 경로가 i, k1, k2, j라면, 해당 경로 상의 엣지 특징을 합산하여 eij를 정의한다.
  • 예를 들어, hik1=[0.2,0.1], hk1k2=[0.3,0.4], hk2j=[0.5,0.2]h_{k_2j} = [0.5, 0.2]hk2​j​=[0.5,0.2]라면, eij=[0.2+0.3+0.5,0.1+0.4+0.2]=[1.0,0.7]\mathbf{e}_{ij} = [0.2+0.3+0.5, 0.1+0.4+0.2] = [1.0, 0.7]eij​=[0.2+0.3+0.5,0.1+0.4+0.2]=[1.0,0.7]가 된다.

 

📝 정리

1. Transformer의 주요 구성 요소
   • 토큰화(Tokenizing): 입력 데이터의 각 부분을 벡터로 변환.
   • 자기 주목(Self-attention): 입력 시퀀스의 각 부분이 다른 부분에 얼마나 집중해야 하는지 결정.
   • 위치 인코딩(Positional Encoding): 시퀀스의 순서를 모델에 알려줌.

2. Graph Transformer의 입력 구성

• 노드 특징(Node Features): 각 노드를 토큰으로 사용.
• 인접 정보(Adjacency Information):
• 위치 인코딩에 포함.엣지 특징(Edge Features): Self-Attention 메커니즘에 포함.

3. 노드 특징을 입력 토큰으로 사용하기

• 노드 특징을 입력 토큰으로 사용하면 그래프의 인접 정보가 사라질 수 있음.
• 따라서, 인접 정보를 위치 인코딩에 포함시켜야 함.

4. 위치 인코딩에 인접 정보 포함하기

• 상대적 거리 기반 위치 인코딩: 노드 간의 상대적 거리를 사용하여 위치 인코딩 생성.
• 라플라시안 행렬(Laplacian Matrix): 그래프 구조를 인코딩하는 데 사용됨. 고유벡터(Eigenvector)는 그래프의 구조를 반영하고, 변환기 모델에 입력으로 사용될 수 있음.
  • 라플라시안 행렬 L을 고유값 분해하여 고유값(eigenvalues)과 고유벡터(eigenvectors)를 구함.
  • 라플라시안 행렬의 고유벡터 중 가장 작은 k개의 고유값에 대응하는 고유벡터를 선택하여 각 노드의 위치 인코딩으로 사용.

5. 엣지 특징을 Transformer Self-Attention에 포함시키기

• 엣지 특징을 토큰이나 위치 인코딩에 포함시키는 것은 어렵지만, Attention Score에 포함시킬 수 있음.
  • 엣지가 있는 경우: 노드 i와 j 사이에 직접적인 엣지가 있고, 그 엣지의 특징이 hij​이면 eij=hij.
  • 엣지가 없는 경우: 최단 경로의 엣지 특징을 합산하여 eij​ 정의.