[SIGIR 2020] Attentional Graph Convolutional Networks for Knowledge Concept Recommendation in MOOCs in a Heterogeneous View

What is heterogeneous graph?

이질적 그래프는 그래프 내에서 두 가지 이상의 유형의 노드 또는 엣지가 있는 그래프를 말합니다. 일반적인 그래프는 모든 노드와 엣지가 동일한 유형을 가질 때 반면, 이질적 그래프는 다양한 유형의 노드와 엣지를 가질 수 있습니다. 예를 들어, 사회 네트워크에서 노드는 ‘사람’, ‘장소’, ‘이벤트’ 등 다양한 유형을 나타낼 수 있고, 엣지는 ‘친구 관계’, ‘방문’, ‘참석’ 등 다양한 유형의 관계를 나타낼 수 있습니다. 이질적그래프는 다음과 같은 특징을 지닙니다.

• 정보의 풍부성: 이질적 그래프는 다양한 유형의 노드와 엣지를 포함하기 때문에 더 많은 정보를 표현하고 저장할 수 있습니다. 예를 들어, 사회 네트워크에서 사용자, 게시물, 그룹, 이벤트 등 다양한 유형의 정보를 하나의 그래프 내에 표현할 수 있습니다.

• 복잡한 관계의 표현: 단일 유형의 노드와 엣지만을 가진 동종 그래프에 비해, 이질적 그래프는 다양한 유형의 관계를 캡처할 수 있습니다. 이를 통해 데이터 간의 더욱 복잡하고 다양한 상호작용을 나타낼 수 있습니다.

• 높은 유연성: 다양한 데이터 소스에서 오는 정보를 통합하는 것이 쉽습니다. 예를 들어, 영화 추천 시스템에서 사용자, 영화, 감독, 배우 등 다양한 엔터티 유형과 그들 간의 관계를 이질적 그래프로 표현할 수 있습니다.

• 향상된 분석 능력: 이질적 그래프를 사용하면 전통적인 동종 그래프보다 더 정확하고 깊은 인사이트를 얻을 수 있습니다. 다양한 유형의 노드와 엣지를 분석함으로써, 더욱 풍부하고 다양한 패턴과 구조를 발견할 수 있습니다.

• 높은 표현력: 이질적 그래프는 복잡한 데이터 세트와 실세계의 다양한 시나리오를 더 잘 표현할 수 있습니다. 실제 세계의 많은 시스템과 네트워크는 여러 유형의 엔터티와 그들 간의 관계로 구성되어 있기 때문입니다.

What is Knowledge Concept?

지식 개념(Knowledge Concept)은 학생이 문제를 풀 때, 문제가 가지고 있는 특성을 의미합니다. 예를 들어 수학에는 극한, 미분, 적분, 기하와 같은 많은 개념들이 존재하고, 과학에서는 유전, 지질, 천체관측 등 다양한 개념들이 존재합니다. 교육관련 분야에서는 이런 문제가 속한 개념을 지식 개념(KC) 라고 정의하고 있습니다.

Introduction

대규모 오픈 온라인 코스(MOOCs)는 전 세계적으로 대안 교육의 모델로 자리잡고 있습니다. Coursera, edX, Udacity와 같은 MOOC 플랫폼은 수백만명의 사용자에게 유명한 대학의 수많은 강의를 제공하고 있습니다. 중국의 XuetangX와 같은 플랫폼에서도 수백만명의 사용자가 수천 개의 강의를 수강하고 있습니다. 그러나 MOOCs의 학생 수가 계속 증가하고 있음에도 전체 강의 완료율은 5% 미만입니다. 따라서 학생들의 관심을 더 잘 이해하고 포착하는 것이 필요합니다. MOOCs 플랫폼에서 학생들의 관심을 이해하고 포착하기 위한 다양한 노력이 있었으며, 이 중에서도 추천 시스템은 강의를 학생들에게 추천하기 위해 MOOCs에 대한 연구들이 진행 되어왔습니다, 그러나 해당 데이터에 포함되는 강의데이터는 여러 비디오 강의로 구성되며, 각각은 특정 지식 개념을 다룹니다. 이로 인해 직접적인 강의 추천은 학생들이 수강하는 비디오를 이해하지 못하여 특정 지식 개념에 대한 관심을 간과하게 됩니다. 이처럼 많은 타입의 노드를 고려하지 못한 문제점이 있었습니다.

