[Graph] 2장. Graph Neural Networks

1. GNN 개요

GNN(Graph Neural Networks)은 그래프 구조의 데이터를 처리하기 위해 개발된 딥러닝 방법입니다. 실제 세계의 많은 데이터가 그래프 형태로 표현될 수 있습니다:

• 소셜 네트워크: 사용자는 노드, 친구 관계는 엣지
• 분자 구조: 원자는 노드, 화학 결합은 엣지
• 교통 네트워크: 교차로는 노드, 도로는 엣지
• 단백질 상호작용 네트워크: 단백질은 노드, 상호작용은 엣지
• 인용 네트워크: 학술 논문은 노드, 인용 관계는 엣지
• 추천 시스템: 사용자와 상품이 노드, 구매 이력이 엣지

2. GNN의 주요 목표

GNN의 주요 목표는 각 노드의 주변 정보(이웃 노드)를 인코딩하는 임베딩을 학습하는 것입니다.

이 임베딩은 노드 분류, 링크 예측, 그래프 분류 등 다양한 작업에 사용될 수 있습니다.

• 예시: 소셜 네트워크에서 사용자 A의 임베딩을 학습한다고 가정해봅시다.
  • 이 임베딩은 다음과 같은 정보를 포함할 수 있습니다:
    • A의 개인 정보 (나이, 성별, 관심사 등)
    • A의 친구들의 특성
    • A의 네트워크 구조 (친구 수, 친구들 간의 연결 등)

3. GNN의 주요 연산

Graph Filtering Operation과 Graph Pooling Operation은 Graph Neural Networks (GNNs)에서 사용되는 두 가지 중요한 연산으로, 다음과 같은 주요 차이점이 있습니다:

Graph Filtering Operation:

1. 목적: 노드의 특징을 업데이트하고 이웃 노드의 정보를 집계합니다.
   (노드의 특성과 그래프 구조를 바탕으로 노드의 새로운 특성을 학습합니다.)
2. 그래프 구조: 원래 그래프의 구조를 유지합니다.
3. 출력: 각 노드에 대해 새로운 특징 벡터를 생성합니다.
4. 주요 기능: 노드 간의 관계를 고려하여 정보를 전파합니다.
   (주로 이웃 노드의 정보를 집계하는 방식으로 이루어집니다.)
5. 예시: 소셜 네트워크에서 사용자 A의 특성을 업데이트한다고 가정해봅시다.
   1. A의 모든 친구들의 특성을 수집합니다.
   2. 이 특성들을 평균내거나, 가중치를 부여하여 합칩니다.
   3. 이 집계된 정보를 A의 원래 특성과 결합하여 새로운 특성을 만듭니다.

Key Idea: Generate the node embeddings using not only the features of the node, but also the surrounding neighbors

Graph Pooling Operation:

1. 목적: 그래프의 크기를 줄이고 계층적 표현을 생성합니다.
   (노드 수준의 특성을 그래프 수준의 특성으로 변환합니다.)
2. 그래프 구조: 그래프의 구조를 변경하여 더 작은 그래프로 만듭니다.
3. 출력: 노드 수가 줄어든 새로운 그래프를 생성합니다.
4. 주요 기능: 그래프의 중요한 정보를 요약하고 계산 효율성을 향상시킵니다.
   (전체 그래프의 표현을 학습하는 데 사용됩니다.)
5. 예시: 분자 구조의 특성을 파악하는 작업을 생각해봅시다.
   1. 각 원자(노드)의 특성을 학습합니다.
   2. 이 원자들의 특성을 집계하여 전체 분자의 표현을 만듭니다.
   3. 이 표현을 사용하여 분자의 특성(예: 용해도, 독성 등)을 예측합니다.

Key Idea: Generally speaking graph pooling can be seeing as an operation that given an initial graph as input, generates a coarsened graph with fewer nodes

차이점 (Graph Filtering vs Graph Pooling):

1. 연산 결과: Filtering은 노드 특징을 업데이트하지만, Pooling은 그래프 구조 자체를 변경합니다.
2. 정보 처리: Filtering은 이웃 노드의 정보를 집계하는 반면, Pooling은 그래프 전체의 정보를 압축합니다.
3. 적용 목적: Filtering은 주로 노드 중심 작업에 사용되고, Pooling은 그래프 수준의 작업에 더 적합합니다.
4. 계산 복잡성: Pooling은 그래프 크기를 줄여 계산 효율성을 높이는 데 도움이 됩니다.

Graph Filtering은 노드 간의 관계를 고려하여 정보를 전파하는 데 중점을 두는 반면, Graph Pooling은 그래프의 전체적인 구조를 압축하고 요약하는 데 초점을 맞춥니다.

두 연산은 GNN에서 상호 보완적으로 사용되어 효과적인 그래프 표현 학습을 가능하게 합니다.

4. 그래프 필터링 방법

그래프 필터링에는 주로 Convolutional Operaion이 수행되며, 대표적으로 spectral-based 기법과 spatial-based 기법이 있습니다.

📌 스펙트럴 기반(Spectral-based) 방법:

1. 개념: 그래프의 스펙트럴 도메인에서 필터링을 수행합니다.
   (그래프의 라플라시안 행렬을 이용한 수학적 접근)

2. 작동 원리:

   • 그래프 라플라시안(Laplacian)의 고유벡터와 고유값을 사용합니다.
   • 그래프 푸리에 변환(Graph Fourier Transform, GFT)을 통해 신호를 주파수 도메인으로 변환합니다.
   • 주파수 도메인에서 필터링을 수행한 후 역변환합니다.

3. 특징:

   • 전체 그래프 구조를 고려한 글로벌 접근 방식입니다.
   • 수학적으로 잘 정의되어 있고 이론적 분석이 용이합니다.
   • 계산 복잡도가 높을 수 있습니다. (특히 대규모 그래프에서 적합하지 않음 )

4. 예시: 5개의 노드로 이루어진 간단한 그래프가 있다고 가정해봅시다.

   1. 이 그래프의 라플라시안 행렬을 계산하고, 이를 이용해 노드 특성을 변환합니다.
   2. 이 과정은 푸리에 변환과 유사하며, 그래프의 전역적 구조를 고려할 수 있습니다.

5. (심화) 스펙트럴 기반 그래프 필터 기법들

   In general, spectral graph filtering is focused on modulate the graph signals by amplifying some and remove others before reconstructing the graph signals (using Graph Fourier Transform)

   1. Poly-filter:
      • 다항식 필터 연산을 사용하여 계산 비용을 줄입니다.
      • k-홉 이웃만을 사용하여 출력 신호를 계산합니다.
      • 단점: 다항식 기저가 직교하지 않아 학습 과정에서 불안정할 수 있습니다.
   2. Cheby-filter:
      • Chebyshev 다항식을 사용하여 Poly-filter의 장점을 유지하면서 더 안정적입니다.
      • 직교 기저를 사용하여 학습 과정의 안정성을 개선합니다.
      • k-홉 이웃만을 사용하여 출력 신호를 계산합니다.
   3. GCN-filter:
      • Cheby-filter를 간소화한 버전으로, 1-홉 이웃만 사용합니다.
      • 공간 기반 필터로도 볼 수 있어, 스펙트럴과 공간 기반 방법의 중간 지점에 위치합니다.

📌 공간 기반(Spatial-based) 방법:

1. 개념: 노드의 로컬 이웃을 직접 활용하여 필터링을 수행합니다.
   (노드의 지역적 이웃 정보를 직접 집계)
2. 작동 원리:
   • 각 노드의 특징을 이웃 노드들의 특징과 결합하여 업데이트합니다.
   • 주로 가중치 합 또는 집계 함수를 사용합니다.
3. 특징:
   • 로컬 그래프 구조에 초점을 맞춥니다.
   • 계산 효율성이 높고 대규모 그래프에 적용하기 쉽습니다.
     (더 효율적이고 유연하며, 대규모 그래프에 적합함)
   • 직관적이고 구현이 상대적으로 간단합니다.
4. 예시: 소셜 네트워크에서 사용자 A의 특성을 업데이트하는 과정을 생각해봅시다:
   1. A의 직접적인 친구들의 특성을 수집합니다.
   2. 이 특성들을 평균내거나 가중합을 계산합니다.
   3. 이 정보를 A의 현재 특성과 결합하여 새로운 특성을 만듭니다.
5. (심화) 공간 기반 그래프 필터 기법들
   1. 초기 공간 기반 필터(2005년 Scarselli 등이 제안):
      • 1-홉 이웃만 사용하여 노드 특성을 업데이트합니다.
      • 지역 전이 함수(local transition function)를 사용하여 필터링을 수행합니다.
   2. GraphSAGE-filter:
      • 이웃 노드에서 정보를 집계하는 방식을 사용합니다.
      • 샘플링, 집계, 결합의 3단계로 구성됩니다.
        • 샘플링: 노드의 이웃 중 일부를 샘플링합니다.
        • 집계: 샘플링된 이웃들의 정보를 집계합니다.
        • 결합: 집계된 이웃 정보와 노드 자체의 정보를 결합하여 새로운 특성을 생성합니다.
      • 다양한 집계 함수(평균, LSTM, 풀링 등)를 사용할 수 있습니다.
   3. GAT-filter (Graph Attention Filter):
      • self-attention 메커니즘을 도입하여 이웃 노드의 중요도를 학습합니다.
      • 이웃 노드들에 다른 가중치를 부여할 수 있습니다.
   4. EC-filter (Edge-Conditioned filter):
      • 엣지에 연관된 정보를 활용하여 그래프 필터를 구현합니다.
      • 다양한 유형의 엣지가 있는 그래프에 적합합니다.
   5. GGNN-filter (Gated Graph Neural Network filter):
      • GRU(Gated Recurrent Unit)를 그래프에 적용합니다.
      • 방향성 그래프와 다양한 엣지 유형에 특화되어 있습니다.

주요 차이점 (Spatial vs Spectral) :

1. 접근 방식: 스펙트럴 방법은 그래프 전체의 구조를 고려하는 반면, 공간 방법은 로컬 이웃 관계에 집중합니다.
2. 계산 복잡도: 스펙트럴 방법은 일반적으로 계산 비용이 높지만, 공간 방법은 더 효율적입니다.
3. 확장성: 공간 방법은 대규모 그래프에 더 적합한 반면, 스펙트럴 방법은 작은 그래프에 더 적합할 수 있습니다.
4. 이론적 기반: 스펙트럴 방법은 수학적으로 더 잘 정의되어 있지만, 공간 방법은 더 직관적이고 유연합니다.
5. 필터 설계: 스펙트럴 방법에서는 주파수 응답을 직접 설계할 수 있지만, 공간 방법에서는 이웃 집계 함수를 통해 간접적으로 필터를 정의합니다.

• 최근 연구에서는 두 방법의 장점을 결합하려는 시도가 있으며, 노드 중심의 스펙트럴 필터링과 같은 하이브리드 접근 방식도 제안되고 있습니다.

5. 그래프 풀링 방법

풀링은 아래 6. GNN Framework기준으로 GRAPH-FOCUSED TASKS에서 많이 사용되며, 그래프의 정보를 축약하는 것을 목적으로 합니다.

평면 그래프 풀링 (Flat Graph Pooling)

• 특징: 노드 특성(Node features)을 직접적으로 이용하여 한 번에 그래프 표현을 생성합니다.
• 방법: 모든 노드의 특성을 평균, 최대값 등의 방법으로 집계합니다.
• 결과: 전체 그래프를 요약하는 단일 노드(또는 벡터)를 생성합니다.
• 장단점:
  • 장점: 계산이 간단하고 빠릅니다.
  • 단점: 그래프의 구조적 정보를 상당 부분 무시할 수 있습니다.
