Online bipartite matching and allocation models are widely
used to analyze and design markets such as Internet advertising,
online labor, and crowdsourcing. Traditionally, vertices
on one side of the market are fixed and known a priori, while
vertices on the other side arrive online and are matched by a
central agent to the offline side. The issue of possible conflicts
among offline agents emerges in various real scenarios when
we need to match each online agent with a set of offline agents.
For example, in event-based social networks (e.g., Meetup),
offline events conflict for some users since they will be unable
to attend mutually-distant events at proximate times; in advertising
markets, two competing firms may prefer not to be
shown to one user simultaneously; and in online recommendation
systems (e.g., Amazon Books), books of the same type
“conflict” with each other in some sense due to the diversity
requirement for each online buyer.
The conflict nature inherent among certain offline agents raises
significant challenges in both modeling and online algorithm
design. In this paper, we propose a unifying model, generalizing
the conflict models proposed in (She et al., TKDE
2016) and (Chen et al., TKDE 16). Our model can capture
not only a broad class of conflict constraints on the offline
side (which is even allowed to be sensitive to each online
agent), but also allows a general arrival pattern for the online
side (which is allowed to change over the online phase). We
propose an efficient linear programming (LP) based online
algorithm and prove theoretically that it has nearly-optimal
online performance. Additionally, we propose two LP-based
heuristics and test them against two natural baselines on both
real and synthetic datasets. Our LP-based heuristics experimentally
dominate the baseline algorithms, aligning with our
theoretical predictions and supporting our unified approach.
more »
« less
Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity
In bipartite matching problems, vertices on one side of a bipartite
graph are paired with those on the other. In its online
variant, one side of the graph is available offline, while the
vertices on the other side arrive online. When a vertex arrives,
an irrevocable and immediate decision should be made
by the algorithm; either match it to an available vertex or
drop it. Examples of such problems include matching workers
to firms, advertisers to keywords, organs to patients, and
so on. Much of the literature focuses on maximizing the total
relevance—modeled via total weight—of the matching.
However, in many real-world problems, it is also important
to consider contributions of diversity: hiring a diverse pool of
candidates, displaying a relevant but diverse set of ads, and so
on. In this paper, we propose the Online Submodular Bipartite
Matching (OSBM) problem, where the goal is to maximize
a submodular function f over the set of matched edges.
This objective is general enough to capture the notion of both
diversity (e.g., a weighted coverage function) and relevance
(e.g., the traditional linear function)—as well as many other
natural objective functions occurring in practice (e.g., limited
total budget in advertising settings). We propose novel algorithms
that have provable guarantees and are essentially optimal
when restricted to various special cases. We also run
experiments on real-world and synthetic datasets to validate
our algorithms.
more »
« less
- Award ID(s):
- 1749864
- NSF-PAR ID:
- 10111461
- Date Published:
- Journal Name:
- AAAI Conference on Artificial Intelligence (AAAI)
- Page Range / eLocation ID:
- 1877-1884
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Recently, considerable research attention has been paid to graph embedding, a popular approach to construct representations of vertices in latent space. Due to the curse of dimensionality and sparsity in graphical datasets, this approach has become indispensable for machine learning tasks over large networks. The majority of the existing literature has considered this technique under the assumption that the network is static. However, networks in many applications, including social networks, collaboration networks, and recommender systems, nodes, and edges accrue to a growing network as streaming. A small number of very recent results have addressed the problem of embedding for dynamic networks. However, they either rely on knowledge of vertex attributes, su er high-time complexity or need to be re-trained without closed-form expression. Thus the approach of adapting the existing methods designed for static networks or dynamic networks to the streaming environment faces non-trivial technical challenges. These challenges motivate developing new approaches to the problems of streaming graph embedding. In this paper, we propose a new framework that is able to generate latent representations for new vertices with high e ciency and low complexity under speci ed iteration rounds. We formulate a constrained optimiza- tion problem for the modi cation of the representation resulting from a stream arrival. We show this problem has no closed-form solution and instead develop an online approximation solution. Our solution follows three steps: (1) identify vertices a ected by newly arrived ones, (2) generating latent features for new vertices, and (3) updating the latent features of the most a ected vertices. The new representations are guaranteed to be feasible in the original constrained optimization problem. Meanwhile, the solution only brings about a small change to existing representations and only slightly changes the value of the objective function. Multi-class clas- si cation and clustering on ve real-world networks demonstrate that our model can e ciently update vertex representations and simultaneously achieve comparable or even better performance compared with model retraining.more » « less
-
Butterflies are the smallest non-trivial subgraph in bipartite graphs, and therefore having efficient computations for analyzing them is crucial to improving the quality of certain applications on bipartite graphs. In this paper, we design a framework called ParButterfly that contains new parallel algorithms for the following problems on processing butterflies: global counting, per-vertex counting, per-edge counting, tip decomposition (vertex peeling), and wing decomposition (edge peeling). The main component of these algorithms is aggregating wedges incident on subsets of vertices, and our framework supports different methods for wedge aggregation, including sorting, hashing, histogramming, and batching. In addition, ParButterfly supports different ways of ranking the vertices to speed up counting, including side ordering, approximate and exact degree ordering, and approximate and exact complement coreness ordering. For counting, ParButterfly also supports both exact computation as well as approximate computation via graph sparsification. We prove strong theoretical guarantees on the work and span of the algorithms in ParButterfly. We perform a comprehensive evaluation of all of the algorithms in ParButterfly on a collection of real-world bipartite graphs using a 48-core machine. Our counting algorithms obtain significant parallel speedup, outperforming the fastest sequential algorithms by up to 13.6× with a self-relative speedup of up to 38.5×. Compared to general subgraph counting solutions, we are orders of magnitude faster. Our peeling algorithms achieve self-relative speedups of up to 10.7× and outperform the fastest sequential baseline by up to several orders of magnitude.more » « less
-
null (Ed.)more » « less
Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e.g., country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application. The source code is made available at https://github.com/faezahmed/diverse_matching.
-
Abstract We develop a framework for incorporating edge-dependent vertex weights (EDVWs) into the hypergraph minimum s - t cut problem. These weights are able to reflect different importance of vertices within a hyperedge, thus leading to better characterized cut properties. More precisely, we introduce a new class of hyperedge splitting functions that we call EDVWs-based, where the penalty of splitting a hyperedge depends only on the sum of EDVWs associated with the vertices on each side of the split. Moreover, we provide a way to construct submodular EDVWs-based splitting functions and prove that a hypergraph equipped with such splitting functions can be reduced to a graph sharing the same cut properties. In this case, the hypergraph minimum s - t cut problem can be solved using well-developed solutions to the graph minimum s - t cut problem. In addition, we show that an existing sparsification technique can be easily extended to our case and makes the reduced graph smaller and sparser, thus further accelerating the algorithms applied to the reduced graph. Numerical experiments using real-world data demonstrate the effectiveness of our proposed EDVWs-based splitting functions in comparison with the all-or-nothing splitting function and cardinality-based splitting functions commonly adopted in existing work.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
