Random Walk for Recommendation

二分圖表示法(Bipartite Graph)

以下內容擷取自推薦系統實踐，加上筆者自己些微註解

record $(u, i)$表示使用者$u$對物品$i$產生過行為，這樣的資料可以用一個二分圖表示

$G(V, E)$ : 使用者-物品二分圖

$V = V_{U} \bigcup V_{I}$ - 使用者頂點集合$V_{U}$和物品頂點$V_{I}$組成

$e_{v_{u}, v_{i}} = 1$ - 有產生互動行為

普遍來說，在這種表示法的情況下，需要去量測兩個頂點之間的相關性，但大致上跑不出以下這幾種思路

頂點之間路徑數
頂點之間的路徑長度
頂點之間經過的頂點數目

而相關性高的一對頂點一般都具有以下特徵

兩個頂點之間有很多路徑相連
連接兩個頂點之間的路徑長度都比較短
連接兩個頂點之間的路徑不會經過out-degree較大的頂點

舉例

A-c vs A-e

有幾條路連通?
- A-c : 2條 (A-a-B-c, A-d-D-c)
- A-e : 1條 (A-b-C-e)
- 對A來說，c比e關係更強
聯通的路徑長度是多少?
- A-c : 長度為3(A-a-B-c, A-d-D-c)
- A-e : 長度為3(A-b-C-e)
聯通路徑的經過頂點out-degree? - 這個做法可以抑制商品以及什麼都喜歡的User
- A-c : (A(3) - a(2) - B(2) - c(2)
- A-c : (A(3) - d(2) - D(2) - c(2)
- A-e : (A(3) - b(2) - C(2) - e(1)

基於以上的思考邏輯，研究人員設計了很多種計算圖中頂點相關性的方法，以下是一個基於隨機遊走(Random walk based)的算法PersonalRank

PersonalRank

假設要給使用者$u$進行個人化推薦，可以從使用者$u$對應的節點$v_{u}$開始進行隨機行走，由走到任何一個節點時，必須按照機率$\alpha$決定繼續走或是停止該次行走，並從$v_{u}$從新開始行走，如果決定繼續行走，那就隨機選擇一個有連接的邊，進入到下一個頂點，如此經過很多次隨機行走之後，每個物品節點被訪問到的機率就會收斂到一個數值，最終物品節點的訪問機率就是推薦排序

Psudo code

personalrank(user_i : Union[int, str]) -> item_distribution : List[int]

Start with user $u$ at vertex $v_{u}$
rec_item = {}
if random.random() > alpha:

random pick an edge and go to next vertex

rec_item[item_idx] += 1
else:

restart at $v_{u}$
repeat 2 and 3, K times
return rec_item

以數學式來表達的話，則會長以下這樣

$PR(v) = \begin{cases} \alpha \sum_{v' \in ~ in ~(v)} \frac{PR(v')}{|out(v')|} ~~ (v \neq v_{u}) \ (1-\alpha) + \alpha \sum_{v' \in ~ in ~ (v)} \frac{PR(v')}{|out(v')|} ~~ (v = v_{u})\ \end{cases}$.

$PR(v)$ - 頂點$v$的訪問機率

$|out(v)|$ - 頂點$v$的out degree

方程式解析

若訪問點為使用者$A$，根據圖2

每一個itertaion

對於非$v_{A}$節點 $$ PR(v_{a}) = \alpha(\frac{PR(v_A)}{|out(v_A)|} + \frac{PR(v_B)}{|out(v_B)|}) $$ $PR(v_a)=1$, the other $PR(v')=0$

僅$v_A, v_B$會進入到節點a，$V_A, V_B$的out degree，來取得分配到的機率，$V_A, V_B$個別有$\frac{1}{3}, \frac{1}{2}$的機率走到$v_a$

對於$v_{A}$節點 $$ PR(v_{A}) = 1 - \alpha + \alpha(\frac{PR(v_a)}{|out(v_a)|} + \frac{PR(v_b)}{|out(v_b)|} + \frac{PR(v_d)}{|out(v_d)|}) $$

有$1- \alpha$的機會重新在$V_A$節點，也有可能從，abd節點走來

以上行為重複$k$個iteration，直到收斂，即可收回item probability list

�課本中有實作程式碼，將每一次iteration取得各個item的機率分佈以堆疊長條圖紀錄，以圖2的例子來說：

在Movielens上的結果則是

優缺點

Pros:

好的理論解釋
容易實踐

Cons:

每次都要在整個圖上迭代，直到機率分佈收斂，時間複雜度高

解決方案

減少迭代次數 - 容易控制準確度和推論時間，且容易實驗準確度影響
從矩陣的角度出發重新設計算法，圖能夠用矩陣表示

Personal Rank(Matrix Form)

各個節點之間若基於隨機行走的假設，會以out degree的反比進行轉移，可以令$M$為使用者物品二分圖的轉移機率矩陣

$$ M(v, v') = \frac{1}{out(v)} $$

$where~~ v \in in(v')$

$$ v = {v_A, v_B, v_C, v_D, v_a, v_b, v_c, v_d, v_e} $$ 矩陣$M$不是一個對稱矩陣，比如圖2的轉移矩陣$M$應為 $$ M_{v \times v} = \begin{pmatrix} 0& 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} & 0 \ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0

\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \ \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0

\end{pmatrix}\quad $$

針對以上矩陣有幾點特性說明如下

轉移矩陣$M$通常不是對稱矩陣，但仍然可能存在特例
轉移矩陣$M$滿足了每一列和為1的性質(每個頂點的out機率和為1)，而行沒有這個特性
轉移矩陣可以搭配Marcov chain相關理論進行推演
實際場景下，使用者互動的物品很少，轉移矩陣高度稀疏
與矩陣分解的關聯性，MF/SVD會直接對User-Item互動矩陣做分解，取出某個User row做推薦，此轉移矩陣的形式和MF/SVD的Input非常像，能夠交互使用，也有一些論文做了這些嘗試