OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization
Authors: Hengrui Zhang
Shen Wang
Soji Adeshina
Vassilis N. Ioannidis
Jiani Zhang
Xiao Qin
Christos Faloutsos
Da Zheng
George Karypis
Philip S. Yu
Venue: Submitted to ICLR 2023 (2023)

Abstract: Graph Neural Networks (GNNs) are currently dominating in modeling graph-structure data, while their high reliance on graph structure for inference significantly impedes them from widespread applications. By contrast, graph-Regularized MLPs (GR-MLPs) implicitly inject the graph structure information into model weights, while their performance can hardly match that of GNNs in most tasks. This motivates us to study the causes of the limited performance of GR-MLPs. In this paper, we demonstrate that node embeddings learned from conventional GR-MLPs suffer from dimensional collapse, a phenomenon in which the largest a few eigenvalues dominate the embedding space, and thus the expressive power is constrained. We further propose ORTHO-REG, a novel GR-MLP model, to mitigate the dimensional collapse issue. Through a soft regularization loss on the correlation matrix of node embeddings, ORTHO-REG explicitly encourages orthogonal node representations and thus can naturally avoid dimensionally collapsed representations. Experiments on traditional transductive semi-supervised classification tasks and inductive node classification for cold-start scenarios demonstrate its effectiveness and superiority.

Under review as a conference paper at ICLR 2023
ORTHOREG: IMPROVING GRAPH-REGULARIZED MLPs VIA ORTHOGONALITY REGULARIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) are currently dominating in modeling graph- structure data, while their high reliance on graph structure for inference significantly impedes them from widespread applications. By contrast, Graph-regularian (GR-MLPs)) implicitly inject the graph structure information into model weights, while their performance can hardly match that of GNNs in most tasks. This moti- vates us to study the causes of the limited performance of GR-MIPs. In this paper, we first demonstrate that node embeddings learned from conventional GR-MLPs suffer from dimensional collapse, phenomenon in which the largest few eigen- values dominate the embedding space, when a linear encoder is used. As a result of this the expressive power of the learned node representations is constrained. We further propose ORTHO REG, a novel GR-MLP model, to mitigate the dimensional collapse issue. Through soft regularization loss the correlation matrix of node embeddings, ORTHO-REG explicitly encourages orthogonal node representations and thus can naturally avoid dimensionally collapsed representations. Experiments on traditional transductive semi -upervipe classification tasks and inductive node classification for cold-start scenarios demonstrate its effectiveness and superiority.
MLPs
INTRODUCTION
Graph Machine Learning (GML) has been attracting in- creasing attention due to its wide applications in many real- world scenarios, like social network analysis (Fan al., 2019), recommender systems (van den Berg et al., 2017; Wu al., 2019b), chemical molecules (Wang et al., 2021: Stärk et al., 2022) and biology structures. Graph Neural Networks (GNNs) (Kipf & Welling. 2017: Hamilton al., 2017: Velickovic et al., 2018; Xu et al., 2019) are currently the dominant models for GML thanks to their powerful representation capability through iteratively aggregating information from neighbors. Despite their successes, such an explicit utilization of graph structure information hin- ders GNNs from being widely applied in industry-level tasks. On the one hand, GNNs rely on layer-wise mes- sage passing to aggregate features from the neighborhood, which is computationally inefffcieett during inference, espe- cially when the model becomes deep (Zhang et al., 2021), I). On the other hand, recent studies have shown that GNN models can not perform satisfactorily in cold-start scenar- ios where the connections of new incoming nodes are few or unknown (Zheng et al., 2021). By contrast, Multi-Layer Perceptrons (MLPs) involve depen- dence between pairs of nodes, indicating that they can infer much faster than GNNs (Zhang et al., 2021). Besides, they can predict for all nodes fairly regardless of the numbers of connections, thus can infer more reasonably when neighborhoods are missing (Zheng et al., 2021). However, it remains challenging inject the knowledge of graph structure information into learning MLPs.
Orthottglous)
GRAND
GGN
MLP
Inference
Figure 1: As an MLP model, our method performs even better than GNN mod- els on Pubmed, but with a much faster inference speed. GRAND (Feng al., 2020) is one of the SOTA GNN models on task. Circled markers denote MLP baselines, and squared markers indicate GNN baselines.
One classical and popular method to mitigate this issue is Regularzee MLPs (GR-MLPs in short). Generally, besides the basic supervised loss (e.g., cross-entropy), GR-MLPS employ

---

Under review as a conference paper at ICLR 2023
an additional regularization term on the final node embeddings or predictions based the graph structure (Ando & Zhang, 2006; Zhou et al., 2003; Yang et al., 2021; Hu et al., 2021). Though having differentt formulations, the basic idea is to make node embeddings/prediccie the graph structure. Even though these GR-MLP models can implicitly encode the graph structure information into model parameters, there is still a considerable gap between their performance compared with GNNs (Ando & Zhang, 2006; Yang et al., 2021). Recently, another line of work, GNN-t--LL knowledge distillation methods (termed by KD-MLPs) (Zhang et al., 2021; Zheng et al., 2021). have been explored to incorporate graph structure with MLPs. In KD-MLPs, a student MLP model is trained using supervised loss and knowledge-distiee distillatiinn loss from a well-trained teacher GNN model. Empirical results demonstrate that with merely node features input, the performance of KD-MLPs can still match that of GNNs as long as they are appropriately learned. However, the 2-step training of KD-MLPs is undesirable, and they still require well-trained GNN model as a teacher. This motivates us to rethink the failure of previous GR-MLPs to solve graph-related applications and study the reasons that limit their performance.
smoothed over
Presented work: In this paper, we first demonstrate that node embeddings learned from existing GR-MLPs suffer from dimensional collapse (Hua et al., 2021; Jing et al., 2022), phenomenon that the embedding space of nodes is dominated by the largest (a few) eigenvalue(s). Our theoretical analysis demonstrates that the dimensional collapse in GR-MLP is due to the irregular feature interaction caused by the graph Laplacian matrix (see Lemma 1). We then propose Orthogonality Regularization (ORTHO-REE in short), novel GR-MLP model, to mitigate the dimensional collapse issue in cemi-supervised node representation learning tasks. The key design of ARTHO-REG is to enforce an additional regularization term on the output node embeddings, making them orthogonal so that different embedding dimensions can learn to express various aspects of information. Besides, ORTHO- -EG extends the traditional first-order proximity preserving target to more flexible one, improving the model's expressive power and generalization ability to non-homophily graphs. We provide a thorough evaluation for ORTHO- REG on various node classification tasks. The empirical results demonstrate that ORTHO-RES can achieve competitive or even better performance than GNNs. Besides, using merely node features to make predictions, ORTHO-RES can infer much faster on large-scale graphs and make predictions more reasonable for new nodes without connections. In Fig. 1 we present the performance of ORTHO- REG compared with GNNs and other MLPs on Pubmed, where ORTHO- REG achieves SOTA performance with the fastest inference speed.
We summarize our contributions as follows:
1) We are the first to examine the limited representation power of existing GR-MLP models from the perspective of dimensional collapse. We provide theoretical analysis and empirical studies to justify our claims.
2) To mitigate the dimensional collapse problem, we design a novel GR-MI GRM model named ORTHO-REG. ORTHO-REC encourages the node embeddings to be orthogonal through explicit soft regularization, thus can naturally avoid dimensional collapse.
3) We conduct experiments on traditional transductive semi- superviee node classification tasks and inductive node classification under cold-start scenarios on public datasets of various scales. The numerical results and analysis demonstrate that by learning orthogonal node representations, ORTHO-REE can outperform GNN models on these tasks.
BACKGROUNDS AND RELATED WORKS
2.1 PROBLEM FORMULATION
We mainly study general semi-super node classification task on single homogeneous graph where we only have one type of node and edge. We denote graph by g = (V,E), where V is the node set, and È is the edge set. For a graph with N nodes (i.e.. [V] = N), we denote the node feature matrix by X E NDD the adjacency matrix by A E N In semi-supervised node classification tasks, only a small portion of nodes are labeled, and the task is to infer the labels of unlabeled nodes using the node features and the graph structure. Denote the labeled node set by V and the unlabeled node set by DV then we have VL n ye = Ø and V U D = V.
Denote the one-hot ground-truth labels of nodes by Y E R NxC, and the predicted labels by Y. One can learn node embeddings H using node features X and adjacency matrix A, and use the
2

