summaries: The article analyzes GCNs from spectral viewpoint, and discusses the performance of GCNs with respect to spectral filtering. The paper shows by experimentation, that the performance of GCNs mainly depend on low frequencies (lower end of the spectrum/eigen-pairs). It then shows that an MLP with low frequency information (Eigen-pairs) performs very well in graph tasks. Aspects such as smoothness and high frequency ablations are also studied.

summaries: This paper aims to study how GCN will behave under spectral perturbations/manipulations. The empirical numerical analysis on three benchmark datasets (cora, citeseer, pubmed) show that most of the necessary information is contained in the low-frequency domain. Based on that, the author propose to expand the node feature matrix with the eigenvectors corresponding to low-frequency domain and apply MLP on this new feature matrix. Experimental results show that the proposed method outperforms vanilla GCN and achieve comparable results on pubmed with other baselines.

summaries: The work presents an interesting analysis of GCN models under spectral manipulations and relates the performance of GCNs through bandpass filtering. The authors demonstrate that GCNs mainly rely more on low-frequencies rather than high-frequencies which is contrary to what is observed in signal processing. For this, the authors use band-pass filters which allow only a portion of the spectrum to be utilized by the GCN model. The major findings are as follows:

abstractText: In this work, we study the behavior of standard models for community detection under spectral manipulations. Through various ablation experiments, we evaluate the impact of bandpass filtering on the numerical performances of a GCN: we empirically show that most of the necessary and used information for nodes classification is contained in the low-frequency domain, and thus contrary to Euclidean graph (e.g., images), high-frequencies are less crucial to community detection. In particular, it is possible to obtain accuracies at a state-of-the-art level with simple classifiers that rely only on a few low frequencies: this is surprising because contrary to GCNs, no cascade of filtering along the graph structure is involved and it indicates that the important spectral components for the supervised community detection task are essentially in the low-frequency domain.

title: Community detection and stochastic block models: recent developments

venue: The Journal of Machine Learning Research,

authors:
Zeyuan Allen-Zhu
Yuanzhi Li

title: Lazysvd: Even faster svd decomposition yet without agonizing pain

venue: In Advances in Neural Information Processing Systems,

authors:
Mathieu Aubry
Ulrich Schlickewei
Daniel Cremers

title: The wave kernel signature: A quantum mechanical approach to shape analysis

venue: In 2011 IEEE international conference on computer vision workshops (ICCV workshops),

authors:
Mikhail Belkin
Partha Niyogi

title: Laplacian eigenmaps and spectral techniques for embedding and clustering

venue: In Advances in neural information processing systems,

authors:
Michael M Bronstein
Joan Bruna
Yann LeCun
Arthur Szlam
Pierre Vandergheynst

title: Geometric deep learning: going beyond euclidean data

venue: IEEE Signal Processing Magazine,

authors:
Joan Bruna
Wojciech Zaremba
Arthur Szlam
Yann LeCun

title: Spectral networks and locally connected networks on graphs

venue: arXiv preprint arXiv:1312.6203,

authors:
Chen Cai
Yusu Wang

title: A note on over-smoothing for graph neural networks

venue: arXiv preprint arXiv:2006.13318,

authors:
Jie Chen
Tengfei Ma
Cao Xiao

title: Fastgcn: Fast learning with graph convolutional networks via importance

venue: sampling. CoRR,

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

authors:
Shay Deutsch
Stefano Soatto

title: Spectral embedding of graph networks, 2020

authors:
Vishwaraj Doshi
Do Young Eun

title: Fiedler vector approximation via interacting random walks

venue: Proceedings of the ACM on Measurement and Analysis of Computing Systems,

authors:
Fernando Gama
Alejandro Ribeiro
Joan Bruna

title: Diffusion scattering transforms on graphs

venue: arXiv preprint arXiv:1806.08829,

authors:
Fernando Gama
Joan Bruna
Alejandro Ribeiro

title: Stability properties of graph neural networks

venue: arXiv preprint arXiv:1905.04497,

authors:
Feng Gao
Guy Wolf
Matthew Hirn

title: Geometric scattering for graph data analysis

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
David K Hammond
Pierre Vandergheynst
Rémi Gribonval

title: Wavelets on graphs via spectral graph theory

venue: Applied and Computational Harmonic Analysis,

authors:
Gao Huang
Zhuang Liu
Kilian Q. Weinberger

title: Densely connected convolutional networks

authors:
Wenbing Huang
Tong Zhang
Yu Rong
Junzhou Huang

title: Adaptive sampling towards fast graph representation learning

authors:
Wenbing Huang
Yu Rong
Tingyang Xu
Fuchun Sun
Junzhou Huang

title: Tackling oversmoothing for general graph convolutional networks, 2020

authors:
Nicolas Keriven
Alberto Bietti
Samuel Vaiter

title: Convergence and stability of graph convolutional networks on large random graphs, 2020

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

authors:
Johannes Klicpera
Stefan Weißenberger
Stephan Günnemann

title: Diffusion improves graph learning

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing

authors:
Qimai Li
Zhichao Han
Xiao-Ming Wu

title: Deeper insights into graph convolutional networks for semi-supervised learning

venue: arXiv preprint arXiv:1801.07606,

authors:
Andreas Loukas
Pierre Vandergheynst

title: Spectrally approximating large graphs with smaller graphs

venue: arXiv preprint arXiv:1802.07510,

title: Group invariant scattering

venue: Communications on Pure and Applied Mathematics,

authors:
Nikhil Mehta
Lawrence Carin
Piyush Rai

title: Stochastic blockmodels meet graph neural networks

venue: arXiv preprint arXiv:1905.05738,

authors:
Kenta Oono
Taiji Suzuki

title: Graph neural networks exponentially lose expressive power for node classification

venue: arXiv preprint arXiv:1905.10947,

title: Interferometric graph transform: a deep unsupervised graph representation

venue: In Proceedings of Machine Learning and Systems

authors:
Karl Rohe
Sourav Chatterjee
Bin Yu

title: Spectral clustering and the high-dimensional stochastic blockmodel

venue: The Annals of Statistics,

authors:
Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang

title: The truly deep graph convolutional networks for node classification

title: Dropedge: Towards deep graph convolutional networks on node classification

venue: In International Conference on Learning Representations,

authors:
Prithviraj Sen
Galileo Namata
Mustafa Bilgic
Lise Getoor
Brian Galligher
Tina EliassiRad

title: Collective classification in network data

venue: AI Magazine,

authors:
Ke Sun
Piotr Koniusz
Zhen Wang

title: Fisher-bures adversary graph convolutional networks

venue: In Uncertainty in Artificial Intelligence,

authors:
Saurabh Verma
Zhi-Li Zhang

title: Stability and generalization of graph convolutional neural networks

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

title: High-dimensional statistics: A non-asymptotic viewpoint, volume 48

authors:
Felix Wu
Amauri H Souza Jr.
Tianyi Zhang
Christopher Fifty
Tao Yu
Kilian Q Weinberger

