Join on Zoom: https://iastate.zoom.us/j/94871918940

Structure-aware Graph Representation Learning Using Graph Neural Networks

Graph Neural Networks (GNNs) have emerged as powerful tools for learning representations from graph-structured data across diverse domains. However, existing GNN architectures often fail to adequately capture critical structural properties that fundamentally influence both the quality and fairness of learned representations. This dissertation addresses three fundamental challenges in structure-aware graph representation learning: preserving directional information in directed graphs, ensuring structural fairness in node representations, and mitigating community-level structural bias in GNN predictions.

First, we propose a novel method for computing joint two-node structural representations for link prediction in directed graphs. Existing approaches either learn node embeddings independently and combine them, failing to differentiate distant nodes with similar neighborhoods, or employ undirected GNNs on enclosing subgraphs, inevitably losing directional signals. Our approach utilizes directed enclosing subgraphs with direction-aware positional encodings and GNNs to preserve edge orientation, demonstrating superior link prediction performance compared to both undirected and existing directed baselines.

Second, we address individual structural bias in GNN-based graph representation learning by incorporating both local and global structural information into representation learning. Prior fairness work has focused primarily on node features while overlooking structural biases that can systematically disadvantage individuals based on their position in the graph. We propose a pre-processing bias mitigation approach that employs locally fair PageRank methods to address local structure discrepancies and truncated singular value decomposition-based similarities to handle global structural disparities between node pairs. This method achieves superior individual fairness metrics while maintaining predictive performance.

Third, we address community-level structural bias in GNN-based graph representation learning, which arises from diverse local neighborhood distributions during GNN message passing. Current GNN fairness research relies on oversimplified evaluation metrics that can provide misleading assessments of fairness. We introduce ComFairGNN, a novel framework that measures and mitigates bias at the community level using a learnable coreset-based debiasing function. This approach addresses the complex evaluation paradoxes inherent in graph-structured data and demonstrates effectiveness across both accuracy and fairness metrics.

Comprehensive evaluations on multiple benchmark datasets validate that our structure-aware approaches significantly outperform state-of-the-art baselines in their respective tasks. This dissertation establishes that explicit modeling of structural properties, including directionality, positional context, and community-level patterns, is essential for developing GNN architectures that are both effective and equitable for real-world applications.

Committee: Qi Li (major professor), Ying Cai, Hongyang Gao, Wallapak Tavanapong, and Ali Jannesari