Towards Expressive Graph Representations for Graph Neural Networks
Authors: Chengsheng Mao
Liang Yao
Yuan Luo
Venue: Submitted to ICLR 2023 (2023)

Abstract: Graph Neural Network (GNN) shows its powerful capability for graph representation learning in various application areas. However, most existing GNN variants learn the graph representations in a non-injective or non-continuous fashion, both reducing the model expressive power. In this paper, we present a theoretical framework to improve the expressive power of GNN by taking both injectivity and continuity into account. Accordingly, we develop \textit{Injective Continuous Graph Neural Network} (ICGNN) that learns the graph and node representations in an injective and continuous fashion, so that it can map similar nodes or graphs to similar embeddings, and non-equivalent nodes or non-isomorphic graphs to different embeddings. We validate the proposed ICGNN model for graph classification and node classification on multiple benchmark datasets including both simple graphs and attributed graphs. The experimental results demonstrate that our model achieves state-of-the-art performances on most of the benchmarks.

Under review as a conference paper at ICLR 2023
TOWARDS EXPRESSIVE GRAPH REPRESENTATIONS FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Network (GNN) aggregates the neighborhood information into the node embedding and shows its powerful capability for graph representation learn- ing in various application areas. However, most existing GNN variants aggregate the neighborhood information in fixed non-injective fashion, which may map different graphs or nodes to the same embedding, detrimental to the model ex- pressiveness. In this paper, we present theoretical framework to improve the expressive power of GNN by taking both injectivity and continuity into account. Based the framework. Neural Network (iceGNN) that learns the graph and node representations in an injective and continuous fashion, that it can map similar nodes graphs to simi- lar embeddings, and non-equivalent nodes or non-isomorphic graphs to different embeddings. We validate the proposed iceGNN model for graph classification and node classification on multiple benchmark datasets. The experimental results demonstrate that our model achieves state-of- of-the-art art performances on most of the benchmarks.
develop injective and continuous expressive Graph
INTRODUCTION
Graph representation learning that maps graphs or their components to vector representations has attracted growing attentions for graph analysis. Recently, graph neural networks (GNN) that can learn distributed representation for a graph or a node in a graph are widely applied to a variety of areas, such social network analysis (Hamilton et al.) [2017] Ying et al.) 2018a). molecular structure inference (Duvenaud et al.] 2015; Gilmer et al. (2017), 77, text mining (ao et al. 2019)) Peng et al. 2018), clinical decision-makinn (Mao et al. 2022b Li et al. 2018) and image processing (Mao et al. 2022a Garcia & Bruna 2018). GNN recursively updates the representation of a node in graph by aggregating the feature vectors of its neighbors and itself (Hamilton et al., 2017) Morris et al.] 2019)
Xu et al. 2019). The graph-level representation can then be obtained through aggregating the final representations of the nodes in the graph. The learned representations can be fed into a prediction model for different learning tasks, such as node classification and graph classification.
In GNN, the aggregation rule plays a vital role in learning expressive representations for the nodes and the entire graph. There many GNN variants with different aggregation rules proposed to achieve good performances for different tasks and different problems (Kipf & Welling 2017; Hamilton et al.) 2017 Zhang et al.] 2018 Xinyi & Chen 2019 Wang al. 2020). However, most of the existing GNN aggregation rules are designed based on a fixed non- ion-injective pooling function, (e.g., max pooling and mean pooling) on non-continuous node types (e.g., graph isomorphism test). The non-injective aggregation may map different (non-isomorphic) graphs or (non-equivalent) nodes to the same embedding; and the non-continuous aggregation may map similar graphs or nodes to quite different embeddings, both detrimental to the expressive power of GNN. For example, for the graph with attributed nodes in Figure a[), mean pooling or sum aggregation on the neighborhoods generates the same neighborhood representation for all the nodes (Figure (()). thus cannot capture any meaningful structure information. Xu et al. (2019) showed that a powerful GNN can at most achieve the discriminative power of Weisfeiler-Lehmne discriminate a broad class of graphs (Weisfeiler & Lehman 1968), and proposed the powerful graph isomorphism network (GIN). However, the theoretical framework of GIN is under the assumption that the input feature space is countable, which makes GIN less expressive when applied to graphs with continuous attributes.
graph isomorphism test (WL test) which can

---

Under review as a conference paper at ICLR 2023
(3,001)
B.100000
(0,00
10,0033333
(0..0.18,00002)
Neightor mm
(A,0A
10,00.1,2333
Injection WKCTE
(3.2000.00)
104.0.14-18
[-30]]
(0.0]
(2/00)
(1,00)
I2A.A.....
(1100.00)
12.01
(1,40
[a] original graph
WL test
expressive representation
(d) mean pooling or sum aggregation
Figure I: An overview of our framework on an exemplar attributed graph in one iteration. (a) Original graph with attributed nodes; (b) Graph nodes represented by the corresponding attribute and neighborhood set through WL test; (c) The node vector representations after an injective set function on neighhorhood sets, here the set function is f(X) Exex (1, 1, xx2 _² x²); (d) A non-injective alternative set function GNNs, after aggregation, the node information remain unchanged, node B and D still have the same representation despite their different neighborhoods.
We argue that the expressive power of a graph mapping should imply two aspects, injectivity and continuity: the injectivity ensures different graphs are mapped to different representations and the continuity ensures that similar graphs are mapped to similar representations. Most previous works only took either one into account for GNN design; few considered both injectivity and continuity. Here, we present a theoretical framework that can guide us to design highly expressive GNNs with both injectivity and continuity for general graphs with continuous attributes. We also present necessary condition related to the representation dimension for fully injective and continuous graph mapping. The general idea of our framework is illustrated in Figure 1
Our main contributions are summarized follows. (1) We present theoretical framework to guide the design of expressive GNNs by ensuring the injectivity and continuity in the neighborhood aggregation process. (2) We present limitation about the representation dimension for fully injective and continuous graph mapping. (3) Based on the framework, we implement two injective and continuous expressive GNN (iceGNN) models with fixed and learnable aggregation function, respectively. (4) We validate our models on multiple benchmark datasets including simple graphs and attributed graphs for graph classification and node classification, the experimental results demonstrate that our models can achieve state-of-the-an performances on most of the benchmarks. Our code is available in the Supplementary Material. Common notations used throughout the paper are found in Appendix A. 5
2 RELATED WORK
Many GNN variants with different aggregation rules are proposed in the literature to achieve good performances in different tasks. GIN proposed Xu et al. (2019) is expected to be highly expressive for simple graphs where node attributes are one-hot encoders which sum aggregation is injective. However, GIN cannot be directly extended to attributed graphs with the same expressive power, because the aggregation is longer injective in uncountable cases. GCN is another GNN variant with simple element-wise mean pooling in a node's neighborhood, including the node itself (Kipf & Welling 2017). Hammlton et al. (2017) tested aggregators in GraphSAGE, including mean aggregator, LSTM aggregator and max pooling aggregator, they found no significant performance difference exists between the LSTM aggregators and pool aggregators, but GraphSAGE-LSTN, significantly slower than GrEp invariant on sets, but the operation not injective, which may result in the same embedding for different inputs. LSTM aggregation could have large expressive capacity, but it is not permutation invariant, this may cause equivalent nodes or isomorphic graphs to have different embeddings. Cooso et al. (2020) combined multiple aggregators with degree-scalers and proposed PNA to improve the expressive power of GNN, but they did not provide a theoretical guidance on how to improve the expressive power of GNN. In this article, we present theoretical framework to guide the design of expressive GNNs by ensuring the injectivity and continuity in the neighborhood aggregation process. PNA can exactly fall into our framework by simple comparison analysis.
Mean aggregation and max pooling are permutation
2

---

Under review as a conference paper at ICLR 2023
Theoretical studies on GNNs showed the expressive power of GNNs has been linked to the WL test (Morris et al., 2019; Xu et al. 2019). Xu et al. (2019) showed that GNNs with 1-hop neighborhood aggregation at most achieve the expressive power of the 1-WL test, and developed GIN that can achieve this expressive power in countable space. Based on k-WL. tests, Morris et al. (2019) proposed k-GNN, which can take higher-order interactions among nodes into account. Maron al. (2019a) proved that order-k invariant graph networks are at least as powerful as the k-WL tests and developed GNN model that is more powerful than message passing GNNs, possessing the expressiveness of 3-WL, but the higher expressive power comes with a computational cost of processing high order tensors. survey on the expressive power of GNN can be found in Sato (2020).
3
PRELIMINARIES
3.1 GRAPH NEURAL NETWORKS
Most modern GNNs fall into the category message passing neural networks (Gilmer al. 2017 that follow a neighborhood aggregation strategy that recursively updates a node representation by aggregating representations of its neighbors and the node itself. The graph-level representation obtained through aggregating the final representations of all the nodes in the graph. Formally, the propagation rule of a GNN layer can be represented as
(i = f1 (WHL E
(1)
(0)+1(()= = f( (o)
(2)
where (v) is the representation vector of node v in the kth layer, and ()) is initialized with
(v), the original attributes of node v. .V(v) is the neighborhood of u. f(Aa) (.) aggregates over the
neighborhood (w) to generate neighborhood representation H (k) [v))' and (k) (-) combines the
node's current representation H (()) (v) and its neighborhood's representation H (A) in the kth layer.
N(w))
For node embedding, the node representation the final layer (²) (suppose a total of K layers) is considered as an informative representation that could be used for downstream tasks, e.g., node classification. For graph or subgraph embedding, another aggregation function s'((.) employed to obtain the graph-level representation la by aggregating the final representations of all nodes in the graph or subgraph G, i.c.
HG = Sn
[a()), so(.) and SR(.)) are crucial for the expressive power of a GNN. fa(:) and fR(.) are set functions that map set to vector, they can be simple summations sophisticated graph-level pooling functions (Ying et al., 2018b Zhang et al. 2018 Wang et al. 2020 fc(-) operates on two vectors, it can be usually modeled by multi-layer perceptron (MLP) linear function on the concatenated vector.
3.2 THE EXPRESSIVE POWER OF GNN
Recently, theoretical analysis showed that the expressive power of a GNN is associated with the WL test (Morris et al. 2019 Xu et al., 2019). Xu et al. (2019) proved that the expressive power of GNN is bounded by the -ineennnnii Theorem from Xu al. (2019) describe the relation between GNNs and WL test in expressive power on discriminating graphs, refer to Xu et al. (2019) for the proofs.
Seisfeiler-Lehmae test. The following Lemma and
Lemma 1. If the WL test decides two graphs G, and G2 are isomorphic. any GNNs defined by Eq. 2 3 will map G1 and G2 to the same embedding.
Theorem 1. If WL test decides two graphs G1 and G2 are not isomorphic, a GNN with sufficiently many GNN layers defined by Eq. [ aand 3 can also map G2 and G2 to different embeddings if the functions (.). fo()) and (n(.) are all injective.
3

---

Under review as a conference paper at ICLR 2023
The above Lemma and Theorem guide to design GNN that has the discriminative power equal to WL test. The key is to design injective functions for (A) fc(.) and fR()). An injective function for fc(-) that operates on two vectors be easily obtained by concatenating the two vectors. But designing an injective function for (a(+) or [n(.) that operates on a set is not trivial, because sets have different number of elements, and the operation on the set elements must be permutation-invarie
While Xu al. (2119) considered the injectivity in their framework, the continuity of these functions are also crucial to the model expressive capability, which was not considered in Xu et al. (019)) Some popular aggregations by pooling, e.g., mean pooling and max pooling, are continuous but not injective. Few works took both injectivity and continuity into account. In the following, we will present how to design the continuous injective aggregation function on set and show a necessary condition related to the dimension for injective and continuous aggregation.
4 METHODS
4.1 SET REPRESENTATION
set function is a function defined in domain that collection sets (specifically multisets where the same object can repeat multiple times, set means finite multiset all through the paper). In finite graph, the neighborhood of each node is considered as a finite set. Thus, in this paper, we only consider set functions of finite sets. A continuous set function is of real importance in practice Wagstaff al. 2011). The continuity of function ensures that the change in output is very slight the input altered slightly by any reason, such truncating to machine precision. In this paper, consider the ordinary continuity, where the continuity of function f(x) at point e is defined by the limit lim f(x) = f(c).
For M E N. a set function f(X) defined in domain X's = {x C | S M) can be represented sequence of permutation-invartee functions for different set sizes, i.e.,
f(X) = (1 ... ,.:) if |
(4)
where T1,' , E.
Definition 1 (Continuous set function). For M N and a set function f(X) defined in domain
XM -X X c B |X| S M), s(X) is represented as Eq. 4 if fi(x1,... ,2:) is continuous in the Euclidean space for every i S M, we call f(XX a continuous set function.
Obviously, continuous set function also have the property that sufficiently small changes in the input (a sufficiently small change will not change the set size) result arbitrarily small changes the output. Thus, by continuous set function, graphs with very similar structures and attributes could be mapped to similar embeddings. An injective set function can map distinct sets to distinct values. Thus, an injective and continuous representation function encode such that different sets have different representations and similar sets have similar representations.
representation
The following theorem provides way construct continuous injective functions in uncountable space by sum aggregation after a certain transformation.
Theorem 2. Assume XM set of finite subsets of RRd with size less than or equal to M, i.e., for M E N and XMs = [X C Rd, ||| S M), there exists an infinite number of continuous functions Rd RR such that the set function f XM + RRP, s(X) = Exxx (xx is continuous and injective.
Theorem generalizes Lemma in Zaheer et al. 2017 ) to multidimensional cases. We prove Theorem
in Appendix A.2] The proof contains three steps: 1. Constructing satisfying function in one dimensional cases (d = 1); 2. Constructing a satisfying function in multidimensional cases(d >> 1) based on the results in step 1; 3. The satisfying function can be used generate infinitely many other satisfying functions.
In our proof, find @ (x) defined Eq. 5 (where i,j 1,... d) that can make f(X) Exex x (xx) continuous and injective if the first entries of all vectors in X are distinct. If the first entries of all vectors in X are not distinct, we could add P; to & M (x) (i.c., &y (x)) to ensure fully injectivity and continuity.
4

---

Under review as a conference paper at ICLR 2023
Pr =[1, x[i]x [.]............................. (0
Pij = =[x[i], x[]]x[]],, x[1]]x
x[1] x[1]
(5)
(x) PI,,PI.2 ...
,P,aa
(x) = ( P2,
In the proof, we also provide a way to construct such a function (xx) by defining a continuous injective function g IR RR then (xg(x)) can also satisfy the condition if have a function (xx) satisfying the condition. We call (x) the transformation function.
The following theorem tells necessary condition of constructing an injective and continuous set function by the sum aggregation.
Theorem 3. Let M E N and XM = [x[X C Rd X = M), thenfor any continuous function $ Rd R.N. if N <, d.M, the set function X R. S(X) Exex Φ(x) is not injective.
Theorem 3 tells that, to construct continuous injective set function for sets with M d-dimensional vectors by sum aggregation with continuous transformation & (x),, (xx) must have at least dMM dimensions. We are restricting & as continuous function so that can be modeled by a neural network, because a neural network can approximate any continuous function rather than any function by the universal approximation theorem (Cybenko) 1989..
We prove Theorem 3 in Appendix A.3
4.2 INJECTIVE AND CONTINUOUS EXPRESSIVE GRAPH NEURAL NETWORKS
Since Theorem 2 tells that a set can be uniquely represented by a sum aggregation of its elements through a continuous transformation function, we can use the unique set representation model the neighborhood of each node in graph, and thus improve the expressiveness of graph representation. From Theorem I design an expressive GNN, we need to design injective and continuous functions for f-).) fc(-) and fx(-). Since fc(-) is easy to get continuous and injective, and fa(-) and fr(()) both operate on set of vectors Ted thus, we need Theorem 2 to guide us to construct continuous and injective set function for fa(-) and fn(()) by sum aggregation after certain continuous transformation.
According Theorem for set of M d-dimensional embeddings. the transformation function must be least ddm-dimensional to construct continuous injective set function with sum aggregation, thus, without dimension reduction in fc(.). we get (dM + d)- dimensional embedding after one layer (dM for the set of neighbors and d for a node's current dimension). After & layers, the output embeddings have d(M + 1)* dimensions, which makes it impractical to implement fully injective and continuous GNN for large graphs. Nevertheless, in a specific learning task, not all dimensions related the learning task, could design learnable neural networks (c.g., MLP) to adaptively reduce the output dimension in each layer as Eq. 6
COMBINE function.
f (k) (x1, x2) MT.P(k) ((x1,X2) X2))
Note that an MLP mapping high-dimensional vectors to low-dimensional vectors cannot be continuous and injective. Here, MLP is used for task-driver feature reduction.
AGGREGATE function. f-(-) operates on set of node embeddings in the neighborhood of node. We have two choices of the transformation function of f- i.e., transformation and learnable transformation.
Fixed transformation. In the proof of Theorem we find the function 1n (x) defined in Eq. can be used continuous transformation function to make the sum aggregation continuous and injective most cases. Let M,, be the max neighborhood size for all nodes in all the graphs. Usually, if M,, not very large, we can set the transformation function as D'M, (x) for each layer & to maintain the expressive power. Then fa(+) for layer k can be represented as
f(() (f (1 (( (w) N(w)))=
I'se. (H(() wEN(()
Σ
Combining Eqs. and we get the propagation rule,
5

---

Under review as a conference paper at ICLR 2023
(0) = MLP ((H())))
Σ IMM, (H (EN(v)
(8)
Though the function (x)(x) defined in Eq. 5 can make the sum aggregation continuous and injective, it may result in numerical stability since the item x[i] will make the number become very large or very close O if M is very large. To address this issue, we use continuous and injective function g(x) to normalize the power, since in the proof of Theorem 2 we know & (9((())))))) is also a qualified transformation function make the sum aggregation continuous and injective, if gxx) continuous and injective. In this paper, we set
[x [ - (-
x(i] 2 0 x[i] <
Learnable transformation. Due to the continuity of the transformation function, we can also learnable MLP to approach the transformation function for fa(-) by the universal approximation theorem (Cybenko 1989), then we get the propagation rule as
H(+ MT.P! ((H())))
MLP (w))) wEN(w)
E
(10)
where MLP,( and (l.P(*) serve as the transformation function and the combine function for the kth layer, respectively. By this way, we get all the node embeddings for all graphs. For graph or subgraph embedding, we need another aggregation function fR(-) to aggregate all the node embeddings in a graph.
READOUT function. fa(-) operates on a set of all node embeddings in graph. For large graphs with many nodes, fully injective and continuous set function will generate high- high-dimensional embeddings. We also use a learnable MLP as the transformation function to reduce the output dimension.
HG ff fR ({ ((H1) = ( (H))
(1I)
VEG
Note that the final node embeddings are output from an MLP! and directly input to M LPc. we merge the two MLPs as one in the implementation. For graph classification, the output graph-level embedding are input to an MLP classifier with ne outputs corresponding to the probabilities of the classes. We only use the final GNN layer outputs for classification rather than concatenating all layers' outputs construct a longer vector representation for classification as GIN did, because we think the final layer outputs contain all information from middle layers and are expressive enough for graph classification. addition, this can reduce the input dimension of the final classifier, resulting in simpler classifier than GIN, especially in case of many layers.
Remark. By the propagation rule Eqs. S and T0, we implement two variants of iceGNNs, namely iceGNN-fixed and iceGNN-MLP, respectively. In practice, for specific learning task, e.g., graph classification that maps a graph to a single label, the whole process cannot be injective, and a certain dimension reduction process must be applied. The key is ensure the dimension reduction is guided by the target task. For example, the sum aggregation is not injective, and moreover, the process is fixed and cannot be adjusted by the loss function; thus, the aggregation could lose important information that is related to the target task. In our framework, according to our theoretical result in Theorem we could achieve an injective and continuous aggregation by employing transformation function (x)). For iceGNN-fixed, fixed transformation function is applied to make the aggregation injective and continuous, and then learnable MLP is applied to reduce the dimension. And for iceGNN-MLP we combine the aggregation and dimension reduction (linear function L) in one learnable MI.P. Thus, the learned low-dim features are related to the task.
EXPERIMENTS
5.1 GRAPH CLASSIFICATION
Datasets. We use simple graph benchmarks and attributed graph benchmarks for graph classifica- tion, the 8 simple graph datasets contain 4 bioinformaties datasets (MUTAG, PTC, NCI1, PROTEINS)

---

Under review as a conference paper at ICLR 2023
Table Accuracy for simple graph classification in test set (%). Top performances on each dataset are bolded. The best performances are underlined. The first two rows are our results, the middle part corresponds the deep learning methods, the bottom part corresponds the graph kernel methods
MUTAG
PTC
NCI1
PROTEINS
COLLAB
IMDB-B
IMDB-M
KDT-B
ScGGNN fixed
91.1 6.7
67.9 1:
82. + 1.6
77.5 62
S0GNN MLP
90.6 1.9
68.8 1: 7.2
83.6 1 1.9
76.5 3.5
78.7 1: 1.5
72.8 1: 3.9
50.3 -1: 2.3
92.0 1: 3,5
GIN-fiml
90.0 = 54
65.9 1: 6.1
61.4 1 1.6
76.2 2 4,9
75.2 :: 2.0
72.5 +
48.9 :2
90.1 :: 5.3
GIN
Xu
2019
89.4 56
64.6 + 7.0
82.7 1 166
76.2 2 2.8
N0.2 = 1.9
75.1 4 5.1
52. 4: 1.8
92.4 :: 2.5
Kipt Wellne
62.7
71.1
GraphSALFF Famile
2017
85.1
76
63.9 +:
77.7 - 1.5
75.9
32
72.1 1
50.9 -
PSCN
Niceel a: 24116
92.6
4.2
60.0 + 4.8
78.6 -
75.9
2.8
72.6 - 2.2
71.0 11.0:10
2.2
45.24 2.8
86.3 = 1.6
CupsGNN
Xina Cen
2019
86.7 6.9
78.4 1: 16
76.3
2: 3.6
79.6 1:
73.1 1
50.3
00.3-:0 2.7
GCAPS.CKN
2018
77.7 +
71.3
48.5
87.6
JEGN
Maron Scol 20/50
84.5 10
59.5 1:
73.7 1: 2.6
75.2
4.3
77.9 3: 1.7
71.3 1
48.6 3.9
1-2:3 CNN Morrs el 2019
86.1
60.9
76.2
75.9
74.2
49.5
HaarPool Wing
90.0 3,6
78.6 +
0.8
8.7
66.2
81.4 +
730
GHC
Nguttn & Maziiom suee
89.3
8.5
72.1 + 26
48.6
Ring UNN
Cizcnet 2019
78.1 5.5
73.0 - 5.
48.2 0124-22 1:7
InfoCiraph
2019
61.6
4..7:005
82.5
CMV-GR (135501s Kiizahnadi
74.3 +
0.5
34.5
WT.
2011
577
$9.9
86.0
311
78.9
73.8 4
81.0
GK
Shervalliizee R.l. 2009
81.6
57.3
1.4
62.5
0.3
71.2 0.6
72.8
65.9 1 1.0
43.9 0:4
77.3 4: 0.2
DOK
Kimardii & Vishveniiamm
2015
874
2.7
60.1
1 2.6
80.3
1 0.5
15.7
0.5
73.1 1 0.3
67.0 0.6
44.6 0.5
78.0 + 0.4
W1-
Kingg 2016
84.5
1.7
63.6 +
86.1
1 0.2
76.4
0.4
80.7 2 0.1
89.3 2 0.3
Toyninalli
66.3
MLG
Konder & Pan 2010
87.9
1.5
63.3
+
1.5
81.8 4 0.2
76.3 0.7
66.6 4 03
41.2 0.0
Table 2: Accuracy for attributed graph classification in test set (%). Top performances on each dataset are bolded. The best performances are underlined.
ENZYMES
FRANKENSTEIN
PROTEINSaI
SYNTHETICnew
Synthic
lexe
67.00
=
77.99
1.77
97.67 +
95.75
71.50
7.01
73.12 2.59
77.27
3.67
99.00 :: 1.53
99.25
1.15
GIN-final
68.50
68.66
2.47
76.64
2.94
83.33 6.67
89.50
GCN (Kipf & Welling
2017
44,17 : 4,90
63.27 = 1.15
68.83
4.39
69.00
1: 7.00
49.25
: 7.59
HGK-SP Morns
71,30
70,06
77.47
0.43
94.34 10.54
HGK-
WL Morrs
2016
67.63 0.95
73.62
0.38
76.70
0.41
98.84 + 0.29
96.75
0.51
GIIK
[erragen el al 10
68.80 0.96
68.48 0.26
72.26
0.34
85.10
1: 1.04
73.18
1: 0.77
GIK
(Orsini
2015)
71.70
0.79
76.31 0.33
76.88
0.47
83.07
1.10
95.75
0.50
P2K [Scumann et di
2016
69.22 = 0.34
73:45
- 0.48
91.70 + 0.86
50.15
1.92
Togninalli
2019)
73.25
0.80
and social network datasets (COLLAB, MNDB-BINARY IMDB-MULTI, and REDDIT-BINARY)
(Yanardag & Vishwanathan 2015). For bioinformatics datasets, the categorical node labels are en- coded as one-hot input features; for social network datasets, because nodes have no given features, we initialize all node features to 1. The 5 attributed graph datasets contain 3 bioinformatics datasets (EN- ZYMES, FRANKENSTEIN, PROTEINSatt) and 2 synthetic datasets (SYNTHETICNEW, Synthie). More detailed information can be found in Appendix A.4 Table [
Baselines. We compared our model with a number of state-of-the-arr methods listed in the first simple graph classification and attributed graph classification, respectively, Besides GIN which inspired this work and the popular GCN (Kipf & WWeling 2017). we also include
column in Tanle
the recent studies on expressive power of GNNs, e.g., Ring-GNN (Chen et 2019). GHC Nguyen & Maehara 2020) and state-of-the-as methods on neighborhood aggregation, e.g., GraphSAGE (Hamilton et al.) 2017) and HaarPool (Wang et al. 2020p. For attributed graphs, few results on the benchmarks with deep learning methods are available in the literature. We are only aware of graph kernel related baselines, listed in the first columns Table We also compared iceGNN with our implemented GIN-final and GCN for attributed graph classification, both implemented by adjusting the corresponding official code.
Results. Table D and 2 list the classification accuracies on test set for simple graph classification and attributed graph classification, respectively. We highlight the top 3 accuracies for each dataset in boldface. From Table for simple graph classification bioinformatics datasets, iceGNN can achieve top 3 on all the 3 datasets except for NCI dataset where we achieve the best results among the deep learning models though. It seems that the graph kernel methods perform well on NCI1
7

---

Under review as a conference paper at ICLR 2023
18
140
16
14
(a) MUTAG (b) PTC
(c) NCI1
(d) Cora
Figure 2: The accuracy curves on training set in the training process.
datset. Especially, on the PTC dataset we achieve the best two performances, and improved 2 points compared to the past best. Although iceGNN can only achieve top 3 on REDDIT-BINARY dataset among the social network datasets, can provide acceptable results overall. From Table 2 for all the attributed graph datasets, iceGNN can achieve top in these 10 models, especially, NN-L places first on 3 datasets. Comparing iceGNN and GIN-final, iceGNN can consistently outperform GIN-final final except for iceGNN- fixed on ENZYMES dataset.
Performance on training set. To evaluate the expressive power, Figure a-c) illustrates accuracies in training sets in the training process on 3 datasets for graph classification. More results on other datasets can be found in Appendix 6 Figure We can see that iceGNN-MI.P on different datasets is able to fit the training sets perfectly and is better than GIN-final and iceGNN-fixed, specifically, L.GNN--LLPXieGNNNE
in terms of the expressive power. For MUTAG and PTC datasets, GIN in Xu et al. (2019) can fit the training set well, while GIN-final cannot, since GIN in [u et al. (2119) concatenates all the middle layer outputs as the graph embedding, it may be the reason that the final layer outputs of GIN may lose some information from middle layers.
GIN-Iial-GiinGGG
We are aware of that iceGNN has more parameters than GIN-final (Appendix A.. Table S). To identify whether the expressive power is just due to more parameters, enlarge GIN with 5 hidden layers in each MLP, so that the number of parameters achieve the same scale with iceGNN, denoting the GIN architecture GIN-m We found that GIN-mlp5 still cannot achieve the training accuracy as iceGNN or even worse than GIN-final, as shown in Figure 2 (a-c).
Recent GNN benchmarks. The recent work by Dwivedi al. (2020) proposed new GNN bench- marks by which we also test our model on their ZINC and MNIST datasets for graph regression and classification, respectively. To ensure a fair comparison, we followed their problem setting (data splits, optimizer, etc.) and GNN structure (number of layers, normalization). Our results together with some state-of-the-arr results from Dwivedi et al. (020)) are listed in Table From the results, we can see that iceGNN-MLL performs best on both ZINC and MNIST datasets among all the models, demonstrating its effectiveness.
Table 3: GNN performance ZINC dataset for graph regression and on MNIST dataset for graph classification. Top 3 performances each dataset are bolded. The best performances are underlined.
Table 4: Node classification results. G
is variant of GCNII from Chen et al. 2020))
Citeseer
Pubmed
Truining accuracy
ZINC
MNIST
ICGNN ML.
1.000 : 0.000
0.975 0.900-00000
#Param
Test MAE
#Param
Test Ace
ICGNN-fixed
0.998=0.004
0.990=0.011
0.904-20.053
ieIGNN-MIP
231049
0.2505
229140
97.340-10000
GIN-final
0.998 0.908=0.001
0.974=0.002
0.935=20.004
JeGNNN-fixed
252345
0.367=00.010
241568
96,490=0.11
GCN
0.977-10.002
0.946=0.003
0.841-00003
GCNI
0.675=00.009
0.596=0.011
0.844=0.003
GIN
103079
0.387-10.015
105434
96.85-10.255
GUNIP
0.679-20.012
0.609=0.010
0.852=0.004
GCN
505079
0.367=0.011
101365
90.705=0.218
GatedGCN
105735
0.405-L0.011
104217
97.340
Tost acouracy
GraphSage
505341
0.398-10.002
104337
97.312-00097
ICGNN-MLP
U.858 0.009
0.728=0.023
0.880
MoNet
504013
0.292=00.006
104049
90.805=0.033
ICGNN fixed
100025
0.720-0.025
0.872-10.02
GAT
531345
0.304
110400
0..5
GIN-final
0.010=000088
0.739=0.031
0.875=00009
RingGNN
97978
0.512.10.023
505182
91. 8.449
GCN
0 : 0.014
0.773 0.020
0.85910.007
3WLGNN
102150
0.407-10.022
108024
956075--0966
GONIT
0.006
0.728
0.869-10.002
PNA
0.300
07.000.00.080
GCNIT
0.852
0.736=0.004
0.880=20.003
8

---

Under review as a conference paper at ICLR 2023
5.2 NODE CLASSIHICATION
We use three popular citation network datasets Cora, Citeseer, and Pubmed (Sen et al. 2008 for semi- supervised node classification. The detailed information of the dataset summarized Appendix Table 7 We compared our performance with recent oafte-of-the-art, GCNII (Chen et al. 2020). Since the expressive power describes the ability of a model to discriminate different nodes, larger training set can reflect the expressive power better. Because the official splits have only few nodes in training, we split the nodes into training. validation and test sets by 8:1:1. The node classification results test sets listed in Table 4 where we found that iceGNNs and can outperform all other baselines on training set; especially on Cora and Citeseer dataset, iceGNNs achieve nearly 100% accuracy, suggesting iceGNNs have strong expressive ability. For test set, iceGNN-MLP performs better than all other models on Pubmed dataset. but does not perform that well on Cora and Citeseer datasets comparing GCN and GIN-final suggesting that iceGNN-MLP also has good generalization ability on Pubmed dataset rather than Cora and Citeseer datasets.
5.3 EXPRESSIVE CAPABILITY ANALYSIS
The expressive power describes how a model can distinguish different samples. Generally, highly expressive model will map different samples to different embeddings and similar samples to similar embeddings. For classification problem, an expressive model should make samples in the same class compact together and samples in different classes highly discriminative. Here, we fetch the output embeddings of GNN before feeding to the classifier, and visualize them to see if GNN can discriminate samples from different classes. Figure 3 shows the t-SNE visualization (Maaten & Hinton 2008) of output graph representations of different GNN models on training data of NCIT dataset. More visualization results can be found in Appendix AA.8) We can see that the output embeddings of iceGNN-MLP and iceGNN-fixed are discriminative on both datasets, and the less expressive GIN-final shows somewhat more overlaps between different classes, which validates the expressive capability of iceGNN.
(a) iceGNN-MLP
(b) iceGNN--ixeee
(c) GIN-final
Figure 3: t-SNE visualization of the output embeddings on training data of NCI1 dataset.
From the experimental results, we found that iceGNN-MLP often performs better than iceGNN- fixed. We identify two reasons could make iceGNN-MLP outperform iceGNN-fixed (1) By the discussion Section 4.2 iceGNN-MLP can also retain the graph label information. (2) iceGNN-fixed usually has a much higher dimension input to each GNN layer, thus more parameters to train, having high risk of encountering local optimum and plateau. This phenomenon also exists general MLP.
6 CONCLUSION
In this paper, we present a theoretical framework to design highly expressive GNNs for general graphs. Based on the framework, we propose two iceGNN variants with fixed transformation function and learnable transformation function, respectively. Moreover, the proposed iceGNN can naturally learn expressive representations for graphs with continuous node attributes. We validate the proposed GNN for graph classification and node classification on multiple benchmark datasets, including simple graphs and attributed graphs. The experimental results demonstrate that model achieves state-of-the -hht--art performances on most of the benchmarks. Future directions include extending the framework graph with continuous edge attributes.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformaties, 21(suppl_1): i47-i56, 2005.
Ming Chen. Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 2020.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4))303-311 -144, 1989.
Asim Kumar Debnath, Rosa I. Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In NeurIPS, pp. 9224-2232. 2015.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00990 2020.
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. Scalable 2013. Erratum available nips erratum. pp
kernels for graphs with continuous attributes. NeurlPS, pp. at utthtp::/ /tt////maae///// diku
Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. In ICLR, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML., pp. 1263-1272. JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pp. 4116-4126 PMLR, 2020.
Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformaties, 17(1):107-008, 2001.
Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448 456. 2015.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016.
tww.orruuuudd.ddddd.......... de
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. Proceedings of the 30th International Conference Neural Information Processing Systems, pp. 2990-2998, 2016.
10

---

Under review as a conference paper at ICLR 2023
Nils M Kriege, Pierre-Loute Giscard, and Richard C Wilson. On valid optimal assignment kernels and applications to graph classification. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 1623-1631, 2016.
Yifu Li, Ran Jin, and Yuan Luo. Classifying relations in clinical narratives using segment graph convolutional and recurrent neural networks (seg-gerns). JAMIA, 26(3):262-268, 2018.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9(oov):5579-2605 2008.
Nathaniel Macon and Abraham Spitzbart. Inverses of vandermonde matrices. Mathematical Monthly, 65(2):95-100, 1958.
The American
Chengsheng Mao, Liang Yao, and Yuan Luo. Towards expressive graph representation. arXiv preprint 20XY:22010.05427, 2020.
Chengsheng Mao, Liang Yao, and Yuan Luo. Imagegen: Multi-relational image graph convolutional networks for disease identification with chest x-rays. IEEE Transactions on Medical Imaging. 2022a.
Chengsheng Mao, Liang Yao, and Yuan Luo. Medgen: Medication recommendation and lab test imputation via graph convolutional networks. Journal of Biomedical Informatics, pp. 104000, 2022b.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurlPS, pp. 2156-2167, 2019a.
Haggai Maron, Heli Ben Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In ICLR, 2019b.
Christopher Morris, Nils M Kriege, Kristian Kersting, and Petra Mutzel. Faster kernels for graphs with continuous attributes via hashing. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 1095-1100. IEEE, 2016.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gauray Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning. 102(2):209-245, 2016.
Hoang Nguyen and Takanori Machara. Graph homomorphism convolution. In International Confer- ence on Machine Learning, pp. 7306-7316. PMLR, 2020.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In ICML, pp. 2014 2023, 2016.
Francesco Orsini, Paolo Frasconi, and Lue De Raedt. Graph invariant kernels. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
Hao Peng, Jianxin Li, Yu He, Yaopeng Liu, Mengjiao Bao, Lihong Wang, Yangqiu Song, and Qiang Yang. Large-scale hierarchical text classification with recursively regularized deep graph-cnn. In WWW, pp. 1063-1072, 2018.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, pp. 485. 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kemnlss JMLR, 12($5p):253--256,, 2011.
11

---

Under review as a conference paper at ICLR 2023
Fan- Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. ICLR, 2019.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-Lóper Bastian Alexander Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lchman graph kernels. Advances in Neural Information Processing Systems 32, pp. 6439-6449, 2019.
Saurabh Verma and Zhi-Li Zhang. Graph capsule convolutional neural networks, arXiv preprint arXiv: 000.88000000000. 2018.
Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Ingmar Posner, and Michael Osborne. On the limitations of representing functions sets. In /CML, 2019.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Yu Guang Wang, Ming Li, Zheng Ma, Guido Montufar, Xiaosheng Zhuang, and Yanan Fan. Haar graph pooling. In ICML., pp. 9952-9962. PMLR, 2020.
Boris Weisfeiler and Andrei A Lehman. reduction of a graph to canonical form and an algebra arising during this reduction. Nauchno- Teehhhhe-Teehhniihekkaya Informatsia, 2(9):12-16) 16, 1968.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In ICLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In ACM SIGKDD, pp. 1365-1374. ACM, 2015.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In
AAAI, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovee. Graph convolutional neural networks for web-scale recommender systems, In ACM SIGKDD, pp. 974 983. ACM, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurIPS, pp. 4800-4810, 2018b.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In NeurlPS, pp. 3391-3401, 2017.
2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, 2018.
12

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1
COMMON NOTATIONS USED THROUGHOUT THE PAPER
Table 5: Common notations used throughout the paper.
Notation
Definition
R
the set of all real numbers
N
the set of all natural numbers the concatenation of vectors X X
[x
x..
(v)
the vector representation of node in the kth layer the neighborhood of node e in a graph
N(v)
x(i]
the ith entry of vector
x(i:
the subvector of x between index and j (including)
13

---

Under review as a conference paper at ICLR 2023
A.2 PROOF OF THEOREM 2
Theorem Assume AM is a sei of finite subsets of IRd with size less than or equal to M, i.e., for M ENN and XMs = {X Rd, ||| M), there exists an infinile number of continuous functions 4 Rd -R RDD such that the set function f XM + IR,, S(X) = =xxex (x) is continuous and injective.
Proof. We prove the theorem by three steps, 1. constructing satisfying function ((x) in one dimensional cases (d = 1); 2. constructing satisfying function & (x) in multi-dimensional cases (d > 1); 3. The number of the satisfying functions is infinite.
One dimensional cases (d 1):
In one dimensional case, the theorem can be easily proved by extending the following lemma from Zaheer et al. (2017).
Lemma. Lef X ((x1,... ,IM) E (0, 1jM I22 S ... S J.M. The sum-of-power mapping
E: X M++1 defined by the coordinate functions
E(X) = E1) .. (M) =
Σ LEX
Z,
Σ IM mEX
(12)
TEX
is injective.
In Zaheer al. (201)) this lemma is proved based the famous Newton-Girard formulae, where the domain X' can be extended to Xas = [X] X C R. [X] S M, M. E N} with the same proof process. [ is the number of elements in X, Egg (X1) Eg (X2) implies equal
Because (X) Σxex
set size between the two sets, it can be easily extended Xs {X X R, X s M, M N).
Exexa"1 ExEx [1, x. .. Let ((x) [1, v....... x obviously (xx) is continuous, thus, we get one (XX) such that f(X) ΣxEx ((x) injective and continuous.
Since F(X) [Exex 1, E, z.....
2. Multi-dimensional cases (d 1):
For a d-dimensional vector x and a integer M, we define
(x; M) =
x x[]]?x] ... M
(13)
where i,j E [L, d]. x[i] is the ith entry of
For given i E [1, d]. define t; Rd + (dM+1)) +x M) = [1, P..,,... Pi.a), we will prove that (x; .M) can meet the condition that f(X) Exex (x M) is injective and continuous X.
x(i] is distinct for
We only consider (x; .). for i = 2. d, the situations are similar. For a clear understanding, reshape 4 (x; M) to d rows similar to matrix, like
1,x[1), x[1]2....
x[1] M x[1] M
x[2], x[1]x(2).....
x(2]. [[(2).
(x;
(14)
x[d]. x[]]x[d],....
x[1]a1-1x(()
For (dm + 1)-dimensional vector V from the image domain of X'M through f(X)
Exex (x; M), we will identify the number of the preimages of V.
Let X a preimage of V. we have the following equation which exactly equation group with dM equations.
ExEx 1, Exex x(1,, Exexx x(2],
ExEx x(1]2
Exex x[1] Exex x
ExEx x(1]x[2].
=
(15)
Exexx(ox
ExEx ExExx(1|x(1)) x([]x[[]]
ExEx x(1]M-1xx(0)
14

---

Under review as a conference paper at ICLR 2023
Note that the first of Eq. [5 is exactly the sum-of-power mapping considered in one dimensional cases, thus we can identify a unique set of the first entry of elements X, and the number of elements in X is also determined. Let X have M elements and X X2, ;MM)) the set [x1 X2 x2(1], ... XM [1]} is uniquely defined.
Consider the second row of Eq. 15 we can rewrite the equations in the second row linear matrix equation as Eq. 16
X1 [2]
X1 [1]
X2
xM[
X1 [1]
X2
[1]
[M
X2
V[2,
(16)
Xx [2]
Xx [1] (M
X2 x2[1] (-]])
XM [M (1](ar11)
Note that the coefficient matrix in left side of Eq. 16 a Vandermonde matrix, the x₃ i1...... ... xM
all distinct, the coefficient matrix is invertible (Macon & Spitzbart 1958). Eq. 16 has a unique solution for X1 [2]. ... XM corresponding to x1 [1, [J.... XM Similarly, by the ith (2 < i d) row of Eq. 15 x1]1].
XM can be uniquely identified.
In the other case, if the x1[1], ... XM[ that solved from the first row of Eq. 15 are not all
distinct, Eq. 16 has infinitely many solutions. o(x) defined by Eq. [4 is not sufficient to make
f(x)= = Exex (xx) injective. We need some more dimensions appended in o(x).
Let X1 [1] = x2 = =...= xk[1], then by combining the items, Eq.
16 is shrinked to
1
1
Σ E xi [2 X [2]
Xk [1
X
XM
Xk 11
Xk+1
XM
[1]
V|2
(17)
XM [2]
X4x (1]
Xk+1 [1] (M))
By solving Eq. tify unique set
17
we have
a unique sum Eist.. x|
To iden- unique
of
{x1
Σ - (2 xx[2]] we
2
x2 [2].
can
define can add
Eis x; [2]2 1 X3 [2]
we
items
[ x
x to ((x) to uniquely identify E x [2]2
Similarly, add items x2]xxx x[[]'x[2]* ... x[1]____XXXX to 4(x) to uniquely identify Σ.=1.. 12 Thus all x2 are identified.
After the set (x1 [x1[2), x2[2]] (....... (2(() is uniquely defined, by adding x(2) ........ M
j.j = 3, .....d 3. d) to (xx), we can use x1 to construct a Vandermonde matrix to solve
3 x gjd].
1,... M). xf 2] are not all distinct, can identify x[[3] similarly by adding x [33 to (xx). By this way, the set X can be uniquely identified.
In our construction of $ (xx), all the functions are continuous, thus, there exists continuous function (xx) such that f(X)= = Exex ((x) is injective and continuous.
The number of the satisfying function infinity:
To prove the number of this kind functions is infinity, we construct a continuous injective function g R > R. we will show that if we have a Φ(x) satisfying the condition f(X) = ExEx ((x) continuous and injective, then d(((x)) also satisfy the condition f(X) Exex ((g(x) is continuous and injective.
We define function h : X X, M(X) {g(x))x E X), since g(x) is injective, h(X) is also injective. If we have function (xx) such that f(X) = ExEx @(x) is injective, f f(h(X) is injective.
S(h(X)) Σ (xx)
Σ x(x) Σ ((((x))
(18)
XEA(X)
xx(
XEX
Because ((x) and g(x) are both continuous, ((g(x)) )x is continuous, thus we find another function ((g(x)) such that Exex Φ(g(x)) injective. Because we can have an infinite number of such continuous injective functions g Rd + Rd (e.g., g(x) = kx, E R), we have a infinite number of such functions (xx) ((g(x)) such that f(x) Exex +(x) is injective.
15

---

Under review as a conference paper at ICLR 2023
A.3 PROOF OF THEOREM 3
Theorem 3 Let M E N and X' = {XXX C E. |X|
M). then for any continuous function
4 Rd R., N dM, the set function x EN f(X) -Exex o(x) injective.
Proof. Suppose f(X) is injective. Because (xx) is continuous, f(X) is finite sum of continuous function, it is also continuous, thus, f(X) is continuous and injective.
All sets X have M elements from Rd. In one dimensional cases 1), has bijection to S = (X = (z1, , X E R S 22 S ... S aar).
In multi- Iulti-dimeenional cases (d 1), we can construct a bijection from X S (X
(x1 xM) E IRMM 1] < x2 S < [M(1]. if x; k) = x k). x; + < X1+1 [k: + 1, M 1, I,.... d For X, let = (x1, XMM). we can sort elements in X by the first entry, for the elements whose first entries are equal, sort them by the second entry, so repeatedly this way, we get final ordered sequence of the vectors, which is unique in S.
Note that S is convex open subset of RdM and is therefore homcomorphic to RdM Since N < d., no continuous injection exists from RdM to RRN. Thus no continuous injective function exist from X to IR Hence we have reached contradiction.
16

---

Under review as a conference paper at ICLR 2023
A.4 DATASET DETAILS
The dataset information is in Table 6 and
Table 6: Dataset information for graph classification. All datasets available from Kersting et al. (001)). #G=number graphs. #C=number classes. #NC=number of node types. AvgN=average number of nodes in one graph. AvgE=average number of edges in one graph. Dim=node attribute dimension. MaxNb is the max 1-hop neighbors in all the nodes.
AC
ANC
AvgN
AvgF:
MaxNh
Dim
Type
Source
19.79
bisinformatics
Debmath
PTC
344
2
19
14.29
14.69
4
bioinformatics
Helma el al
100
2
29.87
32.30
bioinformatics
Walt cr
PROTEINS
1113
2
39.06
72.82
25
bioinformatics
2005
COLLAB
5000
3
74.49
2457.78
491
social networks
Yanardag & Vishwanahhn
2015
IMDB-B
1000
2
96.53
135
social networks
IMDB-M
1500
3
13.00
65.94
88
social networks networks
Tanardag & Valtwanallann
2013
3062
Yanardig
ENZYMES
6U0
32.63
62.14
18
bioinformatics bioinformatics
Borrwardt et al 2005
FRANKENSTEIN
4337
2
16.90
17.88
4
780
Oraan 201
PROTEINS-att
1113
2
39.06
72.82
25
bioinformatics
Horyward ai 2005
SYNTHETTCnew
synthetic
Teragen
Synthie
400
4
95.00
172.93
20
15
synthetic
Morrs
2016
Table 7: Dataset information for node classification.
#Nodes
#Edges
#Classes
Dim
MaxNb
Source
cora
2708
5429
1433
168
Sen al.
2008
Kipf Welling
2017
citeseer
3327
4732
6
3703
99
Sen al.
2008
Kipl & Welling
2017
pubmed
19717
44338
3
500
171
Sen al.
2008
Kipf & Welling
2017
17

---

Under review as a conference paper at ICLR 2023
A.5 IMPLEMENTATION DETAILS
We implement 2 iceGNN variants: (1) iceGNN-fixed, where fixed transformation functions in all as (x) (x) in Eq. (4) in the main paper; (2) iceGNN-MLP, where the transformation functions in all layers are set as a learnable MLP. Since for simple graph with one- hot node features, the summation with identical transformation injective, we set whether the transformation function in the first layer is identical or an MLP as an optional hyperparameter for simple graph classification. For social network datasets, the max neighborhood size too large that fixed transformation function will produce large hidden dimension, we do not implement fixed transformation function. Also, because the nodes have no initial features in the first layer. We also implement GIN with the output of the final layer as node embeddings to sum to graph embedding, denoted as GIN-final.
layers
The two iceGNN variants and GIN-fina finallialllla implemented with 5 layers, all MLPs in iceGNN have 2 layers. Batch normalization Loffe Szegedy (2015) is applied in every hidden layer (including GNN layer and MLP layer) followed by ReLU activation function. We use the Adam optimizer Kingma & Ba (2015) with a initial learning rate and decay the learning rate by 0.5 every 50 epochs. The batch size is 32, dropout layer applied. The search space of hyper-parameters
tuned for each dataset are: (1) The number of hidden units {16, 32, 64]; (2) the inital learning rate 0.01, 0.001; (3) for the 4 bioinformatic simple graph datasets, the transformation function in the first layer is identical or MLP; (4) For IceGNN-fixed the transformation function is tuned with Das (x) or D' (x) in Eq. (4) in the main paper. For each dataset, we follow the standard 10-fold cross validation protocol and use the same splits with Xu et al. (011)). Following the previous work Xu et al. (2019): Maron et al. (2019)); Mao et al. (2020), we reported the best averaged validation accuracy across the 10 folds for a fair comparison. All models are trained 300 epochs. To evaluate the expressive capability, we also record the average training accuracy across the 10 folds of iceGNNs and Gin-final in each epoch.
All the experiments were run in 10 Tesla V100 GPUs with pytorch.
18

---

Under review as a conference paper at ICLR 2023
A.6 ADDITIONAL RESULTS
The accuracy curves on training set in the training process on more datasets are shown in Figure 4 where Figures 4a are for graph classification and Figures 4] are for node classification.
(a) PROTEINS
(b) COLLAB
(C) IMDBBINARY
(d) IMDBMULTI
(c) RDTEB
(f) ENZYMES
(g) FRANKENST
(h) PROTEINSat
ii SYNTHETICnew
(i)
Synthie
(k) Pubmed
(l) Citeseer
Figure 4: The accuracy curves on training in the training process, All the models have hidden dimension 16.
19

---

Under review as a conference paper at ICLR 2023
A.7 MODEL SIZE
Table 8 lists the comparison of number of trainable parameters in different models on different datasets. GIN-mlp(nn) the numbers in parentheses for different datasets are the number of layers in an MLP. GIN-mlp(n) is implemented to enlarge the GIN model to the same parameter scale with iceGNN-MLP to make fair comparison of expressive power. All the models have hidden dimension 16, GIN-mip(n) is GIN model where all MLPs are implemented with layers. Since iceGNN-fixed cannot be implemented with large MaxNb (MaxNb defined Tables and 77) the transformation functions in iceGNN-fixe f-xed are set as 4. (x) (defined in Eq. (5) in the main paper). The results show that, iceGNN more expressive than GIN on most of the datasets, and the expressive power of iceGNN comes from the injective and continuous aggregation scheme rather than the number parameters.
Table 8: Number of trainable parameters of different models on different datasets. All the models have a hidden dimension 16.
models
iceGNN-fixed
iceGNN-MLP
GIN-final
GIN-mlp(n)
GCN
MUTAG
8,706
8,574
4,256
8,816(5)
978
PTC
9,666
9,006
4,472
9,032(5)
1,170
NCII
11,106
9,654
4,796
9,356(5)
1,458
PROTEINS
8,226
8,430
4,184
8,744(5)
914
COLLAB
8,227
7,815
4,213
8,773(5)
899
IMDBBINARY
8,162
7,750
4,148
8,708(5)
882
IMDBMULTI
8,227
7,815
4,213
8,773(5)
899
REDDITBINARY
8,162
7,750
4.148
8,708(5)
882
ENZYMES
10,086
9,338
4,768
9,328(5)
1,270
FRANKENSTEIN
70,546
36,402
18,170
37,930(15)
13,346
PROTEINSatt
34,892
8,466
4,202
8,762(5)
930
Synthie
9,476
8,992
4,530
9,090(5)
1,140
SYNTHETICnew
8,226
8,358
4,148
8,708(5)
882
20

---

Under review as a conference paper at ICLR 2023
A.8 VISUALIZATION
The graph embedding output from the final layer of GNNs on some other datasets is visualized with I-SNE (Figures 8
(a) iceGNN-MLP
(b) iceGNN-fixed
(c) GIN-final
Figure 5: 1-SNE visualization of the output 16-dimensional graph embeddings on training data of FRANKENSTEIN dataset.
(a) MMPP
(b) iceGNN-fixe fixed
(c) GIN-final
(d) GCN
Figure 6: 1-SNE visualization of the output 16-dimensional node embeddings on training data of Citeseer dataset.
(a) iceGNN-MLP
(b) iceGNN- fixed
(c) -iN-final
(d) GCN
Figure 7: 1-SNE visualization of the output 16-dimensional node embeddings on training data of Cora dataset.
(a) iceGNN-MLP
(b) iceGNN-fixed
GIN-final
(d) GCN
Figure 8: 1-SNE visualization of the output 16-dimensional node embeddings on training data of Pubmed dataset.
21

---

Under review as a conference paper at ICLR 2023
A.9 HYPER-PARAMENT PARAMETER SETTING
For the reproducibility. Table 9 provides the hyper-parameters to achieve the results of iceGNN in Table and in the main paper, and the code also attached with this file. For the social network datasets, since MaxNB is too large to implement iceGNN-fixed, we only implement iceGNN-MLA Since all nodes are of the same type, identical transformation function in the first layer applied. For attributed graphs, to preserve injective and continuous, the transformation function in the first layer identical. The results of ieeGNN, GIN and GCN in Table the main paper achieved syper-parameters in Table [0] and all the learning rates are 0.01. The hyper-parameters of GCNII and GCNII* are the same as the official code hhttps:/ the hidden dimensions are 64, 256, 256 for Cora, Citeseer and Pubmed, respectively,
com/ ctt.cheennnccceeeeeeeeee GCNII), where
Table 9:
The hyper- parameters corresponding the results of iceGNN in Table and in the main paper. h=hidden dimension; Ir=learning rate; TF=transformation function; Fl=whether to apply identical tramsformation function for the first layer.
dataset
model
h
lr
FI
TF
MUTAG
iceGNN-fixed
16
0.01
FALSE
$
iceGNN-MI.P
16
0.01
FALSE
MLP
PTC
iceGNN-fixed
16
0.001
TRUE
iceGNN-MLP
16
0.001
FALSE
MLP
NCII
iceGNN-fixed
64
0.001
TRUE
iceGNN-MPP
16
0.001
TRUE
MLP
PROTEINS
iceGNN-fixe
64
0.001
TRUE
'
iceGNN-MLP
64
0.01
TRUE
MLP
COLLAB
iceGNN-MLP
64
0.001
TRUE
MLP
IMDB-B
iceGNN-MIP
16
0.01
TRUE
MLP
IMDB-M
iceGNN-MI.P
16
0.01
TRUE
MLP
RDT-B
iceGNN-MLP
16
0.01
TRUE
MLP
ENZYMES
iceGNN-fixed
64
0.001
FALSE
T
iceGNN-MLP
64
0.001
FALSE
MLP
FRANKENSTEIN
iceGNN-fixed
32
0.001
FALSE
iceGNN-MLP
16
0.001
FALSE
MLP
PROTEINSatt
iceGNN-fixed
16
0.001
FALSE
T
iceGNN-MLP
64
0.01
FALSE
MLP
SYNTHETICnew
iceGNN-fixed
64
0.01
FALSE
T
iceGNN-MI.
64
0.01
FALSE
MLP
Synthic
iceGNN-fixed
64
0.01
FALSE
iceGNN-MLP
32
0.01
FALSE
MLP
Table 10: The syper-parameters corresponding to the results of iceGNN in Table 4 in the main paper. h=hidden dimension; TF=tranfformation function; Fl=whether to apply identical transformation function for the first layer.
dataset
model
h
Ir
FI
TF
drop out rate
weight decay
Cora
iceGNN-fixed
128
0.01
TRUE
0
0.01
icPGNN-MLP
128
0.01
TRUE
MLP
0.6
0
Citesser
iceGNN-fixed
128
0.01
TRUE
4
0
0.01
iceGNN-MLP
128
0.01
TRUE
MLP
0.6
0
Pubmed
iceGNN-fixed
16
0.01
TRUE
0
0.01
iceGNN-MLP
16
0.01
TRUE
MLP
0.6
0
22


Reviews:
[{"review_id": "idJQ7xrjjlr", "reviewer": "Reviewer_EYLv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper investigates GNNs' expressive power. That is, building on the work of Xu et al. (2019) and Morris et al. (2019) it proposes injective and continuous aggregating functions used within GNNs. Specifically, the paper argues that both injectiveness, as well as continuity, is needed to compute meaningful graph and node representations. To that, the paper proposes a simple injective and continuous function for multisets by building on results by Zaheer et al. (2017). Moreover, they derive sufficient conditions for injectivity. \n\nThe theoretical results are complemented with an empirical study, showcasing the benefits of the new aggregation function on a number of standard benchmark datasets. ", "summary_of_the_review": "This is a well-written paper with somewhat interesting theoretical results and a decent experimental study. I have some doubts about the novelty of the theoretical results. That is, prior works already seem to solve the problem of infectivity and continuity.", "strength_and_weaknesses": "**Strength**\n- Paper is well presented and easy-to-read\n- Good empirical results, good experimental study \n- Theory seems, to some extent, align with experimental results  \n\n**Weaknesses**\n- Not clear enough, if existing works already solve the problem of infectivity and continuity; see below \n- Some weaknesses in the experimental protocol; see below \n\n**Questions**\n- Why is the function considered by Xu et al. (2019) not continuous? To the best of my knowledge, it is a composition of continuous functions. \n\n\n**Suggestions/Remarks**:\n- The simple layer proposed by Morris et al. (2019) is already injective *and* continuous.\n- You assume a finite subset of $\\mathbb{R}^d$. Hence, it is countable and can be handled by the approaches of Morris et al. (2019) or Xu et al. (2019) \n- Make more clear that you deal with multiset functions and not set functions\n- In the abstract, you claim \"to improve the expressive power of GNN\". However, existing works, e.g., Xu et al. (2019), are already maximal expressive.\n- Page 2: Corso et al. (2020) does not increase the expressivity of GNNs\n- In the experiments, it would beneficial to also include larger datasets from OGB or TUDataset with continuous node features. The used datasets are rather small \n- The choice of reporting validations set performance is questionable even if other papers have done so in the past.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gQeyuTLEvy7", "reviewer": "Reviewer_eUaW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper identifies the problem of non-injective functions when the dimensions of intermedia representation vectors are not enough. It proposes a new expressive GNN model with an emphasis on the injectivity and continuity of set functions. ", "summary_of_the_review": " This paper provides a practical method to construct injective aggregation functions and solid theoretical analysis. However, I have concerns about the novelty of the proposed solution. I may raise my rating if my concern is resolved.", "strength_and_weaknesses": "Strengths:\n1. The theoretical analysis of the GNN and the injective functions are built on solid foundations,\n2. This paper gives a practical method to construct injective aggregation functions.\n3. The presentation logic is clear.\n\nWeaknesses:\n1. The experiments on node classification are not comprehensive enough. The three citation network datasets are rather toys, and the baselines are limited. More experiments on more datasets and baselines are expected. (Minor: Typo in Table4, ICGNN->iceGNN?)\n2. My main concern is about the novelty. Considering the learnable variant of the aggregate function designed in this paper, it seems very similar to the original solution in [1], which resorts to an MLP (the universal approximation theorem) to model $f \\circ \\phi$ to get injective $\\phi$.\n\n[1] How Powerful are Graph Neural Networks?, Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka, ICLR 2019", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5HEL11WR30x", "reviewer": "Reviewer_84dJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an aggregation framework (set representation) which can lead to both injective and continuous GNN node embedding even if raw node features are from conintuous space rather than countable space.", "summary_of_the_review": "This paper focues on both injectivity of continuity of GNN (set) representations on continuous space which is lack of formal studies.\nAlthough this paper provides an interesting finding of requirement for such representation, the other parts including proposed methods and experinmental results does not give enough contribution.", "strength_and_weaknesses": "## Strength\n\n- This paper shows that there is no way to continuously embed a $M$-size set whose elements are from $R^d$ into less than $Md$ dimension with injectivity. I think formally claiming this is useful.\n\n## Weakness\n\nThe significance of this paper is limited.\n\n- This paper proposes an injective and continuous set representation in Eq (5) for $M$-size set with $R^d$ elements, and the final representation is $Md$ dimension. However, if we simply sort all elements in the set, and concatenate sorted elements together as a $Md$ vector, I believe this is also an injective and continuous set representation. Then, is there any significant benefit to use Eq (5)?\n- From the experiment results, it seems that iceGNN-fixed is not feasible or worse than iceGNN-MLP in half of the cases, and improves slightly than iceGNN-MLP in the remaining half. It seems that injectivity is not very important in practice, but it is a key factor used to blame other models, e.g., GIN.\n- Your iceGNN-fixed looks like a slight variant of EdgeConv which you can easily find in PyTorch Geometric library, thus I think the novelty of this is limited. Besides, it will be better to have GAT results.\n- It will be a lot better if you can provide theory to study how dimension reduction hurts the injectivity and continuity since feature reduction is very common in real world applications.\n\nSome statements are not precise.\n\n- In the theorem 2, the definition of capital $D$ is missing. It is neither provided in appendix. Indeed, in the proof, the value of $D$ is different for different cases.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2Z-pw7qsvg", "reviewer": "Reviewer_Bsrk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work tackles the problem of using a injective and continuous set function as a neighborhood aggregation scheme in GNNs. The authors prove that such a construction exists (by extending some results from DeepSets) and how it would look like in GNNs. Finally, they present the practical benefits of such design in a set of benchmark tasks for graph learning.", "summary_of_the_review": "At this point in the graph learning literature it's hard to accept a paper evaluated only on the TUDataset, Planetoid and ZINC benchmkarks. These were used five years ago and the field has progressed since then. I recommend that the authors take a look at OGB and compare against the baselines that are highly ranked there. Further, I recommend the authors elaborate a result for the gap between their theory and their architecture. My recommendation is thus a result of these weaknesses outweighing the paper's strength.", "strength_and_weaknesses": "---Strength---\na) The problem tackled is relevant and few previous works have tried to address it.\nb) As far as I was able to follow and check, all proofs and theoretical contributions hold.\nc) The paper is well written and clarity is a strength.\n\n\n---Weaknesses---\na) I'm not sure to what extent the changes in the functions proposed by the authors impact their own results, i.e. the functions in 4.2 vs the ones from the theorems. If it doesn't impact, which I'm pretty confident it's not true, then the authors should present the theory matching them. If it doesn't at least we would need to evaluate what's then the actual benefit of using their architecture.\nb) The datasets used to evaluate the method are not sufficient to understand whether it outperforms existing solutions or not. We would need to see the method compared against more baselines, e.g. recent higher-order GNNs, in larger datasets, e.g. open graph benchmark (OGB).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject