Approximate Nearest Neighbor Search (ANNS) over high-dimensional vectors is a foundational problem in databases, where disk I/O often emerges as the dominant performance bottleneck at scale. To accelerate search, graph-based indexes rely on proximity graph, where nodes represent vectors and edges guide the traversal toward the target. However, existing graph indexing solutions for disk-based ANNS typically either optimize the storage layout for a given graph or construct the graph independently of the storage layout, thus overlooking their interaction. In this paper, we bridge this gap by proposing the Block-aware Monotonic Relative Neighborhood Graph (BMRNG), theoretically guaranteeing the existence of I/O monotonic search paths. The core idea is to align the graph topology with the data placement by jointly considering both geometric distance and storage layout for edge selection. To address the scalability challenge of BMRNG construction, we further develop a practical and efficient variant, the Block-Aware Monotonic Graph (BAMG), which can be constructed in linear time from a monotonic graph considering the storage layout. BAMG integrates block-aware edge pruning with a decoupled storage design that separates raw vectors from the graph index, thereby maximizing block utilization and minimizing redundant disk reads. Additionally, we design a multi-layer navigation graph for adaptive and efficient query entry, along with a block-first search algorithm that prioritizes intra-block traversal to fully exploit each disk I/O operation. Extensive experiments on real-world datasets show that BAMG can outperform state-of-the-art methods in search performance.

Graph Neural Networks (GNNs) unlock new ways of learning from graph-structured data, proving highly effective in capturing complex relationships and patterns. Federated GNNs (FGNNs) have emerged as a prominent distributed learning paradigm for training GNNs over decentralized data. However, FGNNs face two significant challenges: high communication overhead from multiple rounds of parameter exchanges and non-IID data characteristics across clients. To address these issues, we introduce CeFGC, a novel FGNN paradigm that facilitates efficient GNN training over non-IID data by limiting communication between the server and clients to three rounds only. The core idea of CeFGC is to leverage generative diffusion models to minimize direct client-server communication. Each client trains a generative diffusion model that captures its local graph distribution and shares this model with the server, which then redistributes it back to all clients. Using these generative models, clients generate synthetic graphs combined with their local graphs to train local GNN models. Finally, clients upload their model weights to the server for aggregation into a global GNN model. We theoretically analyze the I/O complexity of communication volume to show that CeFGC reduces to a constant of three communication rounds only. Extensive experiments on several real graph datasets demonstrate the effectiveness and efficiency of CeFGC against state-of-the-art competitors, reflecting our superior performance on non-IID graphs by aligning local and global model objectives and enriching the training set with diverse graphs.

Information diffusion prediction aims to forecast the temporal spread of opinions and behaviors by identifying potential adopters. Existing methods typically treat information diffusion as a sequence of individual adoptions and rely on computationally expensive pairwise (one-to-one) influence computations, often restricting predictions to just the next adopter. This individual-level paradigm both misrepresents real-world collective (many-to-many) influences and suffers a critical efficiency trade-off: to remain feasible, such models must truncate long diffusion histories, thereby overlooking early initiators and opinion leaders. To overcome these limitations, we formalize a more practical task: Group-based Information Diffusion Prediction, and propose an effective and scalable GRID framework. Specifically, GRID first learns group-oriented graph embeddings via a task-regularized information bottleneck objective, which amplifies key influence pathways and produces reliable user embeddings for group identification. Built on these embeddings, the core GroupAttn module captures inter-group influence while reducing complexity from quadratic to linear in cascade length. This enables the modeling of ultra-long cascades (exceeding 10,000 users) without truncation while preserving representational fidelity within a provable error bound. Finally, a group-wise objective guides the model to predict semantically meaningful future groups. Extensive experiments on four real-world datasets show that GRID outperforms ten state-of-the-art baselines by an average of 10.65% in accuracy, while achieving an order-of-magnitude gain in efficiency and extending the supported cascade length by up to 10 times.

Graph data has become increasingly important in the AI and big data era. However, graph data analysis raises privacy concerns since it often originates from individual users. As a privacy regulation, the right to be forgotten has been established to allow users to erase their data hosted by a third party. When users request to delete their information from the original graph, the deletion must be synchronized to analysis results, like graph statistics or pre-trained AI models. In existing works, much effort has been made to fulfill the right to be forgotten for complicated graph learning models. In this work, we aim at a fundamental query — graph summarization, which serves as a building block for many graph analysis tasks. Since in summarization, when data removal requests are received, re-summarizing the graph from scratch can be costly, we present a novel approach to graph summarization regarding potential deletion requests. Inspired by machine unlearning, we define this problem as graph unsummarization which has three goals: efficiency, forgetting quality, and utility. Towards these goals, we propose SUGPT, a graph summarization and unsummarization method based on matrix partition and trie. The essence of SUGPT is to identify similarities between vertices by embedding matrix partitions into a trie structure, to accelerate summary updating upon deletion requests. We prove the forgetting quality of SUGPT theoretically and our extensive experiments demonstrate that SUGPT balances well in efficiency and utility in graph analysis.

Hierarchical directed acyclic graph (DAG) is an essential model for representing terminologies and their hierarchical relationships, such as Disease Ontology and ImageNet categories. Due to the vast number of terminologies and complex structures in a large DAG, it becomes challenging for humans to effectively analyze and explore the hierarchical relationships they encode. Therefore, summarizing hierarchical DAGs is essential for enhancing the interpretability and visualization of the underlying hierarchy. Beyond visual data exploration, hierarchical DAG summarization also supports a range of applications, such as biomedical ontology analytics, snippet generation for information search, and summarized recommendation. In this article, we address a new problem of finding k representative vertices to summarize a hierarchical DAG. To capture diverse summarization and identify important vertices, we design a summary score function that reflects vertices diversity coverage and structure correlation. The studied problem is theoretically proven to be NP-hard. To tackle it efficiently, we propose a greedy algorithm with an approximation guarantee that iteratively adds vertices with significant summary contributions to the answers. To further enhance the answer quality, we introduce a subtree extraction-based method that is proven to achieve higher-quality answers. Additionally, we develop a scalable algorithm, \(\mathsf {k}\) - \(\mathsf {PCGS}\) , which employs candidate pruning and DAG compression for large-scale hierarchical DAGs. For the query-dependent problem, we propose an index-based method and several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

Community search, which finds cohesive subgraphs containing given query vertices, has attracted much attention in decades. On attributed graphs, when considering the fairness of members' attributes in a community, the cohesiveness constraint of a clique is too strong, which often causes no fair clique based communities can be found. Thus, in this paper, we use the k-truss model, which is a relaxation of the clique but whose members have large engagement and high tie strength, to describe fair communities, namely fair k-truss communities (FTC) and anchored fair k-truss communities (AFTC, using anchored vertices to help satisfying the fairness constraint). We formulate the FTC and AFTC search problems to find the FTC or AFTC containing a given query vertex$q$which has the largest$k$and the smallest diameter. We prove the hardness of both problems. We develop several greedy algorithms and acceleration strategies to solve FTC and AFTC search problems. Experiments on 8 real-world networks show the significance of our FTC and AFTC models, and high performance of our algorithms and acceleration strategies.

Information diffusion prediction is fundamental for forecasting user participation in information sharing on social networks, such as retweets on Twitter. Existing methods typically extract user relationships from social networks and historical interactions, while further capturing contextual information within the specific diffusion process. However, these methods have several limitations: (1) They often utilize sequential diffusion process for prediction and simplify differentiated influences among participants; (2) They capture user relationships on the entire graph for all users, in which most information is not necessary for a specific diffusion process and is too inefficient for real-world large-scale networks. To tackle these limitations, we propose a novel and scalable model SILN, for sphere-based information diffusion prediction on large social networks. Specifically, SILN features three components. First, we integrate two kinds of sphere effects in terms of structural and temporal views, which learn an enhanced cascade representation. Second, SILN designs an efficient learning scheme based on the cascade-specific subgraph, which significantly reduces the entire graph computation to smaller subgraphs. Third, to facilitate subgraph extraction, we develop an optimized graph storage technique to allow constant-time neighbor access and reduce the storage cost by about 30% in practice. Extensive experiments on six real-world datasets validate that SILN consistently outperforms seven state-of-the-art competitors in prediction performance while exhibiting exceptional time and space efficiency on million-node social networks.

Community search finds query-dependent communities over graphs, which has been investigated broadly. In this work, we focus on the task of returning only a single connected community containing all user input query vertices. Most existing studies in the literature only propose a single and static model based on a particular subgraph (e.g., k -core, k -truss, quasi-clique, and learning-based component). These fixed models are hard to find exact community answers on all datasets and fit with different underlying desires of users and queries. This implies that the community search task needs human-in-loop interactions , which allows users to give feedback and dynamically advise community refinement. To tackle the above issues, we formulate and study the problem of interactive community search , which allows users to add/delete vertices for improving community answers in a few rounds of interactions. We first summarize dozens of existing community models and develop an integrated notation system M( G, M, O, P ) to describe them all. Then, we propose a flexible approach to interactive community search over graphs called GICS-framework. The successful principle of GICS-framework lies on three key components: personalized adding/deleting recommendation, parameter auto-tuning , and fast partial refinement. We develop efficient algorithms and successfully deploy three community models on our GICS-framework. We further analyze algorithm complexity of GICS-framework by illustrating one instance model in detail. Extensive experiments on ground-truth communities demonstrate that our interaction of GICS-framework improves F1-score accuracy by 22% against state-of-the-art competitors, and gives users real-time responses within one second.

Data summarization aims at utilizing a small-scale summary to represent massive datasets as a whole, which is useful for visualization and information sipped generation. However, most existing studies of hierarchical summarization only work onone single treeby selecting$k$representative nodes, which neglects an important problem of comparative summarization on two trees. In this paper, given two trees with the same topology structure and different node weights, we aim at finding$k$representative nodes, where$k_{1}$nodes summarize the common relationship between them and$k_{2}$nodes highlight significantly different subtrees meanwhile satisfying$k_{1}+k_{2}=k$. To optimize summarization results, we introduce a scaling coefficient for balancing the summary view between two subtrees in terms of similarity and difference. Additionally, we propose a novel definition based on the Hellinger distance to quantify the node distribution difference between two subtrees. We present a greedy algorithm SVDT to find high-quality results with approximation guaranteed in an efficient way. Furthermore, we explore an extension of our comparative summarization to handle two trees with different structures. Extensive experiments demonstrate the effectiveness and efficiency of our SVDT algorithm against existing summarization competitors.

The problem of structural diversity search has been widely studied recently, which aims to find out the users with the highest structural diversity in social networks. The structural diversity of a user is depicted by the number of social contexts inside his/her contact neighborhood. Three structural diversity models based on cohesive subgraph models (e.g., k-sized component, k-core, and k-truss), have been proposed. Previous solutions only focus on CPU-based sequential solutions, suffering from several key steps of that cannot be highly parallelized. GPUs enjoy high-efficiency performance in parallel computing for solving many complex graph problems such as triangle counting, subgraph pattern matching, and graph decomposition. In this paper, we provide a unified framework to utilize multiple GPUs to accelerate the computation of structural diversity search under the mentioned three structural diversity models. We first propose a GPU-based lock-free method to efficiently extract ego-networks in CSR format in parallel. Second, we design detailed GPU-based solutions for computingk-sized component-based,k-core-based, and alsok-truss-based structural diversity scores by dynamically grouping GPU resources. To effectively optimize the workload balance among multiple GPUs, we propose a greedy work-packing scheme and a dynamic work-stealing strategy to fulfill usage. Extensive experiments on real-world datasets validate the superiority of our GPU-based structural diversity search solutions in terms of efficiency and effectiveness.

A graph is a fundamental data model to represent various entities and their complex relationships in society and nature, such as social networks, transportation networks, financial networks, and biomedical systems. Recently, large language models (LLMs) have showcased a strong generalization ability to handle various natural language processing tasks to answer users' arbitrary questions and generate specific-domain content. Compared with graph learning models, LLMs enjoy superior advantages in addressing the challenges of generalizing graph tasks by eliminating the need for training graph learning models and reducing the cost of manual annotation. However, LLMs are sequential models for textual data, but graphs are non-sequential topological data. It is challenging to adapt LLMs to tackle graph analytics tasks. In this survey, we conduct a comprehensive investigation of existing LLM studies on graph data, which summarizes the relevant graph analytics tasks solved by advanced LLM models and points out the existing challenges and future directions. Specifically, we study the key problems of LLM-based generative graph analytics (LLM-GGA) in terms of three categories: LLM-based graph query processing (LLM-GQP), LLM-based graph inference and learning (LLM-GIL), and graph-LLM-based applications. LLM-GQP focuses on an integration of graph analytics techniques and LLM prompts, includinggraph understandingandknowledge graphs and LLMs, while LLM-GIL focuses on learning and reasoning over graphs, includinggraph learning,graph-formed reasoning, andgraph representation. We summarize the useful prompts incorporated into LLM to handle different graph downstream tasks. Moreover, we give a summary of LLM model evaluation, benchmark datasets/tasks, and a deep pro and cons analysis of the discussed LLM-GGA models. We also explore open problems and future directions in this exciting interdisciplinary research area of LLMs and graph analytics.

