Every graph hides a tree: through tree decomposition—a foundational tool in modern graph theory with broad applications such as in computational power networks, any network can be unfolded into a hierarchy of overlapping vertex bags whose backbone is a tree. Leveraging this powerful lens, we propose Topological Decomposition for Self-supervised Learning (TopDSL), a framework that injects multi-scale signals into graph representation learning. Concretely, we: 1) decompose the input graph into tree structures with bags representing local structural contexts; 2) compute bag-level roles via closeness centrality for nodes and local edge betweenness for edges, and aggregate these scores across bags to capture context-dependent importance (e.g., local structural bridges); 3) convert the resulting importance and attribute-stability scores into a context-aware augmentation policy that adaptively perturbs nodes, edges, and features—preserving local bridges, honoring multi-community vertices, and attenuating noisy global hubs; 4) construct a new structural similarity loss for contrastive learning, which fuses traditional graph-based proximity with a novel tree-based similarity derived from node co-occurrence in decomposition bags; 5) demonstrate that our framework achieves superior performance over state-of-the-art baselines on various graph learning benchmarks.

Multi-Graph Learning (MGL) is a fundamental machine learning paradigm that represents objects as bags-of-graphs, each encoding a distinct structural property, and has broad applications in bioinformatics, chemistry, computing power networks, and software defect detection. However, the inherent scarcity of labeled data poses a significant bottleneck for supervised MGL approaches. While self-supervised contrastive learning offers a compelling solution, its direct application to MGL faces three key challenges: (1) existing graph neural networks, primarily for single-graph modeling, struggle to yield discriminative bag-level representations from bags-of-graphs; (2) conventional contrastive objectives are limited to single-level settings, failing to capture cross-hierarchical dependencies; and (3) standard data augmentation often disrupts intrinsic graph and bag structures, undermining semantic consistency. To address these issues, we propose the Hierarchical Graph-Bag-Network (HGBN), a self-supervised MGL framework that constructs hierarchical representations in the form of a graph-bag-network. HGBN employs an asymmetric hierarchical graph neural network to learn discriminative graph-level and bag-level representations, introduces cross-hierarchical contrastive objectives to align graph-level and bag-level semantics, and leverages the asymmetric network outputs to form positive and negative pairs, preserving intrinsic structural and semantic consistency. Experiments on eight benchmark multi-graph datasets demonstrate that HGBN consistently outperforms both supervised and self-supervised state-of-the-art baselines, achieving average improvements of 4.82% in accuracy and F1 score.

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.

The Hot Object Cache (HOC) admission policy is one of the core technologies in Content Delivery Network (CDN) cache management and plays a critical role in the broader Computing Power Network (CPN) environment. It primarily employs heuristic- and threshold-based methods. These methods are simple and efficient but fail both to capture latent dependencies among requested objects and to support informed admission decisions. We propose a reinforcement learning approach called LEI for multi-object CDN admission (i.e., sequences of request objects across multiple time instants, which include multiple objects requested at each instant). LEI integrates three key components: a Multi-Object Time Encoding (MO-TE) mechanism, which uses density-based representations to model multi-object temporal sequences; a Buffer Mechanism, which addresses the reward-latency issue by buffering historical decision information; and a dual-head network architecture with a two-stage training strategy, which enhances the model's admission decision-making capability and long-term stability. Experiments on four public datasets demonstrate that LEI improves the HOC request hit rate by 5-12% and the HOC byte hit rate by 5-42% compared with state-of-the-art methods. It also reduces disk cache (DC) read and write rates.

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.

To be still yet still moving. - Do Hyun Choe

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.

Community search is a fundamental problem in graph analysis. However, prevailing community search models predominantly focus on non-attributed or vertex-attributed graphs. Real-world graphs often bear crucial information within their edges, depicting intricate interactions among vertices. Integrating this edge-based information becomes pivotal in refining community search methodologies. In this paper, we proposed the Edge-Attributed Community Search (EACS) problem and proved that the EACS problem is NP-hard. Advanced exact and 2-approximation algorithms are proposed to address the EACS problem. Extensive experiments demonstrate the efficiency and effectiveness of our algorithms.

