2020 圖算法工程師面試基礎、要點

來源：圖與推薦

本文約2700字，建議閱讀5分鐘。

為你總結面試必備的知識要點，助你面試成功。

這段時間面試連連，幾輪下來的感受就是，好點兒的公司對細節摳的很細，希望求職者能夠對使用的算法以及這個算法的其它觸類旁通的領域都能夠有系統的理解。

本文原創作者知乎連結為：

https://www.zhihu.com/people/he-he-he-he-77-19-21

GNN 是近年來 AI 領域最熱門的話題之一，但很多人都忽視了基礎。

本文參照之前的：我們如何通過圖算法來幫助提高機器學習算法的性能？以及【圖算法：概覽（https://zhuanlan.zhihu.com/p/64984300）】以及之前劉教授出的GNN系統介紹的書的基礎知識部分進行總結。

圖是一種數據結構，它對一組對象（節點)及其關係(邊)進行建模。近年來，利用機器學習分析圖形的研究越來越多，由於圖的巨大表現力，即圖可以作為包括社會科學（社會網絡）、自然科學（物理系統、蛋白質-蛋白質相互作用網絡、知識圖譜）在內的各個領域的大量系統的外延。圖作為機器學習的一種獨特的非歐幾裡得數據結構，在 nodes 層面的分析中引起了人們的注意——包括了 node prediction、link prediction 和圖聚類。圖神經網絡（GNNs）是一種基於深度學習的在圖域上工作的方法，由於其令人信服的性能和高可解釋性，GNN 近年來已成為一種廣泛應用的圖數據分析方法。在下面的段落中，我們將說明 GNN 的基本動機。

首先，GNNs 是由卷積神經網絡(CNNs) LeCun 等人驅動的。CNN 能夠提取和組合高解析度特徵的多尺度局部空間特徵，這導致了幾乎所有機器學習領域的突破和深度學習的革命。當我們深入到 CNN 和計算機視覺應用時，我們發現CNN 的成功之處在於：局部連接、權值共享和多層的使用。這些對於解決圖域問題也是非常重要的，因為：

圖是最典型的局部連接結構；

與傳統的譜圖理論相比，權值共享降低了計算成本；

多層結構（這裡的意思是不同尺寸的卷積核）是處理不同層次模式的關鍵，它捕捉了不同大小的特徵。

另一個動機來自圖嵌入，它學習在低維向量中表示圖節點、邊或子圖。在圖分析中，傳統的機器學習方法通常依賴於手工設計的特性，受到其不靈活和高成本的限制， 遵循表徵學習的思想和詞嵌入的成功，deepwalk，被認為是第一種基於表示學習的圖形嵌入方法，將SkipGram模型應用於生成的隨機遊走，類似的方法，如node2vec、LINE和TADW也取得了突破，然而，這些方法有兩個嚴重的缺點：

首先，編碼器中的節點之間沒有共享參數，這導致了計算效率低下，因為它意味著參數的數量隨著節點的數量線性增長。

第二，直接嵌入方法缺乏泛化能力，這意味著它們難以處理動態圖或被推廣到新圖。

關於GNN的部分暫時介紹到這邊,下面主要總結一下基礎知識：

圖論

圖通常用 G=(V,E) 來表示， 其中 V 是頂點集，E 是邊集，邊 e 有兩個頂點 u 和 v，被稱為 u 和 v 通過 e 連接。在這種情況下，u 被稱為 v 的鄰居，或者換句話說，這兩個頂點是相鄰的，請注意，邊可以是有向的，也可以是無向的， 如果所有邊都是有向圖，則圖稱為有向圖，如果所有邊都是無向圖，則稱為無向圖。V 的度（degree），用 d(v) 表示，是與 v 連接的邊數。

常見的graph的幾種分類：

有向無向；

有權無權；

同構異構；

當然還有有環無環等分類方式，這裡列出常見的分類方法，需要注意的是，graph 的這幾種分類之間是相互重疊而不是互斥的。詳細可見【圖算法：概覽

（https://zhuanlan.zhihu.com/p/64984300）】

關於基本的圖特徵的構造

total degree：即與節點 V 相鄰節點的數量，稱為節點 V 的度；

degree centrality：度中心性，即標準化的度，是使用節點 V 的度除以全圖節點的數量得到的用以衡量節點度的相對大小，類似於結構化數據中做 0-1 標準化的操作；

number of triangles：節點所在三角形的數量，即三個節點互相連通則稱為一個三角形；

local clustering score：局部聚類得分，2*v 節點所在三角形的數量/(節點 V 的度的平方-節點 v 的度)，用於衡量節點 V 的兩個鄰節點互為鄰居的概率；

Eigenvector Centrality：特徵向量中心度（詳細可見：所謂特徵向量中心度 http://blog.sina.com.cn/s/blog_4c9dc2a10101b4y3.html）

pagerank：特徵向量中心度的一種變體，相對前者，pagerank 要出名多了。（詳細可見：機器學習經典算法之PageRankhttps://www.cnblogs.com/jpcflyer/p/11180263.html）。pagerank能夠實現的功能就是，「如果你的朋友很famous，那麼你也會famous」。

比如說脈脈這個社交軟體，它計算的就是個人在職場的影響力。如果你的工作關係是李開復、江南春這樣的名人，那麼你的職場影響力一定會很高。反之，如果你是個學生，在職場上被鏈入的關係比較少的話，職場影響力就會比較低。

同樣，如果你想要看一個公司的經營能力，也可以看這家公司都和哪些公司有合作。如果它合作的都是世界 500 強企業，那麼這個公司在行業內一定是領導者，如果這個公司的客戶都是小客戶，即使數量比較多，業內影響力也不一定大。

除非像淘寶一樣，有海量的中小客戶，最後大客戶也會找上門來尋求合作。所以權重高的節點，往往會有一些權重同樣很高的節點在進行合作。

betweenness centrality：中介中心性，中介中心性指的是一個結點擔任其它兩個結點之間最短路的橋梁的次數。一個結點充當「中介」的次數越高，它的中介中心度就越大。如果要考慮標準化的問題，可以用一個結點承擔最短路橋梁的次數除以所有的路徑數量。

closeness centrality：接近中心性，接近中心性需要考量每個結點到其它結點的最短路徑的平均長度。也就是說，對於一個結點而言，它距離其它結點越近，那麼它的中心度越高。一般來說，那種需要讓儘可能多的人使用的設施，它的接近中心度一般是比較高的。

最後是圖的代數表示

1. 領接矩陣A

對於一個簡單的圖 G=（V，E），具有 n 個頂點 V；可以用鄰接矩陣來描述圖：

顯然，當 G 是無向圖（實現的時候常當作雙向圖）時，這種矩陣是對稱矩陣，下圖中無向圖 G5 和有向圖 G6 的鄰接矩陣分別為 A1 和 A2。

注意區分有向和無向，如果帶權，則矩陣中的0-1就會被edge的權重所替代了。

2. 度矩陣D

一般來說，有向圖要分出度的度矩陣和入度的度矩陣，但是很多時候為了方便，我們把有向圖當作無向圖來做，因此常常可以看到，無論是有向還是無向，都是一樣計算所有的與節點相連的 edge 的權重之和，注意是權重不是直接計算節點，因為有權圖表示不服；（但是應該一些場景的應用下還是會劃分為出度和入度的度矩陣的）

3. 拉普拉斯矩陣

這裡有個比較直觀的例子：

給定一個graph：

其領接矩陣：

可以看出這是一個無向無權的graph；

則拉普拉斯矩陣為：

對稱歸一化拉普拉斯：

直接看上面的這個公式更好理解一些，可以看到對稱歸一化之後，對角元素全為1，之所以進行對稱歸一化主要是因為對稱歸一化之後的拉普拉斯矩陣有很多好的性質。

4. 隨機遊走標準化拉普拉斯矩陣

5. 關聯矩陣

關聯矩陣即用一個矩陣來表示各個點和每條邊之間的關係。

對於一個無向圖 G，p 為頂點的個數，q 為邊數。bij 表示在關聯矩陣中點 i 和邊 j 之間的關係。若點 i 和邊 j 之間是連著的，則 bij = 1. 反之，則 bij = 0.

編輯：文婧