EFFICIENT DIRECTED GRAPH SAMPLING VIA GERSHGORIN DISC ALIGNMENT Yuejiang Li H. Vicky Zhao Gene Cheungy Dept. of Automation Tsinghua University Beijing China

2025-05-03 0 0 590.44KB 9 页 10玖币

侵权投诉

EFFICIENT DIRECTED GRAPH SAMPLING VIA GERSHGORIN DISC ALIGNMENT

Yuejiang Li?, H. Vicky Zhao?, Gene Cheung†

?Dept. of Automation, Tsinghua University, Beijing, China

†York University, Toronto, Canada

ABSTRACT

Graph sampling is the problem of choosing a node subset via sam-

pling matrix H∈ {0,1}K×Nto collect samples y=Hx ∈RK,

K < N, so that the target signal x∈RNcan be reconstructed

in high ﬁdelity. While sampling on undirected graphs is well stud-

ied, we propose the ﬁrst sampling scheme tailored speciﬁcally for

directed graphs, leveraging a previous undirected graph sampling

method based on Gershgorin disc alignment (GDAS). Concretely,

given a directed positive graph Gdspeciﬁed by random-walk graph

Laplacian matrix Łrw , we ﬁrst deﬁne reconstruction of a smooth sig-

nal x∗from samples yusing graph shift variation (GSV) kŁrwxk2

as a signal prior. To minimize worst-case reconstruction error of

the linear system solution x∗=C−1H>ywith symmetric coef-

ﬁcient matrix C=H>H+µŁ>

rw Łrw, the sampling objective is

to choose Hto maximize the smallest eigenvalue λmin(C)of C.

To circumvent eigen-decomposition entirely, we maximize instead a

lower bound λ−

min(SCS−1)of λmin(C)—smallest Gershgorin disc

left-end of a similarity transform of C—via a variant of GDAS based

on Gershgorin circle theorem (GCT). Experimental results show that

our sampling method yields smaller signal reconstruction errors at a

faster speed compared to competing schemes.

Index Terms—Graph signal processing, signal sampling, Ger-

shgorin circle theorem

1. INTRODUCTION

Graph signal processing (GSP) extends traditional signal processing

tools to analyze signals on irregular data kernels described by ﬁnite

graphs [1, 2]. Most existing GSP works consider undirected graph

structures, where each edge connecting two nodes is bidirectional.

However, directionality plays an important role in many practical

information dissemination scenarios [3]. For example, on Twitter, a

celebrity often has a large following but personally follows very few

users [4]. Thus, in these scenarios it is critical to factor directionality

into the network model, resulting in a directed graph.

Graph sampling selects a node subset to collect samples, so that

the target signal can be recovered in high ﬁdelity [5]. Existing graph

sampling works can be classiﬁed into two categories based on prior

assumptions: i) an assumption on strict bandlimitedness of target

signals with a cutoff frequency, and ii) a more general assumption

assuming target signals are “smooth” with respect to (w.r.t.) the un-

derlying graph (e.g., more energy in low frequencies than high fre-

quencies). Bandlimited assumption in the ﬁrst category means that a

target signal lies strictly inside a linear subspace spanned by the ﬁrst

eigenvectors (Fourier modes) of a graph variation operator, such as

the graph Laplacian matrix Ł or the adjacency matrix W[6–10]. As-

suming that the observed signal samples contain noise, [6] proposed

Gene Cheung acknowledges the support of the NSERC grants RGPIN-

2019-06271, RGPAS-2019-00110.

a greedy algorithm to select sample nodes under the E-optimality

criterion [11], and [7] designed a greedy algorithm to minimize the

reconstruction MSE. To lower complexity, [9] and [12] used graph

spectral proxies and localization operators, respectively, to mitigate

the computation burden of eigen-decomposition.

However, the strict bandlimited assumption of target signals is a

strong one that many practical graph signals do not satisfy. To relax

this assumption, works in the second category assume that a target

signal is generally smooth over a given graph [13, 14]. For example,

graph Laplacian regularizer (GLR) [15], i.e.,x>Łx, is often used to

quantify smoothness of signal xover a graph speciﬁed by Laplacian

Ł [13–17]. GLR is often used to regularize under-determined signal

reconstruction problems, such as denoising, dequantization, and in-

terpolation [15, 18, 19]. Using GLR as signal prior, graph sampling

based on Gershgorin disk alignment (GDAS) was proposed to efﬁ-

ciently select sample nodes on undirected (signed) graphs under the

E-optimality criterion [16, 17]. A key feature of GDAS is that it cir-

cumvents eigen-decomposition entirely and executes in linear time,

and thus is scalable to large graphs.

Although the above sampling algorithms are efﬁcient and ef-

fective, they are all designed for undirected graphs, and cannot be

easily applied to directed graphs. One main challenge in directed

graph sampling is the inherent difﬁculty in deﬁning graph frequen-

cies, due to the asymmetric nature of the directed graphs’ variation

operators, e.g., adjacency and Laplacian matrices, Wand Ł. Asym-

metry means that the graph operator matrix may not be diagonaliz-

able (and thus eigenvectors cannot be easily obtained), and even if

it is, its eigenvalues can be complex, which are difﬁcult to interpret

(e.g., ordering of eigenvectors into frequencies from high to low is

not obvious). Though [6, 9] discussed in passing how their methods

can be adapted to directed graphs, frequency and bandlimitedness

notions are still not well understood on directed graphs.

To circumvent the above challenge, in this work, we formulate

a novel directed graph sampling problem using graph shift variation

(GSV) [20] with a solution that completely avoids matrix asymme-

try, and in so doing enable a variant of GDAS for fast sampling.

Speciﬁcally, we ﬁrst deﬁne GSV kŁrwxk2

2as a smoothness prior

for directed graph signal x∈RN, where Łrw is a random-walk

graph Laplacian for directed graph Gd. Using GSV as regularizer

to reconstruct signal xfrom samples y=Hx ∈RK, where H∈

{0,1}K×Nis a sampling matrix, the solution is x∗=C−1H>y,

with symmetric coefﬁcient matrix C=H>H+µŁ>

rw Łrw. To min-

imize the worst-case reconstruction error (E-optimality), the sam-

pling objective is to choose Hto maximize the smallest eigenvalue

λmin(C)of C. To mitigate eigen-decomposition entirely, we devise

a variant of previous GDAS to efﬁciently choose Hto maximize a

lower bound λ−

min(SCS−1)—smallest Gershgorin disc left-end of

a similarity transform of C—based on Gershgorin circle theorem

(GCT) [21]. Experimental results show that our sampling method

yields smaller signal reconstruction errors at a faster speed compared

arXiv:2210.14263v1 [eess.SP] 25 Oct 2022

to competing schemes. To the best of our knowledge, this is the ﬁrst

directed graph sampling algorithm in GSP free from explicit deﬁni-

tions of directed graph frequencies.

2. PRELIMINARIES

Consider a directed graph Gd= (V,E,W)with Nnodes Vand

directed edges E.Wis an adjacency matrix, where Wi,j ∈R+

is the positive weight of directed edge (i, j)if it exists in E. We

assume no self-loops, and thus Wi,i = 0,∀i. Denote by Dthe

diagonal out-degree matrix such that Di,i =PjWi,j . We assume

that each node has strictly positive degree, i.e.,Di,i >0,∀i; this

means that there are no sink nodes. Graph Laplacian matrix of the

directed graph is deﬁned as Ł ,D−W. The normalized adjacency

matrix is ¯

W=D−1W, and the random-walk graph Laplacian is

Łrw ,D−1Ł=I−¯

W. Finally, we assume that there exists at

least one node vsuch that there are directed paths from all other

nodes v0∈ V to node v. This assumption ensures that the rank of

the random-walk Laplacian matrix Łrw is N−1[22].

3. PROBLEM FORMULATION

We ﬁrst review a previously proposed smoothness prior—-graph

shift variation (GSV) [20]—-and use it to reconstruct a directed

graph signal given limited samples. We then formulate a di-

rected graph sampling problem given a deﬁned signal reconstruction

scheme.

3.1. Signal Reconstruction on a Directed Graph

Graph Shift Variation Prior. Denote by x∈RNa signal on a

directed graph Gd. An important assumption in GSP is that the signal

is smooth w.r.t. an underlying graph. For undirected graphs, there

exist different smoothness measures of a graph signal, such as GLR

[15] and graph total variation (GTV) [23]. However, for directed

graphs, because Laplacian Ł is asymmetric, smoothness priors like

GLR cannot be used directly. In this paper, we adopt GSV in [20] as

the smoothness measure of a signal xon directed graph Gd,i.e.,

S(x) = 



x−1

|λa

max(Ws)|Wsx



.(1)

Here, Wsis a graph shifting operator [24, 25], and it has the same

support as adjacency matrix W.λa

max(Ws)is the largest magnitude

eigenvalue of Ws, and |λa

max(Ws)|is the spectral radius of matrix

Ws.1/|λa

max(Ws)|is used for normalization. 1

|λa

max (Ws)|Wsx

shifts each node’s sample to its one-hop neighbors, and S(x)mea-

sures the difference between signal xand its shifted version.

In this work, we use the normalized adjacency matrix ¯

D−1Was the graph shift operator, since its largest eigenvalue is

λa

max(¯

W) = 1. Consequently, the GSV prior is deﬁned as

S(x) = 

x−¯

Wx

2

2=kŁrw xk2

2=x>Ł>

rw Łrwx.(2)

This GSV prior in (2) is similar to the left eigenvector random walk

graph Laplacian (LeRAG) regularizer in [18]. It is shown that the

