Graph Neural Networks 이란? (파파고 번역)

https://towardsdatascience.com/an-introduction-to-graph-neural-networks-e23dc7bdfba5

An introduction to Graph Neural Networks

---

Graph Neural Network를 조금이라도 알고 싶은 마음에 읽어봤으나, 표현도 어렵고 파파고를 한 90% 돌린 것 같습니다.
해당 글에 대한 원문인 위의 글을 읽어주세요. :)

---

그래프 구조 데이터는 다양한 영역에서 공통적으로 나타나며, 분자와 같은 예는 그래프로 나타낼 수 있는 방대한 데이터 배열의 일부에 불과하다.

기계 학습의 진보와 함께 우리는 이용 가능한 데이터에 지능형 알고리즘을 적용할 수 있는 가능성을 목격한다.
Graph Neural Network는 가장 효과적인 방법으로 그래프 데이터를 위한 신경 네트워크 구축에 관한 기계 학습의 한 분야다.

컨볼루션 네트워크가 있는 컴퓨터 비전 영역에서 ML의 발전에도 불구하고, GN(Graph Neural Networks)은 더 어려운 문제에 직면하고 있다. they deal with the awkward nature of graphs.

이미지와 텍스트와는 다르게 그래프는 잘 정의된 구조를 가지고 있지 않다.
그래프의 노드는 연결이 없거나 많을 수 있거나, 방향성이 있거나 없을 수도 있다.
데이터 세트의 그래프는 다양한 수의 노드와 가장자리를 가질 수 있으며 적절히 '재조정'할 수 없으며, 순환, 순환, 접합, 분리가 될 수 있다.
앞에서 말한 것들로 인해 데이터 처리 과정은 더욱 어렵다.

 

그래프를 다루는 간단한 방법은 노드를 연결하고 더 친근한 구조적 데이터 세트를 구축하는 것이며(which could be fed to a MultiLayer Perceptron (MLP)), 비록 아주 좋은 방법은 아니지만 좋은 결과를 제공할 수 있다.

비록 이러한 방법은 다양한 크기와 위상의 여러 그래프를 다루거나 입력의 차수를 증가시키는 큰 그래프를 다루는 것은 충분하지 않다.

다양한 크기의 그래프들은 노드들을 시퀀스로 변환된 RNN으로 처리될 수 있다.
그러나, 이 전략은 역시 실패할 운명인데, 그래프 내에서 가장 중요한 정보 중 하나는 노드 순서에 아무런 흔적도 남기지 않는 그것의 구조다.

그래프 데이터는 구조를 처리하도록 맞춤화된 더 강건한 접근법이 필요로 한다.
그래프들을 처리하는데 어려움에도 불규하고, Convolution Network의 발달은 GNN 영역에 더 새로운 접근에 영감을 주었다. Convolution Layer들은 몇 가지 유용한 속성을 누린다.

• local connectivity
  • they assume that pixels which are close together are highly correlated. 
• Shift invariance
  •  convolutions learn the features of objects notwithstanding their spatial position. 

또한 Convolution Layer는 어떤 크기의 이미지에 대해서도 잘 이해한다.
이 모든 것들은 그래프에 있는 신경 네트워크에 정말 매력적인 기능이다.

• local connectivity
  
  • 노드들의 이웃들은 서로 상관관계가 있기 때문에 주변 연결성을 학습해야 한다.
• Shift Invariance
  • 그래프에서 특정한 위치에 있다 할지라도 같은 의미를 나타내야 한다.
  • 또한 그래프의 크기에 불변해야 한다.

이는 주로 Spatial 기반 그래프 Convolution 또는 Spectral 기반 그래프 Convolution으로 분류될 수 있는 그래프에 Convolution을 적용하는 다른 접근방식을 낳았다.

---

Spectral Graph Convolutions

Spectral GNN은 신호 전처리 이론에 기반을 둔 원칙적인 Convolution 접근법이다.

spectral convolution 대한 이론에 대해 자세히 설명하지 않고, spatial 영역의 Convolution 영역의 곱셈과 같다는 것이 밝혀졌다.(convolution theorem).
이와 같은 이론을 그래프에 적용될 수 있다. 그러나. 기저로써 Discrete Fourier Transform matrix를 사용하는 것 대신에, he eigenvectors of the graph Laplacian를 사용한다고 한다.

spectral convolutions 의 주요 한계점은 Laplacian Matrix의 eigenvectores의 의존성이다. 이것은 모든 계산에서 backward propagation을 위해 O(n2)과 eigen-decomposition을 위해 O(n3)의 시간 복잡성을 가진다. 

Chebyshev polynomials and Cayley Polynomials를 사용한 식을 근사화해서 시간 복잡성을 완하 시킨 추가 연구가 있다고 한다.

GCN (Graph Convolutional Networks)   Chebyshev 다항식을 사용한 ChebNet 네트워크를 더욱 단순화시켰다.

---

Spatial Graph Convolutions

Spatial convolution은 보다 graph convolution의 완화된 버전이며, 이전의 spectral gnn에 대한 gcn의 단순화에 의해 대중화되었다고 한다. Spatial Convolutions은 노드들에 대한 spatially convolute 한 보통의 convolution과 유사하다.

Convolutions은 픽셀로부터 새로운 픽셀을 생성한다(픽셀은 새로운 것과 같은 위치에 놓인다.)
주변 픽셀, 공간 그래프 컨볼루션은 노드와 인접 노드를 새로운 노드로 통합하여 Convolution을 만든다.

