Search

The widespread use of the internet has led to an overwhelming amount of data, which has resulted in the problem of information overload. Recommender systems have emerged as a solution to this problem by providing personalized recommendations to users based on their preferences and historical data. However, as recommendation models become increasingly complex, finding the best hyperparameter combination for different models has become a challenge. The high-dimensional hyperparameter search space poses numerous challenges for researchers, and failure to disclose hyperparameter settings may impede the reproducibility of research results. In this paper, we investigate the Top-N implicit recommendation problem and focus on optimizing the benchmark recommendation algorithm commonly used in comparative experiments using hyperparameter optimization algorithms. We propose a research methodology that follows the principles of a fair comparison, employing seven types of hyperparameter search algorithms to fine-tune six common recommendation algorithms on three datasets. We have identified the most suitable hyperparameter search algorithms for various recommendation algorithms on different types of datasets as a reference for later study. This study contributes to algorithmic research in recommender systems based on hyperparameter optimization, providing a fair basis for comparison.

Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal \lambda-frequency group (MFG). Given a temporal bipartite graph G=(U,V,E), a vertex set V_S \subseteq V is an MFG if i) there are no less than \lambda timestamps, at each of which V_S can form a (t_U,t_V)-biclique with some vertices in U at the corresponding snapshot, and ii) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O(|V|). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.

A signed graph is a graph where each edge receives a sign, positive or negative. The signed graph model has been used in many real applications, such as protein complex discovery and social network analysis. Finding cohesive subgraphs in signed graphs is a fundamental problem. A k-plex is a common model for cohesive subgraphs in which every vertex is adjacent to all but at most k vertices within the subgraph. In this paper, we propose the model of size-constrained antagonistic k-plex in a signed graph. The proposed model guarantees that the resulting subgraph is a k-plex and can be divided into two sub-k-plexes, both of which have positive inner edges and negative outer edges. This paper aims to identify all maximal antagonistic k-plexes in a signed graph. Through rigorous analysis, we show that the problem is NP-Hardness. We propose a novel framework for maximal antagonistic k-plexes utilizing set enumeration. Efficiency is improved through pivot pruning and early termination based on the color bound. Preprocessing techniques based on degree and dichromatic graphs effectively narrow the search space before enumeration. Extensive experiments on real-world datasets demonstrate our algorithm's efficiency, effectiveness, and scalability.

Given a graph G, a budget k and a misinformation seed set S, Influence Minimization (IMIN) via node blocking aims to find a set of k nodes to be blocked such that the expected spread of S is minimized. This problem finds important applications in suppressing the spread of misinformation and has been extensively studied in the literature. However, existing solutions for IMIN still incur significant computation overhead, especially when k becomes large. In addition, there is still no approximation solution with non-trivial theoretical guarantee for IMIN via node blocking prior to our work. In this paper, we conduct the first attempt to propose algorithms that yield data-dependent approximation guarantees. Based on the Sandwich framework, we first develop submodular and monotonic lower and upper bounds for our non-submodular objective function and prove the computation of proposed bounds is \#P-hard. In addition, two advanced sampling methods are proposed to estimate the value of bounding functions. Moreover, we develop two novel martingale-based concentration bounds to reduce the sample complexity and design two non-trivial algorithms that provide (1-1/e-\epsilon)-approximate solutions to our bounding functions. Comprehensive experiments on 9 real-world datasets are conducted to validate the efficiency and effectiveness of the proposed techniques. Compared with the state-of-the-art methods, our solutions can achieve up to two orders of magnitude speedup and provide theoretical guarantees for the quality of returned results.

We investigate the generation of optical shock waves in strongly interacting Rydberg atomic gases with a spatially homogeneous dissipative potential. The Rydberg atom interaction induces an optical nonlocal nonlinarity. We focus on local nonlinear ($R_b\ll R_0$) and nonlocal nonlinear ($R_b\sim R_0$) regimes, where $R_b$ and $R_0$ are the characteristic length of the Rydberg nonlinearity and beam width, respectively. In the local regime, we show spatial width and contrast of the shock wave change monotonically when increasing strength of the dissipative potential and optical intensity. In the nonlocal regime, the characteristic quantity of the shock wave depend on $R_b/R_0$ and dissipative potential nontrivially and on the intensity monotonically. We find that formation of shock waves dominantly takes place when $R_b$ is smaller than $R_0$, while the propagation dynamics is largely linear when $R_b$ is comparable to or larger than $R_0$. Our results reveal nontrivial roles played by dissipation and nonlocality in the generation of shock waves, and provide a route to manipulate their profiles and stability. Our study furthermore opens new avenues to explore non-Hermitian physics, and nonlinear wave generation and propagation by controlling dissipation and nonlocality in the Rydberg media., Comment: 14 pages, 10 figures

