With growing demands for data privacy and model robustness, graph unlearning (GU), which erases the influence of specific data on trained GNN models, has gained significant attention. However, existing exact unlearning methods suffer from either low efficiency or poor model performance. While more utility-preserving and efficient, current approximate methods require access to the forget set during unlearning, which makes them inapplicable in immediate deletion scenarios, thereby undermining privacy. Additionally, these approximate methods, which attempt to directly perturb model parameters, still raise significant concerns regarding unlearning power in empirical studies. To fill the gap, we propose Transferable Condensation Graph Unlearning (TCGU), a data-centric solution to graph unlearning. Specifically, we first develop a two-level alignment strategy to pre-condense the original graph into a compact yet utility-preserving dataset for subsequent unlearning tasks. Upon receiving an unlearning request, we fine-tune the pre-condensed data with a low-rank plugin, to directly align its distribution with the remaining graph, thus efficiently revoking the information of deleted data without accessing them. A novel similarity distribution matching approach and a discrimination regularizer are proposed to effectively transfer condensed data and preserve its utility in GNN training, respectively. Finally, we retrain the GNN on the transferred condensed data. Extensive experiments on 7 benchmark datasets demonstrate that TCGU can achieve superior performance in terms of model utility, unlearning efficiency, and unlearning efficacy compared to existing GU methods. To the best of our knowledge, this is the first study to explore graph unlearning with immediate data removal using a data-centric approximate method.

With the rapid growth of online social networks, strengthening their stability has emerged as a key research focus. This study aims to identify influential relationships that significantly impact community stability. In this paper, we introduce and explore the anchor trussness reinforcement problem to reinforce the overall user engagement of networks by anchoring some edges. Specifically, for a given graph$G$and a budget$b$, we aim to identify$b$edges whose anchoring maximizes the trussness gain, which is the cumulative increment of trussness across all edges in$G$. We establish the NP-hardness of the problem. To address this problem, we introduce a greedy framework that iteratively selects the current best edge. To scale for larger networks, we first propose an upward-route method to constrain potential trussness increment edges. Augmented with a support check strategy, this approach enables the efficient computation of the trussness gain for anchoring one edge. Then, we design a classification tree structure to minimize redundant computations in each iteration by organizing edges based on their trussness. We conduct extensive experiments on 8 real-world networks to validate the efficiency and effectiveness of the proposed model and methods.

Interactions between two entities often occur at specific timestamps, which can be modeled as a temporal graph. Exploring the relationships between vertices based on temporal paths is one of the fundamental tasks. In this paper, we conduct the first research to propose and investigate the problem of generating the temporal simple path graph (tspG), which is the subgraph consisting of all temporal simple paths from the source vertex to the target vertex within the given time interval. Directly enumerating all temporal simple paths and constructing the tspG is computationally expensive. To accelerate the processing, we propose an efficient method named Verification in Upper-bound Graph. It first incorporates the temporal path constraint and simple path constraint to exclude unpromising edges from the original graph, which obtains a tight upper-bound graph as a high-quality approximation of the tspG in polynomial time. Then, an Escape Edges Verification algorithm is further applied in the upper-bound graph to construct the exact tspG without exhaustively enumerating all temporal simple paths between given vertices. Finally, comprehensive experiments on 10 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques.

Influence maximization (IM) aims to identify a small set of influential users to maximize the information spread. It has been widely applied in the context of viral marketing, where a company distributes incentives to a few influencers to promote the product. However, in practical scenarios, not all users hold equal importance and certain users need to be prioritized for the specific requirements. Motivated by this, recently, a variant problem of IM, called influence maximization with priority (IMP), has been proposed. Given a graph G=(V,E), a priority set P ⊆ V and a threshold T ∈ [0, |P|], IMP aims to identify a set of k nodes (termed seeds ) to maximize the expected number of activated nodes in G while satisfying that the expected number of activated nodes in~P is no less than the given threshold. Nevertheless, we show that existing solutions for IMP are inferior in maximizing the influence spread in G, and can only offer poor approximation ratios in many cases. To address these limitations, in this paper, we first propose a novel framework named SAR with both superior effectiveness and strong theoretical guarantees. In addition, to obtain more practical results, we study the IMP problem under the adaptive setting, where the seeds are iteratively selected after observing the diffusion result of the previous seeds. We design an effective method AAS that achieves expected approximation guarantees. Extensive experiments demonstrate that, compared with the state-of-the-art method, SAR achieves up to 22.3% larger spread and ås achieves up to 42.6% larger spread, with both exhibiting a higher approximation ratio.

Abstract In the rapidly advancing field of graph-based applications, accurate graph similarity computing (GSC) has become increasingly important. However, due to the complexity of graph structures, this task remains a challenge because of the intricate calculations involved. To solve the limitations of existing works, this paper introduces the Interpretable Graph Fusion Model (), a novel framework designed to enhance the accuracy and efficiency of graph similarity computation. Specifically, our model can fully utilize graph structure information and comprehensively assess graph similarity at both fine-grained and coarse-grained levels, ultimately achieving more accurate predictions. Experimented extensively across four real-world datasets, demonstrates a significant improvement over existing SOTA methods to solve the GSC challenge. In numerous experimental tests, our model shows performance improvements in terms of MSE (Mean Squared Error), ranging from 4.66% to as much as 56.92% compared to the second-best method.

Community detection is a fundamental problem and has been extensively studied. With the abundance of information in real-world networks, the discovery of communities in attribute graphs is increasingly valuable. However, numerous previous models in attribute graphs neglect the fairness concept, which plays an important role in ensuring that graph analysis is not biased toward specific groups. In this paper, we propose a novel model, named proportional fair clique (PFC). Specifically, given an attribute graph G = (V, E, A), an integer k and a threshold λ ∊ [0, 1/|A|], a subgraph S of G is a PFC if (i) S is a clique with size at least k and (ii) |Sai |/|S| ≥ λ for each attribute ai in G, where Sai is the node set in S associated with attribute ai. We show that the problem of enumerating all the maximal proportional fair cliques (MPFC) is NP-hard. A reasonable baseline algorithm is first presented by extending the BronKerbosch framework. To scale for large networks, we propose several optimization strategies to accelerate the computation. Finally, comprehensive experiments are conducted over 6 graphs to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Hypergraphs provide a more flexible representation for group interactions in complex systems compared to ordinary graphs, where each hyperedge can connect any number of nodes. In practice, data modeled as hypergraphs often contain hyperedge importance values, which indicate the influence or popularity of the group collaborations. For example, in a co-authorship hypergraph, a paper (hyperedge) is co-authored by multiple authors (nodes). The number of citations a paper receives can be regarded as the importance value of its corresponding hyperedge, reflecting its academic influence and significance.

Supergraph search is a fundamental graph query processing problem. Supergraph search aims to find all data graphs contained in a given query graph based on the subgraph isomorphism. In other words, the goal is to determine if part of the query graph is the same as a smaller data graph. Existing algorithms construct the indices and adopt the filtering-and-verification framework, which is usually computationally expensive and can cause redundant computations. Recently, various learning-based methods have been proposed for a good trade-off between accuracy and efficiency for query processing tasks. However, to our knowledge, no learning-based method is proposed for the supergraph search task. In this paper, we propose the first learning-based method for similarity search on supergraph containment, named Neural Supergraph similarity Search (NSS). NSS first learns the representations for query and data graphs and then efficiently conducts the supergraph search on the representation space, the complexity of which is linear to the number of data graphs. The carefully designed Wasserstein discriminator and reconstruction network enable NSS to capture better the interrelation, structural and label information between and within the query and data graphs. Experiments demonstrate that the NSS is up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in query processing and is more accurate than the other learning-based solutions.

As a popular data structure, bipartite graph is widely used to model the complex relationships between two types of entities widely in many real world application domains[1]. Detecting cohesive subgraphs, such as biclique, is a fundamental problem in graph analysis[2], [3]. Given a bipartite graph$G$, a subgraph$B=(X,\ Y)$is a biclique if$B$is a complete subgraph.

Influence Maximization (IM) has promising applications in social network marketing and has been extensively researched over the past years. However, previous IM studies mainly focus on ordinary graphs rather than hypergraphs, where edges cannot accurately describe group interactions or relationships. To model group interactions, we investigate the IM problem on hypergraphs under the Susceptible–Infected spreading model with Contact Process dynamics (SICP) in this paper. In this paper, we proposed a probability distribution-based method, called Multi-hop Influence Estimation (MIE), which can accurately estimate the rank of influence expectation of nodes, to solve the IM problem on hypergraphs. Specifically, we compute the influence score for each node through a constrained Depth First Search (DFS) under a probability model, and then select seed node according to the influence score. In addition, by analysing the characteristics of the influence diffusion model, we find that the influence of a node is significantly related to its neighbourhood structure. Based on the observation, we propose a term named neighbourhood coefficient to describe the neighbourhood structure of a node. Further, an efficient and effective method, called Adaptive Neighbourhood Coefficient Algorithm (Adeff), is proposed to solve the IM problem on hypergraphs. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our proposed methods. Compared with the state-of-the-art approach, our proposed methods can achieve up to 450% improvement in terms of effectiveness.

Finding bicliques is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph$G$and two positive integers$\tau _{U}, \tau _{V}$, a subgraph$S=(U_{S},V_{S},E_{S})$of$G$is a balanced signed biclique if$i)$$S$is a biclique without any unstable motif, i.e., unbalanced butterfly, and$ii)$$|U_{S}| \geq \tau _{U}$and$|V_{S}| \geq \tau _{V}$. In this paper, we propose and investigate two important problems, i.e., maximal balanced signed biclique enumeration and maximum balanced signed biclique identification. Due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problems directly. For the enumeration task, to construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for large networks, optimized strategies are proposed to overcome the three limitations in the baseline method. For the identification task, we first propose a baseline method by leveraging the proposed enumeration framework. Moreover, employing novel optimizations, an anchor balanced bipartite graph based search framework is introduced to accelerate the search. Finally, extensive experiments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of the proposed techniques and model.

Supergraph search is a fundamental graph query processing problem. Supergraph search aims to find all data graphs contained in a given query graph based on the subgraph isomorphism. Existing algorithms construct the indices and adopt thefiltering-and-verificationframework which is usually computationally expensive and can cause redundant computations. Recently, various learning-based methods have been proposed for a good trade-off between accuracy and efficiency for query processing tasks. However, to the best of our knowledge, there is no learning-based method proposed for the supergraph search task. In this paper, we propose the first learning-based method for similarity search on supergraph containment, named Neural Supergraph similarity Search (NSS).NSSfirst learns the representations for query and data graphs and then efficiently conducts the supergraph search on the representation space whose complexity is linear to the number of data graphs. The carefully designed Wasserstein discriminator and reconstruction network enableNSSto better capture the interrelation, structural and label information between and within the query and data graphs. Experiments demonstrate that theNSSis up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in terms of query processing and more accurate compared to the other learning-based solutions.

k-peak is a well-regarded cohesive subgraph model in graph analysis. However, the k-peak model only considers the direct neighbors of a vertex, consequently limiting its capacity to uncover higher-order structural information of the graph. To address this limitation, we propose a new model in this paper, named (k,h)-peak, which incorporates higher-order (h-hops) neighborhood information of vertices. Employing the (k,h)-peak model, we explore the higher-order peak decomposition problem that calculates the vertex peakness for all conceivable k values given a particular h. To tackle this problem efficiently, we propose an advanced local computation based algorithm, which is parallelizable, and additionally, devise novel pruning strategies to mitigate unnecessary computation. Experiments as well as case studies are conducted on real-world datasets to evaluate the efficiency and effectiveness of our proposed solutions.

Maximum biclique identification, which aims to find the biclique with the largest size, can find a wide spectrum of applications in different domains, such as E-Commerce, healthcare and bioinformatics. However, the previous studies mainly focus on unsigned bipartite graphs. The signed information naturally exists in real applications, such as like and dislike. The neglect of signed information may fail to discover the inherent properties of networks. In this paper, we propose a novel model, named signed (k,l)-biclique (SKLB), by enforcing constraints over the number of positive and negative connections. Specifically, given a signed bipartite graph and two positive integers k,l, SKLB is a biclique, where each vertex has no less than k positive neighbors and no more than l negative neighbors. We prove the problem of finding the maximum signed (k,l)-biclique (MaxSKLB) is NP-hard. Moreover, we show that the problem is still NP-hard, even if the input graph is a biclique itself. A baseline algorithm is first presented through biclique enumeration, which tries to find the MaxSKLB for each encountered biclique and return the largest one. However, considering that the extraction of MaxSKLB from a biclique is still NP-hard, a greedy strategy is developed to accelerate the processing with competitive result. Furthermore, to efficiently handle large graphs, we optimize the algorithm from different perspectives, including unnecessary search branches and unpromising vertices filtering. Finally, comprehensive experiments are conducted over 10 graphs to validate the efficiency and effectiveness of proposed techniques and model.

The maximum clique problem, which is to find the clique with the largest size, can find many real-world applications and is notable for its capability of modeling many combinatorial problems. However, most existing research focuses on processing unsigned graphs, i.e., treat each connection equally. In real applications, edges of graphs are usually associated with signed information, i.e., positive or negative edges, and signed graph analysis has attracted great attentions in the recent. In this paper, we first analyze the disadvantages of existing signed clique models, and then propose a novel clique model, named signed$\theta$-clique. Given a signed graph$G$and a subgraph$S$, let$d^{+}_{S}(u)$and$d^{-}_{S}(u)$be the number of positive and negative neighbors of vertex$u$in$S$. We say a subgraph$S$is a signed$\theta$-clique if$i)$$S$is a clique and$ii)$each vertex$u$in$S$fulfills$d^{+}_{S}(u) - d^{-}_{S}(u) \geq \theta$. We show that the problem of identifying the maximum signed$\theta$-clique is NP-hard. Novel pruning techniques are proposed to reduce the searching space. In addition, efficient searching strategies are developed to scale for large graphs. Comprehensive experiments on 8 real-world datasets are conducted to demonstrate the effectiveness and efficiency of the proposed approaches.

In social networks, dense relationships among users contribute to stable communities. Breakdowns of critical connections may cause users to leave the group. A popular model to measure the cohesiveness of a network is k-core or coreness. To identify important connections, in this paper, we propose and investigate the problem of k-core minimization problem under three different metrics. Specifically, given a graph G and a budget b, we aim to retrieve a set B of b edges for deletion purpose, which can minimize i) the number of nodes in the collapsed k-core (KNM), ii) the number of edges in the collapsed k-core (KEM), and iii) the overall coreness decreased in the target node set P (KCM). We first formally define the problems and prove that the three problems are all NP-hard. Then, a baseline greedy searching framework is developed. To scale for large graphs, optimized algorithms are developed by integrating novel pruning strategies and group-based structures. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed models and methods.

Uncertain graphs have been widely used to model complex linked data in many applications, such as guaranteed-loan networks and power grids. In these networks, a node usually has a certain chance of default due to self-factors or the influence from upstream nodes. For regulatory authorities, it is critical to efficiently identify the vulnerable nodes, i.e., nodes with high default risks, such that they could pay more attention to these nodes for the purpose of risk management. In this paper, we propose and investigate the top-k vulnerable nodes detection problem in uncertain graphs. We formally define the model and prove it hardness. A sampling-based approach is first proposed. Rigorous theoretical analysis is conducted to bound the quality of returned results. Novel optimization techniques and a bottom-k sketch based approach are further developed to scale for large networks. We demonstrate the performance of proposed techniques on 3 real financial networks and 5 benchmark networks. Moreover, to further verify the advantages of our model, we integrate the proposed techniques with our loan risk control system, which is deployed in the collaborated bank. Particularly, we show that our proposed model can better estimate the default risks of enterprises compared to the state-of-the-art techniques.

