On the Topology Awareness and Generalization Performance of Graph Neural
  Networks
Junwei Su Chuan Wu
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.