Aug 2026· IEEE Transactions on Parallel and Distributed Systems· Vol 37, pp. 2327-2341· 0 citations· 50 references
Computer Science
TL;DR
This work proposes a redundancy-aware HGNN sampling paradigm that leverages a metapath trie to reuse traversal paths, effectively eliminating redundant memory accesses and introduces a reusability-driven metapath grouping technique that optimally clusters metapaths to maximize reusable traversal paths within hardware channels, enhancing efficiency in scenarios with semantic parallelism.
Abstract
Heterogeneous graph neural networks (HGNNs) are highly effective in processing heterogeneous graph data and have been widely adopted in critical domains. As real-world graph data continues to scale, performing direct inference on entire graphs becomes increasingly infeasible, making mini-batch methods the standard approach. However, in end-to-end HGNN inference, metapath-based mini-batch sampling constitutes a significant performance bottleneck due to the extensive random memory accesses induced by the irregular traversal of graph structures. Existing sampling paradigms suffer from excessive redundant traversals caused by inherent semantic redundancy, severely degrading sampling efficiency and, consequently, leading to suboptimal mini-batch inference performance. In this work, we propose a redundancy-aware HGNN sampling paradigm that leverages a metapath trie to reuse traversal paths, effectively eliminating redundant memory accesses. We then map it onto a multi-channel hardware sampling unit denominated ESR-HGNN. Furthermore, we introduce a reusability-driven metapath grouping technique that optimally clusters metapaths to maximize reusable traversal paths within hardware channels, enhancing efficiency in scenarios with semantic parallelism. Extensive experimental results demonstrate that ESR-HGNN achieves an average sampling performance improvement of one order of magnitude over CPU and GPU, accompanied by significant energy savings. Additionally, it delivers substantial speedup in end-to-end mini-batch inference when integrated with GPU and state-of-the-art HGNN inference accelerator.
Noesis, a decoupled Graph-RAG architecture addressing limitations through four algorithms: Bidirectional Graph Traversal with a Graph-Feedback Context Resolver simulating human reading with degrading memory, an AIMD Concurrency Controller adapted from TCP congestion control, and Moesis, domain-aware selective quantization for MoE models.
Experiments show that AP-REASONER outperforms baseline subsamplers on structure-sensitive downstream tasks and enables controllable recovery of alternative protein conformations, highlighting the value of modeling MSA subsampling as a controllable optimization problem, where factor-graph reasoning offers an effective alternative to heuristic selection.
Retrieval-Augmented Generation over Knowledge Graphs (GraphRAG) enhances Large Language Models (LLMs) with structured, multi-hop evidence. However, existing GraphRAG systems predominantly linearize retrieved subgraphs into long textual prompts, forcing LLMs to recompute identical schema-level reasoning across queries repeatedly. This text-centric design incurs substantial prefilling latency, memory overhead, and severely limited cache reuse under entity-level variations. We observe that although retrieved entities differ across queries, their underlying logical schemas (meta-structures) recur with high frequency, indicating that most computational cost is spent on repeatedly encoding invariant structural logic. In this paper, we propose MetaKV, the first structure-aware KV caching mechanism that explicitly decouples static structural logic from dynamic entity semantics in GraphRAG inference. In a preparation phase, MetaKV mines frequent meta-structures and pre-computes their Key-Value (KV) caches as reusable Skeleton KVs. During inference, query-specific entity representations are injected into reserved structural slots to assemble the context without recomputing graph topology. To further enforce faithfulness to graph reasoning, MetaKV introduces a Topological Mask that constrains attention to valid graph edges. Extensive experiments conducted on HotpotQA and MetaQA datasets demonstrate that MetaKV achieves up to 6.4× prefilling speedup and a 73% effective cache-hit rate while maintaining competitive reasoning accuracy, enabling high-throughput, low-latency GraphRAG without sacrificing adherence to graph topology.
Ruikun Luo, C. Gu, Jing Yang et al.· Proceedings of the 32nd ACM...· 0 citations
Taurus is presented, a single-machine system for GNN inference on graphs that do not fit in RAM, supporting both full-graph inference and fanout-sampled inference, and outperforms the strongest layer-wise baseline, DGI.
Pranjal Naman, Yogesh L. Simmhan· arXiv.org· 0 citations
Integrating Knowledge Graphs (KGs) into Retrieval-Augmented Generation (RAG) can substantially improve LLM performance on complex question answering (QA) by reducing hallucinations and supplying structured context. However, building high-quality KGs over large corpora for edge scenarios is challenging: cloud-based processing introduces latency and dependency on remote services, while exhaustive on-device construction with LLMs is often computationally infeasible under limited hardware budgets. We observe that traditional non-LLM methods can efficiently capture explicit knowledge, and that real-world queries typically touch only a small, highly concentrated portion of the graph. As a result, static and exhaustive KG construction is redundant and inefficient. We propose Edge-AdaptiveKG, a resource-aware framework that combines an offline Seed KG (S-KG) with an online Query-driven KG (Q-KG). Lightweight non-LLM methods build the S-KG, while the LLM is invoked on demand during question answering to incrementally expand the Q-KG only when complex relations are needed. Experiments show that Edge-AdaptiveKG reduces computational overhead and inference latency, enabling KG-enhanced RAG on resource-constrained devices while maintaining competitive QA accuracy.
Yuyu Du, Juxin Niu, Chun Jason Xue et al.· IEEE International Conferenc...· 0 citations
BoxDPpS performs box-level search with safe region pruning, eliminates redundant representations of the same iRM-set, improves early pruning through bounded warm-up, and compresses each fixed-M auxiliary network for exact parametric pseudoflow solving.
Jiadong Xie, Jiaming Yang, Kangfei Zhao et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
