2. 그래프 선택 CS224W: Machine Learning with Graphs 정리

https://web.stanford.edu/class/cs224w

목차

- 그래프 표현 선택

- 방향 그래프와 무방향 그래프

- 이분 그래프

- 인접 행렬

👉 그래프 표현 선택

1. 동종그래프

2. 이종그래프

 

1. 일반적인 그래프(동종)

 그래프는 노드와 엣지로 구성되어 있고 수식으로 G(V, E)로 표현한다. 일반적인 그래프는 아래와 같이 동종의 그래프이다. 노드의 특징이 동일하며 노드와 노드를 연결하는 엣지들이 존재한다. 아래와 같은 노드와 엣지를 가진 그래프가 있을 때  Actor1과 Actor2는 Movie1에 같이 출연했다로 해석할 수 있다. 

• 노드 : 배우
• 엣지 : 영화

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

 

2. Heterogeneous graph(이종 그래프)

이종 그래프는 위의 동종의 그래프와는 다르게 노드가 단일 종류가 아닌 여러종류가 될 수 있으며 실제로 많은 그래프들은 이종 그래프이다. 이종 그래프는 G = (V, G, R, T)와 같이 표현이 된다.

 

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

그래프를 만드는 방법

• 노드가 무엇인가?
• 에지가 무엇인가?

주어진 도메인/문제에 대한 적절한 네트워크 표현을 선택하는 것은 네트워크를 성공적으로 사용할 수 있는 능력을 결정한다.

•  특정 도메인이나 문제를 효과적으로 해결하기 위해서는 이를 모델링하는 네트워크(그래프)의 표현 방식을 적절히 선택하는 것이 매우 중요하다다. 네트워크 표현은 문제 해결 능력에 직접적인 영향을 미친다.
• 표현의 유일성과 다양성: 어떤 문제나 도메인은 명확하고 유일한 네트워크 구조로 표현될 수 있다. 이는 문제를 모델링하는 방법에 대한 명확한 지침이 있음을 의미한다. 반면, 다른 문제들은 여러 가지 방식으로 모델링될 수 있으며, 이는 하나의 문제에 대해 다양한 그래프 표현이 가능함을 의미한다. 이 경우, 선택한 표현 방식이 문제 해결의 효과에 큰 영향을 미칠 수 있다.
• 링크 할당의 중요성: 네트워크 내에서 노드 사이의 연결(링크)을 어떻게 정의하느냐는 모델링하려는 문제의 본질을 결정한다. 즉, 네트워크에서 링크를 할당하는 방식은 분석하고자 하는 질문의 종류를 결정하며, 따라서 분석 결과에 큰 영향을 미친다.
  
  

올바른 네트워크 표현을 선택하는 것은 문제 해결의 성공 여부를 좌우할 수 있으며, 이는 GNN과 같은 고급 기술을 활용할 때 특히 더 중요한 고려사항이 된다.

 

👉 방향그래프와 무방향 그래프

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

 

 

- 방향그래프는 연결여부 뿐아니라 방향정보도 중요한 데이터에서 사용한다. 

- 무방향그래프는 노드와 노드의 연결여부만이 중요한 데이터에서 사용한다.

 

👉 이분 그래프

이분 그래프는 노드를 두 개의 분리된 집합 U와 V로 나눌 수 있는 그래프로, 모든 링크가 U의 노드와 V의 노드를 연결하는, 즉 U와 V가 독립적인 집합인 그래프이다. 조금 더 이해하기 쉽게 하자면 2개의 다른 타입의 노드가 존재하고 같은 타입의 노드끼리는 연결되지 않고 다른 타입의 노드끼리 연결된 그래프이다.

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf,  https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

 

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

위와 같은 이분 그래프는 공통된 이웃을 이용하여 한 쪽 노드로 투영할 수 있다.

예를 들어 1, 2, 3번 배우가 A라는 영화에 함께 출연했다면 1, 2, 3번 배우는 연결되었다고 할 수 있다.

 

예시

- 저자-논문(저자가 저술한 논문

- 배우 대 영화(출연)

- 사용자-영화(사용자가 평가한 영화)

 

👉 인접 행렬

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

 

무방향 그래프의 인접행렬

- 방향이 지정되지 않은 그래프의 경우 A행렬의 ij의 항목은 노드 i와 j가 연결되어 있으며 1 없으면 0으로 표현한다.

- 기본적으로 무방향 그래프는 대칭이다 즉, Aij = Aji 식이 성립하며 자기 자신은 Aii = 0이다.

- I노드의 차수는 I노드에 대한 모든 J노드의 값을 합한 값이다. 1번 노드의 차수는 A11, A12, A13, A14 = 2

 

방향 그래프의 인접행렬

- 방향이 지정된 그래프의 경우 인접행렬 해당 방향으로의 연결이 되어있으면 1 없으면 0으로 표현한다.

- 방향 그래프는 무조건 대칭일 수 없다. 따라서 Aij != Aji 이며 마찬가지로 자기 자신은 Aii = 0이다.

 

추가적인 인접행렬 표현 방법(셀프 루프, 다중연결, 가중치 그래프)

출처 : https://web.stanford.edu/class/cs224w/slides/01-intro.pdf

 

📝 정리

우리는 그래프의 다양한 표현 방식과 그 종류를 알아봤다. 동종그래프와 이종그래프로 시작하여 방향 그래프, 무방향 그래프, 그리고 이분 그래프에 이르기까지, 각각의 구조에 대해 살펴보았다. 이를 통해 도메인에 따른 올바른 네트워크 표현을 선택하여 그래프 신경망(GNN)을 포함한 다양한 애플리케이션에서 복잡한 데이터 구조를 적용할 수 있다.

 

다음 정리에서는 GNN을 이용하여 할 수 있는 TASK들에 대해 알아보겠다!

2024.03.14 - [GNN/CS224] - 3. GNN의 TASK CS224W: Machine Learning with Graphs 정리

3. GNN의 TASK CS224W: Machine Learning with Graphs 정리