Clique, as a fundamental model for graph analysis, is widely investigated in the literature. However, with the emergence of various graph data, such as signed graph, novel clique model is desired to better capture the cohesiveness within these graphs. Different from unsigned graphs, where only one type of edge exists, in signed graphs, nodes can be connected either positively or negatively (e.g., friend or enemy). In this article, we propose a novel clique model, called signed$k$-clique, which aims to find cohesive subgraphs in signed networks based on the classic clique model and balance theory. Given a signed graph$G$, an induced subgraph$S$is a signed$k$-clique if$|S| \geq k$and$S$is a clique without any unbalanced triangle. Moreover, we propose and investigate two fundamental problems, i.e., maximal signed$k$-clique enumeration and maximum signed$k$-clique identification, both of which are shown to be NP-hard. For maximal signed$k$-clique enumeration, novel balance graph based search framework and optimization techniques are proposed to eliminate the limitations in the developed baseline. For maximum signed$k$-clique identification, different upper bound based techniques are developed to early terminate the search. Furthermore, the support of finding top-$\gamma$results is also discussed. Finally, comprehensive experiments on seven real-world datasets are conducted to demonstrate the efficiency and effectiveness of the proposed techniques. Compared with the baseline, the optimized algorithm can achieve up to four orders of magnitude speedup.

Bipartite graphs are widely used to capture the relationships between two types of entities. In bipartite graph analysis, finding the maximum balanced biclique (MBB) is an important problem with numerous applications. A biclique is balanced if its two disjoint vertex sets are of equal size. However, in real-world scenarios, each vertex is associated with a weight to denote its properties, such as influence, i.e., weighted bipartite graph. For weighted bipartite graphs, the previous studies for MBB are no longer applicable due to the ignorance of weight. To fill the gap, in this paper, we propose a reasonable definition of “balance” by restricting the weight difference between two sides of a biclique within$k$. Given a weighted bipartite graph$G$and a constraint$k$, we aim to find the maximum$k$-balanced biclique (Max$k$BB) with the maximum weight. To address the problem, we first propose an approach based on biclique enumeration on single side of$G$following the Branch-and-Bound framework. To improve the performance, we further devise three optimization strategies to prune invalid search branches. Moreover, we utilize graph reduction strategy to reduce the redundant search space. Extensive experiments are conducted on 12 real bipartite datasets to demonstrate the efficiency, effectiveness and scalability of our proposed algorithms. The experimental results show that our algorithms can address MBB detection problem efficiently, and the case study demonstrates the effectiveness of our model compared with MBB model.

The reachability query is a fundamental problem in graph analysis. Recently, many studies focus on label-constraint reachability queries, which tries to verify whether two vertices are reachable under a given label set. However, in many real-life applications, it is more practical to find the minimum label set required to ensure the reachability of two vertices, which is neglected by previous research. To fill the gap, in this paper, we propose and investigate the minimum reachable label set (MRLS) problem in edge-labeled graphs. Specifically, given an edge-labeled graph and two vertices s, t, the MRLS problem aims to find a label set L with the minimum size such that s can reach t through L. We prove the hardness of our problem, and develop different optimization strategies to improve the scalability of the algorithms. Extensive experiments on 6 datasets demonstrate the advantages of the proposed algorithms.

Maximum clique identification is a fundamental problem for many domains. In real-world applications, signed information, e.g., friend and enemy, naturally exists in graphs. However, most existing research focuses on unsigned graph analysis. In this paper, we propose a new clique model for signed graphs, named signed$\theta$-clique. We show that the problem of identifying the maximum signed$\theta$-clique is NP-hard. To scale for large signed graphs, novel pruning rules and search strategies are developed. Extensive experiments are conducted on 8 real-world graphs to verify the advantages of proposed model and techniques.

Uncertain graphs have been widely used to model complex linked data in many applications, such as guaranteed-loan networks and power grids. In these networks, a node usually has a certain chance of default due to self-factors or the influence from upstream nodes. For regulatory authorities, it is critical to efficiently and accurately identify the vulnerable nodes, i.e., nodes with high default risk, such that people could pay more attention to these nodes for the purpose of risk management. In this paper, we propose and investigate the top-k vulnerable nodes detection problem in uncertain graphs. Due to the hardness of the problem, sampling-based methods are proposed with tight theoretical guarantee. We demonstrate the performance of proposed techniques on 3 real financial networks and 5 benchmark networks.

Community detection is a fundamental problem in graph analysis, while most existing research focuses on unsigned graphs. In many applications, networks involve both positive and negative connections. It is important to exploit the signed information to identify more stable communities. In this paper, we propose a novel model, named stable k-core, to measure the stability of a community in signed graphs by leveraging the concept of balance theory. We show that the problem of finding the maximum stable k-core is NP-hard. Advanced approaches are proposed to accelerate the processing. Experiments on 6 signed networks are conducted to verify the efficiency and effectiveness of proposed model and techniques.

Maximal biclique enumeration is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, in this paper, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph$G$, two positive integers$\tau_{U}, \tau_{V}$, a subgraph$S=(U_{S},\ V_{S},\ E_{S})$of$G$is a balanced signed biclique if$i$)$S$is a biclique without any unstable motif, i.e., unbalanced butterfly, and ii)$\vert U_{S}\vert \geq\tau_{U}$and$\vert V_{S}\vert \geq\tau_{V}$. In this paper, we aim to enumerate all the maximal balanced signed bicliques, which is proved to be NP-hard. Moreover, due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problem directly. To construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for larger networks, novel optimized strategies are proposed to overcome the three limitations in the baseline method. Extensive experi-ments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of proposed techniques and model. Compared with the baseline approach, the optimized algorithm can achieve up to 3 orders of magnitude speedup.

Community detection is one of the most fundamental problems in social network analysis, while most existing research focuses on unsigned graphs. In real applications, social networks involve not only positive relationships but also negative ones. It is important to exploit the signed information to identify more stable communities. In this paper, we propose a novel model, named stable$k$-core, to measure the stability of a community in signed graphs. The stable$k$-core model not only emphasizes user engagement, but also eliminates unstable structures. We show that the problem of finding the maximum stable$k$-core is NP-hard. To scale for large graphs, novel pruning strategies and searching methods are proposed. We conduct extensive experiments on 6 real-world signed networks to verify the efficiency and effectiveness of proposed model and techniques.

With the development of the Internet and the continuous expansion of social networks, more and more people use location-based services for data sharing. As a classic model for studying social networks, k-core is widely used for capturing the cohesive subgraphs and community identification. Due to the large number of spatial data growing rapidly and its complicated attributes, we recognize the characteristics of the spatial data effectively by using the spatial k-core model. Spatial k-core is one that can clearly reflect the clustering of spatial cohesive subgraphs. For two vertices in the spatial k-core, their pair-wise distance is less than or equal to a given threshold, and each of the degree of the vertex at least equals to k. In order to scale for large spatial datasets, in this paper, a quadtree-based algorithm and a bound-based algorithm are proposed and developed by integrating novel pruning strategies. Finally, we conducted 5 reallife datasets on the new pruning algorithm to verify the efficiency and effectiveness of proposed techniques.

Abstract Community search, which aims to retrieve important communities (i.e., subgraphs) for a given query vertex, has been widely studied in the literature. In the recent, plenty of research is conducted to detect influential communities, where each vertex in the network is associated with an influence value. Nevertheless, there is a paucity of work that can support personalized requirement. In this paper, we propose a new problem, i.e., maximal personalized influential community search. Given a graph G, an integer k and a query vertex u, we aim to obtain the most influential community for u by leveraging the k-core concept. To handle larger networks efficiently, two algorithms, i.e., top-down algorithm and bottom-up algorithm, are developed. In real-life applications, there may be a lot of queries issued. Therefore, an optimal index-based approach is proposed in order to meet the online requirement. In many scenarios, users may want to find multiple communities for a given query. Thus, we further extend the proposed techniques for the top-r case, i.e., retrieving r communities with the largest influence value for a given query. Finally, we conduct extensive experiments on 6 real-world networks to demonstrate the advantage of proposed techniques.