또한, 기존의 추천 전략인 협업 필터링(CF)은 사용자의 이력을 기반으로 추천을 제공하는데 성공을 거두었습니다. 그러나 CF 기반 방법은 사용자-항목 간의 희소성 문제로 인해 추천 성능에 제한이 있습니다. 이 문제를 해결하기 위해, 본 연구에서는 다양한 타입의 엔터티와 그들 사이의 관계를 활용하는 방식을 제안합니다. 이러한 관계는 추천 시스템에 다양한 이점을 제공합니다.

본 연구에서 사용되는 데이터셋과 각 데이터셋 사이의 연결관계는 다음과 같이 나타납니다.

본 데이터의 엔티티는 표 1에 나타납니다. 지식 개념, 비디오, 강좌 , 강사, 사용자으로 구분이 되며 각 entities의 관계를 통해 Heterogeneous graph를 구성합니다. 이 연구의 주요 기여는 다음과 같습니다:

지식 개념 추천이라는 중요한 문제를 파악하였으며, 기존의 MOOCs 추천 시스템에서 고려하지 못한 Heteroginety 부분을 해결합니다. 다양한 이종 컨텍스트 부가 정보를 활용하여 지식 개념 추천을 도와주는 새로운 프레임워크인 ACKRec를 제안합니다. MOOCs 플랫폼에서 다양한 엔터티 간의 복잡한 상호 작용을 포착하기 위해 이종 정보 네트워크 모델링을 개발하였습니다.

PROBLEM STATEMENT AND SYSTEM ARCHITECTURE

2.1 Problem Statement

MOOCs에서 대상 사용자와 관련된 상호 작용 데이터가 주어졌을 때, 사용자와 일련의 지식 개념에 대한 관심 점수를 계산하고 지식 개념의 상위 N 목록을 추천하는 것이 목표입니다. 보다 형식적으로, 사용자 $u$의 상호 작용 데이터가 주어졌을 때, 예측 함수 $f$는 추천 지식 개념 목록 $K$ (예: “c++”, “binary tree”, “linked list” 등)를 생성하는 데 사용되며, $f : u \rightarrow {ki \vert ki \in K, i < N}$.

2.2 System Architecture

제안된 지식 개념 추천 시스템, ACKRec의 구조는 그림 2에 나와 있습니다. 이는 다음과 같은 구성 요소로 이루어져 있습니다:

• Feature Extraction: MOOCs에서 수집한 데이터를 사용하여 지식 개념의 이름에서 콘텐츠 정보를 콘텐츠 특징으로 추출하고, 지식 개념을 설명하기 위해 다양한 유형의 엔터티(예: 지식 개념, 비디오, 강좌) 간의 다양한 관계(예: 개념-비디오 및 개념-강좌 관계)를 분석합니다. 마찬가지로 사용자에 대한 개념 특징과 컨텍스트 특징도 생성됩니다.

• Meta-path Selection: 데이터에서 추출한 특징을 기반으로, 이 모듈에서는 다양한 유형의 엔터티 간의 관계를 모델링하기 위해 구조적 HIN(Heterogeneous Imformation Network)을 구성하고, HIN에서 지식 개념들의 관련성을 나타내기 위해 다양한 메타 경로를 선택합니다.

• Representation Learning of Heterogeneous Entities: 이전 단계에서 구성된 메타 경로를 기반으로, 이종 관점에서 엔터티의 저차원 표현을 학습하는 모델이 제안됩니다. 이 모델은 Heterogeneous Entities 간의 구조적 상관관계를 포착할 수 있습니다.

• Rating Prediction: 사용자와 지식 개념의 저차원 표현을 생성한 후, 엔터티의 Dense 벡터는 확장된 행렬 분해에 공급되어 모델의 매개 변수를 학습합니다.

  3. Proposed Method

이 섹션에서는 생성된 콘텐츠 특징과 컨텍스트 특징을 기반으로 지식 개념과 사용자의 표현을 어떻게 학습하며, 학습된 표현을 기반으로 지식 개념 추천을 어떻게 수행하는지에 대한 세부 정보를 소개합니다.

3.1 Feature Extraction

3.1.1 Content Feature

지식 개념의 명칭은 대부분 지식 개념의 일반화(e.g., “c++,” “binary tree,” “linked list”)로서 풍부한 의미 정보를 포함하고 있습니다. 따라서 지식 개념의 이름의 단어 임베딩을 생성하고 지식 개념의 콘텐츠 특징으로 사용합니다. 특히, Word2vector를 사용하여 단어 임베딩을 생성합니다. 사용자 개념의 경우 사용자가 관측한 지식 개념의 정보를 함축하여 정의됩니다.

3.1.2 Context Feature

지식 개념 명칭의 단어 임베딩과 같은 콘텐츠 특징은 지식 개념의 정보를 나타내는 데 사용될 수 있습니다. 또한, 네트워크 구조 내의 다른 엔터티 간의 관계와 같은 풍부한 컨텍스트 정보가 존재합니다. 이러한 다양한 유형의 엔터티 간의 복잡한 관계를 포함하기 위해 컨텍스트 정보를 특징으로 모델링합니다.

3.2 Meta-path Based Relationship

다양한 유형의 엔터티와 그들 사이의 복잡한 관계를 적절하게 모델링하기 위해, 본 연구는 먼저 HIN을 사용하여 사용자, 지식 개념, 그리고 그들 사이의 이종 관계를 어떻게 묘사하는지 설명합니다.

• 정의 1.Heterogeneous information network (HIN):
  • HIN은 객체 세트 $ V $와 링크 세트 $ E $로 구성됩니다.
  • $ G = {V, E} $
  • HIN은 또한 객체 타입 매핑 함수 $ \phi : V \rightarrow N $ 및 링크 타입 매핑 함수 $ \varphi : E \rightarrow R $와 연관되어 있습니다. 여기서 $ N $과 $ R $은 사전에 정의된 객체 및 링크 유형의 집합을 나타냅니다.
• 정의 2. Network schema:
  • 네트워크 스키마는 $ S = (N, R) $로 나타낼 수 있습니다.
  • 이것은 정보 네트워크 $ G = {V, E} $의 메타 템플릿입니다.
  • 이 스키마는 object type mapping $ \phi : V \rightarrow N $ 및 link type mapping $ \varphi : E \rightarrow R $에 따라 정의된 객체 유형 $ N $ 위의 방향성 그래프입니다.
• 정의 3. Meta-path:
  • 메타 경로는 네트워크 스키마 $ S = (N, R) $에서 정의되며, $ N_1 R_1 \rightarrow N_2 R_2 \rightarrow \ldots R_l \rightarrow N_{l+1} $의 형태의 경로로 나타냅니다.
  • 이것은 객체 $ N_1 $과 $ N_{l+1} $ 사이의 복합 관계 $ R $를 설명하는 경로입니다.
  • Meta-path는 동일한 타입의 객체들사이의 연결 관계를 나타내고 있으며, 본 연구의 경우 user-course-user와 같이 user사이의 연결이 course에 의해 연결된 경우를 $MP_ {\vert course \vert}$와 같이 표현하고 있습니다.

이러한 정의와 구조를 통해 HIN의 중요성과 그것이 어떻게 다양한 엔터티 간의 관계를 모델링하는 데 사용되는지 이해할 수 있습니다.

3.3 Attention-based Graph Convolutional Networks for HIN Representation Learning

콘텐츠 특징과 컨텍스트 특징을 얻은 후, 본 연구는 엔터티 콘텐츠 특징을 graph neural network에 입력하여 잠재 엔터티 표현을 학습합니다.

• 네트워크 및 메타 경로 정의:
  • 다양한 정보 네트워크 $G = (V, E)$
  • 메타 경로 집합 $ MP = {MP_ 1, MP_ 2, … MP_ {\vert MP \vert}} $
  • 인접 행렬 $ A = {A_ 1, A_ 2, … A_ {\vert MP \vert}} $

메타 경로의 수는 $\vert MP \vert$로 표시됩니다. 본 연구는 다음의 계층별 전파 규칙을 가진 여러 계층의 graph neural network (GCN)를 채택합니다:

$ h^{(l+1)} = \sigma(P h^l W^l) $ 여기서, $ h^{(l+1)} $는 엔터티의 새로운 표현을 나타냅니다. 특히, $ h^0 $는 첫 번째 단계에서 추출한 콘텐츠 특징입니다.

• 정보 전파:
  • $ h_1 = \text{ReLU} ((P_0 X) W_0) $
  • $ h_2 = \text{ReLU} ((P_1 H_1) W_1) $
  • $ h_3 = \text{ReLU} ((P_2 H_2) W_2) $
  • $ e^{MP} = h_3 $

세 개의 전파 계층을 거쳐 각 메타 경로에 대한 표현을 학습합니다. 그러나 다른 메타 경로들은 동등하게 고려되어서는 안됩니다. 이 문제를 해결하기 위해, 본 연구는 attention mechanism을 활용하여 다른 메타 경로의 안내 아래에서 학습된 엔터티의 표현을 aggregate하고 general representation을 생성합니다.

• attention mechanism:
  • $ e = \sum_ {i=1}^{\vert MP \vert} \text{att}(e^{MP_ i} \otimes e^{MP_ i}) $
  • $ \alpha^{MP_ i} = \frac{\exp(\sigma(a e^{MP_ i}))}{\sum_ {j \in \vert MP \vert} \exp(\sigma(a e^{MP_ j}))} $
  • 최종 표현: $ e = \sum_ {i=1}^{\vert MP \vert} \alpha^{MP_ i} e^{MP_ i} $

이 알고리즘은 다양한 메타 경로의 상관 관계를 활용하여 엔터티 표현을 학습하도록 허용합니다.

3.4 Matrix Factorization for Knowledge Concept Recommendation

지금까지 사용자와 지식 개념의 콘텐츠 특징 및 컨텍스트 특징을 추출하는 방법을 학습했습니다. Attention mechanism GCN을 사용한 표현 학습을 통해 지식 개념의 표현 $ e_k $와 사용자의 표현 $ e_u $를 얻을 수 있습니다. 이 부분에서는 확장된 행렬 인수분해 (MF) 기반 방법을 사용하여 사용자에게 지식 개념 추천을 수행하려고 합니다.

• 사용자가 지식 개념을 클릭하는 횟수를 평가 행렬로 간주합니다.
• 사용자가 지식 개념에 대한 평가는 다음과 같이 정의됩니다: $r_ {u,k} = x_ u^T y_ k$
  • 여기서 $ x_ u $는 사용자의 잠재 요인을 나타내고, $ y_ k $는 지식 개념의 잠재 요인을 나타냅니다. $ D $는 잠재 요인의 수입니다. $r_ {u,k}$는 사용자와 지식 개념사이의 predict rating을 나타내주고 있습니다.
• 사용자 $ u $와 지식 개념 $ k $에 대한 표현을 얻었으므로, 다음과 같이 classifier의 input으로 넣습니다.: $ r_ {u,k} = x_ u^T y_ k + \beta_u \cdot e_ u^T t_ k + \beta_ k \cdot t_ u^T e_ k $
  • $ e_ u $와 $ e_ k $는 사용자와 지식 개념의 표현입니다. $ t_ k, t_ u $는 학습 가능한 파라미터 이며, $ e_ k, e_ u $ 는 사용자와 지식 개념을 표현하는 vector입니다.

• MF의 목적 함수는 다음과 같이 정의됩니다: $ \min_ {U,K} \frac{1}{m \times n} \sum_ {u=1}^n \sum_ {k=1}^m (r_ {u,k} - r_ {u,k})^2 $

• regularization term 을 추가하여 함수를 다시 정의하면, 최종 목적 함수는 다음과 같이 표현됩니다: $ \min_ {U,K} \frac{1}{m \times n} \sum_ {u=1}^n \sum_ {k=1}^m (r_ {u,k} -r_ {u,k})^2 + \lambda (||x_u||^2 + ||y_k||^2 + ||t_u||^2 + ||t_k||^2) $

