CIRCA seminar: Peter Cameron and Richard Connor

Peter Cameron (School of Mathematics and Statistics) and Richard Connor (School of Computer Science) will speak at this CIRCA seminar, presenting on ‘When is the commuting graph split or threshold?' and ‘Similarity search by graph navigation: some high-dimensional problems' respectively.

Abstract for Peter's ‘When is the commuting graph split or threshold?': The commuting graph of a group (or semigroup) G has vertex set G, two vertices joined if they commute. It was introduced by Brauer and Fowler in 1955, in their seminal work on involution centralisers in simple groups. Split graphs and threshold graphs are two subgraph-closed graph families arising in operations research. A graph is split if the vertex set is the union of a complete graph and a null graph (with maybe some edges between); it is threshold if there are vertex weights and two vertices are joined if the sum of their weights exceeds a threshold.

Peter hopes to present the complete proof of the classification of groups whose commuting graph is split or threshold: they are either abelian, or generalised dihedral of twice odd order.

Abstract for Richard's ‘Similarity search by graph navigation: some high-dimensional problems': Similarity search is a simple concept: to (efficiently) find, from within a (very) large collection, those objects which are most similar to a query object presented from the same domain. Even approximate search becomes linear-time when the data is ‘high dimensional', and linear time is no use to us. Unfortunately, ‘high' means something like more than 20 Euclidean dimensions, and our main current interest is in searching embeddings, which are high-dimensional vectors arising from convolutional neural networks (such as GPT.) Language model embeddings have thousands of dimensions.

Some interesting recent systems have emerged which use novel graph navigation techniques. Simply, each element of the collection is represented as a graph node, and nodes are connected according to some relation. Search strategy is something like: start at a random node and navigate the graph, at each step moving closer to the query, which should thus be reached in a logarithmic number of steps. The current ‘state-of-the-art' is hnswlib (Hierarchical Navigable Small-World), which claims to work independently of dimensionality.

In this talk, Richard will examine the essential concepts presented by the authors, and some unfortunate properties of high-dimensional spaces which spoil the low-dimensional intuitions of graph navigation.

All welcome.