# NISQ-ready community detection based on separation-node identification

Jonas Stein1, Dominik Ott1, Jonas Nüßlein1, David Bucher2, Mirco Schoenfeld3
and Sebastian Feld4
1Mobile and Distributed Systems Group, LMU Munich
2Aqarios GmbH
3Data Modelling & Interdisciplinary Knowledge Generation, University of
Bayreuth
4Delft University of Technology
e-mail<EMAIL_ADDRESS>0000-0001-5727-9151 0000-0001-7129-1237
0009-0002-0764-9606 0000-0002-2843-3137 0000-0003-2782-1469

###### Abstract

The analysis of network structure is essential to many scientific areas,
ranging from biology to sociology. As the computational task of clustering
these networks into partitions, i.e., solving the community detection problem,
is generally NP-hard, heuristic solutions are indispensable. The exploration
of expedient heuristics has led to the development of particularly promising
approaches in the emerging technology of quantum computing. Motivated by the
substantial hardware demands for all established quantum community detection
approaches, we introduce a novel QUBO based approach that only needs number-
of-nodes many qubits and is represented by a QUBO-matrix as sparse as the
input graph’s adjacency matrix. The substantial improvement on the sparsity of
the QUBO-matrix, which is typically very dense in related work, is achieved
through the novel concept of separation-nodes. Instead of assigning every node
to a community directly, this approach relies on the identification of a
separation-node set, which – upon its removal from the graph – yields a set of
connected components, representing the core components of the communities.
Employing a greedy heuristic to assign the nodes from the separation-node sets
to the identified community cores, subsequent experimental results yield a
proof of concept. This work hence displays a promising approach to NISQ ready
quantum community detection, catalyzing the application of quantum computers
for the network structure analysis of large scale, real world problem
instances.

###### Index Terms:

Quantum Computing, Community Detection, QUBO, NISQ

##  I Introduction

In the era of digitization, the amount of collected data is rising rapidly.
This poses substantial problems in data analysis as the algorithms employed
there typically have superlinear and thus deficient runtime for many relevant
datasets. In this work, we investigate a new approach to cope with this
problem in the domain of graph structure analysis. Graphs are one of the
central data structures used in information theory and find application in a
vast range of scientific disciplines [1, 2, 3]. The task of identifying the
inherit structure of a graph is known as community detection [4]. In practice,
the use of corresponding clustering methods allows for the discovery of
structural information from real world networks in domains ranging from social
science to biology [5, 6].

Although no exact definition has been agreed upon, a graph is typically said
to inherit a community structure if it can be partitioned in a way such that
the number of edges within the partitions is higher than the number of edges
between the partitions [5]. While some approaches exist that can provably find
existing community structures, all of them are NP-hard [7, 8, 9, 10]. This
indicates a general NP-hardness of community detection and hence poses a
demand for efficient heuristics to acquire solutions in reasonable time.
Motivated by recent advancements and promising results in solving NP-hard
problems in the field of quantum computing (QC) [11, 12, 13, 14], we
investigate possible advantages in building such heuristics by utilizing the
more powerful algorithmic toolset available in QC.

In general, quantum computers allow for the application of quantum mechanical
effects to do computation. Based on the concepts of superposition and
entanglement, quantum computers can solve many computational problems provably
faster than classical computers [15, 16, 17]. In the case of community
detection, related work has shown promising results using the popular
modularity maximization approach [12, 18]. Modularity is a measure for the
quality of a given partitioning based on comparing the edge distribution of
the given graph to the edge distribution of a graph with the same node degree
but inheriting no community structure [19]. The more these distributions
differ, the higher the modularity indicating a clearer community structure.
While this approach is provably optimal in the sense that no other approach
could detect a community structure when modularity maximization cannot [7],
its implementation on a quantum computer is cumbersome, especially for current
quantum computers.

Present implementations of modularity maximization on quantum computers make
use of the intrinsic quadratic nature of the modularity [12, 18]. Simulating
the time evolution of a specific quantum physical system, i.e., typically the
transverse field Ising Model under adiabatic time evolution, a quantum
heuristic solver for quadratic unconstraint binary optimization (QUBO)
problems (e.g., modularity maximization) can be implemented on a quantum
computer [12, 20]. Even though no quantum speedups where proven for solving
NP-hard optimization problems with this approach jet, many cases of potential
scaling advantages have been identified, with modularity maximization being
one of them [12, 13, 14].

A critical limitation of the established quantum modularity maximization
approach hindering its execution on near term quantum hardware is the size of
the search space in optimization. Scaling linearly in the number of nodes and
the number of communities, the required amount of quantum bits (qubits) needed
for representing a specific solution quickly exceeds the number of qubits
available in present noisy intermediate scale quantum (NISQ) hardware [21].

Motivated by these results, we develop a novel approach to community
detection, specialized for (quantum heuristic) QUBO solving that uses a
smaller search space than the state-of-the-art quantum modularity maximization
approach. This objective led to the sociologically inspired approach of
defining a community by its extreme ends, similar to, e.g., differentiating
political parties by their position on the left-right spectrum. For graphs, we
translate this idea to the existence of, what we will later define as, a
bijective set of separation nodes. The removal of the nodes contained in this
set then yields connected components, which represent the ”cores” of the
communities. We subsequently conduct experiments, that indicate that this
essentially solves the hard part of the community detection problem, as the
community assignment for the separation nodes can typically be obtained using
a greedy optimizer.

This idea allows for a quantum-classical hybrid detection of communities while
merely using one qubit for every node in the graph with a single call to a
QUBO solver. We show empirically that such a set of separation nodes can be
found for graphs inheriting community structure and introduce a quantum
heuristic approach to find them, constituting a proof-of-concept.

This paper is structured in the following way: in section II we describe the
current state of the art of quantum community detection, in section III the
separation node set approach to (quantum) community detection is introduced to
then get evaluated in section IV before concluding the findings in section V.

##  II Related Work

With the advent of quantum optimization heuristics like quantum annealing,
possible quantum advantages have been explored for many optimization problems
[22]. Easily allowing for a binary encoding of solutions and showing promising
performance, community detection quickly became a popular problem in quantum
optimization [23].

Representing community detection natively as a QUBO problem in the basic case
of partitioning into $k=2$ communities, modularity maximization was the first
approach used in quantum community detection [18]. For a given graph
$G=\left(V,E\right)$, the modularity of a partitioning into
$V_{0}=\left\\{v_{i}\in V\mid x_{i}=0\right\\}$ and $V_{1}=\left\\{v_{i}\in
V\mid x_{i}=1\right\\}$ according to
$x=\left(x_{1},...,x_{\left|V\right|}\right)\in\left\\{0,1\right\\}^{\left|V\right|}$
is given by

$\dfrac{1}{2\left|E\right|}\sum_{ij}\left(a_{ij}-\dfrac{d_{i}d_{j}}{2\left|E\right|}\right)x_{i}x_{j}$
(1)

for given node degrees $d=\left(d_{1},...,d_{\left|V\right|}\right)$ and
$a_{ij}$ denoting the entries of the adjacency matrix $A$ of $G$.
Straightforward calculations yield the resulting QUBO matrix
$Q=A-\frac{dd^{\intercal}}{2\left|E\right|}$ which is sufficient to apply
practically all currently available quantum optimization heuristics.

This approach to can be generalized to $k>2$ communities by introducing one-
hot encoding. Here, the community assignment of a node $v_{i}\in V$ is encoded
by a $k$-dimensional bit string
$x_{i}=\left(x^{\left(1\right)}_{i},...,x^{\left(k\right)}_{i}\right)$ with
$x^{\left(l\right)}_{i}=1$ and $x^{\left(m\right)}_{i}=0$ $\forall m\neq l$ if
the node $v_{i}$ is assigned to community $l$. The resulting optimization term
is hence given by:

$\dfrac{1}{2\left|E\right|}\sum_{ij}\left(a_{ij}-\dfrac{d_{i}d_{j}}{2\left|E\right|}\right)\left(\sum_{l}x^{\left(l\right)}_{i}x^{\left(l\right)}_{j}\right)$
(2)

In order to formulate this as a QUBO problem, we have to add a suitably
weighted penalty term $P(x)$ (for details, see [24]) to the optimization term
to indirectly enforce the one-hot encoding by $P(x)=0$ if every node is
assigned to exactly one community and $P(x)>0$ otherwise:

$P(x)=\sum_{i}\left(1-\sum_{l}x^{\left(l\right)}_{i}\right)^{2}$ (3)

Apart from capitalizing on the inherent QUBO form of modularity maximization,
many other quantum computing based approaches to community detection like
Quantum Genetic Algorithms and Quantum Walks have been proposed in recent
literature [25, 26]. A particularly promising approach for near term
application on large graphs is based on exploiting the quadratic nature of
regularity checking related to Szemeredi’s Regularity Lemma (SRL) [27]. While
similar to our approach, as the QUBO problems solved only involve
$\left|V\right|$ qubits, it fundamentally works differently, as communities
are identified iteratively. In essence, the algorithm proposed in [27]
executes the following steps:

  1. 1.

Randomly split the given graph $G=\left(V,E\right)$ into two equally sized
partitions $A\dot{\cup}B=V$ and delete all edges inside the partitions to
yield a bipartite graph

  2. 2.

Find subsets $X\subseteq A$ and $Y\subseteq B$ such that $X=\left\\{v_{i}\in
A\mid s_{i}=1\right\\}$ and $Y=\left\\{v_{j}\in B\mid s_{j}=1\right\\}$ where
$s=\left(s_{1},...,s_{\left|V\right|}\right)$ is the solution to the quadratic
program given by:

$\operatorname*{arg\,min}_{s\in\left\\{0,1\right\\}^{\left|V\right|}}\sum_{\begin{subarray}{c}v_{i}\in
A\\\ v_{j}\in B\end{subarray}}\left(d(A,B)-a_{ij}\right)s_{i}s_{j}$ (4)

Here, $d(V_{1},V_{2})$ denotes the link density of two disjoint sets $V_{1}$,
$V_{2}$ given by $\frac{e(V_{1},V_{2})}{\left|V_{1}\right|\left|V_{2}\right|}$
and $e(V_{1},V_{2})$ represents the number of edges connecting $V_{1}$ and
$V_{2}$.

  3. 3.

Identify $C\vcentcolon=X\cup Y$ to be a community and repeat steps 1) and 2)
for the subgraph induced on $G$ by $V\setminus C$.

While this approach has a solid graph theoretic foundation, the high number of
needed solver calls and the dense QUBO matrix still pose nontrivial hardware
execution challenges in the NISQ era.

Aiming to minimize the demands to the QUBO solver, we propose a radically
different approach that only needs a single QPU call and whose QUBO matrix is
topologically identical to adjacency matrix of the given graph and hence,
equally sparse. The approach presented in this work essentially purifies a
solution of relaxed community detection problem, i.e., the final community
structure is represented by the solution of a QUBO problem which is based on
classically computed, probabilistic community assignments for each node. While
we introduce a particularly efficient approach to calculate the needed input
for the QUBO problem, many other approaches to relaxed community detection
have been proposed in related work like semidefinite programming or
convexification [28, 29, 30, 31].

As derived in detail in the next section, our approach requires a solution for
a novel relaxation of the community detection problem as input to the QUBO
problem formulation. In essence, our approach demands for an estimate value
for each edge, specifying whether it connects nodes belonging to different or
the same communities. While such estimates could in principle be computed
based on the output of solvers for the relaxed community detection problem by
using, e.g., the KL-divergence of the community affiliations of neighboring
nodes, we introduce a specialized estimation method tailored to this task.
Notably, metrics like the edge betweenness centrality [32] also do not yield
satisfactory results for our approach, as the difference in values between
separation- and non-separation-edges is seemingly too small.

##  III Concept

In the following, we explore the idea of performing community detection based
on finding a suitable set of nodes separating the communities as defined in
III.1 in a rigorous mathematical manner. Meeting the demand from the derived
QUBO formulation for a separation edge estimator, we subsequently introduce a
promising heuristic approach based on the concept of modularity.

###  III-A Separation-node sets

The approach presented in this paper consists of two steps:

  1. (1)

identifying a set of nodes separating communities and thus revealing the
fundamental community structure (sec. III-B and III-C)

  2. (2)

classifying the community of each separation-node to finalize the community
detection (sec. III-D)

Either using a trivial, greedy approach introduced in III-D or a slight
adaptation of the well-known QUBO-formulation of modularity maximization [33]
to perform (2), the main objective of this paper is the development of a QUBO-
approach realizing (1). To provide a more formal definition of (1), we now
introduce the concept of separation-node sets. In the following, we use
$\mathcal{S}$ to denote the set of all separation-node sets.

######  Definition III.1.

For a graph $G=\left(V,E\right)$ and a ground truth community structure $C$
partitioning $V$, we call $S\subseteq V$ a set of separation-nodes iff the
connected components $\overline{S}_{i}$ partitioning the graph induced by
$V\setminus S$ are distributed such that
$\left\\{\overline{S}_{i}\right\\}_{i}$ is a refinement of $C$.

Equivalent to this definition, one could also demand the existence of a
refinement map
$\phi:\mathcal{P}\left(V\right)\rightarrow\mathcal{P}\left(V\right)$ mapping
each connected component $\overline{S}_{i}\subseteq V$ onto a community
$\phi\left(\overline{S}_{i}\right)=C_{j}\in C$ such that
$\overline{S}_{i}\subseteq C_{j}$. Utilizing the notion of separation-node
sets, (1) can be formulated as finding a smallest set of separation-nodes
whose associated refinement map $\phi$ is ideally bijective. An example of a
set of separation-nodes satisfying these conditions is depicted in subfigure
1(b), which is part of figure 1 displaying the proposed approach. As it will
become apparent in the evaluation, such well behaved separation node sets can
also be found in graphs with application near topologies.

(a) Exemplary graph consisting of three connected cliques.

(b) Identification of a set of separation-nodes (marked in red).

(c) Removal of the set of identified separation-nodes and identification of
the resulting connected components.

(d) Classification of the community of all identified separation-nodes.

Figure 1: Outline of the workflow for the approach proposed approach of
community detection via separation-node identification. The computationally
expensive tasks of identifying a set of separation-nodes (subfigure 1(b)) and
classifying the communities for these nodes (subfigure 1(d)) are performed
using quantum computing, while the computationally cheap tasks of removing the
classified separation-nodes and identifying the resulting connected components
(subfigure 1(c)) are done classically.

The surjectivity of $\phi$ ensures that each community gets detected and its
injectivity ascertains, that no communities get split. In the following, we
will call separation-node sets injective, surjective or bijective iff the
respective refinement function satisfies these conditions. In order to
formulate a QUBO problem where the optimal solution represents the minimal
separation-node set, we start by stating an alternate, more convenient,
definition of minimal separation-node sets.

######  Theorem III.1.

For an adequate penalty term $P$ ensuring the separation-node set properties,
the following equation states an equivalent definition of the set containing
all minimal separation-node sets $\mathcal{S}_{min}$.

$\mathcal{S}_{min}=\left\\{\bigcup_{\begin{subarray}{c}v_{i}\in V\\\
x_{i}=0\end{subarray}}v_{i}\mid
x=\operatorname*{arg\,min}_{x\in\left\\{0,1\right\\}^{\left|V\right|}}2P(x)-\sum_{v_{i}\in
V}x_{i}\right\\}$ (5)

Here, we used $x\in\left\\{0,1\right\\}^{\left|V\right|}$ as a $0$-flag for
separation-nodes, $a_{ij}$ to denote the entries of the adjacency matrix,
$c:V\rightarrow C$ as a mapping of nodes to their ground truth community and
the Kronecker delta $\delta_{xy}$. For a penalty term $P$ ensuring the
validity of the separation-node set definition by penalizing incident node
pairs from strictly different communities where neither node is element of the
sought-after separation-node set, see the following definition:

$P\left(x\right)\vcentcolon=\sum_{\left(v_{i},v_{j}\right)\in
V^{2}}a_{ij}\left(1-\delta_{c\left(v_{i}\right)c\left(v_{j}\right)}\right)x_{i}x_{j}$

###### Proof.

See appendix V-A. ∎

Therefore, the task of finding a smallest set of separation-nodes for any
given graph is native to the concept of QUBO and its formulation can be
reduced to approximating $\delta_{c\left(v_{i}\right)c\left(v_{j}\right)}$ for
incident node pairs $v_{i},v_{j}\in V$. This can be understood as calculating
the probability of an edge being an interconnection of adjacent nodes
belonging to different communities, or more formally, a separation-edge.

Most interestingly, we can show that solving the QUBO problem stated in
equation 5 is NP-hard for a specific estimator. To see this, we start by
observing a substantial similarity of our QUBO formulation with the QUBO
formulation of the Max-Clique problem as stated in [34]:

$\operatorname*{arg\,min}_{x\in\left\\{0,1\right\\}^{\left|V\right|}}2\sum_{\left(v_{i},v_{j}\right)\in
V^{2}}\left(1-a_{ij}\right)x_{i}x_{j}-\sum_{v_{i}\in V}x_{i}$ (6)

for a given graph $G=(V,E)$ and its corresponding adjacency matrix $A$ with
entries $a_{ij}$. Choosing the estimator $s:V\times
V\rightarrow{}\left\\{0,1\right\\}$ by
$s\left(\left(v_{i},v_{j}\right)\right)\vcentcolon=a_{ij}$, it becomes
apparent, that the QUBO formulations are identical if we specify to use a
complete graph of size $\left|V\right|$ as an input to our QUBO formulation.
Leaving an extensive mathematical analysis of the NP-hardness for more
realistic estimators to future work, this shows that the problem of finding a
minimal separation-node set is NP-hard when treating the estimator as a
variable. This result supports the pursuit of the proposed approach of using
quantum computing in order to find a minimal separation-node.

Returning to the initial goal of finding bijective separation-node sets, we
now explore their surjectivity. A significant discovery regarding surjectivity
is illustrated in figure 2, showing no-free-lunch when using theorem III.1 to
find surjective separation-node sets. This necessitates the addition of a
penalty term to the QUBO formulation in order to ensure surjectivity when
building upon theorem III.1. For the formulation of a suitable penalty term,
see appendix V-B.

(a) A graph and its community structure.

(b) Minimal separation-node set consisting of all nodes marked in red.

(c) Minimal surjective separation-node set consisting of all nodes marked in
red.

Figure 2: Counterexample proving no-free-lunch when using theorem III.1 to
find surjective separation-node sets.

As our formulation results in a PUBO (polynomial unconstrained binary
optimization) problem of degree $\mathcal{O}(\log_{2}|V|)$, we conjecture,
that this constraint cannot be realized in QUBO form without the addition of
ancillary variables. Using the standard quadratization approach with the
Rosenberg polynomial [35], a QUBO formulation of this term demands
superpolynomially many ancillary variables, i.e.,
$\mathcal{O}\left(\left|V\right|^{2\log_{2}\log_{2}\left|V\right|}\right)$. In
the context of quantum annealing, this scaling beyond a quadratic number of
qubits makes the surjective separation-node approach overly complex compared
to the standard modularity maximization. In the gate model, the QAOA can be
used to solve PUBO problems in principle, but as current hardware limitations
prohibit adequate evaluation, we leave the exploration of the surjectivity
constraint to future work.

As a consequence of not enforcing surjectivity, there exists a possibility
that number of communities is incorrect after step (1) of detecting the
fundamental community structure by separation-node set identification.
Modifying step (2) slightly, this could in principle be compensated by
iteratively increasing the number of possible communities until no further
improvement of the modularity can be achieved. A clever way to do this, could
be the elbow-method as known in clustering [36]. For the alternative greedy
approach for the second step (2), the possibility of merging communities could
be allowed.

Fortunately, conducted experiments show that topological structures precluding
free lunch are scarce in practice. Therefore, we will omit the explicit demand
for surjective separation-node sets in the following.

Analog to the surjectivity, there exist graph topologies like the one
displayed in figure 3 showing no free lunch when using theorem III.1 to find
injective separation-node sets. Hence, it appears necessary to ensure
injectivity explicitly using a penalty term when building upon theorem III.1
in principle, as well. The formulation of such a penalty term also turns out
to be rather tedious, as can be seen in appendix 18. In this case, we end up
with an even higher dimensional PUBO problem for the injectivity than for the
surjectivity. Luckily, compared to the surjectivity, the injectivity of a
separation-node set is of less importance, as the second step (2) could easily
be adapted to cope with this. Analog to the case of surjectivity, we observe
such topological structures preventing free lunch quite rarely in conducted
experiments, resulting in the analog dismissal of an explicit demand for the
separation-node sets to be injective in practice.

(a) A graph and its community structure.

(b) Minimal separation-node set consisting of all nodes marked in red.

(c) Minimal injective separation-node set consisting of all nodes marked in
red.

Figure 3: Counterexample indicating no-free-lunch when using theorem III.1 to
find injective separation-node sets.

In summary, the apparent infrequence of topological structures preventing free
lunch regarding bijectivity renders the QUBO-formulation stated in theorem
III.1 to be a well-founded starting point for the stated proposition of QUBO
based community detection via separation-node sets.

While this approach provides exact results for a perfect classification of
separation-edges, it fully relies on a suitable estimation heuristic. Although
many known measures for a variety of edge properties exist (as described in
II), none showed to be entirely suitable for detecting separation-edges
according pretesting conducted for this paper. Consequently, we now motivate a
novel approach tailored for exactly this task based on the concept of
modularity.

###  III-B Modularity based separation-edge estimation

Motivated by the proven optimality of modularity and by the fact that at its
core, modularity stems on essentially estimating whether each node pair is
likely to belong to the same or different communities, we start by showing how
this idea can be used to estimate
$\delta_{c\left(v_{i}\right)c\left(v_{j}\right)}$. For this, recall the
definition of the entries of the modularity matrix:

$m_{ij}\vcentcolon=\dfrac{a_{ij}-\mathbb{E}\left[J_{ij}\right]}{\left|E\right|}$
(7)

As before $a_{ij}$ are the entries of the respective adjacency matrix, while
$\mathbb{E}\left[e_{ij}\right]$ denotes the expected value of the number of
edges between $v_{i}$ and $v_{j}$, $J_{ij}$. Upon closer inspection, we
observe two main cases:

  * •

$m_{ij}>0$, iff less connectivity between $v_{i}$ and $v_{j}$ was to be
expected, indicating that $v_{i}$ and $v_{j}$ likely belong to the same
community

  * •

$m_{ij}<0$, iff more connectivity between $v_{i}$ and $v_{j}$ was to be
expected, indicating that $v_{i}$ and $v_{j}$ likely belong to different
communities

As the matrix entries $m_{ij}$ are normalized to the interval of
$\left[-1,1\right]$ by the division with $\left|E\right|$, we can see, that
using proper rescaling to the intervall of $\left[0,1\right]$, i.e., via
$2\left(m_{ij}+1\right)$, this allows for an estimation of the term
$\delta_{c\left(v_{i}\right)c\left(v_{j}\right)}$ in principle.

In practice however, this approach yields extremely bad estimations, as only
the entries $m_{ij}$ of the modularity matrix are relevant, that correspond to
a given edge $\left(v_{i},v_{j}\right)\in E$. For these, it quickly becomes
apparent, that $m_{ij}$ is typically larger than $0$, making this exact idea
infeasible in practice. These considerations motivate an adaptation of
modularity for the estimation of separation-edges as proposed in the
following.

###  III-C Edge neighborhood connectivity based separation-edge estimation

Exploiting the mathematical structure of modularity for a straightforward
separation-edge estimation, we now introduce a promising generalization of the
previous approach, which we coin as the neighborhood connectivity of an edge.
Instead of merely taking the direct connection between two nodes into account
(i.e., an edge), the neighborhood connectivity of an edge considers
connections between the neighborhoods of the nodes. In this context, the
neighborhood $N_{r}\left(v\right)$ of a node $v\in V$ is defined to be the set
of nodes with a shortest path of length $r$ to $v$.

Based on this idea, we can rephrase the basic case of our generalization,
i.e., modularity, as merely counting the number of unique edges on paths of
length $1$ between the $0$-neighborhoods $N_{0}\left(v_{i}\right)$ and
$N_{0}\left(v_{j}\right)$ of the respective nodes $v_{i}$ and $v_{J}$. The
here proposed generalization introduces the following two new notions:

  1. (1)

Consider connections between $r$-neighborhoods with radius $r\geq 0$

  2. (2)

Also consider paths of length $2$

Stating this more precisely in mathematical form, we now define the
neighborhood connectivity $\nu_{r}^{\left(l\right)}$ of an edge given a path
length $l$, and a neighborhood size $r$:

$\nu_{r}^{\left(l\right)}\vcentcolon=\dfrac{a_{r}^{\left(l\right)}-\mathbb{E}\left(a_{r}^{\left(l\right)}\right)}{n_{r}^{\left(l\right)}}$
(8)

In this definition, $a_{r}^{\left(l\right)}$ denotes the number of unique
edges contained in paths of length $l$ connecting the $r$-neighborhoods of the
given nodes which do not involve nodes or edges contained by the
$\left(r-1\right)$-neighborhoods (as this would result in possible double
counting of edges). Analogously to the definition of modularity,
$\mathbb{E}\left(a_{r}^{\left(l\right)}\right)$ denotes the expected value
corresponding to $a_{r}^{\left(l\right)}$ and $n_{r}^{\left(l\right)}$ acts as
a normalization factor denoting the highest possible number
$a_{r}^{\left(l\right)}$ can assume.

These values can be calculated based on a simple breadth first search with
depth $r$ iterating of the neighborhood layers while choosing $v_{i}$ and
$v_{j}$ as starting nodes. As for the expected value calculation, the
configuration model has shown to be an adequate choice (which is in line with
modularity). For details on this, we refer to our implementation which can be
made available upon request to the authors.

Our preferred method of combining the results into the neighborhood
connectivity $\nu$ of a given edge based on all $\nu_{r}^{\left(l\right)}$ is
the dot product with a weight vector $w$ with entries
$w_{r}^{\left(l\right)}\in\mathbb{R}_{0}^{+}$ such that their sum equals $1$:

$\nu\vcentcolon=\sum_{r=1}^{d}w_{r}^{\left(1\right)}\nu_{r}^{\left(1\right)}+\sum_{r=0}^{d-1}w_{r}^{\left(2\right)}\nu_{r}^{\left(2\right)}$
(9)

As we know that the standard modularity value is of little use, we chose
$w_{0}^{\left(1\right)}=0$. We consider the remaining weights as
hyperparameters, for which $w_{0}^{\left(2\right)}=0.5=w_{1}^{\left(1\right)}$
have proven to be suitable values according to conducted experiments.

###  III-D Assigning the separation-nodes to communities

As stated in sec. III-A, we propose two different approaches to assigning the
separation-nodes to communities, i.e., (1) a greedy strategy and (2)
modularity maximization. In the experiments conducted in this paper, the
greedy strategy was mainly employed for all experiments. It works as follows:

  1. (1)

count the number of edges to every know community for each separation-node

  2. (2)

assign the node with the most edges to a single community to that community

  3. (3)

update the counts for every neighboring separation-node

  4. (4)

repeat steps two and three until every separation-node is properly assigned to
a community

This algorithm has a runtime of the number of separation nodes $S$ times the
number of communities $\left|C\right|$,
$\mathcal{O}\left(S\cdot\left|C\right|\right)$ and hence runs very
efficiently.

As the results calculated based on the edge neighborhood connectivity did not
always show reasonable quality to sensibly use this greedy optimizer, we chose
to use the standard of modularity maximization for these special cases.
Fortunately, the well known QUBO approach to this [18], can be easily adapted
to our situation, i.e., by clamping the values of the known community
assignments, where clamping is to be understood in the same way as it is used
in quantum Boltzmann machines [37]. This yields a QUBO problem of size
$\mathcal{O}\left(S\cdot\left|C\right|\right)$, which often can be solved a
lot quicker than the original problem, as $S<\left|V\right|$ in practice.

##  IV Evaluation

The evaluation aims at the examination of the validity of the following two
claims:

  1. (1)

the assignment of separation-nodes to their communities is computationally
easy, given a good enough estimator

  2. (2)

neighborhood connectivity allows for proof of concept results

As we will show in the following, both claims appear to be valid according to
the conducted experiments.

For investigating claim (1), we propose to check, if the greedy separation-
node assignment as described in sec. III-D is sufficient to assign the nodes
of a well behaved separation-nodes to the correct communities. If this
approach is indeed sufficient to obtain (nearly) perfect solutions, we reason
that the claim is most likely valid.

In order to eliminate the possibility of an insufficient separation-node set,
we use a synthetic dataset with known community structure, allowing for the
use of a perfect estimator for the separation-edges. In order to find a very
good separation-node set, we utilize a simple simulated annealing approach to
solve the associated QUBO as defined in 5. Regarding the synthetic dataset, we
choose the stochastic block model (SBM) [38] which is a widely used tool for
benchmarking in the realm of community detection. Aiming to achieve realistic
results, we use a graph of size $\left|V\right|=250$, structured into seven
equally sized communities with varying intra- and interconnections between the
communities, resembling three different difficulties, according to the phase
transition of community detection on SBMs (for details on the phase
transition, see [9]). As it becomes apparent in the corresponding figure 4,
the greedy separation-node assignment indeed yields optimal or at least close
to optimal results, indicating the validity of claim (1).

Figure 4: This figure shows the NMI score of the presented approach for 50
different graphs each, based on ground truth and a perfect separation-edge
estimator coupled with the greedy separation-node assignment. The NMI score as
defined in [39, 40] was used, as it resembles a well proven measure for the
accuracy of a community given ground truth [41]. The different probabilities
for intra-community edges in the chosen SBM model resemble different
difficulties according to the phase transition known for this model. The lower
the stated probability, the harder the problem. The probabilities were chosen
such that the hardest graphs barely differed from a null model inheriting no
measurable structure up to the hardest that still allowed perfect NMI scores.

Having seen solid results for the optimal estimator, we now want to
investigate the performance of the here presented ”neighborhood connectivity”
approach for real world data and hence explore claim (2). For this, we choose
the greedy separation-node assignment, so that the separation-node
identification displays the only non-trivial task, capable of solving the
problem instances. Choosing standard real world benchmark graphs of varying
size, we can observe stable results for most datasets in figure 5, while often
achieving 90 to 95% optimal results.

Figure 5: This box plot displays the fraction of the achieved modularity score
by the best known solution for selected standard benchmark datasets: (1) the
social network of a karate club [42], (2) the social interactions between
dolphins [43], (3) the collectively appearing characters in the book ”Les
Miserables” [44], (4) protein protein interacations [45] and (5) jointly
bought political books [46]. Each graph was analyzed 10 times using simulated
annealing. Our approach clearly does not work well for the karate club
network. Closer inspections yield that the connected components resulting from
the found separation-node sets often only consist of single nodes, indicating
suboptimality in using neighborhood connectivtiy for this dataset.

Motivated by these proof of concept results, we now investigate the
performance of the proposed estimator (edge neighborhood connectivity) in
order to explore its optimal mission scenario. For this, we again resort to
equally formed SBM benchmark graphs with slightly higher intra-community
connection probabilities, as they offer the comparison with ground truth
information. Concretely, we chose these probabilities to be 0.75 for the easy
case, 0.625 for the medium case and 0.5 for the hard case, which was the easy
case for the experiments conducted with the perfect estimator (and picked
previously as the hardest case to still yield perfect results).

Analogously to the perfect estimator, the identified separation-node sets were
all valid and bijective in a small test run on 10 graphs. Switching the main
optimization goal, we now examine the size of the identified separation-node
sets for graphs of different difficulty, as displayed in figure 6. Here, we
can see, that the sizes of the separation-node sets found are substantially
larger than the best known solution, this becomes apparent especially for easy
problem instances. Interestingly, the performance quality increases for harder
problems in relative perspective, showing promising scaling behavior.

Figure 6: The $y$-axis depicts the deviation factor from the best known
separation-node set in size. Notably, the absolute sizes of the identified
separation-node sets are typically similar over the different difficulties,
while they rise slightly for larger graphs.

Although the separation-node sets found are well behaved, the combination with
the greedy separation-node assignment to communities does yield substantially
worse results than the perfect estimator, as shown in figure 7.

Figure 7: This figure depicts the normalized mutual information score of the
selected SBM benchmark graphs using the greedy assignment of separation-nodes
to communities. A substantial drop off in performance can be observed for the
harder datasets.

Subsequent experiments show, that the performance for the medium and hard
datasets can be improved significantly by exchanging the greedy approach for a
simulated annealing based one, as shown in figure 8.

Figure 8: This figure depicts the normalized mutual information score of the
selected SBM benchmark graph using a simulated annealing based approach of
assigning the separation-nodes to communities. The worse performance for the
easy dataset clearly indicates that the chosen simulated annealing approach
based on the QUBO as described in III-D is suboptimal in general.

As described in the caption of figure 8, simulated annealing based on the QUBO
as described in III-D seems to be a suboptimal choice to assign separation-
nodes to communities. We suspect that the reason for this resides in the large
size of the search space for the given problem instances due to the employed
one-hot encoding. As identified separation-node sets are typically sized up to
200 nodes (compared to the roughly 120 nodes for the perfect estimator), the
search space for the problem instances thus contains roughly $\left(200\cdot
7\right)!=1400!$ possible solutions, as 7 different communities exist.

In order to put the results of the developed separation-edge estimator based
on edge neighborhood connectivity into perspective with an optimal estimator,
we now investigate its $R^{2}$ score in figure 9. Interestingly, the worse
performance for larger datasets has no impact on the validty and bijectivity
of the subsequently identified separation-node set, which is very promising in
regards to scaling.

Figure 9: $R^{2}$ score of the edge neighborhood connectivity based
separation-edge estimator. In practice, an $R^{2}$ score of 30% implies that
merely 30% of the variability of the ground truth has been accounted for. A
strict trend towards worse results for harder datasets is clearly visible.
This shows that the performance of the estimator decreases for harder problem
instances as to be expected while still yielding somewhat accurate results.

##  V Conclusion

Having set out with the goal of developing a quantum community detection
approach that allows for the analysis of large graphs in the NISQ era, we
presented the idea of identifying communities via their borders. The derived
separation-node set based approach was shown to yield (close to) optimal
results depending on the accuracy of the classical separation-edge estimator.
The therefore proposed heuristic approach based on the introduced concept of
”edge neighborhood connectivity” enabled for proof of concept results on real
world data. In particular, as our approach merely requires $\left|V\right|$
qubits and as the corresponding QUBO is as sparse as the input graph
$G=\left(V,E\right)$, separation-node based community detection resembles the
least hardware demanding quantum computing approach to community detection to
the best of our knowledge. The underlying trade-off necessary for this
accomplishment clearly is the more demanding classical part in this hybrid
approach (i.e., the separation-edge estimation). We firmly encourage future
work on this heuristic, while conjecturing the incorporation of solutions of
the relaxed community detection problem as highly beneficial. Furthermore, the
exploration of adaptations of similar known metrics like edge betweenness
centrality [47] also seem very interesting. Overall, we conclude our approach
to be highly promising for accelerating the possibility of solving real world
community detection problems using quantum computers and thus opening up a
path towards network structure analysis in big data.

## Acknowledgments

This work was partially funded by the German BMWK project PlanQK (01MK20005I)
and the Bavarian StMWi project QAR-Lab Bayern (46-6665e/443), respectively.

## References

  * [1] J. A. Bondy and U. S. R. Murty.  Graph Theory with Applications.  Elsevier, New York, 1976.
  * [2] A R Mashaghi, A Ramezanpour, and V Karimipour.  Investigation of a protein complex network.  Eur. Phys. J. B - Condens. Matter Complex Syst., 41(1):113–121, 2004.
  * [3] Preya Shah, Arian Ashourvan, Fadi Mikhail, Adam Pines, Lohith Kini, Kelly Oechsel, Sandhitsu R Das, Joel M Stein, Russell T Shinohara, Danielle S Bassett, Brian Litt, and Kathryn A Davis.  Characterizing the role of the structural connectome in seizure dynamics.  Brain, 142(7):1955–1972, 05 2019.
  * [4] Santo Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75–174, 2010.
  * [5] M. Girvan and M. E. J. Newman.  Community structure in social and biological networks.  Proceedings of the National Academy of Sciences, 99(12):7821–7826, 2002.
  * [6] Hossein Fani and Ebrahim Bagheri.  Community detection in social networks.  Encyclopedia with Semantic Computing and Robotic Intelligence, 01(01):1630001, 2017.
  * [7] Raj Rao Nadakuditi and M. E. J. Newman.  Graph spectra and the detectability of community structure in networks.  Phys. Rev. Lett., 108:188701, May 2012.
  * [8] U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner.  Maximizing modularity is hard, 2006.
  * [9] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Inference and phase transitions in the detection of modules in sparse networks.  Phys. Rev. Lett., 107:065701, Aug 2011.
  * [10] M. E. J. Newman.  Equivalence between modularity optimization and maximum likelihood methods for community detection.  Phys. Rev. E, 94:052315, Nov 2016.
  * [11] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G S L Brandao, David A Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P Harrigan, Michael J Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S Humble, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandra, Jarrod R McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C Platt, Chris Quintana, Eleanor G Rieffel, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Kevin J Sung, Matthew D Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M Martinis.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [12] Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Ilya Safro, Susan Mniszewski, and Yuri Alexeev.  Network community detection on small quantum computers.  Advanced Quantum Technologies, 2(9):1900029, 2019.
  * [13] Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven.  What is the computational value of finite-range tunneling?  Phys. Rev. X, 6:031015, Aug 2016.
  * [14] Tameem Albash and Daniel A. Lidar.  Demonstration of a scaling advantage for a quantum annealer over simulated annealing.  Phys. Rev. X, 8:031016, Jul 2018.
  * [15] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96, pages 212–219, Association for Computing Machinery, 1996. Philadelphia, Pennsylvania, USA.
  * [16] Peter W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM Journal on Computing, 26(5):1484–1509, 1997.
  * [17] Seth Lloyd.  Universal quantum simulators.  Science, 273(5278):1073–1078, 1996.
  * [18] Hayato Ushijima-Mwesigwa, Christian F. A. Negre, and Susan M. Mniszewski.  Graph partitioning using quantum annealing on the d-wave system.  In Proceedings of the Second International Workshop on Post Moores Era Supercomputing, PMES’17, page 22–29, New York, NY, USA, 2017. Association for Computing Machinery.
  * [19] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Phys. Rev. E, 69:026113, Feb 2004.
  * [20] Tadashi Kadowaki and Hidetoshi Nishimori.  Quantum annealing in the transverse ising model.  Phys. Rev. E, 58:5355–5363, Nov 1998.
  * [21] John Preskill.  Quantum Computing in the NISQ era and beyond.  Quantum, 2:79, August 2018.
  * [22] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova.  Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles.  EPJ Quantum Technol., 8(1):12, 2021.
  * [23] Sana Akbar and Sri Khetwat Saritha.  Towards quantum computing based community detection.  Computer Science Review, 38:100313, 2020.
  * [24] Ehsan Zahedinejad, Daniel Crawford, Clemens Adolphs, and Jaspreet S. Oberoi.  Multiple global community detection in signed graphs.  In Kohei Arai, Rahul Bhatia, and Supriya Kapoor, editors, Proceedings of the Future Technologies Conference (FTC) 2019, pages 688–707, Cham, 2020. Springer International Publishing.
  * [25] Alireza Saleh Sedghpour and Amin Nikanjam.  Overlapping community detection in social networks using a quantum-based genetic algorithm.  In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, page 197–198, New York, NY, USA, 2017. Association for Computing Machinery.
  * [26] Kanae Mukai and Naomichi Hatano.  Discrete-time quantum walk on complex networks for community detection.  Phys. Rev. Res., 2:023378, Jun 2020.
  * [27] Hannu Reittu, Ville Kotovirta, Lasse Leskelä, Hannu Rummukainen, and Tomi Räty.  Towards analyzing large graphs with quantum annealing.  In 2019 IEEE International Conference on Big Data (Big Data), pages 2457–2464, 2019.
  * [28] Emprise Y. K. Chan and Dit-Yan Yeung.  A convex formulation of modularity maximization for community detection.  In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Three, IJCAI’11, page 2218–2225. AAAI Press, 2011.
  * [29] Yudong Chen, Xiaodong Li, and Jiaming Xu.  Convexified modularity maximization for degree-corrected stochastic block models.  The Annals of Statistics, 46(4):1573–1602, 2018.
  * [30] Pedro Abdalla and Afonso S Bandeira.  Community detection with a subsampled semidefinite program.  Sampl. Theory, Signal Process. Data Anal., 20(1):6, 2022.
  * [31] Wenye Li.  Visualizing network communities with a semi-definite programming method.  Information Sciences, 321:1–13, 2015.  Security and privacy information technologies and applications for wireless pervasive computing environments.
  * [32] Ulrik Brandes.  A faster algorithm for betweenness centrality.  The Journal of Mathematical Sociology, 25(2):163–177, 2001.
  * [33] Christian F.A. Negre, Hayato Ushijima-Mwesigwa, and Susan M. Mniszewski.  Detecting multiple communities using quantum annealing on the D-Wave system.  PLoS ONE, 15(2), 2020.
  * [34] Guillaume Chapuis, Hristo Djidjev, Georg Hahn, and Guillaume Rizk.  Finding Maximum Cliques on the D-Wave Quantum Annealer.  J. Signal Process. Syst., 91(3):363–377, 2019.
  * [35] Ivo G. Rosenberg.  Reduction of bivalent maximization to the quadratic case.  Cahiers du Centre d’etudes de recherche operationnelle, 17:71–74, 1975.
  * [36] Robert L Thorndike.  Who belongs in the family?  Psychometrika, 18(4):267–276, 1953.
  * [37] Mohammad H. Amin, Evgeny Andriyash, Jason Rolfe, Bohdan Kulchytskyy, and Roger Melko.  Quantum boltzmann machine.  Phys. Rev. X, 8:021050, May 2018.
  * [38] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social Networks, 5(2):109–137, 1983.
  * [39] Ana L. N. Fred and Anil K. Jain.  Robust data clustering.  2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings., 2:II–II, 2003.
  * [40] L.I. Kuncheva and S.T. Hadjitodorov.  Using diversity in cluster ensembles.  In 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583), volume 2, pages 1214–1219 vol.2, 2004\.
  * [41] Leon Danon, Albert Díaz-Guilera, Jordi Duch, and Alex Arenas.  Comparing community structure identification.  Journal of Statistical Mechanics: Theory and Experiment, 2005(09):P09008, sep 2005.
  * [42] Wayne W. Zachary.  An information flow model for conflict and fission in small groups.  Journal of Anthropological Research, 33(4):452–473, 1977.
  * [43] David Lusseau, Karsten Schneider, Oliver J Boisseau, Patti Haase, Elisabeth Slooten, and Steve M Dawson.  The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations.  Behavioral Ecology and Sociobiology, 54(4):396–405, 2003.
  * [44] Donald E. Knuth.  The stanford graphbase: A platform for combinatorial algorithms.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’93, page 41–43, USA, 1993. Society for Industrial and Applied Mathematics.
  * [45] Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek.  Uncovering the overlapping community structure of complex networks in nature and society.  Nature, 435(7043):814–818, 2005.
  * [46] M. E. J. Newman.  Modularity and community structure in networks.  Proceedings of the National Academy of Sciences, 103(23):8577–8582, 2006.
  * [47] Yong Li, Wenguo Li, Yi Tan, Fang Liu, Yijia Cao, and Kwang Y Lee.  Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks.  Sci. Rep., 7(1):46491, 2017.
  * [48] Robert Sedgewick.  Algorithms in c, Part 5: Graph Algorithms, Third Edition.  Addison-Wesley Professional, third edition, 2001.

## Appendix

###  V-A Proving theorem IV.1

In the following, we provide a proof for theorem III.1, which states the
following equation:

$\mathcal{S}_{min}=\left\\{\bigcup_{\begin{subarray}{c}v_{i}\in V\\\
x_{i}=0\end{subarray}}v_{i}\mid
x=\operatorname*{arg\,min}_{x\in\left\\{0,1\right\\}^{\left|V\right|}}2P(x)-\sum_{v_{i}\in
V}x_{i}\right\\}$ (10)

Where, by definition, we have:

$\mathcal{S}_{min}\vcentcolon=\left\\{S\in\mathcal{S}\mid\left|S\right|\leq\left|S^{\prime}\right|\,\forall
S^{\prime}\in\mathcal{S}\right\\}$ (11)
$P\left(x\right)\vcentcolon=\sum_{\left(v_{i},v_{j}\right)\in
V^{2}}a_{ij}\left(1-\delta_{c\left(v_{i}\right)c\left(v_{j}\right)}\right)x_{i}x_{j}$
(12)

Aiming to prove “$\subseteq$” and “$\supseteq$” individually, we first prove
some lemmata.

######  Lemma V.1.

All $x\in\left\\{0,1\right\\}^{\lvert V\rvert}$ satisfying $P(x)=0$ represent
sets of separation-nodes.

###### Proof.

Let $x$ be a binary vector such that $P(x)=0$ and let $S$ be the corresponding
set of nodes. In order to prove the desired statement by contradiction, assume
$S\notin\mathcal{S}$, which is equivalent to the existence of a connected
component of the graph induced by $V\setminus S$ not being a subset of one
community. Then at least two nodes $v_{i},v_{j}\in V$ must exist, that are
connected via a path and belong to different communities. On this path, there
must exist two adjacent nodes the belong to different communities with neither
of them being an element of $S$. Therefore $P(x)$ must be bigger than $0$,
yielding a contradiction. ∎

######  Lemma V.2.

The following equation states an alternative definition of the set containing
all sets of separation-nodes.

$\mathcal{S}=\left\\{\bigcup_{\begin{subarray}{c}v_{i}\in V\\\
x_{i}=0\end{subarray}}v_{i}\mid P(x)=0\right\\}$ (13)

###### Proof.

Using lemma V.1 to show “$\supseteq$”, we now show “$\subseteq$”. Let
$S\in\mathcal{S}$ be an arbitrary separation-node set and $x$ the
corresponding binary vector $0$-flagging the nodes belonging to $S$. Assuming
$P(x)\neq 0$, at least two adjacent nodes $v_{i},v_{j}\in V$ belonging to
different communities exist following the definition of $P$. These nodes
subsequently belong to the same connected component $\overline{S}_{i}$ of the
graph induced by $V\setminus S$ implicating that no community can exist, that
resembles a superset of the nodes inducing the connected component
$\overline{S}_{i}$. Therefore $S$ can not be a set of separation-nodes as the
corresponding refinement map can not exist, yielding a contradiction and
showing $P(x)=0$. ∎

######  Lemma V.3.

For every $S\subset V$ satisfying $P(x)>0$, there exists a superset
$\tilde{S}\supset S$ such that $\tilde{x}^{T}Q\tilde{x}<x^{T}Qx$, with $Q$
defined such that $x^{T}Qx=2P(x)-\sum_{v_{i}\in V}x_{i}$ and $\tilde{x}$
corresponding to $\tilde{S}$.

###### Proof.

Let $S\subset V$ be a set of nodes such that the corresponding penalty term
$P(x)$ is bigger than zero. This implicates the existence of a pair of
incident nodes $v,w\in V$ being part of the same community while neither $v\in
S$ nor $w\in S$. Then the set $\tilde{S}:=S\cup\left\\{v\right\\}$ (without
loss of generality, we could also define $\tilde{S}:=S\cup\left\\{w\right\\}$
while achieving the same) has a smaller QUBO-value compared to $S$: With a
decrement of at least $4$ in the the penalty term (i.e., taking its weighting
of $2$ into account) and an increment in the cost function (i.e., the sum of
the $x_{i}$’s) of $1$, we get $\tilde{x}^{T}Q\tilde{x}\leq x^{T}Qx-1$,
completing the proof. ∎

######  Corollary V.0.1.

$x=\operatorname*{arg\,min}_{x\in\left\\{0,1\right\\}^{\left|V\right|}}2P(x)-\sum_{v_{i}\in
V}x_{i}\Rightarrow P(x)=0$.

###### Proof.

This result follows directly from application of lemma V.3, as $P(x)\neq 0$
would violate the minimality property of $x$. ∎

With these lemmata, we are now ready to prove theorem III.1:

###### Proof.

Let $Q\in\mathbb{R}^{\left|V\right|\times\left|V\right|}$ be defined such
that:

$x^{T}Qx=2P(x)-\sum_{v_{i}\in V}x_{i}$ (14)

We start by proving “$\subseteq$”: Let $S\in\mathcal{S}_{min}$ and $x$ its
corresponding $0$-flag vector, then we know by corollary V.0.1, that $P(x)=0$.
Therefore
$x^{T}Qx=\left|S\right|-\left|V\right|=\vcentcolon\overline{s_{min}}$. It is
sufficient to show, that
$\overline{s_{min}}=\min_{x\in\left\\{0,1\right\\}^{\left|V\right|}}-\sum_{v_{i}\in
V}x_{i}+2P(x)$. For this, we assume, that there exists an $\widetilde{x}$ such
that $\widetilde{x}^{T}Q\widetilde{x}<\overline{s_{min}}$. Now, as
$P\rightarrow\mathbb{N}_{0}$ two possibilities exist:

  1. 1.

$P(\widetilde{x})=0$ and the separation-node set $\widetilde{S}$ is smaller
than $S$.

  2. 2.

$P(\widetilde{x})>0$ and the separation-node set $\widetilde{S}$ is much
smaller than $S$.

As we can see using lemma V.3, we can reduce the latter case to the former
case by iteratively eradicating all penalties. Now, using corollary V.0.1,
$\widetilde{S}$ is a separation-node set and by definition of $\widetilde{S}$,
$\left|\widetilde{S}\right|<s$ yielding a contradiction to the minimality of
$\mathcal{S}_{min}$ and thereby proving “$\subseteq$”.

We now prove “$\supseteq$”: Let
$x^{*}\vcentcolon=\operatorname*{arg\,min}_{x\in\left\\{0,1\right\\}^{\left|V\right|}}2P(x)-\sum_{v_{i}\in
V}x_{i}$ and let $S^{*}$ be the node set corresponding to $x^{*}$. As we can
see using lemma V.3, $P(x^{*})$ must be zero, otherwise $x^{*}$ could not be
minimal in the sense of satisfying its definition. Therefore, $S^{*}$ is a
separation-node set according to lemma 13. Assuming
$S^{*}\notin\mathcal{S}_{min}$ yields $\left|S^{*}\right|\neq\left|S\right|$,
for an arbitrary $S\in\mathcal{S}_{min}$ and thus two cases are possible:

  1. 1.

$\left|S^{*}\right|<\left|S\right|$.

  2. 2.

$\left|S^{*}\right|>\left|S\right|$.

The former yields a contradiction to $\mathcal{S}_{min}$ being minimal and the
latter yields a contradiction to the minimality of $x^{*}$. ∎

###  V-B Constructing penalty terms for the in- and surjectivity constraints

In this section, we formulate penalty terms realizing the in- and surjectivity
constraints for separation-node sets. Instead of solving this seemingly non-
straightforward task directly, we will realize the individual constraints with
terms, that are larger than $0$ iff the constraint is satisfied and $0$
otherwise. Exploiting the possibilities of PUBO, we will show that the
respective terms can be used to build penalty functions using a moderate
amount of ancillary variables.

######  Lemma V.4.

The separation-node set associated with the $0$-flag vector
$x\in\left\\{0,1\right\\}^{\left|V\right|}$ is surjective iff $\sum_{v_{j}\in
V}\delta_{c(v_{i})c(v_{j})}x_{j}>0$ for all $v_{i}\in V$.

###### Proof.

This equivalence can be trivially observed by closely inspecting the sum and
is left as an exercise to the reader. ∎

As the heuristic approaches presented in this work only allow for the
estimation of $\delta_{c(v_{i})c(v_{j})}$ for adjacent node pairs
$\left(v_{i},v_{j}\right)\in E$, no direct estimation for
$\delta_{c(v_{i})c(v_{j})}$ seems accessible. However, we can use the
estimation of $\delta_{c(v_{i})c(v_{j})}$ for adjacent node pairs, to estimate
$\delta_{c(v_{i})c(v_{j})}$ for non-adjacent node pairs:

$\delta_{c(v_{i})c(v_{j})}=\text{sgn }\sum_{\overline{p}\in
p(v_{i},v_{j})}\prod_{k=1}^{dim(\overline{p})-1}\delta_{c(\overline{p}_{k})c(\overline{p}_{k+1})}$
(15)

Here, $p(v_{i},v_{j})$ denotes a function, that returns the set of all simple
paths $(v_{\pi(1)},...,v_{\pi(l)})$ between $v_{i}$ and $v_{j}$. To allow for
this convenient notation, we introduced
$\pi:V\rightarrow\left\\{1,...,\left|V\right|\right\\}$ as the projection,
mapping the indices of the path entries of the elements of $p(v_{i},v_{j})$ to
their global indices from $\\{v_{1},...,v_{n}\\}\in V$. In practice, these
paths could be found using techniques presented in [48].

The value inside sign function resembles the number of simple, intracommunity
paths between $v_{i}$ and $v_{j}$. A general upper bound for the number of
paths with these properties is $2^{\left|V\right|-2}$, i.e., the number of all
subsets of $V$ containing $v_{i}$ and $v_{j}$. For practical purposes, this
term clearly is unsuitable, as small errors in the estimation of
$\delta_{c(v_{i})c(v_{j})}$ add up very quickly. Neglecting applicability
concerns for reasons described in III-A, we now show how to build a PUBO
penalty function associated to the surjectivity term used in lemma V.4.

######  Lemma V.5.

Given a function
$f:\left\\{0,1\right\\}^{n}\rightarrow\left\\{0,...,m\right\\}$ for arbitrary
$n,m\in\mathbb{N}$ representing a constraint via $f(x)>0$, the following
penalty terms can be used to ensure that $f(x)>0$ in PUBO:

$\displaystyle\begin{split}P_{1}(x,y)\vcentcolon=&\left(f(x)-\sum_{i=0}^{\left\lceil\log_{2}(m)\right\rceil}2^{i}y_{i}\right)^{2}\\\
=&\begin{cases}0&\text{if
$\mathrm{y}\vcentcolon=\displaystyle\sum_{i=0}^{\left\lceil\log_{2}(m)\right\rceil}2^{i}y_{i}=f(x)$}\\\
>0&\text{otherwise.}\end{cases}\end{split}$ (16)
$\displaystyle\begin{split}P_{2}(y)\vcentcolon=&\prod_{i=0}^{\left\lceil\log_{2}(m)\right\rceil}\left(1-y_{i}\right)\\\
=&\begin{cases}1&\text{if $\mathrm{y}=0$}\\\ 0&\text{otherwise, i.e.,
$\mathrm{y}>0$.}\end{cases}\end{split}$ (17)

###### Proof.

Clearly, $min_{x,y}P_{1}(x,y)+P_{2}(y)=0$ $\iff$ $f(x)>0$ and thus
$P_{1}(x,y)+P_{2}(y)>0$ $\iff$ $f(x)=0$. ∎

When denoting the surjectivity constraint from lemma V.4 as $f(x)$, we can
see, that $f(x)<\left|V\right|$ for every $v_{i}\in V$. Therefore, we can use
lemma V.5 to formulate a penalty term for the surjectivity constraint at the
expense of at most $\left|V\right|\lceil\log_{2}\left|V\right|\rceil$
ancillary qubits.

With these results, we are now ready to formulate the following PUBO penalty
term for injectivity.

######  Lemma V.6.

$\overline{\sigma}_{ij}(x)$ is positive for every $v_{i}\in V$ and $v_{j}\in
c(v_{i})\setminus\left\\{v_{i}\right\\}$ not contained in the separation-node
set iff the separation-node set associated with the $0$-flag vector
$x\in\left\\{0,1\right\\}^{\left|V\right|}$ is injective, and $0$, otherwise.

$\overline{\sigma}_{ij}(x)\vcentcolon=\sum_{\overline{p}\in
p(v_{i},v_{j})}\prod_{k=1}^{dim(\overline{p})-1}\delta_{c(\overline{p}_{k})c(\overline{p}_{k+1})}x_{\pi(\overline{p}_{k})}x_{\pi(\overline{p}_{k+1})}$
(18)

###### Proof.

Here, $\overline{\sigma}_{ij}(x)$ is positive, iff a simple path
$\overline{p}\in p(v_{i},v_{j})$ between $v_{i}$ and $v_{j}$ exists, that
consists exclusively of nodes assigned to the community of $v_{i}$ which are
not part of the separation-node set, and $0$, otherwise. ∎

Analogously to lemma V.4, we can observe, that $\overline{\sigma}_{ij}(x)\leq
2^{\left|V\right|-2}$. Thus, we can use lemma V.5 at the expense of less than
of $\lceil\log_{2}\left|V\right|\rceil$ ancillary qubits for every single node
pair $v_{i}\in V$ and $v_{j}\in c(v_{i})\setminus\left\\{v_{i}\right\\}$. As
injectivity demands the positiveness of $\overline{\sigma}_{ij}(x)$ for all
node pairs $v_{i}\in V$ and $v_{j}\in
c(v_{i})\setminus\left\\{v_{i}\right\\}$,
$\left|V\right|^{2}\lceil\log_{2}\left|V\right|\rceil$ ancillary qubits
suffice to construct a penalty term for injectivity. The selection of
appropriate node pairs $v_{i}\in V$ and $v_{j}\in
c(v_{i})\setminus\left\\{v_{i}\right\\}$ can be done using the term
$x_{i}x_{j}\delta_{c(v_{i})c(v_{j})}$.