GREASE: Graph Imbalance Reduction by Adding Sets of Edges
Yoosof Mashayekhi, Bo Kang, Jefrey Lijffijt, Tijl De Bie · IEEE Transactions on Knowledge and Data Engineering · 2023
Real-world data can often be represented as a heterogeneous network relating nodes of different types. E.g., a job market can be represented as a job seeker-skill-vacancy network. It can be relevant to consider theimbalancebetween nodes of different types, in terms of whether they are similarly connected in the network. For example, it is desirable that job seekers and vacancies are mixed well. If they are not, then there is imbalance. We propose to quantify the imbalancebetween two sets of nodesin a network as the Earth Mover's Distance between the sets. Given this quantification, we introduceGREASE(Graph imbalance REduction by Adding Sets of Edges), a method that selects a fixed number of unconnected node-pairs, which—if links were added between them—aims to maximally reduce the imbalance. In the job market network,GREASEcan be used to select skills that job seekers do not yet have, but could strive to acquire, to reduce the imbalance between job seekers and vacancies.GREASEmay also be used in other applications, such as reducing controversy between opposing sides on a polarizing topic. We evaluatedGREASEon several datasets and find thatGREASEoutperforms baselines in reducing network imbalance.