揭示消息传递GNN在图结构区分上的根本表达力瓶颈
Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
- 定义聚合函数的信息复杂度，统一刻画多种实际聚合方式
- 任何此类MP-GNN最多区分多项式级图等价类，而真实图数量为超指数级
- 对比2轮颜色细化即达指数级区分能力，凸显MP-GNN表达力严重不足
我们为聚合函数定义了一种信息复杂度属性，涵盖大量实际应用中的聚合方式。证明了使用此类聚合的任意消息传递图神经网络（MP-GNN）在所有图上仅能产生多项式数量的等价类，而不同构图的数量是超指数级（随顶点数增长）。从另一视角看，仅需2轮颜色细化（CR）即可生成至少指数级的等价类，表明上述MP-GNN表达力相对极其有限。以往研究称求和聚合的MP-GNN可匹配完整颜色细化，但其比较基于弱化的‘非均匀’区分能力——每个图大小可能需要不同的MP-GNN来区分至该规模。本文结果同时涉及非同构顶点与非同构图的区分能力。
原文摘要 · Abstract (English)
We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2 iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。