  Real-world graphs exhibit increasing heterophily, where nodes no longer tend
to be connected to nodes with the same label, challenging the homophily
assumption of classical graph neural networks (GNNs) and impeding their
performance. Intriguingly, we observe that certain high-order information on
heterophilous data exhibits high homophily, which motivates us to involve
high-order information in node representation learning. However, common
practices in GNNs to acquire high-order information mainly through increasing
model depth and altering message-passing mechanisms, which, albeit effective to
a certain extent, suffer from three shortcomings: 1) over-smoothing due to
excessive model depth and propagation times; 2) high-order information is not
fully utilized; 3) low computational efficiency. In this regard, we design a
similarity-based path sampling strategy to capture smooth paths containing
high-order homophily. Then we propose a lightweight model based on multi-layer
perceptrons (MLP), named PathMLP, which can encode messages carried by paths
via simple transformation and concatenation operations, and effectively learn
node representations in heterophilous graphs through adaptive path aggregation.
Extensive experiments demonstrate that our method outperforms baselines on 16
out of 20 datasets, underlining its effectiveness and superiority in
alleviating the heterophily problem. In addition, our method is immune to
over-smoothing and has high computational efficiency.
