Recent studies on Graph Neural Networks(GNNs) provide both empirical and
theoretical evidence supporting their effectiveness in capturing structural
patterns on both homophilic and certain heterophilic graphs. Notably, most
real-world homophilic and heterophilic graphs are comprised of a mixture of
nodes in both homophilic and heterophilic structural patterns, exhibiting a
structural disparity. However, the analysis of GNN performance with respect to
nodes exhibiting different structural patterns, e.g., homophilic nodes in
heterophilic graphs, remains rather limited. In the present study, we provide
evidence that Graph Neural Networks(GNNs) on node classification typically
perform admirably on homophilic nodes within homophilic graphs and heterophilic
nodes within heterophilic graphs while struggling on the opposite node set,
exhibiting a performance disparity. We theoretically and empirically identify
effects of GNNs on testing nodes exhibiting distinct structural patterns. We
then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs,
revealing reasons for the performance disparity, namely the aggregated feature
distance and homophily ratio difference between training and testing nodes.
Furthermore, we demonstrate the practical implications of our new findings via
(1) elucidating the effectiveness of deeper GNNs; and (2) revealing an
over-looked distribution shift factor on graph out-of-distribution problem and
proposing a new scenario accordingly.

本文研究了 GNN 在同构和异构图中节点分类性能的差异。我们提出了一种非 i.i.d PAC-Bayesian 概率界，并通过特征聚合距离和同质比异质性差异解释了性能差异，并证实了较深的 GNN 的有效性。此外，我们发现了图形分布偏移问题的一个新因素，并提出了相应的新场景。

图神经网络结构差异的解密：一个大小适合所有问题么？

Demystifying Structural Disparity in Graph Neural Networks: Can One Size  Fit All?

Graph Neural Networks (GNNs) have been highly successful for the node
classification task. GNNs typically assume graphs are homophilic, i.e.
neighboring nodes are likely to belong to the same class. However, a number of
real-world graphs are heterophilic, and this leads to much lower classification
accuracy using standard GNNs. In this work, we design a novel GNN which is
effective for both heterophilic and homophilic graphs. Our work is based on
three main observations. First, we show that node features and graph topology
provide different amounts of informativeness in different graphs, and therefore
they should be encoded independently and prioritized in an adaptive manner.
Second, we show that allowing negative attention weights when propagating graph
topology information improves accuracy. Finally, we show that asymmetric
attention weights between nodes are helpful. We design a GNN which makes use of
these observations through a novel self-attention mechanism. We evaluate our
algorithm on real-world graphs containing thousands to millions of nodes and
show that we achieve state-of-the-art results compared to existing GNNs. We
also analyze the effectiveness of the main components of our design on
different graphs.

本研究设计了一种新颖的图神经网络，通过自注意机制，优先适应不同的图的不同节点特征和拓扑结构，且考虑到正负权重和节点对称性，在处理同构和异构图分类任务上，相较于传统的图神经网络实现了最领先的性能。