Rethinking and Extending the Probabilistic Inference Capacity of GNNs
Authors: Tuo Xu
Lei Zou
Venue: ICLR 2024 poster (2024)
Keywords: graph neural networks
expressiveness
approximate inference
Primary area: learning on graphs and other geometries & topologies
TL;DR: Discuss and extend GNNs' expressive power for probabilistic inference.

Abstract: Designing expressive Graph Neural Networks (GNNs) is an important topic in graph machine learning fields. Despite the existence of numerous approaches proposed to enhance GNNs based on Weisfeiler-Lehman (WL) tests, what GNNs can and cannot learn still lacks a deeper understanding. This paper adopts a fundamentally different approach to examine the expressive power of GNNs from a probabilistic perspective. By establishing connections between GNNs' predictions and the central inference problems of probabilistic graphical models (PGMs), we can analyze previous GNN variants with a novel hierarchical framework and gain new insights into their node-level and link-level behaviors. Additionally, we introduce novel methods that can provably enhance GNNs' ability to capture complex dependencies and make complex predictions. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our approaches.

Published as a conference paper at ICLR 2024
RETHINKING AND EXTENDING THE PROBABILISTIC INFERENCE CAPACITY OF GNNS
Tuo Xu
Lei Zou
Wangxuan Institute of Computer Technology Peking University
Wangxuan Institute of Computer Technology Peking University
Beijing, China
Beijing, China zoulei @pku edu.
doujzcestu. pku. edu.cn cn
ABSTRACT
Designing expressive Graph neural networks (GNNs) is an important topic in graph machine learning fields. Despite the existence of numerous approaches proposed to enhance GNNs based on Weisfeiler-Lehman (WL) tests, what GNNs can and cannol learn still lacks a deeper understanding. This paper adopts a fun- damentally different approach to examine the expressive power of GNNs from a probabilistic perspective. By establishing connections between GNNs' pre- dictions and the central inference problems of probabilistic graphical models (PGMs), we can analyze previous GNN variants with a novel hierarchical frame- work and gain new insights into their node-level and link-level behaviors. Addi- tionally, we introduce novel methods that can provably enhance GNNs' ability to capture complex dependencies and make complex predictions. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our ap- proaches.
INTRODUCTION
Graph neural networks (GNNs) are the dominant approaches for learning graph-structured data, among which message passing neural networks (MPNNs) are the most promising variants, demon- strating remarkable success across various domains. The development of MPNNs can be classi- fied into several distinct theoretical motivations. From the perspective of graph signal processing, MPNNs were proposed as generalization of convolutions on Euclidean graph domains (Bruna al. 2013). Also, MPNNS have been motivated by their connection to the Weisfeiler-Lehman (WL) graph isomorphism tests (Hamilton et al. 2017). At the same time. MPNNs were proposed by parameterizing mean-field inference in probabilistic graphical models (PGMs) (Dai et al. 2016). Although GNNs have been well studied, motivated and improved in terms of graph convolutions and WL tests, few works study GNN's probabilistic inference capacity. Many works (Dai et al.)
2016 Satorras & Welling 2021 Qu al. 2022) implicitly assume that GNNs themselves fail to capture the complex joint dependencies among nodes, and consequently these works attempt to in- tegrate GNNs with graphical models, where predictions are then obtained by variational inference algorithms such as loopy belief propagation (Murphy et al.) 1999). The underlying belief behind these GNN-PGM models that leveraging GNNs to parameterize graphical models can enhance GNN's probabilistic inference capacity with belief propagation. However, in this work, we contend that despite the empirical success of these methods, GNNs themselves fact possess substantial approximation capabilities for posterior distributions in various graphical models.
In this study, our objective is to gain deeper understandings of the expressive power of GNNs in terms of approximate inference in graphical models. Unlike the k-WL hierarchy, graphical models provide a more intuitive framework for interpreting graph data and evaluating GNNs. Precisely, we propose an alternative expressive power hierarchy by introducing family of Markov random fields (MRFs) with increasingly complex distribution and inference targets. Based on these metrics, we provide novel insights into various GNN variants including MPNNs, higher-order GNNs (Morris) jet al. 2018), subgraph GNNs (Bevilacqua et al,] (02I). labeling trick (Zhang et al. 2020), etc. within the contexts of node classification and link prediction. Our finding confirm the progressively

---

Published as a conference paper at ICLR 2024
increasing ability of existing GNN variants in terms of capturing higher-orde dependencies, while also providing a novel perspective on their link prediction capacities.
In the second part of this study, we attempt to design systematic and efficient framework for extend- ing the capabilities of GNNs in modeling complex distributions and inference targets. By rethinking the inherent connection between 1-WL (MPNNs) and the Bethe approximation on pairwise Markov Random Fields (MRFs), we propose two methods, namely phantom nodes and phantom edges, each targeting at one of the problems. We then provide a formal analysis of the expressive power of these approaches. The primary advantage of our proposed methods, in contrast to other variants like higher-order GNNs, lies in their simplicity and efficiency. which can be easily implemented as graph preprocessing. Empirically, we demonstrate that our framework significantly enhances the capabilities of MPNNs capturing complex distributions and inference targets, and also improve the performance of MPNNs on various real-world node classification and link prediction tasks.
2 BACKGROUND
We use O to denote sets and use {(} to denote multisets. The index set is denoted as [n] {1....,n} n). We consider node-attributed undirected graphs G = (A, X), where A E R is the adjacency matrix representing the set of edges &g over the nodes of G indexed by VG = [n]. and A.. (i.)eEa. X E I is the collection of node features, with its i-th entrance denoted as a; E Rd corresponding
the feature of the node i. We use Ni( to denote the set of neighbors of the node i in G. A clique C' is fully-connect subset of nodes C = {(i, in} and we refer to k the order of C. A permutation π is a bijective mapping [n] + [n]] For convenience ι can act on graphs, adjacency matrices, node features and indices as usual by π (G) (T(A), T (X)) with π (A) (1) = Ai.j, (X))
X I (fd1,...,4y) 4) = (T( x (ix)))
Given graphs of n nodes we consider set of random variables denoted (x1, 21, ... Xn; z, and use 21, 21, to denote the realization of random variables or non-probabilistic variables. To simplify notations, given a subsets of indices A we let XA to stand for {x, | E A}. For example, if A = {2, 4} and B = [3], we represent p(x2 22, X4 = Dz X3 = 03) as p(xA = AA XB = xB) and more compactly p(xA XB). We also will often use X to stand for {xI.... Xn, and Z for (2,...,Zn, Z.)
Graph isomorphism and Weisteiler-Lehman tests. Two graphs G = (Aa. Xa) and = (An, AAH are isomorphic, denoted as G = H, if they both have n nodes and there exists permu- tation æ : [n] + [r] satisfying A = =(A)) (()))()))))) and (Xc); = (X (z))()) for all j, E [n]] Such is an isomorphism. Weisfeiler-Lehme Lehman (WL) tests a family of necessary tests for graph isomorphism. Apart from some corner cases (Cai et al. 1992), they are effective and computation- ally efficient tests for graph isomorphism. Its 1-dimensional variant is analogous to MPNNs, which iteratively aggregates the colors of nodes and their neighborhoods and then injectively hashes them into new colors. The algorithms decides two graphs non-isomorphic if the colors of two graphs are different. A detailed description of WL tests is in Appendix B Due to space limits we leave a more detailed discussion of previous works in Appendix A
A PROBABILISTIC INTERPRETATION OF GRAPHS
In this section we describe graphical models for graph data as well as highlighting the key problems of inference in graphical models. Given graph G (A, X) with n nodes, we hypothesise each node is completely described by an (unknown) latent random variable z, E Z and denote by = (Z).... 2n,) E 2n the collection of the latent variables. For simplicity we may assume 2 is a discrete space, but our results are also applicable to continuous 2 as long as we generalize GNNs to output Hilbert space embeddings of distributions (Smola et al., 2007 Dai et al. 2016). A specifies the conditional independence structure of Z: ZA IL ZB 2c whenever there no path from node in A to a node in B which does not pass through a node in C. The node features are generated by these latent variables: for a node i, given its latent variable z, the corresponding observed node feature 2; is sampled from z; Paf z.). The graph learning target is, given observed node features X, to infer the latent variables (2.). which can be further used for tasks such as:
2

---

