# Revealed Preferences of One-Sided Matching

Andrew Tai I am grateful to David Ahn, Haluk Ergin, and Chris Shannon for
their guidance. I also thank Federico Echenique, Yuichiro Kamada, and Shachar
Kariv for helpful comments. All mistakes are my own.

(September 2022)

###### Abstract

Consider the object allocation (one-sided matching) model of Shapley and Scarf
(1974). When final allocations are observed but agents’ preferences are
unknown, can the allocation be in the core? This is a one-sided analogue of
Echenique, Lee, Shum, and Yenmez (2013). I build a model in which the strict
core is testable (“rationalizability”) based on types of agents who share
preferences. I find if and only if conditions for an allocation to be
rationalizable. The main theorem also partially identifies the set of
preferences which rationalize an allocation when possible.

##  1 Introduction

Matching literature is typically concerned with the construction of optimal or
stable matchings. Exemplified by the canonical work of Gale and Shapley (1962)
and Shapley and Scarf (1974), the agents’ preferences are given, and the
objective is to find stable matchings. In real world economic settings
however, market outcomes are typically observed and agents’ preferences are
not. Samuelson (1938) lays out a theory of revealed preferences for consumer
theory. He takes utility to be imagined (or at least unobservable) and choices
to be fundamental. Given the choices, when is a utility maximizing agent
falsified? The Weak Axiom of Revealed Preference gives an answer.

Work by Echenique, Lee, Shum, and Yenmez (2013) deals with the revealed
preferences of two-sided matching. The matching (the market outcome) is
observed, and the agents’ preferences are not – can the matching be stable? My
paper builds on such work and deals with the revealed preferences of one-sided
matching. Similarly in my setup, the final allocation111To distinguish from
two-sided matchings, I will refer to the matchings as “allocations.” is
observed, but not the agents’ preferences. My objective is to develop a model
of house allocation where stability is testable.

The outline of my model is as follows: consider the indivisible object
assignment problem with endowments (as in Shapley and Scarf). Suppose the
observer sees the allocation, but not the agents’ preferences. Under what
conditions can the allocation be _rationalized_ as in the core? That is – is
there a preference profile that makes the allocation in the core? Analogously
to Echenique et al., I consider an aggregate matchings model, with _types_ of
agents and types of houses. There is some number of each type of agent, and
agents of the same type have common preferences. Each agent is endowed with a
house. In this paper, I derive necessary and sufficient conditions for an
allocation to be possibly in the strong core. It is restrictive to impose
types, but it is necessary to give the problem testable content.

While this is of course highly abstract, it provides a framework for a theory
of object allocation as a market in the spirit of revealed preferences. In a
typical observable economic market, only the set of agents and the outcome is
observed, while the preferences and the market “mechanism” are unobserved. We
would nevertheless like to infer stability properties of the market and
perhaps back out the preferences.

This paper seeks to build on recent work in the revealed preferences of
matching theory. As mentioned above, Echenique et al. find conditions on
stable aggregate matchings when preferences are not observed in both
transferable and non-transferable utility settings. Earlier work by Echenique
(2008) finds conditions for stability when multiple matchings are observed for
the same set of agents.

As will be apparent once the model is formally introduced, this paper is tied
to the the object allocation problem with indifferences. Quint and Wako (2004)
find the strict core of the Shapley-Scarf economy with indifferences. Alcalde-
Unzu and Molis (2011) find Pareto efficient weak core allocations when the
strict core is empty.

There are two other ways to interpret this paper. Analysts may deal with
settings where the mechanism is unknown and therefore cannot be directly
evaluated. In practice, many mechanisms are hidden, or no particular
centralized mechanism is used at all. But we nevertheless want to determine
whether these unknown or decentralized mechanisms might be stable. For
example, Roth and Xing (1997) study decentralized matching for clinical
psychologists. This paper offers a way to evaluate mechanisms when essentially
nothing is known about the matching process, but the analyst still wants to
determine whether the allocation is stable.

Viewed another way, this paper provides a partial identification result for a
one-sided matching model. Given an allocation presumed to be stable, I find a
partial set of possible preference profiles. In a model with transferable
utility, Choo and Siow (2006) studied aggregate matchings empirically in the
marriage market. In the non-transferable utility case, analysts can use
intermediate matching data to recover the agents’ preferences; Hitsch,
Hortaçsu, and Ariely (2010) use rejections in online dating. Recent work by
Galichon, Kominers, and Weber (2019) develops an intermediate case, where
utility is imperfectly transferable. See Chiappori and Salanié (2016) for a
survey of the econometrics of matching.

##  2 Model

The model is a object allocation analogue to Echenique et al. and Choo and
Siow. The general setup is that of the Shapley-Scarf model, where agents are
grouped into types. There are types of agents, and all agents within a type
share the same preferences. Let the set of agent types be
$A=\\{1,2,...,\alpha\\}$. Denote the number of each type
$\mathbf{K}=\left(K_{i}\right)_{i\in\\{1,...,\alpha\\}}$ and the set of
individual agents
$\mathcal{A}=\\{1_{1},...,1_{K_{1}};...;\alpha_{1},...,\alpha_{K_{\alpha}}\\}$;
I refer to these as “agents” or “individuals”. I refer to a generic agent type
as $i$ and a generic agent as $i_{k}$. In examples and proofs when I refer to
specific agents, I will denote them as $1a,1b,...,2a,2b,...$ and so on. That
is, $1a$ and $1b$ are two individuals of the same type.

Analogously to the agents, let $H=\\{h_{1},...,h_{\eta}\\}$ be the set of
house types. Denote the number of each house type as
$\mathbf{L}=\left(L_{\ell}\right)_{\ell\in\\{1,...,\eta\\}}$. I refer to a
generic house type as $h_{\ell}$. I will not refer to individual houses –
i.e., there is no house analogue of $\mathcal{A}$.

Each agent type $i$ has a strict preference $\succsim_{i}$ over $H$; all
agents of this type have the same preference. I will illustrate in the next
section that this is the key restriction that makes the strict core testable.
Let $\succsim$ be the preference profile; with minimal consequence of
confusion, this can be the profile of types or all individuals.

Each agent is endowed with a house, given by the endowment function
$\mu^{E}:\mathcal{A}\rightarrow H$ such that
$\left|\left(\mu^{E}\right)^{-1}(h_{\ell})\right|=L_{\ell}$ for all $\ell$.
That is, the number of individuals endowed with house type $h_{\ell}$ equals
the total supply of it. Similarly, an allocation is
$\mu:\mathcal{A}\rightarrow H$ such that
$\left|\mu^{-1}(h_{\ell})\right|=L_{\ell}$ for all $\ell$. Individuals of the
same type may have different endowments and allocations.

###  2.1 Core and rationalizability

######  Definition 1.

An allocation $\mu$ is in the (strong) core for a preference profile
$\succsim$, denoted $\mu\in\text{core$\left(\succsim\right)$}$, if there is no
blocking coalition $A^{\prime}\subseteq\mathcal{A}$ and sub-allocation
$\mu^{\prime}$ such that:

  1. 1.

$\mu^{\prime}(A^{\prime})=\mu^{E}(A^{{}^{\prime}})$

  2. 2.

$\mu^{\prime}(i_{k})\succsim_{i}\mu(i_{k})$ for all $i_{k}\in A^{\prime}$, and
$\mu^{\prime}(i_{k})\succ_{i}\mu(i_{k})$ for at least one $i_{k}\in
A^{\prime}$

By convention, when a blocking coalition $A^{\prime}$ is one individual, I say
$\mu$ is not individually rational.

######  Definition 2.

Suppose we observe allocation $\mu$, but not the agents’ preferences. A tuple
$\left(A,\mathcal{A},H,\mathbf{L},\mu^{E},\mu\right)$ is a problem. Given a
problem, the allocation $\mu$ is rationalizable if there exists a preference
profile $\succsim$ such that $\mu\in\text{core$\left(\succsim\right)$}$.

This paper derives necessary and sufficient conditions for an allocation to be
rationalizable. This setting can be interpreted as the “reverse direction” of
the classic house allocation problem with universally shared indifferences.
That is, if we re-interpret this model in the typical positive direction, we
have a market of house exchange where any indifferences are shared by all
agents, and we would be looking for a TTC-like mechanism to find stable
allocations. A number of papers deal with this; Quint and Wako (2004) is
particularly important for this paper’s main result.

I have made an important modeling decision in restricting to common
preferences within agent type. As noted above, this is necessary to give the
problem testable content; with fully general preferences, any allocation is
rationalizable.222There are alternatives, such as repeated re-matchings as in
Echenique (2008). Suppose all agents are allowed to have unique preferences.
Given an allocation $\mu$, a preference profile such that each $i_{k}$’s
favorite is $\mu(i_{k})$ rationalizes $\mu$. Alternatively, suppose we allow
for $\succsim_{i}$ to have indifferences over $H$. Then making all agents
indifferent over all houses rationalizes $\mu$.

The reader might ask whether rationalizability is too weak a concept. The
following simple example shows that this model indeed has testable content –
there exist allocations that are not rationalizable.

######  Example 1.

Let there be two agents of the same type endowed with different houses who
trade. This is represented by the table below.

$\begin{array}[]{ccc}\mathcal{A}&\mu(\mathcal{A})&\mu^{E}(\mathcal{A})\\\
1a&h_{1}&h_{2}\\\ 1b&h_{2}&h_{1}\end{array}$

