Temporal subgraph matching aims to identify occurrences of a query graph within a large target graph, subject to certain temporal constraints that require that timestamps on the edges increase in accordance with the direction of the path. Current research on temporal subgraph matching typically identifies each non-temporal match and then filters out occurrences by examining all paths within each occurrence for compliance with temporal constraints. However, this approach proves to be highly inefficient, as it involves excessive unnecessary computation on non-temporal occurrences that do not meet the temporal constraints and can be pruned early during the matching process. Moreover, the constraint examination on all paths within each occurrence further results in numerous redundant timestamp comparisons. Therefore, a high-performance solution is demanded to overcome these drawbacks. In this paper, we introduce TeMatch, a high-performance framework designed to be compatible with any enumeration-based solution for temporal subgraph matching. TeMatch features a novel topological representation of temporal constraints in the query graph, along with three temporal-aware subgraph matching algorithms that enable rapid constraint checking and enhance early pruning and filtration. Extensive experiments reveal that TeMatch efficiently harnesses temporal information to enable early pruning and achieves a speedup of 313.57x while being parallel-friendly, highly compatible, and yielding identical matching results.

Monotonic graph algorithms, such as shortest path, BFS, and reachability, are fundamental to graph analytics and are widely used across domains. Recent systems employ pruning techniques to accelerate the processing of these algorithms. However, state-of-the-art monotonic graph engines are restricted to in-memory execution and cannot scale to graphs that exceed main memory capacity. In contrast, existing out-of-core graph engines are designed for general-purpose workloads and lack effective pruning mechanisms tailored to monotonic graph algorithms. To bridge this gap, we present Gem, an out-of-core graph engine designed for monotonic graph algorithms. Gem introduces a PageRank-based graph sketch that captures key topological features inmemory with minimal preprocessing overhead. Building on this sketch, we propose a novel graph abstraction that enables the direct derivation of tight bounds for monotonic graph algorithms, supporting effective pruning at both the vertex and partition levels. Comprehensive evaluations on six real-world datasets, including the 42.5-billion-edge ClueWeb graph, show that Gem significantly outperforms existing systems. It achieves up to 135.40× speedup over GridGraph and 12.58× over Wonderland in out-of-core settings, and also delivers substantial improvements in other modes: up to 10.41× over RisGraph in memory and 20.64× over CGgraph out-of-GPU memory.

The k -core model has garnered widespread adoption for preserving essential cohesive subgraphs owing to its linear-time computability, making it particularly suitable for hypergraph analysis. However, considering the continuously evolving characteristics of real-world hypergraphs, recent research efforts have focused on developing efficient algorithms that can maintain the core value of each vertex amid structural alterations. Despite these efforts, frequent insertions and deletions in dynamic hypergraphs continue to pose significant inefficiencies, primarily due to the increased traversal overhead incurred by hyperedge insertion algorithms. This exacerbates performance disparities between handling hyperedge insertions and deletions, underscoring the persistent challenge of effective k -core analysis in hypergraphs. To effectively address these challenges, we have gained key insights that enable us to define a specific order, termed the hypergraph k -order, which significantly reduces redundant vertex traversal and narrows down the search space during hyperedge insertions. Based on the proposed hypergraph k -order, we define two indices, the order index and the pivotal index, aimed at minimizing traversal costs and expediting the hyperedge insertion algorithm. Moreover, it is essential to recognize that the recomputation of the support degree ( sd ) for all vertices following each hyperedge deletion can significantly diminish the performance efficiency of deletion algorithms. To address this, we introduce an optimized approach that leverages the incremental maintenance of the support degree ( sd ) value to expedite the hyperedge deletion process. By leveraging these optimizations, we introduce a novel Order-based Traversal core Maintenance methodology, designated as OTM , which markedly enhances the efficiency of core maintenance in dynamic hypergraphs. Our comprehensive evaluation, which covers 12 real-world hypergraph datasets and a synthetic dataset, reveals that OTM achieves staggering speedup, outperforming the state-of-the-art approach with a 41,420 \(\times\) speedup in the insertion algorithm and 8,284 \(\times\) speedup in the deletion algorithm, underscoring its remarkable efficiency and effectiveness.

Temporal graphs attach time information to edges and are commonly used for implementing time-critical applications that can not be effectively processed by traditional static and dynamic graph processing engines. State-of-the-art solutions that target temporal path problems remain ad-hoc and often suboptimal. A unified and high-performance solution that could efficiently process general temporal path problems via a universal optimization strategy and relieve practitioners from heavy optimization efforts is in urgent demand. In this paper, we make two key observations: (1) temporal path problems can be described as topological-optimum problems and solved by a universal single scan execution model; and (2) data redundancy commonly occurs in the native format of the transformed temporal graphs, which is unnecessary for information propagation and can be eliminated for better memory utilization and execution efficiency. Based on these core insights, we propose TegRaph, the first general-purpose temporal graph computing engine to provide a unified optimization strategy and execution model for general temporal path problems and their applications. TegRaph not only presents temporal information-aware graph representation that naturally fits temporal graphs but also offers general system-level supports such as out-of-core execution. Extensive evaluation reveals that TegRaph can achieve significant speedups over the state-of-the-art designs with up to two orders of magnitude (241×) with the throughput of two hundred million edges per second.