title: Simplifying graph convolutional networks

authors:
Chaoqi Yang
Ruijie Wang
Shuochao Yao
Shengzhong Liu
Tarek Abdelzaher

title: Revisiting” over-smoothing” in deep gcns

venue: arXiv preprint arXiv:2003.13663,

authors:
Lingxiao Zhao
Leman Akoglu

title: Pairnorm: Tackling oversmoothing in gnns

venue: arXiv preprint arXiv:1909.12223,

authors:
Dingyuan Zhu
Ziwei Zhang
Peng Cui
Wenwu Zhu

title: Robust graph convolutional networks against adversarial attacks

heading: 1 INTRODUCTION

text:
Graph Convolutional Networks (GCNs) are the state of the art in community detection (Kipf & Welling, 2016). They correspond to Graph Neural Networks (GNNs) that propagate graph features through a cascade of linear operator and non-linearities, while exploiting the graph structure through a linear smoothing operator. However, the principles that allow GCNs to obtain good performances remain unclear. It is suggested in Li et al. (2018) that GCNs are eager to over-smooth their representation, which indicates they average too much neighborhood nodes and dilute classification information. The smoothing is generally interpreted as a low-pass filtering through the graph Laplacian, and finding a way to exploit high-frequencies of the graph Laplacian is an active research question (Oono & Suzuki, 2019). In contrast to this, our work actually suggests that, in the setting of community detection, graph Laplacian high-frequencies have actually a minor impact on the classification performances of a standard GCN, as opposed to standard Convolutional Neural Networks for vision, which are built thanks to image processing considerations.
Graph Signal Processing (GSP) is a popular field whose objective is to manipulate signals spectrum whose topology is given by a graph. Typically, this graph has a non-Euclidean structure, however many central theoretical results (Hammond et al., 2011) are based on an analogy with Euclidean, regular grids. For instance, a spectral component or frequency has to be understood as an eigenvalue of the Laplacian, yet it thus suffers from intrinsic issues such as isotropy (Oyallon, 2020). The principles of GSP are very appealing because they allow to use the dense literature of harmonic analysis, on graphs. Thus, this literature is at the core of many intuitions and drives many key ingredients of a GCN design, which evokes standard tools of signal processing: convolutions, shift invariance, wavelets, Fourier (Bronstein et al., 2017), etc. Here, we certainly observe several limits of this analogy in the context of community detection: for instance, we observe that discarding high-frequencies has a minor impact on a GCN behavior, because the spectrum of the graphs of the datasets that are used is essentially located in the low-frequency domain. This type of ideas is for instance core in spectral clustering algorithms.
Spectral clustering is a rather different point of view from deep supervised GCNs which studies node labeling in unsupervised contexts: it generally relies on generative models based on the graph spectrum. The main principle is to consider the eigenvectors corresponding to the smallest nonzero eigenvalues, referred to as Fiedler vectors (Doshi & Eun, 2020): those directions allow to define clusters, depending on the sign of a feature. Several theoretical guarantees can be obtained in the context of Stochastic Block Model approximation (Rohe et al., 2011). Our paper proposes
to establish a clear link with this approach: we show that the informative graph features are located in a low-frequency band of the graph Laplacian and do not need extra graph processing tools to be efficiently used in a deep supervised classifier.
This paper shows via various ablation experiments that experiments on standard community detection datasets like Cora, Citeseer, Pubmed can be conducted using only few frequencies of their respective graph spectrum without observing any significant performances drop. Other contributions are as follows: (a) First we show that most of the necessary information exploited by a GCN for a community detection task can actually be isolated in the very first eigenvectors of a Laplacian. (b) We numerically show that the high-frequency eigenvalues are less informative for the supervised community detection task and that a trained GCN is more stable to them. (c) We observe that a simple MLP method fed with handcrafted features allows to successfully deal with transdusctive datasets like Cora, Citeseer or Pubmed: to our knowledge, this is the first competitive results obtained with a MLP on those datasets.
We now discuss the organization of the paper: first, we discuss the related work in Sec. 2. We explain our notations as well as our work hypotheses in Sec. 3. Then, we study low-rank approximations of the graph Laplacian in Sec. 4.1. Finally, the end of Sec. 4 proposes several experiments to study the impact of high-frequencies on GCNs. A basic code is provided in the supplementary materials, and our code will be released on an online public repository at the time of publication.

heading: 2 RELATED WORK

text:
GCNs and Spectral GCNs Introduced in Kipf & Welling (2016), GCNs allow to deal with large graph structure in semi-supervised classification contexts. This type of model works at the node level, meaning that it uses locally the adjacency matrix. This approach has inspired a wide range of models, such as linear GCN (Wu et al., 2019), Graph Attention Networks (Veličković et al., 2017), GraphSAGE (Hamilton et al., 2017), etc. In general, this line of work does not consider directly the graph Laplacian. Another line of work corresponds to spectral methods, that employ filters which are designed from the spectrum of a graph Laplacian (Bruna et al., 2013). In general, those works make use of polynomials in the Laplacian (Defferrard et al., 2016), which are very similar to an anisotropic diffusion (Klicpera et al., 2019). All those references share the idea to manipulate bandpass filters that discriminate the different ranges of frequencies.
Over-smoothing in GCNs In the context of GCN, Li et al. (2018) is one of the first papers to notice that cascading low-pass filters can lead to a substantial information loss. The result of our work indicates that the important spectral components for detecting communities are already in the low-frequency domain and that this is not due to an architecture bias. Zhao & Akoglu (2019); Yang et al. (2020) proposes to introduce regularizations which address the loss of information issues. Cai & Wang (2020); Oono & Suzuki (2019) study the spectrum of a graph Laplacian under various transform, yet they consider the spectrum globally and in asymptotic settings, with a deep cascade of layers. Huang et al. (2020); Rong et al. (2019b) introduce data augmentations, whose aim is to alleviate over-smoothing in deep networks: we study GCNs without this ad-hoc procedure.
Spectral clustering and low rank approximation As the literature about spectral clustering is large, we mainly focus on the subset that connects directly with GCN. Mehta et al. (2019) proposes to learn an unsupervised auto-encoder in the framework of a Stochastic Block Model. Oono & Suzuki (2019) introduces the Erdös – Renyi model in the GCN analysis, but only in an asymptotic setting. Loukas & Vandergheynst (2018) studies the graph topology preservation under the coarsening of the graph, which could be a potential direction for future works.
Node embedding A MLP approach can be understood as an embedding at the node level. For instance, Aubry et al. (2011) applies a spectral embedding combined with a diffusion process for shape analysis, which allows point-wise comparisons. We should also point Deutsch & Soatto (2020) that uses a node embedding, based on the spectrum of a quite modified graph Laplacian, obtained from on a measure of node centrality.
Graph Scattering Networks (GSN) This class model explicitly employs band-pass based on the spectrum of a graph Laplacian and it is thus necessary to review it. Gao et al. (2019); Gama et al.
(2018; 2019) are a class of neural networks built upon an analogy with a Scattering Transform (Mallat, 2012). They typically rely on a cascade of wavelets followed by an absolute value: the objective of each wavelet is to separate multi-scale information into dyadic bandpass filters. This method relies heavily on each eigenvector of the Laplacian and the dyadic space is typically constructed from a diffusion process at dyadic intervals. Interferometric Graph Transform on the other hand relies on the concept of demodulation, which is clear in the context of Lie groups but unclear for community detection tasks (Oyallon, 2020).
GCN stability Stability of GCNs has been theoretically studied in Gama et al. (2019), which shows that defining a generic notion of deformations is difficult. Surprisingly, it was noted in Oyallon (2020) that stability is not a key component to good performances. The stability of GCN has also been investigated in Verma & Zhang (2019) but only considers neural networks with a single layer and relies on the whole spectrum of the learned layer. Keriven et al. (2020) considers the stability of GCNs, and relies on an implicit Euclidean structure: it is unclear if this holds in our settings. Sun et al. (2020) is one of the first works to study adversarial examples linked to the node connectivity and introduces a loss to reduce their effects. Zhu et al. (2019) also addresses the stability issues by embedding GCNs in a continuous representation. None of these work directly related a trained GCN to spectral perturbations.

