Teleport Graph Convolutional Networks
Authors: Hongyang Gao
Shuiwang Ji
Venue:  (2021)
Keywords: over-smoothing

Abstract: We consider the limitations in message-passing graph neural networks. In message-passing operations, each node aggregates information from its neighboring nodes. To enlarge the receptive field, graph neural networks need to stack multiple message-passing graph convolution layers, which leads to the over-fitting issue and over-smoothing issue. To address these limitations, we propose a teleport graph convolution layer (TeleGCL) that uses teleport functions to enable each node to aggregate information from a much larger neighborhood. For each node, teleport functions select relevant nodes beyond the local neighborhood, thereby resulting in a larger receptive field. To apply our structure-aware teleport function, we propose a novel method to construct structural features for nodes in the graph. Based on our TeleGCL, we build a family of teleport graph convolutional networks. The empirical results on graph and node classification tasks demonstrate the effectiveness of our proposed methods.

Under review as a conference paper at ICLR 2021
TELEPORT GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
We consider the limitations in message-passingg graph neural networks. In message-passing operations, each node aggregates information from its neigh- boring nodes. To enlarge the receptive field, graph neural networks need to stack multiple message- -asggingggg graph convolution layers, which leads to the over-fitting issue and over-smoothing issue. To address these limitations, we propose tele- port graph convolution layer (TeleGCL) that uses teleport functions to enable each node aggregate information from a much larger neighborhood. For each node, teleport functions select relevant nodes beyond the local neighborhood, thereby resulting in larger receptive field. To apply our structure-aware teleport func- tion, we propose novel method to construct structural features for nodes in the graph. Based on our TeleGCL, we build a family of teleport graph convolutional networks. The empirical results on graph and node classification tasks demon- strate the effectiveness of our proposed methods.
INTRODUCTION
Graph neural networks (GNNs) have shown great capability in solving challenging tasks on graph data such node classification (Grover & Leskovec) 2016; Kipf & Welling 2017; Veličković et al.)
2017 Gao et al.] 2018), graph classification (Xu et al., 2018 Gao Ji
2019; You et al. 2019)),
2019). Most graph con- and link prediction (Zhang & Chen 2018 Chen et al. 2019 Zhou et al.
volutional networks are based on pessage-passing operations, in which each node aggregates in- formation from its neighboring nodes. To enable larger receptive field (Chen et al., 2016), GNNs need to stack multiple layers, which is straightforward but can result in several issues. Firstly, stack- ing multiple layers involves massive trainable parameters, which consequently increases the risk of over-fitting. Secondly, message-paste passing operations mostly use averaging to combine the aggregated features, which significantly reduces the distinguishability of network embeddings. From this point, GNNs that are based on message- gaasagg-psssingggg operations can not use deep network architecture due to these limitations. Some works such as Geom-GCN (Pei et al. 2020) try to solve these issues by in- volving more nodes in the feature aggregation process. However, Geom-GCN doesn't consider the original graph topology information when generating the additional set of nodes for aggregation, which can neglect some relevant nodes from structural perspective.
To address the above limitations and increase the receptive field effectively, we propose a teleport graph convolution layer (TeleGCL) that uses teleport functions to select highly-relevant nodes at the global scope. A teleport function computes relevances between the center node and other nodes beyond the local neighborhood. The nodes with particular relevances are teleported for the center node. Here, the selection of teleported nodes is not restricted by the graph topology. This enables the center node to gather information from larger neighborhood without going deep, which helps to avoid over-fitting and over-smoothing issues. In particular, we propose two teleport functions; those structure-aware and feature-aware teleport functions. They compute the nodes' relevances from graph structural perspective and node features perspective, respectively. Based on our TeleGCL, we build a family of teleport graph convolutional networks. The empirical results on graph and node classification tasks demonstrate the effectiveness of our proposed methods.
2 BACKGROUND AND RELATED WORK
In this section, we describe message paatgggg operations on graph data and geometric graph convo- lutional networks. Graph neural networks (Fan al. 2019 Wu et al. 2019 Morris et al. 2019 Wul

---

Under review as a conference paper at ICLR 2021
et al. 2020) have achieved state-of-the performances various challenging tasks in the field of network embedding. The mainstream of graph deep learning operations follows a message-passsing schema. In pesssag--psssnn operation, each node sends its features, known message, to its neighboring nodes in the graph. Then each node aggregates messages from its neighborhood and uses them to update its features. When combing the aggregated features, different strategies can be applied. In the graph convolution layer (GCN) (Kipf & Welling 2017). features from neigh- boring nodes are given equal weights in the aggregation process. To assign different weights to different neighboring nodes, the graph attention network (Veličković et al., 2017) employs an at- tention mechanism to compute aggregation weights. Based on these pesssag--passingg operations, graph neural networks stack multiple layers, which enables larger receptive field. Recently, some research works try to perform message passing beyond the local neighborhood. pei et al. (2020) proposed to construct a continuous latent space that enables graph neural networks to perform fea- ture learning in the latent space. To be specific, first projects nodes' features to a 2-dimensional latent and continuous space. Based on the latent space, structural neighborhood is constructed based on the Euclidean distance of each pair of nodes in the 2-dimensional space. In this process, the construction of structural features does not consider the graph connectivity information in the graph. Thus, the structural neighborhood in (Pei et al., 2020) is still built on node features without considering the graph topology. In this work, we propose method to generate structure-aware fea- tures for each node. In particular, we use the graph connectivity and similarity information with the neighboring nodes and construct a feature vector for each node. By considering graph connectivity, our constructed structural features can reflect graph topology information.
3 TELEPORT GRAPH CONVOLUTIONAL NETWORKS
In this work, we propose the teleport graph convolution layer (TeleGCL) that enables a center node to aggregate information beyond regular neighborhood structure by using some teleport functions. To enable effective node teleportation, we propose two teleport functions from structure- and feature-aware perspectives. Specifically, we propose a novel method to construct structural features for nodes, which can be used by structure- aware functions to select relevant nodes. Based our TeleGGI, we propose the teleport graph convolutional networks for network embedding learning.
3.1 LIMITATIONS OF MESSAGE-PASSIAE OPERATIONS
Currently, most graph convolution networks are based on pesssage-passing operations. In a message- passing operation, each node aggregates information from its neighboring nodes that usually are the one-hop neighborhood. Intuitively, it is beneficial to use information from a large neighborhood for network embedding learning. To enlarge the receptive field, a straight way is to stack multiple gesssag-passingg layers. A graph convolutional network with A: layers enables nodes to receive infor- mation from a k-hop neighborhood. However, this method results in two issues. Firstly, it increases the risk of over-fitting by involving much more trainable parameters. The number of trainable pa- rameters in the network increases when stacking multiple layers. Unlike regular convolutional neural networks, there is no effective graph pooling layer that can enlarge the receptive field without in- volving trainable parameters. Stacking many graph convolution layers will inevitably increase the risk of over-fitting. Secondly, stacking multiple layers will reduce the distinguishability of network embeddings, which is often referred to as the over-smoothing issue (Pei et al. 2020). Due to the invariant property in graph structures, message-passinngg the aggregation process (Kipf & Welling 2017 Gao et al. 2018). Averaging operation is usually used for information aggregation from the neighborhood. Consequently, information from relevant distant nodes will be diluted and each node carries similar information. In this work, we propose teleport graph convolution layer address this issue. This layer enables each node to aggregate information from a set of relevant nodes that are not directly connected to the center node in the original graph structure. Teleport functions are used to determine the relevant nodes from different perspectives.
operations cannot learn trainable weights in
3.2 TELEPORT GRAPH CONVOLUTION LAYER
To address the limitations in message- paggggnggggnnggggge operations, we propose the teleport graph convolution layer (TeleGCL)) which enables nodes aggregate information beyond their local neighborhoods.
2

