[논문리뷰 | CV] SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS (2017) Summary
1
[논문리뷰]
목록 보기
14/41
Title
- SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS
- GCN
DSBA 연구실(윤훈상)님의 논문 리뷰를 참고하여 작성하였습니다.
0. Background
0.1. Semi-Supervised Classification
- label data는 적고, unlabel data는 많을 때 (훈련으로 보충하고자 할 때) 사용함.
- Target(Label)이 있다가도 없음.
0.2. Graph Neural Network
- Graph꼴의 구조를 갖는 데이터에 대한 Neural Network
- Graph의 기하하적 구조 때문에 Geometric Deep Learning이라고도 칭함.
- Graph와 관련된 모든 Neural Network를
GNN
0.3. Convolution on Graph
- CNN(Convolution Neural Network)은 이미지에 대하여 Filter를 통해 정보들을 Aggregate해 나가는 과정임.
Convolution이란?
- 두 함수의 합성곱임.
- f,g 가운데 하나의 함수를 반전 or 전이 시킨 다음 다른 하나의 함수와 곱한 결과를 적분함.
-> 현재의 합성곱의 값은 이전 시간의 결과를 포함함.
ex) 산에서 메아리를 한다고 하면, t시점의 소리는 이전 소리와 중첩되어 나타나는데, 아래의 예시와 같음
- 최종 output은 맨 오른쪽의 하늘색 선과 같이 나타나게 됨.
🤜 이는 '이미지'에서만 사용되는 개념이 아님.
Graph Convolution이란?
- Graph에 Convolution Filter을 적용해서 하나의 노드의 인접 노드와의 관계를 계산하고 싶을 때 함.
- Convolution은 전체 data에서 Local Feature를 뽑아내는 데 매우 유용함.
- Filter들이 Spatial location에 따라서 변하지 않음.
- 이미지에서는 Grid형태로 Graph로 나타낼 수 있지만, Graph에서는 Convolution Filter가 계속해서 모양이 달라지게 됨.
- 즉, 그래프에서의 Convolution Filter가 모든 데이터에 대하여 같은 크기가 아니기 때문에 사용 불가함.
- Convolution = Regular Grid
하지만 어떻게든 Graph에 Convolution을 쓰고 싶으면?
Convolution Theorem
- 한 Domain의 Convolution은 다른 Domain의 point-wise multiplication과 같음.
🤜 즉, Graph Domain의 Conv는 Fourier Domain의 point=wise multiplication과 같음.
- Conv의 Laplace 변환은 point-wise multiplication으로 변함.
0.3.1. CNN vs GCN
- 합성곱 연산을 통해 각 Layer마다 weight와 filter의 값들을 스스로 update하여 학습함
- 각 Layer를 통과하면서 Convolution 연산을 수행하고 그래프의 특정 값을 update함.
-> 그래프의 점(vertex) or 선(edge)가 될 수 있지만, 이 논문에서는 vertex의 feature값을 update하는 논문임.
0.4. Spectral vs Spatial (Conv)
- Central Node의 Feature를 연삼함에 있어서 Neighbors를 이용하는 것은 같은데, 사용하는 방식이 다름.
🤜 사용하는 관점만 다름!
Spectral Convolution
- 이는 수학 기반이며, Graph Conv을 Graph Signal processing의 일환으로 봄.
- Graph Signal에 대한 Noise 제거 과정으로 봄.
- Spectral = Spectrum
- 수학적 기반이 탄탄하게 잡혀 있어서 Spectral을 많이 사용함.
Spatial Convolution
- 공간에 대해서 Convolution을 하겠다라는 의미임.
- Central Node를 주위 Neighbor의 Feature로 Update 하는 과정임.
🤜 Spectral은 계산 비용이 크지만, Spatial은 크지 않음.
0.5. 꼭 알아야 할 것
주어져 있는 정보는?
- Labeled / Unlabeled Node들이 공존해 있는 그래프
- 각 노드들의 Feature / Edge 정보 존재
찾아야 하는 미지수는?
- Supervised Loss를 통해 모델을 훈련시키는 과정을 거침. (Labeled)
- 하지만 Inference할 때는 Unlabeled Data에 대해서 진행함.
- 목적은 Labeled, Unlabeled data를 Convolution을 통해서 Node Classification or Graph Classification을 진행하는 것임.
Abstract
- 이 연구는 Graph Convolution Network (GCN)에 대한 초창기 연구로, GCN은 Adjacency Matrix, Degree Matrix 또는 Feature Matrix를 활용하여 그래프를 표현하는 신경망 기법을 소개함.
- GCN에는 두 가지 형태인
Spatial GCN과Spectral GCN이 있으며, 이 중 본 연구는Spectral GCN에 초점을 둠.
- 이 연구는 Layer-wise Propagation 규칙을 간략히 소개하며, 이 규칙이 Spectral graph Convolution에 대한 효과적이고 빠른 1차 근사법이라는 것을 입증
- 이 방법은 연결된 노드들 간의 유사성을 전제로 하므로(같은 Label을 가질 가능성이 큼), 그 이상의 다양한 정보를 포착하지 못해 모델의 성능에 제약이 생김.
- 제시한 방법이 빠르고 효율적인(Fast Approximate Convolutions on Graph) 근사임을 증명함.
- 그래프의 각 노드의 feature와 adjacency matrix A가 주어졌을 때, 이를 이용해 classification할 수 있는 multi-layer graph convolutional network(GCN) 즉, 𝑓(𝑋,𝐴)
를 제시함.
1. Introduction
- 이전의 semi-supervised 연구에서 사용되었던 loss는 '연결된 vertex간에는 유사한 label을 지닌다'고 학습되었기에 graph가 지닌 추가적 정보를 담지 못하는 한계가 존재했음.
- 이 연구에서 소개하는 GCN(Graph Convolution Network)은 Adjacency Matrix를 입력 값으로 취하여 연결된 노드들의 관계를 직접 활용함으로써 기존의 한계를 극복함.
- 위 수식은 그래프의 연결된 노드가 동일한 Label을 공유할 가능성이 있다는 가정에 의존하여 학습 진행하기 때문에, 모델의 능력(capacity)을 제한한다고 언급하며 GCN을 제안함.
2. Fast Approximate Convolutions on Graphs
- 본 논문에서는 Graph-based Neural Network model를 위와 같이 정의함.
- 이는 Spectral Convolution Network를 1차 근사만으로도 계산할 수 있게 만들고 접근성이 좋음.
- 위의 식이 first-order approximation of lacalized spectral filters on graph인 것을 유도하는 것이 본 논문의 핵심임.
- 위의 빨간색 친 부분을 이해하기 위해서는 위의 그림의 개념들을 다 알아야 함.
2.1. Spectral Graph Convolutions
- Graph에서의 Spectral Convolution은 Fourier Transform을 통해 eigen-decomposition을 수행하는 것이며, 수식은 위와 같음.
2.1.1. (Graph) Fourier Transform
- Signal을 Frequency별로 분행하는 과정을 의미함.
- 이는 [Time Domain] -> [Frequency Domain]
- Signal을 분해하는 방법은 Signal을 Fourier Basis에 Projection(사영)함.
🤜 PCA에서 어떤 vector을 기저 vector로 사용하듯이
- Fourier Transform은 주파수마다 Signal을 출력하는데, 이 때 주파수에는 Singal을 사영(Projection)하는 Fourier Bases가 존재함.
- 고유 분해 즉, eigen-decomposition을 수행하여 이를 찾는 것임.
그러면 이는 그래프 푸리에 변환에서는 어떻게 적용될까?
- Graph Signal(=Feature)을 Frequency(=Feature들 간의 차이)별로 분해하는 과정임.
- [Graph Domain] -> [Frequency Domain]
2.1.2. Spectral vs Spatial (Convolution)
- 위에서 설명했기 때문에 pass
2.1.3. Laplacian Matrix
= -
- Laplacian Matrix는 2가지 관계를 하나의 Matrix로 규합한 것임.
-
Degree Matrix
: 하나의 노드가 다른 몇개의 노드와 연결되어 있는가? (대각행렬) -
Adjacency Matrix
: 하나의 노드가 다른 어떤 노드와 연결되어 있는가? (비대각행렬)
- 대각행렬과 비대각행렬의 '차'이지만, 두 행렬의 차가 값을 뺀다는 의미가 X
-> 두 행렬을 하나의 행렬로 합친다는 의미임.
왜 Graph Fourier Transform을 적용함에 있어 Laplacian이 왜 등장할까?
- Fourier Transform 안에 이미 Laplace operator가 포함됨.
- 기존 Fourier Transform에도 Laplace operator가 쓰이는 것과 대응관계이고, Laplacian의 Eigen-vector가 Fourier Basis 역할을 수행함.
- Laplacian을 Feature Vector에 곱하는 것이 Fourier Transform의 역할을 함.
2.1.4. Fourier Transform Check
- Graph Fourier Transform을 통해 Frequency가 낮은 관계들을 우선적으로 반영함.
- Laplacian Matrix의 적용 자체가 Convolution임.
Signal: Node Feature
Frequency: Central Node와 Neighbor node간의 차이 (Laplacian으로 구함)
2.1.5. Localized Filtering
2.1.6. Chebyshev Polynomial
- 문제점: 해당 식은 Computationally Expensive함. -> 근사식 활용
2.2. Layer-Wise Linear Model
- GCN은 결국 Chebyshev Polynomial의 K를 1로 변환한 뒤, 해당 과정을 Layer로 표현함
3. Semi-supervised Node Classification
- 이처럼 많은 trick을 가한 후 최종적으로
를 Deep Learning form으로 변환하면 다음과 같음.
- 위 수식을 통해 two-layer GCN을 구성할 수 있음.
4. Experiments
- Node는 논문을 사용하였고, Egde는 논문들 간의 인용을 의미함.
Label rate는 각 데이터셋에서 훈련에 사용되는 node를 전체 노드 개수로 나눈 비율을 의미하며,Node Feature와Label은 각각 Bag of Words, Node Label을 의미함.
- 기존 논문에서 제안한 모델들 보다 본 논문에서 제안하는 GCN의 성능이 우수한 것을 확인
- 위 그림은 Chebyshev filter를 2차, 3차 다항식으로 계산한 값과, 1st-order model을 한 경우와 single parameter, Renormalization trick을 사용한 경우와 비교한 결과 Renormalization trick을 사용한 경우 가장 우수한 성능을 보임.
5. Results
- pass
6. Future Work
Memory Requirement
Directed edges and edge features
Limiting assumptions
7. Conclusion
- 이 연구에서는 그래프 구조 데이터에 대한 준지도 학습 분류를 위한 새로운 방법을 소개함.
- 제안된 GCN 모델은 그래프 상의 스펙트럼 합성의 1차 근사에 기반한 효율적인 계층별 전파 규칙을 사용
- 다양한 네트워크 데이터세트에서의 실험 결과, 이 GCN 모델은 준지도 분류에 유용한 방식으로 그래프 구조와 노드 특징을 모두 인코딩할 수 있음을 보여줌.
- 이러한 설정에서, 이 모델은 최근에 제안된 여러 방법들을 크게 앞선 성능으로 보여주면서도 계산적으로 효율적임.
🎯 Summary
- 저자가 뭘 해내고 싶어 했는가?
- 이 연구의 접근 방식에서 중요한 요소는 무엇인가?
-
그래프의 각 노드의 feature와 adjacency matrix A가 주어졌을 때, 이를 이용해 classification할 수 있는 multi-layer graph convolutional network(GCN) 즉, 𝑓(𝑋,𝐴)를 제시
-
제시한 방법이 빠르고 효율적인(Fast Approximate Convolutions on Graph) 근사임을 증명함.
-
이전의 semi-supervised 연구에서 사용되었던 loss는 “연결된 vertex간에는 유사한 label을 지닌다”고 학습되었기에 graph가 지닌 추가적 정보를 담지 못하는 한계가 존재했음. 본 논문에서 제시한 GCN은 adjacency matrix를 입력에 사용함으로써 이에 대한 제한을 해결함.
- 어느 프로젝트에 적용할 수 있는가?
- 참고하고 싶은 다른 레퍼런스에는 어떤 것이 있는가?
- 느낀점은?
📚 References
Youtube
- https://youtu.be/F-JPKccMP7k?si=Szes9qBWYizxdW67, 고려대학교 산업경영공학DSBA 연구실
Blog
데이터사이언티스트가 되기 위해 [a-zA-Z]까지 정리하는 거나입니다 😊