Graph Theory and Algorithms

Latest papers

• Supplementary Materials to Graph Convolutional Branch and Bound

  Lorenzo Sciandra, Roberto Esposito, Andrea Cesare Grosso, Laura Sacerdote, Cristina Zucca · 6 April 2026

  This article explores the integration of deep learning models into combinatorial optimization pipelines, specifically targeting NP-hard problems. Traditional exact algorithms for such problems often rely on heuristic criteria to guide the exploration of feasible solutions. In this work, we propose u…

• Hierarchical Discrete Flow Matching for Graph Generation

  Yoann Boget, Pablo Strasser, Alexandros Kalousis · 2 April 2026

  Denoising-based models, including diffusion and flow matching, have led to substantial advances in graph generation. Despite this progress, such models remain constrained by two fundamental limitations: a computational cost that scales quadratically with the number of nodes and a large number of fun…

• Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

  Selin Bayramo\u{g}lu, George L Nemhauser, Nikolaos V Sahinidis · 2 April 2026

  Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typ…

• Contextual Graph Matching with Correlated Gaussian Features

  Mohammad Hassan Ahmad Yarandi, Luca Ganassali · 25 March 2026

  We investigate contextual graph matching in the Gaussian setting, where both edge weights and node features are correlated across two networks. We derive precise information-theoretic thresholds for exact recovery, and identify conditions under which almost exact recovery is possible or impossible, …

• MS-DGCNN++: Multi-Scale Dynamic Graph Convolution with Scale-Dependent Normalization for Robust LiDAR Tree Species Classification

  Said Ohamouddou, Hanaa El Afia, Mohamed Hamza Boulaich, Abdellatif El Afia, Raddouane Chiheb · 25 March 2026

  Graph-based deep learning on LiDAR point clouds encodes geometry through edge features, yet standard implementations use the same encoding at every scale. In tree species classification, where point density varies by orders of magnitude between trunk and canopy, this is particularly limiting. We pro…

• Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning

  Kaiyang Li, Shihao Ji, Zhipeng Cai, Wei Li · 20 March 2026

  Approximate subgraph matching (ASM) is a task that determines the approximate presence of a given query graph in a large target graph. Being an NP-hard problem, ASM is critical in graph analysis with a myriad of applications ranging from database systems and network science to biochemistry and priva…

• Byte-token Enhanced Language Models for Temporal Point Processes Analysis

  Quyu Kong, Yixuan Zhang, Yang Liu, Panrong Tong, Enqi Liu, Feng Zhou · 19 March 2026

  Temporal Point Processes (TPPs) have been widely used for modeling event sequences on the Web, such as user reviews, social media posts, and online transactions. However, traditional TPP models often struggle to effectively incorporate the rich textual descriptions that accompany these events, while…

• MICRO: A Lightweight Middleware for Optimizing Cross-store Cross-model Graph-Relation Joins [Technical Report]

  Xiuwen Zheng, Arun Kumar, Amarnath Gupta · 17 March 2026

  Modern data applications increasingly involve heterogeneous data managed in different models and stored across disparate database engines, often deployed as separate installs. Limited research has addressed cross-model query processing in federated environments. This paper takes a step toward bridgi…

• Persistent Autoregressive Mapping with Traffic Rules for Autonomous Driving

  Shiyi Liang, Xinyuan Chang, Changjie Wu, Huiyuan Yan, Yifan Bai, Xinran Liu, Hang Zhang, Yujian Yuan, Shuang Zeng, Mu Xu, Xing Wei · 17 March 2026

  Safe autonomous driving requires both accurate HD map construction and persistent awareness of traffic rules, even when their associated signs are no longer visible. However, existing methods either focus solely on geometric elements or treat rules as temporary classifications, failing to capture th…

• Instruction set for the representation of graphs

  Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez · 12 March 2026

  We present IsalGraph, a method for representing the structure of any finite, simple graph as a compact string over a nine-character instruction alphabet. The encoding is executed by a small virtual machine comprising a sparse graph, a circular doubly-linked list (CDLL) of graph-node references, and …

• Towards Neural Graph Data Management

  Yufei Li, Yisen Gao, Jiaxin Bai, Jiaxuan Xiong, Haoyu Huang, Zhongwei Xie, Hong Ting Tsang, Yangqiu Song · 9 March 2026

  While AI systems have made remarkable progress in processing unstructured text, structured data such as graphs stored in databases, continues to grow rapidly yet remains difficult for neural models to effectively utilize. We introduce NGDBench, a unified benchmark for evaluating neural graph databas…

• Bures-Wasserstein Flow Matching for Graph Generation

  Keyue Jiang, Jiahao Cui, Xiaowen Dong, Laura Toni · 6 March 2026

  Graph generation has emerged as a critical task in fields ranging from drug discovery to circuit design. Contemporary approaches, notably diffusion and flow-based models, have achieved solid graph generative performance through constructing a probability path that interpolates between reference and …

• Effective Sample Size and Generalization Bounds for Temporal Networks

  Barak Gahtan, Alex M. Bronstein · 5 March 2026

  Learning from time series is fundamentally different from learning from i.i.d.\ data: temporal dependence can make long sequences effectively information-poor, yet standard evaluation protocols conflate sequence length with statistical information. We propose a dependence-aware evaluation methodolog…

