Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs
Authors: Dingmin Wang
Yeyuan Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: Knowledge Graphs
First-Order Logic
Temporal Knowledge Graph
Graph Neural Networks

Abstract: As a powerful framework for graph representation learning, Graph Neural Networks (GNNs) have garnered significant attention in recent years. However, to the best of our knowledge, there has been no formal analysis of the logical expressiveness of GNNs as Boolean node classifiers over multi-relational graphs, where each edge carries a specific relation type. In this paper, we investigate $\mathcal{FOC}_2$, a fragment of first-order logic with two variables and counting quantifiers. On the negative side, we demonstrate that the R$^2$-GNN architecture, which extends the local message passing GNN by incorporating global readout, fails to capture $\mathcal{FOC}_2$ classifiers in the general case. Nevertheless, on the positive side, we establish that R$^2$-GNNs models are equivalent to $\mathcal{FOC}_2$ classifiers under certain restricted yet reasonable scenarios. To address the limitations of R$^2$-GNNs regarding expressiveness, we propose a simple graph transformation technique, akin to a preprocessing step, which can be executed in linear time. This transformation enables R$^2$-GNNs to effectively capture any $\mathcal{FOC}_2$ classifiers when applied to the "transformed" input graph. Moreover, we extend our analysis of expressiveness and graph transformation to temporal graphs, exploring several temporal GNN architectures and providing an expressiveness hierarchy for them. To validate our findings, we implement R$^2$-GNNs and the graph transformation technique and conduct empirical tests in node classification tasks against various well-known GNN architectures that support multi-relational or temporal graphs. Our experimental results consistently demonstrate that R$^2$-GNN with the graph transformation outperforms the baseline methods on both synthetic and real-world datasets

Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs
Dingmin Wang" University of Oxford dingmin wangdcs. ox ac.
Yeyuan Chen' University of Michigan yeyuanch@umi ch, edu
Abstract
As powerful framework for graph representation learning, Graph Neural Net- works (GNNs) have garnered significant attention in recent years. However, to the best of our knowledge, there has been formal analysis of the logical expres- siveness of GNNs as Boolean node classifiers over multi-relational graphs, where each edge carries specific relation type. In this paper, we investigate FOC₂, a fragment of first-order logic with two variables and counting quantifiers. On the negative side, we demonstrate that the R²-GNN architecture, which extends the local message passing GNN by incorporating global readout, fails to capture FOC₂ classifiers in the general case. Nevertheless, on the positive side, we establish that R² R2-GNN models are equivalent to FOC₂ classifiers under certain restricted yet reasonable scenarios. To address the limitations of G-NN regarding expressive- ness, we propose a simple graph transformation technique, akin to preprocessing step, which can executed in linear time. This transformation enables R2-GNN to effectively capture any FOC₂ classifiers when applied to the "transformed" input graph. Moreover, we extend our analysis of expressiveness and graph trans- formation to temporal graphs, exploring several temporal GNN architectures and providing an expressiveness hierarchy for them. To validate our findings, we im- plement R and the graph transformation technique and conduct empirical tests in node classification tasks against various well-known GNN architectures that support relltinnlational temporal graphs. Our experimental results con- sistently demonstrate that R R2-GNN with the graph transformation outperform the baseline methods both synthetic and real-world datasets. The code available at hhttts:////g githgb...b...... wwtpcommmlllloccccccccmcmmcm..ct / mttmmmmliiii ti graph
Introduction
Graph Neural Networks (GNNs) have become standard paradigm for learning with graph structured data, such as knowledge graphs Park al. [2019], Tena Cucala molecules Hao et al. [2020]. Gasteiger et al. [021]] Guo et al. [202 IJ. GNNs take as input graph where each node labelled by a feature vector, and then they recursively update the feature vector of each node by processing subset of the feature vectors from the previous layer. For example, many GNNs update node's feature vector by combining its value in the previous layer with the output of some aggregation function applied to its neighbours' feature vectors in the previous layer; in this case, after l iterations, a node's feature vector can capture structural information about the node's 's k-hop neighborhood. GNNs have proved to be very efficient in many applications like knowledge graph completion and recommender systems. Most previous work on GNNs mainly revolves around finding
[202T), Wang al. (2023) and
'Equal contribution, listed in alphabetical order.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

GNN architectures (e.g. using different aggregation functions or graph-level pooling schemes) which offer good empirical performance Kipf and Welling 2016), Xu et al. [2018]. Corso al. (2020). The
theoretical properties of different architectures, however, are not yet well understood.
In Xu et al. 2018), the authors first proposed theoretical framework to analyze the expressive power of GNNs by establishing a close connection between GNNs and the Weisfeiler-Lchman (1-WL) test for checking graph isomorphism. Similarly, Geerts and Reutter [2022] provides an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (K-L)) tests. However, the characterization in terms of the Weisfeiler-Lehman test only calibrates distinguishing ability. It cannot answer which Boolean node classifier can be expressed by GNNs. To this end, Barceló et al. [2020] consider a class of GNNs named ACR-GNNS proposed in IBBattallia et al. (2018). where the update function uses a "global" aggregation of the features of all nodes in the graph in addition to the typical aggregation of feature vectors of neighbour nodes. Then, the authors of the paper prove that in the single-relationa. D scenario, ACR-GNN can capture every Boolean node classifier expressible in the logic FOC2-
However, most knowledge graphs need multiple relation types. For example, in a family tree, there are multiple different relation types such as "father" and "spouse". In this paper, we consider the abstraction of widely used GNN architecture called R-GCN Schlichtkrull el al. 2018)) which applicable to multi-relational graphs. Following Barceló et al. [2020], we define R--GNN as a generalization of R-GCN by adding readout functions to the neighborhood aggregation scheme. We show that although adding readout functions enables GNNs to aggregate information of isolated nodes that can not be collected by the nighhorhood-baser aggregation mechanism, R2-GNN are still unable to capture all Boolean node classifiers expressible as formulas in logic FOC₂ in multi-relational scenarios if applied "directly" to the input. This leaves us with the following questions: (1) Are there reasonable and practical sub-classes of multi-relational graphs for which FOC₂ can be captured by RR-GNN? (2) Is there some simple way encode input graphs, so that all FOC₂ node classifiers can be captured by R"-GNN for all multi-relational graphs?
In this paper, we provide answers to the above questions. Moreover, we show that our theoretical findings also transfer to temporal knowledge graphs, which are studied extensively in Park et al.) [202] and Gao and Ribeiro [2022). In particular, we leverage the findings from Gao and Ribeiro 2022 which shows that a temporal graph can be transformed into an "equivvlent" static multi- relational graph. Consequently, our results, originally formulated for static multi-relational graphs, naturally extend to the domain of temporal knowledge graphs. Our contributions are as follows:
We calibrate the logic expressiveness of Ra-GNN as node classifiers over different sub- classes of multi-relational graphs.
In light of some negative results about the expressiveness of R²-GNN found in the multi- relational scenario, there a compelling need to boost the power of R To address this challenge, we propose a graph transformation and show that such a transformation enables
R²-GNN to capture each classifier expressible as a FOC₂ formula in all multi-relational graphs.
We expand the scope of expressiveness results and graph transformation from static multi- relational graphs to temporal settings. Within this context, we propose several temporal GNN architectures and subject them a comparative analysis with frameworks outlined in
Gao and Ribeiro 2022). Ultimately, we derive expressiveness hierarchy.
2 Preliminaries
2.1 Multi-relational Graphs
A multi-relationn graph is a 4-tuple G = EV,,, Pı, P2), where V, P1, Pg are finite sets of nodes, rypes and relations (a.k.a, unary/binary predicates [T] respectively, and & is a set of triples of the form (U1,P2, v2) or (v, (i)e, where E Pt, P2 E P2. U1 U2, v E V, and type is a special symbol.
Next, given arbitrary (but fixed) finite sets P1 and P2 of unary and binary predicates, respectively, we define the following three kinds of graph classes:
"The "single-relational" means there only one type of edges in the graph. Forr directed graphs. we assume P2 contains relations both in two directions (with wwerse-predicates) Moreover, assume there exists an "equality relation" EQ P2 such that Vr,y E V, EQ(x,y) = L.

---

uiiersal graph class can be any set of graphs of the form P2.
bounded graph class is universal graph class for which there exists such that each
graph in the class has no more than n nodes;
a simple graph class
universal graph class where for each graph (V, E, P1. P2) in the
class, and for each pair of nodes 11, 02 V, there exists at most one triple in & of the form (21,,2;22), where P2 E P2.
We typically use symbols Gus Go. and G. to denote universal, bounded, and simple graph classes, respectively.
Definition 1. For given graph class over predicates P1 and Pz. Boolean node classifier is function C such that for each graph G = PI, in that graph class, and each & E V, C classifies as true faalse.
2.2 Graph Neural Networks
Node Encoding We leverage a GNN as a Boolean node classifier for multi-relational graphs, which cannot be directly processed by GNN architectures, requiring graphs where each node is labelled by an initial feature vector. Therefore, we require some form of encoding to map a multi-relational graph to a suitable input for GNN. Such an encoding should keep graph permutation invariance Geerts and Reutter [2021) since we don't want a GNN to have different outputs for isomorphic graphs. Inspired by Liu al. [202]] for a multi-relational graph G (V,&, P1.P2) and ordering P1.P2. Pk: of the predicates in Pt. we define an initialization function I(-) which maps each node E V Boolean feature vector / (() = X. with fixed dimension [Pl where the ith component of the vector is set to 1 if and only if the node v is of the type that is, (x,); = if and only if (v, type, pi) E &. If P1 is an empty set, we specify that each node has a 1-dimension feature vector whose value is 1. Clearly, this encoding is permutation invariant.
2018 a widely-used GNN architecture that can be applied to multi-relational graphs. By allowing different aggregation and combination functions, we extend
R-GNN R-GON Schlichtkrull et al.
L and (C |
R- R-GCN to a more general form which we call R-GNN. Formally, let (44 (1)
be two sets of aggregation and combination functions. An R-GNN computes vectors x! for every node of the multi-relational graph G = PI.P) on each layer i, via the recursive formula
(+) (i-1), (A) (1x!
Nas(o)))) (Px) )
where z: is the initial feature vector encoded by ((-), H-B denotes multiset, (-/Fal denotes tuple of size [P2. NPl denotes the neighbours of u via a binary relation py Ps, that is, nodes w E V such that w) E.
R2-GNN R2-GNN extends R-GNN by specifying readout functions ( ) which aggregates
(8) of each node in G' each layer is the feature vectors of all the nodes in a graph. The vector computed by the following formula
1Pal x (i-1) (1)))) (A)) Nas())))) j-1 (Ex( (u))))
0 = =c()
(2)
Every layer in R2-GNN first computes the aggregation over all the nodes in G; then, for every node v, computes the aggregation over the neighbors of e; and finally, it combines the features of with the two aggregation vectors; the result of this operation is the new feature vector for v. Please note that an R-GNN can be seen as a special type of R2-GNN where the combination function simply ignores the output of the readout function.
is worth noting that R-GNN as well as R2-GNN is not a specific model architecture; a framework that contains a bunch of different GNN architectures. In the paper, we mentioned it's generalized from R-GCN (Schlichtkrull et al. 2018)), but our primary objective is to establish comprehensive framework that serves as abstraction of most Message-Passe Passing GNNs (MPGNN).

---

In the definitions (Equations and 22,, the functions can be set as any functions, such as matrix multiplications or VKVaattentions. Most commonly used GNN such as R-GCN (Schlichtkrul et al.) (018)) and R-GAT (Busbridge et al. 2019) are captured (upper-bounded) within our R-GNN frameworks. Other related works, such as (Barceló et al. [2020], Huang et al. [2023], Qiu al. (2023]) also use intrinsically the same framework as our R- E-GNN/RR--GN which has been widely adopted and studied within the GNN community. We believe that analyzing these frameworks can yield common insights applicable to numerous existing GNNs
GNN-based Boolean node classifier In order translate the output of a GNN Boolean value, we apply a Boolean classification function CLS IR - [flue where d is the dimension of the feature vectors x Hence, a Boolean node classifier based on an R2-GNN M proceeds in three steps: (1) encode the input multi- multi-relational graph G as described above, (2) apply the R and (3) apply CLS to the output of the R -N-G.. This produces true or false value for each node of G. In what follows, we abuse the language and represent familly of GNN-based Boolcan node classifiers by the name of the corresponding GNN architecture; for example, R²-GNV is the set of all PP-GNN-based Boolean node classifiers.
2.3 Logic FOC₂ Formulas
In this paper, we focus on the logic FOC2, fragment of first-order logic that only allows formulas with at most two variables, but turn permits to use counting quantifiers. Formally, given two finite sets Pi and P& of unary and binary predicates, respectively, a FOC2 formula yp is inductively defined according to the following grammar:
:: == A(x) r(z,y) A lvvp 1 where A P1 and r P2
(3)
where z/y in the above rules can be replaced by one another. But please note that and y are the only variable names we allowed to use (Though we can reuse these two names). In particular, FOC, formula yo with exactly one free variable represents a Boolean node classifier for multi-relational graphs as follows: node u is assigned to true iff the formula fo obtained by substituting æ by is satisfied by the (logical) model represented by the multi-relational graph. Similarly as the GNN-based Boolean node classifiers, in what follows, abuse the language and represent the family of FOC2 Boolean node classifiers by its name FOC₂.
2.4 Inclusion and Equality Relationships
In this paper, we will mainly talk about inclusion/non inclussoonnoon-inuussiioouuuuuu hicluusinnoquuliitttttfiriiiceei relationships between different node classifier families on certain graph classes. To avoid ambiguity, we give formal definitions of these relationships here. These definitions are all quite natural.
Definition 2. For any two sets of node classifier A,B, and graph class G. We say:
A B on G, iff for any node classifier that for all graph G E G and v E V (G), it satisfies a a(G.v) = b(G,v) (Namely, a and b evaluate the same for all instances in 9). It implies B is more expressive than A G.
A, there exists some node classifier b B such
A L B on G. iff the above condition in item I doesn't t hold.
A C B on G. iff A C but B & A. It implies B is strictly more expressive than on G. A B iff A C B and B C A. It implies A and B has the same expressivity on G.
3 Related Work
The relationship between first-order logic and the Weisfeiler-Lchman test was initially established
by CCai et al. [1989]. Subsequently, more recent works such as Xu et al. (2018). have connected
the Weisteiler-Lehmnn test with expressivity of GNN. This line of research has been followed by
numerous studies, including Maron et al. 2220). which explore the distinguishability of GNNs using the Weisfeiler-Lehmaae test technique. In particular, Barceló et al.] [2020) introduced the calibration of logical expressivity in GNN- classifiers and proposed a connection between FOC,, and
R2-GNN single-relational scenario. This led to emergence of related works, such as Huang
et al. 2023), Geerts and Reutter [202T], and Qiu et al. (2023). all of which delve into the logical
expressivity GNNs. Moreover, the theoretical analysis provided in Gao and Ribeiro inspired us extend our results temporal graph scenarios.
2022 has

---

