{"ID":2882574,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.09412","arxiv_id":"2508.09412","title":"A pseudo-inverse of a line graph","abstract":"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.","short_abstract":"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 o...","url_abs":"https://arxiv.org/abs/2508.09412","url_pdf":"https://arxiv.org/pdf/2508.09412v2","authors":"[\"Sevvandi Kandanaarachchi\",\"Philip Kilby\",\"Cheng Soon Ong\"]","published":"2025-08-13T01:04:30Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\",\"math.OC\"]","methods":"[]","has_code":false}