The liveness of Petri nets (PNs) means that every event can occur in any state, establishing a close relationship with the deadlock-free property of existing systems. Due to the problem of state space explosion and the infinite state space of unbounded PNs (UPNs), the time complexity and space complexity of the liveness decision are difficult to give accurate measures; at least, they are both NP-hard. Except for some particular subclasses of UPNs, there has not been an accurate method to decide the liveness of generalized UPNs. Thus, a liveness decision method from a machine learning perspective is proposed to predict probability values about UPNs’ liveness within a finite time. The method aims to learn the feature information on UPNs by deep neural networks and establish the mapping relationship between the UPNs and the liveness. First, the concept of approximating infinite space with finite states is applied to generate reachability graphs at different moments, following the firing rules of a UPN. Then, the graph convolutional network (GCN)-based reachability graph feature representation module and the gated recurrent unit (GRU)-based UPN feature representation module are designed to map the reachability graphs at different moments into the low-dimensional feature space. And the feature vector that can characterize the UPN’s liveness is obtained to decide the liveness probabilistically. Finally, three datasets, including 50000 samples, are constructed. Based on these datasets and some case studies, the experimental results validate the method’s ability to make liveness decisions for UPNs, demonstrating its strong performance in terms of effectiveness and generalization.
10 May 2023 in IEEE Transactions on Automation Science and Engineering
Unbounded Petri nets (UPNs) can describe and analyze discrete event systems with infinite states (DESIS). Due to the infinite state space and the combination explosion problem, the reachability analysis of UPNs is an NP-Hard problem. The existing reachability analysis methods cannot achieve an accurate result at reasonable costs (computational time and space) due to the finite reachability tree with $\omega$ -numbers. Based on the idea of approximating infinite space with finite states, given some limited reachable markings of a UPN, we propose a method that can quantitatively solve the UPN’s reachability problem with machine learning. Firstly, we define the probabilistic reachability of markings and transform the UPN’s reachability problem into the prediction problem of markings. The proposed method based on positive and unlabeled learning (PUL) and bagging trains a classifier to predict the probabilistic reachability of unknown markings. Finally, to predict the markings outside the positive sample set and unlabeled sample set, an iterative strategy is designed to update the classifier. Based on seven general UPNs, the results of the experiments show that the proposed method has a good performance in the accuracy and time consumption for the UPN’s reachability problem. Note to Practitioners —In discrete event systems, the reachability problem mainly studies reachable states of the system and the relationship between states, which is the basis of the system’s states, behaviors, attributes and performance analysis. For discrete event systems with infinite states, it is hard to analyze the reachable relationship between states within a finite time due to the infinite state space and the combination explosion problem. The main motivation of the paper is to propose a method that can predict the reachable relationship between the states with a probability value within a finite time. By machine learning algorithms, the method learns the feature information of the known reachable states. The reachability of unknown states in the infinite state space can be predicted approximately. The proposed approximation method can be applied to analyze the reachability properties of general discrete event systems with infinite states, such as checking whether a fault occurs in operating systems, whether a message is delivered in communication and so on.
Graph Neural Networks (GNNs) are susceptible to adversarial injection attacks, potentially compromising the model integrity, reducing accuracy, and posing security risks. However, most of the current countermeasures focus on enhancing the robustness of GNNs rather than directly addressing these specific attacks. The challenge stems from the difficulty of protecting all nodes in the entire graph and the agnostic of the attackers. Therefore, we propose a secure training strategy for GNNs that counters the vulnerability to adversarial injection attacks and overcomes the obstacle of partial observability in existing defense mechanisms—where defenders are only aware of the graph’s post-attack structure and node attributes, without the identification of compromised nodes. Our strategy not only protects specific nodes but also extends security to all nodes in the graph. We model the graph security issues as a Partially Observable Markov Decision Process (POMDP) and use Graph Convolutional Memory (GCM) to transform the observations of a POMDP into states with temporal memory proceeding to use reinforcement learning to solve for the optimal defensive strategy. Finally, we prevent learning from malicious nodes by limiting the convolutional scope, thus defending against adversarial injection attacks. Our defense method is evaluated on five datasets, achieving an accuracy range of 74% to 86.7%, which represents an enhancement of approximately 5.09% to 100.26% over post-attack accuracies. Compared with various traditional experimental models, our method shows an accuracy improvement ranging from 0.82% to 100.26%.
Traditional social recommendation methods often focus on static representations of users and items, neglecting dynamic changes in user interests and item attractiveness over time, which makes it challenging to adapt to temporal variations in user interests. Additionally, the propagation of information along explicit social relationships tends to over-smooth features and weaken individual preferences, while static implicit relationships may increase short-term noise. Thus, a Dual-channel Controllable Diffusion Network based on Hybrid Representations (HR-DCDN) is proposed for social recommendation. The HR-DCDN first incorporates temporal factors by combining dynamic and static representations to capture changes in user interests and item attractiveness. Then, our method proposes a dual-channel aggregation mechanism to obtain higher-order representations of users and items. Explicit social relationships serve as the social-influence channel, while implicit social relationships discovered via dynamic implicit relationship mining constitute the preference-homophily channel. In addition, a learnable polynomial spectral filter incorporates residual connections and dual-channel fusion information at each propagation step, stabilizing deep propagation and alleviating representation homogenization to a limited extent while preserving high-frequency preference information. Finally, we jointly optimize a cross-layer InfoNCE objective on the perturbed interaction branch with the supervised rating loss, which provides an additional empirical regularization effect, improves robustness, and helps preserve representation diversity without altering the graph structure. Experimental results demonstrate that our model outperforms baseline methods on two real-life social datasets.