[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN
做過聚類的小夥伴通常都會有一個頭大的問題，就是“如何確定距離”。這個距離是用於確定兩個節點是否有連線的，它為什麼那麼讓人頭大呢？因為距離閾值設定小了，很多linkage就被斷開了，導致較低的recall；而設大了，就有大量錯誤的linkage，precision就沒法保證了。
本次介紹的工作主要就是為了解決這個問題，這是CVPR 2019的一個文章“Linkage Based Face Clustering via Graph Convolution Network”，就是透過利用GCN來識別graph的linkage關係的！連結如下：
下面主要從以下幾個方面來介紹這篇文章：
簡介
方法介紹
Framework overview
Instance Pivot Subgraph （IPS） &GCN
結果分析
Pros & Cons
1。 簡介——人臉聚類存在的問題，以及文章的解決方法
![[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN](https://img.beesask.com/upload/website_attach/UphkTkVzJrftE_x9q+bjCsp_U85Gwi-p7BLWutDuR2geD_EZVuT98mwsE9kq7_pAtE-uI2Okv8j=oiUGqqbuB4H+E.jpeg)
人臉聚類中一個主要的難題——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
![[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN](https://img.beesask.com/upload/website_attach/XHQ0W8nJVM8SxApzrIk-NV07WWBJYS9b8iH0xyyiLEIPldTk8zs+9VIgCmwcWTgMWj=jDqn3BWkywFnirrklCUttN.jpeg)
該文章提出的方法主要包括以下幾個步驟：
（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的1\2\3- hop neighbors；
（b）接著，對節點特徵做normalization，也就是每個節點的feature都減去pivot的feature，這步可以理解為以pivot為中心，觀察其附近節點的變化（context）；
（這點非常重要，相當於定義了圖/類的中心，後面相當於對節點進行二分類，使得識別的難度大大降低。）
（c）對子圖中的每個節點，連線其u近鄰。
（這一步也就得到了GCN需要輸入的鄰接矩陣，可以直接應用GCN對子圖的節點進行分類了。）
![[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN](https://img.beesask.com/upload/website_attach/bJ=4Q5dVMv1PZh94G69o+cHk2Lzvilc3m=f_3NB7ZspqXEEKyPAkeU+t_k73zDvgOB4W3NOKZEcIYgrvGL9wfYsrh.jpeg)
3。 實驗結果分析
（1）方法比較，文章提出的方法，可見對於比heuristic的方法有比較明顯的提升的。
![[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN](https://img.beesask.com/upload/website_attach/_JS=ItuMMvGPca4zGGamcf5b3+vF-Uf5e=1T1vgTmGPzyaZzyDORPyQB+gSNSATu2+OwgsgFmIVPPZ2_GvaabbFHj.jpeg)
（2）聚類中常見的Singleton對效果的影響。
![[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN](https://img.beesask.com/upload/website_attach/8LbArDoLqCKIUIst61GfU6F4u8TzKi6DEyFP-iVbAshPtUsF=lVCTkVj6wmX+zPDENfk-xuSFwYI7Duw6=G_-+g_w.jpeg)
（3）Multi-view clustering
該方法可以直接應用於Multi-view clustering上，可見也是有不錯的提升的。
文章不僅驗證了該方法在同質資料上的提升，還給出了異質資料上的結果，這也是不錯的一點。
![[論文閱讀] 人臉聚類——Linkage Based Face Clustering via GCN](https://img.beesask.com/upload/website_attach/zeASi_bEhsZDs0a2cWXY53KZgj5qjshKau6SynHK3FCDK_sI2AhtiMDr3q-seBrKyDF-0rrW4NydvHY5cfXO4H9m4.jpeg)
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的工作會陸續出來，坐等！