Graph Theory and Algorithms

Neueste Paper

• Corpus-Guided Dual-Path Propagation for Graph Retrieval-Augmented Generation

  Baoxian Liu, Tong Wei · 1. Oktober 2026

  Graph-based retrieval-augmented generation supports multi-hop retrieval by organizing corpus information into graphs. However, existing relation-free graph retrieval methods rely primarily on query-sentence similarity to search for evidence. This can exclude useful bridging evidence with low query s…

• Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning

  Fangzhou Wu, Haike Xu, Sandeep Silwal · 30. September 2026

  Graph-based approximate nearest neighbor search (ANNS) is widely used for large-scale semantic search. Its indices are constructed primarily based on geometric relationships among embeddings of an input dataset (e.g., documents or images), rather than explicitly optimizing for semantic relevance. Ho…

• Graph Matching Relaxations and Amortization for Supervised Graph Prediction

  Federico M\'endez, Paul Krzakala, Gabriel Melo, Charlotte Laclau, R\'emi Flamary, Florence d'Alch\'e-Buc · 28. September 2026

  End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoret…

• Moment-guided edge sampling

  Weibin Cai, Reza Zafarani · 28. September 2026

  Edge sampling makes local decisions to achieve graph-level objectives, such as preserving structural properties. This creates a fundamental challenge: \textit{how can the effect of a local edge edit (i.e., edge addition or removal) on global graph structure be quantified and controlled?} We address …

• AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs

  Xiaochen Zhang, Haoyu Zhu, Yao Zhang, Qingchun Hou · 25. September 2026

  Graph-structured optimization with linear constraints is fundamental to critical infrastructure but faces scalability limits due to massive strict hard constraints and high dimensionality. While recent projection-based methods such as Trainable Sampling Kaczmarz-Motzkin Net (T-SKM-Net) guarantee fea…

• Scalable Subgraph Sampling via Resistance Curvature

  Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li · 24. September 2026

  Subgraph sampling reduces the training cost of large-scale graph neural networks, but sampling criteria may overlook the geometric roles of edges. We propose a resistance-curvature-guided sampling framework built on ERC-LG, a curvature approximation method for large-scale graphs. ERC-LG combines Joh…

• TWIG: A Time-Causal Wavelet Operator for Autoregressive Forecasting on Irregular Graphs

  Subashree Venkatasubramanian, David A. Barajas-Solano, Chuyang Liu, Daniel M. Tartakovsky, Dipankar Dwivedi · 22. September 2026

  We introduce TWIG (Time-Causal Wavelet Operator for Irregular Graphs), a graph-native neural operator for autoregressive surrogate modeling on static irregular graphs. TWIG transforms each node history into causal multiscale temporal features that separate recent variation from progressively slower …

• Visual Graph Reasoning via Knowledge Compilation

  Rongzheng Wang, Zhe Wang, Ke Qin, Rongwei Wang, Muquan Li, Yizhuo Ma, Yihong Huang, Jielei Wang, Shuang Liang · 22. September 2026

  Visual graph reasoning requires answering graph-theoretic questions directly from graph images, where graph topology and state are conveyed visually rather than given in symbolic form. Despite recent progress of vision-language models (VLMs), current approaches to visual graph reasoning still fail o…

• Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

  Tung Tran, Viet Bao Mai, Hoang Ta, Tuan Dam · 18. September 2026

  Tree-based Monte-Carlo Tree Search (MCTS) duplicates the same state when it is reached through different trajectories, which can waste simulations in stochastic MDPs. We introduce Graph-Based Stochastic-Power-UCT (GS-Power-UCT), which shares states reached at the same planning depth while keeping se…

• On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman

  Fan Yang · 16. September 2026

  Whitney's theorem allows isomorphism testing for connected simple graphs, apart from $K_3$ and $K_{1,3}$, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We…

• Geometry vs Structure: Graph-Based Diagnostics for LiDAR Point-Cloud Simulation Fidelity

  Ghazal Farhani, Taufiq Rahman · 16. September 2026

  Digital twins provide a scalable and cost-effective complement to real-world testing for validating autonomous-driving and advanced driver-assistance system (ADAS) sensor pipelines. However, quantifying their fidelity remains challenging, particularly for 3D LiDAR point clouds, where conventional ge…

• Interpolation Is Not Invariance: Pair Count Is Not Coverage in Transformation Audits

  Mohammed Ahnouch, Lotfi Elaachak · 15. September 2026

  Counting equivalent pairs is a common way to report transformation-audit coverage, but it can substantially overstate the constraints imposed by an audit: pairs generated from the same semantic object are correlated, and complete orbit graphs contain algebraically redundant edges. We therefore disti…

• GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs

  Zixiang Xu, Yanbo Wang, Chenxi Wang, Lang Gao, Zirui Song, Yue Huang, Zhaorun Chen, Xiangliang Zhang, Xiuying Chen · 14. September 2026

  Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasonin…

• From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs

  Shuyuan Zhang, Zihan Wang, Xiao-Wen Chang, Doina Precup · 11. September 2026

  The integration of graphs with Goal-Conditioned Hierarchical Reinforcement Learning (GCHRL) has received increasing attention, as graphs naturally encode task hierarchies for effective subgoal sampling. However, existing methods often overlook intrinsic connectivity information, failing to fully lev…

• TIGPO: Temporal Instance-Graph Policy Optimization for Long-Horizon LLM Agents

  Jinwei Gan · 4. September 2026

  Graph-based policy optimization improves credit assignment for long-horizon LLM agents by organizing rollout trajectories into state-transition graphs. However, existing methods construct graphs independently within each policy update, discarding transitions discovered by earlier policies and limiti…

• TRACE: Spatiotemporal Contact Memory Graph Network Simulator for Granular Dynamics

  Changjian Zhou, Negin Yousefpour, Jie Qi, Junfeng Fang, Guillermo A. Narsilio, Hans Petter Jostad · 4. September 2026

  Learned graph simulators provide an efficient alternative to high-fidelity solvers for granular dynamics. However, granular motion depends strongly on inter-granular contact history, which is difficult to preserve when particle contacts form, break, and rearrange. Existing simulators mainly store te…

• Evaluating Graph Neural Networks for Change-Criticality Classification in Maritime Navigation Charts

  Abhishek Potnis, Jacob Arndt · 4. September 2026

  Graph neural networks (GNNs) are a class of neural networks suitable for learning on graph-structured data. Their application to spatial data is a natural extension, however its relatively unclear which message-passing operations, architectural configurations, and graph representation is best suited…

• Seed-Anchored Budget-Bounded Graph Rendering for Question Answering on Industry-Standard Power-Grid Information and Exchange Models

  Jayakumar Manoharan, Yamini Sehgal · 3. September 2026

  Large language model question answering over power-grid models must respect a fixed context budget. We introduce seed-anchored graph rendering, a deterministic method that prioritizes query-local graph evidence without adding method-specific tuned or learned parameters beyond the shared hop bound an…

• Relational-Core Graph Analytics Querying graphs at SQL scale, and why the node/edge model is a performance tax, not a truer picture of connected data

  Gene Zhang · 2. September 2026

  A durable assumption holds that graph analytics requires a purpose-built graph engine, and that relational systems are ill-suited to connected data. We argue the opposite for the workloads enterprises actually run. A columnar relational engine fronted by a graph query language matches or exceeds nat…

• GraphMemix: Query-Aware Evidence Forests for Long-Term Multimodal Agent Memory

  Geng Li, Yuhao Wang, Dong Li, Jianye Hao, Yuxin Peng · 28. August 2026

  Organizing long-term memory for multimodal agents remains challenging because existing methods either suffer from expensive question-agnostic offline summaries or naive embedding similarity matching that introduces incomplete and redundant context. To address these issues, we propose GraphMemix, a c…

• Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs

  Krzysztof Choromanski, Isaac Reid, Arijit Sehanobish, Avinava Dubey · 27. August 2026

  We present the first linear time complexity randomized algorithms for unbiased approximation of the celebrated family of general random walk kernels (RWKs) for sparse graphs. This includes both labelled and unlabelled instances. The previous fastest methods for general RWKs were of cubic time comple…

• M-Fibration Theory with Applications to Neural Network Compression

  Paolo Boldi · 27. August 2026

  The purpose of this paper is to provide a general, comprehensive, theoretical framework that allows one to deal with fibrations on graphs labelled on a commutative monoid. This is a genuine extension of the theory of graph fibrations (as introduced in "Fibrations of Graphs" [Discrete Math., vol. 243…

• Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)

  Tong Qi, Vera Andersson, Peter Viechnicki, Vince Lyzinski · 26. August 2026

  We present the OmniMatch algorithm for seeded multiple graph matching. In the setting of $d$-dimensional Random Dot Product Graphs (RDPG), we prove that under mild assumptions, OmniMatch with $s$ seeds asymptotically and efficiently perfectly aligns $O(s^{\alpha})$ unseeded vertices -- for $\alpha<2…

• Coarse Indexing, Fine Evidence: Decoupling Temporal Granularity in Long-Video RAG

  Zhe Jin, Zhimin Lin, Bin Zheng, Junhua Fang, Huihua Yang · 25. August 2026

  Graph-based retrieval-augmented generation (RAG) provides a scalable paradigm for long-video understanding, but existing systems typically inherit a fixed temporal granularity from video segmentation when constructing their retrieval index. We argue that this design unnecessarily couples indexing gr…

• RamseyGadgets: A Graph Construction Dataset for LLMs

  Zohair Raza Hassan, Deepak Pandita · 18. August 2026

  Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs a…