Evolving meta-correlation classes for binary similarity

二元相似性的演化元相關(guān)類別

https://www.sciencedirect.com/science/article/pii/S0031320324006228

摘要
在機器學習與模式識別領(lǐng)域，二元相關(guān)性指標的使用對實現(xiàn)精準預(yù)測與建模至關(guān)重要。本文提出一種新穎的進化方法，用于在不同應(yīng)用領(lǐng)域中發(fā)現(xiàn)二元相關(guān)性指標。該方法引入“元相關(guān)性”（meta-correlation）概念——一種表征二元相似性指標類別的參數(shù)化公式——并通過進化策略對其進行優(yōu)化。我們在基于局部拓撲相似性（即圖的鄰域結(jié)構(gòu)）的鏈接預(yù)測問題中對該方法進行了實驗與驗證。采用差分進化（Differential Evolution）優(yōu)化算法，可找出在特定領(lǐng)域中表現(xiàn)最優(yōu)的進化相關(guān)性指標。在多個網(wǎng)絡(luò)領(lǐng)域開展的實驗表明，所發(fā)現(xiàn)的元相關(guān)性實例在所有實驗領(lǐng)域中普遍優(yōu)于當前最先進的二元相關(guān)性指標。該方法能有效探索相關(guān)性空間，并找到可適配目標領(lǐng)域的獨特模式。此類元相關(guān)性類別既可用于拓撲相似性問題，也可用于語義相似性問題，僅依賴局部信息，無需掌握圖的全局完整知識。

關(guān)鍵詞：進化計算；網(wǎng)絡(luò)拓撲；復雜網(wǎng)絡(luò)；鏈接預(yù)測；二元相似性

1. 引言
   二元相關(guān)性指標（Binary Correlation Indices, BCIs）在模式識別中扮演著重要角色，廣泛應(yīng)用于諸多研究領(lǐng)域，涵蓋地質(zhì)學、生物學等自然科學與生命科學，心理學、經(jīng)濟學等社會科學，以及醫(yī)學人工智能 [1]、生物信息學 [2] 和社交網(wǎng)絡(luò)分析 [3] 等新興領(lǐng)域。
   BCIs 用于度量對象或群體之間的相似性，并支持事件預(yù)測（例如：蛋白質(zhì)–蛋白質(zhì)相互作用、蛋白質(zhì)結(jié)構(gòu)表達，以及社交網(wǎng)絡(luò)中的鏈接預(yù)測）。

形式化地：

為特定研究領(lǐng)域構(gòu)建一個有效的二元相關(guān)性指標（BCI），通常需經(jīng)歷漫長且反復迭代的過程：首先基于在其他領(lǐng)域已被證明有效的相關(guān)性，提出一個經(jīng)驗性假設(shè)；隨后通過實驗對該假設(shè)進行驗證、評估與修正，直至獲得理想結(jié)果。索倫森–戴斯指數(shù)（Sorensen–Dice index）即為一例——該指標于20世紀40年代被獨立提出，最初用于評估生態(tài)群落的相似性，此后已被廣泛應(yīng)用于計算語言學、醫(yī)學圖像分割 [4] 等多種場景。最初，Dice 指數(shù)被定義為：針對兩個不同地點 x x 與 y y，評估其各自所擁有的物種集合（設(shè)共有物種集為 F F）之間的相似性。

BCI 的構(gòu)建過程引發(fā)若干重要的研究問題，亦構(gòu)成本文的研究目標，包括以下幾點：

1. 是否可能系統(tǒng)性地改進 BCI 的構(gòu)建與領(lǐng)域適配過程？

2. 是否可從已知關(guān)系出發(fā)啟動這一過程？

3. 是否能為特定領(lǐng)域發(fā)現(xiàn)新的、最優(yōu)適配的相關(guān)性指標？

不同度量方法在各類領(lǐng)域中表現(xiàn)各異，迄今尚無單一 BCI 能全面捕捉各類鏈接形成模式的多樣性 [5]。因此，本文采用的策略是：構(gòu)建元相關(guān)性公式（meta-correlation formulas）——用以表征具有相似語法結(jié)構(gòu)的二元相似性度量類別，并通過優(yōu)化其參數(shù)系數(shù)，為特定領(lǐng)域求得最優(yōu)的 BCI。

因此，本文的主要貢獻如下：
?元相關(guān)性（meta-correlations）的提出：一種參數(shù)化公式，可表征一類二元相似性指標，并涵蓋所有基于局部鄰域（無需圖的全局完整知識）的已知指標；
?元相關(guān)性構(gòu)建框架：所提出的方法采用進化優(yōu)化算法，從元相關(guān)性出發(fā)，為給定領(lǐng)域發(fā)現(xiàn)新型相關(guān)性指標；
? 本方法借助進化算法，使元相關(guān)性能夠自適應(yīng)不同領(lǐng)域。

1. 相關(guān)工作

本文方法提出將元相關(guān)性適配至特定領(lǐng)域。矩陣分解技術(shù)（常通過對網(wǎng)絡(luò)節(jié)點的PMI矩陣進行分解 [6]，或借助DeepWalk對其進行近似 [7]）同樣利用了相關(guān)性指標的概念。然而，與直接使用現(xiàn)成相關(guān)性度量不同，本研究提出定義元相關(guān)性：通過差分進化算法（Differential Evolution, DE）[8] 對一組參數(shù)化實例（每個實例代表一種新的相關(guān)性指標）進行演化，從而發(fā)現(xiàn)面向特定領(lǐng)域的新相關(guān)性指標。

在鏈接預(yù)測中，監(jiān)督學習方法的使用通常受限于其可解釋性不足，難以刻畫網(wǎng)絡(luò)的演化動態(tài)。此前僅有的一項嘗試對相關(guān)性指標進行適配的工作 [9] 采用了16種當前先進指標的線性組合，并借助CMA-ES算法在Twitter數(shù)據(jù)上進行鏈接預(yù)測。該方法的優(yōu)勢在于能透明地識別出作為良好預(yù)測因子的指標，并可能揭示引導網(wǎng)絡(luò)演化的機制。然而，它也存在局限：一是假設(shè)最優(yōu)指標組合為線性形式；二是依賴需全局圖知識的指標（如Katz指標），這對現(xiàn)實世界的大規(guī)模網(wǎng)絡(luò)而言往往難以實現(xiàn)。

本文提出一種替代方案：通過進化算法發(fā)現(xiàn)新型公式（即我們元相關(guān)性的具體實例），使其能自適應(yīng)任意類型的數(shù)據(jù)集，包括具有異質(zhì)模式的數(shù)據(jù)集 [10]。該方法聚焦于局部度量，即便在小型網(wǎng)絡(luò)中也能避免計算不可行性。與 [9] 相比，我們的元相關(guān)性方法不僅克服了其局限性，還將適用范圍拓展至更廣泛的網(wǎng)絡(luò)結(jié)構(gòu)與數(shù)據(jù)集——涵蓋社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)與戰(zhàn)略物流網(wǎng)絡(luò)等多種情境與環(huán)境下的多樣化模式。

鏈接預(yù)測領(lǐng)域的其他研究還包括深度生成網(wǎng)絡(luò) [11] 與進化算法 [12] 的應(yīng)用。而本文方法的獨特之處在于：通過演化相關(guān)性指標實現(xiàn)對任意領(lǐng)域的自適應(yīng)——這一組合在以往研究中尚未被探索。

基于深度學習的方法通常采用圖神經(jīng)網(wǎng)絡(luò)進行新鏈接預(yù)測 [13]，其常見輸入特征包括：從原始網(wǎng)絡(luò)或派生網(wǎng)絡(luò)中學得的節(jié)點嵌入 [7]，以及傳統(tǒng)鏈接預(yù)測指標與圖度量的組合 [14]。但此類方法的主要缺陷在于缺乏可解釋性。另一些關(guān)于網(wǎng)絡(luò)中語義與拓撲關(guān)系的研究，則側(cè)重于通過學習邏輯規(guī)則進行歸納推理以預(yù)測缺失鏈接。例如，Topology Aware CorrelaTions（TACT）模型 [15] 將每一對關(guān)系歸入不同拓撲模型，并提出一種關(guān)系相關(guān)性網(wǎng)絡(luò)，以學習各模型對歸納式鏈接預(yù)測的重要性。與聚焦語義信息的統(tǒng)一模型不同，本文方法具有顯著區(qū)別：例如廣義關(guān)系學習（Generalized Relation Learning, GRL）[16] 等模型需為每個節(jié)點提供元數(shù)據(jù)，而本文方法僅利用純粹的拓撲相關(guān)性，因此可根據(jù)網(wǎng)絡(luò)的隱式結(jié)構(gòu)，靈活適配語義網(wǎng)絡(luò)與拓撲網(wǎng)絡(luò)。

最后，在缺失值估計問題背景下，文獻中已有若干方法通過將傳統(tǒng)鏈接預(yù)測問題分解為更小子問題來擴展其規(guī)模 [17, 18]。而本文方法與之有本質(zhì)不同：它不僅適用于鏈接預(yù)測與缺失鏈接問題，還可推廣至任何需通過演化二元相關(guān)性以實現(xiàn)跨域適配的問題場景。

2.1 鏈接預(yù)測與拓撲相似性

鏈接預(yù)測（Link Prediction, LP）旨在預(yù)測網(wǎng)絡(luò)的演化動態(tài)，評估網(wǎng)絡(luò)中實體（節(jié)點）之間潛在的新連接。LP 的一種常見方法是：計算所有非相連節(jié)點對之間的相似性（即圖上的鄰近性），進而預(yù)測未來最可能出現(xiàn)的鏈接。在此相似性排序中，排名靠前的節(jié)點對代表更有可能形成連接的關(guān)系。用于計算相似性的時刻 t t的網(wǎng)絡(luò)狀態(tài)稱為訓練網(wǎng)絡(luò)，而由該排序?qū)С龅男畔t在測試網(wǎng)絡(luò)（即同一網(wǎng)絡(luò)在未來時刻 t + 1 的狀態(tài)）上進行驗證。

