為什么要可視化圖 大規模圖可視化攻略方案

如果你需要可視化一個大規模的圖網絡，而你嘗試了各種各樣的工具，卻只畫了一個小毛球就耗盡了你的 RAM，這時候你要怎么辦？我的工作常常需要可視化大規模圖（上億的節點），嘗試了非常多的工具和方法。但是，我卻沒有發現有人提供實用的攻略，于是，我決定根據自己的經驗寫一篇攻略。

為什么要可視化圖

發現尋找的目標

通常，我們會將節點和邊的集合作為輸入，然后基于數據可以計算出一些統計信息，但是這不足以從結構中獲得想法。好的可視化可以幫助我們清晰的發現圖中的一些簇、 bridges 或者是點云，還有一些其他的模式。

便于解釋

很明顯，數據的可視化用于表示，這是一個展示工作成果的好方法。例如，如果你解決了一個聚類問題，你可以用不同的顏色表示不同的標簽進行可視化，展示它們是如何連接的。

獲得特征

盡管大多數圖可視化工具都是為制作一些圖片而創建的，但它們也很適合作為降維工具。以鄰接矩陣表示的圖是高維空間中的數據。繪制時，我們得到每個頂點的兩個（通常）坐標。這些坐標也可以用作特征。這個空間中頂點之間的緊密性意味著相似性。

大規模圖的問題

我將用大約 10K 節點和邊的大圖來表示。小規模的圖，通過幾分鐘搜索到的工具基本上都可以解決。大規模圖的難點在哪里呢？主要有兩個問題：可讀性和速度。通常，大規模圖的可視化看起來會非?；靵y，因為圖中有太多對象。此外，圖可視化算法的算法復雜度很高：邊或者頂點數目的二階或三階依賴。即使只看一次結果，也要很久才能找到更好的參數。

已有的研究

Helen Gibson， Joe Faith and Paul Vickers： “A survey of two-dimensional graph layout techniques for information visualization”

本文介紹了有哪些圖可視化方法存在，這些方法是如何工作的。文中將各種算法整理成了表，很清晰。我在這篇文章中也有用到了該文中的一些圖表。

Oh-Hyun Kwon， Tarik Crnovrsanin and Kwan-Liu Ma “What Would a Graph Look Like in This Layout？ A Machine Learning Approach to Large Graph Visualization”

這篇文章的工程量很大。研究人員嘗試了所有可能的算法，然后可視化出來，手工評估相似度。之后，他們擬合模型來預測圖在 layout 中是什么樣子。我也用了一些這篇文章的圖片。

理論部分

Layout 是一種將坐標映射到每個節點的方法。通常，這是指 2D 平面上的坐標。

什么是好的 Layout

很容易評價一個東西看起來是好還是壞，但是很難制定機器評估好壞的標準。為了得到所謂的“好的” layout，可以使用以下這些指標：

1. Minimum edges intersection（最小邊交）

很容易理解，太多的交叉會讓圖看起來很凌亂。

2. 相鄰的節點彼此靠近

邏輯相連的頂點應該彼此靠近，通過定義，它們代表了圖中存在的主要信息。

3. 社區聚類

如果一些節點之間的連接比與其他節點之間的連接頻率更高，那么它們看起來像密集的云。

4. 最小的重疊邊和節點

這也是很明顯的，如果我們不能確定是一個或者幾個節點，那么該圖可視化的可讀性就很差了。

Layout 的類別

同一個圖在不同 layout 上的呈現。

我考慮著重介紹三種比較重要的 Layout，layout 的分類方法有很多，下面這種分類足以涵蓋所有可能的類型。

力導向和基于能量

降維

基于節點特征

力導向

這一類方法是基于物理系統仿真的。頂點表示為相互排斥的帶電粒子，邊被視為彈性線。這些方法試圖建立這個系統的動力學模型或找到最小能量。這些圖通常會比較好的反應圖的拓撲結構，但是計算非常復雜，需要調節非常多參數。

該方法的重要成員包括 Force Atlas，Fruchterman-Reingold，Kamada Kawaii and OpenOrd。最后一種會使用一些優化方法來減少計算量，比如削減長邊，但是作為副作用，會讓圖更加聚集。

降維

一個圖可以用一個 N x N 的鄰接矩陣來表示，N 代表節點的數量。該矩陣同樣可以看作是 N 維空間中的 N 個對象。這種表示允許我們使用通用的降維方法，比如 PCA、UMAP、tSNE 等等。另一種途徑就是計算節點之間的理論距離，并在低維空間中保持該比例。

