Recent advancements in Large Language Models (LLMs) and the proliferation of Text-Attributed Graphs (TAGs) across various domains have positioned LLM-enhanced TAG learning as a critical research area. However, the field faces significant challenges: (1) the absence of a unified framework to systematize the diverse optimization perspectives, and (2) the lack of a robust method capable of handling real-world TAGs, which often suffer from text and edge sparsity, leading to suboptimal performance. To address these challenges, we propose UltraTAG, a unified pipeline for LLM-enhanced TAG learning. UltraTAG provides a comprehensive and domain-adaptive framework that not only organizes existing methodologies but also paves the way for future advancements. Building on this framework, we propose UltraTAG-S, a robust instantiation designed to tackle sparsity issues in real-world TAGs. UltraTAG-S employs LLM-based text propagation and augmentation to mitigate text sparsity, while leveraging LLM-augmented node selection based on PageRank and edge reconfiguration strategies to address edge sparsity. Our experiments demonstrate UltraTAG-S significantly outperforms existing baselines, achieving improvements of 2.12% and 17.47% in ideal and sparse settings, respectively. Moreover, as the data sparsity ratio increases, the performance improvement of UltraTAG-S also rises.

Graph Neural Networks (GNNs) have become a pivotal framework for modeling graph-structured data, enabling a wide range of applications from social network analysis to molecular chemistry. By integrating large language models (LLMs), text-attributed graphs (TAGs) enhance node representations with rich textual semantics, significantly boosting the expressive power of graph-based learning. However, this synergy introduces critical vulnerabilities in both topology and text. Although specialized attack methods have been designed for each of these aspects, no work has yet unified them into a comprehensive approach. In this work, we propose the Interpretable Multi-Dimensional Graph Attack (IMDGA), a human-centric framework orchestrating multi-level perturbations across graph structure and textual features. IMDGA utilizes three tightly integrated modules to craft attacks that balance interpretability and impact, enabling a deeper understanding of Graph-LLM vulnerabilities. Through rigorous theoretical analysis and comprehensive empirical evaluations on diverse datasets and architectures, IMDGA demonstrates superior interpretability, attack effectiveness, stealthiness, and robustness compared to existing methods. By exposing these underexplored semantic vulnerabilities, our work offers valuable insights for improving Graph-LLM resilience. Our code is available at https://github.com/bwfan-bit/IMDGA.

Bipartite graphs are widely used to model relationships between entities of different types, where vertices are divided into two disjoint sets. Biclique-preserving clustering is a fundamental operation that retrieves clusters with dense bicliques, enabling various emerging applications. However, existing methods either fail to accurately capture the unique properties of bipartite graphs or significantly overlook the informative higher-order biclique substructure, leading to compromised clustering quality. Additionally, existing methods are overly dependent on biclique enumeration, resulting in poor scalability. To address these challenges, we propose ECRC, a simple yet provable Edge-Centric Reweighting Clustering framework that provides strict approximation guarantees for any biclique. A key advantage of ECRC is its ability to leverage powerful counting instead of exhaustive enumeration, significantly reducing time and space complexity. To further improve efficiency, we propose several effective graph reduction strategies to eliminate the unqualified vertices and edges before calculating the edge-centric weight. Extensive experiments on five datasets show that our algorithms are more efficient and effective compared to six baselines.

Important communities are densely connected subgraphs containing vertices with high importance values, which have received wide attention recently. However, existing methods, predominantly based on the$k$-core model, suffer from limitations such as rigid degree constraints and suboptimal density, often failing to capture highly important vertices. To address these limitations, we propose a new community model based on pseudoarboricity that guarantees near-optimal density while preserving important vertices. Further, we introduce a novel problem of Psudoarboricity-based Skyline Important Community (PSIC), which uniquely treats density and importance as independent attributes. To efficiently address PSIC, we first devise a basic algorithm climbStairs, which iteratively refines communities by peeling vertices with low importance. To boost efficiency, we develop an advanced algorithm DivAndCon, which employs a recursive divide-and-conquer strategy combined with weight-based and pseudoarboricity-based pruning techniques, significantly reducing the search space. For massive graphs with billions of edges, inspired by a recursive division tree, we develop several parallel algorithms utilizing thread-pool and free-synchronization mechanism. Finally, we conduct extensive experiments on 10 real-world networks, and the results demonstrate the superiority of our solutions in terms of effectiveness, efficiency, and scalability.

Electrical closeness centrality is a classical and robust graph centrality measure. However, existing algorithms for computing electrical closeness centrality are often computationally expensive for large graphs, as they require determining the diagonal elements of the pseudo-inverse of the graph Laplacian matrix, denoted as$L^\dagger$. To address this challenge, we propose novel solutions for approximating$L^\dagger$by establishing a connection with the inverse of a Laplacian submatrix$L_{v}$, which is obtained by removing the$v$-th row and column from the original Laplacian matrix$L$. A key advantage of this connection is that$L_{v}^{-1}$admits various insightful combinatorial interpretations. Specifically, we present two novel interpretations of$L_{v}^{-1}$based on spanning trees and loop-erased random walks, which facilitate the development of efficient sampling algorithms. Building upon these theoretical insights, we introduce two algorithms for efficiently approximating electrical closeness centrality. We extensively evaluate the performance of our algorithms on five real-world datasets. Experimental results demonstrate that our approaches significantly outperform state-of-the-art methods by several orders of magnitude in both running time and estimation accuracy.

Identifying locally dense communities closely connected to the user-initiated query node is crucial for a wide range of applications. Existing approaches either solely depend on rule based constraints or exclusively utilize deep learning technologies to identify target communities. Therefore, an important question is proposed: can deep learning be integrated with rule-based constraints to elevate the quality of community search? In this paper, we affirmatively address this question by introducing a novel approach called Neural Community Search via Attribute augmented Conductance, abbreviated as NCSAC. Specifically, NCSAC first proposes a novel concept of attribute-augmented conductance, which harmoniously blends the (internal and ex ternal) structural proximity and the attribute similarity. Then, NCSAC extracts a coarse candidate community of satisfactory quality using the proposed attribute-augmented conductance. Subsequently, NCSAC frames the community search as a graph optimization task, refining the candidate community through sophisticated reinforcement learning techniques, thereby producing high-quality results. Extensive experiments on six real world graphs and ten competitors demonstrate the superiority of our solutions in terms of accuracy, efficiency, and scalability. Notably, the proposed solution outperforms state-of-the-art methods, achieving an impressive F1-score improvement ranging from 5.3% to 42.4%. For reproducibility purposes, the source code is available at https://github.com/longlonglin/ncsac.

Bipartite graphs are widely used to model relationships between entities of different types, where nodes are divided into two disjoint sets. Similarity search, a fundamental operation that retrieves nodes similar to a given query node, plays a crucial role in various real-world applications, including machine learning and graph clustering. However, existing state of-the-art methods often struggle to accurately capture the unique structural properties of bipartite graphs or fail to incorporate the informative node attributes, leading to suboptimal performance. Besides, their high computational complexity limits scalability, making them impractical for large graphs with millions of nodes and tens of thousands of attributes. To overcome these challenges, we first introduce Attribute-augmented Hidden Personalized PageRank (AHPP), a novel random walk model designed to blend seamlessly both the higher-order bipartite structure proximity and attribute similarity. We then formulate the similarity search over attributed bipartite graphs as an approximate AHPP problem and propose two efficient push-style local algorithms with provable approximation guarantees. Finally, extensive experiments on real-world and synthetic datasets validate the effectiveness of AHPP and the efficiency of our proposed algorithms when compared with fifteen competitors.

In recent years, Graph Neural Networks (GNNs) have made significant advances in processing structured data. However, most of them primarily adopted a model-centric approach, which simplifies graphs by converting them into undirected formats and emphasizes model designs. This approach is inherently limited in real-world applications due to the unavoidable information loss in simple undirected graphs and the model optimization challenges that arise when exceeding the upper bounds of this sub-optimal data representational capacity. As a result, there has been a shift toward data-centric methods that prioritize improving graph quality and representation. Specifically, various types of graphs can be derived from naturally structured data, including heterogeneous graphs, hypergraphs, and directed graphs. Among these, directed graphs offer distinct advantages in topological systems by modeling causal relationships, and directed GNNs have been extensively studied in recent years. However, a comprehensive survey of this emerging topic is still lacking. Therefore, we aim to provide a comprehensive review of directed graph learning, with a particular focus on a data-centric perspective. Specifically, we first introduce a novel taxonomy for existing studies. Subsequently, we re-examine these methods from the data-centric perspective, with an emphasis on understanding and improving data representation. It demonstrates that a deep understanding of directed graphs and their quality plays a crucial role in model performance. Additionally, we explore the diverse applications of directed GNNs across 10+ domains, highlighting their broad applicability. Finally, we identify key opportunities and challenges within the field, offering insights that can guide future research and development in directed graph learning.

Temporal interactions form the crux of numerous real-world scenarios, thus necessitating effective modeling in temporal graph representation learning. Despite extensive research within this domain, we identify a significant oversight in current methodologies: the temporal-spatial dynamics in graphs, encompassing both structural and temporal coherence, remain largely unaddressed. In an effort to bridge this research gap, we present a novel framework termed Graph Representation learning enhanced by Periodic and Community Interactions (GRPCI). GRPCI consists of two primary mechanisms devised explicitly to tackle the aforementioned challenge. Firstly, to utilize latent temporal dynamics, we propose a novel periodicity-based neighborhood aggregation mechanism that underscores neighbors engaged in a periodic interaction pattern. This mechanism seamlessly integrates the element of periodicity into the model. Secondly, to exploit structural dynamics, we design a novel contrastive-based local community representation learning mechanism. This mechanism features a heuristic dynamic contrastive pair sampling strategy aimed at enhancing the modeling of the latent distribution of local com munities within the graphs. Through the incorporation of these two mechanisms, GRPCI markedly augments the performance of graph networks. Empirical evaluations, conducted via a temporal link prediction task across five real-life datasets, attest to the superior performance of GRPCI in comparison to existing state of-the-art methodologies. The results of this study validate the efficacy of GRPCI, thereby establishing a new benchmark for future research in the field of temporal graph representation learning. Our findings underscore the importance of considering both temporal and structural consistency in temporal graph learning, and advocate for further exploration of this paradigm.

As a new distributed graph learning paradigm, Federated Graph Learning (FGL) facilitates collaborative model training across local systems while preserving data privacy. We review existing FGL approaches and categorize their optimization mechanisms into: (1) Server-Client (S-C), where clients upload local model parameters for server-side aggregation and global updates; (2) Client-Client (C-C), which allows direct exchange of information between clients and customizing their local training process. We reveal that C-C shows superior potential due to its refined communication structure. However, existing C-C methods broadcast redundant node representations, incurring high communication costs and privacy risks at the node level. To this end, we propose FedC4, which combines graph Condensation with C-C Collaboration optimization. Specifically, FedC4 employs graph condensation technique to refine the knowledge of each client's graph into a few synthetic embeddings instead of transmitting node-level knowledge. Moreover, FedC4 introduces three novel modules that allow the source client to send distinct node representations tailored to the target client's graph properties. Experiments on eight public real-world datasets show that FedC4 outperforms state-of-the-art baselines in both task performance and communication cost. Our code is now available on https://github.com/Ereshkigal1/FedC4.

Recently, graph neural network (GNN) has emerged as a powerful representation learning tool for graph-structured data. However, most approaches are tailored for undirected graphs, neglecting the abundant information in the edges of directed graphs (digraphs). In fact, digraphs are widely applied in the real world and confirmed to address heterophily challenges. Despite recent advancements, existing spatial- and spectral-based DiGNNs have limitations due to their complex learning mechanisms and reliance on high-quality topology, resulting in low efficiency and unstable performance. To address these issues, we propose Directed Random Walk (DiRW), a plug-and-play strategy for most spatial-based DiGNNs and also an innovative model which offers a new digraph learning paradigm. Specifically, it utilizes a direction-aware path sampler optimized from the perspectives of walk probability, length, and number in a weight-free manner by considering node profiles and topologies. Building upon this, DiRW incorporates a node-wise learnable path aggregator for generalized node representations. Extensive experiments on 9 datasets demonstrate that DiRW: (1) enhances most spatial-based methods as a plug-and-play strategy; (2) achieves SOTA performance as a new digraph learning paradigm. The source code and data are available at https://github.com/dhsiuu/DiRW.

Temporal-constraint subgraph matching has emerged as a significant challenge in the study of temporal graphs, which model dynamic relationships across various domains, such as social networks and transaction networks. However, the problem of temporal-constraint subgraph matching is NP-hard. Furthermore, because each temporal-constraint contains a permutation of temporal parameters, existing subgraph matching acceleration techniques demonstrate limited applicability to temporal-constrained graphs. Traditional continuous subgraph matching approaches prove inadequate in addressing this complex problem due to their inability to effectively handle temporal constraints. This paper addresses the challenge of identifying subgraphs that not only structurally align with a given query graph but also satisfy specific temporal-constraints on the edges. We introduce three novel algorithms to tackle this issue: the TCSM-V2V algorithm, which uses a vertex-to-vertex expansion strategy and effectively prunes non-matching vertices by integrating both query and temporal-constraints into a temporal-constraint query graph; the TCSM-E2E algorithm, which employs an edge-to-edge expansion strategy, significantly reducing matching time by minimizing vertex permutation processes; and the TCSM-EVE algorithm, which combines edge-vertex-edge expansion to eliminate duplicate matches by avoiding both vertex and edge permutations. Notably, our optimal TCSM-EVE algorithm achieves an average three-order-of-magnitude speedup on large-scale datasets. Extensive experiments conducted across 6 datasets demonstrate that our approach outperforms existing methods in terms of both accuracy and computational efficiency.

