一個選擇最大似然互信息特征的網絡關系預測通用模型

伍杰華 熊云艷

1(廣東工貿職業技術學院計算機與信息工程學院 廣東 廣州 510510)2(華南理工大學計算機科學與工程學院 廣東 廣州 510641)

0 引 言

信息網絡是一種基于實體和實體之間紛繁復雜互聯關系組成的網絡結構[1]。各實體通過信息網絡實現信息的傳遞、傳播和交互。比較常見的信息網絡有科研學術合作網絡[2]、社交媒體網絡[3]、生物蛋白質功能網絡[4]等。由于實體之間關系是信息傳播之間的橋梁，因此對關系的分析與研究顯得非常重要[5]，其中一個主要的研究方向是關系預測與推斷(又稱鏈接預測或者關系分類與推斷)[6]。該技術的核心思想是根據當前信息網絡的結構信息預測尚未存在關系的實體之間產生關系的可能性。它首先能夠從理論層面幫助深入理解信息網絡的演化機制和信息傳播機制[7]，例如社交網絡中的消息(信息)傳播機制的本質是把人與人之間的互聯關系引入到傳播過程當中，因此該互聯的社交關系直接影響信息傳播效果及范圍。例如，謠言、傳聞、流言的傳播是目前社交媒體或者社會網絡領域中危害社會穩定和安全的垃圾信息，通過關系預測結合影響力節點分析等其他社交網絡分析技術，我們能夠進一步深入揭示謠言在用戶之間的傳播方式和整個網絡的實體關系及其演化機制，從而有助于更好地找到謠言發起的源頭、散步的規律，協助治理網絡安全。此外，該技術在應用領域也有廣泛的應用前景。例如知識圖譜中實體之間的關系預測[8]。知識圖譜是一種基于語義信息并描述實體與實體之間關系的異質結構。它能把不同知識領域的多維度的關系網絡。關系預測技術有助于實現知識圖譜實體之間關系的學習、融合以及推理，并為其實體關系進行標注，在新聞事件的關聯分析、識別反欺詐潛在風險、失聯客戶管理和謠言識別等眾多領域有重要的應用價值。

圖1 算法模型

1 相關工作

預測，在一定程度上是個概率計算問題。即通過計算兩潛在實體之間產生關系的概率來進行推斷。由于該概率可通過挖掘網絡結構信息直接計算或構建概率模型學習獲得，因此關系預測與推斷算法主要分為基于概率相似度和基于學習思想兩大類[9]。第一類算法把概率視為兩潛在實體之間的相似度，并通過信息網絡節點、路徑、社區、鄰接矩陣等拓撲結構或網絡表示結構計算該相似度,其原理簡單，一直是研究的主流。但是本文主要介紹的是基于學習思想的算法，因此對于第一類算法的相關工作就不作詳細敘述，可參考相關綜述[9-10]。近幾年來，隨著機器學習理論的飛速發展，一些新技術、新方法不斷提出，這些研究為第二類基于統計機器學習技術的關系預測奠定了基礎。該類算法的主要思想是根據社交網絡結構提取特征并建立一個適合的模型，采用統計方法估計模型的參數，然后通過參數進行類別判斷和最優化推斷等。其研究思路主要分為以下幾個方面：基于特征學習的分類算法、基于概率圖(層次圖)模型的算法、基于矩陣分解和補全算法和基于網絡表示學習與嵌入的算法等。(1) 基于特征學習的分類算法。該類算法假設潛在鏈接的形成與否受到與其相關聯的特征空間的影響，并把鏈接形成與否視為一個二分類問題。文獻[11]首先把鏈接預測變成給定特征下的兩分類問題，并比較了多個監督學習算法的性能。文獻[12]提出了一種高性能的基于流信息采用基于Bagging和Random Forest的分類模型，該模型有效地解決了分類中的不平衡問題。文獻[13]提出了一個面向微博社交網絡的預測算法。該算法從多個層面收集了網絡中基于節點、拓撲結構、投票和社交信息等信息構建特征，采用SVM等多種方法有效地進行鏈接分類。(2) 基于概率圖(層次圖)模型的算法。該類算法的主要思想在于兩個節點之間鏈接形成的概率取決于它們從屬的層次、社區或者塊信息。文獻[14]認為鏈接可以看作社交網絡內在的層次結構的反映，并提出了一種挖掘網絡層次結構的最大似然估計的算法。文獻[15]通過引入高斯過程，提出了一種基于隨機關系模型(Stochastic Relational Models，SRM)的鏈接預測算法。該算法的關鍵思想在于通過多重高斯過程的張量相互作用對隨機實體關系結構建模。文獻[16]結合信息網絡另外的一個熱門研究領域-社區劃分，把關系預測的問題從判斷鏈接是否存在變成在一個社區劃分網絡下，已存在網絡結構中不同類型的關系生成最大化推斷問題，提出了一種平衡度模塊度最大化的模型(Modularity Maximization Link Prediction Model, MMLP)。