• GCL-Sampler: Discovering Kernel Similarity for Sampled GPU Simulation via Graph Contrastive Learning

  Jiaqi Wang, Jingwei Sun, Jiyu Luo, Han Li, Guangzhong Sun · 3 March 2026

  GPU architectural simulation is orders of magnitude slower than native execution, necessitating workload sampling for practical speedups. Existing methods rely on hand-crafted features with limited expressiveness, yielding either aggressive sampling with high errors or conservative sampling with con…

• Wave-Attractor-Tree: A Hierarchical Binary Tree Reduction Architecture for Efficient Sequence Modeling

  Igor Berezkin · 3 March 2026

  Work introduces a hierarchical binary tree-based reduction that replaces standard self-attention. The core idea is to use a recursive Gated Linear Unit merge operation, achieving O(n) total merge operations O(log n) parallel depth O(n d^2) total work and O(n) space complexity. In these experiments, …

• LEAP: Local ECT-Based Learnable Positional Encodings for Graphs

  Juan Amboage, Ernst R\"oell, Patrick Schnider, Bastian Rieck · 3 March 2026

  Graph neural networks (GNNs) largely rely on the message-passing paradigm, where nodes iteratively aggregate information from their neighbors. Yet, standard message passing neural networks (MPNNs) face well-documented theoretical and practical limitations. Graph positional encoding (PE) has emerged …

• pathsig: A GPU-Accelerated Library for Truncated and Projected Path Signatures

  Tobias Nygaard · 2 March 2026

  Path signatures provide a rich representation of sequential data, with strong theoretical guarantees and good performance in a variety of machine-learning tasks. While signatures have progressed from fixed feature extractors to trainable components of machine-learning models, existing libraries ofte…

• Democratizing GraphRAG: Linear, CPU-Only Graph Retrieval for Multi-Hop QA

  Qizhi Wang · 2 March 2026

  GraphRAG systems improve multi-hop retrieval by modeling structure, but many approaches rely on expensive LLM-based graph construction and GPU-heavy inference. We present SPRIG (Seeded Propagation for Retrieval In Graphs), a CPU-only, linear-time, token-free GraphRAG pipeline that replaces LLM graph…

• Global graph features unveiled by unsupervised geometric deep learning

  Mirja Granfors, Jes\'us Pineda, Blanca Zufiria Gerbol\'es, Joana B. Pereira, Carlo Manzo, Giovanni Volpe · 27 February 2026

  Graphs provide a powerful framework for modeling complex systems, but their structural variability poses significant challenges for analysis and classification. To address these challenges, we introduce GAUDI (Graph Autoencoder Uncovering Descriptive Information), a novel unsupervised geometric deep…

• Rethinking Flexible Graph Similarity Computation: One-step Alignment with Global Guidance

  Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Shuai Ma, Dongsheng Li · 26 February 2026

  Graph Edit Distance (GED) is a widely used measure of graph similarity, valued for its flexibility in encoding domain knowledge through operation costs. However, existing learning-based approximation methods follow a modeling paradigm that decouples local candidate match selection from both operatio…

• GEDAN: Learning the Edit Costs for Graph Edit Distance

  Francesco Leonardi, Markus Orsi, Jean-Louis Reymond, Kaspar Riesen · 24 February 2026

  Graph Edit Distance (GED) is defined as the minimum cost transformation of one graph into another and is a widely adopted metric for measuring the dissimilarity between graphs. The major problem of GED is that its computation is NP-hard, which has in turn led to the development of various approximat…

• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions

  Yaowen Liu, Xuejia Chen, Anxin Tian, Haoyang Li, Qinbin Li, Xin Zhang, Alexander Zhou, Chen Jason Zhang, Qing Li, Lei Chen · 20 February 2026

  Approximate Nearest Neighbor Search (ANNS) underpins many large-scale data mining and machine learning applications, with efficient retrieval increasingly hinging on GPU acceleration as dataset sizes grow. Although graph-based approaches represent the state of the art in approximate nearest neighbor…

• Learning Admissible Heuristics for A*: Theory and Practice

  Ehsan Futuhi, Nathan R. Sturtevant · 18 February 2026

  Heuristic functions are central to the performance of search algorithms such as A-star, where admissibility - the property of never overestimating the true shortest-path cost - guarantees solution optimality. Recent deep learning approaches often disregard admissibility and provide limited guarantee…

• Hippocampus: An Efficient and Scalable Memory Module for Agentic AI

  Yi Li, Lianjie Cao, Faraz Ahmed, Puneet Sharma, Bingzhe Li · 17 February 2026

  Agentic AI require persistent memory to store user-specific histories beyond the limited context window of LLMs. Existing memory systems use dense vector databases or knowledge-graph traversal (or hybrid), incurring high retrieval latency and poor storage scalability. We introduce Hippocampus, an ag…

• Text2GQL-Bench: A Text to Graph Query Language Benchmark [Experiment, Analysis & Benchmark]

  Songlin Lyu, Lujie Ban, Zihang Wu, Tianqi Luo, Jirong Liu, Chenhao Ma, Yuyu Luo, Nan Tang, Shipeng Qi, Heng Lin, Yongchao Liu, Chuntao Hong · 13 February 2026

  Graph models are fundamental to data analysis in domains rich with complex relationships. Text-to-Graph-Query-Language (Text-to-GQL) systems act as a translator, converting natural language into executable graph queries. This capability allows Large Language Models (LLMs) to directly analyze and man…