如果你需要可視化一個(gè)大規(guī)模的圖網(wǎng)絡(luò)，而你嘗試了各種各樣的工具，卻只畫了一個(gè)小毛球就耗盡了你的 RAM，這時(shí)候你要怎么辦？我的工作常常需要可視化大規(guī)模圖（上億的節(jié)點(diǎn)），嘗試了非常多的工具和方法。但是，我卻沒有發(fā)現(xiàn)有人提供實(shí)用的攻略，于是，我決定根據(jù)自己的經(jīng)驗(yàn)寫一篇攻略。

為什么要可視化圖

發(fā)現(xiàn)尋找的目標(biāo)

通常，我們會(huì)將節(jié)點(diǎn)和邊的集合作為輸入，然后基于數(shù)據(jù)可以計(jì)算出一些統(tǒng)計(jì)信息，但是這不足以從結(jié)構(gòu)中獲得想法。好的可視化可以幫助我們清晰的發(fā)現(xiàn)圖中的一些簇、 bridges 或者是點(diǎn)云，還有一些其他的模式。

便于解釋

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

獲得特征

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

大規(guī)模圖的問題

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

已有的研究

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”

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

理論部分

Layout 是一種將坐標(biāo)映射到每個(gè)節(jié)點(diǎn)的方法。通常，這是指 2D 平面上的坐標(biāo)。

什么是好的 Layout

很容易評(píng)價(jià)一個(gè)東西看起來是好還是壞，但是很難制定機(jī)器評(píng)估好壞的標(biāo)準(zhǔn)。為了得到所謂的“好的” layout，可以使用以下這些指標(biāo)：

1. Minimum edges intersection（最小邊交）

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

2. 相鄰的節(jié)點(diǎn)彼此靠近

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

3. 社區(qū)聚類

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

4. 最小的重疊邊和節(jié)點(diǎn)

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

Layout 的類別

同一個(gè)圖在不同 layout 上的呈現(xiàn)。

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

力導(dǎo)向和基于能量

降維

基于節(jié)點(diǎn)特征

力導(dǎo)向

這一類方法是基于物理系統(tǒng)仿真的。頂點(diǎn)表示為相互排斥的帶電粒子，邊被視為彈性線。這些方法試圖建立這個(gè)系統(tǒng)的動(dòng)力學(xué)模型或找到最小能量。這些圖通常會(huì)比較好的反應(yīng)圖的拓?fù)浣Y(jié)構(gòu)，但是計(jì)算非常復(fù)雜，需要調(diào)節(jié)非常多參數(shù)。

該方法的重要成員包括 Force Atlas，F(xiàn)ruchterman-Reingold，Kamada Kawaii and OpenOrd。最后一種會(huì)使用一些優(yōu)化方法來減少計(jì)算量，比如削減長(zhǎng)邊，但是作為副作用，會(huì)讓圖更加聚集。

降維

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

基于特征

通常，圖數(shù)據(jù)都和現(xiàn)實(shí)生活中的對(duì)象相關(guān)聯(lián)。因此，頂點(diǎn)和邊會(huì)有自己的特征。因此我們可以用這些特征來表示它們。我們可以利用上面講到的降維方法，像處理表數(shù)據(jù)一樣處理節(jié)點(diǎn)的特征，或者直接繪制節(jié)點(diǎn)特征對(duì)的散點(diǎn)圖。值得一提的是 Hive Plot，因?yàn)樗推渌姆椒ǘ疾煌?。?Hive Plot 中，節(jié)點(diǎn)與多個(gè)徑向軸對(duì)齊，邊是它們之間的曲線。

大規(guī)模圖可視化工具

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

GraphViz

2011年以前的比特幣交易圖

有些時(shí)候，調(diào)參非常困難

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

graphviz.org

Gephi

Gephi 圖界面

來自 iMDB 的 13K 的電影推薦系統(tǒng)的圖

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

但是 Gephi 仍然被開發(fā)者拋棄了。它還有一點(diǎn)老式的 GUI 和一些簡(jiǎn)單的特征。

gephi.org

igraph

音樂推薦圖

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

igraph.org

LargeViz

最大的比特幣集群，里面有幾千萬個(gè)節(jié)點(diǎn)（交易和地址）

當(dāng)你需要繪制一個(gè)巨大的圖時(shí)，它將是偉大的救世主。LargeViz 是一種降維工具，不僅可以用于圖，還可以用于任意表數(shù)據(jù)。它從命令行運(yùn)行，工作速度快，占用較少的內(nèi)存。

arxiv.org/abs/1602.00370

github.com/lferry007/LargeVis

Graphistry

一周內(nèi)可能被黑客攻擊的地址以及交易

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

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

www.graphistry.com

Graph Embeddings

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

Node2Vec

Node2Vec + UMAP

這是 word2vec 在圖的改編。圖中使用隨機(jī)游動(dòng)而不是單詞序列。因此，該方法僅使用有關(guān)節(jié)點(diǎn)鄰域的信息。在大多數(shù)情況下，這就足夠了。

snap.stanford.edu/node2vec

github.com/xgfs/node2vec-c

VERSE

VERSE + UMAP

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

tsitsul.in/publications/verse

github.com/xgfs/verse

Graph Convolutions

圖卷積+ 自編碼器 二部圖

有很多方法可以定義圖上的卷積。但事實(shí)上，這是頂點(diǎn)鄰居的簡(jiǎn)單特征“擴(kuò)散”。我們還可以將局部拓?fù)湫畔⒎旁陧旤c(diǎn)特征中。
編輯：hfy