heading: 3 FRAMEWORK

heading: 3.1 METHOD

text:
We first describe our baseline model. Our initial graph data are node features X obtained from a graph with N nodes and an adjacency matrix A with diagonal degree matrix D. We consider GCNs f(X,A) as introduced in (Kipf & Welling, 2016), which correspond to GNNs that propagate features graph input H(0) , X through a cascade of layers, via the iteration:
H(l+1) , σ ( ÃH(l)W (l) ) , (1)
where Ã = 12 (I + D −1/2AD−1/2), σ a point-wise non-linearity and W (l) a parametrized affine operator. Note that if Ã = IN , then Eq. 1 is simply an MLP, which makes its implementation simple. The 12 factor is a normalization factor to obtain ‖Ã‖ = 1. In the semi-supervised setting, a final layer f(X, Ã) , H(L) is fed to a supervised loss ` (here a softmax) and {W (0), ...,WL−1} are trained in an end-to-end manner to adjust the label of each node. We note that for undirected graph, Ã is a positive definite matrix with positive weights, which is understood as an averaging operator Li et al. (2018), as, ignoring D̃, we see that for some node features X , we have:
[(IN +A)X]i = Xi + ∑ j→i Ai,jXj . (2)
We remark that multiple choices of averaging operators are possible: as briefly discussed in Appendix A.3 other formulations did not change our numerical conclusions, thus we decided to keep the simplest to be handled mathematically. We are interested in analyzing the properties of spectral approximations of Ã. We consider the decreasing set of eigenvalues Λ = {λk}k≥0 of Ã, such that λk ≥ λk+1, and we denote by uk the k-th eigenvector corresponding to λk ∈ Λ. We remind that Λ ⊂ [0, 1] and that λ0 = 1 can be interpreted as the lowest frequency of the graph Laplacian. Since the adjacency matrix is normalized, one basis of λ0’s eigenspace is constituted by the constant vectors of 1 supported on each connected component. We then write:
Ã[k1,k2] , ∑
k1≤k≤k2
λkuku T k , (3)
such that Ã = Ã[0,N ]. We are interested to study the degradation accuracy if we replace Ã with Ã[0,k] or Ã[k,N ] for some 0 < k < N . The next section explains that under standard but oversimplifying assumptions, an approximation of the type Ã[0,k] is relevant for community detection tasks.

heading: 3.2 UNDERSTANDING LOW RANK APPROXIMATIONS FOR GCNS

text:
We now justify our approach under the standard setting of the Stochastic Block Model (Abbe, 2017), and we will simply remind the reader of several elementary results. This model corresponds to a generative model that describes the interaction between r communities {C1, ..., Cr}. Assuming that two nodes i, j belong to the communities Cri , Crj , an edge is sampled with a probability pri,rj (Rohe et al., 2011). For the sake of simplicity, let us assume that r = 2, that the probability of an edge between two nodes i, j is p if those nodes belong to the same community and q < p otherwise, and that both communities correspond to |C| nodes. In this case, the unnormalized expected adjacency matrix is given by: p · · · p q · · · q ... ... ... ... p · · · p q · · · q q · · · q p · · · p ... ... ...
... q · · · q p · · · p
 , (4)
where we grouped in matrix block the nodes from the same community. We note that the two dominant eigenvectors are given by:
u1 = [ |C| times︷ ︸︸ ︷ 1, ..., 1, 1, ..., 1︸ ︷︷ ︸
|C| times
] and u2 = [ |C| times︷ ︸︸ ︷ 1, ..., 1,−1, ...,−1︸ ︷︷ ︸
|C| times
] . (5)
Observe that the second eigenvector u2 captures all the information about the two communities, through the sign of its coefficients. Here, the spectral gap (the ratio between the two dominant eigenvalues) is given by 0 ≤ p−qp+q < 1 and ideally this spectral gap should be as large as possible for identifying the two communities. If the number of nodes is large, concentration results (Wainwright, 2019) imply that the empirical adjacency matrix concentrates around its expectation, and that under this assumption, a low-rank approximation Ã[0,2] captures most of the available information about the two communities. We illustrate this idea on Fig. 1. While these assumptions might not hold in practice, it justifies why low-rank approximations of a Laplacian are relevant in the setting of community detection and it explains why high-frequencies might not be as important as low-frequencies for supervised community detection task. The next section validates empirically this approach in the context of GCNs and simpler architectures.

heading: 4 NUMERICAL EXPERIMENTS

text:
Matching the previous work practice, we focus on the three classical benchmark dataset for community detection: Cora, Citeseer and Pubmed (Sen et al., 2008). The task consists in classifying the research topic of papers in three citation datasets. Those tasks are transductive, meaning all node features are accessible during training. We apply the full-supervised training fashion used in Huang et al. (2016), Chen et al. (2018), and Rong et al. (2019b) on all datasets in our experiments. Fig. 2 plots the 3 spectra Λ in decreasing order for each of those datasets. The three datasets exhibit a significant spectral gap, which is aligned with the model of Sec. 1b. Note that Pubmed has one connected component, and that the decay of its spectrum is fast compared to Cora or Citeseer, which indicates a low-dimensional structure (Belkin & Niyogi, 2002). The statistics of each dataset are listed in the supplemental materials.
We choose σ to be the ReLU non-linearity (Krizhevsky et al., 2012). Unless specified otherwise, the weights of our models (either GCN or MLP) are optimized via Adam, with an initial learning rate 0.01 and weight decay of 0.001, during 800 epochs. We use by default a dropout of 0.5. Our model consists in GCN layers with 2 hidden layers of size 128. In all experiments, we cross validate our hyper-parameters on a validation set, using an early stopping at epoch 400. Unless specified otherwise, each plot is obtained by an average over at least 3 different seeds.

heading: 4.1 LOW RANK APPROXIMATION

text:
GCN ablation Here, we consider the two projections Ã[0,k] and Ã[N−k,N ], where k is adjusted to retain only a portion of the spectrum. Via the GSP lens, those projections can be interpreted respectively as high-pass and low-pass filters. As explained in Sec. 1b, those projections will allow to study which frequency band is important for the community detection task. Fig. 3 and Fig. 4 report the respective numerical performance when considering the models f(X, Ã[N−k,N ]) and f(X, Ã[0,k]) for some k.
On Fig. 3, we observe that retaining only very few frequencies (less than 10%) does not degrade much the accuracy of the original network. This does not contradict the observation of Li et al. (2018) which studies empirically the over-smoothing phenomenon, as our finding indicates that a GCN uses mainly the low frequency domain. For Pubmed, using almost all the high-frequencies is required to recover the original accuracy of our model. Interestingly, deeper GCNs seem to benefit from the high frequency ablation, yet their accuracy remains below their shallow counter-part and
they are still difficult to train, as shown on Cora. This instability to spectral perturbations is further studied in Sec 4.2. Fig. 4 indicates that the major information for supervised community detection is contained in the low frequencies: dropping the latter leads to substantial accuracy drop, even for a shallow GCN.
MLP ablation We further study how informative low-frequencies are for community detection tasks via a spare ablation experiment based on a MLP. We augment each graph features X through the concatenation Xk = [X,uT1 , ..., u T k ] of the first k eigenvectors. For a fair evaluation, we used exactly the same hyper-parameters as for the experiments above. Fig. 5 reports the accuracy of our MLP trained on Xk as a function of k. We see that using a fraction kK ≤ 20% of the eigenvectors
allows to recover the performance of a GCN trained end-to-end. More surprisingly, we note that as k increases, the accuracy drops, which indicates that high-frequencies behave like a residual noise that is not well filtered by a MLP, and rather overfitted. This is particularly true for Pubmed, which has a fast spectral decay and for which the low frequencies seem to be the most informative. This experiment emphasizes that a low rank approximation of the Laplacian of the graph of a community detection task can be beneficial to a MLP classifier.
Boosting MLP performances We perform a hyper-parameter grid search on each dataset to investigate MLP strengths further, and report the case giving the best accuracy on each validation set. We summarize our findings in Tab. 1. In particular, one uses a fraction 5.9%, 15.0% and 0.7% of the spectrum respectively on Cora, Citeseer and Pubmed in order to obtain our best performances. We note that a MLP trained solely onX already outperforms the approach of Chen et al. (2018), without relying on a graph structure. More details on the methodology are provided in the supplementary material. This simple model is highly competitive with concurrent works like Rong et al. (2019b); Huang et al. (2018); Chen et al. (2018), and in particular with vanilla GCNs. Note also that our method does not incorporate any data augmentation procedure such as Rong et al. (2019a), and thus a performance gap still remains. We could also potentially incorporated data augmentation procedures, at the price of an extended computation time. We conclude that GCNs do not compute more complex invariants than a MLP fed with low-frequencies, in the context of community detection.
Note on the computational overhead The MLPs introduced above are of interest if the corresponding graph topology is fixed, with a large graph, and high connectivity. Indeed, using a MLP
allows to easily employ mini-batch strategies and the training data can be reduced according to the fraction of low frequencies being kept: an exact k-truncated SVD has a complexity about O(kN2). We note that fast k-truncated -approximate SVD algrotithms for sparse matrix exist (Allen-Zhu & Li, 2016): if ρ is the number of non-zero coefficients of Ã, the complexity can be aboutO(kρ + k2N ).
4.2 STABILITY TO HIGH FREQUENCIES
We now study the stability of a GCN w.r.t. spectrum perturbations. In the case of image processing, it is standard that low-frequencies almost do not affect the classification performances and that perturbations of high-frequencies lead to instabilities. We would like to validate that this principle does not hold here, and to do so, we consider ∇Λ`, which is the gradient w.r.t. every singular value λk. Small amplitudes of | ∂`∂λk | indicate more stable coefficients. Fig. 6 plots the amplitude of the gradient w.r.t. λk at the initialization of a GCN and after training. First, we note that a GCN is more sensitive to spectral perturbations after training, which is logical because the GCN adapts its weights to the specific structure of a given graph. After training, we remark that the highfrequency perturbations have a small impact compared to the low-frequency perturbations on the three datasets, except for Pubmed which has dominant low-frequencies. This is consistent with our previous findings.

heading: 4.3 SMOOTHNESS AND SELF-LOOPS

text:
As proposed by Kipf & Welling (2016), we now study how the self-loop of Ã affects our GCN training procedure and in particular, we study it through the lens of spectral analysis. We consider:
Ãη , 1
1 + η
( ηIN + Ã ) , (6)
where η ∈ [− 12 ,+∞[ can be understood as a smoothness parameter. Note that for η < 0, the spectrum of Ãη is not necessarily positive and we renormalize Ãη such that ‖Ãη‖ = 1,∀η. Here, Ãη enhances the high-frequencies of the averaging while allowing to balance a trade-off between a smoothing and an identity operator, which can be here observed as
Ãη ∼ η→∞ I and Ã0 = Ã . (7)
As observed in Li et al. (2018), oversmoothing phenomena occur because one propagates an input through a cascade of n smoothing operators. Here, we note that a Taylor expansion reveals asymptotically this trade-off for large η:
Ãnη = ∑ λk=1 uku T k + ∑ λk<1 uku T k − n(1− λk) η uku T k +O( 1 η2 ) . (8)
Thus depending on the nature of uk, the degree of averaging can be adjusted. The details of the calculations are given in App. A.4. Fig. 7 indicates that it is possible to adjust the degree of smoothing to train deeper networks (in the degenerate setting η < 0) and to slightly boost the accuracy of a GCN. We report both the training and testing accuracies to emphasize the impact of η on the training dynamics of a GCN. Citeseer exhibits a significant generalization gap for large values of η and a depth of 4: high-frequencies deteriorate the generalization properties. We note that varying η allows to improve the training accuracy of deeper GCNs, though larger η emphasizes higher-frequencies which leads to a significant drop in accuracy. We finally observe that selecting η via the best accuracy on a validation set allows minor boosts in performances: of the order of 1.4% (η = 1) and 1.5% (η = 0.5) for a GCN of depth 2 respectively on Citeseer and Pubmed.

heading: 5 CONCLUSION

text:
In this work, we have studied the classification performance of a GCN if applying low-pass and high-pass filters, in the context of community detection. Our finding is that by design, a GCN mainly relies on the low-frequencies, and that the high-frequencies have less impact on this task. Then, we are able to design MLPs that rely simply on a few eigenvectors of the graph Laplacian that are competitive with deep supervised graph approaches. We also study the stability of a GCN w.r.t. spectral perturbations, and show that they are more robust to high-frequency, which is counterintuitive when compared to vanilla CNNs.
Our work indicates that not only more difficult graph benchmarks are necessary, but also benchmarks whose optimal model would rely on the high-frequencies of a graph Laplacian. It also shows that standard GSP tools such as graph wavelets might be simplified to low-pass filters, in the context of community detection, as we observed that the high-frequency does not bring a significant amount of information, and can even be interpreted as a residual noise, in this particular setting. Note also that our methodology can help to identify if an accuracy improvement of a given algorithm is due to a better processing of high frequencies.

heading: A APPENDIX

heading: A.1 DATASET STATISTICS

heading: Datasets Nodes Edges Classes Features Traing/Validation/Testing split

heading: A.2 HYPER-PARAMETER DESCRIPTION

heading: A.3 ON THE CHOICE OF THE NORMALIZATION

text:
GCNs defined in Kipf & Welling (2016) don’t exactly used the first order Laplacian approximation, but introduce a normalization trick : Ã = (D + IN )− 1 2 (A + IN )(D + IN )
− 12 . Using the standard hyper-parameters defined in Section 4, we averaged our results on 3 seeds and observed no significant difference across datasets, as shown in Fig. 8.

heading: A.4 TAYLOR EXPANSION

text:
We recall that Ãη = 11+η ( ηIN + Ã ) . Thus an eigenvector uk of Ã corresponding to the eigenvalue λk is an eigenvector of Ãη corresponding to the eigenvalue η+λk1+η . Therefore, we have:
Ãη = ∑ λk η + λk 1 + η uku T k ,
And thus,
Ãnη = ∑ λk ( η + λk 1 + η )n uku T k
Ãnη = ∑ λk=1 uku T k + ∑ λk<1 ( η + λk 1 + η )n uku T k
Ãnη = ∑ λk=1 uku T k + ∑ λk<1 uku T k − n(1− λk) η uku T k +O( 1 η2 )


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

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

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

abstractText: 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 taskspecific 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.

authors:
Réka Albert
Albert-László Barabási

title: Statistical mechanics of complex networks

venue: Reviews of modern physics,

authors:
Albert-László Barabási
Réka Albert

title: Emergence of scaling in random networks. science

authors:
Mikhail Belkin
Partha Niyogi
Vikas Sindhwani

title: Manifold regularization: A geometric framework for learning from labeled and unlabeled examples

authors:
Ines Chami
Sami Abu-El-Haija
Bryan Perozzi
Christopher Ré
Kevin Murphy

title: Machine learning on graphs: A model and comprehensive taxonomy

venue: arXiv preprint arXiv:2005.03675,

authors:
Deli Chen
Yankai Lin
Wei Li
Peng Li
Jie Zhou
Xu Sun

title: Measuring and relieving the over-smoothing problem for graph neural networks from the topological view

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Yu Chen
Lingfei Wu
Mohammed J. Zaki

title: Deep iterative and adaptive learning for graph neural networks

venue: In Neural Information Processing Systems (NeurIPS),

authors:
Krzysztof Choromanski
Valerii Likhosherstov
David Dohan
Xingyou Song
Andreea Gane
Tamas Sarlos
Peter Hawkins
Jared Davis
Afroz Mohiuddin
Lukasz Kaiser

title: Rethinking attention with performers

authors:
Luca Cosmo
Anees Kazi
Seyed-Ahmad Ahmadi
Nassir Navab
Michael Bronstein

title: Latent patient network learning for automatic diagnosis

venue: arXiv preprint arXiv:2003.13620,

authors:
Hanjun Dai
Hui Li
Tian Tian
Xin Huang
Lin Wang
Jun Zhu
Le Song

title: Adversarial attack on graph structured data

venue: arXiv preprint arXiv:1806.02371,

authors:
James Fox
Sivasankaran Rajamanickam

title: How robust are graph neural networks to structural noise

venue: arXiv preprint arXiv:1912.10206,

authors:
Luca Franceschi
Mathias Niepert
Massimiliano Pontil
Xiao He

title: Learning discrete structures for graph neural networks

venue: In ICML,

authors:
Victor Garcia
Joan Bruna

title: Few-shot learning with graph neural networks

venue: arXiv preprint arXiv:1711.04043,

authors:
Spyros Gidaris
Nikos Komodakis

title: Generating classification weights with gnn denoising autoencoders for few-shot learning

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Jonathan Halcrow
Alexandru Mosoi
Sam Ruth
Bryan Perozzi

title: Grale: Designing networks for graph learning

venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Weihua Hu
Matthias Fey
Marinka Zitnik
Yuxiao Dong
Hongyu Ren
Bowen Liu
Michele Catasta
Jure Leskovec

title: Open graph benchmark: Datasets for machine learning on graphs

authors:
Weihua Hu
Bowen Liu
Joseph Gomes
Marinka Zitnik
Percy Liang
Vijay Pande
Jure Leskovec

title: Strategies for pre-training graph neural networks

venue: In ICLR,

authors:
Ziniu Hu
Yuxiao Dong
Kuansan Wang
Kai-Wei Chang
Yizhou Sun

title: Gpt-gnn: Generative pre-training of graph neural networks

authors:
Soobeom Jang
Seong-Eun Moon
Jong-Seok Lee

title: Brain signal classification via learning connectivity structure

venue: arXiv preprint arXiv:1905.11678,

authors:
Bo Jiang
Ziyan Zhang
Doudou Lin
Jin Tang
Bin Luo

title: Semi-supervised learning with graph learning-convolutional networks

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Wei Jin
Tyler Derr
Haochen Liu
Yiqi Wang
Suhang Wang
Zitao Liu
Jiliang Tang

title: Self-supervised learning on graphs: Deep insights and new direction

authors:
Wei Jin
Yao Ma
Xiaorui Liu
Xianfeng Tang
Suhang Wang
Jiliang Tang

title: Graph structure learning for robust graph neural networks

venue: arXiv preprint arXiv:2005.10203,

authors:
Daniel D Johnson
Hugo Larochelle
Daniel Tarlow

title: Learning graph structure with a finite-state automaton layer

venue: arXiv preprint arXiv:2007.04929,

authors:
Seyed Mehran Kazemi
Rishab Goel
Kshitij Jain
Ivan Kobyzev
Akshay Sethi
Peter Forsyth
Pascal Poupart

title: Representation learning for dynamic graphs: A survey

authors:
Anees Kazi
Luca Cosmo
Nassir Navab
Michael Bronstein

title: Differentiable graph module (dgm) for graph convolutional networks

venue: arXiv preprint arXiv:2002.04999,

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Yann LeCun
Corinna Cortes
CJ Burges

title: Mnist handwritten digit database

venue: ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist,

venue: In AAAI,

authors:
Ruoyu Li
Sheng Wang
Feiyun Zhu
Junzhou Huang

title: Adaptive graph convolutional neural networks

venue: arXiv preprint arXiv:1801.03226,

authors:
Renjie Liao
Yujia Li
Yang Song
Shenlong Wang
Charlie Nash
William L Hamilton
David Duvenaud
Raquel Urtasun
Richard S Zemel

title: Efficient graph generation with graph recurrent attention

authors:
Jenny Liu
Aviral Kumar
Jimmy Ba
Jamie Kiros
Kevin Swersky

title: Graph normalizing flows

venue: In NeurIPS,

authors:
Wei Liu
Junfeng He
Shih-Fu Chang

title: Large graph construction for scalable semi-supervised learning

authors:
Vinod Nair
Geoffrey E Hinton

title: Rectified linear units improve restricted boltzmann machines

venue: In Icml,

authors:
Fabian Pedregosa
Gaël Varoquaux
Alexandre Gramfort
Vincent Michel
Bertrand Thirion
Olivier Grisel
Mathieu Blondel
Peter Prettenhofer
Ron Weiss
Vincent Dubourg

title: Scikitlearn: Machine learning in python

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

venue: In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,

authors:
Shah Rukh Qasim
Jan Kieseler
Yutaro Iiyama
Maurizio Pierini

title: Learning representations of irregular particle-detector geometry with distance-weighted graph networks

venue: The European Physical Journal C,

authors:
Sam T Roweis
Lawrence K Saul

title: Nonlinear dimensionality reduction by locally linear embedding

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

venue: IEEE Transactions on Neural Networks,

authors:
Prithviraj Sen
Galileo Namata
Mustafa Bilgic
Lise Getoor
Brian Galligher
Tina Eliassi- Rad

venue: AI magazine,

authors:
Otilia Stretcu
Krishnamurthy Viswanathan
Dana Movshovitz-Attias
Emmanouil Platanios
Sujith Ravi
Andrew Tomkins

title: Graph agreement models for semi-supervised learning

authors:
Mohammed Suhail
Leonid Sigal

title: Mixture-kernel graph attention network for situation recognition

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Joshua B Tenenbaum
Vin De Silva
John C Langford

title: A global geometric framework for nonlinear dimensionality reduction

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Lio
Yoshua Bengio

title: Graph attention networks

authors:
Pascal Vincent
Hugo Larochelle
Yoshua Bengio
Pierre-Antoine Manzagol

title: Extracting and composing robust features with denoising autoencoders

authors:
Yue Wang
Yongbin Sun
Ziwei Liu
Sanjay E Sarma
Michael M Bronstein
Justin M Solomon

title: Dynamic graph cnn for learning on point clouds

venue: Acm Transactions On Graphics (tog),

authors:
Xuan Wu
Lingxiao Zhao
Leman Akoglu

title: A quest for structure: Jointly learning the graph structure and semi-supervised classification

venue: In CIKM,

authors:
Liang Yang
Zesheng Kang
Xiaochun Cao
Di Jin
Bo Yang
Yuanfang Guo

title: Topology optimization based graph convolutional network

venue: In IJCAI,

authors:
Jiaxuan You
Rex Ying
Xiang Ren
William L Hamilton
Jure Leskovec

title: Graphrnn: Generating realistic graphs with deep auto-regressive models

venue: arXiv preprint arXiv:1802.08773,

authors:
Yuning You
Tianlong Chen
Zhangyang Wang
Yang Shen

title: When does self-supervision help graph convolutional networks

venue: arXiv preprint arXiv:2006.09136,

authors:
Donghan Yu
Ruohong Zhang
Zhengbao Jiang
Yuexin Wu
Yiming Yang

title: Graph-revised convolutional network

venue: In ECML PKDD,

authors:
Jiani Zhang
Xingjian Shi
Junyuan Xie
Hao Ma
Irwin King
Dit-Yan Yeung

title: Gaan: Gated attention networks for learning on large and spatiotemporal graphs

venue: arXiv preprint arXiv:1803.07294,

authors:
Jiawei Zhang
Haopeng Zhang
Congying Xia
Li Sun

title: Graph-bert: Only attention is needed for learning graph representations

venue: arXiv preprint arXiv:2001.05140,

authors:
Tong Zhao
Yozen Liu
Leonardo Neves
Oliver Woodford
Meng Jiang
Neil Shah

title: Data augmentation for graph neural networks

venue: arXiv preprint arXiv:2006.06830,

authors:
Hao Zhu
Yankai Lin
Zhiyuan Liu
Jie Fu
Tat-seng Chua
Maosong Sun

title: Graph neural networks with generated parameters for relation extraction

authors:
Jiong Zhu
Yujun Yan
Lingxiao Zhao
Mark Heimann
Leman Akoglu
Danai Koutra

title: Beyond homophily in graph neural networks: Current limitations and effective designs

venue: Advances in Neural Information Processing Systems,

authors:
Qikui Zhu
Bo Du
Pingkun Yan

title: Self-supervised training of graph convolutional networks

venue: arXiv preprint arXiv:2006.02380,

authors:
Xiaojin Zhu
Zoubin Ghahramani

title: Learning from labeled and unlabeled data with label propagation

authors:
Yanqiao Zhu
Weizhi Xu
Jinghao Zhang
Qiang Liu
Shu Wu
Liang Wang

title: Deep graph structure learning for robust representations: A survey

venue: arXiv preprint arXiv:2103.03036,

heading: 1 Introduction

text:
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 a key component to the success of the research in this area. Specifically, GNNs have shown promising results for semi-supervised classification when the available graph structure exhibits a high degree of homophily (i.e. connected nodes often belong to the same class) [57].
We study the applicability of GNNs to (semi-supervised) classification problems where a 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 in higher predictive performance compared to the former approach (see, e.g., [12]).
We identify a supervision starvation problem in latent graph learning approaches in which the edges between pairs of nodes that are far from labeled nodes receive insufficient supervision; this results in learning poor structures away from labeled nodes and hence poor generalization. We propose a solution for this problem by adopting a 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 AI.
35th Conference on Neural Information Processing Systems (NeurIPS 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 a 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 a solution for the identified problem through self-supervision, 3) developing SLAPS, a latent graph learning model that adopts the self-supervised solution, 4) providing comprehensive 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.

heading: 2 Related work

text:
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 a full survey.
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 [39, 44, 3]. 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, in [14] a (fixed) kNN graph using the cosine similarity of the node features is 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).
Fully connected graph: Another approach is to 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 [e.g., 43], natural language processing [e.g., 56], and few-shot learning [e.g., 13]. The complexity of this approach grows rapidly making it 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 connected. Their approach relies on an initial graph structure to define the local neighborhoods.
Latent graph learning: Instead of a similarity graph based on the initial features, one may use a graph generator with learnable parameters. In [30], a fully connected graph is created based on a bilinear similarity function with learnable parameters. In [12], a Bernoulli distribution is learned for each possible edge and graph structures are created through sampling from these distributions. In [49], 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. In [38, 21, 8], 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 a 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 [24], 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 general-purpose datasets without access to domain knowledge.
Proposed method: Our model falls within the latent graph learning category. We supplement the training with a self-supervised objective to increase the amount of supervision in learning a 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 et al. [51]), but it 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.

heading: 3 Background and notation

text: We use lowercase letters to denote scalars, bold lowercase letters to denote vectors and bold uppercase letters to denote matrices. I represents an identity matrix. For a vector v, we represent its ith element as vi. For a matrixM , we represent the ith row asMi and the element at the ith row and jth column as Mij . For an attributed graph, we use n, m and f to represent the number of nodes, edges, and features respectively, and denote the graph as G = {V,A,X} where V = {v1, . . . , vn} is a set of nodes,A ∈ Rn×n is an adjacency matrix withAij indicating the weight of the edge from vi to vj (Aij = 0 implies no edge), andX ∈ Rn×f is a matrix whose rows correspond to node features. Graph convolutional networks (GCNs) [27] are a powerful variant of GNNs. For a graph G = {V,A,X} with a degree matrix D, layer l of the GCN architecture can be defined as H(l) = σ(ÂH(l−1)W (l)) where Â represents a normalized adjacency matrix,H(l−1) ∈ Rn×dl−1 represents the node representations in layer l-1 (H(0) = X), W (l) ∈ Rdl−1×dl is a weight matrix, σ is an activation function such as ReLU [34], and H(l) ∈ Rn×dl is the updated node embeddings. For undirected graphs where the adjacency is symmetric, Â = D− 1 2 (A + I)D− 1 2 corresponds to a row-and-column normalized adjacency with self-loops, and for directed graphs where the adjacency is not necessarily symmetric, Â =D−1(A+ I) corresponds to a row normalized adjacency matrix with self-loops. Here,D is a (diagonal) degree matrix for (A+ I) defined asDii = 1 + ∑ jAij .

heading: 4 Proposed method: SLAPS

text: SLAPS consists of four components: 1) generator, 2) adjacency processor, 3) classifier, and 4) self-supervision. Figure 1 illustrates these components. In the next three subsections, we explain the first three components. Then, we point out a supervision starvation problem for a model based only on these components. Then we describe the self-supervision component as a solution to the supervision starvation problem and the full SLAPS model.

heading: 4.1 Generator

text:
The generator is a function G : Rn×f → Rn×n with parameters θG which takes the node features X ∈ Rn×f as input and produces a matrix Ã ∈ Rn×n as output. We consider the following two generators and leave experimenting with more sophisticated graph generators (e.g., [50, 32, 31]) and models with tractable adjacency computations (e.g., [7]) as future work.
Full parameterization (FP): For this generator, θG ∈ Rn×n and the generator function is defined as Ã = GFP (X;θG) = θG. That is, the generator ignores the input node features and directly optimizes the adjacency matrix. FP is similar to the generator in LDS [12] except that the generator of LDS treats each element of Ã as the parameter of a Bernoulli distribution and samples graph structures from these distributions. FP is simple and flexible for learning any adjacency matrix but adds n2 parameters which limits scalability and makes the model susceptible to overfitting.
MLP-kNN: Here, θG corresponds to the weights of a multi-layer perceptron (MLP) and Ã = GMLP(X;θG) = kNN(MLP(X)), where MLP : Rn×f → Rn×f ′ is an MLP that produces a matrix with updated node representations X ′; kNN : Rn×f ′ → Rn×n produces a sparse matrix. The implementation details for the kNN operation is provided in the supplementary material.
Initialization and variants of MLP-kNN: Let AkNN represent an adjacency matrix created by applying a kNN function on the initial node features. One smart initialization for θG is to initialize it
in a way that the generator initially generatesAkNN (i.e. Ã = AkNN before training starts). This can be trivially done for the FP generator by initializing θG toAkNN . For MLP-kNN, we consider two variants. In one, hereafter referred to simply as 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 θG with the identity matrix to ensure that the output of the MLP is initially the same as its input and the kNN graph created on these outputs is equivalent to AkNN (alternatively, one may use other MLP variants but pre-train the weights to output AkNN before the main training starts.). MLP-D can be thought of as assigning different weights to different features and then computing node similarities.

heading: 4.2 Adjacency processor

text:
The output Ã of the generator may have both positive and negative values, may be non-symmetric and non-normalized. We let A = 12D − 12 (P(Ã) + P(Ã)T )D− 1 2 . Here P is a function with a non-negative range applied element-wise on its input – see supplementary material for details. The sub-expression 12 (P(Ã) + P(Ã)
T ) makes the resulting matrix P(Ã) symmetric. To understand the reason for taking the mean of P(Ã) and P(Ã)T , assume Ã is generated by GMLP. If vj is among the k most similar nodes to vi and vice versa, then the strength of the connection between vi and vj will remain the same. However, if, say, vj is among the k most similar nodes to vi but vi is not among the top k for vj , then taking the average of the similarities reduces the strength of the connection between vi and vj . Finally, once we have a symmetric adjacency with non-negative values, we normalize 1 2 (P(Ã) + P(Ã) T ) by computing its degree matrixD and multiplying it from left and right toD− 1 2 .

heading: 4.3 Classifier

text: The classifier is a function GNNC : Rn×f × Rn×n → Rn×|C| with parameters θGNNC . It takes the node featuresX and the generated adjacencyA 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 a twolayer GCN for which θGNNC = {W (1),W (2)} and define our classifier as GNNC(A,X;θGNNC) = AReLU(AXW (1))W (2) but other GNN variants can be used as well (recall thatA is normalized). The training loss LC for the classification task is computed by taking the softmax of the logits to produce a probability distribution for each node and then computing the cross-entropy loss.

heading: 4.4 Using only the first three components leads to supervision starvation

text:
One may create a model using only the three components described so far corresponding to the top part of Figure 1. 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 a scenario during training where two unlabeled nodes vi and vj are not directly connected to any labeled nodes according to the generated structure. Then, since a 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 vi and vj and this edge receives no supervision2. Figure 2 provides an example of such a scenario. Let us call the edges that do not affect the loss function LC (and consequently do not receive supervision) as 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 Erdős-Rényi graphs [10]; in the supplementary, we extend this result to the Barabási–Albert model [1] and scale-free networks [2]. An Erdős-Rényi graph with n nodes and m edges is a graph
chosen uniformly at random from the collection of all graphs which have n nodes and m edges.
Theorem 1 Let G(n,m) be an Erdős-Rényi graph with n nodes and m edges. Assume we have labels for q nodes selected uniformly at random. The probability of an edge being a starved edge with a two-layer GCN is equal to (1− qn )(1− q n−1 ) ∏2q i=1(1−
m−1 (n2)−i ).
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 Erdő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 1 is stated for Erdős-Rényi 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.

heading: 4.5 Self-supervision

text:
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 a prior structure based on the following hypothesis:
Hypothesis 1 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, so it is also suitable for predicting the labels. In the general (non-extreme) case, there may not be a single feature that is equivalent to the labels but a 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 is highly
2While 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.
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 a structure manually (e.g., by handcrafting a 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 a 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 self-supervised task encourages the model to learn a 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 based on denoising autoencoders [46]. Let GNNDAE : Rn×f × Rn×n → Rn×f be a GNN with parameters θGNNDAE that takes node features and a generated adjacency as input and provides updated node features with the same dimension as output. We train GNNDAE 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 to the elements of X to which we have added noise, andXidx represent the values at these indices. During training, we minimize:
LDAE = L(Xidx,GNNDAE(X̃,A;θGNNDAE)idx) (1)
whereA is the generated adjacency matrix and L is a loss function. For datasets where the features consist of binary vectors, idx consists of r percent of the indices of X whose values are 1 and rη percent of the indices whose values are 0, both selected uniformly at random in each epoch. Both r and η (corresponding to the negative ratio) are hyperparameters. In this case, we add noise by setting the 1s in the selected mask to 0s and L is the binary cross-entropy loss. For datasets where the input features are continuous numbers, idx consists of r percent of the indices of X selected uniformly at random in each epoch. We add noise by either replacing the values at idx with 0 or by adding independent Gaussian noises to each of the features. In this case, L is the mean-squared error loss.
Note that the self-supervised task in equation 1 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 of homophily. We refer the reader to the supplementary material for descriptions of self-training and AdaEdge.

heading: 4.6 SLAPS

text: Our final model is trained to minimize L = LC +λLDAE where LC is the classification loss, LDAE is the denoising autoencoder loss (see Equation 1), and λ is a hyperparameter controlling the relative importance of the two losses.

heading: 5 Experiments

text:
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 a 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 is label propagation (LP) [59], a well-known model for semi-supervised learning. Similar to [12], we also consider a baseline named kNN-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 [12], 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 IDGL model because it does not sacrifice accuracy for time complexity, and because anchor-based approximation is model-agnostic and could be combined with other models too. We
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 as well as SLAPS.
Datasets: We use three established benchmarks in the GNN literature namely Cora, Citeseer, and Pubmed [41] as 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, we only feed the node features to the models and not their original graph structure. Following [12, 6], we also experiment with several classification (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 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 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 to the supplementary material.

heading: 5.1 Comparative results

text:
The results of SLAPS and the baselines on our benchmarks are reported in Tables 1 and 2. We start by analyzing the results in Table 1 first. Starting with the baselines, we see that learning a 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, it was shown in the original paper that GRCN can revise a good initial adjacency matrix and provide a substantial boost in performance. However, as evidenced by the results, if the initial graph structure is somewhat poor, GRCN’s performance becomes on par with kNN-GCN. IDGL is the best performing baseline.
In addition to the aforementioned baselines, we also experimented with GCN, GAT, and Transformer (encoder only) architectures applied on fully connected graphs. GCN always learned to 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 in 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 MLP on datasets with many features and MLP outperforming on 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 graphs3. Adding self-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 a high degree of homophily (see Section 5.4).
In Table 2, we only compared SLAPS with the best performing baselines from Table 1 (kNN-GCN, 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 a 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, we 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. [21] 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 total. 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 experiment to measure the performance of SLAPS on these variants of the MNIST dataset. We compare against GLCN [21] as well as the baselines in the GLCN paper including manifold regularization [3], label propagation,
deep walk [37], graph convolutional networks (GCN), and graph attention networks (GAT).
The results are reported in Table 3. From the results, it can be viewed that SLAPS outperforms GLCN and all the other baselines on the 3 variants. Compared to GLCN, on the three variants SLAPS
3We note that IDGL-ANCH also scales to ogbn-arxiv.
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 provide 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 SLAPS2s that is trained in two stages. We first train the GNNDAE model by minimizing LDAE described in in Equation 1. Recall that LDAE depends on the parameters θG of the generator and the parameters θGNNDAE of the denoising autoencoder. After every t 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 only receives gradients from the self-supervised task in Equation 1.
Figure 3 shows the performance of SLAPS and SLAPS2s on Cora and compares them with kNNGCN. Although SLAPS2s 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, SLAPS2s 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.
The value of λ: Figure 4 shows the performance of SLAPS4 on Cora and Citeseer with different values of λ. When λ = 0, corresponding to removing self-supervision, the model performance 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 λ 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 λ = 0, SLAPS with the MLP generator becomes a variant of the model proposed in [8], but with a different similarity function.
Is self-supervision actually solving the supervision starvation problem? In Fig 4, we showed that self-supervision is key to the high performance of SLAPS. Here, we examine if this is 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 are 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 an effective solution to the supervision starvation problem.
The effect of the training set size: According to Theorem 1, a smaller q (corresponding to the training set size) results in more starved edges in each epoch. To explore the effect of self-supervision as a function of q, 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 self-supervision provides 16.7% and 22.0%
4The 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 empirical evidence for Theorem 1. Note that the results on Cora390 and Citeseer 370 datasets provide evidence that the self-supervised task is 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 structure is noisy [see 61, 9, 11]. Here, we verify whether selfsupervision is also helpful when a noisy structure is provided as input. Toward this goal, we 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; it is then further optimized by SLAPS. We perturb the graph structure by replacing ρ percent of the edges in the original structure (selected uniformly at random) with random edges. Figure 5 shows the performance of SLAPS with and without self-supervision (λ = 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-supervision consistently provides a boost in performance especially for higher values of ρ.

heading: 5.4 Analyses of the learned adjacency

text:
Noisy graphs: Following the experiment in Section 5.3, we compared the learned and original structures by measuring the number of random edges added during perturbation but removed by the model and the number of edges removed during the perturbation but recovered by the model. For Cora, SLAPS removed 76.2% and 70.4% of the noisy edges and recovered 58.3% and 44.5% of the removed edges for ρ = 25% and ρ = 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 on self-supervision being helpful for structure learning.
Homophily: As explained earlier, a properly learned graph for semi-supervised classification with GNNs exhibits high homophily. To verify the quality of the learned adjacency with respect to homophily, for every pair of nodes in the test set, we compute the odds of the two nodes sharing the same label as a function of the normalized weight of the edge connecting them. Figure 6 represents 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 are more likely to share the same label compared to nodes with lower or zero edge weights. Specifically, whenAij ≥ 0.1, vi and vj are almost 2.5 and 2.0 times more likely to share the same label on Cora and Citeseer respectively.

heading: 6 Conclusion

text: We proposed SLAPS: a model for learning the parameters of a graph neural network and a graph structure of the nodes connectivities simultaneously 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 well-motivated self-supervised task. We showed the effectiveness of our model through a comprehensive set of experiments and analyses.

heading: 7 Funding Transparency Statement

text: This work was fully funded by Borealis AI.

title: SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks