劉彥北，周敬濤

（天津工業(yè)大學電子與信息工程學院，天津 300387）

圖的應用是非常廣泛的，現實生活中處處是圖的場景。近些年，圖神經網絡的方法得到了廣泛的關注，以傳統(tǒng)圖結構為基礎，在圖表示學習方面取得了很大的成果。然而隨著圖神經網絡應用的不斷擴展，傳統(tǒng)圖結構定義的點與點成對關系已經無法滿足描述現實情況中數據之間高階復雜關系的要求，傳統(tǒng)圖表示學習在消息傳遞方面也面臨挑戰(zhàn)。

相對于普通圖而言，超圖可以更加準確地描述存在多元關聯的對象之間的關系。超邊構建非成對關系，因此，超圖很適合用于描述高階數據相關性，同時在學習多模態(tài)和異構數據上都有建樹。超圖學習最早由Sch?lkopf 等[1]提出，用于處理超圖結構，減小超圖上連接性緊密點的標簽的差異。Metaxas 等[2]提出超圖學習被應用于視頻對象分割任務。Huang 等[3]利用超圖結構對圖像關系進行建模，并且對圖像排序進行轉導推理。Gao 等[4]引入l2 正則化來學習最優(yōu)超邊權值。Hwang 等[5]通過假設高度相關的超邊緣應該具有相似的權重，進一步探討了超邊緣之間的相關性。之后Gao等[6]引入了多超圖結構，并且為不同的子超圖分配不同的權重，以此在處理多模態(tài)數據的基礎上應對不同的模式。Jiang 等[7]提出了動態(tài)超圖神經網絡DHGNN，由動態(tài)超圖構造（DHG）和超圖卷（HGC）2 個模塊構成，通過不斷更新超圖結構來最終達到最貼切數據的學習表示。Bai[8]在圖神經網絡中引入了2 個端到端的可訓練操作內容，即超圖卷積和超圖注意，用于有效學習高階圖結構數據上的深度嵌入。Feng 等[9]設計了一種超邊緣卷積，在超圖神經網絡HGNN 中學習高階數據相關性。Zhang 等[10]開發(fā)了一種新的基于自注意的圖神經網絡，稱為Hyper-SAGNN，適用于具有可變超邊大小的同質和異質超圖。Xia 等[11]將超圖網絡與自監(jiān)督學習相結合并應用于會話推薦任務。Lee 等[12]采用個性化的重加權方案進行節(jié)點跳躍，通過概率的形式重新解釋超圖上的隨機游走概念。

傳統(tǒng)的消息傳遞算法是在圖神經網絡上展開的。文獻[13-14]提出了譜圖卷積神經網絡；文獻[15-16]提出了消息傳遞算法；Dai 等[17]通過遞歸神經網絡進行鄰居聚合；Veliˇckovic＇等[18]在圖神經網絡的基礎上引入了注意機制；AbuElHaija 等[19]提出了隨機游走；Gilmer 等[20]使用了邊緣特征；文獻[21-24]試圖增加跳躍的連接步數來改進傳統(tǒng)的消息傳遞算法；Xu 等[25]將消息傳遞與聚合方案相結合。然而，上述工作的消息傳遞層數依然是有限的。Li 等[26]通過合作訓練和自我訓練相結合的方式來促進模型訓練。Eliav 等[27]也有類似的表現，取得的改進效果接近于其他的半監(jiān)督分類模型。文獻[28-29] 通過結合殘差連接和批量歸一化避免了過擬合問題。Gaseiger[30]使用圖像卷積的關系網絡（GCN）和網頁排名得出一種改進的傳播方案即基于個性化的網頁排名。Sun 等[31]利用將AdaBoost 與網絡合并的方法，構建新圖卷積網絡AdaGCN，從根節(jié)點的高階鄰居中提取信息。綜上所述，超圖學習需要在增大學習領域范圍的同時，保持對根節(jié)點的適當關注。

本文提出了一種使用個性化網頁排名PageRank代替?zhèn)鹘y(tǒng)鄰居聚合的傳播方案，該算法增加了傳播過程傳回根節(jié)點的概率，PageRank 算法在對根節(jié)點的局部領域進行編碼時，能夠在擴大學習領域的同時保持對根節(jié)點信息的關注。模型的傳播方案允許網絡層數逐漸增多，理論上可以接近無限多層，而且不會導致過平滑。除該優(yōu)勢之外，本算法當中的傳播算法與神經網絡獨立存在，因此，可以在不改變原有神經網絡的基礎上來實現更廣的傳播范圍，使模型具有一定的推廣性。與前人所述PageRank 與傳統(tǒng)圖卷積網絡方法相結合的算法PPNP[30]相比，本文提出的算法是將PageRank與超圖卷積網絡相結合克服各自局限性的模型HGNNP，優(yōu)勢在于：利用超圖適合處理數據之間高階關系的特點，有效學習根節(jié)點周圍更多類型的連接信息；使用PageRank 思想在根節(jié)點周圍實現更廣的學習領域，同時不丟失根節(jié)點本身的信息。為驗證所提出的HGNNP 算法的有效性，本文進行了視覺對象分類任務實驗，并與目前流行的方法相比較，以期能夠在較深的卷積網絡層數下較好地處理多模態(tài)數據的高階關系。

1 模型及方法

本文模型HGNNP 將超圖神經網絡與個性網頁排名相結合，包含超圖構建、超圖卷積網絡、個性化網頁排名機制等內容。

1.1 超圖構建

超圖學習是一個很寬泛的概念，其中最基礎的是超圖構造。通常情況下，超圖被定義為G=（V，E，W）。其中：節(jié)點集為V，包含了超圖上所有的頂點；超邊集為E，包含由任意個關聯頂點構成的邊；W 則是由每條超邊的權重構成的權重集，是由超邊權重構成的對角矩陣；而超圖的關聯矩陣H 可以由|V|×|E|來表示；對于任何一個屬于V 的節(jié)點v 而言，節(jié)點的度被定義為d（v）=h（v，e）；對于一個屬于E 的超邊e而言，邊的度被定義為δ（e）=；那么很顯然，De和Dv表示超邊度和節(jié)點度的對角線矩陣。

普通圖描述的是邊和成對節(jié)點之間的關系，超圖的關聯矩陣描述的是超邊與節(jié)點之間的關系。特殊情況下，當超圖中所有的超邊包含的節(jié)點個數都為K 個時，稱該超圖為K 均勻超圖。還應當注意的點是，在超圖構建的過程中，即使超邊所包含的點個數是相同的，超邊的類型也會因為所包含節(jié)點類型的不同而不同，從這里也能看出超圖適用于處理多模態(tài)數據。

1.2 超圖卷積網絡

超圖卷積網絡（HGNN）是在構建超圖的基礎上捕捉節(jié)點之間的高階關系，是由傳統(tǒng)圖卷積網絡發(fā)展而來的。

首先回顧下普通圖的卷積網絡（GCN），傳統(tǒng)的GCN網絡如式（1）所示：

對于超圖卷積網絡而言，輸入網絡數據集通常分為訓練數據集和測試數據集。在輸入網絡時，與傳統(tǒng)圖相同的地方是都使用了最初始的數據特征，不同的地方在于關聯矩陣的形成。超圖利用多模態(tài)數據集的復雜相關性構造了很多超邊緣結構群，通過超邊生成的方式（hyperedge generation）將其連接起來，進而生成鄰接矩陣H，然后將新生成的鄰接矩陣與節(jié)點特征輸入超圖神經網絡，得到最后的標簽特征。由此可知，一個超邊卷積層的公式為：

式中：X(l+1)代表第l+1 層節(jié)點的特征；σ 代表非線性激活函數。超圖神經網絡基于超圖上的譜卷積，在式（2）中實現了節(jié)點—邊—節(jié)點特征的轉換，利用超邊特征聚合和鄰居節(jié)點特征融合，捕捉節(jié)點數據之間的高階相關性。其中，濾波器矩陣θ(l)與初始的節(jié)點特征X(l)相乘進行濾波處理，改變特征的維度；然后根據超邊的特性，將節(jié)點特征匯聚成超邊特征，這一步驟通過與的乘法實現；然后以乘以關聯矩陣He的方式，將與根節(jié)點相關的超邊特征重新匯聚成節(jié)點特征，Dv和De起到歸一化的作用；最后通過非線性激活輸出最終結果。

在超圖神經網絡中，超圖構造首先要考慮超邊的構建，如圖1 所示，網絡模型根據節(jié)點之間的距離來構造關聯矩陣，進而形成超邊。普通圖中，邊只考慮兩點之間的聯系，而超邊衡量了多個節(jié)點之間的關系。

圖1 超邊生成Fig.1 Hyperedge generation

1.3 網頁排名機制PageRank

PageRank 來源于網頁鏈接之間的隨機游走機制，使用戶可以點擊鏈接跳轉到新的頁面，不至于一直在本網頁停留，也不至于鏈接不到新的網頁，使用戶可以一直瀏覽自己所感興趣的網頁內容，類似于學習到了用戶的興趣范圍，其傳播機制如圖2 所示。

圖2 PageRank 傳播機制Fig.2 Propagation mechanism of PageRank

由圖2 可知，對于根節(jié)點x1來說，信息的傳播在相連的節(jié)點之間進行，從一個頂點到下一個頂點游走的過程中，有α 的概率回歸它本身，有1-α 的概率傳遞給x2、x3、x4，同時下一次傳遞時，這3 個頂點也是有α 的概率傳回x1。這個傳播過程是以x1為重心的，即以它作為本次傳播的根節(jié)點，最終學習到的信息為該節(jié)點的信息表示。

如前文提到的，可以利用網頁排名機制PageRank來避免根節(jié)點信息的丟失。為了更方便快速地實現本模型的設計目的，引入一個PageRank 的變體，即將根節(jié)點考慮在內的個性化PageRank。與普通的網頁排名機制不同，個性化PageRank 是針對個人而言的PageRank，每次重新游走的時候，都是從根節(jié)點用戶節(jié)點u 開始，在學習節(jié)點u 的信息時，該節(jié)點初始化為1，其他節(jié)點初始化為0。

個性化PageRank 的進階公式為：

式中：ix為根結點特征向量；為加上歸一化以及自循環(huán)的鄰接矩陣；πppr（ix）為傳播之后的特征；α 為傳播概率。在這里，先將網頁排名機制與圖網絡的傳播過程聯合在一起，得到的公式為：

式中：X 為特征矩陣；fθ（x）為參數為θ 的對數據特征進行預處理的神經網絡。由式（5）可知，對節(jié)點標簽進行預測的神經網絡與傳播機制是分割開來的，神經網絡的結構以及層數深度是獨立于傳播算法存在的。由此可以靈活地改變模型中神經網絡的模型，可以用任意的傳播矩陣來替換式（5）的。本文對式（5）使用了簡便的形式以降低模型的計算復雜度。此外HGNNP模型訓練是端到端的。

1.4 基于PageRank 算法的超圖神經網絡

HGNNP 模型如圖3 所示。

圖3 HGNNP 模型示意圖Fig.3 Schematic diagram of HGNNP model

由圖3 可知，初始數據經過超邊聚集（hyperedge generation）生成超圖的關聯矩陣H，該關聯矩陣描述的是超邊與它包含的多個節(jié)點之間的連接信息，通過該方法生成了不同于傳統(tǒng)圖的“連接信息”。神經網絡的輸入不僅需要連接信息，還需要節(jié)點的屬性信息。因此，將生成的關聯矩陣H 與原始的節(jié)點特征共同輸入超圖神經網絡。該網絡的作用就是利用超圖以及超邊的特性來對原始的節(jié)點特征進行重新表示學習。

具體步驟為輸入的節(jié)點特征利用關聯矩陣中超邊與節(jié)點的關聯信息，依據超圖神經網絡的網絡模型（hypergraph neural networks），經過一層點—邊—點的特征變化過程，不斷迭代更新以得到最終的學習表示，其中“邊”指的是超邊特征。節(jié)點特征經過節(jié)點特征轉換、超邊特征聚合、節(jié)點特征聚合過程得到新的節(jié)點學習表示，再經過非線性激活函數，最終得到初始嵌入節(jié)點特征hi。在初始嵌入節(jié)點特征基礎之上，使用個性化PageRank 機制進行信息傳播，吸收周圍鄰居節(jié)點的信息；同時以一定的概率回到根節(jié)點本身，每經歷一層的信息傳播之后，再進入超圖神經網絡進行下一次特征學習，直到得到最終學習表示。

具體來講，處理之后的節(jié)點特征結合PageRank進行信息傳播，該傳播機制使得節(jié)點信息有α 的概率傳回本身，有1-α 的概率再次進入超圖神經網絡中，正是這個概率保證了一定程度上可以再次匯聚根節(jié)點本身的信息，防止在吸收周圍的鄰居節(jié)點信息時學習范圍過廣或層數過深使得根節(jié)點的信息被丟失掉。因此，使得模型能夠在有效吸收周圍鄰居節(jié)點信息的同時，一定程度上保留根節(jié)點的信息。

上述過程有效地防止了模型層數過深時過擬合、節(jié)點學習表示趨近于穩(wěn)定值和模型泛化能力弱的情況。具體表現為，當學習層數過深時，節(jié)點的學習表示會趨向該圖的極限分布，節(jié)點表示不再取決于根節(jié)點和其周圍的鄰居信息，而取決于整個圖本身，而模型使用的網頁排名機制解決了這個問題。

本文模型結合超圖神經網絡和網頁排名機制，得到HGNNP 的整體公式：

式中：X(l+1)為下一層的節(jié)點特征；α 為傳播概率；Dv和De為節(jié)點和超邊的度矩陣，起到了歸一化的作用；X(0)不是初始的節(jié)點特征，而是經過超圖神經網絡預處理之后的節(jié)點特征hi；其余字符含義不變。

對比超圖神經網絡，HGNNP 每一次傳播不是直接傳播到相鄰節(jié)點，而是有α 的概率回歸到本身，本質上傳播機制發(fā)生了改變。對比PageRank 算法和傳統(tǒng)圖網絡結合的方法，神經網絡模型引入了超圖和超邊的概念，根本區(qū)別是卷積網絡中的連接信息發(fā)生改變，多個節(jié)點相連的超邊的存在使得節(jié)點表示學習中節(jié)點信息學習得更為全面準確。

綜上所述，HGNNP 將超圖神經網絡與PageRank算法相結合，不僅解決了傳統(tǒng)圖學習算法無法處理的高階數據相關性的問題，而且可以利用特定的傳播機制加深模型的網絡層數，以使網絡模型更全面更準確地學習節(jié)點的信息，在處理分類問題和預測問題時，實驗效果會更好。

2 實驗和結果

2.1 數據集和實驗設置

為了驗證本文所提出的HGNNP 模型，實驗利用了2 個視覺對象分類的數據集，包括普林斯頓大學的ModelNet40 數據集以及臺灣大學的NTU 3D 模型數據集。表1 為2 個數據集的節(jié)點種類個數、訓練和測試的節(jié)點個數以及總共的節(jié)點個數。需要注意的是，ModelNet40 數據集由來自40 個流行類別的12 311 個對象組成，并應用了相同的訓練/測試分割。其中，9 843 個物體用于訓練，2 468 個物體用于測試。NTU數據集由來自67 個類別的2 012 個3D 形狀組成，包括汽車、椅子、國際象棋、芯片、時鐘、杯子、門、框架、筆、植物葉等。在NTU 數據集中，80%的數據用于訓練，其他20%的數據用于測試。本實驗采用2 種提取特征的方法MVCNN（用于3D 形狀識別的多視圖卷積神經網絡）和GVCNN（用于3D 形狀識別的群視圖卷積神經網絡）在該三維模型數據集上提取特征，這2種方法在三維對象表示上有著非常好的性能表現。

表1 ModelNet40 和NTU 數據集的詳細信息Tab.1 Detailed information of ModelNet40 and NTU datasets

為了與傳統(tǒng)圖神經網絡做對比，利用節(jié)點之間的距離來構建圖結構。在構造超圖步驟時使用2 種方法：一種是依據KNN（K 最鄰近分類算法）思想選取10個離根節(jié)點最近的點構成超邊，進而構建超圖；另外一種是在數據特征呈現多模態(tài)時，構建超圖關聯矩陣，并將多個不同屬性特征的關聯矩陣拼接在一起，構成多模態(tài)特征的超圖。

在上述2 個數據集完成半監(jiān)督分類實驗的基礎之上，對傳播概率α 和傳播層數N 進行控制變量和消融實驗，以更直觀地判斷出2 個超參數對模型效果的影響。

2.2 半監(jiān)督分類

在ModelNet40 和NTU 數據集上分別實現半監(jiān)督分類實驗，評價標準主要是分類的準確率。其中，每一個數據集在提取特征時都使用MVCNN 和GVCNN 這2 種方法，這2 種方法皆可用于構建超圖或者提取特征。實驗針對不同條件進行分類討論，將2 種卷積方法分別用于構建超圖以及提取特征。

用直方圖直觀地表明本文模型效果的提升，如圖4 所示，并對比不同參數條件下2 個數據集的實驗效果。如不做特殊說明，G+M 表示GVCNN 和MVCNN相結合；G+M_G 表示在構造超圖時使用GVCNN 和MVCNN 提取的特征，在訓練網絡時使用GVCNN 提取的特征這一實驗情況，其他的類比即可。

圖4 不同參數條件下2 個數據集上的分類結果比較Fig.4 Comparison of classification results on two data sets with different parameters

由圖4 可知，在NTU 數據集上，與其他模型相比，HGNNP 多數實驗條件下分類效果是最好的，提升的程度比較大，最高準確率達到85.79%，與HGNN 相比，提高了8.59%；在ModelNet40 數據集上，與其他模型相比，HGNNP 模型性能較好，最高準確率達到了93.07%，但由于ModelNet40 與NTU 數據集相比數據樣本偏少，HGNNP 模型的提升效果不明顯，與HGNN 相比，提高了0.47%。綜上所述，與HGNN 相比，HGNNP在多數情況下提升效果顯著，由此驗證了本文模型的有效性和穩(wěn)定性。個別情況效果比較差，原因是實驗條件中用于構建超圖的特征和用于學習的特征之間存在差異，深度網絡使差異明顯化，因此，在準確率上會有一定的誤差。

2.3 參數分析

為分析傳播概率α 對于模型的影響，本文將所有情況下針對α 在[0.01，0.2]區(qū)間內的分類結果進行展示，如圖5 所示，以探求α 取何值時模型效果取得最優(yōu)。

圖5 HGNNP 在ModelNet40 數據集上隨α 的變化Fig.5 Changes of HGNNP with α in ModelNet40 dataset

由圖5 可以看出，在ModelNet40 數據集上HGNNP隨α 的變化趨勢。一開始在0.1 處準確率比較低，也就是說當接近以往的傳播機制，沒有概率傳回根節(jié)點本身時，準確率會比較低；在0.1～0.15 之間，準確率達到最高，說明在這一范圍內調節(jié)α 可以得到最優(yōu)模型。這也驗證了對根節(jié)點信息進行一定的保留比直接傳播學習的信息更全面準確。在NTU 數據集上也可以發(fā)現類似的規(guī)律，本文不再贅述。傳播概率α 對HGNNP模型效果影響顯著，傳播層數N 在模型中也是重要的影響參數。HGNNP 在Model-Net40 數據集上的分類效果隨N 的變化如圖6 所示。

圖6 HGNNP 在ModelNet40 數據集上隨N 的變化Fig.6 Changes of HGNNP with N in ModelNet40 dataset

由圖6 可知，傳統(tǒng)的卷積神經網絡在層數過深時會出現過擬合的現象，而本文模型在層數過深時依然可以保持穩(wěn)定的分類準確率，并且隨著層數的加深，存在一個臨界值使得模型分類效果最優(yōu)。本文模型在傳播層數較少時準確率較低，傳播層數接近1 時模型上近似于傳統(tǒng)的神經網絡；隨著傳播層數的加深，分類準確率逐漸上升，在傳播層數為2～5 之間時逐漸達到最大值；之后會逐漸地下降。同等意義上，對于本文模型來說，使用網頁排名的傳播機制傳播5 層左右，可以使HGNNP 達到最優(yōu)。

更為重要的是，當傳播層數逐漸加深到一定程度時，HGNNP 表現趨于穩(wěn)定，不再出現大幅度的變化，甚至當接近無限的網絡層數后，模型表現依然不會出現很大的變化，不會因為過平滑的問題而分類錯誤，這正對應了前文提到的要解決的挑戰(zhàn)和問題，驗證了本文模型相比傳統(tǒng)神經網絡的優(yōu)越性。

3 結論

本文針對傳統(tǒng)超圖神經網絡卷積過程中層數過深過擬合以及傳播范圍小的問題，提出了一種基于PageRank 傳播機制的深度超圖神經網絡HGNNP。實驗結果表明：與傳統(tǒng)的深度圖神經網絡相比，HGNNP在各種學習任務中都可以取得較好的性能。其中在ModelNet40 數據集上，最高準確率達到了93.07%，相比HGNN 提高了0.47%；在NTU 數據集上，最高準確率達到了85.79%，相比HGNN 提高了8.59%。