Generalized Laplacian Regularized Framelet Graph Neural Networks Zhiqi ShaoAndi HanDai Shi Andrey Vasnev

2025-05-06 0 0 3.22MB 36 页 10玖币

侵权投诉

Generalized Laplacian Regularized Framelet

Graph Neural Networks

Zhiqi Shao∗Andi Han∗Dai Shi†∗ Andrey Vasnev ∗

Junbin Gao∗

July 14, 2023

Abstract

Graph neural networks (GNNs) have achieved remarkable results for

various graph learning tasks. However, one of the recent challenges for

GNNs is to adapt to diﬀerent types of graph inputs, such as heterophilic

graph datasets in which linked nodes are more likely to contain a diﬀerent

class of labels and features. Accordingly, an ideal GNN model should

adaptively accommodate all types of graph datasets with diﬀerent labeling

distributions. In this paper, we tackle this challenge by proposing a

regularization framework on graph framelet with the regularizer induced

from graph

-Laplacian. By adjusting the value of

, the

-Laplacian based

regularizer restricts the solution space of graph framelet into the desirable

region based on the graph homophilic features. We propose an algorithm

to eﬀectively solve a more generalized regularization problem and prove

that the algorithm imposes a (

-Laplacian based) spectral convolution

and diagonal scaling operation to the framelet ﬁltered node features.

Furthermore, we analyze the denoising power of the proposed model and

compare it with the predeﬁned framelet denoising regularizer. Finally, we

conduct empirical studies to show the prediction power of the proposed

model in both homophily undirect and heterophily direct graphs with

and without noises. Our proposed model shows signiﬁcant improvements

compared to multiple baselines, and this suggests the eﬀectiveness of

combining graph framelet and p-Laplacian.

Highlight

•

We deﬁne two types of new GNN layers by introducing

-Laplacian regu-

larizers to both decomposed and reconstructed framelets.

∗

University of Sydney (

zhiqi.shao@sydney.edu.au

andi.han@uni.sydney.edu.au

andrey.vasnev@uni.sydney.edu.au,junbin.gao@sydney.edu.au)

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

Zhiqi Shao, Andi Han and Dai Shi are with equal contribution.

arXiv:2210.15092v2 [cs.LG] 13 Jul 2023

•

We provide an iterative algorithm to ﬁt the proposed models and explore

an alternative algorithm developed from the F-norm Locality Preserving

Projection (LPP).

•

We prove that our algorithm provides a sequence of spectral graph con-

volutions and diagonal scaling over framelet-ﬁltered graph signals and

this further explains the interaction between

-Laplacian regularizer and

framelet.

•

We link the proposed

-Laplacian regularizer with the previous work of

framelet regularizer to illustrate the denoising power of our model.

•

We test the model on homophilic (undirected) and heterophilic (directed)

graphs. To our best knowledge, we are the ﬁrst to explore the possibility

of applying the framelet GCN for directed graphs

1 Introduction

Graph neural networks (GNNs) have demonstrated remarkable ability for graph

learning tasks (Bronstein et al, 2017; Wu et al, 2020; Zhang et al, 2022; Zhou

et al, 2020). The input to GNNs is the so-called graph data which records

useful features and structural information among data. Such data are widely

seen in many ﬁelds, such as biomedical science (Ahmedt-Aristizabal et al, 2021),

social networks (Fan et al, 2019), and recommend systems (Wu et al, 2022).

GNN models can be broadly categorized into spectral and spatial methods. The

spatial methods such as MPNN (Gilmer et al, 2017), GAT (Veličković et al,

2018) and GIN (Xu et al, 2018a) utilize the message passing mechanism to

propagate node feature information based on their neighbours (Scarselli et al,

2009). On the other hand, the spectral methods including ChebyNet (Deﬀerrard

et al, 2016), GCN (Kipf and Welling, 2017) and BernNet (He et al, 2021) are

derived from the classic convolutional networks, treating the input graph data

as signals (i.e., a function with the domain of graph nodes) (Ortega et al, 2018),

and ﬁltering signals in the Fourier domain (Bruna et al, 2014; Deﬀerrard et al,

2016). Among various spectral-based GNNs, the graph framelets GCN (Zheng

et al, 2022), which is constructed on a type of wavelet frame analogized from the

identical concept deﬁned on manifold (Dong, 2017), further separates the input

signal by predeﬁned low-pass and high-pass ﬁltering functions and resulting a

convolution-type model as in the studies (Chen et al, 2022a; Zheng et al, 2021b,

2022). The graph framelet shows great ﬂexibility in terms of controlling both

low and high-frequency information with robustness to noise and thus in general

possesses high prediction power in multiple graph learning tasks (Chen et al,

2022a; Yang et al, 2022; Zheng et al, 2021b; Zhou et al, 2021a,b; Zou et al, 2022).

Along with the path of developing more advanced models, one of the major

challenges in GNN is identiﬁed from the aspect of data consistency. For example,

