2. Traditional Methods for Machine Learning in Graphs

이성범·2021년 7월 24일
0
post-thumbnail

작성자: 이성범

0.Intro

본 장에서는 Node, Link, Graph를 feature로 만드는 방법에 대하여 다룬다. 아래와 같은 Mathine Learning Tasks를 수행하기 위해서는 Node, Link, Graph를 feature로 만드는 것이 중요하다.
(본 장에서는 hand-designed features와 undirected graphs를 다룬다.)

  • Machine Learning Tasks in Graphs

    • Node-level prediction
    • Link-level prediction
    • Graph-level prediction
  • Machine Learning in Graphs

    • Goal : Make predictions for a set of objects
    • Design choices
      - Features : d-dimensional vectors
      - Objects : Nodes, edges(links), sets of nodes, entire graphs
      - Objects function : 우리의 task를 해결하는 함수

1.Node-level Features

  • Node의 feature를 구하는 방법
    • Node degree
    • Node centrality
    • Clustering coefficient
    • Graphlet Degree Vector

1-1 Node degree

  • 모든 근접 노드를 동등하게 바라봄
  • 노드와 연결된 엣지의 개수를 사용

1-2 Node centrality

Node degree는 Node의 중요도를 반영하지 않기 때문에 노드의 중요도를 반영하기 위해서는 Node centrality를 사용해야 한다.

  • Node centrality 구하는 다양한 방법
    • Engienvector centrality
    • Betweenness centrality
    • Closeness centrality
    • and many others…

(1) Engienvector centrality - 고유벡터 중심성

Engienvector centrality는 주변 노드를 활용해서 노드의 중요성을 나타내는 방법이다.

  • 노드의 중심성을 1번 식과 같이 재귀적인 방식으로 계산할 수 있다. 1번의 재귀적인 방식을 행렬을 활용한다면 2번과 같이 계산할 수 있다.

  • 2번 식을 보면 A는 Grape의 행렬이고 λ\lambda는 고유값을 의미하고 c는 A의 고유벡터를 의미한다. 행렬 A를 가지고 적절한 λ\lambda 값에 대한 고유벡터 c를 계산하면 이를 노드의 중심성을 나타내는데 사용할 수 있다.

(2) Betweenness centrality - 매개 중심성

Betweenness centrality는 노드들 간의 최단 경로를 통해서 노드의 중요성을 나타내는 방법이다.

그림에서 A의 노드의 중요성을 나타내고자 할 때 A를 제외한 나머지 노드들의 이동 경로를 봐야한다. C-B, C-D, B-D, C-E, B-E로 가는 모든 이동 경로를 보면 어떠한 경로도 A를 거치지 않기 때문에 A노드의 중요성은 0이 된다. 이와 같은 방식으로 계산을 통해서 각 노드의 중요성을 나타낼 수 있다.

(3) Closeness centrality - 근접 중심성

Closeness centrality는 중요한 노드일수록 다른 노드까지 도달하는 경로가 짧을 것이라는 가정을 가지고 노드의 중요성을 나타내는 방법이다.

그림처럼 해당 꼭지점의 도달 가능 거리의 총합의 역수를 통해서 나타낼 수 있다.

1-3 Clustering coefficient

Clustering coefficient는 그래프가 얼마나 응집력이 높은지를 알려주는 방법이다.

위 그림처럼 연결된 모든 노드 삼중체 중에서 삼각형을 이루는 노드 삼중체를 구해서 계산할 수 있다. 위 그림은 모든 삼중체 A-B-C, A-B-E, A-C-E, A-C-D, B-C-D, B-C-E 중에서 삼각형을 이루는 노드 삼중체가 A-B-C, A-C-D, B-C-E가 존재하기 때문에 0.5로 계산된다.

1-4 Graphlet Degree Vector

Graphlet Degree Vector는 Graphlet의 개수를 셈으로써 나타내는 표현방법이다. Graphlet Degree Vector를 통해 노드의 국소적인 네트워크의 위상(local network topology)에 대한 measure를 제공할 수 있다.

(1) Graphlet

  • Graphlet : Rooted connected non-isomorphic subgraphs
    • 그래프의 크기↑ → graphlet의 갯수↑
    • 가령, G1과 G2는 노드의 개수는 같지만, non-isomorphic position에 있음. <- 이런 형태들이 graphlet에 포함됨

Summary

  • capture the importance of a node is in a graph (노드의 중요성을 판단하는 방법)

    • Node degree
    • Node centrality
    • 그래프에서 영향력 있는 노드를 찾는데 유용하다. (ex. SNS에서 인플루언서 예측하기)
  • Capture topological properties of local neighborhood around a node (구조의 중요성을 판단하는 방법)

    • Node degree
    • Clustering coefficient
    • Graphlet degree vector
    • 그래프에서 노드가 수행하는 특정 역할을 예측하는데 유용하다. (ex. protein-protein interaction network 에서 protein의 기능을 예측하기)

2.Link-level Features

  • Link의 feature를 구하는 방법
    • Distance-based feature
    • Local neighborhood overlap
    • Global neighborhood overlap

2-1 Distance-based feature

Distance-based feature는 두 노드 간의 최단 거리를 통해 나타난다. 하지만 위 방법은 neighborhood overlap을 반영하지 못한다.
(그림을 보면 B-H를 가는 최단 경로는 2개, B-E를 가는 최단 경로는 1개 하지만 두 노드 간의 링크 모두 같은 숫자로 매핑됨 이렇듯 Distance-based feature 방법은 neighborhood overlap을 반영하지 못함)

