We propose Multi-Conditional Graph Recurrent Attention Networks (MCGRAN) to learn conditional distributions over labeled graphs and show their application in Neural Architecture Search. MCGRAN learns neural network architectures as labeled directed acyclic graphs. With proper conditioning MCGRAN can generate neural network architectures with different performance characteristics. MCGRAN generates architectures with test accuracies of 0.90±0.01 in a high performing regime but also meets test accuracies of 0.53±0.17 when specifically conditioned on low performing architectures. With graph edit distances we demonstrate that 99% of the generated neural network architectures are novel and unique. Using an iterative conditional search, we show that neural network architectures can hierarchically be decomposed in terms of model parameters, training time, and accuracy. Also, we apply MCGRAN to learn random graphs such as Watts-Strogatz and Barabasi-Albert graphs. Our results show that MCGRAN can approximate the Watts-Strogatz graph’s average path length data distribution with a difference of only 0.01. Open source code and statistics accompany our work.