clipper
clipper copied to clipboard
mit-acl
algo updates
-
gradF update: After the most recent optimizations, the gradF update was missing using the gradFnew calculated in the line search. From what I can tell, this fix created no appreciable difference, but values are now aligned with the MATLAB implementation.
-
d steps: changed the update strategy for d steps from using the min (which meant that no elements of the u vector would need to be projected back onto the pos orthant) to using the mean step (which means half of the elements will have to be projected onto the pos orthant). This seems to have produced a significant (2-4x) speedup on the bunny benchmark, with no change on accuracy -- see report below.
-
recale_u0: new parameter added to turn on / off the initial power method step to rescale u0. This does not seem to make an appreciable difference on bunny benchmark.
this version
Benchmarking over 20 trials
Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:44s]
+-------+---------+---------------+-------------------+---------------+------------+
| ρ [%] | # assoc | affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+---------------+-------------------+---------------+------------+
| 0 | 64 | 0.19 ± 0.0 | 0.06 ± 0.0 | 100 | 90 |
| 0 | 256 | 1.05 ± 0.0 | 0.63 ± 0.0 | 100 | 89 |
| 0 | 512 | 3.95 ± 0.1 | 2.41 ± 0.0 | 100 | 89 |
| 0 | 1024 | 15.64 ± 1.0 | 9.86 ± 0.1 | 100 | 89 |
| 0 | 2048 | 94.63 ± 1.4 | 32.53 ± 0.4 | 100 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 20 | 64 | 0.20 ± 0.0 | 0.06 ± 0.0 | 100 | 90 |
| 20 | 256 | 1.88 ± 3.9 | 0.63 ± 0.1 | 99 | 89 |
| 20 | 512 | 3.69 ± 0.1 | 2.35 ± 0.4 | 100 | 89 |
| 20 | 1024 | 14.84 ± 0.6 | 13.51 ± 6.3 | 99 | 89 |
| 20 | 2048 | 85.49 ± 1.5 | 59.20 ± 46.9 | 100 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 40 | 64 | 0.19 ± 0.0 | 0.04 ± 0.0 | 100 | 90 |
| 40 | 256 | 1.00 ± 0.1 | 0.42 ± 0.1 | 100 | 89 |
| 40 | 512 | 3.46 ± 0.1 | 1.58 ± 0.4 | 100 | 89 |
| 40 | 1024 | 13.77 ± 0.4 | 9.27 ± 3.6 | 99 | 89 |
| 40 | 2048 | 71.14 ± 1.1 | 55.42 ± 27.5 | 99 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 80 | 64 | 0.29 ± 0.5 | 0.05 ± 0.0 | 100 | 91 |
| 80 | 256 | 0.89 ± 0.0 | 0.44 ± 0.1 | 100 | 89 |
| 80 | 512 | 3.22 ± 0.1 | 1.62 ± 0.3 | 99 | 90 |
| 80 | 1024 | 12.54 ± 0.1 | 5.71 ± 1.3 | 99 | 90 |
| 80 | 2048 | 66.70 ± 0.5 | 24.55 ± 15.5 | 99 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 90 | 64 | 0.18 ± 0.0 | 0.05 ± 0.0 | 100 | 90 |
| 90 | 256 | 0.95 ± 0.3 | 0.38 ± 0.1 | 99 | 90 |
| 90 | 512 | 3.17 ± 0.1 | 1.44 ± 0.5 | 99 | 90 |
| 90 | 1024 | 12.37 ± 0.1 | 6.12 ± 1.7 | 99 | 90 |
| 90 | 2048 | 66.18 ± 0.3 | 27.09 ± 10.1 | 99 | 90 |
+-------+---------+---------------+-------------------+---------------+------------+
previous version
Benchmarking over 20 trials
Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:54s]
+-------+---------+---------------+-------------------+---------------+------------+
| ρ [%] | # assoc | affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+---------------+-------------------+---------------+------------+
| 0 | 64 | 0.20 ± 0.0 | 0.06 ± 0.0 | 100 | 90 |
| 0 | 256 | 1.12 ± 0.3 | 0.63 ± 0.3 | 100 | 89 |
| 0 | 512 | 4.37 ± 2.0 | 2.12 ± 0.9 | 100 | 89 |
| 0 | 1024 | 16.27 ± 2.8 | 10.21 ± 4.6 | 100 | 89 |
| 0 | 2048 | 94.61 ± 2.4 | 43.25 ± 19.7 | 100 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 20 | 64 | 0.19 ± 0.0 | 0.15 ± 0.0 | 100 | 89 |
| 20 | 256 | 1.02 ± 0.1 | 2.00 ± 0.5 | 100 | 89 |
| 20 | 512 | 3.81 ± 0.7 | 8.84 ± 1.9 | 100 | 89 |
| 20 | 1024 | 14.63 ± 0.6 | 44.83 ± 17.2 | 100 | 89 |
| 20 | 2048 | 84.86 ± 0.9 | 223.11 ± 63.0 | 99 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 40 | 64 | 0.28 ± 0.4 | 0.15 ± 0.0 | 100 | 89 |
| 40 | 256 | 0.99 ± 0.2 | 1.81 ± 0.3 | 99 | 89 |
| 40 | 512 | 3.51 ± 0.1 | 7.50 ± 1.8 | 100 | 89 |
| 40 | 1024 | 13.88 ± 1.0 | 32.58 ± 7.6 | 99 | 89 |
| 40 | 2048 | 71.31 ± 1.0 | 192.51 ± 44.8 | 99 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 80 | 64 | 0.18 ± 0.0 | 0.11 ± 0.0 | 100 | 91 |
| 80 | 256 | 0.93 ± 0.1 | 1.11 ± 0.2 | 99 | 89 |
| 80 | 512 | 3.20 ± 0.1 | 4.01 ± 0.7 | 99 | 90 |
| 80 | 1024 | 12.61 ± 0.2 | 18.62 ± 4.3 | 99 | 89 |
| 80 | 2048 | 67.52 ± 1.5 | 87.97 ± 15.6 | 99 | 89 |
+-------+---------+---------------+-------------------+---------------+------------+
| 90 | 64 | 0.18 ± 0.0 | 0.13 ± 0.0 | 99 | 91 |
| 90 | 256 | 0.90 ± 0.0 | 1.08 ± 0.2 | 99 | 91 |
| 90 | 512 | 3.24 ± 0.1 | 3.76 ± 0.5 | 99 | 90 |
| 90 | 1024 | 12.44 ± 0.1 | 16.57 ± 3.9 | 100 | 90 |
| 90 | 2048 | 66.41 ± 0.4 | 77.50 ± 15.0 | 99 | 90 |
+-------+---------+---------------+-------------------+---------------+------------+
