A pseudo-inverse of a line graph

Graph perturbations are used to test robustness of algorithms. The expectation is that for small graph perturbations algorithm output should not change drastically. While graph perturbations are extensively studied in many contexts, they are underexplored for line graphs, where a line graph is an alternative representation of a graph obtained by mapping edges to vertices. But line graphs are increasingly used in many graph learning tasks including link prediction Cai et al. (2021), expressive GNNs Y ang & Huang (2024) and community detection Chen et al. (2019), and in other scientific disciplines Ruff et al. (2024), Min et al. (2023), Halldórsson et al. (2013). The reason that line graph perturbations are not commonly used is because the perturbed graph may not be a line graph. We introduce a pseudo-inverse of a line graph, which generalises the notion of the inverse line graph extending it to non-line graphs. The proposed pseudo-inverse is computed by minimally modifying the perturbed line graph so that it results in a line graph.