Graph Neural Network(GNN)에서 spatial convolution과 spectral convolution이 어떻게 다른지 살펴보려고 한다.
Spatial GCN
Spatial convolution은 가까운 이웃과 먼 이웃을 구분하여 이웃의 정보를 집계하여 convolution 연산을 수행하는 방식이다. 각 노드와 연결된 이웃 노드들에 한해서 컨볼루션 연산을 수행한다. 노드와 이웃 노드를 특정 grid form으로 재배치하여 convolution 연산을 수행하므로 고정된 크기의 이웃 노드를 선택하는 것이 중요하다. Spatial convolution은 각 노드에서 로컬로 그래프 컨볼루션을 수행하므로 서로 다른 위치 및 구조에서 가중치를 공유할 수 있다(weight sharing). 이는 일반적인 CNN의 성격와 유사하다. Spatial convolution에서 핵심은 노드 i와 이웃 노드 j에 대한 aggregating으로 노드 Vi의 representation을 생성하는 function을 학습하는 것이다.
Spatial convolution 연산은 이웃 노드의 정보를 받아서 특정 노드를 업데이트 하기 때문에, 시간이 지남에 따라서 여러가지 정보가 혼재된다. 이를 time 도메인이 아니라 frequency domain으로 바꿔서 분석을 진행하여, 한 노드에 혼재된 신호 요소를 나누어 노드 특징을 추출해내는 방식이 spectral convolution 연산이라 할 수 있다.
Spatial GCN에 속하는 모델들에 관한 논문은 아래 첨부한다. 본 논문들은 NeurIPS 2022에 Accept된 논문 'VisionGNN: An Images is Worth Graph of Nodes'에서 spatial GCN 모델로 소개되고 있는 논문들이다.
Neural network for graphs: A contextual constructive approach (NN4G)
Neural Network for Graphs: A Contextual Constructive Approach
This paper presents a new approach for learning in structured domains (SDs) using a constructive neural network for graphs (NN4G). The new model allows the extension of the input domain for supervised neural networks to a general class of graphs including
ieeexplore.ieee.org
Neural message passing for quantum chemistry (DCNN)
Neural Message Passing for Quantum Chemistry
Supervised learning on molecules has incredible potential to be useful in chemistry, drug discovery, and materials science. Luckily, several promising and closely related neural network models invariant to molecular symmetries have already been described i
arxiv.org
Spectral GCN
Spectrum이라는 단어는 전자기파, 양자역학 등 다양한 영역에서도 사용된다고 하는데, 기계학습(machine learning)분야에서는 데이터의 특징을 주파수 영역으로 변환하는 것을 의미한다. GCN에서 spectral-based 접근방식은 graph spectral theory에 기반한 그래프 신호 처리 관점(graph siganl processing)에서 filter를 소개하는 graph convolution이라고 정의된다. 직관적으로이해하자면, signal processing 방법을 활용해서(주로 Laplacian Operator를 사용하는 Fourier Transform을 이용하는듯 하다) 활용해서 convolution layer을 생성하는 방법론을 spectral convolution이라고 이해했다.
Spectral GCN에 속하는 모델들에 관한 논문은 아래 첨부한다. 본 논문들은 NeurIPS 2022에 Accept된 논문 'VisionGNN: An Images is Worth Graph of Nodes'에서 Spectral GCN 모델로 소개되고 있는 논문들이다.
Spectral networks and locally connected networks on graphs (SpectralGCN)
Spectral Networks and Locally Connected Networks on Graphs
Convolutional Neural Networks are extremely efficient architectures in image and audio recognition tasks, thanks to their ability to exploit the local translational invariance of signal classes over their domain. In this paper we consider possible generali
arxiv.org
Deep convolutional networks on graph-structured data
Deep Convolutional Networks on Graph-Structured Data
Deep Learning's recent successes have mostly relied on Convolutional Networks, which exploit fundamental statistical properties of images, sounds and video data: the local stationarity and multi-scale compositional structure, that allows expressing long ra
arxiv.org
Convolutional neural networks on graphs with fast localized spectral filtering (ChebNet)
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or wor
arxiv.org
Semi-supervised classification with graph convolutional networks
Semi-Supervised Classification with Graph Convolutional Networks
We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a loc
arxiv.org
spatial conovlution vs spectral convolution
- Computation Cost: spectral conolution은 전체 그래프를 동시에 처리해야 하므로, 노드와 엣지가 거대할 그래프일수록 비실용적일 수 있다. 또한, 동시 처리해야 하기 때문에 오늘날 충분히 활용 가능한 병렬처리 기능이 있음에도 이를 활용하기 어렵다는 단점이 있다. 반면, spatial convolution 기반의 방법들은 이웃 노드들의 정보를 전달하여 연산하므로 spectral convolution에 비해 효율성이 좋다고 할 수 있다.
- Spectral convolution은 신호 처리에 기반하여 그래프를 다루기 때문에 새로운 노드가 추가되거나 그래프가 바뀌는 경우에는 고유벡터부터 새로 계산해서 모델을 학습해야 하므로 그래프가 고정되어 있는 형태라고 가정한다. 따라서 그래프의 관계가 변할 경우에는 일반화되지 않는다는 특성이 있다. 반면, spatial convolution은 그래프가 변화하더라도 해당 노드의 이웃에 대해서만 새로 연산해주면 된다는 장점이 있다.
- Spectral convlution은 무방향(undirected) 그래프로 제한되는 반면, spatial convolution은 여러 방향성을 가진 그래프를 다룰 수 있다는 장점이 있다.
'DS > Graph Neural Network' 카테고리의 다른 글
| Graph Neural Network: Over-smoothing (0) | 2023.05.29 |
|---|
