2025-02-05 graphs lecture 5

Data

subject:: Data Science Methods for Large Scale Graphs

2025-02-05

Table of Contents

Summary

Housekeeping

Scribing

Last Time

• graph convolutions and design
• Learning weights of graph convolution
• Empirical risk minimization problem, statistical risk minimization problem

• 3 problems

  • graph-level problem
  • node-level task / inductive learning

Today

• Graph Neural Networks
  • graph perceptron
  • multi-layer graph perceptron
  • PyTorch (HW) FC NN

1. Graph Signals and Graph Signal Processing

Graph filters work ok for many things, but are limited to linear representations. Therefore, they lack expressivity if the task is complicated. ie, since these operations are only linear, we not able to represent more complex relationships.

Thus, we need to add nonlinearities (ex. ReLU etc) to help with the expressivity of our model. These techniques have been implemented in CNNs for image processing and other domains. GNNs will extend the ideas seen in CNNs to the graph domain - graph convolution .

Simple CNN

We can also think of any image as a graph, where the graph signals are the RGB values at each pixel, and the graph structure is determined by the pixel layout/grid of the image.

Graph Perceptron

Let $\sigma :\mathbb{R}\to \mathbb{R}$. The graph perceptron is defined as

&\to_{u} y \cdot \sigma(u) \;\;\text{pointwise nonlinearity} \to_{y}

\end{aligned}$$

ie a graph convolution followed by a pointwise nonlinear function $y_i=\sigma (u_i)$

Examples

• $\sigma (x)=\max (0,x)$ ReLU
• $\sigma (x)=\frac{1}{1+e^{-x}}$ Sigmoid
• $\sigma (x)=\tanh (x)=\frac{e^x-e^{-x}}{e^x+e^{-x}}$ hypertangent

(see graph perceptron)

Question

Is a graph perceptron local?

convolutional graph filters are local

Yes, we can still write the perceptron in terms of the local nodes, since

Multi-Layer Graph Perceptron

A(n $\ell$-layer) multi-layer graph perceptron (MGLP) is simply several graph perceptrons in sequence. This forms a function with input $x_0=x$, and output $y=x_L$.

Where at each layer, $x_{\ell }=\sigma (u_{\ell })=\sigma \left({\sum }_{k=0}^{K-1}{h}_{\ell ,k}{S}^k{x}_{\ell -1}\right),1\le \ell \le L$ We call $x_{\ell }$ the $\ell$-layer embedding.

For conciseness, we define our weights $H=\{h_{k,\ell }|0\le k\le K-1,1\le \ell \le L\}$ and represent our MLGP as $y=\Phi (x,S;H)$

Illustration

(see multi-layer graph perceptron)

Full-Fledged GNNs

Real-world graph data is often high dimensional.

• in addition to having signal values at the nodes, we often have many features. That is, our signal $x\in {\mathbb{R}}^{n\times d}$ where $n$ is the number of nodes and $d$ is the number of features
• (previously we have been looking at the case where $d=1$)
• Thus it will be necessary for the embeddings $x_{\ell }$ to be multi-dimensional. Note that we also may want embeddings to be multi-dimensional for higher expressivity/flexibility/better representations, not solely because it is necessary.

Example

Suppose $a,b,c$ are drones communicating via wifi and $x$ is their spatial coordinate in 3D: $x\in {\mathbb{R}}^{3\times 3}$.

In order to do this, we need graph convolution that take in multi-dimensional data.

Convolutional Filter Bank

Let $X\in {\mathbb{R}}^{n\times d}$, $H_k\in {\mathbb{R}}^{d\times d^{\prime }}$ for $k=0,\dots ,K-1$. Then a convolutional filter bank (or multiple input multiple output graph convolution) is a multi-dimensional graph convolutiongiven by $Y={\sum }_{k=0}^{K-1}{S}^{k}X{H}_k$

• $S^k\in {\mathbb{R}}^{n\times n}$ is still a graph diffusion/shift
• $H_k$ is a linear transformation mapping $d$ features to $d^{\prime }$ features

(see convolutional filter bank)

GNN

A “full-fledged” GNN layer is given by $X_{\ell }=\sigma (u_{\ell })=\sigma \left({\sum }_{k=0}^{K-1}{S}^k{X}_{\ell -1}{H}_{\ell ,k}\right)$ $H_{\ell ,k}\in {\mathbb{R}}^{d_{\ell -1}\times d_{\ell }}$ for $1\le \ell \le L$, where

• $X_0=X\in {\mathbb{R}}^{n\times d_0}$
• $Y=X_L\in {\mathbb{R}}^{n\times d_{\ell }}$

Here, $X_{\ell }$ is still called an $\ell$-layer embedding.

(see Graph Neural Networks)