Finding hard instances, which need a long time to solve, of graph problems such as the graph coloring problem and the maximum clique problem, is important for (1) building a good benchmark for evaluating the performance of algorithms, and (2) analyzing the algorithms to accelerate them. The existing methods for generating hard instances rely on parameters or rules that are found by domain experts; however, they are specific to the problem. Hence, it is difficult to generate hard instances for general cases. To address this issue, in this paper, we formulate finding hard instances of graph problems as two equivalent optimization problems. Then, we propose a method to automatically find hard instances by solving the optimization problems. The advantage of the proposed algorithm over the existing rule based approach is that it does not require any task specific knowledge. To the best of our knowledge, this is the first non-trivial method in the literature to automatically find hard instances. Through experiments on various problems, we demonstrate that our proposed method can generate instances that are a few to several orders of magnitude harder than the random based approach in many settings. In particular, our method outperforms rule-based algorithms in the 3-coloring problem.
Deep Generative Graph Models: Recently, several generative graph models utilizing deep learning techniques were proposed. The variational graph auto-encoder @cite_5 is one of the first models of this kind. It is a variant of the Variational Auto Encoder (VAE), which outputs a probabilistic adjacent matrix. This model was used for the link prediction of citation networks. Then, VAE @cite_17 @cite_8 @cite_18 @cite_3 , Generative Adversarial Networks (GAN) @cite_9 @cite_21 @cite_12 , and sequential generation @cite_6 @cite_23 @cite_1 @cite_7 based generating models were proposed. In particular, they succeeded in generating various de-novo chemical materials and modeling real-world networks. ORGAN @cite_19 utilizes SeqGAN @cite_10 and reinforcement learning to generate molecular graphs with the desired properties. It uses SMILES @cite_15 to represent a molecular graph because SeqGAN generates a sequence of symbols rather than a graph itself. MolGAN @cite_14 is another graph generative model utilizing GAN and reinforcement learning. It models the probabilistic adjacent matrix and attributes of graphs directly instead of using SMILES. The generative graph model of this work belongs to this stream. To the best of our knowledge, there is no deep learning based hard instance generating algorithm.
@cite_18 @cite_14 @cite_7 @cite_8 @cite_9 @cite_21 @cite_1 @cite_3 @cite_6 @cite_19 @cite_23 @cite_5 @cite_15 @cite_10 @cite_12 @cite_17
2523469089 2964268978 2806351858 2594717275
As a new way of training generative models, Generative Adversarial Nets (GAN) that uses a discriminative model to guide the training of the generative model has enjoyed considerable success in generating real-valued data. However, it has limitations when the goal is for generating sequences of discrete tokens. A major reason lies in that the discrete outputs from the generative model make it difficult to pass the gradient update from the discriminative model to the generative model. Also, the discriminative model can only assess a complete sequence, while for a partially generated sequence, it is non-trivial to balance its current score and the future one once the entire sequence has been generated. In this paper, we propose a sequence generation framework, called SeqGAN, to solve the problems. Modeling the data generator as a stochastic policy in reinforcement learning (RL), SeqGAN bypasses the generator differentiation problem by directly performing gradient policy update. The RL reward signal comes from the GAN discriminator judged on a complete sequence, and is passed back to the intermediate state-action steps using Monte Carlo search. Extensive experiments on synthetic data and real-world tasks demonstrate significant improvements over strong baselines. As a new way of training generative models, Generative Adversarial Net (GAN) that uses a discriminative model to guide the training of the generative model has enjoyed considerable success in generating real-valued data. However, it has limitations when the goal is for generating sequences of discrete tokens. A major reason lies in that the discrete outputs from the generative model make it difficult to pass the gradient update from the discriminative model to the generative model. Also, the discriminative model can only assess a complete sequence, while for a partially generated sequence, it is nontrivial to balance its current score and the future one once the entire sequence has been generated. In this paper, we propose a sequence generation framework, called SeqGAN, to solve the problems. Modeling the data generator as a stochastic policy in reinforcement learning (RL), SeqGAN bypasses the generator differentiation problem by directly performing gradient policy update. The RL reward signal comes from the GAN discriminator judged on a complete sequence, and is passed back to the intermediate state-action steps using Monte Carlo search. Extensive experiments on synthetic data and real-world tasks demonstrate significant improvements over strong baselines. eep generative models for graph-structured data offer a new angle on the problem of chemical synthesis: by optimizing differentiable models that directly generate molecular graphs, it is pos-sible to side-step expensive search procedures in the discrete and vast space of chemical structures. We introduce MolGAN, an implicit, likelihood-free generative model for small molecular graphs that circumvents the need for expensive graph matching procedures or node ordering heuris-tics of previous likelihood-based methods. Our method adapts generative adversarial networks (GANs) to operate directly on graph-structured data. We combine our approach with a reinforce-ment learning objective to encourage the genera-tion of molecules with specific desired chemical properties. In experiments on the QM9 chemi-cal database, we demonstrate that our model is capable of generating close to 100 valid com-pounds. MolGAN compares favorably both to recent proposals that use string-based (SMILES) representations of molecules and to a likelihood-based method that directly generates graphs, al-beit being susceptible to mode collapse. We explore methods of producing adversarial examples on deep generative models such as the variational autoencoder (VAE) and the VAE-GAN. Deep learning architectures are known to be vulnerable to adversarial examples, but previous work has focused on the application of adversarial examples to classification tasks. Deep generative models have recently become popular due to their ability to model input data distributions and generate realistic examples from those distributions. We present three classes of attacks on the VAE and VAE-GAN architectures and demonstrate them against networks trained on MNIST, SVHN and CelebA. Our first attack leverages classification-based adversaries by attaching a classifier to the trained encoder of the target generative model, which can then be used to indirectly manipulate the latent representation. Our second attack directly uses the VAE loss function to generate a target reconstruction image from the adversarial example. Our third attack moves beyond relying on classification or the standard loss for the gradient and directly optimizes against differences in source and target latent representations. We also motivate why an attacker might be interested in deploying such techniques against a target generative network.