Multimodal graph-based recommendation has shown strong potential by jointly modeling user–item interactions and rich multimodal item content. However, existing methods often suffer from noisy features, severe popularity bias, and uniform message propagation that fails to adapt to heterogeneous item popularity and varying signal reliability. To address these issues, we propose PAMS-GNN, a Popularity-Aware Multimodal Semantic Graph Neural Network that formulates recommendation as conditional message passing over collaborative and semantic graphs. The core idea is to adapt both propagation behaviors and channel reliability according to item popularity and local structural conditions. PAMS-GNN introduces a compact prototype-based framework with popularity-aware routing, enabling items from different popularity regimes to adopt distinct multi-hop propagation behaviors with minimal overhead. In addition, a variance-guided fusion mechanism adaptively balances collaborative and semantic signals based on local reliability, while lightweight projection and gating are used to purify multimodal representations and stabilize semantic graph construction. Extensive experiments on multiple benchmarks demonstrate that PAMS-GNN consistently outperforms state-of-the-art methods, effectively alleviating popularity bias and improving long-tail recommendation performance with favorable efficiency.

Discovering cohesive groups is a fundamental primitive in graph-based recommender systems, underpinning tasks such as social recommendation, bundle discovery, and community-aware modeling. In interaction graphs, cohesion is often modeled as the γ-quasi-clique, an induced subgraph whose internal edge density meets a user-defined threshold γ. This formulation provides explicit control over within-group connectivity while accommodating the sparsity inherent in real-world data. However, ensuring explicit density constraints while maintaining robustness remains challenging for existing heuristic approaches. This paper presents EDQC, an effective framework for cohesive group discovery under explicit density constraints. EDQC leverages a lightweight energy diffusion process to rank vertices for localizing promising candidate regions. Guided by this ranking, the framework extracts and refines a candidate subgraph to ensure the output strictly satisfies the target density requirement. Extensive experiments on 75 real-world graphs across varying density thresholds demonstrate that EDQC identifies the largest mean γ-quasi-cliques in the vast majority of cases, achieving lower variance than the state-of-the-art methods while maintaining competitive runtime, making it a robust and practical solution for cohesive group discovery in graph-based recommender systems.

Complete formal verification of neural networks is crucial for their deployment in safety-critical domains. A key bottleneck stems from encoding complexity: traditional methods assign one binary variable per unstable ReLU neuron. We propose the Sign-Absolute Reformulation Theory (SART), which fundamentally breaks the conventional one-to-one mapping between unstable neurons and binary variables by establishing formal reducibility criteria. This allows for finer-grained modeling, where each unstable neuron corresponds on average to fewer than one binary variable, thereby reducing verification complexity at its source. Based on SART, we derive a theoretical lower bound on the number of binary variables required for complete verification and, under the assumption that 𝑃 ≠ 𝑁𝑃, prove that variables in the final layer can be compressed by 50%, while the number of variables in intermediate layers cannot be further reduced. To overcome the apparent “last-layer-only” limitation, we recast verification as a sequential process and, crucially, show that the gain lifts to the entire network: LayerABS, a SART-based progressive tightening verifier, iteratively treats intermediate layers as temporary final layers and propagates tight bounds that shrink the global search space and binaryvariable counts. Furthermore, we reveal a structural law influencing verification complexity: when the signs of weights of unstable neurons satisfy numerical symmetry, with positive and negative weights equal or differing by at most one, the worst-case verification complexity achieves the theoretical optimum, offering theoretical guidance for the design of verification-friendly architectures. As a general-purpose underlying encoding, the value of SART is independent of specific algorithms. To comprehensively evaluate its effectiveness, we first evaluate the abstraction-free SART encoding, and then integrate it with abstraction techniques to construct the complete verifier LayerABS and its incomplete variant Incomplete-LayerABS. Across benchmarks, our methods surpass state-of-the-art baselines, validating SART’s practical impact.

The graph coloring problem (GCP) is a classic combinatorial optimization problem that aims to find the minimum number of colors assigned to the vertices of a graph such that no two adjacent vertices receive the same color. GCP has been extensively studied by researchers from various fields, including mathematics, computer science, and biological science. Due to the$\mathcal {NP}$-hard nature, many heuristic algorithms have been proposed to solve GCP. However, existing GCP algorithms focus on either small hard graphs or large-scale sparse graphs (with up to$10^{7}$vertices). This article presents an efficient hybrid heuristic algorithm for GCP, namedHyColor, which excels in handling large-scale sparse graphs while achieving impressive results on small dense graphs. The efficiency ofHyColorcomes from the following three aspects: 1) a local decision strategy to improve the lower bound on the chromatic number; 2) a graph-reduction strategy to reduce the working graph; and 3) a$k$-core and mixed degree-based greedy heuristic for efficiently coloring graphs.HyColoris evaluated against three state-of-the-art GCP algorithms across four benchmarks, comprising three large-scale sparse graph benchmarks and one small dense graph benchmark, totaling 209 instances. The results demonstrate thatHyColorconsistently outperforms existing heuristic algorithms in both solution accuracy and computational efficiency for the majority of instances. Notably,HyColorachieved the best solutions in 194 instances (over 93%), with 34 of these solutions significantly surpassing those of other algorithms. Furthermore,HyColorsuccessfully determined the chromatic number and achieved optimal coloring in 128 instances.

Real-time tactile perception with biological fidelity is critical for biomedical applications such as neural prosthetics and robotic surgeries, where sub-millisecond latency and micron-scale spatial resolution are essential. Event-based tactile sensors, inspired by mechanoreceptors, offer ultra-low latency and high energy efficiency but pose challenges for learning robust spatiotemporal representations under data scarcity and task variability. Current Spiking Graph Neural Networks (SGNNs) suffer from rigid spatial modeling and high computational costs, limiting deployment on edge devices. We propose MA-SGNN (Multi-view Adaptive SGNN), a lightweight brain-inspired framework emulating the biological tactile pathway: sensory encoding, feature extraction, and perceptual integration. MA-SGNN introduces: (1) a bio-hybrid spike encoder using Leaky Integrate-and- Fire neurons to capture temporal dynamics and extract biologically plausible features; (2) a multi-view adaptive graph constructor modeling structural and semantic taxel correlations via dynamic graphs; and (3) a spatiotemporal aggregator for efficient graph feature fusion. Evaluated on Ev-Objects and Ev-Containers benchmarks, MA-SGNN achieves competitive accuracy while reducing inference time by 59x and 90x versus state-of-the-art models. With only 10% training data, it maintains robust performance, dropping just 13.19%-significantly outperforming baselines. These results establish that MA-SGNN offers a biologically plausible and efficient solution for practical tactile intelligence.

Accurately identifying protein-protein interaction sites (PPIS) is a critical challenge. Existing graph neural network (GNN) methods for PPIS prediction often overlook higher-order structural patterns. We propose ComGAT-PPIS, a Community-Augmented Graph Attention Network that addresses this limitation. Our model constructs a hierarchical graph by first detecting residue communities and then applies a graph attention mechanism across this community level before fusing features back to the residue level. Experiments on standard benchmarks show ComGAT-PPIS consistently outperforms state-of-the-art models, highlighting the importance of incorporating meso-scale topology for enhancing GNN-based PPIS prediction. Our code is available at https://github.com/BiscuitZhang/ComGAT.

Increasing research suggests that microRNAs (miRNAs) serve an essential function as biomarkers in various diseases. The variations in miRNA expression can influence their corresponding mRNAs, which, in turn, regulate the expression of target genes. Recently, graph neural networks (GNNs) have been widely utilized to predict miRNA-disease associations. However, a single GNN model is insufficient for fully learning node representations. Furthermore, individual aggregation methods struggle to effectively extract diverse structural information and node weights. To address these challenges, we propose a method that incorporates Principal Neighborhood Aggregation (PNA) and Graph Attention Networks (GAT) for miRNA-disease association prediction. First, we integrated multiple datasets to construct a weighted heterogeneous graph that models miRNA-LncRNA-disease interactions. Subsequently, PNA extracted node representations using multiple aggregators simultaneously. Additionally, features derived from both PNA and GAT were fused using an attention mechanism. These combined representations were then fed into a fully connected neural network for prediction. Experimental results demonstrate that PNAGMDA achieves exceptional performance, with AUC values of 93.82% and 92.77% on HMDD v2.0 and v3.2, respectively. Case studies, along with supplementary findings, confirm PNAGMDA's reliability for miRNA-disease prediction.

Graphs are the primary means of describing the relation between individuals in society, and have been extensively used for analysing various types of networks, such as social networks, biological networks, and electric networks. Many practical problems can be abstracted to graph problems, and cannot be solved efficiently due to their NP-hard nature. DNA computing, leveraging the vast parallelism and high-density storage of DNA molecules, provides a new way for solving intractable problems. However, existing DNA computing models are limited by single computing function. This paper proposed a novel DNA computing model with two DNA modules-a graph representation module (GRM) and a detection module (DM)-that can solve a variety of NP-hard problems. To show the feasibility of the proposed model, we conducted simulation and biochemical experiments on multiple NP-hard problems, such as the minimum dominating set, maximum independent set, and minimum vertex cover. Experimental results showed that the GRM is a universal graph representation module, based on which multiple graph problems can be solved by cascading a proper designed detection module. Our method also highlighted the potential for DNA strand displacement to act as a computation tool to solve intractable graph problems.

The Traveling Salesman Problem is a combinatorial optimization problem that seeks to find the shortest path visiting a set of locations, where each location is visited exactly once, and the path returns to the starting point. Using traditional computing model to solve Traveling Salesman Problem would face the issue of state explosion. This paper proposes a solving method based on the probe machine model, greatly accelerating the solving speed. By iteratively adding probes and performing probe operations in sequence, both optimal and feasible solutions for this problem can be obtained. We developed a solver PROBE4TSP and presented its framework and execution process. Through comparative experiments, we demonstrate that this method is faster than some classical solvers for small-scale Traveling Salesman Problems, especially fewer than thirty nodes.

Bounded Model Checking (BMC) has been found promising in finding deep vulnerabilities in industry designs and scaling well with design sizes. However, the parallelisation of BMC is challenging, due to the propositional satisfiability (SAT) problem and satisfiability modulo theories problem solving being hard to parallelise. In this paper, we propose a novel approach to perform BMC based on the mathematical model of probe machine, which is the first approach to employ probe machine to accelerate BMC, particularly it can solve SAT formulas in full parallel. We introduce the workflow of the algorithm and explain in detail the process of mapping BMC to the probe machine. A method is provided to prove the correctness of the algorithm and to analyze its time complexity. We develop a model checker called BMC2PROBE based on our approach and explain the framework and memory management of the tool. The experiment results are discussed, which prove the feasibility and effectiveness of our approach.

Given a graph whose vertex set is partitioned, the partition coloring problem (PCP) requires the selection of one vertex from each partite set, such that the subgraph induced by the set of the selected vertices has the minimum chromatic number. Motivated by the routing and wavelength assignment problem for optical networks, PCP has been used to model many other real-world applications, such as dichotomy-based constraint encoding and scheduling problems. Solving PCP for large graphs is still a challenge since it is NP -complete. In this article, we first propose a key concept called a partition independent set (PIS) and design an efficient algorithm called FastPIS to find a maximum PIS. By applying FastPIS with a simple coloring procedure, we can obtain a high-quality initial solution for PCP. Moreover, we propose a reduction rule based on another novel concept called an l -clustering-degree bound ordered set ( l -CDBOS), by which the scale of the working graph can be iteratively reduced. Based on these techniques, we develop an efficient method called HotPGC for solving PCP. The proposed algorithm is evaluated on benchmark graphs, and computational results show that HotPGC achieves highly competitive performance, compared with the state-of-the-art algorithms. The influence of the proposed reduction rule on the efficiency of HotPGC is also analyzed.

Model checking has established as an effective method for automatic system analysis and verification.It is making its way into many domains and methodologies.However, the state space may be extremely large for many practical systems, and this is a major limitation for state-space search algorithms in model checking.We have proposed a novel computing model called probe machine in 2016, which is a fully parallel computing model.In comparison to the Turing machine, it can solve the graph search problems efficiently, which can overcome the existing model checking limitations.In this paper, we propose a novel approach to perform Computation Tree Logic (CTL) model checking based on the mathematical model of probe machine, which can verify all CTL properties.It can greatly reduce the verification time for systems with large state space.We develop a model checker called CTL2PROBE based on our approach and the experimental results show that our approach is better than NuSMV.

In recent years, machine learning has demonstrated impressive performance in many real-world tasks, especially in computer vision and natural language processing.However, to apply them in safety-critical systems one needs formal guarantees on the neural network outputs.The Reluplex tool is proposed to verify the safety of deep neural networks (DNNs), and in case the DNN fails to give a correct output, can generate adversarial examples.Since the tool can only handle DNNs, it is necessary to extend the tool to process image data.Therefore, in this paper, we propose the Conv-Reluplex framework, which is designed to verify the convolutional layer and pooling layer in convolutional neural networks(CNNs), and generate adversarial examples when classification is misguided.We conduct several experiments on MNIST to evaluate our approaches.The results show that the original CNN is improved using the adversarial examples generated by our tool, and the precision of classification can be increased significantly.

Model checking is a verification technique that explores all possible system states in a brute-force manner. However, the state space can be extremely large for many practical systems and the verification time grows exponentially with the size of systems. It is a major limitation for state-space search algorithms of model checking. This paper presents a novel approach to perform Linear Temporal Logic (LTL) and Computation Tree Logic (CTL) model checking by using the connective probe machine, which is a fully parallel computing model. Our state-space search algorithm is based on the semantics of CTL properties and we design transformation algorithms to transform the model of a system into the structure that can run on the existing probe machine. We propose another approach to find multiple accepting cycles in linear time, which greatly shortens the verification time of LTL model checking. Compared to the traditional model checker, our approach can find multiple counterexamples according to the given property, which can trace as many system defects as possible. Simultaneously, it can greatly reduce the verification time for systems with large state spaces. We develop a model checker called MC2PROBE based on our approach and prove the feasibility and efficiency of our checker by experiments.

In recent years, Deep Neural Networks (DNNs) have been experiencing rapid development and have been widely used in various fields. However, while DNNs have shown strong capabilities, their security problems have gradually been exposed. Therefore, the formal guarantee of neural network output is needed. Prior to the appearance of the Reluplex algorithm, the verification of DNNs was always a difficult problem. Reluplex algorithm is specially used to verify DNNs with ReLU activation function. This is an excellent and effective algorithm, but it cannot verify more activation functions. ReLU activation function will bring about "Dead Neuron" problem, and Leaky ReLU activation function can solve this problem, so it is necessary to verify DNNs based on Leaky ReLU activation function. Therefore, we propose the Leaky-Reluplex algorithm, which is based on the Reluplex algorithm. Leaky-Reluplex algorithm can verify DNNs based on Leaky ReLU activation function.

In this paper, we study the problem of extracting a homogeneous graph from a heterogeneous graph. The key challenges of the extraction problem are how to efficiently enumerate paths matched by the provided line pattern and aggregate values for each pair of vertices from the matched paths. To address above two challenges, we propose a parallel graph extraction framework (PGE), where we use vertex-centric model to enumerate paths and compute aggregate functions in parallel. The framework compiles the line pattern into a path concatenation plan and generates the final weighted edges in a divide-and-conquer manner. The new solution outperforms the state-of-the-art ones through the comprehensive experiments.

Graph representation learning aims at transforming graph data into meaningful low-dimensional vectors to facilitate the employment of machine learning and data mining algorithms designed for general data. Most current graph representation learning approaches are transductive, which means that they require all the nodes in the graph are known when learning graph representations and these approaches cannot naturally generalize to unseen nodes. In this paper, we present a Fast Inductive Graph Representation Learning framework (FI-GRL) to learn nodes' low-dimensional representations. Our approach can obtain accurate representations for seen nodes with provable theoretical guarantees and can easily generalize to unseen nodes. Empirically, when the amount of seen nodes are larger than that of unseen nodes, FI-GRL always achieves excellent results. Our algorithm is fast, simple to implement and theoretically guaranteed. Extensive experiments on real datasets demonstrate the superiority of our algorithm on both efficacy and efficiency over both macroscopic level (clustering) and microscopic level (structural hole detection) applications. The full version of this paper is available on arxiv.

Graph embedding has been proven to be efficient and effective in facilitating graph analysis. In this paper, we present a novel spectral framework called NOn-Backtracking Embedding (NOBE), which offers a new perspective that organizes graph data at a deep level by tracking the flow traversing on the edges with backtracking prohibited. Further, by analyzing the non-backtracking process, a technique called graph approximation is devised, which provides a channel to transform the spectral decomposition on an edge-to-edge matrix to that on a node-to-node matrix. Theoretical guarantees are provided by bounding the difference between the corresponding eigenvalues of the original graph and its graph approximation. Extensive experiments conducted on various real-world networks demonstrate the efficacy of our methods on both macroscopic and microscopic levels, including clustering and structural hole spanner detection.

Graphical password (GPW) is one of various passwords used in information communication. The QR code, which is widely used in the current world, is one of GPWs. Topsnut-GPWs are new-type GPWs made by topological structures (also, called graphs) and number theory, but the existing GPWs use pictures/images almost. We design new Topsnut-GPWs by means of a graph labelling, called odd-elegant labelling. The new Topsnut-GPWs will be constructed by Topsnut-GPWs having smaller vertex numbers; in other words, they are compound Topsnut-GPWs such that they are more robust to deciphering attacks. Furthermore, the new Topsnut-GPWs can induce some mathematical problems and conjectures.

Heterogeneous graph is a popular data model to represent the real-world relations with abundant semantics. To analyze heterogeneous graphs, an important step is extracting homogeneous graphs from the heterogeneous graphs, called homogeneous graph extraction. In an extracted homogeneous graph, the relation is defined by a line pattern on the heterogeneous graph and the new attribute values of the relation are calculated by user-defined aggregate functions. The key challenges of the extraction problem are how to efficiently enumerate paths matched by the line pattern and aggregate values for each pair of vertices from the matched paths. To address above two challenges, we propose a parallel graph extraction framework, where we use vertex-centric model to enumerate paths and compute aggregate functions in parallel. The framework compiles the line pattern into a path concatenation plan, which determines the order of concatenating paths and generates the final paths in a divide-and-conquer manner. We introduce a cost model to estimate the cost of a plan and discuss three plan selection strategies, among which the best plan can enumerate paths in O(log)(l) iterations, where l is the length of a pattern. Furthermore, to improve the performance of evaluating aggregate functions, we classify the aggregate functions into three categories, i.e., distributive aggregation, algebraic aggregation, and holistic aggregation. Since the distributive and algebraic aggregations can be computed from the partial paths, we speed up the aggregation by computing partial aggregate values during the path enumeration.

In this paper, we present a novel computing model, called probe machine (PM). Unlike the turing machine (TM), PM is a fully parallel computing model in the sense that it can simultaneously process multiple pairs of data, rather than sequentially process every pair of linearly adjacent data. We establish the mathematical model of PM as a nine-tuple consisting of data library, probe library, data controller, probe controller, probe operation, computing platform, detector, true solution storage, and residue collector. We analyze the computation capability of the PM model, and in particular, we show that TM is a special case of PM. We revisit two NP-complete problems, i.e., the graph coloring and Hamilton cycle problems, and devise two algorithms on basis of the established PM model, which can enumerate all solutions to each of these problems by only one probe operation. Furthermore, we show that PM can be implemented by leveraging the nano-DNA probe technologies. The computational power of an electronic computer based on TM is known far more than that of the human brain. A question naturally arises: will a future computer based on PM outperform the human brain in more ways beyond the computational power?

This paper presents a method for evaluations and measurements of a high frequency nanocrystalline core transformer for power converters. An experimental platform is set up to measure the B-H characteristics of the core and the performances of the transformer with a frequency range up to 100 kHz. Using the measured B-H characteristics, a 3D FEM model of the transformer is built to simulate the performances and calculate the equivalent circuit parameters of the transformer that will be verified by the experimental data. The results show that the B-H characteristics of the nanocrystalline core are non-linear with frequency but well linear before it starts to saturation at a magnetic field of 0.6~0.8 T depending on the frequency. The linear relative permeabilities of the core are as high as around 20000 at room temperature, and the iron losses are so low that the efficiencies of the transformer are kept over 99% in the frequency range of under 100 kHz and with a magnetic field within 0.66 T.

Community structure as a significant feature helps us understand networks in a mesoscopic view. Existing approaches for community detection haven't considered about the formation of communities, whereas community in real social networks is usually established around influential nodes. In this paper, we present an efficient and effective framework based on local influence to detect both overlapping and hierarchical communities. We try to illuminate two fundamental questions: 1)Whether local influence regarded as a new property can affect the formation of communities; 2)How to quantify node's local influence and utilize it to detect communities. To demonstrate the effectiveness of local influence in terms of evaluating node importance, nodes with high local influence are selected to perform the influence maximization experiments on real social networks. Experimental results show that our framework is effective and efficient for both community detection and influence maximization.

In this paper, a new genetic algorithm for solving multi-constrained optimization problems based on KS function is proposed. Firstly, utilizing the agglomeration features of KS function, all constraints of optimization problems are agglomerated to only one constraint. Then, we use genetic algorithm to solve the optimization problem after the compression of constraints. Finally, the simulation results on benchmark functions show the efficiency of our algorithm.