Neurally boosted supervised spectral clustering
Authors: Ali Parviz
Ioannis Koutis
Venue: ICLR 2022 Submitted (2022)
Keywords: Supervised Node Classification
Spectral Embedding
Social Graphs
Neural Models

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 the computation of eigenvectors of a normalized graph Laplacian.   When coupled with standard classifiers, spectral embeddings yield strong baseline performance in node classification tasks. Remarkably, it has been recently shown that these `base' classifications followed by a simple `Correction and Smooth' procedure reach state-of-the-art performance on widely used benchmarks. All these recent works employ classifiers that are agnostic to the nature of the underlying embedding. We present simple neural models that leverage fundamental geometric properties of spectral embeddings and obtains significantly improved classification accuracy over commonly used standard classifiers. Our results are based on a specific variant of spectral clustering that is not well-known, but it is presently the only variant known to have analyzable theoretical properties. We provide a \texttt{PyTorch} implementation of our classifier along with code for the fast computation of spectral embeddings. 

Under review conference paper at ICLR 2022
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 machine learning techniques. Spectral network embeddings are based on eigenvectors of 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 pro- vide a theory-informed implementation of supervised spectral clustering and maximize its performance with the use of a carefully designed RADIAL classifier that leverages fun- damental geometric properties of spectral embeddings. RADIAL raises the performance of supervised spectrally clustering to previously unobserved levels and renders 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 classical unsupervised algorithm for clustering in graphs. gained prominence in data mining and machine learning approximately two decades ago (Shi & Malik, 2000, Ng et al. (00T) and it has since found many applications in multiple domains. While originally concerved as an unsu- pervised 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 TTag & Liu 1 was likely what initiated 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 network embedding, (ii) using the embed- ding as input to a standard classifier. They instantiated step (i) with a spectral embedding, giving thus rise to supervised spectral clustering algorithm. Albeit simple, the algorithm proved be
what can be viewed 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 embed- dings, including (Grover & Leskovec 2016 Tang al. 2015 Tsitsulin et al.) 2018 Qiu al. 2018a), and a race for higher classification accuracy More recently. network embedding methods were succeeded by graph neural networks (GNNs) (e.g. see Kipf & Welling 2017 Velickovie et al. (018)) that have dom- inated the competition. Since the publication of DREPWALKK, 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
A very detailed list can be found in htttts:///ggii wtt.://....oocccccc.......accc www.onggwwweeeeeeeee networkkeeett------e netxork-eebedddinn

---

Under review conference paper at ICLR 2022
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 cluster- ing' 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 PPerozzi 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 a [ also use the normalized graph Laplacian but with 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 All SVM-based model (Tang & Liu 2011). an One-vs Sine-v-RRess Rest logistic regression model (Perozzi et al. 2014). softmax regression model, and three-layered neural network (Huang al., 2021). Adding to the contusion, 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. 202T).
Goal. These considerations provide the motivation of our work. Concretely, we seek to provide theory- informed implementation of supervised spectral clustering, maximize performance with the use of a care- fully 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 variant of spectral clustering that is not well-known widely used, yet can be theoretically analyzed without assumptions about the underlying graphs. The analysis of Lee et al. applies to unsupervised clustering. Thus key contribution of our work is 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 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 directly competitive to prominent alternative methods that were thought to be vastly superior. On the other hand, we observe that non- non-parametric diffusion- 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. (021). Moreover, based on intuition derived section 3.4, we develop a method of enhancing the performance of standard GCNs (Kipf & Welling 2017). More specifically, in section 4 show that when node features available, the performance of GCNs can be significantly enhanced by feeding as additional input features learned by our RADIAL classifier.
2

---

