# Generating hypergraphs of finite groups

Andrea Lucchini  Università degli Studi di Padova
Dipartimento di Matematica “Tullio Levi-Civita”
Via Trieste 63, 35121 Padova, Italy
email<EMAIL_ADDRESS>
###### Abstract.

In a recent paper Cameron, Lakshmanan and Ajith [5] began an exploration of
hypergraphs defined on algebraic structures, especially groups, to investigate
whether this can add a new perspective. Following their suggestions, we
consider suitable hypergraphs encoding the generating properties of a finite
group. In particular, answering a question asked in their paper, we classified
the finite solvable groups whose generating hypergraph is the basis hypergraph
of a matroid.

Project funded by the EuropeanUnion – NextGenerationEU under the National
Recovery and Resilience Plan (NRRP), Mission 4 Component 2 Investment 1.1 -
Call PRIN 2022 No. 104 of February 2, 2022 of Italian Ministry of University
and Research; Project 2022PSTWLB (subject area: PE - Physical Sciences and
Engineering) ” Group Theory and Applications”

##  1\. Introduction

An undirected hypergraph $H$ is a pair $H=(V,E)$ where $V$ is a set of
elements called nodes or vertices and $E$ is a non-empty subset of
$\mathcal{P}(V)$ (power set of $V$) called hyperedges.

Following the suggestions and considerations of Cameron, Lakshmanan and Ajith
in their recent paper [5], we concentrate our attention on hypergraphs that
encode the generating properties of finite groups.

The generating graph of a finite group $G$ is the graph defined on the
elements of $G$ in such a way that two distinct vertices are connected by an
edge if and only if they generate $G.$ It was defined by Liebeck and Shalev in
[17], and has been further investigated by many authors: see for example [2,
3, 4, 7, 8, 12, 19, 20, 21] for some of the range of questions that have been
considered. Clearly the generating graph of $G$ is an edgeless graph if $G$ is
not 2-generated. It is natural to think that for non-2-generated finite
groups, the concept of generating graph can be generalized by making use of
appropriate hypergraphs. We propose two possible definitions in this
direction. For a finite group $G$ denote by $d(G)$ the smallest size of a
generating set of $G$. We define the _generating hypergraph_ $\Gamma(G)$
associated to a finite group $G$ as the undirected hypergraph whose vertices
are the elements of $G$ and where the hyperedges are the generating sets of
$G$ of size $d(G).$ A minimal generating set of $G$ can have a size larger
then $d(G)$, so we may also consider another hypergraph $\Delta(G)$, whose
vertices are again the elements of $G$ but where the set of hyperedges
consists of all the minimal generating sets. We will use for $\Delta(G)$ the
name _global generating hypergraph_. The finite groups $G$ with the property
that $\Gamma(G)=\Delta(G)$ have been classified by P. Apise and B. Klopsch
[1]: they are solvable, with a quite restrictive structure.

The very particular case when $G$ is cyclic is quite different from the
general case; for example $\Gamma(G)$ does not contain hyperedges if we do not
admit loops. This is the reason why we will in general exclude cyclic groups
from our discussion.

In particular we concentrate our attention on the following aspects. In
Section 2 we will investigate whether the hypergraphs obtained from
$\Gamma(G)$ and $\Delta(G)$ by removing their isolated vertices are connected.
We will prove that the answer is affirmative for the global generating
hypergraph and for the generating hypergraph with the possible exclusion, in
the second case, of the 2-generated finite groups. In Section 3 we will
indicate how relevant structural properties of a finite group $G$ (for example
the $p$-solvability property) can be detected from the knowledge of the global
generating hypergraph $\Delta(G).$ Finally in Section 4, answering a question
asked in [5], we classify the finite solvable groups whose generating
hypergraph is the basis hypergraph of a matroid.

##  2\. Connectedness of the generating hypergraphs

A path in a hypergraph $H=(V,E)$ between two distinct vertices $x_{1}$ and
$x_{k}$ is a sequence $x_{1},e_{1},...,x_{k-1},e_{k-1},x_{k}$ with the
following properties:

  1. (1)

$x_{1},...,x_{k}$ are distinct vertices,

  2. (2)

$e_{1},...,e_{k-1}$ are hyperedges (not necessarily distinct),

  3. (3)

$x_{j},x_{j+1}\in e_{j}$ for $j=1,2,\dots,k-1.$

Two vertices $v,w\in V$ are said to be connected in $H$ if there exists a
$(v,w)$-path in $H$. A hypergraph $H$ is connected if every pair of vertices
$v,w\in V$ is connected in $H$. An obstacle to the connectedness of the
generating and global generating hypergraph of a finite group $G$ is the
possible presence of isolated vertices (certainty the identify element of $G$
is an isolated vertex in both hypergraphs). It is so interesting to describe
the set of the isolated vertices of $\Gamma(G)$ and $\Delta(G)$ and to
investigate whether the hypergraphs $\tilde{\Gamma}(G)$ and
$\tilde{\Delta}(G)$ obtained from $\Gamma(G)$ and $\Delta(G)$ by removing the
isolated vertices are connected.

In the case of the global generating ipergraph, the answer to the question
follows immediately from the results obtained in [18].

######  Theorem 1.

Let $G$ be a finite group. The set of isolated vertices of $\Delta(G)$
coincides with the Frattini subgroup $\operatorname{Frat}(G)$ of $G$ and the
hypergraph $\tilde{\Delta}(G)$ is connected.

###### Proof.

In [18] it is defined and investigated the independence graph of $G$: its
vertices are the elements of $G$ and two vertices $x_{1}$ and $x_{2}$ are
joined by an edge if and only if $x_{1}\neq x_{2}$ and there exists a minimal
generating set of $G$ containing $x_{1}$ and $x_{2}$. Clearly the independence
graph and the global generating hypergraph of $G$ have the same isolated
vertices and $\tilde{\Delta}(G)$ is connected if and only if it is connected
the subgraph of the independence graph of $G$ induced by its non-isolated
vertices. So the conclusion follows from Lemma 4 and Theorem 1 in [18]. ∎

Moving from $\Delta(G)$ to $\Gamma(G)$ the role of the independence graph is
played by the rank graph of $G$, in which two distinct vertices $x_{1}$ and
$x_{2}$ are joined by an edge if and only if $x_{1}\neq x_{2}$ and there
exists a generating set of $G$ of size $d(G)$ containing $x_{1}$ and $x_{2}$.
Again the isolated vertices of the rank graph and of the generating hypergraph
are the same, but it is difficult to give a good description of the set of
these isolated vertices. It is in general larger of the Frattini subgroup (for
example it contains all the elements of any normal subgroup $N$ of $G$ with
the property that $d(G)=d(G/N)$) and it is not in general a subgroup. When
$d(G)=2,$ ‘generating graph’, ‘rank graph’ and ‘generating hypergraph’ are
different names for the same object. It seems reasonable to conjecture that
the subgraph of the generating graph of a 2-generated finite group $G$ induced
by its non-isolated vertices is connected. This has been proved under
additional assumptions, for example if $G$ is solvable [8] or if $G$ is a
direct product of simple groups [9], but the question whether this is true in
general is quite difficult and still widely open. However the situation is
better when $d(G)\geq 3.$ In a recent joint paper with D. Nemmi [26] we proved
that, if $d(G)\geq 3,$ then the subgraph of the rank graph of $G$ induced by
its non-isolated vertices is connected. This implies the following theorem:

######  Theorem 2.

Let $G$ be a finite group. If $d(G)\geq 3,$ then the hypergraph
$\tilde{\Gamma}(G)$ is connected.

##  3\. Recognizing a finite group by its generating hypergraphs

For a given $t\in\mathbb{N},$ denote by $P_{G}(t)$ the probability that an
element $(g_{1},\dots,g_{t})$ of $G^{t}$ is a generating $t$-uple for $G$, i.e
$G=\langle g_{1},\dots,g_{t}\rangle.$ If $t\in\mathbb{N},$ then
$(g_{1},\dots,g_{t})$ is a generating $t$-uple of $G$ if and only if
$\\{g_{1},\dots,g_{t}\\}$ contains an hyperedge of $\Delta(G).$ So from the
knowledge of the global generating hypergraph $\Delta(G)$ we can determine
$P_{G}(t)$ for every $t\in\mathbb{N}.$ When we know the value of $P_{G}(t)$
for every $t\in\mathbb{N}$ (or at least for $|G|$ different values of $t$), we
can deduce a great amount of information on the structure of the finite group
$G$. Let us explain why. For any finite group $G$ we may define a sequence of
integers $\\{a_{n}(G)\\}_{n\in\mathbb{N}}$ as follows:

$a_{n}(G)=\sum_{|G:H|=n}\mu_{G}(H).$

Here $\mu_{G}$ is the Möbius function defined on the subgroup lattice of $G$
as $\mu_{G}(G)=1$ and $\mu_{G}(H)=-\sum_{H<K}\mu_{G}(K)$ for any $H<G$.

######  Lemma 3.

Let $G$ be a finite group. Then the knowledge of the hypergraph $\Delta(G)$
allows to determine $a_{n}(G)$ for every $n\in\mathbb{N}.$

###### Proof.

Let $\sum_{n\in\mathbb{N}}{a_{n}(G)}/{n^{s}}$ be the Dirichlet generating
function associated with the sequence $\\{a_{n}(G)\\}_{n\in\mathbb{N}}$. As it
was noticed by P. Hall [15], for any $t\in\mathbb{N}$, the value assumed on
$t$ by this Dirichlet polynomial coincides with $P_{G}(t).$ Let $m=|G|.$
Notice $(a_{1}(G),\dots,a_{m}(G))$ is a solution of the system

$\begin{cases}\frac{a_{1}(G)}{1}+\frac{a_{2}(G)}{2}+\dots+\frac{a_{m}(G)}{m}=P_{G}(1)\\\
\frac{a_{1}(G)}{1}+\frac{a_{2}(G)}{2^{2}}+\dots+\frac{a_{m}(G)}{m^{2}}=P_{G}(2)\\\
\dots\quad\dots\quad\dots\quad\dots\quad\dots\quad\dots\quad\dots\\\
\frac{a_{1}(G)}{1}+\frac{a_{2}(G)}{2^{m}}+\dots+\frac{a_{m}(G)}{m^{m}}=P_{G}(m).\\\
\end{cases}$

Since

$\det\begin{pmatrix}1&2&\cdots&m\\\ 1&2^{2}&\cdots&m^{2}\\\
\vdots&\vdots&\cdots&\vdots\\\ 1&2^{m}&\cdots&m^{m}\end{pmatrix}\neq 0,$

the system has a unique solution, hence the Dirichlet polynomial $P_{G}(s)$ is
uniquely determined from the knowledge of $P_{G}(1),P_{G}(2),\dots,P_{G}(m)$
and, consequently, from the knowledge of the hypergraph $\Delta(G).$ ∎

######  Theorem 4.

Let $G$ be a finite group and let $p$ be a prime divisor of $|G|.$ From the
knowledge of the hypergraph $\Delta(G)$ it is possible to detect whether $G$
is $p$-solvable. In particular it can be recognized whether $G$ is solvable.

###### Proof.

The proof follows from Lemma 3 combined with [11, Theorem 1] and [10, Theorem
1.2]. Indeed $G$ is $p$-solvable if and only if
$a_{p^{c}d}(G)=a_{p^{c}}(G)a_{d}(G),$ whenever $p$ and $d$ are relatively
prime. In particular $G$ is solvable if and only if
$a_{rs}(G)=a_{r}(G)a_{s}(G),$ whenever $r$ and $s$ are relatively prime. ∎

######  Theorem 5.

Let $G$ be a finite non-abelian simple group and let $X$ be a finite group. If
$\Delta(X)\cong\Delta(G),$ then $X\cong G.$

###### Proof.

By Lemma 3, $a_{n}(X)=a_{n}(G)$ for every $n\in\mathbb{N}.$ It follows from
[6] that $X/\operatorname{Frat}(X)$ is a finite non-abelian simple group.
Moreover $\operatorname{Frat}(G)=1,$ hence, by Theorem 1, the identity element
is the unique isolated vertex of $\Delta(G)$. Thus $\Delta(X)$ has the same
property, and consequently $\operatorname{Frat}(X)=1.$ Hence $X$ and $G$ are
simple groups with the same order. By [16, Theorem 5.1] $G$ and $X$ either are
$A_{2}(4)$ and $A_{3}(2)$ or are $B_{n}(q)$ and $C_{n}(q)$ for some $n\geq 3$
and some odd $q.$ However, a direct computation shows that
$P_{2}(A_{2}(4))\neq P_{2}(A_{3}(2))$, and in [21, Section 7] it is proved
that $P_{2}(B_{n}(q))\neq P_{2}(C_{n}(q)).$ Hence $X\cong G.$ ∎

The procedure described in the proof of Theorem 4 in order to recognize from
the knowledge of the global generating hypergraph $\Delta(G)$ whether the
finite group $G$ is solvable is quite complicate. One has to determine the
rational number $P_{G}(t)$ for several values of $t$ (this is in principle an
elementary task but requires a boring enumeration task) and to solve a system
with many equations and indeterminates. So it is natural to ask whether there
is some other more directed criterion, which relies for example on the
topological properties of the hypergraph $\Delta(G).$

##  4\. Basis hypergraph of a matroid

An important class of hypergraphs consists of the basis hypergraphs of
matroids. A basis of a matroid is a maximal independent set. The collection of
matroid bases is characterised by the two properties:

  1. (1)

there is at least one basis;

  2. (2)

(the Exchange Axiom): if $A,B$ are bases and $a\in A\setminus B,$ then there
exists $b\in B\setminus A$ such that $(A\setminus\\{a\\})\cup\\{b\\}$ is a
basis.

It follows from the Exchange Axiom that any two bases have the same number of
elements; that is, the basis hypergraph is uniform, i.e. all the hyperedges
have the same size. So if the global generating graph of a finite group $G$ is
the basis hypergraph of a matroid, then $\Delta(G)=\Gamma(G).$ The authors of
[5] asked the following question:

######  Question 6.

Is it possible to describe groups whose generating hypergraph is the basis
hypergraph of a matroid?

Motivated by the previous questions, we want to study the finite groups $G$
which satisfy the following property: if $G=\langle
x_{1},\dots,x_{d(G)}\rangle=\langle y_{1},\dots,y_{d(G)}\rangle,$ then for
every $1\leq i\leq d(G),$ there exists $j$ such that

$\langle x_{1},\dots,x_{i-1},y_{j},x_{i+1},\dots,x_{d(G)}\rangle=G.$

We call this property the ‘minimal generating set exchange property’ (MGSE
property). If the previous property fails for the two generating sets
$X=\\{x_{1},\dots,x_{d}\\}$ and $X=\\{y_{1},\dots,y_{d}\\}$ we will say that
$X$ and $Y$ fail the MGSE property.

We start our investigation with the following elementary observation.

######  Lemma 7.

Let $G$ be a finite group. Then $G$ satisfies the MGSE property if and only if
$G/\operatorname{Frat}(G)$ satisfies the MGSE property.

We will use the following result by Gaschütz [13] to prove that the MGSE
property is inherited by the quotients.

######  Lemma 8.

Let $N$ be a normal subgroup of $G$ and $\langle
g_{1}N,\dots,g_{r}N\rangle=G/N.$ If $r\geq d(G),$ then we can find $u_{1}\dots
u_{r}$ in $N$ so that $\langle g_{1}u_{1},\dots,g_{r}u_{r}\rangle=G.$

######  Lemma 9.

Let $G$ be a finite group. If $G$ satisfies the MGSE propery, then $G/N$
satisfies MGSE property for every normal subgroup $N$ of $G.$

###### Proof.

Let $N\unlhd G,$ $u=d(G/N),v=d(G).$ Suppose that the two minimal generating
sets $\tilde{X}=\\{x_{1}N,\dots,x_{u}N\\}$ and
$\tilde{Y}=\\{y_{1}N,\dots,y_{u}N\\}$ fail the MGSE property. We may assume
that $\\{y_{j}N,x_{2}N,\dots,x_{u}N\\}\neq G/N$ for every $1\leq j\leq u.$ By
Lemma 8, there exist $m_{1},\dots,m_{v},n_{1},\dots,n_{v}\in N,$ such that

$G=\langle x_{1}m_{1},\dots,x_{u}m_{u},m_{u+1},\dots,m_{v}\rangle=\langle
y_{1}n_{1},\dots,y_{u}n_{u},n_{u+1},\dots,n_{v}\rangle.$

We claim that the minimal generating sets

$X=\\{x_{1}m_{1},\dots,x_{u}m_{u},m_{u+1},\dots,m_{v}\\}\text{ and
}Y=\\{y_{1}n_{1},\dots,y_{u}n_{u},n_{u+1},\dots,n_{v}\\}$

of $G$ fail the MGSE property. Indeed, for every $y\in Y,$

$\langle yN,x_{2}m_{2}N,\dots,x_{u}m_{u}N,m_{u+1}N,\dots,m_{v}N\rangle=\langle
yN,x_{2}N,\dots,x_{u}N\rangle\neq G/N.\qed$

By [5, Theorem 5.1], a finite $p$-group satisfies the MGSE property. We are
going to prove that this is the unique case in which a non-cyclic finite
nilpotent group satisfies the MGSE property.

######  Lemma 10.

Let $G$ be a non-cyclic finite group which satisfies the MGSE property. If $N$
is a normal subgroup of $G$ and $G/N$ is cyclic, then $G/N$ is a $p$-group. In
particular $G/G^{\prime}$ is a $p$-group.

###### Proof.

Suppose, by contradiction, that $G/N=\langle gN\rangle$ and that $|gN|$ is not
a prime-power. Then there exist $g_{1},g_{2}\in G$ such that $g=g_{1}g_{2}$
and neither $g_{1}N$ nor $g_{2}N$ generates $G/N.$ Let $d=d(G).$ By Lemma 8,
there exist $m_{1},\dots,m_{d},n_{1},\dots,n_{d}\in N$ such that

$G=\langle gm_{1},m_{2},\dots,m_{d}\rangle=\langle
g_{1}n_{1},g_{2}n_{2},n_{3},\dots,n_{d}\rangle.$

Then $A=\\{gm_{1},m_{2},\dots,m_{d}\\}$ and
$B=\\{g_{1}n_{1},g_{2}n_{2},n_{3},\dots,n_{d}\\}$ fail the MGSE property.
Indeed there is no $b\in B$ such that $G=\langle b,m_{2},\dots,m_{d}\rangle.$
By Lemma 9 this contradicts the fact that $G$ satisfies the MGSE property. ∎

######  Corollary 11.

Let $G$ be a finite non-cyclic finite nilpotent group. Then $G$ satisfies the
MGSE property if and only if $G$ is a $p$-group.

###### Proof.

It is easy to see that a finite $p$-group satisfies the MGSP propery (see [5,
Theorem 5.1]). Conversely let $G$ be a finite non-cyclic nilpotent group which
satisfies the MGSE property. By Lemmas 9 and 10 $G/G^{\prime}$ is a $p$-group.
This implies that $G$ itself is a $p$-group. ∎

The next results aim to obtain a complete classification of the finite
solvable groups satisfying the MGSE property.

######  Lemma 12.

Let $G$ be a 2-generated solvable non-nilpotent group. If $G$ satisfies the
MGSE property, then $G/\operatorname{Frat}(G)\cong V\rtimes\langle x\rangle,$
where $x$ has prime order and $V$ is a faithful irreducible $\langle
x\rangle$-module.

###### Proof.

Let $G$ be a 2-generated non-nilpotent solvable group. By [25, Theorem 1.7]
either $G/\operatorname{Frat}(G)\cong V\rtimes\langle x\rangle,$ where $x$ has
prime order and $V$ is a faithful irreducible $\langle x\rangle$-module, or
the generating graph $\Gamma(G)$ of $G$ is not a cograph. In the second case,
$\Gamma(G)$ contains four vertices $x_{1},x_{2},x_{3},x_{4}$ such that the
subgroup of $\Gamma(G)$ induced by them is the the four-vertex path
$x_{1}-x_{2}-x_{3}-x_{4}.$ This implies that $A=\\{x_{1},x_{2}\\}$ and
$B=\\{x_{3},x_{4}\\}$ fail the MGSE property, since there is no $b\in A$ such
that $\langle x_{1},b\rangle=G.$ ∎

######  Lemma 13.

Assume that $H$ is a non-cyclic finite solvable group and let $V$ be a
faithful irreducible $H$-module. Then $G=V\rtimes H$ does not satisfy the MGSE
property.

###### Proof.

Let $d=d(H).$ By the main theorem in [22], $d(G)=d(H).$ Assume $H=\langle
h_{1},\dots,h_{d}\rangle.$ By [23, Lemma 2], it is not restrictive to assume
that there exists $n\in N$ such that $G=\langle
h_{1}n_{1},h_{2},\dots,h_{d}\rangle.$ Moreover, by [24, Proposition 2.2] and
its proof, there exist $n_{2},\dots,n_{d}\in N$ such that $G=\langle
h_{1},h_{2}n_{2},\dots,h_{d}n_{d}\rangle.$ We claim that the generating sets
$X=\\{h_{1}n_{1},h_{2},\dots,h_{d}\\}$ and
$Y=\\{h_{1},h_{2}n_{2},\dots,h_{d}n_{d}\\}$ fail the MGSEP property. Indeed
assume that there exists $y\in Y$ such that $\langle
y,h_{2},\dots,h_{d}\rangle=G.$ Since $\langle h_{1},\dots,h_{d}\rangle=H<G,$
it must be $y=h_{i}n_{i}$ for some $2\leq i\leq d.$ But this would implies
$\langle h_{i}n_{i},h_{2},\dots,h_{d}\rangle\leq\langle
h_{2},\dots,h_{d}\rangle N<HN=G.$ ∎

######  Lemma 14.

Let $G$ be a finite non-nilpotent solvable group. If $G$ satisfies the MGSE
property, then $G/\operatorname{Frat}(G)\cong N^{\delta}\rtimes H,$ where $H$
is cyclic of prime order, $N$ is an irreducible $H$-module and $C_{H}(V)=1.$

###### Proof.

It follows from Lemma 7 and the fact that $G$ is nilpotent if and only if
$G/\operatorname{Frat}(G)$ is nilpotent, that we may assume
$\operatorname{Frat}(G)=1.$

But then we may write $\operatorname{Fit}(G)=N_{1}\times\dots\times N_{t}$ as
a product of abelian minimal normal subgroups of $G.$ Since
$\operatorname{Frat}(G)=1,$ $\operatorname{Fit}(G)$ has a complement $H$ in
$G.$ Let $C_{i}=C_{H}(N_{i})$ and $M_{i}=\prod_{i\neq j}N_{j}.$ Then
$M_{i}C_{i}=C_{G}(N_{i})$ is a normal sugroup of $G$ and $G/M_{i}C_{i}\cong
N_{i}\rtimes H/C_{i}$. By Lemma 13, $H/C_{i}$ is cyclic. Since
$C_{G}(\operatorname{Fit}(G))=\operatorname{Fit}(G),$

$H\cong\frac{G}{\operatorname{Fit}(G)}\cong\frac{G}{\bigcap_{1\leq i\leq
t}C_{G}(N_{i})}\leq\prod_{1\leq i\leq
t}\frac{G}{C_{G}(N_{i})}\cong\prod_{1\leq i\leq t}\frac{H}{C_{i}}.$

Hence $H$ is abelian and it follows from Lemma 10 that $H$ is a $p$-group.
There exists $1\leq i\leq t$ such that $[H,N_{i}]\neq 1$ (otherwise $G$ would
be abelian and consequently $G=\operatorname{Fit}(G))$. This implies in
particular $(|N_{i}|,p)=(|N_{i}|,|H|)=1.$ As we noticed before, $H/C_{i}$ is
cyclic, so we may assume $H=\langle h_{1},h_{2},\dots,h_{u}\rangle$ with
$h_{j}\in C_{i}$ if $j\geq 2.$ Let $X=N_{i}H$ and $1\neq n\in N.$ Notice that,
since $(|C_{i}|,|N_{i}|)=1,$ $\langle hm\rangle=\langle h,m\rangle$ for every
$h\in H$ and $m\in N.$ In particular, if $u:=d(H)\geq 3,$ then
$A=\\{h_{1},\dots,x_{u-2},h_{u-1}n,h_{u}\\}$ and
$B=\\{h_{1},\dots,x_{h-2},h_{u-1},h_{u}n\\}$ are two minimal generating sets
of $X$ which fail the MGSE property, since there is no $b\in B$ such that
$G=\langle h_{1},\dots,h_{u-2},b,h_{u}\rangle$. Since $X$ in an epimorphic
image $G$, it follows from Lemma 9 that the assumption $u\geq 3$ leads to a
contradiction. Hence $d(H)\leq 2.$

Let $J$ be a subset of $I=\\{1,\dots,t\\}$ with the property that for any
$i\in I$ there exists one and only one $j\in J$ such that $N_{i}$ is
$H$-isomorphic to $N_{j}.$ Let $Y=(\prod_{j\in J}N_{j})H.$ By Lemma 9, $Y$
satisfies the MGSE property. The maximal subgroups of $Y$ are:

  1. (1)

$(\prod_{j\in J})M_{j}\operatorname{Frat}(H);$

  2. (2)

$(\prod_{j\neq k}M_{j})H^{y}$ with $k\in J$ and $y\in M_{j}.$

This implies that

$\operatorname{Frat}(Y)=\bigcap_{j\in
J}C_{\operatorname{Frat}(H)}(N_{j})=\bigcap_{i\in
I}C_{\operatorname{Frat}(H)}(N_{i})=\operatorname{Frat}(G)=1.$

Moreover it follows from [14, Satz 2 and Satz 3] that $d(Y)=2.$ But then we
may deduce from Lemma 12 that $|J|=1$ and $|H|=p.$ ∎

######  Lemma 15.

Let $V$ be a faithful irreducible $\langle x\rangle$-module with $|x|=p$ a
prime. Then the semidirect product $G=V^{\delta}\rtimes\langle x\rangle$
satisfies the MGSE property.

###### Proof.

We may identify $V$ with the additive group of a finite field $F$ and $x$ with
an element of order $p$ of the multiplicative group of $F.$ Notice that
$d(G)=\delta+1.$ Moreover it follows from [19, Proposition 2.1 and 2.2] that

$\langle(v_{1,1},\dots,v_{1,\delta+1})x_{1},\dots,(v_{\delta+1,1},\dots,v_{\delta+1,\delta+1})x_{\delta+1}\rangle=G$

if and only if

$\det\begin{pmatrix}x_{1}-1&\cdots&x_{\delta+1}-1\\\
v_{1,1}&\cdots&v_{\delta+1,1}\\\ \vdots&\vdots&\vdots\\\
v_{1,\delta+1}&\cdots&v_{\delta+1,\delta+1}\end{pmatrix}\neq 0.$

In particular, to prove that two generating sets

$\displaystyle
X_{1}=\\{(v_{1,1,1},\dots,v_{1,\delta+1,1})x_{1,1},\dots,(v_{1,\delta+1,1},\dots,v_{1,\delta+1,1})x_{1,\delta+1}\\}$
$\displaystyle
X_{2}=\\{(v_{2,1,1},\dots,v_{2,\delta+1,1})x_{2,1},\dots,(v_{2,\delta+1,1},\dots,v_{2,\delta+1,1})x_{2,\delta+1}\\}$

satisfy the MGSE property it suffices to notice that, given the two-matrices

$A_{1}=\begin{pmatrix}x_{1,1}-1&\cdots&x_{1,\delta+1}-1\\\
v_{1,1,1}&\cdots&v_{1,\delta+1,1}\\\ \vdots&\vdots&\vdots\\\
v_{1,1,\delta+1}&\cdots&v_{1,\delta+1,\delta+1}\end{pmatrix},\quad
A_{2}=\begin{pmatrix}x_{2,1}-1&\cdots&x_{2,\delta+1}-1\\\
v_{2,1,1}&\cdots&v_{2,\delta+1,1}\\\ \vdots&\vdots&\vdots\\\
v_{2,1,\delta+1}&\cdots&v_{2,\delta+1,\delta+1}\end{pmatrix},$

for any $i\in\\{1,\dots,\delta+1\\}$ there exists $j\in\\{1,\dots,\delta+1\\}$
such that the matrix obtained replacing the $i$-th column of $A_{1}$ with the
$j$-th column of $A_{2}$ is still invertible. ∎

We may summarize the results obtained in this section in the following
statement:

######  Theorem 16.

A non-cyclic finite solvable group $G$ satisfies the MGSE property if and only
if $G/\operatorname{Frat}(G)\cong N^{\delta}\rtimes H,$ where $H$ is cyclic of
prime order, $N$ is an irreducible $H$-module and $C_{H}(V)=1.$

Combining the previous theorem with the main result of [1], it turns out that
if a finite group $G$ satisfies the MGSE property, then all the minimal
generating sets of $G$ have the same size, or equivalently
$\Delta(G)=\Gamma(G).$ However the converse is not true. For example, let $G$
be the solvable subgroup of $\operatorname{Sym}(5)$ generated by $x=(2,3,4,5)$
and $y=(1,2,3,5,4).$ Then all the minimal generating sets of $G$ has size $2,$
however $A=\\{x^{2},xy\\}$ and $B=\\{x,y\\}$ are two generating sets that
fails the MGSE property, since $\langle x^{2},x\rangle$ and $\langle
x^{2},y\rangle$ are proper subgroups of $G$.

We conjecture that a finite group which satisfies the MGSE property must be
solvable. The following is a partial result supporting this conjecture.

######  Theorem 17.

Let $G$ be a non-nilpotent finite group. If $G$ satisfies the MGSE property,
then $G$ contains a unique maximal normal subgroup, say $N$, and $G/N$ is
cyclic of order $p$. In particular $G$ is non-perfect and $G/G^{\prime}$ is a
cyclic $p$-group.

###### Proof.

By Lemmas 9 and 10, it suffices to prove that a finite non-abelian simple
group does not satisfies the MGSE property. This follows from the fact that
the generating graph of a finite non-abelian simple group contains a 4-path
[25, Corollary 1.10]. ∎

## References

  * [1] P. Apisa and B. Klopsch, _A generalization of the Burnside basis theorem_ , J. Algebra 400 (2014), 8–16.
  * [2] T. Breuer, R. M. Guralnick, A. Lucchini, A. Maróti and G. P. Nagy, _Hamiltonian cycles in the generating graphs of finite groups_ , Bull. London Math. Soc. 42 (2010), 621–633.
  * [3] T. Burness and E. Crestani, _On the generating graph of direct powers of a simple group_ , J. Algebraic Combin. 38 (2013), no. 2, 329–350.
  * [4] T. Burness, R. Guralnick and S. Harper, _The spread of a finite group_ , Ann. of Math. (2) 193 (2021), no. 2, 619–687.
  * [5] P. Cameron, A. Lakshmanan S. and M. V. Ajith, _Hypergraphs defined on algebraic structures_ , arXiv:2303.00546.
  * [6] E. Damian and A. Lucchini, _The probabilistic zeta function of finite simple groups_ , J. Algebra 313 (2007), no. 2, 957–971.
  * [7] P. Cameron, A. Lucchini, C. Roney-Dougal, _Generating sets of finite groups_ , Trans. Amer. Math. Soc. 370 (2018), no. 9, 6751–6770.
  * [8] E. Crestani and A. Lucchini, _The generating graph of a finite soluble groups_ , Israel J. Math. 207 (2015), no. 2, 739–761.
  * [9] E. Crestani and A. Lucchini, _The non-isolated vertices in the generating graph of a direct powers of simple groups_ , J. Algebraic Combin. 37 (2013), no. 2, 249–263.
  * [10] E. Damian and A. Lucchini, _Finite groups with p-multiplicative probabilistic zeta function_ , Comm. Algebra 35 (2007), no. 11, 3451–3472.
  * [11] E. Detomi and A. Lucchini, _Recognizing soluble groups from their probabilistic zeta functions,_ Bull. London Math. Soc. 35 (2003), no. 5, 659–664.
  * [12] F. Erdem, _On the generating graphs of symmetric groups_ , J. Group Theory 21 (2018), no. 4, 629–649.
  * [13] W. Gaschütz, _Zu einem von B. H. und H. Neumann gestellten Problem_ , Math. Nachr. 14 (1955), no. 4–6, 249–252.
  * [14] W. Gaschütz, _Die Eulersche Funktion endlicher auflösbarer Gruppen_ , Illinois J. Math. 3 (1959), 469–476 .
  * [15] P. Hall, _The eulerian functions of a group_ , Quart. J. Math. (1936), no. 7, 134–151.
  * [16] W. Kimmerle, R. Lyons, R. Sandling and D. N. Teague, _Composition factors from the group ring and Artin’s theorem on orders of simple groups_ , Proc. Lond. Math. Soc. (3) 60 (1990), 89–122.
  * [17] M. Liebeck and A. Shalev, _Simple groups, probabilistic methods, and a conjecture of Kantor and Lubotzky_ , J. Algebra 184 (1996), no. 1, 31–57.
  * [18] A. Lucchini,_The independence graph of a finite group_ , Monatsh. Math. 193 (2020), no. 4, 845–856.
  * [19] A. Lucchini and A. Maróti, _On the clique number of the generating graph of a finite group_ , Proc. Amer. Math. Soc. 137, No. 10, (2009), 3207–3217.
  * [20] A. Lucchini and A. Maróti, _Some results and questions related to the generating graph of a finite group_ , in Ischia group theory 2008, 183–208, World Sci. Publ., Hackensack, NJ, 2009.
  * [21] A. Lucchini, A. Maróti and C. Roney-Dougal, _On the generating graph of a simple group_ , J. Aust. Math. Soc. 103 (2017), no. 1, 91–103.
  * [22] A. Lucchini and F. Menegazzo, _Generators for finite groups with a unique minimal normal subgroup_ , Rend. Sem. Mat. Univ. Padova 98 (1997), 173–191.
  * [23] A. Lucchini and F. Menegazzo, _Computing a set of generators of minimal cardinality in a solvable group_ , J. Symbolic Comput. 17 (1994), no. 5, 409–420.
  * [24] A. Lucchini and D. Nemmi, _The non- $\mathfrak{F}$ graph of a finite group_, Math. Nachr. 294 (2021), no. 10, 1912–1921.
  * [25] A. Lucchini and D. Nemmi, _Forbidden subgraphs in generating graphs of finite groups_ , Algebr. Comb. 5 (2022), no. 5, 925–946.
  * [26] A. Lucchini and D. Nemmi, _Connectedness of the rank graph of a finite group_ , in preparation.


# CodeLens: An Interactive Tool for Visualizing Code Representations ††thanks:
This work is funded by the European Union’s Horizon Research and Innovation
Programme under Grant Agreement n∘ 101070303.

1st Yuejun Guo  IT for Innovative Services (ITIS)
Luxembourg Institute of Science and Technology (LIST)
Luxembourg
<EMAIL_ADDRESS>2nd Seifeddine Bettaieb  IT for Innovative Services (ITIS)
Luxembourg Institute of Science and Technology (LIST)
Luxembourg
<EMAIL_ADDRESS>3rd Qiang Hu  SnT
University of Luxembourg
Luxembourg
<EMAIL_ADDRESS>4th Yves Le Traon  SnT
University of Luxembourg
Luxembourg
<EMAIL_ADDRESS>5th Qiang Tang  IT for Innovative Services (ITIS)
Luxembourg Institute of Science and Technology (LIST)
Luxembourg
<EMAIL_ADDRESS>
###### Abstract

Representing source code in a generic input format is crucial to automate
software engineering tasks, e.g., applying machine learning algorithms to
extract information. Visualizing code representations can further enable human
experts to gain an intuitive insight into the code. Unfortunately, as of
today, there is no universal tool that can simultaneously visualise different
types of code representations. In this paper, we introduce a tool, CodeLens,
which provides a visual interaction environment that supports various
representation methods and helps developers understand and explore them.
CodeLens is designed to support multiple programming languages, such as Java,
Python, and JavaScript, and four types of code representations, including
sequence of tokens, abstract syntax tree (AST), data flow graph (DFG), and
control flow graph (CFG). By using CodeLens, developers can quickly visualize
the specific code representation and also obtain the represented inputs for
models of code. The Web-based interface of CodeLens is available at
http://www.codelens.org/. The demonstration video can be found at
http://www.codelens.org/demo.

###### Index Terms:

code representation, interactive visualization

##  I Introduction

The development of machine learning (ML) has enabled the automation of a wide
range of Software Engineering (SE) tasks [1]. For example, large language
models (LLMs), e.g., CodeBERT [2] and CodeX [3], have proven to achieve the
state-of-the-art performance in clone detection, vulnerability detection, and
code generation. One prerequisite to using ML models is the code
representation [4], which involves the transformation of source code into
analyzable data by the ML models.

In the domain of SE, different code representations have been developed and
studied, such as the text-based sequence of tokens [2], tree-based abstract
syntax tree (AST) [5, 6], graph-based data flow graph (DFG) [7, 8] and control
flow graph (CFG) [9]. Before adopting code representations for downstream
tasks, human experts often need to interpret them so that proper actions can
be taken. Without visualization, interpretation is a challenging task even for
experienced developers. In addition, when using these representations (e.g.,
AST and CFG) in ML models, complex parsing libraries and toolkits are required
to be installed to process source code. For example, to convert source code to
the AST format, there are the tree-sitter [10] for multiple programming
languages, Joern [11] for C/C++, and Python parser [12] for Python. Installing
and understanding all these libraries can be time-consuming and complex, as a
result, the whole process of code learning can not be easily automated. An
additional challenge is that there is no library for some formats such as DFG
and CFG.

TABLE I: Comparison between CodeLens and existing code visualization tools.

Tool name | Support language | Support representation | Visualization type | Download type
---|---|---|---|---
AST Visualization on browser [13] | JavaScript | AST | Graph | Image, JSON
Java Parser [14] | Java | AST | - | JSON
code2seq [6] | Java | AST | Graph | Image
Code2flow [15] | Unknown | - | Graph | Image
Swift AST Explorer [16] | Swift | AST | Text | -
JavaScript AST Visualiser [17] | JavaScript | Sequence of tokens, AST | Text | Image
code2vec [5] | Java | AST | Graph | Image
CodeLens |  | Java, Python,
---
JavaScript
| Sequence of tokens, AST,
---
DFG, CFG
Text, graph | Image, JSON

In the literature, several tools have been proposed to visualize code
representations and help developers understand code. A comparison of them is
shown in Table I. Among them, those from [13, 6, 15] receive source code as
input and then visualize it as an AST graph. Such graphs can be downloaded for
further analysis. Besides, the Java Parser from [14] can transfer Java code to
AST with JSON format for understanding Java programs. Other tools such as [16,
17] can transfer and visualize programs as the text of tokens or ASTs.
However, there are a few limitations w.r.t. the existing tools: 1) they can
only support one specific programming language (e.g., Java or JavaScript), 2)
they only support one visualization type (e.g., graph or text), and 3) after
analyzing code, only one format of data can be downloaded (image or JSON).
These issues seriously limit the usage of these tools in practical deployment.

To address these limitations, in this paper, we introduce CodeLens, an
interactive tool for visualizing different code representations for different
programming languages. In more detail, CodeLens supports three popular
programming languages, including Java, Python, and JavaScript. It supports
four types of code representation, including sequence of tokens, AST, DFG, and
CFG. To our knowledge, this is the first tool that supports visualization of
both DFG and CFG. Furthermore, CodeLens supports two types of visualization,
i.e., text and graph, and provides two formats of outputs, i.e., image data
and JSON files, which save all the represented code information and can be
downloaded for further usage. In the evaluation part, we demonstrate the
usefulness of CodeLens with two straightforward use cases, 1) visualizing
different types of code representations to help users understand code
intuitively, and 2) providing different types of pre-processed inputs for
machine learning models. It is worth noting that CodeLens can be used in many
other use cases by providing the necessary input for different code analysis
tasks. Due to the space limitation, we omit the details in this paper.

##  II CodeVis Overview

Figure 1 provides a comprehensive overview of the CodeLens architecture, which
consists of a Web-based frontend (written in JavaScript using React) and a
server-side backend (written in Python) connected through the Flask
microframework. The frontend (client) provides a user-friendly interface,
allowing developers and users to interact with different code representations
seamlessly. The backend (server) of CodeLens plays a crucial role in
processing code and generating graphical code representations of different
formats.

Figure 1: Architecture of CodeLens.

###  II-A User Interface

The user interface prioritizes simplicity, incorporating two distinct boxes.
On the left-hand side, users are provided with a console-like interactive
environment where they can input their code. To cater to the diverse
programming preferences of users, our interface offers a selection of three
programming languages: Python, JavaScript, and Java. Within each language
category, users can explore and experiment with five different code examples,
providing them ample opportunities for practice. On the right-hand side, users
can visualize or download the resulting output, ensuring a comprehensive
understanding of the code’s execution.

To facilitate efficient processing, a Convert button is positioned between the
two boxes, enabling users to initiate the transformation of their input. For a
visual depiction of this intuitive interface, please refer to Figure 2.

Figure 2: User interface design of CodeLens.

###  II-B Back-End Implementation

The backend of CodeLens implements the transformations from source code (i.e.,
Java, Python, and JavaScript) to code representations (i.e., text-based
sequence of tokens, AST, DFG, CFG).

#### Sequence of tokens

A source code is treated as plain text and processed into a linear sequence of
tokens via a tokenizer. Each line of code is chopped into pieces by looking
for the whitespace (tabs, spaces, newlines). Each piece is finally represented
by an integer that refers to the ID of the piece in a so-called vocabulary. A
piece can be a word, a subword, or a character depending on different
tokenizers [18]. The subword-based tokenizer, Byte-Pair Encoding (BPE) [19] is
implemented in CodeLens due to its popularity in code-related DL models.

#### Abstract syntax tree (AST)

An AST is a tree representation of the abstract syntactic structure of a piece
of source code. Each node in the tree represents a construct occurring in the
source code. When converting a piece of source code to an AST, only structural
information is preserved, such as variable types, order and definition of
executable statements, and identifiers. In CodeLens, the tree-sitter[10]
library is used to parse source code in different programming languages.

#### Data flow graph (DFG)

As the name suggests, DFG [7] is a data-oriented graph representation that
shows the flow of data through a piece of source code. In a DFG, each node
represents a variable or an expression, and each edge represents the flow of
data between them. In CodeLens, the DFG is extracted from the AST of the given
source code by tracing the variable or expression statement according to the
programming grammar in the underlying programming language.

#### Control flow graph (CFG)

Similar to DFG, CFG [9] is a graph-based representation. While CFG is process-
oriented, it represents all paths that might be traversed through the
execution. In a CFG, nodes portray basic blocks of statements and conditions,
and edges describe the transfer of control and subsequent access or
modification onto the same variable. For instance, a for-loop is a basic
control flow statement for specifying iteration. Note that, a CFG includes two
designated blocks, an entry block and an exit block where the control enters
and leaves the flow. In CodeLens, the CFG is extracted from the AST of the
given source code by tracing all control statements defined in the underlying
programming language.

##  III Use Cases

In this section, we present two use cases to demonstrate the usage of
CodeLens.

Figure 3: Example of a Java DFG visualized by CodeLens.

#### Code representation visualization

The first usage of CodeLens is to visualize code representation. CodeLens
receives raw code snippets and then draws the code representations in the
right panel as shown in Figure 3. The figures can be downloaded into different
formats for further analysis. For example, a user can use them to check the
change of representation after the change of code snippets or to compare two
representations of two programs.

Figure 4: An example of transformed code data that can be used for tokenizer.

#### Inputs to ML models extraction

In addition to representation visualization, CodeLens also supports producing
pre-processed inputs for ML models. This means that users can easily test
their machine-learning models of code without preparing other packages like
Java/Python Parser. As shown in Figure 4, the transformed code data (e.g.,
tokens, AST) can be downloaded and fed to the tokenizer provided by pre-
trained code models, for example, CodeBERT [2].

##  IV Related Work

#### Code representations in ML models

Machine learning (ML), particularly deep learning (DL), models have been
proven successful in automating various software engineering tasks, such as
problem classification [20], clone detection [21], and vulnerability detection
[22]. Code representation is a preliminary step to convert source code into a
readable format for all models. Among existing code representations, the
representation of a sequence of tokens is mostly used in large language models
(LLMs) for code that supports multiple downstream tasks. For example, CodeBERT
[2], CodeT5 [23], and CodeX [3] take the sequence of tokens of source code by
the BPE tokenizer as input. In addition to the sequence of tokens by the BPE
tokenizer, GraphCodeBERT [7] adds the data flow graph (DFG) representation of
source code to capture the relation of “where-the-value-comes-from” between
variables. The task-specific GraphSearchNet [8] model also considers the DFG
representation of source code to undertake the code search task. code2seq [6]
and code2vec [5] extract a set of syntactic paths from the AST representation
of source code.

#### Online tools for code visualization

Multiple tools with Web-based interface are available, such as the AST
Visualization on browser [13] and Java Parser [14]. However, as shown in the
comparison in Table I, these tools have four main limitations. First, only one
programming language is supported. For example, Java Parser [14], code2seq
[6], and code2vec [5] only support Java. Second, the support code
representation mainly focuses on AST. None of the seven tools support graph-
based representation. Third, the visualization type is limited. Visualizing
the nodes and edges of an AST in a tree diagram is intuitive but challenging.
The Swift AST Explorer [16] and JavaScript AST Visualiser [17] simply
visualize an AST in a tree structure, which is less helpful to understand the
source code. Last, the output of most tools is limited to images. If a
developer is willing to use the representation, e.g., AST generated by a tool,
a JSON file recording the nodes and edges should be provided. In contrast,
CodeLens has addressed all four limitations.

##  V Conclusion

In this paper, we have introduced an interactive tool named CodeLens, which
visualizes four most popular code representations widely used by machine
learning (ML) models, including sequence of tokens, AST, DFG, and CFG. The
tool allows software and application developers to understand how source code
is represented when applying ML models to automate software engineering tasks.
In addition, it can also serve as an interface between source code and numeral
code representations in ML models. This eliminates the necessity for
developers to install complex parsing libraries and toolkits, through making
the code representation process more user-friendly.

CodeLens opens many directions for future work. For example, CodeLens can be
extended to support more programming languages (e.g., C, C++ and PHP) and
other useful code representations. Another direction is to develop
applications on the basis of CodeLens, e.g., integrating a vulnerability
detection module into CodeLens to perform vulnerability detection tasks
without the need to pre-processing the code in advance.

## Acknowledgment

An experienced developer Bowen Liu (who is currently working on ML-based
malware detection) was invited to test CodeLens. We thank him for his valuable
feedback.

