Nodal statistics-based equivalence relation for graph collections Lucrezia Carboni12Michel Dojat2Sophie Achard1 1Univ. Grenoble Alpes CNRS Inria Grenoble INP LJK 38000 Grenoble France

2025-05-02 0 0 997.56KB 15 页 10玖币

侵权投诉

Nodal statistics-based equivalence relation for graph collections

Lucrezia Carboni1,2Michel Dojat2Sophie Achard1

1Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LJK, 38000 Grenoble, France

2Univ. Grenoble Alpes, Inserm, U1216, Grenoble Institut Neurosciences, GIN, 38000 Grenoble, France

(Dated: October 4, 2022)

Node role explainability in complex networks is very diﬃcult, yet is crucial in diﬀerent application

domains such as social science, neurosciences or computer science. Many eﬀorts have been made on

the quantiﬁcation of hubs revealing particular nodes in a network using a given structural property.

Yet, in several applications, when multiple instances of networks are available and several structural

properties appear to be relevant, the identiﬁcation of node roles remains largely unexplored. Inspired

by the node automorphically equivalence relation, we deﬁne an equivalence relation on graph nodes

associated with any collection of nodal statistics (i.e. any functions on the node-set). This allows us

to deﬁne new graph global measures: the power coeﬃcient, and the orthogonality score to evaluate

the parsimony and heterogeneity of a given nodal statistics collection. In addition, we introduce

a new method based on structural patterns to compare graphs that have the same vertices set.

This method assigns a value to a node to determine its role distinctiveness in a graph family.

Extensive numerical results of our method are conducted on both generative graph models and

real data concerning human brain functional connectivity. The diﬀerences in nodal statistics are

shown to be dependent on the underlying graph structure. Comparisons between generative models

and real networks combining two diﬀerent nodal statistics reveal the complexity of human brain

functional connectivity with diﬀerences at both global and nodal levels. Using a group of 200 healthy

controls connectivity networks, our method computes high correspondence scores among the whole

population, to detect homotopy, and ﬁnally quantify diﬀerences between comatose patients and

healthy controls.

Keywords: graph comparison; node roles detection; human brain functional connectivity.

I. INTRODUCTION

In several application scenarios which focus on complex

network studies, being able to determine node roles has

proven to be relevant [1–5]. Indeed, the notion of node

roles has been introduced in social science structural the-

ory [6] with at least two diﬀerent conceptions: structural

equivalence and structural isomorphism. According to

the former, nodes are equivalent if they share exactly the

same neighbors. For the latter, nodes are equivalent if

there exists an automorphism which maps the ﬁrst node

to the second and vice versa. In this work, we consider

this latter conception and identify the node role with its

structural equivalence class.

Recently, node roles analysis has been applied to vari-

ous application domains such as web graphs [7], techno-

logical or biological networks [8]. Diﬀerent algorithms

have been proposed to detect structural equivalence

classes in a single network by evaluating similarity met-

rics among nodes [9–11].

When examining a network collection deﬁned on the

same node-set, node role detection can provide meaning-

ful information for collection characterization, possibly

revealing a speciﬁc nodal partitioning. Indeed, in many

real-world applications, the available graph set can po-

tentially be characterized by speciﬁc node role classes

[12–16]. However, while many graph comparison metrics

already exist [17, 18], there is no evidence of a method

for comparing them, moreover, none of them directly ad-

dress the detection of diﬀerences at the nodal level.

This work has been motivated by our interest in hu-

man brain functional connectivity networks. In such net-

works, node organization has proven to be critical, for in-

stance in consciousness states diﬀerentiation [19]. How-

ever, while current methods allow to discriminate brain

networks under various pathological conditions [20, 21],

interpretation and explanation of the exhibited diﬀer-

ences between graphs at the nodal level remain diﬃcult.

The contributions of this work are then fourfold. First,

we deﬁne a structural equivalence relation on a graph

node-set based on nodal statistics (any functions on the

node-set). The proposed deﬁnition allows determining

node role classes according to statistics values. The main

innovation of this deﬁnition is given by the possibility of

identifying the graph structural pattern based on an orig-

inal combination of as many statistics as desired. Second,

we deﬁne two global measures of a statistics set which

determine parsimony and heterogeneity of its elements.

These measures only depend on the graph structure and

can be used for statistics selection or graph complexity

evaluation [22]. Third, we propose to compare graphs

with the same vertices according to their structural pat-

terns similarity. Indeed, thanks to the identiﬁcation of

node classes, we can compare diﬀerent graph instances

throughout the evaluation of the similarity of their struc-

tural patterns. Finally, we propose a framework to de-

termine node categories in a network group which allows

to characterize the group at a nodal level and to discrim-

inate nodes according to their role.

