p p

# NEURALLY BOOSTED SUPERVISED SPECTRAL CLUSTERING

**Anonymous authors**
**Paper under double-blind review**

ABSTRACT

Network embedding methods compute geometric representations of graphs that render
various prediction problems amenable to machine learning techniques. Spectral network
embeddings are based on eigenvectors of a normalized graph Laplacian. When coupled
with standard classifiers, spectral embeddings yield good baseline performance in node
classification tasks, but they are widely considered to have been amply surpassed by
newer embedding methods and Graph Convolutional Networks. In this work, we provide a theory-informed implementation of supervised spectral clustering and maximize its
performance with the use of a carefully designed RADIAL classifier that leverages fundamental geometric properties of spectral embeddings. RADIAL raises the performance
of supervised spectrally clustering to previously unobserved levels and renders it directly
competitive to newer methods in the context of transductive node classification on social
networks. We also observe that that features learned in an inner layer of RADIAL can
significantly enhance the performance of standard Graph Convolutional Networks.

1 INTRODUCTION

Spectral clustering is a classical unsupervised algorithm for clustering in graphs. It gained prominence in
data mining and machine learning approximately two decades ago (Shi & Malik, 2000; Ng et al., 2001)
and it has since found many applications in multiple domains. While originally conceived as an unsupervised method, spectral clustering has also been employed in transductive learning, and in particular in
semi-supervised node classification that is the focus of this work.

**Background. The work of Tang & Liu (2011) was likely what initiated a long line of work on multi-label**
classification with experimental focus on social network benchmarks. They described a general framework
for node classification consisting of two steps: (i) computing a network embedding, (ii) using the embedding as input to a standard classifier. They instantiated step (i) with a spectral embedding, giving thus rise to
what can be viewed as a supervised spectral clustering algorithm. Albeit simple, the algorithm proved to be
superior relative to the then-available baselines. The thread continued with the very prominent DEEPWALK
embedding algorithm (Perozzi et al., 2014), that claimed superiority over spectral clustering which however
remained competitive. The success of DEEPWALK unleashed a wave of research works on network embeddings, including (Grover & Leskovec, 2016; Tang et al., 2015; Tsitsulin et al., 2018; Qiu et al., 2018a), and
a race for higher classification accuracy [1]. More recently, network embedding methods were succeeded by
graph neural networks (GNNs) (e.g. see (Kipf & Welling, 2017; Velickovic et al., 2018)) that have dominated the competition. Since the publication of DEEPWALK, supervised spectral clustering was at-best
considered a baseline, or entirely vanished from consideration. However it has recently made a comeback
with the work of Huang et al. (Huang et al., 2021) that described a simple ‘correction and smooth’ (C&S)
procedure that can enhance the output of other models. Some of the state-of-the-art results in in the Open

