# Relating graph auto-encoders to linear models

arXiv: https://arxiv.org/abs/2211.01858 · HTML: https://mlsanity.com/paper/2211.01858/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 19 references that are in the map.
- First posted on arXiv 3 Nov 2022.

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Hyperspherical Variational Auto-Encoders](https://mlsanity.com/paper/1804.00891/) (2018)
- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [Adaptive Graph Auto-Encoder for General Data Clustering](https://mlsanity.com/paper/2002.08648/) (2020)
- [Simple and Effective Graph Autoencoders with One-Hop Linear Models](https://mlsanity.com/paper/2001.07614/) (2020)
- [RWR-GAE: Random Walk Regularization for Graph Auto Encoders](https://mlsanity.com/paper/1908.04003/) (2019)

## Built on by (most cited first, 2 of 2)

- [Inductive biases in deep learning models for weather prediction](https://mlsanity.com/paper/2304.04664/) (2023)
- [Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)](https://mlsanity.com/paper/2509.10337/) (2025)

## Abstract (arXiv)

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.