  Graph sketching is a powerful paradigm for analyzing graph structure via
linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has
since found numerous applications in streaming, distributed computing, and
massively parallel algorithms, among others. Graph sketching has proven to be
quite successful for various problems such as connectivity, minimum spanning
trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the
problem of approximating shortest path metric of a graph, and specifically
computing a spanner, is notably missing from the list of successes. This has
turned the status of this fundamental problem into one of the most longstanding
open questions in this area.
  We present a partial explanation of this lack of success by proving a strong
lower bound for a large family of graph sketching algorithms that encompasses
prior work on spanners and many (but importantly not also all) related
cut-based problems mentioned above. Our lower bound matches the algorithmic
bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to
lower order terms, for constructing spanners via the same graph sketching
family. This establishes near-optimality of these bounds, at least restricted
to this family of graph sketching techniques, and makes progress on a
conjecture posed in this latter work.
