A Spectral Perspective on Deep Supervised Community Detection
Authors: Nathan Grinsztajn
Philippe Preux
Edouard Oyallon
Venue:  (2021)
Keywords: GCN
graph spectrum
stability
graph Laplacian

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

Under review as a conference paper at ICLR 2021
A SPECTRAL PERSPECTIVE ON DEEP SUPERVISED COMMUNITY DETECTION
Anonymous authors Paper under double-blind review
ABSTRACT
In this work, we study the behavior of standard models for community detection under spectral manipulations. Through various ablation experiments, we evalu- ate 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 classi- fication is contained in the low-frequency domain, and thus contrary to Euclidean graph (c.g., images), figh-frequencies are less crucial to community detection. particular, it is possible to obtain accuracies classifiers that rely only on a few low frequencies: this is surprising because con- trary GCNs, cascade of filtering along the graph structure is involved and it indicates that the important spectral components for the supervised community detection task essentially in the low-frequency domain.
state-of state-of-the-ar oh-the-rrt level with simple
INTRODUCTION
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 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.
suggested in Li et al. (2018) that GCNs are eager over-smooth their rep- resentation, which indicates they average too much neighborhood nodes and dilute classification information. The smoothing generally interpreted as a low-pass filtering through the graph Lapla- cian, 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 minor impact on the clas- sification 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 popular field whose objective to manipulate signals spectrum whose topology is given by graph. Typically, this graph has a non- non-Euclidean structure. however many central theoretical results (Hammond et al. 2001)) are based on an analogy with Euclidean, eigenvalue regular grids. For instance, spectral component or frequency has to be understood of the Laplacian, yet it thus suffers from intrinsic issues such as isotropy (Oyallon] (020).. 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 essentially located in the low-frequency domain. This type of ideas 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 generative models based on the graph spectrum. The main principle is to consider the eigenvectors corresponding to the smallest non- zero 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

---

Under review as a conference paper at ICLR 2021
to establish clear link with this approach: we show that the informative graph features are located in a lowffrequency 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 de- tection 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 follows: (a) First we show that most of the necessary information exploited by a GCN for 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 MI.P 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 ob- tained 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. proposes several experiments to study the impact of higu-feeqeencies 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.
2 RELATED WORK
GCNs and Spectral GCNs Introduced in Kipf & Welling (2016), GCNs allow to deal with large graph structure in supervupe 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 linear GCN (Wu et al., 2019), Graph Attention Networks (Veličković 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 spectral methods, that employ filters which are designed from the spectrum of 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 anisotropic diffusion (Klicpera 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. (008)) 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 let al. (2020) proposes introduce regularizations which address the loss of information issues. Cai & WWang (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. HHang et al. (2020); Rong et al. (2019b) introduce data augmentations, whose aim is to alleviate over-smoothing deep networks: we study GCNs without this ad-hoe 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 GCN,,Mehta et al. (019 proposes to learn an unsupervised auto-encoder in the framework of a Stochastic Block Model. Oono & Suzuki] (2019) introduces the Erdös Renyi model 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 a potential direction for future works.
Node embedding A MLP approach can be understood instance, Aubry et al. (20IT) applies a spectral embedding combined with a diffusion process for shape analysis, which allows posnt-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 measure of node centrality.
embedding at the node level. For
Graph Scattering Networks (GSN) This class model explicitly employs band-pass based on the spectrum of graph Laplacian and it is thus necessary review it. Gao et al. (2019) Gama et al.
2

---

Under review as a conference paper at ICLR 2021
2018 2019) are class of neural networks built upon analogy with Scattering Transform (Mal- lat 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 lies heavily on each eigenvector of the Laplacian and the dyadic space is typically constructed from diffusion process dyadie intervals. Interferometric Graph Transform 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, was noted in Oyal- lon (2020) that stability is not 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 trained GCN to spectral perturbations.
FRAMEWORK
3.1 METHOD
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) introduced in (Kipf & Welling 2016), which correspond to GNNs that propagate features graph input (0) X through a cascade of layers, via the iteration:
H(+1) (AHOWO)
where À [ D-11112A--22 o a point-wise non-linearity and W parametrized affine operator. Note that if Ā IN. then Eq. [ is simply an MLP, which makes its implementation simple. The 1 factor is a normalization factor to obtain ||A]] = 1. In the semi-supervised setting, final layer fX, A) & (()) is fed to a supervised loss é (here softmax) and (W .... W are trained in an end-to-end manner to adjust the label of each node. We note that for undirected graph, Á is 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:
2
KNN + A)X]; = X1 + Σ Ar
We remark that multiple choices of averaging operators are possible: as brietly discussed in Ap- pendix A.33 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 spec- tral approximations of Á. We consider the decreasing set of cigenvalues A = {Aa of Å, such that \ 2 A and we denote by Uı the k-th eigenvector corresponding to À A. We remind that A C [0. 1] and that Å Since the adjacency matrix normalized, one basis of oo 's eigenspace constituted by the constant vectors of 1 supported on each connected component, We then write:
can be interpreted as the lowest frequency of the graph Laplacian.
À A
Σ
ARUKUT
(3)
Ao Sk
such that À = A We are interested to study the degradation accuracy if we replace with A AR.M for some 0 le < N. The next section explains that under standard but over- simplifying assumptions, an approximation of the type Ao.a) is relevant for community detection tasks.
3

---

Under review as a conference paper at ICLR 2021
3.2 UNDERSTANDING LOW RANK APPROXIMATIONS FOR GCNS
We now justify our approach under the standard setting of the Stochastic Block Model (Abbe) 2017 7) and we will simply remind the reader of several elementary results. This model corresponds to generative model that describes the interaction between communities [Ci,.., Cr Assuming that two nodes i. belong to the communities Cr., Cry. an edge is sampled with a probability Pra.ry (Rohe et al., 2011). For the sake of simplicity, us assume that r = 2, that the probability of an edge between two nodes i,j is if those nodes belong to the same community and q < otherwise, and that both communities correspond to |C] nodes. In this case, the unnormalized expected adjacency matrix is given by:
P
p
q
p
g
...
(4)
q
q
p
P
:
P
where we grouped in matrix block the nodes from the same community. We note that the two dominant eigenvectors are given by:
|C| times
|C] times
"1
and 022
(5)
C
times
|C| times
Observe that the second eigenvector We 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-g < and ideally this spectral gap should be as large as possible for p+4
identifying the two communities. 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, low-rank approximation A captures most of the available information about the two communities. We illustrate this idea on Fig. [ While these assumptions might not hold in practice, it justifies why low-rank approximations of Laplacian are relevant in the setting of com- munity detection and it explains why high-frequencies might not be as important as low-free owwfrequencies for supervised community detection task. The next section validates empirically this approach the context of GCNs and simpler architectures.
U4
Uso
U:sa
(a)
(b)
Figure 1: Under Stochastic Block Model with 4 communities (a), represent the first Eigen- vectors (b, left) and the last Eigenvectors (b, right). On the left figure, the colors stand for the communities. On the right, they stand for the values of the considered eigenvectors (the brighter the higher), A low rank approximation maintains the information related to the different communities.

---

Under review as a conference paper at ICLR 2021
Cora
Citeseer
Pubmed
1.0
0.8
Eigen-value Ax
0.6
0.4
0.2
0.0
1000
2000
1000 2000 3000
5000 10000 15000 20000
Frequency index
Frequency index k
Frequency index k
Figure 2: Spectrum A of Å. Note that the eigenvalues decreasing, displayed with multiplicity. Observe that the decay of the spectrum fast.
4 NUMERICAL EXPERIMENTS
Matching the previous work practice, focus the three classical benchmark dataset for com- munity 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 transductive, meaning all node features are accessible during training, We apply the full-supervised training fashion used in Huang al. (2016), Chen al. (2018), and Rong et al. (2019)) on all datasets our experiments. Fig. 2 plots the 3 spectra A in decreasing order for each of those datasets. The three datasets exhibit significant spectral gap, which is aligned with the model of Sec. [bb Note that Pubmed has one con- nected component, and that the decay of its spectrum is fast compared to Cora or Citeseer, which indicates low-dimensional structure (Belkin & Niyogi 2002). The statistics of each dataset are listed in the supplemental materials.
We choose to the ReLU non-linearity (Krizhevsky et al. 2012). Unless specified otherwise, the weights of our models (either GCN MLP) are optimized via Adam, with 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 hidden layers of size 128. In all experiments, our hypee-parameters on validation set, using an early stopping at epoch 400. Unless specified otherwise, each plot is obtained by average over at least different seeds.
cross validate
4.1
Low RANK APPROXIMATION
GCN ablation Here, we consider the two projections Á and ÂIN-K.N]. where & is adjusted to retain only a portion of spectrum. Via the GSP lens, those projections can be interpreted respectively as high-pass and low-pass filters. As explained in Sec. [b] those projections will allow to study which frequency band is important for the community detection task. Fig. B and Fig. report the respective numerical performance when considering the models f(X, A(N) and f(X, Ap,))) 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 GCN uses mainly the low frequency domain. For Pubmed, using almost all the nigh-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
5

---

Under review as a conference paper at ICLR 2021
Cora
Citeseer
Pubmed
0.85
0.88
0.80
0.7
0.87
0.75
0.6
0.86
Test accuracy
0.70
hidden layers
0.85
0.65
0.60
0.4
0.83
0.55
0.3
0.82
0.81
0.50
0.2
50
100
50
100
50 (%6 retained
100
(%) of retained LF
(%6 retained
Figure 3: Test accuracies reached by a GCN as a function of the Low-Frequencies (LF) band [ Aol retained by Ap. for various depths (100% corresponds to the full spectrum, including low frequen- cies). This figure indicates that informative component for the community detection task are located in the low frequency domain.
Cora
Citeseer
Pubmed
0.8
0.8
0.7
Test accuracy
0.6
0.7
0.5
0.5
0.6
0.4
0.4
0.3
0.5
0.2
0.2
0.4
25
50
75
100
40
60
80
100
50
100
(%) of retained
& (%6 retained HF
(%) of retained
Figure 4: Test accuracies reached by a GCN as a function the Sigh-Frequencies (HF) band [Aw, AN-a] retained by ÂIN-k.N]- for a GCN of depth (100% corresponds to the full spectrum). This figure indicates that high-frequencies are less informative for community detection task.
they are still difficult to train, as shown on Cora. This instability to spectral perturbations is further studied in See 4.2 Fig. 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 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 X₁ [X, .... u of the first & eigenvectors. For fair evaluation, exactly the same hyper-parameters as for the experiments above. Fig. reppors the accuracy of our ML.P trained X₁ function of k. We that using fraction < 20% of the eigenvectors
used

---

Under review as a conference paper at ICLR 2021
Cora
Citeseer
Pubmed
0.72
0.890
0.80
0.70
0.885
0.75
0.68
Test accuracy
0.880
0.70
0.66
0.875
0.65
0.64
0.870
0.60
0.55
0.860
0.58
25
50
75
10
10
(%) of retained LF
(%) of retained LF
(%) of retained LF
R
Figure 5: Accuracy of MLPs trained on Xx, according to the Low- Low-Frequency band [Ax, Ao] retained. We note that selecting narrow low-frequency band can lead to competitive accuracies.
allows to recover the performance of GCN trained end-to-end, More surprisingly, we note that as k increases, the accuracy drops, which indicates that high-frequencies behave like residual noise that is not well filtered by a MLP, and rather overfitted. This is particularly true for Pubmed, which has fast spectral decay and for which the low frequencies seem to be the most informative. This experiment emphasizes that low rank approximation of the Laplacian of the graph a community detection task can be beneficial MLP classifier.
Table 1: Comparison of various models on Cora, Citeseer and Pubmed.
Method
Data augmentation
Cora
Citeseer
Pubmed
GCN (Rong et al. 2019b)
No
86.6
79.3
90.2
Fastgen (Chen et al. 2018
No
86.5
88.8
MLP on
No
74.0
73.3
89.1
MLP on X2 (ours)
No. 86.6
77.3
91.4
DropEdge (Rong et al. 2019b)
Yes
88.2
80.5
91.7
(Huang al. 2018)
Yes
87.4
79.7
90.6
Boosting MLP performances We perform a hyper-parameter grid search on each dataset to in- vestigate MLP strengths further, and report the case giving the best accuracy on each validation set. We summarize our findings in Tab. 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 on X already outperforms the approach of Chen et (2018) without relying on 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 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 proce- dures, at the price of extended computation time. We conclude that GCNs do not compute more complex invariants than a MI.P fed with low-frequencies, the context of community detection.
Note on the computational overhead The MLPs introduced above are of interest the corre- sponding graph topology is fixed, with large graph, and high connectivity. Indeed, using MI.P

---

Under review as a conference paper at ICLR 2021
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 (k: We note that fast k- c-truncated e-approximate SVD algrotithms for sparse matrix exist (Allen- &
Li 2016): if p the number of non non-zero coefficients of A, the complexity can be about O 52
4.2
STABILITY TO HIGH FREQUENCIES
Cora
Citeseer
Pubmed
0.010
Amplitude !i
0.004
0.6
0.4
0.005
0.002
0.2
0.000
0.000
0.0
0.10
0.075
Amplitude [x
0.06
0.050
0.04
0.05
0.025
0.02
0.000
0.00
0.00
0
100
50
100
100
Frequency index (%)
Frequency index & (%)
Frequency index (%)
Øt of the same model taken respectively Figure 6: The (top) and (bottom) figures corresponds to Ag at the initialization and the end of training. Note that high frequencies are more stable than low frequencies for the three datasets.
We now study the stability of GCN w.r.t. spectrum perturbations. In the case of image processing, standard that low-frequencies almost do not affect the classification performances and that perturbations of high-frequencies lead to instabilities. We would like validate that this principle does not hold here, and to do so, we consider VAC, which is the gradient w.r.t. every singular value Ag. Small amplitudes of ixx indicate more stable coefficients. Fig. plots the amplitude of the gradient w.r.t. 2 at the initialization
GCN and after training. First, we note that GCN is more sensitive to spectral perturbations after training, which is logical because the GCN adapts its weights the specific structure of a given graph. After training, we remark that the high- frequency perturbations have 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.
4.3 SMOOTHNESS AND SELF-LOOPS
As proposed by Kipf& & Welling 2016), we now study how the self-loop À affects our GCN training procedure and in particular, we study it through the lens of spectral analysis. We consider:
A A 1
(p/N + A),
(6)
where 7 E [-]] +o0 can be understood as smoothness parameter. Note that for 7j < 0. the spectrum of A. not necessarily positive and we renormalize A, such that ||A, 1, Vn. Here, the averaging while allowing to balance a trade-off between a
A, enhances the high-frequencicr smoothing and an identity operator, which can be here observed as
Ån 7-000
and
Åg = A.
8

---

Under review as a conference paper at ICLR 2021
Cora
Citeseer
Pubmed
1.0
0.95
0.9
0.9
0.90
0.8
0.85
Test accuracy
0.7
0.7
0.80
0.6
0.6
0.75
0.5
hidden layers
0.70
0.5
2
0.4
0.65
0.4
0.3
0.60
0.3
0.2
2
Figure 7: Test (dashed line) and train (plain line) accuracy according to for various depth of GCN. We observed marginal improvements when varying r).
As observed in Li et al. 2018), oversmoothing phenomena occur because propagates in- put through a cascade of n smoothing operators. Here, we note that a Taylor expansion reveals asymptotically this trade-off for large Ty:
n(1 - AR) u + + pp
AN
Ug u
Σ
unu
(8)
17
Thus depending on the nature of Ug. the degree of averaging can be adjusted. The details of the cal- culations are given in App. Fig. iindicatss that it is possible to adjust the degree of smoothing train deeper networks (in the degenerate setting v < 0) and to slightly boost the accuracy of GCN. We report both the training and testing accuracies to emphasize the impact of the training dynamics of GCN. Citeseer exhibits a significant generalization gap for large values of 1 and depth of 4: frequeceqsssss deteriorate the generalization properties. We note that varying allows to improve the training accuracy deeper GCNs, though larger emphasizes which leads to significant drop in accuracy. We finally observe that selecting 17 via the best accu- racy on a validation set allows minor boosts in performances: of the order of 1.4% (1) = 1) and 1.5% (1) 0.5) for GCN of depth 2 respectively Citeseer and Pubmed.
CONCLUSION
In this work, have studied the classification performance of a GCN if applying low-pass and high-pass filters, in the context community detection. Our finding 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 cigenvectors 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 counter- intuitive 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 standard GSP tools such graph wavelets might be simplified to low-pass filters, in the context of community detection, as we observed that the high- figh-frequency does not bring a significant amount of information, and can even be interpreted our methodology can help to identify if an accuracy improvement of a given algorithm is due to a better processing of high frequencies.
graph Laplacian. also shows that
residual noise, in this particular setting, Note also that

---

Under review as a conference paper at ICLR 2021
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, (11))6444665111, 2017.
Zeyuan Allen-Zhu and Yuanzhi Li. Lazysvd: Even faster svd decomposition yet without agonizing pain. In Advances in Neural Information Processing Systems, pp. 974-982, 2016.
Mathieu Aubry, Ulrich Schlickewei, and Daniel Cremers. The wave kemnll signature: A quantum mechanical approach to shape analysis. In 2011 IEEE international conference on computer vision workshops (ICCV workshops), pp. 1626-1633, IEEE, 2011.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-595599 591, 2002.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1312v:11126620:. 2013.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint N0KV:20006.1331. 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. CoRR, 10s/1801.10247, 2018. URL
1801. 10.1102440 10247
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Shay Deutsch and Stefano Soatto. Spectral embedding of graph networks, 2020.
Vishwaraj Doshi and Do Young Eun. Fiedler vector approximation via interacting random walks. Proceedings of the ACM Measurement and Analysis of Computing Systems, 4(1):1-28, 2020.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms graphs.
arXiv preprint arXiv: arXiv:1806.0880 1806.0889, 2018
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. arXiv preprint arXiv: 1905.44955. 2019.
Feng Gao, Guy Wolf, and Matthew Hirn Geometric scattering for graph data analysis. Interna- tional Conference on Machine Learning pp. 2122-2131, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):12--100, 2011.
Gao Huang, Zhuang Liu, and Kilian Q Weinberger. Densely connected convolutional networks. CoRR, abs/1608..00 069.06699, 2016.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558 4567, 2018.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. smoothing for general graph convolutional networks, 2020.
Tackling over-
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolu- tional networks on large random graphs, 2020.
10

