  Node features and structural information of a graph are both crucial for
semi-supervised node classification problems. A variety of graph neural network
(GNN) based approaches have been proposed to tackle these problems, which
typically determine output labels through feature aggregation. This can be
problematic, as it implies conditional independence of output nodes given
hidden representations, despite their direct connections in the graph. To learn
the direct influence among output nodes in a graph, we propose the Explicit
Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph
as a partially observed Markov Random Field. It contains explicit pairwise
factors to model output-output relations and uses a GNN backbone to model
input-output relations. To balance model complexity and expressivity, the
pairwise factors have a shared component and a separate scaling coefficient for
each edge. We apply the EM algorithm to train our model, and utilize a
star-shaped piecewise likelihood for the tractable surrogate objective. We
conduct experiments on various datasets, which shows that our model can
effectively improve the performance for semi-supervised node classification on
graphs.
