基于協作推斷的正例未標注圖學習算法

收稿日期：2021-11-28；修回日期：2022-01-12" 基金項目：國家自然科學基金資助項目（61402375）；陜西省重點研發計劃資助項目（2019ZDLNY07-02-01）；西北農林科技大學中央高校基本科研業務費專項基金資助項目（2452019065）

作者簡介：陳航（1997-），男，湖北黃岡人，碩士研究生，主要研究方向為大數據管理與分析；梁春泉（1981-），男（通信作者），廣西桂平人，副教授，碩導，主要研究方向為大數據管理與數據挖掘（lcquan@nwsuaf.edu.cn）；王紫（1996-），女，貴州安順人，碩士研究生，主要研究方向為大數據管理與分析；趙航（1994-），男，湖北十堰人，碩士研究生，主要研究方向為大數據管理與分析．

摘 要：針對現有正例未標注圖學習方法僅提取節點表征信息、獨立推斷節點類別的問題，提出了一種基于協作推斷分類算法，利用節點之間關聯信息來幫助推斷未標注節點的標簽。首先，采用個性化網頁排位算法計算每個節點與全體已知正例節點的關聯度。其次，采用一個圖神經網絡學習節點表征信息，與正例關聯度聯合構造一個局部分類器，預測未標注節點標簽；采用另一個圖神經網絡獲取局部節點標簽之間依賴關系，與正例關聯度聯合構造一個關系分類器，協作更新未標注節點標簽。然后，借鑒馬爾可夫圖神經網絡方法交替迭代地訓練兩者，形成多跳步節點標簽之間的協作推斷；并且，為有效利用正例與未標注節點訓練分類器，提出了混合非負無偏風險評估函數。最后，選擇兩者中任意一個，預測未標注節點的類別。在真實數據集上的實驗結果表明，無論是識別單類別正例還是識別多類別合成正例，所述算法均表現出比其他正例未標注學習方法更佳效果，且對正例先驗概率誤差表現出更好的魯棒性。

關鍵詞：正例未標注圖學習；協作推斷；圖神經網絡；節點依賴

中圖分類號：TP301.6"" 文獻標志碼：A

文章編號：1001-3695（2022）06-016-1694-06

doi：10.19734/j.issn.1001-3695.2021.11.0604

Positive unlabeled graph learning based on collective inference

Chen Hang，Liang Chunquan，Wang Zi，Zhao Hang

（College of Information Engineering，Northwest Aamp;F University，Yangling Shaanxi 712100，China）

Abstract：Most existing positive-unlabeled （PU） graph learning methods exact only node representations to infer node labels independently.This paper proposed a collective inference based method that exploited the correlations among nodes to assist in classification of unlabeled nodes.Firstly，it used the personalized PageRank algorithm to approximate correlation degrees between each node and observed positive nodes as a whole （positive correlation degree，PCD for short）.Then，it built a local classifier to predict labels of unknown nodes by combining PCD with node representations that were captured via a graph neural network（GNN），and constructed a relational classifier to collectively update labels of unknown nodes by combining PCD with local label dependency of nodes that were exacted via another GNN.Furtherly，it exploited the Markov GNN （GMNN） framework to train these two classifiers，alternately and iteratively，to form a multi-hop collective inference procedure.Besides，

it proposed a mixed non-negative unbiased risk estimator for the two classifiers to estimate empirical loss with only positive and unlabeled nodes.Finally，either of them could predict labels of unknown nodes.Experimental results on real-life datasets show that the proposed method remarkably outperforms the state-of-the-art approaches in identifying both single-class target concept and multiple-classes-merged target concept，and performs quite robust against to error of the prior of positive nodes.

Key words：positive unlabeled graph learning；collective inference；graph neural network；node label dependency

0 引言

圖節點分類問題在過去數十年里一直都是圖數據研究領域的熱點問題，對眾多應用的實施起著關鍵性作用。例如，在社交網絡中，節點分類可實現對用戶類別或者用戶所屬社區的識別［1］；在引文網絡或萬維網中，節點分類可獲得對文檔類型的劃分［2，3］；在蛋白質互作用網絡中，節點分類則可識別參與相同組織機能的蛋白質［4］。為對圖節點有效分類，早期研究界提出了拉普拉斯正則化［5］、統計關系學習［6］和圖嵌入技術［7～9］等眾多方法。近些年來，受深度學習在其他領域成功應用［10］的啟發，研究界將神經網絡模型應用于圖數據，提出了圖神經網絡（graph neural network，GNN）模型［11］對圖節點進行分類。典型GNN模型有圖卷積網絡（graph convolutional network，GCN）［2］和圖注意網絡（graph attention network，GAT）［12］等，前者實現了圖數據上的卷積操作，后者則實現了圖數據上的自注意力機制。此后大多數GNN模型都是在這兩者基礎上添加新特性來實現的，例如自適應圖神經網絡［13］、門注意力網絡［14］、歸納學習圖神經網絡［15］等。在圖節點分類任務中，GNN以端到端方式聚合節點及其鄰居的屬性值作為節點表征信息，推斷節點所屬類別［16］。由于其強大的表征學習能力，GNN表現出優秀的分類效果，成為了解決圖分類問題的新范式。此外，研究界還提出通過整合若干GNN，從圖數據中提取節點表征、節點標簽依賴、全局一致性等多種類型信息，進一步提升分類性能。典型方法有馬爾可夫圖神經網絡（graph Markov neural network，GMNN）方法［17］、圖推理方法［18］、雙卷積網絡［19］等。

