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.

2023

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

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.