A Simple and General Graph Neural Network with Stochastic Message Passing
Authors: Ziwei Zhang
Chenhao Niu
Peng Cui
Bo Zhang
Wei Cui
Wenwu Zhu
Venue:  (2021)
Keywords: Graph Neural Network
Node Proximity
Permutation-equivariant

Abstract: Graph neural networks (GNNs) are emerging machine learning models on graphs. One key property behind the expressiveness of existing GNNs is that the learned node representations are permutation-equivariant. Though being a desirable property for certain tasks, however, permutation-equivariance prevents GNNs from being proximity-aware, i.e., preserving the walk-based proximities between pairs of nodes, which is another critical property for graph analytical tasks. On the other hand, some variants of GNNs are proposed to preserve node proximities, but they fail to maintain permutation-equivariance. How to empower GNNs to be proximity aware while maintaining permutation-equivariance remains an open problem. In this paper, we propose Stochastic Message Passing (SMP), a general and simple GNN to maintain both proximity-awareness and permutation-equivariance properties. Specifically, we augment the existing GNNs with stochastic node representations learned to preserve node proximities. Though seemingly simple, we prove that such a mechanism can enable GNNs to preserve node proximities in theory while maintaining permutation-equivariance with certain parametrization. Extensive experimental results demonstrate the effectiveness and efficiency of SMP for tasks including node classification and link prediction.

Under review as a conference paper at ICLR 2021
A SIMPLE AND GENERAL GRAPH NEURAL NETWORK WITH STOCHASTIC MESSAGE PASSING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are emerging machine learning models on graphs. One key property behind the expressiveness of existing GNNs is that the learned node representations are erty for certain tasks, however, cennutation-equvvriinn being proximity-aware i.c., preserving the walk- proximities between pairs of nodes, which is another critical property for graph analytical tasks. On the other hand, some variants of GNNs are proposed to preserve node prox- imities, but they fail to maintain permutation-cquiiariann GNNs to be proximity-aware while maintaining permutation-equivaiiinn mains an open problem. In this paper, we propose Stochastic Message Passing (SMP), general and simple GNN to maintain both proximity-awarent and permutation cetiiooninuivvviinnnee properties. Specifically, we augment the existing GNNs with stochastic node representations learned to preserve node proximities. Though seemingly simple, we prove that such a mechanism can enable GNNs to preserve node proximities in theory while maintaining tain parametrization. Extensive experimental results demonstrate the effectiveness and efficiency of SMP for tasks including node classification and link prediction.
cuuiiaatioon-euuvviiiinnn Though being a desirable prop-
prevents GNNs from
6
How to empower re-
10
12
14
15
crmmuttaiio-equivrriaann
with cer-
16
17
INTRODUCTION
19
Graph neural networks (GNNs), as generalizations of neural networks in analyzing graphs, have attracted considerable research attention. GNNs have been widely applied various applications
20
21
such as social recommendation (Ma et al. 2019). physical simulation (Kipf et al. 2018), and protein interaction prediction (Zitnik & Leskovee 2017
22
23
One key property of most existing GNNs is ceauuuttiion-qquvaiiinncc. i.c., if we randomly permu- tate the IDs of nodes while maintaining the graph structure, the representations of nodes in GNNs are permutated accordingly. Mathematically, permuiation-equivariani
24
25
reflects one basic symmet- 26 ric group of graph structures. Although is desirable property for tasks such as node or graph classification (Keriven & Peyré. 2019; Maron et al. 2019b), pernutaaion-equivariaaee also prevents GNNs from being proximity proximity-aware, i.e., permutation eeqiivariiuuiaiitni GNNs cannot preserve walk based proximities between nodes such as the shortest distance or high-order proximities (see Theorem D
28
30
Pairwise proximities between nodes are crucial for graph analytical tasks such as link predic- tion (Hu et al. 2020: You al. 2019). To enable proximity-aware GNN, Position-aware GNN (P-GNN) You et al. 2019 proposes a sophisticated GNN architecture and shows better perfor- mance for proximity aware tasks. But P-GNN needs to explicitly calculate the shortest distance be- tween nodes and its computational complexity is unaffordable for large graphs. Moreover, P-GNN completely ignores the permuuation-eqquivaiaanee property. Therefore, cannot produce satisfactory results when commutationeqqiiariinn is helpful.
31
32
34
35
38
37
In real-world scenarios, both proximity- awareness and properties for GNNs. Firstly, different tasks may require different properties. For example, recom- mendation applications usually require the model be proximity-awan (Konstas al. 2009) while
are indispensable
38
39
40
permutation permutation-equiiarriancc is basic assumption in centrality measurements (Borgatti) 2005). Even
In You et al. 2019), the authors consider the special case of shortest distance between nodes and name such property as "positionawware" In this paper, consider more general of any walk-based proximity.

---

Under review as a conference paper at ICLR 2021
41
for the same task, different datasets may have different requirements on these two properties. Taking link prediction as an example, we observe that permutation euuitiironnniivinnntt GNNs such as GCN (Kipf & Welling 2017) or GAT (Velickovic al. 2018 show better results than P-GNN in coauthor graphs, but the opposite in biological graphs (please see Section for details). Unfortunately, in the current show in Theorem [
42
43
44
GNN frameworks, these two properties are contradicting,
Whether there remains
48
exists general GNN to be proximity-aware while maintaining permutation-cquivariae an open problem.
47
48
In this paper, we propose Stochastic Message Passing (SMP), a general and simple GNN to pre- serve both proximity-avarenee and cemmutation-euuvvriiaan properties. Specifically, we augment the existing GNNs with stochastic node representations learned to preserve proximities. Though seemingly simple, we prove that our proposed SMP can enable GNNs to preserve walk-based prox- imities in theory (see Theorem 22 Theorem 3 Meanwhile, SMP is equivalent to permutation- equivariant GNN with certain parametrization and thus at least as powerful as those GNNs in permutation-cquivariaa tasks (see Remark D. Therefore, SMP is general and flexible in handling both proximity-awan and permutation -qquivarinn- tasks, which is also demonstrated by our exten- sive experimental results. Besides, owing to the simple structure, SMP is computationally efficient, with a running time roughly the same as those of the most simple GNNs such as SGC (Wu et al.) 2019) and is at least order of magnitude faster than P-GNN on large graphs. Ablation studies 58
49
50
51
52
53
54
55
57
59
further show that a linear instantiation of SMP is expressive enough as adding extra non-linearities
60
does not lift the performance of SMP on the majority of datasets. Our contributions are as follows.
81
We propose SMP, a simple and general GNN to handle both proximity aware and permutation- equivariant graph analytical tasks.
63
We prove that SMP has theoretical guarantees in preserving walk-based proximities and is at least as powerful as the existing GNNs in permutation-equivariae tasks.
64
65
Extensive experimental results demonstrate the effectiveness and efficiency of SMP. We show that a linear instantiation of SMP is expressive enough on the majority of datasets.
66
67
2
RELATED WORK
68
We briefly review GNNs and their permutaaionn-euuivrriaate equivariance and mroximity-awarenee property.
69
The carliest GNNs adopt recursive definition of node states (Scarselli et al.] 2008 Gori et al.
70
2005) or contextual realization (Micheli) 2009). GGS-NNs (Li et al. (016) replace the recursive
71
definition with recurrent neural networks (RNNs). Spectral GCNs (Bruna et al. 2014) defined graph convolutions using graph signal processing (Shuman et al. 2013 Ortega et al. (0188) with Cheb- Net (Defferrard et al. 2016) and GCN (Kipf & Welling 2017) approximating the spectral filters us-
72
73
74
ing a K -order Chebyshev polynomial and the first-order polynomial, respectively. MPNNs (Gilmer et al., 2017), GraphS (Hamilton et al., 2017). and MoNet (Monti et al. 2017) are proposed as general frameworks by characterizing GNNs with message- paaiiggge-singggggo function and updating function. More advanced variants such as GAT (Velickovic et al. (208)), JK-Nets (Xu et al. 2018b). GIN (Xu et al. 20)8a), and GraphNets (Battaglia et al. 2018) follow these frameworks.
75
77
78
79 Li et al. (Li et al. 2018), Xu et al. (Xu et al., 2018a). Morris er al. (Morris et al. 2019 and Maron et al. (Maron et al., 2019a) show the connection between GNNs and the Weisfeiler-Lehman algorithm (Shervashidze et al. 201 of graph isomorphism tests, in which permutation-eqqivaaiii
80
81
82
holds a key constraint. Maron al. (Maron et al. (019b) and Keriven al. (Keriven & Peyré 2019) analyze the permutation permutation-qquivrriancc property of GNNs more theoretically. To date, most of the existing GNNs are permutation-equivee
83
84
and thus are not proximity aware. The only exception is P-GNN (You et al., 2019), which proposes to capture the positions of nodes using the relative
85
86 distance between the target node and some randomly chosen anchor nodes. However, P-GNN cannot and is computationally expensive.
satisfy permutation-eqqiiariin
88 Very recently, motivated by enhancing the expressive power of GNNs in graph isomorphism tests and distributed computing literature (Angluin) 1980 Linial 1992] Naor & Stockmeyer 1995), some studies suggest assigning unique node identifiers for GNNs (Loukas) 2020) such as one-hot IDs (Mrrphy al. 2019) or random numbers (Dasoulas et al. 2019 Sato et al.] 2020: Corso al.)
90
91
82
2020). For example, Sato et al. (Sato et al.] (020) novelly show that random numbers can enhance
GNNs in tackling two important basph NP problems with theoretical guarantee, namely the
98
2

---

Under review as a conference paper at ICLR 2021
minimum dominating set and the maximum matching problem, and Fey et al. (Fey al. 2020) em- pirically show the effectiveness of random features in the graph matching problem. Our work differs in that systematically study how preserve simultaneously in a simple yet effective framework, which is a new topic different from these ex- isting works. Besides, we theoretically prove that our proposed method preserve walk-based proximities by using the random projection literature. We also demonstrate the effectiveness of our method on various large-scale benchmarks for both node- and edge-level tasks, while no similar results are reported in the literature.
96
and proximity-warrenss awareness
87
99
100
102
The design of our method is also inspired by the random projection literature in dimensionality re- duction |Vempala (005) and to the best of our knowledge, we are the first to study random projection in the scope of GNNs. More remotely, our definition of node proximities is inspired and inherited
103
104
105
from graph kernels (Gärtner et al., 2003 Borgwardt & Kriegel 2005), network embedding (Perozzi
106
et al. 2014, Grover Leskovee 2016). and general studies of graphs (Newman 2018).
MESSAGE-PASSING GNNS
107
We consider graph G = EV,E, F) where V {ui,... uN is the set of N [ nodes, E C V V 109 is the set of M = [E| edges, and F E Nxdo is a matrix of do node features. The adjacency matrix is denoted A, where its 1h row, jth column and an element denoted Ai,: A.j. and Aij
111 respectively. In this paper, we assume the graph is unweighted and undirected. The neighborhood
112 of node ;; is denoted as N₁ and Nr = M₁ J (w:}-
The existing GNNs usually follow message- paasigng-annnggggg framework (Gilmer et al. 2017). where the 1hh 114 layer adopts a neighborhood aggregation function AGG(.) and an updating function UPDATE(.)
m (1) (hh (9) Vj E h
((+1) UPDATE(hh") m ())
115 where h E Rd is the representation of node o; in the 9hh layer, di is the dimensionality, and m,"
the messages. We also denote ( h ;..,. hw] and [- is the concatenation operation. The
node representations are initialized as node features, i.e., H F. We denote GNN following
117
Eq. with L layers as parameterized function as follows
118
( FaNN F; W);
where HL)) are final node representations learned by the GNN and W denotes all the parameters.
119
120
One key property of the existing GNNs is permutation-cqqiiarraane
Definition 1 (Permutation--quiiaaraaa
Consider graph G (V,E, F) and any permutation P. V + V so that G' = (V, E', F') has an adjacency matrix A' = PAP" and a feature matrix
122
F' = PF, where P E 10. NxN is the permutation matrix corresponding to P, i.e., Pi.j = iff
123
124
P(),) = Uy. GNN satisfies permutation-equivarrat equivariance if the node representations are equivariant
with respect to P, i.e.
PFNMN( (F, (, = (PAP W).
126
It is known that GNNs following Eq. 4 are permutaaionn-qqiivariaat (Maron al. 20196).
127
Definition 2 2 (Automorphism). A graph G is said to have (non-trivial) automorphism if there exists
128
non-identity permutation matrix + Iy so that A PAP" and F PF. We denote the corresponding automorphic node pairs as CG = Up {(i,j) P.J + j}
129
130
Corollary 1. Using Definition and 2 if a graph has automorphism, a permutation-equivariiee
GNN will produce identical node representations for automorphic node pairs:
(L) (L)) = h h v(i.j) E CG.
(4)
132
Since the node representations are used for downstream tasks, the corollary shows that permutation- equivariant GNNs cannot differentiate automorphic node pairs. A direct consequence of Corol- lary iss that cennuutatio--qqivarann GNNs cannot preserve walk-based proximities between pairs of nodes. The formal definitions are as follows.
133
134
135
Since the final layer of GNNs is task-specific, e.g., softmax layer for node classification readout layer for graph classification, we only consider the GNN architecture its last hidden layer.
3

---

Under review as a conference paper at ICLR 2021
Definition 3 (Walk-based Proximities). For a given graph G = EV, RNXN to denote
matrix S
137
proximities between pairs of nodes defined as:
Sij = S (1u2 v;)):
(5)
138
where v1 ~: 1/3 denotes walks from node u2 to Vi and S(-) is an arbitrary real-valued function. The length of walk-based proximity is the maximum length of all the walks of the proximity.
139
140
Typical examples of walk-based proximities include the shortest distance You et al. 2019), the high- order proximities (a sum of walks weighted by their lengths) (Zhang et al. 2018), and random walk probabilities (Klippera et al. 2 Next, we give a definition of preserving walk- based proximities.
142
143
Definition 4. For a given walk-based proximity, GNN is said to be able preserve the proximity if there exists a decoder function Fae satisfying that for any graph G = EV,E, F), there exist parameters WG so that Ve 0:
144
145
Si - Fae (H H (1) <c.
(6)
148
where
H = Fawv A, F.Wa).
147
Note that we do not constrain the GNN architecture as long as follows Eq. ① and the decoder function is also arbitrary (but notice that it cannot take the graph structure as inputs). In fact, both the GNN and the decoder function can arbitrarily deep and with sufficient hidden units.
148
149
Theorem 1.
The existing permutation-equueee equivariant GNNs cannot preserve any walk- proximity except the trivial solution that all node pairs have the same proximity 3
151
152
The formulation and proof of the theorem are given in Appendix A.I Since walk-based proximities are rather general and widely adopted in graph analytical tasks such as link prediction, the theorem shows that the existing cermmuaation-qqqvvriiin GNNs cannot handle these tasks well.
153
154
155
THE MODEL
156
4.1
A GNN FRAMEWORK USING STOCHASTIC MESSAGE PASSING
157 A major shortcoming of permutation-equivaat
GNNs is that they cannot differentiate automorphic node pairs. To solve that problem. we need to introduce some mechanism "symmetry breaking", i.e, to enable GNNs to distinguish these nodes. To achieve this goal, we sample a stochastic matrix
158
159
E E Nxd where each element follows an i.i.d. normal distribution A00,, 1). The stochastic matrix can provide signals in distinguishing the nodes because they randomly sampled without being affected by the graph automorphism. In fact, we can easily calculate that the Euclidean distance between two stochastic signals divided by a constant 22 follows a chi distribution Xa:
160
162
163
E.,- -E,, ~ Xd, Vi.j.
(8)
2
When d is reasonably large, e.g., d > 20, the probability of two signals being close is very low. Then, inspired by the message-passing framework, we apply a GNN on the stochastic matrix so that nodes can exchange information of the stochastic signals:
165
E = FANN (A, E; W)
187
We call É the stochastic representation of nodes. Using the stochastic matrix and message-passe passing, E can be used to preserve node proximities (see Theorem 2 and Theorem 3 Then, to let our model
188
189
still be able to utilize node features, we concatenate E with the node representations from another
170
GNN with node features as inputs:
H Fousput H()
(10)
È = FUNN (A, E. W). (L) = FGNNN (A (A,F; W
Prroposition 1 in You et al. distance proximity.
2019 can be regarded as special case of Thenrem Jsing the shortest
4

---

Under review as a conference paper at ICLR 2021
where Fouput(+) is an aggregation function such as linear function simply the identity mapping. In a nutshell, our proposed method augments the existing GNNs with a stochastic representation learned by pressage-passingg to differentiate different nodes and preserve node proximities.
172
173
174
There is also a delicate choice worthy mentioning, i.c., whether the stochastic matrix E is fixed or resampled in each epoch. By fixing E, the model can learn to memorize the stochastic representation and distinguish different nodes, but with the cost of unable to handle nodes not seen during training. On the other hand, by resampling E in each epoch, the model can have better generalization ability since the model cannot simply remember one specific stochastic matrix. However, the node representations are not fixed (but pairwise proximities are preserved: see Theorem (). In these cases,
175
176
177
178
179
180
E is more capable of handling pairwise tasks such as link prediction or pairwise node classification.
181
In this paper, we use fixed E for transductive datasets and resample E for inductive datasets.
182
Time Complexity From EQ, the time complexity of our framework mainly depends on the two GNNs in learning the stochastic and permutation -etiiiariiiiiviiiaattma node representations. In this paper, we instantiate these two GNNs using simple mnessage-passingg GNNs such as GCN (Kipf & Welling
183
184
185
)017) and SGC (Wu et al. 2019) (see Section 4.2 and Section 4.3). Thus, the time complexity of
186
our method is the same as these models, which is O(M), i.e., linear with respect to the number of
edges. We also empirically compare the running time of different models in Appendix [5.5] Besides, many acceleration schemes for GNNs such as sampling (Chen et al. 2018a b Huang et al., 2018)
187
188
or partitioning the graph (Chiang et al. 2019) can be directly applied to our framework.
190
4.2
A LINEAR INSTANTIATION
191
Based on the general framework shown in Eq. (0), we attempt to explore its minimum model jnstantiation, i.e., a linear model. Specifically, inspired by Simplified Graph Convolution (SGC) (Wu
192
193
ct al. 2019), we adopt a linear message-passing for both GNNs, i.c.,
H F ouppue E,, H (D = J ourpue E A
(11)
where A = ID+II ID 1- 1 is the normalized graph adjacency matrix with self-loops
194
195
proposed in GCN (Kipf & Welling, 2017) and K is the number of propagation steps. We also set
196
(.u)pu(()) in Eq. (II as a linear mapping or identity mapping.
Though scemingly simple, we show that such SMP instantiation possesses theoretical guarantee in preserving the bask- proximities.
198
Theorem 2. An SMP in Eq. (II) with the wesssgg--pssiingg matrix À and the number of propagation steps K can preserve the walk-based proximity A K ( y"" with high probability the dimensional- ity of the stochastic matrix d is sufficiently large, where the superscript T denotes matrix transpose. The theorem regardless of whether E are fixed or resampled.
199
200
201
202
203
The mathematical formulation and proof of the theorem are given in Appendix A.2 In addition, we show that SMP is equivalent to a germmutationeequivrraa GNN with certain parametrization.
205
Remark 1. Suppose we adopt Fomspu()) as a linear function with the output dimensionality the FONN (A, F; W") if parameters in F Fomapur (.) are all-zeros for É and an identity matrix for HL),
206
same as ForN. Then, Eq. (10) is equivalent to the
208
The result is straightforward from the definition. Then, we have the following corollary.
209
Corollary 2. For any task, Eq. (T) with the aforementioned linear Fomepu()) (.) is at least as powerful as the pernutation-equiins equivariant For (A, F; W'). i.e., the minimum training loss of using H in 10 is equal to smaller than using (L) FF,N W').
Eq.
In other words, SMP will not hinder the performancd the tasks are permotation-cquiivrrinn since the stochastic representations are concatenated with the permutation-ccuivariee GNNs fol- lowed by a linear mapping. In these cases, the linear SMP is equivalent to SGC (Wu et al. 2019).
212
213
214
215
Combining Theorem 2 and Corollary 2 the linear SMP instantiation in Eq. 11 is capable of han- dling both proximity aware and -otnuutttttoouuuvvviiianttt tasks.
216
'Similar to previous works such (Hamiloon et al. 2017 Xu et al. 2018a). 8a). only consider the minimum
training loss because the optimization landscapes and generalizann lizatinn gaps are difficult analyze analytically.
5

---

Under review as a conference paper at ICLR 2021
4.3
NON-LINEAR EXTENSIONS
218
One may question whether a more sophisticated variant of Eq. 10 can further improve the expres- siveness of SMP. There are three adjustable components in Eq. [T
219
two GNNs in propagating the stochastic matrix and node features, respectively, and an output function. In theory, adopting non-
220
221
linear models as either component is able enhance the expressiveness of SMP. Indeed, if we use sufficiently expressive GNN in learning E instead of linear propagations, we can prove a more
222
223
general version of Theorem 2 as follows.
224
Theorem 3. An SMP variant following Eq. (0) with FONN (A, E; W) containing L layers can and updating finnctions in the GNN are sufficiently expressive. In this theorem, we also assume the Gaussian random vectors E rounded to machine precision so that E is drawn from from countable subspace of R.
preserve any length-L walk-based proximity the message-passinn
226
228
The proof of the theorem is given in Appendix A.3 Similarly, we can adopt more advanced methods for Foupu(() (-) such as gating or attention so that the two GNNs are more properly integrated.
229
230
Although non- non-linear extensions of SMP can, in theory, increase the model expressiveness, they also take a higher risk of wer--itting due to model complexity, not to mention that the computational cost will also increase. In practice, we find in ablation studies that the linear SMP instantiation in Eq. (11)
231
232
233
works reasonably well on most of the datasets (please refer Section 5.4 for further details).
234
EXPERIMENTS
235
5.1
EXPERIMENTAL SETUPS
236
Datasets We conduct experiments on the following ten datasets: two simulation datasets, Grid and Communities Youu al., 2019), a communication dataset Email (You et al., 2019). two coau- thor networks, CS and Physics (Shchur et al. 2018), two protein interaction networks, PPI (Hamil- ton et al.) 2017) and PPA (Hu et al. 2020), and three GNN benchmarks, Cora, CiteSeer, and PubMed Yang et al. 2016). We only report the results of three benchmarks for the node classi- fication task and the results for other tasks are shown in Appendix B due to the page limit. More details of the datasets including their statistics are provided in Appendix C. These datasets cover a wide spectrum of domains, sizes, and with or without node features. Since Email and PPI contain more than graph, conduct experiments in inductive setting these two datasets, i.e., the training, validation, and testing set are split with respect to different graphs.
237
239
241
243
245
246
We adopt two sets of baselines. The first set is pernutation-equuvariin GNNs including GCN (Kipf & Welling, 2017]. GAT (Velickovic et al.) 2018), and SGC (Wu et al.) 2019). which are widely adopted GNN architectures. The second set contains P-GNN YYou et al. 2019). the only proximity-waare GNN date. We use the P-GNN-F version.
Baselines
248
250
In comparing with the baselines, we mainly evaluate two variants of SMP with different Fouturr (:): Ide-Itentity, i.e., (-) as identity mapping, and SMP-Linear, i.e., Foupu((-) as a linear mapping. Note that both variants adopt linear message-passing functions as SGC. We conduct more ablation studies with different SMP variants in Section 5.4
252
253
254
For fair comparisons, we adopt the same architecture and hyper-parameter for all the methods (please refer to Appendix C.2 for the details). For datasets without node features, adopt a con- stant vector as the node features. We experiment on two tasks: link prediction and node classifica- tion. Additional experiments on graph reconstruction, pairwise node classification, and running time comparison are provided in Appendix[B B We repeat the experiments 10 times for datasets except for PPA and 3 times for PPA, and report the average results.
256
257
258
259
260
5.2
LINK PREDICTION
Link prediction aims to predict missing links of graph. Specifically, we split the edges into 80%- 262
10%-109 10% and use them for training, validation, and testing, respectively. Besides adopting those real
obtain negative samples by randomly sampling equal number of node pairs that do not have edges. For all the methods, we set a simple classifier: Sigmoid (H. H,,, ie., the inner product to predict whether node pair (vt, Uz) forms link, and use AUC (area
edges as positive samples,
284
285

---

Under review as a conference paper at ICLR 2021
Table 2: The results of link prediction tasks measured in AUC (%).
The best results and the second- best results for each dataset, respectively, are in bold and underlined.
Model
Grid
Communities
Email
CS
Physics
PPI
SGC
57.6.3.88
11.911.6
68.517.0
96.5.10.1
96.6110.1 93.8
80.5
GCN
61.8+3.6
50.3=2.5
67.4:6.9
93.4
78.0=0044
GAT
61.045.5
1.,1=1.6
53,5+6.3
93.7=#0.9
94.1
79.
PGNN
73.4-16.0
97.8.10.6
70.916.44
82.2.10.5
Out of memory
80.8
SMP-Identity
55.1+4.8
98.0=0.7
72.9+5.11
96,5++0.1
96.5+0.1 96.110.1
81.0=+022
SMP-Linear
73.6:16.2
97.7
75.71:5.0
96.7-10.1
81.9.10.3
266
under the curve) as the evaluation metric. One exception to the aforementioned setting is that on the PPA dataset, we follow the splits and evaluation metric (i.e., Hits @ 100) provided by the dataset (Hu
267
268
ct al.
2020). The results except PPA are shown in Table 2
We make the following observations.
269
Our proposed SMP achieves the best results on five out of the six datasets and is highly compet- itive (the second-best result) on the other (Physics). The results demonstrate the effectiveness of our proposed method on link prediction tasks. We attribute the strong performance of SMP to its capability of maintaining both proximity-
271
272
and permutation-cquivariiee
properties.
On Grid, Communities, Email, and PPI, both SMP and P-GNN outperform the permutation- equivariant GNNs, proving the importance of preserving node proximities. Although SMP is simpler and more computationally efficient than P-GNN, SMP reports even better results.
274
276
When node features are available (CS, Physics, and PPD. SGC can outperform GCN and GAT. The results re- relvadid the experiments in SGC (Wu et al. 2019) that the non-linearity in GNNs is not necessarily indispensable. Some plausible reasons include that the additional model complex- ity brought by non-linear operators makes the models tend to overfit and also difficult to train (see Appendix B.6). On those datasets, SMP retains comparable performance on two coauthor graphs and shows better performance informative than node features on coauthor graphs for predicting links, and thus preserving graph structure is more beneficial on PPI.
277
278
280
PPI, possibly because node features on protein graphs are less
282
As Email and PPI conducted in an inductive setting, i.e., using different graphs for train- ing/ ang/aiiidation/testnng, the results show that SMP can handle inductive tasks as well.
285
286
The results on PPA are shown in Table I SMP again outperforms all the baselines, showing that it can handle large-scale graphs with millions of
Table 1:
The results of link prediction on the PPA dataset. The best result and the second-best result are in bold and underlined, respectively.
287
288
289
nodes and edges. PPA part of recently re-
Model
Hits 100
leased Open Graph Benchmark (Hu et al., (202)). The superior performance on PPA further demon- strates the effectiveness of our proposed method in the link prediction task.
290
291
SGC
0. 0.11871100012
GCN
0.186711.0132 0.1655+000240
292
GraphSAGE
293
P-GNN
Out of Memory
294
5.3
NODE CLASSIFICATION
Node2vec
0.2226
Matrix Factorization
0.3229
295
Next, we conduct experiments of node classifica- tion, i.e., predicting the labels of nodes. Since
SMP-Identity
0.2018=:001153
SMP-Linear
0.3582-:0.0070
297
we need ground- -rouund-tuuths in the evaluation, we only adopt datasets with node labels. Specifically, for
298
CS and Physics, following (Shchur et al., 2018). we adopt 20/30 labeled nodes per class for train-
289
300
ing/validation and the rest for testing. For Communities, we adjust the number as 5/5/10 labeled For Cora, CiteSecr, and PubMed, we use the default splits that came with the datasets. We do not adopt Email because some graphs in the dataset are too small to show stable results and exclude PPI as it is a multi-label dataset.
301
nodes per class for training/allidationttsstti
302
303
Thhe results of PGNN are slightly different compared to the paper because adopt more practical and common setting that negative samples in the data are not known apriori but randomly sampled in each epoch.
7

---

Under review as a conference paper at ICLR 2021
We use a softmax layer the learned node representations as the classifier and adopt accuracy, ie., how many percentages of nodes are correctly classified, as the evaluation criteria. We omit the results of IMM-Iddetity for this task since the node representations in SMP- IMP-Identity have fixed
305
307
dimensionality that does not match the number of classes.
Table 3: The results of node classification tasks measured by accuracy (%). The best results and the second- best results for each dataset, respectively, are in bold and underlined.
Model
Communities
CS
Physics
Cora
CiteSeer
PubMed
SGC
7.122.1
62.2
92.3=1.6
76.910.2
63.620.0
74.2:t0.1
GCN
7.5+12
91.1+0.7
93.1=088
8..41055
71.3::0.5
79.3:0.4
GAT
5.0.0.0
90.5
9..1=0.4
0.5910.5
71.2::0.6
77.9:1..5
PGNN
5.240..5
77.611.6
Out of memory
59.21
55.7:1..9
Out of memory
SMP-Linear
99.9+00.3
91.5++0.8
93.1
80.9+0.8
68.2++1.0
76.5+
308
The results are shown in Table 3 From the table, we observe that SMP reports nearly perfect results on Communities. Since the node labels are generated by graph structures on Communities and there are no node features, the model needs to be proximity- aware to handle it well, P-GNN, which shows promising results in the link prediction task, also fails miserably here.
309
310
311
312
On the other five graphs, SMP reports highly competitive performance. These graphs are commonly- used benchmarks for GNNs. P-GNN, which completely ignores cormuuattoo-qquivriiaa performs GNNs
313
poorly expected. In contrast, SMP can manage to recover the permutation-equivarti and avoid being misled, as proven in Remark []] In fact, SMP even shows better results than its counterpart, SGC, indicating that preserving proximities is also helpful for these datasets.
315
317
5.4
ABLATION STUDIES
318
We conduct ablation studies by comparing different SMP variants, including SMP-Identity, SMP- Linear, and the additional three variants as follows:
SMP-MLP: set set Foupuu()
fully-connected network with hidden layer.
SMP--LinearGGCNNer we set FANN A, F; W") in Eq. (TO) to be GCN (Kipf & Welling 2017). i.e., induce non-linearity in message passing for features. Foutpan (.) is still linear.
321
323
SMP-Linear-GCNhhaii we set both FONN (A, E; W) and FONN' (A, F; W') to be a GCN (iipf
324
& Welling 2017). i.e., induce non-linearity in message passing for both features and stochastic representations. Fouspuc()) is linear.
325
We show the results for link prediction tasks in Table 4 The results for node classification and pairwise node classification, which imply similar conclusions, are provided Table an Table in Appendix B.5 We make the following observations.
327
In general, SMP-Linear shows good-enough performance, achieving the best second-best sults on six datasets and highly competitive on the other (Communities). SMP-Identity, which does not have parameters in the output function, performs slightly worse. The results demon- strate the importance of adopting a learnable linear layer in the output function, which is con- sistent with Remark [ SMP-MLP does not lift the performance in general, showing that adding extra complexities in Fouipul (.) brings no gain in those datasets.
330
332
333
335
SMP-Linear- fCN reports the best results on Communities, PPI, and PPA, indicating that adding extra non-linearities in propagating node features are helpful for some graphs.
337
SMP-Linear- Linear-GNNoh. reports the best results on Gird with considerable margin. Recall that Grid has no node features. The results indicate that inducing non-linearities can help the stochas- tic representations capture more proximities, which is more helpful for featureless graphs
339
5.5
EFFICIENCY COMPARISON
341
To compare the efficiency different methods quantitatively, we report the running time different methods in Table 5. The results are averaged over 3,000 epochs NVIDIA TESLA M40 GPU
8

---

Under review as a conference paper at ICLR 2021
Table 4: The ablation study of different SMP variants for the link prediction task. Datasets except PPA are measured by AUC (%) and PPA is measured by @its@ 100. The best results and the second- best results for each dataset are bold and underlined, respectively,
Model
Grid
Communities
Email
Physics
PPI
PPA
SMP-Ldennity 55. 35.12-4.8
98.0=0.7
72.9=3.1
96.52:01
96.5=0011
81.0+:022
0.2018:
SMP-Lineur
73.6:622
97.710.55
7.07=5.0
96.71:0.1
96.1-001
0.0502
SMP-MLP MLP
72.1144.3
97.8.006
62.7
88.9.0.88
89.2:00.4
80.11:0.3
0.2035_10.0015
OMP-Linear-GONM
72.8:14.2
74.2-39
92.940.6
94.3-0.2
82.3--1.0
0.4090:10.00887
MaP-Linncr-GCN...
80,5+:3,9
97.3=007
73.4=5.5
89.8+2.0
91.7=0.2
79.7#:0.3
0,2125=:0.0522
Table 5: The average running time (in milliseconds) for each epoch (including both training and lesting), on link prediction task.
Model
Grid
Communities
Email
CS
Physics
PPI
SGC
25
28
58
210
651
704
GCN
25
35
75
214
612
784
GAT
36
43
140
258
801
919
PGNN
84
206
19,340
Out of Memory
6,521
SMP-Identity
26
37
96
284
751
840
SMP-Linear
212
616
SMP-MLP
23
28
83
237
614
831
SMP-Liness Aep-Linnar-GNNN
23
29
90
231
636
855
SMP-Linear MMP-Linear-GNNoo..
34
40
95
228
626
895
with 12 GB of memory. The results show that SMP is computationally efficient, i.e., only marginally 344 slower than SGC and comparable to GCN. P-GNN is at least an order of magnitude slower except for the extremely small graphs such as Grid, Communities, or Email with no more than thousand 346 nodes. In addition, the expensive memory cost makes P-GNN unable to work on large-scale graphs.
5.6
MORE EXPERIMENTAL RESULTS
Besides the aforementioned experiments, also conduct experiments the following tasks: graph reconstruction (Appendix B.I. pairwise node classification (Appendix [B.2), and comparing with
349
ooe IDs (Appendix B.3). Please refer to the Appendix for experimental results and correspond- ing analyses.
351
CONCLUSION
352
353
In this paper, we propose SMP, a general and simple GNN to maintain both and permutation-eqqiivarinnee properties. We propose augment the existing GNNs with stochastic node representations learned to preserve node proximities. We prove that SMP can enable GNN to preserve node proximities theory and is equivalent permutation-cquivariiii parametrization. Experimental results demonstrate the effectiveness and efficiency of SMP, Ablation studies show that a linear SMP instantiation works reasonably well on most of the datasets.
355
356
GNN with certain
357
358
359
REFERENCES
380
Dana Angluin. Local and global properties in networks of processors. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pp. 82-93, 1980.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzan Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. drXiv:1806.0126. 2018.
363
Stephen P Borgatti. Centrality and network flow. Social networks, 27(1):55-71, 2005.

---

Under review as a conference paper at ICLR 2021
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels graphs. In Fifth IEEE international conference on data mining (ICDM 055,, pp. 8 pp. IEFE, 2005.
367
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, 2014.
389
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942-950, 201 8a.
371
372
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b. 8b.
373
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
375
378
377
378
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liö, and Petar Veličkovió. Principal neighbourhood aggregation for graph nets. arXiv preprint 1rXiv:20040057/1 2020.
380
George Dasoulas, Ludovie Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. arXiv preprint arXiv: 19/2.00099, 2019.
382
Michaäl Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
384
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. In International Conference on Learning Representations, 2020.
386
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129-143. Springer, 2003.
388
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272, 2017.
390
392
Marco Gori, Gabriele Monfardini, and Franco Scarselli, new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
393
394
395
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
396
397
398
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. 2017.
389
In Advances neural information processing systems, pp.
400
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, YongDong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 639-648, 2020.
401
403
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
405
407
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, 2018.
409
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, pp. 7090-7099, 2019.
10

---

Under review as a conference paper at ICLR 2021
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pp. 2688- 2018. 2018.
412
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the 6th International Conference on Learning Representations. 2017.
415
416
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
417
Ioannis Konstas, Vassilios Stathopoulos, and Joemon M Jose. On social networks and collaborative recommendation. In Proceedings of the 32nd international ACM SIGIR conference on Research and development information retrieval, pp. 195-202, 2009.
420
422
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervisede learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
425
426
Nathan Linial Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193- 201. 1992.
427
428
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- ference Leurning Representations, 2020.
Jianxin Ma, Chang Zhou, Peng Cui, Hongxia Yang, and Wenwu Zhu. Learning disentangled repre- sentations for recommendation. In Advances in Neural Information Processing Systems 32, pp- 5712-5723. 2019.
431
432
433
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167 2019a.
Haggai Maron, Heli Ben-Hamu Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
436
437
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498 511, 2009.
439
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115-
441
5124, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
444
446
Ryan Murphy, Balasubramaniaa Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning. 2019.
447
Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277) 1995.
449
450
Mark Newman. Networks. Oxford university press, 2018.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEFE, 106 (5):808-822 2018
452
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
455

---

Under review as a conference paper at ICLR 2021
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks, arXiv preprint arXiv:2002.03155, 2020.
458
459
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2008.
Kakade Sham and Shakhnarovich Greg. Random projections. CMSC 35900 (Spring 2009) Large Scale Learning, 2020. URL https://ttic. uuc.iiii.ccchcccg....e... wttp:/eeeeegoooo/ooooorrrreere
462
463
[Online; accessed 4-September-2020).
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018
485
466
467
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2561, 2011.
488
469
470
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high nigh-dimensional data analysis to net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
472
473
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference world wide web, pp. 1067-1077, 2015.
475
476
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the 7th International Conference on Learn- ing Representations, 2018
478
479
Santosh S Vempala. The random projection method, volume 65. American Mathematical Soc., 2005.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 1234, 2016.
482
483
484
Duncan J Watts. Networks, dynamics, and the small-world phenomenon. American Journal of sociology, 105(2):493-577, 1999.
485
486
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp. 6861-6871, 2019.
487
489
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018a.
490
491
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462, 2018b.
493
494
Zhilin Yang. William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, pp. 40 2016.
496
497
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference Machine Learning, pp. 7134-7143, 2019.
Ziwei Zhang, Peng Cui, Xiao Wang. Jian Pei, Xuanrong Yao, and Wenwu Zhu. Arbitrary-order proximity preserved network embedding. In Proceedings of the 24thACM ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2778 2786, 2018
500
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1100-i198, 2017.
503
12

---

Under review as a conference paper at ICLR 2021
A
THEOREMS AND PROOFS
505
A.1
THEOREM 1
506
Here we formulate and prove Theorem
Theorem 1 For any walk-based proximity function S()). permatation-equivaiit CNN cannor
508
preserve ).), except the trivial solution that all node pairs have the same proximity, i.e, St. J. where e is constant.
510 Proof. We prove the theorem by contradiction. Assume there exists non-trivial S(.) which permutation-equivarii GNN can preserve. Consider any graph G = (V, F) and denote N [ We can create G' = (V", F') with [V*| = -N so that:
511
Egj E EI-NJ-N
if N
F', F1: FFNN, if > N
if N
if N,J > N,
(12)
else
513
Basically, we generate two "copies" of the original graph, one indexing from 1 N, and the other indexing from N 1 1 to 2N. By assumption, there exists permutation-equivarie
514
GNN which can
preserve S(-) in G' and we denote the node representations as H = FaNN(A', A F'; W W.)). It is
515
516
easy see that node oy and N in G' form an automorphic node pair. Using Corollary ] their
517
representations will be identical in any permutation-cquivarian GNN, i.e..
H (D)
H
(L) N.: Vi S N.
(13)
Also, note that there exists no walk from the two copies. i.c. {o/ ~e 1//} = {2/z ~s 2// = 0, Vi s N.j > N. As result, for Vi S N. S N, Ve O we have:
518
519
[St. - S(0) <
Sig Fdc
H
(L)
(L)
+ S(0) Fac
H (L)
H (1)
(14)
Si.j
Fa
H
H (L)
+ Sty+N Fae
H (L)
H (L)
J+N.)) ) 2c.
520
We can prove the same for Vi > N.j j > N. The equation naturally holds if i < N.j > N or
521 i N.j S N since {o/ ~ v/ = Combining the results, we have > 0, Vi SS.j - S(0) <
522
2c. Since can be arbitrarily small, the equation shows that all node pairs have the same proximity
523
c = (0). which leads to a contraction and finishes our proof.
Notice that in our proof, G' can be constructed for any graph, rather than designing specific counter-example, we have shown that there always exists an infinite number of counter-examples by constructing automorphisms in the graph.
525
526
527
Some may find that our counter-examples in the above proof will lead to multiple connected com- ponents. Next, we give an alternative proof maintaining one connected component (assuming the original graph is connected) under the assumption that the walk-based proximity is of finite length.
528
529
Proof. Similar to the previous proof, we assume there exists a non-trivial S(-) which a permutation- equivariant GNN can preserve. Besides, we assume the length of S(-) is upper bounded by (mxx where mmx is any finite number, i.c., Vi,j.
530
532
Sig S ((us vy)) S ((vs vyllen(ve un)) S Imax))
(15)
13

---

Under review as a conference paper at ICLR 2021
Then, for connected graph G = (V, E),, create G' (V", similar to Eq. ically, denoting Ñ N + Imax. let G' have 3N nodes that:
12
Specif-
Ei,
i s N
1
iN SAISN - if < 1,j S N
F s
if N if < < Ñ if N <
1
iN + 4 - 2N +1, -
F F
E =
F',
E E1-28.122
if < 2N +
if < if <i +
1
if + N < -
F. F.
if 3N, -
1 or 3Ñ
if + N
0
clse
(16)
535
Intuitively, we create three "copies" of G and three "bridges" to connect the copies and thus make G" also connected. It is also easy to see that nodes 2//, vf N and v' 24 all form automorphic node pairs and thus we have:
537
Vi SEN Ñ. H -HIL) N 442M,
H
(17)
538
Next, we can see that the nodes in G' are divided into six parts (three copies and three bridges), which we denote Vy {V1,.... J. V/2 (uN=1:...,gh: V/3 {"N41 UN+N J. V "2 J. and V/ { {22 .... 83N Since V/, V/, V% are bridges with length /max, any walk crosses these bridges will have length large than Lmxx For example, let us focus on E Ví, i.e., i S N. If U is in V/ V4 or V/d (i.e., N < < 2N + N), any
"o.++....,.
N N+N++: 2 }. V/J { (12N
540
541
542
543
walk 1/2 ~ By will either pass the bridge V/2 or V/ and thus has a length larger than Imax As a result,
544
we have:
S ~ 12}) = (fve ~+ By lenn ~y UU) S mmax 1) = S (0).
(18)
If E V u pair similar to Eq. 14 i... VE O, we have
1/2 i.e., j & Ñ, can the fact that Uj and U5+N forms automorphic node
[.. 8(0) <
Sijj Fae
H (L)
(L)
+ S(0) Fic
(L)
(19)
Sij Fac
H (L)
H
+ S S. Fao H (L)
H (z) - ) 2e.
Similarly, if uy E V/ ie., 2Ñ + <. we can use the fact that vy and y forms an automorphic
547
548
node pair to prove the same inequality. Thus, we prove if < N, Ve > 0, Vj. [S,, S(0) < 2e. The same proof strategy can be applied i N. Since can be arbitrarily small, the results show that all node pairs have the same proximity S(0), which leads to contraction and finishes our proof.
549
550
551
S52
A.2
THEOREM
Here formulate and prove Theorem Appendix A.I
2 Note that some notations and definitions introduced in
554
Theorem 2 For the walk-based proximity S = (A"),, SMP can preserve the proximity with
555
596
high probability if the dimensionality of the stochastic matrix is sufficiently large, i.e., Ve. > 0, V5 > O, there =a so that any d. > do:
< <
(20)
558
where H are the node representation obtained from SMP in Eq. U. The result holds for any stochastic matrix and thus is regardless of whether E is fixed or resampled during each epoch.
560 Proof. Our proof is mostly based on the standard random projection theory. Firstly, since we have proven in Theorem [ that the permutation-equivariant representations cannot preserve any walk- based proximity, here we prove that can preserve the proximity only using E, which can be
14

---

Under review as a conference paper at ICLR 2021
easily achieved by ignoring H in Foupurl [E, H),,,, e.g., if we set Fouput linear function, the model can learn to set the corresponding weights for H(L) as all-zeros.
565
We set the decoder function as a normalized inner product:
Fac (H.,.) Hj,)
H
(21)
Then, denoting a; A and recalling E A AKE, E, we have:
S Fde Hy,)) | E, - |a,a} a, EE a
(22)
Since E is Gaussian random matrix, from the Johnson-LLnng Lindenstrauss lemma Vempala 2005 (in
568
the inner product preservation forum, e.g., see Corollary 2.1 and its proof (Sham & Greg 2020
v0 < e' 1. we have:
589
P la.a a, EE a
S 2
[[|a,]| + ||.])) > 1 4e"
(23)
570
By setting
max; mz|l we have 5 (||a,|1 || + ||a II) and:
mons [0
P(S - Fae (H... H < > 1 4e
(24)
which leads to the theorem by solving and setting do follows:
4 loo 2 (max, |a:1l)
max
max
4e
8 = do
(25)
e² max, ||a.
572
573
A.3
THEOREM 3
574
Here we formulate and prove Theorem 3 Note that some notations and definitions are introduced in Appendix A.I
Theorem
For any length- L walk-based proximity, i.e,
S.j = (fv, uz}) S ({va Vyllen(u, 11y I.J),
where len(-) is the length of walk, there exists an SMP variant in Eq. (0) with FONN (A, E; W) containing L layers (including the input layer) to preserve that proximity the following conditions hold: (1) The stochastic matrix E contains unique signals for different nodes, i.e. Ei,; # E,,: Vi +
577
579 j. (2) The message-passe passing and updating functions in learning E are bijective. (3) The decoder
580
function (-) also takes E as inputs and is universal approximation.
Proof. Similar as Theorem we only utilize È during our proof. We use e e S to
581
denote the node representations in the 4t layer of FaNN (A, E; W), i.e., e E., and e (4-1)
583
E. :. Our proof strategy to show that the stochastic node representations can remember all the information about the walks.
584
585
Firstly, the message- passingg and updating function are bijective by assumption, can recover from the node representations in each layer all their neighborhood representations in the previous layer. Specifically, there exist. (()())) < 1 < T. such that:
586
587
FO) (e
e (1-1) f .j N. 6
(26)
588
For notation conveniences, we split the function into two parts, one for the node itself and the other for its neighbors:
F(())
self (e!))
e 111)
(27)
FO
( (e()==((r
(Q())
(1-1) .j Ni)
neighbor
"To let (1) output set with arbitrary lengths, we can adopt sequence-based models such an L.T.M.
15

---

Under review as a conference paper at ICLR 2021
For the first function, if we successively apply such functions from the 1th layer to the imput layer, 591 can recover the imput features of the GNN, i.e., E. Since the stochastic matrix E contains a unique
582 signal for different nodes, we can decode the node ID from e; (0) i.e., there exists Frlli
c E
(0),
For brevity, we denote applying such (+ functions to get the node ID
Frll() (c self
FFll self
(Feel) sell
(Fee)
E) i.
(28)
self
For the second function, we can apply F to the decoded vector set so that we can recover their neighborhood representations in the (1 - 2)th layer, etc.
594
585
Next, we show that for e/ e there exists length-/ walk vy ~n Uj (Va1 Vag: ...y Vay ) where
596
Va = 2/ Va, = by if and only if =((
( 1)- = a = j and there exists e (0) such
597
self
that:
2ll-2) 2)
F(l-1)
(e) ( F J (0:-22
(e
neighhor
01-1:
(l 3) neighbor
x(1-2)
(e(-2))
Felr
(31-33
(ell33)
-1-2
(29)
(0)
F(1) neighbor (e(1))
F(0(0) (e!0) =a1 =i.
This result is easily verified as:
(Uay: Vaz: ... Vay) a walk E, EEg,a, =1 aj D Natt. vlsiel
E (i-1) E
F(()) (e(") I(0-i-1) (e(-11) a5
- VI S <
neightor
(30)
Note that all the information is encoded in E, i.e., we can decode {uz ~ uy|len(vi in 01)) < L} from
601 e (1-1) by successively applying F=())
self (:), )(()) neightor (-). We can also apply F(0:(-11 to e (L-1)
to get
602 the start node ID i. Putting it together, we have:
F F(e/
(1-1) oe ((--1)) (us By len(e; ~n un) S L),
(31)
603
where F(-) is composed of F=() function S(.), we have:
self
(-,,0 S < L and x(()
neighhor (,), L. Applying the proximity
s (F (c/u-11, ee _)( ) St.j
(32)
605
We finish the proof by setting the real decoder function F.)(.) to arbitrarily approximate this desired function S (F (cy-)) under the universal approximation assumption.
608
607
B ADDITIONAL EXPERIMENTAL RESULTS
B.1
GRAPH RECONSTRUCTION
609
To verify that our proposed SMP can indeed preserve node proximities, we conduct experiments of graph reconstruction (Wang et al. 2016), i.e., using the node representations learned by GNNs to reconstruct the edges of the graph. Graph reconstruction corresponds to the first-order proximity
610
611
612
between nodes, i.e., whether two nodes directly have a connection, which the most straight- forward node proximity (Tang et al. 2015). Specifically, following Section 5.2 we adopt the inner product classifier Sigmoid(HH H,, and use AUC as the evaluation metric. To control the impac of node features (i.e., since many graphs exhibit assortative mixing, even models only using node features can reconstruct the edges to a certain extent), we do not use node features for all the models.
614
616
We report the results in Table 6 The results show that SMP greatly outperforms permutation- equivariant GNNs such as GCN and GAT in graph reconstruction, clearly demonstrating that SMP can better preserve node proximities. PGNN shows highly competitive results as SMP. However, similar to other tasks, the intensive memory usage makes PGNN unable to handle medium scale graphs such as Physics and PubMed.
618
620
16

---

Under review as a conference paper at ICLR 2021
Table 6: The results of graph reconstruction measured in AUC (%). The best and the second-best
results for each dataset, respectively, are in bold and underlined. OOM represents out of memory.
Model
Grid
Communities
Email
CS
Physies
PPI
Cora
CiteSeer
PobMed
SGC 74.840..
65.4=16 1.6
71.640.33
66.710.1
66.24000
76.2-0.2
56.749977
58.540..1
71.9:10.11
GCN
73.0=0.3
63.7=1.2
72.5+0.4
75.5=04
76,8+04
79.2=0.4
68.243.9
69.8=8.0
77.2+-211
GAT
59.6.1 1.2
52.9
16991199
57.0114
59.11007
61.1
1.0
6..2:::5
58.810.88
PGNN
9..41:011
97.7=0011
85.6::0.88
97.21:0.6
00M
8.62-0.6
98.111.0.6
99.7:10.1
OOM
SMP-Identin
99.2++0.1
97.5=0.1
80.0-00.3
77.1
03.7+00.3
79.5=0.2
89.74:5.7
97.1=0088
77.0-10.1
SMP-Linear
99.1+0.1
97.8=0.1
86.7.0.22
96.3+0.2
95.5:10.2
85.5=0.1
96.3+.0.1
98.240.1
95.8400.2
622
B.2
PAIRWISE NODE CLASSIFICATION
623
we follow YYou et al. 2019) and experiment on pairwise node classification, i.c., predicting whether two nodes have the same label. Compared with standard node classification, pairwise node classification focuses more on the relations between nodes and thus requires the model to be proxinity-aware to perform well.
Besides standard node classification experiments reported in Section [.3
624
625
626
627
Similar to link prediction, we split the positive samples (i.e., node pairs with the same label) into an set with an equal number of randomly sampled negative pairs. For large graphs, since the possible positive samples are intractable (i.e. O(N2), we use a random subset. Since we also need node labels as the ground-truth, we only conduct pairwise node classification on datasets when node labels are available. We also exclude the results of PPI since the dataset is multi-label and cannot be used in pairwise setting YYou al.] 2019). Similar to Section 5.2 we adopt a simple inner product classifier and use AUC as the evaluation metric.
628
80%- 100-000----- 10% caining-validation-eeete
629
631
633
The results are shown in Table We observe consistent results as link prediction in Section 5.2 i.e.,
635
SMP reports the best results on four datasets and the second- best results on the other three datasets. These results again verify that SMP can effectively preserve and utilize node proximities when needed while retaining comparable performance when the tasks are more permutation-equiiariani
636
637
638
like, e.g., on CS and Physics.
Table 7: The results of pairwise node classification tasks measured in AUC (%). The best results and the second-best results for each dataset, respectively, are in bold and underlined.
Model
Communities
Email
CS
Physics
Com
CiieSeer
PubMad
SGC
67.41:24
56.31.5544
9.0
99.61:0.0
99.2-10.33
9.7
92.3:10.3
GCN
64.9-12.3
55.0.1.5.7
96.8.10.7
99.71.0.1 96.340022
97.7110.6
9.
94.8.0.44
GAT
5..5+11.3
47.742277
95.2440.6
91.6+:0.7
73.6+2.7
87.1
PGNN
98.6.1..55
63.3.15.5
90.0.10.5
Out of memory
85.5.1
4..8.1..88
Out of memory
SMP-Idemiiyy
98.8-1-0.5 98.8:1-0.5
56.9-14,11
99.7+-0.0
99.6++0.00 99.6
99.2-10.22
95.2+ 1.1
91.9 93.4::0.2
SMP-Linear
74.5:t-.11
99.8-10.0
99.3+0.3
95.3+0.4
639
B.3
COMPARISON WITH USING IDS
We further compare SMP with augmenting GNNs using a one-hot encoding of node IDs, i.e., the identity matrix. Intuitively, since the IDs of nodes are unique, such method does not suffer from the automorphism problem and should also enable GNNs preserve node proximities. However, theo- retically speaking, using such a one-hot encoding has two major problems. Firstly, the dimensional- ity of the identity matrix is N x N, and thus the number of parameters in the first message-pasee passinng layer is also on the order of O(N). Therefore, the method will inevitably be computationally ex- pensive and may not be scalable to large-scale graphs. A large number of parameters will also more likely lead to the overfitting problem. Secondly, the node IDs are not transferable across different graphs, i.e., the node 01 in one graph and the node 11 in another graph do not necessarily share a similar meaning. But as the parameters in the message-passinng
641
642
643
644
645
646
647
648
depend on the node IDs (since they 650 are input features), such a mechanism cannot handle inductive tasks well
One may question whether SMP is transferable across different graphs since the stochastic features are independently drawn. Empirically, we find that SMP reports reasonably well results inductive datasets such
17

---

Under review as a conference paper at ICLR 2021
Table 8: The results of comparing SMP with using one-hot IDs in GCNs. 00M represents of
memory. represents the task is unavailable.
Task
Model
Grid
Communities
Email
CS
Physics
PPI
Cora
CiteSeer
PubMed
Link Prodiction
GCNaodat SMP-Linear
91.5442.1 73.6
98.1=0.7
71.243.
93.1
OOM
78.610.3
86811
81.71111
89.4100.5
97.7=0.5
75.7#5.00
96.7=0.1
96.1=0.1
81 81.90033
92.7#b077
92.6110
95.4::02
Pairwise Node
GCNaaete
98.9=0.5
67.34566
97.6-1022
O0M
98 08.24:03
94.41:2
98.940.11
Classification
SMP-Linear
98.8=0.5
74.544.1
99.8=0.0
99.6=0.0
99.34:0.3
95.3+0.4
93.44022
Node
GCNade
99.6:1100
86.9
OOM
77.611 57.74588
74.9:0.6
Clasilication
SMP-Lineur
99.9=0.3
91.5:1088
93.1=0.8
80.9.088
68.2:1100
76.5100.8
651 We also empirically compare such a method with SMP and report the results in Table 8 The results
652 show that SMP-Linear outperforms GCNonchot in most cases. Besides, GCNonchot fails handle
653 Physics, which is only medium-seae scale graph, due to the heavy memory usage. One surprising result that GCN onehot outperforms SMP-Linear on Grid, the simulated graph where nodes are placed on 20 x 20 grid. A plausible reason is that since the edges in Grid follow specific rule, using one-hot encoding gives GCNonehox enough flexibility to learn and remember the rules, and the model does not overfit because the graph has rather small scale.
654
656
658
B.4 ADDITIONAL LINK PREDICTION RESULTS
659
We further report the results of link prediction on three GNN benchmarks: Cora, CiteSeer, and PubMed. The results are shown in Table 9 The results show similar trends as other datasets pre-
681
sented in Section 5.2 i... SMP reports comparable results as other coomutatiionequivarree GNNs while PGNN fails handle the task well.
Table 9: The results of the link prediction task measured in AUC (%).
The best results and the second-best results for each dataset, respectively, are in bold and underlined.
Model
Cora
CiteSeer
PubMed
SGC
93.6+-0.6
94.7+-0.8
95.8-+0.2
GCN
90.6:1..0
78.211.7
92.410.9
GAT
8..5
87.81100
89.2.10.8
PGNN
75.4++2.3
70.6+
Out of memory
SMP-Identity
93.0++0.6
92.9+00.5
94.5+0.3
SMP-Lincar
92.7=t0.7
92.6+1.0
95,4+002
SMP-MLP
82.8+0.9
80.7+1.1
88.0=0.6
SMP-Linear-GCNN
86.7-11.4
81.11114
90.5
SMP-LLinar- GCNout
80.1
80.0+22.0
81.142.0
683
B.5 ADDITIONAL ABLATION STUDIES
664
We report the ablation study results for the node classification task and pairwise node classification task in Table 10 and Table II. respectively. The results again show that SMP-Linear generally achieves good-enough results on the majority of the datasets and adding non-linearities does not necessarily lift the performance of SMP.
685
686
687
688
We also compare whether the stochastic signals E are fixed or not during different training epochs for our proposed SMP. For brevity, we only report the results for the link prediction task Table I2 The results show that fixing E usually leads to better results on transductive datasets (recall that
669
670
671
datasets except Email and PPI are transductive) and resampling E leads better results on inductive
672
datasets in general. The results are consistent with our analysis in Section 4.1
as Email and PPI. One plausible reason is that since the proximities of nodes are preserved even the random features per different (see Thcorem 2] all subsequent parameters based proximities can he transferred.
18

---

Under review as a conference paper at ICLR 2021
Table 10: The ablation study of different SMP variants for the node classification task. The best results and the second-best results are in bold and underlined, respectively.
Model
Communities
CS
Physics
Cora
CiteSeer
PubMed
SMP-Linear SMP-MLP
99.911.33
91.
93.1110.8
80.9.10.8
68.2.11.0
76.5110.8
100.0=0.2
90.1=0.5
92.3+0.8
79.3+0.8
67.0+1.5
76.8+0.9
AMP-Linnar-Ger GCaar 1.0
89 89.8=0.7
92,9+0088
78,941.2
67.8+0.6
77.320.6
SMP-Linear-Ger NChooh
100.0=0.2
77.
87.1
69.2+2.5
49.8#3.1
68.1+4.1
Table 11: The ablation study of different SMP variants for the pairwise node classification task. The best results and the recond-best results are in bold and underlined, respectively.
Model
Communities
Email
CS
Physics
Cora
CiteSeer
PubMed
SMP-Idennity
98.8+0.5
56.9:14.1
99.7=0.0
99.6-:0.00
99.2+0.22
95,2+111
91,920033
SMP-Lineur
98.810..
74.5:14.11
9.08:000
99.6:10.0
99.31.0.3
0.4
93.4:10.2
SMP-MLP
98.7.10.3
65.4-16.1
94.3-006
97.6.10.44
90.311.300
63.7
93.4-10.4
SMP-Linear-GONan
99,0-+0.4
00.2499.
95.6=0077
96.1+-0.7
88.8:1..
94.8--022
SMP Linear GCN
98.8.10.4
61.6.1..0
95.2.10.7
97.8.00.8
94.311.9
83.5.39
94.1
B.6 COMPARISON OF PERMUTATIINN
GNNS FOR LINK PREDICTION
674 To investigate the performance of linear and non-linear variants of connuutttioo-qquvvrriann GNNs for the link prediction task, we additionally report both the training accuracies and the testing aceu- racies of SGC, GCN, and GAT in Table 13 Notice that to ensure fair comparison, we do not adopt
675
677 the early stopping strategy here so that different models have the same number of training epochs (otherwise, if a model tends to overfit, the early stopping strategy will terminate the training process when the number of training epochs is small and result in a spurious underfitting phenomena).
679
The results show that non-linear variants of GNNs (GCN and GAT) more likely to overfit, i.e., the margins between the training accuracies and the testing accuracies are usually larger, than the linear variant SGC. Besides, though possessing extra model expressiveness, non-linear GNNs also difficult to train, i.e., the training accuracies of GCN and GAT are not necessarily higher than SGC. The results are consistent with the literature WWu et al. (2019) He et al. (2020).
881
683
684
685
C
EXPERIMENTAL DETAILS FOR REPRODUCIBILIITY
686
C.1
DATASETS
Grid YYou et al. 2019) : A simulated 2D grid graph with size 20 20 and no node feature.
Communities YYou et al. 2019): A simulated caveman graph WWtts 1999) composed of 20 communities with each community containing nodes. The graph is perturbed by rewiring I 1% edges randomly. It has no node feature and the label of each node indicates which community the node belongs to.
689
691
Emaiñ You et al., 2019): Seven real-world email communication graphs. Each graph has six communities and each node has integer label indicating the community the node belongs to.
692
Coauthor Networks (Shchur et al. 2018): Two networks from Microsoft academic graph in CS and Physics with their nodes representing authors and edges representing co- oo-authorships between authors. The node features are embeddings of the paper keywords of the authors.
695
3 (Hamilton et al. 2017]: 24 protein-protein interaction networks. Each node has 50- dimensional feature vector.
696
TP (Hu et al. 2020): network representing biological associations between proteins from
689
700
58 different species. The node features are one-hot vectors of the species that the proteins are
701
taken from.
19

---

Under review as a conference paper at ICLR 2021
Table 12: The results of comparing whether the stochastic signals E are fixed or during different training epochs for the link prediction task. The better of the two results are in bold.
Model
E
Grid
Communities
CS
Physies
Email
PPI
Fixed
55.114.8
98.0.10.7
9..
96.5100.1
75.913.9
80.410.4
SMP-Identity
Not Fixed
55.2:t4.11
97.6=#0.7
96.4=0.1
96.5+0.1
72.9+5.1
81.0=:.2
Fixed
7..6:16.2
97.7
96.
96.11001
71.31:3.9 75.7:15.00
71.5
SMP-Linear
Not Fixed
64.4:12.99
97.4
96.2.10.1
96,11.0.1
01.9
Table 13: The results of SGC, GCN, and GAT for the link prediction task. Both the training accura- cies and the testing accuracies are reported.
Method
Resalts
Grid
Communities
Email
CS
Physics
PPI
Cora
CiteSeer
PubMed
Train
52.4:0.5
50.4::0.5
68.41100
98.31000
97.7+000
8499004
99.5::000
99.9=0.0
98.9::000
SGC
Text
51.6.299
49.2:1:66
67.011.3
%6.510.1
96.5110.1
78.810.77
92.5110.7
94.0
95.6.10.3
Train
51.3110
50.040.6
68.444.0
95.34033
95.1=033
76.1
96.310
77.3=13
95.921666
GCN
Teat
54.6:24.3
49.2
66.0::3.1
93.24:033
93,820.3
74.9::066
89.2::033
76.1=2.5
90.6:1112
Train
4.
49.610.3
52.243.6
95.71009
96.410.5
82:3:0.3
97.2:0.5
99.3=0.1
98.310.TT
GAT
Test
50.8:6.0
50.8:2.11
47.6:244
91.0=1111
93.920.3
78.5:04
7..7
81.0=0,7
83.7
Cora, CiteSeer, PubMed 11 Yang et al. 2016): Three citation graphs where nodes correspond to papers and edges correspond to citations between papers. The node features are bag-of-worde and the node labels are the ground truth topics of the papers.
702
704
705
We summarize the statistics of datasets in Table
706
C.2
HYPER-PARE PARAMETERS
We the following hyper-parameters:
708
All datasets except PPA: we uniformly set the number of layers for all the methods 2, i.e., pessage-passing steps, and set the dimensionality of hidden layers as 32, i.c., H E R2 x32 for all S 1 S L (for GAT, use heads with each head containing 8 units). We Adam optimizer with an initial learning rate of 0.01 and decay the learning rate by 0.1 at epoch 200. The weight decay is 5e-4. We train the model for 1,000 epochs and evaluate the model every epochs. We adopt an early-stopping strategy by reporting the testing performance at the epoch which achieves the best validation performance. For SMP, the dimensionality the stochastic matrix is d' 32. For P-GNN, use the P-GNN-F version, which uses the truncated 2-hop shortest path distance instead of the exact shortest distance.
709
710
712
714
716
717
PPA: as suggested in the original paper (Hu et al., 2020). we set the number of GNN layers as 3 with each layer containing 256 hidden units and add three-layer MLP after taking the Hadamard product between pair-wise node embeddings as the predictor, i.e., MLP @ H,)- We use Adam optimizer with an initial learning rate of 0.01. We set the number of epochs for training as 40, evaluate the results on validation sets every epoch, and report the testing results using the model with the best validation performance. We also found that the dataset had issues with exploding gradients and adopt a gradient clipping strategy by limiting the maximum p2- norm of gradients as 1.0. The dimensionality of the stochastic matrix in SMP is d = 64.
719
721
723
725
C.3
HARDWARE AND SOFTWARE CONFIGURATION
728
All experiments are conducted on server with the following configurations.
727
Operating System: Ubuntu 18.04.1 LTS
728
CPU: Intel(R) Xeon(R) CPU ES-2699 v4 @ 2.20GHz
NVIDIA TESLA M40 with 12 GB of memory
thwb. wwtp:ttt.w.....oooootooooooooo httpp///ttaaaaoooooooooooooeeeee
20

---

Under review as a conference paper at ICLR 2021
Table 14: The statisties of the datasets. For datasets with more than graph, #Nodes and #Edges are summed over all the graphs and the experiments are conducted in an inductive setting.
Dataset
#Graphs
#Nodes
#Edges
#Fcatures
#Classes
Grid
400
760
Communities
400
3,800
20
Email
1,005
25,571
42
CS
I
18,333
81,894
6,805
15
Physics
1
34,493
247.962
8,415
5
PPI
24
56,944
818,716
50
PPA
576,289
30,326,273
Cora
2,708
5,429
1,433
7
CiteSeer
3,327
4.732
3,703
6
PubMed
19,717
44,338
500
3
730
Software: Python 3.6.8, PyTorch 1.4.0, PyTorch Geometric 1.4.3, NumPy 1.18.1, Cuda 10.1
21


Reviews:
[{"review_id": "y9a3ejyDknM", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "While the paper is easy to follow, I found all the results in this paper trivial and already-known.\n\nPros:\n1. The paper is well-written and easy to follow.\n\nCons:\n1. The entire Section 3 is not novel. It is a mixture of the preliminaries of GNNs and the trivial results of Corollary 1 and Theorem 1. Moreover, Theorem 1 is not rigorous. What if walk-based proximity is just a constant function? What if a given graph does not contain any automorphism?\n2. “Preserve walk-based similarity” is not rigorously defined. It seems that it just means all nodes have different embeddings.\n3. The proposed model is not permutation-equivariant after adding Gaussian noise. It is trivial that the model becomes permutation-equivariant when the Gaussian noise is ignored (because the model just reduces to an ordinary GNN).\n4. The claim that SMP preserves walk-based proximity is trivial and just relies on the fact that randomly-sampled vectors from a Gaussian distribution are different from each other.\n5. The idea of using node identifiers (essentially equivalent to the Gaussian noise) to make GNNs position-aware is not new. In fact, this idea is clearly mentioned in the P-GNN paper already (Section 6.2 of [1] “for inductive tasks, augmenting node attributes with one-hot identifiers restricts a model’s generalization ability”).\n6. In Section 5.3, it is unclear why the OGB node classification datasets are not used.\n\n[1] https://arxiv.org/abs/1906.04817\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "whLxvQhrGVY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Since the publication of P-GNN (You et al., 2019), it has become clear to the graph ML community that node positional information can be effectively leveraged for link prediction and pairwise node classification tasks.\nThis paper introduces SMP, a novel stochastic message passing approach that preserves both permutation-equivariance (common to GNN models) and node proximities. Extensive experimental results show that SMP not only achieves competitive performance on many common graph ML datasets, but also succeeds to combine together the expressiveness of a standard GNN with P-GNN  (without incurring the scalability problem of P-GNN).\n\nI thoroughly enjoyed reading this paper, both for the insights and the technical soundness. I have very few remarks about the paper, as I believe that i) SMP is an ingenious idea, ii) the experimental setting is adequate, iii) the quality of the writeup is high, iv) and the results appear to be reproducible.\n\nIf I had to nitpick, I'd say that part of Table 7 (currently in the Appendix) belongs to the main paper, as I was convinced about the superior runtime performance of SMP only after reading those numbers. If the avg running time for an SMP epoch was significantly larger than the one for GAT (for instance), I would have considered SMP yet another specialized model.\nInstead, given that the GPU consumption (both in terms of computation and memory) is similar to any other GNN model, I believe SMP could be adopted as a more flexible graph ML method (which would avoid having to choose a method given the target task, e.g., node classification vs. link prediction).\n\nOne remark about L278: SMP cannot be considered anymore SotA for ogbl-ppa. The current SotA is more than 10 points above the performance achieved by SMP.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kxYrBgPHjeW", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a proximity-aware graph neural network while maintaining the permutation equivariance property. The proposed model, dubbed as stochastic message passing (SMP), arguments the existing GNNs with stochastic node representations. The author proved the proposed method can model proximity-aware representations based on random projection theory. The experimental results show that the SMP can be used for multiple graphs and tasks. \n\nAlthough the proposed technique is relatively simple, the theorem shows that why such stochastic representations are beneficial for proximity-aware tasks. The experimental results also suggest that this simple technique is quite effective in many tasks. There are a few things that I'd like to comment on or ask listed below:\n\n- Multiple tasks have been conducted to show the performance of the proposed model, but it is unclear which dataset or which task requires to be proximity-aware. It would be great if there's some quantitative metric that shows the importance of proximity in a given task. For example, the number of automorphic node pairs (within k-hop) and the ratio of label (dis)agreement would be a possible metric in node classification tasks. This will characterize the differences between datasets and highlight the contribution of the proposed method. Additionally, showing some examples of automorphic node pairs and the performance on these nodes could demonstrate the difference between models.\n\n- Resampling random matrix at each epoch is emphasized multiple times in the manuscript, but without any empirical experiments. Would it be beneficial to resample this random matrix at every epoch? Although in theory, it would be possible to learn GNN that preserves node proximity, if a given task doesn't need to model proximity-aware representations, random resampling may hinder the convergence of the proposed method.\n\n- There was a bug in the official release of the P-GNN paper, which has been recently fixed (please check the GitHub pull request history at https://github.com/JiaxuanYou/P-GNN/pull/12). I wonder which codebase the authors used for the experiments. / It would be also good if there's some comment on what makes P-GNN memory hunger. Is it because of improper implementation or because of some inherent limitations?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5HVM0qdJs1V", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to add random node features to the input of message passing graph neural networks for them to become proximity-aware. The paper provides exhaustive theoretical and empirical analysis of this idea, highlighting the advantageous properties.\n\nStrengths:\n- The paper is well written.\n- The authors substantiate their claims with proofs and experiments.\n- The method and proofs seem to be mathematically sound.\n- Including the experiments in the appendix, the empirical analysis is very exhaustive and seems to be reproducible.\n- The method is simple but effective, which is good. It also does not lead to a significant computational overhead but fits nicely into the existing message passing framework with linear time complexity (in number of edges).\n- The paper provides a formal framework and analysis for a trick that has already been used successfully in practice.\n\nComments and Questions:\n- The work of Sato et al. [1] seems to be closer to this work than the authors let know. I would welcome a more in-depth discussion than given in related work, even if the paper is only on arxiv.\n- Definition 4 should go to the main text, as it is crucial for understanding.\n- The proof of Theorem 1 shows the result only for graphs with 2 connected components. I think the theorem also holds for connected graphs (with the right automorphisms), which is important. If it wouldn't, the result would not always be relevant for practice. I think the current way of proving the theorem lacks that insight and discussion. Isn't it possible to prove the theorem for all graphs with a certain automorphism, regardless of number of connected components?\n- Can the authors verify the suspicion that the non-linear variants overfit (line 270) by presenting the results on training data?\n- It might be of interest to the authors that the idea was already used in a practical graph matching method by [2] (page 5, last paragraph), although without any theoretical analysis. It is nice to have a formal framework that justifies the application of this trick.\n- In general, GNNs to solve matching tasks are a very fitting application for the proposed method, which the authors do not consider. They often rely on comparing distance measures in both domains, thus need proximity awareness. \n\nTypos:\n- Line 87: \"computationally expansive\" -> expensive\n- Line 607: \"computationally expansive\" -> expensive\n\nAll in all, there is not much to complain about. The paper achieves what it sets out to do in providing an exhaustive theoretical and empirical analysis of a simple but effective idea. The method itself is straight-forward and also not entirely novel. However, the formal framework and analysis is a contribution that is of interest to the community. Due to the shown properties and the high efficiency of the approach, the paper can have significant impact on future GNN architectures in practice. I therefore recommend to accept the paper.\n\n[1] Sato et al., Random features strengthen graph neural networks. arXiv:2002.03155 \n\n[2] Fey et al., Deep Graph Matching Consensus, ICLR 2020", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a modification of a GNN architecture by feeding random node features to bootstrap the message propagation. This enables the discriminability of automorphic node pairs with a lightweight, simple change. Experiments are reported showing improvements over baselines. 
Reviewers had mixed impressions of this work. On one hand, they found the proposed model principled and with strong empirical performance. On the other hand, they perceived a general lack of novelty and a somewhat misleading theoretical analysis. After careful review, the AC ultimately believes that this work does require an extra iteration that further solidifies the contributions and aligns the theoretical analysis with the empirical performance. In particular, the use of random initialization is folklore in the GNN literature, especially with regards to spectral methods (e.g. power iterations are typically initialized using a random vector, and these constitute the simplest forms of linear GNNs). The authors are encouraged to address these comparisons with further detail, as well as the excellent feedback given by the reviewers. 
Decision: Reject