---

Under review as a conference paper at ICLR 2021
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint
2016.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems, pp. 1335-133666 2019.
Alex Krizhevsky, Nya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. arXiv preprint wrXiv:1801.06600 2018.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. arXiv preprint arXiv:1802.07510. 2018.
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65(10):1331-1398, 2012.
Nikhil Mehta, Lawrence Carin, and Piyush Rai. Stochastic blockmodels meet graph neural net- works. arXiv preprint urXiv:1905.055 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprini arXiv: 10947, 2019.
Edouard Oyallon. Interferometric graph transform: deep unsupervised graph representation. In Proceedings of Machine Learning and Systems 2020, pp. 4124-4134. 2020.
Karl Rohe, Sourav Chatterjee, Bin Yu, et al. Spectral clustering and the high- high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4):1878-1915
2011. 2011.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. The truly deep graph convolutional networks for node classification. CoRR, abs/1907.10903 2019a. URL atttt://aaxxx org/
abs/ 10903
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019b.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. AI Magazine, 29(3):93, Sep. 2008, doi: 10. 1609/ fimag.v29i3.2155. URL https: www. aaai orq wtwpg//jjs/inddee pttp.xxpppppammaaaziiaaaa
article/view/211 2117
Ke Sun, Piotr Koniusz, and Zhen Wang. Fisher-bures adversary graph convolutional networks. In Uncertainty in Artificial Intelligence, pp. 465 475. PMLR, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining, pp. 1539-1548, 2019.
Martin J Wainwright. Hiigh-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Felix Wu, Amauri H Souza Jr. Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
Chaoqi Yang. Ruijic Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting" over-smoothing" in deep gens. arXiv preprint arXiv:2003. 13663, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv: /2223, 2019.
11

