文章目錄

• 摘要
• 1.Introduction
• 2. 介紹兩個概念
• • 2.1 Dynamic Heterogeneous Network Model動態異構網絡模型
  • 2.2 時間隨機游走
• 3NODE2BITS:基于散列的Emdedding框架
• • 3.1 采樣時間隨機游動和定義時間上下文
  • 3.2 基于多維特征的時態語境（上下文
  • 3.3基于特征的上下文聚合和散列
• 4.EXPERIMENTS

摘要

在真實的web服務中，識別和匹配各種在線引用(例如，在不同設備和時間段上的會話)到同一用戶的任務對于個性化和推薦是至關重要的。然而，傳統的用戶拼接方法(如分組或阻塞)需要對大量用戶活動進行兩兩比較，從而對計算和存儲都造成了挑戰。最近的作品，往往是應用特定的，啟發式地尋求減少比較的數量，但他們遭受低精度和回憶。為了以與應用程序無關的方式解決這個問題，我們采用了一種基于異構網絡的方法，其中用戶(節點)與內容(如會話、網站)交互，并且可能具有屬性(如位置)。我們提出了node2bits，這是一種使用二進制哈希碼表示節點上下文多維特征的高效框架。node2bits利用基于特征的時間步來封裝異構web網絡中節點之間的短期和長期交互，并采用SimHash來獲得緊湊的二進制表示，避免了相似度搜索的二次復雜度。在大型真實網絡上的大量實驗表明，node2bits的性能比傳統技術和現有工作都要好，后者在用戶拼接方面的F1分數最高可達5.16%，而存儲空間只占1.56%。

1.Introduction

個性化和推薦通過提供相關體驗和處理新聞、web搜索、娛樂等方面的在線信息過載來提高用戶滿意度。隨著時間的推移，準確地建模用戶行為和偏好是個性化的核心。然而，追蹤用戶在線活動是一項挑戰，因為用戶每天都要與來自不同地點的數十臺聯網設備進行交互，導致用戶檔案支離破碎。如果沒有統一的配置文件，所觀察到的用戶數據將是稀疏的、不具有代表性的，并且對于驅動業務成功的準確預測是不夠的。

• 追蹤用戶的挑戰
  • 用戶每天都要與來自不同地點的數十臺聯網設備進行交互，導致用戶檔案支離破碎。

在這項工作中，我們解決了身份或用戶拼接的問題，其目的是識別和分組在不同渠道、平臺、設備和瀏覽器[30]上發生的相同用戶的登錄和匿名會話。這個問題是實體或身份解析的一種形式[13,2]，也稱為實體鏈接、記錄鏈接和重復檢測[6,21,2]。在實體解析中，每個用戶的文本信息(例如，姓名、地址)是可用的，而身份拼接僅依賴于用戶與在線內容和web元數據的交互。雖然cookie可以幫助同一用戶縫幾個不同的會話，但許多用戶有多個cookie(例如，每個設備或web瀏覽器的一個cookie)[8]，而且大多數cookie在短時間內就會過期，因此不能幫助縫用戶。類似地，IP地址在不同位置的變化會導致在不同時間擁有相同IP地址的用戶(例如，機場)之間產生碎片甚至錯誤的拼接。與此同時，指紋識別方法基于設備或瀏覽器配置捕獲用戶相似度，而不是基于跨設備或瀏覽器保持一致的行為模式。另一方面，實體解析的窮舉解決方案需要所有實體對之間的二次比較，這對于大型web服務在計算上是難以處理的。這可以通過阻塞[24]的啟發式來部分處理，它將類似的實體描述分組到塊中，并且只比較同一塊中的實體。

• 本文做

  • 實體鏈接
  • 記錄鏈接
  • 重復檢測

• 實體解析

  • 每個用戶的文本信息(例如，姓名、地址)是可用的，
  • 身份拼接僅依賴于用戶與在線內容和web元數據的交互

• 使用cookie–不可用

  • cookie可以幫助同一用戶縫幾個不同的會話，
  • 但許多用戶有多個cookie
  • 大多數cookie在短時間內就會過期，因此不能幫助縫用戶

• 使用IP地址–不可用

  • P地址在不同位置的變化會導致在不同時間擁有相同IP地址的用戶(例如，機場)之間產生碎片甚至錯誤的拼接。

• 指紋識別方法

  • 基于設備或瀏覽器配置捕獲用戶相似度，而不是基于跨設備或瀏覽器保持一致的行為模式。
  • 不可能用跨設備或瀏覽器

• 窮舉方案–分塊處理

  • 實體解析的窮舉解決方案需要所有實體對之間的二次比較，這對于大型web服務在計算上是難以處理的。
  • 這可以通過阻塞[24]的啟發式來部分處理，它將類似的實體描述分組到塊中，并且只比較同一塊中的實體。

• 解決方案的思想：

  • 相似用戶：:相同的用戶跨平臺訪問相似的內容，并且隨著時間的推移具有相似的行為。
  • 動態異構網絡中隨時間變化的不同內容和平臺的用戶交互進行建模，其中用戶將映射到對應于相同現實實體的節點的標識。
  • 在節點表示學習成功的激勵下，我們的目標是在這個豐富的交互網絡中找到隨時間變化的用戶配置文件的嵌入。

