# On the computational complexity of the Steiner $k$-eccentricity

Xingfu Lia, Guihai Yua, Aleksandar Ilićb, Sandi Klavžarc,d,e,†

aCollege of Big Data Statistics, Guizhou University of Finance and Economics
Guiyang, Guizhou, 550025, China.
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
bFacebook Inc, Menlo Park 94025, California, USA
E-mail<EMAIL_ADDRESS>
c Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
d Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
e Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
<EMAIL_ADDRESS>
###### Abstract

The Steiner $k$-eccentricity of a vertex $v$ of a graph $G$ is the maximum
Steiner distance over all $k$-subsets of $V(G)$ which contain $v$. A linear
time algorithm for calculating the Steiner $k$-eccentricity of a vertex on
block graphs is presented. For general graphs, an
$O(n^{\nu(G)+1}(n(G)+m(G)+k))$ algorithm is designed, where $\nu(G)$ is the
cyclomatic number of $G$. A linear algorithm for computing the Steiner
$3$-eccentricities of all vertices of a tree is also presented which improves
the quadratic algorithm from [Discrete Appl. Math. 304 (2021) 181–195].

Key words: Steiner tree; Steiner $k$-eccentricity; block graph; tree;
algorithm; computational complexity

##  1 Introduction

Every graph $G=(V(G),E(G))$ in this paper is simple and undirected. The order
of $G$ will be denoted by $n(G)$ and the size of $G$ by $m(G)$. The cyclomatic
number, $\nu(G)$, of $G$ is the minimum number of edges of $G$ whose removal
makes $G$ acyclic. If $G$ is connected, then $\nu(G)=m(G)-n(G)+1$. (The
cyclomatic number of $G$ can alternatively be defined as the dimension of its
cycle space.) If every block of $G$ is a clique, then $G$ is a _block graph_.
The _distance_ $d_{G}(u,v)$ between vertices $u$ and $v$ in $G$ is the length
of a shortest $u,v$-path.

The eccentricity ${\rm ecc}_{G}(v)$ of a vertex $v$ in $G$ is the maximum
distance between $v$ and all the other vertices of $G$. We refer to [3, 4, 6,
5, 7, 8, 14, 19, 20] for different investigations of the eccentricity. In this
work we study a generalization of the eccentricity, the Steiner
$k$-eccentricity. Its definition is based on Steiner trees which are in turn
defined as follows. If $S\subseteq V(G)$, then a subgraph $T$ of $G$ is a
Steiner $S$-tree, if $T$ is a minimum connected subgraph of $G$ which spans
all vertices from $S$. Every vertex from $S$ is called a _terminal_ of $T$,
and the set $S$ is the _terminal set_ of $T$. The Steiner $k$-eccentricity,
${\rm ecc}_{k}(v,G)$, of a vertex $v$ is the maximum size over all Steiner
$S$-trees, where $|S|=k$ and $v\in S$, that is,

${\rm ecc}_{k}(v,G)=\max_{S\subseteq V(G)\atop|S|=k,v\in S}\\{m(T):\ T\ {\rm
is\ a\ Steiner}\ S\hbox{-}{\rm tree}\\}\,.$

(For additional aspects of the Steiner distance see [12, 13, 15, 18, 22].)
Note that ${\rm ecc}_{G}(v)={\rm ecc}_{2}(v,G)$. A Steiner $S$-tree $T$ that
realizes ${\rm ecc}_{k}(v,G)$ is a _Steiner $k$-eccentricity tree of $v$_, we
will shortly say that $T$ is a _Steiner $k$-ecc $v$-tree_. The $k$-set $S$
corresponding the the Steiner $k$-ecc $v$-tree is a _Steiner $k$-ecc $v$-set_
in $G$. The problem to find a Steiner $k$-eccentricity tree of a given vertex
is referred to as the _Steiner $k$-eccentricity tree_ (k-ST) problem. The
decision version of the _Steiner k-eccentricity tree problem_ ($k$-ST) is
presented in Table 1.

Table 1: The Steiner $k$-eccentricity tree problem ($k$-ST) Instance: Graph
$G$, $v\in V(G)$, $k\in[n(G)]$, constant $c$.
---
Question: Is there a Steiner $S$-tree $T$, where $|S|=k$ and $v\in S$, such
that $m(T)\geq c$?

The minimum Steiner tree problem is a well-known NP-hard problem [11], but the
hardness of the $k$-ST problem is still unknown. In [16], a linear time
algorithm was designed to find the optimal value of the 3-ST problem on trees,
while in [17] the result was extended to the $k$-ST problem. In the following
section we design a linear time algorithm for the $k$-ST problem on block
graphs. In the subsequent section we present an algorithm for the problem on
general graphs with the time complexity $O(n^{\nu(G)+1}(n(G)+m(G)+k))$. In
Section 4 we present a linear algorithm to calculate the Steiner
$3$-eccentricity for all vertices in a weighted tree. This improves the
corresponding quadratic algorithm for (unweighted) trees from [16]. We
conclude the paper by giving several directions for future work.

##  2 A linear algorithm for block graphs

In this section, we devise a linear-time algorithm to solve the $k$-ST problem
on block graphs. The main idea is to reduce the problem from a block graph $G$
to a special spanning tree $T$ such that the equqality ${\rm
ecc}_{k}(v,G)={\rm ecc}_{k}(v,T)$ holds, and then to invoke the algorithm from
[17].

Let $G$ be a block graph. If $v\in V(G)$ and $B$ is a block of $G$, then let
${\rm Near}_{G}(v,B)$ be a nearest vertex to $v$ in the block $B$, see Fig. 1
for an example. We first observe that ${\rm Near}_{G}(v,B)$ is unique.

###### Property 2.1

If $G$ is a block graph, $v\in V(G)$, and $B$ a block of $G$, then ${\rm
Near}_{G}(v,B)$ is unique.

Proof. If $v\in V(B)$, then clearly ${\rm Near}_{G}(v,B)=v$ is unique. If
$v\notin V(B)$, then let $P$ be a shortest path between $v$ and the block $B$.
Then the end-vertex $x$ of $P$, $x\neq v$, is a cut vertex of $B$ which in
turn implies that ${\rm Near}_{G}(v,B)=x$ is again unique.

Let $v$ be a vertex of a block graph $G$. For every block $B$ of $G$ remove
every edge which is not incident with ${\rm Near}_{G}(v,B)$ and denote the
resulting graph by $T(v,G)$, for an example see Fig. 1 again. Considering
shortest paths between $v$ and the cut vertices of $G$ we infer that $T(v,G)$
is connected. Moreover, it is also clear (having in mind that $G$ is a block
graph) that $T(v,G)$ has no cycle. Hence $T(v,G)$ is a spanning tree of $G$.
In addition, with Property 2.1 in hands it immediately follows from the
construction that $T(v,G)$ is unique for each vertex $v$ of a block graph $G$.

Figure 1: Block graph $G$ (left) and $T(v,G)$ (right). The dashed lines
indicate the edges which must be removed from $G$ to construct $T(v,G)$.

We are now ready for the key result needed for our algorithm for block graphs.

###### Theorem 2.2

Let $v$ be a vertex of a block graph $G$. Then a Steiner $k$-ecc $v$-tree in
$T(v,G)$ is also a Steiner $k$-ecc $v$-tree in $G$.

Proof. Let $T_{1}$ be a Steiner $k$-ecc $v$-tree in $T(v,G)$ and suppose on
the contrary that $T_{1}$ is not a Steiner $k$-ecc $v$-tree in $G$. Let
$T_{2}$ be a Steiner $k$-ecc $v$-tree in $G$. Then we have
$m(T_{1})\not=m(T_{2})$. Moreover, since $T_{1}$ is also a subtree of $G$, we
must have $m(T_{1})<m(T_{2})$. We are now going to construct a tree
$T^{\prime}_{2}$ of $T(v,G)$ with $m(T^{\prime}_{2})>m(T_{1})$, which will
contradict the fact that $T_{1}$ is a Steiner $k$-ecc $v$-tree in $T(v,G)$.

Construct the tree $T^{\prime}_{2}$ from $T_{2}$ through the following
procedure. For every block $B$ of $G$, if there is an edge $e\in E(B)\cap
E(T_{2})$ such that neither endpoint of $e$ is the vertex ${\rm
Near}_{G}(v,B)$, then delete the edge $e$ from $T_{2}$, and add an edge
between one endpoint of $e$ and ${\rm Near}_{G}(v,B)$. After finishing the
whole procedure for all blocks of $G$, the tree $T^{\prime}_{2}$ is
constructed. Since the edge deletion and addition occur pairwise,
$m(T^{\prime}_{2})=m(T_{2})$. Since $m(T_{1})<m(T_{2})$, we have the announced
contradiction $m(T_{1})<m(T^{\prime}_{2})$.

Theorem 2.2 directly leads to Algorithm 1.

Input: Block graph $G$, vertex $v\in V(G)$, an integer $k\geq 3$.

Output: ${\rm ecc}_{k}(v,G)$.

1Determine $T(v,G)$;

Return ${\rm ecc}_{k}(v,T(v,G))$;

Algorithm 1 k-ECC-Block($v$, $G$, $k$)

###### Theorem 2.3

If $G$ is a block graph and $v\in V(G)$, then Algorithm 1 computes ${\rm
ecc}_{k}(v,G)$ and can be implemented to run in $O(k(n(G)+m(G)))$ time.

Proof. The correctness of the algorithm follows from Theorem 2.2.

