Showing 1–50 of 55 results for author: Fletcher, G

Between Suppression and Collapse: Evaluating Narrative Unlearning with LENS

Authors: Viktoriia Makovska, George Fletcher

Abstract: Large language models (LLMs) can reproduce disinformation-aligned narrative frames as plausible explanations, raising the question of whether existing machine-unlearning algorithms can suppress this behavior. We introduce Level-based Evaluation of Narrative Suppression (LENS), a contextualization based evaluation protocol for testing target narrative reproduction across direct, attributed, contras… ▽ More Large language models (LLMs) can reproduce disinformation-aligned narrative frames as plausible explanations, raising the question of whether existing machine-unlearning algorithms can suppress this behavior. We introduce Level-based Evaluation of Narrative Suppression (LENS), a contextualization based evaluation protocol for testing target narrative reproduction across direct, attributed, contrastive, and abstract resistance levels. We evaluate two source-grounded narratives: one framing Russia's war against Ukraine as forced by NATO expansion, and one framing the United States as exploiting or abandoning Taiwan. The experiments cover four near-12B multilingual instruction models: Lapa LLM, Gemma-12B, Qwen-14B, and TAIDE-Gemma. We introduce the Suppression-Collapse Efficiency (SCE) score as a checkpoint selection summary that rewards target-narrative suppression while penalizing degraded outputs. Our results shows that selected checkpoints can reduce narrative reproduction and suppression may transfer beyond direct forget prompts. We also report entity recovery as a separate side effect: abstract A/B/C prompts can cause models to recover the real-world actors associated with the target frame after unlearning. These findings demonstrate that LENS is a successful diagnostic protocol for both reporting and guiding the further study of the deeper structure of narrative unlearning. △ Less

Submitted 31 July, 2026; v1 submitted 27 June, 2026; originally announced July 2026.

GraphAlg Playground: An Online Platform for Learning and Experimenting with the GraphAlg Language

Authors: Daan de Graaf, Robert Brijder, Soham Chakraborty, George Fletcher, Bram van de Wall, Nikolay Yakovets

Abstract: The GraphAlg language for graph algorithms enables native support for user-defined graph analytics workloads in databases. In this demonstration, we present a web-based playground for writing and executing GraphAlg programs in the web browser, including an interactive tutorial explaining its key concepts. The playground runs inside the user's web browser without any installation, and is freely ava… ▽ More The GraphAlg language for graph algorithms enables native support for user-defined graph analytics workloads in databases. In this demonstration, we present a web-based playground for writing and executing GraphAlg programs in the web browser, including an interactive tutorial explaining its key concepts. The playground runs inside the user's web browser without any installation, and is freely available under a permissive license as a reusable library. We present two demonstration scenarios of the publicly available playground website, showing how new users can learn to program in GraphAlg using the tutorial, while expert users can use the playground to prototype and validate their algorithms. △ Less

Submitted 3 June, 2026; originally announced June 2026.

Comments: Accepted at the VLDB 2026 Demonstration Track; to appear in PVLDB Vol. 19. 4 pages, 8 figures, 1 table. Artifacts: https://wildarch.dev/graphalg

Pathways to AGI

Authors: Gordon Fletcher, Saomai Vu Khan

Abstract: Our focus are five related questions that stem from a critical software studies perspective. Underpinning this view is the acknowledged need to avoid assumptions regarding the inevitability of the current situation relating to AI. What we need to see is the closeness of the linkage between current commercial AI development and our prevailing social, political and economic circumstances. This does… ▽ More Our focus are five related questions that stem from a critical software studies perspective. Underpinning this view is the acknowledged need to avoid assumptions regarding the inevitability of the current situation relating to AI. What we need to see is the closeness of the linkage between current commercial AI development and our prevailing social, political and economic circumstances. This does mean that the perspectives presented here are done so critically and conditionally. Most importantly, Artificial General Intelligence (AGI) is seen as being problematic both conceptually and definitionally. This conditioning of any view regarding AGI does lead the discussion in specific directions and to certain conclusions regarding the future. However, adopting this perspective enables the work to offer some final recommendations. We set out to ask the following questions, 1. What are the critical pathways that produced the current dominant generative AI tools (capabilities, product forms, adoption patterns)? 2. Which decision points acted as leverage nodes (small changes that had large downstream effects), and which dead ends reveal alternative possibilities that did not become dominant? 3. How do pathways differ across three foundational-model trajectories such as the frontier proprietary models, open-weight models or specific domain and sovereign models? 4. Which alternative projects branched from key leverage nodes, what is their current state, and why did some succeed, stall, fail or become absorbed? 5. Based on this analysis, what socio-technical development programmes could plausibly move toward AGI-adjacent capability while meeting requirements for transparency, moderation, wellbeing and sustainable business models? △ Less

Submitted 7 May, 2026; originally announced May 2026.

Comments: Additional data at 10.17866/rd.salford.32201874

Systemic Gendered Citation Imbalance in Computer Science: Evidence from Conferences and Journals

Authors: Kazuki Nakajima, Yuya Sasaki, Sohei Tokuno, George Fletcher

Abstract: Gender imbalance persists across science, technology, engineering, and mathematics (STEM) fields, including computer science, where it appears in researcher demographics, productivity, recognition, hiring, and career progression. Given computer science's rapid expansion and global influence, addressing this imbalance is essential for broadening participation and fueling innovation. Although journa… ▽ More Gender imbalance persists across science, technology, engineering, and mathematics (STEM) fields, including computer science, where it appears in researcher demographics, productivity, recognition, hiring, and career progression. Given computer science's rapid expansion and global influence, addressing this imbalance is essential for broadening participation and fueling innovation. Although journal-oriented disciplines exhibit consistent gender imbalances in citation practices, it remains unclear whether similar patterns arise in the conference-centric culture of computer science. Here, we systematically investigate gender imbalance in citations of conference and journal papers in computer science. We find that papers for which a woman is listed as either first or last author receive fewer citations than expected, partly because of homophilic citation tendencies (i.e., authors tend to cite papers that share specific attributes). This imbalance is especially pronounced for conference papers--particularly those published at top-tier venues--relative to journals. Moreover, we find that the prominence of the first or last author and the structure of their local co-authorship networks are potential drivers of these imbalances. By exploring how conference-centric publishing practices can amplify systemic imbalances in computer science, our study offers insights that may inform efforts to foster more equitable representation in academia. △ Less

Submitted 24 March, 2026; originally announced March 2026.

Comments: Accepted for publication in Scientometrics. 31 pages, 7 figures, 3 tables. Includes Supplementary Information

Seeing the Trees for the Forest: Leveraging Tree-Shaped Substructures in Property Graphs

Authors: Daniel Aarao Reis Arturi, Christoph Köhnen, George Fletcher, Bettina Kemme, Stefanie Scherzinger

Abstract: Property graphs often contain tree-shaped substructures, yet they are not captured by existing proposals for graph schemas; likewise, query languages and query engines offer little-to-no native support for managing them systematically. As a first contribution, we report on a micro experiment that demonstrates the optimization potential of treating tree-shaped substructures as first class citizens… ▽ More Property graphs often contain tree-shaped substructures, yet they are not captured by existing proposals for graph schemas; likewise, query languages and query engines offer little-to-no native support for managing them systematically. As a first contribution, we report on a micro experiment that demonstrates the optimization potential of treating tree-shaped substructures as first class citizens in graph database systems. In particular, we show that in systems backed by relational engines, we can achieve substantial speedups by leveraging structural indexes, as originally developed for XML databases, to accelerate path queries. Based on our findings, we put forward a vision in which tree-shaped substructures are systematically managed throughout the graph query lifecycle, from modeling and schema design to indexing and query processing, and outline arising research questions. △ Less

Submitted 12 March, 2026; originally announced March 2026.

Serendipity with Generative AI: Repurposing knowledge components during polycrisis with a Viable Systems Model approach

Authors: Gordon Fletcher, Saomai Vu Khan

Abstract: Organisations face polycrisis uncertainty yet overlook embedded knowledge. We show how generative AI can operate as a serendipity engine and knowledge transducer to discover, classify and mobilise reusable components (models, frameworks, patterns) from existing documents. Using 206 papers, our pipeline extracted 711 components (approx 3.4 per paper) and organised them into a repository aligned to… ▽ More Organisations face polycrisis uncertainty yet overlook embedded knowledge. We show how generative AI can operate as a serendipity engine and knowledge transducer to discover, classify and mobilise reusable components (models, frameworks, patterns) from existing documents. Using 206 papers, our pipeline extracted 711 components (approx 3.4 per paper) and organised them into a repository aligned to Beer's Viable System Model (VSM). We contribute i) conceptually, a theory of planned serendipity in which GenAI lowers transduction costs between VSM subsystems, ii) empirically, a component repository and temporal/subject patterns, iii) managerially, a vignette and process blueprint for organisational adoption and iv) socially, pathways linking repurposing to environmental and social benefits. We propose testable links between repository creation, discovery-to-deployment time, and reuse rates, and discuss implications for shifting innovation portfolios from breakthrough bias toward systematic repurposing. △ Less

Submitted 1 December, 2025; originally announced February 2026.

Memory Undone: Between Knowing and Not Knowing in Data Systems

Authors: Viktoriia Makovska, George Fletcher, Julia Stoyanovich, Tetiana Zakharchenko

Abstract: Machine learning and data systems increasingly function as infrastructures of memory: they ingest, store, and operationalize traces of personal, political, and cultural life. Yet contemporary governance demands credible forms of forgetting, from GDPR-backed deletion to harm-mitigation and the removal of manipulative content, while technical infrastructures are optimized to retain, replicate, and r… ▽ More Machine learning and data systems increasingly function as infrastructures of memory: they ingest, store, and operationalize traces of personal, political, and cultural life. Yet contemporary governance demands credible forms of forgetting, from GDPR-backed deletion to harm-mitigation and the removal of manipulative content, while technical infrastructures are optimized to retain, replicate, and reuse. This work argues that "forgetting" in computational systems cannot be reduced to a single operation (e.g., record deletion) and should instead be treated as a sociotechnical practice with distinct mechanisms and consequences. We clarify a vocabulary that separates erasure (removing or disabling access to data artifacts), unlearning (interventions that bound or remove a data point influence on learned parameters and outputs), exclusion (upstream non-collection and omission), and forgetting as an umbrella term spanning agency, temporality, reversibility, and scale. Building on examples from machine unlearning, semantic dependencies in data management, participatory data modeling, and manipulation at scale, we show how forgetting can simultaneously protect rights and enable silencing. We propose reframing unlearning as a first-class capability in knowledge infrastructures, evaluated not only by compliance or utility retention, but by its governance properties: transparency, accountability, and epistemic justice. △ Less

Submitted 24 February, 2026; originally announced February 2026.

Comments: Undone Computer Science 2026

Seasoning Data Modeling Education with GARLIC: A Participatory Co-Design Framework

Authors: Viktoriia Makovska, Ihor Michurin, Mariia Tokhtamysh, George Fletcher, Julia Stoyanovich

Abstract: Entity-Relationship (ER) modeling is commonly taught as a primarily technical activity, despite its central role in shaping how data systems represent people, processes, and institutions. Prior research in participatory design demonstrates that involving diverse stakeholders in modeling can surface tacit knowledge, challenge implicit assumptions, and produce more inclusive data representations. Ho… ▽ More Entity-Relationship (ER) modeling is commonly taught as a primarily technical activity, despite its central role in shaping how data systems represent people, processes, and institutions. Prior research in participatory design demonstrates that involving diverse stakeholders in modeling can surface tacit knowledge, challenge implicit assumptions, and produce more inclusive data representations. However, database education currently lacks structured pedagogical approaches for teaching participatory ER modeling in practice. We introduce the GARLIC methodology for teaching and learning participatory ER modeling. GARLIC adapts and extends the ONION participatory ER modeling framework of Makovska et al.(HILDA 2025) into a workshop-based learning format that combines role-playing, collaborative synthesis, guided critique, and iterative refinement. GARLIC is designed to develop both technical modeling skills and critical awareness of the social and ethical dimensions of data representation. GARLIC lowers the barrier to participatory ER modeling and equips students with practical skills for collaborative, inclusive data model design. △ Less

Submitted 20 February, 2026; originally announced February 2026.

Comments: DataEd'26: 5th International Workshop on Data Systems Education

Algorithm Support for Graph Databases, Done Right

Authors: Daan de Graaf, Robert Brijder, Soham Chakraborty, George Fletcher, Bram van de Wall, Nikolay Yakovets

Abstract: Graph database query languages cannot express algorithms like PageRank, forcing costly data wrangling, while existing solutions such as algorithm libraries, vertex-centric APIs, and recursive CTEs lack the necessary combination of expressiveness, performance, and usability. We present GraphAlg: a domain-specific language for graph algorithms that compiles to relational algebra, enabling seamless i… ▽ More Graph database query languages cannot express algorithms like PageRank, forcing costly data wrangling, while existing solutions such as algorithm libraries, vertex-centric APIs, and recursive CTEs lack the necessary combination of expressiveness, performance, and usability. We present GraphAlg: a domain-specific language for graph algorithms that compiles to relational algebra, enabling seamless integration with query processing pipelines. Built on linear algebra foundations, GraphAlg provides intuitive matrix operations that are amenable to aggressive optimization including sparsity analysis, loop-invariant code motion, and in-place aggregation. Our implementation in AvantGraph demonstrates significant code complexity reduction compared to SQL/Python and Pregel while achieving excellent performance on LDBC Graphalytics benchmarks. GraphAlg establishes that graph databases can serve as unified platforms for both queries and analytics. △ Less

Submitted 10 January, 2026; originally announced January 2026.

Comments: for GraphAlg compiler source code, see https://github.com/wildarch/graphalg

Reducing research bureaucracy in UK higher education: Can generative AI assist with the internal evaluation of quality?

Authors: Gordon Fletcher, Saomai Vu Khan, Aldus Greenhill Fletcher

Abstract: This paper examines the potential for generative artificial intelligence (GenAI) to assist with internal review processes for research quality evaluations in UK higher education and particularly in preparation for the Research Excellence Framework (REF). Using the lens of function substitution in the Viable Systems Model, we present an experimental methodology using ChatGPT to score and rank busin… ▽ More This paper examines the potential for generative artificial intelligence (GenAI) to assist with internal review processes for research quality evaluations in UK higher education and particularly in preparation for the Research Excellence Framework (REF). Using the lens of function substitution in the Viable Systems Model, we present an experimental methodology using ChatGPT to score and rank business and management papers from REF 2021 submissions, "reverse engineering" the assessment by comparing AI-generated scores with known institutional results. Through rigourous testing of 822 papers across 11 institutions, we established scoring boundaries that aligned with reported REF outcomes: 49% between 1* and 2*, 59% between 2* and 3*, and 69% between 3* and 4*. The results demonstrate that AI can provide consistent evaluations that help identify borderline evaluation cases requiring additional human scrutiny while reducing the substantial resource burden of traditional internal review processes. We argue for application through a nuanced hybrid approach that maintains academic integrity while addressing the multi-million pound costs associated with research evaluation bureaucracy. While acknowledging these limitations including potential AI biases, the research presents a promising framework for more efficient, consistent evaluations that could transform current approaches to research assessment. △ Less

Submitted 26 November, 2025; originally announced November 2025.

Identity Management for Agentic AI: The new frontier of authorization, authentication, and security for an AI agent world

Authors: Tobin South, Subramanya Nagabhushanaradhya, Ayesha Dissanayaka, Sarah Cecchetti, George Fletcher, Victor Lu, Aldo Pietropaolo, Dean H. Saxe, Jeff Lombardo, Abhishek Maligehalli Shivalingaiah, Stan Bounev, Alex Keisner, Andor Kesselman, Zack Proser, Ginny Fahs, Andrew Bunyea, Ben Moskowitz, Atul Tulshibagwale, Dazza Greenwood, Jiaxin Pei, Alex Pentland

Abstract: The rapid rise of AI agents presents urgent challenges in authentication, authorization, and identity management. Current agent-centric protocols (like MCP) highlight the demand for clarified best practices in authentication and authorization. Looking ahead, ambitions for highly autonomous agents raise complex long-term questions regarding scalable access control, agent-centric identities, AI work… ▽ More The rapid rise of AI agents presents urgent challenges in authentication, authorization, and identity management. Current agent-centric protocols (like MCP) highlight the demand for clarified best practices in authentication and authorization. Looking ahead, ambitions for highly autonomous agents raise complex long-term questions regarding scalable access control, agent-centric identities, AI workload differentiation, and delegated authority. This OpenID Foundation whitepaper is for stakeholders at the intersection of AI agents and access management. It outlines the resources already available for securing today's agents and presents a strategic agenda to address the foundational authentication, authorization, and identity problems pivotal for tomorrow's widespread autonomous systems. △ Less

Submitted 29 October, 2025; originally announced October 2025.

MSC Class: 68M12 ACM Class: D.4.6; K.6.5; I.2.11

Journal ref: OpenID Foundation Whitepaper, 2025

ONION: A Multi-Layered Framework for Participatory ER Design

Authors: Viktoriia Makovska, George Fletcher, Julia Stoyanovich

Abstract: We present ONION, a multi-layered framework for participatory Entity-Relationship (ER) modeling that integrates insights from design justice, participatory AI, and conceptual modeling. ONION introduces a five-stage methodology: Observe, Nurture, Integrate, Optimize, Normalize. It supports progressive abstraction from unstructured stakeholder input to structured ER diagrams. Our approach aims to… ▽ More We present ONION, a multi-layered framework for participatory Entity-Relationship (ER) modeling that integrates insights from design justice, participatory AI, and conceptual modeling. ONION introduces a five-stage methodology: Observe, Nurture, Integrate, Optimize, Normalize. It supports progressive abstraction from unstructured stakeholder input to structured ER diagrams. Our approach aims to reduce designer bias, promote inclusive participation, and increase transparency through the modeling process. We evaluate ONION through real-world workshops focused on sociotechnical systems in Ukraine, highlighting how diverse stakeholder engagement leads to richer data models and deeper mutual understanding. Early results demonstrate ONION's potential to host diversity in early-stage data modeling. We conclude with lessons learned, limitations and challenges involved in scaling and refining the framework for broader adoption. △ Less

Submitted 11 July, 2025; originally announced July 2025.

On the feasibility of semantic query metrics

Authors: George Fletcher, Peter Wood, Nikolay Yakovets

Abstract: We consider the problem of defining semantic metrics for relational database queries. Informally, a semantic query metric for a query language $L$ is a metric function $δ:L\times L\to \mathbb{N}$ where $δ(Q_1, Q_2)$ represents the length of a shortest path between queries $Q_1$ and $Q_2$ in a graph. In this graph, nodes are queries from $L$, and edges connect semantically distinct queries where on… ▽ More We consider the problem of defining semantic metrics for relational database queries. Informally, a semantic query metric for a query language $L$ is a metric function $δ:L\times L\to \mathbb{N}$ where $δ(Q_1, Q_2)$ represents the length of a shortest path between queries $Q_1$ and $Q_2$ in a graph. In this graph, nodes are queries from $L$, and edges connect semantically distinct queries where one query is maximally semantically contained in the other. Since query containment is undecidable for first-order queries, we focus on the simpler language of conjunctive queries. We establish that defining a semantic query metric is impossible even for conjunctive queries. Given this impossibility result, we identify a significant subclass of conjunctive queries where such a metric is feasible, and we establish the computational complexity of calculating distances within this language. △ Less

Submitted 23 March, 2025; originally announced March 2025.

CREDAL: Close Reading of Data Models

Authors: George Fletcher, Olha Nahurna, Matvii Prytula, Julia Stoyanovich

Abstract: Data models are necessary for the birth of data and of any data-driven system. Indeed, every algorithm, every machine learning model, every statistical model, and every database has an underlying data model without which the system would not be usable. Hence, data models are excellent sites for interrogating the (material, social, political, ...) conditions giving rise to a data system. Towards th… ▽ More Data models are necessary for the birth of data and of any data-driven system. Indeed, every algorithm, every machine learning model, every statistical model, and every database has an underlying data model without which the system would not be usable. Hence, data models are excellent sites for interrogating the (material, social, political, ...) conditions giving rise to a data system. Towards this, drawing inspiration from literary criticism, we propose to closely read data models in the same spirit as we closely read literary artifacts. Close readings of data models reconnect us with, among other things, the materiality, the genealogies, the techne, the closed nature, and the design of technical systems. While recognizing from literary theory that there is no one correct way to read, it is nonetheless critical to have systematic guidance for those unfamiliar with close readings. This is especially true for those trained in the computing and data sciences, who too often are enculturated to set aside the socio-political aspects of data work. A systematic methodology for reading data models currently does not exist. To fill this gap, we present the CREDAL methodology for close readings of data models. We detail our iterative development process and present results of a qualitative evaluation of CREDAL demonstrating its usability, usefulness, and effectiveness in the critical study of data. △ Less

Submitted 11 February, 2025; originally announced February 2025.

Meta-Property Graphs: Extending Property Graphs with Metadata Awareness and Reification

Authors: Sepehr Sadoughi, Nikolay Yakovets, George Fletcher

Abstract: The ISO standard Property Graph model has become increasingly popular for representing complex, interconnected data. However, it lacks native support for querying metadata and reification, which limits its abilities to deal with the demands of modern applications. We introduce the vision of Meta-Property Graphs, a backwards compatible extension of the property graph model addressing these limitati… ▽ More The ISO standard Property Graph model has become increasingly popular for representing complex, interconnected data. However, it lacks native support for querying metadata and reification, which limits its abilities to deal with the demands of modern applications. We introduce the vision of Meta-Property Graphs, a backwards compatible extension of the property graph model addressing these limitations. Our approach enables first-class treatment of labels and properties as queryable objects and supports reification of substructures in a graph. We propose MetaGPML, a backwards compatible extension of the Graph Pattern Matching Language forming the core of the ISO standard GQL, to query these enhanced graphs. We demonstrate how these foundations pave the way for advanced data analytics and governance tasks that are challenging or impossible with current property graph systems. △ Less

Submitted 15 December, 2025; v1 submitted 17 October, 2024; originally announced October 2024.

Quantifying gendered citation imbalance in computer science conferences

Authors: Kazuki Nakajima, Yuya Sasaki, Sohei Tokuno, George Fletcher

Abstract: The number of citations received by papers often exhibits imbalances in terms of author attributes such as country of affiliation and gender. While recent studies have quantified citation imbalance in terms of the authors' gender in journal papers, the computer science discipline, where researchers frequently present their work at conferences, may exhibit unique patterns in gendered citation imbal… ▽ More The number of citations received by papers often exhibits imbalances in terms of author attributes such as country of affiliation and gender. While recent studies have quantified citation imbalance in terms of the authors' gender in journal papers, the computer science discipline, where researchers frequently present their work at conferences, may exhibit unique patterns in gendered citation imbalance. Additionally, understanding how network properties in citations influence citation imbalances remains challenging due to a lack of suitable reference models. In this paper, we develop a family of reference models for citation networks and investigate gender imbalance in citations between papers published in computer science conferences. By deploying these reference models, we found that homophily in citations is strongly associated with gendered citation imbalance in computer science, whereas heterogeneity in the number of citations received per paper has a relatively minor association with it. Furthermore, we found that the gendered citation imbalance is most pronounced in papers published in the highest-ranked conferences, is present across different subfields, and extends to citation-based rankings of papers. Our study provides a framework for investigating associations between network properties and citation imbalances, aiming to enhance our understanding of the structure and dynamics of citations between research publications. △ Less

Submitted 3 August, 2024; originally announced August 2024.

Comments: 14 pages, 6 figures, and 7 tables. This work has been accepted as a full paper in the AAAI/ACM conference on Artificial Intelligence, Ethics and Society (AIES) 2024

Optimizing Navigational Graph Queries

Authors: Thomas Mulder, George Fletcher, Nikolay Yakovets

Abstract: We study the optimization of navigational graph queries, i.e., queries which combine recursive and pattern-matching fragments. Current approaches to their evaluation are not effective in practice. Towards addressing this, we present a number of novel powerful optimization techniques which aim to constrain the intermediate results during query evaluation. We show how these techniques can be planned… ▽ More We study the optimization of navigational graph queries, i.e., queries which combine recursive and pattern-matching fragments. Current approaches to their evaluation are not effective in practice. Towards addressing this, we present a number of novel powerful optimization techniques which aim to constrain the intermediate results during query evaluation. We show how these techniques can be planned effectively and executed efficiently towards the first practical evaluation solution for complex navigational queries on real-world workloads. Indeed, our experimental results show several orders of magnitude improvement in query evaluation performance over state-of-the-art techniques on a wide range of queries on diverse datasets. △ Less

Submitted 20 May, 2026; v1 submitted 8 June, 2024; originally announced June 2024.

Comments: 26 pages, 26 figures. Published in The VLDB Journal, vol. 34, art. 16 (2025)

ACM Class: H.2.4

Journal ref: The VLDB Journal 34, 16 (2025)

Discovering Graph Generating Dependencies for Property Graph Profiling

Authors: Larissa C. Shimomura, Nikolay Yakovets, George Fletcher

Abstract: With the increasing use of graph-structured data, there is also increasing interest in investigating graph data dependencies and their applications, e.g., in graph data profiling. Graph Generating Dependencies (GGDs) are a class of dependencies for property graphs that can express the relation between different graph patterns and constraints based on their attribute similarities. Rich syntax and s… ▽ More With the increasing use of graph-structured data, there is also increasing interest in investigating graph data dependencies and their applications, e.g., in graph data profiling. Graph Generating Dependencies (GGDs) are a class of dependencies for property graphs that can express the relation between different graph patterns and constraints based on their attribute similarities. Rich syntax and semantics of GGDs make them a good candidate for graph data profiling. Nonetheless, GGDs are difficult to define manually, especially when there are no data experts available. In this paper, we propose GGDMiner, a framework for discovering approximate GGDs from graph data automatically, with the intention of profiling graph data through GGDs for the user. GGDMiner has three main steps: (1) pre-processing, (2) candidate generation, and, (3) GGD extraction. To optimize memory consumption and execution time, GGDMiner uses a factorized representation of each discovered graph pattern, called Answer Graph. Our results show that the discovered set of GGDs can give an overview about the input graph, both schema level information and also correlations between the graph patterns and attributes. △ Less

Submitted 3 February, 2025; v1 submitted 25 March, 2024; originally announced March 2024.

Public Perceptions of Fairness Metrics Across Borders

Authors: Yuya Sasaki, Sohei Tokuno, Haruka Maeda, Kazuki Nakajima, Osamu Sakura, George Fletcher, Mykola Pechenizkiy, Panagiotis Karras, Irina Shklovski

Abstract: Which fairness metrics are appropriately applicable in your contexts? There may be instances of discordance regarding the perception of fairness, even when the outcomes comply with established fairness metrics. Several questionnaire-based surveys have been conducted to evaluate fairness metrics with human perceptions of fairness. However, these surveys were limited in scope, including only a few h… ▽ More Which fairness metrics are appropriately applicable in your contexts? There may be instances of discordance regarding the perception of fairness, even when the outcomes comply with established fairness metrics. Several questionnaire-based surveys have been conducted to evaluate fairness metrics with human perceptions of fairness. However, these surveys were limited in scope, including only a few hundred participants within a single country. In this study, we conduct an international survey to evaluate public perceptions of various fairness metrics in decision-making scenarios. We collected responses from 1,000 participants in each of China, France, Japan, and the United States, amassing a total of 4,000 participants, to analyze the preferences of fairness metrics. Our survey consists of three distinct scenarios paired with four fairness metrics. This investigation explores the relationship between personal attributes and the choice of fairness metrics, uncovering a significant influence of national context on these preferences. △ Less

Submitted 8 May, 2025; v1 submitted 24 March, 2024; originally announced March 2024.

The Linked Data Benchmark Council (LDBC): Driving competition and collaboration in the graph data management space

Authors: Gábor Szárnyas, Brad Bebee, Altan Birler, Alin Deutsch, George Fletcher, Henry A. Gabb, Denise Gosnell, Alastair Green, Zhihui Guo, Keith W. Hare, Jan Hidders, Alexandru Iosup, Atanas Kiryakov, Tomas Kovatchev, Xinsheng Li, Leonid Libkin, Heng Lin, Xiaojian Luo, Arnau Prat-Pérez, David Püroja, Shipeng Qi, Oskar van Rest, Benjamin A. Steer, Dávid Szakállas, Bing Tong , et al. (8 additional authors not shown)

Abstract: Graph data management is instrumental for several use cases such as recommendation, root cause analysis, financial fraud detection, and enterprise knowledge representation. Efficiently supporting these use cases yields a number of unique requirements, including the need for a concise query language and graph-aware query optimization techniques. The goal of the Linked Data Benchmark Council (LDBC)… ▽ More Graph data management is instrumental for several use cases such as recommendation, root cause analysis, financial fraud detection, and enterprise knowledge representation. Efficiently supporting these use cases yields a number of unique requirements, including the need for a concise query language and graph-aware query optimization techniques. The goal of the Linked Data Benchmark Council (LDBC) is to design a set of standard benchmarks that capture representative categories of graph data management problems, making the performance of systems comparable and facilitating competition among vendors. LDBC also conducts research on graph schemas and graph query languages. This paper introduces the LDBC organization and its work over the last decade. △ Less

Submitted 30 August, 2024; v1 submitted 10 July, 2023; originally announced July 2023.

ACM Class: H.2.4

Bridging graph data models: RDF, RDF-star, and property graphs as directed acyclic graphs

Authors: Ewout Gelling, George Fletcher, Michael Schmidt

Abstract: Graph database users today face a choice between two technology stacks: the Resource Description Framework (RDF), on one side, is a data model with built-in semantics that was originally developed by the W3C to exchange interconnected data on the Web; on the other side, Labeled Property Graphs (LPGs) are geared towards efficient graph processing and have strong roots in developer and engineering c… ▽ More Graph database users today face a choice between two technology stacks: the Resource Description Framework (RDF), on one side, is a data model with built-in semantics that was originally developed by the W3C to exchange interconnected data on the Web; on the other side, Labeled Property Graphs (LPGs) are geared towards efficient graph processing and have strong roots in developer and engineering communities. The two models look at graphs from different abstraction layers (triples in RDF vs. edges connecting vertices with inlined properties in LPGs), expose - at least at the surface - distinct features, come with different query languages, and are embedded into their own software ecosystems. In this short paper, we introduce a novel unifying graph data model called Statement Graphs, which combines the traits of both RDF and LPG and achieves interoperability at different levels: it (a) provides the ability to manage RDF and LPG data as a single, interconnected graph, (b) supports querying over the integrated graph using any RDF or LPG query language, while (c) clearing the way for graph stack independent data exchange mechanisms and formats. We formalize our new model as directed acyclic graphs and sketch a system of bidirectional mappings between RDF, LPGs, and Statement Graphs. Our mappings implicitly define read query semantics for RDF and LPGs query languages over the unified data model, thus providing graph users with the flexibility to use the query language of their choice for their graph use cases. As a proof of concept for our ideas, we also present the 1G Playground; an in-memory DBMS built on the concepts of Statement Graphs, which facilitates storage of both RDF and LPG data, and allows for cross-model querying using both SPARQL and Gremlin. △ Less

Submitted 25 April, 2023; originally announced April 2023.

Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and OUT Size Estimation over Joins

Authors: Kyoungmin Kim, Jaehyun Ha, George Fletcher, Wook-Shin Han

Abstract: We propose a new method for estimating the number of answers OUT of a small join query Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy all the following statements. - Support arbitrary Q, which can be either acyclic or cyclic, and contain binary and non-binary relations. - Guarantee an arbitrary small error with a high probability always in Õ(AGM/OU… ▽ More We propose a new method for estimating the number of answers OUT of a small join query Q in a large database D, and for uniform sampling over joins. Our method is the first to satisfy all the following statements. - Support arbitrary Q, which can be either acyclic or cyclic, and contain binary and non-binary relations. - Guarantee an arbitrary small error with a high probability always in Õ(AGM/OUT) time, where AGM is the AGM bound OUT (an upper bound of OUT), and Õ hides the polylogarithmic factor of input size. We also explain previous join size estimators in a unified framework. All methods including ours rely on certain indexes on relations in D, which take linear time to build offline. Additionally, we extend our method using generalized hypertree decompositions (GHDs) to achieve a lower complexity than Õ(AGM/OUT) when OUT is small, and present optimization techniques for improving estimation efficiency and accuracy. △ Less

Submitted 9 April, 2023; v1 submitted 3 April, 2023; originally announced April 2023.

Comments: 19 pages

PG-Schema: Schemas for Property Graphs

Authors: Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savković, Michael Schmidt, Juan Sequeda, Sławek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoč, Mingxi Wu, Dušan Živković

Abstract: Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand, schema support is limited both in existing systems and in the first version of the GQL Standard. It is anticipated that the second version of the GQL… ▽ More Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand, schema support is limited both in existing systems and in the first version of the GQL Standard. It is anticipated that the second version of the GQL Standard will include a rich DDL. Aiming to inspire the development of GQL and enhance the capabilities of graph database systems, we propose PG-Schema, a simple yet powerful formalism for specifying property graph schemas. It features PG-Types with flexible type definitions supporting multi-inheritance, as well as expressive constraints based on the recently proposed PG-Keys formalism. We provide the formal syntax and semantics of PG-Schema, which meet principled design requirements grounded in contemporary property graph management scenarios, and offer a detailed comparison of its features with those of existing schema languages and graph database systems. △ Less

Submitted 8 July, 2023; v1 submitted 20 November, 2022; originally announced November 2022.

Comments: 26 pages

Journal ref: Proc. ACM Manag. Data (2023)

Reasoning on Property Graphs with Graph Generating Dependencies

Authors: Larissa C. Shimomura, Nikolay Yakovets, George Fletcher

Abstract: Graph Generating Dependencies (GGDs) informally express constraints between two (possibly different) graph patterns which enforce relationships on both graph's data (via property value constraints) and its structure (via topological constraints). Graph Generating Dependencies (GGDs) can express tuple- and equality-generating dependencies on property graphs, both of which find broad application in… ▽ More Graph Generating Dependencies (GGDs) informally express constraints between two (possibly different) graph patterns which enforce relationships on both graph's data (via property value constraints) and its structure (via topological constraints). Graph Generating Dependencies (GGDs) can express tuple- and equality-generating dependencies on property graphs, both of which find broad application in graph data management. In this paper, we discuss the reasoning behind GGDs. We propose algorithms to solve the satisfiability, implication, and validation problems for GGDs and analyze their complexity. To demonstrate the practical use of GGDs, we propose an algorithm which finds inconsistencies in data through validation of GGDs. Our experiments show that even though the validation of GGDs has high computational complexity, GGDs can be used to find data inconsistencies in a feasible execution time on both synthetic and real-world data. △ Less

Submitted 1 November, 2022; originally announced November 2022.

ACM Class: H.2

FairSNA: Algorithmic Fairness in Social Network Analysis

Authors: Akrati Saxena, George Fletcher, Mykola Pechenizkiy

Abstract: In recent years, designing fairness-aware methods has received much attention in various domains, including machine learning, natural language processing, and information retrieval. However, understanding structural bias and inequalities in social networks and designing fairness-aware methods for various research problems in social network analysis (SNA) have not received much attention. In this w… ▽ More In recent years, designing fairness-aware methods has received much attention in various domains, including machine learning, natural language processing, and information retrieval. However, understanding structural bias and inequalities in social networks and designing fairness-aware methods for various research problems in social network analysis (SNA) have not received much attention. In this work, we highlight how the structural bias of social networks impacts the fairness of different SNA methods. We further discuss fairness aspects that should be considered while proposing network structure-based solutions for different SNA problems, such as link prediction, influence maximization, centrality ranking, and community detection. This paper clearly highlights that very few works have considered fairness and bias while proposing solutions; even these works are mainly focused on some research topics, such as link prediction, influence maximization, and PageRank. However, fairness has not yet been addressed for other research topics, such as influence blocking and community detection. We review state-of-the-art for different research topics in SNA, including the considered fairness constraints, their limitations, and our vision. This paper also covers evaluation metrics, available datasets, and synthetic network generating models used in such studies. Finally, we highlight various open research directions that require researchers' attention to bridge the gap between fairness and SNA. △ Less

Submitted 20 March, 2024; v1 submitted 4 September, 2022; originally announced September 2022.

GNN Transformation Framework for Improving Efficiency and Scalability

Authors: Seiji Maekawa, Yuya Sasaki, George Fletcher, Makoto Onizuka

Abstract: We propose a framework that automatically transforms non-scalable GNNs into precomputation-based GNNs which are efficient and scalable for large-scale graphs. The advantages of our framework are two-fold; 1) it transforms various non-scalable GNNs to scale well to large-scale graphs by separating local feature aggregation from weight learning in their graph convolution, 2) it efficiently executes… ▽ More We propose a framework that automatically transforms non-scalable GNNs into precomputation-based GNNs which are efficient and scalable for large-scale graphs. The advantages of our framework are two-fold; 1) it transforms various non-scalable GNNs to scale well to large-scale graphs by separating local feature aggregation from weight learning in their graph convolution, 2) it efficiently executes precomputation on GPU for large-scale graphs by decomposing their edges into small disjoint and balanced sets. Through extensive experiments with large-scale graphs, we demonstrate that the transformed GNNs run faster in training time than existing GNNs while achieving competitive accuracy to the state-of-the-art GNNs. Consequently, our transformation framework provides simple and efficient baselines for future research on scalable GNNs. △ Less

Submitted 25 July, 2022; originally announced July 2022.

Comments: Accepted to ECML-PKDD 2022

Universal Early Warning Signals of Phase Transitions in Climate Systems

Authors: Daniel Dylewsky, Timothy M. Lenton, Marten Scheffer, Thomas M. Bury, Christopher G. Fletcher, Madhur Anand, Chris T. Bauch

Abstract: The potential for complex systems to exhibit tipping points in which an equilibrium state undergoes a sudden and often irreversible shift is well established, but prediction of these events using standard forecast modeling techniques is quite difficult. This has led to the development of an alternative suite of methods that seek to identify signatures of critical phenomena in data, which are expec… ▽ More The potential for complex systems to exhibit tipping points in which an equilibrium state undergoes a sudden and often irreversible shift is well established, but prediction of these events using standard forecast modeling techniques is quite difficult. This has led to the development of an alternative suite of methods that seek to identify signatures of critical phenomena in data, which are expected to occur in advance of many classes of dynamical bifurcation. Crucially, the manifestations of these critical phenomena are generic across a variety of systems, meaning that data-intensive deep learning methods can be trained on (abundant) synthetic data and plausibly prove effective when transferred to (more limited) empirical data sets. This paper provides a proof of concept for this approach as applied to lattice phase transitions: a deep neural network trained exclusively on 2D Ising model phase transitions is tested on a number of real and simulated climate systems with considerable success. Its accuracy frequently surpasses that of conventional statistical indicators, with performance shown to be consistently improved by the inclusion of spatial indicators. Tools such as this may offer valuable insight into climate tipping events, as remote sensing measurements provide increasingly abundant data on complex geospatially-resolved Earth systems. △ Less

Submitted 5 December, 2022; v1 submitted 31 May, 2022; originally announced June 2022.

Survey on Fair Reinforcement Learning: Theory and Practice

Authors: Pratik Gajane, Akrati Saxena, Maryam Tavakol, George Fletcher, Mykola Pechenizkiy

Abstract: Fairness-aware learning aims at satisfying various fairness constraints in addition to the usual performance criteria via data-driven machine learning techniques. Most of the research in fairness-aware learning employs the setting of fair-supervised learning. However, many dynamic real-world applications can be better modeled using sequential decision-making problems and fair reinforcement learnin… ▽ More Fairness-aware learning aims at satisfying various fairness constraints in addition to the usual performance criteria via data-driven machine learning techniques. Most of the research in fairness-aware learning employs the setting of fair-supervised learning. However, many dynamic real-world applications can be better modeled using sequential decision-making problems and fair reinforcement learning provides a more suitable alternative for addressing these problems. In this article, we provide an extensive overview of fairness approaches that have been implemented via a reinforcement learning (RL) framework. We discuss various practical applications in which RL methods have been applied to achieve a fair solution with high accuracy. We further include various facets of the theory of fair reinforcement learning, organizing them into single-agent RL, multi-agent RL, long-term fairness via RL, and offline learning. Moreover, we highlight a few major issues to explore in order to advance the field of fair-RL, namely - i) correcting societal biases, ii) feasibility of group fairness or individual fairness, and iii) explainability in RL. Our work is beneficial for both researchers and practitioners as we discuss articles providing mathematical guarantees as well as articles with empirical studies on real-world problems. △ Less

Submitted 20 May, 2022; originally announced May 2022.

The Banking Transactions Dataset and its Comparative Analysis with Scale-free Networks

Authors: Akrati Saxena, Yulong Pei, Jan Veldsink, Werner van Ipenburg, George Fletcher, Mykola Pechenizkiy

Abstract: We construct a network of 1.6 million nodes from banking transactions of users of Rabobank. We assign two weights on each edge, which are the aggregate transferred amount and the total number of transactions between the users from the year 2010 to 2020. We present a detailed analysis of the unweighted and both weighted networks by examining their degree, strength, and weight distributions, as well… ▽ More We construct a network of 1.6 million nodes from banking transactions of users of Rabobank. We assign two weights on each edge, which are the aggregate transferred amount and the total number of transactions between the users from the year 2010 to 2020. We present a detailed analysis of the unweighted and both weighted networks by examining their degree, strength, and weight distributions, as well as the topological assortativity and weighted assortativity, clustering, and weighted clustering, together with correlations between these quantities. We further study the meso-scale properties of the networks and compare them to a randomized reference system. We also analyze the characteristics of nodes and edges using centrality measures to understand their roles in the money transaction system. This will be the first publicly shared dataset of intra-bank transactions, and this work highlights the unique characteristics of banking transaction networks with other scale-free networks. △ Less

Submitted 22 September, 2021; originally announced September 2021.

GenCAT: Generating Attributed Graphs with Controlled Relationships between Classes, Attributes, and Topology

Authors: Seiji Maekawa, Yuya Sasaki, George Fletcher, Makoto Onizuka

Abstract: Generating large synthetic attributed graphs with node labels is an important task to support various experimental studies for graph analysis methods. Existing graph generators fail to simultaneously simulate the relationships between labels, attributes, and topology which real-world graphs exhibit. Motivated by this limitation, we propose GenCAT, an attributed graph generator for controlling thos… ▽ More Generating large synthetic attributed graphs with node labels is an important task to support various experimental studies for graph analysis methods. Existing graph generators fail to simultaneously simulate the relationships between labels, attributes, and topology which real-world graphs exhibit. Motivated by this limitation, we propose GenCAT, an attributed graph generator for controlling those relationships, which has the following advantages. (i) GenCAT generates graphs with user-specified node degrees and flexibly controls the relationship between nodes and labels by incorporating the connection proportion for each node to classes. (ii) Generated attribute values follow user-specified distributions, and users can flexibly control the correlation between the attributes and labels. (iii) Graph generation scales linearly to the number of edges. GenCAT is the first generator to support all three of these practical features. Through extensive experiments, we demonstrate that GenCAT can efficiently generate high-quality complex attributed graphs with user-controlled relationships between labels, attributes, and topology. △ Less

Submitted 12 February, 2023; v1 submitted 9 September, 2021; originally announced September 2021.

Comments: Accepted to Information Systems

A General Cardinality Estimation Framework for Subgraph Matching in Property Graphs

Authors: Wilco van Leeuwen, George Fletcher, Nikolay Yakovets

Abstract: Many techniques have been developed for the cardinality estimation problem in data management systems. In this document, we introduce a framework for cardinality estimation of query patterns over property graph databases, which makes it possible to analyze, compare and combine different cardinality estimation approaches. This framework consists of three phases: obtaining a set of estimates for som… ▽ More Many techniques have been developed for the cardinality estimation problem in data management systems. In this document, we introduce a framework for cardinality estimation of query patterns over property graph databases, which makes it possible to analyze, compare and combine different cardinality estimation approaches. This framework consists of three phases: obtaining a set of estimates for some subqueries, extending this set and finally combining the set into a single cardinality estimate for the query. We show that (parts of) many of the existing cardinality estimation approaches can be used as techniques in one of the phases from our framework. The three phases are loosely coupled, this makes it possible to combine (parts of) current cardinality estimation approaches. We create a graph version of the Join Order Benchmark to perform experiments with different combinations of techniques. The results show that query patterns without property constraints can be accurately estimated using synopses for small patterns. Accurate estimation of query patterns with property constraints require new estimation techniques to be developed that capture correlations between the property constraints and the topology in graph databases. △ Less

Submitted 11 August, 2021; originally announced August 2021.

Journal ref: IEEE Transactions on Knowledge and Data Engineering ( Volume: 35, Issue: 6, 01 June 2023)

Threshold Queries in Theory and in the Wild

Authors: Angela Bonifati, Stefania Dumbrava, George Fletcher, Jan Hidders, Matthias Hofer, Wim Martens, Filip Murlak, Joshua Shinavier, Sławek Staworko, Dominik Tomaszuk

Abstract: Threshold queries are an important class of queries that only require computing or counting answers up to a specified threshold value. To the best of our knowledge, threshold queries have been largely disregarded in the research literature, which is surprising considering how common they are in practice. In this paper, we present a deep theoretical analysis of threshold query evaluation and show t… ▽ More Threshold queries are an important class of queries that only require computing or counting answers up to a specified threshold value. To the best of our knowledge, threshold queries have been largely disregarded in the research literature, which is surprising considering how common they are in practice. In this paper, we present a deep theoretical analysis of threshold query evaluation and show that thresholds can be used to significantly improve the asymptotic bounds of state-of-the-art query evaluation algorithms. We also empirically show that threshold queries are significant in practice. In surprising contrast to conventional wisdom, we found important scenarios in real-world data sets in which users are interested in computing the results of queries up to a certain threshold, independent of a ranking function that orders the query results by importance. △ Less

Submitted 17 November, 2021; v1 submitted 29 June, 2021; originally announced June 2021.

[Technical Report] Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation

Authors: Kyoungmin Kim, Hyeonji Kim, George Fletcher, Wook-Shin Han

Abstract: Graph pattern cardinality estimation is the problem of estimating the number of embeddings of a query graph in a data graph. This fundamental problem arises, for example, during query planning in subgraph matching algorithms. There are two major approaches to solving the problem: sampling and synopsis. Synopsis (or summary)-based methods are fast and accurate if synopses capture information of gra… ▽ More Graph pattern cardinality estimation is the problem of estimating the number of embeddings of a query graph in a data graph. This fundamental problem arises, for example, during query planning in subgraph matching algorithms. There are two major approaches to solving the problem: sampling and synopsis. Synopsis (or summary)-based methods are fast and accurate if synopses capture information of graphs well. However, these methods suffer from large errors due to loss of information during summarization and inherent assumptions. Sampling-based methods are unbiased but suffer from large estimation variance due to large sample space. To address these limitations, we propose Alley, a hybrid method that combines both sampling and synopses. Alley employs 1) a novel sampling strategy, random walk with intersection, which effectively reduces the sample space, 2) branching to further reduce variance, and 3) a novel mining approach that extracts and indexes tangled patterns as synopses which are inherently difficult to estimate by sampling. By using them in the online estimation phase, we can effectively reduce the sample space while still ensuring unbiasedness. We establish that Alley has worst-case optimal runtime and approximation quality guarantees for any given error bound $ε$ and required confidence $μ$. In addition to the theoretical aspect of Alley, our extensive experiments show that Alley outperforms the state-of-the-art methods by up to orders of magnitude higher accuracy with similar efficiency. △ Less

Submitted 26 March, 2021; v1 submitted 25 March, 2021; originally announced March 2021.

Comments: 17 pages

How Fair is Fairness-aware Representative Ranking and Methods for Fair Ranking

Authors: Akrati Saxena, George Fletcher, Mykola Pechenizkiy

Abstract: Rankings of people and items has been highly used in selection-making, match-making, and recommendation algorithms that have been deployed on ranging of platforms from employment websites to searching tools. The ranking position of a candidate affects the amount of opportunities received by the ranked candidate. It has been observed in several works that the ranking of candidates based on their sc… ▽ More Rankings of people and items has been highly used in selection-making, match-making, and recommendation algorithms that have been deployed on ranging of platforms from employment websites to searching tools. The ranking position of a candidate affects the amount of opportunities received by the ranked candidate. It has been observed in several works that the ranking of candidates based on their score can be biased for candidates belonging to the minority community. In recent works, the fairness-aware representative ranking was proposed for computing fairness-aware re-ranking of results. The proposed algorithm achieves the desired distribution of top-ranked results with respect to one or more protected attributes. In this work, we highlight the bias in fairness-aware representative ranking for an individual as well as for a group if the group is sub-active on the platform. We define individual unfairness and group unfairness and propose methods to generate ideal individual and group fair representative ranking if the universal representation ratio is known or unknown. The simulation results show the quantified analysis of fairness in the proposed solutions. The paper is concluded with open challenges and further directions. △ Less

Submitted 1 March, 2021; originally announced March 2021.

Safety Case Templates for Autonomous Systems

Authors: Robin Bloomfield, Gareth Fletcher, Heidy Khlaaf, Luke Hinde, Philippa Ryan

Abstract: This report documents safety assurance argument templates to support the deployment and operation of autonomous systems that include machine learning (ML) components. The document presents example safety argument templates covering: the development of safety requirements, hazard analysis, a safety monitor architecture for an autonomous system including at least one ML element, a component with ML… ▽ More This report documents safety assurance argument templates to support the deployment and operation of autonomous systems that include machine learning (ML) components. The document presents example safety argument templates covering: the development of safety requirements, hazard analysis, a safety monitor architecture for an autonomous system including at least one ML element, a component with ML and the adaptation and change of the system over time. The report also presents generic templates for argument defeaters and evidence confidence that can be used to strengthen, review, and adapt the templates as necessary. This report is made available to get feedback on the approach and on the templates. This work was sponsored by the UK Dstl under the R-cloud framework. △ Less

Submitted 11 March, 2021; v1 submitted 29 January, 2021; originally announced February 2021.

Comments: 136 pages, 57 figures

Report number: Adelard D/1294/87004/1

NodeSim: Node Similarity based Network Embedding for Diverse Link Prediction

Authors: Akrati Saxena, George Fletcher, Mykola Pechenizkiy

Abstract: In real-world complex networks, understanding the dynamics of their evolution has been of great interest to the scientific community. Predicting future links is an essential task of social network analysis as the addition or removal of the links over time leads to the network evolution. In a network, links can be categorized as intra-community links if both end nodes of the link belong to the same… ▽ More In real-world complex networks, understanding the dynamics of their evolution has been of great interest to the scientific community. Predicting future links is an essential task of social network analysis as the addition or removal of the links over time leads to the network evolution. In a network, links can be categorized as intra-community links if both end nodes of the link belong to the same community, otherwise inter-community links. The existing link-prediction methods have mainly focused on achieving high accuracy for intra-community link prediction. In this work, we propose a network embedding method, called NodeSim, which captures both similarities between the nodes and the community structure while learning the low-dimensional representation of the network. The embedding is learned using the proposed NodeSim random walk, which efficiently explores the diverse neighborhood while keeping the more similar nodes closer in the context of the node. We verify the efficacy of the proposed embedding method over state-of-the-art methods using diverse link prediction. We propose a machine learning model for link prediction that considers both the nodes' embedding and their community information to predict the link between two given nodes. Extensive experimental results on several real-world networks demonstrate the effectiveness of the proposed framework for both inter and intra-community link prediction. △ Less

Submitted 1 February, 2021; originally announced February 2021.

GGDs: Graph Generating Dependencies

Authors: Larissa C. Shimomura, George Fletcher, Nikolay Yakovets

Abstract: We propose Graph Generating Dependencies (GGDs), a new class of dependencies for property graphs. Extending the expressivity of state of the art constraint languages, GGDs can express both tuple- and equality-generating dependencies on property graphs, both of which find broad application in graph data management. We provide the formal definition of GGDs, analyze the validation problem for GGDs, a… ▽ More We propose Graph Generating Dependencies (GGDs), a new class of dependencies for property graphs. Extending the expressivity of state of the art constraint languages, GGDs can express both tuple- and equality-generating dependencies on property graphs, both of which find broad application in graph data management. We provide the formal definition of GGDs, analyze the validation problem for GGDs, and demonstrate the practical utility of GGDs. △ Less

Submitted 15 June, 2020; v1 submitted 21 April, 2020; originally announced April 2020.

Comments: 5 pages

ACM Class: H.2

Knowledge Scientists: Unlocking the data-driven organization

Authors: George Fletcher, Paul Groth, Juan Sequeda

Abstract: Organizations across all sectors are increasingly undergoing deep transformation and restructuring towards data-driven operations. The central role of data highlights the need for reliable and clean data. Unreliable, erroneous, and incomplete data lead to critical bottlenecks in processing pipelines and, ultimately, service failures, which are disastrous for the competitive performance of the orga… ▽ More Organizations across all sectors are increasingly undergoing deep transformation and restructuring towards data-driven operations. The central role of data highlights the need for reliable and clean data. Unreliable, erroneous, and incomplete data lead to critical bottlenecks in processing pipelines and, ultimately, service failures, which are disastrous for the competitive performance of the organization. Given its central importance, those organizations which recognize and react to the need for reliable data will have the advantage in the coming decade. We argue that the technologies for reliable data are driven by distinct concerns and expertise which complement those of the data scientist and the data engineer. Those organizations which identify the central importance of meaningful, explainable, reproducible, and maintainable data will be at the forefront of the democratization of reliable data. We call the new role which must be developed to fill this critical need the Knowledge Scientist. The organizational structures, tools, methodologies and techniques to support and make possible the work of knowledge scientists are still in their infancy. As organizations not only use data but increasingly rely on data, it is time to empower the people who are central to this transformation. △ Less

Submitted 16 April, 2020; originally announced April 2020.

Language-aware Indexing for Conjunctive Path Queries

Authors: Yuya Sasaki, George Fletcher, Makoto Onizuka

Abstract: Conjunctive path queries (CPQ) are one of the most frequently used queries for complex graph analysis. However, current graph indexes are not tailored to fully support the power of query languages to express CPQs. Consequently, current methods do not take advantage of significant pruning opportunities during \cpq{} evaluation, resulting in poor query processing performance. We propose the CPQ-awar… ▽ More Conjunctive path queries (CPQ) are one of the most frequently used queries for complex graph analysis. However, current graph indexes are not tailored to fully support the power of query languages to express CPQs. Consequently, current methods do not take advantage of significant pruning opportunities during \cpq{} evaluation, resulting in poor query processing performance. We propose the CPQ-aware path index CPQx, the first path index tailored to the expressivity of CPQ. CPQx is built on the partition of the set of source-target vertex pairs of paths in a graph based on the structural notion of path-bisimulation. Path-bisimulation is an equivalence relation on paths such that each partition block induced by the relation consists of paths in the graph indistinguishable with respect to CPQs. This language-aware partitioning of the graph can significantly reduce the cost of query evaluation. We present methods to support the full index life cycle: index construction, maintenance, and query processing with our index. We also develop interest-aware CPQx to reduce index size and index construction overhead while accelerating query evaluation for queries of interest. We demonstrate through extensive experiments on 14 real graphs that our methods accelerate query processing by up to multiple orders of magnitude over the state-of-the-art methods, with smaller index sizes. Our complete C++ codebase is available as open source for further research. △ Less

Submitted 27 December, 2021; v1 submitted 6 March, 2020; originally announced March 2020.

Comments: 14 pages, 11 figures

ACM Class: H.2.0

Towards Identifying and closing Gaps in Assurance of autonomous Road vehicleS -- a collection of Technical Notes Part 2

Authors: Robin Bloomfield, Gareth Fletcher, Heidy Khlaaf, Philippa Ryan, Shuji Kinoshita, Yoshiki Kinoshit, Makoto Takeyama, Yutaka Matsubara, Peter Popov, Kazuki Imai, Yoshinori Tsutake

Abstract: This report provides an introduction and overview of the Technical Topic Notes (TTNs) produced in the Towards Identifying and closing Gaps in Assurance of autonomous Road vehicleS (Tigars) project. These notes aim to support the development and evaluation of autonomous vehicles. Part 1 addresses: Assurance-overview and issues, Resilience and Safety Requirements, Open Systems Perspective and Formal… ▽ More This report provides an introduction and overview of the Technical Topic Notes (TTNs) produced in the Towards Identifying and closing Gaps in Assurance of autonomous Road vehicleS (Tigars) project. These notes aim to support the development and evaluation of autonomous vehicles. Part 1 addresses: Assurance-overview and issues, Resilience and Safety Requirements, Open Systems Perspective and Formal Verification and Static Analysis of ML Systems. This report is Part 2 and discusses: Simulation and Dynamic Testing, Defence in Depth and Diversity, Security-Informed Safety Analysis, Standards and Guidelines. △ Less

Submitted 28 February, 2020; originally announced March 2020.

Comments: Authors of the individual notes are indicated in the text

Report number: Adelard Tigars D5.6 D/1259/138008/7

Towards Identifying and closing Gaps in Assurance of autonomous Road vehicleS -- a collection of Technical Notes Part 1

Authors: Robin Bloomfield, Gareth Fletcher, Heidy Khlaaf, Philippa Ryan, Shuji Kinoshita, Yoshiki Kinoshit, Makoto Takeyama, Yutaka Matsubara, Peter Popov, Kazuki Imai, Yoshinori Tsutake

Abstract: This report provides an introduction and overview of the Technical Topic Notes (TTNs) produced in the Towards Identifying and closing Gaps in Assurance of autonomous Road vehicleS (Tigars) project. These notes aim to support the development and evaluation of autonomous vehicles. Part 1 addresses: Assurance-overview and issues, Resilience and Safety Requirements, Open Systems Perspective and Formal… ▽ More This report provides an introduction and overview of the Technical Topic Notes (TTNs) produced in the Towards Identifying and closing Gaps in Assurance of autonomous Road vehicleS (Tigars) project. These notes aim to support the development and evaluation of autonomous vehicles. Part 1 addresses: Assurance-overview and issues, Resilience and Safety Requirements, Open Systems Perspective and Formal Verification and Static Analysis of ML Systems. Part 2: Simulation and Dynamic Testing, Defence in Depth and Diversity, Security-Informed Safety Analysis, Standards and Guidelines. △ Less

Submitted 28 February, 2020; originally announced March 2020.

Comments: Authors of individual Topic Notes are indicated in the body of the report

Report number: Adelard Tigars D5.6 v2.0 (D/1259/138008/7)

Novelty Producing Synaptic Plasticity

Authors: Anil Yaman, Giovanni Iacca, Decebal Constantin Mocanu, George Fletcher, Mykola Pechenizkiy

Abstract: A learning process with the plasticity property often requires reinforcement signals to guide the process. However, in some tasks (e.g. maze-navigation), it is very difficult (or impossible) to measure the performance of an agent (i.e. a fitness value) to provide reinforcements since the position of the goal is not known. This requires finding the correct behavior among a vast number of possible b… ▽ More A learning process with the plasticity property often requires reinforcement signals to guide the process. However, in some tasks (e.g. maze-navigation), it is very difficult (or impossible) to measure the performance of an agent (i.e. a fitness value) to provide reinforcements since the position of the goal is not known. This requires finding the correct behavior among a vast number of possible behaviors without having the knowledge of the reinforcement signals. In these cases, an exhaustive search may be needed. However, this might not be feasible especially when optimizing artificial neural networks in continuous domains. In this work, we introduce novelty producing synaptic plasticity (NPSP), where we evolve synaptic plasticity rules to produce as many novel behaviors as possible to find the behavior that can solve the problem. We evaluate the NPSP on maze-navigation on deceptive maze environments that require complex actions and the achievement of subgoals to complete. Our results show that the search heuristic used with the proposed NPSP is indeed capable of producing much more novel behaviors in comparison with a random search taken as baseline. △ Less

Submitted 10 February, 2020; originally announced February 2020.

Evolving Plasticity for Autonomous Learning under Changing Environmental Conditions

Authors: Anil Yaman, Giovanni Iacca, Decebal Constantin Mocanu, Matt Coler, George Fletcher, Mykola Pechenizkiy

Abstract: A fundamental aspect of learning in biological neural networks is the plasticity property which allows them to modify their configurations during their lifetime. Hebbian learning is a biologically plausible mechanism for modeling the plasticity property in artificial neural networks (ANNs), based on the local interactions of neurons. However, the emergence of a coherent global learning behavior fr… ▽ More A fundamental aspect of learning in biological neural networks is the plasticity property which allows them to modify their configurations during their lifetime. Hebbian learning is a biologically plausible mechanism for modeling the plasticity property in artificial neural networks (ANNs), based on the local interactions of neurons. However, the emergence of a coherent global learning behavior from local Hebbian plasticity rules is not very well understood. The goal of this work is to discover interpretable local Hebbian learning rules that can provide autonomous global learning. To achieve this, we use a discrete representation to encode the learning rules in a finite search space. These rules are then used to perform synaptic changes, based on the local interactions of the neurons. We employ genetic algorithms to optimize these rules to allow learning on two separate tasks (a foraging and a prey-predator scenario) in online lifetime learning settings. The resulting evolved rules converged into a set of well-defined interpretable types, that are thoroughly discussed. Notably, the performance of these rules, while adapting the ANNs during the learning tasks, is comparable to that of offline learning methods such as hill climbing. △ Less

Submitted 7 December, 2020; v1 submitted 2 April, 2019; originally announced April 2019.

Comments: Evolutionary Computation Journal

Journal ref: Evolutionary Computation 1 25, 2020

Learning with Delayed Synaptic Plasticity

Authors: Anil Yaman, Giovanni Iacca, Decebal Constantin Mocanu, George Fletcher, Mykola Pechenizkiy

Abstract: The plasticity property of biological neural networks allows them to perform learning and optimize their behavior by changing their configuration. Inspired by biology, plasticity can be modeled in artificial neural networks by using Hebbian learning rules, i.e. rules that update synapses based on the neuron activations and reinforcement signals. However, the distal reward problem arises when the r… ▽ More The plasticity property of biological neural networks allows them to perform learning and optimize their behavior by changing their configuration. Inspired by biology, plasticity can be modeled in artificial neural networks by using Hebbian learning rules, i.e. rules that update synapses based on the neuron activations and reinforcement signals. However, the distal reward problem arises when the reinforcement signals are not available immediately after each network output to associate the neuron activations that contributed to receiving the reinforcement signal. In this work, we extend Hebbian plasticity rules to allow learning in distal reward cases. We propose the use of neuron activation traces (NATs) to provide additional data storage in each synapse to keep track of the activation of the neurons. Delayed reinforcement signals are provided after each episode relative to the networks' performance during the previous episode. We employ genetic algorithms to evolve delayed synaptic plasticity (DSP) rules and perform synaptic updates based on NATs and delayed reinforcement signals. We compare DSP with an analogous hill climbing algorithm that does not incorporate domain knowledge introduced with the NATs, and show that the synaptic updates performed by the DSP rules demonstrate more effective training performance relative to the HC algorithm. △ Less

Submitted 17 April, 2019; v1 submitted 22 March, 2019; originally announced March 2019.

Comments: GECCO2019

struc2gauss: Structural Role Preserving Network Embedding via Gaussian Embedding

Authors: Yulong Pei, Xin Du, Jianpeng Zhang, George Fletcher, Mykola Pechenizkiy

Abstract: Network embedding (NE) is playing a principal role in network mining, due to its ability to map nodes into efficient low-dimensional embedding vectors. However, two major limitations exist in state-of-the-art NE methods: role preservation and uncertainty modeling. Almost all previous methods represent a node into a point in space and focus on local structural information, i.e., neighborhood inform… ▽ More Network embedding (NE) is playing a principal role in network mining, due to its ability to map nodes into efficient low-dimensional embedding vectors. However, two major limitations exist in state-of-the-art NE methods: role preservation and uncertainty modeling. Almost all previous methods represent a node into a point in space and focus on local structural information, i.e., neighborhood information. However, neighborhood information does not capture global structural information and point vector representation fails in modeling the uncertainty of node representations. In this paper, we propose a new NE framework, struc2gauss, which learns node representations in the space of Gaussian distributions and performs network embedding based on global structural information. struc2gauss first employs a given node similarity metric to measure the global structural information, then generates structural context for nodes and finally learns node representations via Gaussian embedding. Different structural similarity measures of networks and energy functions of Gaussian embedding are investigated. Experiments conducted on real-world networks demonstrate that struc2gauss effectively captures global structural information while state-of-the-art network embedding methods fail to, outperforms other methods on the structure-based clustering and classification task and provides more information on uncertainties of node representations. △ Less

Submitted 30 September, 2020; v1 submitted 25 May, 2018; originally announced May 2018.

Limited Evaluation Cooperative Co-evolutionary Differential Evolution for Large-scale Neuroevolution

Authors: Anil Yaman, Decebal Constantin Mocanu, Giovanni Iacca, George Fletcher, Mykola Pechenizkiy

Abstract: Many real-world control and classification tasks involve a large number of features. When artificial neural networks (ANNs) are used for modeling these tasks, the network architectures tend to be large. Neuroevolution is an effective approach for optimizing ANNs; however, there are two bottlenecks that make their application challenging in case of high-dimensional networks using direct encoding. F… ▽ More Many real-world control and classification tasks involve a large number of features. When artificial neural networks (ANNs) are used for modeling these tasks, the network architectures tend to be large. Neuroevolution is an effective approach for optimizing ANNs; however, there are two bottlenecks that make their application challenging in case of high-dimensional networks using direct encoding. First, classic evolutionary algorithms tend not to scale well for searching large parameter spaces; second, the network evaluation over a large number of training instances is in general time-consuming. In this work, we propose an approach called the Limited Evaluation Cooperative Co-evolutionary Differential Evolution algorithm (LECCDE) to optimize high-dimensional ANNs. The proposed method aims to optimize the pre-synaptic weights of each post-synaptic neuron in different subpopulations using a Cooperative Co-evolutionary Differential Evolution algorithm, and employs a limited evaluation scheme where fitness evaluation is performed on a relatively small number of training instances based on fitness inheritance. We test LECCDE on three datasets with various sizes, and our results show that cooperative co-evolution significantly improves the test error comparing to standard Differential Evolution, while the limited evaluation scheme facilitates a significant reduction in computing time. △ Less

Submitted 6 May, 2018; v1 submitted 19 April, 2018; originally announced April 2018.

Comparing Downward Fragments of the Relational Calculus with Transitive Closure on Trees

Authors: Jelle Hellings, Marc Gyssens, Yuqing Wu, Dirk Van Gucht, Jan Van den Bussche, Stijn Vansummeren, George H. L. Fletcher

Abstract: Motivated by the continuing interest in the tree data model, we study the expressive power of downward navigational query languages on trees and chains. Basic navigational queries are built from the identity relation and edge relations using composition and union. We study the effects on relative expressiveness when we add transitive closure, projections, coprojections, intersection, and differenc… ▽ More Motivated by the continuing interest in the tree data model, we study the expressive power of downward navigational query languages on trees and chains. Basic navigational queries are built from the identity relation and edge relations using composition and union. We study the effects on relative expressiveness when we add transitive closure, projections, coprojections, intersection, and difference; this for boolean queries and path queries on labeled and unlabeled structures. In all cases, we present the complete Hasse diagram. In particular, we establish, for each query language fragment that we study on trees, whether it is closed under difference and intersection. △ Less

Submitted 4 March, 2018; originally announced March 2018.

G-CORE: A Core for Future Graph Query Languages

Authors: Renzo Angles, Marcelo Arenas, Pablo Barceló, Peter Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan Sequeda, Oskar van Rest, Hannes Voigt

Abstract: We report on a community effort between industry and academia to shape the future of graph query languages. We argue that existing graph database management systems should consider supporting a query language with two key characteristics. First, it should be composable, meaning, that graphs are the input and the output of queries. Second, the graph query language should treat paths as first-class… ▽ More We report on a community effort between industry and academia to shape the future of graph query languages. We argue that existing graph database management systems should consider supporting a query language with two key characteristics. First, it should be composable, meaning, that graphs are the input and the output of queries. Second, the graph query language should treat paths as first-class citizens. Our result is G-CORE, a powerful graph query language design that fulfills these goals, and strikes a careful balance between path query expressivity and evaluation complexity. △ Less

Submitted 6 December, 2017; v1 submitted 5 December, 2017; originally announced December 2017.

gMark: Schema-Driven Generation of Graphs and Queries

Authors: Guillaume Bagan, Angela Bonifati, Radu Ciucanu, George H. L. Fletcher, Aurélien Lemay, Nicky Advokaat

Abstract: Massive graph data sets are pervasive in contemporary application domains. Hence, graph database systems are becoming increasingly important. In the experimental study of these systems, it is vital that the research community has shared solutions for the generation of database instances and query workloads having predictable and controllable properties. In this paper, we present the design and eng… ▽ More Massive graph data sets are pervasive in contemporary application domains. Hence, graph database systems are becoming increasingly important. In the experimental study of these systems, it is vital that the research community has shared solutions for the generation of database instances and query workloads having predictable and controllable properties. In this paper, we present the design and engineering principles of gMark, a domain- and query language-independent graph instance and query workload generator. A core contribution of gMark is its ability to target and control the diversity of properties of both the generated instances and the generated workloads coupled to these instances. Further novelties include support for regular path queries, a fundamental graph query paradigm, and schema-driven selectivity estimation of queries, a key feature in controlling workload chokepoints. We illustrate the flexibility and practical usability of gMark by showcasing the framework's capabilities in generating high quality graphs and workloads, and its ability to encode user-defined schemas across a variety of application domains. △ Less

Submitted 6 December, 2016; v1 submitted 26 November, 2015; originally announced November 2015.

Comments: Accepted in November 2016. URL: http://ieeexplore.ieee.org/document/7762945/. in IEEE Transactions on Knowledge and Data Engineering 2017

Structural characterizations of the navigational expressiveness of relation algebras on a tree

Authors: George H. L. Fletcher, Marc Gyssens, Jan Paredaens, Dirk Van Gucht, Yuqing Wu

Abstract: Given a document D in the form of an unordered node-labeled tree, we study the expressiveness on D of various basic fragments of XPath, the core navigational language on XML documents. Working from the perspective of these languages as fragments of Tarski's relation algebra, we give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an expres… ▽ More Given a document D in the form of an unordered node-labeled tree, we study the expressiveness on D of various basic fragments of XPath, the core navigational language on XML documents. Working from the perspective of these languages as fragments of Tarski's relation algebra, we give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an expression in these algebras. Since each pair of nodes in such a relation represents a unique path in D, our results therefore capture the sets of paths in D definable in each of the fragments. We refer to this perspective on language semantics as the "global view." In contrast with this global view, there is also a "local view" where one is interested in the nodes to which one can navigate starting from a particular node in the document. In this view, we characterize when a set of nodes in D can be defined as the result of applying an expression to a given node of D. All these definability results, both in the global and the local view, are obtained by using a robust two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the respective fragments of XPath, and then bootstrapping these characterizations to the desired results. △ Less

Submitted 11 February, 2015; originally announced February 2015.

Comments: 58 Pages