Auditing Network Embedding: An Edge Influence Based Approach

Learning node representations in a network has a wide range of applications. Most of the existing work focuses on improving the performance of the learned node representations by designing advanced network embedding models. In contrast to these work, this article aims to provide some understanding of the rationale behind the existing network embedding models, e.g.,
why
a given embedding algorithm outputs the specific node representations and
how
the resulting node representations relate to the structure of the input network. In particular, we propose to discern the edge influence for two widely-studied classes of network embedding models, i.e., skip-gram based models and graph neural networks. We provide algorithms to effectively and efficiently quantify the edge influence on node representations, and further identify high-influential edges by exploiting the linkage between edge influence and network structure. Experimental evaluations are conducted on real datasets showing that: 1) in terms of quantifying edge influence, the proposed method is significantly faster (up to
$2,000\times$
) than straightforward methods with little quality loss, and 2) in terms of identifying high-influential edges, the identified edges by the proposed method have a significant impact in the context of downstream prediction task and adversarial attacking.