---

Under review as a conference paper at ICLR 2023
embeddings to generate predicted labels Y. For example, GNNs generate node representations through iteratively aggregating and transforming the embeddings from the neighbors and could be generally formulated as H fo(X, .A). Then linear layer is employed on top of node embeddings to predict the labels Y = go (.). The model could he trained in an end-to-end manner by optimizing the cross-entropy loss between predicted labels and ground-truth labels of labeled
nodes: Ceu = Ezent (Y Y = Σ (y:: 9:). Note that GNNs explicitly utilize the graph
iEVE
structure information through learning the mapping from node features and graph adjaceney matrix to predicted labels. However, due to the limitations introduced in Sec. 1 (inefficiency at inference and poor performance for cold-start nodes), we seek to learn an MLP encoder, i.e., H = (x) that only takes node features for making predictions.
2.2
GRAPH-REGULARIIEE MLPs
MLPs (GR-MLPs in short) implicitly inject the graph knowledge to the MLP model with an auxiliary regularization term on the node embeddings/prrdictionss over the graph structure (Zhou et al., 2003; Yang et al., 2021; Hu et al., 2021). whose objective function could be generally formulated as: L Loup + >Lreg: where Lreg = E(H, A) or E(Y, A). The most representative graph regularization method, Graph Laplacian Regularization (Zhou et al., 2003; Ando & Zhang, 2006), enforces local smoothness of embeeddings/predicctoons between two connected nodes: L(Y; A) = tr|Y LY]. where L = I A I- D 1/2 AD 1122 is the (symmetric normalized) Laplacian matrix of the graph. Note that Y can be replaced with H if one would like regularize node embeddings instead of predicted labels.
Later works apply advanced forms of regularization, like propagation regularization (P-Reg, Yang et al. (2021)), contrastive regularization (Hu et al., 2021), etc. Regardless of the minor differences, they are all based the graph homophily assumption that connected nodes should have similar representationn/laaels With the graph structure information implicitly encoded into the model parameters, GR-MLPs can improve the representative power of MLP encoders. However, their performances are still hard to match compared to those of GNN models.
Remark 1. (Differences from StaaphAAugeente MLPs). Though sound similar, regpl-eegularized MLPs(GGR-MPPS are totally different from Graph-augment augmented MLPs (GA-MLPs). Although trained with implicit graph structure regularization, GR-MLPs make predictions directly through the MLP model. By contrast, GA-MLPs, such as SGC ( (Wu et al., 2019a), APPNP (Klicpera et al., 2019), GFNN (NT Maehara, 2019) and SIGN (Rossi et al., 2020) explicitly employs the graph structure to augment the node representation generated from MLP model.
2.3 DIMENSIONAL COLLAPSE
Dimensional collapse (also known as spectral collapse in some work (Liu et al., 2019)) is a phe- nomenon in representation learning where the embedding space is dominated by the largest a few singular values (other singular values decay significantly as the training step increases). As the actual embedding dimension is usually large, the dimensional collapse phenomenon prevents different dimensions from learning diverse information, limiting their representation power and ability to be linearly discriminated. Jing et al. (2022) has analyzed the dimensional collapse phenomenon from a theoretical perspective and attributed it to the effect of strong data augmentation and implicit regularization effect of neural networks (Arora et al., 2019; & Telgarsky, 2019). Previous methods usually adopt whitening operation (Hua et al., 2021; Ermolov et al., 2021) to mitigate this issue, while such explicit whitening methods are usually computationally inefficient and thus are not applicable to GR-MLP where efficiency is much more important. In this paper, we demonstrate that node embed- dings learned from conventional Graph-Regulan Regularized MLPs also suffer from dimensional collapse. We provide a theoretical analysis on how it is caused and develop computationally efficient soft regularization term to mitigate
ISSUE DETECTION: DIMENSIONAL COLLAPSE IN GR-MLPS
In this section, investigate the reasons behind the weak representation power of previous GR- MLPs. In short, we find that node embeddings learned through traditional GR-MLPs (e.g., with graph Laplacian regularization (Ando & Zhang, 2006)) suffer from dimensional collapse, a phenomenon
3

---

Under review as a conference paper at ICLR 2023
which is first investigated in contrastive sulf--s learning (He & Ozay, 2022; Hua et al., 2021;
Jing et al., 2022). Generally speaking, dimensional collapse indicates that the embedding space is dominated by the largest few eigenvalues, limiting their representation powers. We then show that the dimensional collapse phenomenon does exist in the typical GR-MIPP model, Graph Laplacinn Regularization (Ando & Zhang, 2006), from both theoretical analysis and empirical justification. We provide further discussion on the impacts of dimensional collapse on downstream classification tasks in Appendix E. The objective function of Graph Laplacian Regularization for semi-supervised node classification tasks could be formulated as follows:
h;
h
C C= Lvent (YL, Y + Xtr[H LH
Σ iEVE
evens (y., D.) +1
Σ Ayl ijEV
12 (I)
VDa
VDj
We would like study the effect of the Laplacian regularization term Lrng tr[H LH] on H's embedding space through analyzing the eigenspectra of its auto-correlation matrix C = {Ca*) J, E Rdxd, where CRR' is defined as:
ENe
(h; hh(h, B)T iEV
CRK'' = VER
and Σ =
(2)
VI
Note that h EI h is the average node embedding vector, so E is the covariance matrix of H, and we denote C's eigenvalues in descending order by {Af, ",,,..))))
Theoretical Analysis. To simplify our analysis, we consider a simple single-layer Perceptron (linear) model the encoder to learn node embeddings, i.c., H XW (note that we validate the non-linear case empirically in the empirical justification part below). where W E RxD is the weight matrix (we further assume F D in this part for simplicity). The model (i.e., the weight matrix W) ) is optimized using stochastic gradient descent. Then we have the following lemma on the evolvement of the weight matrix's singular values.
Lemma 1. (Shrinking singular-space of weight matrix.) Consider the linear model above which is optimized with Freg = tr triHH' LH). Let P = X =Σ Lizx, and denote its non-ascending
i)
eigenvalues by (XP: AP. >P Denote the randomly initialized weight matrix by ( and the updated weight matrix at time by W (t), respectively. We further denote the non-ascending singular values of W at time t by Yo!w (4) Then the relative value of the smaller eigenvalues to the larger ones will decrease as t increases. Formally, 6." (t)
oW (t'(t))
o (t) <
(w((e) Vi<tiis Furthermore,
the following condition holds: X 2 2 X2
441 .... Xp then
W (1) 0, vi < and j 2 d W (I)
lim (1000
See proof in Appendix 1. Lemma 1 indicates that the singular values of W (in proportional to the larger ones) shrink as the training step increases. With Lemma 1, we can conclude the following theorem that reveals a dimensional collapse phenomenon under this condition:
Theorem 1. (Laplacian regularization leads dimensional collapse.) For the linear model above optimized with Graph Laplacian Regularization, the embedding space of nodes tends to be dominated by the largest a few eigenvalues. Specifically, if the covariance matrix of input features is an identity matrix, we have:
(t = 0, Vi d and j 2 d+1. (()
lim
(4)
See proof Appendix A.2. Theorem 1 reveals that with the effect of Graph I Laplacinn Regularization, the node embeddings suffer from dimensional collapse.N As the eigenspectrum is dominated by its largest few eigenvalues, the embedding space is narrow, leading to poor robustness and generalization ability when classified with linear classifiers (see more discussions in Appendix E).
Despite the analysis above, the exact evolving dynamics of node embeddings should be more compli- cated, as 1) the supervised cross- cross-entropy loss forces nodes of different classes to have distinguishable embeddings; 2) the encoder is usually an MLP with non-linear activations instead of a simple linear model. Therefore we further provide empirical results to show that dimensional collapse does exist.
4

---

Under review as a conference paper at ICLR 2023
A
A-00000 0.001
0.1
16:07
500
100
0
A= 0.001
27V
5 Elgervatu rank Epoch -
2
10
10a3
A 0.1
Eigenvauee rank
Elg Dieevvlue rank
NESum
Epoch 20
Epach 100
padd
Eigervalue Fank
Eigenvalue tank
Eigervalue Fant
40 Training epochs
Figure 2: Eigenspectra for node embeddings with different strengths Laplacian regularization À (the upper three figures), Figure 3: Evolving of NESum at different training epochs (the lower three figures). x-axis repre- as the training epoch increases, sents the index sorted eigenvalues and y-axis is the normalized with different regularization eigenvalue (the ratio to the largest one). The results are averaged factors. over 10 random initialization with 95% confidence intervals.
Empirical justification. We train a 3-layer MLP model using Eq. 1 on Cora dataset. The embed- ding dimension is set as 512 and the regularization works the output of the penultimate layer. To study the dimensional collapse phenomenon, we plot the decay of the eigenvalues of node embed- dings' correlation matrix with different strengths of regularization as the training epochs increase in Fig. 2 (here we only plot the top-8 eigenvalues for better visualization, while deferring the original results in Appendix C.4), from which we can easily see that: without Laplacian regularization, the top-C largest eigenvalues (where C' is the number of classes, and C = 7 for Cora) are easily preserved by the model. This means the model learns to discriminate between different classes. However, when we increase the Laplacian regularization factor X, we notice an increasing decay rate of top eigenvalues. As the top eigenvalues indicate the realistic embedding dimension that takes effect, conclude that a large decay rate degrades the importance of the spaces induced by other eigenvalues, thus leading to feature collapse issues.
Besides, employ normalized eigenvalue sum (NESum) introduced in He & Ozay (2022) a metric to measure the extent of dimensional collapse. Formally, NESum is defined as the ratio between the summation of eigenvalue and the largest one: NESum (1 {x())) ) - Σd_ XÇ / Intuitively, large NESum value indicates that the eigenvalues are fluently distributed, while a very small one indicates the dimensional collapse phenomenon (the largest eigenvalue becomes dominant).
In Fig. we plot the evolution of NESum with different regularization strengths. that 1) NESum decreases training goes on because the model learns to pay more attention to important features for downstream classification tasks. 2) NESum trained with purely cross-entropy loss converges to a high value., which is because the top-C' eigenvalues are preserved. 3) With additional Laplacian regularization, NESum decreases quickly and converges to a small value even the regularization factor À is small. The above observations demonstrate that Laplacian regularization leads to larger decay rate of top eigenvalues. The significant decay rate will make the learned representations less informative the model focuses much more the dominant eigenvalue rather than equal to the top eigenvalues.
observed
PROPOSED REMEDY: OVERCOMING DIMENSIONAL COLLAPSE VIA ORTHOGONALITY REGULARIZATION
4.1 EXPLICIT REGULARIZATION ON THE CORRELATION MATRIX
Our thorough analysis Sec. reveals that the poor performance of GR-MLPs could be attributed to less-expressive node representations (due to dimensional collapse). Specifically, establish that the eigenspectrum of the embeddings' correlation matrix is dominated by the largest eigenvalue (different dimensions are over-correlated.
5

---

Under review as a conference paper at ICLR 2023
In contrast to dimensional collapse, whitened representations have identity correlation matrix with equally distributed eigenvalues. Motivated by this, a natural idea should be enforeing a soft regularization term the correlation matrix of node embeddings, e.g,, minimizing the distance between C' and the identity matrix I:
Loorr_reg C - 111 - (1 c.) + - C 171 17)
(5)
Note that the on-diagonal terms Ca for all i, Eq. 5 is essentially forcing the off-diagonal terms of the correlation matrix to become zero, or in other words, making the embeddings orthogonal, so that different dimensions of node embeddings can capture orthogonal information. One may directly equip Eq. 5 with existing GR-MLPs for alleviating the dimensional collapse issue. However, we would like design a more general, flexible, and elegant formulation that can handle high-order connectivity and non-homophily graphs (Pei et al., 2020; Zheng et al., 2022). We then introduce ORTHO- REG, a powerful and flexible GR-MLP model, step by step.
4.2
MLP WITH ORTHO-REG
Similar to previous GR-MLPs, we first use an MLP encoder to map raw node features to the embeddings. This process can be formulated as H MLPx(X), where X {x:]] raw node features while H = (h.) i=1 is the embedding matrix.
The next question is what kind graph structure information is more beneficial. Previous GR-MLPs either resort to edge-centric smoothing (Zhou et al., 2003; Ando & Zhang, 2006) or node-centric matching (Yang al., 2021; Hu et al., 2021). While recent studies indicate that the node-centric method is more appropriate for node-level tasks edge-centrie methods overemphasize the ability to recover the graph structure (Yang et al., 2021). Inspired by this, we employ a neighborhood abstraction operation to summarize the neighborhood information guidance of the central node. Formally, for node i E V and the embeddings of its (up-to) 7 7'-hop neighbors {h, (1:2) (i), we can get the summary if its T- Tohop neighborhoods through pooling function s, Pool( } (1:T) The exact formulation of the pooling function could be flexible to fit graphs with different properties. However, here consider simple average pooling of node embeddings from different order's neighborhoods for simplicity, which can work in most cases:
S Σ A'H/L, where Á = AD-1
To make the node embeddings aware structural information, we employ the following regularization term the cros-correlation matrix of node embeddings H and summary embeddings S:
D CKk + +B
Lreg =
Σ 1=1
Cie. KGKK
where C {CRNr} } 1RDxD is the cross-correlation matrix of H and S. We show in the following theorem that with Eq. 7, the node embeddings will be locally smoothed and at the same time, prevent dimensional collapse:
Theorem 2. Assume T' I and H are free vectors. Let H" be global optimizer of Eq. 7, then H" smoothed over the graph structure and is orthogonal.
See proof in Appendix A.3. Finally, we can employ an additional linear layer to make predictions
Y LIN (H). Then the final objective function be optimized is:
L = Exent L v
Σ
Csa +
Σ K
where a, are trade-off hyperparameters balance the strengths of regularization.
Remark With a well-trained model, we can give prediction for an upcoming node with feature æ with y Ling(MI. (x)) quickly, and without the help of graph structure.

---

Under review as a conference paper at ICLR 2023
Table 1: Prediction accuracy of semi-supervised node classification tasks on the seven benchmark graphs. ORTHO-REG outperforms powerful GNN models and competitive Ml.--architectured baselines on 6 out of datasets.
Methods
Cora
Citeseer
Pubmad
Computer
Photo
CS
Physics
SGC
81,0+0.5
71.9=0.5
78.9+004
80,6+199
90.3++0.8
87.9+0.7
90.3+114
GNNs
GCN
82.2+0.5
71.6+0.4
79.3++0,3
82.9+2.1
91.8++0.6
89. 09.
91.9++1.2
GAT
83.020.7
72.5
79.0+0.3
82.3#1.6
91.410.8
90,540088
92.3:::55
KD-MLPs
GLNN
82.610.5
72.8:0.4
80.2:10.6
82.1
91.31:10
92.6111.0
93.3-1:0.5
MLP
59.71100
57.1=0.5
68.4:10.5
62.621.8
76.24:144
86,9:1100
89.41-0.7
Lap-Reg
60.3+2.5
58.6=2.4
68.7+1.4
62.6+2.0
76.4+111
87.9+0066
89.5+00.5
GR-MLPs
P-Reg
64.4+4455
61.1+2.1
72.3+117
68.9+3.3
79.7+3377
90.9++1.9
91.6++0.7
GraphMLP
79.5+..66
73.1=1044
79.7:t044
7.73+
90.1:10.5
90.3:10.66
91.6:10.8
N2N
83,210.4
73.310.5
80.910.4
81.41.6
90.9110.7
91.5.10.7
91.8.00.7
Ours
-RE
84.7:10.44
73.5:10.4
82.8-10.5
83.7-1
92.3-1-10
92.9-11111
92.8:00.8
EXPERIMENTS
In this section, conduct experiments to evaluate ORTHO- ORTHO-REG by answering the following research questions:
What's the performance of ORTHO- REG common transductive node classification tasks compared with GNN models and other MLP models? (Sec. 5.2)
RQI:
RQ2: On cold-start settings where we do not know the connections of testing nodes, can ORTHO-REG demonstrate better performance than other methods? (Sec. 5.3)
RQ3: Does ORTHO-REG mitigate the dimensional collapse issue, and is each design of ORTHO-REG really necessary its success? (Sec. 5.4)
RQ4: Can ORTHO-REC demonstrates better robustness against structural perturbations compared with Graph Neural Networks? (Sec. 5.5)
Due to space limits, we defer the experiments on heterophily graphs and scalability comparison in Appendix C.2 and Appendix C.3, respectively. A brief introduction of the baselines is given in Appendix B.3.
5.1 EXPERIMENT SETUPS
Datasets. We consider 7 benchmark graph datasets and their variants in this section: Cora, Citeseer, Pubmed, Ciazzon-Comput. they are representative datasets used for semi-supervised node classi- fication (Kipf & Welling, 2017; Hu et al., 2021: Zhang et al., 2021: Zheng et al., 2021). The detailed introduction and statistics of them presented in Appendix B. To evaluate ORTHO-REG on large-scale graphs, we further consider two OGB datasets (Hu et al., 2020): Ogbn-Ar Arxii and Sesbn-Product Note that the OGB datasets are designed for fully-supervised node classification tasks, so we defer their results to Appendix C.
Photoo, Coauthor-CS, and
Seauthor-Physion
two-layer MLP model the encoder generate node embeddings, then another linear layer takes node embeddings as input and outputs predicted node labels. We use Pytorch implement the model and DGL (Wang et al., 2019) to implement the neighborhood summarizing operation in Eq. 6. If not specified, all our experiments are conducted on an NVIDIA V100 GPU with 16G memory with Adam optimizer (Kingma & Ba, 2015).
Implementations. If not specified,
5.2 TRANSDUCTIVE SUPESIEPER NODE CLASSIFICATION (RQ1)
We first evaluate method on transductive semi-supervised node classification tasks. For com- parison, we consider three types of baseline models: 1) Graph Neural Networks (GNNs), including SGC (Wu et al., 2019a), GCN (Kipf & Welling, 2017) and GAT (Velickovic al., 2018). 2) Repre- sentative knowledge distillation (KD-MLP) method GLNN (Zhang et al., 2021). 3) Basic MLP and GR-ML.P models, including Laplacian Regularization Regp-Reg, Zhou et al. (2003), Ando & Zhang
7

---

Under review as a conference paper at ICLR 2023
Table 2: Test accuracy on the isolated nodes.
Table 3: Effects of different components of ORTHO-REG
Methods
Coza
Citeseer
Pubmed
Variants
Cora Citesees Pubmed
GCN
53.02211.88
47.09=1.38
71.50:2.21
GNN6
GraphSAGE
55.38:1.92
41.46=1.57
69.8742.13
Baseline
84.7
73.5
82.8
KD-MEPs
ColdBrew
58.75422.11
53.17=1411
72.31+1199
54.7
51.4
47.2
GLNN
59.34+1977
53.64=1.51
73.1942.11
8
79.3
68.7
76.8
MLP
$2.35:1183
53.26=1441
65.84:1..08
T
83.9
72.9
GR-MIPP
GraphMLP
59.32.11.81
53.17=1.48
1.48
72.33-12.11
T
84.7
73.5
82.8
ORTHO- REG (Ours)
6.773:11.77
1.54
73.4221.99
T
84.3
73.3
82.5
(000))), Propagation Regularization (P-Reg, Yang al. (2021)), GraphMLP (Hu et al., 2021), and hole-to-Neighborrhood Mutual Information Maximization (N2N, Dong et al. (2022))
For each dataset, 1000 nodes for testing. For Cora, Citeseer, and Pubmed we use the public split, while for the remaining datasets, we split randomly. We report the average prediction accuracy with standard deviation over 20 random trials in Table 1.
20 nodes per class for training, 500 nodes for validation, and another
As demonstrated in the table, ORTHO-REG outperforms previous GR-MLPs by large margin, which greatly validates the importance and effectiveness of orthogonal node embeddings. Compared with the competitive knowledge distillation method GLNN, ORTHO- REEG also demonstrates better performance on 6 out of 7 graphs. It is also worth noting that our method even outperforms powerful GNN models such as GCN and GAT, which indicates that node features of the graphs are less exploited by these GNN models. In contrast, our method can fully exploit the potential of node features.
5.3 INDUCTIVE NODE CLASSIFICATION FOR COLD- START SCENARIOS (RQ2)
To evaluate the performance of ORTHO-REC on cold-start scenarios where the connections between newly encountered nodes and existing nodes are missing, we follow the setups in ColdBrew that selects proportion of nodes as isolated nodes which will be removed from the original graph. Then the model is evaluated on the isolated nodes in the testing set. Due the space limit, we present the detailed setups and evaluation methods in Appendix B.2. Besides the baselines used in Zheng et al. (2021), we also include GLNN for a fair comparison.
In Table. 2, report the experimental results of ORTHO- and baseline methods on the isolation nodes. As demonstrated in the table, for isolated nodes whose connectivity in the graph is unknown, GNN models perform poorly as they require both the node features and graph structure for accurate inference. By contrast, MLP-based models generalize better on isolated nodes as they make the best of the available node features. The proposed ORTHO-REs REE outperforms both GNNs and MLPs (including KD MLPs and GR-MLPs) baselines.
5.4
STUDIES OF ORTHO-ROS REG (RQ3)
5.4.1
DOES ORTHO-REG MITIGATE DIMENSIONAL COLLAPSE?
In Sec. 3 we have attributed the limitation of previous GR-MLPs the dimensional collapse phenomenon, and in Sec. 4.2 we have proposed ORTHO- REG to mitigate such a problem from theoretical perspective. this part, we would like to empirically show that ORTHO-RES -TEH can avoid the dimensional collapse issue by keeping node embeddings" eigenspectra.
In consistency with the settings in Sec. 3, we evaluate the embeddings learned from ORTHO-
at different training epochs (we take both Cora and Fubmed for illustrations). The decay of cigenvalues of node embeddings' correlation matrix at different epochs is plotted in Fig. 4 (a) and (c). It is observed that the top eigenvalues are well-reserved thanks to the explicit regularization of node embeddings' correlation matrix. In Fig. 4 (b) and (d) we also plot the change of testing accuracy as well as the NESum value the training epoch increases, from which we could observe positive relationship between the NESum value and the test accuracy: neglecting the initial oscillations, we notice the test accuracy will grow smoothly the NESum value increases and will reach its peak
8

