Block-Structured Optimization for Subgraph Detection in Interdependent Networks Fei Jiey Chunpai Wangz Feng Chenx Lei Liy Xindong Wuk

2025-04-27 0 0 550.85KB 6 页 10玖币

Block-Structured Optimization for Subgraph

Detection in Interdependent Networks

Fei Jie∗†, Chunpai Wang‡, Feng Chen§, Lei Li∗†, Xindong Wu¶∗k

∗Key Laboratory of Knowledge Engineering with Big Data (Hefei University of Technology), Ministry of Education, Hefei, China.

†School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China.

‡Department of Computer Science, University at Albany – SUNY, Albany, NY, USA

§Erik Jonsson School of Engineering & Computer Science, The University of Texas at Dallas, Dallas, TX, USA

¶Mininglamp Academy of Sciences, Mininglamp Technologies, Beijing, China

kInstitute of Big Knowledge Science, Hefei University of Technology, Hefei, China

realfjie@gmail.com, cwang25@albany.edu, feng.chen@utdallas.edu, {lilei,xwu}@hfut.edu.cn

Abstract—We propose a generalized framework for block-

structured nonconvex optimization, which can be applied to

structured subgraph detection in interdependent networks, such

as multi-layer networks, temporal networks, networks of net-

works, and many others. Speciﬁcally, we design an effective,

efﬁcient, and parallelizable projection algorithm, namely Graph

Block-structured Gradient Projection (GBGP), to optimize a gen-

eral non-linear function subject to graph-structured constraints.

We prove that our algorithm: 1) runs in nearly-linear time on the

network size; 2) enjoys a theoretical approximation guarantee.

Moreover, we demonstrate how our framework can be applied

to two very practical applications and conduct comprehensive

experiments to show the effectiveness and efﬁciency of our

proposed algorithm.

Index Terms—subgraph detection, sparse optimization, inter-

dependent networks

I. INTRODUCTION

Subgraph detection in network data has aroused many

interests in recent years because of many real-world ap-

plications, such as disease outbreak detection [1], intrusion

detection in computer networks , event detection in social

networks [2], congestion detection in trafﬁc networks, etc.

However, most of existing works investigate the subgraph

mining on static, isolated networks, and such a problem

involving interdependent networks has not been well studied.

Interdependent networks are comprised of multiple networks

{G1,G2,...,Gk, . . . }and edges E0interconnected among

networks, where Gk= (Vk,Ek).Vkand Ekare vertex set

and edge set of kth network Gkrespectively. Some nodes in

different networks exhibit node-node dependencies that could

be captured by explicit edges or implicit correlation on node

attributes (implicit edges). For instance, a temporal network

can be viewed as multiple temporal-dependent networks, in

which each network represents a snapshot of the temporal net-

work at a speciﬁc time stamp, where current node’s attributes

depend on attributes in the previous time-stamp implicitly [3]

(Figure 1a). A web-scale social network comprised of many

communities is a network of networks (a trivial interdependent

networks) with explicit connections, where communities can

The ﬁrst two authors contributed equally to this research.

T=1 T=2 T=3

(a) Temporal Networks (b) Network of Networks

Fig. 1: Examples of Interdependent Networks. (a) Temporal Net-

works: black dashed lines capture implicit temporal dependencies or

consistencies. (b) Network of Networks: black solid lines are bridges

across networks.

be viewed as small networks or blocks that interconnect with

each other (Figure 1b).

Subgraph detection in multiple interdependent networks can

be formulated as a block-structured optimization problem with

multiple topological constraints on blocks,

min

S1⊆V1,...,SK⊆VKF(S1,··· , SK)

s.t. Sksatisﬁes a pre-deﬁned topological constraint,

(1)

where Fis a user-speciﬁed cost function regularized by block

dependencies, for example, Fcould be f(S1,··· , SK) +

g(S1,··· , SK), where fis used to capture signals in inter-

dependent networks and gmodels the dependencies between

networks. Skis a subset of nodes in kth network Gk,k=

1, ..., K. Vanilla subgraph detection problem is a special case

of problem (1) when number of networks (blocks) is 1.

To the best of our knowledge, most of related studies on

subgraph detection in interdependent networks only focus on

speciﬁc applications and are lack of generality. Furthermore,

they are heuristic-driven with no theoretical guarantee. There-

fore, we propose a general framework that leverages graph

structured sparsity model [4] and block coordinate descent

method [5] to solve this problem which can be modeled as

a block-structured optimization problem.

The contributions of our work are summarized as follows:

arXiv:2210.02702v1 [cs.LG] 6 Oct 2022

•Design of an efﬁcient and scalable approximation al-

gorithm. We propose a novel generic framework, namely,

Graph Block-structured Gradient Projection, for block struc-

tured nonconvex optimization, which can be used to approx-

imately solve a broad class of subgraph detection problems

in interdependent networks in nearly-linear time.

•Theoretical guarantees. We present a theoretical analysis

of the proposed GBGP algorithm and show that it enjoys a

good convergence rate and a tight error bound on the quality

of the detected subgraph.

•Two practical applications with comprehensive exper-

iments. We demonstrate how our framework can be ap-

plied to two practical applications: 1) anomalous evolving

subgraph detection; 2) subgraph detection in network of

networks. We conduct comprehensive experiments on both

synthetic and real networks to validate the effectiveness and

