이번 글에서는 node degree, clustering coefficient와 같이 node 특징을 나타낼 수 있는 척도 중 하나인 특정한 subgraph를 나타내는 말인 graphlet과, 이를 활용하여 node의 특징을 graph의 구조적인 측면을 활용하여 나타낼 수 있는 또다른 척도인 graphlet degree vector(GDV)에 대해 알아보겠다.
Graphlet
우선, graphlet의 정의에 대해 알아보겠다. graphlet은 서로 연결되어 있는(connected) induced non-isomorphic subgraph를 말한다. connected는 떨어져 있는 노드가 없는 것을 의미할 것이고, 다른 두 단어는 조금 생소하다. 각 단어의 뜻을 하나씩 알아보겠다.
induced subgraph
induced subgraph는 어떤 노드들을 선택했을 때, 해당 노드들 사이에 연결된 모든 엣지들을 포함하는 subgraph를 말한다. 예를 들어 다음과 같은 그래프가 있다고 하자.
이 예시 그래프에서, 아래 그래프는 induced subgraph가 맞을까?
위 그래프는 induced subgraph이다. 왜냐하면, 위 예시 그래프에서 선택된 노드인 B, C, u 사이에 존재하는 모든 엣지들을 포함하고 있기 때문이다. 그렇다면 다음 그래프는 induced subgraph가 맞을까?
위 그래프는 induced subgraph가 아니다. 왜냐하면, 선택된 노드인 B, C, u 사이에서 B, C 사이에 존재하는 엣지를 포함하지 않았기 때문이다.
graph isomorphism
graph isomorphism은, 두 그래프가 같은 개수의 노드를 가지고 있고, 이 두 그래프의 노드들이 똑같이 연결되어 있는 것을 말한다. 예를 들어, 다음과 같은 두 그래프가 있다고 하자.
두 그래프는 언뜻 보기에는 다르게 생겼지만, isomorphic graph이다. 왜냐하면, 각 노드들을 (e2, c2), (e1, c5), (e3, c4), (e5, c3), (e4, c1)로 매핑하면 각 노드들 사이에 연결된 엣지 관계가 같기 때문이다.
다시 graphlet의 정의로 돌아가자. graphlet은 서로 연결되어 있는(connected) induced non-isomorphic subgraph를 말한다. 다시 아래와 같은 또다른 예시 그래프가 있다고 하자.
위 그래프로부터 도출될 수 있는 최대 노드 3개의 graphlet에는 어떤 것이 있을까? (이 단계에서는 노드 u, a, b, c를 생략한다.)
이렇게 세 개의 graphlet이 도출될 수 있을 것이다.
Graphlet Degree Vector (GDV)
Graphlet Degree Vector는 해당 노드에 대해 가능한 graphlet의 개수를 센 vector를 말한다. 다시 위 예시 그래프를 살펴보자. 첫 번째 노드 2개짜리 graphlet은 위 그래프에서 노드 a의 자리에 노드 u를 포함하면서 몇 개의 다른 경우의 수가 있을 수 있을까? 답은 아래와 같이 2개이다.
두 번째 노드 3개짜리 graphlet은 위 그래프에서 노드 b의 자리에 노드 u를 포함하면서 몇 개의 다른 경우의 수가 있을 수 있을까? 답은 아래와 같이 1개이다. (해당 graphlet을 돌려가면서 b를 u 자리에 세 번 위치하여도 같은 형태이기 때문에 1개가 된다.)
세 번째 또 다른 노드 3개짜리 graphlet은 c의 자리에 u가 위치하게 만드는 것과 d의 자리에 u가 위치하게 만드는 것이 아예 다른 형태의 graphlet을 도출할 수 있다. 그러므로 노드 c와 d에 대해 각각 빈도를 따로 구해야 한다. 우선, 노드 c의 자리에 노드 u를 포함하면서 몇 개의 다른 경우의 수가 있을 수 있을까? 답은 0개이다. c 자리에 노드 u를 위치하게 되면 그것은 모든 노드에 연결된 엣지를 포함하는 graphlet이 될 수 없기 때문이다. 다음으로, 노드 d의 자리에 노드 u를 포함하면서 몇 개의 다른 경우의 수가 있을 수 있을까? 답은 아래와 같이 2개이다.
그러므로 우리는, 노드 u의 GDV = [a, b, c, d]를 [2, 1, 0, 2]로 표현할 수 있다.
이번 포스팅에서 우리는 graphlet이 무엇인지와 함께 이를 활용하여 node feature를 표현하는 GDV(Graph Degree Vector)에 대해 알아보았다. graphlet은 node feature에 뿐만 아니라, 그래프 전체에서 해당 graphlet이 일어나는 빈도를 활용하여 graph-level feature로도 활용이 가능하다. 다음 포스팅에서는 edge(link) feature들에 대해 알아보겠다.
GNN 이거 포스팅하는 거 맞나... ML도 처음엔 조회수 잘 안나오긴 했는데... (조낳괴)
References
1. Hamilton. William L., Graph Representation Learning.
2. Jure Leskovec. CS224W: Machine Learning with Graphs.
최근댓글