• 挑戰：

  • 大型圖數據–太大了

• 目標：

  • 有效地找到稀疏的二進制表示
  • 和基于相似活動的鏈接實體，同時
  • 避免對所有用戶配置文件進行兩兩比較

• 問題1(臨時的、基于哈希的節點嵌入)。給定一個圖G (V, E),基于散列的網絡嵌入的目標是學習函數χ:V d{0,1}這樣派生的二進制采用嵌入

  • (1)在交互空間中保持相似性在G
  • (2)有效利用空間
  • (3)準確地捕獲時間信息和底層網絡的異構性。
    

• Node2BITs：

  • 它捕獲網絡中節點間的臨時有效交互，并
  • 基于拓撲特征和
  • (可選)參與交互的實體側信息。

• 本文的貢獻：

  • 基于嵌入的公式:超越傳統的阻塞技術，我們將用戶拼接的問題表述為在異構網絡中尋找臨時的、基于散列的嵌入的問題，以便它們在用戶交互之間保持隨時間的相似性。
  • 節省空間的嵌入:我們提出node2bits，這是一個實用、直觀、快速的框架，可以生成適合用戶拼接的緊湊的二進制嵌入。我們的方法結合了上下文的隨機步進抽樣、基于特征的直方圖表示和局部敏感哈希來保持上下文隨時間的異構等價性。
  • 廣泛的經驗分析:我們在真實網絡上的實驗表明，node2bits輸出一種節省空間的二進制表示，比基線少使用63到339個空間，同時在用戶拼接任務中獲得了可比較或更好的性能。此外，node2bits對于大型的現實世界、時間和異構網絡是可伸縮的
  • https://github.com/GemsLab/node2bits.

2. 介紹兩個概念

動態異構網絡模型和時間隨機游動

2.1 Dynamic Heterogeneous Network Model動態異構網絡模型

• 我們將用戶與內容、網站、設備等的交互建模為異構網絡
• 異構網絡：異構網絡G = (V, E,ψ,ξ)
  • V：節點集合
  • E：邊集
  • 映射ψ:V→${\tau }_V$節點類型
  • (iii)映射ξ:E→${\mathrm{T}}_E$邊集類型
• 許多圖類型是異構網絡的特例:
  • 同構圖：$|{\tau }_V|=|{\tau }_E|=1$
  • k部圖： $|{\tau }_V|=k,|{\tau }_E|=k?1$
  • signed network:$|{\tau }_V|=1,|{\tau }_E|=2$
  • labeled graph： a single label per node/edge.
• 建模為連續時間的動態網絡
• (連續時間動態網絡)：一個連續時間動態、異構網絡G = (V, Eτ，ψ,ξ,τ)
  • Eτ：時間邊
  • $\tau :E\to R^{+}$將每條邊映射到對應時間戳的函數

2.2 時間隨機游走

• 圖上的行走是節點序列，其中每對連續節點由一條邊連接。目前流行的網絡嵌入方法是使用隨機化的過程生成游動[25,14]來構造節點ids或節點上下文的語料庫。在連續時間動態網絡中，時間上有效的遍歷被定義為一組節點序列，這些節點由具有非遞減時間戳的邊連接(例如，表示用戶內容交互發生的順序)，并且首次被提出并用于嵌入
• 定義：temporal walk：
  • L:長度v1->vL在圖G = (V, E,ψ,ξ)
  • 路徑：v1,v2,…,vL
  • $$\begin{gathered} <v_i,v_{i+1}>\in E_{\tau },1\le i\le L \\ 時間順序排列：\tau (v_i,v_{i+1})\le \tau (v_{i+1},v_{i+2}),1\le i\le L?1 \end{gathered}$$

3NODE2BITS:基于散列的Emdedding框架

• 任務：用戶拼接
• 目的：在實際交互的上下文中簡潔地描述每個節點/實體(問題1)
• 要求
• 支持異構網絡
• 保證數據中事件和交互的時間有效性;
• 在運行時擴展到具有數百萬個節點/邊的大型網絡;
• 內存需求的規模與空間效率，但強大的二進制嵌入式可以捕獲id無關的相似性。
• 我們詳細介紹了node2bits的三個主要步驟:
  • (3.1)采樣時間隨機游動和定義時間上下文;
  • (3.2)基于多維特征構建時態語境;
  • (3.3)將上下文聚合和散列成稀疏嵌入。我們在圖2和算法1中給出了node2bits的概述
    

3.1 采樣時間隨機游動和定義時間上下文

node2bits的第一步是捕獲節點上下文中的交互，這對于用戶拼接任務非常重要:它不是簡單的交互，而是通過隨機漫步對更復雜的交互序列進行采樣。但與許多現有的表示學習方法不同[25,14]，我們的方法通過Lstep時間隨機游走(定義3[23])對現實交互進行采樣，從而滿足需求R2。node2bits將節點u在時間距離t處的時間上下文$C_u^{\Delta t}$定義為采樣的隨機游走中時間距離$\Delta t$,距離為$\Delta t$的實體集合為u的上下文。

