Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: - This paper proposes F-MPNN, which extends the expressive power of MPNN whilst preserving their O(n) cost in each iteration.
- This paper provides some theoretical guarantees for F-MPNNs. 
-- It shows that F-MPNN can be at most as expressive as F-WL-test
-- It compares the expressive power between F-WL-test and k-WL-test.
- Certain improvements are shown in experiments.

main_review: Pro:
- It is a smart idea to utilize the design of the F-WL-test to design the F-MPNN, so that this type of GNN can enjoy the theoretical guarantee of distinguishing power as what the F-WL-test has.
- This method is less expensive than some higher-order MPNN in terms of the complexity in each iteration.

Cons:
- The proofs heavily depend on existing works but are not suitably mentioned in the main text. I think it is totally fine to make a statement in the main text because a novel combination of existing proof techniques is also valuable.
- As already mentioned by the authors, in practice it is hard to pre-select a suitable set of patterns since they cannot be learned by gradients. The theoretical results in Sec 4 do provide certain information but they are not enough to serve as practical guidance since the search space is just way too large.
- Experiments can be conducted more rigorously (see below).

Detailed questions for experiments:
- By adding the patterns, the dimension of the augmented node features will become larger and the model will contain more parameters. When making the comparison, have all models used the same feature dimension and the same number of parameters? This should be controlled to exclude the effect of using a larger model. (e.g., the results in Table 1 (b))
- The key baseline in this paper is the ISO in Table 1 (a). Why results of ISO are missing in Table 2 and Table 3? If one also searches the best performing pattern for ISO using the same computing cost as the search for F-MPNN, what will be the best performing accuracy for ISO on PATTERN and COLLAB?
- Except for ISO, there are several other works that also augment the initial feature with precomputed node features. Some simple ones include random feature [1], port numbering / weak-coloring feature [2], local matrix feature [3]. I noticed that these three are also cited in related work. It will be better to see a comparison to these simple augmented approaches.
- Minor question: The hyperparameters of the GNNs are not described. What's the hidden size? Number of hops? Will different choices of these hyperparameters affect the improvement from augmenting the features?

Other question:
- Although it is a one-time preprocessing stage, how is the complexity?

Summary:
- This paper provides theoretical guarantees for the proposed F-MPNN in its distinguishing power, which is valuable. However, since the theory is insufficient to provide practical guidance for choosing a suitable set of F patterns, I think the empirical experiments become important to support the claims in this paper. Therefore, my main concern is that the experiments are not convincing enough (see details above).

[1] Sato,  R.,  Yamada,  M.,  and  Kashima,  H. Random features strengthen graph neural networks.arXiv preprintarXiv:2002.03155, 2020.

[2] Sato, R., Yamada, M., and Kashima, H. Approximation ratios of graph neural networks for combinatorial problems.In Advances in Neural Information Processing Systems, pp. 4081–4090, 2019.

[3] Vignac, Clément, Andreas Loukas, and Pascal Frossard. "Building powerful and equivariant graph neural networks with structural message-passing." NeurIPS. 2020.



**After reading the response**

Thank the authors for the detailed response! I appreciate the theoretical contribution of this paper, but I still have concerns about its practical usage, without the experimental comparison to other augmented GNN models. The authors claimed that this method can extend any existing GNNs, including those augmented GNNs. However, although the paper has theoretically shown the improvement in expressiveness compared to MPNN, the improvement to existing *augmented* MPNNs [1,2,3] are unclear, which will require additional experiments to verify. Moreover, these augmented GNNs [1,2,3] and some other alternatives that use distance-based features are less expensive (pre-processing) and do not require choosing the patterns (that means fewer tuning parameters). How useful is the proposed method compared to these **simpler** methods (which also have theoretical guarantees) is unclear. This is the major reason why I choose to retain my initial score. I personally believe this will be a very nice paper if additional experiments with convincing results are provided.

limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a novel GNN framework, F-MPNN, to efficiently increase the expressive power of MPNNs. The proposed framework uses local higher-order graph parameters which are the homomorphism counts of small patterns (graph sets). The adoption of different patterns will result in different MPNNs. 

From a theoretical perspective, the expressive power of F-MPNN is characterized based on the WL algorithm, and is compared to higher-order MPNNs. Since the performance of F-MPNN depends on the selection of patterns, how different patterns affect the expressive power is also investigated.

The theoretical findings are further validated via extensive experiments with various GNNs, datasets, and graph-related tasks. The results demonstrate the promising improvements achieved by using the proposed efficient local graph parameters. 
main_review: The proposed framework successfully unifies several existing extensions of MPNNs with solid theoretical analysis. The connections and comparisons between the proposed F-MPNNs and higher-order MPNNs characterize the expressive power of related models with more insights and details. Besides, the effects of different selection of patterns on the expressive power are also investigated, which helps to better understand the power of the proposed model. 

The experiments are done with broad coverage of models, datasets, and tasks to evaluate the performance of the proposed method. The results are discussed in detail and the promising performance of the proposed methods is validated clearly.

The paper is overall well organized. However, the authors should double-check the grammar if accepted:

Line 14: aide --> aid

Line 17: effect for --> effect on

Line 161: the the --> the

Line 221: in that more --> in more

Line 222: be distinguish --> be distinguished

Line 230: less rounds --> fewer rounds

Line 368: have greatest impact for --> have the greatest impact on

Line 401: deserves --> deserve




limitations_and_societal_impact: The authors have addressed the limitations of their work in Introduction.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a theoretical framework attempting to unify a variety of recent methods in the Graph Neural Network literature, which all follow a similar conceptual approach: they introduce extra structural features in the input of the Neural Network that cannot be computed by traditional message passing. The main formalism underlying the framework is that of homomorphism, which is an adjacency-preserving mapping between two graphs. Differently from subgraph isomorphism, homomorphisms are not necessarily bijective (think of walks vs paths).  The authors define $\mathcal{F}$-MPNNs as a message passing framework where node features are enhanced with the homomorphism counts of every pattern in a collection $\mathcal{F}$. The authors derive a deep characterization of the expressive power of $\mathcal{F}$-MPNNs, both in comparison to the k-WL hierarchy and between different instantiations thereof,  show how it can incorporate other approaches, and answer numerous research questions that have been left open by the most related paper, that of Bouritsas et al., arxiv’20. The method is also validated experimentally, by enhancing GNNs with homomorphism counts of cycles and cliques, on node, edge and graph level tasks, showing consistent improvement against various conventional MPNN counterparts.
main_review: Although injecting structural features in the input of GNNs is common in the GNN community, usually, the theoretical justifications are limited in showing improvements over the 1-WL, while sometimes the structural features are chosen in an ad-hoc way. However, this paper goes much deeper in the theoretical justifications showing that homomorphisms allow a more accurate characterisation of expressivity, while most importantly, using the observation that different types of subgraph counting (motifs, graphlets, homomorphisms…) can be derived from one another via linear combinations (e.g., see  Borgs et al., “Counting Graph Homomorphisms” Topics in Discrete Mathematics, 2006), they motivate why homomorphisms can be an elegant and unifying framework.

I must admit that it is a bit hard to follow for non-experts due to the utilisation of many specialised notions in graph theory, so there is room for improvement in that respect. Specific comments follow:

**Strengths**:

- I found this paper quite useful to the community, bringing important ideas from graph theory to graph neural networks, and shedding light on many open questions in the expressive power of this class of GNNs. I also appreciate the fact that the authors are honest w.r.t. the main limitation of the work, i.e. the pattern selection.
- The paper addresses a number of open research questions described in GSNs (although not directly applicable to GSNs, the corresponding results on $\mathcal{F}$-MPNNs provide important insights to the reader):  
     - How do substructure-enabled MPNNs relate to k-WL (Proposition 2 and 3)?
     - What type of patterns grant F-MPNNs the ability to distinguish graphs that k-WL cannot (cores of treewidth k – Theorem 2; this is in agreement with the 4-clique counterexample used in the GSN paper)? 
     - In which cases can we be sure that expressivity increases when adding patterns to the collection (Propositions 4,5 and Theorem 3)? Moreover, Proposition 5 implies a compositionality property of certain patterns, i.e., when two patterns $P_1$, $P_2$ are added to the collection, expressivity increases more than by simply adding their composition $P_{1,2}$. I am still not sure though if this implies that a $\\{P_1, P_2\\}$-MPNN can count $P_{1,2}$ homomorphisms.
-	The experimental results are diverse, spanning all types of graph-related problems, showing consistent improvement against the conventional MPNN baselines.


**Weaknesses**:
-	In my opinion, the paper is a bit hard to follow. Although this is expected when discussing more involved concepts, I think it would be beneficial for the exposition of the manuscript and in order to reach a larger audience, to try to make it more didactic. Some suggestions: 
    -	A visualization showing a counting of homomorphisms vs subgraph isomorphism counting.
    - It might be a good idea to include a formal or intuitive definition of the treewidth since it is central to all the proofs in the paper.
    - The authors define rooted patterns (in a similar way to the orbit counting in GSN), but do not elaborate on why it is important for the patterns to be rooted, neither how they choose the roots. A brief discussion is expected, or if non-rooted patterns are sufficient, it might be better for the sake of exposition to discuss this case only in the supplementary material.
-	The authors do not adequately discuss the computational complexity of counting homomorphisms. They make brief statements (e.g., L 145 “Better still, homomorphism counts of small graph patterns can be efficiently computed even on large datasets”), but I think it will be beneficial for the paper to explicitly add the upper bounds of counting and potentially elaborate on empirical runtimes.
-	Comparison with GSN: The authors mention in section 2 that F-MPNNs are a unifying framework that includes GSNs. In my perspective, given that GSN is a quite similar framework to this work, this is an important claim that should be more formally stated. In particular, as shown by Curticapean et al., 2017, in order to obtain isomorphism counts of a pattern P, one needs not only to compute P-homomorphisms, but also those of the graphs that arise when doing “non-edge contractions” (the spasm of P). Hence a spasm(P)-MPNN would require one extra layer to simulate a P-GSN. I think formally stating this will give the interested reader intuition on the expressive power of GSNs, albeit not an exact characterisation (we can only say that P-GSN is at most as powerful as a spasm(P)-MPNN but we cannot exactly characterise it; is that correct?)
-	Also, since the concept of homomorphisms is not entirely new in graph ML, a more elaborate comparison with the paper by NT and Maehara, “Graph Homomorphism Convolution”, ICML’20 would be beneficial. This paper can be perceived as the kernel analogue to F-MPNNs. Moreover, in this paper, a universality result is provided, which might turn out to be beneficial for the authors as well.



**Additional comments**:
- I think that something is missing from Proposition 3. In particular, if I understood correctly the proof is based on the fact that we can always construct a counterexample such that F-MPNNs will not be equally strong to 2-WL (which by the way is a stronger claim). However, if the graphs are of bounded size, a counterexample is not guaranteed to exist (this would imply that the reconstruction conjecture is false). Maybe it would help to mention in Proposition 3 that graphs are of unbounded size?  
-	Moreover, there is a detail in the proof of Proposition 3 that I am not sure that it’s that obvious. I understand why the subgraph counts of $C_{m+1}$ are unequal between the two compared graphs, but I am not sure why this is also true for homomorphism counts.
-	Theorem 3: The definition of the core of a graph is unclear to me (e.g., what if P contains cliques of multiple sizes?)
-	In the appendix, the authors mention they used 16 layers for their dataset. That is an unusually large number of layers for GNNs. Could the authors comment on this choice?
-	In the same context as above, the experiments on the ZINC benchmark are usually performed with either ~100K or 500K parameters. Although I doubt that changing the number of parameters will lead to a dramatic change in performance, I suggest that the authors repeat their experiments, simply for consistency with the baselines.
-	The method of Bouritsas et al., arxiv’20 is called “Graph Substructure Networks” (instead of “Structure”). I encourage the authors to correct this.

-------
-------
### After rebuttal

The authors have adequately addressed all my concerns. Enhancing MPNNs with structural features is a family of well-performing techniques that have recently gained traction. This paper introduces a unifying framework, in the context of which many open theoretical questions can be answered, hence significantly improving our understanding. Therefore, I will keep my initial recommendation and vote for acceptance. Please see my comment below for my final suggestions which, along with some improvements on the presentation, I hope will increase the impact of the paper.

limitations_and_societal_impact: *Limitations*: The limitations are clearly stated in section 1, by mainly referring to the fact that the patterns need to be selected by hand. I would also add a discussion on the computational complexity of homomorphism counting.

*Negative societal impact*: A satisfactory discussion is included in the end of the experimental section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes local graph parameter enabled GNNs as a framework for studying the local higher-order graph structural information. Local graph parameters can be added to any GNN architecture, and are cheap to compute. In terms of expressive power, their proposal lies in the middle of GNNs and their higher-order counterparts. Further, they propose several techniques to aide in choosing the right local graph parameters. The experimental evaluation shows that adding local graph parameters often has a positive effect for a variety of GNNs, datasets and grpah learning tasks. 

main_review: For the main part, as a resubmission from ICML, this work fixed the issues as they mentioned in the last submission. The overall quality of the current version is solid and it can deliver  the main idea of F-MPNN method. And this work can inherit the merits from arbitrary GNNs which makes the value of this method more general

For the minor part, this work still has typos and need further proof-read. For example, P2 line 51. 
limitations_and_societal_impact: Yes, this work mentions the limitations in the main paragraph
review_title: null

Meta-review: This paper unifies several classes of recently proposed graph neural network architectures via the notion of graph homomorphisms. The reviewers agree that presented theoretical framework is novel. Even more importantly, it can be successfully applied to propose new GNN architectures. The paper is well written and provides rigorous mathematical analysis of several GNN methods that were previously analyzed only empirically.
Decision: Accept (Poster)