# Predicting Graph Edge Connections

I have a set of nodes in 3d physical space. Some of those nodes are connected to one another by a graph edge, while others are not. Just because two nodes are physically close doesn't necessarily mean they're connected. (For example, Node A and Node B might be physically next to each other, but there's no graph edge permitting travel between them.) I know about the existence of all of the nodes in advance, but I don't necessarily know their exact physical locations. I don't know any of the edges in advance.

An observer moves around in this graph using an instrument to determine which node they're currently located at. The instrument is reasonably accurate, but will sometimes confuse a node for a different node close by. For example, usually when the observer is at Node A, the instrument will read "Node A." Sometimes, it will read "Node B." The instrument is capable of giving a confidence score.

If the observer moves around this graph for an extended period of time and I have continuous readings from the instrument, can I learn the graph? (Assume readings are close enough together such that there's no "gaps" in time where the observer moved more than 1 node.) Essentially, I'd need to separate transitions (Node A -> Node B) that occur because of real edges in the graph from transitions from spurious transitions that occur because the instrument gave a false reading.

I've done quite a bit of Googling, but I can't seem to find much about this specific problem. Most of the "edge prediction" literature seems to be about predicting new graph edges when a bunch of graph edges are already known (e.g., in social networks). But, this is not relevant to my problem.

Is there a body of literature I should be looking at? A search term might even suffice as an answer to my question.

This also relates significantly to a hidden Markov model, but I don't know any of the transition or emission probabilities in advance and essentially want to learn transition probabilities...