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.
论文检索
输入标题、作者或关键词，从 954 篇学术成果中精准定位
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.
Signed Graph Neural Networks (SGNNs) have achieved outstanding performance in Link Sign Prediction (LSP), which involves predicting the existence and polarity of edges, by effectively modeling positive and negative interactions in signed graphs. However, their black-box nature raises transparency concerns, necessitating faithful explanations of model behavior to ensure trustworthiness and accountability. Existing eXplainable GNN (XGNN) methods, primarily designed for unsigned graphs, struggle to provide meaningful and human-understandable explanations for SGNN-based LSP, often generating disconnected subgraph explanations or neglecting the unique sign interactions. To address the gap, we propose SGExplainer, a novel method that leverages balanced paths, a concept rooted in signed graph theory, to provide clear and faithful explanations for LSP. SGExplainer employs a path-enforcing mask learning framework that ensures interpretable balanced path generation while maintaining explanation fidelity. Extensive experiments on real-world signed graphs demonstrate that SGExplainer consistently provides faithful and intuitive explanations for various SGNNs, outperforming state-of-the-art baselines in explanation quality, interpretability, and efficiency.
Graph Foundation Models (GFMs) have emerged as a frontier in graph learning, which are expected to deliver transferable representations across diverse tasks. However, GFMs remain constrained by in-memory bottlenecks: they attempt to encode knowledge into model parameters, which limits semantic capacity, introduces heavy lossy compression with conflicts, and entangles graph representation with the knowledge in ways that hinder efficient adaptation, undermining scalability and interpretability. In this work,we propose RAG-GFM, a Retrieval-Augmented Generation aided Graph Foundation Model that offloads knowledge from parameters and complements parameterized learning. To externalize graph knowledge, we build a dual-modal unified retrieval module, where a semantic store from prefix-structured text and a structural store from centrality-based motif. To preserve heterogeneous information, we design a dual-view alignment objective that contrasts both modalities to capture both content and relational patterns. To enable efficient downstream adaptation, we perform in-context augmentation to enrich supporting instances with retrieved texts and motifs as contextual evidence. Extensive experiments on five benchmark graph datasets demonstrate that RAG-GFM consistently outperforms 13 state-of-the-art baselines in both cross-domain node and graph classification, achieving superior effectiveness and efficiency.
Recent advances in generic large models, such as GPT and DeepSeek, have motivated the introduction of universality to graph pre-training, aiming to learn rich and generalizable knowledge across diverse domains using graph representations to improve performance in various downstream applications. However, most existing methods face challenges in learning effective knowledge from generic graphs, primarily due to simplistic data alignment and limited training guidance. The issue of simplistic data alignment arises from the use of a straightforward unification for highly diverse graph data, which fails to align semantics and misleads pre-training models. The problem with limited training guidance lies in the arbitrary application of in-domain pre-training paradigms to cross-domain scenarios. While it is effective in enhancing discriminative representation in one data space, it struggles to capture effective knowledge from many graphs. To address these challenges, we propose a novel Latent sEmantic Distribution Alignment (LEDA) model for universal graph pre-training. Specifically, we first introduce a dimension projection unit to adaptively align diverse domain features into a shared semantic space with minimal information loss. Furthermore, we design a variational semantic inference module to obtain the shared latent distribution. The distribution is then adopted to guide the domain projection, aligning it with shared semantics across domains and ensuring cross-domain semantic learning. LEDA exhibits strong performance across a broad range of graphs and downstream tasks. Remarkably, in few-shot cross-domain settings, it significantly outperforms in-domain baselines and advanced universal pre-training models.
Graph-based fraud detection (GFD) aims to identify fraud nodes within graph-structured data that significantly deviate from the majority of benign nodes. However, existing graph neural networks (GNNs) often struggle in GFD scenarios due to their reliance on homophily assumption, which is frequently violated by the inherent homophily-heterophily mixture of fraud graphs. Moreover, most methods focus primarily on local topology, overlooking mesoscopic community structures, making them less efficient in detecting suspicious patterns like densely connected subgraphs. To address the aforementioned issues, we present NeCo, a novel approach that integrates mixture of neighborhood and community experts for graph-based fraud detection. Specifically, we first introduce a fraud-discriminative representation preservation mechanism from a neighborhood perspective, leveraging the empirical finding that fraud nodes tend to exhibit larger feature propagation discrepancies compared to benign nodes. We then design a community-oriented node representation module that models structural compactness among nodes, enabling the detection of suspicious topological patterns associated with fraud behaviors. By integrating these two complementary perspectives, NeCo can effectively captures both local inconsistency and global structural irregularity. Extensive experiments across five real-world datasets demonstrate the effectiveness of our proposed NeCo over state-of-the-art baselines.
Foundation models are at the forefront of artificial intelligence. A tokenizer, converting the raw input into discrete representations that the model can understand, plays an important role to the success of foundation models. Unlike the text tokenizer that is well studied in large language models, graph tokenizer is still at its early stage, facing the challenges of tackling the non-Euclidean structures and capturing the structural semantics. How to design a graph tokenizer for structural knowledge transfer? To this end, we propose a Riemannian Graph Tokenizer (RGT ) that bridges the structural knowledge and quantized representations to support cross-domain structural knowledge transfer. The connection is established by Riemannian geometry. Specifically, we first define the geometric vocabulary (trees, cycles and sequences), which captures fundamental structural patterns and reflects the intrinsic geometry of graph. Second, we construct a Riemannian quantizer with Riemannian Straight-Through Estimator to tokenise graph structures across multiple domains into discrete tokens. To ensure consistency and transferability across diverse geometric spaces, RGT further incorporates a geometry-aligned decoder that projects manifold-specific tokens into a unified tangent space. The theoretical analysis and geometric interpretations are provided to support the effectiveness of our proposed method. Extensive experiments across diverse datasets demonstrate that RGT significantly enhances structural knowledge transferability across graph domains.
Accurate traffic flow forecasting is crucial for intelligent transportation systems and relies on effectively modeling complex spatio-temporal dependencies. Although recent graph-based deep learning methods have achieved promising results, most focus on pairwise neighbor relationships, limiting their ability to capture higher-order spatio-temporal interactions in the traffic network. To overcome this limitation, we propose a novel Multi-source information driven Spatio-Temporal HyperGraph learning for traffic forecasting (MSTHG), which is designed to capture richer relational and semantic information. MSTHG introduces a multi-source hypergraph fusion strategy that jointly models dynamic high-order spatial and temporal correlations. Specifically, we build a spatial hypergraph based on geographical proximity to represent high-order spatial dependencies, and a temporal-trend hypergraph leveraging mutual information to capture nonlinear similarities among traffic series. To enhance the semantic richness of node representations, we integrate key daily and weekly information along with periodic features derived from Fast Fourier Transform (FFT). Following the obtained hypergraph, node representations are learned through a hypergraph convolutional network and subsequently processed by a GRU-MLP fusion module, which is designed to capture both local and global temporal dependencies. Extensive experiments on real-world benchmark datasets demonstrate that MSTHG outperforms state-of-the-art baselines. The source code is https://github.com/April-leng/MSTHG.git.