Generalized energy and gradient ﬂow via graph framelets Andi HanDai ShiZhiqi ShaoJunbin Gao

2025-05-06 0 0 626.99KB 18 页 10玖币

侵权投诉

Generalized energy and gradient ﬂow

via graph framelets

Andi Han∗Dai Shi†Zhiqi Shao∗Junbin Gao∗

Abstract

In this work, we provide a theoretical understanding of the framelet-based graph neural

networks through the perspective of energy gradient ﬂow. By viewing the framelet-based models

as discretized gradient ﬂows of some energy, we show it can induce both low-frequency and

high-frequency-dominated dynamics, via the separate weight matrices for diﬀerent frequency

components. This substantiates its good empirical performance on both homophilic and het-

erophilic graphs. We then propose a generalized energy via framelet decomposition and show its

gradient ﬂow leads to a novel graph neural network, which includes many existing models as

special cases. We then explain how the proposed model generally leads to more ﬂexible dynamics,

thus potentially enhancing the representation power of graph neural networks.

1 Introduction

Graph neural networks (GNNs) [

] have become the primary tool for representation

learning over graph-structured data, such as social networks [

] citation networks [

], molecules

[

], traﬃc networks [

], among others. There generally exists two types of GNN models, i.e.,

spatial and spectral based models. Spatial GNNs, including MPNN [

], GAT [

], GIN [

], usually

propagate information in the neighbourhood and update node representations via a weighted average

of the neighbours. Spectral GNNs, including ChebyNet [

], GCN [

], BernNet [

], performs

ﬁltering on the spectral domain provided by graph Fourier transform (where the orthonormal system

is given by the eigenvectors of graph Laplacian). Wavelet-based graph representation learning

[

], a class of spectral methods, provide a multi-resolution analysis

of graph signals and thus often lead to better signal representations by capturing information at

diﬀerent scales. In particular, graph framelets [

], a type of tight wavelet frame, further allows

separate modelling of low-pass and high-pass signal information, and has been considered to deﬁne

graph convolution as in [

]. It has been shown that the graph framelet convolution allows

more ﬂexible control of approximate (via low-pass ﬁlters) and detailed information (via high-pass

ﬁlters) with great robustness and eﬃciency, achieving the state-of-the-art results on multiple graph

learning tasks [8, 50, 51, 55, 56, 58].

Along with the developments of more advanced models, theoretical understanding of both the

power and pitfalls of graph neural networks has called for great attention. Currently, there exists

many known limitations of GNNs, including over-smoothing [

], over-squashing [

], limited

expressive power [

] and poor performance on heterophilic graphs [

]. In an attempt

∗University of Sydney (andi.han@sydney.edu.au,zsha2911@uni.sydney.edu.au,junbin.gao@sydney.edu.au)

†Western Sydney University (dai.shi@sydney.edu.au)

arXiv:2210.04124v1 [cs.LG] 8 Oct 2022

to better resolve the above issues, many studies have tried to understand GNNs through various

frameworks, such as dynamical systems and diﬀerential equations [

], Riemannian

geometry [

], algebraic topology [

]. Nevertheless, existing analyses are limited to either

spatial GNNs or spectral GNNs based on the Fourier transform. In fact, it has been empirically

observed that wavelet/framelet-based models tend to alleviate the previously known issues, such as

mitigating the issue of over-smoothing [

] and achieving good performance on heterophilic graphs

[

]. Despite the success of wavelet-based models, comparatively little is known on how the multi-scale

and frequency-separation properties provided by graph wavelets/framelets potentially avoid the

aforementioned pitfalls and enhance the learning capacity of GNNs.

In this paper, we particularly focus on the graph framelet-based models and analyze the model

behaviors from the perspective of energy gradient ﬂows. In physics, the evolution of particles is

often modelled as diﬀerential equations that minimize an energy, known as the gradient ﬂows. The

energy functional and its gradient ﬂow provide a characterization of particles’ states and movements,

which are essential to understand the dynamics. Recently, such idea has been adapted to graph

neural networks [

]. By modelling GNNs as (discretized) gradient ﬂows, one can study the limiting

behaviors of GNNs, which are closely related to the notions of over-smoothing, over-separating and

heterophilic graphs. Particularly, [

] characterizes the dynamics of GNNs in terms of low-frequency

or high-frequency dominance or both. It is known that low-frequency-dominant (LFD) models tend

to perform well on homophilic graphs (where neighbouring nodes are likely to come from the same

cluster) [

] while in contrast, high-frequency-dominant (HFD) models tend to perform

well on heterophilic graphs [

]. In this regard, models that can be both LFD and HFD are

usually preferred.

To the best of our knowledge, this is the ﬁrst work that provides a theoretical understanding of

multi-scale graph neural networks and justiﬁcation for its good empirical performance. Speciﬁcally,

