SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks
Authors: Bahare Fatemi
Seyed Mehran Kazemi
Layla El Asri
Venue:  (2021)
Keywords: Graph Neural Networks
Graph Representation Learning
Graph Structure Learning
Self-supervision

Abstract: Graph neural networks (GNNs) work well when the graph structure is provided. However, this structure may not always be available in real-world applications. One solution to this problem is to infer the latent structure and then apply a GNN to the inferred graph. Unfortunately, the space of possible graph structures grows super-exponentially with the number of nodes and so the available node labels may be insufficient for learning both the structure and the GNN parameters. In this work, we propose the Simultaneous Learning of Adjacency and GNN Parameters with Self-supervision, or SLAPS, a method that provides more supervision for inferring a graph structure. This approach consists of training a denoising autoencoder GNN in parallel with the task-specific GNN. The autoencoder is trained to reconstruct the initial node features given noisy node features as well as a structure provided by a learnable graph generator. We explore the design space of SLAPS by comparing different graph generation and symmetrization approaches. A comprehensive experimental study demonstrates that SLAPS scales to large graphs with hundreds of thousands of nodes and outperforms several models that have been proposed to learn a task-specific graph structure on established benchmarks.

Under review as a conference paper at ICLR 2021
SLAPS: SELF-SUPERVISION IMPROVES STRUCTURE LEARNING FOR GRAPH NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) work well when the graph structure is provided. However, this structure may not always be available in real-world applications. One solution to this problem is to infer the latent structure and then apply a GNN the inferred graph. Unfortunately, the space of possible graph structures grows super-epoonentilly with the number of nodes and so the available node labels may be insufficient for learning both the structure and the GNN parameters. In this work, we propose the Simultaneous Learning of Adjacency and GNN Parameters with Self-supervision, or SLAPS,, method that provides more supervision for inferring a graph structure. This approach consists of training denoising autoen- coder GNN in parallel with the task-specific GNN. The autoencoder trained to reconstruct the initial node features given noisy node features as well as structure provided by a learnable graph generator. We explore the design space of SLAPS by comparing different graph generation and symmetrization approaches. A com- prehensive experimental study demonstrates that SLAPS scales to large graphs with hundreds of thousands of nodes and outperforms several models that have been proposed to learn a task-specific graph structure on established benchmarks.
INTRODUCTION
Graph representation learning has grown rapidly and found applications in domains where data points define a graph (Chami et al. 2020 Kazemi et al. 2020). Graph neural networks (GNNs) (Scarselli al. 2008) have been a key component to the success of the research in this area. Follow- ing the success of graph convolutional networks (GCNs) (Kipf & Welling
2017) on semi-supervised node classification, several other GNN variants have been proposed for different prediction tasks on graphs (Hamilton et al. 2017 Veličković et al., 2018 Gilmer et al. 2017 Battaglia et al. 2018) and
the power of these models has been studied theoretically (Xu et al.
2019 Sato 2020).
GNNs take input a set of node features and an adjacency matrix corresponding to the graph structure, and, for each node, output an embedding that captures not only the initial features of the node but also the features and embeddings of its neighbors. The performance of GNNs highly depends on the quality of the input graph structure and deteriorates substantially when the graph structure noisy (see Zügner al. 20188] Dai et al. 2018 Fox & Rajamanickam (001)) The need for both node features and a clean graph structure impedes the applicability of GNNs to domains where one has access to set of nodes and their features but to their underlying graph structure, or only has access to noisy structure. Examples of such domains include brain signal classification (Jang al. 2019) computer-aide aided diagnosis (Cosmo et al. 2020). analysis of computer programs Johnson et al. 2020). and particle reconstruction (Qasim et al. 2019).
In this paper, we address this limitation by developing a model that learns both the GNN parameters as well as an adjacency matrix simultaneously. Since the number of possible graph structures grows super-exponentially with the number of nodes (Stanley) 1973) and obtaining node labels is typically costly, the number of available labels may not be enough for learning both the GNN parameters matrix-especiaal especially for semi-supervised node classification. Our main contribution is to supplement the classification task with a self- supervised task that helps lear a high-qualit, adjacency matrix. Our self supervisro approach masks some input features (or adds noise to them)
and an adjacency matrix
and trains separate GNN aiming at updating the adjacency matrix in such way that it can recover

---