Triangle counting serves as a foundational operator in graph analysis. Since graph data often contain sensitive information about entities, the release of triangle counts poses privacy concerns. While recent studies have addressed privacy-preserving triangle counting, they mainly concentrate on unsigned graphs. In this paper, we investigate a new problem of developing triangle counting algorithms for signed graphs that adhere to centralized differential privacy and local differential privacy, respectively. The inclusion of edge signs and more classes of triangles leads to increased complexity and overwhelms the statistics with noise. To overcome these problems, we first propose a novel algorithm for smooth-sensitivity computation to achieve differential privacy under the centralized model. In addition, to handle large signed graphs, we devise a computationally efficient function that calculates a smooth upper bound on local sensitivity. Finally, we release the approximate triangle counts after the introduction of Laplace noise, which is calibrated to the smooth upper bound on local sensitivity. In the local model, we propose a two-phase framework tailored for balanced and unbalanced triangle counting. The first phase utilizes the Generalized Randomized Response mechanism to perturb data, followed by a novel response mechanism in the second phase. Extensive experiments conducted over real-world datasets demonstrate that our proposed methods can achieve an excellent trade-off between privacy and utility.

Mining cohesive subgraphs in attributed graphs is an essential problem in the domain of graph data analysis. The integration of fairness considerations significantly fuels interest in models and algorithms for mining fairness-aware cohesive subgraphs. Notably, the relative fair clique emerges as a robust model, ensuring not only comprehensive attribute coverage but also greater flexibility in distributing attribute vertices. Motivated by the strength of this model, we for the first time pioneer an investigation into the identification of the maximum relative fair clique in large-scale graphs. We introduce a novel concept of colorful support, which serves as the foundation for two innovative graph reduction techniques. These techniques effectively narrow the graph's size by iteratively removing edges that do not belong to relative fair cliques. Furthermore, a series of upper bounds of the maximum relative fair clique size is proposed by incorporating consideration of vertex attributes and colors. The pruning techniques derived from these upper bounds can significantly trim unnecessary search space during the branch-and-bound procedure. Adding to this, we present a heuristic algorithm with a linear time complexity, employing both a degree-based greedy strategy and a colored degree-based greedy strategy to identify a larger relative fair clique. This heuristic algorithm can serve a dual purpose by aiding in branch pruning, thereby enhancing overall search efficiency. Extensive experiments conducted on six real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

The q-parameterized magnetic Laplacian serves as the foundation of directed graph (digraph) convolution, enabling this kind of digraph neural network (MagDG) to encode node features and structural insights by complex-domain message passing. Despite their success, limitations still exist: (1) The performance of MagDGs depends on selecting an appropriate q-parameter to construct suitable graph propagation equations in the complex domain. This parameter tuning limits model flexibility and significantly increases manual effort. (2) Most approaches treat all nodes with the same complex-domain propagation and aggregation rules, neglecting their unique digraph contexts. This oversight results in sub-optimal performance. To address the above issues, we propose two key techniques: (1) MAP is crafted to be a plug-and-play complex-domain propagation optimization strategy, enabling seamless integration into any MagDG to improve predictions while enjoying high running efficiency. (2) MAP++ is a new digraph learning framework, further incorporating a learnable mechanism to achieve adaptively edge-wise propagation and node-wise aggregation in the complex domain for better performance. Extensive experiments on 12 datasets demonstrate that MAP enjoys flexibility for it can be incorporated with any MagDG, and scalability as it can deal with web-scale digraphs. MAP++ achieves SOTA predictive performance on 4 different downstream tasks.

The classic clique model has properties of hereditaries and cohesiveness. Here hereditaries means a subgraph of a clique is still a clique. Counting small cliques in a graph is a fundamental operation of numerous applications. However, the clique model is often too restrictive for practical use, leading to the focus on other relaxed-cliques with properties of hereditaries and cohesiveness. To address this issue, we investigate a new problem of counting general hereditary cohesive subgraphs (HCS). All subgraphs with properties of hereditaries and cohesiveness can be called a kind of HCS. To count HCS, we propose a general framework called HCSPivot, which can be applied to count all kinds of HCS. HCSPivot can count most HCS combinatorially without explicitly listing them. Two additional noteworthy features of HCSPivot are its ability to (1) simultaneously count HCS of any size and (2) simultaneously count HCS for each node or each edge. Based on our HCSPivot framework, we propose two novel algorithms with several carefully designed pruning techniques to count s-defective cliques and s-plexes, which are two specific types of HCS. We conduct extensive experiments on 8 large real-world graphs, and the results demonstrate the high efficiency and effectiveness of our solutions.

Identifying the maximum edge biclique in bipartite graphs, a complete bipartite subgraph with the largest number of edges, plays a crucial role in uncovering densely-connected communities and has significant applications in domains such as recommendation systems and biological network analysis. However, this problem is NP-hard, and existing methods face inefficiencies both in practice and theory. In this paper, we propose two novel algorithms with distinct branching strategies and provable time guarantees for solving the maximum edge biclique search problem. The first is a refined pivot-based branching algorithm that systematically exploits vertex adjacency relationships to bound the search for the maximum edge biclique, achieving a time complexity of O ( m 1.348 n ). The second is a cover-based algorithm that uncovers a novel duality between maximal bicliques and minimal vertex covers in bipartite graphs, attaining a complexity of O ( m 1.381 n ). To the best of our knowledge, these two algorithms achieve the best-known worst-case time complexities for this problem. Notably, while the cover-based algorithm has a marginally higher theoretical complexity, it typically provides superior practical performance on dense graphs due to its inherent pruning efficiency. To further enhance performance, we introduce advanced pruning techniques, including polynomial-time solvable graph cases, neighbor and non-neighbor constraint-based upper bounds, vertex cover constraint-driven upper bounds, heuristic prioritization, and an improved progressive bounding approach. Additionally, we propose a hybrid framework that deploys the pivot-based approach for sparse graph regions and the cover-based approach for dense regions, balancing efficiency across varying graph structures. Extensive experiments on 12 real-world bipartite graphs demonstrate that our hybrid framework outperforms the state-of-the-art baseline by up to four orders of magnitude and achieves speedups of several times to orders of magnitude over the pivot-based approach on dense graphs.

Given an edge-weighted graph and a set of potentially overlapping vertex groups, a group Steiner tree (GST) is a minimum weight tree that includes at least one vertex in each group. Finding GSTs serves as a classical approach to keyword search in relational databases. Existing studies use CPUs to find optimal GSTs in a serial way, and remain slow in some cases. No prior work has applied GPUs to meet this challenge. To fill this gap, first, we propose a parallel-friendly GST solution framework, by breaking the traditional bottom-up dynamic programming order. Second, since a direct execution of this framework on GPUs faces a severe workload imbalance problem, we develop a GST-customized load balancing approach. Specifically, we employ kernel fusion and global memory coalescing techniques to efficiently utilize different parallel granularities to match divergent tree construction workloads. Third, since existing pruning methods cannot be directly applied to a parallel scheme, we modify feasible pruning procedures to reduce the computation burden, and rigorously prove the solution correctness. Furthermore, inspired by recent applications, we present a novel dynamic programming algorithm for finding optimal diameter-bounded GSTs on GPUs. Experiments on various real datasets show that the proposed techniques achieve a speedup of 48-2390× over state-of-the-art methods, and can handle some large weighted graphs where existing solutions are too slow to be applied, and thus could greatly improve the user experience in related applications.

