Graph Neural Network in Image (3)

https://dlgari33.tistory.com/13

Graph Neural Network in Image (1)

https://dlgari33.tistory.com/14

Graph Neural Network in Image (2)

 

이번 포스팅은 Spectral과 Spatial의 비교, Graph pooling 그리고 이론적 측면에 대한 포스팅이므로 Spectral과 Spatial 에 대한 내용은 위 포스팅을 참조하세요!

 

Comparison between spectral and spatial models

  Spectral model은 graph signal processing의 이론적인 측면에 기반한다. 새로운 graph signal filter을 설계한다면 새로운 ConvGNNs을 설계할 수 있다. 하지만, 효율성, 일반성, 유용성 때문에 spatial model이 spectral model보다 더 선호된다.

1. Spectral model이 spatial model보다 덜 효율적이다.
   • Spectral model은 동시에 고유벡터의 연산이나 전체 그래프를 처리해야한다.
   • 반면에, Spatial model은 더 큰 그래프로 확장 가능해서 그래프 영역에서 정보 전파를 convolution으로 수행해 직접으로 전파할 수 있다. 이 연산은 전체 그래프 대신에 노드의 batch에서 수행할 수 있다.
2. 그래프 푸리에 기반에 의존하는 spectral model은 새로운 그래프로 잘 일반화 되지 않는다.
   • Spectral model은 고정된 그래프를 가정하므로, 그래프에 대한 perturbatoin은 결과적으로 eigenbasis의 변화를 일으킬 것이다.
   • 반면에, Spatial-based model은 다양한 위치가 구조에 걸쳐 가중치가 쉽게 공유되어질 수 있는  각 노드에서 locally 하게 graph convolution을 수행한다.
3. Spectral-based model은 무방향 그래프에서 연산이 제한된다.
   • Spatial-based model은 multi-source graph input을 다루기에 더 유연한다.
   • Multi-source graph inputs은 edge inputs, directed graphs, signed graphs, heterogeneous graphs 가 있다.
   • 이러한 graph inputs은 aggregation function에서 쉽게 통합되어질 수 있기 때문이다.

Graph Pooling Moduels

  GNN이 node feature를 생성한 후, 이를 최종 task에 사용할 수 있지만, 이러한 모든 feature를 직접적으로 사용하는것은 계산적으로 어려우므로 down-sampling을 필요로 한다. 네트워크에서 수행하는 목표와 역할에 따라 다른 방법을 사용한다.

1. Pooling 연산은 노드를 down-sampling해 parameter의 크기를 줄이는것과 더 작은 representation을 생성하는것을 목표로 한다. 이 것으로 overfitting, permutation 불변, 계산 복잡도 문제를 피할 수 있다.
2. Readout 연산은 노드 representation에 기반해 graph-level의 representation을 생성하기위해 주로 사용된다. 

일반 ConvGNN과 pooling, readout을 사용한 ConvGNN은 그림 1과 같이 차이가 난다. 

 

그림 1

Previous work

  Pooling 이전연구로는 graph coarsening algorithms를 위상 구조를 기반으로 graph를 coarsen하기 위해 고유값 분해를 사용한다. 하지만, 이러한 방법은 시간 복잡도 문제가 발생한다. Graclus algorithm은 original graph의 clustering version을 계산하기 위한 고유값 분해의 대안이다. 최근 연구는 graph를 coarsen하기 위해 pooling 연산을 사용한다.

 

Pooling

  Mean/Max/Sum pooling은 pooling window에서 mean, max, sum 값을 계산하기위한 가장 원시적이고 효율적인 방법이다. 

 

식 1

  'Deep convolutional networks on graph-structured data' 에서는 간단한 max/mean pooling이 graph domain에서 차원을 줄이고, graph Fourier transform operation에서 비용을 줄여주는 중요한 역할을 한다고 했다. 또한 몇몇 task[2,3,4] 는 mean/sum pooling을 강화하기 위해 attention mechanisms를 사용한다. 

  Attention mechanisms을 사용하더라도, sum pooling과 같이 연산을 줄이는것은 만족스럽지 못하다. 이는 임베딩을 비효율적으로 만들기 때문에, 즉 그래프 크기에 상관없이 고정된 크기의 임베딩을 만들기 때문이다. 'Order matters: Sequence to sequence for sets' 에서는 입력의 크기에 따라 증가하는 메모리를 생성하기위해 Set2Set 방법을 제안한다. 그런 다음 정보를 소실할수 있는 감소가 적용되기 전에 order-dependent 정보를 메모리 임베딩에 통합하려는 LSTM을 구현한다.

  DGCNN에서는 pooling과 비슷한 노드를 의미 있는 순서로 재 정렬하는 SortPooling을 제안한다. ChebNet과 다른점은 DGCNN은 그래프의 구조적 규칙에 따라서 노드를 정렬하는것 이다. Spatial graph convolution에서 graph의 정렬되지 않은 노드의 특징은 continuous WL 색상으로 처리되고 , 노드를 정렬하는데 사용된다. 게다가 노드의 특징을 정렬하기 위해, node feature matrix를 잘라내 그래프 크기를 q 로 통합한다. 만약 n 이 q보다 크다면, 마지막 n-q 행이 삭제되고, 그렇지 않을 경우 q-n 0 행을 추가한다.

  앞서 언급된 pooling 방법들은 주로 graph feature를 고려하고 graph의 구조적 정보는 무시한다. 최근 graph의 계층적 표현을 생성할 수 있는 DiffPool이 제안되었다. 이전의 모든 방법들과 비교 했을때, DiffPool은 단순히 graph node를 군집화 하지 않고 assignment 행렬 S를 학습한다. 가장 최신 SAGPool은 node feature과 graph topology를 모두 고려하고 self-attention 방식으로 pooling을 학습한다. Pooling은 graph의 크기를 줄이기 위한 필수 작업이지만, pooling의 효율성과 계산 복잡성을 개선하는 방법은 아직 미결의 문제이다.

 

[1] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph sequence neural networks,” in Proc. of ICLR, 2015.

[2] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in Proc. of ICML, 2017, pp. 1263–1272.

[3] D. V. Tran, A. Sperduti et al., “On filter size in graph convolutional networks,” in SSCI. IEEE, 2018, pp. 1534–1541.

 

Paper

https://arxiv.org/pdf/1901.00596.pdf