Spectral cnn

Presentation PPT for Spectral CNN

1. Geometric Deep Learning
Going Beyond Euclidean Data
Korea University,
Department of Computer Science & Radio
Communication Engineering
김범수Bumsoo Kim
Spectral Methods

2. Convolutional Theorem
DMIS Presentation 2
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance

3. Convolutional Theorem
DMIS Presentation 3
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
Grids in 2D image formats : pixels

4. Convolutional Theorem
DMIS Presentation 4
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
같은물체는translation 이후에도 같은feature
vector로맵핑이이루어져야 한다.
Invariance를강화하기 위한기법으로 가장
대표적인 것이Image Augmentation.
회전된featurevector가같아지게끔 학습한다.

5. Convolutional Theorem
DMIS Presentation 5
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
같은물체에대해translation 한결과는그feature vector에
translation을한결과와같다.
Equivariance를강화하기 위한기법으로 가장
대표적인 것이Group Convnet & Capsule Net
회전된featurevector는둘다‘비행기＇라고 학습한다.

6. Convolutional Theorem
DMIS Presentation 6
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
Translational structure allows weight sharing
Grid based metric allows compactly supported
filters
Multiscale dyadic clustering allows subsampling
input크기와무관하게 적은개수의parameter개수로학습
stride convolutions & pooling

7. Convolutional Theorem
DMIS Presentation 7
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
Translational structure allows weight sharing
Grid based metric allows compactly supported
filters
Multiscale dyadic clustering allows subsampling
input크기와무관하게 적은개수의parameter개수로학습
stride convolutions & pooling
dyadic refers to a domain with two abstract sets of
objects ????????????=????????????
1,…,????????????
????????????and ????????????={????????????
1,…,????????????
????????????}in which
observations ????????????are made for dyads (????????????
????????????,????????????
????????????).

8. Convolutional Theorem
DMIS Presentation 8
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
Translational structure allows weight sharing
Grid based metric allows compactly supported
filters
Multiscale dyadic clustering allows subsampling
input크기와무관하게 적은개수의parameter개수로학습
stride convolutions & pooling
3D-MESH
SOCIAL NETWORK
GRAPH
FUNCTION ON
MESH (HEAT)
POINT CLOUD

9. Convolutional Theorem
DMIS Presentation 9
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
Translational structure allows weight sharing
Grid based metric allows compactly supported
filters
Multiscale dyadic clustering allows subsampling
input크기와무관하게 적은개수의parameter개수로학습
stride convolutions & pooling
Spatial Construction
Spectral Construction
multiscale clustering
SCNN & Coarsening

10. Convolutional Theorem
DMIS Presentation 10
Why did Convolutional Neural Networks work so well?
Coordinates of data representation has grid
structure
Convolutional Neural Networks
Translational Invariance/Equivariance
Translational structure allows weight sharing
Grid based metric allows compactly supported
filters
Multiscale dyadic clustering allows subsampling
input크기와무관하게 적은개수의parameter개수로학습
stride convolutions & pooling
Spatial Construction
Spectral Construction
multiscale clustering
SCNN & Coarsening

11. Spectral Graph Theorem
DMIS Presentation 11
Simple Intuition

12. Spectral Graph Theorem
DMIS Presentation 12
Simple Intuition

13. Spectral Graph Theorem
DMIS Presentation 13
Simple Intuition
Riemannian manifolds
Graphs
“Eigenvectors of the graph Laplacian converge to Eigenfunction of
the Laplace-Beltrami operator on the underlying manifold”
Fourier Basis
Eigenvectors of Laplacian
Increasing magnitudes of the eigenvalues correspond
to increasing frequencies of the eigenvectors

14. Spectral Graph Theorem
DMIS Presentation 14
What is Spectral?
Spectrum of matrix representing G
Spectral Graph Theory

15. Spectral Graph Theorem
DMIS Presentation 15
What is Spectral?
Spectrumof matrix representing G
Spectral Graph Theory
Eigenvectors ordered by magnitude of corresponding eigenvalues.
Spectrum

