# Learning Concepts Described by Weight Aggregation Logic

arXiv: https://arxiv.org/abs/2009.10574 · HTML: https://mlsanity.com/paper/2009.10574/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2020.

## Built on by (most cited first, 4 of 4)

- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Query languages for neural networks](https://mlsanity.com/paper/2408.10362/) (2024)
- [Recursive querying of neural networks via weighted structures](https://mlsanity.com/paper/2601.03201/) (2026)
- [Query Languages for Machine-Learning Models](https://mlsanity.com/paper/2601.09381/) (2026)

## Abstract (arXiv)

We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of first-order logic that allows to aggregate weights of tuples, compare such aggregates, and use them to build more complex formulas. We provide locality properties of fragments of this logic including Feferman-Vaught decompositions and a Gaifman normal form for a fragment called FOW1, as well as a localisation theorem for a larger fragment called FOWA1. This fragment can express concepts from various machine learning scenarios. Using the locality properties, we show that concepts definable in FOWA1 over a weighted background structure of at most polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear time preprocessing.