相似性概念是該問題的核心：文獻中存在多種定義，主要包括語義相似性與拓撲相似性。前者依據(jù)節(jié)點自身的特征（主要是文本或數(shù)值型元數(shù)據(jù)）評估相似性——直觀而言，兩個節(jié)點的特征值越接近，其相似性越高；后者則關(guān)注圖的結(jié)構(gòu)及節(jié)點在網(wǎng)絡(luò)中的位置，分析范圍可限定于深度為 k 的局部鄰域，也可涵蓋整個網(wǎng)絡(luò)。典型例子包括廣泛使用的 Jaccard 指數(shù) [19] 與 Adamic-Adar 指數(shù) [20]。此類拓撲方法可應(yīng)用于復雜網(wǎng)絡(luò)的多種場景，例如病毒與細菌傳播模型。

每種現(xiàn)有的相似性指標均基于同一組指標（如共享/非共享特征——即鄰居——的數(shù)量）對每一對對象進行計算。然而，不同指標的權(quán)重設(shè)定取決于其最初設(shè)計所面向的具體領(lǐng)域。針對鏈接預(yù)測任務(wù)，已有多種度量被提出用于預(yù)測排序 [21]。形式化地：

鏈接預(yù)測在諸多現(xiàn)實應(yīng)用中具有重要意義：例如，在社交網(wǎng)絡(luò)與合作網(wǎng)絡(luò)中，可用于預(yù)測未來最可能建立連接的節(jié)點；在商品–消費者網(wǎng)絡(luò)中，可用于生成銷售推薦；在合著網(wǎng)絡(luò)中，可輔助作者消歧或?qū)I(yè)匹配。文獻中針對鏈接預(yù)測（LP）提出的最常見方法是 [19]：通過一個排序函數(shù) R ( x , y )
對每條潛在鏈接 ( x , y ) 進行評估，以估計該鏈接在未來生成的可能性；隨后對所有鏈接按得分排序，所得邊列表最終供鏈接預(yù)測應(yīng)用使用，或與真實標簽（如測試集）進行比對評估。

文獻中近期兩篇具有影響力的綜述 [19, 21] 為不同相似性度量在多樣化領(lǐng)域（從社交網(wǎng)絡(luò)到生物網(wǎng)絡(luò)、地理網(wǎng)絡(luò)）的鏈接預(yù)測應(yīng)用提供了基準。本文則對所提出的元相關(guān)性與最常用的度量進行了系統(tǒng)性比較。

我們已開始探索基于拓撲相似性度量的創(chuàng)新鏈接預(yù)測解決方案：通過擴展至二階鄰域（depth-2 neighbourhood），并利用共同鄰居對結(jié)果進行排序，從而改進傳統(tǒng)拓撲相似性方法。在對多種度量、算法、遍歷策略及實際應(yīng)用場景進行大量比較后，我們證實：拓撲相似性與語義相似性均可服務(wù)于相同應(yīng)用——即拓撲相似性度量可映射用于語義領(lǐng)域，反之亦然 [5]。我們在前期關(guān)于進化計算技術(shù)的研究 [22] 中已表明：基于相關(guān)性的相似性度量非常適合作為演化對象，用于評估節(jié)點未來生成新鏈接的可能性；且差分進化（Differential Evolution, DE）算法在此問題上表現(xiàn)優(yōu)異。

本文基于前期工作成果，以 DE 作為基礎(chǔ)進化算法，進一步深化研究：深入探究二元度量，并分析其在元相關(guān)性框架下最優(yōu)的演化方式。最終得到一類新型演化的元相關(guān)性指標，可涵蓋當前最先進的二元相關(guān)性指標（BCI）實例。我們對兩類元相關(guān)性（每類采用兩種不同交叉算子）的實驗結(jié)果，與它們所涵蓋的15種指標、文獻中廣泛使用的9種拓撲度量，以及一個隨機預(yù)測器進行了對比。元相關(guān)性在10個數(shù)據(jù)集（5個社交網(wǎng)絡(luò)、3個生物網(wǎng)絡(luò)、2個含地理約束的網(wǎng)絡(luò)）上進行測試，與所涵蓋指標相比，其性能以平均精確率（Precision）為評估標準；隨后，以AUC為評估指標與適應(yīng)度函數(shù)，采用最大值與平均值作為聚合方式，將元相關(guān)性與當前最先進的拓撲鏈接預(yù)測度量進行比較。

2.2 二元相似性

二元相關(guān)性指標（Binary Correlation Indices）是刻畫生物學、醫(yī)學、經(jīng)濟學、社會學等諸多領(lǐng)域中各類對象特性的有力工具。文獻中已積累了大量此類指標 [23]，充分證明了其在科研中的有效性。例如，Dice 指數(shù)（又稱 S?renson 指數(shù)或 Czekanowski 指數(shù)）最初在植物學中被提出，用于研究生態(tài)群落（見第1節(jié)），此后已被拓展應(yīng)用于醫(yī)學圖像分割、計算機詞典學等領(lǐng)域，用以評估主語–動作–賓語結(jié)構(gòu)間的語言關(guān)聯(lián)性。

