Graph neural networks (GNNs) have demonstrated strong performance in various graph mining tasks but rely heavily on extensively labeled nodes. To improve training efficiency, graph active learning (GAL) has emerged as a solution for selecting the most informative nodes for labeling. However, existing GAL methods are primarily designed for homophilic graphs, where nodes with the same labels are more likely to be connected. In this work, we systematically study active learning on heterophilic graphs, a setting that has received limited attention. Surprisingly, we observe that existing GAL methods fail to consistently outperform random sampling on heterophilic graphs. Through an in-depth investigation, we reveal that these methods implicitly assume homophily even on heterophilic graphs, leading to suboptimal performance. To address this issue, we introduce the principle of "Know Your Neighbors" and propose an active learning algorithm KyN specifically for heterophilic graphs. The core idea of KyN is to provide GNNs with accurate estimations of homophily distribution by labeling nodes together with their neighbors. We implement KyN based on subgraph sampling with probabilities proportional to l1 Lewis weights, which is supported by solid theoretical guarantees. Extensive experiments on diverse real-world datasets, including a large heterophilic graph with over 2 million nodes, demonstrate the effectiveness and scalability of KyN.

Graph recommender (GR) is a type of graph neural network (GNN) encoder that is customized for extracting information from the user-item interaction graph. Due to its strong performance on the recommendation task, GR has gained significant attention recently. Graph contrastive learning (GCL) is also a popular research direction that aims to learn, often unsupervised, GNNs with certain contrastive objectives. As general graph representation learning methods, GCLs have been widely adopted with supervised recommendation loss for joint training of GRs. Despite the intersection of GR and GCL research, theoretical understanding of the relationship between the two fields is surprisingly sparse. This vacancy inevitably leads to inefficient scientific research.

Graph Neural Networks (GNNs) are powerful tools for processing graph data, but training them is typically time-consuming and expensive in terms of GPU memory. Recently, graph reduction techniques have been investigated as a pre-processing step, due to the fact that the time and space complexity of GNNs training is only sublinear on the reduced graphs. Among them, graph coarsening has gained significant attention. By generating a coarse graph while preserving graph structure properties, it can effectively reduce the size of nodes by up to a factor of ten without significantly compromising performance. However, the coarsening phase for this method is purely heuristic, leaving room for improvement. In this paper, we propose Learnable Graph Coarsening with Gradient Matching (LGCGM), boosting graph coarsening with (downstream)task-specific dataset condensation objective. To the best of our knowledge, LGCGM is the first work that incorporates downstream-task information for graph coarsening. Extensive experiments demonstrate that this additional information efficiently enhances the quality of coarse graphs and outperforms previous graph condensation methods on large graphs.

Graph contrastive learning (GCL) has become a powerful tool for learning graph data, but its scalability remains a significant challenge. In this work, we propose a simple yet effective training framework called Structural Compression (StructComp) to address this issue. Inspired by a sparse low-rank approximation on the diffusion matrix, StructComp trains the encoder with the compressed nodes. This allows the encoder not to perform any message passing during the training stage, and significantly reduces the number of sample pairs in the contrastive loss. We theoretically prove that the original GCL loss can be approximated with the contrastive loss computed by StructComp. Moreover, StructComp can be regarded as an additional regularization term for GCL models, resulting in a more robust encoder. Empirical studies on various datasets show that StructComp greatly reduces the time and memory consumption while improving model performance compared to the vanilla GCL models and scalable training methods.