1]QuSoft & CWI, Amsterdam, the Netherlands.

# Quantum Motif Clustering

Chris Cade  Farrokh Labib  Ido Niesen  [

###### Abstract

We present three quantum algorithms for clustering graphs based on higher-
order patterns, known as motif clustering. One uses a straightforward
application of Grover search, the other two make use of quantum approximate
counting, and all of them obtain square-root like speedups over the fastest
classical algorithms in various settings. In order to use approximate counting
in the context of clustering, we show that for general weighted graphs the
performance of spectral clustering is mostly left unchanged by the presence of
constant (relative) errors on the edge weights. Finally, we extend the
original analysis of motif clustering in order to better understand the role
of multiple ‘anchor nodes’ in motifs and the types of relationships that this
method of clustering can and cannot capture.

##  1 Introduction

The study of complex networks has impacted many fields of science Str (01),
including biology Alb (05); SOMMA (02), sociology WF (94), neuroscience BS
(17), and finance AOTS (15); GK (10). In particular, it is commonplace to
study the connectivity patterns of networks at the edge and vertex level in
order to uncover important structures in the underlying data. One method that
provides insight into the connectivity structure of a network is graph
clustering, which entails finding groups of highly connected vertices in order
to uncover underlying community structures. There are many efficient
(heuristic) algorithms for graph clustering, including the theoretically well-
motivated _k-means spectral clustering_ 111See vL (07) for a historical
overview and list of references.. Here, given an integer $k$, the eigenvectors
corresponding to the smallest $k$ eigenvalues of the graph Laplacian are used
as a feature set for a $k$-means clustering algorithm. It has been shown that
in certain circumstances spectral clustering leads to the discovery of
_optimal_ graph partitions PSZ (15).

Recently, it is becoming popular to study more sophisticated connectivity
patterns. This can be done in the context of, for example,
hypergraphs222www.quantamagazine.org/how-big-data-carried-graph-theory-into-
new-dimensions-20210819/ that can express multiple-vertex relationships, or
via small subgraphs, also known as _motifs_ , which can be used to study
higher-order connectivity patterns between vertices. The latter has become a
useful tool for providing deeper insight into a network’s function and
structure, although often the detection of these motifs remains
computationally challenging MNSK (12).

In BGL (16), Benson et al. propose an algorithm for clustering a graph based
on its _motif connectivity_. Their algorithm, which makes use of spectral
clustering and therefore comes with theoretical guarantees PSZ (15), can be
used to uncover collections of vertices that are highly connected via
particular motifs, rather than just by edges as in the ordinary case. The
authors apply their technique to the well known _C. elegans_ neuronal network
and to a transportation reachability network, with a particular motif used for
each case, and find that the motif clustering reveals network organisation not
made apparent by clustering through edge-based connectivity alone.

As a motivating (toy) example, consider the graph shown in the middle of
Figure 1, which could for example represent a financial transaction network:
vertices corresponding to financial entities, and unweighted edges between
them denoting transactions (for example, of a value beyond a particular
threshold). Consider also the motif shown at the top of Figure 1, which
represents the situation wherein two entities, given by the _anchor nodes_
shown in dark red, trade indirectly through three intermediate entities
according with edge pattern of the motif. Suppose that we are interested in
clustering the nodes of the graph into groups that don’t trade with each other
directly, but instead do so only by means of intermediate nodes in accordance
to the structure given by the motif. The method of motif clustering achieves
precisely such a clustering.

As shown by BGL (16), obtaining a motif clustering of the original graph can
be done in two steps. First, we construct the _motif graph_ , displayed in the
bottom of Figure 1. This graph has the same vertex set as the original graph,
but a different edge set: any instance of the motif in the original graph
corresponds to an edge in the motif graph connecting the two anchor nodes of
the motif instance in question. All edges of the motif graph have integer
weights that correspond to the number of motif instances in the original graph
that have the two edge endpoints as anchor nodes. In the second step we use
$k$-means spectral clustering on the motif graph to obtain the required motif
clustering of the original graph.

Figure 1: Example of motif clustering. _Top_ : The motif, with anchor nodes in
dark red. _Middle_ : An example graph, instances of the motif are represented
by red edges, other edges are grey. _Bottom_ : The motif graph. All edges have
weight 1 except for a single weight-2 edge (bold). The motif clusters are
clear: one on the left, one on the right.

In this paper we present three quantum algorithms that can perform motif
clustering faster than the classical algorithm presented in BGL (16). The
majority of the quantum speedup comes from faster finding and/or counting of
motifs in the graph, a task that is often computationally demanding. Our
speedups are of the Grover variety: at most quadratic, and sometimes less,
depending on the choice of motif and the sparsity of the graph. Our reason for
presenting several quantum algorithms is that we have a choice between using
Grover search or quantum approximate counting, as well as the option of
constructing the motif graph in its entirety, or only giving query access to
it. Depending on the input graph, one will be favorable over the other. We
should add that, as argued in BMN+ (21), for quantum algorithms based on
Grover-type speedups to become practically interesting, substantial
improvement in qubit counts, physical gate errors and/or error correction
schemes are required.

We also prove some technical lemmas related to performing spectral clustering
in the presence of errors on the weights of the edges of a graph – this is the
case in our application when the number of motifs connecting two vertices is
estimated using quantum approximate counting – which might be of independent
interest. Along the way, we give a simple ‘no-go’ argument to show that
spectral clustering with errors on _normalized_ Laplacians does not come with
the same guarantees as in the unnormalized case, but nevertheless, numerical
experiments suggest that it still performs well in practice. An interesting
open question is whether we can turn this empirical observation into a
theoretical one.

Finally, in the Appendix we discuss the role of anchor nodes in motifs,
extending the analysis of Benson et al. More specifically, we argue that motif
clustering should be used only for two-anchor node motifs, which express
pairwise relationships between vertices. If, instead, we want to cluster using
relationships between more than two vertices – which is what motifs with more
than two anchor nodes attempt to capture – we should do so within the context
of hypergraphs rather than that of motif clustering.

##### Organisation

After introducing some notation in Section 2, we begin by explaining the
concept of motif clustering and discuss previous work in the (classical)
literature in Section 3. Following this, we summarise our main results in
Section 4. Section 5 describes a classical algorithm for motif clustering, and
introduces the notation that we use throughout the rest of the paper. In
Section 6 we introduce our quantum tools and use those to construct our three
quantum algorithms: one based on Grover search, the other two on quantum
approximate counting. Finally, in Section 7 we consider the effect of quantum
approximate counting, both analytically and numerically, on the guarantees
that come with spectral clustering. In the Appendix we discuss in detail the
role of anchor nodes in motifs.

##  2 Preliminaries

Before we discuss the concept of motif clustering, we first introduce some
notation. In addition, when comparing how well our quantum algorithms perform
relative to their classical counterparts, we want to be able to talk about
their run-times. In the section below, we make precise what we mean with run-
time.

###  2.1 Notation

For an integer $k\geq 1$, we write $[k]:=\\{1,\dots,k\\}$. For a set $W$, we
denote its size by $|W|$. We write $G=(V,E)$ for a directed graph with vertex
set $V$ and edge set $E$, where $n=|V|$ denotes the number of vertices, and
$m=|E|$ the number of edges, and assume a fixed ordering of the vertices in
$V$ that allows for a natural identification of $V$ with $[n]$.

For $v\in V$, we define $d_{v}$ to be the degree of $v$ and $d:=\max_{v\in
V}d_{v}$ the maximum degree of any vertex in the graph. We use $A$ to denote
the adjacency matrix of the graph, and for each vertex $v$ assume that we know
$d_{v}$ and that we have query access to the weighted adjacency list
$J_{v}:[d_{v}]\rightarrow[n]\times\mathbb{R}_{\geq 0}$, which is a function
that assigns labels and weights to the neighbours of $v$. We will call such
access ‘adjacency list access’ to $G$. For a subset $W\subset V$, we write
$\overline{W}$ for the complement, i.e. $\overline{W}=V\setminus W$. A
$k$-_partition_ of $V$ is a collection of pairwise disjoint subsets
$W_{1},\dots,W_{k}\subset V$ such that $V=\cup_{i\in[k]}W_{i}$.

We will often consider the Laplacian $L$ of an $n$-vertex graph $G$, and its
normalized equivalent, the normalized Laplacian $\tilde{L}$. Let $D$ be the
diagonal $n\times n$ matrix of (weighted) vertex degrees in $G$, and $A$ the
adjacency matrix. Then the Laplacian is defined as $L:=D-A$, and the
normalized Laplacian as
$\tilde{L}:=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$
(which is only defined for graphs for which every vertex has a positive
degree).

Finally, given any $n\times n$ real symmetric matrix, such as the graph
Laplacian, we assume that the eigenvalues
$\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ are ordered by
increasing value and denote by
$\mathbf{v}_{1},\mathbf{v}_{2},\dots,\mathbf{v}_{n}$ the corresponding
eigenvectors, which we assume to be normalized. In particular, when we mention
the ‘first $k$ eigenvectors’ of a matrix, we are referring to the eigenvectors
corresponding to the smallest $k$ eigenvalues. For graph Laplacians, which are
positive semi-definite, the smallest eigenvalues will be those closest to
zero.

###  2.2 Query and time complexity

All our quantum algorithms assume coherent access to the input graph in the
form of quantum queries to the adjacency lists. More explicitly, given the
maps $\\{J_{v}:v\in V\\}$ introduced above, coherent access to the adjacency
lists means that we have access to the following unitary

$\ket{v}\ket{i}\ket{0}\mapsto\ket{v}\ket{i}\ket{J_{v}(i)}\,,$ (1)

and its inverse, where $v\in V$, $i\in[d]$ and $\ket{J_{v}(i)}$ contains two
registers, one for the label of $i$-th neighbor of $v$, and one for the weight
of the edge. When we talk about the _query complexity_ of an algorithm, we
mean the number of times the algorithm applies the unitary in Eq. (1). If the
adjacency lists are sorted (according to some ordering of the vertices in
$V$), then the only type of access to the input graph our algorithms require
is this333Except when we also make use of the quantum graph sparsification
algorithm by Apers and de Wolf AdW (20), which requires QRAM – see Section 4
for details..

If we are not provided with coherent access to the adjacency lists, or they
are not sorted, then we must provide our own (perhaps sorted) coherent access,
which will require classically writing to a QRAM, using at most $O(nd)$
operations. We note that since the run-times of our quantum algorithms are
larger than $O(nd)$, our speedups persist even if we pay this cost up front.

Finally, by the _run-time_ of a quantum algorithm we mean the total number of
elementary gates, QRAM writes, and queries made by the algorithm. Our
definition of run-time is the same as that of Apers and de Wolf AdW (20).

##  3 Motif clustering

The idea behind motif clustering is to partition the vertices of a graph into
several clusters based on a higher-order structural pattern, called a _motif_.
The partitions obtained through motif clustering should be such that any two
vertices within a particular cluster are part of relatively many connected
occurrences of the motif in the graph, whereas two vertices in different
clusters should participate in relatively few connected motif occurrences.
This statement will be made precise below. An example of motif clustering for
a particular motif is shown in Figure 1.

In this section, which is based on the content of Benson et al. BGL (16), we
set the stage by introducing the reader to the necessary concepts and
definitions that we use throughout the paper.

###  3.1 Graph motifs

A motif $M=(V_{M},E_{M},V_{A})$ of size $s$ is a connected, unweighted graph
with $s$-sized vertex set $V_{M}$, and edge set $E_{M}$. Throughout this paper
we assume that $s$ is a constant. The motif comes with a set of _anchor nodes_
$V_{A}\subseteq V_{M}$, which will become relevant when we discuss motif cuts.

Given a particular motif $M$ and an unweighted graph $G=(V,E)$, we will be
interested in occurrences of the motif $M$ in $G$, which can be _functional_
or _structural_ SK (04). Formally, a _motif assignment_ is an injective map
$\iota:V_{M}\rightarrow V$. For functional motifs, we require that
$(\iota(v),\iota(w))\in E$ if $(v,w)\in E_{M}$ for every $v,w\in V_{M}$. That
is, any two vertices in $\iota(V_{M})$ should have an edge in $G$ whenever the
corresponding vertices in the motif have one, but there can be additional
edges in $G$ not present in the motif itself. For structural motifs, we have
that $(\iota(v),\iota(w))\in E$ if _and only if_ $(v,w)\in E_{M}$ for all
$v,w\in V_{M}$, and therefore the motif is graph-isomorphic to $\iota(V_{M})$
(i.e. both the edges _and_ non-edges coincide).

Because we are interested in the motif occurring in $G$ as a pattern
irrespective of the actual vertex assignment given by the mapping $\iota$, we
next define an equivalence relation on the set of motif assignments. Two motif
assignments $\iota$ and $\iota^{\prime}$ are considered equivalent if
$\iota(V_{M})=\iota^{\prime}(V_{M})$ as sets and also
$\iota(V_{A})=\iota^{\prime}(V_{A})$ as sets. A single equivalence class is
called a _motif instance_. We write $\mathcal{I}=\mathcal{I}(G,M)$ for the set
of all motif instances of $M$ in $G$. Moreover, we say that a motif instance
has a vertex $u\in V$ as an anchor node if, for any assignment $\iota$ in the
equivalence class of the instance, $u\in\iota(V_{A})$. Note that this
definition is well-defined, as it does not depend on the choice of assignment
$\iota$. In Appendix A, we further elaborate on when two motif assignments are
equivalent, and how this equivalence is related to symmetries of the motif
itself.

Note that, motif clustering can be applied to both directed and undirected
(but unweighted) graphs. When the graph is (un)directed, the motif should also
be (un)directed for motif instances to exist within the graph.

Following BGL (16), we focus on structural motifs in this work. Note that a
functional motif can be thought of as a combination of several structural
motifs444A functional motif only specifies the edges that are present in the
motif. For all other (unspecified) edges, we define a structural motif for
every possible assignment of either edge or non-edge to the set of edges
unspecified by the functional motif.. Since the framework introduced by Benson
et al. BGL (16) can be extended to consider several motifs simultaneously –
see Appendix D.1, and the same extensions work for our framework, we also
capture the case of functional motifs.

###  3.2 Motif cuts

A common method for clustering graphs is to find minimal normalized cuts. This
corresponds to finding a partition of the vertex set that minimizes the total
weight of the cuts (edges connecting different partitions) whilst maximizing
the volumes or sizes of the partitions. The number of partitions (often
denoted $k$) is fixed in advance. Motif clustering works analogously, in the
sense that it minimizes the number of _motif cuts_ whilst maximizing the
_motif volume_ or partition size.

More formally, let $W\subset V$ be a subset of vertices in the graph. An
ordinary graph cut with respect to $W$ and its complement $\bar{W}$ is given
by the number of edges that have one endpoint in $W$ and the other in
$\bar{W}$. Similarly, we _could_ define a motif cut with respect to $W$ and
$\bar{W}$ to be the number of motif instances that have one or more vertices
in $W$ and one or more vertices in $\bar{W}$. However, following BGL (16), we
want to incorporate the idea that each individual motif instance signifies a
mutual relationship between a specific subset of vertices of the motif, called
_anchor nodes_. As such, given a motif $M$, a _motif cut_ in $G$ with respect
to $W$ and its complement $\bar{W}$, denoted by $\text{cut}_{(G,M)}(W)$, is
defined to be the number of motif instances that have at least one anchor node
in both $W$ and $\bar{W}$:

$\text{cut}_{(G,M)}(W):=\left|\\{\iota\in\mathcal{I}|(W\cap\iota(V_{A})\neq\emptyset)\land(\bar{W}\cap\iota(V_{A})\neq\emptyset)\\}\right|\,.$
(2)

Moreover, analogous to the ordinary volume given by the sum of all degrees of
vertices in a given set, define the _motif volume_ $\text{vol}_{(G,M)}(W)$ of
$W$ to be the number of anchor nodes in motif instances that appear in $W$:

$\operatorname{vol}_{(G,M)}(W):=\sum_{\iota\in\mathcal{I}}\left|W\cap\iota(V_{A})\right|\,.$
(3)

Given the notions of motif cut and motif volume, the _motif conductance_ and
the _motif ratio cut_ of the set $W$ are given by555Graph conductance is
usually defined with
$\text{min}\left(\text{vol}_{(G,M)}(W),\text{vol}_{(G,M)}(\bar{W})\right)$ in
the denominator. However, when considering more general partitions of the
graph in possibly more than two sets, such as arbitrary $k$-partitions, we
divide by $\text{vol}_{(G,M)}(W)$ instead: see definitions of Ncut in vL (07)
and the related $k$-way expansion constant in PSZ (15).

$\phi_{(G,M)}(W):=\frac{\text{cut}_{(G,M)}(W)}{\text{vol}_{(G,M)}(W)}\qquad\text{and}\qquad\text{RatioCut}_{(G,M)}(W):=\frac{\text{cut}_{(G,M)}(W)}{|W|}$
(4)

respectively, where we define $\phi_{(G,M)}(W)=0$ and
$\text{RatioCut}_{(G,M)}(W)=0$ when $\text{cut}_{(G,M)}(W)=0$.

Given some integer $k\in\mathbb{N}$ chosen in advance, we can also define the
conductance and ratio cut relative to a $k$-partition $W_{1},\ldots,W_{k}$.
The _motif conductance_ and _motif ratio cut_ of the partition
$\\{W_{i}\\}_{i=1}^{k}$ of $V$ are given by

$\displaystyle\phi_{(G,M)}(W_{1},\ldots,W_{k}):=\sum_{i=1}^{k}\phi_{(G,M)}(W_{i})\qquad\text{and}$
$\displaystyle\operatorname{RatioCut}_{(G,M)}(W_{1},\ldots,W_{k}):=\sum_{i=1}^{k}\operatorname{RatioCut}_{(G,M)}(W_{i})$

respectively.

The goal of motif spectral clustering, for a fixed $k\in\mathbb{N}$ chosen in
advance, is to find a partition $\\{W_{i}\\}_{i=1}^{k}$ that minimizes
$\phi_{(G,M)}(W_{1},\ldots,W_{k})$ or
$\operatorname{RatioCut}_{(G,M)}(W_{1},\ldots,W_{k})$: this will result in a
partitioning of the graph into ($k$) clusters of vertices that are highly
connected via the target motif, whilst very few motifs connect vertices in
different clusters. It turns out that, for motifs with two or three anchor
nodes, one can translate the two minimization problems above to the problems
of ordinary conductance or ratio cut minimization of an auxiliary, weighted
graph, called the _motif graph_ BGL (16) which we introduce in the next
section.

###  3.3 The motif graph

Benson et al. BGL (16) show that for motifs with two or three anchor nodes,
minimizing $\phi_{(G,M)}(W_{1},\ldots,W_{k})$ is equivalent to minimizing the
ordinary conductance on a weighted graph
$\mathpzc{G}=(V,\mathpzc{E},\mathpzc{A})$ that can be constructed from the
graph $G$, which we term the _motif graph_ of $G$ given motif $M$. The graph
$\mathpzc{G}$ has the same vertex set666For practical details regarding
entirely disconnected vertices aside, see Section 5.2.3. as $G$, but in
general a different set of edges, which are now integer weighted. Also,
whereas both $G$ and $M$ can be directed, $\mathpzc{G}$ is always an
undirected graph. For notation we will use ordinary characters $G$, $V$, $E$,
etc. when referring to the original graph $G$, and calligraphic characters
$\mathpzc{G}$, $\mathpzc{E}$, etc. to refer to the motif graph $\mathpzc{G}$.

Given $G$ and $M$, the edge set $\mathpzc{E}$ of $\mathpzc{G}$ is given by
$\mathpzc{E}=\\{(v,w)\in V\times
V|\exists\,\iota\in\mathcal{I}:\\{v,w\\}\subseteq\iota(V_{A})\\}$, i.e. two
vertices $u,v\in V$ are connected by an edge in $\mathpzc{G}$ if they are both
anchor nodes of a motif instance $\iota\in\mathcal{I}$ of $G$. The motif
weighted adjacency matrix $\mathpzc{A}$ of $\mathpzc{G}$ has integer
coefficients given by

$\mathpzc{A}_{uv}=\left|\\{\iota\in\mathcal{I}\mid\\{u,v\\}\subseteq\iota(V_{A})\\}\right|\,,$

i.e. $\mathpzc{A}_{uv}$ is equal to the number of motif instances in $G$ that
contain both $u$ and $v$ as anchor nodes. For $u\in V$, we define the _motif
degree_ $\mathpzc{d}_{u}$ of $u$ to be the total number of edges in
$\mathpzc{G}$ connected to $u$,

$\mathpzc{d}_{u}:=|\\{v\in V:\mathpzc{A}_{uv}>0\\}|,$

and the _motif strength_ $\mathpzc{s}_{u}$ to be the sum of all weights of
edges connected to $u$:

$\mathpzc{s}_{u}:=\sum_{v\in V}\mathpzc{A}_{uv}.$

Given $W\subset V$, $W\neq\emptyset$ let

$\operatorname{vol}_{\mathpzc{G}}(W):=\sum_{u\in W}\mathpzc{s}_{u}$

be the volume of $W$ in $\mathpzc{G}$, and

$\operatorname{cut}_{\mathpzc{G}}(W):=\sum_{u\in
W,v\in\bar{W}}\mathpzc{A}_{uv}$

the cut induced by $W$ in $\mathpzc{G}$. The conductance of and ratio cut of
$W$ in $\mathpzc{G}$ are given by

$\phi_{\mathpzc{G}}(W):=\frac{\text{cut}_{\mathpzc{G}}(W)}{\operatorname{vol}_{\mathpzc{G}}(W)}\qquad\text{and}\qquad\operatorname{RatioCut}_{\mathpzc{G}}(W):=\frac{\operatorname{cut}_{\mathpzc{G}}(W)}{|W|}\,,$

respectively. Finally, for a $k$-partition $W_{1},\ldots,W_{k}$ of $V$ with
$W_{k}\neq\emptyset\forall k$, we define

$\phi_{\mathpzc{G}}(W_{1},\ldots,W_{k}):=\sum_{i=1}^{k}\phi_{\mathpzc{G}}(W_{i}),$

and

$\operatorname{RatioCut}_{\mathpzc{G}}(W_{1},\ldots,W_{k}):=\sum_{i=1}^{k}\operatorname{RatioCut}_{\mathpzc{G}}(W_{i})$

for the conductance and ratio cut of the partition in $\mathpzc{G}$.

Benson et al. prove the following results relating motif conductances and
volumes in $G$ to ordinary conductances and volumes in $\mathpzc{G}$:

######  Lemma 1 (BGL (16)).

Let $G=(V,E)$ be an unweighted graph, $M=(V_{M},E_{M},V_{A})$ a motif with
$|V_{A}|\geq 2$ anchor nodes777Note that one-anchor node motifs cannot be used
for clustering, so the assumption that $|V_{A}|\geq 2$ is no restriction in
practice., $\mathpzc{G}$ the motif graph constructed from $G$ and $M$, and
$W\subset V$. Then

$\operatorname{vol}_{(G,M)}(W)=\frac{1}{|V_{A}|-1}\operatorname{vol}_{\mathpzc{G}}(W).$

Moreover, if $|V_{A}|\in\\{2,3\\}$, then

$\operatorname{cut}_{(G,M)}(W)=c\,\operatorname{cut}_{\mathpzc{G}}(W),$

where the constant $c=1$ if $|V_{A}|=2$, and $c=\frac{1}{2}$ if $|V_{A}|=3$.

The proof for $|V_{A}|=2$ is not given in BGL (16), but it can be proven in
exactly the same way as the proof for the $|V_{A}|=3$ case, see Appendix B for
details. Why the second equation above only holds for motifs with two or three
anchor nodes is discussed extensively in Appendix D.

For $k\in\mathbb{N}$, write $\mathcal{P}_{k}(V)$ for the set of all
$k$-partitions of $V$. The following corollary is immediate from Lemma 1.

######  Corollary 1 (BGL (16)).

Let $G=(V,E)$ be an unweighted graph, $M=(V_{M},E_{M},V_{A})$ a motif with
$|V_{A}|\in\\{2,3\\}$ anchor nodes and $\mathpzc{G}$ the motif graph
constructed from $G$ and $M$. Then, for every subset $W\subset V$, we have

$\phi_{(G,M)}(W)=\phi_{\mathpzc{G}}(W),$

and

$\operatorname{RatioCut}_{(G,M)}(W)=c_{R}\,\operatorname{RatioCut}_{\mathpzc{G}}(W),$

where the constant $c_{R}=1$ if $|V_{A}|=2$, and $c_{R}=\frac{1}{2}$ if
$|V_{A}|=3$. Consequently,

$\operatorname*{arg\,min}_{\\{W_{i}\\}_{i=1}^{k}\in\mathcal{P}_{k}(V)}\phi_{(G,M)}(W_{1},\ldots,W_{k})=\operatorname*{arg\,min}_{\\{W_{i}\\}_{i=1}^{k}\in\mathcal{P}_{k}(V)}\phi_{\mathpzc{G}}(W_{1},\ldots,W_{k}),$

and

$\operatorname*{arg\,min}_{\\{W_{i}\\}_{i=1}^{k}\in\mathcal{P}_{k}(V)}\operatorname{RatioCut}_{(G,M)}(W_{1},\ldots,W_{k})=\operatorname*{arg\,min}_{\\{W_{i}\\}_{i=1}^{k}\in\mathcal{P}_{k}(V)}\operatorname{RatioCut}_{\mathpzc{G}}(W_{1},\ldots,W_{k}).$

In particular, for motifs with two or three anchor nodes, in order to find
partitions of $V$ that have small motif conductance or small motif ratio cut
in $G$, we can instead solve the equivalent problem of finding partitions of
$V$ that have small ordinary conductance or ratio cut in $\mathpzc{G}$
respectively.

In order to obtain a partition that (approximately) minimizes the conductance
or the ratio cut of $\mathpzc{G}$, BGL (16) uses $k$-means spectral clustering
on the motif graph $\mathpzc{G}$. We will describe how to do this in detail in
Section 5. Thereafter, we will discuss how we can improve the classical
algorithm using quantum algorithmic methods in Section 6. We begin by first
stating our results in Section 4.

##  4 Results

Searching for a motif in a graph is essentially an unstructured search
problem. As such, we can speed up the parts of the classical algorithm that
construct the motif graph by applying either Grover search or quantum
counting. Which approach will be faster will depend on the properties of the
input graph, and also affect what type of clustering we can employ. Using
Grover search we can construct the motif graph exactly, and then apply
spectral clustering to its unnormalized or normalized Laplacian while having
guarantees on its behaviour. Using quantum approximate counting, on the other
hand, can be faster than using Grover search but only approximately constructs
the motif graph. As we show in Section 7, in this case we only have guaranteed
behaviour when spectral clustering is applied to the unnormalized Laplacian.
Moreover, rather than pre-compute the entire motif graph $\mathpzc{G}$, for
instance by explicitly writing down the motif adjacency matrix or motif
adjacency lists, in some cases it can be more efficient to provide query
access to it via some subroutine.

Taking the above considerations into account, we present below three quantum
algorithms for motif spectral clustering that give speedups over the best
classical algorithm in various situations. The complexities of the (quantum
and classical) algorithms considered in this work are dominated by the time
required to compute the edges and weights of the motif graph. The first two of
our quantum algorithms focus on constructing the entire motif graph before
applying some classical or quantum algorithm for spectral clustering; the
third provides query access to the motif graph’s adjacency lists, and then
uses a fast quantum spectral clustering algorithm based on quantum graph
sparsification by Apers and de Wolf AdW (20).

##### Input graph

Let $G=(V,E)$ be the input graph that we want to cluster according to some
$s$-vertex motif $M$. Since $s=2$ corresponds to an edge, without loss of
generality we can and will assume throughout the rest of the paper that $s\geq
3$. We write $n=|V|$ for the number of vertices of $G$ and $d$ for the maximum
degree (which can be $n$). We assume that we have adjacency list access to
$G$. In addition, we will only consider constant-sized motifs, meaning that
$s$ is independent of $n$.

For the first quantum algorithm presented below, the run-time depends on
whether the adjacency lists of the input graph are sorted (according to some
chosen ordering of all vertices in $V$) or not.888The assumption of sorted
adjacency lists is natural in the context of, for example, transaction
networks, which are initialized as empty lists, and kept sorted as new
transactions are added to the graph. For the other two, we can sort the
adjacency lists of the input graph beforehand without affecting their
(asymptotic) run-times, and then use the algorithms as described in Section 6,
which assume that access to the input graph is provided via sorted adjacency
lists.

Our quantum algorithms require coherent access to the input graph. If, rather
than coherent access, we are given classical access to the input graph, we
will first need to load the input graph into QRAM in time $O(nd)$. In
addition, sorting the adjacency lists takes time999The $\tilde{O}$ notation
hides poly-logarithmic factors in $n$. $\tilde{O}(nd)$. If we either have to
sort, load to QRAM, or both, we say that we need to _pre-process_ the input
graph. In Appendix C we discuss how pre-processing the input graph affects the
run-times of our algorithms.

###  4.1 Algorithms and their run-times

Below we provide the complexities for constructing the motif graph and
obtaining the $k$ eigenvectors corresponding to the smallest $k$ eigenvalues
of the motif graph Laplacian, where the latter are then used as input to
$k$-means clustering. $k$-means clustering itself is a heuristic algorithm,
with an exponential upper bound to its run-time, but in practice is usually
significantly faster than this. For ‘well-clusterable’ graphs, the $k$-means
part of the algorithm can be done in nearly-linear time PSZ (15). For
simplicity we will denote the time it takes to run $k$-means by
$T_{k\text{-}\mathrm{means}}$, and note that generally this will not be the
most expensive part of the algorithms.

##### Classical

The classical algorithm of BGL (16), which can also be used in combination
with the spectral estimation algorithm of ST (14), takes time
$\tilde{O}(nd^{s-1})$ to obtain the $k$-smallest eigenvectors of the
(optionally normalized) motif Laplacian, adding up to a total run-time of

$\tilde{O}(nd^{s-1}+T_{k\text{-}\mathrm{means}})\,$

for the entire $k$-means motif spectral clustering algorithm. This is
essentially101010Except for certain specific motifs that can be counted more
efficiently in some settings – see Section 5.1 for some examples. optimal for
any algorithm that makes use of the motif Laplacian, since to construct the
motif graph exactly one needs to have counted all motif instances in the
graph, which can be as large as $nd^{s-1}$, and hence counting these
classically requires $\Omega(nd^{s-1})$ queries to the input graph via
standard lower bounds on the query complexity of counting.

##### Quantum via Grover search

Our first quantum algorithm uses Grover search plus classical subroutines to
find all motif instances in the graph and compute the weights of the edges in
the motif graph _exactly_ , before applying the classical spectral clustering
based on the spectral estimation algorithm of ST (14).

######  Theorem 1 (Motif clustering via Grover search).

Given a graph $G$ with maximum degree $d$ and a motif $M$ of size $s$, there
exist quantum algorithms for _exact_ motif clustering under the following
conditions and with the following run-times:

  1. 1.

If we do not have coherent access to the input graph, then there is a quantum
algorithm for motif clustering with expected run-time

$\tilde{O}(nd+\sqrt{nd^{s-1}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})\,,$ (5)

where $\mathpzc{M}$ is the total number of motif instances in the graph $G$.

  2. 2.

If we have coherent access to the input graph, and the adjacency lists are
sorted, then there is an algorithm that takes time

$\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})\,$

in expectation.

  3. 3.

If the adjacency lists are not sorted, then they can be pre-sortedto yield a
quantum algorithm with the same run-time as given in Eq. (5). Otherwise, there
is a quantum algorithm with expected run-time

$\tilde{O}(\sqrt{nd^{s}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})\,.$

The run-times of Algorithms 1 and 2 above are analysed in Section 6.2. Given
coherent access to the input graph, which of Algorithms 2 or 3 to use depends
on $\mathpzc{M}$. The second is faster in case there are relatively few motif
instances $\mathpzc{M}$ in total, i.e. when
$\mathpzc{M}=o\left(\frac{n}{d^{s-2}}\right)$. If we lack any knowledge of a
non-trivial bound on $\mathpzc{M}$, the sensible choice is to first sort all
adjacency lists, since the algorithm so obtained is never slower than its
classical counterpart.

In general, the best upper bound we can put on $\mathpzc{M}$ is $nd^{s-1}$, in
which case the quantum algorithm runs in time $\tilde{O}(nd^{s-1})$ – no
better than classical. Hence, this algorithm provides a speedup whenever
$\mathpzc{M}=o(nd^{s-1})$; we later show that for scale-free networks, which
occur often in practice, this is indeed the case. The advantage of this
algorithm is that by constructing the motif graph exactly, it can be used to
perform spectral clustering using the eigenvectors of the ordinary as well as
the _normalized_ Laplacian — see Section 5 below for a detailed discussion on
the difference between clustering with the Laplacian or its normalized
counterpart.

##### Quantum via approximate counting and classical spectral clustering

Our second quantum algorithm uses quantum approximate counting to estimate the
weights of the motif graph, followed by a classical spectral clustering
routine. To perform spectral clustering using the eigenvectors of the
_unnormalized_ Laplacian, it is sufficient to approximate the entries of the
motif adjacency matrix up to constant multiplicative error, and then use the
spectral clustering algorithm based on the spectral estimation algorithm of ST
(14). We can also perform spectral clustering using the _normalized_
Laplacian, but in this case we lack the theoretical guarantees present in the
unnormalized case. However, our numerical simulations suggest that spectral
clustering with the normalized Laplacian on the approximate motif graph _does_
actually work in practice – see Section 6 for details. We prove the following
result in Section 6.3.

######  Theorem 2 (Motif clustering via quantum counting & classical
clustering).

Given a graph $G$ with maximum degree $d$ and a motif $M$ of size $s$, there
exists a quantum algorithm for approximate motif clustering that takes time

$\tilde{O}(nd^{l+\frac{s}{2}-1}+T_{k\text{-}\mathrm{means}})\,$

in expectation, where $l$ is the maximum distance between any two anchor nodes
in the motif.

Hence, we obtain a speedup over the classical algorithm whenever $l<s/2$. As a
simple example, consider the case of a triangle motif, so that $s=3$ and
$l=1$, and where the input graph is dense $(d=\Theta(n))$. The classical run-
time for motif clustering in this case is $O(n^{3})$, but the quantum run-time
is $\tilde{O}(n^{2.5})$.

Note that, in contrast, constructing the motif graph approximately doesn’t
generally help us in the classical case: if we were to estimate the weights of
the edges of the motif graph with constant relative error, then this would
take time $\tilde{O}(nd^{l+s-1})$, which already for $l=1$ is worse than even
the exact version described above. Hence, using approximate counting only buys
us something in the quantum case.

##### Quantum via approximate counting and quantum spectral clustering

It is sometimes more efficient to provide query access to the approximate
motif graph $\mathpzc{G}$ rather than to construct it explicitly beforehand.
We show the following in Section 6.3.3, by combining the quantum spectral
clustering algorithm of Apers and de Wolf AdW (20) with our algorithms for
approximately constructing the motif graph via quantum counting

######  Theorem 3 (Motif clustering via quantum counting & quantum
clustering).

Given a graph $G$ with maximum degree $d$ and a motif $M$ of size $s$, there
exists a quantum algorithm for approximate motif clustering that takes time

$\tilde{O}\left(\sqrt{n^{3}d^{s-2}}+T_{k\text{-}\mathrm{means}}\right)$

in expectation.

This run-time is independent of whether we have to pre-process the input graph
or not. Hence, whenever $d^{l}=\omega(\sqrt{n})$ (which is the case for, for
example, dense graphs), this algorithm is more efficient than the algorithm of
Theorem 2 above which constructs the approximate motif graph explicitly.

It should be noted that, if we choose to use this algorithm for motif
clustering, we can, generally speaking, only cluster using the unnormalized
Laplacian, because we lose the ability to filter out the vertices that become
disconnected in the motif graph – see Section 5.2.3 for a discussion on this
point.

##### Summary

In all of our quantum algorithms our speedups come primarily from faster
computation of the weights in the motif graph, and in one also from the
application of quantum spectral clustering via AdW (20). In the worst case the
speedup over the classical algorithm is minimal, but for many natural families
of graphs the speedup can be reasonably large (i.e. quadratic). In Table 1 we
summarize the (expected) complexities of the classical and our three quantum
algorithms for performing motif clustering on a general graph using an
arbitrary motif.

Algorithm | Expected run-time
---|---
Classical | $O(nd^{s-1}+T_{k\text{-}\mathrm{means}})$
Quantum-Grover (pre-process). Theorem 1 | $\tilde{O}(nd+\sqrt{nd^{s-1}\mathcal{M}}+T_{k\text{-}\mathrm{means}})$
Quantum-Grover (no pre-process) Theorem 1 | $\tilde{O}(\sqrt{nd^{s}\mathcal{M}}+T_{k\text{-}\mathrm{means}})$
Quantum-Approximate + classical cluster. Theorem 2 | $\tilde{O}(nd^{\frac{s}{2}+l-1}+T_{k\text{-}\mathrm{means}})$
Quantum-Approximate + quantum cluster. Theorem 3 | $\tilde{O}(\sqrt{n^{3}d^{s-2}}+T_{k\text{-}\mathrm{means}})$
Table 1: Expected run-times of the algorithms for motif clustering the input
graph $\mathpzc{G}$, where the motif is of size $s$, $n$ is the number of
vertices of $G$, $d$ is the maximum degree of $G$, and $\mathcal{M}$ is the
number of motif instances in $G$. If we are given coherent rather than
classical access to the input graph, then the run-time of Quantum-Grover is
$\tilde{O}(\sqrt{nd^{s-1}\mathcal{M}}+T_{k\text{-}\mathrm{means}})$ if the
adjacency lists are sorted, or
$\tilde{O}(\sqrt{nd^{s}\mathcal{M}}+T_{k\text{-}\mathrm{means}})$ if not,
where $T_{k\text{-}\mathrm{means}}$ denotes the time it takes to run
$k$-means.

Furthermore, we consider the complexity for power-law graphs, the latter being
a model of many naturally occurring graph families, such as social-networks
and internet graphs FFF (11). In particular, we find that, if we take the
motif to be a clique with two anchor nodes, the speedup becomes more
significant as the size of the motif grows. The corresponding run-time
complexities are given in Section 6.4.

###  4.2 Anchor nodes

Our algorithms for constructing the motif graph work for motifs with an
arbitrary number of anchor nodes111111The algorithms based on quantum
approximate counting assume the motif has two anchor nodes, but, as we show in
Appendix D.2, this is sufficient to be able to construct the motif graph for
motifs with an arbitrary number of anchor nodes.. However, as in the classical
case, clustering by means of the motif graph $\mathpzc{G}$ in order to obtain
a clustering that approximately minimizes motif conductance or motif ratio cut
in the original graph $G$ only works for motifs with two or three anchor
nodes.

In fact, in Appendix D, we argue that motif clustering by means of the motif
graph should only be used for motifs with two anchor nodes — or weighted
combinations thereof, to be made precise in Appendix D. The reason for this is
that the motif graph, being a graph itself, only captures pairwise
relationships between vertices, and a motif with two anchor nodes exactly
expresses a pairwise relationship between its anchor nodes.

Motifs with more than two anchor nodes attempt to capture relationships
between more than two vertices, and such relationships should be described by
a hypergraph instead. This statement seems incompatible with the fact that
Benson et al. perform motif clustering using the motif graph for three-anchor
node motifs. However, as we show in Appendix D, clustering using a three-
anchor node motif is equivalent to clustering with a specific weighted
combination of two-anchor node motifs. This equivalence breaks down for motifs
with more than three anchor nodes.

##  5 Classical algorithms for motif spectral clustering

In this section we follow BGL (16) and describe classical algorithms for
finding a partition that approximately minimizes the motif conductance or
motif ratio cut121212For motifs of two or three anchor nodes; we will find two
anchor nodes to be sufficient for our purpose, see Appendix D.. The algorithms
consist of the following two steps: given the graph $G$ and a motif $M$, first
construct the motif graph $\mathpzc{G}$; second, perform $k$-means spectral
clustering on $\mathpzc{G}$ using either the normalized (resp. unnormalized)
Laplacian in order to find a partition with a low conductance (resp. ratio
cut). An overview of the run-times of the motif spectral clustering algorithms
discussed in this section is given in Table 2, where $n=|V|$ is the number of
vertices and $d$ the maximum degree of the original graph $G$,
$\mathpzc{m}=|\mathpzc{E}|$ is the number of edges of the motif graph
$\mathpzc{G}$, $s=|V_{M}|$ is the size of the motif $M$, $k$ is the number of
clusters, and $\epsilon$ is the relative accuracy with which the eigenvectors
of the Laplacian are approximated.

Algorithm | Specifics | Run-time
---|---|---
Construct $\mathpzc{G}$ | general | $\mathcal{O}(n^{s})$
| bounded degree $d$ | $\tilde{\mathcal{O}}(nd^{s-1})$
Obtain eigenvectors $\mathpzc{L}$ or $\mathpzc{L}_{\operatorname{norm}}$ | exact | $\mathcal{O}(n^{3})$
|  $\epsilon$-approximate | $\tilde{\mathcal{O}}\left(\mathpzc{m}+\frac{kn}{\epsilon^{2}}\right)$
Perform $k$-means clustering | – | $T_{k\text{-}\mathrm{means}}$
Table 2: Run-times of algorithms used for classical motif spectral clustering.

Note that $\mathpzc{m}\leq nd^{l}\leq nd^{s-1}$, since any two anchor nodes of
a given motif instance are in each others $l$-hop neighborhood, and trivially,
also $\mathpzc{m}\leq n^{2}$. If we use the $\epsilon$-approximate
eigenvectors to perform spectral clustering (for which we only require
constant $\epsilon>0$, see Section 5.2, and $k$ is also constant), the time to
perform the $\epsilon$-approximate $k$-means step is $\tilde{O}(nd^{l})$, and
therefore the construction of the motif graph becomes the bottleneck in the
complexity of the entire computation – assuming $k$-means runs in nearly-
linear time.

###  5.1 Constructing the motif graph

Let $G$ be an $n$-vertex, $m$-edge graph, and $M$ be a motif of size $s$. In
order to construct the motif adjacency matrix $\mathpzc{A}$, we need to find
all instances of $M$ in $G$. The most straightforward (and in general the
optimal) way to find all motif instances is to simply consider all ${n\choose
s}$ $s$-sized subsets of the vertex set $V$ and check whether they form motifs
for every choice of anchor nodes in each subset. Checking if a given subset of
$s$ vertices forms a motif instance requires $O(s^{2})=O(1)$ checks, since $s$
is constant. Therefore, the entire process of finding all motif instances
takes $O(n^{s})$ time.

If we have adjacency list access to $G$ and know that it has maximum degree
$d$, then we can more efficiently search for possible motif instances: since
the motif is always taken to be a connected graph, every motif instance can be
found by (i) picking an initial vertex $u\in V$, and (ii) growing the motif
instance from $u$ by exploring the local neighbourhood of $u$ in order to find
$s-1$ more vertices that might yield a match to the motif. Since each vertex
has degree at most $d$, there are at most $d^{s-1}$ possible choices of $s$
vertices in the local neighbourhood of each vertex, and hence this process
requires $\mathcal{O}(nd^{s-1})$ time to check all connected $s$-tuples of
nodes for motif instances. We describe a classical procedure for constructing
these subsets in Section 6.1.1.

The complexities presented above hold for general motifs. However, for certain
motifs the time to find all instances can sometimes be faster – for example,
all triangles in a graph can be found using $\Theta(m^{1.5})$ queries Lat
(08); all induced and non-induced ‘position-aware’ motifs of size at most 4
can be found using $\Theta(m^{2})$ queries MS (10); and quadrangles can be
found using $\Theta(m^{1.5})$ queries CN (85) – see the appendix of BGL (16)
for more details.

###  5.2 k-means spectral clustering

Given an integer $k\in\mathbb{N}$, and (say, adjacency list) access to
$\mathpzc{A}$, we can next proceed to search for a partition
$W_{1},\ldots,W_{k}$ that minimizes either the motif ratio cut or the motif
conductance of $G$ by minimizing the ordinary ratio cut or conductance in
$\mathpzc{G}$ as described at the end of Section 3.3. Both tasks, which are
NP-hard for worst-case instances WW (93), can be tackled using k-means
spectral clustering131313k-means spectral clustering solves a relaxed version
of the NP-hard conductance or ratio cut minimization problem. It outputs
clusters that are close to the optimal clusters for _well-clustered_ graphs
PSZ (15). (see vL (07) and references therein), which finds partitions that
approximately minimize either the ratio cut or the conductance.

Whether spectral clustering minimizes ratio cut or conductance depends on
whether it is performed using the ordinary or the normalized Laplacian of the
motif graph. Let $\mathpzc{D}$ be the diagonal weighted _motif degree matrix_
of $\mathpzc{G}$, with coefficients $\mathpzc{D}_{uu}=\mathpzc{s}_{u}$, where
$\mathpzc{s}_{u}$ is the strength of vertex $u$, and define the _motif
Laplacian_ $\mathpzc{L}$ by

$\mathpzc{L}:=\mathpzc{D}-\mathpzc{A},$

and the _normalized motif Laplacian_ by

$\mathpzc{L}_{\operatorname{norm}}:=\mathpzc{D}^{-\frac{1}{2}}\mathpzc{L}\mathpzc{D}^{-\frac{1}{2}}=I-\mathpzc{D}^{-\frac{1}{2}}\mathpzc{A}\mathpzc{D}^{-\frac{1}{2}}.$

####  5.2.1 Minimizing ratio cut

In order to find a partition with small ratio cut, we can perform spectral
clustering using the unnormalized Laplacian $\mathpzc{L}$. This works as
follows.

  1. 1.

Compute the $k$ eigenvectors of $\mathpzc{L}$ corresponding to the $k$
smallest eigenvalues, and let $U$ be the $n\times k$ matrix containing the
first $k$ eigenvectors as columns.

  2. 2.

For $i\in[n]$, let $u_{i}$ be the $i$-th row of $U$. Each $k$-dimensional row
vector $u_{i}\in\mathbb{R}^{k}$ can be thought of as a feature vector for the
$i$-th vertex of $V$.

  3. 3.

Cluster the vertices of $V$ by performing $k$-means clustering on the $n$
feature vectors $\\{u_{i}\\}_{i=0}^{n-1}\subset\mathbb{R}^{k}$.

####  5.2.2 Minimizing conductance

If, instead of ratio cut, we want to find a partition with low conductance, we
can apply spectral clustering to the normalized Laplacian
$\mathpzc{L}_{\operatorname{norm}}$:

  1. 1.

Compute the first $k$ eigenvectors of $\mathpzc{L}_{\operatorname{norm}}$
corresponding to the smallest $k$ eigenvalues, and let $\tilde{U}$ be the
$n\times k$ matrix containing the first $k$ eigenvectors as columns.

  2. 2.

Let $U$ be the matrix obtained by taking $\tilde{U}$, and renormalizing all
the rows to 1, that is:

$u_{ij}:=\frac{\tilde{u}_{ij}}{\sqrt{\sum_{l=1}^{k}\tilde{u}_{il}^{2}}}.$

  3. 3.

For $i\in[n]$, let $u_{i}$ be the $i$-th row of $U$. Each $k$-dimensional row
vector $u_{i}\in\mathbb{R}^{k}$ can be thought of a feature vector for the
$i$-th vertex of $V$.

  4. 4.

Cluster the vertices of $V$ by performing $k$-means clustering on the $n$
feature vectors $\\{u_{i}\\}_{i=0}^{n-1}\subset\mathbb{R}^{k}$.

Note that, for $\mathpzc{d}$-regular graphs,
$\operatorname{vol}_{\mathpzc{G}}(W)=\mathpzc{d}|W|$. As a consequence, for
these graphs minimizing the conductance is equivalent to minimizing ratio cut.

####  5.2.3 Disconnected vertices

It is possible for certain vertices in $G$ to become entirely disconnected in
$\mathpzc{G}$ because their motif degree is zero. If we want to use the
normalized Laplacian for spectral clustering, then we first have to remove all
such vertices since the normalized Laplacian is obtained by multiplying the
original Laplacian by $D^{-\frac{1}{2}}$.

Moreover, if we were to perform spectral $k$-means clustering (using the
unnormalized Laplacian) on $\mathpzc{G}$ with $\mathpzc{V}=V$, the algorithm
could just output several clusters containing a single disconnected vertex
each and place the remaining vertices into one or more larger clusters to
minimize ratio cut. From the perspective of the motif adjacency matrix, the
clusters containing a single disconnected vertex are not very interesting.
Hence, after the construction of $\mathpzc{G}$ we should remove all vertices
$u\in V$ that have zero (motif) degree $\mathpzc{d}_{u}=0$ and put each of
them in their own size-one cluster. The remaining vertex set $\\{u\in
V:\mathpzc{d}_{u}>0\\}$ will then be the vertex set of $\mathpzc{G}$ on which
we perform k-means spectral clustering. Note that this procedure yields a
number of clusters that is equal to $k$ plus the number of vertices in $V$
that are no anchor node of any motif instance in $G$.

In the remainder of this work, we will not emphasise this practical detail and
simply write $V$ for the vertex set of $\mathpzc{G}$. Note that removing
disconnected vertices does not affect our run-time upper bounds, since none of
our algorithms run in sub-linear time (a single step of $k$-means takes time
linear in $n$).

####  5.2.4 Complexity

For an $n$-vertex, $\mathpzc{m}$-edge motif graph $\mathpzc{G}$, it is
possible to compute the eigenvectors of $\mathpzc{L}$ or
$\mathpzc{L}_{\text{norm}}$ in $O(n^{3})$ time via exact diagonalization.
However, we can also use $\epsilon$-approximate spectral clustering to find an
an $\epsilon$-approximation to the $k$ smallest eigenvalues
$\lambda_{1},\ldots,\lambda_{k}$ of the (normalized) Laplacian together with a
set of orthonormal unit vectors $v_{1},\ldots,v_{k}$ such that

$v_{i}^{T}\mathpzc{L}_{(\text{norm})}v_{i}\leq(1+\epsilon)\lambda_{i}\quad\text{for
all}\quad 1\leq i\leq k$

in time at most
$\tilde{O}\left(\mathpzc{m}+\frac{k\mathpzc{n}}{\epsilon^{2}}\right)$ ST (07,
14); KLP (15). This set of unit vectors approximates the subspace spanned by
the $k$ smallest eigenvectors of $\mathpzc{L}$, and is suitable for performing
spectral clustering, even for _constant_ $\epsilon>0$ PSZ (15); AdW (20).
Finally, we use $k$-means, which takes time $T_{k\text{-}\mathrm{means}}$
adding up to a total run-time of
$\tilde{O}(\mathpzc{m}+T_{k\text{-}\mathrm{means}})$, since one step of
k-means already takes time $nk^{2}$ and $\epsilon$ is constant.

As described in the references above, the method for finding approximate
eigenvectors makes use of a graph sparsification algorithm which, given the
graph $\mathpzc{G}$, constructs a spectral sparsifier $\mathpzc{G}_{S}$ of
$\mathpzc{G}$, and then uses the inverse power method on the graph Laplacian
$\mathpzc{L}_{S}$ corresponding to $\mathpzc{G}_{S}$. This method can also be
used to construct approximate eigenvectors of the normalized Laplacian
$\mathpzc{L}_{\operatorname{norm}}$, by applying the inverse power method to
$\mathpzc{D}^{-1/2}\mathpzc{L}_{S}\mathpzc{D}^{-1/2}$, where $\mathpzc{D}$ is
the degree matrix of the unsparsified graph $\mathpzc{G}$ KLP (15).

##  6 Quantum motif clustering

In this section we present three quantum algorithms for motif spectral
clustering, one using Grover search, and the other two using quantum
approximate counting. All three algorithms consist of two steps: (i) construct
the motif graph $\mathpzc{G}$, and (ii) perform spectral clustering on
$\mathpzc{G}$. As discussed in Section 4, the bottleneck for motif clustering
is in step (i), constructing the motif graph, and this is also where our
contribution lies; for step (ii) we use either the spectral clustering
algorithm based on the spectral estimation algorithm of ST (14) or the
algorithm for quantum spectral clustering of Apers and de Wolf AdW (20).

We begin by introducing the quantum tools that we make use of, followed by a
description in Section 6.1 of a classical subroutine for exploring the local
neighbourhood of vertices in a graph according to a particular motif
structure. In Section 6.2 we discuss how Grover search can be applied to find
all motif instances in order to do motif clustering, and in Section 6.3 we use
quantum approximate counting to construct an approximation to the motif graph,
and discuss under what conditions this approximation can be used for motif
clustering. We then compare the run-times of all approaches in Section 6.4.
Subsequently, in Section 7, we provide details to justify the use of
approximations in the context of spectral clustering.

###  6.1 Preliminaries

We will find the following quantum subroutines useful. For each, we consider a
Boolean function $f:[N]\rightarrow\\{0,1\\}$ on $N$ items, with
$t=|\\{i:f(x)=1\\}|$ the (unknown) number of ‘marked’ items. We will assume
that we have oracle access to $f$, i.e. a unitary $\mathcal{O}_{f}$ that acts
as $\mathcal{O}_{f}\ket{x}\ket{0}=\ket{x}\ket{f(x)}$.

######  Lemma 2 (Grover search with an unknown number of marked items BBHT
(98)).

There exists a quantum algorithm $\text{\bf Search}(\mathcal{O}_{f})$ that,
with probability at least $2/3$, finds and returns an index
$i\in\\{0,\dots,N-1\\}$ such that $x_{i}=1$ if one exists, and requires an
expected number $O(\sqrt{N/t})$ queries to $\mathcal{O}_{f}$ and its inverse,
and $O(\sqrt{N/t}\log(N))$ other elementary operations. If no such $x_{i}$
exists, the algorithm indicates this with certainty and requires $O(\sqrt{N})$
queries to $\mathcal{O}_{f}$ and its inverse, and $O(\sqrt{N}\log(N))$ other
elementary operations.

Using $\text{\bf Search}(\mathcal{O}_{f})$, one can output _all_ $t$ marked
items in time $\tilde{O}(\sqrt{Nt})$. More precisely, we have

######  Lemma 3 (Finding all marked items BBHT (98)).

There exists a quantum algorithm $\text{\bf Find}(\mathcal{O}_{f})$ that
outputs, with constant probability, all $t$ marked items and makes an expected
$O(\sqrt{Nt})$ calls to $\mathcal{O}_{f}$ and its inverse, and
$\tilde{O}(\sqrt{Nt})$ other elementary operations.

######  Lemma 4 (Approximate Quantum Counting BHMT (02)).

There exists a quantum algorithm $\text{\bf Approx-
Count}(\mathcal{O}_{f},\epsilon,\delta)$ that, with probability $\geq
1-\delta$, outputs a number $\tilde{t}$ such that

$|\tilde{t}-t|\leq\epsilon t$

using an expected number
$O\left(\frac{1}{\epsilon}\sqrt{N/t}\log(1/\delta)\right)$ of calls to
$\mathcal{O}_{f}$ and $\mathcal{O}_{f}^{-1}$ and
$\tilde{O}\left(\frac{1}{\epsilon}\sqrt{N/t}\log(1/\delta)\right)$ other
elementary operations. If $t=0$, then the algorithm outputs with certainty
$\tilde{t}=t$ and calls $\mathcal{O}_{f}$ and its inverse $O(\sqrt{N})$ times,
and uses $\tilde{O}(\sqrt{N})$ other elementary operations.

Finally, we will use a quantum algorithm for spectral $k$-means clustering
from Apers and de Wolf AdW (20), which itself uses the (classical) algorithm
of Spielman and Teng ST (14) to find approximations to the first $k$
eigenvectors of a graph Laplacian obtained via quantum graph sparsification.

######  Lemma 5 (Quantum spectral estimation AdW (20)).

Given adjacency list access to an $n$-vertex weighted graph $G$ with $m$
edges, there exists an $\tilde{O}(\sqrt{mn}/\epsilon+kn/\epsilon^{2})$-time
quantum algorithm that outputs, with high probability, an
$\epsilon$-approximation of each of the $k$ smallest eigenvalues
$\lambda_{1},\ldots,\lambda_{k}$ of the graph Laplacian $L$, and a set of
orthogonal unit vectors $v_{1},\dots,v_{k}$ such that
$v_{l}^{T}Lv_{l}\leq(1+\epsilon)\lambda_{l}$ for all $1\leq l\leq k$.

It turns out that choosing $\epsilon$ to be constant is already enough to
perform spectral clustering AdW (20), and hence Apers and de Wolf note that

######  Corollary 2 (Quantum spectral clustering AdW (20)).

There exists a quantum algorithm that, given adjacency list access to an
$n$-vertex weighted graph with $m$ edges, performs spectral $k$-means
clustering on the graph in time
$\tilde{O}(\sqrt{mn}+T_{k\text{-}\mathrm{means}})$.

Classically, a fast algorithm for (approximate) $k$-means spectral clustering
can be obtained by combining the spectral estimation routine of Spielman and
Teng ST (14) with constant error with a $k$-means clustering algorithm,
yielding the following:

######  Lemma 6 (Spectral clustering ST (14)).

There exists a classical algorithm that, given adjacency list access to an
$n$-vertex weighted graph with $m$ edges, performs spectral $k$-means
clustering on the graph in time $\tilde{O}(m+T_{k\text{-}\mathrm{means}})$.

####  6.1.1 Exploring the ‘motif neighbourhood’ of a vertex

Here we describe a short classical algorithm which, given a vertex $u$, motif
$M$ of size $s$, and a sequence of integers $I$ of length $s-1$, can be used
to return a pairing of $s$ vertices around $u$ to vertices in $M$, such that
those vertices are candidates for a match of the motif in the graph. We call
this procedure a ‘tree walk’, for reasons that will become apparent. More
precisely, given a tree $T$ of $t$ vertices, a graph $G$, and a vertex $v$, a
tree walk explores the neighbourhood of $v$ in $G$ by constructing the tree
$T$ locally out of the neighbours of $v$. The output is a list of size $t$
that identifies vertices in $G$ with vertices in the tree $T$. We give details
of the tree walk in Algorithm 1, and show an example of two outcomes of a tree
walk in Figure 2. For any fixed input, the tree walk algorithm takes time
linear in the number of edges in the tree $T$. Note that it is possible for
Algorithm 1 to return a list $L$ shorter than desired ($T$). This will not be
a problem for us.

Algorithm 1 Tree walk

1:function Tree walk(Tree $T$ with root $r$, graph $G$, vertex $v$, sequence
$I=\\{i_{j}\\}_{j=1}^{|T|}$)

2: Initialise $L\leftarrow\\{(r,v)\\}$

3: for Each child vertex $c$ of $r$ do

4: Let $i_{j}$ be the first element from $I$

5: Let $u$ be the $i_{j}$th neighbour of $v$ in $G$ (if $v$ has no $i_{j}$th
neighbour, set $u=\O$)

6: Let $T_{c}$ be the sub-tree rooted at $c$

7: $I\leftarrow I\setminus\\{i_{j}\\}$

8: $L^{\prime}\leftarrow$ Tree walk($T_{c}$, $G$, $u$, $I$)

9: $L\leftarrow L\cup L^{\prime}$

10: end for

11: return $L$

12:end function

Figure 2: The stages of two possible tree walks (corresponding to different
settings of the integer sequence), showing the list $L$ maintained during the
tree walk after each step. The tree is shown in red (top), the graph on which
the walk is performed in blue (middle and bottom). The edges and vertices
selected at each step are shown (thicker edges and darker vertices,
respectively).

###  6.2 Motif clustering with Grover search

The most straightforward way to speed up classical motif clustering is to
replace the search for motif instances by a Grover search. In doing so, we
find all motif instances in $G$ and construct $\mathpzc{G}$ exactly, and
provide a generic speedup over the classical approach. The advantage of
producing the adjacency lists exactly is that we can then cluster based on
both the normalized and unnormalized motif Laplacian with the usual
theoretical guarantees. In Sections 6.2.1 and 6.2.2 below we prove Theorem 1.

##### Checking for motif matches in the graph

We will routinely need to check if a set of $s$ vertices in the input graph
$G$ corresponds to a match of the motif $M$. To do this, we need to check if
all the edges (resp. non-edges) of $M$ are present (resp. not present) in $G$.
Since we only assume adjacency list access to $G$, this will incur some
overhead. In particular, to check for the presence of an edge $(u,v)$ in $G$,
we can check if $v$ appears as a neighbour in $u$’s adjacency list.

As discussed in the introduction, if the adjacency lists are sorted (according
to some fixed ordering over the vertices of $G$), then this can be done in
time $O(\log d)$ per edge. since we will have to check the existence or non-
existence of $O(s^{2})$ edges – with $s$ constant – this will take time
$O(s^{2}\log d)=O(\log d)$.

If the adjacency lists are not sorted, then we can instead use a single
application of Search from Lemma 2 to detect the presence of the edge with
probability $\geq 1-\epsilon$ in time $O(\sqrt{d}\log(1/\epsilon))$. If we
apply this subroutine $N\geq 1$ times and we want all the instances as a whole
to succeed with probability at least $1-C$ ($C>0$ constant to choose to your
liking), then we need $\epsilon=C/N$ by the union bound. The number of times
the function Match is called is $N=O(\sqrt{nd^{s-1}\mathpzc{M}})$ in Algorithm
2, which is also the number of times the subroutine for checking edges is
called (since $s$ is constant). Because this is at most polynomial in $n$, it
will only add a logarithmic overhead to the run-time of Search for edges,
which therefore takes time $\tilde{O}(s^{2}\sqrt{d})=\tilde{O}(\sqrt{d})$.

####  6.2.1 Constructing $\mathpzc{G}$ via Grover search

Our first algorithm is a basic application of Grover search to find all
matches of the motif within the graph, which with some short (classical) post-
processing allows us to obtain the motif adjacency lists
$\\{\mathpzc{J}_{u}\\}_{u\in V}$ exactly (i.e. without errors on the weights).
As we construct the motif adjacency lists, we keep them ordered according to
some arbitrary but fixed ordering of the vertices in $V$. The algorithm makes
direct use of the TreeWalk sub-routine from Algorithm 1.

Algorithm 2 Motif-Grover

1:Initialise $\mathpzc{J}_{u}$ for each $u\in V$.

2:Construct a spanning tree $T$ for the motif $M$.

3:Let $\mathcal{O}_{f}$ be the unitary that implements Match, taking as input
some vertex, integer-sequence pair $(u,I)$ (where $I=\\{i_{j}\\}_{j=1}^{s-1}$,
$i_{j}\in\\{0,\dots,d-1\\}$).

4:Use $\text{\bf Find}(\mathcal{O}_{f})$ to find all $\mathpzc{M}$ motif
instances in the graph, searching over all $O(nd^{s-1})$ possible
vertex/integer-sequence pairs $(u,I)$.

5:Classically post-process the $\mathpzc{M}$ matches to fill in the entries of
each $\mathpzc{J}_{u}$.

6:return $\\{\mathpzc{J}_{u}\\}_{u\in V}$

7:

8:function Match(Tree $T$, graph $G$, vertex $v$, sequence $I$)

9: $L\leftarrow$ TreeWalk($T$,$G$,$v$,$I$)

10: if $L$ gives a match to the motif in $G$ then

11: return 1

12: else

13: return 0

14: end if

15:end function

Each tree walk (Line 9) takes time $s-1$ and each check for a match (Line 10)
takes time either $O(\log d)$ or $\tilde{O}(\sqrt{d})$, depending on whether
the adjacency lists are sorted or unsorted. From Lemma 3, Find requires an
expected $O(\sqrt{nd^{s-1}\mathpzc{M}})$ applications of these subroutines and
$\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}})$ other operations. The classical post-
processing takes $O(l\log d)$ time for each match (if the match concerns
vertices $u$ and $v$ as anchor nodes, we may have to do binary search of the
motif neighbours of $u$ to find the entry in $u$’s motif adjacency list that
corresponds to vertex $v$, and vice versa), hence $\tilde{O}(\mathpzc{M})$
time in total. All steps combined, the algorithm takes time
$\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}}+\mathpzc{M})=\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}})$
if the adjacency lists are sorted, and $\tilde{O}(\sqrt{nd^{s}\mathpzc{M}})$
time if they are not. If we choose to pre-sort the adjacency lists ahead of
time, or need to load the input graph to QRAM, this will add an extra additive
overhead of $\tilde{O}(nd)$.

If the motif $M$ is symmetric under non-trivial motif isomorphisms, then
Algorithm 2 will find each motif instance exactly $S_{M}$ times, where $S_{M}$
is the number of motif isomorphisms of $M$. Because $s$ is constant, so is
$S_{M}$, and therefore we incur a constant overhead in the presence of motif
symmetries; see Appendix A for details.

####  6.2.2 Clustering using Motif-Grover

In the previous section we established how to obtain adjacency list access to
the (exact) motif graph $\mathpzc{G}$. To perform motif clustering, we apply
$k$-means spectral clustering to $\mathpzc{G}$ using the spectral clustering
algorithm of Lemma 6, which results in a clustering that approximately
minimizes the motif RatioCut (when applied to the ordinary Laplacian of
$\mathpzc{G}$), or the motif conductance (when applied to the normalized
Laplacian of $\mathpzc{G}$).

Algorithm 3 Quantum motif clustering: Grover version

Input: A graph $G=(V,E)$, motif $M$, and an integer $k\geq 1$.

1:Apply Algorithm 2 on input $G=(V,E)$ and motif $M$, which returns the set of
exact adjacency lists $\\{\mathpzc{J}_{u}\\}_{u\in V}$ describing the motif
graph $\mathpzc{G}$.

2:Apply the algorithm from Lemma 6 to either i) the unnormalized or ii) the
normalized motif graph Laplacian, using the adjacency lists to provide access.

3:return A $k$-partition of $G=(V,E)$ that approximately minimizes either i)
motif RatioCut or ii) Motif conductance.

The run-time of step 2 is
$\tilde{O}(\mathpzc{m}+T_{k\text{-}\mathrm{means}})$, where
$\mathpzc{m}\leq\text{min}(nd^{l},n^{2})$ is the number of edges in the motif
graph $\mathpzc{G}$ (recall that $l$ is the maximum distance between any two
anchor nodes in the motif). Since $\mathpzc{m}\leq\mathpzc{M}=O(nd^{s-1})$,
with similar considerations to the algorithm from the previous section, the
total expected run-time is either
$\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}}+\mathpzc{m}+T_{k\text{-}\mathrm{means}})=\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})$
if the adjacency lists are sorted, else
$\tilde{O}(\sqrt{nd^{s}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})$. Once again,
if we either have classical access to the input graph and need to load it to
QRAM first, or we need pre-sort the adjacency lists ahead of time in order to
apply the second algorithm, we add an extra additive overhead of
$\tilde{O}(nd)$.

###  6.3 Motif clustering via quantum counting

If some reasonably weak conditions hold for the motif, then it can be faster
to use quantum counting to obtain an $\epsilon$-approximation of the motif
graph (in the sense that the weights on the edges are approximated up to
relative error $\epsilon$), and then use this for motif clustering. In many
cases a rough approximation to the graph is good enough for clustering, and we
argue this both formally (in the case of clustering on the unnormalized
Laplacian) and empirically (in the case of clustering on the normalized
Laplacian) in Section 7.

In this section we present a quantum algorithm (Algorithm 5) for constructing
the approximate motif graph using quantum approximate counting. As before,
this algorithm can be combined with the algorithm of either Corollary 2 or
Lemma 6 to obtain a quantum algorithm for (approximate) motif clustering. We
begin by describing a quantum algorithm (Algorithm 4) for computing
approximations to the entries of the motif adjacency matrix $\mathpzc{A}$, and
then use this to construct the motif graph. More precisely, given vertices $u$
and $v$, we provide a quantum algorithm that outputs an approximation
$\widetilde{\mathpzc{A}_{uv}}$ satisfying

$\left|\widetilde{\mathpzc{A}_{uv}}-\mathpzc{A}_{uv}\right|\leq\epsilon\mathpzc{A}_{uv}$
(6)

with probability at least $1-\delta$ for some choice of accuracy $\epsilon$
and probability of failure $\delta>0$.

The algorithm for approximate motif clustering described in this section
assumes the motif $M$ has two anchor nodes. However, our algorithm can easily
be extended to motifs with more than 2 anchor nodes, since the motif graph can
be constructed in this case by decomposing the motif into a combination of
two-anchor-node motifs – see Appendix D.2 for details.

Algorithm 4 Motif Count

1:function Motif Count(Motif $M=(V_{M},E_{M},V_{A})$ with two anchor nodes $a$
and $b$, graph $G$, vertices $u,v$, accuracy $\epsilon$, probability
$1-\delta$)

2: Construct a spanning tree $T=(V_{T},E_{T})$ of $M$.

3: Split $T$ into two trees: an $s_{a}$-vertex tree
$T_{a}=(V_{T_{a}},E_{T_{a}})$ rooted at $a\in V_{A}$ and an $s_{b}$-vertex
tree $T_{b}=(V_{T_{b}},E_{T_{b}})$ rooted at $b\in V_{A}$.

4: Let $O_{f}$ be the unitary that implements Match on the trees
$T_{a},T_{b}$, graph $G$, vertices $u,v$, and taking as input two integer
sequences
$I_{a}=\\{i^{(a)}_{j}\\}_{j=1}^{s_{a}-1},I_{b}=\\{i^{(b)}_{j}\\}_{j=1}^{s_{b}-1}$,
where $s_{a}=|V_{T_{a}}|$ and $s_{b}=|V_{T_{b}}|$.

5: return $\text{\bf{Approx-Count}}(O_{f},\epsilon,\delta)$

6:end function

7:

8:function Match(Trees $T_{a},T_{b}$, graph $G$, vertices $u,v$, sequences
$I_{a},I_{b}$)

9: $L_{a}\leftarrow$ TreeWalk($T_{a}$,$G$,$u$,$I_{a}$)

10: $L_{b}\leftarrow$ TreeWalk($T_{b}$,$G$,$v$,$I_{b}$)

11: $L\leftarrow L_{a}\cup L_{b}$

12: if $L$ gives a match to the motif in $G$ then

13: return 1

14: else

15: return 0

16: end if

17:end function

######  Lemma 7.

Suppose we have coherent adjacency list access to an $n$-vertex graph $G$ with
maximum degree $d$, where the adjacency lists are assumed to be sorted, and we
are given an $s$-vertex motif $M=(V_{M},E_{M},V_{A})$ with $|V_{A}|=2$. Let
$u,v$ be two vertices of $G$, and $\epsilon>0$. Then, if $\mathpzc{A}_{uv}\geq
1$, Algorithm 4 outputs an approximation $\widetilde{\mathpzc{A}_{uv}}$
satisfying Eq. (6) with probability $\geq 1-\delta$ using
$O\left(\frac{1}{\epsilon}\sqrt{\frac{d^{s-2}}{\mathpzc{A}_{uv}}}\log(1/\delta)\log(d)\right)$
queries to the graph $G$, and
$\tilde{O}\left(\sqrt{\frac{d^{s-2}}{\mathpzc{A}_{uv}}}\log(1/\delta)\log(d)\right)$
other elementary operations. If $\mathpzc{A}_{uv}=0$, then Algorithm 4 outputs
$\widetilde{A}_{uv}=0$ with certainty using $O(\sqrt{d^{s-2}})$ queries to the
graph $G$ and $\tilde{O}(\sqrt{d^{s-2}})$ other operations.

###### Proof.

Our task is to approximately count the number of motifs present in the graph
$G$ that both $u$ and $v$ appear in (as anchor nodes). Algorithm 4 achieves
this by using tree walks to explore locally the areas around $u$ and $v$, in
search of a set of vertices and edges that match the motif structure, and then
uses approximate quantum counting to estimate the number of motifs containing
$u$ and $v$.

As described in Algorithm 4, we start by (classically) constructing a spanning
tree $T=(V_{T},E_{T})$ of the motif $M$, for example using breadth-first
search in time $O(s^{2})=O(1)$. Next, we remove an edge of the tree in such a
way that the two newly formed trees contain one anchor node $a$ and $b$ each,
which yields an $s_{a}$-vertex tree $T_{a}=(V_{T_{a}},E_{T_{a}})$ rooted at
$a$ and an $s_{b}$-vertex tree $T_{b}=(V_{T_{b}},E_{T_{b}})$ rooted at $b$,
respectively. Note that $|E_{T_{a}}|=s_{a}-1$, $|E_{T_{b}}|=s_{b}-1$, and
$s_{a}+s_{b}=s$. See Figure 3 for an example.

Figure 3: A motif $M$ with two anchor nodes (dark red), the spanning tree $T$
of $M$, and the two trees ($T_{a}$ and $T_{b}$) rooted at the anchors nodes.

We then fix two integer sequences that uniquely define a tree walk on each
tree: $I_{a}=\\{i^{(a)}_{j}\\}_{j=1}^{s_{a}-1}$ for the tree walk on $T_{a}$
and $I_{b}=\\{i^{(b)}_{j}\\}_{j=1}^{s_{b}-1}$ for the tree walk on $T_{b}$.
For a fixed pair of sequences, we require $s_{a}+s_{b}-2=s-2$ queries to $G$
to perform both tree walks. Let $L=\\{(b_{j},v_{j})\\}_{j=1}^{s}$ be the union
of the lists output by the two tree walks (i.e. where each $b_{j}$ labels a
vertex in $M$ and $v_{j}$ a vertex in $G$). To check whether the subset of
vertices $v_{j}$ match the motif, we need to check that for every edge
$(b_{j},b_{j^{\prime}})\in E_{M}$, $(v_{j},v_{j^{\prime}})\in E$ and for every
non-edge $(b_{j},b_{j^{\prime}})\notin E_{m}$, $(v_{j},v_{j^{\prime}})\notin
E$. Since we only assume adjacency list access to the edges of $G$, this
incurs some overhead. In particular, given vertices $v_{0},v_{1}$ from $G$, we
must query all of the neighbours of $v_{0}$ for the presence (resp. non-
presence) of $v_{1}$ to check for the edge (resp. non-edge) $(v_{0},v_{1})$.
Since the adjacency lists are sorted, this can be done in time $O(\log d)$
(recall that $s$ is constant).

For the two trees $T_{a}$ and $T_{b}$, there are at most
$d^{s_{a}-1}d^{s_{a}-1}=d^{s_{a}+s_{b}-2}=d^{s-2}$ possible tree walks that
can be performed on $G$, each corresponding to a unique string of $s-2$
integers of value at most $d$. Hence Approx-Count will search over at most
$d^{s-2}$ items. With accuracy $\epsilon$ and probability of success $\delta$,
if $\mathpzc{A}_{uv}\geq 1$, this requires
$O\left(\frac{1}{\epsilon}\sqrt{\frac{d^{s-2}}{\mathpzc{A}_{uv}}}\log(1/\delta)\right)$
queries to the subroutine that checks if a subset of vertices in the graph
matches the motif structure, plus
$\tilde{O}\left(\frac{1}{\epsilon}\sqrt{\frac{d^{s-2}}{\mathpzc{A}_{uv}}}\log(1/\delta)\right)$
other operations; if $\mathpzc{A}_{uv}=0$, we need $O(\sqrt{d^{s-2}})$ queries
and $\tilde{O}(\sqrt{d^{s-2}})$ other operations.

Finally, in the presence of symmetries within the motif, we note that the
quantum counting routine will over count-motif matches. In Appendix A we work
out exactly how many duplicates will be found, and show that this quantity,
$S_{M}^{(a,b)}$, which is $O(1)$ because $s=O(1)$, depends only on the motif
$M$ itself and can be computed ahead of time. Dividing the output of Approx-
Count by $S_{M}^{(a,b)}$ we obtain our estimate $\widetilde{\mathpzc{A}_{uv}}$
(note that this doesn’t affect the accuracy of the estimate). ∎

####  6.3.1 Constructing $\mathpzc{G}$ via quantum approximate counting

As we discuss in Section 7, for the purpose of clustering it turns out that
approximating the edge weights up to _constant_ relative error is sufficient,
and, as we will see, provides a speedup over the classical algorithm when the
motif length $l$ satisfies $2l<s$. Again we construct $\mathpzc{G}$ by
explicitly constructing the motif adjacency lists for each vertex, as
described in Algorithm 5.

Algorithm 5 Approximate-Motif

Input: A graph $G=(V,E)$, motif $M$ with two anchor nodes, relative error
$\epsilon>0$ and probability of failure
$\delta=\Omega\left(\frac{1}{\mathop{poly}(n)}\right)$.

1:Initialise the adjacency lists $\\{\widetilde{\mathpzc{J}}_{u}\\}_{u\in V}$.

2:for Every vertex $u\in V$ do

3: Find the $l$-hop neighborhood $N^{l}_{u}$ of $u$ via breadth-first-search.

4: for Every vertex $v\in N^{l}_{u}$ do

5: Use Algorithm 4 to obtain $\widetilde{\mathpzc{A}}_{uv}$, an approximation
of $\mathpzc{A}_{uv}$ up to relative error $\epsilon$ and with probability
$\geq 1-\frac{\delta}{n^{2}}$.

6: if $\widetilde{\mathpzc{A}}_{uv}\neq 0$ then

7: Update $\widetilde{\mathpzc{J}}_{u}$ to include the edge to $v$ with weight
$\widetilde{\mathpzc{A}}_{uv}$.

8: end if

9: end for

10:end for

11:return $\\{\widetilde{\mathpzc{J}}_{u}\\}_{u\in V}$.

The output of this algorithm is a classical description of an approximation of
the motif adjacency lists. These lists store approximations to the non-zero
entries of the motif adjacency matrix $\mathpzc{A}$, and they satisfy, for all
$u,v\in V$,

$(1-\epsilon)\mathpzc{A}_{uv}\leq\widetilde{\mathpzc{A}}_{uv}\leq(1+\epsilon)\mathpzc{A}_{uv}.$

Complexity-wise, the computation of each $\tilde{\mathpzc{A}}_{uv}$ (using
Algorithm 4 as a subroutine) takes time
$\tilde{O}(\frac{1}{\epsilon}\sqrt{d^{s-2}})$, while the construction and
looping over of the $l$-hop neighbourhoods takes time $O(d^{l})$. So for
constant $\epsilon>0$ and
$\delta=\Omega\left(\frac{1}{\mathop{poly}(n)}\right)$, the total run-time of
this algorithm is

$\tilde{O}(nd^{l}\sqrt{d^{s-2}})\,.$

####  6.3.2 Motif clustering with quantum counting and classical clustering

Given the approximate motif graph $\widetilde{\mathpzc{G}}$ constructed using
Algorithm 5, we next proceed to cluster the vertex set of
$\widetilde{\mathpzc{G}}$, with the approximate adjacency lists
$\\{\widetilde{\mathpzc{J}}_{u}\\}_{u\in V}$ used to provide access.

We first consider spectral clustering on the approximate unnormalized
Laplacian, meaning that the clusters aim to minimize RatioCut. The input is an
unweighted graph $G=(V,E)$ on $n$ vertices and a motif $M$ of size $s$ with
two anchor nodes at distance $l$ from each other. We apply Algorithm 5 to
obtain the adjacency lists of the approximate motif graph
$\tilde{\mathpzc{G}}$ up to fixed relative error $\epsilon>0$, and then use
the algorithm of Lemma 6 to cluster $\tilde{\mathpzc{G}}$.

Let $\widetilde{\mathpzc{D}}$ be the diagonal matrix of (approximate) motif
degrees obtained from $\widetilde{\mathpzc{A}}$, and
$\widetilde{\mathpzc{L}}=\widetilde{\mathpzc{D}}-\widetilde{\mathpzc{A}}$ be
the approximate motif Laplacian. By Lemma 8 (which we will prove later), the
spectral structure of the true motif graph Laplacian $\mathpzc{L}$ of
$\mathpzc{G}$ is preserved by our approximation, i.e.

$(1-\epsilon)\mathpzc{L}\preceq\tilde{\mathpzc{L}}\preceq(1+\epsilon)\mathpzc{L}\,.$
(7)

This property is necessary for applying the Spectral Clustering algorithm in
Lemma 6, where it suffices to choose $\epsilon$ to be some small constant. Our
quantum motif clustering algorithm is given in Algorithm 6 below, which can
also be used to cluster using the normalized approximate motif graph
Laplacian, though here we don’t have the same theoretical guarantees – see
next paragraph.

Algorithm 6 Quantum motif clustering via quantum approximate counting and
classical spectral clustering

Input: A graph $G=(V,E)$, motif $M$ with two anchor nodes and integer $k\geq
1$.

1:Apply Algorithm 5 on input $G=(V,E)$, motif $M$ and some fixed relative
error $\epsilon>0$. This returns the approximate motif graph
$\tilde{\mathpzc{G}}$ via the set of approximate adjacency lists
$\\{\widetilde{\mathpzc{J}}_{u}\\}_{u\in V}$ up to relative error $\epsilon$.

2:Apply the algorithm from Lemma 6 on either i) the unnormalized approximate
motif Laplacian $\tilde{\mathpzc{L}}$ or ii) the normalized approximate motif
Laplacian $\widetilde{\mathpzc{L}}_{\operatorname{norm}}$ of
$\widetilde{\mathpzc{G}}$.

3:return A $k$-partition of $G=(V,E)$ that approximately minimizes either the
i) motif Ratiocut or ii) motif conductance.

With $s$ the size of $M$ and $l$ the distance between the two anchor nodes,
the first step takes $\widetilde{O}(nd^{l+\frac{s}{2}-1})$ time. The run-time
of the second step is at most
$\widetilde{O}(\mathpzc{m}+T_{k\text{-}\mathrm{means}})$, where $\mathpzc{m}$
is the number of edges in the motif graph given by $\widetilde{\mathpzc{A}}$.
Since $\mathpzc{m}=O(\min(nd^{l},n^{2}))$, the expected run-time of the entire
algorithm is

$\widetilde{O}(nd^{l+\frac{s}{2}-1}+T_{k\text{-}\mathrm{means}})\,,$

hence proving Theorem 2. In case we need to to pre-process the input graph in
advance, the run-time complexity will remain the same – see Appendix C.

##### Clustering with the normalized Laplacian

As we will show in Section 7, the equivalent of Eq. (7) for normalized
Laplacians does not hold in general. This means that, in principle, we cannot
apply spectral clustering to the normalized Laplacian for the approximate
motif graph and keep the same theoretical guarantees. However, we can still
make use of the approximate adjacency matrix if, somehow, we happen to know
the motif _degrees_ exactly – see Section 7.2 for details. Unfortunately,
computing the motif degrees exactly takes as much time as doing a Grover
search over all motif instances, and then the run-time is the same as the run-
time of Algorithm 2.

Nevertheless, in the absence of a firm theoretical footing, the numerical
simulations presented in Section 7.3 suggest that, in practice, we can use the
approximate motif graph and the corresponding approximate motif degrees to
cluster successfully using the normalized Laplacian.

####  6.3.3 Motif clustering with quantum counting and quantum clustering

In the case that $d^{l}=\omega(\sqrt{n})$, it is possible to obtain a more
efficient algorithm by not constructing the entire motif graph beforehand, but
instead providing query access to it. To do this, we can assume that the motif
graph is fully connected, but that non-edges have weight $0$. Then, using
Algorithm 4 of Lemma 7 with a constant $\epsilon$, we can provide adjacency
list access (which is now equivalent to adjacency matrix access) to the motif
graph $\mathpzc{G}$ using $\tilde{O}(\sqrt{d^{s-2}})$ queries to the input
graph $G$ and $\tilde{O}(\sqrt{d^{s-2}})$ other operations, and then directly
use the quantum spectral clustering algorithm of Apers and de Wolf from
Corollary 2 to cluster, which will require $\tilde{O}(n^{3/2})$ queries to the
adjacency lists of $\mathpzc{G}$. This will yield an algorithm for performing
motif clustering that takes

$\tilde{O}\left(n^{3/2}\sqrt{d^{s-2}}+T_{k\text{-}\mathrm{means}}\right)$

time, which proves Theorem 3. As before, pre-processing the input graph in
advance does not affect the run-time – see Appendix C. The process described
above is encapsulated in Algorithm 7.

Algorithm 7 Quantum motif clustering via quantum approximate counting and
quantum spectral clustering

Input: A graph $G=(V,E)$, motif $M$ with two anchor nodes and integer $k\geq
1$.

1:Use Algorithm 4 of Lemma 7 on input $G=(V,E)$, motif $M$, some fixed
relative error $\epsilon>0$, and with failure probability at most
$\delta=O(1/n^{3/2})$ to provide adjacency list access to the (all-to-all)
approximate motif graph $\tilde{\mathpzc{G}}$.

2:Apply the algorithm from Corollary 2 to the unnormalized motif Laplacian
$\tilde{\mathpzc{L}}$ by providing query access to $\tilde{\mathpzc{G}}$.

3:return A $k$-partition of $G=(V,E)$ that approximately minimizes the motif
RatioCut.

We note that, by providing query access to the motif graph $\mathpzc{G}$
rather than constructing it explicitly, we lose the ability to detect and
remove isolated vertices in $\mathpzc{G}$. These will now be included in the
graph provided as input to the clustering subroutine, which will almost
certainly assign each isolated vertex to its own cluster. This may impact the
quality of the solutions found by the motif clustering algorithm. However, as
discussed in Section 4, we note that this version of the algorithm should only
be used if $d^{l}$ and the total number of motif instance $\mathpzc{M}$ are
relatively large, in particular $d^{l}=\omega(\sqrt{n})$ and
$\mathpzc{M}=\omega(n^{2}/d)$. In this case, the input graph is quite dense,
and also there are reasonably many motif matches, making it not unlikely that
the number of isolated vertices in $\mathpzc{G}$ will be quite small.

Finally, we should note that for Algorithm 7, we can in general not use the
normalized Laplacian for clustering, since constructing it could mean that we
are dividing by zero due to some vertices possibly being disconnected.

###  6.4 Run-time comparisons

Next, we discuss how the run-time $O(nd^{s-1})$ of the classical algorithm
compares to the run-times of the quantum algorithms introduced in this
section. We will ignore the time it it takes to do $k$-means, which is the
same for all algorithms considered, and we assume is nearly-linear in $n$.

In order to investigate the run-time of our Grover-based Algorithm 3, let us
take the more general starting point and assume that the adjacency lists are
initially not sorted. In this case, we can either pre-process the input graph
(which includes loading the input graph to QRAM if needed), or we can use
Grover search to search through the adjacency lists (assuming we have coherent
access to the input graph).

The run-time of Algorithm 3 depends on the number of motif instances
$\mathpzc{M}$. If we pre-process the input graph, we get a speedup over the
classical algorithm when $\mathpzc{M}=o(nd^{s-1})$, but this speedup is
limited by the time it takes to do the sorting. If
$\mathpzc{M}=\Omega(nd^{s-1})$, there is no speedup at all over the classical
algorithm. In case of coherent access to unsorted adjacency lists of the input
graph, we can also choose not to pre-sort the adjacency lists, but this only
makes sense if the time it takes to run Algorithm 3 without pre-sorting is
faster than the time it takes to sort the adjacency lists. Comparing the upper
bound of $\tilde{O}(\sqrt{nd^{s}\mathpzc{M}})$ for the former to the upper
bound of $O(nd)$ for the latter, we conclude that not pre-sorting is favorable
if $\mathpzc{M}=o\left(\frac{n}{d^{s-2}}\right)$, albeit that what will be
best in practice will depend on how tight these upper bounds are.

The quantum algorithms that use quantum approximate counting are a bit easier
to analyse because they do not depend on $\mathpzc{M}$, nor on whether the
adjacency lists of the input graph are sorted or not, or if we have classical
or coherent access to them, as we can always pre-process the input graph
beforehand. The run-time of Algorithm 6 is $\tilde{O}(nd^{l+\frac{s}{2}-1})$,
which for motifs with $2l<s$ provides a speedup over the classical algorithm.
The run-time of Algorithm 7 is
$\tilde{O}\left(n^{3/2}d^{\frac{s}{2}-1}\right)$, providing a speedup over the
classical algorithm if $\sqrt{nd^{s}}=o(d^{s})$, which will be the case for,
for example, dense graphs.

####  6.4.1 Clique motifs in scale-free networks

Let us investigate the run-times of the quantum motif clustering algorithms
for a class of network that occurs often in practice: so-called scale-free
networks AJB (99); VPSV (02); BB (03); Prž (07); LMvH (09). Such networks have
degree distributions that can be well approximated by a power-law distribution
so that the fraction of vertices of degree $h$ scales as $h^{-\tau}$ for some
$\tau>1$.

As an example, consider motif clustering with the motif being an $s$-clique
with two anchor nodes. We take $s\geq 3$ to be a constant independent of $n$.
For clique motifs the distance between the two anchor nodes is $l=1$.

In JvLS (19), the authors consider the number of $s$-cliques present in power-
law random graphs on $n$ vertices with parameter $\tau\in(2,3)$ (they consider
the so-called “hidden variable” model, see CL (02); BPS (03); BDML (06); BJR
(07)) and find that its expected value is given by
$O(n^{\frac{s}{2}(3-\tau)})$ as $n\to\infty$. This means that for such graphs
$\mathbb{E}[\mathpzc{M}]=O(n^{\frac{s}{2}(3-\tau)})$, where the expectation is
taken over the randomness of the input graph. The maximum degree in these
power-law random graphs is given by $d=n^{1/(\tau-1)}$ BPS (03) (also known as
the “natural cut-off”).

##### Run-time upper bounds

Using the above upper bound for $d$ together with Jensen’s inequality, we
obtain the following upper bound for the expected number of queries to the
graph for Algorithm 3 without pre-sorting the adjacency lists:

$\mathbb{E}\left[\tilde{O}\left(\sqrt{nd^{s}\mathpzc{M}}\right)\right]=\tilde{O}\left(\sqrt{n^{1+\frac{s}{\tau-1}}\mathbb{E}[\mathpzc{M}]}\right)=\tilde{O}\left(n^{\frac{1}{2}+\frac{s}{2}(\frac{1}{\tau-1}+\frac{3-\tau}{2})}\right).$

Similarly, we can obtain upper bounds to the run-times of the other quantum
algorithms. These are given in Table 3.

Algorithm | Expected run-time
---|---
Classical | $O(n^{1+\frac{s-1}{\tau-1}})$
Algorithm 3: quantum-Grover (pre-process) | $\tilde{O}\left(n^{\frac{\tau}{\tau-1}}+n^{\frac{1}{2}+\frac{s}{2}(\frac{1}{\tau-1}+\frac{3-\tau}{2})-\frac{1}{2(\tau-1)}}\right)$
Algorithm 3: quantum-Grover (no pre-process) | $\tilde{O}(n^{\frac{1}{2}+\frac{s}{2}(\frac{1}{\tau-1}+\frac{3-\tau}{2})})$
Algorithm 6: quantum-approximate + classical cluster | $\tilde{O}(n^{1+\frac{s}{2(\tau-1)}})$
Algorithm 7: quantum-approximate + quantum cluster | $\tilde{O}(n^{\frac{3}{2}+\frac{s}{2(\tau-1)}-\frac{1}{\tau-1}})$
Table 3: Expected run-times of motif clustering algorithms when the $n$-vertex
input graph is a power law graph with $\tau\in(2,3)$, and the motif is a
clique of constant size $s$.

##### Comparison of run-time upper bounds

The above (upper bounds for the)141414For the remainder of this section, to
make it easier to read, we will omit the word “upper bound”, and keep in mind
that the word “run-time” actually refers to an upper bound to the run-time.
run-times look somewhat complicated. Let’s compare them to each other to see
which algorithm has the fastest run-time depending on the choice of $s$ and
$\tau\in(2,3)$. Intuitively, we expect that the Grover-based algorithms will
perform well when there are few motif instances — i.e. when
$\mathbb{E}(\mathpzc{M})=O(n^{\frac{s}{2}(3-\tau)})$ is small — which is the
case for $\tau$ close to 3. As $\tau$ decreases, the graph becomes denser
(since $d=n^{\frac{1}{\tau-1}}\rightarrow n$ as $\tau\rightarrow 2$), and we
expect the quantum approximate counting based algorithms to do better. This
intuition turns out to be correct.

First, observe that, since $\tau\in(2,3)$, we have
$1\geq\frac{3}{2}-\frac{1}{\tau-1}$, and therefore quantum-approximate +
quantum cluster is faster than quantum-approximate + classical cluster, and so
we should always use the former given a choice between the two. Second,
comparing the two versions of quantum-Grover, we observe that we should only
_not_ pre-sort if

$\frac{1}{2}+\frac{s}{2}\left(\frac{1}{\tau-1}+\frac{3-\tau}{2}\right)\leq\frac{\tau}{\tau-1}\,,$

which is true only when $s=3$, and $\tau\in[\tau_{1},3)$, where
$\tau_{1}=\frac{5+\sqrt{10}}{3}\approx 2.72$. In particular, for $s\geq 4$, we
should always pre-sort the adjacency lists given the choice between both
quantum-Grover algorithms.

Next, we compare the run-time upper bounds of the competing algorithms for
different values of $s$. For $s\geq 4$, the only two competing algorithms are
quantum-approximate + quantum cluster and quantum-Grover (pre-process). Note
that, in this regime for $s$,

$\frac{3}{2}+\frac{s}{2(\tau-1)}-\frac{1}{\tau-1}\geq\frac{\tau}{\tau-1}\,,$

and therefore quantum-approximate + quantum cluster is always slower than the
time it takes to pre-sort the adjacency lists. Hence, all that remains is to
compare the second term in the run-time of quantum-Grover (pre-process) to the
run-time of quantum-approximate + quantum cluster. After simplifying a bit,
the intersection of the two run-times can be found by solving

$\frac{s}{4}(3-\tau)=1-\frac{1}{2}\frac{1}{\tau-1}$

for $\tau\in(2,3)$ in terms of $s$. The result is

$\tau_{0}(s)=\frac{\sqrt{s^{2}-2s+4}+2s-2}{s},$

which lies in the interval $(2,3)$ for $s\geq 3$.

For the case $s=3$, we first compare quantum-Grover (pre-process) to quantum-
approximate + quantum cluster for $\tau\in(2,\tau_{1})$. In this interval, we
want to use quantum-approximate + quantum cluster for $\tau\in(2,\tau_{0})$
and quantum-Grover (pre-process) for $\tau\in(\tau_{0},\tau_{1})$, where
$\tau_{0}=\tau_{0}(s=3)=\frac{4+\sqrt{7}}{3}\approx 2.22$. Finally, for
$\tau\in(\tau_{1},3)$, quantum-Grover (no pre-process) has a faster run-time
than quantum approximate + quantum cluster.

##### Run-times of fastest algorithms

In short, out of all quantum algorithms presented, we obtain the smallest run-
time for quantum-approximate + quantum cluster for $\tau\in(2,\tau_{0}(s))$.
The run-time for quantum-Grover (pre-process) is smallest for
$\tau\in(\tau_{0}(s),3)$, except for $s=3$, in which case quantum-Grover (no
pre-process) has an even smaller run-time for $\tau\in(\tau_{1},3)$.

As an example, in Table 4 we list the explicit upper bounds to the run-times
for the fastest algorithms as given above for the cases of $s=3$, $s=4$, and
$s=5$, in the limits of $\tau\rightarrow 2$ and $\tau\rightarrow 3$, and
compare them to the run-time of the classical algorithm, (using the upper
bound for the maximum degree given by the natural cut-off
$d=n^{\frac{1}{\tau-1}}$).

|  | Classical | Quantum |
---|---|---|---|---
|  | run-time | run-time | fastest algorithm
$s=3$ | $\tau\rightarrow 2$ | $O(n^{3})$ | $\tilde{O}(n^{2})$ | quantum-approximate + quantum cluster
| $\tau\rightarrow 3$ | $O(n^{2})$ | $\tilde{O}(n^{1.25})$ | quantum-Grover (no pre-process)
$s=4$ | $\tau\rightarrow 2$ | $O(n^{4})$ | $\tilde{O}(n^{2.5})$ | quantum-approximate + quantum cluster
| $\tau\rightarrow 3$ | $O(n^{2.5})$ | $\tilde{O}(n^{1.5})$ | quantum-Grover (pre-process)
$s=5$ | $\tau\rightarrow 2$ | $O(n^{5})$ | $\tilde{O}(n^{3})$ | quantum-approximate + quantum cluster
| $\tau\rightarrow 3$ | $O(n^{3})$ | $\tilde{O}(n^{1.5})$ | quantum-Grover (pre-process)
Table 4: Run-times of the classical and fastest quantum motif clustering
algorithms in expectation over the randomness of the $n$-vertex input power-
law graph, where the motif is a clique of size $s\in\\{3,4,5\\}$. If we need
to pre-process because our access to the input graph is classical, then for
$s=3$ and $\tau\rightarrow 3$ the quantum run-time becomes $O(n^{1.5})$

Note that we get a quadratic speedup on the run-time of the entire algorithm
for the case $s=5,\tau\rightarrow 3$. This happens because, for
$\tau\rightarrow 3$, $\mathpzc{M}\rightarrow O(1)$, and pre-processing the
input graph takes as much time as the Grover search: both are given by
$\tilde{O}(n^{1.5})$.

##  7 Clustering on an approximate graph

In this section we provide analytical and numerical evidence to support the
claim that performing spectral clustering using the Laplacian or the
normalized Laplacian, respectively, on an approximation of a graph yields
similar clusters to those that would be obtained by clustering on the actual
graph. This is of particular relevance to us since our use of quantum
approximate counting in Algorithms 6 and 7 produces only an approximation of
the motif graph, with each edge weight approximated up to some small constant
relative error.

We will consider the reasonably general case in which we wish to perform
spectral clustering on some graph $G=(V,E)$ with real-valued adjacency matrix
$A$ with non-negative coefficients, but where we only have access to an
$\epsilon$-approximation $\tilde{A}$ of $A$, in the sense that
$(1-\epsilon)A_{uv}\leq\tilde{A}_{uv}\leq(1+\epsilon)A_{uv}$ for all $u,v\in
V$. Note that $A_{uv}=0$ if and only if $\tilde{A}_{uv}=0$, so $A$ and
$\tilde{A}$ have the same edge set $E$ (as long as $0<\epsilon<1$). Our
central question is whether performing spectral clustering on the approximate
graph yields clusters that are similar to the clusters obtained by performing
spectral clustering on $G$ itself.

###  7.1 Approximating the unnormalized Laplacian

If we choose to cluster using the (unnormalized) Laplacian, then it turns out
that we can answer the question above positively. That is: if we perturb the
weights on the edges of a weighted graph by adding a multiplicative error, the
spectrum of the Laplacian is preserved up to a similar multiplicative error.

To make this precise, we first introduce some extra notation. Let $G=(V,E)$ be
a undirected graph with symmetric real-valued adjacency matrix $A$ with non-
negative coefficients. For a vertex $u\in V$, we define the indicator vector
$1_{u}$ to be:

$1_{u}(v):=\begin{cases}1&\text{if}\quad v=u,\\\
0&\text{otherwise}.\end{cases}$

Now, can write the Laplacian $L=D-A$, where $D$ is the weighted degree matrix
of $A$ (with diagonal coefficients $D_{uu}=\sum_{v\in V}A_{uv}$ for every
$u\in V$), as

$L=\sum_{\\{u,v\\}\in E}A_{uv}L_{\\{u,v\\}},$

where for each edge $\\{u,v\\}\in E$,
$L_{\\{u,v\\}}:=(1_{u}-1_{v})(1_{u}-1_{v})^{T}$. Then we have the following
result.

######  Lemma 8.

Let $A$ and $\tilde{A}$ both be symmetric adjacency matrices of a graph
$G=(V,E)$ with real-valued non-negative weights. Let $D$ and $\tilde{D}$ be
the corresponding weighted degree matrices, and $L=D-A$ and
$\tilde{L}=\tilde{D}-\tilde{A}$ the corresponding Laplacians, and let
$\epsilon>0$. Then, if for all $u,v\in V$ we have
$(1-\epsilon)A_{uv}\leq\tilde{A}_{uv}\leq(1+\epsilon)A_{uv}$, it follows that

$(1-\epsilon)L\preceq\tilde{L}\preceq(1+\epsilon)L.$ (8)

###### Proof.

We need to show that both $\tilde{L}-L+\epsilon L$ and $L-\tilde{L}+\epsilon
L$ are positive semi-definite. The inequalities
$(1-\epsilon)A_{uv}\leq\tilde{A}_{uv}\leq(1+\epsilon)A_{uv}$ for every $u,v\in
V$ imply that there exists a matrix $\gamma$ such that
$\tilde{A}_{uv}-A_{uv}=\epsilon A_{uv}\gamma_{uv}$ with $\gamma_{uv}\in[-1,1]$
for all $u,v\in V$. Hence,

$\tilde{L}-L+\epsilon L=\sum_{(u,v)\in E}(\tilde{A}_{uv}-A_{uv}+\epsilon
A_{uv})L_{\\{u,v\\}}=\sum_{(u,v)\in E}\epsilon
A_{uv}(\gamma_{uv}+1)L_{\\{u,v\\}},$

which is the Laplacian of a graph $G=(V,E)$ where each edge $(u,v)\in E$ has
weight $\epsilon A_{uv}(\gamma_{uv}+1)\geq 0$, and hence is itself a positive
semi-definite matrix. Likewise,

$L-\tilde{L}+\epsilon L=\sum_{(u,v)\in E}\epsilon
A_{uv}(1-\gamma_{uv})L_{\\{u,v\\}},$

is also the Laplacian of a graph $G=(V,E)$ where each edge $(u,v)\in E$ has
weight $\epsilon A_{uv}(1-\gamma_{uv})\geq 0$, and therefore is also positive
semi-definite. ∎

###  7.2 Approximating the normalized Laplacian

A natural question to ask is if a similar result to that of Lemma 8 also holds
for the normalized Laplacian. That is, does the statement: for every
$\delta>0$ there exist a $\epsilon>0$, such that if $A$ and $\tilde{A}$
satisfy $(1-\epsilon)A_{uv}\leq\tilde{A}_{uv}\leq(1+\epsilon)A_{uv}$ for every
$u,v\in V$, with corresponding Laplacian $L=D-A$, approximate laplacian
$\tilde{L}=\tilde{D}-\tilde{A}$ and corresponding normalized Laplacians given
by

$L_{\operatorname{norm}}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\quad\text{and}\quad\tilde{L}_{\operatorname{norm}}=\tilde{D}^{-\frac{1}{2}}\tilde{L}\tilde{D}^{-\frac{1}{2}},$
(9)

then

$(1-\delta)L_{\operatorname{norm}}\preceq\tilde{L}_{\operatorname{norm}}\preceq(1+\delta)L_{\operatorname{norm}}\,;$
(10)

hold? (Note that for Lemma 8 we have $\epsilon=\delta$.)

First, we observe that, if we choose to normalize the approximate Laplacian
with the true weighted degree matrix $D^{-\frac{1}{2}}$ rather than the
approximate weighted degree matrix $\tilde{D}^{-\frac{1}{2}}$, then the above
statement does hold (for $\epsilon=\delta$).

######  Lemma 9.

Let $A$ and $\tilde{A}$ be adjacency matrices of a graph $G=(V,E)$ with real-
valued non-negative weights, and let $\epsilon>0$. Now, if
$(1-\epsilon)A_{uv}\leq\tilde{A}_{uv}\leq(1+\epsilon)A_{uv}$ holds for all
$u,v\in V$, then the normalized Laplacian
$L_{\operatorname{norm}}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$ and the
approximate Laplacian normalized with true degree matrix
$L_{\operatorname{norm}}^{\prime}=D^{-\frac{1}{2}}\tilde{L}D^{-\frac{1}{2}}$,
where $L=D-A$, and $\tilde{L}=\tilde{D}-\tilde{A}$, are related by

$(1-\epsilon)L_{\operatorname{norm}}\preceq
L_{\operatorname{norm}}^{\prime}\preceq(1+\epsilon)L_{\operatorname{norm}}.$
(11)

###### Proof.

Eq. (11) follows directly from Eq. (8), and the fact that, if $X\succeq 0$,
then $X=B^{\dagger}B$ for some matrix $B$, and therefore
$D^{-\frac{1}{2}}XD^{-\frac{1}{2}}=\left(BD^{-\frac{1}{2}}\right)^{\dagger}BD^{-\frac{1}{2}}\succeq
0$. ∎

As a consequence, for graphs for which we know the motif degrees exactly, we
can use quantum counting to compute the matrix
$L_{\operatorname{norm}}^{\prime}$, which in turn can be used for $k$-means
spectral clustering with $\epsilon$-approximate eigenvectors. Unfortunately,
if we do not know the motif degrees exactly, then quantum counting does not
offer any additional benefit over Algorithm 2, since using quantum counting to
count all the degrees exactly has the same complexity as finding all motif
instances.

Next, we will show that Eq. (10) does not hold in general. Specifically, Eq.
(10) does not hold unless, coincidentally, all perturbations are such that
$D=c\tilde{D}$ for some real-valued constant $c$. Consequently, we do not have
the same guarantees for the approximate normalized Laplacian as we do for the
approximate (unnormalized) Laplacian.

To this end, let $1>\delta>0$. We will show that, no matter how small we pick
$\epsilon>0$, if $L_{\operatorname{norm}}$ are
$\tilde{L}_{\operatorname{norm}}$ as described in and above Eq. (9), we do not
have that

$(1-\delta)L_{\operatorname{norm}}\preceq\tilde{L}_{\operatorname{norm}}\preceq(1+\delta)L_{\operatorname{norm}}\,.$
(12)

In particular, we will show that

$\tilde{L}_{\operatorname{norm}}-(1-\delta)L_{\operatorname{norm}}\succeq 0\ $
(13)

does not hold regardless of how small we pick $\epsilon>0$.

We know that $\mathbf{v}=\sqrt{D}\mathbf{1}$ is a 0-eigenvector of
$L_{\operatorname{norm}}$, and likewise
$\mathbf{\tilde{v}}=\sqrt{\tilde{D}}\mathbf{1}$ a 0-eigenvector of
$\tilde{L}_{\operatorname{norm}}$151515$\mathbf{1}$ is a 0-eigenvector of the
unnormalized Laplacian $L$, and then we have that
$L_{\operatorname{norm}}\sqrt{D}\mathbf{1}=D^{-1/2}LD^{-1/2}\sqrt{D}\mathbf{1}=0$.
Now, let us first assume that the underlying graph for $A$ is connected. In
that case, $\mathbf{v}$ is the only 0-eigenvector of
$L_{\operatorname{norm}}$, and all other eigevectors have an eigenvalue that
is stricly positive. Consequently, as long as $\mathbf{v}$ and
$\mathbf{\tilde{v}}$ are not linearly dependent, which happens when the degree
matrices $D$ and $\tilde{D}$ are not constant multiples of each other, we have

$\mathbf{\tilde{v}}^{T}\left[\tilde{L}_{\operatorname{norm}}-(1-\delta)L_{\operatorname{norm}}\right]\mathbf{\tilde{v}}=-(1-\delta)\mathbf{\tilde{v}}^{T}L_{\operatorname{norm}}\mathbf{\tilde{v}}<0\,.$

This implies that the first inequality above does not hold for general
$\epsilon>0$, regardless of how small we choose $\delta$, unless all
perturbations are such that $D=c\tilde{D}$ for some constant $c>0$.

If the graph is not connected, we can just restrict ourselves to a single
connected component of $A$, and repeat the argument for that connected
component.

The above observation essentially rules out obtaining strong guarantees in the
case of clustering on approximate normalized Laplacians. However, in the next
section we provide numerical evidence to suggest that, in fact, we can
actually use the approximate normalized Laplacian for clustering in practice.

###  7.3 Numerical simulations for the approximate normalized Laplacian

Even though we cannot obtain theoretical guarantees in the case of clustering
via the normalized Laplacian when the weights of the graph are only known
approximately, we give evidence to suggest that, in practice, the situation is
similar to the unnormalized case. Recall that in the latter, the spectrum of
the graph Laplacian is preserved up to small constant multiplicative error
when the weights on the edges of the graph are perturbed by a similarly small
constant multiplicative error (see Lemma 8), and thus spectral clustering will
perform similarly on the original and the perturbed graph.

In what follows, we study empirically what happens to the quality of the
clusters produced by spectral clustering on the normalized Laplacian when we
perturb the edges of weighted, randomly generated graphs. In particular, we
consider weighted undirected graphs $G=(V,E)$ with edge weights $\\{w_{e}|e\in
E\\}$, and their ‘perturbed’ versions with edge weights
$\\{w^{\prime}_{e}|e\in E\\}$, where each $w^{\prime}_{e}$ is drawn uniformly
at random from $[(1-\epsilon)w_{e},(1+\epsilon)w_{e}]$ for some relative error
$\epsilon\in[0,1]$.

We find that, in general, only large values of $\epsilon$ yield significant
differences in the quality of clusters obtained by spectral clustering applied
to the normalized Laplacian of the graph. As an illustration, consider the
graph shown in Figure 4, a commonly used test-case for demonstrations of
clustering algorithms, which consists of two concentric circles of points
embedded in $\mathbb{R}^{2}$. Here we added edges between nearby
points,161616More precisely, we generated data points in $\mathbb{R}^{2}$
representing two concentric circles using the Scikit-learn Python library,
before scaling them to remove the mean (i.e. set it to zero) and obtain unit
variance. Edges were then added between points $\mathbf{x}$ and $\mathbf{y}$
if their Euclidean distance satisfied $d(\mathbf{x},\mathbf{y})\leq 0.6$, and
given weight $\frac{20}{d(\mathbf{x},\mathbf{y})}$. with a weight that scales
inversely proportional to their Euclidean distance, and then applied spectral
clustering to the normalized Laplacian of the resulting graph. Only after
introducing a relative error of $\epsilon=0.6$ did we find that the resulting
clusters differed at all from those found on the original graph. We note that
this graph was even handpicked to demonstrate that perturbations can
qualitatively change the clusters obtained from spectral clustering – in fact
most graphs we generated were much more resilient to perturbations! This is
almost certainly due to the fact that these graphs are ‘well clusterable’ in
the sense that the two clusters are easily (albeit non-linearly) separable in
a low-dimensional space.

Figure 4: Effect of applying relative errors to the weights on the edges of a
graph and then applying spectral clustering ($k=2$) to the resulting
normalized Laplacian. (a) Original graph. (b) $\epsilon=0.6$. (c)
$\epsilon=0.75$. (d) $\epsilon=0.9$. (e) $\epsilon=1$.

To more precisely quantify the effect of relative errors on graph clustering
algorithms, we consider the difference in conductance (see Section 3) achieved
by spectral clustering on the original and perturbed graphs. More precisely,
let $\\{W_{i}\\}_{i=1}^{k}$ be the partition (i.e. set of clusters) output by
applying spectral clustering to the original graph, and
$\\{\tilde{W}_{i}\\}_{i=1}^{k}$ the partition found by applying it to the
perturbed graph. Then we use the quantity

$\phi_{\text{diff}}:=\phi_{G}(\tilde{W}_{1},\dots,\tilde{W}_{k})-\phi_{G}(W_{1},\dots,W_{k})$

as a measure of the difference in quality between the two partitions. Note
that the conductance for both partitions is computed relative to the
_original_ graph $G$ (i.e. without perturbed weights). Since spectral
clustering aims to minimize the conductance, this is the natural quantity to
capture the difference in quality of two different partitions of the same
graph. If the partitions output by spectral clustering on the perturbed graph
are worse, then $\phi_{\text{diff}}$ will be positive; if they happen to be
better, it will be negative.

$n$ | Cluster graph | LFR
---|---|---
$600$ | $-0.001\pm 0.019$ | $0.004\pm 0.03$
$800$ | $0.0\pm 0.021$ | $-0.0\pm 0.027$
$1000$ | $-0.001\pm 0.004$ | $0.001\pm 0.031$
$1200$ | $0.001\pm 0.013$ | $-0.0\pm 0.024$
$1400$ | $0.001\pm 0.016$ | $-0.002\pm 0.039$
$1600$ | $0.0\pm 0.001$ | $-0.0\pm 0.027$
$1800$ | $0.001\pm 0.016$ | $-0.005\pm 0.028$
$2000$ | $-0.002\pm 0.022$ | $0.003\pm 0.036$
Table 5: Average and standard deviation of $\phi_{\text{diff}}$ vs $n$ for 200
randomly generated graphs with fixed relative error $\epsilon=0.1$.

As test cases, we consider two types of random graphs: ‘cluster’ graphs, which
are created by generating random points in $\mathbb{R}^{2}$ centred around
some number of fixed centres, and then adding edges between nearby points with
weights that scale inversely proportional to the Euclidean distance between
them; and so-called LFR-graphs LFR (08), a commonly used family of random
graphs used to test clustering and community-detection algorithms. For all
tests we set $k=5$ (and for the cluster graphs, generated data centred around
$k=5$ fixed centres). Table 5 shows the average value of $\phi_{\text{diff}}$
for a range of sizes of randomly generated graphs of both types for a fixed
relative error of $\epsilon=0.1$. We find that, regardless of graph size, the
perturbation has essentially no effect on the quality of clusters found.

Figure 5: Effect of graph size and relative error on the quality of clusters
found by spectral clustering on LFR graphs. (a) $\phi_{\text{diff}}$ vs. $n$
for fixed $\epsilon=0.1$ with 200 random graphs per value of $n$; (b)
$\phi_{\text{diff}}$ vs. relative error $\epsilon$ for fixed $n=2000$ and 500
random graphs per value of $\epsilon$.

Next we consider the effect of increasing relative error on the quality of
clusters found by spectral clustering. Figure 5 shows, for randomly generated
LFR graphs, the effect of increasing the graph size $n$ (left figure) and of
increasing the relative error $\epsilon$ (right figure) on the value of
$\phi_{\text{diff}}$. It is clear that the clusters do not become worse as $n$
increases (for fixed $\epsilon=0.1$), but do become worse as $\epsilon$
increases (here for fixed $n=2000$). This suggests that, as in the case of
clustering using the unnormalized Laplacian, it suffices to choose a small,
but _constant_ relative error $\epsilon$ to obtain good quality clusters via
the approximate normalized Laplacian.

##  8 Conclusion

We have presented three quantum algorithms that provide a speedup over
classical methods for performing motif clustering. Our speedup relies on
quantum routines for finding or approximately counting the number of motif
instances in the to-be-clustered graph. In the case of approximate quantum
counting, we show that approximations up to only a constant relative error are
sufficient for motif clustering using the unnormalized Laplacian of the motif
graph, which allows us to obtain a quantum speedup in many cases.

This observation in fact holds more generally: if we perturb the weights of a
graph with some constant relative error, then the graph can still be used to
perform spectral clustering via the unnormalized Laplacian, which produces
clusters whose RatioCut is close to the RatioCut that would have been obtained
by performing spectral clustering on the unperturbed graph. It is interesting
that the effect of the perturbation on the quality of the obtained clustering
is independent of the size of the graph.

Our argument for the above claim fails, however, for normalized Laplacians: in
this case, the spectrum of the Laplacian corresponding to the perturbed graph
does not preserve the spectral structure of the unperturbed graph. However,
when applied to randomly generated benchmark graphs, we find numerically that
clustering using the normalized Laplacian of the perturbed graph does in fact
generate clusters for which the conductance is close to the conductance of the
clusters obtained by performing spectral clustering via the normalized
Laplacian of the unperturbed graph, again independent of the size of the
graph. An interesting open question would be to find out why, and under what
conditions, clustering with the normalized Laplacian of the perturbed graph
can be used to obtain a clustering with low conductance in the original graph.

In Appendix D, we discuss motif clustering of a graph $G$ using a motif with
more than two anchor nodes. In particular, we show that clustering with a
motif with three anchor nodes is equivalent to clustering with a weighted
combination of two-anchor-node motifs. We continue to argue that, for motifs
$M$ with four or more anchor nodes, a weighted combination of two-anchor-node
motifs $M_{1},\ldots,M_{q}$, corresponding to the motifs obtained by taking
all possible pairs of anchor nodes of $M$, should be used in place of $M$
itself. The reason is that the motif graph $\mathpzc{G}$ constructed from $G$
and $M$ is itself a graph, and is therefore only capable of expressing
pairwise relationships between vertices that occur as anchor nodes – which is
exactly what the motifs $M_{1},\ldots,M_{q}$ represent – and not higher-order
relationships between sets of more than two vertices. If one wants the latter,
then instead of constructing the motif graph $\mathpzc{G}$, one should
construct a _hypergraph_ where the hyperedges represent the multi-vertex
relationships expressed by $M$, and cluster on the hypergraph instead.

There are existing classical algorithms for clustering on hypergraphs: see for
example TMIY (20) and references therein for a clustering method based on the
so-called ‘personalized pagerank’, which itself is based on the stationary
distribution of a random walk on the hypergraph. An interesting open question
would be to investigate if quantum walks can provide a speedup for the
hypergraph clustering algorithm of TMIY (20).

##### Acknowledgements

We would like to thank Ian Marshall for his active participation in the early
stages of the project, and for the many insights he had during our regular
meetings. We would also like extend our gratitude to Simon Apers for his
useful feedback and for pointing out that there are cases where not
constructing the motif graph explicitly is the most efficient approach, as
well as to Ronald de Wolf for reading an earlier version of this manuscript
and providing feedback. In addition, we would like to thank Johan van
Leeuwarden for clarifying a result in JvLS (19), and Ton Poppe and Edo van
Uitert at ABN AMRO for fruitful discussions on potential applications of
quantum computing in transaction network analysis. Finally, we would like to
thank an anonymous reviewer for pointing out a flaw in our proof of Lemma 11
and suggesting a fix.

##### Funding

IN is a part of the DisQover project: a collaboration between QuSoft and ABN
AMRO, and is partially funded by ABN AMRO. CC was supported by QuantERA
project QuantAlgo 680-91-034. FL was supported by the Gravitation-grant
NETWORKS-024.002.003 from the Dutch Research Council (NWO).

##  Appendix A Motif isomorphisms

When using Algorithms 3, 6 or 7, we count the number of tree walks with the
property that the graph $G$ restricted to the vertex set of the constructed
tree has the same edge structure as the motif $M$. Since each tree-walk is in
one-to-one correspondence with a map $\iota:V_{M}\rightarrow V$, this means we
are actually counting motif _assignments_. However, when constructing the
motif graph, given two vertices $u,v\in V$, we instead want to count the
number of motif _instances_ that have $u$ and $v$ as anchor nodes, and
therefore we must know how to obtain the latter from the former171717See
Section 3.1 for the definitions of motif assignments and motif instances, and
for what it means for a motif instance to have a vertex as an anchor node..

As we will show in Lemma 10 below, every motif instance corresponds to a
constant number $S_{M}$ of motif assignments $\iota:V_{M}\rightarrow V$, and
this constant $S_{M}$ only depends on the motif $M$ itself, and can be
computed ahead of time. More precisely, $S_{M}$ is equal to the number of
graph isomorphisms $f:V_{M}\rightarrow V_{M}$ of $M$ with the property that
anchor nodes get mapped to anchor nodes: i.e. $f(V_{A})=V_{A}$. It will be
convenient to give such graph isomorphisms a name. In particular, for a motif
$M$ with vertex set $V_{M}$ and anchor node set $V_{A}\subseteq V_{M}$, we say
that a graph isomorphism $f:V_{M}\rightarrow V_{M}$ is a _motif isomorphism_
if $f$ maps anchor nodes to anchor nodes, i.e. $f(V_{A})=V_{A}$. In Fig. 6, we
compute $S_{M}$ for two example motifs.

Figure 6: Two example motifs. For motif (a), there are $S_{M}=12$ motif
isomorphisms, because there are six ways of interchanging the non-anchor
nodes, and for each way of interchanging the non-anchor nodes we can choose to
leave the anchor nodes invariant, or interchange them. For motif (b) the only
graph isomorphism of the motif is the one that exchanges the left two non-
anchor nodes, so $S_{M}=2$.

######  Lemma 10.

Let $G=(V,E)$ be an unweighted graph, $M=(V_{M},V_{A},E_{M})$ a motif, and let
$S_{M}$ be the number of motif isomorphisms of $M$. Then every motif instance
of $G$ consists of exactly $S_{M}$ equivalent motif assignments
$\iota:V_{M}\rightarrow V$.

###### Proof.

We need to show that (i) any two motif assignments that correspond to the same
instance are related by a motif isomorphism $f:V_{M}\rightarrow V_{M}$, and
(ii) that for any motif assignment $\iota$, $\iota\circ f$ is equivalent to
$\iota$ for any motif isomorphism $f:V_{M}\rightarrow V_{M}$.

For (i), let $\iota$ and $\iota^{\prime}$ be two motif assignments that
correspond to the same motif instance, that is
$\iota(V_{M})=\iota^{\prime}(V_{M})$, and
$\iota(V_{A})=\iota^{\prime}(V_{A})$. Let $H$ be the subgraph of $G$ obtained
by restricting $G$ to the image of $\iota$ (or $\iota^{\prime}$; both have the
same image). Now, $f=\iota^{-1}\circ\iota^{\prime}:V_{M}\rightarrow V_{M}$ is
a composition of graph isomorphisms, hence a graph isomorphism, and trivially
we have $f(V_{A})=V_{A}$. Consequently, $\iota^{\prime}=\iota\circ f$, for
some motif isomorphism $f$ of $M$. For (ii), given a motif isomorphism
$f:V_{M}\rightarrow V_{M}$ and a motif assignment $\iota:V_{M}\rightarrow V$,
observe that $\iota^{\prime}=\iota\circ f:V_{M}\rightarrow V$ is a motif
assignment, since it is a graph isomorphism onto its image, and also we have
$\iota^{\prime}(V_{M})=\iota(f(V_{M}))=\iota(V_{M})$ as well as
$\iota^{\prime}(V_{A})=\iota(f(V_{A}))=\iota(V_{A})$, so both $\iota$ and
$\iota^{\prime}$ correspond to the same motif instance. ∎

Consequently, when constructing the motif graph $\mathpzc{G}$, for each
$u,v\in V$ we can use Algorithm 3 to count the number of motif assignments
$\iota:V_{M}\rightarrow V$ with $u,v\in\iota(V_{A})$, and then divide by
$S_{M}$ to obtain $\mathpzc{A}_{uv}$: the number of motif instances with $u$
and $v$ as anchor nodes.

Similarly, if we are using Algorithms 6 or 7, which employ tree walks starting
from two fixed anchor nodes (say $a$ and $b$) to count motif assignments,
rather than dividing by $S_{M}$, we have to divide by the number
$S_{M}^{(a,b)}$ of motif isomorphisms that leave the two anchor nodes $a$ and
$b$ fixed. Since Algorithms 6 or 7 assume the motif has two anchor nodes
(which will be $a$ and $b$), $S_{M}^{(a,b)}$ is the number of isomorphisms of
$M$ that permute non-anchor nodes amongst each other. Like $S_{M}$,
$S_{M}^{(a,b)}$ only depends on the motif itself and can be computed in
advance.

Note that the group of motif isomorphisms as well as the subgroup of motif
isomorphisms that leave two given anchor nodes fixed are both subgroups of the
permutation group on $s$ vertices. In particular, because we take $s$ to be
constant, so are $S_{M}$ and $S_{M}^{(a,b)}$, and therefore the overhead
coming from the fact that we are counting motif assignments rather than motif
instances is a constant multiplicative overhead that does not affect the
complexity of Algorithms 3, 6 or 7.

##  Appendix B Motif graph cuts for two-anchor-node motifs

Let $G=(V,E)$ be an unweighted graph with $|V|=n$, $W\subset V$ a subset of
the vertex set $V$ of $G$, $M=(V_{M},E_{M},V_{A})$ a motif with two anchor
nodes: $V_{A}=\\{a,b\\}$, and $x:V\rightarrow\\{-1,1\\}^{n}$ the indicator
function of $W$ that assumes the value 1 for vertices in $W$, and $-1$ for
vertices outside $W$. If $\mathpzc{G}$ is the motif graph constructed from $G$
and $M$, then $\text{cut}_{(G,M)}(W)$ is equal to
$\text{cut}_{\mathpzc{G}}(W)$.

Indeed, following the proof technique from BGL (16), we get the following
equalities:

$\displaystyle\text{cut}_{(G,M)}(W)$
$\displaystyle=\frac{1}{4}\sum_{\iota\in\mathcal{I}}(x_{\iota(a)}-x_{\iota(b)})^{2}$
$\displaystyle=\frac{1}{4}\sum_{\iota\in\mathcal{I}}\left(x_{\iota(a)}^{2}+x_{\iota(b)}^{2}-x_{\iota(a)}x_{\iota(b)}-x_{\iota(b)}x_{\iota(a)}\right)$
$\displaystyle=\frac{1}{4}\left(x^{T}\mathpzc{D}x-x^{T}\mathpzc{A}x\right)$
$\displaystyle=\frac{1}{4}x^{T}\mathpzc{L}x$
$\displaystyle=\text{cut}_{\mathpzc{G}}(W),$

where $\mathpzc{A}$, $\mathpzc{D}$ and $\mathpzc{L}=\mathpzc{D}-\mathpzc{A}$
are the adjacency matrix, degree matrix and Laplacian of $\mathpzc{G}$
respectively. Note that the factor 4 that appears in the one to last line to
compensate for the factor $\frac{1}{4}$ arises because the indicator function
$x$ takes values in $\\{-1,1\\}$ rather than $\\{0,1\\}$.

##  Appendix C Pre-processing the input graph

All our algorithms require coherent access to the adjacency lists of the input
graph. Moreover, the algorithms based on quantum approximate counting in
Section 6.3 assume that the adjacency lists of the input graph are sorted. If
any of these conditions are not met, then we have to pay additional costs up
front to pre-process the input graph, meaning that we have to either load the
graph to QRAM, sort all adjacency lists, or do both. In this section we
discuss what effect pre-processing the input graph has on the run-times of the
algorithms presented in this work.

Let $G$ be the $n$-vertex input graph to which we have adjacency list access,
with maximum degree $d$. Let $M$ be the $s$-vertex motif that we want to use
to cluster $G$ with. If we have classical access to the input graph, then we
first have to load it to QRAM in time $O(nd)$. If we have coherent access to
the input graph, but the adjacency lists are not sorted, then we have two
options: sort all adjacency lists beforehand in $\tilde{O}(nd)$ time, or keep
the lists unsorted, in which case finding an element in an adjacency list
takes $O(d)$ classically, or $\tilde{O}(\sqrt{d})$ using Grover search.

Recall that $s\geq 3$, as $s=2$ implies the motif is an edge, in which case
there is no point in doing motif clustering. Also, the distance $l$ (number of
edges) between any two anchor nodes satisfies $l\geq 1$.

##### Classical

The classical algorithm of Benson et al. BGL (16) is happy to pay
$\tilde{O}(nd)$ up front to sort the adjacency lists, as this always takes
less time than the time it takes to find all motif instances. Hence, including
pre-sorting the adjacency lists, the total run-time remains

$\tilde{O}(nd^{s-1}+T_{k\text{-}\mathrm{means}})$

for the entire classical $k$-means motif spectral clustering algorithm.

##### Quantum via Grover search

Given classical access, we have to pre-process the input graph beforehand in
time $\tilde{O}(nd)$, resulting in an expected run-time of

$\tilde{O}(nd+\sqrt{nd^{s-1}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})\,.$

If we are given coherent access, and the adjacency lists are sorted, then we
have an expected run-time of

$\tilde{O}(\sqrt{nd^{s-1}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})\,.$

If we have coherent access but the adjacency lists are unsorted, and we choose
not to sort them in advance but use Grover search instead to check if and
where a given node in a given motif instance occurs in the adjacency list of
another node in the motif instance (at the cost of an extra factor of
$\tilde{O}(\sqrt{d})$), then total expected run-time becomes

$\tilde{O}(\sqrt{nd^{s}\mathpzc{M}}+T_{k\text{-}\mathrm{means}})\,.$

##### Quantum via approximate counting and classical spectral clustering

Since $s\geq 3$ and $l\geq 1$, we have that $l+\frac{s}{2}-1>1$, and therefore
pre-processing the input graph in time $\tilde{O}(nd)$ does not affect the
complexity of version of quantum motif clustering. The expected run-time of
the algorithm including pre-processing remains

$\tilde{O}(nd^{l+\frac{s}{2}-1}+T_{k\text{-}\mathrm{means}}).$

##### Quantum via approximate counting and quantum spectral clustering

As before, we can pre-process the input graph in time $\tilde{O}(nd)$ without
changing the run-time of the algorithm: indeed, since $s\geq 3$,
$nd\leq\sqrt{n^{3}d}\leq\sqrt{n^{3}d^{s-2}}$. Therefore, the expected run-time
of this algorithm including pre-processing is given by

$\tilde{O}\left(\sqrt{n^{3}d^{s-2}}+T_{k\text{-}\mathrm{means}}\right).$

##  Appendix D Higher-order motifs

Next, we consider more closely the role of anchor nodes. Recall from Section
3.2 that anchor nodes in the motif are the nodes that determine which graph
cuts count as a motif cut and which do not. For motifs with two anchor nodes,
the motif itself expresses a pairwise relation between both of its anchor
nodes, and motif clustering can be thought of as clustering the original graph
after applying some kind of filter to it: a filter that removes all
connections except those that fit the motif pattern, see Fig 1.

We can also perform motif clustering for motifs with more than two anchor
nodes, and as BGL (16) show, doing so makes sense also for motifs with three
anchor nodes. At first, it seems that a motif with three anchor nodes
expresses relationships between three vertices. However, by construction the
motif graph is still a graph, which captures only pairwise relationships. This
begs the question: what is the interpretation of clustering using a motif with
three anchor nodes? In the sections that follow, we address this question in
detail.

###  D.1 Multiple motifs

Recall from the construction of the motif graph that we add $+1$ to the weight
of every edge $(u,v)$ of the motif graph $\mathpzc{G}$ for every motif
instance in $G$ with $u$ and $v$ as anchor nodes. This suggests that the motif
graph obtained from a motif with multiple anchor nodes can be seen as a sum of
two-anchor-node motif graphs: one for each pair of anchor nodes in the
original motif. In the next subsection, we will argue that clustering using a
motif with three anchor nodes is equivalent to clustering based on a
combination of motifs with two anchor nodes. Before we can make this statement
precise, we first follow the supplementary material of Benson et al. BGL (16)
in order to explain what it means to use motif clustering based on a
collection of motifs181818This is also how functional motifs can be included
in the formalism..

Given motifs $M_{1},\ldots,M_{q}$, coefficients
$\alpha_{1},\ldots,\alpha_{q}\in\mathbb{R}$ such that $\alpha_{j}>0$ for all
$j\in[q]$, and a vertex subset $W\subset V$, we can consider weighted motif
cuts

$\text{cut}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W):=\sum_{j=1}^{q}\alpha_{j}\text{cut}_{(G,M_{j})}(W)\,,$

and the weighted motif volume

$\text{vol}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W):=\sum_{j=1}^{q}\alpha_{j}\text{vol}_{(G,M_{j})}(W)\,.$

We can also define the corresponding weighted motif conductance

$\phi_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W):=\frac{\text{cut}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W)}{\text{vol}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W)}\,.$

and weighted motif ratio cut

$\text{RatioCut}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W):=\frac{\text{cut}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W)}{|W|}\,,$

which naturally extend to partitions $W_{1},\ldots,W_{k}$ of $V$ as follows:

$\phi_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W_{1},\ldots,W_{k}):=\sum_{i=1}^{k}\phi_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W_{i})\,,$

for weighted motif conductance, and

$\text{RatioCut}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W_{1},\ldots,W_{k}):=\sum_{i=1}^{k}\text{RatioCut}_{(G,\\{\alpha_{j},M_{j}\\}_{j=1}^{q})}(W_{i})\,,$

for weighted motif ratio cut.

Now, if we are interested in finding partitions of the vertex set $V$ of $G$
that approximately minimize the weighted motif conductance or weighted motif
ratio cut in $G$ with respect to weights $\\{\alpha_{j}\\}_{j=1}^{q}$ and
motifs $\\{M_{j}\\}_{j=1}^{q}$ then, as before, we can instead minimize
ordinary conductance or ordinary ratio cut of the weighted motif graph defined
below, _as long as_ the motifs $M_{j}$ either all have two anchor nodes – the
case we will use – or all have three anchor nodes.

In order to construct the weighted motif graph, we construct the motif graph
$\mathpzc{G}_{j}$ with motif adjacency matrix $\mathpzc{A}_{j}$ for every
$j\in[q]$, and then take a weighted linear combination ($\alpha_{j}\geq 0$ for
$j\in[q]$)

$\mathpzc{A}_{\Sigma}:=\sum_{j=1}^{q}\alpha_{j}\mathpzc{A}_{j}$