Recently, k-vertex connected component (k-VCC) detection has gained significant attention in graph analysis owing to its ability to capture structural cohesion. A k-VCC remains connected even after the removal of any k-1 vertices from itself. The k-VCC has broad applications across multiple domains, such as social network analysis, cybersecurity, and bioinformatics. Yet, the existing exact k-VCC detection algorithms require repeated computation of minimum vertex cuts, imposing a prohibitive computational cost for large scale graphs. In this paper, we present an approximate algorithm for k-VCC detection that leverages Monte Carlo sampling to accelerate minimum vertex cut computation with theoretical guarantee. Further, we design a distributed algorithm for mining all k-VCCs, named DkVCC. DkVCC adopts a divide-and-conquer strategy, decomposing the problem into smaller subgraph mining tasks that can be executed concurrently. Specifically, we generate tasks from individual vertices to construct initial subgraphs, and then iteratively expand and merge the subgraphs to form the final k-VCCs. Extensive experiments on 5 large real datasets demonstrates the efficiency of our proposed algorithms. For example, we achieve 4× runtime speedup on the LiveJournal dataset with 3.99M vertices and 34.7M edges in a 3-node cluster.

Graph stream summarization refers to the technique used to process graph streams-unbounded sequences of edges-by constructing compressed representations that support approximate queries on both graph topology and temporal information in computing power networks. However, existing methods struggle to achieve accurate and efficient temporal queries due to two key limitations: (1) inefficient integration of temporal information, leading to high latency in both edge processing and query execution; and (2) redundant multilayer structures that accumulate errors, significantly reducing query accuracy. In this paper, we propose GRIT, an accurate and efficient Graph stReam summarIzation for Temporal query. GRIT introduces a new structure FlatIndex, which organizes temporal information in a flattened form, playing a critical role in minimizing error accumulation and ensuring accurate temporal queries. To further enhance edge processing efficiency, we introduce a lazy update strategy, which updates only a single element in the FlatIndex upon edge insertion, significantly reducing insertion latency. Moreover, our greedy-based decomposition (GBD) algorithm decomposes the target query range into the minimal number of intervals corresponding to the FlatIndex, enabling efficient execution of temporal queries over arbitrary time ranges. Extensive experiments on five real-world datasets demonstrate that GRIT improves query accuracy by 2-3 orders of magnitude, while reducing query latency by 1-2 orders of magnitude and increasing throughput by 7-13 times compared to state-of-the-art methods.

Network resilience refers to the ability of a network to maintain its functionality despite perturbations, where resilience/robustness is shown when a substantial proportion of its nodes remain engaged even under changes. Such phenomenon is common in real-world networks, such as computing power networks. Previous works demonstrate that the coreness of a user/node effectively captures the dynamics of user engagement. However, most existing works only consider changes in a single coreness value and thus fail to measure the overall network resilience. Subsequent works are either inefficient or do not consider coreness-decreased scenario. In this paper, we propose and study the collapsed follower maximization problem, aiming to maximize the number of coreness-decreased vertices by finding a group collapser (collapsing a set of vertices) with a given budget. We prove that the problem is NP-hard and W[2]-hard parameterized by the budget b. To address the problem, we first present a Greedy algorithm that iteratively finds the best collapser in each of the budget b iterations. To further optimize the Greedy algorithm, we propose GreedyOpt, which leverages the shell component structure to accelerate the computation of follower for one collapser and prune the search space. Extensive experimental results on 8 real-world datasets show that the effectiveness and efficiency of our algorithms.

Graph Neural Networks (GNNs) are the rising standard for graph tasks, yet their distributed training in servers or computing power network remains challenging. Cross-machine sampling and data loading often create bottlenecks, leading to inefficient resource utilization. In this paper, we present Hybrid2, a distributed GNN training system that combines full-graph and mini-batch training through a novel hybrid-batch training method. It also adopts hybrid feature extraction, leveraging both local caching and remote access to improve feature retrieval efficiency. The integration of these methods in Hybrid² results in a dual hybrid-gain effect. First, it reduces sampling and loading overhead by pre-aggregating neighbors for each target vertex, minimizing the layers to sample and load. Second, it accelerates data loading by dynamically identifying and locally caching the most frequently accessed vertices during training, maximizing memory efficiency. Experimental results demonstrate that Hybrid² brings substantial performance improvements across key components of distributed GNN training. Network communication overhead is reduced by up to tens of times, while both sampling and loading achieve at least several-fold speedups. These gains contribute to an overall training acceleration exceeding 20× compared to DistDGL, all with comparable GPU memory usage and no loss in accuracy. Compared to the state-of-the-art system, it achieves nearly 3× speedup while using fewer resources.

