Juan L. Reutter

Urban transportation networks are recognized for their pivotal role in forecasting city indicators and facilitating efficient planning and management. However, despite the increase of methodologies and models harnessing machine learning advancement to forecast these values, challenges persist in scenarios where direct demographic or economic data are limited or unavailable. In this paper, we propose an approach to infer socioeconomic information in an urban context without relying on traditional, official data sources, but rather focusing on publicly available data relating to the digital footprints of the cities’ inhabitants. We leverage Graph Neural Network (GNN) models to capture the spatial relationships inherent in network data while integrating perceptual features extracted from images to enhance predictive accuracy. Our results demonstrate that the combination of these data sources enables a GNN to achieve robust performance in predicting socioeconomic indicators, particularly in settings where traditional demographic and economic data may be sparse or unavailable. Through our analysis, we show that while perceptual features alone offer substantial predictive power, the inclusion of map topology through GNN models provides crucial context, leading to better generalization and more reliable predictions across different urban areas.

In this paper we present TelarKG, a knowledge graph (KG) that consolidates multiple sources of information regarding the Chilean Constitutional process, particularly about the work of the members of the Constitutional Convention. TelarKG contains a wide range of public data, such as the materials from the commissions and information about the members' interventions and votes. In addition, the KG has been enriched with online user-generated content including posts from social networks related to the constitutional process, and transcriptions from the YouTube videos of the plenary sessions. Among other features, TelarKG leverages the semantic similarity search capabilities of the MillenniumDB endpoint to compute text similarity among convention members' Twitter messages. Additionally, we employ Entity Linking techniques to identify references to members of the Convention and Parties within these messages. TelarKG constitutes one of the most comprehensive historical archives on a political event, enabling users to query and navigate through diverse aspects of Chile's constitutional process.

Current knowledge graphs encompass diverse data formats, including images, text, tables, audio files, and videos. Additionally, the graph database ecosystem is required to support multiple co-existing data models. Addressing these challenges is essential for promoting interoperability between data sources. This demo introduces MillenniumDB, a high-performing, open-source graph database handling this diversity of data formats and models. MillenniumDB is a multi-modal, multi-model graph database, supporting the popular property graph paradigm, the Semantic Web format RDF, and the multi-layered graph model, which combines and extends the two. In terms of querying, its provides support for a Cypher-like language over property graphs and multilayered graphs, as well as SPARQL 1.1 support over RDF. The engine is build on a solid theoretical foundation and it leverages worst-case optimal join algorithms in combination with traditional relational query optimization. It also support a wide array of graph-specific tasks such as path finding, pattern recognition, and similarity search on multi-modal data. In this demo, we will showcase how MillenniumDB is currently being used to host three public multi-modal knowledge graphs. The first one, a multi-layered graph called TelarKG, was developed at IMFD Chile to track the information about the Chilean constitutional reform. In the second one, called BibKG, we integrate information about Computer Science publications from different sources and make them available as a property graph. Finally, for RDF, we provide a SPARQL endpoint for Wikidata, the largest knowledge graph openly available online. We remark that our endpoints have stable links, allowing the audience to post queries using their Web browser with no restrictions, and will be available during the review process and during the demo.

We present an indexing scheme for triple-based graphs that supports join queries in worst-case optimal (wco) time within compact space. This scheme, called a ring , regards each triple as a cyclic string of length 3. Each rotation of the triples is lexicographically sorted and the values of the last attribute are stored as a column, so we obtain the order of the next column by stably re-sorting the triples by its attribute. We show that, by representing the columns with a compact data structure called a wavelet tree, this ordering enables forward and backward navigation between columns without needing pointers. These wavelet trees further support wco join algorithms and cardinality estimations for query planning. While traditional data structures such as B-Trees, tries, and so on, require 6 index orders to support all possible wco joins over triples, we can use one ring to index them all. This ring replaces the graph and uses only sublinear extra space, thus supporting wco joins in almost no space beyond storing the graph itself. Experiments querying a large graph (Wikidata) in memory show that the ring offers nearly the best overall query times while using only a small fraction of the space required by several state-of-the-art approaches. We then turn our attention to some theoretical results for indexing tables of arity d higher than 3 in such a way that supports wco joins. While a single ring of length d no longer suffices to cover all d ! orders, we need much fewer rings to index them all: O (2 ^d ) rings with a small constant. For example, we need 5 rings instead of 120 orders for d =5. We show that our rings become a particular case of what we dub order graphs , whose nodes are attribute orders and where stably sorting by some attribute leads us from an order to another, thereby inducing an edge labeled by the attribute. The index is then the set of columns associated with the edges, and a set of rings is just one possible graph shape. We show that other shapes, like for example a single ring instead of several ones of length d , can lead us to even smaller indexes, and that other more general shapes are also possible. For example, we handle d =5 attributes within space equivalent to 4 rings.

We extend the concept of worst-case optimal equijoins in graph databases to the case where some nodes are required to be within the k-nearest neighbors (kNN) of others under some similarity function. We model the problem by superimposing the database graph with the kNN graph and show that a variant of Leapfrog TrieJoin (LTJ) implemented over a compact data structure called the Ring can be seamlessly extended to integrate similarity clauses with the equijoins in the LTJ query process, retaining worst-case optimality in many relevant cases. Our experiments on a benchmark that combines Wikidata and IMGpedia show that our enhanced LTJ algorithm outperforms by a considerable margin a baseline that first applies classic LTJ and then completes the query by applying the similarity predicates. The difference is more pronounced on queries where the similarity clauses are more densely connected to the query, becoming of an order of magnitude in some cases.

In this paper we survey our recent results characterizing various graph neural network (GNN) architectures in terms of their ability to classify nodes over graphs, for classifiers based on unary logical formulas- or queries. We focus on the language FOC2, a well-studied fragment of FO. This choice is motivated by the fact that FOC2 is related to theWeisfeiler-Lehman (WL) test for checking graph isomorphism, which has the same ability as GNNs for distinguishing nodes on graphs. We unveil the exact relationship between FOC2 and GNNs in terms of node classification. To tackle this problem, we start by studying a popular basic class of GNNs, which we call AC-GNNs, in which the features of each node in a graph are updated, in successive layers, according only to the features of its neighbors. We prove that the unary FOC2 formulas that can be captured by an AC-GNN are exactly those that can be expressed in its guarded fragment, which in turn corresponds to graded modal logic. This result implies in particular that ACGNNs are too weak to capture all FOC2 formulas. We then seek for what needs to be added to AC-GNNs for capturing all FOC2. We show that it suffices to add readouts layers, which allow updating the node features not only in terms of its neighbors, but also in terms of a global attribute vector. We call GNNs with readouts ACR-GNNs. We also describe experiments that validate our findings by showing that, on synthetic data conforming to FOC2 but not to graded modal logic, AC-GNNs struggle to fit in while ACR-GNNs can generalise even to graphs of sizes not seen during training.