Higher-order Graph Neural Networks (HOGNNs) based on the 2-FWL test achieve superior expressivity by modeling 2-node and 3-node interactions, but incur cubic computational cost. Existing efficiency methods typically reduce this burden at the expense of expressivity. We propose Co-Sparsify, a connectivity-aware sparsification framework that eliminates provably redundant computations while preserving full 2-FWL expressive power. Our key insight is that 3-node interactions are expressively necessary only within biconnected components, namely, maximal subgraphs where every node pair lies on a cycle. Outside these components, structural relationships are fully captured via 2-node message passing and graph readouts, rendering higher-order modeling unnecessary. Co-Sparsify restricts 2-node message passing to connected components and 3-node interactions to biconnected components, eliminating redundant computation without approximation or sampling. We prove that Co-Sparsified GNNs match the expressivity of the 2-FWL test. Empirically, when applied to PPGN, Co-Sparsify matches or exceeds accuracy on synthetic substructure counting tasks and achieves state-of-the-art performance on real-world benchmarks (ZINC, QM9 and TUD). This study demonstrates that high expressivity and scalability are not mutually exclusive: principled, topology-guided sparsification enables powerful, efficient GNNs with theoretical guarantees.

Graph Neural Networks (GNNs) are widely used in graph data mining tasks. Traditional GNNs follow a message passing scheme that can effectively utilize local and structural information. However, the phenomena of over-smoothing and over-squashing limit the receptive field in message passing processes. Graph Transformers were introduced to address these issues, achieving a global receptive field but suffering from the noise of irrelevant nodes and loss of structural information. Therefore, drawing inspiration from fine-grained token-based representation learning in Natural Language Processing (NLP), we propose the Structure-aware Multi-token Graph Transformer (Tokenphormer), which generates multiple tokens to effectively capture local and structural information and explore global information at different levels of granularity. Specifically, we first introduce the walk-token generated by mixed walks consisting of four walk types to explore the graph and capture structure and contextual information flexibly. To ensure local and global information coverage, we also introduce the SGPM-token (obtained through the Self-supervised Graph Pre-train Model, SGPM) and the hop-token, extending the length and density limit of the walk-token, respectively. Finally, these expressive tokens are fed into the Transformer model to learn node representations collaboratively. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.

To enhance the capability of Graph Neural Networks (GNNs) in judging graph isomorphism and graph classification tasks, this paper introduces a metric space-based graph isomorphism judgment method called the k-MSI test, which offers more topological information than the k-WL test and demonstrates superior graph isomorphism judgment capabilities compared to the k-WL test at the same complexity level. On the open test isomorphic dataset BREC, our k-MSI test accuracy rate is more than 11% ahead of the other methods. Furthermore, based on the k-MSI test, we propose a feature enhancement method Node Metric Indicator (NMI) that supplies additional topological information of graphs for GNNs and presents a novel GNN named Metric Space Indicators Graph Neural Network (MSIGNN). Experimental results on a publicly available benchmark graph classification task indicate that the NMI feature-based MSIGNN outperforms state-of-the-art methods on the BREC graph isomorphism test dataset and achieves satisfactory performance on real-world datasets.

Despite the theoretical expressiveness of 2-dimensional Folklore Weisfeiler-Lehman (2-FWL) Graph Neural Networks (GNNs), a significant gap persists between their theoretical capacity and their practical performance. To bridge this gap, we identify a critical limitation in current Graph Structural Encodings (GSEs): insufficient sensitivity to subtle structural variations, particularly in local connectivity, spectral features, and distance-based patterns. We show that widely used GSEs-such as Relative Random Walk Probability (RRWP) and monomial-based methods-lack full sensitivity across spectral frequency bands and long-range distances. Moreover, they fail to capture fine-grained local connectivity, which is essential for identifying cut nodes, biconnected components, and other higher-order structures that 2-FWL GNNs theoretically encode. To address these limitations, we propose CSDGSE (Connectivity, Spectral, and Distance Graph Structural Encoding), a novel GSE framework that jointly enhances sensitivity to: (1) exact local connectivity via hierarchical graph decomposition(2) full-frequency spectral features using expressive graph polynomials (e.g., Chebyshev), and (3) full-range distance interactions. A key innovation is our scalable divide-and-conquer algorithm for computing exact local connectivity across all node pairs, enabling efficient integration into modern GSEs. Extensive experiments show that CSDGSE outperforms existing GSEs in capturing complex structural patterns, achieving state-of-the-art results on molecular property prediction benchmarks like ZINC. Our work sets a new standard for GSEs by aligning theoretical expressiveness with practical effectiveness through enhanced structural sensitivity.

Learning-based point cloud completion tasks have shown potential in various critical tasks, such as object detection, assignment, and registration. However, accurately and efficiently quantifying the shape error between the predicted point clouds generated by networks and the ground truth remains challenging. While EMD-based loss functions excel in shape detail and perceived density distribution, their approach can only yield results with significant discrepancies from the actual EMD within a tolerable training time. To address these challenges, we first propose the initial price based on the auction algorithm, reducing the number of iterations required for the algorithm while ensuring the correctness of the assignment results. We then introduce an algorithm to compute the initial price through a successive shortest path and the Euclidean information between its nodes. Finally, we adopt a series of optimization strategies to speed up the algorithm and offer an EMD approximation scheme for point cloud problems that balances time loss and computational accuracy based on point cloud data characteristics. Our experimental results confirm that our algorithm achieves the smallest gap with the real EMD within an acceptable time range and yields the best results in end-to-end training.

Existing message passing-based and transformer-based graph neural networks (GNNs) cannot satisfy requirements for learning representative graph embeddings due to restricted receptive fields, redundant message passing, and reliance on fixed aggregations. These methods face scalability and expressivity limitations from intractable exponential growth or quadratic complexity, restricting interaction ranges and information coverage across large graphs. Motivated by the analysis of long-range graph structures, we introduce a novel Graph Neural Network called Hub-Fringe Graph Neural Network (HFGNN). Our Hub-Fringe structure, drawing inspiration from the graph indexing technique known as Hub Labeling, offers a straightforward and effective approach for learning scalable graph representations while ensuring comprehensive coverage of information. HFGNN leverages this structure to enable selective propagation of relevant embeddings through a carefully designed message function. Theoretical analysis is presented to show the expressivity and scalability of the proposed method. Empirically, HFGNN exceeds standard GNNs on tasks including classification and regression, especially for large, long-range graphs where scalability and coverage matter. Ablation studies further confirm the benefits of our hub-fringe based graph neural network, including improved expressivity and scalability. The source codes is available at https://github.com/nick12340/HFGNN.

Graph Neural Networks (GNNs) resemble the Weisfeiler-Lehman (1-WL) test, which iteratively update the representation of each node by aggregating information from WL-tree. However, despite the computational superiority of the iterative aggregation scheme, it introduces redundant message flows to encode nodes. We found that the redundancy in message passing prevented conventional GNNs from propagating the information of long-length paths and learning graph similarities. In order to address this issue, we proposed Redundancy-Free Graph Neural Network (RFGNN), in which the information of each path (of limited length) in the original graph is propagated along a single message flow. Our rigorous theoretical analysis demonstrates the following advantages of RFGNN: (1) RFGNN is strictly more powerful than 1-WL; (2) RFGNN efficiently propagate structural information in original graphs, avoiding the over-squashing issue; and (3) RFGNN could capture subgraphs at multiple levels of granularity, and are more likely to encode graphs with closer graph edit distances into more similar representations. The experimental evaluation of graph-level prediction benchmarks confirmed our theoretical assertions, and the performance of the RFGNN can achieve the best results in most datasets.

From the viewpoint of mission's completion, the occurrence of any failure or safety accident is decided by multiple complex and dynamic factors. The safety analysis methods in present only focus on failure modes in system itself, rather than the whole mission system dynamical process, the Ground Proximity Warning System (GPWS)'s mission dynamic safety modeling was presented based on SoTeRiA in this paper. Combining with the technical system risk model, maintenance process model and organizing risk model, the model of dynamic safety analysis was established. Case study in the end shows the effectiveness of the proposed method.

BACKGROUND: The analysis of mass spectra suggests that the existence of derivative peaks is strongly dependent on the intensity of the primary peaks. Peak selection from tandem mass spectrum is used to filter out noise and contaminant peaks. It is widely accepted that a valid primary peak tends to have high intensity and is accompanied by derivative peaks, including isotopic peaks, neutral loss peaks, and complementary peaks. Existing models for peak selection ignore the dependence between the existence of the derivative peaks and the intensity of the primary peaks. Simple models for peak selection assume that these two attributes are independent; however, this assumption is contrary to real data and prone to error. RESULTS: In this paper, we present a statistical model to quantitatively measure the dependence of the derivative peak's existence on the primary peak's intensity. Here, we propose a statistical model, named ProbPS, to capture the dependence in a quantitative manner and describe a statistical model for peak selection. Our results show that the quantitative understanding can successfully guide the peak selection process. By comparing ProbPS with AuDeNS we demonstrate the advantages of our method in both filtering out noise peaks and in improving de novo identification. In addition, we present a tag identification approach based on our peak selection method. Our results, using a test data set, suggest that our tag identification method (876 correct tags in 1000 spectra) outperforms PepNovoTag (790 correct tags in 1000 spectra). CONCLUSIONS: We have shown that ProbPS improves the accuracy of peak selection which further enhances the performance of de novo sequencing and tag identification. Thus, our model saves valuable computation time and improving the accuracy of the results.