In this paper, we study a problem of index maintenance on evolving graphs for effective resistance computation. Unlike an existing matrices-based index, we show that the index can be efficiently maintained by directly preserving samples of random walks and loop-erased walks. This approach not only enables efficient storage and rapid query response but also supports effective maintenance. We propose a novel approach to convert edge updates into landmark node updates. Building upon this, we present two new update algorithms for random walk and loop-erased walk samples respectively. Both algorithms update samples without requiring complete resampling, ensuring accuracy and high efficiency. A particularly challenging and innovative technique involves updating loop-erased walks. Here we develop a novel and powerful cycle decomposition technique for loop-erased walks, enabling us to update samples at the cycle level rather than the node level, significantly enhancing efficiency. Furthermore, we show that both of our methods achieve an Õ (1) time complexity per edge update in real-world graphs under a mild assumption. We conduct extensive experiments using 10 large real-world datasets to evaluate the performance of our approaches. The results show that our best algorithm can be up to two orders of magnitude faster than the baseline methods.

Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance r(s,t) depends only on labels along the paths from s and t to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose TreeIndex, a novel index method that constructs a resistance distance labelling of size O(n • h G ) in O(n • h G 2 • d max ) time, where h G (tree height) and d max (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in O(h G ) time and single-source queries in O(n • h G ) time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a 405 GB labelling in 7 hours (single-threaded) and answers exact single-pair queries in 10 -3 seconds and single-source queries in 190 seconds-the first exact method scalable to such large graphs.

Minimum Spanning Tree (MST) is a fundamental structure in graph analytics and can be applied in various applications. The problem of maintaining MSTs in dynamic graphs is significant, as many real-world graphs are frequently updated. Existing studies on MST maintenance primarily focus on theoretical analysis and lack practical efficiency. In this paper, we propose a novel algorithm to maintain MST in dynamic graphs, which achieves high practical efficiency. In addition to the tree structure, our main idea is to maintain a replacement edge for each tree edge. In this way, the tree structure can be immediately updated when a tree edge is deleted. We propose algorithms to maintain the replacement edge for each tree edge by sharing the computation cost in the updating process. Our performance studies on large datasets demonstrate considerable improvements over state-of-the-art solutions.

The densest subgraph (DS) search over a directed graph focuses on finding the subgraph with the highest density among all subgraphs. This problem has raised numerous applications, such as fraud detection and community detection. The state-of-the-art DS algorithms have prohibitively high costs or poor approximation ratios, making them unsuitable for practical applications. To address these dilemmas, in this paper, we propose a novel model called integral densest subgraph (IDS). We show that IDS can serve as a near-DS model that has a tight floor relationship with the density of the DS. To compute IDS, we first propose a novel flow network named (α,β)-dense network, based on which we design an exact network-flow algorithm GetIDS with O(p • log |V| • |E| 1.5 ) time complexity, where p is typically a small constant in real-world graphs. Additionally, we propose several non-trivial pruning techniques to further improve the efficiency. Subsequently, we propose a novel (2 + ε)-approximation algorithm MultiCore with near-linear time complexity, providing a good approximation guarantee with high efficiency. Finally, our extensive experiments on 10 real-world graphs demonstrate the effectiveness of the proposed IDS model, and the high efficiency and scalability of the proposed solutions.

Mining dense subgraphs in a bipartite graph is a fundamental task in bipartite graph analysis, with numerous applications in community detection, fraud detection, and e-commerce recommendation. Existing dense subgraph models, such as biclique, k -biplex, k -bitruss, and (α,β)-core, often face challenges due to their high computational complexity or limitations in effectively capturing the density of the graph. To overcome these issues, in this paper, we propose a new dense subgraph model for bipartite graphs, namely (α,β)-dense subgraph, designed to capture the density structure inherent in bipartite graphs. We show that all (α,β)-dense subgraphs are nested within each other, forming a hierarchical density decomposition of the bipartite graph. To efficiently compute the (α,β)-dense subgraph, we develop a novel network flow algorithm with a carefully-designed core pruning technique. The time complexity of our algorithm is O(|E|+|E(R)| 1.5 ), where |E| denotes the number of edges and |E(R)| is the number of edges of the pruned graph, often significantly smaller than |E|. Armed with this algorithm, we also propose a novel and efficient divide-and-conquer algorithm to compute the entire density decomposition of the bipartite graph within O(p ⋅ log d max ⋅ |E| 1.5 ) time, where p is typically a small constant in real-world bipartite graphs and d max is the maximum degree. Extensive experiments and case studies on 11 real-world datasets demonstrate the effectiveness of our (α,β)-dense subgraph model and the high efficiency and scalability of our proposed algorithms.

Federated graph learning (FGL) is a promising distributed training paradigm for graph neural networks across multiple local systems without direct data sharing. This approach inherently involves large-scale distributed graph processing, which closely aligns with the challenges and research focuses of graph-based data systems. Despite the proliferation of FGL, the diverse motivations from real-world applications, spanning various research backgrounds and settings, pose a significant challenge to fair evaluation. To fill this gap, we propose OpenFGL, a unified benchmark designed for the primary FGL scenarios: Graph-FL and Subgraph-FL. Specifically, OpenFGL includes 42 graph datasets from 18 application domains, 8 federated data simulation strategies that emphasize different graph properties, and 5 graph-based downstream tasks. Additionally, it offers 18 recently proposed SOTA FGL algorithms through a user-friendly API, enabling a thorough comparison and comprehensive evaluation of their effectiveness, robustness, and efficiency. Our empirical results demonstrate the capabilities of FGL while also highlighting its potential limitations, providing valuable insights for future research in this growing field, particularly in fostering greater interdisciplinary collaboration between FGL and data systems.

Truss decomposition is a fundamental approach in graph theory that focuses on uncovering cohesive subgraphs within networks. However, many networks involve groupwise rather than pairwise relationships and are often represented as hypergraphs. Modeling and capturing k-truss in hypergraphs is essential for uncovering tight-knit relationships in such multi-relational networks. In this paper, we tackle the problem of truss decomposition in hypergraph. A hyper k-truss is a subgraph in which each node is part of at least k hyper-triangles. We first introduce a framework for hyper-truss decomposition and determine that the most time-consuming component is counting hyper-triangles. To count all hyper-triangles efficiently, we propose an edge-iterator algorithm. To further reduce redundant computations, we present an improved algorithm that combines edge-iterator and node-iterator techniques to prune non-promising nodes. Next, to handle common nodes in hypergraphs, we develop a novel prefix forest technique to encode all hyperedges and count triangles within this prefix forest. We also propose several optimization strategies that reorder nodes and hyperedges to improve work balancing. Finally, we conduct extensive experiments on real-world hypergraph datasets, demonstrating the efficiency and effectiveness of our algorithms.

Higher-order graph clustering partitions graphs use frequently occurring subgraphs instead of edges, proving effective in community detection and knowledge discovery. Motif conductance, known for its strong interpretability, is a leading model. However, existing motif conductance algorithms are hindered by a two-stage reweighting framework that requires enumerating motif instances to generate an edge-weighted graph for partitioning. This framework has two major drawbacks: (1) It provides only a quadratic bound for three-vertex motifs, with no provable approximation guarantees for other motifs. (2) Enumerating motif instances is computationally prohibitive for large motifs or dense graphs due to combinatorial explosions. Besides, costly spectral clustering or local graph diffusion on the edge-weighted graph limits their scalability. In this paper, we propose a novel peeling-based clustering framework, PSMC, offering a motifindependent approximation ratio for any motif. Specifically, PSMC first defines a new locally computable vertex metric Motif Resident based on the given motif. Then, it iteratively deletes vertices with the smallest motif resident using efficient dynamic update techniques, outputting a locally optimal result with approximation guarantees. Besides, we introduce several powerful optimization techniques to further reduce computational costs. Empirical results on real-world and synthetic datasets showcase our proposed solutions' superiority over ten competitors.

A colorful star motif is a star-shaped graph where any two nodes have different colors. Counting the colorful star motif can help to analyze the structural properties of real-life colorful graphs, model higher-order clustering, and accelerate the mining of the densest subgraph exhibiting$h$-clique characteristics in graphs. In this manuscript, we introduce the concept of colorful$h$-star in a colored graph and proposes two higher-order cohesive subgraph models, namely colorful$h$-star core and colorful$h$-star truss. We show that the colorful$h$-stars can be counted and updated very efficiently using a novel dynamic programming (DP) algorithm. Based on the proposed DP algorithm, we develop a colorful$h$-star core decomposition algorithm which takes$O(h m)$time,$O(h n+m)$space; and a colorful$h$-star truss decomposition algorithm which takes$O(h m^{1.5})$time,$O(hm)$space, where$m$and$n$denote the number of edges and nodes of the graph respectively. Moreover, we also propose a graph reduction technique based on our colorful$h$-star core model to accelerate the computation of the approximation algorithm for$ h$-clique densest subgraph mining. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

Graph embedding has become a powerful tool for learning latent representations of nodes in a graph. Despite its superior performance in various graph-based machine learning tasks, serious privacy concerns arise when the graph data contains personal or sensitive information. To address this issue, we investigate and develop graph embedding algorithms that satisfy local differential privacy (LDP). We introduce a novel privacy-preserving graph embedding framework, named PrivGE, to protect node data privacy. Specifically, we propose an LDP mechanism to obfuscate node data and utilize personalized PageRank as the proximity measure to learn node representations. Furthermore, we provide a theoretical analysis of the privacy guarantees and utility offered by the PrivGE framework. Extensive experiments on several real-world graph datasets demonstrate that PrivGE achieves an optimal balance between privacy and utility, and significantly outperforms existing methods in node classification and link prediction tasks.

Bipartite graphs are commonly used to model relationships between two distinct types of entities, such as customer-product relationships in e-commerce platforms and protein-protein interactions in bioinformatics. Enumerating all maximal bicliques from a bipartite graph is a fundamental graph mining problem that has been widely used in many real-world applications including community search and spam detection. Existing algorithms for maximal biclique enumeration can struggle to scale to large graphs with a vast number of maximal bicliques. In this paper, we propose a novel and highly-efficient algorithm for maximal biclique enumeration in bipartite graphs using prefix trees. Specifically, a prefix tree is a data structure that stores lists of elements as paths in the tree, and we observe that a maximal biclique can be represented uniquely by the vertices in one of its vertex layers and stored compactly in prefix trees. The process of our algorithm is divided into two steps. First, we find the lower layer vertices of all maximal bicliques and organize them in a prefix tree (i.e., the result tree). During this step, we transform the original time-consuming operations of checking maximality and filtering candidates for vertex sets into determining uniqueness and performing extraction from a prefix tree at each level of the recursion. Second, we use the result tree to obtain the upper layer vertices of the maximal bicliques by computing the common neighbors of vertices in the tree. In this step, we further optimize the computation for intersections of vertex sets by compressing the neighbors of each vertex and memoization. In addition, we also propose a pre-processing method based on the order of traversal on the prefix tree to reduce memory usage. We conduct extensive experiments on 10 real-world datasets, and the results demonstrate that the proposed algorithm outperforms existing solutions by up to one order of magnitude.

Cohesive sub graph mining has received much at-tention in the area of graph analysis. A k- truss, defined as a sub graph where each edge is associated with at least$k-2$triangles, serves as a fundamental graph analysis tool. Among all k-trusses, the$k_{\max}$-truss with the maximum$k$value holds significant importance in various practical applications such as community search and keyword retrieval. Furthermore, it is also closely related to many graph analysis problems, particularly those computational complexity problems parameterized by$k$. However, real-world graphs often exhibit large-scale characteris-tics, making it impractical to fully load them into main memory. In this paper, we investigate the problem of finding the$k_{\max}$-truss in external memory settings. To address this problem, we propose an 110 efficient algorithm following a semi-external model, which only allows node information to be loaded into main memory. Our approach leverages greedy strategies and a binary search framework to efficiently find the$k_{\max}$- truss. Subsequently, an elegant data structure is proposed to significantly reduce 110 costs. Furthermore, to address dynamic graph updates, we develop an 110 efficient$k_{\max}$- truss maintenance algorithm based on the local-first update technique. To evaluate the performance of our algorithms, we conduct extensive experiments. The results demonstrate the high efficiency and scalability of our algorithms, which are at least two orders of magnitude faster in runtime and at least one order of magnitude lower in terms of 110 costs compared to the state-of-the-art solutions.

Recently, Federated Graph Learning (FGL) has attracted significant attention as a distributed framework based on graph neural networks, primarily due to its capability to break data silos. Existing FGL studies employ community split on the homophilous global graph by default to simulate federated semisupervised node classification settings. Such a strategy assumes the consistency of topology between the multi-client subgraphs and the global graph, where connected nodes are highly likely to possess similar feature distributions and the same label. However, in real-world implementations, the varying perspectives of local data engineering result in various subgraph topologies, posing unique heterogeneity challenges in FGL. Unlike the well-known label Non-independent identical distribution (Non-iid) problems in federated learning, FGL heterogeneity essentially reveals the topological divergence among multiple clients, namely homophily or heterophily. To simulate and handle this unique challenge, we introduce the concept of structure Non-iid split and then present a new paradigm called Adaptive Federated Graph Learning (AdaFGL), a decoupled two-step personalized approach. To begin with, AdaFGL employs standard multi-client federated collaborative training to acquire the federated knowledge extractor by aggregating uploaded models in the final round at the server. Then, each client conducts personalized training based on the local subgraph and the federated knowledge extractor. Extensive experiments on the 12 graph benchmark datasets validate the superior performance of AdaFGL over state-of-the-art baselines. Specifically, in terms of test accuracy, our proposed AdaFGL outperforms baselines by significant margins of 3.24 % and 5.57 % on community split and structure Non-iid split, respectively.

Recently, graph neural networks (GNNs) have shown prominent performance in semi-supervised node classification by leveraging knowledge from the graph database. However, most existing GNNs follow the homophily assumption, where connected nodes are more likely to exhibit similar feature distributions and the same labels, and such an assumption has proven to be vulnerable in a growing number of practical applications. As a supplement, heterophily reflects dissimilarity in connected nodes, which has gained significant attention in graph learning. To this end, data engineers aim to develop a powerful GNN model that can ensure performance under both homophily and heterophily. Despite numerous attempts, most existing GNNs struggle to achieve optimal node representations due to the constraints of undirected graphs. The neglect of directed edges results in sub-optimal graph representations, thereby hindering the capacity of GNNs. To address this issue, we introduce AMUD, which quantifies the relationship between node profiles and topology from a statistical perspective, offering valuable insights for Adaptively Modeling the natural directed graphs as the Undirected or Directed graph to maximize the benefits from subsequent graph learning. Furthermore, we propose Adaptive Directed Pattern Aggregation (ADPA) as a new directed graph learning paradigm for AMUD. Empirical studies have demonstrated that AMUD guides efficient graph learning. Meanwhile, extensive experiments on 16 benchmark datasets substantiate the impressive performance of ADPA, outperforming baselines by significant margins of 3.96%.

Periodic group behaviors often exist in temporal interaction networks, such as monthly group meetings, quarterly animal migrations, and yearly birthday parties. In real life, these events are usually quasi-periodic, meaning that the time intervals between two adjacent events are nearly constant but not exactly constant. Most existing studies mainly focus on identifying exact periodic group behaviors, which may result in an incomplete detection of periodic patterns in temporal networks. To fill this gap, we focus on a quasi-periodic community mining problem, which aims to find the most representative cohesive sub graphs, including the quasi-periodic$k$-core and quasi-periodic k-clique. The number of quasi-periodic communities is much larger than that of periodic communities, since the number of quasi-periodic sub-sequences is larger than that of periodic sub-sequences in a given time sequence. To efficiently compute the quasi-periodic communities, we propose a novel two-stage framework. In the first stage, the framework checks whether the time sequence of each vertex contains quasi-periodic sub-sequences. To this end, we develop a new structure, the DAG oracle, which comprises a set of concise DAGs that enables rapid extraction of all quasi-periodic sub-sequences. Based on the DAG oracle, we can easily compute all quasi-periodic sub-sequences for every vertex. In the second stage, the framework computes local quasi-periodic subgraphs that contain the vertex, which allows for the application of existing community mining algorithms. Given the large number of these subgraphs, we propose several carefully -designed pruning rules to further reduce redundant computations. Extensive experiments on 5 real-life datasets demonstrate the efficiency and effectiveness of our proposed solutions.

Higher-order graph clustering aims to partition the graph using frequently occurring subgraphs (i.e., motifs), instead of the lower-order edges, as the atomic clustering unit, which has been recognized as the state-of-the-art solution in ground truth community detection and knowledge discovery. Motif conductance is one of the most promising higher-order graph clustering models due to its strong interpretability. However, existing motif conductance based graph clustering algorithms are mainly limited by a seminal two-stage reweighting computing framework, needing to enumerate all motif instances to obtain an edge-weighted graph for partitioning. However, such a framework has two-fold vital defects: (1) It can only provide a quadratic bound for the motif with three vertices, and whether there is provable clustering quality for other motifs is still an open question. (2) The enumeration procedure of motif instances incurs prohibitively high costs against large motifs or large dense graphs due to combinatorial explosions. Besides, expensive spectral clustering or local graph diffusion on the edge-weighted graph also makes existing methods unable to handle massive graphs with millions of nodes. To overcome these dilemmas, we propose a Provable and Scalable Motif Conductance algorithm PSMC, which has a fixed and motif-independent approximation ratio for any motif. Specifically, PSMC first defines a new vertex metric Motif Resident based on the given motif, which can be computed locally. Then, it iteratively deletes the vertex with the smallest motif resident value very efficiently using novel dynamic update technologies. Finally, it outputs the locally optimal result during the above iterative process. To further boost efficiency, we propose several effective bounds to estimate the motif resident value of each vertex, which can greatly reduce computational costs. Empirical results on real-life and synthetic demonstrate that our proposed algorithms achieve 3.2-32 times speedup and improve the quality by at least 12 times than the state-of-the art baselines.

The quest to identify local dense communities closely connected to predetermined seed nodes is vital across numerous applications. Given the seed nodes R, the R-subgraph density of a subgraph S is defined as traditional graph density of S with penalties on the nodes in S / R. The state-of-the-art (SOTA) anchored densest subgraph model, which is based on R-subgraph density, is designed to address the community search problem. However, it often struggles to efficiently uncover truly dense communities. To eliminate this issue, we propose a novel NR-subgraph density metric, a nuanced measure that identifies communities intimately linked to seed nodes and also exhibiting overall high graph density. We redefine the anchored densest subgraph search problem through the lens of NR-subgraph density and cast it as a Linear Programming (LP) problem. This allows us to transition into a dual problem, tapping into the efficiency and effectiveness of convex programming-based iterative algorithm. To solve this redefined problem, we propose two algorithms: FDP, an iterative method that swiftly attains near-optimal solutions, and FDPE, an exact approach that ensures full convergence. We perform extensive experiments on 12 real-world networks. The results show that our proposed algorithms not only outperform the SOTA methods by 3.6~14.1 times in terms of running time, but also produce subgraphs with superior internal quality.

Scalable graph neural networks (GNNs) have emerged as a promising technique, which exhibits superior predictive performance and high running efficiency across numerous large-scale graph-based web applications. However, (i) Most scalable GNNs tend to treat all nodes with the same propagation rules, neglecting their topological uniqueness; (ii) Existing node-wise propagation optimization strategies are insufficient on web-scale graphs with intricate topology, where a full portrayal of nodes' local properties is required. Intuitively, different nodes in web-scale graphs possess distinct topological roles, and therefore propagating them indiscriminately or neglecting local contexts may compromise the quality of node representations. To address the above issues, we propose Adaptive Topology-aware Propagation (ATP), which reduces potential high-bias propagation and extracts structural patterns of each node in a scalable manner to improve running efficiency and predictive performance. Remarkably, ATP is crafted to be a plug-and-play node-wise propagation optimization strategy, allowing for offline execution independent of the graph learning process in a new perspective. Therefore, this approach can be seamlessly integrated into most scalable GNNs while remaining orthogonal to existing node-wise propagation optimization strategies. Extensive experiments on 12 datasets have demonstrated the effectiveness of ATP.

A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2 n ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα k n ), where α k < 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ k n ), where β k is strictly less than α k . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.

