雷鋒網(wǎng) AI 科技評論按：在KDD 2017上，香港科技大學(xué)計算機系博士生趙歡作為第一作者的論文 Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks 被 research track接收并做口頭報告。經(jīng)雷鋒網(wǎng) AI 科技評論邀請，趙歡為雷鋒網(wǎng)獨家供稿，分享了團隊此項研究的核心思想、算法框架及實驗結(jié)果。

作者介紹

本文主要介紹 KDD 2017 的一篇有關(guān)推薦系統(tǒng)的論文：「Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks」 這篇論文被KDD 2017的research track接收并做口頭報告(錄取率8.6%)。作者包括：

• 第一作者趙歡，香港科技大學(xué)計算機系博士生，研究方向為「異構(gòu)網(wǎng)絡(luò)與推薦系統(tǒng)」；

• 第二作者姚權(quán)銘，香港科技大學(xué)計算機博士生，研究方向為「機器學(xué)習(xí)優(yōu)化算法研究」，2016 Google Fellowship 獲得者；

• 第三作者李健達，香港科技大學(xué)碩士畢業(yè)生，本科畢業(yè)于上海交通大學(xué)。
  

• 第四作者宋陽秋，香港科技大學(xué)助理教授，研究方向為「知識圖譜、文本數(shù)據(jù)挖掘和自然語言處理」；

• 第五作者李迪麟，香港科技大學(xué)正教授，研究方向為「信息檢索，推薦系統(tǒng)，移動數(shù)據(jù)管理」。

核心思想

在這個信息爆炸的時代，推薦系統(tǒng)不僅能幫助用戶更快地獲取感興趣的信息，同時也能創(chuàng)造巨大的商業(yè)價值，目前全球主要的互聯(lián)網(wǎng)公司都會有專門的推薦團隊來從事推薦算法的研究，旨在提升自己的業(yè)務(wù)效果。

傳統(tǒng)的推薦系統(tǒng)中，最常見的方法就是「協(xié)同過濾」，典型的例子就是我們在電商網(wǎng)站見到的「購買該商品的用戶也購買了/也在看」。協(xié)同過濾方法一般包括兩種方式，即基于用戶和基于商品的協(xié)同過濾，以及矩陣分解 (Matrix Factorization)。自從 2007 年 Netflix 百萬大獎的推薦系統(tǒng)比賽以來，矩陣分解的方法開始變得流行。盡管矩陣分解可以獲得不錯的推薦效果，但也有明顯的問題：

• 1）稀疏性(Sparsity)?，F(xiàn)實生活里的評分矩陣往往非常稀疏，因為單個用戶評分的商品是非常少的；

• 2）冷啟動(Cold Start)。新產(chǎn)生的用戶和商品往往都沒有評分。

上述兩種情況都會嚴重影響矩陣分解的預(yù)測準確性。

除了這兩個基本的問題以外，矩陣分解還有一個更嚴重的問題：它很難適應(yīng)現(xiàn)在的推薦系統(tǒng)。因為當(dāng)下的推薦系統(tǒng)需要處理的特征并非只有評分信息，而是各種各樣的信息（稱作 Side Information），比如商品的描述，圖片，用戶的好友關(guān)系等。我們可以看圖 1 的例子，這是 Yelp 上一個餐館的詳情頁。

圖 1：Yelp 上的一個詳情頁，Royal House

從圖中，我們可以看到，除了評分信息之外，還有餐館的地理位置，用戶上傳的圖片，評論等信息。顯然，在給用戶推薦餐館的過程中，這些信息都非常重要，但它們又很難融入到現(xiàn)有的矩陣分解的模型中。因此，我們需要一個全新的框架來解決這樣的問題。這是我們此次 KDD 工作的核心思想：「我們用 HIN 來對 side information 進行建模，同時設(shè)計了一套有效的算法框架，從而獲得更好的推薦效果」。

算法框架

預(yù)備知識

