CarloLucibello
commented
3 years ago It would be nice to get this in quickly to help with other PRs
Closed CarloLucibello closed 3 years ago
CarloLucibello
commented
3 years ago It would be nice to get this in quickly to help with other PRs
yuehhua
commented
3 years ago Thank you for your work for benchmarking graph convolutional layers. Not only the scale of graph is important, but also the edge number does matter. A graph usually contains less edges. For example, there are N nodes in a graph and the total possible edges are E = N(N+1)/2. Maybe a graph has 0.5 E edges, even less to 0.1 E edges. For a benchmark script, I think it is good to have kwargs for edge_ratio to set the proportion of randomly connected edges.
GraphConv is more than 10x slower than GCNConv, at least at smaller sizes.
Actually, I have no much idea about this.
Since GCNConv calls
adjacency_matrix, that's a problem (for the other graph types) that should be easily fixed by providing better specialized methods.
Either adjacency matrix or other format, it should be transformed into normalized Laplacian matrix. The specialized method can be support of normalized Laplacian matrix for each format.
CarloLucibello
commented
3 years ago For example, there are N nodes in a graph and the total possible edges are E = N(N+1)/2. Maybe a graph has 0.5 E edges, even less to 0.1 E edges. For a benchmark script, I think it is good to have kwargs for edge_ratio to set the proportion of randomly connected edges.
Most natural networks are better modeled by an average degree which is constant or scales very weakly with N, having O(N) degree would produce unrealistically dense graphs. I added the degree as a keyword argument to run_benchmarks so that one can experiment with different values.
CarloLucibello
commented
3 years ago Benchmarking on erdos-renyi exposed another bug: GraphConv fails when the graph contains isolated nodes
CarloLucibello
commented
3 years ago Can we merge this?
yuehhua
commented
3 years ago I would merge this first, but I think it is better to benchmark the conversion function laplacian_matrix and pure propagate function for each graph structures. Pure means there message function and update function returns directly. For example, message(x_i, x_j) = x_j and update(x, m) = m. These micro-benchmarks may represent the effort have to take to convert from original structure and the indexing performance for a structure.
Adding a script doing some basic benchmarking, in order to track performance changes as the library evolves.
I selected for testing the GCNLayer and the GraphConv layers as representatives of the algebraic and the message passing approaches respectively. Edit: Also added GATConv. The benchmarks are on random graphs of small and up to moderate size (10 to 10k nodes). Different graph storage types are tested (adjacency list, dense adjacency matrix, sparse adjacency matrix, LightGraphs.SimpleGraph). These are the results on ~my laptop~ a server, which I'm also committing as a reference
A few notes:
Quite surprisingly, the most performant graph type seems to be the LightGraphs's one, with several orders of magnitude better performances with GCNConv. Since GCNConv calls
adjacency_matrix, that's a problem (for the other graph types) that should be easily fixed by providing better specialized methods. This is the comparison betweenlightgraphand other storage types