Heterophily in graphs is a key challenge for Graph Neural Networks (GNNs). By proposing various homophily measures, recent work has provided insights into how heterophily affects node classification. However, while both graph homophily and heterophily can be further refined into diverse connection patterns, previous work has largely overlooked the role of connection pattern inconsistency. In this paper, we delve deeper into heterophily and homophily by shifting from coarse-grained heterophily ratios to a unified, fine-grained formulation based on connection patterns, and we further reveal an uneven distribution and a train–test gap of these patterns. Empirical studies indicate that this inconsistency leads to severe performance disparity. To address this issue, we propose a novel two-stage method named IVQ-GNN. In the pre-training phase, IVQ-GNN encodes diverse connection patterns into a codebook that serves as an orthogonal basis for the representation space. In the fine-tuning phase, a self-attention module linearly combines these orthogonal bases to expand the learned token space of connection patterns, thereby improving adaptation to rare and out-of-distribution (OOD) patterns. Experimental results on multiple datasets demonstrate that IVQ-GNN significantly improves model performance and validate that the proposed method effectively addresses the connection pattern inconsistency. Our code is available at https://github.com/Duyx5149/IVQ-GNN.

Defending against backdoor attacks on graphs has become increasingly critical. Existing methods predominantly focus on detecting and removing triggers by identifying inconsistencies between trigger and clean nodes. However, adversaries can design triggers that closely resemble clean nodes, making them challenging to detect. Therefore, understanding the mechanisms underlying backdoor attacks is crucial. In this work, we observe an interesting phenomenon: in backdoored models, specific ''backdoor neurons'' (embedding dimensions) are more likely to be activated, causing nodes to be misclassified to the target label. This is largely due to the graph structure, where malicious information propagates through node neighborhoods, activating specific neurons and target label. Based on this observation, we theoretically and empirically demonstrate how graph backdoor attacks exploit this propagation mechanism to effectively poison the target node's embedding. Meanwhile, we propose a novel defense called Graph Backdoor Neuron Defense (GBND) to identify, unlearn, and recover backdoor neurons. Specifically, we design a novel reverse engineering technique to identify triggers that activate backdoor neurons, and eliminate their harmful effects by asymmetric unlearning and recovering at the neuron level. Extensive experiments on four datasets validate the effectiveness of GBND in defending against backdoor attacks.

Graph Anomaly Detection (GAD) is critical in applications such as fraud prevention, cybersecurity, and social governance. While Graph Neural Networks (GNNs) have achieved remarkable success in detecting anomalies on homogeneous graphs, they face fundamental challenges in real-world heterogeneous settings involving diverse node types and imbalanced semantic richness. In heterogeneous graphs, nodes often vary significantly in semantic richness, with anomalies potentially spanning multiple types and emerging implicitly through cross-type dependencies. We identify two core limitations of existing methods: (i) the ineffective propagation of discriminative anomaly cues from informative to sparse nodes due to semantic imbalance, and (ii) conflicting optimization objectives arising from joint detection across multiple node types. To address these issues, we propose CSA-MTHGAD, a novel framework that integrates smoothness-guided cross-type semantic alignment with dynamic multi-task learning. It selectively propagates anomaly-sensitive features across types and harmonizes task-specific gradients through adaptive projection and weighting.To facilitate research, we employ two real-world heterogeneous benchmarks in the domain of social governance. Extensive experiments demonstrate that CSA-MTHGAD achieves superior performance over state-of-the-art baselines in accuracy, robustness, and generalization for multi-type anomaly detection.

Graph-based fraud detection (GFD) aims to identify fraud nodes within graph-structured data that significantly deviate from the majority of benign nodes. However, existing graph neural networks (GNNs) often struggle in GFD scenarios due to their reliance on homophily assumption, which is frequently violated by the inherent homophily-heterophily mixture of fraud graphs. Moreover, most methods focus primarily on local topology, overlooking mesoscopic community structures, making them less efficient in detecting suspicious patterns like densely connected subgraphs. To address the aforementioned issues, we present NeCo, a novel approach that integrates mixture of neighborhood and community experts for graph-based fraud detection. Specifically, we first introduce a fraud-discriminative representation preservation mechanism from a neighborhood perspective, leveraging the empirical finding that fraud nodes tend to exhibit larger feature propagation discrepancies compared to benign nodes. We then design a community-oriented node representation module that models structural compactness among nodes, enabling the detection of suspicious topological patterns associated with fraud behaviors. By integrating these two complementary perspectives, NeCo can effectively captures both local inconsistency and global structural irregularity. Extensive experiments across five real-world datasets demonstrate the effectiveness of our proposed NeCo over state-of-the-art baselines.

The COVID-19 pandemic not only triggered a global health crisis but also amplified public panic through the rapid spread of misinformation. Understanding public sentiment and identifying the causes of sudden sentiment spikes is therefore critical for ensuring accurate information dissemination and guiding effective policymaking. However, mining such causes from social media remains challenging. Tweets collected during sentiment spike periods are often short, noisy, and dominated by repetitive background topics, making it difficult for existing topic models to separate emerging issues from long-standing discussions. To address these challenges, we propose the Sentiment Variation-aware Emerging Topics Mining Model (SVETM), a probabilistic graphical framework that leverages user sentiment variation between adjacent time windows as a guiding signal to distinguish emerging topics from background content. We further reformulate inference as a maximum a posteriori (MAP) problem and develop an efficient variational inference algorithm for scalable learning. Extensive experiments on a large-scale COVID-19 Twitter dataset demonstrate that SVETM outperforms strong baselines in terms of topic coherence, interpretability, and its ability to uncover the underlying causes of sentiment spikes.

Recent years have witnessed fast developments of graph neural networks (GNNs) that have benefited myriad graph analytic tasks and applications. Most GNNs rely on the homophily assumption that nodes belonging to the same class are more likely to be connected. However, as a ubiquitous graph property in numerous real-world scenarios, heterophily, i.e., nodes with different labels tend to be linked, significantly limits the performance of tailor-made homophilic GNNs. Hence, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">GNNs for heterophilic graphs</i> are gaining increasing research attention to enhance graph learning with heterophily. In this paper, we provide a comprehensive review of GNNs for heterophilic graphs. Specifically, we propose a systematic taxonomy that governs existing heterophilic GNN models, along with general summaries and detailed analyses. Furthermore, we discuss the relationship between heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs across a spectrum of practical applications and learning tasks in the graph research community. In the end, we point out potential directions to advance and inspire future research and applications on heterophilic graph learning with GNNs.

The cold-start recommendation has been challenging due to the limited historical interactions for new users and new items. Recently, methods based on meta-learning and graph neural networks are effective on this problem. However, these methods mainly focus on the missing user–item interactions in cold-start scenarios, overlooking the missing of user/item feature information, which significantly limits the quality and effectiveness of node embeddings. To address this problem, we propose an innovative Large Language Model-Guided Feature-Structure Augmented Graph Neural Network (LLM-FSGNN). The proposed framework integrates external semantic knowledge with internal graph structures via LLMs. It generates more comprehensive and robust user and item node representations. Specifically, we leverage the semantic reasoning capabilities of LLMs to extract textual descriptions of users and items, constructing a semantic view to enhance ambiguous or missing attributes and enrich node feature representations. Simultaneously, by analyzing item content to better understand user preferences, LLMs can accurately predict users’ potential intentions toward items and uncover latent interaction relationships, thus strengthening structural features. In addition, we introduce a graph structure enhancement module to complement structural relations from a graph-based perspective, mitigating hallucination issues in LLMs. Experimental results on multiple public benchmark datasets demonstrate consistent improvements in cold-start scenarios. For example, LLM-FSGNN achieves 4.8% lower MAE on MovieLens100K, 3.6% lower MAE on MovieLens1M, and 4.2% lower MAE on Amazon compared with the current state-of-the-art methods.

User decision-making behavior in recommender systems is jointly driven by a large number of underlying factors. Learning and revealing the representations of these latent factors can provide more robustness and interpretability. However, mining the latent intentions of user decision-making behaviors in existing multimodal recommendation studies faces the following two key challenges: (i) Modal Noise Pollution : In multimodal user intent modeling, inputs from individual modalities are inevitably corrupted by noise of varying severity. During message passing, a large proportion of irrelevant or even contradictory signals are propagated and injected into item representations, which impedes the model’s ability to achieve pure semantic alignment at the content level. (ii) User Intent Confounding : Real-world items naturally possess multiple attributes, with different attributes of the same item influencing distinct potential user intentions. However, in existing modeling designs for user intent, such intents are mapped onto user–item interaction labels of the same coarse granularity. This many-to-one mapping relationship between intentions and items leads to significant confounding and dilution of users’ fine-grained intentions. To address the above challenges, this work pays special attention to the implied user intent behind pure multimodal features. Specifically, we construct a dynamic, adaptive, multimodal intent disentanglement model. This model adopts a non-ID paradigm and mines the distribution of user intents in multimodal scenarios directly from users’ decision-making behaviors. A comprehensive experimental study on the Amazon dataset shows that the method is effective and provides a novel learning scheme for mining user intent in multimodal scenarios.

Traffic prediction plays a pivotal role in intelligent transportation systems. Most existing studies only predict traffic flow for a specific time period based on traffic data from a short period, such as an hour, overlooking the influence of periodicity present in traffic data. Moreover, most of the existing advanced methods rely on manually constructed spatio-temporal graphs for joint modeling, or use pure spatial and pure temporal modules to separately model spatial and temporal features, which limits the learning of complex spatio-temporal patterns in traffic data due to structural inadequacies in the model. To address these issues, we propose a novel approach by constructing a learnable long-range spatio-temporal graph, which can better capture complex patterns in traffic data. We introduce a new model, LLGformer, which improves upon traditional Transformer-style models, facilitating more efficient learning of traffic flow data by integrating long-range historical information. Leveraging attention mechanisms on a spatiotemporal graph enables direct interaction of information across different time slices and locations. Additionally, we propose two optimization strategies to further boost the speed of training and inference. Extensive experiments on four real-world datasets show that the new model significantly outperforms state-of-the-art methods.

Heterogeneous graph neural network (HGNN) is a popular technique for modeling and analyzing heterogeneous graphs. Most existing HGNN-based approaches are supervised or semi-supervised learning methods requiring graphs to be annotated, which is costly and time-consuming. Self-supervised contrastive learning has been proposed to address the problem of requiring annotated data by mining intrinsic properties in the given data. However, the existing contrastive learning methods are not suitable for heterogeneous graphs because they construct contrastive views only based on data perturbation or pre-defined structural properties (e.g., meta-path) in graph data while ignoring noises in node attributes and graph topologies. We develop a robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidances of node attributes and graph topologies and integrates and enhances them by a reciprocally contrastive mechanism to better model heterogeneous graphs. In this new approach, we adopt distinct but suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately. We further use both attribute similarity and topological correlation to construct high-quality contrastive samples. Extensive experiments on four large real-world heterogeneous graphs demonstrate the superiority and robustness of HGCL over several state-of-the-art methods.

Contrastive Learning (CL) has emerged as a popular self-supervised representation learning paradigm that has been shown in many applications to perform similarly to traditional supervised learning methods. A key component of CL is mining the latent discriminative relationships between positive and negative samples and using them as self-supervised labels. We argue that this discriminative contrastive task is, in essence, similar to a classification task, and the “either positive or negative” hard label sampling strategies are arbitrary. To solve this problem, we explore ideas from data distillation, which considers probabilistic logit vectors as soft labels to transfer model knowledge. We attempt to abandon the classical hard sampling labels in CL and instead explore self-supervised soft labels. We adopt soft sampling labels that are extracted, without supervision, from the inherent relationships in data pairs to retain more information. We propose a new self-supervised graph learning method, Distill and Contrast (D&C), for learning representations that closely approximate natural data relationships. D&C extracts node similarities from the features and structures to derive soft sampling labels, which also eliminate noise in the data to increase robustness. Extensive experimental results on real-world datasets demonstrate the effectiveness of the proposed method.

Sarcasm thrives on popular social media platforms such as Twitter and Reddit, where users frequently employ it to convey emotions in an ironic or satirical manner. The ability to detect sarcasm plays a pivotal role in comprehending individuals’ true sentiments. To achieve a comprehensive grasp of sentence semantics, it is crucial to integrate external knowledge that can aid in deciphering entities and their intricate relationships within a sentence. Although some efforts have been made in this regard, their use of external knowledge is still relatively superficial. Specifically, Knowledge-enhanced entity and relationship understanding still face significant challenges. In this paper, we propose the Knowledge Enhanced Sentiment Dependency Graph Convolutional Network (KSDGCN) framework, which constructs a commonsense-augmented sentiment graph and a commonsense-replaced dependency graph for each text to explicitly capture the role of external knowledge for sarcasm detection. Furthermore, we validate the irrational relationships between co-occurring entity pairs within sentences and background knowledge by a signed attention mechanism. We conduct experiments on four benchmark datasets, and the results show that KSDGCN outperforms existing state-of-the-art methods and is highly interpretable.

Self-supervised tasks show significant advantages for node representation learning in recommender systems. This core idea of self-supervised task-based recommender systems depends on data augmentation to generate multi-view representations. However, there are two key challenges that are not well explored in existing self-supervised tasks: i) Restricted by the structure of the graph-based CF paradigm itself, the classical graph comparison learning architecture ignores the global structural information on the user-item interaction graph. ii) In a key part of existing contrast learning-random graph data enhancement schemes can significantly deteriorate model performance. To address these challenges, we propose a new hypergraph collaborative filtering with adaptive augmentation framework(HCFAA). It captures both local and global collaborative relationships on the user-item graph through a hypergraph-enhanced joint learning architecture. In particular, the designed adaptive structure-guided model ignores the noise introduced on unimportant edges, and thus learns the critical node information on the user-item graph. Comprehensive experimental studies on the Amazon dataset show that the method is effective, which provides an optimization scheme with a new perspective for the problems of key node loss in graph data enhancement and loss of higher-order structural information in GNN. The source code of our model can be available onhttps://github.com/RSnewbie/RS/tree/master/HCFAA.

Object detection is a widely studied problem in existing works. However, in this paper, we turn to a more challenging problem of “ Covered Object Reasoning ”, aimed at reasoning the category label of target object in the given image particularly when it has been totally covered (or invisible ). To resolve this problem, we propose CoBjeason to seize the opportunity when visual reasoning meets the knowledge graph, where “ empirical cognition ” on common visual contexts have been incorporated as knowledge graph to conduct reinforced multi-hop reasoning via two collaborative agents. Such two agents, for one thing, stand at the covered object (or unknown entity ) to observe the surrounding visual cues in the given image and gradually select entities and relations from the global gallery-level knowledge graph which contains entity-pairs frequently occurring across the entire image-collection, so as to infer the main structure of image-level knowledge graph forward expanded from the unknown entity . In turn, for another, based on the reasoned image-level knowledge graph, the semantic context among entities will be aggregated backward into unknown entity to select an appropriate entity from the global gallery-level knowledge graph as the reasoning result. Moreover, such two agents will collaborate with each other, securing that the above Forward & Backward Reasoning will step towards the same destination of the higher performance on covered object reasoning. To our best knowledge, this is the first work on Covered Object Reasoning with Knowledge Graphs and reinforced Multi-Agent collaboration. Particularly, our study on Covered Object Reasoning and the proposed model CoBjeason could offer novel insights into more basic Computer Vision (CV) tasks, such as Semantic Segmentation with better understanding on the current scene when some objects are blurred or covered, Visual Question Answering with enhancement on the inference in more complicated visual context when some objects are covered or invisible, and Image Caption Generation with the augmentation on the richness of visual context for images containing partially visible objects. The improvement on the above basic CV tasks can further refine more complicated ones involved with nuanced visual interpretation like Autonomous Driving, where the recognition and reasoning on partially visible or covered object are critical. According to the experimental results, our proposed CoBjeason can achieve the best overall ranking performance on covered object reasoning compared with other models, meanwhile enjoying the advantage of lower “ exploration cost ”, with the insensitivity against the long-tail covered objects and the acceptable time complexity.

Graph similarity learning is a significant and fundamental issue in the theory and analysis of graphs, which has been applied in a variety of fields, including object tracking, recommender systems, similarity search, and so on. Recent methods for graph similarity learning that utilize deep learning typically share two deficiencies: (1) they leverage graph neural networks as backbones for learning graph representations but have not well captured the complex information inside data, and (2) they employ a cross-graph attention mechanism for graph similarity learning, which is computationally expensive. Taking these limitations into consideration, a method for graph similarity learning is devised in this study, namely, Contrastive Graph Similarity Network (CGSim). To enhance graph similarity learning, CGSim makes use of the complementary information of two input graphs and captures pairwise relations in a contrastive learning framework. By developing a dual contrastive learning module with a node-graph matching and a graph-graph matching mechanism, our method significantly reduces the quadratic time complexity for cross-graph interaction modeling to linear time complexity. Jointly learning in an end-to-end framework, the graph representation embedding module and the well-designed contrastive learning module can be beneficial to one another. A comprehensive series of experiments indicate that CGSim outperforms state-of-the-art baselines on six datasets and significantly reduces the computational cost, which demonstrates our CGSim model’s superiority over other baselines.

The task of sequential recommendation aims to predict a user’s preference by analyzing the user’s historical behaviours. Existing methods model item transitions through leveraging sequential patterns. However, they mainly consider the target user’s behaviours and dynamic characteristics, while often ignoring high-order collaborative connections when modelling user preferences. Some recent works try to use graph-based methods to introduce high-order collaborative signals for sequential recommendation. However, these methods are flawed by two problems: the sequential patterns cannot be effectively mined and their way of introducing high-order collaborative signals is not suitable for sequential recommendation. To address these problems, we propose to fully exploit sequence features and model high-order collaborative signals for sequential recommendation. We propose a N eighbor user I ntention-based S equential Rec ommender (NISRec), which utilizes the intentions of high-order connected neighbor users as high-order collaborative signals in order to improve recommendation performance for the target user. The NISRec contains two main modules: the neighbor user intention embedding module (NIE) and the fusion module. The NIE module describes both the long-term and short-term intentions of neighbor users and aggregates them separately. The fusion module uses these two types of aggregated intentions to model high-order collaborative signals in both the embedding process and user preference modelling phase for recommendations of the target user. Experimental results show that our new approach outperforms the state-of-the-art methods on both sparse and dense datasets. Extensive studies further show the effectiveness of the diverse neighbor intentions introduced by the NISRec.

Sequential recommendation aims to capture users' dynamic preferences, in which data sparsity is a key problem. Most contrastive learning models leverage data augmentation to address this problem, but they amplify noises in original sequences. Contrastive learning has the assumption that two views (positive pairs) obtained from the same user behavior sequence must be similar. However, noises typically disturb the user's main intention, which results in the dissimilarity of two views.

Recommender systems are essential to various fields, e.g., e-commerce, e-learning, and streaming media. At present, graph neural networks (GNNs) for session-based recommendations normally can only recommend items existing in users’ historical sessions. As a result, these GNNs have difficulty recommending items that users have never interacted with (new items), which leads to a phenomenon of information cocoon. Therefore, it is necessary to recommend new items to users. As there is no interaction between new items and users, we cannot include new items when building session graphs for GNN session-based recommender systems. Thus, it is challenging to recommend new items for users when using GNN-based methods. We regard this challenge as “GNN Session-based New Item Recommendation (GSNIR)”. To solve this problem, we propose a dual-intent enhanced graph neural network for it. Due to the fact that new items are not tied to historical sessions, the users’ intent is difficult to predict. We design a dual-intent network to learn user intent from an attention mechanism and the distribution of historical data respectively, which can simulate users’ decision-making process in interacting with a new item. To solve the challenge that new items cannot be learned by GNNs, inspired by zero-shot learning (ZSL), we infer the new item representation in GNN space by using their attributes. By outputting new item probabilities, which contain recommendation scores of the corresponding items, the new items with higher scores are recommended to users. Experiments on two representative real-world datasets show the superiority of our proposed method. The case study from the real-world verifies interpretability benefits brought by the dual-intent module and the new item reasoning module.

Social Internet of Things (SIoT), a promising and emerging paradigm that injects the notion of social networking into smart objects (i.e., things), paving the way for the next generation of Internet of Things. However, due to the risks and uncertainty, a crucial and urgent problem to be settled is establishing reliable relationships within SIoT, that is, trust evaluation. Graph neural networks for trust evaluation typically adopt a straightforward way such as one-hot or node2vec to comprehend node characteristics, which ignores the valuable semantic knowledge attached to nodes. Moreover, the underlying structure of SIoT is usually complex, including both the heterogeneous graph structure and pairwise trust relationships, which renders hard to preserve the properties of SIoT trust during information propagation. To address these aforementioned problems, we propose a novel knowledge-enhanced graph neural network (KGTrust) for better trust evaluation in SIoT. Specifically, we first extract useful knowledge from users’ comment behaviors and external structured triples related to object descriptions, in order to gain a deeper insight into the semantics of users and objects. Furthermore, we introduce a discriminative convolutional layer that utilizes heterogeneous graph structure, node semantics, and augmented trust relationships to learn node embeddings from the perspective of a user as a trustor or a trustee, effectively capturing multi-aspect properties of SIoT trust during information propagation. Finally, a trust prediction layer is developed to estimate the trust relationships between pairwise nodes. Extensive experiments on three public datasets illustrate the superior performance of KGTrust over state-of-the-art methods.

Network embedding which is to learn a low dimensional representation of nodes in a network has been used in many network analysis tasks. Some network embedding methods, including those based on Generative Adversarial Networks (GAN) (a promising deep learning model), have been proposed recently. Existing GAN-based methods typically use GAN to learn a Gaussian distribution as a prior for network embedding, which makes it difficult to distinguish the node representation from Gaussian distribution. It did not apply the adversarial learning strategy on the representation mechanism but just on representation results. Thus, it does not make full use of the essential advantage of GAN, and leads to compromised performance of the method. To address this problem, we propose a novel adversarial learning framework consisting of three players for network embedding, which applies the adversarial learning strategy on the representation mechanism, called Adversarial representation mechanism GAN (ArmGAN). Specifically, the first two players, named encoder and competitor, aim to learn two different representation mechanisms (i.e., two ways projecting data onto latent space). They compete with each other to improve their representation mechanisms. The third player is the discriminator, which discriminate the representation mechanism of the encoder from that of the competitor. In addition, we design a perturbation strategy to produce fake networks from the original network, and feed the fake networks to the competitor to obtain a “fake” representation mechanism. We evaluated ArmGAN on a variety of tasks including node clustering, node classification, link prediction and visualization. Moreover, we compared ArmGAN with 10 state-of-the-art methods (including DGI, which is well-known for its high accuracy) on 7 real-world networks. The experimental results show the significant superiority of ArmGAN over the existing methods.

Social trust assessment that characterizes a pairwise trustworthiness relationship can spur diversified applications. Extensive efforts have been put in exploration, but mainly focusing on applying graph convolutional network to establish a social trust evaluation model, overlooking user feature factors related to context-aware information on social trust prediction. In this article, we aim to design a new trust assessment framework GATrust which integrates multi-aspect properties of users, including user context-specific information, network topological structure information, and locally-generated social trust relationships. GATrust can assigns different attention coefficients to multi-aspect properties of users in online social networks, for improving the prediction accuracy of social trust evaluation. The framework can then learn multiple latent factors of each trustor-trustee pair to establish a social trust evaluation model, by fusing graph attention network and graph convolution network. We conduct extensive experiments on two popular real-world datasets and the results exhibit that our proposed framework can improve the precision of social trust prediction, outperforming the state-of-the-art in the literature by 4.3% and 5.5% on both two datasets, respectively.

Heterogeneous information network (HIN) embedding, aiming to map the structure and semantic information in a HIN to distributed representations, has drawn considerable research attention. Graph neural networks for HIN embeddings typically adopt a hierarchical attention (including node-level and meta-path-level attentions) to capture the information from meta-path-based neighbors. However, this complicated attention structure often cannot achieve the function of selecting meta-paths due to severe overfitting. Moreover, when propagating information, these methods do not distinguish direct (one-hop) meta-paths from indirect (multi-hop) ones. But from the perspective of network science, direct relationships are often believed to be more essential, which can only be used to model direct information propagation. To address these limitations, we propose a novel neural network method viaimplicitlyutilizing attention and meta-paths, which can relieve the severe overfitting brought by the current over-parameterized attention mechanisms on HIN. We first use the multi-layer graph convolutional network (GCN) framework, which performs a discriminative aggregation at each layer, along with stacking the information propagation of direct linked meta-paths layer-by-layer, realizing the function of attentions for selecting meta-paths in an indirect way. We then give an effective relaxation and improvement via introducing a new propagation operation which can be separated from aggregation. That is, we first model the whole propagation process with well-defined probabilistic diffusion dynamics, and then introduce a random graph-based constraint which allows it to reduce noise with the increase of layers. Extensive experiments demonstrate the superiority of the new approach over state-of-the-art methods.

Community detection, a fundamental task for network analysis, aims to partition a network into multiple sub-structures to help reveal their latent functions. Community detection has been extensively studied in and broadly applied to many real-world network problems. Classical approaches to community detection typically utilize probabilistic graphical models and adopt a variety of prior knowledge to infer community structures. As the problems that network methods try to solve and the network data to be analyzed become increasingly more sophisticated, new approaches have also been proposed and developed, particularly those that utilize deep learning and convert networked data into low dimensional representation. Despite all the recent advancement, there is still a lack of insightful understanding of the theoretical and methodological underpinning of community detection, which will be critically important for future development of the area of network analysis. In this paper, we develop and present a unified architecture of network community-finding methods to characterize the state-of-the-art of the field of community detection. Specifically, we provide a comprehensive review of the existing community detection methods and introduce a new taxonomy that divides the existing methods into two categories, namely probabilistic graphical model and deep learning. We then discuss in detail the main idea behind each method in the two categories. Furthermore, to promote future development of community detection, we release several benchmark datasets from several problem domains and highlight their applications to various network analysis tasks. We conclude with discussions of the challenges of the field and suggestions of possible directions for future research.

Graph neural networks (GNNs) have gained significant success in graph representation learning and become the go-to approach for many graph-based tasks. Despite their effectiveness, the performance of GNNs is known to decline gradually as the number of layers increases. This attenuation is mainly caused by noise propagation, which refers to the useless or negative information propagated (directly or indirectly) from other nodes during the multi-layer graph convolution for node representation learning. This noise increases more severely as the layers of GNNs deepen, which is also a main reason of over-smoothing. In this paper, we propose a new convolution strategy for GNNs to address this problem via suppressing the noise propagation. Specifically, we first find that the feature propagation process of GNNs can be taken as a Markov chain. And then, based on the idea of Markov clustering, we introduce a new graph inflation layer (i.e., using a power function over the distribution) into GNNs to prevent noise propagating from local neighbourhoods to the whole graph with the increase of network layers. Our method is simple in design, which does not require any changes on the original basis and therefore can be easily extended. We conduct extensive experiments on real-world networks and have a stable improved performance as the network depth increases over existing GNNs.

Graph neural network (GNN) has become a popular tool to analyze the graph data. Existing GNNs only focus on networks with first-order dependency, that is, conventional networks following the Markov property. However, many networks in real life own the higher-order dependency, such as click-stream data where the choice of the next page depends not only on the current page but also on previous pages. This kind of sequential data from complex systems (including natural dependencies) are often ignored by existing GNNs which makes them ineffective. To address this problem, we propose for the first time new GNN approaches for higher-order networks in this paper. First, we form sequence fragments by the current node and its predecessor nodes of different orders as candidate higher-order dependencies. When the fragment significantly affects the probability distribution of different successor nodes of the current node, we include it in the higher-order dependency set. We formulize the network with higher-order dependency as an augmented conventional first-order network, and then feed it into GNNs to derive network embeddings. Moreover, we further propose a new end-to-end GNN framework for dealing with higher-order networks directly in the model. Specifically, the higher-order dependency is used as the neighbor aggregation controller when the node is embedded and updated. In the graph convolutional layer, in addition to the first-order neighbor information, we also aggregate the middle node information from the higher-order dependency segment. We finally test the new approaches on three real networks with higher-order dependency, and compare with some state-of-the-art methods. The results show significant improvements of the new approaches which consider higher-order dependency.

Core maximization, that enlarges the k -core as much as possible by inserting a few new edges into a graph, is particularly useful for social group engagement and network stability improvement. However, the core maximization problem has been theoretically proven to be NP-hard even APX-hard for k ≥ 3. Existing heuristic approaches suffer from the limitation of inefficiency on large graphs. To address this limitation, in this paper, we revisit this challenging yet important problem of core maximization, that is, given a graph G , a number k , and a budget b , to insert b new edges into G such that the corresponding k -core is maximized. We propose a novel algorithm FastCM+ based on several fast search strategies. The core idea is to apply graph partition to divide ( k - 1)-shell into different components. Then, FastCM+ considers each ( k - 1)-shell component independently to convert different layered vertices into k -core, in two manners of completely and partially. Based on the complete/partial conversions, FastCM+ is generalized to further handle ( k - λ)-shell conversions for 2 ≤λ k . Leveraging dynamic programming combinations of different components' potential answers, FastCM+ finds a good-quality answer for edge insertions. Experimental results on eleven datasets demonstrate that our algorithm runs much faster than state-of-the-art methods on large graphs meanwhile achieving better answers.

Cohesive substructure identification is one fundamental task of graph analytics. Recently, a useful problem of dense subgraph maximization has attracted significant attentions, which aims at enlarging a dense subgraph pattern using a few new edge insertions, e.g., k-core maximization. As a more cohesive subgraph of k-core, k-truss requires that each edge has at least k-2 triangles within this subgraph. However, the problem of k-truss maximization has not been studied yet. In this paper, we motivate and formulate a new problem of budget-constrained k-truss maximization. Given a budget of b edges and an integer k≥2, the problem is to find and insert b new edges into a graph G such that the resulted k-truss of G is maximized. We theoretically prove the NP-hardness of k-truss maximization problem. To efficiently tackle it, we analyze non-submodular property of k-truss newcomers function and develop non-conventional heuristic strategies for edge insertions. We first identify high-quality candidate edges with regard to (k-1)-light subgraphs and propose a greedy algorithm using per-edge insertion. Besides further improving the efficiency by pruning disqualified candidate edges, we finally develop a component-based dynamic programming algorithm for enlarging k-truss mostly, which makes a balance of budget assignment and inserts multiple edges simultaneously into all (k-1)-light components. Extensive experiments on nine real-world graphs demonstrate the efficiency and effectiveness of our proposed methods.

The dependencies across different layers are an important property in multiplex networks and a few methods have been proposed to learn the dependencies in various ways. When capturing the dependencies across different layers, some of them assumed the structure among layers following consistent connectivity to force two nodes with a link in one layer tend to have links in other layers, some introduced a common vector to model the shared information across all layers. However, the correlations among layers in multiplex networks are diverse, which go beyond the connectivity consistency. In this paper, we propose a novel Modeling Correlations for Multiplex network Embedding (MCME) framework to learn the robust node representations for each layer. It can deal with complex correlations with a common structure, layer similarity and node heterogeneity through a unified framework in multiplex networks. To evaluate our proposed model, we conduct extensive experiments on several real-world datasets and the results demonstrate that our proposed model consistently outperforms state-of-the-art methods.

Graph Neural Networks (GNNs) have demonstrated great power in many network analytical tasks. However, graphs (i.e., networks) in the real world are usually text-rich, implying that valuable semantic information needs to be carefully considered. Existing GNNs for text-rich networks typically treat text as attribute words alone, which inevitably leads to the loss of important semantic structures, limiting the representation capability of GNNs. In this paper, we propose an end-to-end adaptive semantic architecture of graph convolutional networks, namely AS-GCN, which unifies neural topic model and graph convolutional networks, for text-rich network representation. Specifically, we utilize a neural topic model to extract the global topic semantics, and accordingly augment the original text-rich network into a tri-typed heterogeneous network, capturing both the local word-sequence semantic structure and the global topic semantic structure from text. We then design an effective semantic-aware propagation of information by introducing a discriminative convolution mechanism. We further propose two strategies, that is, distribution sharing and joint training, to adaptively generate a proper network structure based on the learning objective to improve network representation. Extensive experiments on text-rich networks illustrate that our new architecture outperforms the state-of-the-art methods by a significant improvement. Meanwhile, this architecture can also be applied to e-commerce search scenes, and experiments on a real e-commerce problem from JD further demonstrate the superiority of the proposed architecture over the baselines.

Graph convolutional networks (GCNs), aiming to obtain node embeddings by integrating high-order neighborhood information through stacked graph convolution layers, have demonstrated great power in many network analysis tasks such as node classification and link prediction. However, a fundamental weakness of GCNs, that is, topological limitations, including over-smoothing and local homophily of topology, limits their ability to represent networks. Existing studies for solving these topological limitations typically focus only on the convolution of features on network topology, which inevitably relies heavily on network structure. Moreover, most networks are text-rich, so it is important to integrate not only document-level information, but also the local text information which is particularly significant while often ignored by the existing methods. To solve these limitations, we propose BiTe-GCN, a novel GCN architecture modeling via bidirectional convolution of topology and features on text-rich networks. Specifically, we first transform the original text-rich network into an augmented bi-typed heterogeneous network, capturing both the global document-level information and the local text-sequence information from texts. We then introduce discriminative convolution mechanisms, which performs convolution on this augmented bi-typed network, realizing the convolutions of topology and features altogether in the same system, and learning different contributions of these two parts (i.e., network part and text part), automatically for the given learning objectives. Extensive experiments on text-rich networks demonstrate that our new architecture outperforms the state-of-the-arts by a breakout improvement. Moreover, this architecture can also be applied to several e-commerce search scenes such as JD searching, and experiments on JD dataset show the superiority of the proposed architecture over the related methods.

Heterogeneous information networks (HINs), also called heterogeneous graphs, are composed of multiple types of nodes and edges, and contain comprehensive information and rich semantics. Graph neural networks (GNNs), as powerful tools for graph data, have shown superior performance on network analysis. Recently, many excellent models have been proposed to process hetero-graph data using GNNs and have achieved great success. These GNN-based heterogeneous models can be interpreted as smooth node attributes guided by graph structure, which requires all nodes to have attributes. However, this is not easy to satisfy, as some types of nodes often have no attributes in heterogeneous graphs. Previous studies take some handcrafted methods to solve this problem, which separate the attribute completion from the graph learning process and, in turn, result in poor performance. In this paper, we hold that missing attributes can be acquired by a learnable manner, and propose a general framework for Heterogeneous Graph Neural Network via Attribute Completion (HGNN-AC), including pre-learning of topological embedding and attribute completion with attention mechanism. HGNN-AC first uses existing HIN-Embedding methods to obtain node topological embedding. Then it uses the topological relationship between nodes as guidance to complete attributes for no-attribute nodes by weighted aggregation of the attributes from these attributed nodes. Our complement mechanism can be easily combined with an arbitrary GNN-based heterogeneous model making the whole system end-to-end. We conduct extensive experiments on three real-world heterogeneous graphs. The results demonstrate the superiority of the proposed framework over state-of-the-art baselines.

Community detection has been extensively studied for various applications. Recent research has started to explore node contents to identify semantically meaningful communities. However, links in real networks typically have semantic descriptions and communities of links can better characterize community behaviors than communities of nodes. The second issue in community finding is that the most existing methods assume network topologies and descriptive contents carry the same or compatible information of node group membership, restricting them to one topic per community, which is generally violated in real networks. The third issue is that the existing methods use top ranked words or phrases to label topics when interpreting communities, which is often inadequate for comprehension. To address these issues altogether, we propose a new Bayesian probabilistic approach for modeling real networks and developing an efficient variational algorithm for model inference. Our new method explores the intrinsic correlation between communities and topics to discover link communities and extract semantically meaningful community summaries at the same time. If desired, it is able to derive more than one topical summary per community to provide rich explanations. We present experimental results to show the effectiveness of our new approach and evaluate the method by a case study.

Most of the existing Graph Neural Networks (GNNs) are deliberately designed for semi-supervised learning tasks, where supervision information (labelled node) is utilized to mitigate the oversmoothing problem of message passing. Unfortunately, the oversmoothing problem tends to be more severe in unsupervised tasks, since supervision information is not available. Since community structure/cluster is an essential characteristic of network, a natural approach to reduce the oversmoothing problem is to also constrain the node embeddings to maintain their own characteristics to prevent all the node embeddings from becoming too similar to be distinguished. In this paper, a novel Optimal Transport based Graph Neural Network (OT-GNN) is proposed to overcome the oversmoothing problem in unsupervised GNNs by imposing the equal-sized clustering constraints to the obtained node embeddings. To solve the combinatorial optimization problem, the constrained objective function of unsupervised GNN is relaxed to an Optimal Transport problem, and a fast version of the Sinkhorm-Knopp algorithm is adopted to handle large networks. Extensive experiments on node clustering and classification demonstrate the superior performance of our proposed OT-GNN.

Relevance has significant impact on user experience and business profit for e-commerce search platform. In this work, we propose a data-driven framework for search relevance prediction, by distilling knowledge from BERT and related multi-layer Transformer teacher models into simple feed-forward networks with large amount of unlabeled data. The distillation process produces a student model that recovers more than 97% test accuracy of teacher models on new queries, at a serving cost that's several magnitude lower (latency 150x lower than BERT-Base and 15x lower than the most efficient BERT variant, TinyBERT). The applications of temperature rescaling and teacher model stacking further boost model accuracy, without increasing the student model complexity. We present experimental results on both in-house e-commerce search relevance data as well as a public data set on sentiment analysis from the GLUE benchmark. The latter takes advantage of another related public data set of much larger scale, while disregarding its potentially noisy labels. Embedding analysis and case study on the in-house data further highlight the strength of the resulting model. By making the data processing and model training source code public, we hope the techniques presented here can help reduce energy consumption of the state of the art Transformer models and also level the playing field for small organizations lacking access to cutting edge machine learning hardwares.

Network embedding (NE), aiming to embed a network into a low dimensional latent representation while preserving the inherent structural properties of the network, has attracted considerable attention recently. Variational Autoencoder (VAE) has been widely studied for NE. Existing VAE based methods let the network follow a unimodal distribution, that is, they typically use some fixed distribution as the prior, e.g. Gaussian distribution. However, in reality networks often contain many complicated structural properties [5], [6] (such as the first/second order proximity, the motif or community structures, power-law, etc). The latent representation from unimodal and fixed distribution is not capable of describing such multi-modal characteristic of networks. To address this issue, we develop a new VAE method for NE, named Normalizing Flow Variational Graph Autoencoder (NF-VGA). We design a prior-generative module based on normalizing flows to generate flexible, multi-modal distribution as the prior of the latent representation. To make the generated prior better describe the coupling relationship between nodes, we further utilize network local structures to guide the prior generation. Extensive experiments on some real-world networks show a superior performance of the new approach over some state-of-the-art methods on some popular network embedding tasks.

Community detection is an important research field in the understanding of networks. The definition of network communities focuses on denser intracommunity links and sparpser intercommunity links. It cannot explain the fundamental generation mechanisms of the two types of links, which is challenging to reveal. Unfortunately, none of existing works can solve this challenge which is important for accurately modeling community structures. This paper investigates a typical category of networks which possess contents on links. Based on analyses of real networks, we get an observation that nodes with distinctive personality regarding content topics are more active across communities, while nodes without it are more active inside a community, behaving in a similar way known as homophily. This observation provides clues to the generation of intracommunity and intercommunity links. Based on above observation, this paper proposes a novel generative community detection model called GHIPT (Group Homophily and Individual Personality of Topics) by integrating group homophily and individual personality of topics. Besides deriving more precise community results by accurately modeling intracommunity and intercommunity links, GHIPT is able to identify those nodes with distinctive personality who are more willing to interact with others from different communities. It further validates that they change their community memberships more frequently. GHIPT is evaluated on two real networks, i.e., Reddit and DBLP. Experimental results show that it outperforms all the state-of-the-art baselines. In addition to case studies on above two datasets, a case study on COVID-19 dataset provides new insights to support the ongoing fight against COVID-19 pandemic.

Existing topic modeling approaches possess several issues, including the overfitting issue of Probablistic Latent Semantic Indexing (pLSI), the failure of capturing the rich topical correlations among topics in Latent Dirichlet Allocation (LDA), and high inference complexity. In this paper, we provide a new method to overcome the overfitting issue of pLSI by using the amortized inference with word embedding as input, instead of the Dirichlet prior in LDA. For generative topic model, the large number of free latent variables is the root of overfitting. To reduce the number of parameters, the amortized inference replaces the inference of latent variable with a function which possesses the shared (amortized) learnable parameters. The number of the shared parameters is fixed and independent of the scale of the corpus. To overcome the limited application of amortized inference to independent and identically distributed (i.i.d) data, a novel graph neural network, Graph Attention TOpic Network (GATON), is proposed to model the topic structure of non-i.i.d documents according to the following two observations. First, pLSI can be interpreted as stochastic block model (SBM) on a specific bi-partite graph. Second, graph attention network (GAT) can be explained as the semi-amortized inference of SBM, which relaxes the i.i.d data assumption of vanilla amortized inference. GATON provides a novel scheme, i.e. graph convolution operation based scheme, to integrate word similarity and word co-occurrence structure. Specifically, the bag-of-words document representation is modeled as a bi-partite graph topology. Meanwhile, word embedding, which captures the word similarity, is modeled as attribute of the word node and the term frequency vector is adopted as the attribute of the document node. Based on the weighted (attention) graph convolution operation, the word co-occurrence structure and word similarity patterns are seamlessly integrated for topic identification. Extensive experiments demonstrate that the effectiveness of GATON on topic identification not only benefits the document classification, but also significantly refines the input word embedding.

Overlapping community detection has triggered recent research in network analysis. One of the promising techniques for finding overlapping communities is the popular stochastic models, which, unfortunately, have some common drawbacks. They do not support an important observation that highly connected nodes are more likely to reside in the overlapping regions of communities in the network. These methods are in essence not truly unsupervised, since they require a threshold on probabilistic memberships to derive overlapping structures and need the number of communities to be specified a priori . We develop a new method to address these issues for overlapping community detection. We first present a stochastic model to accommodate the relative importance and the expected degree of every node in each community. We then infer every overlapping community by ranking the nodes according to their importance. Second, we determine the number of communities under the Bayesian framework. We evaluate our method and compare it with five state-of-the-art methods. The results demonstrate the superior performance of our method. We also apply this new method to two applications, showing its superb performance on practical problems.

Finding semantic communities using network topology and contents together is a hot topic in community detection. Existing methods often use word attributes in an indiscriminate way to help finding communities. Through analysis we find that, words in networked contents often embody a hierarchical semantic structure. Some words reflect a background topic of the whole network with all communities, some imply the high-level general topic covering several topic-related communities, and some imply the high-resolution specialized topic to describe each community. Ignoring such semantic structures often leads to defects in depicting networked contents where deep semantics are not fully utilized. To solve this problem, we propose a new Bayesian probabilistic model. By distinguishing words from either a background topic or some two-level topics (i.e., general and specialized topics), this model not only better utilizes the networked contents to help finding communities, but also provides a clearer multiplex semantic community interpretation. We then give an efficient variational algorithm for model inference. The superiority of this new approach is demonstrated by comparing with ten state-of-the-art methods on nine real networks and an artificial benchmark. A case study is further provided to show its strong ability in deep semantic interpretation of communities.

The rapid development of social media services has facilitated the communication of opinions through online news, blogs, microblogs, instant-messages, and so on. This article concentrates on the mining of readers' social sentiments evoked by social media materials. Existing methods are only applicable to a minority of social media like news portals with emotional voting information, while ignore the emotional contagion between writers and readers. However, incorporating such factors is challenging since the learned hidden variables would be very fuzzy (because of the short and noisy text in social networks). In this paper, we try to solve this problem by introducing a high-order network structure, i.e. communities. We first propose a new generative model called Community-Enhanced Social Sentiment Mining (CESSM), which 1) considers the emotional contagion between writers and readers to capture precise social sentiment, and 2) incorporates network communities to capture coherent topics. We then derive an inference algorithm based on Gibbs sampling. Empirical results show that, CESSM achieves significantly superior performance against the state-of-the-art techniques for text sentiment classification and interestingness in social sentiment mining.

Topic models have many important applications in fields such as Natural Language Processing. Topic embedding modelling aims at introducing word and topic embeddings into topic models to describe correlations between topics. Existing topic embedding methods use documents alone, which suffer from the topical fuzziness problem brought by the introduction of embeddings of semantic fuzzy words, e.g. polysemous words or some misleading academic terms. Links often exist between documents which form document networks. The use of links may alleviate this semantic fuzziness, but they are sparse and noisy which may meanwhile mislead topics. In this paper, we utilize community structure to solve these problems. It can not only alleviate the topical fuzziness of topic embeddings since communities are often believed to be topic related, but also can overcome the drawbacks brought by the sparsity and noise of networks (because community is a high-order network information). We give a new generative topic embedding model which incorporates documents (with topics) and network (with communities) together, and uses probability transition to describe the relationship between topics and communities to make it robust when topics and communities do not match. An efficient variational inference algorithm is then proposed to learn the model. We validate the superiority of our new approach on two tasks, document classifications and visualization of topic embeddings, respectively.

In social network analysis, community detection is a basic step to understand the structure, function and semantics of networks. Some conventional community detection methods may have limited performance because they merely focus on topological structure of networks. In addition to topology, content information is another significant aspect of social networks. Some state-of-the-art methods started to combine these two aspects of information, but they often assume that topology and content share the same characteristics. However, for some examples of social networks, content may mismatch with topological structure. In order to better cope with such situations, we introduce a novel community detection method under the framework of non-negative matrix factorization (NMF). Our proposed method integrates topology and content of networks, and introduces a novel adaptive parameter for controlling the contribution of content with respect to the identified mismatch degree between the topological and content information. The case study using real social networks show that our new method can simultaneously obtain community partition and the corresponding semantic descriptions. Experiments on both artificial networks and real social networks further indicate that our method outperforms some state-of-the-art methods while exhibiting more robust behaviour when the mismatch topological and content information is observed.