但是上述算法依然存在通用的問題，因為它們僅僅考慮了如何建立模型提高對特征的學習，而忽略了特征之間存在的關聯會影響學習與分類的性能。在分類問題中，特征是決定分類性能最重要的因素。但是由于獲取的原始特征不一定能夠準確反映待分類對象的本質特征，樣本也可能比較稀疏，計算量大，不利于高效的分類；同時高維的原始特征存在冗余信息，不做分析直接用于分類會存在“維度災難”，影響分類性能。

針對原始信息網絡特征存在的不足，同時彌補上述算法在特征提取過程當中難以兼顧類型、數量及缺乏特征選擇過程，本文提出一個結合最大似然互信息特征選擇的信息網絡關系預測算法。具體來說，算法首先基于相似度預測指標提取了局部和全局(半局部)兩類特征，然后極大似然推斷最大化特征之間互信息，對特征的重要性進行排序，根據排序選擇最具影響力的特征進行分類。算法的主要貢獻如下：

(1) 結合最大似然理論計算互信息，有效地篩選最具判別性特征，提高了學習和預測效率。

(2) 把提出的特征選擇算法嵌入到基于特征學習的分類算法和新提出的基于概率圖(層次圖)模型中，在多個真實信息網絡數據集的結果表明，分類性能得到提高，特性選擇步驟是必要的。

2 特征提取

2.1 問題定義

基于分類理論的關系預測算法。該類方法把關系預測問題看成是一個標簽預測問題(Label Prediction)，其中存在的和不存在的關系分別被標記為正例和負例?；蛘甙褑栴}看成存在概率P(e∈G)的估計問題，然后建立一個預測模型M和獲取影響鏈接生成的特征空間和參數空間θ，并通過分類、優化等理論與方法計算該概率。概率越高，關系生成的概率越大。具體的函數映射如下：

fM(GT,,θ)→{0,1}

(1)

式中：0表示潛在節點之間不存在鏈接，1則表示存在鏈接。M指預測模型，GT是訓練集網絡。

2.2 局部與全局特征提取

2.2.1局部特征

在信息網絡關系分類領域，鄰接節點指和指定和潛在節點i存在直接鏈接關系的節點集合，記為N(i)。節點i的d路徑內鄰居(或者指d條鏈接內可達到)是指i在d步路徑之內能達到的節點j的集合，記為N(i,d)。如果V是一個節點集合，那么N(V,d)是指V中節點在d步路徑之內能達到的節點集合。由于該節點集合的信息對于潛在節點對是否存在關系的影響是最直觀的，因此局部結構或者局部性(locality)一般表示在1～3步路徑內的節點集合。由于定義信息網絡結構特征的指標有非常多，文中選擇了5個典型具有代表性的指標構建局部特征集合L：

CommonNeighbors(CN)[6]:CN相似度指標(在文中指標也可稱為方法、算法)是鏈接預測中最直觀、最簡單的相似度計算方法。假設兩個潛在節點對擁有的共鄰節點數目越多，它們之間產生鏈接的概率就越高。公式如下：

CN(i,j)=|N(i)∩N(j)|

(2)

式中：N(i)指所有與節點i相鄰的節點的集合。

