腦網絡分類中的改進圖核

張森森，張大坤

(天津工業大學 天津市自主智能技術與系統重點實驗室，天津 300387)

1 引 言

腦網絡分類研究已成為腦網絡分析的一個重要分支，圖核能夠判斷兩個腦網絡數據之間的相似性，圖核的性能對分類結果有著重要的影響[1].圖核主要分為3種：基于游走的圖核、基于路徑的圖核和基于子樹或子圖的圖核[2-5].目前，很多學者對圖核進行了研究，接標等人提出了子網核來度量腦網絡之間的相似性，并將其應用于腦疾病分類[6]；蔣強榮等人提出一種間隔通路核，將其應用于文本之間的相似性計算[7]，此外，蔣強榮等人將圖核與神經網絡相結合用于蛋白質的分類[8].Mautner Stefan等人將圖核應用于RNA的分類，取得較好的分類效果[9]；然而，很多的圖核忽略了圖的標簽信息，不能有效地區分腦網絡數據之間拓撲結構的差異[10].

因此，本文提出了一種改進圖核，該圖核將路徑中的節點加上標簽信息作為判斷腦網絡相似性的因素之一，能有效地區分腦網絡數據之間拓撲結構的差異性，進而提高了腦網絡分類的準確率.

2 改進圖核研究

2.1 圖核簡介

2.1.1 圖核的作用

腦網絡分類中關鍵的問題是判斷腦網絡數據之間的相似性，圖核作為衡量結構性數據之間相似性的一種方法，能夠有效地判斷腦網絡數據之間的相似性.

2.1.2 構建圖核的理論基礎

1999年，美國斯坦福大學的Hausler教授提出了R-convolution理論，這是目前構建圖核的理論基礎[11，12].對于一對圖數據G(V1，E1)和H(V2，E2)，通過算法F對圖G、H進行分解.分解后得到的子圖集合記為{g1，g2，…，gi，…gn}和{h1，h2，…，hi，…hn}.根據R-convolution理論圖核函數定義式如公式(1)所示.

(1)

2.2 圖的分解算法

給定腦網絡數據集中的任意腦網絡數據G(V，E)，其中V表示G的節點集，E表示G的邊集.以G中任一節點vi為中心構建節點vi的子網絡.首先，求出節點vi到網絡中其他節點的最短路徑長度，將到節點vi的最短路徑小于k的節點集作為第i個子圖的節點集，原圖中對應的邊作為子圖的邊集.由此，可得到G的子圖集G={G1，G2…，G116}.對于樣本中的任意腦網絡都可按照上述方法構建出子圖集.

2.3 子結構相似性度量函數設計

腦網絡G中的任意兩個節點vi，vj之間的最短路徑記為pij如公式(2)所示：

pij=(vi，vk1，vk2，…，vkt，vj)

(2)

對于網絡中的任意的一條最短路徑pij，都可以通過L(節點集到標簽集的映射函數)將其映射為帶有標簽信息的最短路徑.節點vi，vj之間的最短標簽路徑的定義如公式(3)所示：

Lij=(L(vi)，L(vk1)，…，L(vkt)，L(vj))

(3)

給定兩個需要進行比較的子網數據g1和g2.M1和M2別表示g1和g2中節點之間的最短標簽路徑的集合，將M1和M2的并集記為M，對于其中任一子網數據gi定義其最短標簽路徑的特征向量，向量的元素計算公式如公式(4)所示：

(4)

其中Lj∈M.g1和g2之間的相似性度量核函數的定義如公式(5)所示：

(5)

該函數將兩個子網絡中加入了節點標簽的最短路徑作為判斷兩個子網絡結構之間的相似性的重要因素，能有效地判斷子網間拓撲結構的差異.

2.4 改進圖核的提出與設計

2.4.1 改進圖核的提出

目前一般研究中采用的圖核在計算數據之間的相似性時忽略了圖的標簽信息，不能有效地區分腦網絡數據之間拓撲結構的差異.為此，本文提出一種改進圖核，即加入節點標簽信息的圖核.

2.4.2 改進圖核表達形式

給定腦網絡數據集中的兩組腦網絡數據F、H，采用2.2的分解算法構建其子網絡集{F1，F2，…，Fn}和{H1，H2，…，Hn}.由公式(5)計算子結構的相似性α=δ(Fi，Hi)，則腦網絡F、H之間的圖核函數的定義如公式(6)所示：

(6)

其中，λi為權重系數.

為了更好地利用類間信息，本研究希望建立的核能夠使得不同類之間的樣本的函數值較小，因此，定義目標函數如公式(7)和公式(8)所示：

maxJ(λ1，λ2，…，λn)=

(7)

(8)

其中，D+表示數據集中的正例樣本集，D-表示數據集中反例樣本集.

確定權值系數后，圖核函數也隨之確定下來.對于2組新的腦網絡數據可直接使用公式(6)計算圖核函數值.

3 實驗及結果分析

3.1 實驗數據

