Graph 검색 결과
22 개의 검색 결과가 있습니다.
Machine Learning - Thoery/Graph Representation Learning

Graph isomorphism network 설명 (GIN 설명, GNN expressive power)

GIN은 graph isomorphism network의 줄임말로, WL test와 같은 강력한 expressive power를 가지고 있기 때문에 가장 널리 쓰이는 GNN 구조 중 하나이다. 이번 글에서는 GIN이 무엇인지와 함께 GNN의 expressive power가 어떻게 정의되는지에 대해서 알아보겠다. Motivation GIN의 motivation을 설명하기 위해서는 GNN의 expressive power가 무엇인지에 대한 정의가 필요하다. Message passing neural network (MPNN)의 정의에서 살펴보았듯이, GNN의 layer는 aggregate (message) function과 combine (update) function으로 구성된다. 이러한 aggregate와 ..

2023. 1. 29. 20:23
Machine Learning - Thoery/Graph Representation Learning

TransR knowledge graph embedding 설명 (TransR 설명)

TransR은 knowledge graph embedding 방법 중 하나로, projection matrix를 활용해서 head와 tail node embedding을 projection한 값 사이의 relation을 모델링하는 embedding 방법을 말한다. 이번 글에서는 RotatE, TransE에 이어, 새로운 knowledge graph embedding 방법인 TransR 방법에 대해 설명하겠다. Motivation TransE에서는 head embedding, tail embedding, relation embedding이 모두 같은 embedding 공간에 존재했다. 하지만 이러한 가정은 적절한 relation embedding을 찾는 것에 제약을 주었다. 그렇다면 head embeddi..

2022. 12. 17. 00:30
Machine Learning - Thoery/Graph Representation Learning

TransE knowledge graph embedding 설명 (TransE 설명)

TransE는 knowledge graph embedding 방법 중 하나로, head node embedding에 relation을 더했을 때 tail node embedding이 되도록 하는 embedding 방법을 말한다. 이번 글에서는 RotatE에 이어, 새로운 knowledge graph embedding 방법인 TransE 방법에 대해 설명하겠다. Method TransE는 아주 직관적인 knowledge graph embedding 방법이다. 간단하게 head node embedding에 relation을 더했을 때 tail node embedding이 되도록 하기 위해 학습을 한다고 생각하면 된다. 그러므로 TransE의 score function을 표현하면 다음과 같다. 이를 그림으로 ..

2022. 12. 3. 18:29
Machine Learning - Thoery/Graph Representation Learning

SELFIES 설명 (SELFIES와 SMILES, Self-referencing embedded strings 설명)

SELFIES는 self-referencing embedded strings의 줄임말로, SMILES, DeepSMILES가 가지고 있던 invalid 문제를 완벽하게 해결한, 분자 구조를 string 형태로 표현하는 방법이다. 이번 글에서는 SELFIES가 무엇인지에 대해 알아보겠다. * 이 글은 SMILES에 대한 기본적인 이해가 있다고 가정한다. Motivation SELFIES가 가지는 가장 큰 특징은 모든 SELFIES string이 100% valid한 molecule을 만들어낼 수 있다는 점이다. SMILES, DeepSMILES는 ring, branch의 표기법에서 오는 문제들 때문에 invalid한 molecule을 만들어내는 경우가 많았지만, SELFIES는 어떤 random한 stri..

2022. 11. 20. 16:41
Machine Learning - Thoery/Graph Representation Learning

DeepSMILES 설명 (DeepSMILES의 장단점, DeepSMILES: an adaptation of SMILES for use in machine-learning of chemical structures 논문 리뷰)

DeepSMILES는 분자 구조를 string 형태로 표기하는 표기법으로, SMILES가 ring과 branch에서 가지고 있는 invalidity 문제를 해결하기 위해서 제시된 방법이다. 이번 글에서는 DeepSMILES가 무엇인지에 대해 알아보겠다. * 이번 글은 SMILES에 대한 기본적인 이해가 있다고 가정한다. Motivation SMILES는 가장 기본적인 분자의 string 표기법으로 널리 사용되어 왔지만 여러 가지 한계점을 가진다. 그 중 대표적인 한계점이 ring을 한 쌍의 숫자로, branch를 한 쌍의 괄호로 표현하기 때문에 이러한 쌍이 만족되지 못하면 invalid한 string이 된다는 점이다. 예를 들어, C1CCC2라는 string이 있다고 하자. SMILES는 하나의 ring..

2022. 10. 19. 23:39
Machine Learning - Thoery/Graph Representation Learning

CharRNN 설명 (Generating Focused Molecule Libraries for Drug Discovery with Recurrent Neural Networks 논문 리뷰)

CharRNN은 SMILES와 LSTM을 활용한 graph generative model로, 각 character를 하나씩 generate하는 모델이다. 이번 글에서는 CharRNN이 무엇인지에 대해 Generating Focused Molecule Libraries for Drug Discovery with Recurrent Neural Networks 논문을 리뷰하면서 알아보겠다. Motivation 이 논문의 motivation은 아주 간단하다. NLP, image 등 다양한 분야에서 recurrent neural network (RNN)이 아주 잘 작동했기 때문에 이를 그래프에도 작동하면 잘 되지 않을까? 라는 생각에서 시작했다. 그래프에 RNN을 적용하기 위해서는 그래프가 sequence 형태로..

2022. 10. 3. 00:58
Machine Learning - Thoery/Graph Representation Learning

RotatE knowledge graph embedding 설명 (RotatE_Knowledge Graph Embedding by Relational Rotation in Complex Space 논문 리뷰)

Knowledge graph embedding은 연결되는 두 노드와 두 노드 사이의 관계를 적절하게 표현하여 head node의 embedding으로부터 어떤 relation을 취했을 때 이것이 tail node의 embedding과 비슷해지도록 만드는 것을 목적으로 한다. 이번 글에서는 knowledge graph embedding 중에서도 대표적인 네 개의 relation pattern을 모두 표현할 수 있는 방법인RotatE 방법에 대해 설명하겠다. Motivation 들어가기에 앞서, RotatE의 motivation에 대해 간단히 설명하겠다. 앞서 설명한 것처럼, knowledge graph embedding의 목적은 head node의 embedding에 어떤 relation을 취했을 때 이것..

2022. 10. 1. 22:12
Machine Learning - Thoery/Graph Representation Learning

Junction tree VAE 설명 (JT-VAE 설명, Junction Tree Variational Autoencoder for Molecular Graph Generation 논문 리뷰)

Junction tree VAE (JT-VAE)는 graph generative model의 하나로, 그래프를 원자가 아닌 조금 더 큰 단위의 scaffold로 쪼개서, tree 형태로 decomposition하여 이에 대해 VAE를 적용함으로써 그래프를 생성하는 모델을 말한다. 이번 글에서는 JT-VAE가 무엇인지에 대해서 Junction Tree Variational Autoencoder for Molecular Graph Generation 논문을 리뷰하면서 알아보겠다. 배경 우선, JT-VAE가 제안된 배경에 대해 먼저 살펴보겠다. 아래 그림과 같은 두 개의 분자가 있다고 하자. 두 분자는 실제 그래프로 표현되었을 때의 분자 구조가 아주 비슷하지만, 이를 SMILES로 표현하면 아주 다른 형태의 ..

2022. 8. 6. 21:37
Machine Learning - Thoery/Graph Representation Learning

WL 알고리즘 설명 (Weisfeiler-Lehman 알고리즘이란? WL test란?)

Weisfeiler-Lehman 알고리즘 (WL 알고리즘)은 두 그래프가 isomorphic한지를 검사하는 알고리즘으로, 이 테스트 결과가 다르면 두 그래프는 isomorphic하지 않다고 결론내릴 수 있다. 이번 글에서는 WL 알고리즘에 예시와 함께 대해 알아보겠다. 알고리즘 WL 알고리즘은 아래와 같은 순서로 진행된다. 각 노드에 initial label을 부여한다. initial label은 무엇이 되어도 상관없으나, 노드의 degree를 label로 사용하거나, 단순히 모두 같은 label을 부여하는 방식을 사용한다. 각 노드의 neighborhood의 label의 multiset에 대한 hash 결과를 해당 노드의 label로 사용한다. 이 때, hash 함수로는 unique한 multiset을..

2022. 7. 22. 14:57
Machine Learning - Thoery/Graph Representation Learning

GraphRNN 설명 (GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models 논문 리뷰)