16. Spectral Graph Theorem
DMIS Presentation 16
What is Spectral?
Spectrumof matrix representing G
Spectral Graph Theory
Eigenvectors ordered by magnitude of corresponding eigenvalues.
Spectrum
Self-adjoint matrix
ex)
22−????????????4
2+????????????3−????????????
4 ????????????1
22+????????????4
2−????????????3+????????????
4 −????????????1
????????????=
̅????????????= ̅???????????? ????????????
=
22−????????????4
2+????????????3−????????????
4 +????????????1
=????????????
에르미트 행렬
실수대칭행렬
????????????=????????????∗=̅????????????
????????????

17. Spectral Graph Theorem
DMIS Presentation 17
What is Spectral?
Spectrumof matrix representing G
Spectral Graph Theory
Eigenvectors ordered by magnitude of corresponding eigenvalues.
Spectrum
에르미트 행렬
실수대칭행렬
Self-adjoint matrix
????????????=????????????∗=̅????????????
????????????
Eigen values are real
Eigen vectors are orthogonal
This assures that when moving to a spectrum,
the eigen vectors will be an orthogonal basis
and its corresponding eigenvalues will be real.

18. Spectral Graph Theorem
DMIS Presentation 18
What is Spectral?
Spectrumof matrix representing G
Spectral Graph Theory
Eigenvectors ordered by magnitude of corresponding eigenvalues.
Spectrum
????????????????????????=????????????????????????
????????????−????????????????????????????????????=0
det????????????−????????????????????????=0(????????????≠0)
As????????????isthevariableindet????????????−????????????????????????=0, det????????????−????????????????????????=0is a ????????????degreepolynomial.
Therefore, there are ????????????eigenvalues ????????????
1,????????????
2, ????????????
3, … , ????????????
????????????
When ????????????
1≤????????????
2≤????????????
3≤… ≤????????????
????????????, spectrum = {????????????
1,????????????
2,????????????
3,… ,????????????
????????????}
The solution for this equation is the eigen value
∴

19. Spectral Graph Theorem
DMIS Presentation 19
What is Spectral?
Combinatorial Laplacian
Spectral Construction
Graph Laplacian
????????????=????????????−???????????? ????????????=????????????−????????????
−
1
2
????????????????????????
−
1 2

20. Spectral Graph Theorem
DMIS Presentation 20
What is Spectral?
Combinatorial Laplacian
Spectral Construction
Graph Laplacian
????????????=????????????−???????????? ????????????=????????????−????????????
−
1
2
????????????????????????
−
1 2
SCNN on d- dimensional grid
On grid space, frequency and smoothness relative to W are interrelated through Laplacian.
Smoothness
If is concentrated in the low-end of the spectrum, the corresponding spatial
kernel function is smooth; conversely, if the corresponding spatial
functions is localized, m is smooth.
Therefore, to obtain a smoother kernel function, we constrain the bandwidth
of m, enabling us to learn a smaller number of parameters; varying the
smoothness of m would control the kernel size.

21. Spectral Graph Theorem
DMIS Presentation 21
What is Spectral?
Combinatorial Laplacian
Spectral Construction
Graph Laplacian
????????????=????????????−???????????? ????????????=????????????−????????????
−
1
2
????????????????????????
−
1 2
SCNN on d- dimensional grid
On grid space, frequency and smoothness relative to W are interrelated through Laplacian.
Smoothness

22. Spectral Graph Theorem
DMIS Presentation 22
What is Spectral?
Combinatorial Laplacian
Spectral Construction
Graph Laplacian
????????????=????????????−???????????? ????????????=????????????−????????????
−
1
2
????????????????????????
−
1 2
SCNN on d- dimensional grid
On grid space, frequency and smoothness relative to W are interrelated through Laplacian.
Smoothness
Eigenvectors of the Laplacian = Fourier vectors
Eigenvector of Combinatorial Laplacian L =

23. Spectral Graph Theorem
DMIS Presentation 23
What is Spectral?
Combinatorial Laplacian
Spectral Construction
Graph Laplacian
????????????=????????????−???????????? ????????????=????????????−????????????
−
1
2
????????????????????????
−
1 2
SCNN on d- dimensional grid
On grid space, frequency and smoothness relative to W are interrelated through Laplacian.
Smoothness
Eigenvectors of the Laplacian = Fourier vectors
Eigenvector of Combinatorial Laplacian L =
Eigenvalues of the Laplacian = Fourier coefficients of a signal = smoothness

24. Spectral Graph Theorem
DMIS Presentation 24
What is Spectral?
Spectral CNN (SCNN)
????????????: nonlinearity
(????????????
1,…,????????????
????????????): input (????????????×????????????)
(????????????
1,…,????????????
????????????): output ( ????????????×????????????)
????????????=|????????????|: # of vertices in the graph: (????????????×????????????)diagonal matrix (=filter)
Combinatorial Laplacian
Spectral Construction
Graph Laplacian
????????????=????????????−???????????? ????????????=????????????−????????????
−
1
2
????????????????????????
−
1 2

25. Spectral Graph Theorem
DMIS Presentation 25
Basic : Convolutional Neural Networks
????????????
1
????????????
2????????????
3
Γ
1,1*????????????
1[:3,:3]+ Γ
1,2*????????????
2[:3,:3]+ Γ
1,3*????????????
3[:3,:3]
Γ
1,3
Γ
1,2
Γ
1,1

26. Spectral Graph Theorem
DMIS Presentation 26
Basic : Convolutional Neural Networks
Γ
2,1
????????????
1
????????????
2????????????
3
Γ
2,3
Γ
2,2 Γ
2,1*????????????
1[:3,:3]+ Γ
2,2*????????????
2[:3,:3]+ Γ
2,3*????????????
3[:3,:3]

27. Spectral Graph Theorem
DMIS Presentation 27
Basic : Convolutional Neural Networks
????????????
1
????????????
2????????????
3
Γ
3,3
Γ
3,2
Γ
3,1
Γ
3,1*????????????
1[:3,:3]+ Γ
3,2*????????????
2[:3,:3]+ Γ
3,3*????????????
3[:3,:3]

28. Spectral Graph Theorem
DMIS Presentation 28
Basic : Convolutional Neural Networks
????????????
1
????????????
2????????????
3
Γ
????????????,3
Γ
????????????,2
Γ
????????????,1
Γ
????????????,1*????????????
1[:3,:3]+ Γ
????????????,2*????????????
2[:3,:3]+ Γ
????????????,3*????????????
3[:3,:3]

29. Spectral Graph Theorem
DMIS Presentation 29
Spectral Convolution
[????????????
1,????????????
2, ????????????
3,… ????????????
????????????] [????????????
1,????????????
2, ????????????
3,… ????????????
????????????]
(n x p) (n x q)(n x k)(k x k)(k x n)

30. Spectral Graph Theorem
DMIS Presentation 30
Spectral Convolution
[????????????
1,????????????
2, ????????????
3,… ????????????
????????????] [????????????
1,????????????
2, ????????????
3,… ????????????
????????????]
(n x p) (n x q)(n x k)(k x k)(k x n)
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????, uniquely factored as the
product of an orthogonal matrix and a symmetric
positive definite matrix
complexity On
2
→O(n)

31. Spectral Graph Theorem
DMIS Presentation 31
Spectral Convolution
[????????????
1,????????????
2, ????????????
3,… ????????????
????????????] [????????????
1,????????????
2, ????????????
3,… ????????????
????????????]
(n x p) (n x q)(n x k)(k x k)(k x n)
(Φ
????????????Γ
1,1Φ
????????????
????????????????????????
1)+
(Φ
????????????Γ
1,2Φ
????????????
????????????????????????
2)+
(Φ
????????????Γ
1,3Φ
????????????
????????????????????????
3)+
…
+(Φ
????????????Γ
1,????????????Φ
????????????
????????????????????????
????????????)
????????????
1=
????????????
1=????????????(????????????
1)

32. Spectral Graph Theorem
DMIS Presentation 32
Spectral Convolution
[????????????
1,????????????
2, ????????????
3,… ????????????
????????????] [????????????
1,????????????
2, ????????????
3,… ????????????
????????????]
(n x p) (n x q)(n x k)(k x k)(k x n)
(Φ
????????????Γ
2,1Φ
????????????
????????????????????????
1)+
(Φ
????????????Γ
2,2Φ
????????????
????????????????????????
2)+
(Φ
????????????Γ
2,3Φ
????????????
????????????????????????
3)+
…
+(Φ
????????????Γ
2,????????????Φ
????????????
????????????????????????
????????????)
????????????
2=
????????????
2=????????????(????????????
2)

