Relating graph auto-encoders to linear models
Authors: Solveig Klepper
Ulrike von Luxburg
Venue: Accepted by TMLR ()

Abstract: Graph auto-encoders are widely used to construct graph representations in Euclidean vector spaces. However, it has already been pointed out empirically that linear models on many tasks can outperform graph auto-encoders. 
In our work, we prove that the solution space induced by graph auto-encoders is a subset of the solution space of a linear map. This demonstrates that linear embedding models have at least the representational power of graph auto-encoders based on graph convolutional networks. So why are we still using nonlinear graph auto-encoders? One reason could be that actively restricting the linear solution space might introduce an inductive bias that helps improve learning and generalization. While many researchers believe that the nonlinearity of the encoder is the critical ingredient towards this end, we instead identify the node features of the graph as a more powerful inductive bias. We give theoretical insights by introducing a corresponding bias in a linear model and analyzing the change in the solution space. Our experiments are aligned with other empirical work on this question and show that the linear encoder can outperform the nonlinear encoder when using feature information.

Published in Transactions Machine Learning Research (09/2023)
Relating graph auto-encoders to linear models
Solvcig Klepper
sobefgg.keppr/uunikcccchnnneeee
Department of Computer Science and Tübingen AI Center University of Tübingen
Ulrike Luxburg
Department of Computer Science and Tübingen AI Center University of Tübingen
Reviewed on OpenReview: kttps: // openreview. net/ forum? id- V IvarE
Abstract
Graph auto-encoders are widely used to construct graph representations Euclidean vector spaces. However, it has already been pointed out empirically that linear models many tasks can outperform graph auto-encoders. In our work, we prove that the solution space induced by graph auto-encoders is subset of the solution space of a linear map. This demonstrates that linear embedding models have at least the representational power of graph auto-encoders based on graph convolutional networks. So why are we still using noulinear graph aulo-encoders? One reason could be that actively restricting the linear solution space might introduce an inductive bias that helps improve learning and generalization. While many rescarchers believe that the noulinearity of the encoder the critical ingredient towards this end, we instead identify the node features of the graph inductive bias. We give theoretical insights by introducing a corresponding bias in linear model and analyzing the change in the solution space. Our experiments are aligned with other empirical work on this question and show that the linear encoder can outperform the nonlinear encoder when using feature information.
more powerful
1 Introduction
Many real-world data sets have a natural representation in terms of a graph that illustrates relationships or interactions between entities (uodes) within the data. Extracting and summarizing information from these graphs is the key problem in graph learning, and representation learning is important pillar in this work. The goal is to represent/encouee /ee///ecceeeeeeeee embed a graph in low-dimensional space to apply machine learning algorithms to solve final task.
In recent. years neural networks and other approaches that automate learning have been employed
powerful alternative to leverage the structure and properties of graphs TTng et al. 2015 Grover & Leskovee
2017 Cao et al. Wang et al. 2016 Chang et al. 2015). For example, Hamilton ct al. 2017b) review key advancements in this area of research, including graph convolutional networks (GCNs). Graph auto-encoders (GAEs), first introduced in Kipf & Welling (2016b), are based graph convolutional network (GCN) architccture. They have been heavily used and further refined for representation learning during the past couple of years (see Li et al. (202T]: Pan el al. (2018); Vaibhay et. al. (2019); Davidson et al. (2018), to name a few). Recently, Salha et al. (2020) discovered that the original GAE architecture, which has been used as a basis for several enhancements, can be out outperformed by simple linear models on an exhaustive set tasks. The equivalence or even superiority of (almost) linear models has also been empirically shown for standard GCN architectures for link prediction and community detection (Wu et al. 2019). The question arises as to why we still use and improve these models when simpler models with comparable performance exist. What the theoretical relation between linear and nonlinear encoders, and does the empirical work provide reason to replace
2016
Ribeiro al. 2017 Dong al. 2017 Hamilton al. 2017a Chamberlai et al.
2016

---

Published in Transactions Machine Learning Research (09/2023)
original graph
encoder
latent representation
decoder
recavered graph
linear
Z Z=ÄXW
o 2j)
Xk
hk
Zk
Ng (0.1, aay 0.9)
Pan
relu
H=relu(AxW(O))
Z=ĀHW(1)
ây = 2(2)
600
X [nx [nxg]
- [n g]
H(1) [n h]
Å [n n
[nxd]
Figure The architecture of a linear auto-encoder and a relu auto-encoder. The only difference is the encoder function: The linear encoder is simple linear map, whereas the relu encoder is two-layer GCN network with relu activation in the first layer and lincar output activation. In both cases, the imput is the graph X), (1)) is the hidden layer of the GCN. A row in the matrix Z gives the latent representation of the respective row/ row/node in the input matrix X. In both cases the decoder is the inner product, and the target is to recover the adjacency matrix A.
graph convolutional networks with linear equivalents? In this paper, we contribute to understanding the underlying inductive bias of the graph auto-encoder model.
Contributions: (1) We draw theoretical connection between linear and non-linear encoders and prove that, under mild assumptions, for any function f(A, X) on graph, there exists a linear encoder that can achieve the same training loss. We use this result show that the representational power of relu encoders is, at most, as large the one of linear encoders. (2) We investigate the bias that is relevant for good generalization and give theoretical insights into how features influence the solution space of a linear model. (3) We empirically find that the nonlinearity in the relu encoder is not the critical ingredient for generalization. Indeed we discover that if the graph features are taken into account appropriately, the lincar model outperforms the relu model test data.
2 Preliminaries
We consider a connected, unweighted and undirected graph G with adjacency matrix A E {0, 13 and feature matrix X Raxg, The feature matrix X contains g g-dimensional feature vectors that describe additional properties of cach node of the graph. For example, if the graph consists of a social network, the features could describe additional properties of the individual persons, such as age and income. If we do not have any feature information for the nodes ("featureless graph"), then we set X as the n n identity matrix. We always assume that all nodes are connected to themselves, that is, an = 1 for all i. We call D Nex the degree matrix with diagonal entries d, = - Aig and 0 everywhere else, and symmetrically normalized adjacency matrix.
1) AD2 1/2 the
Graph convolutional networks. Inspired by convolutional neural networks, graph convolutional networks (GCNs, Kipl Welling (2016a)) are one of the most widely used graph neural network architectures. The input consists of graph X). The graph convolution is applied to matrix Á that encodes the adjacency structure of the graph. This matrix A, called difflusion matrix, is the symmetrically normalized adjacency matrix in our case but could be replaced by any matrix encoding the graph structure, for example, the graph Laplacian. In each layer of the network, node in the graph updates its latent representation, aggregating feature information within its neighbourhood, and learns a low-dimensional represcntation of the graph and its features. More precisely, in layer i, each node update is some function of the diffusion of the weighted

---

Published in Transactions on Machine Learning Research (09/2023)
features: H(++) ((AH(W() with learnable weights W (nonlincar) activation function & and H() as the feature matrix X. The output of the GCN for each node in the graph is a d-dimensional vector representing this node's embedding. This representation can be used for downstream tasks such as node or graph classification or regression.
Graph auto-encoders. Graph auto-encoders aim to learn a mapping of the graph input (A, to an embedding Z E _axd_ This embedding is optimized such that, given decoder, can recover the adja- cency matrix A from the embedding. As visualized in Figure [] the encoder consists of & two-layer graph convolutional network with no output activation and hidden layer with size E N. The decoder simple dot product:
Zreiu = GCN(X, A) = Á relu )
Arclu ((Zrcua F
(1)
encoder
decoder
Here Zielu E Ruxd the latent space representation with embedding dimension d, and the matrix À is the recoustructed adjacency matrix. Note that Á is real-valued matrix that aims to caplure the likelihood of each edge in the graph. To obtain a binary adjacency matrix final result, we discretize by thresholding the values at 0.5. The loss function optimized by the auto-encoder is the cross-entropy between the target matrix A and the reconstructed adjacency matrix Å. It is minimized over the encoder's parameters W The decoder is a deterministic function and is not learned from the data. For a graph with adjacency matrix A, latent space embedding V, and with a(-) denoting the sigmoid function, the loss formalized as follows:
(Z))
Σ mny log(o(=())) + (1 an) (og(((()))))
(2)
Below we compare GAEs based on relu encoder with a simplified model based on linear encoder.
3 Relu encoders have at most the representational power of linear encoders
Graph anto-encoders are widely used for representation learning of graphs. However, it has also been observed that linear models outperform them on several tasks. In this section, we investigate this empirical observation from a theoretical point of view. We define a graph auto-encoder that uses a simple linear map as the encoder and prove that the derived model has larger representational power than relu encoder. To this end, we introduce a linear encoder based on a linear map of the diffusion matrix Zim = AW, where Zum the latent space representation. The loss function and the docoder remain as the relu model. For a relu encoder, the dimension h of the hidden layer satisfies g h > d (for the linear encoder, the parameter does not cxist). We now define the solution spaces to help us describe the respective models' behavior. They will represent the embeddings that can be learned by relu and linear encoders, both with and without node features and more general functions graphs:
3in {Z E Ruxd Z AW for W E Ruxd
Zin,X { Raxd Z AXW for W Raxd]
Zrchu 17 E gaxd 7- = A relu (w for W(0), e Roxb w(l) e Raxd)
Brelu.x (Z E Raxd Z Archu A for W()), e Rank will e Blxdj
2 17 E Baxd
X;0) for Oe
Here ff can be any parameterized function on graph Rxx x Rung x θ - Baxd and O can an arbitrary set of parameters. It is casy to see that 2in,x Zin- In words: when we compare two lincar encoders, one with node features and one without node features, the one with node features has a more restricted solution space. The reason is that the feature matrix is at most rank g and typically has a low rank compared to the diffusion matrix A, which restricts the image of Ax. The same holds for the relu encoder: Zrelu.X E Zrelu- The relation between the linear encoder and the relu encoder is less obvious. One might guess that the relu encoder can learn more mappings than linear encoder. However, we now show that this is not the case: we will see that Zim 2 Zrain focusing on the featureless model. This relation implics that the lincar encoder has a larger reprosentational power than a relu encoder.

---

Published in Transactions Machine Learning Research (09/2023)
While this paper focuses on a specific architecture that has been introduced in previous work and heavily used in practice, some of our insights extend to any encoder function f under mild assumptions on the input graph. Thus, we first state our result in a more general way. We make the following assumptions: Assumption 1. The number of nodes n is larger than the feature dimension
Assumption 2. The rank the diffusion matrix À is larger than or equal to the embedding dimension d. Assumption 3. The fusecion I is invariant to orthogonal transformations, that is, (Z( = (R(2)) for any orthogonal matrix R.
Assumption 1 is typically fulfilled in practice. Vertices are typically described by a moderate number of features. Especially for larger graphs, this is a weak assumption.
Assumption 2 is usually satisfied because the embedding dimension is a choice, and graph auto-encoder aims to find a low-dimensional representation. We can also think about this assumption in the context of the informational content of our data. If the input matrix is of low rank, it holds little information; we will not gain information by embedding it into higher dimensional space. Setting the embedding dimension d smaller than the rank the input matrix rank(A) makes sense.
Assumption 3 is fulfilled in the graph auto-encoder selting; the loss given in Equation 2 is based pairwise distances given by the dot-product. This loss is invariant to orthogonal transformations. Generally, one could construct loss functions not invariant orthogonal transformations. However, orthogonal transformations usually preserve pairwise metrics, and as a result, all loss functions based decoder incorporating pairwise distances will also be invariant to orthogonal transformations.
To prove our main theorem, d-dimensional subset of R", we can find an orthogonal transformation that maps the span of A so that it contains all points in P.
first observe that given Assumption 2, for any set P of points in
Lemma 4. For Pe e Raxd,4 4 Raxm with rank(P) & A), there exists an orthogonal matrie R with span P) _ (RA).
We can prove that the linear model can outperform any other function f on the graph G during training.
Theorem (Minimal Loss). Consider fized graph G = (). Let Å be the diffusion matriz of G and let Z {Z E Raxd Z f(A,X;0) for O) be any latent space representation of any graph function [(A,X; 0)) Let be a loss function and assume that Assumptions 1-3 are salisfied. Then the lineur model can fond a latent space representation with loss at least as good the relu encoder.
Proof. With Lemma it holds that for any Z E Raaxd and any matrix Ā E gaxm with rank(A) > rank (),, there exists an orthogonal matrix R Rax such that all points latent space representation Z are in the image of RA:
ER orthogonal s.t. (RAW) W e RRmxd = (Z Z f(A.X;6) Raxd]
This implics that there exists a weight matrix W e RRa with 1(2) - I(RAW)- - ((AW). In other words, the minimal loss over the set of possible solutions that is learnable by the linear model is smaller or equal to any loss over the solution space achievable by the function f:
(nf,)(Z)) | Zy e 2y) > inf(I(Z(m) Zim e Bno)
Theorem 3 considers a quite general statement. The graph auto-encoder architecture is one particular show that the solution
instance function f. Given the specilic architecture of the auto-encoder space of the relu-encoder is contained in the solution space of the linear model.
Corollary (Representational power of GAEs). For any (trained) graph auto-encoder in
2rein Zialu,x, there crists an equivalent, featureless linear encoder in 3im that can achieve the same training loss because we have ZIo 2 Zielu-

---

Published in Transactions on Machine Learning Research (09/2023)
We refer to Appendix A for the proof. Note that if we assume that rank(AF) d, then the rank of AF larger than the embedding dimension d. Theorem 3 and Corollary P hold for the solution space of the linear model, including features: Ziin,X. We discuss the influence of the features on the representational power of
the linear model in Section 1
Corollary 6 has a simple but strong implication: in principle, the (featureless) linear model is more powerful than the traditional GAE (with or without features). Here "more powerful" means that the linear model can achieve better training loss.
The issue of representational power. Note that we do not claim that
[ʃ: ( R/= - Raxd| X() is any nonlinear GNN] = (S : 12 - Raxd [((A)) - A W for W E Roxd),
which would mean that the function class of linear models contains the function class of noulinear models. However, in the setting of a graph neural network, we usually have a single graph as an input with a fixed number of nodes n. In this setting, the goal to find an embedding of this fixed graph. Our result says that Zy Zmm and in particular Zratuxx S Zzeru E Zin. In words: The solution space of the nonlinear model is contained in the solution space of the linear one, showing that the representational power of the linear model is larger than the one of the nonlinear model.
Generalization properties. Note that Corollary G does not claim that the linear model without features outperforms the relu model. This corollary only considers the training loss. Thus we can not derive anything about the test performance consider training loss and the existence of a weight matrix W. From the above discussion, it is apparent that the linear encoder less restricted, which means that it introduces a weaker inductive bias than the relu encoder. Note that this is independent of the fact that used the relu activation function or the depth of the convolutional network. Regarding the test performance, the question is whether the restriction that the relu encoder puts on the solution space induces a "good" inductive bias that helps improve the model's 's test error. As we see below, we empirically find that when using features, relu encoder does outperform the (featurcless) linear encoder on test data. The relu activation and the features both restrict the solution space and introduce an inductive bias. Next, we investigate which of these two ingredients helps to restrict the representational power in a meaningful way.
the solution that an optimization algorithm might find. So far, we are just.
4 The inductive bias of adding features
This section investigates how features influence the solution space of the linear model and the inductive bias that we introduce by adding features. While Corollary shows the superior representational power of the linear model without features, in Section 5 we will observe improved test performance for models that do use feature information. Whenever the features are low rank compared to the diffusion matrix, they restrict the solution space and introduce an inductive bias that facilitates learning and can improve generalizen gemeralization if they hold helpful information. We observe this behaviour for both considered architectures, the relu and the linear encoder. Consequently, we conjecture that the presence of features, and not the relu nonlinearity, introduces the necessary bias to restrict the solution space in meaningful way. However, some care is needed. As will see, adding features can also harm performance if they contradict the structure of the target graph. In order to quantify the harm, we derive a measure for misalignment between graph structure and feature information. Based on this, we give theoretical insights about the restriction of the solution space when including features in the linear model.
Intuitively, we want to call a graph and the corresponding features X "aligned" if they encode "similar" information. In our setting, this would be the case if A is "close to" XXT; considering the features X E R as node embeddings, the matrix X reconstructed adjacency matrix in a similar way as the dot product decoder. In other words, nodes should be close together the feature space if and only if an edge connects them. Since the adjacency matrix is symmetric, decomposition A = YY'T for Y e Caxn always exists. The error that we might introduce by adding features then comes from the fact that XXT is a (low rank) approximation of yyT A: Even for perfectly aligned features, the feature dimension g is typically much

---

Published in Transactions on Machine Learning Research (09/2023)
smaller than n. Note that if we consider one graph and two different feature matrices with the same span, both features restrict the solution space in the same way and give rise to the same optimal embedding:
Proposition (Features with the same span induce the same solution space). Let À E gax be the diffusion matriz of a fixed graph and U,F R two different feature matrices for this graph. If span(U) - sP then Zúm.U F...F.
Intuitively, this means that if U and F span the same space, the corresponding models can, in principle, learn the same mappings and output the same embeddings.
Proof. We show that for every weight matrix We with Z = AUWe there exists weight matrix We with span(AF) We define corresponding linear maps fu,fr : Rd - R" with (z) = AUx and fr(x) = AFx. Since Im(fe) = Im(fF) we know that every point fu(æ) y has at least one pre-image in fr. Let We [WU,- ... wV, and Z = [zi,.., za] be such that 2, = fo (wy:). For every & there exists at least one wg, with fF(()) = = (a Since this holds for any matrix We we can conclude that Bün,U = Zin.
Z - AFWr. From span(U) - span(F)) it follows that span(At)
We have seen that two different feature matrices with the same span restrict the solution space equivalently. Next, we derive a condition for the alignment between features X and graph structure À that quantifies when features are potentially helpful. To do so, we investigate two settings. In the first setting, the features align with the graph structure and can introduce valuable restriction of the solution space. In the second setting, the features contradict the graph structure and restrict the solution space in such a way that the optimal embedding can no longer be recovered. The intuition for helpful features corresponds with the one for good embeddings: If points are connected in the graph, they should have similar feature vectors. Consequently. we were not to embed the nodes into a low-dimensional space but were simply interested any latent representation of the graph, the features themselves would represent desirable embeddings.
Proposition 8 (Features cannot hurt they perfectly align with the graph structure). Let the feature matriz of the graph with diffusion matriz A and let the embedding dimension coincide with the fealure dimension g- If lm((A)) - Im(X), then there erists a weight malrir W with X = ÁXW.
This proposition shows that if Im(A) Im(AX), then the model can recover the features.
Proof. Since AX and X span the same subspace, we can find a W/ for any wi with Xw1 = AXwa and wy wy e R9, We interpret every column matrix as an independent vector to derive that for any matrix W1 can find matrix 222 with XW1 - ÁxW, and W1, W2 E goxg
The proposition suggests that if the features encode the same structure as the graph's adjacency matrix, they do not negatively restrict the solution space. We now consider the opposite case: if the node relations encoded by their features contradict the adjacency structure of the graph, we can neither recover the features nor the adjacency matrix. In this setting, features restrict the function space a harmful way, preventing the easiest and trivially optimal embedding. From these observations, we then derive definition to measure the alignment between a graph's structure and node features.
Proposition 9 (Features can hurt if they do not align with the graph structure). Let X be the graph's 's feature matriz, and assume that the embedding dimension coincides with the feature dimension, d = g. Let Á be the diffusion matrie and let Y Rexd be a matriz such that À A= YYT. Assume that the graphe can be perfectly represented in g dimensions, that is, there exists Z E IRnx8 with Zz A. Let rank(Y)= = rank(A) =
1. If Im((x) # Im(X), then there erists no weight matris W with X = AAW.
2. If [m(AX) o Im(x)* * Ø, then there erists no weight matrir W with Y ÂxW.
The intuition is that if the adjacency matrix and the node features define two different structures, then neither of the structures can be encoded by the lincar model. The aligument of the structures is captured by the condition on the image of AX and X.

---

Published in Transactions on Machine Learning Research (09/2023)
Proof of Part I. We prove the contraposition: If there exists a weight matrix W with X = AXW then Im(AX)= Im(X). Let À e gax" and let X E Raxg be full rank. Let W be such that X ÁXW. Since X is full rank, the rank of W is full and thus Im(X)= = Im(XXW) = II((AX.
Proof of Part 2. For Y Âxw XY to hold we need W to be the x g inverse of of (V X). We prove that if (AXX o Im(X)' * Ø. then yTX R is of rank smaller 9 and thus not invertible. We again prove the contraposition: If Y is full rank then Im(AX) o Im(X)- = {0]. Note that y is full rank by assumption and thus: Im(AX)
Im(YYTx) Im()). Generally it holds that Im(X)* = ker(X"). Let (XT). ). Since w is in Im(Y) there exists v IRd with
Im(Y) o ker(XT),
Yu. Since w in k,r(XT), it follows
that Y = X" w = O. This implics v = (X" = and thus w = 0 and thus km())oker(X") = (0). D
Note that the dol product is invariant under orthogonal transformatious: thus, for the features, every orthogonal transformation can be absorbed in the weight matrix. Proposition g also holds for orthogonally transformed features and embeddings. Thus given the dot-product as a decoder there is no other embodding y # Y that recovers the adjacency structure of the graph.
Based on all these insights, we propose a misaligument definition between graph and its node features. Inluitively, want to say that A and X are misaligned if AX and X do not span the same subspace. Definition 10 [Misalignment of graph and features). Let À be the symmetrically normalized adjacency matrix and X the normalized feature matrix such that each column has 12-norm 1. We measure misa lignmentt of graph A and its features X using the distance dalgn Rax R I, where the arccos function is applied to every entry in the matrix:
daigo X) - Tr(arccos( (((arccos(AXX))).
We got inspired to this measure by the geodesic distance on the Grassmannian manifold, which measures the principal angles of two subspaces AX and X. If dalgo is low, the alignment between A and X is high. It is easy to see that with this formulation, daign( (A, X) = 0 if A XXx.. This is consistent with our intuition that the features and structure of the graph are perfectly aligned if they encode the same structure.
The generalization error of linear encoders is task dependent. Learning and generalization can only work if the learning architecture encodes the correct bias for the given task. We now consider two tasks to demonstrate the negative and positive impact of the bias that introduce when using features.
In recent work, the most common task is link prediction. For this task we consider a graph given by its adjacency matrix A E {0, 1/ax0 and a feature matrix X E R=xe, We construct train graph A by deleting a set of edges from the graph, which we later, during test time, would like to recover. We train to minimize the loss I(A,)) X), while the test loss is given by X). In our opinion, link prediction is somewhat strange task when talking about generalization. We assume that the input graph is incomplete or perturbed. During training, we optimize the GAE for an adjacency matrix that we do not wish to recover during test time (because we also want to discover the omitted edges). However, this cannot be encoded in the loss of the auto-encoder (compare Eq. )2). For the encoding to discover the desired embedding, the necessary bias to prevent the model from optimally fitting the training data must be somewhere else in the model. We claim that the features introduce this necessary bias, and we evaluate the link prediction task because it is so prominent in the literature.
We consider second lask, node prediction. For this task, the is graph given by its adjacency matrix A E {0, 1| and the feature matrix X E Rax9, We construct a train graph A, X by deleting set of nodes from the graph and the corresponding features from the feature matrix X. We train to optimize 1(,, X). We then compute the test loss on the larger graph X: 1(A,X) X) with the goal of predicting the omitted nodes. The goal is to learn a mapping from the input graph to the latent space that generalizes to new, unseen vertices.

---

Published in Transactions Machine Learning Research (09/2023)
GCK
linear overlapping dimensions df
overlapping dimensions
8/
1.0
0.8
0.7
performatge
train performance
0.5
0.02
0.92
1.11
1.22
1.23
1.28
1.31
foature Ires
0.02
0.93
1.11
1.22
1.24
1.28
1.3
Teature Tests
normalized mismligimnn misllignment
normalized misaligmment
When features help. In the link prediction task, features help to regularize if they align with Á because they encode the larget structure. Along the x-axis we plot. the aligument. between the graph and the features with two different scores: on the bottom, we plot misalignment in Definition I0 (low is good alignment, high is bad aligument).. On the top, we show the aligument given by the number of overlapping dimensions of the two subspaces. The figures show train and test performance for the link prediction task the synthetic dataset described in Section S We embed the points into eight dimensions. We plot values for ten independently sampled graphs. The left figure shows results for the architecture with the relu encoder and the right figure shows results for the linear model.
Figure 2:
measured by daign; described
Intuitively it is clear that, depending the task, the usefulness of the introduced bias might vary. We empirically evaluate the influence of features and compare the performance of the linear and the nonlinear encoder with and without the bias of features.
5 Empirical evaluation
In this section, we evaluate the influence of node features and the role of their alignment both for linear and relu encoders. We will see that the results support the theory that linear encoders outperform relu encoders.
Setting. We consider two models for empirical evaluation. The first the relu encoder defined Equa- tion (1) based on the implementation of Kipf & Welling (2016b), and the second is the linear encoder. Since the relu encoder has two layers and thus two weight matrices, we realize the weights for the linear model accordingly: Zia AXx(") This definition does not contradict the one from above; we can simply choose W (r(1), Regarding the representational power of the model, this makes difference. How- over, from an optimization perspective, can influence the training (see Saxe et al. (2013)), and we aim compare the models fair as possible. We the same objective function as Kipf Welling (2016b), weighting the edges to tackle the sparsity of the graph and regularixing by their mean squared norm to prevent the point embeddings from diverging. We train using gradient descent and the Adam optimizer for 200 epochs. Due to sparsity, the accuracy of the recovered adjacency matrix is not very insightful. As is done in previous work, we measure the performance of the auto-encoders by the area under the receiver operating characteristic curve (AUC). To get a representative motric we use all present (positive) edges from the graph and uniformly sample the number of what call 'nogative' edges, that is, edges that are not present in the graph's 's adjacency matrix. As a result, we only use some of the entries of the adjacency matrix for evaluation and get balanced set of present and non present edges in the graph. To get representative results, we run every experiment 10 times. In real-workd dalasels, different edges or nodes each time. For the synthetic datasets, we draw ten independent graphs from the same generative model described below, then construct the test and train
randomize over the test set, drawing
these.
Datasets. We use the following generative model to get a synthetic dataset with aligned features. We draw 1000 data points from standard Gaussian distribution in g 64 dimensions. We normalize the

---

overlap of approximately 25% of Published in Transactions on Machine Learning Research (09/2023)
GCN
linear
overlapping dimeesions
overlapping dimensions
64
1.0
AUC
0.8
0.7
test performance
train performance
0.5
0.62
0.02
1
1.21
1.25
1.25
1331
fout fouture
0.62
0.92
1.11
1.21
1.24
1.25
1.34
feature
lese
fres
normalized misaligmmntt
normalized misalignment
Figure 3: When features harm. Adding features can harm the node prediction task performance, preventing optimal graph fitting. The x-axis shows the aligmment between the graph and the features with two different. scores: we plot the misalignment as measured by dalgn, described Definition [0 (low is good alignment, high is bad aligmment). On the top, we show alignment given by the number of overlapping dimensions of the two subspaccs. The figures show train and test performance for the node prediction task on the synthetic dataset described in Section 5 We embed the nodes into eight dimensions. We plot values for ten independently sampled graphs The left figure shows results for the architecture with the relu-encoder and the right figure shows results for the linear model.
points to lie the unit sphere and store their coordinates in a feature matrix X Rax0, We then construct the graph by thresholding the matrix XXT to get a 0- 0-1-adjacency matrix of density between 0.01 and 0.02. With this construction, the feature matrix and the graph adjacency matrix are as aligned as possible, given the dimensional restriction. We generate data that simulates misalignment as follows. We aim to construct features that overlap in d dimensions with the graph's optimally alignod, true features. Recall that changing the span does restrict the solution space, space. The feature matrix X is spanned by {ui..., ug]. We construct a perturbed feature matrix X Xprrturbod that has the same rank as and spans the first dimensions of the space; span(ui," .., Ud), but is orthogonal to the remaining space; span(ud+1,-o ug)- We do by calculating the singular value decomposition X UEVT, then choose the first d columns and the last d columns from U. Let U = [M,,.., un], we set Xpertunbed [u,...., Ugs "n-(a-d): un]. Note that the vectors "n=(g-d)=-" ... Un lic completely in the orthogonal complement of span( U1, ..., ug), which means that the span of the optimal features X and the perturbed features X Xparturbad overlap in exactly d dimensions. We calculate the misalignment between the graph A and the perturbed features Xperturted as Definition (10). By this construction, we do not fix the degree of rolation of the non-overlapping dimensions. As result, the misalignment values for an overlap of a specified dimension d can vary slightly in different runs. However, as we normalize the values with regard to the dimensions, we still get insights for quantitative comparison. For example, we get a misalignment value daigo of about 0.92 for an overlap of 32 dimensions on the synthetic dataset with 64 dimensions overall. This corresponds to an overlap approximately 50% of the dimensions. We get a misalignment value daiga of approximately 1.11 for an overlap of 16 dimensions, corresponding the dimensions.
can replace the features with any other basis of the same
As real world datasets we consider three standard benchmarks: Cora, Citeseer, and Pubmed. Similar to previous work, we embed the nodes into 16 dimensions when considering the link prediction task. For the node prediction task, embedding into dimension turns out to be too simple a task. We thus use 4 as the embedding dimension. For graph statistics of all used datasets and more details on the experimental sctup, see Appendix B.
When features help for link prediction. In Figure 2 we plot the AUC performance of both encoder variants, relu and linear, both with and without features, on the link prediction task. We observe that

---

Published in Transactions Machine Learning Research (09/2023)
relu citeseer
linear citeseer
cora
pubmed
cora
pubmed
AUG link prediction
1.00
+
+
1.00
0.95
0.90
0.90
0.85
0.85
0.80
0.75
0.75
with features
featureless
AUC prediction
1.01
1.01
1.00
1.00
0.99
0.99
0.98
0.98
0.97
+
0.97
0.95
0.95
tear
train
leat
brain
test
train
train
leat
train
test
train
Figure 4: Train and test performance for the three real-world datasets CoraCiteseerant Pubmed. Vertical lines indicate standard deviation. We consider relu and linear encoder models with and without features. Top: Link prediction task; we embed points into 16 dimensions. Bottom: Node prediction task, points are embedded into four dimensions. The normalized misalignment 0.86 for Pubmed.
0.67 for Cora, 0.69 for Citeseerand
both models' test performances usually decrease with increasing misalignment between the features and the graph. Adding fcatures decrcases the train performance, indicating that features restrict the solution space. Features may encode similarities in the feature space that are not present in the (incomplete) graph. This information restricts the solution space and help to recover those missing structures. Moreover, the featureless model shows high train performance while the test performance is low. This behavior is expected link prediction as optimal train performance implics sub-optimal test performance. In Figure f we observe the same behavior for the real-world datasets. The features add information about the target structure and improve the test performance. We suggest the following perspective: In the link prediction task, features act as regularizer preventing the model from encoding the training adjacency matrix optimally. they encode the desired graph structure, this regularivation makes the model more robust to perturbations in the adjacency matrix, which is basically the task for link prediction. Here we assume the input graph incomplete or perturbed, and want to be robust against these perturbations and still recover the original graph. If the features do not encode the desired structure, including them can harm the performance. The relu encoder, where the features are passed through a weight multiplication and a relu activation, turns out to be more robust to false information, possibly learning to ignore (parts) of the features. The lincar model can not compensate for erroneous feature information, which becomes visible in Figure where, with training error for the relu encoder drops slowly compared the linear encoder. We suspect slight overfitting in both settings when the overlapping dimension exceeds the embedding dimension. The effect declining test performance, even for very aligned features. In this case, the introduced bias via the features might be weak.
more significant misalignment,
When features harm. In Figure 3 we visualize the performance of the models in the node prediction task. We observe similar behavior for the architectures using features in the previous task. As expected, the performance decrcases for an increasing distance of alignment dalgn- Interostingly, the test performance stays close to the train performance, which indicates that both models generalize well unseen nodes and larger
10

---

Published in Transactions on Machine Learning Research (09/2023)
graphs. Supporting our intuition, we observe that for both encoders, the featureless versions outperform the architectures using features. In the node prediction task, restricting the representational power by adding features harms the model's performance. Our experiments for the node prediction task show that featureless models can outperfor the versions including features. Contrary to the link prediction task, in the node prediction setting, we assume that the given graph adjacency matrix already encodes the target structure of every node in the graph. Even the features align optimally with the adjacency matrix, they do not hold additional information that is not already encoded in the adjacency matrix. In this setting, features still add a bias, but assuming that the given adjacency matrix is noiseless, they restrict the solution space in an undesired way.
In practice and real-world data, we usually do not know whether the given features encode the correct structure or if the graph complete. So, not all of the intuition discussed above directly applies. We compute the normalized distance as given by dalgu and observe that the alignment. is generally very good, with values of 0.6709 and 0.6940 for Cora and Citeseer, respectively. Misalignment is still good but slightly worse for Pubmed with value of 0.8577, which indicates that almost 50% of the dimensions are misaligned. For the three benchmarks and the node prodiction task, embedding into 16 dimensions already achieves nearly perfect recovery for all models. This reinforces our discussion about Assumption 2 being weak to no restriction. Usually, one would choose the smallest possible embedding dimension that shows promising results. See Appendix [C] for the performance when embedding into 16 dimensions. We embed the data into only four dimensions to get more insightful results. In Figure | we see that for the Cora and the Citeseer datasets, the models using features perform slightly better than those without features. This behavior could indicate noise in the input adjacency matrix, which the feature information regularizes. For the Pubmed dataset, where the features are slightly less aligned, not using the features seems to perform better. However, this difference is minimal. Compared to the synthetic datasct and Pubmed, the two networks from Cora and Citeseer have significantly higher feature dimensions in relation to the number of nodes possibly encoding redundancy. In summary, our findings indicate that the features encode mostly the correct structure, and adding them can improve optimization even for features with almost no additional information.
6 Conclusion
This work presents a thcoretical perspective on the reprosentational power and the inductive bias of graph auto-encoders, We consider relu architecture and a linear architecture for the encoder. We prove that the linear encoder has greater representational power than nonlinear encoders. Theorem 5 also extends to more advanced models with similar encoder architecture and even to other nonlinear graph functions. Based on our experiments and empirical work in the literature, the nonlinear structure of the relu auto-encoder does not improve learning compared to the linear encoder. Our evaluations support the idea that the introduced bias from the nonlinearity is not the crucial ingredient to reducing the solution space in a meaningful way. On the other hand, the features can introduce powerful inductive bias to both encoder architectures, improving their test performance. Whether features improve training and test performance heavily depends on the task we want to solve. For the two example tasks we consider in this paper, fcatures help with link prediction but do not help node prediction. However, supporting the idea that linear encoders have larger representational power in training and can generalize, the linear encoder outperforms the nonlinear one in both tasks.
Acknowledgments
This work has been supported by the German Research Foundation through the Cluster of Excellence Machine Learning New Perspectives for Science' (EXC 2064/1 1 number 390727645) and the International Max Planck Research School for Intelligent Systems (IMPRS-IS).
References
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. AAAI Conference Artificial Intelligence, 2016.
11

---

Published in Transactions Machine Learning Research (09/2023)
Benjamin Paul Chamberlain, James Clough, and Marc Peter Deiscnroth. Neural emboddings of graphs hyperbolic space. preprint arXi:: 1705. 10359, 2017.
Shiyu Chang, Wei Han, Jiliang Tang, Guo-Jun Qi, Charu C. Aggarwal, and Thomas S. Huang. Heterogeneous network embodding via doep architecturcs. International conference on knowledge discovery and data mining (KDD), 2015.
Tim R. Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M. Tomezak. Hyperspherical variational auto-encoders. Conference on Uncertainty in Artificial Intelligence (UAI), 2018
Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. Metapath2vec: Scalable representation learning for heterogeneous networks. International conference on knowledge discovery and data mining (KDD), 2017.
Aditya Grover and Jure Leskovec, Node2vee: Scalable feature learning for networks. International conference on Knowledge discovery and data mining (KDD), 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs Neural Information Processing Systems (NeurIPS), 2017a.
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. preprind orXio: 709117990000 709.05584. 2017b.
Thomas N. Kipf and Max Welling. Seni-supervised classification with graph convolutional networks. preprint arXiv:1609 02907, 2016a.
Thomas N Kipf and Max Welling, Variational graph anto-encoders. NearIPS Workshop Bagesion Deep Learning, 2016b.
Xuelong Li, Hongyuan Zhang, and Rui Zhang, Adaptive graph auto-encoder for general data clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. International Joint Conference on Artificial Intelligence, 2018.
Leonardo F.R. Ribeiro, Pedro H.P. Saverese, and Danicl R. Figueirodo. Strue2vee: Learning node represen- tations from structural identity. International conference on knowledge discovery and data mining (KDD), 2017.
Guillaume Salha, Romain Hennequin, and Michalis Vazirgiannis. Simple and effective graph autoencoders with one-hop lincar models. European Conference, ECML PKDD, 2020.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlincar dynamics of learning in deep linear neural networks. arXiv preprint erXie:191..6 6120, 2013.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Largo-scale information network embedding. pp. 1067 1077. International conference on world wide web (WWW), 2015.
Vaibhav, Po-Yao Huang, and Robert Frederking. Rwr-gae: Random walk regularization for graph auto encoders. arXio preprind 1908 1908.0000 2019.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. International conference on Knowledge discovery and data mining (KDD), 2016.
Felix Wu,, Tianyi Zhang, Amauri H. Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. International Conference on Machine Learning (ICML), 2019.
12

---

Published in Transactions Machine Learning Research (09/2023)
A Proofs
In this Section, we provide the proofs of Lemma aand Corollary 6 and discuss the consequences.
Lemma 4 (Orthogonal Transformation). For P gaxd A Raxm, rank(P) & rran( (A), there exists an orthogonal matrix R with span 2 span(P).
Proof of Lemma 3 rank(2) ronk(A) k.
Im(A) is spanned by an orthogonal normal basis (ui=1....d...kk [m( is spanned by an orthogonal normal basis {U:=I....d)
( U1
ud ... and ; ( -. Wd (
Let U==
( ua 0 U U sspan() () E spaan RA).
Then with R = V
Corollary
6 (Representational power of GAEs). For any (trained) graph auto-encoder
Zeelu X there exists an equivalent, featureless linear encoder in Zim, that can achieve the same training loss: Zin 2 Zrelu-
Proof of Corollary c Let Zin(W) = Ā W for W e R=*f be the latent representation of the linear model with weights W. We can write the latent representation for any GAE as a linear function of the form (W))
Á W for some matrix W E W, where W is the set of matrices that can be represented by the relu term in the function: W =
: w E Raxdd w() e Rdxf] s Ra*x We now define the possible latent embeddings that the two models can learn. For the relu encoder we have
Zreiu (W) for all W W), and for the linear model we get Zim (Zin(W) for all W e R=xs). Since W = R=*5, the set of learnable embeddings of the relu encoder is a true subspace of all learnable embeddings of the lincar encoder: Zrchu (åW W e W] (ÁW W R=xa) Zim- It follows that, given any loss I, the lincar model can achieve at least as good performance as the relu encoder: inf ((Tretu) > inf 17in).
Zratat Zrain
Zant Zain
Consequences. To better understand the implications of Corollary 6 is instructive to engage in the lollowing thought experiment. Consider the slandard supervised learning setting with a training data matrix e Rexd and labels E R. For any function (say a deep neural network) f Raxd + R", , it is possible to express f(U)
UW, for some W gdx1 if and only if U has right inverse. This is a mild requirement if d >> n. Note that this is precisely the "underdetermined" or "high-dimensional" setting where it is possible to find a linear map that perfectly fits the training data to the function values. < n, the right inverse cannot exist; therefore, one cannot find such W. Let contrast this with our setting of GNNs in Corollary 6 Since we consider graph networks, the input is the adjacency matrix E IRax=, that is, we have feature dimensions equal to sample size (n = d). If Á is full rank, one can similarly find a linear map that perfectly fits the out of any nonlinear mapping of the input data. While it may seem surprising at first glance, it is intuitively clear that in high dimensions, one can always find a lincar map that perfectly fits the outputs of any nonlinear mapping. If the model is restricted to the input data domain, we can attain the same "training loss". But even if Á was not full rank, in the graph auto-cncoder setting, the GCN's last layer has linear activation, restricting the solution space in exactly the same way the linear model does.
f(U)
13

---

Published in Transactions Machine Learning Research (09/2023)
B
Experimental details
For our empirical evaluation we consider one synthetic dataset and three real world citation networks; Cora, Citeseer and Pubmed. Table shows the graph statisties for the considered datasets.
dataset
nodes
edges
density
dim. features
Cora
2708
5278
0.00143
1433
Citeseer
3327
4614
0.00083
3703
Pubmed
19717
44324
0.00023
500
Synthetic
1000
10000
20000
0.01
0.02
64
Table 1: Graph statistics of the real world datasets and averaged values in the synthetic setting.
For every dataset we compute the performances for two different tasks; node and link prediction, and four different models: using the relu encoder and the linear encoder once with features and also without features. So we compute performances in eight different settings for each dataset.
Every graph is split into train, validation and test sets with ration of 70/10/20. So training always happens on either 70% of the edges and all nodes for the link prediction lask, or on only set of 70% the nodes for the node prediction task. Test performance then evaluated on 90% of the edges / nodes. We do use the parts of the graph used for validation.
The code for the relu graph auto-encoder is publicly available with an MIT license.
We run the experiments on internal cluster on Intel XEON CPU 25-2650 2/4 and GeForce GTX 1080 Ti. All experiments on the synthetic dalasel lake about 9 hours on single CPU and single GPU. Experiments for Cora and Citeseer take about 4 and hours respeetively. For the Pubmed dataset, which is the largest one, rumning all 8 setups took about days on a single CPU and two GPUs.
C Additional experiments
For the real world datasets and the link prediction task we show result for embedding into 4 dimensions in the main paper. Table S show results when embedding into 16 dimensions. All models show near optimall performance which indicates that embedding into 16 dimensions is barely restriction and too simple of lask.

---

Published in Transactions Machine Learning Research (09/2023)
COT8
edge
node
linear
GAE
linear
GAE
features
0.91 + 0.0088
0.88 + 0.0123
0.99 = 0.0009
0.99 + 0.0014
featureless
0.84 + 0.0078
0.85 + 0.0122
0.98 + 0.0027
0.98 + 0.0016
citeseer
edge
node
linear
GAE
linear
GAE
features
0.92 + 0.0087
0.84 + 0.0264
0.99 + 0.0010
0.99 + 0.0012
Teaturcless
0.78 + 0.0131
0.78 + 0.0149
0.98 = 0.0015
0.98 0.0014
pubmed
edge
node
linear
GAF
linear
GAE
features
0.96 + 0.0018
0.92 + 0.0037
0.98 + 0.0006
0.97 + 0.0055
featureless 0.83 + 0.0056
0.83 = 0.0049
0.99 = 0.0009
0.99 = 0.0006
Table Test performance in terms of AUC for the three real world datasets Cora Citeseer and Pubmed with given standard deviations. We consider relu and linear encoder models with and without features. Top row: Link prediction task, points are embedded into 16 dimensions. Bottom row: Node prediction task, points are embedded into 16 dimensions.


Reviews:
[{"review_id": "2JQyjBgfvB", "reviewer": "Reviewer_cPgu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrength: \n\nthe analysis of the relation between linear space and the space of graph autoencoders is thorough and solid. The analysis of the alignment of node features and the adjacency matrix is insightful. Even though the graph autoencoder is an old model, a thorough understanding of this model is useful because it is the basis of many other models. \n\nWeakness:\n\nThe proposed work analyzes a basic version of graph autoencoder, whose weakness mainly comes from the training objective, which is basically the form of low-dimensional decomposition of the adjacency matrix. However, there are many recent developments in the graph autoencoder (just give two examples [1] and [2]). These later works use more complex decoders. In particular, they also decode node attributes at the same time. Therefore, it is unknown how to carry out the analysis in this submission to a larger family of models. \n\n\n[1] Chen, Xiaohui, Xi Chen, and Liping Liu. \"Interpretable Node Representation with Attribute Decoding.\" Transactions on Machine Learning Research (2022).\n[2] Tang, Mingyue, Pan Li, and Carl Yang. \"Graph Auto-Encoder via Neighborhood Wasserstein Reconstruction.\" International Conference on Learning Representations. 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission compares graph autoencoders against linear decompositions of the adjacency matrix. The work points out that: given a fixed graph with features (A and X are fixed), a linear decomposition model achieves the lowest training loss, i.e. the loss of reconstructing the adjacency matrix. The submission further investigates when node features are helpful for the task of link predictions. It reveals that node features that better \"align\" the adjacency matrix are more beneficial to link predictions. Experiments on link prediction tasks support the theoretical analysis. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here is a list of detailed comments: \n\n1. In the \"Contributions\" paragraph: \"relu encoders\" are not well defined yet. I believe it is the non-linear encoder constructed by a GNN. \n\n2. $\\tilde{A}$ is first defined as the \"symmetrically normalized adjacency matrix\", but it is referred to by the \"diffusion matrix\" later. \n\n3. In Lemma 4, can you write $\\mathrm{span}(P) \\subseteq \\mathrm{span}(RA)$ so it is easier to read with a consistent order of $P$ and $A$. \n\n4. I think the proof of Theorem 5 is still not clear enough that $A$ and $X$ (and also $\\tilde{A}$) are fixed and given. The notation of $\\mathcal{Z}$\\_$f_{\\theta}$ is also problematic: since $A$ and $X$ are fixed, $f_\\theta$ should be variable and give the space $\\mathcal{Z}$, but the notation indicates that there is only one $f_\\theta$. \n\n5. Proposition 8: I don't understand the statement in the bracket: \"Proposition 8\". How does the proposition indicate that \"features cannot hurt\"? What does $\\mathrm{Im}(X)$ mean?\n\n[Update: openreview does not allow two-level subscript -- use underscore symbol instead.]\n\n", "broader_impact_concerns": "No concern. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dXqPv8yujB", "reviewer": "Reviewer_KyS4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The investigation of the theoretical relationship between linear and nonlinear graph encoders is interesting and sheds light on the future consideration of the inductive bias in graph auto-encoders.\n* The theoretical foundations for the analysis of the alignment of graphs and features are concrete with insights. Experiments are carefully designed and are conducted on both synthetic and real-world graph datasets.\n* The paper is generally well-written and almost clear everywhere. I enjoyed reading through this manuscript. The revised version explicitly discusses the three assumptions, which delivers clearer background on the theoretical findings and I appreciate the efforts from the authors.\n\nWeaknesses:\n\n* My concerns are mainly from the empirical evaluation. It would be better additionally evaluate the graph generation task which is more aligned with the regular employment of graph auto-encoders, though it is also reasonable for the selected two tasks on link prediction and node classification. An interesting notice from Figure 4 is that the std for relu encoder models seems to be larger than linear encoders in most datasets in both tasks, could the authors provide some insights into this phenomenon? \n\n* The included misalignment scores for three real-world datasets are informative to support the theoretical results in Section 4. Meanwhile, it would be better to also discuss the misalignment scores on synthetic datasets to demonstrate how good the alignment scores are for real-world datasets.\n\n* A minor suggestion is that it would be interesting to discuss how the choice of embedding dimension $d$ affects the performance of linear and non-linear variants for the same task, especially when $d$ getting close to the rank of diffusion matrix $\\hat{A}$ according to Assumption 2.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper theoretically studies how the roles of non-linear activation functions and features in graph auto-encoders. On one hand, the authors prove that a linear encoder has a larger solution space than a nonlinear encoder, which indicates greater representational power. On the other hand, the authors find that the features play an important role in introducing inductive bias on both linear and nonlinear encoder architecture. Empirical evaluations on both synthetic and real-world datasets support the theoretical foundations of both link prediction and node classification tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My concerns are mainly from the part of empirical evaluation. Please kindly refer to Section Strengths and Weaknesses for detailed suggestions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zTxBCmS7WB", "reviewer": "Reviewer_wg8j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The paper provides a useful tool to study the \"power\" between two models, and an interesting conclusion on the relationship between linear and non-linear GAE models.\n- The theoretical study is in-depth: authors analyze the scenarios when node features are absent or not, and when node features align to graph structures.\n- Analysis seems to be correct to me, but I might overlook some details.\n- The assumptions of analysis make sense to me, after removing the old full-rank assumption. Please refer to my summary.\n- The analysis is applicable to GNNs with more than two layers, which add additional merits.\n\nIn general, the revision addresses my previous concerns. I also find the analysis in Sec. 4 interesting, especially Prop. 7&8. Can authors further connect them with the phenomenons of homophily/heterophily in graph data?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "I do the initial review of the paper, and I check the revision. I am generally satisfied with the revised version, and my review will be a combination of the previous plus new comments on the revision.\n\nThe paper conducts a theoretical study on the relationship between linear and non-linear graph auto-encoder (GAE) models, motivated by the observations from the recent literature that, simple linear models can perform on par with the non-linear counterpart. The conclusion is, under certain conditions, the routine ReLU-based non-linear GAE is not more powerful than the linear one. The main approach to reach the conclusion is by checking the solution space between models, in simple words is: checking whether the optimal solution of model A can be ever achieved by model B --> if yes, model A is not more powerful than B.\n\nIn the previous version, the analysis is built on the full-rank assumption on the adjacency matrix which is less practical. The revision replaces the assumption with a weaker and more reasonable one, i.e. the rank of the adjacency matrix is higher than the feature matrix (one special case is full-rank as before). In this way, the adjacency matrix is more informative than the feature matrix thus linear encoders, mining less from node features, can perform comparably to non-linear models in optimization. This meets my empirical intuition.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a resubmission of a previous TMLR submission which was rejected with encouragement to resubmit. The same three reviewers assessed the new version. They agree their concerns have been addressed and unanimously vote for acceptance of the paper.

There are a couple of minor points that would be great to include in the camera-ready version:
+ A discussion about the missalignment information in the synthetic experiments.
+ A discussion of the coice of the embedding dimension $d$ (only if relevant or interesting).
+ Change the color scheme of Figures 2 and 3 to make them friendly to color-blind readers.
Decision: Accept (poster)