---

Under review as a conference paper at ICLR 2021
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1399 1499, 2019.
12

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1
DATASET STATISTICS
Table 2: Dataset Statistics
Datasets
Nodes
Edges
Classes
Features
TraingWValidatioonTesstgg split
Cora
2,708
5,429
7
1,433
1,208/500/1,000
Citeseer
3,327
4,732
6
3,703
1,812/500/1,00
Pubmed
19,717
44,338
3
500
18,217/500/1,000
A.2
HYPER- PARAMETER DESCRIPTION
Table 3: Hyper-parameter Description
Hyper-parameter
Description
Ir hidden layers
learning rate
the number of hidden layers 1.2 regulation weight dropout rate
weight-decay dropout
frequencies
the number of low frequencies to add whether to normalize the new MLP features in line (per nodes) or column (per features)
eigenvector features normalization
A.3 ON THE CHOICE OF THE NORMALIZATION
GCNs defined in Kipf & Welling 2016) don't exactly used the first order Laplacian approximation, but introduce normalization trick A (D + - IN) IN)_ Using the stan- dard hyper-parameters defined in Section 4 we averaged our results on 3 seeds and observed no significant difference across datasets, as shown in Fig.
A.4 TAYLOR EXPANSION
We recall that Å., T+7 (T/N + A). Thus eigenvector un of À corresponding to the eigenvalue A is an eigenvector of A,, corresponding to the eigenvalue n+ Therefore, we have: 1+1
Ån
7 +
uu Uk
1 +
A
And thus,
1 Av
A" Σ
2
1 1+
A
17 + do
Σ
Σ
1 1++1 17
A+=1
n11 )x)
A
u
T
ux
u + 00
A
Axcl
13

