# Single-peaked domains with designer uncertainty 111Guidance by Arunava Sen
and Debasis Mishra is gratefully acknowledged. I am also thankful to Stephen
Morris and Alex Wolitzky for insightful comments.

Aroon Narayanan 222Department of Economics, MIT

###### Abstract

This paper studies single-peaked domains where the designer is uncertain about
the underlying alignment according to which the domain is single-peaked. The
underlying alignment is common knowledge amongst agents, but preferences are
private knowledge. Thus, the state of the world has both a public and private
element, with the designer uninformed of both. I first posit a relevant
solution concept called implementation in mixed information equilibria, which
requires Nash implementation in the public information and dominant strategy
implementation in the private information given the public information. I then
identify necessary and sufficient conditions for social rules to be
implementable. The characterization is used to identify unanimous and
anonymous implementable social rules for various belief structures of the
designer, which basically boils down to picking the right rules from the large
class of median rules identified by Moulin (1980), and hence this result can
be seen as identifying which median rules are robust to designer uncertainty.

Keywords: social choice function, single-peakedness, implementation, designer
uncertainty

JEL Classification: D71

##  1 Introduction

Consider the following situation: a group of people, say voters, need to
select an alternative, say a political party, amongst many that are available
to them. An independent authority is established to determine what the
selection rule should be i.e. what alternative to select based on the
preferences of each person in the group. In many such situations, it is
reasonable to assume that the agents, probably after much discussion amongst
themselves, have a common concern, such as national defence. They would each
have some ideal amount of national defense spend in mind, which would
correspond to their “peak", and they would find any amount farther away from
this peak less attractive than amounts that are closer to it. This captures
their preference over the alternatives. In evaluating the parties based on
their position on how much to spend on national defense, the voters thus find
themselves having “single-peaked preferences" over them. This basically means
that if a party proposes a spend closer to a voter’s peak, the voter will like
it more.

First introduced by Black (1948), single-peaked domains were studied
extensively by Moulin (1980). Since then, the literature has studied them in
the context of some properties of rules that seem quite natural: first,
everybody should find it optimal to report their true preference regardless of
what the others say they prefer, second, if everyone agrees on an alternative,
then that should be chosen, and third, every agent should be ex-ante equal.
These are the properties of strategy-proofness, unanimity, and anonymity,
respectively. A nice class of rules - the median rules - satisfy these
conditions, and in fact only they satisfy these conditions. Essentially such
rules pick the median of the $n$ reported peaks and $n-1$ fixed “phantom
peaks", using an exogenous underlying alignment according to which the
preferences of the agents are known to be single-peaked. Each median rule can
be uniquely identified by these $n-1$ “phantom peaks". Moulin (1980) also
showed that an even more general characterization of rules - which Sprumont
(1995) terms min-max rules - can be obtained if one drops anonymity.

However, in this analysis it was important to assume that the underlying
alignment according to which everyone evaluates the alternatives is known to
the authority. In many situations, this may not be reasonable since the
authority may not be privy to such information. For example, when the
legislature sets up a committee to decide funding for a program, it is quite
likely that the committee members will arrive at a common concern after
discussions, and then vote for the optimal funding based on that concern. But
it is unlikely that the legislature would know the specific concern
beforehand. It would then be prudent to set up a rule that accounts for this
uncertainty. It may even be the case that priorities that produce such
alignments amongst voters changes drastically over time. Witness the
remarkable realignment in the United States Democratic Party’s position on
race, from being anti-abolitionist in the 19th century to passing the Voting
Rights Act in the 20th century. It is reasonable to expect that long-lasting
rules be designed keeping such shifting alignments in mind. Applications also
extend to similar settings in auctions, regulation and a variety of other
domains.

The objective of this paper is to identify social rules that will be robust to
the designer’s uncertainty about the underlying ordering. In particular, we
would like to relate this to Moulin’s class of median rules. Given $m$
alternatives and $n$ players, his median class contains ${m+n-2}\choose{n-1}$
rules for each possible underlying alignment. Clearly a designer then faces a
problem of plenty, and we would like our results to help her in identifying
which of these will have this additional property i.e. the property of being
robust to uncertainty about the underlying ordering.

In order to achieve this objective, it is imperative to first formalize what
this robustness notion should be. Note that the information of each agent can
be split into two - a public state, which is the underlying alignment, and a
private state, which is his own preference. The state of the world then is
composed of an alignment that is in the support of the designer’s belief and a
profile of preferences that is single-peaked according to this alignment, and
any SCF picks an alternative for each state. Given the mixed information
nature of our setting, we posit a suitable solution concept for implementation
of SCFs. With respect to the underlying alignment, which is common knowledge
amongst the agents, we require Nash implementation. Then, given that the
underlying alignment is being truthfully revealed, we require implementation
in dominant strategies with respect to the private information i.e. their
preferences.

Of course, applying our solution concept directly to rules is cumbersome, and
hence first we must obtain a characterization of this concept in terms of
easy-to-check conditions on social rules. By the first requirement,
implementable SCFs will be strategy proof for states that share the same
alignment. By the second, they will have to satisfy a condition that we called
shared-monotonicity, which requires that across two states that share a
preference profile, the SCF must choose the same outcome at that profile. This
is due to the lower contour sets of agents matching exactly for agents with
such preferences across the two states, which leads to Nash equilibria in one
state being Nash equilibria in the other. These conditions, with no veto
power, also turn out to be sufficient.

This characterization enables us to carry out our original objective -
identify robust unanimous and anonymous SCFs. In fact, this objective had a
greater role in inspiring the kind of solution concept that we use than may be
apparent from the deductive narrative we have laid out so far. The axioms
characterizing the solution are such that adding unanimity and anonymity
implies that implementable SCFs, fixing an alignment from the set of all
alignments that the designer believes plausible, must be Moulin’s median
rules. We can then check which median rules satisfy the additional conditions
imposed by implementability for some interesting belief structures of the
designer. This then enables us to cleanly answer some of the question of
robustness within Moulin’s class that inspired us. In fact, this will form the
bulk of our study. The most important of these is the case when the designer
believes that the preferences may have been generated by any possible
alignment - in this case, only the true median rule, i.e. the rule that picks
the median of the reported peaks of the agents, survives the demanding notion
of implementability. We also derive results for other interesting forms of
designer uncertainty.

We are not aware of any paper that studies settings in which the state of the
world has both public and private elements. In that sense, our setting is
novel. There are papers that look at domains which feature multiple single-
peaked domains devoid of any asymmetry in information between the designer and
the agents about the alignments, such Reffgen (2015). Another related strand
of literature studies single-peaked preferences on multi-dimensional domains,
as in Barberà et al. (1993), Border and Jordan (1983), and Heal and
Chichilnisky (1995).

##  2 Model

The environment is the tuple $(N,X,\mathcal{P},\mu)$ where $N:=\\{1,...,n\\}$
is a set of $n$ agents, $X$ is a finite set of alternatives, $\mathcal{P}$ is
the set of all strict alignments over $X$, and $\mu$ is a non-degenerate
probability distribution over $\mathcal{P}$. We assume $n\geq 3$.

The agents in this setting have single-peaked preferences according to some
alignment in the support of $\mu$ 333Note that any alignment and its exact
reverse, for example $a\succ b\succ c$ and $c\succ b\succ a$, produce the same
single-peaked domain, and hence are equivalent for our purposes. All claims
pertain to this equivalence class., and this alignment is common knowledge
amongst them. $\mu$ represents the designer’s belief over which possible
alignment could be underlying the agents’ preferences. The preferences of
agents are private knowledge, i.e. unknown to both other agents and the
designer.

Throughout this study, we will attempt to derive results that do not depend
heavily on the specific prior the designer has. This will be achieved by
working with only the support of the prior, so that our results will be robust
to small changes in the probability assigned to the alignments in the support
of the prior.

We assume wlog that the message space of each agent $i$ in any mechanism must
be of the form $M_{i}=L_{i}\times\mathcal{K}$ where $L_{i}$ is allowed to be
any arbitrary space, and $\mathcal{K}\subseteq\mathcal{P}\times\mathcal{P}$
contains elements of the form $(\succ,P_{i})$ where $P_{i}$ is single-peaked
according to $\succ$.

######  Definition 1.

A mechanism is the tuple $(M,g)$ where $M=(M_{i})_{i\in N}$ is the message
space and $g:M\to X$ assigns an outcome to each message profile.

Let $\Theta$ denote the set of all states. Then, for any state
$\theta\in\Theta$, we can represent it as
$\theta=(\succ^{\theta},(P^{\theta}_{i})_{i\in N})$, where $\succ^{\theta}$ is
an alignment in the support of $\mu$ and represents the public state while
$P^{\theta}_{i}$ represents the private state of agent $i$. The tuple
$(P^{\theta}_{i})_{i\in N}$ identifies a profile of preferences that is
single-peaked according to the public state.

######  Definition 2.

A social choice function $f:\Theta\to X$ assigns an alternative to each state
$\theta$.

Finally, we formally define the solution concept that we set forth in the
introduction. The idea is simple and intuitive - we require Nash
implementation in the public component and dominant strategy implementation in
the private component of the state given truthful reporting of the public
component. Essentially, Nash implementation in the public component ensures
nobody has an incentive to unilaterally misreport the common ordering. Then,
given the common ordering is being reported truthfully, dominant strategy
implementation ensures that the private preferences are also reported
truthfully.

######  Definition 3.

A mechanism $(M,g)$ implements a social choice function $f$ in mixed
information equilibria if for every state
$\theta=(\succ^{\theta},(P^{\theta}_{i})_{i\in N})$ there exists a message
$m^{*}=(l^{*}_{i},\succ^{\theta},(P^{\theta}_{i})_{i\in N})$ such that
$g(m^{*})=f(\theta)$ and we have:

  1. 1.

Nash implementation in public information:

     * •

for all $i$,

$g(m^{*}_{i},(l_{-i},\succ^{\theta},P^{\theta}_{-i}))\ R^{\theta}_{i}\
g((l_{i},\succ^{{}^{\prime}},P^{{}^{\prime}}_{i}),(l_{-i},\succ^{\theta},P^{{}^{\prime}}_{-i}))$

for all $(l_{i})_{i\in N}$, for all
$(\succ^{{}^{\prime}},P^{{}^{\prime}}_{i})\in\mathcal{K}$

     * •

if $\bar{m}$ is a Nash equilibrium and
$\bar{m}_{i}=(\bar{l}_{i},\bar{\succ}_{i},P^{\theta}_{i})$ for some
$(\bar{l}_{i},\bar{\succ}_{i})$, then $g(\bar{m})=g(m^{*})$

  2. 2.

Dominant strategy implementation in private information given truthful public
state reporting: for all $i$,

