1 Generative Models and Learning Algorithms for Core-Periphery Structured Graphs

2025-04-28 0 0 3.29MB 13 页 10玖币

侵权投诉

Generative Models and Learning Algorithms for

Core-Periphery Structured Graphs

Sravanthi Gurugubelli, Student Member, IEEE, and Sundeep Prabhakar Chepuri, Member, IEEE

Abstract—We consider core-periphery structured graphs,

which are graphs with a group of densely and sparsely connected

nodes, respectively, referred to as core and periphery nodes. The

so-called core score of a node is related to the likelihood of

it being a core node. In this paper, we focus on learning the

core scores of a graph from its node attributes and connectivity

structure. To this end, we propose two classes of probabilistic

graphical models: afﬁne and nonlinear. First, we describe afﬁne

generative models to model the dependence of node attributes

on its core scores, which determine the graph structure. Next,

we discuss nonlinear generative models in which the partial

correlations of node attributes inﬂuence the graph structure

through latent core scores. We develop algorithms for inferring

the model parameters and core scores of a graph when both the

graph structure and node attributes are available. When only

the node attributes of graphs are available, we jointly learn a

core-periphery structured graph and its core scores. We provide

results from numerical experiments on several synthetic and

real-world datasets to demonstrate the efﬁcacy of the developed

models and algorithms.

Index Terms—Core-periphery graphs, graphical models, graph

learning, structured graphs, topology inference.

I. INTRODUCTION

CORE-periphery structured graphs have densely connected

groups of nodes, called core nodes, and sparsely con-

nected groups of nodes, called periphery nodes. While the core

nodes are cohesively connected to the other core nodes and

are also reasonably well connected to the peripheral nodes,

the peripheral nodes are not well connected to each other

or to any core node in the graph. Core-periphery structured

graphs are ubiquitous and are extensively used to analyze

real-world networks such as social networks [1], trade and

transport networks [2], and brain networks [3], to name a few.

Identifying the core nodes in a network allows us to analyze

crucial processes in it. For instance, in brain networks, atypical

core-periphery brain dynamics are observed in subjects with

autism spectrum disorder [4]. In social networks [1] (contact

networks [5]), the most inﬂuential spreaders of information

(respectively, a disease) are usually the core nodes. An exam-

ple of a core-periphery structured social network of a subset

of 244 Twitter users [6] is shown in Fig. 1.

Given an adjacency matrix of a graph, its rows and columns

can be permuted to reveal the underlying core-periphery

structure. However, generating all the possible permutations

of its rows and columns to arrive at an adjacency matrix that

reveals the core-periphery structure is an NP-hard problem.

To this end, many heuristics that reveal the core-periphery

S. Gurugubelli and S.P. Chepuri are with the Department of ECE, Indian In-

stitute of Science, Bangalore, India. Email: {sravanthig;spchepuri}@iisc.ac.in

(a) (b)

Core

Periphery

Fig. 1. (a) A network with a core-periphery structure. The dark colored nodes

are the core nodes while the lighter ones form the periphery nodes. (b) Its

adjacency matrix with rows and columns ordered according to the decreasing

nodal core score.

structure from an adjacency matrix are available [7]–[12].

Another commonly used approach to identify the core nodes

in a graph is by learning the so-called core score of a node,

where the core score of a node is related to the likelihood of

that node belonging to the core part of the graph. In some

networks, such as trade, transport, or brain networks, the core

score of a node also depends on its spatial distance from the

other nodes [12]. Speciﬁcally, in such networks, a node that

is spatially far away from another node is very unlikely to

be connected to it. For the graph in Fig. 1(a), a permuted

adjacency matrix (permuted according to the rank-ordered core

scores) is shown in Fig. 1(b), wherein the dense entries in

the top left block correspond to the core-core connections in

the graph and the sparse entries in the bottom right block

correspond to the periphery-periphery connections.

In many real-world networks, we only have access to node

attributes, and the underlying graph might not always be avail-

