publications

2024

1. ICML

   Finite Volume Features, Global Geometry Representations, and Residual Training for Deep Learning-based CFD Simulation

   Loh Sher En Jessica*, Naheed Anjum Arafat*, Wei Xian Lim, and 2 more authors

   2024

   * = equal contribution

2023

1. pVLDB

   Neighborhood-Based Hypergraph Core Decomposition

   Naheed Anjum Arafat, Arijit Khan, Arpit Kumar Rai, and 1 more author

   Proc. VLDB Endow., Jul 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.

2020

1. DEXA

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

   Naheed Anjum Arafat, Debabrota Basu, Laurent Decreusefond, and 1 more author

   Database and Expert Systems Applications, Jul 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.

2. arXiv

   Construction and Random Generation of Hypergraphs with Prescribed Degree and Dimension Sequences (extended version)

   Naheed Anjum Arafat, Debabrota Basu, Laurent Decreusefond, and 1 more author

   Jul 2020

   HTML PDF

2019

1. DEXA

   Topological Data Analysis with ε-net Induced Lazy Witness Complex

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

   Database and Expert Systems Applications, Jul 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.

2. ATDA

   ε-net Induced Lazy Witness Complexes on Graphs

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

   Workshop on Applications of Topological Data Analysis (ECML-PKDD), Jul 2019

   Abs HTML PDF

   Computation of persistent homology of simplicial representations such as the Rips and the Cech complexes do not efficiently scale to large point clouds. It is, therefore, meaningful to devise approximate representations and evaluate the trade-off between their efficiency and effectiveness. The lazy witness complex economically defines such a representation using only a few selected points, called landmarks. Topological data analysis traditionally considers a point cloud in a Euclidean space. In many situations, however, data is available in the form of a weighted graph. A graph along with the geodesic distance defines a metric space. This metric space of a graph is amenable to topological data analysis. We discuss the computation of persistent homologies on a weighted graph. We present a lazy witness complex approach leveraging the notion of ε-net that we adapt to weighted graphs and their geodesic distance to select landmarks. We show that the value of the ϵ parameter of the ε-net provides control on the trade-off between choice and number of landmarks and the quality of the approximate simplicial representation. We present three algorithms for constructing an ε-net of a graph. We comparatively and empirically evaluate the efficiency and effectiveness of the choice of landmarks that they induce for the topological data analysis of different real-world graphs.

3. SEC

   Evolutionary algorithm using adaptive fuzzy dominance and reference point for many-objective optimization

   Siddhartha Shankar Das, Md Monirul Islam, and Naheed Anjum Arafat

   Swarm and Evolutionary Computation, Jul 2019

   Abs HTML

   Many-objective optimization is very important for numerous practical applications. It, however, poses a great challenge to the Pareto dominance based evolutionary algorithms. In this paper, a fuzzy dominance based evolutionary algorithm is proposed for many-objective optimization. The essence of the proposed algorithm is that it adaptively determines a fuzzy membership function for each objective of a given many-objective optimization problem and employs preferred reference points for clustering evolved solutions. Our algorithm uses distribution information of the evolving population to find preferred reference points from a set of generated reference points. The aim of using such preferred points is to emphasize both convergence and diversity of all the evolved solutions by maintaining cluster uniformity and handling irregular Pareto front. Extensive experimentation has been performed on a number of benchmark problems in evolutionary computing, including nine Waking-Fish-Group and seven Deb-Thiele-Laumanns-Zitzler benchmark problems having 2 to 25 objectives. In addition, we have investigated the performance of the proposed algorithm on three instances of degenerate Rectangle Problems. The experimental results show that the proposed algorithm is able to solve many-objective optimization problems efficiently, and it is compared favorably with the other evolutionary algorithms devised for such problems. A parametric study is also provided to understand the influence of a key parameter of the proposed algorithm.

2017

1. DEXA

   Hypergraph drawing by force-directed placement

   Naheed Anjum Arafat, and Stéphane Bressan

   Database and Expert Systems Applications, Jul 2017

   Abs HTML PDF Video

   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.