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

理解图神经网络的异质性

Understanding Heterophily for Graph Neural Networks

Persistent homology is a method for probing topological properties of point
clouds and functions. The method involves tracking the birth and death of
topological features (2000) as one varies a tuning parameter. Features with
short lifetimes are informally considered to be "topological noise," and those
with a long lifetime are considered to be "topological signal." In this paper,
we bring some statistical ideas to persistent homology. In particular, we
derive confidence sets that allow us to separate topological signal from
topological noise.

本文介绍在持久同调领域引入统计学思想，利用置信集区分拓扑信号与拓扑噪声的研究。