本文轉載自公眾號：南大Websoft。

---

相關搜索（Relevance Search）是信息檢索中的一個經典問題，相關搜索是指給定一個查詢實體，返回與其相關度最高的實體（一個類似的問題Similarity Search，一般來說指相關搜索的一個特例，即只返回與查詢實體同類型的相關實體）。相關搜索面臨的一個主要問題是搜索中的歧義性，即不同的用戶對于“相關性”有著不同的理解和偏好。當前的一些方法已經能夠通過要求用戶提供例子的方式在一些schema較為簡單的圖譜（如DBLP, linkedMDB等）上完成對相關搜索的消歧，然而當處理一些更復雜的圖譜時（如DBpedia, YAGO等），因為效率問題，這些方法很難被直接應用。本文提出了一種基于啟發式搜索的算法RelSUE，能夠有效地在schema-rich的知識圖譜上進行搜索，實驗表明RelSUE在我們構建的benchmark數據集上能夠比其他state-of-art的方法取得更好的效果。

Background

知識圖譜是由實體和邊（實體間的二元關系）構成的高度結構化的數據，這樣的數據中蘊含了大量可以被機器所“理解”的語義信息。兩個實體間相關性的語義信息通常可以通過不同元路徑（meta path，即頂點均為type，邊為property的路徑）的加權組合來刻畫，不同的組合即體現了不同的語義。例如下圖中，

?

連接實體Frank Oz以及Kevin Kline的元路徑包括

不同的元路徑組合可以體現不同的偏好，例如如果我們只以一條元路徑iii）作為相關性的語義，那么上圖中以Frank Oz作為查詢實體，符合這種相關性的目標實體只有Kevin Kline一個。可以預見，不同的用戶對于相關性都會有一定不同的理解（或者某一特定場景下的偏好），所以我們需要一種有效的方式來捕捉到不同用戶（或搜索用例）的主觀偏好，目前一種主流的框架是要求用戶除了輸入查詢實體以外再提供幾個預期結果的例子，然后系統根據這些例子自動地生成一種能夠準確刻畫例子與查詢實體間相關性的加權的元路徑組合。加權元路徑組合通常有兩步組成，第一步首先定位出一些promising的元路徑，第二步基于某些統計或學習的方法自動地為這些路徑賦予權重。RelSUE同樣沿用了這一技術路線。

Approach

在過去的方法中，第一步元路徑的定位可以簡單地通過窮舉或者用戶指定等方式完成，然而，這些方法往往只能應用于一些僅包含幾種不同type以及幾種不同property的schema-simple圖譜中，對于DBpedia（645 property，453 type）或者YAGO（37 property, 536,648 type）這種包含大量type即property的圖譜則不再適用——人工挑選元路徑或者窮舉連接實體間的所有元路徑都是不現實的（一方面本身元路徑的數量是個問題，另一方面進一步對所有選出來的元路徑分配權重也是一個問題）。所以我們需要一種更有效地方式來對元路徑進行選擇，RelSUE正是為了解決如何在schema-rich的圖譜中準確并快速地識別出能夠刻畫查詢實體與例子實體間相關性的元路徑。

本文共提出了兩種不同的算法，RelSUE及RelSUE-e。

RelSUE-e首先基于雙向BFS窮舉所有的連接查詢實體與例子的元路徑（給定直徑內），然后根據我們設計的significance函數為每一個元路徑進行打分排序，選出打分最高的K條元路徑作為目標元路徑集合。可以發現RelSUE-e仍然需要先窮舉所有元路徑再進行選擇，雖然選擇最優的K條元路徑可以保證后續的權重分配能夠有效進行，但是窮舉所有路徑的代價仍然非常巨大，且設定最大路徑長度的方式也十分不靈活具有很大的局限性（例如對于YAGO，只能夠做到窮舉所有兩步的元路徑，3步的速度就已經無法接受，意味著所有3步即以上的相關性語義都會被忽視）。

為了應對以上這些缺陷，本文進一步提出了基于啟發式搜索的方法RelSUE。在RelSUE的啟發式搜索框架中，搜索從查詢實體展開，一步步擴展至所有例子實體都被某K條元路徑連接。搜索空間樹結構擴展的優先級基于兩點考慮，1）當前結點所處的潛在的元路徑的長度（可以通過當前結點與查詢實體的距離，以及當前結點與例子實體間的距離來估算，因為搜索是從查詢實體出發，所以當前結點與查詢實體的距離是已知的，而與例子實體的距離，我們通過distance oracle來計算），2）當前結點的度數（度數越大的點往往意味著包含的信息較少，通過度數來作為衡量信息量的指標也是一種常見的做法）；此外，為了避免啟發式搜索找到一些過長的路徑，我們再對1）中估計的路徑長度加上一個衰減因子β∈[0,1]，即在原有打分的基礎上再乘上β^L，其中L為估計的元路徑長度。βL，其中L為估計的元路徑長度此外，對于RelSUE即RelSUE-e，本文的搜索都做了一些針對避免選出冗余元路徑的優化（如果兩條元路徑對應的具體路徑相同，則視為冗余）。

有了這些路徑以后，那么就可以進行到background中所介紹的算法的第二步了。兩種不同版本的RelSUE都通過線性SVM學習各個元路徑的權重（每個元路徑都對應一個特征），至于為什么用SVM，沒什么特別的理由，也不是本文的貢獻所在。

Benchmark

為了進行對比實驗，本文在兩個數據集上（DBpedia, YAGO）分別人工標注了4組查詢（基于對應語義的元路徑數量、長度等緯度區分）。

Evaluation

實驗結果表明RelSUE在兩個不同數據集上都顯著好于現有的方法。

RelSUE的源碼及用到的查詢可以訪問 http://ws.nju.edu.cn/relevance/relsue/.

---

OpenKG.CN

中文開放知識圖譜（簡稱OpenKG.CN）旨在促進中文知識圖譜數據的開放與互聯，促進知識圖譜和語義技術的普及和廣泛應用。

點擊閱讀原文，進入 OpenKG 博客。

總結

以上是生活随笔為你收集整理的论文浅尝 | 知识图谱相关实体搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。