Large Reasoning Models (LRMs) have recently achieved remarkable success in complex reasoning tasks.However, closer scrutiny reveals persistent failure modes compromising performance and cost: I) Intra-step level, marked by calculation or derivation errors; II) Inter-step level, involving oscillation and stagnation; and III) Instance level, causing maladaptive over-thinking.Existing endeavors target isolated levels without unification, while their black-box nature and reliance on RL hinder explainability and controllability.To bridge these gaps, we conduct an in-depth white-box analysis, identifying key neurons (Mixture of Neurons, MoN) and their fluctuation patterns associated with distinct failures.Building upon these insights, we propose NeuReasoner, an explainable, controllable, and unified reasoning framework driven by MoN.Technically, NeuReasoner integrates lightweight MLPs for failure detection with a special token-triggered self-correction mechanism learned via SFT.During inference, special tokens are inserted upon failure detection to actuate controllable remedial behaviors.Extensive evaluations across six benchmarks, six backbone models (8B∼70B) against nine competitive baselines, demonstrate that NeuReasoner achieves performance gains of up to 27.0% while reducing token consumption by 19.6% ∼ 63.3%.... Correct Answer...

Recent Large Reasoning Models (LRMs) likeDeepSeek-R1 have demonstrated remarkable success in complex reasoning tasks, exhibiting human-like patterns in exploring multiple alternative solutions.Upon closer inspection, however, we uncover a surprising phenomenon: The First is The Best, where alternative solutions are not merely suboptimal but potentially detrimental.This observation challenges widely accepted test-time scaling laws, leading us to hypothesize that errors within the reasoning path scale concurrently with test time.Through comprehensive empirical analysis, we characterize errors as a forest-structured Forest of Errors (FoE) and conclude that FoE makes the First the Best, which is underpinned by rigorous theoretical analysis.Leveraging these insights, we propose RED, a self-guided efficient reasoning framework comprising two components: I) Refining First, which suppresses FoE growth in the first solution; and II) Discarding Subs, which prunes subsequent FoE via dualconsistency.Extensive experiments across five benchmarks and six backbone models demonstrate that RED outperforms eight competitive baselines, achieving performance gains of up to 19.0% while reducing token consumption by 37.7% ∼ 70.4%.Moreover, comparative experiments on FoE metrics shed light on how RED achieves effectiveness.... ... ...

Graph Neural Networks (GNNs) have shown remarkable capability in modeling complex relational data, yet their effectiveness is constrained by subtle but critical limitations in the message-passing paradigm. We identify a fundamental issue -- termed aggregation collapse -- arising from the aggregation step that combines representations of central and neighboring nodes with varying sizes. This bottleneck manifests in two forms of inherent information loss: (i) feature information loss, occurring when value distributions in learned representations become concentrated and indistinguishable after aggregation, and (ii) structure information loss, where variable node degrees are obscured by aggregation functions. To address these challenges, we propose complementary solutions: (i) nonlinear feature mapping and distribution re-scaler, which diversify input feature distributions prior to aggregation to preserve valuable feature-level details, and (ii) post-aggregation structural encoding, which retains essential structure information. Our methods are theoretically grounded, easy to implement, and broadly applicable to existing GNN models. Empirical evaluations demonstrate that our techniques successfully alleviate aggregation collapse, leading to improved performance and scalability in GNNs.

Human values and their measurement are long-standing interdisciplinary inquiry. Recent advances in AI have sparked renewed interest in this area, with large language models (LLMs) emerging as both tools and subjects of value measurement. This work introduces Generative Psychometrics for Values (GPV), an LLM-based, data-driven value measurement paradigm, theoretically grounded in text-revealed selective perceptions. The core idea is to dynamically parse unstructured texts into perceptions akin to static stimuli in traditional psychometrics, measure the value orientations they reveal, and aggregate the results. Applying GPV to human-authored blogs, we demonstrate its stability, validity, and superiority over prior psychological tools. Then, extending GPV to LLM value measurement, we advance the current art with 1) a psychometric methodology that measures LLM values based on their scalable and free-form outputs, enabling context-specific measurement; 2) a comparative analysis of measurement paradigms, indicating response biases of prior methods; and 3) an attempt to bridge LLM values and their safety, revealing the predictive power of different value systems and the impacts of various values on LLM safety. Through interdisciplinary efforts, we aim to leverage AI for next-generation psychometrics and psychometrics for value-aligned AI.

Values are core drivers of individual and collective perception, cognition, and behavior. Value systems, such as Schwartz’s Theory of Basic Human Values, delineate the hierarchy and interplay among these values, enabling cross-disciplinary investigations into decision-making and societal dynamics. Recently, the rise of Large Language Models (LLMs) has raised concerns regarding their elusive intrinsic values. Despite growing efforts in evaluating, understanding, and aligning LLM values, a psychologically grounded LLM value system remains underexplored. This study addresses the gap by introducing the Generative Psycho-Lexical Approach (GPLA), a scalable, adaptable, and theoretically informed method for constructing value systems. Leveraging GPLA, we propose a psychologically grounded five-factor value system tailored for LLMs. For systematic validation, we present three benchmarking tasks that integrate psychological principles with cutting-edge AI priorities. Our results reveal that the proposed value system meets standard psychological criteria, better captures LLM values, improves LLM safety prediction, and enhances LLM alignment, when compared to the canonical Schwartz’s values.

Heterogeneous graphs (HGs) are common in real-world scenarios and often exhibit heterophily. However, most existing studies focus on either heterogeneity or heterophily in isolation, overlooking the prevalence of heterophilic HGs in practical applications. Such ignorance leads to their performance degradation. In this work, we first identify two main challenges in modeling heterophily HGs: (1) varying heterophily distributions across hops and meta-paths; (2) the intricate and often heterophily-driven diversity of semantic information across different meta-paths. Then, we propose the Adaptive Heterogeneous Graph Neural Network (AHGNN) to tackle these challenges. AHGNN employs a heterophily-aware convolution that accounts for heterophily distributions specific to both hops and meta-paths. It then integrates messages from diverse semantic spaces using a coarse-to-fine attention mechanism, which filters out noise and emphasizes informative signals. Experiments on seven real-world graphs and twenty baselines demonstrate the superior performance of AHGNN, particularly in high-heterophily situations.

The rapid evolution of large language models (LLMs) has revolutionized various fields, including the identification and discovery of human values within text data. While traditional NLP models, such as BERT, have been employed for this task, their ability to represent textual data is significantly outperformed by emerging LLMs like GPTs. However, the performance of online LLMs often degrades when handling long contexts required for value identification, which also incurs substantial computational costs. To address these challenges, we propose EAVIT, an efficient and accurate framework for human value identification that combines the strengths of both locally fine-tunable and online black-box LLMs. Our framework employs a value detector—a small, local language model—to generate initial value estimations. These estimations are then used to construct concise input prompts for online LLMs, enabling accurate final value identification. To train the value detector, we introduce explanation-based training and data generation techniques specifically tailored for value identification, alongside sampling strategies to optimize the brevity of LLM input prompts. Our approach effectively reduces the number of input tokens by up to 1/6 compared to directly querying online LLMs, while consistently outperforming traditional NLP methods and other LLM-based strategies.

Combinatorial optimization (CO) is fundamental to several realworld applications, from logistics and scheduling to hardware design and resource allocation.Deep reinforcement learning (RL) has recently shown significant benefits in solving CO problems, reducing reliance on domain expertise and improving computational efficiency.However, the absence of a unified benchmarking framework leads to inconsistent evaluations, limits reproducibility, and increases engineering overhead, raising barriers to adoption for new researchers.To address these challenges, we introduce RL4CO, a unified and extensive benchmark with in-depth library coverage of 27 CO problem environments and 23 state-of-the-art baselines.Built on efficient software libraries and best practices in implementation, RL4CO features modularized implementation and flexible configurations of diverse environments, policy architectures, RL algorithms, and utilities with extensive documentation.RL4CO helps researchers build on existing successes while exploring and developing their own designs, facilitating the entire research process by decoupling science from heavy engineering.We finally provide extensive benchmark studies to inspire new insights and future work.RL4CO has already attracted numerous researchers in the community and is open-sourced at https://github.com/ai4co/rl4co 1 .

Global placement, a critical step in designing the physical layout of computer chips, is essential to optimize chip performance. Prior global placement methods optimize each circuit design individually from scratch. Their neglect of transferable knowledge limits solution efficiency and chip performance as circuit complexity drastically increases. This study presents TransPlace, a global placement framework that learns to place millions of mixed-size cells in continuous space. TransPlace introduces i) Netlist Graph to efficiently model netlist topology, ii) Cell-flow and relative position encoding to learn SE(2)-invariant representation, iii) a tailored graph neural network architecture for informed parameterization of placement knowledge, and iv) a two-stage strategy for coarse-to-fine placement. Compared to state-of-the-art placement methods, TransPlace-trained on a few high-quality placements-can place unseen circuits with 1.2x speedup while reducing congestion by 30%, timing by 9%, and wirelength by 5%.

Low-Rank Adaptation (LoRA) is a widely adopted parameter-efficient fine-tuning (PEFT) method validated across NLP and CV domains. However, LoRA faces an inherent low-rank bottleneck: narrowing its performance gap with full fine-tuning requires increasing the rank of its parameter matrix, resulting in significant parameter overhead. Recent linear LoRA variants have attempted to enhance expressiveness by introducing additional linear mappings; however, their composition remains inherently linear and fails to fundamentally improve LoRA’s representational capacity. To address this limitation, we propose \ourmethod, which incorporates an Adaptive Nonlinear Layer (ANL) between two linear projectors to capture \emph{fixed} and \emph{learnable} nonlinearities. This combination forms an {\fontfamily{lmtt}\selectfont \textbf{MLP-like structure}} with a compressed rank, enabling flexible and precise approximation of diverse target functions while theoretically guaranteeing lower approximation errors and bounded gradients. Extensive experiments on 22 datasets and 6 pretrained models demonstrate that \ourmethod: (\textbf{I}) not only matches or surpasses full fine-tuning performance with only $6.18\%\sim25\%$ of LoRA’s parameters but also (\textbf{II}) outperforms state-of-the-art PEFT methods by up to $10.88\%$ in both NLP and CV tasks, and \textbf{(III)} exhibits robust performance across various rank configurations.

The ''pre-train then fine-tune'' approach has advanced GNNs by enabling general knowledge capture without task-specific labels. However, an objective gap between pre-training and downstream tasks limits its effectiveness. Recent graph prompting methods aim to close this gap through task reformulations and learnable prompts. Despite this, they struggle with complex graphs like heterophily graphs. Freezing the GNN encoder can reduce the impact of prompting, while simple prompts fail to handle diverse hop-level distributions. This paper identifies two key challenges in adapting graph prompting methods for complex graphs: (i) adapting the model to new distributions in downstream tasks to mitigate pre-training and fine-tuning discrepancies from heterophily and (ii) customizing prompts for hop-specific node requirements. To overcome these challenges, we propose Distribution-aware Graph Prompt Tuning (DAGPrompT), which integrates a GLoRA module for optimizing the GNN encoder's projection matrix and message-passing schema through low-rank adaptation. DAGPrompT also incorporates hop-specific prompts accounting for varying graph structures and distributions among hops. Evaluations on 10 datasets and 14 baselines demonstrate that DAGPrompT improves accuracy by up to 4.79% in node and graph classification tasks, setting a new state-of-the-art while preserving efficiency. Codes are available at https://github.com/Cqkkkkkk/DAGPrompT GitHub.

