Year: 2021

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.

heading: 1 INTRODUCTION
text: 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
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 clustering 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 theoryinformed 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.

heading: 2 SPECTRAL CLUSTERING WITH SUPERVISION: THE ALGORITHM

heading: 2.1 SPECTRAL EMBEDDING AND GEOMETRIC INTUITION
text: 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.

heading: 2.1.1 DEFINITIONS AND TERMINOLOGY
text: 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) = ∑
i∈S,j 6∈S
wi,j
We also define the volume of S to be vol(S) = ∑ s∈S cut(v).
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
φ(S) = cap(S, V − 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.

heading: 2.1.2 SPECTRAL EMBEDDING AND THE UNSUPERVISED ALGORITHM
text: 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 Si = 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 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 xT d = 0. The eigenvectors are normalized so that xTj Dxj = 1. Let X ∈ Rn×k be the matrix whose columns are the k eigenvectors2.
(b) Orthogonal Projection. LetX ′ = XR, whereR′ ∈ Rk×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.
(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 Rk. 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.

heading: 2.1.3 THE GEOMETRIC INSIGHT
text: The radial projection step reflects the geometric intuition that the eigenvectors place the nodes into k directions in the embedding space.
Consider the eigenvector matrix X ∈ Rn×k. These generalized eigenvectors are D-orthogonal (Stewart & Sun, 1990), i.e. we have xTi Dxj = 0, for each i 6= j. Given that the eigenvectors are also normalized, we have XTDX = I .
Using a well known identity we have
trace(XTDX) = trace(DXXT ) = k.
Summing up the n diagonal entries of DXXT we thus get n∑
j=1
dj ||xj ||22 = k. (1)
Now pick an arbitrary direction in Rk, i.e. a unit vector z. Let w = Xz. Since XTDX = I , and zT z = 1 we have
zTXTDXz = wTDw = n∑ j=1 djw 2 j = 1. (2)
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 w2j 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 Rk, 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 Rk. 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.

heading: 2.2 NEURAL CLASSIFIERS
text: 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.
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 RK×nc as its normal vector. The decision boundary for row Wj is the hyperplane yW + β.
Conic: Row Wj represents represents a direction in RK×nc. The decision boundary is given by equation yWj − ||Wj ||2cos(β), which is well-understood to describe the surface of a cone with axis Wj and aperture β, given that y has unit norm (line 12). We note that the decision boundary can be rewritten as 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 RK×nc, which is the center of the sphere with of radius β. The decision boundary is the sphere β2 − ||Wj − y||22.

heading: 2.3 INITIALIZATION AND TRAINING
text: 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).
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 ∈ RK·nc×nc) is initialized randomly.

heading: 3 EXPERIMENTS
text: This section summarizes our experiments. Our comments on the implications of these experiments are given as bullet-points.

heading: 3.1 EXPERIMENTAL SETUP
text: 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: 2j%, 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.

heading: 3.2 ABLATION STUDY
text: In Figure 2, we present an ablation study on the layers of the RADIAL classifier.
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 SPHERICAL 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.

heading: 3.3 RADIAL VS STANDARD CLASSIFIERS
text: 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.
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 corroborates 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.
• 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.

heading: 3.4 RADIAL SPECTRAL CLUSTERING VS OTHER METHODS
text: 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.
Specifically we consider these algorithms: DeepWalk (Perozzi et al., 2014), NetMF (Qiu et al., 2018b), a standard GCN model4 (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 graph5. 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.

heading: 4 HANDLING NODE FEATURES
text: 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.

heading: 4.1 BOOSTING GCNS WITH LEARNED GRAPHIC FEATURES
text: 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.
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.

heading: 5 CONCLUSION
text: 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.

heading: A DATASETS, HYPERPARAMETERS, VARIANCE.
text: 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 graph6; 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.
Code and Experiments. All experiments were performed on Google Colab. The final paper will disseminate 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%.

heading: B FURTHER DISCUSSION
text: • 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 classification 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.

heading: C EFFICIENT COMPUTATION
text: 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

heading: D THE ALGORITHM
text: Algorithm 1 Radial-Conic-Spherical Classifier with K channels
1: Input: x ∈ R1×k: eigenvector embedding, type: ‘Linear’ or ‘Conic’ 2: Output: y ∈ R1×nc: nc is the number of classes 3: 4: Trainable parameters: 5: Ri ∈ Rk×nc, for i = 1, . . .K, where K is a hyperparameter 6: W ∈ RK·nc×nc 7: β ∈ R1×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: wnrm = norm(W,dim = 1) . wnrm ∈ R1×nc: vector of 2-norms of columns of W 17: y = yW − wnrm. ∗ cos(β) . .∗ denotes pointwise multiplication 18: else if type = ‘Linear’ then

heading: 19: y = yW + β
text: 20: else if type = ‘Spherical’ then 21: y = β2 − (W − 1K·nc×1y)2 . squaring is entry-wise 22: end if 23: y = softmax(y) 24: end function

heading: E MISC EXPERIMENTS
text: 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 ∗RT − 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.

heading: F ALL RESULTS WITH CORRECTION AND SMOOTH

Review summaries:
This paper presents a comprehensive analysis of spectral clustering based approaches for node classification in graph-based data. The paper thoroughly analyzes design decisions of using spectral clustering in this supervised setting. The empirical results indicate that even compared to GCN / deeper approaches, the less parametric spectral clustering-based approach can be competitive or better at classification tasks. 

The paper argues for refocusing the efforts of the graph neural network community onto previous work on spectral clustering. The authors propose the addition of simple, but structured, classification methods to an existing unsupervised spectral clustering algorithm. A battery of empirical results on standard graph benchmarks demonstrate the effectiveness of such simple models and compare favourably to existing, more complex models.

This paper reviewed the application of spectral clustering embedding on node-level classification problems. It first revisited the theoretical foundation of spectral clustering, related to the graph NCut problems. Then it introduced neural network-based classifiers which utilize the embedding for classification tasks. Their benchmark results validated that the neural network framework showed certain advantages in accuracy. And the "correction & smooth" introduced by Huang et al (ICLR 2021) would also improve the performance in a relative big margin.

The paper proposes a study about spectral clustering techniques. Given the standard spectral clustering approach, some variations are investigated, also using recent advancements in the field. The experiments show that such a simple approach can produce state-of-the-art results on social graphs.