0-1 knapsack is of fundamental importance across many fields. In this paper, we present a game-theoretic method to solve 0-1 knapsack problems (KPs) where the number of items (products) is large and the values of items are not predetermined but decided by an external value assignment function (e.g., a neural network in our case) during the optimization process. While existing papers are interested in predicting solutions with neural networks for classical KPs whose objective functions are mostly linear functions, we are interested in solving KPs whose objective functions are neural networks. In other words, we choose a subset of items that maximize the sum of the values predicted by neural networks. Its key challenge is how to optimize the neural network-based non-linear KP objective with a budget constraint. Our solution is inspired by game-theoretic approaches in deep learning, e.g., generative adversarial networks. After formally defining our two-player game, we develop an adaptive gradient ascent method to solve it. In our experiments, our method successfully solves two neural network-based non-linear KPs and conventional linear KPs with 1 million items.

We present a prediction-driven optimization framework to maximize the market influence in the US domestic air passenger transportation market by adjusting flight frequencies. At the lower level, our neural networks consider a wide variety of features, such as classical air carrier performance features and transportation network features, to predict the market influence. On top of the prediction models, we define a budget-constrained flight frequency optimization problem to maximize the market influence over 2,262 routes. This problem falls into the category of the non-linear optimization problem, which cannot be solved exactly by conventional methods. To this end, we present a novel adaptive gradient ascent (AGA) method. Our prediction models show two to eleven times better accuracy in terms of the median root-mean-square error (RMSE) over baselines. In addition, our AGA optimization method runs 690 times faster with a better optimization result (in one of our largest scale experiments) than a greedy algorithm.

The US domestic air passenger transportation is one of the largest markets worldwide.Optimally allocating flights to the US domestic airways (i.e., air routes) is essential in maximizing the revenue of airlines and many research works have been proposed to improve their market shares/profits.Most proposed methods, however, suffer from a lack of scalability; even state-of-the-art methods demonstrate their performance with only tens of routes.To address this shortcoming, we propose a novel unified framework to integrate the market share prediction model and the frequency optimization module, which significantly improves the scalability of the entire framework.By design, our proposed prediction model is concave w.r.t.flight frequency and its gradients are Lipschitz continuous.Exploiting these two properties allows us to use an alternating direction method of multipliers (ADMM)-based optimization technique, which quickly solves a large-scale frequency optimization problem with guaranteed global convergence.Our proposed method is able to solve a problem whose search space size is O(n 700 ) (vs.O(n 30 ) in existing works).

Graph synthesis is a long-standing research problem.Many deep neural networks that learn about latent characteristics of graphs and generate fake graphs have been proposed.However, in many cases their scalability is too high to be used to synthesize large graphs.Recently, one work proposed an interesting scalable idea to learn and generate random walks that can be merged into a graph.Due to its difficulty, however, the random walk-based graph synthesis failed to show state-of-the-art performance in many cases.We present an improved random walk-based method by using negative random walks.In our experiments with 6 datasets and 8 baseline methods, our method shows the best performance in almost all cases.We achieve both high scalability and generation quality.

As one of the fundamental tasks in data analytics, Influence Maximization methods have been widely used in many real-world applications. For instance, in social network analysis, after building a directed graph, where edges are weighted with influence probabilities, influence maximization methods can be used to find a set of users who can maximize the spread of information under certain cascade models. Despite their successes, however, one critical weakness of existing influence maximization methods lies in the fact that edges are weighted with historical probabilities. As such, influence maximization methods perform sub-optimal if there occur non-trivial changes in future. In response to this challenge, in this work, we propose a novel prediction-driven influence maximization method that accurately predicts future influence probabilities using graph convolutional networks and find seed users based on the predicted probabilities. The experiments with five real-world datasets show that our prediction accuracy is accurate (e.g., mean absolute percentage error less than 0.1) in many cases, and our prediction-driven influence maximization is very close to the optimal.

When a new vulnerability is discovered, a Common Vulnerability and Exposure (CVE) number is publicly assigned to it. The vulnerability is then analyzed by the US National Institute of Standards and Technology (NIST) whose Common Vulnerability Scoring System (CVSS) evaluates a severity score that ranges from 0 to 10 for the vulnerability. On average, NIST takes 132.7 days for this - but early knowledge of the CVSS score is critical for enterprise security managers to take defensive actions (e.g. patch prioritization). We present VASE (Vulnerability Analysis and Scoring Engine) that uses Twitter discussions about CVEs to predict CVSS scores before the official assessments from NIST. In order to leverage the intrinsic correlations between different vulnerabilities, VASE adopts a graph convolutional network (GCN) model in which nodes correspond to CVEs. In addition, we propose a novel attention-based input embedding method to extract useful latent features for each CVE node. We show on real-world data that VASE obtains a mean absolute error (MAE) of 1.255 for predicting the CVSS score using only three days of Twitter discussion data after the date a vulnerability is first mentioned on Twitter. VASE can provide predictions for the CVSS scores for 37.85% of the CVEs at least one week earlier than the official assessments by NIST.

In many cases, an organization wishes to release some data, but is restricted in the amount of data to be released due to legal, privacy and other concerns. For instance, the US Census Bureau releases only 1% of its table of records every year, along with statistics about the entire table. However, the machine learning (ML) models trained on the released sub-table are usually sub-optimal. In this paper, our goal is to find a way to augment the sub-table by generating a synthetic table from the released sub-table, under the constraints that the generated synthetic table (i) has similar statistics as the entire table, and (ii) preserves the functional dependencies of the released sub-table. We propose a novel generative adversarial network framework called ITS-GAN, where both the generator and the discriminator are specifically designed to satisfy these two constraints. By evaluating the augmentation performance of ITS-GAN on two representative datasets, the US Census Bureau data and US Bureau of Transportation Statistics (BTS) data, we show that ITS-GAN yields high quality classification results, and significantly outperforms various state-of-the-art data augmentation approaches.

Knowing if/when a cyber-vulnerability will be exploited and how severe the vulnerability is can help enterprise security officers (ESOs) come up with appropriate patching schedules. Today, this ability is severely compromised: our study of data from Mitre and NIST shows that on average there is a 132 day gap between the announcement of a vulnerability by Mitre and the time NIST provides an analysis with severity score estimates and 8 important severity attributes. Many attacks happen during this very 132-day window. We present Vulnerability Exploit Scoring \& Timing (VEST), a system for (early) prediction and visualization of if/when a vulnerability will be exploited, and its estimated severity attributes and score.