PaperlayerView exact revision on arXiv

Source-linked AI summary

Discriminative Embeddings of Latent Variable Models for Structured Data

Hanjun Dai, Bo Dai, Le Song

arXiv:1603.05629v5cs.LG

TL;DR

Existing structured-data kernel methods typically fix representations before discriminative learning, limiting scalability and label-informed feature learning. The paper proposes structure2vec, which embeds latent-variable models and learns explicit feature mappings through inference-like nonlinear functions. On million-scale data, it runs 2 times faster, produces models 10,000 times smaller, and achieves state-of-the-art predictive performance.

  • Problem

    Fixed kernel representations and kernel-matrix methods limit scaling to millions of structured-data points and prevent feature spaces from being learned directly from labels.

  • Method

    structure2vec embeds latent-variable graphical models into explicit feature spaces and learns nonlinear mappings using discriminative information, with inference-like updates.

  • Results

    2 times faster and 10,000 times smaller, structure2vec achieves state-of-the-art predictive performance on applications involving millions of data points.

  • Takeaways & Limitations

    The results support combining graphical models, Hilbert-space embeddings, and discriminative training for large-scale structured-data prediction.

  • Takeaways & Limitations

    The approach assumes a feature space with injective embeddings and uses a hyperparameter d selected by cross-validation.

Abstract

from arXiv · show

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.

1 Introduction

Kernel methods provide powerful structured-data representations, but fixed feature spaces and kernel matrices limit scalability and label-informed representation learning. structure2vec addresses these constraints by learning explicit embeddings through inference-like mappings and achieves strong predictive performance at large scale.

  • Motivation: Kernel methods rely on designed positive semidefinite similarities that implicitly choose feature representations for structured data.These representations can be infinite-dimensional, while downstream algorithms operate on pairwise kernel values.
  • Motivation: Bag-of-structures kernels fix dimensions to counts of elementary substructures before learning.Examples include spectrum, subtree, graphlet, and Weisfeiler-Lehman graph kernels.
  • Motivation: Graphical-model kernels exploit generative models such as hidden Markov models and pairwise Markov random fields.The Fisher kernel and probability product kernel are representative examples.
  • Approach: structure2vec embeds each structured data point's latent-variable model and learns the feature space by minimizing label-defined empirical loss.This directly incorporates discriminative information into representation learning.
  • Approach: structure2vec performs nonlinear mappings in a sequence resembling mean field and belief propagation, rather than probabilistic sum, product, and renormalization operations.A variant uses mean-field updates, and the mappings are learned from discriminative information.
  • Empirical results: 2 times faster and 10,000 times smaller, structure2vec matches state-of-the-art accuracy on a 2.3 million-molecule dataset.The comparison concerns runtime and model size while retaining the reported predictive-performance level.
  • Empirical results: The experiments indicate that combining graphical models, embeddings, and discriminative training improves performance on large-scale structured-data classification and regression problems.The reported evidence includes medium-scale sequence and graph benchmarks and the large Clean Energy Project dataset.

2 Backgrounds

The background develops kernel and distribution-embedding foundations for structured data. It emphasizes feature-map representations, injective embeddings, and their use for transferring operations from distributions into feature spaces.

  • Kernel methods: Kernel methods use symmetric positive semidefinite functions so learning algorithms can operate on pairwise kernel values without accessing original data.This modularity separates representation design from subsequent learning tasks.
  • Structured-data kernels: A structured-data kernel is an inner product between feature maps, including substructure-count representations such as spectrum and graphlet kernels.These bag-of-structures maps can have one dimension per possible subsequence or subgraph.
  • Structured-data kernels: Graphical-model kernels instead derive similarities from probabilistic models fitted globally or separately to individual data points.The Fisher kernel uses a common generative model, whereas the probability product kernel uses per-point models.
  • Distribution embeddings: Hilbert-space embeddings map probability distributions into feature spaces, and injective embeddings preserve distinctions between different distributions.The paper assumes a feature space with injective embeddings for later constructions.
  • Distribution embeddings: An injective embedding can support equivalent function and operator computations through corresponding mappings applied to the embedding.This is the stated basis for exploiting embeddings in later sections.
  • Graphical-model setup: Figure 1 builds hidden-variable graphical models from structured strings and general graphs, with Y representing regression or classification supervision.Y is real-valued for regression and discrete for classification.

3 Model for a Structured Data Point

The paper represents each structured object as a graphical model whose variables and conditional independences follow the object's graph. Hidden node variables motivate embedding posterior computations rather than standard maximum-likelihood estimation.

  • Graph representation: Each structured data point is treated as a graph, with sequences and trees included as special cases.Nodes carry attributes distinct from the label assigned to the entire data point.
  • Latent-variable model: The model assigns an observed-variable and an additional hidden variable to every graph node.A pairwise Markov random field is defined over these variables.
  • Latent-variable model: The input graph directly determines the graphical model's conditional-independence structure.More complex models could add longer-range interactions beyond pairwise potentials.
  • Latent-variable model: Each data point receives its own graphical model, so two inputs may have different conditional-independence structures.The model topology therefore varies with the structured input.
  • Inference and learning: Because hidden variables are unobserved, the paper embeds posterior computations instead of pursuing standard maximum-likelihood estimation.The approach follows the sequence of computations needed to embed the hidden-variable posterior.

4 Embedding Latent Variable Models

The paper embeds latent-variable graphical-model marginals and messages into finite-dimensional feature spaces, replacing probabilistic inference operations with learned nonlinear mappings. Mean-field and loopy belief-propagation updates can thereby be parameterized and trained using discriminative supervision, with extensions to other variational methods.

  • Embedding latent variable models: Posterior marginals of hidden variables are embedded into finite-dimensional feature spaces, whose mappings and model parameters are learned later from supervision.The embedding dimension d is selected by cross-validation, while exact inference over general graphs is difficult.
  • Embedding latent variable models: Only trees permit efficient exact message-passing computation; general graphs therefore motivate approximate methods such as mean field and loopy belief propagation.These methods are presented as empirically effective despite their approximation of exact inference.
  • Embedding mean-field inference: Mean-field updates are reinterpreted as nonlinear function mappings of embedded marginals rather than probabilistic operations over densities.This view converts iterative inference updates into mappings that can be implemented in embedding space.
  • Embedding mean-field inference: Instead of deriving the embedding operator from graphical-model potentials, the method directly parameterizes it and learns it with supervision.The parameterization can use nonlinear mappings such as neural networks with rectified linear units.
  • Embedding loopy BP and other variational methods: Loopy belief propagation embeds messages and marginals, while the same strategy extends to double-loop, damped, tree-reweighted, and generalized belief propagation.Messages are intermediate nonnegative functions that can be normalized and embedded; their update mappings are learned from discriminative supervision.

5 Discriminative Training

structure2vec learns feature spaces and prediction functions jointly from label information, rather than fixing feature spaces beforehand. It trains shared parameters across structure-specific graphical models using discriminative objectives and scalable stochastic optimization.

  • Unlike kernel BP and kernel EP, structure2vec learns feature spaces and the target regressor or classifier end-to-end from label information.
  • Each structured datum is represented by a graphical model with embedded features, while embedding and prediction parameters are shared across individual structures.
  • For classification, structure2vec uses a softmax loss to jointly estimate embedding parameters and the discriminative classifier.
  • The model aggregates embedded marginals and applies a prediction function for regression or classification, with all components learned using supervision.
  • Stochastic gradient descent optimizes the discriminative objective, with parameter gradients computed recursively in a message-passing structure.

6 Experiments

Experiments evaluate structure2vec on string and graph benchmarks, then test scalability and prediction quality on 2.3 million molecules. The method is competitive on medium datasets and combines efficient large-scale training with strong predictive performance.

  • String datasets: Two structure2vec variants are consistently better than string kernels on mean AUC, with a larger improvement on SCOP than FC RES.The paper attributes this difference partly to SCOP’s larger alphabet and the resulting dimensionality of k-mer features.
  • Graph datasets: The embedding methods achieve accuracy comparable to alternative graph kernels across graph datasets with differing numbers of nodes, edges, and labels.The comparison uses five benchmark datasets: MUTAG, NCI1, NCI109, ENZYMES, and D&D.
  • Graph datasets: On D&D, structure2vec performs much better while avoiding graph-kernel dictionary construction that can require more than a year of CPU time.The method learns discriminative embeddings directly from structured data.
  • Harvard Clean Energy Project: On the 2.3 million-sample CEP dataset, structure2vec predicts PCE values effectively, while its two variants perform equally well.The evaluation reports MAE and RMSE and emphasizes graph information for prediction.
  • Harvard Clean Energy Project: Compared with a degree-6 WL tree kernel, structure2vec uses 10,000 times fewer parameters and runs 2 times faster while retaining strong prediction performance.The WL tree kernel also requires preprocessing that complicates use on large datasets.
  • Inference iterations: Higher fixed-point iteration counts lead to faster convergence, while mean-field embedding performs much worse with only one iteration.The number of model parameters remains the same across iteration settings.

7 Conclusion

The conclusion presents structure2vec as a scalable discriminative embedding approach that combines latent-variable graphical models with learned feature mappings. Its design supports multiple inference-inspired architectures and delivers strong performance with reduced computational and memory requirements.

  • Conclusion: Structure2vec embeds latent variable models into feature spaces and learns those spaces using discriminative information.The approach is intended for structured data representation.
  • Conclusion: Its feature extraction applies successive nonlinear function mappings in a manner similar to mean-field and belief-propagation inference.The framework connects graphical-model inference with learned embeddings.
  • Conclusion: The paper reports that structure2vec runs 2 times faster and produces models 10,000 times smaller on applications involving millions of data points.The reported result is paired with state-of-the-art predictive performance.

B Derivation of the Fixed-Point Condition for Mean-Field Inference

The mean-field derivation starts from the variational free-energy objective and obtains a fixed-point condition by differentiating with respect to node beliefs. Conditional independence then simplifies that condition into the form used by the embedding procedure.

  • Mean-field derivation: Mean-field inference is formulated as minimizing variational free energy.
  • Mean-field derivation: Substituting the Markov random field into the objective provides the expression from which the fixed-point condition is derived.
  • Mean-field derivation: Taking derivatives with respect to q_i(h_i) and setting them to zero yields the mean-field fixed-point condition.
  • Mean-field derivation: Conditional independence between h_i and x_j given h_j further reduces the fixed-point condition.
  • Mean-field derivation: The reduced condition contains an integral involving q_j(h_j) and log Φ(h_j, x_j).

C Derivation of the Fixed-Point Condition for Loopy BP

The loopy-BP derivation uses constrained variational optimization to recover marginal and message updates, then parameterizes messages and beliefs in an embedding space. The same embedding view connects several BP variants after their respective free-energy formulations are derived.

  • Loopy BP derivation: Loopy BP is derived from an objective over pairwise and node beliefs with entropy and potential terms.
  • Loopy BP derivation: Lagrange multipliers enforce marginalization, normalization, and marginal-consistency constraints during optimization.
  • Loopy BP derivation: Functional derivatives recover the loopy-BP updates for marginal beliefs and messages.
  • Embedding parameterization: The embedding parameterization represents messages and node marginals with shared learned function forms and vector embeddings.
  • Embedding parameterization: The proposed embedding can be adapted to variational methods based on Bethe, convexified Bethe, and Kikuchi free energies.
  • Embedding parameterization: After parameterization, double-loop BP and damped BP produce essentially the same embeddings, revealing a connection between the two methods.
  • Embedding parameterization: Tree-reweighted BP introduces edge parameters representing probabilities that edges appear in randomly selected spanning trees.

D.4 Generalized Belief Propagation

The generalized belief-propagation embedding extends the framework to region-based interactions using Kikuchi free energy and message updates over nested regions.

  • Kikuchi free energy: Kikuchi free energy generalizes Bethe free energy by incorporating high-order interactions among regions.Regions include clusters, intersections, and recursively defined subregions or superregions.
  • Kikuchi free energy: The over-counting number c_r is defined recursively from the superregions, with c_r = 1 for the largest region.
  • Generalized belief propagation: Generalized loopy belief propagation seeks stationary points of Kikuchi free energy under regional marginal-consistency and density-validation constraints.It does so through message updates.
  • Generalized belief propagation: The message sets M(r) and M(r, s) specify dependencies among messages entering regions and subregions.
  • Embedding updates: The embedding parameterization uses neural networks, and generalized BP updates begin with messages into the smallest regions.The choice of basis clusters and message forms determines embedding dependencies.
  • Experiments: Table 4 reports 10-fold cross-validation accuracy on graph-classification benchmark datasets, using “sp” for shortest-path.

E More experiments

This section introduces a more detailed study of the proposed structure2vec method.

  • More experiments: The paper presents a more detailed study of structure2vec in this section.
  • More experiments: The detailed study concerns the proposed structure2vec method.
  • More experiments: This section marks the beginning of the paper’s more detailed structure2vec analysis.

E.1 Graph classification task

The graph-classification experiments also describe how supervised gradients are propagated through the unfolded embedding iterations and used to update embedding parameters.

  • Gradient computation: The supervised label message for the n-th sample is obtained using the chain rule through the embedding computation.
  • Parameter dependence: The gradients depend on the supervised information, loss function, and nonlinear function used by the model.
  • Embedded mean field: For embedded mean field, the fixed-point equation is unfolded over iterations t = 1, 2, ..., T, enabling recursive derivative computation.
  • Embedded loopy BP: For embedded loopy BP, derivatives with respect to hidden-variable embeddings are obtained from the final message-passing round.
  • Gradient computation: Derivatives with respect to pairwise message embeddings are computed recursively across the fixed-point iterations.
  • Parameter updates: Embedding parameters are updated using derivatives with respect to hidden-node embeddings and the model parameters W1 and W2.
Loading 1603.05629v5…