2025-01-22 graphs lecture 1

Data

subject:: Data Science Methods for Large Scale Graphs

2025-01-22

0. Intro/Class Overview

Signal processing vibes

• This class will be a bit more supervised learning
• GNNs from the very basics
• HWs = labs: pytorch, pygeometric : tutorial on Canvas

No textbook, based on research

Syllabus

3 homeworks 20% each (see syllabus on Canvas)

• project in pytorch
• covers 4 weeks of material Final project 30%
• design a graph dataset (implementation)
• or most recent papers and present (lit review) Participation 10%
• Scribing (google doc)

1. Basics

see Lecture 1.pdf

Today

• Why data science and why large scale graphs?
• What are graphs/graph signals?
• How do graphs and graph signals interact with each other?
  • Graph diffusion processes
• adjacency matrix and laplacian
• Total variation energy on graphs
• Canonical frequencies and oscillation models

Question

What is graph data science?

Examples of Graph Data

• Road networks (graph is the structure of then data: data is “on top” of the graph)
• Network / partially complete network (graph and data are entangled)
• Molecules (graph itself is the datapoint)

Question

Why large scale graphs?

• Graphs can get BIG
  • $10^9+$ nodes

Example

Genome sequencing using graphs.

• lots of tiny pieces of dna sections
• Want to find a path through all of them that makes sense
• edge when there is any overlap

Graph

A graph is a triplet $G=(V,E,W)$ where

• $V=\{1,\dots ,n\},|V|=n$ vertex set
• $E\subseteq V\times V$ edge set
• $W:E\to \mathbb{R}$ weight function

(see graph)

Undirected

A graph $G$ is undirected if for all $(i,j)\in E$ we have $W(i,j)=W(j,i)$. Otherwise, it is directed

(see undirected graph)

Unweighted

A graph $G$ is unweighted if $W:E\to \{0,1\}$ where

• $0$ corresponds to no edge
• $1$ corresponds to an edge These correspond to a binary relationship between nodes

Example

• Friendship networks are unweighted
• Citation networks
• etc

A graph is weighted if $W:E\to \mathbb{R}$

Example

• Road networks, weights proportional to the lengths (traveling salesman problem)
• Correlation networks (graph induced by covariance matrix)
• etc

(see unweighted graph)

Graph Signals

Graph signals are data that exist on a graph $G$. Data are represented as vectors $x\in {\mathbb{R}}^n$ where $x_i$ is the signal value at node $i$. This is often implicit, but sometimes we will use the notation $(G,x)$.

There are two types of signals:

• fixed node properties or features are information associated with nodes
  • ex. Nodes belong to group A or group B
• graph signals (which often implies variability) can be interpreted as variables on the nodes of the graph

  • ex. traffic counts on the roads of minnesota

(see graph signals)

Question

How do we process graph signals? How do signals $x$ interact with the graph $G$?

We can do this through a network diffusion process

• sometimes called message passing, aggregation

Network Diffusion Process

A network diffusion process is a way to process graph signals. It is a procedure or description of ways to estimate information about a graph using available information and computations.

Example

Suppose we have a graph (see notes on Canvas and add graphic) with labelled nodes. We want to determine the labels of some nodes with unknown label.

Local (node-level) estimation or attributes with limited communications imposed by $G$.

• idea: take info from all its neighbors and average their labels
• ${\hat{x}}_a=\frac{{\sum }_{N_a}{x}_j}{|N_a|}$ where $N_a$ is the neighborhood (graph) of $a$.

Example: Signal Forecasting (Traffic Flow) $G$ is a directed graph and weighted with ${\sum }_{j}W(i,j)=1$ at each node $i$. ie, $W(i,j)$ is a probability of moving from $i$ to $j$. If $x_i(t)$ is the traffic at time $t$, how do we estimate $x_i(t+1)$?

Suppose

Define $N_i^{\text{in}}=\{j\in V:(j,i)\in E\}$ and $N_i^{\text{out}}=\{j\in V:(i,j)\in E\}$.

We can estimate $x_i(t+1)$ as ${\hat{x}}_i(t+1)={\sum }_{N_i^{\text{in}}}W(j,i)x_j(t)$

• We assume that all traffic at node $i$ leaves ie $x_i(t)={\sum }_{N_i^{\text{out}}}W(i,j)x_i(t)$

(see network diffusion process)

Neighbors

The neighborhood of node $a$ is the set $N_a=\{j\in V\text{ s.t. }(a,j)\in E\}$

(see neighborhood (graph))

Diffusion processes are local to each node and we represent them locally above.

• Can also represent these globally using matrices

Adjacency Matrix

The adjacency matrix for a graph $G$ is defined as

0 \text{ otherwise}\end{cases}$$

++++ (see notes) In our above example, $x(t+1)$ can be expressed as a function of $x(t)\in {\mathbb{R}}^n$ as $x(t+1)=Ax(t)$ $[Ax(t+1){]}_i={\sum }_{j\in V}{A}_{ij}\cdot x(t{)}_j={\sum }_{j\in N_i^{\text{in}}}W(j,i)\cdot x(t{)}_j$

Graph Shift Opterator

We can define more general diffusion processes by defining the matrix $S\in {\mathbb{R}}^{n\times n}$ such that $S_{ij}\ne 0⟺(i,j)\in E$ (can only equal 0 along the diagonal?)

This matrix is called the graph shift operator (GSO). We way $z=Sx$ is a (graph) “shift” or diffusion of $x$ by $S$.

Most common are adjacency matrix and laplacian We don’t really use 5,6,7 for directed graphs

We can always recover the local implementations: $z_i={\sum }_j{S}_{ij}{x}_j={\sum }_{j\in N_i}{S}_{ij}{x}_j$

(see graph shift operator)

Examples of Graph Shift Operators

• adjacency matrix

• degree matrix

• graph laplacian

• random walk matrix

• random walk laplacian

• normalized adjacency matrix

• normalized graph laplacian

directed graphs.

We usually don’t use the last 3 with