Graph Representation Learning - (1) 그래프 구조의 기초

Basic Graph theory for Machine Learning

 

 

figure1

 

 

그래프의 구성 요소 : 노드(node) , 엣지(edge) , edge weight(가중치) , 노드와 노드 사이의 방향(direction) , Self-connection

 

이때 , 방향과 가중치, 그리고 self-connection 는 있어도 되고 없어도 됩니다. 이는 사용자가 graph 구조의 data structure 를 define (graph construction) 하기 나름입니다. 따라서 그래프에서 노드끼리의 방향성의 유무에 따라 Directed graph / Undirected graph 로 나뉩니다.

가중치가 있는 그래프일 경우 , Weighted graph 가 됩니다.

 

 

How to represent a graph

 

 

 

 

figure2

 

그래프 구조의 데이터를 실제로 컴퓨터에 어떻게 입력시킬까요 ? 

모든 그래프는 Adjacency Matrix 형태로 표현됩니다.

 

따라서 , Graph = Adjacency Matrix 입니다. 완전히 같은 표현입니다.

그러므로 우리가 보는 real world 의 데이터들은 대부분 그래프 구조로 표현하게되면 , adjacency matrix 는 매우 sparsity 가 큽니다.

이게 기계학습에서 어떤 태스크를 풀 때 문제에 따라 GNN 을 이용하는것이 유불리가 분명할것으로 생각됩니다. 

이를테면 , NLP 도메인에서 short text 의 경우에는 오히려 그래프구조가 Bag-of-Words (BoW) representation 이나 tf-idf measure 같은것보다 단어와 단어들사이의 relation 을 학습하기 훨씬 용이하겠지만 , long text 에서는 그래프보다는 transformer 형태의 언어모델이 훨씬 유리할 가능성이 큽니다. 

 

 

 

Node Degree

figure3

 

 

그래프 데이터 구조에서 node degree 란 , 한 노드에 인접해 있는 (연결되어 있는) 노드의 개수를 말합니다.

따라서 위의 그래프에서 빨간색 노드의 node degree = 4 입니다.

 

 

 

따라서 그래프 전체에서 node degree 의 평균값도 위와 같이 계산할 수 있습니다.

추가적으로 , Directed graph 에서는 in-degree 와 out-degree 가 존재하게 됩니다.

 

 

Attributes

 

그래프에서는 노드와 엣지에 적용할 수 있는 여러 속성이 있습니다.

 

• 가중치(Weight) : 객체 간 의사소통을 나타낸 네트워크에서 네트워크의 빈도를 가중치로 표현할 수 있습니다.
• 순위(Ranking) : 객체 간 관계에 순위가 있을 경우 순위 속성을 사용하여 나타낼 수 있습니다.
• 유형(Type) : 객체 간 관계의 유형이 다를 경우 이를 속성으로 추가하여 표현할 수 있습니다.
• 부호(Sign) : 우호 관계, 적대적 관계와 같이 완전히 반대의 관계를 가질 경우 부호 속성을 추가하여 Positive/Negative 관계를 표현할 수 있습니다.

 

Self-Connection (Self-loops)

 

Self-connection 이란 , 그래프에서 한 노드가 자기 자신과도 연결되어 있는것을 뜻합니다. 이 경우 , adjacency matrix 에서 diagonal element 가 0이 아닌 자기자신의 edge weight 값이 오게 됩니다. (위의 figure2 참고)

weight 가 없이 연결만 된 그래프의 경우는 diagonal element = 1 이 됩니다. 

(따라서 일반적인 경우의 그래프는 diagonal elements = 0 입니다.)

 

figure4

 

 

Connectivity

 

 

특별히 , Directed graph (유향 그래프) 에서는 특정한 노드 관계를 가진 두 노드를 강한 연결성(Strong Connectivity) 로 나타낼 수 있다.

 

 

 

위와 같이 , 유향그래프에서 두 노드의 연결성이 A 노드 -> B 노드 와 B 노드 -> A 노드 모두 연결되있을때 Strongly Connected 라고 합니다. 즉 , 유향 그래프에서 어떠한 두 노드를 선택하더라도 서로간을 연결하는 경로가 존재하는 그래프를 말합니다.