[ CVPR2022 / GML4VC ] 3. Geometric Deep Learning (Invariant, Equivariant)

---

 

Graph Machine Learning for Visual Computing (GML4VC) Tutorial 

CVPR 2022 에서 Graph Machine Learning 에 대한 튜토리얼(tutorial)을 진행했습니다.
이에 대해 요약 정리 하는 시리즈 글입니다.

---

[이전 글]

2022.08.22 - [AI/Graph Neural Networks] - [ CVPR2022 / GML4VC ] 1. 개요 (Graph Machine Learning, GNNs)

2022.08.22 - [AI/Graph Neural Networks] - [ CVPR2022 / GML4VC ] 2. Open Remarks

---

Geometric Deep Learning

• 동영상 링크 : Geometric Deep Learning
• 발표자 : Petar Veličković

petar_talk.mp4

• 이번글의 내용은 기하학적 지식이 필요합니다. 꽤 어렵습니다..
• 글의 초중반 부분은 어렵지만, 글의 뒷부분은 비교적 쉽습니다!
• 끝까지 한번 읽어보세요!

---

History

(역사 부분은 크게 중요하진 않으니 관심이 없으신 분은 다음 챕터로...)

from CVPR 2022 Tutorial:Geometric Deep Learning

기하학(Geometry)라고 하면 유클리드를 빼놓을 수 없습니다. 먼 옛날, 유클리드가 정의한 유클리드 기하학은 매우 오랜기간 모든 것의 기준이 되었습니다.

(참고, [수학/Basic] - 유클리드 공간과 기하학 (Euclidean space & geometry))

유클리드 공간과 기하학 (Euclidean space & geometry)

이후 18세기에 이르러서야 유클리드의 세계를 벗어난, 비유클리드 기하학에 대해서 연구되기 시작했습니다.

(참고, [수학/Basic] - 비 유클리드 공간 & 기하학 - 1) hyperbolic geometry(쌍곡 기하학))

비 유클리드 공간 & 기하학 - 1) hyperbolic geometry(쌍곡 기하학)

많은 정의들 중에 무엇이 진리인가에 대해 고민하기 시작했고, Invariance와 symmetry 그리고 group theory를 통해 통합된 기하학이 제시되기 시작했습니다.
(저도 사실 기하학은 잘 몰르겠네요..)

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

---

지금까지의 딥러닝과 GNNs

오랜기간 유클리드 기하학이 진리라고 생각했지만, 18세기 들어 많은 비유클리드 기하학이 생겨났습니다. 이후 다양한 기하학을 모두 아우르는 통합된 이론에 집중했습니다.

(발표자는 딥러닝 발전 과정도 기하학의 발전과 유사하다고 생각합니다.) CNN, RNN, Transformer 등 매우 다양한 모델들이 연구되어 왔으며, 모든 데이터를 다 아우를 수 있는 통합된 구조에 대한 고민이 시작되었습니다.

GNNs 이 통합된 구조로서 역할을 할 수 있을까요?

사실 Fully connected, Convolutional, Recurrent layer 모두 Graph Neural Networks로 표현할 수 있습니다.
그래서 가능성이 있습니다. 이에 대해서 자세히 알아 봅시다.

from CVPR 2022 Tutorial:Geometric Deep Learning

---

Geometric Deep Learning

기본적으로 고차원을 학습한다는 것은 어렵습니다. 차원이 늘어날 수록 필요한 데이터의 수는 급격하게 늘어납니다.
그러나 저차원을 학습하면 표현력이 떨어집니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

이러한 문제를 해결하기 위해 기하학적 가정을 삽입하게 됩니다. 이러한 가정하에 고차원의 문제를 좀 더 쉽게 만들 수 있습니다.

• inductive biases

예를 들어, 이미지의 경우 이미지의 위치 변화(shifts)에 관계없이 항상 인식할 수 있어야합니다. 고양이가 이미지의 좌측아래에 있든지, 우측상단에 있든지, 고양이는 고양이라고 인식해야 한다는 것이죠.

from CVPR 2022 Tutorial:Geometric Deep Learning

구(Spherical) 데이터에서는 회전(rotation) 과 관계없이 동일하게 처리할 수 있어야 합니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

그래프(graph) 데이터에서는 구조적으로 동일할 경우 동일하게 처리되어야 합니다. 예를들어 아래 두개의 그래프는 눈으로 볼땐 다르게 보일 수도 있지만, 노드와 연결 관계를 보면 구조적으로 완전히 동일(isomorphism)합니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

 

---

Geometric domain 표기법

 

from CVPR 2022 Tutorial:Geometric Deep Learning

 

• $\Omega$ : domain(e.g. set of pixels/nodes/...)
• $\mathcal{C}$ : vector space(dimensions are called channels)

$\mathcal{C}$ 신호의 공간을 $\Omega$에서 정의합니다.

• $\mathcal{X}(\Omega ,\mathcal{C}) = \{x: \Omega \rightarrow \mathcal{C} \}$

이산 $\Omega$에 대해서는 신호를 행렬(matrices)로 표현 가능합니다.

• $X \in \mathbb{R}^{|\Omega|\times \textrm{dim} \mathcal{C}}$
• 여기서 $i$번째 행은 $i$번째 노드(node)의 특징(feature)을 의미합니다.

 

from CVPR 2022 Tutorial:Geometric Deep Learning

예를 들어 (n x n) RGB 이미지의 경우

• pixel = 노드(node)
• 픽셀간 위치 = 엣지(edge)
• 노드(node)의 특징(feature) = RGB vector

로 표현할 수 있습니다. 이를 정리하면 아래와 같이 됩니다.

• $\Omega = \mathbb{Z}_n \times \mathbb{Z}_n$
• $\mathcal{C} = \mathbb{R}^3$

---

Hilbert Space Structure

 

• 함수해석학에서 힐베르트 공간(Hilbert空間, 영어: Hilbert space)은 모든 코시 열의 극한이 존재하는 내적 공간이다. 유클리드 공간을 일반화한 개념이다.

 

힐베르트 공간 - 위키백과, 우리 모두의 백과사전

from CVPR 2022 Tutorial:Geometric Deep Learning

 

---

Symmetries

 

A symmetry of an object is a transformation of that object that leaves it unchanged

객체의 symmetry란 객체를 변하지 않게 하는 변형입니다.

symmetry properties

• Identity transformation은 항상 symmetry 하다
• 두 symmetry transformation의 조합(composition)은 항상 symmetry 하다
• 어떠한 symmetry 든 invertible 하다
• 그리고 그것의 inverse 역시 symmetry 하다

이러한 모든 공리(axiom)들이 모여서 하나의 그룹(Group)이라고 부릅니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

 

Symmetry groups, Abstract groups 그리고 Group actions

어렵네요.. 간단하게 아래의 내용을 제가 이해한 바로 정리하자면...

특정한 특성들을 가진 변형을 모아놓은 것을 group 이라고 하는 것 같습니다. 어떠한 group 예를들어 symmetry group 이라면, 위의 공리들(ex. 변형을 가해도 객체는 동일하다)을 모두 만족하는 변형들입니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

 

---

Group representations

Group의 표현입니다. 행렬로 나타낼 수 있습니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

 

---

Invariance and equivariance

위의 내용들을 이용하여 머신러닝 과제들에 대한 invariance와 equivariance를 정의할 수 있습니다.

• Invariant : group action 을 입력값에 적용하더라도 결과에 변화가 없는 것
• Euivariant : group action 을 입력값에 적용한다면 결과에도 완전히 동일하게 반영되야 하는 것

예시!

• Image Classification : ouput 클래스는 이미지의 shift 와 상관없이 동일하게 판단해야 합니다. (Shift Invariant)
• Image Segmentation : segmentation mask는 항상 input image의 어떠한 shift도 동일하게 반영해야합니다. (Shift equivarint)

from CVPR 2022 Tutorial:Geometric Deep Learning

 

Important Constraint : Locality

도메인에서의 가벼운 변화(ex. shift, distortion..)에도 신호(ex. 이미지..)가 안정적이길 바랍니다.
이미지의 locality 제한을 가장 잘 반영한 신경망이 CNN 입니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

---

Building blocks

위의 기하학적 개념을 바탕으로 일반적인 신경망 구조의 특성을 생각해보면 아래와 같습니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

---

모델별 특성 정리

 

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

 

