Methods for Analyzing Large Bipartite Graphs with Applications to Link Prediction

We look at several techniques for analyzing and characterizing large bipartite graphs with a focus on better explaining the performance of graph neural networks in performing link prediction. We prove several results for computing the number of a variety of small subgraphs to help characterize scale in large bipartite graphs, and we also derive an asymptotic formula to characterize the longest simple walk. We then look at using now standard convolution-filter-based graph neural network learning methods to perform link prediction in each data set. Ultimately, we find that the graph learning methods used are most affected by whether the data is well described by a power-law distribution, which indicates a scale-free structure in the data. The scale-free property is shown to degrade predictive power, and it indicates that existing convolutional-filter-based methods learn predictive tasks better when there are strong distinctions in scales in a graph despite there potentially being large numbers of disparate scales.