Machine Learning for Graphs

그래프 기계학습 내용은 개인적인 공부를 위해서 정리하는 용도이다. 개인적으로 인터넷을 통해서 공부한 내용을 포함하여 POSTECH의 안성수 교수님의 그래프 기계학습 강의를 기반으로 정리할 것이다.Graph Neural Network (GNN)은 특정한 function

Graph Neural Network (GNN)에 대해 본격적으로 알기 이전에, GNN 이전에 그래프 데이터에 사용되었던 접근 방식들에 대해서 먼저 알아보고자 한다. 그래프는 노드에 해당하는 entity와 엣지에 해당하는 relation과 interation을 설명하고

Graph Neural Networks 지금까지는 graph를 처리하는 전통적인 algorithm들에 대해서 알아보았다. 이제부터는 graph를 처리하기 위한 deep learning 기반의 방법들에 대해서 알아보고자 한다. 이번에 알아볼 graph neural network (GNN)은 graph를 파악하는 neural network로 아이디어는 굉장히...

GNN Overview Graph neural network(GNN)은 결국 여러개의 permutation equivariant/invariant function들로 구성할 수 있다. 이번에는 둘 중에서 permutation equivariant function에 초

Graph $G$가 있고, $V$는 vertex set, $A$는 adjacency matrix, $X$는 node feature를 표현하는 matrix라고 해보자. 그리고 node $V$에 대해서 이웃한 neighbor node들을 $N(v)$라고 해보자. 이제 우

GNN and Attention 이번에는 GNN과 attention 사이에서 어떻게 개념이 연결될 수 있는지 알아보고자 한다. 지금까지 우리는 의도적으로 중요한 attention mechanism의 존재를 넘겨두고 있었다. 그만큼 중요한 개념이기에 이번에 자세하게 알

Graph Attention Network Graph attention network (GAT)를 이해하기 위해서 우리는 GCN의 message-passing update로부터 시작하고자 한다. 결론부터 이야기하자면 GCN에서의 aggregation step을 att

Why Manipulate Graphs GNN을 다루기 앞서 왜 graph를 manipulation해야 하는지 알아야 한다. 지금까지 우리가 GNN에 넣을 graph를 처리한다고 했을 때, 예를들어 molecular graph나 community graph 등을 파악하기 위해서 GNN에 해당 graph를 넣는다고 가정했을 때, 우리는 raw input g...

Significant GNN Architectuers 이번에는 2021년도까지 약 10년 동안 중요하다고 생각되는 몇몇 GNN들에 대해서 알아보고자 한다. Generalization of CNN to Graphs 가장 먼저 우리는 GNN의 역사에 대해서 알고싶기 때

GNN Benchmarks 이번에는 GNN을 평가하는데 있어 사용되는 여러 benchmark들에 대해서 알아보고자 한다. 이번에 살펴볼 benchmark들은 여러 machine learning 학회에서 볼 수 있는 논문들에 기반한 것들이다. TUDataset 가장

Strateges for Better GNN Architectures 사람들이 여러 GNN을 만들기 위해서 어떠한 것들을 고려하는지 알아보고자 한다. 이를 설명하기 위해서 위와 같은 레퍼런스로부터 미로라는 metaphor를 이용해서 알아볼 것이다. 이미 존재하는 GN

Why Signal Processing? 이번에는 GNN을 signal processing의 관점에서 다시 끌어내보려고 한다. 새로운 GNN 구조를 만든다고 했을 때 사람들은 CNN에서 이미지 상에 잘 동작했던 것을 어떻게 하면 GNN에 가져다가 사용할 수 있을지를

Alternative Fourier Basis 우리는 time signal에 대한 shift operator로 여겨지는 adjacency matrix에 대해서 알아보았고, degree matrix에서 adjaency matrix를 빼서 만들 수 있는 Laplacian

Fourier Transform Graph signal processing 기법 중 graph wavelet transformation을 제대로 이해하기 위해서 우리는 graph domain이 아닌 signal에서의 wavelet transformation (WT)에

Wavelet Transform on Graphs Wavelet transformation (WT)에 대해서 알아보았으면, 이제부터는 본격적으로 WT를 graph에 어떻게 적용하는지 알아보자. 결국 signal processing을 graph에 대해서 수행하는지 알아

이번에는 GNN과 관련하여 Laplacian positional encoding에 대해서 알아볼 것이다. 이 내용은 사실 transformer에 이미 등장했던 개념으로 다시 한번 이 부분에 대해서 자세하게 알아보고자 한다. 먼저 Laplacian matrix $L$로부터 시작할 것이다. $L$은 degree matrix에서 adjacency matrix를...

Graphs Graph neural network(GNN)의 expressive power를 이야기하기 위해서 결론적으로 WL test를 알아야한다. 우리가 GNN1, GNN2, GNN3가 있다고 했을 때 어느 GNN이 더 좋은지 비교를 하고 싶으며, 이는 expre

The Weisfeiler-Lehman (WL) Test Weisfeiler-Lehman (WL) test는 원래 neural network와 관련된 개념이 아니라 graph theory와 관련된 개념이다. ![](https://velog.velcdn.com/ima

MPNN Formalism 오늘 알아볼 내용은 GNN의 이론적인 분석에서 꽤 비중이 있는 paradiam에 대해서 알아볼 것이다. 바로 over-squashing 문제이다. GNN을 어떻게 설계하고 GNN의 expressive power를 어떻게하면 올릴지도 중요한

Some Limitations of Static Graph-Rewiring 이번에는 over-squashing 현상을 해결할 수 있는 graph rewiring의 알고리즘적 접근법에 대해서 알아볼 것이다. 이전에는 이론적인 접근법들을 살펴보았는데, 이번에는 이와 다르

Expander Graphs 이번에는 over-squashing 현상과 관련하여 expander graph의 개념을 기반으로 해결하려는 expander graph propagation에 대해서 알아보고자 한다. 이는 negatively curved graph에 대한

Cooperative Graph Neural Network 마지막으로 over-squashing 현상을 해결하는 방법으로 cooperative graph neural network에 대해서 알아보자. 이 방법은 기존의 graph rewiring을 manual하게 하는

Deep Generative Models 이번에 알아볼 deep graph generative model은 이전까지 알아보았던 graph representation learning과는 조금 다르다. Graph를 생성하기 이전에 최근에는 굉장히 쉽게 고화질의 image

이전에 살펴본 GraphRNN과 BFS를 사용하는 방법이 graph를 생성하는 대표적인 방법 중 하나였고, 많은 문제를 해결할 수 있는 좋은 방법이었다. 하지만 이렇게 좋은 방법이 있음에도 불구하고 연구자들은 계속해서 다양한 연구를 진행하고 이로 인해 다양한 방법들이

Overview Graph neural network (GNN)을 공부하다가 보면 한번쯤은 GNN이 geometric deep learning의 일부분이라는 것을 들어볼 수 있고, GNN에 대해서 이미 친숙하다면 geometric deep learning (GDL)에

Groups and Symmetries 이번에는 geometric deep learning (GDL)과 관련하여 blueprint를 설명하려고 한다. 여기서 blueprint라는 것은 우리가 CNN, GNN 등을 표현하는데 있어서 중요한 formula를 설명하려고 하

3D Point Clouds (or Geometric Graphs) 3D geometric GNN은 3D graph data를 설명하는 framework로 가장 대표적인 data가 바로 3D point cloud이다. 3D 좌표에서 node vertex들이 표현되어