通过最小边修改恢复线图对应的原图，实现线图的伪逆操作。
A pseudo-inverse of a line graph
- 构建线图的最小边编辑整数规划模型，实现伪逆恢复。
- 理论证明在谱范数下伪逆操作稳定可靠。
- 适用于图结构修复与反演任务，适合图学习研究者。
线图是将原图的顶点转换为边的一种图表示，但并非所有图都有对应的原图，因此图到线图的映射不可逆。本文研究线图空间中存在微小扰动时，如何恢复其对应的原图，本质上定义了线图操作的伪逆。提出一个线性整数规划模型，通过编辑最少数量的边使线图可逆。利用谱范数从理论上证明该伪逆操作具有良好性质。在Erdős-Rényi图上的实证实验表明，理论结果在实践中有效。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。