Unsupervised Learningwith Graph Neural Networks
Petar Veličković
ACDL 2019 Satellite Workshop on Graph Neural Networks
22 July 2019

Motivation●

In this talk: using graph neural networks for unsupervised learning.

●

Very important direction: most graphs in the wild are unlabeled!
○●

However, still largely understudied.

Outline:○○○○Graph neural networks recap (GCN/GAT/MPNN);
Random-walk objectives (VGAE);
Mutual information maximisation (DGI);
Latent graph inference (NRI).

Unsupervised Learning with GNNs
— Petar Veličković

Graph Neural Networks

Graphs are everywhere!

Unsupervised Learning with GNNs
— Petar Veličković

Mathematical setup●Graph:●Node features:●Adjacency matrix:●Neighbourhoods:●(Edge features):
Unsupervised Learning with GNNs
— Petar Veličković

Graph Convolutional Network

Unsupervised Learning with GNNs
— Petar Veličković

Message-passing neural networks●

Want permutation invariance => aggregate (e.g. sum) across●Generic graph neural network (GNN) layer usually expressed as:.

where f is a (learnable) function, computing message from j to i.
●Message-passing neural network (MPNN; Gilmer et al., ICML 2017).
Unsupervised Learning with GNNs
— Petar Veličković

Simpler GNN variants●

Graph convolutional network (GCN; Kipf and Welling, ICLR 2017):●

Graph attention network (GAT; Veličković et al., ICLR 2018):

Unsupervised Learning with GNNs
— Petar Veličković

Random-walk objectives

Unsupervised learning setup●

The GNN parameters can be optimised by a supervision signal.

●But what if we have no labels / task is unknown?

●

Want: “good” node* features that adapt to new tasks well.

*if we have good node features, can easily derive good edge/graph features if required.
Unsupervised Learning with GNNs
— Petar Veličković

Structure preservation●

What is in a “good” representation?

●Graphs carry interesting structure!
○●

Simplest notion of graph structure is an edge.
○●

Good node representations should preserve it.

Features of node i and j should be predictive of existence of edge (i,j)!

Yields a straightforward unsupervised objective...

Unsupervised Learning with GNNs
— Petar Veličković

Link prediction●

Hold out some edges from the graph.

●Use a GNN to obtain node representations,●

Optimise the GNN such that●(Variational) graph auto-encoders (VGAE; Kipf and Welling, NIPS BDL 2016)

and.

are predictive of whether:Unsupervised Learning with GNNs
— Petar Veličković

Random-walk objectives●

The link-prediction objective is a special case of random-walk objectives.

●

Predictive of whether i and j co-occur in a (short) random walk.

●

Dominated unsupervised graph representation learning prior to GNNs!
○●

DeepWalk, node2vec, LINE, ...

Combined with GNNs in GraphSAGE (Hamilton et al., NIPS 2017).

Unsupervised Learning with GNNs
— Petar Veličković

Mutual information maximisation

Combining GNNs and local objectives●

Random-walk objectives inherently capture local similarities.

●

But a GNN summarises local patches of the graph!
○○●

Random walk-objectives can fail to provide useful signal to GNNs!
○●

Neighbouring nodes tend to highly overlap in n-step neighbourhoods;
Therefore, a GNN enforces similar features for neighbouring nodes by design.

At times, matched by a random-init GNN! (Veličković et al., ICLR 2019)

We require a move to global objectives...
Unsupervised Learning with GNNs
— Petar Veličković

Global unsupervised objectives●

Want the model to discover interesting structural similarities anywhere!

●

Hypothesis: similar structural roles => likely to be related○

regardless of path distance!

Unsupervised Learning with GNNs
— Petar Veličković

Mutual information maximisation●

A natural way to capture similarities is optimising mutual information.

●

Attempt to simultaneously optimise○

for all pairs of nodes...

The model will “discover” which pairs can be best compressed.

●Scalable proxy: optimise, where is a graph summary vector.

●Yielded great returns on images (Deep InfoMax; Hjelm et al., ICLR 2019).

Unsupervised Learning with GNNs— Petar Veličković

How to optimise MI?
●In neural networks, MI typically optimised using a discriminator.
○○●Requires negative examples: nodes not belonging to the graph.
○●Binary classiﬁer, determining whether and are related.
e.g. “Does node i belong in the graph summarised by ?”But often only have one graph!

Solution: explicit corruption function to produce negative graphs.

Unsupervised Learning with GNNs
— Petar Veličković

Deep Graph Infomax (DGI)

Veličković et al., ICLR 2019
Unsupervised Learning with GNNs
— Petar Veličković

Scaling to large graphs

Competitive results when combined with GraphSAGE-style subsampling
Unsupervised Learning with GNNs
— Petar Veličković

Latent graph inferenceLatent graph inference●All techniques so far require a graph to be provided as input…

●

But can we always see it?

●Could use a fully-connected graph, but…
○○●

not representative of interaction “modes”;does not scale!

Latent graph inference represents a key
challenge for graph neural networks to tackle.
Unsupervised Learning with GNNs
— Petar Veličković

Problem setup

Neural Relational Inference (NRI; Kipf, Fetaya et al., ICML 2018)
Unsupervised Learning with GNNs
— Petar Veličković

Learning the interaction graph●

Use a downstream task to drive graph construction:
○
○
○

●

First, infer the graph (encoder network);
Then, use the graph to make predictions (decoder network).
Optimise the entire system end-to-end through predictive loss.

In the NRI paper:○○○Inputs are particle trajectories;
Want to predict future positions.
Infer physics interactions.

Unsupervised Learning with GNNs
— Petar Veličković

The NRI encoder●

Assume upfront K different interaction types○●Run an MPNN over the complete graph○●(e.g. spring, charged, none…)

This will yield node as well as edge features,Learn a K-way classiﬁer over each edge to infer interaction type○

Sample from its predictions to obtain the latent graph

Unsupervised Learning with GNNs
— Petar Veličković

The NRI decoder●Run another MPNN over the latent graph●Predict the desired output using the node representations●

Optimise the entire system through gradient descent on the output error○●(e.g. MSE in the case of particle trajectories)

Problem: cannot backpropagate through the sampling operation!
○

Use the Gumbel softmax trick at training time.

Unsupervised Learning with GNNs
— Petar Veličković

The NRI architecture

Unsupervised Learning with GNNs
— Petar Veličković

Concluding remarks●

NRI is an important step towards latent graph inference●

Main limitation: does not scale to large graphs!
○○●Still requires message passing on a complete graph…
In practice, should not be required!

Plentiful improvements possible, as well as necessary

Unsupervised Learning with GNNs
— Petar Veličković

Thank you!
Questions?