Neural Architecture Search (NAS) has emerged as a crucial method for automating the design of deep learning models. Despite its potential, NAS frequently requires substantial computational and hardware resources. To mitigate these challenges, transferable NAS (TNAS) has been introduced, leveraging prior NAS results to enhance performance on new tasks. However, existing methods largely focus on knowledge transfer within identical neural search spaces, overlooking the potential for cross-domain transferability. Motivated by this gap, we explore evolutionary TNAS across heterogeneous search spaces by learning common neural representations. In particular, we introduce a novel approach that encodes both operational and topological information of neural architectures into a unified sequence using a simple tokenizer. This sequence is then processed by a variational auto-encoder, with a Transformer-based encoder to capture rich neural representations and a decoder that reconstructs the original sequence. By utilizing these latent representations, we further establish an inter-domain mapping that acts as a bridge, enabling effective explicit solution transfer among diverse search spaces to enhance the evolutionary NAS process. To harness this capability, we develop an evolutionary sequential transfer optimization approach that transfers knowledge during population initialization, providing both flexibility and adaptability. To the best of our knowledge, this work serves as the first attempt in the literature exploring evolutionary TNAS across diverse spaces. Moreover, we demonstrate the utility of our method through comprehensive empirical studies using different architecture spaces, including NAS-Bench-101, NAS-Bench-201, and the DARTS search space. Our results show that the proposed method significantly enhances the adaptability and performance of NAS across varied domains.

Transfer reinforcement learning (TRL) aims to boost the efficiency of reinforcement learning (RL) agents by leveraging knowledge from related tasks. Prior research primarily focuses on intradomain transfer, overlooking the complexities of transferring knowledge across tasks with differing state and action spaces. Recent efforts in cross-domain TRL aim to bridge this gap by establishing mappings between disparate source and target spaces, thereby enabling knowledge transfer across RL tasks with varied state and action configurations. However, existing studies often rely on strict prior assumptions about the relationships between state spaces, which limits their practical generality. In this article, we propose a novel approach to cross-domain TRL based on seeded graph matching, which enables alignment between source and target tasks regardless of differences in their state-action spaces. In particular, we model RL tasks as directed graphs, identify seed node pairs based on common RL properties, and devise a graph matching algorithm to align the source and target tasks by leveraging their structural characteristics. Building on this alignment, we introduce a policy-based transfer algorithm that improves the performance of the target RL task as its RL process progresses. Finally, we conduct comprehensive empirical studies on both discrete and continuous tasks with diverse state-action spaces. The experimental results validate the effectiveness of the proposed algorithm.

Finding the optimal Steiner Tree in graphs has been a critical combinatorial optimization challenge that finds widespread applications in network design. Despite its importance, finding the optimal Steiner Tree remains computationally expensive, especially for large graphs due to its NP-hard nature. Traditional approaches often suffer from high time complexity or poor approximation ratio. Machine learning approaches often leverage local graph structure information instead of global graph structure information, and often suffer from the generalization ability issues in practice. In this paper, we propose a novel reinforcement learning based framework to solve STP, in which we reformulate the classical Q-value computation to capture both global graph structure and deterministic information to search for the Steiner tree. Experiments on both synthetic and real-world datasets demonstrate that our framework exhibits better generalization ability compared to the existing machine learning methods, where our framework can be trained on the small graphs and generalize well to larger graphs and the graphs from different distributions.

In this paper, we study the problem of constrained path search with submodular function maximization (CPS-SM). We aim to find the path with the best submodular function score under a given constraint (e.g., a length limit), where the submodular function score is computed over the set of nodes in this path. This problem can be used in many applications. For example, tourists may want to search the most diversified path (e.g., a path passing by the most diverse facilities such as parks and museums) given that the traveling time is less than 6 hours. We show that the CPS-SM problem is NP-hard. We first propose a concept called “submodular$\alpha$-dominance” by utilizing the submodular function properties, and we develop an algorithm with a guaranteed error bound based on this concept. By relaxing the submodular$\alpha$-dominance conditions, we design another more efficient algorithm that has the same error bound. We also utilize the way of bi-directional path search to further improve the efficiency of the algorithms. We finally propose a heuristic algorithm that is efficient yet effective in practice. The experiments conducted on several real datasets show that our proposed algorithms can achieve high accuracy and are faster than one state-of-the-art method by orders of magnitude.

The problem of selecting a sequence of items that maximizes a given submodular function appears in many real-world applications. Existing study on the problem only considers uniform costs over items, but non-uniform costs on items are more general. Taking this cue, we study the problem of budgeted sequence submodular maximization (BSSM), which introduces non-uniform costs of items into the sequence selection. This problem can be found in a number of applications such as movie recommendation, course sequence design and so on. Non-uniform costs on items significantly increase the solution complexity and we prove that BSSM is NP-hard. To solve the problem, we first propose a greedy algorithm GBM with an error bound. We also design an anytime algorithm POBM based on Pareto optimization to improve the quality of solutions. Moreover, we prove that POBM can obtain approximate solutions in expected polynomial running time, and converges faster than a state-of-the-art algorithm POSEQSEL for sequence submodular maximization with cardinality constraints. We further introduce optimizations to speed up POBM. Experimental results on both synthetic and real-world datasets demonstrate the performance of our new algorithms.

Region search is an important problem in location-based services due to its wide applications. In this paper, we study the problem of optimal region search with submodular maximization (ORS-SM). This problem considers a region as a connected subgraph. We compute an objective value over the locations in the region using a submodular function and a budget value by summing up the costs of edges in the region, and aim to search the region with the largest objective score under a budget value constraint. ORS-SM supports many applications such as the most diversified region search. We prove that the problem is NP-hard and develop two approximation algorithms with guaranteed error bounds. We conduct experiments on two applications using three real-world datasets. The results demonstrate that our algorithms can achieve high-quality solutions and are faster than a state-of-the-art method by orders of magnitude.

Given a set of server points (e.g., locations) P and a set of client points (e.g., users) O, the problem of maximizing bichromatic reverse k-nearest neighbor (MaxBRkNN) aims to find a region for setting up a new service site such that it can influence the most clients, i.e., it is in the kNN results of most client points. All existing studies first compute the kNN of client points and then perform the MaxBRkNN search. However, computing kNN for all clients is extremely time consuming especially on large datasets. Observing this, we develop an approach which computes kNN for only promising clients by utilising a two-level grid index (ADPGI) to reduce the cost substantially. Empirical studies on both real and synthetic datasets show that our proposed exact algorithm is 3 to 5 times faster than two state-of-the-art MaxBRkNN algorithms.

Meme automaton is an adaptive entity that autonomously acquires an increasing level of capability and intelligence through embedded memes evolving independently or via social interactions. This paper begins a study on memetic multiagent system (MeMAS) toward human-like social agents with memetic automaton. We introduce a potentially rich meme-inspired design and operational model, with Darwin's theory of natural selection and Dawkins' notion of a meme as the principal driving forces behind interactions among agents, whereby memes form the fundamental building blocks of the agents' mind universe. To improve the efficiency and scalability of MeMAS, we propose memetic agents with structured memes in this paper. Particularly, we focus on meme selection design where the commonly used elitist strategy is further improved by assimilating the notion of like-attracts-like in the human learning. We conduct experimental study on multiple problem domains and show the performance of the proposed MeMAS on human-like social behavior.

Point-of-interest(POI) recommendation becomes a valuable service in location-based social networks. Based on the norm that similar users are likely to have similar preference of POIs, the current recommendation techniques mainly focus on users' preference to provide accurate recommendation results. This tends to generate a list of homogeneous POIs that are clustered into a narrow band of location categories(like food, museum, etc.) in a city. However, users are more interested to taste a wide range of flavors that are exposed in a global set of location categories in the city.In this paper, we formulate a new POI recommendation problem, namely top-K location category based POI recommendation, by introducing information coverage to encode the location categories of POIs in a city.The problem is NP-hard. We develop a greedy algorithm and further optimization to solve this challenging problem. The experimental results on two real-world datasets demonstrate the utility of new POI recommendations and the superior performance of the proposed algorithms.

Influence maximization problem is to find a set of seed nodes in a social network such that their influence spread is maximized under certain propagation models. A few algorithms have been proposed for solving this problem. However, they have not considered the impact of novelty decay on influence propagation, i.e., repeated exposures will have diminishing influence on users. In this paper, we consider the problem of influence maximization with novelty decay (IMND). We investigate the effect of novelty decay on influence propagation on real-life datasets and formulate the IMND problem. We further analyze the problem properties and propose an influence estimation technique. We demonstrate the performance of our algorithms on four social networks.

Memetic multiagent system emerges as an enhanced version of multiagent systems with the implementation of meme-inspired computational agents. It aims to evolve human-like behavior of multiple agents by exploiting the Dawkins' notion of a meme and Universal Darwinism. Previous research has developed a computational framework in which a series of memetic operations have been designed for implementing human-like agents. This paper will focus on improving the human-like behavior of multiple agents when they are engaged in social interactions. The improvement is mainly on how an agent shall learn from others and adapt its behavior in a complex dynamic environment. In particular, we design a new mechanism that supervises how the agent shall select one of the other agents for the learning purpose. The selection is a trade-off between the elitist and like-attracts-like principles. We demonstrate the desirable interactions of multiple agents in two problem domains.