The study of k -defective cliques, defined as induced subgraphs that differ from cliques by at most k missing edges, has attracted much attention in graph analysis due to their relevance in various applications, including social network analysis and implicit interaction predictions. However, determining the maximum k -defective clique in graphs has been proven to be an NP-hard problem, presenting significant challenges in finding an efficient solution. To address this problem, we develop a theoretically and practically efficient algorithm that leverages newly-designed branch reduction rules and a pivot-based branching technique. Our analysis establishes that the time complexity of the proposed algorithm is bounded by O(mγ k n ), where γ k is a real value strictly less than 2 (e.g., when k= 1, 2, and 3, γ k = 1.466, 1.755, and 1.889, respectively). To our knowledge, this algorithm achieves the best worst-case time complexity to date compared to state-of-the-art solutions. Moreover, to further reduce unnecessary branches, we propose a time-efficient upper bound-based pruning technique, which is obtained by manipulating information such as the number of distinct colors assigned to vertices and the presence of non-neighbors among them. Additionally, we employ an ordering-based heuristic approach as a preprocessing step to improve computational efficiency. Finally, we conduct extensive experiments on a diverse set of over 300 graphs to evaluate the efficiency of the proposed solutions. The results demonstrate that our algorithm achieves a speedup of 3 orders of magnitude over state-of-the-art solutions in processing most of real-world graphs.

Local community search (LCS) finds a community in a given graph G local to a set R of seed nodes by optimizing an objective function. The objective function f(S) for an induced subgraph S encodes the set inclusion criteria of R to a classic community measurement of S such as the conductance and the density. An ideal algorithm for optimizing f(S) is strongly local, that is, the complexity is dependent on R as opposed to G. This paper formulates a general form of objective functions for LCS using configurations and then focuses on a set C of density-based configurations, each corresponding to a density-based LCS objective function. The paper has two main results. i) A constructive classification of C: a configuration in C has a strongly local algorithm for optimizing its corresponding objective function if and only if it is in C L ⊆ C. ii) A linear programming-based general solution for density-based LCS that is strongly local and practically efficient. This solution is different from the existing strongly local LCS algorithms, which are all based on flow networks.

Effective resistance (ER) is a fundamental metric for measuring node similarities in a graph, and it finds applications in various domains including graph clustering, recommendation systems, link prediction, and graph neural networks. The state-of-the-art algorithm for computing effective resistance relies on a landmark technique, which involves selecting a node that is easy to reach by all the other nodes as a landmark. The performance of this technique heavily depends on the chosen landmark node. However, in many real-life graphs, it is not always possible to find an easily reachable landmark node, which can significantly hinder the algorithm's efficiency. To overcome this problem, we propose a novel multiple landmarks technique which involves selecting a set of landmark nodes V l such that the other nodes in the graph can easily reach any one of a landmark node in V l . Specifically, we first propose several new formulas to compute ER with multiple landmarks, utilizing the concept of Schur complement. These new formulas allow us to pre-compute and maintain several small-sized matrices related to V l as a compact index. With this powerful index technique, we demonstrate that both single-pair and single-source ER queries can be efficiently answered using a newly-developed V l -absorbed random walk sampling or V l -absorbed push technique. Comprehensive theoretical analysis shows that all proposed index-based algorithms achieve provable performance guarantees for both single-pair and single-source ER queries. Extensive experiments on 5 real-life datasets demonstrate the high efficiency of our multiple landmarks-based index techniques. For instance, our algorithms, with a 1.5 GB index size, can be up to 4 orders of magnitude faster than the state-of-the-art algorithms while achieving the same accuracy on a large road network.

Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve the efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. Our performance studies on real large datasets show considerable improvement of our algorithms.

Most existing graph neural networks (GNNs) are limited to undirected graphs, whose restricted scope of the captured relational information hinders their expressive capabilities and deployment. Compared with undirected graphs, directed graphs (digraphs) fit the demand for modeling more complex topological systems by capturing more intricate relationships between nodes. While some directed GNNs have been introduced, their inspiration mainly comes from deep learning architectures, which lead to redundant complexity and computation, making them inapplicable to large-scale databases. To address these issues, we propose LightDiC, a scalable variant of the digraph convolution based on the magnetic Laplacian. Since topology-related computations are conducted solely during offline pre-processing, LightDiC achieves exceptional scalability, enabling downstream predictions to be trained separately without incurring recursive computational costs. Theoretical analysis shows that LightDiC achieves message passing based on the complex field, which corresponds to the proximal gradient descent process of the Dirichlet energy optimization function from the perspective of digraph signal denoising, ensuring its expressiveness. Experimental results demonstrate that LightDiC performs comparably well or even outperforms other SOTA methods in various downstream tasks, with fewer learnable parameters and higher efficiency.

Temporal community search is an important task in graph analysis, which has been widely used in many practical applications. However, existing methods suffer from two major defects: (i) they only require that the target result contains the query vertexq, leading to the temporal proximity betweenqand other vertices being ignored. Thus, they may find many temporal irrelevant vertices (these vertices are called query-drifted vertices) concerningqfor satisfying their objective functions; (ii) their methods are NP-hard, incurring high costs for exact solutions or compromised qualities for approximate/heuristic algorithms. In this paper, we propose a new problem named query-centered temporal community search to overcome these limitations. Specifically, we first present a novel concept of Time-Constrained Personalized PageRank to characterize the temporal proximity betweenqand other vertices. Then, we introduce a model calledβ-temporal proximity core, which can seamlessly combine temporal proximity and structural cohesiveness. Subsequently, our problem is formulated as an optimization task that finds aβ-temporal proximity core with the largestβ.We theoretically prove that our problem can circumvent these query-drifted vertices. To solve our problem, we first devise an exact and near-linear time greedy removing algorithm that iteratively removes unpromising vertices. To improve efficiency, we then design an approximate two-stage local search algorithm with bound-based pruning techniques. Finally, extensive experiments on eight real-life datasets and nine competitors show the superiority of the proposed solutions.

Graph coarsening techniques aim at simplifying the graph structure while preserving key properties in the resulting coarsened graph, have been widely used in graph partitioning and graph neural networks (GNNs). Existing graph coarsening techniques mainly focus on preserving cuts or graph spectrums. In this paper, we propose a new method that focuses on preserving graph topological features. In particular, we develop a novel graph coarsening approach, called Graph Elementary Collapse (GEC), by extending the concept of elementary collapse in algebraic topology to graph analysis. With this novel method, we can ensure a kind of equivalence relationship called homotopy equivalence of the graph during the coarsening process, thereby preserving numerous topological properties, including connectivity, rings, and voids. To enhance the scalability, we also propose several carefully-designed optimization techniques to reduce the time and memory consumption of our approach. Extensive experiments on several real-world datasets demonstrate the effectiveness and efficiency of our proposed method across various GNN prediction tasks.

The arboricity a ( G ) of a graph G is defined as the minimum number of edge-disjoint forests that the edge set of G can be partitioned into. It is a fundamental metric and has been widely used in many graph analysis applications. However, computing a ( G ) is typically a challenging task. To address this, an easier-to-compute alternative called pseudoarboricity was proposed. Pseudoarboricity has been shown to be closely connected to many important measures in graphs, including the arboricity and the densest subgraph density ρ ( G ). Computing the exact pseudoarboricity can be achieved by employing a parametric max-flow algorithm, but it becomes computationally expensive for large graphs. Existing 2-approximation algorithms, while more efficient, often lack satisfactory approximation accuracy. To overcome these limitations, we propose two new approximation algorithms with theoretical guarantees to approximate the pseudoarboricity. We show that our approximation algorithms can significantly reduce the number of times the max-flow algorithm is invoked, greatly improving its efficiency for exact pseudoarboricity computation. In addition, we also study the pseudoarboricity maintenance problem in dynamic graphs. We propose two novel and efficient algorithms for maintaining the pseudoarboricity when the graph is updated by edge insertions or deletions. Furthermore, we develop two incremental pseudoarboricity maintenance algorithms specifically designed for insertion-only scenarios. We conduct extensive experiments on 195 real-world graphs, and the results demonstrate the high efficiency and scalability of the proposed algorithms in computing pseudoarboricity for both static and dynamic graphs.

Locally-densest subgraph (LDS) decomposition is a fundamental decomposition in graph analysis that finds numerous applications in various domains, including community detection, fraud detection, graph querying, and graph visualization. However, the LDS decomposition is computationally challenging for both static and dynamic graphs. Furthermore, the LDS decomposition often produces an excessive number of dense subgraph layers, leading to the unnecessary partition of tightly-connected subgraphs. To address these limitations, an alternative concept called density decomposition was proposed, which can generate a more reasonable number of dense subgraph layers. However, the state-of-the-art algorithm for density decomposition requires O ( m 2 ) time ( m is the number of edges of the graph), which is very costly for large graphs. In this paper, we conduct an in-depth investigation of density decomposition and propose efficient algorithms for computing it on both static and dynamic graphs. First, we establish a novel relationship between density decomposition and LDS decomposition. Second, based on these relationships, we propose novel algorithms to compute the density decomposition on static graphs with carefully designed network flow and divide-and-conquer techniques. Our proposed static algorithms significantly reduce the time complexity to O ( m 3/2 log p ) ( p is often a very small constant in real-world graphs). Third, for dynamic graphs, we develop three dynamic algorithms with efficient O ( m ) time complexity. Extensive experiments on several large real-world graphs demonstrate the high efficiency, scalability, and effectiveness of the proposed algorithms.

Densest subgraph search, aiming to identify a subgraph with maximum edge density, faces limitations as the edge density inadequately reflects biases towards a given vertex set R. To address this, the R -subgraph density was introduced, refining the doubled edge density by penalizing vertices in a subgraph but not in R , using the degree as a penalty factor. This advancement leads to the Anchored Densest Subgraph (ADS) search problem, which finds the subgraph Š with the highest R -subgraph density for a given set R. Nonetheless, current algorithms for ADS search face significant inefficiencies in handling large-scale graphs or the sizable R set. Furthermore, these algorithms require re-computing the ADS whenever the graph is updated, complicating the efficient maintenance within dynamic graphs. To tackle these challenges, we propose the concept of integer R -subgraph density and study the problem of finding a subgraph S * ⊆ V with the highest integer R -subgraph density. We reveal that the R -subgraph density of S* provides an additive approximation to that of ADS with a difference of less than 1, and hence S * is termed the Approximate Anchored Densest Subgraph (AADS). For searching the AADS, we present an efficient global algorithm incorporating the re-orientation network flow technique and binary search, operating in a time polynomial to the graph's size. Additionally, we propose a novel local algorithm using shortest-path-based methods for the max-flow computation from s to t around R , markedly boosting performance in scenarios with larger R sets. For dynamic graphs, both basic and improved algorithms are developed to efficiently maintain the AADS when an edge is updated. Extensive experiments and a case study demonstrate the efficiency, scalability, and effectiveness of our solutions.

$K$-clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of$k$-cliques in a graph for a large$k$(e.g.,$k=8$) is often intractable as the number of$k$-cliques increases exponentially w.r.t. (with respect to)$k$. Existing exact$k$-clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of$k$-cliques which integrates both the exact$k$-clique counting technique and three novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the$k$-clique counts in thesparse regionsof a graph, and use the proposed color-based sampling approaches to estimate the number of$k$-cliques in thedense regionsof the graph. Specifically, we develop three novel dynamic programming based$k$-color set sampling techniques to efficiently estimate the$k$-clique counts, where a$k$-color set contains$k$nodes with$k$different colors. Since a$k$-color set is often a good approximation of a$k$-clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

Neighborhood inclusion, representing that all the neighbors of a vertex are also adjacent to another vertex, has been recognized as an important relationship between two vertices in a graph. We call a vertex u dominating v, denoted by v ≤ u, if $N(v) \subseteq N(u) \cup \{ u\} $ holds, where (v) denotes the set of neighbors of v. Based on such a domination relationship, we propose a concept called neighborhood skyline. The neighborhood skyline is a set of vertices in which any vertex u cannot be dominated by the other nodes in the graph G, i.e., $\nexists v \in G,u \leq v$. We study a new problem, called neighborhood skyline computation, and develop a filter-refine search framework, FilterRefineSky, to efficiently find the neighborhood skyline by searching the vertices in a small candidate set instead of in the entire graph. We show that our neighborhood skyline technique can be used to speed up the computation of two well-studied group centrality maximization problems and the maximum clique search problem in graphs. Extensive experimental studies conducted on five large real-life datasets demonstrate the effectiveness of neighborhood skyline, and the efficiency and scalability of our algorithms.

Link prediction is a significant technique to generate latent interactions for the applications of recommendation in large graphs. As the interactions to be predicted often occur among more than two objects, we pay attention to solving the novel problem of predicting the interactions in hypergraphs. Previous studies focus mainly on predicting binary relations; most of those techniques cannot be directly applied to predict multiple relations. In this work, we study the problem of edge prediction in hypergraphs, where we use a concept, Hypergraph Edit Distance (abbreviated as HGED), to measure the similarity of two nodes. Based on HGED, we can record a Hypergraph Edit Path while searching the optimal edit distance, thus this path enables to explain why one node is similar to another node since their neighborhood structure can be edited to be isomorphic following the edit path. We first propose a general framework which can compute the edit distance of neighborhood structure for two nodes in hypergraph. To improve the efficiency, we propose a BFS search-based method with several tightening lower bounds and upper bounds estimation. To predict the multiple relations, we introduce a cluster model in which nodes in each hyperedge are restricted by the hypergraph edit distance. We further present an on-demand algorithm for computing HGED, which substantially avoids redundant computations. Finally, we conduct extensive empirical studies on real hypergraph datasets, and the results demonstrate the effectiveness, efficiency and scalability of our algorithms.

Maximal biclique enumeration is a fundamental problem in bipartite graph data analysis. Existing biclique enumeration methods mainly focus on non-attributed bipartite graphs and also ignore the fairness of graph attributes. In this paper, we introduce the concept of fairness into the biclique model for the first time and study the problem of fairness-aware biclique enumeration. Specifically, we propose two fairness-aware biclique models, called single-side fair biclique and bi-side fair biclique respectively. To efficiently enumerate all single-side fair bicliques, we first present two non-trivial pruning techniques, called fair α-β core pruning and colorful fair α-β core pruning, to reduce the graph size without losing accuracy. Then, we develop a branch and bound algorithm, called FairBCEM, to enumerate all single-side fair bicliques on the reduced bipartite graph. To further improve the efficiency, we propose an efficient branch and bound algorithm with a carefully-designed combinatorial enumeration technique. Note that all of our techniques can also be extended to enumerate all bi-side fair bicliques. We also extend the two fairness-aware biclique models by constraining the ratio of the number of vertices of each attribute to the total number of vertices and present corresponding enumeration algorithms. Extensive experimental results on five large real-world datasets demonstrate our methods’ efficiency, effectiveness, and scalability.

