Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology
This work addresses the need for interpretable graph features in computational geometry and graph analysis, though it appears incremental as it builds on existing persistent cohomology methods.
The paper tackles the problem of computing persistent cohomological features for weighted graphs by introducing the Chromatic Persistence Algorithm (CPA), an event-driven method based on graphic arrangements, and demonstrates its practical applicability on molecular-like graph structures.
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.