# Independence complexes of wedge of graphs

Navnath Daundkar  Department of Mathematics, Indian Institute of Technology
Bombay, India<EMAIL_ADDRESS>,  Saikat Panja  Department of Mathematics,
Harish Chandra Research Institute Prayagraj, India<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Sachchidanand Prasad  Department of Mathematics,
International Centre for Theoretical Sciences Bangalore, India
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this article, we introduce the notion of a wedge of graphs and provide
detailed computations for the independence complex of a wedge of path and
cycle graphs. In particular, we show that these complexes are either
contractible or wedges of spheres.

###### Key words and phrases:

Independence complex, Fold lemma, Wedge of graphs

###### 2020 Mathematics Subject Classification:

05C69, 55P15, 05C10

The first author is supported by IIT Bombay postdoctoral fellowship, the
second author is supported by HRI PDF-M fellowship and the third author is
supported by ICTS postdoctoral fellowship

##  1\. Introduction

A _graph_ is an order pair $G=(V,E)$, where $V$ is called the set of vertices
and $E$ is called the set of edges. The set $E$ is consist of $2$-element
subsets of $V$. A subject topological combinatorics is consist of the study of
homotopy invariants of certain cell complexes constructed using the graph to
obtain combinatorial information about the graph $G$. The first example of
this is the Lovász [9] celebrated proof of the Kneser conjecture. The
neighborhood complex $\mathcal{N}(G)$ of a graph $G$ is an abstract simplicial
complex whose simplices are subsets of the vertex set $V$ having common
neighbors. Lovász uses the connectivity of neighborhood complex
$\mathcal{N}(G)$ to compute a lower bound on the chromatic number of the
corresponding graph. Lovász stated the similar conjecture that the lower bound
on the chromatic number of a graph $G$ can be given in terms of the
connectivity of certain cell complexes associated with cycle graph and $G$.
These complexes are known as _hom complexes_. Babson and Kozlov [1] proved
Lovász conjecture, where they relate these hom complexes to _independence
complexes_.

An abstract simplcial complex consist of all independent subsets of $V$ is
called the _independence complex_ of $G$. It is denoted by $\mathcal{I}(G)$.
In the last two decades, the general problem of determining all the possible
homotopy type of independence complexes for various classes of graphs has
received considerable attention. For example, Kozlov [8] determined the
homotopy type of independence complexes for path and cycle graphs, Kawamura
[7, 6] for chordal graphs and forests, Bousquet-Mélou, Mireille and Linusson,
Svante and Nevo, Eran [2] for square-grid graphs, Engström [4] investigated
this problem for claw-free graphs, and Raun [3] for stable Kneser graphs etc.

The purpose of this paper is to introduce the notion of a wedge of graphs and
compute the all possible homotopy type of independence complexes of wedges of
some classes of graphs. In particular, we consider the class of wedges of path
graphs and cycle graphs. We also describe the relationships between
combinatorial and topological invariants associated with the wedge of graphs
with the corresponding combinatorial and topological invariants of the
components. We hope these computations will be helpful in other parts of
mathematics.

The paper is organized as follows: We begin Section 2 by defining some
combinatorial and topological objects associated with a graph. Then we
introduce the notion of a wedge of graphs. We end this section by recalling
some results about the homotopy type of independence complexes of path graphs
and cycle graphs.

Finally in Section 3, we prove the main results of this paper. Here, we
compute all possible homotopy types of the wedge of finitely many path graphs
and wedge of finitely many different cycle graphs. Next, we consider the wedge
of cycle and path graphs with respect to different base points and comupute
all possible homotopy types of corresponding independence complexes.

##  2\. Preliminaries

In this section, we will define the main object of our study. A couple of
examples will follow this. Also, we will mention the _fold lemma_ , which will
be a main ingredient to some of the proofs. Furthermore, we will mention some
of the previously proven results, which will be used to prove our main
theorems.

######  Definition 2.1.

An abstract simplicial complex $K$ is a collection of subsets of
$\\{v_{1},\dots,v_{n}\\}$, such that

  1. (1)

$\\{v_{i}\\}\in K$ for all $1\leq i\leq n$,

  2. (2)

if $\sigma\in K$ and $\tau\subseteq\sigma$, then $\tau\in K$.

The elements of $K$ are called faces. The _dimension_ of a face $\sigma$ is
defined as $|\sigma|-1$. In this paper, by simplicial complex we mean a
geometric realization of an abstract simplicial complex. Without loss of
generality we use simplicial complex for an abstract simplicial complex.

Now we define an important simplicial complex associated with a graph.

######  Definition 2.2 (Independence complex).

For a finite simple graph $G$, with the vertex set $V$, the independence
complex $\mathcal{I}(G)$ is the simplicial complex consisting of all
independent (i.e. no two vertices are adjacent) subsets of $V$ as its
simplices.

The independence complex of a graph $G$ is denoted by $\mathcal{I}(G)$.

######  Example 2.3.

We now see some examples of the independence complex of graphs.

  1. (1)

Let $P_{3}$ be a path graph on theree vertices $\\{1,2,3\\}$. Then

$\mathcal{I}(P_{3})=\bigg{\\{}\\{1\\},\\{2\\},\\{3\\},\\{1,3\\}\bigg{\\}}.$

Hence the independence complex is homotopy equivalent to $\mathbb{S}^{0}$,
which will be written as $\mathcal{I}(P_{3})\cong\mathbb{S}^{0}$ (see Figure
1).

Figure 1. Path graph $P_{3}$ and $\mathcal{I}(P_{3})$.

  2. (2)

Let $C_{4}$ the cycle graph on $4$ vertices $\\{1,2,3,4\\}$. Then the
independence complex is

$\mathcal{I}(C_{4})=\bigg{\\{}\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{1,3\\},\\{2,4\\}\bigg{\\}}.$

Hence we get that $\mathcal{I}(C_{4})\cong\mathbb{S}^{0}$ (see Figure 2).

Figure 2. Cycle graph $C_{4}$ and $\mathcal{I}(C_{4})$.

A _subcomlex_ of a simplicial complex is a simplicial complex whose faces are
contained in $K$. There are two important subcomplexes associated with any
simplicial complex.

######  Definition 2.4.

Let $K$ be a (abstract) simplicial complex. The link of a vertex $v\in K$ is
defined as

$\mathrm{lk}(v,K):=\\{\sigma\in K\mid v\notin\sigma\text{ and
}\sigma\cup{v}\in K\\}.$

######  Definition 2.5.

Let $K$ be a (abstract) simplicial complex. The deletion of a vertex $v\in K$
is defined as

$\mathrm{del}(v,K):=\\{\sigma\in K\mid v\notin\sigma\\}.$

Observe that for any vertex in $K$, the subcomplex $\mathrm{lk}(v,K)$ is a
subcomplex of $\mathrm{del}(v,K)$. The following is an important result which
describes the homotopy type of a simplicial complex in terms of the link and
deletion.

######  Lemma 2.6 ([5, Lemma 2]).

Let $K$ be a simplicial complex and $v\in K$ be a vertex such that
$\mathrm{lk}(v,K)$ is contractible in $\mathrm{del}(v,K)$. Then
$K\simeq\mathrm{del}(v,K)\vee\sum\mathrm{lk}(v,K)$.

Now we define the central object of study in this paper. This will be followed
by a few examples. Note that the definition depends on the choice of the so-
called ‘wedge point’.

######  Definition 2.7 (Wedge of graphs).

Given a finite family of graphs $G_{i}=(V_{i},E_{i})$, and $a_{i}\in V_{i}$
for all $i$, an _wedge of graphs_ is defined to be a graph $G=(V,E)$ such that

$\displaystyle V$
$\displaystyle=\left(\bigcup_{i}V_{i}\setminus\\{a_{i}\\}\right)\cup\\{a\\},$
$\displaystyle E$ $\displaystyle=\left(\bigcup_{i}E_{i}\setminus\\{e_{j}\in
E_{i}|a_{i}\in\partial(e_{j})\\}\right)\cup\left\\{ab_{k}|a_{i}b_{k}\in
E_{i}\right\\}.$

The common point $a$ will be called _wedge point_.

######  Remark 2.8.

Let $\chi(G)$ be the chromatic number of a graph. Then we can observe that

$\chi(G_{1}\vee G_{2})=\text{max}\\{\chi(G_{1}),\chi(G_{2})\\}.$

