Understanding the Expressive Power of Graph Neural Networks and Advanced Models

1. Graph Neural Networks (GNN)

Graph neural networks (GNN) are used for graph‑level, node‑level, and edge‑level prediction tasks; they can be viewed as functions mapping graphs (with node/edge features) to real‑valued outputs, such as molecular properties.

The expressive power of GNNs concerns how well these graph functions can approximate arbitrary functions.

2. Message Passing Neural Networks (MPNN)

MPNN iteratively updates node embeddings by aggregating messages from neighboring nodes; different neural networks for message generation and node update yield various MPNN variants.

3. Measuring GNN Expressive Power

Key criteria include the ability to distinguish non‑isomorphic graphs (equivalent to the Weisfeiler‑Lehman test for many MPNNs) and to count subgraphs.

2‑Invariant Graph Network (2‑IGN) extends MPNN with equivariant linear layers, achieving global information flow but still limited to 2‑WL distinguishing power.

4. Building More Expressive Models

Ring‑GNN adds matrix multiplication to the 2‑IGN framework, enabling it to distinguish previously indistinguishable non‑isomorphic graphs.

Local Relational Pooling (LRP) applies a powerful Relation Pooling (RP) model to each local neighborhood and aggregates the results, offering stronger expressive ability with manageable complexity.

5. Graph‑Augmented MLP (GA‑MLP)

GA‑MLP separates node feature transformation from propagation, using multi‑hop graph operators to generate augmented node features, which improves scalability and mitigates over‑smoothing.

Comparisons show GA‑MLP may fail to distinguish certain non‑isomorphic graphs that GNNs can, due to limited ability to capture rooted subtree information.

6. Applications and Experiments

LRP achieves strong performance on molecular datasets (QM9, MolHIV) and can identify substructures related to molecular properties.

GA‑MLP with different graph operators (e.g., adjacency matrix powers, Bethe Hessian) shows varying results on community detection, highlighting the importance of operator choice.

7. Q&A Highlights

Expressive power is one factor among optimization, generalization, and scalability; stronger expressive models often perform better on small‑graph tasks like molecular prediction.

MPNN propagates information depth‑wise, while GA‑MLP relies on pre‑computed high‑order operators.

Subgraph counting serves as a practical benchmark for expressive ability because many real‑world tasks depend on recognizing specific substructures.

Conclusion

The article summarizes three expressive‑power metrics—distinguishing non‑isomorphic graphs, subgraph counting, and attributed‑walk counting—and demonstrates limitations of existing models while proposing Ring‑GNN and LRP as more powerful alternatives.