able. For example, in a brain network, we usually have access

to functional magnetic resonance imaging (fMRI) data, but the

structural connectivity information is often unavailable. Node

attributes carry vital information that often complements the

information in the graph structure and can improve the quality

of the core score estimates. However, existing works [7]–[12]

rely only on the knowledge of the underlying graph and do not

use node attributes for inferring the core scores. Therefore, this

work proposes probabilistic models and algorithms to infer the

core scores in the following two cases, namely, (i)when both

the underlying graph structure and node attributes are available

and (ii)when only node attributes are available.

A. Relevant Prior Works

Existing works infer the core scores from a graph, i.e.,

from an adjacency matrix. In [7], correlation measures to

arXiv:2210.01489v1 [cs.LG] 4 Oct 2022

quantify how well a network approximates the ideal model of

a core-periphery structured graph are deﬁned, where the ideal

model consists of a core-core block that is fully connected,

a periphery-periphery block with no connections, and a core-

periphery part that is either fully connected or not connected

at all. These measures are then used to develop algorithms

to estimate the core scores. In [8], the core score vector is

learnt by maximizing the correlation measure from [7] with

a constraint that the core score vector is a shufﬂed version

of an N-dimensional vector whose entries are ﬁxed according

to a number of desired factors that effect the spread of the

core scores, such as the number of nodes in the core region

and the change in the core score from the core to peripheral

nodes. In [9], the edge weight of a node pair is modeled as

the product of its cores scores, and the core score vector is

obtained by minimizing the sum of the squared differences

between the known edge weights and the product of the core

scores of the related node pair, summed over all node pairs.

In [10], a recursive algorithm, called the k-core decomposition,

is proposed to iteratively partition a graph into nodes having

sparse and dense connections. In [11], an iterative algorithm

derived from a standard random walk model is proposed,

where the so-called persistence probability that denotes the

probability that a random walker starting from a certain node

in a sub-network of a network remains in that sub-network

in the next step is deﬁned. Then starting from a sub-network

containing a single node with the weakest connectivity, nodes

are iteratively added to the sub-network such that the increase

in persistence probability is minimal. The above mentioned

existing works, which we refer as, Rombach [8], MINRES [9],

k-cores [10], and Random-Walk [11] serve as the baseline

for the proposed methods.

When only node attributes are available and the underlying

graph structure is unknown, we ﬁrst need to learn the under-

lying graph. We may then infer the core scores using existing

methods. One of the standard approaches to infer graphs

from node attributes is graphical lasso, which solves an `1-

regularized Gaussian maximum log-likelihood problem [13]

to learn a sparse connectivity pattern underlying a Gaussian

graphical model. However, graphical lasso imposes a uniform

`1penalty on each edge and does not account for the core-

periphery structure in networks.

To summarize, when we have access to only node attributes

and the underlying graph is unavailable, the existing methods

cannot be used to estimate core scores. Furthermore, the exist-

ing works do not incorporate node attribute information while

inferring core scores. In this work, we propose generative

models and learning algorithms to address these limitations.

B. Main Results and Contributions

The main results and contributions of the paper are summa-

rized as follows.

•Generative Models: We propose probabilistic generative

models that relate core-periphery structured graphs to

their core scores and attributes of nodes to their re-

spective core scores through an afﬁne model. We re-

fer to these models as Graph-Attributes-Affine

(GA-Affine). In particular, we propose two models,

namely, GA-Affine-Bool and GA-Affine-Real,

to account for binary and real-valued node attributes,

respectively. Next, we propose nonlinear generative

models that, though not as simple as the afﬁne

models, incorporate information about spatial dis-

tances and capture any dependencies between node at-

tributes. Within the nonlinear models, we propose two

models, namely, Graph-Attributes-Nonlinear

(GA-Nonlinear) and Attributes-Only (AO)

to address two different cases, namely, both node at-

tributes and graph structure being available and only

the node attributes being available, respectively. Similar

to the GA-Affine model, the GA-Nonlinear model

assumes the graph is known. However, contrary to the

GA-Affine model, it establishes a nonlinear relation-

ship between the core scores and the node attributes.

On the other hand, the nonlinear AO model assumes

that the underlying graph is unknown and relates node

attributes to core scores through a latent graph structure.

In [14], which is a conference precursor of this work,

we proposed the AO model, which we extend to gener-

ative models that relate core scores to graphs and node

attributes in the paper.

•Algorithms: We infer core scores using both the graph

structure and the complementary information contained in

the node attributes whenever both are available by ﬁtting

one of the proposed models of Graph-Attributes

to the observed data. The problems formulated using

models GA-Affine-Bool and GA-Affine-Real

are non-convex in the core scores and model parame-

ters, which we solve by alternating minimization. With

GA-Nonlinear, the inference problem is a convex

problem in the core scores for which we propose a pro-

jected gradient ascent based solver. Next, when only node

attributes are available, we ﬁt data to the AO model to

simultaneously learn the unknown latent graph structure

and the core scores. The inference problem takes the form

of the graphical lasso problem. However, in contrast to

the standard graphical lasso, the `1regularization is not

uniformly applied on all the edges but is weighed accord-

ing to the latent core scores. We provide an alternating

minimization based solver to jointly learn the underlying

graph and the core scores.

We test the proposed algorithms on several synthetic and

real-world datasets. For synthetic datasets, we observe that

the core scores estimated by the proposed algorithms are the

closest to the groundtruth core scores, in terms of cosine sim-

ilarity, compared to those estimated by the existing methods

that consider only the graph structure. We also perform various

numerical experiments to show the ability of the proposed

algorithms to correctly identify the core parts of various real-

world datasets such as citation, organizational, social, and

transportation networks. Further, when the graph structure is

unavailable, we show that our method learns the core scores

along with the core-periphery structured graphs outperforming

graphical lasso. We also use as inputs the core scores and

graphs learnt using the algorithm obtained from the proposed

AO model to classify healthy individuals and individuals with

attention deﬁcit hyperactivity disorder (ADHD) using graph

neural networks when only the fMRI data of the subjects

is available and also illustrate the major differences in the

core and periphery regions of the two groups. Software

and data to reproduce the results in the paper is available

at https://github.com/SravanthiGurugubelli/CPGraphs.

C. Notation and Organization

Throughout the paper, boldface lowercase (uppercase) let-

ters denote column vectors (respectively, matrices). Operators

tr(.),(.)−1, and (.)Tstand for trace, inverse, and transpose

operations, respectively. INis the identity matrix of size

N×N.1mn and 0mn denote m×ndimensional matrices with

all ones and all zeros, respectively. The projection operator to

project a vector c= [c1, c2,··· , cN]T∈RNonto a constraint

set formed by the intersection of a hyperplane PN

i=1 ci=M

with Mbeing a positive constant and a rectangle c∈[0,1]N

is given by:

PCnc(t)o=P[0,1] nc(t)−λ∗1o,(1)

where λ∗∈Ris the solution to

φ(λ) = 1TP[0,1] {c−λ1} − M= 0.(2)

Since the function φ(λ)is a non-increasing function of λ,

the root of (2), denoted by λ∗, can be easily found using

simple techniques like the bisection method. Here, P[0,1] {a}

denotes the projection operator for projecting the vector a=

[a1, a2,··· , an]Tonto the rectangle a∈[0,1]Nand is given

by the component-wise operator

P[0,1] {a}k=









0, ak≤0,

ak,0≤ak≤1,

1, ak≥1.

The rest of the paper is organized as follows. In Section II,

we model the dependence of graph structures on core scores.

In Section III, we model the dependence of node attributes

on their respective core scores through afﬁne functions and

develop algorithms to infer core scores from both the graph

and its node attributes. In Section IV, we propose nonlinear

models for node attributes and develop algorithms to infer core

scores in the following two cases: when both node attributes

and graph are available and when only node attributes are

available. In Section V, we present results from several numer-

ical experiments to evaluate the proposed algorithms in terms

of their ability to correctly identify the core scores of several

synthetically generated and real-world networks. Finally, we

conclude the paper in Section VI.

II. MODELING CORE SCORES

Consider a weighted and undirected graph G={V,E},

where V={v1,···vN}is the vertex set with Nvertices

and Eis the edge set. The connectivity structure of Gis

captured in Θ∈RN×N, i.e., the (i, j)th entry of Θdenoted

by Θij is nonzero if nodes iand jare connected and is

zero otherwise. Let us denote the node attribute data as

X= [x1,x2,··· ,xd]∈RN×dwith the ith row of X

containing d-dimensional features of the entity associated to

the ith node of G. Let c= [c1, c2,··· , cN]T∈RN

+denote

the core score vector of a graph Gwith Nnodes, where the

ith entry ci∈[0,1] denotes the coreness value of node i. The

core score cidenotes the likelihood of node ibelonging to the

core part of the graph with ci= 1 denoting the certainty of

node ibelonging to the core part of the graph. We denote the

spatial distance between nodes iand jby dij .

In this section, we develop a model to relate the graph Θ

to the core scores of its nodes. Speciﬁcally, we model Θsuch

that it induces a sparsity pattern in graphs determined by the

core scores of its nodes and the spatial distances between the

nodes. The proposed coreness and position-aware probabilistic

model on Θis based on the following intuitions. Firstly,

the connections between nodes with large core scores are

dense, between nodes with large and small core scores are

relatively sparser, and between nodes with small core scores

are very sparse. Secondly, spatially distant nodes have sparse

connections between them.

Let us deﬁne a parameter, e, which determines the depen-

dence of Θij on spatial distances relative to the dependence on

core scores in the model. With a small constant , we model

Θij such that when the value ci+cj−elog(dij +)for any

two nodes iand jis large, Θij is large. When spatial distances

between nodes are not relevant or are not available, eis simply

set to zero. To satisfy the above mentioned requirements, we

model the entries of Θas Laplace random variables with

wij = 1 −ci−cj+elog(dij +)

being the inverse diversity parameter, which depends on the

latent variables ci,cj, and the spatial distances dij for i, j =

1,··· , N. In other words, the probability density function

(PDF) of Θparameterized by the latent core score vector cis

p(Θ;c) =

i,j=1

p(Θij ;ci, cj)

∝

i,j=1

exp (−λwij |Θij |),(3)

where λ > 0controls the dependence of Θon the core scores

and the spatial distances. For p(Θ;c)to be a valid probability

distribution, wij should be positive.

Throughout the paper, we employ the probabilistic model

for Θfrom (3), where we model Θij as a random variable

drawn from a Laplace distribution with inverse diversity

parameter wij . Now that we have a model that relates the

graph structure to the core scores, in what follows, we propose

probabilistic models to relate node attributes to the core scores.

We then propose algorithms to learn the core scores cwhen

both the graph Θand node attributes Xare available and when

only Xis available. We ﬁrst consider simple afﬁne models

to relate attributes of nodes to their respective core scores.

Although afﬁne models are simple, in some cases, the core

scores of different nodes might be dependent not just on their

respective node attributes but on the correlations between the

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

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

10 玖币 0人已下载

立即下载

摘要：

1GenerativeModelsandLearningAlgorithmsforCore-PeripheryStructuredGraphsSravanthiGurugubelli,StudentMember,IEEE,andSundeepPrabhakarChepuri,Member,IEEEAbstractWeconsidercore-peripherystructuredgraphs,whicharegraphswithagroupofdenselyandsparselyconnectednodes,respectively,referredtoascoreandperipheryn...

展开>> 收起<<

1 Generative Models and Learning Algorithms for Core-Periphery Structured Graphs.pdf

共13页,预览3页

还剩页未读，继续阅读

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

1 Generative Models and Learning Algorithms for Core-Periphery Structured Graphs

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: