圖嵌入模型綜述圖分析用于深入挖掘圖數(shù)據(jù)的內(nèi)在特征，然而圖作為非歐幾里德數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)分析方法普遍存在較高的計(jì)算量和空間開(kāi)銷(xiāo)。圖嵌入是一種解決圖分析問(wèn)題的有效方法，其將原始圖數(shù)據(jù)轉(zhuǎn)換到低維空間并保留關(guān)鍵信息，從而提升節(jié)點(diǎn)分類(lèi)、鏈接預(yù)測(cè)、節(jié)點(diǎn)聚類(lèi)等下游任務(wù)的性能。圖是復(fù)雜系統(tǒng)中常用的信息載體，可以表示現(xiàn)實(shí)中許多復(fù)雜關(guān)系，如社交網(wǎng)絡(luò)、犯罪網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。圖結(jié)構(gòu)作為一種非歐幾里德數(shù)據(jù)，很難直接應(yīng)用卷積神經(jīng)網(wǎng)絡(luò)和循環(huán) 神經(jīng)網(wǎng)絡(luò)。為了構(gòu)造用于圖數(shù)據(jù)挖掘的特征表示，圖嵌入將節(jié)點(diǎn)映射到低維空間，生成保留原始圖中某些重要信息的低維向量。目前，圖嵌入不僅在節(jié)點(diǎn)分類(lèi)、鏈接預(yù)測(cè)、節(jié)點(diǎn)聚類(lèi)、可視化等復(fù)雜網(wǎng)絡(luò)上的機(jī)器學(xué)習(xí)任務(wù)中獲得成功，還廣泛用于社交影響力建模、內(nèi)容推薦等現(xiàn)實(shí)任務(wù)。

圖嵌入定義

圖：表示為 ，其中 表示節(jié)點(diǎn)集， 表示邊集。

靜態(tài)圖：給定圖，如果節(jié)點(diǎn)和邊的不隨時(shí)間變化，圖 為靜態(tài)圖。

動(dòng)態(tài)圖：按時(shí)間分成一系列演化圖， 表示演化圖的數(shù)量，每個(gè)演化圖表示時(shí)刻的狀態(tài)。

一階相似度：節(jié)點(diǎn)之間的成對(duì)鄰近度。

二階相似度：節(jié)點(diǎn)鄰域結(jié)構(gòu)的相似度。

圖嵌入 ：將每個(gè)節(jié)點(diǎn)映射成低維向量表示，保留了原始圖中某些關(guān)鍵信息。

圖嵌入分類(lèi)

基于矩陣分解的圖嵌入

基于矩陣分解的圖嵌入通過(guò)分解節(jié)點(diǎn)關(guān)系矩陣獲得低維嵌入。不同的關(guān)系矩陣采用的分解方法不同 ，例如鄰接矩陣通常使用奇異值分解（SVD）的方法生成節(jié)點(diǎn)嵌入，而屬性矩陣通常使用特征值分解的方法。

基于矩陣分解的靜態(tài)圖嵌入

基于矩陣分解的靜態(tài)圖嵌入模型對(duì)節(jié)點(diǎn)關(guān)聯(lián)信息矩陣和屬性信息矩陣進(jìn)行特征分解，然后將分解得到的屬性嵌入和結(jié)構(gòu)嵌入進(jìn)行融合，生成節(jié)點(diǎn)的低維嵌入表示。

局部線性映射LLE將每個(gè)節(jié)點(diǎn)表示為相鄰節(jié)點(diǎn)的線性組合，構(gòu)造鄰域保持映射。具體實(shí)現(xiàn)分為三步：

以某種度量方式（如歐氏距離）選擇 k個(gè)鄰近節(jié)點(diǎn)；

由 k個(gè)近鄰線性加權(quán)重構(gòu)節(jié)點(diǎn)，并最小化節(jié)點(diǎn)重建誤差獲得最優(yōu)權(quán)重；

最小化最優(yōu)權(quán)重構(gòu)建的目標(biāo)函數(shù)生成 Y

基于矩陣分解的動(dòng)態(tài)圖嵌入

基于矩陣分解的動(dòng)態(tài)圖方法利用特征分解構(gòu)造圖的高階相似度矩陣，然后利用矩陣攝動(dòng)理論更新圖的動(dòng)態(tài)信息。DANE采用分布式框架：離線部分，采用最大化相關(guān)性的方法捕捉圖結(jié)構(gòu)和節(jié)點(diǎn)屬性的依賴(lài)關(guān)系；在線部分，使用矩陣攝動(dòng)理論更新嵌入的特征值和特征向量。

基于隨機(jī)游走的圖嵌入

受word2vec的啟發(fā)，基于隨機(jī)游走的圖嵌入方法將節(jié)點(diǎn)轉(zhuǎn)化為詞，將隨機(jī)游走序列作為句子，利用Skip-Gram 生成節(jié)點(diǎn)的嵌入向量。隨機(jī)游走法可以保留圖的結(jié)構(gòu)特性，并且在無(wú)法完整觀察的大型圖上仍有不錯(cuò)的表現(xiàn)。

基于隨機(jī)游走的靜態(tài)圖嵌入

基于隨機(jī)游走的靜態(tài)圖嵌入模型通過(guò)隨機(jī)游走獲得訓(xùn)練語(yǔ)料庫(kù)，然后將語(yǔ)料庫(kù)集成到 Skip-Gram 獲得節(jié)點(diǎn)的低維嵌入表示。Deepwalk使用隨機(jī)游走對(duì)節(jié)點(diǎn)進(jìn)行采樣，生成節(jié)點(diǎn)序列，再通過(guò) Skip-Gram 最大化節(jié)點(diǎn)序列中窗口范圍內(nèi)節(jié)點(diǎn)之間的共現(xiàn)概率。

Deepwalk 不僅在數(shù)據(jù)量較少時(shí)有較好的表現(xiàn)，還可以擴(kuò)展到大型圖的表示學(xué)習(xí)。由于優(yōu)化過(guò)程中未使用明確的目標(biāo)函數(shù)，使得模型保持網(wǎng)絡(luò)結(jié)構(gòu)的能力受到限制。

node2vec在 Deepwalk的基礎(chǔ)上，引入有偏的隨機(jī)游走，增加鄰域搜索的靈活性，生成質(zhì)量更高、信息更多的嵌入表示。通過(guò)設(shè)置 p 和 q 兩個(gè)參數(shù)，平衡廣度優(yōu)先搜索和深度優(yōu)先搜索策略，使生成的嵌入能夠保持社區(qū)結(jié)構(gòu)等價(jià)性或鄰域結(jié)構(gòu)等價(jià)性。

基于隨機(jī)游走的動(dòng)態(tài)圖嵌入

CTDNE利用時(shí)間隨機(jī)游走從連續(xù)型動(dòng)態(tài)圖中學(xué)習(xí)包含時(shí)間信息的嵌入表示。，CTDNE 采用的時(shí)間隨機(jī)游走與靜態(tài)圖方法相似，但約束每個(gè)隨機(jī)游走符合邊出現(xiàn)的時(shí)間順序，即邊的遍歷必須按照時(shí)間遞增的順序，由于每條邊包含多個(gè)時(shí)間戳，使得同一節(jié)點(diǎn)可能在游走中出現(xiàn)多次。

基于自編碼器的圖嵌入

自編碼器使隱藏層學(xué)習(xí)到的表示維度小于輸入數(shù)據(jù)，即對(duì)原始數(shù)據(jù)進(jìn)行降維。基于自編碼器的圖嵌入方法使用自編碼器對(duì)圖的非線性結(jié)構(gòu)建模，生成圖的低維嵌入表示。 基于自編碼器的靜態(tài)圖嵌入

基于自編碼器的圖嵌入方法起源于使用稀疏自編碼器的 GraphEncoder。其基本思想是將歸一化的圖相似度矩陣作為節(jié)點(diǎn)原始特征輸入到稀疏自編碼器中進(jìn)行分層預(yù)訓(xùn)練，使生成的低維非線性嵌入可以近似地重建輸入矩陣并保留稀疏特性。

基于自編碼器的動(dòng)態(tài)圖嵌入

基于自編碼器的動(dòng)態(tài)圖方法將每個(gè)時(shí)刻訓(xùn)練的參數(shù)作為下一時(shí)刻自編碼器的初始值，從而在一定程度上保持生成嵌入的穩(wěn)定性，提高模型的計(jì)算效率。

基于圖神經(jīng)網(wǎng)絡(luò)的圖嵌入

圖神經(jīng)網(wǎng)絡(luò)（GNN）是專(zhuān)門(mén)處理圖數(shù)據(jù)的深度模型，其利用節(jié)點(diǎn)間的消息傳遞來(lái)捕捉某種依賴(lài)關(guān)系，使生成的嵌入可以保留任意深度的鄰域信息。

基于圖神經(jīng)網(wǎng)絡(luò)的靜態(tài)圖嵌入

基于 GNN的靜態(tài)圖模型聚合節(jié)點(diǎn)鄰域的嵌入并不斷迭代更新，利用當(dāng)前的嵌入及上一次迭代的嵌入生成新的嵌入表示。

GraphSAGE 不是為每個(gè)節(jié)點(diǎn)訓(xùn)練單獨(dú)的嵌入，而是通過(guò)采樣和聚合節(jié)點(diǎn)的局部鄰域特征訓(xùn)練聚合器函數(shù)，同時(shí)學(xué)習(xí)每個(gè)節(jié)點(diǎn)鄰域的拓?fù)浣Y(jié)構(gòu)及特征分布，生成嵌入表示。

圖注意力網(wǎng)絡(luò)（graph attention network，GAT）在 GCN 的基礎(chǔ)上引入注意力機(jī)制，對(duì)鄰近節(jié)點(diǎn)特征加權(quán)求和，分配不同的權(quán)值。

基于圖神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)圖嵌入

基于 GNN的動(dòng)態(tài)圖模型通常在靜態(tài)圖模型的基礎(chǔ)上，引入一種循環(huán)機(jī)制更新網(wǎng)絡(luò)參數(shù)，實(shí)現(xiàn)動(dòng)態(tài)過(guò)程的建模，使生成低維嵌入可以有效保留圖的動(dòng)態(tài)演化信息。

DyRep將動(dòng)態(tài)圖嵌入假設(shè)為圖的動(dòng)態(tài)（拓?fù)溲莼┖蛨D上的動(dòng)態(tài)交織演化（節(jié)點(diǎn)間的活動(dòng)）的中介過(guò)程。

DySAT通過(guò)鄰域結(jié)構(gòu)和時(shí)間兩個(gè)維度的聯(lián)合自注意力來(lái)計(jì)算節(jié)點(diǎn)嵌入，結(jié)構(gòu)注意力塊通過(guò)自注意聚集和堆疊從每個(gè)節(jié)點(diǎn)局部鄰域中提取特征。

基于其他方法的圖嵌入

LINE同樣定義了一階相似度和二階相似度函數(shù)，并對(duì)其進(jìn)行優(yōu)化。一階相似度用于保持鄰接矩陣和嵌入表示的點(diǎn)積接近，二階相似度用于保持上下文節(jié)點(diǎn)的相似性。LINE 分別優(yōu)化一階和二階相似度的目標(biāo)函數(shù)，然后將生成的嵌入向量進(jìn)行拼接。

數(shù)據(jù)集與應(yīng)用

靜態(tài)圖嵌入數(shù)據(jù)集

20-Newsgroup：由大約 20 000 個(gè)新聞組文檔構(gòu)成的數(shù)據(jù)集。這些文檔根據(jù)主題劃分成 20 個(gè)組，每個(gè)文檔表示為每個(gè)詞的 TF-IDF 分?jǐn)?shù)向量，構(gòu)建余弦相似圖。為了證明聚類(lèi)算法的穩(wěn)健性，分別從 3、6和 9 個(gè)不同的新聞組構(gòu)建了 3 個(gè)圖。

Flickr：由照片分享網(wǎng)站 Flickr 上的用戶(hù)組成的網(wǎng)絡(luò)。網(wǎng)絡(luò)中的邊指示用戶(hù)之間的聯(lián)系關(guān)系。標(biāo)簽指示用戶(hù)的興趣組（例如黑白色攝影）。

DBLP：引文網(wǎng)絡(luò)數(shù)據(jù)集，每個(gè)頂點(diǎn)表示一個(gè)作者，從一個(gè)作者到另一個(gè)作者的參考文獻(xiàn)數(shù)量由這兩個(gè)作者之間的邊權(quán)重來(lái)記錄。標(biāo)簽上標(biāo)明了研究人員發(fā)表研究成果的 4個(gè)領(lǐng)域。

YouTube：YouTube 視頻分享網(wǎng)站用戶(hù)之間的社交網(wǎng)絡(luò)。標(biāo)簽代表了喜歡視頻類(lèi)型（例如動(dòng)漫視頻）的觀眾群體。

Wikipedia：網(wǎng)頁(yè)共現(xiàn)網(wǎng)絡(luò)，節(jié)點(diǎn)表示網(wǎng)頁(yè)，邊表示網(wǎng)頁(yè)之間的超鏈接。Wikipedia數(shù)據(jù)集的 TF-IDF矩陣是描述節(jié)點(diǎn)特征的文本信息，節(jié)點(diǎn)標(biāo)簽是網(wǎng)頁(yè)的類(lèi)別。

Cora、CiteSeer、Pubmed：標(biāo)準(zhǔn)的引文網(wǎng)絡(luò)基準(zhǔn)數(shù)據(jù)集，節(jié)點(diǎn)表示論文，邊表示一篇論文對(duì)另一篇論文的引用。節(jié)點(diǎn)特征是論文的詞袋表示，節(jié)點(diǎn)標(biāo)簽是論文的學(xué)術(shù)主題。

Yelp：本地商業(yè)評(píng)論和社交網(wǎng)站，用戶(hù)可以提交對(duì)商家的評(píng)論，并與其他人交流。由于缺乏標(biāo)簽信息，該數(shù)據(jù)集常用于鏈接預(yù)測(cè)。

動(dòng)態(tài)圖嵌入數(shù)據(jù)集

Epinions：產(chǎn)品評(píng)論網(wǎng)站數(shù)據(jù)集，基于評(píng)論的詞袋模型生成節(jié)點(diǎn)屬性，以用戶(hù)評(píng)論的主要類(lèi)別作為類(lèi)別標(biāo)簽。該數(shù)據(jù)集有 16個(gè)時(shí)間戳。

Hep-th：高能物理理論會(huì)議研究人員的合作網(wǎng)絡(luò)，原始數(shù)據(jù)集包含 1993 年 1 月至 2003 年 4 月期間高能物理理論會(huì)議的論文摘要。

AS（autonomous systems）：由邊界網(wǎng)關(guān)協(xié)議日志構(gòu)建的用戶(hù)通信網(wǎng)絡(luò)。該數(shù)據(jù)集包含從 1997年 11月 8 日到 2000 年 1 月 2 日的 733 條通信記錄，通常按照年份將這些記錄劃分為不同快照。

Enron：Enron 公司員工之間的電子郵件通信網(wǎng)絡(luò)。該數(shù)據(jù)集包含 1999 年 1 月至 2002 年 7 月期間公司員工之間的電子郵件。

UCI：加州大學(xué)在線學(xué)生社區(qū)用戶(hù)之間的通信網(wǎng)絡(luò)。節(jié)點(diǎn)表示用戶(hù)，用戶(hù)之間的消息通信表示邊緣。每條邊攜帶的時(shí)間指示用戶(hù)何時(shí)通信。

圖嵌入任務(wù)

網(wǎng)絡(luò)重構(gòu)

網(wǎng)絡(luò)重構(gòu)任務(wù)是利用學(xué)習(xí)到節(jié)點(diǎn)低維向量表示重新構(gòu)建原始圖的拓?fù)浣Y(jié)構(gòu)，評(píng)估生成的嵌入保持圖結(jié)構(gòu)信息的能力。好的網(wǎng)絡(luò)嵌入方法能夠捕捉到具有網(wǎng)絡(luò)結(jié)構(gòu)信息的嵌入表示，從而能夠很好地重構(gòu)網(wǎng)絡(luò)。

節(jié)點(diǎn)分類(lèi)

節(jié)點(diǎn)分類(lèi)任務(wù)是利用圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)特征確定每個(gè)節(jié)點(diǎn)所屬類(lèi)別。節(jié)點(diǎn)分類(lèi)任務(wù)可以利用已有標(biāo)簽節(jié)點(diǎn)和連接關(guān)系來(lái)推斷丟失的標(biāo)簽。 鏈接預(yù)測(cè)

鏈接預(yù)測(cè)任務(wù)用于預(yù)測(cè)兩個(gè)節(jié)點(diǎn)之間是否存在邊或者預(yù)測(cè)圖中未觀察到的鏈接，評(píng)估生成嵌入在保持拓?fù)浣Y(jié)構(gòu)方面的性能。

聚類(lèi)

聚類(lèi)任務(wù)采用無(wú)監(jiān)督的方式將圖劃分為若干個(gè)社區(qū)，使屬于同一社區(qū)的節(jié)點(diǎn)具有更多相似特性。將生成的嵌入表示進(jìn)行聚類(lèi)，使具有相似特性的節(jié)點(diǎn)盡可能在同一社區(qū)。在。

異常檢測(cè)

異常檢測(cè)任務(wù)用于識(shí)別圖中的“非正常”結(jié)構(gòu)，通常包括異常節(jié)點(diǎn)檢測(cè)、異常邊緣檢測(cè)和異常變化檢測(cè)。圖數(shù)據(jù)的異常檢測(cè)主要是找出與正常數(shù)據(jù)集差異較大的離群點(diǎn)（異常點(diǎn)）。

可視化

可視化任務(wù)是對(duì)嵌入進(jìn)行降維和可視化，從而直觀地觀察原始圖中某些特征。對(duì)于可視化任務(wù)，好的嵌入表示在二維圖像中相同或相近的節(jié)點(diǎn)彼此接近，不同的節(jié)點(diǎn)彼此分離。

原文標(biāo)題：圖嵌入模型綜述：方法、數(shù)據(jù)集和應(yīng)用

文章出處：【微信公眾號(hào)：Imagination Tech】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。