圖節點分類的有效策略是協作推斷［20～22］。與傳統機器學習采用的獨立分類策略不同，協作推斷不僅利用節點屬性和已知節點標簽信息，更重要的是利用節點標簽之間，包括未標注節點標簽之間的關聯信息，彼此推理未標注節點的類別。協作推斷主要的實現方法有迭代法和全局目標函數優化法。迭代法通過構造一個局部分類器和一個關系分類器，分別初始化未標注節點標簽并對其迭代更新［22，23］。早期的研究工作著重把傳統分類模型，例如決策樹、樸素貝葉斯、邏輯回歸、SVM等［22］，作為局部分類器和關系分類器的基分類器。受深度學習影響，近年來則有研究者將深度學習模型，如循環神經網絡（RNN）作為基分類器，例如深度協作推斷［24］和循環協作分類［20］等，甚至直接利用神經網絡構建協作推斷框架，例如列神經網絡［25］、關系神經網絡［26］及圖置信傳播神經網絡［27］等。全局目標函數優化法建模節點類別的聯合概率分布作為目標函數，通過優化后驗分布實現推斷［22］。由于該方法計算復雜性高，研究界一般采用變分法，如置信傳播或者平均場優化目標函數并推斷節點類別［22］。迭代法實現簡單，但不能保證收斂；全局目標函數法保證收斂，但計算復雜性高。上文提到的GMNN則是一種兼具兩者優點的協作推斷方法。GMNN以條件隨機場建模節點類別聯合概率分布的后驗分布，作為全局目標函數，并交替訓練兩個圖神經網絡，分別作為局部分類器和關系分類器，迭代優化后驗分布和實現對未知節點類別的有效推理。

盡管上述方法可成功地對圖節點分類，然而這些方法大部分都屬于有監督的學習方法，意味著用戶必須提供包含所有類別的已標注節點集，用來計算訓練模型的經驗損失值。另一方面，在許多實際應用中，用戶往往僅可提供少量的、感興趣的若干類節點，但期望識別出感興趣的其他節點。以網頁推薦為例，萬維網中的網頁可構成一個大圖，用戶在瀏覽萬維網時往往會將感興趣的頁面添加至書簽；系統需要根據用戶提供的標簽頁，推薦其他感興趣的網頁。此類問題可建模為圖數據上的正例—未標注（positive-unlabeled， PU）節點分類問題，其中書簽頁可視為正例節點，大量的其他頁面則為未標注。針對該類問題，現有研究提出將圖神經網絡與非負無偏正例未標注學習相結合，并提出了長短距離聚合神經網絡模型（LSDAN）［3，28］。 該模型以昂貴的時空開銷聚合長距離和短距離范圍內的鄰居節點，期望獲得有效的節點表征，但假設節點類別僅依賴于節點屬性，忽略節點標簽之間的關聯關系，限制了其分類效果。其他圖數據上關于正例未標注學習的研究則僅關注圖層次上的分類問題［29，30］。

本文研究圖數據上的PU節點分類問題，受協作推斷，尤其是GMNN方法［17］啟發，提出一個基于協作推斷的正例未標注圖學習算法（PUCI）。該方法旨在從正例和未標注節點中提取節點表征信息和節點標簽之間的關聯信息，特別是未標注節點與全體已知正例的關聯信息，協同推斷節點類別。基本思路是利用提取的信息分別構造局部分類器和關系分類器，形成一跳步節點標簽之間的基本協作推斷；進而借鑒GMNN方法，交替訓練兩者，形成多跳步節點標簽之間的協作推斷。本文利用相似性個性化網頁排位算法，計算獲得未知節點與全體已知正例節點的關聯度。提出基于非負無偏學習與圖神經網絡相結合的一跳步節點標簽之間協作推斷方法。采用混合非負無偏風險評估函數訓練兩個不同圖神經網絡，分別提取節點表征和局部節點標簽關聯信息，并與正例關聯度結合，分別構造一個局部分類器和一個關系分類器；前者初始化未標注節點的標簽，后者利用直接鄰居節點標簽協作更新節點標簽。提出基于迭代法和全局目標優化相結合的多跳步節點標簽之間協作推斷方法。借鑒GMNN方法，以條件隨機場建模節點類別聯合概率分布作為全局目標函數，并以EM算法［29］交替訓練局部分類器和關系分類器進行優化，在此過程中迭代更新未標注節點標簽。

1 問題定義及相關技術

1.1 問題定義

本文中，一個圖可表示為G=（V，E，XV），其中V表示節點集合，E={（u，v）|u，v∈V}表示邊集合，XV表示所有節點的屬性，xv∈XV則表示節點v的屬性。給定一個圖G和少量正例節點PV，PU圖學習問題旨在學習一個二類分類器，用于推斷其他未標注節點v∈V＼P的類標簽yv∈{0，1}，其中0表示負例，1則表示正例。與文獻［3，28，32］相似，本文假設正例的先驗概率π已知，實際應用中可利用正例和未標注樣本進行估算［33］。本文用到的主要符號如表1所示。