Since $T=T(v,G)$ is a tree, Step 1 can be implemented in $O(k(n(T)+m(T))$ time
by invoking the corresponding algorithm from [17]. As for Step 1, to determine
$T(v,G)$ efficiently, Algorithm 2 modifies the depth-first search (DFS)
algorithm, and runs in linear time.

Input: Block graph $G$, vertex $v\in V(G)$.

Output: $T(v,G)$.

1Mark all vertices as ’ _unvisited_ ’, and mark the vertex $v$ as ’ _visited_
’;

2 for  _each unvisited vertex $u\in N_{G}(v)$_ do

3 for  _each vertex $w\in N_{G}(u)$_ do

4 if  _$wv\in E(G)$_ then

5 Delete $uw$ from $G$;

6

7 end if

8

9 end for

10 Get-Tree($u,G$);

11

12 end for

return $G$;

Algorithm 2 Get-Tree($v,G$)

##  3 On general graphs

The basic property that allows a fast algorithm for calculating the Steiner
$k$-eccentricity of a vertex in a tree is that every Steiner $k$-ecc $v$-tree
contains a Steiner $(k-1)$-ecc $v$-tree [17]. This property does not hold in
general graphs. In fact, as the example from Fig. 2 demonstrates, the property
does not hold even on unicycle graphs.

Figure 2: The Steiner $3$-ecc tree of the vertex $v_{0}$ is formed by the
paths $P_{1}$, $P_{2}$, $P_{3}$, $P_{4}$, and $P_{6}$. The Steiner $2$-ecc
tree of $v_{0}$ is formed by the paths $P_{1}$, $P_{5}$ and $P_{6}$. Hence the
Steiner $3$-ecc $v_{0}$-tree does not contain a Steiner $2$-ecc $v_{0}$-tree.

This example illustrates that it could be difficult to find a property that
would lead to a fast algorithm for calculating the Steiner $k$-eccentricity of
a vertex on general graphs. In this section, we present two algorithms to
solve the $k$-ST problem in general graphs. The first one is a brute-forced
method, the other one reduces the problem from general graphs to trees. The
running time of the brute-forced method grows exponentially with $k$, while
the running time of the latter algorithm grows exponentially in $\nu(G)$.

###  3.1 Brute-force algorithm

The definition of the Steiner $k$-eccentricity of a vertex leads to a direct,
brute-force algorithm as follows. Let $v$ be a vertex for which we are going
to calculate the Steiner $k$-eccentricity in a graph $G$. Initially, enumerate
all ($k-1$)-subsets $S$ in $V(G)\setminus\\{v\\}$. For each of these sets $S$
then invoke an algorithm to find a minimum Steiner tree for the set
$S\cup\\{v\\}$. Finally, choose the maximum size among all these minimum
Steiner trees.

The Steiner tree problem is a well-known NP-hard problem [11]. Erickson,
Monma, and Veinott [9] designed an exact algorithm for the Steiner tree
problem with running time $O(3^{k}n+2^{k}(m+n\log n))$, where $n=n(G)$,
$m=m(G)$, and $k$ is the number of terminals. Fuchs et al. [10] and Vygen [21]
followed by exact algorithms with running times $O(2^{k+(k/2)^{1/3}(\ln
n)^{2/3}})$ and $O(nk2^{k+\log_{2}k\log_{2}n})$, respectively. Note that the
running time of all these algorithms grows exponentially with the number of
terminals. So the running time of the brute-forced method also grows
exponentially with respect to the number of terminals.

###  3.2 Reducing to trees

We now devise a novel algorithm whose running time does not grow exponentially
on the number of terminal, that is, on $k$. The key for the algorithm is the
following result, where ${\cal T}(G)$ denotes the set of all spanning trees of
a connected graph $G$.

###### Theorem 3.1

If $G$ is a connected graph, then

${\rm ecc}_{k}(v,G)=\min\\{{\rm ecc}_{k}(v,T):\ T\in{\cal T}(G)\\}\,.$ (1)

Proof. Let $G$ be a graph, $v\in V(G)$, and $T$ s spanning tree of $G$. Then
we claim that the size of a Steiner $k$-ecc $v$-tree in $G$ is not larger than
the size of a Steiner $k$-ecc $v$-tree in $T$.

Suppose on the contrary that there is a Steiner $k$-ecc $v$-tree $T_{1}$ in
$T$ such that $m(T_{1})$ is less than the size of a Steiner $k$-ecc $v$-tree
in $G$. Let $T_{v}$ be a Steiner $k$-ecc $v$-tree in $G$ and $S_{v}$ be the
corresponding Steiner $k$-ecc $v$-set. Then we have $m(T_{1})<m(T_{v})$. Since
$T$ is a spanning tree of $G$, we clearly have $S_{v}\subseteq V(T)$.
Moreover, the size of the minimum Steiner tree on the set $S_{v}$ in $T$ is
not less than the size of $T_{v}$. Let $T_{2}$ be a minimum Steiner tree on
the set $S_{v}$ in $T$. Then we have $m(T_{v})\leq m(T_{2})$ and therefore,
$m(T_{1})<m(T_{2})$. This contradicts to the assumption that $T_{1}$ is a
Steiner $k$-ecc $v$-tree in $T$, hence the claim is proved.

From the claim it now follows that the value of ${\rm ecc}_{k}(v,G)$ is equal
to $\min\\{{\rm ecc}_{k}(v,T):T\in{\cal T}(G)\\}$.

In order to determine the Steiner $k$-eccentricity of a vertex in a graph $G$,
Theorem 3.1 says that it suffices to calculate the Steiner $k$-eccentricity of
the vertex in every spanning tree. In our algorithm we enumerate all possible
edge sets of size $\nu(G)$ rather than enumerating all spanning trees.
Moreover, we calculate the Steiner $k$-eccentricity of a vertex $v$ in a
spanning tree as soon as the spanning tree is enumerated, and maintain the
maximum Steiner $k$-eccentricity of $v$ over all currently enumerated spanning
trees. The enumerating method is based on the following recursive equation.
(Recall that if a graph $G$ is a tree itself, then one can invoke the linear
time algorithm from [17] to calculate the Steiner $k$-eccentricity of $v$.)

${\rm ecc}_{k}(v,G)=\begin{cases}{\rm ecc}_{k}(v,G);&G\ {\rm is\ a\ tree},\\\
\min\limits_{e\in E(C)}\\{{\rm ecc}_{k}(v,G-e)\\};&{\rm
otherwise}\,,\end{cases}$ (2)

where $C$ is a cycle of $G$. The whole procedure is summarized in Algorithm 3,
where the parameter _current-opt_ is initialized to be zero and used to store
the currently maximum Steiner $k$-eccentricity.

Input: Graph $G$, $v\in V(G)$, integer $k\geq 3$.

Output: The Steiner $k$-eccentricity of $v$ in $G$.

1if  _$G$ is a tree_ then

2 _temp_ $\leftarrow$ Steiner $k$-eccentricity of $G$;

3 if  __temp_ $<$ _current-opt__ then

4 _current-opt_ $\leftarrow$ _temp_

5 end if

6 return _current-opt_ ;

7

8 end if

9 else

10 $C$ $\leftarrow$ simple cycle of $G$;

11 for  _each edge $e$ of $C$_ do

12 $H$ $\leftarrow$ $G-e$;

13 k-ECC($v$, $H$, $k$, _current-opt_);

14

15 end for

16

17 end if

Algorithm 3 k-ECC($v$, $G$, $k$, _current-opt_)

###### Theorem 3.2

Let $G$ be a connected graph and $v\in V(G)$. Then Algorithm 3 calculates the
Steiner $k$-eccentricity of $v$ and can be implemented to run in
$O(n^{\nu(G)+1}(n(G)+m(G)+k))$ time.

Proof. The correctness of the algorithm follows from Theorem 3.1.

For the time complexity, we first note that in Step 2 we can apply the linear
algorithm from [17] and that for Step 9 we can use the BFS algorithm starting
from $v$.

For the rest of the proof set $s=\nu(G)$, $n=n(G)$, and $m=m(G)$. Let $T(v,s)$
be the running time of Algorithm 3. By (2) we have

$T(v,s)=\begin{cases}O(kn);&s=0,\\\ O(n+m)+\ell_{1}*T(v,s-1);&s>0,\end{cases}$
(3)

where $\ell_{1}=m(C)$. Setting $M$=$n+m$, we can argue as follows:

$\displaystyle T(v,s)$ $\displaystyle=O(M)+\ell_{1}*T(v,s-1)$
$\displaystyle=O(M)(1+\ell_{1}+\ell_{1}*\ell_{2}+\cdots+\Pi_{i=1}^{s}\ell_{i})+(\Pi_{i=1}^{s}\ell_{i})*T(v,0)$
$\displaystyle=O(M)(1+O(n)+O(n)*O(n)+...+\Pi_{i=1}^{s}O(n))+(\Pi_{i=1}^{s}O(n))*O(kn)$
$\displaystyle=O(n^{s+1}(n+m+k)),$

and we are done.

Note that the time complexity of Algorithm 3 grows exponentially with $\nu(G)$
rather than with $k$.

##  4 Linear time to calculate Steiner $3$-eccentricities for all vertices

As already mentioned, in [16] a linear time algorithm to calculate the Steiner
$3$-eccentricity of a vertex of a tree was designed. In case one wishes to
determine the Steiner $3$-eccentricity of all vertices, for instance in order
to compute the average Steiner $3$-eccentricity, then this approach yields a
quadratic algorithm. In this section we demonstrate that also the Steiner
$3$-eccentricity of all vertices of a tree can be computed in linear time.
Moreover, we also extend this result to weighted trees.

Let $T$ and $T_{r}$, respectively, be a rooted weighted tree on $n$ vertices
and the subtree rooted at a vertex $r\in V$. In other words, $T_{r}$ is a
subgraph induced on vertex $r$ and all of its descendants.

The root of $T$ is assigned by an arbitrary vertex. The weights of edges are
stored in an adjacency list named as $adj$. The linear algorithm is two-stage
DFS procedures. Details for the DFS algorithm can be found in [1]. The first
stage is to compute the longest paths from $v$ in the subtree rooted at $v$
for every vertex $v$, while the second one is to update the longest paths with
the upwards path via parent node for the purpose of computing Steiner
3-eccentricities. The first stage and the second stage are respectively showed
in Algorithms 4 and 5.

Input: The adjacency matrix of the tree $T$ with the root vertex $root$.

Output: The downwards arrays $path\\_weight,path\\_index,attached\\_weight$.

$path\\_weight[v]=(0,0,0)$;

$path\\_index[v]=(-1,-1,-1)$;

$attached\\_weight[v]=(0,0,0)$;

for  _every neighbor $u$ of $v$_ do

if  _$parent[u]=-1$ and $u\neq root$_ then

$parent[u]=v$;

$DFS\\_stage1(u)$;

$update(v,u,adj\\_weight[v][u]+path\\_weight[0][u],\max(path\\_weight[1][u],attached\\_weight[0][u]))$;

end if

end for

Algorithm 4 DFS$\\_$stage1 ($v$)

Input: The outputs of $DFS\\_stage1$.

Output: The arrays $path\\_weight,path\\_index,attached\\_weight$.

$mark[v]=1$;

$u=parent[v]$;

if  _$u\neq-1$_ then

$up\\_path\\_weight=0$;

$up\\_attached\\_weight=0$;

if  _$path\\_index[0][u]\neq v$_ then

$up\\_path\\_weight=adj\\_weight[u][v]+path\\_weight[0][u]$;

if  _$path\\_index[1][u]\neq v$_ then

$up\\_attached\\_weight=\max(path\\_weight[1][u],attached\\_weight[0][u])$;

end if

else

$up\\_attached\\_weight=\max(path\\_weight[2][u],attached\\_weight[0][u])$;

end if

end if

else

$up\\_path\\_weight=adj\\_weight[u][v]+path\\_weight[1][u]$;

$up\\_attached\\_weight=\max(path\\_weight[2][u],attached\\_weight[1][u])$;

end if

$update(v,u,up\\_path\\_weight,up\\_attached\\_weight)$;

end if

for  _every neighbor $u$ of $v$_ do

if  _$mark[u]=-1$_ then

$DFS\\_stage2(u)$;

end if

end for

Algorithm 5 DFS$\\_$stage2 ($v$)

The Steiner 3-eccentricity of the vertex $v$ can be computed as

$\epsilon_{3}(v)=path\\_weight[v][0]+\max\\{path\\_weight[v][1],attached\\_weight[v][0]\\},$

where $path\\_weight[v]$ is initialized as $(0,0,0)$ and represents the length
of the longest path from the vertex $v$ in the subtree $T_{v}$;
$path\\_index[v]$ is initialized as $(-1,-1,-1)$ and represents the neighbor
of $v$ on the longest path from the vertex $v$ in the subtree $T_{v}$;
$attached\\_weight[v]$ is initialized as $(0,0,0)$ and represents the length
of the longest subpath attached at the longest path in the subtree $T_{v}$
strictly bellow $v$.

The main helper function $update(v,u,new\\_weight,new\\_attached\\_weight)$ is
to keep the top three values for the longest paths coming from the vertex $v$
and implemented by the C code in Appendix.

The first stage $DFS\\_stage1$ is to recursively traverse all neighbors of the
vertex $v$. After the subtree is processed, we update the values for the node
$v$ based on the values for each of the subtrees. We traverse the nodes in the
pre-order phase in the second stage $DFS\\_stage2$. We update the values for
the root and then run computation for the neighbors.

###### Theorem 4.1

There is a linear-time algorithm to calculate the Steiner $3$-eccentricities
for all vertices in a weighted tree $T$.

Proof. Given that the algorithm consists of two traversals using DFS
algorithms and with linear initialization, the time complexity of the
algorithm equals $O(n)$. There are six additional vectors of size $n$, and
therefore the memory complexity of the algorithm equals $O(n)$ as well.

The correctness of the algorithm directly follows from the definition of
Steiner 3-eccentricities for the root vertex $v$. For other vertices, we
effectively compute the top three longest paths and attached paths - which is
equivalent as considering those vertices as roots.

##  5 Conclusion

We presented a linear-time algorithm to solve the $k$-ST problem on block
graphs, and an algorithm to solve the $k$-ST problem on general graphs, where
the exponential growth of the running time depends only on the cyclomatic
number of a graph.

It seems that if a graph is dense, then the Steiner $k$-eccentricity of a
vertex may be easy to find. For instance, this is the case for complete graphs
and for complete graphs with one or two edges removed. Inspired by this, an
open question is how to modify Algorithm 3 so that it works well not only for
small values of $\nu$ but also when $\nu$ is large.

For calculating the Steiner $k$-eccentricity of a vertex in a graph $G$, we
showed that there is an algorithm whose running time grows exponentially on
$\mu$ but is independent of the input parameter $k$. On the other hand, is
there is a fixed-parameter tractable algorithm [2] to solve this problem?
Moreover, there is still no answer to the question of whether the problem is
NP-hard.

Let’s turn back to the $k$-ST problem. One can also ask whether there is a
$k$-set $S$ such that the size of the minimum Steiner tree on $S$ is at least
$c$. This yields the _Steiner $k$-eccentricity set problem_ ($k$-SES). The
decision version of the _Steiner k-eccentricity set problem_ ($k$-SES) is
presented in Table 2.

Table 2: The Steiner k-eccentricity set problem ($k$-SES) Instance: Graph $G$,
$v\in V(G)$, $k\in[n(G)]$, constant $c$.
---
Question: Is there a $k$-set $S$, where $v\in S$, such that the size of a
minimum
Steiner tree on $S$ is at least $c$?

For every vertex $v$ in a graph $G$, there is a $k$-set $S_{1}$ such that a
minimum Steiner tree on $S_{1}$ has at least $c$ edges if and only if there is
a minimum Steiner tree on some $k$-set $S_{2}$ such that the size of the
Steiner tree is at least $c$, where $v\in S_{1}$ and $v\in S_{2}$. In other
words, there is a ”YES” answer to the $k$-ST problem if and only if there is a
”YES” answer to the $k$-SES problem. Therefore, the $k$-ST problem is as hard
as the $k$-SES problem. However, algorithms to solve these two problems could
be different. It seems that there is no brute-force algorithm to solve the
$k$-SES problem.

Finally, we designed an $O(n)$-time algorithm to calculate Steiner
$3$-eccentricities for all vertices of a tree. Does this result extend to
$k\geq 4$?

## Acknowledgements

This work was supported by Science Foundation of Guizhou University of Finance
and Economics (2020XYB16), Science Foundation of Guizhou University of Finance
and Economics (2019YJ058). Sandi Klavžar acknowledges the financial support
from the Slovenian Research Agency (research core funding P1-0297, and
projects N1-0095, J1-1693, J1-2452).

## References

  * [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Third Edition, MIT Press, Cambridge, 2009.
  * [2] M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer, Cham, 2015.
  * [3] P. Dankelmann, W. Goddard, C. Swart, The average eccentricity of a graph and its subgraphs, Util. Math. 65 (2004) 41–51.
  * [4] P. Dankelmann, S. Mukwembi, Upper bounds on the average eccentricity, Discrete Appl. Math. 167 (2014) 72–79.
  * [5] P. Dankelmann, F. J. Osaye, Average eccentricity, $k$-packing and $k$-domination in graphs, Discrete Math. 342 (2019) 1261–1274.
  * [6] P. Dankelmann, F. J. Osaye, S. Mukwembi, B. Rodrigues, Upper bounds on the average eccentricity of $K_{3}$-free and $C_{4}$-free graphs, Discrete Appl. Math. 270 (2019) 106–114.
  * [7] Z. Du, A. Ilić, On AGX conjectures regarding average eccentricity, MATCH Commun. Math. Comput. Chem. 69 (2013) 597–609.
  * [8] Z. Du, A. Ilić, A proof of the conjecture regarding the sum of the domination number and average eccentricity, Discrete Appl. Math. 201 (2016) 105–113.
  * [9] R. E. Erickson, C. Monma, A. F. Veinott, Send-and-split method for minimum-concave-cost network flows, Math. Oper. Res. 12 (1987) 634–664.
  * [10] B. Fuchs, W. Kern, D. Mölle, S. Richter, P. Rossmanith, X. Wang, Dynamic programming for minimum Steiner trees, Theory Comput. Syst. 41 (2007) 493–500.
  * [11] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979.
  * [12] T. Gologranc, Steiner convex sets and Cartesian product, Bull. Malays. Math. Sci. Soc. 41 (2018) 627–636.
  * [13] S. Klavžar, D. Kuziak, I. Peterin, I. G. Yero, A Steiner general position problem in graph theory, Comput. Appl. Math. 40 (2021) Paper 223.
  * [14] A. Ilić, On the extremal properties of the average eccentricity, Comput. Math. Appl. 64 (2012) 2877–2885.
  * [15] X. Li, Y. Mao, I. Gutman, The Steiner Wiener index of a graph, Discuss. Math. Graph Theory 36 (2016) 455–465.
  * [16] X. Li, G. Yu and S. Klavžar, On the average Steiner $3$-eccentricity of trees, Discrete Appl. Math. 304 (2021) 181–195.
  * [17] X. Li, G. Yu, S. Klavžar, J. Hu, B. Li, The Steiner $k$-eccentricity on trees, Theoret. Comput. Sci. 889 (2021) 182–188.
  * [18] Y. Mao, P. Dankelmann, Z. Wang, Steiner diameter, maximum degree and size of a graph, Discrete Math. 344 (2021) Paper 112468.
  * [19] H. Smith, L. A. Székely, H. Wang, Eccentricity sum in trees, Discrete Appl. Math. 207 (2016) 120–131.
  * [20] Y. Tang, B. Zhou, On average eccentricity, MATCH Commun. Math. Comput. Chem. 67 (2012) 405–423.
  * [21] J. Vygen, Faster algorithm for optimum Steiner trees, Inform. Process. Lett. 111 (2011) 1075–1079.
  * [22] D. Weißauer, Isometric subgraphs for Steiner distance, J. Graph Theory 94 (2020) 597–613.


# Modeling Long-Range Context for
Concurrent Dialogue Acts Recognition

Yue Yu<EMAIL_ADDRESS>0000-0003-0566-9304 Department of Computer
ScienceGeorgetown University ,  Siyao Peng<EMAIL_ADDRESS>Department
of LinguisticsGeorgetown University and  Grace Hui Yang
<EMAIL_ADDRESS>Department of Computer ScienceGeorgetown University

(2019)

###### Abstract.

In dialogues, an utterance is a chain of consecutive sentences produced by one
speaker which ranges from a short sentence to a thousand-word post. When
studying dialogues at the utterance level, it is not uncommon that an
utterance would serve multiple functions. For instance, “Thank you. It works
great.” expresses both gratitude and positive feedback in the same utterance.
Multiple dialogue acts (DA) for one utterance breeds complex dependencies
across dialogue turns. Therefore, DA recognition challenges a model’s
predictive power over long utterances and complex DA context. We term this
problem Concurrent Dialogue Acts (CDA) recognition. Previous work on DA
recognition either assumes one DA per utterance or fails to realize the
sequential nature of dialogues. In this paper, we present an adapted
Convolutional Recurrent Neural Network (CRNN) which models the interactions
between utterances of long-range context. Our model significantly outperforms
existing work on CDA recognition on a tech forum dataset.

††copyright: acmcopyright††journalyear: 2019††conference: The 28th ACM
International Conference on Information and Knowledge Management; November
3–7, 2019; Beijing, China††booktitle: The 28th ACM International Conference on
Information and Knowledge Management (CIKM ’19), November 3–7, 2019, Beijing,
China††price: 15.00††doi: 10.1145/3357384.3358145††isbn:
978-1-4503-6976-3/19/11

##  1\. Introduction

An utterance is a sequence of sentences that are produced by the same speaker
in his or her turn in a dialogue. Dialogue Acts (DA) aim to capture the
functionality of these utterances. Recognizing DAs can benefit a dialogue
system in many ways. 1) A pre-trained DA model can reduce the number of
utterance annotations required to train a dialogue system (Kumar et al.,
2018a). 2) For retrieval-based dialogue systems, DA modeling can provide
meaningful patterns to reduce the search space and thus expedite response
selection. Even though DA recognition is a well-studied problem, most
contemporary methods concentrate on conversations of short utterances with
usually a single DA per utterance, the case of the Switchboard Dialogue Act
(SwDA) corpus (Jurafsky, 1997). However, when utterances are long and complex,
one DA label would not be sufficient to describe the pragmatic function of an
utterance. As a result, multiple DA labels would be required and the
approaches on SwDA would not apply. We term our problem Concurrent Dialogue
Acts (CDA) Recognition.

Forum discussion is a type of dialogue that breeds CDAs. The sample in Figure
1 from MSDialog-Intent corpus (Qu et al., 2019) discusses a technical issue
with Microsoft Bingo among two users ($U1$ & $U2$) and two agents ($A1$ &
$A2$). For instance, utterance $\mathit{6}$ is simultaneously labeled as GG
for “Good Luck” and PA for “using a Win+Shift+Cursor move” (DA labels are
shown in Table 1). $59.95\%$ of utterances in MSDialog-Intent are indeed
multi-labeled.

Table 1. Taxonomy of 12 dialogue acts in a tech forum.

DA Taxonomy % DA Taxonomy % GG Greetings/Gratitude 40.0 FQ Follow-up Question
8.6 PA Potential Answer 39.7 NF Negative Feedback 7.6 FD Further Details 24.8
CQ Clarifying Question 7.5 OQ Original Question 23.3 RQ Repeat Question 6.1 PF
Positive Feedback 10.7 JK Junk 2.6 IR Information Request 10.7 O Others 1.5

$U1$ $\mathit{1}$ For around a month my settings would disappear … If somebody
know how to fix this , please tell me . [ OQ ]

$\mathit{2}$ Hi … to isolate the issue … we would like to know the following …
look forward to your response . [ GG IR PA ] $A1$

$U2$ $\mathit{3}$ I want to reinstall Microsoft bingo for free I have Windows
10 I can’t even open my store app … [ CQ FD ]

$U2$ $\mathit{4}$ I did n’t have this issue before [ FD ]

$U2$ $\mathit{5}$ There were some issues made [ FD ]

$\mathit{6}$ … you would also have the ( simpler ) alternative of using a
Win+Shift+Cursor move . Good luck … [ GG PA ] $A2$

$U1$ $\mathit{7}$ …The only changes I have made prior to the issue was the
installation of new RAM cards … Windows updates … [ FD ]

$U1$ $\mathit{8}$ Thank you … This works [ GG PF ]

$U1$ $\mathit{9}$ I manage to fix the situation … thank you … [ GG PF ]

Figure 1. Dialogue between two users and two agents.

Another important characteristic of these dialogues is that a speaker can
refer to any of the preceding utterances. Thus, it is unfeasible to determine
a fixed window size that would incorporate all relevant context. In Figure 1,
utterance $\mathit{6}$ provides a potential answer (PA) to utterance
$\mathit{1}$; utterance $\mathit{7}$ provides further details (FD) to the
information request (IR) in utterance $\mathit{2}$. Without the capability of
capturing a wider range of utterances, the chance of recognizing DAs in these
forum conversations would be reduced.

However, current approaches for DA recognition only attempt to capture either
of the two characteristics but not both. 1) Sequence models, that can capture
far-away context information, are often applied to DA sequence labeling. Kumar
et al. (2018b) build a hierarchical RNN using Bi-LSTM as a base unit and CRF
as the last layer; Chen et al. (2018) use the CRF-Attentive Structured Network
for the same hierarchical nature of DAs. Nonetheless, these models only
concern single-label DA datasets (e.g., SwDA) and heavily rely on CRF, which
is incapable of predicting multiple labels for each utterance. 2) Another line
of research casts DA recognition as a multi-label classification problem to
accommodate the CDA scenario. Qu et al. (2019) apply a CNN-based text
classifier proposed by Kim (2014) using a fixed window to represent the
context. Although capable of classifying utterances with CDAs, Qu et al.
(2019)’s model only concerns a strictly-local context range and thus cannot
include distant information.

In this paper, we present a novel neural model that is adapted from
Convolutional Recurrent Neural Network (CRNN) to both incorporate the
interaction between distant utterances and generalize the DA recognition task
to accommodate CDA. Our contributions can be summarized as follows: 1) In our
adapted Convolutional Recurrent Neural Network (CRNN) we use the recurrent
layers to gather long-range contextual information that are extracted from
utterances by the convolutional layers. 2) We further optimize the model by
incorporating highway connections and dynamic $k$-max pooling. 3) Our model
significantly outperforms the state-of-the-art model by 4.68% in accuracy and
3.08% in F-score.

##  2\. Related Work

CRNN has been widely applied to classification tasks. In Natural Language
Processing (NLP) research including sentence segmentation (Treviso et al.,
2017), sentiment analysis (Wang et al., 2016) and discourse modeling
(Kalchbrenner and Blunsom, 2013), CRNN achieves the state-of-the-art in
single-label classification where for each input, a single output would be
predicted.

Deep learning research outside of NLP proves CRNN suitable for classifications
where multiple labels may be assigned to each target. Cakir et al. (2017)
apply CRNN to Polyphonic Sound Event Detection where multiple sound events can
be detected in a timestamp. Similar to single-label CRNNs, features are
extracted by the convolutional layers and further integrated into the
recurrent layers to provide context information. The sigmoid activation
function is used to make multi-binary decisions for each event activity. Choi
et al. (2017) treat music tagging as a multi-label classification task where a
subset of genres, moods, etc. are assigned to each music. In Choi et al.
(2017)’s model, The CNN is responsible for extracting local features and the
RNN presents a temporal summarization. These studies substantiate CRNN’s
applicability to multi-label classification tasks, especially its ability to
extract features from the current step and to integrate features from
arbitrarily long distance.

In previous dialogue research, Kalchbrenner and Blunsom (2013) and Kim et al.
(2016) incorporate CRNN into a single-label DA recognition and dialogue topic
tracking system. Based on this line of research, we argue that CRNN can be
applied for CDA recognition with two adaptations: binary cross-entropy loss
(BCE) and sigmoid activation. Further experiments also show that adding
highway connections and dynamic $k$-max pooling further boosts the
performance.

##  3\. Task Definition

The task is defined as a CDA recognition problem where for each utterance
$u_{t}$ (the $t$-th utterance) in a dialogue, we predict a subset of DA labels
$y_{t}$ that describes the functionality of the utterance from a candidate set
of DA labels $\mathcal{L}=\\{l_{1},l_{2},...,l_{c}\\}$. For a dialog with $s$
utterances, the inputs to the algorithm is
$\mathcal{U}=\\{u_{1},u_{2},...,u_{s}\\}$, and the output is
$\mathcal{Y}=\\{y_{1},y_{2},...,y_{s}\\}$, where $y_{t}$ is the annotated DA
label set for $u_{t}$, in which
$y_{t}=\\{y_{t}^{1},y_{t}^{2},...,y_{t}^{c}\\}$. Here, $y_{t}^{j}=\\{1,0\\}$
denotes whether the $t$-th utterance of the dialog is labeled with DA label
$l_{j}$ or not. When $\sum_{j=1}^{c}y_{t}^{j}>1$, we say CDAs are recognized.
Given a dialogue $\mathcal{U}$, the goal is to predict the DA sequence
$\mathcal{Y}$ from the text.

Figure 2. The proposed CRNN model architecture.

##  4\. The Proposed Approach

The challenge of this task lies in the complexity of dialogue structures in
human conversations where an utterance can express multiple DAs. In this work,
we improve CDA recognition with an adapted CRNN which models the interactions
between long-range context.

###  4.1. Convolutional Layer

The base of our architecture is a CNN module similar to Kim (2014). The module
works by ‘sliding’ through the embedding matrix of an utterance with various
filter sizes to capture semantic features in differently ordered n-grams. A
convolution operation is denoted as

(1) $\displaystyle k_{i}$
$\displaystyle=\tanh(\mathbf{w}\cdot\mathbf{x}_{i:i+d-1}+b_{k})$

where $k_{i}$ is the feature generated by the $i$-th filter with weights
$\mathbf{w}$ and bias $b_{k}$. This filter of size $d$ is applied to an
embedding matrix, which is the concatenation from the $i$-th to the
$(i+d-1)$-th embedding vectors. This operation is applied to every possible
window of words in an utterance of length $n$ and generates a feature map
$\mathbf{k}$.

(2) $\displaystyle\mathbf{k}$ $\displaystyle=[k_{1},k_{2},...,k_{n-d+1}]$

###  4.2. Dynamic $k$-Max Pooling

A max-over-time pooling operation (Kim, 2014) is usually applied over the
feature map and takes the maximum value as the feature corresponding to this
particular filter. The idea is to capture the most important features of an
utterance. However, this mechanism could be problematic when the utterance is
long. We experimented with Dynamic $k$-Max Pooling (Liu et al., 2017) to pool
the most powerful features from $p$ sub-sequences of an utterance with $m$
words. This pooling scheme naturally deals with variable utterance length.

(3) $\displaystyle p(\mathbf{k})$
$\displaystyle=\left[\max\left\\{\mathbf{k}_{1:\lfloor\frac{m}{p}\rfloor}\right\\},\ldots,\max\left\\{\mathbf{k}_{\lfloor
m-\frac{m}{p}+1\rfloor:m}\right\\}\right]$

###  4.3. Recurrent Layer

Based on the local textual features extracted from each utterance, a
bidirectional RNN is applied to gather features from a wider context for
recognizing the DAs in the target utterance, $u_{t}$. We experimented with two
variations of RNN: LSTM (Zaremba and Sutskever, 2014) and GRU (Cho et al.,
2014), both of which utilize gating information to prevent the vanishing
gradient problem. GRU is constructed similarly to LSTM but without using a
memory cell. It exposes the full hidden state without any control, which may
be computationally more efficient. We experimented with both since it is
difficult to predict which one performs better on our task.

###  4.4. Highway Connection

Although LSTM and GRU help capture wider context, the network training becomes
more difficult with the additional recurrent layers. Inspired by the highway
networks (Sanders and Schultes, 2005), we propose to add a highway connection
between the convolutional layer and the last fully connected layer. With this
mechanism, the information about the target utterance, $u_{t}$, can flow
across the recurrent layer without attenuation. The last fully connected layer
learns from the outputs of both recurrent and convolutional layers.

##  5\. Dataset

We use the MSDialog-Intent dataset (Qu et al., 2019) to conduct experiments.
In the dataset, each of the 10,020 utterances is annotated with a subset of 12
DAs. The abundance of information in a single utterance (avg. 72
tokens/utterance) breeds CDA (avg. 1.83 DAs/utterance). We observe a strong
correlation between the number of DAs and utterance length, which necessitates
a CDA model for forum conversations.

The dataset includes plenty of metadata for each utterance, e.g., answer vote
and user affiliation. For generalizability, our model only incorporates
textual content of the dialogues. Besides, unlike Qu et al. (2019), we keep
all the DA annotations in the dataset to preserve the meaningful DA structures
within and across utterances.111Qu et al. (2019) simplified the task by
removing DA labels from certain utterances and reducing rare DA combinations
to top $32$ frequent ones. We re-ran Qu et al. (2019)’s model on the dataset
preserving all DA combinations.

##  6\. Experiments

In this section, three versions of our proposed model with incremental
improvements are evaluated against a CNN baseline (Kim, 2014) and the state-
of-the-art approach for CDA recognition (Qu et al., 2019).

  * •

CNN-Kim(Kim, 2014): One of the first attempts to apply CNN to text
classification. The CNN model consists of three convolutional layers with the
same filter size.

  * •

CNN-CR(Qu et al., 2019): The state-of-the-art approach for CDA recognition on
the MSDialog-Intent dataset (Qu et al., 2019). The CNN model incorporates
context information with a window size of 3.

  * •

CRNN ($v_{1}$): Our base model that adapts CRNN for CDA recognition using BCE
loss and sigmoid activation function.

  * •

CRNN ($v_{2}$): CRNN ($v_{1}$) with highway connections added between the
convolutional layer and the fully connected layer.

  * •

