Graph Theory and Algorithms

Neueste Paper

• GraphSeek: Next-Generation Graph Analytics with LLMs

  Maciej Besta, {\L}ukasz Jarmocik, Orest Hrycyna, Shachar Klaiman, Konrad M\k{a}czka, Robert Gerstenberger, J\"urgen M\"uller, Piotr Nyczyk, Hubert Niewiadomski, Torsten Hoefler · 12. Februar 2026

  Graphs are foundational across domains but remain hard to use without deep expertise. LLMs promise accessible natural language (NL) graph analytics, yet they fail to process industry-scale property graphs effectively and efficiently: such datasets are large, highly heterogeneous, structurally comple…

• Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance

  Mamoona Ghafoor, Tatsuya Akutsu · 3. Februar 2026

  The generation of trees with a specified tree edit distance has significant applications across various fields, including computational biology, structured data analysis, and image processing. Recently, generative networks have been increasingly employed to synthesize new data that closely resembles…

• Qrita: High-performance Top-k and Top-p Algorithm for GPUs using Pivot-based Truncation and Selection

  Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica · 3. Februar 2026

  Top-k and Top-p are the dominant truncation operators in the sampling of large language models. Despite their widespread use, implementing them efficiently over large vocabularies remains a significant challenge. Existing approaches often rely on sorting, which incur significant computation and memo…

• Taxonomy of reduction matrices for Graph Coarsening

  Antonin Joly, Nicolas Keriven, Aline Roumy · 29. Januar 2026

  Graph coarsening aims to diminish the size of a graph to lighten its memory footprint, and has numerous applications in graph signal processing and machine learning. It is usually defined using a reduction matrix and a lifting matrix, which, respectively, allows to project a graph signal from the or…

• PowerGraph-LLM: Novel Power Grid Graph Embedding and Optimization with Large Language Models

  Fabien Bernier, Jun Cao, Maxime Cordy, Salah Ghamizi · 28. Januar 2026

  Efficiently solving Optimal Power Flow (OPF) problems in power systems is crucial for operational planning and grid management. There is a growing need for scalable algorithms capable of handling the increasing variability, constraints, and uncertainties in modern power networks while providing accu…

• Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

  Zekai Huang, Yingyu Liang, Zhenmei Shi, Zhao Song, Zhen Zhuang · 27. Januar 2026

  Looped Transformers have shown exceptional neural algorithmic reasoning capability in simulating traditional graph algorithms, but their application to more complex structures like hypergraphs remains underexplored. Hypergraphs generalize graphs by modeling higher-order relationships among multiple …

• Graph Recognition via Subgraph Prediction

  Andr\'e Eberhard, Gerhard Neumann, Pascal Friederich · 22. Januar 2026

  Despite tremendous improvements in tasks such as image classification, object detection, and segmentation, the recognition of visual relationships, commonly modeled as the extraction of a graph from an image, remains a challenging task. We believe that this mainly stems from the fact that there is n…

• Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs

  Yichun Yang, Longlong Lin, Rong-Hua Li, Meihao Liao, Guoren Wang · 19. Januar 2026

  The computation of resistance distance is pivotal in a wide range of graph analysis applications, including graph clustering, link prediction, and graph neural networks. Despite its foundational importance, efficient algorithms for computing resistance distances on large graphs are still lacking. Ex…

• SwiftMem: Fast Agentic Memory via Query-aware Indexing

  Anxin Tian, Yiming Li, Xing Li, Hui-Ling Zhen, Lei Chen, Xianzhi Yu, Zhenhua Dong, Mingxuan Yuan · 14. Januar 2026

  Agentic memory systems have become critical for enabling LLM agents to maintain long-term context and retrieve relevant information efficiently. However, existing memory frameworks suffer from a fundamental limitation: they perform exhaustive retrieval across the entire storage layer regardless of q…

• ToolACE-MCP: Generalizing History-Aware Routing from MCP Tools to the Agent Web

  Zhiyuan Yao, Zishan Xu, Yifu Guo, Zhiguang Han, Cheng Yang, Shuo Zhang, Weinan Zhang, Xingshan Zeng, Weiwen Liu · 14. Januar 2026

  With the rise of the Agent Web and Model Context Protocol (MCP), the agent ecosystem is evolving into an open collaborative network, exponentially increasing accessible tools. However, current architectures face severe scalability and generality bottlenecks. To address this, we propose ToolACE-MCP, …

• CRoPE: Efficient Parametrization of Rotary Positional Embedding

  Beicheng Lou, Zifei Xu · 7. Januar 2026

  Rotary positional embedding has become the state-of-the-art approach to encode position information in transformer-based models. While it is often succinctly expressed in complex linear algebra, we note that the actual implementation of $Q/K/V$-projections is not equivalent to a complex linear trans…

• DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs

  Dongyuan Li, Shiyin Tan, Ying Zhang, Ming Jin, Shirui Pan, Manabu Okumura, Renhe Jiang · 19. Dezember 2025

  Dynamic graph modeling aims to uncover evolutionary patterns in real-world systems, enabling accurate social recommendation and early detection of cancer cells. Inspired by the success of recent state space models in efficiently capturing long-term dependencies, we propose DyG-Mamba by translating d…

• PyGraph: Robust Compiler Support for CUDA Graphs in PyTorch

  Abhishek Ghosh, Ajay Nayak, Ashish Panwar, Arkaprava Basu · 18. Dezember 2025

  Machine learning (ML) workloads launch hundreds to thousands of short-running GPU kernels per iteration. With GPU compute throughput growing rapidly, CPU-side launch latency of kernels is emerging as a bottleneck. CUDA Graphs promise to address this by replaying a set of kernels with a single dispat…

• Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks

  Shuyang Guo, Wenjin Xie, Ping Lu, Ting Deng, Richong Zhang, Jianxin Li, Xiangping Huang, Zhongyi Liu · 18. Dezember 2025

  Homomorphism is a key mapping technique between graphs that preserves their structure. Given a graph and a pattern, the subgraph homomorphism problem involves finding a mapping from the pattern to the graph, ensuring that adjacent vertices in the pattern are mapped to adjacent vertices in the graph.…

• Toward a Unified Geometry Understanding: Riemannian Diffusion Framework for Graph Generation and Prediction

  Yisen Gao, Xingcheng Fu, Qingyun Sun, Jianxin Li, Xianxian Li · 12. Dezember 2025

  Graph diffusion models have made significant progress in learning structured graph data and have demonstrated strong potential for predictive tasks. Existing approaches typically embed node, edge, and graph-level features into a unified latent space, modeling prediction tasks including classificatio…

• Architecture-Aware Generalization Bounds for Temporal Networks: Theory and Fair Comparison Methodology

  Barak Gahtan, Alex M. Bronstein · 9. Dezember 2025

  Deep temporal architectures such as TCNs achieve strong predictive performance on sequential data, yet theoretical understanding of their generalization remains limited. We address this gap through three contributions: introducing an evaluation methodology for temporal models, revealing surprising e…

• On the identifiability of causal graphs with multiple environments

  Francesco Montagna · 3. Dezember 2025

  Causal discovery from i.i.d. observational data is known to be generally ill-posed. We demonstrate that if we have access to the distribution of a structural causal model, and additional data from only two environments that sufficiently differ in the noise statistics, the unique causal graph is iden…

• On detection probabilities of link invariants

  Tuomas Kelom\"aki, Abel Lacabanne, Daniel Tubbenhauer, Pedro Vaz, Victor L. Zhang · 2. Dezember 2025

  We prove that the detection rate of n-crossing alternating links by many standard link invariants decays exponentially in n, implying that they detect alternating links with probability zero. This phenomenon applies broadly, in particular to the Jones and HOMFLYPT polynomials and integral Khovanov h…

• Neural Graph Navigation for Intelligent Subgraph Matching

  Yuchen Ying, Yiyang Dai, Wenda Li, Wenjie Huang, Rui Wang, Tongya Zheng, Yu Wang, Hanyang Yuan, Mingli Song · 25. November 2025

  Subgraph matching, a cornerstone of relational pattern detection in domains ranging from biochemical systems to social network analysis, faces significant computational challenges due to the dramatically growing search space. Existing methods address this problem within a filtering-ordering-enumerat…

• Gradient-Based Join Ordering

  Tim Schwabe, Maribel Acosta · 19. November 2025

  Join ordering is the NP-hard problem of selecting the most efficient sequence in which to evaluate joins (conjunctive, binary operators) in a database query. As the performance of query execution critically depends on this choice, join ordering lies at the core of query optimization. Traditional app…

• JEDI-linear: Fast and Efficient Graph Neural Networks for Jet Tagging on FPGAs

  Zhiqiang Que, Chang Sun, Sudarshan Paramesvaran, Emyr Clement, Katerina Karakoulaki, Christopher Brown, Lauri Laatu, Arianna Cox, Alexander Tapper, Wayne Luk, Maria Spiropulu · 18. November 2025

  Graph Neural Networks (GNNs), particularly Interaction Networks (INs), have shown exceptional performance for jet tagging at the CERN High-Luminosity Large Hadron Collider (HL-LHC). However, their computational complexity and irregular memory access patterns pose significant challenges for deploymen…

• Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation

  Jinglei Cheng, Ruilin Zhou, Yuhang Gan, Chen Qian, Junyu Liu · 18. November 2025

  We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structu…

• From Small to Large: A Graph Convolutional Network Approach for Solving Assortment Optimization Problems

  Guokai Li, Pin Gao, Stefanus Jasin, Zizhuo Wang · 18. November 2025

  Assortment optimization seeks to select a subset of substitutable products, subject to constraints, to maximize expected revenue. The problem is NP-hard due to its combinatorial and nonlinear nature and arises frequently in industries such as e-commerce, where platforms must solve thousands of such …

• Rethinking Parameter Sharing as Graph Coloring for Structured Compression

  Boyang Zhang, Daning Cheng, Yunquan Zhang · 11. November 2025

  Modern deep models have massive parameter sizes, leading to high inference-time memory usage that limits practical deployment. Parameter sharing, a form of structured compression, effectively reduces redundancy, but existing approaches remain heuristic-restricted to adjacent layers and lacking a sys…

• Charting the Design Space of Neural Graph Representations for Subgraph Matching

  Vaibhav Raj, Indradyumna Roy, Ashwin Ramachandran, Soumen Chakrabarti, Abir De · 28. Oktober 2025

  Subgraph matching is vital in knowledge graph (KG) question answering, molecule design, scene graph, code and circuit search, etc. Neural methods have shown promising results for subgraph matching. Our study of recent systems suggests refactoring them into a unified design space for graph matching n…