Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes an extension of message passing GNNs that can learn approximately universal graph representations. Specifically, based on the colourings search tree method of exact isomorphism solvers, the authors suggest a differentiable approximation over the search tree by sampling multiple paths. 
main_review: Summary:\
The paper is well written and easy to follow. In my opinion, the originality of the paper is high since it is both technically rich and the empirical results are strong. Although there are other papers that have proposed models that are more powerful than 1-WL, the approach proposed in this paper is different from prior work. The model is found to be very effective in graph isomorphism testing and in the detection of graph properties, while it outperforms  the baselines on three real-world datasets. Overall, the paper seems to be proposing a novel contribution.

Theoretical Motivation:\
The paper seems to have a solid theoretical motivation. First, the authors formulate the universality of the graph representations under the framework of individualization and refinement. Then, they show how the distance of the generated embeddings is approximated by sampling a number of paths from the search tree. I am not sure though how useful the bound provided in Theorem 2 could be in practice. In most experiments, the authors have set K equal to 4 or 8. For reasonable values of M and D, a much larger K would be required such that the embeddings of two graphs are separated with high probability by some distance close to the exact distance d.

Since the model performs sampling, to my understanding, two isomorphic graphs will obtain different embeddings from each other. These embeddings might be very similar to each other, however, they will not be identical to each other. Could this be a problem for some application (for instance if nearly isomorphic graphs belong to different classes or their targets in some regression problem are very different from each other)?

Experimental evaluation:\
The authors perform an extensive empirical evaluation of PF-GNN on both synthetic and real-world tasks. In both cases, their model exhibits a strong performance on learning expressive graph representations.
- One of my concerns with this paper is that PF-GNN is mainly evaluated on synthetic datasets, while only three real-world datasets are employed in total. It is not thus entirely clear how effective the proposed model is in real-world scenarios. I would suggest the authors evaluate also the model on standard graph classification datasets such as ENZYMES, NCI1, IMDB-BINARY, REDDIT-BINARY, etc or on some graph property prediction dataset from OGB.
- With regards to the synthetic datasets, the authors could also investigate whether the proposed model can identify fundamental graph properties such as bipartiteness, connectivity and planarity (this problem has been studied in [1] in the context of graph kernels).

Minor comments:\
Please explain how the PF-GNN model is trained on the three graph isomorphism test datasets. What are the class labels of the different samples?

In Table 7, it is shown that a larger number of IR steps does not necessarily lead to a higher classification accuracy. What is the reason behind that? I would like the authors to provide some explanation.

Typos:\
"consistently outperform" => "consistently outperforms" 

References:\
[1] A Property Testing Framework for the Theoretical Expressivity of Graph Kernels. Nils M. Kriege et al, In IJCAI'18.

summary_of_the_review: The paper proposes an original contribution for the graph representation learning community. The proposed model is novel, while the paper provides some theoretical analysis of its benefits. The empirical results are strong since the PF-GNN model outperforms the baselines on almost all datasets.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a neural version of individual-refinement (IR) architecture for improving the expressiveness of GNN in terms of isomorphism test. As IR is the dominant approach of practical graph isomorphism test, adapting IR to GNN is a novel and important idea. As IR suffers from the exponential number of branches, the paper adapts particle filtering algorithm to sample K paths to approximate the full version of IR algorithm.  Simulation and real-world datasets are used to demonstrate the improvement over base GNN. 
main_review: Strengths:
1. Adapting IR to neural and GNN area is a novel and important contribution. The designed algorithm does improve over base GNNs. 
2. The particle filtering algorithm is a elegant and low-complexity realization of IR algorithm. 

Weakness:
1. Particle filtering samples K paths to approximate summation of exponential number of paths in original IR which is theoretically universal in graph isomorphism test, it's would be great to show how much expressive do the K paths keep, with changing K from 1 to K_max (like 30). Nevertheless it's hard to believe K paths are enough to cover exponential number of paths. 
2. Particle filtering assumes all intermediate observations are given but the designed algorithm doesn't have any intermediate observations. The author may need to provide further justification for this significant misalignment.  
3. A bad property for sampling method is that for two same graphs, the algorithm may judge them as non-isomorphic. This can hurt generalization ability a lot. It would be great to figure out ways to solve the issue. 
4. Although not a main issue, the theorem 2 proof seems  incorrect as the value is independent of T. Eq (22) -> Eq (23) is not clear. 
5. The major weakness is the scalability and practical complexity. The designed model is T times deeper and larger than base model, and K path sampling needs K times larger memory for parallel computation. For ZINC dataset I have run the author's implementation and it's too slow comparing with base GNN also eats too much memory. Making the proposed algorithm more practical is extremely important for larger dataset like CIFAR10. 
summary_of_the_review: Overall I think the paper deserves a weak accept: the proposed idea of generalizing IR is novel and important, however the method is still not practical enough to use, and without good theoretical theorem for the expressiveness of the designed sampling version IR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces PF-GNN, a new method through which to individualize node representations with the aim of increasing GNN expressiveness. It is inspired by graph isomorphism algorithms' individualize and refine (IR) approaches, which individualize individual nodes then refine colorings, and then aggregate all colorings across the search tree of possible individualization paths. Specifically, PF-GNN approximately emulates IR by repeating a random sampling k times and returning an aggregate coloring from each sample. For every sample, T iterations are made, such that a sample node is selected for individualization, and then representations are updated using a GNN. However, PF-GNN introduces learnable components to this mechanism, such that affinities for node selection (yielding a distribution over all possible individualization candidate nodes) are learned, rather than simple uniform sampling. Furthermore, beliefs for sampling are iteratively updated in keeping with a particle filtering approach (PF), and node individualization itself is made using a learnable function, to enable more flexibility and data-driven individualization. Finally, the model is empirically evaluated on a series of datasets and compared with existing standard GNNs and individualization techniques, e.g., random node initialization (RNI). In these experiments, PF-GNN is shown to improve model expressiveness, is more resilient than RNI for larger numbers of nodes, and achieves strong performance on real-world datasets.
main_review: The paper introduces a novel, principled means to perform individualization, inspired by IR approaches within graph isomorphism solvers. Moreover, it conducts an extensive empirical analysis to evaluate its claims, and its reported results confirm the value of sequential sampling and highlight the strength of the model. Furthermore, this approach, much like random node initialization, can easily be applied across standard GNNs, which makes it relevant across the GNN community. Finally, the paper is clearly written and its main approach is well-presented. However, I have some concerns regarding the novelty and significance of the approach, which I enumerate below: 

- The paper clearly explains and motivates its particle filtering mechanism, as well as its inspiration by IR. It also performs ablations on its individualization distributions and on its loss to highlight their significance. However, the paper does not consider ablations on its individualization method (via an MLP), or the means of inidividualization (partial or full randomization/individualization, as is studied in random node initialization works). This leaves a rather large gap between random node initialization and PF-GNN, from which any one (or many) distinguishing factors could be key contributors to the observed experimental differences. To illustrate, the difference between RNI and PF-GNN could mostly stem from sampling one node per iteration rather than all nodes initially, or it could stem from the learnable nature of the individualization in PF-GNN, as opposed to the fully randomized initialization in RNI (where the choice of initial distribution could also play a part). It could also be that partial RNI yields better performance as it preserves some deterministic information, as has been observed in Abboud et al (2020). Hence, it is not at all clear how or why PF-GNN achieves these improvements at present, and thus it is not sound to attribute these improvements solely to the PF mechanism and its data-driven approach based on current evidence. 
- As mentioned earlier, the paper only compares with fully randomized RNI. This is not a fair comparison, in my opinion, as fully random RNI has no deterministic information to build on, whereas PF-GNN, by nature, preserves all but one node's features at any given iteration. Therefore, the paper should also consider partial RNI (at different percentages of randomization), where only a fraction of node embeddings is randomized, so as to better appraise the contributions of PF-GNN.
- The paper claims that PF-GNN enables better performance on real-world datasets, but does not use any standard benchmarks to validate this point. Hence, the authors should consider running experiments on standard benchmarks, such as those in OGB [1], to further corroborate this point.

[1] Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020.

summary_of_the_review: The paper proposes PF-GNN, an interesting addition to the literature on individualizing GNN node embeddings which demonstrates strong empirical performance. However, the value of the approach cannot be fully established, as the gap with existing methods is very large, implying that multiple factors (e.g., randomization techniques, initialization choices) could also be responsible for the performance improvement, rather than the proposed approach. Moreover, further evidence and experiments is required to validate the strength of PF-GNN over real-world data. Hence, the authors should conduct further experiments with intermediate randomization and individualization choices, and evaluate PF-GNN on standard benchmarks, to better quantify the impact of their proposed approach and confirm its significance. 

DISCUSSION UPDATE: Rating increased from 5 to 8 following additional experiments (details in review replies).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose PF-GNN for graph-level tasks. Their design is based on exact isomorphism solver. They propose sampling process with particle filter updates to alleviate the high complexity issue.
main_review: ## Pros:

(+) The design and results are theoretically sound.

(+) The empirical results show that PF-GNN outperforms many existing GNN methods on various graph-level tasks.

## Cons:

(-) The clarity of the paper can be improved for non-expert readers.

## Detail comments:

I am not an expert in the graph isomorphism test and particle filter approach discussed in the paper. So, it is quite likely that I do not fully understand all the details. I get the high-level idea that the individualization approach improves the 1-WL test by breaking the symmetry. The experiment results demonstrate the superior performance of PF-GNN. Overall, I think it is a good paper, but the clarity and the way the authors explain their approach can be more friendly to non-expert readers.

One question that I have is that how PF-GNN performs compare to the standard graph isomorphism solver mentioned by the authors (such as Nauty and Traces?). Since PF-GNN is designed based on the IR approach, I would like to see such a comparison as a sanity check of whether we should use GNN-based approaches or just standard solvers. I understand that the embedding of GNN can be used for various downstream tasks and is not restricted to graph isomorphism tests. Yet such a comparison is desirable.

Finally, I notice that the authors demonstrate the time complexity for SR25 datasets compared to their backbone. However, I wonder what is the time complexity of PF-GNN on the other tasks and datasets such as ZINC, ALCHEMY, and QM9. How is the exact running time of PF-GNN to achieve those superior results in these datasets?

summary_of_the_review: The paper is theoretically sounded and the empirical performance of PF-GNN is impressive. Still, I think the explanation can be improved and I also have some regarding the experiment. Together I lean to vote for acceptance of this paper.
review_title: null

Meta-review: This paper presents a neural version of individual-refinement (IR) architecture for improving the expressiveness of GNN in terms of isomorphism tests. As IR is the dominant approach of practical graph isomorphism tests, adapting IR to GNN is a novel and important idea. As IR suffers from the exponential number of branches, the paper adapts particle filtering algorithms to sample K paths to approximate the full version of the IR algorithm. Simulation and real-world datasets are used to demonstrate the improvement over base GNN.

Strengths: 
+ The paper is well written and easy to follow. 

+ The originality of the paper is high since it is both technically rich. Adapting individual-refinement (IR) to Neural and GNNs is a novel and important contribution. The designed algorithm does improve over base GNNs.

+ The particle filtering algorithm is an elegant and low-complexity realization of the IR algorithm.


Weaknesses:

- PF-GNN is mainly evaluated on synthetic datasets, while only three real-world datasets are employed in total. It is not thus entirely clear how effective the proposed model is in real-world scenarios. The authors added a new real-world dataset, OGB-molhiv, during the discussion period. 

- The major weakness is the scalability and practical complexity. The designed model is T times deeper and larger than the base model, and K path sampling needs K times larger memory for parallel computation. Although the reviewers still have some concerns, such as “sampling method may judge isomorphic graphs as non-isomorphic”, the reviewers appreciate the author’s hard work on partially addressing the problem during the discussion period. We encourage the author to continue to improve the paper along this direction.
Decision: Accept (Poster)