######  Example 2.9.

Consider two path graphs $P_{3}$ and $P_{4}$ on $3,4$ vertices respectively.
Then choosing different wedge points, we can obtain different wedge graphs. We
describe some of them here (see Figure 3).

Figure 3. Different wedges graphs of $P_{3}$ and $P_{4}$

######  Remark 2.10.

Note that if we vary the wedge points, the obtained wedge graphs need not be
isomorphic. Furthermore, they do not have a homotopic independence complex as
well. Consider the first and the last wedge graph of $P_{3}$ and $P_{4}$
described in Figure 3. Let us denote them by $G$ and $H$, respectively. Then
one can see that $G$ and $H$ are not isomorphic. Moreover,
$\mathcal{I}(G)\simeq*$ and $\mathcal{I}(H)\simeq S^{1}$.

Note that we have introduced the main two terms of the title, we mention one
of the key ingredients for the proof of our theorems.

######  Theorem 2.11 (Fold lemma).

[4, Lemma 3.4] Let $G$ be a graph, and $v\neq w$ vertices of $G$. If
$N(v)\subseteq N(w)$ then the inclusion $\mathcal{I}(G\setminus
w)\hookrightarrow\mathcal{I}(G)$ is a homotopy equivalence.

We will end this section by mentioning two important results, due to Kozlov.
This will be required in the proof of our theorem, as we are going to consider
a few classes of wedges of these graphs.

######  Theorem 2.12 ([8, Proposition 4.6]).

Let $P_{m}$ be the path graph on $m$ vertices. Then

$\mathcal{I}(P_{m})\simeq\begin{cases}\mathbb{S}^{k-1},&\text{ if }m=3k\\\
\text{pt},&\text{ if }m=3k+1\\\ \mathbb{S}^{k},&\text{ if }m=3k+2.\end{cases}$
(1)

######  Theorem 2.13 ([8, Proposition 5.2]).

Let $C_{n}$ be the cycle graph on $n$ vertices. Then

$\mathcal{I}(C_{n})\simeq\begin{cases}\mathbb{S}^{k-1}\vee\mathbb{S}^{k-1},&\text{
if }n=3k\\\ \mathbb{S}^{k-1},&\text{ if }n=3k+1\\\ \mathbb{S}^{k},&\text{ if
}n=3k+2.\end{cases}$ (2)

##  3\. Main results

We begin this section by proving a sufficient condition for the link of a
vertex to be contractible inside deletion. This is crucial in using the Lemma
2.6. Then we compute the homotopy type of wedge of path graphs and a wedge of
cycle graphs.

######  Lemma 3.1.

Let $G$ be a graph, and $v\in\mathcal{I}(G)$ be a vertex of $G$. Let
$\sigma\in\textup{del}{\left(v\right)}$ be a maximal simplex such that
$\sigma\notin\textup{lk}{\left(v,\mathcal{I}(G)\right)}$ and
$\textup{del}{\left(v,\mathcal{I}(G)\right)}\setminus\\{\sigma\\}$ is
contractible. Then

$\mathcal{I}(G)\simeq\textup{del}{\left(v,\mathcal{I}(G)\right)}\vee\Sigma\left(\textup{lk}{\left(v,\mathcal{I}(G)\right)}\right).$

###### Proof.

Since
$\sigma\notin\textup{lk}{\left(v\right)},~{}\textup{lk}{\left(v\right)}\subseteq\textup{del}{\left(v\right)}\setminus\\{\sigma\\}$,
and $\textup{del}{\left(v\right)}\setminus\\{\sigma\\}$ is contractible hence
we have $\textup{lk}{\left(v\right)}$ is contractible in
$\textup{del}{\left(v\right)}$. Then the result follows from Lemma 2.6. ∎

We start with the case when the wedge is taken to be of two path graphs. We
give a complete description of all the cases. In the later part of the
section, this will be generalized in the case of a wedge of finitely many path
graphs, using the concept of the terminal wedge.

######  Theorem 3.2.

Let $P_{l}$ be the path graph on $l$ vertices. Then

$\mathcal{I}\left(P_{m}\underset{a}{\vee}P_{n}\right)$ (3)

is either a point or a sphere.

###### Proof.

If the wedge point is the terminal point for both of the graphs, then the
wedge graph is $P_{m+n-1}$ hence the independence complex can be found using
Theorem 2.12. Now suppose that $a=a_{m}=b_{l},~{}m\geq 4$. Then Using Theorem
2.11 (with $v=a_{1}$ and $w=a_{3}$), we have that

$\displaystyle\mathcal{I}(P_{m}\underset{a}{\vee}P_{n})\simeq\mathbb{S}^{0}*\mathcal{I}(P_{m-3}\underset{a}{\vee}P_{n}).$

Thus we only need to compute the independence complexes for the cases $m=1,2$
and $3$ (Referring to the diagram Figure 4, we assume $n=l+k$).

$a_{1}$
---
$a_{2}$
---
$a_{t-1}$
---
$a$
---
$a_{t+1}$
---
$a_{m}$
---
$b_{1}$
---
$b_{2}$
---
$b_{3}$
---
$b_{l-1}$
---
$b_{l+1}$
---
$b_{l+2}$
---
$b_{n}$
---
Figure 4. Wedge of path graphs.

### Case 1 $m=1$

In this case the wedge is same as $P_{n}$.

### Case 2 $m=2$

Take $v=a_{1}$ and $w=b_{l-1}$. Then using Theorem 2.11

$\mathcal{I}(P_{2}\underset{a}{\vee}P_{n})\simeq\mathcal{I}(P_{l-2})*\mathcal{I}(P_{n-l+2}).$

### Case 3 $m=3$

Take $v=a_{1}$ and $w=a$. Then using Theorem 2.11,

$\mathcal{I}(P_{3}\underset{a}{\vee}P_{n})\simeq\mathbb{S}^{0}*\mathcal{I}(P_{l-1})*\mathcal{I}(P_{n-l}).$

Now, the result follows from Eq. 1. ∎ The case of a wedge of the cycle graphs
is not straightforward and hence we need to do a more careful analysis. This
is an almost replica of Kozlov’s work. But here we have more than one cycle,
so we need to consider the maximal simplex appropriately inside the deletion
which doesn’t belong to the link. Here is the statement of the main result.

######  Lemma 3.3.

Let $C_{m}\underset{a}{\vee}C_{n}$ be the wedge of cycle graphs and
$G_{m,n}=\mathcal{I}\left(C_{m}\underset{a}{\vee}C_{n}\right)$. Then

$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n})\right)}\vee\sum\textup{lk}{\left(a,G_{m,n}\right)}.$

###### Proof.

We denote $\mathcal{I}\left(C_{m}\underset{a}{\vee}C_{n}\right)$ by $G_{m,n}$.
We show that $\textup{lk}{\left(a,G_{m,n}\right)}$ is contractible in
$\textup{del}{\left(a,G_{m,n}\right)}$. Then the result follows from Lemma
2.6. Observe that, in general we have

$\textup{lk}{\left(a,G_{m,n}\right)}\simeq\mathcal{I}(P_{m-2})*\mathcal{I}(P_{n-2})~{}~{}\text{
and
}~{}~{}\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathcal{I}(P_{m-1})*\mathcal{I}(P_{n-1}).$

We consider the following cases:

Case 1 _ $n=3k$ or $m=3k^{\prime}$._

In this case, either $\mathcal{I}(P_{m-2})\sim\mathcal{I}(P_{3(k-1)+1})$ or
$\mathcal{I}(P_{n-2})\simeq\mathcal{I}(P_{3(k^{\prime}-1)+1})$. From Theorem
2.12, we get that either $\mathcal{I}(P_{m-2})$ or $\mathcal{I}(P_{n-2})$ is
contractible. Therefore, $\textup{lk}{\left(a,G_{m,n}\right)}$ is
contractible. This, from Lemma 2.6 result follows.

Case 2 _ $n=3k+1$ or $m=3k^{\prime}+1$._

Now consider the maximal simplex

$\sigma=\\{a_{1},a_{3},\dots,a_{3k-3},a_{3k-1}\\}\cup\\{b_{1},b_{3},\dots,b_{3k^{\prime}-3},b_{3k^{\prime}-1}\\}.$

