ICML 2023

Timezone: »

Oral

Equivariant Polynomials for Graph Neural Networks

Omri Puny · Derek Lim · Bobak T Kiani · Haggai Maron · Yaron Lipman

Thu Jul 27 06:32 PM -- 06:40 PM (PDT) @ Ballroom C

in Oral C5 Misc »

Graph Neural Networks (GNN) are inherently limited in their expressive power. Recent seminal works (Xu et al., 2019; Morris et al., 2019b) introduced the Weisfeiler-Lehman (WL) hierarchy as a measure of expressive power. Although this hierarchy has propelled significant advances in GNN analysis and architecture developments, it suffers from several significant limitations. These include a complex definition that lacks direct guidance for model improvement and a WL hierarchy that is too coarse to study current GNNs. This paper introduces an alternative expressive power hierarchy based on the ability of GNNs to calculate equivariant polynomials of a certain degree. As a first step, we provide a full characterization of all equivariant graph polynomials by introducing a concrete basis, significantly generalizing previous results. Each basis element corresponds to a specific multi-graph, and its computation over some graph data input corresponds to a tensor contraction problem. Second, we propose algorithmic tools for evaluating the expressiveness of GNNs using tensor contraction sequences, and calculate the expressive power of popular GNNs. Finally, we enhance the expressivity of common GNN architectures by adding polynomial features or additional operations / aggregations inspired by our theory. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.

[ PDF]

Author Information

Omri Puny (Weizmann Institute of Science)

Derek Lim (MIT)

Bobak T Kiani (MIT)

Haggai Maron (NVIDIA Research)

I am a Research Scientist at NVIDIA Research. My main fields of interest are machine learning, optimization, and shape analysis. More specifically, I am working on applying deep learning to irregular domains (e.g., graphs, point clouds, and surfaces) and graph/shape matching problems. I completed my Ph.D. in 2019 at the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman.

Yaron Lipman (Meta AI, WIS)

Related Events (a corresponding poster, oral, or spotlight)

2023 Poster: Equivariant Polynomials for Graph Neural Networks »
Thu. Jul 27th through Fri the 28th Room Exhibit Hall 1 #228