Maximal clique enumeration is a fundamental operator in graph analysis. The model of clique, however, is typically too restrictive for real-world applications as it requires an edge for every pair of vertices. To remedy this restriction, practical graph analysis applications often resort to find relaxed cliques as alternatives. In this work, we investigate a notable relaxed clique model, called s-defective clique, which allows at most s edges to be missing. Similar to the complexity of maximal clique enumeration, the problem of enumerating all maximal s-defective cliques is also NP-hard. To solve this problem, we first develop a new polynomial-delay algorithm based on a carefully-designed reverse search technique, which can output two consecutive results within polynomial time. To achieve better practical efficiency, we propose a branch-and-bound algorithm with a novel pivoting technique. We prove that the time complexity of this algorithm depends only on O(α_sn) or O(αsδ) when using a degeneracy ordering optimization, where αs is a positive real number strictly less than 2, and δ (δ 0). We also develop several new pruning techniques to further improve the efficiency of our branch-and-bound algorithm to enumerate all relatively-large maximal s-defective cliques. In addition, we further generalize our pivot-based branch-and-bound algorithm to enumerate all maximal subgraphs satisfying a hereditary property. Here we call a graph meeting the hereditary property if all its subgraphs have the same property as itself. Finally, extensive experiments on 11 datasets demonstrate the efficiency, effectiveness, and scalability of the proposed solutions.

Finding cohesive subgraphs from a bipartite graph is a fundamental operator in bipartite graph analysis. In this paper, we focus on the problem of mining cohesive subgraphs from a bipartite graph that satisfy a hereditary property. Here a cohesive subgraph meets the hereditary property if all of its subgraphs satisfy the same property as itself. We show that several important cohesive subgraph models, such as maximal biclique and maximal k-biplex, satisfy the hereditary property. The problem of enumerating all maximal hereditary subgraphs was known to be NP-hard. To solve this problem, we first propose a novel and general pivot-based enumeration framework to efficiently enumerate all maximal hereditary subgraphs in a bipartite graph. Then, based on our general framework, we develop a new pivot-based algorithm with several pruning techniques to enumerate all maximal bicliques. We prove that the worst-case time complexity of our pivot-based maximal biclique enumeration algorithm is O(m x 2n/2 ) (or O(m\times 1.414^n)) which is near optimal since there exist up to O(2n/2 ) maximal bicliques in a bipartite graph with n vertices and m edges. Moreover, we also show that our algorithm can achieve polynomial-delay time complexity with a slight modification. Third, on the basis of our general framework, we also devise a novel pivot-based algorithm with several non-trivial pruning techniques to enumerate maximal k-biplexes in a bipartite graph. Finally, we conduct extensive experiments using 11 real-world bipartite graphs to evaluate the proposed algorithms. The results show that our pivot-based solutions can achieve one order of magnitude (three orders of magnitude) faster than the state-of-the-art maximal biclique enumeration algorithms (maximal k-biplex enumeration algorithms).

Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.

Personalized PageRank (PPR) computation is a fundamental problem in graph analysis. The state-of-the-art algorithms for PPR computation are based on a bidirectional framework which include a deterministic forward push and a Monte Carlo sampling procedure. The Monte Carlo sampling procedure, however, often has a relatively-large variance, thus reducing the performance of the PPR computation algorithms. To overcome this issue, we develop two novel variance-reduced Monte Carlo techniques for PPR computation. Our first technique is to apply power iterations to reduce the variance of the Monte Carlo sampling procedure. We prove that conducting few power iterations can significantly reduce the variance of existing Monte Carlo estimators, only with few additional costs. Moreover, we show that such a simple and novel variance-reduced Monte Carlo technique can achieve comparable estimation accuracy and the same time complexity as the state-of-the-art bidirectional algorithms. Our second technique is a novel progressive sampling method which uses the historical information of former samples to reduce the variance of the Monte Carlo estimator. We develop several novel PPR computation algorithms by integrating both of these variance reduction techniques with two existing Monte Carlo sampling approaches, including random walk sampling and spanning forests sampling. Finally, we conduct extensive experiments on 5 real-life large graphs to evaluate our solutions. The results show that our algorithms can achieve much higher PPR estimation accuracy by using much less time, compared to the state-of-the-art bidirectional algorithms.

A (p,q)-biclique is a complete subgraph (X,Y) that |X|=p, |Y|=q. Counting (p,q)-bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p,q)-bicliques for large p and q (e.g., p,q ≥ 10) is extremely difficult, because the number of (p,q)-bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p,q)-biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p,q)-bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p,q)-bicliques for all pairs of (p,q) using a combinatorial technique, instead of exhaustively enumerating all (p,q)-bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p,q)-bicliques for all pairs of (p,q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = min{p,q}). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.

The higher-order structure cohesive subgraph mining is an important operator in many graph analysis tasks. Recently, the colorful h -star core model has been proposed as an effective alternative to h -clique based cohesive subgraph models, in consideration of both efficiency and utilities in many practical applications. The existing peeling algorithms for colorful h -star core decomposition are to iteratively delete a node with the minimum colorful h -star degree. Hence, these methods are inherently sequential and suffer from two limitations: low parallelism and inefficiency for dynamic graphs. To enable high-performance colorful h -star core decomposition in large-scale graphs, we propose highly parallelizable local algorithms based on a novel concept of colorful h -star n -order H-index and conduct thorough analyses for its properties. Moreover, three optimizations have been developed to further improve the convergence performance. Based on our local algorithm and its optimized variants, we can efficiently maintain colorful h -star cores in dynamic graphs. Furthermore, we design lower and upper bounds for core numbers to facilitate identifying unaffected nodes in presence of graph updates. Extensive experiments conducted on 14 large real-world datasets with billions of edges demonstrate that our proposed algorithms achieve a 10 times faster convergence speed and a three orders of magnitude speedup when handling graph changes.

Federated Graph Learning (FGL) is a distributed machine learning paradigm that enables collaborative training on large-scale subgraphs across multiple local systems. Existing FGL studies fall into two categories: (i) FGL Optimization, which improves multi-client training in existing machine learning models; (ii) FGL Model, which enhances performance with complex local models and multi-client interactions. However, most FGL optimization strategies are designed specifically for the computer vision domain and ignore graph structure, presenting dissatisfied performance and slow convergence. Meanwhile, complex local model architectures in FGL Models studies lack scalability for handling large-scale subgraphs and have deployment limitations. To address these issues, we propose Federated Graph Topology-aware Aggregation (FedGTA), a personalized optimization strategy that optimizes through topology-aware local smoothing confidence and mixed neighbor features. During experiments, we deploy FedGTA in 12 multi-scale real-world datasets with the Louvain and Metis split. This allows us to evaluate the performance and robustness of FedGTA across a range of scenarios. Extensive experiments demonstrate that FedGTA achieves state-of-the-art performance while exhibiting high scalability and efficiency. The experiment includes ogbn-papers100M, the most representative large-scale graph database so that we can verify the applicability of our method to large-scale graph learning. To the best of our knowledge, our study is the first to bridge large-scale graph learning with FGL using this optimization strategy, contributing to the development of efficient and scalable FGL methods.

Core decomposition on uncertain graphs is a fundamental problem in graph analysis. Given an uncertain graph G, the core decomposition problem is to determine all (k, \eta)-cores in G, where a (k, \eta)-core is a maximal subgraph of G such that each node has an \eta-degree no less than k within the subgraph. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes nodes with the smallest \eta-degrees and also dynamically updates their neighbors' \eta-degrees. Unfortunately, we find that such a peeling algorithm with the dynamical \eta-degree updating technique is incorrect due to the inaccuracy of the recursive floating-point number division operations involved in the dynamical updating procedure. To solve this problem, we propose a bottom-up algorithm based on an on-demand computational strategy. To further improve the efficiency, we also develop a more-efficient top-down algorithm with several nontrivial optimization techniques. Both of our algorithms do not involve any floating-point number division operations, thus the correctness can be guaranteed. We conduct extensive experiments to evaluate our algorithms using five large real-life datasets. The results show that our algorithms are at least three orders of magnitude faster than the existing exact algorithms on large uncertain graphs.

Densest subgraphs are often interpreted ascommunities, based on a basic assumption that the connections inside a community are much denser than those between communities. In a graph with temporal information, a densest periodic subgraph is the most densely connected periodic behavior which needs to be captured. Unfortunately, the existing work do not model the densest periodic subgraph in temporal graphs, and the current algorithms for mining the densest subgraph cannot be applied to detect the densest periodic subgraph in the temporal networks. To tackle this problem, we propose a novel model, called the densest$\sigma$-periodic subgraph, which presents the densest periodic subgraph whose period size is$\sigma$. We prove that finding the densest$\sigma$-periodic subgraph can be solved in polynomial time, but it is still challenging because the naive algorithm needs to repeatedly invoke a maximum flow algorithm for many periodic subgraphs. To compute the densest$\sigma$-periodic subgraph efficiently, we first develop an effective pruning technique based on the degeneracy of the graph to significantly prune the number of the periodic subgraphs. Then, we present a more efficient algorithm that can reduce the computations for the degeneracy and maximum flow. Next, we develop a greedy algorithm that can compute the approximate densest$\sigma$-periodic subgraph and achieve an approximation ratio of 1/2. Finally, the results of extensive experiments on several real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Data warehouse and OLAP (Online Analytical Processing) are effective tools for decision support on traditional relational data and static multidimensional network data. However, many real-world multidimensional networks are often modeled as temporal multidimensional networks, where the edges in the network are associated with temporal information. Such temporal multidimensional networks typically cannot be handled by traditional data warehouse and OLAP techniques. To fill this gap, we propose a novel data warehouse model, named$\mathsf {Temporal{ }\; Graph{ }\; Cube}$, to support OLAP queries on temporal multidimensional networks. Through supporting OLAP queries in any time range, users can obtain summarized information of the network in the time range of interest, which cannot be derived by using traditional static graph OLAP techniques. We propose a segment-tree based indexing technique to speed up the OLAP queries, and also develop an index-updating technique to maintain the index when the temporal multidimensional network evolves over time. In addition, we also propose a novel concept called$\mathsf {similarity{ }\; of{ }\; snapshots}$which shows a strong correlation with the efficiency of indexing technique and can provide a good reference on the necessity of building the index. The results of extensive experiments on two large real-world datasets demonstrate the effectiveness and efficiency of the proposed method.

Cohesive subgraph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive subgraph mining algorithms on attributed graphs do not consider thefairnessof attributes in the subgraph. In this article, we, for the first time, introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose three novel fairness-aware maximal clique models on attributed graphs, called weak fair clique, strong fair clique and relative fair clique, respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called$\mathsf{WFCEnum}$equipped with a novel colorful$k$-core based pruning technique. We also propose an efficient enumeration algorithm called$\mathsf{SFCEnum}$to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumerations. To enumerate all relative fair cliques, we design an enhanced colorful$k$-core based pruning technique for 2D attributes, and develop two efficient search algorithms:$\mathsf{RFCRefineEnum}$and$\mathsf{RFCAlterEnum}$for arbitrary dimension attributes. The results of extensive experiments on four real-world graphs demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

In this paper, we study a new problem of seeking stable subgraph isomorphisms for a query graph in a temporal graph. To solve our problem, we first develop a pruning-based search algorithm using several new pruning tricks to prune the unpromising matching results during the search procedure. To further improve the efficiency, we propose a novel index structure called BCCIndex, based on an idea of bi-connected component decomposition of the query graph, which can efficiently support the stable subgraph isomorphism search. Equipped with the BCCIndex, we present an efficient query processing algorithm based on a carefully designed tree join technique. We conduct extensive experiments to evaluate our algorithms on four large real-life datasets, and the results demonstrate the efficiency and effectiveness of our algorithms.

Finding all maximal k-plexes on networks is a fundamental research problem in graph analysis due to many important applications, such as community detection, biological graph analysis, and so on. A k-plex is a subgraph in which every vertex is adjacent to all but at most k vertices within the subgraph. In this paper, we study the problem of enumerating all large maximal k-plexes of a graph and develop several new and efficient techniques to solve the problem. Specifically, we first propose several novel upper-bounding techniques to prune unnecessary computations during the enumeration procedure. We show that the proposed upper bounds can be computed in linear time. Then, we develop a new branch-and-bound algorithm with a carefully-designed pivot re-selection strategy to enumerate all k-plexes, which outputs all k-plexes in O(n2?k n) time theoretically, where n is the number of vertices of the graph and ? k is strictly smaller than 2. In addition, a parallel version of the proposed algorithm is further developed to scale up to process large real-world graphs. Finally, extensive experimental results show that the proposed sequential algorithm can achieve up to 2× to 100× speedup over the state-of-the-art sequential algorithms on most benchmark graphs. The results also demonstrate the high scalability of the proposed parallel algorithm. For example, on a large real-world graph with more than 200 million edges, our parallel algorithm can finish the computation within two minutes, while the state-of-the-art parallel algorithm cannot terminate within 24 hours.

Core decomposition on uncertain graphs is shown to be a key problem in graph analysis. However, existing algorithms for solving this problem are based on a peeling algorithm with the dynamically updating technique, which can lead to relatively large errors due to the inaccuracy of the recursive floating-point number division operations. In this paper, we first develop two novel algorithms, a bottom-up approach and a top-down approach, which do not involve any floating-point number division operations to guarantee correctness. Then, we develop a parallel version for each approach to deal with large graphs. Extensive experimental results evidence the efficiency, effectiveness, and scalability of our proposed algorithms.

