Source-linked AI summary
GraphGAN: Graph Representation Learning with Generative Adversarial Nets
Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, Minyi Guo
TL;DR
Graph representation learning seeks low-dimensional vertex embeddings, but existing methods separate generative connectivity modeling from discriminative edge prediction. GraphGAN combines them in an adversarial minimax game and uses graph softmax for structure-aware, efficient generation. Across five real-world datasets and three applications, it substantially outperforms state-of-the-art baselines.
Problem
Graph representation learning methods are divided between generative models that learn connectivity distributions and discriminative models that predict edge existence.
Method
GraphGAN trains a generator and discriminator in a minimax game, using graph softmax to model connectivity with graph structure awareness and computational efficiency.
Results
GraphGAN substantially outperforms state-of-the-art baselines in link prediction, node classification, and recommendation across five real-world datasets.
Takeaways & Limitations
Adversarially unifying generative and discriminative objectives provides a graph representation learning framework effective across multiple prediction and recommendation applications.
Takeaways & Limitations
Traditional softmax remains computationally inefficient for graph generation because it requires calculations involving all vertices.
Abstract
from arXiv · showhide
The goal of graph representation learning is to embed each vertex in a graph into a low-dimensional vector space. Existing graph representation learning methods can be classified into two categories: generative models that learn the underlying connectivity distribution in the graph, and discriminative models that predict the probability of edge existence between a pair of vertices. In this paper, we propose GraphGAN, an innovative graph representation learning framework unifying above two classes of methods, in which the generative model and discriminative model play a game-theoretical minimax game. Specifically, for a given vertex, the generative model tries to fit its underlying true connectivity distribution over all other vertices and produces "fake" samples to fool the discriminative model, while the discriminative model tries to detect whether the sampled vertex is from ground truth or generated by the generative model. With the competition between these two models, both of them can alternately and iteratively boost their performance. Moreover, when considering the implementation of generative model, we propose a novel graph softmax to overcome the limitations of traditional softmax function, which can be proven satisfying desirable properties of normalization, graph structure awareness, and computational efficiency. Through extensive experiments on real-world datasets, we demonstrate that GraphGAN achieves substantial gains in a variety of applications, including link prediction, node classification, and recommendation, over state-of-the-art baselines.
Introduction
Graph representation learning embeds graph vertices into low-dimensional vectors, while existing methods primarily use generative or discriminative formulations. GraphGAN unifies these formulations through adversarial training, introduces graph softmax for efficient structure-aware generation, and improves performance across three applications.
- Motivation: Graph representation learning embeds each graph vertex as a low-dimensional vector for network analysis and prediction over vertices and edges.Applications include link prediction, node classification, recommendation, visualization, knowledge graph representation, clustering, text embedding, and social network analysis.
- Existing Approaches: Generative methods model an underlying true connectivity distribution for each vertex, whereas discriminative methods directly predict edge existence between vertex pairs.These two categories differ in whether connectivity is treated as generated from a conditional distribution or classified directly.
- GraphGAN Framework: GraphGAN unifies generative and discriminative graph representation learning through a minimax game between a generator and a discriminator.The generator fits true connectivity and produces samples, while the discriminator distinguishes ground-truth pairs from generated ones.
- Graph Softmax: Traditional softmax is unsuitable because it ignores graph proximity and requires computation over all vertices; graph softmax addresses both limitations.The proposed graph softmax is designed to provide normalization, graph-structure awareness, and computational efficiency.
- Results: GraphGAN achieves gains over state-of-the-art baselines in link prediction, node classification, and recommendation on five real-world datasets.Reported improvements range from 0.59% to 11.13% in link prediction Accuracy, 0.95% to 21.71% in node classification Accuracy, and at least 38.56% Precision@20 and 52.33% Recall@20 in recommendation.
Graph Generative Adversarial Nets
GraphGAN unifies generative and discriminative graph representation learning through an adversarial minimax game. Its graph softmax generator uses graph structure while reducing computation, and alternates with the discriminator during training.
- GraphGAN framework: GraphGAN defines a generator that approximates each vertex’s true connectivity distribution and a discriminator that predicts whether a vertex pair has an edge.The generator produces likely neighbors, while the discriminator distinguishes ground-truth neighbors from generated samples.
- GraphGAN framework: Generator and discriminator play a two-player minimax game, with the generator fitting true neighbors and the discriminator detecting generated samples.Training alternates discriminator updates on positive and generated negative samples with generator updates guided by the discriminator.
- Discriminator: The discriminator maximizes correct-label likelihood for true and generated samples, using vertex representation vectors and updating only the vectors in each sampled pair.GraphGAN implements D as a sigmoid of the input vertices’ inner product, although other discriminators can also serve.
- Generator optimization: The generator uses policy gradients because sampled vertices are discrete, shifting its connectivity distribution toward samples receiving higher discriminator scores.The gradient weights log-probability gradients by the discriminator-related reward, causing generated negative samples to influence generator updates.
- Graph softmax for the generator: Traditional softmax is inefficient and graph-structure-blind because it considers every vertex equally and requires updates involving all vertices.These limitations are especially problematic for large graphs with millions of vertices.
- Graph softmax for the generator: Graph softmax defines connectivity through relevance probabilities along a BFS-tree path, producing a normalized, graph-structure-aware, computationally efficient generator.The online strategy terminates in O(log V) steps and has O(d log V) complexity, versus O(V ·d log V) for the offline method.
- Graph softmax for the generator: Graph softmax connectivity probability decreases exponentially as the shortest-path distance between two vertices increases.This follows because the probability is a product of relevance probabilities along the BFS-tree path, whose length equals the shortest distance.
Experiments
GraphGAN is evaluated across five real-world datasets and three tasks, with experiments covering link prediction, node classification, and recommendation. Results show strong performance, while additional analyses examine connectivity-distance patterns and training stability.
- Experimental setup: Experiments use five datasets spanning scientific collaboration, social, word co-occurrence, and user–movie graphs.The datasets include arXiv-AstroPh, arXiv-GrQc, BlogCatalog, Wikipedia, and MovieLens-1M.
- Experimental setup: GraphGAN is compared with DeepWalk, LINE, node2vec, and struc2vec across the evaluated graph representation learning tasks.The baselines use random walks, proximity preservation, biased walks, or structural-identity modeling.
- Empirical study: The probability of edge existence drops sharply with shortest distance, with log-probability curves showing R2 values of 0.831 and 0.710.This empirical pattern is approximately exponential and supports graph softmax’s proximity-aware design.
- Link prediction: Link prediction hides 10% of graph edges, learns vertex representations, and uses logistic regression to predict hidden edge existence.The evaluation reports Accuracy and Macro-F1 on arXiv-AstroPh and arXiv-GrQc.
- Training stability: GraphGAN reaches an equilibrium in which the generator performs strongly after convergence, while discriminator performance initially rises before falling below 0.8.The discriminator remains above random-guess behavior because generated samples still include many true negatives.
- Node classification and recommendation: GraphGAN outperforms all baselines in node classification and remains consistently above them in recommendation on the reported metrics.Node classification uses logistic regression with a 9:1 train-test ratio, while recommendation evaluates Precision@K and Recall@K.
Conclusions
GraphGAN unifies generative and discriminative graph representation learning through adversarial minimax training and introduces graph softmax for the generator. Across five datasets and three scenarios, it significantly outperforms strong baselines, which the paper attributes to adversarial training and proximity-aware graph softmax.
- Conclusion: GraphGAN unifies generative and discriminative graph representation learning through adversarial training in a minimax game.The generator and discriminator benefit from each other during training.
- Conclusion: Graph softmax addresses traditional softmax limitations by incorporating graph proximity while improving computational efficiency.It is proposed as the generator implementation under the GraphGAN framework.
- Conclusion: Across five real-world datasets and three scenarios, GraphGAN significantly outperforms strong baselines in all experiments.The paper attributes these gains to its adversarial framework and proximity-aware graph softmax.