---

Under review as a conference paper at ICLR 2021
Figure 1: Illustration of our proposed teleport graph convolution layer. In this layer, the center node (green node) aggregates information from its local neighborhood (blue nodes), feature-aware neighborhood (purple nodes), and senecture-wwar neighborhood (yellow nodes).
In this layer, employ multiple teleport functions generate neighborhoods for each node. The teleport functions select some nodes that are relevant but not directly connected. Since these nodes teleported from global context, the receptive field of each node be effectively enlarged. We require these functions to be permutation invariant such that the property retains in this layer.
VI, each node ture vector V E Rdd and each edge vu,v) E E connects node u and node e in the graph. X = [x], Z2...., xr Rdxx and A ROx* are the feature matrix and adjacency matrix, re- spectively. A teleport function g(v, G) - N takess input node and outputs neighborhood N that includes of relevant nodes for node e's feature aggregation. Section 3.3 and Section 3.4 propose two teleport functions that can construct structure-aware and feature- hoods. Suppose we have m teleport functions, node e aggregates information from a neighborhood N (Ni(v), Ni. (t)).. where Ni(e) {u/u E V. (v, u) E} is the local neighborhood and (o(D) = ( G) is a neighborhood created by the 7th teleport function. Based on this neighborhood, the layer-wise propagation of TeleGCL for node is formulated as
Given graph G EV, where
V is associated with a fea-
neighbor-
Nm.
Σ MEN(())
x (E-1)
[N(O]
where denotes an activation function such as ReLU (Nair & Hinton, 2010 By using teleport functions, node can aggregate features beyond the local neighborhood, thereby leading larger receptive field.
In Section 3.2 we propose the teleport graph convolution layer that enables feature aggregation regardless of the original graph structure. A TeleGCL highly depends on teleport functions which select distant nodes the feature aggregation process. In previous works (Pei al. 2020), teleport functions are mainly based node features while neglecting the graph structural information. The graph topology information should be considered to include nodes that share same structural patterns such graph motifs (Ren & Jin 2020). In this section, propose two teleport functions; those are structure-awar teleport function and fcature-aware teleport function. They select teleport nodes based graph topology and node features, respectively.
3.3 STRUCTURE-AWARE TELEPORT FUNCTION
Structure-aware teleport function focuses on selecting nodes based on the graph topology. In graph, the nodes that share the same structural pattern contain related features. It desirable for node to aggregate information from these relevant nodes. A structure-aware function can be used to capture relevant nodes from a graph structural perspective. With structure-aware function, the teleported nodes for node u selected as:
N.(v) = {ulu E (. & E,t,(,,u)> 01),
(2)
where (u, u) is a structure-ane aware function that computes the relevance two nodes from struc- tural perspective. Here, 0, is used to determine if node is relevant.
In this work, we propose a novel structure-an aware teleport function, which computes the relevance of two nodes by checking if they share the same structural pattern. Our proposed method is based
3

---

Under review as a conference paper at ICLR 2021
0.37
compute
0.37
0.27
rank
0.29
k select
0.37
0.29
0.27
0.27
0.19
Figure 2:
Illustration of our proposed method construct structural features for node. Given center node (green node), we first compute similarity scores between and each of its neighboring nodes. Then, rank these scores and select the k-largest values to form its structural feature vector.
on an intuition that the nodes with the same structural pattern have similar connections with their neighboring nodes. From this point, create structure feature vector for each node, which can reflect its structural pattern such as graph motifs. For each node, we first compute its similarity scores with its neighboring nodes. Then we rank these similarity scores and them the structural feature of this node. To be specific, the structural feature vector for node is constructed as
w. - Rv:
ERR"
idæ, ranks (w, o A.,),
EIR
yo = w. (idæ:);
ER
(5)
where o denotes an element- vector multiplication, and A., is the thth column of the adjacency matrix. rank; operator ranks the similarity scores and outputs the indices the top-k values in w., w. (ida,)) returns subset of rows in w, indexed by idæ..
We first compute the similarity scores between node v and neighboring nodes in Eq. 3 Each element w,,v in w, measures the similarity between node and node In Eq. 44). rank these similarity scores and select the k-largest values in w., The indices of the selected values are stored in idæ., Using indices idæ,, operations on each node, we can obtain a structural feature matrix Y = [81, ./...... yn E R for all nodes in the graph. In this way, the structural feature vector is constructed from similarity scores between the center node and its neighboring nodes. These similarity scores encode its connectivity pattern with surrounding nodes, thereby reflecting the structural information in the graph.
extract structural feature vector ye from w., By repeating these
Based on structural features, we use dot product to compute the relevance of node u and node u: (u, v) softmax (8" yc), which can measure relevance from the perspectives of both angle and magnitude in an efficient way. As illustrated in Eq. (2). the teleport nodes can be selected based on our constructed structural features.
3.4 FEATURE-AWARE TELEPORT FUNCTION
In feature-aware teleport function, the teleported nodes selected based node features. A feature-aware teleport function can select highly relevant nodes based on their features. By using this function, the teleported nodes for node are selected as:
N (v) {ulu V, (v,,) u) & E,ty(u, 02).
(6)
where (v, u) is a teleport function. 0g is a threshold to determine if node is teleported.
Notably, Geom-GCN (Pei al.) 2020) uses special case of this feature-aware teleport function. In Geom-GCN, node features are projected into a 2-dimensional space then the Fuclidean distance computed and used. The structural features in Geom-GCN are based on the latent space without considering graph topology information. The time complexity of this function is O(2d).
In our Feature-aware teleport function, we use dot product to compute the relevance, which is effective and can slightly reduce the computational cost. To be specific, the feature-based rele- By combining
vance between node u and node v is computed as ty(u, u) = softmax(x structure-aware and feature-aware teleport functions, the neighborhood for node is defined as N(v) = (V))), (v)). In our proposed TeleGCL, each node aggregates information from nodes in neighborhood N(v).
4

