ViBR: Visualizing Bipartite Relations at Scale with the Minimum Description Length Principle
作者
纽约大学：
- Gromit Yeuk-Yin
博世北美研究中心
- Panpan Xu
- Zeng Dai
- Liu Ren
摘要：
二部图模拟了许多真实世界中大规模的关键关系，比如顾客购买商品，立法者投票、人与不同社会群体的联系，车辆发生故障等等。然而，对具有成千上万甚至更多节点或边的二部图进行可视化是非常有挑战的。在本文中，我们提出了一种基于最小描述长度（MDL）的新的视觉摘要技术。该方法同时对两个不同的组进行分组并构造平衡了粒度和准确度的二部图关系。它解决了在可视化包含噪声的大规模图数据是一个关键的权衡问题：得到一个清晰简洁的概述，同时最大化信息量。我们将视觉摘要任务定义为一个共聚类问题，并提出了一种基于局部敏感哈希（LSH）的有效算法，能够在合理的交互时间限制下扩展到大规模的图，这是以前的方法所不能满足的。该方法使我们有机会引入一个具有多种细节层次的可视化分析框架，以提供方便的交互式数据探索。在框架中，我们还引入了一个紧凑的视觉设计，该设计受图的邻接表表示启发，作为一个小倍数的构建块，用于比较不同数据子集之间的二部关系。我们进行了对含有真实标签的数据的实例研究，包括唱名投票记录分析和车辆故障模式分析，验证了该方法的实用性和有效性。接受采访的政治科学界和汽车工业界的专家也进一步强调了我们方法的好处。
引言
数据规模大的挑战
- 超出人类认知的能力
- 真实的数据包含很多噪声
为了解决这些挑战，本文采用了信息论中的最小描述长度（MDL）的概念来生成一个高层次的 overview，平衡视觉复杂度和信息损失。
相关工作
二部图关系可视化
展示节点之间的边
- semantic substrates
- PivotPath
- Jigsaw
- Parallel node-link bands
unimodal，将图看做整体
- FacetAtlas
- OntoVis
- Anchored Maps
二部图关系聚类与可视化
提取 bi-cliques：
- CHARM
- LCM
将点聚为两组，放松 bi-cliques 的要求：
- Spectral co-clustering
- spectral bi-clustering
二部图概要的最小描述长度
二部图的 two-part representation
二部图可以表示为图概要 S 和修正 C
根据概要 S 和修正 C，我们能够还原出原始图。所以这是一种无损表示.
MDL 原则
我们提出了一种算法来得到节点的最佳分组。
优化目标：
P、Q 是两部分顶点的划分
计算 MDL 表示
基本方法：BM-MDL
自底向上的贪心方法，每次合并一对 cluster 合并使得 MDL 减少最多，直至不再减少。
加速方法：随机选择一个 cluster，合并至两跳邻居
利用 LSH 加速：
LSH 能够快速发现基于 Jaccard 距离的最相似的两个 clusters
实验评估
对比的方法：
- SCMiner
- CA
- BM-MDL-LSH
数据集：
- MovieLens
系统设计
作者还提出了多种可视化形式，包括基于邻接表的、基于流图的和基于邻接矩阵的设计。
基于邻接表的设计中，填充色块的高度代表边的密度。此种布局较为紧凑，且能够方便用户进行过滤等操作。
用户交互
系统支持多种交互方式：
- 过滤
- 通过节点属性来比较二部图的连接
- 展示需要的细节
- 坐标轴刷取
案例分析
数据集：
- roll-call voting（GovTrack.us）
- vehicles’ after-market repair information