EAE：一種酶知識圖譜自適應嵌入表示方法

杜治娟 張 祎 孟小峰 王秋月

(中國人民大學信息學院 北京 100872)

EAE：一種酶知識圖譜自適應嵌入表示方法

杜治娟 張 祎 孟小峰 王秋月

(中國人民大學信息學院 北京 100872)

(2014000654@ruc.edu.cn)

近年來，構建大規模知識圖譜(knowledge graph, KG)，并用其解決實際問題已經成為大趨勢.KG的嵌入表示方便了機器學習在KG等關系數據上的應用，它可以促進知識分析、推理、融合、補全，甚至決策.最近，開放域知識圖譜(open-domain knowledge graph, OKG)的構建和嵌入表示已經得到蓬勃發展，大大促進了開放域中大數據的智能化.與此同時，特定域知識圖譜(specific-domain knowledge graph, SKG)也成為了特定領域中智能應用的重要資源.但是，SKG還不發達，其嵌入表示尚處于萌芽階段.這主要是由于SKG與OKG的數據分布顯著不同，更具體地說：1)在OKG中，如WordNet,Freebase，頭/尾實體的稀疏度幾乎相等；但是在Enzyme,NCI-PID等SKG中不均勻性更受歡迎，例如微生物領域的酶KG中尾實體是頭實體的1 000倍.2)頭實體和尾實體可以在OKG中交換位置，但是它們在SKG中是非交換的，因為大多數關系是屬性.例如實體“奧巴馬”可以是頭實體也可以是尾實體，但是頭實體“酶”總是處于頭位置.3)關系的廣度在OKG中具有小的偏差，而SKG中很不平衡.例如一個酶實體甚至可以鏈接31 809個“x-gene”實體.基于這些觀察，提出了一個新方法EAE來處理這3個問題，并在鏈接預測和元組分類任務上評估了EAE方法.實驗結果表明：EAE顯著優于Trans(E，H，R，D和TransSparse)，達到了最先進的性能.

特定域知識圖譜；酶；嵌入表示；不均勻；非交換；不平衡

近年來，智能應用受益于實體關系構成的結構化知識[1-2]，比如大規模開放域知識圖譜(open-domain knowledge graphs, OKGs)DBPedia[3],Wikidata[4],Freebase[5],YAGO[6]和Probase[7]等被證明是支持自然語言問答、智能搜索[5,7]以及知識推理、融合和補全[8-10]等的重要資源.構建大規模特定域知識圖譜(specific-domain knowledge graph, SKG)并用于解決實際問題也受到更多關注，例如在生物醫學中，諸如NCI-PID知識庫[11]對于了解復雜疾病如癌癥以及推進精密醫學至關重要，又如Neurocommons[12],Bio2RDF[13],LinkedLifeData[14]等集成了生物醫學信息，并用于生命科學中的決策支持[15-16].雖然這些知識圖譜(knowledge graphs, KG)對于解決實際問題非常重要，但是它們遠不完全，并且在非靜態領域，新事實的產生與日俱增，手動補全KG變得不切實際；此外，隨著KG規模的增加，圖表示的KG在應用中正面臨著數據稀疏和計算效率低下的問題[2,17].更重要的是，用圖表示的KG不便于機器學習[2,17]，而機器學習是大數據自動化和智能化的不可或缺的工具[14].因此，像OKG嵌入一樣，SKG也需要嵌入表示，即將實體和關系表示成連續低維向量.

OKG的嵌入方法已如雨后春筍，如RESCAL[18],TansE[19], HolE[20]等.盡管這些方法在OKG上具有強大的建模能力，但由于實體不均勻、非交互和不平衡的原因，在SKG上仍然具有挑戰性.

我們以中國科學院微生物研究所的酶KG(enzyme KG, EKG)來說明SKG與OKG的差異.完整的EKG包含13種關系、6 482 370個實體(其中包括6 463個頭實體和6 475 907尾實體)、7 017 094個三元組.圖1是EKG的子圖，灰色橢圓代表頭實體，空白橢圓表示尾實體*EKG中的數據表示形式：實體表示格式如〈http://gcm.wdcm.org/data/gcmAnnotation1/enzyme/5.1.1.12〉或者“Acting on amino acids and derivatives”；關系表示格式如〈http://gcm.wdcm.org/ontology/gcmAnnotaion/v1/class 〉.為了簡單起見，我們省略了url前綴“http:// gcm.wdcm.org/ontology/gcmAnnotaion/v1/”和http://gcm.wdcm.org/data/gcmAnnotation1/..

從EKG中我們得到3個觀察結果：

結果1. 大多數實體不連通，并且頭實體都是各種“酶”，如圖1中的“enzyme1.4.1.11”等，而尾實體大部分是屬性值，所以，頭尾實體的位置是不可交換的，頭實體總是處于EKG的頭位置.這與OKG非常不同，在OKG中實體是可以交換的，如“奧巴馬”可以是頭實體，也可以是尾實體.我們把這種現象叫做實體分布的非交換性.

結果2. 圖1中有3個頭實體，卻有25個尾實體，這種現象在EKG中普遍存在，如表1所示，尾實體數是頭實體數的1 000倍.并且頭尾實體的稀疏度*頭/尾實體的稀疏度等于頭/尾實體數除以三元組總數，稀疏度小，說明出現次數少；反之亦然.也顯著不均衡，例如頭數為1 085.73，但尾數為1.08.在OKG中，頭尾實體的稀疏度幾乎相等，比如WN18的頭尾稀疏度之比是1.0，FB15K的頭尾稀疏度之比是0.996 8.我們把這種現象叫做實體分布的不均勻性.

Fig. 1 The subgraph enzyme KG圖1 EKG的子圖

Table 1 Feature Statistics of the Enzyme KG

結果3. 關系的廣度*關系的廣度分為頭廣度和尾廣度，頭廣度定義為(關系，尾實體)對鏈接的頭實體的數量，尾廣度亦然.其中(關系，尾實體)表示關系和尾實體對，即它倆固定，頭實體隨意.在EKG中存在嚴重的不平衡.如表1所示，最大頭廣度為6 436 ，最大尾廣度是40 635，大約6.3倍.據統計，如表1～2所示，不平衡關系在EKG中占有很大的比例，特別是“KeggGene”，“ncbiGene”和“x-gene”關系，如“ncbiGene”實體平均鏈接821.81尾實體，最多可達39 051個，遠遠超過OKG.并且這種不平衡性的變化很大，比如“x-pathway”的頭尾廣度分別是46.08和2.39，遠小于“keggGene”的.我們把現象叫做實體分布的不平衡性，對應的實體稱作重頭或重尾實體.

通過以上分析我們看出了SKG與OKG的數據差異，同時，我們也知道OKG的所有以前的工作，包括TransE,TransH,TransR,TransD和TransSparse都不能很好地解決這3個問題，并且它們以相同的方式對每個關系進行建模.不均勻性可能導致出現次數少的實體和關系(記作不頻繁對象)在訓練過程中出現擬合不足的問題，而出現次數多的實體和關系(記作頻繁對象)會出現過擬合問題.同時，關系廣度的嚴重不平衡(重頭或重尾)表明需要著重區別大量頭實體或者尾實體.

Table 2 Relation Distribution of EKG

為了應對上述挑戰，我們提出了一種新型嵌入表示方法——酶知識圖自適應嵌入(enzyme know-ledge graph adaptive embedding, EAE)方法——來學習EKG的嵌入表示，主要貢獻如下:

1) 針對SKG的不均勻性、非交換性和不平衡性，提出了一種新方法EAE對EKG進行嵌入表示.

2) 為了著重區分重頭或重尾實體，EAE采用了“三角形法則+點積原理”的三元組建模思想，使得h+r和t只需要保持一定的角度，而不是嚴格限制h+r=t*h,r,t依次表示頭實體向量、尾實體向量和關系向量..

3) “三角形法則”和“點積原理”都不會增加模型復雜度.所以，EAE不僅準確性高，還和TransE一樣，具有參數少、時空復雜度低的優勢，可以輕松擴展到大規模SKG.

4) 采用Adadelta動態調整參數，自適應地克服由于不均勻而導致的不頻繁對象的擬合不足問題和頻繁對象的過擬合問題.

5) 在鏈接預測和元組分類任務中，我們的方法取得了最先進的性能.

1 相關工作

OKG的嵌入模型包括翻譯模型、組合模型和神經網絡模型.其中，翻譯模型最簡單，復雜性也較低.為了方便說明，我們首先給出文中使用的數學符號，如表3所示:

Table 3 Mathematical Notations

1.1 翻譯模型

翻譯模型的靈感來自word2vec中詞匯關系的平移不變性.經典模型是TransE[19]，它認為頭實體向量h加上關系向量r可以得到尾實體t，并且h+r越接近于t，相應的元組越有可能是正確的.所以，它的分數函數

(1)

TransE原理很簡單，對于1-to-1關系建模準確性很好.然而，它在處理復雜關系，如1-to-n,n-to-1和n-to-n關系時不占優勢*這種關系分類源于TransE，對于每個關系r，平均鏈接的頭實體h數(或者尾實體t)，若此平均數低于1.5，則參數被標記為1，否則為n..因為，如式(1)所示，當一個關系r鏈接多個實體ek,k=1,2,…,i,…,j,…時會出現多個實體重合的情況，即ei=ej,i≠j.同理，當2個實體間有多重關系時，多個關系也會重合.為此，出現了一些改進方法，如Trans(H,R,D,Sparse)[21-24].

TransH[21]為了使實體面對不同關系有不同的表示，首次使用超平面和映射操作對關系進行建模，然后將頭尾實體映射在超平面上:

(2)

(3)

由式(2)可知，所有關系和實體向量建模在相同語義空間，但是一個實體可能有很多方面，不同關系關注不同的方面.所以相同的語義空間不能表達這樣豐富的信息.為此，Trans(R，D，Sparse)將r和e建模在不同的語義空間中，然后通過映射矩陣Mp將實體e從實體空間投射到關系空間:

ep=Mp×e.

(4)

TransR[22]中h和t共享普通映射矩陣Mp；TransD[23]認為應該區分h和t，并且映射矩陣Mp應該與實體和關系都相關，所以，Mp被實體映射向量和關系映射向量所代替:

(5)

1.2 其他模型

還有組合模型和神經網絡模型.組合模型采用線性組合原理來擬合元組，例如RESCAL[18],LFM[25],DistMult[10]和HolE[20].其分數函數

fr(h,t)=hTMrt.

(6)

