通过信息多视图投影可视化高维图嵌入

# 通过基于信息的多视图投影实现高维图嵌入的可视化 来源: https://arxiv.org/html/2606.31119 \\onlineid 0\\vgtccategoryResearch \\authororcidXuefeng Li0009\-0007\-6059\-9747\\authororcidTimo Brand0009\-0004\-3111\-2045\\authororcidJacob Miller0000\-0002\-0567\-785X\\authororcidPeng Zhang0009\-0002\-7858\-3691\\authororcidStephen Kobourov0000\-0002\-0477\-2724and\\authororcidYifan Hu0000\-0003\-2017\-924X ###### 摘要 图通常以二维 (2D) 形式可视化，人类可以轻松解读空间关系，然而此类布局常常扭曲高维结构。我们提出将图嵌入到高维空间，并搜索信息丰富的二维视角，以优化美学和可读性指标（例如边交叉和角分辨率），这得益于一种新颖的可微分的边交叉替代函数。数值实验表明，这些视角始终优于标准二维布局，甚至可以超越专门为优化这些指标而设计的方法。我们进一步介绍了 \\DataFly，一个交互式系统，通过无缝导航探索多个候选视角。一项可用性研究表明，我们的方法能够揭示在传统二维可视化中隐藏的结构模式。 ###### 关键词: 图可视化, 降维 \\teaser![[未加标题的图片]](https://arxiv.org/html/2606.31119v1/x1.png) 从高维投影生成的示例可视化。(上) 显示一个通过 \\sfdp 在 10D 中嵌入的 7D 超立方体，并分别投影以优化应力、t-SNE 得分、边交叉、角分辨率和边长度方差。(下) 显示经典的足球网络，通过谱嵌入在 10 维中，来自五个不同的轴对齐视角。这组投影揭示了，在前两个投影中以圆圈突出显示的簇显示，类成员关系在某些投影中空间显著，而在其他投影中消失。 \\shortauthortitle Jiet al.: 可视化高维图嵌入 \\authorfooter Ya Ji, Xuefeng Li, Peng Zhang and Yifan Hu 是东北大学 Khoury 计算机科学学院，美国西雅图。电子邮件: \{ji\.ya1 | li\.xuefen | zhang\.peng2, yif\.hu\}@northeastern\.edu. Timo Brand, Jacob Miller and Stephen Kobourov 是慕尼黑工业大学计算、信息与技术学院，德国海尔布隆。电子邮件: \{timo\.brand | jacob\.miller | stephen\.kobourov\}@tum\.de. 引言 图可视化将抽象关系转换为可读的图形，使用户能够理解复杂的关联数据，发现模式并做出明智的决策。传统上，图以二维形式可视化，反映了人类可解释的空间关系。然而，大型现实世界的图通常表现出类似于高维数据的特征：小世界现象——大多数节点对通过短路径连接——镜像了在高维中观察到的距离集中现象；而现实世界的图，如同高维点云，往往局部密集、全局稀疏。二维布局难以保留这些高维关系。就像立方体无法以等边长投影到二维平面上一样，复杂网络包含局部连接模式（例如稠密团或重叠社区），没有任何单一的二维投影能够忠实地表示。因此，单一的二维图布局虽然直观且易于访问，但可能会扭曲或模糊数据的高维结构。然而，高维布局引入了一个实际挑战：向人类读者呈现它们需要随时选择一个二维投影（即视角）。因此，高质量视角对于高维布局成为有效的可视化工具是必要的，但文献中对这一点的探索有限。许多方法依赖于计算满足某些标准的最优单一投影 [Gajer_Goodrich_Kobourov_2000, PivotGraph, spectral]。Van Wageningen 等人 [Wageningen2025] 在三维绘图的背景下研究了视角问题，但尚不清楚是否能实现高维布局的有效投影。这些观察结果激发了我们提出以下研究问题：高维图嵌入是否包含能够揭示传统静态布局中隐藏的结构模式的二维投影？为了探究这一点，我们开发了一个计算流程来系统探索高维图布局，生成一组候选投影。我们进一步引入了一种基于梯度的优化方案，用于找到给定质量指标（如应力、边交叉或角分辨率）的近最优投影。我们的发现表明，这类投影可以优于那些专门设计用于直接在二维中优化相同指标的先进算法。在整篇论文中，我们使用术语 *最优投影* 作为这种基于梯度的优化结果的简写，并指出它收敛到局部最优而非全局最优。为了使这些高维嵌入可访问和可探索，我们提供了 \\DataFly，一个用于实时可视化高维图布局的交互式在线工具。\\DataFly 实现了有原则的视角探索：用户可以检查特定指标的最优投影，或者通过在高层空间中“飞行”来在这些投影之间过渡，观察一个投影如何转变为另一个。由于所有视角都源自同一个共享嵌入，同一网络的不同视觉视角共存于一个连贯的空间结构中，使用户能够发现任何单一二维布局中隐藏的结构模式。我们的主要贡献如下： - • 我们表明，高维图嵌入的最优二维投影可以提供比几种直接在二维中优化此类指标的先进基准更好的指标值。 - • 我们提出一个可微分的损失函数 SigmoidX，能够有效最小化边交叉，并证明使用该损失函数的最优投影实现的交叉数显著少于 SGD2\text\{SGD\}^\{2\} 和 SmartGD。 - • 我们提供了一个 \\DataFly 的工作原型，这是一个用于探索高维图布局并识别感兴趣视角的交互式系统，并通过一项包含专家和非专家参与者的小型可用性研究进行了评估。虽然我们的主要重点是使用直线节点-链接图可视化图数据，但名称 \\DataFly 反映了我们的交互式多视图探索方法自然扩展到通用高维数据。系统运行的视频可在 http://tiny.cc/datafly-video 找到。\\DataFly 已在 https://datafly.algo.cit.tum.de/ 公开提供。在本文余下部分，DataFly 既指代交互式系统，也指代相关的最优投影框架。 ## 1 相关工作 自 1963 年 [tutte_1963] 以来，已经提出了许多图绘制算法。一类广泛使用的生成直线绘制的方法依赖于最小化系统能量的物理模型。例子包括基于应力的模型，它最小化连接节点的弹簧的应力能量 [kamada_kawai_1989, neato, zheng-gd2]，以及弹簧和电荷的力导向系统，其中沿边的弹簧收缩，而节点上的电荷相互排斥 [Eades_1984, Fruchterman_Reingold_1991, kobourov_2013]。 ### 1.1 针对特定指标进行优化的布局算法 存在许多布局方法专门针对美学指标，例如最小化边交叉 [xing-heuristic, spx]、最大化交叉角度 [Argyriou, Bekos-xangle] 或组合 [didimo]。两个值得注意的算法是 SGD2\text\{SGD\}^\{2\} [sgd2] 和 SmartGD [wang_2023_smartgd]。SGD2\text\{SGD\}^\{2\} 是一种可以联合优化多个图可读性标准的方法。特别是，它可以优化任何可以由可微函数描述的标准。当标准不是可微函数（例如边交叉）时，则使用代理目标函数。SGD2\text\{SGD\}^\{2\} 支持优化角分辨率、边交叉和期望边长等标准。SmartGD [wang_2023_smartgd] 是一个基于生成对抗网络的深度学习图绘制框架。它可以从“好”布局的示例中学习，其中“好”可以由甚至不可微的指标（例如边交叉）来定义。虽然 SGD2SGD^\{2\} 和 SmartGD 是首批可以同时优化多个标准的图嵌入方法之一，但两者在小型图 (|V|≈100\|V\|\approx 100) 之外效果不佳。本文提出的最优投影算法在小图和大图（超过 1000 个节点）上均表现良好，同时支持多个标准。虽然联合优化旨在有效最小化给定指标，同时保持布局的美学吸引力，但它不一定能产生任何单一标准最优的绘图。对算法社区特别感兴趣的是那些优化特定指标（可能以可读性为代价）的算法。一个这样的算法是 Vertex Movement [radermacher2019geometric] (VM)，它优化边交叉而忽略其他美学标准。该算法从一个初始布局开始，迭代所有顶点，并尝试为当前顶点找到交叉最小化的位置。虽然不能保证找到最优绘图，但它在找到边交叉较少的绘图方面表现强劲。我们将 VM 作为边交叉最小化的先进基线，但应注意该算法计算复杂度高，不适用于大型图。 ### 1.2 通过投影理解高维数据 Paulovich 等人 [paulovich2025dimensionality] 最近将降维与图绘制联系起来，显示它们之间的密切关系。通过投影探索高维数据的算法和交互式系统早已被研究，早期工作在统计学和物理社区中 [buja:1996:XGobi, cook1995grand, cutura2018viscoder, Dang2014ScagExplorer, laa2020high, huh2002visualization, Morariu_2023]。值得注意的例子包括基于 R 的可视化工具 XGobi [buja:1996:XGobi] 和 Embedding Projector [smilkov2016embedding]。GraphDice [GraphDice2010] 是一个用于探索和分析图数据的相关工具。它支持通过相邻视图之间的动画过渡来探索多元社交网络图。然而，它在观察到的参与者和边属性上操作，而不是在高维图嵌入的几何投影上。EvoGraphDice [EvoGraphDice2012] 将这一工作扩展到通用多维数据，使用交互式进化搜索根据用户反馈提出特定视图。因此，它作为一种用于引导式视角发现的视觉分析方法相关，但并非为图布局或优化图绘制指标而设计。据我们所知，很少有先前工作侧重于通过最优投影理解高维图嵌入（超出 2/3 维）。Gajer 等人 [Gajer_Goodrich_Kobourov_2000] 表明，在高维空间中布局图并随机投影回二维可以产生有趣的绘图，并用莫比乌斯带示例加以说明；然而，他们的工作并不旨在识别最优视图。与此相关的还有 Gaertler 和 Krug 的工作，他们使用了谱图嵌入不同视角之间的动画 [gaertler05]。Li 等人 [li2020visualizing] 研究了可视化来自神经网络的多元数据的方法。尽管他们考察了 t-SNE 和 UMAP 等非线性降维技术，但线性投影因其对原始数据变化的可预测响应而受到青睐。Etemadpour 等人 [Etemadpour2015] 进行了一项基于感知的多维投影用户研究，表明投影性能取决于任务和数据特征。研究表明，没有任何单一投影方法能产生普遍最优的布局，这支持了对高维图布局生成和评估多个视图的论点。Martins 等人 [Martins2012MDProjection] 引入了用于社交网络可视化的多维投影方法，其中节点放置由节点相似性引导，以产生有意义的二维布局，无需大量基于力的优化。该工作表明，高维嵌入和投影驱动的视图可以揭示传统图绘制之外的结构模式，强化了多视图探索高维图布局的动机。已有研究表明，从三维绘图中获取的二维视角绘图的品质可以高于使用相同算法直接生成的二维绘图 [Wageningen2025]。这一结果通过高效的优化算法（包括梯度下降和进化启发的元启发式）实现，这些算法自动为三维直线图绘图寻找高质量视角，取代了需要评估数千个视角的缓慢蛮力采样方法。虽然这种视角优化与 \\DataFly 中的最优投影类似，但我们的目标是找到 K 维图嵌入的良好视角。最近的发现 [joos2025show] 表明，在创建这样的三维绘图后，用户更喜欢从能够产生具有多个二维质量指标高值的二维投影的角度观看。对于降维图 [castelein2023based] 也显示了类似的结果。我们主要考虑线性投影，尽管存在丰富的非线性降维技术；参见最近的综述 [DBLP:journals/tvcg/NonatoA19, DBLP:journals/tvcg/EspadotoMKHT21]。 ## 2 通过高维布局理解图 在这里，我们给出了方法论的高层概述。我们使用标准图定义：G=(V,E)G=(V,E)，其中 VV 表示顶点集，EE 表示边集。我们假设将图嵌入高维空间能够更忠实地表示其内在结构，例如局部邻域。为此，我们首先使用现成的算法将图嵌入到 KK 维空间（例如，KK=10）。剩下的工作是研究该嵌入的潜在有趣的二维视角用于可视化。图̃1 (https://arxiv.org/html/2606.31119#S2.F1) 说明了同一个 10 维嵌入的不同投影如何揭示不同性质的结构。然而，尚不清楚这些视角是否对现实世界数据提供任何实际优势。我们提出以下研究问题： RQ1. 高维图嵌入与精心设计的投影方法相结合，是否在优化特定美学指标方面优于直接的二维布局？ RQ2. 探索高维视角的系统投影是否有助于用户理解图结构？ 参见图注 图 1: 一个细分二十面体图的 10 维谱嵌入的若干投影。最左边的投影看起来像一个典型的嵌入，但其他视角揭示了结构在环境空间中扭曲并缠绕自身。我们通过本节开发的最优视角公式和 3 节 (https://arxiv.org/h) 中的定量评估来解决 RQ1。