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.

Heart Failure (HF) stands as a principal public health issue worldwide, imposing a significant burden on healthcare systems. While existing prognostic methods have achieved certain milestones in predicting the early mortality risk of HF patients, they have not fully considered the dynamic interdependencies among physiological parameters. This paper introduces a novel Multi-scale Spatiotemporal Dynamic Graph Neural Network, MSTD-GNN, which enhances the prediction capability for early mortality in HF patients by dynamically extracting spatio-temporal information of physiological parameters from ICU patient Electronic Health Records (EHRs). Our model constructs dynamic graphs to model multivariate time series data, revealing the implicit dependencies between physiological parameters and capturing the inherent dynamics of the data. We conducted experiments using the MIMIC-III and MIMIC-IV datasets. The experimental results show that, compared to existing methods, MSTD-GNN demonstrates superior performance in predicting the early mortality risk of HF patients. On the MIMIC-III and MIMIC-IV datasets, the AUC scores of MSTD-GNN reached 83.93% and 81.74%, respectively. Furthermore, through dynamic graphs, our model unveils the dynamic relationships between physiological variables across different time scales.

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.