Core decomposition is a widely used hierarchical analysis algorithm for large-scale graphs. It achieves this decomposition by iteratively peeling the vertices along with their adjacency edges off into different hierarchies. With the timeliness requirements of modern applications, many researchers have introduced accelerators, particularly GPUs, to improve the computational efficiency of graph algorithms. However, the empty, sparse, and numerous hierarchies in large graphs lead to inefficient computation and parallelism, not only including unnecessary searching for the hierarchy’s vertices, but also significant thread wastage when peeling off the adjacency edges of these vertices. In this paper, we propose an adaptive parallel framework for core decomposition, namedAdaptiveCore. First, it improves vertex searching efficiency by adaptively skipping the empty hierarchies and reducing the search space. Moreover, it greatly improves thread utilization by adaptively allocating the available threads to peel off the adjacency edges. Comprehensive experiments show that, compared with the state-of-the-art works, the proposed framework achieves an average speedup of 7.1× on the GPU platform and up to 2.0× on the multi-core CPU platform.

Core decomposition is a well-established graph mining problem that involves a widely-used subgraph model k-core in network analysis. Solutions to this problem have been developed using the Peel and Index paradigms. However, existing studies have not effectively harnessed GPU performance to expedite core decomposition, despite the growing need for enhanced performance. This paper introduces an efficient GPU acceleration framework, PICO, for both the Peel and Index paradigms of k-core decomposition. We propose a Peel-based algorithm, named PeelOne, which reduces the frontiers searching cost and redundant memory footprint of the frontiers by virtual small graph transformation and kernel fusion. Moreover, we design a GPU-friendly hybrid frontier queues architecture to balance the performance and the memory usage and quickly handle any overflow of the queues. We also propose an Index-based algorithm, named HistoCore, which addresses the issue of extensive redundant computations across both vertices and edges. Extensive experiments on NVIDIA RTX 3090 GPU show that PeelOne outperforms the SOTA Peel-based algorithm by 1.4 × ∼3.5 × speedup, and HistoCore outperforms the existing Index-based algorithm by 9.4 × ∼26.3 × speedup.

Core decomposition is a well-established graph mining algorithm in network analysis that involves the k-core subgraph model. However, most existing works on GPUs perform inefficiency due to the heavy search cost for identifying the sparse frontiers throughout the entire vertex space, which is caused by the minimum-degree dependency. Existing works design multiple block queues to partially reduce the cost caused by the sparse frontier search. Nonetheless, the queues consume excessive global memory to avoid queue overflow, leading to the decreased scalability. To address these problems, this paper proposes a space-efficient and dependency-aware GPU parallel framework, SpeedCore, for core decomposition. A theoretically verified virtual graph method is proposed to compress the large sparse search space into a small and dense format. A cache-centric hybrid queue method with a task granularity control strategy at the block level is proposed to restrict memory usage and prevent overflow. Furthermore, SpeedCore proposes a context-based binary search method to accelerate the graph degeneracy problem, which is derived from core decomposition. Extensive experiments on the NVIDIA RTX 3090 GPU show that SpeedCore outperforms the state-of-the-art algorithm by a 2.2 × average speedup. Moreover, SpeedCore can still maintain almost the same performance with low memory consumption. To solve the graph degeneracy problem, SpeedCore achieves a 7.5 × average speedup.

We delve into the realm of offline meta-reinforcement learning (OMRL), a practical paradigm in the field of reinforcement learning that leverages offline data to adapt to new tasks. While prior approaches have not explored the utilization of context-based dynamical models to tackle OMRL problems, our research endeavors to fill this gap. Our investigation uncovers shortcomings in existing context-based methods, primarily related to distribution shifts during offline learning and challenges in establishing stable task representations. To address these issues, we formulate the problem as Hidden-Parameter MDPs and propose a framework for effective model adaptation using meta-models plus latent variables, which is inferred by the transformer-based system recognition module trained in an unsupervised fashion. Through extensive experimentation encompassing diverse simulated robotics and control tasks, we validate the efficacy of our approach and demonstrate its superior generalization ability compared to existing schemes, and explore multiple strategies for obtaining policies with personalized models. Our method achieves a model with reduced prediction error, outperforming previous methods in policy performance, and facilitating efficient adaptation when compared to prior dynamic model generalization methods and OMRL algorithms.

Incremental maximal clique enumeration (IMCE), which maintains maximal cliques in dynamic graphs, is a fundamental problem in graph analysis. A maximal clique has a solid descriptive power of dense structures in graphs. Real-world graph data is often large and dynamic. Studies on IMCE face significant challenges in the efficiency of incremental batch computation and hybrid edge changes. Moreover, with growing graph sizes, new requirements occur on indexing global maximal cliques and obtaining maximal cliques under specific vertex scope constraints. This work presents a new data structure SOMEi to maintain intermediate maximal cliques during construction. SOMEi serves as a space-efficient index to retrieve scope-constrained maximal cliques on the fly. Based on SOMEi, we design a procedure-oriented IMCE algorithm to deal with hybrid edge changes within a unified algorithm framework. In particular, the algorithm is able to process a large batch of edge changes and significantly improve the average processing time of a single edge change through an efficient pruning strategy. Experimental results on real and synthetic graph data demonstrate that the proposed algorithm outperforms all the baselines and achieves good efficiency through pruning.

Delay Tolerant Network (DTN) is a widely used network in computer network and wireless network, there are no permanent end-to-end connections between source and destination nodes (vertices). Betweenness centrality (BC) is used to find the key nodes (vertices) of DTNs, and there are kinds of implementations of the BC algorithm for DTNs. However, most recent algorithms in BC computation suffer from the problem of high auxiliary memory consumption. To reduce BC computing’s memory consumption, we propose a path-merging-based algorithm called Galliot to calculate the BC values using GPU, which aims to minimize the on-board memory consumption and enable the BC computation of large-scale graphs on GPU. The proposed algorithm requires$\mathcal {O}(n)$space and runs in$\mathcal {O}(mn)$time on unweighted graphs. We present the theoretical principle for the proposed path merging method. Moreover, we propose a locality-oriented policy to maintain and update the worklist to improve GPU data locality. In addition, we conducted extensive experiments on NVIDIA GPUs to show the performance of Galliot. The results show that Galliot can process the larger graphs, which have$11.32\times $more vertices and$5.67\times $more edges than the graphs that recent works can process. Moreover, Galliot can achieve up to$38.77\times $speedup over the existing methods.