Graph Neural Networks (GNNs) have become the dominant paradigm for machine learning on relational data, yet they remain susceptible to overfitting and noise in graph structures. While data augmentation has proven effective for regularization across domains, existing graph methods operate at coarse levels, such as perturbing entire structures or mixing node features. These approaches are context-agnostic and do not target the core computational process of GNNs: message passing. We introduce MessageShift, a novel fine-grained data augmentation paradigm that operates directly on the messages, the atomic units of information, as they flow through the GNN. The core idea is to apply a contextual perturbation to each message by shifting it towards or away from the center of its local neighborhood. This provides a rich regularization effect, capable of both smoothing noisy messages and sharpening distinctive ones. Extensive experiments on a wide range of benchmark datasets demonstrate that MessageShift consistently outperforms strong baselines across multiple GNN backbones.

Entity alignment (EA) is to identify equivalent entities across different knowledge graphs (KGs), which can help fuse these KGs into a more comprehensive one. Previous EA methods mainly focus on aligning a pair of KGs, and to the best of our knowledge, no existing EA method considers aligning multiple (more than two) KGs. To fill this research gap, in this work, we study a novel problem of aligning multiple KGs and propose an effective framework named MultiEA to solve the problem. First, we embed the entities of all the candidate KGs into a common feature space by a shared KG encoder. Then, we explore three alignment strategies to minimize the distances among pre-aligned entities. In particular, we propose an innovative inference enhancement technique to improve the alignment performance by incorporating high-order similarities. Finally, to verify the effectiveness of MultiEA, we construct two new real-world benchmark datasets and conduct extensive experiments on them. The results show that our MultiEA can effectively and efficiently align multiple KGs in a single pass. We release the source codes of MultiEA at: https://github.com/kepsail/MultiEA.

The ''pre-train, prompt'' paradigm, designed to bridge the gap between pre-training tasks and downstream objectives, has been extended from the NLP domain to the graph domain and has achieved remarkable progress. Current mainstream graph prompt-tuning methods modify input or output features using learnable prompt vectors. However, existing approaches are confined to single-granularity (e.g., node-level or subgraph-level) during prompt generation, overlooking the inherently multi-scale structural information in graph data, which limits the diversity of prompt semantics. To address this issue, we pioneer the integration of multi-scale information into graph prompt and propose a Multi-Scale Graph Chain-of-Thought (MSGCOT) prompting framework. Specifically, we design a lightweight, low-rank coarsening network to efficiently capture multi-scale structural features as hierarchical basis vectors for prompt generation. Subsequently, mimicking human cognition from coarse-to-fine granularity, we dynamically integrate multi-scale information at each reasoning step, forming a progressive coarse-to-fine prompt chain. Extensive experiments on eight benchmark datasets demonstrate that MSGCOT outperforms the state-of-the-art single-granularity graph prompt-tuning method, particularly in few-shot scenarios, showcasing superior performance. The code is available at: https://github.com/zhengziyu77/MSGCOT.

Graph Convolutional Networks (GCNs) are powerful tools for learning representations in graph-structured data. However, their performance tends to degrade with increased model depth due to over-smoothing. Although previous studies attribute degradation to over-smoothing, this work identifies the mutually reinforcing effects of over-smoothing and gradient vanishing as the root cause. In this paper, we propose SkipNode, a plug-and-play module that mitigates degradation in deep GCNs. SkipNode introduces node-sampling in each convolutional layer to selectively skip convolutions, preventing over-smoothing by reducing the depth experienced by specific nodes and facilitating gradient backpropagation. We demonstrate both theoretically and experimentally that SkipNode effectively curtails over-smoothing and gradient vanishing, improving deep GCN performance across diverse tasks. Extensive evaluations show SkipNode's robustness and superior performance over state-of-the-art (SOTA) baselines, establishing it as a practical solution for training deep GCNs.

Knowledge graph (KG) alignment aims to integrate different KGs through the linkage of equivalent entities across them, enabling more comprehensive knowledge and facilitating information fusion. Existing methods, whether translation-based or GNN-based, typically solve this problem by projecting entities and relations into a low-dimensional embedding space, each demonstrating unique advantages in aligning a pair of KGs. However, few studies consider combining these approaches to model translation semantics of various orders. To fill this gap, we propose KG2HIN, a novel KG encoder, which innovatively views head entities, relations, and tail entities as three types of nodes, thereby transforming KGs into HINs (heterogeneous information networks). KG2HIN can adaptively learn the importance of various orders of translation semantics by seamlessly combining the HGNN aggregator operator with the translation operator in KG embedding methods. Building upon the KG2HIN encoder, we further develop a network to effectively and efficiently align multiple (more than two) KGs concurrently, a much more challenging task than the traditional pair-KG alignment task. Compared with the state-of-the-art baseline, KG2HIN significantly improves the M-Hits@1 (accuracy) score from 10.25% to 73.05% on the DBP4 dataset and from 41.19% to 97.81% on the DWY-3 dataset, while requiring significantly fewer model parameters and less training time.

Masked Graph Auto-Encoder, a powerful graph self-supervised training paradigm, has recently shown superior performance in graph representation learning. Existing works typically rely on node contextual information to recover the masked information. However, they fail to generalize well to heterophilic graphs where connected nodes may be not similar, because they focus only on capturing the neighborhood information and ignoring the discrepancy information between different nodes, resulting in indistinguishable node representations. In this paper, to address this issue, we propose a Discrepancy-Aware Graph Mask Auto-Encoder (DGMAE). It obtains more distinguishable node representations by reconstructing the discrepancy information of neighboring nodes during the masking process. We conduct extensive experiments on 17 widely-used benchmark datasets. The results show that our DGMAE can effectively preserve the discrepancies of nodes in low-dimensional space. Moreover, DGMAE significantly outperforms state-of-the-art graph self-supervised learning methods on three graph analytic including tasks node classification, node clustering, and graph classification, demonstrating its remarkable superiority. The code of DGMAE is available at https://github.com/zhengziyu77/DGMAE.

Real-world networks usually have a property of node heterophily, that is, the connected nodes usually have different features or different labels. This heterophily issue has been extensively studied in homogeneous graphs but remains under-explored in heterogeneous graphs, where there are multiple types of nodes and edges. Capturing node heterophily in heterogeneous graphs is very challenging since both node/edge heterogeneity and node heterophily should be carefully taken into consideration. Existing methods typically convert heterogeneous graphs into homogeneous ones to learn node heterophily, which will inevitably lose the potential heterophily conveyed by heterogeneous relations. To bridge this gap, we propose Relation-Aware Separation of Homophily and Heterophily (RASH), a novel contrastive learning framework that explicitly models high-order semantics of heterogeneous interactions and adaptively separates homophilic and heterophilic patterns. Particularly, RASH introduces dual heterogeneous hypergraphs to encode multi-relational bipartite subgraphs and dynamically constructs homophilic graphs and heterophilic graphs based on relation importance. A multi-relation contrastive loss is designed to align heterogeneous and homophilic/heterophilic views by maximizing mutual information. In this way, RASH simultaneously resolves the challenges of heterogeneity and heterophily in heterogeneous graphs. Extensive experiments on benchmark datasets demonstrate the effectiveness of RASH across various downstream tasks. The code is available at: https://github.com/zhengziyu77/RASH.

Graph Neural Networks (GNNs) have revolutionized graph-based machine learning, but their heavy computational demands pose challenges for latency-sensitive edge devices in practical industrial applications. In response, a new wave of methods, collectively known as GNN-to-MLP Knowledge Distillation, has emerged. They aim to transfer GNN-learned knowledge to a more efficient MLP student, which offers faster, resource-efficient inference while maintaining competitive performance compared to GNNs. However, these methods face significant challenges in situations with insufficient training data and incomplete test data, limiting their applicability in real-world applications. To address these challenges, we propose AdaGMLP, an AdaBoosting GNN-to-MLP Knowledge Distillation framework. It leverages an ensemble of diverse MLP students trained on different subsets of labeled nodes, addressing the issue of insufficient training data. Additionally, it incorporates a Node Alignment technique for robust predictions on test data with missing or incomplete features. Our experiments on seven benchmark datasets with different settings demonstrate that AdaGMLP outperforms existing G2M methods, making it suitable for a wide range of latency-sensitive real-world applications. We have submitted our code to the GitHub repository (https://github.com/WeigangLu/AdaGMLP-KDD24).

Graph Convolutional Networks (GCNs) suffer from performance degradation when models go deeper. However, earlier works only attributed the performance degeneration to over-smoothing. In this paper, we conduct theoretical and experimental analysis to explore the fundamental causes of performance degradation in deep GCNs: over-smoothing and gradient vanishing have a mutually reinforcing effect that causes the performance to deteriorate more quickly in deep GCNs. On the other hand, existing anti-over-smoothing methods all perform full convolutions up to the model depth. They could not well resist the exponential convergence of over-smoothing due to model depth increasing. In this work, we propose a simple yet effective plug-and-play module,SkipNode, to overcome the performance degradation of deep GCNs. It samples graph nodes in each convolutional layer to skip the convolution operation. In this way, both over-smoothing and gradient vanishing can be effectively suppressed since (1) not all nodes'features propagate through full layers and, (2) the gradient can be directly passed back through “skipped” nodes. We provide both theoretical analysis and empirical evaluation to demonstrate the efficacy ofSkipNodeand its superiority over SOTA baselines.

There has been a surge of researchers' interest in building predictive models over graphs. However, the overwhelming complexity of graph space often makes it challenging to extract interpretable and discriminative structural features for graph classification. In this work, we propose a new graph neural network model called Substructure Assembling Network (SAN) to learn graph representations for classification. The key innovation is a unified Substructure Assembling Unit (SAU), which is a variant of Recurrent Neural Network (RNN) designed to hierarchically assemble useful pieces of graph components so as to fabricate discriminative substructures. A key challenge is that SAUs need to process the neighbors of a node sequentially while no natural order is defined therein. SAN tries to make the model insensitive to neighborhood orders by randomly shuffling neighborhood sequences in training. However, this could suffer high variance, especially when the neighborhood size is large. Hence, we further propose to equip SAN with a novel module named Soft Sequence with Context Attention (SSCA). SAN-SSCA employs the proposed context attention technique to learn the best "soft" permutation of the neighbors w.r.t. classification. It helps the model achieve higher accuracy as well as lower variance. Experiments confirm the effectiveness of SAN-SSCA.