Papers

Networked discrete dynamical systems are commonly used as formal models to study the spread of contagions over networks. Fixed points of such dynamical systems represent configurations to which systems may converge. In the case of undesirable contagions (such as epidemics, fake news and rumors) spreading over social networks (where nodes represent a population), convergence to configurations with a small number of affected nodes is highly desirable. Motivated by such considerations, we formulate a novel optimization problem for discrete dynamical systems, where the state of each node is from {0, 1} and state 1 indicates a node that has been infected by the contagion. Specifically, the goal of the problem is to find a fixed point of such a system where the number of nodes in state 1 is a minimum. We also require such a fixed point to be nontrivial (to avoid the trivial case where all nodes are in state 0). Our results are for dynamical systems where the behavior of each node is specified by a threshold function. These functions capture simple as well as complex contagions and have also been studied in game theory. We show that, unless P = NP, there is no polynomial time algorithm for approximating the solution to within the factor n^{1 - epsilon} for any constant \epsilon > 0, even when the underlying network is bipartite. We then explore several approaches to cope with the computational intractability of the problem. First, we identify several special cases (e.g., dynamical systems over directed acyclic graphs, progressive contagions where nodes cannot transition from state 1 to state 0) for which the problem can be solved efficiently. We also identify a version that is fixed parameter tractable with respect to a structural parameter associated with the problem. Next, we develop an integer linear programming (ILP) formulation for the problem so that existing solvers such as Gurobi can be used to solve the problem in practice for networks of reasonable size. For larger networks, we propose a general heuristic framework for the problem. We present extensive experimental results using real-world networks to demonstrate the effectiveness of the proposed heuristic framework.

poster session 4 @ red 3, poster session 8 @ red 3, oral session 4 @ red 3, poster session 4, poster session 8, oral session 4

The cost-efficiency of model inference is critical to real-world machine learning (ML) applications, especially for delay-sensitive tasks and resource-limited devices. A typical dilemma is: in order to provide complex intelligent services (e.g. smart city), we need inference results of multiple ML models, but the cost budget (e.g. GPU memory) is not enough to run all of them. In this work, we dug into underlying relationships among black-box ML models and proposed a novel learning task: model linking. Model linking aims to bridges the knowledge of different black-box models by learning mappings between their output spaces. Based on model links, we developed a scheduling algorithm, named MLink. Through collaborative multi-model inference enabled by model links, MLink can significantly improve the accuracy of obtained inference results under the cost budget. We conducted comprehensive evaluations on a multi-modal dataset with seven different ML models and two real-world video analytics systems with 6 ML models and 3,264 hours of video. The experimental results show that our proposed model links can be effectively built among various black-box models. Under the budget of GPU memory, MLink can save 66.7% inference computations while preserving 94% inference accuracy, which outperforms multi-task learning, deep reinforcement learning-based scheduler and frame filtering baselines.

poster session 4 @ red 3, poster session 8 @ red 3, oral session 4 @ red 3, poster session 4, poster session 8, oral session 4

This paper presents a novel collaborative generative modeling (CGM) framework that incentivizes collaboration among self-interested parties to contribute data to a pool for training a generative model (e.g., GAN), from which synthetic data are drawn and distributed to the parties as rewards commensurate to their contributions. Distributing synthetic data as rewards (instead of trained models or money) offers task- and model-agnostic benefits for downstream learning tasks and is less likely to violate data privacy regulation. To realize the framework, we firstly propose a data valuation function using maximum mean discrepancy (MMD) that values data based on its quantity and quality in terms of its closeness to the true data distribution and provide theoretical results guiding the kernel choice in our MMD-based data valuation function. Then, we formulate the reward scheme as a linear optimization problem that when solved, guarantees certain incentives such as fairness in the CGM framework. We devise a weighted sampling algorithm for generating synthetic data to be distributed to each party as reward such that the value of its data and the synthetic data combined matches its assigned reward value by the reward scheme. We empirically show using simulated and real-world datasets that the parties' synthetic data rewards are commensurate to their contributions.

poster session 4 @ red 3, poster session 8 @ red 3, oral session 4 @ red 3, poster session 4, poster session 8, oral session 4