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) have achieved great success but are often considered to be challenged by varying levels of homophily in graphs. Recent empirical studies have surprisingly shown that homophilic GNNs can perform well across datasets of different homophily levels with proper hyperparameter tuning, but the underlying theory and effective architectures remain unclear. To advance GNN universality across varying homophily, we theoretically revisit GNN message passing and uncover a novel \textit{smoothness-generalization dilemma}, where increasing hops inevitably enhances smoothness at the cost of generalization. This dilemma hinders learning in high-order homophilic neighborhoods and all heterophilic ones, where generalization is critical due to complex neighborhood class distributions that are sensitive to shifts induced by noise or sparsity. To address this, we introduce the Inceptive Graph Neural Network (IGNN) built on three simple yet effective design principles, which alleviate the dilemma by enabling distinct hop-wise generalization alongside improved overall generalization with adaptive smoothness. Benchmarking against 30 baselines demonstrates IGNN's superiority and reveals notable universality in certain homophilic GNN variants. Our code and datasets are available at \href{https://github.com/galogm/IGNN}{https://github.com/galogm/IGNN}.

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 .