Introduction

Link prediction in bipartite graphs is a problem arising in a variety of problem context, most prominently recommender systems. This project develops methods for link prediction in bipartite graph structures that integrate (community) information embedded in a graph structure with additional node-specific input from additional information sources such as text data. For modelling our problem and validating our solution, we will utilise procurement data from SpendNetwork which is our industrial partner. The algorithms for link predictions will be integrated into a recommender system and will generate contract recommendations for public suppliers and buyers. Given the vast set of public tender contracts, our system can guide suppliers and buyers to relevant contracts and increase transparency of public contracts. This can result in better value for taxpayers and an increase in competition which can lead to market efficient outcomes.
 

Explaining the science

Due to the survivor bias dominating the observed data in the available tendering data, we are interested in formulating the problem of link prediction as an unsupervised learning problem on bipartite graphs. In the resulting formulation, a link between two nodes is inferred indirectly from the inclusion of a pair of nodes (from the two different parts of the graph) within the same community.

Bipartite graphs arise in a wide range of problems but methodologies for their analysis are in their infancy compared to the range of methodologies for standard graph structures. E.g., the most common approach to community detection is based on the projection of a bipartite graph structure into the space of its top or bottom nodes, but the limitations of this approach are well recognised. We draw on principles from multi-view clustering approaches to address these limitations.

A graph representing interactions between suppliers
Fig 1. In an input Graph (left) representing interactions between suppliers, contracts and buyers we discover communities (center) with unsupervised approaches. Suppliers get recommended contracts from the cluster they were assigned to.
Nodes can be of type Supplier (“s” – square), Notice (“n” – diamond) or Buyer (“b” – circle) and colours represent clusters found with the Louvain algorithm.

 

Project aims

  1. Understand sensitivity to link sparsity, for existing techniques for community detection and link prediction.
     
  2. Develop a novel approach to community detection that addresses the particular case of bipartite graph structures and overcomes the limitations of traditional projection-based approaches to community-detection.
     
  3. Develop a novel link prediction method for bipartite graphs that allows for the frictionless integration of a range of additional data sources including information in text format, through the integration of multiple data views.

Applications

The graph-based, link prediction algorithms will be integrated into a recommender system modelled on the procurement data obtained from SpendNetwork, our industrial partner. Our goal is to have better procurement outcomes by leveraging network theory and unsupervised learning methods. Given the extensive universe of tender contracts, recommender systems (similarly to search engines) can act as filters:

  • Guiding suppliers and buyers to relevant contracts.
  • Increasing transparency of public contracts resulting in better value for tax-payers.
  • Increasing competition which leads to market efficiency and lower prices.

Recent updates

March 2021: Completion of generator

April 2021: First manuscript under submission to CompleNet Live

Organisers

Contact info

Arielle Bennett
[email protected]

Collaborators