Networks in many real-world applications come with an inherent uncertainty in their structure, due to, for example, noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs have attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role. In this article, we study the problem of ( k , γ)-truss indexing and querying over an uncertain graph \({\mathcal {G}}\) . A ( k , γ)-truss is the largest subgraph of \({\mathcal {G}}\) such that the probability of each edge being contained in at least k -2 triangles is no less than γ. Our first proposal, CPT-index, keeps all the ( kz , γ)-trusses: retrieval for any given k and γ can be executed in an optimal linear time w.r.t. the graph size of the queried ( k , γ)-truss. We develop a bottom-up CPT-indexconstruction scheme and an improved algorithm for fast CPT-indexconstruction using top-down graph partitions. For trading off between ( k ,γ)-truss offline indexing and online querying, we further develop an approximate indexing approach ε , Δ r -APXequipped with two parameters, ε and Δ r , that govern tolerated errors. In addition, we further investigate the problem of maintaining ( k , γ)-truss indexes over dynamic uncertain graphs, where the update of vertex/edge insertions/deletions and also edge probability increments/decrements may frequently occur. We propose a comprehensive solution for CPT-indexand (ε , Δ r -APXmaintenance by addressing one fundamental task of one edge’s probability increment/decrement. To reduce the scope of affected edges that have trussness changed, we categorize three types of candidate edges and propose tight lower/upper bounds for trussness refinement, which can efficiently accomplish CPT-indexmaintenance in a local update scheme. Our proposed techniques for one single edge change can also be extended to handle a batch update of multiple edges. Extensive experiments using large-scale uncertain graphs with 261 million edges validate the efficiency of our proposed indexing and querying algorithms, as well as our ( k ,γ)-truss index maintenance algorithms, against state-of-the-art methods. Case studies on real-world graphs demonstrate the significant efficiency improvement by our proposed solutions as well as interesting discoveries.

Addressing the complexities of querying unstructured graphs such as knowledge graphs and social networks, this paper introduces D KWS, a novel distributed keyword search system. Leveraging a monotonic property, we ensure correct parallelization of our advanced keyword search algorithm, which incorporates tight pruning bounds and is divided into monotonic backward and forward search phases. The system is further augmented by the notify-push paradigm and the PINE programming model, facilitating asynchronous communication and preemptive searches to mitigate staleness in distributed environments. Extensive experiments on real-world datasets demonstrate DKWS's performance advantage, being up to two orders of magnitude faster and incurring 7.6 times lower communication costs than the existing systems.

The multilayer (ML) graph model provides a robust representation of multi-sourced relationships among real-world entities, laying a solid foundation for reliable knowledge discovery. ML core decomposition is a fundamental analytical tool for ML graphs. It offers valuable insights into the dense structures in ML graphs and forms the basis for many complex analysis tasks. However, existing ML core decomposition algorithms face performance issues due to unavoidably unnecessary computations and are inherently serial, unable to fully leverage the multi-core processors. In this paper, we reformulate the search space of this problem with a tree-shaped structure called MLC-tree. Based on it, we present an efficient serial ML core decomposition algorithm that achieves improved time complexity over existing solutions and the first parallel framework for this problem by exploiting the path-decomposition of the MLC-tree. Two practical optimizations are introduced to further boost the parallel efficiency. To facilitate applications built upon ML cores, we construct a compact storage and index structure for ML cores based on the MLC-tree. The usefulness of this index is showcased through two applications: ML core search and a novel weighted densest sub graph discovery problem. Extensive experiments on 9 real-world ML graphs show that our MLC-tree-based ML core decomposition algorithm achieves a speedup of up to$128\times$over existing baselines and the parallel approach attains an additional speedup of up to$30.6\times$using 40 cores. Moreover, the MLC-tree index can efficiently support the studied applications.

Graph Neural Networks (GNNs) have proven to be highly effective in addressing the link prediction problem. However, the need for large amounts of user data to learn representations of user interactions raises concerns about data privacy. While differential privacy (DP) techniques have been widely used for node-level tasks in graphs, incorporating DP into GNNs for link prediction is challenging due to data dependency. To this end, in this work we propose a differentially private link prediction (DPLP) framework, building upon subgraph-based GNNs. DPLP includes a DP-compliant subgraph extraction module as its core component. We first propose a neighborhood subgraph extraction method, and carefully analyze its data dependency level. To reduce this dependency, we optimize DPLP by integrating a novel path subgraph extraction method, which alleviates the utility loss in GNNs by reducing the noise sensitivity. Theoretical analysis demonstrates that our approaches achieve a good balance between privacy protection and prediction accuracy, even when using GNNs with few layers. We extensively evaluate our approaches on benchmark datasets and show that they can learn accurate privacy-preserving GNNs and outperforms the existing methods for link prediction.

A cohesive subgraph of k-truss requires that each edge has at least$(k-2)$triangles, which has wide applications of modeling social communities and complex network visualization. Recently, the study of truss maximization has gained attention, which aims to enlarge$k$-truss most by inserting$b$new edges into a graph$G$. However, existing maximization methods suffer from a stiff strategy of complete truss conversion, that is either converting the whole$(k-1)$-truss component to k-truss or converting no edge to k-truss without using any budget. To tackle this bottleneck, we develop a novel partial conversion strategy to explore more insertion plans. Based on partial conversion strategy, we revisit the problem of truss maximization in this paper and propose adaptive solutions by achieving more new k-truss edges. Specifically, we first decompose all$(k-1)$-truss into a series of disjoint components via the triangle connectivity, where each component's conversion is independent to each other. Then, for each$(k-1)$-truss component, we explore possible insertion plans of partial conversions. An intuitive method is to randomly insert a budget no more than$b$new edges and check the expected profit of new$k$-truss edges. Obviously, this method is inefficient due to a large search space of edge insertions and many times of expensive$k$-truss verification. To improve it, we propose a new minimum-cut based approach, which converts a subgraph of$(k-1)$-truss component into a flow graph with weighted edges and finds a key of maximum-flow answer corresponding to a k-truss conversion plan with the minimum budget consumption. Next, we develop a new dynamic programming framework to find the best way to allocate the budget$b$to all components. We design two fast dynamic programming algorithms and analyze the complexities theoretically. In addition, we explore the case of a large given budget$b$and extend our techniques to handle the conversion of$(k-h)$-truss into$k$-truss for$2\leq h\leq k-2$. Extensive experiment results demonstrate the superiority of our algorithms against the state-of-the-art methods.

Community search is a query-dependent graph task to find communities containing a given set of query vertices, which is useful for personalized search and recommendation. Recently, community search over multilayer networks has gained attention thanks to its strong ability to capture cross-layer relationships among diverse entities from multiple domains. This brings significant advantages against the classical studies of community search over only single-layer graphs. However, most existing multilayer community models suffer from two major limitations: 1) failure to identify informative communities with the most layers when a multilayer graph is associated with a large number of layers; 2) missing to distinguish the degree of connections in internal layers and cross-layers. To tackle the above limitations, this paper proposes a novel multilayer subgraph model called$(k, d)$-core. A$(k,d)$-core based community requires that every two layers have enough$k$internal layer connections and$d$cross-layer connections for each vertex in this community. We formulate the problem of multilayer community search (MCS-problem), which finds a$(k,d)$-core connected subgraph$H$containing query vertices to achieve the largest number of cross-layers. For cross-layer connectivity, we consider two-fold definitions of full-layer and path-layer connectivities. First, we consider a strong definition of full-layer connectivity, which constrains that every two layers are connected in$H$. We show that the MCS-problem under full-layer connectivity is NP-hard. We propose two methods of exact exploration and heuristic search for finding M CS answers. Second, to improve the efficiency of community search, we further study a relaxation of path-layer connectivity, allowing two layers to be connected via a path of immediate layers. Then, we develop a fast search algorithm to identify path-layer-based communities and then refine them to full-layer answers. Furthermore, we develop a novel$(k,d){-}$core index that effectively captures essential$(k,d)$-core structure, including the neighborhood information, the layer connectivities, and the internal/cross-layer corenesses. Extensive experiments on nine real-world multilayer graphs demonstrate the effectiveness and efficiency of our M CS model and algorithms.

Community search aims to retrieve dense subgraphs that contain the query vertices. While many effective community models and algorithms have been proposed in the literature, none of them address the unique challenges posed by streaming graphs, where edges are continuously generated over time. In this paper, we investigate the problem of truss-based community search over streaming directed graphs. To address this problem, we first present a peeling-based algorithm that iteratively removes edges that do not meet the support constraints. To improve the efficiency of the peeling-based algorithm, we propose three optimizations that leverage the time information of the streaming graph and the structural information of trusses. As the peeling-based algorithm may suffer from inefficiency when the input peeling graph is large, we further propose a novel order-based algorithm that preserves the community by maintaining the deletion order of edges in the peeling algorithm. Extensive experimental results on real-world datasets show that our proposed algorithms outperform the baseline by up to two orders of magnitude in terms of throughput.

Interactive graph search (IGS) over DAGs aims to find a hidden target by asking interactive questions as few as possible. IGS is useful for many applications, e.g., facilitating supervised learning tasks by harnessing labeled data, image categorization, and product classification. However, most of the existing IGS methods only work for either single target search on DAGs or multiple targets search on simple trees. To overcome the gap, it motivates us to study a challenging and yet not solved problem of multiple targets search over DAGs. We analyze the new problem in-depth and propose a key concept of uncertain candidates. Based on it, we design an effective gain function to determine the best vertex to be asked questions and shrink the search space of potential targets greatly. Leveraging our uncertain candidates and gain function, we develop a unified k-EIS framework to search both single target and multiple targets. We analyze all algorithm complexities and theoretically show that our solution can significantly improve existing DFS-tree-based methods by asking O ( n ) questions to O (log 2 n ) questions in worst cases. To further improve IGS for multiple targets, we propose an advanced solution by dividing the whole DAG into k disjoint subgraphs with single targets and then tackling each subgraph one by one independently. Extensive experiments on real-world datasets validate that our proposed k-EIS framework can save lots of questions to search exact targets against four state-of-the-art IGS competitors.

