Many computer vision and machine learning problems are modelled as learning
tasks on graphs, where graph neural networks (GNNs) have emerged as a dominant
tool for learning representations of graph-structured data. A key feature of
GNNs is their use of graph structures as input, enabling them to exploit the
graphs' inherent topological properties-known as the topology awareness of
GNNs. Despite the empirical successes of GNNs, the influence of topology
awareness on generalization performance remains unexplored, particularly for
node-level tasks that diverge from the assumption of data being independent and
identically distributed (I.I.D.). The precise definition and characterization
of the topology awareness of GNNs, especially concerning different topological
features, are still unclear. This paper introduces a comprehensive framework to
characterize the topology awareness of GNNs across any topological feature.
Using this framework, we investigate the effects of topology awareness on GNN
generalization performance. Contrary to the prevailing belief that enhancing
the topology awareness of GNNs is always advantageous, our analysis reveals a
critical insight: improving the topology awareness of GNNs may inadvertently
lead to unfair generalization across structural groups, which might not be
desired in some scenarios. Additionally, we conduct a case study using the
intrinsic graph metric, the shortest path distance, on various benchmark
datasets. The empirical results of this case study confirm our theoretical
insights. Moreover, we demonstrate the practical applicability of our framework
by using it to tackle the cold start problem in graph active learning.

本文介绍了一个综合性框架，用于描述图神经网络在任何拓扑特征上的拓扑感知能力，并研究了拓扑感知对图神经网络的泛化性能的影响。通过案例研究和实证结果，发现提高图神经网络的拓扑感知能力可能会在结构组之间造成不公平的泛化，同时展示了该框架在解决图主动学习中的冷启动问题上的实际适用性。