  Graph-Convolution-based methods have been successfully applied to
representation learning on homophily graphs where nodes with the same label or
similar attributes tend to connect with one another. Due to the homophily
assumption of Graph Convolutional Networks (GCNs) that these methods use, they
are not suitable for heterophily graphs where nodes with different labels or
dissimilar attributes tend to be adjacent. Several methods have attempted to
address this heterophily problem, but they do not change the fundamental
aggregation mechanism of GCNs because they rely on summation operators to
aggregate information from neighboring nodes, which is implicitly subject to
the homophily assumption. Here, we introduce a novel aggregation mechanism and
develop a RAndom Walk Aggregation-based Graph Neural Network (called RAW-GNN)
method. The proposed approach integrates the random walk strategy with graph
neural networks. The new method utilizes breadth-first random walk search to
capture homophily information and depth-first search to collect heterophily
information. It replaces the conventional neighborhoods with path-based
neighborhoods and introduces a new path-based aggregator based on Recurrent
Neural Networks. These designs make RAW-GNN suitable for both homophily and
heterophily graphs. Extensive experimental results showed that the new method
achieved state-of-the-art performance on a variety of homophily and heterophily
graphs.
