-
Powerful A/B-Testing Metrics and Where to Find Them
Authors:
Olivier Jeunen,
Shubham Baweja,
Neeti Pokharna,
Aleksei Ustimenko
Abstract:
Online controlled experiments, colloquially known as A/B-tests, are the bread and butter of real-world recommender system evaluation. Typically, end-users are randomly assigned some system variant, and a plethora of metrics are then tracked, collected, and aggregated throughout the experiment. A North Star metric (e.g. long-term growth or revenue) is used to assess which system variant should be d…
▽ More
Online controlled experiments, colloquially known as A/B-tests, are the bread and butter of real-world recommender system evaluation. Typically, end-users are randomly assigned some system variant, and a plethora of metrics are then tracked, collected, and aggregated throughout the experiment. A North Star metric (e.g. long-term growth or revenue) is used to assess which system variant should be deemed superior. As a result, most collected metrics are supporting in nature, and serve to either (i) provide an understanding of how the experiment impacts user experience, or (ii) allow for confident decision-making when the North Star metric moves insignificantly (i.e. a false negative or type-II error). The latter is not straightforward: suppose a treatment variant leads to fewer but longer sessions, with more views but fewer engagements; should this be considered a positive or negative outcome?
The question then becomes: how do we assess a supporting metric's utility when it comes to decision-making using A/B-testing? Online platforms typically run dozens of experiments at any given time. This provides a wealth of information about interventions and treatment effects that can be used to evaluate metrics' utility for online evaluation. We propose to collect this information and leverage it to quantify type-I, type-II, and type-III errors for the metrics of interest, alongside a distribution of measurements of their statistical power (e.g. $z$-scores and $p$-values). We present results and insights from building this pipeline at scale for two large-scale short-video platforms: ShareChat and Moj; leveraging hundreds of past experiments to find online metrics with high statistical power.
△ Less
Submitted 30 July, 2024;
originally announced July 2024.
-
$Δ\text{-}{\rm OPE}$: Off-Policy Estimation with Pairs of Policies
Authors:
Olivier Jeunen,
Aleksei Ustimenko
Abstract:
The off-policy paradigm casts recommendation as a counterfactual decision-making task, allowing practitioners to unbiasedly estimate online metrics using offline data. This leads to effective evaluation metrics, as well as learning procedures that directly optimise online success. Nevertheless, the high variance that comes with unbiasedness is typically the crux that complicates practical applicat…
▽ More
The off-policy paradigm casts recommendation as a counterfactual decision-making task, allowing practitioners to unbiasedly estimate online metrics using offline data. This leads to effective evaluation metrics, as well as learning procedures that directly optimise online success. Nevertheless, the high variance that comes with unbiasedness is typically the crux that complicates practical applications. An important insight is that the difference between policy values can often be estimated with significantly reduced variance, if said policies have positive covariance. This allows us to formulate a pairwise off-policy estimation task: $Δ\text{-}{\rm OPE}$.
$Δ\text{-}{\rm OPE}$ subsumes the common use-case of estimating improvements of a learnt policy over a production policy, using data collected by a stochastic logging policy. We introduce $Δ\text{-}{\rm OPE}$ methods based on the widely used Inverse Propensity Scoring estimator and its extensions. Moreover, we characterise a variance-optimal additive control variate that further enhances efficiency. Simulated, offline, and online experiments show that our methods significantly improve performance for both evaluation and learning tasks.
△ Less
Submitted 16 September, 2024; v1 submitted 16 May, 2024;
originally announced May 2024.
-
Multi-Objective Recommendation via Multivariate Policy Learning
Authors:
Olivier Jeunen,
Jatin Mandav,
Ivan Potapov,
Nakul Agarwal,
Sourabh Vaid,
Wenzhe Shi,
Aleksei Ustimenko
Abstract:
Real-world recommender systems often need to balance multiple objectives when deciding which recommendations to present to users. These include behavioural signals (e.g. clicks, shares, dwell time), as well as broader objectives (e.g. diversity, fairness). Scalarisation methods are commonly used to handle this balancing task, where a weighted average of per-objective reward signals determines the…
▽ More
Real-world recommender systems often need to balance multiple objectives when deciding which recommendations to present to users. These include behavioural signals (e.g. clicks, shares, dwell time), as well as broader objectives (e.g. diversity, fairness). Scalarisation methods are commonly used to handle this balancing task, where a weighted average of per-objective reward signals determines the final score used for ranking. Naturally, how these weights are computed exactly, is key to success for any online platform. We frame this as a decision-making task, where the scalarisation weights are actions taken to maximise an overall North Star reward (e.g. long-term user retention or growth). We extend existing policy learning methods to the continuous multivariate action domain, proposing to maximise a pessimistic lower bound on the North Star reward that the learnt policy will yield. Typical lower bounds based on normal approximations suffer from insufficient coverage, and we propose an efficient and effective policy-dependent correction for this. We provide guidance to design stochastic data collection policies, as well as highly sensitive reward signals. Empirical observations from simulations, offline and online experiments highlight the efficacy of our deployed approach.
△ Less
Submitted 16 September, 2024; v1 submitted 3 May, 2024;
originally announced May 2024.
-
Learning Metrics that Maximise Power for Accelerated A/B-Tests
Authors:
Olivier Jeunen,
Aleksei Ustimenko
Abstract:
Online controlled experiments are a crucial tool to allow for confident decision-making in technology companies. A North Star metric is defined (such as long-term revenue or user retention), and system variants that statistically significantly improve on this metric in an A/B-test can be considered superior. North Star metrics are typically delayed and insensitive. As a result, the cost of experim…
▽ More
Online controlled experiments are a crucial tool to allow for confident decision-making in technology companies. A North Star metric is defined (such as long-term revenue or user retention), and system variants that statistically significantly improve on this metric in an A/B-test can be considered superior. North Star metrics are typically delayed and insensitive. As a result, the cost of experimentation is high: experiments need to run for a long time, and even then, type-II errors (i.e. false negatives) are prevalent.
We propose to tackle this by learning metrics from short-term signals that directly maximise the statistical power they harness with respect to the North Star. We show that existing approaches are prone to overfitting, in that higher average metric sensitivity does not imply improved type-II errors, and propose to instead minimise the $p$-values a metric would have produced on a log of past experiments. We collect such datasets from two social media applications with over 160 million Monthly Active Users each, totalling over 153 A/B-pairs. Empirical results show that we are able to increase statistical power by up to 78% when using our learnt metrics stand-alone, and by up to 210% when used in tandem with the North Star. Alternatively, we can obtain constant statistical power at a sample size that is down to 12% of what the North Star requires, significantly reducing the cost of experimentation.
△ Less
Submitted 13 June, 2024; v1 submitted 6 February, 2024;
originally announced February 2024.
-
Variance Reduction in Ratio Metrics for Efficient Online Experiments
Authors:
Shubham Baweja,
Neeti Pokharna,
Aleksei Ustimenko,
Olivier Jeunen
Abstract:
Online controlled experiments, such as A/B-tests, are commonly used by modern tech companies to enable continuous system improvements. Despite their paramount importance, A/B-tests are expensive: by their very definition, a percentage of traffic is assigned an inferior system variant. To ensure statistical significance on top-level metrics, online experiments typically run for several weeks. Even…
▽ More
Online controlled experiments, such as A/B-tests, are commonly used by modern tech companies to enable continuous system improvements. Despite their paramount importance, A/B-tests are expensive: by their very definition, a percentage of traffic is assigned an inferior system variant. To ensure statistical significance on top-level metrics, online experiments typically run for several weeks. Even then, a considerable amount of experiments will lead to inconclusive results (i.e. false negatives, or type-II error). The main culprit for this inefficiency is the variance of the online metrics. Variance reduction techniques have been proposed in the literature, but their direct applicability to commonly used ratio metrics (e.g. click-through rate or user retention) is limited.
In this work, we successfully apply variance reduction techniques to ratio metrics on a large-scale short-video platform: ShareChat. Our empirical results show that we can either improve A/B-test confidence in 77% of cases, or can retain the same level of confidence with 30% fewer data points. Importantly, we show that the common approach of including as many covariates as possible in regression is counter-productive, highlighting that control variates based on Gradient-Boosted Decision Tree predictors are most effective. We discuss the practicalities of implementing these methods at scale and showcase the cost reduction they beget.
△ Less
Submitted 8 January, 2024;
originally announced January 2024.
-
Learning-to-Rank with Nested Feedback
Authors:
Hitesh Sagtani,
Olivier Jeunen,
Aleksei Ustimenko
Abstract:
Many platforms on the web present ranked lists of content to users, typically optimized for engagement-, satisfaction- or retention- driven metrics. Advances in the Learning-to-Rank (LTR) research literature have enabled rapid growth in this application area. Several popular interfaces now include nested lists, where users can enter a 2nd-level feed via any given 1st-level item. Naturally, this ha…
▽ More
Many platforms on the web present ranked lists of content to users, typically optimized for engagement-, satisfaction- or retention- driven metrics. Advances in the Learning-to-Rank (LTR) research literature have enabled rapid growth in this application area. Several popular interfaces now include nested lists, where users can enter a 2nd-level feed via any given 1st-level item. Naturally, this has implications for evaluation metrics, objective functions, and the ranking policies we wish to learn. We propose a theoretically grounded method to incorporate 2nd-level feedback into any 1st-level ranking model. Online experiments on a large-scale recommendation system confirm our theoretical findings.
△ Less
Submitted 8 January, 2024;
originally announced January 2024.
-
On Gradient Boosted Decision Trees and Neural Rankers: A Case-Study on Short-Video Recommendations at ShareChat
Authors:
Olivier Jeunen,
Hitesh Sagtani,
Himanshu Doi,
Rasul Karimov,
Neeti Pokharna,
Danish Kalim,
Aleksei Ustimenko,
Christopher Green,
Wenzhe Shi,
Rishabh Mehrotra
Abstract:
Practitioners who wish to build real-world applications that rely on ranking models, need to decide which modelling paradigm to follow. This is not an easy choice to make, as the research literature on this topic has been shifting in recent years. In particular, whilst Gradient Boosted Decision Trees (GBDTs) have reigned supreme for more than a decade, the flexibility of neural networks has allowe…
▽ More
Practitioners who wish to build real-world applications that rely on ranking models, need to decide which modelling paradigm to follow. This is not an easy choice to make, as the research literature on this topic has been shifting in recent years. In particular, whilst Gradient Boosted Decision Trees (GBDTs) have reigned supreme for more than a decade, the flexibility of neural networks has allowed them to catch up, and recent works report accuracy metrics that are on par. Nevertheless, practical systems require considerations beyond mere accuracy metrics to decide on a modelling approach.
This work describes our experiences in balancing some of the trade-offs that arise, presenting a case study on a short-video recommendation application. We highlight (1) neural networks' ability to handle large training data size, user- and item-embeddings allows for more accurate models than GBDTs in this setting, and (2) because GBDTs are less reliant on specialised hardware, they can provide an equally accurate model at a lower cost. We believe these findings are of relevance to researchers in both academia and industry, and hope they can inspire practitioners who need to make similar modelling choices in the future.
△ Less
Submitted 4 December, 2023;
originally announced December 2023.
-
Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting
Authors:
Aleksei Ustimenko,
Aleksandr Beznosikov
Abstract:
In this work, we consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Stochastic Differential Equation. The chain we study is a unified framework for theoretical analysis. It comes with almost arbitrary isotropic and state-dependent noise instead of normal and state-independent one as in most related papers. Moreover, in our chai…
▽ More
In this work, we consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Stochastic Differential Equation. The chain we study is a unified framework for theoretical analysis. It comes with almost arbitrary isotropic and state-dependent noise instead of normal and state-independent one as in most related papers. Moreover, in our chain the drift and diffusion coefficient can be inexact in order to cover wide range of applications as Stochastic Gradient Langevin Dynamics, sampling, Stochastic Gradient Descent or Stochastic Gradient Boosting. We prove the bound in $W_{2}$-distance between the laws of our Ito chain and corresponding differential equation. These results improve or cover most of the known estimates. And for some particular cases, our analysis is the first.
△ Less
Submitted 30 March, 2024; v1 submitted 9 October, 2023;
originally announced October 2023.
-
On (Normalised) Discounted Cumulative Gain as an Off-Policy Evaluation Metric for Top-$n$ Recommendation
Authors:
Olivier Jeunen,
Ivan Potapov,
Aleksei Ustimenko
Abstract:
Approaches to recommendation are typically evaluated in one of two ways: (1) via a (simulated) online experiment, often seen as the gold standard, or (2) via some offline evaluation procedure, where the goal is to approximate the outcome of an online experiment. Several offline evaluation metrics have been adopted in the literature, inspired by ranking metrics prevalent in the field of Information…
▽ More
Approaches to recommendation are typically evaluated in one of two ways: (1) via a (simulated) online experiment, often seen as the gold standard, or (2) via some offline evaluation procedure, where the goal is to approximate the outcome of an online experiment. Several offline evaluation metrics have been adopted in the literature, inspired by ranking metrics prevalent in the field of Information Retrieval. (Normalised) Discounted Cumulative Gain (nDCG) is one such metric that has seen widespread adoption in empirical studies, and higher (n)DCG values have been used to present new methods as the state-of-the-art in top-$n$ recommendation for many years.
Our work takes a critical look at this approach, and investigates when we can expect such metrics to approximate the gold standard outcome of an online experiment. We formally present the assumptions that are necessary to consider DCG an unbiased estimator of online reward and provide a derivation for this metric from first principles, highlighting where we deviate from its traditional uses in IR. Importantly, we show that normalising the metric renders it inconsistent, in that even when DCG is unbiased, ranking competing methods by their normalised DCG can invert their relative order. Through a correlation analysis between off- and on-line experiments conducted on a large-scale recommendation platform, we show that our unbiased DCG estimates strongly correlate with online reward, even when some of the metric's inherent assumptions are violated. This statement no longer holds for its normalised variant, suggesting that nDCG's practical utility may be limited.
△ Less
Submitted 12 June, 2024; v1 submitted 27 July, 2023;
originally announced July 2023.
-
Deep Stochastic Mechanics
Authors:
Elena Orlova,
Aleksei Ustimenko,
Ruoxi Jiang,
Peter Y. Lu,
Rebecca Willett
Abstract:
This paper introduces a novel deep-learning-based approach for numerical simulation of a time-evolving Schrödinger equation inspired by stochastic mechanics and generative diffusion models. Unlike existing approaches, which exhibit computational complexity that scales exponentially in the problem dimension, our method allows us to adapt to the latent low-dimensional structure of the wave function…
▽ More
This paper introduces a novel deep-learning-based approach for numerical simulation of a time-evolving Schrödinger equation inspired by stochastic mechanics and generative diffusion models. Unlike existing approaches, which exhibit computational complexity that scales exponentially in the problem dimension, our method allows us to adapt to the latent low-dimensional structure of the wave function by sampling from the Markovian diffusion. Depending on the latent dimension, our method may have far lower computational complexity in higher dimensions. Moreover, we propose novel equations for stochastic quantum mechanics, resulting in quadratic computational complexity with respect to the number of dimensions. Numerical simulations verify our theoretical findings and show a significant advantage of our method compared to other deep-learning-based approaches used for quantum mechanics.
△ Less
Submitted 7 July, 2024; v1 submitted 31 May, 2023;
originally announced May 2023.
-
Gradient Boosting Performs Gaussian Process Inference
Authors:
Aleksei Ustimenko,
Artem Beliakov,
Liudmila Prokhorenkova
Abstract:
This paper shows that gradient boosting based on symmetric decision trees can be equivalently reformulated as a kernel method that converges to the solution of a certain Kernel Ridge Regression problem. Thus, we obtain the convergence to a Gaussian Process' posterior mean, which, in turn, allows us to easily transform gradient boosting into a sampler from the posterior to provide better knowledge…
▽ More
This paper shows that gradient boosting based on symmetric decision trees can be equivalently reformulated as a kernel method that converges to the solution of a certain Kernel Ridge Regression problem. Thus, we obtain the convergence to a Gaussian Process' posterior mean, which, in turn, allows us to easily transform gradient boosting into a sampler from the posterior to provide better knowledge uncertainty estimates through Monte-Carlo estimation of the posterior variance. We show that the proposed sampler allows for better knowledge uncertainty estimates leading to improved out-of-domain detection.
△ Less
Submitted 13 March, 2023; v1 submitted 11 June, 2022;
originally announced June 2022.
-
Which Tricks Are Important for Learning to Rank?
Authors:
Ivan Lyzhin,
Aleksei Ustimenko,
Andrey Gulin,
Liudmila Prokhorenkova
Abstract:
Nowadays, state-of-the-art learning-to-rank methods are based on gradient-boosted decision trees (GBDT). The most well-known algorithm is LambdaMART which was proposed more than a decade ago. Recently, several other GBDT-based ranking algorithms were proposed. In this paper, we thoroughly analyze these methods in a unified setup. In particular, we address the following questions. Is direct optimiz…
▽ More
Nowadays, state-of-the-art learning-to-rank methods are based on gradient-boosted decision trees (GBDT). The most well-known algorithm is LambdaMART which was proposed more than a decade ago. Recently, several other GBDT-based ranking algorithms were proposed. In this paper, we thoroughly analyze these methods in a unified setup. In particular, we address the following questions. Is direct optimization of a smoothed ranking loss preferable over optimizing a convex surrogate? How to properly construct and smooth surrogate ranking losses? To address these questions, we compare LambdaMART with YetiRank and StochasticRank methods and their modifications. We also propose a simple improvement of the YetiRank approach that allows for optimizing specific ranking loss functions. As a result, we gain insights into learning-to-rank techniques and obtain a new state-of-the-art algorithm.
△ Less
Submitted 6 October, 2023; v1 submitted 4 April, 2022;
originally announced April 2022.
-
Multipole Born series approach to light scattering by Mie-resonant nanoparticle structures
Authors:
Nikita A. Ustimenko,
Danil F. Kornovan,
Kseniia V. Baryshnikova,
Andrey B. Evlyukhin,
Mihail I. Petrov
Abstract:
Exciting optical effects such as polarization control, imaging, and holography were demonstrated at the nanoscale using the complex and irregular structures of nanoparticles with the multipole Mie-resonances in the optical range. The optical response of such particles can be simulated either by full wave numerical simulations or by the widely used analytical coupled multipole method (CMM), however…
▽ More
Exciting optical effects such as polarization control, imaging, and holography were demonstrated at the nanoscale using the complex and irregular structures of nanoparticles with the multipole Mie-resonances in the optical range. The optical response of such particles can be simulated either by full wave numerical simulations or by the widely used analytical coupled multipole method (CMM), however, an analytical solution in the framework of CMM can be obtained only in a limited number of cases. In this paper, a modification of the CMM in the framework of the Born series and its applicability for simulation of light scattering by finite nanosphere structures, maintaining both dipole and quadrupole resonances, are investigated. The Born approximation simplifies an analytical consideration of various systems and helps shed light on physical processes ongoing in that systems. Using Mie theory and Green's functions approach, we analytically formulate the rigorous coupled dipole-quadrupole equations and their solution in the different-order Born approximations. We analyze in detail the resonant scattering by dielectric nanosphere structures such as dimer and ring to obtain the convergence conditions of the Born series and investigate how the physical characteristics such as absorption in particles, type of multipole resonance, and geometry of ensemble influence the convergence of Born series and its accuracy.
△ Less
Submitted 26 August, 2021;
originally announced August 2021.
-
Multipole optimization of light focusing by silicon nanosphere structures
Authors:
Nikita A. Ustimenko,
Kseniia V. Baryshnikova,
Roman V. Melnikov,
Danil F. Kornovan,
Vladimir I. Ulyantsev,
Boris N. Chichkov,
Andrey B. Evlyukhin
Abstract:
We investigate the applicability of the coupled multipole model and its modification in the framework of the zero-order Born approximation for modeling of light focusing by finite-size nanostructures of silicon nanospheres, supporting electric and magnetic dipole and quadrupole resonances. The results based on the analytical approximations are verified by comparison with the numerical simulations…
▽ More
We investigate the applicability of the coupled multipole model and its modification in the framework of the zero-order Born approximation for modeling of light focusing by finite-size nanostructures of silicon nanospheres, supporting electric and magnetic dipole and quadrupole resonances. The results based on the analytical approximations are verified by comparison with the numerical simulations performed by the T-matrix method. Using the evolutionary algorithm optimization, we apply the developed approach to design the silicon nanosphere metalenses with predefined focusing properties. The obtained results demonstrate a strong optimization potential of the suggested calculation scheme for engineering ultra-thin metalenses.
△ Less
Submitted 3 August, 2021; v1 submitted 2 March, 2021;
originally announced March 2021.
-
Uncertainty in Gradient Boosting via Ensembles
Authors:
Andrey Malinin,
Liudmila Prokhorenkova,
Aleksei Ustimenko
Abstract:
For many practical, high-risk applications, it is essential to quantify uncertainty in a model's predictions to avoid costly mistakes. While predictive uncertainty is widely studied for neural networks, the topic seems to be under-explored for models based on gradient boosting. However, gradient boosting often achieves state-of-the-art results on tabular data. This work examines a probabilistic en…
▽ More
For many practical, high-risk applications, it is essential to quantify uncertainty in a model's predictions to avoid costly mistakes. While predictive uncertainty is widely studied for neural networks, the topic seems to be under-explored for models based on gradient boosting. However, gradient boosting often achieves state-of-the-art results on tabular data. This work examines a probabilistic ensemble-based framework for deriving uncertainty estimates in the predictions of gradient boosting classification and regression models. We conducted experiments on a range of synthetic and real datasets and investigated the applicability of ensemble approaches to gradient boosting models that are themselves ensembles of decision trees. Our analysis shows that ensembles of gradient boosting models successfully detect anomalous inputs while having limited ability to improve the predicted total uncertainty. Importantly, we also propose a concept of a virtual ensemble to get the benefits of an ensemble via only one gradient boosting model, which significantly reduces complexity.
△ Less
Submitted 2 April, 2021; v1 submitted 18 June, 2020;
originally announced June 2020.
-
StochasticRank: Global Optimization of Scale-Free Discrete Functions
Authors:
Aleksei Ustimenko,
Liudmila Prokhorenkova
Abstract:
In this paper, we introduce a powerful and efficient framework for direct optimization of ranking metrics. The problem is ill-posed due to the discrete structure of the loss, and to deal with that, we introduce two important techniques: stochastic smoothing and novel gradient estimate based on partial integration. We show that classic smoothing approaches may introduce bias and present a universal…
▽ More
In this paper, we introduce a powerful and efficient framework for direct optimization of ranking metrics. The problem is ill-posed due to the discrete structure of the loss, and to deal with that, we introduce two important techniques: stochastic smoothing and novel gradient estimate based on partial integration. We show that classic smoothing approaches may introduce bias and present a universal solution for a proper debiasing. Importantly, we can guarantee global convergence of our method by adopting a recently proposed Stochastic Gradient Langevin Boosting algorithm. Our algorithm is implemented as a part of the CatBoost gradient boosting library and outperforms the existing approaches on several learning-to-rank datasets. In addition to ranking metrics, our framework applies to any scale-free discrete loss function.
△ Less
Submitted 20 August, 2020; v1 submitted 4 March, 2020;
originally announced March 2020.
-
SGLB: Stochastic Gradient Langevin Boosting
Authors:
Aleksei Ustimenko,
Liudmila Prokhorenkova
Abstract:
This paper introduces Stochastic Gradient Langevin Boosting (SGLB) - a powerful and efficient machine learning framework that may deal with a wide range of loss functions and has provable generalization guarantees. The method is based on a special form of the Langevin diffusion equation specifically designed for gradient boosting. This allows us to theoretically guarantee the global convergence ev…
▽ More
This paper introduces Stochastic Gradient Langevin Boosting (SGLB) - a powerful and efficient machine learning framework that may deal with a wide range of loss functions and has provable generalization guarantees. The method is based on a special form of the Langevin diffusion equation specifically designed for gradient boosting. This allows us to theoretically guarantee the global convergence even for multimodal loss functions, while standard gradient boosting algorithms can guarantee only local optimum. We also empirically show that SGLB outperforms classic gradient boosting when applied to classification tasks with 0-1 loss function, which is known to be multimodal.
△ Less
Submitted 16 January, 2022; v1 submitted 20 January, 2020;
originally announced January 2020.
-
A new series of dense graphs of high girth
Authors:
Felix Lazebnik,
Vasiliy A. Ustimenko,
Andrew J. Woldar
Abstract:
Let $k\ge 1$ be an odd integer, $t=\lfloor {{k+2}\over 4}\rfloor$, and $q$ be a prime power. We construct a bipartite, $q$-regular, edge-transitive graph $C\!D(k,q)$ of order $v \le 2q^{k-t+1}$ and girth $g \ge k+5$. If $e$ is the the number of edges of $C\!D(k,q)$, then $e =Ω(v^{1+ {1\over {k-t+1}}})$. These graphs provide the best known asymptotic lower bound for the greatest number of edges i…
▽ More
Let $k\ge 1$ be an odd integer, $t=\lfloor {{k+2}\over 4}\rfloor$, and $q$ be a prime power. We construct a bipartite, $q$-regular, edge-transitive graph $C\!D(k,q)$ of order $v \le 2q^{k-t+1}$ and girth $g \ge k+5$. If $e$ is the the number of edges of $C\!D(k,q)$, then $e =Ω(v^{1+ {1\over {k-t+1}}})$. These graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of order $v$ and girth at least $g$, $ g\ge 5$, $g \not= 11,12$. For $g\ge 24$, this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for $5\le g\le 23$, $g\not= 11,12$, it improves on or ties existing bounds.
△ Less
Submitted 31 December, 1994;
originally announced January 1995.