Homophily : 동종 선호, 그래프 내에서 자신과 유사한 개체들이 서로 연결되는 특성
그래프 데이터의 이해
그래프 데이터란?
모든 관계를 그래프로 나타낼 수 있음.
구조 표현의 유연성/확장성 : 개체 간의 복잡한 관계와 의존성 정보를 자연스럽게 포착함. 어떠한 관계도 노드와 그들의 연결 정보(엣지)가 있다면 그래프로 표현할 수 있음
관계의 활용 : 연결 관계에서 정보를 추출한다는 점에서 기존의 분석 방법으로 찾을 수 없던 패턴을 발견할 수 있음
관련 용어
노드 : 정점
셀프 노드 : 본인의 노드와 연결되어 있는 노드
엣지 : 노드를 연결
인접행렬 : 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬
인접행렬의 특징
정사각행렬 : 인접행렬은 N*N의 정사각형 행렬의 형태를 띔
대칭성 : 주대각성분에 대해 대칭을 띔 A[i][j]=A[j][i]
희소성 : 대부분의 그래프의 경우 희소한 수의 행렬 성분을 포함
차수 : 노드에 연결된 엣지의 수
그래프의 종류
유방향 그래프/무방향 그래프 : 양쪽 연결 / 양방향이 아닌 한쪽 방향만 연결
비가중 그래프 / 가중 그래프 : 연결 사이의 가중치 유무
동종 그래프(Homogeneous Graph) : 모든 노드와 엣지가 같은 종류를 가지는 그래프 ex) 소셜 네트워크
이종 그래프(Heterogeneous Graph) : 노드와 엣지의 종류가 다양한 그래프 ex) 이커머스 내에서 유저와 아이템의 그래프
이분형 그래프(Bipartite Graph) : 노드를 두 종류의 분리된 집합으로 나눌 수 있는 그래프, 집합 내의 연결은 없고 집합 간의 연결만 존재, 이종 그래프의 일종이며 추천 시스템 내의 구성을 위와 같은 그래프 형태로 표현 ex) 클릭, 장바구니 여부 등
그래프가 어려운 이유
비-유클리드 공간 : 지금껏 머신러닝 방법론은 유클리드 공간에서 정의되는 데이터를 대상으로 연구했으나, 비유클리드 공간에서 그래프 데이터를 분석하기에 적합하지 않음
네트워크의 복잡성 : 수천, 수십억개의 노드와 엣지로 구성된 네트워크를 직관적으로 이해하고 분석하기 어려움
그래프 어플리케이션
그래프로 풀 수 있는 문제들
그래프 분류 : 특정 그래프가 어떤 그래프인지 분류
링크 예측 : 노드와 노드 사이에 연결이 있는지를 예측
커뮤니티 감지 : 연결 패턴 드의 정보로부터 유의미한 군집이 있는지 발견
-> graph classificaiton, node classification, link prediction, community detection, graph embedding, graph generation
추천 이외에도 다양한 분야에서 graph 기반 머신러닝 모델이 사용됨
신약 개발, 추천시스템, 이미지/텍스트 분석, 교통 예측, 3D mesh, 시뮬레이션 등
소셜미디어, 상품 추천 등 추천시스템의 각 요소를 그래프로 나타내고, Link prediction 형태로 문제를 정의할 수 있음.
multi-hop 관계를 통해 Collaborative Signal을 자연스럽게 잡아낼 수 있음.
피처와 아이템의 관계를 잘 녹여 설명할 수 있음.
networkx 패키지로 구현 가능함.
PageRank
그래프 구조를 활용해 웹 페이지의 중요도를 측정하는 알고리즘
구글 검색 결과 랭킹에 활용됨. -> 중요한 페이지일수록 상단에 노출됨.
Web As a Graph
다른 페이지에서 많이 참조된 링크 페이지는 중요한 페이지일 것이라 가정
웹을 유방향 그래프로 바라보자 -> 노드 : 웹페이지, 엣지 : 하이퍼링크
랜덤 워크(Random Walk)의 직관
PageRank : link를 따라 그래프를 떠돌아 다니는 서퍼가 각 노드에 머물 확률
순간 멈췄을 때 이 서퍼가 멈춰있을 확률이 PageRank
중요한 노드일수록 머물러 있을 확률이 높을 것
The Flow Model
링크가 많이 참조된 페이지는 중요한 페이지
중요한 페이지의 투표는 더 많은 가치를 가짐 -> 각 링크의 투표는 소스의 중요도에 비례함.
페이지 중요도 r_i가 있는 페이지 i에 d_i개의 아웃링크가 있는 경우 각 링크는 r_i/d_i의 투표를 보냄.
확률적 인접행렬을 만듦.
PageRank Score 계산 - Power Iteration
Power Iteration을 통해 수렴된 PageRank 값을 구하기 위해 확률 행렬 M을 R 벡터가 수렴값에 도달할 때까지 반복
문제점 1 - spider trap
들어오는 엣지는 있지만 나가는 엣지가 없는 경우 a->b<->c
이 경우, Power Iteration을 수행해도 수렴하지 못하고 진동 발산함.
문제점 2 - Dead End
들어오는 엣지는 존재하나 나가는 엣지가 없는 경우 a->b
이 경우 page rank 값이 0으로 수렴하게 됨.
해결책 - Random Teleport
매 스탭마다 특정 확률 alpha를 따라 아무 노드로 순간 이동함.
이 방법을 통해 두 문제를 해결 가능함.
추천을 위한 PageRank 변형
추천에서의 Bipartite Graph 예시
특정 아이템을 구매한 사용자에게 PageRank 알고리즘으로 상품을 추천하고자 함.
Bipartite Graph 내에서 teleportation vector를 관심 타겟 유저/아이템에게 one-hot에 가깝게 세팅
이 상황에서의 PageRank Sccore는 타겟 유저/아이템 관점에서의 노드별 중요도를 나타내게 됨.
Graph Neural Network (GNN)
기존 ML 알고리즘을 그래프에 적용하기 힘든 이유
입력형태 : 기존 ML 알고리즘은 입력을 tabular 혹은 image처럼 정해진 형태로 받아들임. 그러나 그래프는 이러한 형태를 그대로 사용하기 어려움. 인접행렬을 그대로 사용하는 것은 연산적으로 불가능에 가까움.
permutation invariant : 같은 그래프를 다른 형태로 입력했을 때 기존의 ML 모델에서는 다른 결과 값을 뱉어내게 됨.
노드, 벡터로 만들어보자
분류, 예측 등 원하는 task를 수행하기 위해 노드를 수치 벡터로 표현해야 함.
연결 관계를 반영하기 위해 인접행렬을 사용할 수 있으나, 실제 computation에서 전체 인접행렬을 사용할 수 없거나 비효율적인 경우가 많음.
따라서 이러한 정보를 압축한 latent feature로 나타내는 것이 필요함.
어떻게 노드를 벡터로 만들까?
인코더 정의 : 각 노드를 저차원 벡터로 임베딩하는 방법 결정
유사도 정의 : 의미상 비슷한 노드는 유사도가 높도록 유도하면서 학습. 유사도를 어떤 함수로 계산하느냐를 결정해야 함.
파라미터 최적화 : 파라미터를 최적화하면서 의미를 잘 보존한 벡터 표현을 생성함.
인코더 - shallow embedding
각 노드에 하나의 임베딩 벡터가 할당됨
위와 같은 테이블을 embedding lookup table이라고 부르는데, 각 노드에 해당하는 벡터를 lookup하듯이 지정해서 사용하기 때문
사용 방법론 : DeepWalk, Node2Vec 등
유사도 함수 정의
기존 그래프 네트워크 내에서 u와 v의 관계가 맵핑 이후의 벡터 공간 내에서의 관계와 유사하도록 하고 싶음
이 유사한 정도를 수치로 나타내는 디코더의 기능을 하는 것이 유사도 함수의 역할
다양한 함수를 적용할 수 있지만 내적이 가장 널리 사용되는 방식임.
Deepwalk
GCN
GraphSAGE
출처 : 패스트캠퍼스 - 30개 프로젝트로 끝내는 추천시스템 구현 강의