knn_graph function outputs

[AmEskandari]

Hi everyone, I am a little bit confused about nn.knn_graph function. This function generates an undirected graph by b matching methods in which each node's degree is k, but when I convert the edge index to Adjacency matrix sum of the rows is not k and nodes have different degrees (flow argument is the default, 'source_to_target'). could you please explain the output of this function to me (more than its doc)?

[rusty1s]

Can you share some reproducible example for this? This is definitely undesired, and all nodes should have exactly k neighbors. Note that this function will not compute an undirected graph though, as the neighbors for two nearby nodes may be different.

[AmEskandari]

Yes I made a mistake about undirected it's obviously directed. As a toy example, consider two set of four points:

x1 = (0,0),(0,1),(1,0),(1,1)
x2 = (0,0),(0,1),(1,0),(2,2)

The first set is a kind of square vertices location. By selecting k = 2 and giving x1 to knn_graph we will have 8 edges which graphs look like a square and everything is normal:

>>> x = torch.FloatTensor([[0,0],[0,1],[1,0],[1,1]])   
>>> edge_index = knn_graph(x , k = 2, flow = 'source_to_target')
>>> edge_index
tensor([[1, 2, 0, 3, 0, 3, 1, 2],
        [0, 0, 1, 1, 2, 2, 3, 3]])
>>> A = to_dense_adj(edge_index)
tensor([[[0., 1., 1., 0.],
         [1., 0., 0., 1.],
         [1., 0., 0., 1.],
         [0., 1., 1., 0.]]])

By a quick view, it's clear nodes have the same degree which is equal to k = 2. But let's do the same for x2.

>>> x = torch.FloatTensor([[0,0],[0,1],[1,0],[2,2]])   
>>> edge_index = knn_graph(x , k = 2, flow = 'source_to_target')
>>> edge_index
tensor([[1, 2, 0, 2, 0, 1, 1, 2],
        [0, 0, 1, 1, 2, 2, 3, 3]])
>>> A = to_dense_adj(edge_index)
tensor([[[0., 1., 1., 0.],
         [1., 0., 1., 1.],
         [1., 1., 0., 1.],
         [0., 0., 0., 0.]]])

The number of edges is still 8, but something bad happened, node index 3 (last row of A matric) is not connected to any nodes, and nodes 1 and 2 are connected to all nodes except themself.

I used these packages: (latest PyG version used)

from torch_geometric.utils import to_dense_adj
from torch_geometric.nn import knn_graph
import torch

[rusty1s]

Ah, I see. Note that you need to look at the destination node indices to determine node degree (A.sum(dim=1)). This aligns with the general message passing flow in GNNs (each node receives exactly k messages).

[AmEskandari]

So there is no problem whit this function? if I use this function and run a GNN-based approach, Can I report in my paper I am using a knn constructed graph in which each node receives k messages?

[rusty1s]

Yes, that‘s what this function is doing.

[AmEskandari]

Aha, Thank you Matthias! You helped a lot I was worried about my results.