pyg-team / pytorch_geometric

Graph Neural Network Library for PyTorch
https://pyg.org
MIT License
21.38k stars 3.67k forks source link

Enquiries about test_geodesic_distance #593

Closed sw-gong closed 5 years ago

sw-gong commented 5 years ago

As for the file test_geodesic.py, I do not understand why the correct case is:

    expected = [
        [0, 1, 1, sqrt(2)],
        [1, 0, sqrt(2), 1],
        [1, sqrt(2), 0, 1],
        [sqrt(2), 1, 1, 0],
    ]

Instead of

expected = [
        [0, 2, 2, 2*sqrt(2)],
        [2, 0, 4, 2],
        [2, 4, 0, 2],
        [2*sqrt(2), 2, 2, 0],
  ]

I assume the geodesic distance of two vertices should be the sum of the Euclidean distances of each edge in a shortest path (therefore, geodesic distance between vertex 0 and vertex 1 is 2 not 1). Please correct me if my understanding is not correct.

Furthermore, as for the geodesic errors used in dataset FAUST, should I set norm=True to reproduce the same geodesic errors within each vertex pair?

Thanks!

rusty1s commented 5 years ago

The geodesic distance is not necessarily the sum of the Euclidean distances of each edge in the shortest path, but rather denotes the shortest distance to reach vertex A from vertex B by any path on the manifold. In addition, norm is used to compute the normalized geodesic distance, normalized by sqrt(A) where A denotes the area of the mesh. This normalized distance is used in the Princeton benchmark (Section 8.2) and should therefore be used when evaluating geodesic errors.

sw-gong commented 5 years ago

Thanks @rusty1s . Can you elaborate it a bit why it could be any path on the manifold? If so, the geodesic distance for two vertices is then indeterminate. Additionaly, assume given any path on the manifold, how to compute the geodesic distance given this path? As for the example shown in test_geodesic.py, vertex 0 and 1 are [0, 0, 0] and [2, 0, 0] respectively. Why the geodesic distance between them is 1 instead of 2? Many thanks!

rusty1s commented 5 years ago

Well, we search for the shortest path on the manifold which connects vertex A and vertex B, but this path has not necessarily go through any other vertex of the triangulation.

In your example, the geodesic distance is 1 because the absolute geodesic distance 2 is normalized according to the mesh surface sqrt(A) = sqrt(4) = 2 with A = 2 * 2 = 4. Concerning your questions on the geodesic distance computation, this link may help.

sw-gong commented 5 years ago

I see. One more question, if I set norm = False, there is no direct edge between vertex 1 and 2. The geodesic distance between them should be 4 instead of 2.8284 from your code since the geodesci distance requires all the paths belonging to the triangulated mesh?

pos = torch.Tensor([[0, 0, 0], [2, 0, 0], [0, 2, 0], [2, 2, 0]])
face = torch.tensor([[0, 1, 3], [0, 2, 3]]).t()
mat = geodesic_distance(pos, face, norm=False)
print(mat)
tensor([[0.0000, 2.0000, 2.0000, 2.8284],
        [2.0000, 0.0000, 2.8284, 2.0000],
        [2.0000, 2.8284, 0.0000, 2.0000],
        [2.8284, 2.0000, 2.0000, 0.0000]])

Shall we change gdist.compute_gdist to gdist.local_gdist_matrix on the case of evaluating the whole mesh as sources, which is more efficient.

rusty1s commented 5 years ago

Although there is no edge between vertex 1 and 2, their shortest path on the manifold is the diagonal line through both triangles, so sqrt(4) is correct.

Regarding local_gdist_matrix, I think I tested the runtimes and they perform equally fast.

sw-gong commented 5 years ago

Although there is no edge between vertex 1 and 2, their shortest path on the manifold is the diagonal line through both triangles, so sqrt(4) is correct.

Regarding local_gdist_matrix, I think I tested the runtimes and they perform equally fast.

Is there any typo in your words? Do you mean 2*sqrt(2) is correct? If sqrt(4) is correct, the result then is wrong.

As for the runtime, image

rusty1s commented 5 years ago

Yes sorry, I mean 2 * sqrt(2). Your obtained runtimes are interesting. I think we should fix this. Do you want to submit a PR or want me to fix this?

sw-gong commented 5 years ago

Thanks for answering my questions all the time. Sure. I can submit a PR later.

sw-gong commented 5 years ago

PR submitted https://github.com/rusty1s/pytorch_geometric/pull/605#issue-305081907

Powerd0g commented 2 years ago

Is pyg available a simple function that takes as input two arguments: the pos and the edge_index , will return the sum of the Euclidean distances of each edge between two nodes in a shortest path. or similar function can get shortest path of a graph.

rusty1s commented 2 years ago

If you have given a shortest path in the form of path = [(v_1, v2), (v2, v3), ...], then you can simply do

src_pos, dst_pos = pos[path.t().view(-1)].view(2, path.size(0), -1)
dist = (src_pos - dst_pos).pow(2).sum(dim=-1).sqrt().sum()