Search

We study the influence minimization problem: given a graph $G$ and a seed set $S$, blocking at most $b$ nodes or $b$ edges such that the influence spread of the seed set is minimized. This is a pivotal yet underexplored aspect of network analytics, which can limit the spread of undesirable phenomena in networks, such as misinformation and epidemics. Given the inherent NP-hardness of the problem under the IC and LT models, previous studies have employed greedy algorithms and Monte Carlo Simulations for its resolution. However, existing techniques become cost-prohibitive when applied to large networks due to the necessity of enumerating all the candidate blockers and computing the decrease in expected spread from blocking each of them. This significantly restricts the practicality and effectiveness of existing methods, especially when prompt decision-making is crucial. In this paper, we propose the AdvancedGreedy algorithm, which utilizes a novel graph sampling technique that incorporates the dominator tree structure. We find that AdvancedGreedy can achieve a $(1-1/e-\epsilon)$-approximation in the problem under the LT model. Experimental evaluations on real-life networks reveal that our proposed algorithms exhibit a significant enhancement in efficiency, surpassing the state-of-the-art algorithm by three orders of magnitude, while achieving high effectiveness., Comment: arXiv admin note: substantial text overlap with arXiv:2302.13529

Individuals with suspected rare genetic disorders often undergo multiple clinical evaluations, imaging studies, laboratory tests and genetic tests, to find a possible answer over a prolonged period of time. Addressing this "diagnostic odyssey" thus has substantial clinical, psychosocial, and economic benefits. Many rare genetic diseases have distinctive facial features, which can be used by artificial intelligence algorithms to facilitate clinical diagnosis, in prioritizing candidate diseases to be further examined by lab tests or genetic assays, or in helping the phenotype-driven reinterpretation of genome/exome sequencing data. Existing methods using frontal facial photos were built on conventional Convolutional Neural Networks (CNNs), rely exclusively on facial images, and cannot capture non-facial phenotypic traits and demographic information essential for guiding accurate diagnoses. Here we introduce GestaltMML, a multimodal machine learning (MML) approach solely based on the Transformer architecture. It integrates facial images, demographic information (age, sex, ethnicity), and clinical notes (optionally, a list of Human Phenotype Ontology terms) to improve prediction accuracy. Furthermore, we also evaluated GestaltMML on a diverse range of datasets, including 528 diseases from the GestaltMatcher Database, several in-house datasets of Beckwith-Wiedemann syndrome (BWS, over-growth syndrome with distinct facial features), Sotos syndrome (overgrowth syndrome with overlapping features with BWS), NAA10-related neurodevelopmental syndrome, Cornelia de Lange syndrome (multiple malformation syndrome), and KBG syndrome (multiple malformation syndrome). Our results suggest that GestaltMML effectively incorporates multiple modalities of data, greatly narrowing candidate genetic diagnoses of rare diseases and may facilitate the reinterpretation of genome/exome sequencing data., Comment: Significant revisions

The emergence of on-demand ride pooling services allows each vehicle to serve multiple passengers at a time, thus increasing drivers' income and enabling passengers to travel at lower prices than taxi/car on-demand services (only one passenger can be assigned to a car at a time like UberX and Lyft). Although on-demand ride pooling services can bring so many benefits, ride pooling services need a well-defined matching strategy to maximize the benefits for all parties (passengers, drivers, aggregation companies and environment), in which the regional dispatching of vehicles has a significant impact on the matching and revenue. Existing algorithms often only consider revenue maximization, which makes it difficult for requests with unusual distribution to get a ride. How to increase revenue while ensuring a reasonable assignment of requests brings a challenge to ride pooling service companies (aggregation companies). In this paper, we propose a framework for vehicle dispatching for ride pooling tasks, which splits the city into discrete dispatching regions and uses the reinforcement learning (RL) algorithm to dispatch vehicles in these regions. We also consider the mutual information (MI) between vehicle and order distribution as the intrinsic reward of the RL algorithm to improve the correlation between their distributions, thus ensuring the possibility of getting a ride for unusually distributed requests. In experimental results on a real-world taxi dataset, we demonstrate that our framework can significantly increase revenue up to an average of 3\% over the existing best on-demand ride pooling method., Comment: Accepted by AAMAS 2024

The term "Reversal Curse" refers to the scenario where auto-regressive decoder large language models (LLMs), such as ChatGPT, trained on "A is B" fail to learn "B is A," assuming that B and A are distinct and can be uniquely identified from each other, demonstrating a basic failure of logical deduction. This raises a red flag in the use of GPT models for certain general tasks such as constructing knowledge graphs, considering their adherence to this symmetric principle. In our study, we examined a bidirectional LLM, BERT, and found that it is immune to the reversal curse. Driven by ongoing efforts to construct biomedical knowledge graphs with LLMs, we also embarked on evaluating more complex but essential deductive reasoning capabilities. This process included first training encoder and decoder language models to master the intersection and union operations on two sets and then moving on to assess their capability to infer different combinations of union and intersection operations on three newly created sets. The findings showed that while both encoder and decoder language models, trained for tasks involving two sets (union/intersection), were proficient in such scenarios, they encountered difficulties when dealing with operations that included three sets (various combinations of union and intersection). Our research highlights the distinct characteristics of encoder and decoder models in simple and complex logical reasoning. In practice, the choice between BERT and GPT should be guided by the specific requirements and nature of the task at hand, leveraging their respective strengths in bidirectional context comprehension and sequence prediction., Comment: Final revision. To appear in Patterns

Visual-language pre-training has achieved remarkable success in many multi-modal tasks, largely attributed to the availability of large-scale image-text datasets. In this work, we demonstrate that Multi-modal Large Language Models (MLLMs) can enhance visual-language representation learning by establishing richer image-text associations for image-text datasets. Our approach is simple, utilizing MLLMs to extend multiple diverse captions for each image. To prevent the bias introduced by MLLMs' hallucinations and monotonous language styles, we propose "text shearing" to maintain the quality and availability of extended captions. In image-text retrieval, without introducing additional training cost, our method consistently obtains 5.6 ~ 35.0 and 16.8 ~ 46.1 improvement on Recall@1 under the fine-tuning and zero-shot settings, respectively. Notably, we obtain zero-shot results that are comparable to fine-tuning on target datasets, which encourages more exploration of the versatile use of MLLMs.

Nonlocality is the defining feature of quantum entanglement. Entangled states with multiple particles are of crucial importance in fundamental tests of quantum physics as well as in many quantum information tasks. One of the archetypal multipartite quantum states, Greenberger-Horne-Zeilinger (GHZ) state, allows one to observe the striking conflict of quantum physics to local realism in the so-called all-versus-nothing way. This is profoundly different from Bell's theorem for two particles, which relies on statistical predictions. Here, we demonstrate an integrated photonic chip capable of generating and manipulating the four-photon GHZ state. We perform a complete characterization of the four-photon GHZ state using quantum state tomography and obtain a state fidelity of 0.729(6). We further use the all-versus-nothing test and the Mermin inequalities to witness the quantum nonlocality of GHZ entanglement. Our work paves the way to perform fundamental tests of quantum physics with complex integrated quantum devices., Comment: 10 pages, 3 figures

Effective user representations are pivotal in personalized advertising. However, stringent constraints on training throughput, serving latency, and memory, often limit the complexity and input feature set of online ads ranking models. This challenge is magnified in extensive systems like Meta's, which encompass hundreds of models with diverse specifications, rendering the tailoring of user representation learning for each model impractical. To address these challenges, we present Scaling User Modeling (SUM), a framework widely deployed in Meta's ads ranking system, designed to facilitate efficient and scalable sharing of online user representation across hundreds of ads models. SUM leverages a few designated upstream user models to synthesize user embeddings from massive amounts of user features with advanced modeling techniques. These embeddings then serve as inputs to downstream online ads ranking models, promoting efficient representation sharing. To adapt to the dynamic nature of user features and ensure embedding freshness, we designed SUM Online Asynchronous Platform (SOAP), a latency free online serving system complemented with model freshness and embedding stabilization, which enables frequent user model updates and online inference of user embeddings upon each user request. We share our hands-on deployment experiences for the SUM framework and validate its superiority through comprehensive experiments. To date, SUM has been launched to hundreds of ads ranking models in Meta, processing hundreds of billions of user requests daily, yielding significant online metric gains and improved infrastructure efficiency., Comment: 8 pages, 3 figures

Neural implicit representations have emerged as a promising solution for providing dense geometry in Simultaneous Localization and Mapping (SLAM). However, existing methods in this direction fall short in terms of global consistency and low latency. This paper presents NGEL-SLAM to tackle the above challenges. To ensure global consistency, our system leverages a traditional feature-based tracking module that incorporates loop closure. Additionally, we maintain a global consistent map by representing the scene using multiple neural implicit fields, enabling quick adjustment to the loop closure. Moreover, our system allows for fast convergence through the use of octree-based implicit representations. The combination of rapid response to loop closure and fast convergence makes our system a truly low-latency system that achieves global consistency. Our system enables rendering high-fidelity RGB-D images, along with extracting dense and complete surfaces. Experiments on both synthetic and real-world datasets suggest that our system achieves state-of-the-art tracking and mapping accuracy while maintaining low latency.

With the development of intelligent transportation systems, vehicles are exposed to a complex network environment. As the main network of in-vehicle networks, the controller area network (CAN) has many potential security hazards, resulting in higher requirements for intrusion detection systems to ensure safety. Among intrusion detection technologies, methods based on deep learning work best without prior expert knowledge. However, they all have a large model size and rely on cloud computing, and are therefore not suitable to be installed on the in-vehicle network. Therefore, we propose a lightweight parallel neural network structure, LiPar, to allocate task loads to multiple electronic control units (ECU). The LiPar model consists of multi-dimensional branch convolution networks, spatial and temporal feature fusion learning, and a resource adaptation algorithm. Through experiments, we prove that LiPar has great detection performance, running efficiency, and lightweight model size, which can be well adapted to the in-vehicle environment practically and protect the in-vehicle CAN bus security., Comment: 13 pages, 13 figures, 6 tables, 51 reference

The nucleus of almost all massive galaxies contains a supermassive black hole (BH). The feedback from the accretion of these BHs is often considered to have crucial roles in establishing the quiescence of massive galaxies, although some recent studies show that even galaxies hosting the most active BHs do not exhibit a reduction in their molecular gas reservoirs or star formation rates. Therefore, the influence of BHs on galaxy star formation remains highly debated and lacks direct evidence. Here, based on a large sample of nearby galaxies with measurements of masses of both BHs and atomic hydrogen (HI), the main component of the interstellar medium, we show that the HI gas mass to stellar masses ratio ($\mu_{\rm HI} = M_{\rm HI}/M_{\star}$) is more strongly correlated with BH masses ($M_{\rm BH}$) than with any other galaxy parameters, including stellar mass, stellar mass surface density and bulge masses. Moreover, once the $\mu_{\rm HI}-M_{\rm BH}$ correlation is considered, $\mu_{\rm HI}$ loses dependence on other galactic parameters, demonstrating that $M_{\rm BH}$ serves as the primary driver of $\mu_{\rm HI}$. These findings provide important evidence for how the accumulated energy from BH accretion regulates the cool gas content in galaxies, by ejecting interstellar medium gas and/or suppressing gas cooling from the circumgalactic medium., Comment: Published in Nature. Updated to match the accepted version

As an important component of internet of vehicles (IoV), intelligent connected vehicles (ICVs) have to communicate with external networks frequently. In this case, the resource-constrained in-vehicle network (IVN) is facing a wide variety of complex and changing external cyber-attacks, especially the masquerade attack with high difficulty of detection while serious damaging effects that few counter measures can identify successfully. Moreover, only coarse-grained recognition can be achieved in current mainstream intrusion detection mechanisms, i.e., whether a whole data flow observation window contains attack labels rather than fine-grained recognition on every single data item within this window. In this paper, we propose StatGraph: an Effective Multi-view Statistical Graph Learning Intrusion Detection to implement the fine-grained intrusion detection. Specifically, StatGraph generates two statistical graphs, timing correlation graph (TCG) and coupling relationship graph (CRG), based on data streams. In given message observation windows, edge attributes in TCGs represent temporal correlation between different message IDs, while edge attributes in CRGs denote the neighbour relationship and contextual similarity. Besides, a lightweight shallow layered GCN network is trained based graph property of TCGs and CRGs, which can learn the universal laws of various patterns more effectively and further enhance the performance of detection. To address the problem of insufficient attack types in previous intrusion detection, we select two real in-vehicle CAN datasets that cover four new attacks never investigated before. Experimental result shows StatGraph improves both detection granularity and detection performance over state-of-the-art intrusion detection methods., Comment: 14 pages, 8 figures, 6 tables, 27 references

Femtosecond laser pulses enable the synthesis of light across the electromagnetic spectrum and provide access to ultrafast phenomena in physics, biology, and chemistry. Chip-integration of femtosecond technology could revolutionize applications such as point-of-care diagnostics, bio-medical imaging, portable chemical sensing, or autonomous navigation. However, current chip-integrated pulse sources lack the required peak power and on-chip amplification of femtosecond pulses has been an unresolved challenge. Here, addressing this challenge, we report >50-fold amplification of 1 GHz-repetition-rate chirped femtosecond pulses in a CMOS-compatible photonic chip to 800 W peak power with 116 fs pulse duration. This power level is 2-3 orders of magnitude higher compared to those in previously demonstrated on-chip pulse sources and can provide the power needed to address key applications. To achieve this, detrimental nonlinear effects are mitigated through all-normal dispersion, large mode-area and rare-earth-doped gain waveguides. These results offer a pathway to chip-integrated femtosecond technology with peak power-levels characteristic of table-top sources., Comment: 15 pages, 7 figures

Automated creation of synthetic traffic scenarios is a key part of validating the safety of autonomous vehicles (AVs). In this paper, we propose Scenario Diffusion, a novel diffusion-based architecture for generating traffic scenarios that enables controllable scenario generation. We combine latent diffusion, object detection and trajectory regression to generate distributions of synthetic agent poses, orientations and trajectories simultaneously. To provide additional control over the generated scenario, this distribution is conditioned on a map and sets of tokens describing the desired scenario. We show that our approach has sufficient expressive capacity to model diverse traffic patterns and generalizes to different geographical regions., Comment: NeurIPS 2023

Visual object tracking is a fundamental component of transportation systems, especially for intelligent driving. Despite achieving state-of-the-art performance in visual tracking, recent single-branch trackers tend to overlook the weak prior assumptions associated with the Vision Transformer (ViT) encoder and inference pipeline in visual tracking. Moreover, the effectiveness of discriminative trackers remains constrained due to the adoption of the dual-branch pipeline. To tackle the inferior effectiveness of vanilla ViT, we propose an Adaptive ViT Model Prediction tracker (AViTMP) to design a customised tracking method. This method bridges the single-branch network with discriminative models for the first time. Specifically, in the proposed encoder AViT encoder, we introduce a tracking-tailored Adaptor module for vanilla ViT and a joint target state embedding to enrich the target-prior embedding paradigm. Then, we combine the AViT encoder with a discriminative transformer-specific model predictor to predict the accurate location. Furthermore, to mitigate the limitations of conventional inference practice, we present a novel inference pipeline called CycleTrack, which bolsters the tracking robustness in the presence of distractors via bidirectional cycle tracking verification. In the experiments, we evaluated AViTMP on eight tracking benchmarks for a comprehensive assessment, including LaSOT, LaSOTExtSub, AVisT, etc. The experimental results unequivocally establish that, under fair comparison, AViTMP achieves state-of-the-art performance, especially in terms of long-term tracking and robustness. The source code will be released at https://github.com/Tchuanm/AViTMP., Comment: IEEE Transactions on Intelligent Vehicles

Large-scale text-to-image diffusion models have been a ground-breaking development in generating convincing images following an input text prompt. The goal of image editing research is to give users control over the generated images by modifying the text prompt. Current image editing techniques predominantly hinge on DDIM inversion as a prevalent practice rooted in Latent Diffusion Models (LDM). However, the large pretrained T2I models working on the latent space suffer from losing details due to the first compression stage with an autoencoder mechanism. Instead, other mainstream T2I pipeline working on the pixel level, such as Imagen and DeepFloyd-IF, circumvents the above problem. They are commonly composed of multiple stages, typically starting with a text-to-image stage and followed by several super-resolution stages. In this pipeline, the DDIM inversion fails to find the initial noise and generate the original image given that the super-resolution diffusion models are not compatible with the DDIM technique. According to our experimental findings, iteratively concatenating the noisy image as the condition is the root of this problem. Based on this observation, we develop an iterative inversion (IterInv) technique for this category of T2I models and verify IterInv with the open-source DeepFloyd-IF model.Specifically, IterInv employ NTI as the inversion and reconstruction of low-resolution image generation. In stages 2 and 3, we update the latent variance at each timestep to find the deterministic inversion trace and promote the reconstruction process. By combining our method with a popular image editing method, we prove the application prospects of IterInv. The code will be released upon acceptance. The code is available at \url{https://github.com/Tchuanm/IterInv.git}., Comment: Accepted paper at ICME 2024