Then
$\sigma\in\textup{del}{\left(a,G_{m,n}\right)}\setminus\textup{lk}{\left(a,G_{m,n}\right)}$.
We also have
$\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathcal{I}(P_{3k})*\mathcal{I}(P_{3k^{\prime}})\simeq\mathbb{S}^{k+k^{\prime}+1}$
using Theorem 2.12. Therefore,
$\textup{lk}{\left(a,G_{m,n}\right)}\setminus{\sigma}$ is contractible. Now
the result follows from Lemma 3.1.

Case 2 _ $n=3k+1$ and $m=3k^{\prime}+2$._

In this case, $\textup{del}{\left(a,G_{m,n}\right)}$ is contractible.
Therefore, the result follows from Lemma 2.6.

In the remaining cases

Case 3 _ $n=3k+2$ and $m=3k^{\prime}+1$_ and

Case 4 _ $n=3k+2$ and $m=3k^{\prime}+2$_ we get that
$\textup{del}{\left(a,G_{m,n}\right)}$ is contractible. Therefore, the result
follows from Lemma 2.6. Finally, in any case we have
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n})\right)}\vee\Sigma\textup{lk}{\left(a,G_{m,n}\right)}$.
∎

Now we consider the general case, where we have a wedge of $k$-many cycle
graphs, with the wedge point to be $a$. Consider the cycle graphs $C_{m_{i}}$
with vertices $\\{a_{1}^{i},a_{2}^{i},\ldots,a_{m_{i}}^{i}\\}$. Let
$G=\vee_{i=1}^{k}C_{m_{i}}$. Then observe that

$\textup{lk}{\left(a,\mathcal{I}(\bigvee_{i=1}^{k}C_{m_{i}})\right)}\simeq*_{i=1}^{k}\mathcal{I}(P_{m_{i}-2})~{}~{}\text{
and
}~{}~{}\textup{del}{\left(v,\mathcal{I}(\bigvee_{i=1}^{k}C_{m_{i}})\right)}\simeq*_{i=1}^{k}\mathcal{I}(P_{m_{i}-1}).$

Now one can see that if one of the $m_{i}$ is of the form $3k$ or $3k+2$, then
either $\textup{lk}{\left(a,\right)}$ or $\textup{del}{\left(a,\right)}$ is
contractible. Now if all $m_{i}$’s are of the form $3l_{i}+1$, then consider
the maximal simplex

$\sigma=\\{a^{1}_{1},a^{1}_{3},\dots,a^{1}_{3k-3},a^{1}_{3l_{1}-1}\\}\cup\dots\cup\\{a^{k}_{1},a^{k}_{3},\dots,a^{k}_{3k^{\prime}-3},a^{k}_{3l_{k}-1}\\}.$

Note that
$\sigma\in\textup{del}{\left(a,G_{m_{1},\dots,m_{k}}\right)}\setminus\textup{lk}{\left(a,G_{m_{1},\dots,m_{k}}\right)}$.
Observe that
$\textup{del}{\left(a,G_{m_{1},\dots,m_{k}}\right)}\simeq\mathbb{S}^{\Sigma_{i}^{k}l_{i}-1}$.
Therefore,
$\textup{del}{\left(a,G_{m_{1},\dots,m_{k}}\right)}\setminus\\{\sigma\\}$ is
contractible. Therefore, using Lemma 3.1 we have the following.

######  Lemma 3.4.

Let $G=\vee_{i=1}^{k}C_{m_{i}}$ be the wedge of $k$-many cycle graphs and
$G_{m_{1},\dots,m_{k}}$ be its independence complex. Then
$G_{m_{1},\dots,m_{k}}\simeq\textup{del}{\left(a,G_{m_{1},\dots,m_{k}}\right)}\vee\Sigma\textup{lk}{\left(a,G_{m_{1},\dots,m_{k}}\right)}$.

We are now ready to compute the homotopy type of the independence complex of a
wedge of cycle graphs. Although this will be further generalized in the later
part, we present the complete computation to ease the reader’s mind.

######  Theorem 3.5.

Let $C_{m}\underset{a}{\vee}C_{n}$ be the wedge of cycle graphs and $G_{m,n}$
be the independence complex of $C_{m}\underset{a}{\vee}C_{n}$. Then $G_{m,n}$
is contractible or homotopy equivalent to wedge of spheres.

###### Proof.

We consider the following cases:

Case 1 _either $n=3k$ or $m=3k^{\prime}$_

In this case $\textup{lk}{\left(a,G_{m,n}\right)}$ is contractible as we saw
in the first case of Lemma 3.3. Therefore, by Lemma 3.3, we have
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathcal{I}(P_{m-1})*\mathcal{I}(P_{n-1})$.
Now we have following subcases using Theorem 2.12:

  1. (1)

_If $m=3k$ and $n=3k$_. In this case,
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathbb{S}^{k-1}*\mathbb{S}^{k^{\prime}-1}=\mathbb{S}^{k+k^{\prime}-1}$.

  2. (2)

_If $m=3k$ and $n=3k^{\prime}+1$._ In this case,
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathbb{S}^{k-1}*\mathbb{S}^{k^{\prime}}=\mathbb{S}^{k+k^{\prime}}$.

  3. (3)

_If $m=3k$ and $n=3k^{\prime}+2$._ In this case,
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathbb{S}^{k-1}*\\{pt\\}=\\{pt\\}$.

  4. (4)

_If $m=3k+1$ and $n=3k^{\prime}$._ In this case,
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathbb{S}^{k}*\mathbb{S}^{k^{\prime}-1}=\mathbb{S}^{k+k^{\prime}}$.

  5. (5)

_If $m=3k+2$ and $n=3k^{\prime}$._ In this case,
$G_{m,n}\simeq\textup{del}{\left(a,G_{m,n}\right)}\simeq\\{pt\\}*\mathbb{S}^{k^{\prime}-1}=\\{pt\\}$.

Case 2 _$m=3k+1$ , $n=3k^{\prime}+1$._

Consider the following diagram Figure 5 of wedge of two cycles where the wedge
point $a$ is taken to be $a_{3k+1}=b_{3k^{\prime}+1}$.

Figure 5. Wedge of $C_{3k+1}$ and $C_{3k^{\prime}+1}$

Consider the simplex

$\sigma=\left\\{a_{1},a_{3},a_{6},a_{9},\cdots,a_{3k}\right\\}\cup\left\\{b_{1},b_{3},b_{6},\cdots,b_{3k^{\prime}}\right\\}.$

Since
$\sigma\in\textup{del}{\left(a\right)}\setminus\textup{lk}{\left(a\right)}$
and $\textup{del}{\left(a\right)}\setminus\\{\sigma\\}$ is contractible in
$\textup{del}{\left(a\right)}$, we get using Lemma 3.1 that

$\displaystyle G_{m,n}$
$\displaystyle=\textup{del}{\left(a,G_{m,n}\right)}\vee\Sigma\textup{lk}{\left(a,G_{m,n}\right)}$
$\displaystyle=\mathbb{S}^{k+k^{\prime}-1}\vee\mathbb{S}^{k+k^{\prime}},$

as
$\textup{del}{\left(a,G_{m,n}\right)}\simeq\mathcal{I}(P_{m-1})*\mathcal{I}(P_{n-1})\simeq\mathcal{I}(P_{3k})*\mathcal{I}(P_{3k^{\prime}})\simeq\mathbb{S}^{k+k^{\prime}-1}$
and
$\textup{lk}{\left(a,G_{m,n}\right)}\simeq\mathcal{I}(P_{m-2})*\mathcal{I}(P_{n-2})\simeq\mathcal{I}(P_{3k-1})*\mathcal{I}(P_{3k^{\prime}-1})\simeq\mathcal{I}(P_{3(k-1)+2})*\mathcal{I}(P_{3(k^{\prime}-1)+2})\simeq\mathbb{S}^{k+k^{\prime}-1}$.

Case 3 _$m=3k+2$ , $n=3k^{\prime}+1$._

In this case, we have $\textup{del}{\left(a,G_{m,n}\right)}$ is contractible
as shown in Lemma 3.3. Therefore, using Lemma 3.3, we have
$G_{m,n}\simeq\Sigma\textup{lk}{\left(a,G_{m,n}\right)}$. Therefore,

$\displaystyle G_{m,n}$
$\displaystyle\simeq\Sigma\bigg{(}\mathcal{I}(P_{m-2})*\mathcal{I}(P_{n-2})\bigg{)}$
$\displaystyle\simeq\Sigma\bigg{(}\mathcal{I}(P_{3k})*\mathcal{I}(P_{3(k^{\prime}-1)+2})\bigg{)}$
$\displaystyle\simeq\Sigma\bigg{(}\mathbb{S}^{k-1}*\mathbb{S}^{k^{\prime}-1}\bigg{)}\simeq\mathbb{S}^{k+k^{\prime}}.$

Case 4 _$m=3k+1$ , $n=3k^{\prime}+2$._

In this case, we have $\textup{del}{\left(a,G_{m,n}\right)}$ is contractible
as shown in Lemma 3.3. Therefore, using Lemma 3.3, we have
$G_{m,n}\simeq\Sigma\textup{lk}{\left(a,G_{m,n}\right)}$. Therefore,

$\displaystyle G_{m,n}$
$\displaystyle\simeq\Sigma\bigg{(}\mathcal{I}(P_{m-2})*\mathcal{I}(P_{n-2})\bigg{)}$
$\displaystyle\simeq\Sigma\bigg{(}\mathcal{I}(P_{3(k-1)+2})*\mathcal{I}(P_{3k^{\prime}})\bigg{)}$
$\displaystyle\simeq\Sigma\bigg{(}\mathbb{S}^{k-1}*\mathbb{S}^{k^{\prime}-1}\bigg{)}\simeq\mathbb{S}^{k+k^{\prime}}.$

Case 5 _$m=3k+2$ , $n=3k^{\prime}+2$._

In this case, we have $\textup{del}{\left(a,G_{m,n}\right)}$ is contractible
as shown in Lemma 3.3. Therefore, using Lemma 3.3, we have
$G_{m,n}\simeq\Sigma\textup{lk}{\left(a,G_{m,n}\right)}$. Therefore,

$\displaystyle G_{m,n}$
$\displaystyle\simeq\Sigma\bigg{(}\mathcal{I}(P_{m-2})*\mathcal{I}(P_{n-2})\bigg{)}$
$\displaystyle\simeq\Sigma\bigg{(}\mathcal{I}(P_{3k})*\mathcal{I}(P_{3k^{\prime}})\bigg{)}$
$\displaystyle\simeq\Sigma\bigg{(}\mathbb{S}^{k-1}*\mathbb{S}^{k^{\prime}-1}\bigg{)}\simeq\mathbb{S}^{k+k^{\prime}}.$

This proves the theorem. ∎

Now we present the generalization of the previous theorem. We hope the path to
generalization will be clear to the reader. We present the theorem without a
detailed proof here, to avoid cumbersomeness.

######  Theorem 3.6.

Let $\bigvee_{i=1}^{k}C_{m_{i}}$ be the wedge of $k$-many cycle graphs. Then
$\mathcal{I}(\bigvee_{i=1}^{k}C_{m_{i}})$ is contractible or wedge of spheres.

###### Proof.

The proof follows from using Lemma 3.4 and induction on $k$. ∎

The next class of graphs is a wedge of a path and a cycle graph. Assume
$C_{n}$ to be the cycle graph whose vertex set is $\\{a_{1},\dots,a_{n}\\}$
oriented counterclockwise and $P_{m}$ be the path graph with vertex set is
$\\{b_{1}\dots,b_{n}\\}$. For $1\leq k\leq\lceil n/2\rceil$, consider the
wedge graph $G_{k}=C_{n}\underset{c_{k}=a_{1}\sim b_{k}}{\vee}P_{m}$. Note
that the function $\lceil~{}\rceil$ appears to avoid obvious isomorphic
classes of graphs. See Fig. 6 for a visual. Next we compute the independence
complex of this graph.

Figure 6. A graph $G_{k}$

######  Theorem 3.7.

The independence complex $\mathcal{I}(G_{k})$ is homotopy equivalent to either
a point or wedge of spheres.

###### Proof.

Let $c_{k}$ be the wedge point of the graph $G_{k}$. Let $C_{n}(n-3)$ be the
subgraph of $G_{k}$ on vertices $\\{a_{3},\dots,a_{n-1}\\}$. One can see that
$C_{n}(n-3)$ is isomorphic to the path graph $P_{n-3}$ on $n-3$ vertices. Let
$P_{m}(k-2)$ be the subgraph of $P_{m}$ on vertices
$\\{b_{1},\dots,b_{k-2}\\}$ and $P_{m}(m-k-1)$ be the subgraph of $P_{m}$ on
$\\{b_{k+2},\dots,b_{m}\\}$. One can see that $P_{m}(k-2)$ is isomorphic to
the path graph $P_{k-2}$ and $P_{m}(m-k-1)$ is isomorphic to $P_{m-k-1}$. Note
that the link $\mathrm{lk}(c_{k},\mathcal{I}(G_{k}))$ can be described as

$\bigg{\\{}A\sqcup B\sqcup C\mid A\in\mathcal{I}(C_{n}(n-3)),B\in
P_{m}(k-2)\text{ and }C\in P_{m}(m-k-1)\bigg{\\}}.$

Therefore, we get the following

$\mathrm{lk}(c_{k},\mathcal{I}(G_{k}))\simeq\mathcal{I}(P_{n-3})*\mathcal{I}(P_{k-2})*\mathcal{I}(P_{m-k-1})$

and

$\mathrm{del}(c_{k},\mathcal{I}(G_{k}))\simeq\mathcal{I}(P_{n-1})*\mathcal{I}(P_{k-1})*\mathcal{I}(P_{m-k}).$

It is easy to see that $\mathrm{lk}(c_{k},\mathcal{I}(G_{k}))$ is contractible
in $\mathrm{del}(c_{k},\mathcal{I}(G_{k}))$. Then by Lemma 2.6, we get
$\mathcal{I}(G_{k})\simeq\mathrm{del}(c_{k},\mathcal{I}(G_{k}))\vee\Sigma\mathrm{lk}(c_{k},\mathcal{I}(G_{k}))$.
Let $\alpha=a+b+c$.

|  | $\mathrm{del}$ | $\mathrm{lk}$
---|---|---|---
|  $m-k$ $k$ | $3b$ | $3b+1$ | $3b+2$ | $3b$ | $3b+1$ | $3b+2$
$n=3a$ | $3c$ | $\mathbb{S}^{\alpha-1}$ | $\mathbb{S}^{\alpha-1}$ | pt | pt | pt | pt
$3c+1$ | pt | pt | pt | pt | $\mathbb{S}^{\alpha}$ | $\mathbb{S}^{\alpha}$
$3c+2$ | $\mathbb{S}^{\alpha}$ | $\mathbb{S}^{\alpha}$ | pt | pt | $\mathbb{S}^{\alpha}$ | $\mathbb{S}^{\alpha}$
$n=3a+1$ | $3c$ | $\mathbb{S}^{\alpha-2}$ | $\mathbb{S}^{\alpha-2}$ | pt | pt | pt | pt
$3c+1$ | pt | pt | pt | pt | pt | pt
$3c+2$ | $\mathbb{S}^{\alpha-1}$ | $\mathbb{S}^{\alpha-1}$ | pt | pt | pt | pt
$n=3a+2$ | $3c$ | pt | pt | pt | pt | pt | pt
$3c+1$ | pt | pt | pt | pt | $\mathbb{S}^{\alpha+1}$ | $\mathbb{S}^{\alpha+1}$
$3c+2$ | pt | pt | pt | pt | $\mathbb{S}^{\alpha+1}$ | $\mathbb{S}^{\alpha+1}$
Table 1. Computation for $\mathrm{del}$ and $\mathrm{lk}$ |  $m-k$ $k$ | $3b$ | $3b+1$ | $3b+2$
---|---|---|---|---
$n=3a$ | $3c$ | $\mathbb{S}^{\alpha-1}$ | $\mathbb{S}^{\alpha-1}$ | pt
$3c+1$ | pt | $\mathbb{S}^{\alpha+1}$ | $\mathbb{S}^{\alpha+1}$
$3c+2$ | $\mathbb{S}^{\alpha}$ | $\mathbb{S}^{\alpha}\vee\mathbb{S}^{\alpha+1}$ | $\mathbb{S}^{\alpha+1}$
$n=3a+1$ | $3c$ | $\mathbb{S}^{\alpha-2}$ | $\mathbb{S}^{\alpha-2}$ | pt
$3c+1$ | pt | pt | pt
$3c+2$ | $\mathbb{S}^{\alpha-1}$ | $\mathbb{S}^{\alpha-1}$ | pt
$n=3a+2$ | $3c$ | pt | pt | pt
$3c+1$ | pt | $\mathbb{S}^{\alpha+2}$ | $\mathbb{S}^{\alpha+2}$
$3c+2$ | pt | $\mathbb{S}^{\alpha+2}$ | $\mathbb{S}^{\alpha+2}$
Table 2. Independence complex

∎

Finally, we will compute the independence complex of a wedge of $k$ many path
graphs. Note that the wedge graphs vary with the choice of wedge point.
Furthermore, the graph obtained after choosing one wedge point, it can be
viewed as _terminal wedge of path graphs_.

Figure 7. $P_{7}\vee P_{7}\vee P_{5}=P_{4}\vee P_{4}\vee P_{4}\vee P_{4}\vee
P_{3}\vee P_{3}$

######  Theorem 3.8.

The independence complex $\mathcal{I}\left(\bigvee_{i=1}^{k}P_{m_{i}}\right)$
of terminal wedge $k$ many path graphs is either a point or a sphere.

###### Proof.

$a$
---

$P_{m_{1}}$
---

$P_{m_{2}}$
---

$P_{m_{3}}$
---

$P_{m_{4}}$
---

$P_{m_{k}}$
---

Figure 8. Terminal wedge of path graphs

First we focus on the case if one of them is of the form $3m$. Without loss of
generality we will assume that $m_{1}=3m$.

Figure 9. Reduction step

Applying Theorem 2.11 (see Figure 9) to $P_{m_{1}}$, we get that

$\mathcal{I}\left(P_{m_{1}}\vee P_{m_{2}}\vee\cdots\vee
P_{m_{k}}\right)=\left(\mathcal{I}(P_{2})\right)^{*(m)}*\mathcal{I}(P_{m_{2}-1})*\cdots*\mathcal{I}(P_{m_{k}-1}).$
(4)

Next, we will compute the independence complex of a wedge of path graphs when
all of them are either of the form $3l_{i}+1$ or $3l_{i}+2$. Now we consider
the case if all of them are of the form $3l_{i}+1$. Then using the Theorem
2.11 (See Fig. 9), we get that independence complexes

$\displaystyle\mathcal{I}\left(\bigvee_{i=1}^{k}P_{m_{i}}\right)$
$\displaystyle=\mathcal{I}(\\{a\\})*\mathcal{I}(P_{2})^{*(l_{1})}*\mathcal{I}(P_{2})^{*(l_{2})}*\cdots*\mathcal{I}(P_{2})^{*(l_{k})}$
$\displaystyle=\textup{pt}.$

Next, assume that all $m_{i}$’s are of the form $3l_{i}+2$. In this case,
using Theorem 2.11 (See Fig. 9), we get that independence complexes

$\displaystyle\mathcal{I}\left(\bigvee_{i=1}^{k}P_{m_{i}}\right)$
$\displaystyle=\mathcal{I}(P_{2})*\mathcal{I}(P_{2})^{*(l_{1})}*\mathcal{I}(P_{2})^{*(l_{2})}*\cdots*\mathcal{I}(P_{2})^{*(l_{k})}$
$\displaystyle=\mathbb{S}^{l_{1}+\cdots+l_{k}}.$

Finally, we will compute if some of them are of the form $3l_{i}+1$ and some
are of the form $3l_{i}+2$. We assume that $k=t+r$, where $m_{i}$’s are of the
form $3l_{i}+1$ for $i=1,2,\cdots,t$ and the rest of them are of the form
$3l_{i}+2$ for $i=t+1,\cdots,t+r$. Applying Theorem 2.11 repeatedly (See Fig.
9), we obtain

$\displaystyle I\left(\bigvee_{i=1}^{k}P_{m_{i}}\right)$
$\displaystyle=\mathbb{S}^{l_{1}+\cdots+l_{k}-1}.$

∎

## References

  * [1] E. Babson and D. N. Kozlov, Proof of the Lovász conjecture, Ann. Math. (2), 165 (2007), pp. 965–1007.
  * [2] M. Bousquet-Mélou, S. Linusson, and E. Nevo, On the independence complex of square grids, J. Algebraic Combin., 27 (2008), pp. 423–450.
  * [3] B. Braun, Independence complexes of stable Kneser graphs, Electron. J. Comb., 18 (2011), pp. research paper p118, 17.
  * [4] A. Engström, Independence complexes of claw-free graphs, Eur. J. Comb., 29 (2008), pp. 234–241.
  * [5] S. Goyal, S. Shukla, and A. Singh, Matching complexes of $3\times n$ grid graphs, Electron. J. Combin., 28 (2021), pp. Paper No. 4.16, 26.
  * [6] K. Kawamura, Homotopy types of independence complexes of forests, Contrib. Discrete Math., 5 (2010), pp. 67–75.
  * [7] , Independence complexes of chordal graphs, Discrete Math., 310 (2010), pp. 2204–2211.
  * [8] D. N. Kozlov, Complexes of directed trees, J. Combin. Theory Ser. A, 88 (1999), pp. 112–122.
  * [9] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Comb. Theory, Ser. A, 25 (1978), pp. 319–324.


# Assessing Network Representations for Identifying Interdisciplinarity

Eoghan Cunningham  0000-0002-0435-1962 School of Computer Science, University
College DublinDublin, Ireland<EMAIL_ADDRESS>and  Derek
Greene  0000-0001-8065-5418 School of Computer Science, University College
DublinDublin, Ireland<EMAIL_ADDRESS>
(2022)

###### Abstract.

Many studies have sought to identify interdisciplinary research as a function
of the diversity of disciplines identified in an article’s references or
citations. However, given the constant evolution of the scientific landscape,
disciplinary boundaries are shifting and blurring, making it increasingly
difficult to describe research within a strict taxonomy. In this work, we
explore the potential for graph learning methods to learn embedded
representations for research papers that encode their ‘interdisciplinarity’ in
a citation network. This facilitates the identification of interdisciplinary
research without the use of disciplinary categories. We evaluate these
representations and their ability to identify interdisciplinary research,
according to their utility in interdisciplinary citation prediction. We find
that those representations which preserve structural equivalence in the
citation graph are best able to predict distant, interdisciplinary
interactions in the network, according to multiple definitions of citation
distance.

datasets, scientific knowledge representation, interdisciplinarity

††journalyear: 2022††copyright: rightsretained††conference: Companion
Proceedings of the Web Conference 2022; April 25–29, 2022; Virtual Event,
Lyon, France††booktitle: Companion Proceedings of the Web Conference 2022 (WWW
’22 Companion), April 25–29, 2022, Virtual Event, Lyon, France††doi:
10.1145/3487553.3524653††isbn: 978-1-4503-9130-6/22/04††ccs: Computing
methodologies Learning latent representations

##  1\. Introduction

_Interdisciplinary research_ is most commonly defined as research activity
which integrates expertise, data or methodologies from two or more distinct
disciplines. In light of its perceived importance, many studies have been
conducted that quantify article and author interdisciplinarity in an effort to
identify relevant research trends and to explore their impact. The most
widely-accepted methods for measuring interdisciplinarity assess _knowledge
integration_ using citation information, attempting to measure
interdisciplinarity as a function of the balance, diversity, and dissimilarity
of the topics identified in an article’s cited papers (Rafols and Meyer, 2010;
Porter et al., 2007; Okamura, 2019). Using these methods, a trend towards
increased interdisciplinarity has been identified (Porter and Rafols, 2009),
which has been been found to correlate positively with research impact
(Okamura, 2019; Larivière et al., 2015) and productivity (Leahey et al.,
2017).

Despite some agreement across measures of interdisciplinarity (with many
studies based on work by (Porter et al., 2007)), the literature lacks
convergence towards a single metric (Wagner et al., 2011). Most candidate
metrics are reliant on explicit research topic or subject category
information, for which sources are numerous, diverse, and sometimes
unavailable. Moreover, the scientific community structure has been shown to be
evolving rapidly (Rosvall and Bergstrom, 2008). This evolution may explain the
lack of agreement between subject taxonomies and hierarchies, which vary
considerably (Milojević, 2020). The limitations of prescribed, static, subject
classifications necessitate a modern approach that identifies research
disciplines – and indeed interdisciplinarity – according to research network
structure. Such an approach may offer a dynamic view of interdisciplinarity,
and may help to map emerging developments that do not fit any existing schema
(Wagner et al., 2011).

In this work, we begin to investigate appropriate graph representation
learning methods which allow us to identify and quantify research
interdisciplinarity in citation networks, so that we can monitor
interdisciplinary interactions and track the development of research topics.
We propose to learn unsupervised node (or paper)-level representations in
research citation networks that encode research ‘interdisciplinarity’. In
pursuit of such a representation, we explore the different network
characteristics that embeddings must preserve in order to encode
interdisciplinarity and we evaluate these embeddings according to their
utility in an interdisciplinary citation prediction task. Specifically, we
investigate how the performance of link prediction models (based on different
node representations) is affected by the distance of citation, according to
the hypothesis that representations that encode article interdisciplinarity
will fare better when predicting “far-reaching” or “long-distance”
interdisciplinary interactions/citations (Larivière et al., 2015), compared to
those that do not. Given the acknowledged limitations of journal-level subject
categories, we explore multiple definitions of citation distance: both
according to prescribed categories with predefined topic distances, and to
network defined distances according to graph structure.

##  2\. Background

###  2.1. Measuring Interdisciplinarity

Numerous studies have developed metrics for quantifying research
interdisciplinarity (IDR). Generally, these methods are designed to evaluate
interdisciplinarity in pursuit of three goals: (i) to explore trends in IDR
over time (Porter and Rafols, 2009), (ii) to measure the benefits of IDR
(Okamura, 2019; Leahey et al., 2017; Larivière et al., 2015), (iii) to measure
changes in interdisciplinarity in response to IDR initiatives (Porter et al.,
2007). While the proposed approaches are diverse, interdisciplinarity is most
commonly measured on the basis of citation analysis. Using citations to model
the flow of information, _knowledge integration_ is calculated as a function
of the balance, diversity and/or distance between the disciplines identified
in _referenced_ articles (Porter and Rafols, 2009; Rafols and Meyer, 2010;
Okamura, 2019; Abramo et al., 2018). Conversely, _knowledge diffusion_ is
measured according to the disciplines of _citing_ articles (Van Noorden et
al., 2015; Porter and Chubin, 1985). These definition of knowledge
integration, knowledge diffusion, or a combination of both have been used to
enumerate interdisciplinarity for research papers. Invariably, such methods
are reliant on explicit topic or discipline categories for research papers,
such as those provided by Web of Science, Scopus, or Microsoft Academic. Such
explicit categorisations for research papers, especially those assigned at a
journal level, are problematic (Milojević, 2020; Abramo et al., 2018).
Moreover, the inconsistencies evident across many of these subject taxonomies
(Shen et al., 2019) may confirm that no singular, correct categorisation
exists. However, recent graph learning methods may be capable of learning
article representations that encode interdisciplinarity, without any knowledge
of explicit discipline categorisation.

###  2.2. Graph Learning - Node Embeddings

Motivated by extensive work on embedded representations in natural language
processing (Mikolov et al., 2013), recently there has been considerable focus
in the field of network analysis on developing analogous approaches for
transforming nodes into low-dimensional vector representations (Cai et al.,
2018; Goyal and Ferrara, 2018). Methods for producing such representations, or
node embeddings, are designed to preserve important relationships between
nodes on the graph. In particular, we focus on approaches which preserve
_proximity_ (where similar embeddings are learned for nodes which belong to
the same community in the graph) and _structural equivalence_ (where similar
embeddings are learned for nodes which have the same structural role in the
graph).

The _DeepWalk_ method (Perozzi et al., 2014), which extends the natural
language processing-inspired SkipGram model (Mikolov et al., 2013), generates
fixed-length random walks from all nodes on the graph. The model learns to
predict the nodes that will occur on walks given the starting node as input.
As such, the model preserves proximities between nodes by learning similar
embeddings for nodes which occur in similar contents, i.e. nodes that co-occur
on random walks. _node2vec_ , proposed by (Grover and Leskovec, 2016), extends
DeepWalk, introducing two parameters which can be used to bias the random
walks in order to explore different aspects of network structure. In our
experiments, we implement both DeepWalk and node2vec as examples of proximity
preserving node embeddings. We also explore the structural equivalence
preserving ‘role embeddings’ learned via _role2vec_ (Ahmed et al., 2019). The
role2vec model further generalises the DeepWalk model attributing structural
features (e.g. graph motif counts) to nodes before mapping those nodes to
‘roles’ and conducting role-based random walks.

##  3\. Data

We conduct experiments using five citation networks, where each paper is
represented as a node and citations are represented as undirected edges
between them. Three of these datasets are well-known benchmark networks used
to evaluate graph learning algorithms. We also contribute two new datasets
which we have collected.

###  3.1. Benchmark Datasets

As our three benchmark bibliographic datasets we consider _Cora_ (McCallum et
al., 2000), _CiteSeer_ (Lu and Getoor, 2003), and _PubMed_ (Namata et al.,
2012). These datasets range from 2,708 to 19,717 nodes (papers), with an
average node degree (citations per paper) ranging from 2.7 – 4.5. Each paper
is assigned a label, representing a topic or field within a discipline. For
example, the Cora dataset contains 7 topics within the field of Computer
Science: _‘case based’_ , _‘genetic algorithms’_ , _’neural networks’_ ,
_‘probabilistic methods’_ , _‘reinforcement learning’_ , _‘rule learning’_ ,
and _‘theory’_. While these datasets offer an accessible medium for exploring
research networks, the insights gained from them may be limited by their
sparsity (low node degree) and the scale of interdisciplinarity, i.e. they
represent interactions between topics within a discipline, rather than macro
interdisciplinary interactions. As such, we also provide two additional
citation graphs that are both more complete and more interdisciplinary in
nature.

###  3.2. Scopus Indexed Datasets

We construct new citation networks using Microsoft Academic Graph citation
data from two different sets of journal papers. These sets consist of two
samples of articles from Scopus indexed journals, stratified according to
their All Science Journal Categories (ASJC). We define two networks containing
different topics, so that we can investigate interactions between different
subsets of disciplines. We refer to these networks as _Scopus1_ and _Scopus2_.
The former contains samples of 1,500 articles published between 2017 and 2018
in Scopus indexed journals with the ASJCs _‘Computer Science’, ‘Mathematics’,
‘Medicine’, ‘Chemistry’_ , and _‘Social Sciences’_. For Scopus2, we use the
seed set of categories: _‘Computer Science’, ‘Mathematics’, ‘Neuroscience’,
‘Engineering’,_ and _‘Biochemistry, Genetics and Molecular Biology’_. For both
datasets, we maximise the completeness of the graph by including all available
referenced articles that are published in Scopus indexed journals. In this
manner, we produce dense, multidisciplinary citation networks, such that each
article can be categorised according to the ASJC of the journal in which it
was published. Scopus1 contains 27,213 nodes with average degree 6.9, while
Scopus2 contains 25,961 nodes with average degree 6.2. See statistics for all
datasets in Table 1 of the Appendix.

##  4\. Methods

###  4.1. Citation Prediction

One established method for evaluating the quality of node embeddings is to
assess their performance in a down-stream link prediction task (Kipf and
Welling, 2016; Grover and Leskovec, 2016). We introduce the following citation
prediction task to evaluate the quality of our paper representations and their
ability to encode the citation graph structure. Further, we explore their
ability to identify and predict interdisciplinary interactions in the network
through their performance in interdisciplinary citation prediction. We
evaluate citation prediction performance with different node representations
using 75:5:20 train:validation:test splits of the edges in each network. Three
sets of node representations (DeepWalk, node2vec, and role2vec) are learned
using the subgraph induced by the training edges. In the case of each model,
we learn node embeddings with 128 dimensions. To train a Multi-Layer
Perception (MLP) model for the citation prediction task, we supplement each
set of edges with a set of negative edges that were not present in the graph.
We then represent each edge as the concatenation of the embedded
representations of the associated nodes, and use train and validation edge
sets to train an MLP model to classify positive and negative edges. We report
performance on the test data as the area under the Receiver Operating
Characteristic curve (AUC). Each experiment is repeated for 5 random splits of
the data and the average AUC score is reported. Using this approach we
evaluate the utility of different node representations in both overall
citation prediction and in interdisciplinary citation prediction.

We use the following methods to identify interdisciplinary citations in the
test data according to both binary and continuous definitions of
interdisciplinary. We report the binary interdisciplinary citation prediction
score as the AUC performance on the test data for only the edges where the
associated nodes belong to different classifications. These scores appear in
parentheses in Table 1. In Figure 1 we compare the relationship between
citation prediction performance and citation distance according to our
continuous definitions of interdisciplinarity, according to the intuition that
representations that encode article interdisciplinarity will fare better when
predicting “long-distance” interdisciplinary citations. To explore this
relationship, we aggregate the edges in the test data (into bins of equal
width) according to the chosen definition of citation distance, and plot the
AUC for bins that contain at least 25 positive and negative edges.

###  4.2. Citation Distance Metrics

To allow us to define a continuous form of interdisciplinarity, we implement
and evaluate five definitions of citation distance: _Scopus Topic Distance_ ,
_Network Distance_ , _DeepWalk Embedding Distance_ , _Node2vec Embedding
Distance_ , and _Role2vec Embedding Distance_. Scopus Topic Distance is
defined according the neighbourhood similarity of the ASJC. Using a network of
6,000,000 papers published between 2010 and 2020, we create a discipline-level
weighted adjacency matrix $\mathbf{W}$, that encodes all of the citations
between categories in the ASJC. We define the topic distance between two
categories $i$ and $j$ as the value $1-S_{ij}$, where $S_{ij}$ is the cosine-
similarity between rows $i$ and $j$ in $\mathbf{W}$. Thus, we can calculate
the Scopus Topic Distance of a citation as the topic distance between the ASJC
assigned to each of the relevant papers. We define the Network Distance of a
citation as the length of the shortest path on the graph between to the two
relevant papers (Wasserman and Faust, 1994). Finally, each of the embedding
distances is defined as the cosine distance between the two vectors learned
for the pair of the papers involved in the citation.

##  5\. Results

###  5.1. Citation Prediction and Binary Interdisciplinarity

####  5.1.1. Benchmark Datasets

Table 1 shows citation results for 3 link prediction models, evaluated on 5
citation datasets. In each case, the AUC score is reported for both the entire
test set and the interdisciplinary portion of the test set (IDR AUC). For each
dataset, the structural representations learned by role2vec outperform those
learned by DeepWalk-based methods. Although predicting interdisciplinary
citations may be slightly more difficult than predicting intradisciplinary
citations, performance in each task seems to correlate well. That is, the
models which perform best at predicting citations within topics are also the
most performant when predicting citations between topics. However, due to the
limitations in scale and completeness of the benchmark datasets (see Section
3.1), we continue experiments using two new citation graphs collected from
journals indexed by Scopus.

Table 1. Citation prediction results: AUC (IDR AUC). Dataset | node2vec (Grover and Leskovec, 2016) | DeepWalk (Perozzi et al., 2014) | role2vec (Ahmed et al., 2019)
---|---|---|---
_Cora_ | 0.785 (0.789) | 0.782 (0.769) | 0.836 (0.817)
_CiteSeer_ | 0.700 (0.670) | 0.692 (0.644) | 0.766 (0.750)
_PubMed_ | 0.800 (0.788) | 0.800 (0.778) | 0.823 (0.818)
_Scopus1_ | 0.909 (0.903) | 0.906 (0.901) | 0.900 (0.896)
_Scopus2_ | 0.879 (0.875) | 0.879 (0.874) | 0.868 (0.869)

####  5.1.2. Scopus Indexed Datasets

Table 1 reports citation prediction performance in relation to the Scopus
datasets. In the case of these larger, more diverse and denser networks, we
find link prediction models are more successful, likely due to the greater
completeness of the graph. Moreover, the DeepWalk-based methods are no longer
less effective than role2vec embeddings, and the gap between intradisciplinary
and interdisciplinary scores has reduced further. To understand better the
ability of different representations to encode the interdisciplinary role of
research articles (by identifying those which can that can predict citations
at greater distances), we now move to a continuous definition of citation
distance.

###  5.2. Citation Distance Metrics

In our Scopus indexed networks, we explore 5 definitions of citation distance:
1 according to journal-level ASJC classifications and their citation
neighbourhoods, 3 according to the distance between different unsupervised
embedding representations, and 1 according to shortest path distance between
papers. We compare these definitions of citation distance below, where we
evaluate their relationship with network modularity and edge betweenness.

####  5.2.1. Edge Distance and Modularity

We compare frequency distributions for distances of positive and negative
edges to examine the extent to which different metrics of edge distance
capture modularity in the Scopus networks. See the supplemental figures in the
Appendix. Crucially, we find that the DeepWalk and node2vec defined citation
distances offer the best separation between distributions of positive and
negative edges.

####  5.2.2. Edge Distance and Edge Betweenness

Table 2 shows Spearman rank correlations between citation distance and edge
betweenness centrality, for each metric of citation distance in the Scopus
indexed graph. The edge betweenness centrality for an edge (or citation) is a
measure of the proportion of shortest paths on the graph which traverse that
edge (Girvan and Newman, 2002). So citations which bridge or connect
communities will have high edge betweenness centrality. As such, we expect a
definition of citation distance which encodes the interdisciplinarity of
citation, to correlate positively with edge betweenness. The distance measures
defined according to the distance between DeepWalk-based embeddings are shown
to have the strongest correlation with edge betweenness centrality.
Conversely, the distances between prescribed topics based on the ASJC from
Scopus show no correlation with edge betweenness, indicating that these topic
assignments, or at least the defined distances between them, do not reflect
the community structure in the graph.

We can further investigate the validity of the ASJC paper categorisations in
the Scopus datasets, by comparing the edge betweenness scores of inter- and
intra-topic edges. If the ASJC assignments represent the communities in the
network, we would expect edges that are _between_ ASJC topics (i.e. citations
linking papers of different categories) to have greater betweenness than those
edges that are _within_ ASJC topics (i.e. linking papers with the same
category). A Kolmogorov-Smirnov test comparing the edge betweenness
distributions of inter- and intra-disciplinary edges finds interdisciplinary
edges to have greater betweenness at 5% significance. This indicates that,
while the predefined distances between ASJC topics do not correlate with
citation distance, the ASJC categorisations are somewhat reflective of the
communities in the network.

Table 2. Citation distances correlated with edge betweenness. Distance | _Scopus1_ | _Scopus2_
---|---|---
Scopus Topic | 0.029 | -0.020
DeepWalk | 0.331 | 0.300
Node2vec | 0.329 | 0.304
Role2vec | 0.191 | 0.193
Figure 1. _Scopus1_ prediction performance (AUC) plotted against citation distance, for different node representations and different metrics of citation distance. Table 3. Link prediction AUC correlated with citation distance. Distance | role2vec | DeepWalk | node2vec
---|---|---|---
Scopus Topic | 0.444* | 0.327* | 0.323*
DeepWalk Embedding | 0.642* | -0.061 | -0.139*
Node2vec Embedding | 0.632* | -0.126* | -0.129*
Role2vec Embedding | -0.875* | -0.929* | -0.914*
Network Distance | 0.245 | -0.173 | -0.191

####  5.2.3. Citation Distance and Link Prediction

Table 3 reports the linear regression coefficients comparing citation
prediction performance with citation distance in the _Scopus1_ network. The
table include stars to highlight regression coefficients significant at 5%
significance. In particular, we note that the models employing role2vec
structural representations of the nodes perform better as citation distance
increases according to most definitions of citation distance. Table 5 in the
Appendix plots similar results for _Scopus2_ , where role2vec performance
again increases with those distances that agree with the underlying network
structure.

##  6\. Discussion and Conclusions

In our investigations of the potential for graph learning methods to identify
interdisciplinary research, we explored three different methods of node
representation and evaluated their utility in predicting interdisciplinary
citations. According to a binary definition of interdisciplinary citation, we
found that predicting links between research topics is indeed more difficult
than predicting within-topic interactions. This effect is more evident in
sparser networks, such as the benchmark citation graphs _Cora_ , _CiteSeer_ ,
and _PubMed_. In the more complete citation networks that we have collected
(_Scopus1_ and _Scopus2_), the distinction between citation prediction and
interdisciplinary citation prediction performances are less apparent.

We explored a continuous definition of interdisciplinary citation, as some
interactions are viewed as being more distant than others (Larivière et al.,
2015). We evaluated five different definitions of citation distance. Although
it remains difficult to determine the most accurate means of measuring the
distance or interdisciplinarity of citation, we highlighted a number of issues
with the predefined ASJC distances, which do not appear to agree with the
underlying network structures. Further, we found that the role2vec-based model
achieved citation prediction AUC that correlates positively with all metrics
of citation distance that do appear to encode the underlying network
structure. This provides evidence that the role2vec-based paper
representations are capable of encoding the structural signatures associated
with interdisciplinary interactions. We suggest that the embeddings which
preserve structural equivalence on the graph are capable of encoding the
‘interdisciplinary role’ of different articles.

We plan to extend this work to learning more advanced paper representations by
including text features on nodes in the graph. There is also potential to
develop means of better explaining these embeddings to quantify
interdisciplinarity and interpret the different interdisciplinary roles of
research papers.

Acknowledgements. This research was supported by Science Foundation Ireland
(SFI) under Grant Number SFI/12/RC/2289_P2.

## References

  * (1)
  * Abramo et al. (2018) Giovanni Abramo, Ciriaco Andrea D’Angelo, and Lin Zhang. 2018.  A comparison of two approaches for measuring interdisciplinary research output: The disciplinary diversity of authors vs the disciplinary diversity of the reference list.  _Journal of Informetrics_ 12, 4 (2018), 1182–1193.
  * Ahmed et al. (2019) Nesreen K. Ahmed, Ryan A. Rossi, John Boaz Lee, Theodore L. Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. 2019.  role2vec: Role-based network embeddings. In _Proc. DLG KDD_. 1–7.
  * Cai et al. (2018) Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2018\.  A comprehensive survey of graph embedding: Problems, techniques, and applications.  _IEEE Transactions on Knowledge and Data Engineering_ 30, 9 (2018), 1616–1637.
  * Girvan and Newman (2002) Michelle Girvan and Mark E.J. Newman. 2002.  Community structure in social and biological networks.  _Proceedings of the national academy of sciences_ 99, 12 (2002), 7821–7826.
  * Goyal and Ferrara (2018) Palash Goyal and Emilio Ferrara. 2018.  Graph embedding techniques, applications, and performance: A survey.  _Knowledge-Based Systems_ 151 (2018), 78–94.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks. In _Proc. 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 855–864.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ (2016).
  * Larivière et al. (2015) Vincent Larivière, Stefanie Haustein, and Katy Börner. 2015.  Long-distance interdisciplinarity leads to higher scientific impact.  _PloS one_ 10, 3 (2015), e0122565–e0122565.
  * Leahey et al. (2017) Erin Leahey, Christine M. Beckman, and Taryn L Stanko. 2017\.  Prominent but less productive: The impact of interdisciplinarity on scientists’ research.  _Administrative Science Quarterly_ 62, 1 (2017), 105–139.
  * Lu and Getoor (2003) Qing Lu and Lise Getoor. 2003.  Link-Based Classification. In _Proc. 20th International Conference on International Conference on Machine Learning_ (Washington, DC, USA) _(ICML’03)_. AAAI Press, 496–503.
  * McCallum et al. (2000) Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. 2000.  Automating the construction of internet portals with machine learning.  _Information Retrieval_ 3, 2 (2000), 127–163.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013\.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_ (2013).
  * Milojević (2020) Staša Milojević. 2020\.  Practical method to reclassify Web of Science articles into unique subject categories and broad disciplines.  _Quantitative Science Studies_ 1, 1 (02 2020), 183–206.
  * Namata et al. (2012) Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. 2012.  Query-driven active surveying for collective classification. In _Proc. 10th International Workshop on Mining and Learning with Graphs_ , Vol. 8. 1\.
  * Okamura (2019) Keisuke Okamura. 2019\.  Interdisciplinarity revisited: evidence for research impact and dynamism.  _Palgrave Communications_ 5, 1 (2019), 1–9.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _Proc. 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. 701–710.
  * Porter and Chubin (1985) ALDE Porter and D Chubin. 1985.  An indicator of cross-disciplinary research.  _Scientometrics_ 8, 3-4 (1985), 161–176.
  * Porter et al. (2007) Alan Porter, Alex Cohen, J. David Roessner, and Marty Perreault. 2007.  Measuring researcher interdisciplinarity.  _Scientometrics_ 72, 1 (2007), 117–147.
  * Porter and Rafols (2009) Alan Porter and Ismael Rafols. 2009.  Is science becoming more interdisciplinary? Measuring and mapping six research fields over time.  _Scientometrics_ 81, 3 (2009), 719–745.
  * Rafols and Meyer (2010) Ismael Rafols and Martin Meyer. 2010.  Diversity and network coherence as indicators of interdisciplinarity: case studies in bionanoscience.  _Scientometrics_ 82, 2 (2010), 263–287.
  * Rosvall and Bergstrom (2008) Martin Rosvall and Carl T Bergstrom. 2008.  Maps of random walks on complex networks reveal community structure.  _Proceedings of the National Academy of Sciences_ 105, 4 (2008), 1118–1123.
  * Shen et al. (2019) Zhesi Shen, Fuyou Chen, Liying Yang, and Jinshan Wu. 2019\.  Node2vec representation for clustering journals and as a possible measure of diversity.  _Journal of Data and Information Science_ 4, 2 (2019), 79\.
  * Van Noorden et al. (2015) Richard Van Noorden et al. 2015\.  Interdisciplinary research by the numbers.  _Nature_ 525, 7569 (2015), 306–307.
  * Wagner et al. (2011) Caroline S. Wagner, J. David Roessner, Kamau Bobb, Julie Thompson Klein, Kevin W. Boyack, Joann Keyton, Ismael Rafols, and Katy Börner. 2011.  Approaches to understanding and measuring interdisciplinary scientific research (IDR): A review of the literature.  _Journal of Informetrics_ 5, 1 (2011), 14–26.
  * Wasserman and Faust (1994) Stanley Wasserman and Katherine Faust. 1994.  _Social Network Analysis: Methods and Applications_.  Cambridge University Press.

##  Appendix A Supplementary Materials

###  A.1. Summary of Datasets

Table 4 below includes descriptive statistics for the five citation datasets
considered in our experiments, including the number of unique topics
(categories) per dataset.

Table 4. Summary of datasets. | Papers | Citations per Paper | Topics
---|---|---|---
Dataset |  |  |
_Cora_ | 2,708 | 3.90 | 7
_CiteSeer_ | 3,327 | 2.74 | 6
_PuMmed_ | 19,717 | 4.50 | 3
_Scopus1_ | 27,162 | 6.91 | 25
_Scopus2_ | 25,961 | 6.15 | 26

###  A.2. Scopus Edge Distance and Modularity

Figures 2 and 3 illustrate the edge distance distributions for both the
positive and negative edges in the training and test portions of the Scopus
indexed datasets. For each definition of edge distance, the frequency
distribution for the distance of positive edges is plotted in blue, and the
distance of negative edges is plotted in red. The DeepWalk-based methods
(DeepWalk and node2vec) appear to learn node representations that encode the
emergent communities in the graph, as adjacent nodes are assigned similar/near
embeddings, while non-adjacent nodes (represented by the negative edge
distribution in red) are found to have more distant embeddings.

Figure 2. Edge distance distribution for positive (blue) and negative (red)
edges in the _Scopus1_ dataset.

Edge distance distribution for positive (blue) and negative (red) edges in the
Scopus Indexed dataset.

Figure 3. Edge distance distribution for positive (blue) and negative (red)
edges in the _Scopus2_ dataset.

Edge distance distribution for positive (blue) and negative (red) edges in the
Scopus Indexed dataset.

Table 5. Link prediction AUC scores correlated with citation distances. Distance | role2vec | DeepWalk | node2vec
---|---|---|---
Scopus Topic | -0.036 | -0.006 | 0.059
DeepWalk Embedding | 0.144* | -0.456* | -0.373*
Node2vec Embedding | 0.284* | -0.357* | -0.218*
Role2vec Embedding | -0.843* | -0.778* | -0.807*
Network Distance | 0.296* | -0.388* | -0.401*

Figure 4. _Scopus2_ citation prediction performance (AUC) plotted against
citation distance, for different node representations and different metrics of
citation distance.

Edge distance distribution for positive (blue) and negative (red) edges in the
Scopus Indexed dataset.