CRNN ($v_{3}$): CRNN ($v_{1}$) with highway connections and dynamic $k$-max
pooling implemented.

###  6.1. Experimental Setup

The dataset is partitioned into training, validation, and test sets in the
ratio of 8:1:1. Hyper-parameters are tuned with the validation set. For word
embedding, we use the publicly available GloVe vectors that were trained on
Wikipedia + Gigaword 5 (Pennington et al., 2014). We find that setting (CNN
filters, CNN dropout, RNN units, RNN layers, RNN dropout and $k$) to (100,
0.4, 900, 2, 0.15 and 2) is the best for our model. The BCE is used as loss
function and Adam (Kingma and Ba, 2015) is used for optimization with an
initial learning rate, 0.001. The models were trained on four GeForce RTX 2080
Ti GPUs.

###  6.2. Metrics

Following previous work (Qu et al., 2019) on multi-label classification, we
adopt label-based accuracy (i.e., Hamming score) and micro-$F_{1}$ score as
our main evaluation metrics. Micro-precision and micro-recall are also
reported to assist the analysis. Among all, accuracy is the only metrics that
is on a per utterance basis. Therefore, Student’s paired t-test is performed
only on accuracy. Other metrics (P, R, $F_{1}$) provide an overall performance
evaluation for all utterances.

###  6.3. Results

All proposed adaptations, i.e., highway connections and dynamic $k$-max
pooling, contribute to the model, as in Table 2. The CRNN models
significantly222* denotes a statistically significant difference over the best
baseline (CNN-CR) with p $\leq$ 0.05, ** for p $\leq$ 0.01, *** for p $\leq$
0.001 and **** for p $\leq$ 0.0001. outperform both baselines. The model with
full adaptation ($v_{3}$), performs the best across all experiments: achieving
the highest accuracy, recall and $F_{1}$ with LSTM and the highest precision
with GRU. The divergence between LSTM and GRU may indicate that the forget and
output gates in LSTM are helpful for the retrieval of related memory but
increase the variance of the model.

Table 2. Performance of CNN-Kim, CNN-CR, and CRNN.2

Models | Accuracy | Precision | Recall |  $F_{1}$ score
---|---|---|---|---
CNN-Kim(Kim, 2014) | 0.5785 | 0.6371 | 0.6745 | 0.6553
CNN-CR(Qu et al., 2019)1 | 0.6354 | 0.7108 | 0.6952 | 0.7029
CRNN ($v_{1}$) w/ LSTM | 0.6668* | 0.7238 | 0.7297 | 0.7267
CRNN ($v_{1}$) w/ GRU | 0.6543* | 0.7056 | 0.7065 | 0.7061
CRNN ($v_{2}$) w/ LSTM | 0.6731**** | 0.7315 | 0.7315 | 0.7315
CRNN ($v_{2}$) w/ GRU | 0.6734** | 0.7280 | 0.7334 | 0.7307
CRNN ($v_{3}$) w/ LSTM |  0.6822**** | 0.7254 | 0.7422 | 0.7337
CRNN ($v_{3}$) w/ GRU | 0.6733*** | 0.7358 | 0.7215 | 0.7286

Table 3. Mean accuracy and the average number of predicted DAs grouped by the
number of reference DAs.2 The percentage indicates the frequency of each DA
group in the test set.

# of ref DAs | % | Mean accuracy | Avg. num. of pred DAs
---|---|---|---
CRNN ($v_{3}$) | CNN-CR | CRNN ($v_{3}$) | CNN-CR
1 | 36.9 |  0.7704** | 0.7126 | 1.44 | 1.44
2 | 42.8 |  0.6641*** | 0.6232 |  2.02** | 1.89
3 | 16.7 |  0.5596* | 0.5177 |  2.56*** | 2.37
$\geq$4 | 3.6 | 0.5618 | 0.5339 | 2.68 | 2.74

Figure 3. Mean accuracy of CRNN ($v_{3}$) vs. CNN-CR.

Table 3 further exemplifies the capability of our best model in recognizing
CDAs. Our model systematically outperforms the state-of-the-art approach, CNN-
CR. More specifically, 1) CRNN achieves better mean accuracy for all reference
sizes and significantly for sizes $1-3$, which consist of 96.4% utterances. 2)
The average number of DAs predicted by CRNN is the closest to the reference.

Another advantage of CRNN is the ability to handle longer dialogues. Figure 3
visualizes the mean accuracy of utterances grouped by dialogue length. Along
with the increase of dialogue length, we observe an increasing advantage of
CRNN (in blue) over CNN-CR (in orange), especially for dialogues longer than 6
utterances.

###  6.4. A Case study

Table 4 shows an example where CRNN and CNN-CR predict differently for
utterance $\mathit{5}$. Utterance $\mathit{5}$ should respond to utterance
$\mathit{2}$, establishing a long-range dependency that cannot be captured by
CNN-CR’s fixed context window. Our CRNN model succeeds in recognizing the
distant context for further details (FD). Furthermore, CNN-CR wrongly
recognizes utterance $\mathit{5}$ as original question (OQ) since the OQ in
utterance $\mathit{1}$ is out of range.

Table 4. Predictions of CRNN ($v_{3}$) and CNN-CR on a dialogue with long-
range dependencies.

# | Utterance |  Ref |  CRNN |  CNN -CR
---|---|---|---|---
$\mathit{1}$ |  How can I download Skype for Windows 8.1 … | OQ | OQ | OQ
$\mathit{2}$ |  Hi … if you are using a phone running Windows 8.1 … no longer … but if … computer … you can … |  GG PA |  GG PA |  GG PA
… Utterances $\mathit{3}$ & $\mathit{4}$ …
$\mathit{5}$ |  Hi , I am using surface tablet 8.1 Windows … tried many times … this app can’t run on this PC |  FD FQ GG |  FD GG PA RQ |  OQ GG

##  7\. Conclusion

Our proposed CRNN models for CDA recognition impose fewer restrictions on the
structure of DAs and capture textual features from a wider context. The
experiment results show that all of the proposed adaptations, i.e., highway
connections and dynamic $k$-max pooling, contribute to the model optimization.
Our final model significantly outperforms the state-of-the-art approach on a
tech forum dataset where the dialogues are packed with complex DA structures
and information-rich utterances. Future work will consider a more fine-grained
set of DAs for a deeper analysis of CDA modeling. It would also be interesting
to annotate antecedent relations among utterances to structure threading
dialogue flows.

##  8\. Acknowledgements

This research is supported by U.S. National Science Foundation IIS-145374. Any
opinions, findings, conclusions, or recommendations expressed in this paper
are of the authors, and do not necessarily reflect those of the sponsor.

## References

  * (1)
  * Cakir et al. (2017) E. Cakir, G. Parascandolo, T. Heittola, H. Huttunen, and T. Virtanen. 2017\.  Convolutional Recurrent Neural Networks for Polyphonic Sound Event Detection.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 25 (2017).
  * Chen et al. (2018) Z. Chen, R. Yang, Z. Zhao, D. Cai, and X. He. 2018.  Dialogue Act Recognition via CRF-Attentive Structured Network. In _SIGIR ’18_. ACM, 225–234.
  * Cho et al. (2014) K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. 2014.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ (2014).
  * Choi et al. (2017) K. Choi, G. Fazekas, M. Sandler, and K. Cho. 2017\.  Convolutional recurrent neural networks for music classification. In _ICASSP ’17_. 2392–2396.
  * Jurafsky (1997) D. Jurafsky. 1997\.  Switchboard SWBD-DAMSL shallow-discourse-function annotation coders manual.  _ICS’97_ (1997).
  * Kalchbrenner and Blunsom (2013) N. Kalchbrenner and P. Blunsom. 2013.  Recurrent convolutional neural networks for discourse compositionality.  _ACL’13_ (2013).
  * Kim et al. (2016) S. Kim, R. Banchs, and H. Li. 2016.  Exploring Convolutional and Recurrent Neural Networks in Sequential Labelling for Dialogue Topic Tracking. In _ACL’16_.
  * Kim (2014) Y. Kim. 2014.  Convolutional Neural Networks for Sentence Classification. In _EMNLP’14_. 1746–1751.
  * Kingma and Ba (2015) D. Kingma and J. Ba. 2015\.  Adam: A method for stochastic optimization. In _ICLR’15_.
  * Kumar et al. (2018b) H. Kumar, A. Agarwal, R. Dasgupta, and S. Joshi. 2018b.  Dialogue act sequence labeling using hierarchical encoder with crf. In _AAAI’18_.
  * Kumar et al. (2018a) H. Kumar, A. Agarwal, and S. Joshi. 2018a.  Dialogue-act-driven Conversation Model: An Experimental Study. In _COLING’18_. 1246–1256.
  * Liu et al. (2017) J. Liu, W.-C. Chang, Y. Wu, and Y. Yang. 2017\.  Deep Learning for Extreme Multi-label Text Classification. In _SIGIR ’17_. New York, NY, USA, 115–124.
  * Pennington et al. (2014) J. Pennington, R. Socher, and C. D. Manning. 2014.  GloVe: Global Vectors for Word Representation. In _EMNLP’14_. 1532–1543.
  * Qu et al. (2019) C. Qu, L. Yang, B. Croft, Y. Zhang, J. R. Trippas, and M. Qiu. 2019\.  User Intent Prediction in Information-seeking Conversations.  _CHIIR ’19_ (2019).
  * Sanders and Schultes (2005) P. Sanders and D. Schultes. 2005.  Highway hierarchies hasten exact shortest path queries. In _European Symposium on Algorithms_. Springer, 568–579.
  * Treviso et al. (2017) M. Treviso, C. Shulby, and S. Aluísio. 2017.  Sentence Segmentation in Narrative Transcripts from Neuropsychological Tests using Recurrent Convolutional Neural Networks. In _EACL ’17_. Association for Computational Linguistics, 315–325.
  * Wang et al. (2016) X. Wang, W. Jiang, and Z. Luo. 2016.  Combination of Convolutional and Recurrent Neural Network for Sentiment Analysis of Short Texts. In _COLING ’16_.
  * Zaremba and Sutskever (2014) W. Zaremba and I. Sutskever. 2014.  Learning to execute.  (2014).


# A nano vacuum gauge based on second-order coherence in optical levitation

Lyu-Hang Liu  Yu Zheng<EMAIL_ADDRESS>Yuan Tian  Long Wang  Guang-Can Guo
Fang-Wen Sun<EMAIL_ADDRESS>CAS Key Laboratory of Quantum Information,
University of Science and Technology of China, Hefei 230026, China  CAS Center
for Excellence in Quantum Information and Quantum Physics, University of
Science and Technology of China, Hefei 230026, China

###### Abstract