1.2 圖神經網絡（GNN）

圖神經網絡是一個可用于圖節點分類的深度學習模型。為此，GNN堆疊多個隱層以提取節點表征信息，并輸入softmax函數，估算（approximate）節點類別概率分布。進一步而言，GNN接收節點屬性為輸入特征，通過多個隱層迭代地聚合節點及其鄰居節點的表征，更新該節點表征。典型更新方法有GCN［2］、GAT［12］等。

具體地，給定一個圖G和一個神經網絡gφ，φ為可學習參數，圖節點表征的獲取可形式化為

Hφ=gφ（XV）（1）

其中：Hφ∈Euclid Math TwoRApk×b表示隱層最終輸出所有節點的表征矩陣，n=|V|為節點數，b表示隱層節點特征向量的維度。V和E在所有層之間共享。對于節點v∈V，可通過將其表征hφ，v∈Hφ輸入到softmax，獲得其類屬概率分布，如式（2）所示。

pφ（yv|XV）=softmax（Whφ，v）（2）

其中：W∈Euclid Math TwoRApk×b是線性變換矩陣，k表示類別數量。

特別地，在式（1）中，當圖神經網絡以鄰居節點標簽XYNB={yNB（v）|v∈V}作為節點輸入特征時，所學到的表征信息可視為局部節點類標簽依賴關系。

1.3 協作推斷與圖馬爾可夫神經網絡

協作推斷是一類利用節點之間，包括未標注節點之間的關聯信息來幫助推斷未標注節點標簽的分類策略。其重要的實現方法有迭代法和全局目標優化法。迭代法構造一個局部分類器和一個關系分類器，前者利用節點屬性和已知節點標簽，預測和初始化未標注節點標簽，后者則利用鄰居節點標簽，更新未標注節點標簽。全局目標函數優化法通過建模節點類別的聯合概率分布構造目標函數，并通過在已標注節點上優化后驗分布實現未標注節點的推斷。

盡管文獻沒有明確指出，GMNN實際上是一種同時采用迭代和全局目標優化的協作推斷方法。它利用條件隨機場建模節點類別聯合概率分布，并使用期望—最大化（EM）算法交替訓練兩個圖神經網絡，分別作為局部分類器和關系分類器，迭代優化后驗分布，實現對未知節點類別的有效推理。

具體地，GMNN使用式（3）建模節點類別聯合概率分布：

pφ（yV|XV）=1Z（X）∏（u，v）∈Eψu，v（yu，yv，XV）（3）

其中：ψu，v是定義在邊（u，v）上的勢函數。參數φ可通過在已標注節點上最大化對數似然函數的證據下界（ELBO）獲得，如式（4）所示。

log pφ（yL|XV）≥Eqθ（yU|XV）［log pφ（yL，yU|XV）-log qθ（yU|XV）］（4）

其中：qθ（yU|XV）可以是任意在yU的概率分布，且當qθ（yU|XV）=pφ（yU|yL，XV）時等式成立。該下界可通過變分EM算法［21，22］，在E步和M步之間交替訓練優化。

E步訓練一個圖神經網絡gθ，以節點屬性XV作為節點輸入特征，獲取高層表征，從而計算未知節點上的變分分布qθ（yU|XV）=∏v∈Uqθ（yv|XV），進而近似計算聯合概率分布pφ（yU|yL，XV）≈qθ（yU|XV）。其中每個節點v的類別分布qθ（yv|XV）可根據式（1）和（2）計算。

M步訓練另一個圖神經網絡gφ，以鄰居節點標簽XYNB={yNB（v）|v∈V}作為節點輸入特征，獲取局部標簽依賴關系，從而計算條件概率分布pφ（yv|yNB（v），XV），進而最大化式（4）中的Eqθ（yU|XV）［log pφ（yL，yU|XV）］。其中每個節點v的類別分布pφ（yv|yNB（v），XV）可根據式（1）和（2）計算。

具體訓練過程中，qθ和pφ彼此作為優化目標，迭代優化。qθ利用節點表征來預測未標注節點yU的標簽，pφ則利用鄰居節點標簽（可能包括由qθ預測的標簽），更新未標注節點標簽，進一步訓練qθ。由此可見，GMNN實際上是一種既定義了全局目標函數，又通過迭代法優化的協同推理方法。其中式（3）條件隨機場可視為全局目標函數，qθ（連同gθ）為局部分類器，pφ（連同gφ）則為關系分類器。

2 提出的方法

2.1 設計思想

本研究提出一個基于協作推斷進行正例未標注圖學習的算法PUCI（positive unlabeled graph learning based on collective inference），旨在從僅含正例和未標注節點的圖數據中獲取節點表征、局部節點標簽依賴關系、正例節點關聯信息，協作預測未知節點類別。借鑒GMNN方法，PUCI使用條件隨機場建模節點類別在屬性條件上的聯合概率分布，并通過EM算法交替訓練一個局部分類器和一個關系分類器，迭代優化。其中局部分類器利用節點表征和正例關聯信息預測未知節點類別，關系分類器則利用節點標簽依賴關系和正例關聯信息，迭代更新節點標簽。此外，由于監督樣本僅含正例節點，本研究提出混合非負無偏風險評估函數來進行正例未標注圖學習，以訓練這兩個分類器。

2.2 計算正例關聯度

借鑒文獻［34］，正例關聯度可通過基于相似性個性化網頁排位算法獲得。該算法從正例節點出發，執行隨機游走，節點排位可通過迭代地聚合其入鄰居的排位獲得，最終關聯度則可由節點排序近似計算。具體計算如式（5）所示。

PR（v）=（1-λ）rv+λ∑u∈in（v）PR（u）×sim（xv，xu）∑o∈out（u）sim（xu，xo）（5）

其中：PR（v）表示節點v的排位值，λ為衰減因子，本文取值為0.85；in（v）={u|（u，v）∈E}和out（v）={u|（v，u）∈E}分別表示節點v的入鄰居（in-neighbors）和出鄰居（out-neighbors），在無向圖中，兩者均為節點的度；rv表示節點v初始排位值，若v∈P，則rv=1，否則rv=0。sim（u，v）為節點u和v之間在屬性上的余弦相似度，且若sim（u，v）=0，則令sim（u，v）=1/n。

本文采用sigmoid函數對每個節點的排位值進行歸一化，估算正例關聯度s（v），如式（6）所示。

s（v）=sigmoid（PR（v））+α（6）

其中：α∈［0.5，1］為調節參數，本文中取α=0.557。最終所有節點正例關聯度表示為S={s（v）|v∈V}。

2.3 PUCI算法

2.3.1 建模節點條件聯合概率分布

具體地，PUCI采用式（3）建模所有節點類屬聯合概率分布pφ（yV|XV）。根據式（4），給定正例節點集P和屬性XV，模型參數φ可通過在P上優化對數似然函數的證據下界獲得，如式（7）所示。

log pφ（yp|XV）≥ELBO（yp，XV）=Eqθ（yU|XV）

［log pφ（yp，yU|XV）-log qθ（yU|XV）］（7）

根據GMNN［17］，該下界可通過一個變分EM算法求解。在E步，使用一個圖神經網絡提取節點表征信息，并與正例關聯度結合，構建局部分類器qθ，從而近似計算聯合概率分布pφ（yU|yP，XV）；在M步，使用另一個圖神經網絡獲取局部標簽依賴信息，并與正例關聯度結合，構建關系分類器pφ，從而計算pφ（yV|yNB（v），XV），并最大化Eqθ（yU|XV）［log pφ（yP，yU|XV）］。

2.3.2 構建局部分類器

為利用節點表征和正例關聯信息S構建局部分類器qθ，首先利用圖神經網絡gθ從節點屬性XV中學習節點表征信息，即Hθ=gθ（XV），并轉換二維表征H2θ=WHθ，其中W∈Euclid Math TwoRAp2×b，b為Hθ特征維數。其次，對每個節點v的二維表征hv，θ∈H2θ，利用正例關聯度s（v）來增強其正例維，即hv，θ（1），實現節點表征與正例關聯度結合。最后使用softmax函數計算節點v屬于正例和負例的概率，得到qθ。具體如式（8）所示。

hv，θ（1）=s（v）×hv，θ（1），qθ（yV|XV）=softmax（hv，θ）（8）

2.3.3 構建關系分類器

同樣地，為利用節點局部依賴關系和正例關聯信息S構造關系分類器pφ，首先利用另一個圖神經網絡gφ，以鄰居節點標簽XYNB={yNB（v）|v∈V}作為輸入特征，提取節點標簽與鄰居節點標簽之間的依賴關系，即Hφ=gφ（XYNB）。其次，將其轉換為二維表征H2φ=WHφ。然后，對每個節點v的二維表征hv，φ∈H2φ，利用正例關聯度s（v）來增強其正例維，即hv，φ（1），實現局部依賴關系與正例關聯度結合。最后使用softmax函數計算節點v屬于正例和負例的概率，得到pφ。具體如式（9）所示。

hv，φ（1）=s（v）×hv，φ（1），pφ（yV|yNB（v），XV）=softmax（hv，φ）（9）

2.3.4 混合非負無偏正例未標注圖學習

根據GMNN，pφ和qθ的構造目標均為減少在已知類別節點P上的經驗損失，同時在未標注節點U上的預測彼此逼近。因此需要計算包含經驗損失和逼近誤差兩部分的混合損失值R^=R^P+R^U，以訓練pφ和qθ。然而，對于第一部分R^P，若僅使用P計算損失值，所得分類模型將偏向于將節點判斷為正例。受文獻［31］啟發，采用非負無偏風險評估函數（non-negative risk estimator），抽取出部分未標注節點U′U，使得|U′|=|P|，與P一起估算損失值R^PU′。最終采用如式（10）所示的混合非負無偏風險評估函數來訓練pφ和qθ。

R^=R^PU′+R^U（10）

為便于討論，這里令pprφ（yv）和qprθ（yv）分別表示pφ（yv|yNB（v），XV）和qθ（yv|XV）中最大概率值，pLφ（yv）和qLθ（yv）則表示最大概率值對應的類標簽；令損失函數為l：Euclid Math TwoRAp×{0，1}→Euclid Math TwoRAp，l（t，y）則表示當真實類別為y、分類器判斷為t時的損失值。則U′和P上的非負無偏經驗損失值可用式（11）估算。