Adamic-Adar(AA)[17]:該指標通過對每個共鄰節點的不同度的對數值差分化處理不同共鄰節點的角色和貢獻，度大的共鄰節點貢獻小于度小的共鄰節點。其公式如下：

(3)

PreferentialAttachment(PA)[18]:該指標主要反映網絡中的偏好性生成機制，即節點的度越大，其吸引其余節點產生關系的可能性越高。公式如下：

PA(i,j)=|N(i)|×|N(j)|

(4)

JaccardCoefficient(JC)[6]:JC指標不僅考慮了預測節點對的共鄰節點數目，它還考慮了共鄰節點在兩個節點的鄰居節點集合中所占的比率。公式如下：

(5)

ClusterCoefficient[18]:聚類系數表示節點鄰接節點之間鏈接的密集程度，該指標取共鄰節點聚類系數的和。公式如下：

(6)

式中：cω表示共鄰節點ω的聚類系數。

2.2.2全局(半全局)特征

基于局部特征算法主要考慮局部拓撲結構屬性，相應的指標所需的信息量少、算法簡單、時間復雜度低，運行速度快，適用于小規模的網絡關系預測任務。但是局部拓撲結構屬性不能夠深層次反映兩節點之間的隱含屬性，也不能反映整個網絡結構對潛在預測節點的影響。基于上述兩個原因，一部分相似度特征指標的構建工作基于路徑或者基于隨機游走展開(由于該過程取決于網絡的結構，因此可能是全局的，也可能是半全局的，但后續均統稱為全局特征)。因此，文中選擇了5個典型的指標構建全局特征集合G：

LocalPath(LP)[19]:為了避免僅僅考慮共鄰節點結構而導致的精確度以及區分度過低等問題，局部路徑指標額外考慮了三階路徑的影響。公式如下：

LP(u,v)=(D2)u,v+α(D3)u,v

(7)

式中：α是權重參數，D是圖矩陣，Du,v表示節點對u、v之間的一步路徑，則是兩步路徑，(D2)u,v以此類推。當α=0時，LP(u,v)=(D2)u,v相似度指標變成只考慮共同鄰居節點的影響，此時LP就是CN。

Katz[20]:根據局部路徑指標可知，如果想要將網絡結構的影響因素更全面地考慮進來，同時更進一步地提高計算精度，可以將四階路徑、五階路徑、乃至n階路徑考慮進來。當n→∞時，相似度計算將全局網絡路徑均考慮在內，此時的相似度指標就相當于Katz指標。公式如下：

Katz(u,v)=(I-αD)-1-I

(8)

式中：I是單位矩陣，該算法將所有對節點間產生影響的路徑信息都考慮進來了。

RandomWalkwithRestart(RWR)[21]:該指標基于一個物理意義上的假設：隨機游走的粒子會以一定的概率返回起始位置，其中元素πuv表示從節點u走到v的概率。公式如下：

RWR(u,v)=πuv+πvu

(9)

同時，基于隨機游走還選取了SRW和LRW兩個指標作為全局特征，由于版面關系，在此不再詳細敘述。

3 算法框架

在基于信息網絡結構的關系預測或者分類算法的相關工作中，所提取的相似度特征一般均基于節點、共鄰節點或者相關路徑等信息構建，因此特征之間會存在相似的信息，直接用作分類和推斷優化會保留特征之間的噪音和冗余信息。因此，本文的核心思想在于考慮能否運用機器學習特征工程領域的特征選擇技術篩選出具備最優判別性的特征幫助分類——即特征選擇。特征選擇技術指在未處理的特征空間中通過指定的標準篩選出一組具備最佳分類性能的特征子集的過程[22]，該過程有助于刪除特征間冗余信息和不相關的特征。

3.1 最大似然互信息特征選擇

在面向特征選擇的信息論中，兩個隨機變量的互信息(Mutual Information，MI)[23]定義變量間相互依賴性的量度。在分類問題中，特征和類別之間的相互信息體現了特征和類別的相關程度，即可以評價特征對于分類效果貢獻。因此，估計特征和類別之間的MI在特征選擇領域多年來一直備受關注，在度量特征之間的關系和輔助特征選擇上有重要的意義。因此，使用互信息理論對特征進行選擇和提取基于如下假設：特征在某個類別出現的頻率高，但是其他出現的頻率低，可以認為該特征和類別的互信息比較大。所以如何計算MI是其中的關鍵問題。MI可以定義為：