The h-clique based higher-order cohesive subgraph mining is an important operator in graph analysis. The h-clique core and h-clique densest subgraph are two representative higher-order cohesive subgraph models which have been widely used in many practical applications. However, computing these two models on large graphs is often very costly due to the hardness of counting the h-cliques. In this paper, we propose a relaxed higher-order cohesive subgraph model, called colorful h-star core, based on counting the number of colorful h-stars. Unlike the h-cliques, we show that the colorful h-stars can be counted and updated very efficiently using a novel dynamic programming (DP) algorithm. Based on the proposed DP algorithm, we develop an efficient colorful h-star core decomposition algorithm which takes O(h × m) time and uses O(h × n+m) space, where$m$and$n$denote the number of edges and nodes of the graph respectively. In addition, we also propose a graph reduction technique based on our colorful h-star core model to accelerate the computation of the state-of-the-art approximation algorithm for h-clique densest subgraph mining. Moreover, we show that the colorful h-star core can also provide a very good approximation of the h-clique densest subgraph. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

Cohesive sub graph mining on attributed graphs is a fundamental problem in graph data analysis. Existing cohesive sub graph mining algorithms on attributed graphs do not consider the fairness of attributes in the subgraph. In this paper, we for the first time introduce fairness into the widely-used clique model to mine fairness-aware cohesive subgraphs. In particular, we propose two novel fairness-aware maximal clique models on attributed graphs, called weak fair clique and strong fair clique respectively. To enumerate all weak fair cliques, we develop an efficient backtracking algorithm called WFCEnum equipped with a novel colorful k-core based pruning technique. We also propose an efficient enumeration algorithm called SFCEnum to find all strong fair cliques based on a new attribute-alternatively-selection search technique. To further improve the efficiency, we also present several non-trivial ordering techniques for both weak and strong fair clique enumeration. The results of extensive experiments on four real-world graphs demonstrate the efficiency and effectiveness of the proposed algorithms.

Betweenness centrality, measured by the number of times a vertex occurs on all shortest paths of a graph, has been recognized as a key indicator for the importance of a vertex in the network. However, the betweenness of a vertex is often very hard to compute because it needs to explore all the shortest paths between the other vertices. Recently, a relaxed concept called ego-betweenness was introduced which focuses on computing the betweenness of a vertex in its ego network. In this work, we study a problem of finding the top-k vertices with the highest ego-betweennesses. We first develop two novel search algorithms equipped with a basic upper bound and a dynamic upper bound to efficiently solve this problem. Then, we propose local-update and lazy-update solutions to maintain the ego-betweennesses for all vertices and the top-k results when the graph is updated by an edge insertion and deletion, respectively. In addition, we also present two efficient parallel algorithms to further improve the efficiency. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Maximal clique enumeration on uncertain graphs is a fundamental problem in uncertain graph analysis. In this paper, we study a problem of enumerating all maximal (k,n)-cliques on an uncertain graph G, where a vertex set H of G is a maximal (k,n)-clique if (1) H (|H| ≥ k) is a clique with probability no less than n, and (2) H is a maximal vertex set satisfying (1). The state-of-the-art algorithms for enumerating all maximal (k,n)-cliques are based on a set enumeration technique which are often very costly. This is because the set enumeration based techniques may explore all subsets of a maximal (k,n)-clique, thus resulting in many unnecessary computations. To overcome this issue, we propose several novel and efficient pivot-based algorithms to enumerate all maximal (k,n)-cliques based on a newly-developed pivot-based pruning principle. Our pivot-based pruning principle is very general which can be applied to speed up the enumeration of any maximal subgraph that satisfies a hereditary property. Here the hereditary property means that if a maximal subgraph H satisfies a property P, any subgraph of H also meets P. To the best of our knowledge, our work is the first to systematically explore the idea of pivot for maximal clique enumeration on uncertain graphs. In addition, we also develop a nontrivial size-constraint based pruning technique and a new graph reduction technique to further improve the efficiency. Extensive experiments on nine real-world graphs demonstrate the efficiency, effectiveness, and scalability of the proposed algorithms.

Computing the personalized PageRank vector is a fundamental problem in graph analysis. In this paper, we propose several novel algorithms to efficiently compute the personalized PageRank vector with a decay factor α based on an interesting connection between the personalized PageRank values and the weights of random spanning forests of the graph. Such a connection is derived based on a newly-developed matrix forest theorem on graphs. Based on this, we present an efficient spanning forest sampling algorithm via simulating loop-erased α-random walks to estimate the personalized PageRank vector. Compared to all existing methods, a striking feature of our approach is that its performance is insensitive w.r.t. (with respect to) the parameter α. As a consequence, our algorithm is often much faster than the state-of-the-art algorithms when α is small, which is the demanding case for many graph analysis tasks. We show that our technique can significantly improve the efficiency of the state-of-the-art algorithms for answering two well-studied personalized PageRank queries, including single source query and single target query. Extensive experiments on seven large real-world graphs demonstrate the efficiency of the proposed method.

K-clique counting is a fundamental problem in network analysis which has attracted much attention in recent years. Computing the count of k-cliques in a graph for a large k (e.g., k = 8) is often intractable as the number of k-cliques increases exponentially w.r.t. (with respect to) k. Existing exact k-clique counting algorithms are often hard to handle large dense graphs, while sampling-based solutions either require a huge number of samples or consume very high storage space to achieve a satisfactory accuracy. To overcome these limitations, we propose a new framework to estimate the number of k-cliques which integrates both the exact k-clique counting technique and two novel color-based sampling techniques. The key insight of our framework is that we only apply the exact algorithm to compute the k-clique counts in the sparse regions of a graph, and use the proposed sampling-based techniques to estimate the number of k-cliques in the dense regions of the graph. Specifically, we develop two novel dynamic programming based k-color set sampling techniques to efficiently estimate the k-clique counts, where a k-color set contains k nodes with k different colors. Since a k-color set is often a good approximation of a k-clique in the dense regions of a graph, our sampling-based solutions are extremely efficient and accurate. Moreover, the proposed sampling techniques are space efficient which use near-linear space w.r.t. graph size. We conduct extensive experiments to evaluate our algorithms using 8 real-life graphs. The results show that our best algorithm is at least one order of magnitude faster than the state-of-the-art sampling-based solutions (with the same relative error 0.1%) and can be up to three orders of magnitude faster than the state-of-the-art exact algorithm on large graphs.

Temporal graphs are ubiquitous. Mining communities that are bursting in a period of time is essential for seeking real emergency events in temporal graphs. Unfortunately, most previous studies on community mining in temporal networks ignore the bursting patterns of communities. In this paper, we study the problem of seeking bursting communities in a temporal graph. We propose a novel model, called the ( l , δ)-maximal bursting core, to represent a bursting community in a temporal graph. Specifically, an ( l , δ)-maximal bursting core is a temporal subgraph in which each node has an average degree no less than δ in a time segment with length no less than l. To compute the ( l , δ)-maximal bursting core, we first develop a novel dynamic programming algorithm that can reduce time complexity of calculating the segment density from O (| T |) 2 to O (| T |). Then, we propose an efficient updating algorithm which can update the segment density in O ( l ) time. In addition, we develop an efficient algorithm to enumerate all ( l , δ)-maximal bursting cores that are not dominated by the others in terms of l and δ. The results of extensive experiments on 9 real-life datasets demonstrate the effectiveness, efficiency and scalability of our algorithms.

The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 real-world networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.

Consider an edge-weighted graph, and a number of properties of interests (PoIs). Each vertex has a probability of exhibiting each PoI. The joint probability that a set of vertices exhibits a PoI is the probability that this set contains at least one vertex that exhibits this PoI. The probabilistic group Steiner tree problem is to find a tree such that (i) for each PoI, the joint probability that the set of vertices in this tree exhibits this PoI is no smaller than a threshold value, e.g. , 0.97; and (ii) the total weight of edges in this tree is the minimum. Solving this problem is useful for mining various graphs with uncertain vertex properties, but is NP-hard. The existing work focuses on certain cases, and cannot perform this task. To meet this challenge, we propose 3 approximation algorithms for solving the above problem. Let |Γ| be the number of PoIs, and ξ be an upper bound of the number of vertices for satisfying the threshold value of exhibiting each PoI. Algorithms 1 and 2 have tight approximation guarantees proportional to |Γ| and ξ, and exponential time complexities with respect to ξ and |Γ|, respectively. In comparison, Algorithm 3 has a looser approximation guarantee proportional to, and a polynomial time complexity with respect to, both |Γ| and ξ. Experiments on real and large datasets show that the proposed algorithms considerably outperform the state-of-the-art related work for finding probabilistic group Steiner trees in various cases.

Influence maximization has recently received significant attention for scheduling online campaigns or advertisements on social network platforms. However, most studies only focus on user influence via cyber interactions while ignoring their physical interactions which are also essential to gauge influence propagation. Additionally, targeted campaigns or advertisements have not received sufficient attention. To address these issues, we first devise a novel holistic influence diffusion model that takes into account both cyber and physical user interactions in an effective and practical way. Based on the new diffusion model, we formulate a new problem ofholistic influence maximization, denoted asHIMquery, for targeted advertisements in a spatial social network. TheHIMquery problem aims to find a minimum set of users whose holistic influence can cover all target users in the network, which belongs to a set covering problem. Since theHIMquery problem is NP-hard, we develop a greedy baseline algorithm and then improve on this algorithm to reduce the computational cost. To deal with large networks, we also design a spatial-social index to maintain the social, spatial and textual information of users, as well as developing an index-based efficient solution. Finally, we conduct extensive experiments using one synthetic and three real-world datasets to validate the efficiency and effectiveness of the proposed holistic influence diffusion model and our developed algorithms.

Degeneracy is an important concept to measure the sparsity of a graph which has been widely used in many network analysis applications. Many network analysis algorithms, such as clique enumeration and truss decomposition, perform very well in graphs having small degeneracies. In this paper, we propose an I/O-efficient algorithm to compute the degeneracy of the massive graph that cannot be fully kept in the main memory. The proposed algorithm only uses$O(n)$memory, where$n$denotes the number of nodes of the graph. We also develop an I/O-efficient algorithm to incrementally maintain the degeneracy on dynamic graphs. Extensive experiments show that our algorithms significantly outperform the state-of-the-art degeneracy computation algorithms in terms of both running time and I/O costs. The results also demonstrate high scalability of the proposed algorithms. For example, in a real-world web graph with 930 million nodes and 13.3 billion edges, the proposed algorithm takes only 633 seconds and uses less than 4.5GB memory to compute the degeneracy.

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study the problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose novel models, including$\sigma$-periodic$k$-core and$\sigma$-periodic$k$-clique, that represent periodic communities in temporal networks. Specifically, a$\sigma$-periodic$k$-core (or$\sigma$-periodic$k$-clique) is a$k$-core (or clique with size larger than$k$) that appears at least$\sigma$times periodically in the temporal graph. The problem of searching periodic core is efficient but the resulting communities may be not enough cohesive; the problem of enumerating all periodic cliques is not efficient (NP-hard) but the resulting communities are very cohesive. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we transform the temporal graph into a static graph and prove that mining the periodic communities in the temporal graph equals mining communities in the transformed graph. Subsequently, we propose a decomposition algorithm to search maximal$\sigma$-periodic$k$-core, a Bron-Kerbosch style algorithm to enumerate all maximal$\sigma$-periodic$k$-cliques, and a branch-and-bound style algorithm to find the maximum$\sigma$-periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Uncertain graph management and analysis have attracted many research attentions. Among them, computing k-cores in uncertain graphs (aka, (k,)-cores) is an important problem and has emerged in many applications. Given an uncertain graph, the (k,)-cores can be derived by iteratively removing the vertex with an -degree of less than k and updating the -degrees of its neighbors. However, the results heavily depend on the two input parameters k and, and the settings for these parameters are unique to the specific graph structure and the user's subjective requirements. Additionally, computing and updating the -degree for each vertex is costly. To overcome these drawbacks, we have developed an index-based solution for computing (k,)-cores in this paper. The size of the index is well bounded by O(m), where m is the number of edges in the graph. Based on this index, queries can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also propose a new algorithm for index construction in external memory, when the uncertain graph cannot be entirely loaded in memory. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all the proposed algorithms.