---

Under review as a conference paper at ICLR 2021
TeleGCL
TeleGCL,
MLP
Pool
Figure 3: Illustration of our proposed teleport graph convolutional networks. In this example, the input graph contains five nodes, each of which has two features. We first use GCN layer to learn a new feature embedding for each node. Each of the following two blocks contains a TeleGCL and pooling layer to reduce graph size. The outputs of all convolution layers globally reduced and fed into the final multi-layer perceptron for prediction.
3.5 TELEPORT GRAPH CONVOLUTIONAL NETWORKS
Based on our TeleGCL, we build a family of teleport graph convolutional networks (TeleGCNs). Given an input graph, we first use embedding layer to learn low-dimensional continuous fea- ture embeddings for nodes in the graph. Possible choices for this embedding layer include fully- connected layer and GCN layer. Here,
GCN layer to learn feature embeddings. Then several convolutional blocks are stacked to gradually learn network embeddings. In each convo- lutional block, we use our TeleGCL to learn high-level feature embedding, and a pooling layer to reduce the graph size and involve more non non-linearity. Here, we use a sampling- method to retrain original graph structures and reduce the risk of over-fitting. Specifically, top-k pooling (Gao & Ji 2019) layers in our model. Finally, we stack the outputs of all TeleGCLs and the output of the first GCN layer. To deal with variable graph sizes in terms of the number of nodes in a graph, we employ several global pooling layers such as averaging, maximization, and summation reduce these outputs into vectors. These feature vectors are concatenated and fed into a multi-layer perceptron (MLP) for prediction.
pooling
4 EXPERIMENTS
In this section, we conduct experiments on graph classification tasks to evaluate our proposed meth- ods. We compare our teleport graph convolutional networks (TeleGCNs) with previous state-of-the- art models. We conduct ablation studies to investigate the contributions of our proposed teleport functions. Some experiments are performed study the impact of thresholds in teleport functions. Our code and detailed experimental setups are available in the supplementary material.
4.1 RESULTS ON GRAPH CLASSIFICATION TASKS
We evaluate our proposed TeleGCL and TeleGCNs on graph classification tasks. We compare our TeleGCNs with the previous model seven datasets including PROTEINS (Borgwardt et al. 2005
COLLAB, D&D (Dobson & Doig 2003). IMDB-MULTI (Yanardag Vishwanathan (215aa) REDDIT-BINARY, REDDIT-MULTI-S
and REDDIT-MULTI-22X (Yanardag & Vishwanathan
20156). These datasets are benchmarking graph datasets and are widely used for evaluation this community. Notably, these datasets have no test dataset. The common practice (Xu et 2018 Ying et al., 2018: Gao & Ji 2019: Lee et al. 2019) is to run 10-fold cross-validation on the train- ing dataset and report the average accuracy (%) with standard deviation. We choose six previous state-of-the-an models as baseline models (Shervashidze et al.) 2011 Niepert et al., 2016). We strictly follow the same practices as previous works. In bioinformaties datasets such as PROTEINS and D&D, we use original node features in the datasets. In social network datasets like REDDIT- BINARY and IMDB-MULTT, we use node degrees as their initial features. The hyper-parameters in TeleGCNs are slightly tuned D&D dataset and migrated to other datasets with slightly different selections.
The experimental results on graph classification tasks are summarized in Table | Here, we report the graph classification accuracies with standard deviations. It can be seen from the results that our proposed TeleGCNs achieve significantly better performances than previous ofte-off-hhe-rt models on six out seven datasets. To be specific, our TeleGCNs outperform previous models by margins of 1.4%, 2.4 3.4, 21.7%. 4.6%, 1.9%, and 5.6% PROTEINS, COLLAB, D&D, MMDB-MUL.T,,
5

---

Under review as a conference paper at ICLR 2021
Table 1: Results on graph classification tasks using PROTEINS, COLLAB, D&D, IMDR-MULTI, REDDIT-BINARY, REDDIT-MULTI-SK, and REDDIT-MULTI-I2K datasets. We compare our TeleGCNs with previous state-of-the-art models, We report the graph classification accuracies (%) with standard deviations on these datasets.
PROTEINS COLLAB
D&D
IMDBM
REDDITB
REDDITS REDDITI2
#classes
2
3
2
3
2
5
11 11929
#graphs
1113
5000
1178
1500
2000
4999
hndde
39.1
74.5
284.3
429.6
508.5
391.4
WL
75.0 + 3.1
78.9 + 1.9
78.3 1 0.6
50.9
4 3.8
81.0 1
3.1
52.5 1 2.1
44.4 + 2.1
PSCN
75.9 + 2.8
72.6 + 2.2
76.3
2.6
45.2
2.8
86.3 + 1.6
49.1
+ 0.7
41.3 + 0.8
DIFFPOOL
76.3
75.5
80.6
47.1
DGCNN
75.5 0.9
73.8 1 0.5
79.4 i 0.9
47.8 0.9
41.8 1 0.6
SAGPool
71.9
76.5
Top-k Pool 77.6
17....1111
82.4 2.9
51.8 3.7
85.5 1.3
0.8
44.5 + 0.6
GIN
76.2
80.6 1 1.9
82.0 2.7
52.3 2.8
92.4 02.422.5 2.5
57.5 1 1.5
TeleGCN
79.0 4.3
83.0 + 1.3
84.1 2.9
56.9 3.2
94.3 0.7
56.6 +
50.1 2.1
+ 1.3
REDDIT- and REDDIT-MULLT-12K datasets. The results above show that our TeleGCNs consistently yield effectiveness of our methods. By using teleport functions, TeleGCL can rapidly and effectively increase the receptive fields without involving massive trainable parameters.
performances on graph classification tasks, which demonstrate the
4.2 PERFORMANCE STUDY ON SMALL DATASETS
The experimental studies in Section 4.1 on relatively large datasets in terms of the num- ber of graphs demonstrate the effectiveness of our proposed methods. In this section, we conduct experiments to study the perfor- mances of our TeleGCNs on three relatively small datasets; those are MUTAG (Wale et al. 2008). PTC (Toivonen et al. 2003), and IMDB- BINARY Yanardag & Vishwanathan 2015a). MUTAG and PTC are bioinformatics datasets,
Table 2: Results on graph classification tasks us- ing MUTAG, PTC, and IMDB-BINARY datasets. We compare our TeleGCNs with previous state- of-the-art models. We report the graph classifica- tion accuracies with standard deviations.
MUTAG
PIC
IMDBB
#classes
2
2
#graphs
188
344
1000
#nodes
17.9
25.5
19.8
while MDB-BINARY is a popular social net-
WL
90.4 = 5.7
59.9
4.3
73.8 + 3.9
PSCN
92.6 = 4.2
60.0 + 4.8
71.0 : 2.2
work dataset. We follow the same experimental setups previous works (Xu et al. 2018 Ying ctt al. 2018 Gao Ji 2019). The experimental setups for experiments plementary material. The experimental results
DGCNN
85.8 1.7
58.6
2.4
70.0 + 0.9
Top-k & Pool
87.2 = 7.8
64.7 6.8
75.4
GIN
90.0 8.8
64.6
+ 7.0
75.1 5.1
provided in the sup-
TeleGCN
93.5 6.8
73.8
3.7
79.8 2.5
summarized in Table 2 Due to the lack of testing datasets, follow the common practices in previous works (Xu et al. 2018 Ying et al., (018)) and report the average accuracies by running 10-fold cross-validation on the training dataset. can be seen from the results that our TeleGCNs achieve promising results on these relatively small datasets. Our TeleGCNs outperform previous models by margins of 0.9%, 9.1%, 1,, and 4.4% on MUTAG, PTC, and AMDB-BINARY datasets. The good performances on small datasets demonstrate that our proposed TeleGCL can effectively increase the receptive field without increasing the risk of over-fitting. To be specific, TeleGCL achieves a larger receptive field by using teleport functions, which teleport relevant nodes without using extra trainable parameters.
4.3 ABLATION STUDY OF TELEPORT FUNCTIONS
In this section, we conduct experiments to study the contributions of our proposed teleport func- tions to the overall performances. In our TeleGCL, we use both structure-aware and feature-aware teleport functions enlarge the receptive fields without stacking many graph convolution layers. The promising results in previous sections have demonstrated the effectiveness of our methods. To investigate the individual contributions of each teleport function, we build multiple networks with