many GNN models (Xu et al, 2018a; Wu et al, 2020; Zhu et al, 2020b; Wu et al,

2021; Liu et al, 2022) are designed based on the homophily assumption i.e., nodes

with similar features or labels are often linked with each other. Such phenomenon

can be commonly observed in citation networks (Ciotti et al, 2016) which have

been widely used as benchmarks in GNNs empirical studies. However, the

homophily assumption may not always hold, and its opposite, i.e. Heterophily,

can be observed quite often in many real-world datasets in which the linked

nodes are more likely to contain diﬀerent class labels and features (Zheng et al,

2021a). For example, in online transaction networks, fraudsters are more likely

to link to customers instead of other fraudsters (Pandit et al, 2007). The GNNs

designed under homophilic assumption are deemed unsuitable for heterophilic

graphs. It is evident from their signiﬁcant performance degradation (Zheng et al,

2021a). The reason is that the class of heterophilic graphs contains heterogeneous

instances and hence the signals should be sharpened rather than smoothed out.

An ideal framework for learning on graphs should be able to accommodate both

homophilic and heterophilic scenarios.

One of the active aspects to resolve the GNN adaption challenge is by

regularizing the solution of GNNs via the perspective of optimization. The

work done by Zhu et al (2021) uniﬁed most of state-of-the-art GNNs as an

optimization framework. Furthermore, one of the recent works (Fu et al, 2022)

considered assigning an adjustable

-Laplacian regularizer to the (discrete) graph

regularization problem that is conventionally treated as a way of producing GNN

outcomes (i.e., Laplacian smoothing). In view of the fact that the classic graph

Laplacian regularizer measures the graph signal energy along edges under

metric, it would be beneﬁcial if GNN could be adapted to heterophilic graphs

under

metric (1

≤p <

2). Given that

metric is more robust to high-

frequency signals, a higher model discriminative power is preserved. The early

work (Hu et al, 2018) has demonstrated the advantage of adopting

metric

in the Locality Preserving Projection (LPP) model. In addition, the recently

proposed

-Laplacian GNN (Fu et al, 2022) adaptively modiﬁes aggregation

weights by exploiting the variance of node embeddings on edges measured by the

graph gradient. With a further investigation on the application of

-Laplacian,

Luo et al (2010) suggested an eﬃcient gradient descent optimization strategy

to construct the

-Laplacian embedding space that guarantees convergence to

viable local solutions. Although the

-Laplacian based optimization scheme has

been successfully lodged in basic GNN model (Fu et al, 2022), whether it can

be further incorporated with more advanced GNN model (i.e., graph framelets)

with higher prediction power and ﬂexibility is still unclear. Speciﬁcally, one

may be interested in identifying whether the advantage of deploying

-Laplacian

in GNN still remains in graph framelet or what is the exact functionality of

-Laplacian interacting with the feature representations generated both low

and high pass framelet domains. In addition, as graph framelets have shown

great potential in terms of the graph noise reduction (Zheng et al, 2022; Yang

et al, 2022; Zou et al, 2022), whether the inclusion of

-Laplacian regularizer

could enhance/dilute such power remains unclear. These research gaps inspire

us to incorporate

-Laplacian into graph framelets and explore further for the

underlying relationship between them.

Since the

-Laplacian regularized optimization problem lacks a closed-form

solution, except for when

= 2 (Zhou and Schölkopf, 2005), an iterative algorithm

is suggested to estimate the solution and each iteration can be analogized to a

GNN layer (Zhou et al, 2021a)). The solution of such an algorithm is deﬁned

by the ﬁrst-order condition of the optimization problem. As a result, one can

relate this to the implicit layer approach (Chen et al, 2022b; Zhang et al, 2003)

which has the potential of avoiding over-smoothing issues since the adjusted node

feature will be re-injected in each iteration step. By adjusting the value of

, both

-Laplacian GNN and the algorithm are capable of producing learning outcomes

with diﬀerent discriminative levels and thus able to handle both homophilic

and heterophilic graphs. Similar work has been done by Frecon et al (2022)

which presents a framework based on the Bregman layer to fulﬁll the bi-level

optimization formulations. To reap the beneﬁt of

-Laplacian regularization in

the framelet domain, in this paper, we propose two

-Laplacian Regularized

Framelet GCN models which are named

-Laplacian Undecimated Framelet GCN

(pL-UFG) and

-Laplacian Fourier Undecimated Framelet GCN (pL-fUFG). In

these models, the

-Laplacian regularization can be applied on either the framelet

domain or the well-known framelet Fourier domain. The

-Laplacian-based

regularizer incurs a penalty to both low and high-frequency domains created

by framelet, producing ﬂexible models that are capable of adapting diﬀerent

types of graph inputs (i.e., homophily and heterophily, direct and undirect). We

summarize our contributions as follows:

•

We deﬁne two types of new GNN layers by introducing

-Laplacian regu-

