인접성 기반 접근법
거리 기반 접근법
NGCF에서 적용
중첩 기반 접근법
경로 기반 접근법
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)
: 그래프에서 노드 간 연결성에 대한 정보
negative sampling
: 기본적인 skip-gram에서는 중심노드에 대한 이웃노드의 확률을 높여간 것에 비해, negative sampling을 이용한 skip-gram은 라벨 1이 주어진 중심노드-주변노드 쌍과 더불어, 라벨 0이 주어진 임의의 negative 노드 쌍을 생성해 함께 학습한다.
softmax 예측값이 0으로 수렴해야 하는 negative 샘플이 학습 데이터로 추가되어 학습의 효율성을 증대되는 것.
참고
- 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/