We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E.
Alongside the graph, you are given an embedding of the graph in k-d space. Let the embedding function be P: V -> R^k.
For each node v in the graph, I want to compute its corresponding r such that: for all u, if Dist(P(v), P(u)) < r then (v, u) in E
In other terms, for every node v in the graph, I want to define a hyper-sphere with center v and radius r, such that all the points inside the sphere correspond to neighbors of v. Points lying outside the sphere can be a neighbor of v, but I want to maximize r until it reaches a roadblock or covers all neighbors. r should be the minimum of
{distance between v and its farthest neighbor, distance between v and its closest non-neighbor}.
One trivial way to do it is to compute the distance matrix and proceed from there. But computing that matrix requires O(n^2) time. Is it possible to do this in linear time or almost-linear time?
I'm sure that this is impossible. Just scatter n vertices around randomly. Connect each vertex to the nearest half of vertices. Now remove one edge. I'm pretty sure that there is no way to find the two vertices whose r was just reduced without a brute force search of the edges, which takes O(k n^2).
If k is large, you additionally run into the Curse of Dimensionality. Any kind of smart search by distance now becomes prohibitive.
But in few dimensions, with few edges and small radii, you can improve on brute force. Just throw your vertices into a k-d tree and then do an expanding nearest neighbors search until you find the last edge, or the first non-edge. The efficiency of this search will depend on k. And again, its speedup can only work if relatively few vertices will be within distance r.