People You May Know（PYMK）是一份根據共同特徵（如共同好友、學校或工作場所）推薦可能認識的人的清單。許多社群網路（如 Facebook、LinkedIn、Twitter）都使用機器學習來驅動 PYMK 功能。

本章將設計一個類似 LinkedIn 的 PYMK 功能。系統接收一位使用者作為輸入，輸出一份按相關性排序的潛在連結推薦清單。

釐清需求#

以下是候選人與面試官之間的典型對話：

候選人： 我是否可以假設建立 PYMK 功能的目的是幫助使用者發現潛在連結並擴展人脈？

面試官： 是的，這是合理的假設。

候選人： 推薦潛在連結需要考慮大量因素，例如地理位置、教育背景、工作經歷、現有連結、過往活動等。我是否應聚焦於最重要的因素，如教育背景、工作經歷和使用者的社交脈絡？

面試官： 聽起來不錯。

候選人： 在 LinkedIn 上，兩人互為好友的條件是雙方都接受了連結請求，對嗎？

面試官： 是的，友誼關係是對稱的。當某人發送連結請求後，對方需要接受才能建立連結。

候選人： 平台的總使用者數是多少？其中有多少日活躍使用者？

面試官： 約 10 億使用者，3 億日活躍使用者。

候選人： 平均每位使用者有多少連結？

面試官： 平均 1,000 個連結。

候選人： 大多數使用者的社交圖譜不會在短期內大幅變動。我可以在設計 PYMK 時做出這個假設嗎？

面試官： 非常好的觀察，這是合理的假設。

問題摘要： 設計一個類似 LinkedIn 的 PYMK 系統，輸入為一位使用者，輸出為按相關性排序的潛在連結清單。目標是幫助使用者更容易發現新連結並擴展人脈。平台共有 10 億使用者，每人平均有 1,000 個連結。

將問題框架化為 ML 任務#

定義 ML 目標#

PYMK 系統常見的 ML 目標是最大化使用者之間形成的連結數量，幫助使用者快速擴展人脈。

指定系統的輸入與輸出#

• 輸入： 一位使用者
• 輸出： 按相關性排序的潛在連結清單

選擇合適的 ML 類別#

以下是建構 PYMK 的兩種常見方法：Pointwise Learning to Rank（LTR） 與 Edge Prediction。

Pointwise LTR#

將 PYMK 框架化為排序問題，使用 pointwise LTR 對使用者進行排序。如圖 11.3 所示，採用二元分類模型，輸入兩位使用者，輸出該配對形成連結的機率。

然而，此方法有一個主要缺陷：由於模型的輸入只有兩位獨立使用者，無法考慮社交脈絡資訊。雖然這簡化了問題，但忽略使用者連結資訊可能導致預測準確度下降。

以下範例說明社交脈絡為何重要。假設我們要預測 $\langle$ user A, user B $\rangle$ 是否為潛在連結：

觀察他們的 one-hop 鄰居（User A 或 User B 的直接連結），可以獲得更多資訊。如圖 11.5 所示，考慮兩種情境：

• 情境 1： User A 和 User B 各有四個共同連結，且 C、D、E、F 之間存在互相連結
• 情境 2： User A 和 User B 各有兩個朋友，且兩人的連結之間沒有交集

透過觀察 one-hop 鄰居，可以判斷情境 1 中 $\langle$ user $A$, user $B\rangle$ 形成連結的可能性高於情境 2。實務上，還可以利用 two-hop 或 three-hop 鄰居來擷取更多社交脈絡資訊。

在討論第二種方法之前，先了解圖（graph）如何儲存結構化資料（如社交脈絡），以及可以在圖上執行哪些機器學習任務。

圖（Graph） 表示一組實體（節點）之間的關係（邊）。整個社交脈絡可以用圖來表示：每個節點代表一位使用者，兩個節點之間的邊代表已建立的連結。圖 11.6 是一個包含四個節點和三條邊的簡單圖。

圖上可執行的三種預測任務：

