initzhang
commented
3 weeks ago Hi @snigdhas1612 , thanks for your interest in our work! I apologise for the late reply but I was way too busy on another project for the past months.
The fast_reorder function actually reorders the graph by renumbering the src node idx and dst node idx of each edge. Below is a simple example:
original (bidirectional) graph with edge list: (0,2) (1,5) (2,0) (2,3) (2,4) (2,5) (3,2) (4,2) (5,1) (5,2).
Say we have a cache priority of 2 > 5 > 1 > 3 > 4 > 0, then we can reorder the original graph with node mapping {2: 0, 5: 1, 1: 2, 3: 3, 4: 4, 0: 5} for each edge and obtain the reordered graph with edge list: (5,0) (2,1) (0,5) (0,3) (0,4) (0,1) (3,0) (4,0) (1,2) (1,0) as follow:
As you can see, each edge from the original graph has its corresponding new edge in the new graph with the only difference of node mapping. Below is the python code snippet:
from common import fast_reorder
import torch
import dgl
src = torch.tensor([0, 1, 2, 2, 2, 2, 3, 4, 5, 5]).long()
dst = torch.tensor([2, 5, 0, 3, 4, 5, 2, 2, 1, 2]).long()
original_graph = dgl.graph(('coo', (src, dst)))
node_perm = torch.tensor([2,5,1,3,4,0]).long()
reordered_graph = fast_reorder(original_graph, node_perm)
print(reordered_graph.edges())
# (tensor([5, 2, 0, 0, 0, 0, 3, 4, 1, 1]), tensor([0, 1, 5, 3, 4, 1, 0, 0, 2, 0]))
I have been exploring the fast_reorder function in the codebase, and I am seeking a better understanding of the detailed steps behind this function. While the code is clear in its intuition, is there any way to check for the functional correctness of the reordering logic?
https://github.com/initzhang/DUCATI_SIGMOD/blob/9cc017f8453a26db72cf5c1c2fa1f4a3c9cee969/common.py#L34
Is there any relevant documentation or links that explain the custom logic in the broader context of reordering the graph? Any help would be appreciated. Thanks.