# Time Changed Normalizing Flows for accurate SDE modeling

###### Abstract

The generative paradigm has become increasingly important in machine learning
and deep learning models. Among popular generative models are normalizing
flows, which enable exact likelihood estimation by transforming a base
distribution through diffeomorphic transformations. Extending the normalizing
flow framework to handle time-indexed flows gave dynamic normalizing flows, a
powerful tool to model time series, stochastic processes, and neural
stochastic differential equations (SDEs). In this work, we propose a novel
variant of dynamic normalizing flows, a Time Changed Normalizing Flow (TCNF),
based on time deformation of a Brownian motion which constitutes a versatile
and extensive family of Gaussian processes. This approach enables us to
effectively model some SDEs, that cannot be modeled otherwise, including
standard ones such as the well-known Ornstein-Uhlenbeck process, and
generalizes prior methodologies, leading to improved results and better
inference and prediction capability.

Index Terms—  Stochastic differential equations, deep generative models,
normalizing flows, time series, convex neural network.

##  1 Introduction

Dynamical systems have widespread use in various scientific areas such as
finance, geosciences, and physics. The representation of these systems usually
involves Ordinary Differential Equations (ODEs), or Stochastic Differential
Equations (SDEs) [1] when noise and perturbations, on top of the deterministic
component, are considered. Crucial applications include modeling volatility in
financial data, or uncertainty quantification and propagation in geosciences.
Tackling such systems through time series modeling has witnessed a surge in
popularity within the machine learning paradigm, and more recently through the
generative approach, for forecasting applications, but also for filtering or
interpolation with a notion of uncertainty in the generated sequences.

Popular generative models include Generative Adversarial Networks (GANs) [2]
and variational autoencoders (VAEs) [3], but also more recently normalizing
flows (NFs) [4, 5] and diffusion/score based models [6]. Though these models
can be applied to generate time series, they are not well-suited for the task
because they treat such data as vectors in $\mathbb{R}^{T}$, with $T$ the
number of time steps, without accounting for the causal structure. Adaptations
of GANs, VAEs, and NFs to time series data have been carried out in [7, 8],[9,
10],[11, 12], respectively. In this work, we focus on NFs for their capacity
to access explicit likelihoods, which is crucial for applications when
uncertainty quantification or anomaly detection is required.

NFs are based on the celebrated change of variables formula that provides an
expression of the probability density function of diffeomorphic
transformations of a random variable. With carefully chosen transformations
(or compositions thereof), if the initial density is tractable (explicit
likelihood and easy sampling, in most cases Gaussian), the transformed density
can be easily manipulated and sampled as well, provided that the Jacobian of
the transformation can be computed efficiently. By considering an infinite
number of transformations, representing the limit case of discrete NFs, we can
build a Continuous Normalizing Flow (CNF) [13]. This can further improve the
computational efficiency of this class of models as we replace the Jacobian by
the integration of its trace.

NFs have been extended to the dynamic setting by replacing the tractable base
distribution with a tractable _stochastic process_ , i.e. a Brownian motion
[14], making this type of model much more efficient for time series
generation. However, it was noted in [15] that these models are theoretically
unable to handle some of the most basic and common processes, such as the
classical Ornstein-Uhlenbeck process.

Thus, in this paper, we propose a generalization of this class of approaches
by using a large family of Gaussian processes as the underlying base process
instead of the conventional standard Brownian motion. The Gaussian processes
are constructed by transforming through time the standard Brownian motion,
giving rise to Time Changed Normalizing Flow (TCNF), a model that possesses
mathematical properties that enable it to describe dynamics and SDEs that
cannot be captured by previous flow-based models, while maintaining the
expressivity of dynamic NFs in other cases. We corroborate these findings by
numerical experiments on several well-known processes.

The remainder of this paper is organized as follows: we first provide, in
section 2, an overview of the neural SDEs, wherein both the drift and
diffusion are neural networks, and the dynamic normalizing flow approach and a
discussion on the inherent limitations of such models. Afterward, in section
3, we introduce our model and describe its characteristics and the training
algorithm. Finally, quantitative results are presented in section 4 and
compared to other flow-based models, and provide concluding remarks in section
5.

Fig. 1: A time change $\phi$ is applied to the Wiener process (red) to create
a new Gaussian process, which is then mapped through a bijection $f_{\theta}$
to the observed process (blue).

##  2 Background

###  2.1 Neural Stochastic Differential Equations

We consider a filtered probability space $(\Omega,\mathcal{F},P)$ and a time
horizon $T$. A diffusion process $X=\\{X_{t}\\}_{t\in[0,T]}$ is defined by the
Itô Stochastic Differential Equation (SDE):

$\displaystyle dX_{t}=\mu(X_{t},t)dt+\sigma(X_{t},t)dW_{t},t\in[0,T]$ (1)

where $W=\\{W_{t}\\}_{t\in[0,T]}$ is the $m$-dimensional adapted standard
Wiener process (or Brownian motion). Functions
$\mu:\mathbb{R}^{d}\times[0,T]\longrightarrow\mathbb{R}^{d}$ and
$\sigma:\mathbb{R}^{d}\times[0,T]\longrightarrow\mathbb{R}^{d\times m}$ are
the drift and diffusion coefficients, respectively. When $\mu$ and $\sigma$
are implemented by neural networks, the SDE is designated as a neural SDE [16,
17].

Several works have been proposed to learn neural SDEs using different
generative modeling frameworks including Variational Autoencoders (VAEs) [9,
10] and Generative Adversarial Networks (GANs) [8]. In this paper, we
specifically focus on the normalizing flow paradigm.

###  2.2 Normalizing flows

A normalizing flow [4, 5, 13] is a transformation designed to model a random
variable $X$ and its corresponding complex distribution $p_{X}$ through a base
distribution $p_{Z}$ and a differentiable bijective function
$f:\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d}$. Such modeling allows for both
exact density estimation and efficient sampling, by using the change of
variable formula for $X=f(Z)$:

$\log p_{X}(x)=\log p_{Z}(z)-\log\left|\det\left(\frac{\partial f}{\partial
z}(z)\right)\right|$ (2)

Previous works have extended this framework to model time series and
stochastic processes by employing a bijection that is continuously indexed by
time $F(.,t)$, along with a Brownian motion as the base process, giving rise
to a Continuous Time Flow Process (CTFP) [14]:

$\displaystyle X_{t}=F(W_{t},t).$

Another approach proposed by [15] involves incorporating latent dynamics from
an Ornstein-Uhlenbeck process combined with a normalizing flow to effectively
model SDEs.

These models have demonstrated the effectiveness of dynamic NFs in capturing
the complex behavior present in various types of stochastic processes and
SDEs. However, it is important to highlight that these models have inherent
limitations. One constraint arises when applying Itô’s lemma to CTFP in order
to derive the Ornstein-Uhlenbeck (OU) process described by the equation:

$\displaystyle dY_{t}=-a(Y_{t}-b)dt+\sigma dW_{t}$ (3)

Indeed, by applying Itô’s lemma to $F(W_{t},t)$ we obtain:

$\displaystyle\begin{split}dF(W_{t},t)=&\frac{\partial F}{\partial
t}(W_{t},t)dt+\frac{\partial F}{\partial x}(W_{t},t)dW_{t}\\\
&+\frac{1}{2}\frac{\partial^{2}F}{\partial x^{2}}(W_{t},t)dt\end{split}$ (4)

By comparing both Eq. (3) and Eq. (4), we deduce that to model the OU process,
we need to have $\frac{\partial F}{\partial x}(W_{t},t)=\sigma$, implying that
$F(W_{t},t)=\sigma W_{t}+g(t)$, where $g$ is a given differentiable function.
However, differentiating this relation wrt $t$ and plugging in (3) leads to
the following condition:

$\displaystyle\frac{dg}{dt}(t)+ag(t)-ab=-a\sigma W_{t}$ (5)

Eq. (5) is not feasible as the left-hand side is a deterministic function of
$t$ while the right-hand side is a stochastic one depending on $W_{t}$. Thus,
CTFP shows limitations and falls short in its ability to effectively model
various stochastic processes.

In the following section, we propose a model that can address this limitation
and achieve improved results.

##  3 Dynamic Normalizing flow with time change

###  3.1 Time changed Normalizing Flow

We propose to model an observed stochastic process, denoted as
$X=\\{X_{t}\\}_{t\in[0,T]}$, by combining a normalizing flow and a time-
changed Wiener process to accurately capture the dynamic behavior of $X_{t}$
based on a realized time series $\\{(x_{t_{i}},t_{i})\\}_{i=1}^{n}$. We
introduce the concept of a time-changed normalizing flow (TCNF), defined as
follows:

$\displaystyle X_{t}=f_{\theta}\left(W_{\phi(t)},\phi(t)\right),\quad\forall
t\in[0,T],\vspace{-0.2cm}$

where $f_{\theta}(.,t):\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d}$ is a
differentiable bijection parameterized by $\theta$, while $W_{\phi(t)}$
denotes a Brownian motion with a time change [18, Sect. 1 Chap. 0]. The time
change is given by $\phi:\mathbb{R}^{+}\longrightarrow\mathbb{R}^{+}$, which
is a measurable, positive and increasing function. The measurable and positive
properties ensure the correct definition of $W_{\phi(t)}$, while the
increasing property ensures the existence of its moments. Consequently, the
neural network modeling the time change function must have intrinsically
positive and increasing attributes. The property of time change has important
applications as it produces a family of Gaussian processes that are more
general than the Brownian motion. The Dubins-Schwarz theorem [18, Theorem
5.1.6] further emphasizes this property as it states that every local
martingale is simply a time-changed Brownian motion. Therefore, by making the
base process of our model a time-changed Brownian motion, we can accurately
capture all instances of local martingales and semimartingales, thus
generalizing the CTFP setting. In fact, the solution to Eq. (3) can be
expressed as follows:

$\displaystyle Y_{t}=Y_{0}e^{-at}+b(1-e^{-at})+\frac{\sigma
e^{-at}}{\sqrt{2a}}W_{e^{2at}-1}$ (6)

which can be properly modeled by TCNF. More general cases like processes with
time-dependent volatility can also be expressed via a time-change and
therefore modeled by TCNF. Finally, for $\phi(t)=t$ we recover the CTFP
setting, which is suitable for modeling SDEs that do not require a time-change
as the Geometric Brownian Motion (GBM) [1].

###  3.2 Time change function

To handle the time change function, we employ a convex neural network that
ensures a positive gradient, thereby guaranteeing a monotone output.
Specifically, we utilize the M-MGN architecture [19] based on $K$ network
modules defined as follows:

$\displaystyle\begin{split}\tilde{t}_{k}&=W_{k}\times t+b_{k},\\\
\text{M-MGN}(t)&=a+V^{\top}Vt+\sum_{k=1}^{K}s_{k}(\tilde{t}_{k})\times
W_{k}^{\top}\sigma_{k}(\tilde{t}_{k})\end{split}$ (7)

where $W_{k},b_{k}\in\mathbb{R}^{l\times 1}$ are respectively weight and bias
vectors of the $k^{th}$ layer,
$\sigma_{k}:\mathbb{R}^{l}\longrightarrow\mathbb{R}^{l}$ is an activation
function and $s_{k}:\mathbb{R}^{l}\longrightarrow\mathbb{R}$ its
antiderivative. $a\in\mathbb{R}$ and $V\in\mathbb{R}^{l\times 1}$ are
additional network parameters. As the result is not necessarily positive, we
apply a translation of the M-MGN output to ensure that the time change is
positive.

###  3.3 Training algorithm

The purpose is to train the TCNF in order to maximize the log-likelihood of
the observed dataset $\\{(x_{t_{i}},t_{i})\\}_{i=1}^{n}$:

$\displaystyle L=\log p_{X_{t_{1}},...,X_{t_{n}}}(x_{t_{1}},...,x_{t_{n}})$
(8)

To compute Eq.(8), we use the change of variable formula and leverage the
independence of increments $W_{\phi(t_{i})}-W_{\phi(t_{i-1})}$. Thus, the log-
likelihood is expressed as follows:

$\displaystyle\begin{split}L=\sum_{i=1}^{n}&\log
p_{W_{\phi(t_{i})}|W_{\phi(t_{i-1})}}\left(w_{\phi(t_{i})}\right)\\\
&-\log\left|\det\frac{\partial
f_{\theta}\left(w_{\phi(t_{i})},\phi(t_{i})\right)}{\partial
W_{\phi(t_{i})}}\right|,\end{split}$ (9)

where $w_{\phi(t_{i})}=f_{\theta}^{-1}\left(x_{t_{i}};\phi(t_{i})\right)$ and
$p_{W_{\phi(t_{i})}|W_{\phi(t_{i-1})}}$ denotes the conditional Gaussian
distribution with mean $W_{\phi(t_{i-1})}$ and variance
$\phi(t_{i})-\phi(t_{i-1})$. This constitutes one notable difference from the
log-likelihood of CTFP which uses a Gaussian distribution with the same mean
but variance $t_{i}-t_{i-1}$.

##  4 Experiments

###  4.1 Toy datasets

To evaluate the performance of our proposed model, we conducted experiments on
three toy datasets comprising univariate time series. These datasets were
generated by sampling from three different stochastic processes. Also, in our
experiments we used an identical architecture as CTFP, leveraging CNFs.

The first dataset (Toy-SDE1) was generated by discretizing the OU process,
given by the equation: $dX_{t}=-\theta(X_{t}-\mu)dt+\sigma dW_{t}$, where
$\mu$ and $\sigma$ represent constant parameters for the drift and volatility
terms, respectively. Parameter $\theta$ captures the speed at which a given
sample path of the process converges towards the drift term. This dataset aims
to assess the model’s ability to capture the dynamics of time changes.

The second dataset (Toy-SDE2) was generated based on the equation:
$dX_{t}=-\theta(X_{t}-\mu)dt+\sigma\sqrt{t}dW_{t}$, describing an OU with a
time-dependent diffusion coefficient, and is used to test the model’s
capability to capture time transformations with increasing complexity.
Notably, this SDE is of interest as it is commonly used in score-based models
[20], where noise is gradually introduced during the training process.

Finally, The third dataset (Toy-SDE3) involved the geometric brownian motion,
described by the equation: $dX_{t}=\mu X_{t}dt+\sigma X_{t}dW_{t}$, where
$\mu$ and $\sigma$ represent constant parameters for the drift and volatility
terms, respectively. This dataset was designed to showcase the capacity of
TCNF to handle SDEs where no time change is required, effectively learning the
simple function $\phi(t)=t$. This shows that our approach can encompass the
CTFP framework.

Dataset | Model | $m_{X_{t}}$ | $\sigma_{X_{t}}$ | IQR | $p_{X_{t}}$
---|---|---|---|---|---
Toy-SDE1 | CTFP | $0.022\pm 0.009$ | $0.241\pm 0.012$ | $0.886\pm 0.021$ | $0.062$
TCNF | $\mathbf{0.019}\pm\mathbf{0.007}$ | $\mathbf{0.109}\pm\mathbf{0.009}$ | $\mathbf{0.700}\pm\mathbf{0.014}$ | $\mathbf{0.033}$
Toy-SDE2 | CTFP | $0.059\pm 0.011$ | $0.523\pm 0.018$ | $1.517\pm 0.037$ | $0.087$
TCNF | $\mathbf{0.024}\pm\mathbf{0.012}$ | $\mathbf{0.322}\pm\mathbf{0.016}$ | $\mathbf{1.183}\pm\mathbf{0.024}$ | $\mathbf{0.061}$
Toy-SDE3 | CTFP | $\mathbf{0.035}\pm\mathbf{0.020}$ | $\mathbf{0.086}\pm\mathbf{0.056}$ | $1.103\pm 0.037$ | $\mathbf{0.005}$
TCNF | $0.036\pm 0.018$ | $0.099\pm 0.072$ | $\mathbf{1.083}\pm\mathbf{0.038}$ | $0.007$
Table 1: Quantitative analysis: We display mean absolute errors (MAE) for
estimating respectively the mean, standard deviation, interquartile range IQR
= $Q_{3}-Q_{1}$, and density. The estimations are based on 1000 sample paths
over 1000 iterations.

Fig. 2: Comparison between TCNF and CTFP on toy-SDE1 (Top) and toy-SDE2
(Bottom). In each figure we depict density MAE between the flow-based models
and the ground truth, along the mean (continuous line) and the IQR (dashed
line).

The quantitative comparison is carried by comparing estimations of the mean
$m_{X_{t}}$, the standard-deviation $\sigma_{X_{t}}$, the interquartile range
IQR$=Q_{3}-Q_{1}$, and the density $p_{X_{t}}$ respectively. For each model,
we compute the mean absolute errors (MAE) against the ground-truth values. The
mean, standard deviation, and quartiles are estimated based on 1000 sample
paths over 1000 iterations, while the density is estimated by the change of
variable formula on a grid consisting of 1000 spatial points and 500 temporal
points within the time interval $[0,T=1.5]$. The quantitative results reported
in Table 1 and Figure 2 show first that TCNF shows no loss in generality as it
handles cases where no time change is required, and second that our model
exhibits superior estimation capability, as it can capture the behavior of
time changed ground truth solutions.

###  4.2 Real-world datasets

To further assess our model’s capacity to capture complex dynamics, we train
it on two real-world datasets: Crypto-forecasting (Crypto) [21] and Electric
Consumption Load (ECL) [22]. The Crypto dataset contains historical prices of
various cryptocurrencies such as Bitcoin or Ethereum. We focused our analysis
on modeling Ethereum returns over the 2020 period. The ECL dataset comprises
electricity consumption data from multiple clients within a 15-minute
interval. We choose to model the consumption of client ’200’ as its data
offers one of the most extended time series.

The results comprise mean absolute errors (MAE) for estimating the mean
($m_{X_{t}}$) and standard deviation ($\sigma_{X_{t}}$) for the Crypto
dataset. For the ECL dataset, we employed mean relative errors (MRE) to scale
the results appropriately. These results are reported in Table 2 and compared
against CTFP.

Dataset | Model | $m_{X_{t}}$ | $\sigma_{X_{t}}$
---|---|---|---
Crypto | CTFP | $0.083\pm 0.007$ | $0.232\pm 0.009$
TCNF | $\mathbf{0.025}\pm\mathbf{0.001}$ | $\mathbf{0.131}\pm\mathbf{0.005}$
ECL | CTFP | $0.771\pm 0.108$ | $26.972\pm 8.634$
TCNF | $\mathbf{0.299}\pm\mathbf{0.007}$ | $\mathbf{2.182}\pm\mathbf{2.081}$
Table 2: Quantitative analysis of real world dataset: We display mean and
standard deviation estimation errors.

##  5 Conclusion

We introduced a generalized approach to modeling stochastic processes and SDEs
via dynamic NFs and time change. By transforming the Wiener process through
time, we generate various Gaussian processes, which are then mapped to the
observed process via a bijection. The time change combined with the bijection
enabled us to model processes that are otherwise challenging to derive due to
calculus constraints. Importantly, this extension retains the advantages of
dynamic NFs, such as exact density estimation and efficient sampling.

Experiments showed that our model produces better performance and possesses a
generalization capacity, on both toy and real datasets. On the numerical side,
we identified that the training of the time-change function can produce
somewhat different solutions having, however, similar likelihood. Therefore,
further investigation must be carried out on regularization criteria and
inductive biases, in order to stabilize training.

## References

  * [1] Bernt Oksendal,  Stochastic differential equations: an introduction with applications,  Springer Science & Business Media, 2013.
  * [2] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio,  “Generative adversarial nets,”  Advances in neurips, vol. 27, 2014.
  * [3] Diederik P Kingma and Max Welling,  “Auto-encoding variational bayes,”  arXiv:1312.6114, 2013.
  * [4] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan,  “Normalizing Flows for Probabilistic Modeling and Inference,”  12 2019.
  * [5] Ivan Kobyzev, Simon J. D. Prince, and Marcus A. Brubaker,  “Normalizing Flows: An Introduction and Review of Current Methods,”  8 2019.
  * [6] Yang Song and Stefano Ermon,  “Generative modeling by estimating gradients of the data distribution,”  Advances in neural information processing systems, vol. 32, 2019.
  * [7] Jinsung Yoon, Daniel Jarrett, and Mihaela Van der Schaar,  “Time-series generative adversarial networks,”  Advances in neural information processing systems, vol. 32, 2019.
  * [8] Patrick Kidger, James Foster, Xuechen Li, and Terry J Lyons,  “Neural sdes as infinite-dimensional gans,”  in International conference on machine learning. PMLR, 2021, pp. 5453–5463.
  * [9] Xuechen Li, Ting-Kam Leonard Wong, Ricky TQ Chen, and David K Duvenaud,  “Scalable gradients and variational inference for stochastic differential equations,”  in Symposium on Advances in Approximate Bayesian Inference. PMLR, 2020, pp. 1–28.
  * [10] Sebastian Zeng, Florian Graf, and Roland Kwitt,  “Latent sdes on homogeneous spaces,”  arXiv preprint arXiv:2306.16248, 2023.
  * [11] Nazanin Mehrasa, Ruizhi Deng, Mohamed Osama Ahmed, Bo Chang, Jiawei He, Thibaut Durand, Marcus Brubaker, and Greg Mori,  “Point process flows,”  arXiv preprint arXiv:1910.08281, 2019.
  * [12] Oleksandr Shchur, Marin Biloš, and Stephan Günnemann,  “Intensity-free learning of temporal point processes,”  arXiv preprint arXiv:1909.12127, 2019.
  * [13] Will Grathwohl, Ricky T. Q. Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud,  “FFJORD: Free-form Continuous Dynamics for Scalable Reversible Generative Models,”  10 2018.
  * [14] Ruizhi Deng, Bo Chang, Marcus A Brubaker, Greg Mori, and Andreas Lehrmann,  “Modeling continuous stochastic processes with dynamic normalizing flows,”  Advances in Neural Information Processing Systems, vol. 33, pp. 7805–7815, 2020.
  * [15] Ruizhi Deng, Marcus A Brubaker, Greg Mori, and Andreas Lehrmann,  “Continuous latent process flows,”  Advances in Neural Information Processing Systems, vol. 34, pp. 5162–5173, 2021.
  * [16] Belinda Tzen and Maxim Raginsky,  “Neural stochastic differential equations: Deep latent gaussian models in the diffusion limit,”  arXiv preprint arXiv:1905.09883, 2019.
  * [17] Xuanqing Liu, Tesi Xiao, Si Si, Qin Cao, Sanjiv Kumar, and Cho-Jui Hsieh,  “Neural sde: Stabilizing neural ode networks with stochastic noise,”  arXiv:1906.02355, 2019.
  * [18] Daniel Revuz and Marc Yor,  Continuous martingales and Brownian motion, vol. 293,  Springer Science & Business Media, 2013.
  * [19] Shreyas Chaudhari, Srinivasa Pranav, and José MF Moura,  “Learning gradients of convex functions with monotone gradient networks,”  in ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023, pp. 1–5.
  * [20] Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang,  “Diffusion models: A comprehensive survey of methods and applications,”  arXiv preprint arXiv:2209.00796, 2022.
  * [21] Alessandro Ticchi, Andrew Scherer, Carla McIntyre, Carlos Stein N Brito, Derek Snow, Develra, dstern, James Colless, Kieran Garvey, Maggie, Maria Perez Ortiz, Ryan Lynch, and Sohier Dane,  “G-research crypto forecasting,” https://kaggle.com/competitions/g-research-crypto-forecasting, 2021,  Kaggle.
  * [22] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang,  “Informer: Beyond efficient transformer for long sequence time-series forecasting,”  in Proceedings of the AAAI conference on artificial intelligence, 2021, vol. 35, pp. 11106–11115.


# A Generalization of Brown’s Construction for the Degree/Diameter Problem

Yawara ISHIDA

###### Abstract

The degree/diameter problem is the problem of finding the largest possible
number of vertices $n_{\Delta,D}$ in a graph of given degree $\Delta$ and
diameter $D$. We consider the problem for the case of diameter $D=2$. William
G Brown gave a lower bound of the order of $(\Delta,2)$-graph. In this paper,
we give a generalization of his construction and improve the lower bounds for
the case of $\Delta=306$ and $\Delta=307$. One is $(306,2)$-graph with $88723$
vertices, the other is $(307,2)$-graph with $88724$ vertices.

##  1 Introduction

The degree/diameter problem is the problem of finding the largest possible
number $n_{\Delta,D}$ of vertices in a graph of given degree $\Delta$ and
diameter $D$ [3, 1]. Let $G$ be a graph with degree $\Delta$ ( $\Delta>2$ )
and diameter $D$, then we have

$|G|\leq n_{\Delta,D}\leq 1+\Delta\sum_{k=1}^{D-1}(\Delta-1)^{k}$

where $|G|$ is the number of vertices of $G$. The right hand side of the above
inequation is called Moore bound. On the other hand, a lower bound of
$n_{\Delta,D}$ for small degree and small diameter are available at
http://combinatoricswiki.org. Especially for case of $D=2$ and large degree,
there exists the general construction that gives a lower bound of
$n_{\Delta,2}$, which is called Brown’s construction [3]. Let $F_{q}$ be the
finite field, where $q$ is a power of a prime. Brown’s construction gives the
graph $\mathrm{B}(F_{q})$ whose vertices are lines in $F_{q}^{3}$ and two
lines are adjacent if and only if they are orthogonal. It follows that

$|\mathrm{B}(F_{q})|=q^{2}+q+1,\quad\Delta(\mathrm{B}(F_{q}))=q+1,\quad
D(\mathrm{B}(F_{q}))=2.$

The degree of each vertex of $\mathrm{B}(F_{q})$ is $q+1$ or $q$. Among
$q^{2}+q+1$ vertices, $q+1$ vertices are of degree $q$ and $q^{2}$ vertices
are of degree $q+1$. If $q$ is a power of $2$, there exists $(q+1,2)$-graph
with $q^{2}+q+2$ vertices [2].

In this paper, we generalize Brown’s construction by replacing a field with a
commutative ring, and search new records of the degree/diameter problem.

##  2 Generalized Brown’s Construction

We give some definitions for generalized Brown’s construction. A graph
$G=(V,E)$ consists of a set $V$ of vertices and a set $E\subset\\{(v,w)\in
V^{2}|v\neq w\\}$ of edges. If $(v,w)$ is in $E$, it is said that $v$ and $w$
are adjacent, which is denoted by $v\sim w$. The order $|G|$ of the graph is
the number of vertices. The neighbours $N(v)$ of the vertex $v$ is a set of
vertices which are adjacent to $v$. The degree $\delta(v)$ of the vertex $v$
is the number of neighbours $|N(v)|$. The degree $\Delta(G)$ of the graph $G$
is the maximum degree of vertices, namely $\Delta(G)=\max\\{\delta(v)|v\in
V\\}$. The distance of the pair $(v,w)$ of vertices is the shortest path
length between $v$ and $w$. The diameter $D(G)$ of the graph is the maximum
distance of all pairs of vertices.

Let $R$ be a commutative ring with unity. $R^{*}$ denotes the set of
invertible elements of $R$. $R^{3}$ is naturally seen as $R$-module. The
addition and $R$-action are defined by coordinate-wise. The inner product
$\cdot:R^{3}\times R^{3}\Rightarrow R$ is defined as follows:

$(v_{1},v_{2},v_{3})\cdot(w_{1},w_{2},w_{3})=v_{1}w_{1}+v_{2}w_{2}+v_{3}w_{3}.$

${\bm{v}}$ and ${\bm{w}}$ are orthogonal if and only if the inner product
vanishes, namely ${\bm{v}}\cdot{\bm{w}}=0$. The cross product
$\times:R^{3}\times R^{3}\Rightarrow R$ is defined as follows:

$(v_{1},v_{2},v_{3})\cdot(w_{1},w_{2},w_{3})=(v_{2}w_{3}-v_{3}w_{2},v_{3}w_{1}-v_{1}w_{3},v_{1}w_{2}-v_{2}w_{1}).$

######  Definition 1.

Let $R$ be a commutative ring with unity. The vertex set $V$ of the graph
$\mathrm{B}(R)$ is

$V=(R^{3}\setminus\\{\bm{v}|\exists r\in R,r\cdot{\bm{v}}={\bm{0}}\\})/\sim$

where $\bm{v}\sim\bm{w}$ if and only if there exists $k\in R^{*}$ such that
$k\cdot{\bm{v}}={\bm{w}}$. The two vertices $[\bm{v}]$ and $[\bm{w}]$ are
adjacent if and only if ${\bm{v}}\cdot{\bm{w}}=0$.

The definition of adjacency above is well-defined because the orthogonality
does not depend on the selection of representatives. We call the above
construction of a graph from a ring generalized Brown’s construction. It is
clear that the new construction coincides with Brown’s one when the ring $R$
is a field.

######  Lemma 1.

Let $E$ be a Euclidean domain and $u$ be a prime element in $E$. If
$E/(u^{k})$ is a finite ring, then the degree of each vertex of
$\mathrm{B}(E/(u^{k}))$ is $\Delta$ or $\Delta-1$, where $(u^{k})$ is the
principal ideal generated by $u^{k}$.

###### Proof.

It is clear that the degrees of vertices represented by
$(1,0,0),(0,1,0),(0,0,1)$ are the same. Let ${\bm{v}}=([a],[b],[c])$ be a
representative of any vertex where $a,b,c\in E$. If any element of
$[a],[b],[c]$ is not invertible in $E/(u^{k})$, there exist natural numbers
$1\leq l,m,n<k$ and some elements $a^{\prime},b^{\prime},c^{\prime}$ in $E$
such that $a=u^{l}a^{\prime},b=u^{m}b^{\prime},c=u^{n}c^{\prime}$. ${\bm{v}}$
is not a representative of vertices because the equation
$[u^{min(l,m,n)}]\cdot{\bm{v}}=([0],[0],[0])$ holds. This is a contradiction.
Therefore, at least one of $[a],[b],[c]$ is invertible. If $[a]$ is
invertible, there exists one-to-one correspondence
$\overline{U}:N([(1,0,0)])\rightarrow N([{\bm{v}}])$ such that for all
$[{\bm{w}}]\in N([1,0,0])$, $\overline{U}([\bm{w}])=[{}^{t}\\!U^{-1}{\bm{w}}]$
where $U$ is an invertible matrix defined as follows

$U=\left(\begin{matrix}[a]&0&0\\\ [b]&1&0\\\ [c]&0&1\end{matrix}\right)$

