Search

A graph G is c-closed if every two vertices with at least c common neighbors are adjacent to each other. Introduced by Fox, Roughgarden, Seshadhri, Wei and Wein [ICALP 2018, SICOMP 2020], this definition is an abstraction of the triadic closure property exhibited by many real-world social networks, namely, friends of friends tend to be friends themselves. Social networks, however, are often temporal rather than static -- the connections change over a period of time. And hence temporal graphs, rather than static graphs, are often better suited to model social networks. Motivated by this, we introduce a definition of temporal c-closed graphs, in which if two vertices u and v have at least c common neighbors during a short interval of time, then u and v are adjacent to each other around that time. Our pilot experiments show that several real-world temporal networks are c-closed for rather small values of c. We also study the computational problems of enumerating maximal cliques and similar dense subgraphs in temporal c-closed graphs; a clique in a temporal graph is a subgraph that lasts for a certain period of time, during which every possible edge in the subgraph becomes active often enough, and other dense subgraphs are defined similarly. We bound the number of such maximal dense subgraphs in a temporal c-closed graph that evolves slowly, and thus show that the corresponding enumeration problems admit efficient algorithms; by slow evolution, we mean that between consecutive time-steps, the local change in adjacencies remains small. Our work also adds to a growing body of literature on defining suitable structural parameters for temporal graphs that can be leveraged to design efficient algorithms., Comment: To appear in AAAI 2025

Geospatial Knowledge Graphs (GeoKGs) have become integral to the growing field of Geospatial Artificial Intelligence. Initiatives like the U.S. National Science Foundation's Open Knowledge Network program aim to create an ecosystem of nation-scale, cross-disciplinary GeoKGs that provide AI-ready geospatial data aligned with FAIR principles. However, building this infrastructure presents key challenges, including 1) managing large volumes of data, 2) the computational complexity of discovering topological relations via SPARQL, and 3) conflating multi-scale raster and vector data. Discrete Global Grid Systems (DGGS) help tackle these issues by offering efficient data integration and representation strategies. The KnowWhereGraph utilizes Google's S2 Geometry -- a DGGS framework -- to enable efficient multi-source data processing, qualitative spatial querying, and cross-graph integration. This paper outlines the implementation of S2 within KnowWhereGraph, emphasizing its role in topologically enriching and semantically compressing data. Ultimately, this work demonstrates the potential of DGGS frameworks, particularly S2, for building scalable GeoKGs.

KnowWhereGraph is one of the largest fully publicly available geospatial knowledge graphs. It includes data from 30 layers on natural hazards (e.g., hurricanes, wildfires), climate variables (e.g., air temperature, precipitation), soil properties, crop and land-cover types, demographics, and human health, various place and region identifiers, among other themes. These have been leveraged through the graph by a variety of applications to address challenges in food security and agricultural supply chains; sustainability related to soil conservation practices and farm labor; and delivery of emergency humanitarian aid following a disaster. In this paper, we introduce the ontology that acts as the schema for KnowWhereGraph. This broad overview provides insight into the requirements and design specifications for the graph and its schema, including the development methodology (modular ontology modeling) and the resources utilized to implement, materialize, and deploy KnowWhereGraph with its end-user interfaces and public query SPARQL endpoint.

Regional defaults describe the emerging phenomenon that text-to-image (T2I) foundation models used in generative AI are prone to over-proportionally depicting certain geographic regions to the exclusion of others. In this work, we introduce a scalable evaluation for uncovering such regional defaults. The evaluation consists of region hierarchy--based image generation and cross-level similarity comparisons. We carry out an experiment by prompting DALL-E 2, a state-of-the-art T2I generation model capable of generating photorealistic images, to depict a forest. We select forest as an object class that displays regional variation and can be characterized using spatial statistics. For a region in the hierarchy, our experiment reveals the regional defaults implicit in DALL-E 2, along with their scale-dependent nature and spatial relationships. In addition, we discover that the implicit defaults do not necessarily correspond to the most widely forested regions in reality. Our findings underscore a need for further investigation into the geography of T2I generation and other forms of generative AI., Comment: Accepted by the 16th Conference on Spatial Information Theory (COSIT 2024): https://cosit.ca

Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors in reporting, temporal graphs derived from data are unlikely to perfectly reflect reality, especially with respect to the precise times at which edges appear. To reflect this uncertainty, we consider a model in which some number $\zeta$ of edge appearances may have their timestamps perturbed by $\pm\delta$ for some $\delta$. Within this model, we investigate temporal reachability and consider the problem of determining the maximum number of vertices any vertex can reach under these perturbations. We show that this problem is intractable in general but is efficiently solvable when $\zeta$ is sufficiently large. We also give algorithms which solve this problem in several restricted settings. We complement this with some contrasting results concerning the complexity of related temporal eccentricity problems under perturbation., Comment: 36 pages, 3 figures

Temporal graphs provide a useful model for many real-world networks. Unfortunately the majority of algorithmic problems we might consider on such graphs are intractable. There has been recent progress in defining structural parameters which describe tractable cases by simultaneously restricting the underlying structure and the times at which edges appear in the graph. These all rely on the temporal graph being sparse in some sense. We introduce temporal analogues of three increasingly restrictive static graph parameters -- cliquewidth, modular-width and neighbourhood diversity -- which take small values for highly structured temporal graphs, even if a large number of edges are active at each timestep. The computational problems solvable efficiently when the temporal cliquewidth of the input graph is bounded form a subset of those solvable efficiently when the temporal modular-width is bounded, which is in turn a subset of problems efficiently solvable when the temporal neighbourhood diversity is bounded. By considering specific temporal graph problems, we demonstrate that (up to standard complexity theoretic assumptions) these inclusions are strict., Comment: 27 pages, 2 figures

Generative AI based on foundation models provides a first glimpse into the world represented by machines trained on vast amounts of multimodal data ingested by these models during training. If we consider the resulting models as knowledge bases in their own right, this may open up new avenues for understanding places through the lens of machines. In this work, we adopt this thinking and select GPT-4, a state-of-the-art representative in the family of multimodal large language models, to study its geographic diversity regarding how well geographic features are represented. Using DBpedia abstracts as a ground-truth corpus for probing, our natural language--based geo-guessing experiment shows that GPT-4 may currently encode insufficient knowledge about several geographic feature types on a global level. On a local level, we observe not only this insufficiency but also inter-regional disparities in GPT-4's geo-guessing performance on UNESCO World Heritage Sites that carry significance to both local and global populations, and the inter-regional disparities may become smaller as the geographic scale increases. Morever, whether assessing the geo-guessing performance on a global or local level, we find inter-model disparities in GPT-4's geo-guessing performance when comparing its unimodal and multimodal variants. We hope this work can initiate a discussion on geographic diversity as an ethical principle within the GIScience community in the face of global socio-technical challenges., Comment: Short paper accepted by AGILE 2024 conference (https://agile-gi.eu/conference-2024)

Superconducting RF cavities are used in particle accelerators to provide energy to the particle beam. Such cavities are mostly fabricated in niobium and often operated in superfluid helium. One of their limits of operation is the appearance of a local quench, initiated by a local field enhancement due to a defect, which leads to a normal conducting transition of the cavity. Localizing the quench area can be achieved with temperature mapping systems. Another method is the use of second sound wave propagation in superfluid helium. Measuring the time of propagation of these waves from quench location to special sensors, called Oscillating Superleak Transducers (OSTs), and using their well-known velocity should allow trilateration. However, most of experimental measurements on cavities show "premature signals", i.e. the second sound signals arrive earlier on the OSTs than expected. This paper presents several quench experiments on cavities equipped with OSTs and temperature mapping quench detection systems. Two hypotheses can explain the observed premature signals. The first one assesses faster propagation in helium. An experimental setup has been developed for testing this hypothesis, where second sound is created by a localized heater in a controlled environment up to 4.3 kW/cm2 and 2.8 J. Premature signals could not be verified in this setup. A second hypothesis based on a simple model including several processes in niobium and second sound propagation in helium is discussed. The model improves significantly the prediction of the times of arrival of the second sound waves. The overall study shows that the processes in niobium play a prominent role in the second sound detection for superconducting cavities., Comment: 12 pages, 22 images

We study {\sc Cluster Edge Modification} problems with constraints on the size of the clusters. A graph $G$ is a cluster graph if every connected component of $G$ is a clique. In a typical {\sc Cluster Edge Modification} problem such as the widely studied {\sc Cluster Editing}, we are given a graph $G$ and a non-negative integer $k$ as input, and we have to decide if we can turn $G$ into a cluster graph by way of at most $k$ edge modifications -- that is, by adding or deleting edges. In this paper, we study the parameterized complexity of such problems, but with an additional constraint: The size difference between any two connected components of the resulting cluster graph should not exceed a given threshold. Depending on which modifications are permissible -- only adding edges, only deleting edges, both adding and deleting edges -- we have three different computational problems. We show that all three problems, when parameterized by $k$, admit single-exponential time FPT algorithms and polynomial kernels. Our problems may be thought of as the size-constrained or balanced counterparts of the typical {\sc Cluster Edge Modification} problems, similar to the well-studied size-constrained or balanced counterparts of other clustering problems such as {\sc $k$-Means Clustering}.

Learning in general-sum games often yields collectively sub-optimal results. Addressing this, opponent shaping (OS) methods actively guide the learning processes of other agents, empirically leading to improved individual and group performances in many settings. Early OS methods use higher-order derivatives to shape the learning of co-players, making them unsuitable for shaping multiple learning steps. Follow-up work, Model-free Opponent Shaping (M-FOS), addresses these by reframing the OS problem as a meta-game. In contrast to early OS methods, there is little theoretical understanding of the M-FOS framework. Providing theoretical guarantees for M-FOS is hard because A) there is little literature on theoretical sample complexity bounds for meta-reinforcement learning B) M-FOS operates in continuous state and action spaces, so theoretical analysis is challenging. In this work, we present R-FOS, a tabular version of M-FOS that is more suitable for theoretical analysis. R-FOS discretises the continuous meta-game MDP into a tabular MDP. Within this discretised MDP, we adapt the $R_{max}$ algorithm, most prominently used to derive PAC-bounds for MDPs, as the meta-learner in the R-FOS algorithm. We derive a sample complexity bound that is exponential in the cardinality of the inner state and action space and the number of agents. Our bound guarantees that, with high probability, the final policy learned by an R-FOS agent is close to the optimal policy, apart from a constant factor. Finally, we investigate how R-FOS's sample complexity scales in the size of state-action space. Our theoretical results on scaling are supported empirically in the Matching Pennies environment.

While the paths humans take play out in social as well as physical space, measures to describe and compare their trajectories are carried out in abstract, typically Euclidean, space. When these measures are applied to trajectories of actual individuals in an application area, alterations that are inconsequential in abstract space may suddenly become problematic once overlaid with geographic reality. In this work, we present a different view on trajectory similarity by introducing a measure that utilizes logical entailment. This is an inferential perspective that considers facts as triple statements deduced from the social and environmental context in which the travel takes place, and their practical implications. We suggest a formalization of entailment-based trajectory similarity, measured as the overlapping proportion of facts, which are spatial relation statements in our case study. With the proposed measure, we evaluate LSTM-TrajGAN, a privacy-preserving trajectory-generation model. The entailment-based model evaluation reveals potential consequences of disregarding the rich structure of geographic space (e.g., miscalculated insurance risk due to regional shifts in our toy example). Our work highlights the advantage of applying logical entailment to trajectory-similarity reasoning for location-privacy protection and beyond.

The current best practice approach for the retrospective diagnosis of adverse drug events (ADEs) in hospitalized patients relies on a full patient chart review and a formal causality assessment by multiple medical experts. This evaluation serves to qualitatively estimate the probability of causation (PC); the probability that a drug was a necessary cause of an adverse event. This practice is manual, resource intensive and prone to human biases, and may thus benefit from data-driven decision support. Here, we pioneer a causal modeling approach using observational data to estimate a lower bound of the PC (PC$_{low}$). This method includes two key causal inference components: (1) the target trial emulation framework and (2) estimation of individualized treatment effects using machine learning. We apply our method to the clinically relevant use-case of vancomycin-induced acute kidney injury in intensive care patients, and compare our causal model-based PC$_{low}$ estimates to qualitative estimates of the PC provided by a medical expert. Important limitations and potential improvements are discussed, and we conclude that future improved causal models could provide essential data-driven support for medication safety monitoring in hospitalized patients., Comment: Extended Abstract presented at Machine Learning for Health (ML4H) symposium 2023, December 10th, 2023, New Orleans, United States, 14 pages