Simultaneous Matrix Orderings for Graph Collections
Nathan van Beusekom, Wouter Meulemans, and Bettina Speckmann.
IEEE Transactions on Visualization and Computer Graphics,
28(1):1—10,
2022.
- Abstract
Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph G can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice.<br/><br/>Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people.<br/>To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously.<br/>The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. <br/>We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.<br/><br/>The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran's I, a spatial auto-correlation metric, which captures the full range of established patterns. Moran's I refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran's I in this context. An ordering that maximizes Moran's I can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP.<br/><br/>We evaluated our methods for simultaneous orderings on real-world datasets using Moran's I as the quality metric. Our results show that our collection-aware approach matches or improves performance<br/>compared to the union approach, depending on the similarity of the graphs in the collection. <br/>Specifically, our Moran's I-based collection-aware leaf order implementation consistently outperforms other implementations.<br/>Our collection-aware implementations carry no significant additional computational costs.
- BibTeX
@article{simultaneous-matrix-orderings-for-graph-collections:2022,
title = {Simultaneous Matrix Orderings for Graph Collections},
author = {Nathan van Beusekom and Wouter Meulemans and Bettina Speckmann},
year = {2022},
bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
}