跳转到主要内容
SEO Title
Large Graph Visualization Tools and Approaches

Image for post

如果你需要可视化一个大的网络图,但是你尝试的所有工具只能画一个毛球或者吃掉你所有的内存然后挂上你的机器,那该怎么办?我曾经在处理大型图(数亿个节点和顶点)上工作了两年多,并尝试了很多工具和方法。但我还是没有找到什么好的调查,所以现在我自己写了一个这样的调查。

(这是我最初用俄语写的关于哈勃的文章的译文)

为什么要把图形形象化?

找到要找的东西

通常,我们只需要一组顶点和边作为输入。我们可以根据这些数据计算一些统计数据或图形度量,但这不足以了解结构。一个好的可视化可以清楚地显示一个图中是否有一些簇或桥,或者它是一个统一的云,或者其他什么。

给公众留下深刻印象

很明显,数据可视化是用来表示的。这是从所做工作中得出结论的好方法。例如,如果解决了聚类问题,则可以按标签为绘图着色,并显示它们是如何连接的。

获取功能

尽管大多数图形可视化工具都是为制作一些图片而创建的,但它们还是很好的降维工具。以邻接矩阵表示的图是高维空间中的数据。当绘制它时,我们得到每个顶点的两个(通常)坐标。这些坐标也可以用作特征。在这个空间中,顶点之间的接近意味着相似性。

大图形有什么问题吗?

我的意思是“大图形”的大小大约是10K个顶点和/或边。小尺寸通常没有问题。搜索几分钟就能找到的所有工具,至少都是可以接受的。大型网络有什么问题?主要有两个问题:可读性和速度。通常,大图形的可视化看起来很混乱,因为一个图中有太多的对象。此外,图形可视化算法大多具有可怕的算法复杂度:二次或三次依赖于边或顶点的数量。即使您只等待一次结果,也将太长时间无法找到更好的参数。

如果你需要可视化一个大的网络图,但是你尝试的所有工具只能画一个毛球或者吃掉你所有的内存然后挂上你的机器,那该怎么办?我曾经在处理大型图(数亿个节点和顶点)上工作了两年多,并尝试了很多工具和方法。但我还是没有找到什么好的调查,所以现在我自己写了一个这样的调查。

关于这个问题已经写了些什么?

[1] 海伦·吉布森、乔·费思和保罗·维克斯:“信息可视化的二维图形布局技术综述”

本文的作者告诉了存在哪些图形可视化方法以及它们是如何工作的。还有一个很好的表格,里面有关于算法、它们的特性和复杂性的信息。我在这篇文章中用了几张报纸上的照片。

[2] Oh Hyun Kwon,Tarik Crnovrsanin和Kwan Liu Ma“在这种布局中,图形会是什么样子?大图形可视化的机器学习方法

作者们做了大量的工作。他们尝试了所有可能的算法。然后他们画出它并手工评估相似度。之后,他们对模型进行拟合,以预测图形在这个布局中的样子。我也用了几张这幅作品的照片。

理论部分

布局是一种将坐标映射到每个顶点的方法。通常,这是二维平面上的坐标。

什么是好的布局?

判断事物的好坏是很容易的。命名标准并不是那么容易,机器如何评估它。为了做出所谓的“好”布局,可以使用美学度量。以下是其中一些:

最小边相交

很明显:过多的交叉口会让情节显得凌乱不堪。

相邻顶点之间的距离比不相邻的顶点更近

这是合乎逻辑的,连接的节点应该彼此靠近。它表示图中定义的主要信息。

社区被分组成集群

如果有一组顶点彼此之间的连接比图的其他部分更频繁,那么它们看起来应该像一个密集的云。

最小重叠边和节点。

这也是显而易见的:如果我们不能确定是否有几个顶点或一个顶点,那么绘图的可读性就很差。

存在哪些布局?

Image for post

我认为有必要提及这三种布局。然而,可以用许多其他方法对它们进行分类。但这种分类足以在所有可能的类型中导航。

  1. 以力为导向,以能量为基础
  2. 降维
  3. 基于节点特征

