User-User interaction recommendation, or interaction recommendation, is an indispensable service in social platforms, where the system automatically predicts with whom a user wants to interact. In real-world social pl...
详细信息
ISBN:
(纸本)9781450390965
User-User interaction recommendation, or interaction recommendation, is an indispensable service in social platforms, where the system automatically predicts with whom a user wants to interact. In real-world social platforms, we observe that user interactions may occur in diverse scenarios, and new scenarios constantly emerge, such as new games or sales promotions. There are two challenges in these emerging scenarios: (1) The behavior of users on the emerging scenarios could be different from existing ones due to the diversity among scenarios;(2) Emerging scenarios may only have scarce user behavioral data for model learning. Towards these two challenges, we present KoMEN, a Domain Knowledge Guided Meta-learning framework for Interaction Recommendation. KoMEN first learns a set of global model parameters shared among all scenarios and then quickly adapts the parameters for an emerging scenario based on its similarities with the existing ones. There are two highlights of KoMEN: (1) KoMEN customizes global model parameters by incorporating domain knowledge of the scenarios (e.g., a taxonomy that organizes scenarios by their purposes and functions), which captures scenario inter-dependencies with very limited training. (2) KoMEN learns the scenario-specific parameters through a mixture-of-expert architecture, which reduces model variance resulting from data scarcity while still achieving the expressiveness to handle diverse scenarios. Extensive experiments demonstrate that KoMEN achieves state-of-the-art performance on a public benchmark dataset and a large-scale real industry dataset. Remarkably, KoMEN improves over the best baseline w.r.t. weighted ROC-AUC by 2.14% and 2.03% on the two datasets, respectively. Our code is available at: https://***/Veronicium/koMen.
In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is upda...
详细信息
ISBN:
(纸本)9781450356398
In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, D-CoSim, for accurate CoSimRank search over evolving graphs. Based on D-CoSim, we also propose a fast scheme, F-CoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that D-CoSim and F-CoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores S, F-CoSim is based on three ideas: (i) It first finds a "spanning polytree" T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores S(T) over the "spanning polytree" T. (iii) On G, D-CoSim is employed to compute the changes of S(T) in response to the delta graph (G circle minus T). Experimental evaluations verify the superiority of D-CoSim over evolving graphs, and the fast speedup of F-CoSim on large-scale static graphs against its competitors, without any loss of accuracy.
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting s - t mincuts (and by duality, the values of s - t maxflows) for all pairs of vertices s and t in an undirected graph. Gom...
详细信息
ISBN:
(纸本)9781450380539
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting s - t mincuts (and by duality, the values of s - t maxflows) for all pairs of vertices s and t in an undirected graph. Gomory and Hu showed that it can be computed using n - 1 exact maxflow computations. Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50 years later, even for approximate mincuts. In this paper, we break this longstanding barrier and give an algorithm for computing a (1 + epsilon)-approximate Gomory-Hu tree using polylog(n) maxflow computations. Specifically, we obtain the runtime bounds we describe below. We obtain a randomized (Monte Carlo) algorithm for undirected, weighted graphs that runs in (O) over tilde (m + n(3/2)) time and returns a (1 + epsilon)-approximate Gomory-Hu tree algorithm whp. Previously, the best running time known was (O) over tilde (n(5/2)), which is obtained by running Gomory and Hu's original algorithm on a cut sparsifier of the graph. Next, we obtain a randomized (Monte Carlo) algorithm for undirected, unweighted graphs that runs in m(4/3+o(1)) time and returns a (1 + epsilon)-approximate Gomory-Hu tree algorithm whp. This improves on our first result for sparse graphs, namely m = o(n(9/8)). Previously, the best running time known for unweighted graphs was (O) over tilde (mn) for an exact Gomory-Hu tree (Bhalgat et al., STOC 2007);no better result was known if approximations are allowed. As a consequence of our Gomory-Hu tree algorithms, we also solve the (1 + epsilon)-approximate all pairs mincut (APMC) and single source mincut (SSMC) problems in the same time bounds. (These problems are simpler in that the goal is to only return the s - t mincut values, and not the mincuts.) This improves on the recent algorithm for these problems in (O) over tilde (n(2)) time due to Abboud et al. (FOCS 2020).
The need to find nodes with large eccentricity arises in many heuristic algorithms for ordering sparse matrix equations. A computer program is presented here for finding such nodes, based on an algorithm due to Gibbs,...
详细信息
This article provides a methodology for construction of data transfer paths through DTN dynamic network, implemented with the devices mounted on moving objects and connected via WI-FI, Bluetooth and LTE D2D. The metho...
详细信息
ISBN:
(纸本)9783319463018;9783319463001
This article provides a methodology for construction of data transfer paths through DTN dynamic network, implemented with the devices mounted on moving objects and connected via WI-FI, Bluetooth and LTE D2D. The methodology covers all the five stages of the Knowledge Discovery in Databases technology. The stage of application of Data Mining tools was studied in more detail. It is based on the application of fuzzy logic instrument to select subset that meet the network parameters from a set of moving objects. Further application to the subset of related objects of Yen's algorithm of search for optimal paths on a weighted graph with weights of the grade of the selected subset ownership of the object allows to build the most credible data transfer path and several alternative paths, ranked by descending of data delivery probability.
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = ( V, E) with edge weights w : E -> R, two terminals s and t in G, find two internally vertex-dis...
详细信息
ISBN:
(纸本)9783959773119
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph G = ( V, E) with edge weights w : E -> R, two terminals s and t in G, find two internally vertex-disjoint paths between s and t with minimum total weight. As shown recently by Schlotter and Sebo (2022), this problem becomes NP-hard if edges can have negative weights, even if the weight function is conservative, i.e., there are no cycles in G with negative total weight. We propose a polynomial-time algorithm that solves the SHORTEST TWO DISJOINT PATHS problem for conservative weights in the case when the negative-weight edges form a constant number of trees in G.
The traditional network flow estimation requires monitoring on every node which consumes too much resource. So how to increase the deployment of new distributed monitors as the network expanding is becoming a new rese...
详细信息
ISBN:
(纸本)9783642275517
The traditional network flow estimation requires monitoring on every node which consumes too much resource. So how to increase the deployment of new distributed monitors as the network expanding is becoming a new research focus. This paper analyses the monitors adding mechanism and present a novel algorithm for finding candidate locations for additional deployment in the network. The algorithm is based on Apriori search method that combines with the link weight change algorithm that aims to facilitate origin-destination flow computation. We also develop the greedy algorithm with Group Betweenness Centrality(GBC) involved for the purpose of comparing. The result shows that the new algorithm need less additional monitors than greedy algorithm.
In this paper we give a linear algorithm to edge partition a toroidal graph, i.e., graph that can be embedded on the orientable surface of genus one without edge crossing, into three forests plus a set of at most thre...
详细信息
暂无评论