Ⅰ. 서 론
그래프 (Graph) 데이터는 주어진 요소들의 관계 정보를 표현, 분석 및 이해하는 데 중요한 도구로 사용되고 있다. 최근 OTT (Over-The-Top)나 전자 상거래 서비스가 발전함에 따라 사용자에게 추천할 제품을 선정하는 모델의 필요성이 증가하고 있다[1]. 또한 인공지능 개인 비서는 질의 검색 시 대답 우선순위를 결정하는데 지식 그래프 (Knowledge Graph)를 사용한다. 이들 모두 노드 중요도를 사용하여 성능을 높일 수 있다. 한편, 한정된 네트워크 자원을 할당하기 위한 우선순위를 정하는 데도 사용된다. 이는 실시간 통신, 비디오 스트리밍 등과 같이 코로나 이후 사용이 지속해서 증가하고 있는 애플리케이션에서 특히 중요하다. 그럼에도 불구하고, 우리가 아는 한 노드 중요도 예측 모델은 아직 체계적으로 정리되지 않았다. 따라서 본 논문에서는 노드 중요도 예측 모델을 정리하고자 한다. 표 1과 같이 모델 학습 방법 및 입력 중요도, 엣지의 종류, 노드중심성 등 사용하는 데이터의 범위에 따라 정리하였다.
대부분의 노드 중요도 예측 모델은 라벨이 있는 데이터가 필요한 지도 학습 기반이다. 하지만 노드 중요도 라벨을 얻는 것은 어려우며, 실제로 노드 중요도 예측 과업은 라벨이 제공되지 않는 상황이 가정된다. 귀납 학습을 통해 이런 상황에서 기존 지도 학습 기반 모델의 활용성 또한 확인한다.
본 논문은 다음과 같은 의미를 가진다.
1. 노드 중요도 예측에 특화된 정리 논문을 제안했다.
2. 모델들을 학습 방법뿐만 아니라 데이터를 얼마나 활용하는지에 따라서 구분했다.
3. 노드 중요도 예측에서 그래프 구조의 중요성을 분석했다.
4. 노드 중요도 예측 모델에 대한 귀납 학습 가능성을 통신 그래프를 통해 확인했다.
본 논문은 다음과 같은 순서로 진행된다. 2, 3장에서는 사용한 데이터 집합과 노드 중요도 예측 모델들을 설명한다. 4장에서 실험 내용 및 결과를 정리 후 5장에서 본 논문을 요약하며 마친다.
노드 중요도 예측 모델 비교 (Difference between Node Importance Estimation Models)
Ⅱ. 배경지식
2.1 그래프 데이터
본 논문에서 사용하는 데이터 집합은 지식 그래프 형태이다. 지식 그래프는 방향 그래프로, 출발 노드를 주체 (Subject)라 하고 도착 노드 (Node)를 대상 (Object)이라 칭하며, 이들을 잇는 엣지 (Edge)는 관계 (Relation) 혹은 술어 (Predicate)라 한다. 이때 주체, 관계, 대상을 묶어 트리플 (Triple)이라 부르며 영어 앞 글자를 따 (s, r , o)와 같이 나타낸다. 본 논문에서는 FB15k[2], TMDB[3], IMDB[4]의 세 가지 지식 그래프 데이터 집합과 분산 응용프로그램을 실행하는 컴퓨터 간의 통신 그래프인 CISCO[5]를 사용한다. 표 2에 이들에 대한 특징이 정리되어 있으며, 상세 내용은 다음과 같다.
지식 그래프 데이터 집합 요약 (A summary of the knowledge graph datasets)
FB15k는 FreeBase[6]의 부분 집합이다. 이는 일반 지식 기반의 트리플과 각 개체의 설명이 포함된 데이터 집합이다. 따라서 다른 지식 그래프에 비해서 많은 개수의 엣지종류를 갖는다. 각 개체는 위키피디아 페이지와 연결되는데, Park 등[8]은 30일 동안의 해당 페이지 방문자 수를 수집하여 노드 중요도로써 활용하였다.
TMDB는 TMDB 5000 데이터 집합으로부터 만들어진 영화에 관련된 지식 그래프이다. 노드는 영화, 배우, 출연진, 제작진, 그리고 영화사들로 이루어져 있다. 영화의 인기도를 노드 중요도로써 활용한다.
IMDB는 또 다른 영화에 관련된 지식 그래프이다. 노드는 영화, 장르, 출연진, 제작진, 배급사, 그리고 배급된 국가들로 이루어져 있다. IMDB 웹사이트에서는 해당 영화에 대한 투표를 진행하는데, 투표수를 노드 중요도로써 활용한다. IMDB는 사용한 데이터 집합 중 가장 커다란 지식 그래프이다.
CISCO는 서로 다른 분산 응용 프로그램을 실행하는 기기 간의 통신을 나타낸다. 따라서 노드는 각 기기를 구분하지 않고 나타내며, 엣지는 기기 간의 통신을 나타낸다. 수집된 기업에 따라 총 22개의 그래프가 존재하여 표 2와 후술할 실험 결과는 평균치이다.
CISCO는 노드 중요도가 사전에 정의되어 있지 않기 때문에 본 논문에서는 많은 패킷을 주고받은 기기가 중요하다는 가정으로 송/수신한 총 패킷의 양을 노드 중요도로써 정의하였다. 노드 특징 또한 정의되어 있지 않아, 128차원의 벡터를 1로 채워 정의하였다.
2.2 그래프 신경망과 노드 중요도 예측 과업
그래프 신경망(Graph Neural Network, GNN)[8]은 그래프 데이터를 입력으로 하는 인공 신경망 (Artificial Neural Network)의 한 종류이다. 인공 신경망에서는 정형 데이터 형태의 입력에 뉴런의 가중치를 적용하여 특징을 추출한다. 이와 대조적으로, GNN은 가중치뿐 아니라 이웃 노드의 정보를 활용하여 각 노드의 특징 벡터를 갱신하고, 특징을 추출한다.
GNN의 과업은 노드, 그래프, 엣지 단위로 나뉜다. 노드나 그래프의 속성을 분류 (Classification)[12,13,15]하거나 회귀 (Regression)[7,8,10]하는 과업과 노드 간 연결 가능성을 예측하는 연결 예측 (Link Prediction)[13,14] 과업이 있다. 전자는 노드 특징 벡터나 한 그래프 내의 모든 노드 특징 벡터를 요약 (Readout)한 임베딩 벡터 (Embedding Vector)를 활용하여, 후자는 노드 특징 벡터 간의 관계를 분석하여 과업을 수행한다.
본 논문에서는 노드 회귀 과업의 하나인 노드 중요도 예측 (Node Importance Estimation)[7,10] 과업에 초점을 맞추고 있다. 이는 2.1에서 소개한 것처럼 다양하게 정의된 노드 중요도 s를 예측하는 과업이다.
노드 중요도 예측 과업은 학습 불가능한 모델인 PR (PageRank)[9]을 처음으로 발달하여 왔으며, 현재는 GENI (GNN for Estimating Node Importance), RGTN (Relational Graph Transformer Network)[10] 등 GNN 기반 학습 가능한 모델들이 제안되어 있다.
2.3 전도성 학습 및 귀납 학습
본 논문에서 다루는 중요도 예측 모델은 모두 지도 학습 기반이다. 즉 학습과 테스트를하나의 데이터 집합에서 진행하는 전도성 학습 (Transductive Learning)으로 모델이 학습된다.
하지만 실제로 노드 중요도 예측 과업은 라벨이 없는 상황에서 수행되는 비지도 학습이 가정된다. 따라서 라벨이 있는 원본 (Source) 데이터를 이용해 모델을 사전 학습한 후 라벨이 없는 목표 (Target) 데이터의 라벨을 얻어내는 귀납 학습 (Inductive Learning)을 도입한다. 목표 데이터에 적은 양의 라벨이 주어지면 이를 이용하여 사전 학습된 모델을 미세 조정 (Finetuning)을 통해 추가 학습을 할 수도 있다.
귀납 학습은 서로 다른 그래프(도메인)에서도 모델이 잘 동작해야 하는 도메인 적응 (Domain Adaptation) 과업이기도 하다. 이때 가장 큰 전제는 사전 학습에 사용된 원본 데이터와 실제로 사용할 목표 데이터가 유사해야 한다는 것이다[11]. 이를 확인하기 위해 4장의 실험에서 데이터 집합 간의 유사성을 구조적 (Topological), 의미적 (Semantic)의 두 가지로 측정하였다. 구조적 유사성은 그래프 구조를, 의미적 유사성은 노드로 사용된 코퍼스 (Corpus)를 벡터화하여 계산하였다.
Ⅲ. 노드 중요도 예측 모델
3.1 학습 불가능한 노드 중요도 예측 모델
3.1.1 PageRank (PR)[9]
웹은 개별 웹페이지를 노드로, 하이퍼링크를 엣지로하여 그래프로 표현될 수 있다. PR은 특정 웹페이지의 중요도를 들어오는 엣지가 많을수록 중요하다고 가정하여 계산한다 (식 1).
[TeX:] $$d_j$$는 노드j의 차수로, 노드 j에서 나가는 엣지의 수이다. β는 무작위 이동과 순간이동의 비율을 정하는 상수이며, N은 노드의 수를 의미한다. 순간이동은 우변의 두번째 항으로 표현되며, 식의 수렴성을 보장한다. 식 (1)을 반복 계산하여 얻은 수렴 값을 최종 노드 중요도로 사용한다.
개별 노드 중요도를 구하는 식 (1)을 전체 노드에 대해 식 (2)와 같이 표현할 수 있다.
s는 노드 전체의 중요도, M은 [TeX:] $$M_{i j}=1 / d_j$$인 열 확률 행렬이다. PR은 직관적인 아이디어로 그래프에서 노드 중요도를 계산한 초기 모델이라 할 수 있다. 그러나 그래프 구조에 따라 값이 고정되는 학습 불가능한 모델이며, 그래프 구조 외의 정보를 활용하지 못하는 한계가 있다.
3.1.2 PPR (Personalized PR)[9]
PPR은 순간이동을 특정 노드에 특정 확률로 하도록 변경한 모델이다. 순간이동 행렬을 R이라 하면 식 (3)과 같이 표현된다.
개별 노드의 중요도를 이용하여 R을 정의하면 특정 페이지에 가중치를 부여할 수 있다. 하지만, 여전히 그래프 구조에 따라 값이 고정되는 학습 불가능한 모델이며, 개별 노드의 중요도 외의 정보는 활용하지 못하는 한계가 있다.
3.2 학습 가능한 노드 중요도 예측 모델
본 논문에서 다루는 학습 가능한 노드 중요도 예측 모델은 GNN을 기반으로 한다. 본 장에서는 GNN의 노드 특징 벡터의 갱신 방법에 따라 노드 중요도 예측 모델을 정리하였다.
3.2.1 합성곱 기반
그래프 합성곱 신경망 (Graph Convolutional Neural Network, GCN)은 식 (4)와 같이 이웃 [TeX:] $$(\mathcal{N})$$ 노드의 특징을 응집 (Aggregation)하여 l번째 층에서 노드 i의 노드 특징 벡터 [TeX:] $$H_i^l$$을 갱신한다. σ는 활성 함수 (Activation Function), W는 가중치이다.
이를 정규화 (Normalized)된 인접 행렬 [TeX:] $$\hat{\tilde{A}}$$와 전체 노드 특징 행렬 H에 대해 식 (5)와 같이 나타낼 수 있다. [TeX:] $$\hat{\tilde{A}}$$는 인접 행렬 A에 자기-연결 (Self-loop)을 추가한 [TeX:] $$\tilde{A}$$와 이에 대한 차수행렬 [TeX:] $$\tilde{D}$$에 대해 [TeX:] $$\hat{\tilde{A}}=\widetilde{D}^{-1 / 2} \tilde{A} \widetilde{D}^{-1 / 2}$$로 정의된다.
대부분의 합성곱 기반 모델은 위 식을 기반으로 한다.
3.2.1.1 APPNP (Approximated PPR Propagation of Neur al Predictions)[12]
GCN에서 층의 개수를 늘리게 되면, 데이터가 과도하게 평활해지는 문제 (Over Smoothing)가 있다. 이는 모든 갱신된 노드 특징 벡터가 비슷해지는 것을 의미한다. APPNP는 노드 특징 벡터 갱신 후에 PPR 전파를 진행하여 특정 노드에 대한 가중치를 잃지 않도록 해서 이 문제를 해결한다. 이를 위해 순간이동 행렬을 입력 노드 특징 행렬 X에 2개 층의 순방향 신경망 (Feed Forward Network, FFN) [TeX:] $$f_\theta$$를 적용한 [TeX:] $$R=f_\theta(X)$$로 정의한다. APPNP는 식 (3)의 열 확률행렬 M 대신 정규화된 인접행렬을 사용하여 식 (6)과 같이 노드 특징을 갱신하며, [TeX:] $$H^\theta$$로는 R을 사용한다.
APPNP는 기존 GCN과 달리 노드 특징을 갱신하는 과정과 갱신된 노드 특징으로부터 중요도를 예측하는 과정이 분리되어 평활 등의 문제를 줄이고자 하였다. 하지만 다양한 종류의 관계(엣지)를 반영하지 못하는 한계점이 있다.
3.2.1.2 RGCN (Relational GCN)[13]
RGCN은 기존 GCN이 다양한 종류의 관계를 반영하지 못하는 문제를 해결하기 위해 고안되었다. 식 (7)과 같이 식 (4)에 합 기호를 하나 추가한 형태이다.
밑 첨자 r은 관계의 종류를, T은 자기-연결을 나타낸다. 그러나 관계의 종류가 많아질 경우 [TeX:] $$W_r$$의 개수가 증가하여 모델의 복잡도가 급증하고, 과적합 (Overfitting)이 발생하기 쉽다. 따라서 가중치 행렬을 식 (8)과 같이 기저 (Basis)와 블록 대각 분해 (Block-Diagonal Decomposition)를 이용하였다. [TeX:] $$V_b$$는 전체 B개 중 b번째 기저 벡터, [TeX:] $$a_{rb}$$는 r번째 관계의 [TeX:] $$V_b$$에 대한 계수이다.
RGCN은 다양한 관계를 적은 변수로 효율적으로 다뤄 과적합을 방지한 모델이나, 너무 많은 수의 관계를 다룰 땐 매개변수가 너무 많아지는 문제가 있다. 또한 입력 노드의 중요도를 받지 못하는 한계가 있다.
3.2.1.3 CompGCN (Composition GCN)[14]
CompGCN은 노드와 엣지에 대한 임베딩 (Embedding)을 구성 연산 (Composition Operation)으로 합치고 엣지의 방향에 따라 세 개의 가중치만을 사용하여 매개변수를 효과적으로 줄였다.
CompGCN은 트리플 형태의 데이터 집합으로 이뤄진 지식 그래프 자료형에 초점을 맞춰서, 대상 (o)에 대한 임베딩(노드 특징 벡터)을 식 (9)와 같이 주체 (s)와 관계 (r) 특징 벡터의 구성 연산 ([TeX:] $$\phi$$)으로 임베딩한다.
CompGCN은 기존의 관계 R에 역전 관계 [TeX:] $$R^{\mathrm{inv}}$$와 자기-연결 T를 추가로 정의하고, 각각 서로 다른 가중치 [TeX:] $$(W_{\lambda(r)})$$를 적용하여 식 (10)과 같이 노드 특징 벡터를 갱신한다.
또한, 식 (11)과 같이 관계에 대한 특징 벡터도 [TeX:] $$W_{\mathrm{rel}}$$로 갱신하여 관계를 더욱 효과적으로 다룬다.
CompGCN은 RGCN보다 좀 더 효율적으로 서로 다른 관계들을 다룬모델이다. 하지만 개별 노드의 중요도를 입력으로 받지 못하는 한계가 있다.
3.2.2 어텐션 (Attention) 기반
GCN 기반의 모델은 대상 노드에 대한 이웃 노드의 가중치가 두 노드의 차수 곱의 제곱근으로 일정하다. 반면 어텐션 기반의 모델은 두 노드 간의 상대적인 가중치 또한 학습한다.
3.2.2.1 GAT (Gr aph Attention Network)[15]
가장 기본적인 모델은 GAT이다. Bahdanau의 어텐션 메커니즘[16]과 비슷하게 어텐션 계수 α는 식 (13)과 같이 계산된다. 여기서 노드 i에 대한 노드 j의 중요도를 뜻하는 [TeX:] $$e_{ij}$$는 식 (12)와 같이 계산된다. [TeX:] $$\vec{a}$$는 어텐션 메커니즘에 해당하는 한 층의 완전 연결 층이며, [TeX:] $$W_F$$는 변환 행렬 (Transformation Matrix)이다. [TeX:] $$\|$$는 연결 (Concatenate) 연산자를 의미한다. 이 어텐션 계수를 이용해서 식 (14)와 같이 한 층의 갱신이 이뤄진다.
어텐션 학습 과정의 안정성을 위하여 여러 개의 어텐션을 사용하기도 하며 이를 다중 어텐션 (Multi-Head Attention)이라 한다.
GAT는 GCN에 마스킹된 (Masked) 자기-어텐션 (Self-Attention)을 적용하여 효율적으로 성능을 높였지만 다양한 종류의 관계를 반영하지 못하는 한계가 있다.
3.2.2.2 GENI (GNN for Estimating Node Impor tance)[16]
GENI는 노드 중심성을 이용해 그래프의 구조적인 정보를 포착하는 한편 노드 특징 벡터가 아닌 스칼라의 노드 중요도를 응집하고 갱신한다.
GENI는 그림 1.a처럼 크게 점수 계산 (Scoring Network), 점수 응집 (Score Aggregation), 중심성 조정 (Centrality Adjustment) 단위로 나뉜다. 이들을 쌓아서 전체 GENI 모델이 만들어지며, 그림 1.b에서는 두 개 층을 각각 2개의 다중 어텐션을 이용하여 쌓았을 때를 예시로 보여주고 있다. 한 층을 지난 후엔 다중 어텐션의 정보를 통합하기 위해 중간 응집 (Intermediate Aggregation) 단위에서 응집하고 다시 나누는 과정을 거치며, 마지막 층에서는 중심성 조정 단위를 통해 차수에 대한 과적합을 방지하고 최종 응집 (Final Aggregation) 단위에서 노드 중요도를 예측한다.
GENI[ 7] 모델 모식도 (The framework of GENI[ 7])
점수 응집 단위에서 노드i의 점수는 식 (15)과 같이 어텐션을 기반으로 갱신된다. [TeX:] $$\alpha_{i j}$$는 GAT와 동일하게 (식 13) 계산되지만 [TeX:] $$e_{i j}$$는 식 (15)와 같이 계산된다. 두 노드뿐 아니라 사이의 r번째 관계에 대한 임베딩 [TeX:] $$\phi\left(p_{i j}^r\right)$$을 같이 연결한다.
[TeX:] $$s^0$$는 노드 특징 벡터 입력으로 FFN으로 구성된 점수 계산 단위를 거쳐 계산된다.
최종적인 노드 중요도 [TeX:] $$s^*$$는 식 (17)과 같이 마지막 층에서의 점수 [TeX:] $$s^L$$에 유연하게 (Flexible) 조정된 중심성 [TeX:] $$c^*$$를 적용하여 계산된다.
노드의 중심성은 식 (18)과 같이 노드 차수의 로그 값으로 정의한다. [TeX:] $$\epsilon$$은 로그의 진수가 0이 되지 않도록 하는 작은 양의 상수이다. γ와 β는 학습 가능한 매개변수로써 차수에 과적합 되는 것을 방지하기 위해 중심성을 유연하게 조정하는 중심성 조정 단위의 연산이다.
GENI는 이전 모델들과 다르게 지식 그래프에서 이웃의 정보를 어텐션 기반으로 가중치를 주고, 다중관계를 고려하며 노드의 중심성과 입력된 중요도를 모두 사용한 모델이다. 또한, 노드의 중심성이 줄 수도 있는 단점을 해소하기 위해 유연함도 추가했다.
3.2.3 트랜스포머(Transformer) 기반
트랜스포머 (Transformer)[17]는 자연어 처리 분야 (Natural Language Progressing)에서 혁신적인 모델로 개발되었으며, 사진 관련 과업에도 널리 응용되고 있다[18]. 그래프에서는 트랜스포머 인코더 (Encoder)에 노드 특징 벡터를 토큰 (Token)으로 간주하여 입력하고 갱신한다.
3.2.3.1 RGTN (Relational Gr aph Transformer Network)[10]
RGTN 모델은 구조적 (Structural), 의미적 (Semantic) 트랜스포머 인코더를 병렬로 이용하여 그래프의 구조적, 의미적인 정보를 동시에 포착한다 (그림 2.a).
두 트랜스포머 인코더에는 노드 특징 벡터가 다르게 정의된 같은 구조 (Topology)의 그래프가 들어간다. 노드의 구조적 특징은 Node2Vec[19]을 통해 얻어지며, 의미적 특징은 노드의 설명을 트랜스포머-XL (Transformer Fixed Length)[20]로 얻는다. 두 인코더는 일반적인 트랜스포머와 동일한 자기-어텐션 기반으로 갱신된다 (그림 2.b).
RGTN[ 10] 모델 모식도 (The framework of RGTN[ 10])
자기-어텐션 중 [TeX:] $$\alpha_{i j}$$는 식 (13)과 동일하게 계산되며, [TeX:] $$e_{i j}$$는 식 (19)와 같이 계산된다.
여기서 변환 행렬 W의 아래 첨자 Q, K, E는 각각 쿼리 (Query), 키 (Key), 값 (Value)을 의미한다. 값으로 엣지 임베딩을 사용해서 E라 한다.
노드 특징 벡터는 식 (22)와 같이 다중 어텐션으로 메시지 M을 생성한다. 그 후 식 (21, 22)처럼 정규화 층 (Normalization Layer, Norm), 잔차 연결 (Residual Connection)과 FFN을 거쳐 노드 특징 벡터가 갱신된다. [TeX:] $$W_{\mathrm{o}}, W_{\mathrm{v}}$$는 변환행렬이다.
구조적, 의미적 트랜스포머 인코더를 통해 갱신된 노드 특징 벡터를 각각 [TeX:] $$H_i^s, H_i^c$$로 표기한다. 이 둘은 노드의 서로 다른 특성을 포함하고 있으므로 상호-어텐션 합성 단위 (Co-Attention Fusion Module)로 합친다.
여기서 W는 변환 행렬이고, 식 (24)와 같이 상호-어텐션 계수를 계산하여 잔차 연결, Norm, FFN을 거쳐 갱신된 뒤 (식 25) 구조적 의미적 점수 [TeX:] $$s^s, s^c$$가 계산된다 (식 26).
이렇게 갱신된 두 점수를 이용하여 최종 점수 [TeX:] $$s^*$$를 구한다 (식 27). 이때 γ는 식 (28)과 같이 계산되는 어텐션 계수, λ는 어텐션 벡터이다.
전체 손실함수L은 MSE(Mean Squared Error)를 최종 점수 [TeX:] $$s^*$$와 구조적, 의미적 점수 [TeX:] $$s^s, s^c$$에 적용한 [TeX:] $$L_0, L_1, L_2$$과 더불어 LTR (Learning-To-Rank) 손실함수 (식 29)를 가중합하여 계산한다 (식 30). 이는 소프트맥스 (Softmax)를 적용한 라벨 [TeX:] $$\hat{g}$$와 예측 점수 [TeX:] $$\hat{s}_i^*$$ 사이의 교차 엔트로피 (Cross Entropy)로 계산된다. 이를 통해 전체적인 노드 중요도 분포 또한 학습할 수 있게 된다.
RGTN은 노드의 구조적, 의미적인 정보를 트랜스포머라는 효과적인 구조를 이용해 병렬로 인코딩하여 성능을 높였다. 하지만 의미적 트랜스포머 인코더의 입력을 위해 노드 설명이란 추가 정보를 트랜스포머-XL로 인코딩하는 과정이 필요한 단점이 있다.
Ⅳ. 실 험
4.1 평가 지표
본 논문에서는 평가 지표로 NDCG@K (Normalized Discounted Cumulative Gain)와 스피어만 (Spearman, SPM), 그리고 OVER@K (Overlap)를 사용하였다. @K는 평가 시 상위 몇 개의 결과를 사용했는지를 의미하며, 100으로 통일한다.
NDCG@K는 DCG@K (Discounted CG)를 정규화한 평가 지표이다. DCG@K는 식 (31)과 같이 추천된 K개의 중요도를 순위에 따라 가중치를 부여하여 더하여 구한다 (식 31).
모델이 추천한 K개가 아닌 실제 라벨값을 이용하여 DCG@K를 계산한 것이 IDCG@K이며, 이를 이용해 식 (32)와 같이 정규화를 통해 0에서 1 사이의 값 NDCG@K를 구한다.
이때 사용하는 데이터 집합마다 전체 객체의 수가 다르므로 K를 늘려 모든 객체의 순위를 고려하긴 어렵다. 따라서 SPM을 이용한다.
SPM은 식(33)과 같이 라벨값의 분포 g와 예측 점수의 분포 s 사이의 순위 상관관계를 측정하는 지표이다. 아래 첨자 r은 순위를 의미한다. 라벨값과 예측 점수가 완전 음의 상관관계를 따르면 -1, 완전 양의 상관관계를 따르면 1의 값을 가진다.
OVER@K는 식 (34)와 같이 예측한 상위 K개와 실제 상위 K개 사이에 겹치는 객체 수의 비율을 의미한다. OVER@K는 0에서 1 사이이다.
4.2 실험
4.2.1 모델 및 데이터 집합
PR과 PPR의 경우 NetworkX[21]에 구현된 것을 사용하였다. 해당모델의 출력인 특정노드에 도착할 확률을 노드 중요도 예측값으로 사용하였다. α는 0.85, 최대 반복 횟수는 100으로 하였다. PPR의 순간이동 벡터는 PR의 결과 중 상위 10%의 노드로 중요도에 비례하게 순간이동 하도록 설정하였다. CompGCN과 GENI, RGTN은 공식 코드를 기반으로 변형하였고, 나머지 GNN 기반의 기준선 모델들은 DGL[22]에 구현된 예제를 응용하여 회귀 모델로 변형하였다.
사용한 데이터 집합은 FB15k, TMDB, IMDB와 CISCO의 네 가지이다. IMDB와 CISCO의 노드 특징 벡터 차원은 128차원, FB15k, TMDB는 64차원으로 서로 다르다. 귀납 학습을 위해 제로 패딩 (Zero Padding)을 이용하여 차원을 통일하였다. 각각 노드에 대응되는 위키 페이지의 방문자 수, 영화의 인기도, 영화에 대한 투표수와 패킷의 양을 노드의 중요도로 사용하였다. 8:1:1로 분할하여 각각 학습, 검증, 테스트에 사용하였고, 다섯 개의 서로 다른 분할의 평균 및 분산을 계산하여 실험 결과를 표 3에 정리하였다.
서로 다른 모델, 방법으로 측정한 세 데이터 집합의 노드 중요도 예측 전도성 실험 결과 (Experimental transductive results of different models and methods over the three datasets)
4.2.2 실험 설정
본 논문의 실험은 크게 전도성 및 귀납 학습으로 나뉜다. 귀납 학습의 경우 학습에 추가로 사용한 목표 데이터의 양에 따라 0, 5, 10, 20, 40, 80, 100%의 7가지로 나뉜다. 학습에 목표 데이터를 사용하지 않아도 준수한 성능을 보여 (표 5) 목표 데이터를 일부 사용해 더욱 준수한 성능을 얻을 수 있는지 확인하고자 하였다.
한편, 실제 상황에서는 노드 특징 벡터가 사용자에 따라 다르게 정의되어 원본과 목표 데이터의 노드 특징 벡터의 각 요소 의미가 달라 원본 데이터에서 학습된 가중치가 목표 데이터에서는 효과적이지 않을 수 있다. 이에 노드 특징 벡터의 모든 요소를 1로 대체하여 노드 특징 벡터를 사용하지 않는 상황을 추가하였다.
따라서 본 논문의 실험은 학습과 테스트 데이터에서 노드 특징 벡터의 사용 유무에 따라 표 4와 같이 6가지로 나뉜다. “O”와 "X”는 각각 노드 특징의 사용 유무를 지칭한다.
전도성 학습의 (1)과 (2)번 실험 결과는 표 3에 정리하였다. 모델 옆에 *가 붙은 것이 (2)번 실험의 결과이다. 사용한 모델 중 RGTN은 그래프의 구조적, 의미적 정보를 모두 갖고 오기 위해 노드 특징을 따로 정의한 모델이기 때문에 이를 사용하지 않는 상황은 적절하지 않아 제외하였으며, PR과 PPR은 노드 특징을 사용하지 않는 모델이기 때문에 제외하였다.
귀납 학습 (3)번 실험의 결과는 표 5에 정리되어 있으며, 그림 3은 (3)과 (4)번 실험의 목표 데이터양에 따른 7가지를 그래프로 나타낸 것이다. 마지막으로 (5)와 (6)번 실험의 결과는 표 8에 정리되어 있다.
CISCO는 정답이 없는 실제 상황, 특히 통신 시나리오에서 귀납 학습을 통한 적용이 가능한지 알아보기 위해 도입하였다. 따라서 전도성 학습은 하지 않았으며, 노드 특징이 정의되지 않았기 때문에 (5)와 (6)번 실험만 진행하였다. CISCO실험 결과도 그림 3과 표 8에 같이 나와 있다.
전도성 및 귀납 학습 실험 설정 (The details of transductive and inductive learning)
GENI[ 7] 모델을 사용한 귀납 학습 결과와 전도성 학습과의 성능 차이 (The results of inductive learning on GENI[ 7] and differences from transductive learning)
1 Difference: (Transductive - Inductive) / Transductive
4.2.3 데이터 집합 간의 유사성 및 노드 수 비교
귀납 학습에는 원본과 목표 데이터 집합이 서로 유사하다는 전제가 중요하다[11]. 따라서 사용한 네 데이터 집합 간의 유사성을 구조적, 의미적 두 가지로 비교하였다.
구조적 유사성은 그래프 구조 자체의 유사성을 의미한다. Graph2Vec[23]으로 128차원으로 임베딩한 그래프 간의 코사인 유사도 (Cosine Similarity)를 구조적 유사성으로 정의하였다.
의미적 유사성은 그래프의 노드로 사용된 단어들로 구성된 코퍼스의 유사성을 의미한다. 각각의 코퍼스로 훈련된 Word2Vec[24] 모델로 단어들을 128차원의 벡터로 임베딩하고 전체 단어에 대해 임베딩 벡터의 평균을 각 데이터 집합의 임베딩 벡터로 사용하였다. 의미적 유사성 또한 이렇게 만든 임베딩 벡터 간의 코사인 유사도로 정의하였다. 단, CISCO에서는 각 노드가 익명의 기기를 지칭하기 때문에 코퍼스를 구성할 수 없어 의미적 유사도 계산에서 제외하였다. 각 유사도 는 표 6에 나와 있다. 우상단 (S)는 의미적 유사도, 좌하단 (T)는 구조적 유사도를 뜻한다.
사용한 데이터 집합 간의 구조적, 의미적 유사도 (The topological and semantic similarity between datasets)
4.3 실험 결과 및 분석
4.3.1 전도성 학습
표 3은 전도성 학습, (1)과 (2)번 실험의 결과를 보여준다. 굵은 글씨는 성능이 가장 좋은 결과를, 밑줄은 그 다음으로 좋은 결과를 나타낸다. 한 가지 경우를 제외하고 가장 많은 정보를 사용한 RGTN의 성능이 가장 우수하였고, 그다음이 GENI였다. 즉 노드 중요도 예측 과업에서는 많은 정보가 중요함을 알 수 있다.
하지만 노드 특징을 사용하지 않은 경우에도 성능 저하가 크지 않다. GENI 모델에서 보면 NDCG@100 성능에 대한 오차가 각각 8.61%, 6.47%, 3.84%밖에 차이 나지 않는다. 즉, 노드 중요도 예측 과업에서 노드 자체의 특징보다는 그래프의 구조, 노드가 어떻게 연결되어 있는지가 중요함을 의미한다.
또한 PR과 PPR은 비록 NDCG@100 성능은 낮지만, SPM과 OVER@100 성능이 다른 모델보다 대체로 높다. 두 모델이 그래프 구조 자체에 집중한 모델인 만큼 전체적인 경향을 잘 예측했기 때문으로 보인다.
4.3.2 데이터 집합 간의 유사도 및 노드 수 비교
이전의 연구에서 미세 조정의 성능에 데이터 집합 간 유사도와 크기 차이가 영향을 미치는 것이 확인됐다[11]. 따라서 귀납 학습 실험 결과를 분석하기 전에 유사도와 크기를 먼저 비교할 필요성이 있다. 표6의 유사성을 [TeX:] $$\operatorname{sim}_{i j}^m$$으로 나타낸다면 이들 간의 대소 관계는 식 (35~37)과 같다.
여기서 아래 첨자 F, T, I는 각각 FB15k, TMDB, IMDB를 지칭하며 위 첨자 s, c는 각각 구조적, 의미적 유사성을 지칭한다. 즉 식 (35)와 식 (37) 은 FB15k, TMDB, IMDB 간의 구조적, 의미적 유사성을, 식 (36)은 CISCO와 FB15k, TMDB, IMDB 간의 구조적 유사성의 대소 관계를 나타낸다.
또한 표 7을 보면 TMDB가 FB15k보다 7.7배, IMDB가 TMDB보다 9.8배, FB15k보다 75배 많은 노드를 갖고 있다. 더 많은 노드에서 사전 학습된 모델은 과적합 (Overfitting)되어 미세 조정이 어려울 것이다. 실제로 IMDB로 사전 학습한 모델은 다른 경우에 비해 미세 조정이 잘되지 않음을 확인하였다.
특히 CISCO는 노드 개수가 적은 편이다. 평균 개수도 FB15k 다음으로 적으며, 제일 적은 그래프는 86개 밖에 되지 않고 제일 많은 그래프도 68,724개로 TMDB보다 적다. 이에 CISCO로의 미세 조정은 오히려 학습을 하지 않았을 때보다 떨어지는 것을 확인하였다.
사용한 양에 따른 데이터 집합 별 노드 개수 (The number of nodes in each dataset by each %)
4.3.3 귀납 학습
그림 3은 귀납 학습의 (3)과 (4)번 실험을 학습에 사용한 목표 데이터 집합의 양에 따른 성능을 나타낸다. x축은 목표 데이터 집합의 양, y축은 성능을 나타내며 실선은 각 목표 데이터 집합의 전도성 (1)번 실험 결과를 나타낸다. 범례의 윗줄은 사전학습에 원본 데이터의 노드 특성을 사용한 경우, 아랫줄은 사용하지 않은 경우를 지칭한다.
먼저 그림 3.a는 목표 데이터가 w/FB15k일 때의 귀납 학습 결과이다. 목표 데이터를 쓰지 않았을 때 NDCG@100 성능은 TMDB에서가 IMDB보다, 그리고 w/에서가 w/o에서보다 더 높다. 구조적 유사성은 IMDB와 더 높지만, 노드 수 차이가 크고, 의미적 유사성이 TMDB와 더 높기 때문이다. 전체적인 경향성을 나타내는 SPM 성능은 IMDB에서 학습된 구조적 정보를 이용하여 원본 데이터가 IMDB일 때 항상 높음을 볼 수 있다. 목표 데이터를 모두 사용하여 노드 수 차이를 최대한 줄였을 때 NDCG@100 성능은 w/IMDB에서 가장 높다. 이는 IMDB의 구조적 유사성을 최대한 활용하였기 때문이다.
그림 3.b는 목표 데이터가 w/TMDB일 때의 귀납 학습 결과이다. 목표 데이터를 쓰지 않았을 때 NDCG@100 성능은 w/IMDB에서 가장 높다. FB15k와의 유사도가 더 높지만, 노드 수로부터 이점을 받았기 때문이다. 학습에 목표 데이터를 사용하게 되면서 구조적인 정보에 더 의존하는 것을 볼 수 있으며, 목표 데이터를 모두 사용했을 땐 FB15k로부터의 구조적 정보를 더 잘 활용하게 되었다.
마지막으로 그림 3.c는 목표 데이터가 w/IMDB일 때의 귀납 학습 결과이다. 그림 3.a와는 반대로 FB15k는 노드가 너무 적기 때문에 좀 더 노드가 많은 w/TMDB에서의 NDCG@100 성능이 더 높다. 하지만 그림 3.a와 같이 SPM 성능은 FB15k의 구조적 정보에서 이점을 받아 전체적으로 높음을 볼 수 있다.
위 결론들을 토대로 귀납 학습은 그래프의 의미적 유사성보다는 구조적 유사성에 좀 더 의존적이며, 노드 수 또한 중요함을 알 수 있다.
한편 표 8은 귀납 학습의 (5)와 (6)번 실험 결과를 나타낸다. CISCO 데이터 집합은 전도성 학습을 진행하지 않았기 때문에, 원본 데이터로는 사용되지 않았으며, 목표 데이터로 사용된 경우는 그림 3.d와 같은 결과이다. 표시된 숫자는 학습에 사용한 목표 데이터양 7가지와 원본 데이터의 노드 특성 사용 여부 2가지, 총 14가지에서의 실험 결과에 대한 평균 ±분산을 나타낸다. CISCO 데이터 집합을 제외한 나머지 세 데이터 집합에서는 원본 데이터의 노드 특징 사용 유무 및 목표 데이터로 추가 학습을 하는 것과 관계없이 성능이 일정함을 확인했다. 이는 그래프 구조가 비슷하다면, 목표 데이터에서 귀납 학습을 통해 준수한 성능을 얻을 수 있음을 보여주는 결과이다.
해당 결과는 큰 이점을 가진다. 하나의 그래프에서 학습된 모델을 이용해서 다른 그래프에 쉽게 적용할 수 있기 때문에, 그래프 자체가 변하거나 여러 종류의 그래프를 포함하고 있는 네트워크를 사용하는 통신 분야에 특히 유용하게 적용될 수 있을 것으로 보인다.
GENI[ 7] 모델에서 특성을 사용하지 않았을 때의 모든 귀납 학습 결과 (The results of inductive learning without node feature of target dataset)
GENI[ 7] 모델에서의 귀납 학습 결과 (The results of inductive learning on GENI[ 7])
4.3.4 통신 시나리오 응용
본 논문에서는 네트워크 그래프인 CISCO 데이터 집합을 이용하여 유용성을 확인하였다. 먼저 그림 3.d에서 귀납 학습에 사용한 CISCO 데이터 집합의 양에 따른 (5)와 (6)번 실험에 대한 결과를 확인할 수 있다. 다른 데이터 집합과 달리, CISCO는 22개의 그래프에 대한 평균값을 보여주고 있기 때문에 ±0.1σ에 해당하는 부분을 음영으로 표시하였다.
대체로 노드 특징을 사용한 FB15k에서 사전 학습했을 때의 성능이 가장 높으며, 노드 특징을 사용한 TMDB에서 사전 학습했을 때의 성능이 가장 낮은 것을 볼 수 있다. 또한 노드 특징을 사용하지 않은 경우 IMDB, FB15k, TMDB 순으로 성능이 높은 것을 볼 수 있는데 이는 4.3.3에서 확인한 것처럼 그래프 구조와 노드 개수 차이에 영향을 받은 결과이다. 식 (36)에서 확인할 수 있듯, CISCO는 구조적으로 FB15k와 제일 유사하며, 그다음 IMDB, TMDB 순으로 유사하다. 또한 표 6에서 보듯 노드 수는 FB15k 다음으로 적다.
먼저 노드 특징을 활용한 경우 FB15k에서가 제일 높고, IMDB와 TMDB 순으로 높다. 이는 FB15k보다 CISCO의 노드가 많아 FB15k에서 학습한 정보를 잘 활용하여 CISCO에 맞게 미세 조정이 되었지만 다른 두 데이터 집합에서는 그러지 못한 것이다. 한편 노드 개수가 가장 많은 IMDB에서 성능이 제일 낮지 않은 것은 구조적 유사성에서 이점을 가져왔기 때문이다.
노드 특징을 활용하지 않은 경우에도 구조적 유사성과 성능이 높은 순서 간의 관계를 찾을 수 있다.
Ⅴ. 요약 및 결론
노드 중요도 예측 과업은 그래프 데이터를 분석하는데 중요한 과업이며, 여러 서비스에서 제품을 추천할 때 지식 그래프에서 질의 검색 시 우선순위를 결정하는 데 활용되고 있다. 본 논문은 이런 노드 중요도 예측 과업을 위한 모델들을 모델 구조 및 사용하는 데이터 범위에 따라 구분하였다. 또한 GENI에서 귀납 학습을 진행한 결과 원본 데이터와 목표 데이터가 구조적으로 유사할 때 더 좋은 성능을 보임을 확인하였고, 이에 더해 노드 수 또한 중요함을 확인하였다.
지도 학습 기반의 모델만 제안된 노드 중요도 예측 과업은 실제로 비지도 학습이 가정된다. 하지만 본 논문을 통해 확인한 전이 학습 및 귀납적 테스트의 가능성은 이런 차이를 보완해 줄 것으로 기대된다. 본 논문에서는 이를 통신 분야 데이터 집합인 CISCO를 통해 실제로 유용함을 입증하였으며, 이뿐 아니라 다른 데이터 집합에도 적용될 수 있을 것이다.