Sparsification of Decomposable Submodular Functions
Authors: Akbar Rafiey, Yuichi Yoshida10336-10344
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirical results. Finally, we empirically examine our algorithm and demonstrate that it constructs a concise sparsifier on which we can efficiently perform algorithms. In this section, we empirically demonstrate that our algorithm (Algorithm 2) generates a sparse representation of a decomposable submodular function F : 2E R+ with which we can efficiently obtain a high-quality solution for maximizing F. We consider the following two settings. Uber pickup. ... Discogs (Kunegis 2013). ... Figure 1 (a) and (b) show the objective value of the solution obtained by the greedy method on the sparsifier relative to that on the original input function with its 25th and 75th percentiles. |
| Researcher Affiliation | Academia | Akbar Rafiey,1 Yuichi Yoshida 2 1 Simon Fraser University 2 National Institute of Informatics arafiey@sfu.ca, yyoshida@nii.ac.jp |
| Pseudocode | Yes | Algorithm 1 Require: Submodular functions fi in dataset D where each fi : {0, 1}E R, ϵ, δ (0, 1) 1: w 0 2: κ 3 log(2n+1/δ)/ϵ2 3: for fi in D do 4: pi max A E fi(A)/F(A) 5: κi min{1, κ pi} 6: wi 1/κi with probability κi do nothing with probability 1 κi 7: return w RD. Algorithm 2 Require: Submodular functions fi : {0, 1}E R in dataset D, matroid M = (E, I), and ϵ, δ (0, 1) 1: w 0 2: κ 3 log(2nr+1/δ)/ϵ2, where r is the rank of M. 3: for fi in D do 4: pi max A I fi(A)/F(A) 5: κi min{1, κ pi} 6: wi 1/κi with probability κi do nothing with probability 1 κi 7: return w RD. |
| Open Source Code | No | The paper does not provide an explicit statement about releasing its own source code or a link to a code repository for the methodology described. |
| Open Datasets | Yes | Uber pickup. We used a dataset of Uber pickups in New York city in May 2014 consisting of a set R of 564,517 records1. ... 1Available at https://www.kaggle.com/fivethirtyeight/uberpickups-in-new-york-city. Discogs (Kunegis 2013). This dataset provides information about audio records as a bipartite graph G = (L, R; E), where each edge (u, v) L R indicates that a label v was involved in the production of a release of a style u. We have |L| = 383 and |R| = 243, 764, and |E| = 5, 255, 950. |
| Dataset Splits | No | The paper describes using the Uber pickup and Discogs datasets but does not provide specific details on how these datasets were split into training, validation, or test sets, nor does it refer to predefined splits with citations. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU/GPU models, memory, or cloud instance types) used for running the experiments. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers (e.g., programming languages, libraries, or frameworks) used for the implementation or experiments. |
| Experiment Setup | No | The paper mentions 'when k = 8' in the experimental results section but does not provide comprehensive experimental setup details such as hyperparameters (e.g., learning rates, batch sizes, optimizers), model initialization, or specific training schedules. |