- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies GNN expressivity, namely preservation under three graph operations: embeddings (extensions), injective homomorphisms, and homomorphisms. To derive the results, authors first focus on logic (so they restrict GNNs to so called threshold-based classifiers). Inb the logic setting, they are able to show that a class of (pointed) graphs is preserved under one of these operations iff it is expressible in suitable fragments of graded modal logic, and then that the class of graphs accepred by a GNN is preserved under these relations iff they are expressible in the corresponding fragments. The second half of the paper deals with syntactic definitions of GNNs that realize these preservation results, which leads to three new classes of GNNs and all capture precisely their corresponding logical formalism.
The paper contains very nice theoretical results, the logical part is probably of independent interest, although GNNs are probably the most obvious applications.
Critical strengths
- Very good theoretical results, with connections from several areas, and a direct application of finite model theory in machine learning.
- Paper is nonetheless very easy to read.
Critical weaknesses
- The main weakness of the paper is the lack of discussion in terms of practical impact. The main question that I would like to be answered is: Why would someone implement one of MGNNs, augmented MGNNs or MAX-MGNNs instead of a more standard GNN model? In terms of expressive power, a more powerful GNN model capable of capturing all graded modal logic would suffice. I think authors discuss about building models to specifically enforce structural preservation properties on the passing, and this could be an interesting answer, but more expanded discussion would be ideal.
Questions for authors
- please engage with the weakness stated above.