This cannot be rationalized. Since $\mu(1a)=h_{2}$, we need
$h_{2}\succ_{1}h_{1}$ for individual rationality. But then $\mu$ is not
individually rational for $1b$.

Of course, a rationalizable allocation is not guaranteed to be in the core –
it only _can_ be. Should we check if allocations can be in the core under
_all_ preference profiles? The following proposition shows that this is too
strict of a solution concept. For non-trivial problems, there always exists a
preference profile $\succsim$ such that $\mu\not\in\text{core}(\succsim)$

######  Proposition 1.

Fix a problem $\left(A,\mathcal{A},H,\mathbf{L},\mu^{E},\mu\right)$ and let
$|A|,\left|H\right|\geq 2$. For any allocation $\mu$, there exists a
preference profile $\succsim$ such that $\mu\not\in\text{core}(\succsim)$.

###### Proof.

Suppose there is an agent $1a$ who is not assigned to his own endowment. Let
type $1$’s favorite be $\mu^{E}(1a)$. Then this allocation is not individually
rational. Instead suppose all agents are assigned to their own endowments.
Without loss of generality let $\mu^{E}(1a)=h_{1}\not=h_{2}=\mu^{E}(2a)$. Let
$1$’s favorite be $h_{1}$, and $2$’s favorite be $h_{2}$. Then this allocation
will not be in the core, as $1a$ and $2a$ form a blocking coalition. ∎

##  3 Graphs

I first introduce some standard definitions for directed graphs that will be
useful.

######  Definition 3.

A directed graph (digraph) is $D=(V,E)$, where $V$ is the set of vertices, and
$E$ is the set of arcs. An arc is an sequence of two vertices $(v_{i},v_{j})$;
here I allow for arcs of the form $(v_{i},v_{i})$, called a self-loop.333This
is more formally called a directed pseudograph. A $(v_{1},v_{k})$-path is
sequence of vertices $(v_{1},v_{2},...,v_{k})$ where each $v_{i}$ is distinct,
and $(v_{i-1},v_{i})\in E$ for each $i\in\\{2,...,k\\}$. A cycle is a path
where $v_{k}=v_{1}$ is the only repeated vertex. Equivalently, a path is a
sequence of arcs $\left((v_{1},v_{2}),...,(v_{k-1},v_{k})\right)$, and a cycle
is where a path (in arcs) where $v_{1}=v_{k}$. The indegree of a vertex
$d^{+1}(v_{i})=\left|(v_{j},v_{i})\in E\right|$ is the number of arcs pointing
at $v_{i}$. Likewise, the outdegree of a vertex
$d^{-1}(v_{i})=\left|(v_{i},v_{j})\in E\right|$ is the number of arcs pointing
from $v_{i}$.

The next definition is used in the main result and its discussion.

######  Definition 4.

A strongly connected component (SCC) of a digraph $D=(V,E)$ is a maximal set
of vertices $S\subseteq V$ such that for all distinct vertices $v_{i},v_{j}\in
S$, there is a $(v_{i},v_{j})$-path and a $(v_{j},v_{i})$-path. By convention,
there is always a path from $v_{i}$ to itself, even if $(v_{i},v_{i})\not\in
E$; an isolated vertex is an SCC.

Figure 1: Example of strongly connected components

Every digraph can be uniquely partitioned (in vertices) into SCCs. An
algorithm by Tarjan (1972) finds a partition in linear time,
$O\left(|V|+|E|\right)$. Figure 1 illustrates a partition into SCCs.

I introduce a graph construction here that is important for the main result.
Construct $\mathcal{G}^{big}=(\mathcal{A},E)$ as follows: each individual is a
vertex. Draw arcs from $i_{k}$ to _all_ vertices $i^{\prime}_{k^{\prime}}$
that are endowed with $\mu(i_{k})$. That is, let
$(i_{k},i^{\prime}_{k^{\prime}})\in E$ if
$\mu(i_{k})=\mu^{E}(i^{\prime}_{k^{\prime}})$. Let $\mathcal{G}^{small}$ be a
digraph representation of $\mu$; an algorithm to construct this is in the
appendix. From here, I will refer to a vertex alternatively as an agent or his
endowed house, where context makes it clear.

######  Example.

Consider the (rationalizable) problem described below.

$\begin{array}[]{ccc}\mathcal{A}&\mu^{E}(\mathcal{A})&\mu(\mathcal{A})\\\
1a&h_{1}&h_{2}\\\ 1b&h_{2}&h_{2}\\\ 1c&h_{4}&h_{5}\\\ 2a&h_{2}&h_{3}\\\
2b&h_{5}&h_{4}\\\ 3&h_{3}&h_{1}\end{array}$

That is, $\mu^{E}(1b)=\mu^{E}(2a)$, and other endowments are unique. The
$\mathcal{G}^{big}$ and an example $\mathcal{G}^{small}$ are given below in
Figure 2.

Figure 2: Example for Theorem 1

Graph $\mathcal{G}^{big}$

$2a$$1a$$3a$$1b$$1c$$2b$

(A particular) Graph $\mathcal{G}^{small}$

$2a$$1a$$3a$$1b$$1c$$2b$

##  4 The main result

I now give necessary and sufficient conditions for a problem to be
rationalizable.

######  Theorem 1.

Fix a problem $\left(A,\mathcal{A},H,\mathbf{L},\mu^{E},\mu\right)$, and
consider $\mathcal{G}^{big}$ constructed from $\mu$. The problem is
rationalizable if and only if: for agents of the same type
$i_{k},i_{k^{\prime}}$ in the same SCC $S$, $\mu(i_{k})=\mu(i_{k^{\prime}})$.
That is, if $i_{k},i_{k^{\prime}}\in S$ are the same type and in the same SCC,
they receive the same house type.

###### Proof.

Appendix. ∎

######  Remark.

I show in Corollary 3 in the appendix that two agents are in the same SCC in
$\mathcal{G}^{big}$ if and only if they are path connected. Then an equivalent
statement is the following. The problem is rationalizable if and only if, for
agents of the same type $i_{k},i_{k^{\prime}}$ when there is a
$(i_{k},i_{k^{\prime}})$-path, $\mu(i_{k})=\mu(i_{k^{\prime}})$.

The full proof is contained in the appendix. A sketch of the proof is as
follows. To prove “if”: First, find the decomposition of $\mathcal{G}^{big}$
into SCCs. Then assign an arbitrary order to the SCCs, and assign preferences
in this order. That is, in the first SCC $S_{1}$, let all agents’ allocated
houses be their first preference. In $S_{2}$, let all agents’ assigned houses
be their first preference if possible, and the second preference if not. The
first key result is that all agents in the same SCC receive the same house
type, so this is a well defined procedure at each step. The second key result
is that all copies of the same house type are contained in the same SCC, so
the procedure never attempts to “re-assign” a preference in a later step. The
argument that this creates no blocking coalitions is similar to the argument
behind Gale’s proof for TTC. To prove “only if”, I show that when the
condition is violated, there is a blocking coalition for all preference
profiles.

######  Example (continued).

The $\mathcal{G}^{big}$ has two SCCs: the left component and the right
component. To apply the theorem, select either arbitrary order. Let the left
component be $S_{1}$, and the right be $S_{2}$.

  1. 1.

In $S_{1}$, assign all agents’ $\succsim_{i}(1)=\mu(i)$, so

$\begin{array}[]{cc}i&\succsim_{i}(1)\\\ 1&h_{2}\\\ 2&h_{3}\\\
3&h_{1}\end{array}$

  2. 2.

In $S_{2}$, assign all agents’ $\succsim_{i}(1)=\mu(i)$ if possible (this is
not possible for anyone here). Otherwise, let $\succsim_{i}(2)=\mu(i)$.

$\begin{array}[]{cc}i&\succsim_{i}(2)\\\ 1&h_{5}\\\ 2&h_{4}\end{array}$

  3. 3.

Assign remaining preferences arbitrarily (omitted).

To check for a blocking coalition, note that $S_{1}$ all receive their
favorite house. Only agents in $S_{2}$ are unsated. Then in any candidate
blocking coalition $(A^{\prime},\mu^{\prime})$, we require
$\mu^{\prime}(1c)=h_{2}$ or $\mu^{\prime}(2b)=h_{3}$. This requires least one
agent in $A^{\prime}\cap S_{1}$ to receive either $h_{4}$ or $h_{5}$, which
are strictly dispreferred.

The condition required in Theorem 1 is easy to check; Tarjan’s algorithm finds
the partition into SCCs in linear time. Within each SCC, checking for a non-
repeated agent type-house type pair is linear in the number of agents.

I have said previously that this paper is tied to object allocation with
indifferences. This is tightly connected to Quint and Wako (2004) in
particular. Their paper establishes a mechanism to find core allocations
through what they term “top trading segmentation.” A segment is a smallest
group of vertices whose neighbors are within the segment. SCCs coincide with
segments in my setting, and my proof “reverse engineers” a partition of the
agents into these segments when possible.

There are two related interpretations of the condition in the theorem. The
first is physical: starting with any house in an SCC, it is possible to make a
series of exchanges to obtain any other house in the same SCC. Then the
necessity that two agents of the same type in an SCC receive the same house
type is immediate. The less well-off agent could execute these exchanges to
receive the better house. The second interpretation is in the context of a
competitive equilibrium market. Famously, Roth and Postlewaite (1977) show
that the strong core is a competitive equilibrium in the typical house
exchange setting with no indifferences. Wako (1983) establishes that a strong
core allocation is also a competitive equilibrium in a the setting with
indifferences. So if $\mu$ is rationalizable and thus
$\mu\in\text{core}(\succsim)$ for some $\succsim$, it is also a competitive
equilibrium.

######  Lemma 1.

If a problem $\left(A,\mathcal{A},H,\mathbf{L},\mu^{E},\mu\right)$ is
rationalizable by a preference profile $\succsim$, then $\mu$ is a competitive
equilibrium.

Similarly to Gale’s TTC proof, the supporting prices are descending in order
of SCCs. Thus if two agents are in the same SCC, their endowments are worth
the same in competitive equilibrium. Again, the necessity of the condition
becomes immediate.

An important implication of Theorem 1 is the following corollary:

######  Corollary 1.

Fix a problem $\left(A,\mathcal{A},H,\mathbf{L},\mu^{E},\mu\right)$ . The
problem is rationalizable only if: whenever agents $i_{k},i_{k^{\prime}}$ are
the same type and $\mu^{E}(i_{k})=\mu^{E}(i_{k^{\prime}})$,
$\mu(i_{k})=\mu(i_{k^{\prime}})$.

###### Proof.

Appendix. ∎

That is, equal agents (of same type and same endowment) must receive the same
house type. Briefly, the theorem requires equal treatment of equals.

######  Corollary 2.

Suppose $\mu^{E}(i_{k})=\mu^{E}(i_{k^{\prime}})$ for all
$k,k^{\prime}\in\\{1,...,K_{i}\\}$ and for all $i\in A$. That is, all agents
of the same type have the same endowment. Then the problem
$\left(A,\mathcal{A},H,\mathbf{L},\mu^{E},\mu\right)$ is rationalizable if and
only if $\mu(i_{k})=\mu(i_{k^{\prime}})$ for all
$k,k^{\prime}\in\\{1,...,K_{i}\\}$ and for all $i\in A$. That is, if and only
if all agents of the same type receive the same house type.

###### Proof.

“Only if” is a consequence of Corollary 1. To prove “if”, note that everyone
of the same type receives the same house type, so we can let everyone’s
favorite house be their allocated house. ∎

This resembles the Debreu and Scarf (1963) theorems for general equilibrium.
Their model is an endowment economy with a finite number of goods, agent
types, $k$ copies of each type, and certain restrictions on preferences. Only
allocations assigning the same bundle to all agents of the same type are in
the core. While neither the Debreu-Scarf model nor my model contains the
other, it would be interesting future work to investigate a whether deeper
connection exists.

The result also solves the analogous problem for two-sided matching in the
strict core. That is, it solves a strict core analogue of Echenique, Lee,
Shum, and Yenmez (2013) with non-transferable utility. There are types of men
and women, and each type has a strict preference over potential partner types.
Here, an agent’s endowment is him- or her- self. An easy way to see this in
the “only if” direction is to let agents’ endowments be themselves and apply
Corollary 1. In this model, agents of the same type always have the same
endowment. Then “equal treatment” means it is necessary for all agents of the
same type must be assigned the same type of partner. To see this is also
sufficient, we can let all agents’ first preference be their assigned partner.

##  5 Conclusion

In this paper, I build a model of aggregate matchings for one-sided matching
with endowments. Stability is falsifiable in this model, and I address the
question of rationalizability: in a setting where the allocations are
observed, but preferences are not, can the allocation be in the core? The main
result gives if and only if conditions for rationalizability; there is an
easily checked condition based on the digraph $\mathcal{G}^{big}$ constructed
from $\mu$. The proof of the result leverages simple ideas from graph theory
and techniques common in matching literature to construct a rationalizing
preference profile. While the setting is highly abstract, I hope this paper is
a helpful base for future research in applied settings.

## References

  * Alcalde-Unzu and Molis (2011) Jorge, Alcalde-Unzu and Elena Molis. 2011. “Exchange of Indivisible Goods and Indifferences: The Top Trading Absorbing Sets Mechanisms.” Games and Economic Behavior. 73(1): 1-16.
  * Bondy and Murty (2008) Bondy, J. Adrian and U.S.R. Murty. 2008. _Graph Theory_. Graduate Texts in Mathematics, Vol. 244\. Springer, Berlin.
  * Chiappori and Salanié (2016) Chiappori, Pierre-André and Bernard Salanié. 2016. “The Econometrics of Matching Models.” Journal of Economic Literature. 54(3): 832-861.
  * Choo and Siow (2006) Choo, Eugene and Aloysius Siow. 2006\. “Who Marries Whom and Why.” Journal of Political Economy. 114(1): 175-201.
  * Debreu and Scarf (1963) Debreu, Gerard and Herbert Scarf. 1963. “A Limit Theorem on the Core of an Economy.” International Economic Review. 3(3): 235-246.
  * Echenique (2008) Echenique, Federico. 2008. “What Matchings Can Be Stable? The Testable Implications of Matching Theory.” Mathematics of Operations Research. 33(3): 757–768.
  * Echenique, Lee, Shum, and Yenmez (2013) Echenique, Federico, Sangmok Lee, Matthew Shum, and M. Bumin Yenmez. 2013. “The Revealed Preference Theory of Stable and Extremal Stable Matchings.” Econometrica. 81(1): 153-171.
  * Gale and Shapley (1962) Gale, David and Lloyd Shapley. 1962\. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly. 69(1): 9-15.
  * Galichon, Kominers, and Weber (2019) Galichon, Alfred, Scott Duke Kominers, and Simon Weber. 2019. “Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility.” Journal of Political Economy. 127(6).
  * Hsieh (2012) Hsieh, Yu-Wei. 2012. “Understanding Mate Preferences from Two-Sided Matching Markets: Identification, Estimation and Policy Analysis.”
  * Hitsch, Hortaçsu, and Ariely (2010) Hitsch, Gunter J., Ali Hortasu, and Dan Ariely. 2010. "Matching and Sorting in Online Dating." American Economic Review, 100(1): 130-63.
  * Quint and Wako (2004) Quint, Thomas and Jun Wako. 2004. “On Houseswapping, the Strict Core, Segmentation, and Linear Programming.” Mathematics of Operations Research, 29(4):861-877.
  * Roth and Postlewaite (1977) Roth, Alvin E. and Andrew Postlewaite. “Weak Versus Strong Domination in a Market with Indivisible Goods.” Journal of Mathematical Economics 4:131-137.
  * Roth and Xing (1997) Roth, Alvin E. and Xiaolin Xing. “Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists.” 1997. Journal of Political Economy. 105(2).
  * Samuelson (1938) Samuelson, Paul A. 1938. “A note on the pure theory of consumers’ behaviour.” Economica, New Series. 5(17): 61-71.
  * Shapley and Scarf (1974) Shapley, Lloyd and Herbert Scarf. 1974. “On Cores and Indivisibility.” Journal of Mathematical Economics. 1(1): 23-37.
  * Tarjan (1972) Tarjan, Robert. 1972. “Depth-first search and linear graph algorithms.” SIAM Journal on Computing. 1(2): 146-160.
  * Veblen (1912) Veblen, Oswald. 1912. “An Application of Modular Equations in Analysis Situs.” Annals of Mathematics, Second Series. 14(1): 86-94.
  * Wako (1983) Wako, Jun. 1983. “A Note on the Strong Core of a Market with Indivisible Goods.” Journal of Mathematical Economics. 13: 189-194.

##  Appendix A Proofs

First, I introduce another graph construction. Given an allocation $\mu$, draw
$\mathcal{G}^{small}=(\mathcal{A},E^{\prime})$ as follows:

  1. Initialize.

Draw all agents $\mathcal{A}$ as vertices. The rest of the procedure takes
$|H|$ steps.

  2. Step $m$.

Consider all agents receiving $h_{m}$, that is all $i_{k}$ such that
$\mu(i_{k})=h_{m}$. Order them according to their index; refer to these as the
“left” side. Similarly, order agents endowed with $h_{m}$ according to their
index; these are the “right” side. By construction, these two sets are the
same cardinality. Draw one arc from the first agent on the left side to the
first agent on the right side, and so on.

The graph produced after $|H|$ steps represents the allocation $\mu$. Note
that each agent has one out-arc and one in-arc. Recall the construction of
$\mathcal{G}^{big}=(\mathcal{A},E)$. Note also that $E\supseteq E^{\prime}$;
that is, $\mathcal{G}^{big}$ is obtained by adding arcs to
$\mathcal{G}^{small}$.

I now provide some intermediate results related to the constructed graphs
$\mathcal{G}^{small}$ and $\mathcal{G}^{big}$. These will be key for the proof
of Theorem 1.

######  Proposition 2.

Consider $\mathcal{G}^{small}=(\mathcal{A},E^{\prime})$ constructed from
$\mu$. $\mathcal{G}^{small}$ has a subgraph partition into cycles. That is,
there are disjoint subgraphs $C_{1},...,C_{N}$ such that
$\mathcal{G}^{small}=\cup_{n=1}^{N}C_{n}$, $C_{m}\cap C_{n}=\emptyset$ for all
$m,n$, and each $C_{n}$ is a cycle.

###### Proof.

Note each vertex $i$ has $d^{-1}(i_{k})=d^{+1}(i_{k})=1$. We can invoke a
version of Veblen’s theorem:

> (Veblen’s theorem) A directed graph $D=(V,E)$ admits a partition of arcs
> into cycles if and only if $d^{-}(v)=d^{+}(v)$ for all vertices $v\in V$.
> (Veblen, 1912; Bondy and Murty, 2008)

Since $d^{-1}(i_{k})=d^{+1}(i_{k})$, $\mathcal{G}^{small}$ has a partition of
arcs into cycles. There are no isolated vertices, so every vertex is in at
least one cycle. Further, since $d^{-1}(i_{k})=d^{+1}(i_{k})=1$ each vertex
must be in at most one cycle. Thus the arc partition into cycles also
partitions the vertices into cycles. ∎

######  Proposition 3.

Consider $\mathcal{G}^{big}$ constructed from $\mu$. For every strongly
connected component $S$ of $\mathcal{G}^{big}$, there is a cycle covering all
vertices in $S$.

###### Proof.

By Proposition 2, $\mathcal{G}^{small}$ admits a partition of vertices into
cycles. Recall $\mathcal{G}^{big}=(\mathcal{A},E)$ and
$\mathcal{G}^{small}=(\mathcal{A},E^{\prime})$, where $E\supseteq E^{\prime}$,
so these cycles also partition $\mathcal{G}^{big}$’s vertices. The SCC $S$ in
$\mathcal{G}^{big}$ is composed of the vertices in a number of
$\mathcal{G}^{small}$-cycles. That is, it cannot include a strict subset of
vertices in a $\mathcal{G}^{small}$-cycle since there is always a path between
any two vertices in a cycle.

The remaining argument is by strong induction on the number $K$ of
$\mathcal{G}^{small}$-cycles contained in $S$. Assign an order to these cycles
in the following way. Let the first cycle be any of these. Choose the $k^{th}$
cycle such that it has the same house type as one of the first $k-1$ cycles.
It is always possible to do this – suppose at some point none of the remaining
cycles has the same house type as the first $k$ cycles. Then there are no
paths in $\mathcal{G}^{big}$ between the first $k$ cycles and the remaining
cycles (recall arcs are drawn from an agent to all agents whose endowment he
receives), so they are not in the same SCC.

  1. Claim.

There is a cycle in $\mathcal{G}^{big}$ covering all vertices in the first $k$
$\mathcal{G}^{small}$-cycles in $S$. For convenience, I will call this the
“big-cycle”, and the $\mathcal{G}^{small}$-cycles will be “small-cycles”.

  2. Base claim.

For $k=1$, the claim is trivial.

  3. $k^{th}$ claim.

Suppose the claim is true for the first $k-1$ cycles. That is, there is a
$k-1^{th}$ big-cycle in $\mathcal{G}^{big}$ covering all the vertices in the
first $k-1$ small-cycles. I show that there is a cycle covering all vertices
in the $k-1^{th}$ big-cycle and the $k^{th}$ small-cycle. The following
argument is illustrated in Figure 3. There are three cases, depending on
whether either cycle is a self-loop.

    1. Case 1.

Suppose neither is a self-loop. Let the big-cycle be $(1a,...,2a,1a)$, and the
$k^{th}$ small-cycle be $(3a,4a,...,3a)$. That is, $\mu(2a)=\mu^{E}(1a)$ and
so on. I do not require that the denoted agents are all different types; e.g.
$2a$ can be $1b$. By the ordering of the cycles, the $k^{th}$ small-cycle and
the big-cycle have at least one of the same house type. Without loss of
generality let $\mu^{E}(1a)=\mu^{E}(4a)$. This gives
$\mu(2a)=\mu^{E}(1a)=\mu^{E}(4a)$, so we have the arc $(2a,4a)\in E$.
Similarly, $\mu(3a)=\mu^{E}(4a)=\mu^{E}(1a)$, so we have the arc $(3a,1a)\in
E$. This gives us a new big-cycle across all the vertices in the first $k$
small-cycles.: $(\underset{\text{big-cycle
}k-1}{\underbrace{1a,...,2a}},\underset{k^{th}\text{
cycle}}{\underbrace{4a,...,3a}},1a)$.

    2. Case 2.

Suppose the $k^{th}$ small-cycle is a self-loop, but the $k-1^{th}$ big-cycle
is not. Then let the big-cycle be $(1a,...,2a,1a)$, and the $k^{th}$ small-
cycle be $(3a,3a)$. Again, let $\mu^{E}(1a)=\mu^{E}(3a)$ without loss of
generality. Then $\mu(2a)=\mu^{E}(1a)=\mu^{E}(3a)$ implies $(2a,3a)\in E$.
Likewise, $\mu(3a)=\mu^{E}(3a)=\mu^{E}(1a)$ implies $(3a,1a)\in E$. So we have
a new big-cycle $(\underset{\text{big-cycle
}k-1}{\underbrace{1a,...,2a}},3a,1a)$. The case if the big-cycle is a self-
loop is analogous (this may occur in the $k=2$ claim).

    3. Case 3.

Suppose both are self-loops. Then let the big-cycle be $(1a,1a)$ and the
$k^{th}$ small-cycle be $(3a,3a)$. Again, we suppose
$\mu^{E}(1a)=\mu^{E}(3a)$. Then $\mu(1a)=\mu^{E}(1a)=\mu^{E}(3a)$ implies
$(1a,3a)\in E$, and likewise $(3a,1a)\in E$. So we have a new big-cycle
$(1a,3a,1a)$.

This completes the proof. ∎

Figure 3: Illustration of Proposition 3

Standard case

$1a$$2a$$3a$$4a$rest of big-cyclerest of small-cycle

Self-loop

$1a$$2a$$3a$rest of big-cycle

The following lemma is derived from Proposition 3 and its proof.

######  Lemma 2.

Consider $\mathcal{G}^{big}$ constructed from $\mu$. Every strongly connected
component $S$ has no in- or out- arcs. That is, if $i_{k}\in
S\subseteq\mathcal{A}$ and $(i_{k},i^{\prime}_{k^{\prime}})\in E$ or
$(i^{\prime}_{k^{\prime}},i_{k})\in E$, then $i^{\prime}_{k^{\prime}}\in S$.

###### Proof.

There is a cycle covering all vertices of $S$ by Proposition 3. Suppose there
is an out-arc from $S$ pointing to a vertex in a different SCC $S^{\prime}$.
$S^{\prime}$ also has a cycle covering all its vertices. The same argument as
in the induction part of the proof of Proposition 3 establishes an arc from
$S^{\prime}$ to $S$. Thus there are paths from between any vertices in $S$ and
$S^{\prime}$, and they are in the same SCC, a contradiction. The case for no
in-arcs is a relabeling of $S$ and $S^{\prime}$. ∎

The following is a corollary of Lemma 2.

######  Corollary 3.

Consider $\mathcal{G}^{big}$ constructed from $\mu$. Let $i_{k}$ and
$i^{\prime}_{k^{\prime}}$ be distinct vertices. There exists a
$(i_{k},i^{\prime}_{k^{\prime}})$-path if and only if $i_{k}$ and
$i^{\prime}_{k^{\prime}}$ are in the same SCC. Equivalently, there exists a
$(i_{k},i^{\prime}_{k^{\prime}})$-path if and only if there exists a
$(i^{\prime}_{k^{\prime}},i_{k})$-path.

###### Proof.

If $i_{k}$ and $i^{\prime}_{k^{\prime}}$ are in the same SCC, there exists a
$(i_{k},i^{\prime}_{k^{\prime}})$-path by definition. Suppose there exists a
$(i_{k},i^{\prime}_{k^{\prime}})$-path. By Lemma 2, there are no paths between
different SCCs, so $i_{k}$ and $i^{\prime}_{k^{\prime}}$ must be in the same
SCC. ∎

######  Corollary 4.

Consider $\mathcal{G}^{big}$ constructed from $\mu$. All copies of the same
house type are in the same SCC. That is, if
$\mu^{E}(i_{k})=\mu^{E}(i^{\prime}_{k^{\prime}})$ and $i_{k}\in S$, then
$i^{\prime}_{k^{\prime}}\in S$.

###### Proof.

Let $\mu^{E}(i_{k})=\mu^{E}(i^{\prime}_{k^{\prime}})$. There is at least one
agent pointing to $i_{k}$, so $\exists a\in\mathcal{A}$ such that
$(a,i_{k})\in E$. Then $(a,i^{\prime}_{k^{\prime}})\in E$ as well by
construction. By Corollary 3, there are $(i_{k},a)$\- and
$(i^{\prime}_{k^{\prime}},a)$\- paths. Then there are
$(i_{k},i^{\prime}_{k^{\prime}})$\- and $(i^{\prime}_{k^{\prime}},i_{k})$\-
paths (through $a$), so $i_{k}$ and $i^{\prime}_{k^{\prime}}$ are in the same
SCC. ∎

If we take Theorem 1 as given for now, we can use the above result to prove
Corollary 1.

###### Proof of Corollary 1.

If if $\mu^{E}(i_{k})=\mu^{E}(i_{k^{\prime}})$, then $i_{k}$ and
$i_{k^{\prime}}$ are in the same SCC. Then apply Theorem 1 to get the desired
result. ∎

