SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks
Authors: Bahare Fatemi
Layla El Asri
Seyed Mehran Kazemi
Venue: NeurIPS 2021 Poster (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 a task-specific 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 task-specific supervision 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 through self-supervision. 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.

SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks
Bahare Fatemi"
University of British Columbia bfatemi0cs. ubc.ca
Layla El Asri
Seyed Mehran Kazemi'
Borcalis Al
Google Research
layla. wawsr@boreallsai.coom
mehrannkazemii@ggglee.cco
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 task-specific latent structure and then apply a GNN to the inferred graph. Unfortunately, the space of possible graph structures grows super-exponentiall with the number of nodes and so the task- specific supervision may be insufficient for learning both the structure and the GNN parameters. In this work, we propose the Simultancous Learning of Adjacency and GNN Parameters with Self-supervision, or SLAPS, method that provides more supervision for inferring a graph structure through self- seff-supervisoo. A compre- hensive 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 a natural graph of the data points is available 4 25). Graph neural networks (GNNs) [40] have been key component to the success the research in this area. Specifically, GNNs have shown promising results for semi-supervised classification when the available graph structure exhibits high degree of homophily (i.c. connected nodes often belong to the same class) [57].
We study the applicability of GNNs to (semi-supervised) classification problems where graph structure is not readily available. The existing approaches for this problem either fix a similarity graph between the nodes or learn the GNN parameters and a graph structure simultaneously (see Related Work). In both cases, one main goal is to construct or learn a graph structure with a high degree of homophily with respect to the labels to aid the GNN classification. The latter approach is sometimes called latent graph learning and often results higher predictive performance compared to the former approach (see, e.g., [12).
We identify a supervision starvation problem in latent graph learning approaches which the edges between pairs of nodes that are far from labeled nodes receive insufficient supervision; this results learning poor structures away from labeled nodes and hence poor generalization. We propose solution for this problem by adopting multi-task learning framework in which we supplement the classification task with a self-supervised task. The self-supervised task is based on the hypothesis
Work was done when authors were at Borealis AL
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

that a graph structure that is suitable for predicting the node features is also suitable for predicting the node labels. It works by masking some input features (or adding noise to them) and training a separate GNN aiming at updating the adjacency matrix in such way that it can recover the masked (or noisy) features. The task is generic and can be combined with several existing latent graph learning approaches.
We develop a latent graph learning model, dubbed SLAPS, that adopts the proposed self-supervised task. We provide a comprehensive experimental study on nine datasets (thirteen variations) of various sizes and from various domains and perform thorough analyses to show the merit of SLAPS.
Our main contributions include: 1) identifying a supervision starvation problem for latent graph learning, 2) proposing solution for the identified problem through sulf-suueriiiion 3) developing SLAPS,, a latent graph learning model that adopts the self-supervised solution, 4) providing compre- hensive experimental results showing SLAPS substantially outperforms existing latent graph learning baselines from various categories on various benchmarks, and 5) providing an implementation for latent graph 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. We discuss selected work from each category and refer the reader to [60] for full survey.
Similarity graph: One approach for inferring a graph structure is select a similarity metric and To obtain 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, in [14 a (fixed) kNN graph using the cosine similarity of the node features created. In 47, this idea is extended by creating a fresh graph in each layer of the GNN based on the node embedding similarities in that layer. Instead of choosing a single similarity metric, in [15 several (potentially weak) measures of similarity are fused. The quality of the predictions of these methods depends heavily on the choice of the similarity metric(s).
set the edge weight between two nodes to be their similarity [39 44 3.
Another approach start with a fully connected graph and assign edge weights using the available meta-data or employ the GNN variants that provide weights for each edge via an attention mechanism 45 53). This approach has been used in computer vision [c.g.. 43), natural language processing [e.g.. 56 and few-shot learning [3). The complexity of this approach grows rapidly making applicable only to small-sized graphs. Zhang et al. [54] propose to define local neighborhoods for each node and only assume that these local neighborhoods are fully
Fully connected graph:
connected. Their approach relies on an initial graph structure to define the local neighborhoods.
Instead of a similarity graph based on the initial features, one may use a graph generator with learnable parameters. In [30]. fully connected graph is created based on a bilinear similarity function with learnable parameters, In [1]. Bernoulli distribution is learned for each possible edge and graph structures are created through sampling from these distributions. In [4)] the input structure is updated to increase homophily based on the labels and model predictions. In 6 an iterative approach is proposed that iterates over projecting the nodes to a latent space and constructing an adjacency matrix from the latent representations multiple times. A common approach in this category is to learn a projection of the nodes to a latent space where node similarities correspond to edge weights or edge probabilities. In 48 the nodes are projected to a latent space by learning weights for each of the input features.
Latent graph learning:
38 21 g a multi-layer perceptron is used for projection. In [52] (55) a GNN is used for projection; it uses the node features and an initial graph structure. In (26], different graph structures are created in different layers by using separate GNN projectors, where the input to the GNN projector in layer is the projected values and the generated graph structure from the previous layer. In our experiments, we compare with several approaches from this category.
Leveraging domain knowledge: In some applications, one may leverage domain knowledge to guide the model toward learning specific structures. For example, in [4]. abstract syntax trees and regular languages are leveraged in learning graph structures of Python programs that aid reasoning for downstream tasks. In [23] the structure learning is guided for robustness to adversarial attacks through the domain knowledge that clean adjacency matrices are often sparse and low-rank and exhibit feature smoothness along the connected nodes. Other examples in this category include

---

19 38). In our paper. we experiment with ceneral-purpose datasets without access to domain
knowledge.
Proposed method: Our model falls within the latent graph learning category. We supplement the training with self-supervised objective increase the amount of supervision in learning structure. Our self-supervised task is inspired by, and similar to, the pre-training strategies for GNNs [17 18 22 51 58] (specifically, we adopt the multi-task learning framework of You al. [5I), but it differs from this line of work as we use self-supervision for learning a graph structure whereas the above methods use learn better (and, in some cases, transferable) GNN parameters.
3 Background and notation
We use lowercase letters to denote scalars, bold lowercase letters to denote vectors and bold uppercase letters to denote matrices. I represents identity matrix. For vector v, represent its 2th element as v;. For matrix M, we represent the 7th row as M, and the element at the 7 row and 1 column as Maj. For an attributed graph, we use n, and f to represent the number of nodes, edges, and features respectively, and denote the graph as G = (V, A, } where V {fi,..., Un is set of nodes, A R=x" is adjacency matrix with Aij indicating the weight of the edge from et to vy (At) 0 implies no edge), and X E Raxf is a matrix whose rows correspond to node features.
Graph convolutional networks (GCNs) 27 are a powerful variant of GNNs. For a graph (V, A, }} with degree matrix D, layer of the GCN architecture can be defined H
a (AH( where Å represents a normalized adjacency matrix, ( E Raadd-1 represents
X). W E qdd:ixd: is a weight matrix, o is an activation function such ReLU (34, and ( Raxd: is the updated node embeddings. For
the node representations in layer [-1 (H
(0)
undirected graphs where the adjacency is symmetric, Å = D (A + D corresponds row-and-column normalized adjacency with self-loops, and for directed graphs where the adjacency is not necessarily symmetric, D- + corresponds to row normalized adjacency matrix with self-loops. Here, D is a (diagonal) degree matrix for (A I) defined as Dú =1 + Σ, Aij.
4 Proposed method: SLAPS
SLAPS consists of four components: 1) generator, 2) adjacency processor, 3) classifier, and 4) self-supervision. Figure Iillustrates these components. In the next three subsections, we explain the first three components. Then, we point out a supervision starvation problem for model based only on these components. Then deseribe the self-supervision component solution to the supervision starvation problem and the full SLAPS model.
4.1 Generator
The generator is a function G: jax + R with parameters OG which takes the node features
X E R as input and produces a matrix Á E R=** as output. We consider the following two generators and leave experimenting with more sophisticated graph generators (e.g., [50 32 and models with tractable adjacency computations (e.g.. (7]) as future work.
Full parameterization (FP): For this generator, IG E R and the generator function is defined as Å GFr(X; 0c) = Oc- That is, the generator ignores the input node features and directly optimizes the adjacency matrix. FP is similar to the generator in LD$ [2] except that the generator of LDS treats each element of À as the parameter a Bernoulli distribution and samples graph structures from these distributions. FP is simple and flexible for learning any adjacency matrix but adds n² parameters which limits scalability and makes the model susceptible to overfitting.
MLP-KNN: Here, IG corresponds to the weights of multi-layer perceptron (MLP) and À GMLP (X; 0G) = KNN(MLP(X)) where MLP f2ax + R f" an MLP that produces matrix with updated node representations X'; kNN Rexf" + x produces a sparse matrix. The implementation details for the KNN operation is provided in the supplementary material.
Initialization and variants of MIPP-NN: Let A ANNN represent an adjacency matrix created by applying kNN function the initial node features. One smart initialization for 0G is to initialize
3

---

Node
10
62
0.
03
01
Generator
Adjacency Processor
0.5
02
2NM
1.
03
Non-symmetri, noe-normalied adjacency
Symmetric normalized adjeancy
Add Noise
GNNNDE
Features
Denoised features
Figure 1: Overview of SLAPS. At the top, a generator receives the node features and produces non-symmetric, non-normalized adjacency having (possibly) 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 (43)). 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.5)
in way that the generator initially generates A (i.e. Á = ANNN before training starts). This can be trivially done for the FP generator by initializing 0G to A&NN For MLP-KNN, we consider two variants. In one, hereafter referred to simply MLP, we keep the input dimension the same throughout the layers. In the other, hereafter referred to as MLP-D, we consider MLPs with diagonal weight matrices (i.e., except the main diagonal, all other parameters in the weight matrices are zero). For both variants, we initialize the weight matrices in OG with the identity matrix to ensure that the output of the MLP initially the same its input and the kNN graph created on these outputs is equivalent to A KNN (alternatively, one may use other MLP variants but pre-train the weights to output A NNN before the main training starts.). MLP-D can be thought of assigning different weights to different features and then computing node similarities.
4.2 Adjacency processor
The output Á of the generator may have both positive and negative values, may be non-symmetric
and non-normalized. We let A = = - (P(() + P(Á)") Here P is a function with non-negative range applied element-wise on its input see supplementary material details. The sub-expression (P(() + P()))) makes the resulting matrix P symmetric. To understand the reason for taking the mean of P(Á) and P(Á)T, assume Á is generated by GMLP. If By is among the most similar nodes to v and vice versa, then the strength of the connection between v; and vj will remain the same. However, if, say, Uj is among the l: most similar nodes to but is not among the top k for uy. then taking the average of the similarities reduces the strength of the connection between t and ey- Finally, once we have symmetric adjacency with non-negative values, we normalize (P(()) () + P(Á)T) by computing its degree matrix D and multiplying it from left and right to D-
4.3 Classifier
The classifier is function GNN T x ROx* -> R 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 corresponds to the classes and |C] corresponds to the number of classes. We use two- layer GCN for which θGNNE = (W(1), (2)) and define our classifier as GNN (A, X; (GNNN) AReLU( A (1) but other GNN variants can be used as well (recall that A is normalized). The training loss Le for the classification task computed by taking the softmax of the logits to produce probability distribution for each node and then computing the cross-entropy loss.

---

4.4 Using only the first three components leads to supervision starvation
One may create model using only the three components described so far corresponding the top part of Figure [ As we will explain here, however, this model may suffer severely from supervision starvation. The same problem also applies to many existing approaches for latent graph learning, as they can be formulated as a combination of variants of these three components.
Consider scenario during training where two unlabeled nodes va and fy not directly con- nected to any labeled nodes according to the generated structure. Then, since two-layer GCN makes predictions for the nodes based on their two-hop neighbors, the classification loss (i.e. Lc) is not affected by the edge between e; and by and this edge receives no supervisior Figure provides an example of such a scenario. Let us call the edges that do not affect the loss function Le (and consequently do not receive supervision) starved edges. These edges are problematic because although they may not affect the training loss, the predictions at the test time depend on these edges and if their values are learned without enough supervision, the model may make poor predictions at the test time. A natural question concerning the extent of the problem caused by such edges is the proportion of starved edges. The following theorem formally establishes the extent of the problem for Erdös-Rényí graphs [0:; ; in the supplementary, we extend this result to the Barabási-Alber model 1 and scale-free networks
Unlabelled
Unizaslled
Labolled
Uniabelled
Unirbelled
Labeled
Figure 2: Using two-layer GCN, the predictions made for the la- beled nodes are not affected by the dashed (starved) edge.
(2). An Erdös-Rény graph with n nodes and m edges is graph chosen uniformly at random from the collection of all graphs which have n nodes and m edges.
Theorem Let G(n, m) be an Frdōs-Rényi graph with n nodes and m edges. Assume we have labels for nodes selected uniformly at random. The probability of edge being a starved edge with two-layer GCN is equal to 91 -1
24
We defer the proof to the supplementary material. To put the numbers from the theorem in perspective, let us consider three established benchmarks for semi-supervised node classification namely Cora, Citeseer, and Pubmed (the statistics for these datasets can be found in the Appendix). For an Erdōs-Rényi graph with similar statistics as the Cora dataset (n 2708, m 5429, q 140), the probability of an edge being a starved edge is 59.4% according to the above theorem. For Citeseer and Pubmed, this number is 75.7% and 96.7% respectively. While Theorem is stated for Erdös-Rény graphs, the identified problem also applies to natural graphs. For the original structures of Cora, Citeseer, and Pubmed, for example, 48.8%, 65.2%, and 91.6% of the edges are starved edges.
4.5 Self-supervision
One possible solution to the supervision starvation problem is to define a prior graph structure and regularize the learned structure toward it. This leads the starved edges toward the prior structure as opposed to neglecting them. The choice of the prior is important as it determines the inductive bias incorporated into the model. We define prior structure based on the following hypothesis:
Hypothesis A graph structure that is suitable for predicting the node features is also suitable for predicting the node labels.
We first explain why the above hypothesis is reasonable for an extreme case that is easy to understand and then extend the explanation to the general case. Consider an extreme scenario where one of the node features is the same as the node labels. A graph structure that is suitable for predicting this feature exhibits homophily for it. Because of the equivalence between this feature and the labels, the graph structure also exhibits homophily for the labels, it is also suitable for predicting the labels. In the general (non-cxtreme) case, there may not be a single feature that is equivalent to the labels but subset of the features may be highly predictive of the labels. A graph structure that is suitable for predicting this subset exhibits homophily for the features in the subset. Because this subset highly
While using more layers may somewhat alleviate this problem, deeper GCNs typically produce inferior results, e.g., due to oversmoothing [29 35 see the supplementary material for empirical evidence.
5

---

predictive of the labels, the structure also exhibits a high degree of homophily for the labels, so it is also suitable for predicting the node labels.
Next, we explain how to design a suitable graph structure for predicting the features and how to regularize toward it. One could design such structure manually (e.g., by handcrafting graph that connects nodes based on the collective homophily between their individual features) and then penalize the difference between this prior graph and the learned graph. Alternatively, in this paper, we take learning-based approach based on self-supervision where we not only use the learned graph structure for the classification task, but also for denoising the node features. The supervised task encourages the model to learn structure that is suitable for predicting the node features. We describe this approach below and provide comparisons to the manual approach in the supplementary material.
Our self-supervised task is hased on denoising autoencoders [46]. Let GNNDAE IR=x/ x IR"xn - R=xf be GNN with parameters NNNOOE that takes node features and generated adjacency as input and provides updated node features with the same dimension as output. We train GNN such that it receives a noisy version X of the features X as input and produces the denoised features X as output. Let idx represent the indices corresponding the elements of X to which we have added noise, and Xitz represent the values at these indices. During training, we minimize:
LDAE L(Xidxx idæ, GNNDAE X, A:; GNNNAF )idæ)
where A is the generated adjacency matrix and L is loss function. For datasets where the features consist of binary vectors, idr consists of percent of the indices of X whose values are and rn percent of the indices whose values are O, both selected uniformly at random in each epoch. Both and 17 (corresponding to the negative ratio) are hyperparameters. In this case, we add noise by setting the Is in the selected mask to Os and L is the binary cross-entropy loss. For datasets where the input features are continuous numbers, idæ consists of r percent of the indices of selected uniformly at random in each epoch. We add noise by either replacing the values at idæ with 0 or by adding independent Gaussian noises to each of the features. In this case, L is the mean mean-squared error loss.
Note that the self-supervise task in equation is generic and can be added to different GNNs as well as latent graph learning models. It can be also combined with other techniques in the literature that encourage learning more homophilous structures or increase the amount of supervision. In our experiments, we test the combination of our self-supervised task with two such techniques namely self-training [29] and AdaEdge (5). Self-training helps the model "see" more labeled nodes and AdaEdge helps iteratively create graph structure with higher degrees homophily. We refer the reader the supplementary material for descriptions of self- self-training and AdaEdge.
4.6 SLAPS
Our final model is trained to minimize L Lc + AADAAE where Lo is the classification loss, CDAE is the denoising autoencoder loss (see Equation I. and À is hyperparameter controlling the relative importance of the two losses.
5 Experiments
In this section, we report our key results. More empirical comparisons, experimental analyses, and ablation studies are presented in the supplementary material.
Baselines:
We compare our proposal to several baselines with different properties. The first baseline is a multi-layer perceptron (MLP) which does not take the graph structure into account, We also compare against MLP-GAM [42 which learns fully connected graph structure and uses this structure to supplement the loss function of the MLP toward predicting similar labels for neighboring nodes. Our third baseline label propagation (LP) [59], well-known model for semi-supervised learning. Similar to [12. we also consider a baseline named &NN-GCN where we create a kNN graph based on the node feature similarities and feed this graph to a GCN; the graph structure remains fixed in this approach. We also compare with prominent existing latent graph learning models including
LDS [1), GRCN [52) DGCNN 47 and IDGL 6. In 6 another variant named IDGL-ANCH is also proposed that reduces time complexity through anchor-based approximation 33 We compare against the base IDGI, model because it does not sacrifice accuracy for time complexity, and because anchor-basee based approximation is model-agnoste and could be combined with other models too. We

---

Table 1: Results of SLAPS and the baselines established node classification benchmarks. indicates results have been taken from Franceschi et al. 12]. $ indicates results have been taken from Stretcu et al. 442 Bold and underlined values indicate best and second-best mean performances respectively. OOM indicates out of memory. OOT indicates out of time (we allowed 24h for each run). NA indicates not applicable.
Model MLP
Cora
Citeseer
Cora390
Citeseer370
Pubmed
ogbn-arxiv
56.1 + 1.6
56.7 1.71
65.8 0.4
67.1 + 0.5
71.4 0.0 71.9
54.7 0.1
MLP-GAM LP kNN-GCN
70.7*
70.3
37.6 - 0.0
23.2
0.0
0.0
41.3 0.0
OOM
1.3
0.5
70.4 0.8
49.1 + 0.3
LDS
71.5
7.15
0OM
OOM
GRCN
67.4+
0.8
0.3
6.3 0.7
OOM
DGCNN
1.2
1.
0.7
6.8
1.3
OOM
IDGL
0.6
0.6
0.5
7..7
7.4
OOM
KNN-GCN + AdaEdge
6.07
68.8
0.4
0.6
OOT
OOT
KNN-GCN self-training
0.3
6.
0.3
0.2
72.7 OOM
NA
SLAPS (FP)
0.4
0.47
0.4
0.6
OOM
SLAPS (MLP)
72.8 0.8
1.1
1.0
0.9
74.4 0.6
56.6 0.1 52.9 0.1
SLAPS (MIP-D)
73.4 0.3
0.6
75.1
0.4
73.1 0.7
SLAPS (MIP) + AdaRdge
72.8 0.7
1.5
0.6
72.6 1.4
OOT
OOT
SLAPS (MLP) + self-training
74.2 0.5
1.0
73.3 0.6 0.7
1.
NA
feed a kNN graph to the models requiring an initial graph structure. We also explore how adding self-training and AdaEdge impact the performance of KNN-GCN well as SLAPS.
Datasets: We use three established benchmarks in the GNN literature namely Cora, Citeseer, and Pubmed 41 well as the ogbn-arxiv dataset [16] 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 these datasets, only feed the node features to the models and not their original graph structure. Following [12 6 we also experiment with several classification (non- (non-graph) datasets available in scikit-learn 36 including Wine, Cancer, Digits, and 20News. Furthermore, following [20]. we also provide results on MNIST (28). The dataset statistics can be found in the supplementary. For Cora and Citeseer, the LDS model uses the train data for learning the parameters of the classification GCN, half of the validation for learning the parameters of the adjacency matrix (in their bi-level optimization setup, these are considered as hyperparameters), 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 is closer 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 shows the number of labels from which gradients are computed. We follow a similar procedure for the scikit-learn datasets.
Implementation: We defer the implementation details and the best hyperparameter settings for our model on all the datasets the supplementary material.
5.1 Comparative results
The results of SLAPS and the baselines on our benchmarks are reported Tables and We start by analyzing the results in [able[[firt.. Starting with the basclines, we see that learning fully connected graph in MLP-GAM makes it outperform MLP. KNN-GCN significantly outperforms MLP on Cora and Citeseer but underperforms on Pubmed and ogbn-arxiv. Furthermore, both self-training and AdaEdge improve the performance of KNN-GCN. This shows the importance of the similarity metric and the graph structure that is fed into GCN; a low-quality structure can harm model performance. LDS outperforms MLP but the fully parameterized adjacency matrix of LDS results in memory issues for Pubmed and ogbn-arxiv. As for GRCN, was shown in the original paper that GRCN can revise a good initial adjacency matrix and provide a substantial boost in performance. However, evidenced by the results, if the initial graph structure somewhat poor, GRCN's performance becomes on par with KNN-GCN. IDGL is the best performing bascline.
7

---

Table 2: Results classification datasets. indicates results have been taken from Franceschi et al. Bold and underlined values indicate best and second-bes, mean performances respectively.
12.
Model
Wine
Cancer
Digits
20mews
MLP
96.1 # 1.0
1.0
30.4 0.1
ANN GCN
93.5 1 0.7
95.3 + 0.4
95.4 1: 0.4
46.3 : 0.3
LDS
97.3 + 0.4
91.1 1.9
92.5
0.7!
46.4 1.6.
9.7
94.2
2.3
92.5
48.5 0.6
SLAPS (FP)
9..4
94.6
0.3
94.4 1 0.7
44.4 1 0.8
SLAPS (MLP)
96.3 10.3110 1.0
96.0 + 0.8
92.5 2 0.7
50.4
+ 0.7
SLAPS (MLP-D)
96.5
0.2
94.2
49.8 0.9
In addition to the aforementioned baselines, we also experimented with GCN, GAT, and Transformer (encoder only) architectures applied fully connected graphs. GCN always learned predict the majority class. This is because after one fully connected GCN layer, all nodes will have the same embedding and become indistinguishable. GAT also showed similar behavior. We believe this is because the attention weights are (almost) random at the beginning (due to random initialization of the model parameters) resulting nodes becoming indistinguishable and GAT cannot escape from that state. The skip connections of Transformer helped avoid the problem observed for GCN and GAT and we were able to achieve better results (~~ 40% accuracy on Cora). However, we observed severe overfitting, even with small models and with high dropout probabilities.
SLAPS consistently outperforms the baselines in some cases by large margins. Among the generators, the winner is dataset-dependent with MLP-D mostly outperforming MI.P on datasets with many features and MIP outperforming datasets with small numbers of features. Using the software that was publicly released by the authors, the baselines that learn a graph structure fail on ogbn-arxiv; our implementation, on the other hand, scales to such large graph Adding eeff-training helps further improve the results of SLAPS. Adding AdaEdge, however, does not seem effective, probably because the graph structure learned by SLAPS already exhibits high degree of homophily (see Section 5.4).
In Table 2 we only compared SLAPS with the best performing baselines from Table (KNN-GNN, LDS and IDGL). We also included an MLP baseline for comparison. On three out of four datasets, SLAPS outperforms the LDS and IDGL. baselines. For the Digits dataset, interestingly KNN-GCN outperforms the learning-based models. This could be because the initial kNN structure for this dataset is already good structure. Among the datasets on which we can train SLAPS with the FP generator, 20news has the largest number of nodes (9,607 nodes). On this dataset, observed that an FP generator suffers from overfitting and produces weaker results compared to other generators due to its large number of parameters.
Jiang et al. (11) show that learning a latent graph structure of the input examples can help with semi-supervised image classification. In particular, they create three versions of the MNIST dataset each consisting of a randomly selected subset with 10,000 examples in to- tal. The first version contains 1000 labels for training, the second contains 2000, and the third version contains 3000 labels for training. All three variants use an extra 1000 labels for validation. The other examples are used as test examples. Here, we conduct an experi- ment to measure the performance of SLAPS on these variants of the MNIST dataset. We compare against GL.N 21 as well as the baselines in the GL.CN paper including man- ifold regularization B. label propagation. deep walk (37]. graph convolutional networks (GCN), and graph attention networks (GAT).
Table 3: Results on the MNIST dataset. Bold values indicate best mean performances. Underlined val- ues indicate second best mean performance. All the results for baseline have been taken from 20
Model ManiReg LP
MNIST1000
MNIST2000
MNIST3000
92.74 0.3
93.96
- 0.2
94.62 1 0.2
79.28 0.9
81.91 0.8
83.45 0.5
DeepWalk GCN
94.55 0.3
95.04
95.34 1 0.3
90.59 - 0.3
9.2
91.01 +.2
GAT
92.11
0.4
92.64
92.81 = 0.3
GLCN
94.28
+ 0.3
9.2
95.46 - 0.2
SLAPS
94.66 0.2
95.35 1 0.1
95.54
0.0
The results are reported in Table 3 From the results, can be viewed that SLAPS outperforms GLCN and all the other baselines on the 3 variants. Compared to GLCN, on the three variants SLAPS
We note that IDGL-ANCH also scales to ogbn-arxiv.
8

---

reduces the error by 7%, 5%, and 2% respectively, showing that SLAPS can be more effective when the labeled set is small and providing more empirical evidence for Theorem 1.
5.2 The effectiveness of self-supervision
Learning a structure only using self-supervision: To pro- vide more insight into the value provided by the self-supervision task and the generalizability of the adjacency learned through this task, we conduct experiments with a variant of SLAPS named SLAPS2, that is trained in two stages. We first train the GNNDAE model by minimizing LDA described in in Equa- tion 1 Recall that LDAF depends on the parameters Oc of the generator and the parameters IGNNOEE 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 the validation set. We select the epoch that produces the adjacency providing the best valida- tion accuracy for the classifier. Note that in SLAPS the ad- jacency matrix only receives gradients from the self-supervised task in Equation I
76
KAN-GON
SLAPS
74
12.4
SLAPS-24
72.1
72.8
73.4
Accuracy
70
69.3
68
66-
FP
MLP
MLP D
Figure 3: SLAPS vs SLAPS2, on
Cora with different generators.
Figure 3 shows the performance of SLAPS and SLAPS2, 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% improvement when using an FP generator). With an FP generator, SL.ASS2s 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- seff-supervision and the task-specific node labels results in higher predictive accuracy.
The value of A: Figure 4 shows the performance of SLAPS on Cora and Citeseer with different values of X. When X = U. corresponding to removing self-supervision, the model per- formance is somewhat poor. As soon as À becomes positive, both models see a large boost in performance showing that self-supervision is crucial to the high performance of SLAPS. Increasing X further provides larger boosts until it becomes so large that the self-supervision loss dominates the classification loss and the performance deteriorates. Note that with À = O. SLAPS with the MLP generator becomes variant of the model proposed in [8) but with a different similarity function.
73-
72-
71
70
68
67-
Cora
66
Gteseer
Is self-supervision actually solving the supervision starva- tion problem? In Fig/4 we showed that self-supervision is key to the high performance of SLAPS. Here, we examine if this because self-supervision indeed addresses the supervision starvation problem. For this purpose, we compare SLAPS with and without self-supervision on two groups of test nodes on Cora: 1) those that are not connected to any labeled nodes after training, and 2) those that connected to at least one labeled node after training. The nodes in group one have a high chance of having starved edges. We observed that adding self-supervision provides 38.0% improvement for the first group and only 8.9% improvement for the latter. Since self-supervision mainly helps with nodes in group 1, this provides evidence that self-supervision is effective solution to the supervision starvation problem.
Figure
The performance of SLAPS with MLP graph generator as a function of X.
The effect of the training set size: According to Theorem I a smaller q (corresponding to the training set size) results in more starved edges in each epoch. To explore the effeet of self-suerrvision as a function of g, we compared SLAPS with and without supervision on Cora and Citeseer while reducing the number of labeled nodes per class from 20 to 5. We used the FP generator for this experiment. With 5 labeled nodes per class, adding sulf-supervision provides 16.7% and 22.0%
'The generator used in this experiment is MLP; other generators produced similar results.

---

improvements on Cora and Citeseer respectively, which is substantially higher than the corresponding numbers when using 20 labeled nodes per class (10.0% and 7.0% respectively). This provides Note that the results on Cora390 and Citeseer 370 datasets provide
empirical evidence for Theorem | evidence that the self-supervised task effective even when the label rate is high.
5.3 Experiments with noisy graphs
The performance of GNNs highly depends on the quality of the input graph structure and deteriorates when the graph struc- ture is noisy [see 61 99 []]. Here, we verify whether self- supervision is also helpful when a noisy structure is provided as input. Toward this goal. experiment with Cora and Citeseer and provide noisy versions of the input graph as input. The provided noisy graph structure is used only for initialization; is then further optimized by SLAPS. We perturb the graph structure by replacing P percent of the edges in the original structure (selected uniformly at random) with random edges. TigureBJshone the performance of SLAPS with and without sulf-superviiion (A = 0 corresponds to no supervision). We also report the results of vanilla GCN on these perturbed graphs for comparison. It can be viewed that self- supervuperviioon consis- tently provides a boost in performance especially for higher values of p.
SLAPS
75-
SLAPS (A-0)
GCN
70-
55
50-
45
Cora p-25%
Cora p 50%
Clesser p- 25%
Clteseer
P-50%
Figure 5: Performance comparison when noisy graphs input (p indicates the percentage of perturbations).
are provided as
5.4 Analyses of the learned adjacency
Noisy graphs: Following the experiment in Section 5.3 we compared the learned and orig- inal structures by measuring the number of random edges added during perturbation but re- moved by the model and the number of edges removed during the perturbation but recov- ered by the model. For Cora, SLAPS removed 76.2% and 70.4% of the noisy edges and re- covered 58.3% and 44.5% of the removed edges for p = 25% and P = 50% respectively while SLAPS with À 0 only removed 62.8% and 54.9% of the noisy edges and recovered 51.4% and 35.8% of the removed edges. This provides evidence self-supervision being helpful for structure learning.
25
Cora
2.0
Ctesser
1.5-
As explained earlier, properly learned graph for semi-supervised classification with GNÑs exhibits high homophily. To verify the quality of the learned adjacency with respect to homophily, 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. reppeseetts the odds for different weight intervals (recall that A is row and column normalized). For both Cora and Citeseer, nodes' connected with higher edge weights more likely to share the same label compared to nodes with lower or zero edge weights. Specifically, when Aúj 2 0.1, u; and by are almost 2.5 and 2.0 times more likely to share the same label on Cora and Citeseer respectively.
Homophily:
1.0
0.s
18 (8..0.0))
1001, 0.0))
(0.05 0.09)
(0 as. 0.00)
aast 0.11
10.0.
Ede wht intrrw
Figure 6: The odds of two nodes in the test set sharing the same label as a function of the edge weights learned by SLAPS.
6 Conclusion
We proposed SLAPS: model for learning the parameters of graph neural network and graph structure of the nodes connectivities simultancously from data. We identified a supervision starvation problem that emerges for graph structure learning, especially when training data is scarce. We proposed a solution to the supervision starvation problem by supplementing the training objective with a mell-motivated self-superv task. We showed the effectiveness of our model through comprehensive set of experiments and analyses.
10

---

7 Funding Transparency Statement
This work was fully funded by Borealis AL.
References
[1] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
[2] Álbert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512 1999.
[3] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. JMLRR, 7(Nov):2399-25) 2434, 2006.
[4] 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.03675 2020.
[5] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages
2020.
[6] Yu Chen, Lingfei Wu, and Mohammed Zaki. Deep iterative and adaptive learning for graph neural networks. In Neural Information Processing Systems (NeurIPS), 2020.
[7] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
[8] Luca Cosmo, Anees Kazi, Beyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein, Latent patient network learning for automatic diagnosis. arXiv preprint arXiv:2003. 2020.
[9] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang. Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint vrXiv:/806.023777 2018.
[10] Paul Erdós and Alfred Rényi. On random graphs. Publicationes Mathematicae Debrecen, 6: 290-297, 1959.
[11] James Fox and Sivasankaran Rajamanickam. How robust are graph neural networks to structural noise? arXiv preprint 1rXhv:1912.10200 2019.
[12] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In 2019.
[13] Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. arXiv preprint 1rXiv:1711.04045 2017.
[14] Spyros Gidaris and Nikos Komodakis. Generating classification weights with gnn denoising autoencoders for few-shot learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 21-30, 2019.
[15] 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 Knowledge Discovery & Data Mining, pages 2523-2532, 2020.
[16] 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 1Xiv:2005.0068/ 2020.
[17] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICLR, 2020.
11

---

[18] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1857-1867, 2020.
[19] Soobeom Jang, Seong-Eun Moon, and Jong-Seok Lee. Brain signal classification via learning connectivity structure. arXiv preprint arXiv: 1678, 2019.
[20] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph cearming-convoluttnn networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 11313-11320, 2019.
[21] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning-convolutiin Computer Vision and Pattern Recognition, pages 11313-1138 11320, 2019.
networks. In Proceedings of the IEEE/CVF Conference on
[22] Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang. Suhang Wang. Zitao Liu, and Jiliang Tang. Self-supervised learning on graphs: Deep insights and new direction. arXiv preprint arXiv:2006. 10141, 2020.
[23] 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, 2020.
[24] Daniel Johnson, Hugo Larochelle, and Daniel Tarlow. Learning graph structure with finite-state automaton layer. arXiv preprint arXiv:2007.04929, 2020.
[25] 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.
[26] Anees Kazi, Luca Cosmo, Nassir Navab, and Michael Bronstein. Differentiable graph module (dgm) for graph convolutional networks. arXiv preprint 0rXiv:2002.04999 2020.
[27] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[28] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecam lecun, htwp://.cc.....c/////////m/ com/extb//nnistt 2, 2010.
[29] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018
[30] Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. arXiv preprint 1 1801003266, 2018
[31] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang. Charlie Nash, William L Hamilton, David Duvenaud, Raquel Urtasun, and Richard S Zemel. Efficient graph generation with graph recurrent attention networks. arXiv preprint arXhv: 2019.
[32] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In NeurlPS, pages 13556-13566, 2019.
[33] Wei Liu, Junfeng He, and Shih-Fu Chang. Large graph construction for scalable semi-supervised learning. In ICMI. 2010.
[34] Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In leml, 2010.
[35] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. ICLR, 2020.
[36] Fabian Pedregosa, Gaël Varoquaux, Alexandre Granfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. JMLR, 12:2825-2830, 2011.
12

---

[37] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[38] Shah Rukh Qasim, Jan Kieseler, Yutaro liyama, and Maurizio Pierini. Learning representations of irregular particle-detector geometry with distance-weighter graph networks. The European Physical Journal C, 79(7):1-11, 2019.
[39] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323-22222 2000.
[40] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):11-80, 2008.
[41] 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
[42] Otilia Stretcu, Krishnamurthy Viswanathan, Dana Movshovitz-Attias Emmanouil Platanios, Sujith Ravi, and Andrew Tomkins. Graph agreement models for semi-supereised learning. In Neur/PS, pages 87233, 2019.
[43] Mohammed Suhail and Leonid Sigal. Mixture-kernel graph attention network for situation recognition. In Proceedings of the IEEE International Conference on Computer Vision, pages 10363-10333 10372, 2019.
[44] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 29065500):231--2333 2000.
[45] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[46] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. ICML, pages 1096-1103, 2008.
[47] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1-12, 2019.
[48] Xuan Wu, Lingxiao Zhao, and Leman Akoglu. A quest for structure: Jointly learning the graph structure and semi-supervised classification. In CIKM, pages 87-96, 2018.
[49] Liang Yang, Zesheng Kang, Xiaochun Cao, Di Jin, Bo Yang, and Yuanfang Guo. Topology optimization based graph convolutional network. In IJCAI, pages 4054-4061 2019.
[50] Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrmn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:1802.08773, 2018.
[51] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? arXiv preprint arXiv:2006.09136, 2020.
[52] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In ECML PKDD, 2020.
[53] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07294 2018.
[54] Jiawei Zhang. Haopeng Zhang, Congying Xia, and Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXhv:2001.051400 2020.
[55] Tong Zhao, Yozen Liu, Lennardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. arXiv preprint arXiv:2006.0688 2020.
13

---

[56] 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 arXiv:1902.00756. 2019.
[57] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
[58] Qikui Zhu, Bo Du, and Pingkun Yan. Self-supervised training of graph convolutional networks. arXiv preprint arXiv:2006. 2006.0000,,, 2020.
[59] Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. 2002.
[60] Yangiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure learning for robust representations: A survey, arXiv preprint arXiv:2103.0300 2021.
[61] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847-2856, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See supplementary material (the Limitations Section).
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The full set of assumptions are given in Theorem
(b) Did you include complete proofs of all theoretical results? [Yes] The proof is in the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No] Due copyright issues, we are not able to share an anonymous version of our code. However, the code will be publicly released upon the acceptance of the paper.
(b) Did you specify all the training details (e.g., e. data splits, hyperparameters, how they were chosen)? [Yes] See the dataset paragraph in Section 5 and the dataset statistics table and best hyperparameters table the supplementary material.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We ran each experiment 10 times and report the mean and standard deviation.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Implementation Details the supplementary material.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] The source websites specify the
licenses.
(c) Did you include any assets either in the supplemental material URL? [No]
14

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "xYLmPC1Apef", "reviewer": "Reviewer_5ygi", "summary": "The authors propose SLAPS, a methodology for deriving latent k-NN graphs for usage as edges of a GNN. They argue theoretically and empirically that it is important to combine self-supervised learning with graph structure learning, to avoid the prevalent edge starvation problem. They validate an approach consisting of a denoising self-supervised objective and various graph derivation strategies against relevant latent graph inference benchmarks, achieving impressive results.", "questions": "", "limitations": "", "rating": 8, "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": "I found the paper well-written, easy to follow and full of useful intuition.\n\nThe authors re-use a familiar construct for latent graph inference (the k-NN graph), and argue well for addition of a self-supervised loss when inferring it. This combination is novel in principle, and the obtained results appear significant. \n\nThe impact for GNN practitioners is clear. In many cases the GNN datasets will contain suboptimal graphs---or complete lack thereof---and different stages of processing may require a different graph. Besides the obvious applicability for relational reasoning, there is potential for spillover into set-structured tasks, or even sequence-style tasks, making the work relevant to a wider community. \n\nFurther, I really appreciate that the authors hadn't merely 'stitched' a self-supervised loss to the architecture without any justification. This choice was substantiated with clear theoretical arguments (edge starvation) as well as a workable hypothesis for denoising to be used. The qualitative analysis (e.g. on homophily properties) is also a nice touch. I recommend acceptance.\n\nI have some suggestions for follow-up experiments that may strengthen the paper further:\n- The theoretical expected ratio of starved edges is currently provided only for Erdős-Rényi graphs, which are purely uniformly distributed and may not be very naturalistic. I recommend the authors also expand their analysis to Barabási-Albert graphs, which might be more appropriate for many complex naturalistic phenomena.\n- Could the authors also include a fully-connected graph baseline (i.e. where all nodes are mutually connected), using a model such as GAT or MPNN? I find such baselines to always be insightful about the impact of graph inference.\n- The investigated latent graph inference baselines could be expanded to also include the Differentiable Graph Module (Kazi et al.), which attacks the \"added supervision\" problem via reinforcement learning-style objectives.\n\n==== Post-rebuttal update: I thank the authors for responding to my comments carefully and faithfully. The theoretical result on Barabási-Albert graphs will surely improve the paper. I have upgraded my score as a result. Well done!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HOQCQXqA3jw", "reviewer": "Reviewer_5rQg", "summary": "This paper combines the self-supervised learning with graph structure learning. A model named SLAPS is proposed to alleviate the \"supervision starvation\" problem of structure learning methods by denoising features using generated graph. Extensive experiments are conducted to show the effectiveness of the model.", "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": "The major strong points are:\n\nS1. The idea of combining SSL to GSL is interesting. To my knowledge, it might be the first work that combines GSL with self-supervised learning.\n\nS2. A model SLAPS is proposed, and appears to be effective under certain settings.\n\nNevertheless, there are also several weak points:\n\nW1. Arguable claims: The major argument of supervision starvation is arguably wrong. In fact, the so-called \"starved edges\" can be optimized by most graph structure learning methods based on metric learning. Specifically, the classifier, i.e. GNN_C in the paper, is a function of \\tilde{A}, as the graph learning module models the \\tilde{A} using graph learning parameters, it can be optimized.\nMoreover, many graph structure learning models apply graph regularization terms. For example, a feature smoothness loss [Chen et al., 2020] can be somehow viewed as a self-supervised term that regularizes the model by homophily assumption, which also provides self-supervision for \"starved_edges\". Besides, other graph regularization terms introduced in [Wei et al., 2020] can also somehow provide supervision for all the potential edges.\n\nW2. Model design: The defined graph structure learning is solely based on the input feature, which overlooks the adjacency matrix. Actually, the optimal adjacency matrix is mostly a shift [Zhao et al., 2021] from the original adjacency matrix. Neglecting the graph structure and generate it via features only apparently hampers the performance.\n\nW3. Experiments: The experimental setting is problematic. For models requiring an initial graph structure, the adjacency model is completely abandoned and instead replaced by a kNN graph. This setting is quite unfair to models that take both adjacency matrix and node features. For example, on Cora, IDGL should be around 84.5; however, with kNN graph as input, the reported results are around 70.9. \n\nBesides, the IDGL model actually is able to scale to OGB-Arxiv with a scalable version IDGL-Anch in the NIPS version [Chen et al., 2020] (The authors seem to be unaware of the NIPS version and cites the AAAI workshop version).\n\nW4. Other minor issues: \n- Grale [Halcrow et al., 2020], which also takes the features as input only, should also be compared. It is also interesting to compare Grale with SLAPS since Grale does not consider self-supervision. However, it is understandable since the code for Grale is unavailable.\n\n- References require revision: Some conference papers are cited with their arxiv version. NIPS version of IDGL should be cited.\n[Wei et al., 2020] Graph Structure Learning for Robust Graph Neural Networks. In KDD, 2020.\n[Chen et al., 2020] Iterative Deep Graph Learning for Graph Neural Networks- Better and Robust Node Embeddings. In NIPS, 2020.\n[Zhao et al., 2021] Data Augmentation for Graph Neural Networks. In AAAI, 2021.\n[Halcrow et al., 2020] Grale: Designing networks for graph learning. In KDD, 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed in the supplementary materials.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "GV-JSDIWVSF", "reviewer": "Reviewer_QmgH", "summary": "This paper studies graph structure learning. Given a dataset with latent but unobserved graph structure, the goal is to infer the graph structure and help downstream tasks. The authors specifically design a feature reconstruction task as self-supervision to improve the structure learning.", "questions": "", "limitations": "", "rating": 6, "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": "Overall I think the direction of using self-supervised learning for learning latent graph structure is very promising, especially for the cases that the authors point out, when the training signal is sparse and cannot propagate to many edges via a local GNN. The feature reconstruction is obviously a good starting point and reasonable choice.\n\nFor the experiments, I have several questions and concerns:\n\n(1) For experiment 5.3, the authors say they add noisy graph as input. But I think the assumption of structure learning is we don't observe any graph. Is this experiment aimed at testing how well the SLAPS can correct the perturbed edges? If so, I think it would be more fair to compare with the other graph structure learning baselines. \n\n(2) Experiment 5.4.1 is very interesting and shows that SLAPS could recover the ground-truth graph structure. However the experiment is conducted in that edges is randomly removed or added. A more realistic setting is that we have a set of nodes without any link to it, which is more close to your analysis about (starved edges). It would be more convincing if the authors could conduct such experiments (for example, randomly select K nodes and delete all the internal edges, or first run a cluster algorithm and pick one cluster to delete, or if you have timestamps, just pick the node after a particular timestamp). Also, it would be intersting to see some visualization results.\n\n(3) For experiment, I think it would be better to also include \"Graph Structure Learning for Robust Graph Neural Networks\" as a baseline (their regularization could also be regarded as a self-supervised task). Also, it would be better to add a GCN results with groundtruth graph structure for comparison (as upper bound)\n\n(4) The authors mainly show the results for node classification, where similar nodes will have tendency to be connected. What about other dataset, such as molecules? Is the feature reconstruction also beneficial to reconstruct a molecule structure? It would be interesting to also test it.\n\n(5) The notation is a little bit confusing to me in Table 1 (I previously thought self-training is L_DAE). It would be better to also include an ablation that remove the feature reconstruction (L_DAE) in the main table to support your hypothesis. \n\nOverall, I think the paper is well written and a good starting point in this research direction.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Would be better to add more experiments to support the effectiveness of feature reconstruction task as I described above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "EVM4tRjuWdv", "reviewer": "Reviewer_KpLH", "summary": "The paper first identifies a starved edge problem in latent graph learning. That is, nodes that are far from labeled nodes may receive insufficient supervision signal during learning. To address this issue, the paper then proposes to leverage a self-supervision signal, which comes from denoising the node features of the graph. Through taking both the noisy node features and the currently learned adjacency matrix as input, the feature denoising process acts as a regularizer to the learning of the adjacency matrix. Experiments on benchmark tasks show that the proposed strategy outperforms several comparison baseline models with or without adjacency matrices given. \n\nThe identification of the starved edge problem in latent graph learning is interesting. The proposed solution that introduces inductive bias in adjacency matrix learning through leveraging node features makes sense to me. Nevertheless, I found that the impact of the starved edge problem to a graph model’s predictive performance could be better justified with stronger evidence and the empirical studies in its current form could be further improved.\n", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well written and easy to follow. The related work section is informative and concise; the ablation studies provided in Sections 5.2-5.4 are beneficial.  \n\nGraph learning in data where graph structure is not readily available is an interesting and important research problem. Also, leveraging node features to regularize the learning of the adjacency matrix seems novel and makes sense to me. Nevertheless, I have the following two main concerns regarding the paper.\n\n1.  Stronger comparison baselines may be beneficial. The proposed model has a larger number of parameters than that of other comparison baseline models. In this sense, I am not sure where is the predictive improvement really coming from. That is, how much the accuracy improvement benefits from extra model freedoms/parameters? For example, the current baseline MLP is a very simple approach. To make the comparison more convincing, a stronger baseline may be useful, such as a Transformer Encoder (with attention) as a non-graph structure baseline for comparison. \n\n2.  I did not see a direct connection between the predictive improvement and addressing the supervision starvation problem (i.e., starved edges). It is useful to identify and show the existence of the starved edges problem in common graph datasets. But the importance of this issue, in terms of its impact on the predictive performance of the trained model, is not clear to me. I think it would be useful to show the importance of the starved edges directly since this is one of the main contribution claims of the paper. This is particularly relevant since as stated in Lines 297-298 that adding AdaEdge does not help. The paper suggests that such non-improvement may due to the proposed method has already learned a good graph structure. On the other hand, I think this might also indicate that some graph structures are just not important to the predictive targets at all. \n\nMinor comments:\n\n1.  Lines 188-189: for real-world graphs, how the percentage of starved edges was calculated is not clear to me.\n2.  Line 390: the statement of “learning the graph structure of the nodes simultaneously based on self-supervision” is a bit ambiguous to me. The self-supervision here is more like an extra task and just act as a model regularizer. It would be useful to make the statement more precise.\n\n==== post-rebuttal update ====\n\nI thank the authors for their response to my reviews; really appreciate that!\nI do not have any major concerns regarding the paper, and hope some of the experiments/analyses from the rebuttal can be added to the main text of the paper in revision.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed an approach for simultaneously inferring graph structure and GNN parameters. In particular, the authors pointed out the problem of edge starvation when learning on graphs with limited number of labels and proposed a self-supervised approach to alleviate such an approach. Experimental results prove the effectiveness of the proposed approach on existing latent graph inference benchmarks.

Overall, the reviewers like the simplicity of the proposed approach with good intuitions by pointing out the edge starvation problem. The authors addressed most of the concerns raised by the reviewers. 
Decision: Accept (Poster)