Recommendation systems typically rely on users’ historical behavior to infer their preferences. However, when new entries emerge, the system cannot make accurate prediction due to the lack of historical data. This is known as the “cold-start” problem, which not only limits the exposure of new items but also impacts the first experience of new users severely. Meta-learning has emerged as a promising approach to address this issue, but existing methods have limitations in dealing with the differences in user preferences and sparse monitoring data. To overcome these limitations, Dual enhanced Meta-learning with Adaptive Task Sampling is proposed. First, we propose an embedding enhancement strategy for cold nodes. Specifically, we map the cold-start embeddings into the warm space based on the common features shared across all nodes, and then add uniform noise to create the contrastive views. This strategy injects warm co-occurrence signals into the content of cold nodes, effectively enriching the feature space of cold nodes. Second, we introduce an adaptive task scheduler to measure the effectiveness of different meta-tasks and filter out the noise from invalid tasks. We assign different sampling probabilities to the tasks based on the learning process (gradient similarity) and the learning result (loss) of the meta-tasks. Finally, we consider the above two modules as auxiliary tasks for the main meta-model. Then, joint optimization is carried out through a multi-task learning framework. Experiments in three cold-start scenarios show that our approach outperforms the most advanced baselines, including traditional methods, HIN-based methods, and meta-learning-based methods.

Large Language Models (LLMs) are transforming diverse fields and gaining increasing influence as human proxies.This development underscores the urgent need for evaluating value orientations and understanding of LLMs to ensure their responsible integration into public-facing applications.This work introduces ValueBench, the first comprehensive psychometric benchmark for evaluating value orientations and value understanding in LLMs.ValueBench collects data from 44 established psychometric inventories, encompassing 453 multifaceted value dimensions.We propose an evaluation pipeline grounded in realistic human-AI interactions to probe value orientations, along with novel tasks for evaluating value understanding in an open-ended value space.With extensive experiments conducted on six representative LLMs, we unveil their shared and distinctive value orientations and exhibit their ability to approximate expert conclusions in value-related extraction and generation tasks.ValueBench is openly accessible at https://github.com/Value4AI/ValueBench.

Graph Neural Networks (GNNs) learn the correlation between local graph neighborhoods and node properties, with the requirement of adequate complete and clean neighborhoods. However, the intrinsic structural characteristics of the long-tail node degree distribution in most real-world graphs violate the assumption. Numerous low-degree nodes lack accurate representation due to limited connections, while bits of high-degree nodes include redundancy and errors in observed neighborhoods, harming the performance of GNNs. In this paper, we propose Laner-GNN, which performs latent neighborhood restoration adapting to aforesaid structural characteristics and improves representation capacity. Specifically, to reduce computational complexity, latent disentangled neighborhood factors are extracted and then manipulated for restoration instead of explicitly altering the entire adjacency matrix. A Degree-Adaptive Restorer captures the dependency of restoration on node degrees, while a Label-Informed Restorer and the Structured Field Augmented Priori enhance restoration with information from the prediction target and the graph structure. Extensive experiments on real-world datasets in different domains verify that our model excels existing SOTAs in different degree bins, thus uplifting the model performance in the whole dataset.

Placement is a critical and challenging step of modern chip design, with routability being an essential indicator of placement quality. Current routability-oriented placers typically apply an iterative two-stage approach, wherein the first stage generates a placement solution, and the second stage provides non-differentiable routing results to heuristically improve the solution quality. This method hinders jointly optimizing the routability aspect during placement. To address this problem, this work introduces RoutePlacer, an end-to-end routability-aware placement method. It trains RouteGNN, a customized graph neural network, to efficiently and accurately predict routability by capturing and fusing geometric and topological representations of placements. Well-trained RouteGNN then serves as a differentiable approximation of routability, enabling end-to-end gradient-based routability optimization. In addition, RouteGNN can improve two-stage placers as a plug-and-play alternative to external routers. Our experiments on DREAMPlace, an open-source AI4EDA platform, show that RoutePlacer can reduce Total Overflow by up to 16% while maintaining routed wirelength, compared to the state-of-the-art; integrating RouteGNN within two-stage placers leads to a 44% reduction in Total Overflow without compromising wirelength.

The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design. The long-standing endeavor of design automation has gained new momentum with the rise of large language models (LLMs). This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMs for heuristic generation, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM reflections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.

Deep learning full waveform inversion (DL-FWI) is an end-to-end and time-efficient high-resolution imaging technique for subsurface media. Popular methods are often plagued by location drift and significant velocity misfits at the stratigraphic boundaries. In this study, we propose an augmented boundary attention algorithm (ABA-FWI) to focus on the key boundary information. Regarding network composition, the wavelet convolution (WTconv) layer and the spatial attention module (SAM) are incorporated into the encoder and the decoder, respectively. The WTconv layer captures low frequencies by obtaining a large receptive field without suffering from overparameterization. SAM extracts distinctive information by utilizing the interspatial relationship of features for resolution enhancement. For loss function design, our reflection coefficient tuned boundary (RCTB) loss introduces the reflection coefficient to adjust the gradient map weight of low-contrast areas. It focuses on boundary regions characterized by speed transitions to minimize errors. Results on OpenFWI, the SEG simulation, and the Marmousi II slice datasets show that our method is superior to the state-of-the-art data-driven methods, especially on boundary details. The source code is available athttps://github.com/FanSmale/ABA-FWI.

Deep learning full waveform inversion (DL-FWI) is gaining much research interest due to its high prediction efficiency, effective exploitation of spatial correlation, and lack of the need for an initial estimate. As a data-driven approach, it has several key issues. For example, effective deep networks need to be designed, the training process needs to be controlled, and the generalization ability needs to be enhanced. In this paper, we propose a dual decoder network with curriculum learning (DD-Net) to handle these issues. First, we design a U-Net with two decoders to grasp the velocity value and stratigraphic boundary information of the velocity model. These decoders’ feedback will be combined at the encoder to enhance the encoding of edge spatial information. Second, we introduce curriculum learning to network training by organizing data in three difficulty levels. The easy-to-hard training process enhances the data fitting of the network. Third, we apply the network to low resolution seismic observations via a pre-network dimension reducer. This can serve as a general design idea without destroying the original network characteristics. Experiments are undertaken on SEG salt datasets and four synthetic datasets from OpenFWI. The results show that our network is superior to other state-of-the-art data-driven networks. The source code is available at github.com/fansmale/ddnet.

The recommender system is one of the most fundamental information services. A significant effort has been devoted to improving prediction accuracy, inevitably leading to the potential degradation of recommendation diversity. Moreover, individuals have different needs for diversity. To address these problems, diversity-enhanced approaches are proposed to modify the recommender models. However, these methods fail to break free from the relevance-oriented paradigm and are mostly haunted by sharply-declined accuracy and high computational costs. To tackle these challenges, we propose the Dual-Process Graph Neural Network (DPGNN), an efficient diversity-enhanced recommender system, resonating with the dual-process model of human cognition and the arousal theory of human interest. The first stage reduces the risk of suboptimal output during the training procedure, which helps to find a solution outside the relevance-oriented paradigm. Moreover, the second stage utilizes user-specific rating adjustments, boosting the recommendation diversity and accommodating users' distinctive needs with minimum computational costs. Extensive experiments on real-world datasets verify the effectiveness of our method in improving diversity, while maintaining accuracy with low computational costs.

In recent years, graph Transformers (GTs) have been demonstrated as a robust architecture for a wide range of graph learning tasks. However, the quadratic complexity of GTs limits their scalability on large-scale data, in comparison to Graph Neural Networks (GNNs). In this work, we propose the Kernel Decomposition Linear Graph Transformer (KDLGT), an accelerating framework for building scalable and powerful GTs. KDLGT employs the kernel decomposition approach to rearrange the order of matrix multiplication, thereby reducing complexity to linear. Additionally, it categorizes GTs into three distinct types and provides tailored accelerating methods for each category to encompass all types of GTs. Furthermore, we provide a theoretical analysis of the performance gap between KDLGT and self-attention to ensure its effectiveness. Under this framework, we select two representative GTs to design our models. Experiments on both real-world and synthetic datasets indicate that KDLGT not only achieves state-of-the-art performance on various datasets but also reaches an acceleration ratio of approximately 10 on graphs of certain sizes.

Graph Transformer is gaining increasing attention in the field of machine learning and has demonstrated state-of-the-art performance on benchmarks for graph representation learning. However, as current implementations of Graph Transformer primarily focus on learning representations of small-scale graphs, the quadratic complexity of the global self-attention mechanism presents a challenge for full-batch training when applied to larger graphs. Additionally, conventional sampling-based methods fail to capture necessary high-level contextual information, resulting in a significant loss of performance. In this paper, we introduce the Hierarchical Scalable Graph Transformer (HSGT) as a solution to these challenges. HSGT successfully scales the Transformer architecture to node representation learning tasks on large-scale graphs, while maintaining high performance. By utilizing graph hierarchies constructed through coarsening techniques, HSGT efficiently updates and stores multi-scale information in node embeddings at different levels. Together with sampling-based training methods, HSGT effectively captures and aggregates multi-level information on the hierarchical graph using only Transformer blocks. Empirical evaluations demonstrate that HSGT achieves state-of-the-art performance on large-scale benchmarks with graphs containing millions of nodes with high efficiency.

Graph Transformer has recently received wide attention in the research community with its outstanding performance, yet its structural expressive power has not been well analyzed. Inspired by the connections between Weisfeiler-Lehman (WL) graph isomorphism test and graph neural network (GNN), we introduce SEG-WL test (Structural Encoding enhanced G lobal Weisfeiler-Lehman test), a generalized graph isomorphism test algorithm as a powerful theoretical tool for exploring the structural discriminative power of graph Transformers. We theoretically prove that the SEG-WL test is an expressivity upper bound on a wide range of graph Transformers, and the representational power of SEG-WL test can be approximated by a simple Transformer network arbitrarily under certain conditions. With the SEG-WL test, we show how graph Transformers' expressive power is determined by the design of structural encodings, and present conditions that make the expressivity of graph Transformers beyond WL test and GNNs. Moreover, motivated by the popular shortest path distance encoding, we follow the theory-oriented principles and develop a provably stronger structural encoding method, Shortest Path Induced Subgraph (SPIS) encoding. Our theoretical findings provide a novel and practical paradigm for investigating the expressive power of graph Transformers, and extensive synthetic and real-world experiments empirically verify the strengths of our proposed methods.

Many real-world graph learning tasks require handling dynamic graphs where new nodes and edges emerge. Dynamic graph learning methods commonly suffer from the catastrophic forgetting problem, where knowledge learned for previous graphs is overwritten by updates for new graphs. To alleviate the problem, continual graph learning methods are proposed. However, existing continual graph learning methods aim to learn new patterns and maintain old ones with the same set of parameters of fixed size, and thus face a fundamental tradeoff between both goals. In this paper, we propose Parameter Isolation GNN (PI-GNN) for continual learning on dynamic graphs that circumvents the tradeoff via parameter isolation and expansion. Our motivation lies in that different parameters contribute to learning different graph patterns. Based on the idea, we expand model parameters to continually learn emerging graph patterns. Meanwhile, to effectively preserve knowledge for unaffected patterns, we find parameters that correspond to them via optimization and freeze them to prevent them from being rewritten. Experiments on eight real-world datasets corroborate the effectiveness of PI-GNN compared to state-of-the-art baselines.

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.

Graph Transformers have proved their advantages in graph data mining with elaborate Positional Encodings, especially in graph-level tasks. However, their application in the node classification task has not been fully exploited yet. In the node classification task, existing Graph Transformers with Positional Encodings are limited by the following issues: (i) PEs describing the node’s positional identities are insufficient for the node classification task on complex graphs, where a full portrayal of the local node property is needed. (ii) PEs for graphs are integrated with Transformers in a constant schema, resulting in the ignorance of local patterns that may vary among different nodes. In this paper, we propose Adaptive Graph Transformer (AGT) to tackle above issues. AGT consists of a Learnable Centrality Encoding and a Kernelized Local Structure Encoding. The two modules extract structural patterns from centrality and subgraph views in a learnable and scalable manner. Further, we design the Adaptive Transformer Block to adaptively integrate the attention scores and Structural Encodings in a node-specific manner. AGT achieves state-of-the-art performances on nine real-world web graphs (up to 1.6 million nodes). Furthermore, AGT shows outstanding results on two series of synthetic graphs with ranges of heterophily and noise ratios.