---

Learning on sets : Setting

지금 당장은 edge 가 없는 그래프만 고려합니다. (즉, 노드만 있는 집합에 대한 학습이라고 생각하시면 됩니다)

• $\mathcal{V}$ : Node sets
• $x_i \in \mathbb{R}^k$ : Features of node $i$
• $X = (x_i, ..., x_n)^T$: Node feature matrix (shape : $|\mathcal{V}| \times k$)
• $X$의 $i$번째 행이 $x_i$입니다.

이때 주의할 점은, 일반적으로 노드에는 순서가 없습니다. 그래서 직접 특정한 노드 순서(Node ordering)을 지정해줘야합니다.
그래서 어떠한 신경망의 결과도 이 특정한 노드 순서와 상관없어야 합니다!! (Permutation Invariant)

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

Permutation Matrices : 각 특성들의 순서를 지정해주는 행렬. 이를 활용하여 원하는 노드의 특성(node features)을 인덱싱할 수 있다.

from CVPR 2022 Tutorial:Geometric Deep Learning

---

Architecture

• 각 노드마다 공유되는 equivariant 함수 적용
• equivariant 함수가 적용된 각 노드들을 모아서 invariant 함수를 적용

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

---

Learning on Graphs

이제 노드(node)와 엣지(edge)가 모두 존재하는 그래프에 대해 학습합니다.

• $\mathcal{G} (\mathcal{V},\mathcal{E})$ : graph
• $\mathcal{V}$ : Node
• $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ : Edge
• $A$ : adjacency matrix (Edge 표현)
• $a_{ij} = 1 \quad \textrm{if}\ (i,j) \in \mathcal{E},\quad 0 \quad \textrm{else}$
• Edge features 도 가능하지만, 지금은 생략
• Permutation {in,equi}variance 는 여전히 유효

 

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

Graph 에서는 단순하게 Adjacency matrix를 이용한 Matrix Multiplication 으로 표현 할 수 있습니다!

from CVPR 2022 Tutorial:Geometric Deep Learning

---

Locality on graphs : Neighbourhoods

그래프의 특징이 여기서 분명하게 나타납니다.

집합(sets)데이터에서는 locality가 따로 없이 모든 노드를 독립적으로 변형 했습니다.
그러나 그래프(graphs)데이터에서는 edge로 연결된 이웃 노드(node's neighbourhood)에 의해 locality 가 정의됩니다.

직접적인 edge 로 연결된 경우 (1-hop) neighbourhood $\mathcal{N}_i$ 라고 합니다.

• $\mathcal{N}_i = \{j:(i,j) \in \mathcal{E} or (j,i) \in \mathcal{E}\}$

따라서, 이웃 노드의 특징 $X_{\mathcal{N}_i}$ 를 추출해 낼 수 있습니다.

• $X_{\mathcal{N}_i}=\{\{x_j : j\in \mathcal{N}_i\}\}$

그리고, local function $\phi(x_i,X_{\mathcal{N}_i})$ 를 적용합니다.

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

from CVPR 2022 Tutorial:Geometric Deep Learning

 

GNN 의 중요한 3 가지 기술

• Graph Convolution
• Graph Attention
• Message-passing

 

• Transformers 는 Fully-connected graph + graph attention과 동일

 

정리 : GNN의 유연성이 대단한 것 같네요..

---

[ 다음 글 ]

다음 글에서는 좀 더 쉽고, 간단하게 그래프 신경망(Graph Neural Networks;GNNs)에 대해서 설명합니다.

2022.08.24 - [AI/Graph Neural Networks] - [ CVPR2022 / GML4VC ] 4. Graph Neural Networks(GNNS) 기본 개념 정리

2022.08.24 - [AI/Graph Neural Networks] - [ CVPR2022 / GML4VC ] 5. Pytorch Geometric 이란 무엇인가?

2022.08.25 - [AI/Graph Neural Networks] - [ CVPR2022 / GML4VC ] 6. Deep GNNs (심층 그래프 신경망) 기본 개념 정리

2022.08.25 - [AI/Graph Neural Networks] - [ CVPR2022 / GML4VC ] 7. 비디오 이해를 위한 GNN 응용 (Graph ML for Video Understanding)

---