# Intertwining of magnetism and charge ordering
in kagome FeGe

Sen Shao  Division of Physics and Applied Physics, School of Physical and
Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link,
637371, Singapore  Jia-Xin Yin  Department of Physics, Southern University of
Science and Technology, Shenzhen, Guangdong 518055, China  Ilya Belopolski
RIKEN Center for Emergent Matter Science (CEMS), Wako, Saitama 351-0198, Japan
Jing-Yang You  Department of Physics, National University of Singapore, 2
Science Drive 3, Singapore 117551  Tao Hou  Division of Physics and Applied
Physics, School of Physical and Mathematical Sciences, Nanyang Technological
University, 21 Nanyang Link, 637371, Singapore  Hongyu Chen  Division of
Physics and Applied Physics, School of Physical and Mathematical Sciences,
Nanyang Technological University, 21 Nanyang Link, 637371, Singapore  Yuxiao
Jiang  Laboratory for Topological Quantum Matter and Advanced Spectroscopy
(B7), Department of Physics, Princeton University, Princeton, New Jersey
08544, USA  Md Shafayat Hossain  Laboratory for Topological Quantum Matter and
Advanced Spectroscopy (B7), Department of Physics, Princeton University,
Princeton, New Jersey 08544, USA  Mohammad Yahyavi  Division of Physics and
Applied Physics, School of Physical and Mathematical Sciences, Nanyang
Technological University, 21 Nanyang Link, 637371, Singapore  Chia-Hsiu Hsu
Division of Physics and Applied Physics, School of Physical and Mathematical
Sciences, Nanyang Technological University, 21 Nanyang Link, 637371, Singapore
Yuan Ping Feng  Department of Physics, National University of Singapore, 2
Science Drive 3, Singapore 117551  Arun Bansil  Department of Physics,
Northeastern University, Boston, MA 02115, USA  M. Zahid Hasan  Laboratory for
Topological Quantum Matter and Advanced Spectroscopy (B7), Department of
Physics, Princeton University, Princeton, New Jersey 08544, USA  Guoqing Chang
<EMAIL_ADDRESS>Division of Physics and Applied Physics, School of
Physical and Mathematical Sciences, Nanyang Technological University, 21
Nanyang Link, 637371, Singapore

###### Abstract

Recent experiments report a charge density wave (CDW) in the antiferromagnet
FeGe, but the nature of the charge ordering and the associated structural
distortion remains elusive. We discuss the structural and electronic
properties of FeGe. Our proposed ground state phase accurately captures atomic
topographies acquired by scanning tunneling microscopy. We show that the
2$\times$2$\times$1 CDW likely results from the Fermi surface nesting of
hexagonal-prism-shaped kagome states. FeGe is found to exhibit distortions in
the positions of the Ge atoms instead of the Fe atoms in the kagome layers.
Using in-depth first-principles calculations and analytical modeling, we
demonstrate that this unconventional distortion is driven by the intertwining
of magnetic exchange coupling and CDW interactions in this kagome material.
Movement of Ge atoms from their pristine positions also enhances the magnetic
moment of the Fe kagome layers. Our study indicates that magnetic kagome
lattices provide a material candidate for exploring the effects of strong
electronic correlations on the ground state and their implications for
transport, magnetic, and optical responses in materials.

KEYWORDS: kagome antiferromagnet, charge density wave, intertwined orders,
first-principles calculations, crystal structure, electronic properties

##  1 Introduction

Density wave orders in two-dimensional and layered materials are known to
exhibit rich interplay with their underlying lattice motifs1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13. For example, the honeycomb lattice exhibits the
kekulé bond-density-wave order1, 2. In graphene, such kekulé order can give
rise to massive Dirac fermions via chiral symmetry breaking, a mechanism
analogous to dynamical mass generation of fundamental fermions in the Standard
Model 3. Similarly, the kagome lattice supports a rich tapestry of charge
density wave (CDW) orders 6, 7, 8, 9, 10, 11, 12, 13. In KV3Sb5, the CDW is
associated with time-reversal-breaking orbital current order, closely related
to the Haldane model for Chern insulators and the Varma model for the cuprate
superconductors 14. The exploration of new quantum materials exhibiting
density wave orders under broken time-reversal symmetry, especially in the
honeycomb and kagome lattices, promises the discovery of exotic many-body
quantum phases, including the exotic orbital current orders15, unconventional
topological superconductors14, 16, 17 and phases supporting fractional
excitations 1.

The antiferromagnet FeGe assumes a crystal structure comprised of alternating
honeycomb and kagome atomic layers. Recent neutron scattering, spectroscopy
and transport measurements suggest a CDW in FeGe, providing an example of a
CDW in a kagome magnet 18, 19. However, the nature of the structural
distortion and the mechanism driving the CDW remain elusive. Here, by
analyzing in-depth first-principles calculations with optimized atomic
structure, we predict that FeGe hosts an unusual hybrid kagome-honeycomb CDW.
We find a $2\times 2\times 1$ CDW, which takes the form of a generalized
kekulé distortion of the Ge honeycomb layers, while the Fe kagome layers
almost remain unchanged. Our analysis indicates that the honeycomb generalized
kekulé distortion is likely to be driven by the Fermi surface nesting of
kagome electronic states. Our predicted honeycomb-kagome CDW is further
substantiated by the matching with the atomic distribution of the electronic
density of states data obtained via scanning tunneling microscopy (STM).

###  1.1 Results and discussion

The pristine phase of FeGe is in the space group $\textit{P}6/\textit{mmm}$
(No.191) [Figure 1a], where Fe atoms form kagome layers. There are two types
of Ge atoms, one is located at the hexagonal center of the Fe kagome layer and
the other forms honeycomb layers located in between the two kagome layers. Our
calculation shows that the pristine phase is inter-layer antiferromagnetic
with magnetic moment perpendicular to the kagome layer. By using the high-
performance structure research software CALYPSO20, 21, 22, we identify four
types of antiferromagnetic FeGe supercell structures (Note 1 in Supporting
Information). Among these, the 2$\times$2$\times$1 and 2$\times$2$\times$2
supercell structures are the lowest energy structures that compete with the
pristine phase after the zero-point energy is included. This is consistent
with experimental results18, 19, where the 2$\times$2$\times$1 and
2$\times$2$\times$2 CDW interactions have been reported. Our ground state
2$\times$2$\times$1 structures are shown in Figure 1b. The 2$\times$2$\times$1
structure shares the $\textit{P}6/\textit{mmm}$ space group with the pristine
phase. Arrows indicate the movement of atoms in the supercell in the ab-plane.
The Fe kagome layers are seen to be almost unchanged. The Ge atoms, which form
the honeycomb lattice in different layers, move in opposite directions. As a
result of this distortion, we have two inequivalent Fe atoms and six
inequivalent Ge atoms in the 2$\times$2$\times$1 supercell.

To understand the transition between the phases, we plot the computed phonon
band structure of the pristine and the 2$\times$2$\times$1 CDW phase in Figure
1c,d, respectively. Both these phases are seen to be dynamically stable. This
should be contrasted sharply with most of the previously reported materials,
which display a CDW phase transition, where the phonon spectrum of the
pristine phase exhibits a softening mode at low temperature26, 27, 28, 29. To
further understand the nature of the phase transition, we consider the Gibbs
free energy of 2$\times$2$\times$1 CDW phase relative to the pristine phase,
which is expected to increase with increasing temperature (Figure 1e). At low
temperatures, the energy difference is negative, but it changes sign at 80 K,
where the phase transition takes place. This is close to the results of the
latest experiments18, 19, where the CDW transition is reported at 100-110 K.
We further consider the energy barrier in the reaction pathway between the
pristine and the 2$\times$2$\times$1 CDW phase in Figure 1f, where both phases
are local minima in energy and the CDW phase shows slightly lower energy.
There is an energy barrier of $\sim$3.06 meV/atom along the reaction path.
This is different from the case of the kagome family AV3Sb5 (A = K, Rb, Cs)
11, where the pristine phase sits at a saddle point of a potential energy
surface, so that the softening mode will trigger a spontaneous change to a
lower energy phase.

To further prove that the distorted 2$\times$2$\times$1 CDW phase correctly
captures the experimentally observed CDW ground state, we show our STM
measurements of the density of states and compare these with our theoretical
predictions. Figure 2a simulates the charge distribution of the pristine phase
at the Fe kagome surface. The charge is mainly distributed on the Fe-triangles
and its distribution will not change significantly as the energy moves around
the Fermi level of the pristine phase. In contrast, in the 2$\times$2 CDW
phase, STM measurements show a clear Fermi-level-dependent charge distribution
(Figure 2b). At 20 and 40meV above the Fermi energy, the charge is mainly
distributed in the Fe-hexagon and its adjacent Fe-triangles, but not in its
neighboring Fe-hexagons. At 40 meV below the Fermi energy, the center of the
bright Fe-hexagons becomes dimmer, and the charge is mainly distributed around
the boundary of the Fe-hexagons and Fe-triangles. The surface charge
distribution based on the 2$\times$2$\times$1 CDW phase presented in Figure 2c
captures the behavior seen in STM plots. These results show that our predicted
2$\times$2$\times$1 CDW phase correctly captures the distorted 2$\times$2
charge ordering structure observed experimentally in FeGe.

We turn now to discuss the origin of the CDW interaction that induces atomic
distortions. In this connection, we first checked the Fermi surface of the
pristine phase (Figure 3a-c). Interestingly we observed a very similar
hexagonal Fermi surface both at ${k_{z}}$=0 and ${k_{z}}$=$\pi$ planes
(colored blue in Figure 3a). This indicates that the colored states have very
small dispersion along the $z$-direction and that a hexagonal prismatic shape
is present in the Fermi surface (Figure S5). The Fermi surface in the $yz$
plane also shows this behavior (Figure 3b,c). The momentum separation of the
quasi-one-dimensional parallel sides of the hexagonal-prism-shaped Fermi
surface is about half of the unit vector of the pristine phase, as indicated
by the yellow arrows in Figure 3a-c. To further demonstrate the role of Fermi-
surface nesting in the CDW formation, we calculate the zero frequency
susceptibility ${\chi^{0}(q,\omega=0)}$, i.e. the Lindhard response
function31, 32, 33, 34, to determine the nesting vector. The two-dimensional
renormalized Lindhard function is plotted in Figure 3d. Indeed the maxima are
located at the center of the boundary of Brillouin zone (BZ) with the nesting
vectors ${\textbf{{Q}}_{1}}$ = (0.5, 0) and $\textbf{{Q}}_{2}$=(0, 0.5). This
is in accord with the corresponding experimental observations18, 19. These
results indicate that the Fermi-surface nesting is the likely driver of the
2$\times$2$\times$1 CDW phase. The role of electron-phonon coupling in this
connection, however, deserves further attention.

To gain further insight into the Fermi surface nesting scenario, we consider
the electronic band structure of the pristine phase. Figure 4a depicts the
electronic band structure of the pristine phase with SOC. The Fe-$d$ orbital-
projected band structures to focus on the singularity of the kagome lattice
are shown in Figure 4b,c. The ’flat bands’ are seen to lie slightly above the
Fermi energy with fairly large bandwidths, which is consistent with previous
studies30. We identify five Dirac cones (DCs) derived from the kagome lattice,
which display van Hove singularities at the M/L points and Dirac points at the
K/H points. A schematic diagram of these Dirac cones is shown in Figure 4d.
Notably, DC2 and DC3 possess similar dispersions, but the related van Hove
singularities lie at different energies. This is because the
$\textit{d${}_{xy}$}/$d${}_{x^{2}-y^{2}}$ orbitals, which dominate DC2 and
DC3, lie in the kagome plane, and their hybridization with the upper and lower
Ge atoms is weak. In contrast, the other three Dirac cones are mainly
contributed by the out-of-plane $\textit{d${}_{xz}$}/$dyz orbitals, and due to
their strong hybridization with Ge orbitals, they show different dispersions
in the ${k_{z}}$=0 and ${k_{z}}$=$\pi$ planes. The DC1 and DC3 Dirac cones
shown by the solid-blue lines in Figure 4d play a major role in producing the
hexagonal prism highlighted in Figure 3. The kagome-derived DC1 plays a major
role in the hexagonal Fermi surface in the ${k_{z}}$=0 plane, while the main
contribution to the hexagonal Fermi surface gradually becomes DC3 as the 2D
Fermi surface lifts from ${k_{z}}$=0 to $\pi$.

Now we discuss the effects of CDW interaction on the band structure. The E-k
dispersion in the 2$\times$2$\times$1 CDW phase with the inclusion of SOC is
given in Figure 4e. Most kagome features: the Dirac points and the flat bands
can still be observed in the 2$\times$2$\times$1 CDW phase. The main effects
of the CDW interactions are on states that are nested by the CDW Q-vectors.
Taking the constant energy contour at kz=$\pi$ at 10 meV below the Fermi
energy as an example, the blue hexagonal contour in the pristine phase changes
into a circle-like contour in the 2$\times$2$\times$1 CDW phase (Figure 4f and
S7). This evolution of the constant energy contours weakens Fermi surface
nesting and induces CDW instability. Energy dispersion along with L′-A′-L′ in
cut2 plane of the pristine phase is shown in Figure 4g, and the unfolded band
structure of the 2$\times$2$\times$1 CDW phase along the same path is shown in
Figure 4h. A clear gap-opening due to CDW interactions can be seen along this
path.

We emphasize that the Fermi surface nesting comes from the kagome-derived
Dirac cones, but structural distortions originate from motions of the Ge
atoms, which lead to the formation of Ge bonds along the c axis and
generalized kekulé distortions35, 36, 37 in the honeycomb layer: the resulting
shortest bonds form an ”O”/”Y” shaped pattern as shown in Figure 4i. In the
nonmagnetic kagome material AV3Sb5 (A=K, Rb, and Cs), the star of David (SoD)
and the inverse star of David (ISD) distortion of the kagome layer decrease
the total energy (Figure 4j). However, in FeGe, the Fermi surface nesting
related to Fe atoms drives the motion of the Ge atoms instead. This
unconventional distortion is caused by the intertwining of magnetism and CDW
interactions. Our analysis shows that the SoD/ISD distortion in the Fe kagome
layers will increase the total energy (Figure 4k). Our Heisenberg model-based
calculations (Note 3 in Supporting Information) yield a similar behavior
(Figure 4l). These results show that the magnetic exchange coupling tends to
force the Fe atoms to remain in their original positions in the kagome layer,
while the CDW interaction tends to move the Fe atoms away from their original
positions. As a consequence of these two competing tendencies, the Fermi
surface nesting forces are transmitted to the Ge atoms through the
hybridization of Fe and Ge orbitals (Figure S10), resulting in the motion of
Ge atoms in the 2$\times$2$\times$1 CDW phase.

In the latest experiments, the observed enhancement of the magnetic moment may
be explained by the chiral flux phase of circulating currents and the effects
of electronic correlations independent of Fermi surface nesting18. Our
calculations show that the magnetic moment of the Fe atom in the
2$\times$2$\times$1 CDW phase is 1.48 $\mu_{B}$, which is greater than the
value of 1.44 $\mu_{B}$ in the pristine phase. This magnetic moment
enhancement found in our work is consistent with aforementioned experimental
observations. To better understand this effect, we calculated the spin-
resolved partial density of states associated with Fe atoms. In the
2$\times$2$\times$1 CDW phase, the spin-up (spin-down) states increase
(decrease) in the top kagome layers and behave in an opposite manner in the
bottom Fe-kagome layer, which leads to the magnetic enhancement of Fe atoms
(Figure S11). To analyze whether such an enhancement is related to Ge motions,
we calculated the change of magnetic moment with the size of Ge motions. As
shown in Figure 4m, the magnetic moment increases approximately linearly with
Ge displacement indicating that the motions of Ge atoms can lead to greater
spin splitting of Fe atoms, which, in turn, enhances the magnetic moments.

##  2 Conclusion

In summary, we have investigated the structural and electronic properties of
antiferromagnetic kagome metal FeGe. Our in-depth analysis of the ground state
2$\times$2$\times$1 CDW phase indicates that this phase will transform into
the pristine phase at a temperature of $\sim$80 K, which is comparable to the
corresponding experimentally measured transition temperature of $\sim$100-110
K18, 19. Our predicted 2$\times$2$\times$1 CDW phase accurately captures the
salient topographic and spectroscopic features our STM/STS experiments and the
experimentally observed enhancement of the magnetic moment18, 19. Our study
unveils the presence of an unconventional intertwining between magnetism and
CDW interactions in kagome magnets (Figure 4n), which forces Fe atoms of the
kagome layers to remain at the original positions, but leads to the motion of
Ge atoms and the formation of a generalized kekulé distortion in the Ge
honeycomb layers. Since Kekulé distortions in graphene open conduction
channels between the valleys that influence optical absorption and
conductivity37, we expect the generalized kekulé distortions in FeGe to also
yield interesting physical effects. Our study provides insight into the CDW
phase and indicates that further exploration of the topological nature of the
ground state of magnetic kagome-honeycomb lattices and their transport and
optical responses will be interesting. We also identify the structure of the
2$\times$2$\times$2 CDW phase and the structures of the two related metastable
1$\times$${\sqrt{3}}$$\times$1 and 2$\times$2${\sqrt{3}}$$\times$1 phases
(Table S1), which could provide theoretical support for future experiments.

##  3 Methods

The CDW phases are proposed based on the structure search method implemented
in the CALYPSO 20, 21, 22 code. First, we fix the positions of the Ge atoms in
the volume of the 2$\times$2$\times$1 pristine phase and generate positions of
the Fe atoms randomly. Then, we fix the positions of the Fe atoms and generate
the positions of Ge atoms randomly. After generating such 2$\times$2$\times$1
structures, we relax them using first-principles calculations using the Vienna
ab-initio Simulation Package (VASP)38 within the Perdew-Burke-Ernzerhof
exchange-correlation functional39. The projector augmented-wave method 40 is
implemented with 3$\textit{d}^{7}$4$\textit{s}^{1}$ and
4$\textit{s}^{2}$4$\textit{p}^{2}$ treated as valence electrons for Fe and Ge
atoms, respectively. The cut-off energy of 520 eV and a dense k-point sampling
of the Brillouin zone with a spacing of 2$\pi$ $\times$ 0.03 Å-1 are used to
ensure the convergence of enthalpy within 1 meV/atom. The phonon spectra are
calculated with the frozen phonon method and the Gibbs free energy is
simulated in the framework of quasi-harmonic approximation as employed in
PHONOPY 41 code. The post-processing of band and DOS calculations is performed
by the VASPKIT tool 42. The pristine phase of FeGe is found to be dynamically
stable at 0 K, indicating that the CDW transition is induced by electrons
nested at the Fermi level. Therefore, we focus on the electronic contribution
to the CDW instability and interpret our results using a simple picture of the
Fermi-surface nesting vectors. We also carry out an accurate calculation of
the electronic susceptibility with $\omega$=0 Lindhard response function. In
the constant-matrix-element approximation,43, 34 $\chi$0(q,0) is given by:

$\chi$0(q,0) = $\sum_{K}$$\frac{f_{K}(1-f_{K+q}}{\epsilon(K+q)-\epsilon(K)}$

Here, the sum is over the whole first Brillouin zone. The Fermi-Dirac
distribution is: fK=$\frac{1}{\frac{\epsilon(K)}{T}+1}$ The STM images of the
2$\times$2$\times$1 CDW and the pristine phases are simulated using a slab
model, which has been used previously to simulate STM images in AV3Sb5 (A=K,
Rb, Cs) 11. The STM images for the Fe kagome surface of pristine and
2$\times$2$\times$1 CDW phases are simulated using a 3-unit-cell thick slab
(144 atoms) with a vacuum layer of $\sim$10 Å. The STM images are calculated
with a fixed height of $\sim$3 Å above the surface in the energy range of ± 25
meV relative to the given energy. Structural relaxation and SOC effect are not
considered in the STM simulations.

##  4 Author Contributions

S. S., J.-X. Y., I. B., and J.-Y. Y. contributed equally to this work. G.C.
was responsible for the overall research direction, planning, and integration
among different research units. All authors contributed to the intellectual
content and the writing of this work.

##  5 Acknowledgment

The work was supported by the National Research Foundation, Singapore under
its Fellowship Award (NRF-NRFF13-2021-0010) and the Nanyang Technological
University start-up grant (NTUSUG). Work at Princeton University was supported
by the Gordon and Betty Moore Foundation (GBMF4547 and GBMF9461; M.Z.H.).
J.Y.Y. and Y.P.F. are supported by the Ministry of Education, Singapore, under
its MOE AcRF Tier 3 Award MOE2018-T3-1-002. The work at Northeastern
University was supported by the US Department of Energy (DOE), Office of
Science, Basic Energy Sciences Grant No. DE-SC0022216 and benefited from
Northeastern University’s Advanced Scientific Computation Center and the
Discovery Cluster, and the National Energy Research Scientific Computing
Center through DOE Grant No. DE-AC02-05CH11231.

Detailed structure information, structures, electronic properties, and
Heisenberg models of antiferromagnetic kagome FeGe.

## References

  * 1 Hou, C. Y.; Chamon, C.; Mudry, C. Electron fractionalization in two-dimensional graphenelike structures. Phys. Rev. Lett. 2007, 98, 186809.
  * 2 Gutiérrez, C.; Kim, C. J.; Brown, L.; Schiros, T.; Nordlund, D.; Lochocki, E. B.; Shen, K. M.; Park, J.; Pasupathy, A. N. Imaging chiral symmetry breaking from kekulé bond order in graphene. Nat. Phys. 2016, 12, 950.
  * 3 Bao, C. H.; Zhang, H. Y.; Zhang, T.; Wu, X.; Luo, L. P.; Zhou, S. H.; Li, Q.; Hou, Y. H.; Yao, W.; Liu, L. W.; Yu, P.; Li, J.; Duan, W. H.; Yao, H.; Wang, Y. L.; Zhou, S. Y. Experimental evidence of chiral symmetry breaking in kekulé-ordered graphene. Phys. Rev. Lett. 2021, 126, 206804.
  * 4 Hasan, M. Z.; Chang, G. Q.; Belopolski, I.; Bian, G.; Xu, S.-Y.; Yin J.-X. Weyl, Dirac and high-fold chiral fermions in topological quantum matter. Nat. Rev. Mater. 2021, 6, 784.
  * 5 Yin, J.-X.; Lian, B.; Hasan, M. Z. Topological kagome magnets and superconductors. Nature 2022, 612, 647.
  * 6 Chen, H.; Yang, H. T.; Hu, B.; Zhao, Z.; Yuan, J.; Xing, Y. Q.; Qian, G. J.; Huang, Z. H.; Li, G.; Ye, Y. H.; Ma, S.; Ni, S. L.; Zhang, H.; Yin, Q. W.; Gong, C. S.; Tu, Z. J.; Lei, H. C.; Tan, H. X.; Zhou S.; Shen, C. M.; Dong, X. L.; Yan, B. H.; Wang Z. Q.; Gao H. J. Roton pair density wave in a strong-coupling kagome superconductor. Nature 2021, 599, 222.
  * 7 Zhao, H.; Li, H.; Ortiz, B. R.; Teicher, S. M.; Park, T.; Ye, M. X.; Wang, Z. Q.; Balents, L.; Wilson S. D.; Zeljkovic, I. Cascade of correlated electron states in the kagome superconductor CsV3Sb5. Nature 2021, 599, 216.
  * 8 Nie, L. P.; Sun, K. L.; Ma, W. R.; Song, D. W.; Zheng, L. X.; Liang, Z. W.; Wu, P.; Yu, F. H.; Li, J.; Shan, M.; Zhao, D.; Li, S. J.; Kang, B. L.; Wu, Z. M.; Zhou, Y. B.; Liu, K.; Xiang, Z. J.; Ying, J. J.; Wang, Z. Y.; Wu, T.; Chen, X. H. Charge-density-wave-driven electronic nematicity in a kagome superconductor. Nature 2022, 604, 59.
  * 9 Jiang,Y. X.; Yin, J.-X.; Denner, M. M.; Shumiya, N.; Ortiz, B. R.; Xu, G.; Guguchia, Z.; He, J. Y.; Hossain, M. S.; Liu, X. X.; Ruff, J.; Kautzsch, L.; Zhang, S. S.; Chang, G. Q.; Belopolski, I.; Zhang, Q.; Cochran, T. A.; Multer, D.; Litskevich, M.; Cheng, Z.-J.; Yang, X. P.; Wang, Z. Q.; Thomale, R.; Neupert, T.; Wilson S. D.; Hasan, M. Z. Unconventional chiral charge order in kagome superconductor KV3Sb5. Nat. Mater. 2021, 20, 1353.
  * 10 Li, H. X.; Zhang, T. T.; Yilmaz, T.; Pai, Y. Y. ; Marvinney, C. E.; Said, A.; Yin, Q. W.; Gong, C. S.; Tu, Z. J.; Vescovo, E. ; Nelson, C. S.; Moore, R. G.; Murakami, S.; Lei, H. C.; Lee, H. N.; Lawrie, B. J.; Miao, H. Observation of unconventional charge density wave without acoustic phonon anomaly in kagome superconductors AV3Sb5(A=Rb, Cs). Phys. Rev. X 2021, 11, 031050.
  * 11 Tan, H. X.; Liu, Y. Z.; Wang, Z. Q.; Yan, B. H. Charge density waves and electronic properties of superconducting kagome metals. Phys. Rev. Lett. 2021, 127, 046401.
  * 12 Neupert, T.; Denner, M. M.; Yin, J. X.; Thomale, R.; Hasan, M. Z. Charge order and superconductivity in kagome materials. Nat. Phys. 2022, 18, 137.
  * 13 Yu, F. H.; Ma, D. H.; Zhuo, W. Z.; Liu, S. Q.; Wen, X. K.; Lei, B.; Ying J. J.; Chen,X. H. Unusual competition of superconductivity and charge-density-wave state in a compressed topological kagome metal. Nat. Commun. 2021, 12, 3645.
  * 14 Mielke, C. III; Das, D.; Yin, J.-X.; Liu, H.; Gupta, R.; Jiang, Y.-X.; Medarde, M.; Wu, X.; Lei, H. C.; Chang, J.; Dai, P. C.; Si, Q.; Miao, H.; Thomale, R.; Neupert, T.; Shi, Y.; Khasanov, R.; Hasan, M. Z.; Luetkens, H.; Guguchia, Z. Time-reversal symmetry-breaking charge order in a kagome superconductor. Nature 2022, 602 245.
  * 15 Yang, H. J.; Kim, H. S.; Jeong, M. Y.; Kim, Y. B.; Han, M. J.; Lee, S. Intertwining orbital current order and superconductivity in kagome metal. 2022, arXiv:2203.07365, arXiv. DOI: 10.48550/arXiv.2203.07365 (accessed May 21, 2022).
  * 16 Mielke, C. III; Qin, Y.; Yin, J.-X.; Nakamura, H.; Das, D.; Guo, K.; Khasanov, R.; Chang, J.; Wang, Z. Q.; Jia, S.; Nakatsuji, S.; Amato, A.; Luetkens, H.; Xu, G.; Hasan, M. Z.; Guguchia, Z. Nodeless kagome superconductivity in LaRu3Si2. Phys. Rev. Materials 2021, 5, 034803.
  * 17 Jiang, Y.-X.; Yin, J.-X.; Denner, M. M.; Shumiya, N.; Ortiz, B. R.; Xu, G.; Guguchia, Z.; He, J. Y.; Hossain, M. S.; Liu, X. X.; Ruff, J.; Kautzsch, L.; Zhang, S. S.; Chang, G. Q.; Belopolski, I.; Zhang, Q.; Cochran, T. A.; Multer, D.; Litskevich, M.; Cheng, Z. J.; Yang, X. P.; Wang, Z. Q.; Thomale, R.; Neupert, T.; Wilson, S. D.; Hasan,M. Z. Unconventional chiral charge order in kagome superconductor KV3Sb5. Nat. Mater. 2021, 20, 1353.
  * 18 Teng, X. K.; Chen, L. B.; Ye, F.; Rosenberg, E.; Liu, Z. Y.; Yin, J.-X.; Jiang, Y.-X.; Oh, J. S.; Hasan, M. Z.; Neubauer, K. J.; Gao, B.; Xie, Y. F.; Hashimoto, M.; Lu, D. H.; Jozwiak, C.; Bostwick, A.; Rotenberg, E.; Birgeneau, R. J.; Chu, J. H.; Yi, M.; Dai, P. C. Discovery of charge density wave in a kagome lattice antiferromagnet. Nature 2022, 609, 490.
  * 19 Yin, J.-X.; Jiang, Y,-X,; Teng, X. K.; Hossain, M. S.; Mardanya, S.; Chang, T.-R.; Ye, Z. J.; Xu, G.; Denner, M. M.; Neupert, T.; Lienhard, B.; Deng, H.-B.; Setty, C.; Si, Q. M.; Chang, G. Q.; Guguchia, Z.; Gao, B.; Shumiya, N.; Zhang, Q.; Cochran, T. A.; Multer, D.; Yi, M.; Dai, P. C.; Hasan, M. Z. Discovery of charge order and corresponding edge state in kagome magnet FeGe. Phys. Rev. Lett. 2022, 129, 166401.
  * 20 Wang, Y. W.; Lv, J.; Zhu, L.; Ma, Y. M. Crystal structure prediction via particle-swarm optimization. Phys. Rev. B 82, 094116 (2010).
  * 21 Wang, Y. W.; Lv, J.; Zhu, L.; Ma, Y. M. CALYPSO: a method for crystal structure prediction. Comput. Phys. Commun. 2012, 183, 2063.
  * 22 Gao, B.; Gao, P. Y.; Lu, S. H.; Lv, J.; Wang, Y. C.; Ma. Y. M. Interface structure prediction via CALYPSO method. Sci. Bull. 2019, 64, 301.
  * 23 Henkelman, G.; Uberuaga, B. P.; Jónsson, H. A climbing image nudged elastic band method for finding saddle points and minimum energy paths. J Chem. Phys. 2000, 113, 9901.
  * 24 Mills, G.; Jónsson, H.; Schenter, G. K. Reversible work transition state theory: application to dissociative adsorption of hydrogen. Surf. Sci. 1995, 324, 305.
  * 25 Sheppard, D.; Terrell, R.; Henkelman, G. Optimization methods for finding minimum energy paths. J Chem. Phys. 2008, 128, 134106.
  * 26 Weber, F.; Rosenkranz, S.; Castellan, J.-P.; Osborn, R.; Hott, R.; Heid, R.; Bohnen, K.-P.; Egami, T.; Said, A. H.; Reznik, D. Extended phonon collapse and the origin of the charge-density wave in 2H-NbSe2. Phys. Rev. Lett. 2011, 107, 107403.
  * 27 Diego, J.; Said, A. H.; Mahatha, S. K.; Bianco, R,; Monacelli, L.; Calandra, M.; Mauri, F.; Rossnagel, K.; Errea, I.; Blanco-Canosa, S. Van der Waals driven anharmonic melting of the 3D charge density wave in VSe2. Nat. Commun. 2021, 12, 598.
  * 28 Kvashnin, Y.; VanGennep, D.; Mito, M.; Medvedev, S. A.; Thiyagarajan, R.; Karis, O.; Vasiliev, A. N.; Eriksson, O.; Abdel-Hafiez, M. Coexistence of superconductivity and charge density waves in tantalum disulfide: experiment and theory. Phys. Rev. Lett. 2020, 125, 186401.
  * 29 Xi, X. X.; Zhao, L.; Wang, Z. F.; Berger, H.; Forró, L.; Shan, J.; Mak, K. F. Strongly enhanced charge-density-wave order in monolayer NbSe2. Nat. Nanotechnol. 2015, 10, 765.
  * 30 Setty, C.; Lane, C. A.; Chen, L.; Hu, H. Y.; Zhu, J.-X.; Si, Q. M. Electron correlations and charge density wave in the topological kagome metal FeGe. 2022, arXiv:2203.01930, arXiv. DOI: 10.48550/arXiv.2203.01930 (accessed Apr 6, 2022).
  * 31 Lindhard, J. On the properties of a gas of charged particles. Dan. Vid. Selsk Mat.-Fys. Medd. 1954, 28, 8.
  * 32 Borisenko, S. V.; Kordyuk, A. A.; Yaresko, A. N.; Zabolotnyy, V. B.; Inosov, D. S.; Schuster, R.; Büchner, B.; Weber, R.; Follath, R.; Patthey, L.; Berger, H. Pseudogap and charge density waves in two dimensions. Phys. Rev. Lett. 2008, 100, 196402.
  * 33 Borisenko, S. V.; Kordyuk, A. A.; Zabolotnyy, V. B.; Inosov, D. S.; Evtushinsky, D.; Büchner, B.; Yaresko, A. N.; Varykhalov, A.; Follath, R.; Eberhardt, W.; Patthey, L.; Berger, H. Two energy gaps and fermi-surface “arcs” in NbSe2. Phys. Rev. Lett. 2009, 102, 166402.
  * 34 Dugdale, S. B. Life on the edge: a beginner’s guide to the Fermi surface. Phys. Scr. 2016, 91, 053009.
  * 35 Kekulé, A. Studies on aromatic compounds. Ann. Chem. Pharm. 1865, 137, 129.
  * 36 Chamon, C. Solitons in carbon nanotubes. Phys. Rev. B 2000, 62, 2806.
  * 37 Herrera, S. A.; Naumis, G. G. Electronic and optical conductivity of kekulé-patterned graphene: intravalley and intervalley transport. Phys. Rev. B 2020, 101, 205413.
  * 38 Kresse, G.; Furthmüller, J. Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set. Phys. Rev. B 1996, 54, 11169.
  * 39 Perdew, J. P.; Burke, K.; Ernzerhof, M. Generalized gradient approximation made simple. Phys. Rev. Lett. 1996, 77, 3865.
  * 40 Blöchl, P. E. Projector augmented-wave method. Phys. Rev. B 1994, 50, 17953.
  * 41 Togo, A.; Oba, F.; Tanaka, I. First-principles calculations of the ferroelastic transition between rutile-type and CaCl2-type SiO2 at high pressures. Phys. Rev. B 2008, 78, 134106.
  * 42 Wang, V.; Xu, N.; Liu, J.-C.; Tang, G.; Geng, W.-T. VASPKIT: a user-friendly interface facilitating high-throughput computing and analysis using VASP code. Comput. Phys. Commun. 2021, 267, 108033.
  * 43 Zhu, X. T.; Cao, Y. W.; Zhang, J. D.; Plummer, E. W.; Guo, J. D. Classification of charge density waves based on their nature. Proc. Natl. Acad. Sci. U. S. A. 2015, 112, 2367.

Figure 1: (a) A 2$\times$2$\times$1 supercell of the pristine phase, where the
primitive cell is marked with the black solid line. (b) The
2$\times$2$\times$1 CDW phase, where the blue and purple arrows show the in-
plane movement of Ge atoms on the top and middle Ge layers, respectively. The
out-of-plane movement of the Ge atoms is given in Note 1 (Supporting
Information). The green arrows in (a) and (b) represent the direction of the
magnetic moment in different kagome layers. (c), (d) Phonon spectra of
pristine and 2$\times$2$\times$1 CDW phases. (e) Gibbs free energy of
2$\times$2$\times$1 CDW phases per cell (48 atoms) relative to the pristine
phase. (f) Reaction path between the pristine and 2$\times$2$\times$1 CDW
phase calculated by NEB23, 24, 25.
Figure 2: (a) DFT simulation of the surface charge distribution on the kagome
layer of the pristine phase, where the black parallelogram marks the primitive
cell. (b) Tunneling current maps measured by STM, where the blue lines mark
the kagome lattice. (c) Simulated surface charge distribution on the kagome
layer of the 2$\times$2$\times$1 CDW phase, where the black parallelogram
marks the primitive cell. Upper, middle, and lower panels in (a)-(c) are the
experimental STM images or the simulated surface charge distribution at 40,
20, and -40 meV relative to the Fermi energy, respectively.
Figure 3: (a) Two-dimensional Fermi surface profiles of pristine phase in the
${k_{z}}$=0 and ${k_{z}}$=$\pi$ planes. (b) Fermi surface contour in the $yz$
plane along the cut1 (${k_{x}}$=-${\sqrt{3}\pi}$/12) in panel (a). (c) Fermi
surface contour in the $yz$ plane along the cut2 (${k_{x}}$=${\sqrt{3}\pi}$/6)
in panel (a). (d) Normalized Lindhard response function for the pristine phase
in the b1-b2 plane. Figure 4: (a) Band structure of the pristine phase
including SOC effects. (b), (c) Orbital-resolved band structure of
dxy/d${}_{x^{2}-y^{2}}$ and $\textit{d${}_{xz}$}/$dyz for the pristine phase,
respectively. (d) Schematic diagram of Dirac cones in the pristine phase,
where the solid lines mark the bands that play a major role in Fermi surface
nesting. (e) Band structures of the 2$\times$2$\times$1 CDW phase including
SOC effects. (f) Constant energy contours for the 2$\times$2$\times$1 CDW
phase in the kz=$\pi$ plane at 10 meV below the Fermi energy. (g) Band
structures of the pristine phase and (h) the unfolded band structures of the
2$\times$2$\times$1 CDW phase along the cut2 plane along L′-A′-L′, where L′ is
(0.166, 0.4167, 0.5) and A′ is (0.166, -0.0833, 0.5). The CDW gap is located
at (0.166, 0.1667, 0.5) with an energy gap of $\sim$45 meV (i) A schematic of
the CDW distorted kagome antiferromagnet. The shortest bonds in the top Ge
layer form the O-shaped bond textures, and the shortest bonds in the middle Ge
layer form the Y-shaped bond textures. Orange and blue spheres represent Fe
and Ge atoms, respectively. Dark green arrows represent magnetic directions.
(j) Relative energy of CsV3Sb5 as a function of the average V motion. (k)
Relative energy of FeGe as a function of the average Fe motion. (l)
Hamiltonian of the Heisenberg model as a function of the average Fe motion.
(m) Average magnetic moment of Fe as a function of the average Ge motion. (n)
Sketch of the intertwining between magnetic exchange coupling and CDW
interaction. The black dashed curve gives the charge density in the pristine
phase. The orange curve gives the charge density in the CDW phase. Black
arrows represent the magnetic exchange coupling effect on the Fe atoms. Green
and white arrows represent the kagome-Fe magnetic moment in the CDW phase and
the pristine phase, respectively.


Locality-based Graph Reordering for Processing Speed-Ups and Its Dependence on
Graph Diameter

Bachelors’ Thesis Project
Submitted in fulfillment of the requirements for the degree of

Bachelor of Technology
in

Electrical Engineering

Author: Vedant Satav (Roll No. 170070012)
Guide: Prof. Virendra Singh

Department of Electrical Engineering

Indian Institute of Technology Bombay

July 4th, 2021

### Abstract

Graph analysis involves a high number of random memory access patterns.
Earlier research has shown that the cache miss latency is responsible for more
than half of the graph processing time, with the CPU execution having the
smaller share. There has been significant study on decreasing the CPU
computing time for example, by employing better cache prefetching and
replacement policies. In this paper, we study the various methods that do so
by attempting to decrease the CPU cache miss ratio.

Graph Reordering attempts to exploit the power-law distribution of graphs- few
sparsely-populated vertices in the graph have high number of connections- to
keep the frequently accessed vertices together locally and hence decrease the
cache misses. However, reordering the graph by keeping the hot vertices
together may affect the spatial locality of the graph, and thus add to the
total CPU compute time. Also, we also need to have a control over the total
reordering time and its inverse relation with the final CPU execution time

In order to exploit this trade-off between reordering as per vertex hotness
and spatial locality, we introduce the light-weight Community-based
Reordering. We attempt to maintain the community-structure of the graph by
storing the hot-members in the community locally together. The implementation
also takes into consideration the impact of graph diameter on the execution
time. We compare our implementation with other reordering implementations and
find a significantly better result on five graph processing algorithms- BFS,
CC, CCSV, PR and BC. Lorder achieved speed-up of upto $7\times$ and an average
speed-up of $1.2\times$ as compared to other reordering algorithms

Index terms– graph analysis, power-law distribution, ground-truth communities

###### Contents

  1. 1 Introduction
  2. 2 Background
    1. 2.1 Structure of Natural Graphs
    2. 2.2 Graph Representation
    3. 2.3 Graph Traversal and Memory Use
  3. 3 Motivation
    1. 3.1 Statement
    2. 3.2 Graph Reordering (GOrder)
    3. 3.3 Structure-preserved Reordering (S-Order)
    4. 3.4 Neighbourhood Reordering (N-Order)
    5. 3.5 Degree-Based Grouping (DBG)
  4. 4 Locality-based Reordering
  5. 5 Performance Evaluation
    1. 5.1 Experimental Setup
    2. 5.2 Results

## Chapter 1Introduction

Over the years, the applications of graph analysis have diversified, one among
the many being the field of social network processing.
However, because of the way graphs are stored in the shared memory, their
processing involves inherent irregular memory access patterns. The random
accessing is further exacerbated by the varied processing style adopted by
different algorithms used in graph processing. These memory indirections
result in frequent cache-misses thereby leading to longer CPU cache latency
issues and thus, limiting the efficiency of graph processing in shared memory
systems.
One way to reduce the cache misses, and the corresponding cache latency, is to
implement prefetchers that have information about the graph processing
algorithm beforehand. These prefetchers would then ensure that the appropriate
cache blocks are ready in the caches.
An alternative method would be to improve cache locality by means of graph
reordering, in which the graph vertices are reassigned indices without
changing the actual structure of the graph itself. Previous studies on
different reordering schemes have shown that the reordered graph has lower
processing time as compared to the original graph. The reordering scheme
itself would be based on a particular feature of the graph that can be
exploited, leading to the introduction of a reordering time overhead in the
end-to-end processing. Graph reordering involves two tradeoffs that need to be
balanced.
(1)The more information that we wish to derive from the graph for reordering,
the higher would be the reordering time, but at the same time, lower would be
the processing time post-reordering. State of the art reordering algorithms
take into account information such as the degree of the vertices, the nature
and the density of connectivity between the vertices, etc. Thus the reordered
graph, although having high execution speedups, also encounters a big overhead
in reordering time. Various lightweight reordering algorithms have hence been
studied that are simply based on exploiting the power-law distribution in
graph- the number of vertices that have high connectivity, and are hence
likely to be processed many times, comprise of a small fraction of all the
vertices. These hot vertices are sparsely distributed across the entire graph.
The probability that a cache block would have multiple hot vertices would be
low. However, any memory block having a high number of these hot vertices
would be more likely to be preserved in the cache, since they are more likely
to be reused due to their high temporal locality. Light-weight reordering
algorithms ensure that highly connected vertices, henceforth referred to as
hot vertices, are reassigned indices closer to each other.
(2) Even though this increases the temporal locality in the graph, it severely
affects the spatial locality in the graph in certain cases. Real-world graphs
are large in size and have connections governed by natural interaction
patterns and thus, carry some inherent connectivity information and display
community structures. The memory access patterns are greatly governed by these
neighbourhood laws. A simple reordering of the graph vertices on the basis of
their degree would threaten to disrupt the spatial locality of neighbourhoods
in the original graph structure. For graph processing algorithms that are
neighbourhood-based, like BFS, decreasing the spatial locality can therefore
lead to worse, if not the same, post-reordering execution time.
Taking into consideration the two trade-offs, we introduce our locality-based
reordering scheme that seeks to benefit from the natural community structures
present in the graph as well as increase the temporal locality by placing the
hot vertices together. LOrder defines various disjoint but complete localities
in the entire graph structure and then carries out coarse-grain reordering of
the vertices in each of the localities- the hot vertices are preferentially
numbered before the cold vertices. Within the hot/cold block, the vertex order
is maintained in the sequence of BFS traversal during definition of the
locality. This method of reordering hot and cold vertices within the locality
itself preserves the structure in the graph as well as benefits from the low
cache misses by keeping the hot vertices together. In the first version, we
define the seed vertex for each community as the unvisited vertex in the
original graph with the lowest index. In the second version of the
implementation, we define communities as the connected components in the graph
that confer to the definition of a ground-truth community in the graph-
although the reordering time is higher, we get lower execution graph
processing times post-reordering. This paper follows this structure

  * •

We first study the nuances of graph reordering and criticise some of the
existing reordering schemes, including the state-of-art GOrder

  * •

We propose LOrder, a new light-weight reordering scheme that carries out
localised coarse-grained reordering to improve the spatio-temporal locality in
the graph

  * •

We compare the results obtained from LOrder with other reordering schemes to
show that it has better performance game for many of the cases (beats DBG 77%
of the time) and has a maximum speed up of $7\times$. We also remark on the
role played by the graph diameter on performance

## Chapter 2Background

###  2.1 Structure of Natural Graphs

Real-world graphs are large in size and have connections governed by natural
interaction patterns and thus, carry some inherent connectivity information
and display community structures. The memory access patterns are greatly
governed by these neighbourhood laws. These natural graphs can be used to
represent many of our network applications like social networks, computer
networks, maps, etc. Two prevalent properties of natural graphs that we borrow
from-
Power-law distribution: Only a small fraction of the vertices have high degree
of connectivity. This skewed distribution of degree is an important property
with respect to cache reuse since a few of these hot vertices have a high
chane of reuse, since they are neighbours of a high number of vertices. A
memory block with many hot vertices would likely be queried large number of
time, and if it were maintained in the cache, the cache miss rate could be
reduced. Table 1 quantifies this skew for the datasets used in this paper. The
table contains the percentage of hot vertices in the entire graphs along with
the number of edges that come in or out of these vertices. Here, hotness is
defined as a vertex having a degree higher than the threshold of average
hotness of the vertices for the graph.
Community structures: Graphs based on natural connection patterns display high
inter-connections in different regions. These clusters are called communities
in a graph. For example, in a social network, members sharing similar likes
and preferences are bound to converge into groups. The corresponding graph
would represent these groups as a closely-knit community of vertices
corresponding to these members. In geographical graphs used for navigation
purposes, smaller towns would be positioned around important towns or cities.

###  2.2 Graph Representation

For the purposes of representation, graphs are modelled by a set of vertices
(V) and the set of their corresponding directed edges (E), G = (V, E). Each of
these vertices would have some properties associated with it, which form the
basis of graph analysis.
In a natural graph, the edges are not uniformly distributed across the
vertices but are in fact sparse due to the underlying community structures in
the graph. Thus, in an adjacency matrix form of representing graphs, most of
the elements would be null, leading to a wastage of expensive shared-memory
space.

(a) Graph structure

(b) Corresponding CSR format

Figure 2.2.1: Example of Compressed Sparse Row (CSR) representation of graphs

An alternative is found in the Compressed Sparse Row (CSR) format for
representing graphs. The CSR format uses a vertex and an edge array to encode
the graph, with an additional array to store the properties corresponding to
each of the vertices. The edge array could represent an in-edge or an out-edge
(in Figure 2.2.1, the out-edges are considered) depending on the type of
computations being carried out. In pull-type computations, the parent vertex
collects the property values from its in-neighbours. Hence, the CSR format
should maintain the in-edges for pull-type computations. In push-type
computations, the parent vertex pushes its property values to its out-
neighbours for which, the CSR format should maintain the out-edges in the edge
array.
How is the CSR format queried? We take a pull-type algorithm as an example.
For every vertex, the vertex array element corresponding to the vertex id
contains the index of the first in-neighbour of the vertex in the edge array.
Thus, each element in the edge array would be the source vertex of that edge.
The number of edges (the degree) for any vertex can be easily determined by
the difference of consecutive elements in the vertex array. In the figure
2.2.1, the Resuse demonstrates the number of queries to the property element
for each graph vertex for one graph traversal. The number is equivalent to the
number of in-edges for the corresponding vertices.

###  2.3 Graph Traversal and Memory Use

For processing a vertex, the graph processing algorithm would query all its
neighbours from the edge array. The property arrays corresponding to each of
these neighbours would be queries to process the parent vertex. In the
traversal of the entire graph, thus, elements in the vertex and the edge
arrays would be queried only once. However, elements in the property arrays
would be queried multiple times, depending on the degree of the vertex. Note
that this degree would depend on the type of computations: out-degree for
pull-based computations and vice versa. The number of reuses of each of the
elements can be understood from the figure given. Hence, out of the three
arrays, the property arrays show temporal locality. In order to improve the
cache utilization from these high-reuse vertices, we try to keep the hotter
vertices together. Graph reordering provides the means to optimize the CPU
access patterns without affecting the graph structure or the algorithm being
executed. The differences in the cache utilizations can be easier understood
by observing the below two conditions:

## Chapter 3Motivation

###  3.1 Statement

The problem statement of graph reordering as follows:
Problem statement: Given that we have a graph modelled as G = (V, E), we need
a permutation function phi() that assigns an unique vertex ID in (1, 2, 3…, n)
to each vertex of the original graph, where n = mod (V), the size of Vertex
data structure. The optimal permutation function $\phi()$ should be such that
it minimises the total cache misses during execution of a typical graph
processing algorithm

The problem statement can be divided into three objective points for
designing, testing and comparing any graph reordering scheme:

  1. 1.

Low reordering overhead\- Although our objective is to minimise the total
execution time for the graph processing algorithm, we need to also consider
the end-to-end time including the time to reorder the entire graph. However,
we need not reorder the graph every time we need to carry out any graph
analysis, since adding a few vertices to the graph do not cause significant
changes in the structure or degrees in the graph. Hence, the reordering time
itself can be amortized over multiple instances. The number of traversals that
would be required to amortize the reordering time depends on the total
reordering time, which thus needs to be curtailed

  2. 2.

High cache utilization\- keeping as many hot vertices together as possible
would lead to better temporal locality of vertices and would thus help in
better cache utilization for memory blocks having these hot vertices

  3. 3.

Preserving the structure\- Many graph analysis algorithms involve high spatio-
temporal locality, i.e, they tend to process those vertices first that are in
the neighbourhood of the current vertices. Hence, the underlying structures
present in the graphs are crucial for determining the data flow in the data
flow. Any reordering scheme should preserve these structures to prevent
adverse impacts on the performance achieved from improving the temporal
locality alone

We now criticise some reordering schemes on the above mentioned objective
points.

###  3.2 Graph Reordering (GOrder)

In GOrder, the authors observe that the data access patterns are greatly
influenced by the neighbourhood relations in the graph. In addition to the
dependency of the neighbouring vertices on the current vertex, it also
observes that the relations between the vertices, called sibling
relationships, are of consequence.
To formalise the graph reordering problem statement, GOrder takes help of a
score function to measure closeness between any two vertices:

$\mathcal{S}(u,v)=\mathcal{S}_{s}(u,v)+\mathcal{S}_{n}(u,v)$ (3.1)

Where,
$\mathcal{S}_{s}$: Number of common in-neighbours of $u$ and $v$
$\mathcal{S}_{n}$: number of times $u$ and $v$ are direct neighbours
Thus, two vertices that are densely connected with each other would have a
greater score function. If by some means, say a permutation function
$\phi(.)$, we ensure that such pairs of vertices are kept close to each other
in the cache, the number of cache hits would increase. Mathematically, Gorder
defines an accumulated locality score $\mathcal{F}(.)$ over a window of size
$\omega$, that should be maximised:

$\mathcal{F}(\phi)=\sum_{0<\phi(v)-\phi(u)\leq\omega}\mathcal{S}(u,v)$ (3.2)

Maximising of $\mathcal{F}$ is proved to be NP-hard by Gorder, which proposes
a greedy algorithm as a solution. Although this greedy algorithm has a high
reordering overhead, the execution time achieved after the reordering is
considerably lesser. A closer analysis of the results from Gorder suggests
that it reorders the hot vertices first as well as keeps the neighbouring
vertices together. The combination of these three results make GOrder a very
good basis for comparison.

###  3.3 Structure-preserved Reordering (S-Order)

It proposes the concept of a hypernode, an aggregate of adjacent unvisited
cold vertices beginning from a seed vertex into a virtual vertex. The
adjacency is defined to be the vertices that are within $\kappa$-hops from the
seed vertices. The neighbours of the vertices present in the hypernode are
then split into two groups based on their hotness. The reordering begins with
the vertices in the hypernode, then the hot neighbours of the hypernode and
finally the cold neighbours.

###  3.4 Neighbourhood Reordering (N-Order)

Norder takes a very different approach to balancing the tradeoffs. It first
creates a list of vertices in descending order of their hotness. The next
iteration, it carries our reordering in BFS-fashion serially taking elements
from the previously arranged list as seed vertices for the BFS. The new
reordering is in the order of traversal. Since the entire graph would be
traversed twice during NOrdering, the reordering time is expected to be
proportionally high as well, as discussed later during the results comparison.

###  3.5 Degree-Based Grouping (DBG)

DBG is a skew-aware coarse-reordering technique that rearranges the graph such
that each cache block has vertices having similar degrees. As opposed to Sort,
which just reorders the entire graph with new vertex ids being assigned in
descending order of their hotness, DBG bins the vertices in different
partitions, in the original vertex numbering order, i.e in each of the
partitions, DBG maintains the original relative order of the vertices. But
that is the extent to which it ensures the integrity of the original structure
of the graph. The partitions are defined with degree ranges that follow the
power-law distribution. Since this technique involves only ‘binning’ and not a
full-blown sorting of the vertices, the reordering time incurred by DBG is
found to be the least for most of the cases. However, since it conforms to the
power-law distribution directly, the results from DBG reordering are quite
aligned with our objective points.

Some key observations after studying the above schemes:

  1. 1.

Since one of the objectives is to maintain the neighbourhood structures of the
original graph, many of the reordering algorithms thus make use of BFS-type
pattern to traverse the entire graph for indexing

  2. 2.

Although GOrder shows promising results for execution time, the reordering
time is quite high

  3. 3.

By forming hypernodes, SOrder tends to prefer preserving neighbourhood
structure over improving the temporal locality

  4. 4.

Norder, on the other hand, trades off the temporal locality over preserving
the community structure, while also encountering significant reordering time
due to the double traversal

  5. 5.

Design of DBG limits its structure-preservation to just maintaining the
relative order of the reordered vertices. The serial vertex IDs of the
original graph may not be the best representative of the underlying cross
connections in the graph

## Chapter 4Locality-based Reordering

To acknowledge the inherent tendency in the vertices to be a part of
communities, we propose Lorder that aims to define small localities in the
graph and carry out reordering keeping these localities as the basis. By
reordering localities in their entirety and then a coarse-grain sorting of
vertices within the localities, Lorder promises to well balance the trade-off
between improving spatial and temporal locality.
Lorder defines a locality as all the vertices that fall within a $\kappa$-hop
distance from a seed vertex, traversed in BFS fashion. The localities are
disjoint and thus, their formation and structure greatly depend on the first
seed vertex that is chosen. We also assign hotness to each of the localities,
henceforth called locality hotness, as the number of hot vertices part of the
locality. Hot vertices are themselves defined to be those vertices having
degrees more than the average degree of the entire graph. The reordering
process can be thus divided into two different parts.

Locality formation At the primitive stage, we use the zeroth vertex of the
original graph as the seed vertex, which also forms a tag for the locality.
Hence, all the vertices within $\kappa$-hops from the zeroth vertex become a
part of its locality. As vertices are added to the locality, a count of the
hot vertices in it is maintained and the vertices themselves are marked with
the locality ID (the reason discussed later).
After the locality is completely formed, the tag of the locality along with
the corresponding hotness is maintained in a list LocalityID. We serially take
up remaining unvisited vertices to be the seed vertex and repeat the above
mentioned steps. Once all the vertices are visited and are thus part of a
unique locality, we sort the LocalityID list in descending order of the
locality hotness. This concludes the locality formation part of the algorithm,
summarised as Algorithm 1.
Assigning new indices Once we have the sorted LocalityID list, we begin with
the actual assignment of new indices. Taking each seed vertex serially, we
begin with traversing the vertices that are within $\kappa$-hops from it and
are a part of its locality. However, as earlier mentioned, the distribution of
vertices into the localities depends on the seed vertex we start with. Hence,
to ensure consistency between localities defined in Algorithm 1 and the
vertices being visited this time, we associate each vertex with the tag of the
locality it belongs with.
For each locality, we maintain a hot and a cold vertices list. As we traverse
the locality from the seed vertex, we serially add vertices in their
respective list. Lorder preferentially assigns consecutive indices to the hot
vertices, before the cold vertices. The process is summarised in Algorithm 2.

1

Input: Graph G = (V, E)

Output: Original graph G = (V, E) and the list LocalityID with locality seed
vertex IDs and corresponding community hotness

2

3for  _$v\in$ V_ do

4 if  _!Assigned_ then

5 $seed$ = $v$, $list$ = $\\{$v$\\}$; $hops\\_left=\kappa$;

6 while  _$hops\\_left$ != 0 _ do

7 $hops\\_left$\- -;

8

9 for  _i $\in Neigh_{out}(v)$ $\&$ !visited()_ do

10 xyz

11

12

13

14

Algorithm 1 Formation of localities

1

Input: Graph G = (V, E)

Output: Graph G = (V, E), list LocalityID

2 seed = 0

/* Now this is an if...else conditional loop */

3 if  _Condition 1_ then

Do something

// this is another comment

4 if  _sub-Condition_ then

5 Do a lot

6

7else if  _Condition 2_ then

8 Do Otherwise

/* Now this is a for loop */

9 for  _sequence_ do

10 loop instructions

11

12else

13 Do the rest

14

/* Now this is a While loop */

15 while  _Condition_ do

16 Do something

17

18

Algorithm 2 Example code

(a) Original graph structure

(b) Property array

Figure 4.0.1: (b) shows the arrangement of the property array in the memory
for graph in (a)

(a) Localities

(b) Locality-hotness

Figure 4.0.2: (b) shows the arrangement of the property array in the memory
for graph in (a)

(a) Reordered graph

(b) Property array

Figure 4.0.3: (b) shows the arrangement of the property array in the memory
for graph in (a)

## Chapter 5Performance Evaluation

###  5.1 Experimental Setup

We evaluate effectiveness of Lorder by running six different graph processing
algorithms on graph reordered by four graph reordering schemes. The
evaluations are run on a machine with following configuration: (add compiler
version here too)
Algorithms: We make use of the GAPS Benchmark suites for carrying out the
graph processing. It has C++ implementations of the following algorithms:

  * •

Breadth-First Search: A fundamental graph traversal technique which starts
from a single source and traverses all the vertices of the current level
before moving on to the next one

  * •

Page Rank: Iteratively computes the rank of vertices using their connectivity
propoerties

  * •

Betweenness centrality: Using BFS traversal to determine the paths originating
from a aprticular source through a particular vertex, it determines a central
vertex

  * •

Single Source Shortest Path: Using the Bellman Ford algorithm, it finds
shortest path to all the connected vertices from a particular vertex

  * •

Connected Components: It assigns unique labels to all the connected components
and the vertices associated with each of these components

  * •

CC_SV: Connected Components implemented with the Shiloach-Vishkin algorithm

Dataset | Type |  # of vertices |  # of nodes
---|---|---|---
lj | Social Network | 4,847,571 | 68,993,773
orkut | Community | 3,072,441 | 117,185,083
pld arc | Hyperlink |  |
kron23 | Kronecker |  |
youtube | Community | 1,134,890 | 2,987,624
pokec | Social Network | 1,632,803 | 30,622,564
Table 5.1: Dataset details

Graph datasets: A total of six graph datasets, summaried in Table XYZ. Apart
from the Kronecker graph by Graph500 benchmark, all the other graphs are real-
world graphs. The average degrees of these graphs are also mentioned, which
forms the threshold for defining hotness for each vertex. We also report the
diameter of the graphs, the longest shortest connected path in the graph, for
those belonging to SNAP Stanford dataset repository. The diameter plays an
integral part in the analysis of Lorder, as summarised in the results.
Evaluation Method For the various reordering schemes, the parameters are set
as per the inferences by their authors. For example, we set $\lambda=50$ and
$\kappa=2$ for SOrder. For LOrder, we set $\lambda=$ the average degree of the
graph. We also have the $\kappa$ parameter in Lorder, which varies from graph
to graaph. the value is chosen such that the final execution time of the
algorithms is least for the set $\kappa$ value. The comparison across the
reordering schemes are based on the execution speedups, the cache statistics,
reordering time as well as interesting observation about the $\kappa$ values.
We report execution times averaged over 16 iterations to incorporate time
required for cache warm-up.

###  5.2 Results

The value of $\kappa$. The number of hops from the seed vertex, parameter
$\kappa$, determines the locality for any seed vertex. The value is set such
that the post-reordering execution time is minimum. The results are as shown
in the Table 5.2. The value of $\kappa$ is observed to be half of the diameter
of the graph, as mentioned on the SNAP dataset repository. Hence, $\kappa$ is
also referred to as the radius in this paper. For the remaining datasets, the
diamater can be shown to be twice of the radius.

Dataset | Type |  Diameter of the graph |  Value of $\kappa$
---|---|---|---
lj | Social Network | 16 | 8
orkut | Community | 9 | 4
youtube | Community | 20 | 10
pokec | Social Network | 11 | 5
Table 5.2: The value of $\kappa$ is set to achieve the lowest execution time

Comparing processing speed-up The proposed reordering scheme is implemented on
the GAPS Benchmark and the execution times post-reordering are compared to the
execution time without reordering. The speed-ups are plotted in Figure 5.2.2
for six different datasets and for five graph processing kernels. Since DBG
provides some of the best processing speed-ups, we compare our results to see
that Lorder beats DBG for 77% of the total comparisons (i.e, 23 times out of
30). Likewise, it beats SOrder 60% of the time (i.e, 18 times out of 30). To
better analyse the overall behaviour of the reordering schemes, we plot their
geometric means for different graph processing kernels in Figure 5.2.3. We can
see that Lorder outright beats all the other reordering schemes for BFS, CC
and PR applications while it is marginally slower that DBG in BC. However,
Lorder consistently performs badly for the CC (Shiloach-Vishkin) graph kernel.
This can be attributed to the uncertainty in which vertices would be a part of
the processed at any given time.
It is also observed that for apart for a few cases, reordering graphs lead to
significant processing speed-ups. For applications involving multiple
iterations or traversals, these speed-ups can greatly reduce the total
processing time. However, we also need to account for the reordering times.
Comparing reordering times. Out of the four reordering schemes being
discussed, DBG and SOrder require a single traversal of the graph while NOrder
and LOrder require two graph traversals. So it is expected of the latter two
to have almost double the reordering time of the former, as collaborated
through Table 5.2.1. The size of the graph also determines the time taken to
reorder it. The values in the above table follow the graph size trends in
Table 5.1.
However, the actual reordering time also depends on factors like the number of
hot vertices being processed initially, etc. The cost of reordering is not
incurred every iteration of processing. A reordered graph is stored in the
memory and thus, can be used multiple times. Also, the addition and removal of
vertices to the reordered graph with significantly high number of vertices
does not affect the processing time much, as shown by a previous study. Hence,
the reordering time is amortized over multiple iterations.

Figure 5.2.1: Time taken (in seconds) to reorder graphs with each of the four
reordering schemes

(a) soc-LiveJournal1

(b) com-Orkut

(c) kron23

(d) pld_arc

(e) com-Youtube

(f) soc-Pokec

Figure 5.2.2: Speed ups comparison contributed by different reordering
algorithms for various datasets. It can be seen that a basic implementation of
Lorder without any embellishments performs better in many cases as discussed
in the results Figure 5.2.3: Geometric means of graph processing speed-ups for
various kernels across different datasets

## Bibliography

  * [1] All the references will be added soon
  * [2]