# Ramsey theory constructions from hypergraph matchings

Felix Joos  Institut für Informatik, Universität Heidelberg, Germany. Research
supported by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) – 428212407<EMAIL_ADDRESS>and  Dhruv Mubayi
Department of Mathematics, Statistics, and Computer Science, University of
Illinois, Chicago, IL, 60607 USA. Research partially supported by NSF grants
DMS-1763317, 1952767, 2153576 and a Humboldt Research Award<EMAIL_ADDRESS>
###### Abstract.

We give asymptotically optimal constructions in generalized Ramsey theory
using results about conflict-free hypergraph matchings. For example, we
present an edge-coloring of $K_{n,n}$ with $2n/3+o(n)$ colors such that each
$4$-cycle receives at least three colors on its edges. This answers a question
of Axenovich, Füredi and the second author (On generalized Ramsey theory: the
bipartite case, J. Combin. Theory Ser B 79 (2000), 66–86). We also exhibit an
edge-coloring of $K_{n}$ with $5n/6+o(n)$ colors that assigns each copy of
$K_{4}$ at least five colors. This gives an alternative very short solution to
an old question of Erdős and Gyárfás that was recently answered by Bennett,
Cushman, Dudek, and Prałat by analyzing a colored modification of the triangle
removal process.

##  1\. Introduction

Given graphs $G$ and $H$, an $(H,q)$-coloring of $G$ is an edge-coloring of
$G$ such that every copy of $H$ in $G$ receives at least distinct $q$ colors.
Let $r(G,H,q)$ be the minimum number of colors in an $(H,q)$-coloring of $G$.
Classical Ramsey numbers for multicolorings are the special case
$G=K_{n},H=K_{p},q=2$. Initiated by Erdős and Shelah [5, 6], and subsequently
developed by Erdős and Gyárfás [7] and by Axenovich, Füredi and the second
author [2], this generalization of Ramsey numbers has given rise to many
interesting problems that have been studied over the years [1, 4, 10, 11].

One of the main problems posed in [2] was to determine the asymptotics of the
smallest open bipartite case when $q>2$, namely, $r(K_{n,n},C_{4},3)$. In this
paper we answer this question by proving

(1) $r(K_{n,n},C_{4},3)=2n/3+o(n).$

Since the work of [2], it was evident why proving (1) would be challenging.
Indeed, the lower bound argument shows that the required coloring must arise
from an asymptotically optimal resolvable bipartite partial Steiner quadruple
system, where the union of any two color classes has girth at least five
(given an appropriate notion of girth). The girth condition between color
classes is the most difficult part of this construction. Using very recent
work of Glock, Kim, Kühn, Lichev, and the first author [8] on conflict-free
hypergraph matchings we are able to provide such a construction.

Our method also yields

(2) $\displaystyle r(K_{n},K_{4},5)=5n/6+o(n).$

This gives a new proof of a very recent result of Bennett, Cushman, Dudek, and
Prałat [3] which answered a question of Erdős and Gyárfás [7]. In [3], the
authors analyze a modification of the triangle removal process where each
selected triangle receives two colors (one which is used twice and one which
is used once). In addition, certain vertices are not allowed to be incident to
a given set of colors and at no point of the process is a 2-colored 4-cycle
allowed to be created. Not surprisingly, the analysis of this process is
technically involved and challenging.

One of the main messages of this paper is that such an intricate analysis is
not needed, as the main result in [8] implies results of this type even in
this fairly involved and particular setting with colors and further
constraints. This is achieved by translating the edge-coloring problem to the
problem of obtaining a large matching in a suitable auxiliary hypergraph.
Presenting this translation is one of our main contributions. We are confident
that this will be helpful in many other scenarios as well. To be clear, it is
still probably helpful to propose a random process that creates the desired
outcome with high probability, but the analysis may not be needed as the
process may be described as a hypergraph matching process and then the result
in [8] can be applied.

##  2\. Hypergraph matchings with conflicts and other preliminaries

In this section we state a simplified version of the conflict-free hypergraph
matching theorem from [8], which is the main tool that we use in our proofs.
Roughly speaking, this result says that vertex-regular uniform hypergraphs
$\mathcal{H}$ with small codegrees admit almost perfect matchings that avoid
specified edge conflicts. Here, conflicts are sets of disjoint edges, modelled
as edges of a hypergraph $\mathcal{C}$ with vertex set $E(\mathcal{H})$, which
could, in principle, appear as a subset of the matching. The theorem
guarantees that all these subsets of edges can be avoided in an almost perfect
matching provided the conflicts satisfy some natural (and necessary)
conditions.

We refer to a $k$-uniform hypergraph as a $k$-graph and identify the edge set
with the hypergraph. For a not necessarily uniform hypergraph $\mathcal{C}$
and an integer $k$, we use $\mathcal{C}^{(k)}$ to denote the subgraph of
$\mathcal{C}$ comprising all edges of size exactly $k$. For a vertex $e$ of
$\mathcal{C}$, we write $\mathcal{C}_{e}$ for the set of all
$C\setminus\\{e\\}$ with $C\in\mathcal{C}$ and $e\in C$. For a hypergraph
$\mathcal{H}$ and a vertex $v$ of $\mathcal{H}$, we use $d_{\mathcal{H}}(v)$
to denote the _degree_ of $v$; that is, the number of edges containing $v$. We
use $\Delta(\mathcal{H})=\max_{u\in V(\mathcal{H})}d_{\mathcal{H}}(u)$ to
denote the _maximum degree_ of $\mathcal{H}$ and, similarly, we define the
_minimum degree_ $\delta(\mathcal{H})$ of $\mathcal{H}$. For $j\geq 2$, we
denote by $\Delta_{j}(\mathcal{H})$ the maximum number of edges that contain a
particular set of $j$ vertices. We also define $[k]=\\{1,\ldots,k\\}$. We use
standard asymptotic notation $o(\cdot),O(\cdot),\Theta(\cdot)$ as
$n\to\infty$, which we always treat as (a set of) non-negative functions.

For a hypergraph $\mathcal{H}$, we refer to $\mathcal{C}$ as a _conflict
system_ for $\mathcal{H}$ if $\mathcal{C}$ is hypergraph with vertex set
$E(\mathcal{H})$. We say that a set $E$ of edges of $\mathcal{H}$ is
_$\mathcal{C}$ -free_ if no $C\in\mathcal{C}$ is a subset of $E$. For integers
$d\geq 1,\ell\geq 3$ and $\varepsilon\in(0,1)$, we say that $\mathcal{C}$ is
_$(d,\ell,\varepsilon)$ -bounded_ if the following holds.

  1. (C1)

$3\leq|C|\leq\ell$ for all $C\in\mathcal{C}$;

  2. (C2)

$\Delta(\mathcal{C}^{(j)})\leq\ell d^{j-1}$ for all $3\leq j\leq\ell$;

  3. (C3)

$\Delta_{j^{\prime}}(\mathcal{C}^{(j)})\leq d^{j-j^{\prime}-\varepsilon}$ for
all $3\leq j\leq\ell$ and $2\leq j^{\prime}\leq j-1$.

This means $\mathcal{C}$ is $(d,\ell,\varepsilon$)-bounded if the conflicts
have size at most $\ell$ and that for all uniform subgraphs of $\mathcal{C}$
the degrees and codegrees are not too large.

Suppose now that $\mathcal{C}$ is $(d,\ell,\varepsilon$)-bounded. The
following concept of weight functions can be used to ensure that the provided
almost perfect matching admits quasirandom properties. A _test function_ for
$\mathcal{H}$ is a function $w\colon\binom{\mathcal{H}}{j}\rightarrow[0,\ell]$
where $j\in\mathbb{N}$ such that $w(E)=0$ whenever
$E\in\binom{\mathcal{H}}{j}$ is not a matching. We refer to $j$ as the
uniformity of $w$ and we say that $w$ is $j$-uniform. In general, for a
function $w\colon A\rightarrow\mathbb{R}$ and a finite set $X\subset A$, we
define $w(X):=\sum_{x\in X}w(x)$. If $w$ is a $j$-uniform test function, we
also use $w$ to denote the extension of $w$ to arbitrary subsets of
$\mathcal{H}$ such that for all $E\subset\mathcal{H}$, we have
$w(E)=w(\binom{E}{j})$. For $j,d\in\mathbb{N}$, $\varepsilon>0$ and a conflict
system $\mathcal{C}$ for $\mathcal{H}$, we say that a $j$-uniform test
function $w$ for $\mathcal{H}$ is  _$(d,\varepsilon,\mathcal{C})$ -trackable_
if the following holds.

  1. (W1)

$w(\mathcal{H})\geq d^{j+\varepsilon}$;

  2. (W2)

$w(\\{E\in\binom{\mathcal{H}}{j}\colon E\supseteq E^{\prime}\\})\leq
w(\mathcal{H})/d^{j^{\prime}+\varepsilon}$ for all $j^{\prime}\in[j-1]$ and
$E^{\prime}\in\binom{\mathcal{H}}{j^{\prime}}$;

  3. (W3)

$|(\mathcal{C}_{e})^{(j^{\prime})}\cap(\mathcal{C}_{f})^{(j^{\prime})}|\leq
d^{j^{\prime}-\varepsilon}$ for all $e,f\in\mathcal{H}$ with
$w(\\{E\in\binom{\mathcal{H}}{j}\colon e,f\in E\\})>0$ and all
$j^{\prime}\in[\ell-1]$;

  4. (W4)

$w(E)=0$ for all $E\in\binom{\mathcal{H}}{j}$ that are not $\mathcal{C}$-free.

######  Theorem 2.1 ([8, Theorem 3.3]).

For all $k,\ell\geq 2$, there exists $\varepsilon_{0}>0$ such that for all
$\varepsilon\in(0,\varepsilon_{0})$, there exists $d_{0}$ such that the
following holds for all $d\geq d_{0}$. Suppose $\mathcal{H}$ is a $k$-graph on
$n\leq\exp(d^{\varepsilon^{3}})$ vertices with
$(1-d^{-\varepsilon})d\leq\delta(\mathcal{H})\leq\Delta(\mathcal{H})\leq d$
and $\Delta_{2}(\mathcal{H})\leq d^{1-\varepsilon}$ and suppose $\mathcal{C}$
is a $(d,\ell,\varepsilon)$-bounded conflict system for $\mathcal{H}$. Suppose
$\mathscr{W}$ is a set of $(d,\varepsilon,\mathcal{C})$-trackable test
functions for $\mathcal{H}$ of uniformity at most $\ell$ with
$|\mathscr{W}|\leq\exp(d^{\varepsilon^{3}})$. Then, there exists a
$\mathcal{C}$-free matching $\mathcal{M}\subset\mathcal{H}$ of size at least
$(1-d^{-\varepsilon^{3}})n/k$ with $w(\mathcal{M})=(1\pm
d^{-\varepsilon^{3}})d^{-j}w(\mathcal{H})$ for all $j$-uniform
$w\in\mathscr{W}$.

##  3\. $r(K_{n,n},C_{4},3)$

It is shown in [2] that $r(K_{n,n},C_{4},3)\geq 2n/3$. Hence it order to prove
(1), it suffices to show that there exists $\delta>0$ for which
$r(K_{n,n},C_{4},3)\leq 2n/3+n^{1-\delta}$ by providing a coloring of
$K_{n,n}$ with at most $2n/3+n^{1-\delta}$ colors such that any $4$-cycle in
$K_{n,n}$ receives at least three colors. Our construction is obtained in two
stages. In the first stage, we translate the problem to a question about
hypergraph matchings and then apply Theorem 2.1. This produces an edge-
coloring of all but $O(n^{2-\delta})$ edges of $K_{n,n}$. Moreover, the
distribution of the uncolored edges admits certain quasirandomness properties.
In the second stage, we color the uncolored edges randomly with a new set of
colors and ensure, by the local lemma, that all $4$-cycles receive at least
three colors.

We proceed with the first part. To this end, we need the following notation.
For $k\geq 2$, a cycle of length $k$ in a hypergraph is a collection of $k$
distinct edges $\\{e_{1},\ldots,e_{k}\\}$ such that there exist $k$ distinct
vertices $v_{1},\ldots,v_{k}$ with $e_{i}\cap e_{i+1}=\\{v_{i}\\}$ for all
$i\in[k]$, where indices are taken modulo $k$. The girth of a hypergraph
$\mathcal{H}$ is the minimum length of a cycle in $\mathcal{H}$. For disjoint
sets $X,Y$, we write $B(X,Y)$ for the complete bipartite graph with parts
$X,Y$.

######  Theorem 3.1.

There exists $\delta>0$ such that for all sufficiently large $n$ in terms of
$\delta$, there exists an edge-coloring of a subgraph of $G\subset B(X,Y)\cong
K_{n,n}$ with at most $2n/3$ colors and the following properties:

  1. (I)

Every color class consists of vertex-disjoint 3-edge stars.

  2. (II)

Given any two colors $i,j$, the 4-graph with vertex set $X\cup Y$ where each
edge is formed by the vertex set of a star in color $i$ or $j$ has girth at
least 5.

  3. (III)

The graph $L=B(X,Y)-E(G)$ has maximum degree at most $n^{1-\delta}$.

  4. (IV)

For each $(x,y)\in X\times Y$, the number of $x^{\prime}y^{\prime}\in E(L)$
with $x^{\prime}\in X\setminus\\{x\\},y^{\prime}\in Y\setminus\\{y\\}$ such
that $xy^{\prime},yx^{\prime}$ receive the same color is at most
$n^{1-\delta}$.

###### Proof.

Our aim is to apply Theorem 2.1. To this end, we define the following
10-uniform hypergraph $\mathcal{H}$ as follows. Let $X,Y$ be two disjoint
vertex sets of size $n$. The vertex set of $\mathcal{H}$ is $U\cup V$, where
$U={X\cup Y\choose 2}$ and $V=\bigcup_{i\in[2n/3]}V_{i}$ where each $V_{i}$ is
a copy of $V(B(X,Y))=X\cup Y$. Let $\mathcal{T}$ be the collection of 4-sets
in $X\cup Y$ which have exactly one or three vertices in $X$. Given
$e\in\mathcal{T}$ and $i\in[2n/3]$, let $e_{i}={e\choose 2}\cup
e^{\prime}_{i}$ where $e^{\prime}_{i}$ is the copy of $e$ in $V_{i}$. Thus
$e_{i}$ has six vertices in $U$ and four vertices in $V_{i}$. Finally, let

$E(\mathcal{H})=\\{e_{i}:e\in\mathcal{T},i\in[2n/3]\\}.$

We write $\mathcal{K}$ for the set of all copies of $K_{4}$ in the complete
graph with vertex set $X\cup Y$ which have exactly one or three vertices in
$X$. Observe that there is a natural bijection between the edge set of
$\mathcal{H}$ and the set of tuples $(K,i)$ where $K\in\mathcal{K}$ and
$i\in[2n/3]$, namely, by mapping $e_{i}\in\mathcal{H}$ with
$e\in\mathcal{T},i\in[2n/3]$ to $(K,i)$ where $K$ is the complete graph on $e$
of size $4$. Moreover, there is also a bijection between $\mathcal{K}$ and all
$3$-edge stars in $B(X,Y)$ by simply deleting three edges from
$K\in\mathcal{K}$ or adding the three missing edges to a star. Hence we refer
to an edge $e$ in $\mathcal{H}$ also as a $K_{4}$ or star with color $i$ and
simply write $e=(K,i)$ for $K\in\mathcal{K}$ and $i\in[2n/3]$. Using this
bijection each matching in $\mathcal{H}$ corresponds to an edge-coloring of a
subgraph of $B(X,Y)$ with at most $2n/3$ colors satisfying (I). In the
following, we aim to find a particular matching which also satisfies
(II)–(IV).

We claim that $\mathcal{H}$ is essentially $d$-regular with $d=2n^{3}/3$.
Indeed, fix $u\in U$. If $u\in{X\choose 2}$, then in order to pick an edge
containing $u$, we pick a vertex $x\in X\setminus u$, a vertex $y\in Y$ and
$i\in[2n/3]$. This gives $(|X|-2)|Y|(2n/3)=d-O(n^{2})$ edges. The same
argument works for $u\in{Y\choose 2}$. Now suppose that $u=\\{x,y\\}$ with
$x\in X,y\in Y$. In this case we pick $Z\in\\{X,Y\\}$ and then distinct
$z,z^{\prime}\in Z\setminus u$ and $i\in[2n/3]$ to obtain $2{n-1\choose
2}(2n/3)=d-O(n^{2})$ edges. Thus in any case

$d-O(n^{2})\leq d_{\mathcal{H}}(u)\leq d.$

Now fix $v\in V_{i}$. Edges containing $v$ in $\mathcal{H}$ arise only from
copies of $K_{4}$ containing the copy of $v$ in $B(X,Y)$ and the number of
such copies is ${n-1\choose 2}n+{n\choose 3}=d-O(n^{2}).$ Therefore,

$d\left(1-\frac{1}{n^{1/2}}\right)\leq\delta(\mathcal{H})\leq\Delta(\mathcal{H})\leq
d.$

It is easy to prove that $\Delta_{2}(\mathcal{H})\leq n^{2}$.

We next define a 4-graph $\mathcal{C}$ which is a conflict system for
$\mathcal{H}$. As required, we set $V(\mathcal{C})=E(\mathcal{H})$. Edges of
$\mathcal{C}$ arise from $4$-cycles in $B(X,Y)$ comprising two monochromatic
matchings of size 2 (hence resulting in a $4$-cycle with exactly two colors).
Such 2-colored 4-cycles arise from four stars in $B(X,Y)$, two in one color
and two in another color, that form a (linear) 4-uniform 4-cycle. More
precisely, given four distinct vertices $x,x^{\prime}\in X$ and
$y,y^{\prime}\in Y$, two distinct colors $i,j\in[2n/3]$, and
$e=(K_{xy},i),e^{\prime}=(K_{x^{\prime}y^{\prime}},i),f=(K_{xy^{\prime}},j),f^{\prime}=(K_{x^{\prime}y},j)$
with $a,b\in V(K_{ab})$ for $a\in\\{x,x^{\prime}\\},b\in\\{y,y^{\prime}\\}$,
we have $\\{e,e^{\prime},f,f^{\prime}\\}\in E(\mathcal{C})$ whenever
$\\{e,e^{\prime},f,f^{\prime}\\}$ is a matching in $\mathcal{H}$.

We next claim that $\Delta(\mathcal{C})=O(d^{3})$. Indeed, given a vertex
$e_{i}=(K,i)\in V(\mathcal{C})$, all edges containing $e_{i}$ are of the form
$\\{(K,i),(K^{\prime},i),(K_{1},j),(K_{2},j)\\}$ for some
$K^{\prime},K_{1},K_{2}\in\mathcal{K}$ and $j\in[2n/3]\setminus\\{i\\}$. There
are $O(n)$ choices for $j$, $O(n^{4})$ choices for $K^{\prime}$, and
$O(n^{4})$ choices for $V(K_{1})\cup V(K_{2})$. Hence
$\Delta(\mathcal{C})=O(n^{9})=O(d^{3})$.

A similar calculation also shows that there are $O(n^{5})$ edges in
$\mathcal{C}$ containing any fixed $(K,i),(K^{\prime},i)\in V(\mathcal{C})$.
Similarly, if we fix $(K,i),(K_{1},j)$, there are $O(n^{3})$ choices for
$(K^{\prime},i)$ and then $O(n^{2})$ choices for $(K_{2},j)$. Consequently,
$\Delta_{2}(\mathcal{C})=O(n^{5})<d^{2-1/4}$ with room to spare. Given
$(K,i),(K^{\prime},i),(K_{1},j)$ as above leaves $O(n^{2})$ choices for
$(K_{2},j)$. Thus $\Delta_{3}(\mathcal{C})<d^{1-1/4}$ and $\mathcal{C}$ is a
$(d,O(1),\varepsilon)$-bounded conflict system for $\mathcal{H}$ for all
$\varepsilon\in(0,1/4)$.

We remark that one can now apply Theorem 2.1 to $\mathcal{H}$ to obtain an
almost perfect conflict-free matching $M$, and this translates to an edge-
coloring of a subgraph $G$ of most edges of $B(X,Y)$ with every $4$-cycle
receiving at least three colors (each color class is a star forest with stars
of three edges); in particular, Theorem 3.1 (I) and (II) hold. However, to
complete this to a coloring of all of $B(X,Y)$, we need to ensure that the
coloring of $G$ has further properties (properties (III) and (IV)). We achieve
this by considering carefully chosen test functions.

To this end, for each $v\in X\cup Y$, let $S_{v}\subset U$ be the set of edges
in $B(X,Y)$ incident to $v$. Let $w_{v}:E(\mathcal{H})\to[0,3]$ be the weight
function that assigns every edge of $\mathcal{H}$ the size of its intersection
with $S_{v}$. Note that $w_{v}(M)$ counts the number of edges in $S_{v}$ that
belong to a star in any collection of stars that stems from some matching $M$
in $\mathcal{H}$. Moreover, $w_{v}(\mathcal{H})=\sum_{e\in
S_{v}}d_{\mathcal{H}}(e)=nd-O(n^{3})$. Observe that (W2)–(W4) are trivially
satisfied, because $w_{v}$ is $1$-uniform. Hence $w_{v}$ is a
$(d,\varepsilon,\mathcal{C})$-trackable 1-uniform test function for all
$\varepsilon\in(0,1/4)$ and $v\in V(B(X,Y))$.

We could now apply Theorem 2.1 to also obtain (III). Indeed, for suitable
$\varepsilon$, and sufficiently large $n$, Theorem 2.1 yields a
$\mathcal{C}$-free matching $M\subset\mathcal{H}$ such that for each $v\in
X\cup Y$,

$\displaystyle
w_{v}(M)>(1-d^{-\varepsilon^{3}})d^{-1}w_{v}(\mathcal{H})>(1-n^{-\delta})n$

for some small enough $\delta>0$. Therefore, for every vertex $v\in X\cup Y$,
there are at most $n^{1-\delta}$ edges in $B(X,Y)$ incident to $v$ that do not
belong to a star selected by $M$.

Next we extend our selection of test functions such that Theorem 2.1 also
yields (IV). For each $(x,y)\in X\times Y$, we proceed as follows. For each
$j_{x},j_{y}\in\\{1,3\\}$, let

$\displaystyle\mathcal{P}_{j_{x},j_{y}}$
$\displaystyle=\\{\\{(K_{x},i),(K_{y},i)\\}\colon i\in[2n/3],V(K_{x})\cap
V(K_{y})=\emptyset,$ $\displaystyle x\in V(K_{x}),|V(K_{x})\cap X|=j_{x},y\in
V(K_{y}),|V(K_{y})\cap Y|=j_{y}\\}.$

Clearly,

$|\mathcal{P}_{j_{x},j_{y}}|=\frac{j_{x}n^{3}}{6}\cdot\frac{j_{y}n^{3}}{6}\cdot\frac{2n}{3}\pm
O(n^{6})=\frac{j_{x}j_{y}n^{7}}{54}\pm O(n^{6})>d^{2+1/4}.$