arXiv:2210.01053v1 [q-bio.NC] 3 Oct 2022

2 1

1 6

L C D I M

A B

E F

G H

A B

C E

F G

- nodes A-I share their roles with

other nodes in both graphs

- node L has a speciﬁc role in the

two graphs

- role of node M depends on graph

instance

the structural pattern is similar in the two graphs

(b) COMPARISON AT GLOBAL LEVEL BASED ON GRAPH STRUCTURAL PATTERNS

(a) SINGLE GRAPH STRUCTURAL PATTERN

IDENTIFICATION BASED ON DEGREE STATISTICS

Percentage of participation in non-trivial classes

A I

FIG. 1. Global comparison and nodal characterization of graphs: (a) structural patterns associated with the same statistics

are determined on the graphs, (b) the structural patterns are matched to compute a similarity value, (c) nodal participation

in non-trivial classes is obtained for nodal characterization.

II. STRUCTURAL EQUIVALENCE FOR A

SINGLE UNDIRECTED UNWEIGHTED GRAPH

We propose to identify the graph structural pattern

with the equivalence classes of a newly deﬁned equiva-

lence relation. The traditional deﬁnition identiﬁes two

nodes as automorphically equivalent if it exists a node

permutation preserving the adjacency matrix (an auto-

morphism) which maps the ﬁrst node to the second and

vice versa [23].

We deﬁne the structural equivalence relation as the union

of many equivalence relations, each one associated with

a single nodal statistics on the graph. When we refer

to nodal statistics, we consider any function on the node

set s:V → s(V) which is a function of the adjacency

matrix, i.e. node degree, clustering coeﬃcient of a node,

centrality measures, etc. We observe that for every pair

of automorphically equivalent nodes u, v ∈ V, any nodal

statistics sis preserved. Therefore, we propose to deﬁne

an equivalence relation ∼s, associated with a statistics s,

on the nodes set Vof a graph as follows:

v∼su⇐⇒ s(u) = s(v).(1)

For a nodal statistics having as s(V) a dense and con-

tinuous subset of R, the equivalence is deﬁned up to a

ﬁxed positive small :v∼su⇐⇒ |s(u)−s(v)| ≤ 

(Supplementary Material (SM) Fig. 11 ). As ∼sis an

equivalence relation on V, it is possible to ﬁnd its induced

partition Pon V,

Ps=V

∼s

={[a]l,∼s∀l∈s(V)},(2)

which deﬁnes the structural pattern of Gassociated with

the statistics s, and whose elements are the classes of

equivalence [a]l,∀l∈s(V),

[a]l,∼s= [a] = {b∈ V|a∼sb⇐⇒ s(a) = s(b) = l}.

(3)

A necessary condition for two nodes to be automorphi-

cally equivalent is to belong to the same equivalence class.

Subsequently, we extend the equivalence relation associ-

ated with a statistics to any statistics collection S=

{si}i=1,..,n, requiring that:

a∼Sb⇐⇒ a∼s1b, a ∼s2b, . . . , a ∼snb. (4)

Again, we can determine PS={[a]∼S}the induced par-

tition by ∼Son Vas the intersection of each class of the

considered {si}i=1,..,n. A visualization of the partitions

associated with degree statistics is shown in Fig. 1 (a).

Since the automorphically equivalence relation pre-

serves any nodal statistics, the nodal statistics-based

equivalence relation associated with an inﬁnity collection

retrieves the automorphically equivalence. However, a

ﬁnite nodal statistics collection with this property may

also exist. We propose to compare statistics collection

according to new deﬁned global graph parameters which

measure respectively parsimony and heterogeneity of its

elements. These global parameters depend on the graph

structure.

Given PS, one can compute exactly the number of eligi-

ble automorphisms that map nodes into the same equiv-

alence class, as it is computed below. Therefore, for each

statistics collection on a graph G, we can estimate how

many permutations are prevented from being tested as

being adjacency preserving in a brute force approach.

We introduce the power coeﬃcient (PC) of a set Sfor a

graph G= (G,E)

PCG(S) = log #{permutations preserving PS}

#{permutations of V} (5)

with

#{permutations preserving PS}=Y

o∈PS

|o|!

#{permutations of V} =|V|!.

The value |V|!e−PC corresponds to an upper bound of the

number of automorphisms of G. Indeed, PC is increasing

when more nodal statistics are combined together (SM,

Fig. 7). In the special case in which the permutations

preserving PScan be identiﬁed with the automorphisms

of G, PC can be interpreted as entropy of the network

ensemble [22] having Gtopology (SM, VII). In all other

cases, PC encodes the amount of information given by S

on the structure of Gand it is a parsimony measure for

