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.
Graphs are a fundamental abstraction for modeling relational data. However, graphs are discrete and combinatorial in nature, and learning representations suitable for machine learning tasks poses statistical and computational challenges. In this work, we propose Graphite an algorithmic framework for unsupervised learning of representations over nodes in a graph using deep latent variable generative models. Our model is based on variational autoencoders (VAE), and differs from existing VAE frameworks for data modalities such as images, speech, and text in the use of graph neural networks for parameterizing both the generative model (i.e., decoder) and inference model (i.e., encoder). The use of graph neural networks directly incorporates inductive biases due to the spatial, local structure of graphs directly in the generative model. Moreover, we draw novel connections between graph neural networks and approximate inference via kernel embeddings of distributions. We demonstrate empirically that Graphite outperforms state-of-the-art approaches for the tasks of density estimation, link prediction, and node classification on synthetic and benchmark datasets. 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 present a simple generation procedure which turns out to be an effective source of very hard cases for graph 3-colorability. The graphs distributed according to this generation procedure are much denser in very hard cases than previously reported for the same problem size. The coloring cost for these instances is also orders of magnitude bigger. This ability is issued from the fact that the procedure favors-inside the class of graphs with given connectivity and free of 4-cliques-the generation of graphs with relatively few paths of length three (that we call 3-paths). There is a critical value of the ratio between the number of 3-paths and the number of edges, independent of the number of nodes, which separates the graphs having the same connectivity in two regions: one contains almost all graphs free of 4-cliques while the other contains almost no such graphs. The generated very hard cases are near this phase transition, and have a regular structure, witnessed by the low variance in node degrees, as opposite to the random graphs. This regularity in the graph structure seems to confuse the coloring algorithm by inducing an uniform search space, with no clue for the search.  In unsupervised data generation tasks, besides the generation of a sample based on previous observations, one would often like to give hints to the model in order to bias the generation towards desirable metrics. We propose a method that combines Generative Adversarial Networks (GANs) and reinforcement learning (RL) in order to accomplish exactly that. While RL biases the data generation process towards arbitrary metrics, the GAN component of the reward function ensures that the model still remembers information learned from data. We build upon previous results that incorporated GANs and RL in order to generate sequence data and test this model in several settings for the generation of molecules encoded as text sequences (SMILES) and in the context of music generation, showing for each case that we can effectively bias the generation process towards desired metrics.    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.  Deep learning on graphs has become a popular research topic with many applications. However, past work has concentrated on learning graph embedding tasks only, which is in contrast with advances in generative models for images and text. Is it possible to transfer this progress to the domain of graphs? We propose to sidestep hurdles associated with linearization of such discrete structures by having a decoder output a probabilistic fully-connected graph of a predefined maximum size directly at once. Our method is formulated as a variational autoencoder. We evaluate on the challenging task of conditional molecule generation.