Mining cohesive subgraphs is a fundamental problem in social network analysis. The k-truss model has been widely used to measure the cohesiveness of subgraphs. Most existing studies about k-truss focus on unsigned graphs. However, in real applications, the edges in the networks can be either positive or negative, e.g., friend or foe relationships, which represents more information than unsigned networks. Therefore, the traditional k-truss model is not applicable for the signed networks. Motivated by this, in this paper, we propose a novel model, named signed (k,r)-truss, which leverages the property of balanced triangle in singed network analysis. Specifically, a signed (k,r)-truss is a subgraph where each edge has no less than k balanced support and no more than r unbalanced support. We prove that the problem of identifying the maximum signed (k,r)-truss is NP-hard. Due to the hardness of the problem, we tend to the heuristic strategies. A trivial algorithm is first presented. Then, two greedy algorithms are developed to enhance the processing. Finally, we conduct comprehensive experiments on real-world signed networks to verify the performance of proposed techniques.

Community detection is a fundamental problem in social network analysis, and most existing studies focus on unsigned graphs, i.e., treating all relationships as positive. However, friend and foe relationships naturally exist in many real-world applications. Ignoring the signed information may lead to unstable communities. To better describe the communities, we propose a novel model, named signed k-truss, which leverages the properties of k-truss and balanced triangle. We prove that the problem of identifying the maximum signed k-truss is NP-hard. To deal with large graphs, novel pruning strategies and algorithms are developed. Finally, we conduct comprehensive experiments on real-world signed networks to evaluate the performance of proposed techniques.

Community search is a fundamental problem in social network analysis. In this paper, we propose a novel problem, called influential maximum connected community (IMCC) search, which leverages the k-ECC model to measure the cohesiveness of subgraphs and tries to find the influential community for a set of query vertices.

In real-world applications, bipartite graphs are widely used to model the relationships between two types of entities, such as customer-product relationship, gene co-expression, etc. As a fundamental problem, cohesive subgraph detection is of great importance for bipartite graph analysis. In this paper, we propose a novel cohesive subgraph model, named (α, β, ω)-core, which requires each node should have sufficient number of close neighbors. The model emphasizes both the engagement of entities and the strength of connections. To scale for large networks, efficient algorithm is developed to compute the (α, β, ω)-core. Compared with the existing cohesive subgraph models, we conduct the experiments over real-world bipartite graphs to verify the advantages of proposed model and techniques.

Bipartite graphs are widely used when modeling the relationships between two different types of entities, such as purchase relationships. In a bipartite graph, the number of butterflies, i.e., 2 × 2 biclique, is a fundamental metric for analyzing the structures and properties of bipartite graphs. Considering the deletion of critical nodes may affect the stability of bipartite graphs, we propose the butterfly minimization problem, where the attacker aims to maximize the number of butterflies removed from the graph by deleting b nodes. We prove the problem is NP-hard, and the objective function is monotonic and submodular. We adopt a greedy algorithm to solve the problem with 1 − 1/e approximation ratio. To scale for large graphs, novel methods are developed to reduce the searching space. Experiments over real-world bipartite graphs are conducted to demonstrate the advantages of proposed techniques.

In order to reduce fuel consumption, many vehicles are equipped with idle start-stop systems. However, due to complex environment in the real world, vehicles with start-stop systems often experience short-term idling and frequent start-stops. It may greatly accelerate equipment deterioration hence reduce driving comfort. To resolve this problem, we propose SSVisual, an intelligent start-stop system by utilizing collected traffic information. Novel approaches are developed to effectively detect the states of traffic lights and traffic conditions based on image recognition techniques. Given the collected information, SSVisual can determine if it is necessary to shut down the engine at the current idle speed. Moreover, SSVisual can be used for both online and offline environments to visualize the performance of different strategies for research purpose.

