Network alignment is a critical steppingstone behind a variety of multi-network mining tasks. Most of the existing methods essentially optimize a Frobenius-like distance or ranking-based loss, ignoring the underlying geometry of graph data. Optimal transport (OT), together with Wasserstein distance, has emerged to be a powerful approach accounting for the underlying geometry explicitly. Promising as it might be, the state-of-the-art OT-based alignment methods suffer from two fundamental limitations, including (1) effectiveness due to the insufficient use of topology and consistency information and (2) scalability due to the non-convex formulation and repeated computationally costly loss calculation. In this paper, we propose a position-aware regularized optimal transport framework for network alignment named PARROT. To tackle the effectiveness issue, the proposed PARROT captures topology information by random walk with restart, with three carefully designed consistency regularization terms. To tackle the scalability issue, the regularized OT problem is decomposed into a series of convex subproblems and can be efficiently solved by the proposed constrained proximal point method with guaranteed convergence. Extensive experiments show that our algorithm achieves significant improvements in both effectiveness and scalability, outperforming the state-of-the-art network alignment methods and speeding up existing OT-based methods by up to 100 times.
User-side group fairness is crucial for modern recommender systems, alleviating performance disparities among user groups defined by sensitive attributes like gender, race, or age. In the everevolving landscape of user-item interactions, continual adaptation to newly collected data is crucial for recommender systems to stay aligned with the latest user preferences. However, we observe that such continual adaptation often worsen performance disparities. This necessitates a thorough investigation into user-side fairness in dynamic recommender systems. This problem is challenging due to distribution shifts, frequent model updates, and nondifferentiability of ranking metrics. To our knowledge, this paper presents the first principled study on ensuring user-side fairness in dynamic recommender systems. We start with theoretical analyses on fine-tuning v.s. retraining, showing that the best practice is incremental fine-tuning with restart. Guided by our theoretical analyses, we propose FAir Dynamic rEcommender (FADE), an end-to-end fine-tuning framework to dynamically ensure user-side fairness over time. To overcome the non-differentiability of recommendation metrics in the fairness loss, we further introduce Differentiable Hit (DH) as an improvement over the recent NeuralNDCG method, not only alleviating its gradient vanishing issue but also achieving higher efficiency. Besides that, we also address the instability issue of the fairness loss by leveraging the competing nature between the recommendation loss and the fairness loss. Through extensive experiments on real-world datasets, we demonstrate that FADE effectively and efficiently reduces performance disparities with little sacrifice in the overall recommendation performance.
Network embedding plays an important role in a variety of social network applications. Existing network embedding methods, explicitly or implicitly, can be categorized into positional embedding (PE) methods or structural embedding (SE) methods. Specifically, PE methods encode the positional information and obtain similar embeddings for adjacent/close nodes, while SE methods aim to learn identical representations for nodes with the same local structural patterns, even if the two nodes are far away from each other. The disparate designs of the two types of methods lead to an apparent dilemma in that no embedding could perfectly capture both positional and structural information. In this paper, we seek to demystify the underlying relationship between positional embedding and structural embedding. We first point out that the positional embedding can produce the structural embedding with simple transformations, while the opposite direction cannot hold. Based on this finding, a novel network embedding model PACER is proposed, which optimizes the positional embedding with the help of random walk with restart (RWR) proximity distribution, and such positional embedding is then used to seamlessly obtain the structural embedding with simple transformations. Furthermore, two variants of PACER are proposed to handle node classification task on homophilic and heterophilic graphs. Extensive experiments on 17 datasets show that PACER achieves comparable or better performance than the state-of-the-arts.