天天看點
傳回

LINE 圖嵌入算法介紹與源碼淺析

LINE 圖嵌入算法介紹與源碼淺析

前言 (可以略過~)

最近閱讀了一些 Paper 和代碼實作, 打算及時記錄下來, 以便日後查閱和回憶; 寫關于 Paper 的部落格, 可以對文章進行翻譯, 也可以隻描述中心思想+自己的感悟, 兩者均有好處: 前者内容詳盡, 事無巨細, 查閱起來友善快捷, 不足之處是我不太擅長, 沒有動力做~ ????; 後者友善了寫作者, 但對閱讀者不太友好, 如果時間一長, 其實對自己也不太友好, 因為文章的主要内容估計忘得差不多了, 又得傳回去看原文 … 聯想到我寫的 ​​PyGCN 源碼閱讀​​, 感覺還是應該多介紹一些理論内容, 再配合源碼進行分析, 事半功倍. 後面寫作的時候, 盡可能使用理論+代碼的形式吧, 如何恰到好處, 得多寫寫文章來把握.

廣而告之

可以在微信中搜尋 “珍妮的算法之路” 或者 “world4458” 關注我的微信公衆号；另外可以看看知乎專欄 ​​PoorMemory-機器學習​​, 以後文章也會發在知乎專欄中；

LINE 圖嵌入算法介紹

文章資訊

  • 論文标題: LINE: Large-scale Information Network Embedding
  • 論文位址:​​https://arxiv.org/abs/1503.03578​​
  • 代碼位址:​​https://github.com/tangjianpku/LINE​​​, 另外作者所在的組還釋出了一個圖架構​​GraphVite​​, 支援大規模的 embedding learning, 内置了多款圖算法.
  • 發表時間: 2015
  • 論文作者: Jian Tang, Meng Qu , Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei
  • 作者機關: Microsoft Research Asia + Peking University + University of Michigan

主要内容

文章介紹了 LINE 算法, 引入了兩個核心概念: first-order proximity (一階鄰近) 和 second-order proximity (二階鄰近). 其中一階鄰近描述的是直接相連的節點之間的關系, 而二階鄰近則指的是節點之間雖然不直接相連, 但是它們會有一些共同的鄰居. 在具體實作上, 為了描述二階鄰近, 作者用了兩個 Embedding Layer, 其中一個用來描述節點本身, 另一個用來描述節點作為其他節點的 context 時的情況. Loss 在設計時借鑒了 Word2Vec 中的 Negative Sampling. 此外, 通過 AliasMethod 來對邊進行采樣, AliasMethod 采樣方法的特點是它的時間複雜度為 , 權重越大的邊有更大的幾率被采樣到.

下圖描述了一階鄰近和二階鄰近:

LINE 圖嵌入算法介紹與源碼淺析

其中節點 6 和節點 7 是直接相連的 (一階鄰近), 它們在低維空間的距離應該是接近的; 另外節點 6 和節點 5 雖然不直接相連, 然後它們有共同的鄰居, 是以它們的低維特征表達也應該是接近的.

為了形式化的表達一階和二階鄰近, 作者分别它們倆進行模組化.

一階鄰近

其中一階鄰近表述如下:

對于每條無向邊 , 定義頂點 (vertex) 和

其中 為頂點

其中 為 Graph 中邊的集合, 為頂點 和

将 和

注意一階鄰近隻适用于無向圖, 而不能用于有向圖. 具體原因見下面我的想法.

插入我的一點想法:
  • 首先, 使用 Sigmoid 定義兩個節點之間的聯合機率, 輸入是兩個節點 embedding 的内積, 注意到 Sigmoid 是遞增函數, 那麼如果兩個向量的内積越大, 即兩個節點比較相似, 那麼 p 的機率就越大. 另外作者後面定義了經驗機率, 如果兩個節點之間的邊權越大, 表示兩個節點的聯系越緊密.
  • 對于一階鄰近隻适用于無向圖的問題, 是因為在計算時的公式是滿足對稱性的, 即交換和的位置, 結果是不變的; 但是對于的結果, 對有向圖來說結果會發生變化, 因為不一定等于; 這樣聯合機率的分布和經驗機率的分布是有差異的, 再去計算它們之間的距離可能學習不到正确的表達.
  • 另外需要注意的是, 使用 Sigmoid 計算出來的值不算分布, 畢竟經驗分布是可以歸一化的, 而

二階鄰近

二階鄰近可以作用于有向/無向/權重/無權圖. 二階鄰近認為, 如果節點 A 和節點 B 共享部分鄰居, 那麼它們之間也是相似的. 在這種情況下, 每個節點有兩種角色, 其中一個即節點自身, 而另一個角色是作為其他節點的 “context”, 即作為其他節點的上下文, 如果節點 A 和 B 的上下文分布相似, 那麼 A 和 B 也應該是相似的.

是以作者對節點 引入了兩個特征表達, 使用 表示它作為節點時的特征表達, 另外使用 表示它作為上下文 context 時的特征表達. 對于有向邊 , 節點 是作為節點

其中 為上下文節點的數量. 對每一個源節點 來說, 上式定義了它在上下文節點上的條件機率分布 . 此外, 經驗機率分布定義為:

其中 表示節點 指向的鄰居集合,

通過對 和 的學習, 最小化目标函數, 這樣就可以得到每個節點 的表達 .

模型優化以及邊采樣

文章提到, 優化 的代價比較大, 因為對每個節點都需要計算 . 為此, 作者借鑒 ​​​Word2Vec​​​ 中的 Negative Sampling, 對負樣本進行采樣. 是以最終對每一條邊 , 優化如下目标函數:

其中 為 sigmoid 函數, 第一項對正樣本進行模組化, 第二項描述負樣本, 表示負樣本的數量, 負樣本的采樣分布 , 其中 表示節點

文章采用 ASGD (Asynchronous Stochastic Gradient Algorithm) 來優化上式. 注意一階鄰近和二階鄰近均采用上式作為目标函數.

由于目标函數 和 中均含有邊權 , 如果邊權過大, 學習速率就需要進行調小, 以避免梯度爆炸, 然而學習速率過小對于那些邊權較小的邊是不利的. 為了處理這個問題, 作者采用 ​​​AliasMethod​​​ 算法進行邊的采樣, 該方法的時間複雜度為 , 對于那些邊權較大的邊, 有更大的機率被采樣到.

好吧, 論文介紹就到這吧, 下面看源碼. 理論介紹是一回事, 代碼實作又是另一回事 ????????????

LINE 算法源碼分析

代碼編譯

LINE 的 C++ 源碼位址在 ​​https://github.com/tangjianpku/LINE​​​, 我看的是 Linux 版本, 但我是在 MacOS 上編譯的. 編譯時需要 ​​GSL​​​ (GNU Scientific Library) 科學計算庫, 以産生随機數. 在 MacOS 使用 ​

​brew install gsl​

​​ 就能友善的安裝. 之後運作 ​

​train_youtube.sh​

​ 即可.

LINE 算法的核心實作主要在 ​

​line.cpp​

​​ 中, 是以抓大放小, 下面隻介紹 ​

​line.cpp​

​ 中的代碼. 另外如果有 Word2Vec 源碼閱讀經驗的話, 看 LINE 的源碼會有幫助, 畢竟 LINE 最後采用的是 Negative Sampling 來進行模型的優化.

Hash Table

這個不多介紹, 圖檔案讀入進來, 節點使用字元串的表示, 需要轉換為節點 id 的形式. 對于大規模的圖網絡, 肯定是需要用到 Hash 的. 代碼中實作的 ​

​InsertHashTable​

​​ 以及 ​

​SearchHashTable​

​ 考慮了哈希沖突的問題. 如圖:

LINE 圖嵌入算法介紹與源碼淺析

代碼如下:

// 節點使用 ClassVertex 表示, 包含名字和邊權 degree
struct ClassVertex {
  double degree;
  char *name;
};

void InsertHashTable(char *key, int value)
{
  int addr = Hash(key);
  while (vertex_hash_table[addr] != -1) addr = (addr + 1) % hash_table_size;
  vertex_hash_table[addr] = value;
}

int SearchHashTable(char *key)
{
  int addr = Hash(key);  // 擷取節點 id
  while (1)
  {
    if (vertex_hash_table[addr] == -1) return -1;
    // 在 addr 位置上查找節點, 還需要保證名字相同, 否則就查找下一個位置
    if (!strcmp(key, vertex[vertex_hash_table[addr]].name)) return vertex_hash_table[addr];
    addr = (addr + 1) % hash_table_size;
  }
  return -1;
}

檔案讀取 - 擷取邊的關系

在 ​

​ReadData()​

​​ 中實作對網絡檔案的讀取, 達到對節點個數以及邊的個數的統計, 使用 ​

​edge_source_id​

​​ 儲存所有源節點, ​

​edge_target_id​

​​ 儲存所有目标節點, ​

​edge_weight​

​ 儲存所有邊的權重.

edge_source_id = (int *)malloc(num_edges*sizeof(int));
edge_target_id = (int *)malloc(num_edges*sizeof(int));
edge_weight = (double *)malloc(num_edges*sizeof(double));

網絡檔案的格式是 ​

​name_v1 name_v2 weight​

​​, 讀取檔案的每一行, 并将節點名字映射為 hash id, 插入到 哈希表以及 ​

​edge_source_id​

​ 數組中:

vid = SearchHashTable(name_v1); // 現在哈希表中查找節點 name_v1, 找尋其 id
if (vid == -1) vid = AddVertex(name_v1); // 如果沒有找到 name_v1, 那麼就插入到 hash_table 中
vertex[vid].degree += weight;
edge_source_id[k] = vid;

對目标節點也做同樣的處理.

初始化 AliasTable

初始化 AliasTable, 以便後面進行邊的采樣. 關于 AliasMethod, 強推 ​​【數學】時間複雜度O(1)的離散采樣算法—— Alias method/别名采樣方法​​​ 這篇文章. 原來大緻是, 對于輸入的邊權分布 , 乘上 N 之後, 其中總有大于 1 的值, 也有小于 1 的值, 這些值的求和肯定等于 N. 如下圖原始邊權分布, 有很多矩陣塊, 這些矩陣塊的面積總和為 N. 現在要設計一種算法, 将大于面積大于 1 的矩陣塊的部分面積, 填補到面積小于 1 的矩陣塊上, 比如下圖中将矩陣 4 的面積分别填補到了矩陣塊 1 和 3 上, 将矩陣 2 的部分面積填充到矩陣塊 5 上. 這樣就得到了 AliasTable.

LINE 圖嵌入算法介紹與源碼淺析

那麼之後如何采樣呢? 需要擲兩次骰子 ????, 第一次投擲, 選擇 AliasTable 的第 i 個位置; 之後第二次投擲, 确定到底使用哪一個矩陣塊 (即哪條邊), 因為第二次投擲時, AliasTable 的第 i 個位置可能會有兩種顔色的矩陣塊 (比如第 0 個位置上, 有紅色 4 和黃色 1 的矩陣塊), 需要确定使用哪種顔色. 具體代碼就不貼了, 了解了 AliasTable 的原理, 代碼實作不難.

采樣邊

因為要投擲兩次骰子 ????, 是以 ​

​SampleAnEdge​

​ 函數需要傳入兩個随機數.

long long SampleAnEdge(double rand_value1, double rand_value2)
{
  long long k = (long long)num_edges * rand_value1;
  return rand_value2 < prob[k] ? k : alias[k];
}

Embedding Layer 初始化

為了實作二階鄰近, 每個節點都會有兩個特征表示, 其中一個為節點自身的表達 ​

​emb_vertex​