we highlight our main contributions as follows.

•

We show the framelet convolutions, either spatial-based [

] or spectral-based [

] can be viewed

as a discretized gradient ﬂow of some energy. From this point of view, we prove that the

framelet-based GNNs can induce both LFD and HFD dynamics, thus theoretically explaining

its eﬀectiveness on heterophilic graphs and its capability to potentially avoid over-smoothing,

as often empirically observed.

•

We then deﬁne a generalized energy via framelet decomposition. We show such energy includes

the energy proposed in [

], which itself is a generalization of the graph Dirichlet energy.

We then propose a GNN model, namely gradient ﬂow based framelet graph convolution

(GradF-UFG), as discretization of the proposed generalized energy.

•

We show the proposed GradF-UFG includes the framelet-based GNNs as special cases. We also

connect the proposed model with the recently introduced energy enhanced framelet convolution

and analyze its behaviors. We explain how the proposed model provides more ﬂexibility

compared to existing works.

Organization.

The rest of the paper is organized as follows. Section 2 ﬁrst summarizes the related

works on continuous GNNs and its connections to dynamical systems and diﬀerential equations. We

also provide an overview on framelet-based graph representation learning. In section 3, we review

the preliminary knowledge on graphs, graph framelets and framelet convolutions. We also introduce

the notions of graph Dirichlet energy, gradient ﬂow along with the deﬁnitions of LFD and HFD

dynamics. Section 4 starts with identifying a connection between the spatial framelet convolution

with Dirichlet energy and also characterizes its asymptotic behaviors from the lens of gradient ﬂow.

In section 5, we deﬁne the framelet generalized energy and propose a GNN model based on its

gradient ﬂow, where we also connect to existing works. Finally, in section 6, we perform similar

analysis for the spectral framelet convolution.

2 Related works

Dynamical systems, diﬀerential equations and GNNs.

Neural ODE [

] is introduced as a

continuous version of ResNet [

]. Since then, many work has studied its counterparts on graphs

and proposed continuous GNNs, such as [

]. Another parallel research direction aims to

understand GNNs from continuous dynamical systems and diﬀerential equations. GCN [

], one

of the most popular GNN models, can be viewed as a discrete Markov process [

] and its linear

version is veriﬁed as the discretized (isotropic) graph heat diﬀusion [

], which minimizes the graph

Dirichlet energy. Similarly, GAT [

] is related to an anisotropic heat diﬀusion on graphs as shown

in [

]. Furthermore, many recent studies introduce GNNs that are inspired by physical systems and

