Graphs with heterophily have been regarded as challenging scenarios for Graph
Neural Networks (GNNs), where nodes are connected with dissimilar neighbors
through various patterns. In this paper, we present theoretical understandings
of the impacts of different heterophily patterns for GNNs by incorporating the
graph convolution (GC) operations into fully connected networks via the
proposed Heterophilous Stochastic Block Models (HSBM), a general random graph
model that can accommodate diverse heterophily patterns. Firstly, we show that
by applying a GC operation, the separability gains are determined by two
factors, i.e., the Euclidean distance of the neighborhood distributions and
$\sqrt{\mathbb{E}\left[\operatorname{deg}\right]}$, where
$\mathbb{E}\left[\operatorname{deg}\right]$ is the averaged node degree. It
reveals that the impact of heterophily on classification needs to be evaluated
alongside the averaged node degree. Secondly, we show that the topological
noise has a detrimental impact on separability, which is equivalent to
degrading $\mathbb{E}\left[\operatorname{deg}\right]$. Finally, when applying
multiple GC operations, we show that the separability gains are determined by
the normalized distance of the $l$-powered neighborhood distributions. It
indicates that the nodes still possess separability as $l$ goes to infinity in
a wide range of regimes. Extensive experiments on both synthetic and real-world
data verify the effectiveness of our theory.

本研究通过引入 Heterophilous Stochastic Block Models (HSBM) 来深入理解图中物种异质性模式对图神经网络的影响，揭示了图卷积操作对分类的可分性提升受到邻域分布欧氏距离和平均节点度的影响，且拓扑噪声对可分性有不利影响，多次图卷积操作时，可分性受邻域分布归一化距离的影响。通过实验验证了理论的有效性。