convergence bound for graph convolutions

[[concept]]

Theorem

Let $(G_n,X_n)\sim (W,\mathcal{X})$ and let graph and graphon convolutions be such that $H(G_n)={\sum }_{k=0}^{\infty }{h}_k{\left(\frac{A_n}{n}\right)}^k\text{ and }{T}_H={\sum }_{k=0}^{\infty }{h}_k{T}_W^k$ Further, assume

1. $||\mathcal{X}||\le 1$ (WLOG)
2. $|h(\lambda )|<1$ and $h(\lambda )$ is $L-$Lipschitz in $[-1,-c]\cup [c,1]$ and $\ell -$Lipschitz in $(-c,c)$

Then we have $||{\mathcal{Y}}_n-\mathcal{Y}||\le \left(L+\frac{\pi n_c}{{\delta }_c}\right)||T_W-T_{W_n}||+(Lc+2)||\mathcal{X}-{\mathcal{X}}_n||+2\ell c$

NOTE

note that this bound depends on

• the norm difference between the graphon and the induced graphon $||T_W-T_{W_n}||$
• the the norm difference between the graphon signal and the induced graphon signal $||\mathcal{X}-{\mathcal{X}}_n||$

We already know that these two things converge (we’ve already discussed the (slow) convergence rate for $W_n$ in induced graph sequence converges if and only if the induced graphon sequence converges). We can bring the rates for both quantities to $\mathcal{O}\left(\frac{1}{n}\right)$ by introducing more restrictive requirements.

• Convergence $(G_n,X_n)\to (W,\mathcal{X})$ with appropriate node labelling means approximation improves with $n$ as expected
• The bound grows with $\left(L+\frac{\pi n_c}{{\delta }_c}\right)$
  • if we want better discriminability, then we need a lower $c$. A lower $c$ means
    • a higher c band cardinality $n_c$
    • a lower c eigenvalue margin ${\delta }_c$
    • a higher $\frac{\pi n_c}{{\delta }_c}$, and thus a worse convergence bound
  • ie, the bound is large when the filter is most discriminative

Here, the convergence-discriminability tradeoff is explicit. We can see that larger $L$ and smaller $c$ (more discriminative filters) lead to a higher error bound.

The last term $2\ell c$ does not vanish. We can think of this as the “approximation error” that comes from the fact that the eigenvalues of the graphs converge non-uniformly (recall this conjecture).

In the finite sample regime, unless $\ell =0$, there is always leftover “nontransferable energy” corresponding to the spectral components with $|{\lambda }_i|<c$ which do not converge

Review

dsg

What 3(or 4) conditions do we need for a convergence bound on the graph convolution $H(G_n)={\sum }_{k=0}^{\infty }{h}_k{\left(\frac{A_n}{n}\right)}^k$ to the limiting graphon convolution $T_H={\sum }_{k=0}^{\infty }{h}_k{T}_W^k$ of a signal $X\to \mathcal{X}$? (hint: signal condition, $h$ function conditions) -?-

1. The graphon signal $||\mathcal{X}||\le 1$
2. the functions $|h(\lambda )|<1$ and
3. $h(\lambda )$ is $L-$Lipschitz in $[-1,-c]\cup [c,1]$
   • and $\ell -$Lipschitz in $(-c,c)$

Mentions

Mentions

TABLE file.mday as "Last Modified"
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source
SORT file.mday ASC
SORT file.name ASC

const { dateTime } = await cJS()
 
return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}