矩阵可视化可以突出图数据中的局部结构。为了使这些结构表现为明显的视觉模式，人们提出了各种矩阵重排的方法来对矩阵的行和列进行适当排序。 但是，图数据可能不是孤立出现的，而是属于共享一组顶点的图集合的一部分。在这种情况下，已有的一种方法是选择一个图进行矩阵重排，然后推广到所有的图上；另一种方法是对所有图进行加权的合并，然后对合并后的图进行重排。然而这些方法都会损失信息，来自荷兰埃因霍芬理工大学的Beusekom等人 [1] 提出了一种考虑整个图集合的重排算法，如图1所示，可以同时对图集合中的所有图数据得到较好的矩阵重排结果。
为了评估矩阵可视化的重排效果，人们提出了一些评估指标。例如带宽（Bandwidth）定义为图中边的顶点之间的最大距离，线性排列（Linear Arrangement）定义为图中边的顶点之间的距离之和等等。这些评价指标和矩阵可视化结果中的视觉特征存在一定的正相关关系，因此，已有的一些算法通过优化这些指标来得到好的矩阵重排的结果。
该工作首先引入了一个新的评价指标 Moran’s I [2] 用于评估矩阵可视化的效果。Moran’s I 是由Moran首先提出的一个衡量整体空间自相关的相关系数，在矩阵可视化的情况下，该工作将其简化为如下的表达式：
\( I(G, \rho) = c_{B}(G) \cdot B(G, \rho) + c_{W}(G) \cdot W(G, \rho) – 1 \\c_{B}(G) = \frac{n}{2(n-1)m} \\
c_{W}(G) = \frac{n}{2(n-1)(n^{2}-m)} \)
其中n为节点数量，m为边的数量。\( B(G, \rho) \) 为黑色方块与黑色方块相邻的数量，\( W(G, \rho) \) 为白色方块与白色方块相邻的数量。如图2所示，具有区块、星形等视觉模式的矩阵可视化相比于随机的布局具有更高的Moran’s I的值，因此可以通过优化 Moran’s I 的值来计算矩阵的排序。该工作通过将最大化Moran’s I的问题转化为最小化距离之和的问题，然后使用叶序法 (Leaf Order Method) [3] 来求解该问题。
另一方面，该工作提出了一种考虑整个图集合的重排思想，可以应用于已有的针对单个矩阵的重排算法，例如叶序法和重心法 (Barycenter Method)。相比于已有的基于加权合并的方法，该工作提出的方法具有更好的效果。
对于单个矩阵的重排，在叶序法中，我们首先使用计算欧几里得（或Moran’s I）距离计算节点之间的距离，然后在节点上构建一个分层的聚类，最后计算得到使矩阵可视化中连续行之间的节点距离之和最小的排序。对于图集合的重排，加权合并的方法在计算距离时采取的方法是先对图集合进行加权合并，然后计算节点之间的距离，而该工作提出的方法是先在每个图中计算节点之间的距离，然后对得到的在不同图中的节点距离进行加权合并。这两种计算方法的相同点在于，当两个节点的邻居节点相似时，得到的距离结果较小，而区别在于在使用加权合并的方法在得到的加权节点距离较小时，两个节点在不同的图中的邻居节点可能并不相似。因此，使用该工作提出的方法可以得到更好的结果。
在重心法中，在计算对于单个矩阵的重排时，每次根据节点的邻居节点的位置中位数对其进行排序，反复更新直到节点位置不再变化。 对于图集合的重排，加权合并的方法每次更新时取的是加权的中位数，而该工作提出的方法则是对于目标节点，取的是图集合中每个图得到该节点的邻居节点的位置中位数的中位数。
为了验证方法的有效性，该工作在三个数据集上进行了实验。如图3所示，使用Moran’I作为优化指标并且使用该工作提出的考虑整个图集合的重排算法具有最好的效果。
参考文献
[1] N. Beusekom, W. Meulemans, and B. Speckmann. Simultaneous matrix orderings for graph collection. IEEE Transactions on Visualization and Computer Graphics, 2021.
[2] P. A. P. Moran. Notes on continuous stochastic phenomena. Biometrika, 37 (1): 17–23, 1950.
[3] Z. Bar-Joseph, D. K. Gifford, and T. S. Jaakkola. Fast optimal leaf ordering for hierarchical clustering. Bioinformatics, 17(suppl 1): S22–S29, 2001.
评论关闭。