華為聯合LSE提出KONG：有序近鄰圖的核函數

選自arXiv

作者：Moez Draief, Konstantin Kutzkov, Kevin Scaman, Milan Vojnovic

機器之心編譯

參與：吳昕

本論文由華為諾亞方舟實驗室聯合倫敦政治經濟學院合作完成，為 NeurIPS 2018 的合作論文。在此論文中，研究員針對近鄰有序的、節點和邊有標籤的圖，提出了新穎的圖核函數。

圖是對結構化數據的獨特表示，從在線社交網路的社區檢測到蛋白質結構預測，圖在機器學習及其相關領域有著極大的應用。所以，基於圖結構實現學習任務能夠吸引研究社區的關注也就不令人驚訝了。圖核函數（Graph kernel）是圖分類的標準工具。給定帶有節點和邊屬性的大型圖合集，我們感興趣的是學習一種能夠最好地捕捉任意兩張圖之間相似性的核函數. 這種圖核函數可用於支持向量機這樣的標準核方法進行圖分類。

圖相似性是一個定義廣泛的概念，也因此有許多帶有不同特性的不同圖核函數被提出。先前工作主要是研究不同圖類別的圖核函數，也就是沒有節點或者邊緣屬性的簡單不加權圖、帶有離散節點和邊標籤的圖、帶有真值向量和部分標籤這樣更複雜屬性的圖。對圖的展開而言，鄰近節點的排序（order）可作為圖類別的參考。具體樣本包括描述用戶瀏覽模式的圖，也包含社交網路、產品購買與瀏覽、推薦系統中的點擊率、合著關係網路等這樣的進化網路。

邊中的排序（order）對原始數據中的結構非常有指示作用。據我們所知，現有的圖核函數並不涉及這一方面。我們提出了一種邊與鄰近節點遵循一定排序的圖核函數框架。我們提出的這一演算法框架 KONG，它表示面向有序近鄰圖的核函數（Kernels for Ordered-Neighborhood Graphs），這一框架還可以擴展到大規模圖和圖集合的高效演算法。

其核心思路是：（a) 使用一種樹遍歷方法通過特徵串（string）表示每個節點近鄰。（b）基於每個節點特徵串的 k-gram 頻率向量，在沒有顯性存儲特徵串的情況下對圖 feature map 進行高效計算。後者使得使用 sketching 技術逼近各種核函數的顯性 feature map 成為了可能。

圖 1:一個有序近鄰圖的示例：近鄰排序是按照字母來排的

本文貢獻如下：

據我們所知，這是首個聚焦且正式定義有序節點近鄰圖核函數的研究。它在串核函數（string kernel）上進行拓展，我們展示且正式分析了一系列用於不同問題的圖核函數。KONG 框架展示了與兩個參數有關的演算法：圖 N 的總數量和邊 M 的總數量。我們提出的方法能夠計算每個圖的顯性 feature map，使得線性 SVM 能用於圖分類，從而避免 O(N2 ) 大小核矩陣的計算。利用前沿的 sketching 技術，可以實時計算帶有 m 個邊的圖的顯性 feature map 近似值。我們也擴展了子線性空間 o(M)，並介紹了如何使用從圖流中學習。

相比使用多項式和餘弦核函數計算的子圖標籤分布，我們的方法可為未排序領域的一般標記圖帶來全新圖核。我們認為，該方法可看作一種對 Weisfeiler-Lehman 節點標註核函數有效的平滑演算法。在真實圖上的實驗評估顯示，我們提出的核方法可以與頂尖的方法相媲美，使用密集的 feature map 在一些基準數據集上能夠達到更好的準確率。

現在的方法可看作一種學習緊緻圖表示的有效演算法。這種方法主要聚焦於學習卷積圖核函數的顯性 feature map。然而，我們的演算法學習到的向量嵌入可以被邏輯回歸、決策樹和神經網路以及無監督方法使用。

論文：KONG: Kernels for ordered-neighborhood graphs

論文地址：https://arxiv.org/abs/1805.10014

摘要：本文提出了一種帶有節點和邊標籤圖的面向有序近鄰圖的全新圖核函數。有序近鄰即相鄰節點有序排列。有序近鄰圖是展開圖的自然數據表示，在展開圖中，邊隨著時間的推移而產生，進而導致了順序。結合卷積子圖核函數和串核函數（string kernel），我們設計了一種新的可擴展演算法，以使用 sketching 技術生成顯式圖 feature map。我們獲得了所提出方法的近似準確率與計算複雜度的精準界限，證明了它們在真實數據集上的可用性。我們的實驗還證明，近鄰排序會產生更多的信息特徵。對於一般圖的特定案例（即非有序近鄰圖）來說，新的圖核函數會為比較圖之間的標籤分布產生高效又簡單的演算法。

演算法

該提出的演算法基於以下幾個關鍵點：a）使用樹遍歷方法用串 Sv 表示每個節點 V 的近鄰，b）使用 sketching 以不需要存儲串 Sv 的方式逼近其 k-gram 頻率向量。

實驗

在此章節中，我們展示了該演算法的分類準確率與計算速度，並與其他基於核的演算法在一組真實圖數據集上做了對比。首先，我們展示了對沒有層級節點近鄰的一般圖的評估，這證明了相比於當前基於核函數的方法，我們的演算法取得了可媲美的效果，甚至在一些情況下有更好的分類準確率。而後，我們展示了對帶有層級的近鄰圖的評估，證明了計入近鄰層級數能帶來更高的分類準確率，以及更好的可延展性。

表 1:一般標記圖的分類準確率（1-gram 示例）

表 2:帶有層級近鄰圖的不同方法準確率與速度的對比，我們使用 K-k 注釋表示使用 k-grams 的 KONG。時間列展示了明確的圖計算時間和 SVM 分類時間。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！