Deep Graph Infomax overview and implementation examples

Deep Graph Infomax

Deep Graph Infomax (DGI) is an unsupervised learning method for graph data, which is an information-theoretic targeted approach to learning node representations DGI aims to match local (node-level) and global (graph-level) features of a graph to obtain high-quality node embeddings.

The basic idea of DGI is as follows

• Information maximisation: learning is performed so that node embeddings and whole graph embeddings share information to the maximum extent possible. To achieve this, the objective function is to maximise the Mutual Information (MI) of the node-level and graph-wide representations.
• False positive and false negative samples: a binary classification problem is solved using randomly generated node representations (false negatives) from the graph to distinguish them from the correct node representations (false positives). This approach ensures that node representations are tuned to be meaningful.
• Use of Graph Neural Networks (GNNs): the node representation is generated on the basis of Graph Convolutional Networks (GCNs) or other GNNs.

The steps of the algorithm take the following form

1. Generate node-level representation: compute the embedding of each node using a graph neural network (e.g. GCN).
2. Generate graph-level representation: compute a representation of the entire graph by aggregating the statistics (e.g. mean or sum) of each node embedding.
3. Generate negative example samples: create negative examples from randomly disturbed graph data (pseudo-negative samples).
4. Defining the target function: setting up a binary classification task to learn to distinguish between pseudo-positive and pseudo-negative samples. Specifically, maximising the amount of mutual information between node embedding and graph embedding.

DGI is an advanced algorithm that utilises unsupervised learning and is particularly suited to graph data with missing labels. It can be combined with other methods to further extend the range of applications.

Implementation example

A simple example implementation of Deep Graph Infomax (DGI) is shown below. It uses PyTorch Geometric to learn node embeddings from graph data.

Deep Graph Infomax implementation example

import torch
from torch_geometric.nn import GCNConv, DeepGraphInfomax
from torch_geometric.data import Data

# Sample graph data
edge_index = torch.tensor([[0, 1, 2, 0, 1], [1, 0, 1, 2, 2]], dtype=torch.long)  # related information
x = torch.tensor([[1], [1], [1]], dtype=torch.float)  # Node features (3 nodes, 1 feature)

# Creating graph data objects
data = Data(x=x, edge_index=edge_index)

# Encoder model definition (using GCN)
class Encoder(torch.nn.Module):
    def __init__(self, in_channels, out_channels):
        super().__init__()
        self.conv = GCNConv(in_channels, out_channels)

    def forward(self, x, edge_index):
        return self.conv(x, edge_index)

# hyperparameter
in_channels = data.x.size(1)  # Dimensions of input features (1D)
hidden_channels = 16          # Number of dimensions of embedding

# Encoder instance.
encoder = Encoder(in_channels, hidden_channels)

# Defining Deep Graph Infomax models
dgi = DeepGraphInfomax(
    hidden_channels=hidden_channels,
    encoder=encoder,
    summary=lambda z, *args, **kwargs: torch.sigmoid(z.mean(dim=0)),  # Embedding the whole graph
    corruption=lambda x, edge_index: (x[torch.randperm(x.size(0))], edge_index),  # Generation of pseudo-negative samples.
)

# Optimisation algorithm settings.
optimizer = torch.optim.Adam(dgi.parameters(), lr=0.01)

# learning loop
for epoch in range(100):
    dgi.train()
    optimizer.zero_grad()
    loss = dgi.loss(data.x, data.edge_index)  # Calculation of losses
    loss.backward()  # Gradient calculation
    optimizer.step()  # Parameter update

    if epoch % 10 == 0:
        print(f"Epoch {epoch}, Loss: {loss.item()}")

# Obtaining node embedding after learning.
dgi.eval()
z = dgi.encoder(data.x, data.edge_index)  # Get node representation.
print("Learned Node Embeddings:")
print(z)

Explanation of execution results

1. Sample data.
   • There are three nodes, each with a one-dimensional feature set.
   • The graph structure is specified by edge_index.
2. Model structure
   • Node embedding is calculated using GCNConv.
   • The number of dimensions of the embedding is hidden_channels=16.
3. Generation of false positives and false negatives
   • The embedding is learnt through the task of creating false positives (correct node representations) and false negatives (randomly shuffled features) and classifying them.
4. Optimisation.
   • Learning 100 epochs and minimising losses.
5. Result.
   • The learned node embeddings (16-dimensional vectors) are obtained as z

Application examples

Specific applications are described below.

1. social network analysis

• Application example: user feature extraction and community detection
• Background: analysing relationships and interaction patterns between users in social networks (e.g. Facebook, Twitter).
• Role of DGI: learn latent features of each user (node) based on the graph structure. Perform community detection and user similarity analysis using the learned embeddings.
• Examples:Identifying influencers to enhance marketing activities. Analysis of user behaviour patterns to detect fake accounts and bots.

2. bioinformatics

• Application example: analysis of protein interaction networks.
• Background: protein-protein interaction (PPI) networks are important for understanding biological functions.
• Role of DGI: learn protein embeddings from the graphical structure of PPI networks. Predicting unknown protein-protein interactions using learned embeddings.
• Examples: discovery of new disease-relevant target proteins. Analysis of drug interaction networks.

3. knowledge graphs

• Example applications: link prediction and entity classification.
• Background: knowledge graphs model entities (nodes) and their relationships (edges).
• Role of DGI: Learning entity embeddings from unlabelled knowledge graphs. Used to predict new relations (links) and categorise entities.
• Examples: product relevance prediction in e-commerce. Relationship discovery between documents in digital archives.

4. recommendation systems

• Application example: user-item relationship modelling
• Background: the relationship between users, goods and services is usually represented as a graph.
• Role of DGI: Models user preferences by learning embeddings of user and product nodes. Improve recommendation accuracy using similarity of embeddings.
• Examples: film recommendation on Netflix; cross-selling of products on Amazon.

5. chemistry and drug design

• Example application: learning representations of molecular structures.
• Background: molecules can be represented as graphs consisting of nodes (atoms) and edges (bonds).
• Role of DGI: Learning molecular features from molecular graphs. Used for classification of active substances and prediction of toxicity.
• Examples: screening of new drug candidates. Design of chemicals with low environmental impact.

6. cyber security

• Application example: network anomaly detection.
• Background: analysis of communication networks is important for the detection of cyber-attacks.
• Role of DGI: Modelling interactions between communication nodes to detect anomalous connections and behaviour.
• Examples: early detection of distributed DoS attacks. Detection of unauthorised access.

7. transport networks.

• Application example: urban traffic optimisation.
• Background: modelling traffic networks as graphs to predict and optimise traffic flows.
• Role of DGI: learns the relationships between traffic nodes (stations, intersections) and predicts traffic demand. Identifies bottlenecks in the road network.
• Examples: real-time traffic management in smart cities. Scheduling optimisation of public transport.

Reasons for using DGI include (1) unsupervised learning (effective even for graph data lacking labels), (2) versatility (applicable to various graph structure data) and (3) performance (high-quality node embedding improves performance of downstream tasks (classification, prediction, etc.)).

Considerations for application include the following

• Data size: computational efficiency is important for very large graphs.
• Pre-processing: accurate modelling of features and graph structure is necessary.
• Hyperparameters: adjusting the number of hidden layer dimensions and learning rate affects performance.

reference book

The following sections describe reference books on Deep Graph Infomax (DGI) and related graph neural networks (GNNs) and graph-based representation learning.

1. graph neural networks in general
Book.
– ‘Graph Representation Learning’.
– Author: William L. Hamilton
– Year of publication: 2020
– Abstract: Provides a detailed introduction to the fundamentals of representation learning on graph data, introducing various graph neural network algorithms, including DGI.

– ‘Deep Learning on Graphs’.
– Author(s): Yao Ma, Jiliang Tang
– Year of publication: 2021
– Abstract: Covers the basics and applications of deep learning on graph data. Especially suitable for learning the theoretical background of unsupervised learning and GNNs.

2. unsupervised representation learning
Paper.
– ‘Deep Graph Infomax’.
– Author(s): petar Veličković et al.
– Year of publication: 2018
– Abstract: Original DGI paper. Describes in detail how to generate node embeddings using unsupervised learning. Official implementation code is also included.

– ‘Contrastive Learning of Structured World Models’.
– Author(s): Will Dabney et al.
– Year of publication: 2020
– Abstract: Describes application examples of algorithms based on contrastive learning and helps to gain an in-depth understanding of related methods in DGI.

3. learning of applications
Book.
– ‘Graph Neural Networks: Foundations, Frontiers, and Applications’.
– Author(s): Lingfei Wu, Peng Cui, Junchi Yan
– Year of publication: 2022
– Abstract: Provides a rich introduction to the fundamentals and applications of GNNs (e.g. knowledge graphs, molecular analysis, recommendation systems, etc.); DGI applications are also covered.

Paper.
– ‘Graph Neural Networks in Practice: Applications and Infrastructure’.
– Author(s): Xiaoying Zhang et al.
– Year of publication: 2021
– Abstract: The paper details real-world applications of GNNs (e.g. social networks, bioinformatics, recommendation systems, etc.).

4. implementation and code
Reference repository.
– Deep Graph Library (DGL)
– Abstract: A Python library that enables the implementation of various GNN algorithms, including DGI. Extensive tutorials are provided in the official documentation.

– PyTorch Geometric
– Summary: PyTorch-based library for easy implementation of GNN algorithms, including official implementations of DGI.

5. related to contrast learning
Paper.
– “Deep Representation Learning: Fundamentals, Technologies, Applications, and Open Challenges”

– ‘A Simple Framework for Contrastive Learning of Visual Representations’.
– Author(s): Ting Chen et al.
– Year of publication: 2020
– Abstract: Allows users to learn the basic concepts of contrastive learning and deepen their understanding of DGI.