publications

2024

1. Graph Edit Distance with General Costs Using Neural Set Divergence

   Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De

   In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

   Abs Bib PDF

   Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs, in terms of the minimum-cost edit sequence that transforms one graph to the other. However, the exact computation of GED is NP-Hard, which has recently motivated the design of neural methods for GED estimation. However, they do not explicitly account for edit operations with different costs. In response, we propose GRAPHEDX, a neural GED estimator that can work with general costs specified for the four edit operations, viz., edge deletion, edge addition, node deletion and node addition. We first present GED as a quadratic assignment problem (QAP) that incorporates these four costs. Then, we represent each graph as a set of node and edge embeddings and use them to design a family of neural set divergence surrogates. We replace the QAP terms corresponding to each operation with their surrogates. Computing such neural set divergence require aligning nodes and edges of the two graphs. We learn these alignments using a Gumbel-Sinkhorn permutation generator, additionally ensuring that the node and edge alignments are consistent with each other. Moreover, these alignments are cognizant of both the presence and absence of edges between node-pairs. Experiments on several datasets, under a variety of edit cost settings, show that GRAPHEDX consistently outperforms state-of-the-art methods and heuristics in terms of prediction error.

   @inproceedings{anonymous2024graph,
     title = {Graph Edit Distance with General Costs Using Neural Set Divergence},
     author = {Jain, Eeshaan and Roy, Indradyumna and Meher, Saswat and Chakrabarti, Soumen and De, Abir},
     booktitle = {The Thirty-eighth Annual Conference on Neural Information Processing Systems},
     year = {2024},
     url = {https://openreview.net/forum?id=u7JRmrGutT},
     bibtex_show = true,
     pdf = {2409.17687v1.pdf}
   }

2023

1. Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks

   Eeshaan Jain, Tushar Nandy, Gaurav Aggarwal, Ashish V. Tendulkar, Rishabh K Iyer, and Abir De

   In Thirty-seventh Conference on Neural Information Processing Systems, 2023

   Abs Bib PDF

   Existing subset selection methods for efficient learning predominantly employ discrete combinatorial and model-specific approaches, which lack generalizability— for each new model, the algorithm has to be executed from the beginning. Therefore, for an unseen architecture, one cannot use the subset chosen for a different model. In this work, we propose SubSelNet, a non-adaptive subset selection framework, which tackles these problems. Here, we first introduce an attention-based neural gadget that leverages the graph structure of architectures and acts as a surrogate to trained deep neural networks for quick model prediction. Then, we use these predictions to build subset samplers. This naturally provides us two variants of SubSelNet. The first variant is transductive (called Transductive-SubSelNet), which computes the subset separately for each model by solving a small optimization problem. Such an optimization is still super fast, thanks to the replacement of explicit model training by the model approximator. The second variant is inductive (called Inductive-SubSelNet), which computes the subset using a trained subset selector, without any optimization. Our experiments show that our model outperforms several methods across several real datasets.

   @inproceedings{jain2023efficient,
     title = {Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks},
     author = {Jain, Eeshaan and Nandy, Tushar and Aggarwal, Gaurav and Tendulkar, Ashish V. and Iyer, Rishabh K and De, Abir},
     booktitle = {Thirty-seventh Conference on Neural Information Processing Systems},
     year = {2023},
     url = {https://openreview.net/forum?id=q3fCWoC9l0},
     bibtex_show = true,
     pdf = {neurips2023.pdf}
   }