• 通過隨機游走對更復雜的交互序列進行采樣
• $$\begin{gathered} 上下文：C_u^{\Delta t}=\{v:|w_K[v]?w_L[u]=\Delta t,任意w_L\in W\} \\ {w}_L[‘]是隨即游走中對應節點的索引 \end{gathered}$$

通常，小的時間距離值可以捕捉到實體間更直接的交互作用和相似性。在靜態圖中，?t僅僅對應于采樣序列中節點之間的距離，沒有捕捉到任何時間信息。
時間局部性。上面定義的上下文沒有明確地包含連續采樣的交互之間經過的時間。然而，在建模臨時用戶交互時，區分短期轉換和長期轉換非常重要。受[23]的啟發，node2bits解釋了連續上下文之間的緊密性或局部性(例如，$C_u^{\Delta t}和C_u^{\Delta t+1}$）通過不同的偏置時間步長策略。例如，在短期策略中，節點u到v的

轉移概率為softmax函數

• short-term transitions
• 轉移概率：$p(v|u)=\frac{exp(?\tau (u,v)/d)}{{\Sigma }_{i\in {\mathrm{T}}_{\tau }(u)}exp(?\tau (u,i)/d)}$softmax
  • $d=ma{x}_{e\in E_{\tau }}\tau (e)?mi{n}_{e\in E_{\tau }}\tau (e)$ 所有時間戳的總持續時間，
  • ${\mathrm{T}}_{\tau }(u)$時間鄰域的集合:從節點u通過時間有效邊到達。
• long-term transitions
  • 轉移概率同上
  • 同樣，在長期政策中，節點u到v的轉移概率如式(2)所示，但分子分母上都有正的符號。

3.2 基于多維特征的時態語境（上下文

式(1)中的上下文取決于節點標識(IDs)。然而，在多平臺環境中，單個實體可能有多個節點id，因此可能導致看起來不同的上下文。為了生成與身份無關的適合用戶拼接的上下文，我們通過假設相應或相似的實體具有相似的特征，使時態上下文具有屬性感知或特征感知(R1)。正式,我們假設一個網絡可能有一組輸入節點屬性(如IP地址,設備類型),以及一組導出拓撲特性(例如,學位,PageRank),所有這些都存儲在一個N
x|F
|特性矩陣F(圖2中,步驟1)。然后,我們推廣我們的隨機漫步不僅依據時間(R2)[23],還捕獲這個特性信息使用的概念認為/特點走在[1提出

• 與id無關的上下文：我們通過假設相應或相似的實體具有相似的特征，使時態上下文具有屬性感知或特征感知(R1)
• 基于特征的時間隨機游走：（通用的
  

3.3基于特征的上下文聚合和散列

用戶縫合的關鍵點是，隨著時間的推移，每個用戶都通過類似的關系與類似類型的實體進行交互:例如，在在線銷售日志中，用戶可能在登錄和匿名會話中瀏覽類似類型的商品;在在線社交網絡中，分享幾乎相同的互動模式(如回復或分享)的賬戶可能來自同一個人。基于這一認識，node2bits使用節點類型(以及隱含的對應關系或邊緣類型)增強了先前生成的時間、多維特征上下文，這是異構網絡(R1)的一個關鍵屬性。隨后，它將它們聚合起來，并通過對位置敏感的哈希得到保持相似性和節省空間的二進制實體表示(R4)。

• 關鍵點：行為相似的用戶是同一個人。
• node2bits：上下文（節點類型+時間+多維特征）->聚合->位置敏感的hash保持相似性，二進制實體表示

context聚合。與現有的將上下文特征聚合成單個值(如平均值或最大值)的工作不同[15,29]，node2bits將它們聚合成更低損耗的表示形式:通過區分節點類型(R1)為異構網絡定制的直方圖。具體地，通過進一步將式(4)中的導出上下文條件設置在節點類型$p_i\in {\mathrm{T}}_v$(即，每個時態上下文只包含一個節點類型的特征)。我們將基于特征和節點類型的時間上下文表示為$C_u^{\Delta t}|f,p$。節點u在時間距離t處的最終直方圖表示由t處條件上下文上的直方圖連接組成(圖2，步驟3)。
在這種表示法中，特征被對數地結合起來，以解釋結構特征(如度)的經常偏態分布。我們注意到，直方圖可以進一步擴展到[19]中所示的邊緣類型，例如，通過區分由多種類型的邊緣連接的節點對。

• simHash：保持相似性的hash表示（也保證了空間效率
  • 余弦相似度也被映射過去了
    
    

4.EXPERIMENTS

• 標準
  • 有效嗎？
  • 比以前好嘛
  • 可擴展嗎
  • 空間需求低否
• 任務構建
  • 用戶鏈接–二元分類任務，每一對節點，是否是一個人？
    

總結

以上是生活随笔為你收集整理的论文学习5-NODE2BITS: Compact Time- and Attribute-aware Node Representations for User Stitching的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。