Auditing Network Embedding An Edge Influence based Approach

Abstract : 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,000x) 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.

 EXISTING SYSTEM :

 ? A simply extended method on LINE for new vertices through updating the embedding of the new vertex and keeping the embeddings of existing vertices. ? It is an extension for the Skip-gram based network embedding methods, which can keep the optimality of the objective in the Skip-gram based methods in theory. ? With the evolvement of networks, the representations of vertices become stale and need to be updated to keep freshness. ? The other is the time complexity of training increases linearly with the number of vertices in networks. ? Actually, a network may not change much during a short time in dynamic situations, thus the embedding spaces should not change too much, and retraining is not necessary as well.

 DISADVANTAGE :

 ? We choose these competitors as they address the same problem setting as our methods, i.e., embedding general networks with only the original network topology as input. ? The fifth extension considers the node embedding problem in heterogeneous networks which contain nodes/edges of different types. ? For example, metapath2vec and HIN2Vec define the context network with metapaths over the heterogeneous networks, and apply skip-gram model and logistic classifier to learn the embeddings, respectively. ? We start with a basic pairwise formulation, and then augments it with a pointwise objective function.

 PROPOSED SYSTEM :

 • In this paper, we propose an efficient and stable embedding framework for dynamic networks. It is an extension of the network embedding methods based on skip-gram in a dynamic setting. • A selection mechanism is proposed to choose the original vertices affected greatly and update the representations of them. • Due to the changes of dynamic network at each time step is small comparing with the network size, we hope to learn new vertices and only update the representations of a part of vertices to improve the efficiency. • Therefore, we firstly propose a decomposable objective equivalent to the Skip-gram objective, which can learn the representation of each vertex separately.

 ADVANTAGE :

 ? Network embedding, which aims to automatically learn the node representations/embeddings in networks, has been attracting much research interest, largely due to its strong empirical performance in many network analysis tasks including node classification, node clustering , and link prediction. ? In practice, we found that these two choices have similar performance in many cases, and computing ?? can be significantly accelerated. ? However, as we will show in the experiment section, for both PaWine and LiWine, we often only need to use the original network as the context matrix to achieve a superior performance over the existing methods. ? This opens the door to a whole family of network embedding methods, with enhanced empirical performance for the downstream mining tasks while still enjoying scalable computation.