Under review conference paper at ICLR 2022
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 run in linear time with strong convergence guarantees. In Section 2.1.33 we discuss the geometric intuition that underlies the theoretical analysis in (Lee et al. 2014b). We note that the material in this subsection the geometric intuition which plays key role in the construction of our classifiers.
We present it for completeness and in particular in order to discuss
2.1.1 DEFINITIONS AND TERMINOLOGY
Let = (V, E, w) be a weighted undirected graph. Definition (Cut and Volume). S C V, we define the cut of S to be
cut(S) Σ
Wi.j
iEBJES
We also define the volume of S to be
( E cut(u).
SES
We will often use the term degree for the cut of a single node.
Definition (Conductance). The conductance of a cluster S C V is defined by
Vop(S.V-55
o(S) min(vol(S)),vo (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 is the adjacency matrix of the graph.
2.1.2 SPECTRAL EMBEDDING AND THE UNSUPERVISED ALGORITIM
The combinatorial idea that underlies spectral clustering is that good clusters should have a relatively small volume to their exterior, or more specifically low conductance. More concretely, the goal is to find k disjoint clusters S5. such that max; ((S)) is as small as possible. this paper we will looking for & clusters that also provide partitioning of the vertex set, i.c. we have U, S; V. The partitioning problem is less well-understood (Louis et al.)., but its simpler non non-partitioning variant has been studied extensively from theoretical perspective (Lee et al.) (2014)), and approximation guarantees are known for it. The spectral clustering algorithm is broadly understood as a relaxation of the discrete clustering problem (e.g. (Cucuringu al. (0166) for complete discussion), and 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 æj corresponding to the A smallest non-zero eigenvalues of the generalized problem La = ADx, under the constraint that x d = O. The eigenvectors are normalized that u Day- 1. Let X E Baak be the matrix whose columns the k eigenvectors
(b) Orthogonal Projection. Let X' X.R, where R' E k random orthogonal projection matrix, where <
Spectral embeddings be computed in nearly-linear time. We discuss their computation in Appendix C
3

---

Under review conference paper at ICLR 2022
(c) Radial Projection. Let Y be the matrix resulting by dividing each row of X by its Euclidean norm, i.c. by "radially projecting' each point onto the unit sphere in R 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 (Lee 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 the embedding space.
Consider the eigenvector matrix X E R"*k, These generalized eigenvectors are D-orthogonal Stewart & Sun 1990p. i.c. we have z! Dr, = for each i * j. Given that the eigenvectors are also normalized, we have
X 1.
Using well known identity we have
trace(X' X DX)= = trace(DXXX) = k.
Summing up the n diagonal entries of DXX we thus get
(1)
Now pick arbitrary direction in R2 i.e. unit vector z. Let w Xz. Since X and 2²= we have
= Dw Σ 5=1
djw =1.
Let us now take closer look at the above equations. From equation 1 we get that that the d-weighted mass of the embedding points kt On the other hand, note that wy the norm of the projection of X[j] onto Thus, equation shows that the d- d-weighted mass of the projections of the points onto is always equal to 1, for any direction z.
A further interpretation of the above equations is that any given direction captures only 1/k fraction of the d-weighted sum of norms the n embedding points. Hence the d-mass of the points must concentrate in at least & different directions. While finding such directions is not straightforward, <Lee al. 2014b) proves that radially projecting the points onto the unit sphere has the following property: if S is set of points in Y that are in a ball of small diameter in R& then S also cannot concentrate large fraction of the d-mass of the points, and thus the points in Y are expected to be in well-separated spheres in R2 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 different but they share certain layers and so they are presented in a compact way in Figure Below we make our main points the design of these classifiers.
4

---

Under review conference paper at ICLR 2022
Reduce layer
Radial Projectionlayee
Choice model
Trainable Params
RAxoe
Linear ylV +
RR RRnene
R
31
livilla
Concatenation
Rixne
embodding
y = billl [bax]
Conic
Softmax(2)
2
2 yW
Warm- cou (
1 k
1 x K
1
VK zRg
UK
RK
Spherical
8 (W 1 18 y)
1 X nc
x
Figure 1: The forward function of the RADIAL classifiers. Pseudocode is given in Appendix section D Details 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 ne 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 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 RG.
We propose three different types of classifiers: Conic, Linear, and Spherical. These share the same parame- ters W and B. The outer dimension of W is proportional to the number of channels, but the inner dimension of both W and B are equal to the number of classes. What differentiates these three types of classifiers is the role of W and B. Their names reflect the corresponding geometric shape of the decision boundaries.
Linear: Each of the rows of W defines hyperplane in RKxn its normal vector. The decision boundary for row Wi is the hyperplane y yW + 3.
Conic: Row W, represents represents a direction in Knee, The decision boundary is given by equation yW,- - [|W ( which is well-understood to describe the surface of cone with axis W, and aperture 3. given that has unit norm (line 12). We note that the decision boundary can be rewritten as yW, + 8', where 3' ||W; [Wjllacos(3). Thus can be seen that Conic restricted or 'regularized" version of Conic because it enforces 3' < [|ll
Spherical: Row W, represents a point in RKxne which is the center of the sphere with of radius 3. The decision boundary is the sphere 3 I|W -l...
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 X R are expected to concentrate in at least nc different directions/geometi after the radial projection step. Approximate directions or 'centers' for these clusters can 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 channels. In our experiments we have used such initializations; they do not affect accuracy, but seem improve convergence speed (see Appendix C.1
clusters
5

---

Under review conference paper at ICLR 2022
We also explore pre-training strategy for K-channel models. We first train single-channel models with different random initializations. The Reduce layers from these K models are used to initialize the corresponding layers of the K K-channel model, while the last layer (parameter matrix W E IR nexnc) initialized randomly.
3
EXPERIMENTS
This section summarizes our experiments. Our comments on the implications of these experiments are given as bullet-ppints.
3.1 EXPERIMENTAL SETUP
Datasets, Hyperparameters, Variance. We use well-known benchmarks and follow standard practices. We refer the reader to Appendix(A]foo detailed information.
Embedding Dimension. We uniformly set the embedding dimension (parameter k in Figure I to k = 2-nc We note that the performance of all methods can slightly raised with choice of higher dimension, but we stick with choice proportional to the number of classes in order to conform with the underlying theory.
measure the accuracy of the various methods trained with randomly selected training sets at label rates: 27, for j O..... 5. For each label rate, 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, is selected randomly and consists of 20% of the training set (i.e. 20% the label rate). We ensure that every class is represented in our training set by forcing 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.
Evaluation Method.
perform 3-fold cross validation where each validation set
3.2
ABLATION STUDY
In Figure we present an ablation study on the layers of the RADIAL classifier.
CITESEER
CORA
WIKICS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
NO-RADIAL
56.4
50.3
51.0
54.3
57.4
58.4
16.7
23.9
25.7
28.6
26.8
29.0
29.7
34.3
35.0
37.7
35,8
35.9
CONIC
45.8
59.6
64.6
67.6
69.7
70.7
16.0
19.0
19.0
22.7
24.4
26.7
69.9
73.2
75.0
75.4
78.7
SPHERICAL
45.0
62.3
65.1
67.9
69.0
70.9
18.1
19.6
22.3
24.5
26.3
28.1
68.8
73.2
75.3
76.9
78.5
79.0
48.1
60.9
65.3
68.2
69.9
17.1
17.9
20.2
21.7
21.7
27.0
70.5
74.0
75.0
76.1
78.4
79.8
CONIC-2C-PT
53.5
65.5
69.1
71.0
17.4
20.1
20.8
22.0
25.8
73.9
75.3
77.6
78.0
80.1
PUBMED
ARXIV
PRODUCTS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
31.1
NO-REDUCE
63.5
64.6
63.4
64.3
65.2
64.0
47.6
48.5
49.0
49.3
49.3
49.4
66.6
66.7
66.6
66.7
3 CONIC
75.6
75.4
76.0
76.6
76.6
76.6
58.4
60.5
61.3
62.1
62.4
62.5
80.9
80.9
80.9
81.0
75.0
75.0
75.5
76.0
76.1
76.3
57.8
60.5
61.9
63.0
63.7
63.8
82.1
82.3
82.4
82.5
CONIC-2C
75.2
76.0
76.4
76.8
76.8
58.6
60.7
64.1
64.9
65.4
83.9
84.0
CONIC-2C-PT
75.3
75.9
76.1
76.5
77.4
77.2
59.5
61.2
62.9
64.4
65.2
65.7
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- pre-training strategy (see section 2.3 Details are discussed in section 3.2 and shorter ablation study on multiple channels can be found in Appendix E.
6

---

Under review conference paper at ICLR 2022
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 !
We note that despite its very different and non-standard mathematical form, the performance of SPHERI- CAT. is comparable to CONTC, 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 SPHERI- CAL. For that reason, we stick with CONIC for the multi-channel experiments.
Overall, Figure jjustifies 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 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 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 maximizes their performance.
CITESEER
CORA
WIKICS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1
LIBLINEARR
55.3
64.4
67.8
68.7
69.8
70.9
63.6
68.8
71.5
74.1
75.0
76,0
72.8
73.6
74.9
75.4
76.1
76.3
2
LIBLINEARNR
54.5
65.0
68.6
64.4
65.1
75.7
78.2
75.0
76.2
3
KNN (K-11)
49.6
62.2
67.3
68.7
69.8
70.7
50.9
66.9
70.7
74.8
77.3
78.9
70.3
72.7
74.6
76.6
78.5
79.5
4
CONIC-2C
48.1
60.9
65.3
68.2
69.9
71.1
17.1
17.9
20.2
21.7
21.7
27.0
70.5
74.0
75.0
76.1
78.4
79.8
5
CONIC-2C-FT
53.5
57.4
65.5
69.1
70.8
71.0
17.4
20.1
18.4
20.8
22.0
25.8
71.8
73.9
75.3
77.6
78.0
80.1
PUBMED
ARXIV
PRODUCTS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1
LIBLINEARR
60.3
60.6
61.7
64.3
67.1
68.8
43.8
45.4
47.3
48.9
50.2
51.4
67.1
69.4
73.4
75.4
76.5
77.3
LIBLINEARRR
72.7
72.1
56.9
58.7
59.2
59.2
79.9
80
80.1
80.1
3
(NNN(K11)
73.5
74.7
75.4
76.3
77.3
78.3
54.7
57.3
59.2
60.9
62.6
64.3
80.7
81.9
83
84.1
85
85.9
4
CONIC-2C
75.2
75.3
76
76.4
76.8
76.8
58.6
60.7
62.6
64.1
64.9
65.4
83.5
83.8
83.9
84
5
CONIC-2C-T
73
75.9
76.1
76.5
77.4
77.2
59.5
61.2
62.9
64.4
65.2
65.7
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 (LIBILINEARRR and regularization (L)) 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 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 this previously used standard classifier
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.
PPPrrzzz 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.
7

---

Under review conference paper at ICLR 2022
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 METHOOS
In this section compare the RADIAL classifier with other methods. The goal of this section is not 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.
CITESEER
CORA-mod
WIKICS
CLASSIFIER
1%
8%
16%
32%
1%
2%
16%
32%
4%
8%
16%
32%
1
CONIC-2C
48.1
60.9
65.3
68.2
69.9
71.1
57.9
63.6
67.9
75.5
77.1
79.9
70,5
74.0
75.0
76.1
78.4
79.8
2
RANDWALK
60.7
65.0
67.1
70.0
71.3
73.0
68.5
72.8
77.4
79.6
81.9
83.1
21.3
32.2
42.6
63.8
73.7
79.1
3
GCN
41.3
44.5
55.9
60.5
65.8
68.9
15.3
16.3
16.6
16.3
16.0
16.8
65.1
69.1
72.7
76.4
78.0
79.0
NETMF
49.8
53.3
54.5
60.8
61.2
66.1
69.5
71.6
74.8
76.8
70.3
68.5
68.6
69.5
73.6
80.7
5
DEEP WALK
49.3
47.1
54.1
63.1
65.8
67.4
61.9
69.2
73.7
77.4
78.5
79.0
72.1
75.0
77.0
78.2
79.2
79.8
PUBMED
ARXIV
PRODUCTS
CLASSIFIER
8%
2%
16%
32%
4%
1
CONIC-2C
75.2
75.3
76.0
76.4
76.8
76.8
58.6
60.7
62.6
64.1
64.9
65.4
83.5
83.8
83.9
84.0
2
RANDWALK
66.8
73.0
77.0
79.4
80.8
81.8
32.3
41.3
52.2
60.9
66.0
69.3
79.1
83.8
85.3
86.7
87.9
89.0
3
GCN
69.0
72.8
75.3
77.3
79.1
80.3
56.8
60.1
62.1
63.6
64.3
64.9
NETMF
75.7
76.1
76.5
76.6
76.7
76.7
5
DEEP WALK
77.2
77.3
77.7
77.8
77.9
78.0
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 mode (Kipf & Welling 2017) and the RANDOM WALKER algorithm (harmonic label interpolation) (Grady) (2066). RRADOMWALKER is a con-aarmmeteric algorithm and it is much faster than all other methods. On the other hand, DREPWALK 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 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 de- veloped in (Koutis & Le 2019), such cases, graph modification can alleviate the problem. CoRA-mod is such a modified version of the CORA grapt Thus, the fact that CORA-mod gives rise to much better spectral embedding explains the failure observed for CORA in previous sections.
RANDOMWALKER has always 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 directly competitive to DEEPWALK and NETMF, for small fraction of runtime.
RANDOM WALOMEWALEER 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(lin the Appendix, we observe that the accuracy enhancement added by C&S correlates strongly with the training ratio. Figure also shows that an improved 'base" generally improves the final output of C&S.
*GCNs by design operate with node features; here we use one-hot vectors as suggested in (Kipf & Welling, 2017 CCoRA-mod used only for CONIC-2C. DEEPWALK and NETMF effectively work with modified graph.
8

---

Under review conference paper at ICLR 2022
4 HANDLING NODE FEATURES
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 ! 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 cases, except the CITESEER data set. These results are reported Figure
CITESEER
CORA
WIKICS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
7%
4%
8%
16%
32%
1 CONIC-2C
48.1
60.9
65.3
68.2
69.9
71.1
17.1
17.9
20.2
21.7
21.7
27.0
70,5
74.0
75.0
76.1
78.4
79.8
2
CONIC-2C+F
44.2
51.6
60.2
63.4
67.5
69.2
21.3
26.9
34.5
43.4
45.0
52.7
71.8
73.9
75.3
77.6
78.0
80.1
PUBMED
ARXIV
PRODUCTS
CLASSIFIER
1%
2%
4%%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
CONIC
75.2
75.3
76.0
76.4
76.8
76.8
58.6
60.7
62.6
64.1
64.9
65.4
83.5
83.8
83.9
84.0
2
CONIC 2C
75.6
76.7
79.7
80.7
82.4
85.4
60.0
61.5
64.7
65.7
67.7
68.6
83.5
84.6
85.4
85.7
Figure 5: Adding features 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 Figure 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 additional input the standard GCN. The outcome of this approach for the ARXIV data set is shown in Figure
1%
2%
4%
8%
16%
REGULARGGN
63.0
65.3
67.7
69.5
71.1
CONIC- BOMO-BD GCN
64.9
67.5
69.0
70.7
Figure 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 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 gagael-pprameeerizeed neural architectures that yield end-to-end trainable network embeddings. This is in stark contrast to the pre-GNN period, when the collec- tive focus was on the design of network embedding methods, with apparently little research devoted the downstream classification task. In this work argued that developing a better theoretical understanding of the geometric embedding opens up the fundamental research direction of designing better gcometry-awan for older algorithms, such
classifiers. This direction lead to surprising substantial improvements, 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.
9

---

Under review conference paper at ICLR 2022
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 117111777778 1783, 2006.
Aditya Grover and Jure Leskovec. Node2Vec: Scalable Feature Learning for Networks. In Proceedings of the 22Nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '16, pp. 355-864, New York, NY, USA, 2016. ACM. ISBN 978 1777--1-550 1-08-------33322-----0 4232-2. 2939754, URL http::ttt/// //oo: acm wrg /10 114./1939672....... 2239775
doi: 10.1 10.1145/2939672.
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.0000 [cs, stat), February 2021. URL http::tttt/t.....t//ee
2005 00687 arXiv: 0005.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 http:tttt/p/eeeeeeeeeeee
net wwtp://eeeetenaaaaeeeeeeee
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: https://cpen.eeieew net/
forum?1d=SJUAayYY0
Andrew V Knyazev. Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Precondi- tioned Conjugate Gradient Method. SIAM Journal on Scientific Computing, 23 2001. doi: 10.1 1577//006488770036666
URL BRLhhtps::// ottp:///.....rr1...11111 017.0//0111111110022222220632220
Ioannis Koutis and Huong Le. Spectral Modification of Graphs for Improved Spectral Clustering. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alc Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4859-4868, 2019. URL htwps: http:///oocceeeeeeeeee ngs nwurips. cc/ paper/2019/ -wt-96666bbbrrrcccc html
htt//bbb6000 2tt.be0033eee9999dddaeaaaaaa
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):163--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.ge 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-Verlee Verlag. ISBN 978-3-642 242-243--33
10

---

Under review conference paper at ICLR 2022
A. Ng. Michael 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 Knowledge Discovery and Data
Mining, KDD '14, pp. 701-710, New York, NY, USA, 2014. ACM ISBN 978-1-4503-29555 2956-9 doi: 2623732
10.11452222333.2222223
BRLbttp::/ /tt::///oooioe/ wcm.mc...mccccccmmmmmmmmmmmm.cc. org/ 10. 11411114222332
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network Embedding Matrix Factorization: Unifying Deep Walk, 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- -500--5-00---8--0 doi: 10.11453119952231599700 URL https:
7/dl. acm http:/oo/10000 1145/ 0115511555522 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, CA, USA, February 5-9, 2018, pp. 459-467, 2018b. doi: 10. 10.1145/3159952.11577777 URL https: //doi. 1145/ 3159652 3159706
Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-900 August 2000. ISSN 0162-8828. doi: 10. 11199/94.4866888. |tL //oi: org skg/10.0 110911101110 868688 Place: Washington, DC, USA Publisher: IEEE Computer Society.
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 Informa- tion 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- --888-3-6--3-3-9--3 doi: 10.1145/2736277. 27.211299. URL htR.tttts:://// htt.htttss///d.acm.. acm acc..////oooo/////00///////
1145/27362 2241224455
Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowl-
edge Discovery, 23(3):447-47) November 2011. ISSN 1384-5810. 1573-756X. doi: 10.1007/ s10618-010-0210-x URL http:///ip//kk spri nger com 100000000010--000020222
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. VERSE: Versatile Graph Embed- dings from Similarity Measures. In Proceedings of the 2018 World Wide Web Conference World Wide Web - WWW '18, pp. 539 539-548, Lyon, France, 2018. ACM Press. ISBN 978- 1-88-11-503-5666 8. doi: 10. ci taattatiinn.. ottp:///cc.....oo..oooooooooaaa. 788
3178876.31 0117766..162200 86120. URL http:: //ll amm
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, 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. for htth::ps: openreview wttp://wwwweee/oooriiiiiie--e fww.m:iddr-JMpiika....
Ulrike von Luxburg. A Tutorial on Spectral Clustering. CoRR, abs/0711.0, 2007, URL http::/arxivv org/abs/0711.00
11

---

Under review conference paper at ICLR 2022
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 connected grapt self-loops are also removed. For all datasets, treat the graphs undirected and only consider the largest connected component. Table Talee[sumee summarizes the number vertices, edges and classes of these largest connected components.
Dataset
CITESEER
CORA
WIKICS
PUBMED
ARXIV
PRODUCTS
3,327
2,708
11,701
19,717
169,343
2,449,029
VI
2,120
2,485
11,311
19,717
169,343
2,385,902
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
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. RCS-CLASSIIY (algorithm D. we take = 2 nc, where ne is the number of classes. In non-reported experiments have found that further increasing the number of dimensions slightly increase accuracy, but we take a choost-consistent decision to make the dimension proportional to number of clusters. The Random Walker algorithm does not have any hyperparameters eters. 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 Deep Walk is set to be 2 e ne; this deviates from the recommendation but it is added here for direct comparison with the setting for RADIAL.
learnable param-
Variance. We note that we omit information on the standard deviation of accuracy over random splits and random initializations. This 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 competitive, and thus they are not included here.
embedding. The results
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, closely related algorithm, motivates the experimental study of the RANDOMWALLR hyperparameters or trainable parameters. We see that in multiple cases RANDOMWALKER WALKER is viable alter- native to other models, especially considering that with proper implementation using Laplacian solvers, LANDOMWALKO is by far faster than all other methods in Table ??. The C&S process not applicable the output of R RANDOMWALKER for certain concrete technical reasons, but worthy research topic it modify RANDOM WALKER way that would enable the application of C&S, in order to enhance its performance.
algorithm, the strengths of which include the fact that it does not have any
"One can use the node features connect these smaller connected components. We avoid this practice in order stick with the decision to only graphic data.
12

---

Under review conference paper at ICLR 2022
C EFFICIENT COMPUTATION
We discuss the computation of eigenvectors of the generalized eigenvalue problem Lx ADx. Several works compute eigenvectors using implementations ARPACK (Lehoucq et al. 1997) in libraries for sparse matrix algebra, in Matlab, Python, or Julia (e.g. (Huang al., 20211). Social networks usually have eigen- value distributions that are 'friendly' to power methods (that are used in ARPACK) in the sense that they can converge in reasonable amount of time. However that is not guaranteed, and in practice convergence be much slower than possible. Fast convergence can presently be guaranteed only via using inverse- power algorithms, i.e. algorithms that use approximations the inverse of the Laplacian, often used as precondi- tioners. In this work we use the preconditioned eigensolver LOBPCG (Knyazev (200T) with the CMG pre- conditioner (Koutis et al. 201T). Besides its stronger theoretical properties, the particular implementation also significantly faster in practice, even on social networks.
C.I INITIALIZATION AND CONVERGENCE
Figure 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

---

Under review conference paper at ICLR 2022
D THE ALGORITHM
Algorithm 1 Radial-Conic-SSheriiaal Classifier with K channels
1: Input: x E <RI eigenvector embedding, type: 'Linear' or 'Conic"
Output: y Rxxee; is the number of classes
3:
4: Trainable parameters:
5: R, E R&xxe, for I,... K, where K is hyperparameter
6: E Renene
7: 8 Rixne
8:
9: function (CS-CLASSIFY(2)
10: for i=1 do to K
11:
y xR
[optional] bi radial projection
12:
//1lv/12
13:
end for
14:
;u::...yKK
concatenate
15:
type 'Conic' then
16:
Warm = norm W, dim 1)
D Wnrm E R lxne; vector of 2-norms of columns of W
17:
y = yW Wnrm- cos(B)
* denotes pointwise multiplication
18:
else if type 'Linear' then
19:
y = yW +
20:
else if type 'Spherical' then
21:
y = 32 (W K-nex| y)
squaring is entry-wise
22:
end if softmax(1))
23:
24:
end function
14

---

Under review conference paper at ICLR 2022
E MISC EXPERIMENTS
E.I 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, has negative impact on accuracy.
We made the Reduce layer non-trainable and orthogonal (as suggested in Lee et al. (014a)). This has significantly negative impact accuracy.
We have added regularization term || R² Ille 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 positive impact on accuracy. On specific fixed training set for the ARXIV recorded accuracies are shown in Figure 8
ARXIV with multiple Channels
#nchannels
1
2
3
6
accuracy
64.2
65.7
66.3
66.7
66.8
66.9
Figure 8: An experiment with multiple channels
15

---

Under review conference paper at ICLR 2022
F ALL RESULTS WITH CORRECTION AND SMOOTH
CITESEER
CORA
WIKICS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
56.4
50.3
51.0
54.3
57.4
58.4
16.7
23.9
25.7
28.6
26.8
29.0
29.7
34.3
35.0
37.7
35.8
35,9
NO-RADIAL
64.5
70.4
81.4
52.1
54.8
60.0
71.5
No-REDUCE
49.0
63.6
66.9
68.9
68.9
71.1
18.9
18.8
18.8
17.5
25.5
27.4
69.4
71.7
73.9
74.8
75.8
76.2
NO-REDUCE+CS
57.6
64.9
68.7
70.6
72.2
74.1
69.3
73.6
75.2
77.9
82.7
84.8
69.2
73.6
76.9
77.6
80.0
81.8
CONIC
45.8
59.6
64.6
67.6
69.7
70.7
16.0
19.0
19.0
22.7
24.4
26.7
69.9
73.2
75.0
75.4
78.2
78.7
COSICICS
55.9
70.2
72.2
82.7
71.1
SPHERICAL
45.0
62.3
65.1
67.9
69.0
70.9
18.1
19.6
22.3
24.5
26.3
28.1
68.8
73.2
75.3
76.9
78.5
79.0
5
CONIC-2C
48.1
60.9
65.3
68.2
69.9
71.1
17.1
17.9
20.2
21.7
21.7
27.0
70.5
74.0
75.0
76.1
78.4
79.8
CONIC-2CICS
55.9
63.5
73.7
56.9
82.0
70.3
76.9
80.3
CONIC PT
53.5
57.4
65.5
69.1
70.8
71.0
17.4
20.1
18.4
20.8
22.0
25.8
71.8
73.9
75.3
77.6
78.0
80.1
7
R
55.3
64.4
67.8
68.7
69.8
70.9
63.6
68.8
71.5
74.1
75.0
76.0
72.8
73.6
74.9
75.4
76.1
76.3
LIBLINEAR-NR
54.5
56.7
65.0
68.6
70.4
71.1
64.4
65.1
71.0
75.7
78.2
78.3
67.5
71.0
75.0
76.2
76.9
77.0
KNN
49.6
62.2
67.3
68.7
69.8
70.7
50.9
66.9
70.7
74,8
77.3
78.9
70.3
72.7
74.6
76.6
78.5
79.5
KNN+CS
57.8
62.9
65.9
67.8
69.5
72.1
71.7
75.2
76.3
79.9
82.4
84.4
73.2
74.6
76.4
78.7
80.4
81.4
10
RANDWALK
60.7
65.0
67.1
70.0
71.3
73.0
68.5
72.8
77.4
79.6
81.9
83.1
21.3
32.2
42.6
63.8
73.7
79.1
41.3
44.5
55.9
60.5
65.8
68.9
16.3
16.6
16.3
16.0
65.1
72.7
76.4
78.0
79.0
12
NETMF
49.8
54.5
60.8
61.2
66.1
69.5
71.6
74.8
70.3
68.6
69.5
73.6
80.7
13
DETP WALK
49.3
47.1
54.1
63.1
65.8
67.4
61.9
69.2
73.7
77.4
78.5
79.0
72.1
75.0
77.0
78.2
79.2
79.8
PUBMED
ARXIV
PRODUCTS
CLASSIFIER
1%
2%
4%
8%
16%
32%
1%
2%
4%
8%
16%
32%
19
2%
4%
8%
16%
32%
1
NO-RAAIAL
53.2
53.6
59.0
55.2
58.8
58.5
21.2
26.5
26.0
24.6
25.8
25.1
27.9
28.7
31.1
28.9
RODIAL 4CS
77.9
2
No-REDUCE
63.5
64.6
63.4
64.3
65.2
64.0
47.6
48.5
49.0
49.3
49.3
49.4
66.6
66.7
66.6
66.7
NO-REDUCE+CS
76,0
77.7
79.4
80.5
81.4
82.3
56.4
61.0
64.8
67.4
69.6
71.3
84.8
85.7
86.5
87.4
75.6
75.4
76.0
76.6
76.6
76.6
58.4
60.5
61.3
62.1
62.4
62.5
80.9
80.9
80.9
81.0
CONICHCS
76.6
77.4
78.3
79.9
81.0
82.3
61.0
63.3
65.4
67.0
69.5
71.3
85.6
86.8
4
SPHERICAL
75.0
75.0
75.5
76.0
76.1
76.3
57.8
60.5
61.9
63.0
63.7
63.8
82.1
82.3
82.4
82.5
5
CONIC-2C
75.2
75.3
76.0
76.4
76.8
76.8
58.6
60.7
62.6
64.1
64.9
65.4
83.5
83.8
83.9
84.0
CONIC-2CICS
76.6
77.4
79.9
82.3
63.3
65.6
69.6
CONIC-2C.P
73.0
75.9
76.1
76.5
77.4
77.2
59.5
61.2
62.9
64.4
65.2
65.7
7
LIBUINAARR
60.3
60.6
61.7
64.3
67.1
68.8
43.8
45.4
47.3
48.9
50.2
51.4
67.1
69.4
73.4
75.4
76.5
77.3
LIBLINEAR-R
73.3
73.4
72.7
72.1
71.6
71.5
56.9
58.7
59.2
59.1
59.2
59.2
79.9
79.9
80.0
80.1
80.1
80.1
KNN
73.5
74.7
75.4
76.3
77.3
78.3
54.7
57.3
59.2
60.9
62.6
64.3
80.7
81.9
83.0
84.1
85.0
85.9
KNN+CS
76.0
76.6
77.9
79.4
80.7
81.9
59.5
62.4
64.8
66.8
68.7
70.6
10
RANDWALK
66.8
73.0
77.0
79.4
80.8
81.8
32.3
41.3
52.2
60.9
66.0
69.3
79.1
83.8
85.3
86.7
87.9
89.0
69.0
72.8
75.3
77.3
80.3
56.8
60.1
62.1
63.6
64.3
64.9
12
NETMF
75.7
76.1
76.5
76.6
76.7
76.7
13
DEEP WALK
77.2
77.3
77.7
77.8
77.9
78.0
Figure 9: Summary of all results
16


Reviews:
[{"review_id": "w-1kmZGOE20", "reviewer": "Reviewer_L1xu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The transfer of geometric intuition from Lee at al. leads to an improved pipeline for supervised spectral-based classification, and is a nice insight. It could spark further research in this direction, by building on strong theoretical foundations.\n\nIt is quite surprising to see that such a supervised spectral clustering pipeline attains higher accuracy than a number of sota methods which were thought to be miles away better in performance, which also has lead to spectral methods being dropped from the comparison baselines in most works. This work demonstrates that with the right pre-processing steps in place (like the radial projection onto the unit sphere), spectral methods could be brought back to the comparison board.\n\nThe experimental results are convincing, though they could be made more complete, but it is enlightening to observe such performance of from a spectral based methods.  \n\nIt would be good to see a comparison of performance for synthetically generated data, for example by considering standard stochastic block models. ", "summary_of_the_paper": "This paper puts forth a methodology for supervised spectral clustering, by leveraging existing theoretical foundations of spectral clustering, in particular drawing insights from seminal works such as Lee at al on multi-way Cheeger inequalities.\n", "summary_of_the_review": "An interesting paper which could open further avenues of research at the intersection of spectral methods and neural-based approaches.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "txDpHXqNf8H", "reviewer": "Reviewer_7yDC", "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": "Strengths: The paper is mostly well written, and the main thrust of the paper is an important point for researchers in this area: simple, but well structured and theoretically motivated graph models can perform surprisingly well against larger, more complex models, and can even outperform them. Also, the empirical results are presented honestly, which is greatly appreciated.\n\nWeaknesses: The main weaknesses of the paper are: (1) a lack of direction and (2) an insufficient distinction from previous works.\n\nIs the point of the paper to alert the community to the previous work of Lee et al. 2014, or is it to emphasise that such models have impressive empirical performance compared with other methods? If it is the former, then Section 2 can be improved by clearing up notation and errors as well as more firmly delineating where this paper diverges from existing work, which would help with point (2) as well. Is Section 2.1.3 the insight of the authors or does it also summarise previous works?\n\nIf it is the latter, then I do not find the argument of the paper either novel or convincing. The results demonstrate that the addition of correction and smooth, the essential point of Huang et al. 2021, consistently has the largest impact on the accuracy. A counter argument to the paper’s results is that the node classification tasks in Citeseer, Cora, and Pubmed are in a way too simple, being well described by local smoothing of the labels. If that is the case how does this differ from the point of Huang et al.? Recent GNN research has focused on topics such as incorporating additional node and edge information, which the proposed method could attempt to incorporate, but is not included in the empirical section as the authors choose to focus solely on the connectivity information. How do the proposed models compare when such information is considered? How can these data be incorporated into the models in a principled manner? The other direction for more challenging graph problems is in inter-domain settings, where there are multiple graphs (such as the molecule classification benchmarks) or in finding correspondences between nodes in situations where the graph has been modified in some way (by pruning or modifying the ambient embedding). Unfortunately, the proposed methods would fail in these situations. However, this would be a very interesting direction for the authors to pursue in the future. \n\nWhat exactly is ‘neural’ about the additional classifiers? Such a description seems to detract from the main claim, and does not seem justified. Is it simply that there are two steps: the spectral embedding and the classification? Is it the inclusion of the K independent channels?\n\nNotation and definitions: \n\na) the definition of vol(.) should be consistent in its indexing.\n\nb) my preference would be to reserve degree of a vertex for the unweighted count of edges, and call what is in the paper the weighted degree.\n\nc) I am familiar with the definition of conductance, but have not seen the notation of cap(.) before, a brief definition would likely improve clarity.\n\nd) I understand what the authors are attempting to communicate about a partition of the vertex set, but as written the statement is incorrect: the S_i must be disjoint as well.\n\ne) Final sentence of Conic in Section 2.2, the second ‘Conic’ should be ‘Linear’.\n\nEmpirical Results: \n\na) Why are there empty entries for the proposed models in the Products results? Do the methods fail at this scale or are there other problems? \n\nb) Inclusion of the results of GCN, NetMF, and DeepWalk in the Arkiv and Products tasks would aid the paper as these are much larger and could be treated as a more challenging comparison. Is there a reason these are not included?", "summary_of_the_paper": "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.", "summary_of_the_review": "I appreciate the main point of the paper, that simple models can perform surprisingly well on standard graph benchmarks, and I find such methods interesting. However, in its current form, the paper insufficiently distinguishes itself either from existing theoretical works such as the cited Lee et al., or the essential empirical point of Huang et al., and so I recommend rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "l4wmbQ1qLBA", "reviewer": "Reviewer_GXsL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "==STRENGHTS==\n\nBACKGROUND\nI have found the theory well written and self-contained. I think a non-expert could find most of the information in the paper, and I appreciate this aspect. \n\nINSIGHTS\nThe geometrical insights are didactical and well communicated. The conclusion given by the experiments looks interesting and valuable for future practitioners, while I think a synthesis would be beneficial for the reader.\n\n==WEAKNESSES==\n\nNOVELTY AND CONTRIBUTION\nThis work does not present any particular methodological novelty, and I see this paper more as an experimental one. I think such kinds of papers are valuable and deserve attention, but in this specific case, I think the contribution provided by the analysis is limited in the following aspects:\na) there are no specific comments for performances on different datasets; for example, why on CORA does the \"Conic\" perform poorly without \"+CS\"? Why on \"arXiv\" outperforms all other methods? Which are the peculiarities of the different datasets? I see that such analysis may be complicated given the dimensionality of the graphs, but I think that even some insights given by further investigation would be important\nb) the experiments lack variety in the applicative domain; for example, spectral clustering has obtained significant attention in the 3D field. It would be interesting to apply the techniques to at least one geometrical dataset that is more prone to have symmetries. These latter are the main limitations of spectral methods that do not consider additional features and should be somehow discussed in the paper to provide a complete overview.\nc) I think that considering only the quantitative performances tells only part of the story, and a deeper analysis should be provided (e.g., error localization, timings)\n\nPRESENTATION\nApart from the background, I find the rest of the paper a bit verbose, and that could be improved in its communication. For example, visualization of spectral embeddings and a pipeline scheme would help a lot in diving into the paper. Also, It is not comfortable to move back and forth to check the results of the final table: I suggest splitting it in two and locate near the discussion text. I think the visual aspect of the paper could be significantly improved and serve as support to the analysis.", "summary_of_the_paper": "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.", "summary_of_the_review": "While I like the general idea and I appreciated the effort in explaining the underlying theory, I think there is no significant methodological novelty and also a significant lack in the experimental and analysis settings. I do not consider it ready for publication in the present state.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KPNdS-gafvn", "reviewer": "Reviewer_YsLB", "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": "Strengths:\n1. This paper is very clear and easy to follow and understand.\n2. It conducted solid experiments to show the performance differences for each method.\n\nWeakness:\nIt is very difficult to position and evaluates this paper. Though it concretely introduces lots of methods, the paper itself does not propose any new methods or insights, such that it does not qualify as a \"new-method\" paper. As for the \"review & benchmark\" paper, this paper lacks a more detailed exploration of this topic and the experimental validation is rather poor compared with review papers. Still, I will treat this paper as a review paper and below are some of my unuseful comments.\n\n1. The mathematical background could be more concrete. Instead of briefly introducing the cut and conductance, the author would also show the equation of graph Ncut, which reveals the power and need of conducting spectral clustering for node embedding.\n\n2. While introducing related methods, it would be better to use mathematical equations to showcase their insights and improvement compared with previous methods.\n\n3. The \"orthogonal projection\", \"radial projection\" and \"geometric partitioning\" can be unified in the classifier section. All these projections could be considered as the preprocessing for classifiers. The author could consider introducing them in the neural classifier part altogether. \n\n4. Though section 2.1.3 talks about clustering from the geometric perspective. But it does feel disconnected in this paper. I don't see the benefit here.\n\n5. About the efficient computing of the eigendecomposition, the author could consider eigengame (ICLR 2020). \n\n6. For a more comprehensive experiments. The author could consider compare spectral clustering embedding with other embedding. Like node2vec, and more graph neural network based methods like GAT, GraphSage et al.\n\n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper is very well written. But it lacks originality and also did not derive new insights.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AFiUQf9FTNK", "reviewer": "Reviewer_os5L", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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**. This paper investigates the use of spectral clustering-based approaches for node classification in graph data. It extends analysis of spectral clustering in Lee et al (2014) including the key steps of spectral embedding, orthogonal projection, radial projection, geometric partitioning.  Overall this paper provides a clear and thoughtful presentation the spectral clustering-based methods. The clarity and care the authors put into understanding each component of the algorithms is a key merit of the paper. \n\n**Merits**. This paper does an excellent job in its thorough investigation of these spectral clustering-based approaches. Not only does this provide an array of competing methods for future work, but also provides for a better understand of the impact of various components of related models. I think this kind of careful analysis is needed, especially as the number of such methods for node classification / related problems increases. Suggesting such a critical look at past work and introduction of baselines from decades prior (e.g. RandomWalker (Kemp, 2006)), I think is fantastic an important contribution.    \n\n**Concerns**. Despite these merits, I have following concerns about the paper. \n* While there is a careful analysis of the different design decisions/performance tradeoffs, I feel that there is only a limited understanding about what are the properties of the datasets that lead to these decisions/performance differences. I.e., what is about the Arxiv data that makes Conic more effective? Is it just the dataset size? Other properties? Why is Knn competitive on some dataset, but then much worse that sota on others (e.g. cora 1%)?\n* While these spectral clustering methods are simpler / more scalable than some competing GCN-based approaches. I feel the (train or test) efficiency / accuracy trad-offs are not sufficiently explored? I.e. when would be scenarios/considerations that someone would chose one of these approaches? \n* I think the paper would be improved with some discussion of tradeoffs empirically from a wider variety of GCN approaches. \n\n**Minor Notes / Typos**:\n\n* Top Table of Table 1: RandomWalker Cora 4% seems to be better than other methods, shouldn't it be bolded? Same for knn in WikiCS 1%?\n* Intro: \"spectacular comeback\" is perhaps a bit informal/colloquial? \n* 2.1: \"Along it\" phrasing seemed confusing to me.\n* 2.1.2: There seem to be four components rather than \"three\" as noted?\n* Top Table of Table 1: 16 % and 32% seems larger font than others\n* Table 1 has a lot of results. and located at the end of the paper as it is, is somewhat difficult to navigate, especially as reading through the experiments section. Perhaps there is a way to include it at least before the end of the text of the section? \n* Several of the citations in the text are missing the year.\n\n\n\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "This is a thoughtful investigation spectral clustering in classification problems for graph-based data. However, there are several concerns regarding missing forms of analysis such as deeper investigations into why certain methods work well on certain datasets.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There was some discussion on this paper, both with the authors and between reviewers. On the one hand, there is a general agreement that the empirical results suggesting that spectral clustering-based method can be competitive with SOTA methods on node classification benchmark is an interesting result. One the other hand, reviewers did not find a significantly novel contribution in the methodology proposed, and found that the empirical evaluation lacks depth and details to be really informative (eg, to understand why some methods work or not on some benchmarks). There is therefore a consensus that the paper is not ready for ICLR in its current form, but we hope that the reviews and discussion will help the authors prepare a revised version in the future.
Decision: Reject