larizers to both decomposed and reconstructed framelets. This paves the

way for introducing more general Bregman divergence regularization in

the graph framelet framework;

•

We propose an iterative algorithm to ﬁt the proposed models and explore

an alternative algorithm developed from the F-norm LPP;

•

We prove that the iteration of the proposed algorithm provides a sequence

of spectral graph convolutions and diagonal scaling over framelet-ﬁltered

graph signals, this gives an deeper explanation of how

-Laplacian regular-

izer interacts with the framelet.

•

We connect the proposed

-Laplacian regularizer to the previously studied

framelet regularizer to illustrate the denoising power of the proposed model.

•

We investigate the performance of the new models on graph learning tasks

for both homophilic (undirected) graphs and heterophilic (directed) graphs.

To our best knowledge, we are the ﬁrst to explore the possibility of applying

the framelet GCN for directed graphs. The experiment results demonstrate

the eﬀectiveness of pL-UFG and pL-fUFG on real-world node classiﬁcation

tasks with strong robustness.

The rest of the paper is organized as follows. In Section 2, we introduce

the

-Laplacian operator and regularized GNN, followed by a review of recent

studies on regularized graph neural networks, which include implicit layers and

graph homophily. In Section 3, we introduce the fundamental properties of graph

framelet and propose the

-Laplacian regularized framelet models. Furthermore,

we develop an algorithm to solve the regularization problem that is more general

than

-Laplacian regularization. We also provide theoretical analysis to show

how the

-Laplacian based regularizer interacts with the graph framelet. By the

end of Section 3 a brief discussion on the denoising power of the proposed model

is presented. Lastly, we present the experimental results and analysis in Section

5. Finally, this paper is concluded in Section 6.

2 Preliminaries

This section provides an in-depth exploration of the fundamental concepts,

encompassing graphs, graph framelets, and regularized graph neural networks.

For the sake of reader comprehension and ease of following the intended ideas,

each newly introduced model and deﬁnition will be accompanied by a succinct

review of its developmental history.

2.1 Basic Notations

Let

= (

V,E, W

)denote a weighted graph, where

{v1, v2,· · · , vN}

and

E ⊆ V ×V

represent the node set and the edge set, respectively. X

∈RN×c

is the

feature matrix for

with

{

2,· · · ,

as its rows, and

= [

wi,j

]

∈RN×N

is the weight matrix on edges with

wi,j >

0if (

vi, vj

)

∈ E

and

wi,j

= 0 otherwise.

For undirected graphs, we have

wi,j

wj,i

which means that

is a symmetric

matrix. For directed graphs, it is likely that

wi,j ̸

wj,i

which means that

may not be a symmetric matrix. In most cases, the weight matrix is the

graph adjacency matrix, i.e.,

wi,j ∈ {

}

with elements

wi,j

= 1 if (

vi, vj

)

∈ E

and

wi,j

= 0 otherwise. Furthermore, let

{vj

: (

vi, vj

)

∈ E}

denote the

set of neighbours of node

and D=

diag

(

d1,1, ..., dN,N

)

∈RN×N

denote the

diagonal degree matrix with

di,i

j=1 wi,j

for

= 1

, ..., N

. The normalized

graph Laplacian is deﬁned as

−

−1

(W+I)D

−1

. Lastly, for any vector

x= (

x1, ..., xc

)

∈Rc

, we use

∥

∥2

= (

i=1 x2

)

to denote its L

-norm, and

similarly for any matrix M= [

mi,j

∥

∥F

= (

Pi,j m2

i,j

)

is used to

denote its Frobenius norm.

2.2 Consistency in Graphs

Generally speaking, most GNN frameworks are designed under the homophily

assumption in which the labels of nodes and neighbours in the graph are mostly

identical. The recent work by Zhu et al (2020a) emphasises that the general

topology GNN fails to obtain outstanding results on the graphs with diﬀerent class

labels and dissimilar features in their connected nodes, which we call heterophilic

or low homophilic graphs. The deﬁnition of homophilic and heterophilic graphs

are given by:

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

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

10 玖币 0人已下载

立即下载

摘要：

GeneralizedLaplacianRegularizedFrameletGraphNeuralNetworksZhiqiShao∗AndiHan∗DaiShi†∗AndreyVasnev∗JunbinGao∗July14,2023AbstractGraphneuralnetworks(GNNs)haveachievedremarkableresultsforvariousgraphlearningtasks.However,oneoftherecentchallengesforGNNsistoadapttodifferenttypesofgraphinputs,suchasheterop...

展开>> 收起<<

Generalized Laplacian Regularized Framelet Graph Neural Networks Zhiqi ShaoAndi HanDai Shi Andrey Vasnev.pdf

共36页,预览5页

还剩页未读，继续阅读

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

Generalized Laplacian Regularized Framelet Graph Neural Networks Zhiqi ShaoAndi HanDai Shi Andrey Vasnev

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: