• 기존 그래프에 기반하지 않은 대부분의 모델에서 사용된 데이터(시계열 데이터, 음성, 이미지)는 유클리드 공간 위에 정의된 데이터였다. 어떤 수식을 통해 데이터간 거리와 데이터간 유사도를 연계해 예측값을 추론해 나갔다.
• 기술과 통신의 발전으로 쌓이는 데이터의 볼륨이 커짐에 따라 그렇게 지엽적인 시각으로 데이터를 다루는 것을 넘어서, 데이터가 가진 구조적인 정보(복잡하고 다양한 관계 정보)에 대한 피쳐들을 모델에 어떻게 반영 할 것 인가에 대한 고민과 연구가 이어지고 있다.

graph

• 그래프는 앞서 소개한 비유클리드 데이터의 표현이다.

Heterogeneous Information Network

• RS 분야에서 주로 활용하게 되는 그래프.
• 이질적인(Heterogeneous), 즉 여러 종류의 노드로 구성된 그래프.
• 같은 노드들 간에 다양한 관계를 가질 수 있다.
• 노드간의 관계를 통해 새로운 정보를 추출 할 수 있다.
  예를들어, (m-a-m) 보다 (m-d-m)의 관계를 갖는 영화(m) 간 유사도를 더 높게 반영 할 수 있다. (배우보다는 감독이 같을 때 영화의 유사도가 높다는 가정 하에)
• 다양한 type의 노드와 관계를 이용해 이웃(neighbor)의 정의를 다양화 할 수 있다. 이에 따라 모델 성능 개선을 이룰 수 있다.
• Heterogeneous한 node 정보를 반영하기 위해 노드 타입에 따라 embedding되는 space를 다르게 가져간다.
  : TransR Embedding 방법론

Knowledge Graph

• Knowledge Graph가 바로 Heterogeneous Network의 한 종류
• Node == entity (Node는 type으로 label됨)
  Edge == relationship (type이 존재함)
  KG는 heterogeneous graph의 하나의 종류

graph based learning

• 비유클리드 데이터는 기존의 유클리드 데이터와 완전히 다른 특성들을 갖고 있으며 부가적인 관계 정보를 모델에 반영해야 하기에, graph에 기존 학습 기법들을 적용하기 쉽지않다.
• 그렇기에 graph의 데이터의 복잡성과 가지고 있는 정보를 반영하는 graph만의 Embedding 과정을 통해 학습을 위한 representation learning을 진행.
• node embedding (graph embedding)
  : 그래프의 요소(노드, 링크, 그래프)를 입력으로 하여 임의의 d차원 벡터로 변환시키는 작업.
• GNN
  : 입력 그래프에 대한 사전 지식이 필요한 기존 그래프 탐색(DFS, BFS, Dijkstra)와 달리, 그래프에 직접 신경망을 적용하여 그래프 레벨에서의 예측을 진행하는 모델. 정보를 보존하며 차원을 줄여 표현 하는 것 자체를 목표로 하는 Embedding 모델과 달리 GNN모델은 그래프 자체를 통해 학습 및 예측 동작을 진행.
  1)graph 자체의 구조적 정보와 2)각 노드 별 정보를 내포 하면서, 그래프 자체의 관계와 노드 정보를 기반으로 학습하게 된다.
• GCN
  : graph에 CNN의 Convolution 개념을 적용한 것.

node embedding 기법

• 인접성 기반 접근법

• 거리 기반 접근법

• NGCF에서 적용

• 중첩 기반 접근법

• 경로 기반 접근법

• Random walk(임의보행) 기반 접근법
  • Deep walk / Node2Vec
  • Metapath2Vec

deepwalk

• RandomWalk 기반한 임베딩 기법.

  RandomWalk

  -walk : sequential 한 path (node의 순서열)
  : 특정 노드에서 임의로 k번 이동하는 sequential한 path를 기록한 data를 뽑는 방법. 이 임의의 path에 어떤 두 node가 함께 등장할 확률을 통해 두 node의 유사도를 측정할 수 있다.: (6step인 path) windowsize가 6인 walk를 random하게 3개 뽑은 예시

• NLP분야의 skip-gram에서 주변 단어 학습을 통한 유사도를 바탕으로 주변 단어를 예측했 던 것 처럼,
  deepwalk는 그래프에서 walk(sequential path) 내 도달 가능한 node 학습을 통해 node간의 연결성 정보를 embedding 합니다.

• (nlp)skip-gram - deepwalk
  문서 - 그래프
  이웃한 단어 - walk내에 도달 가능한 node
  단어 - node

• skip-gram에서 one-hot 이었던 input 대신 PPMI 전처리 data를 사용

• word2Vec은 문장에서 이웃에 해당되는 주변 단어의 범위가 window size였다면
  DeepWalk는 path에서 node들의 범위(walk에서 이동 step 수)가 window size

  input

  -인접한 node 정보가 포함된 정규화 matrix를 k제곱 함으로써, distance(step)가 k인 path로 도달할 수 있는지 연결성 여부가 표현된다. 즉 k step으로 구성된 walk에 대한 목적지가 될 node를 표현한 데이터.
  -windowsize인 k step까지 각 step에 대한 데이터를 시그마, 평균 낸 가중치 데이터를 생성한다.
  -PPMI 정규화를 적용해준다.
  (PMI의 음의 발산을 방지하기 위해 음수일 때 0으로 취급 : PPMI)
  : 그래프에서 노드 간 연결성에 대한 정보

• deepwalk의 한계점
  : Node가 똑같다는 가정하에 출발, 즉 Homogenous network 학습
  → Node type 별 고유한 특성 정보 손실

metapath2Vec

• 목적 : node 종류에 따른 고유한 정보를 통해 다른 relation 찾자.
• random walk 방법론에 기반하여 학습할 임의의 path들을 생성하는 대신,
  node의 종류에 따른 관계의 고유한 정보를 반영하는 적절한 path만 학습한다.
  
• 그렇기에 고유한 관계 정보를 가지는 metapath정보를 사전에 설정해야 한다는 한계가 있다.

metapath2Vec++

• 각 node type 마다 별도의 space에서 embedding을 생성.
  ( : 다른 type의 node → 다른 space에 Embedding)
• node type 같으면 곱연산, node type 다르면 합연산
• metapath2Vec과 달리 negative sampling 과정에서 negative sample을 생성 할 때 metapath에 해당하는 node type으로만 negative sample을 구성.

negative sampling

: 기본적인 skip-gram에서는 중심노드에 대한 이웃노드의 확률을 높여간 것에 비해, negative sampling을 이용한 skip-gram은 라벨 1이 주어진 중심노드-주변노드 쌍과 더불어, 라벨 0이 주어진 임의의 negative 노드 쌍을 생성해 함께 학습한다.
softmax 예측값이 0으로 수렴해야 하는 negative 샘플이 학습 데이터로 추가되어 학습의 효율성을 증대되는 것.

Conclusion

• sparse data에서는, neighbor node의 등장 빈도 정보보다 metapath의 특정한 관계 정보가 모델 성능 향상에 효과가 좋다.
  : 적은 data에서 어떤 node간 (유사도)관계의 등장 횟수는 bias일 수 있기 때문에.

참고
- http://dsba.korea.ac.kr/seminar/?mod=document&uid=387
- GNN
https://thejb.ai/comprehensive-gnns-1/
- 노드 임베딩
https://velog.io/@tobigsgnn1415/Node-Embeddings
https://velog.io/@dldydldy75/Node-Embedding-정점-표현#deepwalk-와-node2vec
https://velog.io/@tjdqja2712/10.-Knowledge-Graph-Embeddings
- Negative Sampling
https://wikidocs.net/69141
- metapath2vec
https://greeksharifa.github.io/machine_learning/2021/12/11/metapath2vec/