Large language models (LLMs) have demonstrated exceptional performance across a wide variety of domains. Nonetheless, generalist LLMs continue to fall short in reasoning tasks necessitating specialized knowledge, e.g., emotional sociology and medicine. Prior investigations into specialized LLMs focused on domain-specific training, which entails substantial efforts in domain data acquisition and model parameter fine-tuning. To address these challenges, this paper proposes the Way-to-Specialist (WTS) framework, which synergizes retrieval-augmented generation with knowledge graphs (KGs) to enhance the specialized capability of LLMs in the absence of specialized training. In distinction to existing paradigms that merely utilize external knowledge from general KGs or static domain KGs to prompt LLM for enhanced domain-specific reasoning, WTS proposes an innovative ''LLM↻KG'' paradigm, which achieves bidirectional enhancement between specialized LLM and domain knowledge graph (DKG). The proposed paradigm encompasses two closely coupled components: the DKG-Augmented LLM and the LLM-Assisted DKG Evolution. The former retrieves question-relevant domain knowledge from DKG and uses it to prompt LLM to enhance the reasoning capability for domain-specific tasks; the latter leverages LLM to generate new domain knowledge from processed tasks and use it to evolve DKG. WTS closes the loop between DKG-Augmented LLM and LLM-Assisted DKG Evolution, enabling continuous improvement in the domain specialization as it progressively answers and learns from domain-specific questions. We validate the performance of WTS on 7 datasets (e.g., TweetQA, ChatDoctor5k) spanning 6 domains, e.g., emotional sociology, medical, ect. The experimental results show that WTS surpasses the previous SOTA in 5 specialized domains, and achieves a maximum performance improvement of 11.3%.

This paper proposes Meta Parallel Graph Neural Network (MPGNN) to establish a scalable Network Intrusion Detection System (NIDS) for large-scale Internet of Things (IoT) networks. MPGNN leverages a meta-learning framework to optimize the parallelism of GNN-based NIDS. The core of MPGNN is a coalition formation policy that generates meta-knowledge for partitioning a massive graph into multiple coalitions/subgraphs in a way that maximizes the performance and efficiency of parallel coalitional NIDSs. We propose an offline reinforcement learning algorithm, called Graph-Embedded Adversarially Trained Actor-Critic (G-ATAC), to learn a coalition formation policy that jointly optimizes intrusion detection accuracy, communication overheads, and computational complexities of coalitional NIDSs. In particular, G-ATAC learns to capture the temporal dependencies of network states and coalition formation decisions over offline data, eliminating the need for expensive online interactions with large IoT networks. Given generated coalitions, MPGNN employs E-GraphSAGE to establish coalitional NIDSs which then collaborate via ensemble prediction to accomplish intrusion detection for the entire network. We evaluate MPGNN on two real-world datasets. The experimental results demonstrate the superiority of our method with substantial improvements in F1 score, surpassing the state-of-the-art methods by 0.38 and 0.29 for the respective datasets. Compared to the centralized NIDS, MPGNN reduces the training time of NIDS by 41.63% and 22.11%, while maintaining an intrusion detection performance comparable to centralized NIDS.

Temporal graphs are ubiquitous data structures in many scenarios, including social networks, user-item interaction networks, etc. In this paper, we focus on predicting the exact time of future interactions between node pairs on a temporal graph. This problem can support interesting applications including time-sensitive items recommendation, congestion prediction on road networks, etc. We present the Graph Neural Point Process (GNPP) to tackle this problem. GNPP relies on the graph neural message passing and the temporal point process framework. Most previous graph neural models devised for temporal graphs either utilize the chronological order information or rely on specific point process models, ignoring the exact timestamps and complicated temporal patterns. In GNPP, we adapt a time encoding scheme to map real-valued timestamps to a high-dimensional vector space so that the temporal information can be modeled precisely. Further, GNPP considers the structural information of graphs by conducting message passing aggregation on the constructed line graph. The obtained representation defines a neural conditional intensity function that models events’ generation mechanisms for predicting interactions’ time between node pairs. We evaluate this model on several synthetic and real-world temporal graphs where it outperforms recently proposed neural point process models and graph neural models devised for temporal graphs. We further conduct ablation comparisons and visual analyses to shed some light on the learned model and understand the functionality of important components comprehensively.

