The goal is to get the visualization of the graph.
- Input: the graph G = (V, E). We can get the real distance between each node (here is the shortest distance in the graph). Then we want our visualization graph to be as close as possible to the real distance guidance.
- Output: each node is assigned a coordinate (X, Y).
-
python graphdraw.py
It would run the original paper's algorithm. It is just simple math without Pytorch implementation. It is not involved with gradient computing. -
python torch_sgd.py
Implement the algorithm in Pytorch. It is fixed to be BATCH_SIZE = 1. The computation should be the same with the original algorithm. The stress function is regarded as the loss function, and.backward()is called to get the gradient for each term. Each time we update a pair of nodes. -
python batch_sgd.py
Pytorch implementation that supports any BATCH_SIZE. Note that the original algorithm is designed only for BATCH_SIZE = 1, and has some specific constraints. To make it reasonable to apply to BATCH_SIZE > 1, I made some modifications, mainly on the learning_rate. -
python batch_sgd_vector_lr.py
Pytorch implementation that supports any BATCH_SIZE. The learning rate is set to be a vector, that aims to be consistent with the original BATCH_SIZE = 1 setting. (But there might be some bugs. )
wc = w * c
wc = torch.min(wc, torch.ones_like(wc))
lr = torch.min(wc / (4 * w))
x.data.sub_(lr * x.grad.data)We would evaluate on two aspects:
- Time consumption & Iteration times
- Quality: graph visualization qualitatively; stress quantitatively.
- Time: 50.07s
- Result:
output/qh882.svg; Stress = 18736
- Time: 18min 46s
- Result:
output/batch_1_iter_15.svg; Stress = 18741
- Time: 1 min 20s
- Result:
output/batch_16_iter_15.svg; Stress = 45287
- Time: 5min 10s
- Result:
output/batch_16_iter_60.svg; Stress = 18759
- Time: 12s
- Stress = 237022
- Time: 44s
- Stress = 187087
- Time: 3min 7s
- Stress = 126226
- Time: 3min 13s
- Stress: 30224
- Time: 6min 10s
- Stress: 18841