[DL Hacks]Graph Convolutional Network LT

Graph Convolutional Network LT M2

• Graph • NN Graph • • • • GCN

• Graph Convolution • Graph Fourier • Graph Convolution • Graph Convolutional Network • 2 • • •

[1]

Graph Convolution • Convolution • • 2 • Graph Fourier • • • Graph Fourier • • Graph

Graph Convolution ( ) • … Convolution Theorem ( Fourier Graph Convolution Theorem ↓ ↓ Graph Fourier Convolution Theorem "! ∗ $ = "& ⊙ $( "& : f Fourier * : ⊙: )

Graph Fourier • • • G = (V, E, W) • V: , E: • • Graph Fourier • d , W: (i, j) (i,j) (d = 1)

Graph Fourier
•
• ! ∈ ℝ$
•

1

!
' +(,* ,( − ,*

.

%&

(,*

•

%$/0
• %& , %0 , … %$/0

ℝ$

%(20 =

argmin

: ∈ ℝ; , : <0, :=>? …=>@

' +(,* ,( − ,*
(,*

.

• ! %",$ &" − &$ ",$ • -. , -/ , … -12/ L ( = 2& + ,&

Graph Fourier # = % = &' , &) , … &+,) !→! • ! = / %0 10 0 • U = 1' , 1) , … 1+,) • Graph Fourier Graph Fourier # = 23 ! ! 4 = 2# # ! ! - GF -.

Graph Convolution • 1. /, 2 GF Graph Convolution / ∗1 2 8 = :; / : /→/ 8 8⊙= 8 2. = :/ 8? 8 = :(8 8) 3. GF :/ ⊙= /⊙= • Convolution Theorem 8) = U(: ; / ⊙ : ; =) / ∗1 2 = :(8 /⊙= • GCN BC = DEFB(G) BC ∗1 I: = :BC : ; I Convolution Theorem J? ∗ B = JK ⊙ BL JK : f Fourier * : ⊙:

Graph Convolution
• ! = ($% , $' , … $)*' )
1 = 23 .
1. . GF
: .→.
1
2. !
:! ⊙ .
1 = 2(! ⊙ .
1)
3.
GF
: !6
⊙.
• Convolution Theorem
1) = U(! ⊙ 2 3 .)
! ∗ . ∶= 2(! ⊙ .
• ! ⊙ 2 3 . = 9:;< ! 2 3 .
<= ∗ >: = 2<= 2 3 >

Convolution Theorem
?6
∗ < = ?@ ⊙ <A
?@ : f Fourier
* :
⊙:

Graph Convolution • (!" = $%&!(()) !" ∗+ ,: = .!" . / , • • • CNN • • • U : O(n^2)

2 • • [2] Graph Convolutional Network [2] [3]

• !" L [2] K • • Λ O(|E|) K

• K=1 [3] # ! = $%& ! ∈ ℝ) × + : % ∈ ℝ) × , : & ∈ ℝ, × + : $# ∈ ℝ, × + : ( GCN )

• GCN

• Karate club •4 • [6]

WordNet • Wang, et al [4] • GCN(Graph Convolutional Network) • Chen, et al [5] • GCN Zero-shot Learning

• Graph Convolution • Graph Fourier Convolution Theorem • Graph Convolution Network • • • GCN

[1]: https://tech-blog.abeja.asia/entry/2017/04/27/105613 • GCN [2] Michael et al. Convolutional neural networks on graphs with fast localized spectral filtering. NIPS’2016. [3] Thomas et al. Semi-Supervised Classification with Graph Convolutional Networks. ICLR’17 [4] X. Wang, et al. Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs. CVPR’18 [5] Meihao Chen, et al. Graph convolutional networks for classification with a structured label space. arXiv preprint arXiv:1710.04908, 2018 [6] https://tkipf.github.io/graph-convolutional-networks/ • [3]

• https://tech-blog.abeja.asia/entry/2017/04/27/105613
• https://tkipf.github.io/graph-convolutional-networks/