Adding random nodes for separate graphs in a batch.

[nsidn98]

I wanted to add random nodes to the edge_index for a given batch. Now there might be different number of nodes in each graph in the given batch, I wanted to make sure that each node gets connected to other nodes in the same graph and not to any nodes from other graphs in the batch.

For example, the given batch has 5 graphs with the following edge_index:

tensor([[  0,   0,   0,   1,   1,   1,   2,   2,   3,   3,   4,   4,   4,   4,
           5,   5,   5,   6,   7,   8,   8,   8,   9,   9,  10,  10,  10,  11,
          11,  12,  12,  13,  13,  14,  14,  15,  15,  16,  17,  17,  17,  18,
          18,  19,  19,  19,  21,  23, ... 118, 119, 120, 119, 120, 120, 123, 125],
        [  1,  21,  22,   2,  21,  22,   3,  22,  23,  26,   5,   6,  26,  27,
           6,   7,  27,   7,  24,   9,  24,  25,  24,  25,  11,  12,  25,  12,
          13,  13,  14,  14,  15,  15,  16,  16,  20,  20,  18,  20,  28,  19,
          28,  28,  29,  31,  22,  26,  27,  27,  29,  31,  31,  33,  32,  33,
          34,  33,  33,  34,  34,   0,   0,   0,   1,   1,   1,   2,   2,   3,
           3,   4,   4,   4,   4,   5,   5,  ... 117, 117, 117, 118, 118, 119, 122, 124]])

These five graphs contain [35, 19, 24, 24, 24] number of nodes respectively.

I was planning to connect random nodes in a graph, using something like this:

num_nodes = [g.number_of_nodes() for g in graphList] #[35, 19, 24, 24, 24]
nodes_cumsum = np.cumsum(num_nodes) # [ 35,  54,  78, 102, 126]
min_idx = 0
for i in range(len(nodes_cumsum)):
    max_idx = nodes_cumsum[i]
    rand_edge_idx = torch.randint(min_idx, max_idx, (2, num_connect))
    batch.edge_index = torch.cat([batch.edge_index, rand_edge_index], dim=1)
    min_idx = nodes_cumsum[i]

With this method it might be possible that rand_edge_idx contains edge connections which already exist in the graph. So will that existence of double edge connections hamper the graph convolutions I might use on these modified graphs?

Also, is there a better(efficient) way of connecting random nodes in the graph? The psueodcode I have given above is a more generalised version of what I want to do. In particular, I would like to do something like:

for each graph in batch:
    for each node_i in graph:
        connect node_i to nom_connect number of random nodes

I did take a look at #2302 and #754 but wasn't sure if the psueodcode given over there by @rusty1s matches with my requirements.

Thanks!

[rusty1s]

You could use torch_geometric.utils.batched_negative_sampling for this and concatenate the resulting negative edges to your edge_index. As an alternative, you can also apply such modifications via the usage of transforms, which has the advantage that you do not need to care about correct mini-batch treatment.

[nsidn98]

I tried adding a custom transform class as an input to the TUDataset where the transform class adds random edges to the input graphs. But it seems that these transforms are performed only once when the dataset is initialised (not really sure if this is the case after giving it to the Dataloader class). What would I have to change so as to add random edges every time the graph is called?

For example: In epoch 0, graph_0 has 5 random edges added. Now in epoch 1, for graph_0, I would want to add random edges which were not sampled before in epoch 0.

[rusty1s]

That is already the case when using transforms. Are you mistakenly setting a seed somewhere in your transform?

[nsidn98]

I am setting the seed in the __init__ of the custom class. Are you saying that if I do not set the seeds(or set the seeds in some other way) the dataloader will make random transformations every time a particular graph is called? If yes, could you suggest the recommended way of setting the seeds?

Edit: adding code snippet of the class definition

class AddRandomEdges(object):
    def __init__(self, K:int):
        self.K = K
        random.seed(0)

    def __call__(self, data):
        num_nodes = data.num_nodes
        node_set = set(np.arange(num_nodes))
        K = min(self.K, num_nodes)  # NOTE some graphs may have less than K nodes
        random_nodes = torch.LongTensor(random.sample(node_set, K)).unsqueeze(0)
        edge_index = data.edge_index
        src_node_idx = torch.arange(num_nodes).long().repeat(K).unsqueeze(0)        # shape [1, num_nodes*K]
        dest_node_idx = random_nodes.repeat((num_nodes,1)).T.flatten().unsqueeze(0) # shape [1, num_nodes*K]
        rand_edge_idx = torch.cat([src_node_idx, dest_node_idx], 0) # shape [2, num_nodes*K]
        new_edge_index = torch.cat([edge_index, rand_edge_idx], 1)  # shape [2, num_nodes*K + num_edges]     
        c_edge_index, _ = coalesce(new_edge_index, None, num_nodes, num_nodes)  # remove double counted edges
        data.edge_index = c_edge_index
        return data

[rusty1s]

I think your script is fine. And it produces different edges each time we access a data object for me:

import torch
import numpy as np
import random
from torch_sparse import coalesce
from torch_geometric.datasets import TUDataset


class AddRandomEdges(object):
    def __init__(self, K: int):
        self.K = K
        random.seed(0)

    def __call__(self, data):
        num_nodes = data.num_nodes
        node_set = set(np.arange(num_nodes))
        K = min(self.K,
                num_nodes)  # NOTE some graphs may have less than K nodes
        random_nodes = torch.LongTensor(random.sample(node_set,
                                                      K)).unsqueeze(0)
        edge_index = data.edge_index
        src_node_idx = torch.arange(num_nodes).long().repeat(K).unsqueeze(
            0)  # shape [1, num_nodes*K]
        dest_node_idx = random_nodes.repeat(
            (num_nodes, 1)).T.flatten().unsqueeze(0)  # shape [1, num_nodes*K]
        rand_edge_idx = torch.cat([src_node_idx, dest_node_idx],
                                  0)  # shape [2, num_nodes*K]
        new_edge_index = torch.cat([edge_index, rand_edge_idx],
                                   1)  # shape [2, num_nodes*K + num_edges]
        c_edge_index, _ = coalesce(new_edge_index, None, num_nodes,
                                   num_nodes)  # remove double counted edges
        data.edge_index = c_edge_index
        return data


dataset = TUDataset('/tmp/TUDataset', 'MUTAG', transform=AddRandomEdges(K=10))
print(dataset[0])
print(dataset[0])

[nsidn98]

Thanks a lot! This works as intended.