基于特征

通常，圖數據都和現實生活中的對象相關聯。因此，頂點和邊會有自己的特征。因此我們可以用這些特征來表示它們。我們可以利用上面講到的降維方法，像處理表數據一樣處理節點的特征，或者直接繪制節點特征對的散點圖。值得一提的是 Hive Plot，因為它和其他的方法都不同。在 Hive Plot 中，節點與多個徑向軸對齊，邊是它們之間的曲線。

大規模圖可視化工具

雖然圖可視化是一個老生常談的問題，但是支持大規模圖可視化的工具仍然捉襟見肘。其中有很多都被它們的開發者遺棄了。并且其中有很多都有自己明顯的缺陷。我只介紹這些工具中值得被提及并且支持大規模圖的，這樣可以幫助大家快速尋找到一個靠譜的工具，并且它還工作的很好。

GraphViz

2011年以前的比特幣交易圖

有些時候，調參非常困難

這是一款 old-school CLI 工具，它有自己的圖定義語言，叫做“dot”。這是一個有幾個 layouts 的包。針對大規模圖，它有 sfdp layout，來自于力導向家族。該工具的優點和缺點一樣：它從命令行運行。它對自動化很有用，但是沒有互動性的調參非常困難。你根本不知道你自己會等多久才能得到最后的結果，也不知道是否是需要停止它，并使用其他的參數重新開始。

graphviz.org

Gephi

Gephi 圖界面

來自 iMDB 的 13K 的電影推薦系統的圖

這是我知道的最好的圖可視化工具。它有 GUI，包含一些 layouts 和很多圖分析工具。還有很多社區貢獻的插件。例如我最喜歡的 layout，“Multigravity Force-Atlas 2” 或者 sigma.js 傳播工具，并且提供交互式的網頁端頁面。在 Gephi 中，可以根據節點和邊的特征設置顏色。

但是 Gephi 仍然被開發者拋棄了。它還有一點老式的 GUI 和一些簡單的特征。

gephi.org

igraph

音樂推薦圖

我需要向這個通用圖分析的工具致敬。其中最令人印象深刻的圖可視化是由 igraph 的一位作者制作的。igraph 的缺點對于 python API 來說是糟糕的文檔，但是源代碼是可讀的并且注釋良好。

igraph.org

LargeViz

最大的比特幣集群，里面有幾千萬個節點（交易和地址）

當你需要繪制一個巨大的圖時，它將是偉大的救世主。LargeViz 是一種降維工具，不僅可以用于圖，還可以用于任意表數據。它從命令行運行，工作速度快，占用較少的內存。

arxiv.org/abs/1602.00370

github.com/lferry007/LargeVis

Graphistry

一周內可能被黑客攻擊的地址以及交易

直觀并且美觀的界面，但是很有限

該工具是這篇攻略中唯一需要付費的。Graphistry 是一種服務，直接輸入數據，并進行所有計算，只需要在客戶端瀏覽器查看漂亮的圖片。Graphistry 出了具有合理的默認參數，良好的配色方案和稍好的交互性之外，其他特性與Gephi 相比并沒有太大的改進。它只提供一個力定向 layout 并且還具有800K個節點或邊的限制。

www.graphistry.com

Graph Embeddings

也有一種方法可以解決瘋狂的尺寸問題。從大約一百萬個頂點開始，只需要合理地查看頂點密度，而不需要繪制邊和特定的頂點。因為沒有人能在這樣的圖上辨認出單個的物體。此外，大多數用于圖可視化的算法將在這樣的大小上工作很多小時，甚至幾天。如果我們稍微改變一下方法，這個問題就可以解決。有很多方法可以得到反映圖頂點特征的固定大小表示。在得到這樣的表示之后，你唯一需要做的就是把維數降到2，以便得到一張圖片。

Node2Vec

Node2Vec + UMAP

這是 word2vec 在圖的改編。圖中使用隨機游動而不是單詞序列。因此，該方法僅使用有關節點鄰域的信息。在大多數情況下，這就足夠了。

snap.stanford.edu/node2vec

github.com/xgfs/node2vec-c

VERSE

VERSE + UMAP

用于通用圖表示的高級算法，是我用起來最好的之一。

tsitsul.in/publications/verse

github.com/xgfs/verse

Graph Convolutions

圖卷積+ 自編碼器 二部圖

有很多方法可以定義圖上的卷積。但事實上，這是頂點鄰居的簡單特征“擴散”。我們還可以將局部拓撲信息放在頂點特征中。
編輯：hfy