Published as a conference paper at ICLR 2024
Node classification: node label y; is obtained by p(y: x)= -2, plys Zz)ppzz X).
Link prediction: it can be naturally interpreted asking "given that node is the source node, what the possibility label Yij for node pair (i.j) is obtained from both Z, and 2z: plyy X) E2,2, P(y:s Zi 2, )p(z,, X).
j being the target node?". Thus the link
Obviously, once obtained the marginals p(z;) X) and more generally p(z,, 2 X), the labels can be easily inferred. Thus the key problem lies in inferring marginals of the joint posteriori p(Z X). Our target, therefore, is investigate whether and what extend are GNNs expressive enough for inferring the marginals of the graphical models p(Z X). We now introduce details of our framework for investigating GNNs.
3.1 THE PROBABILISTIC FORMULATION
We first formally define the joint distribution we consider. Clifford & Hammersley (1971) states that a positive distribution satisfies the above conditional independence structure if and only it can be represented by
p(X, Z)
II (Z x;) REV
II Vc(zc), GEC
(1)
Z
where vr, Ve are potential functions, the set of CliquesFin G, and Z is the partition function Z Σx,z liev (z. x:) IIcec Vc(zc) (assuming discrete node features). A potential function Vo(zc) is nonnegative, real-valued function the possible realizations of zc- Such family of distributions called Markov random fields (MRFs). Albeit powerful their expressiveness,, the formulation in Eq. does follow general invariant and equivariant assumptions in the graph data. First, each data instance in graphical models are assumed to share the same structure, while in graph machine learning fields each instance corresponds different graphs with possibly different structures. Moreover, Eq. [ might specifies different probabilistic distributions for two isomorphic graphs. To this end, we first define a family of MRFs that are applicable to different graph structures and also invariant to permutations.
Lemma 1. Suppose there is an algorithm F, given any graph G = (A, F maps the indepen- dence structure A to a MRF PG = F(A). Then, satisfies that for any permutation æ [n] + [n] and A:
(T( T (Z)) = PG Z),
if and only if PG can be represented in the form ! with potentials given by Ve A(C, A), V, A(i,A) where A permutation-invant invariiin function that maps cliques (nodes) of graphs
to potential functions: functionn
A(C,A) = ((T()), VC 10,1) and T: [m] - [n].
Lemma T precisely describes the space of invariant MRFs: we can fully define such MRFs by specifying permuration-invariant A. This enables to further discuss the general relation between GNNs and graphical models. In reality, many works choose to parameterize the potential functions above, with A being implemented constant function (Dai et al. 2016) or GNN (Qu al., 2022
3.2 METRICS FOR EVALUATING GNNS
With the properly defined families of MRFs we now discuss our framework for evaluating the ex- pressive power of GNNs.
Complexity of distributions. From the above discussions the complexity of the distribution is fully governed by A. We consider two metrics for evaluating the complexity of distributions: the discriminating power of A and the order of the MRF. We will measure the discriminating power by the WL hierarchy, and define A is k-WL distinguishable if and only if for any cliques C1 C2 from two graphs G = (Ac, H = (AH, XH), A(C1, Ac) # A(O2. Aн) only when k-WL
We do restrict C be maximal cliques
3

---

Published as a conference paper at ICLR 2024
distinguishes C1 and C2 (we assume k- WL does not input node features here; see Appendix for detailed descriptions The order of a MRF refers to the maximum order of cliques C we consider in Eq. [ For example, in pairwise MRFs C. is the set of cliques with orders no more than 2 (i.c., edges). Formally, a k-order MRF is defined by A that satisfies A(C,, G) = for all |C] > k where $ constant. It is able to describe k-order dependencies over k-tuples of nodes.
Target posteriori. As previously discussed, we are interested in the inference problems of estimat- ing posteriori including marginal distributions p(z, X) for node-level tasks and the joint distribu- tion over parts of the variables p(z;, Zj X) for link-level tasks. Note that since we can factorize the posteriori as
p(z zj
X = p(z, Z,, x))(zz X):
the posteriori can also be estimated by repeatedly applying inference algorithms on the conditional marginals.
Methods for inference. Given the recent developments in GNNs, one may expect that GNNs might be able to perform exact inference in MRFs. However, our next theorem states that the exact in- ference of even a simple pair-wise MRF with merely 1-WL distinguishable potentials requires the ability of distinguishing all non-isomorphic graphs
Given any connected graphs G (Ac, If i and are not isomorphic, then there exists I-WI. distinguishable 2-order A such that the pair-wise MRFs pG, PH specified by A on G and H satisfy:
Theorem 2.
XH) and E Va.5 E Vn-
Pa(z: = X = XG) # pu(Zz = X Xn).
Therefore, current GNNs fail to learn the exact inference on general graphs. This is not surprising the exact inference on graphs with loops are often exponentially expensive, and often resort to variational inference for estimating the marginals. Given the original intractable distribution p. variational inference aims find tractable distribution g to approximate p: min, (qlp), where DKL is the Kullback-Leibler (Kullback & Leibler 1951) divergence. In this paper we will focus on the successful approximate inference method belief propagation, which is also known as the Bethe approximation (Murphy et al. 1999 Yedidia et al. 2001). Bethe approximation on pairwise (c.(x;,;;)
MRFs assumes a quasi distribution q (Z) LiEv Vi (z,) (I,j)EE (2,))),;(2,) thus considering the dependencies over nodes. (Yedidia et al. 200T). A successful algorithm for minimizing the Bethe free energy is the loopy belief propagation (Heskes) 2002b), which is a fixed iteration over messages
of edges.
Problem setup. Our analysis aims answer the question: what extent GNNs approximate the inference of graphical models? We tackle the problem by investigating GNN variants via the following criteria as discussed above:
How complex the joint distribution can be? This includes the discriminating power and the maximum order of A.
What posteriori can GNNs approximate?
If GNNs cannot perform exact inference over MRFs, how approximate can their predictions be?
We believe answering these questions would print clearer picture about what GNNs can learn from a more intuitive, probabilistic perspective.
4 ANALYSING THE PROBABILISTIC INFERENCE CAPACITY OF GNNS
4.1 ON MPNNS AND PAIRWISE MRFS
Our first results aim to characterize the expressive power of MPNNs in terms of modeling proba- bilistic distributions over MRFs, as well as introducing our strategy for evaluating GNN models.
2 We choose the WL hierarchy due to its prevalence in the GNN literature; other metrics are certainly accept- able. Note that MRFs are usually powerful even with less expressive A: in reality, A is usually implemented simply producing identical potentials. Fully prohability-based results without the utilization of WL. tests is provided in Appendix K.2
4

---

Published as a conference paper at ICLR 2024
MPNNs generally applied to learn node representations and are bounded by 1-WL which aggre- gates information from neighbors, thus this section we consider pairwise MRFs defined by 1-WL distinguishable, 2-order A.
We first discuss the equivalence between them in terms discriminating power.
Theorem 3. Given any graphs = (Ag. (AA,,x)... H = (AH, XH) and any 1-WL. distinguishable 2-order A. If at some iteration, the collection of the messages of parallel belief propagation on G and H are different, then 1-WL also distinguishes G, H.
Surprisingly, although the message passing procedure in belief propagation operates on directed edges, we have shown that equivalent to 1-WL in terms of distinguishing power. Continuing from Theorem 3 it's obvious that MPNNs can also approximate the posteriori. In fact, it turns out that the correspondence reveals stronger facts about MPNNs.
Theorem 4. MPNNs can learn marginals that are at least as accurate as belief propagation. For- mally, there exists decoding functions f. such that given any 1-WL distinguishable 2-order A, for arbitrary e > and n E N, there exists a MPNN such that for any graphs with no more than n. nodes, such that:
(xl(f(h.) I q.) S e E V and DKL(g(h,, h2) 9s) S e.for (..))EE.
where q: Qiş are node and edge marginals specified by a local extrema of Bethe approximation, h; the representation of node obtained by the MPNN, DRL is the Ballback-Leible divergence.
Theorem 4 directly indicates that MPNNs are not only capable of approximating node marginals of Bethe approximation, but also edge marginals. In other words, if two nodes are connected, MPNNS are suitable for learning the joint representation of these two nodes! This implication will be exploited in S where extend MPNNs for link prediction in novel and simple manner.
Putting these together, we conclude the section by stating that MPNNs are able to perform exact inference trees. This result naturally aligns with the fact that MPNNs, which shares the equivalent expressiveness with the 1-WL test, can exactly capture tree patterns Zhang et al. (2024).
Corollary 5. Given any graph G and 1-WL distinguishable 2-order A, if G is a tree, there is MPNN that outputs true node and edge marginals of the MRF defined by A.
4.2 ANALYSING EXISTING GNN VARIANTS
In this section we switch to more complex and powerful GNN variants. From previous discussions, is evident that current GNNs are likely capable of approximating variational methods including naive mean field (as shown by Dai et al.) (2016)) and Bethe approximation. Thus, our analysis focuses on the remaining two metrics Section 3 i.e. the complexities of the joint distribution and the target posteriori. For ease of discussion summarize metrics for evaluating the expressive power GNNs as follows.
Definition 6. A class of GNN models can k-l approximate some posteriori p if and only given arbitrary k- WL distinguishable A with maximum order being it satisfies:
It can distinguish all graphs distinguished by iterations of belief propagation in Theorem
It can provide marginals least as accurate as Bethe approximation as in Theorem
Therefore, and are corresponded the complexity of the joint distribution and p is corresponded to the target posteriori. For example, the results about MPNNs in Section 4.1 can be abbreviated as MPNNs can 1-2 approximate p(z, X). We can also derive upper bounds for MPNNs as follows.
Theorem 7. MPNNs can at most 1-2 approximate p(z;
X) for arbitrary G and i Vo.
Similarly with our metrics, we notice that existing GNN variants also extend MPNNs mainly from two motivations: to increase the graph-level expressive power and another solve more plex tasks such as link prediction. Here we also discuss these variants separately according to their motivations.
5

---

Published as a conference paper at ICLR 2024
4.2.1 GNNs THAT FOCUS ON EXPRESSIVE POWER
In this section we investigate GNN variants that focus on increasing the expressive power beyond 1-WL. We shall see that most of them sufficiently improve expressiveness by approximating more complex distributions.
k-GNNs. The first GNN variants we consider are know as the higher-order GNNs, which directly corresponds to the k- WL hierarchy (Morris et al.] 2018 Keriven & Peyré 2019; Geerts & Reutter 2022 Maron et al. (019a). We will focus on N-GNNs Ns that are bounded the by W- test. Note that
k-GN generally computes the representation of single node as the representation of (j.J,....)
Proposition 8. k-GNNs can k-k approximate p(z, X) for arbitrary G.
Remark. Unsurprisingly, k-GNNs provably capture k-order dependencies. At initialization, k- GNNs inject structural information of node tuples into their representations; At each layer, k-GNNs directly pass messages among k-tuples which share k - common nodes. This helps them to sim- ulate the messages between factors and nodes in belief propagation.
Subgraph GNNs. Bevilacqua et al. (2021) proposed a new type of GNNs namely Equivariant Sub- graph Aggregation Networks (ESANs), which provides a novel variant of GNNs namely subgraph GNNs. We consider its node-based variant, which are also studied in Frasca et al. (2022), showing 3-WL upper bound for its expressiveness. Yet, this result is limitation of ESANS and it's un- clear how much the gap is between ESANs and 3-WL. ZZang et al. (2023a) showed that ESANs are equivalent to 3-WL the very specific graph biconnectivity tasks.
Proposition 9. ESANs with node marking policy can 1-3 approximate p(z; X) for arbitrary G.
Remark. Here, we take a step forward and show that ESANs are equivalent to 3-WL in capturing higher-order dependencies. In fact, each subgraph with marked node i can capture i's adjacent 3-cliques, and by aggregating all subgraphs together at each layer. ESANs are able to capture all 3-cliques.
GNNs with liftinng transformations. Bodnar et al. (202 a) designed new WL variants to consider graph structures such as cliques and eycles. We summarize their expressiveness as follows.
Proposition 10. The GNN variants corresponding with SWL/ / CWL with k-clique simplex can 1-k approximate p(z. X).
Remark. Similar with k-GNNs, this variant successfully exploits arbitrary order dependencies. With the specifically designed message passing paradigm, cliques can now send and receive messages as an ensemble. We believe this is the key to model complex distributions, and in Section 5 we will develop novel framework to improve MPNNs' probabilistic inference capacity in similar but simpler and more efficient manner.
Other variants. We notice that there are also other variants including ID-GNNs You et al. 2021 Nested GNNs (Zhang & Li [02T], etc. However, we summarize that they cannot improve MPNNs probabilistic inference capacity.
Proposition 11. The above GNNs can at most 1-2 approximate p(z; X).
4.2.2 GNNs THAT FOCUS ON COMPLEX PREDICTION TASKS
We now list GNN variants that focus on link prediction and more generally joint prediction of multi- nodes. In this section we shall see that they sufficiently approximate more complex posteriori.
k-GNNs. Since GNNs learn representations for k-node tuples, it's natural to expect them being capable of approximating joint posteriori of nodes.
Proposition 12. k-GNNs cannot 1-2 approximate p(Z......, Zig. for arbitrary k 2 2.
Remark. Surprisingly, our result states that k-GNNs are not capable of approximating k-posteriori even for simple pairwise MRFs. This explains why few works apply k-GNNs for link prediction, although 2-GNNs naturally produces node pair representations. Nevertheless, we notice that there is another line of expressive GNNs inspired by FWL,, among which Edge Transformers (Bergen jet al. 2021b) are 2-FWL-MPNNs designed for link prediction. Our next theorem verifies the effec- tiveness of these variants.

---

Published as a conference paper at ICLR 2024
Proposition 13. k-FWL-MPNNS can 1-2 approximate p(Zi ..., Zig X).
Labeling trick. To extend MPNNs for link prediction, SEAL (Zhagg & Chen 2018) adds labels to nodes to tag the target nodes equivalently and differently from the rest of the nodes. This technique was summarized and generalized in Zhang et al. (2020) known as labeling trick.
Proposition 14. k-labeling trick MPNNs 1-2 approximate f(z) not p(z,, Ziz X).
p(z;,
Zie
X but
Remark. The target posteriori might seem strange since it indicates all target nodes indistin- guishable from each other, which means that SEAL cannot learn representations of ordered node tuples: it cannot distinguish the target link (i, between (i, This aligns with the fact that SEAL is only applied on undirected link prediction problems.
Ordered node pair labeling. Similar to SEAL, GralL (Teru al.) 2019). INDIGO (Liu et al. 2021), etc. add labels to target node pairs but now source and target nodes are labeled differently. Proposition 15. MPNNs with ordered node pair labeling 1-2 approximate p(z,, zj X).
Remark. With different labels on the source and target nodes, these methods are able to learn rep- resentations of directed node pairs. This aligns with the fact that these methods are designed for predicting directed links in heterogeneous knowledge graphs.
Source node labeling. Another line of research YYou et al., 2021 Zhu al. 2021 also uses node labels for link prediction, but they only tag the source node, yielding more efficient framework compared with labeling trick. Here we show that they are also able learn node pair representations.
Proposition 16. Source node labeling MPNNs 1-2 approximate p(z,, 25 X).
5 EXTENDING MPNNS FOR MODELING MORE COMPLEX DISTRIBUTIONS
After investigating previous GNN architectures, in this section we would like to study whether we can improve GNNs' expressive power for modeling MRFs well as being more efficient compared with previous approaches. Formally, we also focus on the two targets: modeling more complex distribution and inferring more complex posteriori. We design novel methods namely phantom nodes and phantom edges, for provably lifting GNNs' expressive power of approximating complex distributions and complex posteriori respectively. These two approaches can be easily implemented as preprocessing procedure of the input graphs.
5.1 PHANTOM NODES FOR MODELING HIGHER- ORDER DEPENDENCIES
We discuss extending MPNNs for learning more complex distributions. As previously discussed, the aggregation functions of MPNNs help them to be aware of edges, which naturally corresponds to 2-cliques in MRFs. Intuitively, capturing higher-order cliques requires the aggregation function to pass messages within higher-order cliques of nodes, which calls for different network architectures. To avoid such inconvenience, inspired by belief propagation on factor graphs we add a phantom node to for every maximum clique C in G, and connect te all nodes in C. The phantom nodes then serve as midway of the cliques that stores the messages among cliques of nodes. In fact, we further tag all phantom nodes with an invented label Í that distinguishes them from the ordinary nodes. By applying MPNNs on the augmented graph. We have the following result:
Proposition 17. MPNNs with phuntom nodes can 1-c0 approximate p(z; X).
Relaxation. Sometimes unpractical to find maximum cliques. We can relax our method by only finding cliques with no more than k nodes an approximation to the original approach. Proposition 18. .PNNN with phantom nodes of cliques no more than can 1-k approximate p(z, X).
5.2
PHANTOM EDGES FOR MODELING JOINT POSTERIORI
We discuss learning joint posteriori p(z,,z; X) for node pairs (i.j). Different from the previously discussed node labeling hierarchy, we provide alternate method for link prediction inspired by

---

Published as a conference paper at ICLR 2024
Table 1: Results node classification, Best results of each category are bold. Results with taken from Qu et al. (2022). ). PN stands for phantom nodes.
PPI-1
PPI-2
PPI-10
Algorithm
Accuracy
Micro-F1
Accuracy
Micro-F1
Accuracy
Micro-F1
GCN
76.24+0.10
54.55=0.29
76.82=:0.13
56.10+0.36
80.43=0.10
62.48=0.27
*CRF*
76.33110.21
50.79:10.74
76.27:0.10
49.47:10.63
77.08:1000
52.36:1.72
+SPN*
77.07=0.005
54.15=0.17
78.02:00.05
05.73=+0115
80.59:10.04
61.36#0.11
+PN(ours)
77.45-10.07
60.17:1023
78.81
61.94:0.17
80.8710.03
64.85
SAGE
79.3
62.25=0.11
84.13::0.04
72.93+0.04
92.13+0.04
87.72=0.05
+CRF*
77.43:10.22
54.57
76.27:0.100
49.47-10.63
77.65+1..8
54.4411.34
+SPN*
82.11+0.033
68.5620.07
85.40=0.05
74.45+0.07
95.28+0.02
91.99=0.04
+PN(ours)
82.30-10.02
68.9310.04
8..60
74.64
92.2910.03
0.005
GCNII
77. 07.94
65.79=0.25
84.81
74.54+0.14
97.53+0.01
95.86=0.01
*CRF*
79.98-10.32
61.22:11.10
81.73.0.33
66.37+10.56
92.111:.228
87.10
*SPN*
0..0
67.80=0.11
85.83+:0.44
75.96
97.55+0.01
90.07
+PN(ours)
81.76:10.02
69.0710.113
85.45.10.05
75.28
97.47:10.03
9..84
the specific formulation of the mean field and Bethe free energy, which optimize the following variational free energy on pairwise MRFs respectively:
4ú 4z 2,)
min ( X)), where g (Z)) II (z.) or II (z,).
II
qi (2,)),,(2,)) (K))E
iev
4x 2,, in Bethe free energy models the Compared with mean field free energy, the edge terms joint dependencies between node pairs thus can result in more accurate estimations of marginals. Inspired by this difference, to predict set of target links & {(u1, 01), (w2, ....... that do not appear in the original graph, we add "phantom" term for each target link into the formulation of (Z). yielding the following quasi distribution:
q.(2))g,
(Z)
II % (2,))
II (KJ)EE
Oij (Zi, 2n)
II
Tuo Ze:)
Li (i(z))q;
Iu (zu (o (o(()))
(u.D)E&
Compared with the original formulation, Eq. directly consider the dependence between and v, and by minimizing the KL. divergence we can now also obtain the approximate marginal of quv (Zu, 2.). To reflect this modification in GNNs, add phantom edge for each target link. The phantom edges are tagged with an invented label i that distinguishes them from the original edges. Then, the link representation of (u, v) is computed as f(h.., h.). where h., h. are represen- tations of nodes u, learnt by MPNNs and f MIP. The following proposition states the relation between phantom edges and the altered Bethe free energy.
Proposition 19. MPNNs with phantom edges 1-2 approximates p(zu, z+) given by the modified Bethe free energy with altered distribution in Eq. 2
One major drawback is that when initialized with multiple phantom edges, MPNNs might longer preserve equivariant properties. Since DropGNN (Papp et al. (022 uses a similar technique that deletes nodes randomly but instead increases the robustness and expressiveness of GNNs, also suppose that MPNNs can learn to handle with phantom edges properly. We can also use sim- ilar methods for predicting p(z;, Zj, B., . X), but since it's less practical we left the description together with detailed and practical implementation at Appendix D
may
EVALUATION
We conduct two sets experiments to empirically validate our results and verify the probabilistic inference capacity of methods. Firstly, verify whether our proposed phantom nodes / edges
8

---

Published as a conference paper at ICLR 2024
frameworks can systematically help MPNNS to learn higher-order dependencies and joint posteriori as our theory implies. Secondly, we investigate whether MPNNs with expressiveness for complex distributions and posteriori can also help real-world node classification and link prediction tasks.
Compared algorithms. Our phantom nodes edges are frameworks for lifting the probabilistic inference capacities of general GNNs. We consider popular MPNNs GCN (Kipf & Welling 2016b), SAGE (Hamilton et al., 2017) and GCNII (Chen et al. 2020a) on all tasks. For node classification tasks, we consider SPN (Qu al.) 2022). recent GNN-CRF framework that also lifts GNNs' probabilistic inference capacity. For link prediction tasks, We also compare with recent state-of-the art GNNs on undirected graphs ELPH (Chamberlain et 2023) and BUDDY (Chamberlain al.)
2023).
Synthetic tasks. We generate synthetic graphs and define pairwise and 3-order potential functions. Marginals are obtained by running loopy belief propagation and are used as the training target of GNNs. The results are in Table B The main metric that evaluates the similarity between GNNs and marginals is the KL divergence, where our methods systematically improve over base GNNs. We also notice that for predicting edge and node pair marginals, the KL divergence between our approaches and belief propagation does not reduce to O. We hypothesis the reason to be the limited design of the output layers. Nevertheless, our approaches steadily enhance the performance of base GNNs in different tasks and metrics.
Real-world tasks. We consider two types of tasks. For Node Classification we consider the PPI ZZtmik& & Leskovee 2017 Hamilton al., 2017) dataset, where each node has 121 labels. To make the dataset more challenging we try using only the first 1/2/10 training graphs, yielding PPI-1, PPI-2 and PPI-10. We have rerun GCNs, SAGE, GCNII and their phantom node enhanced versions on these datasets to jointly predict all the 121 labels at once, making it more challenging than Qu et al.) (2022). The MPNNs and their phantom node enhanced versions share the same hyperparameters and network architectures. Empirically, the phantom nodes work well especially when training data is limited (PPI-1), due to their ability of performing data augmentation with the awareness of higher-order structures.
For Link Prediction we consider the Planetoid citation networks Cora (McCallum et al. 2000). Citeseer (Sen et al.] 2008) and Pubmed (Namata et al. 2012). We apply our phantom edges on GCN, SAGE and GCNII. The results are Table 2 Our methods can systematically improve MPNNs for real-world tasks. The effects of phantom edges are significant when the graphs are complex, which demonstrates phantom edges are able to model link-level structures by aggregating representations of nodes at each end of the target links.
Algorithm
Cora
Citeseer
Pubmed
Algorithm
Nodes
Edges
Node pairs
GCN
40.57=1.65
51.21+11.33
29.97
+PE(ours)
54.69=1.07
64.29+1.08
41.28=0.88
GCN
BCE loss
0.045
1.008
1.373
KL div
0.003
0.835
0.748
SAGE
43.03-2.39
43.22-11.92
16.16.10.65
BCE loss
0.044
0.931
1.368
+PNR
+PE(ours)
46.64=2.61
39.45+22.48
34.91=1.71
KL div
0.000
0.602
0.729
GCNII
51.52-1.22
53.41110.79
30,9310.92
BCE loss
0.044
0.991
1.372
GIN
+PE(ours)
60.09_3.13
67.80111117
1..10
KL div
0.001
1.021
0.765
BCE loss
0.043
0.964
1.373
ELPII
1.99
64.35.11.53 58.2311144
32.94 1..3
+PNE
KL div
0.000
0.947
0.694
BUDDY
1..02-1.37
Table 2: Results on link prediction tasks. The Table 3: Results on syntactic tasks. PNE: phantom nodes edges.
metrics are Hit@ 10.
7 CONCLUSION
In this paper, develop strong theoretical connections between GNNs and variational inference, show that MPNNs can achieve good estimations of node and edge marginals, and further investigate various GNN variants from the expressiveness and link prediction perspective while corresponding them to different inference problems in graphical models. We provide new understandings about how and why previous GNN variants works well under different settings. We develop new methods that provably lift MPNNs for modeling more complex distributions and predictions. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our approaches.

