Year: 2020

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

Graph neural networks (GNNs) are emerging machine learning models on graphs.1 One key property behind the expressiveness of existing GNNs is that the learned2 node representations are permutation-equivariant. Though being a desirable prop-3 erty for certain tasks, however, permutation-equivariance prevents GNNs from4 being proximity-aware, i.e., preserving the walk-based proximities between pairs5 of nodes, which is another critical property for graph analytical tasks. On6 the other hand, some variants of GNNs are proposed to preserve node prox-7 imities, but they fail to maintain permutation-equivariance. How to empower8 GNNs to be proximity-aware while maintaining permutation-equivariance re-9 mains an open problem. In this paper, we propose Stochastic Message Passing10 (SMP), a general and simple GNN to maintain both proximity-awareness and11 permutation-equivariance properties. Specifically, we augment the existing GNNs12 with stochastic node representations learned to preserve node proximities. Though13 seemingly simple, we prove that such a mechanism can enable GNNs to preserve14 node proximities in theory while maintaining permutation-equivariance with cer-15 tain parametrization. Extensive experimental results demonstrate the effectiveness16 and efficiency of SMP for tasks including node classification and link prediction.17
1 INTRODUCTION18
Graph neural networks (GNNs), as generalizations of neural networks in analyzing graphs, have19 attracted considerable research attention. GNNs have been widely applied to various applications20 such as social recommendation (Ma et al., 2019), physical simulation (Kipf et al., 2018), and protein21 interaction prediction (Zitnik & Leskovec, 2017).22
One key property of most existing GNNs is permutation-equivariance, i.e., if we randomly permu-23 tate the IDs of nodes while maintaining the graph structure, the representations of nodes in GNNs24 are permutated accordingly. Mathematically, permutation-equivariance reflects one basic symmet-25 ric group of graph structures. Although it is a desirable property for tasks such as node or graph26 classification (Keriven & Peyré, 2019; Maron et al., 2019b), permutation-equivariance also prevents27 GNNs from being proximity-aware, i.e., permutation-equivariant GNNs cannot preserve walk-based28 proximities between nodes such as the shortest distance or high-order proximities (see Theorem 1).29
Pairwise proximities between nodes are crucial for graph analytical tasks such as link predic-30 tion (Hu et al., 2020; You et al., 2019). To enable a proximity-aware GNN, Position-aware GNN31 (P-GNN) (You et al., 2019)1 proposes a sophisticated GNN architecture and shows better perfor-32 mance for proximity-aware tasks. But P-GNN needs to explicitly calculate the shortest distance be-33 tween nodes and its computational complexity is unaffordable for large graphs. Moreover, P-GNN34 completely ignores the permutation-equivariance property. Therefore, it cannot produce satisfactory35 results when permutation-equivariance is helpful.36
In real-world scenarios, both proximity-awareness and permutation-equivariance are indispensable37 properties for GNNs. Firstly, different tasks may require different properties. For example, recom-38 mendation applications usually require the model to be proximity-aware (Konstas et al., 2009) while39 permutation-equivariance is a basic assumption in centrality measurements (Borgatti, 2005). Even40
1In (You et al., 2019), the authors consider the special case of shortest distance between nodes and name such property as “position-aware”. In this paper, we consider a more general case of any walk-based proximity.
for the same task, different datasets may have different requirements on these two properties. Taking41 link prediction as an example, we observe that permutation-equivariant GNNs such as GCN (Kipf &42 Welling, 2017) or GAT (Velickovic et al., 2018) show better results than P-GNN in coauthor graphs,43 but the opposite in biological graphs (please see Section 5.2 for details). Unfortunately, in the current44 GNN frameworks, these two properties are contradicting, as we show in Theorem 1. Whether there45 exists a general GNN to be proximity-aware while maintaining permutation-equivariance remains46 an open problem.47
In this paper, we propose Stochastic Message Passing (SMP), a general and simple GNN to pre-48 serve both proximity-awareness and permutation-equivariance properties. Specifically, we augment49 the existing GNNs with stochastic node representations learned to preserve proximities. Though50 seemingly simple, we prove that our proposed SMP can enable GNNs to preserve walk-based prox-51 imities in theory (see Theorem 2 and Theorem 3). Meanwhile, SMP is equivalent to a permutation-52 equivariant GNN with certain parametrization and thus is at least as powerful as those GNNs in53 permutation-equivariant tasks (see Remark 1). Therefore, SMP is general and flexible in handling54 both proximity-aware and permutation-equivariant tasks, which is also demonstrated by our exten-55 sive experimental results. Besides, owing to the simple structure, SMP is computationally efficient,56 with a running time roughly the same as those of the most simple GNNs such as SGC (Wu et al.,57 2019) and is at least an order of magnitude faster than P-GNN on large graphs. Ablation studies58 further show that a linear instantiation of SMP is expressive enough as adding extra non-linearities59 does not lift the performance of SMP on the majority of datasets. Our contributions are as follows.60
• We propose SMP, a simple and general GNN to handle both proximity-aware and permutation-61 equivariant graph analytical tasks.62 • We prove that SMP has theoretical guarantees in preserving walk-based proximities and is at63 least as powerful as the existing GNNs in permutation-equivariant tasks.64 • Extensive experimental results demonstrate the effectiveness and efficiency of SMP. We show65 that a linear instantiation of SMP is expressive enough on the majority of datasets.66
2 RELATED WORK67
We briefly review GNNs and their permutation-equivariance and proximity-awareness property.68
The earliest GNNs adopt a recursive definition of node states (Scarselli et al., 2008; Gori et al.,69 2005) or a contextual realization (Micheli, 2009). GGS-NNs (Li et al., 2016) replace the recursive70 definition with recurrent neural networks (RNNs). Spectral GCNs (Bruna et al., 2014) defined graph71 convolutions using graph signal processing (Shuman et al., 2013; Ortega et al., 2018) with Cheb-72 Net (Defferrard et al., 2016) and GCN (Kipf & Welling, 2017) approximating the spectral filters us-73 ing a K-order Chebyshev polynomial and the first-order polynomial, respectively. MPNNs (Gilmer74 et al., 2017), GraphSAGE (Hamilton et al., 2017), and MoNet (Monti et al., 2017) are proposed75 as general frameworks by characterizing GNNs with a message-passing function and an updating76 function. More advanced variants such as GAT (Velickovic et al., 2018), JK-Nets (Xu et al., 2018b),77 GIN (Xu et al., 2018a), and GraphNets (Battaglia et al., 2018) follow these frameworks.78
Li et al. (Li et al., 2018), Xu et al. (Xu et al., 2018a), Morris et al. (Morris et al., 2019), and79 Maron et al. (Maron et al., 2019a) show the connection between GNNs and the Weisfeiler-Lehman80 algorithm (Shervashidze et al., 2011) of graph isomorphism tests, in which permutation-equivariance81 holds a key constraint. Maron et al. (Maron et al., 2019b) and Keriven et al. (Keriven & Peyré, 2019)82 analyze the permutation-equivariance property of GNNs more theoretically. To date, most of the83 existing GNNs are permutation-equivariant and thus are not proximity-aware. The only exception84 is P-GNN (You et al., 2019), which proposes to capture the positions of nodes using the relative85 distance between the target node and some randomly chosen anchor nodes. However, P-GNN cannot86 satisfy permutation-equivariance and is computationally expensive.87
Very recently, motivated by enhancing the expressive power of GNNs in graph isomorphism tests88 and distributed computing literature (Angluin, 1980; Linial, 1992; Naor & Stockmeyer, 1995),89 some studies suggest assigning unique node identifiers for GNNs (Loukas, 2020) such as one-hot90 IDs (Murphy et al., 2019) or random numbers (Dasoulas et al., 2019; Sato et al., 2020; Corso et al.,91 2020). For example, Sato et al. (Sato et al., 2020) novelly show that random numbers can enhance92 GNNs in tackling two important graph-based NP problems with a theoretical guarantee, namely the93
minimum dominating set and the maximum matching problem, and Fey et al. (Fey et al., 2020) em-94 pirically show the effectiveness of random features in the graph matching problem. Our work differs95 in that we systematically study how to preserve permutation-equivariance and proximity-awareness96 simultaneously in a simple yet effective framework, which is a new topic different from these ex-97 isting works. Besides, we theoretically prove that our proposed method can preserve walk-based98 proximities by using the random projection literature. We also demonstrate the effectiveness of our99 method on various large-scale benchmarks for both node- and edge-level tasks, while no similar100 results are reported in the literature.101
The design of our method is also inspired by the random projection literature in dimensionality re-102 duction (Vempala, 2005) and to the best of our knowledge, we are the first to study random projection103 in the scope of GNNs. More remotely, our definition of node proximities is inspired and inherited104 from graph kernels (Gärtner et al., 2003; Borgwardt & Kriegel, 2005), network embedding (Perozzi105 et al., 2014; Grover & Leskovec, 2016), and general studies of graphs (Newman, 2018).106
3 MESSAGE-PASSING GNNS107
We consider a graphG = (V, E ,F) where V = {v1, ..., vN} is the set ofN = |V| nodes, E ⊆ V×V108 is the set of M = |E| edges, and F ∈ RN×d0 is a matrix of d0 node features. The adjacency matrix109 is denoted as A, where its ith row, jth column and an element denoted as Ai,:, A:,j , and Ai,j ,110 respectively. In this paper, we assume the graph is unweighted and undirected. The neighborhood111 of node vi is denoted as Ni and Ñi = Ni ∪ {vi}.112 The existing GNNs usually follow a message-passing framework (Gilmer et al., 2017), where the lth113 layer adopts a neighborhood aggregation function AGG(·) and an updating function UPDATE(·):114
m (l) i = AGG({h (l) j ,∀j ∈ Ñi}),h (l+1) i = UPDATE([h (l) i ,m (l) i ]), (1)
where h(l)i ∈ Rdl is the representation of node vi in the lth layer, dl is the dimensionality, and m (l) i115
are the messages. We also denote H(l) = [h(l)1 , ...,h (l) N ] and [·, ·] is the concatenation operation. The116 node representations are initialized as node features, i.e., H(0) = F. We denote a GNN following117 Eq. (1) with L layers as a parameterized function as follows2:118
H(L) = FGNN(A,F;W), (2) where H(L) are final node representations learned by the GNN and W denotes all the parameters.119
One key property of the existing GNNs is permutation-equivariance.120 Definition 1 (Permutation-equivariance). Consider a graph G = (V, E ,F) and any permutation121 P : V → V so that G′ = (V, E ′,F′) has an adjacency matrix A′ = PAPT and a feature matrix122 F′ = PF, where P ∈ {0, 1}N×N is the permutation matrix corresponding to P , i.e., Pi,j = 1 iff123 P(vi) = vj . A GNN satisfies permutation-equivariance if the node representations are equivariant124 with respect to P , i.e.,125
PFGNN(A,F;W) = FGNN(PAPT ,PF;W). (3)
It is known that GNNs following Eq. (1) are permutation-equivariant (Maron et al., 2019b).126 Definition 2 (Automorphism). A graph G is said to have (non-trivial) automorphism if there exists127 a non-identity permutation matrix P 6= IN so that A = PAPT and F = PF. We denote the128 corresponding automorphic node pairs as CG = ⋃ P6=IN {(i, j)|Pi,j 6= 0, i 6= j}129 Corollary 1. Using Definition 1 and 2, if a graph has automorphism, a permutation-equivariant130 GNN will produce identical node representations for automorphic node pairs:131
h (L) i = h (L) j ,∀(i, j) ∈ CG. (4)
Since the node representations are used for downstream tasks, the corollary shows that permutation-132 equivariant GNNs cannot differentiate automorphic node pairs. A direct consequence of Corol-133 lary 1 is that permutation-equivariant GNNs cannot preserve walk-based proximities between pairs134 of nodes. The formal definitions are as follows.135
2Since the final layer of GNNs is task-specific, e.g., a softmax layer for node classification or a readout layer for graph classification, we only consider the GNN architecture to its last hidden layer.
Definition 3 (Walk-based Proximities). For a given graph G = (V, E ,F), we use a matrix S ∈136 RN×N to denote walk-based proximities between pairs of nodes defined as:137
Si,j = S ({vi vj}) , (5) where vi vj denotes walks from node vi to vj and S(·) is an arbitrary real-valued function. The138 length of a walk-based proximity is the maximum length of all the walks of the proximity.139
Typical examples of walk-based proximities include the shortest distance (You et al., 2019), the high-140 order proximities (a sum of walks weighted by their lengths) (Zhang et al., 2018), and random walk141 probabilities (Klicpera et al., 2019). Next, we give a definition of preserving walk-based proximities.142 Definition 4. For a given walk-based proximity, a GNN is said to be able to preserve the proximity143 if there exists a decoder function Fde(·) satisfying that for any graph G = (V, E ,F), there exist144 parameters WG so that ∀ > 0:145 ∣∣∣Si,j −Fde (H(L)i,: ,H(L)j,: )∣∣∣ < , (6) where146
H(L) = FGNN(A,F;WG). (7)
Note that we do not constrain the GNN architecture as long as it follows Eq. (1), and the decoder147 function is also arbitrary (but notice that it cannot take the graph structure as inputs). In fact, both148 the GNN and the decoder function can be arbitrarily deep and with sufficient hidden units.149 Theorem 1. The existing permutation-equivariant GNNs cannot preserve any walk-based proximity150 except the trivial solution that all node pairs have the same proximity.3151
The formulation and proof of the theorem are given in Appendix A.1. Since walk-based proximities152 are rather general and widely adopted in graph analytical tasks such as link prediction, the theorem153 shows that the existing permutation-equivariant GNNs cannot handle these tasks well.154
4 THE MODEL155
4.1 A GNN FRAMEWORK USING STOCHASTIC MESSAGE PASSING156
A major shortcoming of permutation-equivariant GNNs is that they cannot differentiate automorphic157 node pairs. To solve that problem, we need to introduce some mechanism as “symmetry breaking”,158 i.e., to enable GNNs to distinguish these nodes. To achieve this goal, we sample a stochastic matrix159 E ∈ RN×d where each element follows an i.i.d. normal distribution N (0, 1). The stochastic matrix160 can provide signals in distinguishing the nodes because they are randomly sampled without being161 affected by the graph automorphism. In fact, we can easily calculate that the Euclidean distance162 between two stochastic signals divided by a constant √ 2 follows a chi distribution χd:163
1√ 2 |Ei,: −Ej,:| ∼ χd,∀i, j. (8)
When d is reasonably large, e.g., d > 20, the probability of two signals being close is very low.164 Then, inspired by the message-passing framework, we apply a GNN on the stochastic matrix so that165 nodes can exchange information of the stochastic signals:166
Ẽ = FGNN (A,E;W) . (9)
We call Ẽ the stochastic representation of nodes. Using the stochastic matrix and message-passing,167 Ẽ can be used to preserve node proximities (see Theorem 2 and Theorem 3). Then, to let our model168 still be able to utilize node features, we concatenate Ẽ with the node representations from another169 GNN with node features as inputs:170
H = Foutput([Ẽ,H(L)]) Ẽ = FGNN (A,E;W) ,H(L) = FGNN′(A,F;W′),
(10)
3Proposition 1 in (You et al., 2019) can be regarded as a special case of Theorem 1 using the shortest distance proximity.
where Foutput(·) is an aggregation function such as a linear function or simply the identity mapping.171 In a nutshell, our proposed method augments the existing GNNs with a stochastic representation172 learned by message-passings to differentiate different nodes and preserve node proximities.173
There is also a delicate choice worthy mentioning, i.e., whether the stochastic matrix E is fixed or174 resampled in each epoch. By fixing E, the model can learn to memorize the stochastic representation175 and distinguish different nodes, but with the cost of unable to handle nodes not seen during training.176 On the other hand, by resampling E in each epoch, the model can have a better generalization177 ability since the model cannot simply remember one specific stochastic matrix. However, the node178 representations are not fixed (but pairwise proximities are preserved; see Theorem 2). In these cases,179 Ẽ is more capable of handling pairwise tasks such as link prediction or pairwise node classification.180 In this paper, we use a fixed E for transductive datasets and resample E for inductive datasets.181
Time Complexity From Eq.(10), the time complexity of our framework mainly depends on the182 two GNNs in learning the stochastic and permutation-equivariant node representations. In this paper,183 we instantiate these two GNNs using simple message-passing GNNs such as GCN (Kipf & Welling,184 2017) and SGC (Wu et al., 2019) (see Section 4.2 and Section 4.3). Thus, the time complexity of185 our method is the same as these models, which is O(M), i.e., linear with respect to the number of186 edges. We also empirically compare the running time of different models in Appendix 5.5. Besides,187 many acceleration schemes for GNNs such as sampling (Chen et al., 2018a;b; Huang et al., 2018)188 or partitioning the graph (Chiang et al., 2019) can be directly applied to our framework.189
4.2 A LINEAR INSTANTIATION190
Based on the general framework shown in Eq. (10), we attempt to explore its minimum model191 instantiation, i.e., a linear model. Specifically, inspired by Simplified Graph Convolution (SGC) (Wu192 et al., 2019), we adopt a linear message-passing for both GNNs, i.e.,193
H = Foutput([Ẽ,H(L)]) = Foutput( [ ÃKE, ÃKF ] ), (11)
where Ã = (D+ I)− 1 2 (A+ I)(D+ I)− 1 2 is the normalized graph adjacency matrix with self-loops194 proposed in GCN (Kipf & Welling, 2017) and K is the number of propagation steps. We also set195 Foutput(·) in Eq. (11) as a linear mapping or identity mapping.196 Though seemingly simple, we show that such an SMP instantiation possesses a theoretical guarantee197 in preserving the walk-based proximities.198 Theorem 2. An SMP in Eq. (11) with the message-passing matrix Ã and the number of propagation199 stepsK can preserve the walk-based proximity ÃK(ÃK)T with high probability if the dimensional-200 ity of the stochastic matrix d is sufficiently large, where the superscript T denotes matrix transpose.201 The theorem is regardless of whether E are fixed or resampled.202
The mathematical formulation and proof of the theorem are given in Appendix A.2. In addition, we203 show that SMP is equivalent to a permutation-equivariant GNN with certain parametrization.204 Remark 1. Suppose we adopt Foutput(·) as a linear function with the output dimensionality the205 same as FGNN′ . Then, Eq. (10) is equivalent to the permutation-equivariant FGNN′(A,F;W′) if the206 parameters in Foutput(·) are all-zeros for Ẽ and an identity matrix for H(L).207
The result is straightforward from the definition. Then, we have the following corollary.208 Corollary 2. For any task, Eq. (10) with the aforementioned linear Foutput(·) is at least as powerful209 as the permutation-equivariant FGNN′(A,F;W′), i.e., the minimum training loss of using H in210 Eq. (10) is equal to or smaller than using H(L) = FGNN′(A,F;W′).211
In other words, SMP will not hinder the performance4 even the tasks are permutation-equivariant212 since the stochastic representations are concatenated with the permutation-equivariant GNNs fol-213 lowed by a linear mapping. In these cases, the linear SMP is equivalent to SGC (Wu et al., 2019).214
Combining Theorem 2 and Corollary 2, the linear SMP instantiation in Eq. (11) is capable of han-215 dling both proximity-aware and permutation-equivariant tasks.216
4Similar to previous works such as (Hamilton et al., 2017; Xu et al., 2018a), we only consider the minimum training loss because the optimization landscapes and generalization gaps are difficult to analyze analytically.
4.3 NON-LINEAR EXTENSIONS217
One may question whether a more sophisticated variant of Eq. (10) can further improve the expres-218 siveness of SMP. There are three adjustable components in Eq. (10): two GNNs in propagating the219 stochastic matrix and node features, respectively, and an output function. In theory, adopting non-220 linear models as either component is able to enhance the expressiveness of SMP. Indeed, if we use221 a sufficiently expressive GNN in learning Ẽ instead of linear propagations, we can prove a more222 general version of Theorem 2 as follows.223 Theorem 3. An SMP variant following Eq.(10) with FGNN (A,E;W) containing L layers can224 preserve any length-L walk-based proximity if the message-passing and updating functions in the225 GNN are sufficiently expressive. In this theorem, we also assume the Gaussian random vectors E226 are rounded to machine precision so that E is drawn from a countable subspace of R.227
The proof of the theorem is given in Appendix A.3. Similarly, we can adopt more advanced methods228 for Foutput(·) such as gating or attention so that the two GNNs are more properly integrated.229 Although non-linear extensions of SMP can, in theory, increase the model expressiveness, they also230 take a higher risk of over-fitting due to model complexity, not to mention that the computational cost231 will also increase. In practice, we find in ablation studies that the linear SMP instantiation in Eq. (11)232 works reasonably well on most of the datasets (please refer to Section 5.4 for further details).233
5 EXPERIMENTS234
5.1 EXPERIMENTAL SETUPS235
Datasets We conduct experiments on the following ten datasets: two simulation datasets, Grid236 and Communities (You et al., 2019), a communication dataset Email (You et al., 2019), two coau-237 thor networks, CS and Physics (Shchur et al., 2018), two protein interaction networks, PPI (Hamil-238 ton et al., 2017) and PPA (Hu et al., 2020), and three GNN benchmarks, Cora, CiteSeer, and239 PubMed (Yang et al., 2016). We only report the results of three benchmarks for the node classi-240 fication task and the results for other tasks are shown in Appendix B due to the page limit. More241 details of the datasets including their statistics are provided in Appendix C.1. These datasets cover242 a wide spectrum of domains, sizes, and with or without node features. Since Email and PPI contain243 more than one graph, we conduct experiments in an inductive setting on these two datasets, i.e., the244 training, validation, and testing set are split with respect to different graphs.245
Baselines We adopt two sets of baselines. The first set is permutation-equivariant GNNs including246 GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018), and SGC (Wu et al., 2019), which are247 widely adopted GNN architectures. The second set contains P-GNN (You et al., 2019), the only248 proximity-aware GNN to date. We use the P-GNN-F version.249
In comparing with the baselines, we mainly evaluate two variants of SMP with different Foutput(·):250 SMP-Identity, i.e., Foutput(·) as an identity mapping, and SMP-Linear, i.e., Foutput(·) as a linear251 mapping. Note that both variants adopt linear message-passing functions as SGC. We conduct more252 ablation studies with different SMP variants in Section 5.4.253
For fair comparisons, we adopt the same architecture and hyper-parameters for all the methods254 (please refer to Appendix C.2 for the details). For datasets without node features, we adopt a con-255 stant vector as the node features. We experiment on two tasks: link prediction and node classifica-256 tion. Additional experiments on graph reconstruction, pairwise node classification, and running time257 comparison are provided in Appendix B. We repeat the experiments 10 times for datasets except for258 PPA and 3 times for PPA, and report the average results.259
5.2 LINK PREDICTION260
Link prediction aims to predict missing links of a graph. Specifically, we split the edges into 80%-261 10%-10% and use them for training, validation, and testing, respectively. Besides adopting those real262 edges as positive samples, we obtain negative samples by randomly sampling an equal number of263 node pairs that do not have edges. For all the methods, we set a simple classifier: Sigmoid(HTi Hj),264 i.e., use the inner product to predict whether a node pair (vi, vj) forms a link, and use AUC (area265
under the curve) as the evaluation metric. One exception to the aforementioned setting is that on the266 PPA dataset, we follow the splits and evaluation metric (i.e., Hits@100) provided by the dataset (Hu267 et al., 2020). The results except PPA are shown in Table 2. We make the following observations.268
• Our proposed SMP achieves the best results on five out of the six datasets and is highly compet-269 itive (the second-best result) on the other (Physics). The results demonstrate the effectiveness of270 our proposed method on link prediction tasks. We attribute the strong performance of SMP to its271 capability of maintaining both proximity-awareness and permutation-equivariance properties.272
• On Grid, Communities, Email, and PPI, both SMP and P-GNN outperform the permutation-273 equivariant GNNs, proving the importance of preserving node proximities. Although SMP is274 simpler and more computationally efficient than P-GNN, SMP reports even better results.275
• When node features are available (CS, Physics, and PPI), SGC can outperform GCN and GAT.276 The results re-validate the experiments in SGC (Wu et al., 2019) that the non-linearity in GNNs is277 not necessarily indispensable. Some plausible reasons include that the additional model complex-278 ity brought by non-linear operators makes the models tend to overfit and also difficult to train (see279 Appendix B.6). On those datasets, SMP retains comparable performance on two coauthor graphs280 and shows better performance on PPI, possibly because node features on protein graphs are less281 informative than node features on coauthor graphs for predicting links, and thus preserving graph282 structure is more beneficial on PPI.283
• As Email and PPI are conducted in an inductive setting, i.e., using different graphs for train-284 ing/validation/testing, the results show that SMP can handle inductive tasks as well.285
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.
Model Hits@100
SGC 0.1187±0.0012 GCN 0.1867±0.0132 GraphSAGE 0.1655±0.0240 P-GNN Out of Memory
Node2vec 0.2226±0.0083 Matrix Factorization 0.3229±0.0094 SMP-Identity 0.2018±0.0148 SMP-Linear 0.3582±0.0070
The results on PPA are shown in Table 1. SMP286 again outperforms all the baselines, showing that287 it can handle large-scale graphs with millions of288 nodes and edges. PPA is part of a recently re-289 leased Open Graph Benchmark (Hu et al., 2020).290 The superior performance on PPA further demon-291 strates the effectiveness of our proposed method292 in the link prediction task.293
5.3 NODE CLASSIFICATION294
Next, we conduct experiments of node classifica-295 tion, i.e., predicting the labels of nodes. Since296 we need ground-truths in the evaluation, we only297 adopt datasets with node labels. Specifically, for298 CS and Physics, following (Shchur et al., 2018), we adopt 20/30 labeled nodes per class for train-299 ing/validation and the rest for testing. For Communities, we adjust the number as 5/5/10 labeled300 nodes per class for training/validation/testing. For Cora, CiteSeer, and PubMed, we use the default301 splits that came with the datasets. We do not adopt Email because some graphs in the dataset are too302 small to show stable results and exclude PPI as it is a multi-label dataset.303
5The results of PGNN are slightly different compared to the paper because we adopt a more practical and common setting that negative samples in the data are not known apriori but randomly sampled in each epoch.
We use a softmax layer on the learned node representations as the classifier and adopt accuracy,304 i.e., how many percentages of nodes are correctly classified, as the evaluation criteria. We omit the305 results of SMP-Identity for this task since the node representations in SMP-Identity have a fixed306 dimensionality that does not match the number of classes.307
The results are shown in Table 3. From the table, we observe that SMP reports nearly perfect results308 on Communities. Since the node labels are generated by graph structures on Communities and there309 are no node features, the model needs to be proximity-aware to handle it well. P-GNN, which shows310 promising results in the link prediction task, also fails miserably here.311
On the other five graphs, SMP reports highly competitive performance. These graphs are commonly-312 used benchmarks for GNNs. P-GNN, which completely ignores permutation-equivariance, performs313 poorly as expected. In contrast, SMP can manage to recover the permutation-equivariant GNNs314 and avoid being misled, as proven in Remark 1. In fact, SMP even shows better results than its315 counterpart, SGC, indicating that preserving proximities is also helpful for these datasets.316
5.4 ABLATION STUDIES317
We conduct ablation studies by comparing different SMP variants, including SMP-Identity, SMP-318 Linear, and the additional three variants as follows:319
• SMP-MLP: we set Foutput(·) as a fully-connected network with 1 hidden layer.320 • SMP-Linear-GCNfeat: we set FGNN′(A,F;W′) in Eq. (10) to be a GCN (Kipf & Welling,321 2017), i.e., induce non-linearity in message passing for features. Foutput(·) is still linear.322 • SMP-Linear-GCNboth: we set both FGNN (A,E;W) and FGNN′(A,F;W′) to be a GCN (Kipf323 & Welling, 2017), i.e., induce non-linearity in message passing for both features and stochastic324 representations. Foutput(·) is linear.325
We show the results for link prediction tasks in Table 4. The results for node classification and326 pairwise node classification, which imply similar conclusions, are provided in Table 10 and Table 11327 in Appendix B.5. We make the following observations.328
• In general, SMP-Linear shows good-enough performance, achieving the best or second-best re-329 sults on six datasets and highly competitive on the other (Communities). SMP-Identity, which330 does not have parameters in the output function, performs slightly worse. The results demon-331 strate the importance of adopting a learnable linear layer in the output function, which is con-332 sistent with Remark 1. SMP-MLP does not lift the performance in general, showing that adding333 extra complexities in Foutput(·) brings no gain in those datasets.334 • SMP-Linear-GCNfeat reports the best results on Communities, PPI, and PPA, indicating that335 adding extra non-linearities in propagating node features are helpful for some graphs.336 • SMP-Linear-GCNboth reports the best results on Gird with a considerable margin. Recall that337 Grid has no node features. The results indicate that inducing non-linearities can help the stochas-338 tic representations capture more proximities, which is more helpful for featureless graphs.339
5.5 EFFICIENCY COMPARISON340
To compare the efficiency of different methods quantitatively, we report the running time of different341 methods in Table 5. The results are averaged over 3,000 epochs on an NVIDIA TESLA M40 GPU342
with 12 GB of memory. The results show that SMP is computationally efficient, i.e., only marginally343 slower than SGC and comparable to GCN. P-GNN is at least an order of magnitude slower except344 for the extremely small graphs such as Grid, Communities, or Email with no more than a thousand345 nodes. In addition, the expensive memory cost makes P-GNN unable to work on large-scale graphs.346
5.6 MORE EXPERIMENTAL RESULTS347
Besides the aforementioned experiments, we also conduct experiments on the following tasks: graph348 reconstruction (Appendix B.1), pairwise node classification (Appendix B.2), and comparing with349 one-hot IDs (Appendix B.3). Please refer to the Appendix for experimental results and correspond-350 ing analyses.351
6 CONCLUSION352
In this paper, we propose SMP, a general and simple GNN to maintain both proximity-awareness353 and permutation-equivariance properties. We propose to augment the existing GNNs with stochastic354 node representations learned to preserve node proximities. We prove that SMP can enable GNN to355 preserve node proximities in theory and is equivalent to a permutation-equivariant GNN with certain356 parametrization. Experimental results demonstrate the effectiveness and efficiency of SMP. Ablation357 studies show that a linear SMP instantiation works reasonably well on most of the datasets.358
REFERENCES359
Dana Angluin. Local and global properties in networks of processors. In Proceedings of the twelfth360 annual ACM symposium on Theory of computing, pp. 82–93, 1980.361
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi,362 Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al.363 Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261, 2018.364
Stephen P Borgatti. Centrality and network flow. Social networks, 27(1):55–71, 2005.365
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Fifth IEEE366 international conference on data mining (ICDM’05), pp. 8–pp. IEEE, 2005.367
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally368 connected networks on graphs. In International Conference on Learning Representations, 2014.369
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with370 variance reduction. In International Conference on Machine Learning, pp. 942–950, 2018a.371
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgcn: Fast learning with graph convolutional networks via372 importance sampling. In International Conference on Learning Representations, 2018b.373
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gcn: An374 efficient algorithm for training deep and large graph convolutional networks. In Proceedings of375 the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.376 257–266, 2019.377
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal378 neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.05718, 2020.379
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural380 networks for node disambiguation. arXiv preprint arXiv:1912.06058, 2019.381
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on382 graphs with fast localized spectral filtering. In Advances in neural information processing systems,383 pp. 3844–3852, 2016.384
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph385 matching consensus. In International Conference on Learning Representations, 2020.386
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient387 alternatives. In Learning theory and kernel machines, pp. 129–143. Springer, 2003.388
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural389 message passing for quantum chemistry. In International Conference on Machine Learning, pp.390 1263–1272, 2017.391
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains.392 In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2,393 pp. 729–734. IEEE, 2005.394
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings395 of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining,396 pp. 855–864, 2016.397
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.398 In Advances in neural information processing systems, pp. 1024–1034, 2017.399
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, YongDong Zhang, and Meng Wang. Lightgcn:400 Simplifying and powering graph convolution network for recommendation. In Proceedings of401 the 43rd International ACM SIGIR Conference on Research and Development in Information402 Retrieval, pp. 639–648, 2020.403
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta,404 and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv405 preprint arXiv:2005.00687, 2020.406
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph407 representation learning. In Advances in neural information processing systems, 2018.408
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In409 Advances in Neural Information Processing Systems, pp. 7090–7099, 2019.410
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational411 inference for interacting systems. In International Conference on Machine Learning, pp. 2688–412 2697, 2018.413
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-414 works. In Proceedings of the 6th International Conference on Learning Representations, 2017.415
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:416 Graph neural networks meet personalized pagerank. In International Conference on Learning417 Representations, 2019.418
Ioannis Konstas, Vassilios Stathopoulos, and Joemon M Jose. On social networks and collaborative419 recommendation. In Proceedings of the 32nd international ACM SIGIR conference on Research420 and development in information retrieval, pp. 195–202, 2009.421
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for422 semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.423
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural424 networks. In International Conference on Learning Representations, 2016.425
Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193–426 201, 1992.427
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con-428 ference on Learning Representations, 2020.429
Jianxin Ma, Chang Zhou, Peng Cui, Hongxia Yang, and Wenwu Zhu. Learning disentangled repre-430 sentations for recommendation. In Advances in Neural Information Processing Systems 32, pp.431 5712–5723. 2019.432
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph433 networks. In Advances in Neural Information Processing Systems, pp. 2156–2167, 2019a.434
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph435 networks. In International Conference on Learning Representations, 2019b.436
Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions437 on Neural Networks, 20(3):498–511, 2009.438
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M439 Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In440 Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115–441 5124, 2017.442
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav443 Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks.444 In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.445
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling446 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,448 24(6):1259–1277, 1995.449
Mark Newman. Networks. Oxford university press, 2018.450
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst.451 Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106452 (5):808–828, 2018.453
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre-454 sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge455 discovery and data mining, pp. 701–710, 2014.456
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural457 networks. arXiv preprint arXiv:2002.03155, 2020.458
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.459 The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2008.460
Kakade Sham and Shakhnarovich Greg. Random projections. CMSC 35900 (Spring 2009) Large461 Scale Learning, 2020. URL https://ttic.uchicago.edu/˜gregory/courses/462 LargeScaleLearning/lectures/jl.pdf. [Online; accessed 4-September-2020].463
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls464 of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS465 2018, 2018.466
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg-467 wardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539–468 2561, 2011.469
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The470 emerging field of signal processing on graphs: Extending high-dimensional data analysis to net-471 works and other irregular domains. IEEE signal processing magazine, 30(3):83–98, 2013.472
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale473 information network embedding. In Proceedings of the 24th international conference on world474 wide web, pp. 1067–1077, 2015.475
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua476 Bengio. Graph attention networks. In Proceedings of the 7th International Conference on Learn-477 ing Representations, 2018.478
Santosh S Vempala. The random projection method, volume 65. American Mathematical Soc.,479 2005.480
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of481 the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp.482 1225–1234, 2016.483
Duncan J Watts. Networks, dynamics, and the small-world phenomenon. American Journal of484 sociology, 105(2):493–527, 1999.485
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim-486 plifying graph convolutional networks. In International Conference on Machine Learning, pp.487 6861–6871, 2019.488
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural489 networks? In International Conference on Learning Representations, 2018a.490
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie491 Jegelka. Representation learning on graphs with jumping knowledge networks. In International492 Conference on Machine Learning, pp. 5453–5462, 2018b.493
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning494 with graph embeddings. In Proceedings of the 33rd International Conference on International495 Conference on Machine Learning-Volume 48, pp. 40–48, 2016.496
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International497 Conference on Machine Learning, pp. 7134–7143, 2019.498
Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu. Arbitrary-order499 proximity preserved network embedding. In Proceedings of the 24th ACM SIGKDD International500 Conference on Knowledge Discovery & Data Mining, pp. 2778–2786, 2018.501
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue502 networks. Bioinformatics, 33(14):i190–i198, 2017.503
A THEOREMS AND PROOFS504
A.1 THEOREM 1505
Here we formulate and prove Theorem 1.506
Theorem 1. For any walk-based proximity function S(·), a permutation-equivariant GNN cannot507 preserve S(·), except the trivial solution that all node pairs have the same proximity, i.e., Si,j =508 c,∀i, j, where c is a constant.509
Proof. We prove the theorem by contradiction. Assume there exists a non-trivial S(·) which a510 permutation-equivariant GNN can preserve. Consider any graph G = (V, E ,F) and denote N =511 |V|. We can create G′ = (V ′, E ′,F′) with |V ′| = 2N so that:512
E ′i,j =  Ei,j if i ≤ N, j ≤ N Ei−N,j−N if i > N, j > N 0 else , F′i,: = { Fi,: if i ≤ N Fi−N,: if i > N . (12)
Basically, we generate two “copies” of the original graph, one indexing from 1 to N , and the other513 indexing from N +1 to 2N . By assumption, there exists a permutation-equivariant GNN which can514 preserve S(·) in G′ and we denote the node representations as H′(L) = FGNN(A′,F′;WG′). It is515 easy to see that node v′i and v ′ i+N in G
′ form an automorphic node pair. Using Corollary 1, their516 representations will be identical in any permutation-equivariant GNN, i.e.,517
H ′(L) i,: = H ′(L) i+N,:,∀i ≤ N. (13)
Also, note that there exists no walk from the two copies, i.e. { v′i v ′ j } = { v′j v ′ i } = ∅,∀i ≤518 N, j > N . As a result, for ∀i ≤ N, j ≤ N, ∀ > 0, we have:519
|Si,j − S(∅)| ≤ ∣∣∣Si,j −Fde (H′(L)i,: ,H′(L)j,: )∣∣∣+ ∣∣∣S(∅)−Fde (H′(L)i,: ,H′(L)j,: )∣∣∣
= ∣∣∣Si,j −Fde (H′(L)i,: ,H′(L)j,: )∣∣∣+ ∣∣∣Si,j+N −Fde (H′(L)i,: ,H′(L)j+N,:)∣∣∣ < 2 . (14)
We can prove the same for ∀i > N, j > N . The equation naturally holds if i ≤ N, j > N or520 i > N, j ≤ N since { v′i v ′ j } = ∅. Combining the results, we have ∀ > 0,∀i, j, |Si,j − S(∅)| <521 2 . Since can be arbitrarily small, the equation shows that all node pairs have the same proximity522 c = S(∅), which leads to a contraction and finishes our proof.523
Notice that in our proof, G′ can be constructed for any graph, so rather than designing one specific524 counter-example, we have shown that there always exists an infinite number of counter-examples by525 constructing automorphisms in the graph.526
Some may find that our counter-examples in the above proof will lead to multiple connected com-527 ponents. Next, we give an alternative proof maintaining one connected component (assuming the528 original graph is connected) under the assumption that the walk-based proximity is of finite length.529
Proof. Similar to the previous proof, we assume there exists a non-trivial S(·) which a permutation-530 equivariant GNN can preserve. Besides, we assume the length of S(·) is upper bounded by lmax,531 where lmax is any finite number, i.e., ∀i, j,532
Si,j = S ({vi vj}) = S ({vi vj |len(vi vj) ≤ lmax}) . (15)
Then, for a connected graph G = (V, E ,F), we create G′ = (V ′, E ′,F′) similar to Eq. (12). Specif-533 ically, denoting Ñ = N + lmax, we let G′ have 3Ñ nodes so that:534
E ′i,j =  Ei,j if i, j ≤ N 1 if N ≤ i, j ≤ Ñ + 1, |j − i| = 1 Ei−Ñ,j−Ñ if Ñ < i, j ≤ Ñ +N 1 if Ñ +N ≤ i, j ≤ 2Ñ + 1, |j − i| = 1 Ei−2Ñ,j−2Ñ if 2Ñ < i, j ≤ 2Ñ +N 1 if 2Ñ +N ≤ i, j, |j − i| = 1 1 if i = 3Ñ , j = 1 or j = 3Ñ , i = 1 0 else ,F′i,: =  Fi,: if i ≤ N 0 if N < i ≤ Ñ Fi−Ñ,: if Ñ < i ≤ Ñ +N 0 if Ñ +N < i ≤ 2Ñ Fi−2Ñ,: if 2Ñ < i ≤ 2Ñ +N 0 if 2Ñ +N < i .
(16) Intuitively, we create three “copies” of G and three “bridges” to connect the copies and thus make535 G′ also connected. It is also easy to see that nodes v′i, v ′ i+Ñ , and v′ i+2Ñ
all form automorphic node536 pairs and thus we have:537
H ′(L) i,: = H ′(L) i+Ñ,: = H ′(L) i+ ˜2N,: ,∀i ≤ Ñ . (17)
Next, we can see that the nodes in G′ are divided into six parts (three copies and three bridges),538 which we denote as V ′1 = {v1, ..., vN}, V ′2 = {vN+1, ..., vÑ}, V ′3 = { vÑ+1, ..., vÑ+N } , V ′4 =539 {
vÑ+N+1, ..., v2Ñ } , V ′5 = { v2Ñ+1, ..., v2Ñ+N } , and V ′6 = { v2Ñ+N+1, ..., v3Ñ } . Since V ′2, V ′4, V ′6540 are bridges with length lmax, any walk crosses these bridges will have a length large than lmax. For541 example, let us focus on vi ∈ V ′1, i.e., i ≤ N . If vj is in V ′3, V ′4, or V ′5 (i.e., Ñ < j ≤ 2Ñ +N ), any542 walk vi vj will either pass the bridge V ′2 or V ′6 and thus has a length larger than lmax. As a result,543 we have:544
Si,j = S ({vi vj}) = S ({vi vj |len(vi vj) ≤ lmax}) = S (∅) . (18)
If vj ∈ V ′1 or vj ∈ V ′2, i.e., j ≤ Ñ , we can use the fact that vj and vj+Ñ forms an automorphic node545 pair similar to Eq. (14), i.e., ∀ > 0, we have546
|Si,j − S(∅)| ≤ ∣∣∣Si,j −Fde (H′(L)i,: ,H′(L)j,: )∣∣∣+ ∣∣∣S(∅)−Fde (H′(L)i,: ,H′(L)j,: )∣∣∣
= ∣∣∣Si,j −Fde (H′(L)i,: ,H′(L)j,: )∣∣∣+ ∣∣∣Si,j+Ñ −Fde (H′(L)i,: ,H′(L)j+Ñ,:)∣∣∣ < 2 . (19)
Similarly, if vj ∈ V ′6, i.e., 2Ñ +N < j, we can use the fact that vj and vj−Ñ forms an automorphic547 node pair to prove the same inequality. Thus, we prove that if i ≤ N, ∀ > 0,∀j, |Si,j − S(∅)| < 2 .548 The same proof strategy can be applied to i > N . Since can be arbitrarily small, the results show549 that all node pairs have the same proximity S(∅), which leads to a contraction and finishes our550 proof.551
A.2 THEOREM 2552
Here we formulate and prove Theorem 2. Note that some notations and definitions are introduced in553 Appendix A.1.554
Theorem 2. For the walk-based proximity S = ÃK(ÃK)T , SMP can preserve the proximity with555 high probability if the dimensionality of the stochastic matrix is sufficiently large, i.e., ∀ > 0,∀δ >556 0, there ∃d0 so that any d > d0:557
P (|Si,j −Fde (Hi,:,Hj,:)| < ) > 1− δ, (20)
where H are the node representation obtained from SMP in Eq. (11). The result holds for any558 stochastic matrix and thus is regardless of whether E is fixed or resampled during each epoch.559
Proof. Our proof is mostly based on the standard random projection theory. Firstly, since we have560 proven in Theorem 1 that the permutation-equivariant representations cannot preserve any walk-561 based proximity, here we prove that we can preserve the proximity only using Ẽ, which can be562
easily achieved by ignoring H(L) in Foutput([Ẽ,H(L)]), e.g., if we set Foutput as a linear function, the563 model can learn to set the corresponding weights for H(L) as all-zeros.564
We set the decoder function as a normalized inner product:565
Fde (Hi,:,Hj,:) = 1
d Hi,:H
T j,:. (21)
Then, denoting ai = ÃKi,: and recalling Ẽ = Ã KE, we have:566
|Si,j −Fde (Hi,:,Hj,:)| = |aiaTj − 1
d Ẽi,:Ẽ
T j,:| = |aiaTj − ai
1 d EETaTj |. (22)
Since E is a Gaussian random matrix, from the Johnson-Lindenstrauss lemma (Vempala, 2005) (in567 the inner product preservation forum, e.g., see Corollary 2.1 and its proof in (Sham & Greg, 2020)),568 ∀0 < ′ < 12 , we have:569
P ( |aiaTj − ai 1
d EETaTj | ≤
′
2 (‖ai‖+ ‖aj‖)
) > 1− 4e− ( ′2− ′3)d 4 . (23)
By setting ′ = maxi‖ai‖ , we have > ′ 2 (‖ai‖+ ‖aj‖) and:570
P (|Si,j −Fde (Hi,:,Hj,:)| < ) > 1− 4e− ( maxi‖ai‖
2− maxi‖ai‖ 3)d
4 , (24) which leads to the theorem by solving and setting d0 as follows:571
4e− ( maxi‖ai‖
2− maxi‖ai‖ 3)d0
4 = δ ⇒ d0 = 4 log 4δ (maxi ‖ai‖)
3
2 maxi ‖ai‖ − 3 . (25)
572
A.3 THEOREM 3573
Here we formulate and prove Theorem 3. Note that some notations and definitions are introduced in574 Appendix A.1.575 Theorem 3. For any length-L walk-based proximity, i.e.,
Si,j = S ({vi vj}) = S ({vi vj |len(vi vj) ≤ L}) , where len(·) is the length of a walk, there exists an SMP variant in Eq. (10) with FGNN (A,E;W)576 containing L layers (including the input layer) to preserve that proximity if the following conditions577 hold: (1) The stochastic matrix E contains unique signals for different nodes, i.e. Ei,: 6= Ej,:,∀i 6=578 j. (2) The message-passing and updating functions in learning Ẽ are bijective. (3) The decoder579 function Fde(·) also takes E as inputs and is universal approximation.580
Proof. Similar as Theorem 2, we only utilize Ẽ during our proof. We use e(l)i , 0 ≤ l < L to581 denote the node representations in the lth layer of FGNN (A,E;W), i.e., e(0)i = Ei,: and e (L−1) i =582 Ẽi,:. Our proof strategy is to show that the stochastic node representations can remember all the583 information about the walks.584
Firstly, as the message-passing and updating function are bijective by assumption, we can recover585 from the node representations in each layer all their neighborhood representations in the previous586 layer. Specifically, there exist F (l)(·), 1 ≤ l < L such that:587
F (l) ( e (l) i ) = [ e (l−1) i , { e (l−1) j , j ∈ Ni }] 6. (26)
For notation conveniences, we split the function into two parts, one for the node itself and the other588 for its neighbors:589 F (l)self ( e (l) i ) = e (l−1) i ,
F (l)neighbor ( e (l) i ) = { e (l−1) j , j ∈ Ni } .
(27)
6To let F (l)(·) output a set with arbitrary lengths, we can adopt sequence-based models such an LSTM.
For the first function, if we successively apply such functions from the lth layer to the input layer, we590 can recover the input features of the GNN, i.e., E. Since the stochastic matrix E contains a unique591 signal for different nodes, we can decode the node ID from e(0)i , i.e., there existsF (0) self ( e (0) i ;E ) = i.592
For brevity, we denote applying such l + 1 functions to get the node ID as593 F (0:l)self ( e (l) i ) = F (0)self ( F (1)self ( ... ( F (l)self ( e (l) i ))) ;E ) = i. (28)
For the second function, we can apply F (l−1)neighbor to the decoded vector set so that we can recover their594 neighborhood representations in the (l − 2)th layer, etc.595
Next, we show that for e(l−1)j , there exists a length-l walk vi vj = (va1 , va2 , ..., val), where596
va1 = vi, val = vj if and only if F (0:l−1) self ( e (l−1) j ) = al = j and there exists e(l−2), ..., e(0) such597 that:598 e(l−2) ∈ F (l−1)neighbor ( e (l−1) j ) ,F (0:l−2)self ( e(l−2) ) = al−1,
e(l−3) ∈ F (l−2)neighbor ( e(l−2) ) ,F (0:l−3)self ( e(l−3) ) = al−2,
... e(0) ∈ F (1)neighbor ( e(1) ) ,F (0:0)self ( e(0) ) = a1 = i.
(29)
This result is easily verified as:599
(va1 , va2 , ..., val) is a walk⇔ Eai,aj = Eaj ,ai = 1⇔ ai ∈ Nai+1 ,∀1 ≤ i < l ⇔ ∃e(i−1) ∈ F (i)neighbor ( e(i) ) ,F (0:i−1)self ( e(i−1) ) = ai,∀1 ≤ i < l.
(30) Note that all the information is encoded in Ẽ, i.e., we can decode {vi vj |len(vi vj) ≤ L} from600 e (L−1) j by successively applying F (l) self (·) ,F (l) neighbor (·). We can also apply F (0:L−1) self to e (L−1) i to get601 the start node ID i. Putting it together, we have:602
F ( e (L−1) j , e (L−1) i ) = {vi vj |len(vi vj) ≤ L} , (31)
whereF(·) is composed ofF (l)self (·) , 0 ≤ l < L andF (l) neighbor (·) , 1 ≤ l < L. Applying the proximity603
function S(·), we have:604 S ( F ( e (L−1) j , e (L−1) i )) = Si,j . (32)
We finish the proof by setting the real decoder function Fde(·) to arbitrarily approximate this desired605 function S (F (·, ·)) under the universal approximation assumption.606
B ADDITIONAL EXPERIMENTAL RESULTS607
B.1 GRAPH RECONSTRUCTION608
To verify that our proposed SMP can indeed preserve node proximities, we conduct experiments of609 graph reconstruction (Wang et al., 2016), i.e., using the node representations learned by GNNs to610 reconstruct the edges of the graph. Graph reconstruction corresponds to the first-order proximity611 between nodes, i.e., whether two nodes directly have a connection, which is the most straight-612 forward node proximity (Tang et al., 2015). Specifically, following Section 5.2, we adopt the inner613 product classifier Sigmoid(HTi Hj) and use AUC as the evaluation metric. To control the impact614 of node features (i.e., since many graphs exhibit assortative mixing, even models only using node615 features can reconstruct the edges to a certain extent), we do not use node features for all the models.616
We report the results in Table 6. The results show that SMP greatly outperforms permutation-617 equivariant GNNs such as GCN and GAT in graph reconstruction, clearly demonstrating that SMP618 can better preserve node proximities. PGNN shows highly competitive results as SMP. However,619 similar to other tasks, the intensive memory usage makes PGNN unable to handle medium-scale620 graphs such as Physics and PubMed.621
B.2 PAIRWISE NODE CLASSIFICATION622
Besides standard node classification experiments reported in Section 5.3, we follow (You et al.,623 2019) and experiment on pairwise node classification, i.e., predicting whether two nodes have the624 same label. Compared with standard node classification, pairwise node classification focuses more625 on the relations between nodes and thus requires the model to be proximity-aware to perform well.626
Similar to link prediction, we split the positive samples (i.e., node pairs with the same label) into an627 80%-10%-10% training-validation-testing set with an equal number of randomly sampled negative628 pairs. For large graphs, since the possible positive samples are intractable (i.e. O(N2)), we use a629 random subset. Since we also need node labels as the ground-truth, we only conduct pairwise node630 classification on datasets when node labels are available. We also exclude the results of PPI since631 the dataset is multi-label and cannot be used in a pairwise setting (You et al., 2019). Similar to632 Section 5.2, we adopt a simple inner product classifier and use AUC as the evaluation metric.633
The results are shown in Table 7. We observe consistent results as link prediction in Section 5.2, i.e.,634 SMP reports the best results on four datasets and the second-best results on the other three datasets.635 These results again verify that SMP can effectively preserve and utilize node proximities when636 needed while retaining comparable performance when the tasks are more permutation-equivariant637 like, e.g., on CS and Physics.638
B.3 COMPARISON WITH USING IDS639
We further compare SMP with augmenting GNNs using a one-hot encoding of node IDs, i.e., the640 identity matrix. Intuitively, since the IDs of nodes are unique, such a method does not suffer from the641 automorphism problem and should also enable GNNs to preserve node proximities. However, theo-642 retically speaking, using such a one-hot encoding has two major problems. Firstly, the dimensional-643 ity of the identity matrix is N ×N , and thus the number of parameters in the first message-passing644 layer is also on the order of O(N). Therefore, the method will inevitably be computationally ex-645 pensive and may not be scalable to large-scale graphs. A large number of parameters will also more646 likely lead to the overfitting problem. Secondly, the node IDs are not transferable across different647 graphs, i.e., the node v1 in one graph and the node v1 in another graph do not necessarily share a648 similar meaning. But as the parameters in the message-passings depend on the node IDs (since they649 are input features), such a mechanism cannot handle inductive tasks well.7650
7One 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 on inductive datasets such
We also empirically compare such a method with SMP and report the results in Table 8. The results651 show that SMP-Linear outperforms GCNonehot in most cases. Besides, GCNonehot fails to handle652 Physics, which is only a medium-scale graph, due to the heavy memory usage. One surprising result653 is that GCNonehot outperforms SMP-Linear on Grid, the simulated graph where nodes are placed on654 a 20 × 20 grid. A plausible reason is that since the edges in Grid follow a specific rule, using a655 one-hot encoding gives GCNonehot enough flexibility to learn and remember the rules, and the model656 does not overfit because the graph has a rather small scale.657
B.4 ADDITIONAL LINK PREDICTION RESULTS658
We further report the results of link prediction on three GNN benchmarks: Cora, CiteSeer, and659 PubMed. The results are shown in Table 9. The results show similar trends as other datasets pre-660 sented in Section 5.2, i.e., SMP reports comparable results as other permutation-equivariant GNNs661 while PGNN fails to handle the task well.662
B.5 ADDITIONAL ABLATION STUDIES663
We report the ablation study results for the node classification task and pairwise node classification664 task in Table 10 and Table 11, respectively. The results again show that SMP-Linear generally665 achieves good-enough results on the majority of the datasets and adding non-linearities does not666 necessarily lift the performance of SMP.667
We also compare whether the stochastic signals E are fixed or not during different training epochs668 for our proposed SMP. For brevity, we only report the results for the link prediction task in Table 12.669 The results show that fixing E usually leads to better results on transductive datasets (recall that670 datasets except Email and PPI are transductive) and resampling E leads to better results on inductive671 datasets in general. The results are consistent with our analysis in Section 4.1.672
as Email and PPI. One plausible reason is that since the proximities of nodes are preserved even the random features per se are different (see Theorem 2), all subsequent parameters based on proximities can be transferred.
B.6 COMPARISON OF PERMUTATION-EQUIVARIANT GNNS FOR LINK PREDICTION673
To investigate the performance of linear and non-linear variants of permutation-equivariant GNNs674 for the link prediction task, we additionally report both the training accuracies and the testing accu-675 racies of SGC, GCN, and GAT in Table 13. Notice that to ensure a fair comparison, we do not adopt676 the early stopping strategy here so that different models have the same number of training epochs677 (otherwise, if a model tends to overfit, the early stopping strategy will terminate the training process678 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) are more likely to overfit, i.e.,680 the margins between the training accuracies and the testing accuracies are usually larger, than the681 linear variant SGC. Besides, though possessing extra model expressiveness, non-linear GNNs are682 also difficult to train, i.e., the training accuracies of GCN and GAT are not necessarily higher than683 SGC. The results are consistent with the literature Wu et al. (2019); He et al. (2020).684
C EXPERIMENTAL DETAILS FOR REPRODUCIBILITY685
C.1 DATASETS686
• Grid (You et al., 2019): A simulated 2D grid graph with size 20× 20 and no node feature.687 • Communities (You et al., 2019): A simulated caveman graph (Watts, 1999) composed of 20688 communities with each community containing 20 nodes. The graph is perturbed by rewiring 1%689 edges randomly. It has no node feature and the label of each node indicates which community690 the node belongs to.691
• Email8 (You et al., 2019): Seven real-world email communication graphs. Each graph has six692 communities and each node has an integer label indicating the community the node belongs to.693
• Coauthor Networks9 (Shchur et al., 2018): Two networks from Microsoft academic graph in694 CS and Physics with their nodes representing authors and edges representing co-authorships695 between authors. The node features are embeddings of the paper keywords of the authors.696
• PPI8 (Hamilton et al., 2017): 24 protein-protein interaction networks. Each node has a 50-697 dimensional feature vector.698
• PPA10 (Hu et al., 2020): A network representing biological associations between proteins from699 58 different species. The node features are one-hot vectors of the species that the proteins are700 taken from.701
8https://github.com/JiaxuanYou/P-GNN/tree/master/data 9https://github.com/shchur/gnn-benchmark/tree/master/data/npz/
10https://snap.stanford.edu/ogb/data/linkproppred/ppassoc.zip
• Cora, CiteSeer, PubMed11 (Yang et al., 2016): Three citation graphs where nodes correspond702 to papers and edges correspond to citations between papers. The node features are bag-of-words703 and the node labels are the ground truth topics of the papers.704
We summarize the statistics of datasets in Table 14.705
C.2 HYPER-PARAMETERS706
We use the following hyper-parameters:707
• All datasets except PPA: we uniformly set the number of layers for all the methods as 2, i.e., 2708 message-passing steps, and set the dimensionality of hidden layers as 32, i.e., H(l) ∈ RN×32,709 for all 1 ≤ l ≤ L (for GAT, we use 4 heads with each head containing 8 units). We use Adam710 optimizer with an initial learning rate of 0.01 and decay the learning rate by 0.1 at epoch 200.711 The weight decay is 5e-4. We train the model for 1,000 epochs and evaluate the model every 5712 epochs. We adopt an early-stopping strategy by reporting the testing performance at the epoch713 which achieves the best validation performance. For SMP, the dimensionality of the stochastic714 matrix is d = 32. For P-GNN, we use the P-GNN-F version, which uses the truncated 2-hop715 shortest path distance instead of the exact shortest distance.716 • PPA: as suggested in the original paper (Hu et al., 2020), we set the number of GNN layers717 as 3 with each layer containing 256 hidden units and add a three-layer MLP after taking the718 Hadamard product between pair-wise node embeddings as the predictor, i.e., MLP(Hi Hj).719 We use Adam optimizer with an initial learning rate of 0.01. We set the number of epochs for720 training as 40, evaluate the results on validation sets every epoch, and report the testing results721 using the model with the best validation performance. We also found that the dataset had issues722 with exploding gradients and adopt a gradient clipping strategy by limiting the maximum p2-723 norm of gradients as 1.0. The dimensionality of the stochastic matrix in SMP is d = 64.724
C.3 HARDWARE AND SOFTWARE CONFIGURATIONS725
All experiments are conducted on a server with the following configurations.726
• Operating System: Ubuntu 18.04.1 LTS727 • CPU: Intel(R) Xeon(R) CPU E5-2699 v4 @ 2.20GHz728 • GPU: NVIDIA TESLA M40 with 12 GB of memory729 11https://github.com/kimiyoung/planetoid/tree/master/data
• Software: Python 3.6.8, PyTorch 1.4.0, PyTorch Geometric 1.4.3, NumPy 1.18.1, Cuda 10.1730

Review summaries:
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.