OpenRaiser/Intern-Atlas huggingface dataset:
Nearly Tight Bounds For Differentially Private Min $s$-$t$ and Multiway Cut
Venue: arXiv cs.DS 2023
Year: 2023

Finding min $s$-$t$ cuts in graphs is a basic algorithmic tool with applications in image segmentation, community detection, reinforcement learning, and data clustering. In this problem, we are given two nodes as terminals, and the goal is to remove the smallest number of edges from the graph so that these two terminals are disconnected. We study the complexity of differential privacy for the min $s$-$t$ cut problem and show nearly tight lower and upper bounds where we achieve privacy at no cost for running time efficiency. We also develop a differentially private algorithm for the multiway $k$-cut problem, in which we are given $k$ nodes as terminals that we would like to disconnect. As a function of $k$, we obtain privacy guarantees that are exponentially more efficient than applying the advanced composition theorem to known algorithms for multiway $k$-cut. Finally, we empirically evaluate the approximation of our differentially private min $s$-$t$ cut algorithm and show that it almost matches the quality of the output of non-private ones.
Gaussian Mixture Proposals with Pull-Push Learning Scheme to Capture Diverse Events for Weakly Supervised Temporal Video Grounding
Venue: arXiv cs.CV 2023
Year: 2023

In the weakly supervised temporal video grounding study, previous methods use predetermined single Gaussian proposals which lack the ability to express diverse events described by the sentence query. To enhance the expression ability of a proposal, we propose a Gaussian mixture proposal (GMP) that can depict arbitrary shapes by learning importance, centroid, and range of every Gaussian in the mixture. In learning GMP, each Gaussian is not trained in a feature space but is implemented over a temporal location. Thus the conventional feature-based learning for Gaussian mixture model is not valid for our case. In our special setting, to learn moderately coupled Gaussian mixture capturing diverse events, we newly propose a pull-push learning scheme using pulling and pushing losses, each of which plays an opposite role to the other. The effects of components in our scheme are verified in-depth with extensive ablation studies and the overall scheme achieves state-of-the-art performance. Our code is available at https://github.com/sunoh-kim/pps.
Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners
Venue: arXiv cs.CG 2023
Year: 2023

In this paper, we present approximate distance and shortest-path oracles for fault-tolerant Euclidean spanners motivated by the routing problem in real-world road networks. An $f$-fault-tolerant Euclidean $t$-spanner for a set $V$ of $n$ points in $\mathbb{R}^d$ is a graph $G=(V,E)$ where, for any two points $p$ and $q$ in $V$ and a set $F$ of $f$ vertices of $V$, the distance between $p$ and $q$ in $G-F$ is at most $t$ times their Euclidean distance. Given an $f$-fault-tolerant Euclidean $t$-spanner $G$ with $O(n)$ edges and a constant $\varepsilon$, our data structure has size $O_{t,f}(n\log n)$, and this allows us to compute an $(1+\varepsilon)$-approximate distance in $G-F$ between $s$ and $s'$ can be computed in constant time for any two vertices $s$ and $s'$ and a set $F$ of $f$ failed vertices. Also, with a data structure of size $O_{t,f}(n\log n\log\log n)$, we can compute an $(1+\varepsilon)$-approximate shortest path in $G-F$ between $s$ and $s'$ in $O_{t,f}(\log^2 n\log\log n+\textsf{sol})$ time for any two vertices $s$ and $s'$ and a set $F$ of failed vertices, where $\textsf{sol}$ denotes the number of vertices in the returned path.
FCDNet: Frequency-Guided Complementary Dependency Modeling for Multivariate Time-Series Forecasting
Venue: arXiv cs.LG 2023
Year: 2023

Multivariate time-series (MTS) forecasting is a challenging task in many real-world non-stationary dynamic scenarios. In addition to intra-series temporal signals, the inter-series dependency also plays a crucial role in shaping future trends. How to enable the model's awareness of dependency information has raised substantial research attention. Previous approaches have either presupposed dependency constraints based on domain knowledge or imposed them using real-time feature similarity. However, MTS data often exhibit both enduring long-term static relationships and transient short-term interactions, which mutually influence their evolving states. It is necessary to recognize and incorporate the complementary dependencies for more accurate MTS prediction. The frequency information in time series reflects the evolutionary rules behind complex temporal dynamics, and different frequency components can be used to well construct long-term and short-term interactive dependency structures between variables. To this end, we propose FCDNet, a concise yet effective framework for multivariate time-series forecasting. Specifically, FCDNet overcomes the above limitations by applying two light-weight dependency constructors to help extract long- and short-term dependency information adaptively from multi-level frequency patterns. With the growth of input variables, the number of trainable parameters in FCDNet only increases linearly, which is conducive to the model's scalability and avoids over-fitting. Additionally, adopting a frequency-based perspective can effectively mitigate the influence of noise within MTS data, which helps capture more genuine dependencies. The experimental results on six real-world datasets from multiple fields show that FCDNet significantly exceeds strong baselines, with an average improvement of 6.82% on MAE, 4.98% on RMSE, and 4.91% on MAPE.
MolSets: Molecular Graph Deep Sets Learning for Mixture Property Modeling
Venue: arXiv cs.LG 2023
Year: 2023

Recent advances in machine learning (ML) have expedited materials discovery and design. One significant challenge faced in ML for materials is the expansive combinatorial space of potential materials formed by diverse constituents and their flexible configurations. This complexity is particularly evident in molecular mixtures, a frequently explored space for materials such as battery electrolytes. Owing to the complex structures of molecules and the sequence-independent nature of mixtures, conventional ML methods have difficulties in modeling such systems. Here we present MolSets, a specialized ML model for molecular mixtures. Representing individual molecules as graphs and their mixture as a set, MolSets leverages a graph neural network and the deep sets architecture to extract information at the molecule level and aggregate it at the mixture level, thus addressing local complexity while retaining global flexibility. We demonstrate the efficacy of MolSets in predicting the conductivity of lithium battery electrolytes and highlight its benefits in virtual screening of the combinatorial chemical space.
Federated Continual Learning via Knowledge Fusion: A Survey
Venue: arXiv cs.LG 2023
Year: 2023

Data privacy and silos are nontrivial and greatly challenging in many real-world applications. Federated learning is a decentralized approach to training models across multiple local clients without the exchange of raw data from client devices to global servers. However, existing works focus on a static data environment and ignore continual learning from streaming data with incremental tasks. Federated Continual Learning (FCL) is an emerging paradigm to address model learning in both federated and continual learning environments. The key objective of FCL is to fuse heterogeneous knowledge from different clients and retain knowledge of previous tasks while learning on new ones. In this work, we delineate federated learning and continual learning first and then discuss their integration, i.e., FCL, and particular FCL via knowledge fusion. In summary, our motivations are four-fold: we (1) raise a fundamental problem called ''spatial-temporal catastrophic forgetting'' and evaluate its impact on the performance using a well-known method called federated averaging (FedAvg), (2) integrate most of the existing FCL methods into two generic frameworks, namely synchronous FCL and asynchronous FCL, (3) categorize a large number of methods according to the mechanism involved in knowledge fusion, and finally (4) showcase an outlook on the future work of FCL.
Toward Methodical Discovery and Handling of Hidden Assumptions in Complex Systems and Models
Venue: arXiv cs.SE 2023
Year: 2023

Methodologies for development of complex systems and models include external reviews by domain and technology experts. Among others, such reviews can uncover undocumented built-in assumptions that may be critical for correct and safe operation or constrain applicability. Since such assumptions may still escape human-centered processes like reviews, agile development, and risk analyses, here, we contribute toward making this process more methodical and automatable. We first present a blueprint for a taxonomy and formalization of the problem. We then show that a variety of digital artifacts of the system or model can be automatically checked against extensive reference knowledge. Since mimicking the breadth and depth of knowledge and skills of experts may appear unattainable, we illustrate the basic feasibility of automation with rudimentary experiments using OpenAI's ChatGPT. We believe that systematic handling of this aspect of system engineering can contribute significantly to the quality and safety of complex systems and models, and to the efficiency of development projects. We dedicate this work to Werner Damm, whose contributions to modeling and model-based development, in industry and academia, with a special focus on safety, helped establish a solid foundation to our discipline and to the work of many scientists and professionals, including, naturally, the approaches and techniques described here.
FALCON: Feature-Label Constrained Graph Net Collapse for Memory Efficient GNNs
Venue: arXiv cs.LG 2023
Year: 2023

Graph Neural Network (GNN) ushered in a new era of machine learning with interconnected datasets. While traditional neural networks can only be trained on independent samples, GNN allows for the inclusion of inter-sample interactions in the training process. This gain, however, incurs additional memory cost, rendering most GNNs unscalable for real-world applications involving vast and complicated networks with tens of millions of nodes (e.g., social circles, web graphs, and brain graphs). This means that storing the graph in the main memory can be difficult, let alone training the GNN model with significantly less GPU memory. While much of the recent literature has focused on either mini-batching GNN methods or quantization, graph reduction methods remain largely scarce. Furthermore, present graph reduction approaches have several drawbacks. First, most graph reduction focuses only on the inference stage (e.g., condensation and distillation) and requires full graph GNN training, which does not reduce training memory footprint. Second, many methods focus solely on the graph's structural aspect, ignoring the initial population feature-label distribution, resulting in a skewed post-reduction label distribution. Here, we propose a Feature-Label COnstrained graph Net collapse, FALCON, to address these limitations. Our three core contributions lie in (i) designing FALCON, a topology-aware graph reduction technique that preserves feature-label distribution; (ii) implementation of FALCON with other memory reduction methods (i.e., mini-batched GNN and quantization) for further memory reduction; (iii) extensive benchmarking and ablation studies against SOTA methods to evaluate FALCON memory reduction. Our extensive results show that FALCON can significantly collapse various public datasets while achieving equal prediction quality across GNN models. Code: https://github.com/basiralab/FALCON
Enhancing Traffic Flow Prediction using Outlier-Weighted AutoEncoders: Handling Real-Time Changes
Venue: arXiv cs.LG 2023
Year: 2023

In today's urban landscape, traffic congestion poses a critical challenge, especially during outlier scenarios. These outliers can indicate abrupt traffic peaks, drops, or irregular trends, often arising from factors such as accidents, events, or roadwork. Moreover, Given the dynamic nature of traffic, the need for real-time traffic modeling also becomes crucial to ensure accurate and up-to-date traffic predictions. To address these challenges, we introduce the Outlier Weighted Autoencoder Modeling (OWAM) framework. OWAM employs autoencoders for local outlier detection and generates correlation scores to assess neighboring traffic's influence. These scores serve as a weighted factor for neighboring sensors, before fusing them into the model. This information enhances the traffic model's performance and supports effective real-time updates, a crucial aspect for capturing dynamic traffic patterns. OWAM demonstrates a favorable trade-off between accuracy and efficiency, rendering it highly suitable for real-world applications. The research findings contribute significantly to the development of more efficient and adaptive traffic prediction models, advancing the field of transportation management for the future. The code and datasets of our framework is publicly available under https://github.com/himanshudce/OWAM.
Beyond the Surface: Advanced Wash Trading Detection in Decentralized NFT Markets
Venue: arXiv cs.CE 2023
Year: 2023

Wash trading in decentralized markets remains a significant concern magnified by the pseudonymous and public nature of blockchains. In this paper we introduce an innovative methodology designed to detect wash trading activities beyond surface-level transactions. Our approach integrates NFT ownership traces with the Ethereum Transaction Network, encompassing the complete historical record of all Ethereum account normal transactions. By analyzing both networks, our method offers a notable advancement over techniques proposed by existing research. We analyzed the wash trading activity of 7 notable NFT collections. Our results show that wash trading in unregulated NFT markets is an underestimated concern and is much more widespread both in terms of frequency as well as volume. Excluding the Meebits collection, which emerged as an outlier, we found that wash trading constituted up to 25% of the total trading volume. Specifically, for the Meebits collection, a staggering 93% of its total trade volume was attributed to wash trading.
Twice Class Bias Correction for Imbalanced Semi-Supervised Learning
Venue: arXiv cs.LG 2023
Year: 2023

Differing from traditional semi-supervised learning, class-imbalanced semi-supervised learning presents two distinct challenges: (1) The imbalanced distribution of training samples leads to model bias towards certain classes, and (2) the distribution of unlabeled samples is unknown and potentially distinct from that of labeled samples, which further contributes to class bias in the pseudo-labels during training. To address these dual challenges, we introduce a novel approach called \textbf{T}wice \textbf{C}lass \textbf{B}ias \textbf{C}orrection (\textbf{TCBC}). We begin by utilizing an estimate of the class distribution from the participating training samples to correct the model, enabling it to learn the posterior probabilities of samples under a class-balanced prior. This correction serves to alleviate the inherent class bias of the model. Building upon this foundation, we further estimate the class bias of the current model parameters during the training process. We apply a secondary correction to the model's pseudo-labels for unlabeled samples, aiming to make the assignment of pseudo-labels across different classes of unlabeled samples as equitable as possible. Through extensive experimentation on CIFAR10/100-LT, STL10-LT, and the sizable long-tailed dataset SUN397, we provide conclusive evidence that our proposed TCBC method reliably enhances the performance of class-imbalanced semi-supervised learning.
Evolutionary Swarm Robotics: Dynamic Subgoal-Based Path Formation and Task Allocation for Exploration and Navigation in Unknown Environments
Venue: arXiv cs.RO 2023
Year: 2023

This research paper addresses the challenges of exploration and navigation in unknown environments from an evolutionary swarm robotics perspective. Path formation plays a crucial role in enabling cooperative swarm robots to accomplish these tasks. The paper presents a method called the sub-goal-based path formation, which establishes a path between two different locations by exploiting visually connected sub-goals. Simulation experiments conducted in the Argos simulator demonstrate the successful formation of paths in the majority of trials. Furthermore, the paper tackles the problem of inter-collision (traffic) among a large number of robots engaged in path formation, which negatively impacts the performance of the sub-goal-based method. To mitigate this issue, a task allocation strategy is proposed, leveraging local communication protocols and light signal-based communication. The strategy evaluates the distance between points and determines the required number of robots for the path formation task, reducing unwanted exploration and traffic congestion. The performance of the sub-goal-based path formation and task allocation strategy is evaluated by comparing path length, time, and resource reduction against the A* algorithm. The simulation experiments demonstrate promising results, showcasing the scalability, robustness, and fault tolerance characteristics of the proposed approach.
Exploring intra-task relations to improve meta-learning algorithms
Venue: arXiv cs.LG 2023
Year: 2023

Meta-learning has emerged as an effective methodology to model several real-world tasks and problems due to its extraordinary effectiveness in the low-data regime. There are many scenarios ranging from the classification of rare diseases to language modelling of uncommon languages where the availability of large datasets is rare. Similarly, for more broader scenarios like self-driving, an autonomous vehicle needs to be trained to handle every situation well. This requires training the ML model on a variety of tasks with good quality data. But often times, we find that the data distribution across various tasks is skewed, i.e.the data follows a long-tail distribution. This leads to the model performing well on some tasks and not performing so well on others leading to model robustness issues. Meta-learning has recently emerged as a potential learning paradigm which can effectively learn from one task and generalize that learning to unseen tasks. In this study, we aim to exploit external knowledge of task relations to improve training stability via effective mini-batching of tasks. We hypothesize that selecting a diverse set of tasks in a mini-batch will lead to a better estimate of the full gradient and hence will lead to a reduction of noise in training.
A pipeline for multiple orange detection and tracking with 3-D fruit relocalization and neural-net based yield regression in commercial citrus orchards
Venue: arXiv cs.CV 2023
Year: 2023

Traditionally, sweet orange crop forecasting has involved manually counting fruits from numerous trees, which is a labor-intensive process. Automatic systems for fruit counting, based on proximal imaging, computer vision, and machine learning, have been considered a promising alternative or complement to manual counting. These systems require data association components that prevent multiple counting of the same fruit observed in different images. However, there is a lack of work evaluating the accuracy of multiple fruit counting, especially considering (i) occluded and re-entering green fruits on leafy trees, and (ii) counting ground-truth data measured in the crop field. We propose a non-invasive alternative that utilizes fruit counting from videos, implemented as a pipeline. Firstly, we employ CNNs for the detection of visible fruits. Inter-frame association techniques are then applied to track the fruits across frames. To handle occluded and re-appeared fruit, we introduce a relocalization component that employs 3-D estimation of fruit locations. Finally, a neural network regressor is utilized to estimate the total number of fruit, integrating image-based fruit counting with other tree data such as crop variety and tree size. The results demonstrate that the performance of our approach is closely tied to the quality of the field-collected videos. By ensuring that at least 30% of the fruit is accurately detected, tracked, and counted, our yield regressor achieves an impressive coefficient of determination of 0.85. To the best of our knowledge, this study represents one of the few endeavors in fruit estimation that incorporates manual fruit counting as a reference point for evaluation. We also introduce annotated datasets for multiple orange tracking (MOrangeT) and detection (OranDet), publicly available to foster the development of novel methods for image-based fruit counting.
HMP: Hand Motion Priors for Pose and Shape Estimation from Video
Venue: arXiv cs.CV 2023
Year: 2023

Understanding how humans interact with the world necessitates accurate 3D hand pose estimation, a task complicated by the hand's high degree of articulation, frequent occlusions, self-occlusions, and rapid motions. While most existing methods rely on single-image inputs, videos have useful cues to address aforementioned issues. However, existing video-based 3D hand datasets are insufficient for training feedforward models to generalize to in-the-wild scenarios. On the other hand, we have access to large human motion capture datasets which also include hand motions, e.g. AMASS. Therefore, we develop a generative motion prior specific for hands, trained on the AMASS dataset which features diverse and high-quality hand motions. This motion prior is then employed for video-based 3D hand motion estimation following a latent optimization approach. Our integration of a robust motion prior significantly enhances performance, especially in occluded scenarios. It produces stable, temporally consistent results that surpass conventional single-frame methods. We demonstrate our method's efficacy via qualitative and quantitative evaluations on the HO3D and DexYCB datasets, with special emphasis on an occlusion-focused subset of HO3D. Code is available at https://hmp.is.tue.mpg.de
L-LO: Enhancing Pose Estimation Precision via a Landmark-Based LiDAR Odometry
Venue: arXiv cs.RO 2023
Year: 2023

The majority of existing LiDAR odometry solutions are based on simple geometric features such as points, lines or planes which cannot fully reflect the characteristics of surrounding environments. In this study, we propose a novel LiDAR odometry which effectively utilizes the overall exterior characteristics of environmental landmarks. The vehicle pose estimation is accomplished by means of two sequential pose estimation stages, namely, horizontal pose estimation and vertical pose estimation. To achieve effective landmark registration, a comprehensive index is proposed to evaluate the level of similarity between landmarks. This index takes into account two crucial aspects of landmarks, namely, dimension and shape in evaluating their similarity. To assess the performance of the proposed algorithm, we utilize the widely recognized KITTI dataset as well as experimental data collected by an unmanned ground vehicle platform. Both graphical and numerical results indicate that our algorithm outperforms leading LiDAR odometry solutions in terms of positioning accuracy.