---

Under review as a conference paper at ICLR 2023
Normalized eigenvalie Nomallres aigervatts
Eigenvalue detribution
Evolvement NESum
101
1pech
291
Apcuray
6.8-
GDI Orna
84
Pubmed
GOh om Rra
1:.4
393
NES
82
1830
2330
0.21
Eigenvalue rank
131
1P
Training Epoch
Accuracy
80
[c)
Putmed Eigenvo ue destibution
[d]
Pubmed: Evalvement NESum
78
78
kpcch
433
Adcurasy
MEGum
NESUm
76
23
1900
74
74
Eigenvalue
Trxining Fpoch
Masking
Masking ratio
Figure 4: Visualization of ORTHO-REG'S impact Figure 5: Performance with different strengths of on node embeddings Eigenspectra on Cora and edge masking ratios.
Pubmed.
when NESum overwhelms (Cora) converges (Pubmed). The above observations demonstrate that ORTHO-REG does mitigate the dimensional collapse problem and lead to more powerful model.
5.4.2 ABLATION STUDIES
We then conduct ablation studies to study the effect of different components of ORTHO-REG, and we present the results in Table We first study the impact of the two regularization terms by setting the corresponding factors (a: and (3) to O. respectively. When = 0 (i.e., only decorrelating different dimensions), we observe that the model's performance even worse than the pure MLP model (see in Table 1). This indicates that adding orthogonal regularization is not always beneficial (e.g.. for vanilla MLP), but is indeed beneficial for GR-MLPs. By contrast, without orthogonal regularization (i.e., 3 = 0), the power of structure regularization is restricted, and decorrelating different dimensions can boost performance greatly. We further investigate whether considering a larger neighborhood would improve the model's performance. The empirical results demonstrate that considering larger neighborhood improves the performance compared to only using first-order neighborhoods, but T = 2 is already optimal for most datasets.
5.5 ROBUSTNESS AGAINST STRUCTURAL PERTURBATIONS (RQ4)
Finally, we study the robustness of ORTHO-ROO -EG against attacks the graph structures compared with GNN models. As ORTно-RES -EG uses node features rather than a combination node features and edges for prediction, we expect demonstrate better robustness under mild structural perturbations. To reach this target, we randomly mask a fraction of the edges of the graph and evaluate the performance of ORTHO-REC and GCN under different edge-masking ratios. In Fig. 5, plot how the model's performance changes (with standard deviation) as the masking ratio increases with 20 random trials. As demonstrated in Fig. 5, method demonstrates better robustness against moderate-leve edge perturbations. This is because we do not explicitly use the graph structure for generating predictions, making ORTHO-PR -EG less sensitive to perturbations on the graph structure.
6 CONCLUSIONS
In this paper, we have proposed ORTHO-REG, novel Graua-Reg MLP method for node representation learning. We show that simple graph regularization methods can cause dimensionally collapsed node embeddings both theoretically and empirically. We show that the proposed ORTHI-- REG, which enforces the orthogonality of the correlation matrix of node embeddings, can naturally avoid the feature collapse phenomenon. We have conducted extensive experiments, including traditional transductive semi-supervised node classification tasks and inductive node classification for cold-start nodes, demonstrating the superiority of ORTHO-REG.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rie Kubota Ando and Tong Zhang. Learning on graph with laplacian regularization. In NIPS, pp. 25-32. MIT Press, 2006.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In NeurIPS, pp. 7411-7422, 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
Valerio Ciotti, Moreno Bonaventura, Vincenzo Nicosia, Pietro Panzarasa, and Vito Latora. Homophily and missing links in citation networks. EPJ Data Sci., 5(1):7, 2016.
Wei Dong, Junsheng Wu, Yi Luo, Zongyuan Ge, and Peng Wang. Node representation learning in graph via node-to-nnighbourhood mutual information maximization. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 16620-16629, 2022.
Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe. Whitening for self- supervised representation learning. In ICML. volume 139 of PRML, pp. 3015-3024. PMLR. 2021.
Wenqi Fan, Yao Ma Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs In NeurIPS, 2020.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. NIPS, pp. 1024-1034, 2017.
Bobby He and Mete Ozay. Exploring the gap between collapsed & whitened features in self- supervised learning. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 2022.
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. In NeurIPS, 2020.
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: Node classification without message passing in graph. CoRR, abs/2106.04051, 2021. URL https: / aaaaiiiiv..///a. org/ abs/ abss/20ss 221..110...20 04051.
Tianyu Hua, Wenxiao Wang. Zihui Xue, Sucheng Ren, Yue Wang, and Hang Zhao. On feature decorrelation in self-supervised learning. In ICCV, pp. 9578-9588, 2021.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In ICLR. 2019.
Li Jing, Pascal Vincent, Yann LeCun, and Yuandong Tian. Understanding dimensional collapse in contrastive sule-supe learning. ICLR, 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Kanglin Liu, Guoping Qiu, Wenming Tang, and Fei Zhou. Spectral regularization for combating mode collapse in gans. In ICCV, pp. 6381-6389, 2019.
10

---

Under review as a conference paper at ICLR 2023
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review sociology, 27(1):415 444, 2001.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. 2019.
arXiv preprint arXiv: 1w0Xv:1905,000
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuad Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. SIGN: scalable inception graph neural networks. arXiv preprint arXiv: abs/2004.11199. 2020.
Hannes Stärk, Dominique Beaini, Gabriele Corso, Prudencio Tossou, Christian Dallago, Stephan Günnemann, and Pietro Liò. 3d infomax improves gnns for molecular property prediction. In International Conference on Machine Learning, pp. 20479-20502. PMLR, 2022.
Rianne van den Berg, Thomas N. Kipf, and Max Welling. Graph convolutional matrix completion. CoRR, abs/1706.02263, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Minjie Wang. Lin Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufci Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv, 1909.01315, 2019.
Yuyang Wang, Jianren Wang. Zhonglin Cao, and Amir Barati Farimani. MoleIr: Molecular contrastive learning of representations via graph neural networks. arXiv preprint arXiv:2102. 10056, 2021.
Felix Wu, Amauri H. Souza Jr., Tiayyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871, 2019a.
Qitian Wu, Hengrui Zhang. Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen. Dual graph attention networks for deep latent representation of multifaceted social effects in recommender systems. WWW, pp. 2091-2102, 2019b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Han Yang, Kaili Ma, and James Cheng. Rethinking graph regularization for graph neural networks. In AAAI, pp. 4573-4581. AAAI Press, 2021.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. ICLR, 2021.
Wenqing Zheng, Edward W. Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete missing neighbor- hoods. ICLR, 2021.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S. Yu. Graph neural networks for graphs with heterophily: A survey. arXiv prepint arXiv:2202.079 270200002, 2022.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency, In NIPS, pp. 321-328. MIT Press, 2003.
11

---

Under review as a conference paper at ICLR 2023
A PROOFS
A.1 PROOFS FOR LEMMA
Proof. First, let's take the gradient of the regularization loss Lreg with respect to the weight matrix
W:
Ohreg
d UH(HT LH)
OW
OW
i uT( (XXX))T(XXX
ow
=2X =2X LXW
-2P
Treat the weight matrix function of the training step i.e., W ((t,, then derive the gradient of (I) with respect to by dW(t) 2PW. both X and L are fixed, we can solve the equation analytically,
dt
(t = exp(Pt) : W(0).
(10)
As have the -sc-adcen eigenvalues of as X Xx 2 2 X we can define an auxiliary function 2f Xfr exp(Aft)) exp(Aft) () ( -2frr It is obvious that [(1; Af" >f)) is
monotonically decreasing for all j 2 i. As W is transformation of its initial state W (0) to exp(Pt), we can easily conclude that
W (1) (1)()
S 0 W(L) (t)
Ai<K 1' and i و.
(11)
(1)
o, (t))
If we further have the condition that XP 2
1
X 2
2
Xp. we have
lim [(t; Aft:AP.2P1 = 0, Vi < d.j + 1. Then we are able to complete the proof.
A.2 PROOFS FOR THEOREM
Proof. The embedding space is identified by the eigenspectrum of the correlation (covariance) matrix C' of node embeddings H. As XW. its correlation matrix can be (simply) identified as:
N
Σ
hh - TT)((h, -h)NN
i=1
(12)
N
Σ
W (x;; xx) T x: W/N.
=
According to Lemma 1, W has shrinking singular values, so has vanishing eigenvalues, indicating collapsed dimensions.
Specially, when the input features have an identity matrix, we have:
N
c=
W
(x:
x)
T (x:
F W/N.
N
(x; 8
(x; T W
(13)
W
N
1=1
W W.
L
Thus, for C's eigenvalues (X() D we have 2 = =ooW)2 Then Theorem can be easily concluded with Lemma 1.
12

---

Under review as a conference paper at ICLR 2023
A.3 PROOFS FOR THEOREM
Proof. Note that we aim to optimize the following objective function (Eq. 7):
-= -0 Σ Ckk +
CRu- WAR
km
As the first term applies only on the on-diagonal terms of the correlation matrix and the second term applies only on the off-diagonal terms, we able to study the effects of terms respectively:
Con-diog ding
kk
k=1
(14)
D
Loss =
Σ
For the on-diagonal terms Lon-diags we have 1, we have C
Σ h /N, and
N C&k = Σ (ha)a (8i)x/N (the subscript denotes the k-th dimension). Then, 1=1
θCka 0(hs)&
1 N (si)s, and 0Ckr 0, Vk' + k. 0(h;)k
(15)
As result,
D
0 Σ
CrA
1
1 EjeNo h N
k=1
8;
(16)
Oh,
[W(1)
Eq. 16 indicates that the on-diagonal terms force each node embedding to be smoothed within its first-order neighborhoods.
Then we turn to the off-diagonal terms Lofg- Similarity, we have CRR Σ (he)): (st) /N.
As for both H and S, the diagonal term of their correlation matrixes for each dimension should be equal to 1, formally,
N
Σ
Σ
(x))
1.
(17)
N
N
Then according to Cauchy-Schwarzz Schwarz inequality, we have:
N
2
Σ
(he)a
(si)a
Σ
(h
Σ (s:)
N22
(18)
(hi)
(8s)
N
and the equality holds if and only if (hx); (st)s, Vi. As result, the global optimizer of Lon-diag will induce h; = 8i, Vi. Then, when CKK. = 0, o f we have:
Σ (ha)x (sI)
Σ (h)) (ho)w/N
Crauto 0,
(19)
where Coato is the auto-correlation matrix of H. So we've completed the proof.
13

---

Under review as a conference paper at ICLR 2023
B EXPERIMENT DETAILS IN SECTION 5
B.1 DATASETS DETAILS
We present the statistics of datasets used in transductive node classification tasks Table 4, including the number of nodes, number of edges, number of classes, number of input node features well as the number of wrainingvaaiddaiioneesingg nodes.
Table 4: Statistics of benchmarking datasets transductive settings
Dataset
#Nodes
#Edges
#Classes
#Features
#Train/Val/Test
Cora
2,708
10,556
7
1,433
140/500/1000
Citeseer
3,327
9,228
6
3,703
120/500/1000
Pubmed
19,717
88,651
500
60/500/1000
Coauthor-CS
18,333
327,576
15
6,805
300/500/1 000
Coauther-Physics
34,493
991,848
5
8,451
100/500/1000
Amazon-Computer
13,752
574,418
10
767
200/500/1000
Amazon-Photo 7,650
287,326
745
160/500/1000
For the inductive node classification tasks in cold-start settings, also present the statistics of Cora. Citeseer and Pubmed in Table 5, where we provide the number of isolated nodes, the number of tail nodes as well as the number of edges left after removing the isolated nodes from the graph.
Table 5: Statisties of benchmarking datasets in inductive settings
Dataset
#Nodes
#Edges
#lsolated
#Tail
#Edges left
Cora
2.708
10.556
534
534
9,516
Citeseer
3,327
9,228
676
676
7,968
Pubmed
19,717
88,651
4,547
4,547
79,557
B.2 DETAILS OF EXPERIMENTS ON COLD-START SCENARIOS (SEC. 5.3)
In this section, we detailedly elaborate how inductive isolated nodes are selected. Note that our processing directly follows the officially-imllemennee codes' in ColdBrew (Zheng et al., 2021). For each dataset, we first rank among the nodes according to their node degrees, through which we are able to get the degree of the bottom 3th percentile node, termed by dzm.- Then screen out nodes whose degree is smaller than or equal to d as isolated nodes, which are subsequently removed from the original graph.
Note that in these datasets most of nodes only have a few connections (e.g. 1 or 2), the actually numbers of isolated nodes and tail nodes usually much larger than the expected 3%. See Table for details.
For each dataset, remaining nodes for testing.
the fixed 20 nodes per class (as in the public split) for training and all the
B.3 INTRODUCTION OF BASELINES
In Sec. 5.1 we've briefly introduced the baselines for comparison, here we'd like to detailedly introduce the MLP-based baselines.
KD-MLPs: We have covered two KD-MLP models: GLNN (Zhang al., 2021) and Cold- Brew (Zheng et al., 2021).
hhtpp:://gi http://///gtuub...oomaaaaooooo http://amoonnneeeeeeeeaeaeemeaee --gnneral ization
14

---

Under review as a conference paper at ICLR 2023
As typical GNN-to-MLP knowledge distillation method, given the predicted soft labels from a well-learned GNN model {z;}- GLNN learns an MLP model through jointly optimizing the supervised loss labeled nodes and the cross-entropy loss between MLP's predictions and GNN's predictions over all nodes:
GLNN:
ggnnn =s + ALkdd
Soup
Σ LVVL
exent (v. and Lud = -Dxr(0
(20)
LEV
where is a trade-off hyperparameter.
ColdBrew: As another KD-MLP model, ColdBrew specially designed handle cold-start problems and has a totally different formulation compared with GLNN. First, it equips the teacher GNN model with structural embedding so that it can overcome the oversmoothing issue. Then, besides the knowledge distillation loss, it discovers the virtual neighborhood each node using the embedding learned from the student MLP. With this operation, the model is able to estimate the possible neighbors of each node and thus can generalize better in inductive cold-start settings.
We then introduce the covered GR-MLP models, including Lap-Reg (Zhou et al., 2003; Ando & Zhang, 2006), P-Reg (Yang et al., 2021) and GraphMLP (Hu et al., 20 detailedly. Besides the basic supervised cross-entropy loss, GR-MLPs employ variety of regularization losses to inject the graph structure knowledge into the learning of MLPs implicitly.
GR-MLPs:
Lap-Reg: Based on the graph homophily assumption, Lap-Reg enforces Laplacian smooth- ing the predicted node signals over the graph structure. Its regularization target could be formulated as:
Liap-reg reg ir(Y LY);
(21)
where Y the predicted node signals and is the Laplacian matrix of the graph.
P-Reg: Similar to Lap-Reg, P-Reg is also built on top of the graph homophily assumption.
However, instead of using edge-centric smoothing regularization, P-Reg employs a node- centric proximity preserving term that maximizes the similarity each node and the average of its neighbors. The regularization objective could be formulated as:
Cp-reg
N db H. AH),
(22)
where ÄH the propagated node embedding matrix, and Φ is function that measures the difference between H and ÅH, which could be implemented with variety of measures like Square Error, Cross Entropy, Kullback-Leine Divergence, etc.
Graph-MLP: Inspired by the success of contrastive learning, Graph-MLP tries to get rid of GNN models by contrasting between connected nodes. Formally:
Σ exp(sim(h,, h2)/ JEN()
N
1
Cgraph-mip
log
(23)
N
Σ exp(sim(h; (yp(sim(t;,hbb//77 hw)/T)
REV
The final objective function is also trade between the supervised cross-entropy loss and the regularization loss.
C ADDITIONAL EXPERIMENTS
C.I EXPERIMENTS ON OGB-GRAPHI
To study the effectiveness of ORTHO- -EG on large-scale graphs, conduct experiments two large-scale graphs: Ogbn-Arxi v and Ogbn-Products and we present the results in this section.
The statisties of the two datasets in the transductive setting and the inductive cold-start setting presented in Table and Table 7. Note that the official split of OGB datasets is different from other datasets in Sec. 5 and does not follow the semi-supervised setting.
15

---

Under review as a conference paper at ICLR 2023
Table 6: Statistics of OGB datasets in transductive settings
Dataset
#Nodes
#Edges
#Classes
#Features
#Train/Val//er
Ogbn-Arxiv
169,343
2,332,486
40
128
90,941 / 29,799 48,603
Ogbn-Products
2,449,029
123,718,024
47
100
196,615 / 39,323 2,213,091
Table Statisties of OGB datasets inductive settings
Dataset
#Nodes
#Edges
#Isolated
# Nodes left
Edges left
Ogbn-Arxis
169,343
2,332,486
16,934
152,409 2,204.127
2,298.618 123,661,058
Ogbn-Products
2,449,029
123,718.024
244,902
For fair comparison, we use the same model size (i.e., the number of parameters) for each model. We train each model for 10 times on each dataset and report the average accuracy with standard deviation on transductive setting and inductive cold-start setting in Table 8 and Table respectively.
Table 8: Test accuracy on OGB datasets in trans-Table 9: Test accuracy the isolated nodes of ductive settings.
OGB datasets.
Methods
-gxiv
Ogbn-Products
Methods
Ogon-Arxiv
Ogbn-Producta
GNNs
GCN
SAGE
7..74
71.49:0.277
78.61:10.23
75.26:10.21
GNNs
GraphSAGE
GCN
44.51#0.85 47.32+0089
57.88=1.011
36.62=1.12
KD-MLPs
69.37:10.25
75.19:10.34
KD-MLPs
ColdBrew
$2.36-+0084
61.64-0.98
MLP
56.28:10.37
61.06:10.08
GR-MLPs Lap-Reg
57,83-40052
65.91-40.31
MLP
51.03++0.75
60,18=0884
P-Reg
58.41=0045
65.324+.28
Lap-Reg
51.8740.81
60.47=0.77
GraphMLP
61.11=0.36
68.34:20.3
GR-MLP P-Reg
51.79.10.88
60.5910.91
GraphMLP
52.21:10.91
61.12=0.98
Ours
ORTHO-RRG
70.35=#0.22
74.35=#0.19
ORTHO REG (Ours)
54.51.1.77
63.95.0.74
As demonstrated in Table 8, though under-performing GNN models, ORTHO-RES gives quite good performance (which are very close to that of GNNs) on these two datasets. On inductive cold-start prediction tasks, ORTHO-REG also outperforms both GNN models and other MI.P models.
C.2 EXPERIMENTS ON HETEROPHILY GRAPHS
Then we study the generalization ability of ORTHO-REE -ERG on heterophily nion-hompphily) graphs. We first give the formal definition of graph homophily ratio as follows:
Definition 1. (Graph Homophily Ratio) For a graph G -V,E) with adjacency matrix A, its homophily ratio & defined as the probability that two connected nodes share the same label:
Σnsev Aij 1 yı
Σiyev Aij 1ly, =y
(24)
ΣijEy Aij
The evaluated datasets previously all homophily graphs, where connected nodes tend share the same labels. To evaluate ORTHO- REG more extensively we consider three more widely used heterophily graphs: Chameleon. Squirrel and Actor. We provide statistics of the three datasets in Table 10.
For heterophily graphs where the graph homophily assumption does not hold (McPherson et al., 2001; Ciotti et al., 2016), it might be improper to enforce node embeddings/preciicion to be smoothed over the graph structure. As a result, we modify the neighborhood abstraction function so that can better adjust to heterophily graphs. Specifically, we adopt the following function to construct summary embedding:
- H
(25)
Compared with Eq. 6, we use only the second neighbors for heterophily graphs. We present the results on the three heterophily graphs in Table 11. For comparison with GNN models, cover additional
16

---

Under review as a conference paper at ICLR 2023
Table 10: Statisties of heterophily graphs
Dataset
#Nodes
#Edges
#Classes
#Features
Heterophily ratio ø
Chameleon
2,277
36,101
5
2,325
0.25
Squirrel
5,201
217,073
5
2,089
0.22
Actor
7,600
33,544
5
0.24
Table 11: Performance on heterophily graphs
Methods
Chameleon.
Squirrel
Actor
Geom-GCN
67.32+11.76
46.01+1.27
30.59:1-0.76
GNNs
GPRGNN
66.31
50.56+ 1.51
30.78++0.83
KD-MLPs
GLNN
60.58:+1.72
43.72=1.166
34.12:10.77
ML.P
47.59-+0.73
31.67+0.61
35.93-10.61
GR-MLPs
Lap-Reg
1..7
30.44+0.97
33.71+0.599
ORTHO-REG (ours)
63.55+00.83
48.72+0093
36.64+0067
two GNN models that specifically designed for handle heterophily graphs: Geom-GCN (Pei et al., 2020) and GPRGNN (Chien et al., 2021)
As demonstrated in the Table, though can't match the performance of advanced GNN models on heterophily graphs, method greatly narrows the gap between MLPs and GNNs. Specifically, on heterophily graphs where GNNs even perform worse than the vanilla MLP, our model is able to achieve even better performance, thanks to the MLP-based encoder and the regularization loss.
C.3 SCALABILITY TEST
Finally, we show that with an MLP model as encoder, ORTHO-RES is able to perform inference fast without the reliance on graph structure. We plot the inference time of ORTHO-RES and GraphSAGE on Ogbn-Producct with different model depths Fig. The result demonstrates the superiority of the inference benefit of ORTHO-REG over GNN models.
led
Ortho-Reg (ours)
3.0
GraphSAGE
Inference Time (ms)
2.5
2.0
1.5
1.0
0.5
1
Number Layers
Figure 6: The inference time comparison of GraphSAGE and ORTHO-REG on Ogbn -ron-Products. ORTHO-REG able to perform inference much faster than GraphSAGE.
C.4 COMPLETE EMPIRICAL RESULTS FOR SEC. 3
In Fig. 2, we only plot the evolving of top-8 eigenvalues for better visualization. Here, we plot the evolving of all 512 eigenvalues. We also provide the result when À 0.01 for better comparison.
17

---

Under review as a conference paper at ICLR 2023
A=0
0.000
0=0.01
==0.1
107
10
10"
10-1
10-
10-2
10
10-2
Exxh
Ebsdh
10-3
10
10
10
10-4
10-1
10-4
10
10a
10:
10
10:
10
10
10
10
10P
10:
10
10
10
104
10-
Eigenvalue
Eigenvalue rank
Eigenvalue rank
Eigenvalue rank
Figure 7: Eigenspectra for node embeddings with different strengths of Laplacian regularization (A). The node embeddings are from the second last layer, with dimension d = 512. x-axis represents the index sorted eigenvalues while y-axis is the corresponding normalized values.
C.5 SENSITIVITY ANALYSIS OF TRADE-OFF HYPERPARAMETERS
Cora
Citeseer
Pubmed
0.0005
0.0005
0.825
0.73
0.72
2.01
0.003
0.71
0.202
0.002
0.025
6.05
0.58
8.005
3.65
-0.67
0411
0.01
001
3.60
-0.66
2e-00
5e 00
2--0
06
1e 05
1e
1e:6
1e:0
20.0 20.07
SwaD7
05
to 1e
10
Figure Performance heat map when using different a, B combinations Eq. 7, on Cora, Citeseer and Pubmed.
In this section, we study how the two trade-off hyperparameters and / affects the performance of ORTHO-RECE We try different combinations of and /3 on Cora, Citeseer, and Pubmed, and plot the performance heatmap in Fig. 8.
The conclusion is very interesting: the performance of ORTHO--REC is not very sensitive specific value of a or 33 In other words, for a reasonable value of a (B), we can easily find another value of B (a) that can achieve similarly high performance. The ratio between and 9 seems much more important. From Fig. 8, we can observe that for Cora, a/3 = 2 10a. and for Pubmed, a/B 1 10 can lead to the optimal performance; changing the value of while fixing a/ will not change the performance very much.
D REPRODUCIBILITY
Please check the supplementary material.
E RELATIONSHIP BETWEEN DIMENSIONAL COLLAPSE AND LINEAR CLASSIFICATION PERFORMANCE
In Sec. 3, we mainly demonstrate that the dimensional collapse phenomenon does exist in the typical GR-MLP method Laplacian Regularization. In this section, we'd like to use simple example to explain why dimensional collapse may lead to limited expression power and sub-optimal linear classification performance, which will better support the motivation of this work.
To simplify the analysis, consider two-class classification problem where each data point is embedded 2-dimensional space R². The two dimensions are denoted by e and 62, respectively. In Fig. 9, we consider three cases: 1) complete dimensional collapse where the embeddings fall line
18

---

Under review as a conference paper at ICLR 2023
class 1
embedding space
decision boundary
decorrelated (whitened) features demonstratte better izatralizaiion ability to nolay data
Dimensional collapse
Decorrelated Features
Figure 9: How dimensional collapse affects the performance of linear classification. Left: complete dimensional collapse; Mid: weak dimensional collapse; Right: perfectly decorrelated features.
(the left case); 2) weak dimensional collapse where the variance of the larger eigenvalue's direction is much larger than the other one (the middle case); 3) perfectly decorrelated features where the two eigenvalues' direction are equally important (the right case). We assume that the labels of training data are generated according to ÿ = sgn(e2 - 61), i.e., the data point will be labeled as class when 62 C1, and class otherwise. As result, obvious linear decision boundary will be e2 61.
In the first case (complete dimensional collapse), the data points cannot be linearly classified as they all fall the same line. In the remaining cases, data points belonging two different classes be easily separated with the decision boundary illustrated above. However, the above results only hold when the data points and labels are generated exactly following the above assumption, which is hard to meet. In many cases, the input data might be noisy, leading to shifting in its final representation. As shown in the circled areas Fig. 9, when the embedding shift phenomenon occurs (from the brown triangle to the brown triangle) in the weak dimensional collapse case, the shifted embedding can be easily misclassified by the original linear classifier, even if the original embedding is already far from the decision boundary. By contrast, for perfectly decorrelated features, the embeddings can show better tolerance for data noise. Besides, decorrelated features can also show better robustness to attacks and better generalization ability testing data, thanks to wider embedding space for each class separated by the decision boundary.
19


Reviews:
[{"review_id": "tphx8p0u8q", "reviewer": "Reviewer_GzRn", "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": "", "summary_of_the_paper": "This paper aims to investigate why the performance of graph-regularized methods could not match GNN models. It shows that the spectral collapse occurs under the linearity assumption of the mapping module (i.e., linear MLP). Then, the authors design a new regularization term for GR-MLPs. The experimental results show that the proposed term works pretty well on real datasets. ", "summary_of_the_review": "Overall, the paper is well-motivated and easy to follow. The theoretical analysis makes the orthogonal term convincing. The paper has some  merits, but there are several drawbacks as well. I'd like to update my score after reading the feedback and other reviews.  ", "strength_and_weaknesses": "### Strength\n- The paper is well-written and well-motivated. The idea and motivation are clarified and the paper is easy to follow. \n- The experiments are strong and the performance could match the results of SOTA GNN models. \n\n### Weakness\n- The theoretical conclusions are based on the linearity assumption, which is not clarified in ABSTRACT. It is an important precondition of the theoretical analysis and it should be emphasized. \n- When theoretically analyzing the existence of dimensionality collapse, the supervised loss, ($\\ell_{xent}$, is neglected. It also produce the gradient w.r.t. W. However, Lemma 1 fails to clarify it. If I don't misunderstand, the conclusion only holds when $\\lambda \\rightarrow \\infty$ ($\\lambda$ is defined in Eq. 1). It is the main limitation of the anlaysis and the preconditions have to be clarified in Lemma 1. \n- $\\{\\lambda_i^C\\}$  seems to only appear in the beginning of theoretical analysis. I know the convergence of $\\sigma_i(W(t))$ would lead to the statement, but there should be some descriptions of $\\{\\lambda_i^C\\}_{i=1}$ after Lemma 1. \n- As the authors claim that the efficiency of graph models is quite important, Eq. 5 seems a quite time-consuming operation. What is the difference between the GR-MLP with the proposed term and other models, including existing GR-MLPs and GNNs?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aMmeHe_KhD", "reviewer": "Reviewer_JMnM", "summary": "", "questions": "", "limitations": "", "rating": 6, "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_of_the_paper": "The authors propose a theoretical and empirical study on the problem of dimensional collapse due to over-smoothing in graph-regularized MLPs. Then, they propose to regularize the cross-correlation between node features and pooled features to alleviate this problem. The resulting model \"Ortho-Reg\" surpasses the performance of the compared baselines on semi-supervised and cold-start scenarios. Additional experiments show that the proposed regularization helps to alleviate the smoothing problem, that the proposed model is robust to perturbations, and the robustness to different hyperparameter choices.\n", "summary_of_the_review": "Overall the method is sound and interesting, the authors add details for reproducibility and include theoretical and empirical insights. Most of my concerns are about clarity and I suggest the authors to go through my questions above. Also, there is the name of the method, which has been used in the past in a slightly-related topic.\n\nGiven that this work still needs polishing, I think it is \"marginally below the acceptance threshold\". However, I think my concerns are easy to address in a rebuttal and I encourage the authors to do so. \n\nAfter rebuttal\n==========\nThe authors' responses clarified all my questions and resolved most of the other reviewers' concerns. Thus, I raise my score to accept.", "strength_and_weaknesses": "Strengths\n=======\n* The proposed method is sound and it improves performance of GraphMLPs. \n* The authors provide code and ablations, which makes their method more reproducible\n* The additional analysis / empirical study is interesting\n\nWeaknesses\n=========\n* There exists another OrthoReg in the literature [A] that is also a regularization that enforces orthogonality. Although this does not affect the novelty of this work (since they were proposed for different purposes), it could generate some confusion. I suggest to change the name to CorrReg / OrthoGraph / OrthoGraphMLP / OrthoNodeReg / OrthoGraphReg / ....\n* The number of baselines is small compared to other works [B]. Is there any reason for that?\n* In Figure 2 I cannot see a big difference between different coefficients.\n\n[A]  \"Regularizing cnns with locally constrained decorrelations.\" ICLR 2017.\n\n[B] \"Node Representation Learning in Graph via Node-to-Neighbourhood Mutual Information Maximization.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.", "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": "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": {}}, {"review_id": "XBQz6W2T6bz", "reviewer": "Reviewer_Mv49", "summary": "", "questions": "", "limitations": "", "rating": 6, "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_of_the_paper": "This paper finds that the conventional Graph Regularized MLPs(GR-MLPs) suffer from the dimensional collapse phenomenon that a few large eigenvalues dominate the embedding space and proposes ORTHO-REG, a GR-MLP model that encourages orthogonal embeddings to mitigate the issue.", "summary_of_the_review": "This paper tries to show that the dimensional collapse phenomenon leads to poor performance of the existing GR-MLP model, but there are defects in both the experiment and the theory, which makes a claim not strong enough.\n", "strength_and_weaknesses": "This paper demonstrates that the conventional GR-MLPs suffer from the dimensional collapse phenomenon in which a few large eigenvalues dominate the embedding space, thus restricting the representation power of these models through theoretical analysis and empirical results. To solve this problem, the authors propose ORTHO-REG, a GR-MLP model that adds regularization terms to encourage orthogonal embeddings and tackle high-order connectivity and non-homophily graphs. The model shows improved performance compared with conventional GR-MLPs and some GNNs on semi-supervised datasets and cold-start scenarios. In general, the paper explains the failure of existing GR-MLPs and is of good structure. However, there are some issues the authors need to address.\n\n1. The theoretical analysis in Sec.3 is questionable. Lemma 1 and Theorem 1 only consider the laplacian smoothing term as the loss function and do not consider the effect of classification loss, which makes the whole theoretical analysis fundamentally problematic. In fact, the proof of lemma 1 implicitly assumes that the laplacian smoothing loss will be optimized to zero. However, in most cases, the smoothing term will not converge to zero because of the classification loss’s influence; thus, the relative value of the smaller eigenvalues to the largest one may not always decrease. Therefore, the lemma, as well as the theorem, does not hold.\n\n2. In the experiment of Sec.3, the eigenspectra for node embeddings do not change much as the weight of the smoothing term increases, which may indicate the dimensional collapse phenomenon is not too severe. It also suggests that classification loss dominates the training process instead of smoothing loss, which contradicts the assumption of the above theoretical analysis.\n\n3. The relation between the dimensional collapse phenomenon and the poor performance of existing GR-MLPs should be explained. Sec.3 mainly demonstrates the existence of the dimensional collapse phenomenon. However, there is no evidence that this phenomenon causes performance degradation of existing models. Intuitively, a modest dimensional collapse might help improve model performance because it might filter noise from input features.\n\n4. Furthermore, the final model is inconsistent with the previous analysis because it introduces higher-order connectivity information, so it cannot be demonstrated that mitigating the dimensional collapse phenomenon alone will improve model performance. To verify this, experiments using the model based on eq.4 are suggested.\n", "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": "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": {}}, {"review_id": "IwIFYoyUCb", "reviewer": "Reviewer_2EfD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies graph-regularized MLPs performance limitations. They show that the node embeddings space from a conventional GR-MLP suffers from dimensional collapse (or spectral collapse). Their solution, ORTHO-REG, mitigates this issue by introducing a soft regularization term based on the correlation matrix of node embeddings in the loss function and then removing the dependency of graph structure on the MLP loss term. Their experimental evaluation shows performance improvement over the SOTA.", "summary_of_the_review": "Ablation study on the range of \\alpha and \\beta parameters done in section 5.4.2 highlights the strengths as well as limitations. Although, the authors demonstrate empirically that their regularization mitigates the spectral collapse problem, the theory proposed is not sufficient. ", "strength_and_weaknesses": "Pros:\n1. The authors take into account the related methods and explain their differences from their technique clearly. For example, differences from the graph-augmented MLPs were explained. \n2. The idea of combining node embeddings and summary embeddings in Eq.7 is neat but with certain caveats, I believe. The choice of \\alpha and \\beta will play a vital role here. \n3. The results in Table 1 are impressive \n4. The paper in general clearly states the contribution and comparison with related works.\n\nComments\n1. Extension to other graph types, Multi-graphs, graphs with hypernodes? As these types are typically used to represent knowledge graphs, do you foresee any issues with generalising the guarantees to these graph types?\n2. (Page 3, 1st para) “Note that GNNs explicitly utilize the graph structure information through learning the mapping from node features and graph adjacency matrix to predicted labels. However, due to the above limitations, we seek for learning an MLP encoder, i.e., H = fθ(X) that only takes node features for making predictions.” Can you please explain the limitations? Are the limitations introduced by the graph structure, can you please give examples as GNNs perform quite well on graph structured data? (I might be missing some context here, in that case, kindly add more explanation in the draft. Maybe, here the authors might want to introduce the idea of soft-regularization.)\n3. The theoretical results are for linear f(X). How well will they hold for the non-linear nature of MLPs? I only see empirical justification. This will be a strong paper if some theory can be developed in that direction, as pointed out in page 4.  \n4. What are the values of \\alpha and \\beta in table3, for the bottom 3 rows? I would like to understand how the regularization terms trade-off with each other. Thanks.\n5. Have you studied other types of graph regularizations?\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject