Author name cluster

Andrew Davison

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

NeurIPS Conference 2024 Conference Paper

Community Detection Guarantees using Embeddings Learned by Node2Vec

Andrew Davison
S. Carlyle Morgan
Owen G. Ward

Embedding the nodes of a large network into an Euclidean space is a common objective in modernmachine learning, with a variety of tools available. These embeddings can then be used as features fortasks such as community detection/node clustering or link prediction, where they achieve state of the artperformance. With the exception of spectral clustering methods, there is little theoretical understandingfor commonly used approaches to learning embeddings. In this work we examine the theoreticalproperties of the embeddings learned by node2vec. Our main result shows that the use of k-meansclustering on the embedding vectors produced by node2vec gives weakly consistent community recoveryfor the nodes in (degree corrected) stochastic block models. We also discuss the use of these embeddingsfor node and link prediction tasks. We demonstrate this result empirically for bothreal and simulated networks, and examine how this relatesto other embedding tools for network data.

PDF Details DOI

JMLR Journal 2023 Journal Article

Asymptotics of Network Embeddings Learned via Subsampling

Andrew Davison
Morgane Austern

Network data are ubiquitous in modern machine learning, with tasks of interest including node classification, node clustering and link prediction. A frequent approach begins by learning an Euclidean embedding of the network, to which algorithms developed for vector-valued data are applied. For large networks, embeddings are learned using stochastic gradient methods where the sub-sampling scheme can be freely chosen. Despite the strong empirical performance of such methods, they are not well understood theoretically. Our work encapsulates representation methods using a subsampling approach, such as node2vec, into a single unifying framework. We prove, under the assumption that the graph is exchangeable, that the distribution of the learned embedding vectors asymptotically decouples. Moreover, we characterize the asymptotic distribution and provided rates of convergence, in terms of the latent parameters, which includes the choice of loss function and the embedding dimension. This provides a theoretical foundation to understand what the embedding vectors represent and how well these methods perform on downstream tasks. Notably, we observe that typically used loss functions may lead to shortcomings, such as a lack of Fisher consistency. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

PDF Details

NeurIPS Conference 2022 Conference Paper

Asymptotics of $\ell_2$ Regularized Network Embeddings

Andrew Davison

A common approach to solving prediction tasks on large networks, such as node classification or link prediction, begin by learning a Euclidean embedding of the nodes of the network, from which traditional machine learning methods can then be applied. This includes methods such as DeepWalk and node2vec, which learn embeddings by optimizing stochastic losses formed over subsamples of the graph at each iteration of stochastic gradient descent. In this paper, we study the effects of adding an $\ell_2$ penalty of the embedding vectors to the training loss of these types of methods. We prove that, under some exchangeability assumptions on the graph, this asymptotically leads to learning a graphon with a nuclear-norm-type penalty, and give guarantees for the asymptotic distribution of the learned embedding vectors. In particular, the exact form of the penalty depends on the choice of subsampling method used as part of stochastic gradient descent. We also illustrate empirically that concatenating node covariates to $\ell_2$ regularized node2vec embeddings leads to comparable, when not superior, performance to methods which incorporate node covariates and the network structure in a non-linear manner. .

PDF Details

TMLR Journal 2022 Journal Article

Auto-Lambda: Disentangling Dynamic Task Relationships

Shikun Liu
Stephen James
Andrew Davison
Edward Johns

Understanding the structure of multiple related tasks allows for multi-task learning to improve the generalisation ability of one or all of them. However, it usually requires training each pairwise combination of tasks together in order to capture task relationships, at an extremely high computational cost. In this work, we learn task relationships via an automated weighting framework, named Auto-Lambda. Unlike previous methods where task relationships are assumed to be fixed, i.e., task should either be trained together or not trained together, Auto-Lambda explores continuous, dynamic task relationships via task-specific weightings, and can optimise any choice of combination of tasks through the formulation of a meta-loss; where the validation loss automatically influences task weightings throughout training. We apply the proposed framework to both multi-task and auxiliary learning problems in computer vision and robotics, and show that AutoLambda achieves state-of-the-art performance, even when compared to optimisation strategies designed specifically for each problem and data domain. Finally, we observe that Auto-Lambda can discover interesting learning behaviors, leading to new insights in multi-task learning. Code is available at https://github.com/lorenmt/auto-lambda.

PDF Details

NeurIPS Conference 2019 Conference Paper

Self-Supervised Generalisation with Meta Auxiliary Learning

Shikun Liu
Andrew Davison
Edward Johns

Learning with auxiliary tasks can improve the ability of a primary task to generalise. However, this comes at the cost of manually labelling auxiliary data. We propose a new method which automatically learns appropriate labels for an auxiliary task, such that any supervised learning task can be improved without requiring access to any further data. The approach is to train two neural networks: a label-generation network to predict the auxiliary labels, and a multi-task network to train the primary task alongside the auxiliary task. The loss for the label-generation network incorporates the loss of the multi-task network, and so this interaction between the two networks can be seen as a form of meta learning with a double gradient. We show that our proposed method, Meta AuXiliary Learning (MAXL), outperforms single-task learning on 7 image datasets, without requiring any additional data. We also show that MAXL outperforms several other baselines for generating auxiliary labels, and is even competitive when compared with human-defined auxiliary labels. The self-supervised nature of our method leads to a promising new direction towards automated generalisation. Source code can be found at \url{https: //github. com/lorenmt/maxl}.

PDF Details

LPAR Conference 1993 Conference Paper

Parsing with DCG-terms

Andrew Davison

Abstract Definite Clause Grammars (DCGs) are powerful adjuncts to Prolog, permitting the clear and succinct encoding of parsers and other grammar related programs. Normally, a DCG is incorporated into a Prolog program by being treated as a special set of predicates. This paper utilises DCGs in a different way, by augmenting the unification algorithm with DCG-terms. More importantly, this notation allows token lists to be constructed and deconstructed by reference to nonterminal names. Examples in the parsing domain are used to illustrate these ideas, and show how programs are improved. In particular, searches for sublists of tokens of different types can be expressed simply, without having to complicate the underlying DCG. Also, the DCG part of a program is more independent of the other code, which makes both easier to debug and modify.

Details