Graph Convolution Networks

Graph Convolution Networks

Jin Young Choi

Seoul National University

Graphs from social networks

 people and their interactions

 directed (Twitter) and undirected (Facebook)

 typical ML tasks

 Link(edge) prediction

 advertising (recommendation)

 product placement

node edge

Social Graphs

Graphs from utility and technology networks

 power grids, roads, internet, sensor networks

 structure is either hand designed or not

 typical ML tasks

 best routing under unknown or variable costs

 identify nodes of interest

Transportation Graphs

Graphs from information networks

 web

 blogs

 wikipedia

 typical ML tasks

 find influential sources

 search (page rank)

Web Graphs

Graphs from biological networks

 protein-protein interactions

 gene regulatory networks

 typical ML tasks

 discover unexplored interactions

 learn or reconstruct the structure (graph auto- encoder)

 recognize a similar structure for personalized cancer

treatment (graph classification)

Gene Graphs

Cell Graphs

Graphs from similarity networks

Graphs from similarity networks

Graphs from similarity networks

Graphs from similarity networks

 vision

 audio

 text

 typical ML tasks

 semi-supervised learning

 spectral clustering

(unsupervised learning, graph auto-encoder)

 manifold learning (hyperbolic representation learning)

What will you learn in the Graphs in ML course?

 Concepts and methods to work with graphs in ML.

 Theoretical tools to analyze graph-based algorithms.

 Specific applications of graphs in ML.

 How to tackle: large graphs, online setting, graph construction …

 One example: Online Semi-Supervised Face Recognition

Online Semi-Supervised Face Recognition

Online Semi-Supervised Face Recognition

Online Semi-Supervised Face Recognition

Unsupervised Graph Clustering of Data

Non-Euclidean distance:

Geodesic distance

in tangent space of manifold

→Geometric deep learning

Data as Graphs

Jian Xu. Representing Big Data as Networks.

PhD Dissertation, University of Notre Dame

Deep Learning Meets Graphs: Challenges

 Traditional DL is designed for simple grids or sequences

 CNNs for fixed-size images/grids

 RNNs for text/sequences

 But nodes on graphs have different connections

 Arbitrary neighbor size

Graph Neural Networks

Graph-level

Node-level

Graph Convolutions Graph Convolutions Activation Function

Representations

Machine Learning with Graphs

 Node classification (semi-supervised Learning)

 Predict a type of a given node

 Link prediction

 Predict whether two nodes are linked

 Community detection (node clustering, unsupervised learning)

 Identify densely linked clusters of nodes

 Network similarity

 How similar are two (sub)networks

 Ranking

1 4

2 3

7 node edge

Course Objective

To be sure to grasp new concepts related with GCN

To become familiar with the new terms related with GCN

To learn the underlying theory for GCN (graph spectral theory) To derive formulas related with GCN

To introduce recent GCN structures

To be experienced with the coding for GCN and applications

References:

 Graphs in Machine Learning, Michal Valko, DeepMind Paris and Inria Lille

 Graph Spectral Theory

 Graph Cut

 Graph Node Clustering

 Graph Laplacian

 Laplacian Smoothing

 Semi-supervised Learning (SSL) with Graph

 Online SSL and SSL for large graph

References:

 Graph Neural Networks: Models and Applications(AAAI 2020 Tutorial), Yao Ma, Wei Jin, and Jiliang Tang, Michigan State University; Lingfei Wu and Tengfei Ma, IBM Research

 Graph Convolution Networks (GCN)

 Graph Filtering in GCN

 Graph Pooling in GCN

 Spectral Filtering in GCN

 Spatial Filtering in GCN

 Recent GCN papers

References:

 Geometric Deep Learning on graph and manifolds, Michael Bronstein, SIAM 2018, Imperial College London

 Basics of deep learning

 Basics of graph theory and differential geometry

 Spectral analysis on graphs and manifolds (in Hilbert Space)

 Spectral-domain geometric deep learning methods

 Spatial-domain geometric deep learning methods

 Applications: network analysis, recommender systems, computer graphics and vision, chemistry, high-energy physics, drug design, etc



Course Plan

(1 주)

• Definition of Graph

• Node, Edge

• Affinity Matrix (2 주)

• Spectral Clustering

• Graph Laplacian (3 주)

• Graph Random Walk

• Diffusion

• Applications of Graph (4 주)

• Node classification

• Link prediction

• Community detection

(5 주)

• Network similarity

• Feature Learning in Graphs

• Node embedding (6주)

• Adjacency-based Similarity

• Multi-hop Similarity

• Random-walk Embedding

• Graph Neural Networks (GNN)

(7 주)

• Embedding Nodes

• Deep Encoder (8 주)

• 중간고사 (50%)

• Review

(9주)

• Similarity function

• Neighborhood Aggregation (10 주)

• Neighborhood Convolutions

• Training for Embedding

• Graph Convolutional Networks (GCN)

(11 주)

• Basic GCN configuration

• MPNN (Message Passing Neural Networks)

(12 주)

• GraphSage (Aggregate then Update)

• SGC (Simplifying GCN)

(13 주)

• GAT (Graph Attention Networks)

• GIN (Graph Isomorphism Networks)

(14 주)

• JK (Jumping Knowledge)

• APPNP (Approximated Personalized Propagation of Neural Predictions)

• PAG (Position Aware Graph Neural Networks)

• Applications of Graph Convolutional Networks (GCN)

(15주)

• Select one paper and Reproducing (Term Project 50%)

• Presentation