資料內(nèi)容：
1.5.1圖特征選擇
現(xiàn)實(shí)世界中的數(shù)據(jù)通常是高維度的，并且存在嘈雜的、不相關(guān)和多余的特征（或
維度），尤其是在考慮給定任務(wù)時(shí)。特征選擇旨在自動(dòng)地選擇一小部分特征，這些子
集具有最小的冗余度，但與學(xué)習(xí)目標(biāo)（例如在監(jiān)督學(xué)習(xí)中的類標(biāo)簽）有最大相關(guān)性。
在許多應(yīng)用中，原始特征對(duì)于知識(shí)提取和模型解釋至關(guān)重要。例如，在用于研究癌
癥的遺傳分析中，除了區(qū)分癌組織，鑒定誘導(dǎo)癌發(fā)生的基因（即原始特征）更重要。
在這些應(yīng)用中，特征選擇是優(yōu)先考慮的，因?yàn)樗梢员Ａ粼?/span>特征，并且它們的語(yǔ)
義通常為學(xué)習(xí)問(wèn)題提供關(guān)鍵的見(jiàn)解和解釋。傳統(tǒng)特征選擇假定數(shù)據(jù)實(shí)例是獨(dú)立同分
布的（i.i.d.）。然而，許多應(yīng)用中的數(shù)據(jù)樣本都鼠人在圖上，因此它們?cè)诒举|(zhì)上不是
獨(dú)立同分布的，這推動(dòng)了圖特征選擇的研究領(lǐng)域。給定圖g = {v,£},其中V是節(jié)
點(diǎn)集，是邊集，假設(shè)每個(gè)節(jié)點(diǎn)最初都與一組維度為d的特征T =
相關(guān)聯(lián)。圖特征選擇旨在從尸中選擇K個(gè)特征，其中K " 首先，在有監(jiān)督的
情況下對(duì)該問(wèn)題進(jìn)行了研究【5, 6】。這些方法使用線性分類器將所選特征映射到類別標(biāo)
簽，并引人圖正則化項(xiàng)，以捕獲結(jié)構(gòu)信息來(lái)選擇特征。特別地，該正則項(xiàng)旨在確保具
有所選特征的連接的節(jié)點(diǎn)可以映射到相似的標(biāo)簽中。然后，在無(wú)監(jiān)督的情況下對(duì)問(wèn)題
進(jìn)行了進(jìn)一步研究【7，&9j。在文獻(xiàn)［9］中，它首先從結(jié)構(gòu)信息中提取偽標(biāo)簽，然后用偽
標(biāo)簽充當(dāng)監(jiān)督信息指導(dǎo)特征選擇過(guò)程。在文獻(xiàn)⑺中，假定節(jié)點(diǎn)內(nèi)容和結(jié)構(gòu)信息都是
從一組高質(zhì)量的特征中生成的，而這些特征可以通過(guò)最大化生成過(guò)程獲得。在后續(xù)的
工作中，問(wèn)題從簡(jiǎn)單圖擴(kuò)展到復(fù)雜圖，例如動(dòng)態(tài)圖【1。}、多維圖皿］、有符號(hào)圖2.13］
和屬性圖網(wǎng)。第1章緒論
1.5.2圖表示學(xué)習(xí)
與圖特征選擇不同，圖表示學(xué)習(xí)是學(xué)習(xí)一組新的節(jié)點(diǎn)特征，它已經(jīng)被深入研究了
數(shù)十年，并且通過(guò)深度學(xué)習(xí)得到了極大的加速。本節(jié)將簡(jiǎn)要回顧從淺層模型到深層模
型的歷史過(guò)程。
在早期階段，圖表示學(xué)習(xí)已經(jīng)在譜聚類【15, 16｝、基于圖的降維［17,18,19］和矩陣分
解［0 18. 19］的背景下進(jìn)行了研究。在譜聚類中，數(shù)據(jù)點(diǎn)被視為圖的節(jié)點(diǎn)，然后聚類
問(wèn)題變成了將圖劃分為節(jié)點(diǎn)社區(qū)。譜聚類的關(guān)鍵一步是譜嵌入，它旨在將節(jié)點(diǎn)嵌入低
維空間中，在該空間中可以將傳統(tǒng)的聚類算法（如K-Means ）應(yīng)用于識(shí)別聚類。基
于圖的降維技術(shù)可以直接應(yīng)用于學(xué)習(xí)節(jié)點(diǎn)表示。這些方法通常基于數(shù)據(jù)樣本的原始特
征，使用預(yù)定義的距離（或相似度）函數(shù)構(gòu)建親和度圖，然后通過(guò)保留該親和度圖的
結(jié)構(gòu)信息學(xué)習(xí)節(jié)點(diǎn)表示。例如，IsoMap網(wǎng)通過(guò)測(cè)地線保留全局幾何，而LLEP9】和
eigenmap阿保留親和圖中的局部鄰域信息。因?yàn)榍笆龇椒ń?jīng)常需要在親和矩陣（鄰
接矩陣或拉普拉斯矩陣）上進(jìn)行特征分解，所以它們通常具有很高的計(jì)算復(fù)雜度。矩
陣是表示圖（例如鄰接矩陣和拉普拉斯矩陣）最流行的方法之一。矩陣分解可以自然
地應(yīng)用于學(xué)習(xí)節(jié)點(diǎn)表示。使用鄰接矩陣來(lái)表示圖作為示例，矩陣分解的目的是將節(jié)點(diǎn)
嵌入低維空間中，在該空間中可以利用新的節(jié)點(diǎn)表示重建鄰接矩陣。文檔語(yǔ)料庫(kù)可以
表示以文檔和單詞為節(jié)點(diǎn)的二分圖，如果一個(gè)單詞出現(xiàn)在某個(gè)文檔中，貝9單詞和對(duì)應(yīng)
的文檔之間存在一條邊。LSI已采用截?cái)嗥娈愔捣纸?/span>（truncated SVD）學(xué)習(xí)文檔和
單詞的表示形式網(wǎng)。在推薦系統(tǒng)中，用戶和商品之間的交互可以表示為二分圖。矩
陣分解既被用于推薦系統(tǒng)學(xué)習(xí)用戶和商品的表示⑵】，也被用于節(jié)點(diǎn)分類【22, 23］、鏈接
預(yù)測(cè)【2」,2切和社區(qū)檢測(cè)｛26｝等任務(wù)學(xué)習(xí)節(jié)點(diǎn)表示。實(shí)際上，后文介紹的一系列最新的
圖嵌入算法也可以歸為矩陣分解【27］。
