Uncertainty Visualization for Graph Coarsening
Uncertainty Visualization for Graph Coarsening
复制标题
DOI：
10.1109/bigdata55660.2022.10021039
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Fangfei Lan;Sourabh Palande;Michael Young;Bei Wang
中科院分区：
文献类型：
--
作者：
Fangfei Lan;Sourabh Palande;Michael Young;Bei Wang
现实世界中大型图形的复杂性使得对其进行分析的成本过高，可视化效果不佳。图缩减的理念是在保留图的相关属性的同时缩小图的大小。为了提高计算效率并提供可证明的保证，许多图缩减技术都采用了随机化技术。然而，与随机图缩减及其后续解释相关的不确定性在很大程度上仍未得到探索。在本文中，我们提出了一个框架，用于量化和可视化与随机图缩减技术相关的不确定性。我们将重点放在 Ng、Jordan 和 Weiss 引入的谱聚类上，这是一种流行的图缩减技术，通过将图中的节点聚类为超级节点来减少节点数量。我们引入了两种不确定性测量方法--局部调整的兰德指数和共现指数--来量化和可视化与缩减图集合相关的不确定性。我们通过实验证明，这些测量方法在可视化不确定性和指导选择最佳聚类数量方面相辅相成。
The complexity of large real-world graphs makes their analyses prohibitively costly and their visualizations uninformative. The idea behind graph reduction is to reduce the size of a graph while preserving its properties of interest. To improve computational efficiency and to provide provable guarantees, many graph reduction techniques employ randomization. However, the uncertainty associated with randomized graph reduction and its subsequent interpretation has remained largely unexplored. In this paper, we present a framework to quantify and visualize the uncertainty associated with randomized graph reduction techniques. We focus on spectral clustering introduced by Ng, Jordan, and Weiss, a popular graph reduction technique that reduces the number of nodes by clustering the nodes of a graph into super-nodes. We introduce two uncertainty measures – local adjusted Rand indices and co-occurrences – to quantify and visualize uncertainty associated with an ensemble of reduced graphs. We demonstrate via experiments, that these measures complement each other in visualizing uncertainty and guiding the selection of optimal numbers of clusters.