RESCAL優化整個Mr，帶來了更多的參數.因此，LFM僅優化非零元素， DistMult使用Mr的對角矩陣代替Mr來減少參數，但這種方法只能建立對稱關系.HolE使用點積代替張量積，并采用h和t之間的循環相關來表示實體對:

fr(h,t)=σ(rT(h*t)),σ(x)=1/(1+e-x),

(7)

(8)

HolE在非交換關系和等價關系上優勢很大，并且可以通過快速傅里葉變換加速計算.

神經網絡模型包括SE[26],SME[27],NTN[28]和SLM[28].SE基于式(9)通過頭實體特定矩陣Mrh和尾實體特定矩陣Mr t來轉換實體空間,但是它不能捕捉實體之間的關系[28].SME[27]處理實體和關系之間的相關性可以通過:

(9)

fr(h,t)=(M1h⊙M2r+b1)T(M3h⊙M4r+b2).

(10)

SLM[28]使用單層神經網絡的非線性運算來增強實體間關系的精確性，并減少SE的參數.但是它只提供實體和關系之間相對較弱的聯系.NTN模型結合SLM[28]和LFM[25]定義了得分函數:

(11)

2 EAE模型

由引言分析可知，EKG嵌入表示的困難在于：1)區分重尾實體；2)克服由于不均勻而引起的不頻繁對象的擬合不足問題和頻繁對象的過擬合問題.然而，翻譯模型對于1-to-1關系工作良好，在復雜(n-to-1，1-to-n和n-to-n)關系中存在問題，組合模型表達能力強,但是復雜度高；神經網絡模型又不適用.為此，我們提出了EAE模型.

2.1 EAE建模

1) 成像.將h和r的線性操作看作t的像timag*也可以將t和r的線性操作看作h的像，關系也一樣.，根據三角形法[29]則有式(12)成立:

timag=h+r,

(12)

2)計算物像相似度.采用l1,l2—norm計算尾巴t與計算得到的像timag之間的相似度：

(13)

此時，我們可以清楚地看到，式(12)原理簡單、參數少，很好地建模了實體和關系.但是式(13)中l1,l2—norm屬于賦范空間中的范數[29]范疇，所以當timag與t特別像時，就會產生timag=t*向量都從原點出發，長度相同，當timag=t時，向量終點必然會重合，即2個向量完全重合.，當有多個尾實體t1,t2,…,ti,…時，就會出現timag=t1=t2=…=ti=….

為了區分眾多t1,t2,…,ti,…，我們想到了比范數更具有表達能力的點積*從數學上看，賦范空間定義了范數(范數有長度和數乘可提取)，內積空間定義了內積(內積空間有角度和長度)，且內積可以誘導范數，但范數不一定能誘導內積，所以范數弱于內積, n維向量的內積也叫作點積.，即用點積[29]度量timag與t的相似度.因此，我們提出了基于“三角形法則+點積(n維向量的點積是線性組合)原理”的EAE模型，如圖2所示.數學符號如表3所示.

Fig. 2 EAE model圖2 EAE模型

圖2中的“三角形法則”用于成像，和翻譯模型一樣，即式(12)所示.“點積原理”用于計算物像相似度，即用式(14)代替式(13):

sim(timag,t)=dot(timag,t).

(14)

采用式(14)時timag和t,或者眾多ti,i=1,2,…之間只需要保持一定的角度，而不是嚴格的timag=t.再從線性代數的角度看[29]，dot(timag,t)是線性組合，timag是給定的權重向量，t是特征向量，所以timag與t之間存在式(15)的關系:

timag=?iti.

(15)

從式(15)也可以看出，采用點積(或者線性組合)后，眾多尾實體相當于被加上了權重，所以可以被區分.當然，像翻譯模型一樣，完整的EAE模型也可以合并式(14)(15)，統一寫作:

fr(h,t)=dot(h+r,t).

(16)

當然，h+r和t都是n維向量，所以式(16)也可以寫作[29]:

fr(h,t)=dot(h+r,t)=(h+r)Tt.

(17)

2.2 模型訓練

(18)

Δ′={(h′,r,t)|h′∈E∪(h,r,t′)|t′∈E},

(19)

其中，γ是邊界，Δ′和Δ分別是正確和不正確的三元組的集合，Δ′是Δ的負采樣集.

接下來需要解決由于不均勻而引起的不頻繁對象的擬合不足問題和頻繁對象的過擬合問題.在傳統模型中，大多數采用隨機梯度下降SGD[30]求解.SGD使用全局學習速率η更新所有參數，而不管數據特性如何.但是根據前面分析，我們可以看到不頻繁出現的實體需要較長的時間來學習，頻繁出現的實體則需要較短的時間來學習.所以，我們采用Adadelta[31]訓練模型，它可以隨著時間的推移動態調整參數，使得小梯度具有較大的學習率，而大梯度具有較小的學習率.具體做法如下[31]：

首先，Adadelta限制了過去梯度的窗口，以固定大小?累積，然后將該積累表示為平方梯度的指數衰減平均值.假設在時間epo上，運行平均值E[g2]epo:

(20)

其中，ρ是衰減常數.由于在更新參數時需要這個數量的平方根，所以，將其近似轉化為歷史累計梯度的平方根RMS:

(21)

其中,ε是常數.所以，參數更新:

(22)

因此，EAE的算法如算法1所示.

算法1. EAE算法.

