Maximal cliques are useful in many applications, e.g., community detection, bioinformatics, anomaly detection and graph visualization. Enumerating maximal cliques from a graph is a computationally challenging problem, as the output size can be exponentially large with respect to the vertex number. Such a large number of cliques typically overlap heavily, which brings information redundancy when being applied to aforementioned domains. This paper studies how to use a small set of maximal cliques, i.e., a summary, to summarize all the maximal cliques in a graph. The state-of-the-art suffers from inefficiency in updating the summary with progressively generated cliques, especially when the summary grows large. In this work, we identify the challenge of summary updating to be how to efficiently estimate the overlap between cliques in the summary and each newly found maximal clique. By exploiting the vertex order information, we propose the notion of clique comparator, and devise four types of operators to quickly identify clique overlap in less costly manners. We conduct extensive experiments on six real-world datasets to verify the effectiveness of our approach, which reduces unnecessary clique intersection calculations by at least seven orders of magnitude and achieves a speedup of 2.5 ~3.1 times compared to the state-of-the-art.

The number of bicliques in a bipartite graph may grow exponentially as its vertices increase. A biclique summary is a subset of all maximal bicliques and can somehow represent all maximal bicliques. In practical application scenarios, a summary helps users obtain more representative results. Due to its compact size, it enables users to efficiently locate and select the information they need. For instance, in the biomedical field, when researchers explore relationships between genes and proteins, they are often faced with an excessive number of combinations. Using a summary of these gene-protein relationships not only provides more representative insights but also significantly reduces the time needed for analysis. To find such representative maximal bicliques faster, we propose a method to determine whether to terminate the current search by computing lower bounds. We begin by introducing a baseline method, MBS, followed by two algorithms that incorporate bound pruning: MBSL, a neighborhood-based search algorithm, and MBSc, an$(\alpha,\beta)$- core-based search algorithm. We also provide three strategies for optimizing the algorithms. They are the Upper Bound Deflation Pruning method, the Intersection Deflation Heuristic method, and the Lazy Lower Bound Evaluation method. Based on the above optimization strategies, we present the advanced algorithms MBSA and MBScA. In experiments, we demonstrate the efficiency and result quality of the proposed algorithms. After incorporating three optimization strategies, MBSA and MBScA show improvements in computation time compared to the baseline MBS and are able to generate smaller summaries.

The k-plex model, which allows each vertex to miss connections with up to$k$neighbors, serves as a relaxation of the clique model. Its adaptability makes it more suitable for analyzing graphs from real-world applications, where noise and imperfect data are common and the stringent clique model is often impractical. The challenge of identifying maximum k-plex (MKP, an NP-hard problem) is gaining attention in fields such as social network analysis, community detection, terrorist network identification, and graph clustering. Recent research efforts have focused on optimizing the time complexity of MKP algorithms. The state-of-the-art has reduced the complexity from a trivial$O^{*}(2^{n})$to$O^{*}(c_{k}^{n})$, with$c_{k} > 1.94$for$k$> 3, where$n$denotes the number of vertices. In this paper, we demonstrate that MKP can be solved in$O^{*}(1.42^{n})$and propose the first two quantum algorithms, qTKP and qMKP, to achieve this complexity. qTKP employs quantum search integrated with graph encoding, degree count, degree comparison, and size determination to find a k-plex of a given size; qMKP uses a binary search to progressively identify the maximum solution. To validate the practical performance and effectiveness of our algorithms, proof-of-principle experiments were conducted using the latest IBM quantum simulator currently available. This work holds potential to be applied to a wide range of clique relaxations, e.g., n-clan and n-club.

The Graph Neural Networks (GNNs) model is a powerful tool for integrating node information with graph topology to learn representations and make predictions. However, the complex graph structure of GNNs has led to a lack of clear explainability in the decision-making process. Recently, there has been a growing interest in seeking instance-level explanations of the GNNs model, which aims to uncover the decision-making process of the GNNs model and provide insights into how it arrives at its final output. Previous works have focused on finding a set of weights (masks) for edges/nodes/node features to determine their importance. These works have adopted a regularization term and a hyperparameter K to control the explanation size during the training process and keep only the top-K weights as the explanation set. However, the true size of the explanation is typically unknown to users, making it difficult to provide reasonable values for the regularization term and K. In this work, we propose a novel framework AMExplainer which leverages the concept of adversarial networks to achieve a dual optimization objective in the target function. This approach ensures both accurate prediction of the mask and sparsity of the explanation set. In addition, we devise a novel scaling function to automatically sense and amplify the weights of the informative part of the graph, which filters out insignificant edges/nodes/node features for expediting the convergence of the solution during training. Our extensive experiments show that AMExplainer yields a more compelling explanation by generating a sparse set of masks while simultaneously maintaining fidelity.

Maximal clique, the most cohesive structure in a graph, has a broad range of applications, e.g., community detection, bioinformatics, anomaly detection, and graph visualization. However, the sheer number of maximal cliques brings the challenge to fully examine them all. In addition, the omnipresent overlaps between cliques imply that it may not be necessary to process every maximal clique, since many vertices are shared in multiple cliques. A real example is that, in commercial advertising, a small group of individuals who participate in different communities can help spread an advertisement across all the communities. Inspired by this observation, we study the problem of finding a τ-cover, which is a subset of vertices in a graph. This subset overlaps with each maximal clique by no less than τ, where τ is a threshold reflecting the user's requirement. We prove the NP-hardness and the non-submodularity of finding a minimum τ-cover. As a result, to find a small τ-cover as best effort, we propose three methods: MCCb, MCC, and EMCC. MCCb is a baseline that adds vertices into the cover while doing clique enumeration until the coverage requirement is satisfied. MCC decides whether to add a vertex with more caution by evaluating the increment of coverage lower bound with O(1) time complexity. EMCC is a randomized algorithm built on an elegant adaptive sampling, which further achieves cover conciseness by relaxing the coverage requirement in a statistical manner. Extensive experiments show that MCC (1.3 ∽ 2.5 × faster) produces a cover whose size is 1/2 of MCCb, and EMCC (2 ∽ 5 × faster) averagely produces a cover whose size is one order of magnitude smaller vs. MCCb.

The number of maximal cliques could be exponentially large with respect to the number of vertices. A clique summary is a subset of all the maximal cliques and can somehow represent all the maximal cliques. Finding such a summary is deemed important in information distribution, influence estimation, cost-effective marketing, etc. The existing approach that finds a maximal clique summary suffers from long running time due to the excessive number of costly bound calculations that are used to estimate the size of to-be-found cliques during the enumeration process. Furthermore, we found that, sometimes, the bound calculation is not necessary at all. As a result, in order to provide the best study of the problem, we propose four strategies in two directions to speed up the process of finding a maximal clique summary by (1) restricting the bound calculation operation to a particular subset of all search branches and (2) making the best use of the bounds that have been previously calculated. Extensive experiments are conducted on eight real-world datasets to validate our strategies. Results demonstrate that the proposed method can reduce the number of bound calculations by 3 ~ 5 orders of magnitude, and each run of our algorithm can be up to 2.x times faster than the state-of-the-art algorithm while still keeping the summary concise. Our method can potentially benefit other large-output enumeration based problems, such as frequent itemset mining, when a summary of results is needed.

Maximal clique enumeration (MCE) is a fundamental problem in graph theory and is used in many applications, such as social network analysis, bioinformatics, intelligent agent systems, cyber security. Most existing MCE algorithms focus on improving the efficiency rather than reducing the size of the output, which could consist of a large number of maximal cliques. In this paper, we study how to report a summary of less overlapping maximal cliques. The problem was studied before, however, after examining the pioneer approach, we consider it still not satisfactory. To advance the research along this line, this paper attempts to make two contributions: (a) We propose a more effective sampling strategy, which produces a much smaller summary but still ensures that the summary can somehow witness all the maximal cliques and the expectation of each maximal clique witnessed by the summary is above a predefined threshold. (b) To verify experimentally, we tested ten real benchmark datasets that have a variety of graph characteristics. The results show that our new sampling strategy consistently outperforms the state-of-the-art method by producing smaller summaries and running faster on all the datasets.