[DL Hacks]Semi-Supervised Classification with Graph Convolutional Networks

Semi-Supervised Classification with Graph Convolutional Networks M2 0

• • ICLR 2017 • • • 1

• (Graph Convolutional Network) • • • Graph Convolutional Network • • Graph Convolution 2

Graph Convolutional Network ( ) A • • "! = " + %& (A: , %& : ')) = Σ+ "! )+ ( ,: . (0) ∈ ℝ& × 5 : l ) 3

N ! (#) ∈ ℝ' × ) ! (#*+) ∈ ℝ' × , : Shuman et al. 2013 4

Spectral Graph Convolutions (1) N ( ) (1) (1) • 7 89 • U • U • • x: • ! ∈ ℝ$ ( • U: ) + , * • % = '$ − ) -) • 12 = 3451 6 • 6 ∈ ℝ$ + , * = .Λ. 0 5

1 • • L: • A: • D: ( ) 6

2 … Convolution Theorem ( Fourier Graph Convolution Theorem ↓ ) ↓ Graph Fourier Convolution Theorem "! ∗ $ = "& ⊙ $( "& : f Fourier * : ⊙: Graph Convolutional Network LT ( DL_Hacks ) https://www.slideshare.net/DeepLearningJP2016/graph-convolutional-network-lt 7

• https://www.slideshare.net/DeepLearningJP2016/graph-convolutional-network-lt

Spectral Graph Convolutions (2)
• !"

[Hammond et al. 2011]

Λ

(2)
•

$Λ$ %

&

= $Λ& $ %
(3)

• (3)

k-hop

(
• (′ ∈ ℝ,
- = . Λ − 45 (7: 9
• Λ
• 9; =

/012
.

/012

)

)

9 − 45
8

Layer-Wise Linear Model (1) GCN • (3) • • • !"#$ K = 1, !"#$ = 2 ( ) NN (4) • (4) • % = %'( = −%*( (5) 9

Layer-Wise Linear Model (2) & %' & %' & * %' & + * %' • !" + $ ($ → $ ($ • (+ = ( + !" *-- = Σ/ (+ -/ •$ • (5) • 0 ∈ ℝ"×4 • Θ ∈ ℝ4×6 • Z ∈ ℝ"×6 10

Graph Convolutional Network ( ) A • • "! = " + %& (A: , %& : ')) = Σ+ "! )+ ( ,: . (0) ∈ ℝ& × 5 : l ) 11

GCN • • • • • ( ) • • Karate Club [Brandes et al. 2008] 12

• • Ex. [Zhu et al., 2003] • • • skip-gram • Ex. DeepWalk [Perozzi et al., 2014] • random walk • 13

GCN 1, 4 • • 2 Loss ( ) GCN Loss [X1 [X2 [X3 [X4 ] ] ] ] 4*K [Z1 [Z2 [Z3 [Z4 ] ] ] ] 4*Q 14

Citation Network • Citation Network • • • Label rate bag-of-words 15

16

• • • • • • https://www.inference.vc/how-powerful-are-graph-convolutions-review-ofkipf-welling-2016-2/ • • 17

• https://www.inference.vc/how-powerful-are-graph-convolutions-review-of-kipf-welling-2016-2/

Graph Convolutional Network Graph Convolution • • • • • GCN • • 18