In Graph Neural Networks (GNNs), hierarchical pooling operators generate
local summaries of the data by coarsening the graph structure and the vertex
features. Considerable attention has been devoted to analyzing the expressive
power of message-passing (MP) layers in GNNs, while a study on how graph
pooling affects the expressiveness of a GNN is still lacking. Additionally,
despite the recent advances in the design of pooling operators, there is not a
principled criterion to compare them. In this work, we derive sufficient
conditions for a pooling operator to fully preserve the expressive power of the
MP layers before it. These conditions serve as a universal and
theoretically-grounded criterion for choosing among existing pooling operators
or designing new ones. Based on our theoretical findings, we analyze several
existing pooling operators and identify those that fail to satisfy the
expressiveness conditions. Finally, we introduce an experimental setup to
verify empirically the expressive power of a GNN equipped with pooling layers,
in terms of its capability to perform a graph isomorphism test.

本文研究图神经网络中的池化操作的表现力问题，并介绍了一种可以全面维持 message-passing 层的表现力的池化操作设计原则，进而通过实验验证其在图同构检测上的效果。

图神经网络中池化的表达能力

The expressive power of pooling in Graph Neural Networks

Message passing Graph Neural Networks (GNNs) provide a powerful modeling
framework for relational data. However, the expressive power of existing GNNs
is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test,
which means GNNs that are not able to predict node clustering coefficients and
shortest path distances, and cannot differentiate between different d-regular
graphs. Here we develop a class of message passing GNNs, named Identity-aware
Graph Neural Networks (ID-GNNs), with greater expressive power than the 1-WL
test. ID-GNN offers a minimal but powerful solution to limitations of existing
GNNs. ID-GNN extends existing GNN architectures by inductively considering
nodes' identities during message passing. To embed a given node, ID-GNN first
extracts the ego network centered at the node, then conducts rounds of
heterogeneous message passing, where different sets of parameters are applied
to the center node than to other surrounding nodes in the ego network. We
further propose a simplified but faster version of ID-GNN that injects node
identity information as augmented node features. Altogether, both versions of
ID-GNN represent general extensions of message passing GNNs, where experiments
show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy
improvement on challenging node, edge, and graph property prediction tasks; 3%
accuracy improvement on node and graph classification benchmarks; and 15% ROC
AUC improvement on real-world link prediction tasks. Additionally, ID-GNNs
demonstrate improved or comparable performance over other task-specific graph
networks.

本文提出了一种名为 Identity-aware Graph Neural Networks (ID-GNNs) 的消息传递图神经网络，通过节点中心的次元网络和异构消息传递来考虑节点的身份，在图形预测任务中比传统的 GNNs 提供更高的准确性。