RelSUE:知識圖譜相關實體搜尋 （WSDM’19 錄用論文介紹）
本部落格旨在框架性地介紹我們近期被WSDM錄用的工作，不影響達意的細節將不予贅述（具體細節如果有興趣的話歡迎移步原文）。
相關搜尋（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的元路徑包括\(i)Director\stackrel{directed}\longrightarrow Comedy \stackrel{acted\_in}\longleftarrow Actor\),\(ii)Director\stackrel{directed}\longrightarrow Film \stackrel{acted\_in}\longleftarrow Actor\), \(iii)Actor\stackrel{directed}\longrightarrow Film \stackrel{acted\_in}\longleftarrow Singer\)等。
不同的元路徑組合可以體現不同的偏好，例如如果我們只以一條元路徑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）中估計的路徑長度加上一個衰減因子\(\beta \in [0, 1]\)，即在原有打分的基礎上再乘上\(\beta^L\)，其中L為估計的元路徑長度。
此外，對於RelSUE即RelSUE-e，本文的搜尋都做了一些針對避免選出冗餘元路徑的優化（如果兩條元路徑對應的具體路徑相同，則視為冗餘）。
有了這些路徑以後，那麼就可以進行到background中所介紹的演算法的第二步了。兩種不同版本的RelSUE都通過線性SVM學習各個元路徑的權重（每個元路徑都對應一個特徵），至於為什麼用SVM，沒什麼特別的理由，也不是本文的貢獻所在。
Benchmark
為了進行對比實驗，本文在兩個資料集上（DBpedia, YAGO）分別人工標註了4組查詢（基於對應語義的元路徑數量、長度等緯度區分）。
Evaluation
實驗結果表明RelSUE在兩個不同資料集上都顯著好於現有的方法。
（不知道出了什麼問題，圖片傳不上來了，一直報http錯誤… 後面正常了再貼圖吧）
RelSUE的原始碼及用到的查詢可以訪問 http://ws.nju.edu.cn/relevance/relsue/.