efﬁciency of our proposed algorithm.

II. METHODOLOGY

A. Problem Formulation

First, we reformulate the combinatorial problem (1) in dis-

crete space as an nonconvex optimization problem in continu-

ous space. Interdependent networks can be viewed as one large

network G= (V,E), where V={1,··· , N}could be cut into

{V1,··· ,VK}and Ecould be split into {E0,E1,··· ,EK}.

Each pair of (Vk,Ek)forms a small network Gkfor k=

1,··· , K, and E0are edges interconnected among different

small networks. Edges in E0should be treated differently with

the edges in each Ek, since they models the dependencies

among different networks. W= [w1,··· ,wN]∈RP×Nis

the feature matrix, and wi∈RPis the feature vector of vertex

i,i∈V.Nk=|Vk|is the size of the subset of vertices Vk.

The general subgraph detection problem in interdependent

networks can be formulated as following general block-

structured optimization problem with topological constraints:

min

x=(x1,...,xK)F(x1,...,xK)

s.t.supp(xk)∈M(Gk, s), k = 1,··· , K

(2)

where the vector x∈RNis partitioned into multiple disjoint

blocks x1∈RN1,··· ,xK∈RNK, and xkare variables

associated with nodes of network Gk. The objective function

F(·)is a continuous, differentiable and convex function, which

will be deﬁned based on the feature matrix W. In addition,

F(·)could be decomposed as f(x) + g(x), where fis used

to capture signals on nodes in interdependent networks and g

models the dependencies between networks. supp(xk)denotes

the support set of vector xk,M(Gk, s)denotes all possible

subsets of vertices in Gkthat satisfy a certain predeﬁned

topological constraint. One example of topological constraint

for deﬁning M(Gk, s)is connected subgraph, and we can

formally deﬁne it as follows:

M(Gk, s):={S|S⊆Vk;|S| ≤ s;Gk

Sis connected.}(3)

where sis a predeﬁned upperbound size of S,S⊆Vk,

and Gk

Srefers to the induced subgraph by a set of vertices

S. The topological constraints can be any graph structured

sparsity constraints on Gk

S, such as connected subgraphs,

dense subgraphs, compact subgraphs [6]. Moreover, we do not

restrict all supp(x1),··· ,supp(xK)satisfying an identical

topological constraint.

Algorithm 1 Graph Block-structured Gradient Projection

Input:{G1,...,GK}

Output:x1,t,··· ,xK,t

Initialization,i= 0,xk,i =initial vectors, k=1,. . . , K

1: repeat

2: for k= 1,··· , K do

3: Γxk=H(∇xkF(x1,i,...,xK,i))

4: Ωxk= Γxk∪supp(xk,i)

5: end for

6: Get (bi

x1,...,bi

xK)by solving problem (6)

7: for k= 1,··· , K do

8: Ψi+1

xk=T(bi

xk)

9: xk,i+1 = [bi

xk]Ψi+1

10: end for

11: i=i+ 1

12: until PK

k=1 

xk,i+1 −xk,i

≤

13: C= (Ψi

x1,...,Ψi

xk)

14: return (x1,i,··· ,xK,i), C

B. Head and Tail Projections on M(G, s)

•Tail Projection (T(x)): is to ﬁnd a subset of nodes S⊆V

such that

kx−xSk2≤cT·min

S0∈M(G,s)kx−xS0k2,(4)

where cT≥1, and xSis a restriction of xon Ssuch that:

(xS)i= (x)iif i∈S, and (xS)i= 0 otherwise. When

cT= 1,T(x)returns an optimal solution to the problem:

minS0∈M(G,s)kx−xS0k2. When cT>1,T(x)returns an

approximate solution to this problem with the approximation

factor cT.

•Head Projection (H(x)): is to ﬁnd a subset of nodes S

such that

kxSk2≥cH·max

S0∈M(G,s)kxS0k2,(5)

where cH≤1. When cH= 1,H(x)returns an optimal

solution to the problem: maxS0∈M(G,s)kxS0k2. When cH<

1,H(x)returns an approximate solution to this problem

with the approximation factor cH.

Although the head and tail projections are NP-hard when

we restrict cT= 1 and cH= 1, these two projections can

still be implemented in nearly-linear time when approximated

solutions with cT>1and cH<1are allowed.

C. Algorithm Details

We propose a novel Graph Block-structured Gradient Pro-

jection, namely GBGP, to approximately solve problem (2)

in nearly-linear time on the network size. The key idea is to

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

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

10 玖币 0人已下载

立即下载

摘要：

Block-StructuredOptimizationforSubgraphDetectioninInterdependentNetworksFeiJiey,ChunpaiWangz,FengChenx,LeiLiy,XindongWu{kKeyLaboratoryofKnowledgeEngineeringwithBigData(HefeiUniversityofTechnology),MinistryofEducation,Hefei,China.ySchoolofComputerScienceandInformationEngineering,HefeiUniversityof...

展开>> 收起<<

Block-Structured Optimization for Subgraph Detection in Interdependent Networks Fei Jiey Chunpai Wangz Feng Chenx Lei Liy Xindong Wuk.pdf

共6页,预览2页

还剩页未读，继续阅读

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

Block-Structured Optimization for Subgraph Detection in Interdependent Networks Fei Jiey Chunpai Wangz Feng Chenx Lei Liy Xindong Wuk

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: