Graph generation is a fundamental problem in graph learning with broad applications across Web-scale systems, knowledge graphs, and scientific domains such as drug and material discovery. Recent approaches leverage diffusion models for step-by-step generation, yet unconditional diffusion offers little control over desired properties, often leading to unstable quality and difficulty in incorporating new objectives. Inference-time guidance methods mitigate these issues by adjusting the sampling process without retraining, but they remain inherently local, heuristic, and limited in controllability. To overcome these limitations, we propose TreeDiff, a Monte Carlo Tree Search (MCTS) guided dual-space diffusion framework for controllable graph generation. TreeDiff is a plug-and-play inference-time method that expands the search space while keeping computation tractable. Specifically, TreeDiff introduces three key designs to make it practical and scalable: (1) a macro-step expansion strategy that groups multiple denoising updates into a single transition, reducing tree depth and enabling long-horizon exploration; (2) a dual-space denoising mechanism that couples efficient latent-space denoising with lightweight discrete correction in graph space, ensuring both scalability and structural fidelity; and (3) a dual-space verifier that predicts long-term rewards from partially denoised graphs, enabling early value estimation and removing the need for full rollouts. Extensive experiments on 2D and 3D molecular generation benchmarks, under both unconditional and conditional settings, demonstrate that TreeDiff achieves state-of-the-art performance. Notably, TreeDiff exhibits favorable inference-time scaling: it continues to improve with additional computation, while existing inference-time methods plateau early under limited resources.
论文检索
输入标题、作者或关键词，从 15,207 篇学术成果中精准定位
Identification of Influential Node Group in Attributed Graph through Explaining Graph Neural Network
Identification of influential groups of nodes in attributed graphs has applications in a wide range of real-world problems, for instance, collecting important proceedings in citation networks, or identifying essential genes for diagnosing disease in Protein-Protein Interaction networks. Previous approaches for influence maximization manipulated on the graph structure, despite their proliferation, neglect the node attribute information containing additional knowledge. In this work, we introduce Global Graph UNderstanding (GGUN), a perturbation-based framework leveraging the explanatory power of Graph Neural Networks. It takes into account the entire graph structure and node attributes simultaneously and fuses knowledge through GNN layers. Following the perturbation-based explanation, GGUN fills the gap between Deep Neural Network gradient-based feature importance analysis and discrete structure in the graph, which is formulated as a combinatorial optimization problem. Moreover, GGUN obtains an efficient solution by relaxing the infeasible combinatorial optimization problem with performance guaranteed. Evaluations of synthetic and real-world datasets show that GGUN outperforms baselines on both quantitative metrics and human-intelligible analysis.
Cross-domain recommendation (CDR) has emerged as a promising solution by effectively alleviating data sparsity by leveraging information from auxiliary domains. However, a major challenge in CDR is its dependence on predefined alignment rules (e.g., structural or distribution matching) to achieve cross-domain knowledge transfer, which impose fixed transfer patterns and lack the flexibly need for diverse cross-domain scenarios. Furthermore, most existing approaches still rely on coarse-grained representations. Knowledge transfer built upon imprecise representations can, even with improved alignment rules, instead lead to negative transfer in the target domain. To address these challenges and optimize recommendation efficacy, a new framework named meta-learning driven few-shot knowledge transfer with dual-stage adaptive data replay for cross-domain recommendation (MFACDR) is proposed. Specifically, a new meta-learning driven few-shot knowledge transfer method is proposed. This method leverages overlapping parts as anchors to guide the non-overlapping parts in autonomously exploring alignment rules through meta-learning, thus enabling few-shot knowledge transfer and flexible handling of different cross-domain scenarios. In addition, a dual-stage adaptive data replay mechanism is proposed, which enables fine-grained cross-domain adaptability and helps to mitigate negative transfer. Extensive experiments on three real-world datasets consistently demonstrate the superior effectiveness and robustness of the proposed MFACDR.
This paper investigates a novel and critical problem of Graph Cross-Domain Continual Fine-Tuning, which aims to adapt a large pre-trained Graph Foundation Model across diverse domains. Existing continual graph learning methods are mostly limited to incremental settings within only a single domain, and are typically trained from scratch. As a result, they fail to handle cross-domain shifts effectively, suffer from severe forgetting, and lack transferability. To address these challenges, we present G-CORMoL, Graph Continual Fine-tuning with Orthogonal, Router-driven Mixture of LoRA experts. G-CORMoL achieves effective adaptation while preserving prior knowledge by enforcing mathematical orthogonality between expert LoRA adapters, thereby eliminating interference across tasks. It further supports cross-domain knowledge transfer through a symmetric dual-driven routing mechanism that learns a global composition policy over all learned LoRA experts. In addition, it promotes expert specialization via a contrastive objective with theoretical guarantees. Extensive experiments on different cross-domain task orders demonstrate that G-CORMoL achieves robust state-of-the-art performance, not only preventing catastrophic forgetting but also leveraging accumulated knowledge to enable positive transfer.
Federated graph-level clustering (FGC) provides an effective solution for analyzing decentralized graph data with privacy protection. Existing methods typically assume that all clients have the same number of clusters. This assumption simplifies the learning task and has achieved preliminary success. However, this assumption rarely holds in practice, as clients often exhibit substantial heterogeneity in both data distributions and semantic granularity. As a result, cluster-specific knowledge becomes misaligned during server-side aggregation, which ultimately degrades the overall clustering performance. To address this challenge, we propose a novel Federated Graph Clustering under Inter-Client Cluster Number Discrepancy (FedCND) framework, which aligns inter-client heterogeneous distributions by decoupling graph data into public and private patterns. Specifically, after initial local training and clustering on each client, we design a public learner and a private learner to model public and private graph data, respectively. Only anonymized, cluster-level public information is uploaded to the server, while private information remains local. On the server, cluster-level public prototypes are aggregated based on affinities between reconstructed cluster-level graphs, enabling privacy-preserving prototype alignment across clients with heterogeneous cluster numbers and mitigating interference from misaligned information during global aggregation. Finally, private subgraphs derive client-specific prototypes through local relearning, which are subsequently fused with globally oriented public prototypes for better clustering. Extensive experiments demonstrate that the proposed FedCND achieves an average of 4.9% accuracy improvement against current state-of-the-art methods.
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.
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.
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.
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.
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.
Graph anomaly detection (GAD) identifies nodes, edges, and subgraphs that deviate from normal patterns, playing a key role in cybersecurity, finance, and web technologies. However, existing deep learning paradigms trained on fixed datasets struggle to generalize to unseen graphs, while current graph foundation models (GFMs) face inherent challenges in anomaly detection. Their generalization objectives conflict with the rarity and divergence of anomalies, and existing attempts to develop GFMs for GAD mainly fall into two directions: single-task cross-domain models and domain-specific multi-task models. The former transfers knowledge across domains but fails to capture cross-level dependencies, whereas the latter handles multiple tasks jointly but lacks cross-domain adaptability. Both rely heavily on labeled data, limiting scalability. These limitations highlight the need for a unified unsupervised graph foundation model capable of generalizing across domains and detecting anomalies at multiple levels. We propose GFM-UAD, a Graph Foundation Model for Unified Anomaly Detection. It is pretrained on a single dataset and performs multi-level anomaly detection across unlabeled domains. To address anomaly scarcity, GFM-UAD extracts high-confidence normal samples and synthesizes diverse anomalies through adversarial generation. By freezing the backbone and fine-tuning the detection head with distribution alignment and message passing, the model adapts flexibly to unseen environments without supervision. Experiments across multiple datasets demonstrate that GFM-UAD achieves superior accuracy and generalization, establishing a foundation for future unsupervised graph foundation models in anomaly detection.
In web-based systems, elements are commonly organized within a graph structure, with each node collecting essential spatio-temporal data. Examples include websites on the World Wide Web, traffic monitors in transportation networks, or sensors in the Internet of Things (IoT). However, sensors are typically deployed sparsely and unevenly, leaving the remaining nodes unobserved. The spatio-temporal kriging task, which infers values at unobserved nodes from observed ones, has thus attracted significant research interest. Due to limitations such as reliance on static graph structures and iterative Graph Convolution Network (GCN) frameworks, accurate kriging remains challenging. To address these issues, we propose a Diffusion-based Kriging Model with Graph-enhanced Attention (DKM-GA). Our approach first introduces a graph-enhanced attention mechanism that dynamically learns more accurate graph structures by combining predefined graph knowledge with global node value similarities. It is then integrated into a diffusion-based framework, which is tailored for the reliance of attention on known values. Therefore, the framework progressively refines the target values using correlated nodes, and the graph-enhanced attention selects more relevant neighbors based on the refined values. Furthermore, a node-based rescaling strategy is introduced to align the inference phase graphs to the training ones. Experiments on eight real-world datasets demonstrate that DKM-GA achieves superior performance, reducing estimation errors by up to 12.66%. Moreover, our analysis identifies three practical scenarios where the model delivers greater performance gains, even achieving 19.51% improvements on datasets that show minor gains under standard settings. These results highlight the effectiveness and potential of our model, while the scenarios provide settings for more comprehensive evaluations in terms of performance and robustness.
Graph incremental learning aims to sequentially adapt models to evolving graphs while mitigating catastrophic forgetting. This problem becomes particularly challenging due to the simultaneous occurrence of covariate and label distribution shifts, introduced by newly emerging node classes, changes in node feature styles, and additional edges. To address these challenges, we propose DINGLE, a novel framework for both class and domain (class-domain) incremental learning on graphs. DINGLE consists of two key modules: a representation decoupler, which disentangles node representations into domain-invariant semantic factors for classification and domain-specific variation factors, and a teacher-student knowledge distillation module, which facilitates knowledge transfer across tasks while mitigating catastrophic forgetting through memory replay. By leveraging a Representative Node Feature (RNF) bank and an Encoder Parameters (EP) bank, DINGLE ensures effective knowledge retention and adaptation. Extensive experiments on 5 real-world datasets demonstrate that DINGLE outperforms 11 state-of-the-art baselines in class-domain incremental learning, improving classification accuracy while effectively preventing forgetting across tasks.
Unsupervised graph domain adaptation (UGDA) aims to transfer knowledge from a labeled source graph to an unlabeled target graph, addressing the performance degradation caused by distributional shifts in node attributes and graph structures across domains. Despite recent progress, existing UGDA approaches still face two key challenges: (C1) Data-level: Most methods rely on a single source domain, overlooking the complementary knowledge that could be leveraged from multiple sources. (C2) Model-level: Many UGDA models emphasize complex, handcrafted Graph neural network (GNN) architectures, while simpler yet effective designs with propagation (P) & transformation (T) pipeline remain underexplored. To address these challenges, in this paper, we propose a novel approach, which leverages Concise Propagation–Transformation pipeline for multi-source unsupervised Graph Domain Adaptation, dubbed as CPT-GDA, to better capture complementary knowledge from multiple sources in an efficient manner. Specifically, the proposed CPT-GDA adopts a dual-branch GNN architecture with different depths of propagation but the same P-T patterns, which enables the model to efficiently learn node representations to mitigate domain discrepancy. Meanwhile, to facilitate effective knowledge transfer across graphs, we derive three optimization objectives: (1) the classifier loss to learn discriminative representations; (2) the alignment loss weighted by the graph Wasserstein distance to align the structure and feature distribution; and (3) the pseudo-label loss to refine target node representations. Extensive experiments on real-world datasets confirm that the proposed method outperforms recent state-of-the-art baselines, demonstrating its effectiveness.
We initiate the study of single-sample bilateral trade with a broker, drawing an analogy to the setting of single-sample bilateral trade without a broker considered in [1] and [5]. Our model captures the three-sided interaction in which a broker mediates trade between a buyer and seller, each described by a valuation distribution from which a single sample can be drawn. We consider two settings in particular: one where the valuation distributions of the buyer and seller are identical and one where the valuation distributions are stochastically ordered. We analyze simple mechanisms that rely only on a single sample from each agent's distribution and show that these mechanisms achieve constant-factor approximations to the first-best gains-from-trade (GFT), first-best social welfare (SW), and optimal profit under the standard monotone-hazard-rate assumption. We then complement these results with matching or nearly matching upper bounds on the GFT and SW of our mechanisms. Notably, in both settings, we observe fairly small losses in the approximation factors to the first-best GFT and first-best SW due to the existence of the broker (benchmarked against the corresponding approximation factors in the setting without a broker). Furthermore, our results stand in stark contrast to those of [12], who show inapproximability results under a strategic broker with full distributional knowledge. Our results provide insight into the design of data-efficient brokerage mechanisms for online marketplaces and decentralized trading platforms, where intermediaries must facilitate trade under severe informational constraints. They highlight how even minimal data can enable robust and incentive-compatible brokerage in uncertain markets for both the broker and the market participants.
In online advertising, the inherent complexity and dynamic nature of advertising environments necessitate the use of auto-bidding services to assist advertisers in bid optimization. The complexity escalates in multi-channel scenarios, where effective allocation of budgets and constraints across channels with distinct behavioral patterns becomes critical for optimizing return on investment. Current approaches predominantly employ either optimization-based strategies or reinforcement learning (RL) techniques. However, optimization-based methods lack the flexibility to adapt to dynamic market conditions, while RL-based approaches struggle to capture essential historical dependencies and observational patterns within the constraints of Markov Decision Process (MDP) frameworks. To address these limitations, we propose AHBid, an Adaptable Hierarchical Bidding framework that integrates generative planning with real-time control. The framework employs a high-level generative planner utilizing diffusion models to dynamically allocate budgets and constraints through effective capture of historical context and temporal patterns. We introduce a constraint enforcement mechanism to ensure compliance with specified constraints, complemented by a trajectory refinement mechanism that enhances adaptability to environmental changes through historical data utilization. The system further incorporates a control-based bidding algorithm that synergistically combines historical knowledge with real-time information, significantly improving both adaptability and operational efficacy. Extensive experiments are conducted using both large-scale offline datasets and online A/B tests, demonstrating the effectiveness of AHBid by yielding a 13.57% increase in overall return compared to existing baselines.
We investigate majority voting where agents possess private information about an unobservable ground truth that determines their preferences. In such settings, agents may hold different preferences and (collectively) engage in counterintuitive strategic behaviors. Previous work either assumes strategic behavior occurs without coordination or with unlimited coordination, yielding overly inclusive or exclusive predictions about voting outcomes. We incorporate coordination ability—the largest coalition size at which agents could strategically coordinate—into the analysis. Under the ex-ante Bayesian k-strong equilibrium framework, where no group of at most k agents can benefit from deviation, we provide closed-form characterizations of when informed majority decisions, the decision favored by the majority if the ground truth is common knowledge, are achievable. Specifically, we determine (1) when all k-strong equilibria reach the informed majority decision and (2) when at least one such equilibrium exists. These conditions depend on three factors: coordination ability, fraction of majority agents, and information structure. The boundary for the second question exhibits surprising complexity--non-continuous, non-linear, and segmental. Our results reveal the complicated landscape and provide refined predictions for strategic behavior across different coordination levels.
The growing scale of ad auctions on online advertising platforms has intensified competition, making manual bidding impractical and necessitating auto-bidding to help advertisers achieve their economic goals. Current auto-bidding methods have evolved to use offline reinforcement learning or generative methods to optimize bidding strategies, but they can sometimes behave counterintuitively due to the black-box training manner and limited mode coverage of datasets, leading to challenges in understanding task status and generalization in dynamic ad environments. Large language models (LLMs) offer a promising solution by leveraging prior human knowledge and reasoning abilities to improve auto-bidding performance. However, directly applying LLMs to auto-bidding faces difficulties due to the need for precise actions in competitive auctions and the lack of specialized auto-bidding knowledge, which can lead to hallucinations and suboptimal decisions. To address these challenges, we propose a hierarchical Large auto-Bidding Model (LBM) to leverage the reasoning capabilities of LLMs for developing a superior auto-bidding strategy. This includes a high-level LBM-Think model for reasoning and a low-level LBM-Act model for action generation. Specifically, we propose a dual embedding mechanism to efficiently fuse two modalities, including language and numerical inputs, for language-guided training of the LBM-Act; then, we propose an offline reinforcement fine-tuning technique termed GQPO for mitigating the LLM-Think's hallucinations and enhancing decision-making performance without simulation or real-world rollout like previous multi-turn LLM-based methods. Experiments demonstrate the superiority of a generative backbone based on our LBM, especially in an efficient training manner and generalization ability.
Auto-bidding systems are widely used in advertising to automatically determine bid values under constraints such as total budget and Return-on-Spend (RoS) targets. Existing works often assume that the value of an ad impression, such as the conversion rate, is known. This paper considers the more realistic scenario where the true value is unknown. We propose a novel method that uses conformal prediction to quantify the uncertainty of these values based on machine learning methods trained on historical bidding data with contextual features, without assuming the data are i.i.d. This approach is compatible with current industry systems that use machine learning to predict values. Building on prediction intervals, we introduce an adjusted value estimator derived from machine learning predictions, and show that it provides performance guarantees without requiring knowledge of the true value. We apply this method to enhance existing auto-bidding algorithms with budget and RoS constraints, and establish theoretical guarantees for achieving high reward while keeping RoS violations low. Empirical results on both simulated and real-world industrial datasets demonstrate that our approach improves performance while maintaining computational efficiency.