[论文] Exact Topological Compliance: Generating Persistence-Equivalent Graphs

论文概要

研究领域: ML
作者: Mattie Ji, Indradyumna Roy, Vikas Garg
发布时间: 2026-10-13
arXiv: 2610.18856

中文摘要

持续同调将图的拓扑演化总结为持久图（PD）。生成拓扑匹配目标描述符的图日益重要，但现有拓扑感知生成模型依赖软正则化，生成的图其 PD 可能仅近似相似。我们对生成问题发起了一项有原则的探究：精确地生成实现目标 PD 的图。我们提出了两种方法，由目标 PD 施加的隐式局部和全局约束引导。局部方法迭代构建基于度的 PD 等价图，我们证明每个输出都实现了目标 PD，且每个基于度的 PD 等价图都可达。然而如后所示，局部生成必然需要在样本多样性和到达不可行状态之间进行权衡。因此我们将生成重构为全局约束满足问题，具有可由现代约束规划求解器求解的完整编码。这适用于任何基于顶点的置换等变过滤方案，在度过滤下是最小的。在四个标准图生成基准上的实验证实两种方法都能精确实现目标 PD。

原文摘要

Persistent homology summarizes the topological evolution of a graph as persistence diagrams (PDs). Generating graphs whose topology matches a target descriptor is increasingly important, yet existing topology-aware generative models rely on soft regularization, producing graphs whose PDs may only be approximately similar. We initiate a principled investigation of the generation problem: produce graphs that realize a target PD exactly. We propose two approaches guided by the implicit local and global constraints a target PD imposes. The local approach builds degree-based PD-equivalent graphs iteratively, and we prove that every output realizes the target PD and that every degree-based PD-equivalent graph is reachable. However, as shown thereafter, local generation necessarily trades off bet...

自动采集于 2026-10-15

#论文 #arXiv #ML #小凯