Truss decomposition is to find the hierarchy of all the k-trusses in a graph for$k\geq 2$. Existing GPU-based algorithms first compute edge support by parallelly counting the number of triangles each edge is contained in, and then iteratively peel off edges with the smallest support and update support of the affected edges in parallel. However, these algorithms perform truss decomposition on undirected graphs, which causes large storage space and numerous triangle existence checks during support update. Moreover, they are developed based on CUDA, which cannot naturally adapt to emerging hardware accelerators and support the end-to-end downstream graph machine learning (ML) tasks. In this paper, we propose a truss decomposition framework based on tensors (TDT), which can leverage the parallelism of heterogeneous hardware backends to speed up the computation and seamlessly integrate with downstream graph ML tasks. We first convert the original input graph into a directed graph and represent it by compacted tensors. Then we perform truss decomposition on the tensorized directed graph by efficient tensor operators. Such a directed-graph storage model not only saves the storage space but also naturally supports efficient support computation/update during the truss decomposition. To further accelerate truss decomposition, we also partition vertex neighbors into blocks to balance the computation workload and optimize key steps such as support computation/update in our framework. Extensive experimental studies show that our Python-based TDT algorithm not only achieves$2.3\times-8.5\times$speedup in most cases compared with the state-of-the-art CUDA-based algorithms, but also can efficiently deal with large graphs with hundreds of millions of nodes and billions of edges while the baseline fails due to large storage cost. Our source code is publicly available at https://github.com/LiGuojing194/TDTdecomposition.

Graph is ubiquitous in various real-world applications, and many graph processing systems have been developed. Recently, hardware accelerators have been exploited to speed up graph systems. However, such hardware-specific systems are hard to migrate across different hardware backends. In this paper, we propose the first tensor-based graph processing framework, Tgraph, which can be smoothly deployed and run on any powerful hardware accelerators (uniformly called XPU) that support Tensor Computation Runtimes (TCRs). TCRs, which are deep learning frameworks along with their runtimes and compilers, provide tensor-based interfaces to users to easily utilize specialized hardware accelerators without delving into the complex low-level programming details. However, building an efficient tensor-based graph processing framework is non-trivial. Thus, we make the following efforts: (1) propose a tensor-centric computation model for users to implement graph algorithms with easy-to-use programming interfaces; (2) provide a set of graph operators implemented by tensor to shield the computation model from the detailed tensor operators so that Tgraph can be easily migrated and deployed across different TCRs; (3) design a tensor-based graph compression and computation strategy and an out-of-XPU-memory computation strategy to handle large graphs. We conduct extensive experiments on multiple graph algorithms (BFS, WCC, SSSP, etc.), which validate that Tgraph not only outperforms seven state-of-the-art graph systems, but also can be smoothly deployed and run on multiple DL frameworks (PyTorch and TensorFlow) and hardware backends (Nvidia GPU, AMD GPU, and Apple MPS).

Identifying protein complexes from protein-protein interaction (PPI) networks is essential for understanding cellular organization and biological processes. Most of the existing works treat PPI networks as static and focus on detecting densely connected regions. Several recent works have explored the dynamics of PPIs in the network, but may identify complexes with false-positive edges of low confidence. In this paper, we propose a novel Dynamic COre-ATtachment based protein complex detection algorithm (DCOAT). First, we derive co-expressed gene biclusters from the gene expression data by a memetic algorithm to enable the construction of dynamic subnetworks from a static PPI network. Next, we evaluate the confidence of edges within each dynamic subnetwork by integrating both topological features and biological information to filter false-positive edges. Then, we detect complexes from each weighted subnetwork based on the core-attachment structure. Finally, we build an overlapping graph and merge redundant complexes using maximum weight matching. The experimental results validate that DCOAT achieves state-of-the-art performance compared to the nine baseline methods based on static and dynamic networks across multiple evaluation measures, especially in terms of F1and precision. Moreover, the detected stable and temporal complexes are consistent with real biological scenarios and have biological significance. Our code and datasets are publicly available at https://github.com/LiGuojing194/DCOAT.

This article proposes a novel method for the generation of the deceptive jamming signal against spaceborne SAR, which can calculate the jammer’s frequency response (JFR) efficiently. The first advantage of this algorithm is that the real-time computational complexity is independent of the number of fake scattering units, so it is particularly suitable for generating scenes containing a large number of scatterers. Besides, the imaging quality of fake targets is also improved significantly, especially in the case of squint geometries. First, using the Taylor series expansion and approximations, we derive the recurrence relationship of the slant range between the adjacent pulse repetition intervals. Based on this relationship, the JFR at each azimuth time is mapped to a special spatial spectrum, which is the 2-D Fourier transform along the range and azimuth dimensions of the JFR matrix at the time of the first pulse arrival. Therefore, after the initial JFR is calculated, the subsequent JFRs can be quickly obtained by sinc function interpolation. Then, the validity and effective region of this algorithm are estimated by the theoretical analysis of the slant range error. The simulation results and a computational complexity analysis verify that the algorithm demonstrates superior performance in terms of imaging quality and efficiency.