Sparse matrices are extensively used to model interactions between entities and facilitate computations in neural networks. Sparse Matrix Multiplication (SpGEMM) serves as a fundamental operation in graph algorithms, social network analysis, and deep learning, attracting considerable research interest. Among the four primary paradigms for defining sparse matrix multiplication, the Inner Product (IP) method most closely aligns with the standard definition of matrix multiplication. However, due to its limited data reuse and reliance on index matching, the IP method has been rarely explored in the literature. This paper investigates the strong connection between SpGEMM and set intersection computation, introducing a hybrid sparse matrix multiplication algorithm that builds upon the numerical computation of the IP method. By leveraging the IP method's advantages-such as minimal intermediate results and high flexibility-our approach effectively enhances computational efficiency. Experimental evaluations on benchmark datasets demonstrate the superiority of the proposed algorithm, particularly in scenarios where the resulting matrix exhibits high sparsity. Furthermore, our method proves effective in several applications, including self-transpose multiplication and sparse matrix multiplications in graph neural networks.

Training graph neural networks (GNNs) on large-scale graphs is challenging due to neighbor explosion problem. To alleviate this, various sampling methods have been proposed. However, they still suffer from several issues like sparse relationships between layers of computation graphs or edge information loss during sampling. Different from them, we propose a novel sampling strategy named HFLR, which uses a small subset of total nodes for training. The basic principle is that not all nodes contribute to accuracy improvement. Specifically, in each epoch, we sample a small number of nodes for computing loss and updating parameters, where some are fixed for all epochs, while others are resampled in each epoch. To guarantee an unbiased estimation of training loss, we further present normalization techniques. Extensive experiments on six large-scale graphs demonstrate our method achieves comparable F1scores with 1.7x-3.3x speedups over other sampling-based algorithms.

The volume of graph data is increasing substantially, exerting significant pressure on graph analytics, especially when computing resources are limited. To address this challenge, we investigate the problem of developing compact representations that directly support widely used graph analytics. Leveraging interval encoding, we introduce two compact graph representations: the unified interval (UI) representation and the hybrid vertex-interval (HVI) representation. To minimize the sizes of these representations, we mathematically formulate two graph reordering problems, MUIP and MHVIP, and provide an NPhardness analysis. To solve these problems, we propose a spaceefficient edge-dropping framework, which, powered by a weightpriority approach, offers approximation ratio guarantees. We also develop a sampling method based on random walks to accelerate the edge-dropping process. Extensive experiments on 15 graph datasets demonstrate that the UI and HVI representations achieve an average compactness of 34.54% and 26.99%, respectively. Moreover, the HVI representation significantly speeds up various graph analytics, such as edge existence determination, triangle counting, and PageRank.

In real-world scenarios, the application of reinforcement learning is significantly challenged by complex non-stationarity. Most existing methods attempt to model changes in the environment explicitly, often requiring impractical prior knowledge of environments. In this paper, we propose a new perspective, positing that non-stationarity can propagate and accumulate through complex causal relationships during state transitions, thereby compounding its sophistication and affecting policy learning. We believe that this challenge can be more effectively addressed by implicitly tracing the causal origin of non-stationarity. To this end, we introduce the Causal-Origin REPresentation (COREP) algorithm. COREP primarily employs a guided updating mechanism to learn a stable graph representation for the state, termed as causal-origin representation. By leveraging this representation, the learned policy exhibits impressive resilience to non-stationarity. We supplement our approach with a theoretical analysis grounded in the causal interpretation for non-stationary reinforcement learning, advocating for the validity of the causal-origin representation. Experimental results further demonstrate the superior performance of COREP over existing methods in tackling non-stationarity problems. The code is available at https://github.com/PKU-RL/COREP.

As one of the most primitive operators in graph algorithms, such as the triangle counting, maximal clique enumeration, and subgraph listing, a set intersection operator returns common vertices between any two given sets of vertices in data graphs. It is therefore very important to accelerate the set intersection, which will benefit a bunch of tasks that take it as a built-in block. Existing works on the set intersection usually followed the merge intersection or galloping-search framework, and most optimization research focused on how to leverage the SIMD hardware instructions. In this paper, we propose a novel multi-level set intersection framework, namely hierarchical set partitioning and join (HERO), by using our well-designed set intersection bitmap tree (SIB-tree) index, which is independent of SIMD instructions and completely orthogonal to the merge intersection framework. We recursively decompose the set intersection task into small-sized subtasks and solve each subtask using bitmap and boolean AND operations. To sufficiently achieve the acceleration brought by our proposed intersection approach, we formulate a graph reordering problem, prove its NP-hardness, and then develop a heuristic algorithm to tackle this problem. Extensive experiments on real-world graphs have been conducted to confirm the efficiency and effectiveness of our HERO approach. The speedup over classic merge intersection achieves up to 188x and 176x for triangle counting and maximal clique enumeration, respectively.