Datawhale提供的課程鏈接：https://github.com/datawhalechina/team-learning-nlp/blob/master/GNN
一掺出、引言
圖表征學習要求在輸入節(jié)點屬性衙伶、邊和邊的屬性（如果有的話）得到一個向量作為圖的表征，基于圖表征我們可以做圖的預測】觯基于圖同構網絡（Graph Isomorphism Network,GIN）的圖表征網絡是當前最經典的圖表征學習網絡库继。
二艺谆、基于圖同構網絡（GIN）的圖表征網絡的實現
2.1 基于圖同構網絡的圖表征學習的過程
1.首先計算得到節(jié)點表征
2.其次對圖上各個節(jié)點的表征做圖池化（Graph Pooling）虫给，或稱為圖讀出（Graph Readout）舆床，得到圖的表征（Graph Representation）
2.2 基于圖同構網絡的圖表征模塊（GINGraphRepr Module）
此模塊首先采用GINNodeEmbedding模塊對圖上每一個節(jié)點做節(jié)點嵌入（Node Embedding）盛垦，得到節(jié)點表征；然后對節(jié)點表征做圖池化得到圖的表征榨呆；最后用一層線性變換對圖表征轉換為對圖的預測彻消。代碼實現如下:
2.3 基于圖同構網絡的節(jié)點嵌入模塊（GINNodeEmbedding Module）
此節(jié)點嵌入模塊基于多層GINConv實現結點嵌入的計算锥忿。此處我們先忽略GINConv的實現缎谷。輸入到此節(jié)點嵌入模塊的節(jié)點屬性為類別型向量，我們首先用AtomEncoder對其做嵌入得到第0層節(jié)點表征（稍后我們再對AtomEncoder做分析）灶似。然后我們逐層計算節(jié)點表征列林，從第1層開始到第num_layers層，每一層節(jié)點表征的計算都以上一層的節(jié)點表征h_list[layer]酪惭、邊edge_index和邊的屬性edge_attr為輸入希痴。需要注意的是，GINConv的層數越多春感，此節(jié)點嵌入模塊的感受野（receptive field）越大砌创，結點i的表征最遠能捕獲到結點i的距離為num_layers的鄰接節(jié)點的信息。
2.3?GINConv--圖同構卷積層
PyG可以通過torch_geometric.nn.GINConv來使用PyG定義好的圖同構卷積層鲫懒，該實現不支持存在邊屬性的圖嫩实。在這里自定義一個支持邊屬性的GINConv模塊。
輸入的邊屬性為類別型窥岩，需先將類別型邊屬性轉換為邊表征甲献。定義的GINConv模塊遵循“消息傳遞、消息聚合颂翼、消息更新”這一過程晃洒。
1.這一過程隨著self.propagate()方法的調用開始執(zhí)行，該函數接收edge_index, x, edge_attr此三個參數朦乏。接著message()方法被調用球及，在這里要傳遞的消息是源節(jié)點表征與邊表征之和的relu()的輸出。
2.在super(GINConv, self).init(aggr = "add")中定義了消息聚合方式為add呻疹，那么傳入給任一個目標節(jié)點的所有消息被求和得到aggr_out吃引，它還是目標節(jié)點的中間過程的信息。
3.接著執(zhí)行消息更新過程，類GINConv繼承了MessagePassing類际歼，因此update()函數被調用惶翻。
我們希望對節(jié)點做消息更新中加入目標節(jié)點自身的消息，因此在update函數中只簡單返回輸入的aggr_out鹅心。然后在forward函數中吕粗，執(zhí)行out = self.mlp((1 + self.eps) *x + self.propagate(edge_index, x=x, edge_attr=edge_embedding))實現消息的更新。
代碼實現如下：
2.4 AtomEncoder 與 BondEncoder
由于節(jié)點和邊的屬性都為離散值旭愧，它們屬于不同的空間颅筋，無法直接將它們融合在一起。通過嵌入（Embedding）输枯，可以將節(jié)點屬性和邊屬性分別映射到一個新的空間议泵，在這個新的空間中，就可以對節(jié)點和邊進行信息融合桃熄。在GINConv中先口，message()函數中的x_j + edge_attr 操作執(zhí)行了節(jié)點信息和邊信息的融合。
節(jié)點屬性映射到一個新的空間是如何實現的?
1.full_atom_feature_dims 是一個鏈表list瞳收，存儲了節(jié)點屬性向量每一維可能取值的數量碉京，即X[i] 可能的取值一共有full_atom_feature_dims[i]種情況，X為節(jié)點屬性螟深；
2.節(jié)點屬性有多少維谐宙，那么就需要有多少個嵌入函數，通過調用torch.nn.Embedding(dim, emb_dim)可以實例化一個嵌入函數界弧；
3.torch.nn.Embedding(dim, emb_dim)凡蜻，第一個參數dim為被嵌入數據可能取值的數量，第一個參數emb_dim為要映射到的空間的維度垢箕。得到的嵌入函數接受一個大于0小于dim的數划栓，輸出一個維度為emb_dim的向量。嵌入函數也包含可訓練參數条获，通過對神經網絡的訓練茅姜，嵌入函數的輸出值能夠表達不同輸入值之間的相似性。
4.在forward()函數中月匣，我們對不同屬性值得到的不同嵌入向量進行相加操作钻洒，實現了將節(jié)點的的不同屬性融合在一起。
三锄开、理論分析
3.1 動機
新的圖神經網絡的設計大多基于經驗性的直覺素标、啟發(fā)式的方法和實驗性的試錯。人們對圖神經網絡的特性和局限性了解甚少萍悴，對圖神經網絡的表征能力學習的正式分析也很有限头遭。
3.2?貢獻與結論
1. （理論上）圖神經網絡在區(qū)分圖結構方面最高能達到與WL Test一樣的能力寓免。
2. 確定了鄰接節(jié)點聚合方法和圖池化方法的應具備的條件，在這些條件下计维，所產生的圖神經網絡能達到與WL Test一樣的能力袜香。
3. 分析出過去流行的圖神經網絡變體（如GCN和GraphSAGE）無法區(qū)分一些結構的圖。
4. 開發(fā)了一個簡單的圖神經網絡模型--圖同構網絡（Graph Isomorphism Network,GIN）鲫惶，并證明其分辨圖的同構性的能力與表示圖的能力與WL Test相當蜈首。
3.3?Weisfeiler-Lehman Test (WL Test)
3.3.1 圖同構性測試
兩個圖是同構的，意思是兩個圖擁有一樣的拓撲結構欠母，也就是說欢策，我們可以通過重新標記節(jié)點從一個圖轉換到另外一個圖。Weisfeiler-Lehman 圖的同構性測試算法赏淌，簡稱WL Test踩寇，是一種用于測試兩個圖是否同構的算法。
WL Test 的一維形式六水，類似于圖神經網絡中的鄰接節(jié)點聚合俺孙。WL Test 1）迭代地聚合節(jié)點及其鄰接節(jié)點的標簽，然后2）將聚合的標簽散列（hash）成新標簽掷贾，該過程形式化為下方的公示：
在迭代過程中鼠冕，發(fā)現兩個圖之間的節(jié)點的標簽不同時，就可以確定這兩個圖是非同構的胯盯。需要注意的是節(jié)點標簽可能的取值只能是有限個數。
WL測試不能保證對所有圖都有效计露，特別是對于具有高度對稱性的圖博脑，如鏈式圖委粉、完全圖泥兰、環(huán)圖和星圖，它會判斷錯誤锐借。
Weisfeiler-Lehman Graph Kernels 方法提出用WL子樹核衡量圖之間相似性该押。該方法使用WL Test不同迭代中的節(jié)點標簽計數作為圖的表征向量疗杉，它具有與WL Test相同的判別能力。直觀地說蚕礼，在WL Test的第 次迭代中烟具，一個節(jié)點的標簽代表了以該節(jié)點為根的高度為 的子樹結構。
Weisfeiler-Leman Test 算法舉例說明：
給定兩個圖奠蹬，每個節(jié)點擁有標簽（實際中朝聋，一些圖沒有節(jié)點標簽，我們可以以節(jié)點的度作為標簽）囤躁。
Weisfeiler-Leman Test 算法通過重復執(zhí)行以下給節(jié)點打標簽的過程來實現圖是否同構的判斷：
1. 聚合自身與鄰接節(jié)點的標簽得到一串字符串冀痕，自身標簽與鄰接節(jié)點的標簽中間用,分隔荔睹，鄰接節(jié)點的標簽按升序排序。排序的原因在于要保證單射性言蛇，即保證輸出的結果不因鄰接節(jié)點的順序改變而改變僻他。
2. 標簽散列，即標簽壓縮腊尚，將較長的字符串映射到一個簡短的標簽吨拗。
3. 給節(jié)點重新打上標簽。
每重復一次以上的過程跟伏，就完成一次節(jié)點自身標簽與鄰接節(jié)點標簽的聚合丢胚。當出現兩個圖相同節(jié)點標簽的出現次數不一致時，即可判斷兩個圖不相似受扳。如果上述的步驟重復一定的次數后携龟，沒有發(fā)現有相同節(jié)點標簽的出現次數不一致的情況，那么我們無法判斷兩個圖是否同構勘高。
3.3.2 圖相似性評估
WL Test 算法的一點局限性是峡蟋，它只能判斷兩個圖的相似性，無法衡量圖之間的相似性华望。要衡量兩個圖的相似性蕊蝗，我們用WL Subtree Kernel方法。該方法的思想是用WL Test算法得到節(jié)點的多層的標簽赖舟，然后我們可以分別統(tǒng)計圖中各類標簽出現的次數蓬戚，存于一個向量，這個向量可以作為圖的表征宾抓。兩個圖的這樣的向量的內積子漩，即可作為這兩個圖的相似性的估計，內積越大表示相似性越高石洗。
3.4?圖同構網絡模型的構建
能實現判斷圖同構性的圖神經網絡需要滿足幢泼，只在兩個節(jié)點自身標簽一樣且它們的鄰接節(jié)點一樣時，圖神經網絡將這兩個節(jié)點映射到相同的表征讲衫，即映射是單射性的缕棵。可重復集合（Multisets）指的是元素可重復的集合涉兽，元素在集合中沒有順序關系招驴。 一個節(jié)點的所有鄰接節(jié)點是一個可重復集合，一個節(jié)點可以有重復的鄰接節(jié)點枷畏，鄰接節(jié)點沒有順序關系忽匈。因此GIN模型中生成節(jié)點表征的方法遵循WL Test算法更新節(jié)點標簽的過程。
在生成節(jié)點的表征后仍需要執(zhí)行圖池化（或稱為圖讀出）操作得到圖表征矿辽，最簡單的圖讀出操作是做求和丹允。由于每一層的節(jié)點表征都可能是重要的郭厌，因此在圖同構網絡中，不同層的節(jié)點表征在求和后被拼接雕蔽，其數學定義如下：
采用拼接而不是相加的原因在于不同層節(jié)點的表征屬于不同的特征空間折柠。未做嚴格的證明，這樣得到的圖的表示與WL Subtree Kernel得到的圖的表征是等價的批狐。