• Graph-level prediction（圖層級預測）： 例如，將化合物表示為圖，預測該化合物是否為酵素
• Node-level prediction（節點層級預測）： 例如，在社交網路圖中預測某位使用者（節點）是否為垃圾帳號
• Edge-level prediction（邊層級預測）： 預測兩個節點之間是否存在邊。例如，在社交網路圖中預測兩位使用者是否可能連結

Edge Prediction#

在此方法中，模型以圖資訊作為補充輸入，利用從社交圖譜中提取的額外知識來預測兩個節點之間是否存在邊。

更正式地說，模型接收整個社交圖譜作為輸入，預測兩個特定節點之間存在邊的機率。為了對 User A 的潛在連結進行排序，計算 User A 與其他使用者之間的邊機率，並以此作為排序依據。

資料準備#

資料工程#

本節討論可用的原始資料：

• Users（使用者）
• Connections（連結）
• Interactions（互動）

Users#

除了使用者的人口統計資料外，還有教育背景、工作經歷、技能等資訊。表 11.1 為使用者教育背景資料的範例：

表 11.1：使用者教育背景資料

此類原始資料的一個挑戰在於，同一屬性可能有不同的表示形式。例如「computer science」和「CS」意義相同但文字不同。因此在資料工程步驟中標準化原始資料非常重要。常見的標準化方法包括：

• 強制使用者從預定義清單中選擇屬性
• 使用啟發式方法將同一屬性的不同表示形式分組
• 使用 ML 方法，如 clustering 或語言模型，對相似屬性進行分組

Connections#

表 11.2 為連結資料的簡化範例，每一列代表兩位使用者之間的一個連結及其建立時間：

表 11.2：連結資料

Interactions#

互動類型包括：發送連結請求、接受請求、追蹤其他使用者、搜尋實體、檢視個人檔案、對貼文按讚或回應等。實務上互動資料可能儲存在不同資料庫中，此處為簡化起見合併於單一表格。

表 11.3：互動資料

特徵工程#

為了確定某使用者（如 User A）的潛在連結，模型需要利用 User A 的資訊（如年齡、性別等），以及 User A 與其他使用者之間的親和度（affinity）。以下討論最重要的特徵。

使用者特徵#

人口統計特徵：年齡、性別、城市、國家等

• 人口統計資料有助於判斷兩位使用者是否可能建立連結
• 使用者傾向與具有相似人口統計特徵的人連結
• 人口統計資料中常有缺失值，處理方式請參閱「Introduction and Overview」章節

連結數、追蹤者數、追蹤中數量及待處理請求數

• 使用者更傾向與擁有大量追蹤者或連結的人建立連結

帳號年齡

• 近期建立的帳號可信度較低。例如，昨天建立的帳號更可能是垃圾帳號，不宜推薦給其他使用者

收到的互動次數

• 代表在特定期間內（如一週）收到的按讚、分享、留言等互動總數
• 使用者傾向與平台上更活躍、收到更多互動的使用者連結

使用者間親和度特徵#

兩位使用者之間的親和度是預測他們是否會連結的良好信號。以下是捕捉使用者間親和度的重要特徵。

教育與工作親和度

• 共同學校數： 使用者傾向與就讀相同學校的人連結
• 同校同期： 在校時間重疊會提高連結的可能性。例如，使用者可能想與同時就讀學校 X 的人連結
• 相同主修： 布林特徵，表示兩位使用者是否有相同主修
• 共同公司數： 使用者可能與曾在同一家公司工作的人連結
• 相同產業： 布林特徵，表示兩位使用者是否在同一產業工作

社交親和度

• 個人檔案瀏覽次數： 一位使用者查看另一位使用者個人檔案的次數
• 共同連結數（mutual connections）： 若兩位使用者有許多共同連結，他們更可能建立連結。此特徵是最重要的預測特徵之一
• 時間衰減的共同連結（time discounted mutual connections）： 此特徵根據共同連結存在的時間長度進行加權

以下範例說明時間衰減的意義。假設要判斷 User B 是否為 User A 的潛在連結，考慮兩種情境：

• 情境 1： User A 的連結是近期建立的，表示 User A 的人脈正在成長，更有可能與 User B 連結
• 情境 2： User A 的連結是很久以前建立的，表示 User A 可能已經知道 User B 但選擇不連結