We define an indicator weight function $w_{x,y,j_{x},j_{y}}$ for the pairs in
$\mathcal{P}_{j_{x},j_{y}}$. Assume for now that these test functions are
$(d,\varepsilon,\mathcal{C})$-trackable for all $\varepsilon\in(0,1/4)$ (note
that each pair in $\mathcal{P}_{j_{x},j_{y}}$ corresponds to a matching of
size $2$ in $\mathcal{H}$). Adding all these weight functions (for all
$(x,y)\in X\times Y$ and $j_{x},j_{y}\in\\{1,3\\}$) to the set of weight
functions which we give to Theorem 2.1, we obtain a matching $M$ such that

(3) $\left|{M\choose
2}\cap\mathcal{P}_{j_{x},j_{y}}\right|=w_{x,y,j_{x},j_{y}}(M)\leq(1+d^{-\varepsilon^{3}})d^{-2}|\mathcal{P}_{j_{x},j_{y}}|\leq(1+n^{-2\delta})\frac{j_{x}j_{y}n}{24}$

for each $x,y,j_{x},j_{y}$.

Now we verify that $w_{x,y,j_{x},j_{y}}$ is indeed
$(d,\varepsilon,\mathcal{C})$-trackable. We already checked (W1). To see (W2),
we fix one $(K_{x},i)$ and observe that there are $O(n^{3})<n^{7}/d^{1+1/4}$
choices for $(K_{y},i)$ (and similarly when $x,y$ are swapped), which shows
(W2). To see (W3), fix $e=(K_{1},i),f=(K_{2},j)$ with
$w_{x,y,j_{x},j_{y}}(\\{e,f\\})>0$. Hence $i=j$ and, say,
$e=(K_{x},i),f=(K_{y},i)$ as in the definition of $\mathcal{P}_{j_{x},j_{y}}$.
To choose the three edges of $\mathcal{H}$ that form a conflict with both $e$
and $f$, we can choose at most six further vertices outside $V(K_{x})\cup
V(K_{y})$ and one color in $[2n/3]\setminus\\{i\\}$ resulting in
$O(n^{7})<d^{3-1/4}$ choices, which shows (W3). Property (W4) is vacuously
true.

Now we define a set of triples $\mathcal{T}_{j_{x},j_{y}}$ that extend the
pairs in $\mathcal{P}_{j_{x},j_{y}}$. Given
$\\{(K_{x},i),(K_{y},i)\\}\in\mathcal{P}_{j_{x},j_{y}}$, we add the triple
$\\{(K_{x},i),(K_{y},i),(K,j)\\}$ to $\mathcal{T}_{j_{x},j_{y}}$ whenever
$j\in[2n/3]\setminus\\{i\\}$ and $K$ contains exactly one vertex in
$V(K_{x})\setminus X$ and exactly one vertex in $V(K_{y})\setminus Y$.
Consequently, we have

$|\mathcal{T}_{j_{x},j_{y}}|=(4-j_{x})(4-j_{y})(d\pm
O(n^{2}))|\mathcal{P}_{j_{x},j_{y}}|$

and all triples in $\mathcal{T}_{j_{x},j_{y}}$ are matchings of size $3$ in
$\mathcal{H}$. In the same vein as above, we define an indicator weight
function $w_{x,y,j_{x},j_{y}}^{\prime}$ on the triples of $E(\mathcal{H})$.
Assume for now that these weight functions are
$(d,\varepsilon,\mathcal{C})$-trackable for all $\varepsilon\in(0,1/4)$.
Theorem 2.1 gives rise to a matching $M$ such that

(4) $\left|{M\choose
3}\cap\mathcal{T}_{j_{x},j_{y}}\right|\geq(1-n^{-2\delta})(4-j_{x})(4-j_{y})\cdot\frac{j_{x}j_{y}n}{24}$

for each $x,y,j_{x},j_{y}$.

The crucial observation is that each $x^{\prime}y^{\prime}$ from (IV) arises
from an edge of $\mathcal{H}$ in some triple of $\mathcal{T}_{j_{x},j_{y}}$
that contains some pair from $\mathcal{P}_{j_{x},j_{y}}$. Therefore the number
of $x^{\prime}y^{\prime}$ as in (IV) is at most

$\sum_{j_{x},j_{y}\in\\{1,3\\}}(4-j_{x})(4-j_{y})\left|{M\choose
2}\cap\mathcal{P}_{j_{x},j_{y}}\right|-\left|{M\choose
3}\cap\mathcal{T}_{j_{x},j_{y}}\right|.$

By (3) and (4), we see that Theorem 2.1 yields a matching M such that the
above quantity at most $n^{1-\delta}$, which proves (IV).

It remains to check that $w_{x,y,j_{x},j_{y}}^{\prime}$ is
$(d,\varepsilon,\mathcal{C})$-trackable for all $\varepsilon\in(0,1/4)$.
Observe that
$w_{x,y,j_{x},j_{y}}^{\prime}(\mathcal{H})=\Theta(n^{10})>d^{3+1/4}$ and hence
(W1) holds. To see (W2), we observe that
$w_{x,y,j_{x},j_{y}}^{\prime}(\\{E\in\binom{\mathcal{H}}{3}\colon E\supseteq
e\\})=O(n^{6})<w_{x,y,j_{x},j_{y}}^{\prime}(\mathcal{H})/d^{1+1/4}$ for all
$e\in\mathcal{H}$ and also
$w_{x,y,j_{x},j_{y}}^{\prime}(\\{E\in\binom{\mathcal{H}}{j}\colon E\supseteq
E^{\prime}\\})=O(n^{3})<w_{x,y,j_{x},j_{y}}^{\prime}(\mathcal{H})/d^{2+1/4}$
for all $E^{\prime}\in\binom{\mathcal{H}}{2}$. To see (W3), fix
$e=(K_{1},i),f=(K_{2},j)$ with $w_{x,y,j_{x},j_{y}}(E)>0$ for some
$\\{e,f\\}\subset E\in\binom{\mathcal{H}}{3}$. If $i=j$ as above for
$\mathcal{P}_{j_{x},j_{y}}$, then we again conclude as above the desired
bound. Hence assume that $i\neq j$. There at most $O(n^{8})<d^{3-1/4}$
conflicts containing $e$ which involve only edges of $\mathcal{H}$ with
colours $i,j$. This is clearly an upper bound for
$|(\mathcal{C}_{e})^{(3)}\cap(\mathcal{C}_{f})^{(3)}|$ and thus implies (W3).
Property (W4) is vacuously true, which completes the proof.

Next we finish the proof of (1). First we apply Theorem 3.1 (with $2\delta$
playing the role of $\delta$) and obtain a coloring as stated in Theorem 3.1.
In particular, $\Delta(L)\leq n^{1-2\delta}$ by (III). We now show how to
color the edges of $L$ with a set $P$ of $k=n^{1-\delta}$ new colors so that
no $4$-cycle in the final coloring has fewer than three colors on its edges.
We color each edge of $L$ with a color from $P$ with equal probability $1/k$,
independently of all other edges. We apply the symmetric form of the local
lemma to show that there is no 2-colored $4$-cycle and to this end we now
define three types of bad events.

For any pair $e,f$ of adjacent edges in $L$ and $i\in P$, we let $A_{e,f,i}$
be the event that both $e$ and $f$ receive color $i$. Clearly,
$\mathbb{P}[A_{e,f,i}]=k^{-2}$. For $4$-cycle $D$ in $L$, we define $B_{D}$ to
be the event that $D$ receives exactly two colors (and this coloring is
proper). Hence $\mathbb{P}[B_{D}]=(k(k-1))^{-1}\leq 2k^{-2}$. For a $4$-cycle
$D=xyx^{\prime}y^{\prime}$ in $K_{n,n}$ and $i\in P$, where
$xy,x^{\prime}y^{\prime}\in E(L)$ and $xy^{\prime},yx^{\prime}$ belong to two
stars colored alike by Theorem 3.1, we let $C_{D,i}$ be the event that both
$xy$, $x^{\prime}y^{\prime}$ receive color $i$. Clearly,
$\mathbb{P}[C_{D,i}]=k^{-2}$. Let $\mathcal{E}$ be the collection of all these
defined events.

We say two events as above are edge-disjoint if the edges in $L$ that can be
associated with them are distinct. Fix an event $E\in\mathcal{E}$ as above.
There are at most $8\Delta(L)\cdot k\leq 8k^{2}n^{-\delta}$ events $A_{e,f,i}$
that are not edge-disjoint from $E$; there are at most $4(\Delta(L))^{2}\leq
k^{2}n^{-\delta}$ events $B_{D}$ that are not edge-disjoint from $E$; and
there are at most $4n^{1-2\delta}k\leq 4k^{2}n^{-\delta}$ events $C_{D,i}$
that are not edge-disjoint from $E$ by (IV). Consequently, for any event
$E\in\mathcal{E}$, there is a set $\mathcal{E}_{E}$ of $13k^{2}n^{-\delta}$
events from $\mathcal{E}$ such that $E$ is independent of any collection of
events in $\mathcal{E}\setminus\mathcal{E}_{E}$. Since
$13k^{2}n^{-\delta}\cdot(2k^{-2})\leq 1/4$, by the local lemma, there is a
coloring of the edges of $L$ such that none of the events in $\mathcal{E}$
hold. Then given such a coloring, it is easy to see that every $4$-cycle in
$K_{n,n}$ receives at least three distinct colors.

##  4\. $r(K_{n},K_{4},5)$

In this section we prove (2). Recently, (2) was proven in [3] by analyzing an
elaborated extension of the triangle removal process. Here we encode (the
result of) this random process as a hypergraph matching problem (with
conflicts) in a similar fashion as in the previous section. We expect that
this methodology may be fruitful for many other applications as well.

It will be convenient to use the following concentration inequality due to
McDiarmid.

######  Theorem 4.1 (McDiarmid’s inequality, see [9]).

Suppose $X_{1},\dots,X_{m}$ are independent random variables. Suppose $X$ is a
real-valued random variable determined by $X_{1},\dots,X_{m}$ such that
changing the outcome of $X_{i}$ changes $X$ by at most $b_{i}$ for all
$i\in[m]$. Then, for all $t>0$, we have

$\mathbb{P}[|X-\mathbb{E}[X]|\geq t]\leq
2\exp\left({-\frac{2t^{2}}{\sum_{i\in[m]}b_{i}^{2}}}\right).$

We now state and prove the main technical statement which gives a partial
coloring of $K_{n}$.

######  Theorem 4.2.

There exists $\delta>0$ such that for all sufficiently large $n$ in terms of
$\delta$, there exists an edge-coloring of a subgraph $F\subset K_{n}$ with at
most $5n/6+n^{1-\delta}$ colors and the following properties:

  1. (I)

Every color class consists of vertex-disjoint edges and 2-edge paths.

  2. (II)

For all triangles $xyz$ in $F$ where $xy,yz$ receive the same color and $xz$
is colored $i$, the vertex $y$ is an isolated vertex and $xz$ forms a
component in color class $i$.

  3. (III)

Every $4$-cycle in $F$ receives at least three distinct colors.

  4. (IV)

The graph $L=K_{n}-E(F)$ has maximum degree at most $n^{1-\delta}$.

  5. (V)

For each $xy\in E(K_{n})$, the number of $x^{\prime}y^{\prime}\in E(L)$ with
$\\{x,y\\}\cap\\{x^{\prime},y^{\prime}\\}=\emptyset$ for which $xx^{\prime}$
and $yy^{\prime}$ receive the same color in $F$ is at most $n^{1-\delta}$.

###### Proof.

