118 research outputs found
A Work-Efficient Parallel Sparse Matrix-Sparse Vector Multiplication Algorithm
No full textWe design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memory parallel SpMSpV algorithm is work efficient in the sense that its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs
A matrix-algebraic formulation of distributed-memory maximal cardinality matching algorithms in bipartite graphs
No full textWe describe parallel algorithms for computing maximal cardinality matching in a bipartite graph on distributed-memory systems. Unlike traditional algorithms that match one vertex at a time, our algorithms process many unmatched vertices simultaneously using a matrix-algebraic formulation of maximal matching. This generic matrix-algebraic framework is used to develop three efficient maximal matching algorithms with minimal changes. The newly developed algorithms have two benefits over existing graph-based algorithms. First, unlike existing parallel algorithms, cardinality of matching obtained by the new algorithms stays constant with increasing processor counts, which is important for predictable and reproducible performance. Second, relying on bulk-synchronous matrix operations, these algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms.We report high-performance implementations of three maximal matching algorithms using hybrid OpenMP-MPI and evaluate the performance of these algorithm using more than 35 real and randomly generated graphs. On real instances, our algorithms achieve up to 200 × speedup on 2048 cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where our algorithms show good scaling on up to 16,384 cores
GNNShap: Scalable and Accurate GNN Explanation using Shapley Values
No full textGraph neural networks (GNNs) are popular machine learning models for graphs
with many applications across scientific domains. However, GNNs are considered
black box models, and it is challenging to understand how the model makes
predictions. Game theoric Shapley value approaches are popular explanation
methods in other domains but are not well-studied for graphs. Some studies have
proposed Shapley value based GNN explanations, yet they have several
limitations: they consider limited samples to approximate Shapley values; some
mainly focus on small and large coalition sizes, and they are an order of
magnitude slower than other explanation methods, making them inapplicable to
even moderate-size graphs. In this work, we propose GNNShap, which provides
explanations for edges since they provide more natural explanations for graphs
and more fine-grained explanations. We overcome the limitations by sampling
from all coalition sizes, parallelizing the sampling on GPUs, and speeding up
model predictions by batching. GNNShap gives better fidelity scores and faster
explanations than baselines on real-world datasets. The code is available at
https://github.com/HipGraph/GNNShap
LACC: A Linear-Algebraic Algorithm for Finding Connected Components in Distributed Memory
No full textPublication Trends in Artificial Intelligence Conferences: The Rise of Super Prolific Authors
No full textPapers published in top conferences contribute influential discoveries that are reshaping the landscape of modern Artificial Intelligence (AI). We analyzed 87,137 papers from 11 AI conferences to examine publication trends over the past decade. Our findings reveal a consistent increase in both the number of papers and authors, reflecting the growing interest in AI research. We also observed a rise in prolific researchers who publish dozens of papers at the same conference each year. In light of this analysis, the AI research community should consider revisiting authorship policies, addressing equity concerns, and evaluating the workload of junior researchers to foster a more sustainable and inclusive research environment
GNNShap: Scalable and Accurate GNN Explanation using Shapley Values
No full text<p>Source code of "GNNShap: Scalable and Accurate GNN Explanation using Shapley Values"</p>
<p>Please refer to the README.md file for instructions. You can also access it here: <a href="https://github.com/HipGraph/GNNShap">https://github.com/HipGraph/GNNShap</a>.</p>
Multithreaded Algorithms for Matching in Graphs with Application to Data Analysis in Flow Cytometry
No full text- …
