About SubModLib

SubModLib is an easy-to-use, efficient and scalable Python library for submodular optimization with a C++ optimization engine. Submodlib finds its application in summarization, data subset selection, hyper parameter tuning, efficient training etc. Through a rich API, it offers a great deal of flexibility in the way it can be used.

Please check out our latest arxiv preprint: https://arxiv.org/abs/2202.10680

Salient Features

• Rich suite of functions for a wide variety of subset selection tasks:
  • regular set (submodular) functions
  • submodular mutual information functions
  • conditional gain functions
  • conditional mutual information functions
• Supports different types of optimizers
  • naive greedy
  • lazy (accelerated) greedy
  • stochastic (random) greedy
  • lazier than lazy greedy
• Combines the best of Python's ease of use and C++'s efficiency
• Rich API which gives a variety of options to the user. See this notebook for an example of different usage patterns
• De-coupled function and optimizer paradigm makes it suitable for a wide-variety of tasks
• Comprehensive documentation (available here)

Google Colab Notebooks Demonstrating the power of SubModLib and sample usage

• Modelling capabilities of regular submodular functions
• Modelling capabilities of submodular mutual information (SMI) functions
• Modelling capabilities of conditional gain (CG) functions
• Modelling capabilities of conditional mutual information (CMI) functions
• This notebook contains a quantitative analysis of performance of different functions and role of the parameterization in aspects like query-coverage, query-relevance, privacy-irrelevance and diversity for different SMI, CG and CMI functions as observed on synthetically generated dataset.
• This notebook contains similar analysis on ImageNet dataset.
• For a more detailed discussion on all possible usage patterns, please see Different Options of Usage

Setup

Alternative 1

• $ pip install -i https://test.pypi.org/simple/ --extra-index-url https://pypi.org/simple/ submodlib

Alternative 2 (if local docs need to be built and test cases need to be run)

• $ git clone https://github.com/decile-team/submodlib.git
• $ cd submodlib
• $ pip install .
• Latest documentation is available at readthedocs. However, if local documentation is required to be built, follow these steps::
  • $ pip install -U sphinx
  • $ pip install sphinxcontrib-bibtex
  • $ pip install sphinx-rtd-theme
  • $ cd docs
  • $ make clean html
• To run the tests, follow these steps:
  • $ pip install pytest
  • $ pytest # this runs ALL tests
  • $ pytest -m <marker> --verbose --disable-warnings -rA # this runs test specified by the

Usage

It is very easy to get started with submodlib. Using a submodular function in submodlib essentially boils down to just two steps:

1. instantiate the corresponding function object
2. invoke the desired method on the created object

The most frequently used methods are:

1. f.evaluate() - takes a subset and returns the score of the subset as computed by the function f
2. f.marginalGain() - takes a subset and an element and returns the marginal gain of adding the element to the subset, as computed by f
3. f.maximize() - takes a budget and an optimizer to return an optimal set as a result of maximizing f

For example,

from submodlib import FacilityLocationFunction
objFL = FacilityLocationFunction(n=43, data=groundData, mode="dense", metric="euclidean")
greedyList = objFL.maximize(budget=10,optimizer='NaiveGreedy')

For a more detailed discussion on all possible usage patterns, please see Different Options of Usage

Functions

• Regular set (submodular) functions (for vanilla subset selection requiring representation, diversity, importance, relevance, coverage)
  • Facility Location
  • Disparity Sum
  • Disparity Min
  • Log Determinant
  • Set Cover
  • Probabilistic Set Cover
  • Graph Cut
  • Feature Based
• Submodular mutual information functions (for query-focused subset selelction)
  • Facility Location Mutual Information
  • Facility Location Variant Mutual Information
  • Graph Cut Mutual Information
  • Log Determinant Mutual Information
  • Concave Over Modular
  • Set Cover Mutual Information
  • Probabilistc Set Cover Mutual Information
• Conditional gain functions (for query-irrelevant/privacy-preserving subset selection)
  • Facility Location Conditional Gain
  • Graph Cut Conditional Gain
  • Log Determinant Conditional Gain
  • Set Cover Conditional Gain
  • Probabilistic Set Cover Conditional Gain
• Conditional mutual information functions (for joint query-focused and privacy-preserving subset selection)
  • Facility Location Conditional Mutual Information
  • Log Determinant Conditional Mutual Information
  • Set Cover Conditional Mutual Information
  • Probabilistic Set Cover Conditional Mutual Information

Modelling Capabilities of Different Functions

We demonstrate the representational power and modeling capabilities of different functions qualitatively in the following Google Colab notebooks:

• Modelling capabilities of regular submodular functions
• Modelling capabilities of submodular mutual information (SMI) functions
• Modelling capabilities of conditional gain (CG) functions
• Modelling capabilities of conditional mutual information (CMI) functions

This notebook contains a quantitative analysis of performance of different functions and role of the parameterization in aspects like query-coverage, query-relevance, privacy-irrelevance and diversity for different SMI, CG and CMI functions as observed on synthetically generated dataset. This notebook contains similar analysis on ImageNette dataset.

Optimizers

• NaiveGreedy
• LazyGreedy
• StochasticGreedy
• LazierThanLazyGreedy
• This notebook demonstrates the use and comparison of different optimizers.

Sample Application (Image collection summarization)

• This notebook contains demonstration of using submodlib for an image collection summarization application.

Timing Analysis

To gauge the performance of submodlib, selection by Facility Location was performed on a randomly generated dataset of 1024-dimensional points. Specifically the following code was run for the number of data points ranging from 50 to 10000.

K_dense = helper.create_kernel(dataArray, mode="dense", metric='euclidean', method="other")
obj = FacilityLocationFunction(n=num_samples, mode="dense", sijs=K_dense, separate_rep=False,pybind_mode="array")
obj.maximize(budget=budget,optimizer=optimizer, stopIfZeroGain=False, stopIfNegativeGain=False, verbose=False, show_progress=False)

The above code was timed using Python's timeit module averaged across three executions each. We report the following numbers:

Citing

If your research makes use of SUBMODLIB, please consider citing:

SUBMODLIB (Submodlib: A Submodular Optimization Library (Kaushal et al., 2022))

@article{kaushal2022submodlib,
  title={Submodlib: A submodular optimization library},
  author={Kaushal, Vishal and Ramakrishnan, Ganesh and Iyer, Rishabh},
  journal={arXiv preprint arXiv:2202.10680},
  year={2022}
}

Contributors

• Vishal Kaushal, Ganesh Ramakrishnan and Rishabh Iyer. Currently maintained by CARAML Lab

Contact

Should you face any issues or have any feedback or suggestions, please feel free to contact vishal[dot]kaushal[at]gmail.com

Acknowledgements

This work is supported by the Ekal Fellowship (www.ekal.org). This work is also supported by the National Science Foundation(NSF) under Grant Number 2106937, a startup grant from UT Dallas, as well as Google and Adobe awards.