Neural architecture search (NAS) has recently been addressed from various\ndirections, including discrete, sampling-based methods and efficient\ndifferentiable approaches. While the former are notoriously expensive, the\nlatter suffer from imposing strong constraints on the search space.\nArchitecture optimization from a learned embedding space for example through\ngraph neural network based variational autoencoders builds a middle ground and\nleverages advantages from both sides. Such approaches have recently shown good\nperformance on several benchmarks. Yet, their stability and predictive power\nheavily depends on their capacity to reconstruct networks from the embedding\nspace. In this paper, we propose a two-sided variational graph autoencoder,\nwhich allows to smoothly encode and accurately reconstruct neural architectures\nfrom various search spaces. We evaluate the proposed approach on neural\narchitectures defined by the ENAS approach, the NAS-Bench-101 and the\nNAS-Bench-201 search space and show that our smooth embedding space allows to\ndirectly extrapolate the performance prediction to architectures outside the\nseen domain (e.g. with more operations). Thus, it facilitates to predict good\nnetwork architectures even without expensive Bayesian optimization or\nreinforcement learning.\n