EXAGRAPH: Graph and combinatorial methods for enabling exascale applications


Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

Acer S, Azad A, Boman EG, et al. "EXAGRAPH: Graph and combinatorial methods for enabling exascale applications." The International Journal of High Performance Computing Applications. October 2021.

Privacy-Preserving Decentralized Aggregation for Federated Learning


In this paper, we develop a privacy-preserving decentralized aggregation protocol for federated learning. We formulate the distributed aggregation protocol with the Alternating Direction Method of Multiplier (ADMM) algorithm and examine its privacy challenges. Unlike prior works that use differential privacy or homomorphic encryption for privacy, we develop a protocol that controls communication among participants in each round of aggregation to minimize privacy leakage. We establish the protocol's privacy guarantee against an honest-but-curious adversary. We also propose an efficient algorithm to construct such a communication pattern, which is inspired by combinatorial block design theory. Our secure aggregation protocol based on the novel group-based communication pattern leads to an efficient algorithm for federated training with privacy guarantees. We evaluate our federated training algorithm on computer vision and natural language processing models over benchmark datasets with 9 and 15 distributed sites. Experimental results demonstrate the privacy-preserving capabilities of our algorithm while maintaining learning performance comparable to the baseline centralized federated learning.

Beomyeol Jeon, S M Ferdous, Muntasir Raihan Rahman, Anwar Walid, "Privacy-Preserving Decentralized Aggregation for Federated Learning." In the proceedings of IEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2021.

A Parallel Approximation Algorithm for Maximizing Submodular b-Matching


We design new serial and parallel approximation algorithms for computing a maximum weight b-matching in an edge-weighted graph with a submodular objective function. This problem is NP-hard; the new algorithms have approximation ratio 1/3, and are relaxations of the Greedy algorithm that rely only on local information in the graph, making them parallelizable. We have designed and implemented Local Lazy Greedy algorithms for both serial and parallel computers. We have applied the approximate submodular b-matching algorithm to assign tasks to processors in the computation of Fock matrices in quantum chemistry on parallel computers. The assignment seeks to reduce the run time by balancing the computational load on the processors and bounding the number of messages that each processor sends. We show that the new assignment of tasks to processors provides a four fold speedup over the currently used assignment in the NWChemEx software on 8000 processors on the Summit supercomputer at Oak Ridge National Lab.

S M Ferdous, Alex Pothen, Arif Khan, Ajay Panyala, Mahantesh Halappanavar, "A Parallel Approximation Algorithm for Maximizing Submodular b-Matching." In the proceedings of SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), 2021.

Approximation algorithms in combinatorial scientific computing


We survey recent work on approximation algorithms for computing degree-constrained subgraphs in graphs and their applications in combinatorial scientific computing. The problems we consider include maximization versions of cardinality matching, edge-weighted matching, vertex-weighted matching and edge-weighted-matching, and minimization versions of weighted edge cover and b-edge cover. Exact algorithms for these problems are impractical for massive graphs with several millions of edges. For each problem we discuss theoretical foundations, the design of several linear or near-linear time approximation algorithms, their implementations on serial and parallel computers, and applications. Our focus is on practical algorithms that yield good performance on modern computer architectures with multiple threads and interconnected processors. We also include information about the software available for these problems.

Alex Pothen, S. M. Ferdous, Fredrik Manne, "Approximation algorithms in combinatorial scientific computing." Acta Numerica, 2019.

Adaptive Anonymization of Data using b-Edge Cover


We explore the problem of sharing data that pertains to individuals with anonymity guarantees, where each user requires a desired level of privacy. We propose the first sharedmemory as well as distributed memory parallel algorithms for the adaptive anonymity problem that achieves this goal, and produces high quality anonymized datasets.

Arif Khan, Krzysztof Choromanski, Alex Pothen, S M Ferdous, Mahantesh Halappanavar, Antonino Tumeo, "Adaptive Anonymization of Data using b-Edge Cover." In the proceedings of SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, 2018.

Parallel Algorithms Through Approximation: B-Edge Cover


We describe a paradigm for designing parallel algorithms via approximation, and illustrate it on the b-Edge Cover problem. A b-Edge Cover of minimum weight in a graph is a subset C of its edges such that at least a specified number b(v) of edges in C is incident on each vertex v, and the sum of the edge weights in C is minimum. The Greedy algorithm and a variant, the LSE algorithm, provide 3/2-approximation guarantees in the worst-case for this problem, but these algorithms have limited parallelism. Hence we design two new 2-approximation algorithms with greater concurrency. The MCE algorithm reduces the computation of a b-Edge Cover to that of finding a b'-Matching, by exploiting the relationship between these subgraphs in an approximation context. The LSENW is derived from the LSE algorithm using static edge weights rather than dynamically computing effective edge weights. This relaxation gives S-LSE a worse approximation guarantee but makes it more amenable to parallelization. We prove that both the MCE and S-LSE algorithms compute the same b-EDGE COVER with at most twice the weight of the minimum weight edge cover. In practice, the 2-approximation and 3/2-approximation algorithms compute edge covers of weight within 10% the optimal. We implement three of the approximation algorithms, MCE, LSE, and S-LSE, on shared memory multi-core machines, including an Intel Xeon and an IBM Power8 machine with 8 TB memory. The MCE algorithm is the fastest of these by an order of magnitude or more. It computes an edge cover in a graph with billions of edges in 20 seconds using two hundred threads on the IBM Power8. We also show that the parallel depth and work can be bounded for the Suitor and b-Suitor algorithms when edge weights are random.

