图机器学习中的数据增强技术
文稿整理者：張琳
審稿&修改：趙通
本人總結來自圣母大學的博士生趙通在深藍學院分享的“圖機器學習中的數據增強技術”公開課。通過介紹圖機器學習的概念，發展歷程等，以及分享兩篇文獻和最后回答提問完成本次公開課。
01
圖機器學習的概念及發展歷程
圖是一種比較特殊的數據格式，由節點和節點之間的邊構成，在圖數據上可以訓練圖機器學習模型。圖機器學習在實際工業的應用非常廣泛，比如節點的分類，節點的屬性預測，鏈路預測，圖異常檢測。
圖機器學習的手段具體通過圖表征學習實現，圖數據屬于非歐式結構，具有高維和數據稀疏的特點。圖數據的鄰接矩陣通常是稀疏矩陣，因此很難直接用這樣的高維數據在模型中學習。所以，通常用圖表征學習學習節點的表征，節點表征是低維的。經過圖表征學習模型，可以得到低維的節點/圖表征。有節點表征后，就可以用來完成下游任務。比如可以將其放入分類器中完成節點分類、異常檢測。如果把它放到回歸模型中，可以進行屬性預測，如果把兩個節點的表征一起放入一個分類器中就能鏈路預測。
圖機器學習近幾年是比較火的話題，以下是一個簡單的發展歷程。最開始，圖機器學習主要用的手段是矩陣分解，通過分解鄰接矩陣來得到節點的低維表征，一直到2012年都還有相關研究的論文。2014年從DeepWalk[1]開始，圖嵌入方法是圖機器學習的主流。直到2017年，圖神經網絡的提出進一步促進了圖深度學習的發展，圖神經網絡在各種圖任務上都表現出了非常優秀的效果。
圖神經網絡的輸入是圖數據以及可選的節點屬性，輸出的是每個節點的低維表征。圖神經網絡的核心是鄰域聚合，生成的節點表征基于鄰域節點。
在下圖中的左圖[2]，對于A節點，如果用兩層的神經節點計算的流程圖如右圖，每一層都卷積周圍鄰域信息。
圖神經網絡近幾年發展很好，2018年以后很多論文從不同角度切入嘗試提出更好的圖神經網絡。在這里我們主要討論從數據的角度去提升圖神經網絡，也就是去嘗試解決圖數據的稀疏性問題：大多圖數據呈現Power-law分布，有非常少的節點有非常多的鄰域，有非常多的節點有非常少的鄰域。這種分布導致對大量的稀疏節點不能充分學習。因此會導致過擬合的問題，模型的結果和泛化性會比較差。
下圖是一個簡單的電影打分預測的效果，縱軸是MAE，越低代表效果越好。可以看出，數據越多，模型的效果越好。
?
要得到更多的數據，就需要進行數據增強。維基百科對于數據增強的定義：通過添加已存在數據的略微修改的副本或從現有數據中新創建的合成數據來增加數據量的技術。它充當正則化器和有助于在訓練機器學習模型時減輕數據的過擬合問題。
數據增強在CV，NLP等成熟領域已經得到非常廣泛的運用。下圖是CV的例子[3]，數據集中只有一只貓的圖片，可以將這張圖片裁切或旋轉得到很多張貓的圖片，就可以減輕訓練中的過擬合問題。
同樣，在NLP中以同義詞替換為例[4]，在訓練過程中以It is awesome句子為例，在同義詞此表中發現awesome和amazing，awe-inspring，awing是可以替換的，將awesome換為amazing以后得到了新的句子It is amazing。如果在情感和表達的意思上差別不大，豐富了數據集。?
02
針對節點分類的圖數據增強
第一篇文獻：Data augmentation for graph neural networks [5]，這篇文章關注的是節點分類的圖數據增強，目的是提升節點分類的效果。
在圖上做數據增強，和CV，NLP不同的點是無法直接把傳統CV數據增強技術直接應用到圖上。比如CV中的圖片可以通過旋轉獲得新圖片，但圖數據的旋轉并沒有改變圖。另一個主要的問題是對于節點分類的任務，數據是通過節點和節點連接的。圖片分類中的圖片之間是沒有關系的，改變其中一個不會影響其他的，只會影響改變的圖片。但對于圖數據，節點的改變會影響該節點以及它的鄰域，甚至它鄰域的鄰域。因此對于這種互相依賴的數據，不能直接應用CV或NLP數據增強。在這個工作中，我們提出通過加減邊來進行圖數據增強，也就是加一些圖里沒有的邊，并從現有的邊里面刪除一些的操作。
以扎克的跆拳道俱樂部這個社交網絡為例。這個數據中節點的不同顏色代表了二分類的標簽。圖中有30多個節點，對每個節點隨機生成二維屬性，將其可視化如右圖。
屬性是隨機初始化的，將上述兩幅圖過一個隨機GCN層，可得到：
這里的GCN層沒有經過訓練，GCN層中的參數是隨機初始化的。將隨機初始化的特征過一個隨機初始化的GCN，可以看出，在上圖中的節點在二維平面上的分布已經有一些分離，左上角大部分是紅色點，右下角大部分是綠色點。這因為圖本身有非常強的同秩性(homophily)：原圖中紅色節點的大部分鄰域是紅色節點，綠色節點的大部分鄰域是綠色節點。同秩性導致不需訓練GCN就能對節點有一定的分離程度。
如果隨機挑6個類內的邊加上去，再隨機挑6個類間的邊拿掉：
上圖中較粗的藍線是新加的邊，藍色虛線表示去掉的邊。將改動過的圖還是用一樣的隨機屬性過隨機初始化的GCN：
可以發現它已經可以很不錯地分離了，所有的紅色點都在一邊，所有的綠色點都在另一邊。這是因為改動后的圖有了更強的的同秩性導致的。如果極端一點把所有相同類的節點都連在一起，將所有類間的邊全部刪掉：
所有的紅色點都會聚到一個點，所有的綠色點也會聚到另一個點。這個在論文中有證明。
但是這種加減邊要知道節點的標簽，它們是否屬于同一類，才能知道增加或刪除哪條邊。但在真正的學習過程中模型是不知道應該加哪條邊，刪哪條邊的。但好在圖機器學習可以幫助我們做的比隨機加減邊更好。
因此，我們提出了GAug-M模型：先改動圖，然后在此基礎上學習。在原圖上先訓練一個鏈路預測的模型，鏈路預測模型對所有的點對都可以得到兩個點之間存在邊的概率。對概率特別高但是現在圖中沒有邊的點對，加邊將它們連接起來；對概率特別低但現在圖中有邊的點對，刪掉這個邊。然后加邊的數量和刪邊的數量我們利用兩個超參控制改動程度的大小。這種簡單的操作就可以得到很好的節點分類效果，如下圖：
藍色的線代表類內的邊的數量，橙色的線代表類間的邊的數量，綠色的線代表它的節點分類的效果。可以看到，我們通過鏈路預測模型在加邊的情況下，主要加的是類內的邊。因為這個模型不是完美的，可能會有失誤加一些類間的邊，但藍色的線走的更快說明加了更多類內的邊，綠色的線隨著圖的同秩性越來越強也在不斷地增長。與之對比的是，如果隨機的加邊會怎樣？我們發現隨機加邊的話，更多的邊會是類間的邊，會損害圖的同秩性，將得到一個更差的節點分類結果。
通過GAug-M模型改圖得到一個更好或更容易訓練的圖，但它存在一個問題就是圖神經網絡很注重的inductive learning。當數據發生改變后，GAug-M需要重新訓練一個鏈路預測模型，然后利用這個模型修改圖數據，改完后重新訓練圖神經網絡。如果數據一直在變動，這個操作會非常昂貴，我們不希望這樣。所以雖然GAug-M在靜態數據中效果很好，針對這個問題，我們提出了GAug-O模型。
GAug-O是端到端的模型，當它訓練好以后，只要輸入一個圖，就能得到這個圖的節點分類預測結果。因此，它對于新加入的數據不需要去重新做一個完成的訓練。GAug-O的設計思路和之前模型的設計思路是一樣的，但它會稍微復雜一些。輸入的圖會先過一個鏈路預測模型，得到一個密集的邊存在概率矩陣，把它和原來的鄰接矩陣加在一起采樣，得到一個改過的鄰接矩陣，然后把改動過的鄰接矩陣輸入到圖神經網絡中得到節點分類。這個過程如下圖：
在GAug-M中，改動圖的方法是把概率最高的邊加上，概率最低的邊去掉，但是這個操作離散且不可導。在端到端的模型中這種操作會使得鏈路預測模型無法得到訓練。所以只能把確定性的加減邊變成取樣操作，然后把概率和原來的鄰接矩陣加起來，保證采樣結果不會太偏。得到加權重的概率后，在每一個點對的概率上進行伯努利取樣。由于伯努利取樣也是離散的，在實際設計方法時用的是Gumbel-softmax加straight-through的設計。通過這樣的技術手段實現整個模型端到端的訓練。
由于訓練中有兩個模型，即鏈路預測模型和節點分類模型，都是有參數需要訓練的。所以文章中使用兩個損失函數，包括節點分類的損失函數和鏈路預測的損失函數，通過同時訓練可以得到相互增強。
GAug-O和GAug-M一樣，訓練過程以及取樣的圖會有更多的類內的邊和更少的類間的邊。下圖的藍線是類內的邊在所有圖中所占的比例，可以發現隨著GAug-O訓練的進行，類內的邊數有一個非常快速的上漲，最終穩定在一個比較大的值，這意味著我們確實做到了增強圖的同秩性。
分析實驗結果時使用6個常見的公開數據集，數據增強的模型對使用哪種圖神經網絡沒有嚴格要求。使用4個常見的圖神經網絡，包括GCN，GSAGE，GAT和JK-NET，在6個數據集上都能得到很好的效果。
在數據稀疏時經常會面臨訓練數據或訓練用的標注數據減少的問題。所以，我們測試了在訓練數據更少的情況下模型的性能。可以看出訓練數據非常少的時候，模型有更明顯的提升。
03
針對鏈路預測的圖數據增強
第二篇文獻：Counterfactual graph learning for link prediction [7].
和節點分類不同，鏈路預測中數據增強的目的是得到新的邊。這樣就可以像其他的數據增強一樣，可以在更多的數據上訓練模型以避免過擬合問題。這篇文章提出生成反事實鏈路來嘗試學習對于邊的形成來說最重要的信息。反事實鏈路是在這篇文章中新定義的一個概念。
?
上圖是一個簡單的小社交網絡，假設圖中每個節點代表一個人，每條邊代表連接的兩個人是朋友，三個顏色代表相同顏色的人在一個小區居住。在圖中可以看出Alice和Adam兩個人是住在一個小區的朋友。
疑問：假如這兩個人不在同一個小區，還會不會是朋友？這個問題就是反事實問題，在因果推斷中經常使用。通過回答這個問題可以得知這兩個人是否因為居住在同一個小區才成為的朋友。在因果推斷中通常有定義干擾（treatment），一般是0和1，在這里定義為兩人是否居住在一個小區。這兩個人住在一個小區，結果是她們是朋友。
那么為了知道干擾（住在一個小區）對結果（他倆是朋友）是否有影響，我們需要知道這兩人如果不在一個小區里，還會不會是朋友？如果是，說明她們住不住一個小區對她們是不是朋友沒有影響，沒有因果關系；反之，住不住一個小區對她們是朋友有因果關系。但問題在于他們不住在一個小區還是不是朋友是不可觀測數據。
這也是因果推斷中的常見問題，可觀測到的結果只有一個，無法觀測當干預不同的時候結果是怎樣。因為這個世界上沒有第二個Alice和第二個Adam，除非有平行宇宙中存在同樣的二人而且不居住在一個小區，才能觀測二人是不是朋友。
在現實中無法這樣觀測，但我們又想知道這個結果，因為知道這個結果以后才能知道住在一個小區這個信息是不是有用信息。當我們知道住在一個小區是不是有用信息后，就能進行更好的鏈路預測。
在文章中提出反事實的邊近似問題的答案。對于Alice和Adam，確實無法知道她們不在一個小區的話還是不是朋友。但可以在社交網絡里找和Alice還有Adam分別最接近的人Helen和Bob，在社交網絡中可知Helen和Bob不住一個小區是怎么樣的。
在這個例子中，可以觀測到Helen和Bob不住在一個小區但他們是朋友（有邊相連）。我們把Helen和Bob之間邊的存在定義為Alice和Adam的反事實鏈路，這樣我們就相當于知道了Alice和Adam不住在一個小區的時候還會不會是朋友。我們無從驗證這種推理是否正確，但這種近似是能做到的最好結果。
有反事實鏈路后，可以讓機器學習的模型從可觀測的圖和生成的反事實鏈路一起學習。也就是說，把圖數據經過圖神經網絡編碼器，之后得到節點表征，將Alice和Adam的節點表征放在一起，然后把它和兩種煩擾（也就是二者在不在小區）的信息一起輸入解碼器。在本例子中事實鏈路和反事實鏈路都是1，那么解碼器會學到不管Alice和Adam在不在一個小區，她倆都是朋友。這樣，圖機器學習模型就能抓到更關鍵的信息。
從下表的結果可以看出鏈路預測的效果不錯，相較于目前SOTA的鏈路預測方法也可以達到非常多的提升。實驗中用5個公開數據集，除了圖學習中常見的Cora，CiteSeer，PubMed外，還有Facebook和OGB-DDI數據。
在OGB-DDI的官方的榜單中，本文提出的方法（CFLP）是第三名。CFLP和前兩名在參數量上相差很多，可以看出CFLP是一個比較輕量級的模型，所以能夠達到這樣的結果已經非常不錯。
04
Takeaways
（1）?圖數據增強從數據角度嘗試提升圖機器學習。雖然不是一個非常火熱的話題但也還是一個很有效的手段；
（2）?圖數據增強可以被用于各種圖機器學習的任務中，比如節點分類和鏈路預測；
由于它并沒有被過多的研究，圖數據增強還有非常多可以做的工作，未來的研究方向有：異構圖上的數據增強，圖數據增強的理論基礎，自動化數據增強手段等。
05
Q&A
（1） Q:請問隨機增加邊為什么出現了很多類間的邊？
A：這由圖本身標簽分布決定。在那個數據中如果把圖加滿變成一個任意兩點都有邊的全連接圖（clique），會發現在那個圖中大多數都是類間的邊。既然這個分布是這樣的，在隨機的時候就有更高的可能性去隨機到這個類間邊。
（2） Q:在異構圖和帶權圖中有用該技術做增強嗎？
A：在異構圖中做圖數據增強是很有意思的方向，但目前并沒有看到很多這方面的工作，這個方向是很值得學習和研究的。
（3） Q:圖數據增強和圖類比學習有何異同？
A：這里討論的數據增強針對的是有監督學習的工作，在有監督或者半監督的情況下更好的提升數據。而圖對比學習是自監督學習，通過對圖數據做一些改動，對比學習改動前和改動后的圖，使模型在無需監督的情況下學到節點的低維表征。在對比學習中也需要用到圖數據增強的手段，但自監督學習中的數據增強通常是一些擾動和噪音用來避免模型坍塌和簡單解，和監督學習中的數據增強是不一樣的。在監督學習中的數據增強一般會適當更復雜一些。
（4） Q:在圖分類任務里有沒有什么數據增強的思路呢？
A：很多節點分類數據增強可以用于圖分類任務中的數據增強，比如在第一個工作中用的大部分baseline都可以用在圖分類任務中。而且在圖分類任務中做數據增強的話其實會和在圖片中做數據增強更相似，因為在圖分類任務中的數據就是很多小圖，圖和圖之間是相互獨立的，沒有之前提到的數據之間相互依賴的問題。在這個情況下，很多CV和NLP中的數據增強技術手段都是可以拿來在圖分類中用的。
（5） Q:請問在鏈接預測任務中做數據增強，有思路嗎？
A：第二個工作就是連接預測中的數據增強。
（6） Q: Alice和Adam可以不在一個小區，然后改變Adam的屬性去數據增強嗎？Adam和其他鄰居的關系怎么處理？
A：不是通過改變Adam的屬性實現數據增強，而是找到它的反事實邊做數據增強。
（7） Q:第一個工作在異配網絡上效果應該更好吧？
A：第一個工作實驗中的Flickr和BlogC兩個數據應該屬于異配圖。在異配圖種GAug-M能得到更好的結果，GAug-O效果不如GAug-M。因為在異配圖中需要刪除非常多的邊才能得到高同質性，這種情況下由于GAug-M的刪減操作很方便，導致GAug-M在異配圖中效果更好。
（8） Q:有介紹模型庫如何的使用嗎？就是Gaug-M和Gaug-O模型庫代碼介紹哪里有呢？
A：代碼在github上。
Reference:
[1]Perozzi, Bryan, et al. "Deepwalk: Online learning of social representations."?KDD. 2014.
[2]Ying, Rex, et al. "Graph convolutional neural networks for web-scale recommender systems." KDD. 2018.
[3]https://www.kdnuggets.com/2018/05/data-augmentation-deep-learning-limited-data.html
[4]https://amitness.com/2020/05/data-augmentation-for-nlp/
[5]Zhao, Tong, et al. "Data Augmentation for Graph Neural Networks" AAAI. 2021.
[6]Zhao, Tong, et al. "Counterfactual Graph Learning for Link Prediction" Arxiv. 2021.
*感謝張琳同學的整理，非常感謝趙通博士對本文的審核。
點擊“閱讀原文”，直通公開課。
總結
以上是生活随笔為你收集整理的图机器学习中的数据增强技术的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 不确定下钻数的循环(部门下所属部门 多层
- 下一篇： CSS 让数字滑动显示