18 papers
EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks
Sai Karthik Navuluru, Siddhartha Shankar Das, Franck Dernoncourt +7
Sparse GNN training reduces computation, but deciding which edges to keep can be costly. Reusing one sparse graph is cheap, but locks training to a fixed topology, while varying it…
Parametrized Exact Hardware-Software Partitioning
Cameron Ibrahim, S M Ferdous, Erdal Mutlu +2
When optimizing computing architecture for specific computationally intensive tasks, such as evaluating or training a neural network, it is important to identify what computational…
Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks
Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous +7
Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers…
DynLP: Parallel Dynamic Batch Update for Label Propagation in Semi-Supervised Learning
S M Shovan, Arindam Khanda, S M Ferdous +2
Semi-supervised learning aims to infer class labels using only a small fraction of labeled data. In graph-based semi-supervised learning, this is typically achieved through label p…
Anonymized Network Sensing using C++26 std::execution on GPUs
Michael Mandulak, Sayan Ghosh, S M Ferdous +2
Large-scale network sensing plays a vital role in network traffic analysis and characterization. As network packet data grows increasingly large, parallel methods have become mains…
ApproxJoin: Approximate Matching for Efficient Verification in Fuzzy Set Similarity Join
Michael Mandulak, S M Ferdous, Sayan Ghosh +2
The set similarity join problem is a fundamental problem in data processing and discovery, relying on exact similarity measures between sets. In the presence of alterations, such a…
Weighted Matching in a Poly-Streaming Model
Ahammed Ullah, S. M. Ferdous, Alex Pothen
We introduce the poly-streaming model, a generalization of streaming models of computation in which processors process data streams containing a total of items. The alg…
ELRUHNA: Elimination Rule-basedHypergraph Alignment
Cameron Ibrahim, S M Ferdous, Ilya Safro +2
Hypergraph alignment is a well-known NP-hard problem with numerous practical applications across domains such as bioinformatics, social network analysis, and computer vision. Despi…
GNN-Based Candidate Node Predictor for Influence Maximization in Temporal Graphs
Priyanka Gautam, Balasubramaniam Natarajan, Sai Munikoti +2
In an age where information spreads rapidly across social media, effectively identifying influential nodes in dynamic networks is critical. Traditional influence maximization strat…
SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks
Siddhartha Shankar Das, Naheed Anjum Arafat, Muftiqur Rahman +3
We propose SGS-GNN, a novel supervised graph sparsifier that learns the sampling probability distribution of edges and samples sparse subgraphs of a user-specified size to reduce t…
Semi-Streaming Algorithms for Hypergraph Matching
Henrik Reinstädtler, S M Ferdous, Alex Pothen +2
We propose two one-pass streaming algorithms for the -hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a sta…
GreediRIS: Scalable Influence Maximization using Distributed Streaming Maximum Cover
Reet Barik, Wade Cappa, S M Ferdous +3
Influence maximization--the problem of identifying a subset of k influential seeds (vertices) in a network--is a classical problem in network science with numerous applications. Th…
AGS-GNN: Attribute-guided Sampling for Graph Neural Networks
Siddhartha Shankar Das, S M Ferdous, Mahantesh M Halappanavar +2
We propose AGS-GNN, a novel attribute-guided sampling algorithm for Graph Neural Networks (GNNs) that exploits node features and connectivity structure of a graph while simultaneou…
Approximate Bipartite -Matching using Multiplicative Auction
Bhargav Samineni, S M Ferdous, Mahantesh Halappanavar +1
Given a bipartite graph with vertices and edges and a function , a -matching is a subset of edges such that every verte…
GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions
Shivaram Gopal, S M Ferdous, Hemanta K. Maji +1
We describe a parallel approximation algorithm for maximizing monotone submodular functions subject to hereditary constraints on distributed memory multiprocessors. Our work is mot…
Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing
S M Ferdous, Reece Neff, Bo Peng +6
A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivat…
Semi-Streaming Algorithms for Weighted -Disjoint Matchings
S M Ferdous, Bhargav Samineni, Alex Pothen +2
We design and implement two single-pass semi-streaming algorithms for the maximum weight -disjoint matching (-DM) problem. Given an integer , the -DM problem is to find…
A Parallel Approximation Algorithm for Maximizing Submodular -Matching
S M Ferdous, Alex Pothen, Arif Khan +2
We design new serial and parallel approximation algorithms for computing a maximum weight -matching in an edge-weighted graph with a submodular objective function. This problem…