PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-supervised Learning on Graphs with Generative Adversarial Nets

Ming Ding, Jie Tang, Jie Zhang

arXiv:1809.00130v1cs.SIcs.AI

TL;DR

The paper addresses the limited use of GANs for semi-supervised learning on graphs. It introduces GraphSGAN, whose generator-classifier game places fake samples in density gaps; the paper reports benchmark superiority and scalability.

  • Problem

    Few prior works explored GANs for semi-supervised learning on graphs.

    Source: §1 · p. 1

  • Method

    GraphSGAN trains a generator and classifier in a competitive game that generates fake samples in low-density gaps between subgraphs at equilibrium.

    Source: §1 · p. 1, §3.3.1 · p. 3

  • Results

    GraphSGAN significantly outperforms previous works across datasets and demonstrates outstanding scalability.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The density-gap working principle can improve graph Laplacian regularization with theoretical guarantees and experimental validation.

    Source: §7 · p. 10

    Future work includes stabilizing and accelerating training, investigating more ideal equilibria, and strengthening the method’s theoretical basis.

    Source: §7 · p. 10

Abstract

from arXiv · show

We investigate how generative adversarial nets (GANs) can help semi-supervised learning on graphs. We first provide insights on working principles of adversarial learning over graphs and then present GraphSGAN, a novel approach to semi-supervised learning on graphs. In GraphSGAN, generator and classifier networks play a novel competitive game. At equilibrium, generator generates fake samples in low-density areas between subgraphs. In order to discriminate fake samples from the real, classifier implicitly takes the density property of subgraph into consideration. An efficient adversarial learning algorithm has been developed to improve traditional normalized graph Laplacian regularization with a theoretical guarantee. Experimental results on several different genres of datasets show that the proposed GraphSGAN significantly outperforms several state-of-the-art methods. GraphSGAN can be also trained using mini-batch, thus enjoys the scalability advantage.

1 INTRODUCTION

The paper investigates GANs for graph-based semi-supervised learning, where few prior works had explored their use. It introduces GraphSGAN, analyzes its density-gap mechanism, and reports theoretical guarantees, benchmark gains, and scalability.

1 INTRODUCTION

  • Prior graph-learning approaches include Laplacian regularization and graph embedding; cited examples include Label Propagation and Planetoid [38].The paper also notes strong performance by graph convolution networks [17] and attention-based extensions [34].Source: §1 · p. 1
  • The paper investigates GANs for graph semi-supervised learning, a setting with few prior GAN-based works.GANs train a generator and discriminator in a min-max game.Source: §1 · p. 1
  • GraphSGAN uses a generator-classifier game to place fake samples in low-density gaps between subgraphs, reducing nearby samples’ influence and helping classification.The authors analyze the game’s dynamics, equilibrium, and working principles.Source: §1 · pp. 1–2
  • The adversarial technique is theoretically shown to yield perfect classification with plentiful but finite generated samples.The paper also connects the approach to improvements of traditional graph Laplacian regularization.Source: §1 · pp. 1–2
  • GraphSGAN significantly outperforms several state-of-the-art methods on datasets of different genres and supports mini-batch training for scalability.The paper also reports evaluation across datasets of different scales.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries define graph-based semi-supervised learning using labeled and unlabeled nodes, node features, and graph structure. They also describe GANs as a min-max game between a generator and a discriminator.

2.1 Problem Definition

  • Graph semi-supervised learning predicts unlabeled-node labels using node features and graph structure; the paper mainly studies transductive learning on undirected graphs.The setting has far fewer labeled than unlabeled nodes, and the authors note that extension to directed graphs is straightforward.Source: §2.1 · p. 2

2.2 Generative Adversarial Nets (GANs)

  • A GAN trains a generator to fit the training data and a discriminator to distinguish real samples from generated samples in a min-max game.The loss uses training-data distribution p_d and input-noise prior p_z.Source: §2.2 · p. 2

3 MODEL FRAMEWORK

GraphSGAN uses a generator and classifier to place fake samples in density gaps between graph subgroups, aiming to reduce harmful propagation across those gaps. It maps graph nodes into feature space and trains the networks through a competitive game with losses designed to produce the expected equilibrium.

3.1 Motivation

  • GraphSGAN targets density gaps between subgraphs, where fake-sample discrimination is intended to weaken label propagation across the gaps.The motivation contrasts two subgraphs and their intervening density gap; the approach generates samples there and seeks higher classification-function curvature around the gap.Source: §3.1 · pp. 2–3

3.2 Architecture

  • GraphSGAN represents each node by concatenating its original features with a learned network embedding, then feeds real and generated inputs to a classifier.The classifier and generator are multilayer perceptrons; the classifier uses a fake-class output and extracts hidden representations for feature matching.Source: §3.2 · p. 3, Figure 2 · p. 3

3.3.1 Game and Equilibrium.

  • The model modifies GAN losses so that, at equilibrium, generated samples lie in central density gaps rather than mimicking the real-data distribution.The motivation is that central regions in the high-dimensional representation can become hubs that occur among nearest neighbors of samples from other classes.Source: §3.3.1 · pp. 3–4, Figure 3 · p. 4

3.3.2 Discriminative Losses.

  • The classifier losses promote distinct class clusters, real-versus-fake discrimination, definite labels for unlabeled nodes, and separation between clusters.The supervised loss supports class separation, the unsupervised loss penalizes real-or-fake misclassification, entropy regularization encourages definite unlabeled predictions, and the pull-away term widens density gaps.Source: §3.3.2 · p. 4

3.3.3 Generative Losses.

  • The generator uses feature matching to place samples near the real-batch center and a pull-away term to encourage diverse coverage of central areas.The training batch center replaces the center of all real samples; the authors report that L1 distance also works well, with slightly better performance in practice.Source: §3.3.3 · pp. 4–5

3.3.4 Training.

  • GraphSGAN alternates classifier and generator updates, training the generator to convergence after each classifier update.The classifier uses labeled, unlabeled, and generated batches; the generator’s losses compare real and generated batch centers and measure generated-sample diversity.Source: §3.3.4 · p. 5

4 THEORETICAL BASIS

The theoretical analysis frames generated fake nodes as a way to reduce the influence of marginal nodes in graph Laplacian regularization. Under stated connectivity and generation conditions, it establishes perfect classification when enough fake samples are added.

4 THEORETICAL BASIS

  • The analysis uses graph Laplacian regularization to study how generated nodes linked to marginal nodes alter marginal-node influence and the regularization weights.The framework’s normalization is identified as central to reducing marginal-node influence; generated fake labels are excluded from unlabeled-node assignments and loss is computed only on real-node edges.Source: §4 · p. 5

4.1 Proof

  • Adding generated nodes decreases the ground-truth labeling loss, and the proof concludes that all classes are correctly classified under the theorem’s conditions.The analysis notes that decreasing loss makes the ground truth more likely to be acquired, while recognizing that other classification solutions may also have decreasing loss before proving the sufficient-sample result.Source: §4.1 · p. 6
  • Under the convergence and connectivity assumptions, enough generated samples make every node correctly classified once each marginal node’s degree exceeds d0.The assumptions require generated nodes to link to nearby marginal nodes and each class’s interior-node subgraph to be connected, with each marginal node connected to an interior node of its class.Source: §4 · p. 5, §4.1 · p. 6

5 EXPERIMENTS

Experiments evaluate GraphSGAN on citation networks and entity extraction, verify its proposed equilibrium and working principles, and examine memory use and adversarial improvement of Label Propagation. GraphSGAN significantly outperforms comparison methods on both evaluated tasks, while its scalability and the benefits of adversarial Label Propagation are also examined.

5 EXPERIMENTS

  • The experiments cover two citation networks and one entity-extraction dataset, using default training settings to avoid over-tuning architectures and hyperparameters.Citation-network comparisons use 20 labeled instances per class, 1,000 test instances, and averages over ten random splits.Source: §5 · p. 6, §5.1 · p. 6

5.1 Results on Citation Networks

  • On Cora and Citeseer, GraphSGAN significantly outperforms regularization- and embedding-based methods, beats Chebyshev and GCN, and is slightly better than GAT.Compared with convolution-based methods, its performance is more sensitive to labeled data and has larger variance, possibly due to GAN training instability and mode collapse.Source: Table 2 · p. 7, §5.1 · p. 7

5.2.1 Verification of equilibrium.

  • By 20 epochs, adversarial training places fake samples in central areas surrounded by real-sample clusters, the expected equilibrium.The classifier learns a nonlinear transformation separating real and fake samples; mini-batch training, losspt in LG, and Gaussian noise prevent generator overfitting on the center point.Source: §5.2.1 · p. 7

5.2.2 Verification of working principles.

  • Marginal nodes’ predicted fake probability and gradient norm change synchronously, while interior nodes are never predicted fake and remain smooth after receiving a definite label.The reported Pearson correlation coefficient exceeds 0.6, indicating positive correlation.Source: §5.2.2 · p. 7

5.4 Space Efficiency

  • For small datasets GraphSGAN consumes the most space, but for large datasets it uses the least GPU memory; its mini-batch memory use is independent of node count.GCN requires full-batch training and cannot handle graphs with millions of nodes; Planetoid and GraphSGAN use mini-batches.Source: §5.4 · p. 8

5.5 Adversarial Label Propagation

  • Adversarial Label Propagation improves as marginal-node degree increases, but still underperforms GraphSGAN; τ = 0.1 is a good threshold for separating marginal and interior nodes.Reconstructing the graph from a supervised MLP’s first-layer output further improves performance.Source: §5.5 · p. 8

5.3 Results on Entity Extraction

  • GraphSGAN achieves the best DIEL entity-extraction recall@k, significantly outperforming all comparison methods (p−value≪0.01, t−test).The DIEL dataset has millions of nodes and edges, making full-batch GCN infeasible with sparse storage requiring more than 200GB.Source: §5.3 · p. 7, Table 3 · p. 9

6 RELATED WORK

The related work spans graph semi-supervised learning, image-focused semi-supervised GANs, and other GAN applications on graphs. GraphSGAN is distinguished by bringing GANs to graph classification with a game designed around graph density and clustering.

6.1 Semi-supervised Learning on Graphs

  • Graph Laplacian methods propagate labels or use smoothing, but their focus on local smoothness can neglect graph clustering and make density-gap cases difficult.Label Propagation propagates labels to adjacent nodes until convergence; later work adds smoothing regularizations and bootstrapping.Source: §6.1 · p. 9
  • Graph embedding methods include unsupervised DeepWalk [23] paired with an SVM, label-informed Planetoid [38], and graph convolution models such as GCN [17].More complex graph convolution methods [9] [34] are described as performing better, while GraphSGAN incorporates embedding into its approach.Source: §6.1 · p. 9

6.2 GANs for Semi-supervised Learning

  • GraphSGAN introduces a GAN-like game with working principles for graph semi-supervised learning, where earlier semi-supervised GAN work focused on image data and left its principles unexplored.The cited work also analyzes generator–classification trade-offs, estimates manifold tangent spaces, and combines auxiliary architectures for image classification.Source: §6.2 · p. 9

6.3 GAN-based Applications on Graphs

  • GAN applications on graphs include graph generation, link formation, link prediction, and adversarial regularization of graph representations.The cited approaches preserve graph topology or link distributions, learn classification-oriented embeddings, or transform embeddings to preserve structure and mimic a prior distribution [19] [36] [7].Source: §6.3 · pp. 9–10

7 CONCLUSION AND FUTURE WORK

GraphSGAN uses a generator–classifier game to place generated samples in graph density gaps, and its principles also extend to graph Laplacian regularization. The authors identify training stability, speed, theoretical development, and additional graph tasks as directions for future work.

7 CONCLUSION AND FUTURE WORK

  • GraphSGAN places generated samples in density gaps at equilibrium through a competitive generator–classifier game, with experiments on three benchmark datasets demonstrating effectiveness.Several loss terms together guarantee the expected equilibrium.Source: §7 · p. 10
  • Generated samples reduce the influence of nearby nodes in density gaps, clarifying decision boundaries; the principle can improve graph Laplacian regularization with theoretical guarantees and experimental validation.The authors also report scalability and good performance on the large DIEL dataset.Source: §7 · p. 10
  • Future work includes finding a more ideal equilibrium, stabilizing and accelerating training, strengthening the theoretical basis, and extending the method to other graph tasks.Source: §7 · p. 10

Related papers

Loading 1809.00130v1…