Discriminative Embeddings of Latent Variable Models for Structured Data

By Hanjun Dai, Bo Dai, Le Song. 2016

757 citations recorded by the source corpus.

Kernel classifiers and regressors designed for structured data, such as sequences, trees and graphs, have significantly advanced a number of interdisciplinary areas such as computational biology and drug design. Typically, kernels are designed beforehand for a data type which either exploit statistics of the structures or make use of probabilistic generative models, and then a discriminative classifier is learned based on the kernels via convex optimization. However, such an elegant two-stage approach also limited kernel methods from scaling up to millions of data points, and exploiting discriminative information to learn feature representations. We propose, structure2vec, an effective and scalable approach for structured data representation based on the idea of embedding latent variable models into feature spaces, and learning such feature spaces using discriminative information. Interestingly, structure2vec extracts features by performing a sequence of function mappings in a way similar to graphical model inference procedures, such as mean field and belief propagation. In applications involving millions of data points, we showed that structure2vec runs 2 times faster, produces models which are 10, 000 times smaller, while at the same time achieving the state-of-the-art predictive performance.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Generative Models

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Generative Models

Citations in the corpus

Inductive Representation Learning on Large Graphs (2017, neutral): “There are also a number of recent neural network approaches to supervised learning over graph structures [7, 10, 21, 31].”
Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018, background): “Following on this work, a number of authors proposed improvements, extensions, and approximations of these spectral convolutions [6, 10, 11, 13, 18, 21, 24, 29, 31], leading to new state-of-the-art results on benchmarks such as node classification, link prediction, as well as recommender system task”
Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “Previously, [9] required a ground truth label for every input graph G in order to train the structure2vec architecture.”
Relational inductive biases, deep learning, and graph networks (2018, methodology): “Various models, including CommNet (Sukhbaatar et al., 2016), structure2vec (Dai et al., 2016) (in the version of (Dai et al., 2017)), and Gated Graph Sequence Neural Networks (Li et al., 2016) have used a φ e which does not directly compute pairwise interactions, but instead ignore the receiver…”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “Differentiable Pooling on STRUCTURE2VEC.”
An End-to-End Deep Learning Architecture for Graph Classification (2018, methodology): “(Dai, Dai, and Song 2016) represented each graph using a latent variable model and then explicitly embedded them into feature spaces in a way similar to graphical model inference.”
Representation Learning on Graphs: Methods and Applications (2017, methodology): “The most prominent application domain is for classifying the properties of graphs corresponding to different molecules [16, 21, 43, 33].”
Learning Multimodal Graph-to-Graph Translation for Molecular Optimization (2018, background): “, 2018) and recurrent architectures (Li et al., 2015; Dai et al., 2016; Lei et al., 2017).”
Junction Tree Variational Autoencoder for Molecular Graph Generation (2018, positive): “Graph Encoder We first encode the latent representation of G by a graph message passing network (Dai et al., 2016; Gilmer et al., 2017).”
Deriving Neural Architectures from Sequence and Graph Kernels (2017, methodology): “Dataset and Setup We further evaluate our graph NN models on the Harvard Clean Energy Project benchmark, which has been used in Dai et al. (2016); Duvenaud et al. (2015) as their evaluation dataset.”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “Finally, our theoretical results in Section 5 suggest that a principled design of layerwise propagation rules in graph neural networks inspired by additional message passing inference schemes (Dai et al., 2016; Gilmer et al., 2017) is another avenue for future research.”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, methodology): “For example, [54] embeds a graph with discrete node attribute value (e.”
Towards Sparse Hierarchical Graph Classifiers (2018, background): “…broadly fall into two categories: 1) aggregating node representations in a global pooling step after each [8] or after the ﬁnal message passing step [19, 5, 11], and 2) aggregating node representations into clusters which coarsen the graph in a hierarchical manner [4, 22, 6, 20, 24, 10, 21, 28, 1].”
Attention-based Graph Neural Network for Semi-supervised Learning (2018, background): “We give a typical example of a GNN in Section 3, but several diverse variations have been proposed in [10, 17, 29, 24, 39, 8, 15, 13, 3, 32, 38, 23, 37, 38].”
Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017, neutral): “[34] and to four approaches using deep learning as at least one of their components [2, 27, 40, 8].”
Graph networks as learnable physics engines for inference and control (2018, background): “…of graph neural networks (GNNs) (Scarselli et al., 2005; 2009a;b; Bruna et al., 2013; Li et al., 2015; Henaff et al., 2015; Du-venaud et al., 2015; Dai et al., 2016; Defferrard et al., 2016; Niepert et al., 2016; Kipf & Welling, 2016; Battaglia et al., 2016; Watters et al., 2017; Raposo et al.,…”
Syntax-Directed Variational Autoencoder for Structured Data (2018, background): “The recently developed deep learning models (Duvenaud et al., 2015; Dai et al., 2016; Lei et al., 2017) provide powerful candidates as encoder.”
The Multiscale Laplacian Graph Kernel (2016, background): “Most recently, structure2vec[12] attempts to represent each graph with a latent variable model and then embeds them into a feature space, using the inner product as a kernel.”
Devign: Effective Vulnerability Identification by Learning Comprehensive Program Semantics via Graph Neural Networks (2019, methodology): “[31] proposed Gemini for binary code similarity detection, where functions in binary code are represented by attributed control ﬂow graphs and input Structure2vec [22] for learning graph embedding.”