R^PU′=πR^1P+max（0，R^0U′-πR^0P）（11）

對于qθ，式（11）中各部分為

R^1P=1|P|∑v∈Pl（qprθ（yv），1），R^0P=1|P|∑v∈Pl（qprθ（yv），0），R^0U′=1|U′|∑v∈U′l（qprθ（yv），0）（12）

在U上qθ與pφ之間逼近誤差，則可用式（13）計算。

R^U=1|U＼U′|∑v∈|U＼U′|l（qprθ（yv），pLφ（yv））（13）

對于pφ，式（11）中各部分為

R^1P=1|P|∑v∈Pl（pprφ（yv），1），R^0P=1|P|∑v∈Pl（pprφ（yv），0）R^0U′=1|U′|∑v∈U′l（pprφ（yv），0）（14）

在U上pφ與qθ之間逼近誤差，則可用式（14）計算。

R^U=1|U＼U′|∑v∈|U＼U′|l（pprφ（yv），qLθ（yv））（15）

最終，PUCI采用如算法1所示偽代碼交替訓練pφ和qθ。算法中，步驟（c）僅利用正例和部分未標注節點來預訓練局部分類器qθ，使得首次進入M步時，可初始化未標注節點的類標（步驟e））。M步中，利用局部分類器qθ初始化未標注節點標簽后，可構造屬性集XYNB（步驟f））；以此作為輸入，利用混合非負無偏風險評估函數訓練神經網絡gφ，獲得節點與鄰居節點在標簽上的依賴關系（步驟g）），進而結合正例相關度，構造關系分類器pφ（步驟h））。E步中，利用關系分類器pφ更新未標注節點的類標簽（步驟h））；以節點屬性XV為輸入，利用混合非負無偏風險評估函數訓練神經網絡gθ，獲得節點表征（步驟j）），進而結合正例相關度，更新局部分類器qθ（步驟h））。E步和M步交替訓練，直至收斂。最后返回未標注節點分類結果集{qLθ（yv）|v∈U}。

算法1 PUCI算法

輸入：G=（V，E，XV）：頂點集V，邊集E，頂點屬性集XV；π為正例節點的先驗概率；P為已知正例節點集合。

輸出：未標記節點的類標簽yU。

a）令U=V＼P；

b）從P開始在圖G上執行個性化隨機行走，以式（6）計算S；

c）利用P，U′U和π，以式（11）和（8）預構造qθ；

d）while不收斂do

M步構造關系分類器：

e） 利用qθ預測qLθ（yv），v∈U；

f） 利用qLθ（yv）和P構造XYNB={yNB（v）|v∈V}；

g） 以XYNB作為輸入特征，利用qLθ（yv）、P、π，以式（10）（11）（14）和（15）估算混合損失值，訓練gφ；

h） 利用gφ和S以式（9）構造pφ；

E步構造局部分類器：

i） 利用pφ預測pLφ（yv），v∈U；

j） 以XV作為輸入特征，利用pLφ（yv）、P、π，以式（10）～（13）估算混合損失值，訓練gθ；

k） 利用gθ和S以式（8）構造qθ；

l）end while

m）return {qLθ（yv）|v∈U}

3 實驗及結果分析

本部分在三個真實數據集上進行實驗評估，與最新的圖節點分類的正例與未標注學習算法比較，以F1值為衡量標準［3，28］，驗證本文算法PUCI的分類性能。為便于后文討論，算法使用GCN情況下，命名為PUCI-GCN；使用GAT情況下，命名為PUCI-GCN；PUCI則表示這兩者。

3.1 實驗設置

實驗中所有評估算法均在PyTorch平臺上采用Python（v3.7）編程語言實現。實驗所用計算機的信息為：處理器AMD Ryzen 5 1500X 3.50 GHz，內存16.0 GB，操作系統Windows 10。

a）基準算法。實驗中，本文提出的PUCI算法將與下列基準算法比較：GCN ［2］、GAT［12］和LSDAN［3，28］。與LSDAN類似，為能夠直接從PU節點中訓練GCN和GAT模型，實驗中使用非負無偏風險估計函數。

b）數據集。實驗使用圖半監督分類研究中廣泛采用的三個圖數據集［2，12，17］，包括Cora、Citeseer、Pubmed等。數據集中每個節點表示在相應期刊上發表的一篇文章，邊表示一篇文章引用了另一篇文章，節點類別則代表文章的主題。每個數據集中的每個節點都包含了一個二元詞袋（bag-of-words，BoW）特征。表2說明了數據集的具體信息。

c）二類數據集。以上數據集均包含多個類別，因此，實驗依據可能的應用場景，以兩種方式將這些數據集轉換成二類數據集。一種是輪流選擇每個類別作為正例，其余作為負例；另一種是合并若干類別的節點為正例節點，其余作為負例。對于后者，在Cora數據集上合并1、3、5類標簽為正例，在Citeseer數據集上則合并2、4、6類標簽作為正例。轉換成二類數據集后，可直接獲得正例的先驗概率π，在實驗中提供給算法。

d）參數設置。所有圖神經網絡模型的學習率設置為0.005。GCN和GAT均采用兩個隱層，其中第一層包含25個神經元，第二層包含2個。LSDAN算法聚合4跳步以內鄰居屬性作為節點表征。對每個實驗設置，選擇不同隨機種子重復運行20次，最后報告F1平均值。

