Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel and distributed systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, poor scale-out capability, and possibly inaccurate results. In this article, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. The execution engine of T-FSM supports both intra-machine parallelism and inter-machine parallelism. For intra-machine parallelism, T-FSM adopts a novel task-based execution model to ensure high multithreading concurrency, bounded memory consumption, and effective load balancing. For inter-machine parallelism, T-FSM ensures good scale-out performance with a lightweight pattern rebalancing approach that reduces workload skewness of pattern evaluations among machines. To avoid recomputing the contexts for migrated patterns, we design a novel context cache table to support concurrent and asynchronous requesting and caching of remote context data, which can timely evict and garbage collect used pattern contexts that are no longer needed to keep memory consumption bounded. Extensive experiments show that T-FSM is orders of magnitude faster than existing state-of-the-art parallel systems (more than 10×, 51×, 131×, 55× speedup over ScaleMine, DistGraph, Pangolin and Peregrine, respectively) and distributed systems (more than 42× and 88× over ScaleMine and DistGraph, respectively) for frequent subgraph pattern mining, and it scales out satisfactorily to 512 CPU cores on the Polaris supercomputer at Argonne National Laboratory.

Accurate and prompt mapping of flood extent is important for effective disaster management. Prior terrain-guided methods utilizing digital elevation model (DEM) data to improve segmentation quality, but are only applicable to small areas with restricted assumptions. We propose ZoneGraph, a scalable flood mapping approach that is generally applicable to any area. Since water level varies a lot from upstream to downstream, and an Earth image may contain multiple river channels or branches, ZoneGraph partitions an Earth image into localized zones each with a consistent water level for intra-region inference using hidden Markov trees (HMTs), and uses a zone adjacency graph for inter-zone regularization to enforce flow direction consistency across adjacent zones. Parallelization techniques are applied to speed up the zonal water level computations. Experiments show ZoneGraph achieves higher accuracy than existing methods, scale to a large area with 24,805 × 40,129 pixels, and yields up to 14.3× parallelization speedup on 32 threads.

Spatial join is a fundamental operation in many applications such as geographic information system (GIS) and simulation sciences. Recent works advocate in-memory spatial join for efficiency, but they require entire datasets to be loaded into memory, and they were only tested on small to medium-sized datasets. In this paper, we target out-of-core parallel spatial join to handle massive data, and surprisingly, we find that our solution can be orders of magnitude faster than the state-of-the-art in-memory solutions. Our system, called T-Spatial, decomposes a spatial-join job into tasks to expose massive parallelism opportunities. A BFS-DFS hybrid execution model is designed to enable memory-bounded high-throughput task processing, which exploits spatial locality to reuse cached data as much as possible to reduce disk IOs. T-Spatial also effectively overlaps computations with disk IOs by prefetching, and integrates a few optimization techniques including work stealing to avoid stragglers, write contention mitigation under multithreading, and a NUMA-aware design. Extensive experiments show that T-Spatial significantly outperforms state-of-the-art in-memory approaches (e.g., PBSM, TOUCH) and cloud-based parallel spatial systems (e.g., Apache Sedona) with 2–3 orders of magnitude of speedup ratio, and it is the first in the literature to test spatial joins on billion-scale datasets.

Applying blockchain technology to a distributed Internet-of-Things (IoT) environment has emerged as a promising solution for enhancing system data security and mitigating the risk of privacy leakage. Meanwhile, to meet the computational demands of blockchain, IoT devices can offload their computational tasks to nearby edge nodes or even the cloud side, thereby compensating for their insufficient computational resources and available energy. This paper addresses the issue of computational task offloading for heterogeneous IoT devices in a distributed and dynamic environment. It first considers factors such as the delay in IoT execution of blockchain computations, energy consumption costs, and the payable budget required for offloading, and establishes a time-series optimization model. Subsequently, a swarm intelligence method is introduced into Multi-agent Reinforcement Learning to solve the optimization problem, effectively overcoming the challenges faced by purely Reinforcement Learning (RL)-based method, which are susceptible to hyperparameter tuning and prone to getting stuck in local optima, leading to sub-optimal solutions. Comparative experiments with several representative baseline methods shown that the proposed computational task offloading method exhibits relatively better convergence performance, solution quality across different network scales, and robustness.

The growing reliance on deep learning models in safety-critical domains such as healthcare and autonomous navigation underscores the need for defenses that are both robust to adversarial perturbations and transparent in their decision-making. In this paper, we identify a connection between interpretability and robustness that can be directly leveraged during training. Specifically, we observe that spurious, unstable, or semantically irrelevant features identified through Local Interpretable Model-Agnostic Explanations (LIME) contribute disproportionately to adversarial vulnerability. Building on this insight, we introduce an attribution-guided refinement framework that transforms LIME from a passive diagnostic into an active training signal. Our method systematically suppresses spurious features using feature masking, sensitivity-aware regularization, and adversarial augmentation in a closed-loop refinement pipeline. This approach does not require additional datasets or model architectures and integrates seamlessly into standard adversarial training. Theoretically, we derive an attribution-aware lower bound on adversarial distortion that formalizes the link between explanation alignment and robustness. Empirical evaluations on CIFAR-10, CIFAR-10-C, and CIFAR-100 demonstrate substantial improvements in adversarial robustness and out-of-distribution generalization.

Machine unlearning (MU) aims to remove the influence of specific data points from trained models, enhancing compliance with privacy regulations. However, the vulnerability of basic MU models to malicious unlearning requests in adversarial learning environments has been largely overlooked. Existing adversarial MU attacks suffer from three key limitations: inflexibility due to pre-defined attack targets, inefficiency in handling multiple attack requests, and instability caused by non-convex loss functions. To address these challenges, we propose a Flexible, Efficient, and Stable Attack (DDPA). First, leveraging Carathéodory's theorem, we introduce a convex polyhedral approximation to identify points in the loss landscape where convexity approximately holds, ensuring stable attack performance. Second, inspired by simplex theory and John's theorem, we develop a regular simplex detection technique that maximizes coverage over the parameter space, improving attack flexibility and efficiency. We theoretically derive the proportion of the effective parameter space occupied by the constructed simplex. We evaluate the attack success rate of our DDPA method on real datasets against state-of-the-art machine unlearning attack methods. Our source code is available at https://github.com/zzz0134/DDPA.

Flood extent mapping is crucial for disaster response and damage assessment. While Earth imagery and terrain data (in the form of DEM) are now readily available, there are few flood annotation data for training machine learning models, which hinders the automated mapping of flooded areas. We propose ALFA, an interactive active-learning-based approach to minimize the annotators' efforts when preparing the ground-truth flood map in a satellite image. ALFA calibrates the prediction consistency of a segmentation model (1) across training cycles and (2) for various data augmentations. The two consistencies are integrated into the design of both the acquisition function and the loss function to enhance the robustness of active learning with limited annotation inputs. ALFA recommends those superpixels that the underlying model is most uncertain about, and users can annotate their pixels with minimal clicks with the help of elevation guidance. Extensive experiments on various regions hit by flooding show that we can improve the annotation time from hours to around 20 minutes. ALFA is open sourced at https://github.com/saugatadhikari/alfa.

Adversarial examples reveal critical vulnerabilities in deep neural networks by exploiting their sensitivity to imperceptible input perturbations. While adversarial training remains the predominant defense strategy, it often incurs significant computational cost and may compromise clean-data accuracy. In this work, we investigate an architectural approach to adversarial robustness by embedding group-equivariant convolutions—specifically, rotation- and scale-equivariant layers—into standard convolutional neural networks (CNNs). These layers encode symmetry priors that align model behavior with structured transformations in the input space, promoting smoother decision boundaries and greater resilience to adversarial attacks. We propose and evaluate two symmetry-aware architectures: a parallel design that processes standard and equivariant features independently before fusion, and a cascaded design that applies equivariant operations sequentially. Theoretically, we demonstrate that such models reduce hypothesis space complexity, regularize gradients, and yield tighter certified robustness bounds under the CLEVER (Cross Lipschitz Extreme Value for nEtwork Robustness) framework. Empirically, our models consistently improve adversarial robustness and generalization across CIFAR-10, CIFAR-100, and CIFAR-10C under both FGSM and PGD attacks, without requiring adversarial training. These findings underscore the potential of symmetry-enforcing architectures as efficient and principled alternatives to data augmentation-based defenses.

Federated Learning (FL) is a promising distributed machine learning approach that enables collaborative training of a global model using multiple edge devices. The data distributed among the edge devices are highly heterogeneous. Thus, FL faces the challenge of data distribution and heterogeneity, where non-Independent and Identically Distributed (non-IID) data across edge devices may yield in significant accuracy drop. Furthermore, the limited computation and communication capabilities of edge devices increase the likelihood of stragglers, thus leading to slow model convergence. In this article, we propose the FedDHAD FL framework, which comes with two novel methods: dynamic heterogeneous model aggregation (FedDH) and adaptive dropout (FedAD). FedDH dynamically adjusts the weights of each local model within the model aggregation process based on the non-IID degree of heterogeneous data to deal with the statistical data heterogeneity. FedAD performs neuron-adaptive operations in response to heterogeneous devices to improve accuracy while achieving superb efficiency. The combination of these two methods makes FedDHAD significantly outperform state-of-the-art solutions in terms of accuracy (up to 6.7% higher), efficiency (up to 2.02 times faster), and computation cost (up to 15.0% smaller).

As a promising approach to deal with distributed data, Federated Learning (FL) achieves major advancements in recent years. FL enables collaborative model training by exploiting the raw data dispersed in multiple edge devices. However, the data is generally non-independent and identically distributed, i.e., statistical heterogeneity, and the edge devices significantly differ in terms of both computation and communication capacity, i.e., system heterogeneity. The statistical heterogeneity leads to severe accuracy degradation while the system heterogeneity significantly prolongs the training process. In order to address the heterogeneity issue, we propose an Asynchronous Staleness-aware Model Update FL framework, i.e., FedASMU, with two novel methods. First, we propose an asynchronous FL system model with a dynamical model aggregation method between updated local models and the global model on the server for superior accuracy and high efficiency. Then, we propose an adaptive local model adjustment method by aggregating the fresh global model with local models on devices to further improve the accuracy. Extensive experimentation with 6 models and 5 public datasets demonstrates that FedASMU significantly outperforms baseline approaches in terms of accuracy (0.60% to 23.90% higher) and efficiency (3.54% to 97.98% faster).

Flood mapping on Earth imagery is crucial for disaster management, but its efficacy is hampered by the lack of high-quality training labels. Given high-resolution Earth imagery with coarse and noisy training labels, a base deep neural network model, and a spatial knowledge base with label constraints, our problem is to infer the true high-resolution labels while training neural network parameters. Traditional methods are largely based on specific physical properties and thus fall short of capturing the rich domain constraints expressed by symbolic logic. Neural-symbolic models can capture rich domain knowledge, but existing methods do not address the unique spatial challenges inherent in flood mapping on high-resolution imagery. To fill this gap, we propose a spatial-logic-aware weakly supervised learning framework. Our framework integrates symbolic spatial logic inference into probabilistic learning in a weakly supervised setting. To reduce the time costs of logic inference on vast high-resolution pixels, we propose a multi-resolution spatial reasoning algorithm to infer true labels while training neural network parameters. Evaluations of real-world flood datasets show that our model outperforms several baselines in prediction accuracy. The code is available at https://github.com/spatialdatasciencegroup/SLWSL.

Mining dense subgraphs from a big graph is important in applications such as community (or module) detection in social (or biological) networks. While most dense structures are defined on undirected graphs, recent efforts have generalized these notions to directed graphs. In this demonstration paper, we present DirDense, an interactive tool that makes it easy for end-users to mine dense structures from a big directed graph. DirDense currently supports the mining of maximal (γ1, γ2)-quasi-cliques, maximal (k 1,k 1)-plexes, and the directed densest subgraph. DirDense facilitates parameter tuning for each type of the structure-mining tasks, and provides intuitive interfaces to visualize and examine the dense directed structures. Using real-world data, we showcase how users can mine dense directed structures by parameter tuning in DirDense, and how they can conveniently examine these structures and cascade the mining tasks to find progressively larger dense subgraphs more quickly.

Explaining black-box models is fundamental to gaining trust and deploying these models in real applications. As existing explanation methods have been shown to lack robustness against adversarial perturbations, there has been a growing interest in generating robust explanations. However, existing works resort to empirical defense strategies and these heuristic methods fail against powerful adversaries. In this paper, we certify the robustness of explanations motivated by the success of randomized smoothing. Specifically, we compute a tight radius in which the robustness of the explanation is certified. While a challenge is how to formulate the robustness of the explanation mathematically, we quantize the explanation into discrete spaces to mimic classification in randomized smoothing. To address the high computational cost of randomized smoothing, we introduce randomized gradient smoothing. Also, we explore the robustness of the semantic explanation by certifying the robustness of capsules. In the experiment, we demonstrate the effectiveness of our method on benchmark datasets from the perspectives of post-hoc explanation and semantic explanation respectively. Our work is a promising step towards filling the gap between the theoretical robustness bound and empirical explanations. Our code has been released at https://github.com/NKUShaw/CertifiedExplanation.

As a promising paradigm to collaboratively train models with decentralized data, Federated Learning (FL) can be exploited to fine-tune Large Language Models (LLMs).While LLMs correspond to huge size, the scale of the training data significantly increases, which leads to tremendous amounts of computation and communication costs.The training data is generally non-Independent and Identically Distributed (non-IID), which requires adaptive data processing within each device.Although Low-Rank Adaptation (LoRA) can significantly reduce the scale of parameters to update in the fine-tuning process, it still takes unaffordable time to transfer the low-rank parameters of all the layers in LLMs.In this paper, we propose a Fisher Information-based Efficient Curriculum Federated Learning framework (FibecFed) with two novel methods, i.e., adaptive federated curriculum learning and efficient sparse parameter update.First, we propose a fisher informationbased method to adaptively sample data within each device to improve the effectiveness of the FL fine-tuning process.Second, we dynamically select the proper layers for global aggregation and sparse parameters for local update with LoRA so as to improve the efficiency of the FL fine-tuning process.Extensive experimental results based on 10 datasets demonstrate that FibecFed yields excellent performance (up to 45.35% in terms of accuracy) and superb fine-tuning speed (up to 98.61% faster) compared with 17 baseline approaches).Our code will be publicly available.

In this demonstration paper, we describe FSM-Explorer, an interactive tool that makes it easier for end-users to mine frequent subgraph patterns from a big graph$G$, and to explore the subgraph instances in$G$that match the patterns. FSM-Explorer not only supports the popular MNI support measure, but also the recently proposed Fraction-Score measure that is more accurate. Its backend engine is built on top of our recently developed T-FSM system that ensures high concurrency, bounded memory consumption, and effective load balancing. Using real-world data, we showcase how users can mine frequent subgraph patterns by parameter tuning in FSM-Explorer, and how they can conveniently examine the many matched instances in$G$one batch at a time to improve productivity.

Subgraph search problems such as maximal clique enumeration and subgraph matching generate a search-space tree which is traversed in depth-first manner by serial backtracking algorithms that are recursive. Since Jenkins et al. reported the backtracking paradigm to be sub-optimal for GPU acceleration, breadth-first traversal of the search-space tree is widely adopted by GPU algorithms. However, they produce a lot of intermediate subgraphs that exhaust the GPU device memory. Recent works revive the depth-first backtracking paradigm for GPU acceleration, where each warp is a basic processing unit with its own stack in device memory for subgraph backtracking. However, they adopt complicated methods for load balancing that incur a lot of overheads. They also use hardcoded fixed space for stacks that is determined ad-hoc and may lead to inaccuracy when the allocated space is insufficient. In this paper, we use subgraph matching as a case study to propose novel depth-first GPU solutions to address the above problems. Our approach, called T-DFS, decomposes computation into independent tasks that process search-space subtrees, which are managed by an efficient lock-free circular task queue. Tasks are distributed to different warps for parallel processing, and a novel timeout mechanism is used to eliminate straggler tasks to ensure load balancing. We also support flexible and fine-grained dynamic memory allocation for stack spaces to avoid the stack space allocation pitfalls of existing works. Extensive experiments on real graphs show that T-DFS significantly outperforms existing depth-first GPU solutions for the subgraph matching application.

Finding all those subgraphs of a big graph that satisfy certain conditions (aka. subgraph finding) is useful in many applications such as community detection and subgraph matching. These problems often generate a search-space tree with size exponential to the size of the input graph. GPUs with thousands of cores are a natural choice to speed up subgraph finding, but existing GPU solutions either conduct BFS on the search-space tree which leads to memory overflow due to intermediate subgraph-size explosion, or they conduct DFS on the search-space tree which is memory-efficient but can be 2 orders of magnitude slower than a BFS solution. In this paper, we present$\mathbf{G}^{2}$-AIMD, a subgraph-centric framework for efficient subgraph Search on GPUs, which enjoys the efficiency of BFS on the search-space tree, while avoids intermediate subgraph-size explosion with novel system designs such as adaptive chunk-size adjustment and host-memory subgraph buffering, inspired by the additive-increase/multiplicative-decrease (AIMD) algorithm in TCP congestion control.$\mathrm{G}^{2}$-AIMD provides a convenient subgraph-centric programming interface to facilitate the implementation of subgraph finding algorithms on top, so as to enjoy the above performance merits.$\mathbf{G}^{2}{-}$AIMD also supports multi-GPU execution where each GPU only needs to load a fraction of the input graph. To demonstrate the efficiency and scalability of$\mathbf{G}^{2}$-AIMD, two algorithms were implemented on top with additional optimization techniques, and they significantly outperform the existing GPU solutions.

Graph matching in the setting of federated learning is still an open problem. This paper proposes an unsupervised federated graph matching algorithm, UFGM, for inferring matched node pairs on different graphs across clients while maintaining privacy requirement, by leveraging graphlet theory and trust region optimization. First, the nodes’ graphlet features are captured to generate pseudo matched node pairs on different graphs across clients as pseudo training data for tackling the dilemma of unsupervised graph matching in federated setting and leveraging the strength of supervised graph matching. An approximate graphlet enumeration method is proposed to sample a small number of graphlets and capture nodes’ graphlet features. Theoretical analysis is conducted to demonstrate that the approximate method is able to maintain the quality of graphlet estimation while reducing its expensive cost. Second, we propose a separate trust region algorithm for pseudo supervised federated graph matching while maintaining the privacy constraints. In order to avoid expensive cost of the second-order Hessian computation in the trust region algorithm, we propose two weak quasi-Newton conditions to construct a positive definite scalar matrix as the Hessian approximation with only first-order gradients. We theoretically derive the error introduced by the separate trust region due to the Hessian approximation and conduct the convergence analysis of the approximation method.

Federated Learning (FL) has achieved significant achievements recently, enabling collaborative model training on distributed data over edge devices. Iterative gradient or model exchanges between devices and the centralized server in the standard FL paradigm suffer from severe efficiency bottlenecks on the server. While enabling collaborative training without a central server, existing decentralized FL approaches either focus on the synchronous mechanism that deteriorates FL convergence or ignore device staleness with an asynchronous mechanism, resulting in inferior FL accuracy. In this paper, we propose an Asynchronous Efficient Decentralized FL framework, i.e., AEDFL, in heterogeneous environments with three unique contributions. First, we propose an asynchronous FL system model with an efficient model aggregation method for improving the FL convergence. Second, we propose a dynamic staleness-aware model update approach to achieve superior accuracy. Third, we propose an adaptive sparse training method to reduce communication and computation costs without significant accuracy degradation. Extensive experimentation on four public datasets and four models demonstrates the strength of AEDFL in terms of accuracy (up to 16.3% higher), efficiency (up to 92.9% faster), and computation costs (up to 42.3% lower).

Despite achieving remarkable performance, Federated Learning (FL) encounters two important problems, i.e., low training efficiency and limited computational resources. In this article, we propose a new FL framework, i.e., FedDUMAP, with three original contributions, to leverage the shared insensitive data on the server in addition to the distributed data in edge devices so as to efficiently train a global model. First, we propose a simple dynamic server update algorithm, which takes advantage of the shared insensitive data on the server while dynamically adjusting the update steps on the server in order to speed up the convergence and improve the accuracy. Second, we propose an adaptive optimization method with the dynamic server update algorithm to exploit the global momentum on the server and each local device for superior accuracy. Third, we develop a layer-adaptive model pruning method to carry out specific pruning operations, which is adapted to the diverse features of each layer so as to attain an excellent tradeoff between effectiveness and efficiency. Our proposed FL model, FedDUMAP, combines the three original techniques and has a significantly better performance compared with baseline approaches in terms of efficiency (up to 16.9 times faster), accuracy (up to 20.4% higher), and computational cost (up to 62.6% smaller).

Online shopping has become a crucial way to encourage daily consumption, where the User-generated, or crowdsourced product comments, can offer a broad range of feedback on e-commerce products. As a result, integrating critical opinions or major attitudes from the crowdsourced comments can provide valuable feedback for marketing strategy adjustment or product-quality monitoring. Unfortunately, the scarcity of annotated ground truth on the integrated comment, or the limited gold integration reference, has incurred the infeasibility of the regular supervised-learning-based comment integration. To resolve this problem, in this article, inspired by the principle of Transfer Learning, we propose a three-stage transferable and generative crowdsourced comment integration framework ( TTGCIF ) based on zero-and-few-shot learning with the support of domain distribution alignment. The proposed framework aims at generating abstractive integrated comment in target domain via the enhanced neural text generation model, by referring the available integration resource in related source domains, to avoid the exhausted effort on resource annotation devoted to the target domain. Specifically, at the first stage, to enhance the domain transferability, representations on the crowdsourced comments have been aligned up between the source and target domain, by minimizing the domain distribution discrepancy in the kernel space. At the second stage, Zero-shot comment integration mechanism has been adopted to deal with the dilemma that none of the gold integration reference may be available in target domain. In other words, taking the sample-level semantic prototype as input, the enhanced neural text generation model in TTGCIF is trained to learn data semantic association among different domains via semantic prototype transduction, so that the “ unlabeled ” crowdsourced comments in target domain can be associated with existing integration references in related source domains. At the third stage, based on the parameters trained at the second stage, fast domain adaptation mechanism in a Few-shot manner has also been adopted by seeking most potential parameters along the gradient direction constrained by instances across multiple source domains. In this way, parameters in TTGCIF can be sensitive to any alteration on training data, ensuring that even if only few annotated resource in target domain are available for “Fine-tune,” TTGCIF can still react promptly to achieve effective target domain adaptation. According to the experimental results, TTGCIF can achieve the best transferable product comment integration performance in target domain, with fast and stable domain adaption effect depending on no more than 10% annotated resource in target domain. More importantly, even if TTGCIF has not been fine-tuned on the target domain, yet by referring to the available integration resource in related source domains, the integrated comments generated by TTGCIF on the target domain are still superior to those generated by models already fine-tuned on the target domain.

Federated learning (FL) is a promising paradigm to enable collaborative model training with decentralized data.However, the training process of Large Language Models (LLMs) generally incurs the update of significant parameters, which limits the applicability of FL techniques to tackle the LLMs in real scenarios.Prompt tuning can significantly reduce the number of parameters to update, but it either incurs performance degradation or low training efficiency.The straightforward utilization of prompt tuning in the FL often raises non-trivial communication costs and dramatically degrades performance.In addition, the decentralized data is generally non-Independent and Identically Distributed (non-IID), which brings client drift problems and thus poor performance.This paper proposes a Parameter-efficient prompt Tuning approach with Adaptive Optimization, i.e., Fed-PepTAO, to enable efficient and effective FL of LLMs.First, an efficient partial prompt tuning approach is proposed to improve performance and efficiency simultaneously.Second, a novel adaptive optimization method is developed to address the client drift problems on both the device and server sides to enhance performance further.Extensive experiments based on 10 datasets demonstrate the superb performance (up to 60.8% in terms of accuracy) and efficiency (up to 97.59% in terms of training time) of FedPepTAO compared with 9 baseline approaches.Our code is available at https://github.com/llm-eff/FedPepTAO.

Federated Learning (FL) provides a new solution to the conflict between model training based on data aggregation and data privacy protection. However, in FL, end nodes (or clients) need to constantly exchange model parameters with the aggregation server, resulting in significant communication overhead. This paper proposes a structured compression-based method. During local training, each client iteratively prunes the original network based on the L1 norm of the channel as an importance measure to dynamically converge to sub-networks with different structures that fit their local data. When the server aggregates the heterogeneous networks of all clients, it takes average of the channels, significantly improving communication and computation overhead. This paper evaluated the proposed method on several public datasets for image classification, and the results showed that compared with the original network, the model parameter volume was compressed by 61 % to 91 %. Moreover, while maintaining model accuracy, compared to existing methods, the proposed method reduced training time by 39 % to 54%, but decreased the number of floating-point operations by 21 % to 44%.

Crowdsourcing is a sourcing model where individuals or organizations obtain goods and services from a large, relatively open and often rapidly evolving group of internet users. The most common way that crowdsourcing can facilitate machine learning is to annotate instances with labels [1] . However, the same instance may have inconsistent class labels, in the eyes of various annotators. Therefore, current efforts in crowdsourcing mainly focus on the truth inference or label integration, to remove inconsistent labels or to alleviate biased labeling. In turn, instances with the integrated labels could facilitate the training on machine learning models. The future direction of crowdsourcing is to apply more fine-grained truth inference methods to different application domains [2] . Consequently, we evolve toward another challenging problem of comment integration. That is, how can we integrate or summarize the core opinions of multiple product comments obtained from users, rather than the discrete labels.

Certified_Watermarks is the first to provide a watermark certificate against $l_2$-norm watermark removal attacks, by leveraging the randomized smoothing techniques for certified robustness to adversarial attacks. However, the randomized smoothing techniques suffer from hardness of certified robustness in high-dimensional space against $l_p$-norm attacks for large $p$ ($p>2$). The certified watermark method based on the randomized smoothing is no exception, i.e., fails to provide meaningful certificates in high-dimensional space against the $l_p$-norm watermark removal attacks ($p>2$). By leveraging mollifier theory, this paper proposes a mollifier smoothing method with dimension-independent certified radius of our proposed smooth classifier, for conducting the certified watermark problem against the $l_p$-norm watermark removal attacks ($1 \leq p \leq \infty$) for high parameter dimension $d$. Based on partial differential equation (PDE) theory, an approximation of mollifier smoothing is developed to alleviate the inefficiency of sampling and prediction in the randomized smoothing as well as numerical integration in the mollifier smoothing, while maintaining the certified watermark against the $l_p$-norm watermark removal attacks ($1 \leq p \leq \infty$).

Federated machine unlearning (FMU) aims to remove the influence of a specified subset of training data upon request from a trained federated learning model. Despite achieving remarkable performance, existing FMU techniques suffer from inefficiency due to two sequential operations of training and retraining/unlearning on large-scale datasets. Our prior study, PCMU, was proposed to improve the efficiency of centralized machine unlearning (CMU) with certified guarantees, by simultaneously executing the training and unlearning operations. This paper proposes a fast FMU algorithm, FFMU, for improving the FMU efficiency while maintaining the unlearning quality. The PCMU method is leveraged to train a local machine learning (MU) model on each edge device. We propose to employ nonlinear functional analysis techniques to refine the local MU models as output functions of a Nemytskii operator. We conduct theoretical analysis to derive that the Nemytskii operator has a global Lipschitz constant, which allows us to bound the difference between two MU models regarding the distance between their gradients. Based on the Nemytskii operator and average smooth local gradients, the global MU model on the server is guaranteed to achieve close performance to each local MU model with the certified guarantees.

The past decade has witnessed wide applications of machine learning to various domains for decision-making, including crime detection, urban planning, drug discovery, and health monitoring, which benefited from surging data resources. As data collection in real-world applications is often done in different locations, being able to mine and discover knowledge from distributed data sources is an essential requirement for building powerful predictive models. However, directly uploading all data sources to an untrustworthy centralized data server for learning will lead to risks of privacy leakage. Federated Learning (FL) emerges as a decentralized learning framework that aggregates knowledge from distributed data without centralizing them, hence mitigating privacy risks. By hosting this workshop, we aim to attract a broad spectrum of audiences, including researchers and practitioners from academia and industry interested in the latest advances in FL. As an effort to advance the fundamental development of FL in data mining, this workshop will encourage ideas exchange on the trustworthiness, scalability, robustness, and broad applications of FL.

Recent years have witnessed a large amount of decentralized data in various (edge) devices of end-users, while the decentralized data aggregation remains complicated for machine learning jobs because of regulations and laws. As a practical approach to handling decentralized data, Federated Learning (FL) enables collaborative global machine learning model training without sharing sensitive raw data. The servers schedule devices to jobs within the training process of FL. In contrast, device scheduling with multiple jobs in FL remains a critical and open problem. In this article, we propose a novel multi-job FL framework, which enables the training process of multiple jobs in parallel. The multi-job FL framework is composed of a system model and a scheduling method. The system model enables a parallel training process of multiple jobs, with a cost model based on the data fairness and the training time of diverse devices during the parallel training process. We propose a novel intelligent scheduling approach based on multiple scheduling methods, including an original reinforcement learning-based scheduling method and an original Bayesian optimization-based scheduling method, which corresponds to a small cost while scheduling devices to multiple jobs. We conduct extensive experimentation with diverse jobs and datasets. The experimental results reveal that our proposed approaches significantly outperform baseline approaches in terms of training time (up to 12.73 times faster) and accuracy (up to 46.4% higher).

Recent years have witnessed a large amount of decentralized data in multiple (edge) devices of end-users, while the aggregation of the decentralized data remains difficult for machine learning jobs due to laws or regulations. Federated Learning (FL) emerges as an effective approach to handling decentralized data without sharing the sensitive raw data, while collaboratively training global machine learning models. The servers in FL need to select (and schedule) devices during the training process. However, the scheduling of devices for multiple jobs with FL remains a critical and open problem. In this paper, we propose a novel multi-job FL framework to enable the parallel training process of multiple jobs. The framework consists of a system model and two scheduling methods. In the system model, we propose a parallel training process of multiple jobs, and construct a cost model based on the training time and the data fairness of various devices during the training process of diverse jobs. We propose a reinforcement learning-based method and a Bayesian optimization-based method to schedule devices for multiple jobs while minimizing the cost. We conduct extensive experimentation with multiple jobs and datasets. The experimental results show that our proposed approaches significantly outperform baseline approaches in terms of training time (up to 8.67 times faster) and accuracy (up to 44.6% higher).

Quasi-cliques are a type of dense subgraphs that generalize the notion of cliques, important for applications such as community/module detection in various social and biological networks. However, the existing quasi-clique definition and algorithms are only applicable to undirected graphs. In this paper, we generalize the concept of quasi-cliques to directed graphs by proposing (γ1, γ2) -quasi-cliques which have density requirements in both inbound and outbound directions of each vertex in a quasi-clique subgraph. An efficient recursive algorithm is proposed to find maximal (γ1,γ2)-quasi-cliques which integrates many effective pruning rules that are validated by ablation studies. We also study the finding of top-k large quasi-cliques directly by bootstrapping the search from more compact quasi-cliques, to scale the mining to larger networks. The algorithms are parallelized with effective load balancing, and we demonstrate that they can scale up effectively with the number of CPU cores.

Recent studies on federated learning (FL) have sought to solve the system heterogeneity issue by designing customized local models for different clients. However, public dataset introduction, sensitive information exchange, non-trivial computational cost, or particular architecture requirement limit the applicability of most of them in real scenarios. This paper presents a novel federated fingerprint learning model for making full use of the computing power of each client with the customized local models for improving the FL convergence, while keeping the data and sensitive information safe and local. First, we decompose the parameters of each local model into two types of parameters: rigid ones that have fixed model architecture for ensuring the convergence of global model training and elastic ones that contain customized model structure and size for allowing to make full use of the computing power of each client based on individual data scale. Second, we adopt the standard FL scheme to update and aggregate the local rigid parameters. We introduce a Gaussian distribution as auxiliary input and output K local fingerprints respectively for the elastic parameters of all K local models. The server aggregates K local fingerprints into a global one and sends it back to the clients. A fingerprint-based aggregation strategy makes the local models indirectly receive the aggregated elastic parameters through the aggregation of K local fingerprints while fixing data locally. Last but not least, we design a parameter masking method to mask the rigid parameters irrelevant to the local classification task in the local models. We develop a parameter separation method to guarantee that the combination of unmasked rigid parameters in all local models are able to cover all the rigid parameters as many as possible, for further raising the utilization rate of each rigid parameter.

iPSCs are pluripotent stem cells generated from adult tissue through a process called cellular reprogramming. However, cellular reprogramming is a lengthy and inefficient process since only a small fraction of cells can reliably become iPSCs. The reprogramming efficiency is generally measured by counting the number of reprogrammed colonies that emerge and grow as rounded clusters of compact cells around 20 days after adding the reprogramming vectors. However, counting colonies manually is labor-intensive, time-consuming, and error-prone.This work develops a semi-automated tool for colony counting from iPSC culture plate images, where colonies are automatically annotated with their centers. Our model uses multi-task learning to jointly predict the colony centers and conduct colony segmentation, in hope that the latter will improve the performance of the former. An annotation tool is developed to facilitate the collection of ground-truth masks by crowdsourcing. Two center-based loss functions are investigated and compared, one based on oriented Gaussian kernel and the other based on average Hausdorff distance. Extensive experiments verify that (i) the former loss outperforms the latter, (ii) the segmentation head is effective in improving center predictions. Our code has been released at https://github.com/MTSami/iPSC-Colony-Counting.

The federated learning (FL) framework enables edge clients to collaboratively learn a shared inference model while keeping privacy of training data on clients. Recently, many heuristics efforts have been made to generalize centralized adaptive optimization methods, such as SGDM, Adam, AdaGrad, etc., to federated settings for improving convergence and accuracy. However, there is still a paucity of theoretical principles on where to and how to design and utilize adaptive optimization methods in federated settings. This work aims to develop novel adaptive optimization methods for FL from the perspective of dynamics of ordinary differential equations (ODEs). First, an analytic framework is established to build a connection between federated optimization methods and decompositions of ODEs of corresponding centralized optimizers. Second, based on this analytic framework, a momentum decoupling adaptive optimization method, FedDA, is developed to fully utilize the global momentum on each local iteration and accelerate the training convergence. Last but not least, full batch gradients are utilized to mimic centralized optimization in the end of the training process to ensure the convergence and overcome the possible inconsistency caused by adaptive optimization methods.

Only recently, researchers attempt to provide classification algorithms with provable group fairness guarantees. Most of these algorithms suffer from harassment caused by the requirement that the training and deployment data follow the same distribution. This paper proposes an input-agnostic certified group fairness algorithm, FairSmooth, for improving the fairness of classification models while maintaining the remarkable prediction accuracy. A Gaussian parameter smoothing method is developed to transform base classifiers into their smooth versions. An optimal individual smooth classifier is learnt for each group with only the data regarding the group and an overall smooth classifier for all groups is generated by averaging the parameters of all the individual smooth ones. By leveraging the theory of nonlinear functional analysis, the smooth classifiers are reformulated as output functions of a Nemytskii operator. Theoretical analysis is conducted to derive that the Nemytskii operator is smooth and induces a Frechet differentiable smooth manifold. We theoretically demonstrate that the smooth manifold has a global Lipschitz constant that is independent of the domain of the input data, which derives the input-agnostic certified group fairness.

Despite achieving remarkable performance, Federated Learning (FL) suffers from two critical challenges, i.e., limited computational resources and low training efficiency. In this paper, we propose a novel FL framework, i.e., FedDUAP, with two original contributions, to exploit the insensitive data on the server and the decentralized data in edge devices to further improve the training efficiency. First, a dynamic server update algorithm is designed to exploit the insensitive data on the server, in order to dynamically determine the optimal steps of the server update for improving the convergence and accuracy of the global model. Second, a layer-adaptive model pruning method is developed to perform unique pruning operations adapted to the different dimensions and importance of multiple layers, to achieve a good balance between efficiency and effectiveness. By integrating the two original techniques together, our proposed FL model, FedDUAP, significantly outperforms baseline approaches in terms of accuracy (up to 4.8% higher), efficiency (up to 2.8 times faster), and computational cost (up to 61.9% smaller).

Given raster imagery features and imperfect vector training labels with registration uncertainty, this paper studies a deep learning framework that can quantify and reduce the registration uncertainty of training labels as well as train neural network parameters simultaneously. The problem is important in broad applications such as streamline classification on Earth imagery or tissue segmentation on medical imagery, whereby annotating precise vector labels is expensive and time-consuming. However, the problem is challenging due to the gap between the vector representation of class labels and the raster representation of image features and the need for training neural networks with uncertain label locations. Existing research on uncertain training labels often focuses on uncertainty in label class semantics or characterizes label registration uncertainty at the pixel level (not contiguous vectors). To fill the gap, this paper proposes a novel learning framework that explicitly quantifies vector labels' registration uncertainty. We propose a registration-uncertainty-aware loss function and design an iterative uncertainty reduction algorithm by re-estimating the posterior of true vector label locations distribution based on a Gaussian process. Evaluations on real-world datasets in National Hydrography Dataset refinement show that the proposed approach significantly outperforms several baselines in the registration uncertainty estimations performance and classification performance.

The right to be forgotten calls for efficient machine unlearning techniques that make trained machine learning models forget a cohort of data. The combination of training and unlearning operations in traditional machine unlearning methods often leads to the expensive computational cost on large-scale data. This paper presents a prompt certified machine unlearning algorithm, PCMU, which executes one-time operation of simultaneous training and unlearning in advance for a series of machine unlearning requests, without the knowledge of the removed/forgotten data. First, we establish a connection between randomized smoothing for certified robustness on classification and randomized smoothing for certified machine unlearning on gradient quantization. Second, we propose a prompt certified machine unlearning model based on randomized data smoothing and gradient quantization. We theoretically derive the certified radius R regarding the data change before and after data removals and the certified budget of data removals about R. Last but not least, we present another practical framework of randomized gradient smoothing and quantization, due to the dilemma of producing high confidence certificates in the first framework. We theoretically demonstrate the certified radius R' regarding the gradient change, the correlation between two types of certified radii, and the certified budget of data removals about R'.

Given earth imagery with spectral features on a terrain surface, this paper studies surface segmentation based on both explanatory features and surface topology. The problem is important in many spatial and spatiotemporal applications such as flood extent mapping in hydrology. The problem is uniquely challenging for several reasons: first, the size of earth imagery on a terrain surface is often much larger than the input of popular deep convolutional neural networks; second, there exists topological structure dependency between pixel classes on the surface, and such dependency can follow an unknown and non-linear distribution; third, there are often limited training labels. Existing methods for earth imagery segmentation often divide the imagery into patches and consider the elevation as an additional feature channel. These methods do not fully incorporate the spatial topological structural constraint within and across surface patches and thus often show poor results, especially when training labels are limited. Existing methods on semi-supervised and unsupervised learning for earth imagery often focus on learning representation without explicitly incorporating surface topology. In contrast, we propose a novel framework that explicitly models the topological skeleton of a terrain surface with a contour tree from computational topology, which is guided by the physical constraint (e.g., water flow direction on terrains). Our framework consists of two neural networks: a convolutional neural network (CNN) to learn spatial contextual features on a 2D image grid, and a graph neural network (GNN) to learn the statistical distribution of physics-guided spatial topological dependency on the contour tree. The two models are co-trained via variational EM. Evaluations on the real-world flood mapping datasets show that the proposed models outperform baseline methods in classification accuracy, especially when training labels are limited.

Network alignment, which aims at learning a matching between the same entities across multiple information networks, often suffers challenges from feature inconsistency, high-dimensional features, to unstable alignment results. This article presents a novel network alignment framework, Unsupervised Adversarial learning based Network Alignment(UANA), that combines generative adversarial network (GAN) and reinforcement learning (RL) techniques to tackle the above critical challenges. First, we propose a bidirectional adversarial network distribution matching model to perform the bidirectional cross-network alignment translations between two networks, such that the distributions of real and translated networks completely overlap together. In addition, two cross-network alignment translation cycles are constructed for training the unsupervised alignment without the need of prior alignment knowledge. Second, in order to address the feature inconsistency issue, we integrate a dual adversarial autoencoder module with an adversarial binary classification model together to project two copies of the same vertices with high-dimensional inconsistent features into the same low-dimensional embedding space. This facilitates the translations of the distributions of two networks in the adversarial network distribution matching model. Finally, we develop an RL based optimization approach to solve the vertex matching problem in the discrete space of the GAN model, i.e., directly select the vertices in target networks most relevant to the vertices in source networks, without unstable similarity computation that is sensitive to discriminative features and similarity metrics. Extensive evaluation on real-world graph datasets demonstrates the outstanding capability of UANA to address the unsupervised network alignment problem, in terms of both effectiveness and scalability.

Crowdsourcing is a hotspot research field which can facilitate machine learning by collecting labels to train models. Consequently, the state-of-the-art research efforts in crowdsourcing focus on truth inference or label integration, to remove inconsistent labels or to alleviate biased labeling. In turn, the integrated labels will be used to fine-tune machine learning models. Particularly, in this paper, we change the target of truth inference in crowdsourcing from discrete labels to multiple comments given by online participants, that is, the integration of the crowdsourced comments. For such a goal, we propose aSelf-play andSentiment-EmphasizedCommentIntegrationFramework (SSECIF), based on deepQ-learning, with three unique features. First, our framework SSECIF can generate the comment integration in a totally self-play way, without relying on the ground truth generated by human effort. Second, the integrated comment generated by SSECIF can include salient content with low redundancy. Third, the proposed framework SSECIF has emphasized, with a higher intensity, the sentiment in the integrated comment, in order to reflect the attitude or opinion more obviously. Extensive evaluation on real-world datasets demonstrates that SSECIF has achieved the best overall performance in terms of both effectiveness and efficiency, compared with the state-of-the-art methods.

Despite achieving remarkable performance, previous knowledge-enhanced works usually only use a single-source homogeneous knowledge base of limited knowledge coverage.Thus, they often degenerate into traditional methods because not all dialogues can be linked with knowledge entries.This paper proposes a novel dialogue generation model, MSKE-Dialog, to solve this issue with three unique advantages: ( 1) Rather than only one, MSKE-Dialog can simultaneously leverage multiple heterogeneous knowledge sources (it includes but is not limited to commonsense knowledge facts, text knowledge, infobox knowledge) to improve the knowledge coverage; (2) To avoid the topic conflict among the context and different knowledge sources, we propose a Multi-Reference Selection to better select context/knowledge; (3) We propose a Multi-Reference Generation to generate informative responses by referring to multiple generation references at the same time.Extensive evaluations on a Chinese dataset show the superior performance of this work against various state-of-the-art approaches.To our best knowledge, this work is the first to use the multi-source heterogeneous knowledge in the open-domain knowledge-enhanced dialogue generation.

Recent literatures have shown that knowledge graph (KG) learning models are highly vulnerable to adversarial attacks. However, there is still a paucity of vulnerability analyses of cross-lingual entity alignment under adversarial attacks. This paper proposes an adversarial attack model with two novel attack techniques to perturb the KG structure and degrade the quality of deep cross-lingual entity alignment. First, an entity density maximization method is employed to hide the attacked entities in dense regions in two KGs, such that the derived perturbations are unnoticeable. Second, an attack signal amplification method is developed to reduce the gradient vanishing issues in the process of adversarial attacks for further improving the attack effectiveness.

A recent study has shown that graph matching models are vulnerable to adversarial manipulation of their input which is intended to cause a mismatching. Nevertheless, there is still a lack of a comprehensive solution for further enhancing the robustness of graph matching against adversarial attacks. In this paper, we identify and study two types of unique topology attacks in graph matching: inter-graph dispersion and intra-graph assembly attacks. We propose an integrated defense model, IDRGM, for resilient graph matching with two novel defense techniques to defend against the above two attacks simultaneously. A detection technique of inscribed simplexes in the hyperspheres consisting of multiple matched nodes is proposed to tackle inter-graph dispersion attacks, in which the distances among the matched nodes in multiple graphs are maximized to form regular simplexes. A node separation method based on phase-type distribution and maximum likelihood estimation is developed to estimate the distribution of perturbed graphs and separate the nodes within the same graphs over a wide space, for defending intra-graph assembly attacks, such that the interference from the similar neighbors of the perturbed nodes is significantly reduced. We evaluate the robustness of our IDRGM model on real datasets against state-of-the-art algorithms.

Recent findings have shown multiple graph learning models, such as graph classification and graph matching, are highly vulnerable to adversarial attacks, i.e. small input perturbations in graph structures and node attributes can cause the model failures. Existing defense techniques often defend specific attacks on particular multiple graph learning tasks. This paper proposes an attack-agnostic graph-adaptive 1-Lipschitz neural network, ERNN, for improving the robustness of deep multiple graph learning while achieving remarkable expressive power. A K_l-Lipschitz Weibull activation function is designed to enforce the gradient norm as K_l at layer l. The nearest matrix orthogonalization and polar decomposition techniques are utilized to constraint the weight norm as 1/K_l and make the norm-constrained weight close to the original weight. The theoretical analysis is conducted to derive lower and upper bounds of feasible K_l under the 1-Lipschitz constraint. The combination of norm-constrained weight and activation function leads to the 1-Lipschitz neural network for expressive and robust multiple graph learning.

Due to limited knowledge carried by queries, traditional dialogue systems often face the dilemma of generating boring responses, leading to poor user experience. To alleviate this issue, this paper proposes a novel infobox knowledge-aware dialogue generation approach, HITA-Graph, with three unique features. First, open-domain infobox tables that describe entities with relevant attributes are adopted as the knowledge source. An order-irrelevance Hierarchical Infobox Table Encoder is proposed to represent an infobox table at three levels of granularity. In addition, an Infobox-Dialogue Interaction Graph Network is built to effectively integrate the infobox context and the dialogue context into a unified infobox representation. Second, a Hierarchical Infobox Attribute Attention mechanism is developed to access the encoded infobox knowledge at different levels of granularity. Last but not least, a Dynamic Mode Fusion strategy is designed to allow the Decoder to select a vocabulary word or copy a word from the given infobox/query. We extract infobox tables from Chinese Wikipedia and construct an infobox knowledge base. Extensive evaluation on an open-released Chinese corpus demonstrates the superior performance of our approach against several representative methods.

Accurate forecasting of stock prices plays an important role in stock investment. With the advancement of AI in Fintech applications, various deep learning models have recently been developed for stock price forecasting. However, these models focus on designing sequence models to capture the temporal dependence from a stock's historical prices (and other information such as technical indicators and news), leaving the information from similar stocks underexplored. To fill this gap, we propose a novel deep learning approach for stock price forecasting, which builds and uses a stock correlation graph$G$where nodes are stocks and edges connect highly price-correlated stocks. Our model combines the graph convolutional network (GCN) and gated recurrent unit (GRU). Specifically, the GCN is used to extract features from the price of each stock and the prices of those highly similar stocks inG. For each stock, a sequence of these extracted features are then fed into a GRU model to capture temporal dependence. The model training follows the idea of multi-task learning, where each task learns its unique RNN-based sequence predictor for one stock, but all stocks share a common GCN module to improve GCN training to more effectively propagate correlation-related market signals. Our extensive experiments on real stock price data demonstrate that our approach consistently outperforms a GRU baseline that does not consider similar stocks during prediction, which verifies the effectiveness of using a stock correlation graph.

Recently, linear regression models have shown to often produce rather competitive results against more sophisticated deep learning models. Meanwhile, the (weighted) matrix factorization approaches have been popular choices for recommendation in the past and widely adopted in the industry. In this work, we aim to theoretically understand the relationship between these two approaches, which are the cornerstones of model-based recommendations. Through the derivation and analysis of the closed-form solutions for two basic regression and matrix factorization approaches, we found these two approaches are indeed inherently related but also diverge in how they "scale-down" the singular values of the original user-item interaction matrix. We further introduce a new learning algorithm in searching (hyper)parameters for the closed-form solution and utilize it to discover the nearby models of the existing solutions. The experimental results demonstrate that the basic models and their closed-form solutions are indeed quite competitive against the state-of-the-art models, thus, confirming the validity of studying the basic models. The effectiveness of exploring the nearby models are also experimentally validated.

Despite achieving remarkable efficiency, traditional network pruning techniques often follow manually-crafted heuristics to generate pruned sparse networks. Such heuristic pruning strategies are hard to guarantee that the pruned networks achieve test accuracy comparable to the original dense ones. Recent works have empirically identified and verified the Lottery Ticket Hypothesis (LTH): a randomly-initialized dense neural network contains an extremely sparse subnetwork, which can be trained to achieve similar accuracy to the former. Due to the lack of theoretical evidence, they often need to run multiple rounds of expensive training and pruning over the original large networks to discover the sparse subnetworks with low accuracy loss. By leveraging dynamical systems theory and inertial manifold theory, this work theoretically verifies the validity of the LTH. We explore the possibility of theoretically lossless pruning as well as one-time pruning, compared with existing neural network pruning and LTH techniques. We reformulate the neural network optimization problem as a gradient dynamical system and reduce this high-dimensional system onto inertial manifolds to obtain a low-dimensional system regarding pruned subnetworks. We demonstrate the precondition and existence of pruned subnetworks and prune the original networks in terms of the gap in their spectrum that make the subnetworks have the smallest dimensions.

Recent studies have shown that graph learning models are highly vulnerable to adversarial attacks, and network alignment methods are no exception. How to enhance the robustness of network alignment against adversarial attacks remains an open research problem. In this paper, we propose a robust network alignment solution, RNA, for offering preemptive protection of existing network alignment algorithms, enhanced with the guidance of effective adversarial attacks. First, we analyze how popular iterative gradient-based adversarial attack techniques suffer from gradient vanishing issues and show a fake sense of attack effectiveness. Based on dynamical isometry theory, an attack signal scaling (ASS) method with established upper bound of feasible signal scaling is introduced to alleviate the gradient vanishing issues for effective adversarial attacks while maintaining the decision boundary of network alignment. Second, we develop an adversarial perturbation elimination (APE) model to neutralize adversarial nodes in vulnerable space to adversarial-free nodes in safe area, by integrating Dirac delta approximation (DDA) techniques and the LSTM models. Our proposed APE method is able to provide proactive protection to existing network alignment algorithms against adversarial attacks. The theoretical analysis demonstrates the existence of an optimal distribution for the APE model to reach a lower bound. Last but not least, extensive evaluation on real datasets presents that RNA is able to offer the preemptive protection to trained network alignment methods against three popular adversarial attack models.

Generative dialogue systems tend to produce generic responses, which often leads to boring conversations.For alleviating this issue, Recent studies proposed to retrieve and introduce knowledge facts from knowledge graphs.While this paradigm works to a certain extent, it usually retrieves knowledge facts only based on the entity word itself, without considering the specific dialogue context.Thus, the introduction of the context-irrelevant knowledge facts can impact the quality of generations.To this end, this paper proposes a novel commonsense knowledge-aware dialogue generation model, ConKADI.We design a Felicitous Fact mechanism to help the model focus on the knowledge facts that are highly relevant to the context; furthermore, two techniques, Context-Knowledge Fusion and Flexible Mode Fusion are proposed to facilitate the integration of the knowledge in the ConKADI.We collect and build a large-scale Chinese dataset aligned with the commonsense knowledge for dialogue generation.Extensive evaluations over both an open-released English dataset and our Chinese dataset demonstrate that our approach ConKADI outperforms the state-of-the-art approach CCM, in most experiments.

Stock investment is a vehicle for many people to grow their wealth. However, market downturns can cause huge losses and need to be predicted for a timely sell. In fact, with effective prediction, stocks are a good investment even during periods of market volatility as many stocks are "on sale".News is an important source of signal for stock price movement. However, stock analysts usually adjust their analysis according to the news in a subject manner, and wrong judgments can cause investors huge losses.Twitter is a great source for breaking news, and provides a timely stream of signals on stock trends. News on Twitter also tends to have a great impact on the market due to the large number of Twitter users. This paper proposes a data-driven pipeline to timely incorporate Twitter news about a company into a time series prediction model on the company's stock price. Our approach, called BERT-LSTM (BELT), extracts informative features on stock price direction from Twitter news using the state-of-the-art natural language processing (NLP) model BERT, which are then used as covariates to a many-to-many stacked LSTM model that also utilizes historical stock prices to predict the direction of future stock price. Utilizing a carefully curated stock news dataset, we fine-tune BERT to effectively identify those news tweets that are relevant, and to extract NLP features that are indicative of price rises and falls. All model parameters are trained end-to-end to provide a data-driven and objective pipeline to incorporate news signals so as to avoid subjective analysis. Extensive experiments on real stock prices and Twitter news show that BELT is able to predict stock prices more accurately utilizing news information than if historical price data are used alone for prediction, and beats StockNet which is the current state of the art for news-based stock movement prediction.

Network alignment techniques, which aim to identify the same entities across multiple networks, often suffer challenges from feature inconsistency to transitivity law preservation. This paper presents a purely unsupervised network alignment method, KEMINA, with three original contributions. First, in order to address the feature inconsistency issue, an adversarial kernel embedding technique is proposed to extract network-invariant information among multiple networks without prior alignment knowledge, and project them into the common embedding space. Second, a multinomial generative adversarial network (GAN) model is developed to train multiple network alignment tasks simultaneously in an unsupervised manner with preserving the transitivity law property. Third but last, a variational inference model is designed to alleviate the data sparsity and inadequate training issues by filling realistic detail for vertices with sparse features and generating real-looking supplementary vertex samples within limited training opportunity of each pair of source and target networks.

Recent studies have shown that graph mining models are vulnerable to adversarial attacks. This paper proposes a robust meta network embedding framework, RoMNE, which improves the robustness of multiple network embedding on adversarial noisy networks while preserving the utility on original clean ones. First, we propose a generic meta learning based multiple network embedding model that can quickly adapt it to new embedding tasks on a variety of network data with only a small number of parameter and training updates. Second, Gumbel estimator and Gaussian smoothing techniques are introduced to implement differentiable approximation for optimizing non-differential objective of effective adversarial attacks. Last but not least, the adversarial attack and defense models are integrated into a dynamic adversarial training model. The competition of two models helps the latter be robust to adversarial attacks.

Machine learning algorithms, especially deep learning architectures, have demonstrated immense potential for biomedical segmentation, often surpassing expert-level performance. For cardiac magnetic resonance (CMR) imaging, semantic segmentation is critical to deriving clinical measures such as myocardial mass and volume. However, challenges still exist. Manual delineation by domain experts is time-consuming and subject to human errors. With semi-automated segmentation techniques, it is challenging to analyze images of the same subject twice, end-diastole and end-systole of the cardiac cycle. To address these challenges, we propose a deep learning-based end-to-end analytical pipeline for automated segmentation of short-axis CMR imaging. The automated pipeline successfully avoids the problem of human subjectivity and achieves expert-level segmentation accuracy. With a large heterogeneous data inclusive of subjects with varying conditions, our model overcomes the data-homogeneity and achieves 99.9% dice similarity score, which outperforms the current state-of-art work.

Insufficient semantic understanding of dialogue always leads to the appearance of generic responses, in generative dialogue systems. Recently, high-quality knowledge bases have been introduced to enhance dialogue understanding, as well as to reduce the prevalence of boring responses. Although such knowledge-aware approaches have shown tremendous potential, they always utilize the knowledge in a black-box fashion. As a result, the generation process is somewhat uncontrollable, and it is also not interpretable. In this paper, we introduce a topic fact-based commonsense knowledge-aware approach, TopicKA. Different from previous works, TopicKA generates responses conditioned not only on the query message but also on a topic fact with an explicit semantic meaning, which also controls the direction of generation. Topic facts are recommended by a recommendation network trained under the Teacher-Student framework. To integrate the recommendation network and the generation network, this paper designs four schemes, which include two non-sampling schemes and two sampling methods. We collected and constructed a large-scale Chinese commonsense knowledge graph. Experimental results on an open Chinese benchmark dataset indicate that our model outperforms baselines in terms of both the objective and the subjective metrics.

Despite achieving remarkable performance, deep graph learning models, such as node classification and network embedding, suffer from harassment caused by small adversarial perturbations. However, the vulnerability analysis of graph matching under adversarial attacks has not been fully investigated yet. This paper proposes an adversarial attack model with two novel attack techniques to perturb the graph structure and degrade the quality of deep graph matching: (1) a kernel density estimation approach is utilized to estimate and maximize node densities to derive imperceptible perturbations, by pushing attacked nodes to dense regions in two graphs, such that they are indistinguishable from many neighbors; and (2) a meta learning-based projected gradient descent method is developed to well choose attack starting points and to improve the search performance for producing effective perturbations. We evaluate the effectiveness of the attack model on real datasets and validate that the attacks can be transferable to other graph learning models.

The advent of social networks and activity networks affords us an opportunity of utilizing explicit social information and activity information to improve the quality of recommendation in the presence of data sparsity. In this article, we present a social-influence-based collaborative filtering (SICF) framework over heterogeneous information networks with three unique features. First, we integrate different types of entities, links, attributes, and activities from rating networks, social networks, and activity networks into a unified social-influence-based collaborative filtering model through the intra-network and inter-network social influence. Second, we propose three social-influence propagation models to capture three kinds of information propagation within heterogeneous information networks: user-based influence propagation on user rating networks, item-based influence propagation on user-rating activity networks, and term-based influence propagation on user-review activity networks, respectively. We compute three kinds of social-influence-based user similarity scores based on three social-influence propagation models, respectively. Third, a unified social-influence-based CF prediction model is proposed to infer rating tastes by incorporating three kinds of social-influence-based similarity measures with different weighting factors. We design a weight-learning algorithm, SICF, to refine the prediction result by quantifying the contribution of each kind of information propagation to make a good balance between prediction accuracy and data sparsity. Extensive evaluation on real datasets demonstrates that SICF outperforms existing representative collaborative filtering methods.

Network embedding techniques aim to encode each vertex/edge as a low-dimensional vector, enabling easy integration with existing graph mining algorithms. This paper presents a novel network embedding framework, VEEMBEDCLASS, that combines local vertex/edge embedding with deep matrix fusion and Siamese multi-label classification for facilitating classification-based local network embedding. First, we propose to perform the embeddings of each vertex/edge on K local vertex/edge embedding models respectively, with the joint optimization by considering both intra-class and inter-class correlations, to learn their latent local features on each class. The deep matrix fusion technique is developed to preserve the first-order and second-order proximity of vertices and edges on each of K classes simultaneously. Second, a Student t-distribution based Siamese multi-label classification method is designed to train associated vertices and edges with similar local characteristics together and learn their class membership probabilities, in response to the power-law vertex degree distribution widespread in real graphs. A principle of vertex-edge homophily is introduced to guarantee that the common edge/vertex shared by two associated vertices/edges and themselves are similar in terms of both structural correlations and class memberships. Finally, we integrate local vertex/edge embedding and Siamese multi-label classification into a unified model by mutually enhancing each other.

Real-world graphs are usually very sparse in terms of inadequate edges and labels as well as have poor quality due to a large amount of noisy data. In this paper, we propose a classification-based local vertex ranking architecture through dual generative adversarial networks in the semi-supervised setting, DQGAN, for analyzing sparse noisy graphs with rarely labeled data. First, we develop a quadruple generative adversarial ClassNet model to address the noisy data and data sparsity issues as well as to classify each vertex into K classes by automatically creating imaginary/real-looking supplementary labeled vertices with the quite different/similar distributions as real vertices, without the high cost of multi-step graph propagation, heterogeneous graph mining, and iterative weight learning. In addition, the vertex label vicinity is incorporated into the classification model to capture the pairwise vertex closeness based on the labeling and align the vertex label vicinity with the well-known vertex homophily for preserving the original structural semantics in the classification space. Second, we present a quintuple generative adversarial RankNet framework to locally rank each vertex on each of K classes by designing the game of multiple competitors utilizing the mix of real and noisy data to fight against each other, for improving the robustness of local vertex ranking to noisy data with few help from human efforts. The cycle ranking consistency strategy is designed to make the ranking quality verifiable through the bidirectional information-lossless translations between the original features and the ranking features. We propose to utilize the relaxed local PageRank property to produce high-quality local vertex ranking results in the context of information networks. Third but last, extensive evaluation on real graph datasets demonstrates that DQGAN outperforms existing representative methods in terms of both classification and ranking in the semi-supervised setting.

Network alignment, which aims to learn a matching between the same entities across multiple information networks, often suffers challenges from feature inconsistency, high-dimensional features, to unstable alignment results. This paper presents a novel network alignment framework, RANA, that combines dual generative adversarial network (GAN) techniques to match the distributions of two networks based on two dimensions of distance and shape. First, we propose an adversarial network distribution matching model to perform the bidirectional cross-network alignment translations between two networks, such that the cross-network transformed distributions of two networks move closer to each other and finally meet with each other halfway. In addition, a homophily consistency loss is introduced to maintain the vertex homophily consistency between pairwise vertices on two networks in both the embedding space. Second, in order to address the feature inconsistency issue, we integrate a dual adversarial autoencoder module with an adversarial two-class classification model together to twist the cross-network transformed distributions of two networks, such that two distributions could have the same shape. This facilitates the translations of the distributions of two networks in the adversarial network distribution matching model. Moreover, a semantic preservation loss is introduced to preserve the original embedding semantics of one network when this network is translated to another network and returned to itself. Third but last, the competition game by integrating the above two adversarial models together can help project two copies of the same vertices with high-dimensional inconsistent features into the same low-dimensional embedding space, and thus guarantee the distribution consistency between two networks in terms of both distance and shape.

With the widespread use of GPS-equipped smartphones and Internet of Things devices, a huge amount of data with location information is being generated at an unprecedented rate. To gain a deeper insight into such a plethora of spatial data, scientists and engineers are widely using spatial queries for their big data applications. However, because of not only the massive spatial data size but also the complexity of spatial query processing, they are struggling to efficiently process the spatial queries. In this paper, we propose lightweight and scalable indexing and querying services for big spatial data stored in distributed storage systems or graph-based systems. Our spatial services have several advantages over existing approaches. First, our services can be easily applied to existing storage systems or graph-based models without modifying the internal implementation of existing systems/models. Second, our services achieve high pruning power by efficiently selecting only relevant spatial objects based on a simple yet effective filter. Third, our services support a customizable and easy-to-use control of index data size by adjusting the precision of indexed geometries. Lastly, our services support efficient updates of spatial data. Our experimental results using real-world datasets validate the effectiveness and efficiency of our spatial services.

Network embedding aims to learn latent low dimensional representation of vertices in graphs while preserving the intrinsic characteristics of graph data. In this paper, we propose a density-aware local autoencoder embedding architecture, DAL-SAE, with three features. First, we develop a flexible density-aware local deep autoencoder embedding method to perform local embedding on each of K clustering-based subgraphs with the optimization at both vertex and subgraph levels, in response to imbalanced density-based local characteristics of vertices and subgraphs. We design K local autoencoder embedding models, each with individual parameters and structure, to jointly train K subgraphs and optimize the loss functions within and across clusters. Second, we design an autoencoder graph clustering method to optimize local embedding and graph clustering simultaneously and capture local, clustering, and global network structure in the learning process. Third but last, a density-aware local Siamese autoencoder embedding approach can be utilized to train multiple clustering-based subgraphs with similar local characteristics on the common Siamese networks, to save the memory consumption of multiple local embedding models as well as maintain the similar embedding features.

Traditional network representation learning techniques aim to learn latent low-dimensional representation of vertices in graphs. This paper presents a novel edge representation learning framework, GANDLERL, that combines generative adversarial network based multi-label classification with density-adaptive local edge representation learning for producing high-quality low-dimensional edge representations. First, we design a generative adversarial network based multi-label edge classification model to classify rarely labeled edges in graphs with a large amount of noise data into K classes. A four-player zero-sum game model, with the mixed training of true and real-looking fake edges as well as a contrastive loss containing a similar-loss and a dissimilar-loss, is proposed to improve the classification quality of unlabeled edges. Second, a local autoencoder edge representation learning method is developed to design K local representation learning models, each with individual parameters and structure to perform local representation learning on each of K classification-based subgraphs with unique local characteristics and jointly optimize the loss functions within and across classes. Third but last, we propose a density-adaptive edge representation learning method with the optimization at both edge and subgraph levels to address the representation learning of graph data with highly imbalanced vertex degree and edge distribution.

Conventional private data publication schemes are targeted at publication of sensitive datasets either after the k -anonymization process or through differential privacy constraints. Typically these schemes are designed with the objective of retaining as much utility as possible for the aggregate queries while ensuring the privacy of the individual records. Such an approach, though suitable for publishing aggregate information as public datasets, is inapplicable when users have different levels of access to the same data. We argue that existing schemes either result in increased disclosure of private information or lead to reduced utility when some users have more access privileges than the others. In this article, we present an anonymization framework for publishing large datasets with the goals of providing different levels of utility to the users based on their access privilege levels. We design and implement our proposed multilevel utility-controlled anonymization schemes in the context of large association graphs considering three levels of user utility, namely, (1) users having access to only the graph structure, (2) users having access to the graph structure and aggregate query results, and (3) users having access to the graph structure, aggregate query results, and individual associations. Our experiments on real large association graphs show that the proposed techniques are effective and scalable and yield the required level of privacy and utility for each user privacy and access privilege level.

Utilizing graph analysis models and algorithms to exploit complex interactions over a network of entities is emerging as an attractive network analytic technology. In this paper, we show that traditional column or row-based trace analysis may not be effective in deriving deep insights hidden in the storage traces collected over complex storage applications, such as complex spatial and temporal patterns, hotspots and their movement patterns. We propose a novel graph analytics framework, GraphLens, for mining and analyzing real world storage traces with three unique features. First, we model storage traces as heterogeneous trace graphs in order to capture multiple complex and heterogeneous factors, such as diverse spatial/temporal access information and their relationships, into a unified analytic framework. Second, we employ and develop an innovative graph clustering method that employs two levels of clustering abstractions on storage trace analysis. We discover interesting spatial access patterns and identify important temporal correlations among spatial access patterns. This enables us to better characterize important hotspots and understand hotspot movement patterns. Third, at each level of abstraction, we design a unified weighted similarity measure through an iterative dynamic weight learning algorithm. With an optimal weight assignment scheme, we can efficiently combine the correlation information for each type of storage access patterns, such as random versus sequential, read versus write, to identify interesting spatial/temporal correlations hidden in the traces. Some optimization techniques on matrix computation are proposed to further improve the efficiency of our clustering algorithm on large trace datasets. Extensive evaluation on real storage traces shows GraphLens can provide broad and deep trace analysis for better storage strategy planning and efficient data placement guidance. GraphLens can be applied to both a single PC with multiple disks and a distributed network across a cluster of compute nodes to offer a few opportunities for optimization of storage performance.

The cloud service marketplace (CSM) is an exploratory project aiming to provide “an AppStore for Services.” It is an intelligent online marketplace that facilitates service discovery and acquisition for enterprise customers. Traditional service discovery and acquisition are time-consuming. In the era of OneClick Checkout and pay-as-you-go service plans, users expect services to be purchased online efficiently and conveniently. However, as services are complex and different from software apps, the currently prevailing App Store based on keyword search is inadequate for services. In CSM, exploring and configuring services are an iterative process. Customers provide their requirements in natural language and interact with the system through questioning and answering. Learning from the input, the system can incrementally clarify users’ intention, narrow down the candidate services, and profile the configuration information for the candidates at the same time. CSM’s back end is built around the Services Knowledge Graph (SKG) and leverages data mining technologies to enable the semantic understanding of customers’ requirements. To quantitatively assess the value of CSM, empirical evaluation on real and synthetic datasets and case studies are given to demonstrate the efficacy and effectiveness of the proposed system.

NoSQL systems have become the vital components to deliver big data services in the Cloud. However, existing NoSQL systems rely on experienced administrators to configure and tune the wide range of configurable parameters in order to achieve high performance. In this paper, we present a policy-driven configuration management system for NoSQL systems, called PCM. PCM can identify workload sensitive configuration parameters and capture the tuned parameters for different workloads as configuration policies. PCM also can be used to analyze the range of configuration parameters that may impact on the runtime performance of NoSQL systems in terms of read and write workloads. The configuration optimization recommended by PCM can enable NoSQL systems such as HBase to run much more efficiently than the default settings for both individual worker node and entire cluster in the Cloud. Our experimental results show that HBase under the PCM configuration outperforms the default configuration and some simple configurations on a range of workloads with offering significantly higher throughput.

Iterative computation on large graphs has challenged system research from two aspects: (1) how to conduct high performance parallel processing for both in-memory and out-of-core graphs; and (2) how to handle large graphs that exceed the resource boundary of traditional systems by resource aware graph partitioning such that it is feasible to run large-scale graph analysis on a single PC. This paper presents GraphLego, a resource adaptive graph processing system with multi-level programmable graph parallel abstractions. GraphLego is novel in three aspects: (1) we argue that vertex-centric or edge-centric graph partitioning are ineffective for parallel processing of large graphs and we introduce three alternative graph parallel abstractions to enable a large graph to be partitioned at the granularity of subgraphs by slice, strip and dice based partitioning; (2) we use dice-based data placement algorithm to store a large graph on disk by minimizing non-sequential disk access and enabling more structured in-memory access; and (3) we dynamically determine the right level of graph parallel abstraction to maximize sequential access and minimize random access. GraphLego can run efficiently on different computers with diverse resource capacities and respond to different memory requirements by real-world graphs of different complexity. Extensive experiments show the competitiveness of GraphLego against existing representative graph processing systems, such as GraphChi, GraphLab and X-Stream.

Many popular web service networks are content-rich in terms of heterogeneous types of entities and links, associated with incomplete attributes. Clustering such heterogeneous service networks demands new clustering techniques that can handle two heterogeneity challenges: (1) multiple types of entities co-exist in the same service network with multiple attributes, and (2) links between entities have diverse types and carry different semantics. Existing heterogeneous graph clustering techniques tend to pick initial centroids uniformly at random, specify the number k of clusters in advance, and fix k during the clustering process. In this paper, we propose Service Cluster, a novel heterogeneous service network clustering algorithm with four unique features. First, we incorporate various types of entity, attribute and link information into a unified distance measure. Second, we design a Discrete Steepest Descent method to naturally produce initial k and initial centroids simultaneously. Third, we propose a dynamic learning method to automatically adjust the link weights towards clustering convergence. Fourth, we develop an effective optimization strategy to identify new suitable k and k well-chosen centroids at each clustering iteration. Extensive evaluation on real datasets demonstrates that Service Cluster outperforms existing representative methods in terms of both effectiveness and efficiency.

Meta paths are good mechanisms to improve the quality of graph analysis on heterogeneous information networks. This paper presents a meta path graph clustering framework, VEPATHCLUSTER, that combines meta path vertex-centric clustering with meta path edge-centric clustering for improving the clustering quality of heterogeneous networks. First, we propose an edge-centric path graph model to capture the meta-path dependencies between pairwise path edges. We model a heterogeneous network containing M types of meta paths as M vertex-centric path graphs and M edge-centric path graphs. Second, we propose a clustering-based multigraph model to capture the fine-grained clustering-based relationships between pairwise vertices and between pairwise path edges. We perform clustering analysis on both a unified vertex-centric path graph and each edge-centric path graph to generate vertex clustering and edge clusterings of the original heterogeneous network respectively. Third, a reinforcement algorithm is provided to tightly integrate vertex-centric clustering and edge-centric clustering by mutually enhancing each other. Finally, an iterative learning strategy is presented to dynamically refine both vertex-centric clustering and edge-centric clustering by continuously learning the contributions and adjusting the weights of different path graphs.

In recent years, systems researchers have devoted considerable effort to the study of large-scale graph processing. Existing distributed graph processing systems such as Pregel, based solely on distributed memory for their computations, fail to provide seamless scalability when the graph data and their intermediate computational results no longer fit into the memory; and most distributed approaches for iterative graph computations do not consider utilizing secondary storage a viable solution. This paper presents GraphMap, a distributed iterative graph computation framework that maximizes access locality and speeds up distributed iterative graph computations by effectively utilizing secondary storage. GraphMap has three salient features: (1) It distinguishes data states that are mutable during iterative computations from those that are read-only in all iterations to maximize sequential access and minimize random access. (2) It entails a two-level graph partitioning algorithm that enables balanced workloads and locality-optimized data placement. (3) It contains a proposed suite of locality-based optimizations that improve computational efficiency. Extensive experiments on several real-world graphs show that GraphMap outperforms existing distributed memory-based systems for various iterative graph algorithms.

Large-scale real-world graphs are known to have highly skewed vertex degree distribution and highly skewed edge weight distribution. Existing vertex-centric iterative graph computation models suffer from a number of serious problems: (1) poor performance of parallel execution due to inherent workload imbalance at vertex level; (2) inefficient CPU resource utilization due to short execution time for low-degree vertices compared to the cost of in-memory or on-disk vertex access; and (3) incapability of pruning insignificant vertices or edges to improve the computational performance. In this paper, we address the above technical challenges by designing and implementing a scalable, efficient, and provably correct two-tier graph parallel processing system, GraphTwist. At storage and access tier, GraphTwist maximizes parallel efficiency by employing three graph parallel abstractions for partitioning a big graph by slice, strip or dice based partitioning techniques. At computation tier, GraphTwist presents two utility-aware pruning strategies: slice pruning and cut pruning, to further improve the computational performance while preserving the computational utility defined by graph applications. Theoretic analysis is provided to quantitatively prove that iterative graph computations powered by utility-aware pruning techniques can achieve a very good approximation with bounds on the introduced error.

Social influence analysis has shown great potential for strategic marketing decision. It is well known that people influence one another based on both their social connections and the social activities that they have engaged in the past. In this article, we develop an innovative and high-performance social influence based graph clustering framework with four unique features. First, we explicitly distinguish social connection based influence (self-influence) and social activity based influence (co-influence). We compute the self-influence similarity between two members based on their social connections within a single collaboration network, and compute the co-influence similarity by taking into account not only the set of activities that people participate but also the semantic association between these activities. Second, we define the concept of influence-based similarity by introducing a unified influence-based similarity matrix that employs an iterative weight update method to integrate self-influence and co-influence similarities. Third, we design a dynamic learning algorithm, called SI-C luster , for social influence based graph clustering. It iteratively partitions a large social collaboration network into K clusters based on both the social network itself and the multiple associated activity information networks, each representing a category of activities that people have engaged. To make the SI-C luster algorithm converge fast, we transform sophisticated nonlinear fractional programming problem with respect to multiple weights into a straightforward nonlinear parametric programming problem of single variable. Finally, we develop an optimization technique of diagonalizable-matrix approximation to speed up the computation of self-influence similarity and co-influence similarities. Our SI-Cluster-Opt significantly improves the efficiency of SI-Cluster on large graphs while maintaining high quality of clustering results. Extensive experimental evaluation on three real-world graphs shows that, compared to existing representative graph clustering algorithms, our SI-C luster -O pt approach not only achieves a very good balance between self-influence and co-influence similarities but also scales extremely well for clustering large graphs in terms of time complexity while meeting the guarantee of high density, low entropy and low Davies--Bouldin Index.

Distributed service networks are popular platforms for service providers to offer services to consumers and for service consumers to acquire services from unknown parties. eBay and Amazon are two well-known examples of enabling and hosting such service networks to connect service providers to service consumers. Trust management is a critical component for scaling such distributed service networks to a large and growing number of participants. In this article, we present ServiceTrust ++ , a feedback quality--sensitive and attack resilient trust management scheme for empowering distributed service networks with effective trust management capability. Compared with existing trust models, ServiceTrust ++ has several novel features. First, we present six attack models to capture both independent and colluding attacks with malicious cliques, malicious spies, and malicious camouflages. Second, we aggregate the feedback ratings based on the variances of participants’ feedback behaviors and incorporate feedback similarity as weight into the local trust algorithm. Third, we compute the global trust of a participant by employing conditional trust propagation based on the feedback similarity threshold. This allows ServiceTrust ++ to control and prevent malicious spies and malicious camouflage peers from boosting their global trust scores by manipulating the feedback ratings of good peers and by taking advantage of the uniform trust propagation. Finally, we systematically combine a trust-decaying strategy with a threshold value--based conditional trust propagation to further strengthen the robustness of our global trust computation against sophisticated malicious feedback. Experimental evaluation with both simulation-based networks and real network dataset Epinion show that ServiceTrust ++ is highly resilient against all six attack models and highly effective compared to EigenTrust, the most popular and representative trust propagation model to date.

With more data generated and collected in a geographically distributed manner, combined by the increased computational requirements for large scale data-intensive analysis, we have witnessed the growing demand for geographically distributed Cloud datacenters and hybrid Cloud service provisioning, enabling organizations to support instantaneous demand of additional computational resources and to expand inhouse resources to maintain peak service demands by utilizing cloud resources. A key challenge for running applications in such a geographically distributed computing environment is how to efficiently schedule and perform analysis over data that is geographically distributed across multiple datacenters. In this paper, we first compare multi-datacenter Hadoop deployment with single-datacenter Hadoop deployment to identify the performance issues inherent in a geographically distributed cloud. A generalization of the problem characterization in the context of geographically distributed cloud datacenters is also provided with discussions on general optimization strategies. Then we describe the design and implementation of a suite of system-level optimizations for improving performance of Hadoop service provisioning in a geo-distributed cloud, including prediction-based job localization, configurable HDFS data placement, and data prefetching. Our experimental evaluation shows that our prediction based localization has very low error ratio, smaller than 5%, and our optimization can improve the execution time of Reduce phase by 48.6%.

Multi-label classification of heterogeneous information networks has received renewed attention in social network analysis. In this paper, we present an activity-edge centric multi-label classification framework for analyzing heterogeneous information networks with three unique features. First, we model a heterogeneous information network in terms of a collaboration graph and multiple associated activity graphs. We introduce a novel concept of vertex-edge homophily in terms of both vertex labels and edge labels and transform a general collaboration graph into an activity-based collaboration multigraph by augmenting its edges with class labels from each activity graph through activity-based edge classification. Second, we utilize the label vicinity to capture the pairwise vertex closeness based on the labeling on the activity-based collaboration multigraph. We incorporate both the structure affinity and the label vicinity into a unified classifier to speed up the classification convergence. Third, we design an iterative learning algorithm, AEClass, to dynamically refine the classification result by continuously adjusting the weights on different activity-based edge classification schemes from multiple activity graphs, while constantly learning the contribution of the structure affinity and the label vicinity in the unified classifier. Extensive evaluation on real datasets demonstrates that AEClass outperforms existing representative methods in terms of both effectiveness and efficiency.

Big data business can leverage and benefit from the Clouds, the most optimized, shared, automated, and virtualized computing infrastructures. One of the important challenges in processing big data in the Clouds is how to effectively partition the big data to ensure efficient distributed processing of the data. In this paper we present a Scalable and yet customizable data PArtitioning framework, called SPA, for distributed processing of big RDF graph data. We choose big RDF datasets as our focus of the investigation for two reasons. First, the Linking Open Data cloud has put forwards a good number of big RDF datasets with tens of billions of triples and hundreds of millions of links. Second, such huge RDF graphs can easily overwhelm any single server due to the limited memory and CPU capacity and exceed the processing capacity of many conventional data processing software systems. Our data partitioning framework has two unique features. First, we introduce a suite of vertexcentric data partitioning building blocks to allow efficient and yet customizable partitioning of large heterogeneous RDF graph data. By efficient, we mean that the SPA data partitions can support fast processing of big data of different sizes and complexity. By customizable, we mean that the SPA partitions are adaptive to different query types. Second, we propose a selection of scalable techniques to distribute the building block partitions across a cluster of compute nodes in a manner that minimizes inter-node communication cost by localizing most of the queries on distributed partitions. We evaluate our data partitioning framework and algorithms through extensive experiments using both benchmark and real datasets. Our experimental results show that the SPA data partitioning framework is not only efficient for partitioning and distributing big RDF datasets of diverse sizes and structures but also effective for processing big data queries of different types and complexity.

A known problem for virtualized cloud data centers is the inter-VM communication inefficiency for data transfer between co-resident VMs. Several engineering efforts have been made on building a shared memory based channel between co-resident VMs. The implementations differ in terms of whether user/program transparency, OS kernel transparency or VMM transparency is supported. However, none of existing works has engaged in an in-depth measurement study with quantitative and qualitative analysis on performance improvements as well as tradeoffs introduced by such a residency-aware inter-VM communication mechanism. In this paper we present an extensive experimental study, aiming at addressing a number of fundamental issues and providing deeper insights regarding the design of a shared memory channel for co-resident VMs. Example questions include how much performance gains can a residency-aware shared memory inter-VM communication mechanism provide under different mixtures of local and remote network I/O workloads, what overhead will the residence-awareness detection and communication channel switch introduce over the remote inter-VM communication, what factors may exert significant impact on the throughput and latency performance of such a shared memory channel. We believe that this measurement study not only helps system developers to gain valuable lessons and generate new ideas to further improve the inter-VM communication performance. It also offers new opportunities for cloud service providers to deploy their services more efficiently and for cloud service consumers to improve the performance of their application systems running in the Cloud.

Service network analysis is an essential aspect of web service discovery, search, mining and recommendation. Many popular web service networks are content-rich in terms of heterogeneous types of entities, attributes and links. A main challenge for ranking services is how to incorporate multiple complex and heterogeneous factors, such as service attributes, relationships between services, relationships between services and service providers or service consumers, into the design of service ranking functions. In this paper, we model services, attributes, and the associated entities, such as providers, consumers, by a heterogeneous service network. We propose a unified neighborhood random walk distance measure, which integrates various types of links and vertex attributes by a local optimal weight assignment. Based on this unified distance measure, a reinforcement algorithm, ServiceRank, is provided to tightly integrate ranking and clustering by mutually and simultaneously enhancing each other such that the performance of both can be improved. An additional clustering matching strategy is proposed to efficiently align clusters from different types of objects. Our extensive evaluation on both synthetic and real service networks demonstrates the effectiveness of ServiceRank in terms of the quality of both clustering and ranking among multiple types of entity, link and attribute similarities in a service network.

Social networks continue to grow in size and the type of information hosted. We witness a growing interest in clustering a social network of people based on both their social relationships and their participations in activity based information networks. In this paper, we present a social influence based clustering framework for analyzing heterogeneous information networks with three unique features. First, we introduce a novel social influence based vertex similarity metric in terms of both self-influence similarity and co-influence similarity. We compute self-influence and co-influence based similarity based on social graph and its associated activity graphs and influence graphs respectively. Second, we compute the combined social influence based similarity between each pair of vertices by unifying the self-similarity and multiple co-influence similarity scores through a weight function with an iterative update method. Third, we design an iterative learning algorithm, SI-Cluster, to dynamically refine the K clusters by continuously quantifying and adjusting the weights on self-influence similarity and on multiple co-influence similarity scores towards the clustering convergence. To make SI-Cluster converge fast, we transformed a sophisticated nonlinear fractional programming problem of multiple weights into a straightforward nonlinear parametric programming problem of single variable. Our experiment results show that SI-Cluster not only achieves a better balance between self-influence and co-influence similarities but also scales extremely well for large graph clustering.

Social networks, sensor networks, biological networks, and many other information networks can be modeled as a large graph. Graph vertices represent entities, and graph edges represent their relationships or interactions. In many large graphs, there is usually one or more attributes associated with every graph vertex to describe its properties. In many application domains, graph clustering techniques are very useful for detecting densely connected groups in a large graph as well as for understanding and visualizing a large graph. The goal of graph clustering is to partition vertices in a large graph into different clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structure for clustering, but largely ignore the vertex properties, which are often heterogenous. In this article, we propose a novel graph clustering algorithm, SA-Cluster , which achieves a good balance between structural and attribute similarities through a unified distance measure. Our method partitions a large graph associated with attributes into k clusters so that each cluster contains a densely connected subgraph with homogeneous attribute values. An effective method is proposed to automatically learn the degree of contributions of structural similarity and attribute similarity. Theoretical analysis is provided to show that SA-Cluster is converging quickly through iterative cluster refinement. Some optimization techniques on matrix computation are proposed to further improve the efficiency of SA-Cluster on large graphs. Extensive experimental results demonstrate the effectiveness of SA-Cluster through comparisons with the state-of-the-art graph clustering and summarization methods.

In recent years, many networks have become available for analysis, including social networks, sensor networks, biological networks, etc. Graph clustering has shown its effectiveness in analyzing and visualizing large networks. The goal of graph clustering is to partition vertices in a large graph into clusters based on various criteria such as vertex connectivity or neighborhood similarity. Many existing graph clustering methods mainly focus on the topological structures, but largely ignore the vertex properties which are often heterogeneous. Recently, a new graph clustering algorithm, SA-Cluster, has been proposed which combines structural and attribute similarities through a unified distance measure. SA-Cluster performs matrix multiplication to calculate the random walk distances between graph vertices. As the edge weights are iteratively adjusted to balance the importance between structural and attribute similarities, matrix multiplication is repeated in each iteration of the clustering process to recalculate the random walk distances which are affected by the edge weight update. In order to improve the efficiency and scalability of SA-Cluster, in this paper, we propose an efficient algorithm Inc-Cluster to incrementally update the random walk distances given the edge weight increments. Complexity analysis is provided to estimate how much runtime cost Inc-Cluster can save. Experimental results demonstrate that Inc-Cluster achieves significant speedup over SA-Cluster on large graphs, while achieving exactly the same clustering quality in terms of intra-cluster structural cohesiveness and attribute value homogeneity.

Bug localization has attracted a lot of attention recently. Most existing methods focus on pinpointing a single statement or function call which is very likely to contain bugs. Although such methods could be very accurate, it is usually very hard for developers to understand the context of the bug, given each bug location in isolation. In this study, we propose to model software executions with graphs at two levels of granularity: methods and basic blocks. An individual node represents a method or basic block and an edge represents a method call, method return or transition (at the method or basic block granularity). Given a set of graphs of correct and faulty executions, we propose to extract the most discriminative subgraphs which contrast the program flow of correct and faulty executions. The extracted subgraphs not only pinpoint the bug, but also provide an informative context for understanding and fixing the bug. Different from traditional graph mining which mines a very large set of frequent subgraphs, we formulate subgraph mining as an optimization problem and directly generate the most discriminative subgraph with a recently proposed graph mining algorithm LEAP. We further extend it to generate a ranked list of top-k discriminative subgraphs representing distinct locations which may contain bugs. Experimental results and case studies show that our proposed method is both effective and efficient to mine discriminative subgraphs for bug localization and context identification.

The goal of graph clustering is to partition vertices in a large graph into different clusters based on various criteria such as vertex connectivity or neighborhood similarity. Graph clustering techniques are very useful for detecting densely connected groups in a large graph. Many existing graph clustering methods mainly focus on the topological structure for clustering, but largely ignore the vertex properties which are often heterogenous. In this paper, we propose a novel graph clustering algorithm, SA-Cluster , based on both structural and attribute similarities through a unified distance measure. Our method partitions a large graph associated with attributes into k clusters so that each cluster contains a densely connected subgraph with homogeneous attribute values. An effective method is proposed to automatically learn the degree of contributions of structural similarity and attribute similarity. Theoretical analysis is provided to show that SA-Cluster is converging. Extensive experimental results demonstrate the effectiveness of SA-Cluster through comparison with the state-of-the-art graph clustering and summarization methods.