Heterogeneous Information Networks (HINs) encapsulate diverse entity and relation types, with meta-paths providing essential meta-level semantics for knowledge reasoning, although their utility is constrained by discovery challenges. While Large Language Models (LLMs) offer new prospects for meta-path discovery due to their extensive knowledge encoding and efficiency, their adaptation faces challenges such as corpora bias, lexical discrepancies, and hallucination . This paper pioneers the mitigation of these challenges by presenting EvoPath, an innovative framework that leverages LLMs to efficiently identify high-quality meta-paths. EvoPath is carefully designed, with each component aimed at addressing issues that could lead to potential knowledge conflicts. With a minimal subset of HIN facts, EvoPath iteratively generates and evolves meta-paths by dynamically replaying meta-paths in the buffer with prioritization based on their scores. Comprehensive experiments on three large, complex HINs with hundreds of relations demonstrate that our framework, EvoPath, enables LLMs to generate high-quality meta-paths through effective prompting, confirming its superior performance in HIN reasoning tasks. Further ablation studies validate the effectiveness of each module within the framework.

Graph neural networks (GNNs) are effective machine learning models for many graph-related applications. Despite their empirical success, many research efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive power. Early works in this domain mainly focus on studying the graph isomorphism recognition ability of GNNs, and recent works try to leverage the properties such as subgraph counting and connectivity learning to characterize the expressive power of GNNs, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for models for enhancing expressive power under different forms of definition. Concretely, the models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.

Inferring the fine-grained urban flows based on the coarse-grained flow observations is practically important to many smart city-related applications. Adequate data is usually a prerequisite for existing machine learning methods, especially most deep learning models. However, many cities still suffer from the data scarcity issue due to the unbalanced city development levels. To mitigate this issue, we propose a novel cross-city fine-grained urban flow inference model named FGITrans, which aims to effectively transfer the knowledge from the data-rich cities to the data-scarce cities. Specifically, we design a weight-sharing triple-branch transformer framework which adopts self-attention and cross-attention for source/target city feature learning and domain alignment, respectively. Then, we propose a novel spatio-temporal adaptive embedding (STAE) layer for our transformer framework, and introduce a cross-city knowledge distillation (CKD) loss to narrow the cross-city disparities. The CKD loss explicitly enforces the framework to learn the discriminative domain-specific and domain-invariant representations simultaneously. Extensive experiments conducted on four large real-world datasets validate the effectiveness of FGITrans compared with the state-of-the-art baselines.

Many complex problems encountered in both production and daily life can be conceptualized as combinatorial optimization problems (COPs). Many ad-hoc deep learning methods have been proposed to solve these problems, but there still lacks an effective unified framework. In this work, we take a step towards this goal by designing an unified end-to-end deep reinforcement learning framework named CONQUER. CONQUER first translates various COPs into the unified QUBO (Quadratic Unconstrained Binary Optimization) formalization, and afterwards trains a neural QUBO solver to search high-quality strategies, which are then checked and repaired to obtain the solutions for original COPs. The QUBO solver is a purely data-driven neural model, which does not rely on any expert inputs. We adopt the graph transformer network to represent the QUBO graph, so as to effectively capture the features of problem objective and constraints. The Deep Q-network is utilized to train the QUBO solver to find long-sighted solution strategies. Despite being trained solely on small synthetic graphs, CONQUER exhibits promising generality on much larger instances, and can be easily adapted to real-world datasets. Experimentally, we show that CONQUER achieves the state-of-the-art performances on four COPs over graphs, including minimum vertex cover, maximum independent set, maximum clique and maximum cut problem.

The combinatorial optimization problems (COPs) over graph are of great significance both in theory and practice, covering a wide range of scenarios in daily life and industrial production. Recent years, reinforcement learning (RL) based models have emerged as a promising direction, which treat solving the COPs as a heuristic learning problem. However, current finite-horizon Markov Decision Process (MDP) based RL models are not allowed to explore adquately for improving solutions at test time, which may be necessary given the complexity of NP-hard optimization tasks. Some recent attempts solve this issue by focusing on reward design and state feature engineering, which are tedious and ad-hoc. To address this challenge, we introduce a physics-inspired technique called gauge transformation (GT), which is highly effective in enabling RL agents to explore and continuously enhance solution quality during testing. GT seamlessly transforms any state within the MDP back to its initial state, allowing the RL agent to continue exploration within the transformed space. Empirically, we demonstrate that traditional RL models equipped with the GT technique achieve the SOTA performance on the MaxCut problem. Moreover, GT is exclusively applied during testing and does not alter the training phase of the model. It can be readily integrated into existing RL models, providing a pathway for more effective exploration in solving the COPs.

Entity alignment (EA) is the task of detecting equivalent entities from different knowledge graphs (KGs). Although this problem has been intensively studied during the last few years, the majority of the state-of-the-arts heavily rely on the labeled data, which are difficult to obtain in practice. Therefore, it calls for the study of EA with scarce supervision. To resolve this issue, we put forward a reinforced active entity alignment framework to select the entities to be manually labeled with the aim of enhancing alignment performance with minimal labeling efforts. Under this framework, we further devise an unsupervised contrastive loss to contrast different views of entity representations and augment the limited supervision signals by exploiting the vast unlabeled data. We empirically evaluate our proposal on eight popular KG pairs, and the results demonstrate that our proposed model and its components consistently boost the alignment performance under scarce supervision.

Betweenness centrality (BC) is a widely used centrality measures for network analysis, which seeks to describe the importance of nodes in a network in terms of the fraction of shortest paths that pass through them. It is key to many valuable applications, including community detection and network dismantling. Computing BC scores on large networks is computationally challenging due to its high time complexity. Many sampling-based approximation algorithms have been proposed to speed up the estimation of BC. However, these methods still need considerable long running time on large-scale networks, and their results are sensitive to even small perturbation to the networks. In this paper, we focus on the efficient identification of top-k nodes with highest BC in a graph, which is an essential task to many network applications. Different from previous heuristic methods, we turn this task into a learning problem and design an encoder-decoder based framework as a solution. Specifically, the encoder leverages the network structure to represent each node as an embedding vector, which captures the important structural information of the node. The decoder transforms each embedding vector into a scalar, which identifies the relative rank of a node in terms of its BC. We use the pairwise ranking loss to train the model to identify the orders of nodes regarding their BC. By training on small-scale networks, the model is capable of assigning relative BC scores to nodes for much larger networks, and thus identifying the highly-ranked nodes. Experiments on both synthetic and real-world networks demonstrate that, compared to existing baselines, our model drastically speeds up the prediction without noticeable sacrifice in accuracy, and even outperforms the state-of-the-arts in terms of accuracy on several large real-world networks.

Crime analysis has been widely studied, but problem of identifying conspirators through communication network analysis is still not well resolved. In this paper, we proposed a fuzzy clustering algorithm to detect hidden criminals from topic network, which took no use of individuals' prior identity information. We first built up a local suspicion calculation from nodes' neighboring information (node and edge); and then with global information, we employed the fuzzy k-means clustering algorithm, and made the membership to suspicious group as the global suspicion degree. Experiments showed it works well on identification: known suspects gained relative high values and known innocents got relative low values.