$g(m^{*}_{i},(l_{-i},\succ^{\theta},P_{-i}^{{}^{\prime}}))\ R^{\theta}_{i}\
g((l_{i},\succ^{\theta},P_{i}^{{}^{\prime}}),(l_{-i},\succ^{\theta},P_{-i}^{{}^{\prime}}))$

for all $(l_{i})_{i\in N}$, for all $P_{i}^{{}^{\prime}}$, for all
$P_{-i}^{{}^{\prime}}$, with strict preference for some
$(l_{-i},\succ^{\theta},P_{-i}^{{}^{\prime}})$

A social choice function $f$ is said to be implementable in mixed information
equilibria if there exists a mechanism that implements it.

To further expand on this definition, the first condition of Nash
implementation requires that agents not be able to unilaterally deviate along
both private and public dimensions while the second ensures that the
equilibrium message is the unique Nash equilibrium with respect to the public
state. This ensures that the public state is conveyed accurately to the
designer. Then, the second condition says that given this public state, we
must have dominant strategy implementation in the private state.

##  3 Implementable choice functions

The primary motive of this study is to understand the nature of choice
functions which can be implemented by the designer in this context. Clearly
the definition above of implementability is onerous to check in practice. The
obvious first step then would be to arrive at a characterization in terms of
some properties that can be directly verified for choice functions, and this
is indeed the step we take. Then, we can apply these properties directly to
the choice functions to identify which of them satisfy these properties.

Our first result will be to identify necessary and sufficient conditions for
SCFs to be implementable in mixed information equilibria. In order to state
the result, a few notions will be required.

Denote by $f_{\succ}$ the SCF $f$ restricted to $\\{\theta=(\succ,P)\\}$ where
$P$ is allowed to be any profile of preferences that is single-peaked
according to $\succ$.

######  Definition 4.

The SCF $f_{\succ}$ is strategy-proof if for every preference $P_{i}$ that is
single-peaked according to $\succ$, either $f_{\succ}(P_{i},P_{-i})$ $P_{i}$
$f_{\succ}(P_{i}^{{}^{\prime}},P_{-i})$ or
$f_{\succ}(P_{i},P_{-i})=f_{\succ}(P_{i}^{{}^{\prime}},P_{-i})$ for all
deviating preference reports $P_{i}^{{}^{\prime}}$ and for all preferences of
the other agents $(P_{-i})$.

######  Definition 5.

The SCF $f$ is shared-monotonic if for all pairs of alignments
$\succ,\succ^{{}^{\prime}}$ such that there exists a profile of preferences
$P$ that is single-peaked according to both $\succ$ and $\succ^{{}^{\prime}}$,
$f(\succ,P)=f(\succ^{{}^{\prime}},P)$.

######  Definition 6.

The SCF $f$ satisfies no veto power (NVP) if for all $\theta=(\succ,P)$ such
that $P_{i}(1)=a$ for all but one agent, then $f(\theta)=a$.

Before we present the theorem, let us try to intuitively understand why these
conditions are relevant to the notion of implementability. Consider any
implementable SCF. By the dominant strategy requirement of implementation, we
must have strategy-proofness of $f_{\succ}$ for all $\succ$ in the support of
the designer’s belief. Hence the necessity of strategy-proofness is obvious.
Moreover, if a message is a Nash equilibrium at a state $\theta$, it will
continue to be a Nash equilibrium for states which share the profile of
preferences in $\theta$, since the lower contour sets coincide exactly for
each player across the states. So if two different alignments generate some
common set of single-peaked preferences, whenever these preferences are held
by agents, the outcomes must also be exactly the same. By the requirement of
Nash implementation in the public information, we must then have shared-
monotonicity.

It turns out that these two conditions, along with NVP, are also sufficient
for any SCF to be implementable. We use a fairly standard mechanism to show
this. Agents are asked to report the state i.e. an alignment and a preference
single-peaked according to that alignment, and also their preferred
alternative and an integer. If at least N-1 agents agree on the alignment,
then that alignment is fixed as the public state. If not, the agent reporting
the highest integer gets his preferred alternative.

######  Theorem 1.

If a social choice function $f$ is implementable in mixed information
equilibria, then $f_{\succ}$ is strategy-proof for all $\succ$ in the support
of $\mu$, and $f$ is shared-monotonic.

Conversely, if a social choice function $f$ is such that $f_{\succ}$ is
strategy-proof for all $\succ$ in the support of $\mu$, $f$ is shared-
monotonic, and $f$ satisfies no veto power, then it is implementable in mixed
information equilibria.

##  4 Implementability of unanimous and anonymous rules

Now, after identifying the right solution concept and the right set of tools
to check for it, we turn towards identifying what implementable rules actually
look like. Recall that our motivation was to apply robustness requirements on
Moulin (1980), looking at unanimous and anonymous rules. This classic paper
led to the characterization that a rule is strategy-proof, unanimous and,
anonymous if and only if it is a generalized median rule. These rules have an
intuitive and appealing visual representation. First, place the alternatives
on a line left to right according to the underlying alignment. Then, place
$n-1$ “phantom top" on the alternatives on the line - each generalized median
rule is associated with a unique placement of these phantom tops. Given any
profile of preferences of the agents, identify each agent’s most preferred
alternative, or “top", and mark them on the line. The outcome of the
generalized median rule is the median of these $n$ agent tops and the $n-1$
phantom tops.

Part of the appeal of these properties lies in their normative nicety. If all
the agents like the same alternative, it would be quite reasonable for a
social rule to assign them that alternative. Equality amongst the agents as
well is a fairly standard requirement. The intuitive nature of the generalized
median rules also adds to the appeal of these properties, since in essence
they are tied to these rules by the characterization. However, importantly,
the class of generalized median rules is vast. In fact, if we have $m$
alternatives and $n$ agents, his result gives us ${m+n-2}\choose{n-1}$ rules
to choose from. Our results will be able to identify which of these will be
robust to designer uncertainty in the underlying alignment.

At this point, we should be more specific by what we mean by designer
uncertainty. We assume that the designer has some belief over the possible
alignments according to which the domain of agents’ preferences is single-
peaked. The result in the previous subsection identifies general conditions on
implementable SCFs. The strength of these conditions, of course, is dependent
on the kind of belief that the designer has. Varying her belief will vary the
type of SCFs that will be implementable. In order to be robust to changes in
belief probabilities, we work with the support of the belief i.e. the designer
only uses information about the alignments that she places a positive
probability on, and not the specific probability that she places on them.

It will also be useful to state Moulin’s result here, since we will draw on it
later.

######  Theorem 2 (Moulin (1980)).

In a single-peaked domain, a social choice function is strategy-proof,
anonymous and unanimous if and only if it is a generalized median rule.

A generalized median rule specifies $n-1$ “phantom" voters who each vote for a
given alternative regardless of the preferences of the agents. The rule
chooses the median of the $n$ most-preferred alternatives of the agents and
these $n-1$ phantom votes. An example is shown in Figure 1 \- note that
$P_{1}$ and $P_{2}$ are the top preferences of the agents and $F_{1}$ is the
fixed phantom vote that identifies the rule.

Figure 1: Moulin’s generalized median SCF.

For us, the following definitions of unanimity and anonymity will be
applicable.

######  Definition 7.

Let $P(1)$ identify the most preferred alternative in $P$, also called its
peak. The SCF $f$ is unanimous if for all preference profiles $(P_{i})$ such
that $P_{i}(1)=a$ for some $a\in X$ and for all $i\in N$, we have
$f(\succ,P)=a$.

######  Definition 8.

The SCF $f$ is anonymous if for all preference profiles $(P_{i})$ and for all
bijective functions $\sigma:N\to N$, we have
$f(\succ,(P_{i}))=f(\succ,(P_{\sigma(i)}))$.

Since implementable SCFs must be strategy-proof for each $\succ$, it is clear
that adding unanimity and anonymity implies that implementable SCFs must have
some median rule for each $f_{\succ}$. A slightly more subtle point relates to
the property of no veto power. Consider what happens when there are no
phantoms of a median rule at one of the two extreme ends. Then, one can always
construct a profile where a single agent would indeed have a veto - for
example with all but one agent having their top preference at the end without
a phantom. At the same time, having at least one phantom on both ends ensures
that there is no veto at any profile.

######  Observation 1.

If an anonymous and unanimous SCF $f$ is implementable, then $f_{\succ}$ must
be a median rule for all alignments $\succ$ in the support of $\mu$. It
satisfies no veto power if and only if each $f_{\succ}$ places at least one
phantom on the extreme ends of $\succ$. We call such SCFs no veto projected
median SCFs (NVPMS).

Figure 2: An NVPMS. Note that the three alignments that the designer believes
possible are $acb$, $abc$, and $bac$. The green arrows represent position of
the phantoms.

We present five results here, progressing in a natural way over possible
beliefs of the designer. First, suppose the designer places positive
probabilities over exactly two alignments, each of which is the reverse of the
other. We may think of this as a good starting point, since the single-peaked
domains produced by each alignment is exactly the same.

######  Observation 2.

Let $\hat{\succ}^{-1}$ denote the alignment where the ordering of alternatives
of $\hat{\succ}$ is exactly reversed. If
$supp(\mu)=\\{\hat{\succ},\hat{\succ}^{-1}\\}$ for some
$\hat{\succ}\in\mathcal{P}$, then any NVPMS with
$f_{\hat{\succ}}=f_{\hat{\succ}^{-1}}$ is implementable.

When the designer is dealing with such a belief, any report of preference
profiles could have been produced by either of the alignments. Shared-
monotonicity then kicks in with full force - it must be the case that the SCFs
chosen for each alignment must then be exactly the same.

This leads us to ask whether there might be cases where shared-monotonicity
might have no bite at all. Indeed, whenever the two sets of single-peaked
preferences for two alignments are disjoint, shared-monotonicity is satisfied
vacuously, and we have the following result.

######  Proposition 1.

Let $\mathcal{D}_{\succ}$ be the set of all preferences that are single-peaked
according to $\succ$. If for all $\succ,\succ^{{}^{\prime}}\in supp(\mu)$,
$\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}=\emptyset$, then any
NVPMS is implementable.

This is a very permissive result, since it gives a free hand to the designer
to choose any median rule for each alignment, as long as it places at least
one phantom on both ends of each alignment.

We would quite naturally be interested to know the circumstances under which
the designer would be much more constrained than this in her choices. Consider
then the case where the designer is uncertain entirely about the underlying
alignment, that is, she places a positive probability over every possible
alignment in $\mathcal{P}$. This would be the case when the designer wants her
mechanism to robust to any possible underlying alignment, for example when
designing a voting system where the voters may end up having any common
concern, or even any change in the alignment over time.

The result for such a belief structure requires a few notations, which we
present before the theorem.

######  Definition 9.

Given $|A|=3$, we call an SCF a symmetric order-statistic SCF if for any
alignment $\succ\ \in\\{abc,bca,cab\\}$ where $a,b,c\in X$, $f{\succ}$ places
$k$ phantoms on the leftmost alternative and $(n-1)-k$ on the rightmost
alternative, with $1\leq k\leq(n-2)$. Note that in alignment $abc$, $a$ is the
leftmost alternative and $c$ is the rightmost alternative.

Figure 3: A symmetric order-statistic SCF. Note that for each alignment, the
phantoms are at the ends and in the same pattern across alignments.

######  Definition 10.

Given $n$ is odd, we call an SCF a true median SCF if $\forall\succ\ \in
supp(\mu)$, $f_{\succ}$ chooses the median of the reported peaks of the
agents.

Figure 4: A true median SCF. Note that all the phantoms must be equally
distributed at the two ends.

######  Theorem 3.

Suppose $supp(\mu)=\mathcal{P}$ and $|A|\geq 3$. Then

  1. 1.

If $|A|=3$, then an SCF is implementable if and only if it is a symmetric
order-statistic mechanism.

  2. 2.

If $n$ is even and $|A|>3$, then there are no implementable SCFs.

  3. 3.

If $n$ is odd and $|A|>3$, then an SCF is implementable if and only if it is
the true median mechanism.

The surprising thing about this result is how it picks a handful of median
rules from the vast class identified by Moulin. From ${m+n-2}\choose{n-1}$
possible rules, these have been whittled down to just $1$ when we have $m>3$
and $n$ is odd. What this means is that if the designer actually has some
(possibly very small) non-zero belief over all possible alignments, she should
choose the true-median so that she can have this additional bulwark of
implementability in mixed information equilibria. This result (and others in
this study) can thus also be seen as identifying special mechanisms within the
class of median rules, so that designers can be assisted in choosing from
within it.

Let us now try to address what happens when we do not have the full support,
but there are still alignments with common preferences in their single-peaked
domains. Because a general characterization is bound to be messy, we consider
an important special case.

######  Definition 11.

Let $T_{\succ,\succ^{{}^{\prime}}}=$ $\\{x\in X\ |\ x=P(1)$ for some
$P\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}\\}$. We say that
the belief $\mu$ has constant shared peaks if
$T_{\succ,\succ^{{}^{\prime}}}=T$ for all $\succ,\succ^{{}^{\prime}}\in
supp(\mu)$, where $T\subseteq X$ is a fixed subset of the set of alternatives.

Figure 5: A set of alignments that have constant shared peaks. All preferences
that are shared across these alignments have peaks on the red colored
alternatives.

In this case, as we show in a lemma that we use to prove our theorems, the
shared peaks must be a contiguous subordering of each alignment, so one can
imagine these tops as being lumped together in the same order, and then the
other alternatives moving around to the left and right of this lump to
generate the entire support. For such beliefs, there is a fairly large
possibility result.

######  Proposition 2.

Suppose $\mu$ has constant shared peaks. Then $T$ is a contiguous subordering
of each alignment in $supp(\mu)$. Denote this subordering by $R$. An SCF is
implementable if it is a projected median mechanism that, given any
$\succ,\succ^{{}^{\prime}}\ \in supp(\mu)$, places

  1. 1.

the same number of phantoms before and after $R$ for both $\succ$ and
$\succ^{{}^{\prime}}$

  2. 2.

at least one phantom on either end of both $\succ$ and $\succ^{{}^{\prime}}$

  3. 3.

the same pattern of phantoms on $R$ for both $\succ$ and $\succ^{{}^{\prime}}$

Proposition 2 admits an interesting corollary. Suppose $|supp(\mu)|=2$. In
this case, regardless of which alignments are part of $supp(\mu)$, either the
two alignments share a given set of preferences or they do not. Thus, the
premise of the proposition is met, and we can identify implementable SCFs.
$|supp(\mu)|=2$ includes practically important situations such as when the
designer is uncertain just about the relative alignment of two adjacent
alternatives.

Finally, we show that if we impose a fairly weak additional assumption, we
again get a very permissive result. Dutta and Sen (2012) Dutta and Sen (2012)
introduced the concept of a “partially honest" agent, who strictly prefers to
reveal the true state as long as he is not worse off.

######  Definition 12.

An agent $i$ is partially honest if given that $\hat{\succ}$ is the true
underlying alignment, and $m,m^{{}^{\prime}}$ are such that
$m_{i}=(\\_,\hat{\succ},\\_)$ and it is not the case that
$g(m^{{}^{\prime}})P_{i}g(m)$, then he strictly prefers to send $m$.

They show that having just one partially honest agent can make it possible to
Nash implement SCFs that satisfy only No Veto Power, doing away with the
otherwise necessary Maskin Monotonocity requirement. Unsurprisingly, this
assumption is strong in our setting as well - in the presence of just one
partially honest agent, we are able to implement a very large class of SCFs,
regardless of the belief structure.

######  Proposition 3.

Let $|supp(\mu)|\geq 3$. Suppose that at least one agent is partially honest.
Then, any NVPMS is implementable.

##  5 Discussion

The primary innovation of this paper is the study of a setting in which the
state of the world has public and private components, with the designer being
uninformed about both components and agents informed of the public state and
their own private state. Settings like this merit practical interest, since
not all information available to an agent can be neatly bucketed into either
something only privately observed or only publicly observed. The solution
concept that we use is relevant for our specific case, but there may be others
or generalizations of the same which could lead to interesting results.

We focus on the single peaked domain since our interest is in answering
questions related to robustness when the designer is not certain about the
underlying alignment of the domain. Our general result on implementation in
mixed information equilibria, which involves Nash implementation in the public
component and dominant strategy implementation in the private component,
identifies necessary and sufficient conditions on SCFs for them to be
implementable. This is in and of itself useful in practice, since these
conditions can be directly checked and it can be verified whether the SCF can
be implemented.

It is for anonymous and unanimous rules that we go further and identify
implementable SCFs. Fixing the public part of the state i.e. the underlying
alignment, implementability necessitates that the SCF behave as a Moulin
generalized median mechanism. Implementability could also impose further
constraints on which median mechanisms these can be, depending on which
alignments are possible. For some sets of alignments, there are no additional
constraints imposed, while if the set of alignments is the set of all possible
alignments, then only one median mechanism is admissible for each alignment.
This is how we answer the robustness questions - depending on which alignments
the designer thinks are possible, she can identify which SCF she should choose
from all of Moulin’s median mechanisms.

A more general question to tackle in this setting would be to identify the
structure of unanimous implementable rules. As alluded to earlier, it is known
that unanimous strategy-proof rules must be “min-max" rules, and the same
questions of robustness to designer uncertainty can be asked about these
rules. Here our choice was to investigate the generalized median rules since
they have an intuitive visualization and also because anonymity is a fairly
standard normative requirement. The literature post Moulin (1980) has also
focused a great deal on median rules for similar reasons.

## References

  * Barberà et al. (1993) Salvador Barberà, Faruk Gul, and Stacchetti Ennio.  Generalized median voter schemes and committees.  _Journal of Economic Theory_ , 61(2):262–289, 1993.  URL https://EconPapers.repec.org/RePEc:eee:jetheo:v:61:y:1993:i:2:p:262-289.
  * Black (1948) Duncan Black.  On the rationale of group decision-making.  _Journal of Political Economy_ , 56(1):23–34, 1948.  ISSN 00223808, 1537534X.  URL http://www.jstor.org/stable/1825026.
  * Border and Jordan (1983) Kim C. Border and J. S. Jordan.  Straightforward elections, unanimity and phantom voters.  _Review of Economic Studies_ , 50(1):153–170, 1983.  URL https://EconPapers.repec.org/RePEc:oup:restud:v:50:y:1983:i:1:p:153-170.
  * Dutta and Sen (2012) Bhaskar Dutta and Arunava Sen.  Nash implementation with partially honest individuals.  _Games and Economic Behavior_ , 74(1):154–169, 2012.
  * Heal and Chichilnisky (1995) Geoffrey Heal and Graciela Chichilnisky.  The geometry of implementation: A necessary and sufficient condition for straightforward games.  Working papers, Columbia - Graduate School of Business, 1995.  URL https://EconPapers.repec.org/RePEc:fth:colubu:95-22.
  * Moulin (1980) H. Moulin.  On strategy-proofness and single peakedness.  _Public Choice_ , 35(4):437–455, Jan 1980.  ISSN 1573-7101.  doi: 10.1007/BF00128122.  URL https://doi.org/10.1007/BF00128122.
  * Reffgen (2015) Alexander Reffgen.  Strategy-proof social choice on multiple and multi-dimensional single-peaked domains.  _Journal of Economic Theory_ , 157:349 – 383, 2015.  ISSN 0022-0531.  doi: https://doi.org/10.1016/j.jet.2014.12.010.  URL http://www.sciencedirect.com/science/article/pii/S0022053114001872.
  * Sprumont (1995) Yves Sprumont.  Strategyproof collective choice in economic and political environments.  _Canadian Journal of Economics_ , 28(1):68–107, 1995.  URL https://EconPapers.repec.org/RePEc:cje:issued:v:28:y:1995:i:1:p:68-107.

##  Appendix A Proofs

###### Proof of Theorem 1.

Let $f$ be an implementable SCF, and let $(M,g)$ be the mechanism that
implements it.

Let $\succ$ be an alignment in the support of $\mu$. Fix an agent $i$. Let
$P_{i}$, $P_{i}^{{}^{\prime}}$ and $P_{-i}^{{}^{\prime}}$ be arbitrary
preferences single peaked according to $\succ$. Then, there exists an $m^{*}$
such that $m^{*}_{i}=(l^{*}_{i},\succ,P_{i})$,
$m^{*}_{-i}=(l^{*}_{-i},\succ,P^{{}^{\prime}}_{-i})$, and
$g(m*)=f(\succ,P_{i},P_{-i}^{{}^{\prime}})$. Also, there exists an $m^{**}$
such that $m^{**}_{i}=(l^{**}_{i},\succ,P_{i}^{{}^{\prime}})$,
$m^{**}_{-i}=(l^{**}_{-i},\succ,P^{{}^{\prime}}_{-i})$, and
$g(m^{**})=f(\succ,P_{i}^{{}^{\prime}},P_{-i}^{{}^{\prime}})$. By dominant
strategy implementation in private information,
$g(m^{*}_{i},(l^{*}_{-i},\succ,P_{-i}^{{}^{\prime}}))\ R_{i}\
g((l^{**}_{i},\succ,P_{i}^{{}^{\prime}}),(l^{**}_{-i},\succ,P_{-i}^{{}^{\prime}}))$,
which implies $g(m^{*})R_{i}g(m^{**})$, and hence we have
$f(\succ,P_{i},P_{-i}^{{}^{\prime}})R_{i}f(\succ,P_{i}^{{}^{\prime}},P_{-i}^{{}^{\prime}})$.
Since $P_{i}^{{}^{\prime}}$ and $P_{-i}^{{}^{\prime}}$ were arbitrary, this
means that $f_{\succ}$ is strategy-proof.

Let $(\succ,P)$ and $(\succ^{{}^{\prime}},P)$ be two states that share
preferences. Let $m_{i}^{*}=(l^{*}_{i},\succ,P_{i})$ be the implementing
message in state $(\succ,P)$ and $m^{**}$ in $(\succ^{{}^{\prime}},P)$. We
must have that deviating with respect to the underlying alignment leads to
some outcome in the lower contour set for each agent $i$. Then, at state
$(\succ^{{}^{\prime}},P)$ as well deviations from $m^{*}$ will lead to some
outcome in the lower contour set for each agent $i$, and hence $m^{*}$ will be
a Nash equilibrium at $(\succ^{{}^{\prime}},P)$. By Nash implementation in
public information, $f(\succ,P)=g(m^{*})=g(m^{**})=f(\succ^{{}^{\prime}},P)$.

For the other direction, let $f$ be such that $f_{\succ}$ is strategy-proof
for all $\succ$ in the support of $\mu$, $f$ is shared-monotonic, and $f$
satisfies no veto power. Consider the following mechanism:

  * •

$M_{i}=N\times X\times\mathcal{K}$ for all $i$, where $N$ is the set of
natural numbers.

  * •

if messages are of the form $m_{i}=(l_{i},x_{i},\succ,P_{i})$ for all except
at most one agent i.e. at least $n-1$ agents agree on the alignment,
$g(m)=f(\succ,P)$.

  * •

if not, select the agent with the lowest index amongst those sending the
highest natural number, say $j$. $g(m)=x_{j}$.

To verify dominant strategy implementation in private information, note that
given $\succ$, truth-telling is a dominant strategy since $f_{\succ}$ is
strategy proof. Unilateral deviations along $N\times X$ do not change the
outcome. To verify Nash implementation in public information, note first that
unilateral deviations for the alignment do not change the outcome. Second, if
all but one agent $i$ report the same alignment but $i$ reports a different
alignment, we can have a Nash equilibrium in the public information only if
the outcome chosen is the best alternative for all agents but $i$. But then,
by NVP, this outcome coincides with $f(\succ,P)$. Finally, if all agents
report a different alignment, by shared-monotonicity the outcome is the same
as $f(\succ,P)$. ∎

######  Lemma 1.

[Consistency] Suppose $\succ$ and $\succ^{{}^{\prime}}$ are such that
$\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}\neq\emptyset$. Let
$T_{\succ,\succ^{{}^{\prime}}}=\\{x\in X\ |\ x=P(1)$ for some
$P\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}\\}$. Then the
following hold

  1. 1.

$|T_{\succ,\succ^{{}^{\prime}}}|\geq 2$.

  2. 2.

Let $T_{\succ,\succ^{{}^{\prime}}}=\\{x_{1},x_{2},...,x_{|T|}\\}$. Then
$x_{1},x_{2},...,x_{|T_{\succ,\succ^{{}^{\prime}}}|}$ are adjacent in both
$\succ$ and $\succ^{{}^{\prime}}$, and they are in the same order in both
$\succ$ and $\succ^{{}^{\prime}}$ 444We reiterate that an alignment and its
exact reverse are equivalent for our purposes, so this statement and the rest
in this paper should be considered up to these equivalence classes..

###### Proof of Lemma 1.

  1. 1.

Note that $T_{\succ,\succ^{{}^{\prime}}}\neq\emptyset$. Let $x\in
T_{\succ,\succ^{{}^{\prime}}}$. Then, $\exists\
P\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$ such that
$x=P(1)$. Let $y=P(2)$. Consider a preference $P^{{}^{\prime}}$ such that
$P^{{}^{\prime}}(1)=y$ and $P^{{}^{\prime}}(2)=x$ and
$P^{{}^{\prime}}(i)=P(i)\ \forall\ i>2$. Since this change continues to make
the new ordering single-peaked with respect to whatever $P$ was single-peaked
according to, we must have
$P^{{}^{\prime}}\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$.
Since this implies $y\in T_{\succ,\succ^{{}^{\prime}}}$, we are done.

  2. 2.

Let $x,y\in T_{\succ,\succ^{{}^{\prime}}}$ such that in $\succ$, $t$ lies
between $x$ and $y$ for all $t\in T_{\succ,\succ^{{}^{\prime}}}$. Now, let
$z\in X$ be in between $x$ and $y$ in $\succ$. Let us check where $z$ will be
in $\succ^{{}^{\prime}}$. Suppose it is not in between the two. Without loss
of generality, let it be to the left of both $x$ and $y$ in
$\succ^{{}^{\prime}}$. Since $y\in T_{\succ,\succ^{{}^{\prime}}}$, $\exists\
P\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$ such that
$y=P(1)$. By single peakedness, $zPx$ in $\succ$ but $xPz$ in
$\succ^{{}^{\prime}}$, which is a contradiction. Thus, $z$ must be in between
$x$ and $y$ in $\succ^{{}^{\prime}}$ as well.
It is straightforward to show by a similar argument that if both $z_{1}$ and
$z_{2}$ are in between $x$ and $y$ in $\succ$, then the four must be in the
same order in $\succ^{{}^{\prime}}$ as well. Thus, the order between $x$ and
$y$ is preserved across $\succ$ and $\succ^{{}^{\prime}}$.
Now, let $z$ be next to $x$ in $\succ$ and between $x$ and $y$. Since $x\in
T_{\succ,\succ^{{}^{\prime}}}$, $\exists\
P^{{}^{\prime}}\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$
such that $x=P^{{}^{\prime}}(1)$. Consider a preference
$P^{{}^{\prime\prime}}$ such that $P^{{}^{\prime\prime}}(1)=z$ and
$P^{{}^{\prime\prime}}(2)=x$ and $P^{{}^{\prime\prime}}(i)=P^{{}^{\prime}}(i)\
\forall\ i>2$. We must have
$P^{{}^{\prime\prime}}\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$.
In this manner, $z\in T_{\succ,\succ^{{}^{\prime}}}$ for all $z$ in between
$x$ and $y$, which proves our hypothesis.

∎

######  Lemma 2.

[Symmetry] Suppose $\succ$ and $\succ^{{}^{\prime}}$ are such that
$\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}\neq\emptyset$. Let
$x,y\in T_{\succ,\succ^{{}^{\prime}}}$ be such that $x$ and $y$ are adjacent
to each other, with $x$ before $y$. Then, $f_{\succ}$ and
$f_{\succ^{{}^{\prime}}}$ must have the same number of phantoms with tops on
or before $x$.

###### Proof of Lemma 2.

Let $P_{x}\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$ denote
the preference with $x$ at top and
$P_{y}\in\mathcal{D}_{\succ}\cap\mathcal{D}_{\succ^{{}^{\prime}}}$ denote the
preference with $y$ at top. For any $k,l\in\\{0,1,...,n\\}$ such that $k+l=n$,
we must have that reports of $k$ number of $P_{x}$ and $l$ number of $P_{y}$
preferences must lead to the same outcome across $\succ$ and
$\succ^{{}^{\prime}}$. If the number of phantoms before $x$ were not the same
across the two alignments, this would not be possible. ∎

###### Proof of Theorem 3.

Since Lemma 2 establishes that Symmetry is necessary, we first show that
everything but the order statistic mechanisms with odd agents will violate
Symmetry and, for $|A|>3$, we show that all except the true median will
violate it. Then we show that for these surviving mechanisms, NVP is
necessary. Showing that the surviving mechanisms satisfy Symmetry and NVP
completes the proof.

Our first claim is that phantoms cannot be placed on the interior for any
alignment, where interior of an alignment is anything not at the two ends.
Suppose the median SCF chosen for some alignment, say $\succ$, contains
phantoms in the interior. Select one alternative in the interior which has a
phantom on it, and call it $y$. Let the alternative to the left of it be $x$
and the one to its right be $z$. Suppose there are $k$ phantoms on or before
$x$, and $l$ phantoms on or before $y$. By assumption, $k<l$. Consider the
alignment, say $\succ^{{}^{\prime}}$, with $z$ pulled to the left of $x$, but
everything else in the same position. Since we have full support, this
alignment is in the support of $\mu$. Clearly, $\succ$ and
$\succ^{{}^{\prime}}$ share preferences with tops at $x$ and $y$. Thus, there
must continue to be $k$ phantoms before $x$ in $\succ^{{}^{\prime}}$. Consider
the alignment, say $\succ^{{}^{\prime\prime}}$, with $y$ and $z$ interchanged
in $\succ$, with all other alternatives at the same position. $\succ$ and
$\succ^{{}^{\prime\prime}}$ share preferences with tops at $y$ and $z$, so
after $y$ in $\succ^{{}^{\prime\prime}}$, we must have $l$ phantoms. Now, note
that $\succ^{{}^{\prime}}$ and $\succ^{{}^{\prime\prime}}$ share preferences
with tops at $x$ and $z$. Before $x$ in $\succ^{{}^{\prime}}$, we have $k$
phantoms but after $x$ in $\succ^{{}^{\prime\prime}}$ we have at least $l$
(since $y$ is to the right of $x$), which is a contradiction.

Second, we claim that the number of phantoms must be the same on both ends for
all alignments when $|A|>3$. Suppose the median SCF chosen for some alignment,
say $\succ$, contains $k$ phantoms at the left end. Let $a$, $b$, $c$, $d$ be
the first four alternatives in $\succ$, in that order. Consider the alignment,
say $\succ^{{}^{\prime}}$, with $a$, $d$, $b$, $c$ as the first four
alternatives, in that order, and the rest the same as $\succ$. Clearly,
$\succ$ and $\succ^{{}^{\prime}}$ share preferences with tops at $b$ and $c$,
so $\succ^{{}^{\prime}}$ must have $k$ phantoms on $a$. Consider the
alignment, say $\succ^{{}^{\prime\prime}}$, with $c$, $b$, $a$, $d$ as the
first four alternatives, in that order, and the rest the same as $\succ$.
Clearly, $\succ^{{}^{\prime}}$ and $\succ^{{}^{\prime\prime}}$ share
preferences with tops at $a$ and $d$, so $\succ^{{}^{\prime\prime}}$ must have
$k$ phantoms on $c$. Now, note that $\succ^{{}^{\prime}}$ and
$\succ^{{}^{\prime\prime}}$ share preferences with tops at $a$ and $b$, so in
$\succ$, there must be $k$ phantoms on the right end. Thus, we have ruled out
everything but the true-median.

Now, we note that No Veto Power (NVP) is also a necessary condition for the
surviving mechanisms under full support. In the class of order statistics
mechanisms, a mechanism does not satisfy NVP if for some $\succ$, the SCF
chosen for $\succ$ has all phantoms placed on one or the other side. Suppose
such a $\succ$ exists and without loss of generality, let all phantoms be on
the left end. Let $a,b,c$ be the first three alternatives in $\succ$. Consider
a profile of preferences with $n-1$ peaks at $a$ and $b$, and $1$ peak at $c$
(call this agent $i$). Consider a $\succ^{{}^{\prime}}$ where $c,a,b$ are the
first three alternatives and everything else is the same as $\succ$. By
Symmetry, $\succ^{{}^{\prime}}$ must also have all the peaks at $c$. Then, by
misreporting to a preference $\succ^{{}^{\prime}}$ with top at $c$, agent $i$
can profitably deviate.

We close by noting that the true median and the symmetric order statistic
mechanisms satisfy both NVP and Symmetry. Consider the true median mechanism.
For any pair of alternatives, Symmetry is satisfied by definition since the
number of phantoms is the same on both ends of every alignment. For any
profile of preferences with $n-1$ them on the same alternative, this
alternative must be chosen since there will be at least one phantom on each
end. Consider the symmetric order statistic mechanism. For any pair $a,b$,
they are shared across exactly two alignments, and in the same order. Thus,
symmetry is guaranteed. NVP follows by the fact that they have at least one
phantom on either side. ∎

###### Proof of Proposition 2.

This follows directly from Lemmas 1 and 2. Note that Consistency implies that
the shared tops must be a contiguous subordering of each alignment in $S$, and
Symmetry then implies parts $1.$ and $3.$ of the proposition. $2.$ is a
consequence of NVP, as noted earlier. ∎

###### Proof of Proposition 3.

Consider the following indirect mechanism $\mathcal{M}$: each agent sends a
message $m_{i}=(\succ_{i},P_{i},f_{i},z)$ such that $\succ_{i}\in\mathcal{P}$,
$P_{i}\in\mathcal{D}_{\succ_{i}}$, $f_{i}$ is a median SCF, and $z$ is an
integer. Let $x_{i}$ be the top of $P_{i}$.

  1. 1.

If at least $N-1$ agents send $\succ_{i}=\succ^{*}$, run any median mechanism
$\mathcal{M}^{c}$ satisfying No Veto Power (NVP) using $\succ^{*}$ as the
underlying alignment and $x_{i}$ as the peaks, and

  2. 2.

otherwise, choose the agent with the lowest index agent, say $j$, amongst
those sending the largest integer in their message, and run the median
mechanism $\mathcal{M}^{j}$ dictated by $f_{j}$ and $\succ_{j}$, using $x_{i}$
as the peaks.

Suppose all agents send $\hat{\succ}$ as part of their message. Then,
$\mathcal{M}^{c}$ is run using the correct alignment and all the equilibria
are the same as a strategy-proof, unanimous, and anonymous direct mechanism.
Deviations in reporting of $\succ_{i}$ do not lead to a change in the outcome,
and hence they cannot be profitable.

Suppose all agents send $\succ^{{}^{\prime}}\neq\hat{\succ}$ as part of their
message. Since there exists an agent with preference for honesty, this agent
will deviate to sending $\hat{\succ}$ since that doesn’t change the outcome,
and hence this cannot be an equilibrium message profile.

Suppose there are two alignments $\succ^{{}^{\prime}}$ and
$\succ^{{}^{\prime\prime}}$ sent by the agents. Consider two cases:

Case 1: The true peaks of all but one agents are at the same alternative, say
$a$. If at least one of the agents with the true peak at $a$ sends an
alignment $\succ^{{}^{\prime}}$ while the others send
$\succ^{{}^{\prime\prime}}\neq\succ^{{}^{\prime}}$, then the agent with the
true peak not at $a$ can deviate to some
$\succ^{{}^{\prime\prime\prime}}\notin\\{\succ^{{}^{\prime}},\succ^{{}^{\prime\prime}}\\}$
and get his true peak selected.
Suppose instead that all the agents with the true peak at $a$ send the same
$\succ^{{}^{\prime}}$ and the remaining agent sends
$\succ^{{}^{\prime\prime}}\neq\succ^{{}^{\prime}}$. Note that for such a
message to be a Nash equilibrium, it must be that $a$ is the outcome, since if
some $b\neq a$ is chosen, then, one of the agents with peak at $a$ can deviate
to report some
$\succ^{{}^{\prime\prime\prime}}\notin\\{\succ^{{}^{\prime}},\succ^{{}^{\prime\prime}}\\}$
and get $a$ chosen, which is a profitable deviation. By NVP, the alternative
chosen in the dominant strategy equilibrium of $\mathcal{M}^{c}$ under
knowledge of $\succ$ is $a$ as well.
Case 2: If the true peaks of fewer than $N-1$ agents are the same, then there
will be at least two agents who do not get their preferred alternative. At
least one of these agents can profitably deviate by sending a larger integer
and a different alignment $\succ^{{}^{\prime\prime\prime}}$ (along with the
appropriate $f_{j}$) to get his preferred alternative given the messages of
others. ∎


# Fast Search for Dynamic Multi-Relational Graphs

Sutanay Choudhury

Lawrence Holder

George Chin

Pacific Northwest National Laboratory, USA<EMAIL_ADDRESS>Washington State University, USA<EMAIL_ADDRESS>Pacific Northwest National
Laboratory, USA<EMAIL_ADDRESS>John Feo

Pacific Northwest National Laboratory, USA<EMAIL_ADDRESS>
(2013)

###### Abstract

Acting on time-critical events by processing ever growing social media or news
streams is a major technical challenge. Many of these data sources can be
modeled as multi-relational graphs. Continuous queries or techniques to search
for rare events that typically arise in monitoring applications have been
studied extensively for relational databases. This work is dedicated to answer
the question that emerges naturally: how can we efficiently execute a
continuous query on a dynamic graph? This paper presents an exact subgraph
search algorithm that exploits the temporal characteristics of representative
queries for online news or social media monitoring. The algorithm is based on
a novel data structure called the _Subgraph Join Tree (SJ-Tree)_ that
leverages the structural and semantic characteristics of the underlying multi-
relational graph. The paper concludes with extensive experimentation on
several real-world datasets that demonstrates the validity of this approach.

###### category:

H.2.4 Systems Query processing

###### keywords:

Continuous Queries; Dynamic Graph Search; Subgraph Matching

††conference: DyNetMM’13, June 23, 2013, New York, USA.

##  1 Introduction

Social networks, social media websites and mainstream news media are driving
an exponential growth in online content. This information barrage presents
both a formidable challenge and an opportunity to applications that thrive on
situational awareness. Examples of such applications include emergency
response, cyber security, intelligence and finance where the data stream is
monitored continuously for specific events. Timeliness of the detection
carries paramount importance for such applications. The applications derive
their competitive edge from fast detection as late detection may not have much
value due to incurred damage to resources. Our work is motivated by queries
that look for rare events, have a time constraint on the time to discovery and
never need a bulk retrieval of historic data due to their monitoring nature.

Continuous queries evolved in the field of relational databases to address
applications with precisely the above characteristics. A continuous query
system is defined as one where a query logically runs continuously over time
as opposed to being executed intermittently [1, 2]. Thus, continuous query
processing is data-driven or trigger oriented. Many of the prominent news or
social media streams can be represented as multi-relational data sources.
Multi-relational graphs are often an attractive representation for data
sources with sparsity. The problem of monitoring events in such data streams
can be viewed as continuously searching the dynamic graph for patterns that
represent events of interest.

Figure 1: A graph query for monitoring emergencies in social media and news
streams.

Fig. 1 shows a graph pattern that represents such an event. An operator may
substitute the "keyword" with "fire" or "accident" and register several
queries. Articles refer to articles in news as well as social media posts.
This query will capture events that are reported from the same location.
Observe that we specify the label for only one vertex in this query, the rest
of the vertices have only type specified. Therefore, we are using the labeled
vertex to anchor into a context and report when multiple events with that
context are detected in the data stream.

Graph search involves finding exact or approximate matches for a query
subgraph in a larger graph. It has been studied extensively and is formally
defined as the problem of subgraph isomorphism: given a pattern or query graph
(henceforth described as query graph) $G_{q}$ and a larger input graph
(henceforth described as the data graph) $G_{d}$, find all isomorphisms of
$G_{q}$ in $G_{d}$. Following the definition of isomorphism, the matching
involves finding a one-to-one correspondence between the vertices of a
subgraph of $G_{d}$ and vertices of $G_{q}$ such that all vertex adjacencies
are preserved. Now consider the challenges in applying traditional graph
search techniques to this problem. Unless carefully adapted, a standard search
function will search the entire data graph repeatedly and retrieve the same
search results. Also, many of the best performing graph search algorithms rely
on indexing the graph. Even with an interval as large as 5 minutes, rebuilding
the index of a massive graph repeatedly is infeasible. This motivates
exploration of incremental algorithms for continuous queries, although the
general problem of incremental subgraph isomorphism is proven to be NP-
complete as well [3].

Queries like the one shown in Fig. 1 share a number of common attributes.
First, they all involve an implicit time window to suggest the timeliness
aspect associated with the query. Clearly, the length of the time window
varies depending on the application context. The average monitoring time
window for a high volume social media stream may be in tens of minutes whereas
the equivalent period for online news may be in hours or days. Second, all
these queries aim to discover a number of temporal events that share the same
context, such as a common set of keywords and location. Lastly, a multi-
relational graph often takes the form of k-partite graphs [4, 5] where each
partite set represents a group of entities of the same type. For queries as
ones described in Fig. 1, each event that is represented by an article or a
tweet can be viewed as a k-partitite subgraph.

We exploit these three features to implement a continuous query processing
framework for multi-relational graphs. First, by utilizing a rolling time
window we continuously prune partial search results that would otherwise need
to be tracked and would contribute to the combinatorial growth in memory
utilization. Second, the temporal property of the vertices and edges
representing events suggests that it is logical to search for distinct
subgraphs where such “temporal" vertices or edges are ordered, thus
significantly reducing the search space. Finally, we take advantage of the
multi-relational structure of the data and the characteristics of temporal
events to avoid expensive joins. Given a multi-relational query graph we
decompose it in a hierarchical fashion. We design a data structure called the
_Subgraph Join Tree_ , or henceforth referred as the _SJ-Tree_ to model the
hierarchical decomposition and store matches with various subgraphs of the
query graph as represented in the tree. This paper demonstrates the validity
of this decomposition approach towards query processing. Automated
construction of SJ-Tree from an arbitrary query graph is not discussed in this
paper. We refer to the smallest units of the decomposed query graph as “search
primitives", which almost always consists of more than one edge. As new edges
arrive over time, we continuously perform (a) “local searches" to look for
matches with the search primitives and (b) use the decomposition structure to
“join" them into progressively larger matches. This represents a middle ground
between the periodic application of a graph search algorithm on the data graph
and the approach that would have been employed by a traditional stream
database. Stream databases have no alternative but to model each edge in the
query graph as a separate join operator. Our model can express this degenerate
case where an edge is represented as a search primitive in the SJ-Tree, but
the performance is extremely poor. By grouping subgraphs into search
primitives, we can simplify the query plan, significantly improve performance
by multiple orders of magnitude, and perhaps most importantly, reason about
the trade-offs involved and explore a large space of possible optimizations.