In the heterogeneous information network (HIN), a motif-clique is a "complete graph" for a given motif (or a small connected graph) that could capture the desired relationship in the motif. The maximal motif-cliques of HINs have found various applications in community discovery, recommendation, and biological network analysis. The state-of-the-art algorithm for enumerating maximal motif-cliques may have to explore all possible subgraphs of a maximal motif-clique and check whether a maximal motif-clique has been enumerated at each recursive step, which is very time-consuming. To improve the efficiency of enumeration, in this paper, we develop efficient algorithms for maximal motif-clique enumeration over large HINs. We first introduce an order-based framework to avoid duplicated enumeration, which results in lower time complexity compared to the existing algorithm. We then propose a pivot-based pruning strategy, which significantly reduces the search space. We further optimize the process of identifying the candidate sets and locating the subgraphs containing the maximal motif-cliques. Extensive experiments on five real-world HINs demonstrate that our proposed algorithm achieves high efficiency and is up to three orders of magnitude faster than the state-of-the-art algorithm.

Due to the unstructuredness and the lack of schemas of graphs, such as knowledge graphs, social networks, and RDF graphs, keyword search for querying such graphs has been proposed. As graphs have become voluminous, large-scale distributed processing has attracted much interest from the database research community. While there have been several distributed systems, distributed querying techniques for keyword search are still limited. This paper proposes a novel distributed keyword search system called$\mathsf {DKWS}$. First, we present amonotonicproperty with keyword search algorithms that guarantees correct parallelization. Second, we present a keyword search algorithm as monotonic backward and forward search phases. Moreover, we propose new tight bounds for pruning nodes being searched. Third, we propose anotify-pushparadigm and$\mathsf {PINE}$programming modelof$\mathsf {DKWS}$. The notify-push paradigm allowsasynchronouslyexchanging the upper bounds of matches across the workers and the coordinator in$\mathsf {DKWS}$. The$\mathsf {PINE}$programming model naturally fits keyword search algorithms, as they have distinguished phases, to allowpreemptivesearches to mitigate staleness in a distributed system. Finally, we investigate the performance and effectiveness of$\mathsf {DKWS}$through experiments using real-world datasets. We find that$\mathsf {DKWS}$is up to two orders of magnitude faster than related techniques, and its communication costs are 7.6 times smaller than those of other techniques.

(α, β)-core is an important cohesive subgraph model for bipartite graphs. Given a bipartite graph G, the problem of (α, β)-core decomposition is to compute non-empty (α, β)-cores for all possible values of α and β. The state-of-the-art (α, β)-core decomposition algorithm is a peeling-based algorithm, which iteratively deletes the vertex from high degree to low degree. However, as the peeling-based algorithm is designed for centralized environments, it cannot be applied to distributed environments, where graphs are partitioned and stored in different machines. Motivated by this, in this paper, we study the distributed (α, β)-core decomposition problem, aiming to develop new algorithms to support (α, β)-core decomposition in distributed environments. To this end, first, we analyze the local properties of (α, β)-core, and devise n-order Bi-indexes for the vertex, which are iteratively defined using the vertex neighbors’ (n − 1)-order Bi-indexes. Next, we propose an algorithm for (α, β)-core decomposition through iteratively calculating n-order Bi-indexes for every vertex. To further improve the efficiency of the algorithm, we propose two optimizations. Then, we extend our proposed algorithms to different distributed graph processing frameworks to make them run in distributed environments. Finally, extensive experimental results on both real and synthetic bipartite graphs demonstrate the efficiency of our proposed algorithms.

Socially tenuous groups (or simply tenuous groups) in a social network/graph refer to subgraphs with few social interactions and weak relationships among members. However, existing studies on tenuous group queries do not consider the user profiles (keywords) of the members whereas in many social network applications, e.g., finding reviewers for paper selection and recommending seed users in social advertising, keywords also need to be considered. Thus, in this paper, we investigate the problem of keywords-based socially tenous group (KTG) queries. A KTG query is to find top N tenuous groups in which the members of each group jointly cover the most number of query keywords. To address the KTG problem, we first propose two exact algorithms, namely KTG-VKC and KTG-VKC-DEG, which give priority to the valid keyword coverage and the combination of valid keyword coverage and degree, respectively, to select members to form a feasible group by adopting a branch and bound (BB) strategy. Moreover, we propose keyword pruning and k-line filtering to accelerate the algorithms. To yield diversified KTG results, we also study the problem of diversified keywords-based socially tenous group (DKTG) queries. To deal with the DKTG problem, we propose a DKTG-Greedy algorithm by exploiting a greedy heuristic in combination with KTG-VKC-DEG. Furthermore, we design two alternative indexes, namely NL and NLRNL, to efficiently check whether the social distance of any two members is greater than the social constraint k in the above algorithms. We conduct extensive experiments using real datasets to validate our ideas and evaluate the proposed algorithms. Experimental results show that the NLRNL index achieves a better performance than the NL index.

K-truss is a useful notion of dense subgraphs, which can represent cohesive parts of a graph in a hierarchical way. In practice, in order to enable various truss-based applications to answer queries faster, the edge trussnesses are computed in advance. However, real-world graphs may not always be static and often have edges inserted or removed, leading to costly truss maintenance of recomputing all edge trussnesses. In this paper, we focus on dynamic graphs with star insertions/deletions, where a star insertion can represent a newly joined user with friend connections in social networks or a recently published paper with cited references in citation networks. To tackle such star-based truss maintenance, we propose a new structure of AffBall based on the local structure of an inserted/deleted star motif. With AffBall, we make use of the correlation of inserted edges to compute the trussnesses of the inner edges surrounding the star. Then, we analyze the onion layer of k-truss and conduct truss maintenance for the edges beyond the star, which can be efficiently achieved with a time complexity related to the number of the edges that change the onion layer. Moreover, we extend star-based truss maintenance to handle general updates and single-edge insertions/deletions. Extensive experiments on real-world dynamic graphs verify the effectiveness and efficiency of proposed algorithms against state-of-the-art truss maintenance algorithms.

Community detection is an important topic in network analysis, and recently many community detection methods have been developed on top of the Nonnegative Matrix Factorization (NMF) technique. Most NMF-based community detection methods only utilize the first-order proximity information in the adjacency matrix, which has some limitations. Besides, many NMF-based community detection methods involve sparse regularizations to promote clearer community memberships. However, in most of these regularizations, different nodes are treated equally, which seems unreasonable. To dismiss the above limitations, this article proposes a community detection method based on node centrality under the framework of NMF. Specifically, we design a new similarity measure which considers the proximity of higher-order neighbors to form a more informative graph regularization mechanism, so as to better refine the detected communities. Besides, we introduce the node centrality and Gini impurity to measure the importance of nodes and sparseness of the community memberships, respectively. Then, we propose a novel sparse regularization mechanism which forces nodes with higher node centrality to have smaller Gini impurity. Extensive experimental results on a variety of real-world networks show the superior performance of the proposed method over thirteen state-of-the-art methods.

