Summary
The authors introduce a novel graph learning method that leverages message passing over product graphs. Specifically, message passing is performed over both the input graph and its product with a coarsened version of itself, which can be derived through techniques such as node clustering. Additionally, the authors propose a concept called symmetry-based updates, where message passing is enhanced by incorporating a graph representing a linear equivariant layer over the product graphs. A basis for such layers is also developed as part of their contribution. Experimental results demonstrate that this method performs comparably to state-of-the-art approaches.
Strengths
**S1 Product construction** The main conceptual contribution of the paper is the use of product graph construction to allow more flexibility and control over certain types of subgraph GNNs. The product construction itself is quite natural, although it introduces some overhead depending on the chosen instantiation.
**S2 Equivariant basis** The key theoretical contribution is the identification of the bases of equivariant layers for such product graphs. This allows for a principled introduction of message passing using symmetries in the product graph.
**S3 Competitive architecture** Experiments validate the proposed methods, showing that they are competitive with state-of-the-art methods.
Weaknesses
**W1 Unclear key definition**
The key idea underlying the paper is commendable, although not extremely innovative. However, one crucial component is the graph coarsening introduced in Section 4.1. I found the definition on page 4 confusing despite multiple readings. What is defined there is an exponentially large fixed graph, with all subsets as nodes and adjacencies defined in equation (3). However, you mention before and after this that various coarsenings can be used, such as spectral clustering. How do these fit into the fixed definition given here? The presentation could be clearer.
**W2 Weak theoretical analysis**
The significance of Section 5, where the authors use their model for analyzing marking strategies, is not strongly demonstrated, at least based on the main paper. It primarily serves to justify the marking strategy in equation (10) but leaves a more detailed understanding of this strategy open. The section would benefit from a clearer presentation.
**W3 Unclear presentation**
Certain parts, as noted already in **W1** and **W2**, are not clearly described. Another example is Section 4.2.3, which is too succinct, and the visualization of $A_{equiv}$ is rather cryptic. You mention a characterization and updates, but it is not clear what is meant here. A clear description of the instantiation of the framework used would be helpful. Similarly, the section starting from line 357 about “more than a coarsening function” is unclear, including the “informal” proposition statement.
**W4 Unclear connection with OSANs**
In the related work section, the authors contrast their proposal with OSANs [30], stating that OSANs use ordered tuples whereas the current paper uses sets of indices. However, unordered subgraphs play a key role in the OSAN paper as well since they showed that they can encompass most subgraph formalisms. A more detailed comparison would benefit the paper.
**W5 Missing experimental details**
- For the peptides experiments, you write “by using effective subsets of subgraphs.” What do you mean by this? What is this effective subset? How did you choose it?
- Which version of OSAN do you compare with in the experiments (Table 4)?
- Why do you use comparisons with different methods across the experiments (Table 2 vs Table 4)?
**W6 Maximally expressiveness: clarification needed** At several points in the paper, you mention maximally expressive subgraph GNNs. It is unclear what is meant by this and this should be detailed, regardless of whether it was shown in [39]. As far as I know, general subgraph GNN do not have a maximally expressive instantiation, so I assume certain restrictions on the class of subgraph GNNs are in place. It would be beneficial to make these explicit to better understand the limitations of the proposed methods.
**W7 Minor comments**
*All figures (especially the font size used in the text in figures) in the paper are too small. Please enlarge them.*
- L.82: What is $\mathcal{X}$?
- L218: The choice of $S_n$ as a symbol for the symmetric group is not optimal, as subsets are denoted by $S_1$, $S_2$, etc.
- L225: You mention “extension to multiple features is straightforward” and refer to [22]. A bit more explanation would be helpful.
Questions
I would appreciate it if the authors could respond to the weak points **W1**, **W4**, **W5**, and explain what they want to convey with the section on “more than a coarsening function" in Section 5.