By mimicking the brain's efficient spiking encoding paradigm, spiking graph neural networks exhibit significant potential for efficient graph data analysis. Due to the inherent expressive limitations of binary spiking signals adopted in spiking encoding, existing models typically enhance their expression by integrating numerous real-valued multiplication-additions or high-latency encoding. However, such integrations compromise the core efficiency superiority of spiking models, limiting their scalability in real-world applications. To simultaneously reconcile considerable expression and efficiency, we propose E2SGNN, a novel network comprising a dual-scale modulated spiking backbone and a latency-dynamic optimization module. The former backbone integrates global and local real-valued graph modulations into spiking graph convolution, enabling discriminative dual-scale neighbor embedding in the encoding process. It both breaks through binary spiking signals' expressive limitations and improves the content expressiveness of spiking graph representations, while retaining low-latency and addition-only efficient advantages. Moreover, to further reduce the latency redundancy for higher efficiency, the latter module adaptively customizes the latency for each graph data based on data complexity. In this way, our network can finally generate graph representations expressively and efficiently. Experiments on various datasets demonstrate the superiority of our network in expression and efficiency.
论文检索
输入标题、作者或关键词，从 100,903 篇学术成果中精准定位
Dynamic graph anomaly detection (DGAD) is essential for iden- tifying anomalies in evolving graphs across domains such as fi- nance and social networks. Recently, generalist graph anomaly detection (GAD) models have shown promising results. They are pretrained on multiple source datasets and generalize across do- mains. While effective on static graphs, they struggle to capture evolving anomalies in dynamic graphs. Moreover, the continuous emergence of new domains and the lack of labeled data further challenge generalist DGAD. Effective cross-domain DGAD requires both domain-specific and domain-agnostic anomalous patterns. Importantly, these patterns evolve temporally within and across domains. Building on these insights, we propose a DGAD model with Dynamic Prototypes (DP) to capture evolving domain-specific and domain-agnostic patterns. Firstly, DP-DGAD extracts dynamic prototypes, i.e., evolving representations of normal and anomalous patterns, from temporal ego-graphs and stores them in a memory buffer. The buffer is selectively updated to retain general, domain- agnostic patterns while incorporating new domain-specific ones. Then, an anomaly scorer compares incoming data with dynamic prototypes to flag both general and domain-specific anomalies. Fi- nally, DP-DGAD employs confidence detection guided memory buffer updating for effective adaptation to target domain. Extensive experiments demonstrate state-of-the-art performance across ten real-world datasets from different domains.
Clustering is a fundamental task in graph data mining, including both node-level and graph-level clustering. While the former has been extensively explored to capture local structures and features, the latter has gained attention for its ability to capture global relationships and high-level abstractions. However, existing methods often address these two tasks in isolation, which not only wastes computational resources but also fails to fully leverage the knowledge from both levels to improve each other, hindering consistent performance improvement. To this end, we propose a novel Unified Graph Clustering Network called UGCN, which employs both local and global graph information to address node- and graph-level clustering collaboratively. In detail, we design a dual-branch projector that performs joint learning at both node and graph levels. The first branch extracts node-level features and projects them into distinct cluster layers, where the derived prototypes are used to refine graph attributes and highlight clustering-friendly substructures. In parallel, the second branch captures subgraph embeddings and aggregates them into discriminative graph-level representations. we align the two branches through joint contrastive objectives to establish a bidirectional interaction: refined prototypes guide subgraph and graph-level clustering, while graph-level pseudo-labels provide feedback to enhance node-level clustering. Extensive experimental results across seven datasets demonstrate that our method significantly outperforms existing state-of-the-art approaches.
How can we accurately classify graphs using only positive and unlabeled instances? This setting commonly arises in real-world tasks. For example, in drug side effect prediction, each drug is represented as a graph based on its chemical structure, and only those observed to cause adverse effects are labeled as positive. The remaining drugs are left unlabeled—not because they are confirmed safe, but because such side effects have not yet been discovered or reported. A challenge is that positive and negative graphs often share similar substructures, making it difficult for models to capture the subtle structural differences that distinguish true positives among unlabeled ones. This difficulty is further exacerbated by the absence of explicit negative labels, which leaves the model without clear guidance on how to separate informative from non-informative patterns. We propose Delta-PU, an accurate method for PU graph classification. Delta-PU performs dual reweighting: hop-level reweighting to emphasize informative substructures during pooling, and graph-level reweighting to suppress ambiguous unlabeled graphs. This dual mechanism allows the model to progressively focus on discriminative patterns while reducing the uncertainty introduced by unlabeled instances. Extensive experiments demonstrate that Delta-PU achieves the state-of-the-art performance in PU graph classification.
We consider a novel vertex cover problem on temporal graphs, where the edges in the graph may change over time, and a vertex selected into the solution has a lifespan d. Specifically, a vertex selected at time t can cover all incident edges in graphs from time slot t to t+d-1. This model effectively captures the scenario of monitoring communication links via secure nodes (monitors) with limited lifespan in a dynamic network. We provide a systematic study of this problem from both theoretical and practical perspectives. We analyze its computational complexity, develop approximation and online algorithms with tight ratios, and present a parameterized algorithm and a tight quadratic kernel under fixed d. Experimental results on random and real-world temporal networks demonstrate the effectiveness of our algorithms. We believe that our systematic study not only reveals the nature of the problem itself, but also paves the way for investigating the ''sustained'' version of other problems on temporal graphs.
A significant challenge in developing graph foundational models is to achieve universality and generalizability across general graphs, beyond text-attribute graphs. Unfortunately, most graph neural networks are designed for specific applications in particular fields and are difficult to generalize across different graphs. The most critical problem is the lack of Transfer Invariant Metadata (TIM) for graphs, akin to pixels for images and vocabularies for text, which prevents the development of graph foundational models. TIM is particularly problematic, albeit critical, on graph nodes with semantically variable features, making it difficult to transfer knowledge across graphs. Here, we analyze TIM and propose a theoretical approach to mining TIM in node features. It extracts semantically consistent information across domains and unifies data space with relatively low information loss. We then introduce a Transfer-Invariant Graph (TIG) foundational model to transform features of different dimensions into a unified structural representation. This transformation can effectively learn and extract TIM and intrinsic graph knowledge by self-supervised learning. We conducted extensive experiments, and the results showed that TIG even outperformed some models trained on data from targeted domains. In one-shot cross-domain scenarios, TIG achieved high accuracy with less training data and without any prompt tuning.
Graph property detection aims to determine whether a graph exhibits certain structural properties, such as being Hamiltonian. Recently, learning-based approaches have shown great promise by leveraging data-driven models to detect graph properties efficiently. In particular, vision-based methods offer a visually intuitive solution by processing the visualizations of graphs. However, existing vision-based methods rely on fixed visual graph layouts, and therefore, the expressiveness of their pipeline is restricted. To overcome this limitation, we propose VSAL, a vision-based framework that incorporates an adaptive layout generator capable of dynamically producing informative graph visualizations tailored to individual instances, thereby improving graph property detection. Extensive experiments demonstrate that VSAL outperforms state-of-the-art vision-based methods on various tasks such as Hamiltonian cycle, planarity, claw-freeness, and tree detection.
Linear attention mechanisms have emerged as efficient alternatives to full self-attention in Graph Transformers, offering linear time complexity. However, existing linear attention models often suffer from a significant drop in expressiveness due to low-rank projection structures and overly uniform attention distributions. We theoretically prove that these properties reduce the class separability of node representations, limiting the model's classification ability. To address this, we propose a novel hybrid framework that enhances both the rank and focus of attention. Specifically, we enhance linear attention by attaching a gated local graph network branch to the value matrix, thereby increasing the rank of the resulting attention map. Furthermore, to alleviate the excessive smoothing effect inherent in linear attention, we introduce a learnable log-power function into the attention scores to reduce entropy and sharpen focus. We theoretically show that this function decreases entropy in the attention distribution, enhancing the separability of learned embeddings. Extensive experiments on both homophilic and heterophilic graph benchmarks demonstrate that our method achieves competitive performance while preserving the scalability of linear attention.
Subgraph Anomaly Detection (SAD) is crucial for identifying groups that deviate from the regular pattern within graphs, which benefits different domains such as financial fraud and network security. However, current studies rely on traditional node detection methods and fixed sampling strategies of subgraph structures, which makes it difficult to learn the pattern collaboration behavior of subgraphs. To address this limitation, this paper proposes a novel unsupervised framework named PC-SAD. The PC-SAD framework first employs an improved Graph AutoEncoder to identify core anomaly nodes by capturing multi-scale neighborhood information. Starting from these core anomaly nodes, we sample candidate subgraphs with path, tree, and cyclic structures, and enhance them according to the characteristics of the subgraph structures. Subsequently, candidate subgraphs are fed into the proposed Pattern Collaboration-based Graph Contrastive Learning method to generate collaborative pattern embeddings, thereby distinguishing anomaly subgraphs. The experimental results show that PC-SAD outperforms the state-of-the-art baseline methods on four benchmark datasets, which proves that PC-SAD is an effective solution to detect anomaly subgraphs.
The Group Steiner Tree Problem (GSTP) has been popularly used to formulate graph-based tasks on the Web where the number of groups (i.e., g), e.g., representing the number of keywords in knowledge graph search, is assumed to be small. This assumption never holds in emerging tasks such as the summarization of knowledge graphs, where g represents the number of distinct entity description patterns that increases with graph order (i.e., n) and reaches 105 in practice. Existing algorithms become impractical, since they are optimized for large n but not for large g. In this paper, we devise novel approximation algorithms for GSTP that exhibit scalability in relation to both n and g. When g is large, our algorithms outperform existing algorithms that have a comparable approximation ratio by orders of magnitude in running time, showing their unique ability to practically support such challenging Web applications.
Text-Attributed Graph (TAG) is an important type of graph structured data, where each node has a text description. TAG models usually train a Graph Neural Network (GNN) and language model jointly, which leads to high space and time consumption, especially on large datasets. To mitigate this, we propose TAGSAM, a condensation method that compresses TAGs while preserving training accuracy. TAGSAM comes with two key designs, i.e., subgraph text Selection and Attribute similarity Matching, which compress the text description and graph topology of TAG, respectively. For the texts, subgraph text selection selects and merges representative text chunks from multiple related text descriptions by maximizing mutual information. For the graph topology, popular condensation methods based on Matching Training Trajectories (MTT) suffer from high variance, which hinders accuracy. Our attribute similarity matching mitigates this issue by aligning stable similarity matrices. We evaluate TAGSAM against six state-of-the-art baselines, where it showcases superior performance. For the same compressed size, TAGSAM improves upon the best-performing baseline by an average of 4.9% in accuracy. Furthermore, it maintains competitive training accuracy even when the TAG is condensed to just 1% size. Our code is available at https://github.com/SundayVHan/TAGSAM
Fraud detection on streaming transaction graphs (STGs) faces challenges on the catastrophic forgetting of previously learned fraud patterns when adapting to evolving patterns. Although some Graph Continual Learning (GCL) approaches mitigate this issue by storing and revisiting historical samples, practical storage constraints prevent them from fully preserving previous patterns. In this work, we propose STG-DGR, a streaming GNN model with diffusion-based generative replay that generates synthetic samples to retain previously learned patterns without storing real samples. The generation of replay samples for STGs faces two key challenges: (1) Heterogeneity challenge of generating STG samples with discrete adjacency table, user features, transaction features, and transaction timestamps. (2) Dependency challenge of capturing bottom-up dependencies across layers in STG samples. To address these challenges, STG-DGR integrates two novel components: (1) a Computational Subgraph Processor (CSP) that transforms heterogeneous STG samples into well-organized hierarchical subgraphs, and (2) a Diffusion-based Subgraph Generator (DSG) that captures the bottom-up dependencies using a novel Transformer-based Hierarchical Denoising Network (THDN), and generates synthetic replay samples that preserve these dependencies. Extensive experiments on four streaming fraud detection datasets demonstrate STG-DGR's superiority in reducing forgetting and improving accuracy over nineteen state-of-the-art baselines.
Dynamic graph neural networks (DyGNNs) currently struggle with handling distribution shifts that naturally arise when training and test data follow similar but non-identical distributions. As the generation of dynamic graphs is strongly influenced by latent environments, it is critical to investigate their impacts on the generalization behavior of DyGNNs. We therefore establish a connection between the temporal message-passing scheme employed by DyGNNs and their generalization performance under distribution shifts. Our analysis reveals that environment-specific factors misguide the learning process and lead to unsatisfactory out-of-distribution (OOD) generalization. Based on this insight, we propose MoVE, a Mixture of Variational Experts network to mitigate complex distribution shifts in dynamic graphs. MoVE adopts a hierarchical variational architecture that extrapolates latent representations into a mixture of distribution shifts as pseudo-environments. Additionally, we incorporate a Mixture-of-Experts (MoE) framework with a novel training objective that aligns the outputs of different experts to produce invariant representations. Extensive experiments on various dynamic graphs, including both real-world and synthetic datasets, demonstrate that our model significantly outperforms state-of-the-art techniques.
Large Language Models (LLMs) have shown significant potential in handling text-attributed graphs (TAGs). Nevertheless, existing LLM-enhanced approaches for TAG learning mainly utilize LLMs as text augmenters, which not only incur substantial computational overhead but may also introduce noise. In contrast, their capacity as embedding generators remains underutilized. Furthermore, most current methods are designed for specific TAG instances and lack cross-domain transferability. To overcome these limitations, we propose UTAG, a novel framework that leverages LLMs as unified embedding generators. First, we design a dual-view contrastive fine-tuning approach for cross-domain pretraining. The in-domain view promotes local consistency via adaptive positive sample selection, while the cross-domain view establishes alignment through subspace clustering-based cross-domain prototype aggregation. By jointly pretraining on multiple TAG datasets from diverse domains, we obtain a unified LLM encoder that produces transferable representations. Subsequently, we introduce a graph-specific adaptation training technique that implements two-stage dimensionality reduction with carefully designed semantic and Laplacian reconstruction constraints. This allows effective incorporation of structural signals while preserving semantic information to the greatest extent. Additionally, we employ cross-space alignment to further enhance consistency. Extensive experiments demonstrate that UTAG substantially surpasses existing LLM-enhanced methods, achieving an average improvement of 5.9% on cross-domain transfer tasks, which verifies its effectiveness and superiority.
Open-set node classification (OSNC) allows unlabeled test data to contain novel classes previously unseen in the labeled data. The goal is to classify in-distribution (ID) nodes into corresponding known classes and reject out-of-distribution (OOD) nodes as unknown class. Despite recent notable progress in OSNC, two challenges remain less explored, i.e., how to enhance generalization to OOD nodes, and promote intra-class compactness and inter-class separability. To tackle such challenges, we propose a novel Negative Mixup with Cross-Layer Graph Contrastive Learning (negMIX) model. Firstly, we devise a novel negative Mixup method purposefully crafted for the open-set scenario with theoretical justification, to enhance the model's generalization to OOD nodes and yield clearer ID/OOD boundary. Additionally, a unique cross-layer graph contrastive learning module is developed to maximize the prototypical mutual information between the same class nodes across different topological distance neighborhoods, thereby facilitating intra-class compactness and inter-class separability. Extensive experiments validate significant outperformance of the proposed negMIX over state-of-the-art methods in various scenarios and settings.
Model transferability estimation is a task-adaptive pre-trained model selection problem, aiming to determine the optimal model for target dataset from a model hub pre-trained on source dataset without fine-tuning. Although existing model transferability evaluation methods have made some progress, they mainly focus on image or text data in CV and NLP. In contrast, the graph structural data with GNNs models is still underexplored, due to the complexity of the graph structure and the limitations of the generalization ability of GNN models under distribution shift. To fill this blank, we first propose a Graph Neural Network Model Transferability Estimation method via decomposition-augmented discriminant analysis, named GNNMTE, to evaluate the transferability of GNN models on target graph dataset without fine-tuning. It only calculates the GNNMTE score to determine whether it can be effectively transferred to target graph dataset and better select the optimal model for the target graph dataset. Specifically, our proposed \method contains three core components: (1) Dual-block SVD fusion for obtaining the corresponding principal component information; (2) Adaptive weighting by singular value ratio for guiding the extraction of important principal component information on graph data; (3) Graph discriminant analysis for finding the optimal projection direction that separates the classes of graph data. Extensive experimental results on cross-domain graph datasets achieve excellent results, demonstrating powerful superiority.
Dynamic graph representation learning has become essential for analyzing evolving networks in domains such as social network analysis, recommendation systems, and traffic analysis. However, existing continuous-time methods face three key challenges: (1) some methods depend solely on node-specific memory without effectively incorporating information from neighboring nodes, resulting in embedding staleness; (2) most fail to explicitly capture correlations between node neighborhoods, limiting contextual awareness; and (3) many fail to fully capture the structural dynamics of evolving graphs, especially in absence of rich link attributes. To address these limitations, we introduce TAWRMAC—a novel framework that integrates Temporal Anonymous Walks with Restart, Memory Augmentation, and Neighbor Co-occurrence embedding. TAWRMAC enhances embedding stability through a memory-augmented GNN with fixed-time encoding and improves contextual representation by explicitly capturing neighbor correlations. Additionally, its Temporal Anonymous Walks with Restart mechanism distinguishes between nodes exhibiting repetitive interactions and those forming new connections beyond their immediate neighborhood. This approach captures structural dynamics better and supports strong inductive learning. Extensive experiments on multiple benchmark datasets demonstrate that TAWRMAC consistently outperforms state-of-the-art methods in dynamic link prediction and node classification under both transductive and inductive settings across three different negative sampling strategies. By providing stable, generalizable, and context-aware embeddings, TAWRMAC advances the state of the art in continuous-time dynamic graph learning.
Graph-structured data effectively captures complex relationships in diverse domains such as social networks, financial transactions, citation networks, and recommendation systems. Graph Neural Networks (GNNs) excel in learning intricate topological patterns, yielding strong performance on tasks like node classification and link prediction. However, real-world graphs often scale to millions of nodes and billions of directed edges, posing significant computational and storage challenges for GNN training that frequently exceed available hardware limits. Although graph sampling and distillation techniques alleviate these issues by subsampling or creating surrogate graphs, they primarily handle undirected graphs, neglecting directional semantics that are crucial for applications like fraud detection and causal analysis. To address these limitations, we introduce the Directed Graph Distillation (Dir-GD) framework, which combines distributed learning with community detection to divide large directed graphs into independent subgraphs for distributed directed GNN training. This process culminates in parameter aggregation to produce a compact global synthetic graph that preserves essential topology and directionality. Extensive experiments on large-scale datasets, such as the million-node soc-pokec-relationships, demonstrate over 91% accuracy at 0.001 distillation ratios, accompanied by substantial memory and runtime savings. This work pioneers directed graph distillation as a key paradigm for analyzing ultra-large directed graphs, offering a scalable solution that maintains high fidelity in compressed representations.
State-of-the-art algorithms for randomizing (or ''null-modeling'') graphs, hypergraphs, binary matrices, and market basket datasets are based on the Curveball trade, a procedure that takes two n-dimensional binary vectors (e.g., 1-hop neighborhood vectors, hyperedges, columns, transactions), and transforms them into two new vectors with the same L1 norm, bitwise-XOR, and bitwise-AND as the original ones. We present HomeRun, an algorithm to perform Curveball trades in an almost-streaming fashion. Previous approaches make multiple passes over the input vectors, and perform other operations with O(n) computational cost\@. HomeRun instead performs a single linear scan over the data, and costs less than two passes. We achieve this speedup by framing a Curveball trade as a sampling procedure, and by using reservoir sampling and strict upper bounds to avoid having to compute the population and sample sizes. Our experimental evaluation on real and artificial datasets shows that HomeRun achieves a 2x speedup over existing algorithms.
Reinforcement learning-based recommendation systems (RLRS) are increasingly favored for their ability to leverage online interactive feedback, enabling adaptive and personalized decision-making. In this setting, user feedback serves as both a behavioral signal and an optimization target, making it essential for policy learning. However, collecting such feedback, e.g., clicks, ratings, and engagement traces, raises serious privacy concerns, posing critical challenges for value estimation, online adaptation, and privacy protection. In this paper, we propose FeedGuard, a critic-guided reinforcement learning framework with privacy-preserving feedback. FeedGuard enhances trajectory modeling via critic guidance, enables joint online fine-tuning with effective exploration–exploitation tradeoffs, and enforces end-to-end privacy protection across the feedback lifecycle via split federated learning and differential privacy. We further provide a formal analysis of its differential privacy guarantees. Extensive experiments on four public recommendation datasets and the VirtualTB platform show that FeedGuard performs well in both offline and online settings, while maintaining rigorous privacy guarantees with minimal degradation.