Weisfeiler and Leman Return with Graph Transformations

Fabian Jogl, Maximilian Thiessen, Thomas GärtnerOpenReview 2022 · OpenReview

TL;DR

This paper introduces novel graph transformations that allow standard message-passing Graph Neural Networks (GNNs) to achieve higher expressiveness, matching or exceeding specialized GNN architectures. By transforming graphs before feeding them into existing GNNs, these methods offer a simple yet powerful way to boost performance on graph-based tasks without altering the core learning algorithm.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) that rely on message passing, a common and powerful paradigm for learning on graph-structured data, often suffer from limited expressiveness. This means they can struggle to distinguish between different graph structures, a limitation often quantified by the Weisfeiler-Leman (WL) test. While researchers have developed more expressive GNNs by modifying the message-passing mechanism itself, these approaches can be complex to implement and integrate. The paper addresses this by proposing an alternative: transforming the input graph before message passing, thereby enabling standard GNNs to achieve greater expressive power. This approach aims to be more flexible and easier to adopt than modifying the GNN architecture directly.

Methods

The core contribution of this paper lies in proposing and analyzing two novel graph transformations:

  • Cell Encoding: This method transforms a regular cell complex into a graph. Regular cell complexes are a generalization of simplicial complexes that can capture richer topological information. By encoding these complexes as graphs, standard GNNs can leverage this richer structure. The authors prove that Cell Encoding, when combined with the WL test or a powerful GNN, is at least as expressive as Cellular Weisfeiler-Leman (CWL), a specialized message-passing algorithm for cell complexes.
  • Subgraph Bag Encoding (SBE): This approach transforms a graph into a "bag" of subgraphs, which is then represented as a single graph. SBE allows for flexible integration of various "policies" that define how subgraphs are extracted. The authors prove that SBE, when combined with WL or a powerful GNN, is at least as expressive as DSS-WL, a stronger variant of the WL test designed for subgraph-based methods.

The paper also discusses related concepts like Cellular Ring Encoding (CRE) and the use of type pooling to enhance GNN performance.

Datasets

The paper evaluates its proposed methods on the following datasets:

  • ZINC: A graph regression dataset containing molecular graphs.
  • ogbg-molhiv: A graph classification dataset from the Open Graph Benchmark (OGB) for molecular property prediction.
  • ogbg-moltox21: Another OGB graph classification dataset for molecular property prediction.

These datasets are standard benchmarks for graph machine learning tasks, particularly in the cheminformatics domain.

Key Insights and Ideas

  • Graph Transformations as a Powerful Alternative: The paper demonstrates that modifying the input graph through transformations can be as effective, if not more so, than directly altering the message-passing mechanism of GNNs for achieving higher expressiveness.
  • Bridging the Gap to Specialized Architectures: By using graph transformations, standard GNNs can achieve the expressiveness of more complex, specialized architectures like CW Networks and Equivariant Subgraph Aggregation Networks (ESANs) with minimal changes to the learning pipeline.
  • Simplicity and Flexibility: The proposed transformations require only preprocessing the input data, making them easy to integrate with existing GNN implementations and allowing for quick experimentation with different GNN backbones.
  • Theoretical Guarantees: The authors provide theoretical proofs showing that their graph transformations, when combined with the Weisfeiler-Leman test or a sufficiently powerful GNN, achieve specific expressiveness guarantees.
  • Empirical Validation: Beyond theoretical claims, the paper shows that these transformations lead to competitive results on real-world molecular graph datasets.

Key Results

The paper presents empirical results on graph classification and regression tasks.

  • Competitive Performance: GIN+CRE (GIN with Cell Encoding) and CIN (Cellular Networks) achieved similar results on the tested datasets, outperforming the baseline GIN on two out of three.
  • Strong Improvements: GIN+SBE (GIN with Subgraph Bag Encoding) showed significant improvements over GIN and MLP baselines on two datasets and was competitive with DSS-GNN.
  • ZINC Dataset: Both graph transformations (CRE and SBE) showed strong improvements over GIN on the ZINC dataset.

Limitations and Future Work

  • Computational Overhead: While the transformations themselves are efficient, running WL on the transformed graphs can be computationally more expensive than specialized WL variants, especially for the d-k graph transformation which uses global neighborhoods. The authors suggest that using edge features can mitigate this.
  • Expressiveness vs. Performance: The paper acknowledges that increased expressiveness does not always directly translate to better predictive performance. They propose future work to formalize this idea and investigate how to improve message passing while avoiding the pitfalls of simply compressing information into a single vector.
  • Generalization of Message Passing: The authors conjecture that any GNN that passes messages between objects along fixed paths can be implemented as a graph transformation plus a message-passing neural network (MPNN). This is an area for future exploration.

Summary updated

Abstract

We propose novel graph transformations that allow standard message passing to achieve state-of-the-art expressiveness and predictive performance. Message passing graph neural networks are known to have limited expressiveness in distinguishing graphs. To mitigate this, one can either change message passing or modify the graphs. Changing message passing is powerful but requires significant changes to existing implementations and cannot easily be combined with other approaches. Modifying the graph requires no changes to the learning algorithm and works directly with off-the-shelf implementations. In this paper, we propose novel graph transformations and compare them to the state-of-the-art. We prove that they are at least as expressive as corresponding message passing algorithms when combined with the Weisfeiler-Leman test or a sufficiently powerful graph neural network. Furthermore, we empirically demonstrate that these transformations lead to competitive results on molecular graph datasets.
BibTeX
@misc{jogl2022weisfeiler,
  author = {Fabian Jogl and Maximilian Thiessen and Thomas Gärtner},
  title = {{Weisfeiler and Leman Return with Graph Transformations}},
  year = {2022},
  url = {https://openreview.net/forum?id=Oq5mzL-3SUV},
  howpublished = {OpenReview},
}
Figure