The recent prosperity of temporal graph research redefines many traditional concepts on static graphs, such as triangle, motif,$k$-core, etc. Inspired by that, we propose a novel$(k, \delta)$-truss on temporal graphs, which requires its triangles to exist in short enough time windows ever. The$(k,\delta)$-truss satisfies both static and temporal cohesion, while the original$k$-truss is its special case when$\delta=\infty$. In order to address the$(k, \delta)$-truss query, we propose both index-free and index-based approaches. By leveraging the dual containment relation on$(k, \delta)$-trusses, our indexes can compress all$(k, \delta)$-trusses losslessly into map or tree structures with dramatically less space, so that a specific$(k,\ \delta)$-truss can be retrieved from indexes in the optimal time. To enable our index to scale to large temporal graphs, we develop two index construction algorithms that can reduce redundant computation significantly, based on truss decomposition and truss maintenance respectively. The experimental results demonstrate that index-based approaches process queries in interactive time and outperform the index-free approach by 2~4 orders of magnitude, while indexes achieve compression ratios up to 10-4.

Community detection is a fundamental yet important task for characterizing and understanding the structure of attributed graphs. Existing methods mainly focus on the structural tightness and attribute similarity among nodes in a community. However, grouping numerous semantically homogeneous nodes will result in information cocoons and thus reduce the robustness of community structure and the efficiency of node collaboration in real-world applications, such as recommendation systems and collaboration networks. Since nodes with closer connections tend to be more similar, finding communities with dense structures and diverse attributes poses great challenges to mining latent relationships between the graph structure and attribute distribution. To our best knowledge, very little research has been conducted to address this challenge. In this article, we propose a novel three-view graph attention neural networks (TvGANN) model to formally address the attribute diversity aware community detection problem. TvGANN reveals correlations between the graph structure and attributes distribution from the perspective of node organization, attribute co-occurrence, and the node-attribute interaction. It effectively captures structural features and attributes distribution by feeding a structural network and an attribute co-occurrence network into graph attention modules through the encoder–decoder framework. It also learns heterogeneous information by feeding a network into a meta-node attention module. Then, it fuzes the three modules and clusters the embedding representations through a Student's t -distribution approach, which iteratively refines the clustering results. The experiments show that our method not only improves the quality in dense community detection but also performs efficiently for attributed graphs.

Incremental maximal clique enumeration (IMCE), which maintains maximal cliques in dynamic graphs, is a fundamental problem in graph analysis. A maximal clique has a solid descriptive power of dense structures in graphs. Real-world graph data is often large and dynamic. Studies on IMCE face significant challenges in the efficiency of incremental batch computation and hybrid edge changes. Moreover, with growing graph sizes, new requirements occur on indexing global maximal cliques and obtaining maximal cliques under specific vertex scope constraints. This work presents a new data structure SOMEi to maintain intermediate maximal cliques during construction. SOMEi serves as a space-efficient index to retrieve scope-constrained maximal cliques on the fly. Based on SOMEi, we design a procedure-oriented IMCE algorithm to deal with hybrid edge changes within a unified algorithm framework. In particular, the algorithm is able to process a large batch of edge changes and significantly improve the average processing time of a single edge change through an efficient pruning strategy. Experimental results on real and synthetic graph data demonstrate that the proposed algorithm outperforms all the baselines and achieves good efficiency through pruning.

In recent years, hypergraph analysis have attracted increasing attention due to their ability to model complex data correlation, with hypergraph clustering being one of the most important tasks. However, when the scale of hypergraph is large enough, clustering is difficult based on global consistency. Existing flow-based hypergraph local clustering methods have good theoretical cut improvements and runtime guarantees. However, these methods exhibit poor performance when the initial reference node set is small and are prone to causing the output set to shrink into a small subset, resulting in local minima. To address this issue, we propose the Penalized Flow Hypergraph Local Clustering(PFHLC) and provide new conductance guarantees and runtime analyses for our method. First, we use the random walk method to grow the initial seed set, and introduce the random walk information of nodes as penalized flow into the flow-based framework to optimize the output. Second, we propose a generalized objective function containing random walk information, which takes full advantage of the semi-supervised information of the target cluster to protect important nodes. This feature can avoid the local minima of previous flow-based methods. Importantly, our method is strongly-local and can run efficiently on large-scale hypergraphs. We contribute a real-world dataset and the experiments on real-world large-scale datasets show that PFHLC achieves the state-of-the-art significantly.

Streaming computation for large graphs on parallel systems faces challenges in task decomposition, data skew, and resource scheduling. In this work, we propose a general parallel streaming framework for the node-centered graph algorithms to improve the computation efficiency. We construct the parallel procedure of the incremental maximal clique enumeration (IMCE) task and accelerate the incremental Candidate Map Constructor (CMC) algorithm through the framework for large-scale streaming graphs. Experimental results on three large real-world graphs show the framework’s positive effect on the algorithm’s execution time.

Data mining in infectious disease pandemic scenarios is a complex giant task involving data from various fields and requirements of real-time and dynamic. In this paper, we propose a graph mining system for the infectious disease pandemic, IDGMS, with one-stop, dynamic, and interactive characteristics. The system has been applied to solve problems from three view scales and performs well. The system is constructed as a loose coupling structure at the front and back ends and can be extended to more graph mining issues. To the best of our knowledge, we are the first graph system especially targeting data mining of infectious diseases.

The advancement of science and technology provides the possibility of personalized intelligent education. Representation learning of students’ behavior data is challenging because whether time sequences and interactive behaviors or the correlation between knowledge points and students carrying important information. Some researchers propose knowledge tracing to provide ideas for solving this dilemma. However, existing knowledge tracing methods are divided into machine learning and deep learning. Machine learning-based methods require manual feature extraction and a large amount of prior knowledge. Although deep learning-based methods can automatically extract features, most methods either only use the time series information of the data, or use the association between knowledge points. All the methods ignore the association between knowledge points and students. To fill this gap, we propose a Gated Heterogeneous Graph Convolutional Network (GHGCN) model. We utilize the encoder-decoder framework to predict student performance using the representations of nodes, which is learned from heterogeneous convolutional networks and gate recurrent unit. To validate the effectiveness of the proposed GHGCN model, we conduct the experiments on three public datasets: Simulated Data, Assistments 2009, and Assistments 2015. The results indicate that our method can achieve better performance compared with state-of-the-art algorithms.

In the emerging business of food delivery, rider traffic accidents raise financial cost and social traffic burden. Although there has been much effort on traffic accident forecasting using temporal-spatial prediction models, none of the existing work studies the problem of detecting the takeaway rider accidents based on food delivery trajectory data. In this article, we aim to detect whether a takeaway rider meets an accident on a certain time period based on trajectories of food delivery and riders’ contextual information. The food delivery data has a heterogeneous information structure and carries contextual information such as weather and delivery history, and trajectory data are collected as a spatial-temporal sequence. In this article, we propose a TakeAway Rider Accident detection fusion network TARA-Net to jointly model these heterogeneous and spatial-temporal sequence data. We utilize the residual network to extract basic contextual information features and take advantage of a transformer encoder to capture trajectory features. These embedding features are concatenated into a pyramidal feed-forward neural network. We jointly train the above three components to combine the benefits of spatial-temporal trajectory data and sparse basic contextual data for early detecting traffic accidents. Furthermore, although traffic accidents rarely happen in food delivery, we propose a sampling mechanism to alleviate the imbalance of samples when training the model. We evaluate the model on a transportation mode classification dataset Geolife and a real-world Ele.me dataset with over 3 million riders. The experimental results show that the proposed model is superior to the state-of-the-art.