Mixed-Integer Linear Programming (MILP) is a cornerstone of combinatorial optimization, yet solving large-scale instances remains a significant computational challenge. Recently, Graph Neural Networks (GNNs) have shown promise in accelerating MILP solvers by predicting high-quality solutions. However, we identify that existing methods misalign with the intrinsic structure of MILP problems at two levels. At the leaning objective level, the Binary Cross-Entropy (BCE) loss treats variables independently, neglecting their relative priority and yielding plausible logits. At the model architecture level, standard GNN message passing inherently smooths the representations across variables, msking the natural competitive relationships within constraints. To address these challenges, we propose CoCo-MILP, which explicitly models inter-variable Contrast and intra-constraint Competition for advanced MILP solution prediction. At the objective level, CoCo-MILP introduces the Inter-Variable Contrastive Loss (VCL), which explicitly maximizes the embedding margin between variables assigned one versus zero. At the architectural level, we design an Intra-Constraint Competitive GNN layer that, instead of homogenizing features, learns to differentiate representations of competing variables within a constraint, capturing their exclusionary nature. Experimental results on standard benchmarks demonstrate that CoCo-MILP significantly outperforms existing learning-based approaches, reducing the solution gap by up to 68.12% compared to traditional solvers.

Mixed-Integer Linear Programming (MILP) is a fundamental and powerful framework for modeling complex optimization problems across diverse domains. Recently, learning-based methods have shown great promise in accelerating MILP solvers by predicting high-quality solutions. However, most existing approaches are developed and evaluated in single-domain settings, limiting their ability to generalize to unseen problem distributions. This limitation poses a major obstacle to building scalable and general-purpose learning-augmented solvers. To address this challenge, we introduce RoME, a domain-Robust Mixture-of-Experts (MoE) framework for predicting MILP solutions across domains. RoME dynamically routes problem instances to specialized experts based on learned task embeddings. The model is trained using a two-level distributionally robust optimization strategy: inter-domain to mitigate global shifts across domains, and intra-domain to enhance local robustness by introducing perturbations on task embeddings. We reveal that cross-domain training not only enhances the model's generalization capability to unseen domains but also improves performancewithin each individual domain by encouraging the model to capture more general intrinsic combinatorial patterns. Specifically, a single RoME model trained on three domains achieves an average improvement of $67.7\%$ then evaluated on five diverse domains. We further test the pretrained model on MIPLIB in a zero-shot setting, demonstrating its ability to deliver measurable performance gains on challenging real-world instances where existing learning-based approaches often struggle to generalize.

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.

Abstract Maximizing influences in complex networks is a practically important but computationally challenging task for social network analysis, due to its nondeterministic polynomial time (NP)-hard nature. Most current approximation or heuristic methods either require tremendous human design efforts or achieve unsatisfying balances between effectiveness and efficiency. Recent machine learning attempts only focus on speed but lack performance enhancement. In this paper, different from previous attempts, we propose an effective deep reinforcement learning model that achieves superior performances over traditional best influence maximization algorithms. Specifically, we design an end-to-end learning framework that combines graph neural network as the encoder and reinforcement learning as the decoder, named DREIM. Through extensive training on small synthetic graphs, DREIM outperforms the state-of-the-art baseline methods on very large synthetic and real-world networks on solution quality, and we also empirically show its linear scalability with regard to the network size, which demonstrates its superiority in solving this problem.

Heterogeneous Information Networks (HINs) are information networks with multiple types of nodes and edges. The concept of meta-path, i.e., a sequence of entity types and relation types connecting two entities, is proposed to provide the meta-level explainable semantics for various HIN tasks. Traditionally, meta-paths are primarily used for schema-simple HINs, e.g., bibliographic networks with only a few entity types, where meta-paths are often enumerated with domain knowledge. However, the adoption of meta-paths for schema-complex HINs, such as knowledge bases (KBs) with hundreds of entity and relation types, has been limited due to the computational complexity associated with meta-path enumeration. Additionally, effectively assessing meta-paths requires enumerating relevant path instances, which adds further complexity to the meta-path learning process. To address these challenges, we propose SchemaWalk, an inductive meta-path learning framework for schema-complex HINs. We represent meta-paths with schema-level representations to support the learning of the scores of meta-paths for varying relations, mitigating the need of exhaustive path instance enumeration for each relation. Further, we design a reinforcement-learning based path-finding agent, which directly navigates the network schema (i.e., schema graph) to learn policies for establishing meta-paths with high coverage and confidence for multiple relations. Extensive experiments on real data sets demonstrate the effectiveness of our proposed paradigm.

Over recent years, a number of knowledge graphs (KGs) have emerged. Nevertheless, a KG can never reach full completeness. A viable approach to increase the coverage of a KG is KG alignment (KGA). The majority of previous efforts merely focus on the matching between entities, while largely neglect relations. Besides, they heavily rely on labeled data, which are difficult to obtain in practice. To address these issues, in this work, we put forward a general framework to simultaneously align entities and relations under scarce supervision. Our proposal consists of two main components, relation-enhanced active instance selection (RAS), and cross-view contrastive learning (CCL). RAS aims to select the most valuable instances to be labeled with the guidance of relations, while CCL contrasts cross-view representations to augment scarce supervision signals. Our proposal is agnostic to the underlying entity and relation alignment models, and can be used to improve their performance under limited supervision. We conduct experiments on a wide range of popular KG pairs, and the results demonstrate that our proposed model and its components can consistently boost the alignment performance under scarce supervision.

Large knowledge graphs often grow to store temporal facts that model the dynamic relations or interactions of entities along the timeline. Since such temporal knowledge graphs often suffer from incompleteness, it is important to develop time-aware representation learning models that help to infer the missing temporal facts. While the temporal facts are typically evolving, it is observed that many facts often show a repeated pattern along the timeline, such as economic crises and diplomatic activities. This observation indicates that a model could potentially learn much from the known facts appeared in history. To this end, we propose a new representation learning model for temporal knowledge graphs, namely CyGNet, based on a novel time-aware copy-generation mechanism. CyGNet is not only able to predict future facts from the whole entity vocabulary, but also capable of identifying facts with repetition and accordingly predicting such future facts with reference to the known facts in the past. We evaluate the proposed method on the knowledge graph completion task using five benchmark datasets. Extensive experiments demonstrate the effectiveness of CyGNet for predicting future facts with repetition as well as de novo fact prediction.

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.