  Graph Neural Networks (GNNs) have shown advantages in various graph-based
applications. Most existing GNNs assume strong homophily of graph structure and
apply permutation-invariant local aggregation of neighbors to learn a
representation for each node. However, they fail to generalize to heterophilic
graphs, where most neighboring nodes have different labels or features, and the
relevant nodes are distant. Few recent studies attempt to address this problem
by combining multiple hops of hidden representations of central nodes (i.e.,
multi-hop-based approaches) or sorting the neighboring nodes based on attention
scores (i.e., ranking-based approaches). As a result, these approaches have
some apparent limitations. On the one hand, multi-hop-based approaches do not
explicitly distinguish relevant nodes from a large number of multi-hop
neighborhoods, leading to a severe over-smoothing problem. On the other hand,
ranking-based models do not joint-optimize node ranking with end tasks and
result in sub-optimal solutions. In this work, we present Graph Pointer Neural
Networks (GPNN) to tackle the challenges mentioned above. We leverage a pointer
network to select the most relevant nodes from a large amount of multi-hop
neighborhoods, which constructs an ordered sequence according to the
relationship with the central node. 1D convolution is then applied to extract
high-level features from the node sequence. The pointer-network-based ranker in
GPNN is joint-optimized with other parts in an end-to-end manner. Extensive
experiments are conducted on six public node classification datasets with
heterophilic graphs. The results show that GPNN significantly improves the
classification performance of state-of-the-art methods. In addition, analyses
also reveal the privilege of the proposed GPNN in filtering out irrelevant
neighbors and reducing over-smoothing.