Seismic analysis and interpretation are sensitive to data resolution. High-density acquisition, deconvolution, and inverse Q filtering are traditional methods for resolution improvement. These methods have drawbacks such as strict assumptions and complex parameter solving processes. In this paper, we propose a channel attention U-Net and physical convolution combination (CAUC) algorithm to overcome these limitations. First, we design a channel attention U-Net (CAU) to establish a sophisticated nonlinear relationship between low-frequency data and coarse reflection coefficients. Specifically, we use a channel attention block after each downsampling convolution block to extract important local features of seismic data. Second, we convolve the coarse reflection coefficients with the wavelets to obtain high-resolution data. This physical convolution operation has a solid theoretical foundation. Therefore, our algorithm benefits not only from the learning ability of the neural network but also from the explainability of the physical operation. Both synthetic and field data are employed to verify the validity of the new algorithm. The traditional fast iterative shrinkage-thresholding algorithm (FISTA) and deep convolutional neural network (CNN) are used for comparison. The results show the superiority of the proposed method, especially in enhancing details such as thin layers and continuity.

Super-resolution reconstruction is an essential task of seismic inversion due to the low resolution and strong noise of field data. Popular deep networks derived from U-Net lack the ability to recover detailed edge features and weak signals. In this paper, we propose a dual decoder U-Net (D2UNet) to explore both detail and edge information of the data. The encoder inputs the low resolution image and the edge image obtained through the Canny algorithm. Edge image can provide rich shape and boundary information, which is helpful to generate more accurate and high-quality data. The dual decoder consists of a main decoder for high-resolution recovery and an edge decoder for edge contour detection. These two decoders interact with a texture warping module (TWM) with deformable convolution. TWM aims to distort realistic edge details to match the fidelity of low resolution inputs, especially the location of edges and weak signals. The loss function is a combination ofL1loss and multi-scale structural similarity loss (MS-SSIM) to ensure perception quality. Results on synthetic and field seismic images show that D2UNet not only improves the resolution of noisy seismic images, but also maintains the image fidelity.

Brittleness is an important parameter characterizing the fracturing properties of shale reservoir, which can be predicted by the pre-stack seismic inversion. In order to overcome the low efficiency and ill-posed problems of the traditional pre-stack brittleness inversion, we propose a new unsupervised deep learning (DL) inversion method for seismic brittleness parameters based on the physical equation. This method integrates DL framework and the physical equation, and provides a DL inversion strategy without actual labels. We first input the original seismic data into the Fastformer network, and use the low-frequency model as the physical constraint to predict the brittle parameters. Then, the prediction results of brittleness parameters are sent to the forward modeling module (a linear approximation equation) to calculate the synthetic seismic data. Next, the error between the calculated seismic data and original seismic data is used to update the network prediction results. The network parameters are iteratively optimized to minimize the error, and the brittle prediction parameters are finally output. In the whole training process, it is not necessary to use the real brittle parameters as the labels. Through this method, the effect of approximate unsupervised learning is obtained. Finally, we apply the proposed method to the synthetic data and field data, and compared with the results inverted by the traditional L1 method. The experimental results show that the proposed method has higher inversion accuracy and efficiency than the traditional L1 method, which has a great potential in the practical application.

Due to low cost and nondestructive characteristics, the passive surface-wave imaging has shown great potentials in urban near-surface exploration. However, the imaging methods are facing with many challenges in practical applications, such as uneven noise source distribution and complex site environment, which will seriously affect the dispersion imaging quality of surface waves, and result in the failure of retrieving accurate dispersion curve and inaccurate inversion. Therefore, data screening is required to improve the accuracy of passive surface-wave dispersion imaging. This process is usually completed manually, which is time-consuming for processing the large data sets. To solve this problem, we propose an automatic data screening method for the near-surface passive surface-wave imaging. Based on the distribution characteristics of the surface-wave energy of noise data in the F-K domain, this proposed method uses the least-squares technique to fit the quadratic distribution of energy, and sorts the noise time segments according to the defined correlation coefficients and bandwidth coefficients. Thus, we can automatically detect the noise time segments with high signal-to-noise ratio (SNR) without manual intervention. In order to verify the effectiveness of this proposed method, both synthetic data and field data are used in this study. The results show that this automatic data screening method significantly improves the accuracy of the passive surface-wave dispersion imaging, effectively expands the surface-wave energy band, and realizes rapid and automatic data screening.

Despite the recent success of Graph Neural Networks (GNNs), their learning pipeline is guided only by the input graph and the desired output of certain tasks, failing to capture useful patterns when not enough data are presented. Existing attempts incorporate auxiliary knowledge to mitigate this issue, most of which are not in a unified structure or hard to obtain. Noticing that nodes in graphs usually form implicit hierarchical structures, we proposed to integrate category taxonomies into the learning process of GNNs. A category taxonomy is a form of domain knowledge with a hierarchical tree structure, which is widely adopted in real-world scenarios. In this paper, we introduce Taxonomy-Enhanced Graph Neural Networks (Taxo-GNN). Specifically, we jointly optimize the taxonomy representation and node representation tasks, where categories in taxonomy are mapped to Gaussian distributions and nodes are embedded with the GNN framework. To characterize the bidirectional interaction between the taxonomy and the graph, the model is comprised of two modules, namely information distillation for taxonomy and knowledge fusion to graph. Information is first distilled from the graph and aligned with the hierarchical structure of the taxonomy in a bottom-to-top mechanism.After that, knowledge brought by the taxonomy is in turn fused to the graph convolution process, in the form of taxonomy-aware aggregation weights and taxonomy-augmented contexts. Extensive experiments on real-world datasets in multiple downstream tasks verify the effectiveness of our model.

Graph neural networks (GNNs) have achieved significant success in numerous fields under settings where training and testing graphs are identically distributed. However, this setting is rarely satisfied in real life. Due to the lack of out-of-distribution (OOD) generalization abilities, existing GNNs methods perform disappointingly when there exist distribution shifts between testing and training graphs. Though several attempts have been made to deal with the issue, they mainly focus on structural properties while overlooking rich graph feature information. To this end, we propose an Invariant Factor GNN (IFGNN), which utilizes causal factor graphs to achieve invariant performances across different environments. Specifically, we dissect the graph generalization problem in a causal view, and argue that the key of graph generalization lies in discovering causal factors. Thus we extract the latent factors in the graph through disentanglement, and the causal ones are discovered with the invariant learning mechanism. We conduct extensive experiments on both synthetic and real-world datasets with distribution shifts to validate the OOD generalization abilities. The results demonstrate that our proposed IFGNN significantly outperforms the state-of-the-art baselines.

Training Graph Neural Networks (GNNs) incrementally is a particularly urgent problem, because real-world graph data usually arrives in a streaming fashion, and inefficiently updating of the models results in out-of-date embeddings, thus degrade its performance in downstream tasks. Traditional incremental learning methods will gradually forget old knowledge when learning new patterns, which is the catastrophic forgetting problem. Although saving and revisiting historical graph data alleviates the problem, the storage limitation in real-world applications reduces the amount of saved data, causing GNN to forget other knowledge. In this paper, we propose a streaming GNN based on generative replay, which can incrementally learn new patterns while maintaining existing knowledge without accessing historical data. Specifically, our model consists of the main model (GNN) and an auxiliary generative model. The generative model based on random walks with restart can learn and generate fake historical samples (i.e., nodes and their neighborhoods), which can be trained with real data to avoid the forgetting problem. Besides, we also design an incremental update algorithm for the generative model to maintain the graph distribution and for GNN to capture the current patterns. Our model is evaluated on different streaming data sets. The node classification results prove that our model can update the model efficiently and achieve comparable performance to model retraining. Code is available at https://github.com/Junshan-Wang/SGNN-GR.

Due to the rapid growth in the scale of circuits and the desire for knowledge transfer from old designs to new ones, deep learning technologies have been widely exploited in Electronic Design Automation (EDA) to assist circuit design. In chip design cycles, we might encounter heterogeneous and diverse information sources, including the two most informative ones: the netlist and the design layout. However, handling each information source independently is sub-optimal. In this paper, we propose a novel way to integrate the multiple information sources under a unified heterogeneous graph named Circuit Graph, where topological and geometrical information is well integrated. Then, we propose Circuit GNN to fully utilize the features of vertices, edges as well as heterogeneous information during the message passing process. It is the first attempt to design a versatile circuit representation that is compatible across multiple EDA tasks and stages. Experiments on the two most representative prediction tasks in EDA show that our solution reaches state-of-the-art performance in both logic synthesis and global placement chip design stages. Besides, it achieves a 10x speed-up on congestion prediction compared to the state-of-the-art model.

Despite the recent success of Message-passing Graph Neural Networks (MP-GNNs), the strong inductive bias of homophily limits their ability to generalize to heterophilic graphs and leads to the over-smoothing problem. Most existing works attempt to mitigate this issue in the spirit of emphasizing the contribution from similar neighbors and reducing those from dissimilar ones when performing aggregation, where the dissimilarities are utilized passively and their positive effects are ignored, leading to suboptimal performances. Inspired by the idea of attitude polarization in social psychology, that people tend to be more extreme when exposed to an opposite opinion, we propose Polarized Graph Neural Network (Polar-GNN). Specifically, pairwise similarities and dissimilarities of nodes are firstly modeled with node features and topological structure information. And specially, we assign negative weights for those dissimilar ones. Then nodes aggregate the messages on a hyper-sphere through a polarization operation, which effectively exploits both similarities and dissimilarities. Furthermore, we theoretically demonstrate the validity of the proposed operation. Lastly, an elaborately designed loss function is introduced for the hyper-spherical embedding space. Extensive experiments on real-world datasets verify the effectiveness of our model.

Graph Neural Networks (GNNs) show strong expressive power on graph data mining, by aggregating information from neighbors and using the integrated representation in the downstream tasks. The same aggregation methods and parameters for each node in a graph are used to enable the GNNs to utilize the homophily relational data. However, not all graphs are homophilic, even in the same graph, the distributions may vary significantly. Using the same convolution over all nodes may lead to the ignorance of various graph patterns. Furthermore, many existing GNNs integrate node features and structure identically, which ignores the distributions of nodes and further limits the expressive power of GNNs. To solve these problems, we propose Meta Weight Graph Neural Network (MWGNN) to adaptively construct graph convolution layers for different nodes. First, we model the Node Local Distribution (NLD) from node feature, topological structure and positional identity aspects with the Meta-Weight. Then, based on the Meta-Weight, we generate the adaptive graph convolutions to perform a node-specific weighted aggregation and boost the node representations. Finally, we design extensive experiments on real-world and synthetic benchmarks to evaluate the effectiveness of MWGNN. These experiments show the excellent expressive power of MWGNN in dealing with graph data with various distributions.

Surface-wave analysis methods have been widely applied to construct near-surface shear-wave velocity structures. Whether it is an active source or passive source, the near-surface shear-wave velocity structure is obtained by inverting the surface-wave dispersion curve. In order to solve the problems of low inversion efficiency and poor inversion results in traditional surface-wave exploration, we have studied the surface-wave inversion methods based on deep learning technology. In this study, we propose a long short-term memory (LSTM) surface-wave inversion method based on the first height last velocity (FHLV) loss function. The core of our proposed method is the FHLV loss function consisting of two parts: a speed loss and a thickness loss, which improves the overall prediction accuracy through optimizing the learning process of the thickness parameter by the network. To verify the accuracy of the proposed LSTM surface-wave inversion method based on the FHLV loss function, experiments are conducted on both synthetic and real datasets. The results show that our proposed method can efficiently and accurately invert the near-surface shear-wave velocity structure.

The papers in this special section focus on the most recent advances in network structural modeling and learning with applications in the big data field. A variety of phenomena and systems are usually regraded as networks with a set of nodes and relations. Diversified methods and models have been developed for different tasks on networks, such as structural discovery, link prediction, and anomaly detection. With the growing data scale due to the information explosion and scientific development, network structural modeling has become an interesting and new field of research. Furthermore, building and utilizing new technologies for efficient learning, inference, and predication on different types of networks has become the trend to look forward to. In recent years, all kinds of machine learning technologies on networks have been developed rapidly, especially the network embedding and graph neural networks. They induce various methods and achieve satisfactory performance on network tasks, including node clustering or classification and link prediction. Furthermore, network structural modeling on real big data is also interesting.

Medical concept normalization is a critical problem in biomedical research and clinical applications. In this article, we focus on normalizing diagnostic and operation names in Chinese discharge summaries to standard concepts, which is formulated as a semantic matching problem. However, non-standard Chinese expressions, short-text normalization, heterogeneity of tasks and flexible input of disambiguation mentions pose critical challenges in our problem. We propose two models, the basic model and flexible model, to tackle these problems. The basic model solves the core problem (the first three challenges) in ambiguous mentions normalization, while the flexible model deals with flexible input of ambiguous mentions and further explores the correlation among them. Specifically, in the basic model, we present a general framework to disambiguate a diagnosis and its corresponding operation simultaneously, which introduces a tensor generator and a novel multi-view convolutional neural network (CNN) with a multi-task shared structure. We propose that the key to address non-standard expressions and the short-text problem is to incorporate a matching tensor with multiple granularities. Then a multi-view CNN is adopted to extract semantic matching patterns. Finally, the multi-task shared structure allows the model to exploit medical correlations between diagnosis and operation mentions to better perform disambiguation tasks. Subsequently, we design a flexible model based on the basic model. Specifically, we add a flexible attention layer to all procedure representation vectors, and then apply a flexible multi-task scheme to share the correlated information. Comprehensive experimental analysis indicates that our model outperforms existing baselines, demonstrating the effectiveness and robustness of our model.

The papers in this special section focus on social media computing. With massive amounts of social media data currently available, social media computing has attracted considerable attention in recent years, which aims to represent, analyze, and extract useful patterns from social media data. Social media computing is one typical cross-discipline of computer science, data mining, natural language process, and social sciences. As an emerging research field, there are various open, unexplored, and unidentified problems. There is a great need for computational models for tasks such as social media pattern analysis and prediction on social media data.

Recent works reveal that network embedding techniques enable many machine learning models to handle diverse downstream tasks on graph-structured data. However, as previous methods usually focus on learning embedding for a single network, they cannot learn representations transferable on multiple networks. Hence, it is important to design a network embedding algorithm that supports downstream model transferring on different networks, known as domain adaptation. In this article, we propose a Domain Adaptive Network Embedding framework, which applies Graph Convolutional Network to learn transferable embedding. In DANE, nodes from multiple networks are encoded to vectors via a shared and aligned embedding space. The distribution of embedding on different networks are further aligned by Adversarial Learning Regularization. To achieve better performance in scenarios where labels are provided, DANE adopts a cross-entropy error term of the GCN framework and class centroid aligning method. Moreover, DANE's advantages in learning transferable network embedding can be guaranteed theoretically. Extensive experiments reflect that the proposed framework outperforms other well-recognized network embedding baselines in cross-network domain adaptation tasks, and the semi-supervised components improve the performance significantly.

Many successful methods have been proposed for learning low-dimensional representations on large-scale networks, while almost all existing methods are designed in inseparable processes, learning embeddings for entire networks even when only a small proportion of nodes are of interest. This leads to great inconvenience, especially on large-scale or dynamic networks, where these methods become almost impossible to implement. In this paper, we formalize the problem of separated matrix factorization, based on which we elaborate a novel objective function that preserves both local and global information. We compare our SMF framework with approximate SVD algorithms and demonstrate SMF can capture more information when factorizing a given matrix. We further propose SepNE, a simple and flexible network embedding algorithm which independently learns representations for different subsets of nodes in separated processes. By implementing separability, our algorithm reduces the redundant efforts to embed irrelevant nodes, yielding scalability to large networks. To further incorporate complex information into SepNE, we discuss several methods that can be used to leverage high-order proximities in large networks. We demonstrate the effectiveness of SepNE on several real-world networks with different scales and subjects. With comparable accuracy, our approach significantly outperforms state-of-the-art baselines in running times on large networks.

Heterogeneous information networks (HINs) are ideal for describing real-world data with different types of entities and relationships. To carry out machine learning on HINs, meta-paths are widely utilized to extract semantics with pre-defined patterns, and models such as graph convolutional networks (GCNs) are thus enabled. However, previous works generally assume a fixed set of meta-paths, which is unrealistic as real-world data are overwhelmingly diverse. Therefore, it is appealing if meta-paths can be automatically selected given an HIN, yet existing works aiming at such problem possess drawbacks, such as poor efficiency and ignoring feature heterogeneity. To address these drawbacks, we propose GraphMSE, an efficient heterogeneous GCN combined with automatic meta-path selection. Specifically, we design highly efficient meta-path sampling techniques, and then injectively project sampled meta-path instances to vectors. We then design a novel semantic feature space alignment, aiming to align the meta-path instance vectors and hence facilitate meta-path selection. Extensive experiments on real-world datasets demonstrate that GraphMSE outperforms state-of-the-art counterparts, figures out important meta-paths, and is dramatically (e.g. 200 times) more efficient.

Heterogeneous Graph Neural Networks (HGNNs) have drawn increasing attention in recent years and achieved outstanding performance in many tasks. The success of the existing HGNNs relies on one fundamental assumption, i.e., the original heterogeneous graph structure is reliable. However, this assumption is usually unrealistic, since the heterogeneous graph in reality is inevitably noisy or incomplete. Therefore, it is vital to learn the heterogeneous graph structure for HGNNs rather than rely only on the raw graph structure. In light of this, we make the first attempt towards learning an optimal heterogeneous graph structure for HGNNs and propose a novel framework HGSL, which jointly performs Heterogeneous Graph Structure Learning and GNN parameters learning for classification task. Different from traditional GSL on homogeneous graph, considering the heterogeneity of different relations in heterogeneous graph, HGSL generates each relation subgraph independently. Specifically, in each generated relation subgraph, HGSL not only considers the feature similarity by generating feature similarity graph, but also considers the complex heterogeneous interactions in features and semantics by generating feature propagation graph and semantic graph. Then, these graphs are fused to a learned heterogeneous graph and optimized together with a GNN towards classification objective. Extensive experiments on real-world graphs demonstrate that the proposed framework significantly outperforms the state-of-the-art methods.

Researches on analyzing graphs with Graph Neural Networks (GNNs) have been receiving more and more attention because of the great expressive power of graphs. GNNs map the adjacency matrix and node features to node representations by message passing through edges on each convolution layer. However, the message passed through GNNs is not always beneficial for all parts in a graph. Specifically, as the data distribution is different over the graph, the receptive field (the farthest nodes that a node can obtain information from) needed to gather information is also different. Existing GNNs treat all parts of the graph uniformly, which makes it difficult to adaptively pass the most informative message for each unique part. To solve this problem, we propose two regularization terms that consider message passing locally: (1) Intra-Energy Reg and (2) Inter-Energy Reg. Through experiments and theoretical discussion, we first show that the speed of smoothing of different parts varies enormously and the topology of each part affects the way of smoothing. With Intra-Energy Reg, we strengthen the message passing within each part, which is beneficial for getting more useful information. With Inter-Energy Reg, we improve the ability of GNNs to distinguish different nodes. With the proposed two regularization terms, GNNs are able to filter the most useful information adaptively, learn more robustly and gain higher expressiveness. Moreover, the proposed LEReg can be easily applied to other GNN models with plug-and-play characteristics. Extensive experiments on several benchmarks verify that GNNs with LEReg outperform or match the state-of-the-art methods. The effectiveness and efficiency are also empirically visualized with elaborate experiments.

Spatial-temporal forecasting has attracted tremendous attention in a wide range of applications, and traffic flow prediction is a canonical and typical example. The complex and long-range spatial-temporal correlations of traffic flow bring it to a most intractable challenge. Existing works typically utilize shallow graph convolution networks (GNNs) and temporal extracting modules to model spatial and temporal dependencies respectively. However, the representation ability of such models is limited due to: (1) shallow GNNs are incapable to capture long-range spatial correlations, (2) only spatial connections are considered and a mass of semantic connections are ignored, which are of great importance for a comprehensive understanding of traffic networks. To this end, we propose Spatial-Temporal Graph Ordinary Differential Equation Networks (STGODE).1 Specifically, we capture spatial-temporal dynamics through a tensor-based ordinary differential equation (ODE), as a result, deeper networks can be constructed and spatial-temporal features are utilized synchronously. To understand the network more comprehensively, semantical adjacency matrix is considered in our model, and a well-design temporal dialated convolution structure is used to capture long term temporal dependencies. We evaluate our model on multiple real-world traffic datasets and superior performance is achieved over state-of-the-art baselines.

While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture heterogeneous structures and attributes of an underlying graph. Furthermore, though many Heterogeneous GNN (HGNN) variants have been proposed and have achieved state-of-the-art results, there are limited theoretical understandings of their properties. To this end, we introduce graph kernel to HGNNs and develop a Heterogeneous Graph Kernel-based Graph Neural Networks (HGK-GNN). Specifically, we incorporate the Mahalanobis distance (MD) to build a Heterogeneous Graph Kernel (HGK), and incorporating it into deep neural architectures, thus leveraging a heterogeneous GNN with a heterogeneous aggregation scheme. Also, we mathematically bridge HGK-GNN to metapath-based HGNNs, which are the most popular and effective variants of HGNNs. We theoretically analyze HGK-GNN with the indispensable Encoder and Aggregator component in metapath-based HGNNs, through which we provide a theoretical perspective to understand the most popular HGNNs. To the best of our knowledge, we are the first to introduce HGK into the field of HGNNs, and mark a first step in the direction of theoretically understanding and analyzing HGNNs. Correspondingly, both graph and node classification experiments are leveraged to evaluate HGK-GNN, where HGK-GNN outperforms a wide range of baselines on six real-world datasets, endorsing the analysis.

Molecular representation learning is the first yet vital step in combining deep learning and molecular science. To push the boundaries of molecular representation learning, we present PhysChem, a novel neural architecture that learns molecular representations via fusing physical and chemical information of molecules. PhysChem is composed of a physicist network (PhysNet) and a chemist network (ChemNet). PhysNet is a neural physical engine that learns molecular conformations through simulating molecular dynamics with parameterized forces; ChemNet implements geometry-aware deep message-passing to learn chemical / biomedical properties of molecules. Two networks specialize in their own tasks and cooperate by providing expertise to each other. By fusing physical and chemical information, PhysChem achieved state-of-the-art performances on MoleculeNet, a standard molecular machine learning benchmark. The effectiveness of PhysChem was further corroborated on cutting-edge datasets of SARS-CoV-2.

With the booming of the internet, a popular recommendation scenario has played a vital role in information acquisition for user where the latent heterogeneous collaborative signals and sequential patterns underlying a user's historical behaviors are important for better inferring which item she prefers to interact with next time. Traditional heterogeneous information network based methods or sequential recommendation methods either consider only heterogeneous collaborative signals in the interactions or model user embedding based on only their own item interaction sequence, which either can hardly capture a user's dynamic preferences or face a common data sparsity problem. In this paper, we propose a novel Sequence-aware Heterogeneous graph neural Collaborative Filtering model, called SHCF, which can address the above problems by considering both the high-order heterogeneous collaborative signals and sequential information. Specifically, we first construct a heterogeneous information network (HIN) by enriching the user-item bipartite graph with additional attribute information, and then design novel message passing layers for learning user and item embedding. For user embedding, we consider the sequential information to capture user's dynamic interests over time with a position-aware self-attention mechanism, and capture user's fine-grained static preferences on different aspects of an item with an element-wise attention mechanism. For item embedding, we carefully incorporate the heterogeneous attribute information with dual-level attention, which alleviates the data sparsity problem. Extensive experiments on three real-world datasets illustrate that our model can improve the recommendation performance compared with the state-of-the-art methods.

