PF-GNN: Differentiable particle filtering based approximation of universal graph representations
Authors: Mohammed Haroon Dupty
Yanfei Dong
Wee Sun Lee
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
Graph representation learning
Expressive GNN

Abstract: Message passing Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. Other more expressive models either are computationally expensive or need preprocessing to extract structural features from the graph. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques which operate on the paradigm of $\textit{Individualization and refinement}$ (IR), a method to artificially introduce asymmetry and further refine the coloring when 1-WL stops. Isomorphism solvers generate a search-tree of colorings whose leaves uniquely identify the graph. However, the tree grows exponentially large and needs hand-crafted pruning techniques which are not desirable from a learning perspective. We take a probabilistic view and approximate the search tree of colorings ( i.e. embeddings) by sampling multiple paths from root to leaves of the search-tree. To learn more discriminative representations, we guide the sampling process with $\textit{particle filter}$ updates, a principled approach for sequential state estimation. Our algorithm is end-to-end differentiable, can be applied with any GNN as backbone and learns richer graph representations with only linear increase in runtime. Experimental evaluation shows that our approach consistently outperforms leading GNN models on both synthetic benchmarks for isomorphism detection as well as real-world datasets.

Published as a conference paper at ICLR 2022
PF-GNN: DIFFERENTIABLE PARTICLE FILTERING BASED APPROXIMATION OF UNIVERSAL GRAPH REP- RESENTATIONS
Mohammed Haroon Dupty', Yanfei Dong Wee Sun Lee
1 School of Computing, National University of Singapore PayyPl Innovation Lab [dmharoon, dyanfei, leews @comp. nus. edu.sg
ABSTRACT
Message passing Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refimement test for graph isomorphism. Other expressive models either are computationally expensive need preprocess- ing to extract structural features from the graph. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques which operate on the paradigm of Individualization and Refinement (IR), a method to artificially introduce asymmetry and further refine the color- ing when 1-WL stops. Isomorphism solvers generate a search tree of colorings whose leaves uniquely identify the graph. However, the tree grows exponentially large and needs hand-crafted pruning techniques which are not desirable from a learning perspective. We take a probabilistic view and approximate the search tree of colorings (i.e. embeddings) by sampling multiple paths from root to leaves the search tree. To learn more discriminative representations, we guide the sampling process with particle filter updates, principled approach for sequential state estimation. Our algorithm is end-to-end differentiable, can be applied with any GNN backbone and learns richer graph representations with only linear increase in runtime. Experimental evaluation shows that our approach consistently outperforms leading GNN models on both synthetic benchmarks for isomorphism detection as well as real-world datasets.
INTRODUCTION
In recent years, Graph Neural Networks (GNNs) have emerged as learning models of choice on graph structured data. GNNs operate on a message passing paradigm (Kipf & Welling 2016 Defferrard et al. 2016 Veličković al. 2017 Gilmer et al., 2017), where nodes maintain latent embeddings which are updated iteratively based on their neighborhood. This way of representation learning on graphs provides the necessary inductive bias encode the structural information of graphs into the node embeddings. The process of message passing in GNNs is equivalent to vertex color-refinement procedure or the I-dimensional Weisfeiler-Lchman (WL) test used distinguish non-isomorphic graphs (Xu et al. 2018; Morris et al. 2019). Consequently, GNNs suffer from the limitations of 1-WL colneeefnmmmetnn in their expressive power.
In each step of 1-WL refinemefin,,,n,, two vertices get different colors if the colors of neighboring vertices are different. The procedure stabilizes after a few steps when the colors cannot be further refined. Due to the symmetry in graph structures, certain non-isomorphic graphs induce same colors upon 1-WL. refinement. Higher-order WI. refinement and their neural k-GNN versions break some of the symmetry by operating on k-tuples of nodes. They increasing computation time and hence, are not practical for large Motivated by the fact that a fully expressive graph representation learning model should be able to produce embeddings that can distinguish any two non-isomorphic graphs (Chen et al. (2019b), we turn to exact graph isomorphism solvers for better inductive biases in our learning algorithm.
expressive but require exponentially
Most of the practical graph isomorphism solvers use 1-WL in combination with the traditional technique of individualization and refinement (IR) (McKay Piperno! 2014 Junttila & Kaski 2011)

---

Published as a conference paper at ICLR 2022
for coloring the graph. Individualization is the process of artificially introducing asymmetry by recoloring a vertex and thereby, distinguishing it from the rest of the vertices. Refinement refers to 1-WL refinement which can propagate this information to recolor the rest of the graph. The two graphs shown in Fig. aare not distinguishable after 1-WL. refinement but induce different colorings after one IR step. The IR process is repeated for each refinement until every vertex gets a unique color. However, in order to maintain permutation-invarianee whenever a vertex is individualized, other vertices that have the same color need individualized well and thereafter refined. This process generates search tree with colorings as nodes, and can grow exponentially in worst case.
In this work, we propose to learn graph representations with the induc- tive bias of the search tree generated by the graph-isomorphism solvers. However, generating the complete search tree is computationally ex- pensive. Isomorphism-solver prune the search tree by detecting automor- phisms on the fly as they generate the tree. Nevertheless, detecting automorphisms is non-trivial from the perspective of end-to-end dis- criminative learning and hence, we need to approximate it. To this end, we first define a universal neural graph representation based on the search tree of colorings. Then we take a probabilistic view and approximate it by sampling multiple paths from root to leaves of the search tree. We observe that the process of sampling a vertex, individualizing and the subsequent refinement resembles the state transition in sequential state estimation problems. Hence, we model our sampling approach on the principled technique of Sequential Monte Carlo or Particle Filtering.
Figure 1: Two I-WL equivalent graphs with different color- ings after one step of individualization and refinement.
We introduce Particle Filter Graph Neural Networks (PF-GNN), an end-to-end learnable algorithm which maintains weighted belief distribution over set of K graph colorings/embeddings With each step of IR, PF-GNN transitions to a new set of embeddings. It then updates the belief by re-weighting each particle with a discriminatively learned function that measures the quality of the refinement induced after the transition. With this inductive bias, the belief evolves over time to be more discriminative of the input graph. After a few steps, we can use the belief along with the embeddings to generate the final representation of the graph. Our approach is simple, efficient, parallelizable, easy to implement and can learn representations to distinguish non-isomorphic graphs beyond 1-WL GNNs. We evaluate PF-GNN over diverse set of datasets on tasks which are provably not learnable with 1-WL. equivalent GNNs. Furthermore, our experiments on real-world benchmark datasets show the strong performance of PF-GNN over other more expressive GNNs.
2 RELATED WORK
It was established that GNNs are limited in expressive power, and cannot go beyond 1-WL test for graph isomorphism by Xu et al. (2018) and Morris et al. (011).. Later analysis of GNN has shown other limits of GNNs like counting substructures and detecting graph properties (Arvind et al. 2020 Chen et al. 2020 Loukas 2019: Dehmamy et al. 2019 Srinivasan & Ribeiro 2019). Chen al. (2019b) further formalizes the intuition that there equivalence between learning universal graph representations and solving the graph isomorphism problem. Thereafter, many models have been proposed that are more expressive than I-WL. Prominent ones are k-GNNs and their equiv- alent models (Morrs et al. 2019 Maron et al. 2019 Vignac et al. 2020 Morris et al.) 2020). but they are difficult to scale beyond 3- WL. Other methods need to preprocess the graph to find
substructures (Bouritsas et al. 2020 Li et al. 2020 which are not task-specific and may incur more computation time.
Another way to improve expressivity of GNNs is to introduce randomness You et al., 2019: Sato ct al., 2020) Abboud et al. 20200 Zambon et al., 2020). However, adding uniform randomness interferes with the learning task, and hence these models have not shown good performance on real-world datasets. In PF- FNNN randomness is controlled as only a subset of nodes are sampled. Furthermore, since all components are learned discriminatively, the representation is tuned towards the end task. Our approach of learning with particle filter updates is inspired from recent works which make particle filters differentiable (Karkus et al. 2018 Ma et al. 2019. 2020).
2

---

