Theoretical studies on the representation power of GNNs have been centered around understanding the equivalence of GNNs, using WL-Tests for detecting graph isomorphism. In this paper, we argue that such equivalence ignores the accompanying optimization issues and does not provide a holistic view of the GNN learning process. We illustrate these gaps between representation and optimization with examples and experiments. We also explore the existence of an implicit inductive bias (e.g. fully connected networks prefer to learn low frequency functions in their input space) in GNNs, in the context of graph classification tasks. We further prove theoretically that the message-passing layers in the graph, have a tendency to search for either discriminative subgraphs, or a collection of discriminative nodes dispersed across the graph, depending on the different global pooling layers used. We empirically verify this bias through experiments over real-world and synthetic datasets. Finally, we show how our work can help in incorporating domain knowledge via attention based architectures, and can evince their capability to discriminate coherent subgraphs.

本研究针对图神经网络（GNNs）在表示与优化之间的差异提出了新的见解，指出现有的等价性研究忽视了优化问题。通过理论证明和实验验证，揭示了GNNs在图分类任务中存在的隐含归纳偏差，并展示了如何通过基于注意力的架构融入领域知识以更有效地识别一致子图。

图分类与图神经网络：优化、表示与归纳偏差