這項研究受神經(jīng)架構(gòu)搜索（NAS）的啟發(fā)，提出將 Interstellar 作為一種處理關(guān)系路徑中信息的循環(huán)架構(gòu)。此外，該研究中的新型混合搜索算法突破了 stand-alone 和 one-shot 搜索方法的局限，并且有希望應(yīng)用于其他具有復(fù)雜搜索空間的領(lǐng)域。

視頻鏈接：https://v.qq.com/x/page/n3207ugke4j.html?start=6

知識圖譜嵌入（Knowledge Graph Embedding）目前在學(xué)習(xí)知識圖譜（KG）中的知識表達(dá)上具有很強的能力。在以往的研究中，很多工作主要針對單個三元組（triplet）建模，然而對 KG 而言，三元組間的長鏈依賴信息在一些任務(wù)上也很重要。

在第四范式、香港科技大學(xué)這篇被 NeurIPS 2020 會議接收的論文中，研究者基于由三元組組成的關(guān)系路徑（relational path）提出 Interstellar 模型，通過搜索一種遞歸神經(jīng)網(wǎng)絡(luò)，來處理關(guān)系路徑中的短鏈、長鏈信息。

論文鏈接：https://arxiv.org/pdf/1911.07132.pdf

代碼鏈接：https://github.com/AutoML-4Paradigm/Interstellar

首先，該研究通過一組模擬實驗分析了用單一模型對不同任務(wù)中關(guān)系路徑建模的難度，并由此提出通過搜索的方式對不同任務(wù)針對性地建模。為了提高搜索效率，該研究提出了一種混合搜索算法（hybrid-search algorithm），在鏈接預(yù)測（link prediction）和結(jié)點匹配（entity alignment）任務(wù)上，能高效地搜索到具有更好效果的模型。

背景介紹

知識圖譜嵌入（KG Embedding）旨在把圖譜中的結(jié)點（entities）和關(guān)系（relations）映射到一個低維空間，同時保留圖中的重要性質(zhì)。在目前學(xué)術(shù)領(lǐng)域，一些工作基于單個三元組(s,r,o)建模，如 TransE、RESCAL、DistMult、RotatE、ConvE、SimplE 等，它們在鏈接預(yù)測任務(wù)（即給定頭結(jié)點 s 和關(guān)系 r ，預(yù)測尾結(jié)點 o ）上表現(xiàn)良好，而在結(jié)點匹配任務(wù)（即給定兩個 KG，預(yù)測哪些結(jié)點有相同含義）上性能一般。另一類基于關(guān)系路徑的工作，如 IPTransE、Chains、RSN 等則在結(jié)點匹配任務(wù)上表現(xiàn)更好。

研究人員觀察到，關(guān)系路徑包含多種重要信息，如單個三元組的短鏈信息、多個關(guān)系的復(fù)合、多個三元組之間的長鏈信息等等?；诖?，該研究提出 Interstellar 模型，通過搜索的方式來根據(jù)不同任務(wù)，有針對性地對關(guān)系路徑進(jìn)行建模。

動機

為了驗證不同模型對不同任務(wù)的擬合能力不同，研究人員設(shè)計了一組模擬實驗。Countries 數(shù)據(jù)集有 S1-S3 三個不同任務(wù)，預(yù)測難度逐一增大，需要模擬的預(yù)測路徑逐漸變長。為此研究者基于先驗知識（prior knowledge）設(shè)計了 4 類模式 P1-P4，分別用于建模單個三元組、連續(xù)的兩個三元組、多重關(guān)系的復(fù)合，以及全遞歸連接。直觀上看，P4 的建模能力更強，但在有限的樣本上，樣本復(fù)雜度同樣重要，選擇更能擬合數(shù)據(jù)規(guī)律的模型能夠獲得更好的效果。

如下表所示，在 S1 這個簡單任務(wù)上，基于單個或兩個三元組的模型 P1 和 P2 表現(xiàn)更好，在 S2 上 P1-P3 均優(yōu)于 P4，而在 S3 上，遞歸模型 P4 由于能模擬更長路徑而勝出。由此我們可以得出，關(guān)系路徑上的建模應(yīng)該是模型相關(guān)的，如果我們能夠通過搜索的方式把專家的先驗知識融入到建模能力中，那么針對不同任務(wù)，模型就可以自動地找到更優(yōu)解。

問題定義與搜索空間

首先，研究者將 Interstellar 定義為一個遞歸式地處理關(guān)系路徑的模型，在每一個遞歸步中，模型關(guān)注到一個三元組，信息在三元組之內(nèi)、之間以不同方式穿梭。與傳統(tǒng) RNN 不同，這里的每一步有兩個輸入，同時由于需要考慮知識圖譜相關(guān)的領(lǐng)域知識，單純地使用 RNN 對其建模是不合適的。為了利用好知識圖譜領(lǐng)域的先驗知識，同時使模型可以適用于不同任務(wù)，受神經(jīng)網(wǎng)絡(luò)搜索技術(shù)（Neural Architecture Search）的啟發(fā)，該研究把建模問題定義為搜索問題，來自適應(yīng)地對不同任務(wù)建模。

通過對知識圖譜嵌入領(lǐng)域相關(guān)模型的總結(jié)，該研究提出上圖的搜索空間，利用運算單元 O_s 來處理結(jié)點嵌入 s_t ，用 O_r 來處理關(guān)系嵌入 r_t ，用 O_v 來輸出向量 v_t 從而預(yù)測下一個結(jié)點 s_t+1 。具體而言，該研究在 macro-level 搜索不同單元間的連接方式（connections）和復(fù)合方式（combinators），在 micro-level 搜索激活函數(shù)（activation）與權(quán)重矩陣（weight matrix）。

搜索算法

該研究的目標(biāo)是更快地在搜索空間中找到能在驗證集上達(dá)到更好性能的模型，這可以通過 bi-level 優(yōu)化方式來定義。為了求解這個優(yōu)化問題，學(xué)術(shù)界目前有兩類方法。一類是 stand-alone 算法，對每個模型單獨訓(xùn)練參數(shù) F 至收斂，這樣可以得到準(zhǔn)確的性能評估 Μ ，但訓(xùn)練代價較高；另一類是 one-shot 算法，建立一個包含所有網(wǎng)絡(luò)的超網(wǎng)絡(luò)（supernet），不同模型在超網(wǎng)絡(luò)中采樣，同時可以參數(shù)共享，這樣的評估方式更高效，但不總能保證可靠性。研究人員觀察到在 Interstellar 的建模上，one-shot 方式并不可靠。

為了解決這些問題，該研究提出 Hybrid 搜索算法，在 macro-level 采用 stand-alone 方式，給定 α_2 ，從 Α_1 中采樣不同的 α_1 ，訓(xùn)練模型參數(shù)至收斂，拿到對 α_1 的可靠評估；在 micro-level 采用 one-shot 方式，給定 α_1 ，從 Α_2 中采樣不同的 α_2 ，同時讓不同 α_2 對應(yīng)的模型在超網(wǎng)絡(luò)中共享參數(shù)，加速訓(xùn)練評估的過程。二者結(jié)合，即保證了搜索準(zhǔn)確性，又保證了搜索效率。

實驗結(jié)果

在搜索效果上，該方法在結(jié)點匹配和鏈接預(yù)測任務(wù)中，都能針對不同數(shù)據(jù)任務(wù)搜索到更好的模型，這得益于 Interstellar 上合理的搜索空間和高效的搜索算法。

在搜索效率上，Hybrid 算法能夠比隨機搜索（Random）、強化學(xué)習(xí)（Reinforce）、貝葉斯優(yōu)化（Bayes）算法更快地得到更好的模型，同時下圖中的兩條虛線（表示單獨的 one-shot 算法）表明其在這個問題上性能并不好。在搜索時間上，Hybrid 算法和調(diào)參（如 learning rate、batch size 等參數(shù)）時間是相當(dāng)?shù)?，說明這個搜索方法代價并不高。在新的問題中，先搜索模型再進(jìn)行調(diào)參是一個不錯的選擇。