그래프는 노드의 집합 V와 이들의 관계를 나타내는 엣지의 집합 E로 정의한다. 그래프의 엣지에 방향성이 없다면 이를 undirected graph, 방향성이 있다면 directed graph, 엣지에 weight가 있다면 weighted graph라고 부르는 등 graph에는 다양한 종류들이 있다. 이번 포스팅에서는 multi-relational graph, 그리고 그 대표적인 종류 중 하나인 heterogeneous graph와 multiplex graph에 대해 알아보겠다.
Multi-relational graph
Multi-relational graph는 edge가 특정한 type을 가지고 있는 그래프를 의미한다. 예를 들어, 인스타그램 속 사람들의 관계를 나타내는 그래프가 있다고 하자. 이 관계에는 서로 팔로잉하는 관계, 한쪽만 팔로잉하는 관계, 차단한 관계 등 다양한 종류가 있을 것이다. 이러한 관계의 종류를 edge type이라고 부르는 것이다. Multi-relational graph의 edge는 다음과 같이 정의할 수 있다.
또한 multi-relational graph의 adjacency matrix는 각 edge type별로 정의한다.
Heterogeneous graph
Multi-relational graph의 대표적인 예시 중 하나인 heterogeneous graph는 노드 또한 노드의 타입을 가지고, 이 그래프의 edge들은 node type에 따라 결정된다. 예를 들어, multiparitite graph는 연결되는 노드의 타입이 다를 때에만 두 노드 사이에 엣지를 생성한다. Heterogeneous graph의 또다른 예시는 특정 엣지 타입은 특정 노드 타입의 노드들만을 연결하는 것이다. 예를 들어, 질병, 약, 단백질을 노드 타입으로 가지는 그래프가 있다고 하자. 그러면 어떤 질병을 낫게 하는 약이 무엇인지를 표시하는 엣지는 질병 타입과 약 타입의 노드들만을 연결할 것이다.
Multiplex graph
Multi-relational graph의 또다른 예시 중 하나인 multiplex graph는 graph의 구조를 k개의 layer로 풀어서 설명한다. 모든 노드들이 각 k개의 layer에 모두 있다고 가정하고, 각 layer는 다른 관계를 표현한다.
Multiplex graph에는 intra-layer edge type과 inter-layer edge type의 두 가지 edge type이 있다.
- Intra-layer edge type: 한 layer 안에서 서로 다른 노드를 이어주는 역할을 하는 edge이다.
- Inter-layer edge type: 서로 다른 layer에 있는 같은 노드를 이어주는 역할을 하는 edge이다.
이를 좀 더 직관적인 예시로 설명해보겠다. 예를 들어, 각 layer가 버스 / 기차 / 비행기의 교통수단을 표현하고, 각 노드가 도시들을 표현한다고 하자. 그럼 한 layer 내의 intra-layer edge는 각 도시 간의 버스편 / 기차편 / 비행기편이 있는지를 표현하고, inter-layer edge는 한 도시 안에서 교통수단을 환승하는 것을 의미할 것이다.
이번 포스팅에서는 graph representation learning 포스팅을 시작하기에 앞서, multi-relational graph가 무엇이고 이 예시에는 어떤 것이 있는지에 대해 알아보았다. 앞으로 graph representation learning에 관련된 포스팅도 시작해보겠다. (틈틈이 원래 하던 머신러닝 포스팅도..!)
References
1. Hamilton. William L., Graph Representation Learning.
2.Hammoud, Zaynab & Kramer, Frank. (2020). Multilayer networks: aspects, implementations, and application in biomedicine. Big Data Analytics. 5. 10.1186/s41044-020-00046-0.
최근댓글