編者按：知識圖譜（Knowledge Graph，KG）蘊含着豐富的人類知識資訊，近年來在人工智能領域發揮着越來越重要的作用，已被廣泛地應用于多個領域。然而，知識圖譜難以避免地存在不完整的問題，這在很大程度上限制了相關應用的性能表現。作為一種有效緩解此問題的方法，知識圖譜表示學習（Knowledge Graph EmbeAdding，KGE）近年來受到了學術界的關注與研究。在 ICML 2022 被接收的論文中，微軟亞洲研究院與大連理工大學合作的最新研究工作《HousE: Knowledge Graph Embedding with Householder Parameterization》提出了一種具有強大且全面模組化能力的KGE模型，名為HousE。
論文作者：李銳（大連理工大學），趙健安（凱斯西儲大學），李朝卓（MSRA）、賀笛（MSRA）、孫浩（微軟Bing）、謝幸（MSRA）、申彥明（大連理工大學）等
論文連結：https://arxiv.org/pdf/2202.07919.pdf
代碼連結：https://github.com/rui9812/HousE
什麼是KGE
KGE模型旨在學習KG中實體和關系的表示，并定義一個評分函數來衡量三元組的合理性，用于預測缺失的連結。這些模型的性能表現很大程度取決于對KG中關系模式（relation pattern）和關系映射屬性（relation mapping property）的模組化能力。
知識圖譜中重要的關系模式有：（1）對稱，如is_friend_of就是一種對稱關系；（2）非對稱，如is_father_of就是一種非對稱關系；（3）互逆，如is_teacher_of和is_student_of就是一對互逆的關系；（4）組合，如is_grandmother_of就是is_father_of和is_mother_of的組合關系。而關系的映射屬性則有一對一關系、一對多關系、多對一關系和多對多關系。圖1展示了四種重要的關系模式和兩種複雜的關系映射屬性。
圖1 四種重要關系模式和兩種複雜映射屬性
Motivation
本研究對現有代表性KGE方法的模組化能力進行總結（表1），并進一步分析了其存在的局限性：（1）現有工作已經證明将關系視為實體間的旋轉變換是一種可以模組化多種關系模式的有效方法，然而由表1中的最後一列可以看出，現有方法中的關系旋轉固定于低維空間（2、3、4維），這很大程度地限制了模型的模組化能力；（2）由表1中的2-6列可以看出，現有方法無法全面地模組化知識圖譜中的重要關系模式與複雜映射屬性。
表1 現有代表性KGE模型對重要關系模式和複雜映射屬性的模組化能力
以上問題促使研究員們思考：如何設計一個具有更強大、更全面模組化能力的KGE模型？這其實引發了兩個子問題：
（1）如何強大：現有模型的模組化能力受限于低維空間的關系旋轉，那麼獲得強大模組化能力的關鍵則在于如何自由地擴充關系的旋轉次元。
（2）如何全面：已有工作希望通過設計關系投影變換來模組化複雜映射屬性，但将這些不可逆的關系投影與旋轉變換結合會導緻模型失去模組化逆關系群組合關系的能力，是以獲得全面模組化能力的關鍵則在于如何設計可逆的關系投影變換來與旋轉結合。
Householder架構
為解決以上兩個問題，本研究引入Householder反射變換作為基本數學工具，并基于此進一步設計了兩種線性變換作為KG中的關系表示：
（1） 由多個Householder反射組合而成的Householder旋轉，實作了強大的模組化能力；
（2） 由原始Householder反射修改而來的Householder投影，實作了全面的模組化能力。
在此Householder架構下，本研究得以提出了一個更強大、更全面的KGE模型，名為HousE。如表1所示，HousE能夠自然地将旋轉擴充到任意的K維，并且可以全面地模組化表1中所有關系模式與映射屬性。與此同時，不難看出HousE是現有基于旋轉的KGE模型的推廣。
Householder反射
圖2 二維空間中的Householder反射
Householder矩陣常用于數值代數（如正交分解等），用于描述關于一個（過原點）超平面的基本反射變換。給定一個機關向量u∈R^k，k×k的Householder矩陣H由變量U生成，定義為：
其中I為k×k的機關矩陣。從幾何上來看，如圖2所示，Householder矩陣能夠對向量X做關于以U為機關法向量的超平面的鏡面反射，即Householder反射變換：
其中⟨⋅⟩表示内積運算。需要注意的是，該變換中的矩陣和向量間乘法可以直接轉化為向量間操作，這為本研究在效率上的可行性提供了保障。
Householder旋轉
基于Householder矩陣，本研究定義一個映射來表示旋轉。給定2n個機關向量{u_c }_(c=1)^2n，其中u_c∈R^k，n為正整數，定義如下映射：
針對此映射，本研究從理論上證明了當n=⌊k/2⌋時，任意k×k的旋轉矩陣都可以通過映射Rot-H計算得到。這意味着任意的k維旋轉都可以表示為2⌊k/2⌋個Householder反射的組合，比如任意二維空間中的旋轉都可以分解為兩個基本反射。本研究将這種由2⌊k/2⌋個Householder反射組合而成的旋轉稱為Householder旋轉，進而以此方式自然地将知識圖譜中的關系表示為K維空間中的旋轉變換，進而獲得更為強大的模組化能力。
Householder投影
旋轉變換被證明能夠有效模組化表1中的四種關系模式，然而，由于其嚴格的保距性質，單純的關系旋轉無法有效地處理知識圖譜中複雜的關系映射屬性（一對多、多對一和多對多）。本研究注意到前人的方法（TransH、TransR等）希望引入關系投影變換來模組化映射屬性，然而這些模型中的投影變換均是不可逆的，這會導緻模型失去對逆關系群組合關系的模組化能力。為了解決這一問題，本研究通過對原始的Householder矩陣進行修改，提出了一種新的可逆投影，稱為Householder投影。
更具體地說，給定一個機關向量p∈R^k和一個實數标量τ，對原始Householder矩陣的定義稍作修改，得到k×k的矩陣M，M由變量P和τ生成，定義為：
數學上可以算出，M(p,τ)有(k-1)個特征值為1，1個特征值為(1-τ)，是以當τ≠1時，M(p,τ)總是可逆的。從幾何上來看，M(p,τ)能夠對向量X做沿着P軸的基本投影變換：
其中标量τ決定了投影後x ̂的位置，該變換中的矩陣和向量間乘法也可以直接轉化為向量間乘法。圖3展示了二維空間中，不同τ值下投影後x ̂的不同位置。
圖3 二維空間中M(p,τ)在不同τ值下對應的投影變換
基于以上的基本投影矩陣M，本研究定義一個映射來表示投影。給定一組标量T={τ_c }_(c=1)^m和機關向量P={p_c }_(c=1)^m，其中p_c∈R^k，m為正整數，定義如下映射：
由于可逆矩陣的乘積仍然是可逆矩陣，是以上述映射的輸出也是一個可逆矩陣，對應的投影變換同樣是可逆的。本研究将這種由m個修改後的Householder反射組合而成的可逆投影稱為Householder投影。不同于前文中嚴格保距的關系旋轉變換，Householder關系投影可以在保證可逆性的同時改變實體之間的相對距離，故能夠在不損失對關系模式模組化能力的同時有效地處理複雜的關系映射屬性（一對多、多對一和多對多）。
HousE
圖4 HousE圖示
結合所設計的Householder旋轉與Householder投影，本研究将這兩種變換納入一個統一的架構，提出了一種全新的KGE模型，稱為HousE。如圖4所示，對于給定三元組(h,r,t)，S_h,S_t∈R^(d×k) 分别的頭實體h和尾實體t表示，其中d為實體嵌入表示大小，k為行向量次元，即S_h [i],S_t [i]∈R^k,i∈{1,…,d}。。HousE首先通過Householder投影得到關系r特定的頭尾實體表示S_(h,r)和S_(t,r)，然後對投影後的頭實體表示S_(h,r)進行Householder旋轉，希望旋轉後的結果與S_(t,r)盡可能相近。也就是說，HousE将關系r模組化為實體間行級的兩階段變換：
關系投影階段：HousE首先利用Householder關系投影将實體h和t表示映射為關系r特定的表示S_(h,r)和S_(t,r)。詳細來說，HousE為關系r定義參數P_(r,1),P_(r,2)∈R^(d×m×k)和T_(r,1),T_(r,2)∈R^(d×m)，利用Pro-H映射對頭尾實體的行級表示進行投影：
關系旋轉階段：在完成對頭尾實體的投影變換後，HousE在投影後的頭實體表示S_(h,r)和尾實體表示S_(t,r)之間模組化Householder關系旋轉變換。詳細來說，HousE為關系r定義參數U_r∈R^(d×2⌊k/2⌋×k)，利用Rot-H映射對投影後的頭實體表示S_(h,r)做行級的Householder關系旋轉，希望旋轉後的表示與投影後的尾實體表示S_(h,r)盡可能相近：
這意味着HousE的評分函數為：
在以上投影和旋轉的變換過程中，所有的矩陣和向量間乘法都可以替換為向量間乘法，以保證高效的計算。得益于投影的可逆性和旋轉的可擴充性，HousE能夠全面有效地模組化表1中所有的關系模式和映射屬性，并且可以視為現有旋轉模型的推廣。
實驗分析
主實驗
在實驗階段，該研究在五個公開知識圖譜基準資料集上驗證所提方法的有效性，分别為WN18、FB15k、WN18RR、FB15k-237和YAGO3-10。HousE在這五個資料集的知識圖譜補全任務上的實驗結果如表2和表3所示，其中HousE-r為僅使用Householder關系旋轉（無Householder關系投影）的基礎模型。為了保證比較的公平性，本研究限制了HousE和HousE-r的參數量，使得總參數量與基線模型相近，甚至是遠少于基線方法。
表2 在WN18和FB15k資料集上的實驗結果
表3 在WN18和FB15k資料集上的實體預測結果
從實驗結果可以觀察到，相對于現有的KGE模型，HousE-r和HousE在限制了模型參數的情況下仍然表現出了更加優越的性能，這證明了本研究所設計的Householder架構的有效性。HousE-r相對于的基準模型的性能提升來源于Householder旋轉帶來的強大模組化能力。值得注意的是，HousE-r超越了幾乎所有的基準模型，唯一的例外是在FB15k-237資料集上與Rotate3D的性能表現是相近的，然而HousE-r使用了遠少于Rotate3D的參數（後者的參數量約為HousE-r的3.67倍），這也反映了Householder關系旋轉的有效性。進一步來說，HousE在所有名額上都一緻超越了HousE-r，這得益于HousE中的Householder關系投影所帶來的對複雜關系映射屬性的模組化能力。
細粒度性能分析
表4 WN18RR資料集中各個關系下的性能對比
為了從細粒度角度進一步驗證模型性能，本研究展示了模型在各個關系下的性能表現，如表4所示。可以觀察到，相對于現有的兩種代表性旋轉模型RotatE和QuatE，HousE-r在所有關系下都表現出更好的性能，驗證了Householder旋轉優越的模組化能力。通過結合Householder投影，HousE進一步取得了更好的性能，尤其是在一對多和多對一關系上的性能提升更為顯著，比如在一對多關系member_of_domain_region和多對一關系instance_hypernym上，HousE相對于RotatE分别有62.55%和21.55%的顯著提升，這得益于HousE對複雜映射屬性的有效模組化。
對複雜映射屬性的模組化能力分析
表5 FB15k-237資料集中在不同映射屬性下的性能對比
為了進一步驗證HousE對關系映射屬性的有效模組化，本研究對比了HousE和RotatE在不同關系映射屬性下的性能，如表5所示。可以觀察到，HousE在所有映射屬性下的性能一緻優于RotatE，特别是在複雜的一對多關系（預測尾實體）、多對一關系（預測頭實體）和多對多關系下，HousE相對于RotatE的性能提升更加顯著。HousE的這種優越性能得益于Householder投影對關系映射屬性的有效模組化。
旋轉次元的影響分析
圖5 WN18RR和FB15k-237資料集中旋轉次元對性能的影響
為了驗證高維旋轉的有效性，本研究在WN18RR和FB15k-237資料集上探究旋轉次元對性能的影響，結果如圖5所示。可以觀察到，正如所期望的那樣，在這兩個資料集中，更高維旋轉變換下的HousE和HousE-r相比于其在低維旋轉下時都取得了更優越的性能，因為高維旋轉能夠帶來更為強大的模組化能力。與此同時，在所有旋轉次元下，HousE都一緻且顯著地超越了HousE-r，證明了HousE中Householder關系投影的有效性。例如，在4維旋轉變換下的HousE就已經優于12維旋轉變換下的HousE-r了。 模型變體與潛力
表6 不同模型變體的性能
為了驗證所提出Householder投影的有效性，本研究設計了HousE的兩個變體模型HousH和HousR，分别是将HousE中的Householder投影替換為了TransH和TransR中的不可逆投影。從表6可以觀察到，相比于沒有投影變換的基礎模型HousE-r，HousH和HousR在FB15k-237資料集上的性能僅有略微提升，在WN18RR資料集上的性能甚至會更差一些，這反映了不可逆的投影變換可能會損害模型的模組化能力。進一步來說，HousE在兩個資料集上都顯著地優于HousH和HousR，證明了Householder可逆投影的優越性。
為了進一步探究模型的潛力，本研究也嘗試向HousE和HousE-r中引入了關系平移變換，分别得到HousE+和HousE-r+。從表6中可以看出，這兩種變體在兩個資料集上的性能都要優于它們的原始版本，這是因為平移變換能夠反映KG的層次屬性，因而也可以一定程度地增強HousE和HousE-r的表達能力。