Under review as a conference paper at ICLR 2021
the masked (or noisy) features. Introducing this self-supervision adds the inductive bias that graph structure suitable for predicting the node features is also suitable for predicting the node labels.
We experiment with several classification datasets. For datasets with graph structure, we only feed the node features to our model. The model operates on the node features and an adjacency that is learned simultaneously from data. We compare our model with different classes of methods: some which do not use the graph structure for predicting labels, some which use fixed k-Nearest Neigh- bors (kNN) graph built based on a chosen similarity metric, and some which initialize the graph with KNN but then revise it throughout the training. We show that our model consistently outperforms these methods. We also show that the self-supervised task is key to the high performance of our model. As an additional contribution, we provide an implementation for simultancous structure and parameter learning that scales to graphs with hundreds of thousands of nodes.
2 RELATED WORK
Existing methods that relate to this work can be grouped into the following categories.
Similarity Graph:
One approach for inferring a graph structure is to select a similarity metric and set the edge weight between two nodes to be their similarity (Roweis & Saul, 2000) Tenenbaum al 2000). To obtain a sparse structure, one may create a KNN similarity graph, only connect pairs of nodes whose similarity surpasses some predefined threshold, or do sampling. As an example, Gidaris & Komodakis (2019) create a (fixed) KNN graph using the cosine similarity of the node features. WWang al. (2019b) extend this idea by creating fresh graph in each layer of the GNN based on the node embedding similarities in that layer as opposed to fixing a graph solely based on the initial features. Instead of choosing single similarity metrie, Halcrow et al. (2020) fuse several (potentially weak) measures of similarity. The quality of the predictions of these methods depends heavily the choice of the similarity metric(s) and the value of k for the kNN graph, or the threshold on similarity. Furthermore, designing an appropriate similarity metric may not be straightforward in some applications.
Fully- Fully-connecttd Graph: Another approach is to assume a fully- graph and employ GNN variants such graph attention networks (Veličković et al. 20188 Zhang et al. 2018) or the trans- former (Vaswani et al.) 2017) which infer the graph structure via an attention mechanism, or infer the graph structure using additional information. This approach has been used in computer vision (e.g.,(Shail & Sigal (2119), Garcia
2009), natural language processing (e.g.. S.u et al. 2019), and few-shot learn- ing (e.g.,Garrca & Bruna] 2017), where there are not many nodes. The complexity of this approach, however, grows rapidly making it applicable only to small-sized graphs with a few thousand nodes and not scalable to the datasets we use in our experiments.
Learnable Graph: Instead of computing similarity graph the initial features, one may use
graph generator with learnable parameters. ei al. (2018b) create a fully-connected graph based on bilicar similarity function with learnable parameters. A common approach is to learn to project the
nodes to a latent space where node similarities correspond to edge weights. |Wu et al. (2018) project
the nodes to a latent space by learning weights for each of the input features. Cosmo al. (2020) and Qasim et al. (2019) use a multi-layer perceptron for projection. Yu et al. (2020) use a GNN that projects the nodes into latent space using the initial node features as well as an initial graph structure, aiming at providing a revised graph structure to the task-specific GNN. Franceschi et al.
(2199 propose a model named LDS with a bi-level optimization setup for simultaneously learning the GNN parameters and full adjacency matrix. Yang et al. (2019) update the input adjacency matrix based on the inductive bias that nodes belonging to the same class should be connected to each other and nodes belonging to different classes should be disconnected. [Cen et al. (2020) propose an iterative approach that iterates over projecting the nodes to a latent space and constructing an adjacency matrix from the latent representations multiple times. In our experiments, we compare with several approaches from this category.
Leveraging Domain Knowledge: In applications where specific domain knowledge is available, one may leverage this to guide the model toward learning specific structures. For example, Johnson eet al. (2020) leverage abstract syntax trees and regular languages in learning graph structures of Python programs that aid reasoning for downstream tasks. Jin et al. (2020b) train GNNs that are robust to adversarial attack by learning cleaned version of the input poisoned adjacency matrix
2

---

Under review as a conference paper at ICLR 2021
using the domain knowledge that clean adjacency matrices are often sparse and low-rank and exhibit feature smoothness along connected nodes.
Proposed Method: Our model falls within the learnable graph category in which use graph generators with learnable parameters to infer the adjacency matrix. We supplement the training with self-supervised objective increase the amount of supervision in learning graph structure. The self-supervised objective is generic and can be combined with many of the models described above. It is in the same vein as the auxiliary tasks in the context of multi-task learning used in computer vision, natural language processing, and reinforcement learning (see, e.g.. Daderberg et al.,
2016 Liebel & Körner 2018 Alonso & Plank 2016). The self supervise task is inspired by the successful training procedures of several recent language models such as BERT (Devlin et al. (2018) and RoBERTa (Liu et al. 2019b). Similar self- sulf-suuervision techniques have also been employed
for GNNs (Hu et al.) 2020ble c) (Jin et al. [020a]] You et al. 2020 Zhu et al. 2020). While we employ similar sulf-supervision techniques, our work differs from this line of work as we use self- supervision for learning a graph structure whereas the above methods use it to learn better (and, in some cases, transferable) GNN parameters. Specifically, we adopt the multi-task learning framework of You et al. (2020) with two differences: 1- we do not used shared parameters for the task sess-specific and self-supervised GNNs, and 2- instead of using a fixed adjacency matrix provided as input, allow both GNNs provide gradients for generator that learns generate a graph structure suitable for the downstream task.
BACKGROUND AND NOTATION
We use lowercase letters to denote scalars, bold lowercase letters denote vectors and bold upper- case letters to denote matrices. I represents an identity matrix. For a vector u, we represent its zhh element as Us For matrix M, we represent the :hh row as M, and the element the 7th row and jth column as M2. For an attributed graph, we use m and f to represent the number of nodes, edges, and features respectively, and denote the graph as G = =VV, A, X} where V = {Ui,.... Un a set of nodes, A E R is a (sparse) adjacency matrix with Aij indicating the weight of the edge from 2y to fj (A O implies no edge), and X E B f is matrix whose rows correspond to node features or attributes. A degree matrix D for a graph G is a diagonal matrix where D; = -, Agg.
Graph convolutional networks (GCNs) are a powerful variant of GNNs. For a graph 9 = (V, A, with degree matrix D, layer / of the GCN architecture can be defined as ( = o (1-)) where Á represents normalized adjacency matrix, (1-1) E Baxd represents the node repre- sentations in layer 1-1 with H (0) = X, ( E Rdd:-xxd is weight matrix, is an activation function such as ReLU, and (!)) E nuxd; is the updated node embeddings. For undirected graphs where the adjacency is symmetric. Á = D (A + I)D corresponds to row-and-colum nor- malized adjacency with self-loops, and for directed graphs where the adjacency is not necessarily symmetric, Å = D-' + I) corresponds to a row normalized adjacency matrix with self-loops.
4 SLAPS: SIMULTANEOUS LEARNING OF ADJACENCY MATRIX AND GNN PARAMETERS WITH SELF-SUPERVISION
We break our model into four components: 1) generator, 2) adjacency processor, 3) classifier, and 4) self- superviiris.... The generator takes the node features as input and generates a (perhaps sparse, non-normalized, and non-symmetric) matrix A E _"*" A is then fed into the adjacency processor which outputs A E - corresponding to a normalized, and in some cases symmetric version of Á. The classifier is a GNN that receives A as well as the node features as input and classifies the nodes into set of predefined classes. The self-supervision component is GNN that receives noisy features and the generated adjacency as input and aims at denoising the features. Figure [illuustratss the different components and in what follows, we describe each component in more detail.
3

---

Under review as a conference paper at ICLR 2021
Node features
10
-02
64
A1
Generator
Adjacency Processor
100
05
10
03
82
Non-syymmetic, non-normalied adjacency
Symmetric, normalied adjarency
Add Noise
GNN
Notyy Festures
Denoised features
Figure 1: Overview of SLAPS. At the top, generator receives the node features and produces non-symmetric, normalzzdd adjacency having (potentially) both positive and negative values (Section 4.1 The adjacency processor makes the values positive, symmetrizes and normalizes the adjacency (Section 4.2). The resulting adjacency and the node features go into GNNc which predicts the node classes (Section 4.3). At the bottom, some noise is added to the node features. The resulting noisy features and the generated adjacency go into GNNDAE which then denoises the features (Section 4.4)
4.1 GENERATOR
The generator a function G IRax + Rax* with parameters 9G which takes the node features X as input and produces A E RR=xn as output. We consider the following two generators.
Full Parameterization (FP): In this case, AG is single matrix in Rax and the generator function defined Á = Grr((;;c)
cg. That is, the generator ignores the input node features and directly optimizes the adjacency matrix. The disadvantages of this generator include adding n² parameters to the model, which limits scalability and makes the model susceptible to overfitting. and not being applicable to inductive settings where during test time predictions are to be made for nodes unseen during training. This generator is similar to the one proposed by Franceschi et al. (211)) except that they treat each element of A the parameter of Bernoulli distribution and sample graph structures from these Bernouli distributions.
MLP-KNN: In this case, IG corresponds the weights of multi-layer perceptron (MLP) and Á GMML (X; 0c) kNN(MLP(XX)) where MLP gnxf R=x is an MLP that produces a matrix with updated node representations X'; kNN R - Raxx produces sparse matrix. Let M E Ruxn with M.j- 1 if vy is among the top & similar nodes to and 0 otherwise, and let S R x such that S.y = Sim X X for some differentiable similarity function Sim (we used cosine in experiments). Then A kNN(X') M @ S where represents the Hadamard (element-wise) product. Since S is computed based on X', the gradients flow to the elements in X' (and consequently the weights of the MIP) through S. In the backward phase of our model, compute the gradients only with respect to those elements in S whose corresponding value in M (i.e. those elements Slj such that My 1): the gradient with respect the other elements O. With this formulation, in the forward phase of the network, one can first compute the matrix M using an
k-nearest neighbors algorithm and then compute the similarities in S only for pairs of nodes where MG = 1. Unlike FP, this generator can be used for the inductive setting.
Smart initialization: In our experiments, we found the initialization of the generator parameters (i.e. 0c) to be important. Let A A represent an adjacency matrix created by applying kNN function on the initial node features. One smart initialization for 0G is to initialize them a way that the generator generates A N before training starts (i.e. = A NNN before training starts). Such an initialization can be trivially done for the FP generator by initializing 0g to A but may not be straightforward for the MLP-KNN generator. To enable initializing the parameters the MLP. kNN generator in way that it generates A NNN before training starts, consider two variants of this generator. In one, hereafter referred to simply as MLP, we keep the input dimension the same throughout the layers. In the other, hereafter referred MLP-D,, consider MLPs with diagonal
4

---

Under review as a conference paper at ICLR 2021
weight matrices (i.e., except the main diagonal, all other parameters in the weight matrices zero). For both variants, we initialize the weight matrices in 8g with the identity matrix to ensure that the output of the MLP is initially the same as its input and the kNN graph created these outputs is equivalent to ANNN MLP-D can be thought of as assigning different weights to different features and then computing node similarities. Note that, alternatively, one may other MLP variants but pre-train the weights to output A NNN before the main training starts.
4.2 ADIACENCY PROCESSOR
The output À of the generator may have both positive and negative values, may be non-symmetric and non-normalized. To ensure all values of the adjacency are positive and make the adjacency symmetric and normalized, we apply the following function to A:
= 2 (((A) P(A)) D
(1)
2
Here is a function with a non-negative range. In our experiments, when using an ML.P generator, we apply the ReLU function to the elements of Á. When using the uully-parameterized (FP) gener- ator, applying ReLU results in gradient flow problem as any edge whose corresponding value in Á becomes less than equal zero stops receiving gradient updates. For this reason, for FP we apply
the ELU function to the elements of Á and then add a value of 1. The sub- sub-expressoon P(A)-P(Á)
makes the resulting matrix P(Á) symmetric. To understand the reason for taking the mean of P(A) and P(A)", assume is generated by GMPP- If vj is among the i most similar nodes to v2 and vice versa, then the strength of the connection between and ūj will remain the same. However, if, say, My is among the k most similar nodes to &4 but 6; is not among the top k for uy, then taking the average of the similarities reduces the strength of the connection between e and vy. Finally, once we have a symmetric adjacency with non-negative values, we compute the degree matrix D P(A)+ and normalize P(A)+P(()) by multiplying it left and right with D-1 2
for 2
4.3 CLASSIFIER
The classifier is function GNN R"x x R - [ax[C] with parameters θGNNE- It takes the node features X and the generated adjacency A as input and provides for each node the logits for each class. C corresponns the classes and [C] corresponds to the number of classes. We layer GCN for which AGNN. (W(1), W(2) and define our classifier as GNNc X; ŌGNNe)= ARXLU(AX (LXW())) ()() but other GNN variants can be used as well (recall that A is normalized). The training loss Le for the classification task is computed by taking the softmax of the logits to produce probability distribution for each node and then computing the cross-entropy loss.
4.4 ADDING SELF-SUPERVISION
As explained in Section in many domains, the number of labeled nodes may be insufficient for learning both the structure and the GNN parameters from data. To increase the amount of supervi- sion for learning the structure, we propose self-supervised approach based denoising autoen- coders (Vincent et al., 2008). Let GNN Rnx x R.xx -> R be a GNN that takes node features as well as a normalized adjacency produced by generator as input and provides updated node features with the same dimension as input. We train GNNDAE such that it receives a noisy ver- sion X of the features X as input and produces the denoised features X as output. Let idx represent the indices corresponding to the elements of X to which we have added noise, and Xide represent the values at these indices. The aim of the training procedure is to minimize:
LDAE L(X idz; GNNDAE X, A; IGNNNOE )
where A is the generated adjacency matrix and L is a loss function. To add noise to the input features for datasets where features consist of binary vectors, in each iteration, idæ consists of r percent of the indices of X whose values are ones and ry) percent of the indices whose values selected uniformly at random in each epoch. Both r and 7 (corresponding to the negative ratio) are hyperparameters. In this case, we add noise by setting the ones in the selected mask to zeros and L
zeros, both
5

---

GCN. The Under review as a conference paper at ICLR 2021
is the binary cross-entropy loss. For datasets where the imput features are continuous numbers, idæ consists of percent of the indices of X selected uniformly at random in each epoch. We add noise by either replacing the values at idæ with zeros by adding independent Gaussian noises to each of the features. In this case, is the mean-squared error loss.
To understand the cruciality of the proposed self-supervision, let consider scenario for training the model in Figure [ (or a model with a similar architecture) but with- out the self-supervised task. As training proceeds, assume that two unlabeled nodes U; and Vi are not directly connected to any labeled nodes. Then, since a two-layer GCN makes predictions for the nodes based on their two-hop neighbors. the edge between V and by receives no supervision a quantitative example, the original structures and maann/valdation/testt splits of Cora and Citeseer, 80.4% and 89.9% of the nodes, and consequently 64.6% and 80.8% of pairs of nodes, are not con- nected to any labeled/train nodes. no supervision is provided for some edges in the graph, after train- ing the existence and weights of these edges may end up being set randomly (or the same their ini- tialization value), which may be problematic during testing. With the self-supervised task, however, al- though these edges may not receive supervision from the main task (i.e. from GCNc), the supervision pro- vided by the self self-supervised task (i.e. from GCNDAE) helps learn an appropriate weight for them.
Figure 2
provides an example of such a scenario.
Unlabelled
Unlabelled
labelled
Edge with no pepeen
Unlabelled
Uniabelled
labelled
Figure 2:
The dashed edge receives no su- pervision when training two-layer GCN as it is not in the two-hop neighborhood of any labeled node.
4.5 SLAPS
Our final model, dubbed SLAPS, trained minimize L = Le ALDAE where Le the classi- fication loss, AAA E is the denoising autoencoder loss (see Equatiin 2 and x is hyperparameter controlling the relative importance of the losses.
To verify the merit of the GNN for learning an adjacency matrix in isolation, we also consider a variant of SLAPS named SLAPS that is trained in two stages. We first train the GNN model by minimizing the loss function described in Equation 2 Note that the loss function in Equation 2 depends on the parameters Ic of the generator and the parameters ACNNNpe of the denoising autoen- coder. After every epochs of training. we fix the adjacency matrix, train a classifier with the fixed adjacency matrix, and measure classification accuracy on the validation set. We select the epoch that produces the adjacency providing the best validation accuracy for the classifier. Note that in SLAPS2s, the adjacency matrix is trained only based on GNNDAE-
EXPERIMENTS
Baselines: We compare our proposal to several baselines with different properties. The first baseline is multi-layer perceptron (MLP) which does not take the graph structure into account. We also compare against MLP-GAM* (Stretcu et al. 2019) which learns a fully-connected graph structure and uses this structure supplement the loss function of the MLP toward predicting similar labels for neighboring nodes. Similar to Franceschi et al. (011)), we also consider a baseline named KNN- GCN where we create a kNN graph based on the node features and feed this graph graph structure remains fixed in this approach. We also compare with baselines that learn the graph structure from data including LDS (Franceschi et al.) 2019), GRCN (Yu et al. 2020), DGCNN (Wang et al., 2019b), and IDGL. (Chen et al. 2020). We feed kNN graph to the models requiring an initial graph structure.
Datasets: We use three established benchmarks in the GNN literature namely Cora, Citeseer, and Pubmed (Sen et al. 2008 as well as a newly released dataset for node classification named ogbn-
While this problem may be alleviated to some extent by increasing the number of layers of the GCN,
deeper GCNs typically provide inferior results due to issues such as oversmoothing (see, e.g., Li et al. 2018a
Oono & Suzuki 2020).

---

Under review as a conference paper at ICLR 2021
Table 1: Results SLAPS and the baselines on established node classification benchmarks. indi- cates results have been taken from Franceschi et al. (2019). $ indicates results have been taken from Stretcu al. (2019). Bold and underlined values indicate best and second-bes mean performances respectively. OOM indicates out of memory.
Model
Generator
Cora 56.1 1 1.6 70.74
Citeseer
Cora390 65.8 1 0.4
Citeseer370 67.1 1 0.5
Pubmed
ogbn-arxiv
MLP
56.7 1.71
71.4
54.7 $4.700..1
MLP-GAM'
70.3
71.9
KNN-GCN
66.5 + 0.4
68.3 + 1.31
72.5 + 0.5
71.8 0.8
70.4
49.1 + 0.3
LDS
71511111 0.8
0OM
OOM
GRCN
67.4 0.3
67.3 = 0.8
71.3
7..9
0.3
OOM
DGCNN
56.5
55.1=
0.7
6.8
1.3
OOM
IDGL
70.9 0.6
08.2
0.5
0.4
7.3
OOM
SLAPS
FP
0.44
0.4
0.4
0.61
OOM
OOM
SLAPS
MLP
72.8 0.8
70.5
75.3
73.0
74.4
56.6 0.1
SLAPS
MLP-D
0.3
0.6
0.5
7.4
73.1 0.7
52.9 0.1
arxiv (Hu et al. 2020a) that is orders of magnitude larger than the other three datasets and is more challenging due to the more realistic split of the data into train, validation, and test sets. For all the datasets, we only feed the node features to the models and not the graph structure. Following Franceschi et al. (2019), we also experiment with several classification (non-graph) datasets avail- able in scikit-learn (Pedregosa et al. 2011) including Wine, Cancer, Digits, and 20News. Dataset statistics can be found in the Appendix. For Cora and Citeseer, the LDS model uses the train data for learning the parameters of their classification GCN, half of the validation for learning the parameters of the adjacency matrix (in their bi-level optimization setup, these are considered as hyperparame- ters), and the other half of the validation set for early stopping and tuning the other hyperparameters. Besides experimenting with the original setups of these two datasets, we also consider a setup that closer (although not identical) to that of LDS: we use the train set and half of the validation set for training and the other half of validation for early stopping and hyperparameter tuning. We name the modified versions Cora390 and Citeseer370 respectively where the number proceeding the dataset name corresponds to the number of labels used for training. We also follow similar procedure for the scikit-learn datasets.
5.1 COMPARATIVE RESULTS
The results of SLAPS and the baselines on the node classification benchmarks are reported in Ta- ble I Considering only the baselines first, we see that KNN-GCN significantly outperforms MLP on Cora and Citeseer but underperforms of the similarity metric and the graph structure that is fed into GCN as a low-quality structure can harm model performance. LDS outperforms MIP but the fully parameterized adjacency matrix of LDS results in memory issues for Pubmed and ogbn-arxiv. As for GRCN, it was shown in the orig- inal paper that GRCN can revise good initial adjacency matrix and provide substantial boost in performance, However, as evidenced by the results, if the initial graph structure is somewhat poor, GRCN's s performance becomes on-par with kNN-GCN. IDGL is the best performing baseline but the iterative nature of it makes it slow to train and test.
Pubmed and ogbn-arxiv. This shows the importance
SLAPS consistently outperforms the baselines on all datasets, in some cases by large margins. Among the generators, the winner is dataset-dependent with MIP-DD mostly outperforming MLP on datasets with many features and MI.P outperforming on datasets with small numbers of features. Using the software that publicly released by the authors, all baselines that learn graph structure fail on ogbn-arxiv and our implementation is the first that generalizes to such large graphs.
Table 2 reports the results for the scikit-learn datasets and compares with LDS and IDGL. On three out of four datasets, SLAPS outperforms the other two baselines. Among the datasets on which we can train SLAPS with the FP generator, 20news has the largest number of nodes. On this dataset, we observed that an FP generator suffers from overfitting and produces weaker results compared to other generators due to its large number of parameters.

---

Under review as a conference paper at ICLR 2021
Table Results on classification datasets, indicates results have been taken from Franceschi al. Bold and underlined values indicate best and second-best mean performances respectively.
2019
Model LDS
Generator
Wine
Cancer
Digits
20news
97.3 = 0.4
94.4 = 1.9
92.5 = 0.7
46.4 1.6t
IDGL
97.0 + 0.7
94.2 + 2.3
92.5 + 1.3
48.5 0.6
SLAPS
FP
94.6 = 0.3
94.4 0.7
44.4
SLAPS
MLP MLP-D
1.0
96.0 + 0.8
92.4 0.6
50.4 0.7
SLAPS
+.8
96.6 0.2
93.2 + 0.6
49.8 0.9
5.2 FURTHER ANALYSIS
SLAPS2,; To provide more insight into the value provided by the self-supervision task on the learned adjacency, we conduct experiments with SLAPS Recall from Section 4.3 that in SLAPS the adjacency is learned only based on the self-supervision task and the node labels are only used for early stopping. hyperparameter tuning, and training GCNc. Figure shows the per- formance of SLAPS and SLAPS on Cora and compares them with kNN-GCN. Although SLAPS2, does not use the node labels in learning an adjacency matrix, it outperforms kNN-GCN (8.4% im- provement when using an FP generator). With an FP generator, SLAPS even achieves competitive performance with SLAPS; this is mainly because FP does not leverage the supervision provided by GCNc toward learning generalizable patterns that can be used for nodes other than those in the training set. These results corroborate the effectiveness of the self-supervision task for learning an adjacency matrix. Besides, the results show that learning the adjacency using both self-supervision and the task-specific node labels results in higher predictive accuracy.
Cora and Citeseer with different values of A. When À = O, corresponding to removing self-supervision, the model performance is somewhat poor. As soon as X becomes positive, both models see a large boost in performance show- ing that self-supervision is crucial to the high performance of SLAPS. Increasing À further provides larger boosts until it becomes so large that the supervspenn loss dominates the classification loss and the performance deteriorates, Note that with À = 0, SLAPS with the MLP generator becomes a variant of the model proposed by Cosmo et al. (0200, but with a different similarity function.
The value of X: Figure 3b) shows the performance of SLAPS
Figure 3 c) shows the performance of SLAPS on Cora for three graph generators as a function of in KNN. For all three cases, the value of i plays major role in model performance. The FP generator is the least sensitive because in FP, is only affects the initialization of the adjacency matrix but then the model can change the number neighbors of each node. For MLP and MLP-D, however, the number of neighbors of each node remains close to k (but not necessarily equal as the adjacency processor can add or remove some edges) and the two generators become more sensitive to k. For larger values of k, the extra flexibility of the MLP generator enables removing some of the unwanted edges through the function or reducing the weights of the unwanted edges resulting in MLP being less sensitive large values of l compared MLP-D.
Importance of k in KNN:
Symmetrization: To symmetrize the adjacency, in Equation ! we took the average of P(A) and P(Á)T. Here also consider two other choices: 1) max(P (A), P(A)T), and 2) not symmetrizing the adjacency (i.e. using P()).. Figure d) compares these three choices on Cora and Citeseer with an MLP generator (other generators produced similar results). On both datasets, symmetrizing the adjacency provides a performance boost. Compared to mean symmetrization, max symmetrization performs slightly worse. This may be because max symmetrization does not distinguish between the case where both v; and fy are among the most similar nodes of each other and the case where only one of them is among the l most similar nodes of the other.
Analysing the learned adjacency: Many graph-based semi-supervised classification models are based on the cluster assumption according to which nearby nodes are more likely to share the same label (Chapelle & Zien 2005). To verify the quality of the adjacency matrix learned using SLAPS, for every pair of nodes in the test set, compute the odds of the two nodes sharing the same label as a function of the normalized weight of the edge connecting them. Figure 3 (c) represents the odds
The generator used in this experiment is MI.P; other generators produced similar results.
8