模型開發#

模型選擇#

先前我們將 PYMK 問題框架化為 edge prediction 任務，模型接收社交圖譜作為輸入，預測兩位使用者之間存在邊的機率。為了處理此任務，我們選擇能處理圖輸入的模型——Graph Neural Networks（GNN，圖神經網路）。

GNN 簡介#

GNN 是可以直接應用於圖資料的神經網路，能夠執行 graph-level、node-level 和 edge-level 預測任務。

如圖 11.9 所示，GNN 接收一個圖作為輸入。輸入圖包含與節點和邊相關聯的屬性：

• 節點屬性： 年齡、性別等使用者資訊
• 邊屬性： 使用者間特徵，如共同學校與工作場所數量、連結年齡等

給定輸入圖及相關屬性後，GNN 為每個節點產生 node embeddings。

產生 node embeddings 後，使用相似度度量（如 dot product）來預測兩個節點形成連結的可能性。例如，如圖 11.10 所示，計算節點 2 和節點 4 的 embeddings 之間的 dot product，以預測它們之間是否存在邊。

近年來已發展出多種 GNN 架構，如 GCN、GraphSAGE、GAT 和 GIT。這些變體有不同的架構和複雜度，需要透過大量實驗來確定最佳架構。關於 GNN 架構的深入理解，請參閱。

模型訓練#

訓練 GNN 模型時，提供時間 $t$ 的社交圖譜快照，模型預測在時間 $t+1$ 將形成的連結。

建構資料集#

建構資料集的步驟如下：

1. 建立時間 $t$ 的圖快照
2. 計算圖的初始節點特徵與邊特徵
3. 建立標籤

步驟 1：建立時間 $t$ 的圖快照

訓練資料的第一步是建立模型的輸入。由於 GNN 模型期望社交圖譜作為輸入，我們使用可用的原始資料建立時間 $t$ 的社交圖譜快照。

步驟 2：計算初始節點特徵與邊特徵

如圖 11.12 所示，提取使用者特徵（如年齡、性別、帳號年齡、連結數等）作為節點的初始特徵向量。

同樣地，提取使用者間親和度特徵作為邊的初始特徵向量。如圖 11.13 所示，User 2 和 User 4 之間有一條邊，$E_{2,4}$ 代表初始特徵向量，包含共同連結數、個人檔案瀏覽次數、共同學校的重疊時間等資訊。

步驟 3：建立標籤

使用時間 $t+1$ 的圖快照來確定正負標籤：

如圖 11.14 所示，根據在 $t+1$ 時是否形成新邊來建立正負標籤：

• 正標籤： 兩個節點在 $t+1$ 時建立了連結
• 負標籤： 兩個節點在 $t+1$ 時未建立連結

選擇損失函數#

輸入圖和標籤建立完成後，即可開始訓練 GNN 模型。GNN 訓練的詳細說明及適用的損失函數超出本書範疇，深入了解請參閱。

評估#

離線指標#

離線評估階段，評估 GNN 模型和 PYMK 系統的效能。

GNN 模型#

由於 GNN 模型預測邊的存在，可視為二元分類模型，使用 ROC-AUC 指標來衡量模型效能。

PYMK 系統#

前面章節已詳細討論排序與推薦系統的離線指標選擇，此處不再贅述。在本系統中，使用者會對推薦的連結進行「連結」或「忽略」。由於此二元特性，mAP 是合適的選擇。

線上指標#

實務上，公司會追蹤大量線上指標來衡量 PYMK 系統的影響。以下是兩個最重要的指標：

• 過去 $X$ 天內發送的連結請求總數
• 過去 $X$ 天內被接受的連結請求總數

過去 $X$ 天內發送的連結請求總數

• 幫助了解模型是否增加或減少了連結請求數量
• 例如，若模型使發送的連結請求總數增加 5%，可認為模型對業務目標有正面影響
• 缺點： 新連結僅在接收方接受請求後才會形成。使用者可能發送 1,000 個請求，但只有少數被接受，此指標無法正確反映使用者人脈的實際成長