diﬀusion PDEs, including heat diﬀusion with a source term [

], non-Euclidean Beltrami ﬂow [

wave diﬀusion equation [

], networks of coupled oscillators [

], nonlinear anisotropic diﬀusion [

The recent work [

] provides a framework for analyzing continuous formulation of GNN models as

gradient ﬂows of some energy. In particular, the work proposes a general energy where its gradient

ﬂow leads to many existing GNN models. Under such framework, [

] veriﬁes that many models can

only lead to LFD dynamics, including GCN [28], GRAND [6], CGNN [47] and PDE-GCN [19].

Framelet-based graph learning.

The work [

] provides an eﬃcient way to compute graph

framelet transforms via Chebyshev polynomial approximation, which allows practical applications

such as semi-supervised clustering. Graph spectral framelet convolution has been proposed in [

which is shown to empirically enhance the graph neural networks with its robustness and multi-scale

properties. Later, graph framelets have been integrated for graph signal denoising [

], robust graph

embedding [

], dynamic graph [

] and directed graph learning [

], exhibiting great improvement

in model performance. More recently, [

] proposes a spatial graph framelet convolution and shows

its close connection to the Dirichlet energy. The paper also introduces a perturbed Dirichlet energy

in order to mitigate the over-smoothing issue.

3 Preliminaries

Graphs and graph convolution.

A graph

= (

VG,EG

)of

nodes (with self-loops) can be

represented by graph adjacency matrix

A∈Rn×n

. In this work, we assume the graph is undirected

and unweighted, i.e.,

is symmetric with

aij

= 1 if (

i, j

)

∈ EG

and 0otherwise. In addition,

we consider the symmetric normalized adjacency matrix as

D−1/2AD−1/2

where

is the

diagonal degree matrix, with the

-th diagonal entry given by

Pjaij

, the degree of node

. The

normalized graph Laplacian is given by

In−b

. We use

ρL

to denote the largest eigenvalue (also

called the highest frequency) of

. From the spectral graph theory [

ρL≤

2and the equality

holds if and only if there exists a connected component of the graph Gthat is bipartite.

Graph convolution network (GCN) [

] deﬁnes the layer-wise propagation rule via the normalized

adjacency matrix as

H(`+ 1) = σb

AH(`)W`,(1)

where

(

)denotes the feature matrix at layer

with

(0) =

X∈Rn×c

, the input features (also

called input signals), and

is the learnable feature transformation. It can be shown that GCN

corresponds to a localized ﬁlter via graph Fourier transform, i.e.,

(

+ 1) =

(

In−Λ

)

(

)where

U,Λ

are from the eigendecomposition

U>ΛU

and

is known as the Fourier transform of a

graph signal

h∈Rn

. In this paper, we let

{

(

λi,ui

)

i=1

be the set of eigen-pairs of

where

are

the row vectors of U.

Graph framelets and framelet convolution.

Graph (undecimated) framelets [

] are deﬁned

via a ﬁlter bank

;

b(1), ..., b(L)}

and its induced (complex-valued) scaling functions Ψ =

{α

;

β(1), ..., β(L)}

where

is the number of high-pass ﬁlters. Particularly, it satisﬁes that

bα

) =

(

)

bα

(

)and

β(r)

) =

b(r)

(

)

bα

(

)for all

ξ∈R, r

= 1

, ..., L

where

bα, d

β(r)

denote the Fourier

transform of α, β(r)and ba, d

b(r)denote the Fourier series of a, b(r)respectively. The graph framelets

are deﬁned by

ϕj,p

(

) =

i=1 bαλi/2jui

(

)

(

)and

ψr

j,p

(

) =

i=1 d

β(r)λi/

jui

(

)

(

)for

= 1

, ..., L

and for scale level

= 1

, ..., J

. We use

(

)to represent the eigenvector

at node

ϕj,p and ψr

j,p are known as the low-pass framelets and high-pass framelets at node p.

The framelet coeﬃcients of a graph signal

are given by

{hϕ0,p,hi}p∈VG

{hψr

j,p,hi}p∈VG

For a multi-channel signal H∈Rn×c, we can compactly write its framelet coeﬃcients as

V0=U>bαΛ

2UH,Wr

j=U>d

β(r)Λ

2j+1 UH,∀j= 0, ..., J, r = 1, ..., L

where

bα, d

β(r)

applies elementwise to the diagonal of

, and

V0,Wr

are respectively the low-pass and

high-pass coeﬃcients. Deﬁne the framelet transform matrices

W0,J ,Wr,j

such that

W0,J H

U>Λ0,J UH

, and

Wr,jH

U>Λr,jUH

for

= 1

, ..., L, j

= 1

, ..., J

, where

Λr,j

is a diagonal

matrix with entries (

Λ0,J

)

bα

(

λi/

2) and (

Λr,j

)

β(r)

(

λi/

j+1

). By the tightness of the framelet

transform, we have

Λ2

0,J

Pr,j Λ2

r,j

and the framelet decomposition and reconstruction are

invertible, i.e.,

0,J W0,J H

Pr,j W>

r,jWr,jH

∗

This property allows unique decomposition of

any graph signal onto the spectral framelet domain. Refer to [51, 53] for more detailed discussions.

The spectral graph framelet convolution is proposed in [

], which is similar to the graph

(Fourier) convolution by applying a ﬁlter on the spectral domain before reconstructing the sig-

nal. The layer-wise propagation rule is given by

(

+ 1) =

σW>

0,J diag

(

θ0,J

)

W0,J H

(

)

Pr,j W>

r,jdiag

(

θr,j

)

Wr,jH

(

)

W`

, where

θr,j ∈Rn

is a learnable ﬁlter coeﬃcient and

is a shared

weight matrix across all

r, j

for layer

. Rather than performing spectral ﬁltering as in [

], the

spatial graph framelet convolution performs a spatial message passing over the spectral framelet

domain [8] as H(`+ 1) = W>

0,J σb

AW0,J H(`)W`

0,J +Pr,j W>

r,jσb

AWr,jH(`)W`

r,j.

In this paper, our subsequent analysis focuses on the spatial framelet convolution (or just framelet

convolution) due to its connection to the Dirichlet energy as shown in Section 4. Nevertheless, we

also obtain similar conclusions for spectral framelet convolution in Section 6.

∗

With a slight abuse of notations, we use

to also represent conjugate transpose if the ﬁlters are complex-valued.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

GeneralizedenergyandgradientowviagraphframeletsAndiHan*DaiShiZhiqiShao*JunbinGao*AbstractInthiswork,weprovideatheoreticalunderstandingoftheframelet-basedgraphneuralnetworksthroughtheperspectiveofenergygradientow.Byviewingtheframelet-basedmodelsasdiscretizedgradientowsofsomeenergy,weshowitcanindu...

展开>> 收起<<

Generalized energy and gradient ﬂow via graph framelets Andi HanDai ShiZhiqi ShaoJunbin Gao.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Generalized energy and gradient ﬂow via graph framelets Andi HanDai ShiZhiqi ShaoJunbin Gao

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: