  In recent years, graph neural networks (GNNs) have become increasingly
popular for solving NP-hard combinatorial optimization (CO) problems, such as
maximum cut and maximum independent set. The core idea behind these methods is
to represent a CO problem as a graph and then use GNNs to learn the node/graph
embedding with combinatorial information. Although these methods have achieved
promising results, given a specific CO problem, the design of GNN architectures
still requires heavy manual work with domain knowledge. Existing automated GNNs
are mostly focused on traditional graph learning problems, which is
inapplicable to solving NP-hard CO problems. To this end, we present a new
class of \textbf{AUTO}mated \textbf{G}NNs for solving \textbf{NP}-hard
problems, namely \textbf{AutoGNP}. We represent CO problems by GNNs and focus
on two specific problems, i.e., mixed integer linear programming and quadratic
unconstrained binary optimization. The idea of AutoGNP is to use graph neural
architecture search algorithms to automatically find the best GNNs for a given
NP-hard combinatorial optimization problem. Compared with existing graph neural
architecture search algorithms, AutoGNP utilizes two-hop operators in the
architecture search space. Moreover, AutoGNP utilizes simulated annealing and a
strict early stopping policy to avoid local optimal solutions. Empirical
results on benchmark combinatorial problems demonstrate the superiority of our
proposed model.
