Speed Up Line Graph Construction

[chpoonag]

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!

[minjie]

Yes, the trick is the to use the incidence matrix E of a graph. Incidence matrix - Wikipedia . Below is a brief how-to:

Computing the Adjacency Matrix of the Line Graph Using Linear Algebra

1. Incidence Matrix Overview:

   • The incidence matrix E of a graph G with n vertices and m edges is an n x m matrix.
   • E[i][j] = 1 if vertex i is one of the endpoints of edge j, and 0 otherwise. For directed graphs, use -1 for the source and 1 for the target.

2. Calculate E^T E:

   • Multiply the transpose of E by E to get an m x m matrix, where m is the number of edges in G.
   • This operation produces E^T E where:
     • Diagonal entries of E^T E count the number of vertices each edge is incident to.
     • Off-diagonal entries count the common vertices between pairs of edges.

3. Construct the Adjacency Matrix B of the Line Graph:

   • Initialize B as an m x m zero matrix.
   • Set all diagonal entries of E^T E to 0 because an edge cannot be adjacent to itself in L(G).
   • For off-diagonal entries, set B[i][j] = 1 if (E^T E)[i][j] is non-zero, indicating that edges i and j in G share a common vertex.

[chpoonag]

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.