Naheed Anjum Arafat

selected publications

1. pVLDB

   Neighborhood-Based Hypergraph Core Decomposition

   Arafat, Naheed Anjum, Khan, Arijit, Rai, Arpit Kumar, and Ghosh, Bishwamittra

   Proc. VLDB Endow. 2023

   Abs HTML PDF

   We propose neighborhood-based core decomposition: a novel way of decomposing hypergraphs into hierarchical neighborhood-cohesive subhypergraphs. Alternative approaches to decomposing hypergraphs, e.g., reduction to clique or bipartite graphs, are not meaningful in certain applications, the later also results in inefficient decomposition; while existing degree-based hypergraph decomposition does not distinguish nodes with different neighborhood sizes. Our case studies show that the proposed decomposition is more effective than degree and clique graph-based decompositions in disease intervention and in extracting provably approximate and application-wise meaningful densest subhypergraphs. We propose three algorithms: Peel, its efficient variant E-Peel, and a novel local algorithm: Local-core with parallel implementation. Our most efficient parallel algorithm Local-core(P) decomposes hypergraph with 27M nodes and 17M hyperedges in-memory within 91 seconds by adopting various optimizations. Finally, we develop a new hypergraph-core model, the (neighborhood, degree)-core by considering both neighborhood and degree constraints, design its decomposition algorithm Local-core+Peel, and demonstrate its superiority in spreading diffusion.

2. DEXA

   Hypergraph drawing by force-directed placement

   Arafat, Naheed Anjum, and Bressan, Stéphane

   Database and Expert Systems Applications 2017

   Abs HTML PDF

   We propose a family of algorithms that transform a hypergraph drawing problem into a graph drawing problem and leverage force-directed graph drawing algorithms in order to draw hypergraphs. We propose and discuss a number of criteria to evaluate the quality of the drawings from the points of view of aesthetics and of visualization and analytics. We empirically and comparatively evaluate the quality of the drawings based on these criteria on both synthetic and real data sets. Experiments reveal that the algorithms are generally effective and the drawings generated are aesthetically pleasing.

3. DEXA

   Topological Data Analysis with ε-net Induced Lazy Witness Complex

   Arafat, Naheed Anjum, Basu, Debabrota, and Bressan, Stéphane

   Database and Expert Systems Applications 2019

   Abs HTML PDF

   Topological data analysis computes and analyses topological features of the point clouds by constructing and studying a simplicial representation of the underlying topological structure. The enthusiasm that followed the initial successes of topological data analysis was curbed by the computational cost of constructing such simplicial representations. The lazy witness complex is a computationally feasible approximation of the underlying topological structure of a point cloud. It is built in reference to a subset of points, called landmarks, rather than considering all the points as in the Čech and Vietoris-Rips complexes. The choice and the number of landmarks dictate the effectiveness and efficiency of the approximation. We adopt the notion of ε-cover to define ε-net. We prove that ε-net, as a choice of landmarks, is an ε-approximate representation of the point cloud and the induced lazy witness complex is a 3-approximation of the induced Vietoris-Rips complex. Furthermore, we propose three algorithms to construct ε-net landmarks. We establish the relationship of these algorithms with the existing landmark selection algorithms. We empirically validate our theoretical claims. We empirically and comparatively evaluate the effectiveness, efficiency, and stability of the proposed algorithms on synthetic and real datasets.

4. DEXA

   Construction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences

   Arafat, Naheed Anjum, Basu, Debabrota, Decreusefond, Laurent, and Bressan, Stéphane

   Database and Expert Systems Applications 2020

   Abs HTML PDF

   We propose algorithms for construction and random generation of hypergraphs without loops and with prescribed degree and dimension sequences. The objective is to provide a starting point for as well as an alternative to Markov chain Monte Carlo approaches. Our algorithms leverage the transposition of properties and algorithms devised for matrices constituted of zeros and ones with prescribed row- and column-sums to hypergraphs. The construction algorithm extends the applicability of Markov chain Monte Carlo approaches when the initial hypergraph is not provided. The random generation algorithm allows the development of a self-normalised importance sampling estimator for hypergraph properties such as the average clustering coefficient.