Community search is a fundamental graph processing task that aims to find a community containing the given query node. Recent studies show that machine learning (ML)-based community search can return higher-quality communities than the classic methods such as k-core and k-truss. However, the state-of-the-art ML-based models require a large number of labeled data (i.e., nodes in ground-truth communities) for training that are difficult to obtain in real applications, and incur unaffordable memory costs or query time for large datasets. To address these issues, in this paper, we present the community search based on contrastive learning with partition, namely COCLEP, which only requires a few labels and is both memory and query efficient. In particular, given a small collection of query nodes and a few (e.g., three) corresponding ground-truth community nodes for each query, COCLEP learns a query-dependent model through the proposed graph neural network and the designed label-aware contrastive learner. The former perceives query node information, low-order neighborhood information, and high-order hypergraph structure information, the latter contrasts low-order intra-view, high-order intra-view, and low-high-order inter-view representations of the nodes. Further, we theoretically prove that COCLEP can be scalable to large datasets with the min-cut over the graph. To the best of our knowledge, this is the first attempt to adopt contrastive learning for community search task that is nontrivial. Extensive experiments on real-world datasets show that COCLEP simultaneously achieves better community effectiveness and comparably high query efficiency while using fewer labels compared with the-state-of-the-art approaches and is scalable for large datasets.

This paper presents a novel spatial query, skyline micro-cluster (SMC) query. Given a set of data points P, a query point q, a radius γ and a density parameter k, the SMC query returns the skyline micro-clusters (MCs), where MC is a set of points in P that can be covered by a circle with radius γ and the number of points in MC is at least k. In this paper, we formally define the SMC query. As the brute-force approach to solving the SMC query in massive datasets has high computation and memory costs, we propose a basic skyline micro-cluster query algorithm, BSMC, which can reduce the time complexity from O(2N) to O(N3). Furthermore, on top of BSMC, we propose an efficient skyline micro-cluster query algorithm (ESMC). In ESMC, we use the z-value index and propose a filter to remove the invalid micro-clusters, which reduces significant computation overhead. To reduce the memory overhead, we propose an incremental skyline query method. A comprehensive performance study is conducted on real datasets and the experimental results show that our proposed method, ESMC, can significantly improve the SMC query performance.

Given a graph, searching for a community containing a query vertex is a fundamental problem and has found many applications. Most existing community search models are based on non-attributed or vertex-attributed graphs. In many real-world graphs, however, the edges carry the richest information to describe the interactions between vertices; hence, it is important to take the information into account in community search. In this paper, we conduct a pioneer study on the community search on edge-attributed graphs. We proposed the Edge-Attributed Community Search (EACS) problem, which aims to extract a subgraph that contains the given query vertex while its edges have the maximum attribute similarity. We prove that the EACS problem is NP-hard and propose both exact and 2-approximation algorithms to address EACS. Our exact algorithms run up to 2320.34 times faster than the baseline solution. Our approximate algorithms further improve the efficiency by up to 2.93 times. We conducted extensive experiments to demonstrate the efficiency and effectiveness of our algorithms.

Density Peaks (DP) Clustering organizes data into clusters by finding peaks in dense regions. This involves computing density ($\rho$) and distance ($\delta$) of every point. As such, though DP has been very effective in producing high quality clusters, their complexity is O($N^2$) where$N$is the number of data points. In this paper, we propose a fast distributed density peaks clustering algorithm, FDDP, based on the z-value index. In FDDP, we first employ the z-value index to map multi-dimensional data points into one dimensional space, and then range-partition the data according to the z-value to balance the load across the processing nodes. We ensure minimal overlapping range to handle computations at the boundary points. We also propose FC, an efficient algorithm that employs a forward computing strategy to calculate$\rho$linearly. Additionally, we propose another algorithm, CB, which uses a caching and efficient searching strategy to compute$\delta$. Moreover, FDDP is able to reduce the time complexity from$O(N^2)$to$O(N\cdot log(N))$. We provide a theoretical analysis of FDDP and evaluated FDDP empirically. Our experimental results show that FDDP outperforms the state-of-the-art algorithms significantly.

