Balanced Ranking with Relative Centrality: A multi-core periphery perspective
Authors: Chandra Sekhar Mukherjee
Jiapeng Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Ranking algorithms
community structure
clustering
balanced ranking
centrality measures
Primary area: learning on graphs and other geometries & topologies
TL;DR: We provide a novel approach to design balanced unsupervised ranking algorithms, improving on a large class of centrality measures, along with applications on data with underlying communities

Abstract: Ranking of vertices in a graph for different objectives is one of the most fundamental tasks in computer science. It is known that traditional ranking algorithms can generate unbalanced ranking when the graph has underlying communities, resulting in loss of information, polarised opinions, and reduced diversity (Celis, Straszak \& Vishnoi [ICALP 2018]).

In this paper, we focus on *unsupervised ranking* on graphs and observe that popular centrality measure based ranking algorithms such as PageRank may often generate unbalanced ranking here as well. We address this issue by coining a new approach, which we term *relative centrality*. Our approach is based on an iterative graph-dependent local normalization of the centrality score, which promotes balancedness while maintaining the validity of the ranking.

We further quantify reasons behind this unbalancedness of centrality measures on a novel structure that we propose is called multi-core-periphery with communities (MCPC). We also provide theoretical and extensive simulation support for our approach towards resolving the unbalancedness in MCPC.

Finally, we consider graph embeddings of $11$ single-cell datasets. We observe that top-ranked as per existing centrality measures are better separable into the ground truth communities. However, due to the unbalanced ranking, the top nodes often do not contain points from some communities. Here, our relative-centrality-based approach generates a ranking that provides a similar improvement in clusterability while providing significantly higher balancedness.

Published as a conference paper at ICLR 2025
BALANCED RANKING WITH RELATIVE CENTRALITY:
A MULTI-COR PERIPHERY PERSPECTIVE
Chandra Sekhar Mukherjee
Jiapeng Zhang
Thomas Lord Department of Computer Science University of Southern California chandrasekhar. mukher jee 0 8 gma 1 ccom
Thomas Lord Department of Computer Science University of Southern California j aaanngzuusc.co
ABSTRACT
Ranking of vertices in graph for different objectives is of the most funda- mental tasks in computer science. It is known that traditional ranking algorithms can generate unbalanced ranking when the graph has underlying communities, resulting in loss of information, polarised opinions, and reduced diversity (Celis, Straszak & Vishnoi [ICALP 2018)).
In this paper, we focus on unsupervised ranking on graphs and observe that popular Sentrality-measure-bbee
ranking algorithms such as PageRank may often generate unbalanced ranking here as well. We address this issue by coining new approach, which we term relative centrality. Our approach based on an iterative graph- dependent local normalization of the centrality score, which promotes balancedness while maintaining the validity of the ranking.
We further quantify the reasons behind this unbalancedness of centrality measures. using novel structure that we propose. We term this as the multi-core-pee periphery with communities (MCPC) structure. We provide theoretical and extensive simulation support for our approach towards resolving the unbalancedness MCPC.
Finally, we consider graph embeddings of 11 single-cell datasets. We observe that top-ranked as per existing centrality measures are better separable into the ground truth communities. However, due to the unbalanced ranking, the top nodes often do not contain points from some communities. Here, our relative-cent wewtee-eettaattbbbbeeeeeeee based approach generates a ranking that provides a similar improvement in clusterability while providing significantly higher balancedness.
INTRODUCTION
Ranking of data points is one of the fundamental problems in computer science, with applications ranging from information retrieval (Liu et al. 2009), recommendation systems (Page al. 1998).
community detection (Liu et al., 2016 Hajjj et al. 2020). resource allocation problems (Zipkin 1980) and is also extensively used in online economies (Singh & Joachims 2019).
Ranking algorithms are often applied to data where the data has an underlying partition into groups/ communities, such when allocating resource (Celis et al.) (017). using ranking algorithms for community detection (Liu et al. 2016)) or deciding influential nodes in social networks (where people of different ethnic backgrounds or political beliefs can be considered as communities) (Zhang et al.) 2015) Kojaku & Masuda (017). Here in many cases it is desirable to have a balanced ranking, i.e., top data points ranked by the algorithm should contain a reasonable fraction data points from each community. While there has been recent progress in the supervised setting with respect to ranking with group fairness constraints (Celis et al. 2017 7 Singh & Joachims 2019 Zehlike et al. 2002)) the balancedness of ranking in the unsupervised learning context remains under-explored.
In this paper, we focus on unsupervised ranking on graphs with underlying communities. We note that the primary class of ranking algorithms here are Centrality measures. Different centrality measures
"Research supported by NSF CAREER award 2141536. I Research supported by NSF CAREER award 2141536.

---

Published as a conference paper at ICLR 2025
clussoring
Rank nodes existing centrality measures (Using Pagefoni this Quampl))
Induced subgraph top 20% nodes
INMIN 65, Punty-
Better separable
Complex cancer type
K-NN graph embedding
clsstring:
(1 communily fly lost, Only 10% points of onher communihes present)
Unbalanced
single-cell dataset
Our contribution
Run Louvain clustering:
Rank nodes relative centrality
Run Louvain custering:
Better seporable
(10 underlving communities)
NMI-Q:46 Purity- 0.72
subgraph on top 20% nodes
(NM 64. Purliyed
method this esomple)
Significantly more balanced
communities
An example of the benefit of unsupervised balanced ranking algorithms. While the top-ranked nodes by existing centrality measures have improved separability (the induced subgraph can be clustered with better accuracy), the unbalancedness results in some communitics being completely overlooked. In contrast, our olaaive-eentraliit--aaee algorithm offers significantly higher balancedness while having comparable separability.
Figure 1:
rank the nodes of graph according to their notion of importance. Centrality measures like PageR- ank (Page et al.) 1998) have been hugely influential, and others such as Betweenness (Barthelemy) 2004). Closeness (Okamoto et al., 2008), Degree centrality (Zhang Luo (017) and K-core rank- ing (Hébert-Dufresnee et al. 2016)) have been used in understanding phenomena such as cognitive behavior (Bassett et al. 2013). online amplification (Barberá et al., 2013), and others.
Single-cell RNA seq data: Motivation and use-case of unsupervised balanced ranking.
Balancedness can very important in the unsupervised context as well. As a concrete example, we consider single-cell RNA seq data, which is one of the most influential biological data of the last decade (Chattopadhyay et al. 2014; Poulin et al. 2016 Zhang et al. 2021 Li al. 2024).
Here, we are given dataset with some data points (each data point corresponding to single cell), with d features (each feature corresponding to the gene expressions of a cell). single-cell analysis, the main goal is to understand cell behavior (understanding biological systems, diseases, and others) through gene expression.
Here, separating the data points into different clusters (according to their cell types) using gene expression is an important step in single-cell analysis, as noted by this popular Nature review paper (Heumos et al., (2023). Once the different communities found, bioinformaticians then use for different downstream tasks.
However, despite significant research and progress, the performance of the state-of-the-ar community detection algorithm can be very poor (e.g., NMI less than 0.6). In such a case, centrality measures may be helpful. For example, on the graph and choose to run community detection on only the induced subgraph of the top-ranked vertices, the performance of the community detection algorithm much improved. However, the top-ranked points can be unbalanced, and some communities may be completely missed while others are underrepresented, which affects the downstream tasks. See Figure [ for a detailed example. Motivated by this example, we focus on directed graphs. Our contributions are as follows.
observe that if we run popular centrality measures like PageRank
1.1 CONTRIBUTIONS
A Balanced meta-raanking-algoritnn As the primary contribution, we coin novel concept, "relative centrality", and design meta ranking algorithm (Details in Section 3. that provides superior balancedness to several popular centrality measures on the graph embeddings of a large set of biological (single-cell) datasets.
A new structural assumption. Structural assumptions are ubiquitous in the design and analysis of unsupervised learning algorithms, used for both inspiration of new algorithms as well as analysis of established algorithms. In the context of ranking on graphs with underlying community structures, two such structures are community structure and core-periphery structure. The former is used for understanding community detection, and the latter is heavily interlinked with the performance of centrality measures. We refer the readers to Figure 2 for a schematic representation of these two structures. Here, the recent review (Yanchenko & Sengupta 2023) core- peripheryy structures has noted "a better understanding of the interplay between community and core- pore-periphery structure" as an interesting open problem.
2

---

Published as a conference paper at ICLR 2025
Against this backdrop, propose new structure that call multi-core-ppe porepi-c with communi- ties (MCPC) by combining these two structures to quantify the unbalancedness in traditional centrality measures observed in real-world graphs. Readers may refer to Fo gain initial overview and refer to Section 2 to get a more detailed insight into this structure. We provide theoretical proof of the unbalancedness random graphs with MCPC structure and show that our relative centrality approach overcomes this, demonstrating initial theoretical evidence and large-scale simulation support.
Applications to real-world data in improving inference of community structure. Finally, as concrete application of our balanced ranking algorithm, we show that if we apply graph clustering algorithms the induced subgraph of top-ranked nodes the aforementioned datasets, we have a comparable improvement in clustering accuracy to existing centrality measures, while our result is significantly more balanced. Details can be found Section
We end this section by laying out detailed organization of the rest of the paper.
Organization. In Section 2 provide further background the community and core-periphery structures and the motivation behind our multi-core caali-core-periphrryy structure, and then formalize the MCPC structure and the characteristics of an ideal ranking algorithm in this framework. We further discuss connections to real world data and other models.
Then, in Section 3] we define a random graph model in Section as an instantiation of MCPC and analyze the unbalancedness in traditional centrality measures. In Section 3.1 we define our relative centrality approach and describe our algorithms, along with initial theoretical and simulation support for its balancedness. We also evaluate these phenomena on graph embeddings of generalized mixture model Appendix C
Section contains our experiments on the real-world graphs. Motivated by the standard clustering pipeline of single-cell data, we look at the graph embeddings of 11 complex single-cell datasets. For all the datasets, selecting top-ranked nodes by centrality measures leads to improved separability (observed both structurally and through improved performance of clustering algorithms), with our methods providing significantly superior balancedness compared to traditional centrality measures.
Finally, while we make exciting progress in balanced unsupervised ranking algorithms and show both theoretical analysis and impact real-world datasets, we note that our work has some limitations. We place a detailed discussion in Appendix E.3
We conclude this Section with discussion of related works.
1.2 COMPARISON WITH EXISTING WORK.
In this paper, we design a balanced ranking algorithm that is applicable to a large set of real-world data and can also be theoretically supported in the MCPC structure. Even within the core-periphery literature, work with multiple cores is rarer. The existing works here mainly focused on comparably restrictive settings. The works (Tunç& & Verma 2015) and (Kojaku & Masuda (017)) proposed specific equations to capture the interaction between nodes from different cores and designed maximum likelihood-bant algorithms for these equations; the paper EElioot et al. (2020) studied directed graphs with multi-cores, but they do not consider the coexistence of community structure. As such, we applied the algorithms of Elliot et al. (2020) to our graph simulation model and observed an almost-random outcome and thus placed it in Appendix E. along with with the literature as well as some limitations of our work. Most importantly, to the best of our knowledge, none of the previous papers considered the unbalancedness issue of centrality measures in similar setting.
in-depth comparison
2 MULTI FORE-PERIPHERY WITH COMMUNITIES (MCPC): A THEORETICAL LENS FOR CENTRALITY MEASURES GRAPHS WITH COMMUNITIES
In this section, we lay the intuition behind the MCPC structure to capture the unbalancedness in the ranking due to traditional centrality measures, starting by discussing two popular structures.
Community structure. A graph is thought to have community structure if the vertices have an underlying (unknown) partition into some & communities such that vertices from the same underlying community more likely to be connected by edges than vertices from different communities.
3

---

Published as a conference paper at ICLR 2025
Harder periphery
Separable core
a/ Community structure
Well studied structure for graphs with underiying communibies
b) Unbalanced MCPC structure
a) Multi core periphery (MCPC) structure
Both communities have same amount edges
We postulate that this the structure in many real world graphs with underlying communities
Howevvrr the blue care sparser than the red one.
Sparce peripery
Here all popular centrallyy measures lead unbalanced raniing.
community and pertphery.
Relative centrality solves this issue
b) Core Periphery structure
Inter-cont community edges are more prevalent between the peripheries.
through a data depondent narmalization
A popular structune which PageRank and other centrality ranked above peripheries popular centrality measures.
process
analyzed.
Figure 3: Example of graphs with MCPC structure. Unlike the graphs with community structure where inter-community edges are spread uniformly in community, here, the (dense) cores have smaller fraction inter-community edges. In (a), both cores have the same density (they are identical) and centrality measures such as degree centrality will result in balanced ranking. In (b) the blue core is sparser, and therefore existing centrality measures will rank them lower.
Figure 2: Structures in analysis and design of centrality measures and community inference algorithms
This structural assumption has inspired important clustering objectives such as modularity (Brandes)
al. 2007 2006; Noack, (209)) and correlation clustering (Bansal et al. 2004) and also popular probabilistic models such as the stochastic block model (SBM) (Abbe 2018 Mukherjee et al. (022))
Figure 2 (a) gives a schematic representation of a graph with community structure.
Core periphery (CP) structure. We now turn our focus on different kind of structure called core-periphn pore-periphery (CP) structure which has been extensively studied in the network analysis literature in the last two decades (see the surveys (Rombach et al., 20144) 2017] Yanchenko & Sengupta (023) and the references therein). Here, the graph is assumed to contain a dense subgraph (the core), and the other vertices (forming the periphery) are sparsely connected to each other, well the core. Figure (b) gives a schematic representation of a graph with core- core-periphery structure.
(b)
Centrality measures perform well on core- pore-periphery structure. Identifying the cores is an important task in graphs with core-periphery structure (Cucuringu et al.] 2016; Rombach et al. 2014 Yanchenko & Sengupta 2023). ) Here centrality measures (such degree centrality and RaneRank)
are known to be very good at ranking the core nodes above periphery nodes (Rombach et al.) 2014
Yanchenko & Sengupta 2023) even being near-optimal in some random graph setting (Baruecal
et al. 2016), making CP structures a promising setup to better understand balancedness of centrality measures graphs with underlying community structure.
However, the majority of the work in the pere-perpphey structure is in single-core setting. Some recent papers have observed the existence of multiple cores in graphs (Wang al., 201T Elliott
et al. 2020 Kojaku & Masuda 2017). and also coexistence of CP and community structure (Tunç &
Verma [215]] Yang Leskovee, 2014), with the recent survey (Yanchenko & Senguptal (003)) noting
"a better understanding of the interplay between community and CP structure" as an open problem.
To the best of our knowledge, none of the existing works discussed the balancedness of centrality
measures in the presence of multiple cores. Here we propose the following structure.
The MCPC structure. Consider graph G(V. with a hidden partition into communities Vi,..., Vz. We say that the graph satisfies an MCPC-structure w.r.t the hidden partition if: each set V. has a further partition into a core V1,1 and periphery V., such that most edges starting in core end up in that core itself (the cores are densely connected). The peripheries are loosely connected. We formalize this notion with core concentration as follows.
Definition 2.1 (Core concentration). Given directed graph G(V, E), for any V", V" S V. let E(V', V") denote the number of edges starting in V and ending in v", Then we define the core concentration (or simply concentration) of S C V as
CCa(S) (F(S, S) F(8,5))/IE(S, V)
(1)
4

---

Published as a conference paper at ICLR 2025
That is, expect the core to have two properties. First, only few edges originating in a should leave the core, which we penalize with the -E S) term. Secondly, we expect more edges from the peripheries ending at the cores (making each core more central part of the corresponding community), which we incentivize with the + F(( term.
Next, we expect the cores have fewer inter-community edges compared the peripheries. Note that such a situation were to occur, the top-ranked core-ranking algorithms will be easier to separate, capturing the behavior of PageRank in our initiating example in Figure Then, the concrete definition of the MCPC structure is as follows.
Definition 2.2. We say a graph G(V, E) with an underlying hidden partition (Vi,..., Vaj has an (a, 3)-MCPC structure for Q2() and iff
i) The hidden partition imposes community structure on the graph, i.c., E(V, V)) 2 E(V, V.).
ii) Each hidden partition V; can be further partitioned into two sets, namely the core V111 and the periphery Vi,,, such that CCo(V,,) > (Vo.V.)) + a. (the core V1, has a higher core concentration than periphery Vi,o).
iii) For any two communities Vi, Vg, edges between cores than the peripheries).
E(V.,,))) [Val
< 3 E(G,)) (There are fewer inter-community
In this context, in Figure 3 (a), the two cores have almost identical concentration, whereas the peripherics have a lower concentration than the cores. Therefore, a simple degree centrality (ranking the nodes in descending order of their degree) will rank the cores above peripheries, while also ranking the cores in a balanced manner.
Unbalancedness of Centrality measures on graphs with MCPC structure. However, the bal- ancedness of centrality measures may deteriorate quite fast if the different cores have different levels of connectedness. For example, let consider the instance in Figure bb). Concretely, it is 3-regular directed graph (i.e., each node has the same out-degree, and both the communities (blue and red) have the same number of core and periphery vertices (5 each)). However, the blue core has a lower core-concentration than the red core. In such a case, degree centrality will result in an biased/unbalanced ranking of the nodes. Note that the downstream algorithm will not know the total number of cores or core vertices. In such case, if one selects points from the top of the ranking, may lead to an unbalanced representation the communities (as we observed in the example of the cancer dataset). Against this backdrop we define the two primary characteristics we want in ranking algorithm.
Definition 2.3 (Performance metrics of ranking algorithm w.r.t. the MCPC structure.).
i) Core-prioritization: A ranking algorithm should rank core vertices above periphery vertices. We quantify this as the AUROC value (Marques et al. 2023) of the w.r.t. core/periphery label of each vertex, which is close to 1 when almost all core vertices are placed above almost all periphery vertices.
a ranking of the vertices, and let F. denote the top e n vertices in the ranking. Then, quantify the balancedness in the top G. = (min; L.,.Va.ll maxx; [F.VV.l) That is, the top points in the ranking should contain a roughly equal proportion of points of each core. The ranking reaches a perfect balancedness if B, G) = 1. The total balancedness is defined as B(F, == >. Biin G).
ii) Balancedness: Let
vertices in the ranking as
Relative centrality mitigates the unbalancedness. We show in Section 3 that the relative centrality measure we propose achieves a balanced ranking with high core- pore-riioittization even when the cores have different concentrations. This provides a theoretical understanding of the unbalancedness of existing centrality measures and evidence of our algorithm's performance in a controlled (yet important) setting. We further present extensive experiments in Section to demonstrate the usefulness and balancedness of our algorithm on real-world data.
MCPC in the real world; Single-cell data and beyond. First, we give some more insight why single-cell data is a good fit for this structure. These datasets can be considered as high-dimensional (usually more than 25,00 25,000) noisy data, suffering from technical noise and experimental error Jovic ctt al. (2022). Many data points could be abnormal cells, such as dead cells and doublets, or cells affected adversely by experimental noise. Therefore, separating such cells in the graph embeddings
5

---

Published as a conference paper at ICLR 2025
may be very hard. In our MCPC structure, capture them peripheries. In contrast, the cells with less degenerative effect can be seen as cores. This further motivates the design and analysis of balanced ranking algorithms, one would hope to select cores for each cell type. In Section 4.1 observe that the communities in graph emheddings of real-world biological data indeed contain cores with higher concentration values, and these cores have lower fraction of inter-community edges compared to the whole data.
Beyond this application, MCPC structure may also be relevant to certain social choice scenarios. For example, if we consider the social network of US population through the lens of political affiliation, the resultant data should exhibit some MCPC structure. This is because there will be people who are firmly committed to one political affiliation. either Democrats or Republicans; these people will form the core of each community. In contrast, more neutral people will align with different affiliations for different topics, forming the peripheries. Some recent papers have observed that social networks such as Twitter can have multiple cores (Kojaku & Masuda 2017 Yang et al. 2018).
ANALYSIS AND EXPLORATION OF CENTRALITY AND RELATIVE CENTRALITY IN MCPC VIA A RANDOM GRAPH MODEL
A general graph with an MCPC structure may be too complicated to both simulate and analyze. In this direction, we define a block model-based random graph setup to instantiate graphs with MCPC structure. In a block model, the set of vertices V are divided into some blocks, and then the nature of interaction between two vertices is function of their block identity. For example, the popular stochastic block model (Abbe) 2018) (SBM) is such a model, used to generate graphs with underlying community structure. Block models
also popular in CP literature, with the performance of many algorithms made under different CP assumptions quantified on these block model deee--geeerated
graphs (Cucuringu et al. 2016 Elliott et al. 2020 Zhang et al. 2015 Yang et al. 2018).
We take a similar approach in this paper and define a model that we call MCPC-block model that generates directed graph where the out-degree of each vertex is k(1 = o(1) for some k. For simplicity, we define it w.r.t. = 2 underlying community, which can be easily extended.
Definition 3.1 (MCPC-block model). We have V = {ei,.... Un a set of n vertices that are partitioned into 2 communities V1 and V2, with each Vú further partitioned into a core V1, and periphery Vi,.- There is a4 x block-probabilitty matrix such that each row sums to 1. Then, for any ey E Ve,e and by E Ve'e'' we add an en + Ui edge iid with probability k/IVe, ve I (P((),), (L', c')].
Baseline centrality measures. We consider degree centrality, PageRank (with 3 different damping factors), Katz Centrality (Bloch et al., 2023), and a popular cor-pdecomposition- based algorithm al. 2016) as initial baseline algorithms for
(that we call onion decomposition) (Hébert-Dufresmn evaluation of centrality measures on MCPC structures.
Centrality measures can be unbalanced even when both communities and cores are of same size. We set |V.el = 0.25 x for all the blocks and then set the block parameters to lead to an (a, B) MCPC structure. Here, it is important to note that while we demonstrate the phenomenon in theory and in simulation when the size of all the cores and peripheries are the same, our algorithms are applicable even when they are of different sizes. In fact, our real-world experiments, the size of the different communities in a dataset varies widely. Then, the behavior of degree centrality can be captured as follows.
Theorem 3.2 (Behavior degree centrality). Let GVV E) be graph sampled from the MCPC-block model w.r.t. partition of V into Vi,es (E, c) E {0, 1 where k = wlog n). Let F(v) be the degree of the vertex. Then for any U, E Ve,1 we have F(v;)) = 2k + k. (1 + (L))CCCC(VV)))
That is the degree of vertex almost linearly related to the CCG of the core it belongs in. If (Va(V).) CCa(Ve.,) + C. for any constant C. the degree of all vertices in Ve, will be higher than the ones in Ve 1. This will result in an unbalanced ranking. The proof of Theorem 3.2 can be found in Appendix A.I Next, we observe this in simulation.
Initial simulation. For simulation purposes, we instantiate IP as in Table I parameterized with y When y O, the generated graph will have a RS 0.3 and 3 no 0.25, and CC (Vo,) ~ (Vi.)) In such a case, degree, as well as the other centrality measures, have high balancedness throughout the ranking, as observed in Figure 4(a) Moreover, it has high core prioritization (as the concentration

---

Published as a conference paper at ICLR 2025
Katz Central By
Pegafannc (0
Pogifiins 851
Pegefaanc
2
Sattork
010
Traction
Prattion
Fraction of points
Fractior points
(a) ICEF of induced (b) Balancedness of (c) ICEF of induced sub- (d) Balancedness of rankings for Y subgraph for graph gen- rankings in graph graph y = 0.05 crated with y
0.05
generated from ?
Figure 4: Balancedness and intra-community edge fraction (ICEF) of the induced subgraph of the top-ranked nodes due to different centrality methods and our initial method (N-Rank) on 2-block MCPC graphs generated with parameter 7 as per Table When 7 = 0, in the generated graph both the cores have roughly equal concentration and the centrality measures produce balanced ranking. When y > 0, while the ICEF still increases at the top of the ranking (indicating better separability). the unbalancedness increases, which is mitigated by our method.
of peripheries is lower). Thus, the induced graph of the top e-fraction of the points has a higher intra-community edge fraction (ICEF) (which simply the fraction of edges with endpoints being in the same community) as decreases, which we note in Figure440)
Unbalancedness when cores have varying concentration. However, the scenario changes if > Consider 0.05. Then we have (C,(V = (Vo,V 1 + 0.007. While the core prioritization will still high for the centrality measures, the balancedness becomes very low, shown in Figure 4(c)
3.1 MITIGATING UNBALANCEDNESS WITH RELATIVE CENTRALITY FRAMEWORK
The primary reason behind the unbalancedness of the traditional centrality measures is that they capture the global centrality of vertices. With this observation, we aim to develop a method that generates a scoring with the following properties.
The core vertices should be assigned a higher score than the periphery vertices.
ii) The score of two vertices belonging to different cores should be similar, irrespective of the cores they belong to.
If scoring of the vertices satisfies the two properties, we call it a relative centrality measure. Then ranking vertices descending order according to some score should lead to high balancedness as well as core prioritization. We first propose initial Algorithm I that we call N-Rank.
Algorithm NeighhorRank (N-Rank) with f-step initialization
Input: Graph G(V, E.,t. Let the Adjacency matrix be A.
1,
(#Vector of all ones)
for in do
ATs
(# Obtaining initial centrality score)
end for
(1)) s[{]
for E V do
Ne(u;) is the neighborhood of) By based the outgoing edges
So, <- Du e Ne(e.),F(v)) > (v.) U (a).
(w))
The relative-centrality step]
average (
end for return AM
3.1.1 DESCRIPTION OUR FIRST METHOD N-RANK AND ANALYSIS IN THE TWO BLOCK MODEL
As discussed, we want an "initial centrality measure" that ranks the core vertices above periphery vertices (so far, independent of the balancedness).
7

---

Published as a conference paper at ICLR 2025
We define a generalized class of measure F(t) via t-step power method, defined in Algorithm When t = 1, this converges to the in-degree centrality measure. As we mostly focus on (almost)- regular directed graphs, this is essentially the same as the degree centrality measure. When t > 1, it (approximately) captures the 1-step random-war walk reachability of vertices. We note that we focus on (almost) regular directed graphs in this paper motivated by K-NN embeddings of real-world vector datasets. However, our algorithms can be applied to non-regular directed graphs as well.
Then, let us focus on the performance of the initial centrality measure with = 1. Theorem 3.2 states that vertices from a core with higher CCa will get a higher score as per the initial centrality measure. To mitigate this unbalancednesss, for each v E V. we select the o' E (NG(v) (v's neighborhood) with higher F score and obtain the final score F(v) as the ratio of F value of with average of these neighbors (including itself). Note that this value can be at most 1.
Consider any vertex e E V2, Furthermore, let 3 be small (o(1/k)), i.e., inter-community edges between different cores are few. Then, for many such v, all of its neighbors will belong to either the same core, which will have a very similar score, or peripheries, which will have a lower score as they belong to a set with a lower concentration, following Theorem 3.2 Then, we have F(u)= x 1 for any E V trrespective of which core it is. We capture this behavior in Theorem A.7 in Appendix where we show that almost core vertex has a F(v;) value of - <(1) with high probability. This generates initial intuition about the balancedness of N-Rank. Then, in Lemma [A.8 of Appendix
A [A.
we show that the peripheries will have a lower score than the core vertices, which indicates 1-step N-Rank has high core prioritization.
Finally, we show that on expectation, roughly the same fraction of points from each core has the score of F()) = 1, which is the maximum possible score. In contrast, following Theorem 3.2 the degree-centrality method will have points only from the stronger core at the top of the ranking.
Theorem 3.3 (1-step N-Rank places points from each core at the top). Let G be an vertex graph obtained from the MCPC block model with k: = w<oog n) resulting an (S2(1), o 11+)) - MCPC- structure w.r.t. to the core-periphery blocks and Fvv be the score of the vertices as per Algorithm
fort 1. Then, we get the following behavior on expectation for any core Ve,1-
(1- Vol PI(C, 1), (E, A
(1+ ((1))Val
S BIIV, no: F(v) = 1H1 S (),
That is, on expectation, similar fraction of points (O(1/k)) from each core will have a score of in the 1-step N-Rank method. This provides an initial theoretical insight into why the highest-ranked points in N-Rank should be balanced. The proof can be found in Appendix A.4 A.44
In fact, we observe in all our simulations that N- Rank has a high balancedness while having similar ICEF improvement compared to the baselines (Figure ((d).. Figure ( [[c]ssooss that N-Rank has high balancedness for ry = 0.05, even though the two cores have different concentrations. Thus, N-Rank with 1-step can be thought of as a way to create a relatively central version of degree centrality.
Generalization into a meta-algorithm. Next, we generalize our algorithm in two natural ways.
1) There may be periphery vertices in the graph that have a high FG value compared to its 1-hop neighborhood (E.g.. a periphery vertex that has no edges going to a core). To mitigate this issue, we can look at some y-hop neighborhood Na.((e) of v when selecting the reference set.
2) We have observed that our N-Rank approach increases the balancedness in the initial centrality measure FG. In this direction, we can recursively apply this process by first calculating the y-hop N-Rank value and then feeding it back to the algorithm as the initial centrality measure to further increase balancedness. We can apply this recursive process any
1 many times.
Due to space restriction, we write the general method as a meta-algorithm M-Rank((ty.z) 2 in Appendix B with an in-depth discussion. Then, N-Rank can be written MR- 1R-Rann(1.1..) We further define MR-Rank((t,2.0) as N2-Rank (t steps) and (R-Rann((t,..) as RN-Rank(t steps). M- Rank(ty,z) has runtime of O(t E + (z 1) k. [V]) for k-regular directed graphs.
Large scale simulation and core- prioritizaiion parameterized block probability matrix in Table Tand vary y from 0 to 0.2 with an increment of 0.02, generating graph for each value for large-scale simulation. We make the following observations.
balancedness tradeoffs. We use the y-
8

---

Published as a conference paper at ICLR 2025
Agpullant 10
Segellanc (0.90)
Ouaze decorpoctioo
2N--att
5D Rank
Datwean betraaan cana
(a) Core prioritization
(b) Balancedness
Figure 5: Core-prioritization and total balancedness (as per Definition 2.3 of centrality measures on graphs generated MCPC-block model for different y values (As per Table D. As increases, the difference the concentration of the cores from the two communities increases, and as result, the gap in the balancedness of our method becomes higher (while core- core-prioritization remains similar) compared to existing centrality measures.
As y increases, three structural changes occur in the graph. (separation of CC values between cores and peripheries) decreases, 3 (inter-core edge fraction) increases, and the dif- ference between the core concentration values of the two cores becomes larger. We observe in Figures((a))a happens, our balancedness becomes superior to the baselines while maintaining comparable core prioritization.
Vo,1
Vo,
Vi,0
Vi,1
Vo.
08+
0.075
0.75.
0:05
Voo
Vi,0
0.2
0.9
0.2
0.4
Vi.
0.75-
0.05
as this
Table 1: Block probability matrix to generate MCPC-block model graph
EXPERIMENTS ON REAL-WORLD DATA
Motivated by the workflow of single-cell data, we focus on k-NN embedding of vector datasets. That is, given vector dataset X with datapoints Fi..... Th generate graph Gx (V, E) with V = n and for each datapoint Fj we add directed edges starting from i; and ending at the representative vertices of k-nearest neighbors.
In this direction, we explore the relative centrality measures in a more complex simulation model based on the Gaussian mixture model (Reynolds al. 2009) in Appendix C As before, methods have higher balancedness when different cores have different concentration values.
4.1 SINGLE-CELL DATA
We use total of 11 datasets. We use the 7 datasets from a recent database (Abdelaal et al. 2019), the popular Zheng8eq dataset (Duò et al. 2018), and more large datasets (Smith al. 2019), and T-cell dataset (Savas et al. 2018) of cancer patients. All of these datasets have annotated labels available of their corresponding cell types that form the underlying communities. The size of the datasets vary from 1400 to 54, 000. For each dataset, we first pre- pre-process it with standard pipeline (details in Appendix D) and then obtain its 20-NN graph embedding. which we denote as Go- This is very similar to the pipeline of the state-of-the-arr clustering method for single-cell data, Scurat (Stuart et al.) 2019). Then we apply the baseline centrality measures and our relative centrality- based algorithms to these graphs. We make the following observations.
Datasets:
Inference. For each graph Go (V, E), we select some top e-fraction of the points in the descending order of their ranking per the ranking algorithm F and denote it FV.V). First, explain the observations w.r.t. the T-cell dataset (Savas et al.) 2018).
i) Core- Core-ranking improves community structure. induced subgraph has a higher intra-conmunity edge fraction, as observed Figure 6(a)
We observe that e-decreases, the corresponding
ii) Evidence of cores. Let S be the top e-fraction of the points. Then, have the very interesting observation that CCG, (V: n S) > CCG, (V)). That is, the higher-ranked points indeed form the cores
of their communities per Definition 2.2 We discuss this in detail in the Appendix D
iii) Relative centrality has higher balancedness. The single-cell datasets we look at have many ground truth communities (sub-populations) and we aim keep points from all communities the

---

Published as a conference paper at ICLR 2025
Reszisation Rarie
Uegins counery
Traclaon ponts
Text pants
(a) ICEF of induced subgraph
(b) Preservation ratio of the subset
Figure 6: Improvement in intra-community edge fraction and balancedness for the top-ranked nodes of different centrality measures in the (Savas et al. 2018) dataset
top of the ranking. Thus, balancedness, as defined in Definition 2.3 is unsuitable, as it only captures the behavior of the worst vorst-preserved community. In this direction, we define the following metric.
Definition 4.1 (Preservation ratio). Given set of points V with underlying partition Vi...., V. and a subset C V, the preservation ratio of V w.r.t the underlying partition defined as PR(V,V)
[V] 2 i= min [SSV]] [S]
[ VTJ
That is, each ground truth cluster contributes the minimum of [Vov] [V'
VVVV TVT the term. We want observe what fraction of points are necessary achieve proportionality. The higher this value, the more clusters have a [V|/[V| fraction of the points in the filtered set. Note that the value of PR(V, V") lies between 1/l and Furthermore. when there are only two communities, any set's preservation and balancedness values are related by a fixed linear equation. Then we observe that our methods have a superior preservation ratio throughout for the T-cell dataset Figure rigure[[(b) with RN-Rank having the best performance. In fact, at the = 0.2, the baseline methods completely miss to include vertices from some communities, which we succeed at. The plots of all of the other datasets, along with summarization, can be found in Appendix D
Improvement in clustering outcome. Finally, we observe that not only does the induced graph by FV(V) have higher ICEF, but the subgraph is also better separable into its ground truth communities. To this end, we set 0.2 (the results are robust to the choice of the cutoff point). Then, apply the well-known Louvain algorithm (Blondel et al. 2008) on the original 20-NN embedding as well as the induced subgraph for each CR algorithm. We compare the purity of the outcome on these points compared to the whole graph. We present the results on 7/1 datasets in Table As before, methods again demonstrate superior preservation ratio, with RN-Rank being the best, while having comparable improvement in clustering accuracy. We provide the results for the other datasets, NMI improvement for top 20% in Appendix D As with the experiments presented here, our methods provide a superior preservation ratio throughout the ranking for almost all of the datasets and have similar improvement in ICEF as well as clustering outcome (NMI, purity) compared to the baselines. We add further discussion around the clustering improvement sawroveemenn-aalaneddeeesss tradeoff in Appendix
Datasets
BH
Se
Teell
ALM
AMB
TM
VISP 15413 PR Purity
of points Metrics
1886
2133
5759
10068
12832
54865
PR Purity
PR Purity
PR
Purity
PR Purity
PR
Purity
PR
Purity
Original
0.90
1.00 0.89
1.00
1.00 0.44
L.0. 0.46
0.00
1.00 0.48
values
Katz
0.48 1.00
0.50 1.00
0.60 0.85
0.43 0.73
0.51 0.78
0.74
0.49 0.73
PageRank (0.5)
0.51 1.00
0,50
0.69 0.84
0.47 0.77 0.72
0.57 0.76
0.76 0.98
0.53 0.53 0.71
PageRank (0.85)
0.49 1.00
0.51
0.60 0.84
0.42 0.74
0.49 0.79
0.73 0.98
0.47 0.72
PageRank (0.99)
0.45 1.00
0.50 1.00
0.57 0.85
0.40 0.76
0.44 0.80
0.72 0.99
0.45 0.73
Degree
0.52 1.00
0.50 1.00
0.73 0.81
0.52 0.69
0.61 0.71
0.78 0.96
0.57 0.67
Onion
0.34 1.00
0.22 0.98
0.50 0.77
0.77
0.24 0.73
0.35 0.82
0.51 0.97
0.35 0.75
RN-Rank
0.68 0.99
0.56 0.99
0.89 0.79
0.61 0.71
0.69 0.69
0.87 0.95
0.61 0.68
N2-Rank
0.50 1.00
0.52 1.00
0.87 0.85
0.51 0.71
0.63 0.73
0.85 0.96
0.56 0.69
Table 2: Preservation ratio of top 20% points and purity score of Louvain on the induced subgraph (compared to the entire graph) for graph embeddings of single-cell data.
10

---

Published as a conference paper at ICLR 2025
Ethics statement In this paper have focused balanced ranking, with experiments focused on single-cell RNA seq data. As such, we do not see any direct ethical concern with our current work. However, balanced ranking, in general, has the potential to reduce bias in different contexts, and future work this direction should be ethically verified.
Reproducibility statement Our paper consists of theoretical proofs on the MCPC structure, simu- lations this structure, well large-scale real-world experiments.
We have provided proofs of all of our Theorems in Appendix A
We have shared codes for the simulation and real-world data in the supplementary material. The simulation experiments can be run using the dimulation.ipynt file, and is self-contained (needed modules are provided in the zip). Due to the large size of the real-world vector datasets, we unable to share them, but we have shared the code used to run the experiments.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018.
Tamim Abdelaal, Lieke Michielsen, Davy Cats, Dylan Hoogduin, Hailiang Mei, Marcel JT Reinders, and Ahmed Mahfouz. A comparison of automatic cell identification methods for single-cell ma sequencing data. Genome biology, 20:1-19, 2019.
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56: 89-113, 2004.
Pablo Barberá, Ning Wang, Richard Bonneau, John T Jost, Jonathan Nagler, Joshua Tucker, and Sandra González-Baine Bailón. The critical periphery in the growth of social protests. PloS one, 10(11): c0143611, 2015.
Marc Barthelemy. Betweenness centrality in large complex networks. The European physical journal B, (0.38)))1333B)) 2004.
Paolo Barucca, Daniele Tantari, and Fabrizio Lillo. Centrality metrics and localization in periphery networks. Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023401, 2016.
Danielle S Bassett, Nicholas Wymbs, M Puck Rombach, Mason A Porter, Peter J Mucha, and Scott T Grafton. Task-based pore-perihhery organization of human brain dynamics. PLoS computational biology, 909):e100317) 171, 2013.
Francis Bloch, Matthew O Jackson, and Pietro Tebaldi. Centrality measures in networks. Social Choice and Welfare, (1()):413 453, 2023.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10):P10008, 2008.
Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. Maximizing modularity is hard. arXiv preprint physics/0608255, 2006.
Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On modularity clustering. IEEE transactions on knowledge and data engineering, 20(2):172-18) 2007.
Elisa Celis, Damian Straszak, and Nisheeth Vishnoi. Ranking with fairness constraints. arXiv preprint arXiv: 2017.
Pratip Chattopadhyay, Todd M Gierahn, Mario Roederer, and J Christopher Love. Single-cell technologies for monitoring immune systems. Nature immunology, 15(2): 135, 2014.
11

---

Published as a conference paper at ICLR 2025
Mihai Cucuringu, Puck Rombach, Sang Hoon Lee, and Mason A Porter. Detection of core- periphery structure in networks using spectral methods and geodesic paths. European Journal of Applied Mathematics, 27(6):846-855 2016.
Angelo Duò, Mark Robinson, and Charlotte Soneson. A systematic performance evaluation of clustering methods for single-cell maasee data. F1000Research, 7, 2018.
Andrew Elliott, Angus Chiu, Marya Bazzi, Gesine Reinert, and Mihai Cucuringu. Core- peripperr structure in directed networks. Proceedings of the Royal Society A, 476(2241) 2020.
Mustafa Hajij, Eyad Said, and Robert Todd. Pagerank and the k-means clustering algorithm. arXiv preprint WrXiv:2005.04774, 2020.
Rashida Hakim, Ana-Andreea Stoica, Christos H Papadimitriou. and Mihalis Yannakakis. The fairness-quality trade-off in clustering. arXiv preprini arXiv:2408. 10002, 2024.
Laurent
Joshua A Grochow, and Antoine Allard. Multi-scale structure and topolog- ical anomaly detection via new network statistie: The onion decomposition. Scientific reports, (1):31708, 2016.
Lukas Heumos, Anna C Schaar, Christopher Lance, Anastasia Litinetskaya, Felix Drost, Luke Zappia, Malte D Lücken, Daniel Strobl, Juan Henao, Fabiola Curion, et al. Best practices for single-cell analysis across modalities. Nature Reviews Genetics, 545 2023.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30 1963. doi: 10.1080001621459.1966 10500830. URL //www..//wwww// httt:::/ww..taadfoniineee http://www.o.o..o///////////////
com/ doi aaloo//bbslie http:///////abb.o////00//
9633 10500830
Dragomirka Jovic, Xue Liang, Hua Zeng, Lin Lin, Fengping Xu, and Yonglun Luo. Single-cell ma sequencing technologies and applications: brief overview. Clinical and Translational Medicine, 12(3))e694, 2022.
Sadamori Kojaku and Naoki Masuda. Finding multiple core-periphery pairs in networks. Physical Review E, 96(5):05331,, 2017.
Amit Kumar and Ravindran Kannan. Clustering with spectral norm and the k-means algorithm. In 2010 IEEE 51 Annual Symposium Foundations of Computer Science, pp. 299-308. IEEE, 2010.
Yingcong Li, Ciro Ramirez-Suástteuu, Richard Harris, Francisco Emmanuel Castañeda Castro, Gabriel Ascui, Tamara Pérez-Jeldres. Alejandro Diaz. Carla Morong, Daniel Giles, Jiani Chai, et al. Stem-like cells are associated with the pathogenesis of ulcerative colitis in humans. Nature Immunology, pp. 1-14, 2024.
Li Liu, Letian Sun, Shiping Chen, Ming Liu, and Jun Zhong. K-prscan: A clustering method based on pagerank. Neurocomputing, 175:65-80, 2016.
Tie- Van Liu al. Learning rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3):225-33 23,11,,,333,11 2009.
Matthias Löffler, Anderson Y Zhang, and Harrison H Zhou. Optimality of spectral clustering in the gaussian mixture model. The Annals of Statistics, 4965):206-2230, 2021.
Yu Lu and Harrison H Zhou. Statistical and computational guarantees of lloyd's algorithm and its variants. arXiv preprint arXiv:1612.02099 2016.
Henrique O Marques, Lorne Swersky, Jörg Sander, Ricardo JGB Campello, and Arthur Zimek. On the evaluation of outlier detection and one-class classification: a comparative study of algorithms, model selection, and ensembles. Data Mining and Knowledge Discovery, 37(4):1473-1517, 2023.
Chandra Sekhar Mukherjee, Pan Peng, and Jiapeng Zhang. Recovering unbalanced communities in the stochastic block model with application to clustering with a faulty oracle. Advances Neural Information Processing Systems, 36, 2024.
12

---

Published as a conference paper at ICLR 2025
Andreas Noack. Modularity clustering is force-directed layout. Physical review E, 79(2):026102, 2009.
Kazuya Okamoto, Wei Chen, and Xiang- Yang Li. Ranking of closeness centrality for large-scale social networks. In International workshop on frontiers in algorithmics, pp. 186-195, Springer, 2008.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bring order to the web. Technical report, Technical report, stanford University, 1998.
Jean-Francois Poulin, Bosiljka Tasic, Jens Hjerling-Letfe Jeffrey M Trimarchi, and Rajeshwar Awa- tramani. Disentangling neural cell diversity using single-cell transcriptomics. Nature neuroscience, 19(9): (999:1131-1144 1141, 2016.
Douglas A Reynolds et al. Gaussian mixture models. Encyclopedia of biometrics, (41(659-663), 2009.
M Puck Rombach, Mason Porter, James H Fowler, and Peter Mucha. Core-periphery structure in networks. SIAM Journal on Applied mathematics, 74(1):167-190, 2014.
Puck Rombach, Mason A Porter, James H Fowler, and Peter J Mucha. Core-periphery structure in networks (revisited). SIAM review, 59(3):619-645 2017.
Arora Sanjeev and Ravi Kannan. Learning mixtures arbitrary gaussians. Proceedings of the thirty-third annual ACM symposium Theory of computing, pp. 247-257, 2001.
Peter Savas, Balaji Virassamy, Chengzhong Ye, Agus Salim, Christopher P Mintoff, Franco Caramia, Roberto Salgado, David J Byrne, Zhi Teo, Sathana Dushyanthen, et al. Single-cell profiling of breast cancer t cells reveals risudetrs memory subset associated with improved prognosis. Nature medicine, 24(7):986-992 2018
Ashudcep Singh and Thorsten Joachims. Policy learning for fairness in ranking. Advances in neural information processing systems, 32, 2019.
Stephen J Smith, Uygar Sümbül, Lucas T Graybuck, Forrest Collman, Sharmishtaa Seshamani, Rohan Gala, Olga Gliko, Leila Elabbady, Jeremy A Miller, Trygve E Bakken, et al. Single-cell transcriptomic evidence for dense intracortical neuropeptide networks. elife, 8:e47889, 2019.
Tim Stuart, Andrew Butler, Paul Hoffman, Christoph Hafemeister, Efthymia Papalexi. William M
Mauck, Yuhan Hao, Marlon Stoeckius, Peter Smibert, and Rahul Satija. Comprehensive integration of single-cell data. cell, 177(7): (7(7))1888-190) 2019.
Birkan Tunç and Ragini Verma. Unifying inference of meso-scale structures in networks. PloS one, 10(1 (0(11)3e043333,, 2015.
Yang Wang, Zengru Di, and Ying Fan. Identifying and characterizing nodes important to community structure using the spectrum of the graph. PloS one, 6(11):e2741) 2011.
Eric Yanchenko and Srijan Sengupta. Core-periphery structure in networks: statistical exposition. Statistic Surveys, 17:42-74, 2023.
Jaewon Yang and Jure Leskovee. Overlapping communities explain core-periphery organization of networks. Proceedings of the IEEE, (02(12):19221190) 2014. doi: 10.1109//ROC.20144 2364018.
Jinfeng Yang, Min Zhang, Kathy Ning Shen, Xiaofeng Ju, and Xitong Guo. Structural correlation between communities and core-periphery structures in social networks: Evidence from twitter data. Expert Systems with Applications, 11 111:91-99 2018.
Meike Zehlike, Ke Yang, and Julia Stoyanovich. Fairness in ranking, part i: Score-based ranking. ACM Computing Surveys, 55(6):1-36 2022.
Junlong Zhang and Yu Luo. Degree centrality, betweenness centrality, and closeness centrality in social network. In 2017 2nd international conference on modelling. simulation and applied mathematics (MSAM2017), pp. 300-303. Atlantis press, 2017.
13

---

Published as a conference paper at ICLR 2025
Xiao Zhang, Travis Martin, and Mark EJ Newman. Identification of core-periphery structure in networks. Physical Review E, 91(3)x052803, 2015.
Yijie Zhang, Dan Wang, Miao Peng, Le Tang, Jiawei Ouyang, Fang Xiong, Can Guo, Yanyan Tang, Yujuan Zhou, Qianjin Liao, et al. Single-cell ma sequencing cancer research. Journal of Experimental & Clinical Cancer Research, 40:1-17, 2021.
Paul H Zipkin. Simple ranking methods for allocation of one resource. Management Science, 26(1):
34 43, 1980.
14

---

Published as a conference paper at ICLR 2025
A STRUCTURES AND RESULTS IN THE MCPC-BLOCK MODEL
In this section, provide theoretical support to the observed unbalancedness of centrality measures as well as the balancedness and efficacy of relative centrality as discussed in Section in the random graph model. We first reintroduce the model for ease of following.
The generative block model We are interested in the random graph generated by 4-block model. In this model, we are given a set of n vertices V = {ui..... .,, U/ that has partition into communities Vo. V1, and each community Ve has further partition into core Ve,1 and the periphery Ve.u- We focus on the balanced case, where [Ve.el = n/4 4 for any (e, c) pair. This is associated with a 4 x 4 block-probability matrix IP, that is indexed with (i,j) E [0, Furthermore, IP is row stochastic, ie, Ece.e) I(((e,) c), (L,'') c')l for all (i, pair.
Then, for each vertex pair Us E Vi,e and by Vi,e we add an vs + vy edge with probability P((E, c), (f', Weee""
Then, we work under the following setting.
1. c')( (e, 1)] is 21)) for all & and any c' That is, within community, constant fraction of edges going out from periphery vertex ends up in the corresponding core, and constant fraction of edges originating core vertex remains in the core.
2. k = w(llgn)) n).
3. We denote the total degree, in-degree, and out-degree of a vertex with deg(r:). (e;) and deg_(() respectively and the out-neighbors of e; are denoted as Na(u:).
We denote the resultant graph-gente generating process as BM((Va.cce.oee
Then, we are interested in the case when BM generates an (a, MCPC structure with a = 211) and B < 1. Recall that this implies that (V;,) CVo(Vi,) for E {0, and the fraction of the inter-community edges originating in the core is 3 fraction of that of the ones starting in the periphery.
Preliminary bounds We are primarily interested in the degree of the vertices generated by such graph to quantify the unbalancedness in degree centrality as well the power of our relative centrality approach. We define the map X [n] - {0, 1) s.t X = (f,c) > 0/ E VV.c. First note down the Chernoff concentration bound, which will be useful going forward.
Theorem A.1 (Chernoff Hoeffding bound (Hoefiding) 1963)). Let 21,-..:: Zn be i.i.d random vari- ables that can take values in (0, J, with E for S < n. Then we have
1. Pr Ei= 2 p c) S D(p+ello)n
2. Pr Σn 2, Sp-c) S -(p--el))p)
where D( is the KL divergence of x and y.
Next, we obtain some bounds on out-degree and in-degree of vertices.
Lemma A.2 (The graph is almost-regular w.r.t. out-degree). Let be a graph generated from
BM (e PP, Then, with probability -4 the out degree of any vertex v; E V is bounded as
k k-o(k) < deg (v.) S o(k)
Proof. Let ej, denote the indicator random variable indicating which is if there is edge from us to Uy and otherwise.
Then, deg- (v.) Eje(n) ei Furthermore, let deg denote Ejv, et,-- Then, from a sim- ple counting argument, we have Ejdee; |ioa VVeel (4, = P[X[i), (E, (E) kk.
15

---

Published as a conference paper at ICLR 2025
Next, by Chernoff bound we have
Pr(deg(--ve.) > Ve. +8. vkvlogn)
S Se- -D((eeee kt
B/deR v2, (vx)Vvl IVt.el
We note that the KI. divergence z, y is D(xllv) (n(/vv) +11 x) In((1 x)/(1 - y)), which is lower bounded by (x y)²/2n when x y. Then, the KL divergence can be lower bounded as
D E.
vkvllogn// Ve
Veeel
=D Eldegr- vV, (v:) (v:)) + Vkylog n / 0.25m
Eldeg(- -n. (n.) 0.25n
64k log n
2 (v))
64k log
kP[X[us), (e, c)
216logn
A.c
That is,
Pr(deg (w:) (w)) > [P[ (4.c)] &VKy/oog In -16
Applying it for all (l, e) and summing up we get
Pr(deg((1;) 2 k- Σ F[X (f,c)] + 32V log n) S 15
Here note that Exe,)) [1] c)] 1 and that Vlylogn o(k) as k w(lon)). This completes the upper bound. The lower bound follows similarly.
Then, the distribution of the in-degree of the vertices can be obtained follows. Lemma A.3. Let G' be graph generated from BM(VVcc(c.oggoo.y.....AA k). Then, for any vertex es E V, the expected in-degree of v; is
E deg (u:)] = k Σ cI(C',)),,1) (0,c')
Proof. Let the vertices of V be denoted as v1...., Un- Let eij denote the indicator random variable indicating which is if there is edge from o; Uj, and 0 otherwise.
First, note that all e., are independent. Then, Pr(e,,) 1)
F X Mxul
Then, summing on the
expectation we get, for any
P(C, X
E(deg+ (w:)
Eleyd
Σ
Ve.el
[xx]]l
jE[m]
(0,c))
Σ
k- Σ P((E'c)))
n/4
(0
Then, have the following bound the indegree of the vertices.
16

---

Published as a conference paper at ICLR 2025
Lemma A.4. Let G be graph generated from (M((V.))c.ee(0..p.. any vertex is bounded as
Then, the in-degree of
Pr( deg+ (v) B,deg (v)]l 8- Vllgon In
Proof. We obtain this using Theorem A.1
For the upper tail, we have
8- 8 Pr(deg+ + (v) Ejdeg, [w)] (v)]
Vly logn) S L D000ddddee.0/////a/a//////////11 (wl//n
We note that the KL divergence between Bernoulli random variables x, (x = x In(2x// /2) - (1- x) 1n(11=z)(119)) which lower bounded by (x-y)² y)3 when x > y. Then, D(E (v)) /n)
4 Vlylog ni
can analyzed as
D(Eldeg, httk///++..///////////////// ||E/deg (v)]/n)n
64k log n
2 [dee (v)
64k log n k. Ee, P((E.)),,
16 log
Σ P((())),
Then, substituting, we get an upper bound of n 16
This, along with the fact that the sum of entries of any column of is Q(1), gives the following fact. Fact A.5. Let G be graph sampled from (M(Vicc where k w n) and
P((E, c), 1)] = (2()). Then for all vertices Ve,1, we have deg+(1) = (2(kk with proba- bility 1-n
Proof. This is straight from the fact that E[deg,, (v:) = Q(k) and the tail deviation is Vle o(k) with high probability.
Then we make connection between the concentration of any of the core/periphery blocks and degree of each vertices in the core.
Lemma A.6. Let be graph sampled from BM((VV..crr.))eg......... where = w(logn) Then, for any vertex U; E Vi.c we have with probability - n-1
deg, (w:) k(1 + o(1)) + k (1
Proof. Let first recall the definition of concentration. We have CCa(S) (E(S, E(S, S))/E(SS V).
First, note that E(S, V) = k(1 [Ve,l. Also, let deg(+.s) (1) denote the number of edges connected to from the set S.
Then, we have
CCo(Ve,)) Eosevs deg.(v;) Emer. deg(+.V..))1)) E Enevr, (c.
o(1= VV.cl
Emeri.. deg, (vi) - -E,, Enjev deg(+ deg(+.v..)) (1.)
k(1 + +o1)) [Vecl
ΣmeVi. deg, (v:) - k(1 + o(1)) IV.d
k(1 = ( - IVe.l
That is,
CVo(Ve.))
Σ (v)
(2)
|K(1 + o(1)) Vecl
weV..
17

---

Published as a conference paper at ICLR 2025
Then, can use the fact that the in-degree of each vertex in Ve,e is bounded tightly from Lemma A.4 Applying an union bound we get that with probability 1-n n6,6,, deg, (vi) ( (vy) s 8v BVkvlogy for any De Uy E Vi.c
Then, with the same probability, for any vi E Ve,e, we have that VVe Expevi, deg+ (v/) & /lg.llloo/iv..
deg+ (vi)
Furthermore note that as = wlogn)), we have 1 o(1). This implies with probability 1 for any U/ Vi,c.
[k(1 + oo()) Ve,el deg+ (16) -1) 1) - 322V/olorr n/k 1
Vi.el
(Ve,))
(V2.)
1:(1 + o(1) deg+ (v) ( o(1)
1
At1 = o(1)) deg+ (v:) = 1- (Ve - o11
deg+ (u:) = k + k. = o(k)
deg+ (v,) k-1 o()) k CI
This completes the proof.
A.1 PROOF OF THEOREM 3.2
Now, we are ready to complete our first proof. First, we know that deg(v;) deg. (o) + deg- (v). where deg (v) k + o(k). Then Lemma A.6 directly implies that with probability
deg(u;) = 2k + (VC, + olk).
Here, Fact A.S dictates deg, (v) 22k)) and simply applying Equation 1 we get (Ve((Ve.) ((1). Then, we can write that deg(v;) = k - proof.
(CCCoV 1D), which completes the
A.2 MOST CORE POINTS IN THE 1-STEP N-RANK HAVE HIGH SCORE
We first show that all the points in our block model with MCPC structure assigned a high score in the 1-step N-Rank algorithm (Algorithm) D.
Recall that for 1-step N-Rank first obtain the score F(u;) for all vertices n; V. It is easy to see, that F(t;) = deg, (u:) for all vertices.
Then in the next step, for each vertex 8ú select S,, the set of vertices with higher F score. F(e))
Then, we obtain F(v.) average..es., F(us]*
Then, we are ready to prove that ((v)) is between 1 o(1 and for any core vertex Vs which quantify in the following Theorem.
Lemma A.7. Let G be a graph obtained from the MCPC block model with A: = w(log n)) resulting in an (9(1), o(1 /k)) MCPC-structure w.r.t to the core-periphery blocks. Let F(v) be the score of the vertices as per Algorithm 1 for 1. Then, for 1 o(1) fraction of core vertices v; V4,1 for
any E, we have 1 o(1) < Fat (z)) 1.
Proof. Recall that the graph has (2(1), o(1/k)) MCPC structure. That is, CC&(V,.) 2 Ve for any (e, (") pair where > 0 is constant.
Let CC the minimum concentration among the cores. Then, Lemma A.6 dictates, that with probability 1 - -n
If o E Vi, then dog, < k + k. (CC - a:) + ol)
On the other hand, for vertices have
18

---

Published as a conference paper at ICLR 2025
If os E Ve,1 then deg+ 2 k + k CC o(k)
This implies that for any us V2, and vy Ve,o, Fo(1s) (oyry) with high probability.
Thus, in Algorithm| Then we select Se, for any & E V1,1, it does not include any periphery vertices. Then, show that the final score of all core vertices will be pretty similar.
Consider any Ve,1- We first note that B = o(1/k). Then it is easy to see that PV(V,1, Ve,1) = q = o(1/k) for any e, E.
First we count the number of vertices in V2,1 that has an outgoing edge to Ve, for some &l + l (that inter-core edges originating Ve,1- This can be upper bounded as Ev, deg(+,Ve,,) .).. (v:). This
sum has an expected value of [Ve,1- [e (1/(1/k) = o(VV..)). With high probability this can also Veal
be upper bounded by I((Ve, + vVVa Vaallllonn--- v((V),)))
Let St,1 denote the vertices in Ve,1 that do not have any outgoing edge to Ve, For any such vertex, m ((, (e)(M))) S k. E(e,) c((e'c'),xpp + o(k).
On the other hand, Fo(e, 2 k. P(e,s)P((E.c))
P[( X (kk)
Then we have
P(v:) Z k: Ei
(k)
k ".E P((E,,) [ + (k)
2kk(k)
=1 1 k. E(e,e) X o(k)
1 o())
[As we know k. Σ P(((CC)) X (())
(8,
This completes our proof.
A.3 N-RANK HAS HIGH CORE PRIORITIZATION
Next, show that the periphery vertices have lower score than almost all core vertices, which indicates high core prioritization.
Lemma A.8 (Separation between score of cores and peripheries). Let G be a graph sampled from BM((Vecdde.ogggo.pp... k) where k (log n). Then, for any v; E Ve, (a periphery vertex), F(e:) < mine,ev.. F(ez) with high probability.
Proof. Let U; E Vz. be a periphery vertex s.t. CC(V2,) = CC'. Then, its neighbors consist some vertices and other periphery vertices.
Let hi be the number of neighbors of u; that is a core vertex. As PP((e,)) 0), (4) = 2(1), we know k = 1(A).
Furthermore, U2 E V2,1 deg, (1;) (which is its F(u;) score) is lower bounded by + (CC +
a) ok)) On the other hand, deg, (1z) < k k. CC + o(k).
19

---

Published as a conference paper at ICLR 2025
Then, average,, E3, F(Uz) is lower bounded by
k min deg, (1z) + (deg (v:) - ki) deg+ (vi)
Sy nV21
averageu;es, F(u))
deg_
k1
2 deg (v:) + degn;
min UyE8s,nee
deg (vz) dog, (u;)
kn
2 dog+, (1s)
(
[Using the lower bound on deg, (vy) : us E Ve,1
deg..
and upper bound on deg (v:)
deg. (v:) + C3 k
[For some constant C3]
deg+ (15) + C4 (w:) [For some constant C4 as deg, (u:) = O())
2 deg (1:) + -C4)
Then, have F(e:) S deg, (v4)(1+44) 140, with probability 1 o(1/n). That is, F(u;) is upper bounded by a constant less than with very high probability. On the other hand, Lemma A..7 dictates that F(;)) value of core vertices is upper bounded by o(1). Then there exists a large enough no such that for all no there is separation.
deg,(v.) (v.)
A.4 EXPECTED BEHAVIOR OF THE TOP-RANKED POINTS OF N-RANK
So far, we have shown that while the degree of a core vertex is directly proportional to its concentration, the N-Rank score of core vertices high (1 o(1)) irrespective of the concentration of the core.
Now we prove Theorem 3.3 which shows that expectation, roughly the same fraction @ (1] of points from each core have a score of This is a provable improvement on degree centrality in terms of balancedness.
A.4.1 FACTS ON THE BEHAVIOR OF THE IN-DEGREE OF THE VERTICES IN AN MCPC BLOCK MODEL GRAPII
First, we make some further observations (and recall some previously made ones) about the in- degree and the out-degree neighbors of the vertices. For simplicity, we define iP(ee, c], [C', cdl) = [er (P([,, c), c().
The in-degree of any vertex can be seen as a sum of independent Bernoulli random variables (the possibility of edges), with the deg (v)) having the same distribution for all U, E Vi,e as follows.
Let Binom(n', p') refer to the sum of n' i.idd Bernoulii variables with probability p' of outputting Then,
deg+(v:)
Σ Binom (iee ((C,,)
(3)
2. For any core vertex U E Vr,1, deg. (v:) is greater than all its out-degree neighbors from periphery (this is straightforward see from Lemma A.8 with probability 1 o(1/n).
3. For any core-vertex U; Ve,1 probability that it has out-going edge to Ve is o(1).
4. Without loss of generality, we shall prove the results for the core Vo,1- The same result applies to any core (of course, the dependencies on change based on which core we consider).
Next, prove useful relation between the degree of vertex and degree of a neighbor.
Weak correlation between in-degree of vertex and in-degree of their neighbors.
20

---

Published as a conference paper at ICLR 2025
We note that the in-degrees of Ne(() n Vo,1 (N₂) are slightly different from Equation (3) This because one edge >> u is deterministically there. For simplicity let Pt,c = [P(( c), (0, 1)). Then we have
1. deg+ (V) ~ X = Binom([Vo.l) PO,1) Po.
Binom Binom([Ve,,llaa (VVccll (0.0)_(01)33(0..)))
Σ
(as before).
Xo.1
2. deg+ (u) 1 Y = 1+ Binom (Vo.1
1, 1,00,1
Σ (0.0)((01)){(000))
Binom(Vee.l
Yo,1
(slightly modified)
Next, we note down the following useful equality
n' p' Pr(Binom(n' - 1,p')) (=pp))==) --
Pr(Binom(n's ,p) t)
E Biiom p')l Pr(Binom(n' - 1,p') = =t-1) 1)
Pr(Biioomn'' p²)
Further, note that E[X k (O, 1), (0, 1)]. Further, as (log n) and ((, 1), (0, 1)] 2(1).
a simple Chernoff bound applied along the lines of Lemma A.4 implies that there exists e = o(1) such that
Pr (11 (1--e) e) & Xo,1 & (1+ +) e) 21 n
(4)
Similarly,
Pr ((1 (1- & Yo, $ (1+ c)E 2 21 -1-n
(5)
Let this range, [[1 c)E (1 + e), be called R. Similarly we define R w.r.t Y0.1-
Then.
Pr- = 1|Yo, E R$) < Pr(X K R2) < (1++) Pr(y t 1 E R2) (6)
A result on bounding f'unctions of pmf's.
As we shall see, key we shall control in our analysis would be the following kinds of sum, specifically D Pr(X = 1) Pr(X < t) and En Pr(x f) Pr(X < 1)* where X is discrete distribution with the support (O..... n). In our analysis, X will be the r.v. that describes the in-degree of vertex.
In this direction, we prove the following useful lemma.
Lemma A.9. Let X be any discrete random variable with the support set {0, [0.....n]. n]. Then, the following holds for any k < n.
n Σ
Σ =t( =) Pr(X < 2 2=0
- 1/n < k
Pr(X = Pr(X s x)* + 1/n (7)
2=0
Proof. We know X is a discrete random variable with n possible outcomes. Then, we can extend the probability distribution function of x a continuous function such that f(i) Pr(x
1) for any i E [t, + 1). Then f can be approximated by a continuous function / such that fat1 [f(x) dx=)dd> < - for any constant For now, let us continue with 4
This further implies that | f())dr = + 1/n". This is because f f(x)dr = (as f a step function representation of probability distribution function (corresponding 2:).
Next note that
Jo f(I)dt 1/n2 < J0¹ s(I)dt & 5o f(()dt 1/n2
21

---

Published as a conference paper at ICLR 2025
Furthermore, Pr(X I =)= So f())dt and so on. Therefore,
== fo+ f(t)dt for any t E [n]] This is simple to as Pr(X 0)
Pr(X & [x]) I f(t)tt [x])
Pr(X & [x|) 1/n² - S f(t)dt & Pr(X & [x]) + 1/n
Then, define F(x) So (t)dtt the anti-derivative of f. Simply replacing the definition in the equation above gets us
Pr(X S 1//2 s F(x) S Pr(X S [ar] + 1/n2
Also note that Pr(X & 2), Pr(X < and f(z) are all non-decreasing functions on 2. Now, we are ready prove the bounds. On the right side, have
Σ Pr(X=x)) -Pr < xx)
n+
(%a))
(10) 1(1)ee) do
j(x)
(1" F(oaa)) & de
f(x)
f(z) (f, f(t)dt + 1/n²) de
([""sOsdee + +k/n²) dx
f(z)
m+1 ((x)
([ooatt)) dx foa k/n
0
$ n++
J [(x))(x))dr + 1/n²
Next, note that
J m+1
F(z)k+1
1 1/n2
[<))
(F(m) F(O)) <
(8)
k +1
k+1
1: +
Putting it on the equation above we get
n Pr(X= = x) Pr(x < x))* S
+ 1/n2 1/n < 1
+ 2/n2
1 +
+
1
Pr(X x) Pr(x < x² 2/n2 <
k ++1
22

---

Published as a conference paper at ICLR 2025
Next, prove the other direction. We have
Pr(X -r((
& x))
(Lo f(t)dt) 1
n+1
f(x)
de
n+1
(1 F(taat) dr
f(x)
n+1
(T, s(t)dt s(t))t 1/n²) -1/=t) dr
f(z)
n+1
(1," s(()det) - k/nn dx
f(x)
n+1
((staatt) dx S (ntl
f(x)
k//ndx dr
n+
f())F(x)dd 1/7²
Then applying Equation
we get
Pr(X P < 2))*
k+1 22/n²
-=0
Pr(X = x) Pr(X < <))² + 2/m
k
m=0
This completes the proof.
Next, we shall the aforementioned results to prove an upper bound on the number of core vertices in with N-Rank score 1.
A.4.2 UPPER BOUND ON THE EXPECTED NUMBER OF CORE VERTICES WITH N N-RANK SCORE
Without loss of generality, 1et v be any core vertex in Vo,1- To further simplify notation we denote
Pr.. = P((E, c). (0, 1)].
We obtain upper bound the probability Pr(F(v) 1) for any Vo,1- Let this be defined by the indicator random variable 1,, which is v E S and otherwise. Then we have E[# : E Vo.1. F()) = 1] = VVoal [[1,]. We focus on a specific case (that is simpler to tackle).
B B = Pr(1, =)
Pr deg (v) > max deg+(())
wENo(1)
< Pr deg (v) MENo(e)nVo
dog+ (1)
[Only compare with neighbors from the same core]
For the sake of abbreviation we define N,, == No(u) Vo.1-
23

---

Published as a conference paper at ICLR 2025
We shall further condition the number of neighbors e has that has the same degree as The reason for this step is more technical. Essentially, we want to use the inequality of LemmalA but we have an upper bound only on sum of terms that look like Pr(X (Pr((X < t)) Here roughly Pr(.X t) controls deg+ (v) being i, and (Pr(X < f))* controls the probability that & of its neighbors have lower degree value. Therefore, need to consider the case of the neighhors that may have the same degree. In this direction, we define (vv) == {u : u E No((v) n Vo,1, deg+ (u) deg+ (v)), and get
Pr (ee+(()) (v) >
max WE V
dex+ (u)
=Pr [eg+ (1) max deg+ (u) NEN,
=Pr((Z(u)] 5a) Pr (c) 2 max deg, (v) I <a) weN,
(9)
Pr Pr[[Z(u)] a) Pr (eg+(t) 2 max dey dey+ (1) uEN.
Srr (e)+ max deg (u) Z(v) s a) + ((Z())))) >
oEN.
Then, we prove the two following lemmas. Lemma A.10. Let Z()) == {u: u Nc(v) Vo,1, deg, (u) deg+ (v)) that is the neighbors of in Vo1 with the same in-degree as v. Then, Pr([Z(u) > 10e k2/3) o(1/k)
Proof. First recall that deg (v) is sum of n independent random Bernoulli variables with [(deg,(u)) S C-k for some constant C. Then, is easy to infer that [0. Pr(deg, (v) S 2C Furthermore, note that Pr(deg_ (v) & [E[deg, (v)) - -4Vkk/loon, Eldeg, (v) +VVKklog < vk"
Furthermore with probability - 1/nn,, (N)(v) n Vo.1 $ (1 + o(1)). Then conditioned on this event, we first bound the probability Pr([Z(v)
We get
Pr([Z(v)|= = < k (0)20
10
20 vk- Vlogn-
Vkc
c k
10 Vk)
10e k avk
20 Vi. Vlog.
20 VTe Vlogn.
Then, as per the proof statement let 10e k2/3 Then we get,
Pr([Z(u)| = 10e 1/233)
42/8
1
<20 Vh. Vlogn n
k1/3
13/3__ -6
k3/3_,
<20 -T. v log n
1 1
12
11/3
k
11/3
Then, Pr([Z(v] 2 10e 1,213) < k: Pr([Z(u)]
= 10e
2223 (as Pr( [(()] = () is decreasing
function on t) and get
12/3
13/5
1
1
Pr(1Z(0) 2 10e k2/3) <
<
o(1/k)
k:/33
k1/3
24

---

Published as a conference paper at ICLR 2025
Next we bound the second term, Pr (deg+ (v) 2 maX deg+ [(0) - C12/3)
Lemma A.11. Let be core vertex. Then
1 o(1) P((0, 1), (0, 1)
Pr [dgg+ (v) 2 max deg+ (w) ((0)= S Ch2/8)
ueN.
Proof.
We want to bound Pr (deg+ (c) 2 maX deg+(u) (u) Z(u) - C12 Recall that [c()) n
Vo,1 = P[(O, 1), (0, 1)] k. Let this value be denoted as à for convenience. Then (Na n Vo,1 lies within (1 + o(1)) with probability 1 - n Then we get
Pr
deg (v) 2 max deg (w) ((v) S Ck2/3
uEN,
Pr
max deg (u) NEN: deg+(v) 2
[(v) S CK2/3 |No1 2 (1 ((U)))
+Pr(INol (1 -(1))
Pr
deg (v) max deg (w) [(v) S Ck2/3 No 2 (1 (1- o
+1/12
N
Now, let the event of ((v) S CK2rs, 2 (1 - o(1) jk be denoted as E. Here note now we are working under the condition that there are at least k' = (1 o(1)) Ck2/3 neighbors of y in Va,1 that do not have the same degree as v.
Then, we have
Pr(deg- (v) 2 max
EE) < Pr(deg+ (v) 2 max E, 00, E R2) + Pr(æo.1 & R.) NEN,
NEN.
<Pr(deg, (v) Z max E, To. E R2) + 1/n2
From Equation
MEN.
Continuing, get
Pr(deg, (v) max deg, (u) E, 20,1 R,)) MeN.
Pr(X 1/x E R.) Pr(Y < 1)
(1 + e) Pr =t -t1 Re)) Pr(Y <t - 1)a
From Equation 6
1=1
(1+c)
Pr(Y =t) (Pr(y < 1))
[Pr(A]B) & Pr(A)/Pr(B))
Pr(Yo.1 Re)
1=
n-1
<(1+1.10
Σ
Pr) (Pr(y < ())x
[Substitute Pr(Vo,1 E R2) from Equation
Finally, from Lemma A.9 we have Σn Pr(Y =t) (Prly < <t))² S 1 +1/n3.
Combining the results we get,
Pr dog (w) 2 max deg+ (1) |2(w)] s C1213) WEN.
1
P(Oo, 1), (0, 1)] - C12/3) + 22/2
+ o(1)
P(( 1), (0, 1))k:
25

---

Published as a conference paper at ICLR 2025
Then, continuing from Equation ( get
Pr(deg+ (v) 2 max deg. (u)) - Pr
deg+ (v) (0)++()= 2 max deg, (u) sa) + Pr Pr((((u))
"eNa(")
NEN,
+ o+)(1)
P( 1), (0, 1)]A: + o(1k)
1 1 o(1
P((0, (0,
1 Vo.l = V., for F(v.) = 1H0 -
P[(O, 1), (0, 1)]A
(10)
Note that as the upper bound holds for any core V4,1- Next we establish a lower bound, which we find slightly easier to get (and is still within a (1 - o()) factor the upper bound.
A.4.3 LOWER BOUND ON THE EXPECTED NUMBER OF CORE VERTICES WITH N N-RANK SCORE OF
Next, we want to obtain a lower bound on the expected number of core vertex with F(v) 1 irrespective of the core concentration. Here, re-emphasize that our upper bound was also derived in the same manner.
As before, we are interested
Pr(1, = Pr (deg+(u) (v)
max deg, + (v) (e)
Now, we consider two events
I)
E = deg (v)
max (o(e))((o.ouvv..)
deg (u)
This is the event that e has higher in-degree than all out-neighbor that is periphery vertex. Note that this happens with probability (1 - O(1 (1))) from Lemma A.8
2)
Eg = (Na( n Vi,1 =0
This implies that has no outgoing edge to another core. Note that Eg happens with probability 1 (1) B = o(//k).
Then we have
Pr(1, = 1) 2 Pr(F) Pr(1, =1 Fl F2)
2 (1 - (1)))((11(())))) Pr(1, = Ei, E2) 2 (1 o(1) Pr(1, = 1
E1, E2)
Then, we focus on the conditional probability of the vertex having the highest degree, which is as follows
Pr(1, = 11,,-=1EE,E5 Ez) = Pr deg (dg_(v)) (v)
max deg, (u)
vENo(e)nVo.
Let 1. Eg i,. We then focus on this event for a fixed value of (No(v) Voal, i...
Noll Vo,1 k' We can write it down as
Bii Vo,l = =1 Σ
= Pt
1
t=0
As we have a lower bound in Lemma A.9 this form. we do not need to consider the case of neighbors having the same in degree separately, as we did for the upper bound.
26

---

Published as a conference paper at ICLR 2025
Furthermore, for the upper bound, switched X to Y through simple conditional probability upper bound of Pr(A] B) & Pr(A)/ Pr(B). Unfortunately, there is no such trivial lower bound that need
usable here. Therefore
precise analysis.
Recall that X is a sum of many binomial distribution (each corresponding to one the blocks). In the previous section we used X to obtain upper bound. Let each of these binomial r.vs be denoted as Xe,--
We first define the ordered set T (to.o: t, t1,0.tioo,.. t1,1) and let summ Eier denote the sum of the elements in T.
Then have,
1)=
E
II Pr = 440
T:Ta=
Σ
II Pr(Xee = te,e)
Σ
II Pr(ex = te,c)
T 10,1 R
T to.1 & R T Tuum t
Tsum
Σ1
First we show that Eg very small, which is easy to show.
2i = Σ II Pr(Xe,c te,c)
T 10. Re
T Tuum- t
S
Σ
Pr(Xa,1 = 4011)
T:o, 1 RE Tum =t
Σ
[Applying Chernoff as in Equation 5)
8
T:o, R Tam=t
there are only 4 elements each has t < n possible choices
< n
Next, we look at Σj. Our goal is to switch to as before (with more care as now we need lower bound).
Σ
Σ
P = te,c)
T: to,1 E R. Tsum =t
Σ
Pr(Xo.1 to,1) Pr(Xo,o to.0) Pr(X1,1 1111) Pr(X1,0 t1,0)
T: fo,1 E R Tsum =
Σ
Pr(Xo.1 = to.1) Pr(Yo. = to,o) Pr = f1.1) Pr(Y1. = t1.0)
=
T to,1 E R Tsum =
[s apart from Vo.1, other Xt,c and Yt, are identical (1-e) = -//0.1 E RT) < Σ S (1 + Pr(Y = -//0,,1 E R2))
The last statement comes from the fact that in range of fo.1 1 E Ry (1 - e) Pr(Yo.1 to,1 - Pr(X0.1 fo.1) & (1 <) Pr(Yo,1 = to.1 - 1). Furthermore, using the calculation of Σn directly implies that Pr(Y tlyu,1 RT) Pr(y ((Y,)) 1/n².
27

---

Published as a conference paper at ICLR 2025
Combining these calculations get:
2
Pr(X = t) 2 ((-))
=t 72
(II)
Then we have
|[i.)l Vo.1 =
Pr(X 1(-
Σ
((1 (1-6) Pr(Y = - 1) - 22/ (Pr(V St 1))
Σ [1 Pr(Y = t)(Pr(Y - 22/
L=
2
Σ
Pr(Y ()PP( 20))* -2/1²
1=0
2 (1 1- o(1) 1=)(1)
- 2/
[Apllyng the lower bound from Lemma A.9
K
1 1- o(1
[As o(1)
Then, compiling all the results we have
E 2 (1 o(1)) 0(1/n)) 0(1/n)))
E
[o.) Vo,1l k|
(No(e)rVV,11
(1-o(1) o(1) 2//n²
(1 - o(1) (Ne(m)nVoal
E
k'
(1 (1-o(1)) o(1))
2 (1 o(1)
E
2/n2
[NG(uinVo.l
1'' +1
(1-o(1))
((,, 1), (0, 1)) + o(1)
(1 -1-00 o(1))
P(O, 1), (0, 1)]k
As had chosen the to be Vo,1 without loss of generality, the result holds for any core. We can thus conclude
E [ive F(x)) = =1]]]
(1- P((E, (C,
(12)
A.4.4 PROOF OF THEOREM 3
Then, we can summarize the proof directly from the upper bound obtained in Appendix A.4.2
(concluded in Equation (I0) and the lower bound obtained in the Appendix A.4.3 (concluded in
Equation [22
28

---

Published as a conference paper at ICLR 2025
B META ALGORITHM
Algorithm 2 A meta generalization:
Meta-Relative-Rant Rank (1, y;
Input: Graph G(V, E) and meta veta-parameters t, y, Obtain F(O) as follows.
x- 1n for in do
(#Vector of all ones)
f- A
Obtaining initial centrality score)
end for (1;) < s(i]
(1. Obtain a h-hop N
for y E do
S.a) + {u (v), (w) > (v)
( (v) (verage[F( (v)
s
end for
(2. Recurse the process times)
HG < $(0), counter t- while counter < x do for V do
((9) + {u: U (o,( > H(v))
(v)) (verage(H(w)))H[
wEs(
end for
H H, counter +- counter 1.
end while
return
We design the algorithm meta-algorithm by extending the idea of N-Rank (Algorithm in two ways (as we briefly discussed in Section 3
1) There may be periphery vertices in the graph that have a high F& value compared to its 1-hop neighborhood. To mitigate this issue, we can look at some y-hop neighborhood NG. of when selecting the reference set.
As look larger set of vertices for comparison, this method less likely to report local maxima as core nodes and thus cause increased core prioritization. On the other hand, if we look at a vertex from a sparse core, then a large-hop neighborhood may contain more vertices from other cores, and using them in the reference set reduces their final core. This leads to potentially a lower balancedness.
2) We have observed that our N-Rank approach increases the balancedness the initial centrality measure FG. In this direction, N-Rank value and then feeding it back to the algorithm as the initial centrality measure to further increase balancedness. We can apply this recursive process any
recursively apply this process by first calculating the y- y-hop
many times.
The idea is that if the hopop N-Rank has higher balancedness than the initial centrality measure, recursively applying the process should result in increased balancedness up point. On the other hand, such a method can also amplify any loss core prioritization due to y-hop N- N-Rank, and thus lead to potentially lower core prioritization.
29

---

Published as a conference paper at ICLR 2025
B.1 THE CHOICE OF T FOR THE INITIAL CENTRALITY MEASURE
In the first step of our algorithm, we obtain an initial centrality measure F(t) by calculating the total probability of random walks starting at different vertices and reaching a particular vertex. When t= 1, this converges to the in-degree of a vertex (up to some multiplicative factor). When & is larger, this can be thought of as a truncated variant of PageRank without any damping.
In our experiments, we set t 1 for the graphs generated by the MCPC block model and = log V| for both concentric GMM as well as real-world experiments. This is based on the intuition that t is large, then it can help discard local minima. In real-world data, there may be some periphery vertices that do not have any outgoing edges to a core and, as such, can have the highest F()) value among its outgoing neighbors, thus obtaining a score of 1. A larger t can solve this issue.
On the other hand, if is too large, can further increase the F(t value of core with higher concentration (as more random walks will be trapped there) and can reduce the balancing effect of the subsequent steps.
We further note that while we choose t = log VV. the final outcome is not very sensitive to the choice of f, and for most graphs, the results for 3 I S log V were quite similar. Finally, while we do not need to do a hyperparameter tuning for our real-world experiments (fixing t = log [V] for all experiments), it is an important direction to consider whether a data-dependent value of t can be obtained.
In general, observing the impact of using different initial centrality measures on the overall perfor- mance is an important direction.
C A MORE COMPLEX SIMULATION MODEL: THE CONCENTRIC GAUSSIAN MIXTURE MODEL
Mixture models are one of the fundamental statistical models to study the inference of communities in data. Here, each underlying community has center, and then points for that community are generated with respect to distributions with mean as the respective center. When the distributions are Gaussian, the model is called the Gaussian mixture model (GMM) (Reynolds et al. 2009), which is widely studied in the clustering literature (Sanjeev & Kannan 2001; Kumar & Kannan 2010 Lu & Zhou 2016; Löffler et al. 2021). In this section, extend the GMM in natural way to incorporate an MCPC structure.
Definition C.1 (Concentric GMM with two communities). There are two centers CR E TRd / E {0, 1]- Each center associated with two d-dimensional isotropic Gaussian distributions with the center as its mean and variances σe,1 and σe,0 respectively, with σe,1 2 1.10 We denote the distributions as D(O and D respectively. We sample ne, points from each distribution D( and collectively note them as Vz.. Then, the two underlying communities are V = V2,1 U Ve.0-
For simulation, set d = 20, |Vyll = 2000 for all i, and the variances of the distributions are set where 1 < < 3. Furthermore, we choose the centers as two so that there an overlap between the two communities. Then, we make the following observations.
00.1
00,0
01,1
T1.0
as
0.1
0.3
0.0.1
7 0.3
i) The 20-NN embedding has an (a, B) MCPC periphery structure, with the points sampled from the lower variance distribution 00.0 and .1, forming the cores and the rest being peripheries.
ii) When 7 = 1, the two communities are symmetrical and we have (2, 0.3) - MCPC structure with both cores having similar concentration. Then all core-ranking methods have high balancedness, noted in Figure [ and when we select the top points from the ranking, the induced subgraph has a higher ICEF, as observed in Figure 7(a From hereon, we set := log n step in the first step for all our algorithms to avoid local maxima when obtaining the initial centrality scores.
iii) Cores with different concentration. Next, we observe that if we set y = 1.5, then one core has a higher variance than the other, and the corresponding vertices in the graph have a lower concentration than the other core. Then, traditional centrality measures indeed have a lower balancedness, and our methods perform relatively better, with RN-Rank having the highest balancedness value, as noted
30

---

Published as a conference paper at ICLR 2025
lrgelend of
decan sucliie Ioland
(a) Cores with same CCo (b) Cores with same CCG (c)
Cores with different CCo
(d) Cores with different CCG
Figure 7: Improvement in ICEF, and balancedness of of top points for different ranking algorithms in concentric GMM
Core ranking in the concentric GMM
Core ranking the concentric GMM
Ketz Centrality
0.5
PageRank (0.5)
PageRank (0.85)
Total balarcedness
Awerage ICEF
PageRank (0.99)
Onion decomposition
0.
0.68
Degree centrality
N-Rank
07-
RN-Rank
N2-Rank
09-
Difference between concentration of the two cores
Difference between concentration of the two cores
(a) Average ICEF
(b) Balancedness
Figure 8: Average ICEF and total balancedness of ranking by centrality on the 20-NN embedding of data generated with the concentric GMM for different instantiations of the model
in Figure 7(d) Furthermore, we note that all methods provide similar increase ICEF upon core selection in Figure [c with N2-Rank being slightly better than our other methods, the same as in the random graph model. We provide a more detailed simulation result for different values of y in Appendix to further support the balancedness of relative centrality.
Next, we do a larger-scale simulation to concretize this observation and further look the ICEF- improvement vs. balancedness tradeoff of our methods. We use the same setup in Section C but run our methods on graphs generated with several different parameters.
We set d = 20, size of each core or periphery Vz,- = 2000, and the two centers being (0) and C2 = 0.3 [1)dd Then, we set the following variances of the distributions, parameterized by 7.
00.1 0.1, 01,1 0.3 and 01e 700 c. Then, we generate Ve,e many points with a d-dimensional isotropic Gaussian with C₂ the center and dt.. variance, with the cores being generated with lower variance distribution than their corresponding periphery.
Then, when 1, both the cores (and the peripheries) are generated from distributions of the same variance 0.1 (0.3 for the peripheries). As a result, the cores have similar concentrations, and the graph satisfies (0.2, 0.75) structure. Then, the average ICEF of the induced subgraph, as well as the total balancedness of the ranking of all methods, are very similar.
Next, we increase y slowly, resulting in the variance of the second community being higher both for the core and the periphery. The results are captured Figure g While the average ICEF of all the methods is pretty similar (within 4%), the traditional centrality measures have significantly higher balancedness, becoming as high as 20% for =
Furthermore, among methods, RN-Rank seems have the highest balancedness, whereas N2- Rank seems to have the highest ICEF. This tradeoff indicates the possibility of more interesting algorithms via the relative centrality framework going forward.
31

---

Published as a conference paper at ICLR 2025
Name
Abbreviation
of points
of communities
Source
Baron Human
BM
8569
14
(Abdelaal et al.
2019
Baron Mouse
Baron_Mouse
BH
1886
13
Abdelaal al.
2019
Muraro
Mu
2122
Abdelaal ct al.
2019
Segerstolpe
Se
2133
13
Abdelaal al.
2019
Xin
Xi
1449
4
Abdelaal et al.
2019
Zhengmix8eq
Zh
3994
Duò al.
2018)
T-cell dataset
Tcell
5759
10
Savas et al.
2018
ALM
ALM
10068
136
Smith al. 2019
AMB
AMB
12382
110
AAbdelaal et al.
2019)
TM
TM
54865
(Abdelaal al.
2019
VISP
VISP
15413
135
(Smith al.
2019)
Table 3: Details of the scRNA datasets we use
D SINGLE-CELL DATA
Datasets First, we provide detailed description of the datasets we use in Table Note that each dataset has annotated labels that use to verify the performance of our algorithm. Next, we describe the experimental setup. For each dataset, we first log-normalize it and then apply PCA dimensionality reduction of dimension 50, which is standard pipeline in the single-cell analysis literature (Duð) iet al. 2018). Then, we obtain 20-NN embedding of each of the datasets and obtain a ranking of the vertices via both the baseline and traditional centrality measures approach. Then, we select some c-fraction of the vertices from the top of the ranking and calculate the intra-community edge fraction of the induced subgraph by these vertices and also the preservation ratio, using the annotated labels.
well as relative centrality
ICEF and preservation ratio of all datasets We put the change in the intra-community edge fraction as well as the preservation ratio by changing the fraction of points we select in the ranking for all of the 11 single-cell datasets that we consider this paper in Appendix As can be observed from the figures, our methods have comparable improvement in intra-community edge fraction to the baselines. However, our methods generally have a superior preservation ratio. We make the following three observations.
i) Our RN-Rank method provides the best preservation ratio among all the methods, and has slightly lower ICEF improvement. Here, note that for different values of c, the baseline methods, in fact, completely fail to include many more underlying communities than our relative centrality based methods.
ii) Among our methods, N2-Rank provides the highest improvement in ICEF and has a lower preservation ratio than other methods. In this direction, better understanding of the preservation ratio-ICEF improvement tradeoffs of our framework is a very interesting future direction.
iii) Finally, for the Zhengmix8eq dataset, the traditional centrality measures do not provide any improvement in ICEF via subset selection, as can be observed in Figure 15) This further points to weaknesses in the traditional centrality measures and the power of our relative centrality framework.
Balancedness of ranking We note that the balancedness values for the datasets Xin, Zheng, Tcell, and ALM are moderate, and we observe the same patterns with the preservation ratio, with RN-Rank obtaining the best results. The other datasets show that the balancedness AUC values are very small, less than 0.1. This indicates that least one cluster lost for these datasets when we filter out points. We attribute this to these datasets having several very small clusters. Improving our algorithms to have non-negligible (worst case) balancedness such datasets an important future direction.
Purity improvement upon core-ranking based point selection Here, we put the ICEF, purity, and preservation ratio of the top 20% points for different CR algorithms for all the datasets.
32

---

Published as a conference paper at ICLR 2025
Daissta
MU
8:
2h
Teall
ALM
AMB
of poines
12832
ICEF
Purky
ICE Purily
PR. ICEF Purlyy
PR. ICBF Purio
PR.
PR
Original
1.00 94 0.99
1,000096 13
1.009:93 11
1.00 0.99
1.000.78.00 U.
1 1.0
1.00 0.606666444
1.8. 0.76 (1
1.00 0:96
1000 U
1.00
1,00
0.52 0.99
1.00
0.82
0.60
0.61 0.60
0.53 095
0.57 0.64
PogeRank (0.5)
0:55 1.00 0.00
0.21 1.40
0150.0.00:1 96
0.87 100 0.00
0:04 (179 0.76
0.26-0.000 00.8
01.5 0.500.00066
0.35 0.960.55 0.85
PageKank (0.85)
0,52 1.00 1,30
0.76 1,00 0.00
1.53 0:99 0,39
0.50 1,00 1,00
0.89 0.79 0.80
0.70.0.79..3 0.82
0.7.0.8200 0.00
0.61 0.83 0.70
0,81 0L59 0.96
0.55 0.51 0.64
PagsRonk (1 990
0.52 1.00 8.00
10.5 1.00 1.00
0.59:0.90:0 0.99
0.55 100 1.00
0:84 (154-0000000 0.79
0.64 03778-8880 0.83
(.46 0.700.0...0
0.58:185500 0.35
0.79 1.900.990
01.4 CUB1 6
Ozioa
0.31 1.00 1.00
0.59.0.59110 (1.99
01:2005711 (1.92
0.46 1.001.00
0.89 0:727
0.57 0.78..8.3 01.7
0.57 0:51 0164
0.40 0.700000774
0.61 EU99 0:54
0.85 0.80 0.62
Dogrre
0.50
0.77.099000 0.99
0.53
0.76 1.000.99
0.76
0.800..90...0
0.570.79...6
0.89 0.66
0.55 0.94
0,67 0:60
Bask
0.98
0399
0,79
0,89
0.900000
0:65 0.61
0.73 0.58
0:90 0:4
0.67 0
N2-Raok
0.52.1.00 1.00
0.75 0.00
0.51 0,09 0.99
0.74 1.000..00
0,36.067 0.89
0.89 0.8
0.57 0.76 0.65
0.69 18.00.8.0665
0.38 0.8.0.900091
0.67. 016.00799.0.5
Table 4: Preservation ratio, intra-community edge fraction, and purity score of Louvain of top one-third ranked points
NMI improvement upon core-ranking based point selection Then, in Table we observe the improvement in the NMI outcome of Louvain when applied on the top 20% of the ranked points by the different methods, along with the preservation ratio of the selected subset. As with the purity, all
core ranking methods give subsets that have similar improvements in the NMI.
Datasets
BM
BH
MU
Se
Xi
Zh
Teell
ALM
AMB
TM
VISP
# of points
8569
1886
2122
2133
1449
3994
5759
10068
12832
S4865 PR NMI
15413
Metries
PR NMI
PR NMI
PR
NMI
PR
NMI
PR
NMT
PR NMT
PR NMI
PR NMI
PR NMT
PR NMI
Original
0.05
0.00
1.00
0.07
0.00060
0.00
0.06
1.00.74
1.00 0.74
1.00
0.00
values
Katz
0.77
0.75
0,73
0.50
0.58
0,80
0.60
0.86
0.51 0.87
0.74
0.49
PageRank (0.5)
0.80 0.76
0.51
0.75
0.50
0.93
0.69 0.63
0.47
0.76.0.82
0.53 0.84
PageRank (0.85)
0.79 0.77
0.49 0.75
0,74 0.79
0.51
0.55
0,88 0.77
0.60
0.82
0.49 0.88
0.83
0.47 0.85
PageRank (0.99)
0.79 0.78
0.73 0.76
0.50
0.50
0.79
0.57 0.63
0.40
0.46
0.72.0.83
0.45 0.85
Onion
0.71 0.78
0.75
0.51 0.69
0.40 0.22
0.92 0,74
0.50
0.24
0.35 0.88
0.45
0.35 0.83
Degree
0.76
0.52
0.75
0.78.0.82
0.57 0.82
RN-Rank Rank
0.83
0.68 0.75
0.84 0.78
0.56
0.72
0,85 0,76
0.89 0.60
0.61 0.84
0.69 0.83
0.87 0.80
0.61 0.81
0.85 0.74
0.50
0.52 0.74
0.72
0.77
0.64
0.85
0.56
Table 5: Preservation ratio and NMI of Louvain of top 20% ranked points
Community #
0
3
4
7
8
9
CVG(VV) CCs(V)
-0.14
0.07
0.2
-0.15
-0.09
0.04
0.02
-0.2
-0.3
-0.26
0.1
0.05
0.35
0.05
0.19
0.5
0.15
-0.06
0.4
-0.1
Table 6: A comparison of the concentration of the entire community vs. the subset of each community that is on the top 20% ranked node by RN-Rank (denoted by S) on the T-cell dataset (Savas et al.. 2018). Note that the concentration of the subset is strictly better for each community, denoting presence of core within each community as per our MCPC definition
we see Evidence of MCPC structure in single-cell data As we briefly discussed in Section 4.1 some interesting evidence of presence of cores within communities of the single-cell data as per our definition.
Our large scale experiments on single-cell data has already established
i) As we select top ranked points, they more separable into their ground truth communities.
ii) Our relative-centrality based approach results in significantly more balanced ranking.
While both of these observation mimic our simulation and theoretical observation in the MCPC structure, this does not directly indicate the presence of separable cores within each community in the real- world graphs. To test this, we calculate the concentration (as per Definition 2. in Section 3) of the nodes in each community and also the nodes of each community that are present in the top 20% of the ranking. We use the T-cell data an example. The values are noted in Table
As we can see, the concentrations of the subsets are indeed consistently higher! This indicates that the points we select based on ranking indeed leads a slight MCPC structure the real graphs, making our theoretical insight on the unbalancedness of existing centrality measures in the MCPC structure more relevant.
33

---

Published as a conference paper at ICLR 2025
Seporation vertices cores/perisheries by IKMeans mothod Each color represents a ground truth core/periphery block)
Block number per HITS K-Meaans
Figure 9: Performance of the HITS+K-Means algorithm in (Elliott et al. 2020) when applied to balanced MCPC-block model
E DISCUSSIONS
E.
CORE DETECTION ALGORIHHM IN SINGLE-CORE PERIPHERY STRUCTURE
As we discussed, there exists large literature of core- detectttoo algorithms particularly focused on single core- prr-peeiphery structure (Rombach et al.) 2014 2017 Yanchenko & Sengupta, 2023). this direction, the recent and comprehensive survey Yanchenko & Sengupta 2023) cited that most of the core-periphery detection algorithms need | log [V[ or more time and highlighted centrality measures as being efficient. This, along with the ease of applying these methods to a multi-core periphery structure, motivated our choice of baseline.
E.2 RESEARCH ON EXISTENCE OF MULTIPLE CORES
As we discussed, (Elliott al. 2020) seems be the only notable work in the literature that considered directed graphs with multiple cores. In this direction, we apply their core-detection algorithm to our MCPC-block model. Their method requires the knowledge the number cores and the number of peripheries. When the graph consists of 2 cores and 2 peripheries (as in block model), their method involves first obtaining a 4-dimensional score using the popular HITS algorithm. Then, they apply K -MMens with K 4 to the four-dimensional dataset separate into blocks.
In this direction, we apply their method to graph generated with the block probabilities in Table with 7 and
4000. Note that this is the simplest setting, where both cores have identical behavior in terms of core concentration, inter-core edges as well as overall community structure. We show the outcome in Figure As can observe, the output is not close the ground truth. This can, in part, be attributed to the fact that their structure, although multi-core directed one, is quite different from our MCPC structure.
Finally, (Tunç& & Verma 2015) seems to be the closest structure to our MCPC structure, even though is in an undirected graph setting. Indeed, this seems to be one of the initiating works in aiming to understand the coexistence of community and core- pore-periphery structure in systematic manner, and is thus an important contribution. Their approach as follows.
They also assume that the graph is partitioned into some ground truth communities, and each community has some core and some periphery vertices. They assume hypothesis model in which probability of an edge between v; and vú is aC:,; C₃) + b. We now decompress this definition. Here ōt, = 1 iff and j belong to the same community, and otherwise. Next, C, 1 v, is core vertex. That is, All inter-communtty edge probability is fixed b, ii) Intra-community core-periphery edge probability is a + b. and iii) Intra-core edge probability is 2a + b.
Despite its expressibility, this structure has a few significant shortcomings.
First, does not consider that the edge density can differ for different cores. We quantify this phenomenon with the concentration of set of vertices and show that when cores have different concentrations, it can lead to many core ranking algorithms performing in an unbalanced manner, which we mitigate with novel relative centrality framework.
34

---

Published as a conference paper at ICLR 2025
Next, the model also does not consider that the ioter-community edge probability between vertices is less than between peripheral vertices. We capture this our (a, 3) MCPC structure def- inition, and this observation allows us obtain subsets of real-world datasets with better community structure by using our core ranking algorithms.
Finally, they do not present any core detection algorithm beyond maximum likelihood approach w.r.t. the inference model we discussed. It is well known that such methods may have very slow convergence. Indeed, the experiments in (Tunç & Verma 2015) consider graphs with less than 200 vertices. In comparison, we apply our methods to datasets with > 50, 000 points and terminate generally in less than 10 seconds, owing to our fast O(EE + IV] [V1) run time.
E.3 LIMITATIONS AND FUTURE DIRECTIONS
In this paper, we take a step toward quantification of the MCPC structure, and design of core-ranking algorithms that mitigate unbalancedness observed in traditional centrality measures when applied to MCPC structures. In this direction, there are several questions/directions that we are unable to explore in this paper, which can be thought of as our limitation. We place them here.
1. Our proofs are in the MCPC-block model, which we use to prove the unbalancedness of traditional centrality measures and the performance of our algorithm. It will be interesting to obtain similar proofs in the other simulation model we study, the concentric GMM model. Furthermore, our proofs can be extended to the case when the size of the cores and peripheries are different.
2. We proposed the algorithm concept of relative centrality and proposed the meta-algorithm Meta-Rank in Algorithm 2 We used two instantiations of our algorithm, namely N2-Rank and RN-Rank and showed interesting ICEF improvement vs. balancedness tradeoffs. How- ever, obtaining the best possible instantiations for different problems remains an interesting open direction.
3. Even though our methods provide superior preservation ratio compared the traditional centrality measures in the single-cell data, we also have nower-than-idess preservation ratio in some datasets, such as the Segerstolpe dataset. Designing algorithms with even higher balancedness is an important goal.
4. In this paper, our real-world experiments focused on a large set of single-cell datasets. We believe MCPC structures may be present in other kinds of datasets as well. Exploring the existence of such structures in different domains is also important.
5. We show concrete application to single-cell datasets whereby the subsets are better separable into their ground truth communities. We chose the top 20% of the points for the experiments. Overall, the higher the number of points we select from this ranking, the higher the preservation ratio (less unbalanccdness), but the lower the improvement in separability. As in real-world graphs it is not expected that there is clear separation between core and periphery vertex behavior within communities, a clear cutoff choice is not apparent. However, we observe that choosing any cutoff percentage between 20 and 40 results in noticeable improvement in the clustering accuracy while maintaining good preservation ratio.
6. Although we have significantly higher balancedness/prseevvtion that all baseline centrality measures, the NMI/purity improvement of clustering on the points selected by our methods is lower, even though the improvements are comparable. However, such a tradeoff is inevitable. If the selected points have very low balancedness, then it indicates that only few points from some communities are present (some communities can be also completely missing) and therefore the total number of inter-community edges go down, resulting in visibly better clustering outcome (at the cost of losing information about many underlying communities). Analogous phenomena have been widely studied in the "quality-fairne" fairness" tradeoff in case of the supervised fair-clustering paradigm (Hakim et al.) (2224). Studying the limit of the "clustering improvement balan--aalandesss tradeoff" in unsupervised ranking scenario is a very interesting and important future direction.
7. Finally, we note that in this paper, we used our methods to obtain a subset of the dataset that is better separable into the ground truth communities. An important next step, and thus
35

---

Published as a conference paper at ICLR 2025
limitation of this work, is that do not the clustering this set obtain better clustering of the whole dataset. While we have some progress in this direction, is beyond the scope of the paper and requires systematic study.
PLOTS OF ICEF OF INDUCED SUBGRAPH AND PRESERVATION RATIO OF ALL SINGLE-CELL DATASETS
Baron_Human
Human
Mita-comnuuttyy edge Traction
0.99
Presarvetion raflo
0.99
0.5
0.7
0.98
Onlon decompontiin
0.97
Degres centra by
Ni hant
Rank
0.97
No Bunk
0.2
0.4
0.8
Frection of points
Fraction points
Figure 10: Baron Human dataset
Baron Mouse
Baron Mouse
Intra-cermuun edge traction
1.00
Preservazion rablo
0.5
Pegeltanc
Pegettant (0.85)
Prgettant (0 a99
0.41
Onien decompeation
0.96
Degres centre by
N
Ro4-aani
0.94
0.2
0.4
0.8
0.4
U.4
Frection of points
Fraction of points
Figure 11: Baron Mouse dataset
Muraro
Muraro
Intra concontttt edge traction
1.00
0.99
Prsservation rato
0.98
Katu Centrelty
Pigetann (0.51
0.97
Proeitant (0.85)
Pepeitnt (0.03)
onion decompocttion
0.96
Degree by
0.94
0.2
0.4
0.6
0.8
0.2
044
0.8
10
Froction of points
Fraction of points
Figure 12: Muraro dataset
36

---

Published as a conference paper at ICLR 2025
Segerstolpe
Segerstolpe
Intra-commy uumuuyytyy edge traction
1.00
3.--
0.98
Preservazton r230
0.3
0.97
Pepeitannc (9.51
Pigetann (0 (0.85)
0.1
Chien clecampattion
Pegeltnni (0 999
Degree centra ky
0.2
0.4
0.6
0.8
6.2
04
0-6
0.8
Fraction of points
Fraction of points
Figure 13: Segerstolpe dataset
Xin
Xin
itra-communtt edge traction
1.00
2.2
0.99
Presarvation rati
0.3
0.99
0.7
Katz Contraly ky
Papetant (0.3
0.98
Pegartant (0.85)
Popeiiant (1.33) Onion decampostion
0.97
033
Degree centra by
04-
0.97
0.2
0.4
0.6
0.8
0.2
0.4
0.
10
Frection of points
Fraction of points
Figure 14: Xin dataset
0.98
Zhengmix8cq
ZhengmixBen
Intra- coma-nnnnnittyy edge fraction
1.00
0.93
0-00
0.89
0.25
Koti Contually
Pegefank (3.5)
Pagefannt (2.85)
Pagehaakk (2.99)
0.79
0.55
0.74
0
0.2
0.4
0.5
0.8
0.6 Frection points
Fraction points
Figure 15: Zhengmix8eq dataset
nntracommunity edge Traction
0.89
Tcell-med cine
Teell-medicine
0.85
0.3
Posse Vatonn :3to
0.82
Kats Centrelly
Papeltanc
0.78
03
0.74
N: N-nart
Rank:
0.70
NG Bank
0.2
0.4
0.6
0.8
0.5
Fraction of points
points
Figure 16: Tcell dataset
37

---

Published as a conference paper at ICLR 2025
ALM
intracoommmmi Suuutity edge traction
0.91
ALM
0.86
Preservazton F2500
0.37
Pepeitancc (0.51
0.77
Pigetann (0 (0.55)
Pegeltnni (0 929
Chicn clecampettion
0.72
Degree centra ky
0.4
0.2
0.4
0.6
0.8
6.2
04
0-6
0.
Fraction of points
Fraction of points
Figure 17: ALM dataset
AMB
itra-comnuitt edge traction
0.94
AMB
2.3
0.90
Preservation ratio
0.5
0.86
0.3
Katz Contraly ky
Papetant (0.3
0.82
Pegartant (0.85)
Popeiiant (1.30)
0.4
Onion decampostion
0.78
Degres centra by
0.74
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.0
10
Frection of points
Fraction of points
Figure 18: AMB dataset
TM
TM
Intra-comma edge traction
3.0
0.99
64
Preservation ratlo
0.98
Katu Donbrrky
Papekonn 00
Pageltancc (0 85)
Papettanc
0.95
Pank Na-k
0.94
031
0.2
0.4
0.6
0.8
1
Fraction of points
Frection of points
Figure 19: TM dataset
Intra-community edge Traction
0.90
VISP
VISP
0.85
Proso Vaton att
0.81
Kats Centrally
033
Papeltanc
0.77
0.8-
0.72
N: Rant
Rank:
0.68
NG Bank
0.2
0.4
0.6
0.8
Fraction of points
points
Figure 20: VISP dataset
38


Reviews:
[{"review_id": "sMM5q0P3YB", "reviewer": "Reviewer_JR6C", "summary": "The paper is motivated by the observation that traditional ranking algorithms can produce unbalanced rankings, and it aims to promote balancedness in centrality estimation. It first defines the concept of relative centrality and then proposes an iterative, graph-dependent local normalization of the centrality score. Empirical studies are provided to demonstrate the effectiveness of the proposed concepts.", "questions": "Could you provide further clarifications on W1 and W2 listed above?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper aims to promote balancedness in nodes’ centrality ranking, using community detection as a concrete application scenario. I find this focus interesting.\n\nS2. The paper proposes a multi-core-periphery structure with communities (MCPC) to quantify unbalancedness in centrality measures.", "weaknesses": "W1. The illustrative example in Figure 3 is unclear to me. The blue nodes in Figure 3(a) have more in-neighbors in Figure 3(b), but the out-degrees of the in-neighbors are also larger than those in Figure 3(b). Can we trivially conclude that the blue nodes in Figure 3(b) have smaller PageRank scores than those in Figure 3(a)?\n\nW2. Following W1, if the answer is no, the core idea of defining the MCPC structure requires further clarification. Otherwise, the advantages of MCMC over traditional centrality measures (e.g., PageRank) seem marginal.\n\nW3. The paper does not theoretically demonstrate the superiority of clusters detected by the proposed method over previous approaches, which limits the paper’s contributions. \n\n------\nThe authors’ rebuttal partially addresses my concerns, and I would like to make a slight adjustment to my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "imFUn9HCEC", "reviewer": "Reviewer_SH4R", "summary": "The paper presents a new approach for achieving balanced rankings in graphs that have community structures. It addresses the problem of unbalanced rankings produced by traditional centrality measures. The authors introduce a structural concept called Multi-Core Periphery with Communities (MCPC), which combines both community and core-periphery structures. They propose \"relative centrality\" and develop a ranking algorithm that produces more balanced results than common centrality methods. The paper includes a theoretical analysis of ranking imbalances with MCPC structure and shows how their relative centrality approach resolves this issue. The paper demonstrates that their method improves clustering accuracy while achieving greater ranking balance compared to existing methods.", "questions": "1. How does the computational complexity of the proposed relative centrality algorithms compare to traditional centrality measures?\n\n2. Can the MCPC structure and relative centrality concepts be extended to undirected graphs or weighted networks?\n\n3. How does the performance of the proposed methods change as the number of communities in the graph increases?\n\n4. How does the proposed method handle dynamic or temporal networks where the structure may change over time?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces the concept of \"relative centrality\" and proposes a new structural assumption called Multi-Core Periphery with Communities (MCPC), which combines community structure and core-periphery structure.\n\n2. The paper provides theoretical analysis of their proposed methods, including proofs of unbalancedness with MCPC structure and how their relative centrality approach overcomes this issue.\n\n3. The paper demonstrates the usefulness of their balanced ranking algorithm on real-world data, specifically in improving the inference of community structure in single-cell RNA sequencing data.\n\n4. The authors compare their method against several popular centrality measures and provide extensive simulations on real-world datasets.", "weaknesses": "1. The paper focuses primarily on directed graphs, which may limit the applicability of the methods to certain types of networks.\n\n2. While the authors mention some existing work on multi-core structures, they don't provide a comprehensive comparison with these methods.\n\n3. The paper briefly addresses the computational complexity of M-Rank for k-regular directed graphs in Section 3.2, but lacks analysis for other approaches, such as N2-Rank and RN-Rank. Providing additional clarification or a more comprehensive complexity analysis, especially for larger or irregular graphs, would enhance the paper's practical relevance for large-scale network applications.\n\n4. Although the authors tested their method on 11 diverse single-cell datasets, these datasets are relatively small—only the TM dataset reaches 54K data points, with others below 16K. The superior results on Onion approach on the TM dataset in Table 2 raise questions about the scalability of the MCPC method on larger datasets. Besides, the PR for Onion is higher (.98) than RN-Rank (.87), yet RN-Rank is incorrectly highlighted in bold, which should be corrected. Evaluating the method on more larger datasets (e.g., millions of data points) could strengthen the paper’s contribution.\n\n5. While the PR scores are high for RN-Rank and N2-Rank, the Purity metric is consistently lower than traditional centrality measures across most datasets in Table 2. The paper would benefit from a more in-depth discussion of this trade-off between Preservation Ratio and Purity, including potential ways to improve Purity scores while maintaining a high Preservation Ratio.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lGuhipamoA", "reviewer": "Reviewer_mu1B", "summary": "The paper argues against global centrality measures such as PageRank for ranking nodes and suggests using relative centrality instead. As the name suggests, relative centrality measures centrality of a node relative to its neighborhood. The paper shows that relative centrality on Louvain community detection algorithm produces better clusters (as measured by preservation ratio of top 20% points and purity score).", "questions": "Ranking is often used in recommender systems. The authors point this out in the first sentence of the introduction. Why did they not compare relative centrality for recommending nodes instead of using it for community detection?", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper has a limitations section. Kudos to the authors for being honest about the technical limitations of their study.", "weaknesses": "- I have no objection to adding another centrality measure to the long list of node centrality measures. However, the results would have been more convincing if the experiments had been conducted for recommender systems rather than for community detection.\n\n- The authors may find these references related to their work:\n\nSotiris Tsioutsiouliklis, Evaggelia Pitoura, Panayiotis Tsaparas, Ilias Kleftakis, and Nikos Mamoulis. 2021. Fairness-Aware PageRank. In Proceedings of the Web Conference, pp. 3815–3826. https://doi.org/10.1145/3442381.3450065\n\nKijung Shin, Tina Eliassi-Rad, Christos Faloutsos. 2016. CoreScope: Graph Mining Using k-Core Analysis - Patterns, Anomalies and Algorithms. In Proceedings of the IEEE International Conference on Data Mining, pp. 469-478. https://ieeexplore.ieee.org/document/7837871\n\n- The captions for Figures 10 to 20 should be more informative. As is, they only list the name of the dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WvU6o67oJf", "reviewer": "Reviewer_6naw", "summary": "This paper focuses on the task of **unsupervised ranking on graphs** and aims to generate **balanced ranking**, where the top-ranked nodes contain a reasonable fraction of nodes from each community on the graph.\n\nThe authors propose a novel notion called **relative centrality**, which better preserves balancedness across different communities. Based on relative centrality, the authors propose several new approaches to iteratively update the centrality scores, which can be subsequently used for node ranking and graph clustering.\n\nOn the other hand, the authors propose a novel structural assumption for the underlying graphs, called **multi-core-periphery with communities (MCPC)**. Based on this, the authors define a stochastic block model and show that typical centralities are unbalanced under this model. Finally, experiments on 11 single-cell datasets are conducted to show that the proposed methods achieve higher balancedness while maintaining similar clustering quality.", "questions": "1. Could you provide more justifications for the relevance of this work to the ICLR community? For example, you can give some relevant papers published in ICLR or similar conferences/journals and add discussions to the paper.\n2. The quantities in Table 1 are magical to me. Could you explain them?\n3. Could you explain \"single-cell RNA seq data\" in more detail? Why do you focus on directed graphs as stated in Line 80? What about for undirected graphs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The goal of computing balanced ranking for vertices on graphs is a meaningful and interesting problem.\n2. The proposed assumption of multi-core-periphery structure is a natural combination of the community structure and the core-periphery structure, and the intuitions are conveyed nicely through Figures 2 and 3.\n3. The proposed methods and conducted experiments are generally described in detail.", "weaknesses": "1. I am not sure if this work is interesting to the ICLR community. This paper deals with unsupervised ranking, which can be regarded as unsupervised learning, but it may not fall into the scope of \"representation learning,\" which is \"generally referred to as deep learning\" as indicated on the official website of ICLR 2025. This paper may be more suitable for some venues on data mining or network science, for example.\n2. The theoretical analysis seems limited and not supportive for the balancedness of the proposed methods. The analysis relies on several simplifications: for example, the number of underlying communities is $2$, the size of all the cores and peripheries are the same, and $t=1$ in Theorem 3.6. The authors do claim that the analysis can be extended, but do not provide further explanations. On the other hand, although Theorem 3.6 and Lemma A.7 verify that the relative centrality scores of core vertices are close to $1$ and larger than those of periphery vertices, this does not imply that the induced ranking is balanced, since the scores in one community may be all larger than those in other communities.\n3. The paper is messy and needs significant improvement in presentation and layout. First, there lacks a detailed section on related work, making it hard to judge the contribution of this paper and its relevance to the ICLR community. Although Section 2.1 discusses some related work, it is brief and only concerns part of the contributions of the paper. Second, the text for the proposed assumption, methods, and analysis are not structured nicely, which is somewhat confusing. In particular, the order of the main text is not consistent with the contributions outlined in Section 1.1. Finally, there are numerous writing issues that affect the readability of the paper, as listed below.\n4. Some background concepts are not explained clearly. For example, the meaning of the single-cell data, the metrics of NMI and purity, and the \"onion\" baseline are not introduced clearly enough.\n5. The experiments only focus on single-cell datasets, which is limited. More experiments on other types of networks (e.g., social networks) are expected, and the number of tested single-cell datasets can be reduced.\n\nMinor issues:\n\n1. Most (if not all) citations in this paper should use `\\citep{}` instead of `\\cite{}`, so that the author names are placed in the parentheses. Also, the authors should cite the published version instead of the arXiv version of some papers.\n2. Line 163: \"community structure\" -> \"core-periphery structure\".\n3. Line 287: here the notation $k$ is ambiguous since it has a different meaning in Line 286.\n4. Line 352: \"$N_{G}(v_{j})$\" -> \"$N_{G}(v_{i})$\". Also, here the term \"neighborhood\" should be specified as \"in-neighborhood\" or \"out-neighborhood\".\n5. Line 762: \"upper bounded\" -> \"lower bounded\".\n6. There are some grammatical issues or typos:\n\t1. Lines 22-23;\n\t2. Line 74: \"for e.g.,\" -> \"e.g.,\";\n\t3. Line 130: \"behind of\" -> \"behind\";\n\t4. Line 180 and other occurrences: \"w.r.t\" -> \"w.r.t.\";\n\t5. Line 264: remove \"is defined\";\n\t6. Lines 419 and 1012: remove repetition of \"look at\";\n\t7. Line 463: remove \"to\";\n\t8. Lines 75 and 270: add space before left parentheses;\n\t9. Lines 192-193: the parentheses are not matched;\n\t10. the hyphens in compound words should be used correctly and consistently. For example, it should be \"centrality-measure-based\" in Line 17 and \"Core-Periphery structure\" in the caption of Figure 2(b).\n7. I recommend to beautify the layout of the paper:\n\t1. the captions of Figure 4 are hard to read;\n\t2. the annotation in Lines 352-353 are separated across lines;\n\t3. Table 1 and Figure 5 are placed weirdly;\n\t4. there should be punctuations around multiline math expressions;\n\t5. math expressions are not aligned nicely, and the ones at the top of page 15 are aligned terribly;\n\t6. the font of notations in math expressions is inconsistent in many places (e.g., $k$, $\\mathrm{deg}(\\cdot)$, and $o(\\cdot)$ in Lines 849-856);\n\t7. the text font changes in Lines 1332-1346.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)