\section{Introduction}
\label{sec:intro}
With the advancement of technology and fast dissemination of information, the issue of fake news has also escalated, e.g., the 2016 U.S. presidential election. The discredit caused by misinformation results in unrest and confused public opinions regarding essential subjects, which could endanger the stability and harmony in society\cite{MM21}.
\begin{figure}
    \centering
    \includegraphics[scale=0.42]{Figures/hetero_news_graph_og.png}
    \caption{An illustrative example of a heterogeneous information network with four types of nodes (i.e., subject, news, author and source) and three types of links (i.e., subject-news, news-author, and author-source).}

    \label{fig:hetero_news_graph_og}
\end{figure}

In the past, we require expert fact-checkers to ensure the veracity of a piece of news. However, this process is time-consuming and expensive, which is infeasible in a globalized world with millions of online social media users posting and sharing news every day. Therefore, there have been some serious studies on identifying fake news using an automated system with the help of artificial intelligence. The early efforts include the application machine learning models, such as support vector machines (SVMs), decisions trees, naive bayes and random forest, in classifying news in a data set. The results often vary depending on the domain and data set. If interested, \cite{FakeNewsDetSurvey} summarizes the performance of some traditional machine learning models on the fake news detection task.

Deep learning methods such as convolutional neural networks (CNNs) and recurrent neural networks (RNNs) are also employed in the news classification task. The general method begins by extracting the news content and converting it into a text embedding, which is then passed into a convolutional and/or recurrent networks, whose output indicates whether the news is fake. An early example of such method is using CNN for sentence classification, as shown in \cite{CNNSentenceClassification}.

More recently, there has been an extension of CNN to non-Euclidean graph-structured data known as graph neural network (GNN), pioneered by the introduction of graph convolutional network in e.g., \cite{GCN}. This generalisation allows for many real-world applications such as social networks, bio-molecular graphs, automated traffic systems and mis(dis)information detection, whose data is often large, irregularly-shaped and heterogeneous, to be represented as a graph.
Figure \ref{fig:hetero_news_graph_og} shows an example of a heterogeneous news graph where the nodes consist of news articles, creators and subjects, and the edges consist of news-creator and news-subject relationships. This allows for more contextual information to be considered in the model, which can potentially improve the quality in predicting misinformation than homogeneous graph\cite{info_cred}. There are some recent studies on employing heterogeneous networks for fake news detection, see e.g., \cite{FANG, HGAT}.

A different approach to this problem is by observing the dissemination of the news after they are released. This can be achieved by monitoring the news propagation through users who share the news with their friends/followers on social media. The principle of this method is that fake news tends to propagate faster and to a broader population compared to real news \cite{news_spread, news_prop}. However, this method requires the news to be spread to some people before it is able to make a prediction, in which the damage has been done.

To handle this issue, we propose a novel dynamic heterogeneous attention network, namely Dynamic Heterogeneous Graph Neural Network (DHGNN). DHGNN aims to detect fake news in a timely manner when an incoming piece of news is just released. Although there have been some studies on early fake news detection, see e.g., \cite{early_det}, there are not many kinds of research that considered timely fake news detection with the heterogeneity of the news graph data. For DHGNN, we first implement BERT and finetuned BERT to get a semantic representation of the news article contents and author profiles and convert it into graph data. Then, we construct the heterogeneous news-author graph to reflect contextual information and relationships. Additionally, we adapt ideas from Personalized PageRank propagation in \cite{PPNP} and dynamic propagation in \cite{SDG} to heterogeneous networks in order to reduce the time complexity of back-propagating through many nodes during training.

The structure of this paper is as follows. We introduce related works, which are the state-of-art on fake news detection, in Section \ref{sec:related}. Then, the proposed model is described in Section \ref{sec:prop_model} by going through an overview of the network architecture before focusing on specific parts of the process, such as the data extraction section and the propagation scheme. We compare the training time and prediction quality of our model with some existing state-of-the-art homogeneous and heterogeneous GNNs in Section \ref{sec:experiments}, before finally concluding our studies and findings along with some prospects in the research field in Section \ref{sec:conclusion}.

\section{Related Work}
\label{sec:related}
In this section, we present state-of-art Heterogeneous Graph Neural Networks and Dynamic Graph Neural Networks for fake news detection. Also, we examine the limitation of two different approaches.

\subsection{Heterogeneous Graph Neural Networks for fake news detection}
Heterogeneous Information Networks(HINs) are more suitable for representing complex relationships in the real world, compared
to homogeneous network which consists of only one type of node and edge. In particular, HINs are useful in fake news detection because they can express the social context that occurs through the interaction between users and news on social media, which are widely used worldwide due to the development of the mobile Internet.

To extract abundant social interconnection between entities on social networks, Wang et al. \cite{FANG} suggest graph representation learning for detecting fake news, instead of transductive learning. Unlike transductive embedding frameworks, which rely on neighbourhood information only, GraphSage\cite{hamilton2017inductive} makes use of auxiliary node attribute, as well as proximity sampling, and is implemented to represent HINs of relationship between entities on social platform. By leveraging the underlying social context, this inductive graph learning model improves the quality of representation with minimum training data.

FAKEDETECTOR\cite{zhang2020fakedetector} is designed to handle not only the credibility of the news but also the author and subjects at the same time. Explicit and latent features extracted through representation feature learning are used to model the correlation of entities in a gated diffusive unit(GDU)\cite{chung2014empirical}. GDU, which can handle multiple inputs simultaneously, can effectively form HINs of social networks.

AA-HGNN\cite{ren2020adversarial} is a heterogeneous GNN which uses a hierarchical attention mechanism for node representation learning.This model specializes in detecting fake news at publication using adversarial active learning framework. Similar to active learning, adversarial active learning employs a classifier and a selector, which work hand-in-hand in improving the quality of predicted labels. The addition of the adversarial learning concept from General Adversarial Network (GAN)\cite{goodfellow2014generative} helps with the limited training data in real-world.

Heterogeneous graph neural networks reflect more prosperous relationships between different types of nodes through HINs. However, since they are all based on a static graph, it is difficult to track the relationship between nodes over time. Thus, they are not very suitable for real-time fake news detection.

\subsection{Dynamic Graph Neural Networks for fake news detection}

A static graph has a fixed structure(nodes and edges) and parameters\cite{monical2014static}. On the other hand, a dynamic graph is a graph that reflects changes caused by time or changes in environmental elements such as temperature\cite{monical2014static}. Dynamic graphs are more suitable for modelling real-world problems that are time- sensitive or prompt to changes\cite{song2021temporally}. However, compared to static graph, it is complicated to handle, so many studies are being conducted to deal with dynamic graph.

Song et al.\cite{song2021temporally} indicates the limitations of GNNs models based on static graphs. A continuous-time dynamic GNN, called TGNF, has been proposed to overcome this limitation. It combines the the temporal graph attention neural networks(TGAT) model with a graph convolutional layer to capture the evolution pattern of news propagation in continuous time. However, as a disadvantage, the model took a relatively long execution time compared to other comparative models.

SDG is a GNN that is dynamic and homogeneous\cite{fu2021sdg}. It uses a dynamic propagation scheme because the influence of other nodes on a particular node in a k-layer GNN model is essentially a k-step random walk from that particular node. As the graph structure changes, it was proven that the push-out algorithm used to update the model converges to the stationary distribution of the updated graph. Hence, SDG can find the new dynamic propagation matrix without an expensive cost using the push-out algorithm.

Dynamic GNN models are handy for capturing real-world fluid relationship shifting between nodes over time. However, in most cases, the dynamic structure is captured based on a homogeneous graph, so there are limitations in expressing the various relationships generated by different types of nodes.

\section{Problem Statement}
\label{sec:problem}

\subsection{Terminology Definition}
We describe the the definition of Heterogeneous Information Networks(HINs) on our model as follows:

\textit{DEFINITION 1:} (Heterogeneous Information Networks(HINs)): The news-author based heterogeneous information networks(HINs) is denoted as $G = (V,E)$. $V$ represents the node-set $V = A\cup N \cup S \cup R$, which is $A$ means the set of authors, $N$ means the set of news articles, $S$ means the set of subjects and $R$ represents the set of sources. These three types of nodes are covered in detail later. $E$ denotes the relationships among author and news nodes. There are three types of relationships that are considered: the authorship relation $E_{an}$ between author and news nodes, the affiliation relation $E_{aa}$ between authors, and the subject category relation $E_{nn}$ between news articles.

\textit{DEFINITION 2:} The word graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ represents each news article and author with $\mathcal{V}$ denoting each word in the article content and $\mathcal{E}$ denoting the proximity of one word from another. More specifically, given a  positive integer $q$, if word $\mathcal{V}_1$ lies within $q$ units from $\mathcal{V}_2$, then $\mathcal{E}_{1,2}$ = 1.

Author refers to people who post news article on social media. To define author in formal method, we are described as follows:

\textit{DEFINITION 3:} (Authors): It is the set of authors and represented as $A =\{a_{1}, a_{2}, a_{3}, ... , a_{l}\}$. Each author entity is $a_{i}\in A$, which includes the profile textual.

News article is defined as text content posted by author. To define news article in formal method, we are described as follows:

\textit{DEFINITION 4:}(News Articles): It is the set of news articles and represented as $N =\{n_{1}, n_{2}, n_{3}, ... , n_{m}\}$. Each news article entity is $n_{i}\in N$, which includes news content textual. The reliability of $n_{i}$ is labelled from the label-set $Y = \{Real, Fake\}$.

Subject denotes common topic for news article. To define news article in formal method, we are described as follows:

\textit{DEFINITION 5:} (Subjects): It is the set of subjects and represented as $S =\{s_{1}, s_{2}, s_{3}, ... , s_{n}\}$. Each subject entity is $s_{i}\in S$, which contains topic area textual.

Source means the platform used to post news article.To define source in formal method, we are described as follows:

\textit{DEFINITION 6:} (Sources): It is the set of source and represented as $R =\{r_{1}, r_{2}, r_{3}, ... , r_{o}\}$. Each subject entity is $r_{i}\in R$, which contains name of source textual.

\subsection{Problem Formulation}

The problem we are interested in is to learn a classification function $f:N \rightarrow Y$ on predicting the veracity of an incoming news article $n_{i}$ in a timely manner by modelling the task as a heterogeneous graph $G = (V,E)$ classification problem. The heterogeneity of the graph takes into account contextual information such as author, subject and source for each news article and the heterogeneous relationships among the graph nodes (Figure \ref{fig:hetero_news_graph_og}), whereas the timeliness of the prediction comes from the use of dynamic propagation, which will be described in Section \ref{sec:prop}. To address the above issues, we introduce the \textbf{D}ynamic \textbf{H}eterogeneous \textbf{G}raph \textbf{N}eural \textbf{N}etwork (\textbf{DHGNN}), a novel GNN model which has the following features:
\begin{enumerate}
    \item the use of BERT and finetuned BERT to get a good semantic representation of the news article contents and author profiles.
    \item the separation of the model classifier and its propagation scheme allows a wide range of nodes to be considered with a low number of layers.
    \item dynamic propagation scheme, which is derived from a variant of the personalized pagerank algorithm, allows for timely prediction to be made.
\end{enumerate}
The new contributions we made include:
\begin{enumerate}
    \item The convergence and existence proof of two-hop and mixed (one-hop and two-hop) dynamic propagation schemes.
    \item The application of two-hop and mixed dynamic propagation schemes to bipartite and heterogeneous agnostic models.
\end{enumerate}

\section{Proposed Model and Hypothesis} \label{sec:prop_model}

\subsection{Overview: Proposed Model}

We introduce the \textbf{D}ynamic \textbf{H}eterogeneous \textbf{G}raph \textbf{N}eural \textbf{N}etwork (\textbf{DHGNN}), a novel GNN model.

In addition to the heterogeneous model, we investigate a bipartite model consisting of only the authorship relation between news and author, which, similar to the heterogeneous model, is called the \textbf{D}ynamic \textbf{B}ipartite \textbf{G}raph \textbf{N}eural \textbf{N}etwork (\textbf{DBGNN}). This is done to observe the importance of subject and source information to our model's prediction.

Figure \ref{fig:net_arch} shows the overall network architecture and process from the data extraction of the raw news articles to obtaining prediction through our models. Firstly, each incoming news article is first converted to word graphs $\mathcal{G}$ of each news content and author profile. Then, the data extraction module processes each word graph into a graph embedding vector using BERT model and personalized pagerank algorithm to take into account the word semantic and the influence of words that are close to each other in a word graph. Secondly, the news-author mapping can be obtained from the incoming news article. In addition, by considering the news subject category and author affiliation relationship among the news and author nodes, we can get the news-news and author-author mappings if two news have the same subject and two authors have the same publication source, respectively. Finally, the graph embedding vectors and the mappings are fed into either the DHGNN or DBGNN model, which predicts whether the input news is fake. Each step in the network architecture will be discussed in detail in the subsequent sections.

\begin{figure*}[t!]
    \centering
    \includegraphics[scale=0.58]{Figures/Network_Architecture.png}
    \caption{The overall architecture of the proposed method.}
    \label{fig:net_arch}
\end{figure*}

\subsection{Detailed Model Architecture}
\subsubsection{Data Extraction Method} \label{sec:data_extract}
As the information provided in the data sets and their structures vary, we need to preprocess them to extract some important information that is relevant to our proposed model. Figure \ref{fig:data_extract} shows the data extraction module.
There are three main steps in extracting the data: (i) selecting and cleaning the data, (ii) evaluating the word semantics using BERT \cite{BERT}, and (iii) converting the result into a graph data input for the model.

\subsubsection*{Selecting and Cleaning the data}
In general, the data sets used in our experiments are quite clean. However, as they are not designed specific for our purpose, we need to firstly select the relevant information. More specifically, the following fields are retrieved (if exist):
\begin{enumerate}
    \setlength\itemsep{0em}
    \item News: \textsc{id}, content, author(s), subject(s), label.
    \item Author: \textsc{id}, name, profile, source/affiliation, label.
    \item Source: \textsc{id}, name.
    \item Subject: \textsc{id}, name.
\end{enumerate}
\begin{figure*}[t!]
    \centering
    \includegraphics[scale=0.35]{Figures/Data_Extraction_Module.png}
    \caption{Data extraction module}
    \label{fig:data_extract}
\end{figure*}
The following rules and conditions are applied to each data set:
\begin{itemize}
    \setlength\itemsep{0em}
    \item The news content and author profile must be in English. Texts in other languages are removed from the data set.
    \item If the data does not come with an \textsc{id}, we will assign a unique positive integer as \textsc{id}.
    \item If there is no news content or label, the data point is filtered out.
    \item If there is/are no subject(s), the field is set to empty.
    \item If author profile is not given, the field is set to the author name.
    \item If there is no author or source, author name and profile are set to be unknown.
    \item If there is no author but there is a source, we set the author to be the source.
    \item The author label is computed as the average of the authored news labels.
    \item Non-binary news classification is converted to binary classification (real/fake).
\item Punctuation is removed from news content and author profile.
\end{itemize}

