  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.