異構(gòu)信息網(wǎng)絡(luò) (Hetegeneous Information Network 以下簡稱 HIN），是由 UIUC 的 Han Jiawei 和 UCLA 的 Sun Yizhou 在 2011 年的 VLDB 論文中首次提出 [1]。

簡單地理解，HIN 就是一個有向圖，圖中的節(jié)點和邊都可以有不同的類型，如下圖，是一個從上面 Yelp 詳情頁抽取出來的 HIN。節(jié)點可以代表不同類型的實體，比如 user, review, restaurant 等, 邊代表不同類型的關(guān)系，比如 Check-in, Write, Mention 等。

利用 HIN，我們就可以將各種各樣的 side information 統(tǒng)一起來，接下來我們將介紹如何在 HIN 這個框架下完成我們的推薦過程。

從meta-path到meta-graph

在Sun Yizhou的VLDB2011的論文中，除了提出HIN，同時也提出了meta-path，用來計算兩個節(jié)點之間的相似度。meta-path就是一個節(jié)點的sequence，節(jié)點與節(jié)點之間由不同類型的邊連接，也就是不同的關(guān)系。

比如從上圖中的HIN，我們可以設(shè)計meta-path：

它表示的意義就是兩個用戶在同一個餐館簽到。

我們可以提取一條meta-path的實例：

那我們可以衡量和 Bar Louie 之間的相似度，當(dāng)有越多的meta-path實例來連接和 Bar Louie，它們之間的相似度就越大，我們也會可以給推薦 Bar Louie。我們可以發(fā)現(xiàn)，這條 meta-path 正好對應(yīng)我們熟悉的「基于用戶的協(xié)同過濾」，即經(jīng)常去 Royal House 的人也會去 Bar Louie。

從這個例子我們可以看出，對于推薦系統(tǒng)來說，HIN和meta-path有兩個好處：

• 1) 非常完美地將各種side information融入到一個統(tǒng)一的模型；

• 2）利用meta-path，可以設(shè)計出各種各樣的推薦策略，除了推薦準確性提升之外，還能提供「可解釋性」。

當(dāng)然，在計算節(jié)點相似度這個任務(wù)上，meta-path也有自己的問題：「無法處理復(fù)雜的關(guān)系」。比如兩個用戶之間有如下連接性。

對應(yīng)到圖上的實例， 和 分別給 Royal House 寫了一個評論，不僅給了五星好評，還在評論里同時提到了這里的「Seafood」，可以說這兩個用戶對餐館的偏好非常相似。但是這樣一種相似性，meta-path 無法對其進行建模。為了解決這個問題，有兩篇論文 ( KDD 16 [2] 和 ICDE 16 [3]) 提出了一種更為通用通用的結(jié)構(gòu): meta-graph（也叫 meta-Structure）。相比 meta-path 要求必須是 sequence 的結(jié)構(gòu)，meta-graph 只要求「一個起點和一個終點，中間結(jié)構(gòu)并不限制」，這樣大大提升了靈活性。因此，在我們的 KDD 論文中，我們采用了 meta-graph 這樣一種結(jié)構(gòu)，來計算用戶和商品之間的相似度。在實踐中，我們可以設(shè)計 條 meta-graph，從而得到多種商品和用戶之間的相似度，也就是  個相似度矩陣。

推薦過程: 矩陣分解(MF) + 分解因子機(Factorization Machine)

通過HIN和mega-graph，我們完美地將各種各樣的side information統(tǒng)一到一個框架中。接下來的問題就是「如何設(shè)計更好的推薦算法」。在這個論文里，我們用到了「MF + FM」的框架，簡單來說: 分別對個相似度矩陣進行矩陣分解，得到組用戶和商品的隱式特征，然后將所有的特征拼起來，使用分解因子機進行訓(xùn)練和評分預(yù)測。

對于一個樣本，即用戶-商品對，我們分別可以得到組特征，每組的維度為（在矩陣分解的時候，我們設(shè)定秩為）。那么我們就可以拼出下圖中所以的一個維度為的特征向量。

Factorization Machine (FM) [4] 是 2010 年在 ICDM 上提出一種模型，由于可以對特征之間的高階關(guān)系進行建模，以及對二階參數(shù)進行低秩分解，因而在評分預(yù)測這個推薦任務(wù)上取得了非常好的效果。在實踐中，我們一般使用二階關(guān)系：

其中，是一階參數(shù)，是二階參數(shù)。為了學(xué)出 和，我們使用了 Least Squared loss：

特征選擇: Group Lasso

一般在 FM 的訓(xùn)練過程中，往往也會加上和的正則項來防止過擬合，用的最多的就是  。但是，在我們的工作中，由于我們會設(shè)計多條 meta-graph，并不是每條 meta-graph 都有用，為了自動選擇出有用的 meta-graph，我們放棄了，而選擇，也稱作 group lasso。在我們的算法框架中，我們是以 meta-graph 為單位來構(gòu)造用戶和商品的隱式特征的，因此，每條 meta-graph 對應(yīng)一組用戶和商品的隱式特征。一旦某條 meta-graph 沒有用，那么它對應(yīng)的一組特征都應(yīng)該被去掉，這就是我們采用 group lasso 來做正則項的動機。

使用 group lasso 正則項之后，目標函數(shù)優(yōu)化就變成了一個非凸非光滑（non-convex, non-smooth）的問題，我們使用了鄰近梯度算法（proximal gradient）算法來求解它。

