Adversarial attacks remain a major challenge for deep learning models, as they can undermine both performance and reliability in practical applications such as image recognition. Although evolutionary algorithms (EAs) have proven effective in optimizing complex systems, their use for directly enhancing model robustness for adversarial defense has been limited. In this study, we introduce ResNet-GA, a method that applies evolutionary deep learning (EDL) to develop ResNet-like networks specifically designed to resist different forms of adversarial perturbations. The approach evolves network architectures with a genetic algorithm (GA), adapting the Residual Blocks at every stage in ResNet according to the needs of each dataset and attack type. Experimental results show that ResNet-GA strengthens model robustness beyond standard baselines, highlighting the value of iterative evolutionary design for building more dependable deep learning systems under various adversarial conditions.

We study online routing problems with predictions, inspired by recent exciting results emerged from the area of learning-augmented algorithms. A learning-augmented online algorithm, which incorporates predictions into a black-box manner to outperform existing algorithms if the predictions are accurate while otherwise maintaining theoretical guarantees, is a popular framework for overcoming pessimistic worst-case competitive analysis. In this paper, we particularly investigate the classical online traveling salesman problem (OLTSP) and online dial-a-ride problem (OLDARP), where future requests are augmented with predictions. Unlike the prediction models in other previous studies, each actual request in the OLTSP and OLDARP is associated with its arrival time and position, which, as imagined, leads to a more complicated situation. Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Science Council [Grants NSTC110-2221-E-007-106-MY3, NSTC111-2221-E-007-052-MY3].

Clustering is essential in data analysis since many real-world datasets are unlabeled and are expensive to label. Density-based clustering algorithms are known for their capability of identifying clusters of non-spherical shapes and have been widely studied over recent decades. Among these algorithms, Density Peaks (DP) clustering is an outstanding one that is particularly robust to changes in the distance metric. However, the performance of DP clustering highly depends on the choice of its hyperparameters: the cutoff distance and the number of clusters. As a result, we developed a learning-based approach for selecting appropriate values of the hyperparameters for DP clustering in one-shot. We address the challenging issue of effective one-shot hyperparameter selection by proposing two novel embeddings: the HINT (Histogram of Neighborhood Transform) embedding and the Gamma embedding. The HINT embedding calculates the histogram of the$m$-th neighborhood distances for each node. The neighborhood distances histogram captures practical characteristics of the density property for a given dataset. Meanwhile, the Gamma embedding condenses the information of a decision graph while still providing crucial clues for determining the number of clusters. Therefore, we achieved effective one-shot hyperparameter selection by the proposed novel embeddings. As compared with an exhaustive grid search method, our method is 169 times faster, while its relative performance ratio is up to 89.6%, which demonstrates its effectiveness. As there has been a shortage of research devoted to hyperparameter selection for DP clustering, we expected our promising result to inspire more studies toward the important research topic.

Spectrum sharing in Device-to-Device (D2D) communications with power control and link scheduling is a challenging non-convex combinatorial optimization problem. The state-of-the-art model-based iterative algorithms such as FPLinQ produce optimum-achieving solutions, whilst deep learning-based approaches have been proposed recently to approximate FPLinQ with reduced computational complexity. However, due to the highly non-convex nature of the optimization problem, FPLinQ exhibits certain deficiencies in the highly interference-limited networks, as it may be trapped within certain local sub-optimal solutions that may be far from the global optimum. To address these issues, we propose to unfold FPLinQ, with certain parameters inside the iterative procedure adjusted by a graph reinforcement learning (GRL) method, and end up with a novel hybrid model/data-driven approach, termed UFPLinQ. Not only does UFPLinQ inherit the advantages of FPLinQ and GRL with respect to local optimality, explainability, scalability, and generalizability, but it also provides excellent solutions in interference-limited networks where FPLinQ fails. By numerical evaluations, UFPLinQ outperforms existing learning-based power control mechanisms, with substantially reduced training samples and iterations, and more interestingly remedies the potential deficiencies of FPLinQ in highly interference-limited networks.

Device-to-device (D2D) spectrum sharing in wireless communications is a challenging non-convex combinatorial optimization problem, involving entangled link scheduling and power control in a large-scale network. The state-of-the-art methods, either from a model-based or a data-driven perspective, exhibit certain limitations such as the critical need for channel state information (CSI) and/or a large number of (solved) instances (e.g., network layouts) as training samples. To advance this line of research, we propose a novel hybrid model/data-driven spectrum sharing mechanism with graph reinforcement learning for link scheduling (GRLinQ), injecting information theoretical insights into machine learning models, in such a way that link scheduling and power control can be solved in an intelligent manner. Through an extensive set of experiments, GRLinQ demonstrates superior performance to the existing model-based and data-driven link scheduling and/or power control methods, with a relaxed requirement for CSI, a substantially reduced number of unsolved instances as training samples, a possible distributed deployment, reduced online/offline computational complexity, and more remarkably excellent scalability and generalizability over different network scenarios and system configurations.

The advance of topological interference management (TIM) has been one of the driving forces of recent developments in network information theory. However, state-of-the-art coding schemes for TIM are usually handcrafted for specific families of network topologies, relying critically on experts’ domain knowledge and sophisticated treatments. The lack of systematic and automatic generation of solutions inevitably restricts their potential wider applications to wireless communication systems, due to the limited generalizability of coding schemes to wider network configurations. To address such an issue, this work makes the first attempt to advocate revisiting topological interference alignment (IA) from a novel learning-to-code perspective. Specifically, we recast the one-to-one and subspace IA conditions as vector assignment policies and propose a unifying learning-to-code on graphs (LCG) framework by leveraging graph neural networks (GNNs) for capturing topological structures and reinforcement learning (RL) for decision-making of IA beamforming vector assignment. Interestingly, the proposed LCG framework is capable of recovering known one-to-one scalar/vector IA solutions for a significantly wider range of network topologies, and more remarkably of discovering new subspace IA coding schemes for multiple-antenna cases that are challenging to be handcrafted. The extensive experiments demonstrate that the LCG framework is an effective way to automatically produce systematic coding solutions to the TIM instances with arbitrary network topologies, and at the same time, the underlying learning algorithm is efficient with respect to online inference time and possesses excellent generalizability and transferability for practical deployment.

Incremental learning aims to develop models capable of continuously acquiring knowledge, consistent with many real-world scenarios where data evolves and becomes available over time, and may also come with new classes. When performing classification tasks in incremental learning, there is typically no need to retrain models with previous training data. Instead, models can be updated with new data as it becomes available. This study introduces a novel approach, Incremental Random Forest with Prototypes (IRFwP), for incremental learning using a modified random forest model. It constructs data prototypes for each class by clustering training data while maintaining attribute averages and boundaries. The experiments demonstrate the effectiveness of the proposed approach in comparison to several state-of-the-art incremental learning models.

Device-to-Device (D2D) link scheduling in wireless communications is a challenging non-convex combinatorial optimization problem. The state-of-the-art methods, either from a model-based or a data-driven perspective, exhibit certain limitations such as the critical need of Channel State Information (CSI) and a large number of instances or solved instances as training samples. To advance this line of research, we propose a novel hybrid model/data-driven approach with Graph Reinforcement Learning for Link Scheduling (GRLinQ), injecting information theoretical insights into machine leaning models. GRLinQ demonstrates superior performance to the existing model-based and data-driven link scheduling mechanisms, with a relaxed requirement of CSI, a smaller number of unsolved instances as training samples, a possible distributed deployment, and more remarkably an excellent generalization ability over different network scenarios and system configurations.

In this paper, we consider a primal-dual algorithmic aspect of the link scheduling problem in dynamic wireless networks, where the channel characteristics are dramatically time-varying that could render state-of-the-art link scheduling mechanisms computational expensive to fit network dynamics. Building upon the optimality condition of treating interference as noise, we formulate link scheduling as a maximum weighted clique problem on a coexisting graph, which can be transformed into a minimum weighted vertex coloring problem (MWVCP) through the primal-dual technique. With an adversarial perturbation modeling of network dynamics with edge insertion/deletion, we propose dynamic graph algorithms to solve the MWVCP for chordal graph classes with theoretical guarantees on algorithmic feasibility, optimality, and updating complexity. It is expected the resulting link scheduling mechanism could shed light on robust, scalable, and certifiable system designs in dynamic wireless networks from the algorithmic perspective.

The state-of-the-art coding schemes for topological interference management (TIM) problems are usually handcrafted for specific families of network topologies, relying critically on experts' domain knowledge. This inevitably restricts the potential wider applications to wireless communication systems, due to the limited generalizability. This work makes the first attempt to advocate a novel intelligent coding approach to mimic topological interference alignment via local graph coloring algorithms, leveraging the new advances of graph neural networks (GNNs) and reinforcement learning (RL). The extensive experiments demonstrate the excellent generalizability and transferability of the proposed approach, where the parameterized GNNs trained by small size TIM instances are able to work well on new unseen network topologies with larger size.

Online users’ feedback has numerous text comments to enrich the review quality on mainstream platforms, such as Yelp and Google Maps. Reading through numerous review comments to speculate the important aspects is tedious and time-consuming. Apparently, there is a huge gap between the numerous commentary text and the crucial aspects for users’ preferences. In this study, we proposed a weakly supervised framework called Sequence to Commentary Aspect Score Estimation (Seq2CASE) to estimate the vital aspect scores from the review comments, since the ground truth of the aspect score is seldom available. The aspect score estimation from Seq2CASE is close to the actual aspect scoring; precisely, the average Mean Absolute Error (MAE) is less than 0.4 for a 5-point grading scale. The performance of Seq2CASE is comparable to or even better than the state-of-the-art supervised approaches in recommendation tasks. We expect this work to be a stepping stone that can inspire more unsupervised studies working on this important but relatively underexploited research.

Clustering algorithms have been widely studied in many scientific areas, such as data mining, knowledge discovery, bioinformatics and machine learning. A density-based clustering algorithm, called density peaks (DP), which was proposed by Rodriguez and Laio, outperform almost all other approaches. Although the DP algorithm performs well in many cases, there is still room for improvement in the precision of its output clusters as well as the quality of the selected centers. In this study, we propose a more accurate clustering algorithm, seed-and-extension-based density peaks (SDP). SDP selects the centers that hold the features of their clusters while building a spanning forest, and meanwhile, constructs the output clusters in a seed-and-extension manner. Experiment results demonstrate the effectiveness of SDP, especially when dealing with clusters with relatively high densities. Precisely, we show that SDP is more accurate than the DP algorithm as well as other state-of-the-art clustering approaches concerning the quality of both output clusters and cluster centers while maintaining similar running time of the DP algorithm, particularly for a variety of time-series (i.e. non-metric) data. Moreover, SDP outperforms DP in the dynamic model in which data point insertion and deletion are allowed. From a practical perspective, the proposed SDP algorithm is obviously helpful to many application problems.

We investigate the power-down mechanism which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle cost and switching cost, is minimized. In contrast to most of the previous studies on the offline model, we focus on the online model in which a sequence of jobs with their release time, execution time and deadline, arrive in an online fashion. More precisely, we exploit a different switching on and off strategy and present an upper bound of 3, and further show a lower bound of 2.1, in a dual-machine model, introduced by Chen et al. in 2014 [STACS 2014: 226-238], both of which beat the currently best result.

In this paper, we consider the topological interference management (TIM) problem in a dynamic setting, where an adversary perturbs network topology to prevent the exploitation of sophisticated coding opportunities (e.g., interference alignment). Focusing on a special class of network topology – chordal networks – we investigate algorithmic aspects of the TIM problem under adversarial topology perturbation. In particular, given the adversarial perturbation with respect to edge insertion/deletion, we propose a dynamic graph coloring algorithm that allows for a constant number of re-coloring updates against each inserted/deleted edge to achieve the information-theoretic optimality. This is a sharp reduction of the general graph re-coloring, whose optimal number of updates scales as the size of the network, thanks to the delicate exploitation of the structural properties of chordal graph classes.

The online car-sharing problem finds many real-world applications. The problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and k total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called k S2L-F, assumes that requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. In spite of only two locations, the analysis does not seem easy and the (tight) competitive ratio (CR) is only known to be 2 for k = 2 and 1.5 for a restricted value of k , i.e., a multiple of three. In this paper, we remove all the holes of unknown CR's; namely we prove that the CR is 2 k k + ⌊ k / 3 ⌋ for all k ≥ 2 . Furthermore, if the algorithm can delay its decision until all requests have come in each stage, the CR is improved to roughly 4/3. We can take this advantage even further; precisely we can achieve a CR of 2 + R 3 if the number of requests in each stage is at most Rk , 1 ≤ R ≤ 2 , where we do not have to know the value of R in advance. Finally we demonstrate that randomization also helps to get (slightly) better CR's, and prove some lower bounds to show the tightness.

In this paper, we consider the topological interference management (TIM) problem in a dynamic setting, where an adversary perturbs network topology to prevent the exploitation of sophisticated coding opportunities (e.g., interference alignment). Focusing on a special class of network topology - chordal networks - we investigate algorithmic aspects of the TIM problem under adversarial topology perturbation. In particular, given the adversarial perturbation with respect to edge insertion/deletion, we propose a dynamic graph coloring algorithm that allows for a constant number of re-coloring updates against each inserted/deleted edge to achieve the information-theoretic optimality. This is a sharp reduction of the general graph re-coloring, whose optimal number of updates scales as the size of the network, thanks to the delicate exploitation of the structural properties of chordal graph classes.

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G=(V,E), which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O(log n / epsilon) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem.

MOTIVATION: Protein complexes are one of the keys to studying the behavior of a cell system. Many biological functions are carried out by protein complexes. During the past decade, the main strategy used to identify protein complexes from high-throughput network data has been to extract near-cliques or highly dense subgraphs from a single protein-protein interaction (PPI) network. Although experimental PPI data have increased significantly over recent years, most PPI networks still have many false positive interactions and false negative edge loss due to the limitations of high-throughput experiments. In particular, the false negative errors restrict the search space of such conventional protein complex identification approaches. Thus, it has become one of the most challenging tasks in systems biology to automatically identify protein complexes. RESULTS: In this study, we propose a new algorithm, NEOComplex ( NE CC- and O rtholog-based Complex identification by multiple network alignment), which integrates functional orthology information that can be obtained from different types of multiple network alignment (MNA) approaches to expand the search space of protein complex detection. As part of our approach, we also define a new edge clustering coefficient (NECC) to assign weights to interaction edges in PPI networks so that protein complexes can be identified more accurately. The NECC is based on the intuition that there is functional information captured in the common neighbors of the common neighbors as well. Our results show that our algorithm outperforms well-known protein complex identification tools in a balance between precision and recall on three eukaryotic species: human, yeast, and fly. As a result of MNAs of the species, the proposed approach can tolerate edge loss in PPI networks and even discover sparse protein complexes which have traditionally been a challenge to predict. AVAILABILITY AND IMPLEMENTATION: http://acolab.ie.nthu.edu.tw/bionetwork/NEOComplex. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

With the increasing number of unpredictable accidents and power shortages on utility systems, the need to improve the reliability and security of electric power networks is imminent. Energy management systems that use traditional computer-aided tools to monitor and control generation and transmission systems using supervisory control and data acquisition (SCADA) actually have low sampling and update rates. In recent years, wide area monitoring system (WAMS) can possibly meet these challenges based on the state-of-the-art data retrieval technology. WAMS makes it possible to monitor power utility networks in a real-time dynamic manner using phasor measurement units. These sensor devices can provide synchronized measurements using global positioning satellite systems (GPS). In this paper, we study the power management problem under different scenarios. We present several multi-objective optimization models which can provide a deeper insight into operations on smart grid. We also consider contingency constraints and optimal allocation of these sensor devices on utility systems.

Because high-dimensional wafer bin maps (WBMs) cause various features, it is difficult to search the similarity among WBMs via conventional pattern recognition methods. This study develops a novel morphology-based support vector machine for defective wafer detection. The experimental results demonstrate its usefulness in yield improvements on precision and computation cost.

MOTIVATION: The global alignment of protein interaction networks is a widely studied problem. It is an important first step in understanding the relationship between the proteins in different species and identifying functional orthologs. Furthermore, it can provide useful insights into the species' evolution. RESULTS: We propose a novel algorithm, PISwap, for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology information, trading it off for sequence information. In practice, our algorithm efficiently refines other well-studied alignment techniques with almost no additional time cost. We also show the robustness of the algorithm to noise in protein interaction data. In addition, the flexible nature of this algorithm makes it suitable for different applications of network alignment. This algorithm can yield interesting insights into the evolutionary dynamics of related species. AVAILABILITY: Our software is freely available for non-commercial purposes from our Web site, http://piswap.csail.mit.edu/. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: In the last decade, a considerable amount of research has been devoted to investigating the phylogenetic properties of organisms from a systems-level perspective. Most studies have focused on the classification of organisms based on structural comparison and local alignment of metabolic pathways. In contrast, global alignment of multiple metabolic networks complements sequence-based phylogenetic analyses and provides more comprehensive information. RESULTS: We explored the phylogenetic relationships between microorganisms through global alignment of multiple metabolic networks. The proposed approach integrates sequence homology data with topological information of metabolic networks. In general, compared to recent studies, the resulting trees reflect the living style of organisms as well as classical taxa. Moreover, for phylogenetically closely related organisms, the classification results are consistent with specific metabolic characteristics, such as the light-harvesting systems, fermentation types, and sources of electrons in photosynthesis. CONCLUSIONS: We demonstrate the usefulness of global alignment of multiple metabolic networks to infer phylogenetic relationships between species. In addition, our exhaustive analysis of microbial metabolic pathways reveals differences in metabolic features between phylogenetically closely related organisms. With the ongoing increase in the number of genomic sequences and metabolic annotations, the proposed approach will help identify phenotypic variations that may not be apparent based solely on sequence-based classification.

Due to increases in the complexity of processes involved in semiconductor manufacturing, increasingly high inspection costs associated with defective wafers has become a critical concern of modern manufacturers. More importantly, because of high-dimensional wafer bin maps (WBMs), it is difficult to capture the variations of each dimension via traditional pattern recognition or classification methods. By contrast, this work proposes a novel two-phase morphology-based similarity search consisting of: (1) training sample generation based on the morphological method and (2) SVM categorization for test datasets according to the variant degrees of similarities. The morphology-based samples contain five kinds of features, including original morphology definitions in addition to our proposed features. The second phase, using SVM for similarity searches, extends the usage of pattern recognition to real applications in large sample dimensions. The preliminary results demonstrate the usefulness of our approach in the context of yield improvements in semiconductor manufacturing.

MOTIVATION: With the increasing availability of large protein-protein interaction networks, the question of protein network alignment is becoming central to systems biology. Network alignment is further delineated into two sub-problems: local alignment, to find small conserved motifs across networks, and global alignment, which attempts to find a best mapping between all nodes of the two networks. In this article, our aim is to improve upon existing global alignment results. Better network alignment will enable, among other things, more accurate identification of functional orthologs across species. RESULTS: We introduce IsoRankN (IsoRank-Nibble) a global multiple-network alignment tool based on spectral clustering on the induced graph of pairwise alignment scores. IsoRankN outperforms existing algorithms for global network alignment in coverage and consistency on multiple alignments of the five available eukaryotic networks. Being based on spectral methods, IsoRankN is both error tolerant and computationally efficient. AVAILABILITY: Our software is available freely for non-commercial purposes on request from: http://isorank.csail.mit.edu/.