Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology

• URL: http://arxiv.org/abs/2512.20311v1
• Date: Tue, 23 Dec 2025 12:29:58 GMT
• Title: Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology
• Authors: Yoshihiro Maruyama,
• Abstract summary: We present the Chromatic Persistence Algorithm (CPA), an event-driven method for computing persistent cohomological features of weighted graphs via graphic arrangements.<n>We establish rigorous 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Continuous Product Graph Neural Networks [5.703629317205571]
  Multidomain data defined on multiple graphs holds significant potential in practical applications in computer science. We introduce Continuous Product Graph Neural Networks (CITRUS) that emerge as a natural solution to the TPDEG. We evaluate CITRUS on well-known traffic andtemporal weather forecasting datasets, demonstrating superior performance over existing approaches.
  arXiv  Detail & Related papers  (2024-05-29T08:36:09Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  We introduce an algorithm for graph matching based on the proximal operator, referred to as differentiable proximal graph matching (DPGM) The whole algorithm can be considered as a differentiable map from the graph affinity matrix to the prediction of node correspondence. Numerical experiments show that PGM outperforms existing graph matching algorithms on diverse datasets.
  arXiv  Detail & Related papers  (2024-05-26T08:17:13Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Scalable Bayesian Structure Learning for Gaussian Graphical Models Using Marginal Pseudo-likelihood [2.312692134587988]
  We develop continuous-time (birth-death) and discrete-time (reversible jump) Markov chain Monte Carlo (MCMC) algorithms that efficiently explore the posterior over graph space.<n>The algorithms scale to large graph spaces, enabling parallel exploration for graphs with over 1,000 nodes.
  arXiv  Detail & Related papers  (2023-06-30T20:37:40Z)
• On the Expressivity of Persistent Homology in Graph Learning [13.608942872770855]
  Persistent homology, a technique from computational topology, has recently shown strong empirical performance in the context of graph classification.<n>This paper provides a brief introduction to persistent homology in the context of graphs, as well as a theoretical discussion and empirical analysis of its expressivity for graph learning tasks.
  arXiv  Detail & Related papers  (2023-02-20T08:19:19Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
  arXiv  Detail & Related papers  (2023-02-07T17:07:46Z)
• A Multi-scale Graph Signature for Persistence Diagrams based on Return Probabilities of Random Walks [1.745838188269503]
  We explore the use of a family of multi-scale graph signatures to enhance the robustness of topological features. We propose a deep learning architecture to handle this set input. Experiments on benchmark graph classification datasets demonstrate that our proposed architecture outperforms other persistent homology-based methods.
  arXiv  Detail & Related papers  (2022-09-28T17:30:27Z)
• Graph Pooling with Maximum-Weight $k$-Independent Sets [12.251091325930837]
  We introduce a graph coarsening mechanism based on the graph-theoretic concept of maximum-weight $k$-independent sets. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs.
  arXiv  Detail & Related papers  (2022-08-06T14:12:47Z)
• Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs [2.4118754741048987]
  Clustering in directed graphs remains a fundamental challenge due to the asymmetry in edge connectivity.<n>We introduce the generalized Dirichlet energy (GDE), a novel energy functional that extends the classical Dirichlet energy.<n>We propose the generalized spectral clustering (GSC) method that enables principled clustering of weakly connected digraphs.
  arXiv  Detail & Related papers  (2022-03-07T09:18:42Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-07-07T16:51:39Z)
• Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification [50.83222170524406]
  We study the intrinsic difficulty in graph classification under the unified concept of resolution dilemmas'' We propose SLIM'', an inductive neural network model for Structural Landmarking and Interaction Modelling.
  arXiv  Detail & Related papers  (2020-06-29T01:01:42Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.