/pattern-aware-reordering

Primary LanguageJavaScript

A Summarization-Based Pattern-Aware Matrix Reordering Approach

Our Implementations

We implemented the following algorithms in ./MatrixReordering/

  • Leaf Ordering (with the Scipy Python package)
  • Rank-Two (according to the algorithm description by [1])
  • MDS (with the sklearn Python package)
  • Evolutionary Reordering (translated into Python from the original implementation in R [2])
  • MinLA (implemented in Python according to authors' algorithm description [3])
  • Biclustering (implemented in Python according to the description in [1]);
  • Collection-aware Leaf Ordering using $\delta_I$ (implemented in Python according to the original JavaScript code [4]);

We also implemented four metrics in ./MatrixReordering/Metrics.py:

  • LA (linear arrangement): according to descriptions in [1];
  • PR (profile): according to descriptions in [5];
  • BW (bandwidth): according to descriptions in [1];
  • MI (Moran's I): translated from the original JavaScript code in [4];

Our two techniques (GRD and RMD) are implemented in ./MatrixReordering/PatternOrdering.py (greedy_ordering and randomized_ordering).

Experiments

Before running the code, please make sure that your computer has installed matlab (required by Experiment 1 to run VoG), pycharm, and python3. Note that all python code should be run in pycharm now, because relative path is not configured. Please run pip install -r requirements.txt to install all required python packages.

Experiment 1: How to run the pattern precision comparison?

The results of our previous experiments have been stored in the PatternPrecisionComparison folder. To see the results directly, you only need to perform the last step. To reproduce our experiments, you can follow all steps.

  1. Run cd ./PatternPrecisionComparison

  2. Run .PatternPrecisionComparison/synthetic_generator.py to generate synthetic datasets. They will be stored in ./data/synthetic-x.x-x.x-x.x.json, ./data/synthetic-x.x-x.x-x.x.edgelist, and ./data/synthetic-x.x-x.x-x.x.out.

  3. Run ./VoG/run_structureDiscovery.m to run VoG. The detected patterns are summarized in ./VoG/DATA/synthetic-x.x-x.x-x.x_ALL.model.

  4. Run ./pattern_precision.py to run our model. It will store the results of our model and VoG into a unified file: ./precision.csv

  5. Run ./pattern_significance.py to run the Conover's test. It will generate the p-value.

  6. Run ./draw-precision.html (require a localhost, e.g., python3 -m http.server xxxx) to see the line charts.

Experiment 2: How to run metrics comparisons?

The results of our previous experiments have been stored in the MetricComparison folder. To see the results directly, you only need to perform step 3 and 4. To reproduce our experiments, you can follow all steps. Note that the entire experiment lasts several hours, you can run it after sleeping 😅 or choose small datasets to run it (comment the 12th line in ./MetricComparison/definitions.py and cancel the comment of the 14th line in it). Note that Table 1 (showing metrics for different patterns) in our paper also comes from this folder by running ./pattern_response.py and ./draw-pattern-response.html

  1. Run cd ./MetricComparison

  2. Run ./matrix.py to reorder all twenty matrices (original data are stored in /data/xxx.edgelist) by nine different algorithms. Results are stored in ./matrix and ./results.json

  3. Run ./draw-metrics.html (require a localhost, e.g., python3 -m http.server xxxx) to see the charts.

  4. To explore our results, you can open ./visualization.html with a localhost.

Experiment 3: User Study

The user study is performed by 15 participants. The synthetic dataset was generated by ./UserStudy/synthetic_generator.py (graphs are stored in ./UserStudy/graph/ and reordered matrices are stored in ./UserStudy/matrix/).

One participant needed to perform tasks with ./UserStudy/index.html (require a localhost, e.g., python3 -m http.server xxxx). After finishing the tasks, a JSON file that stores his/her results will be downloaded. All participant results are stored in ./UserStudy/results/.

Run ./UserStudy/data_analysis.py could analyze the collected data. After analysis, run ./UserStudy/visualization.html could visualize the results.

References

[1] M. Behrisch, B. Bach, N. H. Riche, T. Schreck, and J. Fekete, “Matrix reordering methods for table and network visualization,” Computer Graphics Forum, vol. 35, no. 3, pp. 693–716, 2016.

[2] https://web.archive.org/web/20080205025042/http://www.ewas.de/tables/bertin.r

[3] E. Rodriguez-Tello, J. Hao, and J. Torres-Jimenez, “An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem,” Computers and Operations Research, vol. 35, no. 10, pp. 3331–3346, 2008.

[4] nvbeusekom/reorder.js: JavaScript library to reorder matrices (github.com)

[5] N. van Beusekom, W. Meulemans, and B. Speckmann, “Simultaneous matrix orderings for graph collections,” IEEE TVCG, vol. 28, no. 1, pp. 1–10, 2022.