本文實驗從ADNI數據庫下載了72組功能性腦影像數據，其中包括32例輕度認知障礙患者(MCI)的腦影像數據和40例健康人(CN)的腦影像數據，并將上述兩類腦影像數據處理成腦網絡數據.腦影像數據提供者具體參數如表1所示.

表1 腦影像數據來源信息表Table 1 Brain image data provider information

3.2 實驗過程及結果分析

3.2.1 實驗設計

腦網絡的分類是為了區分CN腦網絡數據和MCI腦網絡數據，圖核計算的MCI腦網絡數據與CN腦網絡數據之間的相似度越小越有利于提高分類準確率.為了驗證本文提出的改進圖核的有效性，采用最短路徑核[4]、子樹核[5]、多頻融合圖核[13]、特征選擇圖核[14]和本文提出的改進圖核在MCI腦網絡和CN腦網絡數據集上進行對比實驗，將圖核計算MCI腦網絡數據和CN腦網絡數據之間的相似度作為圖核性能的評判標準.

3.2.2 實驗過程及結果

本文提出的改進圖核、多頻融合圖核和特征選擇圖核采用Python語言編程實現，并從開源代碼庫(GitHub)中下載了Grakel軟件包來實現最短路徑核和子樹核.Grakel由Python語言編寫完成，實現了比較常用的圖核.在每次實驗中從CN腦網絡數據和MCI腦網絡數據集中各隨機抽取10個腦網絡數據分別記為DCN和DMCI，然后采用不同的圖核計算DCN和DMCI之間任意兩個腦網絡數據之間的相似性.對于每一種圖核都可以得到10*10個實驗結果.對上述實驗過程進行4輪實驗，實驗結果如圖1所示，其中橫坐標表示腦網絡數據，縱坐標表示采用5種圖核分別計算的DCN和DMCI數據之間的相似度.

3.2.3 實驗結果分析

為了更加具體地反映不同核函數的性能，本文計算了每次實驗中不同的圖核計算的CN腦網絡和MCI腦網絡數據之間的相似度的平均值，計算結果如圖2所示.由圖2可見：在每次實驗中，最短路徑核計算的CN腦網絡數據和MCI腦網絡數據之間的平均相似度最大，說明最短路徑核不能較好地區分兩類腦網絡數據；子樹核、多頻融合圖核和特征選擇圖核計算的數據之間的平均相似度均小于0.2，與最短路徑相比效果較好，能夠較好地區分兩類數據的差異；本文提出的改進圖核計算的CN腦網絡數據和MCI腦網絡數據之間的平均相似度明顯小于0.1，相比于最短路徑核、子樹核、多頻融合圖核和特征選擇圖核，改進圖核函數計算的CN腦網絡數據和MCI腦網絡數據之間的相似度最小，說明改進圖核能夠更好地反映CN腦網絡和MCI腦網絡數據之間的差異，并能提高分類的準確率.原因分析：本文提出的改進圖核在計算的過程中加入了節點的標簽信息，能夠更有效地區分腦網絡拓撲結構的差異，因此能夠更加精確地反映腦網絡數據之間的相似度.

圖1 DCN和DMCI之間的相似度對比實驗結果圖Fig.1 Experimental results of similarity between DCN and DMCI

圖2 不同圖核計算的數據的平均相似度Fig.2 Average similarity of data calculated by different graph cores

4輪實驗結果的最大值、最小值和平均值如表2所示，對其分析可見，本文提出的改進圖核計算的CN腦網絡和MCI腦網絡數據之間的相似度的最大值、最小值和平均值均小于子樹核、多頻融合圖核、特征選擇圖核和最短路徑核計算的對應值.改進圖核計算的CN腦網絡和MCI腦網絡數據間的平均相似度為0.055，子樹核計算的平均相似度為0.167，多頻融合圖核計算的平均相似度為0.182，特征選擇圖核計算的平均相似度為0.185，最短路徑核計算的平均相似度為0.488，改進圖核計算的平均相似性相比于子樹核降低了67.06%，相比于多頻融合圖核降低了69.78%，相比于特征選擇圖核降低了70.20%，相比于最短路核降低了88.72%，可見本文提出的改進圖核效果明顯.

表2 CN和MCI腦網絡數據間相似度表Table 2 Table of similarity between CN and MCI brain network data

4 總 結

為了提高圖核判斷CN和MCI腦網絡數據之間相似性的準確性，本文提出了一種加入了節點標簽信息的改進圖核.改進圖核將節點的標簽信息作為判斷腦網絡相似性的重要因素之一，有效地反映了腦網絡數據之間拓撲結構的差異性，能夠提高腦網絡分類的準確率.為了驗證改進圖核的有效性，采用改進圖核、子樹核、多頻融合圖核、特征選擇圖核和最短路徑核在腦網絡數據集上進行了對比實驗，改進圖核計算的平均相似度比子樹核計算的平均相似度降低了67.06%、相比于多頻融合圖核降低了69.78%、相比于特征選擇圖核降低了70.20%、比最短路徑核計算的平均相似度降低了88.72%.實驗結果較好地驗證了本文提出的改進圖核的有效性.