We want to use the kernel cut norm to be able to compute a distance between the two induced graphons (recall we do this by dividing the interval $[0,1]$ into $n$ subintervals each corresponding to a node).

However, the cut norm does not take into account {ass||permutations of the intervals $I_k$||limitation} so {has||we cannot use this norm to define our metric directly||consequence}. To take these into account, we use {hha||measure-preserving bijections on the sample space/support for the graphon $W$ (typically the unit interval) which we can think of as "permutations"||workaround}.

Let $G_n$ and $G_m$ be two graphs with possibly different node counts $n$ and $m$ respectively. The cut distance is given by

Where $W_n,W_m$ are the induced graphons of the graphs.

We can show equivalence of right- and left- cut homomorphism density convergence with the cut distance for dense graphs.

Sequences of graphs $\{G_n\}$ converging to graphon $W$ also converge in the cut norm:

Where $W_n$ is the induced graphon of $G_n$.

This answers the question that we had last time

2. Can we prove the GNN is continuous WRT to this metric?

Inequality results comparing the cut norm and various L-p norms are for kernels that are {ass||more general than our graphons||comparison to graphon}. We want {has||the codomain to be $[-1,1]$||modification} because {hha||taking the cut norm for a difference of graphons $W-W^{\prime }$ gives values in this interval.||modification reason}

Let $W:[0,1{]}^2\to [-1,1]$. Then

And convergence $L_p$ for $p\ge 1$ implies convergence in the cut norm

Easy to see (1) from the definition of the cut norm:

Let $W:[0,1{]}^2\to [-1,1]$. Then

ie, cut norm convergence implies convergence in $L_2$

We first show inequality (2). Using the definition of the cut norm, we have

Since we are taking the supremum, it is equivalent to taking the supremum over all $L_{\mathrm{\infty }}$ functions $f$ and $g$.

To get $(\ast )$, we notice that ${\int }_0^{1}W(u,v)f(u)du$ is an integral linear operator with kernel $W$. We denote this with $T_W$ so that

• or equivalently that $T_{W}f={\int }_0^{1}W(u,\cdot )f(u)du$
  We can then see that the definition becomes the absolute value of the inner product of two $L_{\mathrm{\infty }}$ functions.

Note that $||W|{|}_{\mathrm{\infty }\to 1}$ is an induced operator norm of the graphon mapping functions from $L_{\mathrm{\infty }}$ to $L_1$.

• we omit the denominator in our usual definition of the operator norm since $g$ is bounded by $-1$ and $1$ and $g\in L_{\mathrm{\infty }}$
• We can rewrite this using $f$ to match in the definition of the $L_1$ norm since we are taking the supremum
• For more about $L_p$ spaces see wikipedia (hand wavy/cursory for this class on functional analysis details)

We can then rewrite this as

Where we get $(\ast \ast )$ by the triangle inequality and $(†)$ from the definition of $||\cdot |{|}_{◻}$.

• Note that this is a loose bound!

And this gives us the desired result for (2).

Proving (1) is more involved and uses more functional analysis.

Use the Riesz-Thorin interpolation theorem for complex $L_p$ spaces:

Where

• $\theta =min(1-\frac{1}{p},\frac{1}{q})$ and
• $p_0,q_0\in [1,\mathrm{\infty })$
• with $\frac{1}{p}=\frac{1-\theta }{p_0}$ and
• $1-\frac{1}{q}=(1-\theta )(1-\frac{1}{q_0})$ and
• $p_1=\mathrm{\infty },q_1=1$.

Define operator norm$$\lvert \lvert W \rvert \rvert_{\square, \mathbb{C}} = \sup_{\begin{aligned}
f,g:[0,1] &\to \mathbb{C} \\lvert \lvert f \rvert \rvert_{\infty}, \lvert \lvert g \rvert \rvert_{\infty} &≤1 \end{aligned}} \left\lvert \int {0}^1 \int^1 W(u,v) f(u) g(v) , du , dv \right\rvert $$
So for complex functions, we can see that

We then have

Since $W\le 1$, and this gives the desired result.

• We defined convergent graph sequence converging to graphon
• If two graphs belong to the same sequence, we know they are similar using the homomorphism density
• Defined a metric with the cut metric to compute distances between graphs
• If we have convergence in some $L_P$ spaces, we also have convergence in the cut norm and vice versa.
• We can look at graphons as operators

What if the graph is too large and I don’t have enough resources to train on it? (recall GNN forward pass is $\mathcal{O}(LK\cdot |E|)$ where $L$ is the number of layers and $K$ is the order of the filter polynomial)

Graphon as a limiting object for some sequence of graphs

Graphon as generating object for finite graphs

A template graph $G_n$ is a way to sample a graph from a graphon. The nodes are defined by partitioning $[0,1]$ in a grid (regular partition) in the same way we partitioned for induced graphons:

So that $I_1\cup I_2\cup \cdots \cup I_n=[0,1]$ and the node labels are $u_j=\frac{j-1}{n}$ for each $j$.

The adjacency matrix is then given as

Where $W$ is the graphon that we sample from.

This is a complete, weighted graph with edge weights coming from the graphon evaluated at each node pair $(u_i,u_j)\in [0,1{]}^2$.

This is the simplest way to sample a graph. We can think of it as the graph sampling counterpart to inducing a graphon.

Weighted graphs are a way to sample a graph from a graphon. Each node $u_j$ is sampled uniformly at random from the unit interval.

The edges are then defined in the same way as a template graph

Fully random graphs are a way to sample a graph from a graphon. Like a weighted graph (sample), the nodes are sampled uniformly from the unit interval ( $u_i\sim U[0,1]$ ).

The edges are sampled as

So the resulting graph is undirected and unweighted .

Generally we are interested in the fully random graphs.

Let $\{G_n\}$ be a sequence of template graphs sampled from graphon $W$. Then $G_n\to W$ as $n\to \mathrm{\infty }$.

Trivial

• The definition of template graphs is fully deterministic, so there is no randomness here. Since this is the reverse idea of thinking of graphons as graphs with uncountable number of nodes, it is easy to see that the induced graphons $W_n$ converge to $W$ in an $L_2$ way and convergence in L-p implies convergence in cut norm

Let $\{G_n\}$ be a sequence of weighted graphs sampled from graphon $W$. With probability at least $1-\exp (-\frac{n}{2\log n})$,

Where ${\delta }_{◻}$ is the cut metric. ie, $G_n\to W$ in probability.

Let $\{G_n\}$ be a sequence of "fully random" graphs sampled from graphon $W$. With probability at least $1-\exp (-\frac{n}{2\log n})$,

Where ${\delta }_{◻}$ is the cut metric. ie, $G_n\to W$ in probability.

We'll look at the proofs for these later.

If a graph is too big to train on it, we can look at the induced graphon and subsample new graphs from it to train on instead.

How do we determine whether a GNN continuous with respect to the cut metric?

Do GNNs converge?

• generalize up from graphs to graphons
• graph convolution to graphon convolution
• intuition behind why GNNs generalize well with scale
• then look at bounds
  • finite sampling bounds
  • minimum sample sizes
  • error bounds

A graphon signal is defined as a function

contrast this with graph signals, which we defined as $x\in {\mathbb{R}}^n$.

We focus on signals in $L_2$, or "finite energy signals"$\mathcal{X}\in L_2([0,1])$:

Let $(G_n,X_n)$ be a graph signal. The induced graphon signal is defined as the pair $(W_n,{\mathcal{X}}_n)$ where $W_n$ is the induced graphon and

Where $\mathbb{1}$ is the indicator function and

Both representations of 3-node graphs (induced graphon above and induced graphon signal below)