# Flurry: a Fast Framework for Reproducible Multi-layered Provenance Graph
Representation Learning

Maya Kapoor  Parsons CorporationUNC Charlotte<EMAIL_ADDRESS>,  Joshua
Melton  UNC Charlotte<EMAIL_ADDRESS>,  Michael Ridenhour  UNC Charlotte
<EMAIL_ADDRESS>,  Mahalavanya Sriram  UNC Charlotte<EMAIL_ADDRESS>,
Thomas Moyer  UNC Charlotte<EMAIL_ADDRESS>and  Siddharth Krishnan  UNC
Charlotte<EMAIL_ADDRESS>
###### Abstract.

Complex heterogeneous dynamic networks like knowledge graphs are powerful
constructs that can be used in modeling data provenance from computer systems.
From a security perspective, these attributed graphs enable causality analysis
and tracing for analyzing a myriad of cyberattacks. However, there is a
paucity in systematic development of pipelines that transform system
executions and provenance into usable graph representations for machine
learning tasks. This lack of instrumentation severely inhibits scientific
advancement in provenance graph machine learning by hindering reproducibility
and limiting the availability of data that are critical for techniques like
graph neural networks. To fulfill this need, we present Flurry, an end-to-end
data pipeline which simulates cyberattacks, captures provenance data from
these attacks at multiple system and application layers, converts audit logs
from these attacks into data provenance graphs, and incorporates this data
with a framework for training deep neural models that supports preconfigured
or custom-designed models for analysis in real-world resilient systems. We
showcase this pipeline by processing data from multiple system attacks and
performing anomaly detection via graph classification using current benchmark
graph representational learning frameworks. Flurry provides a fast,
customizable, extensible, and transparent solution for providing this much
needed data to cybersecurity professionals.

Graph Representation Learning, Data Provenance, Cyber Security, Complex
Systems

††conference: SIGKDD ’22: ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining; August 14-18, 2022; Washington, DC, USA††ccs:
Security and privacy Intrusion/anomaly detection and malware mitigation††ccs:
Computing methodologies Learning latent representations††ccs: Computing
methodologies Neural networks††ccs: Computer systems organization

##  1\. Introduction

The lineage or record of data modification, access, and usage, known as data
provenance, has been a long-standing tool for resilient cybersecurity systems
to use in attack tracing. Data may be sourced from multiple layers of a host,
including the kernel or operating system level, the application or data
layers, the browser layer, and the physical or virtualized file system. A
single host may produce several gigabytes of log data a day even at a coarse
level of provenance capture (Pasquier et al., 2017). With multiple host
systems generating intranet data over long periods of time, it is evident that
data provenance management and analysis is a big data problem.

Resilient systems use graph representations of data provenance in intrusion
and anomaly detection in order to perform attack tracing and to find causal
dependencies to form mitigation strategies used against all kinds of attacks.
Provenance graphs, often represented as heterogeneous networks, are comprised
of system entities and objects interconnected by a variety of interactions
generated from agents who affect changes in the system. Representing system
activity using knowledge graphs effectively captures the complex and multi-
faceted nature of system activity and lends itself to structural analysis by
graph machine learning algorithms, causal inference, and time series analysis
over dynamically generated networks. Unsupervised learning from the structure
of the network representation has allowed security specialists to detect even
zero-day attacks that have not been previously seen and therefore existing
supervised machine learning techniques lack the training data to effectively
identify such attack vectors (Han et al., 2021, 2020b). Additionally, the
ability of graph machine learning techniques to effectively scale up to web-
scale graphs, coupled with the use of graph summarization techniques (Han et
al., 2020b; Manzoor et al., 2016) has allowed for “low and slow” attack
patterns like Advanced Persistent Threats (APTs) to be detected (Kapoor et
al., 2021) despite the sheer amount of data gathered over long periods of
time, which has thwarted traditional IDSes.

The advantages of graph machine learning applied to provenance graphs for
anomaly detection have inspired a growing, intersectional research community
of cybersecurity specialists, systems engineers, data scientists, and machine
learning experts. Each member of this community has specialized knowledge of
different parts of the non-trivial process of logging data, engineering the
data into graphs, and learning from this graph-structured data. Currently,
there is not a data pipeline for automatically producing data from
cyberattacks, generating provenance graphs, and testing graph machine learning
algorithms on the data; rather, this process must be done manually by experts
from across the fields. This can be challenging, for example, for data
scientists who may not have access to cyberattack data or the specialization
to generate and capture this kind of data themselves. On the other hand,
cybersecurity specialists may not have the graph machine learning expertise to
effectively apply the latest machine learning approaches to the system
provenance data they have on hand.

In order to bridge the gap between these communities, enable automatic data
generation, and optimize the learning process, we propose Flurry, a fast
provenance framework for graph generation and analysis. Flurry is a virtual
machine environment equipped with provenance capture and graph generation
tools. As opposed to learning on static datasets, Flurry dynamically executes
automated cyberattacks and converts these logs into provenance graphs
ingestible by state-of-the-art graph machine learning tools. With the Flurry
system, researchers in provenance graph representation learning are no longer
required to perform their work in separate silos. The process from attack
simulation to anomaly detection is transparent, explainable, and readily
extensible for use with current techniques and for future development of novel
techniques for automated provenance analysis. Researchers may additionally use
our provenance generation system with their own machine learning models for
plug-and-play functionality to test new methods of representation learning.

The Flurry system provides the following contributions:

  * •

An end-to-end pipeline which can take a system execution, model it as a multi-
layer provenance graph, and use graph representation learning to detect
anomalies in that execution,

  * •

Dynamic, reproducible data sets of web-based injection attacks and brute force
password attacks,

  * •

Visualized execution of cyberattacks at the push of a button for full clarity
into our experiments and simplicity for future researchers,

  * •

Concepts for multi-layered data provenance across kernel and application
layers, bridging the semantic gap between user and kernel space,

  * •

A plug-and-play framework for graph learning models to analyze complex
provenance graphs. Furthermore, our framework provides a readily usable
sandbox to test graph machine learning models designed to analyze whole system
provenance graphs,

  * •

A platform to bring together researchers from the machine learning community
and the systems community.

##  2\. Preliminaries

###  2.1. Data Provenance

Provenance refers to the lineage of an object over time. Specifically,
provenance is a record of data origination, modification, and interactions.
Provenance originated in the context of art history, but has been widely
adapted even to computer system data. This kind of data provenance records the
history of system data over time, but also importantly captures relationships
among data. These associations can provide credibility to the data and be used
to establish trust. Furthermore, this trustworthiness makes data reusable for
both scientific research and root cause analysis. Provenance records may be
replayed or analyzed in a security context to determine potential cyber
attacks and mitigate those threats as a response.

Due to its relational properties, provenance data can be well-represented as a
provenance graph. The W3C Incubator Group has defined the PROV-DM model in
order to represent provenance data as directed, acyclic graphs. For node
types, data provenance can be recorded as entities, which are real, physical
or digital concepts; activities, which are interactions between or among
entities; or agents, which can act upon entities. PROV-DM also defines several
relation types between these nodes (W3C-PROV Working Group, 2013). Provenance
graphs are directed, meaning that an entity for example acts upon an activity
in a directional relationship. The graphs are also acyclic due to the time
series of actions. The graphs which are produced by provenance data are by
nature heterogeneous, as nodes will be different files, processes, inodes, and
more diverse node types which will have their own unique features. Provenance
produces multigraphs which have multiple relationships between nodes of
varying edge types, making the graph problem both rich with information and
uniquely challenging for analysis.

Figure 1 presents a high-level abstraction of provenance gathered from the
Google Chrome web browser running on the Flurry system. In the diagram, the
Google Chrome web browsing service (task) was generated by the process memory
which was derived from the binary path. This task is running on the host
machine and receiving messages from a socket. Furthermore, the task is
informing itself of versioning activity as it is running. This depiction
represents only a small portion of the gigabytes of data that are generated as
part of the provenance process over lengthy periods of time.

Figure 1. Sample provenance graph from Google Chrome web browsing activity.

###  2.2. Graph Representation Learning

For data provenance, graph representation learning may be used to detect
anomalies in execution graphs. Executions of anomalous behavior (for example,
a cross-site scripting attack) will generate provenance subgraphs which differ
structurally and in their hidden representations from benign execution graphs
(for example, web requests from a browser). Graph machine learning can aid
cyber security analysts in detecting and adapting to unforeseen attacks in
resilient systems.

We represent this multi-relational provenance data as a heterogenous graph
$G=(V,E,O,T,R)$. This directed graph contains a nodeset $V$, an edgeset $E$, a
set of node types $O$, a set of edgetypes $T$, and a set of canonical relation
types $R$. Each node $v\in V$ maps to a node type $o_{v}\in O$ and each edge
$(u,v)\in E$ maps to an edge type $t_{u,v}\in T$. Each canonical relation type
$r\in R$ maps to a tuple $(o_{u},t_{u,v},o_{v})$. The aim of the graph
representation learning component of this framework is to learn a function
which maps a provenance graph $G$ to an expressive, low-dimensional vector
representation, or embedding, $z$, where distance between embeddings
correlates to similarity between the graphs. In this work graph embeddings are
used to train a classifier to detect graphs containing anomalous behavior.

##  3\. Related Work

The collection, storage, and summarization of data provenance have been well-
studied in the security research community, and representational learning on
heterogeneous provenance graphs has recently become a prominent field in the
machine learning community (Bagavathi and Krishnan, 2019). Despite long-
standing research efforts in their respective communities, the intersection of
data provenance and graph representational learning lacks many foundational
frameworks that provide abundant public datasets, encourage reproducibility,
and enable the use of graph neural networks for system provenance data. Recent
efforts in developing graph-based techniques that employ neural networks for
automated analysis of system provenance data make the need for such frameworks
increasingly clear.

###  3.1. Graph Representation Learning

Graph representation learning seeks to generate low-dimensional feature
vectors (or embeddings) for nodes, edges, or graphs. Traditional methods for
generating embeddings for homogeneous graphs, such as DeepWalk (Perozzi et
al., 2014) and node2vec (Grover and Leskovec, 2016) used random walks on
graphs to learn about the local and global neighborhoods in which nodes
participate, allowing for generation of node representations that preserve
graph structural information. Advances in deep graph neural networks have
introduced the message-passing paradigm and convolutional graph embedding
approaches (GCNs) (Kipf and Welling, 2017; Hamilton et al., 2017). Such GCNs
leverage spectral or spatial convolutional filters along with neighborhood
aggregation to encode graph structural properties in node embeddings. Graph
Attention Networks (GAT) (Veličković et al., 2018) further improved on such
graph convolutional approaches by introducing node-level attention mechanisms
during neighbor aggregation.

Such convolutional approaches were originally limited to homogeneous networks,
but in recent years a number of heterogeneous graph embedding frameworks have
been proposed to extend graph neural networks to such multi-layered networks.
Relational-GCN (Schlichtkrull et al., 2018) extends the idea of GCNs by
employing separate convolutional operations for each relation within a
knowledge graph and then aggregating node representations across the multiple
relations in which each node participates. Heterogeneous Attention Networks
(HAN) similarly extend the idea of GAT to heterogeneous networks by employing
multiple convolutional filters defined over specified metapaths in a graph. To
consolidate the various representations of nodes from multiple metapaths, HAN
employs semantic attention to learn an optimal aggregation of the multiple
embeddings. Graph isomorphism network (GIN) (Xu et al., 2019) explores the
expressive power of GCN models for graph classification. The authors prove
that graph convolutional approaches can at most equal the Weisfeiler-Lehman
algorithm for graph isomorphism and that sum aggregation is more expressive of
the characteristic of multi-sets when compared with mean or max aggregators.
In addition to these works, other recent frameworks extend the ideas of random
walks on heterogeneous graphs (Dong et al., 2017; Bagavathi and Krishnan,
2019), and spectral approaches (Liu et al., 2020) for use with graph neural
networks that are effective techniques for unsupervised learning on
heterogeneous graphs.

###  3.2. Deep Learning on Provenance Graphs

####  3.2.1. Streamspot

Manzoor et al propose StreamSpot (Manzoor et al., 2016) as a clustering-based
anomaly detection approach on heterogeneous streaming graphs. They analyze
browsing data and downloading software in an effort to identify drive-by
download attacks as anomalous behavior.

####  3.2.2. SIGL

SIGL (Han et al., 2021) uses a word2vec-based node embedding approach in
conjunction with a long short-term memory network to capture long-term
dependencies in the provenance graph. Instances that fail to reach a minimum
threshold of reconstruction loss in the decoder stage are determined to be
anomalous software installations.

####  3.2.3. Unicorn

Similar to StreamSpot, Unicorn (Han et al., 2020b) uses a graph sketching
technique based on similarity hashing to reduce graph size to a fixed space.
For classification, the Unicorn system employs a version of the Weisfeiler-
Lehman subtree graph kernel algorithm. They use clustering-based anomaly
detection algorithms to aggregate similar graph hashes and identify anomalous
provenance graph signatures.

####  3.2.4. PROV-GEm

In PROV-GEm (Kapoor et al., 2021), the authors propose a graph embedding
framework based on graph convolutional networks coupled with relational self-
attention to generate informative representations of provenance graphs. This
combination allows PROV-GEm to encode the multi-faceted relationships and
graph structural properties captured in heterogeneous data provenance graphs.
PROV-GEm conducts anomaly detection experiments using the datasets published
by the authors of StreamSpot and Unicorn, outperforming the aforementioned
methods on graph anomaly detection and suggesting great potential for graph
neural network approaches in automated analysis of data provenance graphs.

While the datasets in these related works are publicly available to
researchers, they are static in nature. System provenance data cannot be
easily reproduced with certainty since system specifications and attack
scenarios may differ, and potential researchers must rely on the sparse
documentation of previously published provenance data generation frameworks.
In this work, we propose a paradigm shift to dynamic data collection for
provenance graph analysis. With the Flurry system, researchers can design
their own benign and attack scenarios with support for a wider variety of
attack types than in previous research. Raw system data is dynamically
created, and the logs are converted to graphs using our extensible software
module. This ensures that researchers also have access to the original system
logs, providing a better representation of real-world attack scenarios than
curated, pre-processed datasets (Han, 2018). Flurry’s intuitive GUI
illustrates attack scenarios in the Chrome browser in real time, providing a
transparent and easily understandable system for provenance data generation
usable by both security experts and other non-security researchers from areas
like machine learning and data science.

###  3.3. Automated Attack Systems

####  3.3.1. Xanthus

In conjunction with Unicorn (Han et al., 2020b), Han et al highlight the lack
of publicly available provenance graph datasets and emphasize the deficits of
those datasets that are made available to researchers. They propose a push-
button orchestrated system (Han et al., 2020a) for recreating test and
training data for provenance-based intrusion detection systems. Xanthus
introduces the idea of a distributable virtual machine image with configurable
jobs for automated recreation of attack scenarios, but this system requires
the user to orchestrate the attack and to ensure that the VM and job scripts
are correctly configured to mimic real-life scenarios. This requires extensive
systems knowledge and makes the framework difficult to use for other
researchers focused in data science and not security.

##  4\. System Design

Flurry is designed to work as both independent software modules or a joint
pipeline to support provenance graph learning from data creation and storage
to examination. In the following sections, we detail each stage of this
process which can work jointly or independently at the discretion of the user.
Throughout the system, we offer methods for importing and exporting data in
multiple formats for maximum adaptability.

Figure 2. A system overview of the fast Flurry framework.

###  4.1. Cyber Attack Automation

For Flurry v1.0, we focus on generating provenance data for web-based cyber
attacks. In this architecture, provenance may be captured for data exchanged
across sockets, server-client or peer-to-peer requests and responses, software
or other attachments queried for and returned, file reads and writes and
memory access on both server and client, and running processes on the server
and client, to name a few points of interest. In order to simulate web-based
cyber attacks on a web server, we run an instance of the Damn Vulnerable Web
Application (digininja, 2020) on the Fedora virtual machine that is configured
with a traditional XAMPP stack including Apache2 web server and MySQL database
for storage. This PHP-based application that allows security students and
professionals to practice skills and tools in a legal environment. Because it
is vulnerable, it is strongly recommended not to run the application on any
web server with real user information; therefore, we also recommend not
uploading proprietary or private data to Flurry to prevent exfiltration.

In order to start the DVWA application and web services needed to run it, we
provide a graphical user interface for researchers to start all dependencies
with the push of a button. Once initiated, the user may select one of the
attack scenarios to run and generate provenance, or a benign scenario which
corresponds to one of the attacks from our DVWA Runner application. This level
of abstraction over our automated scripts allows for rapid generation of
gigabytes of data in mere seconds even by inexperienced users. More details
about the attacks Flurry currently supports and the benign behavior is
provided in the datasets section.

As provenance is generated on the backend, the user will see our web driver
service run the scenario in real time on the screen. This allows for full
transparency of the attack process so that researchers are aware of how their
data was made. In addition to the user interface, we provide the Python
scripts themselves so that more experienced users may engineer new scenarios
or make adjustments according to their needs.

###  4.2. Data Provenance Capture and Management

The capture of data provenance is an entire subset field of data engineering.
At the systems level, there are multiple layers, or planes, at which data is
exchanged. In the kernel space, systems like Hi-Fi (Pohly et al., 2012), the
Linux Provenance Modules (LPM) (Bates et al., 2015) framework, and CamFlow
(Pasquier et al., 2017) capture IPC mechanisms, network activity, and access
to the kernel itself from the perspective of the operating system. These
systems use hooks into security access mechanisms to write provenance to a
buffer which is then typically translated into user space. In the user space,
we can divide provenance into even more fine-grained layers. For example, one
may want to isolate application-layer provenance to particular files the user
is modifying. Details of what was modified will not be recorded at the kernel
level, but we may want to semantically tie kernel-level security access with
data modification at the application level. This can be further extended to
browser-level provenance if we are using a browser application to view or
modify the file, and may even go to multi-host or network-level provenance if
we are sharing this file through a file transfer service like FTP. Part of the
data engineering required for good data provenance is determining the
granularity at which to capture metadata and how to semantically tie these
layers together. On the one hand, capturing too little or too coarse an image
of the system execution leads to over-summarization and can cause analysts to
miss anomalies. However, too much detail or association leads to dependency
explosion, or the phenomena of data becoming so entangled that the strongest
semantic ties are lost.

In Flurry, we are proposing to support a multi-plane approach for provenance
graphs for representation learning, which to our knowledge is a novel addition
to this subfield. At the kernel level, we use CamFlow, which is a Linux
security module, to capture provenance through kernel hooks. Data provenance
which is captured by this service include security access to system
information like inodes, security contexts, timestamps and jiffies, which
processes accessed kernel objects, and more. The full description of CamFlow
provenance node and edge types is well-recorded in their documentation
(Pasquier et al., 2017). This provenance information is published to a ring
buffer which is then captured by the CamFlow daemon. In the default
configuration of Flurry, we write this provenance to a log file on the virtual
machine, but it may be additionally configured to use a unix pipe or a
messaging service in order to convey this information dynamically. This allows
the system to work in a non-stop manner without the need for static data
files.

In addition to kernel-level provenance, Flurry adds hooks to PHP-based source
code in DVWA in order to capture application-level provenance. Such provenance
allows us to trace the flow of data within the web application such as where
they came from, how they came to be in their present state, who or what acted
upon them. Here in our application, events such as who inputs the data, how it
is transformed to an HTTP request, and subsequent server responses are
recorded. This additional layer may be combined with kernel access information
to provide semantic context to what is happening at the kernel level. In order
to capture both layers of provenance information in our audit logs, we
integrate the DVWA application source code with the Camflow Userspace API. For
such integrations, we have also used a library called PHP-CPP, developed by
Copernicus. This combination of application-level and kernel-level provenance
gives a wider lens into system execution and a larger plane for anomaly
detection.

Over time, storing provenance as log files is both space-consuming and
unexpressive. Researchers may want to store provenance in a graph database as
opposed to logs. This not only allows for provenance to be stored as nodes and
edges, but also supports querying for specific graph structures from the large
amount of data. For this reason, Flurry can also be configured to push data to
Neo4j (Neo4j, 2012), a graph database which can be refined and queried.
Storage can also be managed in the Flurry environment through the SPADE
(Gehani and Tariq, 2012) controller, an open-source provenance management
software created by Gehani et al. SPADE offers different provenance capture
methods including a CamFlow interface, analyzers, and transformers to perform
execution partitioning and graph summarization. SPADE’s purpose is also to
serve as a control interface to port CamFlow data into Neo4j or even
relational databases like H2. As a research software, some of these
capabilities remain unimplemented or run with error. In future work, we plan
to expand on some of these additional capabilities and contribute to their
improvement.

###  4.3. Provenance Graph Conversion

Related works in provenance graph representation learning have written their
own scripts for conversion of provenance data into complex graphs (Han et al.,
2021, 2020b; Manzoor et al., 2016). While this serves as a stop-gap solution,
ultimately these works have not focused on reusability or extensibility of
conversion. As opposed to scripts for fixed use cases, we add to the field a
software tool which supports conversion of data from many input forms created
by mainstream provenance capture tools into software or serialized graphs
usable by machine learning frameworks. In Flurry v1.0, we call this CF2G,
which stands for “CamFlow to graph”. CF2G accepts as input data serialized in
the W3C-PROV (W3C-PROV Working Group, 2013) JSON format, or the SPADE (Gehani
and Tariq, 2012) JSON format, both of which are published by the CamFlow
daemon and configurable via the camflowd service. From the command line
interface, CF2G parses the input graph and stores it as an internal graph.
Using the CLI or the packaged library, a researcher may create JSON-exportable
network representations of the stored provenance, call for the creation of a
NetworkX (NetworkX developer team, 2014) graph, or construct a Deep Graph
Library (Wang et al., 2019b) graph. CF2G also supports statistical output of
the recorded provenance such as node types, edge types, and overall
dimensionality. Currently, we support direct library calls or serialized and
compressed export of the graphs to the next module.

###  4.4. Feature Engineering

Graph convolutional network models for learning node embeddings rely on
iteratively aggregating a node’s information with the information of its
neighbors. This process hinges on each node having an initial node feature
vector which can be used in the aggregation process. For this work we use
structural node information including node degree and custom spectral methods
for heterogeneous graphs extended from (Belkin and Niyogi, 2003), which
performs an eigendecomposition using the LOBPCG (Stathopoulos and Wu, 2002;
Duersch et al., 2018) estimator on a block matrix (Bianconi, 2018) built
around the normalized Laplacian matrices of each relation type in the graph.

###  4.5. GNN Trainer

In addition to our system provenance collection and graph generation tools, we
provide a unified graph neural network trainer based on DGL and PyTorch,
inspired by the Trainer class provided by HuggingFace for training Transformer
models on NLP tasks. Our training framework consists of a base Trainer class
that defines the core training and evaluation functions for graph
classification using GNN models, and a TrainingArguments class that defines
training and evaluation hyperparameters and additional behavior. We provide a
set of default callback functions that define normal training operations,
including logging, saving model checkpoints, and early stopping using
validation metrics. Our framework also supports custom user-defined callback
functions to further customize the Trainer’s behavior during model training
and evaluation. Our Trainer framework utilizes DGL’s graph batching and
message-passing functionality to provide a standardized yet flexible framework
for training graph neural models. We support standard PyTorch loss functions,
such as cross-entropy loss, and also custom-defined trainable loss functions
that can be used for unsupervised training on graphs. Our framework currently
supports graph classification tasks, and we plan to extend our Trainer
framework to support node classification and edge prediction tasks in the
future.

##  5\. Threat Models

The exact datasets we used for experiments will be publicly available. Table 1
shows the size of the graphs in terms of nodes and edges. Relation types are
defined as unique source node, edge type, destination node three-tuples. The
execution involves navigating to the tab on the DVWA website that corresponds
to the attack and performing some attack or benign behavior. The attacks
covered in this dataset and by the current version of Flurry cover more than
50% of the most popular attack vectors cyber criminals choose for web-based
applications (Positive Technologies, 2019).

Attack Vector | Class Type | Avg. # of Nodes | Avg. # of Edges | Avg. # of Relation Types
---|---|---|---|---
XSS Stored | Benign | 19,436 | 463,682 | 30
| Attack | 19,547 | 480,179 | 31
XSS Reflected | Benign | 33,481 | 824,276 | 31
| Attack | 24,435 | 666,705 | 32
XSS DOM | Benign | 31,243 | 753,519 | 30
| Attack | 30,261 | 751,133 | 32
Command Line Injection | Benign | 32,996 | 793,318 | 29
| Attack | 25,720 | 631,633 | 30
SQL Injection | Benign | 22,903 | 543,266 | 30
| Attack | 29,576 | 733,375 | 30
Brute Force | Benign | 21,518 | 517,101 | 30
| Attack | 418 | 416 | 1
Table 1. Description of Attack Graph Datasets

### Cross-Site Scripting

Cross-site scripting allows an attacker to inject JavaScript in a web
application in order to modify the web page viewed by the user or perform some
other malicious action such as data exfiltration or modification. Like other
injection attacks, the vulnerability usually exists because of a lack of data
input sanitization from web forms or requests.

XSS Reflected. Reflected scripts are non-persistent, meaning that they are
ephemerally injected into the HTTP client request processed by the web server.
If the web server does not properly read the HTML escape sequences when
reading the request, the JavaScript in the request will be executed on the
page on the server side. In the Flurry dataset, we create a benign execution
by filling out and submitting the web form question (“What is your name?”).
For the attack, we inject JavaScript in the web form to pop up a text box and
corresponding message after submission.

XSS Stored. A stored scripted attack is not sent by the client, but rather
stored in the server database and thus is persistent as it can be re-executed.
For example, an attacker may post a message to a forum with an embedded
script. When other clients go to read the message, the attacker’s script will
be executed when the message is read/returned (Positive Technologies, 2020).
In Flurry, we automate posting a non-malicious message to a forum on the XSS
Stored tab for benign execution. For the attack, we inject a script in the
message which creates a bot-style malicious post every time the tab is
visited.

XSS DOM. A DOM-style attack can be modified on the client side and thus does
not require access to the web server or poor sanitization on the server’s
part. It relies on poor reading of HTML escape sequences in the client’s
document object model. The XSS DOM tab in the Damn Vulnerable Web Application
asks the user to choose a language, and this setting is then part of the DOM
and shown in the public-facing URL. In Flurry, we modify the DOM by injecting
the script into the web URL. Our script creates a pop-up similar to the XSS
Reflected attack. For benign behavior, we automate selecting English as the
default language.

### Injection

While cross-site scripting is a style of injection attack specific to
JavaScript and the web page, other types of injections such as SQL for
database access/modification and command line injection can be used to cause
remote code execution, privilege escalation, data exfiltration, and other
types of more consequential attacks.

Command Line Injection. When web submissions are not properly sanitized,
system commands may be included and will be executed on the server machine. In
DVWA, the Command Line Injection tab asks the user to provide an IP address to
ping. For the benign execution, we provide localhost 127.0.0.1 for pinging.
For the attack, we inject pwd to print the current working directory where the
server is executing the ping.

SQL Injection. In the DVWA SQL Injection tab, the user is prompted for an ID.
In a benign execution, this ID is included as part of a SQL query which is
looked up in the internal database. In the attack automation, we include a
semicolon and additional SQL query for other user IDs.

### Password Cracking

In addition to injection-style attacks, we wanted to expand into password
crackers, which make up a significant portion of web application-based cyber
attacks (Positive Technologies, 2019). In future versions of Flurry, we may
further look into more advanced rainbow table or dictionary style password
attacks.

Brute Force. There are an array of automated tools for brute force; we use the
Hydra (Tools, 2021) password cracking tool. We provide an attack script which
executes the hydra command and provide a dictionary with the 100 most commonly
used passwords to try. For benign execution, we automate logging in with the
correct credentials.

##  6\. Experiments

|  | HAN |  |  | R-GCN |  |  | PROV-GEm |
---|---|---|---|---|---|---|---|---|---
| F1 | Precision | Recall | F1 | Precision | Recall | F1 | Precision | Recall
brute-force | 99.51$\pm$0.97 | 100.0$\pm$0.0 | 99.35$\pm$1.29 | 100.0$\pm$0.0 | 100.0$\pm$0.0 | 100.0$\pm$0.0 | 100.0$\pm$0.0 | 100.0$\pm$0.0 | 100.0$\pm$0.0
cl-injection | 63.35$\pm$8.07 | 81.44$\pm$15.97 | 65.57$\pm$12.98 | 70.60$\pm$8.26 | 69.16$\pm$23.59 | 79.84$\pm$12.95 | 58.08$\pm$9.56 | 63.72$\pm$15.37 | 60.00$\pm$12.76
sql-injection | 71.32$\pm$17.85 | 71.43$\pm$16.39 | 83.30$\pm$17.35 | 81.66$\pm$9.19 | 73.07$\pm$15.60 | 89.26$\pm$3.39 | 71.30$\pm$10.61 | 84.59$\pm$5.55 | 69.41$\pm$10.42
xss-dom | 91.23$\pm$4.33 | 84.83$\pm$8.43 | 97.50$\pm$5.00 | 80.70$\pm$9.97 | 81.66$\pm$16.51 | 82.92$\pm$11.95 | 91.23$\pm$4.33 | 84.83$\pm$8.43 | 97.50$\pm$5.00
xss-reflected | 90.35$\pm$4.84 | 88.79$\pm$9.83 | 93.63$\pm$4.05 | 84.22$\pm$4.55 | 85.93$\pm$8.53 | 83.64$\pm$6.37 | 88.87$\pm$7.23 | 83.63$\pm$14.22 | 95.16$\pm$4.78
xss-stored | 52.80$\pm$8.36 | 71.87$\pm$14.48 | 53.96$\pm$10.51 | 48.39$\pm$6.64 | 71.00$\pm$23.63 | 51.59$\pm$6.52 | 53.50$\pm$8.48 | 64.59$\pm$15.92 | 55.93$\pm$12.64
Table 2. Graph classification results using generated Flurry data for six
system attack types.

In this section, we describe the anomaly detection experiments we perform on
system provenance data collected by Flurry. For each of the six attack types
characterized in Section 5, we simulate 100 benign operations and 100 attack
operations. We convert the system provenance data into heterogeneous graphs
and partition the datasets into five cross validation folds to ensure
consistent and reproducible results. For each attack type, we conduct graph
classification experiments using our Trainer class with three different
heterogeneous graph embedding frameworks from graph representational learning
literature—R-GCN (Schlichtkrull et al., 2018), HAN (Wang et al., 2019a), and
PROV-GEm (Kapoor et al., 2021)—implemented in DGL. In each experimental setup,
one cross validation fold is held out as a test set, and the graph embedding
models are trained with the remaining provenance graphs using cross entropy
loss. Our results on the graph anomaly detection task are presented in Table
2. We report the mean and standard deviation over five-fold cross validation
of precision, recall, and F1 score. The code for our experiments along with
our graph neural network training framework are provided
at111https://github.com/NASCL/dgl-trainer.git

Due to the nature of brute force attacks, their system provenance generates
graphs containing only a single relation type: (socket, WasDerivedFrom,
socket). As such, these graphs are trivially easy to distinguish from benign
system behavior, and all three of the graph neural network models were able to
perform perfectly on the generated data. By contrast, for the two injection-
style attacks—command line injection and SQL injection—anomalous behavior is
much more difficult to identify from benign provenance graphs generate during
normal application use. Both scenarios exhibited high variance in performance
across cross validation folds, suggesting that both injection-style attacks
can vary in their graph properties.

In our experiments, we found that the SQL injection and command line injection
attacks were more difficult to detect than others from the datasets that were
gathered. Considering the system execution, the kernel-level provenance and
database-level provenance for both benign and attack scenarios are similar as
both are ultimately SQL queries or file system reads/writes. It is evident
from our experiments that single-layer provenance is not able to capture
anomalies for all attack types; some attacks are more evident at different
layers of the system execution. Currently, existing provenance capture tools
have provided some anomaly detection capability, but there is a lack of tools
for attack types which are not evident at the kernel level. Our results here
are consistent with the postulation that multi-layer provenance would be more
effective.

A similar phenomenon can be noted with our results in the stored cross-site
scripting scenario. The attack behavior is a bot-style message. The attack
itself is not much different from benign posting behavior, but the frequency
of the message may be noted as anomalous in a graph learning system which
models time-series information.

Our models performed best on the cross-site reflected and DOM scenarios. For
the reflected threat model, the attack system execution behavior is distinctly
different as it pulls up a pop-up window which does not exist in the benign
version. Similarly, the DOM model also generates a pop-up window that does not
exist in the benign scenario. Both of these generate unique provenance graph
substructures which are detectable by the models as anomalous in the
provenance layers we examined. A significant finding of our experiments is
that whole-scope anomaly detection in provenance graphs will continue to
require constant vigilance in multiple layers of the target system - no single
layer solution will be sufficient to catch even a narrow variety of attacks.

##  7\. Discussion and Future Work

The Flurry system is a novel, initial contribution to automated provenance
graph generation and machine learning and thus has room for testing and
improvement. The system currently writes logs to files intermittently. This
design is intentional as we do not provide graph summarization beyond the de-
duplication that CamFlow (Pasquier et al., 2017) supports, and thus would
overwhelm the downstream applications with log data if it were piped directly.
Future versions will include a graph summarization element and the ability to
work with streaming data as well as static graphs.

One aspect of browser-level provenance which we have not yet implemented in
Flurry is to capture and compare user entries into forms. We propose in future
work to develop a browser provenance extension to Flurry which will scrape
these forms and use similarity metrics of routine entries as a potential
learning feature. As a practical example, an injected SQL query will be quite
dissimilar to an expected web form entry for a username. Locality sensitive
hashing could provide both a distance measure that could improve model results
for this attack type and obfuscation for user privacy. This experimental
result and potential solution reveal the importance of multi-layer provenance,
as different attacks will be more evident at different layers of the system.

In future versions of Flurry, we intend to design a streaming graph approach
to the pipeline in addition to segmented graphs in order to better capture
attack rates. This approach has been explored in provenance graph learning
systems (Han et al., 2020b; Manzoor et al., 2016) and would be a useful
addition to our automated framework. It gives an additional insight to data
provenance that is temporal as opposed to solely spatial. This would also
likely improve results in other frequency-based vectors like flooding in
denial-of-service or brute-force attacks.

##  8\. Conclusion

Flurry advances the state of the art by extending both ways in the process to
create a full data pipeline for provenance graph representation learning.
First, we expand the user-friendliness and quality assurance of the traces by
providing a GUI for ease of interaction with the attack scenarios. We also use
a web driver to automate the attacks so that the researcher creating the data
can watch the attack as it happens. The data is then captured by provenance
tools pre-installed on our distributable VM image. While highly configurable,
these tools are also ready at deployment to capture provenance at the click of
a button. We provide additional tools to export the raw data or process it
into provenance graphs. For maximum flexibility we provide a library tool for
converting the raw logs into NetworkX or Deep Graph Library graphs, exportable
JSON, or compressed and serialized formats which can be manually uploaded into
other machine learning frameworks. Finally, we provide a collection of deep
learning models for examination of these provenance graphs as they are
generated. Our experiments and results reveal the capability of Flurry as a
provenance graph generation system from cyber attack to anomaly detection. We
offer this system as a tool for the research community to continue to advance
the state of the art in provenance graph representation learning.

## References

  * (1)
  * Bagavathi and Krishnan (2019) Arunkumar Bagavathi and Siddharth Krishnan. 2019.  Multi-Net: A Scalable Multiplex Network Embedding Framework. In _Complex Networks and Their Applications VII_ , Luca Maria Aiello, Chantal Cherifi, Hocine Cherifi, Renaud Lambiotte, Pietro Lió, and Luis M. Rocha (Eds.). Springer International Publishing, Cham, 119–131.
  * Bates et al. (2015) Adam Bates, Dave Tian, Kevin R. B. Butler, and Thomas Moyer. 2015\.  Trustworthy Whole-System Provenance for the Linux Kernel. In _Proceedings of the 24th USENIX Conference on Security Symposium_ (Washington, D.C.) _(SEC’15)_. USENIX Association, USA, 319–334.
  * Belkin and Niyogi (2003) Mikhail Belkin and Partha Niyogi. 2003.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural computation_ 15, 6 (2003), 1373–1396.
  * Bianconi (2018) Ginestra Bianconi. 2018\.  _Multilayer Networks: Structure and Function_.  Oxford university press.
  * digininja (2020) digininja. 2020\.  Damn Vulnerable Web Application.  https://github.com/digininja/DVWA.
  * Dong et al. (2017) Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017\.  metapath2vec: Scalable representation learning for heterogeneous networks. In _SIGKDD_. 135–144.
  * Duersch et al. (2018) Jed A Duersch, Meiyue Shao, Chao Yang, and Ming Gu. 2018\.  A robust and efficient implementation of LOBPCG.  _SIAM Journal on Scientific Computing_ 40, 5 (2018), C655–C676.
  * Gehani and Tariq (2012) Ashish Gehani and Dawood Tariq. 2012.  SPADE: Support for Provenance Auditing in Distributed Environments.  In _Middleware 2012_ , Priya Narasimhan and Peter Triantafillou (Eds.). Lecture Notes in Computer Science, Vol. 7662. Springer Berlin Heidelberg, 101–120.  https://doi.org/10.1007/978-3-642-35170-9_6
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks. In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_. 855–864.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _NeurIPS_. 1024–1034.
  * Han (2018) Xueyuan Han. 2018\.  StreamSpot Dataset.  https://doi.org/10.7910/DVN/83KYJY
  * Han et al. (2020a) Xueyuan Han, James Mickens, Ashish Gehani, Margo I. Seltzer, and Thomas F. J.-M. Pasquier. 2020a.  Xanthus: Push-button Orchestration of Host Provenance Data Collection.  _CoRR_ abs/2005.04717 (2020).  arXiv:2005.04717 https://arxiv.org/abs/2005.04717
  * Han et al. (2020b) Xueyuan Han, Thomas F. J.-M. Pasquier, Adam Bates, James Mickens, and Margo I. Seltzer. 2020b.  UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats.  _CoRR_ abs/2001.01525 (2020).  arXiv:2001.01525 http://arxiv.org/abs/2001.01525
  * Han et al. (2021) Xueyuan Han, Xiao Yu, Thomas Pasquier, Ding Li, Junghwan Rhee, James Mickens, Margo Seltzer, and Haifeng Chen. 2021\.  SIGL: Securing Software Installations Through Deep Graph Learning.  arXiv:2008.11533 [cs.CR]
  * Kapoor et al. (2021) Maya Kapoor, Joshua Melton, Michael Ridenhour, Siddharth Krishnan, and Thomas Moyer. 2021\.  PROV-GEM: Automated Provenance Analysis Framework using Graph Embeddings. In _2021 20th IEEE International Conference on Machine Learning and Applications (ICMLA)_. 1720–1727.  https://doi.org/10.1109/ICMLA52953.2021.00273
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _ICLR_.
  * Liu et al. (2020) Zhijun Liu, Chao Huang, Yanwei Yu, Baode Fan, and Junyu Dong. 2020.  Fast Attributed Multiplex Heterogeneous Network Embedding. In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_. 995–1004.
  * Manzoor et al. (2016) Emaad A. Manzoor, Sadegh Momeni, Venkat N. Venkatakrishnan, and Leman Akoglu. 2016.  Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs.  arXiv:1602.04844 [cs.SI]
  * Neo4j (2012) Neo4j. 2012.  Neo4j - The World’s Leading Graph Database.  http://neo4j.org/
  * NetworkX developer team (2014) NetworkX developer team. 2014\.  NetworkX.  https://networkx.github.io/
  * Pasquier et al. (2017) Thomas F. J.-M. Pasquier, Xueyuan Han, Mark Goldstein, Thomas Moyer, David M. Eyers, Margo I. Seltzer, and Jean Bacon. 2017\.  Practical Whole-System Provenance Capture.  _CoRR_ abs/1711.05296 (2017).  arXiv:1711.05296 http://arxiv.org/abs/1711.05296
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. 701–710.
  * Pohly et al. (2012) Devin J. Pohly, Stephen McLaughlin, Patrick McDaniel, and Kevin Butler. 2012.  Hi-Fi: Collecting High-Fidelity Whole-System Provenance. In _Proceedings of the 28th Annual Computer Security Applications Conference_ (Orlando, Florida, USA) _(ACSAC ’12)_. Association for Computing Machinery, New York, NY, USA, 259–268.  https://doi.org/10.1145/2420950.2420989
  * Positive Technologies (2019) Positive Technologies. 2019\.  Attacks on web applications: 2018 in review.  https://www.ptsecurity.com/ww-en/analytics/web-application-attacks-2019/
  * Positive Technologies (2020) Positive Technologies. 2020\.  What is a cross-site scripting (XSS) attack?  https://www.ptsecurity.com/ww-en/analytics/knowledge-base/what-is-a-cross-site-scripting-xss-attack/#5
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018.  Modeling Relational Data with Graph Convolutional Networks. In _The Semantic Web_. Springer International Publishing, 593–607.
  * Stathopoulos and Wu (2002) Andreas Stathopoulos and Kesheng Wu. 2002.  A block orthogonalization procedure with constant synchronization requirements.  _SIAM Journal on Scientific Computing_ 23, 6 (2002), 2165–2182.
  * Tools (2021) Kali Linux Tools. 2021\.  Hydra.  https://www.kali.org/tools/hydra/
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks. In _ICLR_.
  * W3C-PROV Working Group (2013) W3C-PROV Working Group. 2013\.  PROV-Overview: An Overview of the PROV Family of Documents.  https://www.w3.org/TR/prov-overview/
  * Wang et al. (2019b) Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander J. Smola, and Zheng Zhang. 2019b.  Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs.  _CoRR_ abs/1909.01315 (2019).  arXiv:1909.01315 http://arxiv.org/abs/1909.01315
  * Wang et al. (2019a) Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019a.  Heterogeneous graph attention network. In _WWW_. 2022–2032.
  * Xu et al. (2019) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019\.  How Powerful are Graph Neural Networks?. In _International Conference on Learning Representations_.

##  Appendix A Appendix

###  A.1. Application Level Sample Provenance Graphs

Figure 3. Provenance graph for SQL injection attack. Figure 4. Provenance
graph for command line injection attack. Figure 5. Provenance graph for cross
site scripting attack.

###  A.2. Implementation Details

The experiments were conducted on a 64core AMD EPYC 7742 CPU @ 2.25 GHz with
an NVIDIA A100 GPU. Our models are implemented using PyTorch 1.10.2 and DGL
0.7.2 in Python 3.9. We use our Trainer and TrainingArguments classes to
specify and define training and evaluation behavior, and we use DGL to
implement our message passing graph neural network models. Evaluation metrics
are computed using scikitlearn f1_score, prescision_score, and recall_score.
Experiments were conducted using five-fold cross validation with metrics
reported as the mean and standard deviation averaged over the five folds.

##### Parameter Configuration.

We set the hidden and embedding dimensions for all models to 256 dimensions
for all experiments, and the attention dimension for HAN and PROV-GEm are set
to 64 dimensions. A dropout out rate of 0.5 and L2 regularization weight decay
of 0.005 were used as regularization during model training. Table 3 defines
the individual training parameters used for each model for each experiment
with the six attack-type datasets generated by Flurry.

###  A.3. Learning Parameters

Attack Type | Model | Epochs | Aggregation | Learn Rate
---|---|---|---|---
| HAN | 20 | sum | 0.001
brute-force | R-GCN | 10 | sum | 0.001
| PROV-GEm | 20 | sum | 0.001
| HAN | 7 | sum | 0.0005
cl-injection | R-GCN | 7 | sum | 0.0005
| PROV-GEm | 7 | sum | 0.0005
| HAN | 5 | sum | 0.0005
sql-injection | R-GCN | 20 | mean | 0.0005
| PROV-GEm | 10 | sum | 0.0005
| HAN | 20 | sum | 0.001
xss-dom | R-GCN | 10 | sum | 0.0005
| PROV-GEm | 20 | sum | 0.001
| HAN | 20 | sum | 0.001
xss-reflected | R-GCN | 20 | mean | 0.0005
| PROV-GEm | 20 | sum | 0.001
| HAN | 7 | sum | 0.005
xss-stored | R-GCN | 7 | sum | 0.001
| PROV-GEm | 7 | sum | 0.005
Table 3. Training Parameters for Graph Learning Models


# The Complexity of Power Graphs Associated With Finite Groups

S. Kirkland1, A. R. Moghaddamfar2,3, S. Navid Salehy4,
S. Nima Salehy4 and M. Zohourattar2
1Department of Mathematics, University of Manitoba,
Winnipeg, MB, Canada.
<EMAIL_ADDRESS>
2Faculty of Mathematics, K. N. Toosi University of Technology,
P. O. Box $16315$–$1618$, Tehran, Iran,
3Department of Mathematical Sciences, Kent State University,
Kent, Ohio $44242$, USA
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
4Department of Mathematics, Florida State University,
Tallahassee, FL $32306$, USA.
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

The power graph $\mathcal{P}(G)$ of a finite group $G$ is the graph whose
vertex set is $G$, and two elements in $G$ are adjacent if one of them is a
power of the other. The purpose of this paper is twofold. First, we find the
complexity of a clique–replaced graph and study some applications. Second, we
derive some explicit formulas concerning the complexity
$\kappa(\mathcal{P}(G))$ for various groups $G$ such as the cyclic group of
order $n$, the simple groups $L_{2}(q)$, the extra–special $p$–groups of order
$p^{3}$, the Frobenius groups, etc.

Keywords: Power graph, spanning tree, complexity, group.

footnotetext: $2010$ Mathematics Subject Classification: 20D06, 05C05, 05C50.

##  1 Introduction

All graphs considered here are simple connected graphs. A spanning tree of a
connected graph is a subgraph that contains all the vertices and is a tree.
Counting the number of spanning trees in a connected graph is a problem of
long–standing interest in various fields of science. For a graph $\Gamma$, the
number of spanning trees of $\Gamma,$ denoted by $\kappa(\Gamma),$ is known as
the complexity of $\Gamma$.

In this paper, we consider some graphs arising from finite groups. One
well–known graph is the power graph, as defined more precisely below.

###### Definition 1.1

Let $G$ be a finite group and $X$ a nonempty subset of $G$. The power graph
$\mathcal{P}(G,X)$, has $X$ as its vertex set and two vertices $x$ and $y$ in
$X$ are joined by an edge if $\langle x\rangle\subseteq\langle y\rangle$ or
$\langle y\rangle\subseteq\langle x\rangle$.

The term power graph was introduced in [11], and after that power graphs have
been investigated by many authors, see for instance [1, 5, 15]. The
investigation of power graphs associated with algebraic structures is
important, because these graphs have valuable applications (see the survey
article [12]) and are related to automata theory (see the book [10]).

In the case $X=G$, we will simply write $\mathcal{P}(G)$ instead of
$\mathcal{P}(G,G)$. Clearly, when $1\in X$, the power graph is connected, and
we can talk about the complexity of this graph. For convenience, we put
$\kappa_{G}(X)=\kappa(\mathcal{P}(G,X))$ and
$\kappa(G)=\kappa(\mathcal{P}(G))$. A well known result due to Cayley [6] says
that the complexity of the complete graph on $n$ vertices is $n^{n-2}$. In [2]
it was shown that a finite group has a complete power graph if and only if it
is a cyclic $p$–group, where $p$ is a prime number. Thus, as an immediate
consequence of Cayley’s result, we derive
$\kappa({\mathbb{Z}}_{p^{m}})=p^{m(p^{m}-2)}$. Recently, the authors of [16]
obtained a formula to compute the complexity $\kappa({\mathbb{Z}}_{n})$ for
any $n$ (see Corollary 4.3 below). To obtain Corollary 4.3, we will define a
class of graphs more general than the power graphs of cyclic groups.
Specifically, we start with a graph $\Gamma$ on vertices
$v_{1},v_{2},\ldots,v_{n}$. To construct a new graph, we replace each $v_{i}$
by a complete graph $K_{x_{i}}$ on $x_{i}$ vertices, and if there is an edge
between $v_{i}$ and $v_{j}$ in $\Gamma$, then we connect each vertex of
$K_{x_{i}}$ with each vertex of $K_{x_{j}}$. The new graph will be denoted by
$\Gamma_{[x_{1},\ldots,x_{n}]}$. We will derive explicit formulas for the
complexity $\kappa(\Gamma_{[x_{1},\ldots,x_{n}]})$ (see Theorem 4.1 and Remark
4.2). Then we will obtain a formula for the complexity
$\kappa({\mathbb{Z}}_{n})$ by choosing a certain graph $\Gamma$ on $k$
vertices and positive integers $x_{1},x_{2},\ldots,x_{k}$ (Corollary 4.3).
Finally, the complexities $\kappa(G)$ for certain groups $G$ are presented.

The outline of the paper is as follows. In the next section, we recall some
basic definitions and notation and give several auxiliary results to be used
later. The main result of Section 4 is Theorem 4.1 and we include some of its
applications. In Section 5, we compute $\kappa(G)$ for certain groups $G$.

##  2 Terminology and Previous Results

We first establish some notation which will be used repeatedly in the sequel.
Given a graph $\Gamma$, we denote by $\mathbf{A}_{\Gamma}$ and
$\mathbf{D}_{\Gamma}$ the adjacency matrix and the diagonal matrix of vertex
degrees of $\Gamma$, respectively. The Laplacian matrix of $G$ is defined as
$\mathbf{L}_{\Gamma}=\mathbf{D}_{\Gamma}-\mathbf{A}_{\Gamma}$. Clearly,
$\mathbf{L}_{\Gamma}$ is a real symmetric matrix and its eigenvalues are
nonnegative real numbers. The Laplacian spectrum of $\Gamma$ is

${\rm
Spec}(\mathbf{L}_{\Gamma})=\left(\mu_{1}(\Gamma),\mu_{2}(\Gamma),\ldots,\mu_{n}(\Gamma)\right),$

where
$\mu_{1}(\Gamma)\geqslant\mu_{2}(\Gamma)\geqslant\cdots\geqslant\mu_{n}(\Gamma)$,
are the eigenvalues of $L_{\Gamma}$ arranged in weakly decreasing order, and
$n=|V(\Gamma)|$. Note that $\mu_{n}(\Gamma)=0$, because each row sum of
$\mathbf{L}_{\Gamma}$ is 0. Instead of $\mathbf{A}_{\Gamma}$,
$\mathbf{L}_{\Gamma}$, and $\mu_{i}(\Gamma)$ we simply write $\mathbf{A}$,
$\mathbf{L}$, and $\mu_{i}$ if it does not lead to confusion. Given a subset
$\Lambda$ of the vertex set of a graph, we let $\mathbf{A}(\Lambda)$ denote
the principal submatrix of $\mathbf{A}$ corresponding to the vertices in
$\Lambda$.

For a graph with $n$ vertices and Laplacian spectrum
$\mu_{1}\geqslant\mu_{2}\geqslant\cdots\geqslant\mu_{n}=0$ it has been proved
[3, Corollary 6.5] that:

$\kappa(\Gamma)=\frac{\mu_{1}\mu_{2}\cdots\mu_{n-1}}{n}.$ (1)

The vertex–disjoint union of the graphs $\Gamma_{1}$ and $\Gamma_{2}$ is
denoted by $\Gamma_{1}\oplus\Gamma_{2}$. Define the join of $\Gamma_{1}$ and
$\Gamma_{2}$ to be
$\Gamma_{1}\vee\Gamma_{2}=(\Gamma_{1}^{c}\oplus\Gamma_{2}^{c})^{c}$. Evidently
this is the graph formed from the vertex–disjoint union of the two graphs
$\Gamma_{1},\Gamma_{2}$, by adding edges joining every vertex of $\Gamma_{1}$
to every vertex of $\Gamma_{2}$. Now, one may easily prove the following (see
also [14]).

###### Lemma 2.1

Let $\Gamma_{1}$ and $\Gamma_{2}$ be two graphs on disjoint sets with $m$ and
$n$ vertices, respectively. If

${\rm
Spec}(\mathbf{L}_{\Gamma_{1}})=\left(\mu_{1}(\Gamma_{1}),\mu_{2}(\Gamma_{1}),\ldots,\mu_{m}(\Gamma_{1})\right),$

and

${\rm
Spec}(\mathbf{L}_{\Gamma_{2}})=\left(\mu_{1}(\Gamma_{2}),\mu_{2}(\Gamma_{2}),\ldots,\mu_{n}(\Gamma_{2})\right),$

then, the following hold:

  * (1)

the eigenvalues of Laplacian matrix $\mathbf{L}_{\Gamma_{1}\oplus\Gamma_{2}}$
are:

$\mu_{1}(\Gamma_{1}),\ \ldots,\ \mu_{m}(\Gamma_{1}),\ \mu_{1}(\Gamma_{2}),\
\ldots,\ \mu_{n}(\Gamma_{2}).$

  * (2)

the eigenvalues of Laplacian matrix $\mathbf{L}_{\Gamma_{1}\vee\Gamma_{2}}$
are:

$m+n,\ \mu_{1}(\Gamma_{1})+n,\ \ldots,\ \mu_{m-1}(\Gamma_{1})+n,\
\mu_{1}(\Gamma_{2})+m,\ \ldots,\ \mu_{n-1}(\Gamma_{2})+m,\ 0.$

A universal vertex is a vertex of a graph that is adjacent to all other
vertices of the graph. Now, we restrict our attention to information about the
set of universal vertices of the power graph of a group $G$. As already
mentioned, the identity element of $G$ is a universal vertex in
$\mathcal{P}(G)$, and also $\mathcal{P}(G)$ is complete if and only if $G$ is
cyclic of prime power order, and in this case $G$ is the set of all universal
vertices. However, the following lemma [5, Proposition $4$] determines the set
of universal vertices of the power graph of $G$, in the general case.

###### Lemma 2.2

Let $G$ be a finite group and $S$ the set of universal vertices of the power
graph $\mathcal{P}(G)$. Suppose that $|S|>1$. Then one of the following
occurs:

  * (a)

$G$ is cyclic of prime power order, and $S=G$;

  * (b)

$G$ is cyclic of non–prime–power order $n$, and $S$ consists of the identity
and the generators of $G$, so that $|S|=1+\phi(n)$, where $\phi$ is Euler’s
$\phi$–function;

  * (c)

$G$ is generalized quaternion, and $S$ contains the identity and the unique
involution in $G$, so that $|S|=2$.

We conclude this section with notation and definitions to be used in the
paper. All the groups considered here are finite. We denote by $[G,G]$ the
commutator subgroup, for any group $G$. If $g\in G$, then $o(g)$ denotes the
order of the element $g$. We refer to any element in $G$ of order $2$, as an
involution. An elementary abelian $p$–group of order $p^{n}$, denoted by
${\mathbb{E}}_{p^{n}}$, is isomorphic to a direct product of $n$ copies of the
cyclic group ${\mathbb{Z}}_{p}$. The complement of a graph $\Gamma$ is denoted
by $\Gamma^{c}$. The neighborhood of a vertex $v$ in the graph $\Gamma$ is
denoted by $N_{\Gamma}(v)$. Let $K_{n}$ denote the complete graph (clique)
with $n$ vertices. Throughout we use the standard notation and terminology
introduced in [3, 9] for graph theory and group theory.

##  3 Auxiliary Results

###### Lemma 3.1

Let $\Gamma$ be any graph on $n$ vertices with Laplacian spectrum

$\mu_{1}\geqslant\mu_{2}\geqslant\cdots\geqslant\mu_{n}.$

If $m$ is an integer, then the following product

$(\mu_{1}+m)(\mu_{2}+m)\cdots(\mu_{n-1}+m),$

is also an integer.

Proof. Consider the characteristic polynomial of the Laplacian matrix
$\mathbf{L}$:

$\sigma(\Gamma;\mu)=\det(\mu\mathbf{I}-\mathbf{L})=\mu^{n}+c_{1}\mu^{n-1}+\cdots+c_{n-1}\mu+c_{n}.$

First, we observe that the coefficients $c_{i}$ are integers [3, Theorem 7.5],
and in particular, $c_{n}=0$. This forces $\sigma(\Gamma;-m)$ to be an
integer, which is divisible by $m$. Moreover, we have

$\sigma(\Gamma;\mu)=(\mu-\mu_{1})(\mu-\mu_{2})\cdots(\mu-\mu_{n}),$

and since $\mu_{n}=0$, we obtain

$\sigma(\Gamma;-m)=(-1)^{n}m(\mu_{1}+m)(\mu_{2}+m)\cdots(\mu_{n-1}+m).$

The result now follows. $\square$

###### Lemma 3.2

Let a graph $\Gamma$ with $n$ vertices contain $m<n$ universal vertices. Then
$k(\Gamma)$ is divisible by $n^{m-1}$.

Proof. Let $W$ be the set of universal vertices, $\Gamma_{0}=\Gamma-W$ and
$t=n-m$. Clearly, we have $\Gamma=K_{m}\vee\Gamma_{0}$. Let
$\mu_{1}\geqslant\mu_{2}\geqslant\cdots\geqslant\mu_{t}=0$, be the eigenvalues
of $\mathbf{L}_{\Gamma_{0}}$. Since the Laplacian matrix for the complete
graph $K_{m}$ has eigenvalue $0$ with multiplicity $1$ and eigenvalue $m$ with
multiplicity $m-1$, it follows by Lemma 2.1 that the eigenvalues of the
Laplacian matrix $\mathbf{L}_{\Gamma}$ are:

$n,\underbrace{n,\ n,\ \ldots,\ n}_{m-1},\ \underbrace{\mu_{1}+m,\ \mu_{2}+m,\
\ldots,\ \mu_{t-1}+m}_{t-1},\ 0.$