Accurate measurement of pressure with a wide dynamic range holds significant
importance for various applications. This issue can be realized with a
mechanical nano-oscillator, where the pressure-related collisions with
surrounding molecules induce its energy dissipation. However, this energy
dissipation of the nano-oscillator may be overshadowed by other processes.
Here, we apply the second-order coherence analysis to accurately characterize
those distinct dissipation processes. Based on an optically levitated nano-
oscillator, we successfully obtain precise measurements of the air pressure
surrounding the particles from atmosphere to $7\times 10^{-6}$ mbar, over $8$
orders of magnitude. It proves that the mechanical nano-oscillator is an
extremely promising candidate for precision pressure sensing applications.
Moreover, the second-order coherence analysis method on a classical system can
pave the way to characterize the dynamic properties of an oscillator, which
will benefit microscopic thermodynamics, precision measurement, and
macroscopic quantum research.

Introduction.-Mechanical oscillators, known for their high sensitivity to
various physical quantities, have garnered considerable attentions[1, 2, 3].
As an outstanding optomechanical system, optical levitation is a promising
platform for exploring mesoscopic-scale quantum superpositions[4, 5, 6, 7, 8,
9, 10, 11, 12, 13] and precision measurement[14, 15, 16, 17]. Due to its
unprecedented decoupling from the environment, it plays a significant role in
the field of force[18, 19, 20, 21, 22], mass[23, 24, 25, 26], and
acceleration[27, 28] sensing. Since the particle levitated in optical trap
experiences random collisions with surrounding gas molecules, this system
shows promise as a platform for precise pressure measurement.

In optical levitation, the displacement power spectral density (PSD), which is
the Fourier transform of the first-order autocorrelation function of the
oscillator’s motion trajectory[29], serves as a fundamental analysis tool to
identify the decoherence process. The primary source of decoherence arises
from collisions between trapped particles and air molecules. In the case of a
harmonic oscillator, the width of the PSD peak[30] provides information about
the decoherence induced by this stochastic process. However, limitations
emerge in PSD analysis when dealing with real mechanical systems due to the
presence of additional disturbances, such as nonlinearity in the restoring
force[31, 25, 32, 33] and system instability, which can amplify the
decoherence rate of the system.

Drawing inspiration from the second-order coherence analysis of light
intensity in quantum optics[34], we utilize an energy PSD analysis of a
classical oscillator, which is squared displacement PSD (sdPSD). It can
discern the distinct components of decoherence.

For an anharmonic oscillator, decoherence induced by thermal noise introduces
both energy and phase fluctuations, whereas decoherence arising from
nonlinearity and instability primarily manifests as phase fluctuations. The
autocorrelation of energy fluctuation can be separately obtained through the
second-order coherence analysis. Consequently, the distinction between
different decoherence processes presents a fundamental tool for diverse
studies and applications.

Here, we first employed the sdPSD to verify the feasibility of conducting
distinct analyses of different decoherence processes, where the system’s
energy decoherence is calibrated under the influence of anharmonicity in the
optical levitation system. Simultaneously, the energy decoherence related air
damping rate of the levitated nano-oscillator is precisely measured from
atmosphere to high vacuum.

We also assess its accuracy and robustness in the presence of nonlinearity and
instability. Hence, compared with other air pressure measurement methods[35,
36], this approach enables the continuous and absolute measurement of air
pressure within the range of $10^{3}$ to $7\times 10^{-6}$ mbar, offering a
high-accuracy and wide-range solution for gas pressure metrology with a
mechanical nano-oscillator.

Figure 1:  (a) The schematic diagram of optical levitation. A single silica
nanosphere, which is trapped by a $1064$ nm laser beam, collides with air
molecules in thermal motion randomly. (b) Part of the measured photodetector
signal along y direction at $1$ mbar. (c) The PSD of the detector signal
(orange solid). The dashed black line shows the result from Eq. (1) with
experiment condition and harmonic assumption. (d) Part of the squared detector
signal along y direction at $1$ mbar. (e) The PSD of the squared detector
signal (orange solid). The dashed black line shows the result from Eq. (2).

Dissipation processes characterized with sdPSD.-We investigate the measurement
of gas pressure using a nano-particle levitated in an optical trap. The
surrounding pressure can be obtained by analyzing the dissipation process of
its translational motions. In a harmonic potential, the PSD of the levitated
thermal equilibrium particle’s trajectory along one motion degree of freedom
can be described as[37]

$S_{xx}(\omega)=\frac{2k_{\mathrm{B}}T}{m}\frac{\Gamma_{0}}{(\omega^{2}-\omega_{0}^{2})^{2}+\omega^{2}\Gamma_{0}^{2}}\text{,}$
(1)

where $\Gamma_{0}$ is the damping rate introduced by the collisions with
surrounding molecules, which can be used to measure the pressure. $\omega_{0}$
is the eigenfrequency, $m$ and $T$ are the mass and temperature of the trapped
particle, and $k_{\mathrm{B}}$ is the Boltzmann constant. For a harmonic
oscillator, $\omega_{0}$ is a constant. However, in the presence of the
anharmonicity and instability, the eigenfrequency $\omega_{0}$ is no longer a
constant but $\omega_{0}(x,t)$[31], which induces phase fluctuations. And Eq.
(1) is no longer applicable for the description of the oscillator’s frequency
domain properties. Previous studies have attempted to figure out the PSD shape
under nonlinearity[38]. However, accurately estimating the PSD of realistic
levitation systems is challenging due to the complexity arising from
nonlinearity and stability condition[39, 40]. blackIn addition to employing
PSD, the measurement of $\Gamma_{0}$ for nonlinear oscillators can be
conducted using either the transient trajectories method[41] or the ring-down
method[42, 43]. However, the compatibility of transient trajectories method
under high vacuum conditions remains unverified, while the ring-down method is
not applicable to optical levitation system with shallow trapping potential
well.

Turning to the perspective of energy, we apply the second-order correlation to
present the potential energy PSD analysis. According to the research on a
Langevin oscillator[44], we can have the potential energy PSD of a harmonic
oscillator without the request of quasi-static assumption. Since the potential
energy is $E_{\text{p}}=1/2m\omega_{0}^{2}x^{2}$, the PSD of the squared
displacement is utilized for convenience, which is

$S_{x^{2}x^{2}}(\omega)=\frac{4\Gamma_{0}(k_{\mathrm{B}}T)^{2}}{m^{2}\omega_{0}^{2}}\frac{4\Gamma_{0}^{2}+\omega^{2}+4\omega_{0}^{2}}{(\omega^{2}+\Gamma_{0}^{2})[4\omega^{2}\Gamma_{0}^{2}+(\omega^{2}-4\omega_{0}^{2})^{2}]}\text{.}$
(2)

This sdPSD exhibits two peaks: a zero-frequency peak near $\omega=0$ and a
double-frequency peak near $\omega=2\omega_{0}$. The zero-frequency peak
characterizes energy fluctuations due to stochastic energy exchanges with the
thermal bath, showing the dissipation process ($\Gamma_{0}$) from the
collisions.

According to the dynamics of the levitated particle’s mechanical energy[45],
it is worth pointing out that under the quasi-static assumption, where the
energy dissipation time is much longer than the oscillation period, the energy
fluctuation introduced by the potential’s nonlinearity and instability becomes
negligible. And the PSD of the potential energy can be simplified to
$\displaystyle
S^{0}_{x^{2}x^{2}}(\omega)=\frac{(k_{\mathrm{B}}T)^{2}}{m^{2}\omega_{0}^{4}}\frac{\Gamma_{0}}{\omega^{2}+\Gamma_{0}^{2}}$
black[44], blackwhich has the same shape with the results of mechanical energy
PSD in the presence of nonlinearity[46]. It is independent of eigenfrequency
$\omega_{0}(x,t)$ and has been used to study ultra-high Q oscillators[42, 43,
47, 48, 49].

Experimental measurement of $\Gamma_{0}$.-In the optical levitation system, a
silica nanosphere (nominal radius $82\pm 10$ nm, Bangs labs Inc.) is trapped
in a vacuum chamber with an optical potential, which is formed by a focused
$1064$ nm Gaussian beam laser[50] with an objective lens (NA=$0.9$), as shown
in Fig. 1(a). Air molecules in the chamber collide randomly with the
nanosphere. The optical potential has Duffing nonlinearity component compared
with harmonic one, which results in shift in the oscillator’s eigenfrequency
at varying amplitudes[31]. The x-axis is parallel to the direction of laser
polarization.

The $3$-dimensional motion of the trapped particle is measured with homodyne
detection of forward scattering light with $3$ sets of balanced-
photodetector[33].

We record the trajectories of the nanosphere’s thermal motion from atmosphere
to high vacuum. As shown in Fig. 1(c), the measured PSD peak[30] is asymmetric
and wider than the theoretical fitting from Eq. (1) because of nonlinearity
induced significant asymmetric frequency shift. As for the sdPSD, it manifests
as two distinct peaks, as shown in Fig. 1(e). The double-frequency peak
undergoes broadening for the same reason as the PSD. In contrast, the zero-
frequency peak remains unaffected by nonlinearity and aligns consistently with
theoretical expectations, which is used to get the value of $\Gamma_{0}$ with
high accuracy in high vacuum.

For comparison, both the PSD and sdPSD of these trajectories are utilized to
obtain $\Gamma_{0}$. To get the zero-frequency peak of the sdPSD, a low-pass
fitting filter is employed by setting a threshold value equal to $1\%$ of the
maximum of the sdPSD. As the value of the sdPSD decreases with increasing
frequency from $0$ Hz, we mark a cutoff frequency $\omega_{\text{end}}$ when
the sdPSD value falls below the designated threshold for the first time. Only
the sdPSD data from $0$ Hz to $\omega_{\text{end}}$ are used for fitting the
air damping rate.

Also, the data of sdPSD at black$\omega/2\pi=0\text{Hz}$ is discarded, because
the mean value of the squared displacement is non-zero. . Figure 2 displays
$\Gamma_{0}$ fitted with Eq. (1) and Eq. (2), respectively. PSD fitting
remains approximately constant as the air pressure falls below a particular
threshold. However, in this regime, the air damping rate of the particle in
vacuum is expected to exhibit a linear relationship with air pressure[51, 52].
This is confirmed with the observation that $\Gamma_{0}$ derived from sdPSD
maintains a linear correlation with air pressure even under high vacuum
conditions.

Figure 2:  The damping rate from Eq. (1) and Eq. (2) as a function of gauge
pressure. Each data point and error bar represents the averaged damping rate
and standard deviation over $3$ axes and $10$ sampling trajectories. The
dashed line is a linear fitting. The duration for each trajectory is $2000$ s.

Besides the anharmonicity, the instability of the trapping laser constitutes a
significant source of error in estimating the parameters related to PSD
fitting. Similar to the nonlinearity that induces PSD broadening, power
fluctuations of the trapping laser directly lead to fluctuations in the
oscillator’s eigenfrequency. This, in turn, introduces additional broadening
to the PSD, resulting in errors in damping rate fitting. In order to verify
the sdPSD’s robustness in measuring air damping rates under system
instability, we perform the damping rate measurements at various laser
intensities and with different polarization directions. Fig. 3(a) illustrates
the observation of sdPSD in a fixed y-axis measurement direction while
rotating the polarization direction of the trapping laser using a half-wave
plate. The original double-frequency peak transforms into four peaks, each
corresponding to doubled eigenfrequencies along perpendicular and parallel
polarization directions, the sum frequency, and the difference frequency.
Meanwhile, the shape of the zero-frequency peak remains unchanged. The damping
rates obtained by fitting the zero-frequency peak at various polarization
angles exhibit consistency. Furthermore, as shown in Fig. 3(c), the
frequencies of sdPSD’s double-frequency peak shift when changing the intensity
of the trapping laser. However, the damping rate derived from fitting the
zero-frequency peaks remains constant.

Figure 3:  (a) sdPSDs of the y-axis trajectories under different polarization
angles at $0.1$ mbar. sdPSDs are normalized by the zero-frequency peaks. (b)
Damping rates measured along the y-axis under varying polarization angles. (c)
sdPSDs of the y-axis trajectories under varying trapping laser powers at
$0.005$ mbar. sdPSDs are normalized by the zero-frequency peaks. (d) Damping
rates measured along the y-axis under varying eigen-frequencies. Error bars in
both (b) and (d) represent the standard deviation of ten $300$-second
trajectories.

A nano vacuum gauge.-We can apply the high accurate $\Gamma_{0}$ to measure
the surrounding pressure. In Fig. 2 there is a gap obtained through sdPSD.
This gap coincides with the switching from capacitance gauges (CMR361 and
CMR364 by Pfeiffer Vacuum GmbH) to the cold cathode gauge (PKR361 by Pfeiffer
Vacuum GmbH). Capacitance gauges are accurate for pressure measurements,
whereas the reliability of the cold cathode gauge remains uncertain. For a
cold cathode gauge, apart from the $30\%$ measurement error mentioned in the
manufacturer’s manual, electrode contamination, such as the carbonization of
residual organic molecules, can significantly underestimate the measured
pressure compared to the actual values. In our experimental device, the cold
cathode gauge indicated pressure values approximately $50\%$ lower than those
recorded by the capacitance gauge under identical conditions[46].

However, this gap induced by gauges switching indicates that the air damping
rate of the levitated nanoparticle can be used to improve the accuracy of air
pressure measurements. A deterministic relationship exists between the air
damping rate of the nanoparticle and the air pressure, which is[53, 37]

$\Gamma_{0}=\frac{6\pi\eta
R}{m}\frac{0.619}{0.619+\text{Kn}}(1+c_{\text{K}})\text{,}$ (3)

where
$c_{\text{K}}=0.31\mathrm{Kn}/\left(0.785+1.152\mathrm{Kn}+\mathrm{Kn}^{2}\right)$,
$R$ is the radius of the nanosphere, $\eta$ is the viscosity coefficient of
atmosphere air, and $\mathrm{Kn}=\overline{l}/R$ is the Knudsen number.
Additionally, $\overline{l}=k_{\text{B}}T/\sqrt{2}\pi d^{2}P$ is the mean free
path of air molecules, where $P$ is the air pressure and $d$ is the collision
diameter of air molecules.

blackSince it is difficult to accurately determine the radius and mass of a
nanoparticle, direct use of Eq. (3) may introduce significant errors. For a
more accurate pressure measurement, the coefficients in Eq. (3) can be
calibrated by using an accurate reference pressure. By selecting several
damping rates $\Gamma_{0}$ calculated with sdPSD and corresponding capacitance
gauge readings as calibration points, the coefficients $A=6\pi\eta R/m$ and
$R$ are obtained by fitting Eq. (3) with the data of calibration points. The
calibrated Eq. (3) is used in the nanoparticle air pressure measurements.
Thus, this calibration process introduces a systematic error equal to the
error of the reference capacitance gauge ($0.2\%$ in the manufacturer’s
manual). Figure 4(a) demonstrates that employing a single levitated nanosphere
enables pressure measurements spanning over eight orders of magnitude, ranging
from atmospheric pressure to $7\times 10^{-6}$ mbar, blackwhere the measured
pressure with nanoparticle $P_{\text{measure}}$ is extracted with the damping
rate $\Gamma_{0}$ in Fig. 2 and Eq. (3). Within the pressure range suitable
for capacitance gauge operation, the air pressure values derived from sdPSD-
based damping rate measurements align with the gauge readings. Conversely,
within the range of operation for the cold cathode gauge, the pressures
obtained from sdPSD measurements higher than the cold cathode gauge. This
discrepancy can be attributed to the measurement error of the cold cathode
gauge.

Figure 4:  (a) Comparison of measured pressures using sdPSD (red dots) and
pressure values from gauges (blue squares). The measured pressure data is an
average from $3$-axis damping rates, blackand its error bar represents the
standard deviation of $10$ segments of $2000$ s trajectories and the
systematic error introduced by the calibration process. The error bar for
gauge pressure is sourced from the manufacturer’s manuals. (b) Relative Allan
deviation analysis of pressure measurements. The black dashed lines represent
a curve fitting based on the data in the form of $1/\sqrt{\tau}$.

Additionally, the relative Allan deviation for sdPSD pressure measurements is
obtained. Figure 4(b) illustrates that the relationship among the relative
standard deviation ($\sigma$) of pressure measurements, the integration time
$\tau$, and the pressure ($P$) follows $\sigma/P=C/\sqrt{P\tau}$, where
$C=0.0399(5)\text{ }\mathrm{mbar}^{1/2}\cdot\mathrm{s}^{1/2}$. We can have the
sensitivity of the pressure measurement, which is $S_{P}=C\sqrt{P}$. Lower
measured pressures necessitate longer measurement times to achieve the same
relative error. This is because the sdPSD pressure measurement relies on
fitting the width of the sdPSD zero-frequency peak, which narrows as pressure
decreases. Consequently, longer integration times are necessary for the
desired spectral resolution. In the case of pressure measurements within the
operational range of the cold cathode gauge in Fig. 4(a), we utilize $10$
segments of 3-dimensional trajectory data, each segments with a duration of
$2000$ s.

The lower boundary of pressure measurements using sdPSD hinges on two
constraints. Firstly, it is determined by the minimum air pressure at which
the particle can remain stably trapped under thermal equilibrium without
external control. The application of motion control would introduce an
additional damping that alters the width of the sdPSD zero-frequency peak,
making the extraction of the air damping rate unfeasible. Nevertheless, in the
absence of feedback control, optically levitated particles are susceptible to
loss under conditions of high vacuum[54]. In our experiments, particle loss
occurs during measurements at an air pressure of approximately $5\times
10^{-6}$ mbar. Secondly, when the optically levitated nano-particle is in a
vacuum below $10^{-8}$ mbar, recoil heating from the trapping laser has become
the dominant energy decoherence source over stochastic collisions with air
molecules[2, 55, 56], making the sdPSD-based air pressure measurements
impractical.

Conclusion.-In conclusion, we have presented a novel method for quantifying
energy dissipation in levitated mechanical systems. This method relies on
second-order coherence analysis with the squared displacement power spectrum
density. Through this approach, we are able to mitigate the influence of phase
decoherence stemming from nonlinearities and instabilities on the calculation
of the nano-oscillator’s damping rate. This proposed method for determining
the damping rate demonstrates robustness across independent oscillation axes
and at different eigenfrequencies. In addition, we have successfully applied
this method to measure the air pressure from the atmosphere to $7\times
10^{-6}$ mbar with high accuracy.

The method presented in this study for addressing anharmonic oscillators is
versatile and can be applied to a broader spectrum of nano-, micro-mechanical
systems. Additionally, our work offers a reliable means of absolute pressure
measurement, particularly under wide dynamic range conditions. The air
pressure value derived using this method directly aligns with the definition
of air pressure, which signifies the mechanical impact resulting from air
molecule collisions. This characteristic makes it a valuable reference for
calibrating pressure gauges.

This work was supported by the National Natural Science Foundation of China
(Grant No. 12104438 and No. 62225506), the CAS Project for Young Scientists in
Basic Research (Grant No. YSBR-049), and the Fundamental Research Funds for
the Central Universities.

## References

  * Millen  _et al._ [2020] J. Millen, T. S. Monteiro, R. Pettit, and A. N. Vamivakas, Optomechanics with levitated particles, Rep. Prog. Phys. 83, 026401 (2020).
  * Gonzalez-Ballestero  _et al._ [2021] C. Gonzalez-Ballestero, M. Aspelmeyer, L. Novotny, R. Quidant, and O. Romero-Isart, Levitodynamics: Levitation and control of microscopic objects in vacuum, Science 374, eabg3027 (2021).
  * Bachtold  _et al._ [2022] A. Bachtold, J. Moser, and M. I. Dykman, Mesoscopic physics of nanomechanical systems, Rev. Mod. Phys. 94, 045005 (2022).
  * Aspelmeyer  _et al._ [2014] M. Aspelmeyer, T. J. Kippenberg, and F. Marquardt, Cavity optomechanics, Rev. Mod. Phys. 86, 1391 (2014).
  * Millen  _et al._ [2015] J. Millen, P. Z. G. Fonseca, T. Mavrogordatos, T. S. Monteiro, and P. F. Barker, Cavity cooling a single charged levitated nanosphere, Phys. Rev. Lett. 114, 123602 (2015).
  * Delić  _et al._ [2020] U. Delić, M. Reisenbauer, K. Dare, D. Grass, V. Vuletić, N. Kiesel, and M. Aspelmeyer, Cooling of a levitated nanoparticle to the motional quantum ground state, Science 367, 892 (2020).
  * Magrini  _et al._ [2021] L. Magrini, P. Rosenzweig, C. Bach, A. Deutschmann-Olek, S. G. Hofer, S. Hong, N. Kiesel, A. Kugi, and M. Aspelmeyer, Real-time optimal quantum control of mechanical motion at room temperature, Nature 595, 373 (2021).
  * Tebbenjohanns  _et al._ [2021] F. Tebbenjohanns, M. L. Mattana, M. Rossi, M. Frimmer, and L. Novotny, Quantum control of a nanoparticle optically levitated in cryogenic free space, Nature 595, 378 (2021).
  * Ranfagni  _et al._ [2022] A. Ranfagni, K. Børkje, F. Marino, and F. Marin, Two-dimensional quantum motion of a levitated nanosphere, Phys. Rev. Res. 4, 033051 (2022).
  * Kamba  _et al._ [2022] M. Kamba, R. Shimizu, and K. Aikawa, Optical cold damping of neutral nanoparticles near the ground state in an optical lattice, Opt. Express 30, 26716 (2022).
  * Vijayan  _et al._ [2023] J. Vijayan, Z. Zhang, J. Piotrowski, D. Windey, F. van der Laan, M. Frimmer, and L. Novotny, Scalable all-optical cold damping of levitated nanoparticles, Nat. Nanotechnol. 18, 49 (2023).
  * Pontin  _et al._ [2023] A. Pontin, H. Fu, M. Toroš, T. S. Monteiro, and P. F. Barker, Simultaneous cavity cooling of all six degrees of freedom of a levitated nanoparticle, Nat. Phys. 19, 1003 (2023).
  * Piotrowski  _et al._ [2023] J. Piotrowski, D. Windey, J. Vijayan, C. Gonzalez-Ballestero, A. de los Ríos Sommer, N. Meyer, R. Quidant, O. Romero-Isart, R. Reimann, and L. Novotny, Simultaneous ground-state cooling of two mechanical modes of a levitated nanoparticle, Nat. Phys. 19, 1009 (2023).
  * Li  _et al._ [2010] T. Li, S. Kheifets, D. Medellin, and M. G. Raizen, Measurement of the instantaneous velocity of a brownian particle, Science 328, 1673 (2010).
  * Millen  _et al._ [2014] J. Millen, T. Deesuwan, P. Barker, and J. Anders, Nanoscale temperature measurements using non-equilibrium brownian dynamics of a levitated nanosphere, Nat. Nanotechnol. 9, 425 (2014).
  * Hebestreit  _et al._ [2018a] E. Hebestreit, R. Reimann, M. Frimmer, and L. Novotny, Measuring the internal temperature of a levitated nanoparticle in high vacuum, Phys. Rev. A 97, 043803 (2018a).
  * Kamba and Aikawa [2023] M. Kamba and K. Aikawa, Revealing the velocity uncertainties of a levitated particle in the quantum ground state, Phys. Rev. Lett. 131, 183602 (2023).
  * Ranjit  _et al._ [2016] G. Ranjit, M. Cunningham, K. Casey, and A. A. Geraci, Zeptonewton force sensing with nanospheres in an optical lattice, Phys. Rev. A 93, 053801 (2016).
  * Hempston  _et al._ [2017] D. Hempston, J. Vovrosh, M. Toroš, G. Winstone, M. Rashid, and H. Ulbricht, Force sensing with an optically levitated charged nanoparticle, Appl. Phys. Lett. 111, 133111 (2017).
  * Hebestreit  _et al._ [2018b] E. Hebestreit, M. Frimmer, R. Reimann, and L. Novotny, Sensing static forces with free-falling nanoparticles, Phys. Rev. Lett. 121, 063602 (2018b).
  * Blakemore  _et al._ [2019a] C. P. Blakemore, A. D. Rider, S. Roy, Q. Wang, A. Kawasaki, and G. Gratta, Three-dimensional force-field microscopy with optically levitated microspheres, Phys. Rev. A 99, 023816 (2019a).
  * Blakemore  _et al._ [2021] C. P. Blakemore, A. Fieguth, A. Kawasaki, N. Priel, D. Martin, A. D. Rider, Q. Wang, and G. Gratta, Search for non-newtonian interactions at micrometer scale with a levitated test mass, Phys. Rev. D 104, L061101 (2021).
  * Blakemore  _et al._ [2019b] C. P. Blakemore, A. D. Rider, S. Roy, A. Fieguth, A. Kawasaki, N. Priel, and G. Gratta, Precision mass and density measurement of individual optically levitated microspheres, Phys. Rev. Appl. 12, 024037 (2019b).
  * Ricci  _et al._ [2019] F. Ricci, M. T. Cuairan, G. P. Conangla, A. W. Schell, and R. Quidant, Accurate mass measurement of a levitated nanomechanical resonator for precision force-sensing, Nano Lett. 19, 6711 (2019).
  * Zheng  _et al._ [2020a] Y. Zheng, L.-M. Zhou, Y. Dong, C.-W. Qiu, X.-D. Chen, G.-C. Guo, and F.-W. Sun, Robust optical-levitation-based metrology of nanoparticle’s position and mass, Phys. Rev. Lett. 124, 223603 (2020a).
  * Tian  _et al._ [2023] Y. Tian, Y. Zheng, L.-H. Liu, G.-C. Guo, and F.-W. Sun, Temperature-free mass tracking of a levitated nanoparticle, Chin. Phys. B 32, 074207 (2023).
  * Monteiro  _et al._ [2017] F. Monteiro, S. Ghosh, A. G. Fine, and D. C. Moore, Optical levitation of 10-ng spheres with nano-$g$ acceleration sensitivity, Phys. Rev. A 96, 063841 (2017).
  * Monteiro  _et al._ [2020] F. Monteiro, W. Li, G. Afek, C.-l. Li, M. Mossman, and D. C. Moore, Force and acceleration sensing with optically levitated nanogram masses at microkelvin temperatures, Phys. Rev. A 101, 053835 (2020).
  * Chatfield [1989] C. Chatfield,  _The Analysis of Time Series: An Introduction_ , 4th ed. (Chapman and Hall, London, 1989) pp. 94–95.
  * Berg-Sørensen and Flyvbjerg [2004] K. Berg-Sørensen and H. Flyvbjerg, Power spectrum analysis for optical tweezers, Rev. Sci. Instrum. 75, 594 (2004).
  * Gieseler  _et al._ [2013] J. Gieseler, L. Novotny, and R. Quidant, Thermal nonlinearities in a nanomechanical oscillator, Nat. Phys. 9, 806 (2013).
  * Tian  _et al._ [2022] Y. Tian, Y. Zheng, L.-H. Liu, G.-C. Guo, and F.-W. Sun, Medium vacuum feasible displacement calibration of an optically levitated duffing nonlinear oscillator, Appl. Phys. Lett. 120, 221103 (2022).
  * Zheng  _et al._ [2023] Y. Zheng, L.-H. Liu, X.-D. Chen, G.-C. Guo, and F.-W. Sun, Arbitrary nonequilibrium steady-state construction with a levitated nanoparticle, Phys. Rev. Res. 5, 033101 (2023).
  * Walls and Milburn [2008] D. Walls and G. Milburn,  _Quantum Optics_ , 2nd ed. (Springer, Berlin, 2008) p. 44.
  * Kuhn  _et al._ [2017] S. Kuhn, B. A. Stickler, A. Kosloff, F. Patolsky, K. Hornberger, M. Arndt, and J. Millen, Optically driven ultra-stable nanomechanical rotor, Nat. Commun. 8, 1670 (2017).
  * Blakemore  _et al._ [2020] C. P. Blakemore, D. Martin, A. Fieguth, A. Kawasaki, N. Priel, A. D. Rider, and G. Gratta, Absolute pressure and gas species identification with an optically levitated rotor, J. Vac. Sci. Technol. B 38, 024201 (2020).
  * Li [2012] T. Li,  _Fundamental Tests of Physics with Optically Trapped Microspheres_ (Springer New York, New York, 2012) pp. 57–125.
  * Suassuna  _et al._ [2021] B. Suassuna, B. Melo, and T. Guerreiro, Path integrals and nonlinear optical tweezers, Phys. Rev. A 103, 013110 (2021).
  * Harada and Asakura [1996] Y. Harada and T. Asakura, Radiation forces on a dielectric sphere in the rayleigh scattering regime, Opt. Commun. 124, 529 (1996).
  * Novotny and Hecht [2012] L. Novotny and B. Hecht,  _Principles of Nano-Optics_ (Cambridge University Press, Cambridge, 2012).
  * Flajšmanová  _et al._ [2020] J. Flajšmanová, M. Šiler, P. Jedlička, F. Hrubý, O. Brzobohatý, R. Filip, and P. Zemánek, Using the transient trajectories of an optically levitated nanoparticle to characterize a stochastic duffing oscillator, Sci. Rep. 10, 14436 (2020).
  * Stipe  _et al._ [2001] B. C. Stipe, H. J. Mamin, T. D. Stowe, T. W. Kenny, and D. Rugar, Noncontact friction and force fluctuations between closely spaced bodies, Phys. Rev. Lett. 87, 096801 (2001).
  * Zheng  _et al._ [2020b] D. Zheng, Y. Leng, X. Kong, R. Li, Z. Wang, X. Luo, J. Zhao, C.-K. Duan, P. Huang, J. Du, M. Carlesso, and A. Bassi, Room temperature test of the continuous spontaneous localization model using a levitated micro-oscillator, Phys. Rev. Res. 2, 013057 (2020b).
  * Mishin and Hickman [2016] Y. Mishin and J. Hickman, Energy spectrum of a langevin oscillator, Phys. Rev. E 94, 062151 (2016).
  * Gieseler  _et al._ [2015] J. Gieseler, L. Novotny, C. Moritz, and C. Dellago, Non-equilibrium steady state of a driven levitated particle with feedback cooling, New J. Phys. 17, 045011 (2015).
  * [46] See Supplemental Material at [URL] for details of the dynamic of a levitated oscillator’s energy, and the comparison between cold cathode gauge and capacitance gauge. .
  * Pontin  _et al._ [2020] A. Pontin, N. P. Bullier, M. Toroš, and P. F. Barker, Ultranarrow-linewidth levitated nano-oscillator for testing dissipative wave-function collapse, Phys. Rev. Res. 2, 023349 (2020).
  * Bullier  _et al._ [2021] N. P. Bullier, A. Pontin, and P. F. Barker, Quadratic optomechanical cooling of a cavity-levitated nanosphere, Phys. Rev. Res. 3, L032022 (2021).
  * Golokolenov  _et al._ [2023] I. Golokolenov, A. Ranadive, L. Planat, M. Esposito, N. Roch, X. Zhou, A. Fefferman, and E. Collin, Thermodynamics of a single mesoscopic phononic mode, Phys. Rev. Res. 5, 013046 (2023).
  * Zheng and Sun [2019] Y. Zheng and F. Sun, Three-dimensional position measurement of a levitated nanoparticle in a vacuum by a dove prism, Chin. Opt. Lett. 17, 060901 (2019).
  * Epstein [1924] P. S. Epstein, On the resistance experienced by spheres in their motion through gases, Phys. Rev. 23, 710 (1924).
  * Li and Wang [2003] Z. Li and H. Wang, Drag force, diffusion coefficient, and electric mobility of small particles. i. theory applicable to the free-molecule regime, Phys. Rev. E 68, 061206 (2003).
  * Beresnev  _et al._ [1990] S. A. Beresnev, V. G. Chernyak, and G. A. Fomyagin, Motion of a spherical particle in a rarefied gas. part 2. drag and thermal polarization, J. Fluid Mech. 219, 405 (1990).
  * Zheng  _et al._ [2019] Y. Zheng, G.-C. Guo, and F.-W. Sun, Cooling of a levitated nanoparticle with digital parametric feedback, Appl. Phys. Lett. 115, 101105 (2019).
  * Jain  _et al._ [2016] V. Jain, J. Gieseler, C. Moritz, C. Dellago, R. Quidant, and L. Novotny, Direct measurement of photon recoil from a levitated nanoparticle, Phys. Rev. Lett. 116, 243601 (2016).
  * Kamba  _et al._ [2021] M. Kamba, H. Kiuchi, T. Yotsuya, and K. Aikawa, Recoil-limited feedback cooling of single nanoparticles near the ground state in an optical lattice, Phys. Rev. A 103, L051701 (2021).