ok-lab

Contents 이번 글은 CS224W의 Lecture 5.1 에 대한 내용을 다루고 있다. 해당 챕터에서는 Message Passing과 Node Classification에 대한 내용을 포함하고 있다. 일반적으로 Semi-Supervised Learning을 할 때 사용하며, 일부 노드의 label에 대한 정보가 주어졌을 때, 모든 노드에 label을 부여하는 방법에 대해서 다룬다. Massage Passing은 Node Classification을 하는 방법 중 하나이며, 그 중 Relational Classification, Iterative Classification, Belief Propagation에 대해서 알아보자. Node Classification Node Classification은 ..

Contents Lecture 4 에서는 그래프 분석과 학습하는 방식을 행렬 관점으로 접근한다. 이번 글에서는 그 중 PageRank에 대해서 먼저 알아볼 것이며, PageRank는 이전 강의에서 다룬 Random Walk 방식을 사용하여 node의 중요도를 파악하는 방식이다. PageRank PageRank는 Stanford 대학의 박사 두 분이 만든 모델이다. PageRank에서의 Node는 web page를 의미하고, Edge는 hyperlinks를 의미한다. web에 방문하여 hyperlink를 클릭해 다른 web page로 이동하는 경우를 그래프로 표현한 것이며, 방향성을 가지는 directed graph를 뜻한다. 논문에서 citation을 달아 놓은 경우 논문에서 link를 클릭해 다른 논문..

Contents Embedding Entrie Graphs Approach 1 본 강의에서는 node embedding이 아닌 entire graph를 embedding 하는 방법에 대해서 다룬다. graph embedding은 subgraph나 전체 entire graph를 embedding하는 것이 목표라고 할 수 있다. 이때 $z_G$는 graph embedding을 의미하며, toxic molecules와 non-toxic molecule를 구분하거나, 비정상적인 graph를 식별하는 것에 활용할 수 있다. 가장 간단한 아이디어는 graph에 속한 node embedding을 합하거나 평균을 취하는 것으로도 가능하다. \[ z_G = \sum_{v \in G} z_v \] Approach 2 다음..

Contents 본 강의는 Lecture 3.1로 Node Embedding에 대해서 다룬다. 일단 먼저 Embedding이라는 단어가 무엇인지 알고 있어야 한다. 자연어처리(NLP)에서는 단어를 One-hot Encoding으로 혹은 Look-up Table로 만든 후 Embedding을 진행한다. Embedding은 아무런 의미가 없는 데이터를 임의의 차원으로 보냄으로써 그 숫자 자체에 의미를 지닐 수 있도록 하는 개념으로 이해할 수 있다. Node Embedding도 비슷한 맥락으로 Embedding 값이 가지는 수치를 통해 Node의 특징(feature)을 파악할 수 있도록 하는 것이다. 본 강의에서는 Node Embedding을 하는 방법을 총 4가지 단계로 나누어서 언급한다. 1. Encode..

Contents 이전 챕터에서 Node-level, Link-level prediction에 대해서 다루어보았다. 이번 챕터에서는 마지막 남음 Graph-level prediction에 대해서 다루어본다. Graph-Level Features Kernel Methods Graph-level에서는 Graph kernel이라는 것을 사용하는데, 이는 전체 그래프 예측에 사용되는 kernel을 의미하며, 이를 통해 전체 그래프의 구조에 대한 특징을 추출하는 것을 목표로 한다. 기존의 노드 혹은 링크에서는 각 노드들의 feature vector를 생성하였으나, Graph-level에서는 feature vector 대신에 kernel을 디자인하는 것이 가장 큰 차이점이다. kernel $K(G, G') \in \..

Contents 이전 단계에서는 Node-Level prediction에 대한 내용을 다루었다. 이번 Lecture에서는 Link-Level prediction에 대해서 다룬다. Link는 Edge라고도 부르며 혼용해서 부르니 참고하길 바란다. Link Prediction Task and Features Linke-Level Prediction이란, 이미 존재하는 링크(Link)를 기반으로 노드 $A$와 노드 $B$ 간의 새로운 링크를 예측하는 것이다. 아래의 그림을 살펴보면 노드 $A$와 노드 $B$는 연결되어 있지 않지만, 연결될 가능성을 예측하는 등의 문제를 의미한다. 실제 테스트하는 단계에서는 모든 노드 쌍에 대해 순위가 매겨지고 top-K를 예측하는 형태로 진행된다. 이때 가장 핵심은 노드 쌍에..

Contents 이전 Lecture에서 Node Level, Link Level, Graph Level을 활용한 케이스에 대해서 다루어 보았다. 이번 Lecture에서는 각각의 Level에서의 Prediction 방법에 대해서 다루고 있다. 각각의 Level에 대해서 Prediction을 하기 위해서는 일단 먼저 Node, Link, Graph 등의 feature를 생성하는 것부터 시작이다. 이번 Lecture에서는 전통적인 ML Pipeline을 구축해 Graph를 구축하고 있다. 전통적인 ML은 2 단계로 구성 되어 있다. 첫번째 단계는 먼저 Node, Link, Graph의 feature를 vector 형태로 가져오는 것이다. 그 후 Random forest, SVM, Feed Forward Neu..

Contents Lecture 1.3에서는 Graph Representation를 고르는 방법에 대해서 다룬다. 먼저 Graph Representation을 알기 전 Graph의 구성에 대해서 먼저 알아보자. 그래프는 Nodes, Vertice로 불리는 Objects와 Links, Edges로 불리는 Interactions, 그리고 Network, Graph로 불리는 System로 구성되어 있다. Node로 표현할 경우 $N$, Vertices로 표현할 경우 $V$로 표기한다. Interaction의 경우 주로 Edge로 표현하며 $E$로 표기하고 System은 $G(N,E)$로 표기한다. Graph는 일반적으로 사용자와 사용자 간의 관계를 표현할 때 사용하거나 프로틴(Protein)과 같은 분자 구조를..

Contents 이번 장에서는 그래프 관련 연구의 응용에 대해서 다룬다. 그래프를 사용하는 연구들의 종류는 다음과 같다. Node Classification : 노드의 속성을 예측하는 것 (Categorize online users / items Link Prediction : 두 노드 사이에 놓친 링크가 존재하는지 예측하는 것 (Knowledge graph completion) Graph Classification : 서로 다른 그래프를 분류하는 것 (Molecule property prediction) Clustering : 노드 간의 관계를 Detect하는 것 (Social circle detection) 추가로 새로운 원자 구조를 생성할 때 사용하는 Graph Generation과 물리적인 현상을..