3.2 單類別作為正例的實驗結果

本組實驗運行于已指定單類別作為正例的Cora、Citeseer、Pubmed數據集，用來評估PUCI識別單類別所代表的目標概念的能力。為給所有算法提供PU節點集，實驗中將隨機抽取比例為p=10%，20%，30%，40%的正例節點作為已知的P集，其余節點則作為U集。表3～5給出了在三個數據集上算法獲得F1分值的詳細結果。值得注意的一點是，由于LSDAN在Pubmed數據集運行100 h后仍然未能執行完畢，此處不報告相應實驗結果。從表中可看出，本文所提PUCI算法在所有不同正例數下均表現出比相應GCN和GAT算法更好的分類效果，且大多數情況下更是遠優于LSDAN。例如，在Cora數據集上，當給定p=20%的正例節點時，PUCI-GAT獲得的F1值為0.779，相應的GAT為0.761，LSDAN則僅為0.718；在Citeseer數據集上，p=20%時，PUCI-GAT為0.656，GAT為0.635，LSDAN則為0.637。這是由于PUCI算法通過整合迭代法和全局目標優化法，能夠有效利用節點表征、局部節點標簽依賴以及正例關聯等三方信息協同推斷節點類別，其他算法則僅僅使用了節點表征進行預測。需注意的是，盡管LSDAN聚合了長短距離鄰居特征作為目標節點特征，但并沒有獲得最佳分類效果，這表明節點類別并非僅取決于節點自身或鄰居的特征。PUCI則可以通過綜合利用三方信息，有效推理節點類別。

從表3～5中還可看出，大部分情況下，盡管GAT表現出比GCN更好的分類效果，與之對應的PUCI-GAT和 PUCI-GCN卻表現為勢均力敵。例如，在Cora數據集上，當p=20%時，GAT的F1值0.761明顯優于GCN的0.743，但PUCI-GAT的0.779卻接近于 PUCI-GCN的0.772；當p=40%時，GAT的0.769依然優于GCN的0.756，但PUCI-GAT的0.776則接近于PUCI-GCN的0.780。GAT優于GCN是因為前者的自注意力機制比后者的卷積機制能聚合更相關的鄰居節點屬性，學習目標節點表征。盡管如此，采用注意力機制的PUCI-GAT并沒有因此獲得比PUCI-GCN更明顯的優勢。其背后原因可能是在節點標簽依賴信息和正例關聯信息的幫助下，節點表征不再唯一主導推斷結果。以上這些結果都表明了PUCI算法整合節點依賴信息、正例關聯度、節點特征等多方信息來推斷節點類別的有效性，同時意味著PUCI不需要努力尋找時空開銷昂貴的GNN作為基分類器，即可獲得較好的識別效果。

3.3 合并多類別作為正例的實驗結果

本組實驗運行于已合并多類別作為正例的Cora、Citeseer數據集，并采用與上一組相同的方式，給所有算法提供PU節點集。多類別合成正例代表一種臨時的目標概念，這種合成在實際應用中是一種常見的操作，例如在文獻網絡應用中，用戶可能會感興趣并收集多種不同真實類別的文獻作為正例使用。本組實驗評估PUCI識別這種合成概念的能力。表6和7給出了給定不同正例數時的相應實驗結果。從表中可看到與上組實驗相似的實驗結果，大多數情況下PUCI都表現出優于GAT、GCN、LSDAN等方法的分類效果，PUCI-GAT和 PUCI-GCN則表現出相近的分類能力。例如，在Cora數據集上，當p=20%時，PUCI-GAT獲得的F1值0.853接近PUCI-GCN的0.847，但明顯優于相應GAT的0.825，且遠優于LSDAN的0.806。其背后原因與上組實驗類似，即節點類別并非僅依賴于節點的表征，尤其是在本組實驗中，合成的正例集或負例集各自包含著多種不同真實類別的節點，使得目標概念（即正例或負例）與節點表征之間的依賴關系進一步減弱。GAT、GCN或LSDAN僅利用表征預測未知節點，而PUCI同時利用了節點表征、局部節點標簽依賴以及正例關聯等三方信息協同識別未知節點。這些結果驗證了PUCI具有優秀的合成目標概念識別能力。

3.4 選擇鄰居數最多的節點作為正例的實驗結果

本節實驗采用與3.2節實驗相似的設置。不同在于后者采用隨機抽樣選擇已知P集，本節則從正例中選擇鄰居數目最多的節點，即選出排在前p=10%，20%，30%，40%的正例作為P集。在實際應用中這種選擇也是一種常見的操作，例如在文獻網絡應用中，用戶往往感興趣并收藏被引次數最多的論文作為正例使用。表8～10給出了在三個數據集上的相應實驗結果。從表中同樣可看出與前兩組相似的結果，即大部分情況下，PUCI的分類效果優于GCN、GAT、LSDAN等方法，PUCI-GCN和 PUCI-GAT則表現出勢均力敵的分類能力。

例如，在Cora數據集上，當p=20%時，PUCI-GAT獲得的F1值0.770接近PUCI-GCN的0.769，但明顯優于GAT的0.752，且遠遠優于LSDAN的0.639。其背后原因，除了前兩組實驗所述的節點類別并非僅依賴于節點表征，還有可能是因為鄰居數目較多的節點與較少的節點并非同分布，即已知正例和未知正例并非完全同分布。PUCI除了使用節點表征，還使用了節點標簽依賴信息，特別是正例關聯信息來推斷未知節點類別，幫助減少已知正例和未知正例之間非同分布的影響，因此獲得了比GCN、GAT或LSDAN更好的分類效果。這些實驗結果表明，通過整合三方信息，PUCI可利用感興趣的、度較高的節點，識別出同樣感興趣的度較低的節點，進一步驗證了PUCI的有效性。

3.5 正例關聯信息對類別推斷的影響

本節實驗采用與3.2節相似的設置，評估未標注節點與正例關聯信息對判別節點類別的影響。為便于探討，命名不使用正例關聯信息的PUCI為nPUCI，即令式（10）和（11）所用的s（v）=1。表11～13描述了相應實驗結果。從表中可看出，大多數情況下，PUCI_GCN和 PUCI_GAT都優于不使用正例關聯信息的nPUCI_GCN和nPUCI_GAT。例如在Cora數據集上，當p=20%時，使用了關聯信息的PUCI_GCN和PUCI_GAT獲得的F1值分布為0.779和0.772，而不使用關聯信息的nPUCI_GCN和nPUCI_GAT則只有0.754和0.752。這是由于正例關聯度可反映和度量未知樣本與全體已知正例的相似度，所以有助于推斷未知節點類別。本組實驗的結果再次驗證了PUCI通過整合節點依賴信息，特別是與全體正例的關聯信息，對幫助推斷未知節點類別的有效性。

3.6 正例先驗誤差分析

注意到在實際應用中正例的先驗概率π一般是不可知的，需要通過算法估算，本組實驗評估先驗概率估算誤差對算法的影響。實驗設置與3.2節相似，不同在于本組實驗的先驗概率加入了誤差δ=-20%，-10%，0，10%，20%，給所有算法提供帶誤差的先驗概率=π（1+δ）。圖1給出了當選擇p=10%的正例數，不同先驗誤差下各算法的分類效果。同樣地，由于LSDAN運行過慢的原因，這里未能報告其運行結果。從圖中可以看到，當正例先驗概率存在不同先驗誤差下，PUCI算法表現出穩定的分類性能；在較大正誤差情況下，甚至獲得比沒有誤差時更好的分類效果。其背后原因可能是由于適當增加先驗概率比例會幫助訓練模型，即式（11）可獲得更準確的混合經驗損失值；但其更深層次的機理需進一步探索。此外，在不同先驗誤差下，PUCI算法均表現出比其他算法更好的分類性能。實驗中還選擇了p=20%，30%，40%的正例運行算法，同樣獲得相似的結果。這些結果表明了所提算法PUCI對先驗概率誤差具有較強的魯棒性，意味著在實際應用中，不需要努力尋求精確的先驗概率估算方法，即可獲得較好的識別效果。

4 結束語

本文提出了一種基于協作推斷的正例未標注學習算法PUCI，在正例和未標注節點中提取并有效整合節點表征、局部節點依賴信息、正例節點關聯信息等，推斷未標注節點的類別。采用了個性化網頁排序算法估算未標注節點與全體已知正例節點的關聯度。通過訓練一個圖神經網絡獲得節點表征并與正例關聯度結合，構造了局部分類器。通過訓練另一個圖神經網絡獲取局部節點標簽依賴信息并與正例關聯度結合，構造了協作分類器。采用GMNN框架和混合非負無偏正例未標注學習相結合，交替訓練和迭代優化了這兩個分類器。在真實數據集上的實驗結果表明，不管是識別單類目標概念還是多類合成目標概念，所述PUCI算法均表現出比樸素方法或最新正例未標注學習算法更佳的分類效果，同時能夠利用高節點度正例識別低識別度正例，且對正例先驗誤差表現出更好的健壯性。

參考文獻：

［1］Rahimi A，Cohn T，Baldwin T.Semi-supervised user geolocation via graph convolutional networks［C］//Proc of the 56th Annual Meeting of the Association for Computational Linguistics.Stroudsburg，PA：Association for Computation Linguistics，2018：2009-2019.

［2］Kipf T N，Welling M.Semi-supervised classification with graph convolutional networks［EB/OL］.［2021-12-28］.https：//arxiv.org/pdf/1609.02907.pdf.

［3］Wu Man，Pan Shirui，Du Lan，et al.Learning graph neural networks with positive and unlabeled nodes［EB/OL］.［2021-12-28］.https：//arxiv.org/pdf/2103.04683.pdf.

［4］Fout A M.Protein interface prediction using graph convolutional networks［D］.Colorado：Colorado State University，2018.

［5］Belkin M，Niyogi P，Sindhwani V.Manifold regularization：a geometric framework for learning from labeled and unlabeled examples［J］.Journal of Machine Learning Research，2006，7（11）：2399-2434.

［6］Taskar B，Abbeel P，Wong M F，et al.Relational Markov networks［J］.Introduction to Statistical Relational Learning，2007，40（13）：175-200.

［7］Grover A，Leskovec J.node2vec：scalable feature learning for networks［C］//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2016：855-864.