---

Under review as a conference paper at ICLR 2021
72.5
SLAP5-2x
7344
70.0
72.4
72.8
/0.9
69.3
62.5
60.0
MLP
Otoszer
0.0
0.1
1.0
10.0
120.0
(a)
(b)
(c)
2.5
72.8
72.5
Mean
Mox
70.5
1.5
(ke 6.0)
pall 6.00
Edge ghe [eag, 8.80)
0.85
18.00 8.1)
(d)
Figure 3: The performance of SLAPS (a) compared to SLAPS Cora with different generators. (b) with MLP graph generator on Cora and Citeseer as a function of X, (c) with different graph generators Cora as function of & in kNN, and (d) Cora and Citeseer with different adjacency symmetrizations. (e) The odds of two nodes in the test set sharing the same label as a function of the edge weights learned by SLAPS.
for different weight intervals. For both Cora and Citeseer, nodes connected with higher edge weights are more likely to share the same label compared to nodes with lower or zero edge weights. As specific example, when A.j 2 0.1, E2 and vy are almost 2.5 times more likely share the same label on Cora and almost 2.0 times more likely Citeseer. Note that SLAPS may connect nodes based on a different criterion than the one used in the original datasets and so the learned adjacencies do not necessarily resemble the original structures.
CONCLUSION
In this paper, we proposed a model for learning the parameters of a graph neural network and the graph structure of the nodes simultaneously. We showed the effectiveness of model using comprehensive set of experiments and analyses. In the future, we would like to try more sophisti- cated graph generation models (e.g., GraphRNN (You al. 2018) and GNF (Liu al. (019a)) and extend our approach to applications with a temporal aspect where node features are observed over time but their connections are not provided as input.
REFERENCES
Héctor Martínez Alonso and Barbara Plank. When is multitask learning effective? semantic quence prediction under varying data conditions. arXiv preprint arXiv: 2016.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1806.0 2018.
Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: model and comprehensive taxonomy. arXiv preprint arXiv:2005.0366 2020.

---

Under review as a conference paper at ICLR 2021
Olivier Chapelle and Alexander Zien. Semi-supervised classification by low density separation. In AISTATS, volume 2005, pp. 57-64. Citeseer, 2005.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Deep iterative and adaptive learning for graph neural networks. In The First International Workshop on Deep Learming Graphs: Methodologies and Applications (with AAAI), February 2020. URL httptttss//dllllsl..tt bithucke............. 1o/
aaai20
Luca Cosmo, Anees Kazi, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Latent patient network learning for automatic diagnosis. arXiv preprint arXiv:2003. 13620, 2020.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint arXiv: / /806.0237,, 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018.
James Fox and Sivasankaran Rajamanickam. How robust are graph neural networks to structural noise? arXiv preprint 1912 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In JCML, 2019.
Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. arXiv preprint arXiv:1711.04043 2017.
Spyros Gidaris and Nikos Komodakis. Generating classification weights with gnn denoising autoen- coders for few-shot learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 21 21-30,22 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Searning-Volume Volume 70, pp. 1263-1272. JMLR. org, 2017.
Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowl- 2020.
edge Discovery & Data Mining, pp.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NeurlPS, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICLR, 2020b.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai- Wei Chang, and Yizhou Sun. Gpt-gun: Generative pre-training of graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery Data Mining, pp. 1857-1867, 2020c.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czamecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:/61 100597, 2016.
Soobeom Jang, Seong- Eun Moon, and Jong-Seok Lee. Brain signal classification via learning nectivity structure. arXiv preprint arXiv: 16678, 2019.
Wei Jin, Tyler Demr Haochen Liu, Yigi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self-supervised learning graphs: Deep insights and new direction. arXiv preprint arXiv:2006. 10/41, 2020a.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. arXiv preprint arXiv:2005. 10203, 2020b.
10

---

Under review as a conference paper at ICLR 2021
Daniel D Johnson, Hugo Larochelle, and Daniel Tarlow. Learning graph structure with finite-state automaton layer. arXiv preprint arXiv:2007.04929, 2020.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. JMLR, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018a.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. arXiv preprint arXiv: 1801188016.., 2018b.
Lukas Liebel and Marco Körner. arXiv:1805.0633, 2018.
Auxiliary tasks in multi-task learning.
arXiv preprint
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In NewrlPS, pp. 13556-13566, 2019a.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:
1969, 1692, 2019b.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPN-PSWRR W, 2017.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Seikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Shah Rukh Qasim, Jan Kieseler, Yutaro liyama, and Maurizio Pierini. Learning representations of irregular particle-detector geometry with distance-weighted graph networks. The European Physical Journal C, 19(7):1-11, 2019.
Sam T Roweis and Lawrence K Saul, Nonlinear dimensionality reduction by locally linear embed-
ding. science, 290(5500):2323-2326, 2000.
Ryoma Sato. survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data, Al magazine, 29(3):93 93, 2008
Richard Stanley. Acyclic orientations of graphs. Discrete Mathematics, 5(2):171-178, 1973.
Otilia Stretcu, Krishnamurthy Viswanathan, Dana Movshovitz-Atiie Emmanouil Platanios, Sujith Ravi, and Andrew Tomkins. Graph agreement models for semi- cumi--sperviiedd learning. In Advances in Neural Information Processing Systems, pp. 8713-8723, 2019.
Mohammed Suhail and Leonid Sigal. Mixture-kema kernel graph attention network for situation recogni- tion. In Proceedings of the IEEE International Conference on Computer Vision, pp. 10363-10372, 2019.
11

---

Under review as a conference paper at ICLR 2021
Joshua Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-25533 2323, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances Neural Infor- mation Processing Systems, pp. 3998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pp. 1096-1103, 2008.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv preprint arXiv: 1e../0999911111 2019a.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5): 1-12, 2019b.
Xuan Wu, Lingxiao Zhao, and Leman Akoglu. A quest for structure: Jointly learning the graph structure and sepe-supe classification. In Proceedings of the 27th ACM international con- ference on information and knowledge management, pp. 87-96, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Liang Yang, Zesheng Kang, Xiaochun Cao, Di Jin, Bo Yang, and Yuanfang Guo. Topology opti- mization based graph convolutional network. In IJCAI, pp. 4054-0064 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint 1rXiv:1802.08773. 2018.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? arXiv preprint arXiv:2006.0911 09136, 2020.
Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In ECMI. PKDD, 2020.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07294, 2018.
Hao Zhu, Yankai Lin, Zhiyuan Liu, Jie Fu, Tat-seng Chua, and Maosong Sun. Graph neural networks with generated parameters for relation extraction. arXiv preprint DXXiv:1902.0073 2019.
Qikui Zhu, Bo Du, and Pingkun Yan. Self-supervised training of graph convolutional networks.
arXiv preprint arXiv:2006.023:0 2020.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-28566 2018.
A APPENDIX
Implementation Detail: We implemented our model in PyTorch (Paszke et al. 2017). used deep graph library (DGL) (Wang et al.) 2019a) for the sparse operations, and used Adam (Kingma & Ba 2014) the optimizer. We performed early stopping and hyperparameter tuning based on the accuracy on the validation set for all datasets except Wine and Cancer. For these two datasets, vali- dation accuracy reached 100 percent with many hyperparameter settings, making difficult to select
12

