# From FPGAs to Obfuscated eASICs: Design and Security Trade-offs

Zain Ul Abideen, Tiago Diadami Perez, Samuel Pagliarini

This work was partially supported by the EC through the European Social Fund
in the context of the project “ICT programme”. It was also partially supported
by the Estonian Research Council grant MOBERC35. Centre for Hardware Security,
Tallinn University of Technology (TalTech), Estonia
{zain.abideen, tiago.perez<EMAIL_ADDRESS>
###### Abstract

Threats associated with the untrusted fabrication of integrated circuits (ICs)
are numerous: piracy, overproduction, reverse engineering, hardware trojans,
etc. The use of reconfigurable elements (i.e., look-up tables as in FPGAs) is
a known obfuscation technique. In the extreme case, when the circuit is
entirely implemented as an FPGA, no information is revealed to the adversary
but at a high cost in area, power, and performance. In the opposite extreme,
when the same circuit is implemented as an ASIC, best-in-class performance is
obtained but security is compromised. This paper investigates an intermediate
solution between these two. Our results are supported by a custom CAD tool
that explores this FPGA-ASIC design space and enables a standard-cell based
physical synthesis flow that is flexible and compatible with current design
practices. Layouts are presented for obfuscated circuits in a 65nm commercial
technology, demonstrating the attained obfuscation both graphically and
quantitatively. Furthermore, our security analysis revealed that for truly
hiding the circuit’s intent (not only portions of its structure), the
obfuscated design also has to chiefly resemble an FPGA: only some small amount
of logic can be made static for an adversary to remain unaware of what the
circuit does.

###### Index Terms:

Hardware Obfuscation, Secure ASIC Design, CAD, Reconfigurable obfuscation,
Reverse engineering

##  I Introduction

Shipment of semiconductor devices is forecast to surpass one trillion units in
the year 2021, the third time this mark is surpassed in a calendar year since
2018 [1]. The majority of those devices are being manufactured by foundries
that subscribe to the fab-for-hire model. A rogue element within the foundry
can mount fabrication-time attacks, i.e., the foundry and its employees are
considered potential adversaries. Many potential threats regarding third-party
foundries have been studied in recent years, include tampering,
counterfeiting, reverse engineering, and overproduction [2]. On the other
hand, many techniques have been devised to mitigate threats from untrusted
fabrication. Countermeasure techniques to increase the IC security against not
only third-party foundries but also from the end-user have been recently
demonstrated. Notable examples include IC Camouflaging [3, 4, 5], Logic
Locking [6, 7, 8], and Split Manufacturing [9, 10].

Generally speaking, all of the aforementioned countermeasures attempt to
“hide” the design from adversaries and can be classified as obfuscation
techniques. Unfortunately, none of these techniques is currently adopted in
large-scale production of ICs, for reasons that include (lack of) practicality
[9] and insufficient security guarantees [11]. Another approach towards
obfuscation is the use of an FPGA (or FPGA-like) design, where the
configuration _bitstream serves as a key_ to unlock the functionality of the
circuit [12]. Our paper too explores this possibility. The fabric in an FPGA
contains reconfigurable elements, but this flexibility incurs a limited
performance. On the other hand, ASIC requires one-time placement, it is static
(non-reconfigurable), but it provides best-in-class performance. As shown in
Fig. 1, performance increases if we move from right to left. Contrarily, area,
obfuscation, and flexibility increase if we move from left to right. However,
we argue that _neither extremes of the spectrum are a good design point_ for
circuits that have stringent security and performance constraints. An
intermediate solution is a better trade-off and this is precisely the
motivation for our work. We term our in-between solution an “embedded ASIC”
(eASIC).

Figure 1: The design obfuscation landscape, from ASICs to FPGAs. The relative
sizes are notional.

Design obfuscation concept: In this work, we propose to obfuscate a design by
exploiting the best of both worlds. The generated device is a hybrid which
includes reconfigurable elements (analogous to the FPGA) and also includes
ASIC cells as static elements, i.e., gates with fixed functionality after
fabrication. Previous research on obfuscation by reconfigurable elements has
focused on keeping the reconfigurable portion as small as possible [13, 14],
which is logical if the goal is to keep overheads under control. However, we
later show that true hiding of the circuit’s intent requires a _high degree of
obfuscation_ that is usually not explored in the state of the art. Thus, our
eASIC device is largely non-functional until it is programmed. Our main
contribution is a tool for automatically obfuscating a design in the form of
eASIC, where the obfuscation range can be from 0 to 100%. Furthermore, its
physical synthesis flow is standard-cell based that is compatible with current
design and fabrication practices.

##  II A CAD flow for eASIC

Our CAD flow is centered around a tool named Tuneable Design Obfuscation
Technique using eASIC, or TOTe for short. This section explains the CAD flow
of eASIC and TOTe’s main features. TOTe generates a hybrid design with static
and reconfigurable elements, which we refer to as eASIC. For the
reconfigurable elements, we implement the logic utilizing the notion of
programmable LUTs (Look Up Tables) - same as in FPGAs. The complete TOTe
design flow for generating an eASIC is shown in Fig. 2 and it consists of
three phases.

Figure 2: The CAD flow for eASIC, combining FPGA and ASIC synthesis.

In the first phase of our flow, the design under obfuscation, described in
register-transfer level (RTL) form, is synthesized using a commercial FPGA
synthesis tool. As a result, the netlist contains all typical FPGA primitives,
i.e., FFs, MUXs, and LUTs. The input design requires no special annotations,
synthesis pragmas, or any other change in its representation.

Next, in the second phase, TOTe requires the ASIC standard cell library of
choice. As highlighted in the center of Fig. 2, the core idea of TOTe is to
replace reconfigurable logic for static logic. For TOTe, only the LUTs are
treated as reconfigurable logic, and, any other primitives from the FPGA
synthesis are automatically transformed into static logic. For this phase, the
designer provides an obfuscation target in terms of percentage, which
determines the portion of logic that will remain reconfigurable as LUTs. TOTe
builds a tree representation of the circuit where primitive types are
annotated for every instance. For LUTs, in particular, the tool also annotates
their masking patterns (i.e., the portion of the bitstream associated with an
individual LUT). By using truth tables populated by the masking patterns, TOTe
builds combinational logic that is equivalent to the LUT’s intended usage.
This equivalent logic is what we refer to as the static logic that is used for
replacing the reconfigurable logic. Notice that the equivalent logic is not a
hardwired configurable LUT.

TOTe utilizes its own obfuscation and timing engines. These engines drive the
security vs. performance trade-offs of the tool. Algorithm 1 highlights the
main loop of the tool and its different operations. Here, $L$ is a list of
LUTs, $P$ is a list of timed paths, and $obf_{c}$ is the obfuscation target
criterion. The variables $L\textsubscript{ST}$ and $L\textsubscript{RE}$ are
lists of LUTs in static and reconfigurable form, respectively. The obfuscation
engine is executed until the desired number (determined by the obfuscation
target) of LUTs has been transformed into static logic (line 3), where the
SIZE_OF function returns the size of a list. Inside the obfuscation inner
loop, the critical path is identified (line 4) using the FIND_CRITICAL
function, then the slowest LUT on that path is identified using the
FIND_SLOWEST function (line 5). If the identified LUT is a reconfigurable LUT
(line 6), the lists of LUTs are updated (lines 7-8) and the timing engine
recalculates the timing of affected paths (line 9). If the identified LUT is
not a reconfigurable LUT (line 10), the path is removed (line 11) and the loop
continues (line 3). The INSERT and REMOVE functions update the lists as hinted
by their names. The function GEN_CASE_0_1 generates the constraints to force
the values of the LUTs inputs for the timing and power analysis during
physical synthesis, otherwise, each LUT would be timed for its worst timing
arc instead of the real implemented timing arc when the LUT is programmed. The
algorithm merges $L\textsubscript{ST}$ and $L\textsubscript{RE}$ to generate
eASIC and returns. Finally, TOTe exports an obfuscated hybrid Verilog file
(eASIC), timing report, and area report. A designer can repeat this procedure
until he achieves his obfuscation and performance targets.

Input: $L$ $(list$ $of$ $LUTs$), $P$ $(list$ $of$ $paths)$, $obf_{c}$
$(obfuscation$ $criterion)$

Output: $eASIC\leftarrow f(input)$

1

2$L\textsubscript{ST}\leftarrow\phi$

3$L\textsubscript{RE}\leftarrow L$

4while  _SIZE_OF ( $L\textsubscript{ST}$) $\leq$ $obf_{c}$_ do

5 $path$ $\leftarrow$ FIND_CRITICAL($P$)

6 $lut$ $\leftarrow$ FIND_SLOWEST($path$)

7 if  _$lut\in L\textsubscript{RE}$_ then

8 INSERT($lut$, $L\textsubscript{ST}$)

9 REMOVE($lut$, $L\textsubscript{RE}$)

10 UPDATE_TIMING($lut$, $P$)

11 else

12 REMOVE($path$, $P$)

13

14

15for  _each $lut\in L\textsubscript{RE}$_ do

16 GEN_CASE_0_1($lut$)

17

$eASIC\leftarrow L\textsubscript{ST}\cup L\textsubscript{RE}$

Algorithm 1 Tuneable Obfuscation Technique using eASIC

In the third and final phase, the obfuscated netlist from TOTe is synthesized
using any commercial ASIC CAD tool and implemented using an also commercial
physical synthesis tool where traditional P&R, CTS, DRC, LVS, etc. steps are
executed. Finally, the tapeout database is sent to the foundry for
fabrication. Once the fabricated parts are delivered, they have to be
programmed (i.e., using a bitstream as in FGPAs) for the eASIC design to be
completed and functional.

##  III Experimental results using TOTe

This section reports the analysis of security versus performance, security
versus area for selected designs and reports the results for numerous designs
after obfuscation. For all experimental results that follow, FPGA synthesis
was executed in Vivado and the targeted device is Kintex-7 XC7K325T-2FFG900C,
which contains only 6-input LUTs. For the ASIC flow, the implementations are
done using a commercial 65nm PDK with three standard cell flavors
(LVT/SVT/HVT) and tools from Cadence suite (i.e., Genus and Innovus). However,
we emphasize that TOTe is agnostic with respect to PDKs, libraries, and tools.
In the experiments that follow, we prevent the FGPA synthesis from inferring
any BRAM or instantiating any DSP cells. This choice makes for very clear
trade-offs when obfuscating the logic. Nevertheless, if a given design
requires memory cells, TOTe has the capability to translate the inferred BRAMs
into compiled SRAMs for the specific ASIC technology utilized.

###  III-A Custom standard-cell based LUTs

The premise of eASIC is to have reconfigurable and static elements that can be
integrated transparently. For this reason, we have designed our own custom
LUTs (LUT1, LUT2,…, LUT6) by following VPR’s template [15]. Different from
FPGAs that generally implement only one LUT size, for eASIC we have the
flexibility to implement more than one size because our design intent will not
change. By doing this, we preserve area and potentially increase the
performance of eASIC. The layouts for LUT4, LUT5, and LUT6 macros are shown in
Fig. 3. These blocks are highly compact since the main design goal for them
was area/density. Each LUT has its own registers for storing the
configuration, a functionality that is enabled by including three extra
configuration pins ($serial\\_in$, $serial\\_out$, and $enable$). The LUTs are
connected to one another in a daisy chain that is analogous to a scan chain.
We chose a flip-flop based implementation to make our framework easily
portable between technologies, and also, make the floorplan and placement
almost effortless. Using SRAM for storing those bits, on the other hand, can
save area and power but requires extra effort during implementation since
memories need special power routing and have to be strategically placed to
achieve the best performance.

Figure 3: The layout of macros for LUT4, LUT5 and LUT6. Implementation was
executed in Cadence Innovus.

###  III-B Design Space Exploration in TOTe

For our first experiment, we selected a small but representative design which
covers all possible FPGA primitives: a schoolbook multiplier (SBM), which is a
bit-serial polynomial multiplication circuit. For a SBM design that is
synthesized targeting a very high frequency, the $CP$ and $sumCP$ become, as
calculated by TOTe’s timing engine, 0.490 ns and 16088.69 ns, respectively.
These values correspond to a design obfuscated at 100%, i.e., the design has
only reconfigurable logic. The absolute accuracy of these values is not
relevant since final timing analysis is performed using a commercial physical
synthesis engine later.

While the SBM design is an interesting motivational example, it showed that
$CP$ tends to saturate while the $sumCP$ continues to improve as the
obfuscation is reduced. Next, we wanted to determine if the same saturation
trend appears for other designs and the results are reported in Table I. From
these experiments, it is possible to conclude that the performance of numerous
designs saturates incredibly fast as we decrease the obfuscation level, even
when the obfuscation range is limited to 86-100%. Moreover, the results for
AES-128 [16], RISC-V, and SHAKE-256 have been depicted in Fig. 4. Several
other designs, including ISCAS’85 benchmarks and known opencores, have been
evaluated. The complete set of results can be found in our git repository
[17]. Concerning runtime, TOTe requires only a few minutes for big designs.
Then, commercial CAD tools require a considerable amount of time for logic and
physical synthesis (same as conventional ASIC flow). In summary, TOTe does not
become a bottleneck in the design flow.

TABLE I: Detailed results for selected designs using TOTe Design |  Obf. (%) |  sumCP ($ns$) |  CP ($ns$) |  Area-RE ($\mu m^{2}$) |  Area-ST ($\mu m^{2}$) |  LUT (RE) |  LUT (ST)
---|---|---|---|---|---|---|---
SBM |  98 |  16088.690 |  0.490 |  13190.04 |  0 |  29 |  0
95 |  15895.826 |  0.484 |  12762.00 |  21.40 |  28 |  1
92 |  15877.962 |  0.464 |  12547.80 |  32.11 |  27 |  2
89 |  15458.506 |  0.461 |  12438.72 |  37.56 |  26 |  3
86 |  15370.682 |  0.459 |  12224.52 |  48.27 |  25 |  4
PID |  98 |  2547.581 |  0.756 |  445590.0 |  2816.82 |  896 |  18
95 |  2466.254 |  0.642 |  432340.92 |  9441.36 |  869 |  45
92 |  2391.963 |  0.592 |  421365.95 |  14928.84 |  841 |  73
89 |  2348.613 |  0.568 |  407273.76 |  21974.94 |  814 |  100
86 |  2322.462 |  0.543 |  392345.64 |  29439.00 |  787 |  127
SHA-256 |  98 |  7425.731 |  0.962 |  1313150.76 |  10291.86 |  2195 |  44
95 |  7354.593 |  0.871 |  1275984.00 |  28875.24 |  2128 |  111
92 |  7322.155 |  0.871 |  1233448.56 |  50142.96 |  2060 |  179
89 |  7301.945 |  0.871 |  1179674.64 |  77029.92 |  1992 |  246
86 |  7164.025 |  0.871 |  1125799.56 |  103967.46 |  1925 |  313
FPU |  98 |  2909.063 |  0.707 |  1031676.84 |  1250.028 |  2487 |  50
95 |  2734.008 |  0.650 |  1003225.68 |  2672.586 |  2412 |  126
92 |  2572.952 |  0.650 |  966715.20 |  4498.11 |  2336 |  202
89 |  2478.732 |  0.650 |  935060.04 |  6080.868 |  2259 |  279
86 |  2410.211 |  0.650 |  893005.56 |  8183.592 |  2183 |  355
Figure 4: Obfuscation results for AES-128, RISC-V and SHAKE-256 using TOTe.

##  IV Security Analysis

As compared to conventional logic locking, the LUTs introduced in eASIC are
the key-gate equivalents. In principle, a single LUTn ought to be equivalent
to $2^{n}$ XOR/XNOR key-gates. In practice, the LUT logic has similarities to
a run of key-gates (see [7]) due to the $n$-to-1 multiplexing nature of it,
which reduces the search space and may possibly make eASIC vulnerable to well-
known oracle-based attacks (e.g., SAT). However, notice that we are
considering designs with target obfuscation rates higher than 86%, which
results in bitstreams with thousands of bits. Even for a small and
combinational design as the ISCAS’85 c7552, 50% of obfuscation requires a
bitstream with approximately 11k bits. The SAT attack is not able to find the
correct key, even running for more than 60 hours. On the other hand, the same
circuit with 10% of obfuscation and a bitstream in the order of 1k bits, the
SAT attack was successful, requiring less than a minute to retrieve the
correct key. In general, the high obfuscation percentages obtained in eASIC
discourage an adversary from performing SAT attacks. Similar findings were
reported in [18, 13, 14]. However, our proposed eASIC design _potentially_
creates attack vectors that other approaches do not since a portion of the
design is exposed (from an adversary point of view). We will focus on these
attacks in the text that follows.

###  IV-A Threat Model

In our considered threat model, the primary adversary is the _untrusted
foundry_. We make no distinction whether the adversary is institutional or a
rogue employee. Assuming the security of an eASIC design is a function of its
static logic (fully exposed) and reconfigurable logic (protected by a
bitstream that serves as a key), we make the following assumptions:

  * •

The main adversarial goal is to reverse engineer the design in order to pirate
its IPs, overproduce the IC, or even to insert sophisticated hardware trojans.
For this goal, the adversary must recreate the bistream.

  * •

The adversary goal might also be to identify the circuit intent, even in the
presence of obfuscation. For this goal, the adversary does not need to
recreate the bistream.

  * •

The adversary has access to the GDSII file of the eASIC design. He or she is
skilled in IC design and has no difficulty in understanding this layout
representation. The adversary enjoys access to state-of-the-art CAD tools for
this end.

  * •

The attacker can recognize the standard cells, thus the gate-level netlist of
the obfuscated circuit can be easily recovered [19].

  * •

We assume that the attacker can differentiate between design inputs and
reconfiguration pins [11, 20], thus being able to effortlessly identify all
LUTs and their programming order.

  * •

We assume the adversary can group the standard cells present in the static
logic and convert them back into reconfigurable logic (i.e., LUT
representation)111This is a very generous concession since the static logic is
repeatedly optimized during logic and physical synthesis. Nevertheless, we err
on the side of caution and assume the adversary can achieve a perfect
reconstruction of LUTs, which by itself is a reverse engineering problem..

In order to evaluate the security hardness of eASIC, we propose two different
attacks: one based on the _structure_ of design and another based on the
_composition_ of known different circuits. Being so, we believe that the
adversary can learn and extract information by exploiting the static portion
of the design, including: (1) the frequency of masking patterns (2) the
composition of different designs.

###  IV-B Structural Analysis Attack

Goal: by statistical analysis means, decrease the key search space and attempt
to recover the bitstream.

We recall again that the obfuscation engine of TOTe utilizes six variants of
LUTs (LUT1, LUT2, …, LUT6) during the obfuscation phase. However, the majority
of the LUTs are LUT6 due to the packing algorithm executed during FPGA
implementation. Therefore, let us assume without loss of generality, that any
FPGA-synthesized circuit contains only instances of LUT6s for our security
analysis.

As we mentioned before, the key search space is $2^{64}$ for a single LUT6.
But this assumption only holds if the FPGA synthesis is actually capable of
exercising the entire key search space, which our results reveal that is far
from possible. We have synthesized a large number of representative designs
($>$30) and counted how many unique LUT6 masking patterns appear in the
corresponding netlists. Designs of varied complexity, size, and functionality
where added until the combined number of unique masking patterns appears to
settle, forming a set of $m=3376$ elements. This result alone, albeit being
empirical, reduces the global search space from L1 to L2 as illustrated in
Fig. 5.

Figure 5: The search space of LUT6 as it shrinks with different attacks.

In the next step, we targeted two processor designs in our statistical
analysis: MIPS and RISC-V. For each circuit, we utilize tuples of $\langle
pattern,frequency\rangle$ for tracking how often masking patterns repeat. The
tuples are referenced by integer identifiers and ordered by frequency. Our
analysis reveals that the MIPS netlist has 776 unique LUTs and that there are
very few outliers that occur more than 50 times. Similarly, for RISC-V, there
are 628 unique LUTs and only 3 occur more than 100 times. In practice, if the
attacker could know for a fact that the obfuscated circuits are indeed MIPS
and RISC-V, the search space would shrink further. The shrunk search spaces
are labeled L3 in Fig. 5. The question then becomes whether the static portion
of the circuit is large enough for the adversary to be confident that the
circuit under attack can be labelled as circuit C1, C2, or Cn. We investigate
this possibility by further analysing the behaviour of the frequency of
masking patterns, as depicted in Fig. 6. For this, we utilized polynomial
trendlines for a portion of identifier of masking pattern, considering
netlists generated by TOTe at 98%, 95%, 92%, 89%, and 86% obfuscation levels.
It is noteworthy that the trendlines become better frequency predictors as the
obfuscation level is decreased. For RISC-V, in particular, the adversary can
guess a small number outliers and the best guess (when obfuscation is 86%) is
far from the original frequencies ($>$100).

Figure 6: The structural analysis of MIPS and RISC-V.

###  IV-C Composition Analysis Attack

Goal: identify the circuit by correlation to known circuits.

This attack also exploits the frequency of the LUT6, but here we correlate
entire designs (instead of pattern-frequency tuples) based on their
composition. We consider that the attack is successful if the adversary is
able to identify the circuit (see Threat model, 2nd bullet). Breaking the key
is not necessary for this attack.

In this experiment, we performed correlation analysis for the well-known
SHA-256 crypto core as shown in Fig. 7. The objective of this experiment is to
analyze the leaked information from the static part of an obfuscated design
against a database222We assume the adversary can obtain samples of open source
cores from repositories and execute FPGA synthesis on them with his tool of
choice. of circuits that are known to the attacker. We have obfuscated SHA-256
in the 70-100% range and then correlated the static portion of the design with
the database of known circuits. In Fig. 7, we show the results where the
x-axis shows the obfuscation percentage and the y-axis shows correlation
(right) and number of unique LUTs (left). For this circuit, three regions of
interest can be defined: 97-100% (no correlation), 86-96% (strong correlation
to another circuit), and 70-85% (correlation to itself).

Figure 7: The correlation of SHA-256 versus numerous other designs.

This attack reveals that if the adversary goal is solely to identify the
circuit’s intent, eASIC can be as vulnerable as an ASIC design. To mitigate
this undesirable effect, obfuscation levels should remain relatively high.
Otherwise, if the obfuscation lies between 70 and 84%, the search space would
shift from L3 to L4 as shown in Fig. 5. This is a key finding of our
manuscript and will guide our design choices when implementing the physical
synthesis of eASIC designs in the section that follows.

##  V Physical Synthesis for eASIC

TABLE II: Results for the implementation of SHA-256 for different obfuscation levels CAD Flow |  Obfuscation |  Density |  Area ($\mu m^{2}$) |  Freq. (MHz) |  Leakage ($mW$) |  Dynamic Power ($mW$) |  Total Power ($mW$) |  # LUT |  # Buffer |  # Comb. |  # Inv. |  # Sequential
---|---|---|---|---|---|---|---|---|---|---|---|---
FPGA |  100% |  – |  – |  77 |  158 |  33 |  191 |  2238 |  – |  – |  – |  1830
TOTe |  100% |  46% |  1412227.08 |  166.7 |  17.01 |  257.23 |  274.24 |  2238 |  6234 |  82756 |  4686 |  105128
TOTe |  90% |  45% |  1274690.16 |  178.6 |  15.34 |  246.87 |  262.21 |  2015 |  5411 |  83452 |  4188 |  94876
TOTe |  85% |  46% |  1215328.32 |  200 |  14.62 |  263.20 |  277.82 |  1904 |  5249 |  79626 |  3972 |  90420
TOTe |  80% |  54% |  1135752.20 |  200 |  13.93 |  248.84 |  262.77 |  1792 |  7699 |  74000 |  3755 |  83790
ASIC |  0% |  71% |  43097.40 |  200 |  0.525 |  6.405 |  6.93 |  0 |  119 |  3165 |  128 |  1806
ASIC |  0% |  71% |  60563.52 |  769 |  0.862 |  32.69 |  33.55 |  0 |  336 |  3165 |  128 |  1806

This section contains the physical implementation results for an obfuscated
SHA-256 core. We have selected SHA-256 as it is popular and widely used in
cryptography. The variants of the design with different obfuscation levels are
implemented with the aid of the LUTs defined in Section III-A. The results
obtained after implementation are focused on performance vs. area trade-offs
for the 80-100% obfuscation range as determined by the security analysis of
Fig. 7. Initially, we synthesized and implemented the SHA-256 core on FPGA.
This implementation achieves a frequency of only 77 MHz (for reference, the
Kintex-7 family is produced on a 28nm CMOS technology). To start the analysis,
we select 100% obfuscation as a baseline design because it is fully
reconfigurable and somewhat analogous to an FPGA design.

The implementation results for 0%, 80%, 85%, 90%, and 100% obfuscation are
listed in Table II. These are obtained after physical synthesis and are for
the worst process corner (SS) and a nominal temperature of $25^{\circ}$C. It
is noteworthy that the performance of the design is increasing as we decrease
the level of security. This behaviour is clearly depicted in the fourth column
of Table II and matches the goal we set from the beginning: to trade
performance for security. Here we also show that performance saturates rather
quickly, as predicted by TOTe in Section III-B. The area of the design is
proportional to the obfuscation level which means that increasing the security
of design will cause area overhead. As we only exploit LUT primitives for
promoting obfuscation, the number of LUTs increases with the obfuscation
level. In the same manner, leakage and dynamic power figures are proportional
to security as reconfigurable logic is less efficient than static logic. The
results obtained from the physical synthesis justify trade-offs and the last
five columns of Table II show the resource requirements.

The first three panels (a, b and c) of Fig. 8 illustrate the layouts for 80%,
85% and 90% obfuscation levels. The dimensions of the layouts are indicated on
the bottom and left sides of each panel. All the six variants of LUTs are
highlighted with different colors and the static logic part of eASIC is
highlighted in red – notice that, as expected, the design remains primarily a
sea of LUTs - the reconfigurable logic part. The majority of those LUTs are
LUT6, thus the layouts appear to be dominated by yellow boxes. The placement
of LUTs is done by the ASIC placement tool. For this, we modified the LUT
macros to behave as regular standard cells. Then, the placer exploits its
optimization strategies to place each LUT efficiently. From a magnified view,
the mixed structure of LUT macros and standard cells clearly depicts the
placement pattern, and that spaces between macros are usually filled with
standard cells (static logic part). Notice how the LUT macros align with the
standard cell rows, allowing for the entire design to have a uniform power
rail and power stripe configuration.

Figure 8: Implementation results for SHA-256 with different obfuscation
levels.

##  VI Comparison and discussion

From the many results, we conclude that obfuscation levels should be
relatively high to achieve a considerable security, thus the majority of the
eASIC logic should be reconfigurable logic (i.e., LUTs). Having a large
portion of reconfigurable logic provides an opportunity to correct the
issues/bugs that could be easily fixed during the reconfiguration phase.
Naturally, there are limitations since a portion of the system consists of
static logic and cannot be modified. This limitation could be eased if the
eASIC layout were to include spare LUTs. These same spare LUTs could serve as
decoy LUTs for preventing the composition attack described in Section IV-C,
but at a cost in area, power, and likely timing as well. To some degree, those
spare LUTs could also be used to make side-channel attacks less successful.
These possibilities are not studied in this manuscript but remain promising
concepts for future work.

Our eASIC device presents a largely regular structure upon visual inspection.
This effect can be modulated if it proves to be effective against a reverse
engineering adversary. For instance, we could have mapped LUTs of all sizes to
LUT6, which would increase the layout regularity (i.e., making it only red and
yellow). Similarly, LUTs could have been laid out in a perfect grid fashion.
These two design choices are relatively simple to implement in physical
synthesis but carry overheads that we deemed not advantageous, even if they
make perfect sense for an FPGA device.

A recent trend in obfuscation research is the use of embedded FPGA (eFPGA)
[21, 22]. A very similar approach is also found in [23], where authors perform
obfuscation with transistor-level granularity. While there are advantages to
this practice, it has been used selectively to only protect key portions of a
design and therefore keep the performance penalty as low as possible. The
challenge is in determining which portions of the circuit merit protection and
which ones do not. Our eASIC approach bypasses this question almost completely
by only revealing (portions of) critical paths when they are selected to
become static logic, which we consider an advantage if the ASIC-equivalent
performance can be sacrificed. In [24], the authors present a top-down
methodology to implement ASICs with eFPGAs. Their designs share many of the
advantages of our eASIC solution while presenting more regularity than our
designs (they make use of logic tiles as in commercial FPGAs). Our tile-free
design trades this regularity for performance as evidenced by the layout in
Fig. 8.

##  VII Conclusions

In this paper, we have developed a custom tool (TOTe) that obfuscates a design
and transforms it into an eASIC device. Our eASIC solution contrasts with the
current practice of eFPGA for obfuscation and this is not by coincidence: our
experimental results show that obfuscation rates have to be high to protect
not only the bitstream but also the design’s intent. This is a key finding of
our research which we hope can help to steer current obfuscation practices in
the literature. Our findings are also validated in a commercial physical
synthesis tool with industry-strength timing and power analysis, from which we
confirm that TOTe’s trade-off analysis is sufficiently accurate. Our future
research will focus on the ideas put forward in our discussion, where we argue
that eASIC has many benefits beyond obfuscation.

## References

  * [1] IC Insights, “Semiconductor units forecast to exceed 1 trillion devices in 2021,” [Online]. Available at: https://www.icinsights.com/news/bulletins/Semiconductor-Units-Forecast-To-Exceed-1-Trillion-Devices-Again-In-2021/.
  * [2] S. M. Ben, “Security challenges and requirements for industrial control systems in the semiconductor manufacturing sector,” 2012. [Online]. Available: https://csrc.nist.gov/CSRC/media/Presentations/Security-Challenges-and-Requirements-for-Control-S/images-media/presentation-3_salem.pdf
  * [3] M. Yasin _et al._ , “Removal attacks on logic locking and camouflaging techniques,” _IEEE Transactions on Emerging Topics in Computing_ , vol. 8, no. 2, pp. 517–532, 2020.
  * [4] R. P. Cocchi _et al._ , “Circuit camouflage integration for hardware ip protection,” in _DAC_ , 2014, pp. 1–5.
  * [5] M. Li _et al._ , “Provably secure camouflaging strategy for ic protection,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 38, no. 8, pp. 1399–1412, 2019.
  * [6] K. Zamiri Azar _et al._ , “Threats on logic locking: A decade later,” in _GLSVLSI ’19_ , 2019, p. 471–476.
  * [7] M. Yasin _et al._ , “On improving the security of logic locking,” _IEEE TCAD_ , vol. 35, no. 9, pp. 1411–1424, 2016.
  * [8] J. Sweeney _et al._ , “Latch-based logic locking,” in _2020 IEEE HOST_ , 2020, pp. 132–141.
  * [9] T. D. Perez _et al._ , “A survey on split manufacturing: Attacks, defenses, and challenges,” _IEEE Access_ , vol. 8, pp. 184 013–184 035, 2020.
  * [10] J. Rajendran _et al._ , “Is split manufacturing secure?” in _2013 DATE_ , 2013, pp. 1259–1264.
  * [11] P. Subramanyan _et al._ , “Evaluating the security of logic encryption algorithms,” in _2015 IEEE HOST_ , 2015, pp. 137–143.
  * [12] B. Liu _et al._ , “Embedded reconfigurable logic for asic design obfuscation against supply chain attacks,” in _2014 DATE_ , 2014, pp. 1–6.
  * [13] H. Mardani Kamali _et al._ , “Lut-lock: A novel lut-based logic obfuscation for fpga-bitstream and asic-hardware protection,” in _2018 IEEE ISVLSI_ , 2018, pp. 405–410.
  * [14] S. D. Chowdhury _et al._ , “Enhancing sat-attack resiliency and cost-effectiveness of reconfigurable-logic-based circuit obfuscation,” in _2021 IEEE ISCAS_ , 2021, pp. 1–5.
  * [15] K. E. Murray _et al._ , “Vtr 8: High-performance cad and customizable fpga architecture modelling,” _ACM Transactions on Reconfigurable Technology and Systems_ , vol. 13, no. 2, 2020.
  * [16] H. Hsing, “Aes-128,” 2013. [Online]. Available: https://opencores.org/projects/tiny_aes
  * [17] Z. U. Abideen _et al._ , “TOTe (Tuneable Design Obfuscation Technique using eASIC),” 2021. [Online]. Available: https://github.com/Centre-for-Hardware-Security/eASIC
  * [18] G. Kolhe _et al._ , “Security and complexity analysis of lut-based obfuscation: From blueprint to reality,” in _2019 IEEE ICCAD_ , 2019, pp. 1–8.
  * [19] R. Torrance _et al._ , “The state-of-the-art in ic reverse engineering,” in _CHES 2009_ , C. Clavier _et al._ , Eds., 2009, pp. 363–381.
  * [20] M. Yasin _et al._ , “Provably-secure logic locking: From theory to practice,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, p. 1601–1618.
  * [21] B. Hu _et al._ , “Functional obfuscation of hardware accelerators through selective partial design extraction onto an embedded fpga,” in _GLSVLSI ’19_ , 2019, p. 171–176.
  * [22] J. Chen _et al._ , “DECOY: DEflection-Driven HLS-Based Computation Partitioning for Obfuscating Intellectual PropertY,” in _2020 IEEE DAC_ , ser. DAC ’20. IEEE Press, 2020\.
  * [23] M. M. Shihab _et al._ , “Design obfuscation through selective post-fabrication transistor-level programming,” in _2019 DATE_ , 2019, pp. 528–533.
  * [24] P. Mohan _et al._ , “Top-down physical design of soft embedded fpga fabrics,” in _The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , 2021, p. 1–10.


# HyperGraphDis: Leveraging Hypergraphs for Contextual and Social-Based
Disinformation Detection

Nikos Salamanos1, Pantelitsa Leonidou1, Nikolaos Laoutaris2, Michael
Sirivianos1,
Maria Aspri3, Marius Paraschiv2

###### Abstract

In light of the growing impact of disinformation on social, economic, and
political landscapes, accurate and efficient identification methods are
increasingly critical. This paper introduces HyperGraphDis, a novel approach
for detecting disinformation on Twitter that employs a hypergraph-based
representation to capture (i) the intricate social structure arising from
retweet cascades, (ii) relational features among users, and (iii) semantic and
topical nuances. Evaluated on four Twitter datasets – focusing on the 2016
U.S. Presidential election and the COVID-19 pandemic – HyperGraphDis
outperforms existing methods in both accuracy and computational efficiency,
underscoring its effectiveness and scalability for tackling the challenges
posed by disinformation dissemination. The HyperGraphDis displayed exceptional
performance in an evaluation using a COVID-19-related dataset, achieving an
impressive F1 score of approximately 92.5%. This result represents a notable
improvement of around 7% compared to other existing methods. Additionally,
significant enhancements in computation time were observed for both model
training and inference processes. In terms of model training, completion times
were noticeably accelerated, ranging from 1.6 to 16.5 times faster than
previous benchmarks. Similarly, during inference, computational times
demonstrated increased efficiency, ranging from 1.3 to 17.7 times faster than
alternative methods.

## Introduction

Social media platforms have evolved from mere forums for informal conversation
and idea exchange into essential tools for a diverse array of entities,
including non-governmental organizations, businesses, governments, and media
outlets. Their ubiquity and ability to personalize content according to user
behavior make them pivotal in the modern social landscape. Platforms like
Twitter (currently known as X) and Facebook now serve as the principal sources
of information on a worldwide scale (Westerman, Spence, and Van Der Heide
2014). Nevertheless, the dissemination of false information on these platforms
can exert substantial detrimental effects on society (Chenzi 2021), politics
(Safieddine 2020), and the economy (Visentin, Pizzi, and Pichierri 2019; Cheng
and Chen 2020), making it a rapidly escalating cyber threat (Belova and
Georgieva 2018).

Contemporary techniques for identifying disinformation on social media chiefly
focus on partial data, either concerning user behavior or the topology of the
local network (see Section Related Work for related works). Such an approach
could yield unsatisfactory outcomes, as disinformation typically arises from a
complex interplay of numerous elements, both intrinsic (such as user traits)
and extrinsic (like network features and the content of posts).

In the present study, we aim to enhance the ability to detect disinformation
on social media by introducing an integrated approach that considers both
intrinsic and extrinsic variables. We chose Twitter as the platform for
illustrating the efficacy of our proposed technique. On Twitter, the primary
activities include the creation of messages (tweets) by authenticated users
and the sharing of those messages (retweets) by others within the ecosystem.
Posting a message concerning a specific subject initiates a root-tweet (the
originating tweet that gets retweeted), which is then followed by a sequence
of retweets from various users. This sequence of retweet actions culminates in
a tree-like graph formation, commonly referred to as a retweet cascade.

In our study, we introduce an innovative approach named HyperGraphDis, that
utilizes a hypergraph data structure to encapsulate both the content of
Twitter cascades and the relational information among users. The rationale
behind employing a hypergraph lies in its capability to represent complex
relationships in a more natural manner than traditional graphs. Unlike a
standard graph that is comprised of vertices connected by edges, a hypergraph
consists of hyperedges that can connect more than two nodes. This facilitates
a more nuanced representation of Twitter interactions, taking into account
both the content of tweets and retweets (the Twitter cascades) as well as the
network of users who are participating in these cascades.

The initial phase in constructing this hypergraph involves applying a graph
partitioning algorithm to the existing social network of Twitter users. The
network consists of nodes representing users and edges representing their
social connections. Utilizing graph partitioning algorithms enables us to
effectively identify clusters of users who demonstrate similar patterns of
interactions or content sharing. The essence of graph partitioning in this
context is to optimize the divisions in such a way that intra-cluster
connections are maximized while inter-cluster connections are minimized,
thereby identifying natural communities within the Twitter user base.

Upon identifying these user clusters, we undertake a transformation wherein
each user in a cluster is substituted with a list of Twitter cascades they
have partaken in. In the hypergraph framework, each previously discovered
cluster becomes a hyperedge. The Twitter cascades, which are sequences of
tweets and retweets initiated by a root-tweet, are represented as the nodes
within these hyperedges. This transformation inherently reshapes the problem
space: it turns the complex task of disinformation classification on Twitter
from an intricate, multi-variable problem into a more straightforward node
classification problem within the hypergraph.

The use of hypergraph data structures offers several advantages over
traditional graphs. Unlike conventional graph edges that connect only pairs of
nodes, a hyperedge in a hypergraph links an entire cluster of users, thereby
enriching the relational information in the dataset by capturing multi-way
associations. This multi-faceted relational insight becomes even more potent
when considering hyperedge intersections, which naturally coincide with the
overlap of user clusters. Such overlaps allow for a nuanced understanding of
classes of users sharing specific common features, further augmenting the
dataset’s expressiveness. Moreover, hypergraphs inherently result in less
dense network representations, yielding benefits in terms of reduced
computational processing times and more efficient storage requirements. This
makes hypergraphs an excellent choice for the effective modeling of complex
relational systems.

Moreover, we enrich each Twitter cascade node with a set of features or
attributes that describe the cascade’s characteristics. These may include, for
instance, the frequency of specific keywords, sentiment analysis scores, or
the presence of verified accounts within the cascade. By doing so, we
transform the issue of classifying Twitter cascades in terms of disinformation
into a node classification task within the hypergraph. For the node
classification task, we employ hypergraph neural networks, a modern machine
learning approach optimized for hypergraph structures.

The results from our experiments demonstrate that our hypergraph-based method
not only yields performance metrics that are comparable to or exceed existing
methods relying on both tweet content and user relationships, but it also does
so with the advantages of reduced data size and faster classification run
times. Moreover, the inherent design of our method makes it highly scalable,
allowing it to adapt to varying sizes and complexities of data. Given the
ever-increasing volume of data in social networks like Twitter, the
scalability and adaptability of our approach make it an especially suitable
tool for real-time disinformation detection in large-scale, dynamic social
media ecosystems.

The HyperGraphDis approach demonstrated exceptional performance with an F1
score of approximately 92.5%, surpassing the Meta-graph method (Paraschiv et
al. 2022) by roughly 7% (Table 5) and the state-of-the-art ML text-based
techniques by 13.1% (Table 1), as observed in the evaluation conducted using
the MM-COVID dataset. Furthermore, noteworthy enhancements were observed in
the computation time for both model training and inference processes.
Regarding model training, the completion time is notably expedited, ranging
from 1.6 times to 16.5 times faster than previous benchmarks. Similarly,
during inference, computational time exhibits increased efficiency, ranging
from 1.3 times to 17.7 times faster than the Meta-graph method.

We assess the effectiveness of our approach in four datasets: (i) an extensive
dataset pertaining to the 2016 U.S. Presidential Election, which includes
152.5 million tweets from 9.9 million users; (ii) a large collection of tweets
related to COVID-19 pandemic together with social engagement data (Li et al.
2020); and (iii) the HealthRelease and HealthStory datasets, which are
components of the FakeHealth repository (Dai, Sun, and Wang 2020).

Data availability: Part of the US Elections dataset is publicly available
(Salamanos et al. 2023) under proper restrictions for compliance with
Twitter’s Terms of Service (Tos), General Data Protection Regulation (GDPR).
The FakeHealth repository and the MM-COVID dataset are publicly available
(Dai, Sun, and Wang 2020), (Li et al. 2020).

## Related Work

Considerable research has been dedicated to the problem of identifying false
information on social media platforms. Initial methods primarily focused on
feature-based detection at the individual user level. The work by (Ahmed,
Traore, and Saad 2017), for instance, employs a variety of feature extraction
techniques on social media content to identify linguistic patterns indicative
of disinformation. However, this approach fails to account for the relational
data between the information sources and the users on platforms like Twitter.
Similarly, (Ghosh and Shah 2018) decompose the problem into two distinct
phases: feature extraction and classification, while (Zhang, Zhao, and Lecun
2015) employ character-level convolutional neural networks to merge these
steps. More contemporary methods include the use of BERT language models for
feature extraction as outlined by (Kaliyar, Goswami, and Narang 2021) and
reviewed in depth by (Zhou and Zafarani 2020). On another front, (Castillo,
Mendoza, and Poblete 2011) evaluate the trustworthiness of social media posts
by examining the historical behavior of users, the content of the tweets, and
additional external data. (Shu et al. 2020) take a different tack by
extracting features from individual user profiles to identify those more
likely to disseminate false information. This bears resemblance to the
strategies discussed in (Tacchini et al. 2017; Guo et al. 2018; Jin et al.
2017), which leverage characteristics of user types to categorize posts as
false or genuine.

Turning to methods that incorporate social context, these consider both the
relationships between users sharing news and additional contextual information
about the user and the news content. (Gupta, Zhao, and Han 2012) introduce an
approach that evaluates credibility through a network that includes events,
tweets, and users. While this conceptually aligns with our method, it
overlooks the complex structural data of information cascades and their
similarities. (Shu et al. 2019) suggest a co-attention mechanism between
sentences and comments to explain why a news item is flagged as false by an
algorithm. Concurrently, (Wu and Liu 2018) focus on identifying false
information by analyzing its propagation behavior across the network.

A method closely related to ours is discussed by (Shu, Wang, and Liu 2019),
where an embedding framework known as TriFN is utilized. It models the
relationships between publishers and news items, as well as user interactions
with those news pieces. However, it lacks the incorporation of relational data
between events or cascades, which can be crucial for evaluating historical
user behavior. Additionally, it does not leverage semantic features gained
through topic modeling and sentiment analysis. Another noteworthy method is
presented by (hierarchical), who construct a hierarchical propagation network
for false information and engage in a comparative study between false and true
news from linguistic, structural, and temporal lenses.

We mention here other recent efforts, such as (Chen et al. 2022), which
employs automatic methods and machine learning models like RoBERTa-large to
assess the veracity of claims in medical datasets. This work complements
efforts in understanding web-based relationships, where (Hanley, Kumar, and
Durumeric 2023) utilizes Common Crawl data to analyze hyperlinks between
websites. In (Hanley and Durumeric 2023), the authors present a comprehensive
framework to study Reddit communities, targeting misinformation, toxicity, and
political polarization. Similarly, (Pratelli et al. 2023) delve into the
behavior of social bots on Twitter, categorizing them based on their political
leanings during the 2018 U.S. midterms.(Balcı, Sirivianos, and Blackburn 2023)
extend this by introducing metrics, MRD and MRS, to quantify user migrations
across subreddits on the Reddit social platform. Furthermore, (Elmas,
Overdorf, and Aberer 2023) explores the problem of inauthentic behavior, using
supervised learning to detect repurposed Twitter accounts, shedding light on
their characteristics and behaviors. In (Kozik et al. 2023), the authors
conducted an extensive meta-analysis of Machine Learning techniques applied to
text-based fake news detection. The models that underwent formal evaluation
represent cutting-edge solutions in natural language processing, including
Random Forest, CNN-based, LSTM-based, and BERT-based models. Performance
assessments were carried out using various benchmark disinformation datasets,
among which was the MM-COVID dataset (see Table1). In this study, we evaluated
the HyperGraphDis method using the MM-COVID dataset and the results show that
our approach consistently outperforms all the aforementioned text
classification models in regards to F1 score. This performance advantage
underscores the value of incorporating social network graph data and user-
related features alongside text-based features in enhancing fake news
detection tasks. In (Dhanasekaran et al. 2021), the authors introduce the
SOMPS-Net framework, comprising two essential components: the Social
Interaction Graph and the Publisher and News Statistics. Tested with the
HealthStory dataset, it achieved a 73% accuracy and 79% F1 score in the realm
of fake news prediction. We tested HyperGraphDis using the same dataset,
although we observed slightly diminished results, specifically an accuracy of
62% and an F1 score of 65%. We attribute this decline in performance to the
inherent characteristics of the cascades within the HealthStory dataset, which
tend to be either extremely small or predominantly structured like star-like
graphs. This characteristic leads to embedding vectors that exhibit high
levels of similarity, consequently affecting the overall effectiveness of our
method.

The closest method to the one described in the present work is that of
(Paraschiv et al. 2022), where a meta-graph method is introduced to capture
content and relational information. We compare against this method and show
that HyperGraphDis offers improved results, a lower data footprint as well as
greater computational efficiency.

In evaluating the performance metrics of our proposed method, several key
factors underscore its superiority, particularly when compared to classical
graph-based approaches. First, the inherently reduced connectivity of the
hypergraph structure yields faster computational times and minimizes hardware
resource requirements. This efficiency is not achieved at the expense of
informational richness; to the contrary, hyperedges encapsulate a wealth of
multi-way relationships among nodes, providing a more nuanced understanding of
underlying data patterns. Additionally, the intersections of hyperedges serve
as focal points for identifying user subsets with highly detailed common
features, adding an extra layer of depth to the dataset’s relational
information content.

Training Features |  Dataset |  Model |  Accuracy |  F1 Score
---|---|---|---|---
SOMPS-Net (Dhanasekaran et al. 2021)
User, network, content |  Health Story |  GCN |  0.727 |  0.796
State-of-the-art ML text-based techniques (Kozik et al. 2023)
content |  MM-COVID |  Random Forest |  0.876 |  0.633
CNN |  0.881 |  0.673
LSTM |  0.904 |  0.750
BERT |  0.925 |  0.794
Table 1: Alternative approaches to detect disinformation across datasets
employed in HyperGraphDis evaluation

## Similar Approaches

### Meta-graph

In reference (Paraschiv et al. 2022), the authors introduce a meta-graph data
structure to represent events in a social network. Formally, a meta-graph
$\mathcal{G}=(V,E)$ consists of vertices $V$ and edges $E$, where each vertex
corresponds to a social network event and is characterized by a feature vector
$X_{v}$.

The node feature vector $X_{v}$ encapsulates user attributes, tweet content,
and cascade structural information. Specifically,
$X_{v}=(C_{\text{emb}}||X_{u}||T_{\text{emb}}||S\ldots)$, where $||$ signifies
vector concatenation. The term $C_{\text{emb}}$ denotes the cascade embedding
vector, $X_{u}$ encompasses concatenated user features, $T_{\text{emb}}$ is
the text embedding vector, and $S$ represents sentiment analysis scores if
available (Perozzi, Al-Rfou, and Skiena 2014; Devlin et al. 2019).

Edges in the meta-graph are constructed based on common users or topics and
are described by edge feature vectors $R_{e_{i,j}}$. An example vector is
$R_{e_{i,j}}=(N_{u_{i,j}}||V_{i,j}||H_{i,j}\ldots)$. Here, $N_{u_{i,j}}$
indicates the number of common users between cascades $i$ and $j$, $V_{i,j}$
is a graph similarity metric, and $H_{i,j}$ is a content similarity metric
between the root-tweets of the two cascades (Zager and Verghese 2008; Blondel
et al. 2004; Zhao et al. 2020; Bisseling 2020; Gomaa and Fahmy 2013). Both
node and edge feature vectors are designed for facile extensibility, allowing
the incorporation of additional relational information when needed.

Figure 1: A toy example of the proposed hypergraph construction pipeline

Despite its utility in certain scenarios, the meta-graph method presents
several notable limitations that hamper its broader applicability. One primary
drawback is the high density of its graph representation, which demands
considerable computational resources and results in an increased hardware
footprint. Additionally, the meta-graph edges are confined to capturing
bipartite connections between entities, failing to represent more complex
relational information. This restrictiveness also impedes the exploitation of
partial feature overlaps among different user clusters. To overcome these
challenges, the subsequent section introduces HyperGraphDis, a novel approach
that employs a hypergraph data structure to address these inherent
shortcomings effectively.

## The HyperGraphDis Method

The HyperGraphDis method addresses the detection of disinformation in social
networks by exploiting network structure as well as post content and user
sentiment. As we will show in the next section, the network structure has a
clear impact on classification results. As part of the HyperGraphDis method, a
hypergraph is constructed from the user-user social network as well as the
individual tweet-retweet cascades, which will serve as the nodes of the
hypergraph. The hypergraph structure is used to perform binary classification
of retweet cascades into fake and not-fake classes. Two primary challenges
need to be tackled to apply our methodology to the raw Twitter data. First,
the actual structure of the social network, specifically the follower graph,
remains largely unknown, as access to users’ follower lists is not always
available. Second, the data obtained through the Twitter API offer limited
insights into the origins of influence within retweet cascades. This is
implemented by the social network as a privacy-preserving measure. The only
accessible information consists of the root-tweet and the root-user associated
with a particular retweet. In simpler terms, all retweeters are linked to the
root user, creating a star-like cascade structure that does not always
accurately represent user-to-user interactions or the course of information
diffusion. The methodology steps to address the above issues are the
following:

### Phase-1: The Hypergraph construction

Given a large collection of tweets, we construct a hypergraph with the retweet
cascades as nodes from the dataset in question. (i) From the overall
collection of tweets (tweets, replies, retweets), we construct the user-user
social network – the graph of interactions between the users. This graph
represents an approximation of the Twitter social network. (ii) We partition
this graph (in disjoint sets of nodes/users) by applying METIS – a state-of-
the-art graph partitioning algorithm. Then, in each partition (set of users),
we replace the users with the retweet cascades that have participated. The end
result is a hypergraph where the nodes are the retweet cascades.

Figure 1 presents a toy example of the main HyperGraphDis phases for the
hypergraph construction where the classification of disinformation is taking
place. The hypernodes are the cascades that are represented by feature vectors
(as defined in the next Section, “Phase-2: The Hypernodes features vectors”).
In our methodology, a hyperedge connects two or more cascades if the users of
the same partition of the Twitter social graph participate in these cascades.
To illustrate this, consider the social network and the corresponding graph
partition in Figure 1(A) & (B). Initially, we create a user-to-cascades
mapping, as shown in Figure 1(C). Subsequently, we replace each user within a
given partition from Figure 1(B) with the cascades they have engaged with from
Figure 1(C). This process leads to the formation of the hypergraph (Figure
1(D)) where the hyperedges connect these sets of cascades. The construction of
the hypergraph is scalable since several types of cascade connections
(hyperedges) can be defined. For example, we can construct hyperedges based on
tweet hashtags; i.e., two or more cascades belong to the same hyperedge if the
root-tweets have the same hashtag. In Figure 1, we illustrate the process of
building the cascades hypergraph. This begins with the formation of the social
network and follows through to capturing users’ participation in cascades, all
based on the selected Twitter dataset under consideration. A detailed
description of the proposed pipeline is as follows:

(A): Social Network Construction Initially, we create an approximation of the
Twitter social graph, also known as the follow-graph, grounded in the
activities of users within our dataset. Within this social network, each user
corresponds to a node. We add a directed edge for any interaction between two
nodes. The “interactions” are defined by the user-user actions in the Twitter
platform, such as “retweet,” “reply”, or “mention”. Hence, an edge(i,j)
between two nodes implies that the node i follows the node j. The output of
this process is a multi-graph because of the possibility of multiple
interactions (edges) between two nodes. We remove the duplicate edges and keep
the earliest one.

(B): Graph Partitioning Having the resulting Twitter social graph, we conduct
graph partitioning to identify communities or groups of users. After applying
the selected graph partitioning technique, we get a list of users per
partition. In this paper, we leverage the METIS graph partitioning algorithm
(Karypis and Kumar 1998); a state-of-the-art method in graph-based data
analysis. METIS, short for ”MEsh-based and Two-level ISomeric Scheme,” stands
out for its efficiency and scalability in identifying cohesive substructures
(such as clusters or communities) within large and intricate networks,
including social networks, citation networks and biological networks. Its
methodology involves recursively partitioning a graph into more manageable
subgraphs, beginning with graph partitioning to identify densely connected
regions. The process includes a refinement phase to minimize inter-cluster
connections, hierarchical clustering to explore clusters at different
granularity levels, and a focus on balanced load distribution, ensuring
roughly equal cluster sizes. Other candidate approaches are the community
detection methods such as Louvain (Blondel et al. 2008) and Infomap (Rosvall
and Bergstrom 2008) that are highly efficient in identifying communities or
clusters within complex networks. Preliminary results in the 2016 US Election
and FakeHealth datasets show quite lower performance than METIS. In short, the
classification performance of HyperGraphDis on the hypergraphs that have been
constructed by the Louvain or Infomap graph partitions was quite low in both
accuracy and F1 score. For instance, in the US Election dataset using the
Louvain partition (14 communities), we have achieved an $\text{accuracy}\text{
of }0.713$ and an $\text{f1 score}\text{ of }0.80$. For the Infomap partition
(2074 clusters), we obtained an $\text{accuracy}\text{ of }0.826$ and an
$\text{f1 score}\text{ of }0.866$.

(C): User to Cascades mapping We define a list of users that are involved in
each cascade based on the raw Twitter data. Finally, we derive a user-to-
cascade mapping that denotes that a given user $i$ participated in the set of
cascades {x, y, z}.

(D): The final Hypergraph Using the graph partition from Step-(B) and the
mapping User-to-Cascades from Step-(C), we replace the users in the partition
clusters with the list of cascades they participated in. This process results
in sets of cascades (removing the duplicates), which will define the
hyperedges of the final hypergraph.

Figure 2: A toy example of a hypergraph node. Left-hand: the raw retweet data
provided by Twitter AI always corresponds to a star-like graph with limited
structural information. Right-hand: We enhance the raw data by appending to
the raw star-graph the past interactions between the retweeters (i.e. the
users). Finally, in this enhanced subgraph, we compute the node embeddings
using the DeepWalk algorithm. Bottom: The final feature vector consists of the
DeepWalk embeddings together with users’ features and tweet-text features
(topics, sentiments etc.)

### Phase-2: The Hypernodes features vectors

A retweet cascade is a series of chain events upon the same root-tweet where
users have retweeted the root–tweet, whereas some others have retweeted a
retweet of a friend (retweet of a retweet). This tree-like structure reflects
who was influenced by whom during the retweeting process. Unfortunately, the
raw data by Twitter API does not provide that since it contains only the root-
user and retweeter IDs. In short, the raw–data corresponds to a star-like
graph where all the retweeters are connected with the root–user only. As a
result, this form does not provide sufficient structural information.

To tackle this issue, we construct a subgraph comprising the star-like graph
along with past interactions involving the users who have participated in the
cascade in question. Specifically, for a given retweeter $i$ who engaged in
the retweet action at date $t$, we determine their pre-date $t$ connections
among their friends and ascertain which of them are among the retweeters in
this cascade. Subsequently, we augment this collection of edges, if present,
with the star-like configuration where each retweeter maintains a connection
with the root user. Finally, we eliminate any duplicate edges and transform
the resulting graph into an undirected representation. Through this
methodology, the subgraph consistently retains its connectivity.

The rationale of this approach is that each cascade (i.e., a node of the
hypergraph) should have the corresponding subgraph structure as a feature that
will reflect the social interactions that the retweeters had. For this
purpose, we apply the DeepWalk algorithm (Perozzi, Al-Rfou, and Skiena 2014)
to produce the embedding of a cascade subgraph to a low dimensional space. For
the implementation, we used the Karate Club extension for the NetworkX
(Rozemberczki, Kiss, and Sarkar 2020). The DeepWalk embedding is a $N\times
128$ matrix, where $N$ is the number of retweeters. The default parameters
are: (i) $\text{Number of random walks}=10$; (ii) $\text{Length of random
walks}=80$ and for embeddings (iii) $\text{Dimensionality of embedding}=128$.

Figure 2 provides a toy example: (a) Left-hand figure: the raw data that are
provided by Twitter API correspond to a star-like graph structure with limited
structural information regarding the user-user relation between the
retweeters. (b) Right-hand figure: The augmented Bottom figure: the final
cascade object – a set of features that represent the retweet cascade. The
feature vector consists of the individual users’ features, the DeepWalk
embeddings as well as topic and sentiment analysis (as the tweet-text
features). This will be part of the training data of HyperGraphDis.

## Dataset Descriptions

### US Elections Dataset

The dataset comprises 152.5 million tweets from 9.9 million users related to
the 2016 US presidential election, a period notable for the appearance of a
series of disinformation campaigns. These tweets were harvested between
September 21st and November 7th, 2016, using the Tweepy Python library. To
ensure political relevance, the dataset includes tweets that contain one or
more of 77 specific track terms such as “hillary2016”, “clinton2016”,
“trump2016”, and “election2016”. Each tweet in the dataset is rich in
features, encapsulating 27 different attributes pertaining to the tweet itself
(e.g., tweet-ID, tweet-text) and the corresponding Twitter account (e.g.,
user-ID, screen name, number of followers). Additional metadata, like mentions
and embedded URLs, are also part of the dataset.

Root-Tweets | 46,409 | Root Users | 8204
---|---|---|---
Retweets | 19,588,072 | Retweeters | 3,630,992
URLs (web and media) | 43,989

Table 2: US Elections dataset: Retweet cascades with at least 100 unique
retweeters

A significant subset of this dataset contains 35.5K tweets from 822 verified
state-sponsored Twitter accounts111https://about.twitter.com/en/our-
priorities/civic-integrity, or “trolls,” which were active during this period.
This subset serves as a ground-truth for state-sponsored disinformation
campaigns and has been validated with data provided by Twitter (Salamanos et
al. 2023).

The dataset also focuses on retweet cascades, specifically those that are rich
in transmitted information and have a broad user engagement. These are the
cascades where the original tweet (root-tweet) includes at least one web or
media URL and has been retweeted by a minimum of 100 users (Table 2). A total
of 46.4K such retweet cascades, encompassing 19.6 million tweets, are included
for analysis.

This dataset is a robust resource for studying the dynamics of disinformation
and political polarization on social media, particularly concerning the 2016
US presidential election. It offers an extensive set of features and a sizable
volume of ground-truth data, making it well-suited for both supervised and
semi-supervised learning tasks.

URL Labels: The dataset includes labeled URLs categorized as “fake”, “non-
fake”, or “unknown”. These labels were derived through a multi-step
methodology. Initially, all shortened URLs in the dataset were expanded using
the unshrtn tool to facilitate matching with pre-existing labeled URLs. The
dataset was then enriched with approximately 0.5 million labeled URLs
aggregated from over 25 related open-source research projects focused on the
2016 US elections.

A labeling consistency check was performed to ensure the reliability of the
aggregated labels. Inconsistent labels were set aside for manual validation.
URL matching was conducted to correlate the URLs in our dataset with the
aggregated labeled URLs, resulting in an initial set of labeled data. To
further extend the labeled URLs, manual annotation was performed on a subset
of unknown URLs using four different Fact-Checking tools: PolitiFacts, Media
Bias/Fact Check (MBFC), FactCheck, and Snopes. Priority for manual annotation
was given to URLs that appeared multiple times in the dataset after expansion.
The dataset thus contains a well-curated set of URLs with labels that have
undergone rigorous verification and validation processes, making it a valuable
resource for supervised or semi-supervised learning tasks related to
disinformation analysis.

### MM-COVID Dataset

The authors in (Li et al. 2020) created a multilingual and multimodal dataset
(MM-COVID) to combat misinformation on COVID-19. Despite the news content, the
dataset also contains Twitter’s social network and spatial-temporal
information. The dataset consists of approximately 4K fake news articles and
about 7K trustworthy articles related to COVID-19 across six languages:
English, Spanish, Portuguese, Hindi, French, and Italian. In the English
language subset alone, there are over 1K fake news documents and approximately
5K legitimate articles. We dehydrated the user engagement data only for the
English language dataset subset using Twarc222https://twarc-
project.readthedocs.io/en/latest/ (a Python library for collecting data via
Twitter API). Only a subset of the data was available to collect at the time
of the dehydration of the existing dataset. In summary, for the experimental
evaluation, we used 53,869 tweets, 10,387 replies, and 85,121 retweets by
93,152 users. From this dataset, we kept the cascades that have at least 10
participants. The tweets are in English language, only; the quoted tweets have
been discarded.

### FakeHealth Datasets

To rigorously assess the efficacy of our proposed methodology, we employ two
datasets originating from the FakeHealth repository (Dai, Sun, and Wang 2020).
While the authors of the repository are constrained by Twitter’s user privacy
policies from publicly disseminating the full extent of user engagement and
network data, they have circumvented this limitation by offering an API
https://github.com/EnyanDai/FakeHealth. This API facilitates the acquisition
of comprehensive data pertaining to users’ social engagements and networks.

We have utilized this API to gather all requisite information, the summary of
which is delineated in Tables 3. It is noteworthy that the final data metrics
we report exhibit a marginal reduction, approximately 1.1%, compared to the
figures disseminated by the original authors. Several factors contribute to
this discrepancy: (1) modifications in user settings that restrict public
accessibility to their tweets, (2) deletions of tweets by Twitter in adherence
to their internal policies, and (3) the outright deletion of Twitter user
accounts.

| HeathRelease | HealthStory
---|---|---
tweets | 43,245 | 357,851
replies | 1418 | 23,632
retweets | 15,343 | 105,712
Total | 60,006 | 487,195
Table 3: FakeHealth repository: Tweets, replies and retweets in the collected
datasets

## Evaluation of Performance Benefits

In this section, we evaluate HyperGraphDis across all four previously
mentioned datasets and simultaneously compare it with the Meta-graph approach.
First, we present the basic structures across the four datasets that are the
input of the HyperGraphDis and Meta-graph methods, and then we discuss the
actual classification performance.

The code has been implemented in Python and executed in the CPU of an ASUS
laptop with Intel Core i7-6700HQ CPU 2.60GHz × 8; 32GB RAM; Ubuntu 22.04.3
LTS. The HypergraphConv (Bai, Zhang, and Torr 2021) and GCNConv (Kipf and
Welling 2017) have been implemented in PyTorch Geometric (Fey and Lenssen
2019), maintaining the following hyperparameters constant across experiments:

$\text{\\# of epochs}=100,\text{dropout}=0.5,\text{learning rate}=5*10^{-4}$

Finally, we use an 80/20 train-test split.

### Social Networks

The undirected version of the four social networks has the following
characteristics:

US Election: Total nodes: 482,171. Total edges: 34,691,548. The network is
connected.

MM-COVID: Total nodes: 38,813. Total edges: 50,688. The network is composed of
four connected components, with the largest (giant component) having 38,729
nodes.

Health-Release: It comprises 18,470 nodes. There are 21,502 edges. The network
exhibits a significant level of disconnection, with 1,595 connected
components. The largest connected component contains 13,543 nodes.

Health-Story: It is substantial in size, with 147,607 nodes. There are 187,096
edges. The network is highly fragmented into 12,719 connected components. The
largest connected component encompasses 108,854 nodes.

METIS | 2016 US Election | MM-COVID | Health Story | Health Release
---|---|---|---|---
(#Clusters) | Accuracy | F1 Score | Accuracy | F1 Score | Accuracy | F1 Score | Accuracy | F1 Score
20 | 0.824 | 0.685 | 0.870 | 0.906 | 0.727 | 0.839 | 0.619 | 0.656
50 | 0.835 | 0.697 | 0.854 | 0.893 | 0.742 | 0.844 | 0.579 | 0.616
100 | 0.845 | 0.712 | 0.895 | 0.927 | 0.739 | 0.842 | 0.581 | 0.604
300 | – | – | 0.856 | 0.890 | – | – | – | –
500 | 0.847 | 0.721 | 0.895 | 0.925 | 0.755 | 0.851 | 0.596 | 0.605
1000 | 0.867 | 0.756 | 0.895 | 0.923 | 0.739 | 0.835 | 0.609 | 0.648
2000 | 0.867 | 0.760 | – | – | 0.729 | 0.826 | 0.591 | 0.632
3000 | 0.867 | 0.755 | – | – | 0.735 | 0.828 | 0.602 | 0.636
4000 | 0.868 | 0.744 | – | – | 0.720 | 0.814 | 0.563 | 0.554
5000 | 0.846 | 0.706 | – | – | 0.734 | 0.831 | 0.563 | 0.568
Table 4: Evaluation of HyperGraphDis across all datasets for different METIS
partitions. Some partitions were not tested on a specific dataset. That is why
some cells of the table are empty.

### Cascades and Meta-graphs

US Elections dataset: The initial meta-graph of 8323 labeled cascades –
“fake”: 5,890; “not-fake”: 2433. These 8323 nodes/cascades are connected by
15,946,910 undirected edges. Since the graph is extremely dense, we applied
the disparity filter (Serrano, Boguñá, and Vespignani 2009) for $\alpha=0.5$,
which depicts the best classification results according to (Paraschiv et al.
2022). The 49% of the edges (7,763,018) survived the significance test.

MM-COVID: This dataset counts 1808 cascades – “fake”: 578; “not-fake”: 1230.
The Meta-graph consists of 1808 nodes connected by 87,948 edges.

FakeHealth datasets: In the HealthRelease the meta-graph counts 1969 cascades
– “fake”: 929; “not-fake”: 1040 – connected by 11,581 undirected edges. The
HealthStory’s meta-graph consists of 13,263 cascades – “fake”: 3574; “not-
fake”: 9689 – connected by 100,001 edges.

### Cascade features

In all datasets, we define a threshold for the number of initial retweeters
(users) that we will include in the features (to prevent out-of-memory
issues). The thresholds are US-Election: 250; MM-COVID: 50; FakeHealth: 60.
After constructing the feature matrix, we apply dimensionality reduction using
PCA. The dimensions are reduced to US-Election: 90, MM-COVID: 60; FakeHealth:
60.

User-related features: The user-related features of a given node/cascade with
$N$ users (the retweeters plus the root–user) are the following:

US-Election, HealthRelease and HealthStory: (1) The DeepWalk embedding of the
correspondent subgraph – a $N\times 128$ matrix; (2) The dates of users’
account creation; (3) The maximum value of users’ followers count; (4) The
maximum value of users’ friends count; (5) The maximum value of users’
statuses count; (6) The maximum value of users’ favorites count; (7) A Boolean
identifier whether the users’ account is verified; (8) The language of the
users’ account. (9) For the US-Election only, we have included the users’
“reaction time”, namely, the time difference between a retweet and the root-
tweet.

MM-COVID: (1) The DeepWalk embedding of the correspondent subgraph – a
$N\times 128$ matrix. (2) The dates of users’ account creation. (3) The
maximum value of users’ followers count. (4) The maximum value of users’
friends count. (5) The maximum value per user and metric across all the tweets
that she has posted: (i) listed count; (ii) impression count; (iii) reply
count; (iv) quote count; (v) like count. (6) A Boolean identifier of whether
the user’s account is verified. (7) The users’ “reaction time”.

Text-related features: Finally, the text-related features are the following:
In all datasets, we have included the sentiment (label, score) of the
root–tweet – two values, either $(2,score)$ for ’Positive’ label or
$(1,score)$ ’Negative’ label. In addition, we performed topic detection for
the US-Election dataset only, following the approach of (Paraschiv et al.
2022). For this purpose, we employ a Hierarchical Dirichlet Process (HDP) (Teh
et al. 2005; Newman et al. 2009), using the Tomotopy library (bab2min and
Fenstermacher 2021). Then, we include in the cascades’ feature vector the most
representative topic of the root–tweet based on the three topic models (the
three versions of the HDP model). For the two FakeHealth datasets, we set as
topic (per cascade) the news’ “tags”. This information is provided by the
“reviews” in the FakeHealth repository;

### Results

In this section, we delve into the results obtained from implementing our
HyperGraphDis method across various datasets and compare it against existing
state-of-the-art models. The results are summarized in Table 4 and Table 5.
Specifically, we experimented with a varying number of clusters, ranging from
20 to 5000, all of which were derived using the METIS method for graph
partitioning (see Table 4).

Turning first to the dataset related to the 2016 U.S. Presidential election,
HyperGraphDis yielded its most effective results with an accuracy of 0.867 and
an F1 score of 0.760. These performance metrics highlight not only the
method’s robustness in analyzing politically charged disinformation but also
its aptitude for handling imbalanced data, as reflected by the high F1 score.

When applied to the MM-Covid dataset, we found that the optimum performance
was achieved with 500 clusters, yielding results consistent with those for the
HealthStory dataset. This suggests that HyperGraphDis has broad applicability
across different domains and types of information, including both political
events and public health crises. The consistency in the optimal number of
clusters for these datasets may also indicate an underlying structure that is
particularly amenable to hypergraph-based analyses.

For the Health Release dataset, our results were notably different. The
optimal performance was observed with a minimal cluster size of 20, delivering
an accuracy of 0.619 and an F1 score of 0.656. It is important to note that
this dataset is inherently less dense in terms of its graph representation
compared to the other datasets under consideration. The unique nature of the
Twitter cascades in the Health Release dataset, being star graphs with a
relatively small number of users (18.5K), likely contributed to this
divergence. Despite the lower density and smaller user participation,
HyperGraphDis was still able to yield significant results, underscoring its
flexibility and adaptability to various types of data structures.

To further elucidate the efficacy of HyperGraphDis, we compiled a direct
comparison against the previously described Meta-Graph approach in Table 5.
This side-by-side evaluation was conducted across all four datasets under
investigation. In each case, HyperGraphDis displayed superior performance in
both accuracy and F1 score. Beyond these primary metrics, we also observed a
considerable reduction in both training and inference times when employing the
hypergraph approach. This is a non-trivial benefit, especially considering the
computational resources that large-scale data analysis demands.

In sum, our results robustly confirm that HyperGraphDis offers a compelling
improvement over existing methods for the identification of disinformation on
Twitter. Not only does it deliver more accurate and nuanced results, but it
also does so more efficiently, which is an essential quality for real-time or
large-scale applications. The method’s performance across disparate datasets
further signifies its versatility, making it a highly valuable tool for
combating the pervasive issue of disinformation across various contexts.

2016 US Election
---
| Method
---
| Accuracy
---
| F1
---
Score
| Train
---
Time (sec)
| Inference
---
Time (sec)
HyperGraphDis | 0.867 | 0.760 | 2094.032 | 6.503
Meta-graph |  |  |  |
(#GCNConv layers: 1) | 0.842 | 0.708 | 4946.21 | 17.21
MM-COVID
| Method
---
| Accuracy
---
| F1
---
Score
| Train
---
Time
| Inference
---
Time
HyperGraphDis | 0.895 | 0.925 | 21.464 | 0.075
Meta-graph |  |  |  |
(#GCNConv layers: 5) | 0.804 | 0.858 | 354.983 | 1.325
Health Story
| Method
---
| Accuracy
---
| F1
---
Score
| Train
---
Time
| Inference
---
Time
HyperGraphDis | 0.755 | 0.851 | 64.604 | 0.189
Meta-graph |  |  |  |
(#GCNConv layers: 2) | 0.747 | 0.85 | 191.005 | 0.473
Health Release
| Method
---
| Accuracy
---
| F1
---
Score
| Train
---
Time
| Inference
---
Time
HyperGraphDis | 0.619 | 0.656 | 9.775 | 0.051
Meta-graph |  |  |  |
(#GCNConv layers: 2) | 0.503 | 0.578 | 15.681 | 0.065

Table 5: HyperGraphDis vs Meta-graph: We report the evaluation of the Meta-
graph along with the results for the best hypergraph (smaller hypergraph in
terms of hyperedges with the larger F1 Score) which we have already shown on
Table 4. In HyperGraphDis, the classification is performed by a graph neural
network with one HypergraphConv layer (Bai, Zhang, and Torr 2021); in the
Meta-graph method, the graph neural network consists of one or multiple
GCNConv layers (Kipf and Welling 2017).

## Conclusion

The problem of disinformation on social media is a pressing issue with
substantial social, economic, and political implications. In an era where
false information can spread rapidly, undermining democratic processes and
public health initiatives, robust analytical tools are required to discern the
truth. In this paper, we have introduced a novel method, HyperGraphDis,
designed to combat the spread of disinformation by analyzing Twitter data
through the lens of a hypergraph data structure.

The advantages of using a hypergraph over traditional graph-based approaches
are manifold. First and foremost, the hypergraph structure allows for greater
scalability in terms of computational cost. Given the enormity of data on
social media platforms like Twitter, a method that can analyze large datasets
without proportionally increasing computational time is invaluable. Moreover,
our hypergraph model significantly reduces the storage footprint, addressing
yet another major challenge in big data analytics. Perhaps most importantly,
the hypergraph provides a richer representation of complex relational data,
capturing multi-faceted relationships among users that are often obscured in
simpler graph models.

To validate our method, we have constructed hypergraphs using datasets that
are both health-related and socio-politically focused, specifically including
one dataset related to the 2016 U.S. elections. The versatility of
HyperGraphDis in handling disparate types of data demonstrates its potential
for wide-ranging applications. Our tests, pitted against previous state-of-
the-art approaches, indicate a notable increase in both accuracy and F1 score.
The latter is particularly relevant when dealing with imbalanced data sets,
which are often encountered in the realm of disinformation detection.
Additionally, our method displayed improvements in computational cost and run
times, reinforcing its advantages in terms of scalability and efficiency.

In summary, HyperGraphDis not only addresses the limitations of prior methods
but also brings to the table advancements in data representation and
computational efficiency. As we continue to grapple with the pervasive issue
of disinformation, tools like HyperGraphDis will be crucial in equipping
researchers, policymakers, and the general public with the means to understand
and counteract the spread of false information.

## Acknowledgments

This work has been funded by the European Union under the projects MedDMO
(Grant Agreement no. 101083756) and INCOGNITO (Grant Agreement no. 824015).

## Ethics

This work followed the principles and guidelines on executing ethical
information research and using shared data (Kenneally and Dittrich 2012). The
suggested methodology complies with the GDPR and ePrivacy regulations. We use
existing Twitter datasets that have already been published by other studies.
We did not use or present any identifiable user information from the datasets
(e.g., Twitter user IDs). We applied text preprocessing to clean the tweets
from any information that could identify specific Twitter accounts. Hence, the
training data of the text classifier did not contain Twitter usernames.
Finally, we implemented and executed the experiments locally on our servers
without using any cloud computation services, so we did not upload any of the
datasets to the cloud.

## References

  * Ahmed, Traore, and Saad (2017) Ahmed, H.; Traore, I.; and Saad, S. 2017.  Detection of Online Fake News Using N-Gram Analysis and Machine Learning Techniques.  In Traore, I.; Woungang, I.; and Awad, A., eds., _Intelligent, Secure, and Dependable Systems in Distributed and Cloud Environments_ , 127–138. Cham: Springer International Publishing.  ISBN 978-3-319-69155-8.
  * bab2min and Fenstermacher (2021) bab2min; and Fenstermacher, D. 2021.  bab2min/tomotopy.
  * Bai, Zhang, and Torr (2021) Bai, S.; Zhang, F.; and Torr, P. 2021.  Hypergraph convolution and hypergraph attention.  _Pattern Recognition_ , 110: 107637.
  * Balcı, Sirivianos, and Blackburn (2023) Balcı, U.; Sirivianos, M.; and Blackburn, J. 2023.  A Data-driven Understanding of Left-Wing Extremists on Social Media.  arXiv:2307.06981.
  * Belova and Georgieva (2018) Belova, G.; and Georgieva, G. 2018.  Fake News as a Threat to National Security.  _International conference KNOWLEDGE-BASED ORGANIZATION_ , 24: 19–22.
  * Bisseling (2020) Bisseling, R. 2020.  _Graph matching_ , 291–358.  ISBN 9780198788348.
  * Blondel et al. (2004) Blondel, V.; Gajardo, A.; Heymans, M.; Senellart, P.; and Van Dooren, P. 2004.  A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching.  _SIAM Review_ , 46: 647–666.
  * Blondel et al. (2008) Blondel, V. D.; Guillaume, J.-L.; Lambiotte, R.; and Lefebvre, E. 2008.  Fast unfolding of communities in large networks.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2008(10): P10008.
  * Castillo, Mendoza, and Poblete (2011) Castillo, C.; Mendoza, M.; and Poblete, B. 2011.  Information Credibility on Twitter.  In _Proceedings of the 20th International Conference on World Wide Web_ , WWW ’11, 675–684. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450306324.
  * Chen et al. (2022) Chen, C.; Wang, H.; Shapiro, M.; Xiao, Y.; Wang, F.; and Shu, K. 2022.  Combating Health Misinformation in Social Media: Characterization, Detection, Intervention, and Open Issues.  arXiv:2211.05289.
  * Cheng and Chen (2020) Cheng, Y.; and Chen, Z. F. 2020.  The Influence of Presumed Fake News Influence: Examining Public Support for Corporate Corrective Response, Media Literacy Interventions, and Governmental Regulation.  _Mass Communication & Society_.
  * Chenzi (2021) Chenzi, V. 2021.  Fake news, social media and xenophobia in South Africa.  _African Identities_ , 19(4): 502–521.
  * Dai, Sun, and Wang (2020) Dai, E.; Sun, Y.; and Wang, S. 2020.  Ginger Cannot Cure Cancer: Battling Fake Health News with a Comprehensive Data Repository.  _Proceedings of the International AAAI Conference on Web and Social Media_ , 14(1): 853–862.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT_.
  * Dhanasekaran et al. (2021) Dhanasekaran, P.; Srinivasan, H.; Sree, S. S.; Devi, I. S. G.; Sankar, S.; and Vijayaraghavan, V. 2021.  SOMPS-Net: Attention Based Social Graph Framework for Early Detection of Fake Health News.  In Xu, Y.; Wang, R.; Lord, A.; Boo, Y. L.; Nayak, R.; Zhao, Y.; and Williams, G., eds., _Data Mining_ , 165–179. Singapore: Springer Singapore.  ISBN 978-981-16-8531-6.
  * Elmas, Overdorf, and Aberer (2023) Elmas, T.; Overdorf, R.; and Aberer, K. 2023.  Misleading Repurposing on Twitter.  _Proceedings of the International AAAI Conference on Web and Social Media_ , 17: 209–220.
  * Fey and Lenssen (2019) Fey, M.; and Lenssen, J. E. 2019.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_.
  * Ghosh and Shah (2018) Ghosh, S.; and Shah, C. 2018.  Towards automatic fake news classification.  _Proceedings of the Association for Information Science and Technology_ , 55: 805–807.
  * Gomaa and Fahmy (2013) Gomaa, W. H.; and Fahmy, A. A. 2013.  Article: A Survey of Text Similarity Approaches.  _International Journal of Computer Applications_ , 68(13): 13–18.  Full text available.
  * Guo et al. (2018) Guo, H.; Cao, J.; Zhang, Y.; Guo, J.; and Li, J. 2018.  Rumor Detection with Hierarchical Social Attention Network.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , CIKM ’18, 943–951. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450360142.
  * Gupta, Zhao, and Han (2012) Gupta, M.; Zhao, P.; and Han, J. 2012.  Evaluating Event Credibility on Twitter.  _Proceedings of the 12th SIAM International Conference on Data Mining, SDM 2012_ , 153–164.
  * Hanley and Durumeric (2023) Hanley, H. W. A.; and Durumeric, Z. 2023.  Sub-Standards and Mal-Practices: Misinformation’s Role in Insular, Polarized, and Toxic Interactions.  arXiv:2301.11486.
  * Hanley, Kumar, and Durumeric (2023) Hanley, H. W. A.; Kumar, D.; and Durumeric, Z. 2023.  A Golden Age: Conspiracy Theories’ Relationship with Misinformation Outlets, News Media, and the Wider Internet.  arXiv:2301.10880.
  * Jin et al. (2017) Jin, Z.; Cao, J.; Guo, H.; Zhang, Y.; and Luo, J. 2017.  Multimodal Fusion with Recurrent Neural Networks for Rumor Detection on Microblogs.  795–816.
  * Kaliyar, Goswami, and Narang (2021) Kaliyar, R.; Goswami, A.; and Narang, P. 2021.  FakeBERT: Fake news detection in social media with a BERT-based deep learning approach.  _Multimedia Tools and Application_.
  * Karypis and Kumar (1998) Karypis, G.; and Kumar, V. 1998.  A fast and high quality multilevel scheme for partitioning irregular graphs.  _SIAM Journal on scientific Computing_ , 20(1): 359–392.
  * Kenneally and Dittrich (2012) Kenneally, E.; and Dittrich, D. 2012.  The Menlo report: Ethical principles guiding information and communication technology research.  Available at SSRN 2445102.
  * Kipf and Welling (2017) Kipf, T. N.; and Welling, M. 2017.  Semi-Supervised Classification with Graph Convolutional Networks.  In _Proceedings of the 5th International Conference on Learning Representations_ , ICLR ’17.
  * Kozik et al. (2023) Kozik, R.; Pawlicka, A.; Pawlicki, M.; Choraś, M.; Mazurczyk, W.; and Cabaj, K. 2023.  A Meta-Analysis of State-of-the-Art Automated Fake News Detection Methods.  _IEEE Transactions on Computational Social Systems_ , 1–11.
  * Li et al. (2020) Li, Y.; Jiang, B.; Shu, K.; and Liu, H. 2020.  Toward A Multilingual and Multimodal Data Repository for COVID-19 Disinformation.  In _2020 IEEE International Conference on Big Data (Big Data)_ , 4325–4330.
  * Newman et al. (2009) Newman, D.; Asuncion, A.; Smyth, P.; and Welling, M. 2009.  Distributed Algorithms for Topic Models.  _Journal of Machine Learning Research_ , 10(62): 1801–1828.
  * Paraschiv et al. (2022) Paraschiv, M.; Salamanos, N.; Iordanou, C.; Laoutaris, N.; and Sirivianos, M. 2022.  A Unified Graph-Based Approach to Disinformation Detection Using Contextual and Semantic Relations.  _Proceedings of the International AAAI Conference on Web and Social Media_ , 16: 747–758.
  * Perozzi, Al-Rfou, and Skiena (2014) Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014.  DeepWalk: Online Learning of Social Representations.  In _Proceedings of the 20th International Conference on Knowledge Discovery and Data Mining_ , KDD ’14, 701–710. ACM.
  * Pratelli et al. (2023) Pratelli, M.; Petrocchi, M.; Saracco, F.; and De Nicola, R. 2023.  Swinging in the States: Does disinformation on Twitter mirror the US presidential election system?  1395–1403.
  * Rosvall and Bergstrom (2008) Rosvall, M.; and Bergstrom, C. T. 2008.  Maps of random walks on complex networks reveal community structure.  _Proceedings of the National Academy of Sciences_ , 105(4): 1118–1123.
  * Rozemberczki, Kiss, and Sarkar (2020) Rozemberczki, B.; Kiss, O.; and Sarkar, R. 2020.  Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs.  In _Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM ’20)_ , 3125–3132. ACM.
  * Safieddine (2020) Safieddine, F. 2020.  _Political and Social Impact of digital Fake news in an era of Social Media_ , 43–58.  ISBN 9781786614223.
  * Salamanos et al. (2023) Salamanos, N.; Jensen, M. J.; Iordanou, C.; and Sirivianos, M. 2023.  Did State-Sponsored Trolls Shape the 2016 US Presidential Election Discourse? Quantifying Influence on Twitter.  In Arief, B.; Monreale, A.; Sirivianos, M.; and Li, S., eds., _Security and Privacy in Social Networks and Big Data_ , 58–76. Singapore: Springer Nature Singapore.  ISBN 978-981-99-5177-2.
  * Serrano, Boguñá, and Vespignani (2009) Serrano, M. Á.; Boguñá, M.; and Vespignani, A. 2009.  Extracting the multiscale backbone of complex weighted networks.  _Proceedings of the National Academy of Sciences_ , 106(16): 6483–6488.
  * Shu et al. (2019) Shu, K.; Cui, L.; Wang, S.; Lee, D.; and Liu, H. 2019.  DEFEND: Explainable Fake News Detection.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’19, 395–405. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450362016.
  * Shu, Wang, and Liu (2019) Shu, K.; Wang, S.; and Liu, H. 2019.  Beyond News Contents: The Role of Social Context for Fake News Detection.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , WSDM ’19, 312–320. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450359405.
  * Shu et al. (2020) Shu, K.; Zhou, X.; Wang, S.; Zafarani, R.; and Liu, H. 2020.  The Role of User Profiles for Fake News Detection.  In _Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining_ , ASONAM ’19, 436–439. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450368681.
  * Tacchini et al. (2017) Tacchini, E.; Ballarin, G.; Vedova, M. L. D.; Moret, S.; and de Alfaro, L. 2017.  Some Like it Hoax: Automated Fake News Detection in Social Networks.  arXiv:1704.07506.
  * Teh et al. (2005) Teh, Y. W.; Jordan, M. I.; Beal, M. J.; and M., B. D. 2005.  Sharing clusters among related groups: Hierarchical Dirichlet processes.  NIPS’05, 1385–1392. Advances in Neural Information Processing Systems.
  * Visentin, Pizzi, and Pichierri (2019) Visentin, M.; Pizzi, G.; and Pichierri, M. 2019.  Fake News, Real Problems for Brands: The Impact of Content Truthfulness and Source Credibility on consumers’ Behavioral Intentions toward the Advertised Brands.  _Journal of Interactive Marketing_ , 45: 99–112.
  * Westerman, Spence, and Van Der Heide (2014) Westerman, D.; Spence, P. R.; and Van Der Heide, B. 2014.  Social Media as Information Source: Recency of Updates and Credibility of Information.  _J. Comp.-Med. Commun._ , 19(2): 171–183.
  * Wu and Liu (2018) Wu, L.; and Liu, H. 2018.  Tracing Fake-News Footprints: Characterizing Social Media Messages by How They Propagate.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ , WSDM ’18, 637–645. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450355810.
  * Zager and Verghese (2008) Zager, L.; and Verghese, G. 2008.  Graph similarity scoring and matching.  _Applied Mathematics Letters_ , 21: 86–94.
  * Zhang, Zhao, and Lecun (2015) Zhang, X.; Zhao, J.; and Lecun, Y. 2015.  Character-level Convolutional Networks for Text Classification.  In _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc.
  * Zhao et al. (2020) Zhao, C.; Yin, Z.; Wang, H.; Zhao, X.; and Niu, D. 2020.  A Novel Method for Graph Matching.  177–181.
  * Zhou and Zafarani (2020) Zhou, X.; and Zafarani, R. 2020.  A Survey of Fake News: Fundamental Theories, Detection Methods, and Opportunities.  _ACM Computing Surveys_ , 53.