Learning Convolutional Neural Networks for Graphs (2016 ICML)
ppt講解

[概要]

對(duì)于圖像images來(lái)說，CNN對(duì)輸入image的局部關(guān)聯(lián)的區(qū)域進(jìn)行操作，與此類似，本文提出了一種通用的方法，也抽取graph中局部關(guān)聯(lián)的區(qū)域進(jìn)行相應(yīng)的操作。
由于images是排列成grid形狀，所以images可以直接運(yùn)用卷積操作。但是對(duì)于圖結(jié)構(gòu)來(lái)說，需要一個(gè)從graph到向量的映射的一個(gè)預(yù)處理過程。
作者提出了對(duì)任意的圖學(xué)習(xí)卷積神經(jīng)網(wǎng)絡(luò)的框架：PATCHY-SAN(Select-Assemble-Normalize)。通過三個(gè)步驟構(gòu)建卷積分片：

1. 從圖中選擇一個(gè)固定長(zhǎng)度的節(jié)點(diǎn)序列；
2. 對(duì)序列中的每個(gè)節(jié)點(diǎn)，收集固定大小的鄰居集合；
3. 對(duì)由當(dāng)前節(jié)點(diǎn)及其對(duì)應(yīng)的鄰居構(gòu)成的子圖進(jìn)行規(guī)范化，作為卷積結(jié)構(gòu)的輸入。

通過上述三個(gè)步驟構(gòu)建出所有的卷積片之后，利用卷積結(jié)構(gòu)分別對(duì)每個(gè)分片進(jìn)行操作。
圖結(jié)構(gòu)：可以是有向圖，也可以是無(wú)向圖；圖可以有多種類型的邊；圖的點(diǎn)或邊的特征，可以同時(shí)有多個(gè)離散和連續(xù)的特征。

[應(yīng)用]

將 CNNs 拓展到大規(guī)模的基于 graph 的學(xué)習(xí)問題中，主要考慮兩類問題：

• 給定一組 graphs，學(xué)習(xí)一個(gè)函數(shù)，使之可以對(duì) unseen graphs 用于 classification 或者 regression problem
• 給定一個(gè)大型的 graph，學(xué)習(xí) graph 的表示，使其可以用于推理不可見的 graph 屬性，例如：node types 或者 missing edges

[算法]

1. 節(jié)點(diǎn)序列選擇[Node Sequence Selection]

• graph labeling: labeling算法用來(lái)確定一個(gè)graph中node的次序。這個(gè)算法可以是centrality的測(cè)量方式，比如：between centrality， Weisfeiler-Lehman algorithm, 或者其他你認(rèn)為可行的算法。由此可以得到每個(gè)節(jié)點(diǎn)的rank 值（為了不同的圖能夠有一個(gè)規(guī)范化的組織方式）
• 從該序列中根據(jù)一定的間隔隔段選取個(gè)節(jié)點(diǎn)構(gòu)成最終的節(jié)點(diǎn)序列。對(duì)每個(gè)訪問的點(diǎn)，生成一個(gè)receptive field, 直到生成個(gè)receptive fields。若不足個(gè)節(jié)點(diǎn)，則，在輸出中加全零的receptive field，相當(dāng)于padding
  
  figure 1.jpg

2. 鄰居節(jié)點(diǎn)收集[Neighborhood Assembly]

對(duì)于上一步獲得的節(jié)點(diǎn)序列中的每一個(gè)節(jié)點(diǎn)，利用廣度優(yōu)化搜索擴(kuò)展鄰居節(jié)點(diǎn)，和源節(jié)點(diǎn)一起構(gòu)成一個(gè)至少大小的鄰域集合。

3. 圖規(guī)范化[Graph Normalization]

figure 2.png

4. 卷積結(jié)構(gòu)[Convolutional Architecture]

對(duì)于節(jié)點(diǎn)的屬性，個(gè)節(jié)點(diǎn)屬性值構(gòu)成了一個(gè)輸入通道，對(duì)于邊的屬性，個(gè)屬性值也構(gòu)成了一個(gè)輸入通道。我們可以分別用一維的卷積層來(lái)處理這兩種輸入通道（對(duì)于節(jié)點(diǎn)屬性卷積層長(zhǎng)度為，對(duì)于邊屬性卷積層長(zhǎng)度為）。

[貢獻(xiàn)] Theoretical Contributions

• the definition of the normalization problem on graphs and its complexity;
• a method for comparing graph lebaling approaches for a collection of graphs;
• a result that shows PATCHY-SAN generalizes CNNs on images.

[優(yōu)缺點(diǎn)] Pros/Cons

Advantages

• Graph kernel design not required
• Outperforms graph kernels on several datasets (speed and accuracy)
• Incorporates node and edge features (discrete and continuous)
• Supports visualizations (graph motifs, etc.)

Disadvantages

• Prone to overfitting on smaller data sets (graph kernel benchmarks)
• Shift from designing graph kernels to tuning hyperparameters
• Graph normalization not part of learning

[實(shí)驗(yàn)及結(jié)果分析]

Date Sets

6 standard benchmark data sets: MUTAG, PCT, NCI1, NCI109, PROTEIN, D&D.

Experimental Set-up

PSCN vs state-of-the-art graph kenerls: SP, RW, GK, WL

Reference：

1. 論文筆記：Learning Convolutional Neural Networks for Graphs
2. 論文筆記 |Learning Convolutional Neural Networks for Graphs
3. 深度學(xué)習(xí)在graph上的使用
4. 論文引介 |Learning Convolutional Neural Networks for Graphs4