---

Under review as a conference paper at ICLR 2021
the best set of hyperparameters instead, used the validation cross-entropy loss. We fixed the maximum number of epochs to 2000. We use two-layer GCNs for both GNNc and GNNDAE as well for baselines and two-layer MLPs throughout the paper (for experiments ogbn-arxiv, although the original paper uses models with three layers and with hatch normalization after each layer, to be consistent with our other experiments two learning rates, one for GCNc and one for the other parameters of the models. We tuned the two {0.01, 0.001}. We added dropout layers with dropout probabilities of
used two layers and removed the normalization). We used
learning rates from the 0.5 after the first layer of the GNNs. We also added dropout to the adjacency matrix and tuned the values from the set (0.25, 0.5}. We set the hidden dimension of GNNc 32 for all datasets except for ogbn-arxiv for which we set it to 256. We used cosine similarity for building the kNN graphs and tuned the value of from the set {15, 20, 30).. We tuned (A controls the relative importance of the two losses) from the set (0.1, 1, 10, 100). The code of our experiments will be available upon acceptance of the paper.
For GRCN Yu et al. 2020), DGCNN Wang al. 2019b), and IDGL (Chen et al. 2020). used the code released by the authors and tuned the hyperparameters as suggested in the original papers. The results of LDS (Franceschi et al., 2019) are directly taken from the original paper. All the results for our model and the baselines are averaged over 10 runs. We report the mean and standard deviation.
Dataset statistics: The statistics of the datasets used in the experiments can be found in Table
Table 3: Dataset statistics.
Dataset
Nodes
Edges
Classes
Features
Label rate
Cora
2,708
5,429
7
1,433
0.052
Citeseer
3,327
4,732
6
3,703
0.036
Wine
178
0
3
13
0.112
Cancer
569
0
2
30
0.035
Digits
1,797
0
10
64
0,056
20news
9,607
O
10
236
0.021
Pubmed
19,717
44,338
3
500
0.003
ogbn-arxiv
169,343
1,166,243
40
128
0.537
13