###  A.1 Proof of Theorem 1

###### Proof of Theorem 1.

(“If”) Let the supposition be true: whenever agents of the same type are in
the same SCC, they receive the same house type. I find a preference profile
$\succsim$ that such that $\mu\in\text{core}(\succsim)$. First find the
partition of vertices into SCCs. Then assign an arbitrary order to the SCCs,
and denote them $S_{1},...S_{M}$. Construct the preferences by the following
procedure. As helpful notation, let $\succsim_{i}(n)$ denote type $i$’s
$n^{th}$ favorite house.

  1. Step 1.

In $S_{1}$, for all $i\in S_{1}$, let $\succsim_{i}(1)=\mu(i)$. This is well
defined since if there are multiple agents of the same type in $S_{1}$, they
all receive the same house type.

  2. Step 2.

In $S_{2}$, for all $i\in S_{2}$, let $\succsim_{i}(1)=\mu(i)$ if possible.
This is possible if there were no type $i$’s in $S_{1}$. Otherwise, let
$\succsim_{i}(2)=\mu(i)$. By Corollary 4, a house never reappears in a later
step, so this never assigns a house to two places in the same preference.

  3. Step $m$.

In $S_{m}$ for $m=2,...,M$, for all $i\in S_{k}$, let
$\succsim_{i}(m^{\prime})=\mu(i)$ for the lowest unassigned
$m^{\prime}=2,...,m$. Again by the same argument above, this never assigns two
houses to the same type; it also never assigns the same house type to multiple
places in the same preference.

  4. Step $M+1$.

Assign remaining preferences in any order, if necessary.

I now show this preference profile admits no blocking coalition. Suppose that
there is a coalition of agents $A^{\prime}\subseteq\mathcal{A}$ and sub-
allocation $\mu^{\prime}$ such that
$\mu^{\prime}(A^{\prime})=\mu^{E}(A^{\prime})$ and for all $i_{k}\in
A^{\prime}:\mu^{\prime}(i_{k})\succsim_{i}\mu(i_{k})$. The argument is by
strong induction on the number of SCCs $M$. In each SCC $S_{k}$, the claim is
that $\mu^{\prime}(i_{k})=\mu(i_{k})$ for all $i_{k}\in A^{\prime}\cap S_{m}$.

  1. Base case.

In $S_{1}$, all agents receive their favorite house. Then
$\mu^{\prime}(i_{k})\sim_{i}\mu(i_{k})$ for all $i\in A^{\prime}\cap S_{1}$.
The only indifferences are between copies of the same house type, so this
implies $\mu^{\prime}(i_{k})=\mu(i_{k})$.

  2. $m^{th}$ case.

Suppose the claim is true for all agents in
$A^{\prime}\cap\left(S_{1}\cup\cdots\cup S_{m-1}\right)$. This implies that
$\mu^{\prime}$ allocates all agents in
$A^{\prime}\cap\left(S_{1}\cup\cdots\cup S_{m-1}\right)$ houses in their own
SCC. That is, $\mu^{\prime}(i_{k})\in\mu^{E}(A^{\prime}\cap S_{1})$ for all
$i_{k}\in A^{\prime}\cap S_{1}$, and so on. Toward a contradiction, suppose
that $\exists i_{k}\in S_{m}$ such that
$\mu^{\prime}(i_{k}):=h\succ_{i}\mu(i_{k})$. Then it must be
$h\in\mu^{E}\left(S_{1}\cup\cdots\cup S_{m-1}\right)$, since all strictly
preferred houses are in earlier SCCs. Further, since $\mu^{\prime}$
reallocates within $A^{\prime}$, it must be
$h\in\mu^{E}\left(A^{\prime}\cap\left(S_{1}\cup\cdots\cup
S_{m-1}\right)\right)$. But then it must be that an agent in
$S_{1}\cup\cdots\cup S_{m-1}$ receives a house in
$\mu^{E}\left(A^{\prime}\cap\left(S_{m}\cup\cdots\cup S_{M}\right)\right)$.
This contradicts the supposition, so it must be that
$\mu^{\prime}(i_{k})\sim\mu(i_{k})$ for $i_{k}\in A^{\prime}\cap S_{m}$, which
implies $\mu^{\prime}(i_{k})=\mu(i_{k})$.

Thus $\mu^{\prime}(i_{k})=\mu(i_{k})$ for all $i_{k}\in A^{\prime}$, and
$A^{\prime}$ is not a blocking coalition.

(“Only if”) Toward contraposition, suppose there is a SCC $S$ with two agents
of the same type who receive different houses. By Proposition 3, there is a
cycle covering all vertices in $S$. I now construct a blocking coalition using
this cycle. Note that two of these vertices represent agents of the same type
who receive different houses.

  1. 1.

Suppose the cycle is
$1a\rightarrow\underset{:=c}{\underbrace{2a\rightarrow\cdots\rightarrow
1b}}\rightarrow 3a\rightarrow\cdots\rightarrow 1a$, where
$\succsim_{1}=\succsim_{1^{\prime}}$, and $\mu^{E}(2a)\not=\mu^{E}(3a)$.
Without loss of generality let $\mu^{E}(2a)\succ_{1}\mu^{E}(3a)$. Then
$1b\rightarrow\underset{c}{\underbrace{2a\rightarrow\cdots\rightarrow 1b}}$
represents a blocking coalition. Note that this is a feasible sub-allocation;
it contains its own endowment, and $1b$ is strictly better off.

  2. 2.

Suppose the cycle is $1a\rightarrow
1b\rightarrow\underset{:=c}{\underbrace{2a\rightarrow\cdots\rightarrow 1a}}$.
If $\mu^{E}(2a)\succ_{1}\mu^{E}(1b)$, then
$1a\rightarrow\underset{c}{\underbrace{2a\rightarrow\cdots\rightarrow 1a}}$ is
a blocking coalition. If instead $\mu^{E}(1b)\succ_{1}\mu^{E}(2a)$, then $\mu$
is not individually rational for $1b$.

  3. 3.

If the cycle is $1a\rightarrow 1b\rightarrow 1a$ and
$\mu^{E}(1a)\not=\mu^{E}(1b)$, then $\mu$ is not individually rational.

This completes the proof. ∎


# Seeing All From a Few: Nodes Selection Using Graph Pooling for Graph
Clustering

Yiming Wang1111Contact Author Dongxia Chang1 Zhiqiang Fu1&Yao Zhao1
1Beijing Jiaotong University
<EMAIL_ADDRESS>
###### Abstract

Graph clustering aiming to obtain a partition of data using the graph
information, has received considerable attention in recent years. However,
noisy edges and nodes in the graph may make the clustering results worse. In
this paper, we propose a novel dual graph embedding network(DGEN) to improve
the robustness of the graph clustering to the noisy nodes and edges. DGEN is
designed as a two-step graph encoder connected by a graph pooling layer, which
learns the graph embedding of the selected nodes. Based on the assumption that
a node and its nearest neighbors should belong to the same cluster, we devise
the neighbor cluster pooling(NCPool) to select the most informative subset of
vertices based on the clustering assignments of nodes and their nearest
neighbor. This can effectively alleviate the impact of the noise edge to the
clustering. After obtaining the clustering assignments of the selected nodes,
a classifier is trained using these selected nodes and the final clustering
assignments for all the nodes can be obtained by this classifier. Experiments
on three benchmark graph datasets demonstrate the superiority compared with
several state-of-the-art algorithms.

##  1 Introduction

With the advance of information technology, non-Euclidean domain data can be
readily acquired in many domains, such as human pose[?], protein structure[?]
and social networks[?]. With the emergence of non-Euclidean data, graph
clustering methods[?; ?] arise at the historic moment, and it can boost
clustering performance by learning the adjacency between nodes. However, these
conventional graph clustering methods learn graph features relying overly on
the prior knowledge, which may be incomplete for mining the relationship of
nodes.

To mine non-Euclidean graph information, graph neural networks (GNNs)[?; ?]
which can encode both of the graph structure and the node characteristics for
node latent representations was born. GNNs successfully expand deep learning
techniques to the non-Euclidean graph data and have made considerable
achievements in many graph tasks, such as graph classification[?] and visual
question answering[?]. Benefit from the properties of graph convolution, many
GNNs based graph clustering methods[?; ?] have been proposed. These methods
typically construct adjacency matrices based on the k-NN graphs[?] or
attributed graph[?], and learn graph embedding using graph
autoencoder(GAE)[?]. Finally, conventional clustering algorithms such as
k-means[?] are applied based on the learned graph embedding. These methods can
obtain promising results, however, spurious connections in the initial graph
may deteriorate the clustering performance.

In recent years, graph pooling[?] emerged to learn abstract representation of
the input graph by summarizing local components and discarding redundant
information. With growing interest in graph pooling, some improved methods
have been proposed[?; ?]. They utilize localized node features and connecting
relationship to obtain a smaller graph representation. In fact, these graph
pooling methods focus on the graph representation rather than the node
representation. Therefore, they can be used to select the nodes and edges that
best characterize the graph. But it is difficult to apply them directly to
remove noisy edges and nodes in graph clustering.

In this work, we design a new dual graph embedding network(DGEN) to achieve
more efficient and accurate nodes clustering on graph. It learns all node
representations and informative node representations step-by-step, and the two
processes are connected by a graph pooling layer. To reduce the impact of
noisy edges and nodes on graph clustering, we design a novel neighbor cluster
pooling(NCPool), which selects nodes better fitting the clustering
distribution based on the distance of nodes and their nearest neighbors to the
cluster centers. The basic idea of the pooling is that more precise cluster
assignments can be obtained by minimizing the distance of nodes and their
nearest neighbors to the cluster centers. To obtain the nearest neighbor of
each node, we compute the shared nearest neighbor(SNN)[?] similarity on the
attribute graph. After obtaining the selected node representations,
conventional clustering algorithm K-means is used to obtain the local
clustering assignments. Finally, we use these nodes and their labels to train
a classifier which is used to obtain the final clustering assignments. Our
major contributions can be summarized as follows:

  * •

We propose a dual graph embedding network for clustering on the graph-
structured data. To the best of our knowledge, it is the first time to employ
graph pooling to select informative nodes for graph clustering.

  * •

We devise a novel neighbor clustering pooling (NCPool) to capture local graph
information, which can enhance the robustness to the noisy nodes and spurious
edges in the graph effectively.

  * •

Extensive experiments on benchmark graph datasets show that our DGEN
outperforms state-of-the-art graph clustering methods.

##  2 Background

Let a graph be represented by a triple $G=\\{\mathcal{V},\mathcal{E},X\\}$
with $N=|\mathcal{V}|$ nodes and $|\mathcal{E}|$ edges. The $d$-dimensional
feature of each node $v_{i}\in\mathcal{V}$ is denoted by $x_{i}$, and
$X\in\mathbb{R}^{N\times d}$ denotes the node feature matrix. The topological
structure of $G$ can be represented by an adjacency matrix $A$, where
$A_{i,j}=1$ if $(v_{i},v_{j})\in\mathcal{E}$; otherwise $A_{i,j}=0$.

###  2.1 Graph Convolution

Many approaches have been proposed to apply convolution operations to graph
data inspired by filters designed for graph signal processing. And these graph
convolution layer can be written as a nonlinear function like

$H^{(l+1)}=f(H^{(l)},A;\theta^{(l)}),$ (1)

where $H^{(l)}$ denotes the latent representation learned by the $l$-th graph
convolution layer, and $H^{0}=X$ means the feature matrix fed into the first
layer. $f(\cdot)$ represents graph convolution operations. And $\theta^{(l)}$
denotes the trainable weights of the $l$-th layer.

With the advancement of graph convolution, one of the most popular graph
convolution operations can be written as

$H^{(l+1)}=\phi\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}\right),$
(2)

where $\tilde{A}=A+I$ and $\tilde{D}_{i,i}=\sum_{j}\tilde{A}_{i,j}$. $I$ is
the identity diagonal matrix of the graph $A$ for the self-loop in each node.
$\phi(\cdot)$ is an activation function, and $W^{(l)}$ is the trainable
weights matrix.

In this paper, graph attention network(GAT)[?] with multi-head is used to
learn the representation of neighboring nodes adaptively. Let $h^{(l)}_{i}$ be
the latent representation of the node $v_{i}$ learned by the $l$-th layer, and
the GAT with $m$-head can be expressed as

$h^{(l+1)}_{i}={\rm
concat}_{1}^{m}(\phi(\sum_{j\in\mathcal{N}(i)}\alpha^{m}_{i,j}W^{(l)m}h^{(l)}_{j})),$
(3)

where $\mathcal{N}(i)$ denotes the neighboring nodes of $v_{i}$, ${\rm
concat}_{1}^{m}(\cdot)$ means a vector stitching from the first one to $m$-th.
And the attention coefficients $\alpha_{i,j}$ can be computed as

$\alpha_{i,j}=\frac{\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}^{\top}[Wh_{i}\,\|\,Wh_{j}]\right)\right)}{\sum_{k\in\mathcal{N}(i)\cup\\{i\\}}\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}^{\top}[Wh_{i}\,\|\,Wh_{k}]\right)\right)}.$
(4)

###  2.2 Graph Pooling

Graph pooling methods can learn abstract representation of the input graph and
are widely used in graph classification. Current graph pooling methods can be
divided into two classes: learned graph pooling methods and fixed graph
pooling methods.

#### Learned pooling

Learned pooling layer was first proposed by DiffPool[?]. It is a
differentiable graph pooling method that can learn a assignment matrix at each
GNN layer and generate hierarchical representation of graphs. Let
$S^{(l)}\in\mathbb{R}^{n_{l}\times n_{l+1}}$ denotes the learned assignment
matrix in layer $l$, which contains the probability of nodes in layer $l$
being assigned to clusters in the next layer $l+1$. And nodes can be assigned
by the following equation:

$\displaystyle\begin{aligned} &S^{(l)}={\rm softmax}({\rm
GNN}(A^{(l)},H^{(l)})),\\\ &A^{(l+1)}=S^{(l)T}A^{(l)}S^{(l)},\\\
&H^{(l+1)}=S^{(l)T}H^{(l)},\end{aligned}$ (5)

DiffPool works well, but suffers from two main disadvantages for our purpose:
(a) nodes are assigned to the same cluster based on their features, ignoring
adjacent relations and distances; (b) there is no clear mapping between the
nodes of the previous and subsequent layers, which is crucial in clustering
tasks.

#### Fixed pooling

[?] introduced Graph U-Net, which uses a top-$k$ choice of nodes for their
gPool layer, learning a node score and dropping low score nodes. [?] applied
this to graph classification and proposed TopKPool which achieved comparable
performance with DiffPool. gPool employs a trainable projection vector $p$ to
sample nodes based on their scalar projection values. And it can be described
by the following equation:

$\displaystyle\begin{aligned} &y=H^{(l)}p^{(l)}/||p^{(l)}||,\\\ &{\rm i}={\rm
top}_{k}(y,\lceil kN\rceil),\\\ &H^{(l+1)}=(H^{(l)}\odot tanh(y))_{i},\\\
&A^{(l+1)}=A^{(l)}_{i,i},\end{aligned}$ (6)

where $||\cdot||$ is the $L_{2}$ norm, $top_{k}$ selects the top-$k$ indices
from the given input vector, and $\odot$ denotes broadcasted element-wise
multiplication. TopKPool does not break the mapping from the nodes of the
previous layer to the next layer. But the selected nodes may not be
distributed in all essential areas of the graph, which may lead to the
disappearance of clusters in clustering tasks.

##  3 Proposed Methodology

Figure 1: The framework of the proposed DGEN. Our network consists of a two-
step graph embedding, namely learning the representations of all nodes based
on the original graph and learning the representations of selected nodes based
on the pooled local graph.

###  3.1 NCPool

In order to improve the robustness of the graph clustering to the spurious
edges and noisy nodes, we propose NCPool which uses the node features and
graph topology to choose informative nodes that are more suitable for
clustering. In our graph pooling layer, we select and preserve a ratio of
nodes and connect them based on the original graph structure. Since the pooled
graph would lose some information, it is critical to preserve as much valuable
nodes and edges as possible in the pooled graph and remove noisy nodes and
spurious edges. For this purpose, we propose a novel neighbor cluster
pooling(NCPool), preserving the nodes that belong to the same cluster as their
nearest neighbors.

Here, a pooling function $S(\cdot)$ is introduced to select the subset
$\Phi\subset V$ containing $kN$ vertices. And the pooling problem can be
formulated as

$\max_{\Phi\subset V}\ S(\Phi),\ {\rm subject\ to}\ |\Phi|=kN,$ (7)

where $k$ denotes the ratio of selected nodes. We design $S(\Phi)$ based on
the distance metric of the nodes and the cluster centers. In order to select
nodes that fit the clustering distribution better and discard the noisy nodes,
we calculate the clustering centers by K-means[?]. Then, the distance between
the node and each cluster center is calculated and the smallest distance is
used to define the score of the node.

$S(\Phi)=\min\sum_{v_{i}\in\Phi}||H_{v_{i}}-H_{c_{i,j}}||_{F}^{2},$ (8)

where $||\cdot||_{F}^{2}$ is the Frobenius norm, and $H_{v_{i}}$ is the node
representation of $v_{i}$ fed into the pooling layer. The representation of
cluster center $H_{c_{i,j}}$ can be obtained by

$H_{c_{i,j}}=\mathop{\arg\min}||H_{v_{i}}-H_{c_{j}}||_{F}^{2},$ (9)

where $H_{c_{j}}$ denotes the representation of cluster center.

To obtain the distance between the nearest neighbor of each node and the
cluster center, we use the SNN similarity [?] to define the nearest neighbor
on the attributed graph. And the SNN similarity can be written as

$sim(i,j)=\left\\{\begin{matrix}0,&v_{j}\notin\mathcal{N}(i)\\\
|\mathcal{N}(i)\cap\mathcal{N}(j)|,&v_{j}\in\mathcal{N}(i)\end{matrix}\right.$
(10)

The SNN similarity is used to find the nearest neighbor $v_{in}$ of node
$v_{i}$, and the final $S(\Phi)$ can be calculated by

$S(\Phi)=\min\sum_{v_{i}\in\Phi}||H_{v_{i}}-H_{c_{i,j}}||_{F}^{2}+||H_{v_{in}}-H_{c_{i,j}}||_{F}^{2},$
(11)

where $H_{v_{in}}$ denotes the node representation of $v_{in}$.

After obtaining the clustering score, we apply the node selection method
proposed by [?; ?], which retains a portion of nodes of the input graph even
when graphs of varying sizes and structures are inputted. The top $\lceil
kN\rceil$ nodes are selected based on the value of $S$.

$idx={\rm top}_{k}(S,\lceil kN\rceil),$ (12)

And an input graph is processed by the following operation.

$H^{\prime}=H_{idx,:}\odot(\mathbf{a}\mathbf{1}^{T}),\ \
A^{\prime}=A_{idx,idx}$ (13)

where $\mathbf{a}$ denotes an affinity vector consisting of the score for the
selected nodes, and $\mathbf{1}$ is an all-one vector. $H_{idx,:}$ is the row-
wise indexed feature matrix, and $A_{idx,idx}$ is the row-wise and col-wise
indexed adjacency matrix.

###  3.2 Dual graph embedding network

In this section, the proposed dual graph embedding network(DGEN) which learns
the graph embedding of informative nodes for graph clustering is described in
detail. The overall framework is shown in Fig. 1. In our model, the global
graph embedding $H_{g}$ is first learned via the global GAT encoder. Then,
$H_{g}$ is fed into our NCPool to obtain informative nodes and edges, and the
final embedding $Z$ is obtained by the local GAT encoder. Finally, the local
clustering process is eventually conducted on the informative embedding Z, and
we use them as labels to train a GAT classifier which is used to obtain the
final clustering assignments for all the nodes.

As mentioned in Section 2.1, our DGEN architecture is designed based on a
graph attention network (GAT). In order to adaptively combine the attributes
of neighboring nodes to learn the representations of nodes, our GAT encoder
consists of two layers of GAT with multi-head. In order to guide the GAT
encoder to learn a comprehensive node representation, an inner product decoder
is applied to reconstruct the graph data $\hat{A}$ from the global
representation $Z$.

$\hat{A}_{i,j}={\rm sigmoid}(z_{i}\cdot z_{j}^{T})$ (14)

where $\hat{A}_{i,j}$ denotes the adjacency of node $v_{i}$ and node $v_{j}$
in the reconstructed graph $\hat{A}$. Then, we minimize the reconstruction
error by measuring the difference between $A$ and $\hat{A}$.

$L_{r}=\sum_{i}^{N}loss(A_{i,j},\hat{A}_{i,j})$ (15)

As mentioned before, we have learned the graph embedding. However, the
traditional graph networks is in the semi-supervised learning scenario which
may not be guaranteed suitable for clustering. And the clustering task is
naturally unsupervised and feedback during training as to whether the learned
embedding is well optimized cannot be obtained[?]. Inspired by DEC[?], we
develop a self-optimizing training module as a solution to overcome this
difficulty.

For the $i$-th node and $j$-th cluster, we use the Student’s t-distribution[?]
to measure the similarity between the global representation $z_{i}$ and the
cluster center vector $\mu_{j}$ as follows:

$q_{ij}=\frac{(1+||z_{i}-\mu_{j}||^{2})^{-1}}{\sum_{k}(1+||z_{i}-\mu_{k}||^{2})^{-1}}$
(16)

where $z_{i}$ is the $i$-th row of $Z$ , $\mu_{j}$ is initialized by K-means
on the pre-trained representation. $q_{ij}$ can be seen as the probability of
assigning node $z_{i}$ to cluster $j$, i.e., a soft assignment distribution of
each node. $Q=[q_{ij}]$ is the distribution of the assignments of all nodes.

After obtaining the clustering distribution of each node, the node
representation should be trained to match the distribution. Specifically, we
want to make the representations closer to cluster centers, thus making the
nodes within the same cluster gather densely. Hence, we calculate a target
distribution of each node as follows:

$p_{ij}=\frac{q_{ij}^{2}/\sum_{i}q_{ij}}{\sum_{k}(q_{ik}^{2}/\sum_{i}q_{ik})}$
(17)

Soft assignments with high probability are considered to be trustworthy in
$Q$. So the target distribution $P$ raises $Q$ to the second power to get a
denser distribution. To make the distribution $Q$ approach the target
distribution $P$, the clustering loss of DGEN can be written as follows:

$L_{c}=KL(P||Q)=\sum_{i}\sum_{j}p_{ij}\rm{log}\frac{p_{ij}}{q_{ij}}$ (18)

By minimizing the KL divergence loss between distributions $P$ and $Q$, it can
help to learn the node representations more suitable for clustering task.
Specifically, it can make the nodes within the same cluster are gathered
densely and the boundaries between different clusters are distinct. Thus, the
total objective function of DGEN is defined as:

$L=L_{r}+\lambda L_{c}$ (19)

where $L_{r}$ and $L_{c}$ are the reconstruction loss and clustering loss
respectively, and $\lambda$ is the hyperparameter balancing these two losses.

Therefore, we can obtain the clustering assignments of the selected nodes
based on the local graph embedding. However, our goal is to classify all nodes
into different clusters. To obtain the global clustering assignments, a
classifier is trained using the clustering assignments of selected nodes as
labels. And the final clustering assignments can be obtained by inputting all
nodes to the classifier. There is a notable advantage for our model to use the
classifier to obtain the final clustering assignments instead of obtaining
directly based on the adjacent relations. Spurious edges between discard nodes
and selected nodes can lead to inaccurate classification.

##  4 Experiments

###  4.1 Experimental Settings

Dataset | Clusters | Nodes | Features | Links
---|---|---|---|---
Cora | 7 | 2708 | 1433 | 5429
CiteSeer | 6 | 3327 | 3703 | 4732
PubMed | 3 | 19717 | 500 | 44338
Table 1: Benchmark Graph Datasets.

Method | Info. | Cora | CiteSeer | PubMed
---|---|---|---|---
ACC | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI
K-means | X | 0.500 | 0.317 | 0.239 | 0.544 | 0.312 | 0.285 | 0.580 | 0.278 | 0.246
Spectral | G | 0.398 | 0.297 | 0.174 | 0.308 | 0.090 | 0.082 | 0.496 | 0.147 | 0.098
DNGR | G | 0.419 | 0.318 | 0.142 | 0.326 | 0.180 | 0.043 | 0.468 | 0.153 | 0.059
M-NMF | G | 0.423 | 0.256 | 0.161 | 0.336 | 0.099 | 0.070 | 0.470 | 0.084 | 0.058
GAE | G&X | 0.530 | 0.397 | 0.293 | 0.380 | 0.174 | 0.141 | 0.632 | 0.249 | 0.246
VGAE | G&X | 0.592 | 0.408 | 0.347 | 0.392 | 0.163 | 0.101 | 0.619 | 0.216 | 0.201
MGAE | G&X | 0.684 | 0.511 | 0.448 | 0.661 | 0.412 | 0.414 | 0.593 | 0.282 | 0.248
ARGAE | G&X | 0.640 | 0.449 | 0.352 | 0.573 | 0.350 | 0.341 | 0.681 | 0.276 | 0.291
ARVGAE | G&X | 0.638 | 0.450 | 0.374 | 0.544 | 0.261 | 0.245 | 0.513 | 0.117 | 0.078
DAEGA | G&X | 0.704 | 0.528 | 0.496 | 0.672 | 0.397 | 0.410 | 0.671 | 0.266 | 0.278
GATE | G&X | 0.658 | 0.527 | 0.451 | 0.616 | 0.401 | 0.381 | 0.673 | 0.322 | 0.299
DBGAN | G&X | 0.748 | 0.560 | 0.540 | 0.670 | 0.407 | 0.414 | 0.694 | 0.324 | 0.327
DGEN | G&X | 0.771 | 0.576 | 0.566 | 0.686 | 0.430 | 0.445 | 0.695 | 0.297 | 0.320

Table 2: Performance comparisons of various methods on three benchmark
datasets.

In order to evaluate the effectiveness of our proposed method, we conduct
experiments on three citation networks widely-used for assessment of
attributed graph analysis. For convenience, these datasets are summarized in
Table 1. Moreover, three standard evaluation metrics: Accuracy (ACC),
Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI) are used to
evaluated the performance. In all cases, the values of these metrics are range
between 0 and 1, where higher values correspond to better clustering
performance.

The ratio of selected nodes of NCPool is set to 0.6, and the hyperparameter
$\lambda$ is set to 10. The implementation details such as network
architecture and implementation environment are reported in the supplementary
material.

###  4.2 Baseline Methods

In order to verify the effectiveness of the proposed DGEN, we compare it with
a total of 12 clustering algorithms, including methods that use only node
attribute or graph structure, and methods using both.

  * •

Using node attribute: Kmeans[?];

  * •

Using graph structure: Spectral clustering[?], denoising autoencoder for graph
embedding (DNGR)[?], and modularized nonnegative matrix factorization
(M-NMF)[?];

  * •

Using both node attribute and graph structure: Graph auto-encoders (GAE) and
variational graph auto-encoders (VGAE)[?], marginalized graph autoencoder
(MGAE)[?], adversarial regularized graph autoencoder (ARGAE) and adversarial
variational regularized graph autoencoder (ARVGAE)[?], deep attentional
embedding graph clustering (DAEGA)[?], graph attention auto-encoders
(GATE)[?], and distribution-induced bidirectional generative adversarial
network (DBGAN)[?].

###  4.3 Experiment Results

#### Evaluation Metrics.