P2
p2
P2
p1
G2
G
p11
pt
p2
Node classifier: x(x) == 321 ((pi(x.y)) A p2(x,)))
Figure 1: Multi-edge graphs 11 and G2, and a FOC₂ formula (p(x) that distinguishes them; (o()) evaluates node a in G1 to true and node in G2 to false.
4 Logic expressiveness of R*-GNN in multi-relational graphs
Our analysis begins with the observation that certain Boolcan classifiers can be represented as FOC, formulas, but remain beyond the expressiveness of any R²-GNN (and consequently, any R-GNN or R-GCN). An illustrative example of this distinction is provided in Figure [ In this example, we make the assumption that Pi is empty, thereby ensuring that all nodes in both G1 and G2 possess identical initial feature vectors. Additionally, P2 is defined to comprise precisely two relations, namely, pl and p2. evident that no R2-GNN can distinguish the node a in Gi from node G2 that is, when an R2-GNN performs the neighbour-basee aggregation, it cannot distinguish whether the Pi nniighoour a and the P2- -ciighhbourr cannot help in distinguishing those nodes because all nodes have the same feature vector.
are the same. Moreover, the global readout aggregation
We proceed formalize this intuition and, in the reverse direction, offer corresponding result. We demonstrate that there exist Boolean classifiers that fall within the scope of R2-GNN but elude capture by any FOC₂ formula.
Proposition FOC₂ & R2-GNN and R2-GNN & FOC₂ on some universal graph class.
We prove Proposition 3 in the Appendix. Here, we give some intuition about the proof. The first result proved using the example shown in Figure [ which we have already discussed. To show R2-GNN g FOC2, we construct classifier which classifies node into true iff the node has larger number of -type neighbors than that of r2-type neighbors. We can prove that we can easily construct an R=-GNN to capture However, for FOC₂, this cannot be done, since we can only use counting quantifiers expressing that there exist at most or at least a specific number of neighbours connected particular relation, but target classifier requires comparing indefinite numbers of neighbours via two relations. Thus, we proceed by contradiction, assume that there exists a FOC₂ classifier equivalent and then find two large enough graphs with nodes that cannot be distinguished by the classifier (but can be distinguished by c).
In some world applications, it is often possible to find an upper bound on the size of any possible input graph or to ensure that any input graph will contain at most one relation between every two nodes. For this reason, we next present restricted but positive&praatiial expressiveness results on bounded and simple graph classes.
Theorem 4. FOC, R2 R2-GNN on any simple graph class, and FOC, S. -NNN on some simple graph class.
The key idea the construction that we will first transform the FOC, formula into a new form which call pelation-speciffes FOC₂ (an equivalent form to FOC₂, more details in Appendix), and then we are able to construct an equivalent R²-GNN inductively over the parser tree of the transformed formula.
Having Theorem one may wonder about the inclusion relationship of R2-GNN and FOC, in the backward direction. In Proposition 3 we showed that for arbitrary universal graph classes, this inclusion relationship fails. However, given bounded graph class, we can show that for each R2-GNN Boolean node classifier, one can write an equivalent FOC₂ classifier. An intuition about why this is the case is that all graphs in a bounded graph class will have at most n constants, for some known N, so for each R² RN-GNN classifier, can construct an equivalent FOC, classifier with finite number of sub-formulas to recover the features obtained at different layers of R²-GNN.
Theorem R2-GNN S FOC₂ on any bounded graph class, and R2 -NN ç FOC₂ on some bounded graph class.
5

---

G
G'
P1
P1
F
b
a ... h.......
ab
ba
....
b
P2
P2
Figure 2: Graph Transformation.
Combining Theorem 4 and Theorem
|
we have the following corollary.
Corollary 5.1. RN-GNN= = FOC₂ any bounded simple graph class.
At LLst, one may be curious about the complexity of logical classifier in Theorem Here we can give rather loose bound as follows:
Theorem 6. For any bounded graph class Go- Suppose any E Go has no more than N nodes, and G. has unary predicate set Pi and relation (binary predicate) set Pz. Let m. == |P == | then for any node classifier c, suppose e can represented as an R2-GNN with depth (layer number) L, then by Theorem tthee is a FOC₂ classifier ip equivalent to over Gv, and the following hold:
The quantifier depth of up is no more than L.
* The size of (quantified by the number of nodes of 4 parse tree) is no more than 221(L),
where ((L) == 222
(())) O(2226mm (a0mmmmmm))) mm2)
The key idea of Theorem ijis the following: First, by Lemma 27 in our appendix, the combination of ALL FOC₂ logical classifiers with quantifier depth no more than L can already distinguish accepting and rejecting instances of c. Then by Proposition 26 (This is a key point of this bound: please refer to our appendix), We know the number of intrinsically different bounded-depth FOC₂ classifiers is finite, so we only need to get an upper bound on this number. Finally. we can get the desired bound by iteratively using the fact that a boolean combination of set of formulas can be always written as DNF (disjunctive normal form). The tower of power of two comes from L rounds of DNF enumerations, Although the bound seems scary, it is rather loose bound. We give a detailed proof of Theorem o in the appendix along with the proof of Theorem 5
R2-GNN capture FOC₂ over transformed multi-relational graphs
As we pointed out in the previous section, one of the reasons why R2-GNN cannot capture FOC₂ classifiers over arbitrary universal graph classes is that in multi-relational graphs, they cannot distin- guish whether information about having neighbour connected via a particular relation comes from the same neighbour node or different neighbour nodes. Towards solving this problem, we propose a graph transformation (see Definition 7), which enables R2- to capture all FOC₂ classifiers on multi-relational graphs. Similar transformation operations have also been used and proved to be an effective way to encode multi-relational graphs previous studies, e.g.. MGNNS Tena Cucala et al. (2221) Indigo [iu et al. (202T) and Time- then-Graph Gao and Ribeiro (2022).
Definition 7. Given a multigraah G E.E,PP P1, the transformation F will map G to another graph F F()) (V',E', E', P1) with changes described as follows:
for any two nodes a, b E V, if there exists at least one relation p E Pg between and b, we add two new nodes ab and ba to V".
we add a new unary predicate (primal) and two new binary predicates aax22) Hence, F(P:) = P U ( and F(P2) == P/- = P2 U (aux1, aux2]. For each node v' E V', primal(v') = iff is also in V; otherwise, primal(v') = O: for each triplet of the form (a.P2, b) in E, we add to E' four new triples: (ab,aux1, (bu,aux1, b) and (ub,aux2, ba) as well as (ab.y2,bu)
An example is in Figure We can see that after applying the graph transformation, we need to execute two more hops to propagate information from node a to node However, now we are able to distinguish whether the information about different relations comes from the same node or different nodes. This transformation can be implemented and stored linear time/space complexity O(VVI + [&]), which is very efficient.

---

Definition 8. Given a classifier C and a transformation function F. we define C o F to be new classifier, an extension of with an additional transformation operation on the input graph.
With graph transformation F, we get more powerful class of classifiers than R²-GNN. We analyze the logical expressiveness R²-GNN oF in multi-relations graphs, which means first transform a graph to F(G) and then run an R2-GNN on F(G). We will see in the following that this transformation F boosts the logical expressiveness of R--GNN prominently.
Ra-GNN oF
Rº-GNN
FOC₂
Theorem 9. R²-GNN S R2- -GNN oF on any universal graph class.
Theorem 10. FOC₂ C R R2-GNN oF on any universal graph class.
Figure 3: Relations of R²-GNN, FOC₂ and R² R2-GNN oF.
Theorem demonstrates that R2-GNN with graph transformation F have more expressiveness than R2-GNN; and Theorem 10 shows the connection between FOC₂ and R²-GNN equipped with graph transformation F. We depict their relations in Figure 3 Theorem a natural result since information is lost in the process of transformation, while Theorem I0 is
an extension on Theorem 4 whose formal proofs can be found in the Appendix. As for the backward direction, have the result shown in Theorem
Theorem 11. R2-GNN oF C FOC₂ any bounded graph class.
The proof of the theorem relatively straightforward based on previous results: by Theorem 5 it follows that Ra-GNN of C FOC₂ F on any bounded graph class. Then, it suffices to prove FOC₂ F C FOC,, which we do by using induction over the quantifier depth.
By combining Theorem 10 and Theorem we obtain Corollary 11.1 stating that FOC, and R²-GNN of have the same expressiveness with respect to bounded graph classes. Corollary [1.] does not hold for arbitrary universal graph classes, but our finding is nevertheless exciting because, in many real-world applications there are upper bounds over input graph size.
Corollary 11.1. R2-GNN of FOC₂ on any bounded graph class.
To show the strict separation as in Figure 3 we can combine Proposition 3 and theorems 4 and and Theorem 10 to directly get the following:
Corollary 11.2. R²-GNN Ç. R2-GNN o some universal graph class, and FOC2 R2-GNN oF on some simple graph class.
One may think after transformation F, the logic FOC, o F with new predicateds becomes stronger as well. However by similar proof for Theorem 10 and Lemma 28 we can actually show FOC₂ C FOC₂ always holds, so won't bring added power for FOC2. However, it indeed make RN-GNN strictly more expressive.
6 Temporal Graphs
As stated in Gao and Ribeiro 2022 a temporal knowledge graph, composed of multiple snapshots, consistently undergo transformation into equivalent static representation as multi-relational graph. Consequently, this signifies that our theoretical results initially devised for multi-relational graphs can be extended apply temporal graphs, albeit through certain manner of transfer.
Following previous work Jin et al. 2019], Pareja et al. 2020 Park et al. 2022) Gao and Ribeiro 2002).. we define a temporal knowledge graph as set of graph "snapshots" distributed over sequence of finite and discrete time points {1, {1, 2..,. T).. Formally, a temporal knowledge graph is a set G (G, Gr for some T' E N, where each G, is static multi-relational graph. All these G2 share the same node set and predicate set.
In temporal knowledge graph, a relation unary fact between two nodes might hold or disappear across the given timestamps. For example, a node a may be connected a node via relation p in the first snapshot, but not in the second; in this case, we have (a,p, b) in G₁ not in G2. To keep track of which relations hold at which snapshots, we propose temporal predicates, an operation which we define in Definition 12
7

---

R2-TGNN
R2-GNNoH
C
R2-GNNoF H
R²-TGNN oF
time-then- tae-tghnnpghhhh
time-and-graph
Figure Hierarchic expressiveness.
Definition 12. Given a temporal graph G =G1,.... GrG, where each G. of the form (V,, P1) P2), temporal predicates are obtained from G by replacing, for each t .T) and each p E P2, each triple (Va: Ub) & with (Va, ,06), where p is a fresh predicate, unique for and l. Similarly, each unary fact (va:q) E &t, q E Pi should be replaced by (wast).
Note that temporalising introduces T P| new predicates in total. By temporalizing predicates, assign a superscript to each predicate and use to distinguish relations over different timestamps.
Definition 13. Given temporal knowledge graph G = {G1..... .... the collapse function H maps G to the static graph H (G) obtained by taking the union of graphs over all timestamps in the temporalization of G.
As we have proved in Section 5 for multi-relational graphs, R2-GNN with graph transformation is more powerful than the pure RCGGNN. Here, we transfer these theoretical findings in multi-relational graphs to the setting of temporal knowledge graphs. To be more specific, after temporalizing predicates, we apply graph transformation to each graph snapshot.
Definition 14. We define Fr to be the temporal graph transformation that takes any temporal knowledge graph input, applies graph transformation to each snapshot and outputs. Specially, non-primal nodes, auxl and aux2 edges added any snapshot should be added into all snapshots.
R2-TGNN Gao and Ribeiro 2022) casts node representation in temporal graphs into two frame- works: time-and-graph and time-then- graph. Due to space constraints, refer interested readers to Gao and Ribeiro [2022) for more details about the two frameworks. Here, we define a more general GNN-based framework abbreviated R2-TGNN, where each R2-TGNN is sequence (Ar) where each Ar is an R²-GNN model.Given a temporal knowledge graph G = (GI..... Gr where
G2 (Ve, Ec, PI, P2) for each TT.....T.. The updating rule is follows:
x Ae Ai (Geux"))
where
y = [To, (v) "1, V..
where Ig. (v) is the one-hot initial feature vector of node v timestamp t. and A, (G,,v.y") calculates the new feature vector of v by running the R2-GNN model A, on G,, but using y' as the initial feature vectors. shown Theorem 15| R2-TGNN composed with Ff have the same expressiveness as time-then-eee graph while being more powerful than time-and-gre graph.. Theorem 15. aome-and-grappe S -GNN FT time-then graph..
We also establish the validity of Theorem 16
which asserts that R²-TGNN with graph transformation maintains the same expressive power, whether it is applied directly to the temporal graph or the equivalent collapsed static multi-relational graph
Theorem 16. -GNN o Ra-GNN of o
We also prove strict inclusion that R2-TGNN R2-TGNNeH. Finally get the following hierarchy of these frameworks as in Figure 6 the proof of Theorem 17 is in the appendix. Theorem 17. The following hold:
R2-GNN Ç. R2-GNN oH Ç R2-TGNN oF o H= RT-NGNN FT fime-tthn-graphe Lime-and-graph Ç. R2-TGNN oF..
R²-TGNN'S & time-and-gren graph.
*Since temporalized predicates and timestamps make the definitions of bounde//simpleevnvvess graph class
vague, we no longer distinguish them in temporal settings. In theorem statements of this section, = always hold for any temproral graph class, and Ç. hold for some temporal graph class

---

FOC₂ classifier
PP2
IP'
PP4
Aggregation
sum
max
mean
sum
max
mcan
sum
max
mean
Sum
max
mcan
Temporal Graphs Setting
R-TGNN R2-TGNN
100
60.7
65,4
61.0
51.3
52.4
93.7
82.3
84.4
83.5
60.0
61.3
100
63.5
66.8
93.1
57.7
60.2
94.5
83.3
85.9
85.0
62.3
66.2
R²- R2-TGNN ON
100
67.2
99.0
57.6
62.2
100
88.8
89.2
98.1
73.4
77.5
Aggregated Static Graphs
Setting
R-GNN oH
100
61.2
69.9
62.3
51.3
55.5
94.7
80.5
83.2
80.2
60.1
60.4
-2-GNN aH R²-GNN oF o H
100
62.7
66.8
92.4
56.3
58.5
95.5
84.2
85.2
81.0
58.3
64.5
100
70.2
70.8
98.8
60.6
60.2
100
85.6
86.5
7
95.5
70.3
79.7
Table 1: Test set node classification accuracies (%) on synthetic temporal multi-relational graphs
datasets and their aggregated static multi-relational graphs datasets. The best results are highlighted for two different settings.
Experiment
We empirically verify our theoretical findings for multi-relational graphs by evaluating and comparing the testing performance of R²-GNN with graph transformation and less powerful GNNs (R-GNN and R²-GNN). We did two groups of experiments on synthetic datasets and real-world datasets, respectively. Details for datasets generation and statistical information as well as hyper-parameters can be found in the Appendix.
7.1 Synthetic Datasets
We first define three simple FOC₂ classifiers
P1 == y Red (v)) A 3 (pp((()))).)))) Blue?(y))
4 == g110,20| y (i-pp(((-)))) (m.y) A (v())
93 = 7 A (f(,))
Besides, we define another complicate FOC₂ classifier denoted as 1o shown as follows:
P4 = V (=2"yBBaet()))xRdd (y) (q)
(z.y) ( (ate))//p///..))//////) (op.))))p(
351510 10
where x'(y)= = 322x ))))==>>a<pp( (z.y) Red (z)) 32 Blue (x))
For each of them, we generate an independent dataset containing 7k multi-relational graphs of size up to 50-1000 nodes for training and 500 multi-relational graphs of size similar to the train set. We tried different configurations for the aggregation functions and evaluated the node classification performances of three temporal GNN methods (R-TGNNs, R2-TGNNs and R -GNNS oF on these datasets.
We verify our hypothesis empirically according to models' actual performances of fitting these three classifiers. Theoretically, (P1 should be captured by all three models because the classification result of node is decided by the information of its neighbor nodes, which can be accomplished by the general neighborhood based aggregation mechanism. yo2 should not be captured by R-TGNN because the use of -yf (aryy) as a guard means that the classification result of a node depends on the global information including those isolated nodes, which needs a global readout. For 4P3 and yos, they should only be captured by R2-TGNNs O An intuitive cxplanation for this argument that if we temporalise predicates and then collapse the temporal graph into its equivalent static multi-relational graph using H, we will encounter the same issue as in the Figure Thus we can't distinguish expected nodes without graph transformation.
Results for temporal GNN methods and static GNN methods on four synthetic datasets can be found in Table [ We can see that R2-GNN with graph transformation achieves the best performance. Our theoretical findings show that a more expressive model, and the experiments indeed suggest that the model can exploit this theoretical expressiveness advantage to produce better results. Besides, we can also see that R oF o H and R²-TGNN oFT achieve almost the same performance, which is in line with Theorem [6

---

Table 2: Results on temporal graphs.
Brain-10
Models
Category
Source
GCRN-M2
time-and-gran
Seo et al.
2018
77.0
61.2
73.1
DCRNN
time-and-gen and-graph
Li et al.
2018
84.0
70.1
66.5
TGAT
time-then-grant
Xu et al.
2020
80.0
72.3
79.0
TGN
time-then-gran -gaeng
Rossi ct al.
20200a
91.2
88.5
89.2
GRU-GCN
time-then-graph
Gao and Ribeiro
[2022]
91.6
88.2
87.1
R-TGNN
85.0
82.3
82.8
R
94.8
82.3
91.0
R2-TGNN oF
94.0
83.5
92.5
7.2 Real-world Datasets
For real-world static multi- relational graphs benchmarks, we used AIFB and MUTAG from Ristoski and Paulheim [2016]. Since open source datasets for the node classification temporal knowledge graphs are rare, we only tried one dataset Brain-10 Gao and Ribeiro 2022 for temporal settings
Table 3: Results on two static multi-relational graphs.
Models
AIFB max
MUTAG
sum
mean
sum
max
mean
R-GNN
91.7
73.8
82.5
76.5
63.3
73.2
R2-GNN
91.7
73.8
82.5
85.3
62.1
79.5
R2-GNN oF
97.2
75.0
89.2
88.2
65.5
82.1
R-GCN
95.8
77.9
86.3
73.2
65.7
72.1
For static multi-relational graphs, compare the performances of
our methods with RGCN (Schlichtkrul et al. and the initial embedding of each node is initialised based the node index, the initialisation functional is not pernutation-equivaaiinn Chen et al. 20119] and RGCN cannot be used to perform an isomorphism test. However, from Table 3 we can that R2-GNN with graph transformation still achieves the highest accuracy while being able to be used for the graph isomorphism test. Besides, R2-GNN of also performs better compared with both R-GNN and R2-GNN. This again suggests that the extra expressive power gained by adding graph transformation step to R RNN can be exploited by the model to obtain better results.
2018 Note that RGCN assigns each node an index
For temporal graphs, Gao and Ribeiro [022] have classified existing temporal models into two categories, fime-and-gre graph and time-then-grupp and shown that time-then-graph models have better performance. We choose five models mentioned in |ao and Ribeiro [2022] as our baseline and include the best accuracy of the dataset Brain-10 reported Gao and Ribeiro 2022]] As expected, R RG-GNd 22-TGNN F achieve better performance than that of the baseline models and R-TGNN accoring to Table 2 However, we observed that although theory, R2-TGNN oF has stronger expressive power than R2-TGNN, we did not see an improvement when using R2-TGNN OF (0.8% accuracy drop). To some extent, it may show that some commonly used benchmarks are inadequate for testing advanced GNN variants. Similar phenomena have also been observed in previous works Chen al. [2019b) Barceló al. (2020).
8 Conclusion
We analyze expressivity of R2-GNNs with and without graph transformation in nulti-relational graphs under different situations. Furthermore, we extend our theoretical findings to the temporal graph setting. Our experimental results confirm our theoretical insights, particularly demonstrating the state-of-the-ar performance achieved by our graph transformation technique.
'The other three temporal dataset mentioned in Gao and Ribeiro 2022
not released.
10

---

9
Acknowledgements
The authors extend their gratitude to Bernardo Cuenca Grau and David Tena Cucala for their valuable insights, stimulating discussions, and support.
References
Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, and Christos Faloutsos. Estimating node importance in knowledge graphs using graph neural networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pages 596-606, 2019.
David Jaime Tena Cucala, Bernardo Cuenca Grau, Egor V Kostylev, and Boris Motik. Explainable gun-based models over knowledge graphs. In International Conference on Learning Representa- tions, 2021.
Dingmin Wang, Yeyuan Chen, and Bernardo Cuenca Grau. Efficient embeddings of logical variables for query answering over incomplete knowledge graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4652-465 46522,446,,00 2023.
Zhongkai Hao, Chengqiang Lu, Zhenya Huang, Hao Wang, Zheyuan Hu, Qi Liu, Enhong Chen, and Cheekong Lee. Asgn: An active semi-supervised graph neural network for molecular property prediction. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 731-752, 2020.
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph neural networks for molecules. Advances in Neural Information Processing Systems, pages 6790-6802, 2021.
Zhichun Guo, Chuxu Zhang, Wenhao Yu, John Herr, Olaf Wiest, Meng Jiang, and Nitesh Chawla. Few-shot graph learning for molecular property prediction. In Proceedings of the Web Conference 2021, pages 2559-25677 2021.
Thomas N Kipf and Max Welling, Sepi-super classification with graph convolutional networks. arXiv preprint arviv: 1609.66992222 000.000900,02... 2016.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 11Xiv:18/0.00026, 2018.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Velivckovic. Principal neighbourhood aggregation for graph nets. In NewrlPS, 2020.
Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. arXiv preprint arXiv:2204.04661, 2022.
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva.
The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020. URL httppp///ppppeeeeess..eee//rrrrr
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01 1806.01261, 2018.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018.
Namyong Park, Fuchen Liu, Purvanshi Mehta, Dana Cristofor, Christos Faloutsos, and Yuxiao Dong. Evokg: Jointly modeling event time and network structure for reasoning over temporal knowledge graphs. Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 794-803, 2022.

---

Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In International Conference on Machine Learning, pages 7052-7076. PMLR, 2022.
Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2021.
Shuwen Liu, Bernardo Grau, Ian Horrocks, and Egor Kostylev. Indigo: Gnn-based inductive
knowledge graph completion using pair-wise encoding. Advances in Neural Information Processing Systems, 34:2034 2045, 2021.
Dan Bushridge, Dane Sherburn, Pietro Cavallo, and Nils Hammerla, Relational graph attention networks, 2019.
Xingyue Huang, Miguel Romero Orth, ismail Ilkan Ceylan, and Pablo Barceló. A theory of link prediction via relational weisfeiler-leman, 2023.
Haiquan Qiu, Yongqi Zhang. Yong Li, and Quanming Yao. Logical expressiveness of graph neural network for knowledge graph reasoning, 2023.
J.-Y. Cai, M. Furer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. In 30th Annual Symposium on Foundations of Computer Science, pages 612-617, 1989. doi: 10. 10.119//FFC.1999
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks, 2020.
Woojeong Jin, Meng Qu, Xisen Jin, and Xiang Ren. Recurrent event network: Autoregressive structure inference over temporal knowledge graphs. arXiv preprint arXiv:1904.05530 2019.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5363-5370, 2020.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International conference on neural information processing, pages 362-373. Springer, 2018.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In International Conference on Learning Representations, 2018.
Da Xu, Chuanwei Ruan, Evren Körpeoglu, Sushant Kumar, and Kannan Achan. Inductive repre- sentation learning on temporal graphs. International Conference on Leurning Representations, 2020.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637 2020a.
Petar Ristoski and Heiko Paulheim. Rdf2vec: Rdf graph embeddings for data mining. In International Semantic Web Conference, pages 498-514. Springer, 2016.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019a.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint arXiv:1905.044 2019b.
Brian A Davey and Hilary A Priestley, Introduction lattices and order. Cambridge university press, 2002.
Jia Li, Zhichao Han, Hong Cheng, Jiao Su, Pengyun Wang, Jianfeng Zhang, and Lujia Pan. Predicting path failure in time-evolving graphs, 2019.
12

---

Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks, 2016. |ttppss////xx abs/
1612. 1612.07659
Jinyin Chen, Xueke Wang, and Xuanheng Xu. Gc-lstm: Graph convolution embedded Istm for dynamic link prediction, 2018. URL
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks.
Pattern Recognition, 97:107000, jan 2020. doi: 10. 10011f/ppatog.200911700000.. URL https
//doi.org/// 1016%2FF -attcoo................oo 2019.107000,
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dynamic graph representation learning via self-attention networks, 2018.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasea, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs, 2020b. URL https
7/arxiv. www.vvorggaaee abaaabas//000/ 10637
Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, page 440 440-449, New York. NY. USA, 1992. Association for Computing Machinery. ISBN 089791497X. URL https: http:://doooooe http::::://io.////////// 10. 1145/ 130385. 130432
doi: 10.1145/1 103551138855,.0 130432.
13

---

Appendix
Table of Contents
Preliminaries for Proofs
15
B Proof Proposition
Proof of Theorem
20
D Proof of Theorem Sland and heoremm 6
21
E Proof of Theorem 9
23
Proof Theorem
G Proof of Theorem
26
H Proof of heorem 15
28
Proof of Theorem 16
31
Proof Theorem
Experiment Supplementary
34
K.1 Synthetic dataset generation
34
2 Statistical Information for Datasets
34
K.3 Hlyper-paaaeed
35
More Results.
35
14

---

A Preliminaries for Proofs
In this section, we give some preliminaries which will be used to prove the theorems, propositions and lemmas shown in our main body. In what follows, we fix unary predicate Pi and binary predicate Set P2.
Definition 18. For an RC-GNN. we say it is 0/1-GNN if the recursive formula used to compute vectors x for each node in multi-relationn graph G {V,E, Pi, P2) each layer i is in the following form
x = -5((10)
+ 8(1) ))
x
EE rEPs WEV
10x (0)((-1) R
x (i LEEV
Σ
(5)
where CL., AA RR(() are all integer matrices of size de x 1, b(9) is bias column vector with size d, x 1, where di-1 and di are input/output dimensions, and f is defined as max (0,mnn(x,1))
Furthermore, we restrict the final output dimension be dp L. Since all matrices have inte- ger elements, initial vectors are integer vectors by initialisation function I(-) (Section 2.2 ) and mar((,min(zz.1) will map all integers to 0/1, it's easy see that the output of this kind of model is always 0/1, which can be directly used as the classification result. We call such model 0/1-GNN. model instance can be represented by {C(s) (CA), , B60) Ti=t where K
P2
Lemma 19. Regard 0/1-GNN as node classifier, then the set of node classifiers represented by 0/1-GNN is closed under A, ,-
Proof. Given two 0/1-GNN A1,A2, it suffices show that we can construct -A, and A1 A A2 in 0/1-GNN framework. That's because construction of A₁ V Aa can be reduced to constructions of A,7 by De Morgan's law, e.g., a V -(-0 -b).
Construct -A1. Append a new layer to A, with dimension d++1 = 1. For matrices and bias ((L+1), ((Lt)),(AALttt (A 1e(t)) b((+1) in layer L + set Cf,+1 -1 and 61+11
and
other parameters O. Then it follows x (I+1) maz(O,minn(x! (1) 1,1)). Since (1) is the 0/1
classification result outputted by Ai. It's easy to see that the above equation is exactly x (L+1) X
2. Construct Ai A2. Without loss of generality, can assume two models have same layer number L and same feature dimension de in each layer I E (1.......). Then, we can construct a new 0/1-GNN A. A has I. layers. For each of the first L. layers, say 1-th layer, it has feature } be parameters in layer of K R((), "o""""")) ) (K) RR("
dimension 2d, Let {c(") )
,,6') ,
A1 respectively. Parameters for layer of A are defined below
(C())
R (
b (
c -=
R
(6)
Initialization function of AA is concatenation of initial feature of An,AA. Then it's easy to see that the feature x after running first L layers of A is a two dimension vector, and the two dimensions contains values representing the classification results outputted by AI,,A respectively.
For the last layer L + it has only output dimension. just set C C
c++ 1.b
and all other parameters O. Then it's equivalent to x
(1+1) maaz xx,1
+ 2.2 1,1)) where
(L)
(L) (L)
x. x are output of Ai .A respectively. It's easy to see that the above equation is equivalent to
(L+1) (L) (L)
X X.. xx,2 the A constructed in this way is exactly Ai A A2
Definition 20. FOC, formula is defined inductively according to the following grammar:
A(z), P9 A P1 V 92, " (1(2(x))))) where A P1 and r Ps
15

---

Definition 21. For any subset S _ P2. let (s(2.y) denote the FOC₂ formula (Ares r(a.z)) A (NrePArs -=(x)))- Note that ps(x.y) means there a relation v between x and if and only if E S, so (x, can be seen a formula to restrict specific relation distribution between two nodes. RSFOC² is inductively defined uccording to the following grammar.
A(x), F1 A P2: P1 P12 1. 32% (s((x.)) A pi(()) where A E Pi and S P2
(8)
Next, we prove that FOC₂ and RSFOC, have the same expressiveness, namely, each FOC₂ node classifier can be rewritten in the form RSFOC2.
Lemma 22. FOC₂ RSFOC,
Proof. Comparing the definitions of RSFOC, and FOC,, is obvious that RSFOC, C FOC₂ trivially holds, so we only need to prove the other direction, namely, FOC₂ S RSFOC,. In particular, Boolean logical classifier only contains any one sreefrre-varriblle FOC₂ formula (Ix), we can construct an equivalent RSFOC, formula (x))..
free variable, we only need to prove that for
We prove Lemma 22 by induction over k where A is the quantifier depth of (xx)).
In the base case where i: = 0, (a(r) just the result of applying conjunction, disjunction or negation to bunch of unary predicates A(x), where A E P1. Given that the grammar of generating (p(x) is the same in RSFOC, and FOC₂ when k: 0, so the lemma holds for
For the indutive step, we assume that Lemma [2] holds for all RSFOC, formula with quantifier depth no more than m. next need consider the case when k + 1.
We can decompose (xx to be boolean combination of a bunch FOC₂ formulas yo (x)..... .N (x).
each of which is in the form (a)) A(x) where A E P1 or (x(xx) = 32ny(10 () (I.z)). See the following example for reference.
Example 23. Assume ((x) == (x) A Jy(ri (I,8))) (3y((2))) A (2(22,0) v)) (u((ra(.))) "I can be decomposed into boolean combination four subformulas shown as follows:
(x)) = Ax(x)
P2(x) = Ez(r)
Ps(z) = Ey (A2(v) A r2(2,3))
Pa(x) = =Ey(rs(z.))
We can see that grammars of FOC₂ and RSFOC, have a common part: A(x), 41 A42, P1 Vy2, 7P1 so we can only focus those subformulas (x(()) in the form of 3²" (x.z) In other words, if can rewrite these FOC₂ subformulas into another form satisfying the grammar of RSFOC,, we can naturally construct the desired RSFOC, formula (2x equivalent to FOC, formula (xx).
Without loss generality, in what follows, we consider the construction for ypx)) = " (x,))) Note that xzz) has quantifier depth more than + 1, and sp (1(x.)) has quantifier depth more than m.
We can decompose s' (x.y) into three sets of subformulas where N₂ and N₂ are two natural numbers, op" sp? are maximal subformulas whose free variable is assigned to and y, respectively. sp (x) is the combination of these sets of subformulas using A, V,
(x> (ra(n.v) Pal
Example 24. Assume that we have a FOC, formula in the form of of (x.y) = (r1(1.s) ^
Er(r2(xx))) (#)(3((rs(zw)) (Far
v By(r (3)( A kr2(2.)))
can be decomposed into the following subformulas:
(f(x)= = ()(3a(ra(x.))) v (y(rr(a,))
(z(x)) = [y(A2( A Az(x))));
()(()) = Bx((r(zzy)):
(1,,))
16

---

Assume that N = f1...., Na we construct a RSFOC, formula (7(()) == (Avr Po (z)) A (NENTT (x)), where 7 S N. It is called the x-specification formula, which means (x) is
true iff the following condition holds: for all i E T, of (x) is true and for all E N \ T. oo (r) is false.
By decomposing (a..) into three subformula sets, we know Boolean value of (z,y) can be 1/'al ( Now for any two specific subsets S S P2.7 T C N, we assume şe (z.y) and (7) are all true (Recall the definition of sss (2.y) in Definition 21 Then Boolean values for formulas {of I. ( (r.(() Pal are determined and Boolean value of ('(,))) depends only on Boolean values of [+p] (w))=
decided by Boolean values of these formulas (1] (-) (pp
(y) rim1s (r((x.)))
No Therefore,
j=
we can write a new FOC₂ formula ('s which is boolean combination of (+²(y) No (y) This formula should satisfy the following condition: For any graph G and two nodes a.b on the following holds,
(s((,b) (p)(a)) + (f'(a..) P2,r(())
By our inductive assumption, of ('(xy)) has quantifier depth which is more than m, so {op 1= ( also have quantifier depths no more than m. Therefore, each of them has RSFOC, corresoondence. Furthermore, since A, V V,- are allowed operation in RSFOC,, (f((x) (x) and (v) can also be rewritten as RSFOC2 formulas.
Given that (x.y)) and (y) specify the boolean values for all {op (y)) (x..))) formulas, so we can enumerate all possibilities over S C P2 and T' N. Obviously for any graph G and node pair (a,b), there exists an unique (S,T) pair such that (ps(a,b) A (F(() holds.
Hence, combining Equation (9, 4' p'(zzy) is true only when there exists a (S,T)) pair such that (2.y)))) A (x) (1))(()) true. Formally, we can rewrite ol (x,g) as following form:
('(x)) = V
(ps(x.)) (x) (v)
(10)
SEPAICN
In order to simplify the formula above, let (x) denote the following formula:
(T(z,)) = V
(s((x.)) A (3),T()))
(11)
SCP:
Then we can simplify Equation 10 to the following form:
('(x)))
V
(
(12)
TCN
Recall that (p(x) = y (z.y)). ) so it can be rewritten as:
(xx) = 32""
( TCN
(13)
Since for any graph G and its node there exists exactly one T such that (a)(a) is true. Therefore, Equation (13) can be rewritten as the following formula:
xxx) = V (7(2) ( "
(14)
TCN
Let (x( = 32"y(dr(z.))) Since A,V are both allowed in RSFOC, If want to rewrite (xx) in the RSFOC2 form, it suffices to rewrite (T(x) as RSFOC, formula, which is shown as follows,
(r(x)= = 322 ((((((()))))))) = 32²,
V (ps(a.)) A A v12r(w) SCP,
(15)
Similar to the previous argument, since for any graph G and of of its node pairs (a,b), the relation- specification formula yps (x.y) restricts exactly which types of relations exists between (a,b), there exactly one subset S C P2 such that (s(bb)) holds.
17

---

Therefore, for all S _ P2. we can define ns as the number of nodes such that (2( A P's (v) holds. Since for two different subsets S P2 and a fixed y, ips, (z) and ys, (z,y) can't hold simultaneously, the number of nodes y that satisfies yss (z(z) A ('s is exactly the sum Esgp, ns. Therefore, in order to express Equation [T]) which means there exists at least n nodes y such that Vser, (1,(( A (s,)(()) holds, it suffices to enumerate all possible values for {ns]S C P2) that satisfies (Escp, ns) n, r2s E N. Formally, we can rewrite (r(xx) follows:
pr(z)=
V (Egnn ns)=n SCP
(A
22ns y(ps(a.)) A (3,
(16)
Note that 32 32=5(((s(z.)) APSS (v)) (v)) satisfies the grammar of RSFOC2, so Pr (z) can be rewritten
as RSFOC,, Then, since (x) can also be rewritten as RSFOC, by induction, combining Equation (4) and Equation 115 (xx) is in RSFOC2. We finish the proof.
B Proof of Proposition 3
Proposition
3 FOC₂ & R2-GNN and RR-GNN & FOC₂ on some universal graph class Gu.
Proof. First, we prove FOC₂ & R2-GGNN.
Consider the two graphs G2 in Figure (G),)) can be distinguished by the FOC₂ formula (px)
321y(m (2r.y) A p2(x.y)). However, will prove that any R²-GNN can't distinguish any node in G1 from any node in G2.
Let's prove it by induction over the layer number L of -NNN. That's to say, we want to show that for any L 2 0, RC-GNN with no more than L layers can't distinguish any node of G₁ from that of G2.
For the base case where 0. since each node feature vector initialized by the unary predicate information, so the result trivially holds.
Assume any R2-GNN with no more than L = layers can't ' distinguish nodes of G₁ from nodes of G2. Then we want to prove the result for L. = m + 1.
For any R2-GNN model A with m + 1 layers, let AA' denote its first m layers, we know outputs of A on any node from G1 or G2 are the same, suppose the common output feature is x(m).
Recall the updating rule of R--GNN in Equation ( We know the output of A on any node in G1 or G2 is defined as follows.
(m+1) = ((m+1) ((()) (A(m+ ( ((x(m) (1x))()) B)) (I)+))(((mm)) B)) (((m+1)((x())
XB. (m)
((m) (m)
x
}})
(17)
Here C(m+1), A (m A. fm++1) p(m+1) are parameters in the layer m + 1 of A, un (u) (2(()) (v) is the
only 71 r1-pet neighbor of u, and a,b,c,d are nodes from the corresponding graph G1 or G2. From Figure Twe we can see they are well defined.
By induction, since any node pairs from Gi and G2 can't be distinguished by A', we have
xb (mm) ,x (m) (m) ((m) (mm) .x .x (m) are all the same feature (m), Therefore, Equation 17
( wa())
have the same expression for all nodes v from G1 and G2, which implies any A with m + 1 layers can't 't distinguish nodes from G1 and G2-
Next, we then prove RN-GNNs & FOC₂.
Assume we want to construct classifier e which classifies a node into true iff the node has a larger number of r1 ri-typ neighbors than that r2-type neighbors.
First, we prove that we can construct an 0/1-GNN A to capture c. It only has one layer with parameters ((1) (()) " _R and feature dimension do = di 1. We assume that each node has the same initial feature vector, i.c., 1. We set (1) L(111) = (14
2,(1,1) = -1, where (1) 1,(1,1) denotes the only element in 1(2) placed in the first row and first column (similar for 2.(..)) and all other
18

---

2n + 1 type neighbors
2n ri-type neighbors
3
2n 2
2
2n +
G(n):
H(n)
2n +
2n +
4n 2
2n +
2n + 4
4n +
2n r2-type neighbors
2n r2-type neighbors
Figure 5: ((n) and (n).
parameters 0. It's easy to see that A equivalent to our desired classifier e on any graph since we have x, (1)
(1, EueNo,
EveNe.zte) 1)).
Next, we show FOC₂ can't capture on G.. In order to show that, for any natural number n, we can construct two single-edge graphs G(n), (n) as follows:
V(G(m)) V(H(n)) 4n
E(G(n)) = (ri(1,0)VVi E [2,2n + 2]} U (r2(1.0) E [2n + + 2 (n))))) (r.(1,) [2.2m + 1]} U (r2(1.0) [2n + 2|]
We prove the result by contradiction. Assume there is FOC₂ classifier &p that captures the classifier c, then it has to classify (G( as true and (H).). as false for all natural number n. However, in the following will show that it's impossible, which proves the non-existence of such y.
Suppose threshold numbers used on counting quantifiers of yp don't exceed m, then we only need to prove that &p can't distinguish
(H()) which contradicts our assumption.
For simplicity,
G. H. to denote ((m), H (m). In order prove the above argument. First, define a classiiassiiiattion function CLS((-) as follows. It has G or H as subscript and a node of G or Il as input.
1. CLSa (1) = 1. It means the function returns 1 when the input is the center of or H.
2. CLS = CLSH(22) 2, Vu [2.2m + 21,Ve, E [2,2m 1). which means the function returns 2 when the input is r1 r1-neighbor of center.
3. (L) (LSn = 3, Vvn [2m + 3,4m + 20, [2m + 2,4m + 2], which means the function returns 3 when the input a reinhig of center.
Claim 1: Given any 41 V(G), 02 V(H), if (ITSS
(CI.SH CT,
then any FOC₂ formula with threshold numbers no larger than m can't. distinguish (u1,v1) and (22.
(12)), (1)))))))
This claim is enough for our result. We will prove that for any constant d and any FOC₂ formula é with threshold numbers no larger than m and quantifier depth d, o can't distinguish (u1,0) and (22 given that (
(CLSH CLSH (v2))
The result trivially holds for the base case where d = 0. Now let's assume the result holds for d < k can now prove the inductive
when d k 1.
Since -,(rg) trivially follows, we can only consider the case when s(x,)) is in the form 32N yo (I,w), < or 3 ( m. where o' (z.z) is FOC, formula with threshold
19

---

numbers no more than m and quantifier depth no more than k. Since these two forms are symmetrical, without loss of generality, we only consider the case N2t yo (a. N S m.
Let N1 denote the number of nodes v/ E (VG such that (G, ( ø' and N2 denote the number
of nodes 1/2 E (HH) such that (2)) 12)
= D' Let's compare values of N1 and N2. First, By induction, since we have CLSa(ui) = CLSH (u2) from precondition, so for any vf E ((G), oo e (II), which satisfies CLSa(u11
(1SH)(e), (x.x.)) can't distinguish (u, and (u2,02).
Second, isomorphism tells us o' can't distinguish node pairs from the same graph if they share the same CLS values. Combining these two facts, there has to be subset S {1,2,3}, such that
N1 = Eees (a) and N2 = Eaes NH where Na(a) denotes the number of nodes u on G such that (T) = a, (N (a) is defined similarly).
It's easy to see that Nc(1) (1) = 1, and (a( > for {2.3). Therefore, at least one of N1 = N2 and m < min (i) holds. In neither case 32N yo (x.g), & m can distuigush (11,v1) and (u2.02).
Note that in the above proof our graph class (G(m),,(n)) E N) is actually simple graph class, so we can actually get the following stronger argument. Corollary 24.1. R²-GNN & FOC₂ on some simple graph class.
C Proof of Theorem
Theorem 4 graph class.
FOC₂ R2-NNN on any simple graph class, and FOC₂ & R2-GNN on some simple
Proof. We just need to show FOC, C R2-GNN on any simple graph class, and the second part can it suffices show be just concluded from Corollary 24. By Lemma 22 FOC₂ RRSOOC,
RSFOC, S 0/1-GNN. By Lemma 19 0/1-GNN closed under A, V m, so we can only focus on formulas in RSFOC, of form (tx) equivalent 0/I-GNN A for all formulas of above form, then we can capture all formulas in RSFOC, since other generating rules A, V is closed under 0/1-GNN- In particular, for the setting of single- edge graph class, is meaningful only when |S] S 1. That's because |S| > 2 implies that yp is just the trivial 1 in any single-edge graph class Ge.
32m ((ps((a.)) A ('))),
P2. If we can construct an
Do induction over quantifier depth i of p(x).. In the base case where k = 0, the result trivially holds since in this situation, the only possible formulas that needs to consider are unary predicates A(x), where A E P1, which can be captured by the initial one-hot feature. Next, assume our result holds for all formulas with quantifier depth k no more than m, it suffices prove the result when quantifier depth of (0x) = 32" ((P)(()))) A (3)) is m + 1. follows that quantifier depth of yp (z) is no more than m.
By induction, there 0/1-GNN model A' such that = s' on single-edge graph class. To construct A, we only need to append another layer A'. This layer L + 1 has dimension 1, whose parameters (L++1), (,ottt((((()))))
(A(L+))) ) R(L+1) ((I++) are set as follows:
1. When S 1: Suppose S = (i), set T++ 3,(1,)
1,6 = =1 n. where A A++1
3,(1,1) denotes
the element on the first row and first column of matrix 1((+1) Other parameters in this
layer are 0. This construction represents x (L+1) = (onzr(00mii((eeett
x(1)
(n - 1).1)). Since xu is classification result outputted by A' which is equivalent to sp'
EveNa.(o) x!4 counts the number of j-type neighbor u that satisfies ('(u). Therefore
X (L+1) = 1 if and only if there exists at least j-type neighbors satisfying the condition p', which exactly what sp(x) means.
2. When |S| 0: Let K
1P2. for all j [K]. set A 44+1 11, 1 [((++1) 2,111)
1,b = 1 n and all other parameters 0. This construction represents x; (L+1)
moz(0.min((E.evic) x(1) (EK EneNa.(1) x(1) (n 1).1)). Since we only
20

---

consider single-edge graph, (uevia) x - E EueNo x exactly counts the number of nodes u that satisfies ('(y) (v) and doesn't 't have any relation with e. It's easy to see that X (1+1) iff there exists at least such nodes u, which is exactly what sp(x) means.
Hence, we finish the proof for Theorem f for each FOC₂ formula over the single-edge graph class, we can construct an R²-GNN to capture it.
D Proof of Theorem and Theorem 6
Theorem 5 R²-GNN C FOC₂ on any bounded graph class, and R2-GNN & FOC₂ on some
bounded graph class.
Theorem 6.
For any bounded graph class Go- Suppose any G E Gb has no more than N nodes, and Go has unary predicate P1 and relation (binary predicate) set Pz. Let mı == = |P == P22. then for any node classifier c, suppose can be represented as an R² R2-GNN with depth (layer number) L, then by Theorem there is FOC₂ classifier up equivalent to e. over Gr. Moreover, the followings hold:
1. The quantifier depth of &p is no more than L.
2. The size of yp (quantified by the number of nodes o's parse tree) is no more than 225(L), where
f(L) := =222(N+t)TL-- (0) = (2226m))tm)))
For Theorem we just need to show R2-GNN C FOC₂ on any bounded graph class. The second part can then be shown by the fact that the graph class [G1,Gg] } in Figure I ii a bounded graph class but FOC₂ I R2-GNN still holds, In the following proof, we also show how to get the complexity upper bound claimed in Theorem 6 If want prove R2-GNN C FOC₂, suffices to show that for any Rº-GNN A, there exists an equivalent FOC₂ formula on any bounded graph class Gn- It implies that for two graphs G2,G2 and their nodes a,b, if they are classified differently by A, there exists some FOC, formula yp that can distinguish them. Conversly, if a.b can't 't be distinguished by any FOC₂ formula. then they can't 't be distinguished by any R2-GNI as well.
Definition 25. For sel of classifiers V (um......mm. V-truth-table T is a 0/1 string of length m. T can be seen as a classifier, which classifies node v to be true if and only for any 1 < S m, the classification result of th on equals to T,, where T2 denotes the i-th bit of string T. We define T( == {0,1}mM } m as the set of all Y-truth-tables. We have that for any graph G and its node v, satisfies exactly one truth-table T.
Proposition 26. Let FOC2(n) denote the set of formulas of FOC₂ with quantifier depth no more than n. For any bounded graph class Go and n, only finitely many intrinsically different node classifiers on Gb can be represented by FOC2(n). Furthermore, define N N,m,nng m2 in Theorem 6 the number of intrinsically different FOC, (n) node classifiers on G6 and their parse tree sizes are all upper bounded by fn) as defined in Theorem
Proof. Suppose all graphs in Gb have no more than N constants, then for any natural number m > N, formulas of form 3 ((((,)) are always false. Therefore, it's sufficient only to consider FOC₂ logical classifiers with threshold numbers no more than N on Go.
There are only m, + m2 predicates, and each boolean combination of unary predicates using A, V , can be rewritten in the form of Disjunctive Normal Form (DNF) (Davey and Priestley (2002)) So there are only at most f0) = 22 maa) intrinsically different formulas in FOC₂ with quantifier depth 0. Note that 2(m, + m2) is the number of terms, 2m, +m2) is the number of different truth-table conjunctions these terms, and 22 mm)) is the number of different DNFs on these conjunctions. Each DNF has parse tree of size at most + 22 +m2) (1 + 2m, + 2m2) < 1000 2 mm2)
Therefore, define f(0)- 1000- gg2(m)+m2) = 0
we know the number of different FOC₂ formulas with quantifier depth and parse tree size of these formulas can both be upper bounded by f00).
21

---

By induction, suppose there are only f(k) intrinsically different (O)2(k) formulas on Go. and each meaningful ( 1) formula is generated by the following grammar
A P2 V P2, "2, (x.))) < N
(18)
where 91,422 are FOC2(k + 1) formulas and o' is FOC2(k) formulas.
Given that only the rule y (x,y)) can increase the quantifier depth from k to k: + 1, m S N,, and there are only f(k) intrinsically different s' (z.y) E (k) on Go by induc- tion. Therefore, there are only (2N + 2))(k) intrinsically different FfferrentFFCC( FOC, + 1) formulas of form 3 32"" (x: x0p' (I.y)) or in FO) on Gb. Moreover, their boolean combination using A, V-- can be always rewritten in the DNF form, So there also finitely many intrinsically different FOC2 (A + 1) logical classifiers on Go. Similarly, we can bound the number of differ- ent DNF by f(k + 1) which are mob-foruulas with smaller quantifier depth outermost symbol 3. 22(N+1))(()) is the number of different conjunctions on these building blocks, and f(k + 1) = 22 13500) is the number of different DNF' on these conjunctions. Parse tree size of each of these DNFs is at most f(k + 1). The LHS is from the inductive assumption that each FOC2 (k) formula has a equivalent representation within f(k) parse tree size. The inequality is because we know f(k) 2 1000. Thus, we can upper bound the number of
22 where 2(N (k) is the number of "building blocks"
1 + 22(++1)000 (1 + 2(NV + () + f(k))) S 22
intrinsically different FOC₂(k + 1) formulas on Go and their parse tree size both by f(k + 1). O
Lemma 27. For any two pairs (G1,01) and (G2, U2), where G1 and G2 two bounded graphs from Go and ii and 12 are two nodes in G1 and Gz, respectively. If all logical classifiers in FOC₂(L) can't 't distinguish U2 then any R2-GNN with layer no more than L can't distinguish them well.
Proof. By one-hot feature initialization function of R2-GNN, FOC2(0) can distinguish all different one-hot intial features, so the lemma trivially holds for the base case (L = 0).
For the inductive step, we suppose Lemma 27 holds for all L < k. then we can assume ei 02 can't be distinguished by FOC + 1). Let N = k
G1 and G2 are bounded graphs from Go. so FNC2(N) has finitely many intrinsically different classifiers according to Proposition 26 Let TT (t) denote the FVC
satisfied by v. According to Definition 25 we know that for any T E ((FOC,(N)) there exists a (N) classifier for such that for any node v on G, where i TT = T (G,,v) F pr.
Assume there is an RN- A that distinguish 01 with layer L k + Let Ā denote its first l layers. By update rule of R--GNN illustrated in Equation 2 output of A on node of graph G, (k+1) only dependent on the following three things: X
output of Á on v, x
multiset of outputs of Á on r-type neighbors of u for each r E Pg, fxl (2) u e.e. (a)(
multiset of outputs of À on all nodes in the graph, (x! (k) |u E (v)
By induction, since i1 22 can't be distinguished by FK),(k), they has same feature outputted by A.
Then there are two remaining possibilities.
E (o... * (T)u( E (12) for some binary predicate r. Therefore, there exists a FOC, tk)-ttttth-table T, such that v2 have differently many r- type neighbors that satisfies yor. Without loss of generality, suppose U1 have n A1,0g(m (n) < n2) such neighbors respectively. we can write a FOC2(k + 1) formula 32 (y)) that distinguishes in and U2, which contradicts the precondition that they can't 't be distinguished by FOC, (I: + 11 classifiers.
A
(TT (u)lu u E V(G.)) * (TTx(u))) truth-table T, such that G2 have differently many nodes that satisfies yrr Without loss of generality, suppose G2 have ng(1 < n2) such nodes respectively. we can write
V(G2)). Therefore, there exists (k)
22

---

a FFC (k + 1) formula 32rr))r(3) that distinguishes and 12, which contradicts the precondition that they can't be distinguished by 2OC, + 1) classifiers.
Since all possibilities contradicts the precondition that 01 can't be distinguished by FOC2(k: + 1), such A that distinguishes "1 doesn't exist.
We can now gather all of these to prove Theorem 5 and Theorem
Proof. For any R²-GNN A, suppose it has L layers. For any graph G Go and its node e, let (T) denote the FOC, (L-)((L)ttutthtabblle satisfied by v. For any T T(FOC2(L)) since G. is bounded graph class, using Proposition 26 there exists a (OC2(L) classifier yr such that for any node in graph G E Gb. (T) T + (G.u) F pr. Moreover, by Proposition 26 since T is truth table on at most (L) formulas, for can be written as a conjunction over fL) literals, which means for has parse tree size at most 1 + [(L)²² since by Proposition 26, every formula in FDC2(L) equivalent to some FOC₂ formula with parsee tree size at most (T....
By Lemma 27 If two nodes ,1 have same -LCC((L)-tuut-tabbl))) -truth--table (TT)( = TT (12)), they can't be distinguished by A. Let S denote the subset of ((FOC2 that satisfies A. By Propo- sition 26 and Definition 25 + == {ST( S} is finite set with |$| s 25(2), then disjunction of formulas in Φ (Vres PP) is a FOC₂ classifier that equals to A under bounded graph class Gb-
Furthermore, by the above upper bound of parse tree size of any yr. (Vres (Prs has parse tree size no more than 1 + 21(2 + S(L)²) < 22f(4), where the inequality is from S(L) 2 1000. We complete the proof.
E
Proof of Theorem 9
Theorem
9 R2-GNN C R2-GNN oF any universal graph class Gu.
Proof. Assume that we have a predicate set P = P K = P22| and let P = P U sprimol,auxi ]aur]) denote the predicate set after transformation F. For any R²-GNN A un- der P. we want to construct another Ra-GNN A'' under P', such that for any graph G under P and its node v, has the same feature outputted by A(G,v) and ((F((G),v) Let L denote the layer number of A.
We prove this theorem by induction over the number of layers L. In the base (L = 0), our result trivially holds since the one-hot initialization over P' contains all unary predicate information P. Now suppose the result holds for I. S k so it suffices prove it when T. + 1.
For the transformed graph F(G), primal(v) is true if and only if is the node in the original graph G. Without loss of generality, if we use one-hot feature initialization on P', we can always keep an additional dimension in the node feature vector x, to show whether primal(v) is true, its value is always 0/1, in the proof below when we use x to denote the feature vectors, we omit this special dimension for simplicity. But keep mind that this dimension always keeps so we can distinguish original nodes and added nodes.
By induction, let A denote the first A layers of A. and let A' denote the R²-GNN equivalent with Á on F' transformation such that Á = A' F. We will append three layers to A' to construct A' that is equivalent to A. Without loss of generality, we can assume all layers in A have same dimension length d. Suppose T'' is the layer number of A', so we will append layer L' + 1,L' + 2, + 3. for all I E (L' + 1,I' + 2,L' + 3}, Rr denote the parameters in (-th layer of A. Here, A--(0) : 2ia2 denotes the aggregation function corresponding to two new predicates auxl .aux2, added in transformation F, and (P.(l) (t.(() are different combination function that used for primal nodes and non- non-primal nodes. Note that with the help of the special dimension mentioned above, we can distinguish primal nodes and non-primal nodes. Therefore, It's safe to use different combination functions for these two kinds of nodes. Note that here since we add two predicates aux maxx, the Xaur2.Xg) where Xo is the feature vector of the former layer, and x,.1 1 S j < K denote the output of aggregation function
Recall that an R2-GNN defined by {C(,, (0.0)((A))) (AA)),
let (!)a.() _CP.()), C,,(),(A)) (A) "
input for combination function should be in the form CP C²(xx.(E (x,) ) 1
23

---

A7.0), Xour1 denote the output of aggregation function A A and Xg denotes the feature outputted by global readout function R², For aggregation function and global readout function, their inputs denoted by X, meaning multiset of feature vector. Note that all aggregation functions and readout functions won't 't change the feature dimension, only combination functions CP.l)) (aall) will transform d1-1 dimension features to d, dimension features.
D). layer L' +1: input dimension is d, output dimension is d' = kd. For feature vector with length d', let x0),1 E (1...., ., }} denote its i-th slice in dimension [ - 1)d + 1,id]. Let [xi..... Xml
denote concatenation of x Xm, and let [x]" denote concatenation of copies of x, 0" denote zero vectors of length n. parameters for this layer are defined below:
(o.(1'-1) (x):(x;)) Xaurl Xaur2, [xo:0 -a]
(19)
(x0
(x))
K j=l Nauel (aux2)Xg) [auul] K
(20)
(11+
Σx
(21)
XEX
Other parameters in this layer are set to functions that always output zero-vector.
We here that the layer L' 1 do the following thing:
For all primal nodes and its non-primal neighbor eab, pass concatenation of K copies of xa to Xeas and remains the feature of primal nodes unchanged.
2). layer T' 2, also has dimension d' Kd,, has following parameters.
Co.(E'22) (xo. ) Xaur1 Naur2.Xy) Xo
(22)
(all'42) (x), (a
Σ Xj
(23)
Vj E [1K], (144)) (X) 106-124 1)d
(1)
(24)
xEX
All other parameters in this layer are function that always outputs zero vectors. This layer do the following thing:
For all primal nodes, keep the feature unchanged, for all added node pair Cab, Switch their feature, but for all r E P2. if there is no r; relation between a,b, the i-th slice of Xe.. and Xem. will be set to
3). layer L' + 3, has dimension d, and following parameters.
Co.(L' (pll''-)(xx (x),(x)) (xxx )=1 Xxnr2,Xx)) xxunxXxx11x2xxX = ((L) (x) G) x-)
(25)
(x)(+(3) (X) (1((4) xxx Xo E (.rimal(()))) "4
(26)
(2(433
X [A (fx ( X X
(L) (fxx x X
(27)
Note that (LL) (1)) parameters in this layer are set to functions that always output zero vectors. We can see that this layer
(()),A(1)) .R(E) are all parameters in the last layer of A mentioned previously. All other
simulates the work of last layer of A as follows:
For all 1 ر K, use the j-th slice of feature vector x() to simulate A!4) and store results of aggregation function A/ this slice.
Global readout trivially emulates what R(L) does, but only reads features for primal nodes. It can be done since we always have a special dimension feature to say whether it's primal node.
We just simulate what (LL) does primal nodes. For 1 S j & K The type ry aggregation result (output of A()) used for input of ((L) is exactly j-th slice of return value of Auusl ((((433)
24

---

By construction above, A'' is a desired model that have the same output as A.
F
Proof of Theorem 10
Theorem
10 FOC₂ C RR-GNN oF any universal graph class Gu-
Proof. For any FOC, classifier under predicate set P, we want to construct 0/1-GNN AA on P' PU prrimll,auzl,an
equivalent to oo with graph transformation F.
Recall that FOC₂ = RSFOC, shown Lemma 22 and 0/1-GNNs S R2-GNNs, it suffices to prove that O F capture RSFOCc, By Lemma 19 since A, V - closed under 0/1-GNN suffices to show that when yo is in the form 32" (fs((.))) A 4' (v)) C P2. we can capture it.
We prove by induction over quantifier depth of y. Since O-depth formulas only about unary predicate that can be extracted from one-hot initial feature, our theorem trivially holds for m = Now, we assume it also holds for I k. it suffices to prove the case when k + 1. Then there are two possibilities:
1. When S * 0:
Consider the following logical classifier under P':
(2(x:) (A Aor(ory) ) (A -arr(z.))) rES
(28)
r$
(*)))) restricts that for any r E Pl, x has r-type neighbor if and only if r E S. Review the definition of transformation F, we know that for any added node eab. (F(G),eab) F Gs if and only formula defined in Definition 21 That is say for any r;,1 S K, there is relation ri between a.b if and only if S.
if (G,,,b) -= (a,bb)) where s (x.y) is the pllaiin-speciffcatte
Now consider the following formula:
の = 32"y auxx (x.y) A (5(()) A (2xx2(2(xx))) A (3y(aux/ A & ((())))))
(29)
For any graph G' and its node v. it's easy to see that (G,v) - x + (F(G),v) } G. Therefore we only need to capture & by 0/1-GNN on every primal node of transformed graphs By induction. since quantifier depth of ('(y) is no more than k. we know (0(()) is in 0/1-GNN. c is generated from (y(y) using rules A and By (r(.r))) A ('v)).. By Lemma 19 A is closed under 0/1-GNN. For By (r(((1.)) A sp (v)), we find that the construction needed is the same construction for single- element on single-edge graph class G, used Theorem Therefore, since we can manage these two rules, we can also finish the construction for C. which is equivalent to 4o on primal nodes of transformed graph.
2. When
First, consider the following two logical classifiers:
(xx) = (primal(x) A (
(30)
says node is primal, and satisfies vx(x). Since p((x) has quantifier depth no more than k and closed under 0/I-GNN, There 0/1-GNN Ai equivalent to @ on transformed graph. Then, consider the following formula.
((x)= = (ay(2xx((r ^ (Fr,aux/1 A ()()))
(31)
((x) evaluates on added nodes eat on transformed graph, eab satisfies it satisfies yp
Now for graph G and its node define as the number of nodes on F(G) that satisfies ş. and define ni as the number of aux/-type neighbors of on F(G) that satisfies S. Since spx))
32n (epo(( (x A o (v)) It's casy to see that (G,u) }= ip if and only if ny n2 2
25

---

Formally speaking, for a node set S, let |S] denote number of nodes in S, we define the following classifier such that for any graph G and its node a, ((F(G).a) + (G,a) F
((F(G),a)= = + Kolu E V(F(G)), (F(G),.) + Q NF (v), (F(G), F و 2
(32)
So how to construct model A to capture classifier c? First, by induction p.p are all formulas with quantifier depth no more than k so by previous argument there are 0/1-GNN models A..A that capture them respectively. Then we can use feature concatenation technic introduced in Equation ( to construct a model A based on A,A, such that Á has two-dimensional output, whose first and second dimensions have the same output as A,A respectively.
Then, suppose À has L layers, The only thing we need do is to append a new layer + to A. it has output dimension 1. parameters of it are {C(L+1) (A) (1(+))) " (1+1) (L+1) R(++1)} as defined in Equation ( The parameter settings are as follows:
(++1) R(4+1) 1,A (1,2) = -1,b(
n.. Other parameters are set 0, where A (L+1) (122
denotes the value in the first row and second column of A (I+1)
In this construction, have
x (L+1) m0x(0, Evev(F(G)) x
- -ueNNrio ouzi u,2 2
(L)
(n- 1))), which has exactly
the same output as classifier e defined above in Equation (32). Therefore, a desired model. O
G Proof of Theorem 11
Theorem
11 R²-GNN oF S. FOC₂ any bounded graph class Go-
Before we go into theorem itself, we first introduce Lemma[88 that will be used in following proof.
Lemma 28. Let sp(..y) denote FOC₂ formula with two free variables, for any natural number the following sentence can be captured by FOCz:
There exists no less than ordered node pairs (a.b) such that (G,a,b) F sp.
Let e denote the graph classifier such that c(G) iff G satisfies the sentence above.
Proof. The basic intuition is to define m,,1 < i < n as the number of nodes such that there are exactly nodes that ()) is true. Specially, we define m, as the number of nodes a, such that there are at least n nodes b that (a,bb) is frue. Since Σ im, exactly counts the number of valid ordered pairs when m. = and it guarantees the existence of least n valid ordered pairs when m. > O. It's not hard to see that for any graph G, c(G) 1 +> >n im; n. Futhermore, fix valid sequence (m1.....m,.) such that Σ im; 2 n, there has to be another sequence (k1.....k..) such that n & Σn= ik; S 2n and k; S my for all S < n. Therefore, We can enumerate all possibilities of valid (k)).....,,), and for each valid (k) sequence, we judge whether there are at least k; such nodes a for every 1 < iism n.
Formally, (x) == (1)))()))) can judge whether node has exactly partners such that sp(abb) = where ale y denotes "there are exactly such nodes y" which the abbreviation of formula (3= (-322)++)1)10)) (- (=ppttty(((()))))) The FOC, formula equivalent to our desired sentence e is as follows:
V
(A 32 [11 (((
322k x (3 (²")((((.)))
(33)
ER RSAN S2n
This FOC₂ formula equivalent to our desired classifier e.
With the Lemma
28 we now start to prove Theorem II
Proof. By Theorem it follows that R2-GNNs oF C FFC2 o F. Therefore suffices to show FOC₂ o F C FOC,.
26

---

By Lemma 22 it suffices to show RSFOC2 o F Ç FOC₂. Since A, V, are common rules. We only need show for any RS RSFOc, formula of form p(z) == 3²m ( (z.y)) (v)) under transformed predicate set P = P {aurl .aua2. primapr there exists an FOC₂ formula sp" such that for any graph G under and its node u, (G,r) F p + (F(G),)) = y.
In order to show this, we consider stronger result:
For any such formula y,, including the existence of valid ypt, we claim there also exists FOC₂ formula x² with two free variables such that the following holds: for any graph G under and its added node Cab F(G), (G,a,)) F x² + (F(G)),eb) = s. Call p'."" .p² as first/second discriminant of yp.
Now we need to prove the existence of sp and x2²
We prove by induction over quantifier depth m of ye, Since we only add single unary predicate primal in P any (xx) with quantifier depth 0 can be rewritten as (primal(x)) A t0 (x)) V (-primal(x)) A qp (z)), where yp (z)))) (x) are two formulas that only contain predicates in P. Therefore, s can be naturally seen as the first discriminant of p. Moreover, since (²(x) always evaluates on non-primal nodes, is equivalent to 1 or T under -primal(x) constraint. Therefore, the corresponding
or T can be seen as the second discriminant, so our theorem trivially holds for m = 0. Now assume it holds for m I k, we can assume quantifier depth of o 32 (((s((())))))
4 (v)) is m + 1.
Consider the construction rules of transformation F, for any two primal nodes in F(G), there is no relation between them, for primal node and an added node Cab, there is exactly single relation of type aux/ between them. For a pair of added nodes Cab there are a bunch of relations from the original graph G' and an additional aux2 relation between them. Therefore, it suffices only consider three possible kinds of S C P2 U {aux laux2] according to three cases mentiond above. Then, we will construct first/second determinants for each of these three cases. Since y (yy has quantifier depth no more than k, by induction let G' ,6² be first/second discriminants of yp by induction.
S. {aux1}:
for primal node a, p(aa means the following: there exists at least n nodes b, such that there is some relation between a on G and the added node eab on F(G) satisfies yp. Therefore, the first determinant of o can be defined as following:
(=) 32
(V r(z.w)) (opl)>n?Pu (2)() rEPs
(34)
for added nodes eab F(G), pleat) means satisfies x the second determinant of to is the following:
n (z.)) (x), n> (:.))))))) = 2.S [aux2) UTT PAT #
(35)
primal nodes don't have aux2 neighbors, so first determinant is trivially false.
4 (x) = 1
(36)
For added node Cab, Cub satisfies & iff there are exactly relations between a.b of types in T, and satisfies yp. Therefore the second determinant is as follows, where ypr (x..) is the relation- specification formula under P introduced in Definition 21
n= 1: (x,)) = (2(().)))))))))))))))))<>)) 6 (gzz), (x =
(37)
3. -0
For subset S P2 U [aur2, let (s(r))) denote the relation-speecffcattin formula under Pz U (aux1,aux:2) defined in Definition 21
Since consider on bounded graph class Go node number is bounded by natural number N. For any node a on F(G), let m denote the number of nodes on F(G) such that (b(b) = 1, let mg denote and there is a single relation auxl, between (a.b)
the number of nodes b on F(G) such that yp((b) on FGG), (That is equivalent to (anal) (a.b) = 1). For any T S P2, let my denote the number of nodes on F(G) such that (b(b) = and a.b has exactly relations of types in T U {aux22) on F(G). (That is equivalent to (PTU(au22) (a,b) 1).
27

---

Note that the number of nodes b on F(G) such that a.b don't have any relation, (That is equivalent to (Pa(a.b) 1) and ('b) 1 equals to m mo Σrgr my, Therefore, for any transformed graph F(G) and its node v, (F(G),v) + m - mo ETgr, mr 2 n. Since [V(G) - N for all G in bounded graph class Go. transformed graph F(G) has node number no more than N2. Therefore, we can enumerate all possibilities of m. I N2 C P2 such that the above inequality holds, and for each possibility, we judge whehter there exists exactly such number of nodes for each corresponding parameter. Formally speaking, y can be rewritten as the following form:
Pm,mo (x) = (31ml yy'(v)) ^ A( ((P(oue1)) (1.3) A xp (((1))))
(38)
(0x))
V
Pm,mo (c))(
A
a(mm (.(TTU (r)))
1-- Σrepy myr
TCP
(39)
where almly denotes there are exactly m nodes y.
Since first/second determinant can be constructed trivially under combination of A, V and
we' ve shown how to construct determinants for formulas of form 32 ( A yp (v)) when
S = {auz1} and S = {aau2) UT,T C P2 in the previous two cases. Therefore, in Equation (88
and Equation 39 the only left part is the formula of form (m)yppyy) The only remaining work is to show how to construct first/second determinants for formula in form (p(x) == yy"y'(
Let my denote the number of primal nodes that satisfies (v() and let m2 denote the number of non-primal nodes y that satisfies c'(y). It's not hard to see that for any node e on F(G), (P(G).)) F yp > mi + m2 2 n. Therefore, (((x) y2"'''(" (y) that evaluates on F(G) is equivalent to the following sentence that evaluates on G: "There exists two natural numbers m1, mig such that the following conditions hold: I. my + m2
2. There are at least my nodes b on G that satisfies "², (equivalent to (F(G),b) - 4 ). 3. There are at least m2 ordered node pairs a.b on G such that a.b has some relation and (G,a,b) } &², (equivalent to (F (F(G), Eab) F 4')."
Formally speaking. rewrite the sentence above as formula under P. we get the following construction for first/second determinants of 4p
G (z) = (z,)))
V (E y y ( Fm))
(40)
my tmggn
where Ping is the FOC₂ formula that expresses "There exists at least m2 ordered node pairs (a,b) such that (G,a.b) F (x..)) A (Vrer, r(x.u)"". We've shown the existence of Pmg in Lemma
H Proof of Theorem 15
Theorem
15
time-and-graph R2-TGNN OF -time-then-graph.
For a graph G with n nodes, let TVV E Raaxd denote node feature matrix, and HHE E Rnnxaxd denote edge feature matrix, where H.y denote the edge feature vector from i to j.
First we need to define the GNN used in their frameworks. Note that for the comparison fairness, we add the the global readout to the node feature update we do in RN-N.... It recursively calculates the feature vector H.)(()) (L))) of the node each layer S 1 & L as follows:
H 4. (HT
1)( D,
15 (())) 1 (HH) (HI E vB))
(41)
where (2) denotes the set of all nodes that adjacent to i, and (1) (g)())))() are learnable functions. Note that here the GNN framework is a little different from the general definition defined in Equa-
tion (2) However, this framework is hard to fully implement and many previous works implementing
lime-and- gruph or time-then- gruph Gao and Ribeiro 2022 (Li et al. 2019). Seo et al. (2016), Chen et al. (2018), Manessi et al. [2020), (ankar et al. 2018 Rossi et al. [2020b] don't 't reach the expressiveness of Equation (4p. This definition is more for the theoretical analysis. In contrast, our
28

---

definition for GNN in Equation TT) and Equation 22 is more practical since it is fully captured by bunch of commonly used models such as asSSchlichtkrul et (2018). For notation simplicity, for GNN A, let HVV(L)) A(H _ denote the node feature outputted by A using HH _H initial features.
Proposition 29. (Gao and Ribeimo ( sisiime-andgrrappl Ç &time-then-grapp
The above proposition is from Theorem Gf and Ribeiro 2022 Therefore, in order to complete the proof of Theorem 15, we only need to prove RT-IGNN of
time-then- -time-then-rraph.
Let G = {GI,..., Gr} denote a temporal knowledge graph, and A' E RTXIPI, E R IP, , 1ISIST denonte one-hot encoding feature of unary facts and binary facts on timestamp t, where Pi are unary and binary predicate sets.
The updating rule of time-then theg-hhhn- model can be generalized as follows:
Vi V. H. RNN (AA) ......AA)
(42)
Vi.j V, H RNN [ ()
(43)
X : A(HI _
(44)
where A a GNN defined above, RNN is an arbitrary Recurrent Neural Network. X E Rnd is the final node feature output of time-then graph.
First we need to prove time-then- graph R2-TGNNOP"" That is, for any time-then-graph model, we want to construct an equivalent R R-NNGNN A' to capture it on transformed graph. We can use nodes added after transformation to store the edge feature H and use primal nodes to store the node feature HV. By simulating RNN through choosing specific functions in RGNNN,, we can easily construct a R²-TGNN A' such that for any node i, and any node pair i, with at least one edge in history, x; = HÝ and Xz.; = H.,, hold, where x; and Xe;, are features of corresponding primal node i and added node eij outputted by A'.
Note that AA' is a R2-NGNN, it can be represented as Al......AAy where each 14,1 T R2-GNN. A'' has simulated work of RNN, so the remaining work is to simulate A(HV ,HH). We do the simulation over induction layer number L of A.
When L output of A exactly HV, which has been simulated by A' above.
Suppose L = 1o + 1, let À denote R² R-GGNN extracted from A but without the last layer k + 1. By induction,
construct R2-TGNN Á' that simulates Á(HV H)). Then need to append three layers to A' to simulate the last layer of A.
Let (L)) (0) (1.) denote parameters of the last layer of A. Using notations in Equation 2 let (I)
(C(), (C(),(A)) } are defined as follows:
( A :ur1: ou 12 denote parameters of the three layers appended A'r They
First, we can choose specific function in the first two added layers, such that the following holds:
1. For any added node Cij. feature outputted by the new model is x!? [H|,,x(x'/], where (2) denotes the feature outputted by the second added layer, and x/,x'j are node features of i.j outputted
by A'. For a feature x of added node of this form, we define xo.Xi X2 as corresponding feature slices where IHI,, x(,xx, have been stored.
2. For any primal node, its feature x only stores x² in x1, and Xo.X2 are all slices of dummy bits.
Let X be a multiset of features that represents function input. For the last added layer, we can choose specific functions as follows:
R(3) (X) == (10 E X.primal(x)) =g g(b) (x(xx)x2xx) x E XI) (Xauxl Xx) == u (Xaux1xX))
(45)
A (39 (X) =
(46)
(x3) ((3)
(47)
29

---

where Xauxl,X, are outputs of R(3) and A (3) and all useless inputs of ( are omitted. Comparing this construction with Equation (4T). It's cast to see that after the last layer appended, we can construct an equivalent R² R2-TGNN A' that captures A on transformed graph. By inductive argument, we prove time-then-graet graph _ R 2-TGNN oF"
Then we need to show R²-TGNN OFT C Çiime-ten-ggraph
In Theorem 16 we will prove R2-TGNN oF R2-GNN oF H. Its proof doesn't tt dependent on Theorem 15 so let's assume it's true for now. Then, instead of proving R²-TGNN oF ii''s sufficient to show RC-GNN oF H C tine--hen-graph.
Let Pf, P2f denote the set of temporalized unary and binary predicate sets defined in Definition I2 Based on most expressive ability of Recurrent Neural Networks shown in (Siegelmann and Sontag [1992]. wc can get a most expressive representation for unary and binary fact sequences through RNN. A most expressive RNN representation function is always injective, thus there exists a decoder function translating most-expressive representations back to raw sequences. Therefore, we are able to find appropriate RNN such that its output features H _H in Equation (42) Equation (43) contain all information needed to reconstruct all temporalized unary and binary facts related to the corresponding nodes.
For any R2-GNN A on transformed collpsed temporal knowledge graph, we want to construct an equivalent time-then-graph model (RN to capture A. In order to show the existence of the time-then- theeethh--grahhh model, we will do an inductive construction over layer number L of AA Here in order to build inductive argument, we will consider following stronger result and aim to prove it: In additional to the existence of A', we claim there also exists a function fA with the following property: For any two nodes a.b with at least one edge, fA(x' x² HI Xe.., where x² X,, are features of a, and edge information between a.b outputted by A', and X is the feature of added node cab outputted by A F a H. It suffices to show that there exists such function fA as well as time-then-grage graph model (RN such that the following conditions hold:
For any graph G and its node a.b E V(G),
1. H. [x., li E ()]
2.1f there is at least one edge between a,b in history, fa(El V.0 K.)) .HH mng.
Xeab Otherwise,
fa (HH (.)) . (1)) (H,))HH)))) 0
where (. MrI are node features outputted by A', while Xeas are node features outputted by A on transformed collpased graph. Ene(X) is some injective encoding that stores all information
of multiset X. For node feature (1) of above form, let (V)) == x., V.()) Enc( (l (Xeag Ii E M(a) B) denote two slices that store independent information in different positions.
For the base case L the node feature only depends on temporalized unary facts related the corresponding node. Since by RNN we can use most expressiveness representation to capture all unary facts. specific RNN already captures A when L = 0. Moreover, there is added node eab that relates to any unary fact, so a constant function already satisfies the condition of fA when L = 0. Therefore, our result holds for L
Assume L = k + 1. let A denote the model generated by the first & layers of A. By induction, there is time-then- gruph model A' and function fā. that captures output of A' on transformed collapsed graph.
We can append a layer to Å' to build A'' that simulates A. Let (C(4),(A)))) (b) j=1
TiPs _A( A (L) (
denote the building blocks of layer L of A, and let u u".g"," .r" denote functions used in the layer that will be appended to A' They are defined below:
g" (1l (IH) (1-11) .IA - H&Li e N(O)))) ( ( (H. (L-)) . VH HHMH E B()
(48)
r' (QU (- (EV()))) = R Q11 ( DEVGGUU U Deo(II)
(49)
JEV(G)
u" (x,,,x)) = ((L)) (x,,x,)
(50)
where X, are outputs of g" and r* Dec(X) is a decoder function that do inverse mapping of Enc(X) X) mentioned above, so Dec(H))) v((-1)) is actually {xee, li E (a) Note that primal nodes
30

---

in transformed graph only has type auxl- neighbors, so two inputs Xr, one for aux aggregation output and one for global readout are already enough for computing the value. Comparing the three rules above with Equation ( we can see that our new model A'' perfectly captures A.
We've captured A, and the remaining work is to construct SA defined ahove complete inductive assumption. We can just choose function that simulates message passing between pairs of added nodes cab and eba as well as message passing between eat and a, and that function satisfies the condition for fA. Formally speaking, fA can be defined below:
VOO H == Sim Ar (H) (11-1 H(-1) Iis 9jt Hi)) fA (1) Hy
(51)
Pig = fx (H) 1(--1) my V.(-11 my -n-1) = qm uu 1/
V(G)
(52)
Let's explain this equation, Sim A. (a.g.s,b,, e,e) is a local simulation function which simulates single- iteration message passing in the following scenario:
Suppose there is graph H with three constants V(H) (ba There is aux/ edge between a and Cab. an aux2 edge between eab and Cba. and additional edges of different types between eab and Cba- The description of additional edges can be founded in e. Initial node features of ab are set to a,s, respectively. and the global readout output is Finally, run L-th layer of A on H, and Ai AL is node feature of eab outputted by Ar.
Note that we use appropriate injective encoding or just use concatenation technic, H HV . can be accessed from HH!110) , (3) Therefore the above definition for fA is well-defined. Moreover, in the above explanation we can see that [A _ (1(11) ,H is exactly node feature of eij outputted by A on the transformed collapsed graph, so our proof finishes.
I Proof of Theorem 16
Theorem 16. Ra-TGNN oF R2-TGNN oF H.
First, we recall the definition for R2-TGNN in Equation 53)
x Ao (Couy*
where
ye = (o),(0) VI V(G))
(53)
We say a -TGNNN is homogeneous if A1,... Ar share the same parameters. In particular, we first prove Lemma 30 namely, homogeneous R²-TGNN and R²-TGNN (where paramters A......e Ar may differ) have the same expressiveness.
Lemma 30. homogenous R²-TGNN R2-TGNN
Proof. The forward direction homogeneows R2-TGNNG R²-TGNN trivially holds. It suffices to prove the backward direction.
Let A: {Ar)T denote a R²-TGNN. Without loss of generality, we can assume all models in each timestamps have the same layer number L. Then for each 1 < < T, we can assume all Ar can be represented by (c,)) (A.) j= r² ) Futhormore, without loss of generality, we can assume all (
output dimensions for A.... R2!") and c.(¹) are d. As for input dimension, all of these functions also have input dimension d for 2 < L S L. Specially, by updating rules of RG-TGNN Equation (53), in the initialization stage of each timestamp we have to concat a feature with length PPl to output of the former timestamp, so the input dimension for A()) RR(T)) c(l)) is d P//-
We can construct an equivalent homogeneous R2-TGNN with layers represented by (C*(), (A7 )= ( For 2 < 1 < L. C*(()))) A7,00) _R=(0 use output and input feature dimension d' Td. Similar to the discussion about feature dimension above, since need to concat the unary predicates information before each timestamp, for layer I 1, (+,()) AA (x(()_Ra.0)) (R)(()) have input dimension d' + |P| and output dimension d'. For dimension alignment, x used in Equation 53 is defined zero-vector with length d'.
31

---

Next let's define some symbols for notation simplicity. For a feature vector x, let x xiijj] denotes the slice of in dimension [i.j]. By the discussion above, in the following construction process we will only need feature x with dimension d' or d' + |Pal. When x has dimension d', x()) denotes xdd 1,id], otherwise it denotes x1| + (i 1)d + 1, + id] Let [xr or [x
denotes the concatenation of sequence of feature Xy. and [x]" denote concatenation of copies of x. 0" denotes zero vectors of length n. Furthermore. Let X denotes a multiset of x. Follows
the updating rules defined in Equation 2 for all 1 J S [1 S S L,A, (1++00)) should get input of form X. and the combination function C-+(1)) should get input of form [x, xxg)
where Xy is from the node itself, (x are from aggregation functions (47 ) and x, is
from the global readout R*()), The dimension of x or X should match the input dimension of
corresponding function. For all 1 S L,, parameters layer / for the new model are defined below
1= 1: 1=100 -
1P-] x2) =- 10 ([xo 1,xx (x) (x.,
1,,x 10 1
(54)
2
||3 = (c
11) )
(55)
Vj [ A7 (X) = - (4
|| E (
(56)
1= 1=1: [[x] E
X
(57)
VjE | 47 (x) = [4
x X
(58)
2 L: R (X) = [ ( (fxx x E X
(59)
The core trick is to use T disjoint slices xx.......xx77) to simulate T different models Ar at the same time, Since these slices are isolated from each other, a proper construction above can be found. The only speciality is that in layer 1 = 1, we have to incorporate the unary predicate information [[I,|Pi]] into each slice. By the construction above, we can see that for any node v, x! is exactly the its feature outputted by A. Therefore, we finally construct an homogeneous R²-TGNN equivalent with A.
(T)
(7')
Now, we start to prove Theorem
16
Theorem 16. R²-TGNNs - F -GNNs oF o H on any universal graph class Gu-
Proof. Since R2-TGNN oF only uses a part of predicates of P' =FH(())))) in each timestamp, the forward direction R² R2-TGNN oFT Ç RNN oF o H trivially holds.
For any R2-GNN A under P', want to construct an R2-TGNN A'' under FT(P) such that for any
temporal knowledge graph G, A'' outputs the same feature vectors as A on F (G). We can assume
A is represented as (C()) ((44)) (( A ausz: (() R where K P2/
First, by setting feature dimension to be d' TIP| [|P|+3. 3. We can construct an R--TGNN A' whose output feature stores all facts in (GH( for any graph G. Formally speaking, A' should satisfy the following condition:
For any primal node a, its feature outputted by A' o FT should store all unary facts of form A, T)P: primal(a) on ((H(G)). For any non-primal node cab, its feature outputted by A' FT should store all binary facts of form r,(a,b),r, E P2 or Taual (aur)) (b where b is another node on F (G)).
The A' easy to construct since we have enough dimension size to store different predicates independently, and these facts are completely encoded into the initial features of corresponding timestamp. Let (A(.....AAA)) denote A'.
Next, in order to simulate A, we need to append some layers to Ar. Let L denote the layer number of A, we need to append L layers represented as (C-,()) ((A, (1){1) /=1 - A"."".." (z)(
Since have enough information encoded in features, we can start to simulate A. Since neighbor distribution of primal nodes don't change between E (G)r and (G),, it's easy to simulate all
messages passed to primal nodes destinations by A A*((0) For messages passed to non-primal node
32

---

R2-TGNN
R2-GNNoH
C
R2-GNNoF H
R²-TGNN oF
tmee-then-gres
time-and-graph
Figure Hierarchic expressiveness.
Cab as destination, can be divided into messages from a and messages from Oba- The first class of messages is easy to simulate since the aurl edge between Cab and is the same F" (G)r and F(H(G))
For the second class of messages, since edges of type r;,1 < S P2l may be lost in F (G)T, we have to simulate these messages only by the unchanged edge of type aux2. can be realized by
following construction:
12 L,A L,A auar X) [[A),0 (X))
awa (X)
(60)
where P2l. A (x) = 1 (X) if and only if bba has neighbor r, on F(H(G)) otherwise (1) (X) == 0. Note that X is exactly the feature of Cba and we can access the information about its ry neighbors from feature since has stored information about these facts.
In conclusion, we' ve simulated all messages between neighbors. Furthermore, since node sets on FT FG) and (G)) are the same, global readout ((!) also easy to simulate by R*,(9) Finally, using the original combination function C(),, we can construct an R2-TGNN on FT equivalent to A on (G)) for any temporal knowledge graph G.
Proof of Theorem 17
Based on Theorem 15 Theorem 16 and Corollary 11.2 in order to prove Theorem 17 it suffices to show the following theorems.
Theorem 31. If time range T > 1 R² TGNN Ç. RR-GNN oH.
Theorem 32. If time range > 1 R2-TGNN & time-and-grann
Proof. Since formal proof Theorem 32 relates to too many details in definition of time-and- graph (Please refer to Gao and Ribeiro [022]] which is not the focus here. We will just brief proof sketch of Theorem 32] That's because time-and-graph can not capture a chain of information that continuously scattered in time intervals. Specifically, (p(x) 3 (rf(2.y) (3 (w.)))
can't 't' be captured by aone-and-graple but (p(x) is R²-TGNN.
We mainly give detaild proof of Theorem 31 Since in each timestamp t, R- RR-TGNN only uses a part
of predicates in temporalized predicate set Pr (P),, R² R--NGNN C R2-GNN OH trivially holds. To show R--NGNN is strictly weaker than R RNN oH. Consider the following classifier:
Let time range T 2, and let be binary predicate in Pz. Note that there predicates y 2 in p' = H(P). Consider the following temporal graph G with nodes (1,2,3,4,5). its two snapshots G2 as follows:
different
G = (445))
G2 = (r(33))
It follows that after transformation H, the static version of G is:
H(G) (4.))
Consider the logical classifier Fy rı (x..) A (Zor2(1)2)) under P' can be captured by some R2-GNN under P', Therefore, RN-GNN oH can distinguish nodes 1,4.
33

---

datasets
622
93
Avg # Nodes
477
477
477
477
Time range
2
2
10
# Unary predicate
2
2
# Binary wttpliiccccooo-empraailall
1
1
1
3
Avg Degree (in single timestamp)
3
3
Avg # positive percentage
50.7
52
25.3
73.3
Table 4: statistical information for synthetic datasets.
datasets
AIFB
MUTAG
Brain 10
Nodes
8285
23644
5000
Time Time_Range
# Relation types
45
23
20
# Edges
29043
74227
1761414
# Classes
2
10
# Train Nodes
140
272
4500
Test Nodes
36
68
500
Table 5: statistical information for Real datasets.
hyper-parameter
range
learning rate
0.01
combination
mean/max/ade
aggregation/readout layer
mean/max/add
1,2,3
hidden dimension
10,64,100
Table 6: Hyper-parameters.
However, any R2-TGNN based updating rules in Equation so R2-TGNN strictly weaker than R²-GNN oH.
53) can't distinguish these two nodes,
we can consider logical classifier ys == ((p A (z Note that this classifier is just renaming version of Figure 1 Therefore you can't anntt be captured by R²- RNNGNN eH, not to say weaker framework R2-GNN by Theorem 31
Based on Theorem 31
K
Experiment Supplementary
K.1 Synthetic dataset generation
For each synthetic datasets, generate 7000 graphs tranining and 500 graphs test set. Each graph has 50 1000 nodes. In graph generation, we fix the expected edge density 6. In order to generate graph with nodes, pick ön pairs of distinct nodes uniformly randomly. For each selected node pair a,b, each timestamp and each binary relation type r, we add r (a(bb) and ((,b)) into the graph with independent probability
K.2 Statistical Information for Datasets
We list the information for synthetic dataset in Table 4 and real-world dataset in Table 5 Note that synthetic datasets contains many graphs, but real-world datasets only contains single graph. Therefore, for real-world dataset, we have two disjoint node set as train split and test split for training and testing respectively. In training, the model can see the subgraph induced by train split and unlabelled nodes, testing, the model can see the whole graph but only evaluate the performance on test split.
34

---

FOC₂ classifier
492
(P3
AP4
R-GAT tH
100
61.4
88.6
82.0
R²-GAT oH
100
93.5
95.0
82.2
R²-GAT of o H
100
98.2
100
95.8
Table 7: Extra results synthetic datasets
AIFB
MUTAG
DGS
AM
nodes
8285
23644
333845
1666764
of edges
29043
74227
916199
5988321
R-GCN
95.8
73.2
83.1
89.3
R-GAT
96.9
74.4
86.9
90.0
R-GNN
91.7
76.5
81.2
89.5
RR-GNN
91.7
85.3
85.5
89.9
GNNGNN oF
97.2
88.2
88.0
91.4
Table Extra results for statie real-world datasets.
Models
GRU-GCNoF"
TGN oF
R-TGNN
R-TGNN oF
R2-TGNN 94.8
R-
Brain- 10
95.0
94.2
85.0
90.9
94.0
Table 9; Extra results for temporal real-world dataset Brain- 10.
K.3
Hyper-parameters
For all experiments, we did grid search according Table
K.4 More Results
Apart from those presented main part, we have some extra experimental results here:
1. Extra results on synthetic datasets but using different base model architecture, where R-GAT refers to Busbridge et al. (2019) and R refers to its extension with global readout. Please Refer to Table 7 These results show the generality of our results on different base models within the framework.
2. Extra results for static real-world datasets. Add base model R-GA R-GAI Busbridge et al. (201 and two larger real-world datasets DGS and AM from Schlichtkrull al. [2018). Please refer Table g From the results for two bigger datasets DGM and AM, we can see our framework outperforms the other baselines, which confirms the scalability of our method and theoretical results. These results show our method is effective both on small and large graphs.
3. Extra results for temporal real-world dataset Brain-10. 10. Please refer Table 9 These results implies that our method is effective on different base models in temporal settings. Moreover, we can separate improvements from global readout and graph transformation respectively. As said in the main part, the drop in the last column may be due to the intrinsic drawbacks current real-world datasets. Many real-world datasets non-logical property may lead to less convincing experimental results. As Barceló et al. (2020) commented, these commonly used benchmarks are inadequate for testing advanced GNN variants.
not be perfectly modeled as first-order-loicc classifier. This
35


Reviews:
[{"review_id": "eEuLGHp6p6", "reviewer": "Reviewer_auoR", "summary": "This paper proposes the R^2-GNN that captures the logic features in the graph. The proposed methodology largely resembles the previous work of ACR-GNN, where a GNN variant is proposed to capture the logic feature for graphs with no relation types. The proposed R^2-GNN extends the previous method by considering the graphs that involve a set of unary and binary predicates and potentially temporal information. To do so, the authors apply the same readout function to the base R-GNN model and show that it can capture the full logic classifiers with an additional graph transformation F.  Also an temporal variant R^2-TGNN is proposed to handle the temporal graphs.", "questions": "See above", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The paper is overall easy to read, however, I didn't check all the proof in detail.", "weaknesses": "## Novelty\n\nAs mentioned in summary, the authors follow the same method in ACR-GNN in modifying R-GNN into R^2-GNN to enable the model to capture the FOC_2 logic family. It seems to me the main methodological differences are the additional graph transformation F and the discussion on temporal graphs. \n- The former helps the model to distinguish nodes with different relations, while it seems to work empirically, it is more or less an incremental modification to the framework. \n- For the temporal graphs, the author propose to \"temporalize\" the graph by mapping the graph snapshots into one single static graph and process it with a slightly modified model, namely R^2-TGNN.\n\nThat said, this paper is not very novel methodology-wise.\n\n\n## Quality\n\nThe definition of a multi-relational graph is more or less redundant and confusing: this is effectively the graph with both unary and binary predicates, and many existing KGs already contain facts of both these types. One can refer to it as a real-world graph or just an ordinary graph instead of as \"multi-relational\".\n\nSome model and design choices lack justification:\n- It is unclear why the authors pick the R-GNN as the base model, provided that: (1) most existing GNNs can handle graphs with different relations and (2) the proposed modifications such as readout function and transformation F and H are orthogonal to the choice of the model. The authors may want to consider evaluating their method on different base models empirically to better demonstrate the difference\n- It is also unclear why the task is limited to node classification only: this leads to a narrow choice of the benchmarks in the experiments (L329-L330) and leaves some popular datasets untested such as GDELT and ICEWS.\n\nI'm also concerned about the real-world datasets experiments. The authors show the R^2-(T)RGNN achieves better performance than other GNN variants. While empirically this does have some merits, it does not provide any insights into the proposed model. Since the model focuses on learning the latent FOC_2 classifiers. One should first inspect the datasets and see what are the learnable FOC_2 rules in there. And if the model performs better, the authors should take the opportunity and analyze if this indeed resulted from the extra capabilities introduced to the model.\n\n\n## Clarity\n\nThe paper is overall easy to read, however, I didn't check all the proof in detail.\n\n\n## Significance\n\n\nApart from the lack of novelty, this paper also seems to lack significance. The FOC_2 logic is a small subset of first-order logic. Being able to capture these classifiers leads to minor benefits to the GNN literature: it does not provide sufficient explanation of the GNN model, nor does it tackle the difficult logical reasoning problems on graphs such as multi-hop reasoning, induction, and so on. In the experiments, the model is tested on only synthetic and three real-world datasets, and with no comparison to the SOTA models, so the empirical significance is also unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer auoR for the positive feedback and insightful comments. Below, we would like to give detailed responses to each of your comments.\n\n> **Q1**: Why the authors pick the R-GNN as the base model. The authors should evaluate their method on different base models. \n\n**A1**: It is worth noting that R-GNN is not a specific model architecture; it is a framework that contains a bunch of different GNN architectures. In the paper, we just said it's generalized from R-GCN [1], but our real goal is to define a generalized framework as an abstraction of most Message-Passing GNNs (MPGNN). We feel sorry for not pointing this out explicitly and perfectly in the paper. In the definitions (line 112 and 118), the functions can be set as any functions you like, such as matrix multiplications or QKV-attentions. Most commonly used GNN such as R-GCN[1] and R-GAT[2] are captured (upper-bounded) within our R-GNN frameworks. Many other related works, such as [3], [4] and [5] also use intrinsically the same frameworks as our R-GNN if you read the definitions, so R-GNN is a kind of abstraction framework for MPGNN that has been approved widely and studied a lot in the community. Therefore, we think analyzing these frameworks leads to common results for many existing GNNs.\n\nWe've added a series of experiments that use R-GAT [2] as base model. The following results show the generality of our results on different base models within the framework. (Here, We'd like to **re-emphasize** that R-GAT is actually another specific architecture under R-GNN.)\n\n|  $FOC_2$ classifier  | $\\varphi_1$ | $\\varphi_2$ | $\\varphi_3$ | $\\varphi_4$ |\n| ------------------------------ | ----------- | ----------- | ----------- | ----------- |\n|R-GAT $\\circ H$|100|61.4|88.6|82.0|\n| R-GAT+readout $\\circ H$| 100| 93.5        | 95.0        | 82.2        | \n| R-GAT+readout $\\circ F\\circ H$ | **100**         | **98.2**        | **100**         | **95.8**  |\n\n> **Q2**: It is also unclear why the task is limited to node classification only \n\n**A2**: We consider it as a future work because we are are not sure whether these results can be generalized to other tasks such as link prediction.\n\n Take link prediction as an example. If one wishes to define logics for link prediction, the considered logical formulas have to contain two free variables rather than one in node classification. It may influence some of our theoretical results, but maybe we can use graph transformation to reduce the two-variable case to some one-variable case. We need further research to check whether it is true, and whether our results can be generalized.  \n\n> **Q3**: We focuses on learning the latent $FOC_2$ classifiers. One should first inspect the datasets and see what are the learnable $FOC_2$ rules in there.\n\n**A3**: Many real-world datasets may not be perfectly modeled as first-order-logic classifiers. Sometimes two isomorphic graphs (nodes) have different labels in the dataset. This negative fact about real-world datasets has also been observed and illustrated in [6] (Figure 6).\n\nEven if these datasets can be logically modeled, the challenge lies in extracting intricate latent logical rules from real-world datasets. This very challenge underscores the necessity of employing both synthetic and real-world datasets in our experimentation, as elaborated in this paper. Synthetic datasets serve to showcase enhanced logical expressiveness, whereas real-world datasets demonstrate the tangible performance enhancements stemming from this heightened expressiveness.\n\nConsidering the intricacy of the datasets, we hold reservations about the efficacy of existing logical extraction algorithms, such as those outlined in [7], for our specific objectives. Given the dataset's complexity, a pragmatic approach seems more viable. We envisage a dataset that not only originates from real-world contexts but also employs explicit logical classifiers. Regrettably, our search for such a benchmark dataset remains unfruitful.\n\n> **Q4**: Being able to capture $FOC_2$ leads to minor benefits to the GNN literature. the model is tested on only synthetic and three real-world datasets, and with no comparison to the SOTA models\n\n**A4**:  While $FOC_2$ is a weak fragment within the realm of first-order logic, our **impossibility result** as exemplified in Proposition 2 has shown that R$^2$-GNN, a rather powerful framework, remains **inadequate** in capturing the entirety of $FOC_2$. Consequently, the framework also falters in apprehending more intricate logical architectures such as multi-hop and induction, which inherently belong to the broader scope of first-order logic. This realization prompts us to emphasize the imperative of enhancing the logical expressiveness inherent to GNNs. Our goal is to empower them to encompass even the seemingly modest scope of $FOC_2$. A closer examination of the capabilities of MPGNNs reveals that $FOC_2$ is indeed more formidable than initially perceived.\n\nIn terms of comparison with SOTA, we have added comparison with R-GAT as above. We have to point out that we didn't compare with a few SOTA models, such as [8] because they are not permutation-equivariant and therefore inconsistent for classification tasks.  These non-equivariant GNNs won't be equivalent to any logical classifier, and talking about their logical expressivenesses is meaningless. (See [6] for more detail). \n\n[1]Modeling relational data with graph convolutional networks ESWC2018\n\n[2]Relational graph attention networks arXiv\n\n[3]The logical expressiveness of graph neural networks ICLR2020\n\n[4]A Theory of Link Prediction via Relational Weisfeiler-Leman arXiv\n\n[5]Logical Expressiveness of Graph Neural Network for Knowledge Graph Reasoning arXiv\n\n[6]On the equivalence between temporal and static equivariant graph representations ICML2022\n\n[7]Explainablegnn-based models over knowledge graphs ICLR2021\n\n[8]The surprising power of graph neural networks with random node initialization IJCAI2021"}, {"review_id": "1PZDg343Hr", "reviewer": "Reviewer_Hbfa", "summary": "This work calibrate the logic expressiveness of R2-GNNs as node classifiers on multi-relational graphs. Motivated by some negative results, authors boost R2-GNNs with a graph transformation, which enables R2-GNN to capture FOC2 formulas. They further extend expressiveness results and graph transformation to temporal settings and derive an expressiveness hierarchy of temporal GNNs.", "questions": "1. There is no scalability comparison between the proposed method and baselines. Please add it.", "limitations": "Limitation is not addressed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Clear theoretical results on static and temporal settings.\n\n2. Proposed transformation is straightforward and scalable.", "weaknesses": "1. Nearly no related work. There is no related work section. Only the closest related work is mentioned in introduction and some related works are missing. For example, besides [1], some works also analyze GNN's expressivity as boolean classifier. Weifeiler-Leman test have been connected to boolean graph classifier for a long time [2]. [3] also analyze boolean link classifier.\n\n2. The experiments are only conducted on small datasets. You can use larger DGS and AM in RGCN paper [4].\n\n\n[1] Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. ICLR, 2020\n\n[2] Jin-yi Cai, Martin Fürer, Neil Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989: 612-617.\n\n[3] Xingyue Huang, Miguel A. Romero Orth, Ismail Ilkan Ceylan, Pablo Barceló, A Theory of Link Prediction via Relational Weisfeiler-Leman. CoRR abs/2302.02209 (2023).\n\n[4] Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, Max Welling: Modeling Relational Data with Graph Convolutional Networks. ESWC 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer Hbfa for the recognition of our theoretical results on both static and temporal settings as well as our proposed novel transformation. Below, we would like to give detailed responses to each of your comments.\n___\n> **Q1**: There is no scalability comparison between the proposed method and baselines. Please add it. The experiments are only conducted on small datasets. You can use larger DGS and AM in RGCN paper.\n\n**A1**:  We have followed your advice and tested our method and baselines on larger datasets DGS and AM. The results on the two bigger datasets are as follows. From the results, we can see that R$^2$-GNN$\\circ F$  outperforms the other baselines, which confirms the scalability of our method.\n\n|              | AIFB | MUTAG | DGS  | AM   |\n| ------------------ | ---- | ----- | ---- | ---- |\n|# of nodes|8285|23644|333845|1666764|\n|# of edges|29043|74227|916199|5988321|\n| R-GNN              | 91.7 | 76.5  | 81.2 | 89.5 |\n| R$^2$-GNN          | 91.7 | 85.3  | 85.5 | 89.9 |\n| R$^2$-GNN$\\circ F$ | **97.2** | **88.2**  | **88.0** | **91.4** |\n| R-GCN              | 95.8 | 73.2  | 83.1 | 89.3 |\n| R-GAT              | 96.9 | 74.4  | 86.9 | 90.0 |\n\n\n> **Q2**: Nearly no related work. There is no related work section. Only the closest related work is mentioned in introduction and some related works are missing. For example, besides [1], some works also analyze GNN's expressivity as boolean classifier. Weifeiler-Leman test have been connected to boolean graph classifier for a long time [2]. [3] also analyze boolean link classifier.\n\n**A2**: We didn't have a separate section for related works in this preliminary version due to space constraints. It will be added in later version. Thanks for your proposal.\n\nIt might be worth noting that [2] focuses more on distinguishing ability, which means whether a logic segment can distinguish two graphs. It is slightly different from classification ability. Specifically, consider that we have a graph (node) property $A$, and a set of logical classifiers $B$ (such as $B=FOC_2$). Distinguishing ability of $B$ over $A$ just guarantees that for each graph (node) $G$ with $A$ and each graph (node) $H$ without $A$, there exists a formula $\\varphi_{G,H}\\in B$ such that $G$ and $H$ get different labels on $\\varphi_{G,H}$. However, Classification ability requires stronger expressiveness in the sense that classification ability of $B$ over $A$ means that there exists a **fixed** formula $\\varphi\\in B$, such that for every graph (node) $G$ with $A$ and every graph (node) $H$ without $A$, it satisfies $G\\models \\varphi, H\\models \\neg \\varphi$. This difference appears often in related theoretical analysis, and it has been implicitly and briefly mentioned in the introduction of this preliminary version.\n\n[1]The logical expressiveness of graph neural networks ICLR2020\n\n[2]An Optimal Lower Bound on the Number of Variables for Graph Identification FOCS1989\n\n[3]A Theory of Link Prediction via Relational Weisfeiler-Leman arXiv\n\n\n"}, {"review_id": "kjuNI3UYVt", "reviewer": "Reviewer_p5D8", "summary": "In this paper the authors provide a theoretical analysis of graph neural network (GNN) expressivity on multi-relational and temporal graphs. Specifically, they extend the multi-relational graph convolution network R-GCN to a class of architectures they call R-GNN, which allows for arbitrary aggregation (pooling neighbors with respect to a particular relation) and combination functions (pooling these aggregations with the node representation itself). They further extend this to a class of architectures they call R²-GNN, which adds a global \"readout\" function which aggregates the feature vectors of all nodes in the graph. They analyze the capability of R²-GNN to classify nodes and compare it to that of $\\mathcal{FOC}_2$, a restricted subset of first-order logic which only allows formulas with at most 2 variables but also allows counting quantifiers. They find that neither is a subset of the other, in particular R²-GNN is not able to distinguish whether two neighbors of a given node with different relations are, in fact, the same node. However by first augmenting the graph with a particular transformation $F$ they are able to overcome this restriction, and ultimately show that $R^2-GNNs \\circ F = \\mathcal{FOC}_2$ on any graph class with a bounded number of nodes.\n\nAll of this is then extended to temporal graphs, which can also be converted to a multi-relational graph (with a unique set of relations per time-step). A hierarchy of expressivity with respect to current temporal graph frameworks is presented. Finally, experimental results validating the theoretical expressivity on synthetic and real-world datasets are presented.", "questions": "1. What is the initialization used for the nodes in $V' \\setminus V$? To the best I can tell, they do not have any unary predicates, so they would seem to be initialized with a vector of all zeros.\n2. Not a question as much as a comment - the R²-GNN architecture is equivalent to the R-GNN architecture if we first augment the graph to have a new binary relation which forms a complete graph on all nodes. Given that the work already includes a graph augmentation step, an alternative presentation could potentially avoid the R²-GNN architecture altogether, and simply express the entire thing as R-GNN on an augmented graph. I'm not sure it is clearer to take this approach, but it might be worth noting.\n\nMost of the paper was very well written, but I did find the following typos (mostly in the intro):  \nL37: authors -> the authors  \nL45: authors -> the authors  \nL46: in -> in the  \nL47: edges in graphs -> edge in the graph  \nL48: of -> (delete)  \nL48: graph needs -> graphs need  \nL51: as -> as a  \nL57: be -> can be  \nL60: to -> to the  \nL60: Besides -> Moreover  \nL61: extensively -> extensively in  \nL69: in -> in the  \nL70: power -> the power  \nL71: such -> such a  \nL72: mutli -> multi  \nL91: to -> to denote  \nL96: node Boolean -> Boolean node  \nL111: vectorsx -> vectors x  \nL338: do somorphism -> perform an isomorphism\n\nA minor suggestion: move the sentence in lines 170-171 to around line 85, to motivate the definition of bounded and simple graph classes.", "limitations": "I did not see much discussion of the limitations of the proposed model. Some of the concerns outlined in the weaknesses section above are good candidates for this.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is, to the best of my knowledge, original, and theoretical results analyzing the expressivity of graph neural networks in the multi-relational setting are certainly of significant interest to the graph neural network community.\n\nThe work is of a high quality, and presented clearly. Despite the highly technical nature of the results, the authors do a good job in motivating their work and providing intuition for the proofs.", "weaknesses": "In general, a point of caution with any strongly theoretical work is whether it applies in practice. In this setting the largest concern comes from the graph transformations. It is not unusual for a graph transformation to extend capabilities in the way the authors have done. A classic example is to extend a method which works on undirected graphs to the setting of directed graphs by creating a new graph with twice as many nodes, one representing \"head\" and \"tail\" for each node, however this can make some relationships (eg. transitivity) very difficult to observe. In the author's setting, while the graph augmentation may afford the ability to prove theoretical expressivity results, one might be concerned that the resulting graph is augmented to the point that a GNN architecture may require greater depth to perform the same sort of tasks it did previously. Of course the authors have provided empirical evidence that this augmentation is not problematic in at least three graphs, which is quite reasonable to support their approach, however it is something to bear in mind.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer p5D8 for the recognition of our original and theoretical results analyzing the expressivity of graph neural networks in the multi-relational setting as well as their potential contribution to the graph neural network community. Below, we would like to give detailed responses to each of your comments.\n\n___\n> **Q1**: What is the initialization used for the nodes in $V' \\backslash V$. To the best I can tell, they do not have any unary predicates, so they would seem to be initialized with a vector of all zeros.\n\n**A1**: Yes, your understanding is right. These new nodes are just constructed as auxiliary \"bridges\", so they don't own any substantial properties themselves. Their node features become meaningful only after messages from primal nodes pass to them.\n\n___\n> **Q2**: In general, a point of caution with any strongly theoretical work is whether it applies in practice. In this setting, the largest concern comes from the graph transformations. It is not unusual for a graph transformation to extend capabilities in the way the authors have done. A classic example is to extend a method that works on undirected graphs to the setting of directed graphs by creating a new graph with twice as many nodes, one representing \"head\" and \"tail\" for each node, however this can make some relationships (eg. transitivity) very difficult to observe. In the author's setting, while the graph augmentation may afford the ability to prove theoretical expressivity results, one might be concerned that the resulting graph is augmented to the point that a GNN architecture may require greater depth to perform the same sort of tasks it did previously. Of course the authors have provided empirical evidence that this augmentation is not problematic in at least three graphs, which is quite reasonable to support their approach, however it is something to bear in mind.\n\n**A2**: Indeed, your observation is on point. In essence, a model's complexity is contingent upon its depth (number of layers) and width (feature dimensions). With the incorporation of graph transformation, a single new unary predicate is introduced, thereby necessitating an additional feature dimension. This augmentation contributes to a minor increase in the model's size, which remains quite acceptable. However, a more intriguing aspect surfaces when we delve into the process of graph transformation, depicted in Figure 2 of the paper. Here, the progression from one-hop to three-hop message passing elongates the process, potentially demanding a tripling of the model's depth to achieve similar task outcomes. Furthermore, the graph transformation introduces two novel relation types, although this aspect is generally less consequential in terms of complexity.\n\n___\n\n> **Q3**: Typos and the suggested adjustment of the paper structure.\n\n**A3**: We greatly appreciate your feedback regarding the identified typos and your valuable suggestion for enhancing the readability of our paper. We will address these aspects diligently in our revised version."}, {"review_id": "kO6k251vWX", "reviewer": "Reviewer_Yror", "summary": "The paper extends the logical characterization of GNN --- node classification, by investigating the relational case i.e. multi-relational graphs. The paper generalizes the work of Barcelo et al. [ICLR 2020], who provided the logical characterization of GNNs for node classification in terms of First Order Logic with two variables and counting quantifiers (FOC2). The paper discuss the R2-GNN model, that extends R-GNN --- a GNN architecture for multi-relational graphs --- with a global read out function. The global readout adds aggregation over node features to the combination function in each layer. Some of the key results of the paper are the following:\n\n- R2-GNN are not captured in FOC2 and FOC2 is not captured by R2-GNN (for unbounded graphs)\n- R2-GNN are  captured in FOC2 for bounded graphs (given a known upper-bound on the number of nodes) but not vice versa\n- R2-GNN = FOC2 for simple graphs \n\nThe paper then extends the expressivity of R2-GNNs to full FOC2 , by introducing a transformation F that runs in linear time w.r.t the multi-graph size (O(|V|+|E|)). \n\nFinally, the authors extend there framework to temporal graphs. This is achieved by simply adding additional predicates indexed by time. The authors then discuss the expressivity of this framework with the previously introduced transformation  F applied to each time stamp  and another transformation comprising union of each time stamped graph.\n\nPost-rebuttal: I have read author's rebuttal, and I am more confident about my rating and will keep it, i.e. acceptance.", "questions": "When using many predicates, it seems that one could encounter some form of curse of dimensionality --- Do you think R2-GNNs suffer such issues? Specially in the temporal/transformation case, when number of predicates are further increased.\n\nIn general, some discussion on how the complexity of learning changes with number of predicates could be interesting", "limitations": "The authors discuss the fact that R2-TGNN*F^{T} do not improve performance over R2-TGNN on real-world dataset, whereas on their synthetic dataset they do observe improvement. This ambivalence between theory and practice is quite interesting and further discussion of this--- as to what exactly is different in real-world data that makes more expressive models inferior --- could be very interesting", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper extends logical characterization of GNNs in an interesting direction i.e. over relational structures. The theory presented is rather intuitive and the authors try to convey the key proof ideas. They also exploit their theoretical investigation to expand the expressivity of GNNs over relational structures and temporal graphs. They  provide convincing experiments (although slightly redundant, see weaknesses) over synthetic and real-world data.", "weaknesses": "- Quite terse for non-experts\n- Comparison of all the aggregation functions in tables are not much discussed in the paper and are not really important to the main message of the paper. Maybe this could be removed/shortened to give space for more proof intuitions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer Yror for the recognition of our original and theoretical results analyzing the expressivity of graph neural networks in the multi-relational and temporal setting. Below, we would like to give detailed responses to each of your comments. \n\n> **Q1**: When using many predicates, it seems that one could encounter some form of curse of dimensionality --- Do you think R2-GNNs suffer such issues? Specially in the temporal/transformation case, when number of predicates are further increased. In general, some discussion on how the complexity of learning changes with number of predicates could be interesting\n\n**A1**: Yes. The more predicates there are, the more dimensions are needed in the feature initialization function $I()$ defined in line 103. However, it also means the graph itself is more complex, and reasoning on it requires heavier logic formulas. In some sense, dimensionality is a necessary sacrifice when dealing with graphs under huge semantic systems. In fact, one can indeed avoid this sacrifice by changing the initialization function $I()$. As an extreme example, one can define $I()$ as $I(v):=\\prod_{i}{p_i^{c_i}}$ where $p_i$ is the $i-$th prime and $c_i$ is a $0/1$ that indicates whether node $v$ satisfies the $i-$th predicate. This initialization function also distinguishes nodes with different properties but outputs only one-dimension-features, no matter how large the predicate set is! However, we think these settings are unnatural and inapplicable for practical GNN models, so we don't use them in our paper. However, it might be worth noting that some theoretical work, such as the proof of Theorem5.2 of [1] indeed uses such settings for theoretical analysis convenience.\n\nGraph transformation will only introduce $3$ new predicates, so I think this additional cost is rather small and acceptable.\n\nIn temporal case, if one uses collapse function H (definition 11 in the paper) to transform a temporal graph to a static graph and then run static R$^2$-GNN on it, this truly introduces $|P|\\times T$ predicates and thus huge dimensionality, where $P$ is the unary predicate set and $T$ is the number of timestamps. However, R$^2$-TGNN won't introduce new predicates. It just runs different GNN model instances on different timestamps while preserving the original predicate set on each timestamp. Therefore, R$^2$-TGNN has a size proportional to the timestamp number $T$, but its dimensionality is still $|P|$. Temporal graph transformation $F^T$ (definition 12 in the paper) only introduces $3$ new predicates. In conclusion, R$^2$-TGNN$\\circ F^T$ introduces $3$ new predicates in total, which is acceptable. In Theorem 14 of our paper we've proven its superior expressiveness, so there is no need to use the costly $H$ transformation in temporal graphs. \n\n> **Q2**: The authors discuss the fact that R$^2$-TGNN$\\circ F^{T}$ do not improve performance over R$^2$-TGNN on real-world dataset, whereas on their synthetic dataset they do observe improvement. This ambivalence between theory and practice is quite interesting and further discussion of this--- as to what exactly is different in real-world data that makes more expressive models inferior --- could be very interesting\n\n**A2**: We think maybe that's because our real-world dataset has the following two drawbacks when used as a logical expressiveness benchmark.\n\n 1. Its labels cannot be modeled as a first-order-logic classifier. For example, maybe two isomorphic graphs (nodes) have different labels in the dataset. This negative fact about real-world datasets has also been observed and illustrated in Gao and Ribeiro's work (Figure 6 of [2]). As a result, permutation-equivariant GNNs can not get correct answers, and transformation increases the chaos. It means the real-world dataset may contain non-logical rules.\n\n2. The intrinsic logical rules in the datasets are too complicated. In this scenario, maybe the transformation sometimes makes these rules more complex. That's because the transformation changes the predicate set and graph pattern. As a result, the transformed intrinsic logical rules become too complicated to capture by our model with bounded size.\n\nAs we mentioned in the paper, [1] and [3] also observe the phenomenon. Their comments also say these commonly used benchmarks may be inadequate for testing advanced GNN variants. \n\n> **Q3**: Comparison among different aggregation functions should be removed/shortened to give space for more proof intuitions__\n\n **A3**: Thanks for your suggestions. We will consider your suggestions and add some more necessary proof intuition in our revised version. \n\n[1]The logical expressiveness of graph neural networks ICLR2020\n\n[2]On the equivalence between temporal and static equivariant graph representations ICML2022\n\n[3]Are powerful graph neural nets necessary? a dissection on graph classification arXiv"}, {"review_id": "wPpobcyPMX", "reviewer": "Reviewer_a55p", "summary": "The paper introduces a new connection between the power of the relational GNNs (working on multi-relational graphs) with a class of first-order logic functions. This class of functions named $\\mathcal{FOC}_2$ is a subset of first-order logic functions constrained to having only two variables, but includes counting quantifiers. The theoretical analysis considers three classes of multi-relational graphs: universal graph class, bounded size multi-relational graphs, and simple graphs that two nodes can have just one type of connection. Based on these classes paper proves in general none of $R^2-GNN$ and $\\mathcal{FOC}_2$ class of functions is a subset of each other, but adding a preprocess to the graph can make a model that is at least as powerful as the union of both classes. They also extend their results to the temporal graphs, where time series graphs can be collapsed into a static graph or considered as separate graphs. The paper also compares two different classes of models, time-and-graph versus time-then-graph, and proves second class is absolutely more powerful. Empirical results on synthetic and real-world graphs have been also conducted for supporting theoretical results.", "questions": "1. Node-level binary classification tasks are limited in the real world. Theoretical results are insightful, however, I was wondering if these results can imply anything about any other type of tasks on the graphs, e.g. multi-class node classifications or graph-level tasks.\n2. In Corollaries 4.1 and 9.1, it is interesting to see that both classes have precisely same power. However, this power seems to appear because of $\\mathcal{FOC}_2$ being able to enumerate all possible combinations of relation counts. Is there any complexity measurement, e.g. time-complexity of evaluating a function on a graph, on how complex can the function under $\\mathcal{FOC}_2$ be as the bound on the number of nodes in the graph or number of possible relations in the class increases?\n\n", "limitations": "The paper clearly defines the class of functions analysis. There are limitations on what types of graphs and tasks theoretical results work, but these limitations are clearly indicated in the paper.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Paper for almost all parts is very well-written.\n2. Paper finds the exact class of functions that can be learned by most common relational GNNs. \n3. Theorems show the theoretical superiority of time-then-graph functions on temporal graphs over the time-and-graph models.\n4. Paper finds a hierarchal classification of the power of different models on temporal graphs.\n5. Having supporting experiments for showing that theoretical implications have real effects on real-world datasets.\n", "weaknesses": "1. Intuition behind the functions used for synthetic graphs has not quite been explained. A little more explanation on why these functions and if they are just a random selection or one of the most simple functions that could convey a point will be helpful.\n2. The paper relies a lot on definitions of time-then-graph and time-and-graph models and refers to previous work for their definitions. These definitions are better to be briefly explained at least as a section in the Appendix.\n3. Section 6 starts with the Experiments and it is hard at first to understand that all synthetic are temporal. Particularly, superscripts on the relations were confusing at first without knowing they are temporal indices. It would have been better to clearly indicate that before starting and also include synthetic experiments for the general multi-relational graphs part.\n4. Real-world experiment on the Brain-10 dataset is a little inconsistent with theoretical results. \n\nMinor errors:\n1. Inconsistent use of $FOC$ and $\\mathcal{FOC}$ in the notations.\n2. Line 110, a space missing between \"vectors\" and \"$\\mathbf{x}_v^{(i)}$\".\n3. Line 339, \"somorphism\" -> \"isomorphism\"\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer a55p for acknowledging the merits of our paper in both theoretical and experimental aspects. In particular, we thank you for your interesting and insightful reviews, which motivated us to formally prove and add the following results (see below). We will add these results with rigorous proof in a later version of the paper.\n\n___\n> **Q1**: Node-level binary classification tasks are limited in the real world. Theoretical results are insightful, however, I was wondering if these results can imply anything about any other type of tasks on the graphs, e.g. multi-class node classifications or graph-level tasks.\n\n\n**A1**: In general, for a multi-class node classification task with $n$ labels, we can reduce it to $\\lceil \\log{n} \\rceil$ separate binary node classification tasks by predicting each binary bit of label's index. A more natural way is to just tackle it as $n$ different binary node classifications. Both of the two ways described above may lead to a generalization of this paper to multi-class scenario. However, we don't know how to directly model a multi-class classifier as a unified logical classifier. This may be an interesting future direction.\n\n___\n> **Q2**: In Corollaries 4.1 and 9.1, it is interesting to see that both classes have precisely same power. However, this power seems to appear because of  $FOC_2$\n being able to enumerate all possible combinations of relation counts. Is there any complexity measurement, e.g. time-complexity of evaluating a function on a graph, on how complex can the function under $FOC_2$\n be as the bound on the number of nodes in the graph or number of possible relations in the class increases?\n\n**A2**: We can indeed get a (rather loose) bound: Suppose there are $P$ unary predicates and $R$ relation types, and we are considering a bounded graph class with no more than $N$ nodes. For any classifier $c$, suppose $c$ can be represented as an R$^2$-GNN with depth (layer number) $L$. Then there is a $FOC_2$ classifier $\\varphi$ equivalent to $c$ such that the following bounds hold:\n\n- The quantifier depth of $\\varphi$ is no more than $L$.\n\n- The size of $\\varphi$ (size of parse tree) is no more than $2^{f(L)}$, where $f(L)=2^{2^{2Nf(L-1)}}, f(0)=2^{2^{2(P+R)}}$.\n\nThe key idea is the following: First, by Lemma 25 in our appendix, $c$ can be represented as a $FOC_2$ formula $\\varphi$ with quantifier depth no more than $L$. Then by Proposition 24 in our appendix (This is a key point of this bound; please refer to our appendix). We know the number of intrinsically different bounded-depth $FOC_2$ formulas is finite, so we only need to get an upper bound on this number. Finally, we can get the bound by iteratively using the fact that a boolean combination of a set of formulas can always be written as DNF (disjunctive normal form). The tower of power of two comes from L rounds of DNF enumerations. It is a rather loose bound. We can formulate it in the appendix in later version.\n\n___\n>**Q3**: Real-world experiment on the Brain-10 dataset is a little inconsistent with theoretical results.\n\n**A3** : We think maybe that's because our real-world dataset has the following two drawbacks when used as logical expressiveness benchmark.\n\n- its labels cannot be modeled as first-order-logic classifier. For example, maybe two isomorphic graphs (nodes) have different labels in the dataset. This negative fact about real-world datasets has also been observed and illustrated in Gao and Ribeiro's work (Figure 6 of [1]). As a result, permutation-equivariant GNNs can not get correct answers, and transformation increases the chaos. It means the real-world dataset may contain non-logical rules.\n\n- The intrinsic logical rules in the dataset are too complicated. In this scenario, maybe the transformation sometimes makes these rules more complex. That's because the transformation changes the predicate set and graph pattern. As a result, the transformed intrinsic logical rules become too complicated to capture by our model with bounded size.\n\nAs we mentioned in the paper, [2] and [3] also observe the phenomenon, and they think these commonly used benchmarks are inadequate for testing advanced GNN variants.\n\n___\n> **Q4**: Intuition behind the functions used for synthetic graphs has not quite been explained. A little more explanation on why these functions and if they are just a random selection or one of the most simple functions that could convey a point will be helpful.\nThe paper relies a lot on definitions of time-then-graph and time-and-graph models and refers to previous work for their definitions. These definitions are better to be briefly explained at least as a section in the Appendix.\nSection 6 starts with the Experiments and it is hard at first to understand that all synthetic are temporal. Particularly, superscripts on the relations were confusing at first without knowing they are temporal indices. It would have been better to clearly indicate that before starting and also include synthetic experiments for the general multi-relational graphs part.\n\n\n**A4** : Thanks for pointing it out! We've presented an explanation from line 308-316. Due to space constraints, the explanation may be too brief to be perfectly understood. We will revise this part in later version. Other suggestions on writing will be considered, too.\n\n___\n[1]On the equivalence between temporal and static equivariant graph representations ICML2022\n\n[2]The logical expressiveness of graph neural networks ICLR2020\n\n[3]Are powerful graph neural nets necessary? a dissection on graph classification arXiv"}, {"review_id": "CCKofyjfyo", "reviewer": "Reviewer_KFPi", "summary": "This paper justifies the logical expressiveness of R^2-GNN from the perspective of \"universal\" graph classes, including multigraphs and infinite graphs. Specifically, the R^2-GNN seems to be identical to the previous ACR-GNN in [1]. The engagement of graph classes makes theoretical statements in finer settings than previous ones in [1] which only involve one graph. The thorough inspection of different graph classes captures the expressiveness power of R^2-GNN compared to logical formulas in FOC_2. Moreover, this paper adapts a commonly used graph transformation $F$ to enhance the expressiveness of R^2-GNN to be stronger than FOC_2 on universal graph classes.\n\nThe theoretical results collapse into existing ones in [1] when the graph classes contain finite graphs, which are naturally bounded. The theoretical results can be also extended to temporal graphs under static representations, which are studied in [2]. To achieve this, the authors investigate the expressiveness hierarchy between the collapse function $H$, two static representations, GNN and TGNN (also defined by the author), and graph transformation $F$.\n\nEmpirical results support the expressiveness results partially related to $F$, $H$, and TGNN.\n\n[1] Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., & Silva, J. P. (2020, April). The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020).\n[2] Gao, J., & Ribeiro, B. (2021). On the equivalence between temporal and static graph representations for observational predictions. arXiv preprint arXiv:2103.07016.", "questions": "1. What is the definition of one boolean classifier set A as the subset of another boolean classifier set B for a given graph class GC? There are two possible definitions\n\n1. For any a in A, there exists a b(a) in B so that a and b(a) achieve the same results on all G in GC.\n2. For any G in GC and any a in A, there exists a b(G, a) in B so that a and b(G, a) achieve the same result on G.\n\n2. $F$ enhanced the power of R^2-GNN classifiers but it never relates the R^2-GNN. Can we state that $F$ also enhances the expressiveness of FOC_2 classifiers? What will Figure 3 be if we include FOC_2 \\odot F (or with proper modification of FOC_2 with new predicates introduced)?\n\n3.  For the temporal graph, the author draws two lines of hierarchies of expressiveness. What are the relationships between R^2-TGNN and time-and-graph and R^2-GNN\\odot H and time-and-graph?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper makes a large amount of work to (1) justify the logical expressiveness of R^2-GNN compared to FOC_2 in universal, bounded, and simple graph classes; (2) empirical technics to improve the expressiveness of GNN.\n\nThe theoretical results are original. Though some results are still missing to achieve a complete understanding of this problem. The presented ones are significant and inspiring.", "weaknesses": "The presentation of this paper should be improved given the dense representation of theorems and proofs. \n\nFirstly, the content is not self-contained. The definition of static representation of temporal graphs is not included even in the appendix.\n\nMost importantly, the key definition to justify logical expressiveness is missing. In Lines 130-131, the author states that the R^2-GNN is the set of all R^2-GNN-based boolean node classifiers. However, it is far from a satisfactory definition, which might be risky for accepting this paper. Please check the question part for my questions about the definition.\n\nAnotherW ambiguous part of this paper is that the graph transformation $F$ for multi-graphs is isolated to FOC_2 classifiers. In fact, $F$ should be orthogonal to classifiers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer KFPi for acknowledging the novelty and theoretical significance of our findings within multi-relational and temporal context. In particular, we are enthused by your thought-provoking comments, which motivate us to have deeper contemplation. Below, we would like to give detailed responses to each of your comments.\n\n___\n> **Q1**: What is the definition of one boolean classifier set A as the subset of another boolean classifier set B for a given graph class GC? There are two possible definitions. The definition for R^2-GNN classifiers is not satisfactory\n\n**A1**:  The correct definition is: *For any a in A, there exists a b(a) in B so that a and b(a) achieve the same results on all G in GC.*\n\nA R$^2$-GNN classifier is defined as any classifier that can be represented as a R$^2$-GNN model (outputs node features) equipped with a binary classification function $CLS(x): \\mathbb{R}^D\\rightarrow 0/1$. (where $x$ means that an input of $CLS()$ is a node feature outputted by the model, and $D$ represents the output feature dimension. $CLS()$ can be any function with the above domain and range.)\n\nSorry that we did not explain this explicitly. We will include an explicit definition in our revised version.\n\n___\n>**Q2**: $F$ enhanced the power of $R^2-GNN$ classifiers but it never relates the $R^2-GNN$. Can we state that \n also enhances the expressiveness of $FOC_2$ classifiers? What will Figure 3 be if we include $FOC_2 \\circ F$ (or with proper modification of $FOC_2$ with new predicates introduced)?\n\n**A2**: Your perspective is entirely accurate!  We used the class $FOC_2\\circ F$ in line 230-232 as an auxiliary class.  \n\nAlthough R$^2$-GNN can be boosted by $F$, it is not true for $FOC_2$. A counter-intuitive fact is $FOC_2\\circ F \\subsetneq FOC_2$, which means $FOC_2$ becomes strictly weaker after transformation. Since $FOC_2\\circ F$ is just an unimportant bridge class, we don't write the above as a theorem in our paper. We can add the detailed proof in the appendix afterwards. In the following, I will briefly explain it.\n\nFirst, following the similar idea of proof of Theorem 9 combined with a slightly modified version of Lemma 26 (in the appendix), we can prove $FOC_2\\circ F\\subseteq FOC_2$. We can't give the specific proof idea due to space constraints, so please refer to our appendix or wait for our detailed proof in later version if interested.\n\nThen, consider the logical classifier $\\varphi$ that \"classifies a node $v$ to be true iff there are at least 5 nodes that aren't neighbors of $v$\". $\\varphi$ can be easily represented as a $FOC_2$\n formula. However, it is impossible to construct an equivalent $FOC_2\\circ F$ classifier! Thinking about this example, one may gain some intuition about why the transformation actually makes $FOC_2$ weaker. Combined with the above, we know $FOC_2\\circ F \\subsetneq FOC_2$.\n\nIn fact, we have $FOC_2\\circ F= FOC_2$ for any bounded graph class. Moreover, if we introduce a brand new relation type and modify the definition of graph transformation a bit, $FOC_2\\circ F=FOC_2$ would be true for arbitrary universal graph classes. However, since this modification will introduce more edges and predicates to our transformation and make $F$ more costly and complex, we give in to the current weaker transformation in our paper. After all, $FOC_2\\circ F$ is not important, so we don't have an incentive to boost it.\n\n___\n> **Q3**: For the temporal graph, the author draws two lines of hierarchies of expressiveness. What are the relationships between R$^2$-TGNN and time-and-graph and R$^2$-GNN$\\circ H$ and time-and-graph?\n\n**A3**: First, it must be noted that the original definitions of time-and-graph and time-then-graph only consider localized message-passing. Therefore, in order to compare them fairly with our framework, we have to enable them to do global readout as R$^2$-TGNN do. This is just a slight modification from the original definition of time-and-graph.\n\nRelationships among time-and-graph, R$^2$-TGNN and R$^2$-GNN $\\circ H$ are as follows: We can add formal proof in appendix of later version. Here, we just briefly describe some key points.\n\n1. R$^2$-TGNN  $\\nsubseteq$ time-and-graph\n\nThat's because time-and-graph can not capture a chain of information that is continuously scattered in time intervals. Specifically, $\\varphi(x):=\\exists y,\\Bigl( r_1^2(x,y)\\wedge \\bigl(\\exists x,r_1^1(y,x)\\bigl)\\Bigl)$ can't be captured by time-and-graph but is in R$^2$-TGNN.\n\n2.  time-and-graph $\\nsubseteq$ R$^2$-GNN$\\circ H$\n\nThat's because the static GNN defined in [1] is stronger than R$^2$-GNN. However, Their definition is kind of too ideal and doesn't exactly match most practical models (We can elaborate why this is the case in further discussion if you are interested). That is also why we didn't include a comparison between time-and-graph and R$^2$-TGNN/R$^2$-GNN$\\circ H$ in this version of our paper.\n\n3. Whether time-and-graph $\\bigcap$ R$^2$-GNN $\\circ H\\subseteq$ R$^2$-TGNN ?\n\nRegrettably, we currently do not have a definitive answer to this question, which remains as an open problem. On an intuitive level, however, we are inclined to believe in the validity of *time-and-graph $\\bigcap$ R$^2$-GNN $\\circ H\\subseteq$ R$^2$-TGNN*. \n\n___\n[1] On the equivalence between temporal and static equivariant graph\nrepresentations ICML2022"}, {"review_id": "qKWQEU3def", "reviewer": "Reviewer_pnMq", "summary": "The paper deals with classifying multi-relational graphs, and specifically, the R-GNN architecture, which deals with more than one type of edge by producing a different neighbor set for each of them, aggregating the messages of each neighbor, and then merging them together in a final update layer. The first results in the paper are that these architectures are limited, as Figure 1 shows, these architectures cannot even count the number of total neighbours of a node. To fix this, the proposal is to maintain the architecture, but apply a graph transformation task, some sort of graph reification. Intersectingly, R-GNNs and R^2-GNNs recover the expressive power of similar architectures in the single-relation scenario, when applied not under the original graphs but in the transformed graphs. The second part of the paper looks to implement these ideas specifically in Temporal Graphs, wherein one has a different relation for each timestamp measured in the temporal part. As multi-relational graphs, this is indeed a nice application of the framework. Results and experiments show that the proposed architecture competes with several other proposals for classification of temporal graphs.", "questions": "*  Please justify why a study on R-GNN is important, and whether your insights could be valuable when dealing with any other architecture incorporating edges.\n\n  *  I'd tend to think that maybe every multi-labelled GNN would benefit from the graph transformation approach, and like wise for the global readout. What would happen if I run GRU-GCN or TGN over a temporal graph that has already been transformed? Or if instead of using R^2-GNN I use any other GNN with the graph transformation?", "limitations": "*    Please discuss potential inconveniences regarding using the transformation in graphs. You probably need more layers, with the added cost on training. Also, even if the transformation is linear, it is not free for huge graphs, so your approach is probably better tailored to datasets containing several small graphs.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "* Sound, robust theoretical study relating multi-label GNNs with logic. The proofs seem correct and use a variety of techniques.\n *   Claims are backed up with examples, so that it is easy to quickly grasp the ideas of the paper.\n *   The claims in the paper are backed up with experiments: It really does seem that the power of R-GNNs (and similar architectures) benefits from applying the graph transformation.", "weaknesses": "*   The results are tailored specifically to a single architecture (R-GNNs). One could think of several other ways to incorporate edge information, I know for instance GATs (Velickovic et al. 2018), but the paper does not discuss any other approach, and we don't know if the weakness shown in the results of section 4 are due to the specific architecture, or if there is a bigger problem underlying multi-relation graphs that must be tackled with the transformation.\n\n*    The proposed solution involves a linear transformation in graphs, but probably demands much more layers in a GNN, as the length of every path is now multiplied by two. This involves adding extra costs to the learning process, and probably some difficulties in using the node embedding of the graph.\n\n*    Synthetics experiments do not compare against other GNN architectures capable of dealing with different edges, appart from R-GNN. Real life experiments do compare against other temporal variants, but it is difficult to see if the added power is due to the global readout, the transformation, or the mix of everything in the architecture proposed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer pnMq for the recognition of our theoretical results on both static and temporal settings as well as our proposed novel transformation. Below, we would like to give detailed responses to each of your comments.\n\n___\n> **Q1**: Please justify why a study on R-GNN is important, and whether your insights could be valuable for other architectures such as GAT.\n\n**A1**: It is worth noting that R-GNN is not a specific model architecture; it is a framework that contains a bunch of different GNN architectures. In the paper, we just said it's generalized from R-GCN [1], but our real goal is to define a generalized framework as an abstraction of most Message-Passing GNNs (MPGNN). We feel sorry for not pointing this out explicitly and perfectly in the paper. In the definitions (line 112 and 118), the functions can be set as any functions you like, such as matrix multiplications or QKV-attentions. Most commonly used GNN such as R-GCN[1] and R-GAT[2] are captured (upper-bounded) within our R-GNN frameworks. Many other related works, such as [3], [4] and [5] also use intrinsically the same frameworks as our R-GNN if you read the definitions, so R-GNN is a kind of abstraction framework for MPGNN that has been approved widely and studied a lot in the community. Therefore, we think analyzing these frameworks leads to common results for many existing GNNs.\n\nIn particular, GAT [6] is a kind of single-relation GNN which is not our topic, and its multi-relational variation R-GAT [2] can be incorporated in our R-GNN framework by setting the combination function as QKV-attention module.\n\n___\n> **Q2**: I think every multi-labelled GNN would benefit from graph transformation, and like wise for the global readout. What would happen if I run GRU-GCN or TGN over a transformed temporal graph? Or using any other GNN with the graph transformation?\n\n**A2**: Intuitively, every (temporal) Message-Passing GNN can be augmented by graph transformation and global readout, if they are within our framework. We've added experiments that test performance of the most recent model GRU-GCN/TGN with graph transformation and R-GAT [2] plus global readout and graph transformation. It can be seen that graph transformation indeed improves performance in most cases. Please check the tables below.\n\n| accuracy| $\\varphi_1$ | $\\varphi_2$ | $\\varphi_3$ | $\\varphi_4$ |\n| ------------------------------ | ----------- | ----------- | ----------- | ----------- |\n| R-GAT $\\circ H$           | 100         | 61.4        | 88.6        | 82.0        |\n| R-GAT+readout $\\circ H$        | 100         | 93.5        | 95.0        | 82.2        |\n| R-GAT+readout $\\circ F\\circ H$ | **100**         | **98.2**        | **100**         | **95.8**        |\n\n| Models  | GRU-GCN | TGN  | GRU-GCN$\\circ F^T$ | TGN$\\circ F^T$ |\n| -------- | ------- | ---- | ------------------ | -------------- | \n| Brain-10 | 91.6| 91.2 | 95.0| 94.2| \n\n___\n> **Q3**: Please discuss potential inconveniences regarding using the transformation in graphs. You probably need more layers, with the added cost on training. Your approach is probably better tailored to datasets containing several small graphs\n\n**A3**: You are right. The complexity of a model depends on its depth (layer number) and width (feature dimension). The graph transformation introduces 1 new unary predicate, so one needs to add one feature dimension, which makes the model slightly bigger but acceptable. On the other hand, if we observe the process of graph transformation as shown in Figure 2 of the paper, we will find that one-hop message passing is stretched to three-hop ones, which may require 3 times the depth to do the same task.\n\nHowever, in real-world datasets, the scalability of graph transformation is not as weak as imagined. We've added two real-world datasets DGS and AM (suggested by *Reviewer Hbfa*), whose graphs are much bigger in the following table. These results show our method is effective both on small and large graphs.\n| Models | AIFB | MUTAG | DGS  | AM   |\n| ------------------ | ---- | ----- | ---- | ---- |\n|# of nodes|8285|23644|333845|1666764|\n|# of edges|29043|74227|916199|5988321|\n| R-GNN| 91.7 | 76.5  | 81.2 | 89.5 |\n| R$^2$-GNN| 91.7 | 85.3  | 85.5 | 89.9 |\n| R$^2$-GNN$\\circ F$ |**97.2**|**88.2**|**88.0**| **91.4** |\n\n___\n>**Q4**: Synthetics experiments do not compare against other GNN. It is difficult to see if the added power is due to the global readout, the transformation, or the mix of everything in the architecture proposed.\n\n**A4**: We've added R-GAT [2] synthetic experiments in the first table of Answer 1. In fact, as we've mentioned in Answer 1, R-GAT is also an architecture within R-GNN. From the experiments, we can see expressiveness improvements by using graph transformation/global readout on different kinds of equivariant MPGNN.\n\nWe've added some experiments shown in the table below to help you better see which components of our method bring added power. These experiments show separate improvements from global readout and graph transformation. As we said in the paper, the drop in the last column may be due to the intrinsic drawbacks of current real-world datasets. Many real-world datasets can not be perfectly modeled as first-order-logic classifier. \n This non-logical property may lead to less convincing experimental results. As [3]  commented,  these commonly used benchmarks are inadequate for testing advanced GNN variants.\n\n|Models|R-TGNN|R-TGNN$\\circ F^T$|R$^2$-TGNN|R$^2$-TGNN$\\circ F^T$|\n|--------|------|-----------------|----------|---------------------|\n|Brain-10|85.0|90.9|94.8|94.0|\n\n[1]Modeling relational data with graph convolutional networks ESWC2018\n\n[2]Relational graph attention networks arXiv\n\n[3]The logical expressiveness of graph neural networks ICLR2020\n\n[4]A Theory of Link Prediction via Relational Weisfeiler-Leman arXiv\n\n[5]Logical Expressiveness of Graph Neural Network for Knowledge Graph Reasoning arXiv\n\n[6]Graph Attention Networks ICLR2018"}]

Author rebuttal:

Meta-review: In this submission, the authors explore the expressivity of GNNs in a multi-relational context. The paper is original and offers valuable theoretical insights that are sure to be interesting to the graph neural network community. The authors propose for the first time a rigorous logical foundation for relational GNNs.

While the authors acknowledge limitations in real-world dataset validation (and should make these limitations more visible and explicit in the final manuscript), the theoretical insights offered here outweigh this concern, rendering the paper valuable even without strong empirical results on real-world datasets. Given its contribution to the field and potential for sparking further research, I recommend the acceptance of this paper.
Decision: Accept (poster)