以力为导向,以能量为基础

Image for post

力有向布局示例。

这种方法是基于物理系统仿真的。顶点表示为相互排斥的带电粒子,边被视为弹性弦。这些方法试图模拟这个系统的动力学或找到最小能量。

这种方法通常会产生非常好的结果。结果图很好地反映了图的拓扑结构。但是它们也很难计算,并且有很多参数需要调整。

这个大家庭的重要成员是原力阿特拉斯、弗鲁克特曼·莱因戈尔德、卡马达·卡瓦伊和奥普诺德(Force Atlas, Fruchterman-Reingold, Kamada Kawaii and OpenOrd)。最后一种方法使用复杂的优化来加快计算速度,例如,它切割长边。作为一个有用的副作用图变得更加聚集。

降维

Image for post

降维布局示例。

图可以定义为邻接矩阵NxN,其中N是节点数。这个矩阵也可以看作是N维空间中N个对象的表。这种表示允许我们使用通用的降维方法,如PCA、UMAP、tSNE等。另一种方法是计算节点之间的理论距离,然后在移动到低维空间时尽量节省比例。

基于特征的布局

用于post的图像

Image for post

配置单元图(Hive Plot)示例。

通常,图形数据与现实世界中的某些对象相关。所以顶点和边可以有自己的特征。因此,我们可以使用这些特征在平面上表示它们。我们可以使用上述降维方法或直接绘制特征对的散点图来处理节点特征。值得一提的是蜂巢图,因为它与其他所有的方法都有很大的不同。在配置单元中,打印节点与多个径向轴对齐,边是它们之间的曲线。

大型图形可视化工具

Image for post

尽管图形可视化问题是一个相对古老和流行的问题,但是对于能够处理大型图形的工具来说,这是一个非常糟糕的情况。大部分都被开发商抛弃了。几乎每个人都有自己的大缺点。我只告诉那些值得一提的,能处理大图表的人。关于小图,没有问题。你可以很容易地找到一个适合你的工具,而且很可能会很好地工作。

GraphViz

Image for post

2011年前比特币交易图

Image for post

有时很难调整参数

这是一个老式的CLI工具,它有自己的图形定义语言“dot”。这是一个有几个布局的包。对于大型图形,它具有sfdp布局,源于force-directed family。这个工具的优点和缺点是一样的:它从命令行运行。它对于自动化很有用,但是如果没有交互性,很难调整参数。您甚至不知道需要等待结果多长时间,也不知道是否需要停止它并使用其他参数重新运行。

盖菲(gephi)

Image for post

Image from gephi.org

Image for post

137K movies recommendation graph from iMDB

Image for post

几百万对盖菲来说已经太多了

我所知道的最强大的图形可视化工具。它有图形用户界面,它包含几个布局和许多图形分析工具。还有很多由社区编写的插件。例如我最喜欢的布局“多重引力地图集2”或西格玛js导出工具,它基于项目创建交互式网页模板。在Gephi中,用户可以根据它的特征对节点和边缘进行着色。

但Gephi被开发商抛弃了。它还有一点老式的GUI,缺少一些简单的特性。

Igraph

Image for post

姓氏.fm音乐推荐图。来源,描述和交互版本在这里

我需要向这个通用的图形分析包致敬。其中最令人印象深刻的图形可视化是由一位igraph作者制作的。

igraph的缺点是pythonapi的糟糕文档,但源代码可读性强,注释性强。

LargeViz

Image for post

一个最大的比特币集群中有几千万个顶点(事务和地址)

当你需要画一个非常大的图形时,它是一个伟大的救世主。LargeViz是一种降维工具,不仅可以用于图形,还可以用于任意表格数据。它从命令行运行,运行速度很快,并且消耗少量的RAM。

Graphistry

Image for post

Addresses that could be hacked in one week and their transactions

 

Image for post

直观美观的图形用户界面,但非常有限