We systematically investigate unconventional superfluid phases of fermionic dipolar particles lying in a double-wire setup with laser-assisted interwire tunneling. Our numerical simulations, based on the nonlocal Kohn-Sham Bogoliubov-de Gennes equation, reveal the existence of a large Fulde-Ferrell-Larkin-Ovchinnikov (FFLO) region with a stripe phase under an imbalance of particle densities between two wires. When the laser-assisted interwire tunneling is present, it induces a transition from the FFLO phase to the topological superfluid phase and the associated Majorana zero modes exhibit an oscillation structure, which is significantly enhanced by the long-range nature of the interwire dipolar interaction. This distinguishes itself from the results obtained with usual contact interaction and offers new opportunities for manipulating and reshaping Majorana zero modes by adjusting the degree of the nonlocality and the interwire separation., Comment: 8 pages, 6 figures

By effectively controlling the dipole-dipole interaction, we investigate the characteristics of the ground state of bright solitons in a spin-orbit coupled dipolar Bose-Einstein condensate. The dipolar atoms are trapped within a double-lattice which consists of a linear and a nonlinear lattice. We derive the motion equations of the different spin components, taking the controlling mechanisms of the diolpe-dipole interaction into account. An analytical expression of dipole-dipole interaction is derived. By adjusting the dipole polarization angle, the dipole interaction can be adjusted from attraction to repulsion. On this basis, we study the generation and manipulation of the bright solitons using both the analytical variational method and numerical imaginary time evolution. The stability of the bright solitons is also analyzed and we map out the stability phase diagram. By adjusting the long-range dipole-dipole interaction, one can achieve manipulation of bright solitons in all aspects, including the existence, width, nodes, and stability. Considering the complexity of our system, our results will have enormous potential applications in quantum simulation of complex systems.

We investigate the the itinerant ferromagnetism in a dipolar Fermi atomic system with the anisotropic spin-orbit coupling (SOC),which is traditionally explored with isotropic contact interaction.We first study the ferromagnetism transition boundaries and the properties of the ground states through the density and spin-flip distribution in momentum space, and we find that both the anisotropy and the magnitude of the SOC play an important role in this process. We propose a helpful scheme and a quantum control method which can be applied to conquering the difficulties of previous experimental observation of itinerant ferromagnetism. Our further study reveals that exotic Fermi surfaces and an abnormal phase region can exist in this system by controlling the anisotropy of SOC, which can provide constructive suggestions for the research and the application of a dipolar Fermi gas. Furthermore, we also calculate the ferromagnetism transition temperature and novel distributions in momentum space at finite temperature beyond the ground states from the perspective of experiment., Comment: 8 pages,7 figures

We propose a scheme for the creation of stable optical Ferris wheel(OFW) solitons in a nonlocal Rydberg electromagnetically induced transparency(EIT) medium. Depending on a careful optimization to both the atomic density and the one-photon detuning, we obtain an appropriate nonlocal potential provided by the strong interatomic interaction in Rydberg states which can perfectly compensate for the diffraction of the probe OFW field. Numerical results show that the fidelity keeps larger than 0.96 while the propagation distance has exceeded 160 diffraction lengths. Higher-order OFW solitons with arbitrary winding numbers are also discussed. Our study provides a straightforward route to generate spatial optical solitons in the nonlocal response region of cold Rydberg gases., Comment: Optics Letters in press

The Feedback vertex set with the minimum size is one of Karp's 21 NP-complete problems targeted at breaking all the cycles in a graph. This problem is applicable to a broad variety of domains, including E-commerce networks, database systems, and program analysis. In reality, users are frequently most concerned with the hop-constrained cycles (i.e., cycles with a limited number of hops). For instance, in the E-commerce networks, the fraud detection team would discard cycles with a high number of hops since they are less relevant and grow exponentially in size. Thus, it is quite reasonable to investigate the feedback vertex set problem in the context of hop-constrained cycles, namely hop-constrained cycle cover problem. It is concerned with determining a set of vertices that covers all hop-constrained cycles in a given directed graph. A common method to solve this is to use a bottom-up algorithm, where it iteratively selects cover vertices into the result set. Based on this paradigm, the existing works mainly focus on the vertices orders and several heuristic strategies. In this paper, a totally opposite cover process topdown is proposed and bounds are presented on it. Surprisingly, both theoretical time complexity and practical performance are improved.

Bound states of solitons, alias soliton molecules (SMs), are well known in one-dimensional (1D) systems, while making stable bound states of multidimensional solitons is a challenging problem because of the underlying instabilities. Here we propose a scheme for the creation of stable (2+1)D and (3+1)D optical SMs in a gas of cold Rydberg atoms, in which electromagnetically induced transparency (EIT) is induced by a control laser field. We show that, through the interplay of the EIT and the strong long-range interaction between the Rydberg atoms, the system gives rise to giant nonlocal Kerr nonlinearity, which in turn supports stable (2+1)D spatial optical SMs, as well as ring-shaped soliton necklaces, including rotating ones. They feature a large size, low generation power, and can be efficiently manipulated by tuning the nonlocality degree of the Kerr nonlinearity. Stable (3+1)D spatiotemporal optical SMs, composed of fundamental or vortex solitons, with low power and ultraslow propagation velocity, can also be generated in the system. These SMs can be stored and retrieved through the switching off and on of the control laser field. The findings reported here suggest applications to data processing and transmission in optical systems., Comment: The manuscript has been accepted by laser & Photonics Reviews for publication

Higher-order exceptional points (EPs), which appear as multifold degeneracies in the spectra of non-Hermitian systems, are garnering extensive attention in various multidisciplinary fields. However, constructing higher-order EPs still remains as a challenge due to the strict requirement of the system symmetries. Here we demonstrate that higher-order EPs can be judiciously fabricated in PT -symmetric staggered rhombic lattices by introducing not only on-site gain/loss but also nonHermitian couplings. Zero-energy flatbands persist and symmetry-protected third-order EPs (EP3) arise in these systems owing to the non-Hermitian chiral/sublattice symmetry, but distinct phase transitions and propagation dynamics occur. Specifically, the EP3 arises at the Brillouin zone (BZ) boundary in the presence of on-site gain/loss. The single-site excitations display an exponential power increase in the PT -broken phase. Meanwhile, a nearly flatband sustains when a small lattice perturbation is applied. For the lattices with non-Hermitian couplings, however, the EP3 appears at the BZ center. Quite remarkably, our analysis unveils a dynamical delocalization-localization transition for the excitation of the dispersive bands and a quartic power increase beyond the EP3. Our scheme provides a new platform towards the investigation of the higher-order EPs, and can be further extended to the study of topological phase transitions or nonlinear processes associated with higher-order EPs., Comment: 10 pages, 10 figures

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. However, in real world, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks. Following the balanced clique model, we study the maximal balanced clique enumeration problem (MBCE) which computes all the maximal balanced cliques in a given signed network and the maximum balanced clique search problem (MBCS) which computes the balanced clique with maximum size. We show that MBCE problem and MBCS problem are both NP-Hard. For the MBCE problem, a straightforward solution is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. For the MBCS problem, we propose a new search framework based on search space partition. To further improve the efficiency of the new framework, we propose multiple optimization strategies regarding to redundant search branches and invalid candidates. We conduct extensive experiments on large real datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms for MBCE problem and MBCS problem.

Subgraph matching is a fundamental problem in various fields that use graph structured data. Subgraph matching algorithms enumerate all isomorphic embeddings of a query graph q in a data graph G. An important branch of matching algorithms exploit the backtracking search approach which recursively extends intermediate results following a matching order of query vertices. It has been shown that the matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In recent years, many advanced techniques for query vertex ordering (i.e., matching order generation) have been proposed to reduce the unpromising intermediate results according to the preset heuristic rules. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms. Instead of using the fixed heuristics to generate the matching order, our model could capture and make full use of the graph information, and thus determine the query vertex order with the adaptive learning-based rule that could significantly reduces the number of redundant enumerations. With the help of the reinforcement learning framework, our model is able to consider the long-term benefits rather than only consider the local information at current ordering step.Extensive experiments on six real-life data graphs demonstrate that our proposed matching order generation technique could reduce up to two orders of magnitude of query processing time compared to the state-of-the-art algorithms., Comment: Accepted by ICDE 2022

In this paper, we improve the cube attack by exploiting low-degree factors of the superpoly w.r.t. certain "special" index set of cube (ISoC). This can be viewed as a special case of the correlation cube attack proposed at Eurocrypt 2018, but under our framework more beneficial equations on the key variables can be obtained in the key-recovery phase. To mount our attack, one has two challenging problems: effectively recover algebraic normal form of the superpoly and extract out its low-degree factors; and efficiently search a large quantity of good ISoCs. We bring in new techniques to solve both of them. First, we propose the variable substitution technique for middle rounds of a cipher, in which polynomials on the key variables in the algebraic expressions of internal states are substituted by new variables. This will improve computational complexity of the superpoly recovery and promise more compact superpolys that can be easily decomposed with respect to the new variables. Second, we propose the vector numeric mapping technique, which seeks out a tradeoff between efficiency of the numeric mapping technique and accuracy of the monomial prediction technique in degree evaluation of superpolys. Combining with this technique, a fast pruning method is given and modeled by MILP to filter good ISoCs of which the algebraic degree satisfies some fixed threshold. Thanks to automated MILP solvers, it becomes practical to comprehensively search for good cubes across the entire search space. To illustrate the power of our techniques, we apply all of them to Trivium stream cipher. The previous best practical key recovery attack was on 820-round Trivium with complexity $2^{53.17}$. We put forward 820-, 825- and 830-round practical key-recovery attacks, in which there are 2^{80}\times 87.8%, 2^{80}\times 83% and 2^{80}\times 65.7% keys that could be practically recovered, respectively.

We investigate the Kerr and magneto-optical effects for a probe laser field with two orthogonally polarized components, propagating in a cold Rydberg atomic gas with an inverted-Y-type level configuration via double electromagnetically induced transparency (EIT). Through an approach beyond both mean-field and ground-state approximations, we make detailed calculations on third-order nonlinear optical susceptibilities and show that the system possesses giant nonlocal selfand cross-Kerr nonlinearities contributed by Rydberg-Rydberg interaction. The theoretical result of the cross-Kerr nonlinearity obtained for 85Rb atomic gas is very close to the experimental one reported recently. Moreover, we demonstrate that the probe laser field can acquire a very large magnetooptical rotation via the double EIT, which may be used to design atomic magnetometers with high precision. The results presented here are promising not only for the development of nonlocal nonlinear magneto-optics but also for applications in precision measurement and optical information processing and transmission based on Rydberg atomic gases.

Subgraph matching is a basic operation widely used in many applications. However, due to its NP-hardness and the explosive growth of graph data, it is challenging to compute subgraph matching, especially in large graphs. In this paper, we aim at scaling up subgraph matching on a single machine using FPGAs. Specifically, we propose a CPU-FPGA co-designed framework. On the CPU side, we first develop a novel auxiliary data structure called candidate search tree (CST) which serves as a complete search space of subgraph matching. CST can be partitioned and fully loaded into FPGAs' on-chip memory. Then, a workload estimation technique is proposed to balance the load between the CPU and FPGA. On the FPGA side, we design and implement the first FPGA-based subgraph matching algorithm, called FAST. To take full advantage of the pipeline mechanism on FPGAs, task parallelism optimization and task generator separation strategy are proposed for FAST, achieving massive parallelism. Moreover, we carefully develop a BRAM-only matching process to fully utilize FPGA's on-chip memory, which avoids the expensive intermediate data transfer between FPGA's BRAM and DRAM. Comprehensive experiments show that FAST achieves up to 462.0x and 150.0x speedup compared with the state-of-the-art algorithm DAF and CECI, respectively. In addition, FAST is the only algorithm that can handle the billion-scale graph using one machine in our experiments., Comment: 14 pages, ICDE 2021

Bipartite graphs are widely used to model relationships between two types of entities. Community search retrieves densely connected subgraphs containing a query vertex, which has been extensively studied on unipartite graphs. However, community search on bipartite graphs remains largely unexplored. Moreover, all existing cohesive subgraph models on bipartite graphs can only be applied to measure the structure cohesiveness between two sets of vertices while overlooking the edge weight in forming the community. In this paper, we study the significant (alpha, beta)-community search problem on weighted bipartite graphs. Given a query vertex q, we aim to find the significant (alpha, beta)-community R of q which adopts (alpha, beta)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within R. To support fast retrieval of R, we first retrieve the maximal connected subgraph of (alpha, beta)-core containing the query vertex (the (alpha, beta)-community), and the search space is limited to this subgraph with a much smaller size than the original graph. A novel index structure is presented which can be built in O(delta * m) time and takes O(delta * m) space where m is the number of edges in G, delta is bounded by the square root of m and is much smaller in practice. Utilizing the index, the (alpha, beta)-community can be retrieved in optimal time. To further obtain R, we develop peeling and expansion algorithms to conduct searches by shrinking from the (alpha, beta)-community and expanding from the query vertex, respectively. The experimental results on real graphs not only demonstrate the effectiveness of the significant (alpha, beta)-community model but also validate the efficiency of our query processing and indexing techniques.