Wu, Nan2023-03-172023-03-172022https://udspace.udel.edu/handle/19716/32466Graph Neural Networks (GNNs) have been successfully applied in many areas to solve real-world problems. Among various architectures of GNNs, the class of spatial-based convolutional GNNs (Conv-GNNs) has gained particular attention due to its simplicity yet effectiveness. The essence of a spatial-based Conv-GNN is a message passing scheme which aggregates neighborhood information to update a focal node's representation. Many of these models are referred to as shallow models due to the over-smoothing issue such that their performance degrades significantly when models go deep. Such shallow models have limited capability to capture information from high-order neighborhood and therefore may suffer from information loss. In this dissertation, I propose Graph Tree Networks (GTNets), a deep graph learning architecture with a new general message passing scheme which follows the nature of message passing in the tree representation of a graph where messages propagate upward from the leaf nodes to the root node, and each node preserves its initial information prior to receiving information from its child nodes. In GTNet, a focal node's representation is updated by aggregating its initial feature and its neighbor nodes' updated hidden features. Different aggregators in GTNet lead to various graph tree network models. ☐ In the first part of this dissertation, I propose two homogeneous graph tree network models - Graph Tree Convolutional Network (GTCN) and Graph Tree Attention Network (GTAN) by exploring a normalized mean aggregator and an additive attention aggregator, respectively. Comprehensive experiments on five popular real-world benchmark datasets demonstrate the superior performance of the proposed GTCN and GTAN against the state-of-the-art GNN models. We also demonstrate the deep capability of the proposed GTCN and GTAN through rigorous theoretical analysis and extensive experiments. ☐ In the second part of this dissertation, I propose two heterogeneous graph tree network models - Heterogeneous Graph Tree Convolutional Network (HetGTCN) and Heterogeneous Graph Tree Attention Network (HetGTAN) which are built on GTCN and GTAN, respectively. Heterogeneous graph neural networks (HGNNs) have attracted increasing research interest in recent three years. Most existing HGNNs are a combination of meta-path-specific or edge-type-specific homogeneous Conv-GNNs. The meta-path-based HGNNs either require domain knowledge to handcraft meta-paths or consume huge amount of time and memory to automatically construct meta-paths. Regardless of the meta-path dependency, most existing HGNNs employ shallow Conv-GNNs such as GCN and GAT to aggregate neighborhood information, and may have limited capability to capture information from high-order neighborhood. The proposed HetGTCN and HetGTAN do not rely on meta-paths to encode heterogeneity in both node features and graph structure, and can go deep. Extensive experiments on three real-world heterogeneous graph datasets demonstrate that the proposed HetGTCN and HetGTAN are efficient and consistently outperform all state-of-the-art HGNN baselines on the node classification task. ☐ Despite the success of GNNs in many applications on graph-structured data, most efforts have been devoted to elaborating new network architectures and learning algorithms, but overlooked the leverage of ensemble learning techniques to improve existing graph algorithms. In the third part of this dissertation, I propose a simple generic bagging based ensemble learning strategy, which can be applied to any backbone GNNs. We demonstrate the effectiveness of the proposed ensemble strategy through comprehensive experiments on four real-world homogeneous graph datasets with four backbone GNN models, and three real-world heterogeneous graph datasets with six backbone HGNN models.Convolutional graph neural networksGraph neural networksGraph representation learningHeterogeneous graphsThesis1373238128https://doi.org/10.58088/vt7q-70402023-02-14en