Graph neural networks (GNNs) have achieved tremendous success in graph mining. However, the inability of GNNs to model substructures in graphs remains a significant drawback. Specifically, message-passing GNNs (MPGNNs), as the prevailing type of GNNs, have been theoretically shown unable to distinguish, detect or count many graph substructures. While efforts have been paid to complement the inability, existing works either rely on pre-defined substructure sets, thus being less flexible, or are lacking in theoretical insights. In this paper, we propose GSKN1, a GNN model with a theoretically stronger ability to distinguish graph structures. Specifically, we design GSKN based on anonymous walks (AWs), flexible substructure units, and derive it upon feature mappings of graph kernels (GKs). We theoretically show that GSKN provably extends the 1-WL test, and hence the maximally powerful MPGNNs from both graph-level and node-level viewpoints. Correspondingly, various experiments are leveraged to evaluate GSKN, where GSKN outperforms a wide range of baselines, endorsing the analysis.

The abundant information in graphs helps us to learn more expressive node representations. Different nodes in the neighborhood have different importance to the central node. Thus, average weight aggregation in most Graph Neural Networks would fail to model such difference. GAT-based models introduce the attention mechanism to solve this problem, but they ignore the rich structural information and may suffer from the problem of over-smoothing. In this paper, we propose Graph Neural Networks with STructural Adaptive Receptive fields (STAR-GNN), which adaptively construct a receptive field for each node with structural information and further achieve better aggregation of information. Firstly, we model local structural distribution based on anonymous random walks, followed by using the structural information to construct receptive fields guided with mutual information. Then, as the generated receptive fields are irregular, we design a sub-graph aggregator to boost node representations and theoretically prove that it has the ability to capture the complex structures in receptive fields. Experimental results demonstrate the power of STAR-GNN in learning structural receptive fields adaptively and encoding more informative structural characteristics in real-world networks.

Graph convolutional networks (GCNs) have received considerable research attention recently. Most GCNs learn the node representations in Euclidean geometry, but that could have a high distortion in the case of embedding graphs with scale-free or hierarchical structure. Recently, some GCNs are proposed to deal with this problem in non-Euclidean geometry, e.g., hyperbolic geometry. Although hyperbolic GCNs achieve promising performance, existing hyperbolic graph operations actually cannot rigorously follow the hyperbolic geometry, which may limit the ability of hyperbolic geometry and thus hurt the performance of hyperbolic GCNs. In this paper, we propose a novel hyperbolic GCN named Lorentzian graph convolutional network (LGCN), which rigorously guarantees the learned node features follow the hyperbolic geometry. Specifically, we rebuild the graph operations of hyperbolic GCNs with Lorentzian version, e.g., the feature transformation and non-linear activation. Also, an elegant neighborhood aggregation method is designed based on the centroid of Lorentzian distance. Moreover, we prove some proposed graph operations are equivalent in different types of hyperbolic geometry, which fundamentally indicates their correctness. Experiments on six datasets show that LGCN performs better than the state-of-the-art methods. LGCN has lower distortion to learn the representation of tree-likeness graphs compared with existing hyperbolic GCNs. We also find that the performance of some hyperbolic GCNs can be improved by simply replacing the graph operations with those we defined in this paper.

Cloud-based workflow architecture has been widely used in e-science, e-business, smart city, and others, to automate business processes and improve their flexibility and maintainability. Online workflow executes in a collaborative and distributed environment and is prone to fraud and information leakage. Workflow authorization models are implemented to ensure that tasks are performed by authorized subjects with compliance of security/privacy polices. However, existing workflow authorization models have some limitations. First, most of the existing research focuses on static workflows, where an order arriving at a workflow traverses tasks in a fixed sequence. In many real applications, however, task routing is not deterministic, having a probability distribution or pattern that may be estimated from historical data. Second, existing research ignores practical resource constraints, like user utilization, order waiting time, etc. To address the limitations, this article studies the workflow authorization model under the more realistic dynamic settings. We formulate a workflow as a queueing system, so business constraints can be analytically represented, under reasonable assumptions. We model the studied problems as pseudo-Boolean satisfiaiblity problems and investigate their theoretical properties. We also develop algorithms and carry out computational studies. The experimental results show the effectiveness and efficiency of our developed solutions. Our research results are useful for production and process design in many real-life settings such as health care, online banking and electronic payment systems.

Network embedding is a method of learning a low-dimensional vector representation of network vertices under the condition of preserving different types of network properties. Previous studies mainly focus on preserving structural information of vertices at a particular scale, like neighbor information or community information, but cannot preserve the hierarchical community structure, which would enable the network to be easily analyzed at various scales. Inspired by the hierarchical structure of galaxies, we propose the Galaxy Network Embedding (GNE) model, which formulates an optimization problem with spherical constraints to describe the hierarchical community structure preserving network embedding. More specifically, we present an approach of embedding communities into a low-dimensional spherical surface, the center of which represents the parent community they belong to. Our experiments reveal that the representations from GNE preserve the hierarchical community structure and show advantages in several applications such as vertex multi-class classification, network visualization, and link prediction. The source code of GNE is available online.

Time series modeling has attracted extensive research efforts; however, achieving both reliable efficiency and interpretability from a unified model still remains a challenging problem. Among the literature, shapelets offer interpretable and explanatory insights in the classification tasks, while most existing works ignore the differing representative power at different time slices, as well as (more importantly) the evolution pattern of shapelets. In this paper, we propose to extract time-aware shapelets by designing a two-level timing factor. Moreover, we define and construct the shapelet evolution graph, which captures how shapelets evolve over time and can be incorporated into the time series embeddings by graph embedding algorithms. To validate whether the representations obtained in this way can be applied effectively in various scenarios, we conduct experiments based on three public time series datasets, and two real-world datasets from different domains. Experimental results clearly show the improvements achieved by our approach compared with 16 state-of-the-art baselines.

It is not until recently that graph neural networks (GNNs) are adopted to perform graph representation learning, among which, those based on the aggregation of features within the neighborhood of a node achieved great success. However, despite such achievements, GNNs illustrate defects in identifying some common structural patterns which, unfortunately, play significant roles in various network phenomena. In this paper, we propose GraLSP, a GNN framework which explicitly incorporates local structural patterns into the neighborhood aggregation through random anonymous walks. Specifically, we capture local graph structures via random anonymous walks, powerful and flexible tools that represent structural patterns. The walks are then fed into the feature aggregation, where we design various mechanisms to address the impact of structural features, including adaptive receptive radius, attention and amplification. In addition, we design objectives that capture similarities between structures and are optimized jointly with node proximity objectives. With the adequate leverage of structural patterns, our model is able to outperform competitive counterparts in various prediction tasks in multiple datasets.

The interactions of users and items in recommender system could be naturally modeled as a user-item bipartite graph. In recent years, we have witnessed an emerging research effort in exploring user-item graph for collaborative filtering methods. Nevertheless, the formation of user-item interactions typically arises from highly complex latent purchasing motivations, such as high cost performance or eye-catching appearance, which are indistinguishably represented by the edges. The existing approaches still remain the differences between various purchasing motivations unexplored, rendering the inability to capture fine-grained user preference. Therefore, in this paper we propose a novel Multi-Component graph convolutional Collaborative Filtering (MCCF) approach to distinguish the latent purchasing motivations underneath the observed explicit user-item interactions. Specifically, there are two elaborately designed modules, decomposer and combiner, inside MCCF. The former first decomposes the edges in user-item graph to identify the latent components that may cause the purchasing relationship; the latter then recombines these latent components automatically to obtain unified embeddings for prediction. Furthermore, the sparse regularizer and weighted random sample strategy are utilized to alleviate the overfitting problem and accelerate the optimization. Empirical results on three real datasets and a synthetic dataset not only show the significant performance gains of MCCF, but also well demonstrate the necessity of considering multiple components.

Graph neural networks (GNNs) have achieved strong performance in various applications. In the real world, network data is usually formed in a streaming fashion. The distributions of patterns that refer to neighborhood information of nodes may shift over time. The GNN model needs to learn the new patterns that cannot yet be captured. But learning incrementally leads to the catastrophic forgetting problem that historical knowledge is overwritten by newly learned knowledge. Therefore, it is important to train GNN model to learn new patterns and maintain existing patterns simultaneously, which few works focus on. In this paper, we propose a streaming GNN model based on continual learning so that the model is trained incrementally and up-to-date node representations can be obtained at each time step. Firstly, we design an approximation algorithm to detect new coming patterns efficiently based on information propagation. Secondly, we combine two perspectives of data replaying and model regularization for existing pattern consolidation. Specially, a hierarchy-importance sampling strategy for nodes is designed and a weighted regularization term for GNN parameters is derived, achieving greater stability and generalization of knowledge consolidation. Our model is evaluated on real and synthetic data sets and compared with multiple baselines. The results of node classification prove that our model can efficiently update model parameters and achieve comparable performance to model retraining. In addition, we also conduct a case study on the synthetic data, and carry out some specific analysis for each part of our model, illustrating its ability to learn new knowledge and maintain existing knowledge from different perspectives.

Information networks are ubiquitous and are ideal for modeling relational data. Networks being sparse and irregular, network embedding algorithms have caught the attention of many researchers, who came up with numerous embeddings algorithms in static networks. Yet in real life, networks constantly evolve over time. Hence, evolutionary patterns, namely how nodes develop itself over time, would serve as a powerful complement to static structures in embedding networks, on which relatively few works focus. In this paper, we propose EPNE, a temporal network embedding model preserving evolutionary patterns of the local structure of nodes. In particular, we analyze evolutionary patterns with and without periodicity and design strategies correspondingly to model such patterns in time-frequency domains based on causal convolutions. In addition, we propose a temporal objective function which is optimized simultaneously with proximity ones such that both temporal and structural information are preserved. With the adequate modeling of temporal information, our model is able to outperform other competitive methods in various prediction tasks. © 2020 The authors and IOS Press.

Learning low-dimensional representations on graphs has proved to be effective in various downstream tasks. However, noises prevail in real-world networks, which compromise networks to a large extent in that edges in networks propagate noises through the whole network instead of only the node itself. Whereas existing methods tend to focus on preserving structural properties, the robustness of the learned representations against noises is generally ignored. In this paper, we propose a novel framework to learn noise-free node representations and eliminate noises simultaneously. Since noises are often unknown on real graphs, we design two generators, namely a graph generator and a noise generator, to identify normal structures and noises in an unsupervised setting. On the one hand, the graph generator serves as a unified scheme to incorporate any useful graph prior knowledge to generate normal structures. We illustrate the generative process with community structures and power-law degree distributions as examples. On the other hand, the noise generator generates graph noises not only satisfying some fundamental properties but also in an adaptive way. Thus, real noises with arbitrary distributions can be handled successfully. Finally, in order to eliminate noises and obtain noise-free node representations, two generators need to be optimized jointly, and through maximum likelihood estimation, we equivalently convert the model into imposing different regularization constraints on the true graph and noises respectively. Our model is evaluated on both real-world and synthetic data. It outperforms other strong baselines for node classification and graph reconstruction tasks, demonstrating its ability to eliminate graph noises.

Heterogeneous Information Networks (HINs) are ubiquitous structures in that they can depict complex relational data. Due to their complexity, it is hard to obtain sufficient labeled data on HINs, hampering classification on HINs. While domain adaptation (DA) techniques have been widely utilized in images and texts, the heterogeneity and complex semantics pose specific challenges towards domain adaptive classification on HINs. On one hand, HINs involve multiple levels of semantics, making it demanding to do domain alignment among them. On the other hand, the trade-off between domain similarity and distinguishability must be elaborately chosen, in that domain invariant features have been shown to be homogeneous and uninformative for classification. In this paper, we propose Multi-space Domain Adaptive Classification (MuSDAC) to handle the problem of DA on HINs. Specifically, we utilize multi-channel shared weight GCNs, projecting nodes in HINs to multiple spaces where pairwise alignment is carried out. In addition, we propose a heuristic sampling algorithm that efficiently chooses the combination of channels featuring distinguishability, and moving-averaged weighted voting scheme to fuse the selected channels, minimizing both transfer and classification loss. Extensive experiments on pairwise datasets endorse not only our model's performance on domain adaptive classification on HINs and contributions by individual components.

