A pseudo-inverse of a line graph
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915540547665920 |
|---|---|
| author | Kandanaarachchi, Sevvandi Kilby, Philip Ong, Cheng Soon |
| author_facet | Kandanaarachchi, Sevvandi Kilby, Philip Ong, Cheng Soon |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09412 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A pseudo-inverse of a line graph Kandanaarachchi, Sevvandi Kilby, Philip Ong, Cheng Soon Machine Learning Optimization and Control 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. |
| title | A pseudo-inverse of a line graph |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2508.09412 |