-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Submodular Cost Submodular Cover with an Approximate Oracle
Authors:
Victoria G. Crawford,
Alan Kuhnle,
My T. Thai
Abstract:
In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, wh…
▽ More
In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.
△ Less
Submitted 1 August, 2019;
originally announced August 2019.
-
c-Eval: A Unified Metric to Evaluate Feature-based Explanations via Perturbation
Authors:
Minh N. Vu,
Truc D. Nguyen,
NhatHai Phan,
Ralucca Gera,
My T. Thai
Abstract:
In many modern image-classification applications, understanding the cause of model's prediction can be as critical as the prediction's accuracy itself. Various feature-based local explanations generation methods have been designed to give us more insights on the decision of complex classifiers. Nevertheless, there is no consensus on evaluating the quality of different explanations. In response to…
▽ More
In many modern image-classification applications, understanding the cause of model's prediction can be as critical as the prediction's accuracy itself. Various feature-based local explanations generation methods have been designed to give us more insights on the decision of complex classifiers. Nevertheless, there is no consensus on evaluating the quality of different explanations. In response to this lack of comprehensive evaluation, we introduce the c-Eval metric and its corresponding framework to quantify the feature-based local explanation's quality. Given a classifier's prediction and the corresponding explanation on that prediction, c-Eval is the minimum-distortion perturbation that successfully alters the prediction while keeping the explanation's features unchanged. We then demonstrate how c-Eval can be computed using some modifications on existing adversarial generation libraries. To show that c-Eval captures the importance of input's features, we establish the connection between c-Eval and the features returned by explainers in affine and nearly-affine classifiers. We then introduce the c-Eval plot, which not only displays a strong connection between c-Eval and explainers' quality, but also helps automatically determine explainer's parameters. Since the generation of c-Eval relies on adversarial generation, we provide a demo of c-Eval on adversarial-robust models and show that the metric is applicable in those models. Finally, extensive experiments of explainers on different datasets are conducted to support the adoption of c-Eval in evaluating explainers' performance.
△ Less
Submitted 10 August, 2020; v1 submitted 5 June, 2019;
originally announced June 2019.
-
Heterogeneous Gaussian Mechanism: Preserving Differential Privacy in Deep Learning with Provable Robustness
Authors:
NhatHai Phan,
Minh Vu,
Yang Liu,
Ruoming Jin,
Dejing Dou,
Xintao Wu,
My T. Thai
Abstract:
In this paper, we propose a novel Heterogeneous Gaussian Mechanism (HGM) to preserve differential privacy in deep neural networks, with provable robustness against adversarial examples. We first relax the constraint of the privacy budget in the traditional Gaussian Mechanism from (0, 1] to (0, \infty), with a new bound of the noise scale to preserve differential privacy. The noise in our mechanism…
▽ More
In this paper, we propose a novel Heterogeneous Gaussian Mechanism (HGM) to preserve differential privacy in deep neural networks, with provable robustness against adversarial examples. We first relax the constraint of the privacy budget in the traditional Gaussian Mechanism from (0, 1] to (0, \infty), with a new bound of the noise scale to preserve differential privacy. The noise in our mechanism can be arbitrarily redistributed, offering a distinctive ability to address the trade-off between model utility and privacy loss. To derive provable robustness, our HGM is applied to inject Gaussian noise into the first hidden layer. Then, a tighter robustness bound is proposed. Theoretical analysis and thorough evaluations show that our mechanism notably improves the robustness of differentially private deep neural networks, compared with baseline approaches, under a variety of model attacks.
△ Less
Submitted 2 June, 2019;
originally announced June 2019.
-
Scalable Differential Privacy with Certified Robustness in Adversarial Learning
Authors:
NhatHai Phan,
My T. Thai,
Han Hu,
Ruoming Jin,
Tong Sun,
Dejing Dou
Abstract:
In this paper, we aim to develop a scalable algorithm to preserve differential privacy (DP) in adversarial learning for deep neural networks (DNNs), with certified robustness to adversarial examples. By leveraging the sequential composition theory in DP, we randomize both input and latent spaces to strengthen our certified robustness bounds. To address the trade-off among model utility, privacy lo…
▽ More
In this paper, we aim to develop a scalable algorithm to preserve differential privacy (DP) in adversarial learning for deep neural networks (DNNs), with certified robustness to adversarial examples. By leveraging the sequential composition theory in DP, we randomize both input and latent spaces to strengthen our certified robustness bounds. To address the trade-off among model utility, privacy loss, and robustness, we design an original adversarial objective function, based on the post-processing property in DP, to tighten the sensitivity of our model. A new stochastic batch training is proposed to apply our mechanism on large DNNs and datasets, by bypassing the vanilla iterative batch-by-batch training in DP DNNs. An end-to-end theoretical analysis and evaluations show that our mechanism notably improves the robustness and scalability of DP DNNs.
△ Less
Submitted 15 September, 2020; v1 submitted 23 March, 2019;
originally announced March 2019.
-
Exploring Spatial, Temporal, and Logical Attacks on the Bitcoin Network
Authors:
Muhammad Saad,
Victor Cook,
Lan Nguyen,
My T. Thai,
Aziz Mohaisen
Abstract:
In this paper, we explore the partitioning attacks on the Bitcoin network, which is shown to exhibit spatial bias, and temporal and logical diversity. Through data-driven study we highlight: 1) the centralization of Bitcoin nodes across autonomous systems, indicating the possibility of BGP attacks, 2)the non-uniform consensus among nodes, that can be exploited to partition the network, and 3)the d…
▽ More
In this paper, we explore the partitioning attacks on the Bitcoin network, which is shown to exhibit spatial bias, and temporal and logical diversity. Through data-driven study we highlight: 1) the centralization of Bitcoin nodes across autonomous systems, indicating the possibility of BGP attacks, 2)the non-uniform consensus among nodes, that can be exploited to partition the network, and 3)the diversity in the Bitcoin software usage that can lead to privacy attacks. Atop the prior work, which focused on spatial partitioning, our work extends the analysis of the Bitcoin network to understand the temporal and logical effects on the robustness of the Bitcoin network.
△ Less
Submitted 10 February, 2019;
originally announced February 2019.
-
Network Resilience Assessment via QoS Degradation Metrics: An Algorithmic Approach
Authors:
Lan N. Nguyen,
My T. Thai
Abstract:
This paper focuses on network resilience to perturbation of edge weight. Other than connectivity, many network applications nowadays rely upon some measure of network distance between a pair of connected nodes. In these systems, a metric related to network functionality is associated to each edge. A pair of nodes only being functional if the weighted, shortest-path distance between the pair is bel…
▽ More
This paper focuses on network resilience to perturbation of edge weight. Other than connectivity, many network applications nowadays rely upon some measure of network distance between a pair of connected nodes. In these systems, a metric related to network functionality is associated to each edge. A pair of nodes only being functional if the weighted, shortest-path distance between the pair is below a given threshold \texttt{T}. Consequently, a natural question is on which degree the change of edge weights can damage the network functionality? With this motivation, we study a new problem, \textit{Quality of Service Degradation}: given a set of pairs, find a minimum budget to increase the edge weights which ensures the distance between each pair exceeds $\mathtt{T}$. We introduce four algorithms with theoretical performance guarantees for this problem. Each of them has its own strength in trade-off between effectiveness and running time, which are illustrated both in theory and comprehensive experimental evaluation.
△ Less
Submitted 5 February, 2019;
originally announced February 2019.