Graph Convolutional Networks (GCNs) achieved tremendous success by effectively gathering local features for nodes. However, commonly do GCNs focus more on node features but less on graph structures within the neighborhood, especially higher-order structural patterns. However, such local structural patterns are shown to be indicative of node properties in numerous fields. In addition, it is not just single patterns, but the distribution over all these patterns matter, because networks are complex and the neighborhood of each node consists of a mixture of various nodes and structural patterns. Correspondingly, in this paper, we propose Graph Structural topic Neural Network, abbreviated GraphSTONE 1, a GCN model that utilizes topic models of graphs, such that the structural topics capture indicative graph structures broadly from a probabilistic aspect rather than merely a few structures. Specifically, we build topic models upon graphs using anonymous walks and Graph Anchor LDA, an LDA variant that selects significant structural patterns first, so as to alleviate the complexity and generate structural topics efficiently. In addition, we design multi-view GCNs to unify node features and structural topic features and utilize structural topics to guide the aggregation. We evaluate our model through both quantitative and qualitative experiments, where our model exhibits promising performance, high efficiency, and clear interpretability.

Recent works show that end-to-end, (semi-) supervised network embedding models can generate satisfactory vectors to represent network topology, and are even applicable to unseen graphs by inductive learning. However, domain mismatch between training and testing network for inductive learning, as well as lack of labeled data often compromises the outcome of such methods. To make matters worse, while transfer learning and active learning techniques, being able to solve such problems correspondingly, have been well studied on regular i.i.d data, relatively few attention has been paid on networks. Consequently, we propose in this paper a method for active transfer learning on networks named active-transfer network embedding, abbreviated ATNE. In ATNE we jointly consider the influence of each node on the network from the perspectives of transfer and active learning, and hence design novel and effective influence scores combining both aspects in the training process to facilitate node selection. We demonstrate that ATNE is efficient and decoupled from the actual model used. Further extensive experiments show that ATNE outperforms state-of-the-art active node selection methods and shows versatility in different situations.

In online complex systems such as transportation system, an important work is real-time traffic prediction. Due to the data shift, data model inconsistency, and sudden change of traffic patterns (like transportation accident), the prediction result derived from an offline-built model would be unreliable. Retraining the model is usually not time affordable for online prediction, especially when the prediction model is very complex and costs a lot of training time (for example, deep neural networks). A real-time prediction correction strategy would be of great value under this situation. Traditionally, the prediction correction usually relies on the prediction error in several previous time intervals. They assume that the error pattern is similar in the current time interval, so that it is time-delayed to some extent. In this article, we propose the prediction correction strategy using the reconstruction error in the deep neural network. The reconstruction error can reflect the model’s ability on feature representation and then determine the fitness of an input data to the model. We first build the relationship between reconstruction error and prediction error. From the perspective of the prediction interval, we demonstrate that the reconstruction error is in positive relation with the prediction interval. Thus the prediction result is more reliable when the reconstruction error is smaller. Then we propose two mechanisms of real-time prediction correction using the reconstruction error. The data driven prediction correction approach selects several training instances with similar reconstruction errors to the current instance and using their average prediction error in correcting the prediction result. The model-driven approach builds several component deep neural networks in training. The component training set for each network is selected according to the reconstruction error of training instances. For a predicting instance, it first computes the reconstruction error of the sample in each component network and then averages the results by the reconstruction error and prediction interval. The model-driven approach is actually a reconstruction error-based deep neural network ensemble approach. Finally, a series of experiments demonstrated that reconstruction error based prediction correction approaches are effective in several prediction problems in transportation including traffic flow prediction on road, traffic flow prediction in entrance and exit station and travel time prediction. Besides the high overall accuracy, our approach can also provide many observations of using the reconstruction error in transportation prediction.

Many successful methods have been proposed for learning low dimensional representations on large-scale networks, while almost all existing methods are designed in inseparable processes, learning embeddings for entire networks even when only a small proportion of nodes are of interest. This leads to great inconvenience, especially on super-large or dynamic networks, where these methods become almost impossible to implement. In this paper, we formalize the problem of separated matrix factorization, based on which we elaborate a novel objective function that preserves both local and global information. We further propose SepNE, a simple and flexible network embedding algorithm which independently learns representations for different subsets of nodes in separated processes. By implementing separability, our algorithm reduces the redundant efforts to embed irrelevant nodes, yielding scalability to super-large networks, automatic implementation in distributed learning and further adaptations. We demonstrate the effectiveness of this approach on several real-world networks with different scales and subjects. With comparable accuracy, our approach significantly outperforms state-of-the-art baselines in running times on large networks.

To depict ubiquitous relational data in real world, network data have been widely applied in modeling complex relationships. Projecting vertices to low dimensional spaces, quoted as Network Embedding, would thus be applicable to diverse real-world predicative tasks. Numerous works exploiting pairwise proximities, one characteristic owned by real networks, the clustering property, namely vertices are inclined to form communities of various ranges and hence form a hierarchy consisting of communities, has barely received attention from researchers. In this paper, we propose our network embedding framework, abbreviated SpaceNE, preserving hierarchies formed by communities through subspaces, manifolds with flexible dimensionalities and are inherently hierarchical. Moreover, we propose that subspaces are able to address further problems in representing hierarchical communities, including sparsity and space warps. Last but not least, we proposed constraints on dimensions of subspaces to denoise, which are further approximated by differentiable functions such that joint optimization is enabled, along with a layer-wise scheme to alleviate the overhead cause by the vast number of parameters. We conduct various experiments with results demonstrating our model's effectiveness in addressing community hierarchies.

Graph Convolutional Networks (GCNs) have proved to be a most powerful architecture in aggregating local neighborhood information for individual graph nodes. Low-rank proximities and node features are successfully leveraged in existing GCNs, however, attributes that graph links may carry are commonly ignored, as almost all of these models simplify graph links into binary or scalar values describing node connectedness. In our paper instead, links are reverted to hypostatic relationships between entities with descriptional attributes. We propose GCN-LASE (GCN with Link Attributes and Sampling Estimation), a novel GCN model taking both node and link attributes as inputs. To adequately captures the interactions between link and node attributes, their tensor product is used as neighbor features, based on which we define several graph kernels and further develop according architectures for LASE. Besides, to accelerate the training process, the sum of features in entire neighborhoods are estimated through Monte Carlo method, with novel sampling strategies designed for LASE to minimize the estimation variance. Our experiments show that LASE outperforms strong baselines over various graph datasets, and further experiments corroborate the informativeness of link attributes and our model's ability of adequately leveraging them.

Keyword-based tags (referred to as tags) are used to represent additional attributes of nodes in addition to what is explicitly stated in their contents, like the hashtags in YouTube. Aside of being auxiliary information for node representation, tags can also be used for retrieval, recommendation, content organization, and event analysis. Therefore, tag representation learning is of great importance. However, to learn satisfactory tag representations is challenging because 1) traditional representation methods generally fail when it comes to representing tags, 2) bidirectional interactions between nodes and tags should be modeled, which are generally not dealt within existing research works. In this paper, we propose a tag representation learning model which takes tag-related node interaction into consideration, named Tag2Gauss. Specifically, since tags represent node communities with intricate overlapping relationships, we propose that Gaussian distributions would be appropriate in modeling tags. Considering the bidirectional interactions between nodes and tags, we propose a tag representation learning model mapping tags to distributions consisting of two embedding tasks, namely Tag-view embedding and Node-view embedding. Extensive evidence demonstrates the effectiveness of representing tag as a distribution, and the advantages of the proposed architecture in many applications, such as the node classification and the network visualization.

Recent works reveal that network embedding techniques enable many machine learning models to handle diverse downstream tasks on graph structured data. However, as previous methods usually focus on learning embeddings for a single network, they can not learn representations transferable on multiple networks. Hence, it is important to design a network embedding algorithm that supports downstream model transferring on different networks, known as domain adaptation. In this paper, we propose a novel Domain Adaptive Network Embedding framework, which applies graph convolutional network to learn transferable embeddings. In DANE, nodes from multiple networks are encoded to vectors via a shared set of learnable parameters so that the vectors share an aligned embedding space. The distribution of embeddings on different networks are further aligned by adversarial learning regularization. In addition, DANE's advantage in learning transferable network embedding can be guaranteed theoretically. Extensive experiments reflect that the proposed framework outperforms other state-of-the-art network embedding baselines in cross-network domain adaptation tasks.

Network embedding is a method to learn low-dimensional representation vectors for nodes in complex networks. In real networks, nodes may have multiple tags but existing methods ignore the abundant semantic and hierarchical information of tags. This information is useful to many network applications and usually very stable. In this paper, we propose a tag representation learning model, Tag2Vec, which mixes nodes and tags into a hybrid network. Firstly, for tag networks, we define semantic distance as the proximity between tags and design a novel strategy, parameterized random walk, to generate context with semantic and hierarchical information of tags adaptively. Then, we propose hyperbolic Skip-gram model to express the complex hierarchical structure better with lower output dimensions. We evaluate our model on the NBER U.S. patent dataset and WordNet dataset. The results show that our model can learn tag representations with rich semantic information and it outperforms other baselines.

Recently, real-time air quality estimation has attracted more and more attention from all over the world, which is close to our daily life. With the prevalence of mobile sensors, there is an emerging way to monitor the air quality with mobile sensors on vehicles. Compared with traditional expensive monitor stations, mobile sensors are cheaper and more abundant, but observations from these sensors have unstable spatial and temporal distributions, which results in the existing model could not work very well on this type of data. In this article, taking advantage of air quality data from mobile sensors, we propose an real-time urban air quality estimation method based on the Gaussian Process Regression for air pollution of the unmonitored areas, pivoting on the diffusion effect and the accumulation effect of air pollution. In order to meet the real-time demands, we propose a two-layer ensemble learning framework and a self-adaptivity mechanism to improve computational efficiency and adaptivity. We evaluate our model with real data from mobile sensor system located in Beijing, China. And the experiments show that our proposed model is superior to the state-of-the-art spatial regression methods in both precision and time performances.

Medical concept normalization is a critical problem in biomedical research and clinical applications. In this paper, we focus on normalizing diagnostic and procedure names in Chinese discharge summaries to standard entities, which is formulated as a semantic matching problem. However, non-standard Chinese expressions, short-text normalization and heterogeneity of tasks pose critical challenges in our problem. This paper presents a general framework which introduces a tensor generator and a novel multi-view convolutional neural network (CNN) with multi-task shared structure to tackle the two tasks simultaneously. We propose that the key to address non-standard expressions and short-text problem is to incorporate a matching tensor with multiple granularities. Then multi-view CNN is adopted to extract semantic matching patterns and learn to synthesize them from different views. Finally, multi-task shared structure allows the model to exploit medical correlations between disease and procedure names to better perform disambiguation tasks. Comprehensive experimental analysis indicates our model outperforms existing baselines which demonstrates the effectiveness of our model.

Aligning users across multiple heterogeneous social networks is a fundamental issue in many data mining applications. Methods that incorporate user attributes and network structure have received much attention. However, most of them suffer from error propagation or the noise from diverse neighbors in the network. To effectively model the influence from neighbors, we propose a graph neural network to directly represent the ego networks of two users to be aligned into an embedding, based on which we predict the alignment label. Three major mechanisms in the model are designed to unitedly represent different attributes, distinguish different neighbors and capture the structure information of the ego networks respectively.

