PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Graph Embedding with Adversarial Training Methods

Shirui Pan, Ruiqi Hu, Sai-fu Fung, Guodong Long, Jing Jiang, Chengqi Zhang

arXiv:1901.01250v2cs.LGstat.ML

TL;DR

Existing graph embedding methods often overlook the distribution of latent codes while focusing on structure preservation or reconstruction. The paper introduces adversarially regularized graph autoencoders that combine graph convolutional encoding, graph reconstruction, and prior-distribution matching, with experiments validating the resulting approaches across link prediction and graph clustering.

  • Problem

    Graph embedding methods commonly focus on preserving graph structure or minimizing reconstruction error while overlooking the distribution of latent codes.

  • Method

    The framework uses a graph convolutional encoder for topology and node content, reconstructs graph information, and adversarially regularizes latent codes toward a prior distribution through ARGA and ARVGA.

  • Results

    Experiments on benchmark datasets show that the proposed approaches outperform other methods on different unsupervised tasks, including link prediction and graph clustering.

  • Takeaways & Limitations

    Adversarial regularization offers a framework for learning graph embeddings that jointly represent topology and node content while constraining latent-code distributions.

Abstract

from arXiv · show

Graph embedding aims to transfer a graph into vectors to facilitate subsequent graph analytics tasks like link prediction and graph clustering. Most approaches on graph embedding focus on preserving the graph structure or minimizing the reconstruction errors for graph data. They have mostly overlooked the embedding distribution of the latent codes, which unfortunately may lead to inferior representation in many cases. In this paper, we present a novel adversarially regularized framework for graph embedding. By employing the graph convolutional network as an encoder, our framework embeds the topological information and node content into a vector representation, from which a graph decoder is further built to reconstruct the input graph. The adversarial training principle is applied to enforce our latent codes to match a prior Gaussian or Uniform distribution. Based on this framework, we derive two variants of adversarial models, the adversarially regularized graph autoencoder (ARGA) and its variational version, adversarially regularized variational graph autoencoder (ARVGA), to learn the graph embedding effectively. We also exploit other potential variations of ARGA and ARVGA to get a deeper understanding on our designs. Experimental results compared among twelve algorithms for link prediction and twenty algorithms for graph clustering validate our solutions.

I. INTRODUCTION

Graph embedding provides compact continuous representations for graph analytics, but existing approaches often overlook latent-code distributions. The paper addresses this gap with adversarial regularization, introducing ARGA and ARVGA and evaluating them on unsupervised tasks.

  • Graph embedding transfers graph data into a low-dimensional continuous feature space for tasks including classification, clustering, and link prediction.
  • Many existing methods preserve graph structure or minimize reconstruction error while largely ignoring the latent distribution of the representation.
  • The proposed framework minimizes reconstruction error while enforcing latent codes to match a prior distribution.
  • ARGA and ARVGA combine adversarial regularization with graph autoencoder models for graph embedding.
  • The authors examine prior distributions, decoder construction, and reconstruction targets to assess their influence across tasks.
  • Benchmark experiments report that the proposed graph embedding approaches outperform other methods on different unsupervised tasks.

II. RELATED WORK

Related work spans probabilistic, matrix-factorization, deep-learning, and adversarial approaches to graph embedding. The paper positions its contribution as adversarial regularization that handles both topology and node content.

  • Graph Embedding Models: Graph embedding methods include probabilistic, matrix-factorization, and deep-learning approaches.
  • Graph Embedding Models: Probabilistic methods learn embeddings from graph patterns such as random walks, while matrix-factorization methods factorize graph-derived adjacency representations.
  • Graph Embedding Models: Existing graph embedding algorithms largely ignore embedding distributions, which may produce poor representations on real graph data.
  • Adversarial Models: Earlier adversarial autoencoder and graph methods either target general data or exploit only topological information.
  • Adversarial Models: The proposed work applies graph convolutional models with adversarial training to learn robust graph embeddings from graph structure and node content.

C. Graph Convolutional Nets based Models

The framework uses graph convolutional encoding to combine adjacency structure and node content into embeddings, then reconstructs graph information while adversarially matching latent codes to a prior.

  • A graph is represented by nodes, edges, and node features, with adjacency matrix A encoding graph topology and X encoding textual node content.
  • The embedding function maps graph inputs (A, X) to an embedding matrix Z whose rows are low-dimensional node vectors.
  • ARGA uses a graph convolutional autoencoder, whereas ARVGA replaces the upper tier with a variational graph autoencoder.
  • The graph autoencoder uses A and X to learn latent representation Z and reconstruct graph structure A from Z.
  • The adversarial network discriminates whether latent codes come from the encoder or a prior distribution, thereby regularizing the embedding.

A. Graph Convolutional Autoencoder

The graph convolutional autoencoder uses GCN layers to encode graph structure and node content into a latent representation, then reconstructs selected graph data. Its variational form models the latent representation probabilistically and regularizes it toward a prior distribution.

  • The model addresses simultaneous integration of graph structure A and node features X in an encoder, with decoder reconstruction of graph data.
  • GCN layers transform node features using graph structure A, beginning with Z0 = X and learning filter matrices W^(l).
  • The two-layer graph convolutional encoder maps graph structure and node content into embedding matrix Z.
  • The variational graph encoder represents q(Z|X,A) using node-wise Gaussian distributions parameterized by means µi and variances σ².
  • The basic decoder predicts links from Z so reconstructed adjacency matrix  approximates the ground-truth adjacency matrix A.
  • Optimization combines graph-data reconstruction with a variational lower bound whose prior p(Z) may be Uniform or Gaussian.

B. Adversarial Model D(Z)

The adversarial model regularizes graph embeddings by training a discriminator to distinguish prior samples from encoder-generated latent codes. Encoder updates then make the latent representation match the selected prior distribution.

  • A sigmoid MLP discriminator distinguishes latent codes sampled from prior pz as positive examples from graph-encoder outputs G(X,A) as negative examples.
  • Adversarial training minimizes binary-classifier cross-entropy so the embedding is regularized toward the prior distribution.
  • The framework uses graph G = {V,E,X}, iterates T times, and returns a latent matrix Z ∈ R^n×d.
  • Each iteration generates Z, samples latent codes and prior entities, and updates the discriminator for K steps before updating the graph autoencoder.

C. Algorithm Explanation

Algorithm 1 alternates discriminator training with graph-autoencoder training. It compares generated latent samples with samples from the prior before updating the encoder using the resulting adversarial gradient.

  • The algorithm obtains latent variables from the graph convolutional encoder, then samples equally many codes from generated Z and prior distribution pz.
  • After K discriminator updates using cross-entropy, the graph encoder is updated to confuse the trained discriminator.

D. Decoder Variations

The framework extends its decoder beyond link prediction to graph-convolutional reconstruction of topology, or jointly topology and node content. These variants are paired with standard or variational upper-tier encoders and Gaussian or Uniform priors.

  • The basic ARGA and ARVGA decoders use a dot-product link-prediction layer, while alternative decoders can use graph convolutional layers or combine both designs.
  • ARGA GD adds two graph convolutional decoder layers that take encoder embeddings as input to reconstruct graph structure A.
  • ARGA GD uses a standard graph convolutional autoencoder in its upper tier, while ARVGA GD substitutes a variational graph autoencoder.
  • ARGA AX modifies the graph convolutional decoder to reconstruct both adjacency structure A and node-content matrix X.
  • For ARGA AX, the final reconstruction loss is the sum of graph-structure and node-content reconstruction errors.

V. EXPERIMENTS

The experiments evaluate graph embedding models on citation-graph link prediction and compare how input information, latent regularization, and embedding dimension affect performance.

  • Experimental Setup: The experiments use Cora, Citeseer, and Pubmed citation networks, with publications as nodes, citations as edges, and document words as features.Each experiment separates edges into training, validation, and testing sets and reports means with standard errors over 10 runs.
  • Compared Models: ARGA and ARVGA are evaluated as adversarially regularized autoencoder and variational graph autoencoder approaches, with decoder variants that reconstruct structure or structure plus content.The comparisons examine the effects of distributions, decoder architectures, and reconstruction choices.
  • Evaluation: The link-prediction evaluation reports AUC and average precision, comparing twelve algorithms and distinguishing models that reconstruct graph structure, node content, or both.GAE* and VGAE* use topology only, while other variants incorporate node content and may reconstruct different inputs.
  • Link Prediction: Models using both node content and topology consistently outperform models using graph structure alone.The reported gap between ARGA and GAE indicates an advantage for latent-code regularization in learning robust embeddings.
  • Parameter Study: Embedding dimension is varied from 8 to 1024 neurons on Cora, with performance generally improving as the dimension increases.Performance rises from 8 to 16 neurons, fluctuates at 32 while remaining good, and rises dramatically at 64, 128, and 1024 neurons for both AP and AUC.

B. Node Clustering

The study evaluates graph embeddings for node clustering using K-means and compares twenty approaches across Cora, Citeseer, and Pubmed. ARGA and ARVGA substantially outperform baselines across clustering metrics, while embedding dimension shows no clear trend.

  • The clustering evaluation uses K-means on learned embeddings and five metrics: accuracy, F1, NMI, precision, and average.
  • The clustering comparison includes twenty approaches, with Circle omitted on Pubmed because one experiment exceeded three days without producing an outcome.
  • ARGA and ARVGA achieve dramatic improvements over all baselines across five clustering metrics on Cora, Citeseer, and Pubmed.
  • Methods using only graph structure or node content underperform methods combining topological information and node content.
  • Varying embedding dimensions from 8 to 1024 produces fluctuations without an apparent score trend, suggesting unsupervised clustering is parameter-sensitive.

C. ARGA Architectures Comparison

The architecture study compares ARGA and variational variants using different priors, decoders, and reconstruction targets. Performance depends on these choices, especially for link prediction, while reconstructing both structure and content improves graph-convolutional decoder variants.

  • Gaussian Distribution vs Uniform Distribution: Uniform priors dramatically reduce ARGA DG link-prediction performance across all datasets and metrics relative to Gaussian priors.
  • Gaussian Distribution vs Uniform Distribution: ARGA and ARVGA are less sensitive to prior choice than ARGA DG, with standard and variational versions favoring different priors slightly.
  • Decoders and Reconstructions: The Gaussian-prior ARGA with an inner-product decoder for graph-structure reconstruction has a significant link-prediction advantage.
  • Decoders and Reconstructions: ARGA DG performs sub-optimally because its graph-convolutional decoder does not effectively decode topological information.
  • Decoders and Reconstructions: ARGA AX, which reconstructs both graph structure and node content, substantially improves link prediction and clustering over ARGA DG.

D. Time Complexity on Convollution

The convolutional encoder uses sparse matrix operations to reduce computational cost. Training-time experiments show that adversarial regularization and simultaneous reconstruction of structure and content increase computation.

  • The graph convolution operation has complexity O(|E|md) because adjacency multiplication uses sparse-by-dense matrix multiplication.
  • Computing the inverse of the diagonal degree matrix requires O(|V|) time.
  • Training-time comparisons use six ARGA models and two GAE models over 200 link-prediction epochs on Cora.
  • ARGA models take longer than original GAE models because of the additional regularization module.
  • ARGA AX requires more computation because it reconstructs both topological structure and node characteristics.

VI. CONCLUSION AND FUTURE WORK

The paper presents an adversarial graph embedding framework whose ARGA and ARVGA variants produce robust representations and outperform baselines on link prediction and node clustering. Future work will extend ARGA to realistic graph generation and incorporate label information.

  • ARGA and ARVGA jointly regularize latent codes with adversarial training and graph convolutional autoencoding to produce robust graph representations.The framework reconstructs graph data while matching latent codes to a prior distribution.
  • The proposed algorithms outperform baselines on link prediction and node clustering tasks.
  • Future work will investigate using ARGA to generate realistic graphs, potentially supporting drug discovery in biological domains.
  • Future work will also incorporate label information into ARGA to learn robust graph embeddings.
Loading 1901.01250v2…