GraphRNN은 graph generative model의 하나로, RNN처럼 sequential하고 autoregressive하게 노드와 엣지를 추가함으로써 그래프를 생성하는 모델을 말한다. 이번 글에서는 GraphRNN이 무엇인지에 대해서 GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models 논문을 리뷰하면서 알아보겠다. * 이 글은 RNN에 대한 기본적인 이해가 있다고 가정한다. 배경 우선, GraphRNN이 제안된 배경에 대해 먼저 살펴보겠다. GraphRNN은 아래 그림과 같이 sequential하고 autoregressive하게 노드와 엣지를 추가함으로써 그래프를 생성한다. (Autoregressive는 앞서 만들어진 ..

2022. 4. 1. 20:00
Machine Learning - Thoery/Graph Representation Learning

Permutation invariance와 permutation equivariance 차이 설명

그래프는 adjacency matrix로 표현될 수 있는데, 이 adjacency matrix는 node의 순서 (ordering)가 바뀜에 따라 같은 그래프를 표현하더라도 다르게 표현될 수 있다. Permutation invariance와 permutation equivariance는 그래프에서 노드의 ordering이 바뀔 때 function의 output이 어떻게 바뀌는지를 설명한다. 이번 글에서는 permutation invariance와 permutation equivariance가 각각 무엇이고, 둘의 차이점이 무엇인지에 대해 알아보겠다. Permutation invariance Permutation invariance는 adjacency matrix의 순서가 바뀌더라도 그 output이 변하..

2022. 3. 30. 22:32
Machine Learning - Thoery/Graph Representation Learning

Chemical VAE 설명 (Automatic Chemical Design Using a Data-Driven Continuous Representation of Molecules 논문 리뷰)

Chemical VAE는 어떤 분자 (molecule) 구조를 continuous representation으로 표현하고, 이 continuous representation에 대해 optimization을 통해 최적의 분자 구조를 도출하는 것을 목적으로 한다. 이번 글에서는 graph generative / optimization model 중 하나인 chemical VAE (해당 논문의 github이 chemical VAE라는 이름을 택하고 있어서 이 이름을 사용했다. 논문에는 따로 method를 부르는 이름은 없다.)가 무엇인지에 대해서, Automatic Chemical Design Using a Data-Driven Continuous Representation of Molecules 논문을 리뷰..

2022. 3. 29. 22:06
Machine Learning - Thoery/Graph Representation Learning

SMILES 표기법이란? (SMILES representation 설명 및 장단점)

SMILES 표기법은 Simplified Molecular Input Line Entry System의 준말로, 분자 구조를 string 형태로 표현하여 NLP에 활용된 다양한 머신러닝 / 딥러닝 알고리즘들을 분자 구조에도 적용할 수 있게 해주는 표기법이다. 이번 글에서는 SMILES 표기법을 어떻게 쓸 수 있는지와 함께 이의 장단점에 대해서 알아보겠다. SMILES 구성 요소 SMILES 표기법을 구성하는 요소는 크게 다섯가지로 나눌 수 있고, 이는 원자 (atom), 결합 (bond), 고리 (ring), 방향족 (aromaticity), 그리고 가지 (branch)이다. 각 요소들에 대해서 차례대로 알아보겠다. 원자 (atom) SMILES 표기법에서 각 원자는 해당하는 원소 기호로 표시하고, 수소..

2022. 3. 13. 16:44
Machine Learning - Thoery/Graph Representation Learning

Graph Laplacian 설명 (Unnormalized Laplacian, Normalized Laplacian)

Graph Laplacian은 Adjacency matrix 를 다양한 방법으로 변형하여 그래프를 표현할 수 있게 한 행렬들을 말한다. 이번 글에서는 이 Graph Laplacian의 종류 중 하나인 unnormalized Laplacian, normalized Laplacian의 정의와 특성들에 대해 알아보겠다. Unnormalized Laplacian Laplacian matrix 중 가장 기본이 되는 matrix가 unnormalized Laplacian이다. 이는 다음과 같이 정의한다. 위 식에서 D는 degree matrix, A는 adjacency matrix이다. 그러므로 unnormalized Laplacian matrix의 각 성분(L[i,j])은, (self-loop가 없는 그래프 가정..

2022. 2. 15. 21:00
Machine Learning - Thoery/Graph Representation Learning

Katz index란? (Katz index 증명, Adjacency matrix 설명)

local neighborhood를 활용한 measure들은, 두 노드가 공통된 이웃을 가지고 있지 않는 상황에서는 두 노드 간의 관계에 대해 추론하기 힘들다. 그러므로 이번 글에서는, 이러한 한계점을 해결하기 위해 도출된 개념인 그래프 전체를 고려하여 두 노드 간의 관계를 표현하는 Katz index에 대해 알아보고, 이와 함께 Adjacency matrix가 무엇이고 특성이 무엇인지에 대해 알아보겠다. 정의 Katz index는, 두 노드 사이의 모든 길이의 path의 빈도를 의미한다. 즉, 수학적으로 정의하면 아래와 같이 정의할 수 있다. 위 식에서 i는 두 노드 사이의 path의 길이를 의미하고, beta값은 긴 path에 대해 얼마나 weight를 줄 것인지를 결정한다. 예를 들어, beta가 ..

2022. 2. 9. 23:23
Machine Learning - Thoery/Graph Representation Learning

두 노드 사이의 관계를 표현하는 Local overlap measure (Sorensen index, Salton index, Jaccard overlap, RA index, AA index)

우리는 그래프를 활용해서 어떤 예측을 할 때, 하나의 노드가 어떤 특성을 가지고 있는지를 예측하기도 하지만 (node classification), 두 노드 사이의 관계를 예측하기(link prediction)도 한다. 이번 글에서는 두 노드 사이의 관계를 표현하는 가장 기본이 되는 척도인 neighborhood overlap, 그 중에서도 local overlap measure에 대해서 알아보겠다. 우선, 두 노드 사이의 neighborhood overlap은 말 그대로 몇 개의 이웃(직접 연결된 노드)을 공유하고 있는지를 의미한다. 이를 식으로 나타내면 다음과 같다. 위 식은 다른 말로 common neighbors라고도 부른다. 예를 들어, 다음과 같은 그래프가 있다고 하자. 그림에도 나타나 있듯이..

2022. 2. 8. 22:53