輸出：節點嵌入。 我們還可以嵌入更大的網路結構，子圖，圖形。

關鍵思路：基於本地網路鄰居生成節點嵌入

直覺：節點使用神經網路聚合來自鄰居的資訊

已經提出了具有神經網路差異選擇的許多模型變體。

直覺：網路鄰居定義了一個計算圖

每個節點都基於其鄰域定義一個計算圖！

透過鄰居聚合獲得節點表示

過池化節點表示來獲取圖形表示

圖神經網路在以下方面實現了最先進的效能：

節點分類[Kipf + ICLR’2017]圖形分類[Ying + NeurIPS’2018]連結預測[Zhang + NeurIPS’2018]

圖神經網路是完美的麼？有什麼限制麼？

傳統的GNN無法區分某些簡單的圖形結構。

假定：輸入節點要素是統一的（由相同的節點顏色表示）

GNN不能可靠處理圖資料中的噪聲

傳統圖神經網路在捕獲圖結構時的限制

給定兩個不同的圖，GNN可以正確的把他們對映成不同的圖形表示嗎？

分類解決方案的重要條件

本質上，圖同構測試問題。

對於一般情況，不存在多項式演算法。圖神經網路可能無法完美地區分任何圖形！

圖神經網路可能無法完美地區分任何圖形。

圖神經網路可以執行圖形同構測試的程度如何？

需要重新考慮圖神經網路如何捕獲圖結構的機制。

重新考慮圖神經網路

圖神經網路使用不同的計算圖來區分不同的圖。

節點表示法捕獲根的子樹結構。

大多數判別式GNN將不同的子樹對映到不同的節點表示形式（用不同的顏色表示）。

如果函式將不同的元素對映到不同的輸出，則該函式是單射的。

如果鄰居聚合的每個步驟都是單射的，則整個鄰居聚合都是單射的。

鄰居聚合本質上是多集（具有重複元素的集）上的函式

GNN的判別能力可以透過多集函式來表徵

下面：分析GCN，GraphSAGE

回顧：GCN使用均值池

GCN將無法區分按比例等效的多集。單射行不通！

回顧：GraphSAGE使用最大化池。

GraphSAGE甚至無法用相同種類的不同元素來區分多集。 單射行不通！

我們如何使用神經網路設計單射射多集函式？

定理

任何單射多集函式都可以表示為

圖同構網路（GIN）

GIN的鄰居聚合是單射的！

圖池化也是多集函式。

總和池化可以提供單射圖池化

到目前為止：GIN透過使用內射性鄰居聚合來實現[Xu + ICLR’2019]的最大判別能力。

這有多強大？

GIN與Weisfeiler-Lehman（WL）圖同構測試（1968）密切相關。

已知WL測試能夠區分大多數實際圖形。

WL首先將不同的有根子樹對映到不同的顏色

類似GIN單射鄰居聚合

然後，WL計算不同的顏色。

類似GNN的圖池化

最後，WL比較計數

WL測試和GIN在操作上等效。

WL測試可以區分的GIN可區分的圖

觀察

GIN具有與WL圖同構測試相同的判別能力。已知WL測試可以區分大多數圖形，除了一些特殊情況。

由於所有節點都具有相同的本地子樹結構，因此對於WL測試，兩個圖看起來相同。

後續工作以解決極端情況，但時間複雜度卻成倍增加：

圖分類：社會圖和生物/化學圖訓練不同GNN架構的準確性。

GIN比GCN GraphSAGE更適合訓練資料。

資料集趨勢相同！

圖分類：社會圖和生物/化學圖

GIN在測試準確性方面也優於現有的GNN，因為它可以更好地捕獲圖形結構。

Reddit資料集不具有節點功能

現有的GNN使用非注入式鄰居聚合，因此判別力較低

GIN使用內射性鄰域聚合，與WL圖同構測試具有區別GIN在圖形分類中達到了最先進的測試效能GNN易受圖形資料噪聲影響

深度神經網路容易受到對抗性攻擊！

通常將攻擊作為難以察覺的噪聲實施，從而改變了預測

對抗在圖神經網路的應用中非常常見，例如搜尋引擎，推薦系統，社交網路等。

這些對抗將利用任何公開的漏洞！

GNN是否對對抗敏感？

在這裡，我們重點介紹使用圖卷積神經網路（GCN）進行的半監督節點分類[Kipf + ICLR’2017]

輸入：部分標記的屬性圖

目標：預測未標記節點的標籤

現實世界中受到攻擊可能性？

目標節點t∈V：我們要更改其分類標籤的節點

攻擊者節點s⊂V:攻擊者可以修改的節點

數學上如何計算這些攻擊機率？

Zügner+，針對圖形資料的神經網路的對抗性攻擊，KDD’18

最大化（目標節點的預測標籤的更改）受（圖中的噪聲限制）的影響

查詢修改後的圖形，該圖形可以最大程度地改變目標節點的預測標籤

讓我們解析一下目標函式！

查詢修改後的圖形，該圖形可以最大程度地改變目標節點的預測標籤

GCN在修改的圖形上訓練，然後將其用於預測目標節點的標籤。

修改後的圖應接近原始圖。

實際上，我們不能完全解決最佳化問題，因為……

圖形修改是離散的（不能使用簡單的梯度下降來最佳化）內迴圈涉及昂貴的GCN再訓練

已經提出了一些試探法來有效地獲得近似解。

例如：

貪婪地選擇逐步圖形修改透過取消ReLU啟用來簡化GCN（以封閉形式工作）等

使用GCN的半監督節點分類

由5個具有不同隨機初始化的GCN生成的單個節點的類預測

僅透過5種圖形結構修改（| V | =〜2k，| E | =〜5k）即可輕鬆操縱GCN預測

GAN對於對抗攻擊不夠健壯

問題和未來的方向

化學：分子圖 分子性質預測

生物學：蛋白質-蛋白質相互作用網路 蛋白質功能預測

標籤資料不足標籤需要昂貴的實驗模型過度適合小型訓練資料集分佈外預測測試示例與科學發現訓練非常不同模型通常表現不佳

預訓練GNN

我們已經看到了如何攻擊GNN

公開問題 如何防禦攻擊？

挑戰：

對離散圖形資料的可實踐最佳化在精度和魯棒性之間取得良好的折衷