# A pseudo-inverse of a line graph

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 29 references that are in the map.
- First posted on arXiv 13 Aug 2025.

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

- [Line Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2010.10046/) (2020)

## Abstract (arXiv)

Line graphs are an alternative representation of graphs where each vertex of the original (root) graph becomes an edge. However not all graphs have a corresponding root graph, hence the transformation from graphs to line graphs is not invertible. We investigate the case when there is a small perturbation in the space of line graphs, and try to recover the corresponding root graph, essentially defining the inverse of the line graph operation. We propose a linear integer program that edits the smallest number of edges in the line graph, that allow a root graph to be found. We use the spectral norm to theoretically prove that such a pseudo-inverse operation is well behaved. Illustrative empirical experiments on ErdHos-R'enyi graphs show that our theoretical results work in practice.