###  1.1 Contributions

Our contributions from this research are summarized below.

1\. We introduce a data structure called SJ-Tree for query graph decomposition
(section 4) and present a novel subgraph search algorithm (5) for continuous
queries on dynamic multi-relational graphs.

2\. We compare our performance with the incremental subgraph isomorphism
algorithm developed by Fan et al. [3] and show that our approach provides
improvements by multiple orders of magnitude (section 6).

3\. We present a series of experiments on representative online news (New York
Times), co-authorship networks (DBLP) and social media data sources (Tencent
Weibo) modeled as multi-relational graphs. The scale of these datasets are
orders of magnitude larger than previously reported research [6, 3] in the
literature (section 6).

4\. We present a theoretical model for complexity analysis of the search
algorithm. We also provide an extensive experimental analysis of the
algorithm’s performance as a function of the frequency distribution of vertex
labels for verification of the theoretical model.

Figure 2: More examples of monitoring queries on multi-relational graphs. The
query at the top can be used to discover events in a certain context. Set one
of the keywords to “Oil" and run the query to discover various events that
center around oil, such as price movements, discovery, accident etc. By
setting the keyword to “buyout", the bottom query can be used to detect when
news surface about a merger between two companies.

###  1.2 Problem Statement

Every edge in a dynamic graph has a timestamp associated with it and
therefore, for any subgraph $g$ of a dynamic graph we can define a time
duration $\tau(g)$ which is equal to the duration between the earliest and
latest edge belonging to $g$. Given a dynamic multi-relational graph $G_{d}$,
a query graph $G_{q}$ and a time window $t_{W}$, we report whenever a subgraph
$g_{d}$ that is isomorphic to $G_{q}$ appears in $G_{d}$ such that
$\tau(g_{d})<t_{W}$. The isomorphic subgraphs are also referred to as matches
in the subsequent discussions. If $M(G^{k}_{d})$ is the cumulative set of all
matches discovered until time step $k$ and $E_{k+1}$ is the set of edges that
arrive at time step $k+1$, we present an algorithm to compute a function
$f\left(G_{d},G_{q},E_{k+1}\right)$ which returns the incremental set of
matches that result from updating $G_{d}$ with $E_{k+1}$ and is equal to
$M(G^{k+1}_{d})-M(G^{k}_{d})$. We assume that the graph only receives edge
inserts and no deletions.

##  2 Background

###  2.1 Multi-Relational Graphs

Single relational graphs have been widely used to model systems comprised of
homogeneous elements related by a single type of relation. A social network
where vertices represent people and edges represent connections between people
is an example of a single-relational graph. A multi-relational graph becomes a
useful construct for modeling heterogeneous relations between a possibly
heterogeneous set of entities.

Definition 2.1.1  Multi-Relational Graph A multi-relational graph denoted as
$G=(V,E)$, is a graph representation of a multi-relational database. If the
database contains $K$ entity types as $\xi_{1},...\xi_{K}$, then the vertex
set $V(G)$ is partitioned into $K$ sets $V_{1},...,V_{K}$. For any vertex
$v\in V_{k}$, the label for the vertex is represented from the domain of the
entity type $\xi_{k}$. The edges of the graph are the relations between
various entities as indicated in an entity-relation model. Thus, an edge in
the graph $e\in E(G),e=\left(v_{i},v_{j}\right)$ is an instance of a relation
$R_{ij}$ between entities $\xi_{i}$ and $\xi_{j}$.

A graph representation of such a multi-relational database takes the form of a
K-partite graph [5], if there are no relations between homogeneous entities or
equivalently, if there are no edges between vertices that belong to the same
partite set. In practice, such relationships are not rare. Examples of such
linkages are citation links between articles and social ties between two
members in a network. However, we omit unary relationships from our multi-
relational model. Our omission of unary relationships is driven by usability
and a desire for simplicity. Fig. 1 and 2 show a number of examples embodying
a range of events. Consider the example in Fig. 2 that detects a series of
articles that refer to the same set of keywords; one may wish to introduce
unary relationships in the graph to indicate citation between articles and
thus, focus only on articles with high citation counts. However, such queries
can be alternatively represented by adding a query constraint to the vertices
that require them to have a minimum degree. Or, such relations could be
represented using an intermediate vertex of a different type. Thus, for the
scope of this work we define patterns of interest as query graphs that are
subgraphs of the K-partite multi-relational graph.

###  2.2 Continuous Queries

A continuous query can be described as computing a function $f$ over a stream
$S$ continuously over time and notifying the user whenever the output of $f$
satisfies a user-defined constraint [1]. They are distinguished from ad-hoc
query processing by their high selectivity (looking for unique events) and
need to detect newer updates of interest as opposed to retrieving lots of past
information. In this paradigm the primary objective is to notify a listener as
soon as the query is matched. One may view conventional databases as passive
repositories with large collections of data that work in a request-response
model whereas continuous queries are data-driven or trigger oriented. These
features coupled with real-time demands challenge many of the fundamental
assumptions for conventional databases and establish continuous query
processing on relational data streams as a major research area. The literature
on database research from the past two decades is abundant with work on
continuous query systems [7, 8]. Babcock et al. [9] provide an excellent
overview of continuous query systems and their design challenges.

###  2.3 Graph Queries

Graph querying techniques have been studied extensively in the field of
pattern recognition over nearly four decades [10]. Our work is focused on
subgraph isomorphism which is as defined as follows.

Definition 2.2.1  Subgraph Isomorphism Given the query graph $G_{q}$ and a
matching subgraph of the data graph ($G_{d}$) denoted as
$G^{{}^{\prime}}_{d}$, a matching between $G_{q}$ and $G^{{}^{\prime}}_{d}$
involves finding a bijective function $f:V(G_{q})\rightarrow
V(G^{{}^{\prime}}_{d})$ such that for any two vertices $u_{1},u_{2}\in
V(G_{q})$, $(u_{1},u_{2})\in E(G_{q})\Rightarrow(f(u_{1}),f(u_{2}))\in
E(G^{{}^{\prime}}_{d})$.

Two popular subgraph isomorphism algorithms were developed by Ullman [11] and
Cordella et al. [12]. The VF2 algorithm [12] employs a filtering and
verification strategy and outperforms the original algorithm by Ullman. Over
the past decade, the database community has focused strongly on developing
indexing and query optimization techniques to speed up the searching process.
A common theme of such approaches is to index vertices based on k-hop
neighborhood signatures derived from labels and other properties such as
degrees, spectral properties and centrality [13, 14, 15, 16]. Other major
areas of work involve join-order optimization [17] and search techniques for
alternative representations such as similarity search in a multi-dimensional
vector space [18].

##  3 Related Work

Investigation of subgraph isomorphism for dynamic graphs did not receive much
attention until recently. It introduces new algorithmic challenges because we
can-not afford to index a dynamic graph frequently enough for applications
with real-time constraints. In fact this is a problem with searches on large
static graphs as well [19]. There are two alternatives in that direction. We
can search for a pattern repeatedly or we can adopt an incremental approach.
The work by Fan et al. [3] presents incremental algorithms for graph pattern
matching. However, their solution to subgraph isomorphism is based on the
repeated search strategy. Chen et al. [6] proposed a feature structure called
the node-neighbor tree to search multiple graph streams using a vector space
approach. They relax the exact match requirement and require significant pre-
processing on the graph stream. Our work is distinguished by its focus on
temporal queries and handling of partial matches as they are tracked over time
using a novel data structure. From a data-organization perspective, the SJ-
Tree approach has similarities with the Closure-Tree [20]. However, the
closure-tree approach assumes a database of independent graphs and the
underlying data is not dynamic. There are strong parallels between our
algorithm and the very recent work by Sun et al. [19], where they implement a
query-decomposition based algorithm for searching a large static graph in a
distributed environment. Our work is distinguished by the focus on continuous
queries that involves maintenance of partial matches as driven by the query
decomposition structure, and optimizations for real-time query processing.

##  4 Incremental Query Processing

###  4.1 Naive Approach

We begin with a simplistic solution to motivate an incremental approach for
continuous query processing. For every new edge that is added to $G_{d}$, we
detect if the edge matches any edge in the query graph. This check can be
performed minimally by examining 1) if there are edges in the query graph with
the same type as the new edge and 2) if the endpoint vertices of the new edge
match with the corresponding edges in the query graph based on their types and
attributes. Once an edge is considered as a matching candidate, the next step
is to consider different combinations of matches it can participate in.

Figure 3: Illustration of a naive incremental algorithm. Assme AB matches with
PQ, and AC matches with both QR and QS.

A simple illustration of this matching process is shown in Fig. 3. While
intuitively simple, this approach falls prey to combinatorial explosion very
quickly. It finds the match with the query graph at the cost of creating many
partial matches. Assume that the $G_{d}$ receives a large number of edges that
match with the query graph edge between A and B (Fig. 3a). Let’s denote this
edge as $e_{AB}$. Therefore, a large number of partial matches will be created
with mapping information for $e_{AB}$. Subsequently, every future edge that
matches with $e_{AC}$ will need to be matched or checked against all the
existing partial matches for augmenting into a larger match. While the
subgraph matching problem has an inherent exponential nature associated with
it, a better algorithm will restrict the growth of the number of partial
matches to track and still produce the correct result.

###  4.2 Our Approach

Our objective is to introduce an approach that guides the search process to
look for specific subgraphs of the query graph and follow specific transitions
from small to larger matches. Following are the main intuitions that drive
this approach,

  1. 1.

Instead of looking for a match with the entire graph or just any edge of the
query graph, partition the query graph into smaller subgraphs and search for
them.

  2. 2.

Track the matches with individual subgraphs and combine them to produce
progressively larger matches.

  3. 3.

Define a join order in which the individual matching subgraphs will be
combined. Do not look for every possible way to combine the matching
subgraphs.

Although the current work is completely focused on temporal queries, the graph
decomposition approach is suited for a broader class of applications and
queries. The key aspect here is to search for substructures without incurring
too much cost. Even if some subgraphs of the query graph are matched in the
data, we will not attempt to assemble the matches together without following
the join order. Thus, if there are substructures that are too frequent,
joining them and producing larger partial matches will be too expensive
without a stronger guarantee of finding a complete match. On the other hand,
if there is a substructure in the query that is rare or indicates high
selectivity, we should start assembling the partial matches together only
after that substructure is matched.

Figure 4: Illustration of query decomposition in SJ-Tree.

###  4.3 Subgraph Join Tree (SJ-Tree)

We introduce a tree structure called _Subgraph Join Tree (SJ-Tree)_ that
supports the above intuitions for implementing a join order based on
selectivity of substructures of the query graph.

