Beyond Homophily: Structure-aware Path Aggregation Graph Neural Network

1 Introduction

Graph neural networks (GNNs) have attracted considerable research interest recently [Wu et al., 2020] due to their superior performance in various applications, such as bioinformatics [Borgwardt et al., 2005], finance [Yang et al., 2019b], chemistry [Xiong et al., 2019], social network analysis [Yang et al., 2019a], etc. The typical framework of GNNs can be formulated as message passing, which means node representations are learned by recursively aggregating the neighborhood.

Despite the promising results achieved by GNNs, most of them inevitably assume homophily, that is, the connected nodes tend to have similar attributes or belong to the same class ("birds of a feather flock together") [McPherson et al., 2001] as the example shown in Fig. 1 (a). However, numerous graphs exhibit the "opposites attract" phenomenon, which conflicts with the homophily assumption of GNNs. As the example in Fig. 1 (b) shown, the connected nodes tend to have dissimilar attributes or belong to different classes which leads to the formation of heterophily graphs [Newman, 2003]. For instance, in a heterosexual dating network, a candidate tends to be attracted by one of the opposite gender.

∗Corresponding author.

Although GNNs perform well in homophily graphs, they cannot achieve satisfactory performance in heterophily graphs. Fig. 1 (c) gives us a potential explanation: to aggregate the neighborhood of node 0, it is required to aggregate node 1's neighbors and node 2's neighbors first. Since the receptive field of node 1 is only limited to the direct neighbor 0, 3, 4, and the receptive field of node 2 is limited to node 0, 5, 6, the aggregated features of node 1 and 2 becomes ( 1 ) and ( 1 ), which are indistinguishable to node 0. However, the original node features of node 1 and 2 are different, indicating the flawed aggregation process of GNNs.

In this paper, we shed light onto the path level patterns in a graph, which can model both homophily and heterophily graphs. First, due to the flexibility of the paths, both direct adjacent and higher-order neighborhood information can be retained rather than only depending on the first-order neighboring nodes for aggregation. As depicted in Fig. 1(d), the path on the left contains node 1 and 3, which cannot be aggregated to node 0 simultaneously by GNN. Second, due to the order information brought by the paths, contextual semantic information can be captured to construct distinguishable embedding. Different from Fig. 1(c), our method gathers three types of paths: two of them go through node 1, forming ( ) by node 1 and 3, ( ) by node 1 and 4; the other one goes through node 2, forming ( ) by node 2 and 6, which are quite different for node 0. Although the paths of ( ) and ( ) contains two similar node features, the path embedding is still distinguishable because the order is different.

Based on aforementioned points, one natural implication is to learn each node's embedding by aggregating all involved paths instead of its neighborhoods. However, the question of how to obtain and encode the proper paths for extracting sufficient information is quite challenging.

Firstly, to obtain diverse path information, one straightforward way is to enumerate all paths for each node. However, the number of paths grows exponentially in the receptive field, especially when hub nodes are traversed. Thus, the first challenge is how to define an appropriate sampler that can avoid the over-expansion issue while retaining meaningful structural information.

Secondly, as mentioned above, the order of node appearance in a path is critical for capturing the heterophily in neighborhood. However, most of existing GNNs aggregators are not order sensitive and can not explicitly distinguish the information from different hops. Thus, how to design an orderpreservable aggregator is the second challenge.

Thirdly, nodes give preference to specific paths. For example, paths near the target node are preferred by homophily neighborhoods, whereas paths exploring deep receptive fields are preferred by heterophily ones. Nonetheless, one actually can hardly judge whether a graph is homophily or not with insufficient label information. Thus, the third challenge is how to capture the path preference of different nodes.

In this work, we introduce a structure-aware path aggregation graph neural network (abbreviated as PathNet) to address these challenges. To alleviate the over-expansion issue and to preserve structural patterns, we introduce a maximal entropy path sampler. Moreover, we theoretically and empirically prove that sampling an increasing amount of paths approaches the infinite paths scenario at an exponential rate. To encode paths while retaining the context of higherorder neighborhoods, we introduce a structure-aware path encoder which possesses two advantages: preserving the order through recurrent mechanism and capturing the contextual structure by leveraging distance to the target node. After the path encoding, we propose a path attention mechanism to model the preference of paths for nodes with different homophily level of neighborhoods.

