HP-GMN: Graph Memory Networks for Heterophilous Graphs

We use $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ to denote an attributed graph, where $\mathcal{V}=\{v_{1},...,v_{N}\}$ is the set of $N$ nodes, and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges. $\mathbf{X}=\{\mathbf{x}_{1},...,\mathbf{x}_{N}\}\in\mathbb{R}^{|\mathcal{V}|\times F}$ is the node feature matrix, where $\mathbf{x}_{i}$ is the node features of node $v_{i}$ and $F$ is the feature dimension. $\mathbf{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix, where $\mathbf{A}_{ij}$ = 1 if nodes pair $\{i,j\}\in\mathcal{E}$; otherwise $\mathbf{A}_{ij}$ = 0.

The graph neural networks aim to learn effective node representations $\mathbf{H}\in\mathbb{R}^{|\mathcal{V}|\times F^{\prime}}$ used in downstream tasks, where $F^{\prime}$ is the dimension of representations. Typically, GNNs use message passing [10] to learn representations. Each node aggregates its neighbors’ representations and then combines them with the ego-representation. Hence, there are two essential steps in MPNNs:

where $\mathbf{h}_{v}^{k}$ is the representation of node $v$ at layer $k$ and $\mathcal{N}(v)$ is the neighbors of node $v$. AGGREGATE and COMBINE are two functions specified by GNNs.

Generally, the homophily degree of a graph can be measured by node homophily ratio [11].

Definition1 (Node homophily ratio) [11] It is the average ratio of same-class neighbor nodes to the total neighbor nodes in a graph.

where $y$ is the node label. Graphs with higher homophily are close to 1, and graphs with higher heterophily are close to 0.

There are two main reasons leading to the incompatibility between MPNNs and heterophily. Firstly, AGGREGATE is usually implemented by a mean or weighted mean function and COMBINE is to mix a node’s ego- and neighbor- representations. Because neighbors are from different classes and have different distributions in the heterophily assumption, such process can mix representations from different distributions and make the result of aggregation less discriminative. This mixture gives us poor node representations, which further degrades the quality of global patterns learned from each node. In this case, even MLP can have better performance than GCN because the structure information is harmful according to some empirical results [6, 12]. Secondly, in MPNNs, a node only gathers information from the local neighbors and fails to get more global information. As a result, MPNNs cannot learn global patterns from nodes’ local contexts. Therefore, MPNNs are not good at addressing the heterophily problem.

In a graph, each node has a $k$-hop subgraph centered on itself. The characteristics of the subgraph can provide much information for the node’s local context; therefore, local statistics can be designed to capture this local information for downstream classification tasks. Furthermore, for all the nodes of each class, we can learn the global patterns of the class by extracting representative information of the nodes’ local representations. Then each node can learn global information from similar global patterns. We need to measure the similarity here because we do not need information from different distributions. Based on the high-level ideas, we develop HP-GMN to learn from both local and global information. To measure the performance of our framework, we mainly have semi-supervised node classification as the downstream task.

Problem1 Given an attributed graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ and a training set $\mathcal{V_{L}}\ \subseteq\mathcal{V}$, with known class labels $\mathcal{Y}_{L}=\{y_{v},\forall v\subseteq\mathcal{V_{L}}\}$, the heterophily ratio of the graph $\mathcal{G}$ is low, we aim to learn a GNN that can infer the unknown class labels $\hat{\mathcal{Y}}_{U}=\{\hat{y}_{u},\forall u\subseteq\mathcal{V_{U}}=(\mathcal{V}-\mathcal{V_{L}})\}$.

It has been observed that the local context of nodes in heterophilous graphs can differ a lot for nodes are in different classes, while two nodes in the same class often exhibit similar node features and local subgraphs [13]. Thus, we propose the local statistics including node attributes, neighborhood distributions, and local topology.

The global patterns are some representative local graph patterns that appear most frequently for nodes of each class. We want to learn them so that nodes can aggregate from similar patterns instead of dissimilar neighbors. However, directly learning representative subgraphs is difficult as we need to consider both graph structure and node attributes. Thus, we learn representative global vector representations using a memory module instead. Specifically, the memory is a matrix $\mathbf{M}\in\mathbb{R}^{K\times hidden}=[\mathbf{m}_{1},\mathbf{m}_{2},\cdots,\mathbf{m}_{K}]^{\mathrm{T}}$, where $K$ is the number of memory units and $hidden$ is the feature dimension of a memory unit. Each row $\mathbf{m_{i}}$ is a memory unit used to learn a global pattern.

To get the global representations, we use the attention scores to measure the similarity between each node’s local representation and every global pattern. Then a node gathers information from each pattern according to the attention scores. Intuitively, the node get global information by the combinations of the patterns that can describe the distribution it belongs to. We follow [16] to query the memory and get attention matrix:

where $\mathbf{Q}=[\mathbf{q}_{1},\mathbf{q}_{2},\cdots,\mathbf{q}_{n}]^{\mathrm{T}}$ is the query matrix. $s_{ij}$ indicates the importance of the $i$-th memory to $j$-th node. Then we calculate the value matrix $\mathbf{V}$, which is global representation by weighted average of the memories as:

Eventually, we concatenate the local and global representation of a node followed by an MLP transformation to get the final representation $\mathbf{h}_{v}$. Then we can predict the label distribution of $\hat{\mathbf{y}}_{v}$.

where $\hat{\mathbf{y}}_{i}$ is the predicted label probabilities of node $v_{i}$.

For the training, we minimize the cross-entropy loss as

where $\mathcal{V}_{train}$ is the set of labeled nodes, $\mathbf{y}_{v}$ is the one-hot-encoding of $v$’s label and $l(\cdot,\cdot)$ is the cross entropy loss.

In order to capture global information effectively, we desire two properties of the memory units, i.e., representativeness and diversity. Representativeness is desired because the memory is expected to capture the most representative patterns of the distributions of a class. Diversity is also required to encourage richer information and avoid much-duplicated information recorded in memory units. However, during the training process, memory units are updated by gradient descent. The learned memory units are likely to lack the properties we desire. Therefore, we propose Kpattern and Entropy regularizations to encourage the properties.

Kpattern Regularization. To make the memory representative, we want each query $\mathbf{q}_{v}$ to be at least close to one of the memory units so that each query can retrieve important global information. In other words, the memory should be useful for each node. Thus, we calculate the distances between each node’s local representation and every memory unit. Then we choose the memory unit with the smallest distance. We sum up all the smallest distances over all nodes, and we aim to learn memory that can minimize the total loss as:

where $dist$ can be any function measuring distance between two vectors. We adopt the Euclidean distance in this paper. Intuitively, we prefer representative $\mathbf{M}$ that makes the total distance between the memory and the query minimized, which means the $K$ patterns become representative for the query.

Entropy Regularization. To make the memory diverse, we want each memory to have similar chances of being selected globally. In other words, the averaged importance score over all the nodes for each memory should be similar to each other. Since $s_{ij}$ indicates the importance of $i$-th memory to $j$-th node, the overall importance score of $\mathbf{m}_{i}$ can be written as $\mathbf{s}_{i}^{\prime}=\sum_{j=1}^{N}s_{ij}$. Denote the memory importance vector as $\mathbf{s}^{\prime}\in\mathbb{R}^{K}$ with $\mathbf{s}_{i}^{\prime}$ as the $i$-th element of $\mathbf{s}^{\prime}$ indicating the total importance of $i$-th memory unit.

We need the elements in $\mathbf{s}^{\prime}$ to be equal or similar to others, i.e., $\mathbf{s}^{\prime}$ is uniformly distributed, which means all the memory units are equally important and are used with the same frequency. Otherwise, if some units have low overall importance scores than others, there are two possible reasons. (1) Some memory units are unimportant because they contain duplicated information from others. As a result, the information contained in these units can also be expressed by others. (2) Some memory units are useless, i.e., not representative. They do not contain any useful information demanded by downstream tasks, so they are rarely used. Therefore, we can achieve uniformly distributed $\mathbf{s}^{\prime}$ by maximizing the entropy of it, namely, i.e., minimizing the negative entropy as:

With $\mathbf{h}_{i}$ in Eq.(11) capturing both local and global information, $\mathcal{L}_{kpattern}$ in Eq.(14) to make the memory representative and $\mathcal{L}_{entropy}$ in Eq.(15) to make the memory diverse, the final objective function of HP-GMN is:

where $\alpha$ and $\beta$ are scalars to control the contributions of $\mathcal{L}_{kpattern}$ and $\mathcal{L}_{entropy}$. $\theta$ is the set of parameters of MLPs.

To answer RQ1, we conduct node classification on heterophilous graphs and compare HP-GMN with the baselines. The average accuracy with standard deviation are shown as Table II and we have the following observations:

• •

  GCN is a little better than MLP or even no better than MLP on heterophilous datasets because GCN fails to exploit the structure information of heterophilous graphs. Our HP-GMN considers heterophily properties, and the local statistics can capture heterophilous structures well; thus, it achieves much better performance than MLP and GCN.

• •

  While methods employing higher-order neighborhood information improve the performance, the extent is limited because they aggregate all the higher-order neighbors regardless the homophily or heterophily. HP-GMN only aggregates from similar global patterns, which leads to further improvements in accuracy.

• •

  Methods designed for heterophily have better performance than general graph methods even without global patterns. However, HP-GMN takes advantage of global patterns and outperforms all other baselines significantly.

To answer RQ2, we aim to demonstrate that HP-GMN can also work on homophilous datasets. However, the local statistics in III-A are designed for heterophily and do not fit the homophily problem. In order to show the effectiveness on the homophilous datasets, we use the representation learned by GCN or APPNP as the local statistic on graphs with homophily, denoted as $\text{HP-GMN}_{\text{GCN}}$ and $\text{HP-GMN}_{\text{APPNP}}$. We conduct experiments on three homophilous citation networks. The average accuracy with the standard deviation is shown in Table III. From Table III, we observe that the memory not only promotes the prediction on heterophily but also can facilitate learning on homophily. That is because homophilous graphs also contain some global information that is not captured by other methods.

To answer RQ3, we compare the performance of HP-GMN, HP-GMN without Kpattern regularization (HP-GMN/K), HP-GMN without Entropy regularization (HP-GMN/E), and HP-GMN without regularizations (HP-GMN/KE). We report the performance on Texas and Squirrel in Fig. 3. Then we show the contribution of local statistics. We remove each local statistic to get different designs of the query. We observe the best performance when we use all four local statistics. It reveals that all of them can collect different aspects of local information in the graph, and everyone is essential for describing the local subgraph. Results are shown in Table IV, where “W/O Node Attributes” denotes that “Node Attributes” are removed from local statistics.