## Preliminaries

### Graph

#### What is Graph?

•

A data structure consisting of two components: nodes(vertices) and edges

•

G = (V,E)

◦

V: the set of nodes, E: the edges between them

#### Why Graph?

•

A graph can represent things like social media networks, or molecules(nodes → users // edges → connections)

#### How to represent Graph?

•

A graph is often represented by A, an adjacency matrix

◦

A graph that has n nodes ⇒ A has a dimension of (n x n)

◦

When the nodes have a set of features (e.g., a user profile), in this case, f number of features ⇒ The node feature matrix X has a dimension of (n x f)

### Graph Neural Network (GNN)

#### What is GNN?

•

Graph Neural Networks

•

A class of deep learning methods designed to perform inference on data described by graphs

#### Why GNN? (Why CNNs fail on graphs?)

•

To handle complex graph data with conventional machine learning and deep learning tools

•

Conventional ML and DL tools are specialized in simple data types

◦

E.g., images with the same structure and size ⇒ We can think of as fixed-size grid graphs

◦

E.g., text and speech ⇒ We can think of them as line graphs(reference)

#### With GNN we can do

•

Node classification

•

Graph classification

•

Graph visualization

•

Link prediction

•

Graph clustering

## Graph Convolutional Networks (GCN)

#### What is GCN?

•

First introduced in “Spectral Networks and Deep Locally Connected Networks on Graphs” (Bruna et al, 2014)

•

A method for applying neural networks to graph-structured data

•

The core concept behind CNNs:

◦

Hidden convolution and pooling layers to identify spatially localized features via a set of receptive fields in kernel form

•

This leads to a problem that:

◦

Convolution takes a little sub-patch of the image (a little rectangular part of the image), applies a function to it, and produces a new part (a new pixel)

#### Why GCN?

•

It is difficult to perform CNN on graphs because of

◦

The arbitrary size of the graph and the complex topology (which means there is no spatial locality)

◦

There is unfixed node ordering (Graphs are invariant to node ordering, so we want to get the same result regardless of how we order the nodes)

•

⇒ A method for applying neural networks to graph-structured data is required

#### How to represent a graph in GCN?

•

G = (A, X)

◦

⇒ An adjacency matrix which represents the links between each node

◦

⇒ Node Node feature matrix (N: # of node in a graph, d: # of node features → dimension of node feature vector)

#### Structure of GCN

•

Graph convolution layer & fully connected layer

•

GCN consists of

◦

Graph Convolution

◦

Linear layer

◦

Nonlinear activation

## GraphSAGE

#### What is GraphSAGE?

•

First introduced in Hamilton et al., NIPS 2017

•

A representation learning technique for dynamic graphs

•

A framework for inductive representation learning on large graphs

#### Why GraphSAGE?

•

Low-dimensional vector embeddings of nodes in large graphs have numerous applications in ML (e.g., node classification, clustering, link prediction, etc.)

•

However, most embedding frameworks are 1) inherently transductive, and 2) can only generate embeddings for a single fixed graph

•

These transductive approaches 1) do not efficiently generalize to unseen nodes (e.g., in evolving graphs), and 2) cannot learn to generalize across different graphs

•

⇒ GraphSAGE is an inductive framework that leverages node attribute information to efficiently generate representations on previously unseen data

•

⇒ GraphSAGE can predict the embedding of a new node, without a re-training procedure(reference)

#### What’s different in GraphSAGE?

•

GraphSAGE is useful for graphs that have rich node attribute information (Why?)

## Graph Attention Network (GAT)

#### What is GAT?

•

First introduced in (Velickovic et al., ICLR 2018)