The main contributions of our work are as follows:

1. We propose a novel path aggregation paradigm to capture the structure context information in both homophily and heterophily graphs.
2. We design an end-to-end model PathNet which leverages order and distance information of path to encode complex semantic information in graphs.
3. Extensive experimental results demonstrate that our model achieves superior performance by up to 10.08% in the node classification task on heterophily graphs and competitive results on homophily graphs.

2 RelatedWork

GNN methods have attracted considerable attention. GAT [Veliˇckovi´c et al., 2018] introduces the attention mechanism to parameterize the aggregation function. GIN [Xu et al., 2019] proposes a graph model with the same expressive power as WL graph isomorphism test. However, a majority of these works are based on the homophily assumption [Yang et al., 2018; Wu et al., 2017]. Thus, these approaches fail to achieve satisfactory performance on heterophily graphs.

Recently, several models have emerged to cope with the challenging and largely overlooked setting of heterophily. MixHop [Abu-El-Haija et al., 2019] utilizes higher-order graph convolutional architectures to overcome the limitation of direct aggregation. Likewise, H2GCN [Zhu et al., 2020] proposes to combine three components: ego- and neighbor embedding separation, higher-order neighborhoods and intermediate embedding. GPRGNN [Chien et al., 2021] leverages the diffusion matrix for long-distance propagation and proposes a pagerank-based model under heterophily settings. FAGCN [Bo et al., 2021] puts forward high-pass and lowpass filters to deal with both homophily and heterophily graphs. Although some of them propose to utilize the higherorder neighborhoods in aggregation process, they fail to capture the intrinsic semantic information since the order information are omitted. Furthermore, most of them treat the nodes in higher-order neighborhoods equally since they directly aggregate these nodes without distance information.

To the best of our knowledge, there are two existing works that claim to employ the path to model graphs. GeniePath [Liu et al., 2019] proposes an adaptive path layer that can guide the breadth and depth exploration of the receptive fields. Nonetheless, instead of utilizing the concrete paths, they name the receptive fields as receptive paths. SPAGAN [Yang et al., 2019c] conducts the operation of pathbased higher-order attention to explore the the topological information. However, each node influences the target node only through the shortest distance and omit the structure of higher-order neighborhoods. In general, feature propagation in these models fails to capture the connections between direct neighbors of target nodes and fails to encode different structure into distinguishable embedding, which results in the unsatisfactory performance.

3 PathNet

We begin with some necessary definitions.

Problem definition. Consider a graph G = (V, E), V is the node-set and E is the edge-set. The adjacency matrix and the node feature matrix of G is denoted by A ∈ {0, 1}|V|×|V| and X ∈ R|V|×F respectively, where F is the dimension of feature for each node. In this paper, we focus on the semisupervised node classification task. Specifically, given nodes in training set TV with known labels yv and feature vectors xv for v ∈ V, we aim to infer the unknown yu for all u ∈ (V - TV ).

Homophily and heterophily. The concept of homophily is derived from the tendency of a node to have the same class as its neighbor. The homophily level can be quantified by homophily edge ratio [Zhu et al., 2020], denoted as h(G) = |{(u,v):(u,v)∈E∧yu=yv}| |E| , which calculates the proportion of the edges connect two nodes with the same label. The lower h(G) implies more edges connecting nodes in different classes, that is, stronger heterophily.

The paths have great potential to represent the complex semantic information of graphs. Thus we propose PathNet (Fig. 2) to utilizes the path aggregation paradigm aiming to generalize GNNs for both homophily and heterophily graphs. The paths are firstly sampled under the guidance of maximal entropy random walk, which effectively explores the diversity of the graph structure. Then the paths are encoded by sending the node embedding sequences into the structure-aware recurrent cell Φ with distance-aware component, which captures structural context and extracts semantic information. To model the preference of each path embedding to the target node, a path attention module is employed for path aggregation. Finally the node prediction zv0 can be obtained after a non-linear transformation.

3.1 Maximal Entropy Path Sampler

To obtain the paths with a consideration of the efficiency, a sampling strategy like random walk is required. However, the conventional random walk (CRW) suffers from the identical treatment to different nodes and ignores the centrality of nodes of a graph. To address these problems, we propose to sample paths under the guidance of the maximal entropy random walk (MERW), shown in Fig. 2, left. The MERW seeks the paths in the orientation of entropy rate increase for each step and incorporates the eigenvector centrality which is widely applied to measure the importance of the nodes.

Consider a path sampled with length k from vi to vj, the probability of the path is P k ij = pii1 pi1i2 · · · pik-2ik-1 pik-1j, where pij is a element in transition matrix. As declared in [Cover, 1999], the maximal entropy rate η of random walk on a graph can be computed from the transition matrix P and the stationary distribution π, which can be described as follows:

Moreover, the maximal entropy rate of random walk is bounded by lnλ [Parry, 1964], where λ is the largest eigenvalue of A. In order to maximize the entropy rate of a walk, MERW constructs the transition probabilities as pij = Aij uj λui [Burda et al., 2009], where u = (u1, u2, · · · , un) is the normalized eigenvector. Note that the transition probabilities are proportional to the eigenvector centrality guaranteeing the MERW the ability to capture the structural context of nodes in a graph. It can be reformulated into the maximal entropy transition (MET) matrix, which is defined as

where Du = diag (u1, u2, · · · , un). In short, maximal entropy path sampler not only maximizes the entropy rate but also obtains the complex structual information of a graph.

3.2 Structure-aware Path Aggregator

To aggregate the path information, we propose a structureaware path aggregator. Specifically, we design a structureaware recurrent cell to encode the path embedding, which is capable to incorporate the order and distance information of each node in the path, so as to capture the semantic information. Furthermore, we model the path preference to distinguish the importance of different paths and realize selfadaptive path embedding aggregation.

Structure-aware recurrent cell. Although conventional GNNs are capable of gathering the information of higherorder neighborhoods, they inevitably lead to indistinguishable embedding for treating them in the same way and overlook the global structure context of neighborhoods in graphs. Fig. 3 (a, b) gives an intuitive case that a GNN within two layers generates indistinguishable embeddings of the target node T in two graphs. Because from the GNNs' point of view, only the direct neighbors are visible for each node, and all nodes in (a) and top three nodes in (b) share the identical neighbors. Hence, the two graphs would generate the identical node embedding of T after two-layer aggregation. On the contrary, if we embed the distance to the target information into the directed path sequence (shown in Fig. 3 c, d), the structural information (i.e., closed triangle vs. open paths) is well preserved and the path embedding is distinguishable. Thus, we claim that the distance of each node are the key information for capturing the structural context through path.

As shown in Fig. 1, the order information of the path reveals the distinguishable semantic in the neighborhood for each target node. Instead of aggregating each layer of nodes independently, we propose a recurrent cell to encode path sequence, so as to retain the order information of each node. We next introduce the details of our structure-aware recurrent cell. Note that we encode all the node feature X as node embedding I before engaging the structural information, which is described as

whereWin and bin are learnable parameters of the sigmoid function σ. In order to capture the feature-based diffusion structure, we construct structure-aware recurrent cell Φ as

where hj denotes the latent embedding of node v at the j-th step on the path, ⊙ is the Hadamard product and rj, fj, oj represent the input, forget and output gates, respectively. As a part of the forget gate, gj contributes to the long termmemory cell cj which filter the node feature along the paths. Considering the target node as the most basic part contributes the most, the input sequence is reversed from the collection order of the path (Fig. 2, Node embedding). Finally, we obtain the final path embedding hp for the p-th path.

Considering that the distance information contributes to the structural patterns, we employ a parameter sharing mechanism based on the node distance to the path embedding computation. Specifically, for each node in a path, we use the pre-calculated shortest distance d from the target node as side information, and the nodes with the same d share the same Ud during path encoding (Eq. 4), so as to incorporate the distance information into path embedding.

Modeling path preference. Naturally, neighborhoods with different homophily level have different path preferences. For homophily neighborhoods, the path nearby the target node may contribute more to the classification, while for heterophily ones, the paths to explore broader context of graph structure will be preferred. However, the homophily level of each neighborhood is hard to know. Thus, we model the path preference for each node, that is, take different paths into consideration and learn their importance to facilitate the selfadaptive embedding aggregation.

More specifically, for a particular path p, we obtain its embedding hp after Eq. 4, which is then concatenated with the target node embedding Iv as the input for computing the preference coefficient sv,p by a trainable weight a. We calculation the preference coefficient sv,p as

where δ = LeakyReLU, and a is the trainable weights. In the last step, we use the preference coefficient sv,p to weight the path and make the final prediction zv by Wout and bout:

The computational complexity of PathNet is discussed in the Appendix A.

4 Theoretical Analysis

4.1 Convergence of Path Sampler

As illustrated in Sec. 3.1, we propose to sample paths under the guidance of MERW that retains the structural information of the neighborhoods. Moreover, sampling various paths composed of different node features helps to capture more contextual patterns of the target node. In this section, we prove that sampling finite paths is indeed enough to cover the overall path patterns. Assigning the same tag l to nodes with similar features, we can define an attributed path as follows: For different paths {v1, v2, ..., vk} and {va, v2, ..., vk} of length k, if node features of v1 and va are similar, they both count as the same attributed path sequence of {l1, l2, ..., lk}. Hence, an attributed path can be generated only if nodes with dissimilar features are introduced. The more attributed paths we sample, the more semantic information we can capture from the neighborhoods.

Attributed path sampling deviation is defined as the difference between the proportion of attributed paths from finite sampling and the real attributed path proportion. The exponential convergence relationship between the finite sampling number of paths and the probability of attributed path sampling deviation being smaller than a certain constant is established below:

Theorem 1. Given a graph with adjacency matrix A, for any ϵ > 0, the probability of the attributed path sampling deviation being larger than ϵ decreases exponentially as the number of attributed paths M increases.

The proof is in Appendix B. The theory indicates that although PathNet samples a finite number of paths, the ability to capture the semantic information grows tremendously when the number of sampled paths increases, revealing the feasibility of gathering enough representative information of neighbors by sampling an achievable number of paths.

4.2 Expressive Power of PathNet

PathNet provides a more intact receptive field for target node and generates more distinguishable embedding. Neither stochastic GNNs like GraphSAGE nor deterministic GNNs like GCN can capture the connections between direct neighbors of a node. Because they use the permutation invariant operation such as mean or max pooling for neighboring nodes ignoring the connections between them. Even for the attentive GNNs like GAT, the attention coefficient of neighbors still cannot indicate whether they are connected or not. Instead, our method captures rich structural information by sampling paths in entire neighborhood that contain the edges omitted by GNNs, and also our aggregation method maintains to be permutation invariant because both directions of the edges between direct neighboring nodes can be sampled. Furthermore, as shown in Fig. 3, the distance sensitive mechanism generates the distinguishable embedding for different structure which differs from the conventional aggregation.

5 Experiments

In this section, we aim to practically validate our proposed model by evaluating its performance on semi-supervised node classification task. 1 To be specific, we want to answer the following questions:

• Q1 Does PathNet achieve satisfactory performance on both homophily and heterophily graphs?
• Q2 How does each component contribute to the performance of our model?
• Q3 Is the maximal entropy path sampler able to capture enough structural information to achieve a satisfying performance?
• Q4 Can PathNet actually improve the expressive power by capturing the structural context of neighborhoods?

5.1 Experiment Setup

To answer Q1, we evaluate our model on the semi-supervised node classification with seven real world graph datasets: (1) three widely adopted citation network benchmark: Cora, Pubmed and Citeseer[Kipf and Welling, 2017] with strong homophily; (2) four representative heterophily datasets that span across various domains: Cornell[Rozemberczki et al., 2021], BGP[Luckie et al., 2013], NBA[Dai and Wang, 2021], Electronics[McAuley et al., 2015] collected from web pages, BGP network, NBA players and Amazon product catalog separately. The experiment setting and hyperparameter can be found in Appendix C.

Baselines. We compare PathNet with the following states of the art baselines: (1) Traditional methods: multi-layer perceptron (MLP, graph-agnostic), several classical GNN models GraphSAGE [Hamilton et al., 2017], GAT [Veliˇckovi´c et al., 2018] and GIN [Xu et al., 2019] under the assumption of homophily are used for fundamental evaluation. (2) Models for heterophily graphs: MixHop [Abu-El-Haija et al., 2019], H2GCN [Zhu et al., 2020], GPRGNN [Chien et al., 2021], FAGCN [Bo et al., 2021]. (3) Models using path or node position: GeniePath [Liu et al., 2019] adaptively explores the receptive field which is termed as receptive paths. SPAGAN [Yang et al., 2019c] conducts path-based higher-order attention. P-GNN [You et al., 2019] emphasizes the importance of encoding the position of each node.

5.2 Comparison with State-of-the-art Models

The results are reported in Tab. 1 (upper half). For H2GCN, we use the best result between the H2GCN-1 and H2GCN-2.

1 Codes are available at https://github.com/zjunet/PathNet

"OOM" means out of memory.

Our approach PathNet outperforms all the baselines on all four heterophily graphs, demonstrating the necessity of introducing path aggregation paradigm. Specifically, our model achieves an improvement of 9.96%, 9.61% and 15.3% on average against the traditional methods, the models for heterophily graphs and the models using path or node position respectively. (The calculation of average improvement is to average the result of different methods within the same dataset, and then average their results cross all datasets.) The performance proves the effectiveness of our model to capture the complex structure information on heterophily graphs.

For homophily graphs, our model achieves best performance on Pubmed and Citeseer and presents highly competitive results on Cora (1.14% decline compared to the best). Specifically, our model outperforms the three types of models mentioned in baselines by 3.21%, 0.92% and 4.82% on average. Compared with the performance on heterophily datasets, the improvement of our model is not that notable on homophily graphs, which might result from the similarity of the node features in the nearest neighborhood caused by the high homophily level. In summary, our method achieves the best performance on heterophily graphs and competitive performance on homophily graphs.

5.3 Ablation Study

To answer Q2, we conduct an ablation study by changing parts of the entire framework. The results are shown in Tab. 1 (lower half). When we replace the MERW with CRW while keeping the number and length of paths consistent (RWPathNet), the performance drops by 1.16% on average across all datasets. It shows that MERW indeed preserves the complex structure context of neighborhoods. Furthermore, since the structure-aware recurrent mechanism preserves the semantic information contained in the maximal entropy paths, when we use MLP as a substitute for the recurrent cell ϕ (PathNet-MLP), the performance is reduced by an average of 2.43%, revealing that the recurrent mechanism which retains the node order information is helpful to capture context in neighborhoods. Moreover, the mean accuracy drops by 1.85% and 1.73% on average when replacing the parameter sharing recurrent cell with conventional GRU [Cho et al., 2014] and LSTM [Hochreiter and Schmidhuber, 1997] (PathNet-LSTM/PathNet-GRU). We can tell from the performance that the LSTM version and the GRU version are slightly different on different datasets though they are consistently lower than the proposed parameter sharing recurrent cell ϕ, which indicates that parameter sharing mechanism for path distance-aware contributes to perceive the contextual structure of neighbors. In addition, path preference modeling contributes to our model by an average of 1.65% and 2.84% compared with replacing the path attention into mean/sum pooling respectively (PathNet-Mean/PathNet-Sum), indicating the effectiveness of choosing different paths in different neighborhoods. In summary, even some components are replaced, our model that explicitly exploits paths still gains satisfactory results.

5.4 Model Variants

To answer Q3, we conduct experiments by varying the number and length of maximal entropy paths. Take NBA dataset with path length of 3 as an example (Fig. 4(a)), we change the number of sampled paths for every epochs at increasing intervals for the performance becomes stable when the number is around 40. Before performance convergences, the performance increases with the number of paths increasing, as we analysis in Sec. 4.1. Since we train our model for 1000 epochs, the total number of paths sampled for each node during the entire training process is 1000 times the number of paths per epoch. Thus, even when the number of path is 1 per epoch, the performance is just slightly lower than the average of baselines.

Moreover, when we change the path length between 2 to 5 (Fig. 4(b)), the changes of performance varies with datasets. Generally, the performance of these datasets forms a peek shape. The performance of Cora, Citeseer and NBA peeks at the length of 3 and the other datasets peeks at the length of 4. In summery, the experiments reflect the stability and capability of PathNet on mining the structure information.

5.5 Synthetic Experiment

To answer Q4, we design a synthetic experiment inspired by [Chen et al., 2021]. [Chen et al., 2020] proves that the capability to count substructures indicates the strength of the expressive power. Thus, we aim to test the expressive power of our model by evaluating the ability of finding out the attributed path (mentioned in Sec. 3.1) with the largest number since attributed paths can be seen as a kind of substructure. The datasets are synthesized as follows: we use Cora and Citeseer as graph structure and change the node attributes into a 2-dimensional one-hot vector The vector is assigned as blue if the original node index is even, and as red if the original node index is odd. Since it has two kinds of node attributes, there are eight different attributed paths of length 3. We number different kinds of attributed paths as indexes and there might be a certain amount of each attributed path for one node. The node labels are defined as the indexes of the largest number of attributed path. We use 10 randomly generated splits with 60%, 20%,and 20% for training, validation and testing. The baselines include GIN which achieves the expressive power of the WL test [Xu et al., 2019], GAT which utilizes the attention mechanism and GPRGNN designed for heterophily graphs.

As shown in Tab. 2, our model significantly outperforms other models on both datasets, which proves that PathNet indeed boosts the expressive power as analysised in Sec. 4.2.

6 Conclusion

We propose a novel path aggregation paradigm and design PathNet to capture the semantic and structural information in both homophily and heterophily graphs. Firstly, we sample a reasonable number of paths. Then, we proposes a structureaware recurrent cell with the parameter sharing mechanism to aggregate each path. Furthermore, our path attention module can distinguish the preference of paths. As an end-toend model, we achieve the SOTA performance on both heterophily and homophily graphs.

A Computational Complexity

Here we discuss the computational complexity of PathNet. In general, our method is rather efficient. Concretely, the preprocessing includes the path sampling and shortest distance calculation, with the precise time complexity of O(dk n), where n denotes number of nodes, d is the average degree of the graph (d = 3.89 in Cora) and k is the length of sampled paths (k = 4 in our experiments). Moreover, the overall time complexity of PathNet is O(dk n +mtnhh′ ), where m denotes the number of sampled path (m = 40 in our experiments), t is the iteration (epoch) value, h and h′ represent the dimensions of input and output.

B Proof of Theorem 1

Proof. A tag-limited transition matrix A(l) is derived by setting the same elements as the original adjacency matrix A if the end node can be tagged as l, while other elements are tagged as zero:

During the path sampling process, we sample the neighbors with the probability matrix of maximal entropy calculated as the Eq. 2. Thus, the probability matrix P{l1,l2,...,lk} of sampling a attributed path is as follows:

The element in the i-th row and j-th column of P{l1,l2,...,lk} is the probability of walking from i to j through an attributed path. Moreover, PS,{l1,l2,...,lk}, the probability of sampling an attributed path starting from node S, is derived as follows:

Here, NS,{l1,l2,...,lk} denotes the number of attributed paths in m times of sampling from graph. Since we use the same sampling strategy for every epoch, the probability of attributed paths being sampled is PS,{l1,l2,...,lk}, while the probability of not being sampled is 1 - PS,{l1,l2,...,lk}. Whether an attributed path would be sampled in two samples is independent and identically distributed. Therefore, NS,{l1,l2,...,lk} follows a binomial distribution:

According to Hoeffding's inequality[Hoeffding, 1963], we have

Thus, as the number of sampled paths m increases, the probability on the left of inequality decreases exponentially.

C Experiment Settings and Hyperparameters

As important parts of preprocess, the path sampling and shortest distance calculation between nodes are finished before model training. We use 10 random splits with 48%, 32%, and 20% for training, validation and testing. For Cora, Pubmed, Citeseer and Cornell, we use the the same splits provided by [Zhu et al., 2020]. For NBA, BGP, and Electronics, we randomly generate the 10 splits. We use 1000 epochs for each split. The mean accuracy and standard deviation are calculated from the 10 splits. For our method and baselines, we choose the hyper-parameter settings which can make them perform best. For simplicity, we set the number of paths as 40 for both heterophily and homophily graphs. Moreover, we set the length of paths as 3 for Cora, Citeseer and NBA while 4 for other datasets.

Acknowledgments

This work was partially supported by Zhejiang NSF (LR22F020005), the National Key Research and Development Project of China (2018AAA0101900), and the Fundamental Research Funds for the Central Universities.