OpenRaiser/Intern-Atlas huggingface dataset:
Semi-decentralized Inference in Heterogeneous Graph Neural Networks for Traffic Demand Forecasting: An Edge-Computing Approach
Venue: arXiv cs.LG 2023
Year: 2023

Prediction of taxi service demand and supply is essential for improving customer's experience and provider's profit. Recently, graph neural networks (GNNs) have been shown promising for this application. This approach models city regions as nodes in a transportation graph and their relations as edges. GNNs utilize local node features and the graph structure in the prediction. However, more efficient forecasting can still be achieved by following two main routes; enlarging the scale of the transportation graph, and simultaneously exploiting different types of nodes and edges in the graphs. However, both approaches are challenged by the scalability of GNNs. An immediate remedy to the scalability challenge is to decentralize the GNN operation. However, this creates excessive node-to-node communication. In this paper, we first characterize the excessive communication needs for the decentralized GNN approach. Then, we propose a semi-decentralized approach utilizing multiple cloudlets, moderately sized storage and computation devices, that can be integrated with the cellular base stations. This approach minimizes inter-cloudlet communication thereby alleviating the communication overhead of the decentralized approach while promoting scalability due to cloudlet-level decentralization. Also, we propose a heterogeneous GNN-LSTM algorithm for improved taxi-level demand and supply forecasting for handling dynamic taxi graphs where nodes are taxis. Extensive experiments over real data show the advantage of the semi-decentralized approach as tested over our heterogeneous GNN-LSTM algorithm. Also, the proposed semi-decentralized GNN approach is shown to reduce the overall inference time by about an order of magnitude compared to centralized and decentralized inference schemes.
Efficient Routing Algorithm Design for Large DetNet
Venue: arXiv cs.NI 2023
Year: 2023

Deterministic Networking (DetNet) is a rising technology that offers deterministic delay \& jitter and zero packet loss regardless of failures in large IP networks. In order to support DetNet, we must be able to find a set of low-cost routing paths for a given node pair subject to delay-range constraints. Unfortunately, the \textbf{Delay-Range} Constrained Routing (DRCR) problem is NP-Complete. Existing routing approaches either cannot support the delay-range constraints, or incur extremely high computational complexity. We propose Pulse$+$, a highly scalable and efficient DRCR problem solver. Pulse$+$ adopts a branch-and-bound methodology and optimizes its pruning strategies for higher efficiency. We also integrate Pulse$+$ with a divide-and-conquer approach and propose CoSE-Pulse$+$ to find a pair of active/backup paths that meet DetNet's delay-range and delay-diff constraints. Both Pulse$+$ and CoSE-Pulse$+$ offer optimality guarantee. Notably, although Pulse$+$ and CoSE-Pulse$+$ do not have a polynomial worst-case time complexity, their empirical performance is superior. We evaluate Pulse$+$ and CoSE-Pulse$+$ against the K-Shorst-Path and Lagrangian-dual based algorithms using synthetic test cases generated over networks with thousands of nodes and links. Both Pulse$+$ and CoSE-Pulse$+$ achieve significant speedup. To enable reproduction, we open source our code and test cases at [1].
Comparing Nodes of Multivariate Graphs Through Dynamic Layout Adaptations
Venue: arXiv cs.HC 2023
Year: 2023

Visual comparison is an important task in the analysis of multivariate graphs. However, comparison of topological features of a graph with respect to its data attributes for different portions of the data remains challenging because there is no single visual representation that would suit the dynamic nature of comparative analyses. To facilitate the visual comparison in node-link diagrams, we propose the comparison lens as a focus+context approach for dynamic layout adaptation. The core idea is to start with a topology-driven layout and locally inject an attribute-driven layout based on the multivariate similarity of node attributes. This facilitates comparison tasks on a local level while preserving the user's overall mental map of the graph topology. Additional visual enhancements, including color-coding, reduction of edge clutter, and radial guides, further support the comparison. To fit the lens to different comparison situations, it can be configured via user-controllable parameters. To demonstrate the utility of our approach, we use it for comparison in a real-world dataset of soccer players.
A linear time algorithm for linearizing quadratic and higher-order shortest path problems
Venue: arXiv cs.DS 2023
Year: 2023

An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.
The propagation game: on simulatability, correlation matrices, and probing security
Venue: arXiv cs.CR 2023
Year: 2023