S M Ferdous, Arif Khan, Alex Pothen, "Parallel Algorithms Through Approximation: B-Edge Cover." In the proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2018.

New Approximation Algorithms for Minimum Weighted Edge Cover


We describe two new 3/2-approximation algorithms and a new 2-approximation algorithm for the minimum weight edge cover problem in graphs. We show that one of the 3/2-approximation algorithms, the Dual Cover algorithm, computes the lowest weight edge cover relative to previously known algorithms as well as the new algorithms reported here. The Dual Cover algorithm can also be implemented to be faster than the other 3/2-approximation algorithms on serial computers. Many of these algorithms can be extended to solve the b-Edge Cover problem as well. We show the relation of these algorithms to the K-Nearest Neighbor graph construction in semi-supervised learning and other applications.

S M Ferdous, Arif Khan, Alex Pothen, "New Approximation Algorithms for Minimum Weighted Edge Cover." In the proceedings of 2018 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, 2018.

An Integer Programming Formulation of the Minimum Common String Partition Problem


We consider the problem of finding a minimum common string partition (MCSP) of two strings, which is an NP-hard problem. The MCSP problem is closely related to genome comparison and rearrangement, an important field in Computational Biology. In this paper, we map the MCSP problem into a graph applying a prior technique and using this graph, we develop an Integer Linear Programming (ILP) formulation for the problem. We implement the ILP formulation and compare the results with the state-of-the-art algorithms from the literature. The experimental results are found to be promising.

S. M. Ferdous, M. Sohel Rahman, "An Integer Programming Formulation of the Minimum Common String Partition Problem." PLOS ONE, 2015.

Solving the Minimum Common String Partition Problem with the Help of Ants


In this paper, we consider the problem of finding minimum common partition of two strings (MCSP). The problem has its application in genome comparison. As it is an NP-hard, discrete combinatorial optimization problem, we employ a metaheuristic technique, namely, MAX-MIN ant system to solve this. The preliminary experimental results are found to be promising.

S. M. Ferdous, M. Sohel Rahman, "Solving the Minimum Common String Partition Problem with the Help of Ants." In the proceedings of Advances in Swarm Intelligence, 2013.

Speech development of autistic children by interactive computer games


Purpose – Speech disorder is one of the most common problems found with autistic children. The purpose of this paper is to investigate the introduction of computer-based interactive games along with the traditional therapies in order to help improve the speech of autistic children.

Mustafizur Rahman, S.M. Ferdous, Syed Ishtiaque, Anika Anwar, "Speech development of autistic children by interactive computer games." Interactive Technology and Smart Education, 2011.

A Computer Game Based Approach for Increasing Fluency in the Speech of the Autistic Children


Autism is a complex developmental disability that typically appears during the first three years of life. This is the result of a neurological disorder that affects the functioning of human brain. Children diagnosed with autism often are self-absorbed and seem to exist in a private world where they are unable to successfully communicate and interact with others. Sometimes they have difficulties in developing speaking skills and understanding what others say to them. Lack of fluency in the speech is one of the most frequently found problems with autistic children. The traditional methods for increasing fluency were found to be monotonous and hence, not much successful during our three months of observations over the participants of Autism Welfare Foundation (AWF) at Dhaka. Therefore, we developed an interactive computer game for the autistic children for improving the fluency in their speech. Our game produced encouraging results over a participant during three months of observation. In this paper, we describe our project and the outcomes.

Anika Anwar, Md. Mustafizur Rahman, S M Ferdous, Samiul Alam Anik, Syed Ishtiaque Ahmed, "A Computer Game Based Approach for Increasing Fluency in the Speech of the Autistic Children." In the proceedings of 2011 IEEE 11th International Conference on Advanced Learning Technologies, 2011.

Increasing Intelligibility in the Speech of the Autistic Children by an Interactive Computer Game


Autism is a disorder of neural development which affects about one in every 150 kids on average. One of the major complexities regarding autistic children in social communication is the speech disorder. The problems related to speech disorder fall into different categories and unintelligibility in speech is one of them. Although there is no definite medicine or treatment for autism, doctors, therapists, and special teachers can help kids with autism overcome many difficulties by different physical and psychological therapies. In this paper we have demonstrated our newly developed interactive computer game which will be helpful in increasing intelligibility in the speeches of autistic children and can be used as a therapy besides the traditional approaches. During our five months of intervention with the autistic children of Autism Welfare Foundation (AWF) at Dhaka, we checked the effectiveness of this therapy and got some encouraging results.

Md. Mustafizur Rahman, S M Ferdous, Syed Ishtiaque Ahmed, "Increasing Intelligibility in the Speech of the Autistic Children by an Interactive Computer Game." In the proceedings of 2010 IEEE International Symposium on Multimedia, 2010.