​​, 另一個是節點作為其他節點的上下文時的表達 ​

​emb_context​

​.

Negative Table 初始化

負樣本的采樣需要使用到 Negative Table, 采樣的機率分布服從 , 這就是說, 對于節點 ​​

​u​

​​ 來說, 其出度為 , 那麼其出現的機率為:

假設 Negative Table 的大小為 , 那麼節點

下面的代碼就是為了在 Negative Table 中填充節點 id 值, 對于出度較大的節點, 在 Negative Table 中出現的次數越多.

/* Sample negative vertex samples according to vertex degrees */
// NEG_SAMPLING_POWER 定義為 0.75
void InitNegTable()
{
  double sum = 0, cur_sum = 0, por = 0;
  int vid = 0;
  neg_table = (int *)malloc(neg_table_size * sizeof(int));
  for (int k = 0; k != num_vertices; k++) sum += pow(vertex[k].degree, NEG_SAMPLING_POWER);
  for (int k = 0; k != neg_table_size; k++)
  {
    if ((double)(k + 1) / neg_table_size > por)
    {
      cur_sum += pow(vertex[vid].degree, NEG_SAMPLING_POWER);
      por = cur_sum / sum;
      vid++;
    }
    neg_table[k] = vid - 1;
  }
}

可以看下圖對上面代碼進行了解:

LINE 圖嵌入算法介紹與源碼淺析

Sigmoid Table 的使用

由于 Sigmoid 中含有指數函數, 計算起來相對耗時, 可以使用 Sigmoid Table 提前算好一些值, 後面隻需查詢即可. 假設下面代碼中, 使用 來表示 ​​

​SIGMOID_BOUND​

​​, 使用 來表示 ​​

​sigmoid_table_size​

​​, 那麼計算 範圍内的值的 Sigmoid 結果, 需要先對這個區間進行離散化, 長度為 , 那麼給定索引 , 得到對應的輸入值

那麼給定實數 , 計算它在 Sigmoid Table 中的索引為:

/* Fastly compute sigmoid function */
void InitSigmoidTable()
{
  real x;
  sigmoid_table = (real *)malloc((sigmoid_table_size + 1) * sizeof(real));
  for (int k = 0; k != sigmoid_table_size; k++)
  {
    x = 2.0 * SIGMOID_BOUND * k / sigmoid_table_size - SIGMOID_BOUND;
    sigmoid_table[k] = 1 / (1 + exp(-x));
  }
}

real FastSigmoid(real x)
{
  if (x > SIGMOID_BOUND) return 1;
  else if (x < -SIGMOID_BOUND) return 0;
  int k = (x + SIGMOID_BOUND) * sigmoid_table_size / SIGMOID_BOUND / 2;
  return sigmoid_table[k];
}

負樣本采用随機數

由于要在 Negative Table 中采樣負樣本, 需要随機産生索引:

/* Fastly generate a random integer */
int Rand(unsigned long long &seed)
{
  seed = seed * 25214903917 + 11;
  return (seed >> 16) % neg_table_size;
}

LINE 模型訓練以及梯度更新

由于 LINE 使用 ASGD 對梯度進行更新, 代碼中使用多線程來進行實作, 是以核心代碼在 ​

​TrainLINEThread​

​ 中.

下面代碼中使用 ​

​count​

​​ 對樣本進行計數, 第二個 ​

​if​

​​ 用來對學習速率進行調整, 采用 Learning Rate Decay 的思路. 其中 ​

​rho​

​ 表示學習速率.

//judge for exit
    if (count > total_samples / num_threads + 2) break;

    if (count - last_count > 10000)
    {
      current_sample_count += count - last_count;
      last_count = count;
      printf("%cRho: %f  Progress: %.3lf%%", 13, rho, (real)current_sample_count / (real)(total_samples + 1) * 100);
      fflush(stdout);
      rho = init_rho * (1 - current_sample_count / (real)(total_samples + 1));
      if (rho < init_rho * 0.0001) rho = init_rho * 0.0001;
    }

核心算法:

// 使用 AliasMethod 進行邊的采樣, 得到源節點 u, 正樣本 v 
    curedge = SampleAnEdge(gsl_rng_uniform(gsl_r), gsl_rng_uniform(gsl_r));
    u = edge_source_id[curedge];
    v = edge_target_id[curedge];

    // dim 為 embedding 的大小, lu 表示 u 的 embedding 的起始位置, 因為矩陣使用數組來
    // 表示, embedding 矩陣大小為 [N, emb], 表示成一維數組的大小為 N*emb, 要找到 u 所
    // 代表的 emb, 需要用索引值 u 乘上 dim
    lu = u * dim;
    for (int c = 0; c != dim; c++) vec_error[c] = 0;

    // NEGATIVE SAMPLING
    for (int d = 0; d != num_negative + 1; d++)
    {
      if (d == 0)
      {
        target = v;
        label = 1;
      }
      else
      {
        target = neg_table[Rand(seed)]; // 從 Negative Table 采樣負樣本
        label = 0;
      }
      lv = target * dim;
      // 如果使用一階鄰近, 那麼 Update 的輸入均為 emb_vertex
      if (order == 1) Update(&emb_vertex[lu], &emb_vertex[lv], vec_error, label);
      // 如果使用二階鄰近, 那麼 Update 的輸入分别為 emb_vertex 以及 emb_context
      // emb_vertex 是節點作為自身所代表的 embedding,
      // emb_context 是節點作為其他節點的 context 所代表的 embedding
      if (order == 2) Update(&emb_vertex[lu], &emb_context[lv], vec_error, label);
    }
    // embedding 更新, 這個要根據對 loss 求導來得到, 具體見下面的講解
    for (int c = 0; c != dim; c++) emb_vertex[c + lu] += vec_error[c];

代碼中的思路主要是, 先使用 AliasMethod 對邊進行采樣, 得到 邊, 進而獲得源節點 和正樣本 , 之後采樣 ​​

​num_negative​

​ 個負樣本, 從 Negative Table 中進行采樣. 得到節點的 id 後, 然後擷取它們分别對應的 embedding, 再根據 Negative Sampling 的目标函數進行 loss 的計算 (loss 沒有顯式計算出來) 和梯度的更新, 最後再更新 embedding.

SGD 的計算實作在 ​

​Update​

​ 函數中:

/* Update embeddings */
void Update(real *vec_u, real *vec_v, real *vec_error, int label)
{
  real x = 0, g;
  for (int c = 0; c != dim; c++) x += vec_u[c] * vec_v[c];
  g = (label - FastSigmoid(x)) * rho;
  for (int c = 0; c != dim; c++) vec_error[c] += g * vec_v[c];
  for (int c = 0; c != dim; c++) vec_v[c] += g * vec_u[c];
}

​

​vec_u​

​​ 為源節點的 embeddng, 而 ​

​vec_v​

​ 為目标節點的 embedding. 代碼用公式來表示, 其實就簡單多了. 首先, Negative Sampling 的目标函數為:

先來看對 關于 和 的求導 (之是以用 , 考慮到正負樣本的問題).

代碼中的

為了更新 , 需要對 的結果進行累加, 是以需要使用 ​​

​vec_error​

​​ 對誤差進行累計.

而要更新 , 有:

代碼總結

資料總結

  • Word2Vec 論文:​​Word2Vec​​
  • AliasMethod 的詳細介紹:​​【數學】時間複雜度O(1)的離散采樣算法—— Alias method/别名采樣方法​​
  • ​​LINE:Large-scale Information Network Embedding閱讀筆記​​: 評論區非常熱鬧和精彩, 是關于 LINE 算法更為深入的解讀
GraphEmbedding 圖嵌入 Line 低維空間表示 圖學習
上一篇: path css 發光,css3的clip-path屬性介紹
下一篇: Kettle Spoon入門學習

繼續閱讀