On maximal dominating forest and four colors theorem of planar graph

For a given graph $G(V,E)$ and one of its dominating set $S$, the subgraph $Gleft[Sright]$ induced by $S$ is a called a dominating tree if $Gleft[Sright]$ is a tree. Not all graphs has a dominating tree, we will show that a graph without cut vertices has at least one dominating tree. Analogously, if $Gleft[Sright]$ is a forest, then it is called a dominating forest. As special structures of graphs, dominating tree and dominating forest have many interesting application, and we will focus on its application on the problem of planar graph coloring.

Integer-arithmetic-only Certified Robustness for Quantized Neural Networks

Adversarial data examples have drawn significant attention from the machine learning and security communities. A line of work on tackling adversarial examples is certified robustness via randomized smoothing that can provide a theoretical robustness guarantee. However, such a mechanism usually uses floating-point arithmetic for calculations in inference and requires large memory footprints and daunting computational costs. These defensive models cannot run efficiently on edge devices nor be deployed on integer-only logical units such as Turing Tensor Cores or integer-only ARM processors. To overcome these challenges, we propose an integer randomized smoothing approach with quantization to convert any classifier into a new smoothed classifier, which uses integer-only arithmetic for certified robustness against adversarial perturbations. We prove a tight robustness guarantee under L2-norm for the proposed approach. We show our approach can obtain a comparable accuracy and 4x~5x speedup over floating-point arithmetic certified robust methods on general-purpose CPUs and mobile devices on two distinct datasets (CIFAR-10 and Caltech-101).

SemiFed: Semi-supervised Federated Learning with Consistency and Pseudo-Labeling

Federated learning enables multiple clients, such as mobile phones and organizations, to collaboratively learn a shared model for prediction while protecting local data privacy. However, most recent research and applications of federated learning assume that all clients have fully labeled data, which is impractical in real-world settings. In this work, we focus on a new scenario for cross-silo federated learning, where data samples of each client are partially labeled. We borrow ideas from semi-supervised learning methods where a large amount of unlabeled data is utilized to improve the models accuracy despite limited access to labeled examples. We propose a new framework dubbed SemiFed that unifies two dominant approaches for semi-supervised learning: consistency regularization and pseudo-labeling. SemiFed first applies advanced data augmentation techniques to enforce consistency regularization and then generates pseudo-labels using the models predictions during training. SemiFed takes advantage of the federation so that for a given image, the pseudo-label holds only if multiple models from different clients produce a high-confidence prediction and agree on the same label. Extensive experiments on two image benchmarks demonstrate the effectiveness of our approach under both homogeneous and heterogeneous data distribution settings

SINGA-Easy: An Easy-to-Use Framework for MultiModal Analysis

Deep learning has achieved great success in a wide spectrum of multimedia applications such as image classification, natural language processing and multimodal data analysis. Recent years have seen the development of many deep learning frameworks that provide a high-level programming interface for users to design models, conduct training and deploy inference. However, it remains challenging to build an efficient end-to-end multimedia application with most existing frameworks. Specifically, in terms of usability, it is demanding for non-experts to implement deep learning models, obtain the right settings for the entire machine learning pipeline, manage models and datasets, and exploit external data sources all together. Further, in terms of adaptability, elastic computation solutions are much needed as the actual serving workload fluctuates constantly, and scaling the hardware resources to handle the fluctuating workload is typically infeasible. To address these challenges, we introduce SINGA-Easy, a new deep learning framework that provides distributed hyper-parameter tuning at the training stage, dynamic computational cost control at the inference stage, and intuitive user interactions with multimedia contents facilitated by model explanation. Our experiments on the training and deployment of multi-modality data analysis applications show that the framework is both usable and adaptable to dynamic inference loads. We implement SINGA-Easy on top of Apache SINGA and demonstrate our system with the entire machine learning life cycle.

Sample Efficient Reinforcement Learning via Model-Ensemble Exploration and Exploitation

Model-based deep reinforcement learning has achieved success in various domains that require high sample efficiencies, such as Go and robotics. However, there are some remaining issues, such as planning efficient explorations to learn more accurate dynamic models, evaluating the uncertainty of the learned models, and more rational utilization of models. To mitigate these issues, we present MEEE, a model-ensemble method that consists of optimistic exploration and weighted exploitation. During exploration, unlike prior methods directly selecting the optimal action that maximizes the expected accumulative return, our agent first generates a set of action candidates and then seeks out the optimal action that takes both expected return and future observation novelty into account. During exploitation, different discounted weights are assigned to imagined transition tuples according to their model uncertainty respectively, which will prevent model predictive error propagation in agent training. Experiments on several challenging continuous control benchmark tasks demonstrated that our approach outperforms other model-free and model-based state-of-the-art methods, especially in sample complexity.

Federated Graph Classification over Non-IID Graphs

Federated learning has emerged as an important paradigm for training machine learning models in different domains. For graph-level tasks such as graph classification, graphs can also be regarded as a special type of data samples, which can be collected and stored in separate local systems. Similar to other domains, multiple local systems, each holding a small set of graphs, may benefit from collaboratively training a powerful graph mining model, such as the popular graph neural networks (GNNs). To provide more motivation towards such endeavors, we analyze real-world graphs from different domains to confirm that they indeed share certain graph properties that are statistically significant compared with random graphs. However, we also find that different sets of graphs, even from the same domain or same dataset, are non-IID regarding both graph structures and node features. To handle this, we propose a graph clustered federated learning (GCFL) framework that dynamically finds clusters of local systems based on the gradients of GNNs, and theoretically justify that such clusters can reduce the structure and feature heterogeneity among graphs owned by the local systems. Moreover, we observe the gradients of GNNs to be rather fluctuating in GCFL which impedes high-quality clustering, and design a gradient sequence-based clustering mechanism based on dynamic time warping (GCFL+). Extensive experimental results and in-depth analysis demonstrate the effectiveness of our proposed frameworks.

AMA-GCN: Adaptive Multi-layer Aggregation Graph Convolutional Network for Disease Prediction

Recently, Graph Convolutional Networks (GCNs) have proven to be a powerful mean for Computer Aided Diagnosis (CADx). This approach requires building a population graph to aggregate structural information, where the graph adjacency matrix represents the relationship between nodes. Until now, this adjacency matrix is usually defined manually based on phenotypic information. In this paper, we propose an encoder that automatically selects the appropriate phenotypic measures according to their spatial distribution, and uses the text similarity awareness mechanism to calculate the edge weights between nodes. The encoder can automatically construct the population graph using phenotypic measures which have a positive impact on the final results, and further realizes the fusion of multimodal information. In addition, a novel graph convolution network architecture using multi-layer aggregation mechanism is proposed. The structure can obtain deep structure information while suppressing over-smooth, and increase the similarity between the same type of nodes. Experimental results on two databases show that our method can significantly improve the diagnostic accuracy for Autism spectrum disorder and breast cancer, indicating its universality in leveraging multimodal data for disease prediction.

Average-Reward Reinforcement Learning with Trust Region Methods

Most of reinforcement learning algorithms optimize the discounted criterion which is beneficial to accelerate the convergence and reduce the variance of estimates. Although the discounted criterion is appropriate for certain tasks such as financial related problems, many engineering problems treat future rewards equally and prefer a long-run average criterion. In this paper, we study the reinforcement learning problem with the long-run average criterion. Firstly, we develop a unified trust region theory with discounted and average criteria. With the average criterion, a novel performance bound within the trust region is derived with the Perturbation Analysis (PA) theory. Secondly, we propose a practical algorithm named Average Policy Optimization (APO), which improves the value estimation with a novel technique named Average Value Constraint. To the best of our knowledge, our work is the first one to study the trust region approach with the average criterion and it complements the framework of reinforcement learning beyond the discounted criterion. Finally, experiments are conducted in the continuous control environment MuJoCo. In most tasks, APO performs better than the discounted PPO, which demonstrates the effectiveness of our approach.

Odds Ratios are far from portable: A call to use realistic models for effect variation in meta-analysis

Objective: Recently Doi et al. argued that risk ratios should be replaced with odds ratios in clinical research. We disagreed, and empirically documented the lack of portability of odds ratios, while Doi et al. defended their position. In this response we highlight important errors in their position. Study Design and Setting: We counter Doi et al.s arguments by further examining the correlations of odds ratios, and risk ratios, with baseline risks in 20,198 meta-analyses from the Cochrane Database of Systematic Reviews. Results: Doi et al.s claim that odds ratios are portable is invalid because 1) their reasoning is circular: they assume a model under which the odds ratio is constant and show that under such a model the odds ratio is portable; 2) the method they advocate to convert odds ratios to risk ratios is biased; 3) their empirical example is readily-refuted by counter-examples of meta-analyses in which the risk ratio is portable but the odds ratio isnt; and 4) they fail to consider the causal determinants of meta-analytic inclusion criteria: Doi et al. mistakenly claim that variation in odds ratios with different baseline risks in meta-analyses is due to collider bias. Empirical comparison between the correlations of odds ratios, and risk ratios, with baseline risks show that the portability of odds ratios and risk ratios varies across settings. Conclusion: The suggestion to replace risk ratios with odds ratios is based on circular reasoning and a confusion of mathematical and empirical results. It is especially misleading for meta-analyses and clinical guidance. Neither the odds ratio nor the risk ratio is universally portable. To address this lack of portability, we reinforce our suggestion to report variation in effect measures conditioning on modifying factors such as baseline risk; understanding such variation is essential to patient-centered practice.

CREAMS: Copyrighted Cloud Media Sharing

The advent of the big data era drives the media data owner to seek help from the cloud platform for data hosting and sharing. Sharing media data through the cloud suffers three key security/privacy problems including the leakage of data privacy, the infringement on the data owners copyright, and the infringement on the users right. Existing techniques such as attribute-based encryption, proxy re-encryption, and asymmetric fingerprinting are insufficient to solve all three problems. In this work, we consider the scheme design of being capable of addressing these three problems simultaneously. Associating the additive homomorphic proxy re-encryption technique with the asymmetric fingerprinting based on user-side embedding, we bring forward two novel cloud media sharing schemes: CREAMS-I and CREAMS-II. Among them, CREAMS-II has better security performance, while CREAMS-I has more outstanding cloud-side efficiency. It is demonstrated that both proposed schemes can solve the existing three problems well and have advantages over existing peers. In addition, these two schemes can also be seen as an instantiation of privacy-preserving outsourcing of asymmetric fingerprinting, from which the owner can reap substantial savings in local storage, communication, and computing resources. The feasibility of CREAMS-I and CREAMS-II is also verified by simulation.