search

Multi-Objective-NAS / self-supervised-nas

Official implementation of the paper "Pretraining Neural Architecture Search Controllers with Locality-based Self-Supervised Learning" (NeurIPSW 2020)
5 stars 0 forks source link

Edit distance computational considerations #29

Open bhavna-gopal opened 3 years ago

bhavna-gopal commented 3 years ago

The paper states that computing edit distance is manually expensive? What is used to compute edit distance? Isn't the cost of this compute trivial relative to an RL controller? Appreciate your help greatly!

juice500ml commented 3 years ago

Exact computation of graph edit distance is known to be NP-hard (https://en.wikipedia.org/wiki/Graph_edit_distance). We've checked some approximated versions, but never had any success, as those weren't usually for small-scale graphs like we're handling. For the exact ones, we've used the networkx implementations, and it is very CPU-intensive. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.similarity.graph_edit_distance.html#networkx.algorithms.similarity.graph_edit_distance