Bipartite graph models the relationship between two different sets of entities. Such graph data become more dynamic and are organized as stream with duplicate edges in real-word applications such as customer-product in e-commerce. A butterfly, (2,2)-biclique, is the simplest cohesive substructure and of great importance in a bipartite graph. However, it is challenging to estimate the number of butterflies in large scale and high dynamic bipartite graph stream when given a limited memory. Besides, existing works for butterfly counting assume no duplicate edges in the bipartite graph stream, which cause less accuracy in bipartite graph stream with duplicate edges. In this paper, we propose FABLE, a Fixed-size memory Approximate Butterfly counting algorithm for dupLicate Edges in bipartite graph stream. In FABLE, we compute the number of distinct edges by maintaining an ordered list of edge priorities for replacement and sampling. We provide theoretical proof of unbiasedness and derive the variance of butterfly count. Our extensive experiments on 5 real-world datasets confirm that our approach has higher accuracy compared with the baseline method under the same memory usage.

As real-world graph data continues to grow larger and larger, training large graphs in a distributed environment is becoming increasingly prevalent. However, network transmission in a distributed environment can hinder subsequent training steps, resulting in suboptimal training performance. After conducting a comprehensive analysis and experimental demonstration, we have discovered that during the training process, there exist certain data that can be computed once and reused multiple times. In addition, we also found that after a certain iterations of training, the parameter updates during each iteration had minimal effect on the parameters. Based on these findings, we have improved the original implementation and proposed a cache-enhanced distributed graph training system, NeutronCache. It utilizes cached reusable intermediate data and a dynamically adjusted stale embedding reuse strategy, reducing network overhead in distributed systems and accelerating the training process. Through experimental validation, our implementation achieved acceleration ranging from 1.4X to 16.61X on real graph datasets with almost no loss in accuracy.

Attributed Heterogeneous Information Networks (AHINs) amalgamate the advantages of attributed graphs (AGs) and heterogeneous information networks (HINs) to model intri-cate systems. Within this context, community search-aiming to identify the most probable community containing the queried ver-tex-has been extensively explored in AGs and HINs. However, existing methodologies fall short in simultaneously accommodating heterogeneous attributes and multiple meta-paths in AHINs, posing a substantial challenge in investigating community search within expansive AHINs. Recent studies highlight the efficacy of machine learning-based community search, offering enhanced flexibility and higher-quality communities in comparison to traditional structural-based methods. Yet, semi-supervised learning methods demand substantial labeled data and incur considerable memory and time costs when applied to large AHINs. To tackle these challenges, we propose a MK (Most-likely; K-sized) community search approach. This approach involves defining an MK community and leveraging Graph Neural Networks (GNNs) to amalgamate structures and attributes into a unified goodness metric. Our methodology involves training on local subgraphs sampled via guided random walks based on multiple meta-paths, circumventing the need for training on the entire graph. Moreover, attention-based GNNs adeptly learn meta-path weights to guide weighted walks in subsequent iterations. Additionally, self-training is employed to alleviate the labeling burden. We also demonstrate that pinpointing the location for the MK community is NP-hard and present a heuristic local search strategy that expedites the resolution process through rewriting. Ultimately, the convergence of iterations yields the solution. Extensive experiments conducted on four real-world datasets underscore that the MK framework significantly enhances both effectiveness and efficiency in community search within AHINs. Our code is publicly available at https://github.com/uucxuu/CSAH.

Diagnostic genes refer to the genes closely related to a specific disease phenotype, the powers of which to distinguish between different classes are often high. Most methods to discovering the powerful diagnostic genes are either singleton discriminability-based or combination discriminability-based. However, both ignore the abundant interactions among genes, which widely exist in the real world. In this paper, we tackle the problem from a new point of view and make the following contributions: (1) we propose an EWave model, which profitably exploits the ordered expressions among genes based on the defined equivalent dimension group sequences taking into account the "noise" universal in the real data, (2) we devise a novel sequence rule, namely interesting non-redundant contrast sequence rule, which is able to capture the difference between different phenotypes in a high accuracy using as few as possible genes, (3) we present an efficient algorithm called NRMINER to find such rules. Unlike the conventional column enumeration and the more recent row enumeration, it performs a novel template-driven enumeration by making use of the special characteristic of micro array data modeled by EWave. Extensive experiments conducted on various synthetic and real datasets show that: (1) NRMINER is significantly faster than the competing algorithm by up to about one order of magnitude, (2) it provides a higher accuracy using fewer genes. Many diagnostic genes discovered by NRMINER are proved biologically related to some disease.