輸入：訓練集Δ′和Δ、實體和關系集E和R、邊界γ、嵌入維度n,m；

輸出：h,r,t.

/*初始化*/

/*訓練*/

④ loop

⑥Δbatch←sample(Δ,b)； /*采樣一個大小為b的minibatch*/

⑦Tbatch←?； /*初始化一組三元組*/

⑧ for 〈h,r,t〉∈Δbatchdo

⑩Tbatch←Tbatch∪{(h,r,t),(h′,r,t′)}；

/*更新向量*/

/*歸一化*/

/*更新參數*/

t)-fr(h′,t′)]+； /*計算梯度*/

/*累計梯度*/

/*計算更新*/

2.3 復雜度分析

算法的可擴展性不僅在于高精度，而且還具有低的時間和空間復雜性.我們將EAE與其他模型進行比較，如表4所示:

Table 4 Complexities Comparison

ns=1: linear;λ=2: separate;λ=1: share.

在表4中，復雜度通過參數的數量以及每輪更新中乘法運算所需的時間和內存空間來測量.ne,nr,nt r分別代表KG中的實體、關系和三元組的數量;nk是神經網絡的隱層節點的數量，ns是張量的片數;d表示de=dr,de和dr分別表示實體和關系嵌入空間的維度;θ(0?θ?1)表示映射矩陣的平均稀疏度.從表4中我們可以看到，EAE中的參數數量、運算所需要的內存空間與TransE相同，時間復雜度也與TransE相同，遠優于神經網絡模型和組合模型，同時也好于其他翻譯模型，顯示了我們方法的高效率.這種優勢在嵌入空間越大的情況下越明顯.

2.4 與其他翻譯模型的區別

2.1～2.3節給出了模型定義，并分析了模型的復雜度，本節著重分析與其他翻譯模型相比，我們EAE模型為什么會產生好的性能.眾所周知，翻譯模型的本質是利用關系向量將頭實體轉換為尾實體，數學表示為h⊥+r=t⊥，如表5所示，其幾何表示如圖3所示.

Table 5 The Principle of Translation-Based Models

Fig. 3 The geometric representation of models圖3 翻譯模型的幾何表示

從圖3可以看出，翻譯模型存在2個問題：重頭(或重尾)重合和重關系重合，如圖3(a)和圖3(b)所示.第1個問題的原因如下：由表4可知，在Trans(R,Sparse和H)中，Mr,Mr e和rp由關系r唯一確定.這已經通過實踐證明，例如在OKG的FB15K數據集上，大約只有48.9%的元組(為1-to-1和n-to-1元組)的準確度(Hits@10*Hits@10：預測正確的實體排在前k位的比例.)超過85%，而28.3%的元組(1-to-n)的元組不到60%[20].TransD使用實體投影向量并區分頭實體和尾實體.因此，可以在一定程度上解決第1個問題.但是頭(尾)實體僅受實體空間中的頭(尾)實體投影向量的影響.因此，它比TransSparse降低3%[20].

然而，Trans(R,Sparse和H)很大程度上改善了第2個問題，主要是它們利用了一個投影矩陣Mr,Mr e或投影向量rp，而Mr,Mr e和rp與關系一一對應，它們不同，則關系不同.這也有實踐證明：例如在OKG的FB15K數據集上，所有類型關系的準確度至少提高10%[14].這充分說明了區分重關系的重要性.不幸的是，這個問題在EKG中不存.因此，翻譯模型在EKG中沒有優勢.

雖然我們的EAE與翻譯模式有相似之處，但EAE有優勢：1)dot(h+r，t)規定h+r和t只需要保持一定的角度，而不是嚴格限制h+r等于t，進而可以有效區分重頭和重尾實體，解決不平衡問題.2)EAE采用Adadelta更新參數，它可以隨著時間的推移動態調整參數，使得小梯度具有較大的學習率，而大梯度具有較小的學習率.因此，EAE可以自適應地克服由于不均勻而導致的不頻繁對象的擬合不足問題和頻繁對象的過擬合問題.3)EKG中頭尾實體不存在位置交換性，所以沒有必要區分頭尾實體，也就不需要建立像Trans(D和Sparse)那樣復雜的空間變換模型，減少了模型復雜度.4)點積不會增加時間復雜度和空間復雜度.所以，它保持了線性時間和空間復雜度，可以很容易地擴展到大規模SKG.

3 實驗與結果

為證明EAE的有效性，我們選擇TransE,TransH,TransR,TransD和TransSparse作為基準模型，并在鏈接預測、元組分類和自適應性度量任務上進行比較.

3 1 數據集構建

我們構建EAE模型來處理EKG中不均勻性、非交換性和不平衡性問題.因此，我們從中國科學院微生物研究所的酶知識庫EKG中隨機抽取139 963個實體和10種關系得到實驗數據集E13M.

我們從原始數據中刪除了“description”,“history”和“a(type)”3個關系， 因為：1)“description”和“history”關系對應的尾實體是長文本，不方便處理，并且這些信息作為輔助信息幫助預測更為合適；2)EKG中都是酶數據，所以a(type)對應的尾實體相同，不需要預測.此外，眾所周知，訓練數據、驗證數據和測試數據是實驗數據集包含的3個基本要素.并且在KG 嵌入中，測試時需要使用實體和關系的嵌入向量，而這些向量是訓練過程中產生的，所以測試數據中的每個實體和關系必須存在于訓練集中.我們刪除只出現一次的所有實體和關系，然后隨機抽樣，得到的E13M數據集如表6～7所示:

Table 6 E13M Data Set

Table 7 Relation Type and Feature in E13M

3.2 評價指標與實現

為了評估模型的性能，我們采用和TransE相同的評價指標[15]：1)MeanRank，正確實體的平均排序；2)Hits@k，預測正確的實體排在前k位的比例.MeanRank越低或者Hits@k越高，準確性越高.

首先，對于每個測試三元組〈h,r,t〉，和TransE一樣，也用貝努力抽樣(.bern方法)從E13M中選擇實體替換頭實體h(選擇實體和被替換實體不能是同一實體)，并且通過fr(h,t)給出的相似度得分降序排列這些損壞的三元組.同樣，我們重復這個過程，替換尾實體t.

其次，實驗數據包括訓練數據、驗證數據和測試數據.因此，三者中出現一些損壞的三元組時，上述指標中存在一個小錯誤.例如訓練數據中損壞的三元組可能包含在驗證數據和測試數據中.如果是這樣，排名將是誤導的.為了避免這個缺陷，我們刪除所有出現在訓練數據、驗證數據和測試數據中損壞的三元組，記作Filter原始操作記作Raw.所以，我們報告的MeanRank和Hits@k有2種設置：Raw和Filter.

為了公平，所有模型的維數都設置為d=20，迭代次數epoch=1 000，Adadelta的參數1-ρ=10-3,ε=106，SGD學習率λ={0.001,0.01,0.1}，邊界γ={0.1,0.5,0.6,0.7,1,1.5}，最小批量處理大小B={100,200,480,1440}，EAE中不相似度量使用點積，其他的采用一階矩離或二階距離d={1,2}，每個模型都由Adadelta[27]和SGD[26]分別訓練.

3.3 鏈接預測

鏈接預測是測試補全三元組〈h,r,t〉的一個基準任務，即已知〈h,r,t〉中的任意2個，依據fr(h,t)最小原則預測第3個.這個任務關注相對正確性，即預測的三元組的排序，而不是獲得最好的.所以這里有2個指標：MeanRank和Hits@k.當預測缺失的頭尾實體時，我們和之前的工作做法一樣，設置k=10.但是，對于缺失關系預測，數據集共有10個關系，k=10是無意義的.因此，我們將關系預測的k設置為k=3.我們在E13M上對方法進行評估，結果如表8～10所示:

Table 8 Evaluation Results on Entity Prediction

Note： The bold data is the best one among all models for per metric.

Table 9 Evaluation Results on Relation Rrediction

Note： The bold data is the best one among all models for per metric.

從表8可以看出，EAE在預測頭實體和尾實體時，MeanRank值顯著低于基準模型，而在預測頭實體時，Hits@10值也顯著高于基準模型.比如在預測頭實體時，基準模型中最低的MeanRank值是14.7(TransE),而EAE降低到4.38；對于Hits@10指標，基準模型中最高的是TransD的89.2%，我們的EAE提高了8.62%.在預測尾實體時，EAE在MeanRank指標上也可能比其他基準模型好10～58倍.對于關系預測任務，EAE也獲得了較好的結果，在Hits@10指標上比TransD提升了約1%，但比TransE提高了6%，MeanRank值也得到了最小值.這些結果證明EAE模型在處理酶KG方面具有明顯的優勢.但是,從表8尾實體預測中我們觀察到了一個現象，即在Hits@10指標上，各種模型的最高值不超過17%，出現這種現象的主要原因應該是EKG中每個關系所鏈的尾實體太多，尤其是“keggGene”,“x-gene”,“ncbiGene”關系，平均可達966.31,821.81,275.54個(表2)，這意味著對于這3種關系對應的尾實體，排名在前966.31,821.81,275.54的都是正確的，而目前規定排名前10是正確的，其他均按照預測錯誤處理，并且表7表明這3種關系的數據所占比例很大，所以會顯著影響Hits@10命中率.所以采用MeanRank更能評價模型的性能，并且模型具有較低的MeanRank或較高的Hits@k都意味著更好的效果，所以，我們仍然認為EAE有很好的建模能力.

Table 10 Experimental Results on E13M by Mapping Properties of Relations

Note： The bold data is the best one among all models for per metric.

表10是按關系類別分組的鏈接預測結果，像TransE[14]一樣，包括1-to-1,1-to-n,n-to-1和n-to-n.E13M包括1-to-1,1-to-n和n-to-1關系，不存在n-to-n關系.從表10中我們可以看到，當預測頭實體時，EAE可以在所有基準模型中取得最優性能，并且在預測頭實體方面具有更明顯的優勢，例如EAE可以將Hits@10值提高10%～47.11%，甚至在預測1-to-n關系時可以達到99.98%.但是，EAE在預測尾部實體并沒有占太大優勢，如表8中分析，主要是因為1-to-n中的n太大，遠大于10，所以各種模型沒有明顯區別.

3.4 元組分類

