SU Library

Graph공부 1. Mathine Learning with Graphs 본문

인공지능/Graph-neural network

Graph공부 1. Mathine Learning with Graphs

S U 2021. 6. 20. 01:33

*시작하기에 앞서 스탠포드 대학의 CS224W강의를 듣고 제가 공부하고 이해한 것을 정리해놓은 것입니다.

그래프는 복잡한 세상을 표현하는 일반적인 수단중 하나입니다. 대표적으로 그래프로 표현될 수 있는 정보는 페이스북의 친구관계, 유튜브 알고리즘, 네플릭스 시청자 분석 등이 있지요. 뿐만 아니라 생물학의 단백질 구조, 이미지 내에서으 의 오브젝트의 관계 등등 생각보다 많은 것들을 그래프로 표현할 수 있습니다.

그래프로 표현한 것들

 

머신러닝 관점에서 그래프는 복잡한 도메인들을 관계그래프로써표한할 수 있는 풍부한 관계 구조를 가지고 있는 것이고, 우리는 이러한 관계를 모델링함으로서, 좋은 퍼포먼스를 얻는 것을 목표로 합니다.

 

Ways to Analyze Networks

네트워크(그래프)를 분석하는 방법은 크게 다음과 같은 방법들이 있습니다.

  • Predict the type/color of a given node
    - Node classification
  • Predict whether two nodes are linked
    - Link prediction
  • Identify densely linked clusters of nodes
    - Community detection
  • Measure similarity of two nodes/networks
    - Network similarity

 

Embedding Nodes

d차원의 임베딩에 그래프의 노드들을 매핑시키는 것입니다. 이것은 비슷한 노드들끼리 임베딩차원에서 가까운 거리에 있다는 것을 의미하고 이는 관계를 정량적인 수치로 표현하는 방법입니다. 

그래프의 노드를 임베딩 차원에 매핑시키기

이전까지 개괄적인 방법에 대해서 훑어보았다면 이제부턴 그래프가 무엇인지부터 살펴보겠습니다.

 

Components of a Network

 

그래프

  • 초록색의 점 :Node 혹은 Vertex(ices)라고 부르고 /math{N}으로 표기합니다.
  • 점과 점을 이어주는 선은 links혹은 edge라고 부르며 /math{E}로 표기합니다.
  • 위 구성을 하나의 그래프 혹은 네트워크라고 부르며, /math{G(N,E)}로 표기합니다.

Networks or Graphs?

  • 네트워크는 종종 실제 시스템을 참조하기도합니다. 
    Ex: Web,Social network, Metabolic network. 
  • 그래프는 네트워크를 수학적으로 표현한 것입니다. 
    Ex: Web graph, Social graph, knoledge graph 

노드와 엣지로 표현한 그래프

위의 그림에서는 그래프의 방향이 양방향인 Undirected그래프의 예시였습니다. 그래프의 Edge의 특징은 단방향성만 가지는 것들이 존재하는데, 이를 Directed 그래프라고 합니다. 아래그림을 보면서 차이를 확인하시기바랍니다.

방향이있는 그래프와 방향이 없는 그래프

Directed의 경우 대표적인 예시론 먹이사슬 트위터 팔로우 상태 등이 있습니다.

 

Node degree

그래프에서 각각의 노드들은 degree를 가집니다. 이는 쉽개 말해서 몇개의 edge가 현재 노드로 흘러 들어오는 것이냐를 계산한 것입니다. 이는 다음과 같은 방식으로 계산됩니다. 

현재 노드에 들어오는 edge들을 인접한 노드들의 개수로 나눈 것입니다.

양방향 그래프에서의 degree계산
단뱡향 그래프에서의 degree계산

Complete Graph

하나의 양방향 그래프에서 가장 많은 엣지를 가지는 개수를 구하는 공식은 다음과 같습니다.

 

Representing Graphs: Adjacency Matrix

앞서 정의한 그래프를 인접행렬로 표현한 것입니다. 

방향성을 가질경우 들어오기만 3의 노드는 row값은 전부 0인것을 확인할 수있습니다.

각 행과 열은 각 노드를 의미하는 것이고 1행에서 0 1 0 1은 1번 노드가 2번 4번과 이어져 있다는뜻입니다. 이는 Undirected 그래프에서는 대칭이기때문에 행과열이 같은 값을 지니지만, directed일 경우 오른쪽 그림처럼 대칭성을 지니지 않게 되지요.

Representing Graphs Edge list

노드와 노드를 이어주는 링크들

노드와 노드를 이어주는 링크에 대한 표현입니다. (2,3)은 2와 3을 이어주고 (3,2)는 3에서 2로 가는 것이므로 위의 그림에선 양방향으로 표현했습니다. 그외에 단방향으로는 (3,4) ,(4,5) 등이 있습니다. 

 

Representing Graphs : Adjacency list

인접리스트 설명 

 

인접리스트는 네트워크가 Large하거나 Sparse할때 유용하게 쓰입니다. 


인접리스트는 주변의 인접한 리스트들, 현재 노드에서 이동 할수 있는 노드들을 출력합니다.

 

*여기서 Sparse하다는 의미는 fully connected의 반대의미로 모든 노드들이 maximum 한 링크를 가지지 않는 모든 네트워크를 말합니다. 

sparse

Edge Attributes 

Edge는 노드들의 관계를 나타내는데 이는 항상 0과 1로만 표현할 수 있는 것은 아닙니다. 

노드간의 관계를 나타낼 수 있는 옵션으로는

  • Weight(frequency of communication)
  • Ranking(best friend, second best friend...)
  • Type(firend,relative co-worker)
  • Sign(Friend vs Foe, Trust vs Distrust)
  • Properties depending on the rest of the graph(number of common friends)

이를 활용한 다음의 다양한 그래프들이 있습니다.

 

 

Connectivity of Undirected Graphs

 

이전까지 노드와 노드의 연결성을 확인했지만, 그래프와 그래프의 연결성도 표현할 수 있습니다. 다음은 두 그래프가 연결되어있는 것인지 떨어져 있는 것인지를 표현합니다.

 

그래프가 연결되어있을 시에, 이를 이어주는 노드를 bridge edge라고 하고 이를 이어주는 노드들을 articulation node라고 합니다.  

연결된 그래프에 대한 행렬 표현

Connectivity of Directed Graphs

  • Strongly connected directed graph
    두 노드가 서로 오고 왕복할 수 있는 경로를 가지고 있다면, 강한 연결을 가지고 있다고합니다.
  • Weakly connected directed graph
    두 노드의 이동방향이 한쪽으로만 갈수있고 다른쪽으로는 갈수 없다면 약한 연결을 가지고 있다고합니다.

A와 B는 직접적인 연결은 없지만, C를 통해서 왕복가능하므로 강한연결, D와 A 그리고 E와 A, B와 F, C와 G는 약한연결을 가집니다.

Comments