Core decomposition is a fundamental operator in network analysis. In this paper, we study a problem of computing distance-generalized core decomposition on a network. A distance-generalized core, also termed (k, h)-core, is a maximal subgraph in which every vertex has at least k other vertices at distance no larger than h. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes the vertex (denoted by v) from the graph that has the smallest h-hop degree. The h-hop degree of a vertex v denotes the number of other vertices that are reachable from v within h hops. Such a peeling algorithm, however, needs to frequently recompute the h-hop degrees of v's neighbors after deleting v, which is typically very costly for a large h. To overcome this limitation, we propose an efficient peeling algorithm based on a novel h-hop degree updating technique. Instead of recomputing the h-hop degrees, our algorithm can dynamically maintain the h-hop degrees for all vertices via exploring a very small subgraph, after peeling a vertex. We show that such an h-hop degree updating procedure can be efficiently implemented by an elegant bitmap technique. In addition, we also propose a sampling-based algorithm and a parallelization technique to further improve the efficiency. Finally, we conduct extensive experiments on 12 real-world graphs to evaluate our algorithms. The results show that, when h≥3, our exact and sampling-based algorithms can achieve up to 10x and 100x speedup over the state-of-the-art algorithm, respectively.

Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict, respectively. We propose a novel model, called maximal (a, k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)-clique is a clique in which every node has at most k negative neighbors and at least ⌈ak⌉ positive neighbors (α ≥ 1). We show that the problem of enumerating all maximal (a, k)-cliques in a signed network is NP-hard. To enumerate all maximal (a, k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (a, k)-cliques in the reduced signed network. In addition, we also propose an efficient algorithm with three novel upper-bounding techniques to find the maximum (a, k)-clique in a signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

The structural diversity of an edge, which is measured by the number of connected components of the edge's ego-network, has recently been recognized as a key metric for analyzing social influence and information diffusion in social networks. Given this, an important problem in social network analysis is to identify top-k edges that have the highest structural diversities. In this work, we for the first time perform a systematical study for the top-k edge structural diversity search problem on large graphs. Specifically, we first develop a new online search framework with two basic upper-bounding rules to efficiently solve this problem. Then, we propose a new index structure using near-linear space to process the top-k edge structural diversity search in near-optimal time. To create such an index structure, we devise an efficient algorithm based on an interesting connection between our problem and the 4-clique enumeration problem. In addition, we also propose efficient index maintenance techniques to handle dynamic graphs. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Enumerating maximal cliques from an uncertain graph is a fundamental problem in uncertain graph analysis. Given an uncertain graph G, a set of nodes C in G is a maximal (k, τ)-clique if (1) |C|>k and C is a clique with probability at least τ, and (2) C is a maximal node set meeting (1). The state-of-the-art algorithm for enumerating all maximal (k, τ)-cliques is very costly when handling large uncertain graphs, as its time complexity is proportional to 2^n where n is the number of nodes in the uncertain graph. To overcome this issue, we propose two new core-based pruning algorithms to reduce the uncertain graph size without missing any maximal (k, τ)-clique. We also develop a novel cut-based optimization technique to further improve the pruning performance of the core-based pruning algorithms. Based on these pruning techniques, we propose an improved algorithm to enumerate all maximal (k, τ)-cliques, and a new algorithm with several novel upper-bounding techniques to compute one of maximum (k, τ)-cliques from the pruned uncertain graph. The results of extensive experiments on six real-world datasets demonstrate the efficiency and effectiveness of the proposed algorithms.

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study a problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose a novel model, called maximal σ-periodic k-clique, that represents a periodic community in temporal networks. Specifically, a maximal σ-periodic k-clique is a clique with size larger than k that appears at least σ times periodically in the temporal graph. We show that the problem of enumerating all those periodic cliques is NP-hard. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we present an efficient enumeration algorithm to enumerate all maximal σ-periodic k-cliques in the reduced graph. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Uncertainty in graph data occurs for a variety of reasons, such as noise and measurement errors. Recently, uncertain graph management and analysis have attracted many research attentions. Among them, computing k-cores in uncertain graphs (aka, (k, η)-cores) is an important problem and has emerged in many applications, for example, community detection, protein-protein interaction network analysis and influence maximization. Given an uncertain graph, the (k, η)-cores can be derived by iteratively removing the vertex with an η-degree of less than k and updating the η-degrees of its neighbors. However, the results heavily depend on the two input parameters k and η, and the settings for these parameters are unique to the specific graph structure and the user's subjective requirements. Additionally, computing and updating the η-degree for each vertex is the most costly component of the algorithm, and that cost is high. To overcome these drawbacks, we have developed an index-based solution for computing (k, η)-cores in this paper. The size of the index is well bounded by O(m), where m is the number of edges in the graph. Based on this index, queries for any k and η can be answered in optimal time. Further, the method is accompanied by several different optimizations to speed up construction of the index. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all the proposed algorithms. The results demonstrate that this index-based approach is several orders of magnitude faster at processing queries than the traditional online approaches.?

Community detection is of significant importance in understanding the structures and functions of networks. Recently, overlapping community detection has drawn much attention due to the ubiquity of overlapping community structures in real-world networks. Nonnegative matrix factorization (NMF), as an emerging standard framework, has been widely employed for overlapping community detection, which obtains nodes' soft community memberships by factorizing the adjacency matrix into low-rank factor matrices. However, in order to determine the ultimate community memberships, we have to post-process the real-valued factor matrix by manually specifying a threshold on it, which is undoubtedly a difficult task. Even worse, a unified threshold may not be suitable for all nodes. To circumvent the cumbersome post-processing step, we propose a novel discrete overlapping community detection approach, i.e., Discrete Nonnegative Matrix Factorization (DNMF), which seeks for a discrete (binary) community membership matrix directly. Thus DNMF is able to assign explicit community memberships to nodes without post-processing. Moreover, DNMF incorporates a pseudo supervision module into it to exploit the discriminative information in an unsupervised manner, which further enhances its robustness. We thoroughly evaluate DNMF using both synthetic and real-world networks. Experiments show that DNMF has the ability to outperform state-of-the-art baseline approaches.

Given an undirected graph G and a seed node s, the local clustering problem aims to identify a high-quality cluster containing s in time roughly proportional to the size of the cluster, regardless of the size of G. This problem finds numerous applications on large-scale graphs. Recently, heat kernel PageRank (HKPR), which is a measure of the proximity of nodes in graphs, is applied to this problem and found to be more efficient compared with prior methods. However, existing solutions for computing HKPR either are prohibitively expensive or provide unsatisfactory error approximation on HKPR values, rendering them impractical especially on billion-edge graphs. In this paper, we present TEA and TEA+, two novel local graph clustering algorithms based on HKPR, to address the aforementioned limitations. Specifically, these algorithms provide non-trivial theoretical guarantees in relative error of HKPR values and the time complexity. The basic idea is to utilize deterministic graph traversal to produce a rough estimation of exact HKPR vector, and then exploit Monte-Carlo random walks to refine the results in an optimized and non-trivial way. In particular, TEA+ offers practical efficiency and effectiveness due to non-trivial optimizations. Extensive experiments on real-world datasets demonstrate that TEA+ outperforms the state-of-the-art algorithm by more than four times on most benchmark datasets in terms of computational time when achieving the same clustering quality, and in particular, is an order of magnitude faster on large graphs including the widely studied Twitter and Friendster datasets.

Structural clustering is a fundamental graph mining operator which is not only able to find densely-connected clusters, but it can also identify hub vertices and outliers in the graph. Previous structural clustering algorithms are tailored to deterministic graphs. Many real-world graphs, however, are not deterministic, but are probabilistic in nature because the existence of the edge is often inferred using a variety of statistical approaches. In this paper, we formulate the problem of structural clustering on probabilistic graphs, with the aim of finding reliable clusters in a given probabilistic graph. Unlike the traditional structural clustering problem, our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph. We develop a dynamic programming algorithm with several powerful pruning strategies to efficiently compute the reliable structural similarities. With the reliable structural similarities, we adapt an existing solution framework to calculate the structural clustering on probabilistic graphs. Comprehensive experiments on five real-life datasets demonstrate the effectiveness and efficiency of the proposed approaches.

The problem of influence maximization has recently received significant attention. However, most studies focused on user influence via cyber interactions while ignoring their physical interactions which are important to gauge influence propagation. Additionally, targeted campaigns or advertisements have not received sufficient attention. To do this, we first devise a novel holistic influence diffusion model and then formulate a new holistic influence maximization query problem and develop three algorithms. Finally, we conduct extensive experiments to evaluate the effectiveness and efficiency of the proposed solutions.

Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict respectively. We propose a novel model, called maximal (α, k)-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal (α, k)-clique is a clique in which every node has at most. negative neighbors and at least [αk] positive neighbors (α ≥ 1). We show that the problem of enumerating all maximal (α, k)- cliques in a signed network is NP-hard. To enumerate all maximal (α,k)-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal (α,k)-cliques in the reduced signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.

Community search is a fundamental graph mining task. Unfortunately, most previous community search studies focus mainly on identifying communities in a network without temporal information. In this paper, we study the problem of finding persistent communities in a temporal network, in which every edge is associated with a timestamp. Our goal is to identify the communities that are persistent over time. To this end, we propose a novel persistent community model called (θ,τ) community. We prove that the problem of identifying the maximum (θ,τ) persistent k-core is NP-hard. To solve this problem, we propose a novel branch and bound algorithm with several carefully-designed pruning rules to find the maximum (θ,τ)-persistent. We conduct k-cores efficiently. We conduct extensive experiments in several real-world temporal networks. The results demonstrate the efficiency, scalability, and effectiveness of the proposed solutions.

Given a scientific collaboration network, how can we find a group of collaborators with high research indicator (e.g., h-index) and diverse research interests? Given a social network, how can we identify the communities that have high influence (e.g., PageRank) and also have similar interests to a specified user? In such settings, the network can be modeled as a multi-valued network where each node has d ($d \ge 1$) numerical attributes (i.e., h-index, diversity, PageRank, similarity score, etc.). In the multi-valued network, we want to find communities that are not dominated by the other communities in terms of d numerical attributes. Most existing community search algorithms either completely ignore the numerical attributes or only consider one numerical attribute of the nodes. To capture d numerical attributes, we propose a novel community model, called skyline community, based on the concepts of k-core and skyline. A skyline community is a maximal connected k-core that cannot be dominated by the other connected k-cores in the d-dimensional attribute space. We develop an elegant space-partition algorithm to efficiently compute the skyline communities. Two striking advantages of our algorithm are that (1) its time complexity relies mainly on the size of the answer s (i.e., the number of skyline communities), thus it is very efficient if s is small; and (2) it can progressively output the skyline communities, which is very useful for applications that only require part of the skyline communities. Extensive experiments on both synthetic and real-world networks demonstrate the efficiency, scalability, and effectiveness of the proposed algorithm.

Discovering dense subgraphs in a graph is a fundamental graph mining task, which has a wide range of applications in social networks, biology and visualization to name a few. Even the problem of computing most cohesive subgraphs is NP-hard (like clique, quasi-clique, k-densest subgraph), there exists a polynomial time algorithm for computing the k-core and k-truss. In this paper, we propose a novel dense subgraph model, $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ , which leverages on a new type of important edges based on the basis of k-core and k-truss. We investigate the structural properties of the $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ model. Compared to k-core and k-truss, $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ can significantly discover the interesting and important structural information out the scope of k-core and k-truss. We study two useful problems of $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ decomposition and $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ search. In particular, we develop a k-core-truss decomposition algorithm to find all $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ in a graph G by iteratively removing edges with the smallest $${\mathsf {degree}}$$ - $${\mathsf {support}}$$ . In addition, we offer a $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ search algorithm to identifying a particular $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ containing a given query node such that the core number k is the largest. Extensive experiments on several web-scale real-world datasets show the effectiveness and efficiency of $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ model and proposed algorithms.

Community discovery plays an essential role in the analysis of the structural features of complex networks. Since online networks grow increasingly large and complex over time, the methods traditionally used for community discovery cannot efficiently handle large-scale network data. This introduces the important problem of how to effectively and efficiently discover large communities from complex networks. In this study, we propose a fast parallel community discovery model called picaso (a parallel community discovery algorithm based on approximate optimization), which integrates two new techniques: (1) Mountain model, which works by utilizing graph theory to approximate the selection of nodes needed for merging, and (2) Landslide algorithm, which is used to update the modularity increment based on the approximated optimization. In addition, the GraphX distribution computing framework is employed in order to achieve parallel community detection over complex networks. In the proposed model, clustering on modularity is used to initialize the Mountain model as well as to compute the weight of each edge in the networks. The relationships among the communities are then simplified by applying the Landslide algorithm, which allows us to obtain the community structures of the complex networks. Extensive experiments were conducted on real and synthetic complex network datasets, and the results demonstrate that the proposed algorithm can outperform the state of the art methods, in effectiveness and efficiency, when working to solve the problem of community detection. Moreover, we demonstratively prove that overall time performance approximates to four times faster than similar approaches. Effectively our results suggest a new paradigm for large-scale community discovery of complex networks.

The Group Steiner Tree (GST) problem is a fundamental problem in database area that has been successfully applied to keyword search in relational databases and team search in social networks. The state-of-the-art algorithm for the GST problem is a parameterized dynamic programming (DP) algorithm, which finds the optimal tree in O(3kn+2k(n log n + m)) time, where k is the number of given groups, m and n are the number of the edges and nodes of the graph respectively. The major limitations of the parameterized DP algorithm are twofold: (i) it is intractable even for very small values of k (e.g., k=8) in large graphs due to its exponential complexity, and (ii) it cannot generate a solution until the algorithm has completed its entire execution. To overcome these limitations, we propose an efficient and progressive GST algorithm in this paper, called PrunedDP. It is based on newly-developed optimal-tree decomposition and conditional tree merging techniques. The proposed algorithm not only drastically reduces the search space of the parameterized DP algorithm, but it also produces progressively-refined feasible solutions during algorithm execution. To further speed up the PrunedDP algorithm, we propose a progressive A*-search algorithm, based on several carefully-designed lower-bounding techniques. We conduct extensive experiments to evaluate our algorithms on several large scale real-world graphs. The results show that our best algorithm is not only able to generate progressively-refined feasible solutions, but it also finds the optimal solution with at least two orders of magnitude acceleration over the state-of-the-art algorithm, using much less memory.

Real-time ride-sharing applications (e.g., Uber and Lyft) are very popular in recent years. Motivated by the ride-sharing application, we propose a new type of query in road networks, called the optimal multi-meeting-point route (OMMPR) query. Given a road network G, a source nodes, a target node t, and a set of query nodes U, the OMMPR query aims at finding the best route starting from s and ending at t such that the weighted average cost between the cost of the route and the total cost of the shortest paths from every query node to the route is minimized. We show that the problem of computing the OMMPR query is NP-hard. To answer the OMMPR query efficiently, we propose two novel parameterized solutions based on dynamic programming (DP), with the number of query nodes l (i.e., l = |U|) as a parameter, which is typically very small in practice. The two proposed parameterized algorithms run in O(3l· m + 2l· n · (l + log (n))) and O(2l· (m + n · (l + log (n)))) time, respectively, where n and m denote the number of nodes and edges in graph G, thus they are tractable in practice. To reduce the search space of the DP-based algorithms, we propose two novel optimized algorithms based on bidirectional DP and a carefully-designed lower bounding technique. We conduct extensive experimental studies on four large real-world road networks, and the results demonstrate the efficiency of the proposed algorithms.

Uncertain graph management has been recognized as an important research topic in recent years. In this paper, we first introduce two types of query evaluation problems on uncertain graphs, named expectation query evaluation and threshold query evaluation. Most previous solutions for these problems are based on naive Monte-Carlo (NMC) sampling, which typically result in large variances. To reduce the variance ofNMC, we propose two efficient estimators, calledRSS-IandRSS-IIestimators, based on the idea of recursive stratified sampling (RSS). To further reduce the variances ofRSS-IandRSS-II, we propose a recursivecut-setbased stratified sampling estimator for a particular kind of query evaluation problem. We show that all the proposed estimators are unbiased and their variances are significantly smaller than that ofNMC. Moreover, the time complexity of all the proposed estimators are the same as that ofNMCunder a mild assumption. In addition, we develop an elegant graph simplification technique to further improve the accuracy and running time of our estimators. We also apply the proposed estimators to three different uncertain graph query evaluation problems. Finally, we conduct extensive experiments to evaluate the proposed estimators, and the results show the accuracy, efficiency, and scalability of our estimators.

Social hierarchy (i.e., pyramid structure of societies) is a fundamental concept in sociology and social network analysis. The importance of social hierarchy in a social network is that the topological structure of the social hierarchy is essential in both shaping the nature of social interactions between individuals and unfolding the structure of the social networks. The social hierarchy found in a social network can be utilized to improve the accuracy of link prediction, provide better query results, rank web pages, and study information flow and spread in complex networks. In this paper, we model a social network as a directed graph$G$, and consider the social hierarchy as DAG (directed acyclic graph) of$G$, denoted as$G_D$. By DAG, all the vertices in$G$can be partitioned into different levels, the vertices at the same level represent a disjoint group in the social hierarchy, and all the edges in DAG follow one direction. The main issue we study in this paper is how to find DAG$G_D$in$G$. The approach we take is to find$G_D$by removing all possible cycles from$G$such that$G = {\cal U}(G) \cup G_D$, where${\cal U}(G)$is a maximum Eulerian subgraph which contains all possible cycles. We give the reasons for doing so, investigate the properties of$G_D$found, and discuss the applications. In addition, we develop a novel two-phase algorithm, called Greedy-&-Refine, which greedily computes an Eulerian subgraph and then refines this greedy solution to find the maximum Eulerian subgraph. We give a bound between the greedy solution and the optimal. The quality of our greedy approach is high. We conduct comprehensive experimental studies over 14 real-world datasets. The results show that our algorithms are at least two orders of magnitude faster than the baseline algorithm.

Random walk based graph sampling has been recognized as a fundamental technique to collect uniform node samples from a large graph. In this paper, we first present a comprehensive analysis of the drawbacks of three widely-used random walk based graph sampling algorithms, called re-weighted random walk (RW) algorithm, Metropolis-Hastings random walk (MH) algorithm and maximum-degree random walk (MD) algorithm. Then, to address the limitations of these algorithms, we propose two general random walk based algorithms, named rejection-controlled Metropolis-Hastings (RCMH) algorithm and generalized maximum-degree random walk (GMD) algorithm. We show that RCMH balances the tradeoff between the limitations of RW and MH, and GMD balances the tradeoff between the drawbacks of RW and MD. To further improve the performance of our algorithms, we integrate the so-called delayed acceptance technique and the non-backtracking random walk technique into RCMH and GMD respectively. We conduct extensive experiments over four real-world datasets, and the results demonstrate the effectiveness of the proposed algorithms.

Mining dense subgraphs from a large graph is a fundamental graph mining task and can be widely applied in a variety of application domains such as network science, biology, graph database, web mining, graph compression, and micro-blogging systems. Here a dense subgraph is defined as a subgraph with high density (#.edge / #.node). Existing studies of this problem either focus on finding the densest subgraph or identifying an optimal clique-like dense subgraph, and they adopt a simple greedy approach to find the top-k dense subgraphs. However, their identified subgraphs cannot be used to represent the dense regions of the graph. Intuitively, to represent a dense region, the subgraph identified should be the subgraph with highest density in its local region in the graph. However, it is non-trivial to formally model a locally densest subgraph. In this paper, we aim to discover top-k such representative locally densest subgraphs of a graph. We provide an elegant parameter-free definition of a locally densest subgraph. The definition not only fits well with the intuition, but is also associated with several nice structural properties. We show that the set of locally densest subgraphs in a graph can be computed in polynomial time. We further propose three novel pruning strategies to largely reduce the search space of the algorithm. In our experiments, we use several real datasets with various graph properties to evaluate the effectiveness of our model using four quality measures and a case study. We also test our algorithms on several real web-scale graphs, one of which contains 118.14 million nodes and 1.02 billion edges, to demonstrate the high efficiency of the proposed algorithms.

Community search is a problem of finding densely connected subgraphs that satisfy the query conditions in a network, which has attracted much attention in recent years. However, all the previous studies on community search do not consider the influence of a community. In this paper, we introduce a novel community model called k -influential community based on the concept of k -core, which can capture the influence of a community. Based on the new community model, we propose a linear-time online search algorithm to find the top- r k -influential communities in a network. To further speed up the influential community search algorithm, we devise a linear-space index structure which supports efficient search of the top- r k -influential communities in optimal time. We also propose an efficient algorithm to maintain the index when the network is frequently updated. We conduct extensive experiments on 7 real-world large networks, and the results demonstrate the efficiency and effectiveness of the proposed methods.

We introduce and formulate two types of random-walk domination problems in graphs motivated by a number of applications in practice (e.g., item-placement problem in online social networks, Ads-placement problem in advertisement networks, and resource-placement problem in P2P networks). Specifically, given a graph G, the goal of the first type of random-walk domination problem is to target k nodes such that the total hitting time of an L-length random walk starting from the remaining nodes to the targeted nodes is minimized. The second type of random-walk domination problem is to find k nodes to maximize the expected number of nodes that hit any one targeted node through an L-length random walk. We prove that these problems are two special instances of the submodular set function maximization with cardinality constraint problem. To solve them effectively, we propose a dynamic-programming (DP) based greedy algorithm which is with near-optimal performance guarantee. The DP-based greedy algorithm, however, is not very efficient due to the expensive marginal gain evaluation. To further speed up the algorithm, we propose an approximate greedy algorithm with linear time complexity w.r.t. the graph size and also with near-optimal performance guarantee. The approximate greedy algorithm is based on carefully designed random walk sampling and sample-materialization techniques. Extensive experiments demonstrate the effectiveness, efficiency and scalability of the proposed algorithms.

In this paper, we introduce two types of query evaluation problems on uncertain graphs: expectation query evaluation and threshold query evaluation. Since these two problems are #P-complete, most previous solutions for these problems are based on naive Monte-Carlo (NMC) sampling. However, NMC typically leads to a large variance, which significantly reduces its effectiveness. To overcome this problem, we propose two classes of estimators, called class-I and class-II estimators, based on the idea of stratified sampling. More specifically, we first propose two classes of basic stratified sampling estimators, named BSS-I and BSS-II, which partition the entire population into 2rand r+1 strata by picking r edges respectively. Second, to reduce the variance, we find that both BSS-I and BSS-II can be recursively performed in each stratum. Therefore, we propose two classes of recursive stratified sampling estimators called RSS-I and RSS-II respectively. Third, for a particular kind of problem, we propose two cut-set based stratified sampling estimators, named BCSS and RCSS, to further improve the accuracy of the class-I and class-II estimators. For all the proposed estimators, we prove that they are unbiased and their variances are significantly smaller than that of NMC. Moreover, the time complexity of all the proposed estimators are the same as the time complexity of NMC under a mild assumption. In addition, we also apply the proposed estimators to influence function evaluation and expected-reliable distance query problem, which are two instances of the query evaluation problems on uncertain graphs. Finally, we conduct extensive experiments to evaluate our estimators, and the results demonstrate the efficiency, accuracy, and scalability of the proposed estimators.

The k-core decomposition in a graph is a fundamental problem for social network analysis. The problem of k-core decomposition is to calculate the core number for every node in a graph. Previous studies mainly focus on k-core decomposition in a static graph. There exists a linear time algorithm for k-core decomposition in a static graph. However, in many real-world applications such as online social networks and the Internet, the graph typically evolves overtime. In such applications, a key issue is to maintain the core numbers of nodes when the graph changes overtime. A simple implementation is to perform the linear time algorithm to recompute the core number for every node after the graph is updated. Such simple implementation is expensive when the graph is very large. In this paper, we propose a new efficient algorithm to maintain the core number for every node in a dynamic graph. Our main result is that only certain nodes need to update their core numbers when the graph is changed by inserting/deleting an edge. We devise an efficient algorithm to identify and recompute the core numbers of such nodes. The complexity of our algorithm is independent of the graph size. In addition, to further accelerate the algorithm, we develop two pruning strategies by exploiting the lower and upper bounds of the core number. Finally, we conduct extensive experiments over both real-world and synthetic datasets, and the results demonstrate the efficiency of the proposed algorithm.

Social contagion depicts a process of information (e.g., fads, opinions, news) diffusion in the online social networks. A recent study reports that in a social contagion process the probability of contagion is tightly controlled by the number of connected components in an individual's neighborhood. Such a number is termed structural diversity of an individual and it is shown to be a key predictor in the social contagion process. Based on this, a fundamental issue in a social network is to find top-kusers with the highest structural diversities. In this paper, we, for the first time, study the top-kstructural diversity search problem in a large network. Specifically, we develop an effective upper bound of structural diversity for pruning the search space. The upper bound can be incrementally refined in the search process. Based on such upper bound, we propose an efficient framework for top-kstructural diversity search. To further speed up the structural diversity evaluation in the search process, several carefully devised heuristic search strategies are proposed. Extensive experimental studies are conducted in 13 real-world large networks, and the results demonstrate the efficiency and effectiveness of the proposed methods.

Enhancing diversity in ranking on graphs has been identified as an important retrieval and mining task. Nevertheless, many existing diversified ranking algorithms either cannot be scalable to large graphs due to the time or memory requirements, or lack an intuitive and reasonable diversified ranking measure. In this paper, we propose a new diversified ranking measure on large graphs, which captures both relevance and diversity, and formulate the diversified ranking problem as a submodular set function maximization problem. Based on the submodularity of the proposed measure, we develop an efficient greedy algorithm with linear time and space complexity w.r.t. the size of the graph to achieve near-optimal diversified ranking. In addition, we present a generalized diversified ranking measure and give a near-optimal randomized greedy algorithm with linear time and space complexity for optimizing it. We evaluate the proposed methods through extensive experiments on five real data sets. The experimental results demonstrate the effectiveness and efficiency of the proposed algorithms.

Measuring robustness of complex networks is a fundamental task for analyzing the structure and function of complex networks. In this paper, we study the network robustness under the maximal vertex coverage (MVC) attack, where the attacker aims to delete as many edges of the network as possible by attacking a small fraction of nodes. First, we present two robustness metrics of complex networks based on MVC attack. We then propose an efficient randomized greedy algorithm with near-optimal performance guarantee for computing the proposed metrics. Finally, we conduct extensive experiments on 20 real datasets. The results show that P2P and co-authorship networks are extremely robust under the MVC attack while both the online social networks and the Email communication networks exhibit vulnerability under the MVC attack. In addition, the results demonstrate the efficiency and effectiveness of our proposed algorithms for computing the corresponding robustness metrics.

With the growth of the Internet and E-commerce, bipartite rating networks are ubiquitous. In such bipartite rating networks, there exist two types of entities: the users and the objects, where users give ratings to objects. A fundamental problem in such networks is how to rank the objects by user's ratings. Although it has been extensively studied in the past decade, the existing algorithms either cannot guarantee convergence, or are not robust to the spammers. In this paper, we propose six new reputation-based algorithms, where the users' reputation is determined by the aggregated difference between the users' ratings and the corresponding objects' rankings. We prove that all of our algorithms converge into a unique fixed point. The time and space complexity of our algorithms are linear w.r.t. the size of the graph, thus they can be scalable to large datasets. Moreover, our algorithms are robust to the spamming users. We evaluate our algorithms using three real datasets. The experimental results confirm the effectiveness, efficiency, and robustness of our algorithms.

Link prediction is a fundamental problem in social network analysis. The key technique in unsupervised link prediction is to find an appropriate similarity measure between nodes of a network. A class of wildly used similarity measures are based on random walk on graph. The traditional random walk (TRW) considers the link structures by treating all nodes in a network equivalently, and ignores the centrality of nodes of a network. However, in many real networks, nodes of a network not only prefer to link to the similar node, but also prefer to link to the central nodes of the network. To address this issue, we use maximal entropy random walk (MERW) for link prediction, which incorporates the centrality of nodes of the network. First, we study certain important properties of MERW on graph $G$ by constructing an eigen-weighted graph G. We show that the transition matrix and stationary distribution of MERW on G are identical to the ones of TRW on G. Based on G, we further give the maximal entropy graph Laplacians, and show how to fast compute the hitting time and commute time of MERW. Second, we propose four new graph kernels and two similarity measures based on MERW for link prediction. Finally, to exhibit the power of MERW in link prediction, we compare 27 various link prediction methods over 3 synthetic and 8 real networks. The results show that our newly proposed MERW based methods outperform the state-of-the-art method on most datasets.

Enhancing diversity in ranking on graphs has been identified as an important retrieval and mining task. Nevertheless, many existing diversified ranking algorithms cannot be scalable to large graphs as they have high time or space complexity. In this paper, we propose a scalable algorithm to find the top-K diversified ranking list on graphs. The key idea of our algorithm is that we first compute the Pagerank of the nodes of the graph, and then perform a carefully designed vertex selection algorithm to find the top-K diversified ranking list. Specifically, we firstly present a new diversified ranking measure, which can capture both relevance and diversity. Secondly, we prove the submodularity of the proposed measure. And then we propose an efficient greedy algorithm with linear time and space complexity with respect to the size of the graph to achieve near-optimal diversified ranking. Finally, we evaluate the proposed method through extensive experiments on four real networks. The experimental results indicate that the proposed method outperforms existing diversified ranking algorithms both on improving diversity in ranking and the efficiency of the algorithms.