Density Peaks (DP) Clustering organizes data into clusters by finding peaks in dense regions. This involves computing density (ρ) and distance (δ) of every point, and the time complexity is O(N2) where N is the number of data points. In this paper, we propose a fast distributed density peaks clustering algorithm, FDDP, based on the z-value index. We also propose FC, an efficient algorithm that employs a forward computing strategy to calculate ρ linearly, and CB, which uses a caching and efficient searching strategy to compute δ. Our experimental results show that FDDP outperforms the state-of-the-art algorithms significantly.

Graphs are a powerful and versatile data structure that easily captures real life relationship. Multi-graph Multi-label learning (MGML) is a supervised learning task, which aims to learn a Multi-label classifier to label a set of objects of interest (e.g. image or text) with a bag-of-graphs representation. However, prior techniques on the MGML are developed based on transferring graphs into instances that does not fully utilize the structure information in the learning, and focus on learning the unseen labels only at the bag level. There is no existing work studying how to label the graphs within a bag that is of importance in many applications like image or text annotation. To bridge this gap, in this paper, we present a novel coarse and fine-grained Multi-graph Multi-label (cfMGML) learning framework which directly builds the learning model over the graphs and empowers the label prediction at both the coarse (aka. bag) level and fine-grained (aka. graph in each bag) level. In particular, given a set of labeled multi-graph bags, we design the scoring functions at both graph and bag levels to model the relevance between the label and data using specific graph kernels. Meanwhile, we propose a thresholding rank-loss objective function to rank the labels for the graphs and bags and minimize the hamming-loss simultaneously at one-step, which aims to address the error accumulation issue in traditional rank-loss algorithms. To tackle the non-convex optimization problem, we further develop an effective sub-gradient descent algorithm to handle high-dimensional space computation required in cfMGML. Experiments over various real-world datasets demonstrate cfMGML achieves superior performance than the state-of-arts algorithms.

Advanced microarray technologies have enabled to simultaneously monitor the expression levels of all genes. An important problem in microarray data analysis is to discover phenotype structures. The goal is to 1) find groups of samples corresponding to different phenotypes (such as disease or normal), and 2) for each group of samples, find the representative expression pattern or signature that distinguishes this group from others. Some methods have been proposed for this issue, however, a common drawback is that the identified signatures often include a large number of genes but with low discriminative power. In this paper, we propose a $(g^\ast)$-sequence model to address this limitation, where the ordered expression values among genes are profitably utilized. Compared with the existing methods, the proposed sequence model is more robust to noise and allows to discover the signatures with more discriminative power using fewer genes. This is important for the subsequent analysis by the biologists. We prove that the problem of phenotype structure discovery is NP-complete. An efficient algorithm, FINDER, is developed, which includes three steps: 1) trivial $(g^\ast)$-sequences identifying, 2) phenotype structure discovery, and 3) refinement. Effective pruning strategies are developed to further improve the efficiency. We evaluate the performance of FINDER and the existing methods using both synthetic and real gene expression data sets. Extensive experimental results show that FINDER dramatically improves the accuracy of the phenotype structures discovered (in terms of both statistical and biological significance) and detects signatures with high discriminative power. Moreover, it is orders of magnitude faster than other alternatives.

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.

Clustering is a popular technique for analyzing microarray data sets, with n genes and m experimental conditions. As explored by biologists, there is a real need to identify coregulated gene clusters, which include both positive and negative regulated gene clusters. The existing pattern-based and tendency-based clustering approaches cannot directly be applied to find such coregulated gene clusters, because they are designed for finding positive regulated gene clusters. In this paper, in order to cluster coregulated genes, we propose a coding scheme that allows us to cluster two genes into the same cluster if they have the same code, where two genes that have the same code can be either positive or negative regulated. Based on the coding scheme, we propose a new algorithm for finding maximal subspace coregulated gene clusters with new pruning techniques. A maximal subspace coregulated gene cluster clusters a set of genes on a condition sequence such that the cluster is not included in any other subspace coregulated gene clusters. We conduct extensive experimental studies. Our approach can effectively and efficiently find maximal subspace coregulated gene clusters. In addition, our approach outperforms the existing approaches for finding positive regulated gene clusters.