Creating new graph that will contain all the absent edges of the given graph

I want to create a graph G’ from the given graph G where G’ will contain all the edges that are not present in graph G and G is an undirected graph. Is there any way I can do it easily in dgl?


I assume your graph is not so big thus it’s affordable to do dense operation. Note that if you have multiple edges between pair of nodes, you may need to handle these situation seperately

g = dgl.graph([(1,2), (3,4)] # for example graph g
u = g.adj()
new_adj = 1-u.to_dense()
new_graph = dgl.graph(torch.where(new_adj)) # This is what you need

Thanks for the solution. But as you said it does not scale up well for graph with ~50k edges. Is there any solution for large graphs?

Did you mean 50k nodes? If your number of nodes is this big, then working on a complement graph is unlikely to be scalable since it will be very dense anyway. You probably need to resort to other methodologies (e.g. negative sampling).

Thanks for reply, but taking negative sample as G’ doesn’t ensure all the non-present connections are in the G’. Is there any way around to this?


We have a new pull request handling this problem, [Feature] Negative sampling by BarclayII · Pull Request #3599 · dmlc/dgl · GitHub, to provide true negative edges. We expect it can be merged soon

1 Like

Thanks for reply, but will dgl.dataloading.negative_sampler.GlobalUniform give back all possible true negative edges? or will it give back a fraction of all the true negative edges randomly?

It’s random. Because all negative edges will be expansive for large graph

1 Like