이 최적화 문제는 probability gradienct desecnt을 사용하여 최적화됩니다.

4. EXPERIMENT

4.1 Dataset

• 본 연구는 XuetanX MOOC 플랫폼에서 실제 데이터를 수집했습니다.
• 2016년 10월 1일부터 2017년 12월 30일까지의 등록된 학습 데이터를 훈련 세트로, 2018년 1월 1일부터 2018년 3월 31일까지의 등록된 학습 데이터를 테스트 세트로 선택했습니다.
• 훈련 데이터의 각 시퀀스에서 마지막으로 클릭된 지식 개념을 대상으로 취급하고 나머지를 과거 행동으로 취급합니다.
• 각 positive sample 대해 목표 지식 개념을 대체하기 위해 하나의 negative sample(값이 0)를 무작위로 생성합니다.

4.2 Evaluation Metri

• 모든 방법을 널리 사용되는 지표를 사용하여 평가하였습니다: 상위 K 항목의 히트 비율(HR@K) 및 상위 K 항목의 NDCG(NDCG@K).
• HR@K는 상위 K 항목에서 성공적으로 추천된 실제 인스턴스의 백분율을 측정하는 리콜 기반 지표입니다.
• NDCG@K는 실제 인스턴스의 예측된 위치를 고려하는 정밀도 기반 지표입니다.
• 또한 평균 역순 순위(MRR)를 사용합니다. 큰 MRR 값은 모델의 성능이 더 좋다는 것을 나타냅니다.
• 추가로 ROC의 곡선 아래 영역(AUC)도 지표로 추가했습니다.

4.3 Detailed Analysis of the Proposed Approach

4.3.1 Evaluation of Different Meta-paths Combination.

• 이 실험에서는 ACKRec의 성능에 어떻게 메타 경로 조합 선택이 영향을 미치는지 분석합니다.
• 단일 메타 경로와 그 조합을 모두 고려합니다. -. 표 3에서 각 단일 메타 경로 (예: MP1, MP2, MP3, MP4)는 다른 성능을 보이며, 단일 메타 경로의 조합도 같은 경향을 따릅니다.
• 더 많은 메타 경로를 포함하는 조합이 더 나은 성능을 보이며, 모든 네 메타 경로를 결합함으로써 최상의 성능을 달성합니다.

4.3.2 Evaluation of Model Parameters

• 행렬 인수 분해 기반 방법에서 잠재 요인의 수는 중요한 매개 변수입니다.
• 그림 4에서 HR@K, NDCG@K, MRR, AUC 지표를 사용하여 ACKRec의 성능이 잠재 요인의 수 변화에 따라 어떻게 변하는지 보여줍니다.

• 표 4에서 볼 수 있듯이, HIN 기반 방법들은 다른 모든 방법들보다 더 우수한 성능을 보입니다. 이것은 MOOCs 데이터의 이질성의 중요성을 나타냅니다. 또한 결과는 ACKRecs+r, 콘텐츠 특징과 컨텍스트 특징을 통합하는 것이 최상의 성능을 보인다는 것을 보여줍니다.

• 10에서 40까지 10씩 증가하는 수를 조정합니다. 성능 증가가 잠재 요인의 수가 증가함에 따라 평평해진 것을 볼 수 있습니다.
• 30개의 잠재 요인을 사용하면 최적의 성능을 얻을 수 있습니다.
• 잠재 요인의 수를 30으로 설정한 후, 엔터티 표현의 차원 설정을 시도합니다.
• 결과는 그림 5에 나와 있습니다. 본 연구는 다양한 차원 수 (예: 20, 50, 100, 150, 200)를 사용하여 실험을 수행하고, 100에서 최적의 성능을 달성하는 것을 발견했습니다.

• 결과는 또한 제안된 모델의 성능이 GCN 계층 수에 따라 어떻게 변하는지 보여줍니다. 그림 6에서 본 연구는 확실히 제안된 모델의 성능이 다른 계층 수 (예: 1, 2, 3, 4)와 함께 변하는 것을 볼 수 있습니다.

  4.4 Baseline Methods

