  A seminal work of [Ahn-Guha-McGregor, PODS'12] showed that one can compute a
cut sparsifier of an unweighted undirected graph by taking a near-linear number
of linear measurements on the graph. Subsequent works also studied computing
other graph sparsifiers using linear sketching, and obtained near-linear upper
bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS'14] and
first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA'21].
All these linear sketching algorithms, however, only work on unweighted graphs.
  In this paper, we initiate the study of weighted graph sparsification by
linear sketching by investigating a natural class of linear sketches that we
call incidence sketches, in which each measurement is a linear combination of
the weights of edges incident on a single vertex. Our results are:
  1. Weighted cut sparsification: We give an algorithm that computes a $(1 +
\epsilon)$-cut sparsifier using $\tilde{O}(n \epsilon^{-3})$ linear
measurements, which is nearly optimal.
  2. Weighted spectral sparsification: We give an algorithm that computes a $(1
+ \epsilon)$-spectral sparsifier using $\tilde{O}(n^{6/5} \epsilon^{-4})$
linear measurements. Complementing our algorithm, we then prove a superlinear
lower bound of $\Omega(n^{21/20-o(1)})$ measurements for computing some
$O(1)$-spectral sparsifier using incidence sketches.
  3. Weighted spanner computation: We focus on graphs whose largest/smallest
edge weights differ by an $O(1)$ factor, and prove that, for incidence
sketches, the upper bounds obtained by~[Filtser-Kapralov-Nouri, SODA'21] are
optimal up to an $n^{o(1)}$ factor.
