In general, probably not, as we do not know how the point set is distributed. If you are lucky, there are a couple things to try which may yield results quickly.

The first uses the assumption that the distances have been computed and placed in a doubly linked list sorted by length. Now start at both ends. In alternating steps, if an edge length has distance at most r, increment two counters, one for each vertex on that edge. If an edge length is greater than r, decrement two other counters, one for each vertex on that edge. Stop when the transition from less than r to more than r has been reached at either end. Now poll the appropriate set of counters to see what maximum value has been reached. If your value is close to zero or close to n, you may reach it in sub quadratic time. This works when you have one point set and lots of values of r to test, for then you can amortize the preprocessing time of sorting edges by length.

The second assumes that the metric satisfies the triangle inequality. Take some small number of points, say three, and for each point create an ordered list of distances from that point. If you are lucky, you will get a range from near zero to much greater than 2r for each distance.

Now for each vertex v, find its distance from each of the three points, and then build a list of points to check. This list will be the intersection of three other lists, each which have a distance value within r of that value v has. If all goes well, you will end up checking much fewer than n points for each v. This works when the spread of distances is substantial and r is small. If r is large, hopefully you found that out from the three initial points, and can do something else to determine the value.

Gerhard "Sometimes You Need Lucky Data" Paseman, 2019.08.07.