Maximal Frequent Subgraph (MFS) mining asks to identify the maximal subgraph that commonly appears in a set of graphs, which has been found valuable in many applications in social science, biology, and other domains. Previous studies focused on reducing the search space of MFSs and discovered the theoretically smallest search space. Despite the success in theory, no practical algorithm can exhaustively search the space as it is huge even for small graphs with only tens of nodes and hundreds of edges. Moreover, deciding whether a subgraph is an MFS needs to solve subgraph monomorphism (SM), an NP-complete problem that introduces extra challenges. Here, we propose a practical MFS mining algorithm that targets large MFSs, named SATMargin. SATMargin adopts random walk in the search space to perform efficient search and utilizes a customized conflict learning Boolean Satisfiability (SAT) algorithm to accelerate SM queries. We design a mechanism that reuses SAT solutions to combine the random walk and the SAT solver effectively. We evaluate SATMargin over synthetic graphs and 6 real-world graph datasets. SATMargin shows superior performance to baselines in finding more and larger MFSs. We further demonstrate the effectiveness of SATMargin in a case study of RNA graphs. The identified frequent subgraph by SATMargin well matches the functional core structure of RNAs previously detected in biological experiments. Our software can be found at https://github.com/MuyiLiu2022/SATMargin-and-Baselines.

We present algorithms of the channel and carrier frequency offset (CFO) estimation for burst-mode continuous phase modulation (CPM) transmission with optimized training waveforms, which are obtained through minimizing the Cramer-Rao bound (CRB). Wirtinger calculus, which provides a framework for complex-valued signal processing, is used to simplify the derivations of CRBs and maximum likelihood estimation. Unlike linear modulation, the training waveform is optimized not only with respect to the modulated training sequence but also the sampling delay and sampling rate due to the continuous phase of CPM waveforms. In order to reduce the computation complexity of the optimization, we derive a closed-form expression for efficient computation of the objective function. The numerical results demonstrate the significant performance improvement of the optimized waveforms compared to the training sequences of previous works. Based on that, we propose two schemes for CFO estimation. The first scheme is a suboptimal maximum likelihood estimation of the CFO and it achieves a better trade-off between the estimation accuracy and complexity compared to optimal maximum likelihood estimation. The second scheme is based on the channel estimation, which leads to much lower implementation complexity than the other estimators. Finally, the measured bit error rate reveals the considerable gain of the estimation algorithm with the optimized training waveform.

Frequent Subgraph Mining is important in many scientific fields including molecular biology, genomics, and chemistry. Graphs are used to represent specific structures, and by finding common subgraphs one can infer common properties. Identification of maximum frequent subgraphs, therefore, provides an approach to reveal hidden knowledge shared among graphs, and classify graphs into informative categories. Most existing algorithms explicitly explore the frequent subgraph space by depth-first or breadth-first search, and traverse the entire lattice of subgraphs. However, explicit search for subgraph isomorphism is NP-complete, and limited to small graphs. We propose MMC-Margin, a Metropolis Monte Carlo approach that extends the idea of the Margin search space to greatly reduce time and space complexity. We apply our method to three domain examples: RNA structure graphs from actual biological structures, artificially constructed RNA graphs with known common structures, and structures of chemical mutagens. Our experiments show that MMC-Margin effectively identifies maximum frequent patterns in subgraph spaces where exact algorithms encounter time and space issues. Specifically, we find that MMC-Margin can find the maximum common subgraph in these datasets in as little as 120 seconds, whereas, a complete search with Margin takes hundreds or even thousands of CPU hours. In addition to time efficiency, the MCMC approach requires little memory. The MMC-margin approach described here allows the identification of common subgraphs in biological and chemical datasets and the expansion of using subgraph isomorphism in extracting latent information.