Graph anomaly detection (GAD), which aims to detect outliers in graph-structured data, has received increasing research attention recently. However, existing GAD methods assume identical training and testing distributions, which is rarely valid in practice. In real-world scenarios, unseen but normal samples may emerge during deployment, leading to a normality shift that degrades the performance of GAD models trained on the original data. Through empirical analysis, we reveal that the degradation arises from (1) semantic confusion, where unseen normal samples are misinterpreted as anomalies due to their novel patterns, and (2) aggregation contamination, where the representations of seen normal nodes are distorted by unseen normals through message aggregation. While retraining or fine-tuning GAD models could be a potential solution to the above challenges, the high cost of model retraining and the difficulty of obtaining labeled data often render this approach impractical in real-world applications. To bridge the gap, we proposed a lightweight and plug-and-play Test-time adaptation framework for correcting Unseen Normal pattErns (TUNE) in GAD. To address semantic confusion, a graph aligner is employed to align the shifted data to the original one at the graph attribute level. Moreover, we utilize the minimization of representation-level shift as a supervision signal to train the aligner, which leverages the estimated aggregation contamination as a key indicator of normality shift. Extensive experiments on 10 real-world datasets demonstrate that TUNE significantly enhances the generalizability of pre-trained GAD models to both synthetic and real unseen normal patterns.

Yongxuan Wu, Xixun Lin, He Zhang, Nan Sun, Kun Wang, Chuan Zhou, Shirui Pan, Yanan Cao. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Multi-task learning (MTL) is a standard learning paradigm in machine learning. The central idea of MTL is to capture the shared knowledge among multiple tasks for mitigating the problem of data sparsity where the annotated samples for each task are quite limited. Recent studies indicate that graph multi-task learning (GMTL) yields the promising improvement over previous MTL methods. GMTL represents tasks on a task relation graph, and further leverages graph neural networks (GNNs) to learn complex task relationships. Although GMTL achieves the better performance, the construction of task relation graph heavily depends on simple heuristic tricks, which results in the existence of spurious task correlations and the absence of true edges between tasks with strong connections. This problem largely limits the effectiveness of GMTL. To this end, we propose the Generative Causality-driven Network (GCNet), a novel framework that progressively learns the causal structure between tasks to discover which tasks are beneficial to be jointly trained for improving generalization ability and model robustness. To be specific, in the feature space, GCNet first introduces a feature-level generator to generate the structure prior for reducing learning difficulty. Afterwards, GCNet develops a output-level generator which is parameterized as a new causal energy-based model (EBM) to refine the learned structure prior in the output space driven by causality. Benefiting from our proposed causal framework, we theoretically derive an intervention contrastive estimation for training this causal EBM efficiently. Experiments are conducted on multiple synthetic and real-world datasets. Extensive empirical results and model analyses demonstrate the superior performance of GCNet over several competitive MTL baselines.

Brain graphs (brain connectivity networks) play an important role in modeling the complex structure of the human brain. Furthermore, brain graph learning based on graph neural networks (GNNs) has recently attracted growing interest. Although existing methods have made great progress in brain disorder prediction and pathogenic analysis, there are two key problems: (1) They rarely utilize the pathogenic reason of brain disorders, that is, salient brain regions always lead to abnormal connections between brain regions, to extract critical brain graph information for disorder analysis; (2) Since most of the available brain graph data is limited, how can we improve the performance of brain graph learning models on insufficient training data? Thus, in this paper, we learn brain graph representations for disorder prediction and analyze disorder-specific brain regions and connections from the subgraph perspective. Besides, we introduce the cross-domain brain graph learning framework to alleviate the problem of poor model performance on limited data. To consider the pathogenic reason by brain subgraphs, we first propose the node entropy of brain graphs based on brain graph properties to extract important nodes. We then introduce subgraph information bottleneck to refine the critical subgraph from the rough subgraph generated by these important nodes, recognizing important connections related to disorders. To achieve a better model performance on limited data, we design a cross-domain brain graph learning framework to improve the subgraph extraction model by the meta-learning method. The subgraph extraction model is pre-trained on a large source training dataset and then quickly adapted to target task dataset. Besides, a simple yet effective feature alignment module is applied to mitigate the negative transfer problem for cross-domain datasets. Extensive experimental results, including disorder prediction and pathogenic analysis on real-world neuroimaging data, demonstrate the effectiveness of our method.

Heterogeneous graphs are increasingly used to represent complex real-world scenarios with diverse entities and interactions by meta structures. Recently, the search of meta structures is combined with graph neural architecture search to automatically extract the semantic knowledge for various tasks in heterogeneous graphs. However, prior research primarily focuses on identifying meta structures that are universally applicable across all nodes in a graph, neglecting the variations in meta structure selection that arise from the unique features and topology of individual nodes. To address this challenge, we introduce a Node-Centric approach to search Meta Structures in heterogeneous graphs (NC-MS for short). NC-MS implements a node level method that discover meaningful meta structures tailored to each node, capturing subtle differences in meta structure choices between nodes and providing nuanced identification. Additionally, NC-MS utilizes an efficient and differentiable network to enhance operational efficiency. Empirical studies across three real-world datasets validate the superiority of NC-MS, demonstrating its ability to outperform existing models in heterogeneous graph neural networks.

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.

In this work, we address the test-time adaptation challenge in graph neural networks (GNNs), focusing on overcoming the limitations in flexibility and generalization inherent in existing data-centric approaches. To this end, we propose a novel research problem, test-time graph neural dataset search, which seeks to learn a parameterized test-time graph distribution to enhance the inference performance of unseen test graphs on well-trained GNNs. Specifically, we propose a generative Projection based test-time Graph Neural Dataset Search method, named PGNDS, which maps the unseen test graph distribution back to the known training distribution through a generation process guided by well-trained GNNs. The proposed PGNDS framework consists of three key modules: (1) dual conditional diffusion for GNN-guided generative projection through test-back-to-training distribution mapping; (2) dynamic search from the generative sampling space to select the most expressive test graphs; (3) ensemble inference to aggregate information from original and adapted test graphs. Extensive experiments on real-world graphs demonstrate the superior ability of our proposed PGNDS for improved test-time GNN inference.

Anomaly detection in continuous-time event sequences is a crucial task in safety-critical applications. While existing methods primarily focus on developing a superior test statistic, they fail to provide guarantees regarding the false positive rate (FPR), which undermines their reliability in practical deployments. In this paper, we propose CADES (Conformal Anomaly Detection in Event Sequences), a novel test procedure based on conformal inference for the studied task with finite-sample FPR control. Specifically, by using the time-rescaling theorem, we design two powerful non-conformity scores tailored to event sequences, which exhibit complementary sensitivities to different abnormal patterns. CADES combines these scores with Bonferroni correction to leverage their respective strengths and addresses non-identifiability issues of existing methods. Theoretically, we prove the validity of CADES and further provide strong guarantees on calibration-conditional FPR control. Experimental results on synthetic and real-world datasets, covering various types of anomalies, demonstrate that CADES outperforms state-of-the-art methods while maintaining FPR control.

Graph Transformers (GTs) have emerged as powerful tools for handling graph-structured data through global attention mechanisms. While GTs can effectively capture long-range dependencies, they introduce difficulties in optimization due to their complex, non-differentiable operators, which cannot be directly handled by standard gradient-based optimizers (such as Adam or AdamW). To investigate the above issues, this work adopts the line of Zeroth-Order Optimization (ZOO) technique. However, direct integration of ZOO incurs considerable challenges due to the sharp loss landscape and steep gradients within the GT parameter space. Under the above observations, we propose a Sharpness-aware Zeroth-order Optimizer (SZO) that combines Sharpness-Aware Minimization (SAM) technique facilitating convergence within a flatter neighborhood, and leverages parallel computing for efficient gradient estimation. Theoretically, we provide a comprehensive analysis of the optimizer from both convergence and generalization perspectives. Empirically, we conduct extensive experiments on various classical GTs across a wide range of benchmark datasets, which underscore the superior performance of SZO over the state-of-the-art optimizers.

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.

The human brain is a highly complex neurological system that has been the subject of continuous exploration by scientists. With the help of modern neuroimaging techniques, there has been significant progress made in brain disorder analysis. There is an increasing interest about utilizing artificial intelligence techniques to improve the efficiency of disorder diagnosis in recent years. However, these methods rely only on neuroimaging data for disorder diagnosis and do not explore the pathogenic mechanism behind the disorder or provide an interpretable result toward the diagnosis decision. Furthermore, the scarcity of medical data limits the performance of existing methods. As the hot application of graph neural networks (GNNs) in molecular graphs and drug discovery due to its strong graph-structured data learning ability, whether GNNs can also play a huge role in the field of brain disorder analysis. Thus, in this work, we innovatively model brain neuroimaging data into graph-structured data and propose knowledge distillation (KD) guided brain subgraph neural networks to extract discriminative subgraphs between patient and healthy brain graphs to explain which brain regions and abnormal functional connectivities cause the disorder. Specifically, we introduce the KD technique to transfer the knowledge of pretrained teacher model to guide brain subgraph neural networks training and alleviate the problem of insufficient training data. And these discriminative subgraphs are conducive to learn better brain graph-level representations for disorder prediction. We conduct abundant experiments on two functional magnetic resonance imaging datasets, i.e., Parkinson's disease (PD) and attention-deficit/hyperactivity disorder (ADHD), and experimental results well demonstrate the superiority of our method over other brain graph analysis methods for disorder prediction accuracy. The interpretable experimental results given by our method are consistent with corresponding medical research, which is encouraging to provide a potential for deeper brain disorder study.

E-commerce platforms heavily rely on the wide range of products they offer. Detecting communities within these products is essential for efficient risk management and personalized recommendations. In this paper, we introduce a novel framework that utilizes unsupervised pre-trained social network computing methods to detect communities in e-commerce products. Our key technical contribution lies in capturing domain-specific knowledge from academic social networks during the pre-training phase, which is then transferred to the fine-tuning process of the unsupervised e-commerce product graph model. The framework begins with both unsupervised and supervised pre-training modules, conducting masked graph modeling and node classification tasks on academic social networks. Following this, the pre-trained graph autoencoder is fine-tuned on new datasets. In the final stage, graph clustering on node embeddings is performed using an ensemble method of fast K-means algorithms. We evaluate the proposed framework on large-scale real-world datasets from Amazon’s e-commerce platform. Results demonstrate that our method significantly outperforms other classical benchmark methods, leading the second-best by over 10% in adjusted Rand index, and discovering more than 500 subgraphs in the large-scale e-commerce network.

Recently link weight prediction has attracted an increasing research interest due to its merits in quantifying the strength between nodes within a graph. Nonetheless, current link weight prediction methods focus solely on graph topology, disregarding node feature information embedded in graphs. In real-world applications, we often collect heterogeneous graph data where multiple types of nodes linked by multiple types of edges are available for analysis, and it is essential and challenging to quantify the proximity of different types of nodes. To solve this challenge, we present a new model for Heterogeneous Graph Link Weight Prediction (HLWP for short). In HLWP, message passing in heterogeneous graph neural networks is described as a meta structure, which can be effectively designed by Differentiable Neural Architecture Search (DARTS) algorithms. Thus, HLWP can enhance the message passing in heterogeneous graphs by DARTS. In addition, HLWP employs a perturbation-based algorithm to enhance stability and precision. Through empirical experiments conducted on three real-world datasets, we demonstrate that HLWP achieves accurate predictions of link weights. Our results highlight the superiority of HLWP over existing methods for link weight prediction and baseline GNN models in terms of accurately predicting link weights within heterogeneous graphs.

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.

Graph neural networks (GNNs) have advanced the state of the art in various domains. Despite their remarkable success, the uncertainty estimation of GNN predictions remains under-explored, which limits their practical applications especially in risk-sensitive areas. Current works suffer from either intractable posteriors or inflexible prior specifications, leading to sub-optimal empirical results. In this paper, we present graph neural stochastic diffusion (GNSD), a novel framework for estimating predictive uncertainty on graphs by establishing theoretical connections between GNNs and stochastic partial differential equation. GNSD represents a GNN-based parameterization of the proposed graph stochastic diffusion equation which includes a $Q$-Wiener process to model the stochastic evolution of node representations. GNSD introduces a drift network to guarantee accurate prediction and a stochastic forcing network to model the propagation of epistemic uncertainty among nodes. Extensive experiments are conducted on multiple detection tasks, demonstrating that GNSD yields the superior performance over existing strong approaches.

We present a novel perspective on temporal point processes (TPPs) by reformulating their intensity processes as solutions to stochastic differential equations (SDEs). In particular, we first prove the equivalent SDE formulations of several classical TPPs, including Poisson processes, Hawkes processes, and self-correcting processes. Based on these proofs, we introduce a unified TPP framework called Neural Jump-Diffusion Temporal Point Process (NJDTPP), whose intensity process is governed by a neural jump-diffusion SDE (NJDSDE) where the drift, diffusion, and jump coefficient functions are parameterized by neural networks. Compared to previous works, NJDTPP exhibits model flexibility in capturing intensity dynamics without relying on any specific functional form, and provides theoretical guarantees regarding the existence and uniqueness of the solution to the proposed NJDSDE. Experiments on both synthetic and real-world datasets demonstrate that NJDTPP is capable of capturing the dynamics of intensity processes in different scenarios and significantly outperforms the state-of-the-art TPP models in prediction tasks.

The concept of the sharing economy has gained broad recognition, and within this context, Sharing E-Bike Battery (SEB) have emerged as a focal point of societal interest. Despite the popularity, a notable discrepancy remains between user expectations regarding the remaining battery range of SEBs and the reality, leading to a pronounced inclination among users to find an available SEB during emergency situations. In response to this challenge, the integration of Artificial Intelligence of Things (AIoT) and battery-swap services has surfaced as a viable solution. In this paper, we propose a novel structural Transformer-based model, referred to as the SEB-Transformer, designed specifically for predicting the battery range of SEBs. The scenario is conceptualized as a dynamic heterogeneous graph that encapsulates the interactions between users and bicycles, providing a comprehensive framework for analysis. Furthermore, we incorporate the graph structure into the SEB-Transformer to facilitate the estimation of the remaining e-bike battery range, in conjunction with mean structural similarity, enhancing the prediction accuracy. By employing the predictions made by our model, we are able to dynamically adjust the optimal cycling routes for users in real-time, while also considering the strategic locations of charging stations, thereby optimizing the user experience. Empirically our results on real-world datasets demonstrate the superiority of our model against nine competitive baselines. These innovations, powered by AIoT, not only bridge the gap between user expectations and the physical limitations of battery range but also significantly improve the operational efficiency and sustainability of SEB services. Through these advancements, the shared electric bicycle ecosystem is evolving, making strides towards a more reliable, user-friendly, and sustainable mode of transportation.

In the context of privacy-aware social web services, secure causal reasoning on graphs is an essential task, for example, identifying the key influential nodes/users through which information, ideas, trends spread across the network. Despite the significant advancements achieved by neural network-based methods in these domains, existing research often assumes complete observable of graph data, an assumption that conflicts with privacy concerns in social web services. This assumption may not hold in numerous real-world social analysis applications due to privacy restrictions. In such scenarios, some graph links might remain unobserved until the model is trained, posing a critical challenge for privacy preservation. To address this issue, we introduce a novel model named Causal Effect on Coarsened Graphs (Cecoar), which is specifically designed for privacy-aware social web services. This model employs a new type of coarsened graph that accurately represents partially observed nodes and edges, aligning with the privacy constraints of social web services. We have developed three crucial modules to enable causal estimation on coarsened graphs: (1) a graph sampling module, (2) a confounder encoder, and (3) a graph-based encoder with causal prediction layers. Furthermore, we present a comprehensive theoretical analysis of the proposed model, demonstrating its performance and generalization capabilities. We evaluate our model on two benchmark datasets for causal estimation, and the results confirm its effectiveness in handling graph data containing private information. The code is in https://github.com/liu-yang-maker/Cecoar-ICWS24.

Message passing (MP) is crucial for effective graph neural networks (GNNs). Most local message-passing schemes have been shown to underperform on heterophily graphs due to the perturbation of updated representations caused by local redundant heterophily information. However, our experiment findings indicate that the distribution of heterophily information during MP can be disrupted by disentangling local neighborhoods. This finding can be applied to other GNNs, improving their performance on heterophily graphs in a more flexible manner compared to most heterophily GNNs with complex designs. This article proposes a new type of simple message-passing neural network called Flow2GNN. It uses a two-way flow message-passing scheme to enhance the ability of GNNs by disentangling and redistributing heterophily information in the topology space and the attribute space. Our proposed message-passing scheme consists of two steps in topology space and attribute space. First, we introduce a new disentangled operator with binary elements that disentangle topology information in-flow and out-flow between connected nodes. Second, we use an adaptive aggregation model that adjusts the flow amount between homophily and heterophily attribute information. Furthermore, we rigorously prove that disentangling in message-passing can reduce the generalization gap, offering a deeper understanding of how our model enhances other GNNs. The extensive experiment results show that the proposed model, Flow2GNN, not only outperforms state-of-the-art GNNs, but also helps improve the performance of other commonly used GNNs on heterophily graphs, including GCN, GAT, GCNII, and H2GCN, specifically for GCN, with up to a 25.88% improvement on the Wisconsin dataset.

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.

Representation learning based on dynamic graphs has received a lot of attention in recent years due to its wide range of application scenarios. Although many discrete or continuous dynamic graph representation learning methods have been proposed, many of them ignore the role of edge types. Through the observation of dynamic graphs in the real world, it is found that the types of various edges are very different in nature. They are roughly divided into two categories according to the frequency of occurrence: evolutive edges that appear infrequently and interactive edges that appear frequently. For both types of edges, we propose a coupling-process model (DyCPM) to capture the dynamic mechanisms of them. The model not only generates low-dimensional embedding vectors of nodes, but also aggregates the structural information and temporal information of two kinds of edges. In particular, we design a neural network parameterized discrete process to depict the change law of the topology of evolutive edges and a neural network parameterized temporal point process (TPP) to characterize the temporal dynamic rule of interactive edges. More importantly, we propose a coupling mechanism to transfer the information of the two processes through a shared embedding matrix and finally generate an embedding matrix that aggregates the topology information and temporal information of the two kinds of edges for the dynamic link prediction task. We evaluate our model and several baselines on real datasets. The experimental results show that our model can better aggregate the topology information and temporal information of the two kinds of edges according to their properties and outperforms several state-of-the-art baselines in the performance of dynamic link prediction.

Graph classification plays an important role in a wide range of applications from biological prediction to social analysis. Traditional graph classification models built on graph kernels are hampered by the challenge of poor generalization as they are heavily dependent on the dedicated design of handcrafted features. Recently, graph neural networks (GNNs) become a new class of tools for analyzing graph data and have achieved promising performance. However, it is necessary to collect a large number of labeled graph data for training an accurate GNN, which is often unaffordable in real-world applications. Therefore, it is an open question to build GNNs under the condition of few-shot learning where only a few labeled graphs are available. In this article, we introduce a new Structure-aware Prototypical Neural Process (SPNP for short) for a few-shot graph classification. Specifically, at the encoding stage, SPNP first employs GNNs to capture graph structure information. Then, SPNP incorporates such structural priors into the latent path and the deterministic path for representing stochastic processes. At the decoding stage, SPNP uses a new prototypical decoder to define a metric space where unseen graphs can be predicted effectively. The proposed decoder, which contains a self-attention mechanism to learn the intraclass dependence between graphs, can enhance the class-level representations, especially for new classes. Furthermore, benefited from such a flexible encoding-decoding architecture, SPNP can directly map the context samples to a predictive distribution without any complicated operations used in previous methods. Extensive experiments demonstrate that SPNP achieves consistent and significant improvements over state-of-the-art methods. Further discussions are provided toward model efficiency and more detailed analysis.

Detecting a community in a network is a matter of discerning the distinct features and connections of a group of members that are different from those in other communities. The ability to do this is of great significance in network analysis. However, beyond the classic spectral clustering and statistical inference methods, there have been significant developments with deep learning techniques for community detection in recent years-particularly when it comes to handling high-dimensional network data. Hence, a comprehensive review of the latest progress in community detection through deep learning is timely. To frame the survey, we have devised a new taxonomy covering different state-of-the-art methods, including deep learning models based on deep neural networks (DNNs), deep nonnegative matrix factorization, and deep sparse filtering. The main category, i.e., DNNs, is further divided into convolutional networks, graph attention networks, generative adversarial networks, and autoencoders. The popular benchmark datasets, evaluation metrics, and open-source implementations to address experimentation settings are also summarized. This is followed by a discussion on the practical applications of community detection in various domains. The survey concludes with suggestions of challenging topics that would make for fruitful future research directions in this fast-growing deep learning field.

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.

Evaluating the performance of graph neural networks (GNNs) is an essential task for practical GNN model deployment and serving, as deployed GNNs face significant performance uncertainty when inferring on unseen and unlabeled test graphs, due to mismatched training-test graph distributions. In this paper, we study a *new* problem, **GNN model evaluation**, that aims to assess the performance of a specific GNN model trained on labeled and observed graphs, by precisely estimating its performance (e.g., node classification accuracy) on unseen graphs without labels. Concretely, we propose a two-stage GNN model evaluation framework, including (1) DiscGraph set construction and (2) GNNEvaluator training and inference. The DiscGraph set captures wide-range and diverse graph data distribution discrepancies through a discrepancy measurement function, which exploits the GNN outputs of latent node embeddings and node class predictions. Under the effective training supervision from the DiscGraph set, GNNEvaluator learns to precisely estimate node classification accuracy of the to-be-evaluated GNN model and makes an accurate inference for evaluating GNN model performance. Extensive experiments on real-world unseen and unlabeled test graphs demonstrate the effectiveness of our proposed method for GNN model evaluation.

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.

Classification methods for streaming data are not new, but very few current frameworks address all three of the most common problems with these tasks: concept drift, noise, and the exorbitant costs associated with labeling the unlabeled instances in data streams. Motivated by this gap in the field, we developed an active learning framework based on a dual-query strategy and Ebbinghaus's law of human memory cognition. Called CogDQS, the query strategy samples only the most representative instances for manual annotation based on local density and uncertainty, thus significantly reducing the cost of labeling. The policy for discerning drift from noise and replacing outdated instances with new concepts is based on the three criteria of the Ebbinghaus forgetting curve: recall, the fading period, and the memory strength. Simulations comparing CogDQS with baselines on six different data streams containing gradual drift or abrupt drift with and without noise show that our approach produces accurate, stable models with good generalization ability at minimal labeling, storage, and computation costs.

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.

Relational triplet extraction (RTE) is a fundamental task for automatically extracting information from unstructured text, which has attracted growing interest in recent years. However, it remains challenging due to the difficulty in extracting the overlapping relational triplets. Existing approaches for overlapping RTE, either suffer from exposure bias or designing complex tagging scheme. In light of these limitations, we take an innovative perspective on RTE by modeling it as a word linking problem that learns to link from subject words to object words for each relation type. To this end, we propose a simple but effective multi-task learning model, WLinker, which can extract overlapping relational triplets in an end-to-end fashion. Specifically, we perform word link prediction based on multi-level biaffine attention for leaning the word-level correlations under each relation type. Additionally, our model joint entity detection and word link prediction tasks by a multi-task framework, which combines the local sequential and global dependency structures of words in sentence and captures the implicit interactions between the two tasks. Extensive experiments are conducted on two benchmark datasets NYT and WebNLG. The results demonstrate the effectiveness of WLinker, in comparison with a range of previous state-of-the-art baselines.

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.

Graph Convolutional Networks (GCNs) are powerful frameworks for learning embeddings of graph-structured data. GCNs are traditionally studied through the lens of Euclidean geometry. Recent works find that non-Euclidean Riemannian manifolds provide specific inductive biases for embedding hierarchical or spherical data. However, they cannot align well with data of mixed graph topologies. We consider a larger class of pseudo-Riemannian manifolds that generalize hyperboloid and sphere. We develop new geodesic tools that allow for extending neural network operations into geodesically disconnected pseudo-Riemannian manifolds. As a consequence, we derive a pseudo-Riemannian GCN that models data in pseudo-Riemannian manifolds of constant nonzero curvature in the context of graph neural networks. Our method provides a geometric inductive bias that is sufficiently flexible to model mixed heterogeneous topologies like hierarchical graphs with cycles. We demonstrate the representational capabilities of this method by applying it to the tasks of graph reconstruction, node classification, and link prediction on a series of standard graphs with mixed topologies. Empirical results demonstrate that our method outperforms Riemannian counterparts when embedding graphs of complex topologies.

Graph-level anomaly detection aims to distinguish anomalous graphs in a graph dataset from normal graphs. Anomalous graphs represent a very few but essential patterns in the real world. The anomalous property of a graph may be referable to its anomalous attributes of particular nodes and anomalous substructures that refer to a subset of nodes and edges in the graph. In addition, due to the imbalance nature of anomaly problem, anomalous information will be diluted by normal graphs with overwhelming quantities. Various anomaly notions in the attributes and/or substructures and the imbalance nature together make detecting anomalous graphs a non-trivial task. In this paper, we propose a graph neural network for graph-level anomaly detection, namely iGAD. Specifically, an anomalous graph attribute-aware graph convolution and an anomalous graph substructure-aware deep Random Walk Kernel (deep RWK) are welded into a graph neural network to achieve the dual-discriminative ability on anomalous attributes and substructures. Deep RWK in iGAD makes up for the deficiency of graph convolution in distinguishing structural information caused by the simple neighborhood aggregation mechanism. Further, we propose a Point Mutual Information (PMI)-based loss function to target the problems caused by imbalance distributions. PMI-based loss function enables iGAD to capture essential correlation between input graphs and their anomalous/normal properties. We evaluate iGAD on four real-world graph datasets. Extensive experiments demonstrate the superiority of iGAD on the graph-level anomaly detection task.

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.

Anomaly detection on attributed networks attracts considerable research interests due to wide applications of attributed networks in modeling a wide range of complex systems. Recently, the deep learning-based anomaly detection methods have shown promising results over shallow approaches, especially on networks with high-dimensional attributes and complex structures. However, existing approaches, which employ graph autoencoder as their backbone, do not fully exploit the rich information of the network, resulting in suboptimal performance. Furthermore, these methods do not directly target anomaly detection in their learning objective and fail to scale to large networks due to the full graph training mechanism. To overcome these limitations, in this article, we present a novel Contrastive self-supervised Learning framework for Anomaly detection on attributed networks (CoLA for abbreviation). Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair, which can capture the relationship between each node and its neighboring substructure in an unsupervised way. Meanwhile, a well-designed graph neural network (GNN)-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure and measure the agreement of each instance pairs with its outputted scores. The multiround predicted scores by the contrastive learning model are further used to evaluate the abnormality of each node with statistical estimation. In this way, the learning model is trained by a specific anomaly detection-aware target. Furthermore, since the input of the GNN module is batches of instance pairs instead of the full network, our framework can adapt to large networks flexibly. Experimental results show that our proposed framework outperforms the state-of-the-art baseline methods on all seven benchmark data sets.

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.

Abstract Attributed graph embedding aims to learn node representation based on the graph topology and node attributes. The current mainstream GNN-based methods learn the representation of the target node by aggregating the attributes of its neighbor nodes. These methods still face two challenges: (1) In the neighborhood aggregation procedure, the attributes of each node would be propagated to its neighborhoods which may cause disturbance to the original attributes of the target node and cause over-smoothing in GNN iteration. (2) Because the representation of the target node is derived from the attributes and topology of its neighbors, the attributes and topological information of each neighbor have different effects on the representation of the target node. However, this different contribution has not been considered by the existing GNN-based methods. In this paper, we propose a novel GNN model named API-GNN (Attribute Preserving Oriented Interactive Graph Neural Network). API-GNN can not only reduce the disturbance of neighborhood aggregation to the original attribute of target node, but also explicitly model the different impacts of attribute and topology on node representation. We conduct experiments on six public real-world datasets to validate API-GNN on node classification and link prediction. Experimental results show that our model outperforms several strong baselines over various graph datasets on multiple graph analysis tasks.

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.

Graph representation learning plays a vital role in processing graph-structured data. However, prior arts on graph representation learning heavily rely on labeling information. To overcome this problem, inspired by the recent success of graph contrastive learning and Siamese networks in visual representation learning, we propose a novel self-supervised approach in this paper to learn node representations by enhancing Siamese self-distillation with multi-scale contrastive learning. Specifically, we first generate two augmented views from the input graph based on local and global perspectives. Then, we employ two objectives called cross-view and cross-network contrastiveness to maximize the agreement between node representations across different views and networks. To demonstrate the effectiveness of our approach, we perform empirical experiments on five real-world datasets. Our method not only achieves new state-of-the-art results but also surpasses some semi-supervised counterparts by large margins. Code is made available at https://github.com/GRAND-Lab/MERIT

More and more online resources for computer science are introduced, used and released in scientific literature in recent years. Knowledge about the usage of these online resources can help researchers easily find the applicable resources for their works. However, most existing methods ignore the importance of the content of the online resource citations. To this end, we manually create SciR, a dataset that contains 3,012 annotation sentences for this task, and introduce a multi-task learning framework to automatically extract the entities and relations from the context of online resource citations in scientific papers. Furthermore, considering the words in a sentence usually play different roles under different relations. In this paper, we treat different relations as distinctive sub-spaces and model the correlations between words in sentence for each relation type by a supervised biaffine attention network. Based on this relation-aware attention network, our model can not only effectively obtain the word-level correlations under each relation, but also naturally avoid the problem of overlapping relations. To evaluate the effectiveness of our model, we conduct comprehensive experiments on three datasets and the experimental results demonstrate that our model outperforms other state-of-the-art methods on the two tasks of entity recognition and relation extraction.

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.

One-shot neural architecture search (NAS) has recently become mainstream in the NAS community because it significantly improves computational efficiency through weight sharing. However, the supernet training paradigm in one-shot NAS introduces catastrophic forgetting, where each step of the training can deteriorate the performance of other architectures that contain partially-shared weights with current architecture. To overcome this problem of catastrophic forgetting, we formulate supernet training for one-shot NAS as a constrained continual learning optimization problem such that learning the current architecture does not degrade the validation accuracy of previous architectures. The key to solving this constrained optimization problem is a novelty search based architecture selection (NSAS) loss function that regularizes the supernet training by using a greedy novelty search method to find the most representative subset. We applied the NSAS loss function to two one-shot NAS baselines and extensively tested them on both a common search space and a NAS benchmark dataset. We further derive three variants based on the NSAS loss function, the NSAS with depth constrain (NSAS-C) to improve the transferability, and NSAS-G and NSAS-LG to handle the situation with a limited number of constraints. The experiments on the common NAS search space demonstrate that NSAS and it variants improve the predictive ability of supernet training in one-shot NAS with remarkable and efficient performance on the CIFAR-10, CIFAR-100, and ImageNet datasets. The results with the NAS benchmark dataset also confirm the significant improvements these one-shot NAS baselines can make.

Graph Neural Networks (GNNs) have achieved state-of-the-art performance in many graph data analysis tasks. However, they still suffer from two limitations for graph representation learning. First, they exploit non-smoothing node features which may result in suboptimal embedding and degenerated performance for graph classification. Second, they only exploit neighbor information but ignore global topological knowledge. Aiming to overcome these limitations simultaneously, in this paper, we propose a novel, flexible, and end-to-end framework, Graph Smoothing Splines Neural Networks (GSSNN), for graph classification. By exploiting the smoothing splines, which are widely used to learn smoothing fitting function in regression, we develop an effective feature smoothing and enhancement module Scaled Smoothing Splines (S3) to learn graph embedding. To integrate global topological information, we design a novel scoring module, which exploits closeness, degree, as well as self-attention values, to select important node features as knots for smoothing splines. These knots can be potentially used for interpreting classification results. In extensive experiments on biological and social datasets, we demonstrate that our model achieves state-of-the-arts and GSSNN is superior in learning more robust graph representations. Furthermore, we show that S3 module is easily plugged into existing GNNs to improve their performance.

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 neural networks (GNNs) emerged recently as a powerful tool for analyzing non-Euclidean data such as social network data. Despite their success, the design of graph neural networks requires heavy manual work and domain knowledge. In this paper, we present a graph neural architecture search method (GraphNAS) that enables automatic design of the best graph neural architecture based on reinforcement learning. Specifically, GraphNAS uses a recurrent network 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. Furthermore, to improve the search efficiency of GraphNAS on big networks, GraphNAS restricts the search space from an entire architecture space to a sequential concatenation of the best search results built on each single architecture layer. Experiments on real-world datasets demonstrate that GraphNAS can design a novel network architecture that rivals the best human-invented architecture in terms of validation set accuracy. Moreover, in a transfer learning task we observe that graph neural architectures designed by GraphNAS, when transferred to new datasets, still gain improvement in terms of prediction accuracy.

As communities represent similar opinions, similar functions, similar purposes, etc., community detection is an important and extremely useful tool in both scientific inquiry and data analytics. However, the classic methods of community detection, such as spectral clustering and statistical inference, are falling by the wayside as deep learning techniques demonstrate an increasing capacity to handle high-dimensional graph data with impressive performance. Thus, a survey of current progress in community detection through deep learning is timely. Structured into three broad research streams in this domain – deep neural networks, deep graph embedding, and graph neural networks, this article summarizes the contributions of the various frameworks, models, and algorithms in each stream along with the current challenges that remain unsolved and the future research opportunities yet to be explored.

Knowledge Graphs typically suffer from incompleteness. A popular approach to knowledge graph completion is to infer missing knowledge by multihop reasoning over the information found along other paths connecting a pair of entities. However, multi-hop reasoning is still challenging because the reasoning process usually experiences multiple semantic issue that a relation or an entity has multiple meanings. In order to deal with the situation, we propose a novel Hierarchical Reinforcement Learning framework to learn chains of reasoning from a Knowledge Graph automatically. Our framework is inspired by the hierarchical structure through which human handle cognitionally ambiguous cases. The whole reasoning process is decomposed into a hierarchy of two-level Reinforcement Learning policies for encoding historical information and learning structured action space. As a consequence, it is more feasible and natural for dealing with the multiple semantic issue. Experimental results show that our proposed model achieves substantial improvements in ambiguous relation tasks.

Discrete network embedding emerged recently as a new direction of network representation learning. Compared with traditional network embedding models, discrete network embedding aims to compress model size and accelerate model inference by learning a set of short binary codes for network vertices. However, existing discrete network embedding methods usually assume that the network structures (e.g., edge weights) are readily available. In real-world scenarios such as social networks, sometimes it is impossible to collect explicit network structure information and it usually needs to be inferred from implicit data such as information cascades in the networks. To address this issue, we present an end-to-end discrete network embedding model for latent networks DELN that can learn binary representations from underlying information cascades. The essential idea is to infer a latent Weisfeiler-Lehman proximity matrix that captures node dependence based on information cascades and then to factorize the latent Weisfiler-Lehman matrix under the binary node representation constraint. Since the learning problem is a mixed integer optimization problem, an efficient maximal likelihood estimation based cyclic coordinate descent (MLE-CCD) algorithm is used as the solution. Experiments on real-world datasets show that the proposed model outperforms the state-of-the-art network embedding methods.

Graph Neural Networks (GNNs) have achieved remarkable performance in the task of the semi-supervised node classification. However, most existing models learn a deterministic classification function, which lack sufficient flexibility to explore better choices in the presence of kinds of imperfect observed data such as the scarce labeled nodes and noisy graph structure. To improve the rigidness and inflexibility of deterministic classification functions, this paper proposes a novel framework named Graph Stochastic Neural Networks (GSNN), which aims to model the uncertainty of the classification function by simultaneously learning a family of functions, i.e., a stochastic function. Specifically, we introduce a learnable graph neural network coupled with a high-dimensional latent variable to model the distribution of the classification function, and further adopt the amortised variational inference to approximate the intractable joint posterior for missing labels and the latent variable. By maximizing the lower-bound of the likelihood for observed node labels, the instantiated models can be trained in an end-to-end manner effectively. Extensive experiments on three real-world datasets show that GSNN achieves substantial performance gain in different scenarios compared with stat-of-the-art baselines.

While numerous approaches have been developed to embed graphs into either Euclidean or hyperbolic spaces, they do not fully utilize the information available in graphs, or lack the flexibility to model intrinsic complex graph geometry. To utilize the strength of both Euclidean and hyperbolic geometries, we develop a novel Geometry Interaction Learning (GIL) method for graphs, a well-suited and efficient alternative for learning abundant geometric properties in graph. GIL captures a more informative internal structural features with low dimensions while maintaining conformal invariance of each space. Furthermore, our method endows each node the freedom to determine the importance of each geometry space via a flexible dual feature interaction learning and probability assembling mechanism. Promising experimental results are presented for five benchmark datasets on node classification and link prediction tasks.

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.

Predicting pairs of anchor users plays an important role in the cross-network analysis. Due to the expensive costs of labeling anchor users for training prediction models, we consider in this paper the problem of minimizing the number of user pairs across multiple networks for labeling as to improve the accuracy of the prediction. To this end, we present a deep active learning model for anchor user prediction (DALAUP for short). However, active learning for anchor user sampling meets the challenges of non-i.i.d. user pair data caused by network structures and the correlation among anchor or non-anchor user pairs. To solve the challenges, DALAUP uses a couple of neural networks with shared-parameter to obtain the vector representations of user pairs, and ensembles three query strategies to select the most informative user pairs for labeling and model training. Experiments on real-world social network data demonstrate that DALAUP outperforms the state-of-the-art approaches.

Attributed network embedding plays an important role in transferring network data into compact vectors for effective network analysis. Existing attributed network embedding models are designed either in continuous Euclidean spaces which introduce data redundancy or in binary coding spaces which incur significant loss of representation accuracy. To this end, we present a new Low-Bit Quantization for Attributed Network Representation Learning model (LQANR for short) that can learn compact node representations with low bitwidth values while preserving high representation accuracy. Specifically, we formulate a new representation learning function based on matrix factorization that can jointly learn the low-bit node representations and the layer aggregation weights under the low-bit quantization constraint. Because the new learning function falls into the category of mixed integer optimization, we propose an efficient mixed-integer based alternating direction method of multipliers (ADMM) algorithm as the solution. Experiments on real-world node classification and link prediction tasks validate the promising results of the proposed LQANR model.

With the development of social media and the popularity of mobile devices, it becomes increasingly easy to post rumors and spread rumors on social media. Widespread rumors may cause public panic and negative impact on individuals, which makes the automatic detection of rumors become necessary. Most existing methods for automatic rumor detection focus on modeling features related to contents, users and propagation patterns based on feature engineering, but few work consider the existence of graph structural information in the user behavior. In this paper, we propose a model that leverages graph convolutional networks to capture user behavior effectively for rumor detection. Our model is composed of three modules: 1) a user encoder that models users attributes and behaviors based on graph convolutional networks to obtain user representation; 2) a propagation tree encoder, which encodes the structure of the rumor propagation tree as a vector with bridging the content semantics and propagation clues; 3) an integrator that integrates the output of the above modules to identify rumors. Experimental results on two public Twitter datasets show that our model achieves much better performance than the state-of-the-art methods.

Evolutionary clustering is a way of detecting the evolving patterns of communities in dynamic social networks. In principle, the detection process seeks to simultaneously maximize clustering accuracy at the current time step and minimize the clustering drift between two successive time steps. Several evolutionary clustering methods have been developed in an attempt to find the best trade-off between clustering accuracy and temporal smoothness, but the classic genetic operators in these methods do not make the best of the inter- and intra-connected relationships between nodes, which limits their effectiveness. To overcome this problem, we propose a novel migration operator to work in tandem with classic genetic operators to improve the discovery of evolving community structures. The operator is implemented within an existing genetic algorithm which relies on a genome representation under a decomposition framework that formulates evolutionary community detection as a multiobjective optimization problem. Moreover, we present a new method of calculating modularity directly from a genome matrix as the objective for measuring the snapshot quality, which results in a wider search space for finding the optimal solution. Experimental results over several synthetic networks and one real-world dynamic social network suggest that our method is superior to two other state-of-the-art methods in terms of both accuracy and smoothness in discovering evolving community structures in dynamic social networks.

Network embedding is an efficient method to learn low-dimensional representations of vertexes in networks since the network structure can be captured and preserved through this process. Unlike shallow models, deep neural network framework is able to capture the highly non-linear network structure. Therefore, it can achieve much better performance in comparison of traditional network embedding methods. However, few attention has been paid to the smoothness of such models, in contrast to numerous research works for image and text fields. Methods without smoothness are not robust enough, which means that slight changes on network may lead dramatic changes on the embedding results. Hence, how to find a smooth deep framework is still an open yet important problem. To this end, in this paper, we propose a Smooth Deep Network Embedding method, namely SmNE, which generates stable and reliable embedding results. Empirically, we conduct experiments on real-world networks. The results show that compared to the state-of-the-art methods, our proposed method can achieve significant gains in several applications.

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.

Social recommendation, which aims to exploit social information to improve the quality of a recommender system, has attracted an increasing amount of attention in recent years. A large portion of existing social recommendation models are based on the tractable assumption that users consider the same factors to make decisions in both recommender systems and social networks. However, this assumption is not in concert with real-world situations, since users usually show different preferences in different scenarios. In this paper, we investigate how to exploit the differences between user preference in recommender systems and that in social networks, with the aim to further improve the social recommendation. In particular, we assume that the user preferences in different scenarios are results of different linear combinations from a more underlying user preference space. Based on this assumption, we propose a novel social recommendation framework, called social recommendation with an essential preferences space (SREPS), which simultaneously models the structural information in the social network, the rating and the consumption information in the recommender system under the capture of essential preference space. Experimental results on four real-world datasets demonstrate the superiority of the proposed SREPS model compared with seven state-of-the-art social recommendation methods.

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.

Network embedding has been recently used in social network recommendations by embedding low-dimensional representations of network items for recommendation. However, existing item recommendation models in social networks suffer from two limitations. First, these models partially use item information and mostly ignore important contextual information in social networks such as textual content and social tag information. Second, network embedding and item recommendations are learned in two independent steps without any interaction. To this end, we in this paper consider item recommendations based on heterogeneous information sources. Specifically, we combine item structure, textual content and tag information for recommendation. To model the multi-source heterogeneous information, we use two coupled neural networks to capture the deep network representations of items, based on which a new recommendation model Collaborative multi-source Deep Network Embedding (CDNE for short) is proposed to learn different latent representations. Experimental results on two real-world data sets demonstrate that CDNE can use network representation learning to boost the recommendation performance.

Most of current network representation models are learned in unsupervised fashions, which usually lack the capability of discrimination when applied to network analysis tasks, such as node classification. It is worth noting that label information is valuable for learning the discriminative network representations. However, labels of all training nodes are always difficult or expensive to obtain and manually labeling all nodes for training is inapplicable. Different sets of labeled nodes for model learning lead to different network representation results. In this paper, we propose a novel method, termed as ANRMAB, to learn the active discriminative network representations with a multi-armed bandit mechanism in active learning setting. Specifically, based on the networking data and the learned network representations, we design three active learning query strategies. By deriving an effective reward scheme that is closely related to the estimated performance measure of interest, ANRMAB uses a multi-armed bandit mechanism for adaptive decision making to select the most informative nodes for labeling. The updated labeled nodes are then used for further discriminative network representation learning. Experiments are conducted on three public data sets to verify the effectiveness of ANRMAB.

User alignment between different social networks is a fundamental issue for many applications, such as information diffusion and recommendation. In actuality, the observed anchor users are normally sparse due to the expensiveness of labeling data. Hence how to make the best use of these sparse anchor information is an important open issue. To this end, we proposed a User Alignment via Structural Interaction and Propagation (UASIP) model to capture the structural information interaction across two social networks, which exploits deep structural infor- mation to enhance the representations of users. UASIP learns vector representation by automatically keeping the consistency between this additional structural information and intrinsic structural information of the two social networks. Experiments on real-world social network datasets demonstrate the effectiveness of UASIP compared with several state-of-the-art methods.

Network embedding plays a key role in network analysis, due to its ability to represent features of network structure in a low-dimensional Euclidean space, making it possible to directly utilize the of f-the-shelf mining techniques in a variety of analysis tasks. Although fruitful research papers on network embedding have sprung up in recent years, most of them neglect an important fact that nodes and edges in real-world networks are of diverse interests especially when the network contains little side information such as labels. To tackle this challenge, we propose a novel iWalk model to learn interest-aware network embedding in an unsupervised fashion. iWalk can automatically assign interest to nodes and edges based on network topology and construct custom paths navigated by assigned interest, then Skip-gram is used to learn network embedding from these paths. Sufficient experiments are conducted on different tasks and three typical datasets, the empirical results demonstrate that our model outperform the stat-of-art methods in most instances.

Detecting fraudsters is a meaningful problem for both users and e-commerce platform. Existing graph-based approaches mainly adopt shallow models, which cannot capture the highly non-linear relationship between vertexes in a bipartite graph composed of users and items. To address this issue, in this paper we propose a joint deep structure embedding approach FraudNE for fraud detection that (a) can preserve the highly non-linear structural information of networks, (b) is robust to sparse networks, (c) embeds different types of vertexes jointly in the same latent space. It is worth mentioning that we can detect multiple fraudulent groups without the number of groups as a priori. Compared with baselines, our method achieved significant accuracy improvement.

In many time-aware item recommender systems, modeling the accurate evolution of both user profiles and the contents of items over time is essential. However, most existing methods focus on learning users' dynamic interests, where the contents of items are assumed to be stable over time. They thus fail to capture the dynamic changes in the item's contents. In this paper, we present a novel method CDUE for time-aware item recommendation, which captures the evolution of both user's interests and item's contents information via topic dynamics. Specifically, we propose a dynamic sparse topic model to track the evolution of topics for changes in items' contents over time and adapt a vector autoregressive model to profile users' dynamic interests. The item's topics and user's interests and their evolutions are learned collaboratively and simultaneously into a unified learning framework. Experimental results on two real-world data sets demonstrate the quality and effectiveness of the proposed method and show that our method can be used to make better future recommendations.

Binary embedding is an effective way for nearest neighbor (NN) search as binary code is storage efficient and fast to compute. It tries to convert real-value signatures into binary codes while preserving similarity of the original data. However, it greatly decreases the discriminability of original signatures due to the huge loss of information. In this paper, we propose a novel method double-bit quantization and weighting (DBQW) to solve the problem by mapping each dimension to double-bit binary code and assigning different weights according to their spatial relationship. The proposed method is applicable to a wide variety of embedding techniques, such as SH, PCA-ITQ and PCA-RR. Experimental comparisons on two datasets show that DBQW for NN search can achieve remarkable improvements in query accuracy compared to original binary embedding methods.

Due to the rapid growth of event-based social networks (EBSNs), event recommendation which helps users find their preferred events has become a popular topic. Different from movies or books in conventional recommendation problem, events usually have recommendation lifetimes and almost all the events to be recommended are upcoming, which brings a severe cold start problem. To achieve better event recommendation performance, we formulates multiple interactions among users, events, groups and locations into an unified framework and propose a collective pairwise matrix factorization (CPMF) model to estimate users' pairwise preferences on events, groups and locations. We further develop an efficient stochastic gradient descent algorithm for the model learning. We conduct experiments on real-world Meetup datasets and the experimental results demonstrate that our CPMF model can outperform the state-of-the-art methods.

In this paper we theoretically study the minimum Differentially Resolving Set (DRS) problem derived from the classical sensor placement optimization problem in network source locating. A DRS of a graph G = (V, E) is defined as a subset S ⊆ V where any two elements in V can be distinguished by their different differential characteristic sets defined on S. The minimum DRS problem aims to find a DRS S in the graph G with minimum total weight Σv∈S w(v). In this paper we establish a group of Integer Linear Programming (ILP) models as the solution. By the weighted set cover theory, we propose an approximation algorithm with the Θ(ln n) approximability for the minimum DRS problem on general graphs, where n is the graph size.

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.

Influence maximization aims to find a set of highly influential nodes in a social network to maximize the spread of influence. The most difficult part of the problem is to estimate the influence spread of any seed set, which has been proved to be #P-hard. There is no efficient method to estimate the influence spread of any seed set till now. Thus, the most common way to obtain the approximate influence spread is Monte Carlo simulation and two popular simulating strategies are applied: one is propagation strategy, the other is snapshot strategy. The former only fits for particular seed set and the latter incurs heavy memory cost. In this paper, we present a new algorithm to estimate the influence spread of any seed set. Our algorithm recursively estimates the influence spread using reachable probabilities from node to node. Accordingly, we provide three strategies to start the recursion by integrating the memory cost and computing efficiency. Experiments demonstrate high performance of our influence estimation.

An information cascade occurs when a person observes the actions of others and then engages in the same acts. Cascades may break out if a large population of nodes in the network get affected. The outbreaks of cascades will often bring influential events, which leads to an open research problem: how to accurately predict the cascading outbreaks in social networks? Although there have been some existing works on cascading outbreak prediction, they ignore the structure information of cascades. In this paper, we propose to use subcascades as features for cascade outbreak prediction. We use frequent sequential pattern mining to extract subcascades and then propose a max-margin based classifier to select at most B features for prediction. The proposed model is empirically evaluated on both synthetic and real-world networks. Experimental results demonstrate the effectiveness of the proposed model.

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.

With the rapid growth of event-based social networks (EBSNs) like Meetup, the demand for event recommendation becomes increasingly urgent. In EBSNs, event recommendation plays a central role in recommending the most relevant events to users who are likely to participate in. Different from traditional recommendation problems, event recommendation encounters three new types of information, i.e., heterogenous online+offline social relationships, geographical features of events and implicit rating data from users. Yet combining the three types of data for offline event recommendation has not been considered. Therefore, we present a Bayesian latent factor model that can unify these data for event recommendation. Experimental results on real-world data sets show the performance of our method.

With the rapid growth of event-based social networks, the demand of event recommendation becomes increasingly important. Different from classic recommendation problems, event recommendation generally faces the problems of heterogenous online and offline social relationships among users and implicit feedback data. In this paper, we present a baysian probability model that can fully unleash the power of heterogenous social relations and efficiently tackle with implicit feedback characteristic for event recommendation. Experimental results on several real-world datasets demonstrate the utility of our method.

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.

Text corpus and link network are interrelated data in social networks. Discovering the inner relationship between these two kinds of data can help better understand the evolution mechanism underneath social networks. Moreover, social networks exhibit unique characteristics such as sparse and noisy in both text and link data. Thus, it is imperative to combine both text and link data to complement and correct mining results. However, previous work did not explore a uniform generative model that can unveil their inner relationship probably because of the difficulty to harness the heterogenous data in social networks. To address this issue, in this paper we present a generative model Topic Block that clearly pinpoints the latent concept underlying the text corpus and link network, i.e., User inner interests. In our generative model, user inner interests guide the generation of the topic and community distributions underlying the text corpus and link data. We can infer the topic and community distributions based on the user inner interests through both content and topology information. Compared to existing popular models, our method experimentally outperforms on three real world social network data sets.

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.