CS224W: Machine Learning with Graphs - 01 Introduction

Introduction

1. Course Outline

1). Traditional methods: Graphlets: Graph kernels
2). Methods for node embeddings: DeepWalk, Node2Vec
3). Graph Neural Networks: GCN, GraphSAGE, GAT, Theory of GNNs
4). Knowledge graphs and reasoning: TransE, BetaE
5). Deep generative models for graphs
6). Applications to Biomedicine, Science, Industry

2. Different Types of Tasks

• Node level
• Edge level
• Community (subgraph) level
• Graph-level prediction, Graph generation

3. Classic Graph ML Tasks

1). Node classification: predict a property of a node

• Example: Categorize online users/items

2). Link prediction: predict whether there are missing links

• Example: Knowledge graph completion

3). Graph classification: categorize different graphs

• Example: Molecule property prediction

4). Clustering: detect if nodes form a community

• Example: Social circle detection

5). Graph generation: drug discovery

6). Physical simulation

3. Components of a Network

• Objects: nodes, vertices $N$
• Interactions: links, edges $E$
• Systems: network, graph $G(N,E)$

4. Directed vs Undirected Graphs

• Undirected
  Links: undirected (symmetrical, reciprocal)
  Examples: Collaborations, Friendship on Facebook
• Directed
  Links: directed (arcs)
  Examples: Phone calls, Following on Twitter

5. Node Degrees

• Undirected
  Node degree $k_i$: the number of edges adjacent to node $i$
  Average degree: $\bar{k}=\frac{2E}{N}$
• Directed
  The total degree of a node is the sum of in-degrees and out-degrees.
  $\bar{k}=\frac{E}{N}$ ${\bar{k}}^{in}={\bar{k}}^{out}$

6. Representing Graphs

• Adjacency Matrix
  $A_{ij}=1$ if there is a link from node $i$ to node $j$
  $A_{ij}=0$ otherwise
  The adjacency matrix of an undirected graph is symmtrical ($A_{ij}=A_{ji}$) but that of a directed graph may not ($A_{ij}\ne A_{ji}$).
  Adjacency Matrices are sparse (filled with zeros).
• Edge List
  $(N_i,N_j)$: an edge from node $i$ to node $j$
• Adjacency List
  Easier to work with if network is large and sparse.
  Allow us to quickly retrieve all neighbors of a give node
  $N_i$: its neighors

7. Node and Edge Attributes

• Weight (e.g., frequency of communication)
• Ranking (best friend, second best friend…)
• Type (friend, relative, co-worker)
• Sign: Friend vs. Foe, Trust vs. Distrust
• Properties depending on the structure of the rest of the graph: Number of common friends

8. More Types of Graphs

• Unweighted graphs: A i j ∈ { 0 , 1 } A_{ij} \in \{0, 1\} Aij​∈{0,1}; Weighted graphs: $A_{ij}\in R$
• Self-edges (self-loops): $A_{ii}\ne 0$

9. Connectivity of Undirected Graphs

Connected graph: Any two vertices can be joined by a path
A disconnected graph is made up by two or more connected components

10. Connectivity of Directed Graphs

Strongly connected directed graph has a path from each node to every other node.
Weakly connected directed graph is connected if we disregard the edge directions.