  Graph sparsification is a technique that approximates a given graph by a
sparse graph with a subset of vertices and/or edges. The goal of an effective
sparsification algorithm is to maintain specific graph properties relevant to
the downstream task while minimizing the graph's size. Graph algorithms often
suffer from long execution time due to the irregularity and the large
real-world graph size. Graph sparsification can be applied to greatly reduce
the run time of graph algorithms by substituting the full graph with a much
smaller sparsified graph, without significantly degrading the output quality.
However, the interaction between numerous sparsifiers and graph properties is
not widely explored, and the potential of graph sparsification is not fully
understood.
  In this work, we cover 16 widely-used graph metrics, 12 representative graph
sparsification algorithms, and 14 real-world input graphs spanning various
categories, exhibiting diverse characteristics, sizes, and densities. We
developed a framework to extensively assess the performance of these
sparsification algorithms against graph metrics, and provide insights to the
results. Our study shows that there is no one sparsifier that performs the best
in preserving all graph properties, e.g. sparsifiers that preserve
distance-related graph properties (eccentricity) struggle to perform well on
Graph Neural Networks (GNN). This paper presents a comprehensive experimental
study evaluating the performance of sparsification algorithms in preserving
essential graph metrics. The insights inform future research in incorporating
matching graph sparsification to graph algorithms to maximize benefits while
minimizing quality degradation. Furthermore, we provide a framework to
facilitate the future evaluation of evolving sparsification algorithms, graph
metrics, and ever-growing graph data.