The results on the three benchmark datasets are reported in Table 2, where the
top value is highlighted in red font and the second best in blue. $X$, $G$,
and $G$&$X$ indicate the method uses only node attribute, graph structure, or
both attribute and structure information, respectively. According to these
results, we have the following observations: (1) our proposed method
outperforms the competing methods on these benchmark datasets in most cases.
For example, our method gains large improvements around 11.3%, 11.5% over the
base method GATE in terms of ACC and ARI on Cora, respectively; (2) methods
using both node attribute and graph structure consistently obtain better
performances than methods using only one type of information. It demonstrates
that both the graph structure and node attribute contain useful information
for graph clustering; (3) our algorithm boosts the clustering performance over
other GNN-based method, which indicates the feasibility of applying graph
pooling to graph clustering and the effectiveness of our proposed NCPool.
Although the second best baseline (DBGAN) outperforms our DGEN in several
cases, which is at the cost of a higher representation dimension.

(a) Cora(raw)

(b) Cora(GAE)

(c) Cora(GATE)

(d) Cora(DGEN-G)

(e) Cora(DGEN-L)

(f) PubMed(raw)

(g) PubMed(GAE)

(h) PubMed(GATE)

(i) PubMed(DGEN-G)

(j) PubMed(DGEN-L)

Figure 2: t-SNE visualizations of representations learned by various methods
on Cora (top row) and PubMed (bottom row).

#### Visualization.

In order to show the superiority of the representation obtained by our method,
we visualize the results of different methods on Cora and PubMed with
t-SNE[?]. The results are shown in Fig. 2, where DGEN-G and DGEN-L denotes the
representation of global-graph embedding and local-graph embedding,
respectively. From Fig. 2, it can be seen that the cluster structure of data
recovered by our method is better which has smaller intra-cluster scatter and
larger inter-cluster scatter. Meanwhile, we can see that representation from
DGEN-L has lower intra-cluster error points compared with DGEN-G, which
demonstrates the effectiveness of our proposed NCPool.

(a) ACC

(b) NMI

Figure 3: Visualization the change of parameter $\lambda$.

#### Impact of hyperparameter $\lambda$.

In our proposed model, there is a main hyperparameter $\lambda$ that balance
the reconstruction loss and clustering loss. In the following, we will analyze
the sensitivity of this parameter in the proposed method. In the experiments,
we tune $\lambda$ from $\\{10^{-2},10^{-1},1,10,10^{2},10^{3},10^{4}\\}$ and
the ACC and NMI of the final clustering results with different $\lambda$
(taking Cora and CiteSeer as examples) are shown in Fig. 3. As shown in Fig.
3, when $\lambda$ is between $10$ and $100$, the corresponding evaluation
metrics ACC and NMI will largely remain the same.

#### Impact of ratio of reserved nodes.

The current graph pooling methods usually set the ratio to 0.6. Since our goal
is to learn the representations of nodes rather than representation of the
graph, we do not use the common settings in our approach. We search it in the
range of $\\{0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9\\}$. And Fig. 4 shows the results
of our method using different ratio of reserved nodes (taking CiteSeer as an
example). It is observed that the promising performance could be expected when
the ratio of reserved nodes is between 0.6 and 0.7.

Figure 4: The parameter effect of ratio of reserved nodes.

##  5 Conclusions

In this paper, we propose a dual graph embedding network(DGEN) to learn a more
robust representation for graph clustering. Like most graph learning methods,
we first learn the global graph embedding using the global GAT encoder. In
order to reduce the effect of noisy edges and nodes on graph clustering, a
novel neighbor cluster pooling(NCPool) is designed which can select the most
informative subset of vertices based on the clustering assignments of nodes
and their nearest neighbors. The pooling is based on the assumption that more
precise cluster assignments can be obtained by minimizing the distance of the
nodes and their nearest neighbors to the cluster centers. Then the local GAT
encoder is utilized to learn local graph embedding on the selected nodes and
edges. To train the whole model, we apply a self-optimizing clustering loss
and autoencoder reconstruction loss to make the learned representation more
suitable for clustering. After obtaining the representations of selected
nodes, a conventional clustering algorithm K-means is used to obtain the local
clustering assignments. Then, we use the local clustering assignments as
labels to train a classifier and the final clustering assignments of all nodes
can be obtained by this classifier. The effectiveness of the proposed method
is validated by comparing its experimental results with various state-of-the-
art algorithms.

## References

  * [Arthur and Vassilvitskii, 2007] David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In SODA, pages 1027–1035, 2007.
  * [Bianchi et al., 2020] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi.  Spectral clustering with graph neural networks for graph pooling.  In ICML, pages 874–883, 2020.
  * [Bo et al., 2020] Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui.  Structural deep clustering network.  In WWW, pages 1400–1410, 2020.
  * [Cangea et al., 2018] Catalina Cangea, Petar Velickovic, Nikola Jovanovic, Thomas Kipf, and Pietro Liò.  Towards sparse hierarchical graph classifiers.  arXiv preprint, 1811.01287, 2018.
  * [Cao et al., 2016] Shaosheng Cao, Wei Lu, and Qiongkai Xu.  Deep neural networks for learning graph representations.  In AAAI, pages 1145–1152, 2016.
  * [Cheng et al., 2020] Jiafeng Cheng, Qianqian Wang, Zhiqiang Tao, De-Yan Xie, and Quanxue Gao.  Multi-view attribute graph convolution networks for clustering.  In IJCAI, pages 2973–2979, 2020.
  * [Defferrard et al., 2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In NIPS, pages 3837–3845, 2016.
  * [Dhelim et al., 2020] Sahraoui Dhelim, Nyothiri Aung, and Huansheng Ning.  Mining user interest based on personality-aware hybrid filtering in social networks.  Knowl. Based Syst., 206:106227, 2020.
  * [Fan et al., 2020] Shaohua Fan, Xiao Wang, Chuan Shi, Emiao Lu, Ken Lin, and Bai Wang.  One2multi graph autoencoder for multi-view graph clustering.  In WWW, pages 3070–3076, 2020.
  * [Gao and Ji, 2019] Hongyang Gao and Shuiwang Ji.  Graph u-nets.  In ICML, pages 2083–2092, 2019.
  * [Jarvis and Patrick, 1973] Raymond Austin Jarvis and Edward A Patrick.  Clustering using a similarity measure based on shared near neighbors.  IEEE Trans. comput., 100(11):1025–1034, 1973.
  * [Kipf and Welling, 2016] Thomas N. Kipf and Max Welling.  Variational graph auto-encoders.  arXiv preprint, 1611.07308, 2016.
  * [Kipf and Welling, 2017] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In ICLR, 2017.
  * [Lee et al., 2019] Junhyun Lee, Inyeop Lee, and Jaewoo Kang.  Self-attention graph pooling.  In ICML, pages 3734–3743, 2019.
  * [Li et al., 2019] Linjie Li, Zhe Gan, Yu Cheng, and Jingjing Liu.  Relation-aware graph attention network for visual question answering.  In ICCV, pages 10312–10321, 2019.
  * [Li et al., 2020] Maosen Li, Siheng Chen, Ya Zhang, and Ivor W. Tsang.  Graph cross networks with vertex infomax pooling.  In NeurIPS, 2020.
  * [Maaten and Hinton, 2008] Laurens Van Der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  JMLR, 9(2605):2579–2605, 2008.
  * [Newell et al., 2016] Alejandro Newell, Kaiyu Yang, and Jia Deng.  Stacked hourglass networks for human pose estimation.  In ECCV, pages 483–499, 2016.
  * [Ng et al., 2001] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In NIPS, pages 849–856, 2001.
  * [Pan et al., 2018] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang.  Adversarially regularized graph autoencoder for graph embedding.  In IJCAI, pages 2609–2615, 2018.
  * [Salehi and Davulcu, 2020] Amin Salehi and Hasan Davulcu.  Graph attention auto-encoders.  In ICTAI, pages 989–996, 2020.
  * [Shi and Malik, 2000] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888–905, 2000\.
  * [Velickovic et al., 2018] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In ICLR, 2018.
  * [Wang et al., 2017] Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang.  MGAE: marginalized graph autoencoder for graph clustering.  In ACMCIKM, pages 889–898, 2017.
  * [Wang et al., 2019] Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang.  Attributed graph clustering: A deep attentional embedding approach.  In IJCAI, pages 3670–3676, 2019.
  * [Wang et al., 2020] Hao Wang, Yan Yang, and Bing Liu.  GMC: graph-based multi-view clustering.  IEEE Trans. Knowl. Data Eng., 32(6):1116–1129, 2020.
  * [Xiao et al., 2017] Wang Xiao, Cui Peng, Wang Jing, Pei Jian, Zhu Wenwu, and Yang Shiqiang.  Community preserving network embedding.  In AAAI, pages 203–209, 2017.
  * [Xie et al., 2016] Junyuan Xie, Ross B. Girshick, and Ali Farhadi.  Unsupervised deep embedding for clustering analysis.  In ICML, pages 478–487, 2016.
  * [Ying et al., 2018] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  In NeurIPS, pages 4805–4815, 2018.
  * [Zheng et al., 2020] Shuai Zheng, Zhenfeng Zhu, Xingxing Zhang, Zhizhe Liu, Jian Cheng, and Yao Zhao.  Distribution-induced bidirectional generative adversarial network for graph representation learning.  In CVPR, pages 7222–7231, 2020.