  Neural Architecture Search (NAS) aims to find efficient models for multiple
tasks. Beyond seeking solutions for a single task, there are surging interests
in transferring network design knowledge across multiple tasks. In this line of
research, effectively modeling task correlations is vital yet highly neglected.
Therefore, we propose \textbf{Arch-Graph}, a transferable NAS method that
predicts task-specific optimal architectures with respect to given task
embeddings. It leverages correlations across multiple tasks by using their
embeddings as a part of the predictor's input for fast adaptation. We also
formulate NAS as an architecture relation graph prediction problem, with the
relational graph constructed by treating candidate architectures as nodes and
their pairwise relations as edges. To enforce some basic properties such as
acyclicity in the relational graph, we add additional constraints to the
optimization process, converting NAS into the problem of finding a Maximal
Weighted Acyclic Subgraph (MWAS). Our algorithm then strives to eliminate
cycles and only establish edges in the graph if the rank results can be
trusted. Through MWAS, Arch-Graph can effectively rank candidate models for
each task with only a small budget to finetune the predictor. With extensive
experiments on TransNAS-Bench-101, we show Arch-Graph's transferability and
high sample efficiency across numerous tasks, beating many NAS methods designed
for both single-task and multi-task search. It is able to find top 0.16\% and
0.29\% architectures on average on two search spaces under the budget of only
50 models.