Published as a conference paper at ICLR 2022
3 PRELIMINARIES
Let G be the set of all graphs of vertices with vertex set V 21, and edge set &, Isomorphism between any two graphs G. H E G,, a bijection f: V/g Vu such that (u, v) E &g > (f(c), f(u)) E Ex, An automorphism of G is isomorphism that maps 9 onto itself. One way of identifying non-isomorphic graphs is by generating unique colorings for graphs based on their way and then, comparing them.
structures in permutation-invarte
colouring of the graph 9 E G. is a surjective function π V - N, which assigns each vertex to a natural number. The number of colors is denoted by |.]. The set of vertices sharing the same color form a color cell in the coloring. We denote the set of colored vertices with л = {PI. P2..... .p.) where p, is color cell. A coloring in which every vertex gets distinct color is called discrete colouring i.e. ||| = n. For any two colorings :. π we say that n' is finer than or equal to 9, written T' n, if 7 (v) T (w) + T (v) n' (w) for all v,
V. i.e. each cell of nt is subset of a cell of æ, but the converse is not true. Coloring is also loosely called partition, since it partitions V into cells. A coloring an equitable partition when any two vertices of the same color are adjacent the same number of vertices of each color.
1 I-dimensional Weisfeiler Lehman test is simple and fast procedure to color graphs. It starts with the same initial color for all vertices. Then, it iteratively refines the coloring of the graph by mapping the the tuple of the color of vertex and its neighbors a distinct new color. ie at step t,
(v) HASH (v), (m), M(e) where } denotes multiset and N(v) is the set of adjacent vertices of v. The algorithm terminates when æ forms an equitable partition.
3.1 SEARCH TREE OF COLORINGS
Equitable coloring cannot be further refined due to the symmetry in the graph structure. To break the symme- try. exact isomorphism solvers employ the technique of individualizaaioo-reeee refnemmmnn to generate further refined colorings. Individualization is the technique of breaking the symmetry in the graph by distinguishing a vertex with new unique color. Once vertex is individualized, 1-WL refinement is used to refine the coloring until a further re- fined equitable partition is reached. However, this comes at a cost. In order to maintain permutation permutation-ivvariance we have individualize and refine all the vertices with the same color. As a result, we get as many refined colorings the number of vertices with the chosen color. This pro- cedure can be repeated iteratively for each of the refined coloring and the process takes shape of rooted search free of equitable colorings.
Figure 2: An example search tree of color- ings generated by exact graph isomorphism solvers. Initial coloring produced 1-WL refinement. PF-GNN approximates the by sampling multiples paths from root to leaf.
The search tree has initial 1-WL. coloring at the root. Then non- con-singleton color cell called the target cell is chosen and all vertices of the target cell are individualized in parallel and thereafter, colorings are refined. The refined equitable colorings form the child nodes the root. After sufficient repetitions, we get set of discrete colorings at the leaves. This search tree is unique to the isomorphism class of graphs, i.e. all non-isomorphic graphs produce distinct search trees, and consequently, discrete colorings at the leaves. An example of search tree is shown in Fig.
PROPOSED METHOD
In this section, we first define a universal representation of any n-vertex graph, then propose a practical approximation of the representation.
For any arbitrary n-vertex graph G, we aim to learn its neural representation f(G) that can uniquely construct computation graph which mimics the search tree of
identify G. To achieve this, colorings. We propose to design a neural equivalent the search tree. To do this, we can model the target-cell selector using learnalle function that outputs scalar scores the vertices based
3

---

