  This paper studies node classification in the inductive setting, i.e., aiming
to learn a model on labeled training graphs and generalize it to infer node
labels on unlabeled test graphs. This problem has been extensively studied with
graph neural networks (GNNs) by learning effective node representations, as
well as traditional structured prediction methods for modeling the structured
output of node labels, e.g., conditional random fields (CRFs). In this paper,
we present a new approach called the Structured Proxy Network (SPN), which
combines the advantages of both worlds. SPN defines flexible potential
functions of CRFs with GNNs. However, learning such a model is nontrivial as it
involves optimizing a maximin game with high-cost inference. Inspired by the
underlying connection between joint and marginal distributions defined by
Markov networks, we propose to solve an approximate version of the optimization
problem as a proxy, which yields a near-optimal solution, making learning more
efficient. Extensive experiments on two settings show that our approach
outperforms many competitive baselines.