(10)

然而對上述公式中的密度進行估計是一個比較困難的問題。因為估計密度的劃分涉及到MI的逼近，容易使估計誤差放大。一部分工作例如用k近鄰(KNN)方法估計熵算法嘗試適當地確定k的值以使偏方差權衡得到最優，但是該步驟在MI估計的上下文中的實現并不簡單。當目標密度接近正態分布時，計算邊緣分布的方法效果較好；否則，它是有偏差的和不可靠的。針對計算互信息存在的問題，本文提出了一種稱為最大似然互信息(Maximum Likelihood Mutual Information，MLMI)新的MI估計方法[24]。該方法的優點在于不涉及密度估計，直接對密度比建模：

(11)

(12)

然后用以下線性模型對密度比函數w(x,y)建模:

(13)

式中：α:=(α1,α2,…,αb)T是需要從樣本中學習的參數。φ(x,y):=(φ1(x,y),φ2(x,y),…,φb(x,y)T則是偏差函數。

(14)

(15)

(16)

(17)

現在我們的優化準則總結如下：

在估計密度函數之后以互信息作為提取特征的評價選擇互信息最大的N個特征進行分類。

3.2 基于MLMI的關系預測

整個算法框架如下所示：

Input：網絡G=(V,E)

Output：Accuracy AUC Precision Recall F1

1: 對G劃分為訓練網絡GT和預測網絡GP

2:forGT和GP中的每一條存在或不存在關系do

4:endfor

7: 采用優化準則公式推斷參數

9: 采用NB，SVM和RF進行分類

4 實 驗

4.1 實驗設置

根據關系分類算法遵循圖1的過程：按照比例r(默認設置為0.9)把網絡劃分為訓練網絡和預測網絡，對兩個網絡分別提取特征空間T和P，然后根據圖1的分類優化過程的每個步驟進行實驗。每個算法劃分10次，取10次結果的平均值。其中默認選擇的特征是最具判別性(排序在前)的前8個特征作為特征子集。在該過程中把存在鏈接視為正類(Positive)，不存在鏈接視為負類(Negative)，True表示預測準確，False表示預測錯誤，TP則表示實際存在鏈接被成功分類的數目。實驗結果采用信息檢索領域分類模型標準評價指標準確率(Accuracy)、AUC(Area Under Curve)、精確率(Precision)、召回率(Recall)和F1-Measure對算法進行評價。其中：

(18)

(19)

(20)

(21)

4.2 數據集

(1) Dolphins[26]。這是寬吻海豚的定向社交網絡。節點表示寬吻海豚社區的寬吻海豚，關系表示海豚間的頻繁關聯。

(2) Football[26]。2000年秋季常規賽期間IA大學之間的美式足球比賽網絡。

(3) Enron[27]。郵件網絡，網絡中的節點是表示員工，關系表示節點之間的電子郵件。

(4) Yeast[28]。生物酵母數據集。

(5) Email[28]。Virgili大學成員之間的電子郵件交換網絡。

(6) Openflights[29]，航班網絡。 每個節點表示一個機場，關系代表一個航空公司到另一個航空公司的航班。

數據集的拓撲結構屬性顯示在表1中。

表1 多元網絡結構屬性

4.3 對比方法

實驗中對網絡中的潛在鏈接進行分類和推斷，判斷鏈接是否生成，驗證提出模型的有效性。同時，實驗采用多種有監督學習算法作為分類算法[30]，這些分類算法包括樸素貝葉斯分類(Na?ve Bayes，NB)，支持向量機(Support Vector Machine，SVM)和隨機森林(Radom Forest，RF)。本文提出方法簡稱為MLFS(Maximum Likelihood Mutual Information Feature Selection)。

4.4 實驗結果與分析

為了充分驗證提出特征分類算法對鏈接分類問題的有效性，本文使用不同分類算法在6個數據集中做了大量的實驗。表2和表3給出了結果的平均值，其中No-FS表示沒有經過特征選擇步驟，直接采用原始特征進行分類的算法；MLFS表示經過特征選擇過程的分類算法。根據表2的結果，有以下幾點發現：(1) 實驗使用了6個數據集、5個評價指標和3個分類器，因此共有90個對比案例。經過統計，與No-FS相比，MLFS在67.77%的案例中效果更好，在20%的案例中效果相等，在12.23%的案例中效果相對較差。該結果表明經過最大似然互信息特征選擇步驟得到的分類性能要優于沒有經過特征選擇步驟基準方法，也反映本文提出的算法泛化性能很高，在多個數據集中均具備不錯的性能。同時，對于每個數據集，最優的算法均出現在MLFS中，這是因為特征選擇刪除了一些不相關或冗余的特征，解決了維數過多帶來的災難，在一定程度上避免過擬合，也側面反映特征選擇過程是有效且必要的。需要指出的是，由于這5種評估指標各有側重點，因此一個數據集上一個方法很難在所有評估指標上均優于對應基準算法。(2) 各數據集各指標在不同分類器下的分類結果有差別。在SVM分類器下，76.66%的案例中MLFS比No-FS要優，該百分比在NB和RF分類器分別下降為56.66%和53.33%，因此從整體上看，SVM和RF比NB要更適合信息網絡關系分類這一任務，原因在于SVM的優點是處理高維特征數據，同時能更好地解決特征的非線性問題。(3) 無論是對于小規模的網絡(例如Football數據集潛在關系有35×35)，還是對于較大規模網絡(Openflights數據集潛在關系有3 425×3 425)，在對經過特征選擇的特征分類的過程中均能夠比原始特征取得更好的分類精度，這表明提出的算法能夠適應不同規模的網絡，在一定條件下具備拓展到超大規模網絡應用的基礎。

表2 各分類算法在Dolphins Football Enron下的分類效果

續表2

表3 各分類算法在Yeast Email Openflights下的分類效果

續表3

此外，為了更加細致地分析每個算法的效果，文中還進行了以下拓展實驗：

(1) 為了驗證提出算法的穩定性和解決稀疏網絡學習的能力，表4給出了在不同規模劃分網絡下各分類算法的分類性能力，其中訓練集比例r分別設置為0.5、0.6、0.7、0.8、0.9。我們在其他數據集也發現了類似的效果，由于版面的關系，僅僅給出Email數據集的分類結果。由表4可知，隨著r值不斷變大，對應No-FS和MLFS的分類效果基本上均呈上升趨勢，在r=0.8或r=0.9時達到穩定狀態。這是由于隨著訓練集規模的變大，更多的正例(存在鏈接)被加入到訓練集中。更重要的是，基本在每一步r值上，MLFS均比對應的No-FS表現出更好的分類性能，這表明算法不受訓練集大小的影響，表現出穩定的態勢。值得一提的是，當r=0.5時，Email數據集99.96%共鄰節點數目小于5，99.54%共鄰節點數目小于2，網絡變成一個非常稀疏的狀態，這樣的情況下MLFS在分類任務上仍然獲得一個較為理想的結果，表明提出算法在稀疏網絡上的靈活性和優越性。

表4 Email數據集下的訓練集規模變化下各指標的分類效果

續表4

(2) 第二部分在圖2-圖4輸出了經過MLFS篩選不同特征數目下Openflight數據集各指標的分類效果。需要指出，由于把過多的指標繪制在同一個圖表中會過于擁擠，同時F1指標綜合了Precision和Recall的效果，因此該部分實驗顯示了Accuracy、AUC和F1對應曲線，其中SVM-MLFS表示在SVM算法下經過MLFS特征選擇的分類效果，SVM-NoFS表示未經特征選擇直接分類的效果?？梢钥闯觯斕卣鲾的恐饾u變大的時候(特征數目從5到8)，對應的分類效果也呈現線性增長的趨勢。這是因為特征數目過少(5或者6)會影響分類的性能，增加相似度指標的數目有利于提高特征判別性。同時在許多情況下(例如AUC指標的NB分類算法)，當特征數目為9時分類性能并沒有顯著提升，甚至還有所降低，原因在于特征數目過多基本沒有選擇刪除了不相關或冗余的特征，等于沒有進行特征選擇步驟。綜上所述，默認特征選擇數目設置為8 既保證了實驗性能又提高了分類效率，因此是合理的。值得一提的是，在大部分的不同的特征數目設置中，經過MLFS的各指標性能優于NoFS，表明MLFS對特征數目不敏感，即無論特征數目如何變化，MLFS過程都是十分必要的。

圖2 不同特征數目下Openflight的Accuracy指標

圖3 不同特征數目下Openflight的 AUC指標

圖4 不同特征數目下Openflight的F1指標

(3) 為了驗證局部特征(Local)和全局特征(Global)對分類性能的差異化影響，本文在圖5-圖7輸出了Yeast數據集在Accuracy、AUC和F1指標下各分類器的在局部特征和全局特征下的分類效果，其中Local-MLFS表示使用局部特征并經過MLFS特征選擇的分類效果，其余表示則依次類推。從結果可以明顯看出，無論是局部特征還是全局特征，在大部分情況下MLFS比NoFS的分類性能要好。以圖7為例，可以看出MLFS表示的柱體(第二、四根柱體)比基準分類算法(第一、三根柱體)高，該結果進一步驗證了特征選擇步驟的必要性和有效性。此外，從結果也可以看出基于全局特征的分類算法和基于局部特征的分類算法各有優劣。結合在其他數據集中的統計結果可以發現，全局特征比局部特征判別性要更好，可能原因是在無監督學習鏈接預測任務中，全局特征指標比局部特征指標的整體預測性能更優。但是相關文獻也指出，特征指標的優劣和具體的網絡拓撲屬性相關，因此一類特征無法全面優于另一類特征，結合兩類特征分類是較好的方案。

圖5 Yeast數據集下局部和全局特征的Accuracy指標

圖6 Yeast數據集下局部和全局特征的AUC指標

圖7 Yeast數據集下局部和全局特征的F1指標

為了驗證MLFS步驟的通用性和可推廣性，在最后一部分實驗中擬把特征選擇到新近提出的模塊度最大化鏈接預測算法(Modularity Maximization Link Prediction Model,MMLP)當中。在MMLP中，一個重要步驟是提取基于社區劃分結構下社交網絡的拓撲結構信息，使用的8個特征分別是中介性核心性、緊密中心性、PageRank、HITS、CN、AA、JC和CC。和前文采用同樣的實驗設置，抽取的特征數目設置為6，評估指標設置為AUC。從圖8的實驗結果可以看出，在絕大部分數據集上引入MLFS過程的MMLP算法獲得了較好的性能提升，在各數據集中的預測值增長量分別是8.493%、2.369%、1.871%、-0.762%，1.891%和0.524%。這表明MLFS步驟對于引入特征進行鏈接預測或者鏈接分類的新近提出的算法均是有效的。

圖8 MLFS在MMLP模型中的影響

5 結 語

本文對信息網絡的關系分類與推斷中的特征提取與處理過程進行分析與研究，主要工作包括以下幾個部分：(1) 提取了反映信息網絡局部和全局兩類相似度特征，并提出一種基于密度估計的極大似然算法計算特征之間的互信息，該算法是一種不涉及密度估計的單步處理方法，能采用交叉驗證的方法進行模型選擇，可有效地計算出唯一的全局解。(2) 采用經典分類算法和新近提出的MMLP算法進行關系分類與推斷。通過在真實數據集上的實驗，有效驗證了本文算法的優越性和互信息特征選擇過程的必要性。

下一步將從以下幾個方面繼續深入探索：(1) 引入機器學習特征降維 、維度約減等相關算法進一步處理特征，提高算法的運行效率。(2) 由于網絡結構的復雜性，進一步把模型推廣到符號信息網絡、多維度信息網絡等場景的分類與推斷任務上。