제안된 접근법의 성능을 평가하기 위해, 다음과 같은 다양한 기본 방법들을 고려합니다:

ACKRech

• 설명: ACKRec의 변형으로, 복잡한 정보 네트워크 내의 엔터티들의 다양성을 무시합니다.
• 특징: 관계 행렬을 재생성하여 다른 엔터티들 간의 관계를 나타냅니다.

ACKRecc

• 설명: attention mechanism이 없는 ACKRec의 변형입니다.
• 특징: 서로 다른 메타-경로를 연결(concatenate)합니다.

ACKRecr

• 설명: MOOCs 내의 엔터티들의 문맥 특징을 사용한 ACKRec 기반의 모델입니다.
• 특징: ACKRecs 모델과 유사하게, 엔터티의 문맥 특징을 이 모델에 입력합니다.

ACKRecs+r

• 설명: 제안된 방법으로, HIN 내의 엔터티들을 최대로 묘사하기 위해 이질적인 문맥 특징과 내용 특징을 결합합니다.

모든 baseline 대비 본 논문이 제안하는 ACKRec의 성능이 가장 높게 나옵니다.

4.5 Case Study

이 부분에서는 제안된 방법 ACKRec의 효과성을 보여주기 위해 한 가지 사례를 수행합니다. 본 연구는 무작위로 학생: 2481307을 선택하고, 단일 메타 경로 MP2와 결합된 메타 경로 MP1-MP2-MP3-MP4를 기반으로 두 개의 상위 10 추천 목록을 각각 얻습니다.

5 CONCLUSION

이 연구에서는 MOOCs 시스템에서의 지식 개념 추천 문제를 조사합니다. 이 문제는 대부분의 MOOCs 추천 시스템에서 놓치곤 합니다. 본 연구는 ACKRec를 제안하며, 이는 다양한 이질적 컨텍스트 부가 정보를 자연스럽게 지식 개념 추천에 통합하는 그래프 신경망 기반 접근법입니다. 보다 자연스럽고 직관적인 방식으로 풍부한 컨텍스트 정보를 활용하기 위해, 본 연구는 MOOCs를 이질적 정보 네트워크로 모델링합니다.

본 연구는 attention graph neural network를 설계하여 meta-paht에 따라 어떤 path가 중요한지 attention mechanism을 통해 컨텍스트 정보를 전파함으로써 다양한 엔터티의 표현을 학습합니다. 본 연구에서 제안된 graph neural network은 데이터의 이질적 정보를 파악할 수 있으먀, 사용자의 잠재적 관심사를 효과적으로 포착할 수 있으며, aggregate될 수 있습니다.

6 Future work

본 연구는 몇가지 한계점이 존재 합니다.

1. meta-path를 생성할 때, 타겟이 되는 노드의 유형을 제외한 다양한 노드 유형이 중간 노드에 위치하게 됩니다. 하지만, 해당 노드 유형을 가지고 meta-path를 분류하는데 이떄 해당 중간 노드의 feature는 전혀고려하지 못한채 노드의 유형으로 path가 연결이 결정 됩니다. 이 연구은 detail한 중간 노드를 놓치며, 타켓 노드 사이의 연결성을 제대로 표현 할 수 없다는 한계점이 존재합니다.

2. 모든 meta-path들은 사전에 노드 사이의 연결성을 알고 있어야하며, 어떤 노드들이 연결될 수 있는지에 대한 도메인 지식이 필요하게 됩니다. 이는 매우 휴리스틱한 방법이며, 실제 이런 중간 노드들의 역할이 타당한지는 밝혀지지 않았습니다. 또한, 특정 데이터에만 적용이 가능하며 매우 비효울적인 방법입니다. 따라서 meta-path를 automatic하게 추출하는 방법을 연구한다면, 이질적 그래프를 일반화된 방법으로 해결 할 수 있을 것입니다.

Author Information

• 김종우(20224386)
• Graduate School of Data Science
• Graph mining, Recommendation system