Network Design through Graph Neural Networks: Identifying Challenges and
  Improving Performance
Donald Loveland Rajmonda Caceres
Graph Neural Network (GNN) research has produced strategies to modify a
graph's edges using gradients from a trained GNN, with the goal of network
design. However, the factors which govern gradient-based editing are
understudied, obscuring why edges are chosen and if edits are grounded in an
edge's importance. Thus, we begin by analyzing the gradient computation in
previous works, elucidating the factors that influence edits and highlighting
the potential over-reliance on structural properties. Specifically, we find
that edges can achieve high gradients due to structural biases, rather than
importance, leading to erroneous edits when the factors are unrelated to the
design task. To improve editing, we propose ORE, an iterative editing method
that (a) edits the highest scoring edges and (b) re-embeds the edited graph to
refresh gradients, leading to less biased edge choices. We empirically study
ORE through a set of proposed design tasks, each with an external validation
method, demonstrating that ORE improves upon previous methods by up to 50%.