機器之心發佈
作者：Xiaojie Guo、Liang Zhao等
本文介紹的是一篇 ICDM 2019 最佳論文。作者定義了一種新的圖神經網絡領域的問題：「多屬性圖轉換」，即基於一個多屬性圖生成另一個多屬性圖。多屬性圖指節點和邊都擁有多種描述性屬性（標籤，類別，特徵等）。作者基於此問題開發了一種允許節點屬性和邊屬性同步轉換的新穎框架。所提出的邊屬性轉換是一種通用方法，並證明拓撲邊轉換模型是本文模型的特例。
文中還提出了一種特殊形式的基於拉普拉斯圖頻譜的正則化方法，來學習和保持圖節點和邊屬性的一致化。最後，在對合成和實際應用數據（物聯網安全優化，化學反應預測）的大量實驗證明該方法的有效性和廣泛性。
論文鏈接：http://mason.gmu.edu/~lzhao9/materials/papers/ICDM_2019_NEC_DGT-final.pdf 背景
在將輸入數據（例如圖像，文本）「轉換」為對應的輸出數據的過程中會遇到許多與結構化預測有關的問題，需要學習從輸入域到目標域的轉換映射。例如，圖像處理和計算機視覺中的許多問題都可以看作是從輸入圖像到相應輸出圖像的「翻譯」。這種翻譯問題非常重要並且有極為廣泛的，但實際上卻極為困難，近年來引起了越來越多的關注。
傳統研究只考慮特定結構類型的數據翻譯（轉換）問題，然而在許多實際應用中，需要處理比網格和序列更靈活的結構的數據，因此需要更強大的轉換技術來處理更通用的圖結構數據。現有圖結構翻譯模型有兩種形式，第一種假設來自輸入域和目標域的圖共享相同的圖拓撲結構，但是無法建模或預測圖拓撲的變化, 例如對交通網絡中節點處車流量的預測 [1]。第二種只考慮預測圖結構的變化，不考慮節點屬性的變化過程 [2]。
因此，現有的工作要麼根據固定的拓撲結構預測節點屬性，要麼根據固定的節點屬性預測邊的屬性。但是，在許多實際應用中，節點屬性和邊屬性都可以更改。在本文中，這種通用問題被稱為多屬性圖轉換，其在現實世界中有著重要應用範圍，例如從生物結構到功能性腦神經的網絡轉換和物聯網安全優化問題。
問題概述 首先將輸入圖定義為 ，其中
是 N 個圖節點的集合，而
是 M 個邊的集合。
是代表邊屬性的張量，而 K 是邊屬性的維數。
是表示節點屬性的矩陣，其中 D 是節點屬性的維數。同樣，我們將目標圖定義為
。請注意，目標圖和輸入圖的節點屬性和邊屬性均不同。此外，可能存在向量 C 提供有關轉換過程的一些環境信息。因此，多屬性圖轉換可以被定義為學習一種映射：
多屬性圖轉換問題需要考慮一些獨特的因素對結果的影響，如圖 2 所示：1）邊與邊的交互：在目標域中，邊屬性可能會受到其鄰接邊在輸入域中的屬性的影響，如圖 2(a)。2）節點與邊的交互：在目標域中，邊的屬性可能會受輸入域中其兩個鄰接節點的屬性的影響，如圖 2(b)。3）節點與節點的交互：對於給定的節點，其在輸入域中的屬性; 可能會直接影響該節點在目標域中的屬性，如圖 2(c)。4）邊與節點之間的交互：對於給定節點，其在輸入域中的相關邊屬性可能會影響其在目標域中的屬性，如圖 2(d)。5）頻譜圖屬性：一幅圖中的節點和邊之間會存在複雜的關係，如頻譜圖所反映，在輸入域和目標域中節點與邊具有某些持久性或一致性，這在許多實際應用中也已得到驗證，例如人的大腦網絡，如圖 2(e)。如何將以上四種交互模式都融入到模型當中是整個問題的難點之一。
模型概括
本文所提出的 NEC-DGT (Node-Edge Co-evolution Deep Graph Translation) 在輸入圖和上下文信息的條件下對目標域圖進行預測。但是，這種從輸入圖到最終目標圖的轉換過程可能會經歷邊緣和節點之間一系列不同類型的交互。為了學習這種複雜的過程，該文章提出瞭如圖 3 所示的 NEC-DGT 雙路徑多模塊。具體地說，將輸入圖的節點和邊的屬性作為輸入，經歷若干模塊最終輸出目標圖的節點屬性和邊屬性。每一模塊都包含有節點轉換路徑和邊轉換路徑。並利用 skip-connection 的跨模塊的連接結構（圖 3 中的黑色虛線）來處理圖轉換過程的異步特性，從而確保最終轉換的結果充分利用了每一模塊信息的各種組合。為了訓練該圖神經網絡模型，基本的損失函數最小化如下：
拉普拉斯圖頻譜正則化 1. 基於邊和節點的轉換路徑，我們可以分別生成節點和邊緣屬性。但是，由於這些生成的節點和邊屬性是在不同的路徑中分別預測的，因此它們的模式可不一致。為了探索和確保邊和節點模式的複雜關係，我們提出了一種基於非參數的圖拉普拉斯算子圖頻譜正則化的正則化方法。我們回顧傳統的拉普拉斯正則化表達式為:
傳統的拉普拉斯正則化基於非常嚴格的約束即相連的節點擁有相似的節點屬性，但顯示應用 中節點屬性和邊的連接之間有更為複雜的關係。因此，我們用一個非參數的形式去表示圖的拉普拉斯：
因此非參數的圖頻譜正則化表示為：
2. 目前的正則化複雜度是 O（N），與圖節點的數量線性相關，為了進一步提高該正則化的可擴展性，降低複雜度，我們提出一種基於切比雪夫多項式的可擴展近似的圖拉普拉斯表示，如下：
3. 為了確保學習到的圖頻譜在不同模塊生成的圖之間的保持一定程度的一致（整個過程產生的圖同屬一種類型，如人腦網絡，化學物質結構，社交網絡等），該文章提出的圖頻率正則化不僅允許保持相似性，還允許在某種程度上保留每個塊模式的專有屬性。具體來說，對於學習到的頻率（卷積核），有些對建模節點和圖之間的關係很重要，而有些則不然，導致的稀疏的模式。因此，在多任務學習的啟發下，我們使用 L2-1 範數作為正則化學習了頻率的稀疏模式：
實驗結果
本文分別在人造數據集和兩個實際數據集上進行了實驗，並分別與三類方法（共 7 種）進行了對比。其中 NEC-DGT（no reg) 作為 baseline 表示該模型不加正則化環節。
1. 基於參數衡量的各個數據集的實驗結果：
實驗結果表明，NEC-DGT 是現在唯一一個可以進行多屬性圖轉換的模型，並且分別在節點屬性和邊屬性的預測任務中超過其他單任務模型。與 NEC-DGT（no reg) 的對比表示，所提出的圖頻譜正則化對學習過程非常重要。
2. 物聯網安全優化任務案例分析：
圖 7 研究了 NEC-DGT 輸入圖，實際目標圖和生成目標圖的三種情況。綠色節點表示未感染的設備，紅色節點表示已感染的設備。每個邊的寬度反映了兩個設備之間的距離。在第一行中，在生成的目標圖和實際目標圖中，設備 4 和 6 均恢復正常，而設備 19 受到攻擊並與其他設備隔離。它驗證了我們的 NEC-DGT 成功地找到了轉換節點的規則，並且執行了像真正的限制過程一樣的操作。在第二行，設備 8 將病毒傳播到設備 38，該傳播也同樣出現在由 NEC-DGT 生成的圖中。此外，NEC-DGT 不僅可以正確預測節點屬性，還可以同時發現邊屬性的變化，例如 在第三行，在生成的目標圖和實際目標圖中都切斷了受損設備 10 的大多數連接。 本文提出的 NEC-DGT 模型的代碼和數據網絡鏈接已在論文中公開，歡迎使用。歡迎郵件聯繫 [email protected] 或者 [email protected]. 文獻：[1] Yu, B., Yin, H., & Zhu, Z. (2017). Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.04875.[2] X. Guo, L. Wu, and L. Zhao,「Deep graph translation,」arXiv preprint arXiv:1805.09980, 2018.
閱讀更多 機器之心Pro 的文章