If ${\bm{v}}\cdot{\bm{v}}=0$, then $\delta([\bm{v}])=\delta([(1,0,0)]-1$. If
not so, $\delta([\bm{v}])=\delta([(1,0,0)])$. In the same way, if $[b]/[c]$ is
invertible, then $\delta([\bm{v}])$ is $\delta([(0,1,0)])/\delta([(0,0,1)])$
or $\delta([(1,0,0)]/\delta([(0,0,1)])-1$. Therefore, for all the vertex
$[{\bm{v}}]$,

$\delta([\bm{v}])=\left\\{\begin{array}[]{ll}\delta([(1,0,0)])&({\bm{v}}\cdot{\bm{v}}\neq
0)\\\ \delta([(1,0,0)])-1&(otherwise)\end{array}\right.$

∎

######  Lemma 2.

Let $E$ be a Euclidean domain and $I$ be an ideal of $E$. The diameter of
$\mathrm{B}(E/I)$ is 2.

###### Proof.

For any two distinct vertices represented by
$\bm{v}=([v_{1}],[v_{2}],[v_{3}])$ and $\bm{w}=([w_{1}],[w_{2}],[w_{3}])$,
consider the cross product $\bm{v}\times\bm{w}$. If
$\bm{v}\times\bm{w}=\bm{0}$, then $[v_{i}]\cdot\bm{w}=[w_{i}]\cdot\bm{v}$ for
$i=1,2,3$. There exists $e\in E$ such that $I=(e)$ because any Euclidean
domain is a principal ideal domain. If $\gcd(v_{1},v_{2},v_{3},e)$ is not a
unity, where $\gcd$ is a greatest common divisor, there exists $e^{\prime}\neq
1$ in $E$ such that $e=de^{\prime}$. $\bm{v}$ is not a representative because
$[e^{\prime}]\cdot\bm{v}=\bm{0}$. This is a contradiction. Therefore $d$ is a
unity, namely $v_{1}$ and $v_{2}$, $v_{3}$, $e$ are coprime. Then there exist
$a,b,c,d\in E$ such that $av_{1}+bv_{2}+cv_{3}+de=1$ in $E$. Seeing this
formula in $E/I$, we get $[a][v_{1}]+[b][v_{2}]+[c][v_{3}]=[1]$.

$\bm{v}=[1]\cdot\bm{v}=([a][v_{1}]+[b][v_{2}]+[c][v_{3}])\bm{v}=([a][w_{1}]+[b][w_{2}]+[c][w_{3}])\bm{w}$

means $[\bm{v}]=[\bm{w}]$, which is a contradiction to that two vertices are
distinct, then $\bm{v}\times\bm{w}\neq\bm{0}$. If $\bm{v}\times\bm{w}$ is a
representative of vertex, $[\bm{v}\times\bm{w}]$ is adjacent to $[\bm{v}]$ and
$[\bm{w}]$. If $\bm{v}\times\bm{w}=([k_{1}],[k_{2}],[k_{3}])$ is not a
representative of vertex,
$\bm{v}\times\bm{w}=[\gcd(k_{1},k_{2},k_{3})]\cdot\bm{u}$ and $\bm{u}$ is a
representative of vertex. $[\bm{u}]$ is adjacent to $[\bm{v}]$ and $[\bm{w}]$.
∎

######  Theorem.

The following equations hold.

  1. 1.

$|\mathrm{B}(\mathbb{Z}_{p^{k}})|=p^{2k}+p^{2k-1}+p^{2k-2}$

  2. 2.

$\Delta(\mathrm{B}(\mathbb{Z}_{p^{k}}))=p^{k}+p^{k-1}$

  3. 3.

$D(\mathbb{Z}_{p^{k}})=2$

###### Proof.

It is straightforward to show the formula of the order of
$\mathrm{B}(\mathbb{Z}_{p^{k}})$.

$\displaystyle|\mathrm{B}(\mathbb{Z}_{p^{k}})|$ $\displaystyle=$
$\displaystyle\frac{|\mathbb{Z}_{p^{k}}|^{3}-|\\{mp|0\leq
m<p^{k-1}\\}|^{3}}{|\mathbb{Z}_{p^{k}}|-|\\{mp|0\leq m<p^{k-1}\\}|}$
$\displaystyle=$
$\displaystyle\frac{(p^{k})^{3}-(p^{k-1})^{3}}{p^{k}-p^{k-1}}=p^{2k}+p^{2k-1}+p^{2k-2}$

Using Lemma 1, it is only enough to show that the degree of the vertex
represented by $(1,0,0)$ satisfy the formula of the degree of
$\mathrm{B}(\mathbb{Z}_{p^{k}})$.

$\displaystyle\Delta(\mathrm{B}(\mathbb{Z}_{p}^{k}))$ $\displaystyle=$
$\displaystyle\delta([(1,0,0)])=\frac{|\mathbb{Z}_{p^{k}}|^{2}-|\\{mp|0\leq
m<k\\}|^{2}}{|\mathbb{Z}_{p^{k}}|-|\\{mp|0\leq m<k\\}|}$ $\displaystyle=$
$\displaystyle\frac{(p^{k})^{2}-(p^{k-1})^{2}}{p^{k}-p^{k-1}}=p^{k}+p^{k-1}$

Using Lemma 2, we get $D(\mathrm{B}(\mathbb{Z}_{p}^{k}))=2$

∎

We search new records of the degree/diameter problem among graphs by
generalized Brown’s construction of $\mathbb{Z}_{n}$ where $2\leq n\leq
10000$. Using the above theorem, $\mathrm{B}(\mathbb{Z}_{17^{2}})$ has degree
$306$ and diameter $2$ and $88723$ vertices. It is a new record of $(306,2)$
of the degree/diameter problem because it cannot be obtained from ordinary
Brown’s construction. The power of a prime less than $305=306-1$ is $293^{1}$
and the graph $\mathrm{B}(\mathbb{Z}_{293})$ obtained from ordinary Brown’s
construction of $293^{1}$ has $294=293+1$ degree and $86143=293^{2}+293+1$
vertices. The old record of $306=294+12$ is $86156=86143+12$ obtained from
$\mathrm{B}(\mathbb{Z}_{293})$ by duplicating vertices. In the same way, the
graph obtained from $\mathrm{B}(\mathbb{Z}_{17^{2}})$ by duplicating any one
vertex, whose order is $88724$, is a new record of $(307,2)$ because the power
of a prime less than $306=307-1$ is $293^{1}$.

## Acknowledgements

We wish to thank Ryosuke Mizuno, Nobuhito Tamaki, Masahito Hasegawa,Shin-ya
Katsumata, and Sakie Suzuki.

## References

  * [1] William G Brown.  On graphs that do not contain a thomsen graph.  Canad. Math. Bull, 9(2):1–2, 1966.
  * [2] Paul Erdös, Siemion Fajtlowicz, and Alan J. Hoffman.  Maximum degree in graphs of diameter 2.  Networks, 10(1):87–90, 1980.
  * [3] M. Miller and J. Širáň.  Moore graphs and beyond: a survey of the degree/diameter problem.  The Electronic Journal of Combinatorics, (DS14), 2005.