Introduction
Network Representation Learning (NRL) is a fundamental technique in modern graph analysis, mapping complex relational data into low-dimensional latent vectors. However, most NRL models operate under the assumption of structural uniformity across the network. This paper addresses the critical issue of structural heterogeneity, where distinct subgroups within a network exhibit unique connectivity patterns. When a global model is trained on such data, it often fails to capture the nuances of minority subgroups, leading to biased representations that propagate into downstream tasks like classification and link prediction.
Methodology: Identifying Latent Structural Heterogeneity
The authors propose a framework to automatically detect "unfairness" in representations by identifying subgroups whose local structural properties deviate significantly from the global model's view.
Mean Latent Similarity Discrepancy (MLSD)
MLSD is introduced as a novel quality measure for unfairness. It calculates the statistical difference between the latent similarities of nodes when learned specifically from a subgroup versus when learned from the entire dataset. A high MLSD score indicates that the global embedding has "smeared" the subgroup's unique structure, rendering the representation biased.
Exceptional Model Mining (EMM)
To efficiently search for biased subgroups within a vast space of attribute combinations (e.g., weather conditions combined with geographic locations), the framework utilizes Exceptional Model Mining. This heuristic beam search identifies multi-attribute subgroups that maximize the MLSD score, effectively automating the discovery of unfairness without requiring pre-defined sensitive labels.
Experimental Evaluation
The framework was validated using both synthetic and real-world datasets. Synthetic networks, such as modified versions of the Karate Club and American College Football datasets, were used to establish a ground truth for structural bias.
In real-world applications, the authors analyzed NYC Taxi and San Francisco Bike-sharing datasets. For the NYC Taxi data ($N \approx 1M$ edges), 33 descriptive variables including weather (TMIN, TMAX) and trip details (PickupHour) were used to identify contexts where standard embeddings like node2vec failed to represent specific mobility patterns accurately.
Key Results and Statistical Significance
The method demonstrated high efficacy, achieving True Positive Rates of up to 0.69 in recovering ground truth unfairness in synthetic data. In the NYC Taxi dataset, the model identified that representations were significantly biased during specific time windows (e.g., morning pickups) and under certain weather conditions.
To ensure the discovered subgroups were not artifacts of noise, the authors employed Maximum Mean Discrepancy (MMD) testing. By comparing real fairness scores against shuffled data baselines, they confirmed that the discovered unfairness was statistically significant (e.g., $p=0.0001$ for KarateX4n10k), as illustrated by the clear separation between the quality scores of discovered subgroups and the false discovery baselines.
Conclusion and Future Work
This research highlights that fairness in machine learning must be addressed "upstream" at the representation level. By identifying structural heterogeneity, the proposed framework provides a diagnostic tool for detecting hidden biases in network embeddings. Future work will focus on integrating these detection mechanisms into the training process itself to develop "fair-by-design" network representation models.
Summary updated