Source-linked AI summary
BiRank: Towards Ranking on Bipartite Graphs
Xiangnan He, Ming Gao, Min-Yen Kan, Dingxian Wang
TL;DR
The paper asks how to rank vertices in bipartite graphs using both link structure and vertex priors. It introduces BiRank, a regularization-based iterative method with Bayesian interpretation, and applies it to popularity prediction and personalized recommendation, where experiments report effectiveness across both tasks.
Problem
Existing bipartite-ranking work often targets specific applications or adapts existing algorithms, while the paper seeks a generic approach combining graph structure with vertex priors.
Method
BiRank iteratively ranks bipartite-graph vertices using query-vector priors and symmetric normalization, with graph-regularization and Bayesian interpretations.
Results
BiRank is reported to converge to a unique stationary ranking and is applied in experiments on popularity prediction and personalized recommendation.
Takeaways & Limitations
The framework supports flexible ranking hypotheses and extensions from bipartite to n-partite graphs.
Takeaways & Limitations
The paper uses mean squared error and leaves ranking-oriented losses such as BPR-OPT for future work.
Abstract
from arXiv · showhide
The bipartite graph is a ubiquitous data structure that can model the relationship between two entity types: for instance, users and items, queries and webpages. In this paper, we study the problem of ranking vertices of a bipartite graph, based on the graph's link structure as well as prior information about vertices (which we term a query vector). We present a new solution, BiRank, which iteratively assigns scores to vertices and finally converges to a unique stationary ranking. In contrast to the traditional random walk-based methods, BiRank iterates towards optimizing a regularization function, which smooths the graph under the guidance of the query vector. Importantly, we establish how BiRank relates to the Bayesian methodology, enabling the future extension in a probabilistic way. To show the rationale and extendability of the ranking methodology, we further extend it to rank for the more generic n-partite graphs. BiRank's generic modeling of both the graph structure and vertex features enables it to model various ranking hypotheses flexibly. To illustrate its functionality, we apply the BiRank and TriRank (ranking for tripartite graphs) algorithms to two real-world applications: a general ranking scenario that predicts the future popularity of items, and a personalized ranking scenario that recommends items of interest to users. Extensive experiments on both synthetic and real-world datasets demonstrate BiRank's soundness (fast convergence), efficiency (linear in the number of graph edges) and effectiveness (achieving state-of-the-art in the two real-world tasks).
1 INTRODUCTION
The paper addresses bipartite-graph vertex ranking by combining graph structure with vertex priors. It introduces BiRank, provides theoretical interpretations and extensions, and evaluates it in popularity prediction and personalized recommendation.
- Bipartite-graph ranking supports popularity prediction, similarity search, and recommendation, but prior work largely focused on unipartite graphs or application-specific adaptations.
- BiRank formulates ranking using both graph structure and prior information about vertices, allowing vertex priors to encode features.
- BiRank converges to a unique stationary point and is analyzed through graph regularization and a complementary Bayesian view.
- The method is applied to item popularity prediction and extended to n-partite graphs for personalized ranking.
- The paper reports extensive experiments for popularity prediction and personalized recommendation.
2 RELATED WORK
Related work includes propagation-based ranking, graph regularization, and bipartite-graph applications. BiRank differs by using symmetric normalization to smooth bipartite graphs and support principled extensions.
- PageRank and HITS are prominent graph-ranking methods, while variants study stability and structural issues in iterative rankings.
- Graph-regularization research commonly addresses labeling partially known vertices, with extensions replacing squared-error fitting by hinge ranking loss.
- BiRank targets two vertex types directly rather than treating the graph as homogeneous, and separately handling those types is validated through experiments.
- Existing bipartite-ranking applications include query suggestion, entity ranking, click-spam detection, and related tasks.
- BiRank propagates scores like earlier methods but uses symmetric normalization, normalizing each edge by both endpoint degrees to smooth the graph.
3 PROBLEM FORMULATION
The paper models an undirected weighted bipartite graph with two vertex sets and an edge-weight matrix. Ranking assigns real-valued scores to vertices using graph relationships and query-vector priors.
- A bipartite graph G = (U ∪P, E) contains two vertex sets, U and P, with edges only between the different types.
- Figure 1 illustrates the bipartite user–item structure.
- Non-negative edge weights wij represent relationship strength, forming the |U| × |P| matrix W.
- The model uses weighted-degree diagonal matrices Du and Dp for the two vertex types and treats edges as undirected.
- The input includes graph weights and query vectors encoding prior beliefs, while the output maps every vertex to a real-valued ranking score.
4 ITERATIVE BIRANK
BiRank ranks bipartite-graph vertices by iteratively combining normalized graph structure with query-vector priors. The method has a unique stationary solution, scales linearly with sparse graph edges, and offers convergence guarantees and rate analysis.
- BiRank Design: Symmetric normalization suppresses contributions from high-degree vertices, reducing the dependence of top rankings on hubs.Each edge weight is normalized by the weighted degrees of both connected vertices.
- BiRank Design: BiRank incorporates partial query information directly into ranking rather than combining a graph ranking with priors only in post-processing.This design addresses settings such as recommendation, where known preferences cover only a small proportion of vertices.
- BiRank Design: BiRank iteratively updates vertex scores using graph connections and query vectors, starting from random initialization until convergence.The algorithm repeatedly applies its update rule and returns the two ranking vectors.
- Time Complexity Analysis: O(c|E|) real-time cost makes BiRank linear in graph edges for sparse matrices, and about 10 iterations usually suffice for convergence.Sparse storage processes nonzero entries corresponding to graph edges; c denotes the iterations executed.
- Proof of Convergence: BiRank converges to a stationary and unique solution regardless of initialization.The paper also derives a closed-form stationary solution, although matrix inversion can be more expensive than iteration on large graphs.
- Speed of Convergence: The convergence rate depends on the second-largest eigenvalue magnitude of S^T S and slows as α and β increase.For sparse relational data, a small second dominant eigenvalue can yield fast convergence.
5 FOUNDATIONS OF BIRANK
BiRank is grounded in a regularization framework that combines graph smoothness with fidelity to vertex priors. The framework also establishes Bayesian and n-partite extensions, including an efficient iterative generalization.
- Regularization framework: BiRank iterations implicitly optimize a regularization objective rather than only performing traditional graph ranking updates.The objective is connected directly to the BiRank iteration through coordinate optimization.
- Convergence and optimality: The regularization objective is strictly convex, so BiRank converges to its unique global minimum.Positive definiteness of the Hessian establishes strict convexity and uniqueness.
- Regularization framework: The regularization function enforces smooth scores across connected vertices while fitting scores to the query vector.Its smoothness term penalizes score variation on edges, while fitting terms keep vertex scores near prior scores.
- Bayesian interpretation: A Bayesian formulation makes BiRank equivalent to posterior maximization for latent vertex scores generating the observed query vectors.The graph weights define the prior, while latent scores generate the observed query vectors.
- n-partite extension: The n-partiteRank extension alternates updates across multiple vertex types, recovers BiRank when n = 2, and runs linearly in the number of graph edges.Hyperparameters weight graph substructures, and the converged updates produce rankings for n-partite graphs.
6 APPLICATIONS
The paper applies BiRank to popularity prediction and personalized recommendation by combining weighted user–item interactions with query vectors that encode ranking hypotheses or user preferences. It extends the approach to tripartite graphs for aspect-aware recommendation.
- Popularity Prediction: Popularity prediction uses user comments as accessible feedback because external observers often cannot obtain item view histories.Comments expose historical activity through a single crawl, but their sparsity motivates incorporating additional popularity signals.
- Popularity Prediction: BiRank models users and items as a weighted bipartite graph, with edge weights representing commenting behavior and query vectors encoding popularity hypotheses.The model incorporates temporal recency, user social influence, and current item popularity through graph weights and priors.
- Popularity Prediction: The BiRank iteration mutually reinforces user influence and item popularity while partially preserving the original query-vector settings.Recent comments raise an item's score, and higher item popularity increases the commenting user's influence.
- Personalized Recommendation: For personalized recommendation, BiRank propagates a target user's item preferences through user–item interactions to model collaborative filtering.In the toy example, stronger connection to the rated item gives u2 a higher score than u3, leading p2 to outrank p3 when corresponding edge weights are identical.
- Personalized Recommendation: TriRank extends the method to users, items, and aspects, using review-mentioned properties as an additional source of preference information.Item and aspect query vectors encode the target user's prior interactions and aspect preferences, respectively.
7 EXPERIMENTS
The experiments evaluate BiRank on synthetic data for convergence and time efficiency, then assess its performance on real-world popularity prediction and personalized recommendation tasks.
- Experimental Design: Experiments study BiRank's convergence and time efficiency on synthetic data and evaluate its performance on two real-world ranking applications.The applications are popularity prediction and personalized recommendation.
7.1 Experiments on Synthetic Data
Synthetic experiments test whether BiRank reaches its regularization optimum, how α and β affect convergence, and whether runtime scales with graph size. BiRank converges to the unique optimum quickly, while per-iteration runtime grows linearly with edge count.
- Experimental settings: The experiments used uniformly sampled random graphs and power-law graphs designed to reflect real-world sparsity patterns.Random graph density and power-law structure were controlled during graph generation.
- Experimental settings: The empirical study reports representative settings because findings were consistent across many experimental configurations.
- Convergence to optimum: BiRank reached the unique optimum of its regularization function across random and power-law synthetic graphs.The iterative ranking vector matched the directly calculated stationary solution in all four tested cases.
- Convergence to optimum: BiRank typically converged within 10 iterations, with the deepest descents occurring during early iterations.
- Convergence rate: Higher α and β increase the number of iterations required for convergence because they increase the influence of neighbor-score diffusion.The convergence threshold for Vector Diff was 0.0001.
- Time efficiency: 0.9 seconds per iteration at 2M edges increased to 9 seconds at 20M edges, demonstrating linear runtime growth with edge count.The implementation used sparse matrices and a single CPU thread.
7.2 Evaluation of Popularity Prediction
Popularity prediction evaluates BiRank on three Web 2.0 datasets using future views as ground truth and Spearman agreement as the ranking metric. Bipartite graph methods outperform other approaches, with BiRank generally strongest and best on YouTube and Flickr.
- Experimental settings: The evaluation used future views received during the three days after the crawl date as ground truth and Spearman coefficient for ranking agreement.
- Performance comparison: BiRank, Co-HITS, and BGER significantly outperformed other methods by modeling all three proposed ranking hypotheses.
- Performance comparison: BiRank achieved the best overall performance and was best on the YouTube and Flickr datasets.Co-HITS performed best on Last.fm.
- Performance comparison: BiRank’s improvements over Co-HITS and BGER on YouTube and Flickr were consistent and statistically significant with p < 0.01.The result was obtained through 10-fold cross-validation and one-sample paired t-tests.
- Performance comparison: PageRank performed poorly on Flickr and Last.fm, indicating that item centrality alone was insufficient for accurate popularity prediction.The comparison also highlights the importance of separately handling the two vertex types.
- Baseline analysis: CCP outperformed the multivariate linear model despite using only three days of comment history instead of 30 days.The authors attribute this pattern to short-term prediction and comment sparsity.
7.3 Evaluation of Personalized Recommendation
Personalized recommendation is evaluated on Yelp5 and Amazon Electronics using chronological train, validation, and test splits. TriRank consistently outperforms all baselines, while BiRank leads among collaborative-filtering methods.
- Experimental settings: The evaluation filtered users and items with fewer than 10 reviews and assessed top-K rankings using Hit Ratio and NDCG.
- Experimental settings: Each user’s first 80% of chronological reviews were used for training, followed by 10% validation and 10% testing.
- Performance comparison: TriRank consistently outperformed all baselines on NDCG from positions 10 to 50, with statistically significant improvements at p < 0.01.Hit Ratio showed a similar trend.
- Baseline analysis: ItemPop performed weakly on Amazon and was omitted from its figure to emphasize the other methods.The results indicate that personalized preferences matter beyond item popularity.
- Performance comparison: BiRank achieved the best performance among collaborative-filtering methods on both datasets.It improved over ItemKNN and PureSVD by about 8.3% relatively.
- Performance comparison: TriRank improved over BiRank by more than 10% relatively and significantly outperformed PageRank and TagRW.Review-based methods generally improved over methods using only user–item relationships.
8 CONCLUSION
The paper presents BiRank as a generic ranking method for bipartite and n-partite graphs that combines graph structure with prior knowledge. It is theoretically guaranteed to converge and is interpreted through regularization and Bayesian views.
- Conclusion: BiRank ranks vertices using both graph structure and prior knowledge, with an extension to more general n-partite graphs.
- Conclusion: BiRank is theoretically guaranteed to converge to a stationary solution.
- Conclusion: The method admits both regularization and Bayesian interpretations, supporting principled future extensions.
- Future work: Future work includes adapting parameters using validation data or integrating over parameters under a Bayesian network formalism.