[1A very detailed list can be found in https://github.com/chihming/awesome-network-embedding](https://github.com/chihming/awesome-network-embedding)


-----

p p

Graph Benchmark leaderboard (Hu et al., 2021) are now based on variants of supervised spectral clustering
in combination with the C&S process. These easily surpass previous embedding methods and even exceed
methods based on GNNs using only a small fraction of their number of trainable parameters.

**A Critical Look. This work originates from the observation that previous literature has treated spectral clus-**
tering somewhat casually, and largely ignoring recent major advances in its theoretical understanding. As
discussed above, supervised spectral clustering consists of two steps: (i) Computing a spectral embedding,
and (ii) Giving the embedding as input to a multi-label classifier. In the literature, the term ‘spectral clustering’ is used for multiple different algorithms that implement steps (i) and (ii) in various and sometimes not
adequately described ways.

For example, for step (i), (Tang & Liu, 2011) and (Perozzi et al., 2014) use eigenvectors of the normalized
graph Laplacian as proposed in (Ng et al., 2001) but appear to omit a normalization step from that algorithm,
(Huang et al., 2021) also use the normalized graph Laplacian but with an additional ‘rotation’ transformation,
while other works use the random walk matrix (i.e. the non-symmetric normalization of the Laplacian) which
in fact is a more accurate relaxation of the underlying NCut problem (Shi & Malik, 2000). Classifiers used
for step (ii) include an One-vs-All SVM-based model (Tang & Liu, 2011), an One-vs-Rest logistic regression
model (Perozzi et al., 2014), a softmax regression model, and a three-layered neural network (Huang et al.,
2021). Adding to the confusion, the computation of eigenvectors has been viewed both as computationally
expensive to the point of preventing its application on larger networks (Perozzi et al., 2014), or as able to
scale up to very large networks via standard iterative eigensolvers whose fast convergence cannot however
be guaranteed (Huang et al., 2021).

**Goal. These considerations provide the motivation of our work. Concretely, we seek to provide a theory-**
informed implementation of supervised spectral clustering, maximize its performance with the use of a carefully designed neural model and study its practical performance in the context of multi-label classification
on social networks.

**Contributions. Our RADIAL classifier can be conceptually viewed as a ‘neural’ implementation of the**
seminal theoretical work of Lee et al. (2014b) on multi-way Cheeger inequalities for spectral clustering.
These theoretical guarantees are based on a variant of spectral clustering that is not well-known or widely
used, yet it can be theoretically analyzed without assumptions about the underlying graphs. The analysis of
Lee et al. applies to unsupervised clustering. Thus a key contribution of our work is to transfer the geometric
intuition developed in (Lee et al., 2014b) to the supervised setting with the design of custom-made neural
classifiers that respect and exploit the geometric facts.

Indeed, RADIAL raises the performance of supervised spectral clustering on transductive node classification
to previously unobserved levels, sometimes more than 15% higher than vanilla classifiers. As our ablation
study confirms, this performance is achieved by introducing certain modifications and enhancements to the
basic unsupervised algorithm of (Lee et al., 2014b), and other training tricks.

Within our experimental context, when only graphic data are taken as input, we show that when training
nodes are scarce, supervised spectral clustering is directly competitive to prominent alternative methods
that were thought to be vastly superior. On the other hand, we observe that non-parametric diffusion-based
methods become progressively more effective when training points are abundant, thus offering an empirical
explanation of the success of the C&S algorithm (Huang et al., 2021). Moreover, based on intuition derived
in section 3.4, we develop a method of enhancing the performance of standard GCNs (Kipf & Welling, 2017).
More specifically, in section 4, we show that when node features are available, the performance of GCNs
can be significantly enhanced by feeding as additional input features learned by our RADIAL classifier.


-----

p p

2 SPECTRAL CLUSTERING WITH SUPERVISION: THE ALGORITHM

2.1 SPECTRAL EMBEDDING AND GEOMETRIC INTUITION

We begin with a review of the spectral embedding algorithm. Along it we give concrete details on how
it can be implemented to run in near-linear time with strong convergence guarantees. In Section 2.1.3 we
discuss the geometric intuition that underlies the theoretical analysis in (Lee et al., 2014b). We note that the
material in this subsection is not new. We present it for completeness and in particular in order to discuss
the geometric intuition which plays a key role in the construction of our classifiers.

2.1.1 DEFINITIONS AND TERMINOLOGY

Let G = (V, E, w) be a weighted undirected graph.
**Definition 1 (Cut and Volume). If S ⊂** _V, we define the cut of S to be_


_cut(S) =_

_We also define the volume of S to be_
_vol(S) =_


_wi,j_
_i∈XS,j̸∈S_


_vol(S) =_ _cut(v)._

_sX∈S_

_We will often use the term degree for the cut of a single node._
**Definition 2 (Conductance). The conductance of a cluster S ⊂** _V is defined by_

_cap(S, V_ _S)_
_φ(S) =_ _−_

min(vol(S), vol(V − _S))_


We denote by D the diagonal matrix of the degrees, by d the vector of the node degrees, and by L = D − _A_
the graph Laplacian, where A is the adjacency matrix of the graph.

2.1.2 SPECTRAL EMBEDDING AND THE UNSUPERVISED ALGORITHM

The combinatorial idea that underlies spectral clustering is that good clusters should have a relatively small
volume to their exterior, or more specifically a low conductance. More concretely, the goal is to find k
disjoint clusters {S1, S2, ...Sk} such that maxi φ(Si) is as small as possible. In this paper we will be looking
for k clusters that also provide a partitioning of the vertex set, i.e. we have _i_ _[S][i][ =][ V][ . The partitioning]_

problem is less well-understood (Louis et al.), but its simpler non-partitioning variant has been studied
extensively from a theoretical perspective (Lee et al., 2014b), and approximation guarantees are known

[S]

for it. The spectral clustering algorithm is broadly understood as a relaxation of the discrete clustering
problem (e.g. see (Cucuringu et al., 2016) for a complete discussion), and a number of variants have been
proposed (von Luxburg, 2007). In its simplest form, the variant that is analyzed in (Lee et al., 2014b) consists
of three steps, summarized here:

_(a) Spectral Embedding. Compute the eigenvectors xj corresponding to the k smallest non-zero eigenvalues_
of the generalized problem Lx = λDx, under the constraint that x[T] _d = 0. The eigenvectors are normalized_
so that x[T]j _[Dx][j][ = 1][. Let][ X][ ∈]_ [R][n][×][k][ be the matrix whose columns are the][ k][ eigenvectors][2][.]

_(b) Orthogonal Projection. Let X_ _[′]_ = XR, where R[′] _∈_ R[k][×][k][′] a random orthogonal projection matrix, where
_k[′]_ _≤_ _k._

2Spectral embeddings can be computed in nearly-linear time. We discuss their computation in Appendix C.


-----

p p

_(c) Radial Projection. Let Y be the matrix resulting by dividing each row of X by its Euclidean norm, i.e._
by ‘radially projecting’ each point onto the unit sphere in R[k]. Each row of Y becomes the embedding of the
corresponding node.

_(d) Geometric Partitioning. Use some unsupervised geometric clustering algorithm on the embedding Y ._
(e.g. k-means, or the provable algorithms presented in (Lee et al., 2014b)).

We remark that the two hyperparameters k and k[′] are further specified in sections 2.2 and 3.1.

2.1.3 THE GEOMETRIC INSIGHT

The radial projection step reflects the geometric intuition that the eigenvectors place the nodes into k direc_tions in the embedding space._

Consider the eigenvector matrix X ∈ R[n][×][k]. These generalized eigenvectors are D-orthogonal (Stewart &
Sun, 1990), i.e. we have x[T]i _[Dx][j][ = 0][, for each][ i][ ̸][=][ j][. Given that the eigenvectors are also normalized, we]_
have X _[T]_ _DX = I._

Using a well known identity we have

_trace(X_ _[T]_ _DX) = trace(DXX_ _[T]_ ) = k.

Summing up the n diagonal entries of DXX _[T]_ we thus get

_n_

_dj||xj||2[2]_ [=][ k.] (1)
_j=1_

X

Now pick an arbitrary direction in R[k], i.e. a unit vector z. Let w = Xz. Since X _[T]_ _DX = I, and z[T]_ _z = 1_
we have


_z[T]_ _X_ _[T]_ _DXz = w[T]_ _Dw =_


_djwj[2]_ [= 1][.] (2)
_j=1_

X


Let us now take a closer look at the above equations. From equation 1 we get that that the d-weighted mass
of the n embedding points is k. On the other hand, note that wj[2] [is the norm of the projection of][ X][[][j][]][ onto]
_z. Thus, equation 2 shows that the d-weighted mass of the projections of the n points onto z is always equal_
to 1, for any direction z.

A further interpretation of the above equations is that any given direction z captures only a 1/k fraction of
the d-weighted sum of norms of the n embedding points. Hence the d-mass of the points must concentrate
in at least k different directions. While finding such directions is not straightforward, (Lee et al., 2014b)
proves that radially projecting the points onto the unit sphere has the following property: if S is a set of
points in Y that are in a ball of a small diameter in R[k], then S also cannot concentrate a large fraction of
the d-mass of the points, and thus the points in Y are expected to be in k well-separated spheres in R[k]. This
specific geometric arrangement facilitates the design of an unsupervised geometric clustering algorithm on
the points of Y in (Lee et al., 2014b), but it will also guide the design of our supervised geometric clustering
model.

2.2 NEURAL CLASSIFIERS

We present three types of neural classifiers that reflect our discussion in section 2.1. These are different but
they share certain layers and so they are presented in a compact way in Figure 1. Below we make our main
points on the design of these classifiers.


-----

p p

Figure 1: The forward function of the RADIAL classifiers. Pseudocode is given in Appendix section D.
Details of the algorithm are discussed in section 2.2. Section 2.3 considers initialization and training tricks.
We note that k is the embedding dimension, K is the number of channels, and nc is the number of classes.

Step (ii) in the unsupervised algorithm described in section 2.1.2 is a random orthogonal projection. In
analogy, we introduce a ‘Reduce Layer’ which in our case is entirely trainable. The Reduce and Radial
Projection layers are reproduced independently in K independent channels, where K is a hyperparameter.
Each of these channels has its own operator Ri.

We propose three different types of classifiers: Conic, Linear, and Spherical. These share the same parameters W and β. The outer dimension of W is proportional to the number of channels, but the inner dimension
of both W and β are equal to the number of classes. What differentiates these three types of classifiers is the
role of W and β. Their names reflect the corresponding geometric shape of the decision boundaries.

_Linear: Each of the nc rows of W defines a hyperplane in R[K][×][nc]_ as its normal vector. The decision
boundary for row Wj is the hyperplane yW + β.

_Conic: Row Wj represents represents a direction in R[K][×][nc]. The decision boundary is given by equation_
_βyW, given thatj −||Wj|| y2 has unit norm (line 12). We note that the decision boundary can be rewritten ascos(β), which is well-understood to describe the surface of a cone with axis Wj and aperture yWj + β[′],_
where β[′] = _Wj_ 2cos(β). Thus it can be seen that Conic is a restricted or ‘regularized’ version of Conic
_||_ _||_
because it enforces β[′] _Wj_ 2.
_≤||_ _||_

_Spherical: Row Wj represents a point in R[K][×][nc], which is the center of the sphere with of radius β. The_
decision boundary is the sphere β[2] _−||Wj −_ _y||2[2][.]_

2.3 INITIALIZATION AND TRAINING

The discussion in previous sections allows us certain considerations on the initialization of the trainable
parameters. In the unsupervised algorithm, the Reduce Layer is taken to be a random orthogonal projection,
and we can thus initialize it as such. Moreover, according to the discussion in section 2.1.3, the node
embeddings given by XR are expected to concentrate in at least nc different directions/geometric clusters
after the radial projection step. Approximate directions or ‘centers’ for these clusters can be found using
the spectral embeddings of the training points. Specifically, in order to compute such approximate centers
or directions, we take the radial projection of the training points for each cluster separately, compute their
average, and then we radially project it. These initializations can be carried out independently for each of
the K channels. In our experiments we have used such initializations; they do not affect accuracy, but seem
to improve convergence speed (see Appendix C.1).


-----

p p

We also explore a pre-training strategy for K-channel models. We first train K single-channel models
with different random initializations. The Reduce layers from these K models are used to initialize the
corresponding layers of the K-channel model, while the last layer (parameter matrix W ∈ R[K][·][nc][×][nc]) is
initialized randomly.

3 EXPERIMENTS

This section summarizes our experiments. Our comments on the implications of these experiments are given
as bullet-points.

3.1 EXPERIMENTAL SETUP

**Datasets, Hyperparameters, Variance. We use well-known benchmarks and follow standard practices.**
We refer the reader to Appendix A for detailed information.

**Embedding Dimension. We uniformly set the embedding dimension (parameter k in Figure 1) to k = 2·nc.**
We note that the performance of all methods can be slightly raised with a choice of higher dimension, but
we stick with a choice proportional to the number of classes in order to conform with the underlying theory.

**Evaluation Method. We measure the accuracy of the various methods trained with randomly selected**
training sets at label rates: 2[j]%, for j = 0, . . ., 5. For each label rate, we pick 5 different random training
sets. For each of these training sets we train each classifier for 5 different random initializations of the
trainable weights. For each such experiment, we perform 3-fold cross validation where each validation set
is selected randomly and consists of 20% of the training set (i.e. 20% of the label rate). We ensure that
every class is represented in our training set by forcing one random node from each class in the training set.
Validation is used for RADIAL in order to select the best-performing model over the course of training.

3.2 ABLATION STUDY

In Figure 2, we present an ablation study on the layers of the RADIAL classifier.

Figure 2: An ablation study. CONIC-2C includes all layers of RADIAL (fig, 1). The last layer is ‘Conic’ and
_K = 2. CONIC-2C-PT adds a pre-training strategy (see section 2.3). Details are discussed in section 3.2_
and a shorter ablation study on multiple channels can be found in Appendix E.1.


-----

p p

Classifier NO-RADIAL in the Linear branch of RADIAL, excluding the Reduce and Radial Projection layers.
Classifier NO-REDUCE runs the Linear branch excluding the Reduce layer. The results are similar when
Conic or Spherical are used instead. Classifiers CONIC and SPHERICAL include all layers of the RADIAL
algorithm in Figure 1.

_• We note that despite its very different and non-standard mathematical form, the performance of SPHERI-_
CAL is comparable to CONIC, and potentially better. However we have found that it requires more training,
and the reported results use 4K epochs of training for SPHERICAL, and 2K epochs of training for SPHERICAL. For that reason, we stick with CONIC for the multi-channel experiments.

_• Overall, Figure 2 justifies the layers of RADIAL, especially for larger datasets, and demonstrates the extra_
power of multiple channels and appropriate pre-training strategies. The CORA dataset is a clear exception
that we discuss separately in section 3.4. Further ablation studies are reported in section E.1.

3.3 RADIAL VS STANDARD CLASSIFIERS

In Figure 3 we present a comparison of CONIC-2C and CONIC-2C-PT with standard classifiers. As input to
these other classifiers, we use the radially projected spectral embedding, as it maximizes their performance.

Figure 3: Comparing standard classifiers with RADIAL classifiers.

We compare with a simple one-vs-rest logistic regression classifier. Specifically, we use the LIBLINEAR
library, with its default regularization (LIBLINEAR-R) and no regularization (LIBLINEAR-NR). We also
compare with a kNN classifier, for k=11 that we found to be a good choice. We have also performed
experiments with a standard SVM classifier which did not perform as well. We note that these classifiers do
not use validation; the validation sets are added to the training sets.

_• LIBLINEAR-R was the classifier of choice in DEEPWALK (Perozzi et al., 2014), where it was also used_
in combination with spectral embeddings. We see that RADIAL classifiers increase accuracy, sometimes by
more than 15% relative to this previously used standard classifier [3].

_• We also observe that the use of regularization is detrimental to the accuracy of LIBLINEAR, which corrob-_
orates the theoretical insight on the value of the radial projection step. However, CITESEER and CORA are
exceptions, indicating that overfitting may be an issue for these smaller datasets.

3(Perozzi et al., 2014) do not give details on their implementation of supervised spectral clustering and they do not
use these 6 benchmarks. Based on their description, accuracy of their variant of supervised spectral clustering would
have likely been lower that what we report in row-1.


-----

p p

_• Overall the results of this section show that RADIAL classifiers perform better than standard classifiers,_
with the notable exception of CORA, that we discuss separately, in section 3.4.

3.4 RADIAL SPECTRAL CLUSTERING VS OTHER METHODS

In this section we compare the RADIAL classifier with other methods. The goal of this section is not to claim
that RADIAL classifiers are superior, but to compare them directly with some widely acclaimed methods.
Hence, the list is not exhaustive by any means.

Figure 4: Comparing other methods with RADIAL classifiers. Computing the NETMF and DEEPWALK
embeddings is extremely time-consuming for the two largest sets, thus no results are reported for them.

Specifically we consider these algorithms: DeepWalk (Perozzi et al., 2014), NetMF (Qiu et al., 2018b),
a standard GCN model[4] (Kipf & Welling, 2017) and the RANDOMWALKER algorithm (harmonic label
interpolation) (Grady, 2006). RANDOMWALKER is a non-parameteric algorithm and it is much faster than
all other methods. On the other hand, DEEPWALK and NETMF are computationally much more expensive
than RADIAL. We observe that:

_• Standard GCNs are less competitive in the context of graphic data. Thus we can conjecture that GCNs_
make sub-optimal use of graphic features.

_• Due to the approximation loss reflected in standard Cheeger inequalities, eigenvectors of the normalized_
Laplacian do not always yield good approximations of low-conductance clusters. According to theory developed in (Koutis & Le, 2019), in such cases, a graph modification can alleviate the problem. CORA-mod
is such a modified version of the CORA graph[5]. Thus, the fact that CORA-mod gives rise to a much better
spectral embedding explains the failure observed for CORA in previous sections.

_• RANDOMWALKER has always a very strong performance in higher training ratios, but it can be very_
erratic in lower training ratios, where non-trainable graph embeddings do better. In general, RADIAL is
directly competitive to DEEPWALK and NETMF, for a small fraction of runtime.

_• RANDOMWALKER is based on a harmonic interpolation objective similar to that used in the Correction &_
Smooth (C&S) procedures in (Huang et al., 2021). Indeed, in Figure 9 in the Appendix, we observe that the
accuracy enhancement added by C&S correlates strongly with the training ratio. Figure 9 also shows that an
improved ‘base’ generally improves the final output of C&S.

4GCNs by design operate with node features; here we use one-hot vectors as suggested in (Kipf & Welling, 2017).
5CORA-mod is used only for CONIC-2C. DEEPWALK and NETMF effectively work with a modified graph.


-----

p p

4 HANDLING NODE FEATURES

In this section we go beyond graphic features, and include existing node features in RADIAL. To enable our
RADIAL classifiers to work with features we incorporate one extra channel to the architecture of Figure 1.
The features are standardized to have zero mean and constant standard deviation, and the rest of the layers
are kept in place, including the Radial Projection layer. We find that this simple change raises the accuracy
of our model in all cases, except the CITESEER data set. These results are reported in Figure 5.

Figure 5: Adding features to a RADIAL classifier

4.1 BOOSTING GCNS WITH LEARNED GRAPHIC FEATURES

We have found that GCNs make a better use of node features and in fact produce higher accuracy relative to
that reported in Figure 5 for CONIC-2-FT. Thus GCNs remain very strong when node features are available.
Given that RADIAL performs better than GCNs in the graphic setting, we thus propose to use the learned
**features of our CLASSIFIER. Specifically we use the activations of the Concatenation layer of the model**
learned in Figure 5, and feed them as additional input to the standard GCN. The outcome of this approach
for the ARXIV data set is shown in Figure 6.

Figure 6: Enhancing node features with features learned by CONIC-2C-FT, for the ARXIV data set.

A thorough exploration of the power of these learned graphic features in the broader context of GNNs is not
in the indented scope of this work, and it is left open for future work.

5 CONCLUSION

Research on transductive node classification tasks has recently been dominated by Graph Neural Networks
and the evolution of progressively more elaborate and highly-parameterized neural architectures that yield
end-to-end trainable network embeddings. This is in stark contrast to the pre-GNN period, when the collective focus was on the design of network embedding methods, with apparently little research devoted to the
downstream classification task. In this work we argued that developing a better theoretical understanding of
the geometric embedding opens up the fundamental research direction of designing better geometry-aware
classifiers. This direction can lead to surprising substantial improvements, even for older algorithms, such as
spectral clustering. In principle, this reasoning can be applied to other existing network embedding methods
with the potential to –more broadly– inform the design of improved graph neural architectures.


-----

p p

REFERENCES

Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary L. Miller, and Richard Peng. Simple and scalable
constrained clustering: a generalized spectral method. In AISTATS, 2016.

Leo Grady. Random Walks for Image Segmentation. IEEE Trans. on Pattern Analysis and Machine Intelli_gence, 2(11):1768–1783, 2006._

Aditya Grover and Jure Leskovec. Node2Vec: Scalable Feature Learning for Networks. In Proceedings
_of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD_
’16, pp. 855–864, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4232-2. doi: 10.1145/2939672.
[2939754. URL http://doi.acm.org/10.1145/2939672.2939754.](http://doi.acm.org/10.1145/2939672.2939754)

Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and
Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv:2005.00687

_[[cs, stat], February 2021. URL http://arxiv.org/abs/2005.00687. arXiv: 2005.00687.](http://arxiv.org/abs/2005.00687)_

Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining Label Propagation
and Simple Models out-performs Graph Neural Networks. In International Conference on Learning
_[Representations, 2021. URL https://openreview.net/forum?id=8E1-f3VhX1o.](https://openreview.net/forum?id=8E1-f3VhX1o)_

Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks.
In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26,
_[2017, Conference Track Proceedings. OpenReview.net, 2017. URL https://openreview.net/](https://openreview.net/forum?id=SJU4ayYgl)_
[forum?id=SJU4ayYgl.](https://openreview.net/forum?id=SJU4ayYgl)

Andrew V Knyazev. Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method. SIAM Journal on Scientific Computing, 23(2):517–541, 2001. doi:
[10.1137/S1064827500366124. URL https://doi.org/10.1137/S1064827500366124.](https://doi.org/10.1137/S1064827500366124)

Ioannis Koutis and Huong Le. Spectral Modification of Graphs for Improved Spectral Clustering. In
Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alch´e Buc, Emily B. Fox, and
Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference
_on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver,_
_[BC, Canada, pp. 4859–4868, 2019. URL https://proceedings.neurips.cc/paper/2019/](https://proceedings.neurips.cc/paper/2019/hash/dbbf603ff0e99629dda5d75b6f75f966-Abstract.html)_
[hash/dbbf603ff0e99629dda5d75b6f75f966-Abstract.html.](https://proceedings.neurips.cc/paper/2019/hash/dbbf603ff0e99629dda5d75b6f75f966-Abstract.html)

Ioannis Koutis, Gary L. Miller, and David Tolliver. Combinatorial preconditioners and multilevel solvers
for problems in computer vision and image processing. Computer Vision and Image Understanding, 115
(12):1638–1646, 2011.

James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way spectral partitioning and higher-order
Cheeger inequalities, 2014a.

James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway Spectral Partitioning and Higher-Order
Cheeger Inequalities. ACM, 61:37:1–37:30, 2014b.

R. B. Lehoucq, D. C. Sorensen, and C. Yang. ARPACK: Solution of Large Scale Eigenvalue Problems by
_Implicitly Restarted Arnoldi Methods. Available from netlib@ornl.gov, 1997._

Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Algorithmic Extensions of
Cheeger’s Inequality to Higher Eigenvalues and Partitions. In Proceedings of the 14th International
_Workshop and 15th International Conference on Approximation, Randomization, and Combinatorial Op-_
_timization: Algorithms and Techniques, pp. 315–326. Springer-Verlag. ISBN 978-3-642-22934-3._

10


-----

p p

A. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, 2001.

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. DeepWalk: Online Learning of Social Representations.
In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data
_Mining, KDD ’14, pp. 701–710, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2956-9. doi:_
[10.1145/2623330.2623732. URL http://doi.acm.org/10.1145/2623330.2623732.](http://doi.acm.org/10.1145/2623330.2623732)

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network Embedding as Matrix
Factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In Proceedings of the Eleventh ACM
_International Conference on Web Search and Data Mining, pp. 459–467, Marina Del Rey CA USA,_
February 2018a. ACM. ISBN 978-1-4503-5581-0. doi: 10.1145/3159652.3159706. [URL https:](https://dl.acm.org/doi/10.1145/3159652.3159706)
[//dl.acm.org/doi/10.1145/3159652.3159706.](https://dl.acm.org/doi/10.1145/3159652.3159706)

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network Embedding as
Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In Proceedings of the Eleventh
_[{ACM} International Conference on Web Search and Data Mining, {WSDM} 2018, Marina Del Rey,](https://doi.org/10.1145/3159652.3159706)_
_[CA, USA, February 5-9, 2018, pp. 459–467, 2018b. doi: 10.1145/3159652.3159706. URL https:](https://doi.org/10.1145/3159652.3159706)_
[//doi.org/10.1145/3159652.3159706.](https://doi.org/10.1145/3159652.3159706)

Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Anal. Mach.
_[Intell., 22(8):888–905, August 2000. ISSN 0162-8828. doi: 10.1109/34.868688. URL https://doi.](https://doi.org/10.1109/34.868688)_
[org/10.1109/34.868688. Place: Washington, DC, USA Publisher: IEEE Computer Society.](https://doi.org/10.1109/34.868688)

G. W. Stewart and Ji-Guang Sun. Matrix Perturbation Theory. Academic Press, Boston, 1990.

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web, pp.
1067–1077, Florence Italy, May 2015. International World Wide Web Conferences Steering Committee.
[ISBN 978-1-4503-3469-3. doi: 10.1145/2736277.2741093. URL https://dl.acm.org/doi/10.](https://dl.acm.org/doi/10.1145/2736277.2741093)
[1145/2736277.2741093.](https://dl.acm.org/doi/10.1145/2736277.2741093)

Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowl_edge Discovery, 23(3):447–478, November 2011._ ISSN 1384-5810, 1573-756X. doi: 10.1007/
[s10618-010-0210-x. URL http://link.springer.com/10.1007/s10618-010-0210-x.](http://link.springer.com/10.1007/s10618-010-0210-x)

Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel M¨uller. VERSE: Versatile Graph Embeddings from Similarity Measures. In Proceedings of the 2018 World Wide Web Conference on World Wide
_Web - WWW ’18, pp. 539–548, Lyon, France, 2018. ACM Press. ISBN 978-1-4503-5639-8. doi: 10.1145/_
[3178876.3186120. URL http://dl.acm.org/citation.cfm?doid=3178876.3186120.](http://dl.acm.org/citation.cfm?doid=3178876.3186120)

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li`o, and Yoshua Bengio.
Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018,
_Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018._
[URL https://openreview.net/forum?id=rJXMpikCZ.](https://openreview.net/forum?id=rJXMpikCZ)

[Ulrike von Luxburg. A Tutorial on Spectral Clustering. CoRR, abs/0711.0, 2007. URL http://arxiv.](http://arxiv.org/abs/0711.0189)
[org/abs/0711.0189.](http://arxiv.org/abs/0711.0189)

11


-----

p p

A DATASETS, HYPERPARAMETERS, VARIANCE.

**Datasets. We use 6 labeled datasets that have been used widely as benchmarks. These datasets have been**
processed to remove small connected components because spectral clustering naturally works on a connected
graph[6]; self-loops are also removed. For all datasets, we treat the graphs as undirected and only consider the
largest connected component. Table 1 summarizes the number of vertices, edges and classes of these largest
connected components.

Dataset CITESEER CORA WIKICS PUBMED ARXIV PRODUCTS

_|V |_ 3,327 2,708 11,701 19,717 169,343 2,449,029
_|V[˜] |_ 2,120 2,485 11,311 19,717 169,343 2,385,902

_|E|_ 4,614 6,632 215,863 44,326 2,315,598 123,718,152
_|E[˜]|_ 3,679 5,069 215,554 44,324 2,315,598 123,612,606
#classes 6 7 10 3 40 47

Table 1: Number of vertices and edges in the original and processed graphs

**Code and Experiments. All experiments were performed on Google Colab. The final paper will dissemi-**
nate all code, including the models and the experimental setting.

**Hyperparameter Settings. In RCS-CLASSIFY (algorithm 1), we take k = 2 · nc, where nc is the number**
of classes. In non-reported experiments we have found that further increasing the number of dimensions can
slightly increase accuracy, but we take a theory-consistent decision to make the dimension proportional to
number of clusters. The Random Walker algorithm does not have any hyperparameters or learnable parameters. For the GCN model we used the recommended settings, using the identity matrix in the input into the
GCN. For NetMF we followed the recommended default settings, using an embedding of 128 dimensions.
The dimension for DeepWalk is set to be 2 · nc; this deviates from the recommendation but it is added here
for direct comparison with the setting for RADIAL.

**Variance. We note that we omit information on the standard deviation of accuracy over random splits and**
random initializations. This is in general low (<0.5%) with the exception of 1-2% training ratio for the three
smaller datasets, where standard deviation can be as high as 3%.

B FURTHER DISCUSSION

_• We have also considered the applications of Support Vector Machines on the radially projected spectral_
embedding. The results were not competitive, and thus they are not included here.

_• The RANDOMWALKER method has rarely -if ever- been used as benchmark for supervised node classifica-_
tion on social graphs. However the success of C&S, a closely related algorithm, motivates the experimental
study of the RANDOMWALKER algorithm, the strengths of which include the fact that it does not have any
hyperparameters or trainable parameters. We see that in multiple cases RANDOMWALKER is a viable alternative to other models, especially considering that with a proper implementation using Laplacian solvers,
RANDOMWALKER is by far faster than all other methods in Table ??. The C&S process is not applicable
to the output of RANDOMWALKER for certain concrete technical reasons, but a worthy research topic it
to modify RANDOMWALKER in a way that would enable the application of C&S, in order to enhance its
performance.

6One can use the node features to connect these smaller connected components. We avoid this practice in order to
stick with the decision to only use graphic data.

12


-----

p p

C EFFICIENT COMPUTATION

We discuss the computation of eigenvectors of the generalized eigenvalue problem Lx = λDx. Several
works compute eigenvectors using implementations of ARPACK (Lehoucq et al., 1997) in libraries for sparse
matrix algebra, in Matlab, Python, or Julia (e.g. (Huang et al., 2021)). Social networks usually have eigenvalue distributions that are ‘friendly’ to power methods (that are used in ARPACK) in the sense that they can
converge in a reasonable amount of time. However that is not guaranteed, and in practice convergence can
be much slower than possible. Fast convergence can presently be guaranteed only via using inverse-power
algorithms, i.e. algorithms that use approximations of the inverse of the Laplacian, often used as preconditioners. In this work we use the preconditioned eigensolver LOBPCG (Knyazev, 2001) with the CMG preconditioner (Koutis et al., 2011). Besides its stronger theoretical properties, the particular implementation is
also significantly faster in practice, even on social networks.

C.1 INITIALIZATION AND CONVERGENCE

Figure 7: Convergence of the loss function on the ARXIV with and without the special initilization described
in section 2.3. Initialization results in faster convergence. (Loss is in logarithmic scale for clarity.)

13


-----

p p

D THE ALGORITHM

**Algorithm 1 Radial-Conic-Spherical Classifier with K channels**


1: Input: x ∈ R[1][×][k]: eigenvector embedding, type: ‘Linear’ or ‘Conic’
2: Output: y ∈ R[1][×][nc]: nc is the number of classes
3:
4: Trainable parameters:
5:6: R Wi ∈ ∈ RR[K][k][×][·][nc][nc][×], for[nc] _i = 1, . . . K, where K is a hyperparameter_

7: β ∈ R[1][×][nc]

8:
9: function RCS-CLASSIFY(x)

10: **for i=1 do to K**

11: _y = xRi_ _▷_ [optional]

12: _yi = y/||y||2_ _▷_ radial projection

13: **end for**

14: _y = [y1; . . . ; yK]_ _▷_ concatenate

15: **if type = ‘Conic’ then**

16:17: _wy =nrm yW = normwnrm(W, dim._ _cos = 1)(β)_ _▷wnrm ∈_ R[1][×][nc]: vector of 2-norms of columns of▷. denotes pointwise multiplication W

_−_ _∗_ _∗_

18: **else if type = ‘Linear’ then**

19: _y = yW + β_

20: **else if type = ‘Spherical’ then**

21: _y = β[2]_ _−_ (W − **1[K][·][nc][×][1]y)[2]** _▷_ squaring is entry-wise

22: **end if**

23: _y = softmax(y)_

24: end function

14


-----

p p

E MISC EXPERIMENTS

E.1 ABLATION EXPERIMENTS

We have performed these additional ablation experiments:

-  We added bias to the Reduce layer. This makes the models more general. However, in practice, it
has a negative impact on accuracy.

-  We made the Reduce layer non-trainable and orthogonal (as suggested in Lee et al. (2014a)). This
has a significantly negative impact on accuracy.

-  We have added a regularization term ||R ∗ _R[T]_ _−_ _I||F that penalizes the Reduce layer for deviating_
from orthogonality. This has a negative impact on accuracy.

We also experimented with adding more channels to the RADIAL classifiers, which seems to have a positive
**impact on accuracy. On a specific fixed training set for the ARXIV recorded accuracies are shown in**
Figure 8.

Figure 8: An experiment with multiple channels

15


-----

p p

ALL RESULTS WITH CORRECTION AND SMOOTH

Figure 9: Summary of all results

16


-----

