基于矩陣分解的圖嵌入

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

圖嵌入定義

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

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

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

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

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

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

圖嵌入分類

基于矩陣分解的圖嵌入

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

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

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

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

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

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

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

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

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

基于隨機游走的圖嵌入

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

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

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

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

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

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

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

基于自編碼器的圖嵌入

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

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

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

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

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

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

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

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

GraphSAGE 不是為每個節(jié)點訓練單獨的嵌入，而是通過采樣和聚合節(jié)點的局部鄰域特征訓練聚合器函數(shù)，同時學習每個節(jié)點鄰域的拓撲結(jié)構(gòu)及特征分布，生成嵌入表示。

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

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

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

DyRep將動態(tài)圖嵌入假設(shè)為圖的動態(tài)（拓撲演化）和圖上的動態(tài)交織演化（節(jié)點間的活動）的中介過程。

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

基于其他方法的圖嵌入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖嵌入任務(wù)

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

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

節(jié)點分類

節(jié)點分類任務(wù)是利用圖的拓撲結(jié)構(gòu)和節(jié)點特征確定每個節(jié)點所屬類別。節(jié)點分類任務(wù)可以利用已有標簽節(jié)點和連接關(guān)系來推斷丟失的標簽。 鏈接預(yù)測

鏈接預(yù)測任務(wù)用于預(yù)測兩個節(jié)點之間是否存在邊或者預(yù)測圖中未觀察到的鏈接，評估生成嵌入在保持拓撲結(jié)構(gòu)方面的性能。

聚類

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

異常檢測

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

可視化

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

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

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