Hypergraph Neural Networks (HNNs) have recently gained attention as a powerful approach for capturing high-order correlations through hypergraph-structured encoding and learning techniques. However, despite their potential, existing HNN methods often encounter over-smoothing issues, which limit their ability to effectively integrate global information while maintaining high-order structural details. This limitation compromises the overall effectiveness of these models. To tackle this challenge, we introduce a novel HNN framework called Hypergraph Structural Fusion (HyperSF). HyperSF combines the structural characteristics of both hypergraphs and graphs to effectively integrate global and local information while preserving the complex high-order structures inherent in hypergraphs. This structural fusion mechanism significantly improves model performance by ensuring that both types of information are utilized in a balanced manner. Comprehensive evaluations show that our method outperforms state-of-the-art approaches, demonstrating its effectiveness in hypergraph representation learning.

Hypergraph representation learning has garnered increasing attention across various domains due to its capability to model high-order relationships. Traditional methods often rely on hypergraph neural networks (HNNs) employing messagepassing mechanisms to aggregate vertex and hyperedge features. However, these methods are constrained by their dependence on hypergraph topology, leading to the challenge of imbalanced information aggregation, where high-degree vertices tend to aggregate redundant features, while low-degree vertices often struggle to capture sufficient structural features. To overcome the above challenges, we introduce HyperKAN, a novel framework for hypergraph representation learning that transcends the limitations of message-passing techniques. Hyper- KAN begins by encoding features for each vertex and then leverages Kolmogorov-Arnold Networks (KANs) to capture complex nonlinear relationships. By adjusting structural features based on similarity, our approach generates refined vertex representations that effectively addresses the challenge of imbalanced information aggregation. Experiments conducted on the real-world datasets demonstrate that HyperKAN significantly outperforms stateof-the-art HNN methods, achieving nearly a 9% performance improvement on the Senate dataset.

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.

Hypergraph analysis is widely used in many domains, and real-world hypergraphs often follow power-law degree distributions, a structural pattern that can strongly benefit from the massive parallelism and high bandwidth of GPUs. Although a prior GPU-based framework has demonstrated the feasibility of accelerating hypergraph analytics, they lack optimizations for the structural characteristics of hypergraphs on modern GPU architectures. Meanwhile, the irregular connectivity of hypergraphs presents challenges such as load imbalance, inefficient memory access, and idle SMs. To address these challenges, we propose xHyperG, a GPU-native framework that incorporates a hierarchical workload balancing strategy for redistributing high-degree nodes at runtime, a multi-pipeline execution design that overlaps computation with data movement, and an atomic-centric programming approach that leverages GPU primitives to optimize hypergraph algorithm migration. Evaluations on five real-world datasets show that xHyperG achieves$\text{1 9 - 3 2} \times$the throughput of state-of-the-art CPU systems (Hygra and NWHy) on a 36-core CPU, highlighting the potential of GPUs for large-scale hypergraph analytics.

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.

Many real-world networks are characterized by being temporal and dynamic, wherein the temporal information signifies the changes in connections, such as the addition or removal of links between nodes. Employing random walks on these temporal networks is a crucial technique for understanding the structural evolution of such graphs over time. However, existing state-of-the-art sampling methods are designed for traditional static graphs, and as such, they struggle to efficiently handle the dynamic aspects of temporal networks. This deficiency can be attributed to several challenges, including increased sampling complexity, extensive index space, limited programmability, and a lack of scalability. In this article, we introduce TEA+ , a robust, fast, and scalable engine for conducting random walks on temporal graphs. Central to TEA+ is an innovative hybrid sampling method that amalgamates two Monte Carlo sampling techniques. This fusion significantly diminishes space complexity while maintaining a fast sampling speed. Additionally, TEA+ integrates a range of optimizations that significantly enhance sampling efficiency. This is further supported by an effective graph updating strategy, skilled in managing dynamic graph modifications and adeptly handling the insertion and deletion of both edges and vertices. For ease of implementation, we propose a temporal-centric programming model, designed to simplify the development of various random walk algorithms on temporal graphs. To ensure optimal performance across storage constraints, TEA+ features a degree-aware hybrid storage architecture, capable of adeptly scaling in different memory environments. Experimental results showcase the prowess of TEA+ , as it attains up to three orders of magnitude speedups compared to current random walk engines on extensive temporal graphs.

Temporal graphs are widely used for time-critical applications, which enable the extraction of graph structural information with temporal features but cannot be efficiently supported by static graph computing systems. However, the current state-of-the-art solutions for temporal graph problems are not only ad-hoc and suboptimal, but they also exhibit poor scalability, particularly in terms of their inability to scale to evolving graphs with flexible edge modifications (including insertions and deletions) and diverse execution environments. In this paper, we present two key observations. Firstly, temporal path problems can be characterized astopological-optimumproblems, which can be efficiently resolved using a universal single-scan execution model. Secondly, data redundancy in transformed temporal graphs can be mitigated by merging superfluous vertices. Building upon these fundamental insights, we propose TeGraph+, a versatile temporal graph computing engine that makes the following contributions: (1) a unified optimization strategy and execution model for temporal graph problems; (2) a novel graph transformation model with graph redundancy reduction strategy; (3) a spanning tree decomposition (STD) based distributed execution model which uses an efficient transformed graph decomposition strategy to partition the transformed graph into different spanning trees for distributed execution; (4) an efficient mixed imperative and lazy graph update strategy that offers support for evolving graphs with flexible edge modifications; (5) a general system framework with user-friendly APIs and the support of various execution environments, including in-memory, out-of-core, and distributed execution environments. Our extensive evaluation reveals that TeGraph+ can achieve up to$241\times$speedups over the state-of-the-art counterparts.

Graph Neural Network (GNN) learning over non-Euclidean graph data has recently drawn a rapid increase of interest in many domains. Generalized sparse computation is crucial for maximizing the performance of GNN learning, while most recent GNNs primarily focused on optimizing coarse-grained parallelism associated with nodes, edges, and additional feature dimensions. However, efficiently implementing generalized sparse computation is challenging. The performance optimization of generalized sparse computation lacking in-depth architecture-aware design is seldom supported by existing Domain-Specific Languages (DSLs) and is hard to be tuned by experts, which involves substantial trial and error. In this work, we propose G-Sparse, a new compiler framework that extends the popular Halide compiler to enable effective acceleration for generalized sparse computations for GNNs through compiler-driven optimizations and auto-tuning. To facilitate generalized sparse computations, G-Sparse separates algorithms from schedules and introduces several novel sparse computation optimization techniques for modern GPUs, including two-dimensional shared memory optimizations and efficient cost-driven design space exploration and auto-tuning. Extensive evaluation against highly-optimized state-of-the-art sparse computation kernels and on end-to-end GNN training and inference efficiency has demonstrated that our proposed G-Sparse achieves up to a$4.75\times$speedup over the state-of-the-art sparse kernels, and a training and inference speedup of$1.37\times\sim 2.25\times$over three popular GNN frameworks including GCN, GraphSAGE, and GAT. The source code of G-Sparse is publicly available at https://github.com/TuGraph-family/tugraph-db/tree/master/learn.

As many real-world applications are streaming and attached with time instances, a few works have been proposed to learn streaming graph neural networks (GNNs). Unfortunately, current streaming GNNs are observed to have a large training overhead and suffer from bad parallel scalability on multiple GPUs. These drawbacks pose severe challenges to online learning of streaming GNNs and their application to real-time scenarios. To improve training efficiency, one promising solution is to use sampling, a technique widely used in static GNNs. However, to the best of our knowledge, sampling has not been investigated in learning streaming GNNs. Based on these observations, in this paper, we propose T-GCN, the first sampling-based streaming GNN system, which targets temporal-aware streaming graphs and takes advantage of a hybrid CPU-GPU co-processing architecture to achieve high throughput and low latency. T-GCN proposes an efficient sampling method, namely Segment Its Search, to offer high sampling speed with respect to three typical types of general graph sampling methods (i.e., node-wise, layer-wise, and subgraph sampling). We propose a locality-aware data partitioning method to reduce CPU-GPU communication latency and data transfer overhead, and an NVLink-specific task schedule to fully exploit NVLink's fast speed and improve GPU-GPU communication efficiency. Besides, we further pipeline the computation and the communication by introducing an efficient memory management mechanism, to improve scalability while hiding data communication. Overall, with respect to end-to-end performance, for single-GPU training, T-GCN achieves up to 7.9× speedup than state-of-the-art works. In terms of scalability, T-GCN runs 5.2× faster on average with 8 GPUs than one GPU. Additionally, in terms of sampling, T-GCN also yields a maximum of 38.8× speedup with our Segment Its Search sampling method.

Uncertain or probabilistic graphs have been ubiquitously used to represent noisy, incomplete, and inaccurate linked data in many emerging big-data mining and analytics applications. It is impractical to solve uncertain graph problems exactly as it requires to evaluate an exponential number of certain instances (or "possible worlds") generated from an uncertain graph. Previously, several CPU-based techniques were proposed to use sampling for uncertain graph processing. However, we observe that (1) they suffer from low computation efficiency and large memory overhead due to unnecessary edge sampling at runtime; (2) they cannot leverage the massive parallelism provided by modern general-purpose accelerators; and (3) there lacks a general programming framework for high-performance uncertain graph processing. To tackle these challenges, we propose a novel runtime path sampling method, which is able to identify and eliminate unnecessary edge sampling via incremental path identification and filtering, resulting in significant reduction in computation and data movement. Centered around this idea, we introduce a general uncertain graph processing framework for multi-GPU systems, named BPGraph1. BPGraph provides general support for users to design and optimize a wide-range of uncertain graph algorithms and applications without concerning about the underlying complexity. Extensive evaluation on a variety of real-world uncertain graph applications demonstrates an average speedup of 26X (up to 43X) and better scalability from BPGraph over the state-of-the-art frameworks.

Uncertain or probabilistic graphs have been ubiquitously used in many emerging applications. Previously CPU based techniques were proposed to use sampling but suffer from (1) low computation efficiency and large memory overhead, (2) low degree of parallelism, and (3) nonexistent general framework to effectively support programming uncertain graph applications. To tackle these challenges, we propose a general uncertain graph processing framework for multi-GPU systems, named BPGraph. Integrated with our highly-efficient path sampling method, BPGraph can support a wide range of uncertain graph algorithms' development and optimization. Extensive evaluation demonstrates a significant performance improvement from BPGraph over the state-of-the-art uncertain graph sampling techniques.

Abstract The command line interface is a crucial way of interacting with Linux, many programs such as ls, pwd and netstat are used on it and it is also the primary way to access a server remotely. However, the command line interface is not user friendly and thus it is difficult to use; there are many programs and users do not know which one is appropriate for finishing their task. To help users find useful commands efficiently, the authors propose FindCmd that retrieves commands based on the local data and user familiarity with commands. Then the local command data are collected including user manual such as man , info and strings extracted from the binary ELF (executable and linkable format) file. Based on the characteristics of local data, an enhanced command retrieval framework is proposed. In addition, the authors marginally decreased the priority of familiar commands when retrieving commands since users tend to use command retrieval tool to find an unfamiliar command. To the best of our knowledge, this is the first local tool for personalised command retrieval. In the evaluation section, the authors compare FindCmd with retrieval tools apropos and howdoi ; our experimental results show that FindCmd outperforms the other two tools in retrieving commands. In addition, the experiments demonstrate the effectiveness of personalised search of FindCmd.

Detecting community structure in epidemics networks is crucial for the assessment of epidemic dynamics and effective control of disease spread by targeting at the individuals bridging communities. Common community detection models (e.g., cut-criteria and modularity-criteria based model) are efficient in optimal quality of network partitions. However, most of the approaches fail to consider the dynamic infected possibility in person-to-person interactions. In addition, they present high computational complexity, which was limited by the scale of networks and the performance of hardware platform. In this paper, we propose a Jaccard distance based community detection model by considering both the quality of network partitions and the dynamics of infected interacts (i.e., edges) between two individuals in epidemic diffusion. Then, we design a novel parallel approach based on the high parallism of GPU, called EpCom, for boosting the performance and scalability of parallel community detection over large-scale epidemic networks. From the evaluation results, the proposed GPU-based implementation EpCom exhibits great performance and achieves maximum 604 million TEPS (traversed edges per second), which corresponds to up to 54.2 times and 15.6 times than CPU-based NCut and Louvain approaches separately.

As a promising alternative to centralized scheduling, sample-based scheduling is especially suitable for high fan-out workloads that contain a large number of interactive jobs. Compared to centralized schedulers, existing sample-based schedulers do not hold a global view of the cluster's resource status. Instead, the scheduling decisions are made solely based on the status of a small set of randomly sampled workers. Although this simple approach is highly efficient in large clusters, the lack of global knowledge of the cluster can lead to sub-optimal task placement decisions and difficulties in enforcing global scheduling policies. In this paper, we address these challenges in existing sample-based scheduling approaches by allowing the scheduler to maintain an approximate version of the global resource status through caching the worker node's status extracted from reply messages. More specifically, we introduce the private cluster-state technique (PCS) for the scheduler to obtain such global information. We show that the scheduler can make better scheduling decisions by utilizing PCS and the scheduler can become more capable in enforcing global scheduling policies. The use of PCS is of low cost since it does not initiate new communication in sample-based scheduling. Our approach is implemented in PSCSampler, a full distribute sample-based scheduler, which gains global knowledge from PCS. Experiment results from both simulation runs and Amazon cluster runs show that compared to Sparrow, PCSsampler can significantly reduce both 50thpercentile and 90thpercentile runtime. The firsttime success rate of PCSsampler in gang scheduling is closer to an omniscient centralized scheduler than baseline sample based scheduler.

Sample based distributed scheduling methods have been shown to be promising lower overhead alternatives to their centralized counterparts. These methods can make fast decisions based on information gathered from just a small number of worker nodes instead of the whole cluster. Most recent works in the field tend to adopt a combination of probe actions and worker-end queues in their design. However, as individual worker nodes are becoming increasingly powerful thanks to the rapid hardware evolution, we argue that one-node sampling is now a viable choice. Specifically, we show that it is now possible to achieve even lower scheduling latency by latency by abolishing probes and worker-end queues altogether. With this insight, we introduce Tiresias, a low overhead distributed scheduler based on one-node sampling and a novel task hopping mechanism. Comparing to Sparrow's approach, experiment on Google trace shows Tiresias could reduce 20% and 60% of Sparrow's 50th percentile and 90th percentile job runtime, respectively. In addition, our experiment also shows Tiresias is especially effective in reducing the delay of small jobs in non-highly loaded clusters.