Definition 4.1.1  A SJ-Tree $T$ is defined as a binary tree comprised of the
node set $N_{T}$. Each $n\in N_{T}$ corresponds to a subgraph of the query
graph $G_{q}$. Let’s assume $V_{SG}$ is the set of corresponding subgraphs and
$|V_{SG}|=|N_{T}|$. Additional properties of the SJ-Tree are defined below.

Property 1. The subgraph corresponding to the root of the SJ-Tree is
isomorphic to the query graph. Thus, for $n_{r}=root\\{T\\}$,
$V_{SG}\\{n_{r}\\}\equiv G_{q}$.

Property 2. The subgraph corresponding to any internal node of $T$ is
isomorphic to the output of the join operation between the subgraphs
corresponding to its children. If $n_{l}$ and $n_{r}$ are the left and right
child of $n$, then $V_{SG}\\{n\\}=V_{SG}\\{n_{l}\\}\Join V_{SG}\\{n_{r}\\}$.
Given two graphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, the join
operation is defined as $G_{3}=G_{1}\Join G_{2}$, such that
$G_{3}=(V_{3},E_{3})$ where $V_{3}=V_{1}\cup V_{2}$ and $E_{3}=E_{1}\cup
E_{2}$.

Property 3. Each node in the SJ-Tree maintains a set of matching subgraphs. We
define a function $matches(n)$ that for any node $n\in N_{T}$, returns a set
of subgraphs of the data graph. If $M=matches(n)$, then $\forall G_{m}\in M$,
$G_{m}\equiv V_{SG}\\{n\\}$.

Property 4. Each internal node $n$ in the SJ-Tree maintains a subgraph, CUT-
SUBGRAPH($n$) that equals the intersection of the query subgraphs of its child
nodes.

For any internal node $n\in N_{T}$ such that CUT-SUBGRAPH$(n)\neq\emptyset$,
we also define a projection operator $\Pi$. Assume that $G_{1}$ and $G_{2}$
are isomorphic, $G_{1}\equiv G_{2}$. Also define $\Phi_{V}$ and $\Phi_{E}$ as
functions that define the bijective mapping between the vertices and edges of
$G_{1}$ and $G_{2}$. Consider $g_{1}$, a subgraph of $G_{1}$: $g_{1}\subseteq
G_{1}$. Then $g_{2}=\Pi(G_{2},g_{1})$ is a subgraph of $G_{2}$ such that
$V(g_{2})=\Phi_{V}(V\left(g_{1}\right))$ and
$E(g_{2})=\Phi_{E}(E\left(g_{1}\right))$.

Conceptually, the SJ-Tree is an index structure where keys track the
occurrence of matching subgraphs in the data graph. Our decision to use a
binary tree as opposed to an n-ary tree is influenced by the simplicity and
lowering the combinatorial cost of joining matches from multiple children.
Analyzing the trade-offs between different tree models (e.g. left-deep vs
bushy) is part of future work.

##  5 Continuous Query Algorithm

Figure 5: a) Example query b) Occurrence of a match in the search graph c)
Combining two partial matches to form the complete match

We present a subgraph search algorithm (Algo. 1 and 2) that utilizes the SJ-
Tree structure (referred to as $T$). The search process is illustrated in Fig.
5. The input to PROCESS-CONT-QUERY is the dynamic graph $G_{d}$, the SJ-Tree
($T$) corresponding to the query graph and the set of incoming edges. Each
leaf of the SJ-Tree represents an unique subgraph of the query graph. Lines
4-6 in Algo. 1 describe the search for each of these unique subgraphs around
every incoming edge. Any discovered match is added to the SJ-Tree (line 9).

Algorithm 1 PROCESS-CONT-QUERY($G_{d}$, T, edges)

1:$leaf$-$nodes=$GET-LEAF-NODES$(T)$

2:for all $e_{s}\in edges$ do

3: UPDATE-GRAPH($G_{d},e_{s}$)

4: for all $n\in leaf$-$nodes$ do

5: $g^{q}_{sub}=$GET-QUERY-SUBGRAPH$(T,n)$

6: $matches=$LOCAL-SEARCH($G_{d},g^{q}_{sub},e$)

7: if $matches\neq\emptyset$ then

8: for all $m\in matches$ do

9: T.UPDATE-SJ-TREE$(n,m)$

###  5.1 Local Search

The LOCAL-SEARCH function performs a subgraph isomorphism check around the
neighborhood of every incoming edge $e$. The query decomposition often reduces
the local search to performing star queries where the center of the query is
the vertex representing a temporal event. The peripheral vertices of the star
query are the other entities that represent various attributes of the event.
Further, in the context of real-time search, if the current time is $t$ and
the query specifies a time window of length $t_{W}$ then all edges that have a
timestamp older than $(t-t_{W})$ are ignored from the search. In addition to
filtering search candidates, we also periodically prune the SJ-Tree to remove
partial matches that are older than $t_{W}$ from the current time.

Algorithm 2 UPDATE-SJ-TREE($node,m)$

1:$sibling=sibling[node]$

2:$parent=parent[node]$

3:$k=$GET-JOIN-KEY(CUT-SUBGRAPH[$parent$], $m$)

4:$H_{s}$ = match-tables[$sibling$]

5:$M^{k}_{s}$ = GET($H_{s},k$)

6:for all $m_{s}\in M^{k}_{s}$ do

7: $m_{sup}$ = JOIN($m_{s}m$)

8: if parent = root then

9: PRINT(’MATCH FOUND : ’, $m_{sup}$)

10: else

11: UPDATE-SJ-TREE($parent,m_{sup}$)

12:ADD($matches[node],m$)

13:ADD($match-tables[node],k,m$)

###  5.2 Partial Match Join and Aggregation

This subsection describes the process outlined in UPDATE-SJ-TREE. The SJ-Tree
data structure maintains the sibling and parent information for every node as
distinct arrays (Algo. 2, line 1-2). Each node in the SJ-Tree maintains a hash
table that supports storing multiple objects with the same key. This
collection of tables are denoted by the match-tables property of the SJ-Tree
(Algo 2., line 4). GET() and ADD() provides lookup and update operations on
the hash tables. Whenever a new matching subgraph $g$ (available as a property
of the partial match $m$) is added to a node in the SJ-Tree, we compute a key
using its projection $(\Pi(g))$ and insert the key and the matching subgraph
into the hash table. The projection is obtained by hashing a string
representation of the subgraph.

When a new match is inserted into a leaf node we check to see if it can be
combined (referred as JOIN()) with any matches that are contained in the
collection maintained at its sibling node. A successful combination of
matching subgraphs between the leaf and its sibling node leads to the
insertion of a larger match at the parent node. This process is repeated as
long as larger matching subgraphs can be produced by moving up in the SJ-Tree.
A complete match is found when two matches belonging to the children of the
root node are combined successfully.

The JOIN operation between partial matches is critical to the overall query
processing performance. Suppose we have a query that finds a sequence of two
events with a common set of attributes. Assume that two matching events
${event}_{1}$ and ${event}_{2}$ are found with timestamps $\tau_{1}$ and
$\tau_{2}$ respectively, with $\tau_{1}<\tau_{2}$. For all practical purposes
we can report the sequence $\\{{event}_{1},{event}_{2}\\}$ and ignore the out
of order combination. Therefore, given two partial matches $M_{1}$ and $M_{2}$
with edge sets $\\{E_{i},E_{j}\\}$ and $\\{E_{m},E_{n}\\}$ respectively, the
join algorithm rejects all combinations of these two sets that do not
represent a monotonic order based on timestamps. This is accomplished by
computing a range of timestamps for each partial match. If $t_{low}[M_{i}]$
and $t_{high}[M_{i}]$ are the lowest and highest timestamp for match $M_{i}$,
then we require that $t_{high}[M_{1}]<t_{low}[M_{2}]$ for joining $M_{1}$ and
$M_{2}$.

###  5.3 Complexity Analysis

There are two primary tasks in processing every edge in the continuous query
algorithm, (1) performing a local search for a small subgraph of the query
graph and in case of a successful search, (2) updating the SJ-Tree with the
partial match. For the multi-relational queries described in this paper, the
local search reduces to performing a star query. Assuming the LOCAL-SEARCH is
cheap for star queries, we can approximate the cost of the continuous query
processing for every edge to a small constant in case of a failed local search
and to that of the UPDATE-SJ-TREE() for a successful search. If $C_{k}$ is the
expected value for the cost of insert and joins at node $k$ in the SJ-Tree,
then the complexity of updating the tree is $O((\bar{C_{k}})^{h})$, where
$\bar{C_{k}}$ denotes the expected value of $C_{k}$ over all nodes. This is
not a tight bound, and a more accurate bound can be obtained estimating
$C_{k}$ based on the frequency of the subgraphs satisfying the label
constraints in the query graph. Accurate estimation of the frequency of an
arbitrary subgraph is hard. Therefore, we resort to obtaining a loose bound in
terms of the label constraints. Assume that $v_{q}$ has the lowest degree
among all labeled vertices in the query graph and $v_{s}$ is the corresponding
vertex in the data graph. Then $n_{k}$ is bounded by ${d_{s}}\choose{d_{q}}$,
where $d_{s}$ and $d_{q}$ are the degrees of $v_{s}$ and $v_{q}$. The storage
complexity for SJ-Tree is $O(h\bar{C_{k}}|E(G_{q})|)$.

##  6 Experimental Results

This section is dedicated to answering two questions: 1) How does our
continuous graph query algorithm compare with the state of the art? To answer
this, we compare our algorithm’s performance with the IncIsoMatch algorithm
presented in [3]. 2) How does our query algorithm perform on real-world
datasets? We provide the answers from exhaustive experimentation on three
real-world datasets through systematic query selection.

Graph dataset | vertices | edges | vertex types | edge types
---|---|---|---|---
New York Times | 39,523 | 68,682 | 4 | 4
DBLP | 3.158M | 3.26M | 2 | 1
Tencent Weibo | 2.5M | 89.6M | 4 | 5

Our metric is the time to process increments of a fixed number of edges (1k or
100k) whichever is closer to 1% of the test dataset size. The times reported
only include the time spent in the query processing section. We use the query
template as shown in Fig. 6. To develop a performance model in terms of the
label distribution, we sample the degree distribution of every vertex type and
divide the range of the degree distributions into ten intervals. For each
interval, five closest candidate vertices are selected for testing purposes.
Selection of multiple vertices around each bin allows us to systematically
observe the impact of increasing the degree of the labeled vertex in the query
graph.

###  6.1 Experimental Setup

The results were obtained by using a single core on a 48-core shared memory
system comprising 2.3 GHz Opteron 6176 SE processors and 256 GB RAM. The
processor cache size is 512KB and each system node has 32 GB RAM. The code was
compiled with g++ 4.1.2-52 with -O3 optimization flag on Linux 2.6.18.

###  6.2 New York Times

Figure 6: The query template used to find temporal events. Experiments are
performed using queries with 4 event vertices and 2 feature vertices. One
feature vertex is labeled and all other vertices specify only types. Figure 7:
Results from queries finding four articles with a common keyword and location.
Legends indicate degree of query label. Figure 8: Comparison with IncIsoMatch.
MQD refers to the Multi-Relational Query Decomposition algorithm from this
paper.

We use a news dataset from New York Times collected over Aug-Oct 2011
111http://data.nytimes.com. Each article in the dataset contains a number of
facets that belong to four type of entities. Each of the articles and facets
are represented as vertices in the graph. Each edge that connects an article
with a facet carries a timestamp that is the publication time of the article.
Following the template shown in Fig. 6, we run a query that finds four
articles where all the articles have a common keyword and location. For the
location vertex we specify the labels shown in the top diagram in Fig. 7 and
observe the performance. As the figures indicate, selecting labels that
correspond to vertices with increasing degrees increases the running time of
the query.

Next, we compare our approach with the IncIsoMatch algorithm described by Fan
et al. [3]. The VF2 algorithm [12] is adapted to implement the graph search
functionality as outlined in IncIsoMatch. We specify a label on the feature
marked with $\dagger$ and select a label with one of the highest degrees for
that vertex type. The queries are as follows: 1) Find four articles with a
common keyword and a common organization$\dagger$, 2) Find four articles with
a common entity and a common keyword $\dagger$ and 3) Find four articles with
a common entity and a common location $\dagger$. Fig. 8 shows a performance
improvement from our algorithm by several orders of magnitude. The multiple
orders of improvement in performance is attributed to the strictly ordered
aggregation of partial matches in the SJ-Tree and the temporal property based
optimizations. The performance gap between the processing time of the two
algorithms increases as the graph grows larger. We attribute this to the
nature of the IncIsoMatch where it performs a search around every new edge in
the graph. The search spans all vertices around the endpoints of the new edge
as long as they are within $k$-hops, where $k$ is the diameter of the query
graph. As the data graph grows denser, even for a query graph with small or
modest size, the $k$-hop subgraph accumulates a large number of edges and the
search becomes increasingly expensive.

###  6.3 DBLP Co-Authorship Network

Figure 9: Performance results for queries on the DBLP dataset. The spikes in
the plot can be attributed to the bursty nature of scientific publishing where
authors target the same group of conferences and journals every year.

We build a multi-relational graph representation of the DBLP citation network
111dblp.uni-trier.de/xml with two types of entities: authors and articles. The
author name and the title of the article are stored as labels of respective
vertices. We run a query to find an author (author 1) who has co-authored four
papers with a specified author (author 2). Following the previously shown
query template, our query graph has four article vertices and two author
vertices. Only one author vertex is labeled. We observe the degree
distribution of the “author" vertices and select names with progressively
increasing degrees. The results are shown in Fig. 9. It can be seen that the
performance of the algorithm is quite stable for a modestly large network with
nearly 3M+ edges. Additionally, the results show that even though vertex
degree is a good indicator of the query performance, there are other factors
at play. The graph describes author-article relationship; therefore, the
degree of an author vertex provides the number of authored articles. It does
not provide the information about the number of co-authors of a person.
Searching for a person who publishes a given number of articles with fewer co-
authors will lead to more partial matches and increase per-edge query
processing time. The consistent high processing times for the query containing
"Hsinchun-Chen" despite smaller degree in the graph is a result of this
aspect.

Figure 10: Query processing time for the Tencent Weibo dataset for queries
with varying selectivity.

###  6.4 Social Media

Finally, we present our results on a data set collected from Tencent Weibo, a
Chinese microblogging social network222www.kddcup2012.org/c/kddcup2012-track1.
The data set provides a temporal history of item recommendations to registered
users of the social network. We build a graph with 4 vertex types (users,
items, keywords and categories) and 5 edge types (item-in-category, item-has-
keyword, item-reco-accept, item-reco-reject and user-profile-has-keyword).

Our test query is to detect a series of item acceptances by a group of users
described by a common keyword. Following the previously shown query template,
our query graph has four user vertices and one item and keyword vertex. We
specify a label on the item and seek to discover the keyword that characterize
the users accepting or rejecting that item. The results are shown in Fig. 10.
The figure suggests a clear trend. It shows that as the graph grows large the
query processing time eventually rises sharply. It also shows that the rise
happens earlier for low-selectivity queries where the specified label has
higher degree in the graph. This is because the number of partial matches
grows rapidly in the event of a successful search around a high degree vertex.
Every partial match from the past can potentially be merged with the latest
partial match, and the partial match collection grows combinatorially over
time.

This brings us to implementing the temporal window based pruning. We select
the query with the highest degree label (degree(item) = 299199, Fig. 10) for
which the rise in the processing time was sharpest. We set the time window
$t_{W}$ to 1 day and prune the SJ-Tree after processing every 5 million edges.
The results from the windowing enabled search is shown in Fig. 11. Observe
that the peaks in the processing time are smaller than ones observed in Fig.
10 by an order of magnitude.

Figure 11: Query processing time for the Tencent Weibo dataset with temporal
match pruning applied on every 5 million edges.

This is an extremely promising result for practical applications. Figure 11
suggests that it would take 10 seconds on average to process 100k edges for a
query with very low selectivity. This translates into a throughput of 0.01
million edges/second or 864 million edges per day. At the time of this
writing, high volume data streams such as Twitter receive nearly 300-400
million posts every day. Considering that every user action translates into
multiple edges in a graph, one may expect around billions of edges everyday.
The throughput can be expected to be much higher for a query with moderate
selectivity. Thus, we believe this level of throughput on a very low-
selectivity query gets us close to executing real-time graph queries on such
high volume data streams.

##  7 Conclusion and Future Work

We present a novel graph decomposition based approach for continuous queries
on multi-relational graphs. We introduce the SJ-Tree structure, whose nodes
represent the hierarchical decomposition of the query graph. The SJ-Tree
systematically tracks the evolving matches in the data graph as they
transition from smaller to larger matches based on the query graph
decomposition. We present experimental analysis on several real-world datasets
such as New York Times, DBLP and Tencent Weibo and show that our SJ-Tree based
algorithm coupled with temporal optimizations clearly outperforms the state of
the art [3] by multiple orders of magnitude. Our experiments demonstrate that
it is possible to execute complex multi-relational graph queries in a real-
time setting. To our knowledge, the results presented in this paper are the
best reported performance for such queries. These initial results are highly
promising in that they suggest possible ways of auto-selecting optimal values
for query processing parameters based on the data distribution. Our main
theoretical contribution is to demonstrate that for a prominent class of
multi-relational queries where the local search is cheap, we can execute graph
queries in time that is exponential to the height of the SJ-Tree.

Development of query planning algorithms to generate a SJ-Tree for any query
graph by exploiting its structural and semantic characteristics is the next
logical step. Query planning for 1) complex graph queries where a complete
temporal ordering may not be possible, 2) trade-offs between different query
decomposition strategies and 3) exploring different query classes and
determining the optimal trade-off between local search and joins in the SJ-
Tree represent areas of future work.

## Acknowledgment

The authors are grateful to Dr. Bill Howe at the University of Washington for
his suggestions that have improved this paper. Presented research is based on
work funded under the Center for Adaptive Supercomputing Software -
Multithreaded Architecture (CASS-MT) at the US Department of Energy’s Pacific
Northwest National Laboratory, which is operated by Battelle Memorial
Institute.

## References

  * [1] Y.-N. Law, H. Wang, and C. Zaniolo, “Relational languages and data models for continuous queries on sequences and data streams,” _ACM Trans. Database Syst._ , June 2011.
  * [2] D. Terry, D. Goldberg, D. Nichols, and B. Oki, “Continuous queries over append-only databases,” _SIGMOD Rec._ , 1992.
  * [3] W. Fan, J. Li, J. Luo, Z. Tan, X. Wang, and Y. Wu, “Incremental graph pattern matching,” ser. SIGMOD ’11, 2011.
  * [4] P. Zhao, X. Li, D. Xin, and J. Han, “Graph cube: on warehousing and olap multidimensional networks,” in _SIGMOD ’11_.
  * [5] E. Spyropoulou and T. D. Bie, “Interesting multi-relational patterns,” in _ICDM_ , 2011, pp. 675–684.
  * [6] L. Chen and C. Wang, “Continuous subgraph pattern search over certain and uncertain graph streams,” _IEEE Trans. on Knowl. and Data Eng._ , vol. 22, no. 8, pp. 1093–1109, Aug. 2010.
  * [7] S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. R. Madden, F. Reiss, and M. A. Shah, “Telegraphcq: continuous dataflow processing,” ser. SIGMOD ’03.
  * [8] A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, and J. Widom, “Stream: The stanford stream data manager,” in _SIGMOD ’03_.
  * [9] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, “Models and issues in data stream systems,” ser. PODS ’02.
  * [10] D. Conte, P. Foggia, C. Sansone, and M. Vento, “Thirty years of graph matching in pattern recognition,” _Intl. Journal of Pattern Recognition and Artificial Intelligence_ , 2004.
  * [11] J. R. Ullmann, “An algorithm for subgraph isomorphism,” _J. ACM_ , vol. 23, pp. 31–42, January 1976.
  * [12] L. Cordella, P. Foggia, C. Sansone, and M. Vento, “A (sub) graph isomorphism algorithm for matching large graphs,” _IEEE Trans. on Pattern Analysis and Machine Intelli._ , 2004.
  * [13] Y. Tian and J. Patel, “Tale: A tool for approximate large graph matching,” in _ICDE ’08_.
  * [14] H. Tong, C. Faloutsos, B. Gallagher, and T. Eliassi-Rad, “Fast best-effort pattern matching in large attributed graphs,” ser. KDD ’07.
  * [15] P. Zhao and J. Han, “On graph query optimization in large networks,” _PVLDB._ , vol. 3, pp. 340–351, September 2010.
  * [16] Y. Zhu, L. Qin, J. X. Yu, Y. Ke, and X. Lin, “High efficiency and quality: large graphs matching,” in _Proceedings of the 20th ACM international conference on Information and knowledge management_ , ser. CIKM ’11.
  * [17] L. Zou, L. Chen, and M. T. Özsu, “Distance-join: pattern match query in a large graph database,” _PVLDB_ , vol. 2, no. 1, Aug. 2009.
  * [18] A. Khan, N. Li, X. Yan, Z. Guan, S. Chakraborty, and S. Tao, “Neighborhood based fast graph search in large networks,” ser. SIGMOD ’11.
  * [19] Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li, “Efficient subgraph matching on billion node graphs,” _PVLDB_ , vol. 5, no. 9, 2012.
  * [20] H. He and A. K. Singh, “Closure-tree: An index structure for graph queries,” ser. ICDE ’06.