Recent scientific work [1] leveraging GNNs for routing in computer networks has used a line digraph representation of the computer network topology as input for their GNN policies. The line digraph is formed by taking the original graph's edges as new nodes, and drawing an edge between those new nodes that, as edges in the original graph, form a directed path of length two: E' = {(u, v), (w, x) | (u, v) in E; (w, x) in E; v = w}.
However, AFAIK there is no existing PyG implementation that provides this conversion (and no issue/MR requesting this). The LineGraph transformation is defined differently and produces a different output. Bernárdez et al., in their code, have implemented the conversion manually on a networkX.DiGraph object, and while this works fine I suspect a PyG transformation implementation working on a Data object can provide the functionality more efficiently.
Alternatives
As mentioned above, the existing LineGraph transformation does something slightly different and is therefore not an alternative. Also, while it's possible to manually construct the graph as Bernárdez et al. did in their code, I assume we can do it quicker with tensor ops in PyG.
I have implemented a sketch for the transformation in this gist, however somebody with more PyG experience might help me in optimizing away the for-loop (if possible).
Additional context
Besides, is it possible to apply the transformations of PyG to Batch objects?
[1]: Bernárdez et al. "Magnneto: A graph neural network-based multi-agent system for traffic engineering." IEEE Transactions on Cognitive Communications and Networking 9.2 (2023)
🚀 The feature, motivation and pitch
Recent scientific work [1] leveraging GNNs for routing in computer networks has used a line digraph representation of the computer network topology as input for their GNN policies. The line digraph is formed by taking the original graph's edges as new nodes, and drawing an edge between those new nodes that, as edges in the original graph, form a directed path of length two:
E' = {(u, v), (w, x) | (u, v) in E; (w, x) in E; v = w}.However, AFAIK there is no existing PyG implementation that provides this conversion (and no issue/MR requesting this). The
LineGraphtransformation is defined differently and produces a different output. Bernárdez et al., in their code, have implemented the conversion manually on anetworkX.DiGraphobject, and while this works fine I suspect a PyG transformation implementation working on aDataobject can provide the functionality more efficiently.Alternatives
As mentioned above, the existing
LineGraphtransformation does something slightly different and is therefore not an alternative. Also, while it's possible to manually construct the graph as Bernárdez et al. did in their code, I assume we can do it quicker with tensor ops in PyG.I have implemented a sketch for the transformation in this gist, however somebody with more PyG experience might help me in optimizing away the for-loop (if possible).
Additional context
Besides, is it possible to apply the transformations of PyG to
Batchobjects?[1]: Bernárdez et al. "Magnneto: A graph neural network-based multi-agent system for traffic engineering." IEEE Transactions on Cognitive Communications and Networking 9.2 (2023)