Let $\delta>0$ be sufficiently small and let $n$ be sufficiently large in
terms of $\delta$. Let $\rho=n^{-\delta}$ and $k=(1+\rho)5n/6$. Let $G=K_{n}$.
We first construct a random (vertex) set $V$ as follows. Let
$V^{\prime}=\bigcup_{i\in[k]}V_{i}^{\prime}$ where
$V_{1}^{\prime},\ldots,V_{k}^{\prime}$ are copies of $V(G)$. Delete each
vertex in $\bigcup_{i\in[k]}V_{i}^{\prime}$ independently with probability
$p=\rho/(1+\rho)$. Denote by $V_{i}$ the vertices in $V_{i}^{\prime}$ which
remain. Let $V=\bigcup_{i\in[k]}V_{i}$.

Next, we construct an $8$-graph $\mathcal{H}$ with vertex set $E(G)\cup V$ as
follows. For $i\in[k]$ and $v\in V(G)$, we denote by $v_{i}$ the copy of $v$
in $V_{i}$ (if it exists). For each triangle $uvw$ in $G$ and distinct
$i,j\in[k]$, we add the edge

$\displaystyle\\{uv,uw,vw,u_{i},v_{i},w_{i},v_{j},w_{j}\\}$

to $\mathcal{H}$ if $u_{i},v_{i},w_{i},v_{j},w_{j}\in V$ and $u_{j}\notin V$.

Next we consider triangles where one vertex has a label. Clearly, each
unlabelled triangle gives rise to three different such labelled triangles. Let
$\mathcal{K}$ be the set of all such labelled triangles that arise from
triangles in $G$. Observe that there is an injection from the edge set of
$\mathcal{H}$ to the set of tuples $(K,i,j)$ with $K\in\mathcal{K}$ and
distinct $i,j\in[k]$, where we think of color $i$ appearing on two edges in
$K$ and color $j$ appearing on the edge not incident to the labelled vertex of
$K$. Hence we refer to an edge $e$ in $\mathcal{H}$ also as a triangle (if the
colors and the label do not matter at that point) and simply write $e=(K,i,j)$
for $K\in\mathcal{K}$ and distinct $i,j\in[k]$.

Note that any matching $M\subset\mathcal{H}$ corresponds to a collection of
edge-disjoint triangles in $G$ where each triangle $uvw$ is of the form where
$vw$ is assigned color $j$ and $uv$ and $uw$ are both assigned color $i$.
Moreover, vertex $u$ is not incident to any edge in color $j$ in any other
triangle (due to the condition $u_{j}\not\in V$ above). This yields a
$k$-coloring of the edges of $G$ that lie within these triangles that
satisfies properties (I) and (II). Our goal is to find a particular $M$ such
that the corresponding edge-coloring of $G$ also satisfies (III)–(V). Property
(III) will follow by defining a particular conflict system $\mathcal{C}$ for
$\mathcal{H}$ and finding a $\mathcal{C}$-free matching $M$, and (IV) and (V)
will follow by considering certain trackable test functions.

Note that $\Delta_{2}(\mathcal{H})=O(n^{2})$ (independent of our random
choices). Next, we compute the expected degrees of the vertices in
$\mathcal{H}$. Note that $1-p=(1+\rho)^{-1}$. We obtain for $uv\in E(G)$

$\displaystyle\mathbb{E}[d_{\mathcal{H}}(uv)]$ $\displaystyle=(n-2)\cdot
k(k-1)\cdot 3\cdot(1-p)^{5}p$ $\displaystyle=\frac{5}{2}n^{2}k(1-p)^{4}p\pm
O(n^{2}).$

and for $u_{i}\in V_{i}^{\prime}$

$\displaystyle\mathbb{E}[d_{\mathcal{H}}(u_{i})\mid u_{i}\in V_{i}]$
$\displaystyle=\left(\binom{n-1}{2}+(n-1)(n-2)+(n-1)(n-2)\right)(k-1)(1-p)^{4}p$
$\displaystyle=\frac{5}{2}n^{2}k(1-p)^{4}p.$

We claim that by Theorem 4.1

$\displaystyle\frac{5}{2}n^{2}k(1-p)^{4}p-O(n^{8/3})\leq\delta(\mathcal{H})\leq\Delta(\mathcal{H})\leq\frac{5}{2}n^{2}k(1-p)^{4}p+O(n^{8/3}),$

holds with high probability. Indeed, fix some $uv\in E(G)$ and for $w\in
V^{\prime}$, define $b_{w}=n^{2}$ if $w$ is a copy of $u$ or $v$ and $b_{w}=n$
otherwise. Then $\sum_{w\in V^{\prime}}b_{w}^{2}=O(n^{5})$, which shows
concentration in an interval of length $O(n^{5/2})$ using Theorem 4.1.
Similarly, fix $u_{i}\in V_{i}^{\prime}$ and for $w\in
V^{\prime}\setminus\\{u_{i}\\}$, define $b_{w}=n^{2}$ if $w$ is a copy of $u$
or $w\in V_{i}^{\prime}$ and $b_{w}=n$ otherwise; again the same conclusion
holds.

Hence $\mathcal{H}$ is essentially $d$-regular for some
$d=\Theta(n^{3-\delta})$. In addition, it is easy to check using McDiarmid’s
inequality that given $u_{i},v_{i}\in V$, there are
$O(pn^{2})=O(n^{2-\delta})=O(d/n)$ edges containing both $u_{i},v_{i}$ with
high probability (indeed, for $w\in V^{\prime}\setminus\\{u_{i},v_{i}\\}$,
define $b_{w}=n$ if $w$ is a copy of $u$ or $v$ or $w\in V_{i}^{\prime}$ and
$b_{w}=1$ otherwise). We need that one further quantity is close to its
expected value, namely the size of $\mathcal{P}_{j_{x},j_{y}}$ which will be
defined later in the proof. For now we assume that that it is close to its
expected value with high probability. From now on, we fix one choice for
$\mathcal{H}$ that satisfies these properties and refer to this deterministic
$8$-graph again by $\mathcal{H}$. Moreover, we set $d=\Delta(\mathcal{H})$
(and hence $\mathcal{H}$ is essentially $d$-regular and
$d=\Theta(n^{3-\delta})$).

We next define a 4-graph $\mathcal{C}$ with vertex set $E(\mathcal{H})$ which
is a conflict system for $\mathcal{H}$. The edges of $\mathcal{C}$ arise from
$4$-cycles in $G$ comprising two monochromatic matchings of size 2 (hence
resulting in a $4$-cycle in $G$ with exactly two colors). We only consider
such 2-colored $4$-cycles that arise from four triangles in $G$, two of which
contain one color and the other two contain another color. More precisely,
given four distinct vertices $w,x,y,z\in V(G)$ and two distinct colors
$i,j\in[k]$ with $e_{uv}=(K_{uv},\alpha_{uv},\beta_{uv})$ for all
$uv\in\\{wx,xy,yz,wz\\}$, we have
$\\{e_{wx},e_{xy},e_{yz},e_{wz}\\}\in\mathcal{C}$ whenever

  * •

color $i$ appears on the edges $wx$ in $K_{wx}$ and $yz$ in $K_{yz}$,

  * •

color $j$ appears on the edges $xy$ in $K_{xy}$ and $wz$ in $K_{wz}$,

  * •

$e_{wx},e_{xy},e_{yz},e_{wz}$ form a matching in $\mathcal{H}$.

We emphasize that we do not stipulate whether color $i$ appears as a single
edge or a 2-edge path within the triangle $K_{wx}$ and similarly for the other
colors and triangles. We also do not require $K_{wx}$ and $K_{yz}$ (and
$K_{xy}$ and $K_{wz}$) to be vertex-disjoint. We note that a
$\mathcal{C}$-free matching $M$ in $\mathcal{H}$ gives rise to an edge-
coloring in which each $4$-cycle receives at least three colors. Indeed, by
the definition of $\mathcal{H}$, no color class has a 3-edge path and no two
monochromatic 2-edge paths share two vertices. The only other possibility for
a 2-colored $4$-cycle is if it comprises two monochromatic matchings and this
is precluded by the definition of $\mathcal{C}$.

It is easy to see that $\Delta(\mathcal{C})=O(d^{3})$. Indeed, fix some edge
in $\mathcal{H}$ that assigns color $i$ to $wx\in E(G)$. We have at most
$n^{2}$ choices to fix two further vertices $y,z$ in $G$. There are $O(d/n)$
choices for the edges that contain $y_{i},z_{i}$, at most $d$ choices for the
edges that contain $xy$ (say, $xy$ receives color $j$) and $O(d/n)$ choices
for the edges that contain $z_{j},w_{j}$. With almost the same arguments we
also obtain that $\Delta_{2}(\mathcal{C})=O(d^{2}/n)<d^{2-1/4}$ and
$\Delta_{3}(\mathcal{C})=O(d/n)<d^{1-1/4}$. Consequently, $\mathcal{C}$ is a
$(d,O(1),\varepsilon)$-bounded conflict system for $\mathcal{H}$ for all
$\varepsilon\in(0,1/4)$.

Next we define a set of $(d,\varepsilon,\mathcal{C})$-trackable test functions
that enables us to obtain properties (IV) and (V). For each $v\in V(G)$, let
$S_{v}\subset E(G)$ be the set of $n-1$ edges in $G$ incident to $v$. Let
$w_{v}:E(\mathcal{H})\to[0,2]$ be the weight function that assigns every edge
of $\mathcal{H}$ the size of its intersection with $S_{v}$. Note that
$w_{v}(M)$ counts that number of edges in $S_{v}$ that belong to a triangle in
any collection of triangles that stems from some matching $M$ in
$\mathcal{H}$. Moreover, $w_{v}(\mathcal{H})=\sum_{e\in
S_{v}}d_{\mathcal{H}}(e)=nd-O(n^{3})$. Observe that (W2)–(W4) are trivially
satisfied, because $w_{v}$ is $1$-uniform. Hence $w_{v}$ is a
$(d,\varepsilon,\mathcal{C})$-trackable 1-uniform test function for all
$\varepsilon\in(0,1/4)$ and $v\in V(G)$.

We could now apply Theorem 2.1 to also obtain (IV). Indeed, for suitable
$\varepsilon$, and sufficiently large $n$, Theorem 2.1 yields a
$\mathcal{C}$-free matching $M\subset\mathcal{H}$ such that for each $v\in
V(G)$,

$\displaystyle
w_{v}(M)>(1-d^{-\varepsilon^{3}})d^{-1}w_{v}(\mathcal{H})>(1-n^{-\delta})n$

holds where we choose $\delta>0$ small enough in terms of $\varepsilon$.
Therefore, for every vertex $v\in V(G)$, there are at most $n^{1-\delta}$
edges in $G$ incident to $v$ that do not belong to a triangle selected by $M$.
This proves (III) and (IV).

We turn to (V). In what follows, if $u\in V(G)$, then the notation $K_{u}$ for
a triangle $K_{u}$ implies that $K_{u}$ contains $u$. For all distinct $x,y\in
V(G)$ and $j_{x},j_{y}\in\\{1,2\\}$, we define

$\displaystyle\mathcal{P}_{j_{x},j_{y}}$
$\displaystyle=\\{\\{(K_{x},\alpha_{x},\beta_{x}),(K_{y},\alpha_{y},\beta_{y})\\}\colon(K_{x},\alpha_{x},\beta_{x}),(K_{y},\alpha_{y},\beta_{y})\in\mathcal{H}\text{
are disjoint},$ $\displaystyle\text{some color $i$ is incident to $z$ exactly
$j_{z}$ times in $K_{z}$ for each }z\in\\{x,y\\}\\}.$

It is again easy to exploit McDiarmid’s inequality to show that in the random
8-graph $\mathcal{H}$ we considered earlier with high probability for all
$x,y$ and $j_{x},j_{y}\in\\{1,2\\}$

$|\mathcal{P}_{j_{x},j_{y}}|=\frac{p^{2}(1-p)^{10}k^{3}n^{4}}{j_{x}j_{y}}\pm
O(n^{20/3})$