Since PC takes values in [0,log 1

|V|![, with an upper bound

strictly depending on the number of nodes, we propose a

normalized version of PC, c

PC ∈[0,1] :

PCG(S) = PCG(S)

log |V|!(6)

= 1 −log #{permutations preserving PS}

log #{permutations of V} (7)

The higher the c

PC, the more the collection of statis-

tics Scapture the heterogeneity of nodal structural roles

in G. Indeed, for a vertex-transitive graphs (i.e. all

nodes are automorphically equivalent) c

PCG(S) = 0 for

all nodal statistics S, while if it exists a collection ¯

Ss.t.

PCG(¯

S) = 1 then the graph Gdoes admit non-trivial au-

tomorphisms.

Hence, we introduce the notion of perfectly orthogonal

statistics for heterogeneity evaluation of a collection ele-

ments. First, two nodal statistics are said to be perfectly

orthogonal if their union-associated equivalent relation

induces the trivial partition: all nodes belong to a sin-

gle element set. Next, we extend the deﬁnition to any

nodal statistics set: a nodal statistics collection is said to

be perfectly orthogonal if its induced partition is trivial.

An orthogonality measure for a given nodal statistics set

on a graph can be assessed by computing the number of

nodes in non-trivial classes on its associated partition:

OG(S) = |{v∈ V s.t. #[v]∼S6= 1}|

|V| (8)

OG(S) is the ratio between the number of nodes in non-

trivial classes and the total number of vertices and cor-

responds to an orthogonality score. By deﬁnition, Sis

perfectly orthogonal if and only if OG(S) = 0.

III. STRUCTURAL EQUIVALENCE FOR

GRAPH COLLECTIONS

A. Structural pattern comparison

Graphs that have the same node set can be compared

by evaluating the correspondence between their struc-

tural patterns. The node set constraint can be easily cir-

cumvented when two graphs do not share all the nodes,

by including all nodes to the graphs vertices set and al-

lowing the network to be composed of more connected

components. Indeed, each network can be seen as the

union of one strongly-connected component with as many

single disconnected vertices as needed.

We propose to compare structural patterns as follows.

Let G,G0be two graphs having same vertices Vand let S

be a statistics collection whose associated partitions are

PS, P 0

Son G,G0respectively. Given bijective mapping

from PS, P 0

Sto an initial segment of the natural numbers

as enumerations, let c(vi), c0(vi) be the enumeration of

the classes of vi, the correspondence structural pattern

score between G,G0is deﬁned as:

C(G,G0) = max

π∈Π

|V|

i=1

X(π(c(vi)) = c0(vi)) (9)

where Π is the set of all coupling between the elements

in PSand the elements in P0

Sand Xis the indicator

function.

A possible implementation of C(G,G0) in polynomial time

is given by the Hungarian algorithm ([24]) for assignment

problems with has a complexity O(max{|PS|,|P0

S|}3)

which in the worst case equals O(|V|3).

The correspondence structural pattern score can be

applied for two diﬀerent purposes: to evaluate structural

pattern similarity between two graphs (Fig. 1 (b)) or to

evaluate the similarity of structural patterns associated

with diﬀerent statistics collection on the same graph.

Since at least one class of PSshares one element with one

of the classes in P0

S,C(G,G0)≥1

|V| . As a consequence,

even perfectly orthogonal statistics set of a graph can

exhibit a correspondence pattern score higher than zero

(SM Fig. 8 (c)).

If for every class in PSthere exists one class of P0

having all and only its elements, then PS=P0

Sand

C(G,G0) = 1. The opposite is also true: same par-

titions determine a correspondence structural pattern

score equals to 1.

More general properties of the deﬁned global measures

can be found in the SM VII.

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

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

10 玖币 0人已下载

立即下载

摘要：

Nodalstatistics-basedequivalencerelationforgraphcollectionsLucreziaCarboni1;2MichelDojat2SophieAchard11Univ.GrenobleAlpes,CNRS,Inria,GrenobleINP,LJK,38000Grenoble,France2Univ.GrenobleAlpes,Inserm,U1216,GrenobleInstitutNeurosciences,GIN,38000Grenoble,France(Dated:October4,2022)Noderoleexplainabilityi...

展开>> 收起<<

Nodal statistics-based equivalence relation for graph collections Lucrezia Carboni12Michel Dojat2Sophie Achard1 1Univ. Grenoble Alpes CNRS Inria Grenoble INP LJK 38000 Grenoble France.pdf

共15页,预览3页

还剩页未读，继续阅读

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

Nodal statistics-based equivalence relation for graph collections Lucrezia Carboni12Michel Dojat2Sophie Achard1 1Univ. Grenoble Alpes CNRS Inria Grenoble INP LJK 38000 Grenoble France

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: