Graph Anomaly Detection (GAD) identifies deviant patterns including anomalous nodes, edges, and subgraphs in graph data, with significant applications in social networks, cybersecurity, and financial risk control. While spectral methods have proven effective for homogeneous graph anomaly detection, their application to heterogeneous graphs remains challenging due to structural complexity and semantic richness. Existing heterogeneous graph anomaly detection methods either rely on manually designed meta-paths or decompose the graph into homogeneous subgraphs, leading to limited flexibility or loss of structural integrity. To address these limitations, we propose the Graph Wavelet Transformer (GWT), a novel spectral-based approach that integrates global graph properties and spectral analysis without requiring meta-path information. GWT employs a three-stage process: heterogeneous-to-homogeneous graph conversion, global dependency modeling via graph transformers, and spectral-aware feature enhancement focusing on frequency band components. Extensive experiments on multiple benchmarks demonstrate that GWT significantly outperforms ten baseline methods, providing a new paradigm for heterogeneous graph anomaly detection that preserves structural completeness while achieving computational efficiency.

Graph-level out-of-distribution (OOD) detection, which attempts to identify OOD graphs originated from an unknown distribution, is a vital building block for safety-critical applications in Web and society. Current approaches concentrate on how to learn better graph representations, but fail to provide any statistically guarantee on detection results, therefore impeding their deployments in the scenario where detection errors would result in serious consequences. To overcome this critical issue, we propose the Conformal Graph-level Out-of-distribution Detection (CGOD), extending the theory of conformal prediction to graph-level OOD detection with a rigorous control over the false positive rate. In CGOD, we develop a new aggregated non-conformity score function based on the proposed adaptive data augmentation. Through the guidance from two designed metrics, i.e., score consistency and representation diversity, our augmentation strategy can generate multiple non-conformity scores, and aggregating these generated non-conformity scores together is robust to the misleading information. Meanwhile, our score function can perceive the subsequent process of conformal inference, enabling the aggregated non-conformity score to be adaptive to different input graphs and deriving a more accurate score estimation. We conduct experiments on multiple real-world datasets with different empirical settings. Extensive results and model analyses demonstrate the superior performance of our approach over several competitive baselines.

Dynamics modeling has been introduced as a novel paradigm in message passing (MP) of graph neural networks (GNNs). Existing methods consider MP between nodes as a heat diffusion process, and leverage heat equation to model the temporal evolution of nodes in the embedding space. However, heat equation can hardly depict the wave nature of graph signals in graph signal processing. Besides, heat equation is essentially a partial differential equation (PDE) involving a first partial derivative of time, whose numerical solution usually has low stability, and leads to inefficient model training. In this paper, we would like to depict more wave details in MP, since graph signals are essentially wave signals that can be seen as a superposition of a series of waves in the form of eigenvector. This motivates us to consider MP as a wave propagation process to capture the temporal evolution of wave signals in the space. Based on wave equation in physics, we innovatively develop a graph wave equation to leverage the wave propagation on graphs. In details, we demonstrate that the graph wave equation can be connected to traditional spectral GNNs, facilitating the design of graph wave networks (GWNs) based on various Laplacians and enhancing the performance of the spectral GNNs. Besides, the graph wave equation is particularly a PDE involving a second partial derivative of time, which has stronger stability on graphs than the heat equation that involves a first partial derivative of time. Additionally, we theoretically prove that the numerical solution derived from the graph wave equation are constantly stable, enabling to significantly enhance model efficiency while ensuring its performance. Extensive experiments show that GWNs achieve state-of-the-art and efficient performance on benchmark datasets, and exhibit outstanding performance in addressing challenging graph problems, such as over-smoothing and heterophily. Our code is available at https://github.com/YueAWu/Graph-Wave-Networks.

Methods based on graph neural networks for solving combinatorial optimization (CO) problems have exhibited promising results in tackling a range of NP-hard problems, eliminating the necessity for reliance on manually created domain knowledge. Existing models including reinforcement learning (RL) framework assume that combinatorial instances in the training set contribute equally during training. Nevertheless, there is considerable variation in the quality of training instances, and the performance of models may suffer from the inclusion of low-quality training instances. This paper expands the current scope of neural solvers for CO problems through the incorporation of curriculum learning (CL). To alleviate the adverse impact of low-quality training instances, we propose CL4CO which utilizes CL strategy, a selective training method, to train models based on the rank of instances' quality in neural Combinatorial Optimization framework. Also, we introduce several candidate topology-aware metrics based on heterophily ratio and evaluation of clustering for the training scheduler. Furthermore, it is noteworthy to emphasize that it has potential to enhance the generalization capacity of RL-based baselines and we give a experimental validation. This enhancement plugin from the fact that CL empowers the acquired RL-based solver to effectively leverage commonly shared features within the same class of CO. Empirically, we conduct a case study on MaxCut, a classical discrete Oil-vector CO, to verify our findings and our results demonstrate that CL4CO is efficient and superiority with good generalization ability.

Recommender systems have been widely adopted in various online personal e-commerce applications for improving user experience. A long-standing challenge in recommender systems is how to provide accurate recommendation to users in cold-start situations where only a few user-item interactions can be observed. Recently, meta learning methods provide a promising solution, and most of them follow a way of parameter initialization where predictions can be fast adapted via multiple gradient descent steps. While these meta-learning recommenders promote model performance, how to derive a fundamental paradigm that enables both flexible approximations of complex user interaction distributions and effective task adaptations of global knowledge still remains a critical yet under-explored problem. To this end, we present the Flow-based Adaptive Neural Process (FANP), a new probabilistic meta-learning model where estimating the preference of each user is governed by an underlying stochastic process. Following an encoder-decoder generative framework, FANP is an effective few-shot function estimator that directly maps limited user interactions to a predictive distribution without complicated gradient updates. Through introducing a conditional normalization flow-based encoder, FANP can get rid of the model bias on latent variables and thereby derive more flexible variational distributions. Meanwhile, we propose a task-adaptive mechanism capturing the relevance of different tasks for improving adaptation ability of global knowledge. The learned task-specific and task-relevant representations are simultaneously exploited to generate the decoder parameters via a novel modulation-augmented hypernetwork. FANP is evaluated on both scenario-specific and user-specific cold-start recommendations on various real-world datasets. Extensive experimental results and detailed model analyses demonstrate that our model yields superior performance compared with multiple state-of-the-art meta-learning recommenders.

Graph pooling technique as the essential component of graph neural networks has gotten increasing attention recently and it aims to learn graph-level representations for the whole graph. Besides, graph pooling is important in graph classification and graph generation tasks. However, current graph pooling methods mainly coarsen a sequence of small-sized graphs to capture hierarchical structures, potentially resulting in the deterioration of the global structure of the original graph and influencing the quality of graph representations. Furthermore, these methods artificially select the number of graph pooling layers for different graph datasets rather than considering each graph individually. In reality, the structure and size differences among graphs necessitate a specific number of graph pooling layers for each graph. In this work, we propose reinforced pooling graph neural networks via adaptive hybrid graph coarsening networks. Specifically, we design a hybrid graph coarsening strategy to coarsen redundant structures of the original graph while retaining the global structure. In addition, we introduce multi-agent reinforcement learning to adaptively perform the graph coarsening process to extract the most representative coarsened graph for each graph, enhancing the quality of graph-level representations. Finally, we design graph-level contrast to improve the preservation of global information in graph-level representations. Extensive experiments with rich baselines on six benchmark datasets show the effectiveness of ReiPool1.

Graph Neural Networks (GNNs) have achieved impressive performance in many tasks on graph data. Recent studies show that they are vulnerable to adversarial attacks. Deliberate and unnoticeable perturbations on topology structure could render them near-useless in applications. How to design effective methods to improve the robustness of GNNs is a crucial problem. To solve this problem, some works attempt to design more robust GNN models, while others attempt to remove perturbations from the poisoned graph. Different from the previous works, this paper proposes a general framework termed asGraphReshapeto enhance the robustness of GNNs via directly correcting the shifted classification boundary of GNN models in the presence of adversarial attacks.GraphReshapeconsists of two modules:locating tractive nodesthat could correct GNNs andreshaping local structureto improve their representations in the latent space. Extensive experiments on four real-world datasets show thatGraphReshapeachieves significant performance gain compared with state-of-the-art baselines against different adversarial attacks.

Graph contrastive learning (GCL) has recently achieved substantial advancements. Existing GCL approaches compare two different “views“ of the same graph in order to learn node/graph representations. The underlying assumption of these studies is that the graph augmentation strategy is capable of generating several different graph views such that the graph views are structurally different but semantically similar to the original graphs, and thus the ground-truth labels of the original and augmented graph/nodes can be regarded identical in contrastive learning. However, we observe that this assumption does not always hold. For instance, the deletion of a supernode within a social network can exert a substantial influence on the partitioning of communities for other nodes. Similarly, any perturbation to nodes or edges in a molecular graph will change the labels of the graph. Therefore, we believe that augmenting the graph, accompanied by an adaptation of the labels used for the contrastive loss, will facilitate the encoder to learn a better representation. Based on this idea, we propose ID-MixGCL, which allows the simultaneous interpolation of input nodes and corresponding identity labels to obtain soft-confidence samples, with a controllable degree of change, leading to the capture of fine-grained representations from self-supervised training on unlabeled graphs. Experimental results demonstrate that ID-MixGCL improves performance on graph classification and node classification tasks, as demonstrated by significant improvements on the Cora, IMDB-B, IMDB-M, and PROTEINS datasets compared to state-of-the-art techniques, by 3-29parcent absolute points. The dataset and source code can be found at: https://github.com/zhanggehang/ID-MIXGCL.

Decision-focused learning (DFL) combines both machine learning and combinatorial optimization so as to enhance the quality of decision-making. In general, DFL adds an optimization layer after the neural network and solves a focused combinatorial optimization problem. The optimization layer is usually based on KKT conditions or surrogate functions. However, the optimizer associated with the DFL is inflexible and requires a large amount of expert knowledge. Furthermore, it has been shown that the optimizer exhibits a lack of robustness and differentiability when confronted with complex tasks, especially in the graph domain. To solve this problem, we study a more generic situation by taking the optimization layer as a black-box operator on graphs. Then, we design a mixed zeroth-order optimization to differentiate the layer. Specifically, we combine DFL with graph neural networks and present a decision-focused graph neural network named ZO4Graph based on a mixed zeroth-order optimizer. Empirically, we conduct extensive experiments compared with two-stage models on community detection. Numerical results demonstrate that our proposed framework outperforms its peers.

Anomaly detection in multi-type event sequences is a crucial and challenging problem with important applications in various domains, including cybersecurity, finance and healthcare. Temporal point process has emerged as a powerful technique for modeling event sequences and has gained considerable attention in the field of anomaly detection. However, existing temporal point process approaches are either inapplicable to multi-type event sequence data or incur the loss of valuable information in subsequences associated with specific event types. To this end, we propose a novel Multiple Hypothesis Testing based Anomaly Detection method (MultiAD) to detect anomalous multi-type event sequences. The basic idea of MultiAD is to capture the underlying distribution of normal sequences using a neural multivariate point process, based on which the original hypothesis testing problem can be converted into a multiple hypothesis testing using the multivariate time rescaling theorem. By conducting multiple hypothesis tests on the time-rescaled subsequences, MultiAD makes full use of the valuable information contained within individual subsequences. Moreover, we claim that the existing test statistic ignores the sequential information of inter-event time intervals and propose new statistics to address this shortcoming. Finally, we employ the kernel method to obtain a smooth estimator of the distribution of the proposed statistics under the null hypothesis. This ensures a more accurate and reliable computation of the p-value, providing robust statistical inference. Extensive experimental results demonstrate that MultiAD significantly outperforms the state-of-the-art methods on both synthetic and real-world data.

Graph neural networks (GNNs) are powerful models to handle graph data and can achieve state-of-the-art in many critical tasks including node classification and link prediction. However, existing graph neural networks still face both challenges of over-smoothing and over-squashing based on previous literature. To this end, we propose a new Curvature-based topology-aware Dropout sampling technique named CurvDrop, in which we integrate the Discrete Ricci Curvature into graph neural networks to enable more expressive graph models. Also, this work can improve graph neural networks by quantifying connections in graphs and using structural information such as community structures in graphs. As a result, our method can tackle the both challenges of over-smoothing and over-squashing with theoretical justification. Also, numerous experiments on public datasets show the effectiveness and robustness of our proposed method. The code and data are released in https://github.com/liu-yang-maker/Curvature-based-Dropout.

Graph neural architecture search (NAS) has gained popularity in automatically designing powerful graph neural networks (GNNs) with relieving human efforts. However, existing graph NAS methods mainly work under the homophily assumption and overlook another important graph property, i.e., heterophily, which exists widely in various real-world applications. To date, automated heterophilic graph learning with NAS is still a research blank to be filled in. Due to the complexity and variety of heterophilic graphs, the critical challenge of heterophilic graph NAS mainly lies in developing the heterophily-specific search space and strategy. Therefore, in this paper, we propose a novel automated graph neural network on heterophilic graphs, namely Auto-HeG, to automatically build heterophilic GNN models with expressive learning abilities. Specifically, Auto-HeG incorporates heterophily into all stages of automatic heterophilic graph learning, including search space design, supernet training, and architecture selection. Through the diverse message-passing scheme with joint micro-level and macro-level designs, we first build a comprehensive heterophilic GNN search space, enabling Auto-HeG to integrate complex and various heterophily of graphs. With a progressive supernet training strategy, we dynamically shrink the initial search space according to layer-wise variation of heterophily, resulting in a compact and efficient supernet. Taking a heterophily-aware distance criterion as the guidance, we conduct heterophilic architecture selection in the leave-one-out pattern, so that specialized and expressive heterophilic GNN architectures can be derived. Extensive experiments illustrate the superiority of Auto-HeG in developing excellent heterophilic GNNs to human-designed models and graph NAS models.

Graph neural networks (GNNs) are popularly used to analyze non-Euclidean graph data. Despite their successes, the design of graph neural networks requires heavy manual work and rich domain knowledge. Recently, neural architecture search algorithms are widely used to automatically design neural architectures for CNNs and RNNs. Inspired by the success of neural architecture search algorithms, we present a graph neural architecture search algorithm GraphNAS that enables automatic design of the best graph neural architecture based on reinforcement learning. Specifically, GraphNAS uses a recurrent network as the controller to generate variable-length strings that describe the architectures of graph neural networks, and trains the recurrent network with policy gradient to maximize the expected accuracy of the generated architectures on a validation data set. Moreover, based on GraphNAS, we design a new GraphNAS++ model using distributed neural architecture search. Compared with GraphNAS that generates and evaluates only one candidate architecture at each iteration, GraphNAS++ generates a mini-batch of candidate architectures and evaluates them in a distributed computing environment until convergence. Experiments on real-world datasets demonstrate that GraphNAS can design a novel network architecture that rivals the best human-invented architecture. Moreover, GraphNAS++ can speed up the design process at least five times by using the distributed training framework with GPUs.

Heterogeneous graphs are commonly used to describe networked data with multiple types of nodes and edges. Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for analyzing heterogeneous graphs. However, designing neural architectures of HGNNs requires extensive domain knowledge and time-consuming manual work. Recently, neural architecture search algorithms have become popular in automatically designing neural architectures for homogeneous graph neural networks. In this paper, we present a Heterogeneous Graph Neural Architecture Search algorithm (HGNAS for short) which allows the automatic design of heterogeneous graph neural architectures. Specifically, HGNAS first designs a new search space based on existing popular HGNNs. Then, HGNAS uses a policy network as the controller to sample and find the best neural architecture from the designed search space by maximizing the expected accuracy of the selected architectures on a given validation dataset. Moreover, we design a new method HGNAS++ to improve the efficiency of HGNAS by training the RNN controller within a generative adversarial learning framework. The basic idea of HGNAS++ is to embed a pairwise ranker into the reinforcement learning based architecture search algorithm. The pairwise ranker can be taken as a discriminator which selects more accurate architectures between pairs of candidate architectures. Then, the RNN controller can be updated more efficiently by only using a relatively small number of candidate architectures selected by the pairwise ranker. Experiments on real-world heterogeneous graph datasets show that HGNAS is capable of designing novel HGNNs that beat the best human-invented HGNNs. On the benchmark datasets, HGNAS++ improves HGNAS in terms of evaluation cost, with a reduction of 50% of the evaluated candidate architectures and a decrease of 24% in search time on average. As a byproduct, HGNAS++ can find sparse yet powerful neural architectures for HGNNs.

Deep learning on graphs has attracted significant interests recently. However, most of the works have focused on (semi-) supervised learning, resulting in shortcomings including heavy label reliance, poor generalization, and weak robustness. To address these issues, self-supervised learning (SSL), which extracts informative knowledge through well-designed pretext tasks without relying on manual labels, has become a promising and trending learning paradigm for graph data. Different from SSL on other domains like computer vision and natural language processing, SSL on graphs has an exclusive background, design ideas, and taxonomies. Under the umbrella of graph self-supervised learning, we present a timely and comprehensive review of the existing approaches which employ SSL techniques for graph data. We construct a unified framework that mathematically formalizes the paradigm of graph SSL. According to the objectives of pretext tasks, we divide these approaches into four categories: generation-based, auxiliary property-based, contrast-based, and hybrid approaches. We further describe the applications of graph SSL across various research fields and summarize the commonly used datasets, evaluation benchmark, performance comparison and open-source codes of graph SSL. Finally, we discuss the remaining challenges and potential future directions in this research field.

Anomalies are rare observations (e.g., data records or events) that deviate significantly from the others in the sample. Over the past few decades, research on anomaly mining has received increasing interests due to the implications of these occurrences in a wide range of disciplines - for instance, security, finance, and medicine. For this reason, anomaly detection, which aims to identify these rare observations, has become one of the most vital tasks in the world and has shown its power in preventing detrimental events, such as financial fraud, network intrusions, and social spam. The detection task is typically solved by identifying outlying data points in the feature space, which, inherently, overlooks the relational information in real-world data. At the same time, graphs have been prevalently used to represent the structural/relational information, which raises thegraph anomaly detection problem- identifying anomalous graph objects (i.e., nodes, edges and sub-graphs) in a single graph, or anomalous graphs in a set/database of graphs. Conventional anomaly detection techniques cannot tackle this problem well because of the complexity of graph data (e.g., irregular structures, relational dependencies, node/edge types/attributes/directions/multiplicities/weights, large scale, etc.). However, thanks to the advent of deep learning in breaking these limitations, graph anomaly detection with deep learning has received a growing attention recently. In this survey, we aim to provide a systematic and comprehensive review of the contemporary deep learning techniques for graph anomaly detection. Specifically, we provide a taxonomy that follows a task-driven strategy and categorizes existing work according to the anomalous graph objects that they can detect. We especially focus on the challenges in this research area and discuss the key intuitions, technical details as well as relative strengths and weaknesses of various techniques in each category. From the survey results, we highlight 12 future research directions spanning unsolved and emerging problems introduced by graph data, anomaly detection, deep learning and real-world applications. Additionally, to provide a wealth of useful resources for future studies, we have compiled a set of open-source implementations, public datasets, and commonly-used evaluation metrics. With this survey, our goal is to create a “one-stop-shop” that provides a unified understanding of the problem categories and existing approaches, publicly available hands-on resources, and high-impact open challenges for graph anomaly detection using deep learning.

Graph neural networks (GNNs) offer promising learning methods for graph-related tasks. However, GNNs are at risk of adversarial attacks. Two primary limitations of the current evasion attack methods are highlighted: (1) The currentGradArgmaxignores the “long-term” benefit of the perturbation. It is faced with zero-gradient and invalid benefit estimates in certain situations. (2) In the reinforcement learning-based attack methods, the learned attack strategies might not be transferable when the attack budget changes. To this end, we first formulate the perturbation space and propose an evaluation framework and the projective ranking method. We aim to learn a powerful attack strategy then adapt it as little as possible to generate adversarial samples under dynamic budget settings. In our method, based on mutual information, we rank and assess the attack benefits of each perturbation for an effective attack strategy. By projecting the strategy, our method dramatically minimizes the cost of learning a new attack strategy when the attack budget changes. In the comparative assessment withGradArgmaxandRL-S2V, the results show our method owns high attack performance and effective transferability. The visualization of our method also reveals various attack patterns in the generation of adversarial samples.

Recommender systems which captures dynamic user interest based on time-ordered user-item interactions plays a critical role in the real-world. Although existing deep learning-based recommendation systems show good performances, these methods have two main drawbacks. Firstly, user interest is the consequence of the coaction of many factors. However, existing methods do not fully explore potential influence factors and ignore the user-item interaction formation process. The coarse-grained modeling patterns cannot accurately reflect complex user interest and leads to suboptimal recommendation results. Furthermore, these methods are implicit and largely operate in a black-box fashion. It is difficult to interpret their modeling processes and recommendation results. Secondly, recommendation datasets usually exhibit scale-free distributions and some existing recommender systems take advantage of hyperbolic space to match the data distribution. But they ignore that the operations in hyperbolic space are more complex than that in Euclidean space which further increases the difficulty of model interpretation. To tackle the above shortcomings, we propose an E xplainable H yperbolic T emporal P oint P rocess for User-Item Interaction Sequence Generation (EHTPP) . Specifically, EHTPP regards each user-item interaction as an event in hyperbolic space and employs a temporal point process framework to model the probability of event occurrence. Considering that the complexity of user interest and the interpretability of the model,EHTPP explores four potential influence factors related to user interest and uses them to explicitly guide the probability calculation in the temporal point process. In order to validate the effectiveness of EHTPP, we carry out a comprehensive evaluation of EHTPP on three datasets compared with a few competitive baselines. Experimental results demonstrate the state-of-the-art performances of EHTPP.

Graph anomaly detection in this paper aims to distinguish abnormal nodes that behave differently from the benign ones accounting for the majority of graph-structured instances. Receiving increasing attention from both academia and industry, yet existing research on this task still suffers from two critical issues when learning informative anomalous behavior from graph data. For one thing, anomalies are usually hard to capture because of their subtle abnormal behavior and the shortage of background knowledge about them, which causes severe anomalous sample scarcity. Meanwhile, the overwhelming majority of objects in real-world graphs are normal, bringing the class imbalance problem as well. To bridge the gaps, this paper devises a novel Data Augmentation-based Graph Anomaly Detection (DAGAD) framework for attributed graphs, equipped with three specially designed modules: 1) an information fusion module employing graph neural network encoders to learn representations, 2) a graph data augmentation module that fertilizes the training set with generated samples, and 3) an imbalance-tailored learning module to discriminate the distributions of the minority (anomalous) and majority (normal) classes. A series of experiments on three datasets prove that DAGAD outperforms ten state-of-the-art baseline detectors concerning various mostly-used metrics, together with an extensive ablation study validating the strength of our proposed modules.

Graph neural architecture search (NAS) has gained great popularity in automatically designing powerful graph neural networks (GNNs) with superior learning abilities, significantly relieving human effort and expertise reliance. Despite the advanced performance of automated learning, existing graph NAS models mainly work on single-relational graphs, while the widespread multi-relational graphs in real-world applications, are not well addressed. Moreover, current search spaces of automated GNNs are generally coarse-grained by simply integrating typical GNN layers and hyper-parameters, resulting in severe limitations on search capacities and scopes for creating innovative GNN architectures. To tackle the limitations of single-relational setting and coarse-grained search space design in existing graph NAS, in this paper, we propose a novel framework of multi-relational graph neural architecture search, dubbed MR-GNAS, to automatically develop innovative and excellent multi-relational GNN architectures. Specifically, to enlarge search capacities and improve search flexibility, MR-GNAS contains a fine-grained search space that embraces the full-pipe multi-relational message passing schema, enabling expressive architecture search scopes. With the well-designed fine-grained search space, MR-GNAS constructs a relation-aware supernet with a tree topology, to jointly learn discriminative node and relation representations. By searching with a gradient-based strategy in the supernet, the proposed MR-GNAS could derive excellent multi-relational GNN architectures in multi-relational graph analysis. Extensive experiments on entity classification and link prediction tasks over multi-relational graphs illustrate the effectiveness and superiority of the proposed method.

Graph meta-learning which is used to deal with graph few-shot learning attracts more and more research interests. Existing graph meta-learning methods mainly focus on capturing node-level relations, but they ignore task-level relations which are beneficial for improving the performance of few-shot node classification. Furthermore, contrastive learning which can learn knowledge without labeled data is suitable for few-shot scenario, but existing graph few-shot learning methods have never exploited it. To tackle above problems, in this paper, we combine conventional graph meta-learning framework with graph contrastive learning and propose a novel joint model named -${\underline T}$asklevel -${\underline R}$elations Modelling for -${\underline G}$raph ${\underline M}$eta-learning (TRGM). By constructing auxiliary contrastive pretext tasks, TRGM can fully capture the inter-task relations (task correlation and task discrepancy) and promote the primary few-shot learning. Finally, we conduct extensive experiments on six benchmark datasets to validate the effectiveness and efficiency of TRGM. Experimental results show that our model outperforms several strong baselines and achieves the new state-of-the-art.

Recent knowledge graph (KG) embeddings have been advanced by hyperbolic geometry due to its superior capability for representing hierarchies. The topological structures of real-world KGs, however, are rather heterogeneous, i.e., a KG is composed of multiple distinct hierarchies and non-hierarchical graph structures. Therefore, a homogeneous (either Euclidean or hyperbolic) geometry is not sufficient for fairly representing such heterogeneous structures. To capture the topological heterogeneity of KGs, we present an ultrahyperbolic KG embedding (UltraE) in an ultrahyperbolic (or pseudo-Riemannian) manifold that seamlessly interleaves hyperbolic and spherical manifolds. In particular, we model each relation as a pseudo-orthogonal transformation that preserves the pseudo-Riemannian bilinear form. The pseudo-orthogonal transformation is decomposed into various operators (i.e., circular rotations, reflections and hyperbolic rotations), allowing for simultaneously modeling heterogeneous structures as well as complex relational patterns. Experimental results on three standard KGs show that UltraE outperforms previous Euclidean, hyperbolic, and mixed-curvature KG embedding approaches.

Human mobility prediction is of great importance for various applications such as smart transportation and personalized recommender systems. Although many traditional pattern-based methods and deep models ($e.g.,$ recurrent neural networks) based methods have been developed for this task, they essentially do not well cope with the sparsity and inaccuracy of trajectory data and the complicated high-order nature of the sequential dependency, which are typical challenges in mobility prediction. To solve the problems, this paper proposes a novel framework named G raph C onvolutional D ual-a ttentive N etworks (GCDAN), which consists of two modules: spatio-temporal embedding and trajectory encoder-decoder. The first module employs a bidirectional diffusion graph convolution to preserve the spatial dependency in the location embedding. The second module employs a dual-attentive mechanism based on a Sequence to Sequence architecture to effectively extract the long-range sequential dependency within a trajectory and the correlation between different trajectories for predictions. Extensive experiments on three real-world datasets show that GCDAN achieves significant performance gain compared with state-of-the-art baselines.

In the fraud graph, fraudsters often interact with a large number of benign entities to hide themselves. So, there are not only the homophilic connections formed by the same label nodes (similar nodes), but also the heterophilic connections formed by the different label nodes (dissimilar nodes). However, the existing GNN-based fraud detection methods just enhance the homophily in fraud graph and use the low-pass filter to retain the commonality of node features among the neighbors, which inevitably ignore the difference among neighbor of heterophilic connections. To address this problem, we propose a Graph Neural Network-based Fraud Detector with Homophilic and Heterophilic Interactions (H2-FDetector for short). Firstly, we identify the homophilic and heterophilic connections with the supervision of labeled nodes. Next, we design a new information aggregation strategy to make the homophilic connections propagate similar information and the heterophilic connections propagate difference information. Finally, a prototype prior is introduced to guide the identification of fraudsters. Extensive experiments on two real public benchmark fraud detection tasks demonstrate that our method apparently outperforms state-of-the-art baselines.

With the development of e-commerce, fraud behaviors have been becoming one of the biggest threats to the e-commerce business. Fraud behaviors seriously damage the ranking system of e-commerce platforms and adversely influence the shopping experience of users. It is of great practical value to detect fraud behaviors on e-commerce platforms. However, the task is non-trivial, since the adversarial action taken by fraudsters. Existing fraud detection systems used in the e-commerce industry easily suffer from performance decay and can not adapt to the upgrade of fraud patterns, as they take already known fraud behaviors as supervision information to detect other suspicious behaviors. In this article, we propose a competitive graph neural networks (CGNN)-based fraud detection system (eFraudCom) to detect fraud behaviors at one of the largest e-commerce platforms, “Taobao” 1 . In the eFraudCom system, (1) the competitive graph neural networks (CGNN) as the core part of eFraudCom can classify behaviors of users directly by modeling the distributions of normal and fraud behaviors separately; (2) some normal behaviors will be utilized as weak supervision information to guide the CGNN to build the profile for normal behaviors that are more stable than fraud behaviors. The algorithm dependency on fraud behaviors will be eliminated, which enables eFraudCom to detect fraud behaviors in presence of the new fraud patterns; (3) the mutual information regularization term can maximize the separability between normal and fraud behaviors to further improve CGNN. eFraudCom is implemented into a prototype system and the performance of the system is evaluated by extensive experiments. The experiments on two Taobao and two public datasets demonstrate that the proposed deep framework CGNN is superior to other baselines in detecting fraud behaviors. A case study on Taobao datasets verifies that CGNN is still robust when the fraud patterns have been upgraded.

On-demand food delivery (OFD) platforms have greatly impacted the food service industry, where OFD recommendation systems play a central role in enhancing user experience and raising revenues. OFD recommendation, compared with existing online e-commerce recommendation systems, needs to put more emphasis on fulfillment time related variables, because the order fulfillment cycle time (OFCT) which refers to the time elapsed between a user placing a food order and receiving the food significantly influences a user's choice from the recommended items. In this paper, we investigate the OFCT related information and propose a Fulfillment-Time-Aware Personalized Ranking (FTAPR) method for recommendation. FTAPR mainly consists of three components. First, Transformers are used to estimate OFCT based on a large amount of user order sequences. Then, the predicted OFCT and other OFCT related features are fused and encoded by a deep & cross network to learn fulfillment time related feature representation. At the last step, the time bias representation from the deep & cross network is integrated into the ranking system to deliver final search results. Extensive offline and online experiments on real-world datasets collected from one of China's largest OFD platforms Ele.me show the superiority of our model, e.g., an online A/B testing shows that FTAPR brings 1.3% and 2.5% gains in CTR and CVR compared with baselines.

Graph Neural Networks (GNNs) have emerged as a series of effective learning methods for graph-related tasks. However, GNNs are shown vulnerable to adversarial attacks, where attackers can fool GNNs into making wrong predictions on adversarial samples with well-designed perturbations. Specifically, we observe that the current evasion attacks suffer from two limitations: (1) the attack strategy based on the reinforcement learning method might not be transferable when the attack budget changes; (2) the greedy mechanism in the vanilla gradient-based method ignores the long-term benefits of each perturbation operation. In this paper, we propose a new attack method named projective ranking to overcome the above limitations. Our idea is to learn a powerful attack strategy considering the long-term benefits of perturbations, then adjust it as little as possible to generate adversarial samples under different budgets. We further employ mutual information to measure the long-term benefits of each perturbation and rank them accordingly, so the learned attack strategy has better attack performance. Our method dramatically reduces the adaptation cost of learning a new attack strategy by projecting the attack strategy when the attack budget changes. Our preliminary evaluation results in synthesized and real-world datasets demonstrate that our method owns powerful attack performance and effective transferability.

Heterogeneous Graph Neural networks (HGNNs) have been popularly used in processing complicated networks such as academic networks, social networks, and knowledge graphs. Despite their success, the design of the neural architectures of HGNNs still requires rich domain knowledge and heavy manual work. In this paper, we propose a Heterogeneous Graph Neural Architecture Search algorithm (HGNAS for short) which enables automatic design of the best neural architectures with minimal human effort. Specifically, HGNAS first defines a general HGNN framework on top of existing popular HGNNs. A search space of HGNAS is designed based on the general framework that includes multiple groups of message encoding and aggregation functions. Then, HGNAS uses a policy network as the controller to sample and find the best neural architecture from the designed search space by maximizing the expected accuracy of the selected architectures on a validation dataset. Moreover, we introduce effective methods to improve HGNAS from three aspects, i.e., the optimization of hyper-parameters, the improvement of search space, and the selection of message receptive fields. Experiments on public datasets show that HGNAS is capable of designing novel HGNNs that rival the best human-invented HGNNs. More interestingly, HGNAS finds some sparse yet powerful neural architectures for HGNNs on the benchmark datasets.

Multivariate Hawkes processes (MHPs) are classic methods to learn temporal patterns in event sequences of different entities. Traditional MHPs with explicit parametric intensity functions are friendly to model interpretability. However, recent Deep MHPs which employ various variants of recurrent neural networks are hardly to understand, albeit more expressive towards event sequences. The lack of model interpretability of Deep MHPs leads to a limited comprehension of complicated dynamics between events. To this end, we present a new Disentangled Deep Multivariate Hawkes Process $(\mathrm{D}^{2}$ MHP) to enhance model expressiveness and meanwhile maintain model interpretability. $\mathrm{D}^{2}$ MHP achieves state disentanglement by disentangling the latent representation of an event sequence into static and dynamic latent variables, and matches these latent variables to interpretable factors in the intensity function. Moreover, considering that an entity typically has multiple identities, $\mathrm{D}^{2}$ MHP further splits these latent variables into factorized representations, each of which is associated with a corresponding identity. Experiments on real-world datasets show that $\mathrm{D}^{2}$ MHP yields significant and consistent improvements over state-of-the-art baselines. We also demonstrate model interpretability via the detailed analysis.

The objective of fraud detection is to distinguish fraudsters from normal users. In graph/network environments, both fraudsters and normal users are modeled as nodes, and the connections between those nodes are represented as edges. Fraudsters typically try to camouflage themselves with “normal” behaviors, say, by deliberately establishing many connections to normal users. Such camouflage inherently makes their appearance inconsistent with the essence of what it is to be normal, and gives rise to inconsistencies in the graph. In this paper, we investigate three aspects of these graph inconsistencies: features, topologies, and relations. To date, graph-based fraud detectors have shown a rather limited capability to fuse information about different types of inconsistencies. Apart from that, there is another problem of imbalance to overcome. This is because fraudsters usually only account for a very small percentage of all users. To achieve a promising capability, i.e., dual-resistant to graph inconsistency and imbalance, we present a new fraud detection model FRAUDRE based on Graph Neural Networks. Extensive experiments comparing eight up-to-date baselines on two real-world datasets, Amazon and YelpChi, demonstrate the superiority of FRAUDRE.

User cold-start recommendation is a long-standing challenge for recommender systems due to the fact that only a few interactions of cold-start users can be exploited. Recent studies seek to address this challenge from the perspective of meta learning, and most of them follow a manner of parameter initialization, where the model parameters can be learned by a few steps of gradient updates. While these gradient-based meta-learning models achieve promising performances to some extent, a fundamental problem of them is how to adapt the global knowledge learned from previous tasks for the recommendations of cold-start users more effectively.

Graph neural networks (GNNs) have been successfully used to analyze non-Euclidean network data. Recently, there emerge a number of works to investigate the robustness of GNNs by adding adversarial noises into the graph topology, where gradient-based attacks are widely studied due to their inherent efficiency and high effectiveness. However, the gradient-based attacks often lead to sub-optimal results due to the discrete structure of graph data. To this end, we design a novel exploratory adversarial attack (termed as EpoAtk) to boost the gradient-based perturbations on graphs. The exploratory strategy in EpoAtk includes three phases, generation, evaluation and recombination, with the goal of sidesteping the possible misinformation that the maximal gradient provides. In experiments, EpoAtk is evaluated on benchmark datasets for the task of semi-supervised node classification in different attack settings. Experimental results demonstrate that the proposed method significantly outperforms the state-of-the-art attacks with the same attack budgets.

Network representation aims to learn low-dimensional vector representations of network nodes while preserving the inherent properties of the network. For all its popularity, majority of the existing methods focus on exploitation of diverse information, including network topology and semantic information on nodes of network, and ignore their implicit semantics. For example, we all know the saying that birds of a feather flock together. More concretely, semantic information of one node can be influenced by its neighbors' semantic information. Furthermore, even two nodes are not directly connected, they may have similar implicit semantic information (i.e., high-order semantic proximity). Thus, they should be close in the represented vector space. To this end, we propose a Deep Semantic Network Representation approach (DSNR) in the self-translation framework from sequence to sequence. To excavate the implicit semantic information of nodes and capture the high-order semantic proximity, three key components make our approach effective, i.e., aggregation of nodes neighbors' semantic information and enhancement to the semantic feature representations of nodes by a deep autoencoder, integration of nodes semantic information in node identity sequence to generate node semantic sequence, and translation from node semantic sequence to node identity sequence to capture the high-order semantic proximity in an attention-enhanced seq2seq framework. Extensive experiments based on three real-world datasets have verified the effectiveness of our proposed approach11Code is available at https://github.com/DASE4/DSNR.

Trust relationship prediction among people provides valuable supports for decision making, information dissemination, and product promotion in online social networks. Network embedding has achieved promising performance for link prediction by learning node representations that encode intrinsic network structures. However, most of the existing network embedding solutions cannot effectively capture the properties of a trust network that has directed edges and nodes with in/out links. Furthermore, there usually exist rich user attributes in trust networks, such as ratings, reviews, and the rated/reviewed items, which may exert significant impacts on the formation of trust relationships. It is still lacking a network embedding-based method that can adequately integrate these properties for trust prediction. In this work, we develop an AtNE-Trust model to address these issues. We firstly capture user embedding from both the trust network structures and user attributes. Then we design a deep multi-view representation learning module to further mine and fuse the obtained user embedding. Finally, a trust evaluation module is developed to predict the trust relationships between users. Representation learning and trust evaluation are optimized together to capture high-quality user embedding and make accurate predictions simultaneously. A set of experiments against the real-world datasets demonstrates the effectiveness of the proposed approach.

Graph convolutional networks (GCNs) have achieved impressive success in many graph related analytics tasks. However, most GCNs only work in a single domain (graph) incapable of transferring knowledge from/to other domains (graphs), due to the challenges in both graph representation learning and domain adaptation over graph structures. In this paper, we present a novel approach, unsupervised domain adaptive graph convolutional networks (UDA-GCN), for domain adaptation learning for graphs. To enable effective graph representation learning, we first develop a dual graph convolutional network component, which jointly exploits local and global consistency for feature aggregation. An attention mechanism is further used to produce a unified representation for each node in different graphs. To facilitate knowledge transfer between graphs, we propose a domain adaptive learning module to optimize three different loss functions, namely source classifier loss, domain classifier loss, and target classifier loss as a whole, thus our model can differentiate class labels in the source domain, samples from different domains, the class labels from the target domain, respectively. Experimental results on real-world datasets in the node classification task validate the performance of our method, compared to state-of-the-art graph neural network algorithms.

Cross-lingual Entity Alignment (CEA) aims at identifying entities with their counterparts in different language knowledge graphs. Knowledge embedding alignment plays an important role in CEA due to its advantages of easy implementation and run-time robustness. However, existing embedding alignment methods haven't considered the problem of embedding distribution alignment which refers to the alignment of spatial shapes of embedding spaces. To this end, we present a new Adversarial Knowledge Embedding framework (AKE for short) that jointly learns the representation, mapping and adversarial modules in an end-to-end manner. By reducing the discrepancy of embedding distributions, AKE can approximately preserve an isomorphism between source and target embeddings. In addition, we introduce two new orthogonality constraints into mapping to obtain the self-consistency and numerical stability of transformation. Experiments on real-world datasets demonstrate that our method significantly outperforms state-of-the-art baselines.

Text classification, in cross-domain setting, is a challenging task. On the one hand, data from other domains are often useful to improve the learning on the target domain; on the other hand, domain variance and hierarchical structure of documents from words, key phrases, sentences, paragraphs, etc. make it difficult to align domains for effective learning. To date, existing cross-domain text classification methods mainly strive to minimize feature distribution differences between domains, and they typically suffer from three major limitations - (1) difficult to capture semantics in non-consecutive phrases and long-distance word dependency because of treating texts as word sequences, (2) neglect of hierarchical coarse-grained structures of document for feature learning, and (3) narrow focus of the domains at instance levels, without using domains as supervisions to improve text classification. This paper proposes an end-to-end, domain-adversarial graph neural networks (DAGNN), for cross-domain text classification. Our motivation is to model documents as graphs and use a domain-adversarial training principle to lean features from each graph (as well as learning the separation of domains) for effective text classification. At the instance level, DAGNN uses a graph to model each document, so that it can capture non-consecutive and long-distance semantics. At the feature level, DAGNN uses graphs from different domains to jointly train hierarchical graph neural networks in order to learn good features. At the learning level, DAGNN proposes a domain-adversarial principle such that the learned features not only optimally classify documents but also separates domains. Experiments on benchmark datasets demonstrate the effectiveness of our method in cross-domain classification tasks.

Heterogeneous graphs with different types of nodes and edges are ubiquitous and have immense value in many applications. Existing works on modeling heterogeneous graphs usually follow the idea of splitting a heterogeneous graph into multiple homogeneous subgraphs. This is ineffective in exploiting hidden rich semantic associations between different types of edges for large-scale multi-relational graphs. In this paper, we propose Relation Structure-Aware Heterogeneous Graph Neural Network (RSHN), a unified model that integrates graph and its coarsened line graph to embed both nodes and edges in heterogeneous graphs without requiring any prior knowledge such as metapath. To tackle the heterogeneity of edge connections, RSHN first creates a Coarsened Line Graph Neural Network (CL-GNN) to excavate edge-centric relation structural features that respect the latent associations of different types of edges based on coarsened line graph. After that, a Heterogeneous Graph Neural Network (H-GNN) is used to leverage implicit messages from neighbor nodes and edges propagating among nodes in heterogeneous graphs. As a result, different types of nodes and edges can enhance their embedding through mutual integration and promotion. Experiments and comparisons, based on semi-supervised classification tasks on large scale heterogeneous networks with over a hundred types of edges, show that RSHN significantly outperforms state-of-the-arts.

Unlabeled, multi-view data presents a considerable challenge in many real-world data analysis tasks. These data are worth exploring because they often contain complementary information that improves the quality of the analysis results. Clustering with multi-view data is a particularly challenging problem as revealing the complex data structures between many feature spaces demands discriminative features that are specific to the task and, when too few of these features are present, performance suffers. Extreme learning machines (ELMs) are an emerging form of learning model that have shown an outstanding representation ability and superior performance in a range of different learning tasks. Motivated by the promise of this advancement, we have developed a novel multi-view fusion clustering framework based on an ELM, called MVEC. MVEC learns the embeddings from each view of the data via the ELM network, then constructs a single unified embedding according to the correlations and dependencies between each embedding and automatically weighting the contribution of each. This process exposes the underlying clustering structures embedded within multi-view data with a high degree of accuracy. A simple yet efficient solution is also provided to solve the optimization problem within MVEC. Experiments and comparisons on eight different benchmarks from different domains confirm MVEC’s clustering accuracy.

Fraud detection is of great importance because fraudulent behaviors may mislead consumers or bring huge losses to enterprises. Due to the lockstep feature of fraudulent behaviors, fraud detection problem can be viewed as finding suspicious dense blocks in the attributed bipartite graph. In reality, existing attribute-based methods are not adversarially robust, because fraudsters can take some camouflage actions to cover their behavior attributes as normal. More importantly, existing structural information based methods only consider shallow topology structure, making their effectiveness sensitive to the density of suspicious blocks. In this paper, we propose a novel deep structure learning model named DeepFD to differentiate normal users and suspicious users. DeepFD can preserve the non-linear graph structure and user behavior information simultaneously. Experimental results on different types of datasets demonstrate that DeepFD outperforms the state-of-the-art baselines.

In event-based social networks, such as Meetup, social groups refer to self-organized communities that consist of users who share the same interests. In many real-world scenarios, users usually have social group preference and join interested social groups to attend events. It is therefore necessary to consider the influence of social groups to improve the event recommendation performance; however, existing event recommendation models generally consider users' individual preferences and neglect the influence of social groups. To this end, we propose a new Bayesian latent factor model SogBmf that combines social group influence and individual preference for event recommendation. Experiments on real-world data sets demonstrate the effectiveness of the proposed method.

In this paper we study the friend recommendation problem in event-based social networks (EBSNs). Effective friend recommendation is of benefit to EBSNs, since it can promote user interaction and accelerate information diffusion for promoted events. Different from usual friend recommendations, the aim of making friends in EBSNs is to better participate offline events and enhance user experience. Meanwhile friend recommendation in EBSNs encounters three types of data, i.e. geographical information, implicate user rating, and user behavior. These differences imply that existing friend recommendation approaches are not adequate any more for EBSNs. Under this background, in this paper we propose a Bayesian latent factor model, which can jointly formulate above three types of data, for friend recommendation with better event promotion and user experience. Results on real-world datasets show the efficacy of our approach.

The problem of modeling topics on user behavior data in social networks has been widely studied in social marketing and social emotion analysis, where latent topic models are commonly used as the solutions. The user behavior data are highly related in time and space, which demands new latent topic models that consider both temporal and spatial distances. However, existing topic models either fail to model these two factors simultaneously, or cannot handle the high order dependence among user behaviors. In this paper we present a new nonparametric Bayesian model Time and Space Dependent Chinese Restaurant Processes (TSD-CRP for short). TSD-CRP can auto-select the number of topics and model high-order temporal and spatial dependence behind user behavior data. Empirical results on real-world data sets demonstrate the effectiveness of the proposed method.

Ensemble learning is a common tool for data stream classification, mainly because of its inherent advantages of handling large volumes of stream data and concept drifting. Previous studies, to date, have been primarily focused on building accurate ensemble models from stream data. However, a linear scan of a large number of base classifiers in the ensemble during prediction incurs significant costs in response time, preventing ensemble learning from being practical for many real-world time-critical data stream applications, such as Web traffic stream monitoring, spam detection, and intrusion detection. In these applications, data streams usually arrive at a speed of GB/second, and it is necessary to classify each stream record in a timely manner. To address this problem, we propose a novel Ensemble-tree (E-tree for short) indexing structure to organize all base classifiers in an ensemble for fast prediction. On one hand, E-trees treat ensembles as spatial databases and employ an R-tree like height-balanced structure to reduce the expected prediction time from linear to sub-linear complexity. On the other hand, E-trees can be automatically updated by continuously integrating new classifiers and discarding outdated ones, well adapting to new trends and patterns underneath data streams. Theoretical analysis and empirical studies on both synthetic and real-world data streams demonstrate the performance of our approach.

Influence maximization, defined as finding a small subset of nodes that maximizes spread of influence in social networks, is NP-hard under both Independent Cascade (IC) and Linear Threshold (LT) models, where many greedy-based algorithms have been proposed with the best approximation guarantee. However, existing greedy-based algorithms are inefficient on large networks, as it demands heavy Monte-Carlo simulations of the spread functions for each node at the initial step [7]. In this paper, we establish new upper bounds to significantly reduce the number of Monte-Carlo simulations in greedy-based algorithms, especially at the initial step. We theoretically prove that the bound is tight and convergent when the summation of weights towards (or from) each node is less than 1. Based on the bound, we propose a new Upper Bound based Lazy Forward algorithm (UBLF in short) for discovering the top-k influential nodes in social networks. We test and compare UBLF with prior greedy algorithms, especially CELF [30]. Experimental results show that UBLF reduces more than 95 percent Monte-Carlo simulations of CELF and achieves about 2-10 times speedup when the seed set is small.

Max-margin matrix factorization (M3F) has been popularly applied to collaborative filtering for personalized recommendations. The nonparametric M3F model represents the latest progress of the M3F methods, which can auto-select the number of factors by using nonparametric techniques. However, existing non-parametric M3F methods assume a collection of user rating data can be fully obtained before training, and they are inapplicable for on-the-fly recommender systems where user rating data arrive continuously. In this paper, we present a new efficient online nonparametric 3F model for flexible recommendation. Specifically, we design an online nonparametric M3F model (OnM3F) based on the online Passive-Aggressive learning and solve the corresponding optimization problem by using the online stochastic gradient descent. Empirical studies on two large real-world data sets verify the effectiveness of the proposed method.

In this paper, we study a new problem on social network influence maximization. The problem is defined as, given a target user $w$, finding the top-k most influential nodes for the user. Different from existing influence maximization works which aim to find a small subset of nodes to maximize the spread of influence over the entire network (i.e., global optima), our problem aims to find a small subset of nodes which can maximize the influence spread to a given target user (i.e., local optima). The solution is critical for personalized services on social networks, where fully understanding of each specific user is essential. Although some global influence maximization models can be narrowed down as the solution, these methods often bias to the target node itself. To this end, in this paper we present a local influence maximization solution. We first provide a random function, with low variance guarantee, to randomly simulate the objective function of local influence maximization. Then, we present efficient algorithms with approximation guarantee. For online social network applications, we also present a scalable approximate algorithm by exploring the local cascade structure of the target user. We test the proposed algorithms on several real-world social networks. Experimental results validate the performance of the proposed algorithms.

Influence maximization, defined as finding a small subset of nodes that maximizes spread of influence in social networks, is NP-hard under both Linear Threshold (LT) and Independent Cascade (IC) models, where a line of greedy/heuristic algorithms have been proposed. The simple greedy algorithm [14] achieves an approximation ratio of 1-1/e. The advanced CELF algorithm [16], by exploiting the sub modular property of the spread function, runs 700 times faster than the simple greedy algorithm on average. However, CELF is still inefficient [4], as the first iteration calls for N times of spread estimations (N is the number of nodes in networks), which is computationally expensive especially for large networks. To this end, in this paper we derive an upper bound function for the spread function. The bound can be used to reduce the number of Monte-Carlo simulation calls in greedy algorithms, especially in the first iteration of initialization. Based on the upper bound, we propose an efficient Upper Bound based Lazy Forward algorithm (UBLF in short), by incorporating the bound into the CELF algorithm. We test and compare our algorithm with prior algorithms on real-world data sets. Experimental results demonstrate that UBLF, compared with CELF, reduces more than 95% Monte-Carlo simulations and achieves at least 2-5 times speed-raising when the seed set is small.