Aiming to overcome distribution shift and label sparsity that hinder cross-domain generalization of Graph Neural Networks (GNNs), Unsupervised Graph Domain Adaptation (UGDA) transfers knowledge from a label-rich source to an unlabeled target graph. Yet in practice, strict privacy protocols often withhold the source graph, reducing UGDA to the more constrained Source-Free UGDA (SFUGDA) where only a pre-trained source GNN remains. In this setting, the source GNN serves as a simple, task-specific graph foundation model. Despite recent progress, existing source-free UGDA methods remain hampered by source-knowledge absence: deprived of source graphs, they lose the reference distribution needed to gauge domain shift and must lean on noisy target cues, incurring biased adaptation and catastrophic forgetting. To overcome this drawback, this paper devises Source-Free Graph foundation model Adaptation via pseudo-source Reconstruction (SFGAR), a two-stage SFUGDA framework that first generates pseudo-source graphs to recover the source distribution encoded in a frozen pre-trained GNN, then adversarially aligns these synthetic graphs with the unlabeled target. Theoretical analysis shows that this proxy alignment tightly bounds the target-domain generalization error. Extensive experiments on public benchmarks validate the state-of-the-art performance of SFGAR.

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.

In this paper, we study the problem of maximal similar-weight biclique enumeration for large bipartite graphs. Given an edge-weighted bipartite graph$G=(U,\ V,\ E)$and a weight difference threshold$\delta$, we aim to efficiently enumerate all maximal similar-weight bicliques in$G$, where a maximal similar-weight biclique is a maximal complete subgraph$B(L,\ R)$of$G$such that the weight difference of edges in$E(B)$is not larger than$\delta$. This problem has many applications, such as item recommendation, fraud detection, and biclustering of gene expression data, etc. To the best of our knowledge, we are the first to systematically study this problem. It is very challenging to efficiently solve this problem due to its #P-completeness. In this paper, we propose a two-phase branch-and-bound baseline method, namely MSWBE, which explores the search space in a depth-first manner. Although MSWBE offers a useful computation framework to our problem, its performance is not yet satisfactory due to the large candidate set during the enumeration. To alleviate this, we propose an advanced approach, called MSWBE++. In particular, MSWBE++ exploits the search space by utilizing the edge connectivity and weight information simultaneously, and therefore refines the candidate set significantly. Observing that a straightforward implementation of MSWBE++ by following a depth-first search strategy may generate non-maximal bicliques, we develop a breadth-first search strategy to realize MSWBE++, which can discard the non-maximal sets at an early stage. To accelerate the computation, we introduce effective graph reduction techniques. Our extensive experimental results on 10 real-life datasets demonstrate that MSWBE++ significantly outperforms the baseline methods by up to 2 orders of magnitude. We conduct a case study to show that maximal similar-weight bicliques can provide useful searching hints for fraudulent rating detection.

Graph Transformers (GTs), adept at capturing the locality and globality of graphs, have shown promising potential in node classification tasks. Most state-of-the-art GTs succeed through integrating local Graph Neural Networks (GNNs) with their global Self-Attention (SA) modules to enhance structural awareness. Nonetheless, this architecture faces limitations arising from scalability challenges and the trade-off between capturing local and global information. On the one hand, the quadratic complexity associated with the SA modules poses a significant challenge for many GTs, particularly when scaling them to large-scale graphs. Numerous GTs necessitated a compromise, relinquishing certain aspects of their expressivity to garner computational efficiency. On the other hand, GTs face challenges in maintaining detailed local structural information while capturing long-range dependencies. As a result, they typically require significant computational costs to balance the local and global expressivity. To address these limitations, this paper introduces a novel GT architecture, dubbed DUALFormer, featuring a dual-dimensional design of its GNN and SA modules. Leveraging approximation theory from Linearized Transformers and treating the query as the surrogate representation of node features, DUALFormer \emph{efficiently} performs the computationally intensive global SA module on feature dimensions. Furthermore, by such a separation of local and global modules into dual dimensions, DUALFormer achieves a natural balance between local and global expressivity. In theory, DUALFormer can reduce intra-class variance, thereby enhancing the discriminability of node representations. Extensive experiments on eleven real-world datasets demonstrate its effectiveness and efficiency over existing state-of-the-art GTs.

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.

Graph Transformers (GTs), which effectively capture long-range dependencies and structural biases simultaneously, have recently emerged as promising alternatives to traditional Graph Neural Networks (GNNs). Advanced approaches for GTs to leverage topology information involve integrating GNN modules or modulating node attributes using positional encodings. Unfortunately, the underlying mechanism driving their effectiveness remains insufficiently understood. In this paper, we revisit these strategies and uncover a shared underlying mechanism—Cross Aggregation—that effectively captures the interaction between graph topology and node attributes. Building on this insight, we propose the Universal Graph Cross-attention Transformer (UGCFormer), a universal GT framework with linear computational complexity. The idea is to interactively learn the representations of graph topology and node attributes through a linearized Dual Cross-attention (DCA) module. In theory, this module can adaptively capture interactions between these two types of graph information, thereby achieving effective aggregation. To alleviate overfitting arising from the dual-channel design, we introduce a consistency constraint that enforces representational alignment. Extensive evaluations on multiple benchmark datasets demonstrate the effectiveness and efficiency of UGCFormer.

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.

