Embedding in larger graph

[mxv001]

Hello experts,
Does anyone know of means of embedding a graph in a larger graph? I know it is easy to embed node features in a higher dimensional space, by some kind of matrix multiplication. And I know it is easy to lower the number of nodes in a graph through e.g. hierarchical pooling methods.

But I am looking for methods to systematically and/or iteratively to increase the size of the graph by adding nodes that encode data from neighbors and edges.

The only method I have seen so far is to use artificial nodes as in this article:
https://towardsdatascience.com/how-to-boost-your-gnn-356f70086991

Does anyone have other methods to suggest? Are there any such methods available in pyg?

Thank you!

[rusty1s]

Can you clarify for me what you want to do? Do you want to generate new nodes/edges, or do you want to iteratively increase the nodes you want to embed? A bit confused, sorry.

[mxv001]

I would like to transform my input graph to have new nodes/edges.

For example I see two methods that are plausible for my needs, half-hop and virtual node:
https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.transforms.HalfHop.html#torch_geometric.transforms.HalfHop

and virtual node:
https://pytorch-geometric.readthedocs.io/en/latest/generated/torch_geometric.transforms.VirtualNode.html#torch_geometric.transforms.VirtualNode

But the half-hop method does not work with edge weight or edge attributes, and virtual node adds a node connected to every other node, with edge features of the virtual node are zero-filled.

Is there a way of adding nodes/edges to my graph in a way that is smarter? Perhaps adding a new node between two connected nodes with averaged node/edge features?

I am using this as a preprocessing step before applying learnable layers.

[rusty1s]

Got it. Note that you can simply add new nodes/edges to an existing graph by concatenating them to your node feature matrix and edge_index representation, e.g.:

edge_index = torch.cat([edge_index, torch.tensor([0, 1, 2], [2, 3, 4]])], dim=1)

However, how you define the new nodes/edges is up to you, and depends on what you want to do. If you want to add a node for every edge in your graph, this would mean you need to define a new edge_index representation, and node features would be given as

x_edge = x[edge_index[0]] + x[edge_index[1]] / 2
x = torch.cat([x, x_edge], dim=0)