Graph partitioning is crucial in distributed graph-parallel computing systems, and it is challenging for graph partitioning to optimize the communication cost and load balancing together. Existing state-of-the-art works, such as Powerlyra and TopoX, optimize the load balancing by randomly distributing the edges of high-degree vertices, which inevitably brings a high communication cost that is unbounded. This paper proposes a graph partition model that can minimize communication cost while maximizing load balancing. More specifically, we model the graph partition as the combinatorial design problem. Our proposed model can provide high-quality partition that guarantees that the computing load can be evenly distributed to each worker and minimizes the communication cost with a near-optimal theoretical boundary.Based on the proposed model, we extend the hybrid-cut partitioning algorithm for the power-law graph and propose HCPD, a hybrid-cut partitioning algorithm based on combinatorial design. HCPD uses the proposed model to optimize the load balancing and communication cost simultaneously for high-degree vertices, and assigns the high-degree vertices and their low-degree neighbors to the same workers by label propagation to reduce the overall communication cost. In this way, we partition the low-degree and high-degree vertices holistically and further improve the partition quality, unlike Powerlyra and TopoX, which deal with the two parts independently. Our experiments show that HCPD outperforms Powerlyra on PageRank task by up to 2× faster on real-world power-law graphs with billions of edges.

SimRank is an important metric to measure the topological similarity between two nodes in a graph. In particular, single-source and top-k SimRank has numerous applications in recommendation systems, network analysis, and web mining, etc. Mathematically, given a vertex, the computation of single-machine and single-source SimRank mainly lies in matrix-matrix operations. However, it is almost impossible to directly compute on large graphs. Thus, existing works yield to two main operations: a series of random walks, and sparse matrix and dense vector multiplication operations. This brings about high computation cost for SimRank on large graphs. In real-world applications, there is always the query time and accuracy trade-off, which hinders the computation of high-precision SimRank on large-scale graphs. To handle this problem, this paper proposesClipSim, the first GPU-friendly parallel framework that accelerates the single-source SimRank on GPU with accuracy guarantee. We design a novel data structure and GPU-friendly parallel algorithms for efficient computation of all the operations of SimRank on GPU. Moreover, our theoretical derivation enables ClipSim to largely reduce the number of random walks required for each node, while maintaining the same theoretical accuracy as the state-of-the-art algorithm, ExactSim. We conduct extensive experiments on real-world and synthetic datasets to demonstrate the accuracy and efficiency of ClipSim. The results show that compared with ExactSim, ClipSim obtains single-source SimRank vectors with the same accuracy and up to 160× faster computation time.

Given a data matrix \( D \) , a submatrix \( S \) of \( D \) is an order-preserving submatrix (OPSM) if there is a permutation of the columns of \( S \) , under which the entry values of each row in \( S \) are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work on OPSM has ever considered uncertain value intervals using the well-established possible world semantics. We establish two different definitions of significant OPSMs based on thepossible world semantics: (1) expected support-based and (2) probabilistic frequentness-based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, with a closed-form formula derived to efficiently handle the special case of uniform value distribution and an accurate cubic spline approximation approach that works well with any uncertain value distributions. To efficiently check the probabilistic frequentness, several effective pruning rules are designed to efficiently prune insignificant OPSMs; two approximation techniques based on the Poisson and Gaussian distributions, respectively, are proposed for further speedup. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori, respectively. We further parallelize our prefix-projection-based mining algorithm using PrefixFPM, a recently proposed framework for parallel frequent pattern mining, and we achieve a good speedup with the number of CPU cores. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.

Precipitation nowcasting, which predicts rainfall intensity in the near future, has been studied by meteorologists for decades. Currently, computer vision techniques, especially optical flow based methods, are widely adopted by observatories since they deliver reasonable performance without the need of model training. However, their performance is highly sensitive to model parameters which require a lot of empirical knowledge to optimize. With the recent success of deep learning (DL), machine learning researchers have started to explore the use of spatiotemporal DL models for precipitation nowcasting, which have demonstrated a better performance than optical flow based methods. However, DL models are not easy to conFigure for nonDL experts such as meteorologists. In this poster, we introduce EasyRain, a platform with a user-friendly web interface to help users without domain knowledge (in DL and/or meteorology) to efficiently build DL and optical flow based models. We will demonstrate the efficiency and usability of EasyRain for training, tuning, and comparing precipitation nowcasting models.

Given a data matrix D, a submatrix S of D is an order-preserving submatrix (OPSM) if there is a permutation of the columns of S, under which the entry values of each row in S are strictly increasing. OPSM mining is widely used in real-life applications such as identifying coexpressed genes, and finding customers with similar preference. However, noise is ubiquitous in real data matrices due to variable experimental conditions and measurement errors, which makes conventional OPSM mining algorithms inapplicable. No previous work has ever combated uncertain value intervals using the possible world semantics. We establish two different definitions of significant OPSMs based on the possible world semantics: (1) expected support based and (2) probabilistic frequentness based. An optimized dynamic programming approach is proposed to compute the probability that a row supports a particular column permutation, and several effective pruning rules are introduced to efficiently prune insignificant OPSMs. These techniques are integrated into our two OPSM mining algorithms, based on prefix-projection and Apriori respectively. Extensive experiments on real microarray data demonstrate that the OPSMs found by our algorithms have a much higher quality than those found by existing approaches.