We find immediately using Eq. (1) that

$\kappa(\Gamma)=n^{m-1}(\mu_{1}+m)(\mu_{2}+m)\cdots(\mu_{t-1}+m).$

Finally, since $(\mu_{1}+m)(\mu_{2}+m)\cdots(\mu_{t-1}+m)$ is an integer by
Lemma 3.1, we obtain the result. $\square$

Let $Q_{2^{n}}$ $(n\geqslant 3)$ denote the generalized quaternion group of
order $2^{n}$, which can be presented by

$Q_{2^{n}}=\langle x,y\ |\
x^{2^{n-1}}=1,y^{2}=x^{2^{n-2}},x^{y}=x^{-1}\rangle.$

Moreover, the power graph $\mathcal{P}(Q_{2^{n}})$ has the following form:

$\mathcal{P}(Q_{2^{n}})=K_{2}\vee\Big{(}K_{2^{n-1}-2}\oplus\underbrace{K_{2}\oplus
K_{2}\oplus\cdots\oplus K_{2}}_{2^{n-2}{\rm-times}}\Big{)}.$

Using Lemma 2.1 and Eq. (1), we have the following corollary [16, Theorem
5.2]:

###### Corollary 3.3

Let $n\geqslant 3$ be an integer. Then,
$\kappa(Q_{2^{n}})=2^{(2^{n-2}-1)(2n+1)+4}$.

A finite group $G$ is called an element prime order group (EPO–group) if every
nonidentity element of $G$ has prime order. We can consider the power graph of
an EPO–group $G$ as follows:

$\mathcal{P}(G)=K_{1}\vee\left(\bigoplus_{p\in\pi(G)}c_{p}K_{p-1}\right),$

where $c_{p}$ signifies the number of cyclic subgroups of order $p$ in $G$.
Again, using Lemma 2.1 and Eq. (1), we have the following corollary [16,
Corollary 3.4]:

###### Corollary 3.4

Let $G$ be an EPO–group. Then we have:

$\kappa(G)=\prod_{p\in\pi(G)}p^{(p-2)c_{p}}.$

In particular, we have

$\kappa\left({\mathbb{E}}_{p^{n}}\right)=p^{(p-2)(p^{n}-1)/(p-1)}.$

##  4 Clique–Replaced Graphs

Let $\Gamma$ be a connected graph with vertices $v_{1},\ldots,v_{k}$. Given
positive integers $x_{1},\ldots,x_{k}$, we construct the new graph
$\Gamma_{[x_{1},\ldots,x_{k}]}$ as follows: Replace vertex $v_{i}$ in $\Gamma$
by the complete graph (clique) $K_{x_{i}}$, $i=1,\ldots,k$, and label the
vertex set of $K_{x_{i}}$ for each $i$ as:
$u_{i_{1}},u_{i_{2}},\ldots,u_{i_{x_{i}}}$. Now, if $v_{i}$ is adjacent to
$v_{j}$ in $\Gamma$, then connect all vertices
$u_{i_{1}},u_{i_{2}},\ldots,u_{i_{x_{i}}}$ with all vertices
$u_{j_{1}},u_{j_{2}},\ldots,u_{j_{x_{j}}}$. We call the resulting graph
$\Gamma_{[x_{1},\ldots,x_{k}]}$ the clique–replaced graph. It is clear that
for a fixed $i$, all vertices $u_{i_{1}},u_{i_{2}},\ldots,u_{i_{x_{i}}}$ have
the same degree which is equal to

$n_{i}=x_{i}-1+\sum_{v_{j}\in N_{\Gamma}(v_{i})}x_{j}.$

Put $m_{i}=n_{i}+1=x_{i}+\sum_{v_{j}\in N_{\Gamma}(v_{i})}x_{j},\ \ \
\lambda_{i}=\frac{m_{i}}{x_{i}},\ \ i=1,\ldots,k,$ and
$\Psi=\prod_{i=1}^{k}\lambda_{i}.$ Suppose that $n=x_{1}+\cdots+x_{k}$.

###### Theorem 4.1

With the notation as explained above, we have

$\kappa\left(\Gamma_{[x_{1},\ldots,x_{k}]}\right)=\prod_{i=1}^{k}m_{i}^{x_{i}}\Big{(}\Psi+\sum_{\Lambda}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{1}^{t_{1}}\lambda_{2}^{t_{2}}\cdots\lambda_{k}^{t_{k}}\Big{)}/(\Psi
n^{2}),$ (2)

where $t_{i}\in\\{0,1\\}$, $i=1,\ldots,k$, and the summation is over all
induced subgraphs $\Lambda$ of $\Gamma^{c}$ whose vertex set
$\\{v_{i_{1}},\ldots,v_{i_{s}}\\}$ corresponds to $\\{i_{j}|t_{i_{j}}=0\\}.$

Proof.1 1The idea of this proof is borrowed from [16, Theorem 4.1]. Let
$\Gamma^{\ast}=\Gamma_{[x_{1},\ldots,x_{k}]}$. It is easy to check that, the
matrix $\mathbf{J}+\mathbf{L}_{\Gamma^{\ast}}$ associated with $\Gamma^{\ast}$
has the following block–matrix structure:

$\mathbf{J}+\mathbf{L}_{\Gamma^{\ast}}=\left(\mathbf{D}_{ij}\right)_{1\leqslant
i,j\leqslant k},$ (3)

where $\mathbf{D}_{ij}$ is a matrix of size $x_{i}\times x_{j}$ with

$D_{ij}=\left\\{\begin{array}[]{lll}m_{i}\mathbf{I}&if&i=j,\\\\[5.69046pt]
0&if&i\neq j,\ \ v_{i}\sim v_{j}\ \mbox{in}\ \Gamma,\\\\[5.69046pt]
\mathbf{J}&&\mbox{otherwise}.\end{array}\right.$

We need only to evaluate $\det(\mathbf{J}+\mathbf{L}_{\Gamma^{\ast}})$,
because
$\kappa(\Gamma^{\ast})=\det(\mathbf{J}+\mathbf{L}_{\Gamma^{\ast}})/n^{2}$. In
what follows, $D$ denotes the determinant of the matrix on the right–hand side
of Eq. (3). In order to compute this determinant, we apply the following row
and column operations: We subtract column $j$ from column $j+r$:

$\left\\{\begin{array}[]{ll}j=1+\sum\limits_{l=1}^{h}x_{l},\
h=0,1,2,\ldots,k-1,\\\\[8.5359pt] r=1,2,\ldots,x_{h+1}-1.\end{array}\right.$

Then, we add row $i+s$ to row $i$:

$\left\\{\begin{array}[]{ll}i=1+\sum\limits_{l=1}^{h}x_{l},\
h=0,1,2,\ldots,k-1,\\\\[8.5359pt] s=1,2,\ldots,x_{h+1}-1.\end{array}\right.$

(Note that, when $m>n$, we adopt the convention that $\sum_{i=m}^{n}x_{i}=0$.)
Using the above operations, it is easy to see that

$D=\det\left(\mathbf{M}_{ij}\right)_{1\leqslant i,j\leqslant k},$

where $\mathbf{M}_{ij}$ is a matrix of size $x_{i}\times x_{j}$ with

$\mathbf{M}_{ij}=\left\\{\begin{array}[]{ll}m_{i}\mathbf{I}&\mbox{if}\ \
i=j,\\\\[5.69046pt] 0&\mbox{if}\ \ i\neq j,\ \ v_{i}\sim v_{i}\ \ \mbox{in}\
\Gamma,\\\\[5.69046pt]
x_{i}\mathbf{E}_{1,1}+\mathbf{E}_{2,1}+\cdots+\mathbf{E}_{x_{i},1}&\mbox{otherwise},\end{array}\right.$

where $\mathbf{I}$ is the identity matrix and $\mathbf{E}_{i,j}$ denotes the
square matrix having $1$ in the $(i,j)$ position and $0$ elsewhere.

Therefore, taking out the common factors and developing the determinant along
the columns $j$, $j\neq 1+\sum\limits_{l=1}^{h}x_{l}$, $h=0,1,2,\ldots,k-1$,
one gets

$D=\Phi^{-1}\prod_{i=1}^{k}{m_{i}}^{x_{i}}\cdot\det\left(c_{ij}\right)_{1\leqslant
i,j\leqslant k},$ (4)

where

$c_{ij}=\left\\{\begin{array}[]{cl}\lambda_{i}&\mbox{if}\ \
i=j,\\\\[5.69046pt] 0&\mbox{if}\ \ i\neq j,\ \ v_{i}\sim v_{j}\ \mbox{in}\
\Gamma,\\\\[5.69046pt] 1&\mbox{otherwise}.\end{array}\right.$

As the reader might have noticed, the matrix $\left(c_{ij}\right)_{1\leqslant
i,j\leqslant k}-{\rm diag}(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ is
exactly the adjacency matrix of the graph $\Gamma^{c}$. Consequently, we get

$\det\left(\left[\begin{array}[]{cccc}\lambda_{1}&c_{12}&\ldots&c_{1k}\\\\[2.84544pt]
c_{21}&\lambda_{2}&\ldots&c_{2k}\\\\[2.84544pt]
\vdots&\vdots&\ddots&\vdots\\\\[2.84544pt]
c_{k1}&c_{k2}&\ldots&\lambda_{k}\\\\[2.84544pt]
\end{array}\right]\right)=\Psi+\sum_{\Lambda}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{1}^{t_{1}}\lambda_{2}^{t_{2}}\cdots\lambda_{k}^{t_{k}},$

where $t_{i}\in\\{0,1\\}$, $i=1,2,\ldots,k$, and the summation is over all
induced subgraphs $\Lambda$ of $\Gamma^{c}$ whose vertex set
$\\{v_{i_{1}},\ldots,v_{i_{s}}\\}$ corresponds to $\\{i_{j}|t_{i_{j}}=0\\}.$
This is substituted in Eq. (4):

$D=\Psi^{-1}\prod_{i=1}^{k}{m_{i}}^{x_{i}}\cdot\Big{(}\Psi+\sum_{\Lambda}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{1}^{t_{1}}\lambda_{2}^{t_{2}}\cdots\lambda_{k}^{t_{k}}\Big{)}.$

$\square$

###### Remark 4.2

In this remark, we describe an alternate approach to the computation of
$\kappa\left(\Gamma^{\ast}\right).$ Note that $\mathbf{L}_{\Gamma^{\ast}}$ can
be written as a $k\times k$ block matrix, where, for distinct
$i,j=1,\ldots,k,$ the $(i,j)$ off–diagonal block is either $-J$ or $0$
according as $v_{i}$ is adjacent to $v_{j},$ or not, and where the $j$–th
diagonal block is $m_{j}I-J,j=1,\ldots,k.$ From this block structure, and
applying the technique of equitable partitions (see [4]), it follows readily
that the product of the nonzero eigenvalues of $\mathbf{L}_{\Gamma^{\ast}}$ is
equal to
$\alpha_{2}\cdots\alpha_{k}\left(\prod_{j=1}^{k}\left(m_{j}\right)^{x_{j}-1}\right),$
where $0,\alpha_{2},\alpha_{3},\ldots,\alpha_{k}$ are the eigenvalues of the
the $k\times k$ matrix $\mathbf{S}$ whose entries are given by

$s_{pq}=\left\\{\begin{array}[]{lll}0&&\mbox{if $v_{p}\neq v_{q}$ and $v_{p}$
is not adjacent to $v_{q}$ in $\Gamma$,}\\\\[5.69046pt] -x_{q}&&\mbox{if $p<q$
and $v_{p}$ is adjacent to $v_{q}$ in $\Gamma$},\\\\[5.69046pt]
-x_{p}&&\mbox{if $p>q$ and $v_{p}$ is adjacent to $v_{q}$ in
$\Gamma$},\\\\[5.69046pt] -\sum_{j\neq p}s_{pj}&&\mbox{if $p=q$}.\\\
\end{array}\right.$

(Observe that $\mathbf{S}$ is singular since every row sums to $0.$) In order
to complete the computation of the complexity of $L_{\Gamma^{\ast}}$, we need
to find the product $\alpha_{2}\cdots\alpha_{k}$. For each $j=1,\ldots,k$, let
$\mathbf{S}_{(j)}$ denote the principal sub–matrix of $\mathbf{S}$ formed by
deleting row $j$ and column $j$. Then
$\alpha_{2}\cdots\alpha_{k}=\sum_{j=1}^{k}\det(\mathbf{S}_{(j)}).$

To compute the quantities $\det(\mathbf{S}_{(j)}),j=1,\ldots,k,$ we consider a
weighted directed graph $W$ on vertices $1,\ldots,k,$ whose construction we
now describe. Begin with the graph $\Gamma$ on vertices
$v_{1},v_{2},\ldots,v_{k}$. For each edge $\\{v_{i},v_{j}\\}$ of $\Gamma$, $W$
contains the arcs $i\rightarrow j$ and $j\rightarrow i$; if $i<j$, the weight
of the arc $i\rightarrow j$ in $W$ is $w(i,j)=x_{j}$, and the weight of the
arc $j\rightarrow i$ is $w(j,i)=x_{i}$; if there is no edge between $v_{i}$
and $v_{j}$ in $\Gamma$, then $W$ contains neither an arc from $i$ to $j$ nor
an arc from $j$ to $i$. Fix an index $j$ with $1\leqslant j\leqslant k$. We
can find $\det(\mathbf{S}_{(j)})$ from a generalization of the matrix tree
theorem as follows (see [7]). Let $\tau_{j}$ be the set of all spanning
directed subgraphs of $W$ such that:

(a) the underlying spanning subgraph is a tree; and

(b) in the spanning directed subgraph of $W$, for each vertex $i\neq j$, there
is a directed path from $i$ to $j$.

For each directed graph $\tau\in\tau_{j}$, let the weight of $\tau$,
$\sigma(\tau)$, be the product of the weights of the arcs in $\tau$ (these arc
weights are inherited from $W$). Then
$\det(\mathbf{S}_{(j)})=\sum_{\tau\in\tau_{j}}\sigma(\tau).$ So, we have
$\alpha_{2}\cdots\alpha_{k}=\sum_{j=1}^{k}\sum_{\tau\in\tau_{j}}\sigma(\tau).$
Consequently, we obtain the following formula for $\kappa(\Gamma^{\ast})$:

$\kappa(\Gamma^{\ast})=\frac{\left[\prod_{j=1}^{k}\left(m_{j}\right)^{x_{j}-1}\right]\left[\sum_{j=1}^{k}\sum_{\tau\in\tau_{j}}\sigma(\tau)\right]}{n}.$

Next, we present some applications of the preceding results.

Application 1, clique–replaced paths: Now we consider a particular graph, the
path on $k$ vertices $\Gamma=P_{k}$, where $k\geqslant 3$ is an integer. For
this special case, we apply the technique of Remark 4.2 in order to obtain the
complexity of the graph $\Gamma_{[x_{1},\ldots,x_{k}]}$. For $\Gamma=P_{k},$
the directed graph $W$ of Remark 4.2 is given as follows.

$1$$2$$3$$n-1$$n$$\ldots$$\ldots$

Observe that $\tau_{1}$ contains one directed graph of weight
$x_{1}x_{2}x_{3}\ldots x_{n-1}$, while $\tau_{n}$ contains one directed graph
of weight $x_{2}x_{3}\ldots x_{n}.$ Further, for each $j=2,\ldots,n-1,$ we
find that $\tau_{j}$ contains one directed graph of weight

$(x_{2}\ldots x_{j})(x_{j}\ldots x_{n-1}).$

Consequently for the matrix $\mathbf{S}$ of Remark 4.2, we have

$\sum_{j=1}^{k}\det(\mathbf{S}_{(j)})=x_{1}\ldots
x_{n-1}+\sum_{j=2}^{n-1}x_{j}(x_{2}\ldots x_{n-1})+x_{2}\ldots
x_{n}=(x_{2}\ldots x_{n-1})\sum_{j=1}^{n}x_{j}.$

It now follows that

$\displaystyle\kappa\left(\Gamma_{[x_{1},\ldots,x_{k}]}\right)=\hskip
271.0125pt$
$\displaystyle(x_{1}+x_{2})^{x_{1}-1}\Pi_{j=2}^{n-1}(x_{j-1}+x_{j}+x_{j+1})^{x_{j}-1}(x_{n-1}+x_{n})^{x_{n}-1}(x_{2}\ldots
x_{n-1})\sum_{j=1}^{n}x_{j}.$

Application 2, Cayley’s theorem: In the case when $\Gamma=K_{t}$ and
$x_{1}=\cdots=x_{t}=x$, we have $\Gamma_{[x_{1},\ldots,x_{t}]}=K_{tx}$.
Moreover, in the situation of Theorem 4.1 we have: $n_{i}=\cdots=n_{t}=tx-1$,
$m_{i}=\cdots=m_{t}=tx$, $\lambda_{i}=\cdots=\lambda_{t}=t$ and $\Psi=t^{t}$.
Substitution into Eq. (2) yields

$\kappa(K_{tx})=\left(\prod_{i=1}^{t}(tx)^{x}\right)(t^{t}+0)/(t^{t}(tx)^{2})=(tx)^{tx-2},$

which is equivalent to Cayley’s result.

Application 3, complexity of $\mathcal{P}(\mathbb{Z}_{n})$: Given a natural
number $n$, the divisor graph $D(n)$ of $n$ is the graph with vertex set
$\pi_{d}(n)=\\{d_{1},\ldots,d_{k}\\}$, the set of all divisors of $n$, in
which two distinct divisors $d_{i}$ and $d_{j}$ are adjacent if and only if
$d_{i}|d_{j}$ or $d_{j}|d_{i}$. Let $d_{1}>d_{2}>\cdots>d_{k}$ (evidently
$d_{1}=n$ and $d_{k}=1$). This shows that (see also [13, Theorem 2.2]):

$\mathcal{P}(\mathbb{Z}_{n})=D(n)_{[\phi(d_{1}),\ldots,\phi(d_{k})]}.$ (5)

In what follows, we put $\Gamma=D(n)$, $n_{i}=\phi(d_{i})-1+\sum_{d_{j}\in
N_{\Gamma}(d_{i})}\phi({d_{j}})$, $m_{i}=n_{i}+1$,
$\lambda_{i}=\frac{m_{i}}{\phi(d_{i})},\ \ i=1,\ldots,k,$ and
$\Phi=\prod_{i=2}^{k-1}\lambda_{i},\ \ \Psi=\prod_{i=1}^{k}\lambda_{i}.$ By
using Theorem 4.1, we have the following alternate proof of a result in [16].

###### Corollary 4.3

[16, Theorem 4.1] Let $d_{1}>d_{2}>\cdots>d_{k}$ be the divisors of a positive
integer $n$. With the notation as above, we have

$\kappa(\mathbb{Z}_{n})=\prod_{i=1}^{k}m_{i}^{\phi(d_{i})}\Big{(}\Phi+\sum_{\Lambda}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{2}^{t_{2}}\lambda_{3}^{t_{3}}\cdots\lambda_{k-1}^{t_{k-1}}\Big{)}/(\Phi
n^{2}),$

where $t_{i}\in\\{0,1\\}$, $2\leqslant i\leqslant k-1$, and the summation is
over all induced subgraphs $\Lambda$ of $\Gamma^{c}\setminus\\{d_{1},d_{k}\\}$
whose vertex set $\\{d_{i_{1}},\ldots,d_{i_{s}}\\}$ corresponds to
$\\{i_{j}|t_{i_{j}}=0\\}.$

Proof. Using Eq. (5) and Theorem 4.1, we obtain

$\kappa(\mathbb{Z}_{n})=\prod_{i=1}^{k}m_{i}^{\phi(d_{i})}\Big{(}\Psi+\sum_{\Lambda^{\prime}}\det\mathbf{A}_{\Gamma^{c}}(\Lambda^{\prime})\lambda_{1}^{t_{1}}\lambda_{2}^{t_{2}}\cdots\lambda_{k}^{t_{k}}\Big{)}/(\Psi
n^{2}),$ (6)

where $t_{i}\in\\{0,1\\}$, $i=1,\ldots,k$, and the summation is over all
induced subgraphs $\Lambda^{\prime}$ of $\Gamma^{c}$ whose vertex set
$\\{d_{i_{1}},\ldots,d_{i_{s}}\\}$ corresponds to $\\{i_{j}|t_{i_{j}}=0\\}.$
Since $\deg_{\Gamma}(d_{1})=\deg_{\Gamma}(d_{k})=k-1$, we obtain
$\deg_{\Gamma^{c}}(d_{1})=\deg_{\Gamma^{c}}(d_{k})=0$. Thus, if an induced
subgraph $\Lambda^{\prime}$ of $\Gamma^{c}$ contains $d_{1}$ or $d_{k}$, then
$\det\mathbf{A}_{\Gamma^{c}}(\Lambda^{\prime})=0$, while if it does not
contain $d_{1}$ and $d_{k}$, then the sum
$\sum_{\Lambda^{\prime}}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{1}^{t_{1}}\lambda_{2}^{t_{2}}\cdots\lambda_{k}^{t_{k}}$
is divisible by $\lambda_{1}\lambda_{k}$. Hence, we can write

$\sum_{\Lambda^{\prime}}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{1}^{t_{1}}\lambda_{2}^{t_{2}}\cdots\lambda_{k}^{t_{k}}=\lambda_{1}\lambda_{k}\sum_{\Lambda}\det\mathbf{A}_{\Gamma^{c}}(\Lambda)\lambda_{2}^{t_{2}}\cdots\lambda_{k-1}^{t_{k-1}}$

where the $\Lambda$ run over all induced subgraphs of
$\Gamma^{c}\setminus\\{d_{1},d_{k}\\}$ whose vertex set
$\\{d_{i_{1}},\ldots,d_{i_{s}}\\}$ corresponds to $\\{i_{j}|t_{i_{j}}=0\\}.$
Substituting this in Eq. (6) and simplifying now yields the result. $\square$

##  5  Computing the Complexity $\kappa(G)$

In this section we consider the problem of finding the complexity of power
graphs associated with certain finite groups.

###  5.1 The simple groups $L_{2}(q)$

Let $q=p^{n}\geqslant 4$ for a prime $p$ and some $n\in{\mathbb{N}}$. We are
going to find an explicit formula for $\kappa(L_{2}(q))$. Before we start, we
need some well known facts about the simple groups $G=L_{2}(q)$, $q\geqslant
4$, which are proven in [8]:

  * (a)

$|G|=q(q-1)(q+1)/k$ and $\mu(G)=\\{p,(q-1)/k,(q+1)/k\\}$, where $k={\rm
gcd}(q-1,2)$.

  * (b)

Let $P$ be a Sylow $p$–subgroup of $G$. Then $P$ is an elementary abelian
$p$–group of order $q$, which is a TI–subgroup, and $|N_{G}(P)|=q(q-1)/k$.

  * (c)

Let $A\subset G$ be a cyclic subgroup of order $(q-1)/k$. Then $A$ is a
TI–subgroup and the normalizer $N_{G}(A)$ is a dihedral group of order
$2(q-1)/k$.

  * (d)

Let $B\subset G$ be a cyclic subgroup of order $(q+1)/k$. Then $B$ is a
TI–subgroup and the normalizer $N_{G}(B)$ is a dihedral group of order
$2(q+1)/k$.

We recall that a subgroup $H\leqslant G$ is a TI–subgroup (trivial
intersection subgroup) if for every $g\in G$, either $H^{g}=H$ or $H\cap
H^{g}=\\{1\\}$.

###### Theorem 5.1

Let $q=p^{n}$, with $p$ prime and $n\in{\mathbb{N}}$ and let $G=L_{2}(q)$.
Then we have:

$\kappa(G)=p^{\frac{(q^{2}-1)(p-2)}{p-1}}\cdot\kappa\left({\mathbb{Z}}_{\frac{q-1}{k}}\right)^{q(q+1)/2}\cdot\kappa\left({\mathbb{Z}}_{\frac{q+1}{k}}\right)^{q(q-1)/2},$

where $k={\rm gcd}(q-1,2)$, except exactly in the cases $(p,n)=(2,1)$,
$(3,1)$. In particular, we have

  * (1)

$A_{5}\cong L_{2}(5)\cong L_{2}(4)$ and $\kappa(A_{5})=3^{10}\cdot 5^{18}$
(see [16]).

  * (2)

$L_{3}(2)\cong L_{2}(7)$ and $\kappa(L_{3}(2))=2^{84}\cdot 3^{28}\cdot
7^{40}$.

  * (3)

$A_{6}\cong L_{2}(9)$ and $\kappa(A_{6})=2^{180}\cdot 3^{40}\cdot 5^{108}.$

Proof. Let $q=p^{n}$, with $p$ prime and $n\in{\mathbb{N}}$, and
$(p,n)\neq(2,1),(3,1)$. As already mentioned, $G$ contains abelian subgroups
$P$, $A$ and $B$, of orders $q$, $(q-1)/k$ and $(q+1)/k$, respectively, every
distinct pair of their conjugates intersects trivially, and every element of
$G$ is a conjugate of an element in $P\cup A\cup B$. Let

$G=N_{P}u_{1}\cup\cdots\cup N_{P}u_{r}=N_{A}v_{1}\cup\cdots\cup
N_{A}v_{s}=N_{B}w_{1}\cup\cdots\cup N_{B}w_{t},$

be coset decompositions of $G$ by $N_{P}=N_{G}(P)$, $N_{A}=N_{G}(A)$ and
$N_{B}=N_{G}(B)$, where $r=[G:N_{P}]=q+1$, $s=[G:N_{A}]=q(q+1)/2$ and
$t=[G:N_{B}]=(q-1)q/2$. Then, we have

$G=P^{u_{1}}\cup\cdots\cup P^{u_{r}}\cup A^{v_{1}}\cup\cdots\cup A^{v_{s}}\cup
B^{w_{1}}\cup\cdots\cup B^{w_{t}}.$ (7)

Applying Theorem 3.4 (b) in [16] to Eq. (7), we obtain

$\kappa(G)=\kappa_{G}(P)^{r}\cdot\kappa_{G}(A)^{s}\cdot\kappa_{G}(B)^{t}=\kappa\left({\mathbb{E}}_{q}\right)^{r}\cdot\kappa\left({\mathbb{Z}}_{\frac{q-1}{k}}\right)^{s}\cdot\kappa\left({\mathbb{Z}}_{\frac{q+1}{k}}\right)^{t},$

and so by Corollary 3.4, we get
$\kappa(G)=\left(p^{\frac{q-1}{p-1}(p-2)}\right)^{r}\cdot\kappa\left({\mathbb{Z}}_{\frac{q-1}{k}}\right)^{s}\cdot\kappa\left({\mathbb{Z}}_{\frac{q+1}{k}}\right)^{t}.$
The result follows. $\square$

###  5.2 Extra–special $p$–groups of order $p^{3}$

In the sequel, $P$ will be a $p$–group, with $p$ prime. We recall below some
facts about extra–special groups and other necessary information. We begin
with the definition of the extra special groups. A $p$–group $P$ is called
extra–special if $Z(P)=[P,P]=\Phi(P)\cong\mathbb{Z}_{p}$, where $\Phi(P)$ is
the Frattini subgroup of $P$. If $P$ is an extra–special $p$–group, then the
order of $P$ is $p^{2n+1}$ for some positive integer $n$. The smallest
nonabelian extra–special groups are of order $p^{3}$. When $p=2$, there are,
up to isomorphism, two extra–special $2$–group of order $8$, namely, $D_{8}$
and $Q_{8}$. The exponent of both of these groups is $p^{2}=4$. Furthermore,
from [16, Table 1], we have $\kappa(D_{8})=2^{4}$ and $\kappa(Q_{8})=2^{11}$.

For each odd prime $p$, up to isomorphism, there are just two non–isomorphic
extra–special $p$–groups of order $p^{3}$. The first one has exponent $p$,
which is called the Heisenberg group and denoted by $H_{p}$. In fact, $H_{p}$
as a subgroup of ${\rm GL}(3,p)$ can be presented in the following way:

$H_{p}=\left\\{\left(\begin{array}[]{lll}1&0&0\\\ x&1&0\\\
z&y&1\end{array}\right)\ \Bigg{|}\ x,y,z\in{\rm GF}(p)\right\\}.$

The other one has exponent $p^{2}$, which is denoted by $A_{p}$, and contains
transformations $x\mapsto ax+b$ from $\mathbb{Z}_{p^{2}}$ to
$\mathbb{Z}_{p^{2}}$, where $a\equiv 1\pmod{p}$ and $b\in\mathbb{Z}_{p^{2}}$.

The groups $H_{p}$ and $A_{p}$ are usually presented as:

$H_{p}=\langle x,y,z\ |\ x^{p}=y^{p}=z^{p}=1,[x,y]=z,[x,z]=[y,z]=1\rangle,$

and

$A_{p}=\langle x,y\ |\ x^{p}=y^{p^{2}}=1,y^{x}=y^{p+1}\rangle.$

###### Theorem 5.2

Let $p$ be an odd prime. Then, we have:

  * (a)

$\kappa(H_{p})=p^{(p-2)(p^{2}+p+1)}$.

  * (b)

$\kappa(A_{p})=p^{2p^{3}-p-5}$.

Proof. (a) Clearly, we have

$H_{p}=\bigcup_{j=1}^{p^{2}+p+1}C_{j},$

where $C_{j}\subset H_{p}$ is a subgroup of order $p$, and $C_{i}\cap C_{j}=1$
for $i\neq j$. Now, by Theorem 3.4 (b) in [16], we obtain

$\kappa(H_{p})=\prod_{j=1}^{p^{2}+p+1}\kappa(C_{j})=\prod_{j=1}^{p^{2}+p+1}p^{p-2}=p^{(p-2)(p^{2}+p+1)},$

as desired.

(b) In this case, we have

$A_{p}=\bigcup_{j=1}^{p+1}B_{j},$

where $B_{j}\subset A_{p}$ is a subgroup of order $p^{2}$, and $B_{i}\cap
B_{j}=Z(A_{p})$ for $i\neq j$. Therefore, the power graph of $A_{p}$ has the
following form

${\cal P}(A_{p})=K_{p}\vee\left[(p+1)K_{p^{2}-p}\right].$

It follows by Lemma 2.1 that the eigenvalues of Laplacian matrix
$\mathbf{L}_{{\cal P}(A_{p})}$ are:

$p^{3},\underbrace{p^{2},\ p^{2},\ \ldots,\ p^{2}}_{p-1},\ \underbrace{p^{2},\
p^{2},\ \ldots,\ p^{2}}_{p^{3}-2p-1},\ \underbrace{p,\ p,\ \ldots,\ p}_{p},\
0.$

Using Eq. (1), we get $\kappa(A_{p})=p^{2p^{3}-p-4}$, as required. $\square$

###  5.3 Frobenius groups

Suppose $1\subset H\subset G$ and $H\cap H^{g}=1$ whenever $g\in G\setminus
H$. Then $H$ is a Frobenius complement in $G$. A group which contains a
Frobenius complement is called a Frobenius group. A famous theorem of
Frobenius asserts that in a Frobenius group $G$ with a Frobenius complement
$H$, the set

$F=\left(G\setminus\bigcup_{g\in G}H^{g}\right)\cup\\{1\\},$

is a normal subgroup of $G$ and $G=FH$, $F\cap H=1$. We call $F$ the Frobenius
kernel of $G$.

###### Theorem 5.3

Let $G$ be a Frobenius group, $H$ a Frobenius complement and $F$ the Frobenius
kernel corresponding with $H$. Then, we have:

$\kappa(G)=\kappa_{G}(F)\kappa_{G}(H)^{|F|}.$

In particular, if $G$ is a nonabelian group of order $pq$, where $p<q$ are
primes, then $\kappa(G)=q^{q-2}p^{(p-2)q}.$

Proof. Let $G$ be a Frobenius group, let $H$ be its Frobenius complement and
$F$ its Frobenius kernel. Then $G$ can be written as the union of its
subgroups:

$G=F\cup\bigcup_{g\in F}H^{g}.$

Again, it follows from Theorem 3.4 (b) in [16] that

$\kappa(G)=\kappa_{G}(F)\prod_{g\in
F}\kappa_{G}(H^{g})=\kappa_{G}(F)\kappa_{G}(H)^{|F|},$

as required. $\square$

Acknowledgments

This work was done while the second author had a visiting position at the
Department of Mathematical Sciences, Kent State University, USA. He is
thankful for the hospitality of the Department of Mathematical Sciences of
KSU. The research of the first author is supported by the Natural Sciences and
Engineering Research Council of Canada under grant number RGPIN/6123–2014.

## References

  * [1] J. H. Abawajy, A. V. Kelarev and M. Chowdhury, Power graphs: a survey, Electronic J. Graph Theory and Applications, 1 (2013) (2), 125–147.
  * [2] I. Chakrabarty, S. Ghosh and M. K. Sen, Undirected power graphs of semigroups, Semigroup Forum, 78 (2009), 410–426.
  * [3] N. Biggs, Algebraic Graph Theory, Cambridge University Press, London, 1974.
  * [4] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2012.
  * [5] P. J. Cameron, The power graph of a finite group. II, J. Group Theory, 13(6)(2010), 779–783.
  * [6] A. Cayley, A theorem on trees. Quart. J. Math., 23 (1889), 376–378.
  * [7] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods, 3(3) (1982), 319–329.
  * [8] B. Huppert, Endliche Gruppen I, Springer, Berlin, 1967.
  * [9] M. I. Isaacs, Finite Group Theory, Graduate Studies in Mathematics, 92. American Mathematical Society, Providence, RI, 2008.
  * [10] A. V. Kelarev, Graph Algebras and Automata, Marcel Dekker, New York, 2003.
  * [11] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, Contrib. General Algebra, 12 (2000), 229–235.
  * [12] A. V. Kelarev, J. Ryan and J. Yearwood, Cayley graphs as classifiers for data mining: The influence of asymmetries, Discrete Mathematics, 309(17)(2009), 5360–5369.
  * [13] Z. Mehranian, A. Gholami, and A. R. Ashrafi, A note on the power graph of a finite group, Int. J. Group Theory 5(1) (2016), 1–10.
  * [14] R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl., 278 (1998), 221–236.
  * [15] A. R. Moghaddamfar, S. Rahbariyan, and W. J. Shi, Certain properties of the power graph associated with a finite group, J. Algebra Appl., 13(7) (2014), 1450040, 18 pp.
  * [16] A. R. Moghaddamfar, S. Rahbariyan, S. Navid Salehy and S. Nima Salehy, The number of spanning trees of power graphs associated with specific groups and some applications, Ars Combinatoria, 113 (2017), 269–296.