A pseudo-inverse of a line graph
This work addresses a graph theory problem for researchers in mathematics and computer science, but it is incremental as it builds on known limitations of line graph invertibility.
The paper tackles the problem of inverting the line graph transformation, which is not generally invertible, by proposing a method to recover the root graph from a perturbed line graph with minimal edge edits. Empirical results on Erdős-Rényi graphs demonstrate that the theoretical findings are effective in practice.
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 Erdős-Rényi graphs show that our theoretical results work in practice.