Published as a conference paper at ICLR 2022
on their embeddings, and then individualize those which have the maximum score. Note that node embeddings in GNN are analogous to colors in 1-WL refinement. We can then adopt GNN to produce refined set of embeddings. If we have discrete embeddings after T iterations, then f(G) can be computed as,
p = p <> E GG (T.TTT)
where Z is sequence of vertices individualized iteratively ( [I identifies single path from root to leaf in the search tree) and the summation is over all such paths. σ is the discrete coloring (discrete embeddings) of G after individualizing and refining with vertices in &b is an multiset function approximator and p is an MLP. Theorem presents the expressive power of ((g).
Theorem 1. Consider any n-vertex graph 9 with no distinct node altributes. Assume we use universal multiset function approximators for target-cell selection and graph pooling function 1h, and a GNN with 1-WL equivalent expressive power for color refinement, then the representation fG) in Eqn. permutation invariant and can uniquely identify G.
arrnutation-nvvariant
Proof of Theorem iss provided in Appendix A.3
4.1 PROBABILISTIC REPRESENTATION
The graph representation in Eqn. D is computationally expensive to obtain as the size of the search tree can grow exponentially with the number of vertices. Graph isomorphism solvers like Nauty and Traces (McKay & Piperno| (2014) prune the search tree by detecting automorphisms in order to run faster. To speed up, we instead propose to approximate the representations for the set of colorings at the leaves as suggested by Theorem I [using sampling techniques, and approximate the pruning process by learning to down-weight certain subtrees.
By sequentially sampling the vertices to individualize and refine, we can get a sample set of paths/trajectories from root to leaf the search tree. To facilitate the approximation, we use the expectation of the embeddings instead of the sum of the embeddings. Assume we need T steps to generate discrete colorings. Let I be the sequence of vertices selected to individualize one trajectory from root to leaf. Then, we have the following expectation
F(G)
1 II
Σ ZENT
09 (T)
E[ m+)
where I1 is the set of all paths in the search tree. In this case, we want the E[ VG TF) to be different if the set of leaves different; function v with this property exists if the number of leaves and distinct leaf representations are bounded, e.g. if we limit the size of graphs we consider. To see this, observe that each distinct graph will have a distinct canonical embedding as one of the leaves of its search tree (McKay & Piperno 2014), and v can set one of the components of its output vector to be the indicator function of this canonical embedding. To approximate f(G), we can initialize set of K colorings and in each step, sample a vertex to individualize and refine the colorings. After multiple such steps, we average the K embeddings obtain the final graph embedding. We bound the approximation error of the sampling process in the following theorem.
Theorem 2. Assume we need D dimensional embeddings for some D >> O. in order to uniquely represent any graph of n-vertices. Consider two n-vertex graphs G1 and G2 whose universal representations in Eqn. Mare J1 and J2 after T levels of the search tree. Let the max-norm distance between Ji and J2 be al least d i.e generating the full level-T search tree for both graphs will separate them by d. Assume that the values in embeddings generated by the tree are strictly bounded in the range of I-M M). Then, with probability of least 6, the approximate embeddings. generated by sampling K paths from root to leaves, are separated in max-norm distance by d + provided the number of root leaf paths sampled are at least
(
M In AD
K KEO
2
The proof is provided in Appendix A.3 Further refinement of the method can be made in practice. First, we learn the function used select the node for individualization so that it is adaptive the
4

---

Published as a conference paper at ICLR 2022
end-task. Additionally, the learned function may select different nodes with different probabilities. so the probability of each path down the tree is different. To speed up, practical solvers prune subtrees when they are unlikely to be helpful. We propose to approximate this process by learning how to de-emphasize certain subtrees using particle filter methods as described in the next section.
4.2 PARTICLE FILTER GRAPH NEURAL NETWORK
Particle Filtering: Partiele filtering is monte-carlo technique that sequentially estimates the posterior distribution of the state in non-linear dynamical systems when partial observations are made. Consider a process where we receive an observation o at each time step when it transitions from state Ie to new state I++1 and we have a transition model ((1++1/re)) an observation model p(or (2+) and a sequence of observations [01, distribution of p(ær) (trr)) by maintaining a belief over the state space with set of particles and their corresponding weights. The belief 6(x;) is given by (a w() ==)k= where Ee=1: w = 1.
or]. Then particle filters can approximate the posterior
At every time step I, each particle transitions to a new state w/+1 by sampling from p(
(=t)). We then receive an observation o and the conditional likelihood of o++1 is multiplied with the weight we before normalizing the weights i.e. wf+1 = p(o += w where 1j is the normalizing factor. Usually, the belief update is followed by resampling step where new set of particles are sampled from the distribution of (wf+1) and the weights are reset to // This step handles the problem of particle degeneracy i.e. when most weights are nearly zero. It helps in concentrating on most promising particles. Refer to the Appendix for detailed explanation.
Belief of graph colorings: The task of estimating the expected coloring of a graph G in Eqn. highly resembles the problem of state estimation in particle filtering algorithm. If we consider a graph coloring state, then sampling vertex from distribution, individualizing it and refining the graph coloring can be seen as a stochastic transition from one state to the next. We do not receive a separate observation after every transition. Instead, we use a function of the current graph embeddings to up-weight or down-weight each particle in order to approximate the pruning of non non-promising subtrees. The function is akin to unnormalized observation likelihood p(oc=1| 1) in particle filters.
Specifically, we approximate the expectation in Eqn. 2 with set of is particles and the associated set of weights which form a belief distribution over the set of particles.
(g) ~ (G, ) wx") k=
(3)
The belief (G) at time step / approximates the posterior distribution over the set of colorings of graph G. At each f, we update the belief with a stochastic transition of colorings. and the weights with an observation function. We further do resampling to focus on and expand the most promising colorings. Finally, we compute the mean coloring from the belief which gives an estimate of Eqn. 2 Note that each step can be computed in parallel for all particles and the whole process is discrimnnaivvel trained end-to-end. We call our model Particle Filter- Graph Neural Network (PF-GNN) and give the pseudo-code in Algorithm D Next, we describe the main steps of the algorithm in detail.
Initialization: We first initialize the node embeddings with node attributes or with constant value when attributes are not present. Then, we run 1-WL equivalen GNN for fixed number of iterations of the graph. Next, we instantiate our belief with i copics
to get the initial coloring/embeddinggg of the embeddings along with uniformly distributed weights ie Vk, wt = 1/K. Our belief after initialization is then ((g. HF), w/) k=1K,, where H represents the n x matrix of node embeddings of the 4hth partiele time step 1.
Transition step: In the transition step, for each particle, we pick a vertex, individualize it and refine the coloring. For this, we learn a policy function H( 0) which is discrete distribution on the set of vertices conditioned on the node embeddings H This can be modeled either as a separate GNN or an MLP on node embeddings, which gives non non-negative score for each vertex. We can then normalize the scores and sample a vertex from the distribution. Next, we individualize the sampled vertex by transforming its embeddings with another parameterized MLP. In this way, recoloring of vertices is also learnt from the data. Now that the symmetry in the recolored graph is broken, we refine the embeddings H with a GNN for a fixed number of iterations. This is repeated for every particle to get new set of particles (H (H Specifically, the transition step involves:
4~ P(V H
(4)
M =11 M u.: MLP trans (hor); H = H. @ M
(5)
5

---

Published as a conference paper at ICLR 2022
=
(6)
where M is a mask matrix of ones. Since we are operating on a set of l particles, we need to share GNN parameters across the k transitions. However, we are free to use separate GNN parameters for each step 1. Also, it means increasing the number of particles does not lead to increase in parameters.
Particle weights update step: In particle filtering, an observation is received after every transition. Then an observation function is applied to estimate the likelihood of the observation, which will be used to update the particle weights. In our case, since the new information (or observation) is contained in the refinement, we model the observation as a latent variable conditioned on the refined coloring. learnable observation function fots 1 ( is used to measure the value of the refined embeddings. Specifically, sabs (H 0n) is a set function approximator which outputs a non neg-negatvve score the set of node embeddings. The output of fobe is then multiplied with the weights wf, and the set of weights are normalized to get the updated distribution over colorings.
fobol 1 w
w = Σx Sane (H 0o) w
Note that in the absence of intermediate observations, following Ma al. (2020), we have used a discriminative function fab. (H ) to up/down-weight the state. Since is discriminatively trained to optimize the end task, it performs the same function p(o]s) in partiele filters.
Resampling step: A crucial step in the particle filter algorithm is the resampling operation. The weights of most particles tend to degenerate (i.e., become near zero). To overcome this, need to resample K new particles from the discrete distribution of 1)<+1))=1:K and set their weights to 1/K. Since this is non-differentiable operation, we adopt the differentiable soft-resampling strategy proposed in Karkus et al. (2018). Specifically, we sample new particles from the convex combination of particle weights and uniform distribution i.e., (:(k) aw, + (1 (1-40 a)1/K, where [0, is tunable parameter. The new weights can then be computed by importance weighting, (k))
whth = (k) +w /l/K where (k))) is the weights distribution. This is a differentiable approximation which provides non-zero gradients for the full particle chain with trade off between desired sampling distribution (a = 1) and the uniform sampling distribution (a = 0).
catduualizzatio--ffinneeee over the set of k particles, we have the belief ((G, H w k==kk= We can then adopt sufficiently expressive function over the belief as it a probability distribution on the set of embeddings. Ma al. (2019) proposed Moment Generating Function (MGF) features to readout. However, we found that they are numerically unstable in our experiments. Hence instead, we take the mean particle Ex=1ix H for all t (I...., T) and concatenate the embeddings before readout for the final prediction.
Readout: After T iterations of
Training: We introduced randomness in two parts of our algorithm, one where we sample for indi- vidualization, and the other during resampling of weights. Since our resampling step is differentiable, we only need to optimize the expected loss under P(I), which gives us a REINFORCE type gradient update along with task-specific loss. Let ÿ be the prediction, y the target and I be the sequence of vertices individualized, then the expected loss over K such sequences is,
Loss(G,v) = Σ = (4
(8)
I
and the gradient of the expected loss Losss(G. y) = Σ (1 + Σ
V log P(I|g,
9: (9)
I
On the number of paths needed to get good embeddings with less variance: Since PF-GNN is a sampling based approach, we would want a small number of paths (K) to represent the search- tree with less variance. We now discuss how PF-GNN can generate good embeddings with small K. Firstly, K can be small whenever most colorings are repeated each level of the tree due to the presence of automorphisms in the graph. For example, in Figure 2, all the leaves are rotated versions of the same coloring. Exact isomorphism solvers find automorphisms as well as less promising subtrees on the fly and prune the search-tree. This pruning is approximated in PF-GNN by re- weighting with observation function followed by resampling. Furthermore, our individualization function is learnt end-to- end and will adapt to reduce variance if helps the end performance. Finally, we can tune T (which may increase variance) and K (which reduces variance) to fit the dataset for optimal performance.

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
We evaluate PF-GNN on a set three separate experiments i.e. i.e.raph isomorphism test, graph property detection and real world datasets, Our experiments are up first evaluate the expressivity of PF-GNN and then to compare with other leading GNN models on real world datasets.
5.1
GRAPH ISOMORPHISM DETECTION
Table I: Accuracy on graph isomorphism-test for SR25 and EXP datasets after training 100 epochs.
DATASET
MODEI
CHERNET
PPGN (3-WL)
GNNML3
GCN
GAT
GIN
GNNMLI
SR25
BACKRONE
0.0
0.0g0.0
0.0g0.0
0.0as..
0.0=0.o
0.0:0.0
0.0
+PF-GNN
100.0=0.0
100.0=0.0
100.0:0.0
100.0:0.0
EXP
BACKBONE
0.0.0..
0.0g0.0
100.010.0
0.0
0.0g0.0
0.0.000
0,0
+PF-GNN
100.020.0
100.0:0.0
100.0:0.0
100.0:0.0
Table 2: Graph classification accuracy on the CSL dataset. indicates the backbone model.
GCN
GAT
GIN'
RING-GNN
RP GIN
3. WL GNN
PF-GNN
10
10
37.6
97.8
100.0
MEDIAN
10
10
10
43.3
100.0
MAX
10
10
10
10
53.3
100.0
100.0
MIN
10
100.0
STD
0
0
12.9
10.9
0
We first evaluate the expressiveness of PF-GNN on three graph isomorphism test datasets. 1) SR25 (Mckay] (021). The task is to distinguish all 105 pairs of non-isomorphic strongly regular graphs, which are one of the hard class graphs for the graph isomorphism problem. 2) EXP (Abboud) et al. (0020) consists of 600 pairs of non-isomorphic graphs. For both SR25 and EXP, we train the models with all graphs and test whether the models can learn embeddings that distinguish each pair. Following Balcilar et al. (202I). we use 3-layer models for all the backbones. We run experiments with 10 different seed and report the average accuracy and standard deviation. 3) CSL (Murphy et al., 2019) consists of 150 4-regular graphs divided evenly into 10 isomorphism classes. The task is to classify the graphs into isomorphism classes that can only be accomplished by models with higher expressive power than I-WL. As in Dwivedi et al. 20200) Murphy et al. (2019) we follow 5-fold cross validation for evaluation.
PF-GNN is method that can be easily applied with any GNN backbone. In Tab. compare the isomorphism detection results for models with and without PF-GNN, including GCN Kipf & Welling 2016). GAT (Veličković et al., 2017). GIN (Xu al. 2018) and GNNMLI (Balcilar al.] 2022)) These models are known to be at most 1L, and are expected to fail in the task. After augmenting these models with PF-GNN, most of them can achieve 100% accuracy. We further evaluate our method against several strong and more expressive models such as PPGN (Maron et al.] 2019).
GNNML3 (Balcilar et al., (02T) in Tab and Ring-GNN (Chen et al. 2019b). RP-GNN (Murphy al. 2019) and 3-WL GNN (Dwivedi al. 2020 in Tab. for the CSL dataset. As shown in Tab. and Tab. 2, our proposed method consistently outperforms them experimentally. Note that PPGN equivalent to 3-WL in expressive power. Interestingly, PF-GNN outperforms both PPGN well as recently proposed GNNML3 on SR25 dataset. This shows that PF-GNN is able to distinguish graphs which even 3-WL equivalent models are not able to distinguish. Note that our setting differs from Balcilar et al.
2021 where there is no learning and PPGN gets 100% accuracy for EXP dataset.
5.2
GRAPH PROPERTIES:
Table 3: Classification accuracy on LCC and TRIANGLES datasets.
In this experiment, we evaluate PF-GNN on two property detec- tion tasks where 1-WL GNNs fail. One is counting the num- ber of triangles in TRIANGLES dataset (Knyazev et al.) 2019) and the other is finding the node
RNI
DATASET
TEST SET
GIN GAT CHESNET
12.5%
50%
$7.5%
KNI PF-GNN
LCC
N
50
50
50
83
83
82
82
100
X(LARGE)
50
50
50
86
90
89
100
TRIANGLES
ORIG
47
50
64
49
52
54
59
99
LARGE
27
31
72
clustering co-efficient in LCC dataset (Sato et al. 2020 TRIANGLES (Knyazev et al. 2019) is
7

---

Published as a conference paper at ICLR 2022
Table 4: Graph regression performance on ZINC 10K and ALCHEMY 10K datasets.
DATASET
EDGE-FEAT
MUTRIC
GINE-E
2-WL-GNN
6-2-GNN
6-2-LGNN
PNA
DGN
PF-GNN
ZINC
YES
MAE
0.278
0.399
0.374
0.306
0.187ama.
0.168
0.122
No
MAB
0.320
0.219
0.196.mm
ALCHEMY
YES
MAE
08155mmm
0.149
0.118
0.122
0.162
0.111
YES
LoGMAR
-1.864
-2
-2.033
-2.66
Table 7: Graph classifi- cation on ogbg-molhiv,
Table 6: Error ratio on chemical accuracy on 12 QM9 targets without using node position features.
ROC-AUC
Ace
ma
alpha
HOMO
LUMO
gAp
ZPVH
GIN
75.58
R-GUN
3.21
4.22
1.45
1.62
2.42
16.38
17:40
7.82
8.24
9.05
7.00
3.93
GCN
76.06xoom
R-GIN
2.64
4.67
1.42
1.50
2.27
15.63
12.93
5.88
18.71
5.62
5.38
3.53
PNA
79.05 cus
GNN-FiLM
2.38
3.75
1.22
1,30
1.96
15.59
11.00
5.43
5.95
5.59
5.17
3.46
DGN
79.70samm
PR-GNN
2,06
1.57
1.52
12.76
3
0.9748
0.9747
1.76
Directional GSN
80.39
PF-GNN
80.15
large synthetic dataset with 45000 graphs. The task to count the number of triangles in each graph. LCC dataset (Sato et al. 2020) has graphs with nodes labeled with their local clustering co- co-efficient. TRIANGLES has 10 graph-Ievel classes and LCC has classes at node-level. Both datasets have two different test sets. The test sets Large and X for TRIANGLES and LCC respectively come with graphs with nearly 100 nodes whereas the training set has less than 25 nodes. Better prediction in these test sets suggests that the model is able to generalize better.
Our baselines are 1-WL GNNs, Chebnet and RNI (Sato et al. 2020 Abboud et al. 2020). RNI is 1-WL GNN but with randomly initialized node features which makes it universal approximator graphs. We also compare with RNI on partial levels of individualization as in Abbood et al. (2020). The empirical results in Tab. show that PF-GNN outperforms all RNI models as well as more expressive Chebnet on both datasets. The difference is more evident in TRIANGLA EES-Large where the baselines are not able to generalise graphs with more nodes. Comparison with RNI suggests that learning the subset of nodes to individualize is helpful for generalization towards the end-task.
5.3 REAL WORLD BENCHMARKS
We now evaluate PF-GNN on various real-world benchmark datasets including ZINC (Jin et al. 20iveDwivedi Ramakrishnan et al. 2014) and Ogbg-molhiv (Hu et al.) 2020). For ZINC and ALCHEMY, we use the fixed training set of 10K graphs and 1K graphs each for testing and validation. QM9 dataset consists of nearly 130000 graphs. As is the standard practice, we use the 10K each for testing and validation, and rest of the graphs for training. For egbg-molhiv (Hu et al. 2020). we use full 9-dimensional node features and adopt the standard scaffold split. We report mean absolute error for the former three datasets, and ROC-AUC for ogbg-molhiv. Details are in Appendix (..555
2018, Dwivedi et al. 2020). ALCHEMY (Chen et al. (0T9a) and QM9 (Ruddigkeit et al. 2012
For ZINC, compare with neural k-WL and their sparse ver- sions (Morris et al. 2020) along with other recent models including PNA (Corso et al., 2020), DGN (Beani et al. 202I). For Alchemy, we compare with sparse k-GNNs. Scores of PNA on Alchemy are reported by running their open source code. Tab. shows consistent improvement of error rates in both Zine and Alchemy datasets. In both the datasets, PF-GNN shows strong performance in comparison to all reported models.
Table Mean absolute error on jointly trained QM9 targets w/ position coordinates.
Data set
QM9
GINE-
0,081 is::
MPNN
0,034
1-2-GNN
0.068
1-3-GNN
0,088
1-2-3-GNN
0.062
For QM9, we compare with most of the strong baselines including sparse k-GNN, 3-IGN (Maron et al. 2018) and Dimenet (Klicpera et al. 2020 Tab. 5 we report MAE scores averaged over all 12 targets. PF- GNN achieves best performance compared to all the baseline models. Note that in this setting all targets are jointly trained and include position co-ordinates used either as node or edge features. It has been observed that QM9 results strongly correlated with positional features (Klicpera et al. 2020). This not an appropriate setting to evaluate PF-GNN, as the main motivation of PF-GNN identify nodes without distinguishing features. Therefore, also report
3-IGN
0,046 sam
6.2-LGNN
0.029
Dimenct
0.019
PF-GNN
0.017
8

---

Published as a conference paper at ICLR 2022
T=1
T=2
Table 8: Ablation results of PF-GNN with different T and K. Number the left for TRIANGLESS-arre, on the right are CSL.
15
Ratio
Acc
K=1
K=2
K=4
K=8
K=16
T=1
32 60
29 660
35 160
38 60
401 .50
T=2
47 196
40193
47197
42190
47
T=3
44 494
59195
59198
67 195
69
0
T=4
42 189
43 193
47 18188
46 100
S5 15
K=1
K=2
K=4
K=8
K=16
K=32
T=8
191
33172
33182
31 185
45198 198
Figure 3: Runtime ratio of PF-GNN on SR25 dataset.
results in Tab. for the setting where positional features used. We compare with the bascline results reported in Brockschmidt (2020). PF-GNN outperforms GNN-FiLM (Brockschmidt 2020) in most of the targets. For Oghg-molhiv, compare with some of the strong baselines including GCN, GIN, PNA, DGN and GSN (Bouritsas et al.) 2020). In Tab. 7 we report ROC-AUC scores which shows PF-GNN achieves competitive performance against the baselines.
5.4 ABLATION STUDIES
Performance: We first run ablative experiments of PF-GNN with different number of IR steps (7) and number of particles (K). As presented Tab. g best performance is achieved for TRIANGLES- large at T 3 and K 16, and for CSL at T 4 and K = 8. Note that single IR layer is insufficient to reach the best performance on both TRIANGLES-large and CSL datasets. Subsequent addition of IR steps is beneficial up few rounds but negatively impacts the performance on the end task after T 4 for these two tasks. This is not the case for the number of particles K. With higher K, the score either improves remains the same. This empirically verifies that higher number of samples help in better approximation of the true expectation the embeddings.
Table 9: Effect of resampling and policy
We further study two ablative models of PF-GNN, 1) with- out resampling updates and 2) training without the policy gradient loss. Tab. 9 shows that the test performance of PF-GNN on TRIANG TRIANGLSS-large dataset depends on both the resampling operation as well as training with the policy loss. Interestingly, the policy loss seems to help signifi- cantly which suggests that learning the nodes to individu- alize is important. Furthermore, TRIANGLESS-aage test set contains graphs with larger number of nodes as compared to the graphs in training data. Hence, the results indicate that both operations can help our model to generalize better. Additional ablation experiments are included in the Appendix A.. A.5
loss. Results on TRIANGLES dataset.
Train
Orig
Large
PF-GNN
99
99
72
w/o resampling
99
99
63
w/o policy loss
97
46
Runtime: PF-GNN is efficient in terms of its runtime given its expressive power. Since, we run a GNN in each step for fixed iterations, the runtime of PF-GNN is bounded by O(nT') depth T with parallel computation of K paths. We further empirically evaluate the increase in runtime of PF-GNN compared to the 1-WL GNN model. Fig. plots the ratio of increase in runtime compared to the base GNN, as we increase number of particles and depth. The results confirm that the runtime increase is only linear as keep increasing T. Note that we do not need longer depth a few individualizations are sufficient to break most of the symmetry in graphs. Additional runtime results in Appendix A.5.3
6 CONCLUSION
Message passing GNNs are known to be not fully expressive for learning functions on graph struc- tured data. In this paper, we first define way of learning universal representations of graphs by guiding the learning process with exact isomorphism solver techniques. However, learning these rep- resentations can take exponential time in worst case. To be practically useful, we proposed PF-GNN, differentiable particle filtering based model to approximately learn the universal representations. PF-GNN learns highly discriminative representations while being efficient in runtime requirements. is flexible and can be used with any GNN as backbone. Experimental results on various benchmarks demonstrate that PF-GNN can distinguish even those graphs not distinguishable by 3-WL equivalent models and gives competitive results on real-world datasets.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work is generic method to improve the expressive power of any GNN backbone models. As our work applies GNNs generally, its ethical impacts (both positive and negative) will be on the broad approach of GNNs rather than on any specific application.
REPRODUCIBILITY STATEMENT
The complete proofs for Theorem and Theorem 2 are included in Appendix A.3 For experiments, the settings stated in Section and more details of the model architectures and hyperparam- eter for training are specified in Appendix A.5.5 Details of the datasets used can be found in (..3.. To further facilitate reproducibility of the work, we provide publicly available code at https://ghhuh.com/fggmPPFFCC
ACKNOWLEDGEMENT
This research is supported in part by the National Research Foundation, Singapore under its AI Singapore Program (AISG Award No: AISG2-RP-2020-016)
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179 2020.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42-59 2020.
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. arXiv preprint MXXV:2206604319, 2021.
Dominique Beani, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 748-755 PMLR, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint 0925:2006.09252. 2020.
Mare Brockschmidt. Gnn-film: Graph neural networks with feature- wise linear modulation. In International Conference Machine Learning, pp- 1144-1152. PMLR, 2020.
Guangyong Chen, Pengfei Chen, Chang-Ya Yu Hsich, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, al. Alchemy: A quantum chemistry dataset benchmarking models. arXiv preprint arXiv: 09427, 2019a.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. arXiv preprint 190. 2019b.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint wxXi::2002.04055. 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.05718. 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3855 2016.
10

---

Published as a conference paper at ICLR 2022
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks learning graph topology. arXiv preprint 190ii 05008, 2019.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1263-1272. JMLR. org, 2017.
Wassily Hoeffding. Probability incqualities for sums of bounded random variables. In The collected works of Wassily Hoeffiding, pp. 409-426. Springer, 1994.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0065 2020.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pp. 2323-2332. PMLR, 2018
Tommi Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical labeling. In International Conference on Theory and Practice of Algorithms in (Computer) Systems, pp. 151-162. Springer, 2011.
Peter Karkus, David Hsu, and Wee Sun Lee. Particle filter networks with application to visual localization. In Conference on robot learming, pp. 169-178. PMLR, 2018.
Thomas N Kipf and Max Welling, Semi- eemi-super classification with graph convolutional networks. arXiv preprint
2016.
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.031233 2020.
Boris Knyazev, Graham Taylor, and Mohamed R Amer. Understanding attention and generalization in graph neural networks. arXiv preprint arXiv: 2019.
Nils M Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A property testing framework for the theoretical expressivity of graph kernels. In IJCAI, pp. 2348-2354, 2018.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding-dest design provably more powerful gnns for structural representation learning. arXiv preprint wrXiv:2009.00144 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2019.
Xiao Ma, Peter Karkus, David Hsu, Wee Sun Lee, and Nan Ye. Discriminative particle filter reinforcement learning for complex partial observations. In International Conference Learning Representations, 2019.
Xiao Ma, Peter Karkus, David Hsu, and Wee Sun Lee. Particle filter recurrent neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5101-5108, 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph 2018.
networks. arXiv preprint
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint 1905: 2019.
Brendan McKay and Adolfo Piperno. Nauty and Traces. httpss:/pallii: wnw.iiiiiiiiiiddiimoii...i.....i romal It/Inttroduct oonn html, 2021. [Online; accessed 20-November-20221)
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of Symbolic Computation, 60:94-1122 112, 2014.
11

---

Published as a conference paper at ICLR 2022
Brendon Mckay. Strongly regular graphs. http://sssrrresccccoe www...a..a...u.......... http:///wuuuceeecccooo..aaaaaaaa graphs html, 2021. [Online; accessed 00toberrrr22.1...
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33, 2020.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673. PMLR, 2019.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1:140022, 2014.
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. Journal of chemical information and modeling, 52(1 1):2864-2288 2012.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprint arXiv:2002.03155: 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference Learning Repre- sentations, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 17Xiv:1710.109000 2017.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. arXiv e-prints, pp. arXiv-2006, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint IrXiv:I810..m
2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awes aware graph neural networks. In International Conference Machine Learning, pp. 713777144444 -143. PMLR, 2019.
Daniele Zambon, Cesare Alippi, and Lorenzo Livi. Graph random neural features for distance- preserving graph representations. In International Conference on Machine Learning, pp. 10968- 10977. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 PARTICLE FILTER ALGORITHM
Particle filter estimates the posterior distribution of the states of Markov process when noisy/partial observations are received. It uses set of samples or particles to represent the posterior distribution of the state given a series of observations. One of the main benefit of particle filtering is that the particle set can approximate any arbitrary distributions,
Consider a Markov process with the state transition probability given by p(z, (1-1) where i is the state at time step I. For every transition, we receive an observation described by observation probability of p(o, (.)). Given series of observations 0t=1:T = (0I,..., or) }. particle filters estimate the posterior probability p(ar (o==1:T). ). of the state æT conditioned the sequence of observations.
Specifically, particle filters sequentially approximate the posterior distribution by maintaining a belief over the states b(z) with a set of K particles, i.e., weighted samples from the probability distribution,
bx(x)) R (at; w w
(10)
where Σx w/= 1, K is the number of particles, w is the particle weight and x is the particle state time step f.
The particles are sequentially updated with three steps: transition step, observation update step and the resampling step.
Transition step:
At each time step, the particles transition to new states depending on the current state. For each of the K particles, the new state is computed by sampling from the probabilistic transition model given by,
x ~ p( (
(11)
where p( ( is the probability of state o, given the previous state -x-11-
Observation update step:
After transition step, receive observation which is noisy signal for the state of the system. Therefore, after every transition, the weights of the belief need to be updated with the observation received. The observation compatibility function given by fabs (or (ax)), measures the conditional likelihood of the observation given the state. Since, we have K particles, we measure the observation likelihood for each one of them by computing
fot Lobu (orl
(12)
The weights of the particle set updated by mulitplying with observation model and then normaliz- ing the weights across the K K-particle set.
I = for w
(13)
where 17 Σş=LK fi wi-n the normalization factor.
Resampling step:
very common issue in sequential state estimation with a set of particles is the problem of particle degeneracy when most of the weight tends to be concentrated in one two particles. This issue is resolved by resampling a set of new particles from the weights distribution. The new set of particles are sampled from the weighted distribution (wi k= with repetition. Following the resampling operation, the weights are reset to uniform distribution by setting,
w = 1/K.
(14)
The new belief represented by the particle set (w/, at) approximates the same distribution, but devotes its space to the most promising particles.
At any step f, the state can be estimated by taking the weighted mean of the particle set,
24 Ex w ar
(15)
13

---

Published as a conference paper at ICLR 2022
A.2 DERIVATION OF THE GRADIENT UPDATE
The prediction DT generated by the PF-GNN depends on multiple sampling steps. Therefore, in order optimize the parameters, we minimize the expected loss under the random variables sampled during the process. The two random variables in PF-GNN are the particles selected during resampling step with weights k=1/ and the sequence of individualization vertices Since, we use soft- resampling and are able backpropagate through the weights (w=) we only optimize the expected loss with random variable I.
Let y be the prediction target, I be the sequence of vertices individualized in one particle chain from root to leaf, "f=1- be the colorings generated in one sequence of individualizations I. Then the expected loss over such sequences.
Loss(9,9)
Σ P(I I
(16)
where P -i=1-: 0) is the probablity of the full chain for = 1 of the sequence I and _( y: 8) is the loss of the final model prediction ÿ and the target y. Note that the both P) and L(ū, y: 0) share some of parameters. Consequently, cannot separately learn both the functions. Taking the gradient of the loss, we have:
Loss V Σ P(Ig
- T= 1:T: L)
(17)
Σ PP(I) -f L)
(18)
P VL 3T 1.7
(19)
VPIIS - I 0) 17
PII - 1
(20)
Σ P(I V log ()
In the second step, we used the product rule of differentiation and in last step, have used the identity Vp(Zl-) = p(Z))) V log p(z-) This gives us two additive expectation terms under the distribution of P(IG,, T=1:: 0) to optimize in the loss function.
V Loss((G,)) Ez~r(z)) (L(U(TEE
(21)
EI~P(ZT) (Vlog log P(IG,
We optimize the expectations by the set of K samples of I drawn from the distribution of P(Z]G, of .))
A.3 PROOF FOR THEOREMS
Theorem I Consider a n-vertex graph with no distinct node attributes. Assume we use universal multiset function approximators for target-cell selection and graph pooling function th. and GNN with 1-WL equivalent expressive power for color refinement, then the representation f()) in Eqn. permutation-invariaat and can uniquely identify G.
Proof. First, note that the set of leaves generated by the search tree of the exact graph-isomorphism solvers for a given n-vertex graph respects permutation--qquivanei
and contains the canonical representation the largest element, hence uniquely identifies the graph. Please refer McKKa & Piperno (2014) for a detailed proof. To complete the proof, observe that with sufficiently expressive networks, we approximate the target-cell selector and individualization algorithms in the exact solver arbitrarily closely. Using 1-WL equivalent GNN, we can also approximate the refinement operation arbitrarily closely. Repeated applying these operations give equivalent set of leaves as
14

---

Published as a conference paper at ICLR 2022
those produced by the exact solver. Finally, using universal multiset approximator db in conjunction with an MLP, p which also universal approximator allows us to distinguish distinct sets of leaves from non-isomorphic graphs.
Theorem 2 Assume we need D dimensional embeddings for some D > O, in order to uniquely represent any graph of n-vertices. Consider two n-veriex graphs 91 and G2 whose universal representations in Eqn. are f1 and f2 after T levels of the search tree. Let the max-norm distance between f1 and f2 be at least d ie. generating the full level-T search tree for both graphs will separate them by d. Assume that the values in embeddings generated by the tree are strictly bounded the approximate embeddings,
the range of [-M, M). Then, with probubility of at least generated by sampling K paths from root to leaves, are separated in max-norm distance by d + provided the number of root to leaf paths sampled are at least
M In 4D
KEO O
8
Proof. Observe that we independently sample K paths from root to leaf of the search tree. After steps in the tree, if the mean of the embeddings is ff ii Σ, (G, π:"), then we have K independant samples to approximate the mean. For clarity, we omit G and refer actual expectation as fe and sample approximation with J"
1
Note that by the Hoeffding bound (Hoeffding. 1994; Shalev-Shwart & Ben-David 2014) for mean of K independent random variables Y1, I....., YK in range |-M, M] with expected value μ,, we have
P P( 1l 2 5) eexp (- 2M2
KC²
(22)
Assume we need dimensions for some D > O, in order to fully represent any n-vertex graph. Since, we independently sampling from the leaves of the tree, the Hoeffding bound holds for each of the estimated value in the D-dimensional vector. Hence, for any ęth value in the graph embedding,
P P( firl-frl22 (orlfrrls))) 25) 2
KÇ²
(23)
2M
Since this bound holds for every value of the embedding. we can bound the maximum error for any of the D estimates with the "union bound" probability for all the D values simultaneously.
KC²
P max Jer firl 2 c) S 2D 22Dex exp
(24)
2M2
This gives us the max-norm distance between the estimated and the expected embeddings. Using < = </2, we get
Ke²
P( f1rll2/2))2) exp
(25)
8.22
Now, assume two non con-isomorphic graphs G1 and G2. are separated in max-non norm distance by i.e. IlSrr S2r || = d, at level 7 of the search tree. With at least K samples, we can union bound the error in distance between the two graphs by 6.
p (I]] - F2rll 11 f2rll 2 e) s P (( -hrll 2 ;) + P( fer 2 2)
(26)
Kr²
4D exp
(27)
8.M2
Bounding the failure probability with 8, we get the minimum samples needed for the approximation
as:
8n 4D
K>
(28)
2
M M1n((4) 4D
KEO
(29)
n
15

---

Published as a conference paper at ICLR 2022
A.4 PF-GNN ALGORITHM
Algorithm PF-GNN Algorithm
1: Input: Graph (V,E); GNN; findi fobsiP(;;
2: Output: ú. (g)
3: Initialize Hn =
4: (g) [H| = (N)(HH), w = 1/K)R=1N R=1.K
(initial belief)
5: for 1 to I do
6: for k = to K do
7:
P(VIH, H Sind H G
8:
9:
(transition update)
10:
end for
11:
(wr (=E))==1KKK = rifobo (H (0)) wi u
(observation) (resampling step)
12: (wi+ (1 k=1:K
) k-1:
13: end for
14: (G) = (HT, w
(final belief)
f(G) CONCAT(EELL. i. H )==ir
16: ÿ READOUT
17: Return Ú; br (9)
A.5 ADDITIONAL EXPERIMENTS
In this subsection, we provide further experiments in order to evaluate various components of the PF-GNN algorithm.
A.5.1 IMPACT OF INDIVIDUALIZATIO FUNCTION:
PF-GNN, individualization method involves transforming the selected node embedding via an MLP. In this ablation study, seek to learn whether learning the individualization method is useful for the end performance. For this, we replace the learnable MLP with non-lcarnable random features sampled from standard Normal distribution used in Abboud et al. (2020) and compare the performance TRIANGLES, and CSL datasets. Moreover, we compare both methods of individualization for various partial levels of node-feature perturbations as partial individualizations were noted to be helpful in RNI (bboud et al. 2020). In partial RNI, only part of embedding dimensions are perturbed. For example, 50% refers 50% embedding dimensions of the selected node are perturbed in each IR step. PF-GNN with T=3 and K=4 was used in the experiments. We train all models with randomized individualization till convergence in this experiment.
Table 10: Effect of MLP vs Random individualization functions for various levels of partial individualization.
MLP 100%
ML.
MLP 50%
MLP
DATASET
87.5%
12.5%
100%
87.5%
50%
12.5%
TRIANGLE-LARGE
68.9
67.9
68.3
61.4
64.5
57.4
49.3
27.5
CSL
100
100
100
100
100
100
82.6
48.0
Results in Tab. 10 suggest that learnable MLP is better than random perturbations for node individu- alization. For partial individualization, MLP performs similarly or better than random features. For full individualization, the difference is less clear in CSL dataset both methods give similar result. However, very small levels of partial random perturbation seem to harm performance in both datasets.
A.5.2 IMPACT OF SEQUENTIAL INDIVIDUALIZATION:
We now study the impact of sequential individualization of PF-GNN. In the ablation study of the main paper, we show in Tab, that sequential individualization without learning significantly reduces performance i.e. which nodes are selected in each IR step is important. We further examine the
16

---

Published as a conference paper at ICLR 2022
effects of sequential individualiization compared to simultaneous individualization. For this, compare following ablation models of PF-GNN: 1) PF-GNN with T=3 steps of IR, 2) PF-GNN-A:
PF-GNN with single IR step but 3 randomly chosen nodes individualized in the same step. 3) PF-GNN-B: single IR step but random nodes are individualized at once 4) PF-GNN C: single IR step with 9 nodes individualized. Note that we individualize same number of nodes for PF-GNN method (sequential) and PF-GNN-A method (simultancous). We train all models till convergence in this experiment.
Table 11: Effect of sequential individualization PF-GNN.
DATASRT
PE-GNN-A
HINDIVIDUALIZED NODES
3
6
9
TRINNGESS-ARRE
68.7
35,5
36.2
37.6
49.23
42.67
Results in Tab. 11 show that sequentially individualizing selected nodes is better than individualizing a subset of nodes at once on both the datasets. Since most nodes are indistinguishable initially, is hard to learn the optimal subset in step. With sequential IR, the graph-coloring is refined in each step and the model can learn to successively pick nodes which are likely to generate the best refinement. Therefore, "Sequential IR process with learning" helps in finding those subset of nodes. Furthermore in CSL dataset, performance goes down as we increase the number nodes individualized once, suggesting that larger unguided randomness may not be helpful. Overall, the results suggest that PF-GNN's data-driven sequential refinement improves GNN's expressivity while adding minimal randomness.
A.5.3 RUNTIME ANALYSIS
In this subsection, we further study the running time behaviour of PF-GNN in contrast the base GNN models. Assuming GNN takes linear time for counded-degred graphs On)), runtime of PF- GNN is OnTT)) for T number of IR steps. Note that the computation of K paths can be parallelized. In Tab. 12 we provide additional empirical runtime results of PF-GNN models for different K and values for the Zinc and Alchemy datasets. We also compare with the runtime of the standalone backbone GNN model. The numbers in brackets indicate the ratio of the runtime of PF-GNN w.r. that of backbone GNN. For fair comparison, all models are trained on a single GPU with a batch size of 64 with PNA convolution the base GNN. The results indicate that runtime increase is only linear in T.
Table 12: Runtime ALCHEMY and ZINC datasets. Numbers in the brackets indicate the runtime ratio with respect to the base GNN.
GNN
K=4, T=1
K=4, T=2
K=4.
K=8, T=1
K=8, T=2
K=8, T=3
ALCHEMY
6.72s (1)
11.70s (1.74)
14.82s (2.20)
18:24s (2.71)
12.28s (1.82)
17.35s (2.88)
23.578 (3.51)
ZINC
8.42s (1)
13.12s (1.73)
19.245 (2.54)
26.24s (3.48)
17.148 (2.03)
27.11s (3.21)
38.575 (4.47)
Furthermore, PF-GNN is flexible model. We can reduce the number of GNN iterations within each IR step, we want to keep the same time as the base GNN. Even so, we can still get performance improvements with PF-GNN. Below we report results of the standalone base GNN model with 6 iterations and PF-GNN with = and
6 GNN message passing steps in total. Results in Tab. 13 show that PF-GNN improves upon GNN with the same budget of total GNN layers. Additionally, ly, the results further empirically support that the improvements are a result of IR process and not merely addition of more GNN layers.
Table 13: Runtime VS MAE comparison of PF-GNN with base GNN with a total 6 GNN layers.
MODEL
GNN STEPS
ZINC (MAE)
ZINc (TIME)
ALCHEMY (MAE)
ALCHEMY (TIME)
6-STEP BASE GNN
[6]
18.14
8.92s
6.82s
PF-GNN T=1
[4.2]
13.37
12.338
11.66
9.06s
PF-GNN T=2
[2, 2, 2]
14.01
17.578
11.73
11.175
17

---

Published as a conference paper at ICLR 2022
A.5.4 GRAPH PROPERTY TESTING
the main paper, we studied graph properties like triangle counting and local clustering co-efficient and found the PF-GNN outperforms 1-WL equivalent GNNs. In this subsection, we study another set of fundamental graph properties that GNNs cannot capture. These properties are connectivity, bipartiteness and planarity (Kriege et al. 2018). For all three tasks, generate synthetic datasets of 100 graphs for training and 40 graphs for testing with equal number of positive and negative samples. Each graph consists of 20 nodes each. For connectivity dataset, first generate two random connected graphs which forms a single instance non-connected graph and add an edge between the
make a positive sample of connected graph. For planar datasets, we generate random regular graphs and check for planarity. We repeat till we have equal number of planar and non-po non-planar graphs. For bipartiteness, we generate random bipartite graph and create positive sample by adding an edge between two groups of vertices and negative sample by adding an edge within group of vertices. Tab. 14 shows that GIN model fails on all three tasks while PF-GNN reaches near optimal accuracy on each one of them.
Table 14: GNN and PF-GNN on fundamental graph property testing.
CONNECTIVITY
PLANARITY
BIPARTITENESS
GIN
62.4
50.5
55.7
PF-GNN
97.5
98.7
99.1
A.5.5 HYPERPARAMETER AND ARCHITECTURE DETAILS
In this subsection, we report the hyperparameters used in all experiments from Section Tab. The architecture of PF-GNN is specified by the backbone model, number of particles and number of IR steps. We also report the hyperparameters used for training, including batch size, number of embedding dimensions and the weight for policy loss. The learning rate is set 1e-3 for SR25 and EXP, and we use a scheduler to reduce it based on the improvement of metrics for other datasets.
Table 15: Details of hyperparameters used for each dataset. K: number of particles, T: number of IR steps, y weight of policy loss.
DATASET
BACKBONE
K
T
BATCH SIZE
#HIDDEN DIM
#EPOCHS
SR25
4
8
0.1
128
64
100
EXP
4
8
0.1
128
64
100
CSL
GIN
8
3
16
64
500
TRIANGLES
PNA
24
128
LCC
GIN
4
2
0.1
64
500
ZINC
PNA
8
3
0.1
64
150
500
ALCHEMY
PNA
8
4
0.1
64
150
500
QM9
MPNN
4
2
0.1
64
64
300
OOBG-MOLHIV
PNA
8
2
0.1
256
120
200
Baseline results: The baseline results mentioned in Tab. [ are reproduced from the open sourced
code from Balcilar et al. (2021) and those Tab. are from Dwivedi al. (2020). We reproduced the results from Knyazev et al. (2019) for Tab.
For Tab. 4 reproduced results for PNA from the open sourced code and rest of the results are reported from Morris et al. (2020) for k-GNNs and Beani et al. (2021) for DGN. For QM9 results in Tab. we report results from Morris et al.) (2020); Kllippra et al. (2020) and from BBookkschidd (020 for Tab. 6 For Tab. we get the baseline results from the OGB leaderboard (Hu et al. 2020).
A.5.6 ADDITIONAL EMPIRICAL RESULTS
Two additional sets of experiments are done to complement our empirical evaluation. In Abboud et al. (2020). they different setting for EXP dataset compared to experiment in Tab. which is 10-fold cross-vall validatio..... We follow their setting and make further comparison with more expressive baselines in Tab. 16 PF-GNN again achieved 100% accuracy.
18

---

Published as a conference paper at ICLR 2022
We also include additional ablation study number of IR steps and number of particles. We test the performance for each architecture on the easier TRIANGLES-Ore orig test set, where the number of nodes for each graph is similar to that of the graphs in training set. As shown in Tab. [7] models with I==1 get substantially less accuracy than the deeper ones. Furthermone, increasing both K and TT helps with the performance.
Table 16: Graph isomorphism test on EXP dataset with 10-fold cross-validation. Results of the baselines are from Abboud et al. (2020).
DATA SET
EXP
GCN-r
98.0 +1.8
PPGN
50.0
1-2-3-GCN-L
50.0
PF-GNN
100.0 =0.00
Table 17: Ablation results of PF-GNN with different number of IR steps (T) and different number of particles (K). Results on TRIANGLES-orig
ACC
K=1
K=2
K=4
K=8
K=16
T=1
85
82
87
89
91
T=2
96
93
94
96
96
T=3
99
T=4
99
99
99
99
99
T=8
99
99
99
99
99
A.5.7 DATASETS
SR25:
This dataset (Mckay 2021) contains 15 strongly regular graphs, where each of them has 25 nodes and each node has 12 neighbors. 5 common neighbors are shared by connected nodes while common neighbor shared by disconnected nodes. There in total 105 pairs of non-isomorphic graphs The task is to distinguish all pairs. This is challenging task because strongly regular graphs are known to one of the hardest class of graphs for detecting isomorphism. It is to be noted that SR25 dataset is used as one of the benchmarks for isomorphism detection task.
EXP:
This dataset (Abboud et al. 2020) consists of 600 pairs of non non- non-isomorphic graphs. Each graph in in EXP dataset encodes a propositional formula. Classifying the graph equivalent determining the propositional formula is satisfiable or not.
For both SR25 and EXP, we train the models with all graphs and test whether the models can learn embeddings that distinguish each pair. vollowollo,ing Balcilar et al. (202T) we use 3-layer models for all backbones in Tab. 3 and steps with particles for models with PF-GNN. We run experiments with 10 different seed and report the average accuracy and standard deviation.
CSL.:
This dataset from Murphy et al. (0199) consists of 150 4-regular graphs with edges forming a cycle and contain skip links. The 150 graphs are divided evenly into 10 isomorphism classes based on the skip length. All graphs are 1-WL equivalent. The task is classify the graphs into isomorphism classes that can only be accomplished by models with higher expressive power than 1-WL. As in Dwivedi al. (2020); Murphy al. (2019), follow 5-fold cross validation for evaluation. PF-GNN results are obtained with 3 IR steps, particles and GIN as backbone.
19

---

Published as a conference paper at ICLR 2022
TRIANGLES:
The TRIANGLES dataset, released by (Knyzzev et al. 2019). consists of 45000 graphs and the task is to count the number of triangles in each graph. Interestingly, the dataset comes with two test splits; test-orig and test-large, both of which have 5000 graphs. The training set as well as the test-orig set consists of graphs with < 25 nodes while the test-large set has 100 nodes in each graph. Better prediction in test-large suggests that the model is able to generalize better. It is a graph classification problem with 10 classes.
LCC:
LCC dataset (Sato et al. 2020) consists of 2000 random 3-regular graphs with 1000 graphs each for training and testing. The nodes are labelled with their local clustering coefficient (LCC) value. LCC measures how close a node's 's neighbours are to being a clique. It is yet another property that 1-WL GNNs fail to identify. It is node level classification problem with 3 classes. The dataset consists of two test sets N and X. The training set and test-N set have graphs with 20 nodes and test-X - has graphs with 100 nodes. A good performance on LCC-X further shows the generalization ability of the model to larger graphs.
ZINC:
ZINC a real-world molecular dataset consisting of more than 250K graphs. We select the popularly used subset made available by Dwivedi et al.] (2020) which contains 1000 graphs. The dataset comes with standard split 10000 graphs for training set and 1000 graphs each for testing and validation sets. It contains graphs along with their constrained solubility values. The task is regression on each graph to predict the constrained solubility values. For evaluation, we measure the mean absolute error on the predicted values.
ALCHEMY:
The Alchemy dataset Chen al. (2019)) consists of nearly 200K graphs along with their 12 quantum mechanical properties. We chose the subset provided by |Morris et al. (2020). The dataset comes with 12000 graphs. The test set and the validation set contain 1000 graphs each. The task is to regress the 12 quantum mechanical properties and evaluate on mean absolute error.
QM9
QM9 Ramakkishhan et al. (014)) is a large scale molecular dataset consisting of nearly 130000 graphs. Each graph consists of set of node features associated with atoms along with bonds encoded as edge features. Additionally, we are provided with 3D node position coordinates for each atom. The task is graph regression We follow the convention of randomly splitting the dataset with 10000 graphs each in testing and validation set. The rest of the graphs are used for training. Interestingly, the node position coordinates have been shown to be very useful in Klicpera et al. (2020). However, we conduct two separate experiments, one with node position coordinates and other without the position features.
of 12 quantum-chemical properties associated with each graph.
OGBG-MOLHIV
Ogbg-Molhi Molhiv dataset consists of 41127 molecular graphs. The task binary classification for molecular property prediction. We use the full 9-dimensional node features, and adopt the standard scaffold split provided by Hu et al. (020).
A.6 EXTENDED PRELIMINARIES
In this subsection, we provide extended discussion on the graph coloring process and the search tree which GNN is designed to approximate. For a detailed explanation, please refer to McKay & Piperno 22014). Below figures are adapted from McKay & Piperno (2021), visual guide to the practical graph isomorphism solvers from the authors of Nauty and Traces.
Coloring and 1-WL refinement:
Graph Neural Networks have been shown to be neural analogues of vertex color refinement technique with neural embeddings being equivalent to the colors. Graph coloring is technique of assigning graph vertices with unique numbers in a permutation invariant manner; thereby ordering the vertices. 1- algorithm is one way coloring vertices and is also called naive-vertex refinement. In 1-WL.
20

---

Published as a conference paper at ICLR 2022
refinement, initially all nodes are assigned with the same color. In each iteration, 1-WL reassigns colors of each node based on its neighbourhood. As long as two vertices have different multiset of colors in their neighbourhood, they will be assigned different colors. However, after some iterations, the colors stop changing. At this point, the coloring is called equitable coloring.
Equitable coloring
An equitable coloring is one where every vertices of the same colour adjacent to the same number of vertices of each colour. Fig. 4 shows some of the example equitable colorings. The colorings divides the set of vertices into disjoint sets based on the node colors. Hence, equitable colorings are also loosely called equitable partitions. An equitable coloring where each node has unique color call discrete coloring.
Figure 4: Example equitable partitions. The middle coloring in the second row is both equitable and discrete coloring.
Identifying graphs:
In order to uniquely identify graphs, we need to color every vertex uniquely in permutation invariant manner. For this, we need to generate discrete coloring in a permutation invariant way. Due to symmetry in the graph structures, equitable colorings do not allow 1-WL process further refine the colorings. Therefore, GNNs are also limited in their expressive power to distinguish all non-isomorphic graphs. This bottleneck can be broken with a technique called individualization and refinement.
Individualization and refinement:
Individualization and refinement a technique of breaking the symmetry in the equitable colorings by recoloring a node with unique color. Once, node is distinguished from rest of the vertices, this information can be propagated the I-WL/GNN message passing. Fig. [ shows an example of the IR process. Initially vertex is individualized by coloring it Green. Then in the refinement stage, its neighbours will be distinguished from other vertices. Thereafter, rest of the vertices are similarly distinguished iteratively till finer equitable coloring is reached.
Count Green neighbours
Count Yellow neighbours
Count Red neighbours
Equitable Coloring
Figure 5: IR process: First a vertex distinguished from rest the vertices and this information is propagated to other nodes via message passing generate refined equitable coloring of the graph.
21

---

Published as a conference paper at ICLR 2022
Search tree
The IR process is not permutation invariant operation as the refined coloring depends on the individualized node in the graph. Therefore, in order to preserve permutation invariance, need to repeat the IR process for all the nodes which have the same color i.e., belonging to the same color cell in the equitable coloring. This gives rise to search-tree where the equitable colorings form tree-nodes. The search tree is unique representation of the isomorphism class the input of graph i.e., all isomorphic graphs generate the same search tree and non-isomorphic graphs generate different search trees. Fig. shows the example of one such search tree.
22


Reviews:
[{"review_id": "pNMF5z-3ZNi", "reviewer": "Reviewer_tTwv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Adapting IR to neural and GNN area is a novel and important contribution. The designed algorithm does improve over base GNNs. \n2. The particle filtering algorithm is a elegant and low-complexity realization of IR algorithm. \n\nWeakness:\n1. 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. \n2. 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.  \n3. 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. \n4. 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. \n5. 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_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. ", "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.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "naLzr_iShEN", "reviewer": "Reviewer_weJp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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: \n\n- 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. \n- 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.\n- 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.\n\n[1] Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020.\n", "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.", "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. \n\nDISCUSSION UPDATE: Rating increased from 5 to 8 following additional experiments (details in review replies). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "T1EAZlM8f-p", "reviewer": "Reviewer_YGAz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Pros:\n\n(+) The design and results are theoretically sound.\n\n(+) The empirical results show that PF-GNN outperforms many existing GNN methods on various graph-level tasks.\n\n## Cons:\n\n(-) The clarity of the paper can be improved for non-expert readers.\n\n## Detail comments:\n\nI 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.\n\nOne 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.\n\nFinally, 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?\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GNLenMo5dCk", "reviewer": "Reviewer_WUrz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Summary:\\\nThe 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.\n\nTheoretical Motivation:\\\nThe 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.\n\nSince 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)?\n\nExperimental evaluation:\\\nThe 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.\n- 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.\n- 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).\n\nMinor comments:\\\nPlease explain how the PF-GNN model is trained on the three graph isomorphism test datasets. What are the class labels of the different samples?\n\nIn 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.\n\nTypos:\\\n\"consistently outperform\" => \"consistently outperforms\" \n\nReferences:\\\n[1] A Property Testing Framework for the Theoretical Expressivity of Graph Kernels. Nils M. Kriege et al, In IJCAI'18.\n", "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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)