Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven
learning on various graph domains. They are usually based on a message-passing
mechanism and have gained increasing popularity for their intuitive
formulation, which is closely linked to the Weisfeiler-Lehman (WL) test for
graph isomorphism to which they have been proven equivalent in terms of
expressive power. In this work, we establish new generalization properties and
fundamental limits of GNNs in the context of learning so-called identity
effects, i.e., the task of determining whether an object is composed of two
identical components or not. Our study is motivated by the need to understand
the capabilities of GNNs when performing simple cognitive tasks, with potential
applications in computational linguistics and chemistry. We analyze two case
studies: (i) two-letters words, for which we show that GNNs trained via
stochastic gradient descent are unable to generalize to unseen letters when
utilizing orthogonal encodings like one-hot representations; (ii) dicyclic
graphs, i.e., graphs composed of two cycles, for which we present positive
existence results leveraging the connection between GNNs and the WL test. Our
theoretical analysis is supported by an extensive numerical study.

在研究中，我们分析了 Graph Neural Networks 在简单认知任务中的能力，并讨论了其在学习所谓的 “identity effects” 时的一般化特性和基本限制。 我们通过两个案例研究来支持我们的理论分析。