I have over hundreds of large graphs. Each with num_nodes > 1,000,000, num_edges > 1,000,000.
I want to transform them to line graphs without backtracking.
Is it possible to speed up the trnasformation to line graphs with GPU? If yes, how?
Thanks!
I have over hundreds of large graphs. Each with num_nodes > 1,000,000, num_edges > 1,000,000.
I want to transform them to line graphs without backtracking.
Is it possible to speed up the trnasformation to line graphs with GPU? If yes, how?
Thanks!
Yes, the trick is the to use the incidence matrix E of a graph. Incidence matrix - Wikipedia . Below is a brief how-to:
Incidence Matrix Overview:
Calculate E^T E:
Construct the Adjacency Matrix B of the Line Graph:
Is this correct?
(No idea for the case when backtracking == False)
def line_graph_adjacency(g, backtracking=True):
if backtracking:
# Compute the target and source matrices
R = g.incidence_matrix('in')
L = g.incidence_matrix('out')
B = R.T @ L
# Set diagonal to 0 using sparse indexing
B._values()[B._indices()[0] == B._indices()[1]] = 0
else:
raise NotImplementedError()
return B
Actually, I checked with dgl.line_graph function. Wondering how/whether I can directly use dgl.line_graph where computations are done on GPU.