Speed Up Line Graph Construction

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?


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.
1 Like

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
        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.