---

Under review as a conference paper at ICLR 2021
the same network architecture as TeleGCN. To be specific, we build two networks that only use the feature-aware and structure-aware teleport functions. We denote these two net- works TeleGCN-t, and TeleGGN-I,, respec- tively. Also, we replace our TeleGCLs with GCNs in the network, which results in GCNet. We evaluate these networks on IMDB-MULI REDDIT-BINARY, and REDDIT-MULTI-BE datasets. To ensure fair comparisons, we use the same experimental setups for these net- works. The experimental results are summa- rized in Table can be seen from the results that the best performances are achieved when two teleport functions are used. The networks
Table 3: Comparison of our TeleGCNs with the networks using the same network architecture with TeleGCL. replaced by GCN (denoted as GC- Net) and the networks only with structure-aware teleport function (denoted as TeleGGN-L,) and that with feature-aware teleport function (denoted as TeleGCN-ty) respectively. We report the graph classification accuracies with standard deviations on three datasets.
IMDBM
REDDITB
REDDITI2
GCNet TeleGCN-I,
55,9 = 4.4
93.2 1.5
49.1 + 1.5
56.8
- 3.6
94.1 + 0.9
49.9 1.4
TeleGCN-fy 56,4
= 3.6
93.5 : 1.4
49,9 + 1.1
TeleGCN
56.9 = 3.2
94.3 = 0.7
50.1 E 1.3
with teleport functions significantly outperform GCNet by margins of 1.0%, 1.1%, and 1.0% on IMDB-MULTI, REDDIT-BINARY, and REDDIT-MULTI-IX datasets. The results demonstrate the promising contributions of teleport functions.
4.4 COMPARISON WITH GEOM-GCN ON NODE CLASSIFICATION TASKS
In previous sections, we evaluate our methods using graph classification tasks under inductive settings. Here, we conduct experiments to eval- uate our methods on node classification tasks. We compare our TeleGCN with GCN, GAT, and Geom-GCN GCN on Chameleon and Squirrel datasets (Rozemberczki et al., 2019). To ensure fair comparisons, we use the same experimental setups Geom-GCN. The statistics of datasets and results are summarized in Table 4 From
Comparison results of our TeleGCNs with GCN, GAT, and Geom-GCN on node clas- sification tasks. We report the node classification accuracies Chameleon and Squirrel datasets. Squirrel
Table 4:
Chamelcon
GCN
28.2
24.0
GAT
42.9
30.0
CCom-GCN
60.9
38.1
TeleGCN
62.0
39,1
the results, we can see that our TeleGCN outperforms previous models by margins of 1.1% and 1.0% on Chameleon and Squirrel datasets, respectively. This demonstrates the superior performances of our TeleGCN over previous state-of-the-art models.
4.5 PERFORMANCE STUDIES OF TIRESHOLDS TELEPORT FUNCTIONS
In our proposed TeleGCL, teleport functions employ thresholds to determine if the relevance of nodes is significant. Thus, the threshold is a very important hyper-parameter in our pro- posed methods. It controls the number of nodes teleported in the feature aggregation process. In this section, we conduct experiments to in- vestigate how different threshold values affect the performance of TeleGCN models. In our
82%
-B-DAD PROTEINS MODS-BNARY
81%
TeleGCNs, all teleport functions share the same threshold that is a/IV). This can help to ac- commodate input graphs with variable sizes. In the experiments of previous sections, we set the hyper-parameter a to 2. Here, we vary the thresholds in TeleGCNs and evaluate the resulting networks on D&D, PROTEINS, and IMDB-MULTI datasets. We report the graph classification accuracies (%) illustrated in Figure As demonstrated in the figure, the model achieves the best performance when a = 2. When the threshold is small, many nodes are teleported for feature aggregation, thereby leading to an over- smoothigg problem. As the threshold increases, fewer nodes are selected and the receptive field is not effectively enlarged.
78%
Figure 4: Comparison of TeleGCNs with teleport functions of different thresholds on PTC, PRO- TEINS, and REDDIT-BINARY datasets.
7

