Every graph G can be associated with many well-known invariant properties along with their corresponding values. A framework is proposed to measure the change in any particular invariant upon addition of a new edge $e$ in the resulting graph G+e. In graphs, the P-impact of an edge e is the `magnitude' of the difference between the values of the invariant P in graphs G+e from G. Several famous invariants are explored and a proof towards optimal edge addition for distance-impact in trees is given. A natural application to measuring the impact of edge addition to a graph is that of link prediction. An efficient algorithm for link prediction even with cold-start vertices using a subspace sharing method that decouples matrix completion and side information transduction is presented. This method is extended to predict ratings in user-item recommender systems where both may be cold-start.
Read
