[GNN] Lecture 2 _(1) : 전통 그래프

전통적인 그래프 접근법

 

1. 노드 및 그래프 분류를 위한 그래프 통계량과 커널 방법

그래프 통계량

• 기존의 그래프 데이터에서의 분류 문제는 전통적인 기계학습 패러다임을 따름
• 그래프로부터 통계량 및 특징을 추출하고 분류기의 입력으로 활용
• 노드-레벨 통계량과 그래프-레벨 통계량이 쓰임

 

 

노드-레벨 통계량

• 노드 연결수 (Degree)
  • 가장 유용하고 필수적으로 확인해야 할 노드-레벨 통계량
  • 노드에 대해 인접(incident)한 링크 수를 계산
  • 가중(weighted) 그래프: 위 식을 통한 일반화 가능, 0과 1 대신 가중치로 확장해서 씀,
  • 유향(directed) 그래프: 인접 행렬의 행/열의 합으로 진출/진입 링크 수를 계산하여 정의
  • 예제: Marriage Network
    • 노드 연결수- 메디치: 5, 스트로치: 3, 과다니: 2

 

• 노드 중심성 (Centrality)
  • 일반적으로 노드 분류 문제에서 연결수보다 더 중요한 역할
  • 고유벡터 중심성, 매개 중심성, 근접 중심성 등
  • 고유벡터 중심성 (Eigenvector-)
    • 노드의 이웃이 얼마나 중요한지 고려하여 중심성 계산
    • 노드의 중심성이 이웃들의 중심성의 평균에 비례한다는 점화식을 통해 정의

• 위 식의 해를 노드 중심성 벡터 e라고 하면, 다음과 같이 고유벡터 식과 동일
• 고유벡터 식을 만족하는 중심성 벡터 e가 잘 정의됨
  • Perron-Frobenius Theorem: 행렬 A가 nonnegative irreducible일 때
    (즉, 그래프가 connected), 가장 큰 실수 고유값은 유일하며 연관된 고유벡터(leading eigenvector)의 모든 성분은 양의 값을 가짐
• 고유벡터 중심성 계산
  • 그래프 내에서 노드의 랭크를 무한히 긴 무작위 행보(random walk)를 통해 도달 가능한 정도로 측정
  • Power iteration 방법을 통해 leading (or dominant) 고유벡터를 계산 가능:
    • 반복해서 곱하고 정규화하는 과정

• • 매개 중심성 (Betweenness-)
    • 노드가 다른 노드들 사이의 최단 경로(shortest path)에 얼마나 포함되는지를 측정
    • 노드 u가 s와 t 사이의 최단 경로에 포함되면 1, 아니면 0으로 정의
  • 근접 중심성 (Closeness-)
    • 노드부터 다른 노드까지 도달 가능한 평균적인 최단 경로 거리(geodesic distance)의 역수로 측정
    • 노드 u와 v 사이의 최단 경로 거리

 

• • 노드의 이웃 노드들 사이에서 닫힌 삼각형이 생기는 비율
  • 𝑁(𝑢)= {𝑣 ∈ 𝑉 | 𝑢, 𝑣 ∈ 𝐸} : 노드 𝑢의 이웃 노드 집합군집화 계수 (Clustering Coefficient)

 

• 군집화 계수 (Clustering Coefficient)
  • 좁은 세상 네트워크(small-world network):
  • 많은 소셜, 생물학 네트워크에서 군집화 계수는 무작위(random) 그래프에서의 기대값보다 큰 경향
  • 비율 계산 대신 노드가 속하는 삼각형의 개수로 대체하기도 함

 

 

• 에고 그래프 (Ego Graph)
  • 노드와 이웃 노드 집합 사이의 모든 연결을 포함하는 부분그래프(induced subgraph)
  • 군집화 계수는 에고 그래프 내부 삼각형 개수와 연관됨
    • 전체가 아닌, u와 연결된 노드들의 관계만 보기 때문에 가능
  • 모티프(motif or graphlet): 삼각형 대신 사이클(cycle) 등 보다 복잡한 또는 고차원 구조를 세어서 특성을 파악할 수 있음

 

 

 

 

그래프-레벨 통계량

• 그래프 분류
  • 노드 분류가 아닌 그래프 분류가 목표라면 다른 접근 방식이 필요
  • 그래프 커널(graph kernel): 그래프의 부분구조를 비교하여 그래프 간 유사도를 구할 수 있도록 설계된 커널 함수
• 노드 주머니 (Bag of Nodes)
  • 가장 단순한 방법은 노드-레벨 통계량을 단순 취합(aggregate)하여 정의하는 것
  • 노드들의 연결수, 중심성, 군집화 계수의 히스토그램 또는 요약 통계를 그래프-레벨 표현으로 활용
  • 지역적 노드-레벨 통계량을 기초로 하기 때문에 중요한 전역적 성질을 놓칠 수 있음
• WL 커널 (Weisfeiler-Lehman Kernel)
  • 반복적인 이웃 취합(neighborhood aggregation)을 통한 풍부한 속성 정보 취합
  • 그래프 동형(graph isomorphism) 문제 해결을 위한 근사적 방법으로 널리 쓰임
• WL 알고리즘
  • Step 1: 각 노드의 초기 레이블(abel) 할당
  • Step 2. 반복적으로 다음을 시행:

• Step 3: K번 반복 수행 후, ℓ 𝐾 𝑣 는 K-hop 이웃 관계의 구조를 요약함
• 그래프의 특성 표현으로 이들의 히스토그램 또는 요약 통계를 활용 가능
• WL 커널: 서로 다른 두 그래프의 결과 레이블 집합의 차이를 비교

 

• 모티프 기반 방법
  • 그래프의 부분구조인 모티프의 발생 빈도를 계산 및 열거하여 비교
  • 모티프를 세는 것은 조합적으로 매우 어려운 문제
  • 대안으로는 경로-기반 방법이 활용됨

 

• 경로-기반 방법
  • 모티프를 열거하는 대신 무작위 행보(random walk)를 수행하는 방법 활용
  • 무작위 행보, 경로 관련 방법은 조합적 제약을 피해 구조적 정보를 취합할 수 있는 방법임

 

 

---

 

 

 

출처 :

- William L. Hamilton. (2020). Graph Representation Learning.

- 충남대학교 임성수 교수님 그래프 기계학습 강의