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 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 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 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)

Suppose $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)$ ?

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

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

We assume that all traffic at node $i$ leaves ie $x_{i} (t) = \sum_{N_{i}^{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 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

A_{i j} = {\begin{cases} W (j, i) if (j, i) \in E \\ 0 otherwise \end{cases}

++++ (see notes)
In our above example, $x (t + 1)$ can be expressed as a function of $x (t) \in R^{n}$ as
$x (t + 1) = A x (t)$

[A x (t + 1)]_{i} = \sum_{j \in V} A_{i j} \cdot x (t)_{j} = \sum_{j \in N_{i}^{in}} W (j, i) \cdot x (t)_{j}

Graph Shift Opterator

We can define more general diffusion processes by defining the matrix $S \in R^{n \times n}$ such that

S_{i j} \neq 0 ⟺ (i, j) \in E

(can only equal 0 along the diagonal?)

This matrix is called the graph shift operator (GSO). We way $z = S x$ 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_{i j} x_{j} = \sum_{j \in N_{i}} S_{i j} x_{j}

(see graph shift operator)

Examples of Graph Shift Operators

Note

We usually don't use the last 3 with directed graphs.