This work is intended for researchers in the field of side-channel attacks, countermeasure analysis, and probing security. It reports on a formalization of simulatability in terms of categorical properties, which we think will provide a useful tool in the practitioner toolbox. The formalization allowed us to revisit some existing definitions (such as probe isolating non-interference) in a simpler way that corresponds to the propagation of \textit{erase morphisms} in the diagrammatic language of \prop{} categories. From a theoretical perspective, we shed light into probabilistic definitions of simulatability and matrix-based spectral approaches. This could mean, in practice, that potentially better tools can be built. Readers will find a different, and perhaps less contrived, definition of simulatability, which could enable new forms of reasoning. This work does not cover any practical implementation of the proposed tools, which is left for future work.
Reservoir Computing with Noise
Venue: arXiv cs.NE 2023
Year: 2023

This paper investigates in detail the effects of noise on the performance of reservoir computing. We focus on an application in which reservoir computers are used to learn the relationship between different state variables of a chaotic system. We recognize that noise can affect differently the training and testing phases. We find that the best performance of the reservoir is achieved when the strength of the noise that affects the input signal in the training phase equals the strength of the noise that affects the input signal in the testing phase. For all the cases we examined, we found that a good remedy to noise is to low-pass filter the input and the training/testing signals; this typically preserves the performance of the reservoir, while reducing the undesired effects of noise.
A Universal Question-Answering Platform for Knowledge Graphs
Venue: arXiv cs.AI 2023
Year: 2023

Knowledge from diverse application domains is organized as knowledge graphs (KGs) that are stored in RDF engines accessible in the web via SPARQL endpoints. Expressing a well-formed SPARQL query requires information about the graph structure and the exact URIs of its components, which is impractical for the average user. Question answering (QA) systems assist by translating natural language questions to SPARQL. Existing QA systems are typically based on application-specific human-curated rules, or require prior information, expensive pre-processing and model adaptation for each targeted KG. Therefore, they are hard to generalize to a broad set of applications and KGs. In this paper, we propose KGQAn, a universal QA system that does not need to be tailored to each target KG. Instead of curated rules, KGQAn introduces a novel formalization of question understanding as a text generation problem to convert a question into an intermediate abstract representation via a neural sequence-to-sequence model. We also develop a just-in-time linker that maps at query time the abstract representation to a SPARQL query for a specific KG, using only the publicly accessible APIs and the existing indices of the RDF store, without requiring any pre-processing. Our experiments with several real KGs demonstrate that KGQAn is easily deployed and outperforms by a large margin the state-of-the-art in terms of quality of answers and processing time, especially for arbitrary KGs, unseen during the training.
Guided Graph Generation: Evaluation of Graph Generators in Terms of Network Statistics, and a New Algorithm
Venue: arXiv cs.SI 2023
Year: 2023

We consider the problem of graph generation guided by network statistics, i.e., the generation of graphs which have given values of various numerical measures that characterize networks, such as the clustering coefficient and the number of cycles of given lengths. Algorithms for the generation of synthetic graphs are often based on graph growth models, i.e., rules of adding (and sometimes removing) nodes and edges to a graph that mimic the processes present in real-world networks. While such graph generators are desirable from a theoretical point of view, they are often only able to reproduce a narrow set of properties of real-world networks, resulting in graphs with otherwise unrealistic properties. In this article, we instead evaluate common graph generation algorithms at the task of reproducing the numerical statistics of real-world networks, such as the clustering coefficient, the degree assortativity, and the connectivity. We also propose an iterative algorithm, the Guided Graph Generator, based on a greedy-like procedure that recovers realistic values over a large number of commonly used graph statistics, while at the same time allowing an efficient implementation based on incremental updating of only a small number of subgraph counts. We show that the proposed algorithm outperforms previous graph generation algorithms in terms of the error in the reconstructed graphs for a large number of graph statistics such as the clustering coefficient, the assortativity, the mean node distance, and also evaluate the algorithm in terms of precision, speed of convergence and scalability, and compare it to previous graph generators and models. We also show that the proposed algorithm generates graphs with realistic degree distributions, graph spectra, clustering coefficient distributions, and distance distributions.
The position value as a centrality measure in social networks
Venue: arXiv cs.SI 2023
Year: 2023

The position value, introduced by Meessen (1988), is a solution concept for cooperative games in which the value assigned to a player depends on the value of the connections or links he has with other players. This concept has been studied by Borm et al. (1992) and characterised by Slikker (2005). In this paper, we analyse the position value from the point of view of the typical properties of a measure of centrality in a social network. We extend the analysis already developed in Gomez et al. (2003) for the Myerson centrality measure, where the symmetric effect on the centralities of the end nodes of an added or removed edge is a fundamental part of its characterisation. However, the Position centrality measure, unlike the Myerson centrality measure, responds in a more versatile way to such addition or elimination. After studying the aforementioned properties, we will focus on the analysis and characterisation of the Position attachment centrality given by the position value when the underlying game is the attachment game. Some comparisons are made with the attachment centrality introduced by Skibski et al. (2019).
READ Avatars: Realistic Emotion-controllable Audio Driven Avatars
Venue: arXiv cs.CV 2023
Year: 2023

We present READ Avatars, a 3D-based approach for generating 2D avatars that are driven by audio input with direct and granular control over the emotion. Previous methods are unable to achieve realistic animation due to the many-to-many nature of audio to expression mappings. We alleviate this issue by introducing an adversarial loss in the audio-to-expression generation process. This removes the smoothing effect of regression-based models and helps to improve the realism and expressiveness of the generated avatars. We note furthermore, that audio should be directly utilized when generating mouth interiors and that other 3D-based methods do not attempt this. We address this with audio-conditioned neural textures, which are resolution-independent. To evaluate the performance of our method, we perform quantitative and qualitative experiments, including a user study. We also propose a new metric for comparing how well an actor's emotion is reconstructed in the generated avatar. Our results show that our approach outperforms state of the art audio-driven avatar generation methods across several metrics. A demo video can be found at \url{https://youtu.be/QSyMl3vV0pA}
Building High-accuracy Multilingual ASR with Gated Language Experts and Curriculum Training
Venue: arXiv cs.CL 2023
Year: 2023

We propose gated language experts and curriculum training to enhance multilingual transformer transducer models without requiring language identification (LID) input from users during inference. Our method incorporates a gating mechanism and LID loss, enabling transformer experts to learn language-specific information. By combining gated transformer experts with shared transformer layers, we construct multilingual transformer blocks and utilize linear experts to effectively regularize the joint network. The curriculum training scheme leverages LID to guide the gated experts in improving their respective language performance. Experimental results on a bilingual task involving English and Spanish demonstrate significant improvements, with average relative word error reductions of 12.5% and 7.3% compared to the baseline bilingual and monolingual models, respectively. Notably, our method achieves performance comparable to the upper-bound model trained and inferred with oracle LID. Extending our approach to trilingual, quadrilingual, and pentalingual models reveals similar advantages to those observed in the bilingual models, highlighting its ease of extension to multiple languages.
Dynamic reconfiguration of component-based systems described by propositional configuration logic
Venue: arXiv cs.LO 2023
Year: 2023

We investigate dynamic reconfigurable component-based systems whose architectures are described by formulas of Propositional Configuration Logics. We present several examples of reconfigurable systems based on well-known architectures, and state preliminary decidability results.
SLAS: Speed and Lane Advisory System for Highway Navigation
Venue: arXiv cs.RO 2023
Year: 2023

This paper proposes a hierarchical autonomous vehicle navigation architecture, composed of a high-level speed and lane advisory system (SLAS) coupled with low-level trajectory generation and trajectory following modules. Specifically, we target a multi-lane highway driving scenario where an autonomous ego vehicle navigates in traffic. We propose a novel receding horizon mixed-integer optimization based method for SLAS with the objective to minimize travel time while accounting for passenger comfort. We further incorporate various modifications in the proposed approach to improve the overall computational efficiency and achieve real-time performance. We demonstrate the efficacy of the proposed approach in contrast to the existing methods, when applied in conjunction with state-of-the-art trajectory generation and trajectory following frameworks, in a CARLA simulation environment.
Implementing Active Learning in Cybersecurity: Detecting Anomalies in Redacted Emails
Venue: arXiv cs.HC 2023
Year: 2023

Research on email anomaly detection has typically relied on specially prepared datasets that may not adequately reflect the type of data that occurs in industry settings. In our research, at a major financial services company, privacy concerns prevented inspection of the bodies of emails and attachment details (although subject headings and attachment filenames were available). This made labeling possible anomalies in the resulting redacted emails more difficult. Another source of difficulty is the high volume of emails combined with the scarcity of resources making machine learning (ML) a necessity, but also creating a need for more efficient human training of ML models. Active learning (AL) has been proposed as a way to make human training of ML models more efficient. However, the implementation of Active Learning methods is a human-centered AI challenge due to potential human analyst uncertainty, and the labeling task can be further complicated in domains such as the cybersecurity domain (or healthcare, aviation, etc.) where mistakes in labeling can have highly adverse consequences. In this paper we present research results concerning the application of Active Learning to anomaly detection in redacted emails, comparing the utility of different methods for implementing active learning in this context. We evaluate different AL strategies and their impact on resulting model performance. We also examine how ratings of confidence that experts have in their labels can inform AL. The results obtained are discussed in terms of their implications for AL methodology and for the role of experts in model-assisted email anomaly screening.
Predicting IPv4 Services Across All Ports
Venue: arXiv cs.NI 2023
Year: 2023

Internet-wide scanning is commonly used to understand the topology and security of the Internet. However, IPv4 Internet scans have been limited to scanning only a subset of services -- exhaustively scanning all IPv4 services is too costly and no existing bandwidth-saving frameworks are designed to scan IPv4 addresses across all ports. In this work we introduce GPS, a system that efficiently discovers Internet services across all ports. GPS runs a predictive framework that learns from extremely small sample sizes and is highly parallelizable, allowing it to quickly find patterns between services across all 65K ports and a myriad of features. GPS computes service predictions in 13 minutes (four orders of magnitude faster than prior work) and finds 92.5% of services across all ports with 131x less bandwidth, and 204x more precision, compared to exhaustive scanning. GPS is the first work to show that, given at least two responsive IP addresses on a port to train from, predicting the majority of services across all ports is possible and practical.
Customer Churn Prediction Model using Explainable Machine Learning
Venue: arXiv cs.LG 2023
Year: 2023

It becomes a significant challenge to predict customer behavior and retain an existing customer with the rapid growth of digitization which opens up more opportunities for customers to choose from subscription-based products and services model. Since the cost of acquiring a new customer is five-times higher than retaining an existing customer, henceforth, there is a need to address the customer churn problem which is a major threat across the Industries. Considering direct impact on revenues, companies identify the factors that increases the customer churn rate. Here, key objective of the paper is to develop a unique Customer churn prediction model which can help to predict potential customers who are most likely to churn and such early warnings can help to take corrective measures to retain them. Here, we evaluated and analyzed the performance of various tree-based machine learning approaches and algorithms and identified the Extreme Gradient Boosting XGBOOST Classifier as the most optimal solution to Customer churn problem. To deal with such real-world problems, Paper emphasize the Model interpretability which is an important metric to help customers to understand how Churn Prediction Model is making predictions. In order to improve Model explainability and transparency, paper proposed a novel approach to calculate Shapley values for possible combination of features to explain which features are the most important/relevant features for a model to become highly interpretable, transparent and explainable to potential customers.
A deep learning-based approach for identifying unresolved questions on Stack Exchange Q&A communities through graph-based communication modelling
Venue: arXiv cs.SI 2023
Year: 2023

In recent years, online question-answering (Q&A) platforms, such as Stack Exchange (SE), have become increasingly popular as a source of information and knowledge sharing. Despite the vast amount of information available on these platforms, many questions remain unresolved. In this work, we aim to address this issue by proposing a novel approach to identify unresolved questions in SE Q&A communities. Our approach utilises the graph structure of communication formed around a question by users to model the communication network surrounding it. We employ a property graph model and graph neural networks (GNNs), which can effectively capture both the structure of communication and the content of messages exchanged among users. By leveraging the power of graph representation and GNNs, our approach can effectively identify unresolved questions in SE communities. Experimental results on the complete historical data from three distinct Q&A communities demonstrate the superiority of our proposed approach over baseline methods that only consider the content of questions. Finally, our work represents a first but important step towards better understanding the factors that can affect questions becoming and remaining unresolved in SE communities.
Ego-Vehicle Action Recognition based on Semi-Supervised Contrastive Learning
Venue: arXiv cs.CV 2023
Year: 2023

In recent years, many automobiles have been equipped with cameras, which have accumulated an enormous amount of video footage of driving scenes. Autonomous driving demands the highest level of safety, for which even unimaginably rare driving scenes have to be collected in training data to improve the recognition accuracy for specific scenes. However, it is prohibitively costly to find very few specific scenes from an enormous amount of videos. In this article, we show that proper video-to-video distances can be defined by focusing on ego-vehicle actions. It is well known that existing methods based on supervised learning cannot handle videos that do not fall into predefined classes, though they work well in defining video-to-video distances in the embedding space between labeled videos. To tackle this problem, we propose a method based on semi-supervised contrastive learning. We consider two related but distinct contrastive learning: standard graph contrastive learning and our proposed SOIA-based contrastive learning. We observe that the latter approach can provide more sensible video-to-video distances between unlabeled videos. Next, the effectiveness of our method is quantified by evaluating the classification performance of the ego-vehicle action recognition using HDD dataset, which shows that our method including unlabeled data in training significantly outperforms the existing methods using only labeled data in training.