［8］Tang Jian，Qu Meng，Wang Mingzhe，et al.LINE：large-scale information network embedding［C］//Proc of the 24th International Confe-rence on World Wide Web.New York：ACM Press，2015：1067-1077.

［9］Perozzi B，Al-Rfou R，Skiena S.DeepWalk：online learning of social representations［C］//Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2014：701-710.

［10］Redmon J，Divvala S，Girshick R，et al.You only look once：unified，real-time object detection［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ：IEEE Press，2016：779-788.

［11］徐冰冰，岑科廷，黃俊杰，等.圖卷積神經網絡綜述［J］.計算機學報，2020，43（5）：755-780.（Xu Bingbing，Cen Keting，Huang Junjie，et al.A survey on graph convolutional neural network［J］.Chinese Journal of Computers，2020，43（5）：755-780.）

［12］Velicˇkovic′ P，Cucurull G，Casanova A，et al.Graph attention networks［EB/OL］.［2021-12-28］.https：//arxiv.org/pdf/1710.10903.pdf.

［13］Li Ruoyu，Wang Sheng，Zhu Feiyun，et al.Adaptive graph convolutional neural networks［C］//Proc of the 32nd AAAI Conference on Artificial Intelligence.2018：3546-3553.

［14］Zhang Jiani，Shi Xingjian，Xie Junyuan，et al.GAAN：gated attention networks for learning on large and spatiotemporal graphs［C］//Proc of the 34th Conference on Uncertainty in Artificial Intelligence.2018：339-349.

［15］Hamilton W L，Ying R，Leskovec J.Inductive representation learning on large graphs［C］//Proc of the 31st International Conference on Neural Information Processing Systems.Red Hook：Curran Associates Inc.，2017：1025-1035.

［16］薛磊，農麗萍，張文輝，等.一種改進的圖卷積網絡半監督節點分類［J］.計算機應用與軟件，2021，38（10）：153-158，163.（Xue Lei，Nong Liping，Zhang Wenhui，et al.An improved graph convolution network semi-supervised node classification［J］.Computer Applications and Software，2021，38（10）：153-158，163）

［17］Qu Meng，Bengio Y，Tang Jian.GMNN：graph Markov neural networks［C］//Proc of the 36th International Conference on Machine Lear-ning.New York：ACM Press，2019：5241-5250.

［18］Xu Chunyan，Cui Zhen，Hong Xiaobin，et al.Graph inference learning for semi-supervised classification［EB/OL］.［2021-12-28］.https：//arxiv.org/pdf/2001.06137.pdf.

［19］Zhuang Chenyi，Ma Qiang.Dual graph convolutional networks for graph-based semi-supervised classification［C］//Proc of World Wide Web Conference.New York：ACM Press，2018：499-508.

［20］Fan Shuangfei，Huang B.Recurrent collective classification［J］.Knowledge and Information Systems，2019，60（2）：741-755.

［21］Jensen D，Neville J，Gallagher B.Why collective inference improves relational classification［C］//Proc of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2004：593-598.

［22］Sen P，Namata G，Bilgic M，et al.Collective classification in network data［J］.AI Magazine，2008，29（3）：93-106.

［23］Macskassy S A，Provost F.Classification in networked data：a toolkit and a univariate case study［J］.Journal of Machine Learning Research，2007，8（5）：935-983.

［24］Moore J，Neville J.Deep collective inference［C］//Proc of the 31st AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2017：2364-2372.

［25］Pham T，Tran T，Phung D，et al.Column networks for collective classification［C］//Proc of the 31st AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2017：2485-2491.

［26］Kazemi S M，Poole D.RelNN：a deep neural model for relational lear-ning［EB/OL］.［2021-12-28］.https：//arxiv.org/pdf/1712.02831.pdf.

［27］Jia Junteng，Baykal C，Potluru V K，et al.Graph belief propagation networks［EB/OL］.［2021-12-28］.https：//arxiv.org/pdf/2106.03033.pdf.

［28］Wu Man，Pan Shirui，Du Lan，et al.Long-short distance aggregation networks for positive unlabeled graph learning［C］//Proc of the 28th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2019：2157-2160.

［29］Zhao Yuchen，Kong Xiannan，Philip S Y.Positive and unlabeled learning for graph classification［C］//Proc of the 11th IEEE International Conference on Data Mining.Piscataway，NJ：IEEE Press，2011：962-971.

［30］Wu Jia，Pan Shirui，Zhu Xingquan，et al.Positive and unlabeled multi-graph learning［J］.IEEE Trans on Cybernetics，2016，47（4）：818-829.

［31］Neal R M，Hinton G E.A view of the EM algorithm that justifies incremental，sparse，and other variants［M］//Learning in Graphical Models.Cambridge，MA：MIT Press，1998：355-368.

［32］Kiryo R，Niu G，Plessis M C，et al.Positive-unlabeled learning with non-negative risk estimator［C］//Proc of Annual Conference on Neural Information Processing Systems.2017：1675-1685.

［33］Jain S，White M，Radivojac P.Estimating the class prior and posterior from noisy positives and unlabeled data［C］//Advances in Neural Information Processing Systems.2016：2693-2701.

［34］Kloumann I M，Kleinberg J M.Community membership identification from small seed sets［C］//Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2014：1366-1375.