With the increasing number of vehicles, the number of traffic accidents also increases, especially at traffic lights. To enhance the driving safety at traffic lights, in this paper, we propose an intelligent safe driving assistant to provide drivers with driving advice based on traffic light phases, which information has been neglected by existing research. The driving assistant consists of an image recognition system with a single on-board camera, which can ameliorate the difficulties of observing traffic light phases. The recognition system obtains traffic light countdown information using a Convolutional Neural Network, and estimates the countdown time using the results of traffic light information. In addition, we develop a model to calculate the distance between the traffic light and vehicle by using the information of camera and traffic light. Based on the traffic light phase and the distance obtained, the driving assistant can provide a velocity control strategy to improve driver's safety. Finally, extensive experiments are conducted to verify the effectiveness of proposed methods.

In social networks, dense relationships among users contribute to stable networks. Breakdowns of some relationships may cause users to leave the network hence decrease the network stability. A popular metric to measure the stability of a network is k-core, i.e., the maximal subgraph of a social network in which each node has at least k neighbors. In this paper, we propose a novel problem, called k-core minimization. Given a graph G, an integer k and a budget b, we aim to identify a set B of edges with size b, so that we can get the minimum k-core by deleting B from G. We first formally define the problem and prove its NP-hardness. Then a baseline greedy algorithm is proposed. To handle large graphs, an optimized algorithm, named KC-Edge, is developed by adopting novel pruning rules. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed methods.

Given a positive integer k, a social network G and a certain propagation model M, influence maximization aims to find a set of k nodes that has the largest influence spread. The state-of-the-art method IMM is based on the reverse influence sampling (RIS) framework. By using the martingale technique, it greatly outperforms the previous methods in efficiency. However, IMM still has limitations in scalability due to the high overhead of deciding a tight sample size. In this paper, instead of spending the effort on deciding a tight sample size, we present a novel bottomk sketch based RIS framework, namely BKRIS, which brings the order of samples into the RIS framework. By applying the sketch technique, we can derive early termination conditions to significantly accelerate the seed set selection procedure. Moreover, we provide several optimization techniques to reduce the cost of generating and processing samples. Finally, we conduct experiments over 10 real social networks to demonstrate the efficiency and effectiveness of the proposed method. Further details are reported in [1].

As a key problem in viral marketing, influence maximization has been extensively studied in the literature. Given a positive integer$k$, a social network$\mathcal {G}$and a certain propagation model, it aims to find a set of$k$nodes that have the largest influence spread. The state-of-the-art method IMM is based on the reverse influence sampling (RIS) framework. By using the martingale technique, it greatly outperforms the previous methods in efficiency. However, IMM still has limitations in scalability due to the high overhead of deciding a tight sample size. In this paper, instead of spending the effort on deciding a tight sample size, we present a novel bottom-ksketch based RIS framework, namely BKRIS, which brings the order of samples into the RIS framework. By applying the sketch technique, we can derive early termination conditions to significantly accelerate the seed set selection procedure. Moreover, we provide a cost-effective method to find a proper sample size to bound the quality of returned result. In addition, we provide several optimization techniques to reduce the cost of generating samples’ order and efficiently deal with the worst-case scenario. We demonstrate the efficiency and effectiveness of the proposed method over 10 real world datasets. Compared with the IMM approach, BKRIS can achieve up to two orders of magnitude speedup with almost the same influence spread. In the largest dataset with 1.8 billion edges, BKRIS can return 50 seeds in 1.3 seconds and return 5,000 seeds in 36.6 seconds. It takes IMM 55.32 second and 3,664.97 seconds, respectively.

There exists considerable literature on estimating the cardinality of set intersection result. In this paper, we consider a generalized problem for integer sets where, given a gap parameter δ, two elements are deemed as matches if their numeric difference equals δ or is within δ. We call this problem the gapped set intersection size estimation (GSISE/), and it can be used to model applications in database systems, data mining, and information retrieval. We first distinguish two subtypes of the estimation problem: the point gap estimation and range gap estimation. We propose optimized sketches to tackle the two problems efficiently and effectively with theoretical guarantees. We demonstrate the usage of our proposed techniques in mining top-K related keywords efficiently, by integrating with an inverted index. Finally, substantial experiments based on a large subset of the ClueWed09 dataset demonstrate the efficiency and effectiveness of the proposed methods.