Heterophily-Aware Graph Attention Network

Graph Attention Network (GAT) [2] pioneers to compute the hidden representation of each node by attending over its neighbors, based on a self-attention strategy. Specifically, it generates attention coefficients by performing an inner product between a learnable vector and the concatenated representations of two connected nodes. Subsequently, several GAT variants are proposed by different calculation schemes of the attention coefficients, such as cosine similarity [15] and element-wise product [16, 17]. Besides, some methods are proposed to improve GAT from other perspectives. CS-GNN [18] improves GAT by predicting the attention coefficients based on separate scoring representations, instead of using direct node representations. SuperGAT [17] proposes a self-supervised strategy to learn the attention coefficients with respect to the edge information. GATv2 [19] argues that the attention scores learned by GAT [2] are irrelevant to the ego-representation. Then, it presents an improved variant by modifying the order of operations. All of these attention-based GNNs function decently under the homophilic assumption, i.e., they attempt to measure similarities or distances by employing distinct pair-wise attention functions, which makes them unsuitable to process the networks with heterophily.

Recently, several methods have been proposed to tackle the heterophily problem, which can be divided into two lines.

The first line of approaches intends to model the diverse local patterns via designing adaptive message aggregation schemes. Geom-GCN [21] builds a structural neighborhood by leveraging network embeddings. The neighborhood is then partitioned into several geometric blocks and the neighbors within each block are aggregated separately. FAGCN [23] adopts a self-gating attention mechanism to learn the attention coefficients for both the low-frequency and high-frequency signals. Besides, ACM-GNN [29] proposes an Adaptive Channel Mixing framework to adaptively exploit low-frequency, high-frequency, and identity channels. GBK-GNN [30] employs a bi-kernel feature transformation and a selection gate to simultaneously model the similarity and dissimilarity (i.e., the positive and negative correlations) between node features. By taking node attributes as weak labels, DMP [22] considers the attribute heterophily for diverse message passing and specifies every attribute propagation weight on each edge. WRGNN [31] transforms a heterophilic input graph into a multi-relational graph, in which the proximity and structural information are represented as distinct types of edges. BM-GCN [24] leverages a two-staged block-guided classified aggregation mechanism, to directly model the explicit heterophily and assign edge weights according to the block similarities. MWGNN [28] utilizes well-designed handcrafted features, i.e., local degree profile, sorted node feature, and shortest path distance, to predict the underlying local distribution, and assigns the edge weights by a topology-attribute decoupling mechanism. Although it also considers the local distribution, handcrafted features may not be appropriate for handling all the graphs. Different from the existing literature, our proposed HA-GAT estimates the underlying heterophilic type of each edge to avoid utilizing imprecise label information. It leverages a heterophily-aware attention scheme to adaptively learn the importance of each heterophilic type, presenting a novel paradigm for addressing heterophily.

The other line of approaches focuses on expanding the local neighborhood. H2GCN [20] explicitly aggregates information from high-order neighborhoods to find more similar neighbors, which has proved to be beneficial in heterophily settings. This design is also employed in [32, 33]. GRP-GNN [34] proposes a generalized PageRank architecture to model the importance of different orders of neighborhoods adaptively. Besides, some works utilize different ranking strategies to find potential neighbors. Non-local GNN [35] designs an attention-guided sorting strategy to find distant but informative nodes and put them together. GPNN [36] leverages a pointer network to select the most relevant nodes from a large amount of multi-hop neighborhoods. UGCN [37] introduces a discriminative aggregation to fuse 1-hop, 2-hop, and $k$NN neighbors simultaneously. GloGNN [38] generates node embeddings by aggregating information from global nodes within the graph. Our HA-GAT follows the first line and thus is not similar to these methods.

An attributed graph is denoted as $\mathcal{G}=\left\{\mathcal{V},\mathcal{E},\mathcal{X}\right\}$ with the vertex set $\mathcal{V}=\{v_{i}\}_{i=1}^{N}$ and edge set $|\mathcal{E}|=E$. Each node $v_{i}$ contains a feature $x_{i}\in\mathbb{R}^{d}$. $X\in\mathbb{R}^{N\times d}$ is the collection of all the features in all the nodes. $A=[a_{ij}]\in\left\{0,1\right\}^{N\times N}$ is the adjacency matrix, where $a_{ij}=1$ if nodes $v_{i}$ and $v_{j}$ are connected, or $a_{ij}=0$ otherwise. $d_{i}=\sum_{j}a_{ij}$ stands for the degree of node $v_{i}$ and $D=diag(d_{1},d_{2},\dots,d_{n})$ represents the degree matrix corresponding to the adjacency matrix $A$. For each node $v_{i}$, $\mathcal{N}_{i}=\left\{v_{j}|a_{ij}=1\right\}$ represents the set of its neighbors and $\tilde{\mathcal{N}}_{i}=\mathcal{N}_{i}\cup\left\{v_{i}\right\}$ denotes the set containing both the node $v_{i}$ and its neighbors.

To clearly measure the homophily/heterophily of a graph, we follow [21] to define the homophily ratio $\mathcal{H}(\mathcal{G})$ as

where $\mathcal{H}(\mathcal{G})\in\left[0,1\right]$. A high homophily ratio indicates that the graph is with strong homophily, while a graph with strong heterophily possesses a small homophily ratio.

Local distribution describes a distribution measured by certain characteristics in each local neighborhood. It can be measured by the node label [26] as well as other local characteristics [28]. In general, the local distribution of each node $v_{i}$ can be derived from its local neighborhood, via

where $s_{i}\in\mathbb{R}^{t}$ represents the local distribution of node $v_{i}$ and $\mathcal{N}_{i}^{(p)}$ stands for the collection of nodes within a $p$-hop local neighborhood. Note that $t>0$ is a preset integer constant which represents the number of underlying categories. Each element in $s_{i}$ ($s_{ik}\geq 0$) represents the probability of assigning category $k$ to node $v_{i}$, and $\sum_{k}s_{ik}=1$. Note that $\Theta(\cdot)$ is expected to estimate the appropriate local distribution, according to certain underlying measurements, and thus facilitates the node classification task.

In this paper, instead of generating local distribution by directly estimating the node labels or from well-designed handcrafted features [28], we excavate local information from the local smoothed features. This design is motivated by two aspects. Firstly, based on the analysis [26] under certain ideal assumptions, the local smoothed features tend to contribute similarly in representing heterophily, compared to the local distributions. Under such circumstances, GCN can perform decently by obtaining local smoothed features, because the local distributions according to the node labels are discriminative. Secondly, in practical situations, [28] empirically verifies that the local distributions, which are generated from the local node features and the topological information, can facilitate the weight assignment scheme. However, instead of generating the local distributions based on the handcrafted characteristics from the neighborhoods, e.g., local degree profile, the local smoothed features can be utilized to adaptively select appropriate characteristics as underlying measurements.

Therefore, a 2-layered GCN is employed as an explorer network to excavate local distributions from the local smoothed features as the underlying heterophily. Then, Eq. 8 can be rewritten as

where $S=\{s_{1};s_{2};...;s_{N}\}\in\mathbb{R}^{N\times t}$ represents the local distributions. As stated above, we assume that the local distribution reflects the corresponding node categories, i.e., it can be transformed to the category distribution by a certain linear transformation $W_{t}$. Thus, we can utilize $S$ to approximately model the underlying heterophily by combining the linear projections $W^{(1)}_{e}$ and $W_{t}$. Then, $s_{i}$ represents the category distribution among the underlying categories of node $v_{i}$. Note that $\sigma(\cdot)$ is the ReLU function, $\tilde{A}=\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$, $\hat{A}=A+I$, and $\hat{D}$ is the degree matrix of $\hat{A}$.

Then, the underlying heterophily preference of each edge is re-computed via

where $\mathbf{m_{ij}}\in\mathbb{R}^{t\times t}$ represents the probability distribution of the $(t\times t)$ heterophilic types for edge $e_{ij}$. Each element $m_{ijk_{i}k_{j}}$ in $\mathbf{m_{ij}}$, where $m_{ijk_{i}k_{j}}=s_{ik_{i}}\cdot s_{jk_{j}}$, represents the heterophily preference that edge $e_{ij}$ connects two nodes with their categories being $k_{i}$ and $k_{j}$, respectively. Since $\sum_{k}^{t}s_{ik}=1$ and $\sum_{k}^{t}s_{jk}=1$, $\mathbf{m_{ij}}$ is also a probability matrix, i.e., $\sum_{k_{1}}^{t}\sum_{k_{2}}^{t}m_{ijk_{1}k_{2}}=1$. Therefore, $\mathbf{m_{ij}}$ indicates the heterophily preference of each edge $e_{ij}$, which is utilized in the heterophily-aware attention scheme to generate the attention coefficients and constructs our HA-GAT. Note that we denote a special variant of our HA-GAT with a prior edge heterophily according to the node labels as HA-GAT(L), which is introduced in Sec. 4.

Here, we compare the proposed HA-GAT with typical attention-based GNNs, and analyze its connections to existing GNNs by proposing several HA-GAT variants.

Our HA-GAT has two backbone networks: 1) 2-layered GCN as an explorer network; 2) the classification network.

Overall, for an L-layered HA-GAT, we utilize a 2-layered GCN as an explorer network and an L-layered classification network. The final time complexity and memory complexity are the addition of the corresponding complexities of these (2+L) layers. Considering that $t$ is a relatively small number, e.g., $t=3$ in our settings, the time and memory complexities of L-layered HA-GAT are approximated to those of an (L+2)-layered GCN.

The proposed heterophily-aware attention scheme attempts to find an effective LAP to help nodes to extract appropriate information from both similar and dissimilar neighbors. As can be observed in Tab. 2, by exploiting the prior edge heterophily to identify edges according to node labels, HA-GAT(L) achieves superior results on all the datasets, especially on the heterophilic graphs. It indicates that even on the heterophilic graphs, where the nodes usually connect with other dissimilar nodes, there still exists an effective LAP which can enable the nodes to acquire appropriate information from distinct neighbors. Note that since Texas and Cornell are quite small, their performances are vulnerable to the topological bias. Fig. 2 visualizes the learned LAPs of HA-GAT(L) on Chameleon, where the specific weight assignments from each type of nodes to all their neighbors can be observed. For example, in the first layer, the edges coming into the nodes of C5 have large weights, which suggests that the nodes of C5 may possess salient characteristics after the aggregation. Then, the classification tasks may benefit accordingly. (Note that the nodes of C5 represent the web pages with the most significant averaged traffic.)

When the prior edge heterophily is not given, our HA-GAT excavates effective local distributions as a substitute for the underlying heterophily. Here, we demonstrate the effectiveness of the proposed HA-GAT for both the supervised and semi-supervised node classification on real-world graphs with different homophily ratios.

Our HA-GAT excavates effective local distributions from the local features and topology information, to represent the underlying heterophily. The local distribution exploration is thoroughly examined and analyzed in this subsection.

To provide an intuitive understanding, this subsection visualizes the distributions of the learned weights in our HA-GAT, two attention-based GNNs (i.e., GAT and GATv2) and a structure-based GNN (i.e., GCN). All of these GNNs are constructed with two layers. Fig. 5 shows their layer-wise distributions of the learned weights. As can be observed, the distributions of the learned weights in GCN, GAT, and GATv2 are similar. Besides, there are little variations of their distributions across different layers. On the contrary, the distributions of our HA-GAT are diverse for different layers and datasets. Due to the employed Neighbor Norm, our HA-GAT can assign diverse weights, even more than one, which makes our attention scheme more flexible and can handle graphs with complex local distribution.

For further comparisons, we replace our normalization approach with the Softmax Norm (as shown in Eq. 18), which is employed in GAT and GATv2. Fig. 6 shows the difference between the weights learned by different models with the Mean Norm (as shown in Eq. 16). GCN, which employs GCN Norm (as shown in Eq. 17) to normalize edge weight, is utilized as a baseline. As can be observed, the weights learned by GAT and GATv2 are very close to the averaged normalization, which indicates that they assign most edges equal importance. On the contrary, our heterophily-aware attention scheme in our HA-GAT(S) can generate diverse weights to differentiate various types of edges, which demonstrates the superiority of our attention scheme.

Here, we verify the effectiveness of our Neighbor Norm and the gradient scaling factor.

Here, we explore the impact of two critical hyperparameters: the number of hidden neurons and the number of layers within our HA-GAT.

As depicted in Fig. 9(a), our HA-GAT exhibits increased performance up to a certain number of hidden neurons. Then, its performance stabilizes at high accuracies beyond a certain threshold. This suggests a critical minimum number of hidden neurons is required for our HA-GAT to effectively learn node representations and accomplish downstream tasks. According to this observation, we adopt HA-GAT with 64 hidden neurons in our experiments.

Fig. 9(b) displays the performance of our HA-GAT, configured with 64 hidden neurons across varying numbers of layers. It is evident that the performance of our HA-GAT significantly benefits from increasing the number of layers from 1 to 2. However, performance diminishes when the number of layers exceeds 2, leading to the over-smoothing issue [43]. This trend is consistent with findings in the broader GNN literature [1, 2]. According to the above analysis, a 2-layered HA-GAT is employed in all our settings.

Tab. 4 presents the running times (s) of experiments in Tab. 2. All the experiments are conducted on our Nvidia GeForce RTX 2080Ti GPU. In our settings, all the following methods except BM-GCN are trained for a maximum of 1000 epochs with an early stopping condition at 200 epochs. For BM-GCN, we follow their 2-staged learning strategy, which contains 400 and 1600 epochs for its two training stages. As can be observed, the reported running times of our HA-GAT match the complexity analysis.