# Absolute Expressiveness of Subgraph Motif Centrality Measures

Andreas Pieris  University of Edinburgh & University of CyprusCyprus
<EMAIL_ADDRESS>and  Jorge Salas  Pontificia Universidad Católica de
Chile & University of EdinburghChile<EMAIL_ADDRESS>
###### Abstract.

In graph-based applications, a common task is to pinpoint the most important
or “central” vertex in a (directed or undirected) graph, or rank the vertices
of a graph according to their importance. To this end, a plethora of so-called
centrality measures have been proposed in the literature that assess which
vertices in a graph are the most important ones. Riveros and Salas, in an ICDT
2020 paper, proposed a family of centrality measures based on the following
intuitive principle: the importance of a vertex in a graph is relative to the
number of “relevant” connected subgraphs, known as subgraph motifs,
surrounding it. We refer to the measures derived from the above principle as
subgraph motif measures. It has been convincingly argued that subgraph motif
measures are well-suited for graph database applications. Although the ICDT
paper studied several favourable properties enjoyed by subgraph motif
measures, their absolute expressiveness remains largely unexplored. The goal
of this work is to precisely characterize the absolute expressiveness of the
family of subgraph motif measures.

##  1\. Introduction

Graphs are well-suited for representing complex networks such as biological
networks, cognitive and semanitcs networks, computer networks, and social
networks, to name a few. In many applications that involve (directed or
undirected) graphs, a crucial task is to pinpoint the most important or
“central” vertex in a graph, or rank the vertices of a graph according to
their importance. Indeed, these graph-theoretic tasks naturally appear in many
different contexts, for example, finding people who are more likely to spread
a disease in the event of an epidemic (Dezső and Barabási, 2002), highlighting
cancer genes in proteomic data (Iván and Grolmusz, 2010), assessing the
importance of websites by search engines (Page et al., 1999), identifying
influencers in social networks (Huang et al., 2020), and many more. To this
end, a plethora of centrality measures have been proposed that assess the
importance of a vertex in a graph (Borgatti and Everett, 2006; Newman, 2018).
Centrality measures have been also studied in a principled way with the aim of
providing axiomatic characterizations via structural properties over certain
classes of graphs; see, e.g., (Was and Skibski, 2018; Kitti, 2016; van den
Brink and Gilles, 2000).

#### Centrality Measures and Graph Databases.

As said above, measuring the importance of a vertex in a graph is an important
task in many graph-based applications, and graph databases is no exception.
For example, Neo4j, one of the main graph database management systems, has
adopted and implemented several centrality measures and algorithms in its
Graph Data Science (GDS) library such as Eigenvector (Bonacich, 1987),
PageRank (Page et al., 1999), Closeness (Sabidussi, 1966),
etc.111https://neo4j.com/docs/graph-data-
science/current/algorithms/centrality/

A more principled approach towards centrality measures that are well-suited
for graph database applications has been recently introduced by Riveros and
Salas (Riveros and Salas, 2020). In particular, they proposed a family of
measures based on the following intuitive principle: the importance of a
vertex in a graph is relative to the number of “relevant” subgraphs
surrounding it. More precisely, the importance of a vertex is defined as the
logarithm of the number of relevant subgraphs surrounding it. As explicitly
discussed in (Riveros and Salas, 2020), the choice of applying the logarithmic
function is purely for technical simplicity, and one could adopt any function,
which we call filtering function, that leads to a richer family of centrality
measures. Let us clarify that (Riveros and Salas, 2020) considered only
undirected graphs, but the above general principle can be naturally
transferred to directed graphs. The notion of relevant subgraph is reminiscent
of the concept of subgraph motif, that is, recurrent and statisitically
significant connected subgraphs of a larger graph. Subgraph motifs have
recently attracted considerable attention as a useful tool to reveal
structural design principles of complex networks (Masoudi-Nejad et al., 2012).
Due to this conceptual similarity, we refer to the graph centrality measures
(for directed or undirected graphs) derived from the principle by Riveros and
Salas as subgraph motif measures. We further refer to monotonic subgraph motif
measures if the filtering function is monotonic. Note that the idea of
exploiting subgraph motifs for defining centrality measure has been already
considered in the literature; see, e.g., (Koschützki et al., 2007).

It has been convincingly argued in (Riveros and Salas, 2020) that (monotonic)
subgraph motif measures are conceptually relevant for graph database
applications. Consider, for example, a property graph $G$, which is
essentially a finite directed graph, and a language $L$ of basic graph
patterns (Angles et al., 2017). The evaluation of a query $Q$ from $L$ over
$G$, denoted $Q(G)$, is the set of vertices of $G$ that comply with the graph
pattern expressed by $Q$. In some scenarios, it is reasonable to assume that
the more queries $Q$ from $L$ such that $v\in Q(G)$, the more important $v$ is
in $G$ (relative to $L$). This way of defining the importance of a vertex
follows the general principle discussed above, where the relevant subgraphs
(or subgraph motifs) are the basic graph patterns from the language $L$, and
the filtering function is any monotonic function (e.g., the logarithm).
Analogously, in a different scenario where the less queries $Q$ from $L$ such
that $v\in Q(G)$, the more important $v$ is in $G$ (relative to $L$), a
subgraph motif measure where the underlying subgraph motifs are the graph
patterns of $L$, and the filtering function is a decreasing one, could be
adopted.

#### Our Main Objective.

With the family of subgraph motif measures in place, Riveros and Salas went on
to isolate favourable properties enjoyed by subgraph motif measures depending
on the underlying subgraph motifs, that is, the set of relevant subgraphs
(Riveros and Salas, 2020). Actually, their analysis focused on subgraph motif
measures for undirected graphs with the filtering function being always the
logarithmic function. In this work, instead, our main objective is to
delineate the limits of the family of (monotonic) subgraph motif measures as a
whole (i.e., without fixing a priori the filtering function) for both directed
and undirected graphs. More precisely, we would like to understand when an
arbitrary centrality measure is a (monotonic) subgraph motif one, or when it
induces the same ranking as a (monotonic) subgraph motif one.

#### Our Contributions.

In Section 4, we provide a precise characterization of when an arbitrary
centrality measure is subgraph motif. More precisely, we isolate a “bounded
value” property $P$ over centrality measures, which essentially states that
the total number of distinct values that can be assigned to vertices
surrounded by a certain number of connected subgraphs is bounded, and then
show that a centrality measure can be expressed as a subgraph motif one iff it
enjoys $P$. We then proceed in Section 5 to characterize when an arbitrary
centrality measure induces the same ranking as a subgraph motif measure. In
this case, we isolate a “graph coloring” property $P$ over centrality
measures, and then show that a centrality measure can be expressed as a
subgraph motif one relative to the induced ranking iff it enjoys $P$. In
Section 6, we focus on the family of monotonic subgraph motif measures, and
provide analogous characterizations via refined properties in the spirit of
the “bounded value” property discussed above. An interesting finding of our
analysis is that in the case of connected graphs, every centrality measure can
be expressed as a monotonic subgraph motif measure relative to the induced
ranking. Having the above results, we proceed to determine if established
measures (such as PageRank, Eigenvector, and many others) are (monotonic)
subgraph motif (relative to the induced ranking). Such a classification, apart
from being interesting in its own right, provides insights on the structural
similarities and differences among the considered centrality measures.

#### Clarification Remark.

In the rest of the paper, due to space constraints and for the sake of
clarity, we focus on undirected graphs, but all the notions and results can be
transferred to the case of directed graphs under the standard notion of weak
connectedness. The case of directed graphs is deferred to the appendix.

##  2\. Preliminaries

We recall the basics on undirected graphs and graph centrality measures. In
the rest of the paper, we assume the countable infinite set $\mathbf{V}$ of
vertices. For $n>0$, let $[n]=\\{1,\ldots,n\\}$.

#### Undirected Graphs.

An undirected graph (or simply graph) $G$ is a pair $(V,E)$, where $V$ is a
finite non-empty subset of $\mathbf{V}$ (the set of vertices of $G$), and
$E\subseteq\\{\\{u,v\\}\mid u,v\in V\\}$ (the set of edges of $G$). For
notational convenience, given a graph $G$, we write $V(G)$ and $E(G)$ for the
set of its vertices and edges, respectively. We denote by $\mathbf{G}$ the set
of all graphs, and by $\mathbf{VG}$ the set of vertex-graph pairs
$\\{(v,G)\in\mathbf{V}\times\mathbf{G}\mid v\in V(G)\\}$. The neighbourhood of
a vertex $v\in V(G)$ in $G$, denoted $N_{G}(v)$, is the set $\\{u\in
V(G)\mid\\{u,v\\}\in E(G)\\}$. For $u\in N_{G}(v)$, we say that $v$ and $u$
are adjacent in $G$. For a vertex $v\in\mathbf{V}$, we write $G_{v}$ for the
graph $(\\{v\\},\emptyset)$.

A subgraph of a graph $G$ is a graph $G^{\prime}$ such that
$V(G^{\prime})\subseteq V(G)$ and $E(G^{\prime})\subseteq E(G)$; we write
$G^{\prime}\subseteq G$ to indicate that $G^{\prime}$ is a subgraph of $G$.
Note that the binary relation $\subseteq$ over graphs forms a partial order.
We denote by $\text{\rm Sub}(G)$ all the subgraphs of $G$, that is, the set of
graphs $\\{G^{\prime}\mid G^{\prime}\subseteq G\\}$. Given a set of vertices
$S\subseteq V(G)$, the subgraph of $G$ induced by $S$, denoted $G[S]$, is the
subgraph $G^{\prime}$ of $G$ such that $V(G^{\prime})=S$, and
$E(G^{\prime})=\\{\\{u,v\\}\in E(G)\mid u,v\in S\\}$.

A path in $G$ is a sequence of vertices $\pi=v_{0},v_{1},\ldots,v_{n}$, for
$n\geq 0$, such that $\\{v_{i},v_{i+1}\\}\in E(G)$ for every $0\leq i<n$. We
further say that $\pi$ is a path from $v_{0}$ to $v_{n}$. The length of $\pi$,
denoted $|\pi|$, is the number of edges in $\pi$. By convention, there exists
a path of length $0$ from a vertex to itself. The distance between two
vertices $u,v\in V(G)$ in $G$, denoted $d_{G}(u,v)$, is defined as the length
of a shortest path from $u$ to $v$ in $G$; if there is no path, then
$d_{G}(u,v)=\infty$. We denote by $S_{G}(u,v)$ the set of all the shortest
paths from $u$ to $v$ in $G$, that is, the set $\\{\pi\mid\pi\text{ is a path
from }u\text{ to }v\text{ in }G\text{ with }|\pi|=d_{G}(u,v)\\}$.

A graph $G$ is connected if, for every two distinct vertices $u,v\in V(G)$,
there exists a path from $u$ to $v$. We denote by $\mathsf{A}(v,G)$ the set of
all connected subgraphs of $G$ that contain $v$, that is, the set
$\\{G^{\prime}\subseteq G\mid v\in V(G^{\prime})\text{ and }G^{\prime}\text{
is connected}\\}$. By abuse of notation, we may treat
$\mathsf{A}(\cdot,\cdot)$ as a function of the form
$\mathbf{VG}\rightarrow\mathcal{P}(\mathbf{G})$; as usual, we write
$\mathcal{P}(S)$ for the powerset of a set $S$. A connected component (or
simply component) of $G$ is an induced subgraph $G[S]$ of $G$, where
$S\subseteq V(G)$, such that $G[S]$ is connected, and, for every $v\in
V(G)\setminus S$, there is no path in $G$ from $v$ to a vertex of $S$. It is
clear that whenever $G$ is connected, the only component of $G$ is $G$ itself.
We denote by $\text{\rm Comp}(G)$ all the components of $G$, that is, the set
of graphs $\\{G^{\prime}\mid G^{\prime}\text{ is a component of }G\\}$. Let
$K_{v}(G)$ be the set of vertices of the component of $G$ containing the
vertex $v$.

#### Centrality Measures.

A centrality measure assigns a score to a vertex $v$ in a graph $G$, which
reflects the importance of $v$ in $G$. In other words, we adopt the standard
assumption that the higher the score of a vertex $v$ in $G$, the more
important or “central” $v$ is in $G$. Formally, a centrality measure (or
simply measure) is a function $\mathsf{C}:\mathbf{VG}\ \rightarrow\
\mathbb{R}$. We proceed to recall three measures that will be used throughout
the paper; more measures are discussed in Section 7.

Stress.:

This is a well-known centrality measure introduced in the 1950s (Shimbel,
1953). It measures the centrality of a vertex by essentially counting the
number of shortest paths that go via that vertex. Formally, for a graph $G$
and a vertex $v\in V(G)$, the stress centrality of $v$ in $G$ is

$\mathsf{Stress}(v,G)\ =\ \sum_{u,w\in
V(G)\setminus\\{v\\}}\left|S_{G}^{v}(u,w)\right|,$

where $S_{G}^{v}(u,w)=\\{\pi\in S_{G}(u,w)\mid\pi\text{ contains }v\\}$.

All-Subgraphs.:

This measure was recently introduced in the context of graph databases
(Riveros and Salas, 2020). It essentially states that a vertex is more central
if it participates in more connected subgraphs. Formally, given a graph $G$
and a vertex $v\in V(G)$, the all-subgraphs centrality of $v$ in $G$ is
defined as

$\mathsf{All\text{\rm-}Subgraphs}(v,G)\ =\ \log_{2}|\mathsf{A}(v,G)|.$

Closeness.:

This is a well-known measure introduced back in 1960s (Sabidussi, 1966). It is
usually called a geometrical measure since it relies on the distance inside a
graph. It essentially states that the closer a vertex is to everyone in the
graph the more central it is. Formally, given a graph $G$ and a vertex $v\in
V(G)$, the closeness centrality of $v$ in $G$ is defined as the ratio

$\mathsf{Closeness}(v,G)=\frac{1}{\sum_{u\in K_{v}(G)}d_{G}(v,u)}.$

Let us clarify that we define the sum of distances inside a component of $G$
since the distance between two vertices in different components of $G$ is by
definition infinite.

##  3\. Subgraph Motif Measures

As already discussed in the Introduction, a natural way of measuring the
importance of a vertex in a graph is to count the relevant connected subgraphs
(i.e., the subgraph motifs) surrounding it, and then apply a certain filtering
function from the non-negative integers to the reals on top of the count. Of
course, the relevant subgraphs and the adopted filtering function are
determined by the intention of the centrality measure. Interestingly, both the
stress and the all-subgraphs centrality measures, discussed in the previous
section, are actually based on this principle. Let us elaborate further on
this. Consider a graph $G$ and a vertex $v\in V(G)$:

  * •

For the stress centrality, the important subgraphs for $v$ in $G$ are the
shortest paths that go via $v$ in $G$, and the filtering function is
$f_{\times 2}(x)=2x$ since each shortest path is counted twice. In other
words, with $G_{\pi}$ being the graph that corresponds to a path $\pi$, it is
clear that

$\mathsf{Stress}(v,G)\ =\ f_{\times 2}\left(\left|\bigcup_{u,w\in
V(G)\setminus\\{v\\}}\left\\{G_{\pi}\mid\pi\in
S_{G}^{v}(u,w)\right\\}\right|\right).$

  * •

For the all-subgraphs centrality, the important subgraphs for $v$ in $G$ are
the connected subgraphs of $G$ that contain $v$, that is, the set
$\mathsf{A}(v,G)$, and the filtering function is $\log_{2}$. Indeed, by
definition, we have that

$\mathsf{All\text{\rm-}Subgraphs}(v,G)\ =\ \log_{2}|\mathsf{A}(v,G)|.$

We proceed to formalize the above simple principle, originally introduced in
(Riveros and Salas, 2020), which gives rise to a family of centrality
measures, and then highlight our main research questions.

#### Centrality Measures based on Subgraph Motifs.

We first need a way to specify what are the important subgraphs for a vertex
$v$ in a graph $G$. This is done via the notion of subgraph family, which is
defined as a function from vertex-graph pairs to sets of graphs
$\mathsf{F}:\mathbf{VG}\ \rightarrow\ \mathcal{P}(\mathbf{G})$ such that, for
every $(v,G)\in\mathbf{VG}$, $\mathsf{F}(v,G)\subseteq\mathsf{A}(v,G)$, that
is, $\mathsf{F}$ assigns to each $(v,G)\in\mathbf{VG}$ a set of connected
subgraphs of $G$ surrounding $v$. We also need the notion of filtering
function, which, as said above, is simply a function of the form
$f:\mathbb{N}\rightarrow\mathbb{R}$. We are now ready to define our centrality
measures:

###### Definition 3.1 (Subgraph Motif Measure).

Consider a subgraph family $\mathsf{F}$ and a filtering function $f$. The
$\langle\mathsf{F},f\rangle$-measure is the function
$\mathsf{C}\langle\mathsf{F},f\rangle:\mathbf{VG}\ \rightarrow\ \mathbb{R}$
such that, for $(v,G)\in\mathbf{VG}$,
$\mathsf{C}\langle\mathsf{F},f\rangle(v,G)=f(|\mathsf{F}(v,G)|)$. A centrality
measure $\mathsf{C}$ is a subgraph motif centrality measure if there are a
subgraph family $\mathsf{F}$ and a filtering function $f$ such that
$\mathsf{C}$ is the $\langle\mathsf{F},f\rangle$-measure, namely
$\mathsf{C}=\mathsf{C}\langle\mathsf{F},f\rangle$.

Returning back to our discussion on stress and all-subgraph centralities,
assuming that $\mathsf{S}$ is the subgraph family such that

$\mathsf{S}(v,G)\ =\ \bigcup_{u,w\in
V(G)\setminus\\{v\\}}\left\\{G_{\pi}\mid\pi\in S_{G}^{v}(u,w)\right\\},$

it is straightforward to see that

$\mathsf{Stress}\ =\ \mathsf{C}\langle\mathsf{S},f_{\times
2}\rangle\quad\text{and}\quad\mathsf{All\text{\rm-}Subgraphs}=\mathsf{C}\langle\mathsf{A},\log_{2}\rangle.$

#### Main Research Questions.

Having the family of subgraph motif centrality measures in place, the natural
question that comes up concerns its absolute expressiveness. In other words,
we are interested in the following research question:

Question I: When is a centrality measure a subgraph motif centrality measure?

One may wonder whether the above question is conceptually trivial in the sense
that every centrality measure can be expressed as a subgraph motif centrality
measure by choosing the subgraph family and the filtering function in the
proper way as done for $\mathsf{Stress}$ and
$\mathsf{All\text{\rm-}Subgraphs}$. It turns out that there are measures that
are not subgraph motif, which renders the above question non-trivial.

###### Proposition 3.2.

There exists a centrality measure that is not a subgraph motif centrality
measure.

###### Proof.

Let $\hat{G}$ be the graph
$(\\{v_{1},v_{2},v_{3}\\},\\{\\{v_{1},v_{2}\\}\\})$. Consider the centrality
measure $\mathsf{C}$ defined as follows:

$\mathsf{C}(v,G)\ =\ \begin{cases}1&G\neq\hat{G}\\\ i+1&G=\hat{G}\text{ and
}v=v_{i}\text{ for }i\in[3].\end{cases}$

It suffices to show that $\mathsf{C}$ is not subgraph motif even if we focus
on the set of graphs $\mathbf{G}^{\star}=\\{G_{v}\mid
v\in\mathbf{V}\\}\cup\\{\hat{G}\\}\subseteq\mathbf{G}$. By contradiction,
assume that $\mathsf{C}$ is a subgraph motif measure over
$\mathbf{G}^{\star}$. Thus, there is a subgraph family $\mathsf{F}$ and a
filtering function $f$ such that, for every $G\in\mathbf{G}^{\star}$ and $v\in
V(G)$, $\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$. We observe
that:

  1. (1)

For every $(v,G)\in\mathbf{V}\times\mathbf{G}^{\star}$ with $v\in V(G)$, it
holds that $\mathsf{C}\langle\mathsf{F},f\rangle(v,G)\in\\{1,\ldots,4\\}$,
i.e., we have four distinct values. This follows by the definition of
$\mathsf{C}=\mathsf{C}\langle\mathsf{F},f\rangle$.

  2. (2)

For every $(v,G)\in\mathbf{V}\times\mathbf{G}^{\star}$, it holds that
$|\mathsf{F}(v,G)|\in\\{0,1,2\\}$, i.e., we have three possible sizes for the
sets of subgraph motifs. Indeed, $|\mathsf{F}(v,G_{v})|\in\\{0,1\\}$ for
$v\in\mathbf{V}$,
$|\mathsf{F}(v_{1},\hat{G})|=|\mathsf{F}(v_{2},\hat{G})|\in\\{0,1,2\\}$, and
$|\mathsf{F}(v_{3},\hat{G})|\in\\{0,1\\}$.

Now, by the pigeonhole principle, we can conclude that there are two distinct
pairs $(v,G),(u,G^{\prime})\in\mathbf{V}\times\mathbf{G}^{\star}$ with
$|\mathsf{F}(v,G)|=|\mathsf{F}(u,G^{\prime})|$ such that
$\mathsf{C}\langle\mathsf{F},f\rangle(v,G)\neq\mathsf{C}\langle\mathsf{F},f\rangle(u,G^{\prime})$.
But this contradicts the fact that $f$ is a function, and the claim follows.

As we shall see, not only artificial measures as the one employed in the proof
of Proposition 3.2, but also well-known centrality measures from the
literature (such as $\mathsf{Closeness}$) are not subgraph motif. We are going
to prove such inexpressibility results by using the technical tools developed
towards answering Question I.

In several applications that involve graphs, we are interested in the relative
than the absolute importance of a vertex in a graph. More precisely, we are
interested in the ranking of the vertices of a graph induced by a measure
$\mathsf{C}$, and not in the absolute value assigned to a vertex by
$\mathsf{C}$. This brings us to the next notion:

###### Definition 3.3 (Induced Ranking).

Let $\mathsf{C}$ be a centrality measure. The ranking induced by $\mathsf{C}$,
denoted $\text{\rm Rank}(\mathsf{C})$, is the binary relation

$\left\\{((u,G),(v,G))\mid u,v\in V(G)\text{ and
}\mathsf{C}(u,G)\leq\mathsf{C}(v,G)\right\\}$

over $\mathbf{VG}$. We say that $\mathsf{C}$ is a subgraph motif centrality
measure relative to the induced ranking if there are a subgraph family
$\mathsf{F}$ and a filtering function $f$ with $\text{\rm
Rank}(\mathsf{C})=\text{\rm Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$.

Interestingly, although the measure employed in the proof of Proposition 3.2
is not subgraph motif, we can show that it is a subgraph motif measure
relative to the induced ranking. In particular, with $\hat{G}$ being the graph
$(\\{v_{1},v_{2},v_{3}\\},\\{\\{v_{1},v_{2}\\}\\})$ used in the proof of
Proposition 3.2, by defining the subgraph family $\mathsf{F}$ as

$\mathsf{F}(v,G)\ =\ \begin{cases}\emptyset&G\neq\hat{G}\\\
\emptyset&G=\hat{G}\text{ and }v=v_{1}\\\
\\{G_{v_{2}},\hat{G}[K_{v_{2}}(\hat{G})]\\}&G=\hat{G}\text{ and }v=v_{2}\\\
\\{G_{v}\\}&G=\hat{G}\text{ and }v=v_{3},\end{cases}$

and the filtering function $f$ as $f(0)=1$, $f(1)=3$ and $f(2)=2$, it is not
difficult to see that $\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. This observation brings us to
our next research question:

Question II: When is a centrality measure a subgraph motif centrality measure
relative to the induced ranking?

We conclude this section by showing that the above question is conceptually
non-trivial, i.e., there are measures that are not subgraph motif measures
relative to the induced ranking. In particular, with
$\hat{G}=(\\{v_{1},v_{2},v_{3},v_{4}\\},\\{\\{v_{1},v_{2}\\}\\})$, for the
measure $\mathsf{C}$ defined as

$\mathsf{C}(v,G)\ =\ \begin{cases}1&G\neq\hat{G}\\\ i+1&G=\hat{G}\text{ and
}v=v_{i}\text{ for }i\in[4]\end{cases}$

we can show that, for every subgraph family $\mathsf{F}$ and filtering
function $f$, $\text{\rm Rank}(\mathsf{C})\neq\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. Therefore:

###### Proposition 3.4.

There is a measure that is not a subgraph motif centrality measure relative to
the induced ranking.

Let us stress that, not only artificial measures as the one employed in the
proof of Proposition 3.4, but also established measures (such as
$\mathsf{Closeness}$) are not subgraph motif centrality measures relative to
the induced ranking. Such inexpressibility results are shown by exploiting the
tools developed towards answering Question II.

##  4\. Characterizing Subgraph Motif Measures

We proceed to provide an answer to Question I. More precisely, our goal is to
isolate a structural property $P$ over centrality measures that precisely
characterizes subgraph motif measures, that is, for an arbitrary measure
$\mathsf{C}$, $\mathsf{C}$ is a subgraph motif measure iff $\mathsf{C}$ enjoys
the property $P$. Interestingly, the desired property can be somehow extracted
from the proof of Proposition 3.2. The crucial intuition provided by that
proof is that the absolute expressiveness of subgraph motif measures is
tightly related to the amount of connected subgraphs that are available for
assigning different centrality values to vertices. In other words, a measure
that assigns “too many” values among vertices that are surrounded by “too few”
connected subgraphs cannot be expressed as a subgraph motif measure. We
proceed to formalize this intuition.

We first collect all the different values assigned by a centrality measure
$\mathsf{C}$ to the vertices of a graph $G$ that are surrounded by a bounded
number of connected subgraphs of $G$. In particular, for $n>0$, we define the
set of real values

$\text{\rm Val}_{G}^{n}(\mathsf{C})\ =\ \left\\{\mathsf{C}(v,G)\mid v\in
V(G)\text{ and }|\mathsf{A}(v,G)|\leq n\right\\}.$

We can then easily collect all the values assigned by $\mathsf{C}$ to the
vertices of $\mathbf{V}$ that are surrounded by a bounded number of connected
subgraphs in some graph. In particular, for $n>0$,

$\text{\rm Val}^{n}(\mathsf{C})\ =\ \bigcup_{G\in\mathbf{G}}\text{\rm
Val}_{G}^{n}(\mathsf{C}).$

We now define the following property over measures:

###### Definition 4.1 (Bounded Value Property).

A measure $\mathsf{C}$ enjoys the bounded value property if, for every $n>0$,
$|\text{\rm Val}^{n}(\mathsf{C})|\leq n+1$.

The bounded value property captures the key intuition discussed above. It
actually bounds the number of different values that can be assigned among
vertices that are surrounded by a limited number of connected subgraphs; hence
the name “bounded value property”. Observe that the measure $\mathsf{C}$
devised in the proof of Proposition 3.2 does not enjoy the bounded value
property; indeed, $|\text{\rm Val}^{2}(\mathsf{C})|=4>3$. Surprisingly, the
bounded value property is all we need towards a precise characterization of
subgraph motif measures.

###### Theorem 4.2.

Consider a centrality measure $\mathsf{C}$. The following statements are
equivalent:

  1. (1)

$\mathsf{C}$ is a subgraph motif centrality measure.

  2. (2)

$\mathsf{C}$ enjoys the bounded value property.

The above characterization, apart from giving a definitive answer to Question
I, it provides a useful tool for establishing inexpressibility results. To
show that a centrality measure $\mathsf{C}$ is not a subgraph motif measure it
suffices to show that there exists an integer $n>0$ such that $|\text{\rm
Val}^{n}(\mathsf{C})|>n+1$. For example, in the case of closeness, we can show
that $|\text{\rm Val}^{5}(\mathsf{Closeness})|>6$, and therefore:

###### Proposition 4.3.

$\mathsf{Closeness}$ is not a subgraph motif measure.

Without Theorem 4.2 in place, it is completely unclear how one can prove that
$\mathsf{Closeness}$ (or any other established measure) is not a subgraph
motif measure. More inexpressibility results concerning well-established
centrality measures are discussed in Section 7.

##  5\. Characterizing Subgraph Motif Measures Relative to the Induced Ranking

We now focus on Question II. Our goal is to isolate a structural property $P$
over centrality measures that precisely characterizes subgraph motif measures
relative to the induced ranking, i.e., for an arbitrary measure $\mathsf{C}$,
$\mathsf{C}$ is subgraph motif relative to the induced ranking iff
$\mathsf{C}$ enjoys the property $P$. Despite our efforts, we have not managed
to define $P$ in the spirit of the bounded value property (see Definition
4.1). It turns out, however, that $P$ can be defined by exploiting a certain
notion of graph coloring relative to a centrality measure. At the end of this
section, we discuss how the coloring-based property helps to obtain a bounded-
value-like property that is a necessary condition for a measure being subgraph
motif relative to the induced ranking. As we shall see in Section 7, the
latter provides a convenient tool for showing that several existing measures
are not subgraph motif relative to the induced ranking.

#### Graph Colorings.

The high-level idea is to consider the sizes of the available subgraph
families that can be assigned to a vertex $v$ in a graph $G$, i.e., the set of
integers $\\{0,\ldots,|\mathsf{A}(v,G)|\\}$, as available colors. We can then
refer to a precoloring of $\mathbf{VG}$ (i.e., of all the possible graphs) as
a function $\mathit{pc}:\mathbf{VG}\rightarrow\mathbb{N}$ that assigns to each
vertex $v$ in a graph $G$ only available colors from
$\\{0,\ldots,|\mathsf{A}(v,G)|\\}$. Then, the goal is to isolate certain
properties of such a precoloring of $\mathbf{VG}$ that leads to the desired
characterization, i.e., a measure $\mathsf{C}$ is a subgraph motif relative to
the induced ranking iff there exists a precoloring of $\mathbf{VG}$ that
enjoys the properties in question. Such a characterization tells us that for a
centrality measure being subgraph motif relative to the induced ranking is
tantamount to the fact that there are enough colors (i.e., sizes of sugbraph
families, but without considering their actual topological structure) that
allow us to color $\mathbf{VG}$ in a valid way, namely in a way that the
crucial properties are satisfied. We proceed to formalize the above discussion
about colorings.

Given a set $S\subseteq\mathbf{VG}$, a precoloring of $S$ is a function
$\mathit{pc}:S\rightarrow\mathbb{N}$ such that, for every $(v,G)\in S$,
$\mathit{pc}(v,G)\in\\{0,\ldots,|\mathsf{A}(v,G)|\\}$. It is very natural to
expect from such a precoloring of $S$ to respect the values assigned by a
measure $\mathsf{C}$ to the vertices of a certain graph $G$, i.e., vertices of
$G$ with different centrality values get different colors. This leads to the
following property over precolorings:

###### Definition 5.1 (Non-Uniform $\mathsf{C}$-Injectivity).

Consider a set $S\subseteq\mathbf{VG}$, and a precoloring
$\mathit{pc}:S\rightarrow\mathbb{N}$ of $S$. Given a centrality measure
$\mathsf{C}$, we say that $\mathit{pc}$ is non-uniformly
$\mathsf{C}$-injective if, for every $(u,G),(v,G)\in S$,
$\mathsf{C}(u,G)\neq\mathsf{C}(v,G)$ implies
$\mathit{pc}(u,G)\neq\mathit{pc}(v,G)$.

The term non-uniform in the above definition refers to the fact that
$\mathsf{C}$-injectivity is only enforced inside a certain graph, and not
across all the graphs mentioned in $S$, i.e., it might be the case that a non-
uniformly $\mathsf{C}$-injective precoloring of $S$ assigns to
$(u,G),(v,G^{\prime})$, where $G\neq G^{\prime}$ and
$\mathsf{C}(u,G)\neq\mathsf{C}(v,G^{\prime})$, the same color.

It also natural to expect from a precoloring of $S$ to be somehow consistent
with the induced ranking, not only inside a certain graph, but also among
different graphs mentioned in $S$. In other words, if $(u,G)$ comes before
$(v,G)$, and $(u^{\prime},G^{\prime})$ comes before $(v^{\prime},G^{\prime})$,
then one of the following should hold: $(u,G)$ and $(v^{\prime},G^{\prime})$
get different colors, or $(u^{\prime},G)$ and $(v,G^{\prime})$ get different
colors.

###### Definition 5.2 ($\mathsf{C}$-Consistency).

Consider a set $S\subseteq\mathbf{VG}$, and a precoloring
$\mathit{pc}:S\rightarrow\mathbb{N}$ of $S$. Given a centrality measure
$\mathsf{C}$, we say that $\mathit{pc}$ is $\mathsf{C}$-consistent if, for
every $(u,G),(v,G),(u^{\prime},G^{\prime}),(v^{\prime},G^{\prime})\in S$, the
following holds: if $\mathsf{C}(u,G)<\mathsf{C}(v,G)$ and
$\mathsf{C}(u^{\prime},G^{\prime})<\mathsf{C}(v^{\prime},G^{\prime})$, then
$\mathit{pc}(u,G)\neq\mathit{pc}(v^{\prime},G^{\prime})$ or
$\mathit{pc}(u^{\prime},G)\neq\mathit{pc}(v,G^{\prime})$.

Putting together the above two properties over precolorings, we get the notion
of $\mathsf{C}$-colorability of a set $S\subseteq\mathbf{VG}$:

###### Definition 5.3 ($\mathsf{C}$-Colorability).

We say that a set $S\subseteq\mathbf{VG}$ is $\mathsf{C}$-colorable, for some
measure $\mathsf{C}$, if there exists a precoloring of $S$ that is non-
uniformly $\mathsf{C}$-injective and $\mathsf{C}$-consistent.

#### The Characterization.

Interestingly, $\mathsf{C}$-colorability is all we need towards the desired
characterization, namely a measure $\mathsf{C}$ is subgraph motif relative to
the induced ranking iff $\mathbf{VG}$ (i.e., all possible graphs) is
$\mathsf{C}$-colorable. We further show that the $\mathsf{C}$-colorability of
$\mathbf{VG}$ is equivalent to the $\mathsf{C}$-colorability of every finite
set $S\subsetneq\mathbf{VG}$. The latter, apart from being interesting in its
own right, it also provides a technical tool that is somehow more convenient
than the $\mathsf{C}$-colorability of the whole set $\mathbf{VG}$ for
classifying centrality measures as subgraph motif relative to the induced
ranking.

###### Theorem 5.4.

Consider a centrality measure $\mathsf{C}$. The following statements are
equivalent:

  1. (1)

$\mathsf{C}$ is a subgraph motif measure relative to the induced ranking.

  2. (2)

Every finite set $S\subsetneq\mathbf{VG}$ is $\mathsf{C}$-colorable.

  3. (3)

$\mathbf{VG}$ is $\mathsf{C}$-colorable.

To show the above characterization, it suffices to establish the sequence of
implications $(1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1)$. We proceed to
discuss the key ingredients underlying the proofs of the above implications;
the full proofs can be found in the appendix.

Implication $(1)\Rightarrow(2)$

This implication is a rather easy one to prove. Since, by hypothesis,
$\mathsf{C}$ is a subgraph motif measure relative to the induced ranking,
there are a subgraph family $\mathsf{F}$ and a filtering function $f$ such
that $\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. Given a finite set
$S\subsetneq\mathbf{VG}$, we define the function
$\mathit{pc}_{S}:S\rightarrow\mathbb{N}$ as follows: for every $(v,G)\in S$,
$\mathit{pc}_{S}(v,G)=|\mathsf{F}(v,G)|$. It is clear that $\mathit{pc}_{S}$
is a precoloring of $S$ since, by definition,
$\mathsf{F}(v,G)\subseteq\mathsf{A}(v,G)$, and thus,
$\mathit{pc}_{S}(v,G)\in\\{0,\ldots,|\mathsf{A}(v,G)|\\}$. It is also not
difficult to show that $\mathit{pc}_{S}$ is non-uniformly
$\mathsf{C}$-injective and $\mathsf{C}$-consistent, which in turn implies that
$S$ is $\mathsf{C}$-colorable.

Implication $(2)\Rightarrow(3)$

The proof of this implication heavily relies on an old result that goes back
in 1949 by Rado (Rado, 1949) known as Rado’s Selection Principle. We write
$\mathcal{P}_{\mathsf{fin}}(A)$ for the finite powerset of a set $A$, i.e.,
the set that collects all the finite subsets of $A$. Furthermore, given a
function $f:A\rightarrow B$, we write $f_{|C}$ for the restriction of $f$ to
$C\subseteq A$.

###### Theorem 5.5 (Rado’s Selection Principle).

Let $A$ and $B$ be arbitrary sets. Assume that, for each
$C\in\mathcal{P}_{\mathsf{fin}}(A)$, $f_{C}$ is a function $C\rightarrow B$ (a
so-called “local function”). Assume further that, for every $x\in A$, the set
$\\{f_{C}(x)\mid C\in\mathcal{P}_{\mathsf{fin}}(A)\text{ and }x\in C\\}$ is
finite. Then, there is a function $f:A\rightarrow B$ (a so-called “global
function”) such that, for every $C\in\mathcal{P}_{\mathsf{fin}}(A)$, there is
$D\in\mathcal{P}_{\mathsf{fin}}(A)$ with $C\subsetneq D$ and
$f_{|C}={f_{D}}_{|C}$.

Several proofs and applications of Rado’s Theorem can be found in (Mirsky,
1971). We proceed to discuss how it is used to prove $(2)\Rightarrow(3)$. By
hypothesis, for each $S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$, there
exists a precoloring of $S$, i.e., a function
$\mathit{pc}_{S}:S\rightarrow\mathbb{N}$, that is non-uniformly
$\mathsf{C}$-injective and $\mathsf{C}$-consistent. Since, for every
$(v,G)\in\mathbf{VG}$, $\mathsf{A}(v,G)$ is finite, we can conclude that the
following holds: for every $(v,G)\in\mathbf{VG}$, the set
$\\{\mathit{pc}_{S}(v,G)\mid S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})\text{
and }(v,G)\in S\\}$ is finite. This allows us to apply Theorem 5.5 with
$A=\mathbf{VG}$ and $B=\mathbb{N}$. Therefore, there exists a function
$f:\mathbf{VG}\rightarrow\mathbb{N}$ such that, for every
$S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$, there exists
$S^{\prime}\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$ with $S\subsetneq
S^{\prime}$ and $f_{|S}={\mathit{pc}_{S^{\prime}}}_{|S}$. Interestingly, by
exploiting the latter property of the function $f$ guaranteed by Theorem 5.5,
and the fact that, for each $S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$,
$\mathit{pc}_{S}$ is a precoloring of $S$ that is non-uniformly
$\mathsf{C}$-injective and $\mathsf{C}$-consistent, it is not difficult to
show that $f$ is a precoloring of $\mathbf{VG}$ that is non-uniformly
$\mathsf{C}$-injective and $\mathsf{C}$-consistent, and item (3) follows.

Implication $(3)\Rightarrow(1)$

We finally discuss the proof of the last implication. The goal is to devise a
subgraph family $\mathsf{F}$ and a filtering function $f$ such that $\text{\rm
Rank}(\mathsf{C})=\text{\rm Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$,
which in turn proves item $(1)$. By hypothesis, there exists a precoloring
$\mathit{pc}$ of $\mathbf{VG}$ that is non-uniformly $\mathsf{C}$-injective
and $\mathsf{C}$-consistent. We define $\mathsf{F}$ in such way that, for
every $(v,G)\in\mathbf{VG}$, $|\mathsf{F}(v,G)|=\mathit{pc}(v,G)$; note that
such a subgraph family exists since
$\mathit{pc}(v,G)\in\\{0,\ldots,|\mathsf{A}(v,G)|\\}$. Now, defining the
filtering function $f$ is a non-trivial task. Let $R_{\mathit{pc}}$ be the
relation

$\left\\{(i,j)\in\mathbb{N}\times\mathbb{N}\mid\text{ there are
}(u,G),(v,G)\text{ in }\mathbf{VG}\text{ such that}\right.\\\
\left.\mathsf{C}(u,G)<\mathsf{C}(v,G),\mathit{pc}(u,G)=i,\text{ and
}\mathit{pc}(v,G)=j\right\\}.$

The fact that $\mathit{pc}$ is non-uniformly $\mathsf{C}$-injective allows us
to conclude that $R_{\mathit{pc}}$ is irreflexive. Moreover, the
$\mathsf{C}$-consistency of $\mathit{pc}$ implies that $R_{\mathit{pc}}$ is
asymmetric. Observe now that if we extend $R_{\mathit{pc}}$ into a total order
$R_{\mathit{pc}}^{\star}$ over $\mathbb{N}$, and then show that
$R_{\mathit{pc}}^{\star}$ can be embedded into a carefully chosen countable
subset $N$ of $\mathbb{R}$, then we obtain the desired filtering function $f$,
which assigns real numbers to the sizes of the subgraph families assigned to
the pairs of $\mathbf{VG}$ by $\mathsf{F}$ as dictated by the embedding of
$R_{\mathit{pc}}^{\star}$ into $N\subsetneq\mathbb{R}$. Let us now briefly
discuss how this is done. The binary relation $R_{\mathit{pc}}$ is first
extended into the strict partial order $R_{\mathit{pc}}^{+}$ by simply taking
its transitive closure. Now, the fact that $R_{\mathit{pc}}^{+}$ can be
extended into a total order $R_{\mathit{pc}}^{\star}$ over $\mathbb{N}$
follows by the order-extension principle (a.k.a. Szpilrajn Extension Theorem),
shown by Szpilrajn in 1930 (Szpilrajn, 1930), which essentially states that
every partial order can be extended into a total order. Finally, the fact that
$R_{\mathit{pc}}^{\star}$ can be embedded into $N\subsetneq\mathbb{R}$ is
shown via the back-and-forth method, a technique for showing isomorphism
between countably infinite structures satisfying certain conditions.

#### A Bounded-Value-Like Property.

As discussed at the beginning of the section, despite our efforts, we have not
managed to isolate a property in the spirit of the bounded value property that
can characterize subgraph motif measures relative to the induced ranking. We
managed, however, to isolate a bounded-value-like property that is a necessary
condition for a measure being subgraph motif relative to the induced ranking.
It should be clear that the bounded value property introduced in the previous
section (see Definition 4.1) is not enough towards a necessary condition. This
is because, as discussed in Section 3, there is a measure (see the one devised
in the proof of Proposition 3.2) that is not subgraph motif, which means that
it does not enjoy the bounded value property, but it is subgraph motif
relative to the induced ranking. On the other hand, to our surprise, a non-
uniform version of the bounded value property leads to the desired necessary
condition. Let us make this more precise. The ranking induced by a measure
$\mathsf{C}$ compares only the values of vertices of the same graph; a pair
$((u,G),(v,G^{\prime}))$, where $G\neq G^{\prime}$, will never appear in
$\text{\rm Rank}(\mathsf{C})$. This led us to conjecture that for
characterizing subgraph motif measures relative to the induced ranking, it
suffices to bound the number of different values that can be assigned among
vertices inside the same graph that are surrounded by a limited number of
connected subgraphs. This leads to the non-uniform version of the bounded
value property:

###### Definition 5.6 (Non-Uniform Bounded Value Property).

A measure $\mathsf{C}$ enjoys the non-uniform bounded value property if, for
every integer $n>0$ and graph $G\in\mathbf{G}$, $|\text{\rm
Val}_{G}^{n}(\mathsf{C})|\leq n+1$.

We can then show the following implication:

###### Proposition 5.7.

Consider a centrality measure $\mathsf{C}$. If there exists a precoloring of
$\mathbf{VG}$ that is non-uniformly $\mathsf{C}$-injective, then $\mathsf{C}$
enjoys the non-uniform bounded value property.

By combining Theorem 5.4 and Proposition 5.7, we get the following corollary,
which establishes that indeed the non-uniform bounded value property leads to
the desired necessary condition:

###### Corollary 5.8.

If a centrality measure is a subgraph motif measure relative to the induced
ranking, then it enjoys the non-uniform bounded value property.

The question whether the non-uniform bounded value property is also a
sufficient condition is negatively settled by the next result:

###### Proposition 5.9.

There exists a measure that is not a subgraph motif measure relative to the
induced ranking, but it enjoys the non-uniform bounded value property.

Let us stress that Corollary 5.8 equips us with a convenient tool for showing
that a centrality measure $\mathsf{C}$ is not a subgraph motif measure
relative to the induced ranking: it suffices to show that there exist an
integer $n>0$ and a graph $G$ such that $|\text{\rm
Val}_{G}^{n}(\mathsf{C})|>n+1$. In the case of closeness, we can show that
there exists a graph $G$ such that $|\text{\rm
Val}_{G}^{5}(\mathsf{Closeness})|>6$, which in turn implies that:

###### Proposition 5.10.

$\mathsf{Closeness}$ is not a subgraph motif measure relative to the induced
ranking.

More inexpressibility results of the above form concerning established
centrality measures are discussed in Section 7.

#### Connected Graphs.

After a quick inspection of the proof of Proposition 4.3, one can conclude
that $\mathsf{Closeness}$ is not a subgraph motif measure even if concentrate
on connected graphs. On the other hand, the proof of Proposition 5.10 heavily
relies on the fact that the employed graphs are not connected. This
observation led us ask ourselves whether $\mathsf{Closeness}$ is a subgraph
motif measure relative to the induced ranking if we consider only connected
graphs. It turned out that, if we focus on connected graphs, not only
$\mathsf{Closeness}$, but every measure is a subgraph motif measure relative
to the induced ranking. We proceed to formalize the above discussion.

Let $\mathbf{VCG}=\\{(v,G)\in\mathbf{VG}\mid G\text{ is connected}\\}$. For an
arbitrary centrality measure $\mathsf{C}$, its version that operates only on
connected graphs is defined as the function
$\mathsf{ConC}:\mathbf{VCG}\rightarrow\mathbb{R}$ such that, for every
$(v,G)\in\mathbf{VCG}$, $\mathsf{C}(v,G)=\mathsf{ConC}(v,G)$, i.e., it is the
restriction of $\mathsf{C}$ over $\mathbf{VCG}$. We then say that
$\mathsf{ConC}$ is a subgraph motif measure (resp., subgraph motif measure
relative to the induced ranking) if there exist a subgraph family $\mathsf{F}$
and a filtering function $f$ such that
$\mathsf{ConC}=\mathsf{Con}\mathsf{C}\langle\mathsf{F},f\rangle$ (resp.,
$\text{\rm Rank}(\mathsf{C})\cap\mathbf{VCG}^{2}=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)\cap\mathbf{VCG}^{2}$). We can then
establish the following result:

###### Theorem 5.11.

Consider a centrality measure $\mathsf{C}$. It holds that $\mathsf{ConC}$ is a
subgraph motif measure relative to the induced ranking.

As discussed above, $\mathsf{Con}\mathsf{Closeness}$ is not a subgraph motif
measure (implicit in the proof of Proposition Proposition 4.3), whereas
$\mathsf{Con}\mathsf{Closeness}$ is a subgraph motif measure relative to the
induced ranking (follows from Theorem 5.11). This reveals a striking
difference between the two notions of expressiveness, that is, being subgraph
motif or being subgraph motif realtive to the induced ranking, when focussing
on connected graphs.

We conclude this section by stressing that Theorem 5.11 is interesting in its
own right as it provides a unifying framework for all centrality measures in a
practically relevant setting: connected graphs and induced ranking. Indeed,
graphs in real-life scenarios, although might be non-connected, they typically
consists of one dominant connected component and several small components that
are usually neglected as, by default, the most important vertex appears in the
dominant component. Moreover, in real-life graph-based applications, we are
usually interested in the induced ranking rather than the absolute centrality
values assigned to vertices.

##  6\. Monotonic Filtering Functions

Until now, we considered arbitrary filtering functions without any
restrictions. On the other hand, the filtering functions $f_{\times 2}$ and
$\log_{2}$ used to express $\mathsf{Stress}$ and
$\mathsf{All\text{\rm-}Subgraphs}$, respectively, as subgraph motif measures
are monotonic; formally, a filtering function $f$ is monotonic if, for all
$x,y\in\mathbb{N}$, $x\leq y$ implies $f(x)\leq f(y)$. It is natural to ask
Questions I and II for monotonic subgraph motif centrality measures, i.e.,
subgraph motif centrality measures $\mathsf{C}\langle\mathsf{F},f\rangle$
where $f$ is monotonic. Needless to say, one can study a plethora of different
families of subgraph motif centrality measures that use filtering functions
with certain properties (e.g., linear functions, logarithmic functions, etc.).
However, such a thorough analysis is beyond the scope of this work, and it
remains the subject of future research. In what follows, we revisit Questions
I and II focussing on the family of subgraph motif measures that use monotonic
filtering functions.

#### Monotonic Subgraph Motif Measures.

We first give a result analogous to Proposition 3.2, establishing that not all
subgraph motif measures are monotonic, which means that the bounded value
property (Definition 4.1) is not the answer to Question I in the case of
monotonic subgraph motif measures.

###### Proposition 6.1.

There is a subgraph motif centrality measure that is not monotonic.

###### Proof.

Let $\hat{G}$ be the graph
$(\\{v_{1},v_{2},v_{3}\\},\\{\\{v_{2},v_{3}\\}\\})$. Consider the centrality
measure $\mathsf{C}$ defined as follows:

$\mathsf{C}(v,G)\ =\ \begin{cases}1&G\neq\hat{G}\text{ or }(G=\hat{G}\text{
and }v=v_{3})\\\ 3&G=\hat{G}\text{ and }v=v_{1}\\\ 2&G=\hat{G}\text{ and
}v=v_{2}.\end{cases}$

We first show that $\mathsf{C}$ is a subgraph motif measure. Notice that, for
every vertex $v\in\mathbf{V}$,
$\mathsf{C}(v,G_{v})=\mathsf{C}(v_{3},\hat{G})=1$. Hence, we have only two
options concerning the set of connected subgraphs assigned to the vertices of
$\hat{G}$ by a subgraph family, and the filtering function, which are the
following: with $G_{uv}$ being the single-edge graph
$(\\{u,v\\},\\{\\{u,v\\}\\})$, either

$\mathsf{F}_{1}(v,\hat{G})\ =\ \begin{cases}\emptyset&v=v_{1}\\\
\\{G_{v_{2}},G_{v_{2}v_{3}}\\}&v=v_{2}\\\ \\{G_{v_{3}}\\}&v=v_{3}\end{cases}$

with $f_{1}(0)=3$, $f_{1}(1)=1$ and $f_{1}(2)=2$, or

$\mathsf{F}_{2}(v,\hat{G})\ =\ \begin{cases}\\{G_{v_{1}}\\}&v=v_{1}\\\
\\{G_{v_{2}},G_{v_{2}v_{3}}\\}&v=v_{2}\\\ \emptyset&v=v_{3}\end{cases}$

with $f_{2}(0)=1$, $f_{2}(1)=3$ and $f_{2}(2)=2$. Now, by extending
$\mathsf{F}_{1}$ and $\mathsf{F}_{2}$ in such a way that, for
$(v,G)\in\mathbf{VG}$ with $G\neq\hat{G}$, $\mathsf{F}_{1}(v,G)=\\{G_{v}\\}$
and $\mathsf{F}_{2}(v,G)=\emptyset$, it is clear that
$\mathsf{C}=\mathsf{C}\langle\mathsf{F}_{1},f_{1}\rangle=\mathsf{C}\langle\mathsf{F}_{2},f_{2}\rangle$.
Observe, however, that $\mathsf{C}\langle\mathsf{F}_{1},f_{1}\rangle$ and
$\mathsf{C}\langle\mathsf{F}_{2},f_{2}\rangle$ are not monotonic.

The proof of Proposition 6.1 essentially tells us that the key reason why the
subgraph motif measure $\mathsf{C}$ is not monotonic is because the maximum
centrality value is assigned to a vertex surrounded by few connected
subgraphs. To formalize this intuition, we first collect all the different
values $x$ assigned by a measure $\mathsf{C}$ to the vertices of a graph $G$
that are surrounded by “too many” connected subgraphs such that $x$ does not
exceed the maximum value assigned by $\mathsf{C}$ to the vertices of $G$
surrounded by “too few” connected subgraphs. More precisely, for an integer
$n>0$, we define the set

$\text{\rm BVal}_{G}^{n}(\mathsf{C})\ =\ \bigg{\\{}x\in\bigcup_{m>0}\text{\rm
Val}_{G}^{m}(\mathsf{C})\mid\\\ x\not\in\text{\rm
Val}_{G}^{n}(\mathsf{C})~{}~{}\text{and}~{}~{}x<\max\text{\rm
Val}_{G}^{n}(\mathsf{C})\bigg{\\}},$

We then define the set of values

$\text{\rm BVal}^{n}(\mathsf{C})\ =\ \bigcup_{G\in\mathbf{G}}\text{\rm
BVal}_{G}^{n}(\mathsf{C}).$

We can now define a refined version of the bounded value property, which
provides a better upper bound for $|\text{\rm Val}^{n}(\mathsf{C})|$:

###### Definition 6.2 (Monotonic Bounded Value Property).

A centrality measure $\mathsf{C}$ enjoys the monotonic bounded value property
if, for every integer $n>0$, $|\text{\rm Val}^{n}(\mathsf{C})|\leq
n+1-|\text{\rm BVal}^{n}(\mathsf{C})|$.

It is easy to see that the measure $\mathsf{C}$ devised in the proof of
Proposition 6.1 does not enjoy the monotonic bounded value property. Indeed,
$\text{\rm Val}^{1}(\mathsf{C})=\\{1,3\\}$ and $\text{\rm BVal}^{1}=\\{2\\}$,
and thus, $|\text{\rm Val}^{1}(\mathsf{C})|=2>1$. The above refinement of the
bounded value property is all we need to get a precise characterization of
monotonic subgraph motif measures; hence the name “monotonic bounded balue
property”.

###### Theorem 6.3.

Consider a centrality measure $\mathsf{C}$. The following statements are
equivalent:

  1. (1)

$\mathsf{C}$ is a monotonic subgraph motif centrality measure.

  2. (2)

$\mathsf{C}$ enjoys the monotonic bounded value property.

#### Induced Ranking.

Concerning the expressiveness of monotonic subgraph motif centrality measures
relative to the induced ranking, we can show that the non-uniform version of
the monotonic bounded value property provides a precise characterization.

###### Definition 6.4 (Non-Uniform Monotonic Bounded Value Property).

A centrality measure $\mathsf{C}$ enjoys the non-uniform monotonic bounded
value property if, for every integer $n>0$ and graph $G\in\mathbf{G}$, it
holds that $|\text{\rm Val}_{G}^{n}(\mathsf{C})|\leq n+1-|\text{\rm
BVal}_{G}^{n}(\mathsf{C})|$.

We can then establish the following characterization that is in striking
difference with Theorem 5.4, which shows that the non-uniform bounded value
property is only a necessary condition (but not a sufficient condition) for a
centrality measure being subgraph motif relative to the induced ranking.

###### Theorem 6.5.

Consider a centrality measure $\mathsf{C}$. The following statements are
equivalent:

  1. (1)

$\mathsf{C}$ is a monotonic subgraph motif centrality measure relative to the
induced ranking.

  2. (2)

$\mathsf{C}$ enjoys the non-uniform monotonic bounded value property.

#### Connected Graphs.

Recall that the family of subgraph motif measures relative to the induced
ranking provides a unifying framework for all centrality measures whenever we
concentrate on connected graphs (see Theorem 5.11). Interestingly, a careful
inspection of the proof of Theorem 5.11 reveals that this holds even for the
family of monotonic subgraph motifs relative to the induced ranking.

###### Theorem 6.6.

For a measure $\mathsf{C}$ it holds that $\mathsf{ConC}$ is a monotonic
subgraph motif measure relative to the induced ranking.

##  7\. Classification

The results of the previous sections provide tools that allow us to establish
whether a measure can be expressed as a (monotonic) subgraph motif measure
(relative to the induced ranking). With such technical tools available, the
next step is to determine whether existing measures belong to the family of
(monotonic) subgraph motif measures (relative to the induced ranking). Such a
classification, apart from being interesting in its own right, will provide
insights on the structural similarities and differences among existing
centrality measures. To this end, we focus on established measures from the
literature (including $\mathsf{Stress}$, $\mathsf{All\text{\rm-}Subgraphs}$,
and $\mathsf{Closeness}$), and provide a rather complete classification
depicted in Tables 1 and 2; the formal definitions of the considered measures
are omitted, and can be found in the appendix. The second (resp., third)
column determines whether the measure $\mathsf{C}$ stated in the first column
is subgraph motif (resp., subgraph motif relative to the induced ranking);
$\checkmark$ means that it is, $\times$ means that it is not,
$\times[\mathit{trees}]$ means that it is not even for trees,
$\checkmark[\mathit{con}]$ means that it is over connected graphs,
$\checkmark[\mathit{trees}]$ means that it is over trees, and $?$ means that
it is open. Concerning Table 2, $\star$ refers to any measure considered in
Table 1 apart from $\mathsf{Betweenness}$, and $\times[\mathit{con}]$ means
that the respective measure (i.e., $\mathsf{Betweenness}$) is not monotonic
subgraph motif even for connected graphs. Note that Table 2 is identical to
Table 1, apart from $\mathsf{Betweenness}$, which is provably not monotonic
subgraph motif (relative to the induced ranking).

We would like to remark that the result $\checkmark[\mathit{con}]$ for
$\mathsf{Eigenvector}$ in both tables holds for a broader class of graphs than
connected graphs. Moreover, we can show that $\mathsf{Betweenness}$ is a
(monotonic) subgraph motif measure (relative to the induced ranking) for a
class of graphs that captures the class of trees and is incomparable to the
class of connected graphs. Nevertheless, for the sake of readability, we state
our expressibility results only for trees and connected graphs; further
details can be found in the appendix.

Measure | Absolute Values | Induced Ranking
---|---|---
$\mathsf{Stress}$ | $\checkmark$ | $\checkmark$
$\mathsf{All\text{\rm-}Subgraphs}$ | $\checkmark$ | $\checkmark$
$\mathsf{Degree}$ | $\checkmark$ | $\checkmark$
$\mathsf{Cross\text{\rm-}Clique}$ | $\checkmark$ | $\checkmark$
$\mathsf{Closeness}$ | $\times[\mathit{trees}]$ |  $\times$ and $\checkmark[\mathit{con}]$
$\mathsf{Harmonic}$ | $\times[\mathit{trees}]$ |  $\times$ and $\checkmark[\mathit{con}]$
$\mathsf{PageRank}$ | $\times[\mathit{trees}]$ |  $\times$ and $\checkmark[\mathit{con}]$
$\mathsf{Eigenvector}$ | $\times[\mathit{trees}]$ |  $?$ and $\checkmark[\mathit{con}]$
$\mathsf{Betweenness}$ |  $?$ and $\checkmark[\mathit{trees}]$ |  $?$ and $\checkmark[\mathit{con}]$
Table 1. Subgraph Motif Measures  Measure | Absolute Values | Induced Ranking
---|---|---
$\star$ | as in Table 1 | as in Table 1
$\mathsf{Betweenness}$ |  $\times[\mathit{con}]$ and $\checkmark[\mathit{trees}]$ |  $\times$ and $\checkmark[\mathit{con}]$
Table 2. Monotonic Subgraph Motif Measures

#### Take-home Messages.

We proceed to highlight the key take-home messages of the above
classification, which we believe they provide further insights concerning the
centrality measures in question:

  1. (1)

If we focus on the induced ranking rather than the absolute values over
connected graphs, then the family of monotonic subgraph motif measures should
be understood as a unifying framework that incorporates every other measure.

  2. (2)

Our classification excludes a priori the adoption of certain centrality
measures (e.g., $\mathsf{Closeness}$, $\mathsf{Harmonic}$, etc.) in
applications where the importance of a vertex should be measured based on the
subgraph motifs surrounding it.

  3. (3)

$\mathsf{Betweenness}$, which computes the percentage of the shortest paths in
a graph going through a vertex, is of different nature compared to all the
other measures. Notably, although it looks similar to $\mathsf{Stress}$, it
behaves in a significantly different way. The relationship of
$\mathsf{Betweenness}$ with (monotonic) subgraph motif measures deserves
further investigation.

  4. (4)

There is a notable difference between the two feedback measures considered in
our classification, i.e., $\mathsf{PageRank}$ and $\mathsf{Eigenvector}$, that
deserves further exploration. As mentioned above, $\mathsf{Eigenvector}$ is a
(monotonic) subgraph measure relative to the induced ranking over a broader
class $\mathcal{C}$ of graphs than connected graphs, whereas
$\mathsf{PageRank}$ is provable not a subgraph motif measure over the class
$\mathcal{C}$.

#### A Note on Directed Graphs.

As discussed in the clarification remark at the end of Section 1, although our
analysis (including the classification of this section) focused on undirected
graphs, all the notions and results can be transferred to the case of directed
graphs under the notion of weak connectedness. The only exception is the
negative result $\times[\mathit{trees}]$ for $\mathsf{Eigenvector}$ in both
Tables 1 and 2. Although we can show that for directed graphs,
$\mathsf{Eigenvector}$ is not a (monotonic) subgraph motif centrality measure,
it remains open whether these negative results hold even for directed trees
(i.e., directed graphs whose underlying undirected graph is a tree).

##  8\. Conclusions

We have provided a rather complete picture concerning the absolute
expressiveness of the family of (monotonic) subgraph motif centrality measures
(relative to the induced ranking) by establishing precise characterizations.
We have also presented a detailed classification of standard centrality
measures by using the tools provided by the aforementioned characterizations.
Recall that, although our development focused on undirected graphs, all the
notions and results can be transferred to the case of directed graphs under
the standard notion of weak connectedness.

At this point, we would like to stress that the machinery on graph colorings,
introduced in Section 5, can be used to provide characterizations for all the
families considered in the paper, and not only for the family of subgraph
motif measures relative to the induced ranking. For example, we can show that
a measure $\mathsf{C}$ is subgraph motif iff there exists a precoloring of
$\mathbf{VG}$ that is uniformly $\mathsf{C}$-injective; the latter is defined
as non-uniform $\mathsf{C}$-injectivity with the difference that
$\mathsf{C}$-injectivity is enforced across all the graphs (not only inside a
certain graph).

The obvious question that remains open is whether we can isolate a bounded-
value-like property that characterizes subgraph motif measures relative to the
induced ranking. We strongly believe that the coloring-based characterization
established in this work (Theorem 6.5) is a useful tool towards such a
bounded-value-like characterization. Finally, towards a deeper understanding
of the family of subgraph motif measures, one should perform a more refined
analysis by focussing on restricted classes of subgraph families and filtering
functions that enjoy desirable structural properties.

## References

  * (1)
  * Angles et al. (2017) Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017.  Foundations of Modern Query Languages for Graph Databases.  _ACM Comput. Surv._ 50, 5 (2017), 68:1–68:40.
  * Bonacich (1987) Phillip Bonacich. 1987\.  Power and centrality: A family of measures.  _American journal of sociology_ 92, 5 (1987), 1170–1182.
  * Borgatti and Everett (2006) Stephen P. Borgatti and Martin G. Everett. 2006.  A Graph-theoretic perspective on centrality.  _Soc. Networks_ 28, 4 (2006), 466–484.
  * Dezső and Barabási (2002) Zoltán Dezső and Albert-László Barabási. 2002\.  Halting viruses in scale-free networks.  _Phys. Rev. E_ 65 (2002), 055103.  Issue 5.
  * Everett and Borgatti (1998) Martin G Everett and Stephen P Borgatti. 1998.  Analyzing clique overlap.  _Connections_ 21, 1 (1998), 49–61.
  * Freeman (1977) Linton C Freeman. 1977\.  A set of measures of centrality based on betweenness.  _Sociometry_ (1977), 35–41.
  * Hagberg et al. (2008) Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008\.  _Exploring network structure, dynamics, and function using NetworkX_.  Technical Report.
  * Huang et al. (2020) Xinyu Huang, Dongming Chen, Dongqi Wang, and Tao Ren. 2020\.  Identifying Influencers in Social Networks.  _Entropy_ 22, 4 (2020), 450.
  * Iván and Grolmusz (2010) Gábor Iván and Vince Grolmusz. 2010.  When the Web meets the cell: using personalized PageRank for analyzing protein interaction networks.  _Bioinformatics_ 27, 3 (2010), 405–407.
  * Kitti (2016) Mitri Kitti. 2016\.  Axioms for centrality scoring with principal eigenvectors.  _Social Choice and Welfare_ 46, 3 (2016), 639–653.
  * Koschützki et al. (2007) Dirk Koschützki, Henning Schwöbbermeyer, and Falk Schreiber. 2007\.  Ranking of network elements based on functional substructures.  _Journal of Theoretical Biology_ 248, 3 (2007), 471–479.
  * Masoudi-Nejad et al. (2012) A. Masoudi-Nejad, F. Schreiber, and Z.R.M. Kashani. 2012\.  Building Blocks of Biological Networks: A Review on Major Network Motif Discovery Algorithms.  _IET Systems Biology_ 6, 5 (2012), 164–174.
  * Mirsky (1971) Leonid Mirsky. 1971\.  _Transversal Theory: An Account of Some Aspects of Combinatorial Mathematics_.  Academic Press.
  * Newman (2018) Mark Newman. 2018\.  _Networks_.  Oxford University Press.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank Citation Ranking: Bringing Order to the Web._ Technical Report 1999-66.
  * Rado (1949) Richard Rado. 1949\.  Axiomatic treatment of rank in infinite sets.  _Canad. J. Math._ (1949), 337–343.
  * Riveros and Salas (2020) Cristian Riveros and Jorge Salas. 2020.  A Family of Centrality Measures for Graph Data Based on Subgraphs. In _ICDT_. 23:1–23:18.
  * Rochat (2009) Yannick Rochat. 2009\.  _Closeness centrality extended to unconnected graphs: The harmonic centrality index_.  Technical Report.
  * Sabidussi (1966) Gert Sabidussi. 1966\.  The Centrality Index of a Graph.  _Psychometrika_ 31, 4 (1966), 581–603.
  * Shimbel (1953) Alfonso Shimbel. 1953\.  Structural Parameters of Communication Networks.  _Bull. Math. Biophysics_ 15 (1953), 501–507.
  * Szpilrajn (1930) Edward Szpilrajn. 1930\.  Sur l’extension de l’ordre partiel.  _Fundamenta Matematicae_ 16 (1930), 386–389.
  * van den Brink and Gilles (2000) René van den Brink and Robert P. Gilles. 2000.  Measuring domination in directed networks.  _Social Networks_ 22, 2 (2000), 141–157.
  * Was and Skibski (2018) Tomasz Was and Oskar Skibski. 2018.  Axiomatization of the PageRank Centrality.. In _IJCAI_. 3898–3904.

##  Appendix A Preliminary Notions

In this preliminary section, we present some auxiliary notions that have not
been introduced in the main body of the paper, but are needed for the proofs
given in the appendix. In particular, we are going to introduce some special
classes of graphs (lines and stars), and a couple of useful properties of
centrality measures (closure under isomorphism and locality).

### Special Graphs

The line graph with $m>0$ vertices, denoted $L_{m}$, is the undirected graph
$(V,E)$, where

$V\ =\ \\{1,\ldots,m\\}\quad\text{and}\quad
E=\bigcup_{i\in\\{1,\ldots,m-1\\}}\\{\\{i,i+1\\}\\}.$

The star graph with $m>0$ vertices, denoted $S_{m}$, is the undirected graph
$(V,E)$, where

$V\ =\ \\{1,\ldots,m\\}\quad\text{and}\quad E\ =\
\bigcup_{i\in\\{2,\ldots,m\\}}\\{\\{1,i\\}\\}.$

We refer to the vertex $1$ as the center of $S_{m}$.

### Closure Under Isomorphism

We say that two graphs $G_{1}$ and $G_{2}$ are isomorphic, denoted
$G_{1}\simeq G_{2}$, if there exists a bijective function $h:V(G_{1})\to
V(G_{2})$ such that $\\{v,u\\}\in E(G_{1})$ iff $\\{h(v),h(u)\\}\in E(G_{2})$.
Furthermore, given the vertices $v_{1}\in V(G_{1})$ and $v_{2}\in V(G_{2})$,
we say that the pairs $(v_{1},G_{1})$ and $(v_{2},G_{2})$ are isomorphic,
denoted $(v_{1},G_{1})\simeq(v_{2},G_{2})$, if $G_{1}\simeq G_{2}$ witnessed
by $h$, and $h(v_{1})=v_{2}$. We are now ready to define the property of being
closed under isomorphism for centrality measures.

###### Definition A.1.

Consider a centrality measure $\mathsf{C}$. We say that $\mathsf{C}$ is closed
under isomorphism if, for every two pairs $(v_{1},G_{1})\in\mathbf{VG}$ and
$(v_{2},G_{2})\in\mathbf{VG}$, $(v_{1},G_{1})\simeq(v_{2},G_{2})$ implies
$\mathsf{C}(v_{1},G_{1})=\mathsf{C}(v_{2},G_{2})$.

In simple words, the above property states that the values assigned by a
measure to the vertices of a graph do not depend on the names of the vertices,
but only on the structure of the graph; hence, the above property is sometimes
called anonymity.

### Locality

We finally recall the so-called locality property. Recall that, given a graph
$G$ and a set of vertices $S\subseteq V(G)$, we write $G[S]$ for the subgraph
of $G$ induced by $S$. Moreover, for a vertex $v\in V(G)$, we write $K_{v}(G)$
for the set of vertices occurring in the component of $G$ containing the
vertex $v$. The definition of locality follows:

###### Definition A.2.

A centrality measure $\mathsf{C}$ is local if, for every pair
$(v,G)\in\mathbf{VG}$, $\mathsf{C}(v,G)=\mathsf{C}(v,G[K_{v}(G)])$.

In simple words, the above property tells us that the value assigned by a
measure $\mathsf{C}$ to a vertex $v$ in a graph $G$ depends only on the
component $G^{\prime}\in\text{\rm Comp}(G)$ that contains $v$, i.e., during
the calcuation of $\mathsf{C}(v,G)$, $\mathsf{C}$ considers only the component
$G^{\prime}$.

##  Appendix B Proofs of Section 3

### Proof of Proposition 3.4

Let $\hat{G}=(\\{v_{1},v_{2},v_{3},v_{4}\\},\\{\\{v_{1},v_{2}\\}\\})$.
Consider the centrality measure $\mathsf{C}$ defined as follows:

$\mathsf{C}(v,G)\ =\ \begin{cases}1&G\neq\hat{G}\\\ i+1&G=\hat{G}\text{ and
}v=v_{i}\text{ for }i\in[4].\end{cases}$

It suffices to focus on the set of graphs $\mathbf{G}^{\star}=\\{G_{v}\mid
v\in\mathbf{V}\\}\cup\\{\hat{G}\\}\subseteq\mathbf{G}$. By providing an
argument similar to that in the proof of Proposition 3.2, we can show that,
for every subgraph family $\mathsf{F}$ and filtering function $f$, there exist
$1\leq i<j\leq 4$ such that
$\mathsf{C}\langle\mathsf{F},f\rangle(v_{i},\hat{G})=\mathsf{C}\langle\mathsf{F},f\rangle(v_{j},\hat{G})$.
Therefore,
$\\{((v_{i},\hat{G}),(v_{j},\hat{G})),((v_{j},\hat{G}),(v_{i},\hat{G}))\\}\subseteq\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. On the other hand, only
$((v_{i},\hat{G}),(v_{j},\hat{G}))$ belongs to $\text{\rm Rank}(\mathsf{C})$.
Consequently, for every subgraph family $\mathsf{F}$ and filtering function
$f$, $\text{\rm Rank}(\mathsf{C})\neq\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$, and the claim follows.

##  Appendix C Proofs of Section 4

### Proof of Theorem 4.2

$\underline{(1\Rightarrow 2).}$ By contradiction, assume that $\mathsf{C}$
does not enjoy the bounded value property, namely there exists an integer
$n\geq 1$ such that $|\text{\rm Val}^{n}(\mathsf{C})|>n+1$. By hypothesis,
$\mathsf{C}$ is a subgraph motif centrality measure, and thus, there exist a
subgraph family $\mathsf{F}$ and a filtering function $f$ such that the
following holds: for every $(v,G)\in\mathbf{VG}$,
$\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$. We now define the
set

$B_{n}\ =\ \left\\{|\mathsf{F}(v,G)|\mid(v,G)\in\mathbf{VG}\text{ and
}|\mathsf{A}(v,G)|\leq n\right\\}.$

Clearly, $|B_{n}|\leq n+1$ since $\mathsf{F}(v,G)\subseteq\mathsf{A}(v,G)$. We
also define the function $h:\text{\rm Val}^{n}(\mathsf{C})\to B_{n}$ such that

$h(\mathsf{C}(v,G))\ =\ |\mathsf{F}(v,G)|.$

By the pigeonhole principle, $h$ is not injective, i.e., there exist
$\mathsf{C}(v_{1},G_{1})$ and $\mathsf{C}(v_{2},G_{2})$ such that
$\mathsf{C}(v_{1},G_{1})\neq\mathsf{C}(v_{2},G_{2})$ but
$|\mathsf{F}(v_{1},G_{1})|=|\mathsf{F}(v_{2},G_{2})|$. This contradicts the
fact that $\mathsf{C}(v_{1},G_{1})=f(|\mathsf{F}(v_{1},G_{1})|)\neq
f(|\mathsf{F}(v_{2},G_{2})|)=\mathsf{C}(v_{2},G_{2})$.

$\underline{(2\Rightarrow 1).}$ The goal is to show that there exist a
subgraph family $\mathsf{F}$ and a filtering function $f$ such that, for every
$(v,G)\in\mathbf{VG}$,
$\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$. We start by
defining a total order $\preceq_{\mathsf{C}}$ over the set of values
$\text{\rm Val}(\mathsf{C})=\bigcup_{i=1}^{\infty}\text{\rm
Val}^{i}(\mathsf{C})$. By definition, for every $n,m>0$ such that $n\leq m$,
it holds that $\text{\rm Val}^{n}(\mathsf{C})\subseteq\text{\rm
Val}^{m}(\mathsf{C})$. In other words, as we increase the integer $n$ we are
adding new values to the set $\text{\rm Val}^{n}(\mathsf{C})$. We can now
define the binary relation $\preceq_{\mathsf{C}}$ over $\text{\rm
Val}(\mathsf{C})$ as follows: for each $a,b\in\text{\rm Val}(\mathsf{C})$,
$a\preceq_{\mathsf{C}}b$ if $a\leq b$, or there exists $n$ such that
$a\in\text{\rm Val}^{n}(\mathsf{C})$ but $b\not\in\text{\rm
Val}^{n}(\mathsf{C})$. It is easy to see that $\preceq_{\mathsf{C}}$ is a
total order over $\text{\rm Val}(\mathsf{C})$, and thus, it is a total order
over $\text{\rm Val}^{n}(\mathsf{C})$ for each $n>0$. For notational
convenience, in the rest of the proof we assume that $\text{\rm
Val}(\mathsf{C})=\\{a_{1},a_{2},a_{3},\ldots\\}$ and
$a_{1}\preceq_{\mathsf{C}}a_{2}\preceq_{\mathsf{C}}a_{3}\preceq_{\mathsf{C}}\cdots$.

By exploiting the total order $\preceq_{\mathsf{C}}$ over $\text{\rm
Val}(\mathsf{C})$, we now define a subgraph family $\mathsf{F}$. Consider an
arbitrary pair $(v,G)\in\mathbf{VG}$, and let $n=|\mathsf{A}(v,G)|$. By
hypothesis, $\mathsf{C}$ enjoys the bounded value property, which in turn
implies that $|\text{\rm Val}^{n}(\mathsf{C})|\leq n+1$. Therefore,
$\mathsf{C}(v,G)\in\left\\{a_{1},a_{2},...,a_{|\text{\rm
Val}^{n}(\mathsf{C})|}\right\\}=\text{\rm Val}^{n}(\mathsf{C})$. We further
observe that $\mathsf{A}(v,G)$ is a finite set, and assume that
$\mathsf{A}(v,G)=\\{S_{1},S_{2},...,S_{n}\\}$. The subgraph family
$\mathsf{F}$ is defined as follows:

$\mathsf{C}(v,G)=a_{i}\quad\text{implies}\quad\mathsf{F}(v,G)=\\{S_{1},...,S_{i-1}\\}.$

This is indeed a subgraph family since
$\mathsf{F}(v,G)\subseteq\mathsf{A}(v,G)$. Notice that $|\mathsf{F}(v,G)|=i-1$
for $i\in\\{1,...,|\text{\rm Val}^{n}(\mathsf{C})|+1\\}$. Finally, we define
the filtering function $f:\mathbb{N}\to\text{\rm Val}(\mathsf{C})$ as follows:
for each $i\in\mathbb{N}$,

$f(i)\ =\ a_{i+1}.$

We proceed to show the following technical lemma, which essentially states
that $\mathsf{F}$ and $f$ capture our intention:

###### Lemma C.1.

For every $(v,G)\in\mathbf{VG}$,
$\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$.

###### Proof.

Let $n=|\mathsf{A}(v,G)|$. If $\mathsf{C}(v,G)=a_{i}\in\text{\rm
Val}^{n}(\mathsf{C})$, then $|\mathsf{F}(v,G)|=i-1$. Therefore,
$f(|\mathsf{F}(v,G)|)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)=\mathsf{C}(v,G)$.
Conversely, if $\mathsf{C}\langle\mathsf{F},f\rangle(v,G)=a_{i}$, then
$|\mathsf{F}(v,G)|=i-1$, and thus, by construction, $\mathsf{C}(v,G)=a_{i}$.

By Lemma C.1, we get that $\mathsf{C}$ is a subgraph motif centrality measure,
and Theorem 4.2 follows.

### Proof of Proposition 4.3

Our goal is to show that $\mathsf{Closeness}$ does not enjoy the bounded value
property, and thus, by Theorem 4.2, it is not a subgraph motif measure, as
needed. To this end, we need to show that there exists an integer $n>0$ such
that $|\text{\rm Val}^{n}(\mathsf{Closeness})|>n+1$. For notational
convenience, given a pair $(v,G)\in\mathbf{VG}$, let
$\textsc{SD}(v,G)=\sum_{u\in K_{v}(G)}d_{G}(v,u)$. We observe that, for each
$n>0$,

$|\text{\rm
Val}^{n}(\mathsf{Closeness})|>n+1\quad\text{iff}\quad|\underbrace{\\{\textsc{SD}(v,G)\mid
v\in V(G)\text{ and }|\mathsf{A}(v,G)|\leq n\\}}_{\Sigma_{n}}|>n+1.$

Therefore, it suffices to show that there is $n>0$ such that
$|\Sigma_{n}|>n+1$. The rest of the proof proceeds in two main steps:

  1. (1)

For every $n>0$, it is easy to see that
$\textsc{SD}(1,L_{n})=\frac{n\cdot(n-1)}{2}$ and $|\mathsf{A}(1,L_{n})|=n$.
Therefore, it is clear that, for every $i,j\in[n]$ with $i\neq j$,
$\textsc{SD}(1,L_{i})\neq\textsc{SD}(1,L_{j})$, $|\mathsf{A}(1,L_{i})|\leq n$,
and $|\mathsf{A}(1,L_{j})|\leq n$. Therefore, $|\Sigma_{n}|>n$.

  2. (2)

It remains to show that there exists $n>0$ for which there are two pairs
$(v_{1},G_{1}),(v_{2},G_{2})$ of $\mathbf{VG}$ such that
$|\mathsf{A}(v_{1},G_{1})|\leq n$ and $|\mathsf{A}(v_{2},G_{2})|\leq n$, but
$\textsc{SD}(v_{1},G_{1})\neq\textsc{SD}(v_{2},G_{2})\neq\textsc{SD}(1,L_{i})$,
for every $i\leq n$, which implies that $|\Sigma_{n}|>n+1$, as needed. We
proceed to show that the latter holds for $n=5$. It is easy to verify that the
center of the star graph $S_{4}$ participates in eight connected subgraphs.
Thus, any leaf vertex participates in $1+2^{2}=5$ connected subgraphs.
Therefore, $|\mathsf{A}(i,S_{4})|\leq 5$ for $i\in\\{2,3,4\\}$. On the other
hand, if we look at the center vertex of $L_{3}$, that is, vertex $2$ of
$L_{3}$, it participates in four connected subgraphs, and thus,
$|\mathsf{A}(2,L_{3})|\leq 5$. Finally, we have that $\textsc{SD}(1,S_{4})=5$
whereas $\textsc{SD}(2,L_{3})=2$. Observe that there is no
$i\in\\{1,\ldots,5\\}$ such that $\textsc{SD}(1,L_{i})\in\\{2,5\\}$, and thus,
$|\Sigma_{5}|>6$.

##  Appendix D Proofs of Section 5

### Proof of Theorem 5.4

$\underline{(1\Rightarrow 2).}$ Since, by hypothesis, $\mathsf{C}$ is a
subgraph motif measure relative to the induced ranking, there are a subgraph
family $\mathsf{F}$ and a filtering function $f$ such that $\text{\rm
Rank}(\mathsf{C})=\text{\rm Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$.
Given a finite set $S\subsetneq\mathbf{VG}$, we define the function
$\mathit{pc}_{S}:S\rightarrow\mathbb{N}$ as follows: for every $(v,G)\in S$,
$\mathit{pc}_{S}(v,G)=|\mathsf{F}(v,G)|$. It is clear that $\mathit{pc}_{S}$
is a precoloring of $S$ since, by definition,
$\mathsf{F}(v,G)\subseteq\mathsf{A}(v,G)$, and thus,
$\mathit{pc}_{S}(v,G)\in\\{0,\ldots,|\mathsf{A}(v,G)|\\}$. It remains to show
that $\mathit{pc}_{S}$ is (i) non-uniformly $\mathsf{C}$-injective, and (ii)
$\mathsf{C}$-consistent, which in turn implies that $S$ is
$\mathsf{C}$-colorable:

  * (i)

Since $\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$, for every
$(u_{1},G),(u_{2},G)\in S$, it holds that
$\mathsf{C}(u_{1},G)\neq\mathsf{C}(u_{2},G)$ iff
$\mathsf{C}\langle\mathsf{F},f\rangle(u_{1},G)\not=\mathsf{C}\langle\mathsf{F},f\rangle(u_{2},G)$.
Therefore,
$\mathit{pc}_{S}(u_{1},G)=|\mathsf{F}(u_{1},G)|\neq|\mathsf{F}(u_{2},G)|=\mathit{pc}_{S}(u_{2},G)$,
which implies that $\mathit{pc}_{S}$ is non-uniformly $\mathsf{C}$-injective.

  * (ii)

By contradiction, assume that there exist
$(v_{1},G_{1}),(v_{2},G_{1}),(u_{1},G_{2})$ and $(u_{2},G_{2})$ such that
$\mathsf{C}(v_{1},G_{1})<\mathsf{C}(v_{2},G_{1})$ and
$\mathsf{C}(u_{1},G_{2})>\mathsf{C}(u_{2},G_{2})$ but
$\mathit{pc}_{S}(u_{1},G_{2})=\mathit{pc}_{S}(v_{1},G_{1})$ and
$\mathit{pc}_{S}(v_{2},G_{1})=\mathit{pc}_{S}(u_{2},G_{2})$. Therefore,
$|\mathsf{F}(v_{1},G_{1})|=|\mathsf{F}(u_{1},G_{2})|$ and
$|\mathsf{F}(v_{2},G_{1})|=|\mathsf{F}(u_{2},G_{2})|$. Consequently, using the
fact that $\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$,
$\mathsf{C}\langle\mathsf{F},f\rangle(v_{1},G_{1})<\mathsf{C}\langle\mathsf{F},f\rangle(v_{2},G_{1})=\mathsf{C}\langle\mathsf{F},f\rangle(u_{2},G_{2})<\mathsf{C}\langle\mathsf{F},f\rangle(u_{1},G_{2})=\mathsf{C}\langle\mathsf{F},f\rangle(v_{1},G_{1})$,
which is clearly a contradiction. Hence, $\mathit{pc}_{S}$ is also
$\mathsf{C}$-consistent.

$\underline{(2\Rightarrow 3).}$ The proof of this implication heavily relies
on Rado’s Selection Principle (see Theorem 5.5). By hypothesis, for each
$S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$, there exists a precoloring of
$S$, i.e., a function $\mathit{pc}_{S}:S\rightarrow\mathbb{N}$, that is non-
uniformly $\mathsf{C}$-injective and $\mathsf{C}$-consistent. Since, for every
$(v,G)\in\mathbf{VG}$, $\mathsf{A}(v,G)$ is finite, we can conclude that the
following holds: for every $(v,G)\in\mathbf{VG}$, the set
$\\{\mathit{pc}_{S}(v,G)\mid S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})\text{
and }(v,G)\in S\\}$ is finite. This allows us to apply Theorem 5.5 with
$A=\mathbf{VG}$ and $B=\mathbb{N}$. Therefore, there exists a function
$f:\mathbf{VG}\rightarrow\mathbb{N}$ such that, for every
$S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$, there exists
$S^{\prime}\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$ with $S\subsetneq
S^{\prime}$ and $f_{|S}={\mathit{pc}_{S^{\prime}}}_{|S}$. By exploiting the
latter property of the function $f$ guaranteed by Theorem 5.5, and the fact
that, for each $S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$,
$\mathit{pc}_{S}$ is a precoloring of $S$ that is non-uniformly
$\mathsf{C}$-injective and $\mathsf{C}$-consistent, we can show that (i) $f$
is a precoloring of $\mathbf{VG}$ that is (ii) non-uniformly
$\mathsf{C}$-injective, and (iii) $\mathsf{C}$-consistent, which in turn
implies item (3):

  * (i)

For every pair $(v,G)\in\mathbf{VG}$, we have that
$f(v,G)=\mathit{pc}_{S}(v,G)$ for some set
$S\in\mathcal{P}_{\mathsf{fin}}(\mathbf{VG})$ such that $\\{(v,G)\\}\subsetneq
S$. Since $\mathit{pc}_{S}$ is a precoloring of $S$, we get that
$f(v,G)=\mathit{pc}_{S}(v,G)\in\\{0,\ldots,|\mathsf{A}(v,G)|\\}$, and thus,
$f$ is a precoloring of $\mathbf{VG}$.

  * (ii)

For every two pairs $(v_{1},G)$ and $(v_{2},G)$ such that
$\mathsf{C}(v_{1},G)\neq\mathsf{C}(v_{2},G)$ we know there exists a finite set
$S$ such that $\\{(v_{1},G),(v_{2},G)\\}\subsetneq S$ with
$\mathit{pc}_{S}(v_{i},G)=f(v_{i},G)$ for $i\in\\{1,2\\}$. Therefore, since
$\mathsf{C}(v_{1},G)\neq\mathsf{C}(v_{2},G)$ and $\mathit{pc}_{S}$ is non-
uniformly $\mathsf{C}$-injective, we get that
$f(v_{1},G)=\mathit{pc}_{S}(v_{1},G)\neq\mathit{pc}_{S}(v_{2},G)=f(v_{2},G)$.
This implies that $f$ is non-uniformly $\mathsf{C}$-injective.

  * (ii)

Finally, by contradiction, assume there are four pairs
$(v_{1},G_{1}),(v_{2},G_{1}),(u_{1},G_{2})$ and $(u_{2},G_{2})$ in
$\mathbf{VG}$ such that $\mathsf{C}(v_{1},G_{1})<\mathsf{C}(v_{2},G_{1})$ and
$\mathsf{C}(u_{2},G_{2})<\mathsf{C}(u_{1},G_{2})$, but
$f(v_{1},G_{1})=f(u_{1},G_{2})$ and $f(v_{2},G_{1})=f(u_{2},G_{2})$. We know
that there exists a finite set $S^{\prime}$ such that
$S=\\{(v_{1},G_{1}),(v_{2},G_{1}),(u_{1},G_{2}),(u_{2},G_{2})\\}\subsetneq
S^{\prime}$ with $f(v,G)=\mathit{pc}_{S^{\prime}}(v,G)$ for every $(v,G)\in
S$. This implies that $\mathit{pc}_{S^{\prime}}$ is not
$\mathsf{C}$-consistent, which is clearly a contradiction.

This completes the proof of the second implication.

$\underline{(3\Rightarrow 1).}$ The goal is to devise a subgraph family
$\mathsf{F}$ and a filtering function $f$ such that $\text{\rm
Rank}(\mathsf{C})=\text{\rm Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$,
which in turn proves item $(1)$. By hypothesis, there exists a precoloring
$\mathit{pc}$ of $\mathbf{VG}$ that is non-uniformly $\mathsf{C}$-injective
and $\mathsf{C}$-consistent. We define $\mathsf{F}$ in such way that, for
every $(v,G)\in\mathbf{VG}$, $|\mathsf{F}(v,G)|=\mathit{pc}(v,G)$; note that
such a subgraph family exists since
$\mathit{pc}(v,G)\in\\{0,\ldots,|\mathsf{A}(v,G)|\\}$. We now proceed to
define the filtering function $f$. Let $R_{\mathit{pc}}$ be the binary
relation

$\left\\{(i,j)\in\mathbb{N}\times\mathbb{N}\mid\text{ there are
}(u,G),(v,G)\text{ in }\mathbf{VG}\text{ such that
}\mathsf{C}(u,G)<\mathsf{C}(v,G),\mathit{pc}(u,G)=i,\text{ and
}\mathit{pc}(v,G)=j\right\\}.$

The fact that $\mathit{pc}$ is non-uniformly $\mathsf{C}$-injective allows us
to conclude that $R_{\mathit{pc}}$ is irreflexive. Moreover, the
$\mathsf{C}$-consistency of $\mathit{pc}$ implies that $R_{\mathit{pc}}$ is
asymmetric. Observe now that if we extend $R_{\mathit{pc}}$ into a total order
$R_{\mathit{pc}}^{\star}$ over $\mathbb{N}$, and then show that
$R_{\mathit{pc}}^{\star}$ can be embedded into a carefully chosen countable
subset $N$ of $\mathbb{R}$, then we obtain the desired filtering function $f$,
which assigns real numbers to the sizes of the subgraph families assigned to
the pairs of $\mathbf{VG}$ by $\mathsf{F}$ as dictated by the embedding of
$R_{\mathit{pc}}^{\star}$ into $N\subsetneq\mathbb{R}$. We proceed to explain
how this is done.

The binary relation $R_{\mathit{pc}}$ is first extended into the strict
partial order $R_{\mathit{pc}}^{+}$ by simply taking its transitive closure.
Now, the fact that $R_{\mathit{pc}}^{+}$ can be extended into a total order
$R_{\mathit{pc}}^{\star}$ over $\mathbb{N}$ follows by the order-extension
principle (a.k.a. Szpilrajn Extension Theorem), shown by Szpilrajn in 1930
(Szpilrajn, 1930), which essentially states that every partial order can be
extended into a total order. It remains to show that $R_{\mathit{pc}}^{\star}$
can be embedded into some countable set $N\subsetneq\mathbb{R}$. This is done
via the back-and-forth method, a technique for showing isomorphism between
countably infinite structures satisfying certain conditions. We proceed by
considering four different cases:

Case 1.:

Assume first that there exists a minimum and maximum element in the ordered
set $(\mathbb{N},R_{\mathit{pc}}^{\star})$, denoted $n_{0}$ and $n_{1}$,
respectively. Consider a close range of the rational numbers
$[a,b]\subseteq\mathbb{Q}$ with $a<b$. Fix any order of the set
$\mathbb{N}-\\{n_{0},n_{1}\\}=\\{a_{1},a_{2},...\\}$, and fix a different
order of $[a,b]=\\{b_{1},b_{2},...\\}$. This is possible because both sets are
countable. We proceed to define the order preserving embedding of
$(\mathbb{N},R_{\mathit{pc}}^{\star})$ to $([a,b],<)$. First, define
$f(n_{0})=a$ and $f(n_{1})=b$. Now, the back and forth method goes as follow:

  1. (1):

Take $a_{i}$ such that $i$ is the first index where $f(a_{i})$ is not assign
yet. Define $f(a_{i})=b_{j}$ such that $b_{j}$ is the first element in the
list without pre image from $f$, and respects the order embedding up to this
point. In other words, for every $a_{k_{1}}$ and $a_{k_{2}}$ such that
$f(a_{k_{1}})$ and $f(a_{k_{2}})$ are defined and
$a_{k_{1}}R_{\mathit{pc}}^{\star}a_{i}R_{\mathit{pc}}^{\star}a_{k_{2}}$, it
holds that $f(a_{k_{1}})<b_{j}<f(a_{k_{2}})$.

  2. (2):

Repeat the previous step until we cover the whole set $\mathbb{N}$.

Given $a_{p}$ and $a_{q}$ such that
$a_{p}R_{\mathit{pc}}^{\star}a_{i}R_{\mathit{pc}}^{\star}a_{q}$ where
$f(a_{p})$ and $f(a_{q})$ are both assigned, since $([a,b],<)$ is a dense
order, for every two elements there is always another element in between.
Therefore, we can always find $b_{j}$ as stated in the previous steps. In
conclusion, we can map $(\mathbb{N},R_{\mathit{pc}}^{\star})$ to $([a,b],<)$
respecting both orders, and $f$ is precisely the filtering function that we
are looking for.

Cases 2, 3 and 4.:

In the remaining three cases, where $(\mathbb{N},R_{\mathit{pc}}^{\star})$ has
only a minimum element, only a maximum element, and no extreme elements,
respectively, the same argument as above applies using the sets
$\mathbb{Q}^{+}$, $\mathbb{Q}^{-}$ and $\mathbb{Q}$, respectively, instead of
$[a,b]\subseteq\mathbb{Q}$ .

It remains to show that $\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)=\text{\rm Rank}(\mathsf{C})$ for
the family $\mathsf{F}$ and filtering function $f$ defined above. Take any two
pairs $(v_{1},G)$ and $(v_{2},G)$ such that
$\mathsf{C}(v_{1},G)<\mathsf{C}(v_{2},G)$. By definition, we have that
$(\mathit{pc}(v_{1},G),\mathit{pc}(v_{2},G))\in R_{\mathit{pc}}^{\star}$. This
is equivalent to
$f(\mathit{pc}(v_{1},G))=f(|\mathsf{F}(v_{1},G)|)<f(\mathit{pc}(v_{2},G))=f(|\mathsf{F}(v_{2},G)|)$.
Therefore, $\mathsf{C}\langle\mathsf{F},f\rangle$ and $\mathsf{C}$ induce the
same ranking inside each graph, and the claim follows.

### Proof of Proposition 5.7

Let $pc$ be the non-uniform $\mathsf{C}$-injective precoloring of
$\mathsf{C}$, which exists by hypothesis. Consider a graph $G$, and an integer
$n>0$. Define the set

$S_{n}\ =\ \\{pc(v,G)\mid|\mathsf{A}(v,G)|\leq n\\}.$

In other words, $S_{n}$ collects all the colors assigned by $pc$ to vertices
with at most $n$ connected subgraphs around them. We then have that
$|\text{\rm Val}_{G}^{n}(\mathsf{C})|\leq|S_{n}|$ since $pc$ is non-uniformly
$\mathsf{C}$-injective. Since $pc$ is a precoloring,
$S_{n}\subseteq\\{0,\ldots,n\\}$, and thus, $|S_{n}|\leq n+1$, as needed.

### Proof of Proposition 5.9

We are going to devise a centrality measure that is not subgraph motif
relative to the induced ranking, but it enjoys the non-uniform bounded value
property. Consider the graphs

$G_{1}\ =\ (\\{v_{1},v_{2},v_{3}\\},\\{\\{v_{2},v_{3}\\}\\})\qquad G_{2}\ =\
(\\{u_{1},u_{2},u_{3}\\},\\{\\{u_{2},u_{3}\\}\\})\qquad G_{3}\ =\
(\\{w_{1},w_{2},w_{3}\\},\\{\\{w_{2},w_{3}\\}\\}).$

Observe that these three graphs have the same structure, that is, one isolated
node and two nodes connected by an edge. We now define the following
centrality measure:

$\mathsf{C}(v,G)=\begin{cases}1&(v,G)\in\\{(v_{1},G_{1}),(u_{2},G_{2}),(w_{3},G_{3})\\}\\\
2&(v,G)\in\\{(v_{2},G_{1}),(u_{3},G_{2}),(w_{1},G_{3})\\}\\\
3&(v,G)\in\\{(v_{3},G_{1}),(u_{1},G_{2}),(w_{2},G_{3})\\}\\\
1&\text{otherwise.}\end{cases}$

Roughly speaking, $\mathsf{C}$ is defined in such a way that the position of
the isolated vertex in the induced ranking is shifted. Indeed, in $\text{\rm
Rank}(\mathsf{C})$, $(v_{1},G_{1})$ comes first, $(w_{1},G_{3})$ comes second,
and $(u_{1},G_{2})$ comes third. It can be shown that $\mathsf{C}$ is not
subgraph motif relative to the induced ranking since any subgraph motif
measure will need too many values in $\text{\rm Val}^{n}(\mathsf{C})$, for
some $n\geq 1$, in order to mimic $\text{\rm Rank}(\mathsf{C})$. On the other
hand, for every $i\in\\{1,2,3\\}$, $|\text{\rm
Val}_{G_{i}}^{n}(\mathsf{C})|\leq n+1$, and thus, $\mathsf{C}$ enjoys the non-
uniform bounded value property, as needed.

### Proof of Proposition 5.10

We are going to show that there exists a graph $G$ such that $|\text{\rm
Val}_{G}^{5}(\mathsf{Closeness})|>6$. This implies that $\mathsf{Closeness}$
does not enjoy the non-uniform bounded value property, and thus, by item (2)
of Theorem 5.4, it is not a subgraph motif measure relative to the induced
ranking, as needed. Consider the graphs $L_{1},L_{2},\ldots,L_{5},S_{4}$. We
define the graph $G$ as the minimal graph with the following structural
property: for every graph $G^{\prime}\in\\{L_{1},L_{2},\ldots,L_{5},S_{4}\\}$,
there exists a component $G^{\prime\prime}\in\text{\rm Comp}(G)$ that is
isomorphic to $G^{\prime}$. By employing an argument similar to that in the
proof of Proposition 4.3, and exploiting the fact that $\mathsf{Closeness}$ is
closed under isomorphism (see Definition A.1) and local (see Definition A.2),
we can show that $|\text{\rm Val}_{G}^{5}(\mathsf{Closeness})|>6$.

### Proof of Theorem 5.11

We are going to define a subgraph family $\mathsf{F}$ and a filtering function
$f$ such that $\text{\rm Rank}(\mathsf{C})\cap\mathbf{VCG}^{2}=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)\cap\mathbf{VCG}^{2}$, which in
turn implies that $\mathsf{ConC}$ is a subgraph motif measure relative to the
induced ranking, as needed. Consider an arbitrary connected graph $G$. We
first observe that, for every $v\in V(G)$, it holds that
$|\mathsf{A}(v,G)|\geq|V(G)|$ since every path from $v$ to any other vertex in
$G$ is a connected subgraph containing $v$. We then define the equivalence
relation $\equiv_{G}$ over $V(G)$ as follows: $v\equiv_{G}u$ if
$\mathsf{C}(v,G)=\mathsf{C}(u,G)$. Let
$V(G)/_{\equiv_{G}}=\\{C_{1},\ldots,C_{m}\\}$ be the equivalence classes of
$\equiv_{G}$. We can assume, without loss of generality, that, for every
$i,j\in[m]$, with $C_{i}=[v]_{\equiv_{G}}$ and $C_{j}=[u]_{\equiv_{G}}$, $i<j$
implies $\mathsf{C}(v,G)<\mathsf{C}(u,G)$. We then define the subgraph family
$\mathsf{F}$ in such a way that, for every vertex $v\in V(G)$,
$|\mathsf{F}(v,G)|=i-1$ if $[v]_{\equiv_{G}}=C_{i}$.222Note that for pairs
$(u,H)$, where $H$ is a non-connected graph, we can simply define
$\mathsf{F}(u,H)$ as the empty set since it is irrelevant what $\mathsf{F}$
does over non-connected graphs. Note that such a subgraph family $\mathsf{F}$
always exists since, as discussed above, $|\mathsf{A}(v,G)|\geq|V(G)|$, but we
have that $|V(G)/_{\equiv_{G}}|\leq|V(G)|$. Finally, we define the filtering
function $f$ in such a way that, for every $i\in\\{0,\ldots,m-1\\}$,
$f(i)=i+1$. It is now not difficult to verify that indeed $\text{\rm
Rank}(\mathsf{C})\cap\mathbf{VCG}^{2}=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)\cap\mathbf{VCG}^{2}$, and the
claim follows.

##  Appendix E Proofs of Section 6

### Proof of Proposition 6.1

Let $\hat{G}$ be the graph
$(\\{v_{1},v_{2},v_{3}\\},\\{\\{v_{2},v_{3}\\}\\})$. Consider the centrality
measure $\mathsf{C}$ defined as follows:

$\mathsf{C}(v,G)\ =\ \begin{cases}1&G\neq\hat{G}\text{ or }(G=\hat{G}\text{
and }v=v_{3})\\\ 3&G=\hat{G}\text{ and }v=v_{1}\\\ 2&G=\hat{G}\text{ and
}v=v_{2}.\end{cases}$

We first show that $\mathsf{C}$ is a subgraph motif measure. Notice that, for
every vertex $v\in\mathbf{V}$,
$\mathsf{C}(v,G_{v})=\mathsf{C}(v_{3},\hat{G})=1$. Hence, we have only two
options concerning the set of connected subgraphs assigned to the vertices of
$\hat{G}$ by a subgraph family, and the filtering function, which are the
following: with $G_{uv}$ being the single-edge graph
$(\\{u,v\\},\\{\\{u,v\\}\\})$, either

$\mathsf{F}_{1}(v,\hat{G})\ =\ \begin{cases}\emptyset&v=v_{1}\\\
\\{G_{v_{2}},G_{v_{2}v_{3}}\\}&v=v_{2}\\\ \\{G_{v_{3}}\\}&v=v_{3}\end{cases}$

with $f_{1}(0)=3$, $f_{1}(1)=1$ and $f_{1}(2)=2$, or

$\mathsf{F}_{2}(v,\hat{G})\ =\ \begin{cases}\\{G_{v_{1}}\\}&v=v_{1}\\\
\\{G_{v_{2}},G_{v_{2}v_{3}}\\}&v=v_{2}\\\ \emptyset&v=v_{3}\end{cases}$

with $f_{2}(0)=1$, $f_{2}(1)=3$ and $f_{2}(2)=2$. Now, by extending
$\mathsf{F}_{1}$ and $\mathsf{F}_{2}$ in such a way that, for
$(v,G)\in\mathbf{VG}$ with $G\neq\hat{G}$, $\mathsf{F}_{1}(v,G)=\\{G_{v}\\}$
and $\mathsf{F}_{2}(v,G)=\emptyset$, it is clear that
$\mathsf{C}=\mathsf{C}\langle\mathsf{F}_{1},f_{1}\rangle=\mathsf{C}\langle\mathsf{F}_{2},f_{2}\rangle$.
Observe, however, that $\mathsf{C}\langle\mathsf{F}_{1},f_{1}\rangle$ and
$\mathsf{C}\langle\mathsf{F}_{2},f_{2}\rangle$ are not monotonic, and the
claim follows.

### Proof of Theorem 6.3

$\underline{(1\Rightarrow 2).}$ By contradiction, assume that $\mathsf{C}$
does not enjoy the monotonic bounded value property, namely there exists an
integer $n\geq 1$ such that $|\text{\rm Val}^{n}(\mathsf{C})|>n+1-|\text{\rm
BVal}^{n}(\mathsf{C})|$. By hypothesis, $\mathsf{C}$ is a monotonic subgraph
motif centrality measure, and thus, there exist a subgraph family $\mathsf{F}$
and a monotonic filtering function $f$ such that the following holds: for
every $(v,G)\in\mathbf{VG}$,
$\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$. By the pigeonhole
principle, and the fact that $\text{\rm Val}^{n}(\mathsf{C})\cap\text{\rm
BVal}^{n}(\mathsf{C})=\emptyset$, we can conclude that there is a value
$b\in(\text{\rm Val}^{n}(\mathsf{C})\cup\text{\rm BVal}^{n}(\mathsf{C}))$ such
that the following holds: there exists a pair $(v,G)\in\mathbf{VG}$ with
$\mathsf{C}(v,G)=b$ and $|\mathsf{F}(v,G)|>n$. Observe that $b\not\in\text{\rm
Val}^{n}(\mathsf{C})$ since this would imply that $|\mathsf{F}(v,G)|\leq n$,
which contradicts the fact that $|\mathsf{F}(v,G)|>n$; therefore,
$b\in\text{\rm BVal}^{n}(\mathsf{C})$. This means that $b<\max\text{\rm
Val}^{n}(\mathsf{C})$. Therefore, for some pair
$(v^{\prime},G^{\prime})\in\mathbf{VG}$, we have that
$f(|\mathsf{F}(v^{\prime},G^{\prime})|)=\max\text{\rm
Val}^{n}(\mathsf{C})>f(|\mathsf{F}(v,G)|)=b$, but
$|\mathsf{F}(v^{\prime},G^{\prime})|\leq|\mathsf{A}(v^{\prime},G^{\prime})|\leq
n<|\mathsf{F}(v,G)|$. This in turn implies that $f$ is not a monotonic
filtering function, which leads to a contradiction.

$\underline{(2\Rightarrow 1).}$ We show that there exist a subgraph family
$\mathsf{F}$ and a monotonic filtering function $f$ such that, for every
$(v,G)\in\mathbf{VG}$,
$\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$. We start by
defining a total order $\preceq_{\mathsf{C}}$ over the set of values
$\text{\rm Val}(\mathsf{C})=\bigcup_{i=1}^{\infty}\text{\rm
Val}^{i}(\mathsf{C})$. For some $n\geq 1$, let $D_{n}(\mathsf{C})=\text{\rm
Val}^{n}(\mathsf{C})\cup\text{\rm BVal}^{n}(\mathsf{C})$. By hypothesis,
$\mathsf{C}$ enjoys the monotonic bounded value property, and thus,

$|D_{n}(\mathsf{C})|\ =\ |\text{\rm Val}^{n}(\mathsf{C})|+|\text{\rm
BVal}^{n}(\mathsf{C})|-|\text{\rm Val}^{n}(\mathsf{C})\cap\text{\rm
BVal}^{n}(\mathsf{C})|\ =\ |\text{\rm Val}^{n}(\mathsf{C})|+|\text{\rm
BVal}^{n}(\mathsf{C})|\ \leq\ n+1.$

We proceed to show that, for every $a\in D_{n}(\mathsf{C})$ and $b\in
D_{n+1}(\mathsf{C})\setminus D_{n}(\mathsf{C})$, it holds that $a<b$. By
contradiction, assume that there are $a\in D_{n}(\mathsf{C})$ and $b\in
D_{n+1}(\mathsf{C})\setminus D_{n}(\mathsf{C})$ such that
$b<a\leq\max\text{\rm Val}^{n}(\mathsf{C})$. We proceed by considering two
cases:

  * •

The first case is when $b\in\text{\rm Val}^{n+1}(\mathsf{C})$. In this case,
by definition, $b\in\text{\rm BVal}^{n}(\mathsf{C})$. Therefore, $b\in
D_{n}(\mathsf{C})$, which contradicts the fact that $b\in
D_{n+1}(\mathsf{C})\setminus D_{n}(\mathsf{C})$.

  * •

The second case is when $b\in\text{\rm BVal}^{n+1}(\mathsf{C})$. In this case,
$b\in\text{\rm Val}(\mathsf{C})\setminus\text{\rm
Val}^{n+1}(C)\subseteq\text{\rm Val}(\mathsf{C})/\text{\rm
Val}^{n}(\mathsf{C})$ since $\text{\rm Val}^{n}(\mathsf{C})\subseteq\text{\rm
Val}^{n+1}(\mathsf{C})$. Since $b<\max\text{\rm Val}^{n}(\mathsf{C})$, by
definition, we have that $b\in\text{\rm BVal}^{n}(\mathsf{C})$. Therefore,
$b\in D_{n}(\mathsf{C})$, which contradicts the fact that $b\in
D_{n+1}(\mathsf{C})\setminus D_{n}(\mathsf{C})$.

We have just seen that for every $n\geq 1$, $D_{n}(\mathsf{C})$ is finite.
Moreover, every value of $D_{n+1}(\mathsf{C})\setminus D_{n}(\mathsf{C})$ is
strictly greater than every value of $D_{n}(\mathsf{C})$. With the above two
facts in place, we can easily define the desired total order
$\preceq_{\mathsf{C}}$ over $\text{\rm Val}(\mathsf{C})$: for each
$a,b\in\text{\rm Val}(\mathsf{C})$, $a\preceq_{\mathsf{C}}b$ if $a<b$. For
notational convenience, in the rest of the proof we assume that $\text{\rm
Val}(\mathsf{C})=\\{a_{1},a_{2},a_{3},\ldots\\}$ and
$a_{1}\preceq_{\mathsf{C}}a_{2}\preceq_{\mathsf{C}}a_{3}\preceq_{\mathsf{C}}\cdots$.

Having the total order $\preceq_{\mathsf{C}}$ over $\text{\rm
Val}(\mathsf{C})$ in place, we can now define the desired subgraph family
$\mathsf{F}$ and monotonic filtering function $f$. For an arbitrary pair
$(v,G)\in\mathbf{VG}$, we define $\mathsf{F}(v,G)$ in such a way that

$\mathsf{C}(v,G)=a_{i}\quad\text{implies}\quad|\mathsf{F}(v,G)|=i-1.$

We proceed to show that $\mathsf{F}$ always exists. By contradiction, assume
that there is $(v,G)\in\mathbf{VG}$ such that $|\mathsf{A}(v,G)|<i-1$ but
$\mathsf{C}(v,G)=a_{i}$; for brevity, let $n=|\mathsf{A}(v,G)|$. We define the
set $S_{i}=\\{a\in D_{n}(\mathsf{C})\mid a\leq a_{i}\\}$. Observe that

$n+1\ <\ i\ =\ |S_{i}|\ \leq\ |D_{n}(\mathsf{C})|\ =\ |\text{\rm
Val}^{n}(\mathsf{C})|+|\text{\rm BVal}^{n}(\mathsf{C})|,$

which contradicts the fact that $\mathsf{C}$ enjoys the monotonic bounded
value property We finally define the monotonic filtering function
$f:\mathbb{N}\to\text{\rm Val}(\mathsf{C})$ as follows: for each
$i\in\mathbb{N}$,

$f(i)\ =\ a_{i+1}.$

It is straightforward to see that, for every $(v,G)\in\mathbf{VG}$,
$\mathsf{C}(v,G)=\mathsf{C}\langle\mathsf{F},f\rangle(v,G)$. Thus,
$\mathsf{C}$ is a monotonic subgraph motif centrality measure, and Theorem 6.3
follows.

### Proof of Theorem 6.5

$\underline{(1\Rightarrow 2).}$ Consider a centrality measure $\mathsf{C}$
that is monotonic subgraph motif relative to the induced ranking. By
definition, there are a subgraph family $\mathsf{F}$ and a monotonic filtering
function $f$ such that $\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. Assume, by contradiction, that
$\mathsf{C}$ does not enjoy the non-uniform monotonic bounded value property,
i.e., there exist a graph $G$ and an integer $n\geq 1$ such that $|\text{\rm
Val}_{G}^{n}(\mathsf{C})|+|\text{\rm BVal}_{G}^{n}(\mathsf{C})|>n+1$. Since
$|\text{\rm Val}_{G}^{n}(\mathsf{C}\langle\mathsf{F},f\rangle)|=|\text{\rm
Val}_{G}^{n}(\mathsf{C})|$ and $|\text{\rm
BVal}_{G}^{n}(\mathsf{C}\langle\mathsf{F},f\rangle)|=|\text{\rm
BVal}_{G}^{n}(\mathsf{C})|$,

$|\text{\rm Val}_{G}^{n}(\mathsf{C}\langle\mathsf{F},f\rangle)|+|\text{\rm
BVal}_{G}^{n}(\mathsf{C}\langle\mathsf{F},f\rangle)|\ >\ n+1.$

This means that $\mathsf{C}\langle\mathsf{F},f\rangle$ does not enjoy the non-
uniform bounded value property. Hence, by Theorem 6.3, we get that
$\mathsf{C}\langle\mathsf{F},f\rangle$ is not a subgraph motif measure
relative to the induced ranking, which leads to contradiction. Consequently,
$\mathsf{C}$ enjoys the non-uniform bounded value property, as needed.

$\underline{(2\Rightarrow 1).}$ We need to show that there exist a subgraph
family $\mathsf{F}$ and a monotonic filtering function $f$ such that
$\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. For a graph $G$, we define the
equivalence relation $\equiv_{G}$ over $V(G)$, and we order the equivalence
classes of $V(G)/_{\equiv_{G}}$ as done in the proof of Theorem 5.11, namely
with $V(G)/_{\equiv_{G}}=\\{C_{1},\ldots,C_{m}\\}$, we assume that, for every
$i,j\in[m]$, with $C_{i}=[v]_{\equiv_{G}}$ and $C_{j}=[u]_{\equiv_{G}}$, $i<j$
implies $\mathsf{C}(v,G)<\mathsf{C}(u,G)$. We then define the subgraph family
$\mathsf{F}$ and the monotonic filtering function $f$ as in the proof of
Theorem 5.11: for every $v\in V(G)$, $|\mathsf{F}(v,G)|=i-1$ if
$[v]_{\equiv_{G}}=C_{i}$, and $f(i)=i+1$. It is not difficult to verify that
indeed $\text{\rm Rank}(\mathsf{C})=\text{\rm
Rank}(\mathsf{C}\langle\mathsf{F},f\rangle)$. It remains to show that the
subgraph family $\mathsf{F}$ always exists.333Note that here the argument for
this statement is slightly more complex than the one given in the proof of
Theorem 5.11 for a similar statement since we do not deal only with connected
graphs. Assume, by contradiction, that there is a vertex $v\in V(G)$ such that
$|\mathsf{A}(v,G)|=n<i-1$. We can show, by case analysis, that

$\\{\mathsf{C}(w,G)\mid\mathsf{C}(w,G)<\mathsf{C}(v,G)\\}\ \subseteq\
\text{\rm Val}_{G}^{n}(\mathsf{C})\cup\text{\rm BVal}_{G}^{n}(\mathsf{C}).$

Indeed, if $|\mathsf{A}(w,G)|\leq|\mathsf{A}(v,G)|=n$, then
$\mathsf{C}(w,G)\in\text{\rm Val}_{G}^{n}(\mathsf{C})$; otherwise, if
$|\mathsf{A}(w,G)|>|\mathsf{A}(v,G)|$, then, by definition,
$\mathsf{C}(w,G)\in\text{\rm BVal}_{G}^{n}(\mathsf{C})$. Therefore, we can
conclude that

$n+1\ <\ i\ =|\\{C_{1},\ldots,C_{i}\\}|\ =\
|\\{\mathsf{C}(w,G)\mid\mathsf{C}(w,G)\ <\ \mathsf{C}(v,G)\\}|\ \leq\
|\text{\rm Val}_{G}^{n}(\mathsf{C})\cup\text{\rm BVal}_{G}^{n}(\mathsf{C})|\
=\ |\text{\rm Val}_{G}^{n}(\mathsf{C})|+|\text{\rm
BVal}_{G}^{n}(\mathsf{C})|,$

which contradicts the fact the $\mathsf{C}$ enjoys the non-uniform monotonic
bounded value property, and the claim follows.

### Proof of Theorem 6.6

It is enough to observe that the filtering function $f$ employed in the proof
of Theorem 5.11 is monotonic.

##  Appendix F Proofs of Section 7

In this final section of the appendix, we provide formal proofs for the
expressibiliy/inexpressibility results presented in Section 7 (see Tables 1
and 2). The fact that $\mathsf{Stress}$ and $\mathsf{All\text{\rm-}Subgraphs}$
are (monotonic) subgraph motif (and thus, (monotonic) subgraph motif relative
to the induced ranking) has been already observed in the main body of the
paper. Indeed, we have seen that

$\mathsf{Stress}\ =\ \mathsf{C}\langle\mathsf{S},f_{\times
2}\rangle\qquad\text{and}\qquad\mathsf{All\text{\rm-}Subgraphs}=\mathsf{C}\langle\mathsf{A},\log_{2}\rangle,$

where both $f_{\times 2}$ and $\log_{2}$ are monotonic filtering functions.

Concerning $\mathsf{Closeness}$, we have already shown that it is not a
subgraph motif measure (see Proposition 4.3), and thus, it is not a monotonic
subgraph motif measure. A simple inspection of the proof of Proposition 4.3,
reveals that actually $\mathsf{Closeness}$ is not a subgraph motif measure
(and thus, not a monotonic subgraph motif measure) even if we concentrate on
trees, as claimed in Tables 1 and 2. The fact that $\mathsf{Closeness}$ is not
a subgraph motif measure (and thus, not a monotonic subgraph motif measure)
relative to the induced ranking has been established by Proposition 5.10.

Finally, the fact that every centrality measure considered in the
classification of Section 7 is (monotonic) subgraph motif relative to the
induced ranking if we concentrate on connected graphs, is a consequence of
Theorems 5.11 and 6.6. We proceed to establish the claims stated in Tables 1
and 2, but are not covered by the above discussion.

### Degree

The degree centrality measure is one of the simplest measures that can be
found in the literature. It states that the bigger the neighborhood of a
vertex, the most central it is. Formally, given a graph $G$ and $v\in V(G)$,
the degree centrality of $v$ in $G$ is

$\mathsf{Degree}(v,G)\ =\ |N_{G}(v)|.$

We proceed to show the following result:

###### Proposition F.1.

$\mathsf{Degree}$ is a monotonic subgraph motif measure.

###### Proof.

For the degree centrality, the important subgraphs for a vertex $v$ in a graph
$G$ are simply the edges of the form $\\{u,v\\}$. Formally, we define the
subgraph family $\mathsf{F}_{\mathsf{Degree}}$ in such a way that, for every
$(v,G)\in\mathbf{VG}$,

$\mathsf{F}_{\mathsf{Degree}}(v,G)\ =\
\\{(\\{u,v\\},\\{\\{u,v\\}\\})\mid\\{u,v\\}\in E(G)\\}.$

We also consider the filtering function $\mathit{id}$ that is the identity
over $\mathbb{N}$, i.e., $\mathit{id}(x)=x$, which is monotonic. Clearly,

$\mathsf{Degree}(v,G)\ =\ \mathit{id}(|\mathsf{F}_{\mathsf{Degree}}(v,G)|)$

which in turn implies that

$\mathsf{Degree}\ =\
\mathsf{C}\langle\mathsf{F}_{\mathsf{Degree}},\mathit{id}\rangle$

and the claim follows.

### Cross-Clique

The cross-clique centrality measure (Everett and Borgatti, 1998), was
introduced in the context of analyzing virus and information propagation. It
is defined as the amount of cliques containing a certain vertex. Given a graph
$G$ and a vertex $\in V(G)$, we define the set
$\mathit{Cl}(v,G)=\\{S\in\mathsf{A}(v,G)\mid S\text{ is a clique}\\}$. The
cross-clique centrality of $v$ in $G$ is

$\mathsf{Cross\text{\rm-}Clique}(v,G)\ =\ |\mathit{Cl}(v,G)|.$

It is straightforward to see that the following holds:

###### Proposition F.2.

$\mathsf{Cross\text{\rm-}Clique}$ is a monotonic subgraph motif measure.

### Harmonic

This centrality measure is commonly considered as an extension of
$\mathsf{Closeness}$ to disconnected graphs. Given a graph $G$ and a vertex
$v\in V(G)$, the harmonic centrality (Rochat, 2009) of $v$ in $G$ is defines
as

$\mathsf{Harmonic}(v,G)\ =\ \begin{cases}0&v\text{ is isolated in }G\\\ &\\\
\displaystyle\sum_{u\in
V(G)\setminus\\{v\\}}\frac{1}{d_{G}(v,u)}&\text{otherwise}.\end{cases}$

Recall that, for two nodes $v,u\in V(G)$, if there is no path between them,
then $d_{G}(v,u)=\infty$. Therefore, a vertex $u\in V(G)$ that is not
connected with $v$ in $G$ via a path, has no impact on the harmonic centrality
of $v$ in $G$. Just as $\mathsf{Closeness}$, $\mathsf{Harmonic}$ is usually
called a geometrical measure since it relies on the distance inside a graph.
We proceed to show the following:

###### Proposition F.3.

The following hold:

  1. (1)

$\mathsf{Harmonic}$ is not a subgraph motif measure, even if we focus on
trees.

  2. (2)

$\mathsf{Harmonic}$ is not a subgraph motif measure relative to the induced
ranking.

###### Proof.

Item (1). We follow the same strategy as in the proof of Proposition 4.3. We
first observe that
$\mathsf{Harmonic}(1,L_{i})=\sum_{j=1}^{i-1}\displaystyle\frac{1}{j}$.
Therefore, for $n>1$, we have that
$\mathsf{Harmonic}(1,L_{n+1})=\mathsf{Harmonic}(1,L_{n})+\displaystyle\frac{1}{n}$.
This means $\mathsf{Harmonic}(1,L_{i})\not=\mathsf{Harmonic}(1,L_{j})$ for
every $i,j$ with $i\neq j$. Hence, $|\text{\rm
Val}^{n}(\mathsf{Harmonic})|\geq n-1$. Since $\mathsf{Harmonic}(1,L_{1})=0$,
we get that $|\text{\rm Val}^{n}(\mathsf{Harmonic})|\geq n$. Now, let $n=5$.
There are two pairs left: $(2,L_{3})$ and $(1,S_{3})$. We first observe that,
for every $n>0$,

$\mathsf{Harmonic}(2,L_{3})\ =\ 2\ >\
\sum_{i=1}^{n-1}\displaystyle\frac{1}{i}\ =\ \mathsf{Harmonic}(1,L_{n}).$

Moreover, we have that

$\mathsf{Harmonic}(1,S_{3})\ =\ 1+\frac{1}{2}+\frac{1}{2}\ =\ 2.$

Therefore, $|\text{\rm Val}^{5}(\mathsf{Harmonic})|=6$, which means
$\mathsf{Harmonic}$ does not violate the bounded value property for $n=5$.
However, for $n=6$ we get that $|\text{\rm Val}^{6}(\mathsf{Harmonic})|\geq 7$
since, by definition, $\text{\rm Val}^{5}(\mathsf{Harmonic})\subseteq\text{\rm
Val}^{6}(\mathsf{Harmonic})$. Now, for the pair $(2,L_{4})$ we have
$|\mathsf{A}(2,L_{4})|=6$, whereas $\mathsf{Harmonic}(2,L_{4})=2.5$.
Therefore, $|\text{\rm Val}^{6}(\mathsf{Harmonic})|>7$. Hence,
$\mathsf{Harmonic}$ violates the bounded value property. Thus, by Theorem 4.2,
we conclude that $\mathsf{Harmonic}$ is not a subgraph motif measure. This
hold even if we concentrate on trees since the line and star graphs used above
are trees.

Item (2). By Theorem 5.4, it suffices to show that $\mathsf{Harmonic}$ does
not enjoy the non-uniform bounded value property. To this end, we follow the
same idea as in the proof of Proposition 5.10 to, roughly speaking, gather all
the graphs employed above to prove that $|\text{\rm
Val}^{6}(\mathsf{Harmonic})|>7$ in one disconnected graph $G$. Then, by
exploiting the fact that $\mathsf{Harmonic}$ is closed under isomorphism (see
Definition A.1) and local (see Definition A.2), we can show that $|\text{\rm
Val}_{G}^{6}(\mathsf{Harmonic})|>7$.

### PageRank

This measure, introduced in (Page et al., 1999), is used in Google’s web
searching engine. Given a graph $G$ with $V(G)=\\{v_{1},\ldots,v_{|V(G)|}\\}$,
we define the adjacency matrix of $G$ as the matrix $A_{G}$ such that
${A_{G}}_{ij}=1$ if $\\{v_{i},v_{j}\\}\in E(G)$. We then define P as the
column-stochastic matrix such that:

$\textbf{P}_{ij}\ =\ \displaystyle\frac{{A_{G}}_{ij}}{|N_{G}(i)|}.$

In other words, P contains the probabilities of jumping from node $i$ to node
$j$ during a random walk over $G$. Let $\mathbf{v}$ be a stochastic vector
$(\mathbf{1}^{T}\mathbf{v}=1)$, and let $0<\alpha<1$ be a teleportation
parameter. Then, the ($\mathbf{v},\alpha$)-PageRank vector is defined as the
vector $x_{\mathbf{v},\alpha}$ that solves the equation
$(I-\alpha\textbf{P})x=(1-\alpha)\mathbf{v}$. Now, given a graph $G$ with
$V(G)=\\{v_{1},\ldots,v_{|V(G)|}\\}$, the PageRank centrality of $v_{i}$ in
$G$ is defined as

$\mathsf{PageRank}(v_{i},G)=x_{0.8,\mathbf{u}}[i],$

where $\mathbf{u}=\mathbf{1}\cdot\frac{1}{|V(G)|}$. Several variations of
$\mathsf{PageRank}$ have been proposed in the literature. In particular, if we
do not force $x_{0.8,\mathbf{u}}$ to be a probability distribution, we can ask
that the sum of centrality values inside a connected component is equal to the
number of nodes in that component. Therefore, this give rise to the local
version of $\mathsf{PageRank}$, denoted $\mathsf{LPR}$. We call it local since
the values in a connected component are always the same regardless of the
graph.

###### Proposition F.4.

The following hold:

  1. (1)

$\mathsf{PageRank}$ is not a subgraph motif measure, even if we focus on
trees.

  2. (2)

$\mathsf{PageRank}$ is not a subgraph motif measure relative to the induced
ranking.

###### Proof.

For both items, it suffices to consider the local version of
$\mathsf{PageRank}$ since $\text{\rm Rank}(\mathsf{PageRank})=\text{\rm
Rank}({\mathsf{LPR}})$.

Item (1). It can verified that $\text{\rm
Val}_{L_{2}}^{6}(\mathsf{LPR})=\\{1\\}$, $\text{\rm
Val}_{L_{3}}^{6}(\mathsf{LPR})=\\{0.5,0.33\\}$, $\text{\rm
Val}_{L_{4}}^{6}(\mathsf{LPR})=\\{0.17,0.25\\}$, $\text{\rm
Val}_{L_{5}}^{6}(\mathsf{LPR})=\\{0.1\\}$, $\text{\rm
Val}_{L_{6}}^{6}(\mathsf{LPR})=\\{0.07\\}$, and $\text{\rm
Val}_{S_{3}}^{6}(\mathsf{LPR})=\\{0.2\\}$. Therefore,

$\\{1,0.5,0.33,0.17,0.25,0.1,0.07,0.2\\}\ \subseteq\ \text{\rm
Val}^{6}(\mathsf{LPR}).$

Thus, $|\text{\rm Val}^{6}(\mathsf{LPR})|>7$, which implies that
$\mathsf{LPR}$ does not enjoy the bounded value property. Hence, by Theorem
4.2, we conclude that $\mathsf{LPR}$ is not a subgraph motif measure. This
holds even if we focus on trees since the line graphs considered above are
trees.

Item (2). By Theorem 5.4, it suffices to show that $\mathsf{LPR}$ does not
enjoy the non-uniform bounded value property. To this end, we follow the same
idea as in the proof of Proposition 5.10 to, roughly speaking, gather all the
graphs employed above to prove that $|\text{\rm Val}^{6}(\mathsf{LPR})|>7$ in
one disconnected graph $G$. Then, by exploiting the fact that $\mathsf{LPR}$
is closed under isomorphism (see Definition A.1) and local (see Definition
A.2), we can show that $|\text{\rm Val}_{G}^{6}(\mathsf{LPR})|>7$, and the
claim follows.

### Eigenvector

Given a graph $G$ with $V(G)=\\{u_{1},...,u_{|V(G)|}\\}$, we define the
adjacency matrix of $G$ as the matrix $A_{G}$ such that ${A_{G}}_{ij}=1$ if
$\\{u_{i},u_{j}\\}\in E(G)$. Let $\lambda_{\max}(G)$ be the greatest
eigenvalue of $A_{G}$. We define the unique $L^{2}$ normalized eigenvector
associated with $\lambda_{\max}(G)$ as $\mathbf{v}_{\max}$. The eigenvector
centrality (Bonacich, 1987) of $u_{i}$ in $G$ is the $i$-th entrance of
$\mathbf{v}_{\max}$:

$\mathsf{Eigenvector}(u_{i},G)\ =\mathbf{v}_{\max}^{i}.$

We proceed to show the following:

###### Proposition F.5.

$\mathsf{Eigenvector}$ is not a subgraph motif measure, even if we focus on
trees.

###### Proof.

The power method is the usual way to compute $\mathsf{Eigenvector}$ (Hagberg
et al., 2008). With an initial vector $\mathbf{v}=\mathbf{1}$, a tolerance
factor $\epsilon=1.0e-6$, and precision of three decimals, we get the
following values:

$\text{\rm
Val}_{L_{3}}^{7}(\mathsf{Eigenvector})=\\{0.5,0.707\\}\qquad\text{\rm
Val}_{L_{4}}^{7}(\mathsf{Eigenvector})=\\{0.371,0.601\\}\qquad\text{\rm
Val}_{L_{5}}^{7}(\mathsf{Eigenvector})=\\{0.288\\}$ $\text{\rm
Val}_{L_{6}}^{7}(\mathsf{Eigenvector})=\\{0.231\\}\qquad\text{\rm
Val}_{L_{7}}^{7}(\mathsf{Eigenvector})=\\{0.191\\}\qquad\text{\rm
Val}_{S_{3}}^{7}(\mathsf{Eigenvector})=\\{0.408\\}$

and, for $T=(\\{1,2,3,4,5\\},\\{\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{2,5\\}\\})$,

$\text{\rm Val}_{T}^{7}(\mathsf{Eigenvector})=\\{0.353\\}.$

Therefore, $\mathsf{Eigenvector}$ does not enjoy the bounded value property,
and thus, by Theorem 4.2, it is not a subgraph motif measure. This holds even
for trees since all the graphs used above are indeed trees.

By Theorem 6.6, $\mathsf{Eigenvector}$ is a subgraph motif measure relative to
the induced ranking over connected graphs. We proceed to strengthen this
result by showing that it holds over a broader class of graphs than the class
of connected graphs. Let

$\mathbf{K}_{1}\ =\ \\{G\in\mathbf{G}\mid\text{for every
}G_{1},G_{2}\in\text{\rm
Comp}(G),\lambda_{\max}(G[V(G_{1})])=\lambda_{\max}(G[V(G_{2})])=\lambda_{\max}(G)\text{
implies }G_{1}\cong G_{2}\\}.$

It is easy to verify that every connected graph belongs to $\mathbf{K}_{1}$,
and that $\mathbf{K}_{1}$ may contain disconnected graphs. We show that:

###### Proposition F.6.

$\mathsf{Eigenvector}$ is a subgraph motif measure relative to the induced
ranking when restricted to $\mathbf{K_{1}}$.

###### Proof.

From the proof of Proposition F.5, we know that for every component of
$M(G)=\\{S\in\text{\rm
Comp}(G)\mid\lambda_{\max}(G[V(S)])=\lambda_{\max}(G)\\}$, the eigenvector
centrality assigns the same amount of values to the connected component as it
seen as a connected graph. On the other hand, if $S\not\in M(G)$, then, for
every vertex $v\in V(S)$, we have that $\mathsf{Eigenvector}(v,G)=0$. Note
that, whenever two graphs are isomorphic they have the same values in every
eigenvector. Values are just permuted depending on the isomorphism you map
each graph to the other. Therefore, we have that, for every graph
$G\in\mathbf{K}_{1}$, there exists $S\in M(G)$ such that $\text{\rm
Val}_{G}^{n}(\mathsf{Eigenvector})=\text{\rm
Val}_{G[V(S)]}^{n}(\mathsf{Eigenvector})$. In other words, when
$\mathsf{Eigenvector}$ is restricted to $\mathbf{K}_{1}$ it behaves like
$\mathsf{Con}\mathsf{Eigenvector}$. Hence, we can use the same subgraph family
and filter function employed in the proof of Proposition 5.11 with the
addition of value $0$ for vertices outside $S$ in $M(G)$.

### Betweenness

This centrality measure is similar to $\mathsf{Stress}$ with the difference
that we take the proportion of shortest paths going through a certain vertex.
Formally, given a graph $G$ and a vertex $v\in V(G)$, the betweenness
centrality (Freeman, 1977) of $v$ in $G$ is

$\mathsf{Betweenness}(v,G)\ =\
\sum_{(u,w)\in(K_{v}(G)\setminus\\{v\\})^{2}}\displaystyle\frac{|S_{G}^{v}(u,w)|}{|S_{G}(u,w)|}.$

We proceed to show the following result:

###### Proposition F.7.

$\mathsf{Betweenness}$ is a subgraph motif measure when restricted to trees.

###### Proof.

We need to show that there exist a subgraph family $\mathsf{F}$ and a
filtering function $f$ such that
$\mathsf{Betweenness}=\mathsf{C}\langle\mathsf{F},f\rangle$. Since we focus on
trees, there is natural subgraph family that does the job. For every tree $T$
and $v\in V(T)$, we define $\mathsf{F}$ as follows:

$\mathsf{F}(v,T)\ =\ \\{\pi_{uw}\in\mathsf{A}(v,T)\mid u,w\in
V(T)\setminus\\{v\\}\text{ and }\pi_{uw}\in S_{T}(u,w)\\}.$

For the filtering function we simply use the function $f_{\times 2}$, i.e.,
$f_{\times 2}(x)=2x$. It remains to show that, for every $v\in V(T)$,
$\mathsf{Betweenness}(v,T)=f_{\times 2}(|\mathsf{F}(v,T)|)$. In trees we know
that, for every pair of vertices $u,v$, it holds that $|S_{G}(u,v)|=1$.
Therefore, for any $v\in V(T)$, we have that
$\mathsf{Betweenness}(v,T)=\mathsf{Stress}(v,T)=f_{\times
2}(|\mathsf{F}(v,T)|)$, and the claim follows.

One can define a broader class of graphs than the class of trees over which
$\mathsf{Betweenness}$ still a subgraph motif measure. Let

$\mathbf{C}_{1}=\\{G\in\mathbf{G}\mid\text{for every }v,u\in
V(G),|S_{G}(v,u)|\leq 1\\},$

i.e., it collects all the graphs such that, for every two nodes $v,u$ in $G$,
there exists exactly one shortest path from $v$ to $u$, a property that trees
trivially satisfy. It is then not difficult to show the following result by
exploiting the subgraph family and the filtering function used in the proof of
Proposition F.7:

###### Proposition F.8.

$\mathsf{Betweenness}$ is a subgraph motif measure when restricted to
$\mathbf{C}_{1}$.

It turned out that the question whether $\mathsf{Betweenness}$ is a subgraph
motif in general is a non-trivial one that remains open. We conclude this
section by dealing with rankings. We proceed to show the following
inexpressibility result:

###### Proposition F.9.

The following hold:

  1. (1)

$\mathsf{Betweenness}$ is not a monotonic subgraph motif measure, even if we
focus on connected graphs.

  2. (2)

$\mathsf{Betweenness}$ is not a monotonic subgraph motif measure relative to
the induced ranking.

###### Proof.

Item (1). We are going to show that $\mathsf{Betweenness}$ does not enjoy the
monotonic bounded value property, and thus, by Theorem 6.3, it is not a
monotonic subgraph motif measure. For $n\geq 1$, consider the connected graph
$H_{n}=(V_{n},E_{n})$, where

$V_{n}\ =\ \\{1,2,...,n+2\\}\qquad\text{and}\qquad E_{n}=\\{\\{1,i\\}\mid
i\in\\{3,4,\ldots,n+2\\}\\}\cup\\{\\{2,i\\}\mid i\in\\{3,4,.\ldots,n+2\\}\\}.$

It can be verified that $\mathsf{Betweenness}(3,H_{n})=\frac{2}{n}$. However,
for $n>1$, $|\mathsf{A}(3,H_{n})|>4$. Therefore, we have that

$|\text{\rm Val}^{4}(\mathsf{Betweenness})|+|\text{\rm
BVal}^{4}(\mathsf{Betweenness})|\ >\ 5,$

which implies that $\mathsf{Betweenness}$ does not enjoy the monotonic bounded
value property, as needed.

Item(2). By Theorem 5.4, it suffices to show that $\mathsf{Betweenness}$ does
not enjoy the non-uniform bounded value property. Since $\mathsf{Betweenness}$
is closed under isomorphism and local, we will use the same strategy as we did
in analogous proofs. In particular, we define the graph $G$ as the minimal
graph with the following property: for every graph
$G^{\prime}\in\\{H_{1},H_{2},\ldots,H_{5},H_{6}\\}$, there exists a component
$G^{\prime\prime}\in\text{\rm Comp}(G)$ such that $G^{\prime\prime}$ is
isomorphic to $G^{\prime}$. We can then show that

$|\text{\rm Val}_{G}^{4}(\mathsf{Betweenness})|+|\text{\rm
BVal}_{G}^{4}(\mathsf{Betweenness})|\ >\ 5,$

which implies that $\mathsf{Betweenness}$ does not enjoy the non-uniform
monotonic bounded value property, and the claim follows.

##  Appendix G Directed Graphs

### Preliminaries

A directed graph (or digraph for short) $G$ is a pair $(V,E)$, where $V$ is a
finite non-empty subset of $\mathbf{V}$ (the set of vertices of $G$), and
$E\subseteq\\{(u,v)\mid u,v\in V\\}$ (the set of edges of $G$). As for
undirected graphs, we write $V(G)$ and $E(G)$ for the set of vertices and
edges of $G$, respectively. A multi-graph $M$ is defined in the same way as
undirected graphs, with the key difference that the edges from a multiset (or
a bag), i.e., we can have more than one undirected edges between two vertices.
The notations $V(M)$ and $E(M)$ can ba naturally defined for multi-graphs.
Given a directed graph $G$, the undirected version of it, denoted
$\text{UN}(G)$, is defined as the multi-graph $(V(G),[\\{u,v\\}\mid(u,v)\in
E(G)\text{ or }(v,u)\in E(G)])$. Note that we use the notation $[\cdot]$ to
denote bags. For example, $[a,a,b]$ is the bag consisting of two occurrences
of $a$ and one occurrence of $b$. We say that a directed graph $G$ is
connected if the multi-graph $\text{UN}(G)$ is connected. This notion of
connectedness is known in the literature as weak connectedness. In simple
words, $G$ is connected if the multi-graph obtained after removing the
directions of the edges is connected. For a vertex $v$ in a directed graph
$G$, we define the children of $v$ in $G$ as the set $\text{OUT}(v,G)=\\{u\in
V(G)\mid(v,u)\in E(G)\\}$ and the parents of $v$ in $G$ as the set
$\text{IN}(v,G)=\\{u\in V(G)\mid(u,v)\in E(G)\\}$. A connected subgraph of $G$
is any graph $G^{\prime}$ such that $V(G^{\prime})\subseteq V(G)$ and
$E(G^{\prime})\subseteq E(G)\cap(V(G^{\prime})\times V(G^{\prime}))$, and we
write $G^{\prime}\subseteq G$ to indicate that $G^{\prime}$ is a subgraph of
$G$. Given a vertex $v\in V(G)$, we define the set of all connected subgraphs
containing $v$ in $G$ as $\mathsf{A}(v,G)=\\{G^{\prime}\subseteq G\mid v\in
V(G^{\prime})\text{ and }G^{\prime}\text{ is connected}\\}$. Given two
vertices $u,v$ in $V(G)$, a path connecting $u$ and $v$ is a sequence of
vertices $\pi_{uv}=w_{1}w_{2}...w_{n}$ such that $w_{1}=u$, $w_{n}=v$ and, for
every $i\in\\{1,..,n-1\\}$, $(w_{i},w_{i+1})\in E(G)$. The size of $\pi_{uv}$
is defined as $|\pi_{uv}|=n-1$. By convention, $\pi_{uu}=u$ and
$|\pi_{uu}|=0$. A connected component (or simply component) of $G$ is an
induced subgraph $G[S]$ of $G$, where $S\subseteq V(G)$, such that $G[S]$ is
connected, and, for every $v\in V(G)\setminus S$, there is no path in $G$ from
$v$ to a vertex of $S$ neither a path from any vertex in $S$ to $v$. We denote
by $\text{\rm Comp}(G)$ all the components of $G$, that is, the set of graphs
$\\{G^{\prime}\mid G^{\prime}\text{ is a component of }G\\}$. We define the
reachable component of a node $v$ in $G$ as the set $K_{v}(G)\subseteq V(G)$
such that $K_{v}(G)=\\{u\in V(G)\mid\text{there exists a path from $v$ to $u$
in }G\\}$. We denote by $\mathbf{G}$ the set of all digraphs, and by
$\mathbf{VG}$ the set of vertex-digraph pairs
$\\{(v,G)\in\mathbf{V}\times\mathbf{G}\mid v\in V(G)\\}$. Note that we
overload the notation and we use $\mathbf{G}$ and $\mathbf{VG}$, as for
undirected graphs, to refer to the set of all digraphs and the set of vertex-
digraph pairs, respectively. This will not cause any confusion as the rest of
the appendix is only about digraphs. A centrality measure for digraphs is a
function $\mathsf{C}:\mathbf{VG}\to\mathbb{R}$. In the rest of the appendix,
we may say graph meaning digraph, and we only refer to centrality measures for
digraphs.

### Special Graphs

The line graph with $m>0$ vertices, denoted $L_{m}$, is the digraph $(V,E)$,
where

$V\ =\ \\{1,\ldots,m\\}\quad\text{and}\quad
E=\bigcup_{i\in\\{1,\ldots,m-1\\}}\\{(i,i+1)\\}.$

The star graph with $m>0$ vertices, denoted $S_{m}$, is the digraph $(V,E)$,
where

$V\ =\ \\{1,\ldots,m\\}\quad\text{and}\quad E\ =\
\bigcup_{i\in\\{2,\ldots,m\\}}\\{(i,1)\\}.$

We refer to the vertex $1$ as the center of $S_{m}$.

### Closure Under Isomorphism

We say that two digraphs $G_{1}$ and $G_{2}$ are isomorphic, denoted
$G_{1}\simeq G_{2}$, if there exists a bijective function $h:V(G_{1})\to
V(G_{2})$ such that $(v,u)\in E(G_{1})$ iff $(h(v),h(u))\in E(G_{2})$.
Furthermore, given the vertices $v_{1}\in V(G_{1})$ and $v_{2}\in V(G_{2})$,
we say that the pairs $(v_{1},G_{1})$ and $(v_{2},G_{2})$ are isomorphic,
denoted $(v_{1},G_{1})\simeq(v_{2},G_{2})$, if $G_{1}\simeq G_{2}$ witnessed
by $h$, and $h(v_{1})=v_{2}$. We are now ready to define the property of being
closed under isomorphism for centrality measures.

###### Definition G.1.

Consider a centrality measure $\mathsf{C}$. We say that $\mathsf{C}$ is closed
under isomorphism if, for every two pairs $(v_{1},G_{1})\in\mathbf{VG}$ and
$(v_{2},G_{2})\in\mathbf{VG}$, $(v_{1},G_{1})\simeq(v_{2},G_{2})$ implies
$\mathsf{C}(v_{1},G_{1})=\mathsf{C}(v_{2},G_{2})$.

In simple words, the above property states that the values assigned by a
measure to the vertices of a graph do not depend on the names of the vertices,
but only on the structure of the graph; hence, the above property is sometimes
called anonymity.

### Locality

We finally recall the so-called locality property. Recall that, given a graph
$G$ and a set of vertices $S\subseteq V(G)$, we write $G[S]$ for the subgraph
of $G$ induced by $S$. The definition of locality follows:

###### Definition G.2.

A centrality measure $\mathsf{C}$ is local if, for every pair
$(v,G)\in\mathbf{VG}$, $\mathsf{C}(v,G)=\mathsf{C}(v,G[K_{v}(G)])$.

In simple words, the above property tells us that the value assigned by a
measure $\mathsf{C}$ to a vertex $v$ in a graph $G$ depends only on the
component $G^{\prime}\in\text{\rm Comp}(G)$ that contains $v$, i.e., during
the calculation of $\mathsf{C}(v,G)$, $\mathsf{C}$ considers only the
component $G^{\prime}$.

### Subgraph Motif Measures for Directed Graphs

We proceed to introduce the family of subgraph motif measures for directed
graphs. This is actually done in the exactly the same way as for undirected
graphs. Nevertheless, for the sake of completeness and clarity, we give here
all the definitions. A subgraph family as a function
$\mathsf{F}:\mathbf{VG}\to\mathcal{P}(\mathbf{G})$ such that for every pair
$(v,G)\in\mathbf{VG}$, $\mathsf{F}(v,G)\subseteq\mathsf{A}(v,G)$. A filtering
function is a function $f:\mathbb{N}\to\mathbb{R}$.

###### Definition G.3 (Subgraph Motif Measure (for Directed Graphs)).

Consider a subgraph family $\mathsf{F}$ and a filtering function $f$. The
$\langle\mathsf{F},f\rangle$-measure is the function
$\mathsf{C}\langle\mathsf{F},f\rangle:\mathbf{VG}\ \rightarrow\ \mathbb{R}$
such that, for $(v,G)\in\mathbf{VG}$,
$\mathsf{C}\langle\mathsf{F},f\rangle(v,G)=f(|\mathsf{F}(v,G)|)$. A centrality
measure $\mathsf{C}$ is a subgraph motif centrality measure if there are a
subgraph family $\mathsf{F}$ and a filtering function $f$ such that
$\mathsf{C}$ is the $\langle\mathsf{F},f\rangle$-measure, namely
$\mathsf{C}=\mathsf{C}\langle\mathsf{F},f\rangle$.

We can define the sets $\text{\rm Val}_{G}^{n}(\mathsf{C})$ and $\text{\rm
Val}^{n}(\mathsf{C})$ in exactly the same way as for undirected graphs. The
key difference is that now we might have more values for a fixed integer $n$.
In other words, in general, there are more pairs $(v,G)$ such that
$|\mathsf{A}(v,G)|\leq n$ when $G$ is a directed graph rather than being
undirected. Analogously, we can define the notion of $\mathsf{C}$-colorability
for a measure $\mathsf{C}$ over directed graphs. We are now ready to state our
main characterizations for the case of directed graphs, which are similar to
the ones for undirected graphs.

###### Theorem G.4.

Consider a centrality measure $\mathsf{C}$ for digraphs. The following
statements are equivalent:

  1. (1)

$\mathsf{C}$ is a subgraphs motif centrality measure for digraphs.

  2. (2)

For every $n>0$, $|\text{\rm Val}^{n}(\mathsf{C})|\leq n+1$.

###### Theorem G.5.

Consider a centrality measure $\mathsf{C}$ for digraphs. The following
statements are equivalent:

  1. (1)

$\mathsf{C}$ is a subgraph motif centrality measure for digraphs relative to
the induced ranking.

  2. (2)

Every finite set $S\subseteq\mathbf{VG}$ is $\mathsf{C}$-colorable.

  3. (3)

$\mathbf{VG}$ is $\mathsf{C}$-colorable

The above statements look the same as Theorems 4.2 and 5.4. Note, however,
that they are semantically different since all the underlying notion (such as
$\text{\rm Val}^{n}(\mathsf{C})$ and $\mathbf{VG}$ are for directed graphs).
Interestingly, the proofs are identical with those for Theorems 4.2 and 5.4.
We can finally state a result, analogous to Proposition 5.7, for directed
graphs, which essentially states that the non-uniform bounded value property
for directed graphs is a necessary condition for a measure for digraphs being
subgraph motif relative to induced ranking.

###### Proposition G.6.

Consider a centrality measure $\mathsf{C}$ for digraphs. If there exists a
precoloring of $\mathbf{VG}$ that is non-uniformly $\mathsf{C}$-injective,
then $\mathsf{C}$ enjoys the non-uniform bounded value property.

### Monotonic Subgraph Motif Measures for Digraphs

We now state our main characterizations concerning monotonic subgraph motif
measures for the case of directed graphs, which are similar to the ones for
undirected graphs. Note that the sets $\text{\rm BVal}_{G}^{n}(\mathsf{C})$
and $\text{\rm BVal}^{n}(\mathsf{C})$ are defined in exactly the same way as
for undirected graphs.

###### Theorem G.7.