Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?
异质性是否对图神经网络进行节点分类构成真正的噩梦？

The (combinatorial) graph Laplacian is defined as $L=D-A$, which is Symmetric Positive Semi-Definite (SPSD) [8]. Its eigendecomposition gives $L=U\Lambda U^{T}$, where the columns $\boldsymbol{u}_{i}$ of $U\in{\mathbb{R}}^{N\times N}$ are orthonormal eigenvectors, namely the graph Fourier basis, $\Lambda=\mathrm{diag}(\lambda_{1},\ldots,\lambda_{N})$ with $\lambda_{1}\leq\cdots\leq\lambda_{N}$, and these eigenvalues are also called frequencies. The graph Fourier transform of the graph signal ${\boldsymbol{x}}$ is defined as $\bm{x}_{\mathcal{F}}=U^{-1}\bm{x}=U^{T}\bm{x}=[\boldsymbol{u}_{1}^{T}{\boldsymbol{x}},\ldots,\boldsymbol{u}_{N}^{T}{\boldsymbol{x}}]^{T}$, where $\bm{u}_{i}^{T}\bm{x}$ is the component of $\bm{x}$ in the direction of $\bm{u_{i}}$.
(组合)图拉普拉斯定义为 $L=D-A$ ，它是对称正定半定(SPSD) [8]。它的特征分解给出 $L=U\Lambda U^{T}$ ，其中列 $\boldsymbol{u}_{i}$ 是 $U\in{\mathbb{R}}^{N\times N}$ 的标准正交特征向量，即图傅立叶基 $\Lambda=\mathrm{diag}(\lambda_{1},\ldots,\lambda_{N})$ ，满足 $\lambda_{1}\leq\cdots\leq\lambda_{N}$ ，这些特征值也被称为频率。图信号 ${\boldsymbol{x}}$ 的图傅立叶变换定义为 $\bm{x}_{\mathcal{F}}=U^{-1}\bm{x}=U^{T}\bm{x}=[\boldsymbol{u}_{1}^{T}{\boldsymbol{x}},\ldots,\boldsymbol{u}_{N}^{T}{\boldsymbol{x}}]^{T}$ ，其中 $\bm{u}_{i}^{T}\bm{x}$ 是 $\bm{x}$ 在 $\bm{u_{i}}$ 方向上的分量。

In additional to $L$, some variants are also commonly used, e.g., the symmetric normalized Laplacian $L_{\text{sym}}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$ and the random walk normalized Laplacian $L_{\text{rw}}=D^{-1}L=I-D^{-1}A$. The affinity (transition) matrices can be derived from the Laplacians, e.g., $A_{\text{rw}}=I-L_{\text{rw}}=D^{-1}A$, $A_{\text{sym}}=I-L_{\text{sym}}=D^{-1/2}AD^{-1/2}$ and are considered to be low-pass filters [30]. Their eigenvalues satisfy $\lambda_{i}(A_{\text{rw}})=\lambda_{i}(A_{\text{sym}})=1-\lambda_{i}(L_{\text{sym}})=1-\lambda_{i}(L_{\text{rw}})\in(-1,1]$. Applying the renormalization trick [18] to affinity and Laplacian matrices respectively leads to $\hat{A}_{\text{sym}}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ and $\hat{L}_{\text{sym}}=I-\hat{A}_{\text{sym}}$, where $\tilde{A}\equiv A+I$ and $\tilde{D}\equiv D+I$. The renormalized affinity matrix essentially adds a self-loop to each node in the graph, and is widely used in Graph Convolutional Network (GCN) [18] as follows,
除了 $L$ 之外，还有一些常用的变体，例如对称归一化拉普拉斯 $L_{\text{sym}}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$ 和随机游走归一化拉普拉斯 $L_{\text{rw}}=D^{-1}L=I-D^{-1}A$ 。亲和（转移）矩阵可以从拉普拉斯矩阵中导出，例如 $A_{\text{rw}}=I-L_{\text{rw}}=D^{-1}A$ ， $A_{\text{sym}}=I-L_{\text{sym}}=D^{-1/2}AD^{-1/2}$ ，被认为是低通滤波器[30]。它们的特征值满足 $\lambda_{i}(A_{\text{rw}})=\lambda_{i}(A_{\text{sym}})=1-\lambda_{i}(L_{\text{sym}})=1-\lambda_{i}(L_{\text{rw}})\in(-1,1]$ 。将亲和矩阵和拉普拉斯矩阵分别应用重新归一化技巧[18]，得到 $\hat{A}_{\text{sym}}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 和 $\hat{L}_{\text{sym}}=I-\hat{A}_{\text{sym}}$ ，其中 $\tilde{A}\equiv A+I$ 和 $\tilde{D}\equiv D+I$ 。重新归一化的亲和矩阵实质上为图中的每个节点添加了自环，并且在图卷积网络（GCN）[18]中被广泛使用，如下所示，

$$Y=\text{softmax}(\hat{A}_{\text{sym}}\;\text{ReLU}(\hat{A}_{\text{sym}}{X}W_{0})\;W_{1})$$

(1)

where $W_{0}\in{\mathbb{R}}^{F\times F_{1}}$ and $W_{1}\in{\mathbb{R}}^{F_{1}\times O}$ are learnable parameter matrices. GCN can be trained by minimizing the following cross entropy loss
其中 $W_{0}\in{\mathbb{R}}^{F\times F_{1}}$ 和 $W_{1}\in{\mathbb{R}}^{F_{1}\times O}$ 是可学习的参数矩阵。GCN 可以通过最小化以下交叉熵损失来训练

$$\mathcal{L}=-\mathrm{trace}(Z^{T}\log Y)$$

(2)

where $\log(\cdot)$ is a component-wise logarithm operation. The random walk renormalized matrix $\hat{A}_{\text{rw}}=\tilde{D}^{-1}\tilde{A}$, which shares the same eigenvalues as $\hat{A}_{\text{sym}}$, can also be applied in GCN. The corresponding Laplacian is defined as $\hat{L}_{\text{rw}}=I-\hat{A}_{\text{rw}}$. $\hat{A}_{\text{rw}}$ is essentially a random walk matrix and behaves as a mean aggregator that is applied in spatial-based GNNs [15, 14]. To bridge the spectral and spatial methods, we use $\hat{A}_{rw}$ in the paper.
其中 $\log(\cdot)$ 是一个逐分量对数运算。随机游走归一化矩阵 $\hat{A}_{\text{rw}}=\tilde{D}^{-1}\tilde{A}$ ，其特征值与 $\hat{A}_{\text{sym}}$ 相同，也可以应用于 GCN。相应的拉普拉斯定义为 $\hat{L}_{\text{rw}}=I-\hat{A}_{\text{rw}}$ 。 $\hat{A}_{\text{rw}}$ 本质上是一个随机游走矩阵，并且作为应用在基于空间的 GNNs [15, 14]中的均值聚合器。为了连接频谱和空间方法，我们在论文中使用 $\hat{A}_{rw}$ 。

The metrics of homophily are defined by considering different relations between node labels and graph structures defined by adjacency matrix. There are three commonly used homophily metrics: edge homophily [1, 40], node homophily [33], and class homophily [24] ²²2The authors in [24] did not name this homophily metric. We name it class homophily based on its definition.
[ 24]中的作者没有给这个同质性度量取名。我们根据其定义将其命名为类同质性。
同质性度量是通过考虑节点标签之间的不同关系和邻接矩阵定义的图结构来定义的。有三种常用的同质性度量：边同质性[ 1, 40]，节点同质性[ 33]和类同质性[ 24] ² defined as follows: 如下所定义：

		$\displaystyle H_{\text{edge}}(\mathcal{G})=\frac{\big{|}\{e_{uv}\mid e_{uv}\in\mathcal{E},Z_{u,:}=Z_{v,:}\}\big{|}}{|\mathcal{E}|},\ \ H_{\text{node}}(\mathcal{G})=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\frac{\big{|}\{u\mid u\in\mathcal{N}_{v},Z_{u,:}=Z_{v,:}\}\big{|}}{d_{v}},$		(3)
		$\displaystyle H_{\text{class}}(\mathcal{G})=\frac{1}{C-1}\sum_{k=1}^{C}\left[h_{k}-\frac{\big{|}\{v\mid Z_{v,k}=1\}\big{|}}{N}\right]_{+},\ \ h_{k}=\frac{\sum_{v\in\mathcal{V}}\big{|}\{u\mid Z_{v,k}=1,u\in\mathcal{N}_{v},Z_{u,:}=Z_{v,:}\}\big{|}}{\sum_{v\in\{v|Z_{v,k}=1\}}d_{v}}$

where $[a]_{+}=\max(a,0)$; $h_{k}$ is the class-wise homophily metric [24]. They are all in the range of $[0,1]$ and a value close to $1$ corresponds to strong homophily while a value close to $0$ indicates strong heterophily. $H_{\text{edge}}(\mathcal{G})$ measures the proportion of edges that connect two nodes in the same class; $H_{\text{node}}(\mathcal{G})$ evaluates the average proportion of edge-label consistency of all nodes; $H_{\text{class}}(\mathcal{G})$ tries to avoid the sensitivity to imbalanced class, which can cause $H_{\text{edge}}$ misleadingly large. The above definitions are all based on the graph-label consistency and imply that the inconsistency will cause harmful effect to the performance of GNNs. With this in mind, we will show a counter example to illustrate the insufficiency of the above metrics and propose new metrics in the following section.
其中 $[a]_{+}=\max(a,0)$ ; $h_{k}$ 是基于类别的同质性度量[24]。它们都在 $[0,1]$ 的范围内，接近 $1$ 的值表示强同质性，而接近 $0$ 的值表示强异质性。 $H_{\text{edge}}(\mathcal{G})$ 衡量连接两个同类节点的边的比例； $H_{\text{node}}(\mathcal{G})$ 评估所有节点的边标签一致性的平均比例； $H_{\text{class}}(\mathcal{G})$ 试图避免对不平衡类别的敏感性，这可能导致 $H_{\text{edge}}$ 误导性地增大。上述定义都基于图标签的一致性，并暗示不一致性会对 GNN 的性能产生有害影响。考虑到这一点，我们将展示一个反例来说明上述度量的不足，并在下一节提出新的度量方法。

Heterophily is believed to be harmful for message-passing based GNNs [40, 33, 7] because intuitively features of nodes in different classes will be falsely mixed and this will lead nodes indistinguishable [40]. Nevertheless, it is not always the case, e.g., the bipartite graph shown in Figure 1 is highly heterophilous according to the homophily metrics in (LABEL:eq:definition_homophily_metrics), but after mean aggregation, the nodes in classes 1 and 2 only exchange colors and are still distinguishable. Authors in [7] also point out the insufficiency of $H_{\text{node}}$ by examples to show that different graph typologies with the same $H_{\text{node}}$ can carry different label information.
异质性被认为对基于消息传递的 GNNs 有害[ 40, 33, 7]，因为直观地，不同类别节点的特征将被错误混合，这将导致节点无法区分[ 40]。 然而，并非总是如此，例如，图 1 中显示的二部图根据同质性度量在（LABEL:eq:definition_homophily_metrics）中高度异质，但在均值聚合后，类别 1 和 2 中的节点仅交换颜色仍然可区分。 [ 7]中的作者还通过示例指出 $H_{\text{node}}$ 的不足，以表明具有相同 $H_{\text{node}}$ 的不同图拓扑结构可以携带不同的标签信息。

To analyze to what extent the graph structure can affect the output of a GNN, we first simplify the GCN by removing its nonlinearity as [36]. Let $\hat{A}\in\mathbb{R}^{N\times N}$ denote a general aggregation operator. Then, equation (1) can be simplified as,
为了分析图结构对 GNN 输出的影响程度，我们首先通过去除其非线性性来简化 GCN[ 36]。 让 $\hat{A}\in\mathbb{R}^{N\times N}$ 表示一般的聚合算子。 然后，方程（1）可以简化为，

$\displaystyle Y=\text{softmax}(\hat{A}XW)=\text{softmax}(Y^{\prime})$

(4)

After each gradient decent step $\Delta W=\gamma\frac{d\mathcal{L}}{dW}$, where $\gamma$ is the learning rate, the update of $Y^{\prime}$ will be (see Appendix B for derivation),
每次梯度下降步骤之后 $\Delta W=\gamma\frac{d\mathcal{L}}{dW}$ ，其中 $\gamma$ 是学习率， $Y^{\prime}$ 的更新将会是（见附录 B 进行推导），

$\displaystyle\Delta Y^{\prime}=\hat{A}X\Delta W=\gamma\hat{A}X\frac{d\mathcal{L}}{dW}\propto\hat{A}X\frac{d\mathcal{L}}{dW}=\hat{A}XX^{T}\hat{A}^{T}(Z-Y)=S(\hat{A},X)(Z-Y)$

(5)

where $S(\hat{A},X)\equiv\hat{A}X(\hat{A}X)^{T}$ is a post-aggregation node similarity matrix, $Z-Y$ is the prediction error matrix. The update direction of node $i$ is essentially a weighted sum of the prediction error, i.e., $\Delta(Y^{\prime})_{i,:}=\sum_{j\in\mathcal{V}}\left[S(\hat{A},X)\right]_{i,j}(Z-Y)_{j,:}$.
其中 $S(\hat{A},X)\equiv\hat{A}X(\hat{A}X)^{T}$ 是后聚合节点相似性矩阵， $Z-Y$ 是预测误差矩阵。节点 $i$ 的更新方向本质上是预测误差的加权和，即 $\Delta(Y^{\prime})_{i,:}=\sum_{j\in\mathcal{V}}\left[S(\hat{A},X)\right]_{i,j}(Z-Y)_{j,:}$ 。

To study the effect of heterophily, we first define the aggregation similarity score as follows.
研究异质性效应，我们首先定义聚集相似度分数如下。

$S_{\text{agg}}(S(\hat{A},X))$ measures the proportion of nodes $v\in\mathcal{V}$ that will put relatively larger similarity weights on nodes in the same class than in other classes after aggregation. It is easy to see that $S_{\text{agg}}(S(\hat{A},X))\in[0,1]$. But in practice, we observe that in most datasets, we will have $S_{\text{agg}}(S(\hat{A},X))\geq 0.5$. Based on this observation, we rescale (6) to the following modified aggregation similarity for practical usage,

$$S^{M}_{\text{agg}}\left(S(\hat{A},X)\right)=\left[2S_{\text{agg}}\left(S(\hat{A},X)\right)-1\right]_{+}$$

(7)

In order to measure the consistency between labels and graph structures without considering node features and make a fair comparison with the existing homophily metrics in (LABEL:eq:definition_homophily_metrics), we define the graph ($\mathcal{G}$) aggregation ($\hat{A}$) homophily and its modified version as

$$H_{\text{agg}}(\mathcal{G})=S_{\text{agg}}\left(S(\hat{A},Z)\right),\;H_{\text{agg}}^{M}(\mathcal{G})=S_{\text{agg}}^{M}\left(S(\hat{A},Z)\right)$$

(8)

In practice, we will only check $H_{\text{agg}}(\mathcal{G})$ when $H_{\text{agg}}^{M}(\mathcal{G})=0$. As Figure 1 shows, when $\hat{A}=\hat{A}_{\text{rw}}$, $H_{\text{agg}}(\mathcal{G})=H_{\text{agg}}^{M}(\mathcal{G})=1$. Thus, this new metric reflects the fact that nodes in classes 1 and 2 are still highly distinguishable after aggregation, while other metrics mentioned before fail to capture the information and misleadingly give value 0. This shows the advantage of $H_{\text{agg}}(\mathcal{G})$ and $H_{\text{agg}}^{M}(\mathcal{G})$ by additionally considering information from aggregation operator $\hat{A}$ and the similarity matrix.
在实践中，我们只会在 $H_{\text{agg}}^{M}(\mathcal{G})=0$ 时检查 $H_{\text{agg}}(\mathcal{G})$ 。如图 1 所示，当 $\hat{A}=\hat{A}_{\text{rw}}$ 时， $H_{\text{agg}}(\mathcal{G})=H_{\text{agg}}^{M}(\mathcal{G})=1$ 。因此，这个新度量反映了类别 1 和 2 中的节点在聚合后仍然高度可区分，而之前提到的其他度量未能捕捉到这一信息，误导性地给出值 0。这显示了 $H_{\text{agg}}(\mathcal{G})$ 和 $H_{\text{agg}}^{M}(\mathcal{G})$ 的优势，因为它们另外考虑了来自聚合算子 $\hat{A}$ 和相似度矩阵的信息。

To comprehensively compare $H_{\text{agg}}^{M}(\mathcal{G})$ with the metrics in (LABEL:eq:definition_homophily_metrics) in terms of how they reveal the influence of graph structure on the GNN performance, we generate synthetic graphs and evaluate SGC [36] and GCN [18] on them in the next subsection.
为了全面比较 $H_{\text{agg}}^{M}(\mathcal{G})$ 与(LABEL:eq:definition_homophily_metrics)中的指标，看它们如何揭示图结构对 GNN 性能的影响，我们生成了合成图，并在下一小节评估了 SGC [ 36]和 GCN [ 18]。