I’m attempting to solve the Time Difference of Arrival (TDoA) multilateration problem using a Graph Neural Network, implemented in TensorFlow. The problem statement is as follows: given the known coordinates of 4 “receivers” and the difference in arrival times of some signal between any two such receivers, I wish to determine the entirely unknown coordinates of the signal source. There are many existing ways to solve this problem. I’m pursuing this particular direction out of pure curiosity.
I’ve decided to describe the problem as a fully-connected homogenous graph with 5 nodes, where the “feature” associated with each node is its 3-dimensional coordinates, and the feature associated with each edge is the associated pairwise arrival time difference (e.g. the feature associated with the edge between nodes 1 and 2 is the signal arrival time difference between transmitters 1 and 2). The 5th node is the signal source, and in practice we know neither its coordinates nor the feature associated with any of the edges connecting it to the remaining nodes (i.e. the distance between the source and any given transmitter).
While I’ve had graph theory, I’m entirely new to the theory of GNN’s, and I’m finding the TensorFlow GNN documentation to be a bit obtuse. I’ve begun working out a rough sketch of the code in Python, starting by defining the graph schema in a file graph_schema.pbtxt as follows:
node_sets {
key: "node"
value {
description: "The nodes comprising the network (4 receivers + 1 signal source)."
features {
key: "coordinates"
value: {
dtype: DT_FLOAT
shape: { dim: { size: 3 } }
}
}
}
}
edge_sets {
key: "pseudorange"
value {
description: "The arrival time differences."
source: "node"
target: "node"
features {
key: "differences"
value: {
dtype: DT_FLOAT
}
}
}
}
Again, each node is associated with a set of three dimensional coordinates, and each edge with a pairwise arrival time difference. I then attempt to create a graph specification from this schema, and begin producing some training data:
import tensorflow as tf
import tensorflow_gnn as tfgnn
import numpy as np
graph_schema = tfgnn.read_schema("./graph_schema.pbtxt")
graph_spec = tfgnn.create_graph_spec_from_schema_pb(graph_schema)
def make_graph_tensor():
# Generate random coordinates for 5 nodes, where the 5th node is the "transmitter"
node_coordinates = np.random.random(size=(5,3))
# Compute the arrival times, pairwise arrival time differences
c = 299792
arrival_times = np.sum(np.sqrt((node_coordinates - node_coordinates[4])**2), axis=1) / c
arrival_times = arrival_times[:, np.newaxis]
time_differences = arrival_times - arrival_times.T
time_differences = time_differences[np.triu_indices(len(time_differences), k=1)]
# Define the node adjacency (fully connected graph)
sources = [0,0,0,1,1,2,0,1,2,3]
targets = [1,2,3,2,3,3,4,4,4,4]
node_adjacency = tfgnn.Adjacency.from_indices(source=('node', tf.cast(sources, dtype=tf.int32)),
target=('node', tf.cast(targets, dtype=tf.int32)))
# Create GraphTensor object
network = tfgnn.NodeSet.from_fields(features={'coordinates': node_coordinates}, sizes=tf.shape(node_coordinates))
pseudoranges = tfgnn.EdgeSet.from_fields(features={'differences': time_differences},
adjacency=node_adjacency,
sizes=tf.shape(time_differences))
return tfgnn.GraphTensor.from_pieces(node_sets={'node': network}, edge_sets={'pseudorange': pseudoranges})
print(graph_spec.is_compatible_with(make_graph_tensor()))
In make_graph_tensor(), I attempt to create a GraphTensor object for one instance of randomly generated training data. One instance consists of some randomly-generated coordinates of 4 nodes + 1 signal source (held in node_coordinates), and 10 pairwise arrival time differences (held in time_differences). I then define the node adjacency such that the graph is fully connected, and attempt to create a GraphTensor object from the node coordinates, adjacency, and pairwise arrival time differences.
When I check that the resulting GraphTensor object is compatible with the graph specification using print(graph_spec.is_compatible_with(make_graph_tensor())), however, I get False. Unfortunately, it isn’t clear to me why this is. I initially expected it might have something to do with dimensions, so I tried changing shape: { dim: { size: 3 } } so that the feature shape would be inferred, but this did not help.
Why is the GraphObject incompatible with the graph specification resulting from the above schema?