---

Published as a conference paper at ICLR 2024
REFERENCES
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural
networks. In International Conference on Learning Representations, 2020. URL. https:
//api. www.ssssnnnccccolaa.ccoo http:/hhhhoaa..ccooooooooaaaaaa.
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. ArXiv, abs/1909.01311 2019. URL https:://appptt www.ntp..eeemaaammmmma..mmmm www.aeeeaatntnteeee http://ti.....a..aooooooooooaaaa
Pablo Barcel'o, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Neural Information Processing Systems, 2021. URL https:
//api. www.seetttnnncholonoooo wwtp/ooppssD:
Leon Bergen, Timothy J. O'Donnell, and Dzmitry Bahdanau. Systematic generalization with edge transformers. In NeurlPS, 2021a.
Leon Bergen, Timothy O' O'Donnell, and Dzmitry Bahdanau. Systematic generalization with edge transformers. In Neural Information Processing Systems, 2021b. URL https://app.
semanticschol org/ parg:/Corput1::24473333
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, G. Bal- amurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- org/
works. ArXiv, abs/2110.029100 2021. URL c
Coxpus_D:2384077)
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang. Pietro Lio', Guido Montúfar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: networks. In Neural Information Processing Systems, 2021a. URL https: //ap semant cscho aarooolar.co ar. Orgg/CorpuSTD)
235606230
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pictro Lio', and Michael M. Bronstein. Weisfeiler and lchman go topological: Message passing simplicial net-
works. ArXiv, abs/2103.03212, 2021b. URL https: aapi. www.sstiescoooolsee... org/
CoopuusDD2331106522
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions
Pattern Analysis and Machine Intelligence, 45:657-668, 2020. URL https://app.
semanticscholest htwpioolrrrrrraaeooooooo Corpps Sttpchhooa...orr//oorsssia:/111 219008611
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 33 2013.
Jin-Yt Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 22:389-110, 1989.
Jin-Yr Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, (2(4):389-41) 1992.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. ICLR, 2023.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. International Conference on Machine Learning, 2020a. URL https:
7/api //api.semanticscholaaa org wwtp://///...://00....
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? ArXiv. abs/2002.04025, 2020b. URL htt.a///coapp.eenttccccccooo.a
orc//CorpusDD:2110555
P Clifford and JM Hammersley. Markov fields on finite graphs and lattices. 1971.
10

---

Published as a conference paper at ICLR 2024
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. ArXiv, abs/2110.00577, 2021. URL https://apii stt.app....aaaiscshssaaaaaaaa org/
CorpusID:2382553
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. International Conference on Machine Learning, 2016.
Fabrizio Frasca, Beatrice Bevilaequa, Michael M. Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. ArXiv, abs/2206.1 140, 2022. URL
Floris Geerts and Juan L. Reutter. Expressiveness and approximation properties of graph neural semant. wws.mnntisscooooooooooo ccccccccllacccco org/
networks. ArXiv, abs/2204.04661, 2022. URL
CorpusiD:2240848556
Lukas Gianinazzi, Maciej Besta, Yannick Schaffner, and Torsten Hoefler. Parallel algorithms for finding large cliques in sparse graphs. Proceedings of the 33rd ACM Symposium on Paral- lelism in Algorithms and Architectures, 2021. URL https:/ wtt.app....aaiiii.mmmmmmmm www.etiiiacoool.........
org/Corpus TD: 235689574
Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80:797 844, 2012.
Fangda Gu, Heng Chang. Wenwu Zhu, Somayeh Sojoudi, and Laurent Ghaoui. Implicit graph neural networks. ArXiv, 1bs/2009.06211, 2020. URL https: /api. semanticscho.....
org/CorpusID: 221 655683
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
Tom Heskes. Stable fixed points of loopy belief propagation are local minima of the bethe free energy. Advances in neural information processing systems, 15, 2002a.
Tom M. Heskes. Stable fixed points of loopy belief propagation local minima of the bethe free energy. In NIPS, 2002b. URL https::///// http://///.///////oaooooaaaooooo 45429087
semanticcchhi wtwpchoooar..oo/oouusssl.l.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Alexander Rieck, and Karsten M. Borgwardt. Topological graph neural networks. ArXiv, abs/2102.07835, 2021. URL
attpss//aple wtw.::i.sssmmttnscccsseecoe
:
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In
Neurul Information Processing Systems, 2019. URL
Orq/CorpusID. 1aee::5522280 152282292
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization.
CoRR, abs/1412.6980, 2014. URL htttss////aap http://aweaa.eeooooooooooooo/ooa 6628106
Thomas Kipf and Max Welling. Variational graph auto-encoders. ArXiv, abs/161 0101661110730... 201
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: wet.ii669.00000 2016b.
Solomon Kullback and R. A. Leibler. On information and sufficiency. Annals of Mathematical Statistics. 22:79-86, 1951.
120349231
Juncheng Liu, Bryan Hooi, Kenji Kawaguchi, and X. Xiao. Mgnni: Multiscale graph
ral networks with implicit layers. ArXiv, abs/2210.08353, 2022a. URL https::/appi
ientanttisccholo wttphooorr..rg/oouuuuuuuooo : 252918651111
Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and X. Xiao.
Eignn: Efficient
infinite-depth graph neural networks. ArXiv, abs/2202,10720, 2022b. URL httpss//app..
semant cschol ar. ort.arrg/ooppsstt:25555555 6994

---

Published as a conference paper at ICLR 2024
S. Liu. Bernardo Cuenca Grau, Ian Horrocks, and Egor V. Kostylev. Indigo: Gnn-based induc- tive knowledge graph completion using pair-wise encoding. Neural Information Processing Systems, 2021. URL https://apppp.... semaeeiisaacccccaaaaaaao
Haggai Maron, Heli Ben-Hamu. Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ArXiv, abs/1812.09902. 2018. URL https://aatttt
CorpusTD: :6:
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. ArXiv, abs/1905. 10000.11166....000.11..1..111111 1136,, 2019a. oe
/tappp:://ap....
CorpusID: 166.288711622277
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. ArXiv, 0tbs//901.09342 2019b. URL httpss///pp...emannccccccco..
CorpusID:5931677
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning, Information Retrieval, 3:127 3:127-163, 2000,
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gau- rav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neu- ral networks. In AAAI Conference on Artificial Intelligence, 2018. URL https://api.
semanticschol..
Orgg/oorpusDD. :2:119909099
Kevin P Murphy, Yair Weiss, and Michael I Jordan. Loopy belief propagation for approximate inference: an empirical study. In Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, pp. 467-475, 1999.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann ma- chines. In International Conference on Machine Learning, 2010. URL //api.
semanticscholast htw.aaaa..org/oooous:111553333
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, pp. 1, 2012.
Jaroslav Nesetril and Svatopluk Poljak. On the complexity of the subgraph problem. 1985, URL https://api. www.:eessseennncchcl.......o. htt.://........roooorooo11111111
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network ex-
tensions. ArXiv, abs/2201. 2022. URL https: /atss:///pp.... api www.sticschooeeeeee... htt.choooaarro/ooooooo
Corpus 1D:
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random
dropouts increase the expressiveness of graph neural networks. Neural Information Processing Systems, 2021. http:://wppp...caaaaa...cooooeer
Junyoung Park, Jinhyun Choo, and and Park. Convergent solvers ArXiv, htt.:/aww....aaooooooo.ooooooora
Jeffrey Pennington, Richard Socher, and Christopher D) Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Chen Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Or-
dered subgraph aggregation networks. ArXiv, abs/2206. 11168, 2022. URL https: :/api. Iemmant irrrantisscholare wwwp
Meng Qu, Huiyu Cai, and Jian Tang. Neural structured prediction for inductive node classification.
arXiv preprint arXiv:2204.07522 2022.
Victor Garcia Satorras and Max Welling. Neural enhanced belief propagation on factor graphs. In
International Conference Artificial Intelligence and Statistics, pp. 685-693. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2024
M. Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutionall networks. Extended Semantic Web Confer- ence, 2017. hww.lttps://// /ttp::///ppp.e semant wtt.:aaww...acaaoo..........aaaa 5458500
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. In The Al Magazine, 2008
Alex Smola, Arthur Gretton, Le Song, and Bernhard Scholkopf. A hilbert space embedding for distributions. In IFIP Working Conference Database Semantics, 2007. URL https:// //
api semant. cscho laroollrrooo org/ httpg//Crpuuspp.p 44300
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 990-998, 2008.
Komal K. Teru, E. Denis, and William L.. Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, 2019. URL https://app. semanticschen
Erik H. Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets.
In Neural Information Processing Systems, 2021. URL http://app..eaaiiiccccccccccccca
ort/CorruusD::2329777
Kristina Toutanova, Xi Victoria Lin, Wen tau Yih, Hoifung Poon, and Chris Quirk. Compositional learning of embeddings for relation paths in knowledge base and text. In ACL, 2016.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 12-66 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 18X0v 00826 2018.
Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, Bethe free energy, kikuchi approxima- tions, and belief propagation algorithms. 2001. URL org/Corpus ID: : 13980420
Jonathan Yedidia, William T Freeman, and Yair Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on information theory, 51()): 2282-2312, 2005.
Jiaxuan You, Jonathan M. Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. AAAI Conference on Artificial Intelligence, 2021. URL https://api,
semanticscholas org/Corpust: 23186887333
Alan Yuille and Anand Rangarajan. The concave-convex procedure (ccep). Advances in neural information processing systems, 14, 2001.
Alan Loddon Yuille. A double-loop algorithm to minimize the bethe free energy. Energy Minimization Methods in Computer Vision and Pattern Recognition, 2001. URL https:
//api. www.ssssnnticccclar...ooo..
11:025333
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power
of gnns via graph biconnectivity. ArXiv, abs/2301.095t0 .09505, 2023a. URL https://api. semanticscholar.co wttp:/ooa.....o//ooouooo....aia.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for gnn expressiveness. In International Conference Ma- chine Learning, 2024.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Neural Information Processing Systems, 2018. URL https:/ /api. semanticschol.. orq/
Corpus1D:3573167
13

---

Published as a conference paper at ICLR 2024
Muhan Zhang and Yixin Chen. Inductive matrix completion based graph neural networks. In ICLR, 2020.
Muhan Zhang and Pan Li. Nested graph neural networks. ArXiv, abs/2110.13197 2021. URL https:/ /ettss//app... appi. semanticscholaat wtt.e/ioooo..ooooorroououuuuaa 2398885522288885
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using graph neural networks for modti-node representation learning. In Neural Information Processing Systems, 2020. BRRl:ttp:://aptt http::///aap.eemiiiiciic..ae www.etiisccoooo...oo.....
Zhen Zhang. Mohammed Haroon Dupty, Fan Wu, and Fan Wu. Factor graph neural net- works. ArXiv, abs/2308.0088 00887, 2023b. URL https://api semanticschholl.
CorpusID:2272764655
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplift-
ing any gnn with local structure awareness. ArXiv, abs/2110.03753, 2021. URL https:
semant s/p....e www.emmatnssccolaa.rrrr.... www.olaaa..rggogooooooooooeooeee Cttp:o/oo/o/ :2:r:uu11:::283317333
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford net- works: A general graph neural network framework for link prediction. Neural Information Processing Systems, 2021. URL
235422273
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):110-ii198 2017.
14

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Extended Related Works
16
B Weisfeiler-Lehmen tests
17
B.1
I-WL (Color Refinement)
17
B.2 W-
17
B.3
k-FWL
17
B44
of k-WL/k
18
C Discussions about the Fixed Point Properties of MPNNs and Bethe approximation
18
D Extended Discussions about Phantom Nodes Edges
19
D.I Phantom Nodes
19
D.2 Phantom Edges
20
E
Experimental Details
21
E.1
Datasets
21
E.2
Contigurations
22
F.3
Additional Experiments
23
F
Proof w.r.. invariant MRFs
23
F1 Proof of Lemmal
23
F2 Proof of Theorem
24
G
Proof w.rlt MPNNS
25
G.
Proof of Theorem
................................
25
G.2
................................ -
Proof of Theorem 4
27
G.3
Proof of Theorem 20
................................
29
G.4
Proof Corolloary
................................
32
G.5
Proof of Theorem
................................
32
H
Proof w.rt. Approximating Complex Distributions
33
H
k-ICWL: A Tool for the Proof
................................
33
H2
Proof. w.r.t. E-GNNS
................................
35
H13
Proof w.r.t. Subgraph GNNs
................................
36
H 4
Proof w.r.t. SWL./CW/
................................
36
H.
Proof w.r.t. Other Variants
................................
37
Proof w.rt. Approximating Joint Posteriori
38
T.1
I-Node Labeling: A Tool for
38
1.2
Proof w.r.t. k-GNNs
................................
39
1.3
Proof w.r.t. -.WNN
40
1.4
Proof w.r.t. laheling trick
41
L.S
Proof w.r.l. Ordered Node Labeling
41
Proof w.r.t. Source Node Labeling
41
Proof w.r.t. Phantom Nodes Edges
42
J.1
Proof Proposition 17
42
1.2
Proof Proposition 18
42
15

---

Published as a conference paper at ICLR 2024
J.3
Proof of Proposition 19
42
K The expressiveness of GNNs without the WL hierarchy
43
K A redefinition of the metrics
43
2 Results w.r.t. hode-level expressiveness
43
33
Proofs
44
A EXTENDED RELATED WORKS
In this section we discuss more related works that aims to improve GNNs.
Higher order GNNs. Since the works of Xu et al. 20188; Morris et al. (2018) that relate GNNs with the 1-WL tests, straightforward extend GNNs by imitating higher-order WL tests. Pre- cisely, k-order WL tests assign colors for k-tuples of nodes and perform color aggregation between different tuples. Similarly, instead of learning representations for nodes, many works choose to apply the message passing paradigm in higher-order WL tests to GNNs and directly learn represen-
tations for node tuples (Morris et al., 2018 Maron et al. 2019a 2018 2019b Keriven & Peyré 2019
Azizian & Lelarge 2020) Geerts & Reutter 2022).
Subgraph GNNs. Since the higher order GNNs are often too expensive for larger graphs, many works try find cheaper ways to design more expressive GNNs. variety of works feed subgraphs to MPNNs. At each layer, a set of subgraphs is generated according to some predefined permutation-
invariant policies, including node deletion (Cotta al. 202I), edge deletion Beviiaaqua al. (2021).
node marking (Papp & Wattenhofer 22022.. ego-networks (Zhao et al. 2021; 22aaggaagggaa & Li [202] You
al.] (202). We will focus on the unified ESAN framework proposed by (Bevilaquua et al. (202))
Qian al. (2022): Frasca et al. (2022) studied the expressive power of different branches of subgraph
GNNs.
Substructure counting GNNs. There is another way design GNNs that surpass 1-WL. by con- structing structural features for GNNs. Chen et al. (2200b) showed that regular MPNNs cannot capture simple patterns such as cycles, cliques and paths. Bouritsas al. (2020); Barcel'o et al. (202T) proposed to apply substructure counting as pre-processing, and add substructure information into node features. [Bodnar al. (2021b ab: Thiede al. (202T); Horn et al. (202I) 1) further designed novel WL variants and proposed fully-neural approaches that captures complex substructures.
GNNs for link prediction. Standard GNNs learn representations for each node. Early methods such GAE Kipf & Welling (2016a) use GNN as an encoder and decode link representations as a function over node representation pairs. These methods are problematic in capturing complex graph structures, and might lead to poor performance. Later on, labeling trick was introduced by SEAL/Zhang & Chen (2018) and adopted by GraiL[Teru et al. (2019). (GMC//hang) & Chen (2020), INDIGO Liu et al. (2021), etc. These methods encode source and target nodes mark them differ- ently from the rest of the graph, and are proved to be more powerful than GAF. ID-GNN You et al. (00T)) and NBFNet Zhu et al. (202T) ) both augments GNNs with the identity of the souree nodes. Besides, All-path Toutanova et al. (2016) encodes relations linear projections and proposes to ef- ficiently aggregate all paths with dynamic programming. However, All-Path restricted bilinear models, has limited link prediction capability and is also not inductive. Edge Transforerr [Bergen al. (2021a) utilizes attention mechanism to learn representations for nodes and links. While also follows the 2-FWL message passing procedure, operates directly fully-connected graphs and have no proposals for simplifications as we do, thus it is not scalable to larger graphs. ELPH and BUDDY (Chamberlain et al. 2023) incorporate neighbor counting into node features to enhance the link prediction performance of MPNNs.
PGM-GNN combined methods. There are also works that aim to combine GNNs and PGMs to obtain better graph representations. Dai al. (2016) first proposed to parameterize the mean field iterations and loopy belief propagation of PGMs and construct two neural architectures, one of which is similar MPNNs. Compared with work, Dai al. (2016) only showed that MPNNs
16

---

Published as a conference paper at ICLR 2024
parameterize the mean field iterations of simple pairwise MRF with identical potential functions. Satorras & Welling (2021): Zhang et al. (2023b) propose to parameterize the loopy belief propa- gation inference algorithm for higher-order PGMs. |Satoras & Welling (202I) propose to directly parameterize the loopy belief propagation algorithm, which operates on edge-level messages. /Zhang et al. 2023b) propose different message passing paradigm which consists of two distinct modules namely factor-(o-variable module and variable-to-factor module. To summarize, these frameworks fundamentally different with typical GNNs. Compared with their work, our proposed phantom node framework can also capture higher-order PGMs, but is built on MPNNSs and thus can provably improve the probabiliiticc inference capacity of different MPNN architectures, (Qu al. (2022) pro- pose to parameterize the potential functions of CRFs with GNNs and propose novel method for training the CRFs. Compared with our work, they are only able handle pairwise potentials and GNNs only serve as component of the training and inference framework while we aim to improve GNNs themselves to be able to capture higher-order MRFs.
B WEISFEILER-LEMMAN TESTS
In this section we introduce the Weisfeiler-Lehman (WL) tests and their variants.
B.1 WI (COLOR REFINEMENT)
The classic 1-WL test (Weisfeiler & Leman 1968) maintains color for each node which is refined by aggregating the colors of their neighbors. It can be easily applied on node-featured graphs (Xu al. 2018) in Algorithm
Algorithm 1: The 1-WL test (color refinement)
Input : G X)
1 x- 0;
cl + hash(x.)) for all v E Vo;
while not converge
C hash(d (1 I (())))
1 1+1+1;
end
return (1c, V vo]}::
The iteration converges when the partitions of nodes no longer changes. The 1-WL test decides two graphs are non-isomorphic if the multisets of colors the two graphs are different. The WL algorithm successfully distinguishes most pairs of graphs, apart from some special examples such as regular graphs. Similarly, given subset of nodes C. 1-WL. define its color as {(d, u E C)). and 1-WL distinguishes two set of nodes if the colors of them are differernt.
B.2 &-
The k-WL tests extend 1-WL to coloring k-tuples of nodes as in Algorithm where we use v to denote tuple of nodes, G(v) for ordered subgraphs, The neighbors (v) are defined as follows: assume v = (N1,..,, Uk), then A/((w) = (o)) (v)), where
(b) (1 U--1, 2411 ux) uu VB
B.3 4-FWL
The k-F (Cai et al. 1989) test is equally expressive with the (k: 1)-WL test. It has the same ini- tialization with (k- WL. The neighbors A (v) are defined follows: assume (Ui.... Uk),
then MeenA(((e) (²) [[At t (v) u E v)J. where
Nà (v) ((u, U2,... Uk), (U1, ,.,,,, Uk)..., (U1, m, U, Ut)).
17

---

Published as a conference paper at ICLR 2024
Algorithm 2: The k- k-WL tests
Input : G = (A,
I 1 0;
c t -hash(G'o)) for all E VV: while not converge do
c+1 f- hash(c.. {[ u (o))))
1+
end
return
(1/2g v Va for all e E w]}:
Algorithm 3: The k-FWL tests
Input :G (A, X)
I O=0;
e < -hash(G'v)) ')) for all v E Vi
while not converge do
c+1 hash(c (clllllE
1+1+1;
end
return
(1c6 e Vg for all v e v}}
B.4 COLORS OF G-WL/ k-FWL
From the previous discussions WL and k-FWL both assign colors for k-tuples of nodes. The color of the graph G is defined by
cg Hash([[cc y* H)).
Similarly, given any subset of nodes S C V, we also define its color as
cs = Hash(ffc. 1 s*))).
C DISCUSSIONS ABOUT THE FIXED POINT PROPERTIES OF MPNNS AND BETHE APPROXIMATION
In the previous discussion we have seen that MPNNs are capable of approximating local extrema of the Bethe approximation. To further extend our results we ask: can MPNNs capture all local extrema of the Bethe approximation? We first notice that recently class of neural networks (Bai al. 2019) treat the fixed points of their layers as outputs. To better discuss the properties of MPNNs, we try to establish general correspondence between MPNN layers and the Bethe free energy in the perspective of fixed points.
Theorem 20. Given 1-WL distinguishable 2-order A. there is a MPNN layer L such that all fixed points of = CoCouat H, X),, ),, A) implies local extrema of the Bethe free energy of the MRF given any graph G, and also all local extrema of Bethe approximation there exists a function such that given any graph G (of the size n), let H be the set of fixed points local extrema of Bethe approximation, then is always surjective from H
implied in C. That is,
of L and S be the to S.
Recall that the fixed points of Bethe approximation contain not only node marginals but also edge marginals, thus Theorem 20 confirms the fact that MPNNs are actually able to learn edge represen- tations. In practice, there are several fixed-point MPNNs (Gu et al. 2020 Park et al. 202 Liu et al. (222b]a) that work well on node classification, and Theorem 20 suggests the possibility of using them to learn node and edge marginals of Bethe approximation.
18

---

Published as a conference paper at ICLR 2024
D EXTENDED DISCUSSIONS ABOUT PHANTOM NODES! / EDGES
In this section we give extended description of the proposed phantom nodes / edges methods.
D.1 PHANTOM NODES
We summarize the procedure in Algorithm For the original phantom nodes, the function FindCliques finds maximum cliques in given graph; for the relaxed version the function finds all cliques with no more than nodes.
Algorithm 4: The Phantom Node Procedure
Input G = (A
Output: G XA
C 1--Findliiquee (G);
(N,d) Shaape (X);
+ +
d
Ā -Zeros (Ñ, N):
X Zeros (Ñ, d);
ANN. A;
X.N.d + X;
p ==N+ =
for CECO
X p.d 1;
12
for do
ALp + 1;
13
4 Ap. f 1;
15
end
16
end
return G= (A,
The procedure is standard and easy to implement, but it might not suit most practical MPNN archi- tectures such GCNs, SAGE, because the MPNNs will have learn from data treat the phantom nodes (tagged with only the last dimension of the input node feature) are differently from the regular nodes. practical implementation is realized follows, where we use i, refer to regular nodes and p to refer to phantom nodes.
h COM (h., AGG'pN (((n) PENON)))) AGG (((h) ((N])ee()))) hot1 CÓM' (G (((tlieN())))
where 1 is the set of phantom nodes.
Algorithm complexities. We now discuss the time and space complexities proposed Algo- rithm and compare with k-GNNs.
The major complexities come from finding cliques in line Suppose the input graph contains N nodes. In worst cases when the graph is dense (contains ((N2) edges), FindCliques would
N )
return
O(Nk) results (suppose k << N) and takes more than O(Nk) time
Nesetril & Poljak 1985). In this case the augmented graph & contains Ñ = O(N*) nodes and OKkN*) edges. Applying MPNNs such augmented graph then takes OkNN*) time each layer (for ease of comparison we only consider terms w.r.t sizes of graphs). To summarize, the algorithm takes (NN)) space and (k:Nk) time. k-GNNs takes O(N*) space and (k-Nkk+) time.
19

---

Published as a conference paper at ICLR 2024
(a)
(d)
Figure 1: Relation between node labeling and phantom edges.
If the input graph is sparse, our method is far more efficient than k-GNNs when the number of k-cliques much less than N Suppose there are cliques, then the augmented graph contains O + C') nodes and O(M + kC)) edges, where M is the number of edges in the original graph, and each layer of the MPNNs only takes O(M+KC + time and ( + C) space. The time complexity of finding cliques in sparse graphs is hard to estimate, but there are empirically efficient algorithms that can effective find k-cliques in large graphs (see, eg. Gianinazzi et al. (2021), ). Since F Findcliqque quees one-time pre-processing procedure, the proposed algorithm much more efficient than k-GNNs.
Limitations. From the above analysis it is evident that when the input graph is large and dense, the proposed method might add large amount of phantom nodes the input graph, making the algorithm inefficient especially when i is set to a large value. Even so, the proposed method still more efficient than k-GNNs.
D.2 PHIANTOM EDGES
It's simple to extend MPNNs to learn edges of different types, and our practical implementation here follows the common approaches Schlichtkrull al. (2017). Let & denote the of regular edges and & the of phantom edges. Let NV() denote the neighbors of via regular edges and (i) the neighbors of i via phantom edges. Our practical implementation is
h1+1 h,+1 Xh!+1
h COM' (hi, AGG ((
h1 CôM' (k, ((
Note that, we can also implement phantom edges for predicting p(Z,, Ziz X). This is done by noticing that belief propagation factor graphs also produces marginals for factors, i.e., eliques of nodes. By adding a phantom node which is connected with i ik. we have shown in the proof of 18 that by applying MPNNs we can also learn the posteriori p(z,, Zia X.. even if the nodes .... in are not connected in the original graph.
Proposition 17
Algorithm complexities. We now discuss the time and space complexities of the proposed phan- tom edges and compare with node labeling methods. Given a graph G with N nodes and M edges, we are asked to predict a batch of links &. Simultaneously predicting all links in & equiva- lent to applying MPNNs on an induced graph with N nodes and A + _ edges thus requires O(N + M + (&() time. For labeling trick methods, they need to rerun GNNs for each target link thus requires O(E(N + M)) time. For source node labeling methods, they need to rerun GNNs for target links with different source nodes. Therefore, suppose the target links & contains S different source nodes, they require O(S(N + M)) time.
Relation with node labeling methods. We now discuss the relation between methods and node labeling methods. We will mainly focus on the ordered labeling trick (Zhang et al,, 2020 Liu al. 202T) and the partial node labeling (Zhu al. 2021
20

---

Published as a conference paper at ICLR 2024
Table 4: Statics of datasets.
Dataset
Task
# Features
# Labels
# Nodes
Edges
PPI
NC
50
121
56944
818716
Cora
LP
1433
2708
5278
Citeseer
LP
3703
1
3327
4676
Pubmed
LP
500
18717
44237
We first show that labeling trick can be seen as a special case of the phantom edge. Suppose given graph G, the target links & only contain one link & = {(s, In this case, we only add one phantom edge (s, I) into the original graph (Figure (b)). Labeling trick methods add additional labels to mark 8, differently from the rest of the nodes (Figure [ (a)). As we shall see later, both the two methods aim to mark the target link (s, uniquely: that is, for any graphs G, H and s,t VG.P.g VH. obviously
G~H
G H +
There exists an isomorphism π from to H. (()) = p. (() = q. (3)
where G, fl are graphs induced by phantom edges and G, H are graphs induced by labeling trick. Therefore, both the methods aim tag the target link uniquely.
Now we discuss how partial node labeling and general phantom edges extend the above methods to obtain more efficient variants. As we shall see later, both the methods aim to produce representations of multiple links within one run of GNNs. Since the labeling trick methods can only compute the representation of one link, partial node labeling methods relax this deficiency by modifying the node-level labels. By only considering the source nodes (or the tail nodes), they are able to produce representations of links that share same source (or tail) node within one run GNNs (Figure M (c)). In contrast, our methods work at the edge level: we extend (b) in Figure [ by allowing more than one phantom edges to present simultancously (Figure (d)). Compared with the partial node labeling methods, the advantage of method is that it is more flexible, since allow the simultaneous computation of link representations that not necessary share the same source (tail) node. The limitation, however, that our methods no longer strictly preserve the isomorphism property in Eq.
E EXPERIMENTAL DETAILS
In this section we describe our experimental setup in more details.
E. DATASETS
Statics of datasets are in Table
For node classification tasks, the experiments follow the settings in Qu al. (2022). For fairness we have rerun the results GCN (Kipf & Welling 2016b), SAGE (Hamilton et al. 2017)) and GCNII Chen et al. (2020a) on the datasets. We train the GNNs output 121 dimensional vectors, with each dimension corresponds to one of the labels.
For link prediction tasks, the experiment configurations follow the settings in Chamberlain et al. (202).. To make the tasks more challenging we record the Hit@ 10 metric. For all tasks we use negative sampling to generate negative targets. At training time the message passing links are equal to the supervision links, while at test time disjoint sets of links are held out that are never seen at training time. We random generate 70-10-20 percent train-val-test splits which is the same as Chamberlain et al. 2023). The predictor of the model is designed as p(u, v) MLP(h,, O h.) where h. h2 are node representations of u, respectively.
For syntactic tasks, first randomly generate set of graphs. Then, define potential functions of MRFs, For simplicity we select the following potential functions:
2, Zjo
(2 22)
2,
else,
21

---

Published as a conference paper at ICLR 2024
for all edges, and select
[10, 2; Zk: V3 22,
(
else,
for all 3-cliques. We then run loopy belief propagation on the graphs and obtain node marginals and edge marginals. We also obtain node pair marginals by adding phantom terms as discussed in Section These marginals are use as training targets for GNNs, where we optimize on the cross entropy loss. We also evaluate the KL divergence between the marginals produced by GNNs and the marginals produced by loopy belief propagation.
E.2 CONFIGURATIONSS
Phantom nodes for node classification. We apply our phantom nodes on GNNs without changing hyperparameters or network structures. We choose the Adam (Kingma & Ba 2014 optimizer, with learning rate x 10-3, weight decay O.
We set the numbers of hidden neurons to 128, and the number of layers to We use ReL.U (Nair & Hinton 2010) the activation function. We set dropout rate to be 0.5 and apply layer normalization.
GCN (Kipf & Welling, 201
SAGE (Hamilton et al., 2017). We set the numbers of hidden neurons to 1024, and the number of layers to 2. We use ReLU (Nair & Hinton 2010) as the activation function. We set dropout rate to be 0.5 and apply layer normalization.
GCNII (Chen et al. 2020a). We set the numbers of hidden neurons to 1024, and the number of layers to 5. We use ReLU (Nair & Hinton, 2010) as the activation function. We set dropout rate to be 0.5 and do not apply layer normalization.
Implementation with phantom nodes. input graph we find all maximum cliques.
The configurations of GNN layers are the same. For each The layers are implemented as follows,
H²+1 H + App H pht
H = Layer, (H', Areg);
H'+1 Layer, [H' Apha),
where A is the adjacency matrix, Aphi is the adjacency matrix w.r.t. phantom nodes, i.c. only edges connected with phantom nodes are considered. Areg the original adjacency matrix. Apht the normalized version of Aph.
Phantom edges for link prediction. We apply our phantom nodes on GNNs without changing hyperparameters or network structures. We choose the Adam (Kingma & Ba 2014) optimizer, with learning rate x 10-4, weight decay 5 10-4
GCN (Kipf & Welling, 2016b). We set the numbers of hidden neurons to 1024, and the number of layers to 2. We use ReL.U (Nair Hinton 2010) as the activation function. We set dropout rate to be 0.5 and apply layer normalization.
SAGE Kippf & Welling, 2016b).
We set the numbers of hidden neurons to 1024, and the number of layers to 2. We use ReLU (Nair & Hinton 2010) as the activation function. We set dropout rate to be 0.5 and apply layer normalization.
20166)..
GCNII (Cen et al. 2020a). We set the numbers of hidden neurons to 1024, and the number of layers to We use ReLU (Nair & Hinton 2010) as the activation function. We set dropout rate to be 0.5 and do not apply layer normalization.
22

---

Published as a conference paper at ICLR 2024
Table 5: Results on the DBLP dataset built by
by/Quuuuuuuu Qu al. (2022).
Model
GAT
GAT-SPN
GAT-PN
GCNII
GCNII-SPN
GCNII-PN
Accuracy 79.16
84.84
86.34
81.79
83.57
85.08
Implementation with phantom edges. The configurations of GNN layers are the same. We set the batch size 1024. At each iteration, we randomly select 1024 edges as positive and negative training targets, and add 1024 phantom edges to the original graphs. The layers are implemented as follows,
H Layer, (H' Areg) + ALayer, (H' Aphe), where Areg g is the original adjacency matrix, Apht is the phantom edge matrix. To predict the link (i,j) we have
Vij MLP(h; O h2),
where @ is the Hadamard production.
E.3 ADDITIONAL EXPERIMENTS
We also conduct additional experiments on DBLP (Tang et al. 2008 datasets. The experimental setup follows Qu et al. (2022), where papers from eight conferences are treated as nodes, and are splitted them into three categories for classification according to conference domains. For each paper, the mean Glo Ve embedding (Pennington al. (2014) of words in the title and abstract as node features. The
graph is formed as the citation graph of papers published before 1999, from 2000 to 2009, after 2010 respectively. The results are in Table
F PROOF W.R.T. INVARIANT MRFs
F.1 PROOF OF LEMMA 1
Lemmal 1.
Suppose there is an algorithm F. given any graph G = (A, F maps its structure A a MRF pc F(A). Then, satisfies that for any permutation π [m]] [n] and A:
Pa(G) (T (X), (Z)) pa (X. Z)
if and only if pG be represented in the form / with potentials given by Vec A(C, A) where A is crrmutation-invariann
A(C, A) = A(T(C), V.C.G, G, and क [m] + [m].
Proof. Since MRFs can be written in the form of
p(,
II
v (Zi, x;)
II (z(z)),
iev
GEc
therefore F can be seen as function that maps graph G = (A, X) to a set of potential functions ( C' Co V.).
1-+2. Given any F. we define the corresponding A follows. Given graph G. can identify all graphs that are isomorphic to G, and we suppose these graphs compose a set G which we refer to as the isomorphism set of G. For each isomorphism set G of arbitrary graph, arbitrarily specify an element Go in g and refer to it as the isomorphism prototype of all graphs in G. Then, for any graph, G we define A
A(C,G) = V..o
where Cc is computed by F(Go), Gy is the isomorphism prototype G with Go = TT)), and Co (C). Now we show A satisfies the constraint. Given any graph G and permutation [n] [n]. we have
A(C,G) Vc. A(T((C)=(CT)
23

---

Published as a conference paper at ICLR 2024
Since FF satisfies P=(G),=(T(X) n (Z)) (X, 2), also have PG,F (X, Z) - P (1) (Z)),
thus PG,F can be represented by A.
2-11. For any G, we denote Vc A(C, G). Then, we have
(
II A(i, (G)) iEx(V)
II A(C,
CEN(C)
II A(T((), TT (G)](2;, x;) II ((T(C),T(G))
7 :EV)
CEC
II 1/ X;)
II Vc((c)
Z
CEC
(X,
F.2 PROOF OF THEERRE 2
Theorem Consider simple pairwise MRFs parameterized with:
(11,
|C|
1, 2,
A(C,
2 |C|
Given any connected graphs G (Ag, Xa), H (AH, X1) and E Vo.j E Vn. If and are not isomorphic, then there exists 1 D2 and E Z such that the pair-wise MRFs pGs PH specified by G and H satisfy:
Pc(z: = 2 X X6) + pH X XH).
Proof. We proof the theorem by manually constructing 1 D that distinguishes nodes i.j. With- out loss of generality we may assume node features are taken from a finite discrete space x, {oI,..., 2.). If not, we simply encode all features in G and H into such discrete space.
By flatting Eq. we have
PG 22
X
XG)
+ pH(2 = =2 Xn)
II
D (XG.A. 2b))
II (2 zi)
ZG Z kEin]
(k.D)Ea
# ZH Z, kE[n]
Σ
1 (XH, ZR)
II (k.1)EER
D2 2i)
Zh Σ II
D (XG. Z&)
II
22 Z1)
Z, KEIm]
(ki))E&
4 Za
4 (XH, 2R)
II (R.))e&
22 21),
2, KE
where Σz, denotes summing over all 21, Z2... in Z except 2;. If we combine G, H into huge graph G" (A, with ([Val + [V nodes such that
Ac. 0
A
O, As
X6
X
XH
24

---

Published as a conference paper at ICLR 2024
and denote its edges as & and nodes as V. and let i' = i, j + VVcl be the nodes corresponding to i in G, H, we can describe Eq. Jover as
Pc =
Xc) + (H = = = XH)
Φ (X,: ZR)
II $2(ZE, 2i)
N KEV
(K.))E
D1 [kk Zi)
II (2(Z
Zo KEV
(K,))E
Za
X)
# Zo (zy = X)
To proceed, we assume latent variables are taken from discrete space Zu E Z = (1...,, m where n [V.. Obviously we can encode tuple (b, A, X) into the space of Zμ where 10,1) X E gnxd with a bijective mapping [(b, A, X). To lighten nota- tions we denote (b(2)), (zz)) ((x)))= f to be the inverse mapping of Given (A,
b E {1, A A
design the potential functions as follows:
4 (Z;, 1 1 (z: (zi)b(z.) x.} g(b(z.)),
A A(4)) = A(zz). and 22 = 1 X X(zi) = X ((z)). and A A(zi)b(e.).b6z) =1
where we define g(b) (n! + 1)n". Denote (2) Zo.por 2 X), we now prove gr'(f(t', A, + gy (f(1',
thus proving the theorem. We do this by manually summing all non-zero assignments of Z and show that the special bit of the base-(n! + +1) numbers of gv (f((,, X)) and (f(i', X)) are different. First, it's obvious that both (f' A, X)) and gr (f (i,,,, X)) are integers. Now let's consider the possible values of Z given 2₂ f(i', A, X). Obviously all z for A E V must share the same X and A, thus the only difference is the assignments of b. Note that the non-zero probability assignments of b satisfying {(b(21),... ((z,)))))))))) ) = {(b,...., b, B is exactly the (Eiejn) n²)) --bt bit of the base-(n!+ +1) form of ge (J(i', A, X)) (Since there are no more than n! per-
mutations of (fb,,..., bn no carry-in are produced). Thus the (Ene(n) n²) bit of the base-(n!+ 1) form of gr (f(i', A, X)) corresponds to situations where {(b(2)), ((z,))) f(1,2, 2, n])- Clearly, b(2k) = for k [n] is valid situation for calculating gv (f(r, A, there- fore the (Evejn) n') bit is non-zero. In contrast, because G and H are non-isomorphic, when calculating 9 X)) it's impossible to find valid assignment of that both satisfies ((b(21).... b(z,))) = {{1,2 ........ n}} and makes the potentials non-zero, therefore the (Ere(n) n²) bit is zero. Thus, we have
(((( # gy (((,,,,)))
G PROOF W.R.T. MPNNS
G. PROOF OF THEOREM 3
Theorem 3. Given any graphs G (Ac, Xa), H = (An, X+) and any 1-WL distinguishable 2- order A. If at some iteration, the messages of parallel belief propagation on G and H are different, then 1-WL also distinguishes G, H.
Proof. 1-2. We suppose after iteration t, 1-WL assigns different colors for nodes i,j in G, H, and denote the node colors Col(i, and Col(j, H). We define 2, 2 {0, 1]. Denoting
25

---

Published as a conference paper at ICLR 2024
GA A(k, G') and V (R.))..r A(fk, 1, G'), we let (1,
Col(G', k) Col(G,
V2, 0 else.
And
V = 0,
((x.),.r))) = 1.
Obviously, we have (a(2; = ||Xc) > 0 while qu = 0 XH) = 0 for both methods.
2-+1. The standard belief propagation is summarized follows.
Probabilistic formulation. Given any graph, the conditional distribution p(Z X) is given as
p x)
II
(,,,,,,,)
II
(zy(
Z
1EV
(1J)EE
Initialization. For (i,j)= E and Zi, Bj E Z,
0 mz,)(zz) x 1 x mz).(zz).
Message passing. (1 = 0,,,,,,,.... For E and (N)),.
++1 (2j)(2;)
Σ (2,, 1i (Zi 2j)
II
min)(Zi),
2,EZ
REN(OV
where all messages are normalized: Exyez (2)) =1
We denote m,_; to be all messages computed in iteration i w.r.t. message functions m/ stacked up into a giant vector. Then we have
m
and
++1 1+1 m
f (xi, {f {m, k E ((()(())
(5)
= f (x,, m (1 (m 1: E (())))
Next, we show that all messages can be written as m = (';c;, C,) where oj is the color of node i computed by 1-WL test. At iteration O, clearly we have m x 1 = (c c,) where for all i (recall that within 1-WL's expressiveness). At iteration f, we have
m : I' (xi, m/m ((mi-n (()()))
= f' ( ([0'(ck. ci) & (())))
= (c. (fcx K (()))).
Substituting ct Hash(c, (fe, li E (()))), we have
++1 = (c,
The marginal distribution g(z; X) is then given by
(2; X) x Vi x:) II JEA(()
(z.))
Similarly, we represent g(z, X) with embedding d: and
q: M(f(m (ieN()) (((((())))) 11
As conclusion, have proved that the belief propagation update steps be described by the 1- I-WL (color refinement), therefore any nodes that are distinguished by belief propagation can also be distinguished by MPNN.
n
26

---

Published as a conference paper at ICLR 2024
G.2 PROOF OF THEOREM 4
MPNNs can learn marginals that are at least as accurate as Bethe approximation. Formally, there exists decoding finnctions J 9 such that given any I-WL distinguishble 2-order A. for arbitrary > O and n. E N, there exists a MPNN such that for any graphs with no more than n. nodes, such that:
Theorem 4
(f 9:) S e
i E V and (gs, (1)))g)))>)))))))) S f (i.j) E E, where qs 96 are node and edge marginals specified by a local extrema of Bethe approximation.
where h; is the representation of node i obtained by the MPNN, DKL. is the Kallback-Leible diver- gence.
Proof. Given graph G, the conditional distribution is given by
z X)
II SEV
V (Z. x;)
Viy (1,( (L.)EE
II
7
Bethe approximation defined by minimizing the corresponding free energy DKL(ellP), where we (,((2.2,) and the Bethe free energy is assume (2) = Iliev (e(z;) [(G.)ev (2,))),,(2)]
Bethhe = Σ Σ 2i (2;; 23) log (z..Z))z))
(d: 1) Σ (2:) log qi(2,)
Σ(d iEV
V (z,
;1;
(1 22
qty (Zi, 2,) 2 0, En, d (Zi, 23) q.(z)., and de is the degree of node i. Unluckily, the variational free energy is not convex, therefore finding the global extrema is hard.
where gi(2;) 2 Ex, (z.))
oz (2z)) En, dig (Zi Baح
We now describe a procedure to find local extrema of the Bethe free energy Bethee which is further captured by MPNNs. The procedure is based the concave-come convex procedure (Yuille & Ran- garajan 2001). which states that by decomposing an energy function into a convex function and concave function, we can an discrete iteration procedure monotonically decrease the energy and hence converge to a minimum or a saddle point.
We decompose the Bethe free energy into convex and concave parts (Yuille 2001 )
Ever
Σ
Σ
4ss (Zi, Bj) log Dt (Z,, zj)
+
q: (2,) log qi (Z,)
V Wij(Zi, 2z)
(z;)
(iJ)EE 2.,2,Z2
NEV 2,E2
(z,)))
Σ de NEV
1 log ( F.a)
Bethe
z,eZ
The double-loop algorithm for optimization is proposed by Yuille (200)), which is summarized as follows. The outer loop which has discrete time parameter given by:
22) = 1 (z,, Z,)
-I AAsstas) (as((t))-Aiiti)) AAil)))) -u
(z)) V,(2,, ax))
di
(z:) (., 2e eed
CCEENCy Ani(s.)
The (1g)) (Aigh (1ii) are specified by the inner loop which has discrete time parameter 7:
e
Σ (,, 1ec)) -1,((s)) N3,((,)
Zi,Z,EZ
En, V (1, (Zi, 2,ye AJi(
2x7 (2))
(2 D)
di
ELENON (2,)
We now show that these iterations can be captured by MPNNs. At the beginning, we assume that initialize {g. }, (q (1.)) V. (12)) uniformly:
(+-) (+) x 7h (3 1.
27

---

Published as a conference paper at ICLR 2024
Since the random variables z, E 2 have finite states, the functions Pij. Ai over 2 or 2 2 can be fully described by vectors. For example, if we assume 2 has K states, we can use a dimeeennsoaa vector to represent the function By where Oiy qiy(p. (p. q) corresponds to the (pK + q)-th entrance of the vector. We then design the MPNN follows. The first layers of the MPNN
corresponded the 1-WL coloring procedure. We add sufficient layers for all graphs of no more than n nodes to obtain stable node color. For ease of notation denote the colors by hς for all E V. The parameters of the double-loop algorithm (at iteration 0) can be expressed as
4 92 ( 12)):
0
4. oh
1 (h AG = (
-h: 96 are some functions that maps the node representations h! to the parameters in where g2 g.. the double-loop algorithm.
For ease of notation we use a binary tuple (1, to sequentially and uniquely represent the number of the iterations, where corresponds the current iteration of the outer loop and corresponds to the current iteration the inner loop. We now prove that for both the inner loop and the outer loop, at iteration (f, -) express the parameters as follows:
d g2( h)
N (h n)
then at iteration (t+11T)) or (t, we can still express the parameters in the same forms, where node representations computed by MPNN. Since the MRF is within 1-WL's diseriminative power, the potential functions V;, Vey can be computed by V = +(h)) and Viy = o(h%)) For di in the outer loop, we thus have
1+ 4i
(zi, Viz(Zis 2,)e =f(h 17 ,,
(2,) -252 (2))
where we only use f to refer to node-irrelevant functions. For of the outer loop, we have
d.
q. (z:)) Vi x;,)
t 1+1.7 = Vi(z,, x.)
EC Ali (x:)
= f(h"" (((h), k NN()))
= =f(httlir,
where h 1+1,
hh {(hht" 1i ((N())))
For 7ég +r+1 in the inner loop, have
e
Σ
2:2;E2
= =(h, h h.
For 16,+1 in the inner loop, we have
En. 1 (z,
A/2 (ni) -
2x13 2x
(eg)
(2)),e)) di T)(cy135)
=f hit ((hhT.hh" ( (EE()
=s(hl nit Alhh ((hhT,h)))) ke (()))
=s(hitt))
28

---

Published as a conference paper at ICLR 2024
( Therefore, all the iterations in the double-loop algorithm can be described by iterations of MPNNs. Since the double-loop algorithm is proved to converge (Yulle, 2001), given any positive integer
where h h h 6r
[[
can implement the algorithm with sufficient MPNN layers to guarantee that for all graphs of size less or equal than n, the error between the MPNN outputs and the true local extrema is arbitrary small.
G.3 PROOF OF THEOREM 20
Theorem 20, Given a 1-WL distinguishable 2-order A, there is a MPNN layer L such that all fixed points of H L(Concal X), A) implies fixed points of Bethe approximation of the MRF given any graph G, and all fixed points of Bethe approximation are implied in L. That is, there exists function f such that given any graph G (of the size n), let H. be the set of fixed points of C and be the set of local extrema of Bethe approximation, then is always surjective from H S.
Proof. The layer is implemented as
h (h, Tz. ((h) E (())))
We need to add the node features X into the layer because otherwise the fixed points would be irrelevant w.r.t. X. Without loss of generality we assume Z 2" comes from discrete space, but the proof is equivalently applicable on continuous situations.
We begin by summarizing the Bethe approximation of the original distribution p(Z X) given some fixed X Rnndd Recall that
plz x) = II
(z x.)
II (K,))E
(iy(2i 23) exp E(Z).
VEV
By introducing
II May p4 (1(2))yzZ))
(Z)
II Na (x,)
(K,))E
where Mi are pseudo node marginals and edge marginals, we aim to minimize the Kullback- Leibler divergence (ull() between and p. By further denoting
F(R) = Σ p (Z)E(Z)
Σ M(Z) (()
ZE
ZEZ"
-. + 1- log ((Z)]
the Bethe variational problem for the log partition function then given as
log Zuethe max F(u),
(6)
subject to:
pig(Zi, 21)
(Z)) II (c(x;)
II
for all Z E 2
(L,)) 14 (1(2))115(3))
LEV
(1(z)) 2 0
for all i V,z, E Z
Σ (i(z,) = 1
for all iE V
2:EZ
14j Nz:( 23) 2 0
for all (i,j) E E, 2;, EZ
Σ Mij (Zi, 2,) (z,)
for all (i,j) E E, z; E
4,E2
Σ
Piy pig (Zi, 2n) 1z(2,)
for all (i.j) m, 2, Z
29

---

Published as a conference paper at ICLR 2024
To solve Eq. 7 we first unroll F(4) to be
F()) - E,, [[] + E, log (Z)
=EE [log Z + pZ X)] + 1 log (())
=1
Σ (1 -1)-d))bm log v xz).x))
LiEV
+ E,
Σ (GJ)EE
(log (2;(2i,))) + log V. x.) + log v, ,, x;))
E
Σ
(1 d.) log log)
Σ
log Uij (z,: 24) 2f)
iEV
(i,))E
(1 d:) dr) log (i xi)l
1EV
Bus [log U (Z,, 23) log V. (z,,,) + log v (z), X,]]
(J)EE
+ Σ (1 d, E,, 1og 10gg
Σ
Ba, |- log Maj (z,, 2,)]
REV
(WJE
Fbotthe (14)
- -dd) di)
Σ (i(2;) (2, log (z:))
LEV
2:E2
+
Σ
Σ (in(Z,, 2z)
(W)EEE
[log (i,(z,, zj) + log V (2,, x,) + log v (z}z - log Mey (2;, 2,),,
where d is the degree of node i. Then, the problem 6 is equivalent to:
max Foethe /2
subject to:
Mi (2;) 2 0
for all i VVV2 E Z for all i
Σ [i(2;) =
2,EZ
Mig (Zi, 2z)) 2 0
for all (i,j) E E,2;, 23 E 2
Σ Mij (Zi, 2,)) = (z,)
for all (i,j) E E, 2; E
2,EZ
Σ (ig(2s, 22) 1z(25) for all (i,j) &, nj 2
We now introduce Lagrange multipliers to solve Eq. 7 X for constraints Ex,ez (2; = 1, (2:)) for constraints Σx,ez (1,((,, 2,) (2,), and (z,(2,) for constraints Σx,ez Mij (2,, 2,)
(z,). The non-negative constraints are not active, therefore we do introduce multipliers for these constraints. The Lagrangian is defined as
C(u, 2) =Foethe + Σ >
Σ (a(z)) -1)
LEV
2:EZ
Σ Σ
As((z))
Σ
Mig (ng(2s)2)) - m4(2))
2,E2
Σ Σ )zs(zz)
Σ
Mig Mas( 22)) - 11((z))
(1,))E
2.52
30

---

Published as a conference paper at ICLR 2024
Since the local extrema of L corresponds to extrema of the problem 7 we now only need to prove that there exists a MPNN layer such that all the fixed points satisfying
h = Φ (h,, zt, Wh j E ((OH)
corresponds to local extrema of the Lagrangian L. This is to show that h; contains sufficient statistic for 14i for all i E V and (h, h2y) contains sufficient statistic for Paj for all (i,j) E
We begin by setting the derivatives of C(p, A) to be O. First differentiate w.r.t. f4:
(C(H, 0p.(z.) = (1 - (1-d; (Z,, x log - + - Σ )z.(zi)
jEN(()
-d(- - 1) 1 x,), + (d. () + 1) A
E
Azi(z)) =0. 0.
JEN(()
Therefore
V((i,)) pi(zi) exp exp { log
1
1 di 1
Σ Ap((a)ds
-1
(EE(()
fi (Zi, Xi, di Usi lj E (V())) A(ii, G)),
where d; is implied in H4 ji N(i)) Since A within 1-WL expressiveness, by denoting C; be the I-WL color of node have
1 Fi (x, Au WOge (JEN()) .c..
Next, we differentiate w.r.t Pay:
aL(,,,) llog (iy(z,, z1) + log (2,, + log W, x,)
loggus (zi, 2j) + (zi) \zz(Zz) O.
Therefore
Miy Miy(z; 23) cxp flog V Vij 23) + log V (2,, + log xz), - Azi(2;) >)5(2;))
= f2 (Zi, 2j, Xi, xj, Xaj, Azi- A (i,j).))
and similarly
Pij = F2 Xj, Aeg Ases Co cj).
Setting the derivatives w.r.. À to 0 results in
1 Fa(mi ci),
#4 = Fi(Mif, Cs. ci):
#4 Fo Cj, Ci);
We now parameterize Pa: Mij, Ai, Aij as
14 thy (hi),
Pij = du (hi h2);
A: th (h:);
Nij = the (h;, hz),
where h; is the node representation for node i. Note that for arbitrary choices of {ui). [mg)) (Ar,, {Aih} there must be set of node representations { that express them. For ex- ample, we can set h2[0] i, h,[ll = M4 h [2] = X,, h, [2+]] Pyy if (i,j) E &, h, = Xιj (i, E E, and all other dimensions of h, being O. Then we can express those terms via node rep- resentations. The above results are then written
Vya (hx)) Fi tha (hi), Uerr (hj, ha) (iEN(())))
uu (h,, h2) Fo(x,, Xj, this (hi, hz), 4x (hg,h.))
= Fo( (hx)),
Via (h:) Fa(ming (his hi)))
Vy (fz:) Fo (hij, I2:)),
31

---

Published as a conference paper at ICLR 2024
G
H
Figure 1-WL undistinguished graphs
To summarize, these equations correspond to two properties: a node property where for E V.
Mnode (h; x ([h 1 ((())) 0,
and an edge property where for all (i.j) EE
Medga Chi, hj, Xi, x,) [=)=) =0
which can be equivalently described as for all i E V,
Medge ([((h hy, x,, x1) E N(())) = 0.
By introducing constraints for all E V, the (h:) x;, we have Medge (h,, ((h; 1j (())))
Therefore, all constraints specified by MPNN layer.
G.4 PROOF OF COROLLOARY 5
Corolloary Given any graph G and corresponding pairwise MRF, if is tree, there is a MPNN that outputs true node and edge marginals.
Proof. From Theorem 4 we know that MPNNs capture belief propagation. Since belief propagation can compute exact marginals on trees, so do MPNNs.
G.5 PROOF OF THEOREM 7
Theorem 7
MPNNs can at most 1-2 approximate p(z: X) for arbitrary G and E VG-
Proof. We only need to show that MPNNs cannot 2-2 1-3 approximate p(z; X). For 2-2 approximations, recall that although 2-WL. and 1-WL are equivalent in distinguishing graphs, they nodes, and set H only contain
differ in distinguishing nodes. We set graph G to only contain two isolated nodes. 1-WL always assigns all nodes the same color, but 2-WL assigns different color for nodes in G and Н. In this manner potentials for nodes in G and H, thus the posteriori are different.
set 2-WL distinguishable A to assign different
Now we consider the 1-3 approximations. Consider the graphs in Figure guished by 1-WL, but we can set potential functions to be
G and H are undistin-
V (2,) Vig (24, 21)) = 1,
V Wiyk (2,, Zy. 2k) = {1, 2, = 2, 24 =0,
else.
for all é, k. where we let = {0. Obviously due to the application of the 3-order potential function in G, the posteriori of nodes in G is different from that in H.
32

---

Published as a conference paper at ICLR 2024
H PROOF W.R.T. APPROXIMATING COMPLEX DISTRIBUTIONS
H.1 A-1-CWL: A TOOL FOR THE PROOF
In this section we will prove results for many GNN variants. For simplicity we first design family of WL variants that provably approximate complex MRFs, then show that the GNN variants are expressive enough for capturing these WL variants.
We name our WL variants k-l Clique WL (CWL). At the beginning. the k-1 CWL first apply classic k-WL on the graph and assign colors for k-tuples. Recall that for any subset of nodes C== = ff.....mm J. k-WL computes the color of C' as Col (C) = if v E c*}] }}. At iteration O, we initialize the colors of CWL as (i) = Hash(a;) for all E V. At iteration / + 1, we have
et Hash (c) {{ (c), Col (f4,)) (5 M[)) {[(c) Col (1)) (1))IiEMM ( where (i) {1 j.k ji,...: (N()), (i).....)) C},
(i....d)) = -( s }} C is the set of cliques, Col is the colors specified by k-WL.
By parameterizing the hashing functions in k-l-CWL, we obtain the k-I-CWL-GNNs. Our next result confirms the expressiveness of k-I-CWL-GNNs.
Theorem 21. k-I-CWL-GNNs can k-(1 + 1) approximate p(z: X).
Proof. We first show that k-I-CWL is expressive enough for distinguishing non-isomorphic graphs compared with belief propagation. Belief propagation on (1 + oorde MRF is summarized as follows.
Initialization. We first transform the original graph into a factor graph Gy. For each term in the MRF formulation, we create corresponding factor. That is, each clique C' of order more than I ++T is corresponded a unique factor c, corresponding to the term V.. Further more, each node i is connected with its own factor, corresponding the term V,, In the factor graph, each node is connected and only connected factor nodes, thus composing a bipartite graph. We use j,.... to refer to nodes and a, b, c... ... to refer to factors. For all (i, a) Ec, and E Z,
ma-si(zi) & 1 (z;)
Message passing, (t = 0, 0,1,2,...) 2,...
For (i, a) E Eag,
m+t1 (z:)
Σ
V Va ZN(a)v))
II m)-a(Zz). JEN(a)
++1 m mi-ra
(z:)
II bEA(o)a
mf
where Va denotes the potential function w.r.t. the factor Specifically, when only contains single node i, we let m m (2:) V.(2i, x,).
Similarly before, if we use m mf_a to represent sufficient statistics of the pseudo distribu- tions m. ss: m the above iterations can be written as follows in the factor graph:
m m+1 f(W(()), x, Col)( (mm) ij M(a)ii)) f' m Col* (() E )())))),
++1
g 9(((m),,) be ((i)aa))
m
(m) (fmi E (())))).
We first prove that this procedure can be captured by 1-WL on the factor graph, where we set the initial color of factors to be equivalent but different from the nodes. Next we show that all messages can be written as m m for node in the original graph G at iteration L and ct for in the factor graph Gy stands for
(c),, ef) and m = (c(, c where of is the color of k-L-CWL
33

---

Published as a conference paper at ICLR 2024
c = 1 I At iteration 0 clearly the statement is true. At iteration t assume is still true. At iteration t 1, we have
m
(x, Col Coll(W(a)), aa: Mii
(x, (N() (
(c,, Col (ol(( c e =ottlcctt,, ,c,tt).
m t+1 = g (miasi Hm TacllbeNNNN (EN()))
= (vb' ct), (e c) lb (be)())))
(c)tt ,tt))
Thus the statement holds. The last steps hold because
Hash(c), (fe, a e N()))
Hashh (fc (il
= Hash(e, (a (l la
= -Hahh
(a
=Hash (G:(((e
-Hash
-Hash (f- (J))))))))
{( =Hash (c, 1 M()) .a......... (ie'llie
[[c-"IjEM(() - (15
where Ng follow the definitions given by k-CWL in the original graph. Therefore, the up- dates follow the k-CWL procedure. The marginal distribution qi be described as
q: = -illminil (aE
Nilt c la (()))
l'(ctt))
Thus the statement holds.
Now we show that k-I-CWL-GNNS can approximate local extrema of the Bethe approximation to arbitrary precision. We will adopt the general Bethe free energy on factor graphs, which have been shown its connection with belief propagation factor graphs (Heskes 2002a Yedidia al. 2005).
which is defined as follows:
(c())) Betthe >E (z(z)) log (Z()c)
Σ (n: 1) iEV
Σ (z.) log (z:).
zc
where for simplicity we assume single node also composes a clique C and in that case (z( is shorthand for Vi(zi, R;). Again, there is a convex-concave algorithm for finding the local extrema of the Bethe approximation (Heskes 2002a). where for the outer loop iteration (t + 1) we have
log t log V (2a) +
T4 log d: (za),
sEN(()
La
1+,,5 (2x) (t1,7(Z0))
1
Th 1+1 (va))
II
mi-a( (z,):
1,7
Z
(EN(()
34

---

Published as a conference paper at ICLR 2024
and for the inner loop at iteration t, 7 + the messages computed by regular belief propagation and
1 (zi)
II (EA(()
m
m (2i)
Z;
1
9o
1
(2a)
1
L.T
(Za)
II (EA(a)
f.r m (zi).
Za
We now show that both the inner and outer loops captured by K-I-CWL-GNNS. Previously we have shown that the messages of belief propagation can be captured by k-I-WWL-GNNS. By assuming
T ( [a))())))),
f.r = dc (Hf [i))(a)))).
q f = gi'1(c (d)"),
we have
log 11- (zo) = log What (za) (
+
a
log (za)
n1
iEN(a)
= =((Col (fe |iEN())))
= =f(fl (iE
1T+ (Zn)
= (ettli (za)
II
m (2)
lo
Za
(EV(a)
= =((Co)(W(a)) (( (iEN(a)))
= ffff& ortl
of [iEN(a)
11+ (2:) = 1
m m (2i) (EV(()
II
Z,
= f([f ( a Ni))),
thus the iterations are also within 1-I-CWLGNNSS' expressive power.
H.2 PROOF. W.R.T. k-GNNS
Proposition
g k-GNNs can k-k approximate p(z, for arbitrary
Proof. We prove this by showing k-GNNs implement k--k - 1)-CWL-GNNs. We use h to stand for the embeddings of k-(k 1)-CWL-GNNs and for k-GNNs. We will reuse the symbol f to represent arbitrary functions. We have
h ++1 = (n..
{{ (h',, Coll i )M))) {(nj,
We first show that k-GNNs can implement the following procedure
b s(bj {{ (hjj Col (i) E mO)))
for any 1 1 k 1. By letting the corresponding k-GNN layers to be
h h = s(h (1h j.a.... |j E v}] ... ((hT-1 13 [}&)
fo(h 7....
1j 1
v)])
fi
fesitaa.. ju E V}} i e v)))
f2(hT
In, v)]
-
((ht) Ji.je..., jt E v}})
35

---

Published as a conference paper at ICLR 2024
Note that since the embeddings of k-GNNNs are initialized with internal structural information, can define
h he....... = fr ( d i W
dan J1, 12. It E EHH)
( (A..... 13 (fi,.... {)())))
Thus any function I' can be implemented by k-GNNs via backtrace of the above procedure. Since ii...... are computed by k-GNNs it can also capture the k-WL colors with sufficient layers. Thus by using multiple layers together the k-GNN layers can implement the above procedure with
h h
for т. Obviously, the k--Kk- 1) 1J-CWL-GNN layers are implemented by this procedure, thus k-GNNs implement k-(k - 1)-CWL-GNNs.
H.3
PROOF W.R.T. SUBGRAPH GNNS
Proposition g
ESANs with node marking policy can 1-3 approximate p(z, X) for arbitrary G.
Proof. Recall that the update iterations in ESANS is called DSS-WI.. node marking variant implemented as:
Hash (c)
c 4+ (j) Hash( (f(U) EN))
with initialization
<0) (0,x,), i
(1.2,), i=j.
We will focus on the 1-2-CWL-GNN variant, which is given as
c +++1 f(c;, ((c)) l E NG(O) H. (61.22) E N2())))
Note that we exclude the Col terms in the original definition because since the 1-2-CWL. already implies 1-WL, the colors 1-WL can also be obtained by applying 1-2-CWL solely. We next show how we can implement 1-2-CWL-GNNs with ESANs. In the first iteration can compute the colors ESANs to be
c) = (Lo.)) 2z),
thus identifying the neighbors of each marked nodes. Then we can implement 1-2-CWL as
c++ = f(c,,, f(c, li (..
(1.12) (i. N((())))
= (oce((e)jeekkk)llll.c.lllllllva2
I e
N()) = f6(ff(t' v))))
where cf) = H))h(c/()) ((c(0) & E df. (fc]. E Thus we can imple-
ment 1-2-CWL-GNN layers with ESANS and DSS-WL.
H.4 PROOF W.R.T. SWL/ / CWL
Proposition 10 The SWL/ / CWL and the corresponding GNN variants with k-clique simplex can I-k approximate p(z, X).
36

---

Published as a conference paper at ICLR 2024
(a)
(b)
(c)
(d)
Figure 3: Counter example for ID-GNNs and Nested GNNs.
Proof. Considering the expressiveness of the two approaches (Bodnar et al. 2021a). we will focus on the less expressive SWL variant, together with its GNN variant, MPSN, which is given by
h++ f(h,t mB 1 (o), m ( (m). # (o), (o), m
++1 (a) = {[Ms(h's kt, I B(o))
m
m [{Mc(hh' 11,) [
m (o) (H ht nour) 1 [N(o)))
(a) = ([M hi, h ITE
For details of the definitions please refer Bodnar al. (2021b). The k-clique complex lifting is described as follows. Given graph G, its corresponding simplicial complex K. satisfies: if nodes (i1,...,() in where I forms clique G. then (f1...,,1 E K.
We first show that in this case, nodes and cliques can interchange messages via finite of MPSN layers. Suppose a corresponds
single node. Then by repeatedly applying the co-boundary adjacency C(ar), we obtain the edges, 3-cliques, that contains o. For simplicity we refer to the set of edges, 3-cliques, as C(a)) C (=))..... Similarly, if corresponds to a clique, then by repeatedly applying the boundary adjacency B(ar), eventually obtain the nodes that it contains. We also refer to the set of nodes as (a) Thus we can implement I-(k 1)-CWL with MPSNs as
h ++1 f(h). ((h)) l EEM() ..... ((hj j
f(h) (MM(,)))) .- (frie W (0) }})
Shh, ((hg a EC())), [[h9 o E c()))
where h' = (o). Thus the above procedure can be realized by finite iterations of MPSN layers.
H.5 PROOF W.R.T. OTHER VARIANTS
We now construct counter examples for these GNN variants.
ID-GNNs. Consider the graphs in Figure where we use ID-GNNs to learn the black colored
nodes. Obviously, ID-GNNs cannot distinguish the node in (a) with the node (b), but clearly (a) has 6 3-cliques while (b) has 8 3-cliques, thus (a) and (b) are distinguishable by 3-order MRFs. To show that ID-GNNs is weaker than 2-WL, consider the graphs (c) and (d) in Figure 3 Since (c) has 7 nodes and (d) has 4 nodes, the black nodes are distinguished by 2-WL. However, since 1-WL only aggregates local neighbors, it cannot distinguish the black nodes in (c) and (d).
We still consider the graphs in Figure 3 where we use Nested GNNs to learn the black colored nodes. For graphs (a) and (b), no matter what the number of hops choose, NGNNs cannot distinguish the black nodes (a) between the black node in (b). Similarly, it also cannot distinguish the black nodes in (c) and (d).
Nested GNNs
37

---

Published as a conference paper at ICLR 2024
1 PROOF W.R.T. APPROXIMATING JOINT POSTERIORI
I.1 k-NODE LABELING: TOOL. FOR PROOF
We first introduce the k-node labeling framework. p(Zi,,-. Zig X). We set augmented node features as
Suppose to learn the posterioni
H,- (1i=í2) .... ,
Then we apply a MPNN on the augmented graph and output the node representation h as the final representation of the posteriori p(z,, .... Zi, X). Then, we have
Theorem 22. The k-node labeling with MPNNs 1-2 approximates p(zi, Zi, X).
Proof. As discussed above, we factorize p(Zi, pZZii:-.. :..,. Zig X)
p(z.,.-.. Zip, X) = p(zi, Zig...., Zig X)
plzz. X).
Thus to compute p Zi, X) we need to repeatedly apply belief propagation (Bethe approx-
imation) on the conditional MRFs. Concretely, to compute plz:,.....24 Zia X) for all values of Zig we need to
Compute p(Z,,
Zig Zip X)
for all 2 2, 2
Compute p(Zig
Zign.... Zig X)
for all Zig ..., Zig 2,
for all Zi E Z. We now show that the k-node labeling can compute all the above functions. First consider computing p(z,, Ziz u.. Zig X). The original MRF can be written
Compute p (Z
X
p(Z
X
II
(Z,,,,,
II (,,(Z,,
iEV
(L,))E
Fixing Zigr ... Big we can rewrite the MRF as
1
pl Z (ffe..nnn Zigs Ziz: X)=
(i x:)
II
Vis(zi, 2j)
7
iEV (EVA(aa
( (
II
(,(Z,, xi)
II
(,y(2,, 2g)
iE (k2
iE (((().)d))))EN(
(8)
II iEV.(ta....ik)
vi(Zi, xi)
II
Viy(Zi, 21)
7'
II JEN(2))
II JEN((
Vie (Zix: 2z).
Assume each z, Z has S states, then the above equations induce S MRFs based on different values of ......., Zi.- We notice that the above conditional MRFs can be regarded as normal MRFs on modified graphs: given the original graph G. we first add unique label for each neighbor of the node i2, then delete i2 from G; we then repeat this procedure for ig. in. obtaining the
induced graph G. Then, there exists 1-WI. distinguishable 2-order A1,...AAu 1, such that the conditional MRFs on G are given by A,, ...; Aga-1 on G. This is simply done by setting
G) (+)() + V... (8ms)), node i has label L,, for E [kt],
A
(,),,,,
else.
Aa((i,
Vij-
According to our previous discussion on MPNNs and I-L expressive 2-order MRFs, MPNNs on & can compute marginals on all 5 MRFs. There's 's only one step before we prove the theorem. Note that after one iteration of MPNN our k-node labeling framework, the neighbors of 2.,,..., Zi, are naturally tagged with unique labels, thus & and our k-node labeling enhanced graph are equivalent for MPNNs. Thus, k-node labeling with MPNNs can also 1-2 approximates p(z,, Zig..... Zi, X). Since computing p(z;, Zi....., Ziz: X). only requires performing node labeling on ig ..., ie.... the k-node labeling can also approximate them. Putting these together, the k-node labeling with MPNNs 1-2 approximates p(z.,.-.. ..., 2i X).
38

---

Published as a conference paper at ICLR 2024
1.2
PROOF W.R.T. k-GNNS
Proposition
12
k- k-GNNs cannot 1-2 approximate p(z,, ....... Zie X for arbitrary k 2 2.
2022). where they showed that k-node labeling not weaker than k-W The core is to construct graphs that are undistinguished by k-WL. but are distinguished by (A: - node labeling. We construct CFI graphs ((K) and (XC). From Grohe & Otto (202)) we know that (AC) and ((C.) cannot be distinguished by (A- - 1) WLW,, whose expressive power bounded by (k- 2)-FWL.
Proof. The proof is similar with the proof in (Qian et al.
Next we show that ((() and ((C) can be distinguished by (k: -)-ndde labeling. To do so we need to introduce the concept of pebble games (Grohe & Otto, 2012 Cai et al., 1989). The readers are welcome to check Grohe & Outo (2012) for more detailed introduction. Given two structures A, B, the bijective k-pebble game is played by two players by placing pairs of pebbles on pair of structures A, B. The rounds of the game are as follows. Player I picks up one of his pebbles, and player II picks up her corresponding pebble. Then player II chooses bijection f between A and B (if no such bijection exists player II immediately loses). Then player places his pebble on an element a of A, and player places her pebble on f(a). After each round there subset p S A x B consisting of the at most k pairs of elements corresponding to the pebbles placed. Player II wins a play if every position p a local isomorphism.
Theorem 23. Cai al. 1989) A = B if and only if player Il has winning strategy for the bijective k-pebble game on A.B.
Theorem 23 indicates that (k: 1WLFWW can distinguish A, B if and only if player II has winning strategy for the bijective k- pebbeb game on A. B. However, although it justifies (A 1)-L it has nothing do with the (k - node labelind here. We propose a variant of the bijective k-pebble game, namely restricted bijective k-i-pebble game, described as follows. Given two structures A. B, the restricted bijective k-i-pebble game also played by two players by placing & pairs of pebbles on pair of structures A, B. The rounds of the game are as follows. Player I picks up one of his pebbles, and player I1 picks up her corresponding pebble. Then player II chooses a bijection f between A and B (if no such bijection exists player II immediately loses). Then player places his pebble on an element a of A, and player II places her pebble on fa). The difference is, i pairs of the pebbles are static, when the players place these pebbles the elements of A, B, they can longer pick and replace them on other elements. Then, we have
Theorem 24. There is a (k - 2)-n labeling MPNN that distinguishes the (Is 2)- u, v from A, B if and only if player II has winning strutegy for the restricted bijective k-(k-2) (-kk-)--ebblee game on A, which initially places (k - 2) static pebbles on u, v, if A, are connected graphs.
Proof. Let G, H be a pair of connected graphs and let u, v be the target k-tuples. Let G(u)), H()) be the corresponding node labeling induced graphs. Since G, H are connected, we need to show the following statements are equivalent.
1. 1-WL cannot distinguish G(u)) H(v)
2. 2-WL cannot distinguish G(uys H(v)
3. No FOC₂ formula distinguishes G(u), H[v)
4. Player II has a winning strategy for the (k + 2)-k pebble game on G, H which initially places the A pairs of static pebbles
1 1 2 2 3 is proved as a special case in Cai et al. (1989). Since G, H are connected,
1 - also holds.
2-4: Suppose after r iterations the 2-WL still assigns the same color to G(m): H(v)- We instead prove the following statement:
39

---

Published as a conference paper at ICLR 2024
After + & iterations 2-WL gives (æ1, 3/1 E Vo... and (22, 12)
Vi the same color Player II has a winning strategy for the (k+22) 2)-k pebble game on G, which initially places the k pairs of static pebbles on u, v and place the other pairs of static pebbles on (I1, v1) and (222, V2) in r moves.
We assume W" to be the color assignment of 2-WL at iteration r + k. Clearly player I can only chooses one of the pebbles on 21, 91. 31, Without loss of generality suppose he picks up ZT. The player II answers with the bijective mapping that maps node pairs with the same W color, that is, f(t1) E {t2 W W = - (12, 92)) Note that such mapping must exist because
('(,, v) Hash (W (x, v), { W (x,=)
VaJ) (2,")(
Va]))
the same for (ar, y1) and (.2, y2). No matter which node player I places his pebble on, player II places her pebble on the corresponding node. Player II has not yet lost: the structure between (41, yi) and (f2: 122 must be the same, otherwise they have different W colors. The structure between (t1, u) and (t2, v) are also the same: This is because that at the start added unique labels to the k-tuples u and v. Therefore, after the first rounds of 2-WL iterations if the subgraphs induced by h, V1, from ((u) and f2, U2, from (v) are different, (f1, V1) and (12, y2) will also have different 2-WL colors. Now, since (41, 2/1 and (12, y2) have the same W colors, by induction on proved the above statement.
By further induction on r in the statement, we can prove 2 because we have showed that for any node pairs the results of 2-WL and the pebble game are always consistent.
-3- -4: Suppose for some FOC2 formula sp Gi and H(v) If sp is conjunction then G(u); H(v) must differs on at least one of the conjuncts, so we may assume şo is of the form 3P Without loss of generality we assume the quantifier depth of yp is r. Note that there are total 2 free pairs of pebbles that can be placed to nodes, which exactly corresponds to the number of free variables in FOC₂ formula. Player I takes pebble, corresponding to the variable in y. Player II must respond with a bijective mapping f. Since ((m) and H(v) we know that there are at least N nodes satisfying d in ((u) but less than N nodes satisfying y in H(v)- Player I then picks the node in ((u) such that vb(w) is true but (w(()) is false. By induction can see that at quantifier depth 0 player II loses the game.
With Theorem 24 we can now prove that the graphs (KC) and (AC) can be distinguished by (k (k- node labeling. The prove steps are exactly the same as Grohe Outo (2012), , as the steps in Grohe & Otto (2012) naturally follow the constraints of the bijective k-(k: 2)-pebble game.
We give a winning strategy for player in the bijective k--k 2) pe-pbee game. the first k rounds the game, player I picks his k - pebbles on vg.... ..,, et and suppose p(u?) = v.s the corresponding position for some sets S,. That is,
0 8k
We now assume that the pebbles at u ..., og are static. Therefore vg. ...... of compose all static pebbles and the pebble at ug is still movable. In the next round of the game player I starts by selecting this pebble, and places it on ei In the next round, player starts by selecting the pebble on ei2 and places it on of. is proved by Grohe & Outo (012) that player I wins this time. O
1.3 PROOF W.R.T. A-FWL-MPNNS
Proposition
13
k-FWL-MPNNS can 1-2 upproximate p(zi,, Biy X).
Proof. Given G (V,E), the k-FWI. each layer evaluates
Con (all+)((u,....... u+) = Hash (Col (u1..., ux).
{( (o) (v. 02, uz,..., ux), (o (un,, ..,,, ux), (ur,.,, | lvEv!f)
40

---

Published as a conference paper at ICLR 2024
If consider fragment of the above procedure where replace the last colors in each neighbor with the initial colors
Coll+1)(u (ui, .... ux) Hash (ui, uk):
{ (Col u2.... ... ux); Col (u1, o.... uz) Col (u (u...., z)) M(wn)})
Note that the neighbors (ui) are already encoded in Col (u,,,,..) Clearly, this variant is less expressive than the original one. We can rewrite this variant to make it strictly corresponded to k - 1-node labeling
= (
{f (
where initialize f(() as (v) Col (v. u2,..., uz). The computation of f() is exactly the same as (k - -o-e labeling when we apply node labeling on ug ..,, Ug. Since clearly corresponded to smaller fragment of the above equations compared with k-FWL, we have proved the result.
1.4 PROOF W.R.T. LABELING TRICK
Proposition
14 X
k-labeling trick MPNNs 1-2 approximate f(z) p(z,,
Zie
X) but
not p(z., Zj
Proof. It's simple show that labeling trick cannot capture p(z,, 2,
X). Consider graph G with
two isolated nodes 1, with different node features. Then obviously we can have p(z1, Z2 X) +
p(z2, 21 X) but labeling trick will always assign them the same representation.
Next we show that k-labeling trick MPNNs 1-2 approximate f(z) p(z.,
Zia = X).
This is done by altering the MRFs Eq. g can rewrite the MRFs as
p(Z (11.22....1)
Ziz
Zz
X
II
(Z x;)
II
(ir(z,, 23)
SEVIEE....ee
(
II JEA((S)
V (z,
II
V Vin.i 2z)
JEN((E)
Thus f(z) is computed by only reserving the MRFs specified by A, for s E Z (for simplicity we assume Z [S]) where we add an identical label to ig,..., and set
(.)(.) L (s, is labeled, A. G) (v),))
else.
A.((i.)), Viji i,j are not labeled,
11, else.
This identical labeling procedure is captured by the k-lahening trick, thus the representation of node i in k-labeling trick capture p(z; Zi, ... 2i, z, X) and similarly as discussion before, p(z,, Zi Zi 2, X). Since k-labeling trick aggregates all nodes in the graph, the graph representation can capture p(Zi,
Zi, z, X).
1.5 PROOF W.R.T. ORDERED NODE LABELING
Proposition 15
MPNNs with ordered node pair labeling 1-2 approximate p(z,, z₁ X).
Proof. To approximate p(z., 2, X) we only need to an label on node j. Since ordered node pair labeling adds labels on both and it can also approximate p(z;, Zj X).
I.6
PROOF W.R.T. SOURCE NODE LABELING
Proposition
16 Source node labeling MPNNs 1-2 approximate p(z;, Zj X).
Proof. The source node labeling is exactly 1-node labeling applied on
41

---

Published as a conference paper at ICLR 2024
J PROOF W.R.T. PHANTOM NODES / EDGES
J.1 PROOF OF PROPOSITION 17
Proposition 17 MPNNs with phantom nodes can 1-30 approximate p(z; X).
Proof. We prove by showing that for any E N+, phantom nodes can capture 1-n-CWL-GNNs for graphs with no more than n nodes. To separate our notations for nodes and phantom nodes, we will use i.J.... ... to refer to nodes and p, ... to refer to phantom nodes. We next show that two layers of phantom node enhanced MPNNS can capture one layer I-n-CWL-GNNs:
++1 (c), [[(e) | (EM()) ([(c) |j (.)))
= fo (c, ([()) (.. UN.())
Since smaller cliques are completely contained in larger cliques, we can also only preserve maximum cliques in the above equation:
c = fi (c) ([(c) (U) (()))c))))))) ec))
f2 (cl ([(c (()))
where we further define for phantom nodes
c {(c i [D)))
Therefore, two iterations of phantom node enhanced MPNNs can capture one layer of 1-n-CWL- GNNs for arbitrary large n.
J.2 PROOF OF PROPOSITION
Proposition 18
MPNNs with phantom nodes of cliques more than k can 1-k approximate
p(z; X).
Proof. The proof equivalent the proof of Proposition corresponds to k-cliques thus are corresponded to 1-(k -WWN-GGGS
except that the phantom nodes at most
c = f (c), ([(c)) e
fo JiC
= (iu ecH))
= [p
J.3 PROOF OF PROPOSITION
9
Proposition 19
MPNNs with phantom edges 1-2 approximates p(zu, 2.) given by the modified Bethe free energy with altered distribution in Eq. 2
Proof. Given MRF
p X)
II
(2.,,,))
II
Viy(Zi, 2;)
Z
LeV
(K,))
and the corresponding altered distribution for Bethe free energy
(Z)
II (z().)
(2, (z(2)) (2,)
quo (Zu. 2o)
In (Z,, (zz.)g (z,)
V
(KJ)E
(u.N)EÉ
we aim to
min (gl(p
42

---

Published as a conference paper at ICLR 2024
We can write altered MRF
Z X
II KEV
(Z
II V. (z, 2z) (KJ)EE
II ((z,, 2,);
(u,o)EÊ
where . = 1, thus this formulation is equivalent with the original one. Applying Bethe approx-
imation on this formulation naturally yields the quasi distribution in Eq. p Obviously, by adding phantom edges for each (u, v) & to the original G, the augmented graph G can naturally produce the altered MRF with
A(i,G) Ui
Vig (i,j) E,
A(Li,),C)
Φ (i.j) E.
Since this A is still within I-WL's expressive power, MPNNs with phantom edges can 1-2 approxi- mate the modified Bethe approximation.
K
THE EXPRESSIVENESS OF GNNs WITHOUT THE WL HIERARCHY
K.1 A REDEFINITION OF THE METRICS
In our previous discussions, we constrain the expressiveness of the function A for producing poten- tials in MRFs by the k-WL hierarchy. In this section we relax this constraint and provide a more fine-grained description of GNN variants without the k-WL constraints of A. In contrast, strict the expressiveness of A to be dependent on the GNN models M we are to evaluate. Since obviously M won't be able to capture A if A is more expressive than .,, restrict that A is equally or less expressive than M, which further leads to the following redefinition of our metrics of expressiveness.
Our discussion now begins with the following definition of expressiveness.
Definition 25. class of GNN models M can /-approximate some posteriori p if and only given arbitrary A satisfying:
The maximum order of A is l.
For arbitrary G = (Ac, H = (AH, XH) and C1, C2 being two nodes or cliques with more than nodes from G, H respectively, A(C1, Ag) + A(C2, Ah) only when there exists a GNN instance from M that distinguishes C1 and C2.
There exists an instance
such that:
It can distinguish all graphs distinguished by iterations of belief propagation in Theorem
It can provide marginals at least as accurate as Bethe approximation as in Theorem $
Clearly, the above definition relaxes the WL constraint of in Definition 6 by restricting A to share the equivalent expressiveness with the GNN models. As we shall see, the results of the expressiveness GNN models in Section 4 still holds.
K.2 RESULTS W.R.T. NODE-LEVEL EXPRESSIVENESS
Proposition 26. MPNNs can most 2-approximate p(z; X) for arbitrary G and E Vo-
Proposition 27. k-GNNs can k-approximate p(z; X) for arbitrary G.
Proposition 28, ESANs with node marking policy can 3-approximate p(z; X) for arbitrary G.
Proposition 29, The GNN variants corresponding with SWL / CWL with k-clique simplex can k-
approximate p(z; X).
Proposition 30. ID- ID-GNNs YYou et al. 2021 and Nested GNNs Zhang Li 2021) can at most 2-approximate p(z; X).
43

---

Published as a conference paper at ICLR 2024
K.3 PROOFS
First we note that the only difference between the above propositions and the main results in this paper is that A is the previous proof in Section H.T and Section [.I it is seen that the potential functions V/ over factors when restricted by the k-WL tests, can be regarded as functions over the k-WL colors V f(Col" (a)), where (-) indicates the k-WL color. We can then extend Theorem 21 to proof the above propositions.
limited by the GNN models themselves rather than the k-WL tests. In
Theorem 31. Suppose the expressiveness of A is limited by some coloring function M. We define generalized I-CWL, whose only difference between k-l-CWL is that I-CWL first apply M to the graph and records the colors. Then, I-CWL-GNNs can (I + -apppooxiee pizz X).
Proof. The proof is the same except that replace all Col emerged in the proof in Section H.1 with M(.).
With Theorem 31 the additional results in Section K.2 are proved with exactly the say steps in Section H except that we replace the k-I-CWL in Section H with the I-CWL in Theorem 33 and set M to be the GNN models (i.e. MPNNs, k-GNNs, ESANs, etc.) in each proposition.
44


Reviews:
[{"review_id": "sDdpyJppNR", "reviewer": "Reviewer_ubyE", "summary": "The authors report a slate of new theoretical results regarding the expressive power of a variety of GNNs w.r.t. MRFs. Utilizing this theoretical basis, they then propose a novel extension of MPNNs utilizing so-called \"phantom nodes/edges\". These proposed algorithms are tested using synthetic and real world data, comparing against state-of-the-art algorithms. \n\nIn node classification tasks, the phantom node lifting method improved state of the art when applied on GCN, and compared well to recent works when utilized with SAGE and GCNII methodologies. In link prediction, phantom edges proved to improve all compared results using standard datasets and metrics.\n\nIn summary, recasting GNN's expressibility via MRF, the authors were able to improve the understanding of MPNNs and used this probabilistic viewpoint to introduce a novel methodology that matches or outperforms the current state-of-the-art in standard tests.", "questions": "1. Question: It seems that DropGNN (perhaps applied to a slightly modified graph) is closely related to the proposed PN method. How do the two compare in inference tasks?\n\n2. Suggestion: I find the paper would be strengthened by a more direct discussion of the origins of the methodology (i.e., how does this differ/extend from previous works? E.g. node labeling)", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper makes two contributions: (1) improving the theoretical understanding of GNNs utilizing a probabilistic viewpoint to classify expressibility with respect to (and beyond) Weisfeiler-Lehman tests and (2) utilizing this probabilistic viewpoint to propose a novel methodology to lift the expressive power of MPNNs.\n\nRecasting the question of expressiveness from limited WL tests into a probabilistic frame is natural in the setting of ML, and as shown, lucrative.", "weaknesses": "While the results are compelling - I find the exposition of the novel phantom node/edge methodology lacking. While proofs are given on their approximation power, and one can assume motivation from framed previous works, the paper would be strengthened with the motivation driving the methodology.\n\nFurther, after the long theoretical exposition, the analysis of the proposed method is brief, and restricted mainly to results. A longer discussion of the modified properties (and potential limitations) of the graph would allow more informed adoption.", "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": "", "extra_scores": {}}, {"review_id": "cWeTjQ3r9w", "reviewer": "Reviewer_rfPW", "summary": "The paper proposes a new approach to evaluate the expressive power of graph neural networks from a probabilistic perspective instead of Weisfeiler-Lehman (WL) tests, which are generally used for evaluating the expressiveness of GNNs. By introducing the central inference problems of probabilistic graphical models (PGMs), the authors analyze GNNs. In addition, the authors design two methods (phantom nodes and phantom edges) for the expressive power.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written.\n- The research topic about the expressive power of GNNs is important and interesting.\n- The paper seems novel to me. Different from existing methods on the expressive power of GNNs, which use WL test, this paper analyze the expressive power of GNNs in the perspective of the probabilistic view.", "weaknesses": "- Do you have any ideas for the graph classification tasks? Generally, the papers about the  expressiveness power of GNNs use graph classification tasks to demonstrate the effectiveness of their methods.\n- Could you apply your methods on large-scale graphs?", "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": "", "extra_scores": {}}, {"review_id": "uXWt0SbIG0", "reviewer": "Reviewer_jjG1", "summary": "The paper studies the expressivity of the Graph neural networks from the perspective of probabilistic graphical methods. Although multiple works have previously established connections between GNNs and PGMs, this paper studies it from the perspective of expressive power of the GNNs. After formulating the correspondence between WL power with PGMs, the authors present several results in providing a new perspective of seeing the expressivity of GNNs in its ability to learn the complex higher-order distributions formalized as clique based MRFs.", "questions": "Please address the weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The GNN’s connection to the PGMs is developed in an interesting and principled way.. Specifically, the formulation overcomes the permutation invariance inherent to the graph neural networks but missing in the PGMs.\n1. The results progressively elaborate on the connections between GNN’s expressive power in terms of the learnable capacity of node marginals. \n1. Some of the results are surprising although many of them are intuitively known. The correspondence between k-wl and clique orders is intuitive and is \n1. The paper is well written and the presentation flow is reasonably clear.", "weaknesses": "1. The first paragraph is problematic. “implicitly assume that node representations learnt by GNNs are independent conditioned on node features and edges, thereby ignoring the joint dependency among nodes...” does not represent the related works accurately. These works do not ignore dependency among the nodes, which is captured via multiple rounds of message passing similar to loopy belief propagation. I find the first paragraph could be phrased in a different way to make the distinctions accurate.\n1. The introduction of phantom nodes and edges is not a novel development and closely resembles the other methods like CIN. However, the problem of inefficiency remains in such methods i.e. the computational complexity of finding maximal cliques which can be used for phantom nodes to guarantee the inferential capacity.\n1. Certain related works are missing in the paper. Recent works on Factor Graph Neural Networks (FGNN) [1] are highly related works in establishing connections between PGMs and GNNs. A small discussion on the relevance would be pertinent. \n1. The experimental section could be more elaborate to study the effectiveness of GNNs in learning higher-order distributions. For example, comparison with Zhen et al. (2023)  on inference of higher-order LDPC codes. \n\n**Overall,** \nI find the paper making a good contribution to the understanding of the GNN's expressivity in a new perspective from the lens of Probabilistic graphical models. Although, I haven't carefully checked all the proofs, the results are mostly not surprising.\n\n**References:**\n\n [1] Zhen Zhang, Mohammed Haroon Dupty, Fan Wu, Javen Qinfeng Shi, Wee Sun Lee. \"Factor Graph Neural Networks\" Journal of machine Learning research 24(181):1−54, 2023", "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": "", "extra_scores": {}}, {"review_id": "aHtDQsXakn", "reviewer": "Reviewer_G9eq", "summary": "This paper delves into the expressive power of Graph Neural Networks (GNNs) within the context of approximate inference in graphical models, going beyond the common association of GNNs with graph convolutions and Weisfeiler-Lehman (WL) graph isomorphism tests. The paper challenges the prevailing notion that GNNs necessitate integration with graphical models to enhance their probabilistic inference capacity, asserting that GNNs intrinsically possess robust approximation capabilities for posterior distributions. The research introduces a new expressive power hierarchy using Markov Random Fields (MRFs) with increasingly complex distributions and inference targets, providing insights into various GNN variants, including MPNNs, higher-order GNNs, subgraph GNNs, and labeling tricks in the contexts of node classification and link prediction. Furthermore, the paper presents a systematic framework for extending the capabilities of GNNs in modeling complex distributions and inference targets, with a particular focus on phantom nodes and phantom edges, showcasing their empirical improvements in real-world applications of GNNs.", "questions": "1. For link prediction tasks, how is the experiments done? Why don't choose metric of link prediction to be HITS@10 like in the BUDDY paper. Also, why not include other baselines in the BUDDY paper, especially the GNN ones? Also, maybe lack of other experiments on large link prediction datsets\n2. For node classification task, why not choose traditional homogeneous datasets and heterogeneous datasets like previous works. How will phantom nodes have impact when meeting graphs with different heterophily? Also, why For GCNII it hardly work better than SPN?\n3. What's the complexity of GNNs with phantom nodes or phantom edges, for node classification and link prediction ,respectively?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Theoretical analysis is solid and reasonable on the inference capacity of various GNNs.\n* The paper identifies that GNNs can do Probabilistic inference on its own, which has novelty than other methods combining GNN with graphical models.\n* The paper proposes methods like phantom nodes and edges based on their inference analysis framework and show experiments of their methods.", "weaknesses": "* Experiments on large link prediction datasets are lacked.\n* While the theoretical analysis has included a lot of GNN methods, the experiments don't include them all.\n* Experiments on various node classification datasets(including homogeneous and heterogeneous graphs) are lacked.\n* Improvements of better GNNs(like GCNII) in node classification is limited.\n* Experiments details are lacked, like how to choose hyperparameters.", "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": "", "extra_scores": {}}, {"review_id": "UTwNz3TQsJ", "reviewer": "Reviewer_G6RK", "summary": "The paper studies the expressiveness of different GNN variants from a probabilistic inference perspective. Specifically, under certain settings of PGMs and different ways to measure their complexity, the paper studies to what extent MPNNs can approximate node and edge marginals which are obtained from local minima of Bethe approximation. The analysis is also extended to other GNN variants. To equip GNNs with the power of estimating more complex node and edge marginals, phantom nodes and edges are proposed respectively, and experiments are conducted on several node and link prediction datasets to evaluate the proposed methods.", "questions": "1.  In 3.1, while lemma 1 is straight-forward, I do not fully understand why the authors mention “in graph machine learning fields each instance corresponds to different graphs with possibly different structures”, as the paper does not address the case of graph classification? And what does “instance” present? (the authors might wanna refer to a graph as an instance, but in the context of paper where node- and edge-level tasks are considered, each node or random variable in the PGM correspond an an instance.)\n2. What is the complexity of the proposed method, and are there any ways to scale it to large graphs?\n3. If possible, please also answer to questions in the weakness section.\n\n---\n\nI decrease score from 6 to 5 due to my lingering concerns, and there has been no response from the authors to date.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Analyzing how well GNNs can approximate marginals in PGMs is interesting (though there are limitations as will be discussed), and offers a new perspective for measuring the expressiveness of GNNs.\n2. The paper is generally well written with clear background introductions and problem setup. Many details are given in the appendix, which is also appreciated.\n2. A lot of analysis has been done with discussions on many different GNN variants and inference tasks. Results also seem solid (but I did not carefully check the proof).", "weaknesses": "1. Defining the discriminative power of potential function by WL test appears to be a somewhat contrived setup, whereby the problem still boils down to graph isomorphism. I am not sure how practically relevant this setting is, and whether it is truly “fundamentally different” with works on WL tests. A more comprehensive discussion about the connection may mitigate the issue.\n2. Following the above point, the analysis does not take into account node features, whereas in many PGMs node and clique potentials are functions on node features. This further stresses the point that the setup might deviate from practice.\n3. The proposed method seems not scalable as it requires identifying maximum cliques that is exponentially complex, and even relaxing it to cliques with size k has super-quadratic complexity O(n^k) (please correct me if I am wrong). This limitation has not been discussed in the paper, and experiments only include small datasets.\n4. The experimental results are relatively weak. E.g. on PPI, best performance in most cases (4 out of 6 columns in the table) is achieved by GCNII+SPN. Improvement on synthetic dataset is also limited, and Planetoid dataset is outdated. Baselines are also limited. Particularly, many GNN variants are considered in the analysis but are not compared in experiments, and I wonder why? Moreover, the proposed methods are essentially based on data augmentation, but competitors in this category are missing.\n\nTypos: invalid reference in appendix A and E.2; “a successful ? for minimizing” in 3.2; repeated references Bergen et al. and Cai \nat al.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)