The COVID-19 pandemic has caused the society lockdowns and a large number of deaths in many countries. Potential transmission cluster discovery is to find all suspected users with infections, which is greatly needed to fast discover virus transmission chains so as to prevent an outbreak of COVID-19 as early as possible. In this article, we study the problem of potential transmission cluster discovery based on the spatio-temporal logs. Given a query of patient user q and a timestamp of confirmed infection t q , the problem is to find all potential infected users who have close social contacts to user q before time t q . We motivate and formulate the potential transmission cluster model, equipped with a detailed analysis of transmission cluster property and particular model usability. To identify potential clusters, one straightforward method is to compute all close contacts on-the-fly, which is simple but inefficient caused by scanning spatio-temporal logs many times. To accelerate the efficiency, we propose two indexing algorithms by constructing a multigraph index and an advanced BCG-index. Leveraging two well-designed techniques of spatio-temporal compression and graph partition on bipartite contact graphs, our BCG-index approach achieves a good balance of index construction and online query processing to fast discover potential transmission cluster. We theoretically analyze and compare the algorithm complexity of three proposed approaches. Extensive experiments on real-world check-in datasets and COVID-19 confirmed cases in the United States validate the effectiveness and efficiency of our potential transmission cluster model and algorithms.

Recommender system provides personalized suggestions based on users' interests and social connections. However, most existing social recommendation models utilize social relationships in a direct manner, i.e., they only consider the user-user connections, neglecting the clustering nature of social networks. As social information recursively spreads in the social network, the community structure, which contains richer information in contrast to pure user-user relationships, would emerge. To dismiss these limitations, in this paper, we propose a unified recommendation framework named Simultaneous Community detection and Singular Value Decomposition (SCSVD), which utilizes the underlying community structure to regularize user latent preferences. We propose a well-designed iterative optimization algorithm to tackle social recommendation efficiently. In addition, we theoretically analyze the proposed algorithm in terms of convergence, time complexity, and also the unified process of community detection and user embedding learning. Extensive experiments are conducted on three benchmark real-world datasets of product reviews, demonstrating the effectiveness, robustness, and flexibility of SCSVD in both rating prediction and top-N recommendation tasks, compared to fifteen state-of-the-art approaches.

City express delivery services (a.k.a.~last-mile delivery) have become more prominent in recent years. Many logistics giants, such as Amazon, JD, and Cainiao, have deployed intelligent express delivery systems to deal with the growing demand for parcel delivery. Existing works adopt queuing or batch processing approaches to assign parcels to couriers. However, these approaches do not fully consider the distribution of parcels and couriers, leading to poor quality of task assignment. In this paper, we investigate a problem of delivery matching based on revenue maximization in real-time city express delivery services. Given a set of couriers and a stream of parcel collection tasks, our problem aims to assign each collection task to a suitable courier to maximize the overall revenue of the platform. The problem is shown to be NP-hard. To tackle the problem efficiently, we present a time-aware batch matching algorithm to offer high-quality courier-task matching in each sliding window. We further theoretically analyze the matching approximation bound. In addition, we propose an efficient deep reinforcement learning-based approach to adaptively determine the sliding window size for better matching results. Finally, extensive experiments demonstrate that our proposed algorithms can achieve desirable effectiveness and efficiency under a wide range of parameter settings.

Data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., gene ontology, disease ontology, to name a few. In this paper, we study the weighted tree summarization. We motivate and formulate our${\mathsf {kWTS}}$-${\mathsf {problem}}$as selecting a diverse set of$k$nodes tosummarize a hierarchicaltree$T$withweighted terminologies. We first propose an efficient greedy tree summarization algorithm${\mathsf {GTS}}$. It solves the problem with$(1-1/e)$-approximation guarantee. Although${\mathsf {GTS}}$achieves quality-guaranteed answers approximately, but it is still not optimal. To tackle the problem optimally, we further develop a dynamic programming algorithm${\mathsf {OTS}}$to obtain optimal answers for${\mathsf {kWTS}}$-${\mathsf {problem}}$in$O(nhk^3)$time, where$n, h$are the node size and height in tree$T$. The algorithm complexity and correctness of${\mathsf {OTS}}$are theoretically analyzed. In addition, we propose a useful optimization technique of tree reduction to remove useless nodes with zero weights and shrink the tree into a smaller one, which ensures the efficiency acceleration of both${\mathsf {GTS}}$and${\mathsf {OTS}}$in real-world datasets. Moreover, we illustrate one useful application of graph visualization based on the answer of$k$-sized tree summarization and show it in a novel case study. Extensive experimental results on real-world datasets show the effectiveness and efficiency of our proposed approximate and optimal algorithms for tree summarization. Furthermore, we conduct a usability evaluation of attractive topic recommendation on ACM Computing Classification System dataset to validate the usefulness of our model and algorithms.

Geo-social groupqueries, which return a social cohesive user group with a spatial constraint, have receive significant research interests due to their promising applications for group-based activity planning and scheduling in location-based social networks (LBSNs). However, existing studies on geo-social group queries mostly assume the users are stationary whereas in realistic LBSN application scenarios all users may continuously move over time. Thus, in this paper, we investigate the problem ofcontinuousgeo-socialgroupsmonitoring(CGSGM) over moving users. A challenge in answering CGSGM queries over moving users is how to efficiently update geo-social groups when users are continuously moving. To address the CGSGM problem, we first propose a baseline algorithm, namelyBaseline-BB, which recomputes the new geo-social groups from scratch at each time instance by utilizing a branch and bound (BB) strategy. To improve the inefficiency of BB, we explore a new strategy, called common neighbor or neighbor expanding (CNNE), which expands the common neighbors of edges or the neighbors of users in intermediate groups to quickly produce the valid group combinations. Accordingly, another baseline algorithm, namelyBaseline-CNNE, is proposed. As these baseline algorithms do not maintain intermediate results to facilitate further query processing, we develop an incremental algorithm, calledincremental monitoring algorithm (IMA), which maintains the support, common neighbors and the neighbors of current users when exploring possible user groups for further updates and query processing. Since IMA requires many times of truss decomposition when processing mutiple-users updates, we propose an improved incremental algorithm, calledimproved incremental monitoring algorithm (IIMA), which performs truss decompostion only once. Moreover, we design algorithms for handling the social changes that result in insertion/deletion of some edges in the social network. Owing to the challenge in setting, an appropriate monitoring distance, we further study the top$N$CGSGM problem, which finds top$N$result groups at each time instance. Finally, we conduct extensive experiments using four real datasets to validate our ideas and evaluate the proposed algorithms.

Social recommendation aims at improving recommendation performance by incorporating social information. Most existing social recommender systems only utilize the one-hop interpersonal social information, neglecting the community structure emerged in social networks, which may contain additional conducive information. In this paper, we propose a unified Simultaneous Community detection and Singular Value Decomposition (SCSVD) framework for community-aware social recommendation. An efficient optimization algorithm is also derived to optimize SCSVD, with an analysis of convergence and computational complexity. Comprehensive experimental results on three real-world benchmark datasets demonstrate the effectiveness of SCSVD, over both traditional matrix factorization based recommendation models and advanced neural network based recommendation models.

Recently a lot of research works have focused on geo-social group queries for group-based activity planning and scheduling in location-based social networks (LBSNs), which return a social cohesive user group with a spatial constraint. However, existing studies on geo-social group queries assume the users are stationary whereas in real LBSN applications all users may continuously move over time. Thus, in this paper we in-vestigate the problem of continuous geo-social groups monitoring (CGSGM) over moving users. A challenge in answering CGSGM queries over moving users is how to efficiently update geo-social groups when users are continuously moving. To address the CGSGM problem, we first propose a baseline algorithm, namely Baseline-BB, which recomputes the new geo-social groups from scratch at each time instance by utilizing a branch and bound (BB) strategy. To improve the inefficiency of BB, we propose a new strategy, called common neighbor or neighbor expanding (CNNE), which expands the common neighbors of edges or the neighbors of users in intermediate groups to quickly produce the valid group combinations. Based on CNNE, we propose another baseline algorithm, namely Baseline-CNNE. As these baseline algorithms do not maintain any intermediate results to facilitate further query processing, we develop an incremental algorithm, called incremental monitoring algorithm (IMA), which maintains the support, common neighbors and the neighbors of current users when exploring possible user groups for further updates and query processing. Finally, we conduct extensive experiments using three real datasets to validate our ideas and evaluate the proposed algorithms,

Given one or more query vertices, Community Search (CS) aims to find densely intra-connected and loosely inter-connected structures containing query vertices. Attributed Community Search (ACS), a related problem, is more challenging since it finds communities with both cohesive structures and homogeneous vertex attributes. However, most methods for the CS task rely on inflexible pre-defined structures and studies for ACS treat each attribute independently. Moreover, the most popular ACS strategies decompose ACS into two separate sub-problems, i.e., the CS task and subsequent attribute filtering task. However, in real-world graphs, the community structure and the vertex attributes are closely correlated to each other. This correlation is vital for the ACS problem. In this vein, we argue that the separation strategy cannot fully capture the correlation between structure and attributes simultaneously and it would compromise the final performance. In this paper, we propose Graph Neural Network (GNN) models for both CS and ACS problems, i.e., Query Driven-GNN (QD-GNN) and Attributed Query Driven-GNN (AQD-GNN). In QD-GNN, we combine the local query-dependent structure and global graph embedding. In order to extend QD-GNN to handle attributes, we model vertex attributes as a bipartite graph and capture the relation between attributes by constructing GNNs on this bipartite graph. With a Feature Fusion operator, AQD-GNN processes the structure and attribute simultaneously and predicts communities according to each attributed query. Experiments on real-world graphs with ground-truth communities demonstrate that the proposed models outperform existing CS and ACS algorithms in terms of both efficiency and effectiveness. More recently, an interactive setting for CS is proposed that allows users to adjust the predicted communities. We further verify our approaches under the interactive setting and extend to the attributed context. Our method achieves 2.37% and 6.29% improvements in F1-score than the state-of-the-art model without attributes and with attributes respectively.

Given a directed graph G and integers k and l , a D-core is the maximal subgraph H ⊆ G such that for every vertex of H , its in-degree and out-degree are no smaller than k and l , respectively. For a directed graph G , the problem of D-core decomposition aims to compute the non-empty D-cores for all possible values of k and l. In the literature, several peeling-based algorithms have been proposed to handle D-core decomposition. However, the peeling-based algorithms that work in a sequential fashion and require global graph information during processing are mainly designed for centralized settings, which cannot handle large-scale graphs efficiently in distributed settings. Motivated by this, we study the distributed D-core decomposition problem in this paper. We start by defining a concept called anchored coreness , based on which we propose a new H-index-based algorithm for distributed D-core decomposition. Furthermore, we devise a novel concept, namely skyline coreness , and show that the D-core decomposition problem is equivalent to the computation of skyline corenesses for all vertices. We design an efficient D-index to compute the skyline corenesses distributedly. We implement the proposed algorithms under both vertex-centric and block-centric distributed graph processing frameworks. Moreover, we theoretically analyze the algorithm and message complexities. Extensive experiments on large real-world graphs with billions of edges demonstrate the efficiency of the proposed algorithms in terms of both the running time and communication overhead.

Core maximization, that enlarges the k -core as much as possible by inserting a few new edges into a graph, is particularly useful for social group engagement and network stability improvement. However, the core maximization problem has been theoretically proven to be NP-hard even APX-hard for k ≥ 3. Existing heuristic approaches suffer from the limitation of inefficiency on large graphs. To address this limitation, in this paper, we revisit this challenging yet important problem of core maximization, that is, given a graph G , a number k , and a budget b , to insert b new edges into G such that the corresponding k -core is maximized. We propose a novel algorithm FastCM+ based on several fast search strategies. The core idea is to apply graph partition to divide ( k - 1)-shell into different components. Then, FastCM+ considers each ( k - 1)-shell component independently to convert different layered vertices into k -core, in two manners of completely and partially. Based on the complete/partial conversions, FastCM+ is generalized to further handle ( k - λ)-shell conversions for 2 ≤λ k . Leveraging dynamic programming combinations of different components' potential answers, FastCM+ finds a good-quality answer for edge insertions. Experimental results on eleven datasets demonstrate that our algorithm runs much faster than state-of-the-art methods on large graphs meanwhile achieving better answers.

Social decisions made by individuals are easily influenced by information from their social neighborhoods. A key predictor of social contagion is the multiplicity of social contexts inside the individual’s contact neighborhood, which is termed structural diversity. However, the existing models have limited decomposability for analyzing large-scale networks, and suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to overcome the weak decomposability. Based on this model, we study a novel problem of truss-based structural diversity search in a graph$G$, that is, to find the$r$vertices with the highest truss-based structural diversity and return their social contexts. To tackle this problem, we propose an online structural diversity search algorithm in$O(\rho (m+\mathcal {T}))$time, where$\rho$,$m$, and$\mathcal {T}$are respectively the arboricity, the number of edges, and the number of triangles in$G$. To improve the efficiency, we design an elegant and compact index, called TSD-index, which keeps the structural diversity information for all individual vertices. We further optimize the structure of TSD-index into a highly compressed GCT-index. Our GCT-index-based structural diversity search utilizes the global triangle information for fast index construction and finds answers in$O(m)$time. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.

Cohesive substructure identification is one fundamental task of graph analytics. Recently, a useful problem of dense subgraph maximization has attracted significant attentions, which aims at enlarging a dense subgraph pattern using a few new edge insertions, e.g., k-core maximization. As a more cohesive subgraph of k-core, k-truss requires that each edge has at least k-2 triangles within this subgraph. However, the problem of k-truss maximization has not been studied yet. In this paper, we motivate and formulate a new problem of budget-constrained k-truss maximization. Given a budget of b edges and an integer k≥2, the problem is to find and insert b new edges into a graph G such that the resulted k-truss of G is maximized. We theoretically prove the NP-hardness of k-truss maximization problem. To efficiently tackle it, we analyze non-submodular property of k-truss newcomers function and develop non-conventional heuristic strategies for edge insertions. We first identify high-quality candidate edges with regard to (k-1)-light subgraphs and propose a greedy algorithm using per-edge insertion. Besides further improving the efficiency by pruning disqualified candidate edges, we finally develop a component-based dynamic programming algorithm for enlarging k-truss mostly, which makes a balance of budget assignment and inserts multiple edges simultaneously into all (k-1)-light components. Extensive experiments on nine real-world graphs demonstrate the efficiency and effectiveness of our proposed methods.

Structural diversity, the multiplicity of social contexts inside an individual's contact neighborhood, is shown to play an important role in the social contagion process. Existing models have limited decomposability for analyzing large-scale networks, which may suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to address the limitations. We study the problem of top-r structural diversity search to find r vertices with the largest truss-based structural diversity scores in a graph. We propose two novel index structures of TSD-index and GCT-index, and efficient index-based query processing algorithms to solve the problem. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.

Networks in many real-world applications come with an inherent uncertainty in their structure, due to e.g., noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs has attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role.

