  In this work we provide a new technique to design fast approximation
algorithms for graph problems where the points of the graph lie in a metric
space. Specifically, we present a sampling approach for such metric graphs
that, using a sublinear number of edge weight queries, provides a {\em linear
sampling}, where each edge is (roughly speaking) sampled proportionally to its
weight.
  For several natural problems, such as densest subgraph and max cut among
others, we show that by sparsifying the graph using this sampling process, we
can run a suitable approximation algorithm on the sparsified graph and the
result remains a good approximation for the original problem. Our results have
several interesting implications, such as providing the first sublinear time
approximation algorithm for densest subgraph in a metric space, and improving
the running time of estimating the average distance.