33. Spectral Graph Theorem
DMIS Presentation 33
Spectral Convolution
[????????????
1,????????????
2, ????????????
3,… ????????????
????????????] [????????????
1,????????????
2, ????????????
3,… ????????????
????????????]
(n x p) (n x q)(n x k)(k x k)(k x n)
(Φ
????????????Γ
3,1Φ
????????????
????????????????????????
1)+
(Φ
????????????Γ
3,2Φ
????????????
????????????????????????
2)+
(Φ
????????????Γ
3,3Φ
????????????
????????????????????????
3)+
…
+(Φ
????????????Γ
3,????????????Φ
????????????
????????????????????????
????????????)
????????????
3=
????????????
3=????????????(????????????
3)

34. Spectral Graph Theorem
DMIS Presentation 34
Spectral Convolution
[????????????
1,????????????
2, ????????????
3,… ????????????
????????????] [????????????
1,????????????
2, ????????????
3,… ????????????
????????????]
(n x p) (n x q)(n x k)(k x k)(k x n)
(Φ
????????????Γ
????????????,1Φ
????????????
????????????????????????
1)+
(Φ
????????????Γ
????????????,2Φ
????????????
????????????????????????
2)+
(Φ
????????????Γ
????????????,3Φ
????????????
????????????????????????
3)+
…
+(Φ
????????????Γ
????????????,????????????Φ
????????????
????????????????????????
????????????)
????????????
????????????=
????????????
????????????=????????????(????????????
????????????)

35. Spectral Graph Theorem
DMIS Presentation 35
Limitations of Spectral CNN
Failure with different basis

36. Spectral Graph Theorem
DMIS Presentation 36
Spectral Pooling
(n x k)(kx k)(kx n)
If is concentrated in the low-end of the spectrum, the corresponding spatial
kernel function is smooth; conversely, if the corresponding spatial
functions is localized, m is smooth.
Therefore, to obtain a smoother kernel function, we constrain the bandwidth
of m, enabling us to learn a smaller number of parameters; varying the
smoothness of m would control the kernel size.
Graph Coarsening
Pooling & StridedConvolution

37. Spectral Graph Theorem
DMIS Presentation 37
Spectral Pooling
(n x k)(kx k)(kx n)
Graph Coarsening
Pooling & StridedConvolution
Local filters at deeper layers in the spatial construction to be
low frequency.
Group structure does not commute with the Laplacian

38. Spectral Graph Theorem
DMIS Presentation 38
Limitations of Spectral Pooling
Graph does not have a group structure
Group structure does not commute with the Laplacian
Individual high frequency eigenvectors become highly unstable.
By grouping high frequency eigenvectors in each octave, can obtain stable information
(=Wavelet construction)

39. Reference
DMIS Presentation 39
Convolution & Laplacian :
https://www.khanacademy.org/math/differential-equations/laplace-transform/convolution-integral/v/the-convolution-and-the-laplace-transform
Equivariance / Invariance:
https://www.slideshare.net/ssuser06e0c5/brief-intro-invariance-and-equivariance
Spectral Graph Theory :
http://www.cs.yale.edu/homes/spielman/561/
Introduction to Spectral Graph Theory :
https://www.youtube.com/watch?v=01AqmIU9Su4
SyncSpecCNN:
https://arxiv.org/pdf/1612.00606.pdf
Convergence of Laplacian Eigenmaps:
http://papers.nips.cc/paper/2989- convergence- of-laplacian-eigenmaps.pdf
Laplacian Mesh Processing:
https://people.eecs.berkeley.edu/~jrs/meshpapers/Sorkine.pdf
What is Fourier Transform? :
https://www.youtube.com/watch?v=spUNpyF58BY
Harmonic Analysis on Graphs and Networks:
http://www.gretsi.fr/peyresq14/documents/1-Vandergheynst.pdf

40. Thank you for your attention
Q & A