• 종류
  1. 평균 풀링: 모든 노드의 특성을 평균냅니다.
     • 예시 : 소셜 네트워크의 전반적인 특성을 파악하기 위해 모든 사용자의 나이를 평균낼 수 있습니다.
  2. 최대 풀링: 각 특성의 최대값을 선택합니다.
     • 예시 : 단백질 네트워크에서 가장 높은 상호작용 강도를 가진 연결을 선택하여 네트워크의 주요 특성을 파악할 수 있습니다.
  3. 주의 기반 풀링: 각 노드에 가중치를 부여하여 중요도에 따라 집계합니다.
     • 예시 : 추천 시스템에서 사용자의 최근 행동에 더 높은 가중치를 부여하여 현재 관심사를 더 잘 반영할 수 있습니다.

계층적 그래프 풀링 (Hierarchical Graph Pooling)

• 특징: 그래프 구조(Graph structure)를 보존하면서 점진적으로 그래프를 축소합니다.
• 방법: 여러 단계에 걸쳐 노드들을 그룹화하고, 각 그룹을 새로운 노드로 표현합니다.
• 결과: 원래 그래프의 계층적 구조를 반영하는 축소된 그래프를 생성합니다.
• 장단점:
  • 장점: 그래프의 구조적 정보를 더 잘 보존합니다.
  • 단점: FLAT GRAPH POOLING에 비해 계산이 복잡할 수 있습니다.
• 종류

  1. 다운샘플링 기반 풀링:
     - 예시 : 중요한 노드를 선택하여 축소된 그래프를 생성합니다.

     b. 슈퍼 노드 기반 계층적 그래프 풀링:

  • 예시 : 입력 그래프의 노드들을 결합하여 "슈퍼 노드"를 만들고, 이를 축소된 그래프의 노드로 사용합니다.

FLAT GRAPH POOLING은 주로 노드 특성에 집중하여 빠르게 전체 그래프를 요약하는 반면, HIERARCHICAL GRAPH POOLING은 그래프의 구조적 특성을 더 잘 보존하면서 점진적으로 그래프를 축소합니다.

6. GNN Framework

Graph Neural Networks (GNNs)에서 서로 다른 유형의 작업을 수행하기 위해 2가지 프레임워크 구조가 존재합니다: NODE-FOCUSED TASKS, GRAPH-FOCUSED TASKS

1. NODE-FOCUSED TASKS:
   • 목적: 개별 노드의 특성이나 레이블을 예측하는 작업
   • 구조: 그래프 필터링 레이어와 비선형 활성화 함수의 조합
   • 관련 요소: 주로 그래프 필터링(Graph Filtering)에 중점
   • 예: 소셜 네트워크에서 사용자의 관심사 예측
2. GRAPH-FOCUSED TASKS:
   • 목적: 그래프 전체의 특성이나 분류를 예측하는 작업
   • 구조: 그래프 필터링 레이어, 비선형 활성화 함수, 그리고 풀링 레이어의 조합
   • 관련 요소: 그래프 필터링(Graph Filtering)과 풀링(Pooling) 모두 중요
   • 예: 분자 구조의 특성 예측

주요 차이점 (NODE-FOCUSED vs GRAPH-FOCUSED):

• NODE-FOCUSED TASKS는 개별 노드에 집중하므로 풀링 레이어가 필요 없습니다.
• GRAPH-FOCUSED TASKS는 그래프 전체 정보를 집약해야 하므로 풀링 레이어가 필수적입니다.

두 프레임워크 모두 그래프 필터링을 사용하지만, GRAPH-FOCUSED TASKS에서는 추가로 풀링 단계를 통해 노드 수준의 정보를 그래프 수준으로 집약합니다.