Search

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.

Ultrasmall Au nanoclusters have been proven to effectively enhance the catalytic performance of NiFe layered double hydroxides (NiFe-LDHs) toward oxygen evolution reaction (OER), yet the surface ligand effect of the Au nanoclusters still remains elusive. Herein, a systematic study is reported to examine the OER performance of NiFe-LDHs supported atom-precise all alkynyl-protected [Au28(tBuC≡C)17]− nanoclusters (Au28-Alkynyl in short) and thiolate-protected Au28(TBBT)20 (TBBT = 4-tert-butylbenzenethiol) counterparts (Au28-Thiolate in short). The Au28-Alkynyl cluster has characteristic absorbance feature, and its composition is verified by mass spectrometry. It possesses a drastically different structure from the reported mixed ligand protected Au28 nanoclusters. Interestingly, the NiFe-LDHs loaded with Au28-Alkynyl exhibited a superior OER performance than the sample loaded with Au28-Thiolate under the same conditions, evidenced by a smaller overpotential of 205 mV at the current density of 10 mA·cm−2 and a lower Tafel slope value of 41.0 mV·dec−1 in 1 mol·L−1 KOH. Such excellent performance is attributed to the interfaces created between the NiFe-LDHs and the Au nanoclusters, as density functional theory calculations reveal that more significant charge transfer occurs in Au28-Alkynyl/NiFe-LDHs catalyst, and more importantly, the energy barrier of the potential-determining step in the OER process for Au28-Alkynyl/NiFe-LDHs is much lower than that of Au28-Thiolate/NiFe-LDHs hence favors the electrocatalytic reaction.

Xiao-kun Liu,1,* Dan-ling Huang,1,2,* Li-ping Meng,1 Wei Cheng,1 Yi-yi Li,1 Lu-lu Qin,3 Ao Yang,4 Fan Zeng,5 Qin Zou,1 Qi-fu Li6 1Clinical Psychology Department, The First Affiliated Hospital of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China; 2Neurology Department, Graduate School of Tianjin Medical University, Tianjin City, People’s Republic of China; 3Department of Social Medicine and Health Management, School of Medicine, Hunan Normal University, Changsha City, Hunan Province, People’s Republic of China; 4Health Management Department, School of Management of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China; 5Graduate School of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China; 6Neurology Department, The First Affiliated Hospital of Hainan Medical University, Haikou City, Hainan Province, People’s Republic of China*These authors contributed equally to this workCorrespondence: Xiao-kun Liu; Qi-fu Li, Email lacyfairy@qq.com; lee-chief@163.comAim: This study was designed to develop an effective measurement tool for occupational stress among medical staff and to identify the underlying risk factors among clinical nurses in China under depression during and after COVID-19.Methods: In the first stage, an occupational stress scale was developed for medical staff based on qualitative and quantitative methods. The dimensions of the scale were based on childhood stress and seven other parameters of working stress. In the second stage, a provincial survey was conducted among clinical nurses in Hainan. The structure of Medical Staff Occupational Stress Scale was tested in secondary and tertiary hospitals. The socio-demographic information, occupational stress (measured using the developed scale), and current depression symptoms (assessed with the nine‐item Patient Health Questionnaire) were evaluated. The risk factors for occupational

Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design efficient query processing and index construction algorithms with good performance guarantees. Moreover, due to the dynamic properties of real-world networks, we also devise index maintenance algorithms that can maintain the index efficiently. To evaluate the performance of proposed methods, we conduct extensive experimental studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to two orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the experimental results also show that the index can also be efficiently constructed and maintained for dynamic graphs.

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.

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.

Bipartite graphs are naturally used to model relationships between two different types of entities. On bipartite graphs, maximum biclique search is a fundamental problem that aims to find the complete bipartite subgraph (biclique) with the maximum number of edges and is widely adopted for many applications such as anomaly detection in E-commerce and social network analysis. However, maximum biclique search only identifies the biclique whose size is globally maximum, whereas fast microscopic (personalized) analysis is needed in many real-world scenarios. For instance, when a suspected user is identified in an E-commerce network (e.g., a user-product network), it is important to quickly find the anomalous group containing the user and send the group of users for further human expert investigation. To fill this research gap, for the first time, we study the efficient personalized maximum biclique search problem, which aims to find the maximum biclique containing a specific query vertex in real-time. Apart from online computation algorithms, we explore index-based approaches and propose the PMBC-Index. With the PMBC-Index, the query algorithm is up to five orders of magnitude faster than the baseline algorithms. Furthermore, effective pruning strategies and parallelization techniques are devised to support efficient index construction. Extensive experiments on 10 real-world graphs validate both the effectiveness and the efficiency of our proposed techniques.

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.

Subgraph counting is a fundamental graph analysis task which has been widely used in many applications. As the problem of subgraph counting is NP-complete and hence intractable, approximate solutions have been widely studied, which fail to work with large and complex query graphs. Alternatively, Machine Learning techniques have been recently applied for this problem, yet the existing ML approaches either only support very small data graphs or cannot make full use of the data graph information, which inherently limits their scalability, estimation accuracies and robustness. In this paper, we propose a novel approximate subgraph counting algorithm, NeurSC, that can exploit and combine information from both the query graphs and the data graphs effectively and efficiently. It consists of two components: (1) an extraction module that adaptively generates simple yet representative substructures from data graph for each query graph and (2) an estimator WEst that first computes the representations from individual and joint distributions of query and data graphs and then estimates subgraph counts with the learned representations. Furthermore, we design a novel Wasserstein discriminator in WEst to minimize the Wasserstein distance between query and data graphs by updating the parameters in network with the vertex correspondence relationship between query and data graphs. By doing this, WEst can better capture the correlation between query and data graphs which is essential to the quality of the estimation. We conduct experimental studies on seven large real-life labeled graphs to demonstrate the superior performance of NeurSC in terms of estimation accuracy and robustness.

Xiao-kun Liu,1 Shan-lin Chen,1 Dan-ling Huang,1 Zi-shang Jiang,1 Yu-ting Jiang,1 Li-juan Liang,1 Lu-lu Qin2 1The First Affiliated Hospital of Hainan Medical University, Haikou, People’s Republic of China; 2Department of Social Medicine and Health Management, School of Medicine, Hunan Normal University, Changsha, People’s Republic of ChinaCorrespondence: Xiao-kun LiuThe First Affiliated Hospital of Hainan Medical University, 3 Xueyuan Road, Haikou, 571199, Hainan, People’s Republic of ChinaEmail lacyfairy@qq.comPurpose: Road safety research is important due to the large number of road traffic fatalities globally. This study investigated the influences of age, driving experience and other covariates on aggressive driving behavior.Methods: A cross-sectional survey was conducted in Yixing City, Wuxi City, Jiangsu Province, China. Regression analysis was applied to explore the influences of age and driving experience and their interactions with other covariates on aggressive driving behavior. Two analyses methodologies were used to assess the simple effect of the interactions. Firstly, the Jamovi automatic analysis classification program was used to calculate the simple slope test. Second, the SPSS macro program was also used to calculate the simple slope test also.Results: A total of 570 drivers (247 males, 282 females) participated in the survey. A negative correlation was found between age and aggressive driving behaviors, and a positive correlation was found between neuroticism and aggressive driving behaviors in the multiple regression analysis. Significant associations were also found between age, driving experience, and depression, as well as age, driving experience, and neuroticism. Simple slope tests showed that depressive symptoms could increase aggressive behaviors in the elderly and experienced drivers. When experiencing neuroticism, individuals with higher driving experience were more aggressive in driving than shorter experienced drivers.Conclusion: A