Graph Theory and Algorithms

Derniers papiers

• RIDGECUT: Learning Graph Partitioning with Rings and Wedges

  Qize Jiang, Angelo Zangari, Linsey Pang, Alice Gatti, Mahima Aggarwal, Giovanna Vantini, Xiaosong Ma, Weiwei Sun, Sourav Medya, Sanjay Chawla · 16 juin 2026

  Reinforcement learning (RL) has shown promise for combinatorial optimization problems on graphs by learning heuristics that generalize across instances. However, effectively incorporating domain knowledge into RL frameworks for graph partitioning remains challenging, as existing approaches typically…

• Using Reinforcement Learning to Optimize the Global and Local Crossing Number

  Timo Brand, Henry F\"orster, Stephen Kobourov, Daniel Kohrt, Robin Schukrafft, Markus Wallinger, Johannes Zink · 16 juin 2026

  Graph drawing concerns the algorithmic visualization of graphs. A good drawing of a graph is easy to read and facilitates solving tasks on the graph. Several properties have been identified to occur in good drawings of graphs. Such properties include a low number of crossings, large angles between e…

• IntentKV: Cross-Turn Intent-Aware KV Cache Pruning for Agent Inference

  Junjie Li, Jiong Lou, Jie Li · 10 juin 2026

  Multi-turn LLM agents fan short queries into long trajectories of tool calls, search results, and intermediate reasoning. Both KV memory and KV read bandwidth grow by orders of magnitude across a single trajectory, making the key-value (KV) cache, not parameter compute, the dominant serving bottlene…

• When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding

  Xu Yang, Lunyiu Nie, Ethan Chandra, Stanislav Gannutin, Fangru Lin, Swarat Chaudhuri · 2 juin 2026

  Multi-agent Large Language Model (LLM) systems offer a way to decompose complex tasks, such as coding, through parallelization and context isolation. However, adding agents in practice introduces inter-agent communication overhead, which incurs extra cost and can sometimes offset the efficiency gain…

• NGDBench: Towards Neural Graph Data Management

  Yufei Li, Yisen Gao, Jiaxuan Xiong, Jiaxin Bai, Shijie Zhong, Haoyu Huang, Zhongwei Xie, Hong Ting Tsang, Yangqiu Song · 1 juin 2026

  Data critical to real-world decision-making is increasingly found within organizations. Such data is heterogeneous, constantly evolving, and only imperfectly captured. However, current data management systems remain largely passive, retrieving what is explicitly stored while offering limited support…

• DynaGraph: Lightweight Multi-Model Interaction Framework via Dynamic Topological Reconfiguration

  Yanxing Guo, Zihao Zheng, Fangzhou Wu, Ling Liang, Lin Bao, Zongwei Wang, Yimao Cai · 29 mai 2026

  Tackling complex reasoning tasks typically relies on massive monolithic LLMs, which suffer from severe computational redundancy. While task decomposition through structured pipelines or multi-agent collaborations offers an alternative, these approaches inevitably fall into a critical dilemma: predef…

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

  Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica · 27 mai 2026

  Despite their importance in model sampling, efficient implementation of Top-k and Top-p algorithms for large vocabularies remains a significant challenge. Existing approaches often rely on sorting, which incurs significant computation and memory overhead on GPUs, or on stochastic approaches that alt…

• Subspace Aggregation Query and Index Generation for Multidimensional Resource Space Model

  Xiaoping Sun, Hai Zhuge · 26 mai 2026

  Organizing large-scale resources in a multidimensional semantic space is an approach to efficiently managing and querying resources from different semantic dimensions. To support advanced applications, this paper proposes a resource space model for aggregation query on subspaces defined by a range w…

• TGFormer: Towards Temporal Graph Transformer with Auto-Correlation Mechanism

  Hongjiang Chen, Pengfei Jiao, Ming Du, Xuan Guo, Zhidong Zhao, Di Jin, Xiao Liu · 26 mai 2026

  The growing interest in Temporal Graph Neural Networks (TGNNs) stems from their ability to model complex dynamics and deliver superior performance. However, TGNNs encounter fundamental challenges in capturing long-term dependencies and identifying periodic patterns. To address these limitations, we …

• Building Deep Graph Predictors with Graph Imitation Learning

  Andr\'e Eberhard, Gerhard Neumann, Pascal Friederich · 21 mai 2026

  Recent years have seen substantial progress in neural generation of text, images, and audio, supported by mature training pipelines and large-scale optimization. For graphs, however, comparable progress has been more limited. We attribute this gap to graph-specific optimization and representation ch…

• LARGER: Lexically Anchored Repository Graph Exploration and Retrieval

  Yuntong Hu, Tongli Su, Liang Zhao, Bowen Zhu, Hasibul Haque · 19 mai 2026

  Repository-level coding agents must first localize the files and symbols relevant to a task; failures at this stage can cascade across downstream objectives ranging from patch generation to test writing and codebase question answering. Existing agents navigate repositories primarily through lexical …

• Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction

  Ziwei Li, Tao Yuan, Shuzi Niu, Huiyuan Li · 19 mai 2026

  Sparse matrix reordering can significantly reduce the fill-in during matrix factorization, thereby decreasing the computational and storage requirements in sparse matrix computations. Finding a minimal fill-in ordering is known to be an NP-hard problem. Moreover, there is a paradox: matrix reorderin…

• Self-Supervised Learning for Sparse Matrix Reordering

  Ziwei Li, Tao Yuan, Fangfang Liu, Shuzi Niu, Huiyuan Li, Wenjia Wu · 19 mai 2026

  Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches…

• On the Identifiability of Causal Graphs with the Invariance Principle

  Francesco Montagna · 15 mai 2026

  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 {induced} by a structural causal model, and additional data from (in the best case) \textit{only two} environments that sufficiently differ in the noise stati…

• Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

  Jannik Irmai, Lucas Fabian Naumann, Bjoern Andres · 14 mai 2026

  The multicut problem is an NP-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural networks have been defined for the multicut problem but can be adapted further to its specific objective function and constr…

• Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS

  Laurent Guigues · 8 mai 2026

  We introduce Graph Normalization (GN), a principled dynamical system on graphs that serves as a differentiable approximation engine for the NP-hard Maximum Weight Independent Set (MWIS) problem. MWIS encompasses many combinatorial challenges, including optimal assignment, scheduling, set packing, an…

• Graph Query Generation with Constraint-guided Large Language Agents

  Mengying Wang, Nicolaas Jedema, Rahul Pandey, RaviKiran Krishnan, Jens Lehmann, Yinghui Wu · 6 mai 2026

  Knowledge Graph Question Answering (KGQA) has advanced through structured query generation, yet most efforts target RDF/SPARQL, leaving Cypher and property graphs underexplored, despite increasing demand for unified KGQA in industry settings. We propose UniQGen, a novel constraint-based framework th…

• StreamIndex: Memory-Bounded Compressed Sparse Attention via Streaming Top-k

  Jaber Jaber, Osama Jaber · 5 mai 2026

  DeepSeek-V3.2 and V4 introduce Compressed Sparse Attention (CSA): a lightning indexer (a learned scoring projection over compressed keys) scores them, the top-k are selected per query, and a sparse attention kernel reads only those. Public CSA implementations materialize a [B, S, H_I, T] FP32 score …

• A Short Note on Batch-efficient Divide-and-Conquer Algorithm for EigenDecomposition

  Yue Song · 1 mai 2026

  EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. One crucial bottleneck limiting its usage is the expensive computation cost, particularly for a mini-batch of matrices in deep neural networks. Our previous work proposed a dedicated QR-based ED algorithm fo…

• Memanto: Typed Semantic Memory with Information-Theoretic Retrieval for Long-Horizon Agents

  Seyed Moein Abtahi, Rasa Rahnema, Hetkumar Patel, Neel Patel, Majid Fekri, Tara Khani · 27 avril 2026

  The transition from stateless language model inference to persistent, multi session autonomous agents has revealed memory to be a primary architectural bottleneck in the deployment of production grade agentic systems. Existing methodologies largely depend on hybrid semantic graph architectures, whic…

• SynthPID: P&ID digitization from Topology-Preserving Synthetic Data

  Suraj Prasad, Pinak Mahapatra · 21 avril 2026

  Automating the digitization of Piping and Instrumentation Diagrams (P&IDs) into structured process graphs would unlock significant value in plant operations, yet progress is bottlenecked by a fundamental data problem: engineering drawings are proprietary, and the entire community shares a single pub…

• Heat and Mat\'ern Kernels on Matchings

  Dmitry Eremeev, Salem Said, Viacheslav Borovitskiy · 17 avril 2026

  Applying kernel methods to matchings is challenging due to their discrete, non-Euclidean nature. In this paper, we develop a principled framework for constructing geometric kernels that respect the natural geometry of the space of matchings. To this end, we first provide a complete characterization …

• RegD: Hierarchical Embeddings via Dissimilarity between Arbitrary Euclidean Regions

  Hui Yang, Jiaoyan Chen · 15 avril 2026

  Hierarchical data is common in many domains like life sciences and e-commerce, and its embeddings often play a critical role. While hyperbolic embeddings offer a theoretically grounded approach to representing hierarchies in low-dimensional spaces, current methods often rely on specific geometric co…

• Symmetry-Aware Generative Modeling through Learned Canonicalization

  Kusha Sareen, Daniel Levy, Arnab Kumar Mondal, S\'ekou-Oumar Kaba, Tara Akhound-Sadegh, Siamak Ravanbakhsh · 14 avril 2026

  Generative modeling of symmetric densities has a range of applications in AI for science, from drug discovery to physics simulations. The existing generative modeling paradigm for invariant densities combines an invariant prior with an equivariant generative process. However, we observe that this te…

• ReLU Networks for Exact Generation of Similar Graphs

  Mamoona Ghafoor, Tatsuya Akutsu · 8 avril 2026

  Generation of graphs constrained by a specified graph edit distance from a source graph is important in applications such as cheminformatics, network anomaly synthesis, and structured data augmentation. Despite the growing demand for such constrained generative models in areas including molecule des…