Quadratic Decomposable Submodular Function Minimization: Theory and Practice
Authors: Pan Li, Niao He, Olgica Milenkovic
JMLR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | For hypergraph-adapted semi-supervised learning, we provide numerical experiments demonstrating the efficiency of our QDSFM solvers and their significant improvements on prediction accuracy when compared to state-of-the-art methods. |
| Researcher Affiliation | Academia | Pan Li EMAIL Department of Computer Science Purdue University West Lafayette, IN 47907, USA Niao He EMAIL Department of Industrial and Enterprise Systems Engineering University of Illinois at Urbana-Champaign Champaign, IL 61820, USA Olgica Milenkovic EMAIL Department of Electrical and Computer Engineering University of Illinois at Urbana-Champaign Champaign, IL 61820, USA |
| Pseudocode | Yes | Algorithm 1: The RCD method for Solving (6) Algorithm 2: The AP Method for Solving (11) Algorithm 3: The Conic MNP Method for Solving (12) Algorithm 4: The Conic FW Algorithm for Solving (12) Algorithm 5: An Exact Projection Algorithm for a Directed Hyperedge |
| Open Source Code | No | The paper does not explicitly provide a link to a code repository or an affirmative statement about releasing source code for the described methodology. |
| Open Datasets | Yes | We also evaluated the proposed algorithms on three UCI datasets: Mushroom, Covertype45, Covertype67, used as standard test datasets for SSL on hypergraphs (Zhou et al., 2007; Hein et al., 2013; Zhang et al., 2017). |
| Dataset Splits | Yes | We uniformly at random picked l = 1, 2, 3, 4 vertices from each cluster to represent labeled datapoints. With the vector x obtained by solving (21), we classified the variables based on the Cheeger cut rule (Hein et al., 2013): suppose that xi1 Wi N i N , and let Sj = {i1, i2, ..., ij}. We partitioned [N] into two sets (Sj , Sj ), where j = arg min j [N] Φ(Sj) |
| Hardware Specification | Yes | All algorithms were executed on a 3.2GHz Intel Core i5 machine. For each algorithm, the average and variance of the primal gap are obtained via 100 independent tests. ... The CPU times of all methods are recorded on a 3.2GHz Intel Core i5. |
| Software Dependencies | No | All the aforementioned methods, except Inv Lap, are implemented in C++ in a nonparallel fashion. Inv Lap is executed via matrix inversion operations in Matlab, and may be parallelized. (No specific versions for C++ compiler, Matlab, or any libraries are given.) |
| Experiment Setup | Yes | For the particular problem at hand, the QDSFM problem can be formulated as follows: min x RN β x a 2 + X r [R] max i,j Sr( xi Wii xj p Wjj )2, (21) where ai { 1, 0, 1} indicates if the corresponding variable i has a negative, missing, or positive label, respectively, β is a parameter that balances out the influence of observations and the regularization term, {Wii}i [N] defines a positive measure over the variables and may be chosen to be the degree matrix D, with Dii = |{r [R] : i Sr}|. ... For this purpose, we construct a synthetic QDSFM problem (4) by fixing N = 100, R = 100, and Wii = 1, for all i [N]. We generate each incidence set Sr by choosing uniformly at random a subset of [N] of cardinality 10, and then set the entries of a to be i.i.d. standard Gaussian. ... For all algorithms, we terminate the inner loop by setting δ = 10 12 or a maximum number of iterations |Sr|3 = 1000. ... in the experiment, we used Wii = Dii, i, and tuned β to be nearly optimal for different objectives with respect to the classification error rates: for QDSFM as the objective, using QRCD-SPE, QAP-SPE, PDHG, and SGD as the methods of choice, we set β = 0.02; for DSFM as the objective, including the DRCD method, we set β = 1; for Inv Lap, we set β = 0.001. ... for PDHG, we set σ = τ = 1 1+maxi Dii and for SGD, we set ηk = 1 kβ maxi Wii . |