以上就是我們的算法框架，接下來，我們將通過部分實驗結(jié)果，來證明我們算法的優(yōu)勢。

實驗結(jié)果

數(shù)據(jù)集和評估標準

我們使用了 Yelp 和 Amazon 這兩個數(shù)據(jù)集，這兩個都是非常經(jīng)典的推薦系統(tǒng)數(shù)據(jù)集，同時也包含了豐富的 side information。數(shù)據(jù)的具體統(tǒng)計數(shù)據(jù)，可以參看我們的論文，這里只展示我們用到的 meta-graph，如下圖。在 Yelp 上，我們設(shè)計了 9 條 meta-graph，在 amazon 上，我們設(shè)計了 6 種 meta-graph。

在推薦系統(tǒng)中，我們一般用來評估評分預(yù)測的好壞，越小意味著推薦效果越好。

其中，是實際評分，是預(yù)測評分，是 test set 的個數(shù)。

推薦效果

在實驗中，我們和一些常見的方法相比，包括基于矩陣分解和基于HIN的方法。具體結(jié)果如下圖：

上圖中，RegSVD 和 FMR 是基于矩陣分解的方法，HeteRec [5] 和 SemRec [6] 分別是 WSDM14 和 CIKM15 上的兩篇論文，在 HIN 上用 meta-path 來進行推薦，F(xiàn)MG 是我們的算法。另外，CIKM-Yelp 和 CIKM-Douban 兩個數(shù)據(jù)集是 CIKM15 的作者 Shi Chuan 提供給我們的。根據(jù)上圖，我們有以下發(fā)現(xiàn)：

在所有的數(shù)據(jù)集上，F(xiàn)MG 打敗了所有的方法，推薦效果取得了不同程度的提升，證明了我們算法的有效性。

在 CIKM-Yelp 和 CIKM-Douban 這兩個數(shù)據(jù)集，我們使用和 CIKM15 一樣的 meta-path，依然取得了 4.2% 和 3.2% 的提升，進一步證明在 HIN 這個框架下，我們推薦算法的有效性。

在兩種基于 HIN 的方法中，我們發(fā)現(xiàn) SemRec 比 HeteRec 的效果好不少。除去推薦算法的差異，一個重要的不同就是，在 SemRec 中，作者設(shè)計了 U→?←U→B 這樣形式的 meta-path，而在 HeteRec，作者使用了 U→B←?→B 這樣形式的 meta-path。在我們的算法中，最終選擇出來有效的 meta-graph，大多就是 U→?←U→B 這樣的形式。這個發(fā)現(xiàn)非常有意思，說明通過「用戶協(xié)同」的推薦結(jié)果效果會更好一些。這個發(fā)現(xiàn)也和現(xiàn)實生活中對應(yīng)，我們獲取感興趣的商品或者餐館，除了興趣本身之外，更多的時候是通過朋友圈里好友推薦而發(fā)現(xiàn)。它反過來也能解釋 SemRec 好于 HeteRec。

除了推薦效果的比較，我們還做了其他很多實驗，有興趣的讀者可以去閱讀我們的論文，在這里就不做贅述了。

總結(jié)

最后，給我們的論文做一個簡單的總結(jié)。近些年，由于移動互聯(lián)網(wǎng)和大數(shù)據(jù)的發(fā)展，現(xiàn)在的推薦系統(tǒng)面臨豐富side information場景，傳統(tǒng)的基于矩陣分解的方法已經(jīng)很難再發(fā)揮作用，而基于人工設(shè)計的特征工程又極其費勁。通過HIN和meta-graph，我們提供了一種簡單有效的框架，既能夠非常靈活地利用side information來提升推薦效果，同時，還能利用人工設(shè)計的meta-graph來保留必要的語義信息，從而對推薦結(jié)果提供一定的「可解釋性」。通過實驗，我們也證明了這個框架的有效性。

這個論文的代碼和數(shù)據(jù)也已經(jīng)公布到Github上： https://github.com/HKUST-KnowComp/FMG 。

參考文獻

1. Sun Yizhou et.al., PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. VLDB 2011

2. Huang Zhipeng et.al., Meta Structure: Computing Relevance in Large Heterogeneous Information Networks. KDD 2016

3. Fang Yuan et.al., Semantic Proximity Search on Graphs with Metagraph-based Learning. ICDE 2016

4. Rendle et.al., Factorization Machines. ICDM 2010

5. Yu Xiao et.al., Personalized Entity Recommendation: A Heterogeneous Information Network Approach. WSDM 2014

6. Shi Chuan et.al., Semantic Path based Personalized Recommendation on Weighted Heterogeneous Information Networks. CIKM 2015

雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。