The metric backbone of a weighted graph is the union of all-pairs shortest paths (i.e., simply remove all the edges that do not belong to the shortest path). Because (i) the metric backbone is relatively simple to build (compute all-pair shortest paths) and (ii) it preserves many properties (either exactly such as graph distances) or approximately (Page rank score, random walks, spreading processes, communities), this is a good candidate for graph sparsification [1].

In a recent work, we proved that the metric backbone preserves the community structure. We also observed numerically that the metric backbone preserves the communities better than spectral sparsifiers [2]. (This is still unpublished work but the preprint will be soon available.)

The goal of this project is to explore other potential uses of the metric backbone, for example:

• comparing networks using their APSP structure;
• comparing different graph sparsification for various tasks (such as GNN);
• other network analysis tasks such as denoising graphs or link prediction.

This project is open for bachelor's or master's students and can be accommodated for several (2 or 3) students working together.

[1] Kalavri, V., Simas, T., & Logothetis, D. (2016). The shortest path is not always a straight line: leveraging semi-metricity in graph analysis. Proceedings of the VLDB Endowment, 9(9), 672-683.

[2] Spielman, D. A., & Srivastava, N. (2008). Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium on Theory of computing (pp. 563-568).