David Richerby

David Richerby

Auto-generated profile, based on publicly available information

David Richerby

University of Essex, Colchester, United Kingdom

Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
Verified
Conference Paper
Open access
PDF file
MDMartin Dyer
Martin Dyer
LGLeslie Ann Goldberg
Leslie Ann Goldberg
MJMarkus Jalsenius
Markus Jalsenius
DRDavid Richerby
David Richerby
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations $\{0\}$ and $\{1\}$. When the maximum degree is at least $25$ we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of $\{0\}$, $\{1\}$ and binary implication. Otherwise, there is no FPRAS unless $\NPtime = \RPtime$. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.


9 December 2025 in Expert Systems
Verified
Journal Article
Open access
TBTill Blume
Till Blume
JRJannik Rau
Jannik Rau
DRDavid Richerby
David Richerby
ASAnsgar Scherp
Ansgar Scherp
Most graph summarization algorithms are tailored to a specific graph summary model and were designed for one‐time computations only, that is, batch‐based computations. We developed a universal approach for parallel graph summarization and three algorithms to compute graph summaries—a batch‐based algorithm for static graphs, an incremental algorithm for evolving graphs, and a hash‐based algorithm that scales to large graphs and large schema structures, that is, using paths of length up to to define vertex equivalence. Experimenting with benchmark and real‐world datasets, we observe that the incremental algorithm almost always runs faster than batch computation, even when 50% of the graph changes, and even when using fewer cores; however, it only uses 8% more memory (). Furthermore, we show that the hash‐based algorithm can compute 10‐hop equivalent subgraphs on graphs with over 10 M edges within seconds, on graphs of 100 + M edges within a few minutes, and on graphs of 1 + B edges in less than an hour. We analyse the complexity of our algorithms in detail and prove that the incremental algorithm is correct. Overall, we show with these three algorithms that our parallel approach for graph summarisation is versatile and opens the path for various applications that require summaries of large‐scale graphs.

14 March 2026 in Results in Engineering
Verified
Journal Article
Open access
BCBruno Ramos Cruz
Bruno Ramos Cruz
JAJavier Andreu-Perez
Javier Andreu-Perez
DRDavid Richerby
David Richerby
Luis MartinezLuis Martinez
Luis Martinez

8 December 2022 in arXiv
Verified
Preprint
Open access
PDF file
MBMaximilian Blasi
Maximilian Blasi
MFManuel Freudenreich
Manuel Freudenreich
JHJohannes Horvath
Johannes Horvath
DRDavid Richerby
David Richerby
ASAnsgar Scherp
Ansgar Scherp
The goal of graph summarization is to represent large graphs in a structured and compact way. A graph summary based on equivalence classes preserves pre-defined features of a graph's vertex within a $k$-hop neighborhood such as the vertex labels and edge labels. Based on these neighborhood characteristics, the vertex is assigned to an equivalence class. The calculation of the assigned equivalence class must be a permutation invariant operation on the pre-defined features. This is achieved by sorting on the feature values, e. g., the edge labels, which is computationally expensive, and subsequently hashing the result. Graph Neural Networks (GNN) fulfill the permutation invariance requirement. We formulate the problem of graph summarization as a subgraph classification task on the root vertex of the $k$-hop neighborhood. We adapt different GNN architectures, both based on the popular message-passing protocol and alternative approaches, to perform the structural graph summarization task. We compare different GNNs with a standard multi-layer perceptron (MLP) and Bloom filter as non-neural method. For our experiments, we consider four popular graph summary models on a large web graph. This resembles challenging multi-class vertex classification tasks with the numbers of classes ranging from $576$ to multiple hundreds of thousands. Our results show that the performance of GNNs are close to each other. In three out of four experiments, the non-message-passing GraphMLP model outperforms the other GNNs. The performance of the standard MLP is extraordinary good, especially in the presence of many classes. Finally, the Bloom filter outperforms all neural architectures by a large margin, except for the dataset with the fewest number of $576$ classes.

4 November 2022 in arXiv
Verified
Preprint
Open access
PDF file
TBTill Blume
Till Blume
JRJannik Rau
Jannik Rau
DRDavid Richerby
David Richerby
ASAnsgar Scherp
Ansgar Scherp
We developed a flexible parallel algorithm for graph summarization based on vertex-centric programming and parameterized message passing. The base algorithm supports infinitely many structural graph summary models defined in a formal language. An extension of the parallel base algorithm allows incremental graph summarization. In this paper, we prove that the incremental algorithm is correct and show that updates are performed in time $\mathcal{O}(\Delta \cdot d^k)$, where $\Delta$ is the number of additions, deletions, and modifications to the input graph, $d$ the maximum degree, and $k$ is the maximum distance in the subgraphs considered. Although the iterative algorithm supports values of $k>1$, it requires nested data structures for the message passing that are memory-inefficient. Thus, we extended the base summarization algorithm by a hash-based messaging mechanism to support a scalable iterative computation of graph summarizations based on $k$-bisimulation for arbitrary $k$. We empirically evaluate the performance of our algorithms using benchmark and real-world datasets. The incremental algorithm almost always outperforms the batch computation. We observe in our experiments that the incremental algorithm is faster even in cases when $50\%$ of the graph database changes from one version to the next. The incremental computation requires a three-layered hash index, which has a low memory overhead of only $8\%$ ($\pm 1\%$). Finally, the incremental summarization algorithm outperforms the batch algorithm even with fewer cores. The iterative parallel $k$-bisimulation algorithm computes summaries on graphs with over $10$M edges within seconds. We show that the algorithm processes graphs of $100+\,$M edges within a few minutes while having a moderate memory consumption of $<150$ GB. For the largest BSBM1B dataset with 1 billion edges, it computes $k=10$ bisimulation in under an hour.