smooth prior in (2) is insensitive to vertex degrees. Further, it is

shown [18] that GSV of a constant signal x=c1evaluates to

S(x) = 0, which is intuitive and important for imaging applications.

Signal Reconstruction using GSV Prior. Suppose that we obtain

Ksamples, y∈RK, of graph signal x∈RN, where K < N. We

aim to reconstruct signal x∗given observation y. To regularize this

under-determined problem, we employ GSV (2) as prior and solve

the following regularized optimization problem [20, 26]:

x∗= arg min

xkHx −yk2

2+µx>Ł>

rw Łrwx,(3)

where H∈ {0,1}K×Nis the sampling matrix, and µ > 0is a

weight parameter that trades off the ﬁdelity term with the GSV prior.

The optimal solution x∗to (3), which is quadratic and convex, can

be obtained by solving the following linear system

H>H+µŁ>

rw Łrwx∗=H>y.(4)

Note that both H>Hand Ł>

rw Łrw are positive semi-deﬁnite matrix.

For matrix Łrw, we have Łrw 1= (I−D−1W)1=1−1=

0. Thus, Span{1} ⊆ N ull(Łrw). With the assumption in Sec. 2

that there exists at least one node that can reach any other nodes

through directed paths, from Theorem 4.5 in [22], the dimension of

Null(Łrw )is 1. Thus, we have Null(Łrw ) = Span{1}. Note that

for x/∈Span{1}, we have x>H>Hx ≥0and x>Ł>

rw Łrwx>0.

For x∈Span{1}, say x=c1where cis a non-zero real scalar, we

have x>H>Hx >0and x>Ł>

rw Łrwx≥0. In summary, for any

x∈RN, we have x>(H>H+Ł>

rw Łrw)x>0, and thus, (H>H+

Ł>

rw Łrw)is a positive deﬁnite matrix and invertible. Consequently,

the unique optimal solution to (3) as well as (4) is

x∗=H>H+µŁ>

rw Łrw−1

H>y.(5)

Note that given the coefﬁcient matrix in (4) is symmetric, sparse, and

positive deﬁnite, x∗can be solved using conjugate gradient (CG)

[27] without performing any matrix inverse.

3.2. Directed Graph Sampling Problem

Observation ymay contain noise. Given a sampling budget K, to

minimize worst-case reconstruction error using reconstruction (5),

we adopt the E-optimality criterion [6, 16] to maximize the smallest

eigenvalue of coefﬁcient matrix H>H+µŁ>

rw Łrw. For notation

simplicity, we deﬁne diagonal matrix A,H>H, whose diagonal

entry Ai,i = 1 if node iis sampled and Ai,i = 0 otherwise. The

sampling problem is thus formulated as

max

Aλmin(A+µŁ>

rw Łrw)

s.t. Ai,i ∈ {1,0},∀i, tr(A) = K. (6)

The second constraint in (6) indicates that we can sample Knodes.

Note that optimization (6) is combinatorial in nature and NP-hard in

general. Next, we develop an efﬁcient algorithm for (6).

4. THE PROPOSED GDA-DIRECT METHOD

We ﬁrst review the Gershgorin disc alignment sampling (GDAS) al-

gorithm in [16]. We then derive a lower bound of the objective in (6)

and design an efﬁcient algorithm to solve (6) based on GDAS.

4.1. Gershgorin Disc Alignment Algorithm

The foundation of GDAS is Gershgorin Circle Theorem (GCT) [21].

Gershgorin disc Ψiof the i-th row of a real matrix Mis a cir-

cle on the complex plane, with center (Mi,i,0) and radius ri=

Pj6=i|Mi,j |. GCT states that all eigenvalues of Mreside inside the

union of Gershgorin discs of M. For a real symmetric matrix M

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

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

10 玖币 0人已下载

立即下载

摘要：

EFFICIENTDIRECTEDGRAPHSAMPLINGVIAGERSHGORINDISCALIGNMENTYuejiangLi?,H.VickyZhao?,GeneCheungy?Dept.ofAutomation,TsinghuaUniversity,Beijing,ChinayYorkUniversity,Toronto,CanadaABSTRACTGraphsamplingistheproblemofchoosinganodesubsetviasam-plingmatrixH2f0;1gKNtocollectsamplesy=Hx2RK,K

展开>> 收起<<

EFFICIENT DIRECTED GRAPH SAMPLING VIA GERSHGORIN DISC ALIGNMENT Yuejiang Li H. Vicky Zhao Gene Cheungy Dept. of Automation Tsinghua University Beijing China.pdf

共9页,预览2页

还剩页未读，继续阅读

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

EFFICIENT DIRECTED GRAPH SAMPLING VIA GERSHGORIN DISC ALIGNMENT Yuejiang Li H. Vicky Zhao Gene Cheungy Dept. of Automation Tsinghua University Beijing China

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: