Summary
In this article, the authors present new contributions on the understanding on the computational framework provided by GNNs.
In particular, they draw a connection between Arithmetic Circuits and GNNs.
Based on a new definition of GNN using arithmetic circuits, they show that the function computed by a GNN on each node can be thought of a function that an (tail-symmetric) arithmetic circuit computes, by stacking the adjacency matrix of the graph and the features vector. In other words, by using arithmetic circuits as comb and aggregation functions inside a message passing framework, the overall procedure can still be thought of as an arithmetic circuit (and vice-versa).
Strengths
- The paper reads well, in particular the introduction about related work is useful. (although the authors may want to include some additional references for completeness, as detailed below in the Questions section).
- The authors propose a new way to think about GNNs, as a correspondence between a given iteration number, and two family circuits (which used to be the COMB and AGG functions).
- I find the several contributions interesting.
Weaknesses
- The main weakness that I can see, is that the definition of the C-GNNs makes the connection between AC-GNN (or close variants, which is what is implemented and used in practice) and circuits. Since the correspondence between GNNs and tail-symmetric arithmetic circuit is established in the following sense:
$$ \text{AC-GNN} \subsetneq (\text{ C-GNNs} = FAC^{0}_{\mathbb{R}^{k}}[\mathcal{A}] )$$
There is potentially a huge gap between AC-GNNs and C-GNNs, that is partially discussed in Remark 3.4. The obscure part of this correspondance seems to arise mainly because of the aggregation functions: i.e., if we have the sum, max and product as aggregation functions, what part of the C-GNNs can we simulate (with polynomial reductions)?
- Also, although I personally find the results interesting, they are not very deep or insightful: if one provide arithmetic circuit power on each node, and arithmetic circuit power as aggregation, then we obtain at most arithmetic circuits.
Questions
- The authors emphasize (and I think it is a good thing) that the computational equivalence they obtain with Arithmetic circuits is something that applies to the message passing framework (the essence of GNNs), regardless of the computational power on the nodes. But in their work, the authors provide an arithmetic circuit as computational power to the nodes. In other words, do the authors believe there is an arithmetic circuit that cannot be computed by an AC-GNN?
- The authors define standard notations like $[n]$, notation for multisets, but not for $(\mathbb{R}^{k})^{*}$. This probably refers to all possible n-tuples of $R^{k}$ for every n. However, it becomes confusing at several locations in the paper.
- From the abstract, the authors mention that their result hold uniformly and non uniformly. This is not mentioned again nor explained in the paper (uniform vs. non uniform) (except if I missed it?)
- The definition of an AC-GNN, as an C-GNN does not coincide with the standard one: a function \sigma^{i} is applied after the combination. This does not align for instance with [2020, Barcelo & Al.].
- Definition 3.3, is unclear: The authors may want to elaborate why the proj_1 and proj_2 operations are made consecutively, why is proj_2 needed for $\sigma^{(i)}$ ? I suppose that this is in order to have access to two different arithmetic consecutively.
- The authors may want to consider in their introduction, in order to compare their result (in particular the independence w.r.t. the activation functions) the references:
- Impact of aggregation function: Eran Rosenbluth, Jan Tönshoff, Martin Grohe ``Some might say all you need is sum``
Martin Grohe, Eran Rosenbluth ``Are Targeted Messages More Effective?``
- Impact of activation function on GNN expressivity: Sammy Khalife ``Graph Neural Networks with polynomial activations cannot express all GC2 queries``
- Sammy Khalife, Amitabh Basu ``On the power of graph neural networks and the role of the activation function.``
- In proof of Theorem 3.11 is used Definition A.7, and mentioned (``via the injective function'', but this definition allows several functions (as long as different depth implies different values taken by the function). Can the authors confirm and/or clarify this?
- I had a look at the proof of Theorem 3.11 in details (I find this result the most interesting). Can the authors confirm: the essence of the proof is to group the input of the initial circuits (vector of reals) and the circuit as a new graph input to the C-GNN? The gates and structure of the initial circuit is then processed by the C-GNN, in order to compensate for the excess (addition and multiplication shown in Algorithm 1). The division performed in Algorithm 1 is allowed as it is the same as multiplying by the inverse of a constant (this number is indeed a constant as it relates to the structure of the circuit, not the input).
Limitations
The authors are transparent in the conclusion of their work about the limitations of their work.