Global flash floods, exacerbated by climate change, pose severe threats to humanlife, infrastructure, and the environment. Recent catastrophic events in Pakistan andNew Zealand underscore the urgent need for precise flood mapping to guide restoration efforts, understand vulnerabilities, and prepare for future occurrences. While Synthetic Aperture Radar (SAR) remote sensing offers day-and-night, all-weatherimaging capabilities, its application in deep learning for flood segmentation is limited by the lack of large annotated datasets. To address this, we introduce KuroSiwo, a manually annotated multi-temporal dataset, spanning 43 flood events globally. Our dataset maps more than 338 billion $m^2$ of land, with 33 billion designatedas either flooded areas or permanent water bodies. Kuro Siwo includes a highlyprocessed product optimized for flash flood mapping based on SAR Ground RangeDetected, and a primal SAR Single Look Complex product with minimal preprocessing, designed to promote research on the exploitation of both the phase and amplitude information and to offer maximum flexibility for downstream task preprocessing. To leverage advances in large scale self-supervised pretraining methodsfor remote sensing data, we augment Kuro Siwo with a large unlabeled set of SARsamples. Finally, we provide an extensive benchmark, namely BlackBench, offering strong baselines for a diverse set of flood events globally. All data and code arepublished in our Github repository: https://github.com/Orion-AI-Lab/KuroSiwo.

Abstract In the realm of online continual learning, models are expected to adapt to an ever-changing environment. One of the most persistent hurdles in this adaptation is the mitigation of a phenomenon called "Catastrophic Forgetting" (CF). This critical condition occurs when models trained on non-identically distributed data lose performance in previously learned tasks. Rehearsal methods, leveraging the ability to replay older samples, aim to address this challenge by incorporating a buffer of past training samples. However, the absence of known task boundaries complicates the adaptation of current CF mitigation methods. This paper proposes a method attuned to data stream characteristics and online model performance in a resource-constrained environment. The number of training iterations and learning rate emerges as crucial hyperparameters, impacting the efficacy and efficiency of online continual learning. Up to this point, we propose a combination of Experience Replay methodologies, a Drift Detector, and various training convergence policies, specially tailored for scenarios with unknown task boundaries. Experimental results demonstrate the effectiveness of our approach, maintaining or enhancing performance compared to baseline methods, while significantly improving computational efficiency.

Ground deformation measured from interferometric synthetic aperture radar (InSAR) data is considered a sign of volcanic unrest, statistically linked to a volcanic eruption. Recent studies have shown the potential of using Sentinel-1 InSAR data and supervised deep learning (DL) methods for the detection of volcanic deformation signals, toward global volcanic hazard mitigation. However, detection accuracy is compromised from the lack of labeled data and class imbalance. To overcome this, synthetic data are typically used for fine-tuning DL models pretrained on the ImageNet dataset. This approach suffers from poor generalization on real InSAR data. This letter proposes the use of self-supervised contrastive learning to learn quality visual representations hidden in unlabeled InSAR data. Our approach, based on the SimCLR framework, provides a solution that does not require a specialized architecture nor a large labeled or synthetic dataset. We show that our self-supervised pipeline achieves higher accuracy with respect to the state-of-the-art methods and shows excellent generalization even for out-of-distribution test data. Finally, we showcase the effectiveness of our approach for detecting the unrest episodes preceding the recent Icelandic Fagradalsfjall volcanic eruption.

The detection of early signs of volcanic unrest preceding an eruption, in the form of ground deformation in Interferometric Synthetic Aperture Radar (InSAR) data is critical for assessing volcanic hazard. In this work we treat this as a binary classification problem of InSAR images, and propose a novel deep learning methodology that exploits a rich source of synthetically generated interferograms to train quality classifiers that perform equally well in real interferograms. The imbalanced nature of the problem, with orders of magnitude fewer positive samples, coupled with the lack of a curated database with labeled InSAR data, sets a challenging task for conventional deep learning architectures. We propose a new framework for domain adaptation, in which we learn class prototypes from synthetic data with vision transformers. We report detection accuracy that amounts to the highest reported accuracy on a large test set for volcanic unrest detection. Moreover, we built upon this knowledge by learning a new, non-linear, projection between the learnt representations and prototype space, using pseudo labels produced by our model from an unlabeled real InSAR dataset. This leads to the new state of the art with 97.1% accuracy on our test set. We demonstrate the robustness of our approach by training a simple ResNet-18 Convolutional Neural Network on the unlabeled real InSAR dataset with pseudo-labels generated from our top transformer-prototype model. Our methodology provides a significant improvement in performance without the need of manually labeling any sample, opening the road for further exploitation of synthetic InSAR data in various remote sensing applications.

Mathematical software and graph-theoretical algorithmic packages to efficiently model, analyze, and query graphs are crucial in an era where large-scale spatial, societal, and economic network data are abundantly available. One such package is JGraphT, a programming library that contains very efficient and generic graph data structures along with a large collection of state-of-the-art algorithms. The library is written in Java with stability, interoperability, and performance in mind. A distinctive feature of this library is its ability to model vertices and edges as arbitrary objects, thereby permitting natural representations of many common networks, including transportation, social, and biological networks. Besides classic graph algorithms such as shortest-paths and spanning-tree algorithms, the library contains numerous advanced algorithms: graph and subgraph isomorphism, matching and flow problems, approximation algorithms for NP-hard problems such as independent set and the traveling salesman problem, and several more exotic algorithms such as Berge graph detection. Due to its versatility and generic design, JGraphT is currently used in large-scale commercial products, as well as noncommercial and academic research projects. In this work, we describe in detail the design and underlying structure of the library, and discuss its most important features and algorithms. A computational study is conducted to evaluate the performance of JGraphT versus several similar libraries. Experiments on a large number of graphs over a variety of popular algorithms show that JGraphT is highly competitive with other established libraries such as NetworkX or the BGL.

Graph matching is an important yet difficult task with many applications in bioinformatics, where it uncovers hidden relationships between species, network security, where it can be used for network de-anonymization, and computer vision, where it solves correspondence problems. When no side information is available, any graph matching algorithm must rely only on the structural information of the two input graphs in order to compute a mapping between the two node sets. One of the most scalable approaches for graph matching uses ideas from percolation theory, where already matched pairs ”infect” other neighbouring pairs. In the absence of any side information, such algorithms expect from the user to provide an initial set of pairs, the seeds, from which the percolation can start. In this paper, we propose DiNoiSe, a new distributed percolation graph matching algorithm, which employs the structural information of the network, but no initial seeds or any other node or edge labels. The algorithm takes advantage of the structural features of scale-free graphs (such as the ones behind social networks) and scales well for large networks, without using any additional input. We demonstrate the effectiveness of our algorithm via experiments on synthetic and real-world datasets.

Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest.

TELEIOS is a recent European project that addresses the need for scalable access to petabytes of Earth Observation data and the discovery and exploitation of knowledge that is hidden in them. TELEIOS builds on scientific database technologies (array databases, SciQL, data vaults) and Semantic Web technologies (stRDF and stSPARQL) implemented on top of a state of the art column store database system (MonetDB). We demonstrate a first prototype of the TELEIOS Virtual Earth Observatory (VEO) architecture, using a forest fire monitoring application as example.

We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) graph G with m edges, n vertices and nonnegative edge weights. In this problem, a {0, 1} (−1,0,1}) incidence vector is associated with each cycle and the vector space over F 2 (Q) generated by these vectors is the cycle space of G . A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G . Cycle bases of low weight are useful in a number of contexts, for example, the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. There exists a set of Θ( mn ) cycles which is guaranteed to contain a minimum cycle basis. A minimum basis can be extracted by Gaussian elimination. The resulting algorithm [Horton 1987] was the first polynomial-time algorithm. Faster and more complicated algorithms have been found since then. We present a very simple method for extracting a minimum cycle basis from the candidate set with running time O ( m 2 n ), which improves the running time for sparse graphs. Furthermore, in the undirected case by using bit-packing we improve the running time also in the case of dense graphs. For undirected graphs we derive an O ( m 2 n /log n + n 2 m ) algorithm. For directed graphs we get an O ( m 3 n ) deterministic and an O ( m 2 n ) randomized algorithm. Our results improve the running times of both exact and approximate algorithms. Finally, we derive a smaller candidate set with size in Ω( m ) ∩ O ( mn ).

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over $\mathbb{F}_{2}$ generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m 2 n+mn 2log n) algorithm. When the edge weights are integers, we have an O(m 2 n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ω ) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight.

An instance of the stable marriage problem is an undirected bipartite graph G = ( X ∪ W , E ) with linearly ordered adjacency lists with ties allowed in the ordering. A matching M is a set of edges, no two of which share an endpoint. An edge e = ( a , b ) ∈ E ∖ M is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M , and b is unmatched, strictly prefers a to its partner in M , or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We give an O ( nm ) algorithm for computing strongly stable matchings, where n is the number of vertices and m the number of edges. The previous best algorithm had running time O ( m 2 ). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an O ( m ∑ h∈H p h ) algorithm for computing a strongly stable matching in the hospitals-residents problem, where p h is the quota of a hospital h . The previous best algorithm had running time O ( m 2 ).

Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O (min( n + C , C √ n ) m ), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.