基本信息
- 论文： GUIRO: User-Guided Matrix Reordering
- 作者： Michael Behrisch, Tobias Schreck, and Hanspeter Pfister
- 来源： IEEE Vis 2019 / TVCG 2020 Jan.
背景
邻接矩阵是常见的一种表示关系型数据的方式，在表示大规模数据时有许多节点-链接图所不具备的优势。矩阵重排序的几个研究问题需要解决：
- Which 选取哪种重排序算法？
- What 通过重排序可以从数据中得到什么信息？
- How 如何设计出更好的矩阵重排序算法？
贡献
构建了用于矩阵重排序的可视分析系统 ：GUIRO: user-GUIded matrix Re-Ordering。做到了：
- 整合并提供重排序算法
- 交互选择并自动/手动重排序
- 比较重排序算法量化指标
用户场景分析
本文将矩阵重排序的用户场景分为三类：学者、网络分析师以及算法设计师，对与三类分别阐述了他们的动机和应用场景。
- 学者：主要通过比较不同算法的效果，选取合适的算法呈现自己数据中的特征
- 网络分析师：运用多种分析手段，对数据的全局/局部特征进行分析
- 算法设计师：设计新的重排序算法并进行比较分析
预备知识
矩阵可视化特征
以下方的图为例进行阐述：
block-diagnal
聚集在对角线的方阵形式，如 v1,v2,v3，表示一个全连接的子图。
off-diagnal block
分布在对角线外的两侧，为部分群体与另一部分群体均有连接的情况，如 v5,v6 和 v1-v4。
Band
成条带状，表示图中的路径结构。
Star/Line
星状或带状结构，表示图中的星状的连接结构。
矩阵重排序方法
常见的矩阵重排序方法有两类，自动与手动。
- 自动重排序：通过优化某种度量指标（如相邻行/列的相似程度）来指导进行排序
- 手动重排序：通过交互的方式，用户指定对应的排序
系统介绍
系统主体分为三个部分，分别为：左侧的数据集与重排序算法选择界面；中部的重排序结果呈现视图以及右侧的重排序结果的投影视图。
矩阵重排序
系统左侧视图，列举了本文所封装实现的 71 种矩阵重排序算法，用户可以预览结果、评价指标，以及针对启发式算法生成的多重结果来选择应用于全局的重排序算法。
另外，本文创新性的引入了投影视图来辅助重排序算法的呈现与交互：
将矩阵的每一行/列提取成一个向量，并对其运用降维方法进行投影，得到而为空间的点，而其中的边则表示的是重排序的相邻关系。
用户交互
用户可以在投影视图中进行直观的交互。主要有两种形式。
一种是半自动的操作，即用户用 lasso 选取部分节点，生成 submatrix，然后针对 submatrix 应用重排序得到局部的排序结果。
另一种是手动操作，用户对排序结果进行调整，改变节点间的相邻关系，从而得到新的符合用户需求的排序。
算法指标分析
GUIRO 还提供了不同算法的对比分析视图以供算法设计者比较不同的算法：
除了在表格中呈现不同算法对应的指标之外，GUIRO 还采取了平行坐标的形式来展现不同算法的排序结果，用户还可以通过拖拽的交互调整顺序来表达不同算法的计算结果。
系统评估
Case Study
如上图所示，本文展示了如何利用 GUIRO 来指导用户重排序并得到更好的 pattern。
- 初始导入的数据，为随机排序，毫无特征可言
- 为数据应用全局的重排序算法之后，得到了初步结果
- 发现左上角分布仍然比较杂乱，因此试图从投影视图中发现改进方法
- 在投影视图中选取左上角聚类，发现在排序的矩阵中分布并不连续，对其应用另一种重排序算法之后，得到了右图所示的结果，此时发现左上角的特征得到了呈现
通过上述操作流程，我们可以看到，在 GUIRO 系统的指导下，的确对我们分析数据并得到数据中的全局或局部特征有一定帮助。
讨论
优势
- 引入 Projection View，便于交互提取 submatrix，便于对局部的 submatrix 应用重排序算法
- 支持交互式手动排序，提高了排序的灵活性
- 支持层级式操作，可以从全局到局部渐进地进行重排序与特征的提取
不足与未来工作
在系统所用的方法上：
- 目前仅支持对称方阵，考虑支持非对称方阵，非方矩阵
- 需要拓展 projection 方法，增强 Projection View 的指导性
在系统的技术实现上：
- 目前采用了 Web-based C/S 结构，信息传递效率低
- 矩阵绘制为 SVG，考虑基于 Canvas/WebGL 实现
总结
本文用可视分析的方法进行矩阵重排序，主要有以下特点：
- 引入投影视图，打开重排序算法的黑盒
- 交互选取对全局或局部应用重排序算法
- 对不同重排序算法指标进行对比分析
✉️ zhaoxiaodong@zju.edu.cn