Community search aims at finding densely connected subgraphs for query vertices in a graph. While this task has been studied widely in the literature, most of the existing works only focus on finding homogeneous communities rather than heterogeneous communities with different labels. In this paper, we motivate a new problem of cross-group community search, namely Butterfly-Core Community (BCC), over a labeled graph, where each vertex has a label indicating its properties and an edge between two vertices indicates their cross relationship. Specifically, for two query vertices with different labels, we aim to find a densely connected cross community that contains two query vertices and consists of butterfly networks, where each wing of the butterflies is induced by a k-core search based on one query vertex and two wings are connected by these butterflies. We first develop a heuristic algorithm achieving 2-approximation to the optimal solution. Furthermore, we design fast techniques of query distance computations, leader pair identifications, and index-based BCC local explorations. Extensive experiments on seven real datasets and four useful case studies validate the effectiveness and efficiency of our BCC and its multi-labeled extension models.

Interactive graph search leverages human intelligence to categorize target labels in a hierarchy, which is useful for image classification, product categorization, and database search. However, many existing interactive graph search studies aim at identifying a single target optimally, and suffer from the limitations of asking too many questions and not being able to handle multiple targets. To address these two limitations, in this paper, we study a new problem of budget constrained interactive graph search for multiple targets called kBM-IGS problem. Specifically, given a set of multiple targets T in a hierarchy and two parameters k and b , the goal is to identify a k -sized set of selections S , such that the closeness between selections S and targets T is as small as possible, by asking at most a budget of b questions. We theoretically analyze the updating rules and design a penalty function to capture the closeness between selections and targets. To tackle the kBM-IGS problem, we develop a novel framework to ask questions using the best vertex with the largest expected gain, which provides a balanced trade-off between target probability and benefit gain. Based on the kBM-IGS framework, we first propose an efficient algorithm STBIS to handle the SingleTarget problem, which is a special case of kBM-IGS. Then, we propose a dynamic programming based method kBM-DP to tackle the MultipleTargets problem. To further improve efficiency, we propose two heuristic but efficient algorithms, kBM-Topk and kBM-DP+. Experiments on large real-world datasets with ground-truths verify both the effectiveness and efficiency of our algorithms.

Directed acyclic graph (DAG) is an essentially important model to represent terminologies and their hierarchical relationships, such as Disease Ontology. Due to massive terminologies and complex structures in a large DAG, it is challenging to summarize the whole hierarchical DAG.

As an online, query-dependent variant of the well-known community detection problem, community search has been studied for years to find communities containing the query vertices. Along with the generation of graphs with rich attribute information, attributed community search has attracted increasing interest recently, aiming to select communities where vertices are cohesively connected and share homogeneous attributes. However, existing community models may include cut-edges/vertices and thus cannot well guarantee the strong connectivity required by a cohesive community. In this paper, we propose a new cohesive attributed community (CAC) model that can ensure both structure cohesiveness and attribute cohesiveness of communities. Specifically, for a query with vertex vq and keyword set S, we aim to find the cohesively connected communities containing vq with the most shared keywords in S. It is nontrivial as we need to explore all possible subsets of S to verify the existence of structure cohesive communities until we find the communities with the most common keywords. To tackle this problem, we make efforts in two aspects. The first is to reduce the candidate keyword subsets. We achieve this by exploring the anti-monotonicity and neighborhood-constraint properties of our CAC model so that we can filter out the unpromising keyword subsets. The second is to speed up the verification process for each candidate keyword subset. We propose two indexes TIndex and MTIndex to reduce the size of the candidate subgraph before the verification. Moreover, we derive two new properties based on these indexes to reduce the candidate keyword subsets further. We conducted extensive experimental studies on four real-world graphs and validated the effectiveness and efficiency of our approaches.

Due to the unstructuredness and the lack of schemas of graphs, such as knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public- private networks has not yet been studied. For example, query answers on private networks and on a combination of private and public networks can be different. In this paper, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. Since there have been plenty of keyword search semantics, we select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that spans through them.

Attributed community search aims to find the community with strong structure and attribute cohesiveness from attributed graphs. However, existing works suffer from two major limitations: (i) it is not easy to set the conditions on query attributes; (ii) the queries support only a single type of attributes. To make up for these deficiencies, in this paper, we study a novel attributed community search called vertex-centric attributed community (VAC) search. Given an attributed graph and a query vertex set, the VAC search returns the community which is densely connected (ensured by the k-truss model) and has the best attribute score. We show that the problem is NP-hard. To answer the VAC search, we develop both exact and approximate algorithms. Specifically, we develop two exact algorithms. One searches the community in a depth-first manner and the other is in a best-first manner. We also propose a set of heuristic strategies to prune the unqualified search space by exploiting the structure and attribute properties. In addition, to further improve the search efficiency, we propose a 2-approximation algorithm. Comprehensive experimental studies on various realworld attributed graphs demonstrate the effectiveness of the proposed model and the efficiency of the developed algorithms.

Community search enables personalized community discovery and has wide applications in large real-world graphs. While community search has been extensively studied for undirected graphs, the problem for directed graphs has received attention only recently. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time. To address the limitations, in this paper, we systematically study the problem of community search over large directed graphs. We start by presenting a novel community model, called D-truss, based on two distinct types of directed triangles, i.e., flow triangle and cycle triangle. The D-truss model brings nice structural and computational properties and has many advantages in comparison with the existing models. With this new model, we then formulate the D-truss community search problem, which is proved to be NP-hard. In view of its hardness, we propose two efficient 2-approximation algorithms, named Global and Local, that run in polynomial time yet with quality guarantee. To further improve the efficiency of the algorithms, we devise an indexing method based on D-truss decomposition. Consequently, the D-truss community search can be solved upon the D-truss index without time-consuming accesses to the original graph. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.

We are pleased to present a special issue of Data Science and Engineering (DSE), which contains a collection of five papers from the WISE 2019 conference, and two regular submission papers.The International Conference on Web Information Systems Engineering (WISE) has established itself as a community aiming at high-quality research and offering the ground for advancing efforts in topics related to Web information systems.WISE 2019 focuses on research, development, and applications in relation to Web information systems, including a wide range of topics, such as blockchain, deep learning, machine learning, recommender systems, data mining, Web-based applications, graph learning, knowledge graphs, graph mining, text mining, and crowdsourcing.WISE 2019 was held in Hong Kong, China, during January 19-21, 2020.WISE 2019 attracted a total of 211 research paper submissions.The conference program committee selected 50 full research papers (with an acceptance rate of 23.7%), five demonstration papers, and three tutorial papers to be presented at the conference and published in the proceedings [1,2].The conference program also included keynote presentations by

Hierarchical directed acyclic graph (HDAG) is an essential graph model to represent terminology relationships in a hierarchy, such as Disease Ontology, Gene Ontology, and Wikipedia. However, due to massive terminologies and complex structures in a HDAG, an end user might feel difficult to explore and summarize the whole graph, which is practically useful but less studied in the literature. In this demo, we develop an interactive system of HDAG-Explorer to help users summarize HDAG with highly important and diverse vertices. Our HDAG-Explorer system exhibits several useful features including summarized visualization, interactive exploration, and structural statistics report. All these features facilitate in-depth understanding of the HDAG data. We showcase the usability of the HDAG-Explorer through two real-world applications of summarized topic recommendation and visual data exploration.

Finding semantic communities using network topology and contents together is a hot topic in community detection. Existing methods often use word attributes in an indiscriminate way to help finding communities. Through analysis we find that, words in networked contents often embody a hierarchical semantic structure. Some words reflect a background topic of the whole network with all communities, some imply the high-level general topic covering several topic-related communities, and some imply the high-resolution specialized topic to describe each community. Ignoring such semantic structures often leads to defects in depicting networked contents where deep semantics are not fully utilized. To solve this problem, we propose a new Bayesian probabilistic model. By distinguishing words from either a background topic or some two-level topics (i.e., general and specialized topics), this model not only better utilizes the networked contents to help finding communities, but also provides a clearer multiplex semantic community interpretation. We then give an efficient variational algorithm for model inference. The superiority of this new approach is demonstrated by comparing with ten state-of-the-art methods on nine real networks and an artificial benchmark. A case study is further provided to show its strong ability in deep semantic interpretation of communities.

Community search that finds only the communities pertaining to the query input has been widely studied from simple graphs to attributed graphs. However, a significant limitation of previous studies is that they all require the input of query nodes, which makes it difficult for users to specify exact queries if they are unfamiliar with the queried graph. To address this issue, in this paper we study a novel problem of keyword-centric community search (KCCS) over attributed graphs. In contrast to prior studies, no query nodes, but only query keywords, need to be specified to discover relevant communities. Specifically, given an attributed graph G, a query Q consisting of query keywords WQ, and an integer k, KCCS serves to find the largest subgraph of k-core of G that achieves the strongest keyword closeness w.r.t. WQ. We design a new function of keyword closeness and propose efficient algorithms to solve the KCCS problem. Furthermore, a novel core-based inverted index is developed to optimize performance. Extensive experiments on large real networks demonstrate that our solutions are more than three times faster than the baseline approach, and can find cohesive communities closely related to the query keywords.

Given a query vertex in a graph, the task of community search is to find all meaningful communities containing the query vertex in an online manner. In this demonstration, we propose a novel query processing system for searching and visualizing communities in graphs, called VizCS. It exhibits three key innovative features. First, VizCS adopts several community models and supports community search on dynamic graphs where nodes/edges undergo frequently insertions/deletions. Second, VizCS offers a user-friendly visual interface to formulate queries and a real-time response query processing engine. Last but not least, VizCS generates a community exploration wall by offering interactive community visualization, which facilitates users to in-depth understanding of the data. Furthermore, VizCS becomes a community search platform that can visualize and compare different community results by various state-of-the-art algorithms and user-uploaded approaches.

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.

Data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., the international classification of Diseases-9, Medical Subject Heading, and Gene Ontology, to name a few. In this paper, we study the problem of selecting a diverse set of k elements to summarize an input dataset with hierarchical terminologies, and visualize the summary in an ontology structure. We propose an efficient greedy algorithm to solve the problem with (1-1/e)≈ 62%-approximation guarantee. Preliminary experimental results on real-world datasets show the effectiveness and efficiency of the proposed algorithm for data summarization.

Communities serve as basic structures for understanding the organization of many real-world networks, such as social, biological, collaboration, and communication networks. Recently, community search over large graphs has attracted significantly increasing attention, from simple and static graphs to evolving, attributed, location-based graphs. Different from the well-studied problem of community detection that finds all communities in an entire network, community search is to find the cohesive communities w.r.t. the query nodes. In this tutorial, we survey the state-of-the-art of community search on various kinds of networks across different application areas such as densely-connected community search, attributed community search, social circle discovery, and querying geosocial groups. We first highlight the challenges posed by the community search problems. We continue the presentation of their principles, methodologies, algorithms, and applications, and give a comprehensive comparison of the state-of-the-art techniques. This tutorial finally concludes by offering future directions for research in this important and growing area.

Recently, community search over graphs has gained significant interest. In applications such as analysis of protein-protein interaction (PPI) networks, citation graphs, and collaboration networks, nodes tend to have attributes. Unfortunately, most previous community search algorithms ignore attributes and result in communities with poor cohesion w.r.t. their node attributes. In this paper, we study the problem of attribute-driven community search, that is, given an undirected graph G where nodes are associated with attributes, and an input query Q consisting of nodes V q and attributes W q , find the communities containing V q , in which most community members are densely inter-connected and have similar attributes. We formulate this problem as finding attributed truss communities (ATC), i.e., finding connected and close k-truss subgraphs containing V q , with the largest attribute relevance score. We design a framework of desirable properties that good score function should satisfy. We show that the problem is NP-hard. However, we develop an efficient greedy algorithmic framework to iteratively remove nodes with the least popular attributes, and shrink the graph into an ATC. In addition, we also build an elegant index to maintain k -truss structure and attribute information, and propose efficient query processing algorithms. Extensive experiments on large real-world networks with ground-truth communities show that our algorithms significantly outperform the state of the art and demonstrates their efficiency and effectiveness.

A key operation in network analysis is the discovery of cohesive subgraphs. The notion of $k$-truss has gained considerable popularity in this regard, based on its rich structure and efficient computability. However, many complex networks such as social, biological and communication networks feature uncertainty, best modeled using probabilities. Unfortunately the problem of discovering k-trusses in probabilistic graphs has received little attention to date. In this paper, given a probabilistic graph G, number k and parameter γ --(0,1], we define a (k,γ)-truss as a maximal connected subgraph H ⊆ G, in which for each edge, the probability that it is contained in at least (k-2) triangles is at least γ. We develop an efficient dynamic programming algorithm for decomposing a probabilistic graph into such maximal (k,γ)-trusses. The above definition of a (k,γ)-truss is local in that the "witness" graphs that has the (k-2) triangles containing an edge in H may be quite different for distinct edges. Hence, we also propose: a global (k,γ)-truss, which in addition to being a local (k,γ)-truss, has to satisfy the condition that the probability that H contains a k-truss is at least γ. We show that unlike local (k,γ)-trusses, the global (k,γ)-truss decomposition on a probabilistic graph is intractable. We propose a novel sampling technique which enables approximate discovery of global (k,γ)-trusses with high probability. Our extensive experiments on real datasets demonstrate the efficacy of our proposed approach and the usefulness of local and global (k,γ)-truss.

Recently, there has been significant interest in the study of the community search problem in social and information networks: given one or more query nodes, find densely connected communities containing the query nodes. However, most existing studies do not address the "free rider" issue, that is, nodes far away from query nodes and irrelevant to them are included in the detected community. Some state-of-the-art models have attempted to address this issue, but not only are their formulated problems NP-hard, they do not admit any approximations without restrictive assumptions, which may not always hold in practice. In this paper, given an undirected graph G and a set of query nodes Q , we study community search using the k -truss based community model. We formulate our problem of finding a closest truss community (CTC), as finding a connected k -truss subgraph with the largest k that contains Q , and has the minimum diameter among such subgraphs. We prove this problem is NP-hard. Furthermore, it is NP-hard to approximate the problem within a factor (2-ε), for any ε > 0. However, we develop a greedy algorithmic framework, which first finds a CTC containing Q , and then iteratively removes the furthest nodes from Q , from the graph. The method achieves 2-approximation to the optimal solution. To further improve the efficiency, we make use of a compact truss index and develop efficient algorithms for k -truss identification and maintenance as nodes get eliminated. In addition, using bulk deletion optimization and local exploration strategies, we propose two more efficient algorithms. One of them trades some approximation quality for efficiency while the other is a very efficient heuristic. Extensive experiments on 6 real-world networks show the effectiveness and efficiency of our community model and search algorithms.

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.

Community detection which discovers densely connected structures in a network has been studied a lot. In this paper, we study online community search which is practically useful but less studied in the literature. Given a query vertex in a graph, the problem is to find meaningful communities that the vertex belongs to in an online manner. We propose a novel community model based on the k-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of k-truss communities with a linear cost with respect to the community size. In addition, we investigate the k-truss community search problem in a dynamic graph setting with frequent insertions and deletions of graph vertices and edges. Extensive experiments on large real-world networks demonstrate the effectiveness and efficiency of our community model and search algorithms.

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.

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.