過去 $X$ 天內被接受的連結請求總數

• 由於新連結僅在接收方接受請求後才形成，此指標能準確反映使用者人脈的真實成長

上線服務#

在服務階段，PYMK 系統需高效地為給定使用者推薦潛在連結清單。本節說明為何需要速度最佳化，並介紹提高 PYMK 效率的技術，最後提出各元件協同運作的系統設計。

效率最佳化#

根據需求，平台共有 10 億使用者，意味著為單一使用者找到潛在連結需要遍歷 10 億個 embeddings。更具挑戰性的是，需要為每位使用者都執行此演算法。以下是兩種常見的最佳化技術：

利用 Friends of Friends（FoF）#

根據 Meta 研究，92% 的新友誼都是透過 FoF 形成的。此技術利用使用者的 FoF 來縮小搜尋空間。

• 每位使用者平均有 1,000 個朋友
• FoF 數量約為 100 萬（$1000 \times 1000$）
• 搜尋空間從 10 億縮減至 100 萬

預先計算 PYMK#

需要在線上預測與批次預測之間做出選擇。

線上預測（Online Prediction）

• 在使用者載入首頁時即時產生潛在連結
• 不為不活躍使用者產生推薦
• 缺點：若計算時間過長，會造成不良的使用者體驗

批次預測（Batch Prediction）

• 系統預先為所有使用者計算潛在連結並儲存於資料庫
• 使用者載入首頁時直接取得預計算的推薦，體驗上幾乎是即時的
• 缺點：可能產生不必要的計算。若每天只有 20% 的使用者登入，為每位使用者每天產生推薦會浪費 80% 的計算資源

選擇批次預測的原因：

• 有 3 億日活躍使用者，為所有人即時計算 PYMK 可能太慢
• PYMK 的社交圖譜變化不快，預計算的推薦可在較長時間內保持相關性（例如保留 7 天後重新計算）
• 對於較新的使用者，可以縮短時間窗口（例如 1 天），因為其人脈成長較快

為避免使用者重複看到相同的推薦連結，可以預計算比所需更多的連結，僅顯示使用者尚未看過的推薦。

ML 系統設計#

圖 11.19 為 PYMK 的 ML 系統設計，包含兩個 pipeline：

• PYMK 產生 pipeline
• 預測 pipeline

PYMK 產生 pipeline#

此 pipeline 負責為所有使用者產生 PYMK 並將結果儲存至資料庫。流程如下：

步驟 1：FoF 服務 為特定使用者將連結縮小為候選連結子集（2-hop 鄰居）。

步驟 2：評分服務 接收 FoF 服務產生的候選連結，使用 GNN 模型為每個候選連結評分，產生排序後的 PYMK 清單並儲存至資料庫。使用者請求時，直接從資料庫取得個人化的 PYMK 清單。

預測 pipeline#

當請求到達時，PYMK 服務先查看預計算的 PYMK 是否存在推薦：

• 存在： 直接取得推薦
• 不存在： 向 PYMK 產生 pipeline 發送一次性請求

以上是簡化的系統設計。若面試中被要求進一步最佳化，可考慮：

• 僅為活躍使用者預計算 PYMK
• 使用輕量級排序器在評分服務之前縮減候選集
• 使用重排序服務為最終 PYMK 清單增加多樣性

其他討論要點#

若面試尚有剩餘時間，可以探討以下主題：

• Personalized random walk 是另一種常用的推薦方法，由於效率高，適合作為 baseline
• 偏差問題（Bias）： 高頻使用者在訓練資料中的代表性高於低頻使用者，模型可能對某些群體產生偏差。例如，高頻使用者可能以更高的比率被推薦給其他使用者，進而建立更多連結，使其在訓練資料中的代表性更高
• 忽略推薦的處理： 當使用者反覆忽略推薦的連結時，未來重排序中應降低被忽略推薦的排名
• 延遲回饋（Delayed feedback）： 使用者可能不會在收到推薦時立即發送連結請求，可能需要數天或數週。那麼何時將推薦的連結標記為負樣本？推薦系統中如何處理延遲回饋是一個重要議題