Reviews:
[{"review_id": "lPpVONlB-V", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of nodes classification with few labeled data and missing graph structures. The proposed solution is expected to infer unobserved graph structure as well as the parameters of the classification model. The main contribution of this paper is proposing adding a denoise autoencoder layer which provides more supervision to the learning. The model compares favorably with other states of art models in several benchmark graph data sets.\n\nConcerns:\n1. The experiments assume inputs only contain node features. The solution proposed seems to be incremental under this setting as the problem is a special case of few-shot learning where metric-learning based methods including GNN and denoise autoencoder all have been studied before. See [1], [2], [3]. Further discussion of related works is necessary.\n\n2. The proposed method seems very heuristic driven without providing further theoretical analysis. It is unclear how and why the self-supervision might help the classification learning task. Figure 2 gives a negative example of the existing method but it does not explain why the proposed method could make a difference.\n\n3. How does the proposed model compare with regular GNN/GCN models if edges are not entirely missing? The scope of the paper will be limited if it doesn’t work well when graph data is noisy but not entirely missing.\n\nReference\n[1] https://arxiv.org/abs/1905.01102\n[2] http://www.cs.toronto.edu/~gkoch/files/msc-thesis.pdf\n[3] https://arxiv.org/abs/1711.04043\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "caadRfEb027", "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": "Summary:  \nThis paper proposes to tackle jointly learning graph structures and GNN parameters without accessing the original graph structure. Specifically, the proposed method adopts a self-supervised auxiliary task, i.e., parallel training using the supervision of node labels and a self-supervised task using de-noised auto-encoding. The latent graph structure is generated through a fully-parameterized adjacency matrix or a KNN construction subsequent to passing node features to an MLP. Experimental results and corresponding analyses demonstrate the effectiveness of the proposed model.\n  \nPros:  \n1. Using self-supervision to guide graph structure learning sounds like an interesting and promising idea.   \n2. Most claims are supported by experimental results. Specifically, comparisons with baselines show that the proposed model can alleviate the problems of previous works such as sensitivity to the similarity metric and high-quality initial graph structure, memory problems, etc. Datasets like Wine, 20news, etc., demonstrate the model's validity for tasks without graph structure. Parameter sensitivity and other ablation studies are also conducted.  \n3. Overall, the paper is well written and easy to follow.   \n\nCons:  \n1. Some model designs are not entirely clear. For example, based on my understanding, the KNN step is not differentiable, thus the model with MLP-kNN generator cannot be trained end-to-end. The authors may want to detail how to cope with this problem in the training process.  \n2. I also have a question regarding the model design regarding the self-supervised loss. If neglecting the supervised part (i.e., GNNc and its loss in Figure 1), the self-supervised part basically tries to reconstruct the original feature from the noisy features using GNN_DAE. In that case, should KNN using initial features be the optimal solution (since GCN is essentially smoothing features and these nodes have the most similar features)? If that is true, I feel that the self-supervision may actually work like a regularizer to the MLP subsequent to KNN.  \n3. The experiments show that the symmetrization step is very useful while lacking analysis of why it works. Could the authors provide further exploration in that aspect?  \n4. It seems bizarre that only LDS is adopted as the baseline in Table 2 since the codes and datasets are ready. I suggest the authors at least add IDGL, the most competitive baseline in Table 1, into Table 2.   \n4. There's little comparison of the learned graph structure with the original one (Figure 3.e only utilize node labels but not the original graph structure). Since the main goal of the paper is to learn GNN and graph structure simultaneously, the learned graph structure is important and should be analyzed empirically. For example, the authors may want to follow previous works to design certain metrics to compare the learned graph structure with the original one, provide some visualizations, or case studies in synthesis graphs.  \n\nMinor:  \n1. The complete parameter sensitivity could be added to the supplementary material. For example, I am interested to see how the sensitivity of parameter k for kNN behaves across different datasets with different scales.  \n2. Some related works are missing, e.g., [1-3].  \n\n[1] Adaptive Graph Convolutional Neural Networks, AAAI 2018.  \n[2] Topology Optimization based Graph Convolutional Network, IJCAI 2019.  \n[3] Graph Structure Learning for Robust Graph Neural Networks, KDD 2020.  \n\nOverall, though I like the paper in general, I believe the paper could be further improved and thus vote for weakly rejection. I am happy to increase my scores if the authors can address my above concerns.   \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_0ltaipY67", "reviewer": "AnonReviewer2", "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": "The authors propose a method for simultaneously learning the graph structure (or a graph generative model) and the parameters of a GNN for node classification. This is a topic of recent interest and highly relevant to the ICLR community. \n\nThe authors propose two different ways for the graph generator. First, a fully parameterized method that outputs a continuous (weighted) adjacency matrix. The second computes a spare k-NN graph based on the input similarities. Using the word “graph generator” or “generative model” is a bit of a misnomer here because both methods are not probabilistic but deterministic. The adjacency matrices output by these “generators” are then made into symmetric and positive matrices (i.e., adjacency matrices for positively weighted undirected graphs). Finally, in addition to the typical supervised loss, the authors also propose an unsupervised loss based on a reconstruction loss. \n\nFirst, I like the idea of adding an unsupervised loss and also appreciate the experiments and the results as robust. \n\nI have a concern about the approach though and perhaps this could be clarified in a conversation here. When you don’t use the MLP-kNN “generator” then the adjacency matrix generated is not sparse at all. But what that means is that you are using (for each node) a fully connected layer. Do you think that the advantage of your method then is in the “adjacency processor step”? When you do use the MLP-kNN, how do you compute the gradients? Is it that you only compute gradients for the edges you selected? In this case you would have lots of edges without “supervision” as you call it. Or are you also obtaining gradients for the edges not selected? In this case, creating the kNN graph is a discrete operation and it is not clear to me how to differentiate through such an operation. Of course, recent proposals have been made for differentiating through kNN but I don’t see any reference or mention of what you are doing here. Could you please elaborate on that? \n\nRegarding the statements about LDS. First, you write that if two nodes v_i and v_j are not directly connected to any labeled nodes, then the RV between them (the edge) does not receive supervision. The statement (and the text following it) is somewhat misleading for two reasons. \n\nFirst, both of the nodes have to be not directly connected. But then in the next sentence you wrote that 80 and 89% of nodes are not directly connected to a labeled node for the standard benchmark graphs. The more appropriate analysis, however, would be to count the number of pairs of nodes where both nodes are not connected to a labelled node. This should also include the validation nodes used for the outer objective in LDS. Also note that LDS doesn’t always use the standard benchmark graphs (it either constructs a k-NN graph where k is a hyperparameter of the method or initializes with a subgraph of the given graph). \n\nSecond, your statement is true for *one* sampled graph. Remember that LDS samples a set of graphs in each iteration. It can happen that, even if there is a pair of nodes where both nodes are not directly connected to a labelled node in one sampled graph, one of these nodes might be connected in a different sample. Indeed, if a sampled edge connecting either v_i or v_j directly to a labelled node leads to a reduction of the loss, the next time said edge is probably more likely to be sampled. This is not to say that self-supervision is not a good idea (I do like the idea) but I’m not sure if your statements about LDS are quite accurate. \n\nOverall, I think that this paper strength is the proposed self-supervised loss and the experimental evaluation. It is rather weak on the methodology, its presentation, and related  discussion. There are several questions I need to hear your response to. Once these are clarified I'm open to adjust my score accordingly. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KX2uDF2HrLn", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 paper proposes a way to use self-supervision with denoising autoencoders to improve learning of the graph structure for GNNs. The approach is compared with a number of recent approaches from the literature.\n\nThe approach addresses the highly relevant problem of learning graph structure with GNNs. The paper is well written, with clear motivation and an informative summary of similar prior works. The differences with respect to these approaches, primarily the self-supervised aspects, are clearly pointed out.\n\nThere are a few prior works covering self-supervision with GNNs that are all quite new [1-3]. It would strengthen the manuscript if these works were discussed in relation to this work. However, consider how new they all are it is not surprising that they were not mentioned.\n\n\nQuality\n- While the originality is perhaps not big, the work is thorough and well written. There is a substantial experimental comparison with relevant prior work and the conclusions seems to be substantiated.\n\nClarity\n- The paper is well written and easy to understand. I would have liked a little more details and explanation on the MLP-kNN aspects.\n\nOriginality\n- Self-supervision seems to be the topic of a lot of papers lately, so in that respect, this work is perhaps not the most original.\n\nSignificance\n- I am not aware of similar works and the results are convincing, so I guess the approach could have reasonable influence on the field.\n\n[1] Jin, Wei, et al. \"Self-supervised learning on graphs: Deep insights and new direction.\" arXiv preprint arXiv:2006.10141 (2020).\n[2] You, Yuning, et al. \"When Does Self-Supervision Help Graph Convolutional Networks?.\" arXiv preprint arXiv:2006.09136 (2020).\n[3] Zhu, Qikui, Bo Du, and Pingkun Yan. \"Self-supervised Training of Graph Convolutional Networks.\" arXiv preprint arXiv:2006.02380 (2020)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GlOs9xwewkz", "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": "Graph neural networks (GNNs) have become de facto methods for integrating the input graph structure and node features to learn effective node representations. However, in some domains (such as brain signals, particle reconstruction, etc.), there is access to only node features (but not the underlying graph structure). Motivated by the fact that GNNs tend to perform poorly in the absence of the graph structure, the paper\n1) proposes a self-supervised framework for generating the graph structure,\n2) explores the design space of the framework by comparing different graph generation methods,\n3) demonstrates the framework's effectiveness on node classification datasets.\n\n\n\n##  Pros\n+ [Motivation] A strength of the paper is the motivation of the problem. It is well-known that the performance of GNNs is highly sensitive to the quality of the input graph structure. Hence, in domains such as brain signals, particle reconstruction, etc., it is necessary to generate a high-quality graph structure so that GNNs could be effectively leveraged. \n+ [Presentation] The high-level ideas of the paper are easy to read with clear figures and notation.\n+ [Relevance] The topic of GNNs has gained increasing attention recently such that a significant portion of the ICLR community should be interested.\n\n\n\n## Cons\nThe main weaknesses of the paper are along the axis of the significance of the contributions. The paper requires thorough discussions / positioning / comparisons with many existing publications in GNN literature. The detailed comments are as follows.\n- [Self Supervision] The framework proposed in the paper can be seen as an instance of a general framework for self-supervision proposed in SS-GCN (When Does Self-Supervision Help Graph Convolutional Networks?, In ICML'20). \n- [Self Training] A closely related idea for self-supervision is self-training. The basic idea of self-training is to add high-confident predictions to the training set to increase supervision. The paper should be positioned with (and empirically compare against) self-training-based approaches such as (but not limited to)\ni) GAM (Graph Agreement Models for Semi-Supervised Learning, In NeurIPS'19) that can also handle noisy / learn graph structures, \nii) AdaEdge (Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View, In AAAI'20).\n- [Quality] Regarding experiments, the dataset domains (such as citation networks) considered in the paper are those in which the graph structure is known. So, it would be more convincing if the adjacency of the dataset was used as the initial adjacency matrix in the proposed framework. The baselines to compare against would then be models such as SS-GCN, GAM, etc.  \n- [Soundness] It is unclear why datasets from domains discussed in the introduction section were not considered in the experiments. These domains include, as listed in the paper, brain signal classification, computer-aided diagnosis, analysis of computer programs, and particle reconstruction.  \n- [Clarity] Though the high-level ideas were easy to read, the paper should clearly discuss finer details. In particular, in section 4.1 (paragraph preceding 4.2), the details of adjacency initialisation are hastily mentioned, and it feels like the discussion mixes adjacency and weight matrices up. \n- [Metric Learning] An idea for learning graph structures for GNNs is to learn the underlying similarity metric (rather than use a chosen one). This idea has been used in certain domains of computer vision and natural language processing. The paper should be positioned with relevant publications (albeit for small graphs) including (but not limited to)\ni) Few-Shot Learning with Graph Neural Networks, In ICLR'18\nii) Graph Neural Networks with Generated Parameters for Relation Extraction, In ACL'19", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received 5 reviews, one of which had positive feedback. Although there are merits associated with the paper, several concerns raised in the reviews and the discussion period that prevents the paper to be accepted. It appears that experiments on noisy graphs are not properly done and competitive baselines are not used for validations. The quality of the learned graph structure is not adequately analyzed. and the experimental setup was not clearly explained. All these indicate that there is a need for a major revision before the paper can be considered for acceptance.
Decision: Reject