Faster Fundamental Graph Algorithms via Learned Predictions
Authors: Justin Chen, Sandeep Silwal, Ali Vakilian, Fred Zhang
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate the applicability of our learning-based reductions framework with a real world case study on foreign exchange markets. The reduction we focus on is the general shortest paths to bipartite matching reduction outlined in Section 7. We focus our evaluation on this task since prior work in (Dinitz et al., 2021) has already demonstrated the empirical advantage of learning-based methods for bipartite matching.Our graph dataset is constructed as follows. |
| Researcher Affiliation | Academia | 1MIT 2TTIC 3UC Berkeley. Correspondence to: Fred Zhang <z0@berkeley.edu>. |
| Pseudocode | Yes | Algorithm 1 Faster Primal-Dual Scheme for MWPM; Algorithm 2 Rounding Predictions for Reduced Edge Length Duals; Algorithm 3 General Reduction Framework for Learning Based Algorithms; Algorithm 4 Primal-Dual Scheme for MWBM from (Dinitz et al., 2021); Algorithm 5 Learning-based Shortest Paths |
| Open Source Code | No | We use the code from (Dinitz et al., 2021) 2 for the maximum weight bipartite matching algorithm. Available at https://github.com/tlavastida/Learned Duals. This link refers to code from a prior work that the authors used, not the novel code developed in *this* paper. |
| Open Datasets | Yes | Dataset scraped from https://fxtop.com/en/historical-exchange-rates.php |
| Dataset Splits | No | The paper describes 'training dataset' and 'testing dataset' but does not specify a separate validation dataset or explicit split percentages for any of the datasets. |
| Hardware Specification | No | The paper does not mention any specific hardware components (e.g., GPU models, CPU models, memory size, cloud instance types) used for running the experiments. |
| Software Dependencies | No | The paper states 'We use the code from (Dinitz et al., 2021)' but does not specify any software dependencies with version numbers (e.g., Python version, specific libraries, frameworks). |
| Experiment Setup | Yes | We construct the graph described above for each month of the year 2019 where we use the average monthly exchange rates as edge weights before performing the transformation. Our testing dataset are similarly constructed graphs for each month of 2020 and 2021. For each graph, we construct the reduction from shortest paths to matching outlined in Section 5.2. By Lemma 5.2, the output of the maximum weight perfect matching on the bipartite graph obtained via the reduction gives us feasible reduced edge length duals which we can be subsequently use to solve shortest paths in nearly linear time. The resulting bipartite graphs have 500 vertices each and 5 104 edges. We use the code from (Dinitz et al., 2021) 2 for the maximum weight bipartite matching algorithm. As in (Dinitz et al., 2021), we measure the runtime in terms of the number of steps used by the Hungarian algorithm to solve the matching instances derived from our training and test graph datasets when we initialize the algorithm with predicted duals versus when we start the algorithm from scratch. We instantiate predictions in two distinct ways, similar to the methodology of (Dinitz et al., 2021): (a) first, we consider the batch version where we compute the optimal dual variables in the training set, take their median, and use these as the predicted dual variables for each of the graphs in the test set. (b) The second method is the online version where we use the optimal dual variables from the graph for the prior month in the test set as initialization for the current month. |