Graph Construction

Follow this topic Ask about this topic

Latest papers

14 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Exact Topological Compliance: Generating Persistence-Equivalent Graphs
Oct 13, 2026Mattie Ji, Indradyumna Roy, Vikas GargGraph Construction Constrained Generative Modeling
University of Pennsylvania · Equal Contributions. · Aalto University +1
Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion
Oct 8, 2026Zeru Zhu, Marco Gamarra, Ji LiuGraph Construction Topology Optimization
Department of Applied Mathematics and Statistics at Stony Brook University · Air Force Research Laboratory · Department of Electrical and Computer Engineering at Stony Brook University
A Comparative Study of Graph Representations for GNN-Based Power Grid Control in L2RPN
Sep 2, 2026Adrian Degenkolb, Qiong Huang, Benjamin SchäferGraph Construction Power Systems
Karlsruhe Institute of Technology Karlsruhe, Germany
RamseyGadgets: A Graph Construction Dataset for LLMs
Aug 15, 2026Zohair Raza Hassan, Deepak PanditaGraph Construction Graph Generation
Rochester Institute of Technology, NY, USA
Neurosymbolic Discovery of Algebraic Graph Constructions
Aug 8, 2026David Seka, Stefan SzeiderGraph Construction Neuro-Symbolic Reasoning
Algorithms and Complexity Group TU Wien, Vienna, Austria
Graph Machine: Exploring Edge Mechanisms as an Inductive Bias
Aug 7, 2026Lintai HouGraph Structure Learning Neural Algorithmic Reasoning
Iter Labs
TraversRL: Traversable Pedestrian Pathway Generation With Reinforcement Learning
Jul 20, 2026Bin Han, Robert Wolfe, Bill HoweRemote Sensing Image Understanding Reinforcement Learning
University of Washington · Rutgers University
Visual graphs for image classification: does the structure affect performance?
Jul 7, 2026Alessandra IbbaGraph Structure Learning Graph Neural Networks
University of Sassari - Department of Engineering, Sassari, Italy
RankGraph-2: Lifecycle Co-Design for Billion-Node Graph Learning in Recommendation
Jun 16, 2026Renzhi Wu, Zikun Cui, Junjie Yang +10Graph Representation Learning Graph Construction
Meta MRS · Meta Training Data Infra · FB Monetization
Learning Minimally Rigid Graphs with High Realization Counts
May 12, 2026Oleksandr Slyvka, Jan Rubeš, Rodrigo Alves +1RL for Combinatorial Optimization Graph Construction
Faculty of Information Technology, Czech Technical University in Prague, Czechia · ETH ZÜrich, Switzerland
New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search
May 1, 2026Jay Bhan, Nicole Nobili, Patrick LangerGraph Construction
ETH Zürich Zürich, Switzerland 8092 · Stanford University Stanford, CA 94305
Robustness of Spatio-temporal Graph Neural Networks for Fault Location in Partially Observable Distribution Grids
Apr 22, 2026Burak Karabulut, Carlo Manna, Chris DevelderAnomaly Localization Graph Neural Networks
Ghent University – imec · VITO
a-TMFG: Scalable Triangulated Maximally Filtered Graphs via Approximate Nearest Neighbors
Mar 10, 2026Lionel YelibiGraph Construction Graph Sparsification
Department of Statistical Sciences, University of Cape Town, Rondebosch, 7701, Cape Town, Western Cape, South Africa
How the Graph Construction Technique Shapes Performance in IoT Botnet Detection
Feb 28, 2026Hassan Wasswa, Hussein Abbass, Timothy LynarGraph Construction IoT Intrusion Detection
School of Systems and Computing, University of New South Wales, Canberra, 2600 ACT Australia

Oct 13, 2026J/K move · Enter open · S save

Exact Topological Compliance: Generating Persistence-Equivalent Graphs

Mattie Ji, Indradyumna Roy, Vikas Garg

University of Pennsylvania · Equal Contributions. · Aalto University+1

Graph Construction Constrained Generative Modeling Persistent Homology

Open paper AskPDF arXiv

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 between sample diversity and reaching infeasible states. We therefore recast generation as a global constraint satisfaction problem with a complete encoding solvable by modern constraint programming solvers. This is applicable to any vertex-based permutation equivariant filtration scheme and is minimal under the degree filtration. Experiments on four standard graph generation benchmarks confirm that both methods realize the target PD exactly. Together, our methods provide a principled treatment of strict topology-compliant graph generation. Code is available at https://github.com/Aalto-QuML/ExactCompliance.