In this paper, we study the problem of maximal biclique enumeration on large uncertain bipartite graphs. Given an uncertain bipartite graph $\mathcal{G}=(U,V,E,p)$ , a probability threshold $\tau$ , and two size constraints $\alpha$ and $\beta$ , we aim to efficiently enumerate all maximal $\tau$ -bicliques in $\mathcal{G}$ , where a maximal $\tau$ -biclique $B(L,R)$ is a complete subgraph of $\mathcal{G}$ with (1) the probability of B is no less than $\tau$ , (2) $|L| \ge \alpha$ and $|R| \ge \beta$ , and (3) $B$ is a maximal complete subgraph satisfying (1) and (2). This problem has many applications, such as biclustering of gene expression data, fraud detection, similar group identification, etc. Despite the wide range of applications, to the best of our knowledge, we note that there are no efficient and scalable solutions to this problem in the literature. This problem is computationally challenging due to its #P-completeness. In this paper, we propose a competitive branch-and-bound method, namely MBEN, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of MBEN, we propose several novel and efficient search processing optimizations. First, we always select the side with fewer candidates to expand the search space. With this search strategy, we have a chance to prune the fruitless branches early. Second, we devise an advanced pruning technique by considering the size pruning and probability pruning at the same time to boost the pruning capacity. Last, we implement MBEN with pre-allocated arrays and pointer maintaining techniques such that the frequent work sets creating operations can be substituted by array element switching operations. In addition, we introduce useful graph reduction techniques to further accelerate the computation. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by more than two orders of magnitude.

As an essential technique for Graph Contrastive Learning (GCL), Graph Augmentation (GA) improves the generalization capability of the GCLs by introducing different forms of the same graph. To ensure information integrity, existing GA strategies have been designed to simultaneously process the two types of information available in graphs: node attributes and graph topology. Nonetheless, these strategies tend to augment the two types of graph information separately, ignoring their correlation, resulting in limited representation ability. To overcome this drawback, this paper proposes a novel GCL framework with a Joint spectrAl augMentation, named GCL-JAM. Motivated the equivalence between the graph learning objective on an attribute graph and the spectral clustering objective on the attribute-interpolated graph, the node attributes are first abstracted as another type of node to harmonize the node attributes and graph topology. The newly constructed graph is then utilized to perform spectral augmentation to capture the correlation during augmentation. Theoretically, the proposed joint spectral augmentation is proved to perturb more inter-class edges and noise attributes compared to separate augmentation methods. Extensive experiments on homophily and heterophily graphs validate the effectiveness and universality of GCL-JAM.

Extracting evolving communities in social networks has attracted much attention recently due to its usefulness in the area of social media. Most existing models assume that network structures evolve monotonically and fail to leverage the fluctuating variation in the real world. Moreover, it is difficult to extract valuable community knowledge from previous snapshots, leading to a negative transfer to the current snapshot. In this article, we design a novel transferring strategy for dynamic community detection based on dual-population cooperation and competition. The transfer strategy guides the search by leveraging the meaningful community structures among previous snapshots based on the similarity between the current and all previous ones. Furthermore, to avoid the problem of insufficient population diversity caused by previous single-population algorithms, this article utilizes dual-population cooperative competition for multiobjective optimization. An intercooperation method effectively interchanges information according to normalized mutual information of different individuals in dual-population. Each population optimizes according to different objectives with a role-oriented teaching–learning-based optimizer to compensate for defects such as many hyperparameters, declining diversity, and insufficient convergence. Top students integrate the fine-grained strategy to mutate boundary nodes depending on embedding-based node activity; Ordinary students fuse the coarse-grained method to separate loosely connected subcommunities, while the bottom students do normal learning. Experimental results indicate that our approach outperforms state-of-the-art methods with high consistency.

As a pivotal architecture in Self-Supervised Learning (SSL), Graph Contrastive Learning (GCL) has demonstrated substantial application value in scenarios with limited labeled nodes (samples). However, existing GCLs encounter critical issues in the graph augmentation and positive and negative sampling stemming from the lack of explicit supervision, which collectively restrict their efficiency and universality. On the one hand, the reliance on graph augmentations in existing GCLs can lead to increased training times and memory usage, while potentially compromising the semantic integrity. On the other hand, the difficulty in selecting TRUE positive and negative samples for GCLs limits their universality to both homophilic and heterophilic graphs. To address these drawbacks, this paper introduces a novel GCL framework called GRAph learning via Self-contraSt (GRASS). The core mechanism is node-attribute self-contrast, which specifically involves increasing the feature similarities between nodes and their included attributes while decreasing the similarities between nodes and their non-included attributes. Theoretically, the self-contrast mechanism implicitly ensures accurate node-node contrast by capturing high-hop co-inclusion relationships, thereby enabling GRASS to be universally applicable to graphs with varying degrees of homophily. Evaluations on diverse benchmark datasets demonstrate the universality and efficiency of GRASS. The dataset and code are available at URL: https://github.com/YukunCai/GRASS.