現(xiàn)有相關(guān)研究文獻 [9] 提出了一種具有類似進化步驟的方法，但其依賴于線性組合，存在如引言所述的局限性。相比之下，我們的方案可直接與所有基于鄰域的二元相似性度量（如2.1節(jié)所述 [21]）進行比較——這些度量均被用于鏈接預(yù)測，且同時適用于拓撲相似性與語義相似性任務(wù)。

1. 所提方法
   先前研究結(jié)果 [22] 已證實：二元相似性度量可用于拓撲鏈接預(yù)測任務(wù)。第3.1節(jié)將闡述如何將二元相似性指標映射為鏈接預(yù)測中的拓撲指標；第3.2節(jié)與第3.4節(jié)則給出元相關(guān)性（meta-correlations）的定義，并說明其基于差分進化（Differential Evolution, DE）算法的演化方案。

3.1 拓撲相似性到二元相似性的映射
本方法的一個基本出發(fā)點是：證明現(xiàn)有拓撲指標可被重新表述為二元相關(guān)性形式。

盡管該定義形式簡潔，卻具有重要推論：它實現(xiàn)了拓撲指標與二元相關(guān)性指標之間的雙向映射。例如，考慮 Jaccard 指數(shù) [24] 的拓撲形式（見公式 (2)）：

將拓撲特征映射為二元特征的積極影響是雙重的：若干用于鏈接預(yù)測的拓撲指標原本以節(jié)點度和鄰居集合 Γ 表示，現(xiàn)均可被重新表述為二元相關(guān)性指標；例如，經(jīng)本文提出的重構(gòu)方法，共同鄰居（Common Neighborhood）可簡化為：

另一方面，原本并非為拓撲相似性設(shè)計的相關(guān)性指標，也可通過重新表述而應(yīng)用于網(wǎng)絡(luò)場景。任意二元相關(guān)性指標只需適當?shù)赜嬎銋?shù) a , b , c , d
，即可用于鏈接預(yù)測（LP）問題。

3.2 元相關(guān)性指標

考察表1前兩列所列的二元相關(guān)性指標，我們發(fā)現(xiàn)：許多指標可被視為一種基本語法結(jié)構(gòu)的變體——即相關(guān)因子 a , b , c , d的線性與非線性組合之間的比值；這些組合在乘性系數(shù)和所用運算符（如加法、減法、乘法）方面存在差異。基于這一觀察，可定義元相關(guān)性指標（meta-correlation index）的概念。

3.3 元相關(guān)性的設(shè)計

本文設(shè)計了兩類主要的元相關(guān)性，旨在涵蓋文獻中已知的二元指標集合，以及鏈接預(yù)測中使用的拓撲指標。

設(shè) u u 與 v v 為網(wǎng)絡(luò)中的兩個節(jié)點，其一階特征包括：

公式 (11) 與公式 (12) 展示了兩種元指標的表達形式；表1列出了部分被涵蓋的指標及其對應(yīng)的參數(shù)賦值。

3.4 用于鏈接預(yù)測的差分進化

我們的總體目標是：針對鏈接預(yù)測（LP）任務(wù)，優(yōu)化相關(guān)性指標的預(yù)測能力——通過定義二元相關(guān)性元指標，并為其尋找適配特定領(lǐng)域的參數(shù)配置。差分進化（Differential Evolution, DE）作為一種穩(wěn)健且被深入研究的進化計算算法 [25]，非常適合用于演化元相關(guān)性的系數(shù)向量。因此，本文所提出的方法將采用差分進化算法，對一組元相關(guān)性指標實例構(gòu)成的種群進行演化，同時優(yōu)化它們在鏈接預(yù)測任務(wù)中的性能表現(xiàn)。

針對鏈接預(yù)測任務(wù)、適配于元相關(guān)性指標演化的連續(xù)型差分進化算法結(jié)構(gòu)，如偽代碼 Algorithm 1 所示，其中Dimensions表示元相關(guān)性指標參數(shù)的維度（即參數(shù)個數(shù)）。

3.5 差分進化策略與種群初始化

在差分進化中，選擇個體構(gòu)建變異向量的策略，以及決定在哪些維度上執(zhí)行交叉操作，是影響性能的關(guān)鍵決策。本文考慮了兩種差分進化變異與交叉策略變體，依據(jù)標準DE命名規(guī)范，分別簡記為：

1. RAND/1/EXP：指數(shù)型交叉策略（EXP）
2. RAND/1/BIN：二進制交叉策略（BIN）

兩種變體中，用于構(gòu)建變異向量的個體均隨機選取。

差分進化的一個已知問題是：當某個參數(shù)值出現(xiàn)完全或高度一致時，種群多樣性易喪失。對于本文的元相關(guān)性實例而言，該問題尤為突出——因其涵蓋的指標往往共享相同的參數(shù)取值。因此，通過在初始種群中引入經(jīng)噪聲擾動的個體，可有效緩解此問題。

1. 實驗：數(shù)據(jù)與設(shè)置
   本節(jié)介紹并說明實驗所用數(shù)據(jù)集、預(yù)處理階段及實驗設(shè)置。

4.1 數(shù)據(jù)集
為便于比較，我們在10個廣泛用于鏈接預(yù)測（LP）實驗、并被近期高影響力綜述文獻 [19, 21] 所引用的數(shù)據(jù)集上測試了所提框架。所選數(shù)據(jù)集涵蓋三類重要領(lǐng)域：

• 社交數(shù)字通信網(wǎng)絡(luò)

  （如社交網(wǎng)絡(luò)、電子郵件交互、合著網(wǎng)絡(luò)）；

• 生物網(wǎng)絡(luò)

  （如蛋白質(zhì)–蛋白質(zhì)相互作用、連接組、簡單生物體（如線蟲）的神經(jīng)連接網(wǎng)絡(luò)、動物社群）；

• 地理網(wǎng)絡(luò)

  （受地理因素制約的物理通信網(wǎng)絡(luò)，如交通網(wǎng)絡(luò)、路由器網(wǎng)絡(luò)）。

社交數(shù)字通信網(wǎng)絡(luò)：

• CA-GrQC

  [26]（GRQ）與Netscience[27]（NSC）是兩個經(jīng)典合著網(wǎng)絡(luò)，分別包含1993–2004年間廣義相對論與量子宇宙學領(lǐng)域，以及網(wǎng)絡(luò)科學領(lǐng)域的論文合作關(guān)系；

• Email-eu-core

  [26, 28]（EUC）為某歐洲機構(gòu)員工間的電子郵件通信網(wǎng)絡(luò)；

• Ia-radoslaw-email

  [29]（RAD）為一家制造企業(yè)員工間的郵件往來網(wǎng)絡(luò)；

• PetsterHamster

  [30]（PET）刻畫了 Hamsterster.com 社交平臺上用戶間的友誼關(guān)系。

生物網(wǎng)絡(luò)：

• Macaque [31]（MAC）為恒河猴大腦皮層的神經(jīng)連接映射；
• 蛋白質(zhì)–蛋白質(zhì)相互作用網(wǎng)絡(luò)（PPI）源自文獻 [32]；
• C.Elegans [33]（CEL）為秀麗隱桿線蟲的完整神經(jīng)網(wǎng)絡(luò)。

地理網(wǎng)絡(luò)：
該類數(shù)據(jù)集中，地理因素對網(wǎng)絡(luò)結(jié)構(gòu)具有決定性影響。

• USAir [34]（USA）為1997年美國航空航線網(wǎng)絡(luò)，雖因航程受限時新建航線相對便捷而使地理約束有所緩解，但仍呈現(xiàn)類似現(xiàn)象；
• Football （FOB）為美國某橄欖球聯(lián)盟的地區(qū)錦標賽比賽關(guān)系數(shù)據(jù)集

4.2 預(yù)處理階段

數(shù)據(jù)集需經(jīng)過預(yù)處理階段：有向網(wǎng)絡(luò)被轉(zhuǎn)換為無向網(wǎng)絡(luò)（當至少存在一條原始有向邊時），并移除自環(huán)和孤立節(jié)點，因為它們對基于直接鄰居的相關(guān)性指標沒有任何貢獻。

4.3 差分進化（DE）參數(shù)設(shè)置與運行配置

最大進化代數(shù)（MaxGenerations）經(jīng)實驗設(shè)為300。圖1以PPI數(shù)據(jù)集為例，采用元相關(guān)性指標?展示了進化過程的動態(tài)變化情況；每條曲線對應(yīng)一次折疊（fold）上的演化過程，所采用策略為DE RAND/1/BIN，并從中10次折疊中選取了5次予以展示�？梢钥闯觯嚓P(guān)性空間中存在若干平臺區(qū)域（plateaus），即適應(yīng)度函數(shù)返回相同得分的區(qū)域，從而減緩了進化過程中的性能提升。針對其他數(shù)據(jù)集、相關(guān)性指標及交叉策略組合也進行了實驗，均表現(xiàn)出類似行為：絕大多數(shù)情況下，從第一代至最后一代性能提升顯著；但當進化代數(shù)超過300時，適應(yīng)度不再呈現(xiàn)可觀測的進一步改善。

突變縮放因子F與交叉概率參數(shù)CR分別設(shè)為0.7和0.5，該設(shè)定位于取值范圍 ∈ [0, 2]、 ∈ [0, 1]之內(nèi)，并符合我們對適應(yīng)度函數(shù)的預(yù)期假設(shè)。