and we assume that we have chosen $\mathcal{H}$ such that this holds now
(indeed, for $w\in V^{\prime}$, define $b_{w}=10n^{6}$ if $w$ is a copy of $x$
or $y$ and $b_{w}=10n^{5}$ otherwise; hence $\sum_{w\in
V^{\prime}}b_{w}^{2}=O(n^{13})$). We define an indicator weight function
$w_{x,y,j_{x},j_{y}}$ for the pairs in $\mathcal{P}_{j_{x},j_{y}}$. Assume for
now that these test functions are $(d,\varepsilon,\mathcal{C})$-trackable for
all $\varepsilon\in(0,1/4)$. Adding all these weight functions to the set of
weight functions which we give to Theorem 2.1, we obtain a matching $M$ such
that

(5) $\left|{M\choose
2}\cap\mathcal{P}_{j_{x},j_{y}}\right|=w_{x,y,j_{x},j_{y}}(M)\leq(1+d^{-\varepsilon^{3}})d^{-2}|\mathcal{P}_{j_{x},j_{y}}|\leq(1+n^{-2\delta})\frac{4(1-p)^{2}k}{25j_{x}j_{y}}$

for each $x,y,j_{x},j_{y}$.

Now we verify that $w_{x,y,j_{x},j_{y}}$ is
$(d,\varepsilon,\mathcal{C})$-trackable. Property (W1) follows trivially by
our estimation of $|\mathcal{P}_{j_{x},j_{y}}|=\Theta(nd^{2})$ above. To see
(W2), fix some edge $e$ of $\mathcal{H}$; as we may assume that this edge is
contained in at least some pairs in $\mathcal{P}_{j_{x},j_{y}}$, by symmetry,
we may assume $e=(K,i,j)$ for some distinct $i,j\in[k]$. Then the weight of
all pairs containing $e$ is $O(d)<nd^{1-1/4}$ as any pair needs to contain at
least one vertex in $\\{y_{i},y_{j}\\}$. This proves (W2). To see (W3), we
argue as follows. We select two edges
$e=(K_{x},\alpha_{x},\beta_{x}),f=(K_{y},\alpha_{y},\beta_{y})$ of
$\mathcal{H}$ so that $\\{e,f\\}\in\mathcal{P}_{j_{x},j_{y}}$. We aim to find
an upper bound for the number of triples $g_{1},g_{2},g_{3}\in\mathcal{H}$
such that they form an element of $\mathcal{C}$ both with $e$ and with $f$.
First we only focus on $e$. In order to find an upper bound on the number of
such triples that form a conflict with $e$, we can choose five vertices in $G$
and four colors, resulting in an upper bound of $O(n^{9})$. If the triples
$g_{1},g_{2},g_{3}$ also form a conflict with $f$, we can select at most four
vertices outside $V(K_{x})\cup V(K_{y})$ and again at most four colors. Hence
there are at most $O(n^{8})<d^{3-1/4}$ such triples. This proves (W3). For
future reference, we note here that in order to prove (W3) it suffices to
assume that $K_{x},K_{y}$ share at most one vertex. Property (W4) is vacuously
true.

Next we define a set of triples $\mathcal{T}_{j_{x},j_{y}}$ that extend the
pairs in $\mathcal{P}_{j_{x},j_{y}}$. Suppose that we have a pair
$\\{(K_{x},\alpha_{x},\beta_{x}),(K_{y},\alpha_{y},\beta_{y})\\}\in\mathcal{P}_{j_{x},j_{y}}$.
We add the triple
$\\{(K_{x},\alpha_{x},\beta_{x}),(K_{y},\alpha_{y},\beta_{y}),(K,\gamma,\gamma^{\prime})\\}$
to $\mathcal{T}_{j_{x},j_{y}}$ whenever $K$ is edge-disjoint from
$K_{x},K_{y}$ and $K$ contains vertices $v_{x}\in V(K_{x}),v_{y}\in V(K_{y})$
and such that $xv_{x},yv_{y}$ have color $i$ in $K_{x},K_{y}$. The vertex
$v_{x}v_{y}$ in $\mathcal{H}$ has degree $d\pm O(n^{2})$ as $\mathcal{H}$ is
almost regular and as $\Delta_{2}(\mathcal{H})=O(d/n)$ almost all edges
containing $v_{x}v_{y}$ avoid
$(K_{x},\alpha_{x},\beta_{x}),(K_{y},\alpha_{y},\beta_{y})$. Consequently,

$|\mathcal{T}_{j_{x},j_{y}}|=j_{x}j_{y}(d\pm
O(n^{2}))|\mathcal{P}_{j_{x},j_{y}}|.$

In the same vein as above, we define an indicator weight function
$w_{x,y,j_{x},j_{y}}^{\prime}$ on the triples of $E(\mathcal{H})$. Assume for
now that these weight functions are $(d,\varepsilon,\mathcal{C})$-trackable
for all $\varepsilon\in(0,1/4)$. Theorem 2.1 gives rise to a matching $M$ such
that

(6) $\left|{M\choose
3}\cap\mathcal{T}_{j_{x},j_{y}}\right|=w^{\prime}_{x,y,j_{x},j_{y}}(M)\geq(1-d^{-\varepsilon^{3}})d^{-3}|\mathcal{T}_{j_{x},j_{y}}|\geq(1-n^{-2\delta})\frac{4(1-p)^{2}k}{25}$

for each $x,y,j_{x},j_{y}$.

The crucial observation is that each edge $x^{\prime}y^{\prime}$ from (V)
arises from an edge of $\mathcal{H}$ in some triple of
$\mathcal{T}_{j_{x},j_{y}}$ that contains a pair from
$\mathcal{P}_{j_{x},j_{y}}$. Therefore the number of $x^{\prime}y^{\prime}$ as
in (V) is at most

$\sum_{j_{x},j_{y}\in\\{1,3\\}}j_{x}j_{y}\left|{M\choose
2}\cap\mathcal{P}_{j_{x},j_{y}}\right|-\left|{M\choose
3}\cap\mathcal{T}_{j_{x},j_{y}}\right|.$

By (5) and (6) we see that this is at most $n^{1-\delta}$, which proves (V).

It remains to check that $w_{x,y,j_{x},j_{y}}^{\prime}$ is
$(d,\varepsilon,\mathcal{C})$-trackable for all $\varepsilon\in(0,1/4)$. To
see (W1), recall that
$|\mathcal{T}_{j_{x},j_{y}}|=\Theta(d|\mathcal{P}_{j_{x},j_{y}}|)=\Theta(nd^{3})$.
To see (W2), we follow the same argument as above for $w_{x,y,j_{x},j_{y}}$
and conclude that there is $O(d^{2})<nd^{2-1/4}$ weight on triples containing
a particular edge of $\mathcal{H}$ and $O(d)<nd^{1-1/4}$ weight on triples
containing two fixed edges. As we noted earlier when we checked (W3) for
$w_{x,y,j_{x},j_{y}}$, the number of conflicts that form a conflict with two
different edges which have at most one common vertex is at most $d^{3-1/4}$.
This applies to any pair of edges of $\mathcal{H}$ that belong to a triple
with positive weight given by $w_{x,y,j_{x},j_{y}}^{\prime}$. Hence (W3)
holds. Property (W4) is again vacuously true and this completes the proof of
Theorem 4.2.

To prove (2), we may proceed very similar as for the proof of (1) in the
previous section and also apply the local lemma with almost the same
collection of bad events. Here we deviate slightly from the approach in [3] as
we aim to use the most basic version of the local lemma which appears easier
to us.

First apply Theorem 4.2 (with $2\delta$ playing the role of $\delta$) and
obtain a coloring as stated in Theorem 4.2. In particular, $\Delta(L)\leq
n^{1-2\delta}$ by (IV). Color the edges of $L$ with a set $P$ of
$k=n^{1-\delta}$ new colors independently and uniformly at random.

For any pair $e,f$ of adjacent edges in $L$ and $i\in P$, we let $A_{e,f,i}$
be the event that both $e$ and $f$ receive color $i$. Clearly,
$\mathbb{P}[A_{e,f,i}]=k^{-2}$. For a $4$-cycle $D$ in $L$, we define $B_{D}$
to be the event that $D$ receives two colors (and this coloring is proper).
Hence $\mathbb{P}[B_{D}]=(k(k-1))^{-1}\leq 2k^{-2}$. For a $4$-cycle
$D=xyx^{\prime}y^{\prime}$ in $K_{n}$ and $i\in P$, where
$xy,x^{\prime}y^{\prime}\in E(L)$ and $xy^{\prime},yx^{\prime}$ belong to two
triangles colored alike by Theorem 3.1, we let $C_{D,i}$ be the event that
both $xy$, $x^{\prime}y^{\prime}$ receive color $i$. Clearly,
$\mathbb{P}[C_{D,i}]=k^{-2}$. Using essentially the same argument verbatim as
in the previous section, we can apply the local lemma to avoid all these
events simultaneously. This shows (2).

##  5\. Concluding remarks

As a further example of the versatility of our method, we can prove the
following nonbipartite version of (1):

(7) $r(K_{n},C_{4},3)=n/2+O(n^{1-\delta}).$

The lower bound is easy: every component of every color class in a
$(C_{4},3)$-coloring of $K_{n}$ is a star or a triangle, hence each color
class has at most $n$ edges. So the number of colors is at least ${n\choose
2}/n=(n-1)/2$. For the upper bound, our main tool is the following result that
is the nonbipartite analogue of Theorem 3.1.

######  Theorem 5.1.

There exists $\delta>0$ such that for all sufficiently large $n$ in terms of
$\delta$, there exists an edge-coloring of a subgraph of $G\subset K_{n}$ with
at most $n/2$ colors and the following properties:

  1. (I)

Every color class consists of vertex-disjoint triangles.

  2. (II)

Given any two colors $i,j$, the 3-graph with vertex set $V(G)$ where each edge
is formed by the vertex set of a triangle in color $i$ or $j$ has girth at
least 5.

  3. (III)

The graph $L=K_{n}-E(G)$ has maximum degree at most $n^{1-\delta}$.

  4. (IV)

For each $xy\in E(K_{n})$, the number of $x^{\prime}y^{\prime}\in E(L)$ with
$\\{x,y\\}\cap\\{x^{\prime},y^{\prime}\\}=\emptyset$ for which $xx^{\prime}$
and $yy^{\prime}$ receive the same color in $G$ is at most $n^{1-\delta}$.

The proof of Theorem 5.1 is very similar to the proof of Theorem 3.1. One can
then quickly use the local lemma to prove (7). It is an interesting question
to decide if one can improve the error term in this result. Roughly speaking,
this is equivalent to constructing an essentially resolvable Steiner triple
system where the union of any two color classes has girth 5. We conjecture
that such objects exist.

######  Conjecture 5.2.

$r(K_{n},C_{4},3)=\frac{n}{2}+O(1)$ and $r(K_{n},C_{4},3)=\frac{n-1}{2}$ for
infinitely many $n$.

In a similar vein, we pose another conjecture and problem.

######  Conjecture 5.3.

$r(K_{n,n},C_{4},3)=\frac{2n}{3}+O(1)$ and $r(K_{n,n},C_{4},3)=\frac{2n}{3}$
for infinitely many $n$.

######  Problem 5.4.

Is $r(K_{n},K_{4},5)=\frac{5n}{6}+O(1)?$

## References

  * [1] M. Axenovich, _A generalized Ramsey problem_ , Discrete Math. 222 (2000), 247–249.
  * [2] M. Axenovich, Z. Füredi, and D. Mubayi, _On generalized Ramsey theory: the bipartite case_ , J. Combin. Theory Ser. B 79 (2000), 66–86.
  * [3] P. Bennett, R. Cushman, A. Dudek, and P. Prałat, _The Erdős-Gyárfás function $f(n,4,5)={5n}/{6}+o(n)$ – so Gyárfás was right_, arXiv:2207.02920 (2022).
  * [4] D. Conlon, J. Fox, C. Lee, and B. Sudakov, _The Erdős-Gyárfás problem on generalized Ramsey numbers_ , Proc. Lond. Math. Soc. (3) 110 (2015), 1–18.
  * [5] P. Erdős, _Problems and results on finite and infinite graphs_ , Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp. 183–192. (loose errata).
  * [6] by same author, _Solved and unsolved problems in combinatorics and combinatorial number theory_ , Congr. Numer. 32 (1981), 49–62.
  * [7] P. Erdős and A. Gyárfás, _A variant of the classical Ramsey problem_ , Combinatorica 17 (1997), 459–467.
  * [8] S. Glock, F. Joos, J. Kim, M. Kühn, and L. Lichev, _Conflict-free hypergraph matchings_ , arXiv:2205.05564 (2022).
  * [9] C. McDiarmid, _On the method of bounded differences_ , Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, 1989, pp. 148–188.
  * [10] D. Mubayi, _Edge-coloring cliques with three colors on all $4$-cliques_, Combinatorica 18 (1998), 293–296.
  * [11] by same author, _An explicit construction for a Ramsey problem_ , Combinatorica 24 (2004), 313–324.


# META-CODE: Community Detection via Exploratory Learning in Topologically
Unknown Networks

Yu Hou  1234-5678-9012 Yonsei UniversityP.O. Box 1212SeoulRepublic of
Korea43017-6221<EMAIL_ADDRESS>,  Cong Tran  Posts and Telecommunications
Institute of TechnologyHanoiVietnam<EMAIL_ADDRESS>and  Won-Yong Shin
Yonsei UniversitySeoulRepublic of Korea<EMAIL_ADDRESS>
(2022)

###### Abstract.

The discovery of community structures in social networks has gained
considerable attention as a fundamental problem for various network analysis
tasks. However, due to privacy concerns or access restrictions, the network
structure is often unknown, thereby rendering established community detection
approaches ineffective without costly data acquisition. To tackle this
challenge, we present META-CODE, a novel end-to-end solution for detecting
overlapping communities in networks with unknown topology via exploratory
learning aided by easy-to-collect node metadata. Specifically, META-CODE
consists of three steps: 1) initial network inference, 2) node-level
community-affiliation embedding based on graph neural networks (GNNs) trained
by our new reconstruction loss, and 3) network exploration via community-
affiliation-based node queries, where Steps 2 and 3 are performed iteratively.
Experimental results demonstrate that META-CODE exhibits (a) superiority over
benchmark methods for overlapping community detection, (b) the effectiveness
of our training model, and (c) fast network exploration.

Community detection, exploratory learning, graph neural network (GNN), node
query, topologically unknown network

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
31st ACM International Conference on Information and Knowledge Management;
October 17–21, 2022; Atlanta, GA, USA††booktitle: Proceedings of the 31st ACM
International Conference on Information and Knowledge Management (CIKM ’22),
October 17–21, 2022, Atlanta, GA, USA††price: 15.00††isbn:
978-1-4503-9236-5/22/10††doi: 10.1145/3511808.3557639††ccs: Information
systems Social networks††ccs: Information systems Clustering

##  1\. Introduction

Community detection (Lancichinetti and Fortunato, 2009; Papadopoulos et al.,
2012; Xie et al., 2013; Cao et al., 2018; Kang et al., 2020; Ding et al.,
2021) is an indispensable task in network analyses to understand the
fundamental features of networks. Community detection algorithms should be
designed by taking into account the inherently overlapping nature since
community memberships in social networks are allowed to overlap as nodes
belong to multiple clusters at once (Shchur and Günnemann, 2019; Yang and
Leskovec, 2012, 2013; Yang et al., 2013; Ye et al., 2018; Tran et al., 2021a).

Nevertheless, the underlying true network is not initially known in various
domains of real-world network applications (Valente and Pumpuang, 2007). Thus,
existing downstream graph mining approaches are often ineffective without
retrieving relationships among nodes in a network, which is very labor-
intensive. To overcome this problem, exploratory influence maximization was
introduced along with a solution to perform information retrieval over unknown
networks by querying individual nodes to explore their neighborhoods, while
aiming at discovering the set of seed nodes leading to the maximum influence
spread (Wilder et al., 2018a, b; Kamarthi et al., 2020; Tran et al., 2021b).
However, the aforementioned studies focused on solving the problem of
influence maximization; the research related to community detection via
exploratory learning has been largely underexplored yet.

In social networks, node metadata can often be retrieved from a variety of
sources such as user-created content over given (social) networks (Leroy et
al., 2010) or even be inferred from users’ behavior (Kosinski et al., 2013),
thereby making them more readily available than the relationship between
individuals. In this paper, motivated by the fact that collecting such node
metadata is relatively easy-to-collect and cost-effective (Leroy et al.,
2010), we present META-CODE, a novel end-to-end framework for overlapping
community detection in networks with unknown topology via exploratory learning
that retrieves information from both node queries and node metadata. As the
first step of META-CODE, we infer the network structure by using both the
multi-assignment clustering (MAC) (Streich et al., 2009) and the community-
affiliation graph model (AGM) (Yang and Leskovec, 2012). Then, META-CODE
performs the following two steps iteratively: we generate node-level
community-affiliation embeddings based on graph neural networks (GNNs) trained
by our new loss function, which is established for preserving structural and
attribute information; and, for network exploration, we identify the next node
to query based on the discovered community affiliations.

Figure 1. The schematic overview of META-CODE when a query budget $T$ is given
by 3.

Through comprehensive experiments using real-world datasets, we demonstrate
that META-CODE consistently outperforms benchmark methods for overlapping
community detection. We also validate the effectiveness of both our network
inference module and our training model in GNNs. Moreover, the proposed node
query strategy in META-CODE shows faster network exploration than competing
sampling strategies, thus potentially leading to superior performance on
community detection.

##  2\. Methodology

###  2.1. Basic Settings and Problem Definition

Let us denote an underlying network as
$G=\left({\mathcal{V},\mathcal{E}}\right)$, which is initially unavailable,
where $\mathcal{V}$ is the set of $N$ nodes and $\mathcal{E}$ is the set of
edges. We assume $G$ to be an undirected unweighted attributed network having
collectible node metadata ${\bf\mathcal{X}}\in\mathbb{R}^{N\times D}$ of
binary-valued node features111Non binary-valued node features can be
transferred to binary values via one-hot encoding (Leskovec and Mcauley,
2012)., where $D$ is the dimension of each feature vector. We assume that
social networks follow the AGM (Yang and Leskovec, 2012), which can be
represented by a non-negative weight affiliation matrix ${\bf
F}\in\mathbb{R}^{N\times C}$ regarded as node-level community-affiliation
embeddings, where $C$ is the number of communities and ${\bf F}_{u}$ is the
affiliations of node $u$. Following the concept of active learning [2,12], we
are allowed to perform $T$ node queries given a query budget $T$ for network
exploration. When we query a single node, we are capable of discovering
neighbors of the queried node. The observable subgraph can then be expanded
accordingly, which essentially follows the same setting as prior work (Wilder
et al., 2018b, a; Mihara et al., 2015).

Problem definition: Given an initially unknown network
$G=\left({\mathcal{V},\mathcal{E}}\right)$, node metadata $\mathcal{X}$, and
$T$ node queries, we aim to assign nodes to $C$ overlapping communities.

###  2.2. Methodology

####  2.2.1. Overview of META-CODE

We describe our META-CODE method composed of three steps. The schematic
overview of META-CODE for $T=3$ is illustrated in Figure 1.

In Step 1, we discover the initial communities using the MAC (Streich et al.,
2009) that assigns nodes to multiple communities based on the node metadata
$\mathcal{X}$. We then infer the network, denoted as
$G_{0}=(\mathcal{V},\mathcal{E}_{0})$, from the initially discovered
communities using the AGM, where $\mathcal{E}_{0}$ is the set of initially
inferred edges. The function of initial network inference is denoted as
$G_{0}=f_{\text{init}}(\mathcal{X})$. In Step 2, we generate node-level
community-affiliation embeddings by designing a new GNN model. Specifically,
we build a GNN architecture and then train our GNN model by establishing our
own reconstruction loss in terms of preserving structural and attribute
information. In Step 3, we explore a subgraph by selecting an influential node
through the query process. To this end, we present our query node selection
strategy, which is inspired by the claim that querying nodes not only
belonging to more communities but also being distributed over diverse
communities is more influential in enabling the explored subgraph to grow
faster, thus resulting in potentially better performance on community
detection. This claim will be empirically validated in Section 3. In Sections
2.2.2 and 2.2.3, we elaborate on the embedding and network exploration steps,
respectively.

####  2.2.2. Community-Affiliation Embedding via GNNs

Let $G_{t}=(\mathcal{V},\mathcal{E}_{t})$ denote the discovered network whose
explored parts are expanded by replacing the connectivity information with
some amount of uncertainty for a queried node at the $t$-th query step
($t\in\\{1,\cdots,T\\}$) by connections between the queried node and its
neighbors, as depicted in Figure 1. Using the discovered network $G_{t}$ and
node metadata $\mathcal{X}$, we aim at designing our GNN model to generate
node-level embeddings that are represented as a non-negative weight
affiliation matrix ${\bf F}$:

(1) $\displaystyle{\bf F}:=GNN_{\theta}(G_{t},\mathcal{X}).$

Toward this goal, we would like to characterize the following two
relationships.

Structure-community relationship: Given the affiliation matrix ${\bf F}$, the
probability of having an edge between two nodes $u$ and $v$ can be modeled as
${1-\exp\left({-{\bf F}_{u}{\bf F}_{v}^{T}}\right)}$, which is built upon the
probabilistic generative model in (Yang and Leskovec, 2013). This implies
that, if a pair of nodes belongs to more communities in common, then the
probability that the node pair is connected becomes higher. In this context,
the negative log-likelihood (NLL) can be formulated as
$\mathcal{L}_{1}\left({\bf F}\right)=-\log P\left({G_{t}|{\bf F}}\right)$.

Metadata-community relationship: Intuitively, there exists a relationship
between node metadata and nodes’ affiliations. According to attribute modeling
in (Yang et al., 2013), the $d$-th attribute $\mathcal{X}_{ud}$ of node $u$
can be probabilistically modeled as

(2) $Q_{ud}=\frac{1}{{1+\exp\left({-\sum\nolimits_{c}{W_{dc}\cdot{\bf
F}_{uc}}}\right)}},$

where ${\bf F}_{uc}$ is the $c$-th entry in ${\bf F}_{u}$, and $W_{dc}$, the
$(d,c)$-th entry of weight matrix ${\bf W}\in\mathbb{R}^{D\times C}$,
indicates the relevance of community $c$ to the $d$-th node feature. Thus, the
NLL can be formulated as $\mathcal{L}_{2}\left({\bf F}\right)=-\log
P\left({\mathcal{X}|{\bf F},{\bf W}}\right)$.

Model training: Based on the two relationships above, we establish our
reconstruction loss as follows:

$\displaystyle\mathcal{L}\left({\bf F}\right)$
$\displaystyle=\mathcal{L}_{1}({\bf F})+\eta\mathcal{L}_{2}({\bf F})$
$\displaystyle=-\sum\limits_{\left({u,v}\right)\in\mathcal{E}_{t}}{\log\left({1-\exp\left({-{\bf
F}_{u}{\bf
F}_{v}^{T}}\right)}\right)+\sum\limits_{\left({u,v}\right)\notin\mathcal{E}_{t}}{{\bf
F}_{u}{\bf F}_{v}^{T}}}$ (3)
$\;\;\;\;\;\;\;-\eta\sum\limits_{u,d}{\left({\mathcal{X}_{ud}\log
Q_{ud}+\left({1-\mathcal{X}_{ud}}\right)\log\left({1-Q_{ud}}\right)}\right)},$

where $\eta\geq 0$ is the hyperparameter to balance between two terms. Note
that the first and second terms in Eq. (3) aim at reconstructing the network
structure and node metadata, respectively. We update the parameters $\theta$
of our GNN model in the sense of minimizing the loss function.

####  2.2.3. Network Exploration via Node Queries

As stated in Section 2.1, we discover neighbors of each queried node for
network exploration. Thus, we are interested in how to select the set of $T$
queried nodes. Although querying high-degree nodes is expected to make the
explored subgraph grow fastest, it may not be true as long as the community
detection task is concerned; moreover, such topology-aware query strategies
would not be feasible due to the neighbor unawareness of nodes (e.g., the
degree of each node) beforehand. In our study, the node query strategy is
built upon our claim that each queried node should not only belong to more
communities but also be distributed over diverse communities for faster
network exploration. In this context, we select the $t$-th node to query for
$t\in\\{1,\cdots,T\\}$ according to the following formulation:

(4)
$\hat{u}_{t}=\mathop{\arg\max}\limits_{u}\left({\left\|{F_{u}}\right\|_{1}+\lambda\left({1-\frac{1}{{\left|\mathcal{P}_{t}\right|}}\sum\limits_{v\in\mathcal{P}_{t}}{\text{sim}\left({F_{u},F_{v}}\right)}}\right)}\right),$

where $\left\|\cdot\right\|_{1}$ is $L_{1}$-norm of a vector,
$\mathcal{P}_{t}$ is the set of queried nodes up to the $t$-th iteration,
$\lambda\geq 0$ is the hyperparameter to balance between two terms, and
$\text{sim}(\cdot,\cdot)$ is the cosine similarity. Here, the second term in
Eq. (4) controls a node to be selected from communities different from those
of previous queried nodes.

##  3\. Experimental Evaluation

Datasets. We conduct our experiments on two Facebook datasets (Leskovec and
Mcauley, 2012), which are ego-networks collected from Facebook social
networks, and one large network dataset, Engineering, which is a co-authorship
network constructed from the Microsoft Academic Graph (Microsoft, 2015) where
communities correspond to research areas and node metadata are based on
keywords of the papers by each author222Although there are other Facebook and
large co-authorship networks, we have not further adopted them since they
exhibit similar tendencies to those of the above three datasets under
consideration..

Performance metrics. We quantify the degree of agreement between the ground
truth communities and the detected communities by adopting the normalized
mutual information (NMI) and the $F_{1}$ score. We note that the two metrics
are in a range of $[0,1]$, and higher values represent better performance.

Table 1. Performance comparison of META-CODE and six competing methods in terms of two metrics (average $\pm$ standard deviation) when different portions (%) of nodes are queried among $N$ nodes. Here, the best and second best performers are highlighted by bold and underline, respectively. | 10% queried nodes | 20% queried nodes | 30% queried nodes | 40% queried nodes
---|---|---|---|---
Dataset | Method | NMI |  $F_{1}$ score | NMI |  $F_{1}$ score | NMI |  $F_{1}$ score | NMI |  $F_{1}$ score
Facebook 0 | BIGCLAM+RS |  0.0058$\pm$0.0012 |  0.4048$\pm$0.0092 |  0.0189$\pm$0.0088 |  0.4253$\pm$0.0156 |  0.0252$\pm$0.0094 |  0.4535$\pm$0.0056 |  0.0348$\pm$0.0095 |  0.5168$\pm$0.0046
BIGCLAM+DFS |  0.0206$\pm$0.0092 |  0.4131$\pm$0.0108 |  0.0218$\pm$0.0047 |  0.4217$\pm$0.0426 |  0.0242$\pm$0.0095 |  0.4514$\pm$0.0147 |  0.0263$\pm$0.0112 |  0.4576$\pm$0.0652
vGraph+RS |  0.0079$\pm$0.0036 |  0.4102$\pm$0.0681 |  0.0195$\pm$0.0130 |  0.4989$\pm$0.0482 |  0.0217$\pm$0.0058 |  0.5026$\pm$0.0233 |  0.0410$\pm$0.0131 |  0.5429$\pm$0.0480
vGraph+DFS |  0.0180$\pm$0.0070 |  0.4826$\pm$0.0269 |  0.0301$\pm$0.0077 |  0.5029$\pm$0.0147 |  0.0321$\pm$0.0116 |  0.5066$\pm$0.0237 |  0.0335$\pm$0.0035 |  0.5173$\pm$0.0186
NOCD+RS |  0.0256$\pm$0.0312 |  0.5052$\pm$0.0431 |  0.0328$\pm$0.0301 |  0.5319$\pm$0.0216 |  0.0447$\pm$0.0234 |  0.5539$\pm$0.0676 |  0.0450$\pm$0.0157 |  0.6047$\pm$0.0395
NOCD+DFS |  0.0198$\pm$0.0057 |  0.5018$\pm$0.0504 |  0.0290$\pm$0.0029 |  0.5467$\pm$0.0128 |  0.0308$\pm$0.0216 |  0.5506$\pm$0.0294 |  0.0391$\pm$0.0243 |  0.5938$\pm$0.0551
META-CODE |  0.0298$\pm$0.0157 |  0.5119$\pm$0.0432 |  0.0357$\pm$0.0348 |  0.5596$\pm$0.0313 |  0.0463$\pm$0.0155 |  0.5623$\pm$0.0484 |  0.0556$\pm$0.0119 |  0.6102$\pm$0.0433
Facebook 348 | BIGCLAM+RS |  0.0263$\pm$0.0056 |  0.4349$\pm$0.0213 |  0.0539$\pm$0.0193 |  0.5025$\pm$0.0681 |  0.0703$\pm$0.0135 |  0.5896$\pm$0.0117 |  0.1083$\pm$0.0162 |  0.6503$\pm$0.1299
BIGCLAM+DFS |  0.0379$\pm$0.0057 |  0.4757$\pm$0.0115 |  0.0571$\pm$0.0211 |  0.5364$\pm$0.0351 |  0.0657$\pm$0.0197 |  0.5452$\pm$0.0733 |  0.0785$\pm$0.0139 |  0.5987$\pm$0.0448
vGraph+RS |  0.0559$\pm$0.0152 |  0.5700$\pm$0.0149 |  0.0914$\pm$0.0089 |  0.7046$\pm$0.0550 |  0.1332$\pm$0.0116 |  0.7233$\pm$0.0461 |  0.1573$\pm$0.0098 |  0.7708$\pm$0.0398
vGraph+DFS |  0.0601$\pm$0.0221 |  0.5526$\pm$0.0527 |  0.0943$\pm$0.0104 |  0.6614$\pm$0.0288 |  0.1030$\pm$0.0180 |  0.7079$\pm$0.0584 |  0.1272$\pm$0.0103 |  0.7297$\pm$0.0356
NOCD+RS |  0.0704$\pm$0.0191 |  0.6503$\pm$0.0960 |  0.1022$\pm$0.0089 |  0.6627$\pm$0.0836 |  0.1422$\pm$0.0111 |  0.7445$\pm$0.0168 |  0.1958$\pm$0.0191 |  0.7652$\pm$0.0399
NOCD+DFS |  0.0594$\pm$0.0111 |  0.5471$\pm$0.0283 |  0.0965$\pm$0.0213 |  0.6568$\pm$0.0616 |  0.1329$\pm$0.0218 |  0.7352$\pm$0.0713 |  0.1683$\pm$0.0247 |  0.7885$\pm$0.0542
META-CODE |  0.0791$\pm$0.0198 |  0.6842$\pm$0.0343 |  0.1132$\pm$0.0167 |  0.7221$\pm$0.0567 |  0.1578$\pm$0.0169 |  0.7923$\pm$0.0493 |  0.2003$\pm$0.0164 |  0.8218$\pm$0.0085
Engineering | BIGCLAM+RS |  0.0000$\pm$0.0000 |  0.1315$\pm$0.0386 |  0.0000$\pm$0.0000 |  0.2635$\pm$0.0207 |  0.0000$\pm$0.0000 |  0.3015$\pm$0.0531 |  0.0144$\pm$0.0133 |  0.4659$\pm$0.0317
BIGCLAM+DFS |  0.0029$\pm$0.0066 |  0.3460$\pm$0.0370 |  0.0194$\pm$0.0123 |  0.4530$\pm$0.0674 |  0.0406$\pm$0.0192 |  0.5160$\pm$0.0351 |  0.0590$\pm$0.0088 |  0.5980$\pm$0.0387
vGraph+RS |  0.0000$\pm$0.0000 |  0.1972$\pm$0.0282 |  0.0000$\pm$0.0000 |  0.3334$\pm$0.0080 |  0.0334$\pm$0.0042 |  0.4702$\pm$0.0188 |  0.0522$\pm$0.0116 |  0.5877$\pm$0.0913
vGraph+DFS |  0.0000$\pm$0.0000 |  0.3219$\pm$0.0084 |  0.0281$\pm$0.0114 |  0.4449$\pm$0.0642 |  0.0368$\pm$0.0054 |  0.4811$\pm$0.0820 |  0.0504$\pm$0.0194 |  0.5217$\pm$0.0137
NOCD+RS |  0.1262$\pm$0.0219 |  0.7081$\pm$0.0277 |  0.2148$\pm$0.0113 |  0.7924$\pm$0.0367 |  0.2875$\pm$0.0182 |  0.8387$\pm$0.0238 |  0.3128$\pm$0.0175 |  0.8529$\pm$0.0370
NOCD+DFS |  0.1466$\pm$0.0322 |  0.7542$\pm$0.0598 |  0.2046$\pm$0.0185 |  0.7760$\pm$0.0638 |  0.2702$\pm$0.0158 |  0.8261$\pm$0.0304 |  0.3038$\pm$0.0172 |  0.8427$\pm$0.0178
META-CODE |  0.1575$\pm$0.0371 |  0.7613$\pm$0.0193 |  0.2177$\pm$0.0207 |  0.8079$\pm$0.0193 |  0.2921$\pm$0.0169 |  0.8431$\pm$0.0177 |  0.3191$\pm$0.0302 |  0.8581$\pm$0.0175

Benchmark methods. We present three benchmark methods for overlapping
community detection: BIGCLAM (Yang and Leskovec, 2013) learns the affiliation
matrix using a block coordinate gradient ascent algorithm; vGraph (Sun et al.,
2019) jointly performs community detection and node representation learning
based on a generative model; and NOCD (Shchur and Günnemann, 2019) discovers
overlapping communities via GNNs using the network structure and node
metadata. Since the above benchmark methods were originally developed for
fully observable networks, we need to first infer the network structure. To
this end, we employ two sampling strategies for network exploration via node
queries: random sampling (RS) and depth-first search (DFS)333Although other
sophisticated sampling strategies such as biased random walks can also be
employed, they were not employed in our study since they reveal similar
tendencies to those of RS and DFS.. Similarly as in META-CODE, we iteratively
perform community detection alongside the explored network via sampling given
a budget of node queries. We implement all these benchmark methods through the
parameter settings mentioned in the original articles.

Experimental setup. In our experiments, we adopt GCN (Kipf and Welling, 2017)
with 2 layers as a popular GNN architecture to extract the community-
affiliation embeddings. We train our GNN model using Adam optimizer (Kingma
and Ba, 2015) with a learning rate of 0.001. All models are implemented via a
geometric learning library, named PyTorch Geometric (Fey and Lenssen, 2019).
We tune the hyperparameter $\eta$ within a designated range
$\eta\in[1.0,2.0]$, which leads to substantial gains over the case of $\eta=0$
corresponding to the GNN model trained in the sense of preserving the
structural information only. We also tune the hyperparameter $\lambda$ within
a designated range $\lambda\in[0.0,3.0]$.