它是本次调查中唯一的付费工具。Graphistry是一种服务,它接受您的数据并进行所有计算。客户只在浏览器中查看漂亮的图片。除了Graphistry有合理的默认参数、良好的颜色方案和稍微更好的交互性之外,其他特性都没有Gephi更好。它只提供一种力导向布局。它也有800K个节点或边的限制。

图嵌入

对于疯狂的尺码也有办法。从大约一百万个顶点开始,只有合理的方法来观察顶点密度,而根本不绘制边和特定的顶点。只是因为没有人能在这样的图上辨认出单个的物体。此外,大多数为图形可视化而设计的算法在这样的尺寸下要工作很多小时,甚至几天。如果我们稍微改变一下方法,这个问题是可以解决的。有很多方法可以得到反映图顶点特征的固定大小的表示。在得到这样的表示之后,你唯一需要做的就是把维数降到2,这样才能得到一张图片。

节点2VEC

Image for post

节点2VEC+UMAP

这是word2vec对图形的改编。它在图中使用随机游动而不是单词序列。因此,该方法只利用节点邻域的信息。在大多数情况下,这已经足够了。

VERSE

Image for post

韵文+UMAP

通用图形表示的高级算法。这是我经验中最好的一个。

图卷积(Graph Convolutions)

Image for post

图形卷积+自动编码器。二部图。

有很多方法可以定义图上的卷积。但事实上,这是一个简单的“传播”特征顶点的邻居。我们还可以将局部拓扑信息放在顶点特征中。

小奖励

我做了一个小教程简化图卷积没有神经网络。它就在这里。我还制作了一个图形嵌入教程,其中我展示了如何使用上述一些工具。

Links

  • Simplifying Graph Convolutional Networks
  • arxiv.org/pdf/1902.07153.pdf
  • GraphViz
  • graphviz.org
  • Gephi
  • gephi.org
  • igraph
  • igraph.org
  • LargeViz
  • arxiv.org/abs/1602.00370
  • github.com/lferry007/LargeVis
  • Graphistry
  • www.graphistry.com
  • Node2Vec
  • snap.stanford.edu/node2vec
  • github.com/xgfs/node2vec-c
  • VERSE
  • tsitsul.in/publications/verse
  • github.com/xgfs/verse
  • Notebook with simplified graph convolutions example
  • github.com/iggisv9t/graph-stuff/blob/master/Universal%20Convolver%20Example.ipynb
  • Graph Convolutions
  • List of papers about Graph Convolutional Networks: github.com/thunlp/GNNPapers

TL;DR:

Image for post

新希望:格拉菲亚[2020年6月5日更新]

Image for post

这是苍蝇大脑部分的神经元连接https://neuprint.janelia.org/

这篇文章发表于大约一年前。现在有一种新的非常有前途的图形可视化工具,尤其是大型图形:Graphia。它正在积极开发中,而不是很久以前就被抛弃的Gephi,而且它的工作速度也快得多。由于Gephi it集成了许多工具,您可以在这里阅读:https://graphia.app/userguide.html

缺点是可以原谅的:

  • 目前,它只有一个力导向的布局和非常有限的方式来调整它。
  • 渲染选项不适用于大型图形。至少关闭边显示或添加不透明度的选项会非常有用。
  • 现在葡萄还比较生。例如,为了放入graphi,我不得不用Gephi转换图形格式,而graphia在用CSV表示的同一个图形上崩溃了。但我相信这些小事很快就会得到改善。

优点太多,难以列举。想象一下Gephi,所有这些分析工具,但从头改写C++,速度更快,在积极发展。作为比较:Gephi需要几个小时来布局173K节点图,而Graphia只需要几分钟。

我相信这个评论很快就会过时,所以最好自己检查一下这个应用程序的当前状态。

原文:https://towardsdatascience.com/large-graph-visualization-tools-and-approaches-2b8758a1cd59

本文:http://jiagoushi.pro/node/1089

讨论:请加入知识星球【首席架构师圈】或者微信小号【jiagoushi_pro】

Tags