對于?，種群規(guī)模設(shè)為27個個體，其中初始種群包含9個已知可被?涵蓋的經(jīng)典指標個體，其余18個個體通過在這些基準指標基礎(chǔ)上添加噪聲擾動生成。對于?，種群規(guī)模為24個個體，其中6個初始個體對應(yīng)已知可被?涵蓋的經(jīng)典相關(guān)性指標，其余18個同樣通過噪聲擾動生成。

在候選適應(yīng)度函數(shù)中（參見第3.4節(jié)），經(jīng)系統(tǒng)性測試，AUC（曲線下面積）被選定為最終使用的適應(yīng)度指標——該選擇源于前期實驗中AUC展現(xiàn)出的主導性性能優(yōu)勢。

1. 實驗結(jié)果
   本節(jié)展示了實驗結(jié)果。關(guān)鍵數(shù)據(jù)以表格與圖表形式呈現(xiàn)。所得精度（Precision）與AUC結(jié)果，均與當前最先進的排序相關(guān)性指標進行了對比。同時，對所發(fā)現(xiàn)的元相關(guān)性（meta-correlations）進行了討論。

5.1 元相關(guān)性的精度

為評估精度，表3–6右側(cè)各列展示了每種演化所得的元相關(guān)性變體——即1-、1-、2-與2-——在各數(shù)據(jù)集上相對于兩類基準指標所實現(xiàn)的精度提升值：

• 第一類為被其涵蓋（subsumed）的經(jīng)典指標（見表中第一區(qū)塊）；

• 第二類為鏈路預(yù)測領(lǐng)域中常用的標準拓撲相關(guān)性指標（見表中第二區(qū)塊）。

表中每個條目均表示精度提升量，即：對應(yīng)行中該指標所得精度值，與每一（元相關(guān)性，DE交叉策略）組合下十次演化所得相關(guān)性在測試集上精度的平均值之間的差值。

各指標縮寫如下：3WJaccard（T 3WJT）、 Sokal Sneath 1（T SS1）、 Sokal Sneath 2（T SS2）、 Rogers Tanimoto（T RT）、 Faith（T Fa）、 Sokal Sneath 3（T SS3）、 Kulczynski 1（T Ku1）、 Gower Legendre（T GL）、 Cosine（T Co）、 Sorensen（T So）、 Mountford（T Mo）、McConaughey（T McC）、 Johnson（T Jo）、 Kulczynski 2（T Ku2）、Common Neighbours（CN）、Jaccard（Jacc）、Preferential Attachment（PA）、Sorensen（So）、Hub Promoted（HubP）、Hub Depressed（HubD）、Leicht Holme Newman（LHN）、Random（Rnd）。

在表8中，報告并比較了Netscience數(shù)據(jù)集上各參考指標的真陽性絕對數(shù)量與精度值，并與表7中每個（元相關(guān)性，DE交叉策略）組合的平均值進行了對比。所有元相關(guān)性的提升均顯著，盡管其絕對真陽性數(shù)值的提升受限于邊數(shù)。

我們可以觀察到，幾乎所有的增量均為正值，即演化所得的元相關(guān)性指標表現(xiàn)優(yōu)于原始相關(guān)性指標，且超越了二進制或指數(shù)型DE突變/交叉策略。最大的偏差可歸因于部分原始指標表現(xiàn)較差。因此，值得關(guān)注的是最小差異值——它表示最佳表現(xiàn)的參考相關(guān)性指標與演化指標平均表現(xiàn)之間的增量。除Football數(shù)據(jù)集外（該數(shù)據(jù)集呈現(xiàn)大部分負值），所有數(shù)據(jù)集上均可觀察到對被涵蓋指標的性能提升，其幅度從Netscience數(shù)據(jù)集上的約2%最低提升，到同一數(shù)據(jù)集上約50%的顯著提升不等；而在Ia-radoslaw-email數(shù)據(jù)集上，若干指標的提升約為44%，此處演化相關(guān)性表現(xiàn)出最高的最小增量預(yù)測性能。在進化階段，系統(tǒng)能有效引導搜索朝向相關(guān)性空間中適應(yīng)度最佳的區(qū)域，同時排除表現(xiàn)最差指標的貢獻。可以觀察到，在Netscience、PPI、Hamsterster和Ia-radoslaw-email數(shù)據(jù)集上，?-BIN組合（即元相關(guān)性?與二進制交叉策略）排名首位；而在CA-GrQc、Macaque、UsAir、C. Elegans及Email-eu-core數(shù)據(jù)集上，?-EXP表現(xiàn)更優(yōu)�？傮w而言，?似乎更適合該過程，因為除所選交叉策略外，其演化所得的相關(guān)性實例始終優(yōu)于?實例。如前所述，F(xiàn)ootball數(shù)據(jù)集在?和?上均呈現(xiàn)輕微下降（即<1×10?2）；而?在采用EXP交叉策略時仍能改善幾乎所有指標的性能，但在此情況下差異微小。關(guān)于拓撲指標第二區(qū)塊，