\subsubsection*{Finetuning BERT}
BERT (Bidirectional Encoder Representation from Transformers) is a language representation model which uses the idea from Transformer \cite{transformer} and achieves state-of-the-art results on various NLP tasks, including text classification. The original source code by Google Research team is made available \href{https://github.com/google-research/bert}{here}, which is adapted by \href{https://huggingface.co/}{Hugging Face} in their \href{https://huggingface.co/transformers/index.html}{Transformers library} for PyTorch, TensorFlow, and Jax.

For our purpose, we use the pretrained base BERT model and tokenizer for uncased English texts from Hugging Face Transformers. The model consists of 12 layers, 768 hidden channels and 12-headed attention mechanism. However, the maximum input sequence length is 512, which is too small, considering some news articles contain thousands of words. Furthermore, the pretrained model is trained on Wikipedia pages, which is not specific to our problem. Hence, we want to finetune the pretrained model with our data sets.
For the finetuning process of the pretrained BERT model, in general, we train the pretrained BERT model and pool the result through a final linear (dense) layer, which yields the final output prediction. The idea follows the suggestion given by BERT's first author on this \href{https://github.com/google-research/bert/issues/27}{Github issue}.

\subsubsection*{Getting BERT word token embedding}
The process of obtaining tokenized sequence embedding with a BERT model is outlined as follows:
\begin{enumerate}
    \setlength\itemsep{0em}
    \item Each cleaned textual description, i.e., news content and author profile, is tokenized using the base BERT model tokenizer. If the resulting tokenized sequence length is longer than 512, it is split into tokenized sequences of length 512. If the sequence is shorter than 512, it is padded with zeros. Note that we need to ensure that each split tokenized sequence starts and ends with tokens ('[CLS]', 101) and ('[SEP]', 102), respectively.

    \item The token-index mapping is also saved so that we can construct each word embedding for our feature matrices. This is due to how each word is tokenized.
    Note that some words such as 'gruesome' and 'closeby' are split into multiple tokens. Detailed information on various BERT tokenizers is available \href{https://huggingface.co/transformers/tokenizer_summary.html}{here}.

    \item The pretrained BERT model is loaded from Transformers and set to evaluation mode. Alternatively, we can finetune the pretrained BERT model as described in the previous section.
    \item There are different methods in computing the final tokenized sequence embedding using BERT. Comparisons of some of these methods are reported in \cite[Table 7]{BERT}. In our experiment, the embedding vector of eachtokenized sequence is computed by adding the output of the last four hidden layers of the pretrained BERT model.
\end{enumerate}
At the end of the last step, we have an embedding matrix along with a token-index mapping for each tokenized sequence, which can be converted into a feature matrix for each sequence. Note that we apply this process to both news content and author profile.

There are of course other methods we can use to get text embedding such as Word2Vec \cite{Word2Vec}, GloVe \cite{GloVe} and TF-IDF \cite{TFIDF}. However, they are context independent, which means that each polysemous word is represented by the same vector. For example, the word 'fly', regardless whether it is a noun or verb will be represented by the same vector. As context is important in the news classification task, we choose BERT to generate each word embedding in a text.

\subsubsection*{Conversion to graph data}
To use our data in a GNN model, we need to convert it into graph input data, as described in Section \ref{sec:problem}. This includes an adjacency matrix and a feature matrix for each word graph $\mathcal{G}$, mappings among authors and news articles to represent the edges in graph $G$, and a list of labels corresponding to each word graph.\\
The construction of the feature matrix can be done in the following steps:
\begin{enumerate}
    \setlength\itemsep{0em}
    \item Get the tokenized sequence embedding matrix and token-index mapping of each sequence.
    \item If each word in the sequence is represented by one token, we take the token embedding vector as the word embedding vector. However, if each word is represented by multiple tokens, we take the average of the token embedding vectors as the word embedding vector.
    \item The feature matrix of each sequence is obtained by concatenating the word embedding vectors.
\end{enumerate}
The construction of the adjacency matrix can be done in the following steps:
\begin{enumerate}
    \setlength\itemsep{0em}
    \item As outlined in Section \ref{sec:problem}, the edge $\epsilon$ denotes the proximity of words in the graph, represented by the window size $q$. The value used in our experiments is $q = 3$.
    \item Since each word in a sequence is sequentially process for the feature matrix, the adjacency matrix is a sparse matrix with up to four diagonals with all ones. If the sequence is empty, an empty matrix is returned.
\end{enumerate}
There are three different mappings on the heterogeneous graph $G$:
\begin{itemize}
    \setlength\itemsep{0em}
    \item author-author: an edge exists between two authors if their news articles are published on the same media channel.
    \item news-news: an edge exists between two news articles if they are on at least one same topic.
    \item author-news: an edge exists between author and news article if the news is written by the author.
\end{itemize}
The feature and adjacency matrices, along with the labels and mappings among news and authors, are then saved into a file, to be used in the model training and evaluation.
Note that in this experiment, we have multiple instances of the same word in the word graph. This is due to the fact that many English words are polysemous and using BERT, we are able to differentiate the word semantics. Hence, rather than pooling the result, we preserve each word embedding for our classification task.

\subsubsection{Model Implementation}

\begin{figure*}
    \centering
    \includegraphics[scale=0.6]{Figures/DHGNN_and_DBGNN.png}
    \caption{Overview of DHGNN and DBGNN}
    \label{fig:DHGNN_DBGNN}
\end{figure*}

Figure \ref{fig:DHGNN_DBGNN} shows the architecture of DBGNN and DHGNN. The model consists of a classifier and a propagation method, which are implemented separately. This is due to the application of dynamic propagation to replace the usual message passing in GNN. The outline of the network is shown in the following sections.

\subsubsection*{Getting the news-author graph data}
To construct the news-author graph, we firstly combine the word embedding vectors in each sequence. The idea is to compute the influence of each neighbouring word in the sequence using a personalized pagerank algorithm. Then, the aggregate embedding vector of each text is just the weighted average of the neighbouring words' embedding vectors. This weighted average serves as the feature vector of the sequence and it is applied to every news content and author profile. The next step is to construct the news-author graph. The feature matrix is obtained by appending the feature vectors we obtained in the previous step. The adjacency matrix is constructed using the news-author mapping that we get from the data extraction phase whereas the news and author labels can be used as they are.

\subsubsection*{Agnostic Model/Classifier $f_\theta(X)$}
The classifier used is a vanilla Graph Convolutional Network (GCN) without the usual message-passing propagation, which was initially implemented in \cite{PPNP}. The timeliness of the model is achieved by replacing the usual message passing propagation mechanism with dynamic propagation, which will be described in detail in Section \ref{sec:prop}.

\subsubsection*{$K$-Fold Cross Validation}
The $K$-Fold Cross Validation is a common method to robustly test the prediction quality of a model. The data set is divided into $K$ even (or almost even) partitions, and then in each iteration, we run the model with $K-1$ partitions for training and 1 partition for validation. At the end, we take an average of the validation results as the final result. The cross validation scheme can be combined with a final testing phase by only dividing the training and validation data into $K$ partitions, while leaving some data points for testing after the cross validation is finished.

\subsubsection{Dynamic Propagation} \label{sec:prop}
In \cite{SDG}, the authors utilize a dynamic propagation scheme to replace the usual message passing propagation. This not only reduces the training time, but also allows for larger neighborhoods to be considered in their model.
Following the idea in the aforementioned paper, the DHGNN model utilizes the 2-hop dynamic propagation whereas the DBGNN model utilizes the mixed dynamic propagation, which are both a variation of the original dynamic propagation method in \cite{SDG}, applied on a heterogeneous graph.

\subsubsection*{2-Hop Dynamic Propagation}
To provide a timely prediction, we aim to apply dynamic propagation scheme, proposed in \cite{SDG}, on graph $G = (V,E)$. This scheme allows the model to recompute the propagation matrix when there is new information without having to retrain the model.
In more detail, each row of the dynamic propagation matrix $P$, or $P(i,:)$, is a stationary distribution of a random walk with restart (RWR) from node $V_i$, which can be expressed as follows. Let $V_i$ be the seed node. Then,
\begin{align} \label{eq:P_def}
   P(i,:)^\top \,=\, \alpha \, M P(i,:)^\top + (1-\alpha) \,\mathbf{e}_i,
\end{align}
where $\alpha \in [0,1)$ is the probability of moving through an outgoing edge from the current node, and $1-\alpha$ the restart probability, i.e., the probability of jumping back to the seed node. In the equation, $M = A D^{-1}$ is a $n \times n$ column stochastic matrix, which is obtained by multiplying the $n \times n$ adjacency matrix $A$ with the inverse of the $n \times n$ diagonal matrix $D$ whose entries $d_{i}$ are the degrees of node $V_i$ for all $i$. The vector $\mathbf{e}_i$ denotes the standard basis vector where all its components are zero, except the $i$-th element, which is one.

When there is a change in the graph topology, i.e., insert/delete edge and/or new nodes, each row of the dynamic propagation matrix $P$ needs to be updated. The exact computation of RWR, and consequently $P$, is expensive, however, there are fast and scalable methods which provide good approximation. One such methods uses cumulative power iteration (CPI) \cite{TPA} by pushing out the previous probability distribution score from the changed part to the residual part of the graph, as outlined in \cite{SDG, OSP}. Mathematically, the process can be written as
\begin{align*}
    P(i,:)^\top_{\mathrm{pushout}} &\,=\, \alpha (M' - M) P(i,:)^\top, \hspace{1em} \text{and}\\
    P(i,:)^\top_{\mathrm{new}} &\,=\,  P(i,:)^\top + \sum_{k=0}^\infty \, (\alpha M')^k P(i,:)^\top_{\mathrm{pushout}},
\end{align*}
where $M' = A' D'^{-1}$, $A'$ is the new adjacency matrix and $D'$ is the new diagonal degree matrix after the graph is updated. Note that the convergence and exactness of the above process have been studied in \cite[Section 3.1]{OSP}, which shows that the method does converge and result in the new probability distribution score as $k \rightarrow \infty$.

However, due to the heterogeneous nature of the problem, the unipartite dynamic propagation in the aforementioned paper cannot be applied directly to our bipartite news-author network, and consequently the heterogeneous network. To resolve this issue on the bipartite network, instead of using 1-hop random walk, we apply 2-hop random walk. Thus, $M_2 = M^2 = (AD^{-1})^2$. Since $M$ is a stochastic matrix and the fact that a product of stochastic matrices is also a stochastic matrix, $M_2$ is also a stochastic matrix.

To prove the convergence and exactness of the 2-hop dynamic propagation, we will follow the proof in \cite{OSP} and replace $M$ with $M_2$ as shown in the following theorem.

\begin{theorem}[Convergence and Exactness of 2-Hop Dynamic Propagation Scheme] \label{thm:two_hop}
\hspace{0.5em} Let $G = (V,E)$ be the bipartite news-author graph. Suppose that $G$ is updated to $G' = (V',E')$ such that the 2-hop dynamic propagation scheme is given by
\begin{align*}
    P(i,:)^\top_{\mathrm{pushout}} &\,=\, \alpha (M_2' - M_2) P(i,:)^\top, \hspace{1em} \text{and}\\
    P(i,:)^\top_{\mathrm{new}} &\,=\,  P(i,:)^\top + \sum_{k=0}^\infty \, (\alpha M_2')^k P(i,:)^\top_{\mathrm{pushout}},
\end{align*}
where $P(i,:)$ is the $i$-th row of the dynamic propagation matrix $P$, $\alpha \in [0,1)$ is the probability of jumping to the outgoing edge of the current node and $M_2 = (AD^{-1})^2$.
Then, $\sum_{k=0}^\infty \, (\alpha M_2')^k P(i,:)^\top_{\mathrm{pushout}}$ converges to a constant value as $k \rightarrow \infty$ and $P_{\mathrm{new}}$ is the new propagation matrix of the updated graph $G'$ whose rows are denoted as $P(i,:)_{\mathrm{new}}$.
\end{theorem}

\begin{proof}
We will begin by proving the convergence of the summation term. By expanding the pushout term, we have
\begin{align} \label{eq:conv_proof}
    &\sum_{k=0}^\infty \, (\alpha M_2')^k P(i,:)^\top_{\mathrm{pushout}}
    \,=\, \sum_{k=0}^\infty \, (\alpha M_2')^k \alpha (M_2' - M_2) P(i,:)^\top \\
    &\,=\,
    \sum_{k=0}^\infty \, (\alpha M_2')^{k+1} P(i,:)^\top - \big(\alpha^{k+1} (M_2')^k M_2 \big) \, P(i,:)^\top. \nonumber
\end{align}
Since $M_2$ and $M_2'$ are stochastic matrices, we have $\|M_2\|_1 = 1$ and $\|M_2'\|_1 = 1$. Moreover, $\|P(i,:)\|_1 = 1$ as $P(i,:)$ is a stationary distribution of $V_i$. Thus, the summation terms converge since $\alpha \rightarrow 0$ as $k \rightarrow \infty$.

We will exhaustively prove that $P(i,:)_{\mathrm{new}}$ is indeed the $i$-th row of the new propagation matrix $P_{\mathrm{new}}$. Firstly, we check the case when there is no update in the graph, which implies that $M_2 = M_2'$ and subsequently, $P(i,:)^\top_{\mathrm{pushout}} = \mathbf{0}$. It is clear that in this case, $P(i,:)_{\mathrm{new}}^\top = P(i,:)^\top$. When there is an update in the graph, we begin by expanding the pushout summation term as shown in \eqref{eq:conv_proof}. Then, rewriting vector $P(i,:)^\top$ as $\sum_{k' = 0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}}$, we have
\begin{align*}
    &\sum_{k=0}^\infty \, (\alpha M_2')^k P(i,:)^\top_{\mathrm{pushout}} \\
    & \,=\, \sum_{k=0}^\infty \bigg( (\alpha M_2')^k \alpha (M_2' - M_2) \sum_{k' = 0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}} \bigg) \\
    &\,=\,
    \sum_{k=0}^\infty \bigg( (\alpha M_2')^{k+1} \sum_{k'=0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}} \\
    & \,\,\,\,\,\,\, - (\alpha M_2')^{k} \sum_{k'=0}^\infty (\alpha M_2)^{k' + 1} P(i,:)^\top_{\mathrm{old}} \bigg).
\end{align*}
Since the last summation term in the sum over $k$ can be rewritten as
\begin{align*}
    \sum_{k'=0}^\infty (\alpha M_2)^{k' + 1} P(i,:)^\top_{\mathrm{old}}
    &\,=\,
    -P(i,:)^\top_{\mathrm{old}} +\sum_{k'=0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}},
\end{align*}
and the first term (including the outer sum) can be rewritten as
\begin{align*}
    & \sum_{k=0}^\infty (\alpha M_2')^{k+1} \sum_{k'=0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}} \\
    &\,=\,
    -\sum_{k'=0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}} + \sum_{k=0}^\infty (\alpha M_2')^{k} \sum_{k'=0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}},
\end{align*}
we have
\begin{align*}
    & \sum_{k=0}^\infty \, (\alpha M_2')^k P(i,:)^\top_{\mathrm{pushout}} \\
    &\,=\,
    -\sum_{k'=0}^\infty (\alpha M_2)^{k'} P(i,:)^\top_{\mathrm{old}} + \sum_{k=0}^\infty (\alpha M_2')^{k} P(i,:)^\top_{\mathrm{old}} \\
    &\,=\,
    -P(i,:)^\top + \sum_{k=0}^\infty (\alpha M_2')^{k} P(i,:)^\top_{\mathrm{old}}.
\end{align*}
Hence, substituting the above equation to the formula for $P(i,:)^\top_{\mathrm{new}}$ yields
\begin{align*}
    P(i,:)^\top_{\mathrm{new}}
    &\,=\,
    P(i,:)^\top + \sum_{k=0}^\infty \, (\alpha M_2')^k P(i,:)^\top_{\mathrm{pushout}} \\
    &\,=\,
    \sum_{k=0}^\infty (\alpha M_2')^{k} P(i,:)^\top_{\mathrm{old}},
\end{align*}
which is exactly the stationary distribution of $P(i,:)$ using CPI.
\end{proof}

\subsubsection*{Mixed Dynamic Propagation}
In DHGNN, we take into account three different mappings among news and author entities: news-author, news-news and author-author mappings. Note that the news-author mapping can be independently represented by the 2-hop dynamic propagation derived in the previous section, whereas the homogeneous news-news and author-author mappings can be represented by the original dynamic propagation in \cite{SDG}. Thus, the mixed dynamic propagation is a weighted average of the two-hop dynamic propagation and the original dynamic propagation. To be more precise, given the two-hop propagation matrix $P_{an}$ and the dynamic propagation matrices $P_{nn}$ and $P_{aa}$, the mixed propagation matrix $P$ is defined as
\begin{align*}
    P &\,=\, \beta_0 P_{an} + \beta_1 P_{nn} + \beta_2 P_{aa},
\end{align*}
where $\beta_0 + \beta_1 + \beta_2 = 1$, and $P_{an}$, $P_{nn}$ and $P_{aa}$ represent the propagation matrices of author-news, news-news and author-author relationships, respectively.

Similar to the 2-hop dynamic propagation scheme, the convergence and exactness of the mixed dynamic propagation scheme can be proved by observing that the weighted sum of stochastic matrices is also a stochastic matrix. Hence, the mixed dynamic propagation matrix is a stochastic matrix. Then, the proof of Theorem~\ref{thm:two_hop} can be applied to the mixed dynamic propagation scheme by replacing the two-hop propagation matrix with the mixed propagation matrix.

\section{Experiments} \label{sec:experiments}
In this section, we will analyze the performance of our model in comparison to existing state-of-the-art agnostic and task-dependent homogeneous and heterogeneous models.
To compare our models and others, we conducted a grid search for the most optimal hyperparameters for each model listed in Section \ref{sec:models} with 4-fold cross validation.
The metrics observed include the accuracy, precision, recall, AUC and F1 scores of the model on the validation set, and the training time with early stopping. The training is only stopped when the training loss does not improve within 10 consecutive epochs. Note that the quoted training time includes the propagation scheme of the model.

All experiments are conducted using a shared computational cluster called \href{https://doi.org/10.26190/669x-a286}{Katana} supported by Research Technology Services at UNSW Sydney with up to six Tesla V100-SXM2-32GB GPUs and eight CPUs run on CentOS Linux 7.
\subsection{Data Sets}
For our research on the timely fake news detection with bipartite and heterogeneous news-author networks, there are two suitable data sets that will be used: LIAR \eqref{dataset:liar} and FakeNewsNet \eqref{dataset:fakenewsnet}.

\subsubsection{LIAR} \label{dataset:liar}
\emph{LIAR} contains 12,800 manually labelled short statements from various subjects, sourced from PolitiFact over a 10-year-period from 2007 to 2016\cite{wang2017liar}. It groups the data into training, testing and validation, with each row containing the following information:
\begin{center}
    \{id, statement, label, subject(s), speaker name, speaker profile (job title, US base state,\\ party affiliation), context, statement setting, speaker's total historical score\}.
\end{center}
LIAR is publicly available for fake news detection and can access via this \href{https://www.cs.ucsb.edu/~william/data/liar_dataset.zip}{link}.\\

\subsubsection{FakeNewsNet} \label{dataset:fakenewsnet}
\emph{FakeNewsNet} is a tool which enables its users to collect, analyse and visualize fake news detection and dissemination on social media, namely Twitter. Combining the news from PolitiFact and GossipCop, along with the corresponding tweets and retweets related to the news, the data collected are labelled by experts and journalists. The data is separated based on the source, i.e., Politifact or GossipCop, and whether the label is fake or real.

The repository is publicly available for fake news detection, fake news propagation and can be accessed \href{https://github.com/KaiDMML/FakeNewsNet}{here}. \\

\begin{table}[t]
  \caption{Statistics of the LIAR and FakeNewsNet Datasets.}
  \small\centering
  \begin{tabular}{lc|c|c|c}
    \toprule[.2em]
    & {} & \multicolumn{1}{c|}{\bfseries Liar} & \multicolumn{1}{c|}{\bfseries Gossipcop} &\multicolumn{1}{c}{\bfseries Politifact} \\
    \midrule[.1em]
    \multirow{5}{0.77cm}{\#entity}
      & {news} & 12,836 & 17,543 & 656  \\
    \cmidrule(lr){2-5}
      & {author} & 3,318 & 3,848 & 315 \\
    \cmidrule(lr){2-5}
      & {subject} & 144 & 0 & 0 \\
      \cmidrule(lr){2-5}
      & {source} & 5,103 & 1,544 & 106  \\
    \midrule[0.1em]

    \multirow{4}{0.8cm}{\#link}
      & {news-author} & 12,836 & 17,542 & 656 \\
    \cmidrule(lr){2-5}
      & {news-news} & 66,288 & N/A & N/A \\
    \cmidrule(lr){2-5}
      & {author-author} & 18,228 & 86,721 & 2,819 \\

    \bottomrule[.2em]
    \end{tabular}
    \label{tab:dataset}
\end{table}

\subsection{Models} \label{sec:models}
\begin{enumerate}
    \item DBGNN

    Our dynamic bipartite model without BERT finetuning in the data extraction module.

    \item DBGNN$_{finetuning}$

    Our dynamic bipartite model with BERT finetuning in the data extraction module.

    \item DHGNN

    Our dynamic heterogeneous model without BERT finetuning in the data extraction module.

    \item DHGNN$_{finetuning}$

    Our dynamic heterogeneous model with BERT finetuning in the data extraction module.

    \item GCN

    2-layer Vanilla GCN from \cite{GCN} for a homogeneous graph-level news classification problem with Word2Vec to get embedding for each text.

    \item GAT

    2-layer GAT from \cite{GAT} for a homogeneous graph-level news classification problem with Word2Vec to get embedding for each text.

    \item HAN

    HAN model from \cite{wang2019heterogeneous} for heterogeneous graph-level news classification problem with author and subject information and TfIdfVectorizer for data extraction.

    \item HGAT

    HGAT model from \cite{HGAT} for a heterogeneous graph-level news classification problem with author and subject information and TfIdfVectorizer for data extraction.

\end{enumerate}

\subsection{Results}

Table~\ref{tab:result_liar}, ~\ref{tab:result_Gossipcop}, and~\ref{tab:result_Politifact} summary the training time and prediction quality of different models in the experiments on each dataset.

\subsubsection{Effectiveness of BERT Finetuning}
In this section, we will compare the quality of the model which uses pretrained BERT model with the model which uses finetuned BERT model in the data extraction phase. Note that the details about pretrained and finetuned BERT models are discussed in Section \ref{sec:data_extract}.

The 5th and 6th columns and the 7th and 8th columns of each table shows that in general, the finetuning of BERT model results in lower training time. The lower training time is caused by an earlier convergence in the models with BERT finetuning as the resulting feature matrices from the data extraction method were obtained from finetuning BERT.However, in terms of prediction quality, based on the five metrics, i.e., accuracy, precision, recall, AUC and F1 score, the finetuning of BERT model shows similar or lower performance. Due to the millions of parameters in the BERT base model and a significantly smaller benchmarking data sets, BERT finetuning results in overfitting, which leads to lower prediction quality in comparison to the models using a pretrained BERT model.

\subsubsection{Incorporation of Contextual Information in the Models}
In this section, we will discuss the influence of contextual information such as news subject and source to the quality of the models, which can be inferred by comparing the same variant of DBGNN and DHGNN models.

Table~\ref{tab:result_liar}, ~\ref{tab:result_Gossipcop}, and~\ref{tab:result_Politifact} shows that the training in the DHGNN model converges slower than DHGNN. This is due to the heavier sparse matrix computations in the dynamic propagation matrix calculation. This is expected as the number of matrix multiplications is tripled in each step.
On the other hand, we also observe that the predictions made by DHGNN and DBGNN are different depending on the dataset. In LIAR and Gossipcop dataset, DBGNN makes predictions with slightly higher accuracy than DHGNN. However, in case of Politifact dataset, the result is different from the previous result. A possible explanation of this occurrence is the insufficient cleaning and filtering of the contextual information in the data sets. For example, the source column in the LIAR data set is often descriptive and not categorical, and there is not many news in the Gossipcop data set which contains subject information. Therefore, the use of contextual information in our models is not consistent. Further studies are needed to confirm the effect of adding contextual information into the models.

\subsubsection{Comparison on the Training Time of Different Models}
It is clear that our bipartite models have the shortest training time for LIAR, Gossipcop and Politifact data sets. Our heterogeneous model is the second fastest model. Compared to the bipartite model, DHGNN took 23\%, 27\% and 39\% more training time for LIAR, Gossipcop and Politifact dataset, respectively. HGAT trained for more than twice the training duration of the heterogeneous models, followed by HAN models with around 234 seconds for LIAR, 783 seconds for Gossipcop, and 152 seconds for Politifact data sets. Finally, the homogeneous models, namely GCN and GAT, were significantly slower with around 300 seconds, over 1200 seconds, and over 200 seconds training time for LIAR, Gossipcop and Politifact dataset, respectively.

\subsubsection{Comparison on the Prediction Quality of Different Models}
For LIAR data set in Table\ref{tab:result_liar}, most of the models in the experiment produced similar results, with around 72.3\% accuracy and precision, and nearly 100\% recall. This is due to the small size of the news content and data set. HGAT and HAN, however, performed slightly worse than the other models with 70.17\% and 71.94\% accuracy.
On the other hand, HGAT performed best when predicting the Gossipcop data set, with 82.64\% accuracy, 82.18\% precision and 97.42\% recall. This result is considerably higher than other models in the experiment, including our bipartite and heterogeneous models. Our models without BERT finetuning perform second best with approximately 80\% accuracy, 79\% precision, and almost 100\% recall. GCN and GAT produce similar results with around 76\% accuracy and precision, and 100\% recall. HAN, a heterogeneous model, showed better accuracy than GAT and GCN with an accuracy of 76.58\%.

As DBGNN and DHGNN use GCN as classifier in this experiment, we can see that by using the dynamic propagation scheme, we are able to reduce the training time of a vanilla GCN significantly. In fact, for LIAR data set, the training time of DBGNN and DHGNN are $\frac{1}{20}$ and $\frac{3}{50}$ of GCN training time, respectively. Similar observations can be made when trained with the FakeNewsNet data set.
Moreover, when compared with vanilla GCN, we are able to retain the prediction quality, as evident by our results in Table~\ref{tab:result_liar}, \ref{tab:result_Gossipcop} and \ref{tab:result_Politifact}.

We are aware that when trained and tested with the Gossipcop and Politifact data set, HGAT performs best in regards to both training time and prediction quality. We suspected that the results of DBGNN and DHGNN were worse than our expectation due to some overfitting as we use GCN as our classifier, although further investigation is needed to ascertain the actual cause.

\begin{table*}[t]
  \caption{Training Time and Prediction Quality of Different models on \textit{LIAR} Dataset.}
  \normalsize\centering
  \begin{tabular}{c|cccccccc}

    \toprule[.2em]

    {\bfseries Metric }& {GAT} & {GCN} & {HAN} & {HGAT} &{DBGNN} &{DBGNN$_{f}$} &{DHGNN} &{DHGNN$_{f}$}  \\
    \midrule[.1em]

      {Accuracy}

      & 0.7226 & 0.7228 & 0.7194 & 0.7017 & 0.7227 & 0.7228 & 0.7226 & 0.7227 \\

    \cmidrule(lr){2-9}
      {Precision}

      & 0.7226 & 0.7228 & 0.7192 & 0.7120 & 0.7227 & 0.7232 & 0.7234 & 0.7230 \\
    \cmidrule(lr){2-9}
      {Recall}

      & 1.0000 & 0.9998 & 0.9997 & 0.9847 & 0.9984 & 0.9972 & 0.9969 & 0.9978 \\
      \cmidrule(lr){2-9}
      {F1-score}

      & 0.8390 & 0.8390 & 0.8198 & 0.8147 & 0.8386 & 0.8390 & 0.8383 & 0.8393 \\
      \cmidrule(lr){2-9}
      {Time(s)}

      & $318.75\pm24.56$ & $282.09\pm52.87$  & $183.77\pm54.13$  & $41.28\pm10.28$  & $12.93\pm5.17$  & $12.28\pm4.56$ & $15.92 \pm4.60$ & $15.48\pm4.32$ \\

    \bottomrule[.2em]
  \end{tabular}
  \label{tab:result_liar}
\end{table*}

\begin{table*}[t]
  \caption{Training Time and Prediction Quality of Different models on \textit{Gossipcop} Dataset.}
  \normalsize\centering
  \begin{tabular}{c|cccccccc}

    \toprule[.2em]

    {\bfseries Metric }& {GAT} & {GCN} & {HAN} & {HGAT} &{DBGNN} &{DBGNN$_{f}$}&{DHGNN}&{DHGNN$_{f}$} \\
    \midrule[.1em]

      {Accuracy}
      & 0.7608 & 0.7549 & 0.7658 & 0.8264 & 0.7985 & 0.7875 & 0.7978 & 0.7874\\
    \cmidrule(lr){2-9}
      {Precision}
      & 0.7608 & 0.7549 & 0.7662 & 0.8218 & 0.7945 & 0.7876 & 0.7990 & 0.7880\\
    \cmidrule(lr){2-9}
      {Recall}
      & 1.0000 & 1.0000 & 0.9889 & 0.9742 & 0.9962 & 0.9964 & 0.9967 & 0.9986\\
      \cmidrule(lr){2-9}
      {F1-score}
      & 0.8550 & 0.8550 & 0.8613 & 0.8932 & 0.8702& 0.8705 & 0.8725 & 0.8712 \\
      \cmidrule(lr){2-9}
      {Time(s)}
      & $1223.19\pm100.05$ & $1098.37\pm158.08$ & $783.67\pm4.56$ & $68.39\pm24.51$ & $21.67\pm5.90$ & $19.54\pm4.56$ & $27.58 \pm5.16$ & $23.71\pm4.20$ \\

    \bottomrule[.2em]
  \end{tabular}
  \label{tab:result_Gossipcop}
\end{table*}

\begin{table*}[t]
  \caption{Training Time and Prediction Quality of Different models on \textit{Politifact} Dataset.}
  \normalsize\centering
  \begin{tabular}{c|cccccccc}

    \toprule[.2em]

    {\bfseries Metric }& {GAT} & {GCN} & {HAN} & {HGAT} &{DBGNN} &{DBGNN$_{f}$}&{DHGNN}&{DHGNN$_{f}$} \\
    \midrule[.1em]

      {Accuracy}
      & 0.7405 & 0.7405 & 0.7481 & 0.7710 & 0.7557 & 0.7557 & 0.7634 & 0.7634\\
    \cmidrule(lr){2-9}
      {Precision}
      & 0.7833 & 0.7881 & 0.7949 & 0.8051 & 0.7966 & 0.8017 & 0.8087 & 0.8034\\
    \cmidrule(lr){2-9}
      {Recall}
      & 0.9216 & 0.9118 & 0.9118 & 0.9314 & 0.9216 & 0.9118 & 0.9118 & 0.9216\\
      \cmidrule(lr){2-9}
      {F1-score}
      & 0.8500 & 0.8551 & 0.8551 & 0.8649 & 0.8594 & 0.8551 & 0.8649 & 0.8651\\
      \cmidrule(lr){2-9}
      {Time(s)}
      & $201.63\pm9.70$ & $194.88\pm11.05$ & $152.89\pm4.56$ & $19.41\pm4.23$ & $5.99\pm1.40$ & $5.04\pm1.51$ & $8.35\pm2.02$ & $7.90\pm1.34$ \\

    \bottomrule[.2em]
  \end{tabular}
  \label{tab:result_Politifact}
\end{table*}

\section{Conclusion and Future Outlook} \label{sec:conclusion}
The field of deep learning has brought tremendous contribution to the society with applications in the computer vision, natural language processing, and many others. The emerging branch of GNN has slowly shown some promising results in tackling various problems such as automating traffic systems, analysing social networks, and discerning mis(dis)information in the social media.

\bibliographystyle{ACM-Reference-Format}


\section{Results}\label{PRELIM}

The de Moivre--Laplace theorem for the symmetric binomial distribution
can be written as the following bound on the binomial coefficients:
$$
\binom{n}{k}=\frac{2^n}{\sqrt{\pi n/2}}\exp\left(-\frac{2(k-n/2)^2}{n}
\right)(1+O(1/\sqrt{n})).
$$
The bound holds for $n\to\infty$ and $|k-n/2|=O(\sqrt{n})$,
that is, in the so-called central region.

The fact that the bound is asymptotic and valid only in the
central region makes it difficult to apply in certain cases
(some of them are considered in this paper).
There are known non-asymptotic bounds that hold for wider ranges of parameters.
For example,
\begin{align*}
\left(\frac{n}{k}\right)^k
&\leq \binom{n}{k}
\leq\left(\frac{en}{k}\right)^k,\quad
1\leq k\leq n,\\
\intertext{or, denoting $H_2(x)=-x\log_2 x - (1-x)\log_2(1-x)$,}
\frac{2^{n H_2(k/n)}}{\sqrt{8 k (1-k/n)}}
&\leq \binom{n}{k}
\leq \frac{2^{n H_2(k/n)}}{\sqrt{2\pi k (1-k/n)}},\quad
1\leq k\leq n-1
\end{align*}
(see~\cite{Odl95} and \cite[Chapter~10, Lemma~7]{McWSlo78} respectively).
However, these bounds are either not accurate enough or their forms are not
convenient enough.

We suggest an upper bound on the binomial coefficients that holds over the
entire parameter range and preserves the de Moivre--Laplace form.

\begin{theorem*}\label{Th.PRELIM.1}
For a positive integer~$n$ and $k\in\{0,1,\ldots,n\}$, it holds that
$$
\binom{n}{k}\leq \frac{2^n}{\sqrt{\pi n/2}}
\exp\left(-\frac{2(k-n/2)^2}{n}+\frac{23}{18n}\right).
$$
\end{theorem*}

When deriving the bound, we follow the approach of the paper~\cite{Sza16} which
in turn extends previous lines of research as explained in the paper.

In Sections~\ref{BENT}~--- \ref{SQUARES}, we discuss the use of the proposed bound.
More specifically, in Section~\ref{BENT} we estimate the number of
continuations of a given Boolean function to bent functions,
in Section~\ref{LATIN} we investigate dependencies into the Walsh--Hadamard
spectra,
in Section~\ref{SQUARES} we obtain restrictions on the number of
representations as sum of squares of integers bounded in magnitude.
Section~\ref{PROOF} contains the proof of Theorem.

\section{Continuations to bent functions}\label{BENT}

Let $\FF_2$ be the field of 2 elements ($0$ and $1$), $\FF_2^n$ be the
$n$-dimensional vector space over~$\FF_2$, and $\calF_n$ be the set of Boolean
functions in $n$ variables, that is, the functions from $\FF_2^n$ to~$\FF_2$.
A function $f\in\calF_n$ is uniquely described by its Walsh--Hadamard
spectrum (spectral function)
$$
\hatup{f}(\vec{u})=
\sum_{\vec{x}\in\FF_2^n}\chi(f(\vec{x})+\vec{x}\cdot\vec{u}),\quad
\vec{u}\in\FF_2^n.
$$
Here $\chi$ is the non-trivial additive character of $\FF_2$: $\chi(a)=(-1)^a$,
the dot denotes the inner product of vectors.

A spectrum~$\hatup{f}$ satisfies Parseval's identity:
$$
\sum_{\vec{u}\in\FF_2^n}\hatup{f}(\vec{u})^2=2^{2n}.
$$
Due to this identity, $\max_\vec{u}|\hatup{f}(\vec{u})|\geq 2^{n/2}$.
If the lower bound is attained (this is only possible when $n$ is even),
then~$f$ is called a \emph{bent function}~\cite{Rot76}.
Let $\calB_n$ be the set of bent functions in $n$ variables.

Bent functions are ideal objects in several contexts of coding theory,
cryptography and combinatorics.
Despite intensive research, bent functions remain difficult to study,
there are many open problems related to them.
One of these problems is to estimate the number of bent functions both from
below and from above.
In~\cite{Agi20} it is proposed to obtain upper bounds by estimating the number
of continuations of a Boolean function to bent functions.
Next we recall and detail the approach of~\cite{Agi20}.

Let~$k<n$.
A function $f\in\calF_n$ is a \emph{continuation} of~$g\in\calF_k$ if
$$
g(y_1,\ldots,y_k)=f(\underbrace{0,\ldots,0}_{n-k},y_1,\ldots,y_k).
$$
In other words, $f$ is a continuation of~$g$ if $g$ is a \emph{restriction}
of~$f$ to the affine plane $E=\{(0,\ldots,0,y_1,\ldots,y_k)\colon y_i\in\FF_2\}$.
The actual choice of~$E$ here is unimportant, any other plane of dimension~$k$
can be used instead.

Let $\calB_n(g)$ be the set of all functions~$f\in\calB_n$ that continue~$g$.
To obtain an upper bound on $|\calB_n(g)|$ we use the representation of bent
functions by bent rectangles. This representation is introduced
in~\cite{Agi02}. Let us recall it.

Let $f\in\calF_n$ and $n=m+k$, where $m$ and~$k$ are positive integers.
Consider all possible restrictions of~$f$ on the planes parallel to~$E$:
$$
f_\vec{u}(\vec{y})=f(\vec{u},\vec{y}),\quad
\vec{u}\in\FF_2^m,\quad
\vec{y}\in\FF_2^k.
$$
Let us pass from the restrictions $f_\vec{u}$ to their spectra $\hatup{f}_\vec{u}$
and then construct the function
$$
\boxup{f}(\vec{u},\vec{v})=\hatup{f}_\vec{u}(\vec{v}),\quad
\vec{u}\in\FF_2^m,\quad
\vec{v}\in\FF_2^k.
$$
We call $\boxup{f}$ a \emph{rectangle} of $f$.
By construction, the restrictions $\boxup{f}(\vec{u},\vec{v})$ to $\vec{v}$
(\emph{rows}) are spectral functions. If additionally the restrictions
$\boxup{f}(\vec{u},\vec{v})$ to $\vec{u}$ (\emph{columns}) multiplied by
$2^{(m-k)/2}$ are also spectral functions, then $\boxup{f}$
is called a \emph{bent rectangle}.
In~\cite{Agi02} it is proved that $f$ is bent if and only if $\boxup{f}$ is bent.

In terms of bent rectangles, the problem of estimating the cardinality of
$\calB_n(g)$ reduces to estimating the number of bent rectangles $\boxup{f}$
whose first row is fixed:
$$
\boxup{f}(\vec{0},\vec{v}) = \hatup{g}(\vec{v}).
$$

Note that if $k>n/2$, then there exist functions $g$ that cannot be
continued: $|\calB_n(g)|=0$.
An example is a function that takes exactly $2^{k-1}+1$ zero values and
therefore~$\hatup{g}(\vec{0})=2$.
The normalized column $2^{(m-k)/2}\boxup{f}(\vec{u},\vec{0})$ takes odd or
fractional value
$$
2^{(m-k)/2}\boxup{f}(\vec{0},\vec{0})=2^{(m-k)/2}\hatup{g}(\vec{0})=2^{(m-k)/2+1}
$$
and cannot be a spectral function.
Hence $\boxup{f}$ cannot be a bent rectangle.

For $k\leq n/2$ the situation changes.

\begin{proposition}\label{Pr.BENT.1}
If~$n$ is even, then for any Boolean function $g$ in $k\leq n/2$ variables
it holds that $|\calB_n(g)|>0$ and
$$
\log_2|\calB_n(g)|\leq {2^n\left(1-\gamma_{2^{n-k}}\right)},
$$
where
$$
\gamma_M=
\frac{\log_2 e+\log_2\pi + \log_2 M - 1}{2M}-\frac{23\log_2 e}{18M^2}.
$$
\end{proposition}
\begin{proof}
Let us prove that $|\calB_n(g)|\neq 0$.
It is sufficient to consider the case $k=n/2$. The rectangle
$$
\boxup{f}(\vec{u},\vec{v})=\hatup{g}(\vec{u}+\vec{v}),\quad
\vec{u},\vec{v}\in\FF_2^k,
$$
implements the biaffine construction from~\cite{Agi08} and is therefore bent.
The function~$f$ corresponding to~$\boxup{f}$ is also bent.
Moreover, the first ($\vec{u}=\vec{0}$) row of $\boxup{f}$ coincides
with~$\hatup{g}$ and $f$ is a continuation of~$g$.
In whole, $f\in\calB_n(g)$ and $\calB_n(g)$ is non-empty.

Let us proceed to find an upper bound on $|\calB_n(g)|$.
We have to estimate the number of bent rectangles $\boxup{f}(\vec{u},\vec{v})$
such that $\boxup{f}(\vec{0},\vec{v})=\hatup{g}(\vec{v})$.
Denote $M=2^m$, $K=2^k$, $s_\vec{v}=2^{(m-k)/2}\hatup{g}(\vec{v})$.

Consider the columns of $\boxup{f}$ multiplied by $2^{(m-k)/2}$.
They are spectral functions
$$
\hatup{g}_\vec{v}(\vec{u})=2^{(m-k)/2}\boxup{f}(\vec{u},\vec{v}),\quad
\vec{u}\in\FF_2^m,\quad
\vec{v}\in\FF_2^k,
$$
which correspond to the functions $g_\vec{v}\in\calF_m$.
According to the restrictions on $\boxup{f}$,
$$
\hatup{g}_\vec{v}(\vec{0})=
2^{(m-k)/2}\boxup{f}(\vec{0},\vec{v})=
2^{(m-k)/2}\hatup{g}(\vec{v})=
s_\vec{v}.
$$

There are $2^M$ ways to choose $g_\vec{v}$ and exactly
$$
\binom{M}{(M+s_\vec{v})/2}
$$
of them yield the equality $\hatup{g}_\vec{v}(\vec{0})=s_\vec{v}$.
Therefore, the desired number of continuations
(the number of suitable bent rectangles)
$$
|\calB_n(g)|\leq\prod_{\vec{v}\in\FF_2^k}\binom{M}{(M+s_\vec{v})/2}.
$$
Taking the logarithm of both parts of this inequality and using the bound of
Theorem, we obtain
$$
\log_2|\calB_n(g)|\leq\sum_{\vec{v}\in\FF_2^k}
\left(M-\alpha_M s_\vec{v}^2 - \beta_M\right).
$$
Here
$$
\alpha_M = \frac{\log_2 e}{2M},\quad
\beta_M  = \frac{1}{2}(\log_2\pi + \log_2 M - 1) - \frac{23\log_2 e}{18M}.
$$

Using the equality
$$
\sum_{\vec{v}\in\FF_2^k} s_\vec{v}^2 =
2^{m-k}\sum_{\vec{v}\in\FF_2^k}\hatup{g}(\vec{v})^2 =
2^{m-k}\cdot 2^{2k} = MK,
$$
we finally get
$$
\log_2|\calB_n(g)|\leq MK(1-\alpha_M -\beta_M/M) = MK(1-\gamma_M).
$$
That was to be proven.
\end{proof}

In the proof, we used the following form of the bound of Theorem:
$$
\binom{M}{(M+s)/2}\leq 2^{M-\alpha_M s^2-\beta_M}.
$$
From the coefficients $\alpha_M$ and~$\beta_M$ we determined the
quantity~$\gamma_M=\alpha_M+\beta_M/M$.
The larger~$\gamma_M$, the more accurate the estimate of $|\calB_n(g)|$.
It turns out that $\alpha_M$ and~$\beta_M$ can be adjusted so that $\gamma_M$
increases, but the bound on the binomial coefficients remains valid.

For small~$M$, the optimal tuples $(\alpha_M,\beta_M,\gamma_M)$ can be found by
solving the linear programming problem. The solutions are presented in the table below.
The quantities $\gamma_M$ in the last column of the table can be used in
Proposition~\ref{Pr.BENT.1} instead of those specified there.

$$
\begin{array}{|c|c|c|c|}
\hline
M  &  \alpha_M & \beta_M & \gamma_M\\
\hline
\hline
2  &  1/2 & 1 & 3/4\\
4  &  1/6 & 4/3 & 1/2\\
8  &  1/12 & 14/3-\log_2 7 &
   2/3-(\log_2 7)/8\approx 0.3157\\
\hline
\end{array}
$$

\section{Latin dependencies}\label{LATIN}

Let~$\ZZ^N$ be the set of $N$-tuples of integers,
$\Omega$ be a finite subset of $\ZZ^N$,
and $p$ be a probability distribution over $\Omega$.
Let $\vec{a}=(a_1,\ldots,a_N)$ be a random tuple of~$\Omega$ following~$p$ and
let $p_i$ be the marginal distribution of the $i$th coordinate of the tuple:
$p_i(x)=\Pr{a_i=x}$, $i=1,\ldots,N$.

The degree of dependence between coordinates of $\vec{a}$ can be estimated as follows.
\begin{enumerate}
\item
Choose tuples $\vec{a}^1,\ldots,\vec{a}^N$ independently at random according to
the distribution~$p$.
\item
Construct a tuple $\vec{b}=(b_1,\ldots,b_N)$ in which $b_i$ is the $i$th
coordinate of $\vec{a}^i$.
\item
Determine the degree of dependence: $L(p) = \Pr{\vec{b}\in\Omega}$.
\end{enumerate}

It is convenient to imagine that the tuples $\vec{a}^i$ form the rows of a
matrix of order~$N$ and then $\vec{b}$ is the diagonal of the matrix.
The probability $\Pr{\vec{b}\in\Omega}$ characterizes the fulfillment of a
constraint on the diagonal provided that all rows satisfy this constraint.
Similar constraints (on rows, columns, sometimes on diagonals) are imposed in
Latin squares. That is why we call the quantity $L(p)$ the degree of the
\emph{Latin} dependence.

The quantity~$L(p)$ is the probability of a successful ``assembly'' of an
element of~$\Omega$ from ``scattered'' coordinates with the
distributions~$p_1,\ldots,p_N$.
As the dependence between the coordinates of~$\vec{a}$ increases, we should
expect a decrease in the probability~$L(p)$.
The maximum value of $L(p)=1$ is achieved when the coordinates of~$\vec{a}$
are independent.

The degree of the Latin dependence can be computed as follows:
$$
L(p)=\sum_{(b_1,\ldots, b_N)\in\Omega}\prod_{i=1}^N p_i(b_i).
$$

\begin{example}
Let $\Omega$ consist of permutations of the numbers from $1$ to $N$
and let $p$ be the uniform distribution over~$\Omega$.
Then $p_i(x) = 1 / N$ if $x\in\{1,\ldots,N\}$ and $p_i(x)=0$ otherwise.
Thus,
$$
L(p)=\frac{N!}{N^N} \approx \frac{\sqrt{2\pi N}}{e^N}.
$$
We can speak of the \emph{exponential} dependence meaning that $1/L(p)$
grows exponentially with $N$.
\end{example}

\begin{example}
Let $N$ be even and $p$ assign the probability $1/\binom{N}{N/2}$
to each of $(0,1)$-tuples of length $N$ with exactly $N/2$ units.
Then~$p_i(x)=1/2$ for $x\in\{0,1\}$ and
$$
L(p)=\binom{N}{N/2} 2^{-N}\approx \sqrt{\frac{2}{\pi N}}.
$$
We can speak of the \emph{power} dependence or, more precisely, ``\emph{square root}''
dependence.
\end{example}

Let us show how to use Theorem to estimate the degree of the Latin dependence
in the Walsh--Hadamard spectra (see Section~\ref{BENT}).

\begin{proposition}\label{Pr.LATIN.1}
Let $\Omega$ consist of tuples of values of spectral functions $\hatup{f}$
corresponding to all possible $f\in\calF_n$.
Let~$p$ be the uniform distribution over~$\Omega$.
Then
$$
L(p)\leq
\exp\left(\frac{23}{18}\right)
\left(\frac{8}{\pi e N}\right)^{N/2},\quad
N=2^n.
$$
\end{proposition}

\begin{proof}
Since there are $2^N$ functions $f$ and the mapping $f\mapsto\hatup{f}$ is bijective,
$|\Omega|=2^N$.
Elements of $\Omega$ are $N$-tuples of even numbers bounded in magnitude by~$N$.
Marginal distributions of coordinates of the tuples:
$$
p_i(x)=2^{-N}\binom{N}{(N+x)/2},\quad
x\in\{-N,-N+2,\ldots,N\}.
$$
The degree of dependence between coordinates:
$$
L(p)=\sum_{(b_1,\ldots,b_N)\in\Omega}\prod_{i=1}^N 2^{-N}\binom{N}{(N+b_i)/2}.
$$
Note that due to Parseval's identity, $\sum_i b_i^2 = N^2$.

Applying Theorem, we obtain
\begin{align*}
L(p)
&
\leq 2^N \max_{(b_1,\ldots,b_N)\in\Omega}
\prod_{i=1}^N\sqrt{\frac{2}{\pi N}}\exp\left(-\frac{b_i^2}{2N}+\frac{23}{18N}\right)=\\
& =
2^N \left(\frac{2}{\pi N}\right)^{N/2}
\exp\left(-\frac{N}{2}+\frac{23}{18}\right)
=
\exp\left(\frac{23}{18}\right)
\left(\frac{8}{\pi e N}\right)^{N/2}.
\end{align*}
That was to be proven.
\end{proof}

As we see, the degree of dependence in the Walsh--Hadamard spectra
is asymptotically higher than in the permutations. In the case of spectra,
we can speak of the \emph{factorial} dependence.

\section{Representations as sum of squares}\label{SQUARES}

Let $r_{s,n}(N)$ be a number of representations of a positive integer $N$
as sum of squares of~$s$ integers, each bounded in magnitude by~$n$:
$$
r_{s,n}(N)=\left|\left\{(a_1,\ldots,a_s)\in\ZZ^s\colon
\textstyle\sum_{i=1}^s a_i^2=N,\
|a_i|\leq n\right\}\right|.
$$

The function $r_{s,n}(N)$ and especially the function $r_s(N)$, in which the
restrictions on $|a_i|$ are removed, have long been studied in number theory.
One of the results is the following asymptotic integral bound on $r_s(N)$:
$$
\sum_{N=1}^R r_s(N)=
\frac{(\pi R)^{s/2}}{\Gamma(s/2+1)}+O(R^{(s-1)/2}),\quad
R\to\infty
$$
(see for example~\cite{Tak18}).
For $s=2$, this is known as Gauss' circle theorem.

Using our Theorem, we obtain an integral bound on $r_{s,n}(N)$.

\begin{proposition}\label{Pr.SQUARES.1}
It holds that
$$
\sum_{N=0}^{sn^2}
r_{s,n}(N)\exp\left(-\frac{N}{n}\right)
\geq
(\pi n)^{s/2}
\exp\left(-\frac{23 s}{36 n}\right).
$$
\end{proposition}

\begin{proof}
A tuple $(a_1,\ldots,a_s)$ is an integral point of the $s$-dimensional
real space $\RR^s$.
The point lies within $s$-dimensional cube with side~$2n$ and simultaneously
on a circle of radius~$\sqrt{a_1^2+\ldots+a_s^2}$ centered at the origin.
Any point within the cube lies on a circle of some radius and the square of
this radius is a non-negative integer not exceeding $sn^2$.
Let us use this observation.

Let $\xi_1,\ldots,\xi_s$ be random variables obtained by summing
$2n$ independent random variables taking the values $1$ and $-1$
with equal probability.
Then for the points $(a_1,\ldots,a_s)$ within the cube it holds that
$$
\Pr{(\xi_1,\ldots,\xi_s)=(2a_1,\ldots,2a_s)}
=\prod_{i=1}^s 2^{-2n}\binom{2n}{n+a_i}
\leq
\frac{1}{(\pi n)^{s/2}}\exp\left(-\frac{N}{n}+\frac{23 s}{36 n}\right).
$$
Here $N=\sum_i a_i^2$ is a square of a radius of a circle containing
the point $(a_1,\ldots,a_s)$.

We have
\begin{align*}
1 &= \sum_{-n\leq a_1,\ldots,a_s\leq n}
\Pr{(\xi_1,\ldots,\xi_s)=(2a_1,\ldots,2a_s)}=\\
&=\sum_{N=0}^{sn^2}\,\sum_{\genfrac{}{}{0pt}{1}
{-n\leq a_1,\ldots,a_s\leq n}{\sum a_i^2 = N}}
\Pr{(\xi_1,\ldots,\xi_s)=(2a_1,\ldots,2a_s)}\leq\\
&
\leq
\sum_{N=0}^{sn^2}
r_{s,n}(N)
\frac{1}{(\pi n)^{s/2}}\exp\left(-\frac{N}{n}+\frac{23 s}{36 n}\right),
\end{align*}
from which the desired result follows.
\end{proof}

\section{Proof of Theorem}\label{PROOF}

\begin{lemma*}\label{L.PROOF.1}
For a positive integer~$n$ and $k=0,\pm 1,\ldots,\pm n$, it holds that
$$
\binom{2n}{n+k}\leq\frac{2^{2n}}{\sqrt{\pi n}}
\exp\left(-\frac{k^2}{n}+\frac{23}{36n}\right).
$$
\end{lemma*}
\begin{proof}
The bound obviously holds for $k=\pm n$.
For $n=1,2$, the bound is verified by direct calculations.
Since the binomial coefficients $\binom{2n}{n+k}$ and $\binom{2n}{n-k}$
coincide, it remains to deal with the case where $n\geq 3$ and $0\leq k<n$.

For this case, as shown in~\cite{Sza16},
$$
\log\left(\binom{2n}{n+k}2^{-2n}\right)\leq
\log\frac{1}{\sqrt{\pi n}} - b_{k,n} - \frac{1}{9n},
$$
where
$$
b_{k,n}=n\left(
\left(1+\frac{k+1/2}{n}\right)\log\left(1+\frac{k}{n}\right)+
\left(1-\frac{k-1/2}{n}\right)\log\left(1-\frac{k}{n}\right)
\right).
$$
To complete the proof, we show that $b_{k,n}>k^2/n-c/n$, $c=23/36+1/9=3/4$.

Let us consider the function $f(k)=b_{k,n}-k^2/n$.
In~\cite{Sza16}, it is represented as follows:
$$
f(k)=
-\frac{k^2}{2n^2}+
\frac{k^4}{2n^3}\left(\frac{1}{3}-\frac{1}{2n}\right)+
\frac{k^6}{2n^5}\left(\frac{1}{5}-\frac{1}{2n}\right)+\ldots.
$$
Let $k_0=\sqrt{3n/2}$. In the region $k\leq k_0$, the inequality
$$
f(k)>-\frac{k^2}{2n^2}\geq -\frac{k_0^2}{2n^2}=-\frac{c}{n}
$$
holds.
Now it is sufficient to prove that $f(k)$, viewed as a real-variable function,
increases for $k\in[k_0,n-1]$.

Denote $x=k/n$ and take the derivative:
\begin{align*}
f'(k)&=2\arctanh\left(\frac{k}{n}\right)-\frac{2k}{n}+\frac{k}{k^2-n^2}=\\
&=2\arctanh x-2x-\frac{x}{2n(1-x^2)}=\\
&=\frac{2x^3}{3}+\frac{2x^5}{5}+\frac{2x^7}{7}+\ldots-\frac{x}{2n(1-x^2)}>\\
&>\frac{2x^3}{3}+\frac{2x^5}{5}-\frac{x}{2n(1-x^2)}.
\end{align*}

The derivative of the last expression has the form:
$$
\frac{(1+x^2)(4n x^2(1-x^2)^2-1)}{2n(1-x^2)^2}.
$$
It is positive in the region $x\in[k_0/n,(n-1)/n]$ and therefore
$f'(k)$ increases for $k\in[k_0,n-1]$.
Moreover,
$$
f'(k_0)>\frac{2x_0^3}{3}-\frac{x_0}{2n(1-x_0^2)}=
x_0\left(\frac{1}{n}-\frac{1}{2n(1-3/(2n))}\right)\geq 0
$$
(we take into account that $n\geq 3$) and therefore $f(k)$ also increases.
\end{proof}

Let us now turn to the proof of Theorem.
It is sufficient to consider the case of odd $n=2m-1$ and $k\leq m$.
In this case,
\begin{align*}
\binom{2m-1}{k}&=\frac{2m-k}{2m}\binom{2m}{k}\leq\\
&\leq\left(1-\frac{k}{2m}\right)\frac{2^{2m}}{\sqrt{\pi m}}
\exp\left(-\frac{(k-m)^2}{m}+\frac{23}{36m}\right)\leq\\
&\leq\frac{2^{2m-1}}{\sqrt{\pi (m-1/2)}}
\exp\left(-\frac{(k-m+1/2)^2}{m-1/2}+\frac{23}{36(m-1/2)}+t(k)\right),
\end{align*}
where
\begin{align*}
t(k)&=-\frac{(k-m)^2}{m}+
  \frac{(k-m+1/2)^2}{m-1/2}+\log 2 + \log\left(1-\frac{k}{2m}\right)=\\
&=\log\left(2-\frac{k}{m}\right)-\frac{2m^2-m-2k^2}{2m(2m-1)}.
\end{align*}

To complete the prove, we show that $t(k)\geq 0$ for $k\in[0;m]$.

The derivative
$$
t'(k)=\frac{2k}{2m^2-m}-\frac{1}{2m-k}=\frac{2(m-k)^2-m}{(2m^2-m)(2m-k)}.
$$
Therefore, the minimum of $t(k)$ is reached at the point $k_0=m-\sqrt{m/2}$,
and this minimum is
$$
t(k_0)=\log\left(1+\frac{1}{\sqrt{2m}}\right)-\frac{1}{1+\sqrt{2m}}.
$$
Denoting $x=\sqrt{2m}$, we obtain
$$
t(k_0)\geq \frac{1}{x}-\frac{1}{2x^2}-\frac{1}{1+x}=\frac{x-1}{2x^2(x+1)}>0.
$$
That was to be shown.