Understanding Graph Neural Network Expressiveness and Differences between MPNN and Graph‑Augmented MLP

Q1: Is the expressive power of graph neural networks (GNNs) proportional to their practical performance, and are there comparative application examples?

A1: Expressive power is only one aspect; models also need to consider optimization, generalization, stability, scalability, etc. A stronger expressive model does not guarantee better performance; it depends on the task. In molecular prediction, where graphs are small and scalability is not a bottleneck, models with higher expressive power often perform better. In large‑scale scenarios such as social networks, scalability and over‑smoothing become critical, and overly complex models may overfit and be affected by noise.

Q2: MPNN also aggregates and propagates based on the adjacency matrix; what is the fundamental difference from Graph‑Augmented MLP approaches?

A2: In MPNNs, the distance that information can travel in the graph equals the depth of the network—e.g., a 10‑layer MPNN can gather information from nodes up to ten hops away. By contrast, Graph‑Augmented MLP is a “shallow” architecture: to obtain ten‑hop information it does not stack ten propagation layers but instead applies the adjacency matrix raised to the 10th power to generate augmented node features, then processes each node with a two‑ or three‑layer MLP.

Q3: Why is measuring a model’s expressive ability related to subgraph counting?

A3: This is the metric we propose for expressive ability. Fundamentally, the expressive power of a GNN is its capacity to approximate functions on graphs—i.e., the universal approximation property. Similar to studies on feed‑forward networks, we investigate which functions GNNs can represent, focusing on tasks such as subgraph counting that are relevant to real‑world applications.

Chen Zhengdao, Ph.D. student at New York University – Guest speaker.

"What Kind of Graph Neural Network Has Stronger Expressive Ability?" – Source.

DataFun is celebrating its 5‑year anniversary. From December 2022 to January 2023, a series of technical articles will be published, focusing on hot topics in big data and artificial intelligence, featuring contributions from senior community experts who will summarize recent technological evolutions and forecast future trends. Additionally, on January 7, 2023, DataFunTalk will release the industry’s first data‑intelligence knowledge map, with a live broadcast invitation for interested participants.