-
LLM-assisted Concept Discovery: Automatically Identifying and Explaining Neuron Functions
Authors:
Nhat Hoang-Xuan,
Minh Vu,
My T. Thai
Abstract:
Providing textual concept-based explanations for neurons in deep neural networks (DNNs) is of importance in understanding how a DNN model works. Prior works have associated concepts with neurons based on examples of concepts or a pre-defined set of concepts, thus limiting possible explanations to what the user expects, especially in discovering new concepts. Furthermore, defining the set of concep…
▽ More
Providing textual concept-based explanations for neurons in deep neural networks (DNNs) is of importance in understanding how a DNN model works. Prior works have associated concepts with neurons based on examples of concepts or a pre-defined set of concepts, thus limiting possible explanations to what the user expects, especially in discovering new concepts. Furthermore, defining the set of concepts requires manual work from the user, either by directly specifying them or collecting examples. To overcome these, we propose to leverage multimodal large language models for automatic and open-ended concept discovery. We show that, without a restricted set of pre-defined concepts, our method gives rise to novel interpretable concepts that are more faithful to the model's behavior. To quantify this, we validate each concept by generating examples and counterexamples and evaluating the neuron's response on this new set of images. Collectively, our method can discover concepts and simultaneously validate them, providing a credible automated tool to explain deep neural networks.
△ Less
Submitted 12 June, 2024;
originally announced June 2024.
-
CHARME: A chain-based reinforcement learning approach for the minor embedding problem
Authors:
Hoang M. Ngo,
Nguyen H K. Do,
Minh N. Vu,
Tamer Kahveci,
My T. Thai
Abstract:
Quantum Annealing (QA) holds great potential for solving combinatorial optimization problems efficiently. However, the effectiveness of QA algorithms heavily relies on the embedding of problem instances, represented as logical graphs, into the quantum unit processing (QPU) whose topology is in form of a limited connectivity graph, known as the minor embedding Problem. Existing methods for the mino…
▽ More
Quantum Annealing (QA) holds great potential for solving combinatorial optimization problems efficiently. However, the effectiveness of QA algorithms heavily relies on the embedding of problem instances, represented as logical graphs, into the quantum unit processing (QPU) whose topology is in form of a limited connectivity graph, known as the minor embedding Problem. Existing methods for the minor embedding problem suffer from scalability issues when confronted with larger problem sizes. In this paper, we propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm ensuring solution validity, and an order exploration strategy for effective training. Through comprehensive experiments on synthetic and real-world instances, we demonstrate that the efficiency of our proposed order exploration strategy as well as our proposed RL framework, CHARME. In details, CHARME yields superior solutions compared to fast embedding methods such as Minorminer and ATOM. Moreover, our method surpasses the OCT-based approach, known for its slower runtime but high-quality solutions, in several cases. In addition, our proposed exploration enhances the efficiency of the training of the CHARME framework by providing better solutions compared to the greedy strategy.
△ Less
Submitted 11 June, 2024;
originally announced June 2024.
-
DS@BioMed at ImageCLEFmedical Caption 2024: Enhanced Attention Mechanisms in Medical Caption Generation through Concept Detection Integration
Authors:
Nhi Ngoc-Yen Nguyen,
Le-Huy Tu,
Dieu-Phuong Nguyen,
Nhat-Tan Do,
Minh Triet Thai,
Bao-Thien Nguyen-Tat
Abstract:
Purpose: Our study presents an enhanced approach to medical image caption generation by integrating concept detection into attention mechanisms. Method: This method utilizes sophisticated models to identify critical concepts within medical images, which are then refined and incorporated into the caption generation process. Results: Our concept detection task, which employed the Swin-V2 model, achi…
▽ More
Purpose: Our study presents an enhanced approach to medical image caption generation by integrating concept detection into attention mechanisms. Method: This method utilizes sophisticated models to identify critical concepts within medical images, which are then refined and incorporated into the caption generation process. Results: Our concept detection task, which employed the Swin-V2 model, achieved an F1 score of 0.58944 on the validation set and 0.61998 on the private test set, securing the third position. For the caption prediction task, our BEiT+BioBart model, enhanced with concept integration and post-processing techniques, attained a BERTScore of 0.60589 on the validation set and 0.5794 on the private test set, placing ninth. Conclusion: These results underscore the efficacy of concept-aware algorithms in generating precise and contextually appropriate medical descriptions. The findings demonstrate that our approach significantly improves the quality of medical image captions, highlighting its potential to enhance medical image interpretation and documentation, thereby contributing to improved healthcare outcomes.
△ Less
Submitted 1 June, 2024;
originally announced June 2024.
-
Analysis of Privacy Leakage in Federated Large Language Models
Authors:
Minh N. Vu,
Truc Nguyen,
Tre' R. Jeter,
My T. Thai
Abstract:
With the rapid adoption of Federated Learning (FL) as the training and tuning protocol for applications utilizing Large Language Models (LLMs), recent research highlights the need for significant modifications to FL to accommodate the large-scale of LLMs. While substantial adjustments to the protocol have been introduced as a response, comprehensive privacy analysis for the adapted FL protocol is…
▽ More
With the rapid adoption of Federated Learning (FL) as the training and tuning protocol for applications utilizing Large Language Models (LLMs), recent research highlights the need for significant modifications to FL to accommodate the large-scale of LLMs. While substantial adjustments to the protocol have been introduced as a response, comprehensive privacy analysis for the adapted FL protocol is currently lacking.
To address this gap, our work delves into an extensive examination of the privacy analysis of FL when used for training LLMs, both from theoretical and practical perspectives. In particular, we design two active membership inference attacks with guaranteed theoretical success rates to assess the privacy leakages of various adapted FL configurations. Our theoretical findings are translated into practical attacks, revealing substantial privacy vulnerabilities in popular LLMs, including BERT, RoBERTa, DistilBERT, and OpenAI's GPTs, across multiple real-world language datasets. Additionally, we conduct thorough experiments to evaluate the privacy leakage of these models when data is protected by state-of-the-art differential privacy (DP) mechanisms.
△ Less
Submitted 2 March, 2024;
originally announced March 2024.
-
MIM-Reasoner: Learning with Theoretical Guarantees for Multiplex Influence Maximization
Authors:
Nguyen Do,
Tanmoy Chowdhury,
Chen Ling,
Liang Zhao,
My T. Thai
Abstract:
Multiplex influence maximization (MIM) asks us to identify a set of seed users such as to maximize the expected number of influenced users in a multiplex network. MIM has been one of central research topics, especially in nowadays social networking landscape where users participate in multiple online social networks (OSNs) and their influences can propagate among several OSNs simultaneously. Altho…
▽ More
Multiplex influence maximization (MIM) asks us to identify a set of seed users such as to maximize the expected number of influenced users in a multiplex network. MIM has been one of central research topics, especially in nowadays social networking landscape where users participate in multiple online social networks (OSNs) and their influences can propagate among several OSNs simultaneously. Although there exist a couple combinatorial algorithms to MIM, learning-based solutions have been desired due to its generalization ability to heterogeneous networks and their diversified propagation characteristics. In this paper, we introduce MIM-Reasoner, coupling reinforcement learning with probabilistic graphical model, which effectively captures the complex propagation process within and between layers of a given multiplex network, thereby tackling the most challenging problem in MIM. We establish a theoretical guarantee for MIM-Reasoner as well as conduct extensive analyses on both synthetic and real-world datasets to validate our MIM-Reasoner's performance.
△ Less
Submitted 10 March, 2024; v1 submitted 23 February, 2024;
originally announced February 2024.
-
Smart Textile-Driven Soft Spine Exosuit for Lifting Tasks in Industrial Applications
Authors:
Kefan Zhu,
Bibhu Sharma,
Phuoc Thien Phan,
James Davies,
Mai Thanh Thai,
Trung Thien Hoang,
Chi Cong Nguyen,
Adrienne Ji,
Emanuele Nicotra,
Nigel H. Lovell,
Thanh Nho Do
Abstract:
Work related musculoskeletal disorders (WMSDs) are often caused by repetitive lifting, making them a significant concern in occupational health. Although wearable assist devices have become the norm for mitigating the risk of back pain, most spinal assist devices still possess a partially rigid structure that impacts the user comfort and flexibility. This paper addresses this issue by presenting a…
▽ More
Work related musculoskeletal disorders (WMSDs) are often caused by repetitive lifting, making them a significant concern in occupational health. Although wearable assist devices have become the norm for mitigating the risk of back pain, most spinal assist devices still possess a partially rigid structure that impacts the user comfort and flexibility. This paper addresses this issue by presenting a smart textile actuated spine assistance robotic exosuit (SARE), which can conform to the back seamlessly without impeding the user movement and is incredibly lightweight. The SARE can assist the human erector spinae to complete any action with virtually infinite degrees of freedom. To detect the strain on the spine and to control the smart textile automatically, a soft knitting sensor which utilizes fluid pressure as sensing element is used. The new device is validated experimentally with human subjects where it reduces peak electromyography (EMG) signals of lumbar erector spinae by around 32 percent in loaded and around 22 percent in unloaded conditions. Moreover, the integrated EMG decreased by around 24.2 percent under loaded condition and around 23.6 percent under unloaded condition. In summary, the artificial muscle wearable device represents an anatomical solution to reduce the risk of muscle strain, metabolic energy cost and back pain associated with repetitive lifting tasks.
△ Less
Submitted 3 February, 2024;
originally announced February 2024.
-
OnDev-LCT: On-Device Lightweight Convolutional Transformers towards federated learning
Authors:
Chu Myaet Thwal,
Minh N. H. Nguyen,
Ye Lin Tun,
Seong Tae Kim,
My T. Thai,
Choong Seon Hong
Abstract:
Federated learning (FL) has emerged as a promising approach to collaboratively train machine learning models across multiple edge devices while preserving privacy. The success of FL hinges on the efficiency of participating models and their ability to handle the unique challenges of distributed learning. While several variants of Vision Transformer (ViT) have shown great potential as alternatives…
▽ More
Federated learning (FL) has emerged as a promising approach to collaboratively train machine learning models across multiple edge devices while preserving privacy. The success of FL hinges on the efficiency of participating models and their ability to handle the unique challenges of distributed learning. While several variants of Vision Transformer (ViT) have shown great potential as alternatives to modern convolutional neural networks (CNNs) for centralized training, the unprecedented size and higher computational demands hinder their deployment on resource-constrained edge devices, challenging their widespread application in FL. Since client devices in FL typically have limited computing resources and communication bandwidth, models intended for such devices must strike a balance between model size, computational efficiency, and the ability to adapt to the diverse and non-IID data distributions encountered in FL. To address these challenges, we propose OnDev-LCT: Lightweight Convolutional Transformers for On-Device vision tasks with limited training data and resources. Our models incorporate image-specific inductive biases through the LCT tokenizer by leveraging efficient depthwise separable convolutions in residual linear bottleneck blocks to extract local features, while the multi-head self-attention (MHSA) mechanism in the LCT encoder implicitly facilitates capturing global representations of images. Extensive experiments on benchmark image datasets indicate that our models outperform existing lightweight vision models while having fewer parameters and lower computational demands, making them suitable for FL scenarios with data heterogeneity and communication bottlenecks.
△ Less
Submitted 21 January, 2024;
originally announced January 2024.
-
OASIS: Offsetting Active Reconstruction Attacks in Federated Learning
Authors:
Tre' R. Jeter,
Truc Nguyen,
Raed Alharbi,
My T. Thai
Abstract:
Federated Learning (FL) has garnered significant attention for its potential to protect user privacy while enhancing model training efficiency. For that reason, FL has found its use in various domains, from healthcare to industrial engineering, especially where data cannot be easily exchanged due to sensitive information or privacy laws. However, recent research has demonstrated that FL protocols…
▽ More
Federated Learning (FL) has garnered significant attention for its potential to protect user privacy while enhancing model training efficiency. For that reason, FL has found its use in various domains, from healthcare to industrial engineering, especially where data cannot be easily exchanged due to sensitive information or privacy laws. However, recent research has demonstrated that FL protocols can be easily compromised by active reconstruction attacks executed by dishonest servers. These attacks involve the malicious modification of global model parameters, allowing the server to obtain a verbatim copy of users' private data by inverting their gradient updates. Tackling this class of attack remains a crucial challenge due to the strong threat model. In this paper, we propose a defense mechanism, namely OASIS, based on image augmentation that effectively counteracts active reconstruction attacks while preserving model performance. We first uncover the core principle of gradient inversion that enables these attacks and theoretically identify the main conditions by which the defense can be robust regardless of the attack strategies. We then construct our defense with image augmentation showing that it can undermine the attack principle. Comprehensive evaluations demonstrate the efficacy of the defense mechanism highlighting its feasibility as a solution.
△ Less
Submitted 3 June, 2024; v1 submitted 22 November, 2023;
originally announced November 2023.
-
On the Communication Complexity of Decentralized Bilevel Optimization
Authors:
Yihan Zhang,
My T. Thai,
Jie Wu,
Hongchang Gao
Abstract:
Stochastic bilevel optimization finds widespread applications in machine learning, including meta-learning, hyperparameter optimization, and neural architecture search. To extend stochastic bilevel optimization to distributed data, several decentralized stochastic bilevel optimization algorithms have been developed. However, existing methods often suffer from slow convergence rates and high commun…
▽ More
Stochastic bilevel optimization finds widespread applications in machine learning, including meta-learning, hyperparameter optimization, and neural architecture search. To extend stochastic bilevel optimization to distributed data, several decentralized stochastic bilevel optimization algorithms have been developed. However, existing methods often suffer from slow convergence rates and high communication costs in heterogeneous settings, limiting their applicability to real-world tasks. To address these issues, we propose two novel decentralized stochastic bilevel gradient descent algorithms based on simultaneous and alternating update strategies. Our algorithms can achieve faster convergence rates and lower communication costs than existing methods. Importantly, our convergence analyses do not rely on strong assumptions regarding heterogeneity. More importantly, our theoretical analysis clearly discloses how the additional communication required for estimating hypergradient under the heterogeneous setting affects the convergence rate. To the best of our knowledge, this is the first time such favorable theoretical results have been achieved with mild assumptions in the heterogeneous setting. Furthermore, we demonstrate how to establish the convergence rate for the alternating update strategy when combined with the variance-reduced gradient. Finally, experimental results confirm the efficacy of our algorithms.
△ Less
Submitted 1 June, 2024; v1 submitted 19 November, 2023;
originally announced November 2023.
-
QOMIC: Quantum optimization for motif identification
Authors:
Hoang M. Ngo,
Tamim Khatib,
My T. Thai,
Tamer Kahveci
Abstract:
Network motif identification problem aims to find topological patterns in biological networks. Identifying non-overlapping motifs is a computationally challenging problem using classical computers. Quantum computers enable solving high complexity problems which do not scale using classical computers. In this paper, we develop the first quantum solution, called QOMIC (Quantum Optimization for Motif…
▽ More
Network motif identification problem aims to find topological patterns in biological networks. Identifying non-overlapping motifs is a computationally challenging problem using classical computers. Quantum computers enable solving high complexity problems which do not scale using classical computers. In this paper, we develop the first quantum solution, called QOMIC (Quantum Optimization for Motif IdentifiCation), to the motif identification problem. QOMIC transforms the motif identification problem using a integer model, which serves as the foundation to develop our quantum solution. We develop and implement the quantum circuit to find motif locations in the given network using this model. Our experiments demonstrate that QOMIC outperforms the existing solutions developed for the classical computer, in term of motif counts. We also observe that QOMIC can efficiently find motifs in human regulatory networks associated with five neurodegenerative diseases: Alzheimers, Parkinsons, Huntingtons, Amyotrophic Lateral Sclerosis (ALS), and Motor Neurone Disease (MND).
△ Less
Submitted 5 November, 2023;
originally announced November 2023.
-
UIT-Saviors at MEDVQA-GI 2023: Improving Multimodal Learning with Image Enhancement for Gastrointestinal Visual Question Answering
Authors:
Triet M. Thai,
Anh T. Vo,
Hao K. Tieu,
Linh N. P. Bui,
Thien T. B. Nguyen
Abstract:
In recent years, artificial intelligence has played an important role in medicine and disease diagnosis, with many applications to be mentioned, one of which is Medical Visual Question Answering (MedVQA). By combining computer vision and natural language processing, MedVQA systems can assist experts in extracting relevant information from medical image based on a given question and providing preci…
▽ More
In recent years, artificial intelligence has played an important role in medicine and disease diagnosis, with many applications to be mentioned, one of which is Medical Visual Question Answering (MedVQA). By combining computer vision and natural language processing, MedVQA systems can assist experts in extracting relevant information from medical image based on a given question and providing precise diagnostic answers. The ImageCLEFmed-MEDVQA-GI-2023 challenge carried out visual question answering task in the gastrointestinal domain, which includes gastroscopy and colonoscopy images. Our team approached Task 1 of the challenge by proposing a multimodal learning method with image enhancement to improve the VQA performance on gastrointestinal images. The multimodal architecture is set up with BERT encoder and different pre-trained vision models based on convolutional neural network (CNN) and Transformer architecture for features extraction from question and endoscopy image. The result of this study highlights the dominance of Transformer-based vision models over the CNNs and demonstrates the effectiveness of the image enhancement process, with six out of the eight vision models achieving better F1-Score. Our best method, which takes advantages of BERT+BEiT fusion and image enhancement, achieves up to 87.25% accuracy and 91.85% F1-Score on the development test set, while also producing good result on the private test set with accuracy of 82.01%.
△ Less
Submitted 19 November, 2023; v1 submitted 6 July, 2023;
originally announced July 2023.
-
When Decentralized Optimization Meets Federated Learning
Authors:
Hongchang Gao,
My T. Thai,
Jie Wu
Abstract:
Federated learning is a new learning paradigm for extracting knowledge from distributed data. Due to its favorable properties in preserving privacy and saving communication costs, it has been extensively studied and widely applied to numerous data analysis applications. However, most existing federated learning approaches concentrate on the centralized setting, which is vulnerable to a single-poin…
▽ More
Federated learning is a new learning paradigm for extracting knowledge from distributed data. Due to its favorable properties in preserving privacy and saving communication costs, it has been extensively studied and widely applied to numerous data analysis applications. However, most existing federated learning approaches concentrate on the centralized setting, which is vulnerable to a single-point failure. An alternative strategy for addressing this issue is the decentralized communication topology. In this article, we systematically investigate the challenges and opportunities when renovating decentralized optimization for federated learning. In particular, we discussed them from the model, data, and communication sides, respectively, which can deepen our understanding about decentralized federated learning.
△ Less
Submitted 4 June, 2023;
originally announced June 2023.
-
FairDP: Certified Fairness with Differential Privacy
Authors:
Khang Tran,
Ferdinando Fioretto,
Issa Khalil,
My T. Thai,
NhatHai Phan
Abstract:
This paper introduces FairDP, a novel mechanism designed to achieve certified fairness with differential privacy (DP). FairDP independently trains models for distinct individual groups, using group-specific clipping terms to assess and bound the disparate impacts of DP. Throughout the training process, the mechanism progressively integrates knowledge from group models to formulate a comprehensive…
▽ More
This paper introduces FairDP, a novel mechanism designed to achieve certified fairness with differential privacy (DP). FairDP independently trains models for distinct individual groups, using group-specific clipping terms to assess and bound the disparate impacts of DP. Throughout the training process, the mechanism progressively integrates knowledge from group models to formulate a comprehensive model that balances privacy, utility, and fairness in downstream tasks. Extensive theoretical and empirical analyses validate the efficacy of FairDP and improved trade-offs between model utility, privacy, and fairness compared with existing methods.
△ Less
Submitted 21 August, 2023; v1 submitted 25 May, 2023;
originally announced May 2023.
-
Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
Authors:
Canh V. Pham,
Tan D. Tran,
Dung T. K. Ha,
My T. Thai
Abstract:
This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size $n$ subject to a knapsack constraint, $\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm that provides an approximation factor of $6+ε$ while $\mathsf{RLA}$ is a randomized algorithm with a…
▽ More
This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size $n$ subject to a knapsack constraint, $\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm that provides an approximation factor of $6+ε$ while $\mathsf{RLA}$ is a randomized algorithm with an approximation factor of $4+ε$. Both run in $O(n \log(1/ε)/ε)$ query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.
△ Less
Submitted 10 July, 2023; v1 submitted 17 May, 2023;
originally announced May 2023.
-
Deep Graph Representation Learning and Optimization for Influence Maximization
Authors:
Chen Ling,
Junji Jiang,
Junxiang Wang,
My Thai,
Lukas Xue,
James Song,
Meikang Qiu,
Liang Zhao
Abstract:
Influence maximization (IM) is formulated as selecting a set of initial users from a social network to maximize the expected number of influenced users. Researchers have made great progress in designing various traditional methods, and their theoretical design and performance gain are close to a limit. In the past few years, learning-based IM methods have emerged to achieve stronger generalization…
▽ More
Influence maximization (IM) is formulated as selecting a set of initial users from a social network to maximize the expected number of influenced users. Researchers have made great progress in designing various traditional methods, and their theoretical design and performance gain are close to a limit. In the past few years, learning-based IM methods have emerged to achieve stronger generalization ability to unknown graphs than traditional ones. However, the development of learning-based IM methods is still limited by fundamental obstacles, including 1) the difficulty of effectively solving the objective function; 2) the difficulty of characterizing the diversified underlying diffusion patterns; and 3) the difficulty of adapting the solution under various node-centrality-constrained IM variants. To cope with the above challenges, we design a novel framework DeepIM to generatively characterize the latent representation of seed sets, and we propose to learn the diversified information diffusion pattern in a data-driven and end-to-end manner. Finally, we design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints. Extensive analyses are conducted over both synthetic and real-world datasets to demonstrate the overall performance of DeepIM. The code and data are available at: https://github.com/triplej0079/DeepIM.
△ Less
Submitted 6 May, 2023; v1 submitted 1 May, 2023;
originally announced May 2023.
-
Cultural-aware Machine Learning based Analysis of COVID-19 Vaccine Hesitancy
Authors:
Raed Alharbi,
Sylvia Chan-Olmsted,
Huan Chen,
My T. Thai
Abstract:
Understanding the COVID-19 vaccine hesitancy, such as who and why, is very crucial since a large-scale vaccine adoption remains as one of the most efficient methods of controlling the pandemic. Such an understanding also provides insights into designing successful vaccination campaigns for future pandemics. Unfortunately, there are many factors involving in deciding whether to take the vaccine, es…
▽ More
Understanding the COVID-19 vaccine hesitancy, such as who and why, is very crucial since a large-scale vaccine adoption remains as one of the most efficient methods of controlling the pandemic. Such an understanding also provides insights into designing successful vaccination campaigns for future pandemics. Unfortunately, there are many factors involving in deciding whether to take the vaccine, especially from the cultural point of view. To obtain these goals, we design a novel culture-aware machine learning (ML) model, based on our new data collection, for predicting vaccination willingness. We further analyze the most important features which contribute to the ML model's predictions using advanced AI explainers such as the Probabilistic Graphical Model (PGM) and Shapley Additive Explanations (SHAP). These analyses reveal the key factors that most likely impact the vaccine adoption decisions. Our findings show that Hispanic and African American are most likely impacted by cultural characteristics such as religions and ethnic affiliation, whereas the vaccine trust and approval influence the Asian communities the most. Our results also show that cultural characteristics, rumors, and political affiliation are associated with increased vaccine rejection.
△ Less
Submitted 14 April, 2023;
originally announced April 2023.
-
Integrating Image Features with Convolutional Sequence-to-sequence Network for Multilingual Visual Question Answering
Authors:
Triet Minh Thai,
Son T. Luu
Abstract:
Visual Question Answering (VQA) is a task that requires computers to give correct answers for the input questions based on the images. This task can be solved by humans with ease but is a challenge for computers. The VLSP2022-EVJVQA shared task carries the Visual Question Answering task in the multilingual domain on a newly released dataset: UIT-EVJVQA, in which the questions and answers are writt…
▽ More
Visual Question Answering (VQA) is a task that requires computers to give correct answers for the input questions based on the images. This task can be solved by humans with ease but is a challenge for computers. The VLSP2022-EVJVQA shared task carries the Visual Question Answering task in the multilingual domain on a newly released dataset: UIT-EVJVQA, in which the questions and answers are written in three different languages: English, Vietnamese and Japanese. We approached the challenge as a sequence-to-sequence learning task, in which we integrated hints from pre-trained state-of-the-art VQA models and image features with Convolutional Sequence-to-Sequence network to generate the desired answers. Our results obtained up to 0.3442 by F1 score on the public test set, 0.4210 on the private test set, and placed 3rd in the competition.
△ Less
Submitted 3 September, 2023; v1 submitted 22 March, 2023;
originally announced March 2023.
-
Active Membership Inference Attack under Local Differential Privacy in Federated Learning
Authors:
Truc Nguyen,
Phung Lai,
Khang Tran,
NhatHai Phan,
My T. Thai
Abstract:
Federated learning (FL) was originally regarded as a framework for collaborative learning among clients with data privacy protection through a coordinating server. In this paper, we propose a new active membership inference (AMI) attack carried out by a dishonest server in FL. In AMI attacks, the server crafts and embeds malicious parameters into global models to effectively infer whether a target…
▽ More
Federated learning (FL) was originally regarded as a framework for collaborative learning among clients with data privacy protection through a coordinating server. In this paper, we propose a new active membership inference (AMI) attack carried out by a dishonest server in FL. In AMI attacks, the server crafts and embeds malicious parameters into global models to effectively infer whether a target data sample is included in a client's private training data or not. By exploiting the correlation among data features through a non-linear decision boundary, AMI attacks with a certified guarantee of success can achieve severely high success rates under rigorous local differential privacy (LDP) protection; thereby exposing clients' training data to significant privacy risk. Theoretical and experimental results on several benchmark datasets show that adding sufficient privacy-preserving noise to prevent our attack would significantly damage FL's model utility.
△ Less
Submitted 24 July, 2023; v1 submitted 24 February, 2023;
originally announced February 2023.
-
LAVA: Granular Neuron-Level Explainable AI for Alzheimer's Disease Assessment from Fundus Images
Authors:
Nooshin Yousefzadeh,
Charlie Tran,
Adolfo Ramirez-Zamora,
Jinghua Chen,
Ruogu Fang,
My T. Thai
Abstract:
Alzheimer's Disease (AD) is a progressive neurodegenerative disease and the leading cause of dementia. Early diagnosis is critical for patients to benefit from potential intervention and treatment. The retina has been hypothesized as a diagnostic site for AD detection owing to its anatomical connection with the brain. Developed AI models for this purpose have yet to provide a rational explanation…
▽ More
Alzheimer's Disease (AD) is a progressive neurodegenerative disease and the leading cause of dementia. Early diagnosis is critical for patients to benefit from potential intervention and treatment. The retina has been hypothesized as a diagnostic site for AD detection owing to its anatomical connection with the brain. Developed AI models for this purpose have yet to provide a rational explanation about the decision and neither infer the stage of disease's progression. Along this direction, we propose a novel model-agnostic explainable-AI framework, called Granular Neuron-level Explainer (LAVA), an interpretation prototype that probes into intermediate layers of the Convolutional Neural Network (CNN) models to assess the AD continuum directly from the retinal imaging without longitudinal or clinical evaluation. This method is applied to validate the retinal vasculature as a biomarker and diagnostic modality for Alzheimer's Disease (AD) evaluation. UK Biobank cognitive tests and vascular morphological features suggest LAVA shows strong promise and effectiveness in identifying AD stages across the progression continuum.
△ Less
Submitted 16 March, 2023; v1 submitted 6 February, 2023;
originally announced February 2023.
-
Investigating the Dynamics of Social Norm Emergence within Online Communities
Authors:
Shangde Gao,
Yan Wang,
My T. Thai
Abstract:
Although the effects of the social norm on mitigating misinformation are identified, scant knowledge exists about the patterns of social norm emergence, such as the patterns and variations of social tipping in online communities with diverse characteristics. Accordingly, this study investigates the features of social tipping in online communities and examines the correlations between the tipping f…
▽ More
Although the effects of the social norm on mitigating misinformation are identified, scant knowledge exists about the patterns of social norm emergence, such as the patterns and variations of social tipping in online communities with diverse characteristics. Accordingly, this study investigates the features of social tipping in online communities and examines the correlations between the tipping features and characteristics of online communities. Taking the side effects of COVID-19 vaccination as the case topic, we first track the patterns of tipping features in 100 online communities, which are detected using Louvain Algorithm from the aggregated communication network on Twitter between May 2020 and April 2021. Then, we use multi-variant linear regression to explore the correlations between tipping features and community characteristics. We find that social tipping in online communities can sustain for two to four months and lead to a 50% increase in populations who accept the normative belief in online communities. The regression indicates that the duration of social tipping is positively related to the community populations and original acceptance of social norms, while the correlation between the tipping duration and the degrees among community members is negative. Additionally, the network modularity and original acceptance of social norms have negative relationships with the extent of social tipping, while the degree and betweenness centrality can have significant positive relationships with the extent of tipping. Our findings shed light on more precise normative interventions on misinformation in digital environments as it offers preliminary evidence about the timing and mechanism of social norm emergence.
△ Less
Submitted 1 January, 2023;
originally announced January 2023.
-
XRand: Differentially Private Defense against Explanation-Guided Attacks
Authors:
Truc Nguyen,
Phung Lai,
NhatHai Phan,
My T. Thai
Abstract:
Recent development in the field of explainable artificial intelligence (XAI) has helped improve trust in Machine-Learning-as-a-Service (MLaaS) systems, in which an explanation is provided together with the model prediction in response to each query. However, XAI also opens a door for adversaries to gain insights into the black-box models in MLaaS, thereby making the models more vulnerable to sever…
▽ More
Recent development in the field of explainable artificial intelligence (XAI) has helped improve trust in Machine-Learning-as-a-Service (MLaaS) systems, in which an explanation is provided together with the model prediction in response to each query. However, XAI also opens a door for adversaries to gain insights into the black-box models in MLaaS, thereby making the models more vulnerable to several attacks. For example, feature-based explanations (e.g., SHAP) could expose the top important features that a black-box model focuses on. Such disclosure has been exploited to craft effective backdoor triggers against malware classifiers. To address this trade-off, we introduce a new concept of achieving local differential privacy (LDP) in the explanations, and from that we establish a defense, called XRand, against such attacks. We show that our mechanism restricts the information that the adversary can learn about the top important features, while maintaining the faithfulness of the explanations.
△ Less
Submitted 14 December, 2022; v1 submitted 8 December, 2022;
originally announced December 2022.
-
On the Limit of Explaining Black-box Temporal Graph Neural Networks
Authors:
Minh N. Vu,
My T. Thai
Abstract:
Temporal Graph Neural Network (TGNN) has been receiving a lot of attention recently due to its capability in modeling time-evolving graph-related tasks. Similar to Graph Neural Networks, it is also non-trivial to interpret predictions made by a TGNN due to its black-box nature. A major approach tackling this problems in GNNs is by analyzing the model' responses on some perturbations of the model's…
▽ More
Temporal Graph Neural Network (TGNN) has been receiving a lot of attention recently due to its capability in modeling time-evolving graph-related tasks. Similar to Graph Neural Networks, it is also non-trivial to interpret predictions made by a TGNN due to its black-box nature. A major approach tackling this problems in GNNs is by analyzing the model' responses on some perturbations of the model's inputs, called perturbation-based explanation methods. While these methods are convenient and flexible since they do not need internal access to the model, does this lack of internal access prevent them from revealing some important information of the predictions? Motivated by that question, this work studies the limit of some classes of perturbation-based explanation methods. Particularly, by constructing some specific instances of TGNNs, we show (i) node-perturbation cannot reliably identify the paths carrying out the prediction, (ii) edge-perturbation is not reliable in determining all nodes contributing to the prediction and (iii) perturbing both nodes and edges does not reliably help us identify the graph's components carrying out the temporal aggregation in TGNNs.
△ Less
Submitted 1 December, 2022;
originally announced December 2022.
-
Heterogeneous Randomized Response for Differential Privacy in Graph Neural Networks
Authors:
Khang Tran,
Phung Lai,
NhatHai Phan,
Issa Khalil,
Yao Ma,
Abdallah Khreishah,
My Thai,
Xintao Wu
Abstract:
Graph neural networks (GNNs) are susceptible to privacy inference attacks (PIAs), given their ability to learn joint representation from features and edges among nodes in graph data. To prevent privacy leakages in GNNs, we propose a novel heterogeneous randomized response (HeteroRR) mechanism to protect nodes' features and edges against PIAs under differential privacy (DP) guarantees without an un…
▽ More
Graph neural networks (GNNs) are susceptible to privacy inference attacks (PIAs), given their ability to learn joint representation from features and edges among nodes in graph data. To prevent privacy leakages in GNNs, we propose a novel heterogeneous randomized response (HeteroRR) mechanism to protect nodes' features and edges against PIAs under differential privacy (DP) guarantees without an undue cost of data and model utility in training GNNs. Our idea is to balance the importance and sensitivity of nodes' features and edges in redistributing the privacy budgets since some features and edges are more sensitive or important to the model utility than others. As a result, we derive significantly better randomization probabilities and tighter error bounds at both levels of nodes' features and edges departing from existing approaches, thus enabling us to maintain high data utility for training GNNs. An extensive theoretical and empirical analysis using benchmark datasets shows that HeteroRR significantly outperforms various baselines in terms of model utility under rigorous privacy protection for both nodes' features and edges. That enables us to defend PIAs in DP-preserving GNNs effectively.
△ Less
Submitted 10 November, 2022;
originally announced November 2022.
-
EMaP: Explainable AI with Manifold-based Perturbations
Authors:
Minh N. Vu,
Huy Q. Mai,
My T. Thai
Abstract:
In the last few years, many explanation methods based on the perturbations of input data have been introduced to improve our understanding of decisions made by black-box models. The goal of this work is to introduce a novel perturbation scheme so that more faithful and robust explanations can be obtained. Our study focuses on the impact of perturbing directions on the data topology. We show that p…
▽ More
In the last few years, many explanation methods based on the perturbations of input data have been introduced to improve our understanding of decisions made by black-box models. The goal of this work is to introduce a novel perturbation scheme so that more faithful and robust explanations can be obtained. Our study focuses on the impact of perturbing directions on the data topology. We show that perturbing along the orthogonal directions of the input manifold better preserves the data topology, both in the worst-case analysis of the discrete Gromov-Hausdorff distance and in the average-case analysis via persistent homology. From those results, we introduce EMaP algorithm, realizing the orthogonal perturbation scheme. Our experiments show that EMaP not only improves the explainers' performance but also helps them overcome a recently-developed attack against perturbation-based methods.
△ Less
Submitted 17 September, 2022;
originally announced September 2022.
-
NeuCEPT: Locally Discover Neural Networks' Mechanism via Critical Neurons Identification with Precision Guarantee
Authors:
Minh N. Vu,
Truc D. Nguyen,
My T. Thai
Abstract:
Despite recent studies on understanding deep neural networks (DNNs), there exists numerous questions on how DNNs generate their predictions. Especially, given similar predictions on different input samples, are the underlying mechanisms generating those predictions the same? In this work, we propose NeuCEPT, a method to locally discover critical neurons that play a major role in the model's predic…
▽ More
Despite recent studies on understanding deep neural networks (DNNs), there exists numerous questions on how DNNs generate their predictions. Especially, given similar predictions on different input samples, are the underlying mechanisms generating those predictions the same? In this work, we propose NeuCEPT, a method to locally discover critical neurons that play a major role in the model's predictions and identify model's mechanisms in generating those predictions. We first formulate a critical neurons identification problem as maximizing a sequence of mutual-information objectives and provide a theoretical framework to efficiently solve for critical neurons while keeping the precision under control. NeuCEPT next heuristically learns different model's mechanisms in an unsupervised manner. Our experimental results show that neurons identified by NeuCEPT not only have strong influence on the model's predictions but also hold meaningful information about model's mechanisms.
△ Less
Submitted 17 September, 2022;
originally announced September 2022.
-
UIT-ViCoV19QA: A Dataset for COVID-19 Community-based Question Answering on Vietnamese Language
Authors:
Triet Minh Thai,
Ngan Ha-Thao Chu,
Anh Tuan Vo,
Son T. Luu
Abstract:
For the last two years, from 2020 to 2021, COVID-19 has broken disease prevention measures in many countries, including Vietnam, and negatively impacted various aspects of human life and the social community. Besides, the misleading information in the community and fake news about the pandemic are also serious situations. Therefore, we present the first Vietnamese community-based question answerin…
▽ More
For the last two years, from 2020 to 2021, COVID-19 has broken disease prevention measures in many countries, including Vietnam, and negatively impacted various aspects of human life and the social community. Besides, the misleading information in the community and fake news about the pandemic are also serious situations. Therefore, we present the first Vietnamese community-based question answering dataset for developing question answering systems for COVID-19 called UIT-ViCoV19QA. The dataset comprises 4,500 question-answer pairs collected from trusted medical sources, with at least one answer and at most four unique paraphrased answers per question. Along with the dataset, we set up various deep learning models as baseline to assess the quality of our dataset and initiate the benchmark results for further research through commonly used metrics such as BLEU, METEOR, and ROUGE-L. We also illustrate the positive effects of having multiple paraphrased answers experimented on these models, especially on Transformer - a dominant architecture in the field of study.
△ Less
Submitted 14 September, 2022;
originally announced September 2022.
-
An Explainer for Temporal Graph Neural Networks
Authors:
Wenchong He,
Minh N. Vu,
Zhe Jiang,
My T. Thai
Abstract:
Temporal graph neural networks (TGNNs) have been widely used for modeling time-evolving graph-related tasks due to their ability to capture both graph topology dependency and non-linear temporal dynamic. The explanation of TGNNs is of vital importance for a transparent and trustworthy model. However, the complex topology structure and temporal dependency make explaining TGNN models very challengin…
▽ More
Temporal graph neural networks (TGNNs) have been widely used for modeling time-evolving graph-related tasks due to their ability to capture both graph topology dependency and non-linear temporal dynamic. The explanation of TGNNs is of vital importance for a transparent and trustworthy model. However, the complex topology structure and temporal dependency make explaining TGNN models very challenging. In this paper, we propose a novel explainer framework for TGNN models. Given a time series on a graph to be explained, the framework can identify dominant explanations in the form of a probabilistic graphical model in a time period. Case studies on the transportation domain demonstrate that the proposed approach can discover dynamic dependency structures in a road network for a time period.
△ Less
Submitted 2 September, 2022;
originally announced September 2022.
-
Lifelong DP: Consistently Bounded Differential Privacy in Lifelong Machine Learning
Authors:
Phung Lai,
Han Hu,
NhatHai Phan,
Ruoming Jin,
My T. Thai,
An M. Chen
Abstract:
In this paper, we show that the process of continually learning new tasks and memorizing previous tasks introduces unknown privacy risks and challenges to bound the privacy loss. Based upon this, we introduce a formal definition of Lifelong DP, in which the participation of any data tuples in the training set of any tasks is protected, under a consistently bounded DP protection, given a growing st…
▽ More
In this paper, we show that the process of continually learning new tasks and memorizing previous tasks introduces unknown privacy risks and challenges to bound the privacy loss. Based upon this, we introduce a formal definition of Lifelong DP, in which the participation of any data tuples in the training set of any tasks is protected, under a consistently bounded DP protection, given a growing stream of tasks. A consistently bounded DP means having only one fixed value of the DP privacy budget, regardless of the number of tasks. To preserve Lifelong DP, we propose a scalable and heterogeneous algorithm, called L2DP-ML with a streaming batch training, to efficiently train and continue releasing new versions of an L2M model, given the heterogeneity in terms of data sizes and the training order of tasks, without affecting DP protection of the private training set. An end-to-end theoretical analysis and thorough evaluations show that our mechanism is significantly better than baseline approaches in preserving Lifelong DP. The implementation of L2DP-ML is available at: https://github.com/haiphanNJIT/PrivateDeepLearning.
△ Less
Submitted 26 July, 2022;
originally announced July 2022.
-
Optimizing Resource Allocation and VNF Embedding in RAN Slicing
Authors:
Tu N. Nguyen,
Kashyab J. Ambarani,
My T. Thai
Abstract:
5G radio access network (RAN) with network slicing methodology plays a key role in the development of the next-generation network system. RAN slicing focuses on splitting the substrate's resources into a set of self-contained programmable RAN slices. Leveraged by network function virtualization (NFV), a RAN slice is constituted by various virtual network functions (VNFs) and virtual links that are…
▽ More
5G radio access network (RAN) with network slicing methodology plays a key role in the development of the next-generation network system. RAN slicing focuses on splitting the substrate's resources into a set of self-contained programmable RAN slices. Leveraged by network function virtualization (NFV), a RAN slice is constituted by various virtual network functions (VNFs) and virtual links that are embedded as instances on substrate nodes. In this work, we focus on the following fundamental tasks: i) establishing the theoretical foundation for constructing a VNF mapping plan for RAN slice recovery optimization and ii) developing algorithms needed to map/embed VNFs efficiently. In particular, we propose four efficient algorithms, including Resource-based Algorithm (RBA), Connectivity-based Algorithm (CBA), Group-based Algorithm (GBA), and Group-Connectivity-based Algorithm (GCBA) to solve the resource allocation and VNF mapping problem. Extensive experiments are also conducted to validate the robustness of RAN slicing via the proposed algorithms.
△ Less
Submitted 18 July, 2022;
originally announced July 2022.
-
Towards An Optimal Solution to Place Bistatic Radars for Belt Barrier Coverage with Minimum Cost
Authors:
Tu N. Nguyen,
Bing-Hong Liu,
My T. Thai,
Ivan Djordjevic
Abstract:
With the rapid growth of threats, sophistication and diversity in the manner of intrusion, traditional belt barrier systems are now faced with a major challenge of providing high and concrete coverage quality to expand the guarding service market. Recent efforts aim at constructing a belt barrier by deploying bistatic radar(s) on a specific line regardless of the limitation on deployment locations…
▽ More
With the rapid growth of threats, sophistication and diversity in the manner of intrusion, traditional belt barrier systems are now faced with a major challenge of providing high and concrete coverage quality to expand the guarding service market. Recent efforts aim at constructing a belt barrier by deploying bistatic radar(s) on a specific line regardless of the limitation on deployment locations, to keep the width of the barrier from going below a specific threshold and the total bistatic radar placement cost is minimized, referred to as the Minimum Cost Linear Placement (MCLP) problem. The existing solutions are heuristic, and their validity is tightly bound by the barrier width parameter that these solutions only work for a fixed barrier width value. In this work, we propose an optimal solution, referred to as the Opt_MCLP, for the "open MCLP problem" that works for full range of the barrier width. Through rigorous theoretical analysis and experimentation, we demonstrate that the proposed algorithms perform well in terms of placement cost reduction and barrier coverage guarantee.
△ Less
Submitted 19 July, 2022;
originally announced July 2022.
-
On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network
Authors:
Hongchang Gao,
Bin Gu,
My T. Thai
Abstract:
Bilevel optimization has been applied to a wide variety of machine learning models, and numerous stochastic bilevel optimization algorithms have been developed in recent years. However, most existing algorithms restrict their focus on the single-machine setting so that they are incapable of handling the distributed data. To address this issue, under the setting where all participants compose a net…
▽ More
Bilevel optimization has been applied to a wide variety of machine learning models, and numerous stochastic bilevel optimization algorithms have been developed in recent years. However, most existing algorithms restrict their focus on the single-machine setting so that they are incapable of handling the distributed data. To address this issue, under the setting where all participants compose a network and perform peer-to-peer communication in this network, we developed two novel decentralized stochastic bilevel optimization algorithms based on the gradient tracking communication mechanism and two different gradient estimators. Additionally, we established their convergence rates for nonconvex-strongly-convex problems with novel theoretical analysis strategies. To our knowledge, this is the first work achieving these theoretical results. Finally, we applied our algorithms to practical machine learning models, and the experimental results confirmed the efficacy of our algorithms.
△ Less
Submitted 27 March, 2023; v1 submitted 30 June, 2022;
originally announced June 2022.
-
Blockchain-based Secure Client Selection in Federated Learning
Authors:
Truc Nguyen,
Phuc Thai,
Tre' R. Jeter,
Thang N. Dinh,
My T. Thai
Abstract:
Despite the great potential of Federated Learning (FL) in large-scale distributed learning, the current system is still subject to several privacy issues due to the fact that local models trained by clients are exposed to the central server. Consequently, secure aggregation protocols for FL have been developed to conceal the local models from the server. However, we show that, by manipulating the…
▽ More
Despite the great potential of Federated Learning (FL) in large-scale distributed learning, the current system is still subject to several privacy issues due to the fact that local models trained by clients are exposed to the central server. Consequently, secure aggregation protocols for FL have been developed to conceal the local models from the server. However, we show that, by manipulating the client selection process, the server can circumvent the secure aggregation to learn the local models of a victim client, indicating that secure aggregation alone is inadequate for privacy protection. To tackle this issue, we leverage blockchain technology to propose a verifiable client selection protocol. Owing to the immutability and transparency of blockchain, our proposed protocol enforces a random selection of clients, making the server unable to control the selection process at its discretion. We present security proofs showing that our protocol is secure against this attack. Additionally, we conduct several experiments on an Ethereum-like blockchain to demonstrate the feasibility and practicality of our solution.
△ Less
Submitted 11 May, 2022;
originally announced May 2022.
-
FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing
Authors:
Phuc Thai,
My T. Thai,
Tam Vu,
Thang N. Dinh
Abstract:
Quantum annealing (QA) that encodes optimization problems into Hamiltonians remains the only near-term quantum computing paradigm that provides sufficient many qubits for real-world applications. To fit larger optimization instances on existing quantum annealers, reducing Hamiltonians into smaller equivalent Hamiltonians provides a promising approach. Unfortunately, existing reduction techniques a…
▽ More
Quantum annealing (QA) that encodes optimization problems into Hamiltonians remains the only near-term quantum computing paradigm that provides sufficient many qubits for real-world applications. To fit larger optimization instances on existing quantum annealers, reducing Hamiltonians into smaller equivalent Hamiltonians provides a promising approach. Unfortunately, existing reduction techniques are either computationally expensive or ineffective in practice. To this end, we introduce a novel notion of non-separable~group, defined as a subset of qubits in a Hamiltonian that obtains the same value in optimal solutions. We develop a theoretical framework on non-separability accordingly and propose FastHare, a highly efficient reduction method. FastHare, iteratively, detects and merges non-separable groups into single qubits. It does so within a provable worst-case time complexity of only $O(αn^2)$, for some user-defined parameter $α$. Our extensive benchmarks for the feasibility of the reduction are done on both synthetic Hamiltonians and 3000+ instances from the MQLIB library. The results show FastHare outperforms the roof duality, the implemented reduction method in D-Wave's SDK library, with 3.6x higher average reduction ratio. It demonstrates a high level of effectiveness with an average of 62% qubits saving and 0.3s processing time, advocating for Hamiltonian reduction as an inexpensive necessity for QA.
△ Less
Submitted 10 May, 2022;
originally announced May 2022.
-
Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint
Authors:
Lan N. Nguyen,
My T. Thai
Abstract:
In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance gu…
▽ More
In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance guarantee of some existing techniques. We further investigate those algorithms' performance in two applications: Boosting Influence Spread and Video Summarization. Experiments show our algorithms return comparative results to the state-of-the-art algorithms while taking much fewer queries.
△ Less
Submitted 28 April, 2022;
originally announced April 2022.
-
SaPHyRa: A Learning Theory Approach to Ranking Nodes in Large Networks
Authors:
Phuc Thai,
My T. Thai,
Tam Vu,
Thang N. Dinh
Abstract:
Ranking nodes based on their centrality stands a fundamental, yet, challenging problem in large-scale networks. Approximate methods can quickly estimate nodes' centrality and identify the most central nodes, but the ranking for the majority of remaining nodes may be meaningless. For example, ranking for less-known websites in search queries is known to be noisy and unstable. To this end, we invest…
▽ More
Ranking nodes based on their centrality stands a fundamental, yet, challenging problem in large-scale networks. Approximate methods can quickly estimate nodes' centrality and identify the most central nodes, but the ranking for the majority of remaining nodes may be meaningless. For example, ranking for less-known websites in search queries is known to be noisy and unstable. To this end, we investigate a new node ranking problem with two important distinctions: a) ranking quality, rather than the centrality estimation quality, as the primary objective; and b) ranking only nodes of interest, e.g., websites that matched search criteria. We propose Sample space Partitioning Hypothesis Ranking, or SaPHyRa, that transforms node ranking into a hypothesis ranking in machine learning. This transformation maps nodes' centrality to the expected risks of hypotheses, opening doors for theoretical machine learning (ML) tools. The key of SaPHyRa is to partition the sample space into exact and approximate subspaces. The exact subspace contains samples related to the nodes of interest, increasing both estimation and ranking qualities. The approximate space can be efficiently sampled with ML-based techniques to provide theoretical guarantees on the estimation error. Lastly, we present SaPHyRa_bc, an illustration of SaPHyRa on ranking nodes' betweenness centrality (BC). By combining a novel bi-component sampling, a 2-hop sample partitioning, and improved bounds on the Vapnik-Chervonenkis dimension, SaPHyRa_bc can effectively rank any node subset in BC. Its performance is up to 200x faster than state-of-the-art methods in approximating BC, while its rank correlation to the ground truth is improved by multifold.
△ Less
Submitted 3 March, 2022;
originally announced March 2022.
-
Preserving Privacy and Security in Federated Learning
Authors:
Truc Nguyen,
My T. Thai
Abstract:
Federated learning is known to be vulnerable to both security and privacy issues. Existing research has focused either on preventing poisoning attacks from users or on concealing the local model updates from the server, but not both. However, integrating these two lines of research remains a crucial challenge since they often conflict with one another with respect to the threat model. In this work…
▽ More
Federated learning is known to be vulnerable to both security and privacy issues. Existing research has focused either on preventing poisoning attacks from users or on concealing the local model updates from the server, but not both. However, integrating these two lines of research remains a crucial challenge since they often conflict with one another with respect to the threat model. In this work, we develop a principle framework that offers both privacy guarantees for users and detection against poisoning attacks from them. With a new threat model that includes both an honest-but-curious server and malicious users, we first propose a secure aggregation protocol using homomorphic encryption for the server to combine local model updates in a private manner. Then, a zero-knowledge proof protocol is leveraged to shift the task of detecting attacks in the local models from the server to the users. The key observation here is that the server no longer needs access to the local models for attack detection. Therefore, our framework enables the central server to identify poisoned model updates without violating the privacy guarantees of secure aggregation.
△ Less
Submitted 28 August, 2023; v1 submitted 7 February, 2022;
originally announced February 2022.
-
Learning Interpretation with Explainable Knowledge Distillation
Authors:
Raed Alharbi,
Minh N. Vu,
My T. Thai
Abstract:
Knowledge Distillation (KD) has been considered as a key solution in model compression and acceleration in recent years. In KD, a small student model is generally trained from a large teacher model by minimizing the divergence between the probabilistic outputs of the two. However, as demonstrated in our experiments, existing KD methods might not transfer critical explainable knowledge of the teach…
▽ More
Knowledge Distillation (KD) has been considered as a key solution in model compression and acceleration in recent years. In KD, a small student model is generally trained from a large teacher model by minimizing the divergence between the probabilistic outputs of the two. However, as demonstrated in our experiments, existing KD methods might not transfer critical explainable knowledge of the teacher to the student, i.e. the explanations of predictions made by the two models are not consistent. In this paper, we propose a novel explainable knowledge distillation model, called XDistillation, through which both the performance the explanations' information are transferred from the teacher model to the student model. The XDistillation model leverages the idea of convolutional autoencoders to approximate the teacher explanations. Our experiments shows that models trained by XDistillation outperform those trained by conventional KD methods not only in term of predictive accuracy but also faithfulness to the teacher models.
△ Less
Submitted 12 November, 2021;
originally announced November 2021.
-
Continual Learning with Differential Privacy
Authors:
Pradnya Desai,
Phung Lai,
NhatHai Phan,
My T. Thai
Abstract:
In this paper, we focus on preserving differential privacy (DP) in continual learning (CL), in which we train ML models to learn a sequence of new tasks while memorizing previous tasks. We first introduce a notion of continual adjacent databases to bound the sensitivity of any data record participating in the training process of CL. Based upon that, we develop a new DP-preserving algorithm for CL…
▽ More
In this paper, we focus on preserving differential privacy (DP) in continual learning (CL), in which we train ML models to learn a sequence of new tasks while memorizing previous tasks. We first introduce a notion of continual adjacent databases to bound the sensitivity of any data record participating in the training process of CL. Based upon that, we develop a new DP-preserving algorithm for CL with a data sampling strategy to quantify the privacy risk of training data in the well-known Averaged Gradient Episodic Memory (A-GEM) approach by applying a moments accountant. Our algorithm provides formal guarantees of privacy for data records across tasks in CL. Preliminary theoretical analysis and evaluations show that our mechanism tightens the privacy loss while maintaining a promising model utility.
△ Less
Submitted 11 October, 2021;
originally announced October 2021.
-
Groups Influence with Minimum Cost in Social Networks
Authors:
Phuong N. H. Pham,
Canh V. Pham,
Hieu V. Duong,
Thanh T. Nguyen,
My T. Thai
Abstract:
This paper studies a Group Influence with Minimum cost which aims to find a seed set with smallest cost that can influence all target groups, where each user is associated with a cost and a group is influenced if the total score of the influenced users belonging to the group is at least a certain threshold. As the group-influence function is neither submodular nor supermodular, theoretical bounds…
▽ More
This paper studies a Group Influence with Minimum cost which aims to find a seed set with smallest cost that can influence all target groups, where each user is associated with a cost and a group is influenced if the total score of the influenced users belonging to the group is at least a certain threshold. As the group-influence function is neither submodular nor supermodular, theoretical bounds on the quality of solutions returned by the well-known greedy approach may not be guaranteed. To address this challenge, we propose a bi-criteria polynomial-time approximation algorithm with high certainty. At the heart of the algorithm is a novel group reachable reverse sample concept, which helps speed up the estimation of the group influence function. Finally, extensive experiments conducted on real social networks show that our proposed algorithm outperform the state-of-the-art algorithms in terms of the objective value and the running time.
△ Less
Submitted 14 December, 2022; v1 submitted 18 September, 2021;
originally announced September 2021.
-
Minimum Robust Multi-Submodular Cover for Fairness
Authors:
Lan N. Nguyen,
My T. Thai
Abstract:
In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MinRF), as follows: given a ground set $V$; $m$ monotone submodular functions $f_1,...,f_m$; $m$ thresholds $T_1,...,T_m$ and a non-negative integer $r$, MinRF asks for the smallest set $S$ such that for all $i \in [m]$, $\min_{|X| \leq r} f_i(S \setminus X) \geq T_i$. We prove that MinRF is inapproximable…
▽ More
In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MinRF), as follows: given a ground set $V$; $m$ monotone submodular functions $f_1,...,f_m$; $m$ thresholds $T_1,...,T_m$ and a non-negative integer $r$, MinRF asks for the smallest set $S$ such that for all $i \in [m]$, $\min_{|X| \leq r} f_i(S \setminus X) \geq T_i$. We prove that MinRF is inapproximable within $(1-ε)\ln m$; and no algorithm, taking fewer than exponential number of queries in term of $r$, is able to output a feasible set to MinRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for $r=0$, one for $r=1$, and one for general $r$. We further investigate our algorithms' performance in two applications of MinRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.
△ Less
Submitted 14 December, 2020;
originally announced December 2020.
-
PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks
Authors:
Minh N. Vu,
My T. Thai
Abstract:
In Graph Neural Networks (GNNs), the graph structure is incorporated into the learning of node representations. This complex structure makes explaining GNNs' predictions become much more challenging. In this paper, we propose PGM-Explainer, a Probabilistic Graphical Model (PGM) model-agnostic explainer for GNNs. Given a prediction to be explained, PGM-Explainer identifies crucial graph components…
▽ More
In Graph Neural Networks (GNNs), the graph structure is incorporated into the learning of node representations. This complex structure makes explaining GNNs' predictions become much more challenging. In this paper, we propose PGM-Explainer, a Probabilistic Graphical Model (PGM) model-agnostic explainer for GNNs. Given a prediction to be explained, PGM-Explainer identifies crucial graph components and generates an explanation in form of a PGM approximating that prediction. Different from existing explainers for GNNs where the explanations are drawn from a set of linear functions of explained features, PGM-Explainer is able to demonstrate the dependencies of explained features in form of conditional probabilities. Our theoretical analysis shows that the PGM generated by PGM-Explainer includes the Markov-blanket of the target prediction, i.e. including all its statistical information. We also show that the explanation returned by PGM-Explainer contains the same set of independence statements in the perfect map. Our experiments on both synthetic and real-world datasets show that PGM-Explainer achieves better performance than existing explainers in many benchmark tasks.
△ Less
Submitted 12 October, 2020;
originally announced October 2020.
-
Length-Bounded Paths Interdiction in Continuous Domain for Network Performance Assessment
Authors:
Lan N. Nguyen,
My T. Thai
Abstract:
Studying on networked systems, in which a communication between nodes is functional if their distance under a given metric is lower than a pre-defined threshold, has received significant attention recently. In this work, we propose a metric to measure network resilience on guaranteeing the pre-defined performance constraint. This metric is investigated under an optimization problem, namely \textbf…
▽ More
Studying on networked systems, in which a communication between nodes is functional if their distance under a given metric is lower than a pre-defined threshold, has received significant attention recently. In this work, we propose a metric to measure network resilience on guaranteeing the pre-defined performance constraint. This metric is investigated under an optimization problem, namely \textbf{Length-bounded Paths Interdiction in Continuous Domain} (cLPI), which aims to identify a minimum set of nodes whose changes cause routing paths between nodes become undesirable for the network service.
We show the problem is NP-hard and propose a framework by designing two oracles, \textit{Threshold Blocking} (TB) and \textit{Critical Path Listing} (CPL), which communicate back and forth to construct a feasible solution to cLPI with theoretical bicriteria approximation guarantees. Based on this framework, we propose two solutions for each oracle. Each combination of one solution to \tb and one solution to \cpl gives us a solution to cLPI. The bicriteria guarantee of our algorithms allows us to control the solutions's trade-off between the returned size and the performance accuracy. New insights into the advantages of each solution are further discussed via experimental analysis.
△ Less
Submitted 18 September, 2020;
originally announced September 2020.
-
Auditing the Sensitivity of Graph-based Ranking with Visual Analytics
Authors:
Tiankai Xie,
Yuxin Ma,
Hanghang Tong,
My T. Thai,
Ross Maciejewski
Abstract:
Graph mining plays a pivotal role across a number of disciplines, and a variety of algorithms have been developed to answer who/what type questions. For example, what items shall we recommend to a given user on an e-commerce platform? The answers to such questions are typically returned in the form of a ranked list, and graph-based ranking methods are widely used in industrial information retrieva…
▽ More
Graph mining plays a pivotal role across a number of disciplines, and a variety of algorithms have been developed to answer who/what type questions. For example, what items shall we recommend to a given user on an e-commerce platform? The answers to such questions are typically returned in the form of a ranked list, and graph-based ranking methods are widely used in industrial information retrieval settings. However, these ranking algorithms have a variety of sensitivities, and even small changes in rank can lead to vast reductions in product sales and page hits. As such, there is a need for tools and methods that can help model developers and analysts explore the sensitivities of graph ranking algorithms with respect to perturbations within the graph structure. In this paper, we present a visual analytics framework for explaining and exploring the sensitivity of any graph-based ranking algorithm by performing perturbation-based what-if analysis. We demonstrate our framework through three case studies inspecting the sensitivity of two classic graph-based ranking algorithms (PageRank and HITS) as applied to rankings in political news media and social networks.
△ Less
Submitted 15 September, 2020;
originally announced September 2020.
-
Denial-of-Service Vulnerability of Hash-based Transaction Sharding: Attack and Countermeasure
Authors:
Truc Nguyen,
My T. Thai
Abstract:
Since 2016, sharding has become an auspicious solution to tackle the scalability issue in legacy blockchain systems. Despite its potential to strongly boost the blockchain throughput, sharding comes with its own security issues. To ease the process of deciding which shard to place transactions, existing sharding protocols use a hash-based transaction sharding in which the hash value of a transacti…
▽ More
Since 2016, sharding has become an auspicious solution to tackle the scalability issue in legacy blockchain systems. Despite its potential to strongly boost the blockchain throughput, sharding comes with its own security issues. To ease the process of deciding which shard to place transactions, existing sharding protocols use a hash-based transaction sharding in which the hash value of a transaction determines its output shard. Unfortunately, we show that this mechanism opens up a loophole that could be exploited to conduct a single-shard flooding attack, a type of Denial-of-Service (DoS) attack, to overwhelm a single shard that ends up reducing the performance of the system as a whole.
To counter the single-shard flooding attack, we propose a countermeasure that essentially eliminates the loophole by rejecting the use of hash-based transaction sharding. The countermeasure leverages the Trusted Execution Environment (TEE) to let blockchain's validators securely execute a transaction sharding algorithm with a negligible overhead. We provide a formal specification for the countermeasure and analyze its security properties in the Universal Composability (UC) framework. Finally, a proof-of-concept is developed to demonstrate the feasibility and practicality of our solution.
△ Less
Submitted 26 August, 2023; v1 submitted 16 July, 2020;
originally announced July 2020.
-
OptChain: Optimal Transactions Placement for Scalable Blockchain Sharding
Authors:
Lan N. Nguyen,
Truc Nguyen,
Thang N. Dinh,
My T. Thai
Abstract:
A major challenge in blockchain sharding protocols is that more than 95% transactions are cross-shard. Not only those cross-shard transactions degrade the system throughput but also double the confirmation time, and exhaust an already scarce network bandwidth. Are cross-shard transactions imminent for sharding schemes? In this paper, we propose a new sharding paradigm, called OptChain, in which cr…
▽ More
A major challenge in blockchain sharding protocols is that more than 95% transactions are cross-shard. Not only those cross-shard transactions degrade the system throughput but also double the confirmation time, and exhaust an already scarce network bandwidth. Are cross-shard transactions imminent for sharding schemes? In this paper, we propose a new sharding paradigm, called OptChain, in which cross-shard transactions are minimized, resulting in almost twice faster confirmation time and throughput. By treating transactions as a stream of nodes in an online graph, OptChain utilizes a lightweight and on-the-fly transaction placement method to group both related and soon-related transactions into the same shards. At the same time, OptChain maintains a temporal balance among shards to guarantee the high parallelism. Our comprehensive and large-scale simulation using Oversim P2P library confirms a significant boost in performance with up to 10 folds reduction in cross-shard transactions, more than twice reduction in confirmation time, and 50% increase in throughput. When combined with Omniledger sharding protocol, OptChain delivers a 6000 transactions per second throughput with 10.5s confirmation time.
△ Less
Submitted 18 October, 2021; v1 submitted 16 July, 2020;
originally announced July 2020.
-
A Blockchain-based Iterative Double Auction Protocol using Multiparty State Channels
Authors:
Truc D. T. Nguyen,
My T. Thai
Abstract:
Although the iterative double auction has been widely used in many different applications, one of the major problems in its current implementations is that they rely on a trusted third party to handle the auction process. This imposes the risk of single point of failures, monopoly, and bribery. In this paper, we aim to tackle this problem by proposing a novel decentralized and trustless framework…
▽ More
Although the iterative double auction has been widely used in many different applications, one of the major problems in its current implementations is that they rely on a trusted third party to handle the auction process. This imposes the risk of single point of failures, monopoly, and bribery. In this paper, we aim to tackle this problem by proposing a novel decentralized and trustless framework for iterative double auction based on blockchain. Our design adopts the smart contract and state channel technologies to enable a double auction process among parties that do not need to trust each other, while minimizing the blockchain transactions. In specific, we propose an extension to the original concept of state channels that can support multiparty computation. Then we provide a formal development of the proposed framework and prove the security of our design against adversaries. Finally, we develop a proof-of-concept implementation of our framework using Elixir and Solidity, on which we conduct various experiments to demonstrate its feasibility and practicality.
△ Less
Submitted 16 July, 2020;
originally announced July 2020.
-
Threat from being Social: Vulnerability Analysis of Social Network Coupled Smart Grid
Authors:
Tianyi Pan,
Subhankar Mishra,
Lan N. Nguyen,
Gunhee Lee,
Jungmin Kang,
Jungtaek Seo,
My T. Thai
Abstract:
Social Networks (SNs) have been gradually applied by utility companies as an addition to smart grid and are proved to be helpful in smoothing load curves and reducing energy usage. However, SNs also bring in new threats to smart grid: misinformation in SNs may cause smart grid users to alter their demand, resulting in transmission line overloading and in turn leading to catastrophic impact to the…
▽ More
Social Networks (SNs) have been gradually applied by utility companies as an addition to smart grid and are proved to be helpful in smoothing load curves and reducing energy usage. However, SNs also bring in new threats to smart grid: misinformation in SNs may cause smart grid users to alter their demand, resulting in transmission line overloading and in turn leading to catastrophic impact to the grid. In this paper, we discuss the interdependency in the social network coupled smart grid and focus on its vulnerability. That is, how much can the smart grid be damaged when misinformation related to it diffuses in SNs? To analytically study the problem, we propose the Misinformation Attack Problem in Social-Smart Grid (MAPSS) that identifies the top critical nodes in the SN, such that the smart grid can be greatly damaged when misinformation propagates from those nodes. This problem is challenging as we have to incorporate the complexity of the two networks concurrently. Nevertheless, we propose a technique that can explicitly take into account information diffusion in SN, power flow balance and cascading failure in smart grid integratedly when evaluating node criticality, based on which we propose various strategies in selecting the most critical nodes. Also, we introduce controlled load shedding as a protection strategy to reduce the impact of cascading failure. The effectiveness of our algorithms are demonstrated by experiments on IEEE bus test cases as well as the Pegase data set.
△ Less
Submitted 15 May, 2020;
originally announced May 2020.
-
Privacy Preserving Distributed Energy Trading
Authors:
Shangyu Xie,
Han Wang,
Yuan Hong,
My Thai
Abstract:
The smart grid incentivizes distributed agents with local generation (e.g., smart homes, and microgrids) to establish multi-agent systems for enhanced reliability and energy consumption efficiency. Distributed energy trading has emerged as one of the most important multi-agent systems on the power grid by enabling agents to sell their excessive local energy to each other or back to the grid. Howev…
▽ More
The smart grid incentivizes distributed agents with local generation (e.g., smart homes, and microgrids) to establish multi-agent systems for enhanced reliability and energy consumption efficiency. Distributed energy trading has emerged as one of the most important multi-agent systems on the power grid by enabling agents to sell their excessive local energy to each other or back to the grid. However, it requests all the agents to disclose their sensitive data (e.g., each agent's fine-grained local generation and demand load). In this paper, to the best of our knowledge, we propose the first privacy preserving distributed energy trading framework, Private Energy Market (PEM), in which all the agents privately compute an optimal price for their trading (ensured by a Nash Equilibrium), and allocate pairwise energy trading amounts without disclosing sensitive data (via novel cryptographic protocols). Specifically, we model the trading problem as a non-cooperative Stackelberg game for all the agents (i.e., buyers and sellers) to determine the optimal price, and then derive the pairwise trading amounts. Our PEM framework can privately perform all the computations among all the agents without a trusted third party. We prove the privacy, individual rationality, and incentive compatibility for the PEM framework. Finally, we conduct experiments on real datasets to validate the effectiveness and efficiency of the PEM.
△ Less
Submitted 25 April, 2020;
originally announced April 2020.
-
Advanced Intelligent Systems for Surgical Robotics
Authors:
Mai Thanh Thai,
Phuoc Thien Phan,
Shing Wong,
Nigel H. Lovell,
Thanh Nho Do
Abstract:
Surgical robots have had clinical use since the mid 1990s. Robot-assisted surgeries offer many benefits over the conventional approach including lower risk of infection and blood loss, shorter recovery, and an overall safer procedure for patients. The past few decades have shown many emerging surgical robotic platforms that can work in complex and confined channels of the internal human organs and…
▽ More
Surgical robots have had clinical use since the mid 1990s. Robot-assisted surgeries offer many benefits over the conventional approach including lower risk of infection and blood loss, shorter recovery, and an overall safer procedure for patients. The past few decades have shown many emerging surgical robotic platforms that can work in complex and confined channels of the internal human organs and improve the cognitive and physical skills of the surgeons during the operation. Advanced technologies for sensing, actuation, and intelligent control have enabled multiple surgical devices to simultaneously operate within the human body at low cost and with more efficiency. Despite advances, current surgical intervention systems are not able to execute autonomous tasks and make cognitive decisions that are analogous to that of humans. This paper will overview a historical development of surgery from conventional open to robotic-assisted approaches with discussion on the capabilities of advanced intelligent systems and devices that are currently implemented in existing surgical robotic systems. It will also revisit available autonomous surgical platforms with comments on the essential technologies, existing challenges, and suggestions for the future development of intelligent robotic-assisted surgical systems towards the achievement of fully autonomous operation.
△ Less
Submitted 1 January, 2020;
originally announced January 2020.
-
Cost-aware Targeted Viral Marketing: Approximation with Less Samples
Authors:
Canh V. Pham,
Hieu V. Duong,
My T. Thai
Abstract:
Cost-aware Targeted Viral Marketing (CTVM), a generalization of Influence Maximization (IM), has received a lot of attentions recently due to its commercial values. Previous approximation algorithms for this problem required a large number of samples to ensure approximate guarantee. In this paper, we propose an efficient approximation algorithm which uses fewer samples but provides the same theore…
▽ More
Cost-aware Targeted Viral Marketing (CTVM), a generalization of Influence Maximization (IM), has received a lot of attentions recently due to its commercial values. Previous approximation algorithms for this problem required a large number of samples to ensure approximate guarantee. In this paper, we propose an efficient approximation algorithm which uses fewer samples but provides the same theoretical guarantees based on generating and using important samples in its operation. Experiments on real social networks show that our proposed method outperforms the state-of-the-art algorithm which provides the same approximation ratio in terms of the number of required samples and running time.
△ Less
Submitted 8 February, 2020; v1 submitted 2 October, 2019;
originally announced October 2019.