Reciprocity in Directed Hypergraphs Measures Findings and Generators Sunwoo Kim1 Minyoung Choe1 Jaemin Yoo3 and Kijung Shin12

2025-04-29 0 0 1.43MB 38 页 10玖币
侵权投诉
Reciprocity in Directed Hypergraphs: Measures, Findings, and
Generators
Sunwoo Kim∗1, Minyoung Choe†1, Jaemin Yoo‡3, and Kijung Shin§1,2
1Kim Jaechul Graduate School of AI, KAIST
2School of Electrical Engineering, KAIST
3Heinz College of Information Systems and Public Policy, Carnegie Mellon University
Abstract
Group interactions are prevalent in a variety of areas. Many of them, including email exchanges,
chemical reactions, and bitcoin transactions, are directional, and thus they are naturally modeled as
directed hypergraphs, where each hyperarc consists of the set of source nodes and the set of destination
nodes. For directed graphs, which are a special case of directed hypergraphs, reciprocity has played a key
role as a fundamental graph statistic in revealing organizing principles of graphs and in solving graph
learning tasks. For general directed hypergraphs, however, even no systematic measure of reciprocity has
been developed.
In this work, we investigate the reciprocity of 11 real-world hypergraphs. To this end, we first introduce
eight axioms that any reasonable measure of reciprocity should satisfy. Second, we propose HyperRec, a
family of principled measures of hypergraph reciprocity that satisfy all the axioms. Third, we develop
FastHyperRec, a fast and exact algorithm for computing the measures. Fourth, using them, we examine
11 real-world hypergraphs and discover patterns that distinguish them from random hypergraphs. Lastly,
we propose ReDi, an intuitive generative model for directed hypergraphs exhibiting the patterns.
1 Introduction
Beyond pairwise interactions, understanding and modeling group-wise interactions in complex systems
have recently received considerable attention [Benson et al., 2018a, Comrie and Kleinberg, 2021, Do
et al., 2020, Kook et al., 2020, Lee et al., 2021]. A hypergraph, which is a generalization of a graph, has
been used widely as an appropriate abstraction for such group-wise interactions. Each hyperedge in a
hypergraph is a set of any number of nodes, and thus it naturally represents a group-wise interaction.
Many group-wise interactions are directional, and they are modeled as a directed hypergraph, where
each hyperarc consists of the set of source nodes and the set of destination nodes. Examples of directional
group-wise interactions include email exchanges (from senders to receivers), chemical reactions [Yadati
et al., 2020], road networks [Luo et al., 2022], and bitcoin transactions [Ranshous et al., 2017]; and they
are modeled as directed hypergraphs for various applications, including metabolic-behavior prediction
[Yadati et al., 2020] and traffic prediction [Luo et al., 2022]. See Figure 1 for an example of hypergraph
modeling.
Reciprocity [Newman et al., 2002, Garlaschelli and Loffredo, 2004], which quantifies how mutually
nodes are linked, has been used widely as a basic statistic of directed graphs, which are a special case of
directed hypergraphs where every arc has exactly one source node and one destination node. Reciprocity
increase understanding of a graph, especially potential organizing principles of it, and has proved useful
for various tasks, including trust prediction [Nguyen et al., 2010], persistence prediction [Hidalgo and
Rodr´ıguez-Sickert, 2008], anomaly detection [Akoglu et al., 2012], and analysis of the spread of a computer
virus through emails [Newman et al., 2002].
∗kswoo97@kaist.ac.kr
†minyoung.choe@kaist.ac.kr
‡jaeminyoo@cmu.edu
§kijungs@kaist.ac.kr
1
arXiv:2210.05328v3 [cs.SI] 9 Jul 2023
Nodes (Authors) Head Sets and Tail Sets (Papers)
Paper 𝑻𝟏by 𝒗𝟓& 𝒗𝟔
Paper 𝑯𝟏by 𝒗𝟏& 𝒗𝟐
Paper 𝑻𝟐by 𝒗𝟐, 𝒗𝟑, & 𝒗𝟒
Paper 𝑯𝟐by 𝒗𝟔, 𝒗𝟕, & 𝒗𝟖
Paper 𝑻𝟑by 𝒗𝟕& 𝒗𝟖
Paper 𝑯𝟑by 𝒗𝟒
Hyperarcs (Papers)
𝒆𝟏: 𝑻𝟏cites 𝑯𝟏
𝒆𝟐: 𝑻𝟐cites 𝑯𝟐
𝒆𝟑: 𝑻𝟑cites 𝑯𝟑
𝒗𝟏, ⋯, 𝒗𝟖
(a) Example Citation Dataset
𝒆𝟏𝒆𝟐𝒆𝟑
𝒗𝟏𝒗𝟐𝒗𝟑𝒗𝟒
𝒗𝟓𝒗𝟔𝒗𝟕𝒗𝟖
(b) Model
Figure 1: A citation dataset modeled as a directed hypergraph with 8 nodes and 3 hyperarcs. Nodes
correspond to authors. Hyperarcs correspond to citations. The head set and tail set of each hyperarc
correspond to sets of papers.
However, reciprocity has remained unexplored for directed hypergraphs, and to the best of our knowl-
edge, no principled measure of reciprocity has been defined for directed hypergraphs. One straightforward
approach is to first convert a directed hypergraph into an ordinary directed graph via clique expansion and
then calculate standard reciprocity on the ordinary graph, as suggested in [Pearcy et al., 2014]. However,
clique expansion may incur considerable information loss [Yadati et al., 2020, Dong et al., 2020, Yoon
et al., 2020]. Thus, multiple directed hypergraphs whose reciprocity should differ, if they are determined
by a proper measure, may become indistinguishable after being clique-expanded.
In this work, we investigate the reciprocity of real-world hypergraphs based on the first principled
notion of reciprocity for directed hypergraphs. Our contributions toward this goal are summarized as
follows:1
•
Principled Reciprocity Measure: We design HyperRec, a family of probabilistic measures of
hypergraph reciprocity. We prove that HyperRec satisfy eight axioms that any reasonable measure of
hypergraph reciprocity should satisfy, while baseline measures do not.
•
Fast and Exact Search Algorithm: The size of search space for computing HyperRec is exponential
in the number of hyperarcs. We develop FastHyperRec, a fast and exact algorithm for computing
HyperRec.
•
Observations in Real-world Hypergraphs: Using HyperRec and FastHyperRec, we investigate
11 real-world directed hypergraphs, and discover three reciprocal patterns pervasive in them, which are
verified using a null hypergraph model.
•
Realistic Generative Model: To confirm our understanding of the patterns, we develop ReDi, a
directed-hypergraph generator based on simple mechanisms on individual nodes. Our experiments
demonstrate that ReDi yields directed hypergraphs with realistic reciprocal patterns.
For reproducibility, the code and data are available at https://github.com/kswoo97/hyprec.
In Section 2, we discuss preliminaries and related work. In Section 3, we propose a family of measures
of hypergraph reciprocity with a computation algorithm. In Section 4, we discuss reciprocal patterns of
real-world directed hypergraphs. In Section 5, we propose a generative model for directed hypergraphs.
Lastly, we offer a conclusion in Section 6.
1
This work is an extended version of [Kim et al., 2022], which was presented at the 22nd IEEE International Conference on
Data Mining (ICDM 2022). In the extended version, we introduce several theoretical extensions: (a) generalized versions of
the axioms in Section 3.1 and a proof of Theorem 1 for the generalized versions (Appendix A), (b) seven baseline hypergraph
reciprocity measures (Section 3.3), (c) a proof that none of the baseline measures satisfies all the axioms (Appendix B), and (d)
proofs of Theorem 2 and Corollary 1 (Appendix A). In addition, we conduct additional experiments regarding (a) the efficiency
of FastHyperRec (Figure 4 and Table 3 in Section 3.4), (b) the statistical significance of Observation 1 (Table 8 in Section 4.2),
(c) the robustness of HyperRec with respect to the choice of
α
(Tables 6 and 9 in Section 4.2), and (d) the verification of
Observation 2 in 12 more real and synthetic hypergraphs (Figure 5 in 4.2 and Figure 7 in Section 5.2). At last, we provide one
additional reciprocal pattern in real-world hypergraph (Observation 3: Figure 6 in Section 4.2) and verify whether ReDi can
reproduce this pattern.
2
Table 1: Frequently-used symbols.
Notation Definition
G= (V, E) hypergraph with nodes Vand hyperarcs E
ei=⟨Hi, Ti⟩hyperarc (or a target arc)
Hi, Tihead set and tail set of a hyperarc ei
Ri={e′
1,· · · , e′
|Ri|}reciprocal set of a hyperarc ei(see Section 3.1 for details)
r(ei, Ri) reciprocity of a target arc eiwith a reciprocal set Ri
r(G) reciprocity of a hypergraph G
din(v), dout(v) in-degree and out-degree of a node v
|A|cardinality of a set A(i.e., number of elements in A)
2 Basic Concepts and Related Work
In this section, we introduce some basic concepts and review related studies. See Table 1 for frequently-used
symbols.
2.1 Basic Concepts
Adirected hypergraph
G
= (
V, E
) consists of a set of nodes
V
=
{v1,· · · , v|V|}
and a set of hyperarcs
E
=
{e1,· · · , e|E|} ⊆ {⟨H, T ⟩
:
H⊆V, T ⊆V}
. For each hyperarc
ei
=
⟨Hi, Ti⟩ ∈ E
,
Hi
indicates the
head set and
Ti
indicates the tail set. In Figure 1, the hyperarc
e1
=
⟨H1, T1⟩ ∈ E
is represented as
an arrow that heads to
H1
=
{v1, v2}
from
T1
=
{v5, v6}
. It is assumed typically and also in this work
that, in every hyperarc, the head set and the tail set are disjoint (i.e.,
Hi∩Ti
=
∅,∀i
= 1
,· · · ,|E|
). The
in-degree
din
(
v
) =
|{ei∈E
:
v∈Hi}|
of a node
v∈V
is the number of hyperarcs that include
v
as a
head. Similarly, the out-degree
dout
(
v
) =
|{ei∈E
:
v∈Ti}|
of
v∈V
is the number of hyperarcs that
include vas a tail.
From now on, we will use the term hypergraph to indicate a directed hypergraph and use the term
undirected hypergraph to indicate an undirected one. We will also use the term arc to indicate a hyperarc
when there is no ambiguity.
2.2 Related Work
Reciprocity of Directed Graphs:
Reciprocity of directed graphs (i.e., a special case of directed hy-
pergraphs where all head sets and tail sets are of size one) is a tendency of two nodes to be mutually
linked [Newman et al., 2002, Garlaschelli and Loffredo, 2004]. This is formally defined as
|E↔|/|E|
, where
|E|
is the number of edges in a graph, and
|E↔|
is the number of edges whose opposite directional arc
exists, i.e.,
e
=
⟨{vi},{vj}⟩ ∈ |E↔|
if and only if
⟨{vj},{vi}⟩ ∈ E
. The notion was extended to weighted
graphs [Squartini et al., 2013, Akoglu et al., 2012], and using them, the relationship between degree and
reciprocity was investigated [Akoglu et al., 2012]. Moreover, the preferential attachment model [Albert
and Barab´asi, 2002] was extended by adding a parameter that controls the probability of creating a
reciprocal edge for generating reciprocal graphs [Cirkovic et al., 2022, Wang and Resnick, 2022]. Refer to
Section 1 for more applications of reciprocity.
Patterns and Generative Models of Hypergraphs:
Hypergraphs have been used widely for model-
ing group-wise interactions in complex systems, and considerable attention has been paid to the structural
properties of real-world hypergraphs, with focuses on node degrees [Do et al., 2020, Kook et al., 2020],
singular values [Do et al., 2020, Kook et al., 2020], diameter [Do et al., 2020, Kook et al., 2020], density
[Kook et al., 2020], core structures [Bu et al., 2023], the occurrences of motifs [Lee et al., 2020, Lee and
Shin, 2021], simplicial closure [Benson et al., 2018a], ego-networks [Comrie and Kleinberg, 2021], the
repetition of hyperedges [Benson et al., 2018b, Choo and Shin, 2022], and the overlap of hyperedges [Lee
et al., 2021]. Many of these patterns can be reproduced by hypergraph generative models that are based
on intuitive mechanisms [Benson et al., 2018b, Do et al., 2020, Kook et al., 2020, Lee et al., 2021]. Such
models can be used for anonymization and graph upscaling in addition to testing our understanding of
the patterns [Leskovec, 2008]. All the above studies are limited to undirected hypergraphs, while this
paper focuses on directed hypergraphs.
3
Directed Hypergraphs and Reciprocity:
Directed hypergraphs have been used for modeling chemical
reactions [Yadati et al., 2020], knowledge bases [Yadati et al., 2021], road networks [Luo et al., 2022],
bitcoin transactions [Ranshous et al., 2017], etc. To the best of our knowledge, there has been only one
attempt to measure the reciprocity of directed hypergraphs [Pearcy et al., 2014], where (a) a hypergraph
G
is transformed into a weighted digraph
¯
G
by clique expansion, i.e., by replacing each arc
ei
=
⟨Hi, Ti⟩
with the bi-clique from
Ti
to
Hi
, (b) a weighted digraph
¯
G′
is obtained in the same way from a hypergraph
G′
where, the perfectly reciprocal arc
⟨Ti, Hi⟩
of each arc
ei
=
⟨Hi, Ti⟩ ∈ E
is added if it is not already in
E
, and (c)
tr(¯
A2)/tr(¯
A′2)
, where
¯
A
and
¯
A′
are the weighted adjacency matrices of
¯
G
and
¯
G′
, respectively,
is computed as the reciprocity of
G
. Note that
tr
(
¯
A2
) corresponds to the weighted count of paths of
length two in
¯
G
that start and end at the same node, which is the same as the weighted count of mutually
linked pairs of nodes in
¯
G
, and
tr
(
¯
A′2
) is the count in the perfectly reciprocal counterpart. However, as
discussed in Section 1, clique expansion may cause substantial information loss [Yadati et al., 2020, Dong
et al., 2020, Yoon et al., 2020], and thus multiple directed hypergraphs whose reciprocities should differ,
if they are determined by a proper measure, can be transformed into the same directed graphs by clique
expansion. We further analyze the limitations of this approach based on axioms in the following section.
3 Directed Hypergraph Reciprocity
In this section, we present eight necessary properties of an appropriate hypergraph reciprocity measure.
Then, we present a family of reciprocity measures, namely HyperRec, and an algorithm for fast
computation of them. Lastly, we compare HyperRec with baseline measures to support its soundness.
3.1 Framework and Axioms
We present our framework for measuring hypergraph reciprocity. Then, we suggest eight axioms that any
reasonable reciprocity measure must satisfy.
Framework for Hypergraph Reciprocity:
Given a hypergraph
G
, we measure its reciprocity at two
levels:
•How much each arc (i.e., group interaction) is reciprocal.
•How much the entire hypergraph Gis reciprocal.
For a target arc, which we measure reciprocity for, multiple arcs should be involved in measuring its
reciprocity inevitably. For example, in Figure 1, arc
e2
’s head set and tail set overlap with
e1
and
e3
’s tail
set and head set, respectively, and thus we should consider both e1and e3in measuring e2’s reciprocity.
In graphs, however, only the arc with the opposite direction is involved in the reciprocity of an arc. This
unique characteristic of hypergraphs poses challenges in measuring reciprocity. The reciprocal set
Ri
of
a target arc
ei
is the set of reciprocal arcs that we use to compute the reciprocity of
ei
, We use
r
(
ei, Ri
)
to denote the reciprocity of an arc
ei
, where the domain is
E×
2
E
.
2
In graphs, a traditional reciprocity
measure [Newman et al., 2002] is defined as the proportion of arcs between nodes that point both ways,
and if we assign 1 to such an arc and 0 to the others as reciprocity, the proportion is equivalent to the
average reciprocity of arcs. Similarly, we regard, as the reciprocity of a hypergraph
G
, the average
reciprocity of arcs, i.e.,
r(G) := 1
|E|X|E|
i=1 r(ei, Ri).(1)
Motivations of axioms:
What are the characteristics required for
r
(
ei, Ri
) and
r
(
G
)? We introduce
eight axioms that any reasonable measure of
r
(
ei, Ri
) (Axioms 1-5) and
r
(
G
) (Axioms 6-8) should
satisfy. blue We first provide the motivation and necessity of the proposed axioms.
•
Incremental changes: Understanding when a value of a measure increases (decreases) helps users to
understand how the measure works and have faith in the values the measure returns. Without this
understanding, one cannot trust the measure, and this unreliability towards a measure may lead to
misinterpretation of the measured value. Thus, we propose Axioms 1-4 (and their generalized axioms)
to describe the cases where the value of a reciprocity measure increases (decreases).
•
Boundness: Establishing a finite range for a measure helps an intuitive comprehension of the numerical
extent of a characteristic. For instance, if a measure does not lie in a fixed range, it becomes challenging
to readily ascertain whether a particular hypergraph is reciprocal or not. Furthermore, a measure with
2Note that all arcs in Riare used in computing the reciprocity of ei, and thus it does not correspond to a search space.
4
(a) AXIOM 1 (b) AXIOM 2A (c) AXIOM 2B
(d) AXIOM 3A (e) AXIOM 3B (f) AXIOM 4
Left side in each subfigure
𝑒𝑖(target arc)
𝑒𝑖1
′(or 𝑒𝑖
′)
𝑒𝑖2
′
Other
candidates
(Only in Axiom 4)
𝑒𝑗(target arc)
𝑒𝑗
′
Right side in each subfigure
Figure 2: Examples for Axioms 1-4. In each subfigure, the reciprocity of the arc
ei
on the left side should be
smaller than that of the arc
ej
on the right side. This inequality holds by HyperRec (see Section 3.2) in all
subfigures. Specifically, if
α
= 1,
r
(
ei
) &
r
(
ej
) are 0
.
0000 & 0
.
3605 in (a), 0
.
2697 & 0
.
5394 in (b), 0
.
4444 &
0.5394 in (c), 0.3167 & 0.6466 in (d), 0.3233 & 0.6466 in (e), and 0.2347 & 0.2500 in (f).
a defined finite range enhances the ability to make meaningful comparisons across diverse hypergraphs.
Motivated by this intuition, we propose Axiom 5 and Axiom 7, which suggest the bound of hyperarc
and hypergraph reciprocity measures, respectively.
•
Reducibility: Reciprocity in an ordinary directed graph is a well-known statistic that is widely used
in various fields of study [Nguyen et al., 2010, Hidalgo and Rodr´ıguez-Sickert, 2008, Newman et al.,
2002] (see Section 1 for details). Since a directed hypergraph is a generalization of an ordinary directed
graph, one would expect that a directed hypergraph reciprocity measure should be equivalent to the
common directed graph reciprocity when applied to any hypergraph containing only hypercars with
head sets and tail sets of size 1 (i.e., directed graph. where
|Hi|
=
|Ti|
= 1
,∀⟨Hi, Ti⟩ ∈ E
). Thus, we
propose Axiom 6, which suggests this characteristic
•
Reachability: Identifying whether the upper bound of a measure is truly achievable or not plays a
crucial role in ensuring the reliability of the measure’s range and the accurate interpretability of its
returned value. For example, let’s consider a reciprocity measure with a known upper bound of 1, but
it can actually only reach the value of 0.2. In this scenario, if a particular hypergraph achieves the
reciprocity value of 0.2, which is actually the maximum possible value for a hypergraph, one may think
the corresponding hypergraph is not highly reciprocal, since the known upper bound of 1. Thus, we
propose Axiom 8to formalize the reachability of the maximum reciprocity value.
Details of axioms:
In Axioms 1-4, we compare the reciprocity of two target arcs
ei
and
ej
whose
reciprocal sets are
Ri
and
Rj
, respectively. Moreover, in Axiom 2-4, we commonly assume two target
arcs
ei
and
ej
are of equal size (i.e.,
|Hi|
=
|Hj|
and
|Ti|
=
|Tj|
). Here, we say two arcs
ei
and
ek∈Ri
inversely overlap if and only if
Hi∩Tk̸
=
∅
and
Ti∩Hk̸
=
∅
. Below, the statements in Axioms 1-4
are limited to the examples in Figure 2 for simplicity. Each statement of Axioms 1-4 is generalized in
Generalized Axioms 1-4.
Axiom 1 (Existence of Inverse Overlap).In Figure 2(a),
r
(
ei, Ri
)
< r
(
ej, Rj
)should hold. Roughly, an
arc with at least one inverse-overlapping reciprocal arc is more reciprocal than an arc with no inverse-
overlapping reciprocal arcs.
Generalized Axiom 1 (Existence of Inverse Overlap).Consider two arcs
ei
and
ej
. If
Ri
and
Rj
satisfy
(i)∀e′
i∈Ri: min(|Hi∩T′
i|,|Ti∩H′
i|) = 0,
(ii)∃e′
j∈Rj: min(|Hj∩T′
j|,|Tj∩H′
j|)≥1,
then the following inequality holds:
r(ei, Ri)< r(ej, Rj).
Axiom 2 (Degree of Inverse Overlap).In Figures 2(b-c),
r
(
ei, Ri
)
< r
(
ej, Rj
)should hold. Roughly, an
arc that inversely overlaps with reciprocal arcs to a greater extent (with a larger intersection and/or with
a smaller difference, which are considered separately in the generalized axioms) is more reciprocal.
5
摘要：

ReciprocityinDirectedHypergraphs:Measures,Findings,andGeneratorsSunwooKim∗1,MinyoungChoe†1,JaeminYoo‡3,andKijungShin§1,21KimJaechulGraduateSchoolofAI,KAIST2SchoolofElectricalEngineering,KAIST3HeinzCollegeofInformationSystemsandPublicPolicy,CarnegieMellonUniversityAbstractGroupinteractionsareprevalen...

收起<<
Reciprocity in Directed Hypergraphs Measures Findings and Generators Sunwoo Kim1 Minyoung Choe1 Jaemin Yoo3 and Kijung Shin12.pdf

共38页,预览5页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：38 页 大小：1.43MB 格式：PDF 时间：2025-04-29

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 38
评分 收藏
分享
立即下载
客服
关注