With the empirical success of Graph Neural Networks (GNNs) on graph-related tasks, it is intriguing to investigate their theoretical power on these tasks. In this paper, we focus on GNNs’ theoretical power on substructure counting, a fundamental yet challenging task in many applications. Previous works have proven that the 2-dimensional Weisfeiler-Leman algorithm (2-WL) equivalent GNNs can only count limited substructures. However, the substructure counting ability of theoretically more powerful and computationally tractable GNNs remains unclear. In this paper, we study conditions for substructures to be theoretically countable by k-WL equivalent GNNs, and then focus on 3-WL equivalent ones, which are currently the most theoretically powerful instances with practical computational cost. Further, we propose an algorithm to determine the countability of substructures for 3-WL equivalent GNNs. Our results reveal that 3-WL equivalent GNNs can count considerably more substructures than 2-WL equivalent ones. However, the proportion of countable patterns and prediction performance decrease as the pattern size increases. Therefore, we propose a Layer Permutation Pooling (LPP) model for better substructure counting performance. LPP first decomposes the data graph into subgraphs. Then we propose a layer permutation scheme to represent each decomposed subgraph as a set of matrices. Finally, LPP utilizes a neural network to conduct predictions on matrices. We compare LPP with several state-of-the-art GNNs on various datasets. Experimental results show that LPP outperforms baselines by 84% on average with the RMSE metric.

In many route planning applications, finding constrained shortest paths (CSP) is an important and fundamental problem. CSP aims to find the shortest path between two nodes on a graph while satisfying a path constraint. Solving CSPs requires a large search space and is prohibitively slow on large graphs, even with the state-of-the-art parallel solution on GPUs. The reason lies in the lack of effective navigational information and pruning strategies in the search procedure. In this paper, we propose SPEC, a Shortest Path Enhanced approach for solving the exact CSP problem. Our design rationales of SPEC rely on the observation that the shortest path (SP) provides valuable information in the search procedure of CSP. Hence, we propose a label priority that distinguishes promising candidate paths based on SP. We further devise efficient pruning and teleporting strategies utilizing SP lengths and costs, which eliminates unfeasible paths at an early stage. Furthermore, we observe that the expansion number at each search iteration affects the overall performance significantly. Thus, we devise an adaptive controller based on reinforcement learning. We also show that SPEC works seamlessly with the parallel implementation. Extensive experimental results on 8 read-world graphs reveal that single thread SPEC achieves an order of magnitude speedup over the state-of-the-art GPU-based method. The parallel implementation boosts SPEC 3 to 5 times further.

Link prediction is a fundamental task for graph analysis and the topic has been studied extensively for static or dynamic graphs. Essentially, the link prediction is formulated as a binary classification problem about two nodes. However, for temporal graphs, links (or interactions) among node sets appear in sequential orders. And the orders may lead to interesting applications. While a binary link prediction formulation fails to handle such an order-sensitive case. In this paper, we focus on such an interaction order prediction problem among a given node set on temporal graphs. For the technical aspect, we develop a graph neural network model named Temporal ATtention network (TAT), which utilizes the fine-grained time information on temporal graphs by encoding continuous real-valued timestamps as vectors. For each transformation layer of the model, we devise an attention mechanism to aggregate neighborhoods' information based on their representations and time encodings attached to their specific edges. We also propose a novel training scheme to address the permutation-sensitive property of the problem. Experiments on several real-world temporal graphs reveal that TAT outperforms some state-of-the-art graph neural networks by 55% on average under the AUC metric.

Influence diffusion estimation is a crucial problem in social network analysis. Most prior works mainly focus on predicting the total influence spread, i.e., the expected number of influenced nodes given an initial set of active nodes (aka. seeds). However, accurate estimation of susceptibility, i.e., the probability of being influenced for each individual, is more appealing and valuable in real-world applications. Previous methods generally adopt Monte Carlo simulation or heuristic rules to estimate the influence, resulting in high computational cost or unsatisfactory estimation error when these methods are used to estimate susceptibility. In this work, we propose to leverage graph neural networks (GNNs) for predicting susceptibility. As GNNs aggregate multi-hop neighbor information and could generate over-smoothed representations, the prediction quality for susceptibility is undesirable. To address the shortcomings of GNNs for susceptibility estimation, we propose a novel DeepIS model with a two-step approach: (1) a coarse-grained step where we estimate each node's susceptibility coarsely; (2) a fine-grained step where we aggregate neighbors' coarse-grained susceptibility estimations to compute the fine-grained estimate for each node. The two modules are trained in an end-to-end manner. We conduct extensive experiments and show that on average DeepIS achieves five times smaller estimation error than state-of-the-art GNN approaches and two magnitudes faster than Monte Carlo simulation.