近日，韋靈思團(tuán)隊的一項研究通過研究圖的局部對稱性，提出了一種新的算法。該算法在不同的邊上使用不同的核，從而使網(wǎng)絡(luò)在局部與全局的圖同構(gòu)體上是等變的，也更易于表達(dá)。

通常來說，常規(guī)神經(jīng)消息傳遞算法在消息排列下是不變的，因此會忘記信息流如何在網(wǎng)絡(luò)中傳遞。

近日，阿姆斯特丹大學(xué) ML 教授、高通技術(shù)副總裁韋靈思（Max Welling）團(tuán)隊通過研究圖的局部對稱性，提出了一種通用性更強(qiáng)的算法。該算法在不同的邊上使用不同的核，從而使得網(wǎng)絡(luò)在局部圖和全局圖同構(gòu)上呈現(xiàn)等變化，也因而更易于表達(dá)。

論文地址：https://arxiv.org/abs/2007.08349v1

具體而言，研究者使用了初級范疇論，將許多顯式等變神經(jīng)網(wǎng)絡(luò)形式化為自然圖網(wǎng)絡(luò)（Natural Graph Network, NGN），并表明它們的核正是兩個函子（functor）之間的自然轉(zhuǎn)換。

他們還提供了一個自然網(wǎng)絡(luò)的圖實例，該網(wǎng)絡(luò)使用等變消息網(wǎng)絡(luò)參數(shù)化，在多個基準(zhǔn)上實現(xiàn)了良好的性能。

接下來我們來看這篇論文的具體內(nèi)容。

自然圖網(wǎng)絡(luò)

在圖上構(gòu)建神經(jīng)網(wǎng)絡(luò)有一種完全不同的策略，即使用圖卷積神經(jīng)網(wǎng)絡(luò)或消息傳遞網(wǎng)絡(luò)（Kipf 和 Welling, 2016；Gilmer 等人, 2017）。研究者將這類方法稱為局部圖網(wǎng)絡(luò)（local graph network, LIGN）。

以最簡單的形式，這些每個節(jié)點上具有特征 v_p 的轉(zhuǎn)換圖信號 v，使用單個共享線性變換 W 在圖的邊上傳遞消息，如下公式 2 所示：

其中 E 是圖的邊集。這類卷積架構(gòu)通常比全局方法具有更高的計算效率，這是因為計算線性變換的計算成本與邊的數(shù)量呈線性比例關(guān)系。

為了克服現(xiàn)有消息傳遞網(wǎng)絡(luò)的局限性，同時又保持更高的計算效率，研究者提出了一種新型的消息傳遞網(wǎng)絡(luò)，其中的權(quán)重是由圖結(jié)構(gòu)決定的。

也就是說，研究者對公式 2 做了改進(jìn)，得到以下公式 3：

其中線性核在每個圖每條邊上都是不同的。顯然，并非所有此類核都會導(dǎo)致等變網(wǎng)絡(luò)。接下來研究者詳細(xì)介紹了如何定義核空間。

全局和局部圖對稱性

研究者用整數(shù)數(shù)組表示圖 G 中的節(jié)點 N_G，即

，然后圖中的邊用整數(shù)對表示，邊的集合是ε(G)，則邊(p,q)∈ε(G)。

如果圖是帶有 p→q 這樣箭頭符號的有向圖，那么圖 G 和 G’是相似或同構(gòu)的。換句話說，圖同構(gòu)將節(jié)點映射到節(jié)點，邊映射到邊。一種特殊的同構(gòu)是自同構(gòu)，只是節(jié)點的排列順序有所變化，邊集保持不變。根據(jù)定義，一個組中的自同構(gòu)，稱為自同構(gòu)組。

特征

為了使等變神經(jīng)網(wǎng)絡(luò)具有可表達(dá)的核，必須將節(jié)點 p 處的特征向量 v_p 進(jìn)行變換，因為節(jié)點 p 通過某種全局對稱性映射到 p’，而不是像固定消息傳遞網(wǎng)絡(luò)中那樣保持不變。研究者重新定義了特征向量在局部節(jié)點對稱性下的變換規(guī)則。

局部等變性

邊 (p,q) 上的核是 p 點的向量空間 V_p 到 q 點的向量空間 V_q 的映射。核的局部等變性意味著，如果有局部同構(gòu)的邊的空集

，則這樣做和以下兩種情況的結(jié)果一樣：

將信號從 p 傳遞到 p’，然后再申請內(nèi)核 K^(G’)_p’q’；

先申請內(nèi)核 K^G_pq，然后將 q 轉(zhuǎn)換成 q’。

具體如下圖 6 所示：

因此需要以下公式 4：

圖神經(jīng)網(wǎng)絡(luò)的消息參數(shù)化

等變性只需要在具有同構(gòu)鄰域的邊之間共享權(quán)重，因此在定理中，我們可以將分類參數(shù)用于每個同構(gòu)類的邊鄰域，以參數(shù)化等變核的空間。

實際上，像社交圖（social graph）這類圖的異構(gòu)性很強(qiáng)，很少有邊是同構(gòu)的，并且很少需要共享權(quán)重，因而學(xué)習(xí)和泛化也是很困難的。

這一點可以通過以下方式解決：將 p 到 q 的消息

重新解釋為函數(shù)

，其中 G_pq 是邊鄰域，v_p 是 p 點的特征值，在 v_p 中可能被泛化為非線性的，K 是基于消息網(wǎng)絡(luò)的神經(jīng)網(wǎng)絡(luò)。

下圖 7 所示為作為圖卷積的消息傳遞過程：

范疇論

全局對稱性的等變約束，比如機(jī)器學(xué)習(xí)中廣泛使用的公式 1 最近已經(jīng)被擴(kuò)展到局部對稱性或規(guī)范對稱性中。

但是，這些形式不包括圖的動態(tài)局部對稱性，并且需要一種通用性更強(qiáng)的語言。

基于此，研究者使用了范疇論，該理論最初是從代數(shù)拓?fù)浒l(fā)展而來的，近來也被用作更多問題的建模工具。范疇論的結(jié)構(gòu)為建立等變消息傳遞網(wǎng)絡(luò)（稱為自然網(wǎng)絡(luò)）提供了一個良好的框架，研究者稱為「自然網(wǎng)絡(luò)（Natural Network）」。

實驗

二十面體（Icosahedral）的 MNIST

為了在實驗中驗證該方法與全局對稱的等變性，并增強(qiáng)在不變消息傳遞網(wǎng)絡(luò)（GCN）上的可表達(dá)性，研究者對投影到二十面體的 MNIST 進(jìn)行了分類。

下表 1 第一列顯示了在一個固定（fixed）投影上進(jìn)行訓(xùn)練和測試的準(zhǔn)確率。在第二列中，研究者在通過隨機(jī)二十面體對稱性變換的投影上測試了相同的模型。

結(jié)果表明，NGN 的性能優(yōu)于 GCN，并且準(zhǔn)確率相等表明該模型是完全等變的。

圖分類

在 Yanardag 和 Vishwanathan 于 2015 年提出的 8 個標(biāo)準(zhǔn)圖分類基準(zhǔn)集上（包括 5 個生物學(xué)數(shù)據(jù)集和 3 個社交圖），研究者使用 GCN 消息參數(shù)化評估了該模型。

具體而言，研究者使用了十倍交叉驗證（10-fold cross validation）方法，并給出了十倍情況下的最佳平均準(zhǔn)確率，如下表 2 所示：

實驗結(jié)果表明，在大多數(shù)數(shù)據(jù)集上，該研究提出的局部等變方法性能不遜于全局等變方法。