1 of 41

Graph Foundational Model

2 of 41

Graph Transformer

3 of 41

Do Transformers Really Perform Bad for Graph Representation? Chengxuan Ying et al. NeurIPS 2021

Graphormer

4 of 41

Translating text transformer idea in graph

1

2

4

3

5

1

2

4

3

5

5 of 41

Translating text transformer idea in graph

Multi-Head Attention

No Change

Residual Connection

No Change

Adding non-Linearity

No Change

Layer Normalization

No Change

Scaled Dot Product

No Change

6 of 41

Translating text transformer idea in graph

Positional Embedding

Change

Position of a word in text is indicated by the ordinal value

Position of a node in graph is indicated by the connections

Centrality of node 🡪 Centrality Encoding

“Spatial” position of node 🡪 Structure Encoding

Encoding Structural Information

Features of Edges 🡪 Edge Encoding

7 of 41

Graphormer: Architecture

8 of 41

Graphormer : Spatial Encoding

An advantage of Transformer is its global receptive field.

In each Transformer layer, each token can attend to the information at any position and then process its representation.

Issue: model has to explicitly specify different positions or encode the positional dependency (such as locality).
For sequential data (Text)

Absolute Positional Encoding: give each position an embedding
Relative Positional Encoding: encode the relative distance of any two positions

9 of 41

Graphormer : Centrality Encoding

Centrality: How important a node is in the graph.
Graphormer uses Degree Centrality.
Develop a Centrality Encoding which assigns each node two learnable embedding vectors according to its indegree and outdegree.

10 of 41

Graphormer : Centrality Encoding

1

2

4

3

5

6

8

7


0
1
2
3
4
5

9

Trainable

11 of 41

Graphormer : Spatial Encoding

12 of 41

1

2

4

3

5

6

8

7

9


0
1
2
3

More attention to nearby nodes - less attention to distant nodes

13 of 41

Graphormer : Edge Encoding

In many graph tasks, edges also have structural features.

In a molecular graph, atom pairs may have features describing the type of bond between them.

How to better incorporate edge feature information?

Learn edge embedding along with Shortest Path of each node pair.

14 of 41

Graphormer : Edge Encoding

SP_i,j( e₁, e₂, …, e_N): edges in shortest path between node pairs.
Compute an average of the dot-products of the edge feature and a learnable embedding along the path.

15 of 41

Graphormer : Edge Encoding

1

2

4

3

5

6

8

7

16 of 41

Graphormer : Transformer Encoder

Use classic Transformer encoder implementation

Modification- Apply the layer normalization (LN) before the multi-head self-attention (MHA) and the feedforward blocks (FFN)

17 of 41

Graphormer : Special Virtual Node

Instead of READOUT/Pooling, add a special node called [VNode].
make connection between [VNode] and each node individually.
Entire graph representation h_G would be the node feature of [VNode] (Similar to [CLS] token)

[VNode]

This will get mixed up with nodes that are one-hop SPD apart

Solution:

18 of 41

Graphormer : Results

19 of 41

GRAPH-BERT: Only Attention is Needed for Learning Graph Representations, Zhang et al. arxiv, 2020

GRAPH-BERT

20 of 41

General View of Graph Pre-Training

Pre-Training Task

Pre-Training Loss

Entire Graph

Subgraph

sampling

Subgraph Minibatch

Linkless graph

Start Embedding

Final Embedding

Back propagation & Parameter update

21 of 41

GRAPH-BERT Architecture

22 of 41

Linkless Sub-Graph Batching

Top-k intimacy sampling

23 of 41

Graph Isomorphism

Source: Wikipedia

24 of 41