Search

Graphs are ubiquitous, and they can model unique characteristics and complex relations of real-life systems. Although using machine learning (ML) on graphs is promising, their raw representation is not suitable for ML algorithms. Graph embedding represents each node of a graph as a $d$ d -dimensional vector which is more suitable for ML tasks. However, the embedding process is expensive, and CPU-based tools do not scale to real-world graphs. In this work, we present GOSH, a GPU-based tool for embedding large-scale graphs with minimum hardware constraints. GOSH employs a novel graph coarsening algorithm to enhance the impact of updates and minimize the work for embedding. It also incorporates a decomposition schema that enables any arbitrarily large graph to be embedded with a single GPU. As a result, GOSH sets a new state-of-the-art in link prediction both in accuracy and speed, and delivers high-quality embeddings for node classification at a fraction of the time compared to the state-of-the-art. For instance, it can embed a graph with over 65 million vertices and 1.8 billion edges in less than 30 minutes on a single GPU. [ABSTRACT FROM AUTHOR]

Influence maximization (IM) is the problem of finding a seed vertex set which is expected to incur the maximum influence spread on a graph. It has various applications in practice such as devising an effective and efficient approach to disseminate information, news or ad within a social network. The problem is shown to be NP-hard and approximation algorithms with provable quality guarantees exist in the literature. However, these algorithms are computationally expensive even for medium-scaled graphs. Furthermore, graph algorithms usually suffer from spatial and temporal irregularities during memory accesses, and this adds an extra cost on top of the already expensive IM kernels. In this article we leverage fused sampling, memoization, and vectorization to restructure, parallelize and boost their performance on undirected networks. The proposed approach employs a pseudo-random function and performs multiple Monte-Carlo simulations in parallel to exploit the SIMD lanes effectively and efficiently. In addition, it significantly reduces the number of edge traversals, hence the amount of data brought from the memory, which is critical for almost all memory-bound graph kernels. We apply the proposed approach to the traditional MixGreedy algorithm and propose INFuseR-MG which is more than $3000\times$ 3000 × faster than the greedy approaches and can run on large graphs that have been considered as too large in the literature. For instance, the new algorithm runs in 2.09, 0.08, 0.36 seconds on graphs Amazon, NetHEP, NetPhy with 16 threads where the sequential baseline takes 141.3, 259.1 and 1725.2 seconds, respectively. To compare INFuseR-MG with the state-of-the-art approximation algorithms, we conduct a thorough experimental analysis with various influence settings. The results on real-life, undirected networks show that on 16 threads, INFuseR-MG is $2.3\times$ 2. 3 × – $173.8\times$ 173. 8 × faster than state-of-the-art while being superior in terms of influence scores, and using a comparable amount of memory. [ABSTRACT FROM AUTHOR]

The scheduling of independent but file-sharing tasks on heterogeneous master-slave platforms has recently found important applications in Grid environments. The scheduling heuristics recently proposed for this problem are all constructive in nature and based on a common greedy criterion which depends on the momentary completion time values of the tasks. We show that this greedy decision criterion has shortcomings in exploiting the file-sharing interaction among tasks since completion time values are inadequate to extract the global view of this interaction. We propose a three-phase scheduling approach which involves initial task assignment, refinement, and execution ordering phases. For the refinement phase, we model the target application as a hypergraph and, with an elegant hypergraph-partitioning-like formulation, we propose using iterative-improvement-based heuristics for refining the task assignments according to two novel objective functions. Unlike the turnaround time, which is the actual schedule cost, the smoothness of proposed objective functions enables the use of iterative-improvement-based heuristics successfully since their effectiveness and efficiency depend on the smoothness of the objective function. Experimental results on a wide range of synthetically generated heterogeneous master-slave frameworks show that the proposed three-phase scheduling approach performs much better than the greedy constructive approach. [ABSTRACT FROM AUTHOR]