做過聚類的小夥伴通常都會有一個頭大的問題，就是「如何確定距離」。這個距離是用於確定兩個節點是否有連接的，它為什麼那麼讓人頭大呢？因為距離閾值設置小了，很多linkage就被斷開了，導致較低的recall；而設大了，就有大量錯誤的linkage，precision就沒法保證了。

本次介紹的工作主要就是為瞭解決這個問題，這是CVPR 2019的一個文章「Linkage Based Face Clustering via Graph Convolution Network」，就是通過利用GCN來識別graph的linkage關係的！鏈接如下：

Linkage Based Face Clustering via Graph Convolution Network?

arxiv.org

下面主要從以下幾個方面來介紹這篇文章：

  1. 簡介
  2. 方法介紹
    1. Framework overview
    2. Instance Pivot Subgraph (IPS) &　GCN
  3. 結果分析
  4. Pros & Cons

1. 簡介——人臉聚類存在的問題，以及文章的解決方法

人臉聚類中一個主要的難題——link的判斷，在figure 1給了很清晰的闡述：

（a）文中focus的問題是要判斷兩個節點i和j是否有link。

（b）樸素的想法是判斷i、j之間的距離是否小於一定的閾值，如果不是的話，則兩個節點之間不會有link。

（c）ARO方法通過人為設定的規則來確定是否應該有link，這種手工設計的方式還是不夠準確。

（d）文中提出的方法是通過GCN獲取i、j 的neighbor信息，並學習兩者之間是否有link。

這種方法不需要依賴於一個全局的閾值如（a）或者人為設定的局部閾值如（c），可以讓演算法自己來觀察當前的context，從而確定結果，這會使得linkage更加robust。

2. 方法介紹

（1）Framework Overview

該文章提出的方法主要包括以下幾個步驟：

(a) 首先，是通過CNN來提取feature，這時候我們可以看到，feature雖然是有分開大致的group，但是對於一些比較困難的類來說，feature會分佈得很散（這個對應於實際情況中的遮擋、模糊等情況）；另外常見的困難情況，圖中沒有畫出來——有些類別之間會非常的相似，有一些overlap的部分。

(b) IPS：對於每個樣本點，構建其對應的子圖，文中稱為Instance Pivot Subgraph （IPS）。對於這一步我們可以看做是對每個樣本找出它的n-hop neighbor，為了給後面的節點分類提供context信息。

(c) Node Classification：把每個子圖送進GCN，並判斷出哪個樣本與子圖中的pivot是屬於同類的。這個是GCN常見的一個用途——分類，用得挺到位的。

(d) 連接該有的link，並找出其中的連通圖，這樣就得到聚類的結果了！

（2）Instance Pivot Subgraph （IPS）& GCN Node Classification

IPS+GCN是該文章的重點模塊。

IPS的建立方式有一下幾個步驟，如下圖：

  • （a）首先，對於pivot node找出其子圖，文中設定的子圖節點包括pivot的123- hop neighbors；
  • （b）接著，對節點特徵做normalization，也就是每個節點的feature都減去pivot的feature，這步可以理解為以pivot為中心，觀察其附近節點的變化（context）；
    • （這點非常重要，相當於定義了圖/類的中心，後面相當於對節點進行二分類，使得識別的難度大大降低。）
  • （c）對子圖中的每個節點，連接其u近鄰。
    • （這一步也就得到了GCN需要輸入的鄰接矩陣，可以直接應用GCN對子圖的節點進行分類了。）

3. 實驗結果分析

（1）方法比較，文章提出的方法，可見對於比heuristic的方法有比較明顯的提升的。

（2）聚類中常見的Singleton對效果的影響。

（3）Multi-view clustering

該方法可以直接應用於Multi-view clustering上，可見也是有不錯的提升的。

文章不僅驗證了該方法在同質數據上的提升，還給出了異質數據上的結果，這也是不錯的一點。

4. 總結

Pros:

（1）用GCN來解決Clustering中hard core的linkage問題，方法比較新穎——GCN中利用到了數據的局部信息，能夠更準確地判斷節點之間的關係；

（2）構建IPS的想法很好，巧妙地利用了GCN做節點分類的特性，並且使用Pivot Normalization很好地定義了節點的主次關係，能更好地進行分類。

Cons:

（1）在scalability和efficiency方面尚有欠缺，文中對於每個樣本都會建立一個IPS，並在上面應用GCN，雖然使用的GCN計算量不大，但畢竟在大規模數據上還是喫不消的，這個方面還是有比較大的擴展空間；

（2）看到文章中提到Singleton的問題時，我是挺期待作者能描述一下他們是如何把這些singleton歸類的，畢竟在實際問題下，這種情況實在是太太太常見了！

據我所知，近期還有不少GCN + Clustering的工作會陸續出來，坐等！

推薦閱讀：

相關文章