RAW-GNN: RAndom Walk Aggregation based Graph Neural Network

1 Introduction

Graphs are ubiquitous in the real world, such as social networks, brain networks, transportation networks and citation networks. Network analysis [Wang et al., 2016; Jin et al., 2021] has been extensively studied and broadly applied in many fields, ranging from computer science to social sciences, biology, physics, and many more. Recently, messagepassing neural networks (MPNNs) [Kipf and Welling, 2017]

∗Corresponding authors

have been successfully adopted for various problems on graphs, e.g., node classification, graph classification, link prediction, and anomaly detection [Wang et al., 2022; Yu et al., 2021].

An MPNN runs an iterative process and in each iteration, every node sends its features as a message to its neighbors and then aggregates messages from other nodes to update its representation. GCN [Kipf and Welling, 2017], as a typical MPNN, works under the homophily assumption - i.e., most connected nodes are from the same class and have similar attributes. GCN and its variants, like GraphSAGE [Hamilton et al., 2017], possess great power for learning on graphs and have shown excellent performance on many downstream tasks on networks with homophily.

However, many real-world networks do not satisfy the homophily assumption. But rather, there exist many heterophily or low homophily networks where most adjacent nodes may belong to different classes and have dissimilar attributes. For example, in protein structures, an amino acid type is more likely to connect to different amino acid types rather than the same amino acid type; In email networks, spam users often contact normal users; In e-commerce networks, fraudsters are more likely to connect to accomplices than to other fraudsters. Conventional GCNs are not designed for heterophily networks and they use message propagation mechanisms based on the homophily assumption, as a result, information from different classes will get mixed during propagation on heterophily networks using such message propagation methods.

To deal with the homogeneity restriction in GCNs, several methods have already been proposed. Based on the aggregation mechanisms that they use, these methods can be divided into two categories: (1) Methods adjusting attention weights between neighbors of different labels in aggregation, which include GGCN [Yan et al., 2021], CPGNN [Zhu et al., 2021a], HOG-GCN [Wang et al., 2022], GNN-LF/HF[Zhu et al., 2021b] and BM-GCN [He et al., 2022]. In essence, these methods assign a weight to each connected node pair with the guidance of heterophily information. In specific, label-guided methods [Zhu et al., 2021a; Wang et al., 2022; He et al., 2022] integrate label information into their framework and aggregate nodes with the same label in the neighborhood and reduce the degree of aggregation of neighbors with different labels; Signed-message-guided methods [Yan et al., 2021; Zhu et al., 2021b] extend attention weight from

[0, 1] to [-1, 1]. As a result, messages between nodes of the same type of label are assigned positive weights, which boost message passing in the same class, and messages between nodes of different labels are given negative values, which prevent dissimilar neighbors from passing harmful and irrelevant information to one another. (2) Methods directly aggregating messages among higher-order neighbor nodes, including Geom-GCN [Pei et al., 2020], H2GCN [Zhu et al., 2020], GPR-GNN [Chien et al., 2021] and LINKX [Lim et al., 2021]. These methods assume that directly adjacent neighborhoods may be heterophily-dominant for heterophily network, but the higher-order neighborhoods are homophilydominant which can provide more useful information for the target node. By explicitly aggregating information from higher-order neighborhoods, these methods alleviate the heterophily problem to certain extent.

However, these methods do not change the fundamental aggregation mechanism of GCNs because of the summation operator in the aggregation process, which is implicitly subject to the homophily assumption. To be specific, labelguided methods try to learn the weights between nodes of different labels to 0. In fact, this is equivalent to omitting the information of heterophily nodes in the aggregation, which is useful for network representation learning and downstream tasks. In signed-message-guided methods, weight -1 is introduced based on an analysis of graphs with two kinds of labels, so that this design is only effective on networks with a small class number close to 2 and do not work well for networks with large number of classes. In short, these designs alleviate the homogeneity restriction problem to some extent, but they are still constraint by the summation aggregator. In addition, the existing methods that directly aggregate higherorder neighbor use the classical summation aggregator to aggregate higher-order neighbors based on their distances to the target node and concatenate aggregated results with different distances. These methods also suffer from the constraints of the summation aggregator.

To address these problems, we introduce a new aggregation mechanism and propose a RAndom Walk aggregationbased Graph Neural Network, short-handed as RAW-GNN. We integrate random walk sampling into graph neural networks and extend the conventional neighborhoods to k-hop path-based neighborhoods. A k-hop path formed by random walks preserves the original attributes on this k nodes and the original structural connections of these nodes in the random walk sequence. In this way, the path-based neighborhoods can represent the neighborhood distribution of the target node better than the conventional neighborhoods. Furthermore, we utilize breadth-first search random walk (BFS) to capture homophily information and depth-first search (DFS) to collect heterophily information. To go beyond the exiting aggregation mechanism of GCNs and to take full advantage of the path-based neighborhoods, we adopt a sequential Recurrent Neural Networks (RNN) based aggregator, which can take into consideration the order information of neighbor nodes preserved by random walks. The RNNs have the advantage that they can handle the diverse attributes of adjacent nodes, which accommodates the need for heterophily networks. Finally, we use the attention mechanism to learn the importance of different paths from DFS channel (and BFS channel respectively), which can better extract heterophily (and homophily) neighborhood distribution with minimal mixing of information and can enable the model to automatically make a trade-off between homophily and heterophily according to different network characteristics.

2 Preliminaries

We now present notations and related definitions, including path-based neighborhood and generalized homophily ratio, which are important for our work.

2.1 Basic Notations

Let G = (V,E,X) denote an undirected, unweighted and attributed network, where V = {v1, v2, ..., vn} is a set of n nodes and X ∈ Rn×f is a set of node attributes. Every node i is associated with f attributes xi, which form the i-th row of X. E = {eij} ⊆ V × V is a set of edges represented by an adjacency matrix A = [aij ] ∈ Rn×n , where aij = 1 if nodes vi and vj are connected, or aij = 0 otherwise.

In this paper, we focus on semi-supervised node classification task. In a semi-supervised node classification task, every node belongs to a class c ∈ C and |C| is the number of classes. Here, the labels of nodes are given in set VL. Every node vi ∈ VL is assigned with a label yi ∈ L = {1, 2, ...|C|}. The objective of node classification task is to predict the labels for all the unlabeled nodes in node set V \VL.

2.2 Message-Passing Neural Network

In a message-passing neural network, neighborhood is defined as neighbor nodes that are one or more hops away. Messages from nearby nodes are aggregated to the target node and updated iteratively. The l-th layer of a MPNN can be defined as follows:

where h(l) i is the feature vector of node i in the l-th layer. The beginning vector h(0) i is xi, and Ni is a set of neighbor nodes of node i. Different choices of Ni, aggregate(l) and combine(l) result in different models. Usually, the neighbor nodes of node i are either the adjacent nodes of i or the khop neighbor nodes of i. In the following subsection, we will define another kind of neighborhood, which is based on paths.

2.3 Path-based Neighborhoods

The path-based neighborhood has already been applied to heterogeneous graphs [Fu et al., 2020] and knowledge graphs [Du et al., 2021]. Here we modify their definition to make it suitable for heterophily graphs. Formally, a path P is defined in the form of an ordered list P = {vp1 , vp2 , ..., vpK }, where vpk ∈ V, k = 1, 2, ...,K and epkpk+1 ∈ E, k = 1, 2, ..., K - 1, and K is the length of the path. A path-based neighbor of node i is denoted as Pi, where the ending node in the list vpK is vi. All path-based neighbor Pi of node i collected by strategy s ∈ S forms the path-based neighborhood N s i , where S is the set of strategies. In other words, all Pi ∈ N s i .

2.4 Generalized Edge Homophily Ratio

The edge homophily ratio [Zhu et al., 2020] measures the overall homophily in a graph. Specifically, it measures the fraction of edges that connect nodes that have the same label and it is defined as Hlabel E (G) = |{(u, v) : eu,v ∈ E ∧ yu = yv}|/|E|. This metric is based on node labels. Here we generalize edge homophily ratio to node features. First, we define the similarity function between two nodes as sim : V × V → [0, 1]. This function should have such property that, when node i and node j are similar, sim(i, j) is close to 1 and when node i and node j are dissimilar, sim(i, j) is close to 0. Then the generalized edge homophily ratio HE : G → [0, 1] is defined as:

when the similarity function sim(i, j) is Eq. (3), Eq. (2) becomes the label-based edge homophily ratio mentioned above.

We can also use node features to define node similarity, e.g., cosine similarity in Eq. (4), then we can generalize the concept of homophily ratio to features.

3 The Architecture

In this section, we describe the proposed RAW-GNN for homophily and heterophily graph embedding. We start with a brief overview and then introduce the details of components.

3.1 Overview

To let the aggregation mechanism truly go beyond the homophily assumption, here we propose a novel approach that consists of four components: random walk generator, RNNbased path aggregator, attention-based intra-strategy combinator and inter-strategy combinator. The whole framework of our approach RAW-GNN is shown in Fig. 2. Different from the frameworks of other GCNs, we encode the homophily and heterophily information into two different channels. In specific, we use two random walk generators to sample k-hop paths, i.e., using Breadth-First Search random walk (BFS) generator to sample homophily neighborhood distribution and Depth-First Search (DFS) generator to sample heterophily neighborhood distribution. Each sampling strategy (BFS or DFS) will sample multiple paths so as to capture the neighborhood distribution more accurately. After getting BFS neighborhood paths and DFS neighborhood paths, two RNN-based path aggregators are used to aggregate the ordered attributes of nodes in a path to form a path embedding. Then, we use the attention mechanism to learn the importance of different paths from DFS strategy and BFS strategy respectively, and form two strategy-specific embeddings. At last, we concatenate the two embeddings from BFS channel and DFS channel to form the whole embedding which can represent homophily and heterophily information together in the same framework.

3.2 RandomWalk Generator

The key role of neighbors is to provide useful information for the target node, so it doesn't have to be like neighborhoods in classical GCNs. Here, we use paths to define neighborhood. However, given a receptive field, there are more paths than nodes so that it is not computationally feasible to use all the paths especially when the receptive field is large. To collect more information with fewer paths in the search space, we adopt a 2-nd order random walk with two parameters p and q from Node2Vec [Grover and Leskovec, 2016] to simulate Breadth-first Search and Depth-first Search.

Consider a random walk that has traversed edge et,s , is now on node s and is going to visit the next node r. We set the unnormalized transition probability as follows:

where dtr is the length of the shortest path between nodes s and r. When we set p < 1 and q > 1, the random walk tends to behave like BFS; and when p > 1 and q < 1, the random walk tends to behave like DFS.

BFS collects information from the immediate neighbors of the target node and can extract homophily information (Fig. 2). DFS tends to sequentially reach nodes at increasing distances from the source node, which can extract heterophily information. Since real networks exhibit both homophily and heterophily, so both search strategies are applied.

3.3 RNN-based Path Aggregator

Given a path Pi, a path aggregator should learn the structural and semantic information of all nodes on P, not just the starting node vi and the ending target node, but also all the context nodes in between. Note that the existing methods that treat all neighboring nodes as an unordered set. Nevertheless, a path naturally comes with an order, which also preserves the ordered connections among the nodes on the path. The objective of the path aggregator is to encode all the nodes on the path and consider the order of the nodes on the path to preserve more relational information among the connected nodes. The path aggregator fpath (l) : RK×dl → Rdl for the l-th layer is defined as:

where h(l) P ∈ Rdl is the l-th layer embedding vector of path P = {vn1 , vn2 , ..., vnK }, h(l) pk ∈ Rdl is the feature of node vnk in layer l, k = 1, 2, ...,K and θ represents all the learnable parameters of the aggregator. To encode a path, we can use any encoder that takes the order of elements into consideration. Here we choose a simple sequence encoders GRU (Gate Recurrent Unit) [Cho et al., 2014], a variant of RNN with a gating mechanism as the message function.

For simplicity, we set the layer to l and omit the superscript indicating the layer of an embedding in the rest of the paper unless otherwise specified.

3.4 Attention-based Intra-Strategy Combinator

After computing the path embeddings hsP ∈ N S i for every node vi ∈ V for strategy s, we need to combine them into strategy-specific node embeddings. We assume that given a certain sampling strategy, the generated paths obey a corresponding distribution . Since all paths are sampled from the same distribution, it is reasonable to sum these paths to approximate the corresponding distribution. It is worth noting that this summation is different from combining node embeddings in GCNs because the pattern exhibited in a path cannot be well captured in a single node and beginning with summing node embeddings like typical GCNs weakens such path pattern. Furthermore, different paths may contribute differently to the target node embedding, so that we adopt an attention mechanism to learn the different weight of the path embeddings in N S i , which is defined as:

where aP ∈ Rdl is the learnable attention parameter, aTP denotes the transpose of aP , eP is the unnormalized importance weight of path P , and αP is the path weight normalized across all the paths in N S i using softmax. It is worth noting that we do not consider the embedding of the target node hi separately again during the combination procedure like Eq. (1), since every path in N S i already contains hi as its ending node embedding. To further stabilize the learning process, we adopt the standard multi-head attention. Specifically, H attention heads in Eq. (7) are used and then their embeddings are concatenated, which is formalized as:

3.5 Inter-Strategy Combinator

After aggregating the path information within every strategy, we need to combine them using an inter-strategy combination layer. Since different strategies gather paths of different distribution, in order to combine embeddings from different strategies without mixing them, we use concatenation to combine embeddings from different strategies, rather than summing them as done in the GCN [Kipf and Welling, 2017] model, which is given by:

where hi ∈ Rdfinal is the final embedding of node vi, dfinal = H × dL × |S|, and |S| is the number of strategies.

3.6 Classifier

In this work, we focus on the semi-supervised node classification task. We use a linear layer followed by a softmax to compute the predicted label probabilities, and employ the standard cross-entropy as the loss:

where W ∈ Rdfinal×|C| is the learnable weight matrix and Yi, ˆ yi ∈ R|C| is the one-hot embedding of label yi and the predicted label of i respectively, Yic = 1 when c = yi. The other elements in Yi are all set to zero.

4 Experiments

We now compare our RAW-GNN with the state-of-the-art models on the problems of node classification and visualization using seven real-world datasets varying from strong heterophily to strong homophily.

4.1 Datasets

To demonstrate that RAW-GNN can adaptively learn path propagation mechanism under both homophily and heterophily, we evaluate the performance of RAW-GNN and the existing state-of-the-art methods on seven real-world datasets, including three homophilic networks and four heterophilic networks. The features of these datasets are summarized in Table ??. L.H.R. represents the label-defined edge homophily ratio of the network. F.H.R represents the cosine feature edge homophily ratio of the network.

Cora, Citeseer and Pubmed are homophilic citation network benchmark datasets [Sen et al., 2008; Namata et al., 2012], where nodes represent papers, and edges represent citations between papers. Node features are the bag-of-words representation of papers, and node labels are academic topics.

Cornell, Texas and Wisconsin are webpage datasets collected from computer science departments of corresponding universities [Pei et al., 2020], where nodes represent web pages, edges are hyperlinks, node features are the bag-ofwords representation of webpages, and node labels are pages categories (student, project, course, staff, and faculty). Actor is a heterophilic actor co-occurrence network [Tang et al., 2009], in which nodes correspond to an actor, and the edge between two nodes denotes co-occurrence on the same Wikipedia page. Node features correspond to some keywords in the Wikipedia pages. Node labels are categories in term of words of actor's Wikipedia.

4.2 Baselines

We compare our proposed approach RAW-GNN with the following baseline methods: 1) MLP (Multi-Layer Perceptron), which only uses node attributes; 2) Node2Vec [Grover and Leskovec, 2016], which only uses graph structures. Since our work adopt a similar random walk sampling strategy of Node2Vec, we add it for comparison; 3) Traditional GNN models : GCN [Kipf and Welling, 2017] and GraphSAGE [Hamilton et al., 2017], which work under homophily assumption; 4) Frameworks designed for heterophily: H2GCN [Zhu et al., 2020], CPGNN [Zhu et al., 2021a], GPR-GNN [Chien et al., 2021], BM-GCN [He et al., 2022] and HOGGCN [Wang et al., 2022]. In this paper, we choose the best results of each method for comparison, since some methods have more than one variants.

4.3 Parameter Setup

Following [Pei et al., 2020] and [Wang et al., 2022], we generate 10 random splits for all datasets. In each dataset, 48% of the nodes are used as the training set, 32% of the nodes are used as the validation set, and the rest as the test set. For a fair comparison, all methods use the same 10 random splits. All the parameters of the baseline methods were set as what were used by their authors. For the random walk sampling in RAW-GNN, we use DFS strategy with p = 10, q = 0.1 and BFS strategy with p = 0.1, q = 10. We choose different path lengths from {3, 4, 5, 6, 7} for different datasets. With every strategy, we sample 6 paths for each node in one epoch. For the RNN-based aggregator, we use GRU with 32 hidden units and attention head number is set to 2. The learning rate is set to 0.05. We adopt the Adam optimizer and the default initialization in Pytorch.

4.4 Node Classification

We conduct experiments on seven real-world datasets to compare the performance of different models for node classification (Table ??). We use the mean accuracy and standard deviation as the evaluation metric. As shown, our RAW-GNN performs best on 5 out of 7 networks. Below are the detailed observations.

• Our RAW-GNN approach performs the best on all of the four heterophilic networks, i.e., Texas, Wisconsin, Actor, and Cornell, which empirically proves the effectiveness of RAW-GNN. To be specific, RAW-GNN outperforms heterophily-agnostic models, i.e., Node2Vec, GCN and GraphSAGE, by 34.20%, 25.33% and 2.81% respectively. This is largely because the rival methods cannot generalize to heterophilic scenarios. GraphSAGE performs relatively well and we assume the reason is the use of neighbor sampling like our RAW-GNN,

which demonstrates the effectiveness of sampling in heterophily graphs. Compared with the methods designed for heterophily, such as H2GCN, CPGNN and GPRGNN, BM-GCN, and HOG-GCN, RAW-GNN also achieves an improvement between 0.88% and 10.35% by mean accuracy. These results demonstrate the effectiveness of our new method on heterophily networks.

• On homophilic networks, i.e., Cora, Citeseer, and Pubmed, RAW-GNN also has competitive performance compared with the baselines. Specifically, RAW-GNN performs the best on Cora and the second best on Pubmed. We assume that since every dataset is a mixture of homophily and heterophily, the heterophily information from the DFS channel also helps model performance on these homophily datasets. Note that RAWGNN outperforms GCN and GraphSAGE on all these datasets by 1.32% and 0.87% by mean accuracy. These results demonstrate that RAW-GNN still maintains comparable performance on homophilic datasets. Furthermore, for datasets with lower cosine feature homophily ratios (F.H.R < 0.2), the best path-length is longer, which indicates that heterophily networks need large receptive field to extract the hidden neighborhood distribution in the network. These results show the effectiveness and robustness of the proposed framework empirically.

4.5 Visualization

In addition to the quantitative node classification, we also visualize node embeddings on Cora dataset to assess the embedding results qualitatively. We project the node embeddings into a 2-dimensional space using t-SNE [LJPvd and Hinton, 2008]. Here we illustrate the visualization results of GCN, H2GCN, CPGNN, GPR-GNN and our RAW-GNN in Fig. 3, where points with different color indicate different classes. As shown, the visualization results of GCN and CPGNN are less satisfactory in this case, since points with the same class are dispersed and some points with different classes are mixed. As shown, the visualization of GPR-GNN and H2GCN are better but still blurred along the border of different classes. The result of our RAW-GNN is the best, where the border between different classes is the most discernible. This result is consistent with classification result.

5 Conclusion

In this paper, we propose a random walk aggregation based graph neural network that can process homophily and heterophily graphs at the same time. The proposed framework extends the neighborhoods in traditional GCNs to k-hop path-based neighborhoods generated by two random walk sampling strategies (i.e., breadth-first search and depth-first search). Then, the proposed framework uses the sequential RNN-based aggregator to encode the ordered attribute information of neighbor nodes. Then, the path embeddings for each strategy are gathered to the target node with an attention mechanism to form strategy-specific embedding. At last, node embeddings from different strategy channels are concatenated to prevent information of different characteristics from mixing and enable the model to automatically tradeoff between homophily and heterophily according to different network characteristics. Experiments on seven real-world datasets demonstrate that the proposed approach outperforms existing methods under heterophily, and also performs competitively under homophily.

Acknowledgments

This research was partly supported by the Natural Science Foundation of China under grants 61876128, the Tianjin Municipal Science and Technology Project (Grant No. 19ZXZNGX00030), and Meituan Project.