$p$-Laplacian Based Graph Neural Networks
  Graph neural networks (GNNs) have demonstrated superior performance for
semi-supervised node classification on graphs, as a result of their ability to
exploit node features and topological information simultaneously. However, most
GNNs implicitly assume that the labels of nodes and their neighbors in a graph
are the same or consistent, which does not hold in heterophilic graphs, where
the labels of linked nodes are likely to differ. Hence, when the topology is
non-informative for label prediction, ordinary GNNs may work significantly
worse than simply applying multi-layer perceptrons (MLPs) on each node. To
tackle the above problem, we propose a new $p$-Laplacian based GNN model,
termed as $^p$GNN, whose message passing mechanism is derived from a discrete
regularization framework and could be theoretically explained as an
approximation of a polynomial graph filter defined on the spectral domain of
$p$-Laplacians. The spectral analysis shows that the new message passing
mechanism works simultaneously as low-pass and high-pass filters, thus making
$^p$GNNs are effective on both homophilic and heterophilic graphs. Empirical
studies on real-world and synthetic datasets validate our findings and
demonstrate that $^p$GNNs significantly outperform several state-of-the-art GNN
architectures on heterophilic benchmarks while achieving competitive
performance on homophilic benchmarks. Moreover, $^p$GNNs can adaptively learn
aggregation weights and are robust to noisy edges.
