본문 바로가기
728x90

분류 전체보기

 (81)
[DGL] local_scope란? dgl 라이브러리를 사용한 그래프를 다루는 함수 중에서 with graph.local_scope() 라는 코드가 종종 보입니다! 이 코드는 무슨 역할을 해주는 코드일까요? dgl.DGLGraph.local_scope — DGL 0.7.2 documentation © Copyright 2018, DGL Team. Revision de0eb209. docs.dgl.ai 공식 문서를 참고 해보면 local_scope 내에서 그래프를 변형할 경우 실제 그래프에 반영이 되지 않는다고 합니다! 예시를 통해 한 번 살펴볼까요? 자, 다음과 같은 그래프가 있다고 가정해봅시다! >>> g = dgl.graph((torch.tensor([0, 1, 1]), torch.tensor([0, 0, 2]))) >>> g Grap..
[DGL] ndata, edata, srcdata, dstdata란? homogeneous graph(단순 노드, 엣지가 한가지 의미를 가지고 있는 그래프)에서 각 노드의 feature 정보를 표현하기 위해서는 ndata라는 속성을 이용하면 됩니다. 반대로 각 엣지의 feature 정보를 표현하기 위해서는 edata라는 속성이 있습니다. 예를 들어 인스타그램 팔로우 그래프를 만든다고 가정해봅시다. 아래 예시는 사용자는 총 6명이고, 각각의 팔로우 여부를 의미합니다. (*참고로 dgl에서 노드는 0번부터 연속적으로 생성이 됩니다. 중간에 비어있는 id도 노드가 생성이 됩니다.) >>> src_ids = torch.tensor([0, 2, 3, 2, 1]) >>> dst_ids = torch.tensor([2, 3, 1, 5, 4]) >>> g = dgl.graph((src_..
[DGL] Graph와 Heterogeneous Graph의 차이 그래프 데이터를 학습시키기 위해서는 데이터를 그래프 형태로 변형을 해주어야 합니다. GNN을 조금 더 쉽고, 편리하게 개발할 수 있도로 도와주는 라이브러리로 dgl(Deep Graph Library)가 존재합니다. DGL에서 만들 수 있는 그래프 객체의 종류는 크게 'heterograph'와 'graph' 두 가지가 있습니다. 1. graph (Homogeneous Graph) 그래프는 node와 edge의 종류가 한 가지인 것을 의미합니다. 예를 들어 페이스북 친구 관계를 그래프로 표현한다면 다음과 같을 것입니다. 노드는 사용자, 엣지는 친구 여부를 의미합니다. 즉, 노드와 엣지의 종류가 한가지라고 볼 수 있습니다. 만드는 방법도 간단합니다. 노드 source, 즉 어떤 노드에서 출발하여 노드 dest..
[그래프와 추천 시스템] 페이지 랭크 계산하기 페이지 랭크 계산하는 법 = "반복곱" 1. 각 웹 페이지 $i$의 페이지랭크 점수 $r^{(0)}_i$를 동일하게 $\frac{1}{웹 페이지의 수}$로 초기화 2. 아래 식을 통해 각 웹 페이지의 페이지 랭크 점수 갱신 $$ r_j = \sum_{i\in{N}_{in}(j)} \frac{r_i}{d_{out}(i)}$$ 3. 페이지 랭크 점수가 수렴하였으면 종료, 아니면 2번 반복 예시를 들어 살펴보겠습니다. 위 식을 사용하여 계산해보면 어렵지 않게 이해할 수 있습니다! 0 1 2 3 ... $r_y$ 1/3 1/3 5/12 9/24 ... 6/15 $r_a$ 1/3 3/6 1/3 11/24 ... 6/15 $r_m$ 1/3 1/6 3/12 1/6 ... 6/15 실제로 각 페이지의 랭크는 수렴하는 ..
[그래프와 추천 시스템] 페이지 랭크 페이지 랭크(Page Rank)란? 웹은 웹 페이지와 하이퍼링크로 구성된 방향성이 있는 그래프라고 볼 수 있습니다. 예를 들어, 네이버 -> 네이버 검색 -> 다른 사이트 -> ... 이런식으로 연결되어져있는 것이죠! 그렇다면 이런 웹 속에서 검색 엔진은 어떻게 만들어지는 것일까요? 구글 이전의 검색엔진 1. 웹을 거대한 디렉토리로 정리 - 웹 페이지 수가 증가함에 따라 수와 깊이가 무한정 커지는 문제점 - 카테고리의 구분이 모호하여 저장, 검색이 어려움 2. 웹페이지에 포함된 키워드에 의존한 검색 엔진 - 사용자가 입력한 키워드에 대해 해당 키워드를 여러 번 반복한 웹페이지 반환 - 악의적인 웹페이지에 취약 (임의로 특정 키워드 반복하여 사용) 그렇다면 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹..
[그래프와 추천 시스템] 그래프 패턴 - 다양한 그래프 패턴 연결성(Degree)이란? 정점과 연결된 간선의 개수를 의미합니다. 예를 들어 아래와 같은 그래프에서 A의 degree는 1, B의 degree는 3이라고 할 수 있습니다. 그러면 그래프 내에서 이러한 연결성(Degree)의 분포도는 어떨까요? 실제 그래프와 랜덤 그래프는 둘다 작은 세상 효과를 가지고 있습니다! (자세한 내용은 여기!) 그러나 연결성 분포는 전혀 다르게 나타납니다. 실제 그래프의 연결성 분포는 다음과 같이 두터운 꼬리(Heavy Tail)를 가지고 있습니다. 아래 예시와 같이 일반 사용자의 팔로워 수와 셀럽의 팔로워 수는 극단적으로 차이가 나므로 이런 식의 분포도를 가지게 됩니다. 그러나 랜덤 그래프는 일정 확률에 의해서 랜덤하게 생성이 되는 그래프이므로 연결성 분포가 다음과 같이 정규..
[그래프와 추천 시스템] 그래프 패턴 - 실제 그래프와 랜덤 그래프 실제 그래프(Real Graph)란? 다양항 복잡계로부터 얻어진 그래프를 의미 ex) 소셜 네트워크, 전자 상거래 거래 내역 등 랜덤 그래프(Random Graph)란? 확률적 과정을 통해 생성한 그래프를 의미 ex) 에르되스 - 레니 랜덤 그래프 (Erdos - Renyi Random Graph) - 임의의 두 정점 사이 간선의 존재 여부를 동일한 확률 분포로 형성 - $G(n, p)$ : n개의 정점을 가지고, 임의의 두 점 사이에 p의 확률로 간선 생성 그래프의 지름(Diameter)란? 그래프 내에 있는 정점 간 거리의 최댓값 작은 세상 효과(Small World Effect)란? 여섯 단계 분리 실험 (Six Degrees of Separation)이란 것이 있습니다. 아마 실험 내용은 다들 한..
[그래프와 추천 시스템] 그래프의 유형 및 분류 그래프의 유형 1. 방향이 없는 그래프 (Undirected Graph) 간선에 방향이 없는 그래프입니다. 예를 들면, 페이스북 친구 관계같은 것이 있습니다. 2. 방향이 있는 그래프 (Directed Graph) 간선에 방향이 있는 그래프입니다. 예를 들면, 인스타그램에서 팔로우, 팔로잉 같은 것이 있습니다. 방향이 있는 그래프에서는 나가는 이웃(Out-Neighbor)와 들어오는 이웃 (In-Neighbor)를 구별해주어야 합니다. 3. 가중치가 없는 그래프 (Unweighted Graph) 간선에 가중치가 없는 그래프입니다. 페이스북 친구 그래프 같은 경우 단순 친구인가의 여부만 있으니 딱히 가중치가 필요없습니다. 4. 가중치가 있는 그래프 (Weighed Graph) 간선에 가중치가 있는 그래프입..
728x90

티스토리툴바