## References

  * [1] S. Lu, D. Guo, S. Ren, J. Huang, A. Svyatkovskiy, A. Blanco, C. B. Clement, D. Drain, D. Jiang, D. Tang, G. Li, L. Zhou, L. Shou, L. Zhou, M. Tufano, M. Gong, M. Zhou, N. Duan, N. Sundaresan, S. K. Deng, S. Fu, and S. Liu, “Codexglue: a machine learning benchmark dataset for code understanding and generation,” in _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track_. OpenReview.net, 2021. [Online]. Available: https://openreview.net/pdf?id=6lE4dQXaUcb
  * [2] Z. Feng, D. Guo, D. Tang, N. Duan, X. Feng, M. Gong, L. Shou, B. Qin, T. Liu, D. Jiang, and M. Zhou, “Codebert: a pre-trained model for programming and natural languages,” pp. 1536–1547, November 2020. [Online]. Available: https://aclanthology.org/2020.findings-emnlp.139
  * [3] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. de Oliveira Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, A. Ray, R. Puri, G. Krueger, M. Petrov, H. Khlaaf, G. Sastry, P. Mishkin, B. Chan, S. Gray, N. Ryder, M. Pavlov, A. Power, L. Kaiser, M. Bavarian, C. Winter, P. Tillet, F. P. Such, D. Cummings, M. Plappert, F. Chantzis, E. Barnes, A. Herbert-Voss, W. H. Guss, A. Nichol, A. Paino, N. Tezak, J. Tang, I. Babuschkin, S. Balaji, S. Jain, W. Saunders, C. Hesse, A. N. Carr, J. Leike, J. Achiam, V. Misra, E. Morikawa, A. Radford, M. Knight, M. Brundage, M. Murati, K. Mayer, P. Welinder, B. McGrew, D. Amodei, S. McCandlish, I. Sutskever, and W. Zaremba, “Evaluating large language models trained on code,” 2021. [Online]. Available: https://arxiv.org/abs/2107.03374
  * [4] H. P. Samoaa, F. Bayram, P. Salza, and P. Leitner, “A systematic mapping study of source code representation for deep learning in software engineering,” _IET Software_ , vol. 16, no. 4, pp. 351–385, 2022. [Online]. Available: https://ietresearch.onlinelibrary.wiley.com/doi/abs/10.1049/sfw2.12064
  * [5] U. Alon, M. Zilberstein, O. Levy, and E. Yahav, “Code2vec: learning distributed representations of code,” _Proceedings of the ACM on Programming Languages_ , vol. 3, no. POPL, January 2019. [Online]. Available: https://doi.org/10.1145/3290353
  * [6] U. Alon, O. Levy, and E. Yahav, “code2seq: generating sequences from structured representations of code,” in _International Conference on Learning Representations_ , 2019. [Online]. Available: https://openreview.net/forum?id=H1gKYo09tX
  * [7] D. Guo, S. Ren, S. Lu, Z. Feng, D. Tang, S. Liu, L. Zhou, N. Duan, A. Svyatkovskiy, S. Fu, M. Tufano, S. K. Deng, C. Clement, D. Drain, N. Sundaresan, J. Yin, D. Jiang, and M. Zhou, “Graphcodebert: pre-training code representations with data flow,” in _International Conference on Learning Representations (ICLR)_. OpenReview.net, 2021. [Online]. Available: https://openreview.net/forum?id=jLoC4ez43PZ
  * [8] S. Liu, X. Xie, L. Ma, J. K. Siow, and Y. Liu, “Graphsearchnet: enhancing gnns via capturing global dependency for semantic code search,” 2021. [Online]. Available: https://arxiv.org/abs/2111.02671
  * [9] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, _Compilers: principles, techniques, & tools (Second Edition)_. New York: Pearson Education Addison Wesly, 2007.
  * [10] M. Brunsfeld and P. Thomson, “Tree-sitter: a parser generator tool and an incremental parsing library,” 2023. [Online]. Available: https://tree-sitter.github.io/tree-sitter/
  * [11] “Joern - the bug hunter’s workbench,” https://joern.io/, 2023.
  * [12] “parser — access python parse trees,” https://docs.python.org/3.7/library/parser.html, 2023.
  * [13] N. Hirokazu, “Ast visualization on browser - realtime javascript abstract syntax tree visualisation,” 2012. [Online]. Available: http://nhiro.org/learn_language/AST-Visualization-on-browser.html
  * [14] O. Mazko, “Online java parser & abstract syntax tree demo,” 2016. [Online]. Available: https://mazko.github.io/jsjavaparser/
  * [15] I. Code Charm, “Code2flow - interactive code to flowchart converter,” 2022. [Online]. Available: https://code2flow.com/
  * [16] K. Katsumi, “Swift ast explorer - ast visualizer for swift source code,” 2023\. [Online]. Available: https://swift-ast-explorer.com/
  * [17] J. developers, “Javascript ast visualiser,” unk. [Online]. Available: https://www.jointjs.com/demos/abstract-syntax-tree
  * [18] S. J. Mielke, Z. Alyafeai, E. Salesky, C. Raffel, M. Dey, M. Gallé, A. Raja, C. Si, W. Y. Lee, B. Sagot, and S. Tan, “Between words and characters: a brief history of open-vocabulary modeling and tokenization in nlp,” 2021. [Online]. Available: https://arxiv.org/abs/2112.10508
  * [19] P. Gage, “A new algorithm for data compression,” _C Users Journal_ , vol. 12, no. 2, p. 23–38, February 1994.
  * [20] Q. Hu, Y. Guo, X. Xie, M. Cordy, L. Ma, M. Papadakis, and Y. Le Traon, “Codes: towards code model generalization under distribution shift,” in _International Conference on Software Engineering (ICSE): New Ideas and Emerging Results (NIER)_ , 2023.
  * [21] M. Zubkov, E. Spirin, E. Bogomolov, and T. Bryksin, “Evaluation of contrastive learning with various code representations for code clone detection,” arxiv, 2022\.
  * [22] Y. Zhou, S. Liu, J. Siow, X. Du, and Y. Liu, “Devign: effective vulnerability identification by learning comprehensive program semantics via graph neural networks,” in _Proceedings of the 33rd International Conference on Neural Information Processing Systems_. Red Hook, NY, USA: Curran Associates Inc., 2019.
  * [23] Y. Wang, W. Wang, S. Joty, and S. C. Hoi, “Codet5: identifier-aware unified pre-trained encoder-decoder models for code understanding and generation,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Online and Punta Cana, Dominican Republic: Association for Computational Linguistics, Nov. 2021, pp. 8696–8708. [Online]. Available: https://aclanthology.org/2021.emnlp-main.685


Power Plant Classification from Remote Imaging with Deep Learning
Michael Mommert, Linus Scheibenreif, Joëlle Hanna, Damian Borth
University of St. Gallen, Institute of Computer Science

Presented at the 2021 IEEE International Geoscience and Remote Sensing
Symposium (IGARSS).

###### Abstract

Satellite remote imaging enables the detailed study of land use patterns on a
global scale. We investigate the possibility to improve the information
content of traditional land use classification by identifying the nature of
industrial sites from medium-resolution remote sensing images. In this work,
we focus on classifying different types of power plants from Sentinel-2
imaging data. Using a ResNet-50 deep learning model, we are able to achieve a
mean accuracy of 90.0% in distinguishing 10 different power plant types and a
background class. Furthermore, we are able to identify the cooling mechanisms
utilized in thermal power plants with a mean accuracy of 87.5%. Our results
enable us to qualitatively investigate the energy mix from Sentinel-2 imaging
data, and prove the feasibility to classify industrial sites on a global scale
from freely available satellite imagery.

##  1 Introduction

The availability of satellite remote imaging data with global coverage and
high imaging cadence enable the detailed investigation of land use patterns
and changes therein. Land use classification creates a mapping of how land is
being utilized by humans; such information is highly valuable to better
understand socio-economic, environmental, and ecological problems and to
inform policy-makers. However, the value of land use information is limited by
both the spatial and categorical resolution of the data, the latter referring
to the level of detail utilized in the classification or segmentation.

We investigate the use of deep learning applied to satellite remote imaging to
identify the nature of industrial sites in an attempt to improve the level of
detail of land use classification maps. Previous works have successfully
combined both approaches for land use classification [1], to detect solar [2]
and wind power facilities [3], as well as oil and gas processing facilities
[4]. However, all these works rely on high-resolution remote imaging data,
which are typically associated with high cost and have a low imaging cadence.
In this work, we investigate the use of freely available medium-resolution and
high-cadence satellite imaging data to classify different types of power
plants as a test bed for a future application to industrial sites. This
application also addresses the topic of climate change mitigation by enabling
the qualitative analysis of the energy mix from satellite imagery.

##  2 Data Set

For this study, we select a total of 450 different power plant sites from the
JRC Open Power Plants Database (JRC-PPDB-OPEN, [5]), which in addition to
general power plant type information also provides approximate geolocation
data for each site. For each power plant class, we extract up to 50 different
sites for which we verify and improve geolocation data based on high-
resolution remote imaging data provided by the Google Maps service. Our
resulting sample contains the following power plant classes (nomenclature as
used in JRC-PPDB-OPEN, number in parentheses refer to the number of different
sites in the sample): “Fossil Brown coal/Lignite” (50), “Fossil Gas” (50),
“Fossil Hard Coal” (50), “Fossil Oil” (30), “Hydro Pumped Storage” (50),
“Hydro Run-of-river and poundage” (50), “Hydro Water Reservoir” (50),
“Nuclear” (50), “Solar” (20), “Wind Onshore” (50).

Images utilized in this work were acquired with the Multi-Spectral Imagers
(MSI) onboard the two Sentinel-2 Earth-observing satellites operated by the
European Space Agency. Both satellites observe the land surface of the Earth
in 13 bands covering the optical to short-wave infrared wavelengths at spatial
resolutions of 10 m to 60 m per pixel and with an imaging cadence of ${\geq}$5
days for most locations on Earth.

For each site, we download a total of 10 different and mostly cloud-free
Sentinel-2 rasters taken during 2020 to ensure proper coverage of seasonal and
other temporal changes in each site. Around each location, we crop a square
image region with an edge length of 1 km. We utilize only those MSI imaging
channels that do not focus on atmospheric features (bands 2, 3, 4, 5, 6, 7, 8,
8A, 11, and 12) and upsample all bands to the highest image resolution (10
m/pixel). We perform the same extraction procedure on 4 randomly selected
locations on each raster, resulting in our background images, which are used
as a control group to quantify the detectability of power plants against
random settings.

Our data set consists of 4,154 images of 450 different power plant sites
across Europe and 16,064 random background images. Example images are shown in
Figure 2.

##  3 Methods

Deep Neural Network approaches are well-suited to deal with the complexity
inherent to remote imaging data. We approach the multi-class classification
problems in this work with a ResNet-50 deep residual neural network [6] that
was slightly modified: the first convolutional layer takes in 10-channel input
images (see Section 2) and the final fully connected layer returns a number of
logits that is equal to the number of classes of the respective problem.
Furthermore, the first convolutional and maxpool layers have been modified to
use a 3$\times$3 kernel size and a stride of unity to enforce sensitivity to
small-scale structure in our images.

For all experiments we utilize stochastic gradient descent with momentum as
our optimizer. The learning is based on a cross entropy loss function. Our
deep learning methods are implemented utilizing PyTorch [7].

To boost the learning and results of our classifiers, we pretrain our models
on the EuroSAT dataset [8], which contains a sample of Sentinel-2 image
patches with corresponding land use classification labels.

We randomly split our data set on a per-image basis into a training,
validation, and test data set using a 80%/10%/10% split. Before provided to
the model for either training or evaluation, each image is normalized based on
the mean and standard deviation of each Sentinel-2/MSI band across all images.
Furthermore, random image flipping, mirroring, and rotations by integer
multiples of 90 degrees are applied to provide data augmentation. For each
epoch during training, validation, and testing, balanced samples are drawn
from the corresponding data sets, using either subsampling or oversampling
depending on the number of available images in each class.

##  4 Results

###  4.1 Power Plant Classification

We train our modified ResNet-50 architecture on the classification task
involving 10 different power plant classes (see Section 2) and a background
class. After tuning the hyperparameters of the model on the validation data
set, we evaluate the model performance on the test data set. We find an
overall accuracy over all classes of 90.0%; the accuracy of individual classes
varies between 77.4% for the background class and 97.5% for solar power
plants. Figure 1 shows the per-class accuracies and corresponding
uncertainties in detail. The accuracy variations between power plant types
correlate well with the presence or absence of unique feature that would
enable a clear identification.

Figure 1: Confusion matrix for the classification of 10 different power plant
classes (classes “Brown Coal”, “Gas”, “Hard Coal”, and “Oil” refer to fossil
fuel power plants, whereas “Run-of-River”, “Reservoir”, and “Pumped Storage”
refer to hydroelectric plants) and one background class. Values are accuracies
expressed as percentages. Uncertainties, derived as standard deviations across
ten different randomly drawn balanced samples from the test data set, are
quoted where significant. While most classes have high individual detection
accuracies, there are chances of confusion among the different hydroelectric
classes (see example images on the right) and the fossil fuel plant classes,
as well as between the renewable energy classes and the background class.

###  4.2 Power Plant Cooling Classification

Thermal power plants utilize different methods of cooling necessary for the
mechanical generation of power from steam. As provided by JRC-PPDB-OPEN, our
full data set contains 4 different cooling types among the thermal power
plants (all fossil fuel plants and nuclear plants): air cooling (29 examples),
mechanical draft tower (22 examples), natural draft tower (84 examples), once-
through cooling (90 examples). We ignore 5 examples of thermal power plants
that do not utilize active or passive cooling. The full data set of thermal
power plants includes 2,112 images.

We investigate the possibility to also classify the type of cooling used with
the same ResNet-50 architecture as outlined in Section 3. Utilizing the same
approach as introduced above, we train the model on the reduced data set of
thermal power plants and train against the 4 different target classes (see
above). We utilize the trained model from Section 4.1 as a pretrained model
for this task.

Our trained model achieves a mean accuracy of 87.5% over all cooling classes.
The individual class accuracies range from 70.0% for mechanical draft towers
to 99% for once-through cooling. This range is easily explainable as once-
through cooling systems require access to a water body that is readily
detectable, whereas mechanic draft towers can resemble other buildings and
structures.

##  5 Discussion and Conclusions

In order to verify that predictions made by our architecture are based on
salient features relevant to the classification task, we utilize Class
Activation Maps (CAM, [9]). CAMs highlight the most important image areas in
the model’s classification process. Examples, shown in Figure 2, show that
CAMs indeed focus on relevant image regions. For instance, coal-powered plants
are identified based on the presence of coal piles, oil and gas power plants
based on storage tanks, solar plants based on their unique shape and spectral
behavior, and hydroelectric plants based on the presence of gorges, water
bodies, and dam structures. In the case of the background class, activation
maps are typically more uniform than for power plant images due to the lack of
characteristic features.

We would like to point out that our results are based on a spatially limited
sample of power plants (all located in Europe), which is likely to have a
beneficial effect on our classification accuracies. For instance, brown coal
power plants in our sample are likely to be located in Eastern Europe, whereas
hydroelectric plants are mainly located in Scandinavia or the Alps. This
localization and its effect on site surroundings, but also similarities in the
design of plants, are likely to be learned by our model and are thus reflected
by its results.

Nevertheless, the results presented in this work underline the suitability of
medium-resolution remote imaging data to classify different power plant types,
providing the ability to estimate the energy mix in a given region. We
conclude that extending this classification method to other industrial sites
would be worthwhile and strongly improve the value of land use classification
information.

Figure 2: Image examples for all power plant types and the background class.
For each image pair, the left image shows an RGB image of the site, while the
right image shows the Class Activation Map (CAM, see Section 5) of the
corresponding class. All examples shown here have been identified correctly by
our model (see Section 4.1). In most cases, the most important image regions
for the classification (brightest region in the CAM) correlate well with
characteristic image features of the corresponding power plant type.

## References

  * [1] P. Zhang, Y. Ke, Z. Zhang, M. Wang, P. Li, and S. Zhang, “Urban land use and land cover classification using novel deep learning models based on high spatial resolution satellite imagery,” Sensors (Basel, Switzerland), vol. 18, 2018.
  * [2] J. Yu, Z. Wang, A. Majumdar, and R. Rajagopal, “Deepsolar: A machine learning framework to efficiently construct a solar deployment database in the united states,” Joule, vol. 2, pp. 2605–2617, 2018.
  * [3] S. Zhou, J. A. Irvin, Z. Wang, E. Zhang, J. Aljubran, W. Deadrick, and R. Rajagopal, “Deepwind: Weakly supervised localization of wind turbines in satellite imagery,” in Tackling Climate Change with Machine Learning, NeurIPS 2019, 2019.
  * [4] H. Sheng, J. Irvin, S. Munukutla, S. Zhang, C. T. Cross, K. Story, R. Rustowicz, C. W. Elsworth, Z. Yang, M. Omara, R. Gautam, R. B. Jackson, and A. Ng, “Ognet: Towards a global oil and gas infrastructure database using deep learning on remotely sensed imagery,” ArXiv, vol. abs/2011.07227, 2020.
  * [5] K. Kanellopoulos, M. D. Felice, I. H. Gonzalez, and A. Bocin, “Jrc open power plants database (jrc-ppdb-open),” Dec. 2019.
  * [6] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770–778, 2016.
  * [7] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” in NeurIPS, 2019.
  * [8] P. Helber, B. Bischke, A. Dengel, and D. Borth, “Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification,” IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 12, pp. 2217–2226, 2019.
  * [9] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba, “Learning deep features for discriminative localization,” 2015.