MAMuhammad Ahmad

Muhammad Ahmad

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Muhammad Ahmad has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    SsAG : Summarization and Sparsification of Attributed Graphs

    by Sarwan Ali, Muhammad Ahmad, Maham Anwer Beg, Imdad Ullah Khan, Safiullah Faizullah, Muhammad Asad Khan

    Graph summarization has become integral for managing and analyzing large-scale graphs in diverse real-world applications, including social networks, biological networks, and communication networks. Existing methods for graph summarization often face challenges, being either computationally expensive, limiting their applicability to large graphs, or lacking the incorporation of node attributes. In response, we introduce SsAG , an efficient and scalable lossy graph summarization method designed to preserve the essential structure of the original graph. SsAG computes a sparse representation (summary) of the input graph, accommodating graphs with node attributes. The summary is structured as a graph on supernodes (subsets of vertices of G ), where weighted superedges connect pairs of supernodes. The methodology focuses on constructing a summary graph with k supernodes, aiming to minimize the reconstruction error (the difference between the original graph and the graph reconstructed from the summary) while maximizing homogeneity with respect to the node attributes. The construction process involves iteratively merging pairs of nodes. To enhance computational efficiency, we derive a closed-form expression for efficiently computing the reconstruction error (RE) after merging a pair, enabling constant-time approximation of this score. We assign a weight to each supernode, quantifying their contribution to the score of pairs, and utilize a weighted sampling strategy to select the best pair for merging. Notably, a logarithmic-sized sample achieves a summary comparable in quality based on various measures. Additionally, we propose a sparsification step for the constructed summary, aiming to reduce storage costs to a specified target size with a marginal increase in RE. Empirical evaluations across diverse real-world graphs demonstrate that SsAG exhibits superior speed, being up to 17 × faster, while generating summaries of comparable quality. This work represents a significant advancement in the field, addressing computational challenges and showcasing the effectiveness of SsAG in graph summarization.


  • Open Access

    Efficient Data Analytics on Augmented Similarity Triplets

    by Sarwan Ali, Muhammad Ahmad, Umair Ul Hassan, Muhammad Asad Khan, Shafiq Alam, Imdadullah Khan

    Data analysis require a pairwise proximity measure over objects. Recent work has extended this to situations where the distance information between objects is given as comparison results of distances between three objects (triplets). Humans find the comparison tasks much easier than the exact distance computation and such data can be easily obtained in big quantity via crowd-sourcing. In this work, we propose triplets augmentation, an efficient method to extend the triplets data by inferring the hidden implicit information form the existing data. Triplets augmentation improves the quality of kernel-based and kernel-free data analytics. We also propose a novel set of algorithms for common data analysis tasks based on triplets. These methods work directly with triplets and avoid kernel evaluations, thus are scalable to big data. We demonstrate that our methods outperform the current best-known techniques and are robust to noisy data.

  • Open Access

    SsAG: Summarization and sparsification of Attributed Graphs

    by Sarwan Ali, Muhammad Ahmad, Maham Anwer Beg, Imdad Ullah Khan, Safiullah Faizullah, Muhammad Asad Khan

    We present SsAG, an efficient and scalable lossy graph summarization method that retains the essential structure of the original graph. SsAG computes a sparse representation (summary) of the input graph and also caters to graphs with node attributes. The summary of a graph $G$ is stored as a graph on supernodes (subsets of vertices of $G$), and a weighted superedge connects two supernodes. The proposed method constructs a summary graph on $k$ supernodes that minimize the reconstruction error (difference between the original graph and the graph reconstructed from the summary) and maximum homogeneity with respect to attributes. We construct the summary by iteratively merging a pair of nodes. We derive a closed-form expression to efficiently compute the reconstruction error after merging a pair and approximate this score in constant time. To reduce the search space for selecting the best pair for merging, we assign a weight to each supernode that closely quantifies the contribution of the node in the score of the pairs containing it. We choose the best pair for merging from a random sample of supernodes selected with probability proportional to their weights. A logarithmic-sized sample yields a comparable summary based on various quality measures with weighted sampling. We propose a sparsification step for the constructed summary to reduce the storage cost to a given target size with a marginal increase in reconstruction error. Empirical evaluation on several real-world graphs and comparison with state-of-the-art methods shows that SsAG is up to $5\times$ faster and generates summaries of comparable quality.

  • Combinatorial trace method for network immunization

    by Muhammad Ahmad, Sarwan Ali, Juvaria Tariq, Imdadullah Khan, Mudassir Shabbir, Arif Zaman