---

Under review as a conference paper at ICLR 2021
Figure 5: Visualization of teleported nodes. In these graphs, green nodes center nodes. Yellow nodes are teleported to center nodes by our structure-aware teleport function. From these graphs, can that the teleported nodes (yellow) share similar structural patterns center nodes.
4.6 PERFORMANCE STUDIES OF
In our structure-aware teleport function, we propose a novel method to construct structural features for teleport function to compute sim- ilarities of nodes from graph structural per- spective. Essentially, each node uses the con-
Table 5: Comparison of our TeleGCNs using dif- ferent & values when constructing structural fea- tures structure-aware teleport functions. We re- port the graph classification accuracies.
D&D
PROTEINS
IMDBB
nections with & neighborhoods to build a k- dimensional feature vector. From this point, k is an important hyper-parameter especially for our TeleGCL. In this section, we conduct exper- iments to study the impacts of different l values on overall model performances. To this end, we vary the values of ls in TeleGCLs and evaluate the resulting models on three datasets; those are D&D, PROTEINS, and graph classification performances on these datasets. The results are summarized in Table 5 We can observe from the results that the networks achieve the best performances when k = 8. As the increase of k. there is no significant improvement in network performances but the computational cost for computing relevances will increase. Thus, we set k in experiments it is the best practice for both efficiency and performance.
2
83.8
78.6
79.2
4
84.0
79.0
79.5
8
84.1
79.0
79.8
16
84.1
78.8
79.8
We report
4.7 VISUALIZATION OF TELEPORTED NODES
In our proposed structure-aware teleport function, the nodes that share the same structural patterns as the center node are teleported. In this part, we provide some visualization analysis of these teleported nodes. Here, we select three graphs from the PROTEINS dataset and visualize them in Figure The green node in each graph is the center nodes and the orange nodes are teleported by the structure-awes -ware teleport function. We can observe from these graphs that the teleported nodes share very similar graph topology information to their corresponding center nodes. The teleported nodes the first and third graphs are multiple hops away from the center nodes. The teleported nodes enable the center nodes aggregate information from larger receptive field. This demonstrates that our proposed structure-aware teleport function can select informative nodes for center nodes beyond the local neighborhood.
CONCLUSION
In this work, we address two major limitations of graph convolutional networks that are usually based on message-passing operations. To overcome the over-fitting and over-smoothing issues, we propose the teleport graph convolution layer, which utilizes teleport functions to select relevant nodes beyond the original graph structure. In particular, we propose two teleport functions; those structure-aware and feature-awer teleport functions. These two teleport functions select rel- evant nodes from structural and feature perspectives. Based on our TeleGCL, we construct teleport graph convolutional networks network embedding learning.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl.1) 1): i47-i56, 2005.
Hlang-Chich Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. Transactions on Pattern Analysis and Machine Intelligence, 2016.
Zhengdao Chen, Joan Bruna Estrach, and Lisha Li. Supervised community detection with line graph neural networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
Paul D) Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 337 2003.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. International Conference on Machine Learning. pp. 2083-2092 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424. ACM, 2018
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. 864. ACM, 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. The International Conference on Learning Representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference on Learning Representations, 2017.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings The 36th International Conference on Machine Learning, 2019.
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, volume 33, pp. 4602-4609, 2019.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 807-814, 2010.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International Conference Machine Learning, pp. 2014-2023, 2016.
Hongbin Pei. Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint S.ii:2000.052877 2020.
Weikai Ren and Ningde Jin. Sequential limited penetrable sabbilitygrapple motifs. Nonlinear Dy-
namics, pp. 1-10, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint arXiv: /3021, 2019.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhom, and Karsten M Borg- wardt. Weisneille-lehman graph kernels. Journal of Machine Learning Research, 12(Sep))2539- 2561, 2011.

