Graph Theory and Algorithms

Latest papers

• Sparse Mutual Information Graph Averaging for Improving Random Indexing Embeddings

  Sriram Loganathan, Gokul Anand, Aung Bo Bo, Yourui Shao, William B. Andreopoulos · 7 August 2026

  Sparse word embedding pipelines can avoid dense co-occurrence matrix materialization, dense factorization, and gradient training while still relying on sparse global corpus statistics. This paper studies Random Indexing (RI) vectors refined by weighted averaging on a sparse Positive Pointwise Mutual…

• CourseGraph: Finding overlaps and differences in Computer Science courses across universities

  Arthur Nijdam, Paul Stankovski Wagner, Sara Ramezanian · 7 August 2026

  Student mobility programs such as Erasmus+ enable students to take courses at other universities, broadening their academic and cultural horizons. However, this flexibility also leads to a practical challenge: ensuring that students do not take courses elsewhere that substantially overlap with cours…

• GRALS: GCN-Guided Redundancy-Aware Local Search for Minimum Vertex Cover

  Chanjuan Liu, Qiqi Bao, Yu Zhang, Enqiang Zhu · 6 August 2026

  The minimum vertex cover (MVC) problem seeks to identify the smallest set of vertices that cover all edges in an undirected graph. As a fundamental NP-hard combinatorial optimization problem, MVC has been widely studied due to its applications in network analysis and system design. For large-scale i…

• Tropical Algebraic Geometry for Neuronal Representations: An Arakelov-Green Measure Based Descriptor for Graph Learning

  Yuyang Zhang, Weihan Xu, Xuehai Zhou, Shucheng Cao, Qihuang Zhang · 6 August 2026

  The quantitative analysis of 3D neuronal morphologies requires capturing both graph topology and spatial geometry. Current message-passing Graph Neural Networks (GNNs) are bounded by the 1-Weisfeiler-Lehman (1-WL) test, limiting their ability to capture cycles induced by spatial proximities. To addr…

• EvtGraph: Event-Adaptive Compression for Sparse Temporal Graph Learning in Multimodal Time Series

  Ziqian Wang, Tingxiong Xiao, Yuxiao Cheng, Jinli Suo · 6 August 2026

  Multimodal temporal data are inherently irregular and uneven in information density, yet most models rely on uniform discretization, leading to inefficient representations. We propose \textbf{EvtGraph}, a unified framework that aligns computation with temporal salience under explicit budget constr…

• FastGFDs: Efficient Validation of Graph Functional Dependencies with Desbordante

  Anton Chernikov, Yurii Litvinov, Kirill Smirnov, George Chernishev · 4 August 2026

  Graph functional dependencies (GFD) are a recently-developed concept aimed at capturing both topological structures in graphs and functional dependencies between attributes. The process of verifying whether a given GFD holds over a particular graph is referred to as GFD validation. In this very comp…

• GABench: A Comprehensive Benchmark for Evaluating LLM Agents on Graph Analysis Tasks

  Jiarui Tan, Zhongjian Zhang, YaBo Guo, Jiawei Liu, Yujie Xing, Muhan Zhang, Cheng Yang, Chuan Shi · 4 August 2026

  Large language model (LLM) agents are increasingly capable of planning, using tools, and interacting with external environments. They are typically supported by harnesses, which manage state and coordinate multi-step execution. Graph analysis provides a promising setting for evaluating their agentic…

• A Graph-Native Bitemporal Memory Store for Conversational AI Agents

  Alp Niksarli, Gopesh Baheti · 30 July 2026

  Conversational AI agents commonly lack persistent memory across sessions. The obvious fixes like injecting full chat histories into the context window, or delegating to a third-party memory service, either exhaust the model's context budget or send personal data through infrastructure the user does …

• KAP: Bridging the Knowledge Selection-Runtime Consumption Gap in LLM Systems

  Shuo Wang, Fang Xi, Wenyuan Huang, Qing Wang, Junming Su · 28 July 2026

  Modern LLM systems increasingly rely on knowledge-selection processes that produce high-value structured priors, such as ranked evidence, graph topology, multimodal alignment, and confidence signals. Yet LLM serving remains fundamentally oblivious to this rich structure: once such signals are serial…

• Supra Cognitive Modes: A Routed Architecture for Agent Memory

  Joshua Tobkin, David Yang · 22 July 2026

  Agent-memory workloads mix direct factual lookup, relation-chain and current-state reasoning, and broad synthesis over long histories. We describe Supra Cognitive Modes (SCM), an architecture that maps explicit or automatically selected per-query modes to retrieval and synthesis payloads over one sh…

• Taurus: Accelerating Out-of-Core Graph Neural Network Inference on Billion-Scale Graphs

  Pranjal Naman, Yogesh Simmhan · 21 July 2026

  Graph Neural Network (GNN) inference on billion-scale graphs is challenging due to the large memory footprint of features and embeddings and high disk I/O costs in out-of-core settings. Existing distributed GNN systems incur high communication times and infrastructure costs, while disk-based GNN sys…

• LiteTopK: Exploiting the Curse of Dimensionality for a Fused Indexer-TopK Kernel in Long-Context Sparse Attention

  Ziqi Yin, Jianyang Gao, Peiqi Yin, Jiangneng Li, Gao Cong · 15 July 2026

  Indexer-TopK, the operation to compute the scores and select the top-k candidates, is widely used by sparse attention kernels in large language models and vector retrieval in recommendation systems and vector databases. However, existing GPU-based Indexer-TopK kernels like DeepSeek Sparse Attention …

• CGS: Configurable Graph Summarization with Bounded Neighborhood Loss and Query Support

  Shubhadip Mitra, Sona Elza Simon, C Oswald, Arnab Bhattacharya, Arindam Pal · 14 July 2026

  Given a large graph, how to generate a compact summary graph that is configurable by the user and supports multiple graph queries with either no loss or with high accuracy? The ever growing size of graph datasets makes the above question on graph summarization very pertinent. Although, there are sev…

• Efficient Partitioning Method of Large-Scale Public Safety Spatio-Temporal Data based on Information Loss Constraints

  Jie Gao, Yawen Li, Zhe Xue, Zeli Guan · 10 July 2026

  The storage, management, and application of massive spatio-temporal data are widely used in practical scenarios, including public safety. However, due to the unique spatio-temporal distribution characteristics of real-world data, existing methods still face limitations in preserving spatio-temporal …

• GraphBU: MILP Instance Generation with Graph-Native Block Units

  Xiaolei Guo, Chenyu Zhou, Jianghao Lin, Dongdong Ge · 8 July 2026

  Mixed-integer linear programming (MILP) instances used for solver development are hard to obtain when models come from private or application-specific pipelines. A generator must keep the structure that solvers and learned policies rely on. Existing general generators usually choose their generation…

• Leveraging Neural Graph Compilers in Machine Learning Research for Edge-Cloud Systems

  Alireza Furutanpey, Carmen Walser, Philipp Raith, Pantelis A. Frangoudis, Schahram Dustdar · 8 July 2026

  This work presents a comprehensive evaluation of neural network graph compilers across heterogeneous hardware platforms, addressing the critical gap between theoretical optimization techniques and practical deployment scenarios. We demonstrate how vendor-specific optimizations can invalidate relativ…

• HNSW with Accuracy Guarantees Using Graph Spanners

  Minghao Li, Raghav Mittal, Sanjivni Rana, Suraj Shetiya, Gautam Das, Nick Koudas · 7 July 2026

  Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper, we propose a novel …

• Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs

  Filippo Biondi, Mirco Tribastone, Max Tschaikowski · 7 July 2026

  The stable coloring of the Weisfeiler-Leman (1-WL) test is a cornerstone of Graph Neural Networks because it provides an upper bound to the expressive power of message-passing architectures. Unfortunately, computing it presents two fundamental bottlenecks. First, classic algorithms are inherently se…

• HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report

  Minghao Li, Raghav Mittal, Sanjivni Rana, Suraj Shetiya, Gautam Das, Nick Koudas · 3 July 2026

  Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper, we propose a novel …

• Multi-Agent Routing as Set-Valued Prediction: A WildChat Benchmark and Cost-Aware Evaluation

  Ananto Nayan Bala, Faisal Muhammad Shah · 30 June 2026

  Tool and agent routing from natural-language prompts is naturally a set-valued prediction problem: a single query may require multiple agents, while over-selection increases execution cost. The benchmark introduced here is derived from WildChat and contains 3,000 prompts over a fixed 12-agent catalo…

• Computationally-efficient Graph Modeling with Refined Graph Random Features

  Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish, Isaac Reid · 26 June 2026

  We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more dist…

• FuseSampleAgg: One-Pass Neighborhood Estimation for Budgeted Knowledge-Graph Refresh and Validation

  Aleksandar Stankovi\'c, Haoran Du, Xinming Wang · 24 June 2026

  Operational knowledge-graph (KG) pipelines in networking and cybersecurity increasingly need to refresh embeddings under strict time, memory, and audit budgets, especially as curated feeds and LLM-assisted extraction accelerate KG updates. A recurring per-step cost in mini-batch KG learning is neigh…

• Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index

  Minghao Chen, Jiale Zheng · 24 June 2026

  Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic gr…

• LLM-Aided A* Search in Non-Geometric Network Graphs

  Nouf Alabbasi, Esraa Ghourab, Omar Alhussein · 23 June 2026

  Finding the shortest path in non-geometric network graphs, where edge weights encode arbitrary metrics such as latency or monetary cost rather than spatial distance, poses a challenge for informed search algorithms. Their efficiency depends on an informative heuristic, typically supplied in spatial …

• Graph Alignment via Dual-Pass Spectral Encoding and Latent Space Communication

  Maysam Behmanesh, Erkan Turan, Maks Ovsjanikov · 23 June 2026

  Graph alignment, the problem of identifying corresponding nodes across multiple graphs, is fundamental to numerous applications. Most existing unsupervised methods embed node features into latent representations to enable cross-graph comparison without ground-truth correspondences. However, these me…