Research questions. Our empirical study is designed to answer the following
three key research questions (RQs).

  * •

RQ1. How much does the META-CODE method improve the performance of community
detection over the benchmark methods?

  * •

RQ2. How effective is our initial network inference module for accurate
community detection?

  * •

RQ3. How effective is our node query strategy for fast network exploration?

(RQ1) Comparison with benchmark methods. The performance comparison between
our META-CODE method and three benchmark methods with two different sampling
strategies is comprehensively presented in Table 1 with respect to two
performance metrics using three real-world datasets when different portions of
nodes are queried among $N$ nodes. We observe the following: 1) META-CODE
consistently outperforms benchmark methods; 2) the performance improvement of
META-CODE over the second best performer is the largest when 40% nodes are
queried on Facebook 0—the maximum gain of $23.56\%$ is achieved in terms of
the NMI; and 3) the second best performer tends to be NOCD with RS in most
cases since NOCD also generates community-affiliation embeddings via GNNs,
which is more capable of precisely discovering communities.

Table 2. Performance comparison of META-CODE with two different initial network inference strategies in terms of the NMI when 10% of nodes are queried. Dataset |  META-CODE ($k$NN) |  META-CODE (MAC+AGM)
---|---|---
Facebook 0 |  0.0272$\pm$0.0194 |  0.0298$\pm$0.0157
Facebook 348 |  0.0772$\pm$0.0174 |  0.0791$\pm$0.0198
Engineering |  0.1431$\pm$0.0204 |  0.1575$\pm$0.0371

(RQ2) Effectiveness of initial network inference. We investigate the effect of
our initial network inference module based on the MAC and AGM on the
performance of META-CODE in comparison with the case of using a $k$-nearest
neighbor ($k$NN)-aided strategy. The performance comparison between two
different strategies is presented in Table 2 with respect to the NMI when 10%
of node are queried. Our observations include that 1) META-CODE (MAC+AGM) is
consistently superior to META-CODE ($k$NN) and 2) the maximum gain of 9.55% is
achieved on Facebook 0.

(RQ3) Growth of explored subgraphs. To empirically validate the effectiveness
of our node query strategy, we conduct experiments by plotting the number of
explored nodes (i.e., the size of explored subgraphs), denoted as
$N_{\text{ex}}$, versus a portion of queried nodes in Figure 2 in comparison
with two cases in which two sampling strategies (i.e., RS and DFS) are
employed for network exploration in META-CODE rather than Eq. (4). Our
findings are summarized as follows: 1) our query strategy based on the
discovered community affiliations is consistently beneficial over other
samplings with respect to the growth of explored subgraphs by exploring the
unknown parts of the underlying network faster; and 2) the growth rate of
$N_{\text{ex}}$ for RS is even higher than that for DFS since querying nodes
away from explored subgraphs via RS (instead of expanding the explored
subgraph via DFS) is more effective as the number of queried nodes increases.

Figure 2. The number of explored nodes, $N_{\text{ex}}$, according to
different portions (%) of queried nodes among $N$ nodes.

##  4\. Concluding Remarks

We introduced META-CODE, a novel end-to-end solution for overlapping community
detection in networks with unknown topology. Our META-CODE method was designed
in such a way of leveraging limited node queries and node metadata to
iteratively generate GNN-based embeddings and identify queried nodes after
initial network inference. Using three real-world datasets, we demonstrated
(a) the superiority of META-CODE over competitors with substantial gains up to
$23.56\%$ and (b) the effectiveness of key components in META-CODE such as the
initial network inference module and the network exploration module via node
queries.

###### Acknowledgements.

This work was supported by the National Research Foundation of Korea (NRF)
grant funded by the Korea government (MSIT) (No. 2021R1A2C3004345).

## References

  * (1)
  * Cao et al. (2018) Cheng Cao, Zhengzhang Chen, James Caverlee, Lu-An Tang, Chen Luo, and Zhichun Li. 2018\.  Behavior-based Community Detection: Application to Host Assessment in Enterprise Information Networks. In _Proc. 27th ACM Int. Conf. Inf. Knowl. Manage. (CIKM ’18)_ (Torino, Italy). 1977–1985.
  * Ding et al. (2021) Daizong Ding, Mi Zhang, Hanrui Wang, Xudong Pan, Min Yang, and Xiangnan He. 2021\.  A Deep Learning Framework for Self-evolving Hierarchical Community Detection. In _Proc. 30th ACM Int. Conf. Inf. Knowl. Manage. (CIKM ’21)_ (Virtual Event). 372–381.
  * Fey and Lenssen (2019) Matthias Fey and Jan Eric Lenssen. 2019.  Fast Graph Representation Learning with PyTorch Geometric. In _Proc. 7th ICLR Workshop on Representation Learning on Graphs and Manifolds_ (New Orleans, LA).
  * Kamarthi et al. (2020) Harshavardhan Kamarthi, Priyesh Vijayan, Bryan Wilder, Balaraman Ravindran, and Milind Tambe. 2020\.  Influence Maximization in Unknown Social Networks: Learn Policies for Effective Graph Sampling. In _Proc. 19th Int. Conf. Auton. Agents Multiagent Syst. (AAMAS ’20)_ (Auckland, New Zealand). 575–583.
  * Kang et al. (2020) Yoonsuk Kang, Jun Seok Lee, Won-Yong Shin, and Sang-Wook Kim. 2020.  Cr-graph: Community Reinforcement for Accurate Community Detection. In _Proc. 29th ACM Int. Conf. Inf. Knowl. Manage. (CIKM ’20)_ (Virtual Event). 2077–2080.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization. In _Proc. 3rd Int. Conf. Learn. Representations (ICLR ’15)_ (San Diego, CA).
  * Kipf and Welling (2017) Thomas N Kipf and Max Welling. 2017.  Semi-supervised Classification with Graph Convolutional Networks. In _Proc. 5th Int. Conf. Learn. Representations (ICLR ’17)_ (Toulon, France).
  * Kosinski et al. (2013) Michal Kosinski, David Stillwell, and Thore Graepel. 2013\.  Private Traits and Attributes are Predictable from Digital Records of Human Behavior.  _Proceedings of the National Academy of Sciences_ 110, 15 (2013), 5802–5805.
  * Lancichinetti and Fortunato (2009) Andrea Lancichinetti and Santo Fortunato. 2009.  Community Detection Algorithms: A Comparative Analysis.  _Physical Review E_ 80, 5 (2009), 056117.
  * Leroy et al. (2010) Vincent Leroy, B Barla Cambazoglu, and Francesco Bonchi. 2010\.  Cold Start Link Prediction. In _Proc. 16th Int. Conf. Knowl. Disc. Data Mining (KDD ’10)_ (Washington, DC). 393–402.
  * Leskovec and Mcauley (2012) Jure Leskovec and Julian Mcauley. 2012.  Learning to Discover Social Circles in Ego Networks. In _Proc. 26th Annu. Conf. Neural Inf. Process. Syst. (NeurIPS ’12)_ (Lake Tahoe, Nevada). 548–556.
  * Microsoft (2015) Microsoft. 2015\.  Announcing the Microsoft Academic Graph: Let the Research Begin!  https://www.microsoft.com/en-us/research/blog/announcing-the-microsoft-academic-graph-let-the-research-begin/.
  * Mihara et al. (2015) Shodai Mihara, Sho Tsugawa, and Hiroyuki Ohsaki. 2015\.  Influence Maximization Problem for Unknown Social Networks. In _Proc. 7th Int. Conf. Advances Social Netw. Anal. Mining (ASONAM ’15)_ (Paris, France). 1539–1546.
  * Papadopoulos et al. (2012) Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyridonos. 2012\.  Community Detection in Social Media.  _Data Mining and Knowledge Discovery_ 24, 3 (2012), 515–554.
  * Shchur and Günnemann (2019) Oleksandr Shchur and Stephan Günnemann. 2019.  Overlapping Community Detection with Graph Neural Networks. In _Proc. 25th ACM SIGKDD Workshop on Deep Learning on Graphs: Methods and Applications_ (Anchorage, AK).
  * Streich et al. (2009) Andreas P Streich, Mario Frank, David Basin, and Joachim M Buhmann. 2009.  Multi-assignment Clustering for Boolean Data. In _Proc. 26th Int. Conf. Mach. Learn. (ICML ’18)_ (Montreal, Quebec). 969–976.
  * Sun et al. (2019) Fan-Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wei Huang, and Jian Tang. 2019.  vGraph: A Generative Model for Joint Community Detection and Node Representation Learning. In _Proc. 33rd Annu. Conf. Neural Inf. Process. Syst. (NeurIPS ’19)_ (Vancouver, BC, Canada). 512–522.
  * Tran et al. (2021a) Cong Tran, Won-Yong Shin, and Andreas Spitz. 2021a.  Community Detection in Partially Observable Social Networks.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ 16, 2 (2021), 1–24.
  * Tran et al. (2021b) Cong Tran, Won-Yong Shin, and Andreas Spitz. 2021b.  IM-META: Influence Maximization Using Node Metadata in Networks with Unknown Topology.  _arXiv preprint arXiv:2106.02926_ (2021).
  * Valente and Pumpuang (2007) Thomas W Valente and Patchareeya Pumpuang. 2007.  Identifying Opinion Leaders to Promote Behavior Change.  _Health Education & Behavior_ 34, 6 (2007), 881–896.
  * Wilder et al. (2018a) Bryan Wilder, Nicole Immorlica, Eric Rice, and Milind Tambe. 2018a.  Maximizing Influence in an Unknown Social Network. In _Proc. 32nd Conf. Artif. Intell. (AAAI ’18)_ (New Orleans, LA), Vol. 32. 1–8.
  * Wilder et al. (2018b) Bryan Wilder, Laura Onasch-Vera, Juliana Hudson, Jose Luna, Nicole Wilson, Robin Petering, Darlene Woo, Milind Tambe, and Eric Rice. 2018b.  End-to-End Influence Maximization in the Field. In _Proc. 17th Int. Conf. Auton. Agents Multiagent Syst. (AAMAS ’18)_ (Stockholm, Sweden), Vol. 18. 1414–1422.
  * Xie et al. (2013) Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski. 2013\.  Overlapping Community Detection in Networks: The State-of-the-art and Comparative Study.  _ACM Computing Surveys (CSUR)_ 45, 4 (2013), 1–35.
  * Yang and Leskovec (2012) Jaewon Yang and Jure Leskovec. 2012.  Community-affiliation Graph Model for Overlapping Network Community Detection. In _Proc. 12th Int. Conf. Data Mining_ (Brussels, Belgium). IEEE, 1170–1175.
  * Yang and Leskovec (2013) Jaewon Yang and Jure Leskovec. 2013.  Overlapping Community Detection at Scale: a Nonnegative Matrix Factorization Approach. In _Proc. 6th ACM Int. Conf. Web Search Data Mining_ (Rome, Italy). 587–596.
  * Yang et al. (2013) Jaewon Yang, Julian McAuley, and Jure Leskovec. 2013\.  Community Detection in Networks with Node Attributes. In _Proc. 13th Int. Conf. Data Mining_ (Dallas, TX). IEEE, 1151–1156.
  * Ye et al. (2018) Fanghua Ye, Chuan Chen, and Zibin Zheng. 2018.  Deep Autoencoder-like Nonnegative Matrix Factorization for Community Detection. In _Proc. 27th ACM Int. Conf. Inf. Knowl. Manage. (CIKM ’18)_ (Torino, Italy). 1393–1402.