Efficient and Transferable Graph Learning via Anchor-Based Structural Encodings

Abstract

Graph-structured data arise in many domains, including biological networks, social systems, recommendation platforms, and knowledge graphs. While graph neural networks (GNNs) have become a dominant framework for learning from such data, their effectiveness often depends on iterative message passing, substantial computational cost, and assumptions that may limit scalability and robustness in large or weakly attributed graphs. In large graphs, message passing may require repeated neighborhood aggregation across multiple layers to capture non-local structural information, which can increase latency and resource consumption while also introducing problems such as over-smoothing, loss of node-level distinction, and sensitivity to weak or missing node attributes. These limitations are especially important for resource-constrained settings such as IoT devices, mobile systems, and large-scale scientific graph analysis, where accuracy alone is not sufficient and the trade-off among performance, parameter count, computation time, and scalability becomes central. Graph learning does not have to depend only on iterative message passing. Prior work and empirical evidence suggest that graph-distance structure in many practical benchmark graphs often exhibits approximately low-dimensional or low-rank regularity. This dissertation uses that property as a design principle: rather than constructing dense all-pairs distance matrices or repeatedly propagating information through GNN layers, it samples graph-distance structure through anchors, compresses it into structural coordinates, and reuses the resulting representations across prediction tasks and anchor-induced views. The novelty of this work lies not in the existence of landmark distances alone, but in developing them into a unified, scalable graph-learning framework: sampled graph distances are compressed into structural coordinates, reused across prediction tasks and anchor-induced views, and evaluated as a resource-efficient alternative or complement to message-passing GNNs. This provides a scalable and Green-AI-oriented path for graph learning, especially when full GNNs are too expensive or when node features are weak. This dissertation develops and evaluates scalable anchor-based structural encodings as an alternative and complement to conventional message-passing GNN pipelines. The central idea is to represent nodes through their relationships to selected anchor sets or landmark nodes, producing structural coordinates that capture graph position and topology even when node attributes are limited, noisy, or unavailable. Building on this idea, the dissertation investigates several coordinate-based representations, including virtual coordinates (VC), topology coordinates (TC), and directional virtual coordinates (DVC), and demonstrates how these representations can be compressed, aligned, and used in downstream prediction tasks. The central goal is to preserve useful local and global topological information while reducing or eliminating dependence on deep message-passing architectures and avoiding dense all-pairs graph computations. The main contribution of this dissertation is a scalable structural-learning framework that encodes graph topology through anchor-based representations rather than relying solely on iterative message passing. By representing each node through its distances or coordinate relationships to a selected set of anchors, the proposed VC, TC, and DVC methods provide compact structural features that capture both local neighborhood structure and non-local topological relationships. These features can be used with conventional neural predictors for node classification and link prediction. Empirically, these methods show a favorable accuracy and efficiency trade-off. On OGBN-Products, TC-based models match or slightly exceed comparable GCN performance while using roughly 78% fewer trainable parameters, and a smaller TC configuration remains within about one percentage point of GCN accuracy while using roughly 91% fewer parameters. In the selected OGBN-Products comparison, the nearest higher-ranked listed baseline uses about 2.1x10^5 trainable parameters, while the rank-1 listed model uses about 1.4x10^8, placing the highest-ranked model at a much larger parameter scale. On OGBN-Proteins, compact TC models achieve stronger ROC-AUC than GCN while using about 89\% fewer parameters, and achieve performance comparable to GeniePath-BS while using about 97% fewer parameters. In the selected OGBN-Proteins comparison, the nearest higher-ranked listed baseline uses about 4.9x10^5 trainable parameters, while the rank-1 listed model uses about 6.6x10^8. These results suggest that the proposed methods are not primarily intended to replace the highest-accuracy leaderboard models, but instead provide a resource-adaptable alternative when the goal is to preserve strong predictive performance with substantially lower model complexity. The framework is especially applicable to large sparse graphs, biological and scientific networks, recommendation and social networks, and edge or IoT settings where graph structure is informative but memory, computation, latency, or node-feature quality limits the use of deeper message-passing models. Beyond single-task prediction, the dissertation also contributes scalable construction methods, including anchor sampling, dimensionality reduction, chunked computation, and partition-aware processing, as well as transfer analysis across anchor-induced views. The strongest transfer evidence is for reusing models across different views of the same graph or overlapping subgraphs through lightweight orthogonal Procrustes alignment, while transfer across substantially different graph domains remains a harder open problem. Across these experiments, the results show that anchor- and distance-based structural representations provide a viable and flexible alternative or complement to traditional GNN pipelines. They are especially useful in settings where graph structure is informative, node features are limited, or scalability is a primary concern. A key practical advantage of this approach is that graph topology can be converted into reusable structural features before downstream learning, allowing conventional neural predictors such as multilayer perceptrons or lightweight classifiers to exploit graph information without performing iterative message passing during prediction. This separation between structural feature construction and neural prediction supports a Green-AI-oriented perspective, in which graph learning methods are evaluated not only by predictive accuracy but also by parameter efficiency, computational cost, memory use, and deployability. More broadly, this dissertation contributes a structural learning perspective that connects graph topology, representation design, transfer, and practical deployment, and it offers guidance for developing graph learning systems that are both effective and computationally manageable.