更大的差異出現(xiàn)在Netscience數(shù)據(jù)集上，其中發(fā)現(xiàn)的相關(guān)性在Preferential Attachment指標上實現(xiàn)了約50%的提升。在Ia-radoslaw-email數(shù)據(jù)集中，發(fā)現(xiàn)的相關(guān)性在Hub Promoted和LHN指標上獲得了約40%的提升。這兩種指標屬于原始測量方法可能表現(xiàn)較低因而潛力更高的情況。Preferential Attachment和Hub Promoted均更傾向于預(yù)測已擁有大量連接的節(jié)點之間形成新鏈接（第一種情況中的偏好節(jié)點，第二種情況中的樞紐節(jié)點）。這一特性并非適用于所有數(shù)據(jù)集：在測量方法表現(xiàn)較差的情況下，我們的指標更有可能超越其預(yù)測能力。

盡管所發(fā)現(xiàn)的相關(guān)性在系數(shù)值上有所不同，但它們在?和?下均實現(xiàn)了相似的性能，表明相關(guān)性空間中存在具有相似適應(yīng)度值的局部極大值。圖2展示了每個數(shù)據(jù)集演化的詳細結(jié)果：每個箱形圖描繪了針對某一（元相關(guān)性，DE交叉策略）組合在十次運行實例（每次對應(yīng)一個折疊）中測試集_上的精度值；箱體中間線表示中位數(shù)，十字符號表示均值。箱體底部和頂部線分別代表第一四分位數(shù)?和第三四分位數(shù)?，觸須延伸至數(shù)據(jù)集的最小值和最大值。孤立點表示離群值，即距離?或?超過1.5倍四分位距（IQR=???）的數(shù)據(jù)點。我們觀察到多數(shù)情況下表現(xiàn)相似，僅有少數(shù)案例顯著高于或低于中位數(shù)，例如Ia-radoslaw-email數(shù)據(jù)集，以及程度較輕的Netscience數(shù)據(jù)集。

5.2 發(fā)現(xiàn)的相關(guān)性

所采用的進化方法針對特定領(lǐng)域?qū)υ嚓P(guān)性進行了優(yōu)化。對于Netscience（NSC）數(shù)據(jù)集，最優(yōu)排序相關(guān)性為 ?(, )ΠNSC，其對應(yīng)的優(yōu)化元參數(shù)向量如下：

保留至小數(shù)點后兩位，由此得到以下公式：

值得指出的是，公式（14）至公式（19）中的相關(guān)性此前從未在文獻中出現(xiàn)過，均由本文所提出的進化式領(lǐng)域自適應(yīng)與優(yōu)化過程所發(fā)現(xiàn)。

5.3 元相關(guān)性的 AUC

我們將各類元相關(guān)性的 AUC 與近期一篇頗具影響力的鏈路預(yù)測綜述文獻[19, 21]中所列舉的最常用拓撲指標的 AUC 進行了比較（見表9）。

每列表示一個不同的數(shù)據(jù)集；第一區(qū)塊列出了最常用的拓撲二元相關(guān)性指標，第二和第三區(qū)塊則記錄了我們提出的兩類元相關(guān)性指標。元相關(guān)性的 AUC 結(jié)果基于對給定領(lǐng)域數(shù)據(jù)集相同劃分下進行的10次進化運行所得，針對四種（, 策略）組合（即 ?-EXP、?-BIN、?-EXP、?-BIN）分別計算；結(jié)果按聚合函數(shù)分為兩類呈現(xiàn)：取各次運行中最優(yōu)/最大值（BEST）的 AUC，以及取平均值（AVG）的 AUC�；鶞释負渲笜说男阅芤嘣谕粩�(shù)據(jù)劃分上進行評估。表中凡超過所有基準 AUC 的數(shù)值均加粗顯示。

大量加粗數(shù)值清晰表明元相關(guān)性方法具備優(yōu)異性能。BEST 聚合結(jié)果顯示：即便在相關(guān)性空間中存在較大方差、從而顯著影響平均性能的情況下，某些元相關(guān)性在所有數(shù)據(jù)集上仍能超越表現(xiàn)最佳的拓撲指標。在部分數(shù)據(jù)集（如 C. Elegans 和 Football）中，我們的兩類元相關(guān)性均優(yōu)于基準指標；在 PetsterHamster 和 Macaque 數(shù)據(jù)集中，多數(shù)元相關(guān)性組合達到或超過了基準指標性能；在 UsAir 數(shù)據(jù)集中，無論采用 EXP 還是 BIN 策略，? 的表現(xiàn)均優(yōu)于 ?�？傮w而言，并不存在一類元相關(guān)性始終優(yōu)于另一類；但 ? 通常展現(xiàn)出更高的 AUC：在每一個數(shù)據(jù)集上，由 ? 演化得到的元相關(guān)性均優(yōu)于文獻中用于鏈路預(yù)測的現(xiàn)有最先進拓撲相似性指標——這一結(jié)論與第4節(jié)中關(guān)于精度（Precision）相對于其所涵蓋相似性指標的提升結(jié)果一致。因此，我們可以得出結(jié)論：所演化的元相關(guān)性實例，其性能優(yōu)于當前鏈路預(yù)測文獻中主流的拓撲相似性度量，且展現(xiàn)出顯著的領(lǐng)域自適應(yīng)能力。

1. 結(jié)論

本研究提出了一種新穎且具創(chuàng)新性的進化方法，用于生成面向特定領(lǐng)域的二元相關(guān)性指標。該方法利用優(yōu)化算法探索相關(guān)性類別，并引入參數(shù)化元相關(guān)性（parametric meta-correlations）的概念——當參數(shù)取特定值時，這些元相關(guān)性可涵蓋諸多已知的二元指標。這一特性使我們得以在相關(guān)性類別內(nèi)部開展演化與搜索。我們以鏈路預(yù)測為應(yīng)用場景，對所提方法的有效性進行了實驗驗證。鏈路預(yù)測在拓撲背景下使用二元指標，通過利用局部網(wǎng)絡(luò)結(jié)構(gòu)信息來評估節(jié)點間的相似性，并對潛在鏈接形成的概率進行排序。

本文方案在兩類元相關(guān)性?與?上進行了測試，二者均可涵蓋大量經(jīng)典二元相關(guān)性指標；并采用差分進化（DE）的兩種變體——BIN 與 EXP——對其進行演化優(yōu)化。演化過程中，以 AUC 評估指標作為適應(yīng)度函數(shù)。該方法在三類鏈路預(yù)測領(lǐng)域（社交數(shù)字通信、生物網(wǎng)絡(luò)、地理網(wǎng)絡(luò)）共計十個數(shù)據(jù)集上進行了測試。結(jié)果表明，相較于近期具有影響力的研究所列舉的拓撲指標及被涵蓋指標，該方法能夠發(fā)現(xiàn)性能更優(yōu)的二元指標實例。

實驗顯示，在精度（Precision）方面，相對于被涵蓋指標及其他常用拓撲指標，本方法的提升幅度從平均最低約2%（如 CA-GrQc 數(shù)據(jù)集）至最高約50%（如 Netscience 數(shù)據(jù)集）不等；在 Ia-radoslaw-email 數(shù)據(jù)集中觀察到約44%的顯著最小提升。Football 數(shù)據(jù)集中出現(xiàn)較多千分位級別的負值（即性能輕微下降），可歸因于該網(wǎng)絡(luò)鏈接總數(shù)較少——單次預(yù)測結(jié)果即代表較大比例，因而波動更顯著。在四種（元相關(guān)性，策略）組合中，? 似乎更適于探索二元相關(guān)性空間：無論采用 BIN 或 EXP 策略，基于 ? 演化所得的相關(guān)性實例始終優(yōu)于基于 ? 的實例。對于 ?，EXP 策略在五個數(shù)據(jù)集上表現(xiàn)更佳；而 BIN 策略僅在四個數(shù)據(jù)集上對 ? 取得最優(yōu)結(jié)果。

在 AUC 指標上，所有演化所得的元相關(guān)性在絕大多數(shù)數(shù)據(jù)集（包括 Football）上均超越了當前最先進的基準指標。這凸顯了演化所得元相關(guān)性卓越的跨領(lǐng)域泛化能力，及其對特定領(lǐng)域的強自適應(yīng)性。

因此，本文提出的研究問題（見第1節(jié)）可回答如下：

1. 本研究引入的框架——即對元相關(guān)性指標進行進化計算——是一種系統(tǒng)性開發(fā)與適配二元相關(guān)性指標的恰當方法。

2. 元相關(guān)性這一概念，因其能夠涵蓋并統(tǒng)攝現(xiàn)有相關(guān)性關(guān)系，使得演化過程得以從已確立的知識基礎(chǔ)出發(fā)。

3. 在不同領(lǐng)域開展的實驗結(jié)果表明，發(fā)現(xiàn)性能優(yōu)于當前最先進指標的新相關(guān)性是切實可行的。

綜上所述，本文所提出的、用于生成領(lǐng)域適配型二元相關(guān)性指標的進化方法已得到驗證，并在鏈路預(yù)測任務(wù)中展現(xiàn)出優(yōu)于現(xiàn)有拓撲度量的性能。與傳統(tǒng)方法（例如對已有指標的線性組合權(quán)重進行演化）以及其他黑箱方法（如深度學習）相比，本方法具有明顯優(yōu)勢：它不僅能發(fā)現(xiàn)全新的相關(guān)性指標，還通過顯式提供演化所得優(yōu)化元相關(guān)性實例中各參數(shù)的權(quán)重，顯著提升了模型透明性，從而為理解相關(guān)性結(jié)構(gòu)及其潛在機制提供了寶貴洞見。

此外，本方法具備廣泛的應(yīng)用潛力，可拓展至鏈路預(yù)測以外的諸多領(lǐng)域；例如在生物學中，可用于揭示疾病、癥狀與治療之間的潛在關(guān)聯(lián)。

原文鏈接： https://www.sciencedirect.com/science/article/pii/S0031320324006228