---

Under review as a conference paper at ICLR 2021
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, 1lya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, ((LI):1929-1988, 2014.
Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics,
2003.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2017.
Nikil Wale, lan A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008
Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. Session-based rec- ommendation with graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 346-353, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008222 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemnels. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 13741 ACM, 2015a.
Pinar Yanardag and SVN Vishwanathan. structural smoothing framework for robust graph com- parison. In Advances in Neural Information Processing Systems, pp. 1134-2142, 2015b.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810, 2018
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143, 2019.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Kai Zhou, Tomasz P Michalak, Marcin Waniek, Talal Rahwan, and Yevgeniy Vorobeychik. Attack- ing similarity-based link prediction in social networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 305-313, International Founda- tion for Autonomous Agents and Multiagent Systems, 2019.
10

---

Under review as a conference paper at ICLR 2021
A APPENDIX
In this section, we introduce the experimental setup for our experiments. In this work, we mainly utilize graph classification tasks demonstrate the effectiveness of our proposed methods. We con- duct experiments on ten datasets; those are PROTEINS, COLLAB, D&D, IMDB-BINARY, IMDB- MULTI, MUTAG, PTC, REDDIT-BINARY, REDDIT-MULTISK and REDDIT-MULTII2, In our proposed TeleGCNs, we use GCN layer as the initial embedding layer. After that, three blocks as described in Section B.5 are stacked before the final multi- layer perceptron.
each block, we use TeleGCI. and gPool layer (Gao & Ji 2019). The output features of the initial GCN and TeleGCLs are reduced to three 1-dimensional feature vectors using global max, glohal averaging, and global summation operations. These feature vectors concatenated and fed into a two-layer perceptron. The number hidden neurons 512. In each convolutional layer, we apply a dropout (Srivastaval et al. 2014) the feature matrix. In the multi-layer perceptron, also dropout input feature tuning is performed on the D&D dataset with slight changes on other datasets. The details of syper-parameters summarized in Table
vectors. The
Table 6: Syper-parametent for each dataset used in this work.
tel tel thred
layer dim
net drop
cls drop
net act
cls act
PROTEINS
2
64
0.3
0.3
ELU
EL.U
COLLAB
2
64
0.3
0.2
ELU
ReLU
D&D
2
0.3
ELU
ELU
IMDBB
2
48
0.3
0.2
LeakyReLLU
ELU
IMDBM
2
48
0.1
0.1
LeakyReLU
ELU
MUTAG
2
ELU
PTC
8
2
64
0.2
0.2
ELU
ELU
REDDITB
2
64
0.1
0.01
ELU
ELU
REDDITS
2
64
0.01
ELU
REDDITI2 8
2
64
0.0
0.01
ELU
ELU
On each dataset, we run experiments for 200 epochs by using an Adam optimizer (Kingma & Ba 2013). The learning rate is 0.001 with weight decay of 0.0008 to reduce the risk of over-fitting The batch size is set 64, We use NVIDIA GeForce RTX 2080 GPU to train our models.
11


Reviews:
[{"review_id": "zsQNcEJn1jy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper analyzed the key issues of the existing message-passing graph convolutional networks. That is, the multiply stacked layer might be over-fitting and over-smoothing. Thus it proposed to choose the neighbors from the entire graph based on the structure-aware and feature-aware relatedness rather than simply choosing the local neighborhood. However, the motivations of the proposed structure-aware and feature-aware teleport functions are not very convincing, and Table 3 shows that the performance improvement of TeleGCN might largely be induced by model architecture rather than the proposed TeleGCL. \n\nPros:\n[1] It analyzed the potential issues of message-passing operations in conventional graph convolutional networks.\n[2] It proposed structure-aware and feature-aware teleport functions to select the neighbors from the entire graph.\n[3] The experiments show that the proposed TeleGCN outperforms the existing graph convolutional networks.\nCons:\n[1] It is confusing why the proposed TeleGCN model could avoid the risk of over-fitting. From Figure 3, it also stacks multiple teleport graph convolution layers.\n[2] Another concern is the scalability of the proposed graph convolutional networks. It might not be efficient to be applied to large-scale networks by selecting the neighbors from the entire graph for every TeleGCL. Besides, it might be more convincing to empirically compare the running time of the proposed method to the baselines.\n[3] For structure-aware teleport function, it involved the top-k similar connected neighbors as the structural feature vector. Then why not consider the high-order structural similarity or specific graph motif similarity?\n[4] From Table 3, it shows that the performance improvement of TeleGCL is very limited and the GCNet model can obtain superior performance. That might indicate that the performance improvement of TeleGCN might largely be induced by model architecture rather than the proposed TeleGCL.\n[5] It is not clear which papers the baselines, e.g., WL, PSCN, DIFFPOOL, etc., are from.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "aSDfPljIte", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The manuscript proposes a novel convolutional layer that computes a node embedding by selectively summing the nodes' embeddings neighbors at different hop distances (from 1 to m hops).  The aim of the Teleport graph convolutional layer is to solve the major limitations introduced by using the message-passing paradigm.\n\nIn the introduction, the authors highlight the main issues related to message passing paradigms and deep GNN models. The authors state that stacking multiple layers involves massive trainable parameters, which consequently increases the risk of over-fitting.  It is important to note that the issue of having several different GNN stacked layers were already faced in some papers: “The Graph Neural Network Model” by Scarselly et al. (2019), and in “Gated Graph Sequence Neural Networks” by Li et al. (2016). In these papers, the authors use recurrent models that exploit the weights sharing mechanism in order to limit the number of trainable parameters. Moreover, several works that propose an alternative to the message passing paradigm were published in the last few years. For instance, several convolutional operators are designed to consider a larger receptive field. By exploiting power series of the diffusion operator or leveraging on a multi-scale operator:  Diffusion-convolutional neural networks, Atwood et al. (2016), LanczosNet: Multi-scale deep graph convolutional networks, Liao et al. (2019), Break the ceiling: Stronger multi-scale deep graph convolutional networks, Luan et al. (2019), SIGN: Scalable Inception Graph Neural Networks, Rossi et al. (2020). Since the Teleport GCN tries to solve the same issues, all these models should be discussed in the related works section, and also considered in the comparison of the experimental results.\nIn this regards note that, even if the idea of using the features-aware or the structure-aware teleport function is interesting, the teleport convolutional layer defined in section 3.2 is not very novel in my opinion, since it seems very close to a multi-scale approach where in the same layer several exponentiations of linear diffusion operator are considered.\n\nThe main problem of this work is the empirical evaluation of the proposed method. The authors validate the models using an unfair method. Indeed the authors state “ The hyper-parameters in TeleGCNs are slightly turned on D&D dataset and are migrated to other datasets with slightly different selections' '. Using similar hyper-parameters tuned in D&D for the other datasets in my opinion is not correct. Note that the other datasets differ significantly from D&D (e.g. PROTEINS has 39.1 nodes vs 284.3; COLLAB has a significantly different number of classes and 5 times the number of graphs; etc.). It is also important to notice that all these datasets require a different type of classification task.\nMoreover, the method used by the authors differs from the “common practice”  used in (Xu et al., 2018; Ying et al., 2018; Gao & Ji, 2019; Lee et al., 2019) since in Xu et al., 2018 the authors state: “The hyper-parameters we tune for each dataset are: (1) the number of hidden units ∈ {16, 32} for bioinformatics graphs and 64 for social graphs; (2) the batch size ∈ {32, 128}; (3) the dropout ratio ∈ {0, 0.5} after the dense layer (Srivastava et al., 2014); (4) the number of epochs, i.e., a single epoch with the best cross-validation accuracy averaged over the 10 folds was selected”. The validation phase has to be executed independently for each dataset, otherwise, the obtained result will be clearly biased. Moreover, note that the impact of the validation phase in evaluating the performance of a model is discussed in “A Fair Comparison of Graph Neural Networks for Graph Classification” by Errica et al. (ICLR 2019). The results reported in this paper show that performing a fair validation procedure is crucial to evaluate the model's performance.\n\nMinor comments:\nFrom section 4.2 to section 4.7  it is almost impossible to distinguish between tables' captions and sections text.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "L7Gt8MXKv82", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n**Summary:**\n\nThe paper proposes a method to increase the receptive field of GNNs, while avoiding oversmoothing. The idea is to create extra connections by linking distant nodes based on two criteria: node feature similarity and node structure similarity. Pairs of nodes that are more similar than a threshold are connected. For structure-aware linking (teleport) a descriptor of the local structure is constructed for each node, by stacking the similarity scores to the most similar k neighbours. Computing the dot product between descriptors, gives a similarity measure of the local structure of each node. For feature-aware linking the features dot product is directly used as a measure. Experiments show that both types of teleport functions are helpful.\n\n\n**Strong Points:**\n\nClearly motivated and simple method. Carefully adding extra connections in the graph is a good idea, and the two proposed ways are sound.\n\nThe paper highlights the importance of extra connections based on structure similarity and proposes an interesting mechanism to achieve this.\n\nThe visualizations in Figure 5 are useful.\n\n**Weak Points:**\n\nThere are some concerns regarding the evaluation of the method. \n a)  The comparing methods from Table 1 have poorer performance than the GCNet baseline used in this work. The baseline GCNet represents a simple GNN formed by stacking GCN and gPool layers and Table 3 shows that it has better results than all the comparing methods from Table 1. Compared to the gap to other methods, the performance improvement brought by the proposed TeleGCL is relatively minor.\n\n b) The performance for GCNet baseline should be given for every dataset. Since on graph classification the only other results are from the Geom-GCN paper, it would really help to present the results of GCNet baseline on these datasets, with the same splits and settings as in the Geom-GCN paper.\n\nMore details about the computational complexity of the model should be given. Due to the computation of the pairwise dot product between all the nodes, the feature-aware teleport function has complexity $O( n \\times n \\times d )$. Similarly,  the structure-aware function has complexity $O( n \\times n \\times k  + n \\times n \\times d)$ (or $|E| \\times d$ for the second term, depending on the implementation). For large graphs, the quadratic term in the number of nodes is really problematic. This should be compared to the approach of Geom-GCN.\n\nSome statements regarding Geom-GCN must be clarified: “ Geom-GCN doesn’t consider the\noriginal graph topology information when generating the additional set of nodes for aggregation” or “structural neighborhood in (Pei et al., 2020) is still built on node features without considering the graph topology”. Like the current method, Geom-GCN creates links between nodes that are similar in an embedding space. Their embeddings are given by  Isomap (Tenenbaum et al., 2000), Poincare embedding (Nickel & Kiela, 2017), and struc2vec (Ribeiro et al., 2017) and it seems that they also take into account the structure of the graph. The proposed method given in Eq. 3-5 could be a good alternative to these methods, but more detailed explanations and comparisons should be given.\n\n\n**Additional Comment:**\n\nFair evaluation of graph methods on small datasets is challenging. It would have been better to evaluate the method on bigger datasets like OGB [A]. \n\n\n[A] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" arXiv preprint arXiv:2005.00687 (2020).\n\n\n**Conclusion**:\n\nThis paper presents a good and clear idea to add additional connections in a graph, but it has some issues with the evaluation and some comparisons with prior work. In this form I am inclined towards giving a  *5: marginally below* rating.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2cHEyWBv6l5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "A new architecture for graph neural networks, which the authors name as Teleport Graph Convolutional Networks (TGL), is proposed in this paper.  Teleport graph convolution layer is proposed to address the limitations in message-passing operations of graph neural networks:  1.  over-smoothing and 2. over-fitting. The architecture enables nodes to aggregate information beyond their local neighborhoods. TGL operates as follows: 1) it first aggregates neighbors as in normal graph neural networks, 2) it selects some nodes that are relevant but not directly connected using 2a) feature similarity and 2b) similarity of structure.\n\nSpecifically, TGL builds upon Pei et al., 2020, which attacks the over-smoothing problem by mapping node features to latent spaces and performing aggregation based on latent space similarity. Authors motivate their work by reporting Pei et al., 2020 ignore the graph topology, but TGL can incorporate graph topology with a similar latent space approach. Experiments are conducted on graph and node classification datasets.\n\nOverall, the paper presents some useful attempt to address problems in message passing operations, and some accuracy gains are shown in the graph and node classification datasets. The trick to aggregate based on similarity of features and structure leads to some gains compared to those only based on graph topology. However, there are some concerns lingering around. \n\nI. The presented idea, though boosts accuracy of state-of-the-art graph neural networks such as GIN or Geom-GCN, by 2%, is not quite novel. This paper is perhaps better suited for more practical venues, while ICLR is reserved for the most exciting and eye-opening research in AI. \n\nII. How does teleGCN solve over-smoothing, which is supposed to be the main problem? Not discussed in paper.\n\nIII. The motivation for how structure-aware teleport is constructed is unclear yet. Why is yellow node similar to green node in Figure 1? How are their similarity computed in equations, which is missing in paper? \n\nIV. How is the feature-aware (pink node in Figure 1) different from Pei et al., 2020?\n\nV. I recommend authors to include more state-of-the-art baselines for comparison. The following are recommended.\nhttps://arxiv.org/abs/2002.05287\nhttps://arxiv.org/abs/1905.13192\nhttps://arxiv.org/pdf/2007.02133.pdf\nhttps://arxiv.org/abs/2006.07739\n\n\nGrammar / typos: \n\nGeom-GCN doesn’t consider the -> does not\n\nthose are structure-aware teleport function  -> those that are\n\nThese similarity scores encode its connectivity -> \"its\" is unclear", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper seeks to increase receptive fields of GNNs by aggregating information beyond local neighborhoods with the idea of addressing oversmoothing and/or overfitting issues with message passing algorithms. The proposed method is simple and primarily makes use of node features and local structure similarities. In this sense the approach is related to Pei et al. Several concerns remained as articulated in the reviews, including: oversmoothing is not discussed/analyzed, performance gains are small, more extensive comparisons are needed. 

Decision: Reject