1. 前言
論文連結：https://arxiv.org/abs/2006.01963?context=cs.LG
github：https://github.com/sunxiangguo/MGCN
如今，大多數人都參與了不止一個線上社交網絡(OSN)，如Facebook、Twitter、微網誌、Linkedin。通常情況下，使用者為了不同的目的在不同的OSNs上注冊，不同的OSNs顯示了不同的觀點和人的不同方面。例如，一個使用者在Facebook上聯系他們的朋友，但是使用Linkedin聯系他/她的同僚，感興趣的公司和尋找工作機會。雖然不同的OSNs表現出不同的特性和功能，但在不同的社交平台上，個人使用者帳戶的重疊現象一直存在。然而，出于隐私考慮或缺乏動機，在大多數社交網絡中，屬于同一個人的多個賬戶的資訊并沒有明确給出。
在資料挖掘研究領域中，将來自不同社交網絡的屬于同一個人的賬号比對問題定義為Account Mapping(賬号映射)、Socia Network De-anonymization(社交網絡去匿名化)或Social Anchor Link Prediction(社交錨鍊預測)。不同社交平台上的賬戶比對在社交網絡分析中扮演着重要的角色
因為它有助于改善許多下遊應用，如線上個性化服務、連結預測、推薦系統、生物蛋白-蛋白對老化相關複合物的比對，以及犯罪行為檢測。盡管人們對這一具有挑戰性的課題給予了很大的關注，但仍有很大的改進空間。以往的研究提出利用可用的輔助資訊，如自生成的使用者資料、每日生成的内容和其他人口統計特征(如使用者名、頭像、位置、性别、文章、部落格、評論等)來解決這一問題。然而，随着公衆隐私和資訊權利意識的提高，這些資訊越來越難以獲得和擷取。
跨平台賬戶比對在社交網絡分析中扮演着重要的角色，并且有利于廣泛的應用。然而，現有的方法要麼嚴重依賴高品質的使用者生成内容(包括使用者配置檔案)，要麼僅關注網絡拓撲結構就存在資料不足的問題，這給研究者帶來了模型選擇的兩難困境。為了解決這個問題，本文提出了一個新的架構，在局部網絡結構和超圖結構上統一考慮多層次的圖卷積。該方法克服了現有工作中資料不足的問題，且不需要依賴使用者的人口統計資訊。此外，為了使所提方法能夠處理大規模社交網絡，提出了一種兩階段空間協調機制，以在基于網絡劃分的并行訓練和跨不同社交網絡的賬戶比對中對齊嵌入空間。在兩個大規模的現實社會網絡上進行了廣泛的實驗。實驗結果表明，該方法的性能優于現有模型。
近年來，随着網絡嵌入(NE)技術的發展，相關問題的研究重點已轉移到挖掘網絡結構資訊上。社交網絡結構資料在正确性和完整性方面更加可靠。但是，隻注重網絡結構本身的模組化，使得幾乎所有現有的方法都存在資料不足的問題，特别是在小規模網絡和冷啟動設定(即使用者是網絡的新使用者)。是以，在現實場景中，這一直是從業者所面臨的困境，迫切需要有效的解決方案。基于此提出利用并整合從原始網絡中提取的超圖資訊來進行資料增強。在本文的其餘部分，我們分别使用“簡單圖”和“超圖”來表示原始網絡和從原始網絡中提取的超圖。與簡單圖相比，超圖允許一條邊(又名heperedge)同時連接配接兩個以上的節點。這意味着圖中節點之間的非成對關系可以很容易地組織并表示為超邊。此外，超圖具有魯棒性和靈活性，能夠适應各種各樣的社交網絡，無論給定的社交網絡是純社交網絡還是具有各種屬性和連結的異構社交網絡。
更具體地說，提出了一種新的多層圖卷積網絡的嵌入架構，即MGCN，用于聯合學習不同粒度靈活GCN核(即簡單圖GCN、超圖GCN)的網絡頂點的嵌入。社交網絡的簡單圖結構資訊揭示了使用者之間的關系(如友誼、關注者)，而超圖則根據其在社交網絡中的具體定義具有不同的語義意義。例如，基于N-hop鄰居的超圖(使用者的N-hop鄰居通過同一個超邊連接配接)在一定程度上表示朋友圈。基于中心的超圖表示不同的社會層次(具有相似中心性值的使用者可能具有相同的社會地位)。是以，通過定義各種超圖并将其嵌入到網絡嵌入學習中，将有助于學習更好的使用者表示。為了支援這一點，MGCN架構是靈活的，可以包含各種超圖定義，它可以将任何超圖作為向量表示，使模型結構對各種超圖定義不變性。通過擴充GCN來利用和內建超圖的基本原理是，超圖提供了更靈活的網絡。與本地網絡拓撲上的單個圖GCNs相比，可以包含更多更豐富的資訊的表示。在大多數情況下，GCN層的最優數量總是被設定為2，因為添加更多的層不能顯著提高的性能。是以，GCNs隻能捕獲網絡中某個節點周圍的本地資訊。這一現象也使得solo GCN存在沖突，是以在account matching task上表現的一般，因為task的關鍵是探索更多更深的資訊來進行預測。從直覺上看，在從原始網絡中提取的hypergrpahs上定義GCNs将補充現有基于gc的網絡嵌入模型的局限性。
然而，這仍然是一項具有挑戰性的任務，因為社交網絡是大規模的，有數百萬個節點和數十億個邊緣。傳統的集中訓練方法由于計算量大，無法适應這樣大的網絡。為了使MGCN适應于大規模社交網絡，提高其可擴充性和效率，提出了一種新的訓練方法，該方法首先将大規模社交網絡分割成簇，然後以完全分散的方式學習網絡嵌入。為了對齊不同簇的學習嵌入空間，提出了一種新的兩相空間協調機制。在第一階段，我們對齊從同一網絡内的每個簇中學習到的嵌入空間。除了不同子網之間的排列在同一網絡,推導空間和解對齊兩個不同網絡通過少量的觀測錨節點,這使得我們的MGCN架構實作更精确的錨點連結比最先進的模型和預測效率高在大型社交網絡。
總結論文主要貢獻如下：
- 提出了一個新的架構MGCN，用于預測跨不同社交網絡的錨連結這一具有挑戰性的任務。該方法同時考慮了局部和超圖級的圖卷積來學習網絡嵌入，能夠為任務捕獲更廣泛、更豐富的網絡資訊。
- 為了使所提出的架構能夠适應大規模的社交網絡，提出了一系列的處理方法，包括網絡分割和空間調和來處理分布式的訓練過程。
- 對大規模真實資料集進行了廣泛的評估，實驗結果證明了提出的MGCN模型相對于最新模型的優越性。
2. 定義
2.1 問題定義
已知多個圖例如： G 1 = { V 1 , E 1 } \mathcal{G_1=\{V_1,E_1\}} G1={V1,E1} 和 G 2 = { V 2 , E 2 } \mathcal{G_2=\{V_2,E_2\}} G2={V2,E2} 和 一組錨點連結 S a n c h o r = { ( u , v ) ∣ u ∈ V 1 , v ∈ V 2 } S_{anchor}=\mathcal{\{(u,v)|u \in V_1,v \in V2\}} Sanchor={(u,v)∣u∈V1,v∈V2}，目标是對無法觀測到的跨平台錨點連結進行預測，并把整個問題看成是一個二分類問題，進而将問題轉化為：給出一組節點 ( u , v ) \mathcal{(u,v)} (u,v) 并滿足 u ∈ V 1 , v ∈ V 2 \mathcal{u \in V_1},v \in V_2 u∈V1,v∈V2，利用模型對他們之間是否存在連結進行預測。
2.2 超圖定義
對于簡單圖來說一條邊僅連接配接兩個節點，對于超圖來說圖定義為 G h = { V , E h } \mathcal{G^h=\{V,E^h\}} Gh={V,Eh}，其中 V \mathcal{V} V 代表節點集， E h \mathcal{E^h} Eh 代表超邊集，對于每一條超邊 e ∈ E h e \in \mathcal{E^h} e∈Eh 存在 e = { v 1 , . . . v p } , v i ∈ V , 2 < p < = ∣ V ∣ e=\{v_1,...v_p\},v_i \in \mathcal{V},2<p<=|\mathcal{V}| e={v1,...vp},vi∈V,2<p<=∣V∣
3. 模型
3.1 模型架構
為了預測錨鍊，引入了一種新的多層次圖卷積網絡(MGCN)來學習每個網絡的嵌入。圖1展示了提出的MGCN架構，它由兩個層次的圖卷積操作組成。它首先對簡單的圖(即本例中原始的社交網絡)進行卷積。在從簡單圖的卷積中得到節點嵌入後，通過定義在超圖上的一個創新的卷積運算對節點嵌入進行細化。在最終獲得兩個社交網絡的嵌入後，我們通過嵌入和解過程對齊兩個網絡的潛在空間。最後，部署一個全連接配接的網絡來預測來自兩個網絡的任意對節點之間是否存在錨鍊。此外提出了一種可并行的方案，使MGCN能夠通過圖劃分有效地處理大規模網絡。
3.2 Convolution on Simple Graphs
首先我們已知初始的社交網絡 G = { V , E } \mathcal{G =\{V,E\}} G={V,E} 并假設我們已經從原始的圖中建構出了超圖 G h \mathcal{G^h} Gh 其中每一條超邊應滿足 e ∈ E h , e = { v 1 , v 2 , . . . , v n } , v i ∈ V e \in \mathcal{E^h},e=\{v_1,v_2,...,v_n\},v_i \in \mathcal{V} e∈Eh,e={v1,v2,...,vn},vi∈V。節點的特征矩陣表示為 X ∈ R ∣ V × d ∣ X \in \mathbb{R}^{|\mathcal{V}\times d|} X∈R∣V×d∣，其中 d d d 表示特征嵌入次元。是以在超邊 e e e 内的簡單圖卷積可以被定義為
其中 A e ∈ R ∣ V ∣ × ∣ V ∣ A_e \in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|} Ae∈R∣V∣×∣V∣ 代表在超邊内的鄰接矩陣， σ ( ⋅ ) \sigma(\cdot) σ(⋅) 代表以 R e L U ( ⋅ ) ReLU(\cdot) ReLU(⋅) 為例的非線性激活函數
與簡單地作用于整個圖的普通GCN相比，對每個超邊分别執行卷積操作。其基本原理是，我們可以将來自超邊的細粒度本地結構資訊合并到已學習的節點嵌入中。為了實作這一點，文章對每一條超邊 e e e 定義了一個度矩陣 S e ∈ R ∣ V ∣ × ∣ V ∣ S_e \in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|} Se∈R∣V∣×∣V∣，矩陣中的每一個點 S e ( v i , v j ) S_e(\mathcal{v_i,v_j}) Se(vi,vj) 被定義為：
其中 p ( v , e ) p(v, e) p(v,e) 表示在超邊 e e e 中觀察節點 v v v 的可能性，其計算取決于超邊的特定定義。之後定義 A ^ = I ∣ V ∣ + D − 1 2 A D − 1 2 \hat{A}=I_{|\mathcal{V}|}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} A^=I∣V∣+D−21AD−21 其中 D ∈ R ∣ V ∣ × ∣ V ∣ D \in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|} D∈R∣V∣×∣V∣ 是一個對角矩陣，其中的值代表每一個節點在簡單圖中的度， A A A 代表簡單圖中的鄰接矩陣， I ∣ V ∣ I_{|\mathcal{V}|} I∣V∣ 代表機關矩陣，基于此超邊 e e e 的鄰接矩陣可以被定義為
直覺地， A e A_e Ae可以看作是超邊 e e e 中直接連接配接節點的鄰接矩陣，再由 S e ( v i , v j ) S_e(\mathcal{v_i,v_j}) Se(vi,vj)中的超邊連通性對其進行權重。是以，在執行簡單的圖卷積時，我們可以同時考慮兩種類型的本地節點-節點結構資訊，使已學習的基嵌入更具表現力。根據(1)，通過對所有超邊求和，可以得到對整個簡單圖G的卷積運算:
⊕ ⊕ ⊕ 代表對每一條超邊 e e e 進行本地圖卷積運算後将結果進行級聯操作， f ( ⋅ ) f(\cdot) f(⋅) 表示将連接配接的嵌入映射回 d d d 維空間的密集層。
3.3 Convolution on Hypergraphs
再簡單圖上學習到節點的嵌入表示 X s i m p l e K X_{simple}^K XsimpleK之後，我們希望在每一個節點表示中繼續加入構造後的超圖 G h \mathcal{G^h} Gh 中包含的結構化資訊。近年來，超圖卷積網絡開始受到網絡嵌入研究界的關注。不同于大多數相關工作利用頻譜卷積理論推導超圖卷積，本文中将其視為簡單圖卷積的廣義版本，推導出了超圖卷積的數學形式，使推理過程更加直覺、自然。
超圖的關聯矩陣 H ∈ R ∣ V ∣ × ∣ E h ∣ H \in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{E^h}|} H∈R∣V∣×∣Eh∣ 中的元素值被定義為
其中 p ( v , e ) p(v,e) p(v,e) 的含義與上一節中在簡單圖中的圖卷積意義相同，定義對角矩陣 D n ∈ R ∣ V ∣ × ∣ V ∣ , D n ( v , v ) = ∑ e ∈ E h H ( v , e ) D_n \in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|},D_n(\mathcal{v,v})=\sum_{e \in \mathcal{E^h}}H(v,e) Dn∈R∣V∣×∣V∣,Dn(v,v)=∑e∈EhH(v,e)，相似的超邊的度矩陣可以被表示為 D e ∈ R ∣ E h ∣ × ∣ E h ∣ , D e ( e , e ) = ∑ v ∈ V H ( v , e ) D_e \in \mathbb{R}^{|\mathcal{E^h}|\times|\mathcal{E^h}|},D_e(e,e)=\sum_{\mathcal{v \in V}}H(v,e) De∈R∣Eh∣×∣Eh∣,De(e,e)=∑v∈VH(v,e)。節點的度矩陣和邊的度矩陣可以分别了解為節點與多少條超邊相關，一條超邊中含有多少個節點。基于此權重的鄰接矩陣 A h ∈ R ∣ V ∣ × ∣ V ∣ A_h \in \mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|} Ah∈R∣V∣×∣V∣ 可以表示為
在獲得了超圖的鄰接矩陣後，我們可以很自然地将簡單圖卷積推廣到超圖 G h \mathcal{G^h} Gh。回想一下，在2017年發表的圖卷積經典論文中給出的典型GCN架構中，對于一個簡單圖 G s = { V s , E s } \mathcal{G^s = \{V^s, E^s\}} Gs={Vs,Es}，标準圖卷積定義為:
其中 D s D_s Ds 包括了圖中所有節點的度， A s A_s As 代表圖的鄰接矩陣。除機關矩陣 I ∣ V s ∣ I_{|\mathcal{V}^s|} I∣Vs∣外，上述标準圖卷積的核心依賴于度矩陣和鄰接矩陣 D s D_s Ds 和 A s A_s As 中編碼的節點關系。是以，将其輸入替換為從超圖 G h 中 \mathcal{G}^h中 Gh中提取的相應資訊，我們可以像對每一層 k k k 的标準GCN一樣，有效地對超圖卷積模組化:
其中滿足 X k = X s i m p l e K , k = 0 X^k=X^K_{simple},k=0 Xk=XsimpleK,k=0。假設我們在超圖上也采用 K K K 層卷積，那麼多層圖卷積網絡的最終輸出為 X K X^K XK。這樣，在 X s i m p l e k + 1 X^{k+1}_{simple} Xsimplek+1 中生成的節點嵌入既可以捕獲成對關系(即1跳鄰域)，也可以捕獲高階非成對關系(即超邊)。當用于訓練的觀察錨節點數量有限時，這一點尤為重要。
3.4 Learning Network Embeddings
對于網絡嵌入，通過最大化正邊的機率和最小化負邊的機率來學習(9)中的輸出嵌入:
其中 η ( ⋅ , ⋅ ) \eta(\cdot,\cdot) η(⋅,⋅) 代表 sigmoid函數來計算包含 ( v i , v j ) (v_i,v_j) (vi,vj)的機率
對于訓練集中給定的正邊 ( v i , v j ) (v_i,v_j) (vi,vj)，我們使用雙向負采樣政策繪制負邊進行訓練。具體來說，我們固定 v i v_i vi，通過一個關于 d v 0.75 d_v^{0.75} dv0.75的噪聲分布 P n ( v ) P_n(v) Pn(v)生成 M M M 個負節點 v k v_k vk，其中 d v d_v dv 是節點 v v v 的度數。然後，我們用同樣的方法固定 v j v_j vj 并采樣 M M M個負節點。通過對(10)的優化，我們可以從最後一層 k k k 中得到 X K X^K XK 中最優的嵌入值，然後将最終的嵌入值進一步用于下遊錨鍊預測任務。
3.5 Anchor Link Prediction
在得到兩個圖的嵌入表示 X 1 K X_1^K X1K 和 X 2 K X_2^K X2K 之後我們不能直接将其用于連接配接預測，因為兩者被映射在了不同的表示空間，這在語義語境中有很大的不同。相反，我們首先将它們協調到相同的潛在空間中，然後使用對齊的嵌入來進行錨鍊預測。為了将 X 1 K X_1^K X1K 和 X 2 K X_2^K X2K 映射到同一個空間中，我們将 X 1 k X^k_1 X1k固定下來，并将 X 2 K X_2^K X2K 投影到 X 1 K X_1^K X1K 所在的同一個空間中。讓 γ ( . ∣ Γ , b ) γ(.|Γ,b) γ(.∣Γ,b) 是一個投影函數的投影矩陣 Γ Γ Γ 和偏置矩陣 b b b。然後，通過調整錨節點在兩個圖中的嵌入表示，我們可以學習投影函數中的參數，進而確定兩者被映射到同一空間：
其中 γ ( . ∣ Γ , b ) = x Γ + b γ(.|Γ,b)=xΓ+b γ(.∣Γ,b)=xΓ+b， S a n c h o r S_{anchor} Sanchor 代表帶标簽的錨點連結。那麼，對于任意一對節點 ( v i , v j ) ， v i ∈ G 1 , v j ∈ G 2 (v_i,v_j)，v_i \in \mathcal{G_1},v_j \in \mathcal{G_2} (vi,vj)，vi∈G1,vj∈G2，這對節點的表示可以用它們對應的嵌入連接配接表示。我們将這對嵌入發送到一個全連接配接網絡中，最後輸出它們是否是錨鍊的預測，并使用交叉熵作為錨鍊預測的損失函數。
3.6 Handling Large-Scale Networks
雖然基于GCN的方法在各種任務中得到了廣泛的應用，但是大多數相關方法在處理大規模網絡時仍然存在“最後一英裡”的問題，因為大多數基于GCN的方法需要全局鄰接矩陣作為輸入，這很容易造成GPU計算的記憶體不足問題。此外，随着網絡規模的增大，計算時間也會增加。是以，我們需要一個有效的圖劃分政策，以便并行部署所提議的MGCN。
為此，我們首先通過算法1提出一種圖劃分方法，并提出一種兩階段協調機制，如圖2所示。具體來說，我們根據子產品化最大化将大型網絡劃分為幾個分區，然後在每個分區上部署我們的模型。對于每一個圖,
在對整個圖進行分區時，我們使用保留的錨節點将所有分區的潛在空間協調到同一個分區中。然後，我們使用從兩個圖中觀察到的錨節點将 G 1 \mathcal{G_1} G1 和 G 2 \mathcal{G_2} G2 的嵌入對齊到相同的潛在空間中。
3.6.1 Graph Partition
如算法1所示，為了将大型網絡分割成若幹個大小可接受的分區(例如，從 N m i n N_{min} Nmin 節點到 N m a x N_{max} Nmax 節點)，我們首先使用Louvain算法計算子產品化程度最大的網絡分區。對于每個分區 G ′ = { V ′ ， E ′ } \mathcal{G ' = \{V '， E '\}} G′={V′，E′}，如果其大小大于上界，即 ∣ V ′ ∣ > N m a x |V ' | > N_{max} ∣V′∣>Nmax，我們再次将 G ′ G' G′ 作為輸入，重複算法将 G G G '進一步分割成更多更小的分區。如果 ∣ V ′ ∣ < N m i n |V ' | < N_{min} ∣V′∣<Nmin，則随機将其配置設定給其他已建立的分區。
3.6.2 Reconcile Latent Embedding Spaces
将模型獨立地部署到不同的分區實際上會在不同的潛在空間中産生嵌入。是以我們需要進一步将不同的分區比對到相同的表示空間中。在這裡，從網絡中選擇 N N N 個節點作為跨所有分區的共享節點，并将這 N N N 個節點以及它們的關聯邊附加到所有分區中。然後選擇一個固定的分區，并将其他分區協調到同一個空間中，例如，對于所有 P P P 分區 G 1 , G 2 ， ⋅ ⋅ ⋅ , G P \mathcal{{G_1, G_2，···,G_P}} G1,G2，⋅⋅⋅,GP，我們修複分區 G 1 \mathcal{G_1} G1 和所有其他分區的嵌入通過線性函數轉換 g ( ⋅ ) g(\cdot) g(⋅)。最大化以下目标:
V s h a r e d \mathcal{V}_{shared} Vshared 是一組共享的節點出現在所有分區,和 x i ( p ) x_i^{(p)} xi(p) 是節點的表示 v i v_i vi在 p p p 分區。因為我們已經将每個分區的解雇映射到相同的空間，是以我們可以得到最終網絡的嵌入，由此根據(11)可以得到最終的結果。
3.7 Optimization Strategy
在本文中采用逐漸訓練政策來訓練模型，具體地說,通過優化圖嵌入目标函數 O e m b e d d i n g O_{embedding} Oembedding 來第一次訓練MGCN模型。然後對圖劃分協調目标函數 O p a r t i t i o n O_{partition} Opartition(即第一階段空間協調)進行優化，再對協調目标 O a n c h o r O_{anchor} Oanchor(即第二階段空間協調)進行優化。最後，利用兩個圖中完全對齊的節點嵌入，通過最小化交叉熵損失來優化用于錨鍊預測任務的MGCN
4. 實驗結果