Chinese medical concept normalization, which maps non-standard medical concepts to standard expressions, is a NLP task with wide-ranging applications in medical big data research and clinical statistic. Many previous works apply supervised methods which require a lot of annotated data. However, they can not address the challenge brought by the high cost of medical data annotation, which requires sufficient professional knowledge and experience. Meanwhile, existing unsupervised methods perform poorly facing the various non-standard expression from different data sources. In this paper, we propose DUNE, Disease Unsupervised Normalization by Embedding, an unsupervised Chinese medical concept normalization framework by applying denoising auto-encoder (DAE) and network embedding. We formulate this task as finding mention-entity pairs with great text and comorbidity similarity. To handle the noise in text, we design a multi-view attention based denoising auto-encoder (MADAE) to capture text information from multiple views, reduce the influence of noise, and transform text to denoised vectors. To introduce comorbidity information, we construct a comorbidity network with both standard and non-standard disease names as nodes from medical records. Because of the diversity of nonstandard expressions, one disease perhaps corresponds to several different nodes, which causes noise in comorbidity network. To handle such network structure noise, we propose a denoising network embedding framework, which reduce the structure noise with the help of text information, to embed the nodes to vectors for comorbidity similarity measurement. Convincing experiment results show that our method performs better than existing unsupervised baselines and approaches the performance of classical supervised machine learning model on this task.

Network embedding is a method of learning a low-dimensional vector representation of network vertices under the condition of preserving different types of network properties. Previous studies mainly focus on preserving structural information of vertices at a particular scale, like neighbor information or community information, but cannot preserve the hierarchical community structure, which would enable the network to be easily analyzed at various scales. Inspired by the hierarchical structure of galaxies, we propose the Galaxy Network Embedding (GNE) model, which formulates an optimization problem with spherical constraints to describe the hierarchical community structure preserving network embedding. More specifically, we present an approach of embedding communities into a low dimensional spherical surface, the center of which represents the parent community they belong to. Our experiments reveal that the representations from GNE preserve the hierarchical community structure and show advantages in several applications such as vertex multi-class classification and network visualization. The source code of GNE is available online.

Network embedding, as an approach to learn low-dimensional representations of vertices, has been proved extremely useful in many applications. Lots of state-of-the-art network embedding methods based on Skip-gram framework are efficient and effective. However, these methods mainly focus on the static network embedding and cannot naturally generalize to the dynamic environment. In this paper, we propose a stable dynamic embedding framework with high efficiency. It is an extension for the Skip-gram based network embedding methods, which can keep the optimality of the objective in the Skip-gram based methods in theory. Our model can not only generalize to the new vertex representation, but also update the most affected original vertex representations during the evolvement of the network. Multi-class classification on three real-world networks demonstrates that, our model can update the vertex representations efficiently and achieve the performance of retraining simultaneously. Besides, the visualization experimental result illustrates that, our model is capable of avoiding the embedding space drifting.

Accurate causal inference among time series helps to better understand the interactive scheme behind the temporal variables. For time series analysis, an unavoidable issue is the existence of time lag among different temporal variables. That is, past evidence would take some time to cause a future effect instead of an immediate response. To model this process, existing approaches commonly adopt a prefixed time window to define the lag. However, in many real-world applications, this parameter may vary among different time series, and it is hard to be predefined with a fixed value. In this letter, we propose to learn the causal relations as well as the lag among different time series simultaneously from data. Specifically, we develop a probabilistic decomposed slab-and-spike (DSS) model to perform the inference by applying a pair of decomposed spike-and-slab variables for the model coefficients, where the first variable is used to estimate the causal relationship and the second one captures the lag information among different temporal variables. For parameter inference, we propose an efficient expectation propagation (EP) algorithm to solve the DSS model. Experimental results conducted on both synthetic and real-world problems demonstrate the effectiveness of the proposed method. The revealed time lag can be well validated by the domain knowledge within the real-world applications.

Mining human behaviors has always been an important subarea of Data Mining. While it provides empirical evidences to psychological/behavioral studies, it also builds the foundation of various big-data systems, which rely heavily on the prediction of human behaviors. In recent years, the ubiquitous spreading of mobile phones and the massive amount of spatio-temporal data collected from them make it possible to keep track of the daily commute behaviors of mobile subscribers and further conduct routine mining on them. In this article, we propose to model mobile subscribers’ daily commute behaviors by three levels: location trajectory, one-day pattern, and routine pattern. We develop the model Spatio-Temporal Routine Mining Model (STRMM) to characterize the generative process between these three levels. From daily trajectories, the STRMM model unsupervisedly extracts spatio-temporal routine patterns that contain two aspects of information: (1) How people’s typical commute patterns are. (2) How much their commute behaviors vary from day to day. Compared to traditional methods, STRMM takes into account the different degrees of behavioral uncertainty in different timespans of a day, yielding more realistic and intuitive results. To learn model parameters, we adopt Stochastic Expectation Maximization algorithm. Experiments are conducted on two real world datasets, and the empirical results show that the STRMM model can effectively discover hidden routine patterns of human commute behaviors and yields higher accuracy results in trajectory prediction task.

The interpolation, prediction, and feature analysis of fine-gained air quality are three important topics in the area of urban air computing. The solutions to these topics can provide extremely useful information to support air pollution control, and consequently generate great societal and technical impacts. Most of the existing work solves the three problems separately by different models. In this paper, we propose a general and effective approach to solve the three problems in one model called the Deep Air Learning (DAL). The main idea of DAL lies in embedding feature selection and semi-supervised learning in different layers of the deep learning network. The proposed approach utilizes the information pertaining to the unlabeled spatio-temporal data to improve the performance of the interpolation and the prediction, and performs feature selection and association analysis to reveal the main relevant features to the variation of the air quality. We evaluate our approach with extensive experiments based on real data sources obtained in Beijing, China. Experiments show that DAL is superior to the peer models from the recent literature when solving the topics of interpolation, prediction, and feature analysis of fine-gained air quality.

Social influence is a fundamental issue in social network analysis and has attracted tremendous attention with the rapid growth of online social networks. However, existing research mainly focuses on studying peer influence. This paper introduces a novel notion of structural influence and studies how to efficiently discover structural influence patterns from social streams. We present three sampling algorithms with theoretical unbiased guarantee to speed up the discovery process. Experiments on a big microblogging dataset show that the proposed sampling algorithms can achieve a 10 times speedup compared to the exact influence pattern mining algorithm, with an average error rate of only 1.0%. The extracted structural influence patterns have many applications. We apply them to predict retweet behavior, with performance being significantly improved.

As both social network structure and strength of influence between individuals evolve constantly, it requires tracking the influential nodes under a dynamic setting. To address this problem, we explore the Influential Node Tracking (INT) problem as an extension to the traditional Influence Maximization problem (IM) under dynamic social networks. While the Influence Maximization problem aims at identifying a set of k nodes to maximize the joint influence under one static network, the INT problem focuses on tracking a set of influential nodes that keeps maximizing the influence as the network evolves. Utilizing the smoothness of the evolution of the network structure, we propose an efficient algorithm, Upper Bound Interchange Greedy (UBI) and a variant, UBI+. Instead of constructing the seed set from the ground, we start from the influential seed set we found previously and implement node replacement to improve the influence coverage. Furthermore, by using a fast update method by calculating the marginal gain of nodes, our algorithm can scale to dynamic social networks with millions of nodes. Empirical experiments on three real large-scale dynamic social networks show that our UBI and its variants, UBI+ achieves better performance in terms of both influence coverage and running time.

Previous works related to anomaly detection in mobile phone data rely heavily on manually selected features or statistics, which weakens the generalization of the model. In addition, traditional methods only allow anomaly to appear in certain fixed time interval with predefined duration. In this work, based on an unsupervised probabilistic topic model, we propose a Routine Mining Based Anomaly Detection (RMBAD) approach that learns the pattern of normal from naturally existing human routines, free of any manually extracted features. Taking a generative approach, the RMBAD model combines group anomaly detection and topic segmentation method, segmenting mobile subscriber's sequence of behaviors into explainable routines and report those unexplainable segments as anomalies simultaneously. Furthermore, The RMBAD model allows routines of different durations to coexist, thus achieving a more realistic modeling of human activity pattern, which ultimately leads to higher anomaly detection accuracy. Extensive experiments are conducted on both synthetic and real world mobile datasets, and the empirical results show that the RMBAD model can effectively discover hidden routines of human activity and identify those groups of behaviors that collectively appear anomalous.

Ensemble learning of neural network is a learning paradigm where ensembles of several neural networks show improved generalization capabilities that outperform those of single networks. For deep learning of multi-layer neural networks, ensemble learning is still applicable. In addition, characteristics of deep neural networks can provide potential opportunities to improve the performance of traditional neural network ensembles. In this paper, we propose an ensemble criterion of deep neural networks that is based on the reconstruction error and present two strategies to solve the most important issues in ensemble learning of neural networks: component dataset sampling and output averaging. Component training datasets are selected according to the reconstruction error instead of random bootstrap sampling or re-weighting. Moreover, for each testing instance, we can compute the reconstruction error yielded by the sub-model simultaneously with the output. The reconstruction error is used as the weights in output averaging. From the perspectives of prediction interval and confidence interval, we demonstrated that smaller reconstruction error could ensure smaller prediction interval. We also incorporate the famous structure ensemble approach “Dropout” into the proposed approach to achieve the best performance. We conduct experiments on classification and regression datasets to validate the effectiveness of our approach.

Learning temporal causal structures between time series is one of key tools for analyzing time series data. Most previous works focuse on learning with static temporal causal relationships. However, in many real world applications, such as climate environment and transportation system, the causal structures vary dramatically over time. In this paper, we propose a probabilistic dynamic causal (PDC) model based on Lasso-Granger to uncover the dynamic temporal dependencies. Specifically, the PDC model infers different state varying of temporal data and causal structures of each state in one unified model. We devise the expectation-maximization (EM) algorithm to infer the model parameters. Furthermore, to address the smoothness of state varying in adjacent time, we extend the PDC model with a regularization term encouraging states to be similar in adjacent time. Though it may slightly decrease the precision on training data, it improves the generalization capability of the model. We conduct experiments on synthetic dataset as well as two real-world datasets of climate and traffic to evaluate the effectiveness of the PDC model. Experimental results show that the proposed model is effective in discovering the dynamic causal factors of Particulate Matter 2.5 (PM2.5) and traffic spatial causalities.

Real world marketing campaign utilizing the word-of-mouth effect usually lasts a long time, where multiple sets of influential users need to be mined and targeted at different times to fully utilize the power of viral marketing. As both social network structure and strength of influence between individuals evolve constantly, it requires to track the influential nodes under a dynamic setting. To address the above problem, we explore the Influential Node Tracking (INT) problem as an extension to the traditional Influence Maximization problem under dynamic social networks. While Influence Maximization problem aims at identifying a set of k nodes to maximize the joint influence under one static network, INT problem focuses on tracking a set of influential nodes that keeps maximizing the influence as the network evolves. Utilizing the smoothness of the evolution of the network structure, we propose an efficient algorithm, Upper Bound Interchange Greedy (UBI) to solve the INT problem. Instead of constructing the seed set from the ground, we start from the influential seed set we find previously and implement node replacement to improve the influence coverage. Furthermore, by using a fast update method to maintain an upper bound on the node replacing gain, our algorithm can scale to dynamic social networks with millions of nodes. Empirical experiments on three real large-scale dynamic social networks show that our UBI algorithm achieves better performance in terms of both influence coverage and running time.

Correlation based graphical models are developed to detect the dependence relationships among random variables and provide intuitive explanations for these relationships in complex systems. Most of the existing works focus on learning a single correlation based graphical model for all the random variables. However, it is difficult to understand and interpret the massive dependencies of the variables learned from a single graphical model at a global level especially when the graph is large. In order to provide a clearer understanding for the dependence relationships among a large number of random variables, in this paper, we propose the problem of estimating an overlapping decomposition for the Gaussian graphical model of a large scale to generate overlapping sub-graphical models, where strong and meaningful correlations remain in each subgraph with a small scale. Specifically, we propose a greedy algorithm to achieve the overlapping decomposition for the Gaussian graphical model. A key technique of the algorithm is that the problem of solving a (k + 1)-node Gaussian graphical model can be approximately reduced to the problem of solving a one-step vector regularization problem based on a solved k-node Gaussian graphical model with theoretical guarantee. Based on this technique, a greedy expansion algorithm is proposed to generate the overlapping subgraphs. Moreover, we extend the proposed method to deal with dynamic graphs where the dependence relationships among random variables vary with the time. We evaluate the proposed methods on synthetic dataset and a real-life traffic dataset, and the experimental results show the superiority of the proposed methods.

With the proliferation of mobile devices and wireless technologies, mobile social network systems are increasingly available. A mobile social network plays an essential role as the spread of information and influence in the form of “word-of-mouth”. It is a fundamental issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g., to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). The problem of finding the most influential nodes is unfortunately NP-hard. It has been shown that a Greedy algorithm with provable approximation guarantees can give good approximation; However, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large mobile social network. In this paper, a divide-and-conquer strategy with parallel computing mechanism has been adopted. We first propose an algorithm called Community-based Greedy algorithm for mining top-K influential nodes. It encompasses two components: dividing the large-scale mobile social network into several communities by taking into account information diffusion and selecting communities to find influential nodes by a dynamic programming. Then, to further improve the performance, we parallelize the influence propagation based on communities and consider the influence propagation crossing communities. Also, we give precision analysis to show approximation guarantees of our models. Experiments on real large-scale mobile social networks show that the proposed methods are much faster than previous algorithms, meanwhile, with high accuracy.

Multi-task learning seeks to improve the generalization performance by sharing common information among multiple related tasks. A key assumption in most MTL algorithms is that all tasks are related, which, however, may not hold in many real-world applications. Existing techniques, which attempt to address this issue, aim to identify groups of related tasks using group sparsity. In this paper, we propose a probabilistic tree sparsity (PTS) model to utilize the tree structure to obtain the sparse solution instead of the group structure. Specifically, each model coefficient in the learning model is decomposed into a product of multiple component coefficients each of which corresponds to a node in the tree. Based on the decomposition, Gaussian and Cauchy distributions are placed on the component coefficients as priors to restrict the model complexity. We devise an efficient expectation maximization algorithm to learn the model parameters. Experiments conducted on both synthetic and real-world problems show the effectiveness of our model compared with state-of-the-art baselines.

People play different roles in various social networks. Even in a single network, people may interact with others based on different roles, and there are various relationships among them. However, current research usually treats all relationships homogeneously (i.e. friendship). In this paper, we try to identify different types of relationship (family, colleague, and social) within social networks. By analyzing a large-scale cellphone network, we gain insights about human mobility patterns. We design three metrics to capture colocation behaviors for cellphone users, taking spatial-temporal factors into consideration. These metrics show that users with different relationships demonstrate significantly different co-locating patterns. With these metrics as features, we adopt supervised approach to classify cellphone user pairs into different relationship categories. Comparing to using network and communication features, co-location metrics demonstrate better performance to fulfill the task of relationship identification.

Process neural network is widely used in modeling temporal process inputs in neural networks. Traditional process neural network is usually limited in structure of single hidden layer due to the unfavorable training strategies of neural network with multiple hidden layers and complex temporal weights in process neural network. Deep learning has emerged as an effective pre-training method for neural network with multiple hidden layers. Though deep learning is usually limited in static inputs, it provided us a good solution for training neural network with multiple hidden layers. In this paper, we extended process neural network to deep process neural network. Two basic structures of deep process neural network are discussed. One is the accumulation first deep process neural network and the other is accumulation last deep process neural network. We could build any architecture of deep process neural network based on those two structures. Temporal process inputs are represented as sequences in this work for the purpose of unsupervised feature learning with less prior knowledge. Based on this, we proposed learning algorithms for two basic structures inspired by the numerical learning approach for process neural network and the auto-encoder in deep learning. Finally, extensive experiments demonstrated that deep process neural network is effective in tasks with temporal process inputs. Accuracy of deep process neural network is higher than traditional process neural network while time complexity is near in the task of traffic flow prediction in highway system.

Deep learning has attracted a lot of attention in research and industry in recent years. Behind the success of deep learning, there is much space for improvement. It is difficult to identify if a testing sample can be represented by the deep network effectively before we examining the final result. In this paper, we proposed a dynamic boosting strategy according to reconstruction error in deep networks. We use reconstruction error to determine whether the result is reliable or not. From the perspective of prediction interval, we demonstrated that with the increase of reconstruction error, the prediction interval would become bigger. Therefore, the classification result is not reliable when the reconstruction error exceeds the predetermined threshold. Since we can record the reconstruction error as well as the classification error for all training samples in training set. We can learn an extra boosting model besides the deep network in training set to improve the performance of the model. An important factor in learning the boosting model is to determine an appropriate threshold for selecting training samples. In testing, we first examine whether the reconstruction error of a testing sample exceeds the threshold to determine if we should use the boosting model. If the boosting model is used, the final result is the average of the output of the deep network and the boosting model. We conducted experiments on two widely used classification datasets and an air quality dataset. From the experiments, we see that our boosting strategy is effective in improving the performance of classification. We tested several boosting models in this paper. They can all reduce the test error to some extent under appropriate parameter settings.

Traffic flow prediction is a fundamental problem in transportation modeling and management. Many existing approaches fail to provide favorable results due to being: 1) shallow in architecture; 2) hand engineered in features; and 3) separate in learning. In this paper we propose a deep architecture that consists of two parts, i.e., a deep belief network (DBN) at the bottom and a multitask regression layer at the top. A DBN is employed here for unsupervised feature learning. It can learn effective features for traffic flow prediction in an unsupervised fashion, which has been examined and found to be effective for many areas such as image and audio classification. To the best of our knowledge, this is the first paper that applies the deep learning approach to transportation research. To incorporate multitask learning (MTL) in our deep architecture, a multitask regression layer is used above the DBN for supervised prediction. We further investigate homogeneous MTL and heterogeneous MTL for traffic flow prediction. To take full advantage of weight sharing in our deep architecture, we propose a grouping method based on the weights in the top layer to make MTL more effective. Experiments on transportation data sets show good performance of our deep architecture. Abundant experiments show that our approach achieved close to 5% improvements over the state of the art. It is also presented that MTL can improve the generalization performance of shared tasks. These positive results demonstrate that deep learning and MTL are promising in transportation research.

Causal graphical models are developed to detect the dependence relationships between random variables and provide intuitive explanations for the relationships in complex systems. Most of existing work focuses on learning a single graphical model for all the variables. However, a single graphical model cannot accurately characterize the complicated causal relationships for a relatively large graph. In this paper, we propose the problem of estimating an overlapping decomposition for Gaussian graphical models of a large scale to generate overlapping sub-graphical models. Specifically, we formulate an objective function for the overlapping decomposition problem and propose an approximate algorithm for it. A key theory of the algorithm is that the problem of solving a κ+1 node graphical model can be reduced to the problem of solving a one-step regularization based on a solved κ node graphical model. Based on this theory, a greedy expansion algorithm is proposed to generate the overlapping subgraphs. We evaluate the effectiveness of our model on both synthetic datasets and real traffic dataset, and the experimental results show the superiority of our method.

In many real-world situations, different and often opposite opinions, innovations, or products are competing with one another for their social influence in a networked society. In this paper, we study competitive influence propagation in social networks under the competitive linear threshold (CLT) model, an extension to the classic linear threshold model. Under the CLT model, we focus on the problem that one entity tries to block the influence propagation of its competing entity as much as possible by strategically selecting a number of seed nodes that could initiate its own influence propagation. We call this problem the influence blocking maximization (IBM) problem. We prove that the objective function of IBM in the CLT model is submodular, and thus a greedy algorithm could achieve 1 — 1/e approximation ratio. However, the greedy algorithm requires Monte-Carlo simulations of competitive influence propagation, which makes the algorithm not efficient. We design an efficient algorithm CLDAG, which utilizes the properties of the CLT model, to address this issue. We conduct extensive simulations of CLDAG, the greedy algorithm, and other baseline algorithms on real-world and synthetic datasets. Our results show that CLDAG is able to provide best accuracy in par with the greedy algorithm and often better than other algorithms, while it is two orders of magnitude faster than the greedy algorithm.

The problem of influence maximization, i.e., mining top-k influential nodes from a social network such that the spread of influence in the network is maximized, is NP-hard. Most of the existing algorithms for the prob- lem are based on greedy algorithm. Although greedy algorithm can achieve a good approximation, it is computational expensive. In this paper, we propose a totally different approach based on Simulated Annealing(SA) for the influence maximization problem. This is the first SA based algorithm for the problem. Additionally, we propose two heuristic methods to accelerate the con- vergence process of SA, and a new method of comput- ing influence to speed up the proposed algorithm. Experimental results on four real networks show that the proposed algorithms run faster than the state-of-the-art greedy algorithm by 2-3 orders of magnitude while being able to improve the accuracy of greedy algorithm.

With the proliferation of mobile devices and wireless technologies, mobile social network systems are increasingly available. A mobile social network plays an essential role as the spread of information and influence in the form of "word-of-mouth". It is a fundamental issue to find a subset of influential individuals in a mobile social network such that targeting them initially (e.g. to adopt a new product) will maximize the spread of the influence (further adoptions of the new product). The problem of finding the most influential nodes is unfortunately NP-hard. It has been shown that a Greedy algorithm with provable approximation guarantees can give good approximation; However, it is computationally expensive, if not prohibitive, to run the greedy algorithm on a large mobile network.

Mobile social network is a typical social network where one or more individuals of similar interests or commonalities, conversing and connecting with one another using the mobile phone. Our works in this paper focus on the experimental study for this kind of social network with the support of large-scale real mobile call data. The main contributions can be summarized as three-fold: firstly, a large-scale real mobile phone call log of one city has been extracted from a mobile phone carrier in China to construct mobile social network; secondly, common features of traditional social networks, such as power law distribution and small diameter etc, have been experimented, with which we confirm that the mobile social network is a typical scale-free network and has small-world phenomenon; lastly, different from traditional analytical methods, important properties of the actors, such as gender and age, have been introduced into our experiments with some interesting findings about human behavior, for example, the middle-age people are more active than the young and old people, and the female is unusual more active than the male while in the old age.

An increasing number of large-scale applications exploit peer-to-peer network architecture to provide highly scalable and flexible services. Among these applications, data management in peer-to-peer systems is one of the interesting domains. In this paper, we investigate the multidimensional skyline computation problem on a structured peer-to-peer network. In order to achieve low communication cost and quick response time, we utilize the iMinMax(\theta ) method to transform high-dimensional data to one-dimensional value and distribute the data in a structured peer-to-peer network called BATON. Thereafter, we propose a progressive algorithm with adaptive filter technique for efficient skyline computation in this environment. We further discuss some optimization techniques for the algorithm, and summarize the key principles of our algorithm into a query routing protocol with detailed analysis. Finally, we conduct an extensive experimental evaluation to demonstrate the efficiency of our approach.

Traffic flow prediction is a basic function of Intelligent Transportation System. Due to the complexity of traffic phenomenon, most existing methods build complex models such as neural networks for traffic flow prediction. As a model may lose effect with time lapse, it is important to update the model on line. However, the high computational cost of maintaining a complex model puts great challenge for model updating. The high computation cost lies in two aspects: computation of complex model coefficients and huge amount training data for it. In this paper, we propose to use a nonparametric approach based on locally weighted learning to predict traffic flow. Our approach incrementally incorporates new data to the model and is computationally efficient, which makes it suitable for online model updating and predicting. In addition, we adopt wavelet analysis to extract the periodic characteristic of the traffic data, which is then used for the input of the prediction model instead of the raw traffic flow data. The primary experiments on real data demonstrate the effectiveness and efficiency of our approach.