2-2 Local neighborhood overlap

Local neighborhood overlap은 neighborhood overlap을 반영할 수 있는 방법이다. 위 그림 처럼 두 노드 사이에 얼마나 많은 노드를 공유하는지를 통해서 계산할 수 있다.

하지만 Local neighborhood overlap은 위 그림 처럼 두 노드 사이에 공유하는 노드가 없다면 0으로 계산된다는 단점이 존재한다.

2-3 Global neighborhood overlap

Global neighborhood overlap은 전체 그래프를 고려함으로써 Local neighborhood overlap의 단점을 해결한 방식이다.

Global neighborhood overlap은 Katz index(count the number of paths of all lengths between a given pair of nodes)와 adjacency matrix을 활용하여 구할 수 있다.

adjacency matrix는 위 그림처럼 각 노드와 노드의 연결을 1과 0으로 표현한 행렬이다. 위 그림은 길이가 1인 adjacency matrix를 표현했다.


위 그림은 길이가 2인 adjacency matrix를 구하는 방법을 나타낸 것이다.

adjacency matrix와 Katz index를 활용하면 모든 길이에 대한 경로의 수를 구할 수 있고 이를 위 그림과 같은 공식을 활용하면 Global neighborhood overlap을 계산할 수 있다.

Summary

  • Distance-based feature
    • 두 노드 간의 최단 거리를 통해 나타냄
    • neighborhood overlap을 반영하지 못한다는 단점이 존재
  • Local neighborhood overlap
    • 두 노드 사이에 얼마나 많은 노드를 공유하는지를 통해서 계산
    • neighborhood overlap을 반영하지만 두 노드 사이에 공유하는 노드가 없다면 0으로 계산된다는 단점이 존재
  • Global neighborhood overlap
    • adjacency matrix와 Katz index를 활용하여 모든 길이에 대한 경로의 수를 구하여 계산
    • Distance-based feature와 Local neighborhood overlap의 단점을 모두 해결할 방법

3.Graph-Level Features

  • Graph의 feature를 구하는 방법
    • Graphlet kernel
    • Weisfeiler-Lehman Kernel

Graph Kernels

Graph의 feature를 구하는 방법을 이해하기 위해서는 Graph Kernels에 대하여 우선 알아야 할 필요가 있다. (kernel은 SVM에서 다루는 kernel과 동일함)

Graph Kernels은 두 개의 그래프간의 유사성을 측정하는 방법으로 그 종류로 Graphlet Kernel, Weisfeiler-Lehman Kernel, Random-walk kernel, Shortest-path graph kernel 등등 다양하다.

  • Graph Kernels은 graph를 feature로 만드는 것을 목표로함
  • Graph Kernels은 그래프를 Bag-of-Words 방식을 활용하여 나타내는 것이 주요 아이디어(BOW는 문서에서 단어의 카운트를 feature로 나타내는 방법)
  • Graph Kernels은 Words 대신 Nodes를 사용하여 BOW 방식을 활용
  • 아래의 그림 처럼 4개의 동일한 노드를 가지고 있다면 두 다른 그래프는 동일한 feature를 가짐

위 그림처럼 node degrees를 사용한다면 다른 노드를 가지고 있기 때문에 두 그래프는 다른 feature를 가지게 된다. 이는 정교한 방법이 아니다.

Graphlet Kernel와 Weisfeiler-Lehman Kernel는 node degrees 보다 더욱더 정교한 방법으로 그래프의 representation을 Bag-of-* 을 사용해 나타낸다. (여기서 * 에 무엇을 사용하느냐가 중요!)

3-1 Graphlet kernel

Graphlet kernel은 * 에 Graphlet을 사용하는 방법이다.

Graphlet kernel은 위와 같은 식으로 계산한다. 그러나 G와 G'의 사이즈가 다르면 값이 크게 왜곡될 수 있다. 따라서 아래와 같은 식을 통하여 정규화를 한다.

그런데 Graphlet kernel을 Graphlet을 세는 것에 매우 많은 시간과 비용이 들기 때문에 효율적이 방법이 아니다. 따라서 조금 더 효율적인 방법으로 Weisfeiler-Lehman Kernel을 사용한다.

3-2 Weisfeiler-Lehman Kernel

Weisfeiler-Lehman Kernel은 * 에 colors를 사용하는 방법이다.

Color refinement라고 불리는 Algorithm을 활용하여 나타낸다.

우선 위 그림처럼 colors를 초기화 한 후 인접 노드의 colors를 추가한다.

후에 위 그림처럼 Aggregated colors를 Hash table에 새로운 컬러로 맵핑한다.

다시 위와 같은 동일한 괴정을 반복한다.

위 그림 처럼 각 colors의 개수를 센다.

위 그림 처럼 두 color count vectors를 내적하면 WL kernel value를 계산할 수 있다.

Weisfeiler-Lehman Kernel은 시간 복잡도가 선형이기 때문에 Graphlet kernel보다 매우 효율적인 방법이다.

Summary

  • Graphlet Kernel
    • Bag-of-graphlets
    • 시간과 비용이 많이드는 매우 비효율적인 방법
  • Weisfeiler-Lehman Kernel
    • Bag-of-colors
    • Color refinement Algorithm 사용
    • 시간복잡도가 선형인 효율적인 방법
    • 우리가 앞으로 다룰 GNN과 매우 밀접한 방법

참고자료

profile
안녕하세요.👋 같이에 가치를 아는 머신러닝 엔지니어 이성범 입니다.

0개의 댓글