用代数拓扑方法提取可解释的图特征，适合分子结构分析
Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology
- 基于图形排列计算图的持久上同调特征
- 对树、环等常见图类近乎线性高效，最坏情况指数级复杂度
- 适用于需可解释性的分子图分析场景
我们提出染色持久算法（CPA），一种通过图形排列计算加权图持久上同调特征的事件驱动方法。该方法在最坏情况下为指数复杂度，但在树宽固定时是固定参数可解的，并且对树、环和串联并联图等常见图类接近线性时间。最后，我们在类似分子的图结构上通过受控实验展示了其实际应用价值。
原文摘要 · Abstract (English)
We present the Chromatic Persistence Algorithm (CPA), an event-driven method for computing persistent cohomological features of weighted graphs via graphic arrangements, a classical object in computational geometry. We establish rigorous complexity results: CPA is exponential in the worst case, fixed-parameter tractable in treewidth, and nearly linear for common graph families such as trees, cycles, and series-parallel graphs. Finally, we demonstrate its practical applicability through a controlled experiment on molecular-like graph structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。