Graph data mining techniques in real-world scenarios often encounter significant computational challenges, especially when the graph contains a large number of nodes and edges. Recently, Graph Condensation (GC) has emerged to offer data-centric solutions that address the challenge of graph volume, enhancing the efficiency of graph data mining and storage. Current methods in GC rely solely on optimizing heuristic metrics of one-way maintenance of key information in the condensed graph. However, the maintenance of key information may be insufficient due to the significant condensation ratio, yet these methods lack an effective mechanism to verify and compensate for that. To this end, this paper aims to enhance the maintenance of key information through a reconstruction based alignment mechanism. More specifically, inspired by the Kolmogorov Complexity, we revisit the theoretical foundations of GC and propose a way-back mechanism that introduces a feedback loop of learning to reconstruct the original graph from the condensed graph, with the objective of key information align ment, namely the WbGC. We modify several GC methods with our mechanism, and the experiments show that our approach provides an enhanced solution for GC. Code is available at https://anonymous.4open.science/r/WbGC-1842.

Graph Neural Networks (GNNs) excel in graph mining tasks thanks to their message-passing mechanism, which aligns with the homophily assumption. However, connected nodes can also exhibit inconsistent behaviors, termed heterophilic patterns, sparking interest in heterophilic GNNs (HTGNNs). Although the message-passing mechanism seems unsuitable for heterophilic graphs owing to the propagation of dissimilar messages, it is still popular in HTGNNs and consistently achieves notable success. Some efforts have investigated such an interesting phenomenon, but are limited in the data perspective. The model-perspective understanding remains largely unexplored, which is conducive to guiding the designs of HTGNNs. To fill this gap, we build the connection between node discriminability and the compatibility matrix (CM). We reveal that the effectiveness of the message passing in HTGNNs may be credited to increasing the proposed Compatibility Matrix Discriminability (CMD). However, the issues of sparsity and noise pose great challenges to leveraging CM. Thus, we propose CMGNN, a novel approach to alleviate these issues while enhancing the CM and node embeddings explicitly. A thorough evaluation involving 13 datasets and comparison against 20 well-established baselines highlights the superiority of CMGNN.

Graph data, prevalent across domains like social networks, biological systems, and recommendation systems, presents significant challenges due to its large scale and complex structure. The advent of Graph Neural Networks (GNNs) has revolutionized graph data mining by effectively capturing node dependencies and neighborhood information. However, the computational complexity of processing large-scale graphs remains a major hurdle, as real-world graphs often consist of millions or even billions of nodes and edges. Efficient techniques like message passing and sampling have helped mitigate this issue, but memory and processing constraints persist. A promising approach to addressing these challenges is learning to reduce the size of large-scale graphs while retaining essential information, thus facilitating faster and more efficient graph data mining tasks, such as graph condensation, reduction, coarsening, summarization, and so on. Despite the differences in terminology, approaches under these topics share the same motivation: to generate smaller yet informative graphs that can replace the original large-scale datasets. In this article, we unify these approaches under the concept of Graph Scaling (GS), highlighting the shared motivation across multiple topics. Alongside this definition, to clarify the question of what principles should be followed when scaling a graph and how a scaled graph was formulated, we propose a taxonomy to methodically categorize and understand existing methods. Moreover, by organizing the dataset and evaluation metrics, we aim to provide a more comprehensive understanding of the GS methods from a practical perspective. Moving forward, we delve into the limitations and challenges of GS methods, identifying the shortcomings and potential in the literature. Finally, we conclude this article by outlining future directions and offering concise guidelines to inspire future research in this field. A full paper list and online resources about GS are available at https://github.com/Frostland12138/Awesome-Graph-Scaling .

3D convolutional neural networks have revealed superior performance in processing volumetric data such as video and medical imaging. However, the competitive performance by leveraging 3D networks results in huge computational costs, which are far beyond that of 2D networks. In this paper, we propose a novel Hilbert curve-based cross-dimensionality distillation approach that facilitates the knowledge of 3D networks to improve the performance of 2D networks. The proposed Hilbert Distillation (HD) method preserves the structural information via the Hilbert curve, which maps high-dimensional (>=2) representations to one-dimensional continuous space-filling curves. Since the distilled 2D networks are supervised by the curves converted from dimensionally heterogeneous 3D features, the 2D networks are given an informative view in terms of learning structural information embedded in well-trained high-dimensional representations. We further propose a Variable-length Hilbert Distillation (VHD) method to dynamically shorten the walking stride of the Hilbert curve in activation feature areas and lengthen the stride in context feature areas, forcing the 2D networks to pay more attention to learning from activation features. The proposed algorithm outperforms the current state-of-the-art distillation techniques adapted to cross-dimensionality distillation on two classification tasks. Moreover, the distilled 2D networks by the proposed method achieve competitive performance with the original 3D networks, indicating the lightweight distilled 2D networks could potentially be the substitution of cumbersome 3D networks in the real-world scenario.