PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Graph Infomax

Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, R Devon Hjelm

arXiv:1809.10341v2stat.MLcs.ITcs.LGcs.SI

TL;DR

Many graph datasets are unlabeled, limiting supervised learning where unsupervised graph representation learning is needed. DGI maximizes mutual information between graph patch representations and high-level summaries, achieving competitive performance across transductive and inductive classification tasks and sometimes outperforming supervised architectures.

  • Problem

    Most successful graph-learning methods use supervision, although graph data is often unlabeled and unsupervised learning is needed for important tasks.

  • Method

    DGI learns node embeddings by maximizing mutual information between graph patch representations and high-level graph summaries produced by graph convolutional encoders.

  • Results

    DGI achieves competitive performance across five transductive and inductive classification datasets, sometimes exceeding supervised architectures.

  • Takeaways & Limitations

    DGI produces node embeddings that capture global graph structural properties while supporting downstream classification across transductive and inductive settings.

  • Takeaways & Limitations

    Deeper encoders can mix patch representations and reduce example-pool variability, so shallower or wider architectures performed better on some datasets.

Abstract

from arXiv · show

We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised manner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. We demonstrate competitive performance on a variety of node classification benchmarks, which at times even exceeds the performance of supervised learning.

1 INTRODUCTION

The introduction motivates unsupervised graph representation learning because graph data is often unlabeled and existing random-walk objectives have important limitations. It presents Deep Graph Infomax as a mutual-information-based alternative adapted from image-domain methods to graph-structured inputs.

  • Motivation: Most successful graph neural-network methods use supervised learning, which is often infeasible because graph data in the wild is largely unlabeled.
  • Existing approaches: Random-walk-based unsupervised methods encourage nodes close in the input graph to remain close in representation space.
  • Limitations: Random-walk objectives over-emphasize proximity over structural information and make performance highly dependent on hyperparameter choices.
  • Limitations: It is unclear whether random-walk objectives provide useful signals when graph-convolutional encoders already bias neighboring nodes toward similar representations.
  • Deep Graph Infomax: DGI proposes mutual-information maximization instead of random walks and adapts ideas from Deep InfoMax to graph-structured inputs.The approach is motivated by scalable mutual-information estimation through a classifier distinguishing joint-distribution samples from samples drawn from product-of-marginals distributions.

2 RELATED WORK

Related work frames unsupervised graph representation learning through contrastive objectives, sampling strategies, and predictive coding. Prior methods contrasting global and local graph representations use matrix-factorization-style objectives that do not scale to larger graphs.

  • Contrastive methods: Contrastive methods learn representations by increasing scores for positive examples that capture desired dependencies and decreasing scores for negative examples that do not.These methods use an encoder and a scoring function to distinguish real from fake inputs.
  • Sampling strategies: Prior unsupervised graph methods use local contrastive losses, typically treating node pairs co-occurring in short random walks as positive samples.This setup effectively treats nodes as words and random walks as sentences.
  • Predictive coding: Contrastive predictive coding also maximizes mutual information, but uses conditional-density estimation through noise contrastive estimation as its scoring function.Unlike the described approach and graph methods, CPC is predictive.
  • Global and local representations: Prior graph methods contrasting global and local representations rely on adjacency-matrix autoencoding or community-level constraints in node embeddings.Both use matrix-factorization-style losses and are not scalable to larger graphs.

3 DGI METHODOLOGY

DGI learns node-level patch representations with graph convolutional encoders and trains them to retain information about a graph-level summary. It uses discriminator-based contrastive learning between positive patch-summary pairs and negatives formed from alternative or corrupted graphs.

  • Encoder: DGI encodes node features and graph structure into high-level node representations that can support downstream node classification.The encoder maps X and A to H, whose vectors represent individual nodes.
  • Encoder: Graph convolutional encoders aggregate local neighborhoods, so each node embedding summarizes a graph patch centered on that node.The method therefore treats node embeddings as patch representations rather than representations of isolated nodes.
  • Mutual-information objective: DGI maximizes mutual information between local patch representations and a global graph summary produced by a readout function.The summary is computed as s = R(E(X, A)).
  • Contrastive learning: A discriminator scores patch-summary pairs, using observed pairs as positives and pairs with patches from alternative or corrupted graphs as negatives.For a single graph, a stochastic corruption function generates the negative example; its design influences which structural information is captured.
  • Contrastive learning: The objective uses binary cross-entropy noise contrastive estimation to distinguish joint samples from samples drawn from the product of marginals.This objective effectively maximizes mutual information through the Jensen-Shannon divergence.
  • Representation properties: Preserving mutual information with the global summary helps embeddings retain patch-level similarities, including similarities between distant nodes with similar structural roles.The paper connects discriminator classification error to mutual-information maximization for suitable finite input sets and deterministic readout functions.

4 CLASSIFICATION PERFORMANCE

DGI was evaluated as an unsupervised representation-learning method for node classification across transductive and inductive benchmarks, using linear logistic-regression classifiers. It achieved strong, competitive performance across five datasets, surpassing supervised GCN results on Cora and Citeseer while showing benefits over random initialization.

  • Evaluation setup: DGI learned node patch representations fully unsupervised, then evaluated them with a simple linear logistic-regression classifier.The evaluation covered both transductive and inductive node-classification tasks.
  • Evaluation setup: The benchmarks covered topic classification on Cora, Citeseer, and Pubmed, Reddit community prediction, and protein-role classification on unseen PPI networks.The tasks included transductive learning, inductive learning on large graphs, and generalization across multiple graphs.
  • Comparative results: DGI achieved strong performance across all five datasets and was competitive with supervised GCN results, exceeding them on Cora and Citeseer.The authors attribute this advantage to DGI indirectly giving nodes access to structural properties of the entire graph, unlike a two-layer supervised GCN.
  • Comparative results: Random-Init embeddings served as a strong baseline, and the results showed that DGI further improved over this baseline, particularly on inductive datasets.The cited discussion contrasts DGI with prior random walk-based negative-sampling methods on inductive tasks.
  • Architectural effects: Shallower architectures performed better on some datasets, while DGI generally benefited from wider rather than deeper models.The authors relate this to deeper encoders causing more pronounced mixing and reducing positive/negative example variability, while cautioning that the trend may not generalize.

5 QUALITATIVE ANALYSIS

Qualitative analyses on Cora show that DGI embeddings form topic-aligned clusters and reveal a mechanism separating dimensions that suppress negative examples from those encoding positive-example information. These insights explain why competitive performance with a supervised GCN persists after removing half the patch-representation dimensions.

  • 5 QUALITATIVE ANALYSIS: The analyses focus exclusively on Cora, whose smaller node count aids clarity.The study performs a diverse set of analyses to better understand DGI’s learned embeddings.
  • 5 QUALITATIVE ANALYSIS: DGI’s 2D t-SNE projections show discernible clustering that respects Cora’s seven topic classes, especially compared with raw features and Random-Init.The projection achieves a Silhouette score of 0.234, compared with 0.158 previously reported for Embeddin.
  • 5 QUALITATIVE ANALYSIS: DGI uses biased embedding dimensions to push negative-example scores down while the remaining dimensions encode useful information about positive examples.This analysis isolates distinct roles among embedding dimensions.
  • 5 QUALITATIVE ANALYSIS: Competitive performance relative to the supervised GCN is retained after half the encoder’s patch-representation dimensions are removed.The result follows from insights into the distinct roles of embedding dimensions.

6 CONCLUSIONS

Deep Graph Infomax (DGI) learns unsupervised node representations by maximizing local mutual information across graph patches using graph convolutional architectures. Its embeddings capture global graph structure and achieve competitive performance on transductive and inductive classification tasks.

  • 6 CONCLUSIONS: DGI learns unsupervised representations for graph-structured data by maximizing local mutual information across patch representations.The patch representations are obtained using graph convolutional architectures.
  • 6 CONCLUSIONS: DGI produces node embeddings that are mindful of a graph’s global structural properties.
  • 6 CONCLUSIONS: DGI achieves competitive performance across transductive and inductive classification tasks.

A FURTHER DATASET DETAILS

The evaluation covers transductive citation-network benchmarks and inductive settings on a large Reddit graph and multiple protein–protein interaction graphs. These datasets use document, post, or gene-related node features and support prediction of node or community labels.

  • Transductive learning: Transductive evaluation uses the Cora, Citeseer, and Pubmed citation networks, where nodes are documents, edges are undirected citations, and features are bag-of-words representations.Each node has a class label, with only 20 nodes per class used for training.
  • Inductive learning on large graphs: Inductive evaluation on Reddit uses a graph with 231,443 nodes and 11,606,919 edges to predict posts’ subreddit communities.Inputs include GloVe embeddings of post content and comments, score, and number of comments; posts connect when the same user commented on both.
  • Inductive learning on multiple graphs: Inductive evaluation across multiple graphs uses protein–protein interaction graphs from different human tissues, with 20 training, 2 validation, and 2 testing graphs.Testing graphs remain completely unobserved during training, and each node has 50 features composed of positional gene information.

B FURTHER QUALITATIVE ANALYSIS

The qualitative analysis visualizes discriminator scores and embedding examples to examine how DGI distinguishes positive and negative nodes. It finds biased embedding dimensions can be removed while classification and discrimination remain competitive for much of the embedding.

  • Visualizing discriminator scores: Only a handful of “hot” nodes within positive Cora embedding clusters receive high discriminator scores.Scores were visualized for positive nodes and randomly sampled negative examples.
  • Impact and role of embedding dimensions: Top-scoring positive and negative examples show distinct embedding dimensions in which each group is strongly biased.The embeddings of the highest-scored positive and lowest-scored negative examples are visualized in Figure 5.
  • Impact and role of embedding dimensions: Removing biased dimensions first preserves classification performance for over half the embedding dimensions while remaining competitive with the supervised GCN.Dimensions are removed in order from most or least distinguishable, and classification is monitored using logistic-regression test accuracy.
  • Impact and role of embedding dimensions: Positive examples remain mostly correctly discriminated until well over half the embedding dimensions are removed when biased dimensions are removed first.The observed trends largely support the hypothesis that embedding dimensions have distinct roles in discrimination.

C ROBUSTNESS TO CHOICE OF CORRUPTION FUNCTION

DGI is stable across corruption strategies for node classification, including feature shuffling, adjacency perturbation, and their combination. Performance requires sufficient graph perturbation and is strongest when negative and positive graphs have similar connectivity, while broader task settings remain open.

  • Overall robustness: DGI remains stable and robust across different corruption strategies for node classification on Cora.The study considers feature shuffling, adjacency perturbation, and compound corruption.
  • Limitations: Choosing appropriate corruption strategies for tasks beyond node classification remains an open research problem.The reported robustness primarily concerns node classification.
  • Adjacency corruption: Adjacency-only corruption preserves features while adding or removing edges, and higher corruption rates produce competitive embeddings.With ρ = 0, the positive and negative graphs are identical, making discriminator learning impossible and matching randomly initialized DGI performance.
  • Compound corruption: Compound feature shuffling and adjacency perturbation still yields useful features, with sparsity-preserving corruption performing best but large disruptions remaining effective.Figure 8 reports best performance for ρ ≈ 1/N and good performance when edge additions or removals have probabilities approaching 1.
  • Connectivity effects: A lower bound on positive-graph perturbation is required for competitive node embeddings, with strongest downstream features when negative and positive graphs have similar connectivity.The conclusion applies to the classification task on Cora.
  • Connectivity effects: Classification performance peaks at reasonably high but sparse perturbation, while denser negative graphs cause only marginal degradation and still outperform the considered unsupervised baselines.Sparse perturbations preserve diverse negative examples by limiting mixing between separate 1-step patches.
Loading 1809.10341v2…