Continuous subgraph matching (CSM) is a critical task for analyzing dynamic graphs and has a wide range of applications, such as merchant fraud detection, cyber-attack hunting, and rumor detection. Although many efficient CSM algorithms have been recently proposed, they are mainly designed to process a single query. However, in some application scenarios, multi-query oriented continuous subgraph matching (MQCSM) may be of more interest. To our knowledge, the two existing solutions to MQCSM are outdated due to unsatisfactory performance. In this paper, we propose MQ-Match, an efficient approach to MQCSM. First, we design a compact yet effective index structure CCG, which maintains the local matching result of vertices in the data graph using a directed graph. The directed edges in CCG can be utilized as an effective pruning rule for the subsequent incremental matching algorithm when expanding a partial match. Then, we develop a computation sharing incremental matching algorithm. In specific, a set of matching trees is constructed based on the depth-first search trees of the query graphs. By utilizing CCG, we conduct subgraph matching for the matching tree to collect the incremental matches for the query graphs, where the common structures of query graphs are matched only once. Extensive experiments show that MQ-Match can achieve 3.1x-7071.4x speedup over the competitors, and consumes much less memory under the majority of the experiment settings.

Continuously monitoring structural patterns in streaming graphs is a critical task in many real-time graph-based applications. In this paper, we study the problem of time-constrained continuous subgraph matching (shorted as TCSM) over streaming graphs. Given a query graph Q with timing order constraint and a data graph stream G , TCSM aims to report all incremental matches of Q in G for each update of G , where a match should obey both structure constraint (i.e., isomorphism) and timing order constraint of Q. Although TCSM has a wide range of applications, such as cyber-attack detection and credit card fraud detection, we note that this problem has not been well addressed. The state-of-the-art bears the limitations of high index space cost and intermediate result maintenance cost. In this paper, we propose TC-Match, an effective approach to TCSM. First, we design a space and time cost-effective index CSS, which is essentially a k -partite graph structure where a node corresponds to an edge in G. By carefully creating links between nodes, we can encapsulate into CSS the partial embedding and timing order information between edges in G. We theoretically show that CSS has polynomial space and construction time complexities. Second, based on the property of CSS, we develop an efficient incremental matching algorithm with an effective node merging optimization. Extensive experiments show that TC-Match can achieve up to 3 orders of magnitude query performance improvement over the baseline methods, and meanwhile the memory consumption is reduced by 48.7%-86.7%.

In this article, 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| \geq \alpha$and$|R| \geq \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 article, we propose a competitive branch-and-bound method, namely${\sf MBEN}$, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of${\sf 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${\sf 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.

Predicting the number of faults in software modules can be more helpful instead of predicting the modules being faulty or non-faulty.Chen et al. (SEKE 397-402, 2015) and Rathore et al. (Soft Computing 21: 7417-7434, 2017) empirically investigate the feasibility of some regression algorithms for predicting the number of defects.The experimental results showed that the decision tree regression algorithm performed best in terms of average absolute error (AAE), average relative error (ARE) and root mean square error (RMSE).However, they did not consider the imbalanced data distribution problem in defect datasets and employed improper performance measures for evaluating the regression models to evaluate the performance of models for predicting the number of defects.Hence, we revisit the impact of different regression algorithms for predicting the number of defects using Fault-Percentile-Average (FPA) as the performance measure.The experiments on 31 datasets from PROMISE repository show that the prediction performance of models for predicting the number of defects built by different regression algorithms are various, and the gradient boosting regression algorithm and the Bayesian ridge regression algorithm can achieve better performance． Keywords-predicting the number of defects; regression algorithm; data imbalance; Fault-Percentile-Average;

Prediction the number of faults in software modules can be more helpful instead of predicting the modules being faulty or non-faulty.Some regression models have been used for predicting the number of faults.However, the software defect data may involve irrelevant and redundant module features, which will degrade the performance of these regression models.To address such issue, this paper proposes a feature selection method based on Feature Spectral Clustering and feature Ranking (FSCR) for the number of software faults prediction.First, FSCR groups the original features with spectral clustering according to the correlation between every two features.Second, FSCR employs ReliefF algorithm to compute the relevance between each feature with respect to the number of faults and selects top p most relevant features from each resulted cluster.We evaluate our proposed method on 6 widely-studied project datasets with four performance metrics.Comparison with five existing feature selection methods demonstrates that FSCR is effective in selecting features for the number of faults prediction.