什麼是圖結構

導語

相比於計算機視覺和自然語言處理，圖挖掘領域中對資料增強的相關研究仍處於起步階段。來自浙江工業大學·網路空間安全研究院的宣琦教授團隊的工作較早地探索瞭如何設計圖上的資料增強方法，研究表明，簡單的啟發式網路重連方法就可以作為有效的資料增強策略，對圖模型的最佳化起到一定的幫助。

論文題目：

M-Evolve： Structural-Mapping-Based Data Augmentation for Graph Classification

原文地址：

https：//ieeexplore。ieee。org/document/9237158

https：//arxiv。org/abs/2007。05700

圖分類的應用價值

圖分類，或稱網路分類，主要根據圖的拓撲結構來預測其標籤資訊，是圖資料探勘領域中一個重要的學習任務。不同於節點分類、鏈路預測等利用圖的區域性結構進行推理，圖分類需要關注圖資料的全域性資訊來建模圖到標籤的對映。該任務常用於生物、化學、社交等領域，典型的應用有藥物分類、毒性檢測、蛋白質分析、社交模式識別等。例如，在生物化學領域中，化合物可以看成一個帶標籤的分子圖，圖中的節點代表原子，邊代表原子之間的化學鍵，圖分類的目的在於根據分子結構特徵去確定化合物的性質，例如是否具有致癌性、是否具有某種催化效果等。

圖1：圖資料探勘中不同任務的視角差異。

從左到右依次是：節點分類、鏈路預測、社群檢測以及圖分類，四種任務的聚焦依次是：節點視角、邊視角、中觀視角以及全圖視角。

探索圖上的資料增強

圖資料探勘演算法如圖分類等，極度依賴於大量的標籤資料來訓練模型。而生物、化學領域中，一些用於圖分類的標準資料集，如MUTAG、KKI等，存在資料量過少的問題。即使圖分類演算法不斷地被最佳化創新，資料集規模的限制依舊會給模型帶來過擬合、泛化能力低等問題。

資料增強

（data augmentation）

是一種透過讓有限的資料產生更多的等價資料來人工擴充套件訓練資料集的技術，是解決模型過擬合的有效途徑。在計算機視覺領域，常用的資料增強技術主要有幾何變換、顏色調整、風格遷移、加噪聲等。例如，透過對一張貓的圖片經過簡單的資料增強

（如旋轉、放縮、銳化）

，可以生成大量等價的圖片。然而，對於圖結構資料而言，由於其不規則、非歐的結構以及強烈的語義拓撲依賴性，我們無法直接將影象領域的資料增強技術直接應用於圖資料。

鑑於此，來自浙江工業大學·網路空間安全研究院的宣琦教授團隊對此問題進行了研究——探索圖結構資料上的資料增強。這項研究工作的結果於2020年發表在

IEEE

Transactions on Network Science and Engineering

（IEEE TNSE）

期刊。

圖2：資料增強的應用示例。資料增強透過人工擴充有限的訓練集，來生成更多有效的訓練資料。

這項工作中，主要研究的物件是圖分類任務。對該任務，作者提出了針對圖的若干啟發式的資料增強技術，包括隨機對映、節點相似度對映、模體隨機對映以及模體-相似度對映。其中隨機對映透過對原始圖進行一定比例的隨機重連生成新的圖；節點相似度對映刪除相似度較低的節點對之間的連邊，增加相似度較高的節點對之間的連邊；模體-隨機對映透過對網路中的特定模體進行邊交換來豐富網路結構，如圖3所示；模體-相似度對映在模體隨機對映的基礎上，將節點相似度作為取樣權重，如圖4所示。

圖3：模體中的邊交換示意圖

圖4：模體-相似度對映示意圖

透過提出的啟發式資料增強方法，我們可以生成大量的弱標註樣本，擴充圖資料集的規模。然而，考慮到資料增強會引入一定的噪聲，生成得到的弱標註樣本是否可以直接用於訓練依舊值得思考。在計算機視覺中，資料增強對影象的語義資訊幾乎不會造成破壞，然而對於圖結構資料，由於其性質極度依賴於拓撲結構，透過修改圖結構生成的樣本可能會丟失原本的語義資訊，原本的標籤不一定適用於新生成的樣本。鑑於此，作者引入了“標籤可信度”的概念，用於衡量樣本和其標籤的匹配程度，達到資料篩選的目的。

最後，作者提出了一個模型演化框架M-Evolve，該框架結合了資料增強、資料篩選、模型迭代重訓練三個部分，如圖5所示，可以有效地逐步最佳化圖分類器，緩解過擬合，提高泛化能力。

圖5：模型演化框架M-Evolve流程圖。

1）預訓練圖分類器；2）利用資料增強生成大量弱標註樣本；3）利用驗證集計算標籤可信度閾值；4）計算弱標註樣本的標籤可信度；5）利用閾值進行篩選，獲得擴充的訓練集；6）利用擴充的資料集重訓練圖分類器。

模型演化框架對圖模型的最佳化效果

作者在6個小規模標準資料集、5種圖分類模型上進行了實驗，得出瞭如下結論：1）四種圖資料增強方法結合“標籤可信度”指導資料篩選均可以有效增強圖分類模型，增強效果視資料集而定，從2。78%-13。36%不等；2） M-Evolve中的資料篩選機制非常重要，可以穩定增強後的模型效能；3） 該框架可以有效地提升資料規模、豐富資料分佈、最佳化分類器的決策邊界

（模型在最佳化前後訓練資料分佈以及決策邊界的比較見圖6、7所示）

；4） 該框架可以有效地緩解模型在小資料集上訓練時產生的過擬合問題，提升模型的泛化能力。

圖6：模型演化前後訓練資料分佈視覺化

圖7：模型演化前後模型決策邊界視覺化

新方向：圖上的資料增強

相比於計算機視覺和自然語言處理，圖挖掘領域中對資料增強的相關研究仍處於起步階段。本文的工作較早地探索瞭如何設計圖上的資料增強方法，研究表明，簡單的啟發式網路重連方法就可以作為有效的資料增強策略，對圖模型的最佳化起到一定的幫助。筆者認為，這項工作為圖資料探勘及演算法安全領域提供了新的研究思路。同時，結合自監督學習、圖對抗學習等新興的研究熱點，相信圖資料增強將會逐步體現出其在該領域重要的研究和應用價值。

周嘉俊 | 作者

鄧一雪 | 編輯

商務合作及投稿轉載｜swarma@swarma。org

◆ ◆ ◆

搜尋公眾號：集智俱樂部

加入“沒有圍牆的研究所”

讓蘋果砸得更猛烈些吧！