---

Under review as a conference paper at ICLR 2021
Cora
Citeseer
test test accuracy
0.6
0.6
0.4
0.4
Lest
0.2
0.2
normalization
GCN
number of hidden layers
number of hidden layers
Pubmed
0.8
test accuracy
0.6
0.4
normalization trick
number hidden
Figure 8: Comparison between the standard Laplacian first order normalization and the GCN malization trick
14


Reviews:
[{"review_id": "Xw9fGHKJ780", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe 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:\n1. The high-frequency eigenvalues are less informative and perturbing them does not have much effect on GCN’s output. This supports the over-smoothing phenomena empirically observed by Li et al. 2018\n2. A simple MLP with few initial eigenvectors as additional features outperforms several existing GCN models. Moreover, including higher eigenvectors degrades performance as it adds noise which could not be well filtered by MLP. \n\n\nQuestions:\n1. The reason why GCN model with 8 hidden layers gives poor performance is not properly justified. It would be great if authors could provide more intuition behind it. Can over-parameterization can be a factor for such poor generalization?\n2. Can the authors provide some explanation behind the sudden jerks observed in Figures 2 and 4? \n\nTypos:\n1. In the related work section (para 2 and 3) change ‘overs-moothing’ to ‘over-smoothing’ and ‘litterature’ to ‘literature’. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "WzlafAtE9w9", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Brief summary\n\nThis paper studies the contribution of low-frequency eigenvalues and high-frequency eigenvalues of graph Laplacian empirically. The authors show that high-frequency eigenvalues are less informative. In their work, they propose an MLP model that can achieve equal or better performance than GCN by using eigenvectors as part of input features.\n\nPros:\n\n1. MLP fed with node features and spectral coordinates of a given node is competitive with a GCN and more efficient than GCN.\n2. The empirical study of high-frequency and low-frequency eigenvalues provides great insights on whether we should build high-pass filters for graph signals.\n3. The authors show that high-pass filters tuned properly can lead to some minor performance boosts on GCNs.\n\nCons:\n\n1. Although it can be done in the pre-processing step, the computation cost of eigenvalue decomposition is heavy. Besides, as the proposed method assumes the corresponding graph topology is fixed, it can not be used in an inductive setting.\n2. The idea of feeding node features and spectral coordinates to MLP is not novel. It is a kind of feature engineering.\n3. The impact of high-frequency eigenvalues on graph-level tasks is not studied. Graph-level tasks are equally important as node-level tasks for a powerful GCN.\n4. The authors said larger eta emphasizes higher frequencies, and when eta=2 or eta=3 it marginally boosts the performance of GCN on CiteSeer and Pubmed. Larger eta not only emphasizes higher frequencies but also lower frequencies because when eta goes to infinity, it leads to an all-pass filter which includes both high frequencies and low frequencies.\nOriginality\n\nThe paper provides new insights about low-pass filters and high-pass filters on graphs. Since the paper essentially proposed to use new features for an mlp model. The novelty of this paper is limited.\n\nMinor comments:\n\n1. About Equation 7 and Equation 8, the illustration is not clear to me. What is the range of eta? going from 0 to infinity? or going from negative infinity to 1? It seems quite ambiguous. In addition, if the range of eta varies from 0 to infinity, I think Equation 8 balances a trade-off between a smoothing low-pass filter and an all-pass filter. It is better to plot the spectrum of Equation 7 to verify you argument.\n2. How is Equation 9 derived?", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mj2WKywdv7p", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI think the paper has a pretty good start point: understanding how the spectrum of adjacency matrix will affect the behavior of GCN. But I think the manuscript is loosely written and I can hardly follow it. I do have a lot of confusion about this paper and hope that the authors can clarify them.\n\n- In general, there are too many typos and grammar errors which make the manuscript hard to read.\n- Sec 1: in the 1st paragraph, what does 'graph principles' mean? I cannot recall a clear definition of this term. I think the authors could clarify it before using it formally.\n- Other contributions in Sec 1:\n  * (a), I think the empirical results in the paper show that retaining a small portion of low-frequencies is enough for achieving good classification accuracy. From the results and your analysis, I can hardly find a clear conclusion that links to it (i.e., the very first eigenvector is most informative); \n  * (b) and (e) are somehow connected since both are mentioning about GCN's behavior over manipulating high frequencies; \n  * (c), I actually did not quite understand where the clear link is. I would suggest the authors clarify it more clearly in the manuscript;\n  * Just a minor thing, what exactly does 'informative' mean, greatest change in loss function or greatest change in test accuracy? Better make it clear.\n- Sec 3:\n  * Notations are quite messy. A matrix can be denoted using italic lowercase letter, italic uppercase letter, calligraphic uppercase letter, bold italic uppercase letter. It is very confusing when reading the paper, especially when some scalars are also denoted using the same convention.\n  * I did not find any framework in this section, which contradicts the last paragraph in Sec 1.\n- Sec 4:\n  * Pubmed should have only 1 connected components. In the following sentence, what does 'not necessarily fully supported on ...' mean? \n  * In Sec 4.1, is there any intuition or theoretical justification for the projection operation used in band-pass filter?\n  * In Figure 2, it seems that Cora has a very sharp performance drop (~0.82 -> ~0.5) when x-axis is nonzero, is there any insightful explanation on that?\n  * Does the content of 'MLP ablation' correspond to your proposed method? This is the only place I can find clues about your method. I understand that the goal of this paper is show a MLP can perform better or comparable with GCN that perform message passing. But I believe you still need topology information to get those eigenvectors. Is there any insight or theoretical concern about simple concatenation instead of linear transformations like $e^T e x$?", "extra_scores": {}, "extra_text": {}}, {"review_id": "J1wQWeUGwf", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n 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.\n\n--------------------\nStrengths:\n1. Paper presents a study of GCNs from spectral perspective.\n2. Paper makes few interesting observations about the influence of low and high frequency components of the Graph Laplacian on GCN performance.\n3. MLP with spectral information is investigated for graph tasks. \n--------------------\nWeakness:\n1. Novelty in the study is limited.\n2. Experimental results are inadequate.\n3. Presentation is poor.\n--------------------\nDetails: \nI have the following comments about the paper:\n\n1.  Novelty is limited: The novelty of this study is unclear to me. The fact that the GCN model of (Kipf and Welling, 2016) is based on low pass filtering is well-known. Note that, their model is simply a degree-one approximation of the low pass Chebyshev filter approach of (Defferrard et al., 2016). The original objective of spectral GCNs have been low pass (localized) filtering as proposed by (Bruna et al., 2013). The study in (Li et al., 2018) also further establishes these spectral results. Hence, the novelty of the paper is limited. \n\n2. The experiment results are inadequate. The paper considers just 3 datasets (all three have similar spectrum), and it is hard to make conclusions with the few results presented. The results in Figure 2, do not actually support the conclusions. The effects of retaining more LF components is not clear, especially for deeper networks.\nResults on more datasets with different spectral distributions would make the study more conclusive.\n\n3. The paper is poorly written, and needs to be checked for language consistency throughout. I recommend having the paper proof-read by a native speaker.\nNotation is inconsistent. Both upper and lower case letters are used for matrices.\n\n4. Cost: Note that GCN is a very simple model that is computationally inexpensive. It requires just few matvecs (# of features) at each layer to implement.\nThe proposed MLP requires eigenvectors, i..e, requires a complete Eigen-decomposition of the Laplacian, that has a cubic K^3 cost. Computational complexity of the compared methods should be discussed.\n\nMinor Comment:\ni. Page 2, \"one of the first paper\" --> one of the first papers\n\"litterature\", \"overs-moothing\" and many more incorrect spellings throughout", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Though the observation regarding the importance of the low end of the spectrum is interesting in its own right, the paper would be better substantiated by experiments on more datasets and a more thorough characterization of the paper novelty/contrast to state of the art.
Decision: Reject