PaperlayerView exact revision on arXiv

Source-linked AI summary

Adversarial Network Embedding

Quanyu Dai, Qiang Li, Jian Tang, Dan Wang

arXiv:1711.07838v1cs.LG

TL;DR

Existing network embedding methods capture structural properties but often lack constraints that improve robustness to noisy data. ANE combines structure preservation with adversarial learning, and empirical evaluations find it competitive with or superior to state-of-the-art methods on benchmark tasks.

  • Problem

    Existing network embedding methods lack additional constraints for robust representations, limiting their reliability when network data are noisy.

  • Method

    ANE combines structure preservation with adversarial learning that regularizes representations by matching their distribution to a prior.

  • Results

    AIDW achieves the best classification accuracy across three benchmark datasets and training ratios, except Wiki at a 10% training ratio.

  • Takeaways & Limitations

    Empirical evaluations in network visualization and node classification support ANE’s effectiveness for learning robust graph representations.

  • Takeaways & Limitations

    The choice of prior distribution may further improve application-specific performance when guided by domain knowledge.

Abstract

from arXiv · show

Learning low-dimensional representations of networks has proved effective in a variety of tasks such as node classification, link prediction and network visualization. Existing methods can effectively encode different structural properties into the representations, such as neighborhood connectivity patterns, global structural role similarities and other high-order proximities. However, except for objectives to capture network structural properties, most of them suffer from lack of additional constraints for enhancing the robustness of representations. In this paper, we aim to exploit the strengths of generative adversarial networks in capturing latent features, and investigate its contribution in learning stable and robust graph representations. Specifically, we propose an Adversarial Network Embedding (ANE) framework, which leverages the adversarial learning principle to regularize the representation learning. It consists of two components, i.e., a structure preserving component and an adversarial learning component. The former component aims to capture network structural properties, while the latter contributes to learning robust representations by matching the posterior distribution of the latent representations to given priors. As shown by the empirical results, our method is competitive with or superior to state-of-the-art approaches on benchmark network embedding tasks.

Introduction

The introduction motivates Adversarial Network Embedding (ANE) as a way to address the fragility of unsupervised network embeddings on noisy data. ANE combines structure preservation with adversarial training to learn more robust representations.

  • Motivation: Node embedding learns low-dimensional representations that encode rich information from graph-structured data for graph analysis.The passage cites node embedding as an efficient and effective approach to analyzing graphs, including citation networks.
  • Related Work: Existing network embedding methods capture local connectivity, first- and second-order proximities, structural equivalence, and other high-order proximities.Examples include DeepWalk, LINE, and node2vec.
  • Problem: Existing structure-preserving methods lack additional constraints for robustness, making unsupervised embeddings vulnerable to noisy network data.The passage states that noisy real-world networks can produce poor representations.
  • Contribution: ANE learns robust network representations by adding adversarial learning to the objective for preserving network structure.The adversarial process is introduced to model data uncertainty.
  • Framework: ANE unifies a structure-preserving component with adversarial training using samples from a prior distribution.The structure-preserving component captures network properties, while adversarial training improves representation robustness; the framework uses an inductive DeepWalk variant.

Related Work · Network Embedding Methods

Unsupervised network embedding methods are organized into probabilistic, matrix factorization-based, and autoencoder-based approaches. These methods respectively learn representations from random-walk sequences, processed adjacency matrices, or reconstruction-oriented latent spaces.

  • Network Embedding Methods: Unsupervised network embedding methods are divided into probabilistic, matrix factorization-based, and autoencoder-based groups.The classification is based on the techniques used.
  • Network Embedding Methods: Probabilistic methods include DeepWalk, LINE, and node2vec.These examples are identified as representative probabilistic approaches.
  • Network Embedding Methods: DeepWalk generates node sequences through random walks and learns latent representations with Skip-gram.The method treats node sequences as word sentences.
  • Network Embedding Methods: LINE preserves first-order and second-order proximities using separate objectives, then concatenates the resulting representations.Its two proximity types are optimized separately before direct concatenation.
  • Network Embedding Methods: Node2vec uses biased random walks to determine neighboring structure and balance homophily.The supplied passage states the balance objective but is truncated before specifying its counterpart.
  • Network Embedding Methods: Matrix factorization methods preprocess adjacency matrices to capture high-order proximities before decomposing them into graph embeddings.GraRep uses a PPMI matrix, based on an equivalence between k-step DeepWalk walks and k-step probability transition matrices.
  • Network Embedding Methods: Autoencoders learn compact representations by preserving information in latent space for reconstructing the original data.This reconstruction-oriented formulation motivates autoencoder-based network embedding methods.
  • Network Embedding Methods: DNGR computes a PPMI matrix before learning representations with a stacked denoising autoencoder, while SDNE adds a loss-function constraint.Both methods are presented as autoencoder-based approaches.

Generative Adversarial Networks

GANs use a generator and discriminator in a minimax adversarial game, but are not directly suited to unsupervised representation learning. Prior work addresses this through inference structures or discriminator hidden-layer representations, with applications including robust image classification and document retrieval.

  • GAN fundamentals: GANs comprise a generator and discriminator that play a minimax game between generating samples from a prior and distinguishing fake from real data.The generator maps prior-distribution samples to data space, while the discriminator separates generated samples from real data.
  • Representation learning: GANs are not directly suitable for unsupervised representation learning because the framework lacks explicit support for inferring latent features from data.
  • Existing approaches: Prior approaches learn representations by integrating inference structures, using discriminator hidden layers, or applying fractionally-strided convolutional layers.Examples include BiGAN, ALI, EBGAN, and DCGANs.
  • Existing approaches: These approaches can learn robust representations in applications such as image classification and document retrieval.

Problem Definition and Notations

Network embedding learns meaningful node representations from an information network modeled as G = (V, E, A), with edges encoding relationships and A quantifying their strengths.

  • Problem Definition and Notations: An information network is represented as G = (V, E, A), where V contains nodes, E contains pairwise relationships, and A is a weighted adjacency matrix.For unweighted graphs, entries in A are 0 or 1, indicating whether an edge exists.

An Overview of the Framework

The ANE framework uses adversarial learning to learn stable and robust network representations. It combines a structure-preserving component for encoding network structural information with an adversarial component that regularizes representation learning.

  • Framework components: ANE consists of a structure-preserving component and an adversarial learning component.The framework is designed to leverage adversarial learning for stable and robust representations.
  • Framework components: The structure-preserving component encodes network structural information into the representations.The passage identifies exploring nodes’ local neighborhood connectivity patterns as part of this structural encoding.
  • Framework components: The adversarial component uses a generator G(·) and discriminator D(·) to regularize learning a stable and robust feature extractor.During training, G(·)'s parameters are updated directly instead of the embedding vectors.

Graph Preprocessing

The method preprocesses sparse network adjacency information into shifted PPMI features for the generator, using high-order proximities to characterize node contexts. These features derive from normalized transition probabilities aggregated across multiple path lengths, with β set to 1/N.

  • Graph Preprocessing: The generator uses a shifted PPMI matrix X as input features to alleviate network sparsity and its potential over-fitting effects.The preprocessing incorporates high-order proximities before representation learning.
  • Graph Preprocessing: M =  + Â^2 + · · · + Â^t aggregates high-order proximities across multiple transition steps. is the 1-step probability transition matrix obtained by row-normalizing the weighted adjacency matrix A.
  • Graph Preprocessing: Each row vector x_i^T in X encodes node v_i’s graph-context information, but remains high-dimensional.The context features are constructed from the high-order proximity matrix.
  • Graph Preprocessing: The preprocessing sets β to 1/N in the shifted PPMI construction.β is the parameter specified for the PPMI-based input features.

Structure Preserving Model

The structure-preserving component uses parameterized neural generators to encode node dependencies and capture network structural properties. It supports attribute-aware, nonlinear representations and optimizes target-context relationships with negative sampling.

  • Representation generation: Unlike transductive embedding-lookup methods such as DeepWalk and LINE, the parameterized generator can use node attributes and model nonlinear network properties.Existing scalable methods can also preprocess raw graphs to provide lower-dimensional input features for large networks.
  • Structural objective: IDW samples η random-walk sequences of length l from each node, selecting neighbors with probability proportional to edge weights and using alias tables for efficiency.The alias table method takes O(1) time for a single sampling step.
  • Representation generation: The model generates target and context node representations from input features using parameterized neural-network functions G and F.For node v_i with feature row x_i^T, the target representation is produced as u_i = G(x_i; θ_1), with the context representation generated analogously.
  • Structural objective: Network structure is learned by optimizing an objective over positive target-context node pairs with negative sampling.The objective uses K negative samples per positive pair and samples negative context nodes from a noise distribution P_n(v).

Adversarial Learning

The adversarial learning component regularizes network representations by matching embedding vectors to samples from a chosen prior distribution. The framework combines a shared generator and discriminator with structure-preserving models, including IDW and DAE, while considering Uniform and Gaussian priors.

  • Adversarial Learning: Adversarial learning regularizes representations through a generator that transforms high-dimensional input features into embedding vectors and a discriminator that distinguishes real from generated samples.The generator is shared with the structure-preserving component.
  • Adversarial Learning: Unlike standard GANs, ANE treats samples from a selected prior distribution as real data and embedding vectors as fake samples.The discriminator is trained to distinguish prior samples from embedding vectors.
  • Adversarial Learning: The framework instantiates adversarial learning with inductive DeepWalk and denoising autoencoder structure-preserving components, producing AIDW in the former case.The authors associate adversarial learning with improved robustness and structural meanings in learned representations.
  • Adversarial Learning: ANE considers Uniform and Gaussian noise priors, which are described as enabling meaningful and robust representations against uncertainty.The paper states that both prior types were considered in experiments but truncates the reported comparison.

Algorithm

ANE is implemented through joint training with separate structure-preserving and adversarial-learning phases. The adversarial phase imposes a prior on representations through minimax optimization while addressing mode collapse in traditional GAN training.

  • Training procedure: ANE uses joint training with a structure-preserving phase followed by an adversarial-learning phase.The structure-preserving phase optimizes objective function (2) for AIDW.
  • Adversarial learning: The adversarial phase imposes a prior distribution on representations through a minimax optimization problem.This phase trains a discriminator to distinguish prior samples from embedding vectors before updating generator parameters.
  • Adversarial learning: The training procedure is designed to avoid mode collapse in traditional GAN training.

Experiments

Experiments on citation, web-page, and other real-world networks evaluate ANE through visualization, node classification, and parameter sensitivity analyses. AIDW generally improves representation quality and robustness over structure-preserving methods and baselines, while ADAE provides more limited gains over DAE.

  • Network visualization: t-SNE visualizations on Cit-DBLP show that AIDW produces clearer, better-separated category clusters than DeepWalk and LINE.DeepWalk and LINE mix categories near the center; LINE also produces six clusters that conflict with the true three-category structure and has unclear boundaries.
  • Multi-class classification: AIDW consistently outperforms IDW and DeepWalk across Cora, Citeseer, and Wiki and all training ratios.On Cora, AIDW gains more than 4% accuracy over DeepWalk under every training-ratio setting.
  • Multi-class classification: ADAE gains about 1% accuracy over DAE on Citeseer, performs slightly better on Cora, and is comparable on Wiki.ADAE does not show obvious improvements over its corresponding structure-preserving model, unlike AIDW.
  • Multi-class classification: AIDW achieves the best classification accuracy across the three benchmark datasets and training ratios, except on Wiki at a 10% training ratio.Node2vec performs better than DeepWalk, LINE, and GraRep on average, while AIDW improves further over node2vec.
  • Parameter sensitivity: AIDW accuracy increases with representation dimension before saturating around 128, while remaining relatively stable across tested walk lengths and context sizes.Accuracy becomes stable for walk lengths from 40 to 100 and slightly degrades when context size exceeds 6.

Conclusion

The paper proposes an adversarial network embedding framework for robust graph representations. It combines structure preservation through inductive DeepWalk with adversarial learning that imposes a prior distribution via minimax optimization.

  • Conclusion: The proposed framework targets robust graph representation learning through adversarial network embedding.It is designed to learn robust graph representations.
  • Conclusion: Its structure-preserving component uses inductive DeepWalk to capture network structural properties.Inductive DeepWalk provides the framework’s structure-preserving mechanism.
  • Conclusion: Its adversarial component formulates a minimax optimization problem that imposes a prior distribution on representations to enhance robustness.The prior-distribution constraint is introduced through adversarial learning.
  • Conclusion: The framework was empirically evaluated in network visualization.The supplied passage indicates empirical evaluation in network visualization but does not report its results.
Loading 1711.07838v1…