아래 그림은 구조화된 이미지의 그리드에서 convolution과 그래프에서 spatial graph convolution 사이에 차이를 설명하는 그림이다.
> 결국 주변 픽셀(노드)을 본다는 뜻인 듯

단일 노드에 대한 Spatial graph convolution는 다음과 같이 정의된다고 한다.

• ni : Rc에 속하는 node i를 표한한다.
• N : ni의 이웃들을 표현한다.
• w : Rc에 속하는 weight matrix이다. 
• hi : noed i의 새로운 representation을 나타낸다.

이 convolution은 노드의 새 노드에 대한 로컬 정보를 모은다.  GCN Paper에서는 다음과 같다.

이전 등식과 유사하다는 것을 알 수 있고, Theta는 non-linear activation 함수이다.
à 는 identity matrix와 graph adjacency matrix의 합이다. 이것은 이웃한 것들의 모든 노드를 모으는 역할을 한다.

D는 대각선 행렬이다. 첫 번째 방정식에서 노드 i의 모든 이웃에 대해 합산하고 그래프에 있는 노드에는 임의의 수의 이웃이 있을 수 있다는 점을 주목한다면, 우리는 합산 결과를 정상화해야 한다는 점에 유의해야 한다. 역 대각선 행렬을 곱하면 효과가 있다. 

이 간단한 시행은 spatial convolution의 기저다.
그리고 dropout과 L2, Relu를 쌓고 , adam으로 최적화하면 GCN은 이 분야에서 3개 노드 분류 벤치마크에 대해 SOTA를 달성할 수 있었다.

 

 

Graph Neural Networks can deal with a wide range of problems, 

몇 개의 이름을 지정하고 어떻게 해결되는지에 대한 주요 직감을 줄 수 있다..

• Node prediction
  • 하나 또는 다양한 그래프에서 node들이 label 또는 값을 예측하는 항목이다.
  • citation network의 페이퍼의 subject를 예측
  • 이 데스크들은 위에 설명된 convolution을 적용함으로써 간단히 풀 수 있다.
  • 대부분의 벤치마크들은 semi-supervised 설정에 있다. 
  • 이 데이터셋은 단일 그래프로 이루어졌다. 
• Graph Prediction
  • graph의 label이나 값을 예측하는 것이다.
  • ex ) 특정 분자의 독성을 예측
  • 이러한 작업은 보통 노드 간에 정보를 집계하기 위해 두 개의 그래프 Convolution 레이어를 적용한 다음, 일종의 판독 작업을 사용하여 그래프에 있는 모든 노드를 고정 크기 표현으로 집계한 다음 최종 결과를 얻기 위해 MLP 모델을 적용함으로써 해결된다.
• Graph generation
  • graph를 생성하기
  • ex) 약물의 유사성과 합성 접근성과 같은 원하는 특성이 가진 새로운 분자 생성
• Edge prediction
  
  •  

More example of tasks (as well as benchmarks and papers) can be found here.

Further we explore a few extensions to Graph Convolution Networks and GNNs.

---

Spatial-temporal Graph Neural Networks

GNN은 또한 시간이 변하는 데이터를 다루는 시간 예측 문제 또는 예측 문제를 처리하도록 맞춤화할 수 있다. ( traffic flow prediction)

Spatial-temporal graph data는 각각이 TIME STEP들을 표현하는 다중 그래프, 다양한 사이즈를 가진 그래프를 나타낸다고 한다.
이런 것들은 cnn과 rnn을 적용함으로써 해결할 수 있다고 한다.

RNN solutions generally apply graph convolutions to aggregate node-level information and apply RNN’s to aggregate temporal level information.

Convolutional approaches follow the same spirit and generally apply graph convolutions to aggregate nodes, and then 1D convolutions for temporal level information.

이미지는 트래픽 흐름을 예측해야 하는 몇 가지 관심 지점(POI)을 포함하고 있다. 도로가 자연적으로 그래프로 구조화되어 있고 모든 지역 정보(예: 근처 학교나 공원의 존재 등)가 그래프에 포함될 수 있기 때문에 이것은 공간적 GNN에 잘 맞는 작업이다. 이 문제는 또한 시간 하고도 연관되어 있다. 트래픽 흐름은 하루의 시간이나 요일에 따라 변할 것이다.

자연스럽게, 예측에서 주변 상관성이 중요하다는 것을 알 수 있다. 트래픽 흐름은 그 주변에 있는 것들에 의존적이다.
그리고 지역적이지 않고, 상황에 맞는 상관관계를 발견한다. 특히 POI 1과 3은 근처에 병원과 오락 공원이 위치하기 때문에 매우 상관성을 가지는 트래픽 흐름을 가질 것이라고 가정할 수 있다. 
이러한 문맥적인 상관성을 동일시하는 것은 모델의 일반화 성능을 향상할 수 있다. 
POI들의 사이에서 유사성을 측정할 수 있다.

‘As’ is a N x N matrix which serves a similar purpose as of the adjacency matrix as in the equation for GCN above.

비록 이것은 과제별 문제지만, 많은 작업들이 지역적인 상관관계를 가지고 있지 않으며 그래프 기반 작업에서는 이 문제가 판독 작업에 의해 완화된다.

---

Conclusion

GNN의 대부분의 문제들은 플러그 앤 플레이 솔버 역할을 하는 잘 확립된 솔루션이나 우수한 모델 아키텍처를 가지고 있지 않다. 그래프 영역의 문제들은 분명히 수직적 사고를 요구하고 있으며, 광범위한 해결책은 문제와 데이터에 따라 더 나은 결과를 얻을 수 있다.

https://www.kaggle.com/c/champs-scalar-coupling/overview

Predicting Molecular Properties