元組分類是一種二元分類，其目的是判斷給定的三元組〈h,r,t〉是否正確.因此，我們還使用E13M作為實驗數據集，并按照TransParse的基本思想生成負例.對于驗證數據，我們采用任意實體隨機替換尾實體產生負例.同時，負例不能出現在原始驗證數據集中；否則，用其他實體替換原始尾實體.測試數據也是如此.接下來，基于式(1)計算每個三元組的得分，并由閾值θ區分正例和負例.θ由驗證數據集中正例和負例之間的距離得分最大化決定.最后，如果一個新的三元組〈h,r,t〉得分高于θ，那是正確的；否則，是錯誤的.在這里，我們包括2個指標：第1個是模型在整個數據集上的分類準確性，即所有關系上的分類準確性.例如，總共有nc個三元組，我們正確地判斷出ns個元組的正確性，那么整個數據集上的分類準確性是ns/nc.類似地，通過關系名稱分組三元組可以獲得每個關系上的分類準確性.我們選擇TransE，TransH，TransR，TransD和TransSparse作為基準模型，其結果如圖4和表11所示.

Fig. 4 Triples classification accuracies圖4 元組分類準確性

圖4顯示出EAE在所有基準模型中具有絕對的優勢，得到最佳準確度為99.39%，幾乎接近1，并且顯著高于其他基準模型，最差也不比TransH高7.82%.這表明了EAE模型的正確性.

表11也明確顯示出EAE在簡單和復雜的關系上顯著提高了性能.此外，EAE在10種關系上，分類準確率都高于97.2%，但是其他模型則差很多，比如，TransE的最低準確性為56.3%，TransH為50%，TransR為50%，TransD為76.8%，TransSparse為66.7%.這就是為什么我們使用“三角形法則和點積原理”思想.因此，我們認為EAE模型可以很好地處理重尾和重頭數據，如EKG.

Table 11 Classification Accuracies of Different Relations

Note： The bold data is the best one among all models for per metric.

Fig. 6 MeanRank of entity prediction by SGD and Adadelta圖6 采用SGD和Adadelta訓練的實體預測的MeanRank

3.5 自適應性度量

EKG具有不均勻性，為了不讓這種不均勻性影響模型準確性，使模型更容易訓練，我們用Adadelta代替了SGD.為了驗證Adadelta更適合這種數據, 我們將基準模型TransE,TransH,TransR,TransD,TransSparse和我們的EAE模型分別用SGD和Adadelta訓練.采用實體預測和關系預測作為實驗載體，度量指標仍然用MeanRank和Hits@10，其結果如圖5和圖6所示.

從圖5我們可以看出，在Hits@10指標上，模型用Adadelta訓練最少也能比用SGD提升1.3%.最好的如TransR可以提高8.5%,TransSparse提高了5.8%.這也就應證了面對不均勻數據時，Adadelta的自適應學習要比SGD使用全局學習速率η更新所有參數更有效，因為Adadelta對不頻繁出現的實體給予較長的時間來學習，頻繁出現的實體則給予較短的時間來學習，平滑了不頻繁實體/關系擬合不足、簡頻繁實體/關系過度擬合的問題.

Fig. 5 Hits@10(%) of entity prediction by SGD and Adadelta圖5 采用SGD和Adadelta訓練的實體預測值Hits@10(%)

同樣，圖6的MeanRank值也充分說明了這一點，每個模型在用Adadelta訓練都會比用SGD有一定的改善，比如TransR最明顯，MeanRank值降低了1 291.7(MeanRank值越低越好)，這主要是TransR采用矩陣映射，參數較多，又加上數據的不均勻性較大，使用SGD的全局學習率不利于不頻繁實體和頻繁實體同時學習，而Adadelta可以隨著時間的推移動態調整參數，使得小梯度具有較大的學習率，這樣一來不頻繁實體，如尾實體就有了充分的學習時間，頻繁實體也不會因為訓練時間過長而過擬合.同理，其他模型在采用Adadelta訓練后，MeanRank值也有不同程度的降低.而我們的EAE在采用SGD和Adadelta前后也有45.7的改進.

4 總 結

在本文中，我們基于“三角形法則+點積原理”思想和“自適應學習時間調整”的策略提出了EAE模型來嵌入表示EKG.其優點是:

1)dot(h+r，t)規定h+r和t只需要保持一定的角度，而不是嚴格限制h+r等于t，進而可以有效區分重頭和重尾實體，解決不平衡問題；

2) EAE采用Adadelta更新參數，它可以隨著時間的推移動態調整參數，使得小梯度具有較大的學習率，而大梯度具有較小的學習率.因此，EAE可以自適應地克服由于不均勻而導致的復雜關系擬合不足和簡單關系過度擬合地問題；

3) 點積不會增加時間復雜度和空間復雜度.所以，它可以很容易地擴展到大規模的SKG.

我們只能證明EAE對酶KG的能力很強，但當EAE遇到多個關聯的微生物KG時的能力是未知的.因此，在未來的工作中，我們將考慮多個關聯的微生物知識圖譜的情況.

致謝感謝中國科學院微生物研究所提供微生物數據；感謝為本論文提供修改意見的老師和同學們！

[1]Meng Xiaofeng, Du Zhijuan. Research on the big data fusion: Issues and challenges[J]. Journal of Computer Research and Development, 2016, 53(2): 231-246 (in Chinese)(孟小峰, 杜治娟. 大數據融合研究: 問題與挑戰[J]. 計算機研究與發展, 2016, 53(2): 231-246)

[2] Liu Qiao, Li Yang, Duan Hong, et al. Knowledge graph construction techniques[J]. Journal of Computer Research and Development, 2016, 53(3): 582-600 (in Chinese)(劉嶠, 李楊, 段宏, 等. 知識圖譜構建技術綜述[J]. 計算機研究與發展, 2016, 53(3): 582-600)

[3] Walter S, Unger C, Cimiano P. DBlexipedia: A nucleus for a multilingual lexical Semantic Web[C] //Proc of the 3rd Int Workshop on NLP and DBpedia, Co-located with the 14th Int Semantic Web Conf (ISWC’15). Berlin: Springer, 2015: 87-92

[4] Vrandecic D, Kr?tzsch M. Wikidata: A free collaborative knowledgebase[J]. Communications of the ACM, 2014, 57(10): 78-85

[5] Bollacker K, Evans C, Paritosh P, et al. Freebase: A collaboratively created graph database for structuring human knowledge[C] //Proc of the 2008 ACM SIGMOD Int Conf on Management of Data (SIGMOD’08). New York: ACM, 2008: 1247-1250

[6] Suchanek F M, Kasneci G, Weikum G. Yago: A core of semantic knowledge[C] //Proc of the 16th Int Conf on World Wide Web (WWW’07). New York: ACM, 2007: 697-706

[7] Wu Wentao, Li Hongsong, Wang Haixun, et al. Probase: A probabilistic taxonomy for text understanding[C] //Proc of the 2012 ACM SIGMOD Int Conf on Management of Data(SIGMOD’12). New York: ACM, 2012: 481-492

[8] Dong X, Gabrilovich E, Heitz G, et al. Knowledge vault: A Web-scale approach to probabilistic knowledge fusion[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining(SIGKDD’14). New York: ACM, 2014: 601-610

[9] Neelakantan A, Roth B, McCallum A. Compositional vector space models for knowledge base completion[C] //Proc of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th Int Joint Conf on Natural Language Processing of the Asian Federation of Natural Language Processing (ACL’15). Menlo Park, CA: AAAI, 2015: 156-166

[10] Yang Bishan, Yih W, He Xiaodong, et al. Embedding entities and relations for learning and inference in knowledge bases[EB/OL]. (2014-12-20) [2017-08-01]. https://arxiv.org/abs/1412.6575

[11] Schaefer C F, Anthony K, Krupa S, et al. PID: The pathway interaction database[J]. Nucleic Acids Research, 2008, 37(Suppl_1): D674-D679

[12] Momtchev V, Peychev D, Primov T, et al. Expanding the pathway and interaction knowledge in linked life data[C] //Proc of the 8th Int Semantic Web Challenge (ISWC’09). Berlin: Springer, 2009: 1247-1250

[13] Belleau F, Nolin M A, Tourigny N, et al. Bio2RDF: Towards a mashup to build bioinformatics knowledge systems[J]. Journal of Biomedical Informatics, 2008, 41(5): 706-716

[14] Li Min, Meng Xiangmao. The construction, analysis, and applications of dynamic protein-protein interaction networks[J]. Journal of Computer Research and Development, 2017,54(6): 1281-1299 (in Chinese)(李敏, 孟祥茂. 動態蛋白質網絡的構建、分析及應用研究進展[J]. 計算機研究與發展, 2017, 54(6): 1281-1299)

[15] Nickel M, Murphy K, Tresp V, et al. A review of relational machine learning for knowledge graphs[J]. Proceedings of the IEEE, 2016, 104(1): 11-33

[16] Ruttenberg A, Rees J A, Samwald M, et al. Life sciences on the semantic Web: The neurocommons and beyond[J]. Briefings in Bioinformatics, 2009, 10(2): 193-204

[17] Liu Zhiyuan, Sun Maosong, Lin Yankai, et al. Knowledge representation learning: A review[J]. Journal of Computer Research and Development, 2016, 53(2): 247-261 (in Chinese)(劉知遠, 孫茂松, 林衍凱, 等. 知識表示學習研究進展[J]. 計算機研究與發展, 2016, 53(2): 247-261)

[18] Nickel M, Tresp V, Kriegel H P. A three-way model for collective learning on multi-relational data[C] //Proc of the 28th Int Conf on Machine Learning (ICML’11). Cambridge, MA: MIT Press, 2011: 809-816

[19] Bordes A, Usunier N, Garcia-Duran A, et al. Translating embeddings for modeling multi-relational data[C] // Proc of the 27th Annual Conf on Neural Information Processing Systems (NIPS’13). Cambridge, MA: MIT Press, 2013: 2787-2795

[20] Nickel M, Rosasco L, Poggio T A. Holographic embeddings of knowledge graphs[C] //Proc of the 30th AAAI Conf on Artificial Intelligence (AAAI’16). Menlo Park, CA: AAAI, 2016: 1955-1961

[21] Wang Zhen, Zhang Jianwen, Feng Jianlin, et al. Knowledge graph embedding by translating on hyperplanes[C] //Proc of the 28th AAAI Conf on Artificial Intelligence (AAAI’14). Menlo Park, CA: AAAI, 2014: 1112-1119

[22] Lin Yankai, Liu Zhiyuan, Sun Maosong, et al. Learning entity and relation embeddings for knowledge graph completion[C] //Proc of the 29th AAAI Conf on Artificial Intelligence (AAAI’15). Menlo Park, CA: AAAI, 2015: 2181-2187

[23] Ji Guoliang, He Shizhu, Xu Liheng, et al. Knowledge graph embedding via dynamic mapping matrix[C] //Proc of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th Int Joint Conf on Natural Language Processing of the Asian Federation of Natural Language Processing (ACL’15). Menlo Park, CA: AAAI, 2015: 687-696

[24] Ji Guoliang, Liu Kang, He Shizhu, et al. Knowledge graph completion with adaptive sparse transfer matrix[C] /Proc of the 30th AAAI Conf on Artificial Intelligence (AAAI’16). Menlo Park, CA: AAAI, 2016: 985-991

[25] Jenatton R, Roux N L, Bordes A, et al. A latent factor model for highly multi-relational data[C] // Proc of the 26th Annual Conf on Neural Information Processing Systems (NIPS’12). Cambridge, MA: MIT Press, 2012: 3167-3175

[26] Bordes A, Weston J, Collobert R, et al. Learning structured embeddings of knowledge bases[C] //Proc of the 25th AAAI Conf on Artificial Intelligence (AAAI’11). Menlo Park, CA: AAAI, 2011, 6(1): 301-306

[27] Bordes A, Glorot X, Weston J, et al. A semantic matching energy function for learning with multi-relational data[J]. Machine Learning, 2014, 94(2): 233-259

[28] Socher R, Chen Danqi, Manning C D, et al. Reasoning with neural tensor networks for knowledge base completion[C] // Proc of the 27th Annual Conf on Neural Information Processing Systems (NIPS’13). Cambridge, MA: MIT Press, 2013: 926-934

[29] Banchoff T, Wermer J. Linear Algebra Through Geometry[M]. Berlin: Springer, 1972: 197-254

[30] Duchi J, Hazan E, Singer Y. Adaptive subgradient methods for online learning and stochastic optimization[J]. Journal of Machine Learning Research, 2011, 12(7): 2121-2159

[31] Zeiler M D. ADADELTA: An adaptive learning rate method [EB/OL]. (2012-12-22) [2017-08-01]. http://arxiv.org/abs/1212.5701

EAE:EnzymeKnowledgeGraphAdaptiveEmbedding

Du Zhijuan, Zhang Yi, Meng Xiaofeng, and Wang Qiuyue

(SchoolofInformation,RenminUniversityofChina,Beijing100872)

In recent years a drastic rise in constructing Web-scale knowledge graph (KG) has appeared and the deal with practical problems falls back on KG. Embedding learning of entities and relations has become a popular method to perform machine learning on relational data such as KG. Based on embedding representation, knowledge analysis, inference, fusion, completion and even decision-making could be promoted. Constructing and embedding open-domain knowledge graph (OKG) has mushroomed，which greatly promots the intelligentization of big data in open domain. Meanwhile, specific-domain knowledge graph (SKG) has become an important resource for smart applications in specific domain. However, SKG is developing and its embedding is still in the embryonic stage. This is mainly because there is a germination in SKG due to the difference for data distributions between OKG and SKG. More specifically: 1) In OKG, such as WordNet and Freebase, sparsity of head and tail entities are nearly equal, but in SKG, such as Enzyme KG and NCI-PID, inhomogeneous is more popular. For example, the tail entities are about 1 000 times more than head ones in the enzyme KG of microbiology area. 2) Head and tail entities can be commuted in OKG，but they are noncommuting in SKG because most of relations are attributes. For example, entity “Obama” can be a head entity or a tail entity, but the head entity “enzyme” is always in the head position in the enzyme KG. 3) Breadth of relation has a small skew in OKG while imbalance in SKG. For example, a enzyme entity can link 31 809 x-gene entities in the enzyme KG. Based on observation, we propose a novel approach EAE to deal with the 3 issues. We evaluate our approach on link prediction and triples classification tasks. Experimental results show that our approach outperforms Trans(E, H, R, D and TransSparse) significantly, and achieves state-of the-art performance.

specific-domain knowledge graph (SKG); enzyme; embedding; inhomogeneous; nonco-mmuting; imbalance

2017-09-01；

2017-10-17

國家自然科學基金項目(61379050，61532010，91646203，61532016，61762082)；國家重點研發計劃項目(2016YFB1000603，2016YFB1000602)；2017年度河南省科技開放合作項目(172106000077)；北大方正集團有限公司數字出版技術國家重點實驗室開放課題

This work was supported by the National Natural Science Foundation of China (61379050, 61532010, 91646203, 61532016, 61762082), the National Key Research and Development Program of China (2016YFB1000603, 2016YFB1000602), the Science and Technology Opening up Cooperation Project of Henan Province (172106000077), and the Opening Project of State Key Laboratory of Digital Publishing Technology.

孟小峰(xfmeng@ruc.edu.cn)

TP181

DuZhijuan, born in 1986. PhD at Renmin University of China. Member of CCF. Her main research interests include Web data management and cloud data management.

ZhangYi, born in 1995. Master candidate at Renmin University of China. Member of CCF. Her main research interests include Web data management.

MengXiaofeng, born in 1964. Professor and PhD supervisor at Renmin University of China. Fellow of CCF. His main research interests include cloud data management, Web data management,flash-based data-bases, privacy protection etc.

WangQiuyue, born in 1974. PhD. Assistant professor at Renmin University of China. Her main research interests include data-base and information systems, information retrieval, knowledge base, natural language questions answering, etc.