GNN

This page is heavily conditioned on the course “ESE 5140 Graph Neural Networks” by Prof. Alejandro Ribeiro at UPenn.

Graph

Def: a triplet

• Vertices: set of
• Edges: ordered pairs of label
• Weights:

Properties:

• Symmetric/Undirected:
• Unweighted:

Graph Shift Operator#

Def: a stand-in for any matrix representation of graph

Key property: Symmetric:

Notions:

• Neighborhood: set of nodes that influence
• Degree: sum of weights of its incident edges:
• Degree Matrix: diagonal matrix

Types:

• Adjacency Matrices: sparse matrix with nonzero entries $$ A_{ij}=w_{ij}\ \ \forall(i,j)\in\mathcal{E} $$
  • If symmetric:
  • If unweighted:
• Normalized Adjacency Matrix: weights relative to nodes’ degrees $$ \bar{A}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}} $$
  • entries:
• Laplacian Matrix: weights relative to nodes’ degrees $$ L=D-A $$
  • Non-diagonal entries:
  • Diagonal entries:
• Normalized Laplacian Matrix: $$ \bar{L}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-\bar{A} $$

Graph Signal#

Graph Signal: a vector

• If the graph is intrinsic to the signal, we write
• The graph is an expectation of proximity/similarity between signal components

Graph Signal Diffusion: diffused signal

• Stronger weights contribute more to diffusion output
• Codifies a local operation where components are mixed with components of neighboring nodes

Diffusion Sequence:

• Recursive ver: (best for implementation)
• Power ver: (best for analysis)
• -hop neighborhoods
• used for graph convolution

Graph Convolutional Filter#

Graph Filter: a polynomial for linear processing of graph signals $$ H(S)=\sum_{k=0}^{\infty}h_kS^k $$

• : graph shift operator
• : filter coefficients

Graph Convolution: apply filter $$ \textbf{y}=h_{\star S}\textbf{x}=H(S)\textbf{x}=\sum_{k=0}^{\infty}h_kS^k\textbf{x} $$

• Convolution = shift + scale + sum
• Graph convolution = weighted linear combination of diffusion sequence (i.e., shift register)
• Properties:
  • Globalization: aggregate info from local to global neighborhoods
  • Transferability: the same filter can be executed in multiple graphs

Time Convolution: linear combination of time-shifted inputs

• Time signals are representable as graph signals on a line graph .
  • nodes = data points
  • edges = temporal relationships between adjacent data points
• Time shift can be interpreted as multiplications of adjacency matrix .

Graph Fourier Transform#

Notions:

• Eigenvectors & Eigenvalues:
• Eigenvector matrix:
  • 
• Eigenvalue matrix:
  • Ordered real eigenvalues:
• Eigenvector decomposition:

Graph Fourier Transform: Given on the eigenspace is: $$ \tilde{\textbf{x}}=V^T\textbf{x} $$

Inverse Graph Fourier Transform: Given from the eigenspace is: $$ \tilde{\tilde{\textbf{x}}}=V\tilde{\textbf{x}}=VV^T\textbf{x}=I\textbf{x}=\textbf{x} $$

Graph Frequency Represention of Graph Filters: consider graph filter are related by $$ \tilde{\textbf{y}}=\sum_{k=0}^{\infty}h_k\Lambda^k\tilde{\textbf{x}} $$

• Graph convolutions are pointwise in GFT domain:
• Frequency Response of a Graph Filter: $$ \tilde{h}(\lambda)=\sum_{k=0}^{\infty}h_k\lambda^k $$
  • = the same polynomial that defines the graph filter, but on scalar variable
  • Independent of the graph
    • Role of the graph: to determine the eigenvalues on which the response is instantiated
    • Eigenvectors determine the meaning of the frequencies

Graph Neural Network

Learning with Graph Signals#