\section{Introduction}
Deep learning, especially in the form of convolutional neural networks (CNNs), has achieved tremendous successes in various machine learning tasks, such as image classification~\cite{imagenet_cvpr09}, object detection~\cite{lin2014microsoft} and machine translation~\cite{vaswani2017attention} \emph{etc}\onedot} \def\vs{\emph{vs}\onedot However, it remains a big challenge dealing with non-grid or irregular data such as \emph{e.g}\onedot} \def\Resp{\emph{resp}\onedot protein-interaction networks, social networks, and knowledge graphs that may best be considered graph-structured data. Due to an abundance of such graph-structured data, graph neural networks (GNNs) have been attracting an increasing level of attention and have successfully been applied to a number of tasks. Consequently, we can see in the literature that much research effort has gone into investigating deep learning architectures and finding powerful representations for such graph-structured data.

On the path to finding powerful and discriminative representations, exploiting pairwise relationships within graph data and their feature vectors in a principled way has become a pivotal part of the graph learning area. One of the earliest works can be traced back to~\cite{henaff2015deep} in 2015, and the following works including Chebyshev Convolutional Neural Networks (ChebyNets)~\cite{defferrard2016convolutional}, Graph Convolutional Neural Networks (GCNs)~\cite{kipf2016semi}, GraphSAGE~\cite{hamilton2017inductive} and Graph Attention Networks (GATs)~\cite{velivckovic2017graph} demonstrate the importance of leveraging neighborhood information. Although those methods are derived from different perspectives (the spatial and spectral domain), all of them follows message passing scheme where messages between connected nodes are iteratively passed and permutation-invariant aggregation functions (such as mean, summation, and maximum) are employed in each layer to learn a representation for each node or graph.

Recent work~\cite{xu2018powerful} proposes a simple architecture, GIN, which is as powerful as Weisfeiler-Lehman (WL) \cite{leman1968reduction}. Meanwhile, they unveil that a GNN can achieve this when it learns a injective multiset function which should consist a summation aggregator~\cite{xu2018powerful}. A \textit{multiset}, mathematically speaking, denotes a set of feature vectors of a node and its neighbors, while nodes' class and their feature vectors can be repeated. In this scenario, GNNs have mean or maximum aggregator will fail to learn a injective multiset function. However, during training stage, a GNN may still generate indiscriminative features after the sumation aggregator when the network have not converged to an injection function, which will harm the performance.

Moreover, by gathering information layer by layer, all the nodes in a \textit{multiset} tend to have similar representations, which is also known as over-smoothing. This is also the reason why these types of works are favored by assortative graphs such as citation networks but degenerate significantly in disassortative graphs where the nodes of the same class share a high structural similarity but are far apart from each other~\cite{ribeiro2017struc2vec}. This phenomenon is consistent with the most recent paper~\cite{dwivedi2020benchmarking} which thoroughly demonstrates the performance of different architectures on various benchmarks.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=8cm,keepaspectratio]{Figures/training_curve_train_MAE.pdf}
  \caption{Trainig mean absolute error (MAE) on ZINC with GatedGCN-E and GatedGCN-E+FOG. Both networks have same hyper-parameter settings except hidden layer dimension which is for keeping networks having similar total number of parameters. As the baseline model, GatedGCN-E has a rougher training curve and lower finial performance which will be shown in the experiment section.} \label{fig:GatedGCNEvsGatedEFOG}
\end{figure}

The core part of GNNs is to learn a parametrized network that work as an injection function to project every \textit{multiset} into a single unique representation~\cite{xu2018powerful}. Existing approaches ignore the fact that, given the same multiset, two different center nodes might have significantly different second-order feature spaces while sharing the same first-order feature space. Hence, we propose a novel central node permutation variant aggregation module called \textbf{F}eature c\textbf{O}rrelation \textbf{A}ggregation (FOG) to discover the intrinsic representation ability of a multiset. To address the aforementioned drawbacks of existing GNNs, we use the Kronecker Product of a multiset's feature vector to generate a correlation space (second-order statistical information). In this new space we aggregate the correlation feature vectors as a complementary information based on the aggregation features of existing nodes. Despite two multisets being quite similar, the resulting feature extracted from the
second-order space is distinctive while the simple first-order aggregation fails to find the difference.  In addition, our FOG may be readily layered on top of any existing GNNs.  As Fig.~\ref{fig:GatedGCNEvsGatedEFOG} shown, FOG helps the GateGCN-E \cite{bresson2017residual} to learn more discriminative feature and achieve lower cross-entropy loss compared to the original networks.

In a nutshell, our contribution in this paper is three-fold.
\begin{enumerate}
    \item We discuss and analyze the weaknesses in current GNN structures, while proposing a new FOG module which dynamically aggregates feature representations from the feature correlation space for each multiset.
    \item Our FOG module is extremely simple and can be inserted in any GNN structure. We carefully design and embed our FOG module into GCNs, GAT, GatedGCNs, GIN, and GraphSAGE with a fewer number of parameters compared to the original models to provide fair comparisons.
    \item  We conduct comprehensive experiments on graph pattern recognition, node classification, graph regression, and edge classification on different types of datasets to validate the effectiveness and compatibility of our module.
\end{enumerate}

\section{Related Works}

\begin{table*}[!ht]
\caption{Commonly used notation in this paper}
\begin{center}
\scalebox{0.8}{
\begin{tabular}{l|l}
\hline
Notation & Descriptions \\
\hline

$f_{base}$ & The function of the base GNN module. \emph{e.g}\onedot} \def\Resp{\emph{resp}\onedot, GCN, GAT, GatedGCN, GIN, and GraphSAGE. \\

$\otimes$ & Kronecker product. Given two vectors $\Mat{a} \in \mathbb{R}^{C_\Mat{a}},\Mat{b} \in \mathbb{R}^{C_\Mat{b}}$, the outcome of the Kronecker product is\\
& $\Mat{a} \otimes \Mat{b} = [a_1\Mat{b},a_2\Mat{b},..,a_{C_\Mat{a}}\Mat{b}] \in \mathbb{R}^{C_\Mat{a}C_\Mat{b}}.$ \\
$\relu(\cdot)$ & Rectified linear unit. $\relu(x)=\max(x,0)$. \\

$\concat(\cdot,\cdot)$ & Concatenate two vectors along the channel.\\
$\phi(\cdot)$ & An non-linear activation function.\\
$\bn(\cdot)$ & Batch normalization.\\

\hline
\end{tabular}
}
\end{center}\label{table:ops}
\end{table*}
Our FOG module is used to enhance the representation ability of existing GNN structures, therefore it is closely related to works in that domain.
One of the components in our module related to the way we generate the correlation feature has been investigated in previous studies. In this section, we review methods that are related and discuss their contributions.

\noindent\textbf{Graph Neural Networks.} GNN was first proposed by Gori~\cite{GNN2005} and have since evolved and been applied in a much wider range of applications. Most of the GNNs are considered from either a spectral or a spatial perspective. For example, by defining the Laplacian matrix for a given graph, the orthogonal graph transform basis can be obtained through applying SVD on the Laplacian matrix. Spectral-based methods are able to filtering the feature vectors using the element-wise Hadamard product in the spatial domain which is equivalent to applying the convolution operation in the graph domain. ChebyNets~\cite{defferrard2016convolutional} approximates the k-th order convolutional kernel by employing Chebyshev polynomials in a recursive way. GCNs~\cite{kipf2016semi} replace the k-th order Chebyshev expansion with a first-order approximation to simplify the structure.

From the spatial perspective, existing methods focus on the way of picking appropriate neighbors during aggregation. GraphSAGE~\cite{hamilton2017inductive} proposes a sampling algorithm that randomly samples a fixed number of neighbors during training. FastGCN~\cite{chen2018fastgcn} and AdaptGCN~\cite{huang2018adaptive} propose to apply different sampling methods in the local neighborhood to alleviate the exponential growth in the number of locally sampled nodes and thereby speeding up the convergence of the optimization. Instead of dropping nodes, Graph Attention Network (GAT) \cite{velivckovic2017graph} adopts a multi-head attention mechanism \cite{vaswani2017attention} from an NLP task to learn a weight for each central-neighbor pair.

\vspace{2pt}
\noindent\textbf{Feature Correlation Description.} Feature aggregation has been studied extensively for visual tasks, such as image or object retrieval and detection. The Kronecker product is the most widely used operation used to capturing second-order statistical information~\cite{Tuzel2006RegionCovariance,Tuzel2007Human,Lin2015BCNN,NIPS2018_7429,lin2017improved,Shen2018EndtoEndDK, Fang2019BiAttention}. In detection tasks, covariance matrices are investigated to represent the regional descriptors~\cite{Tuzel2006RegionCovariance, Tuzel2007Human}. Lin \emph{et al}\onedot proposed the bilinear CNN where the outer product of two feature vectors, generated from two non-identical networks, is used to model the local pairwise interactions~\cite{Lin2015BCNN}. A further study in~\cite{lin2017improved} proved that rich correlation statistics could also be obtained by a self outer product. Cross-modality features, \emph{e.g}\onedot} \def\Resp{\emph{resp}\onedot, visual and language, can also be fused via a bilinear operation~\cite{NIPS2018_7429}. In~\cite{Fang2019BiAttention}, second-order auto-correlation, generated via a bilinear mapping, is used in an attention block to identify salient regions within the images.

In this paper, the proposed FOG module extracts a more discriminative feature from a correlation space which is constructed by using the Kronecker product between the central node and its neighbours in a graph neural network. This simple, yet effective, module brings significant performance gains across various tasks on graph-structured data over and above existing state-of-the-art GNNs.

\section{Methodology}\label{sec:structure}
\subsection{Notation}
We show a graph $\mathcal{G}$ with nodes $\mathcal{V} = \{v_1, v_2, \ldots, v_n\}$ and edge set $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ by $\mathcal{G}=(\mathcal{V}, \mathcal{E})$. For each node $v \in \mathcal{V}$, its feature representation is denoted by $\Mat{h}_v \in \mathbb{R}^{C_v}$, where $C_v$ is the channel dimension of the node feature. Given $v$ as a central node, its neighbour set is defined as $\mathcal{N}(v) = \{u_i \in \mathcal{V}: (v,
u_i) \in \mathcal{E},i=1,2,\cdots, \left | \mathcal{N}(v) \right |\}$. The
cardinality of the neighbour set of $v$ is shown by
$\left | \mathcal{N}(v) \right |$. The feature of the edge connecting node $v$ and $u_i$, is denoted by $\Mat{e}_{vu_i} \in \mathbb{R}^{C_e}$, where $C_e$ is the channel dimension of the edge feature. Other notations used in this paper are illustrated in Table \ref{table:ops}.

Formally, the $l$-th layer/iteration layer of a GNN can be formulated as,
\begin{align}
\Vec{a}_{v}^l =\text{AGGREGATE}\big(\{\Mat{h}_{u}^{l-1}:u \in \mathcal{N}(v)\}\big)\;,
\end{align}
\begin{align}
\Vec{h}_{v}^l = \text{COMBINE} (\Vec{h}_v^{l-1}, \Vec{a}_{v}^l),
\end{align}
where $\text{AGGREGATE}(\cdot)$ is an aggregation function that aggregating features of neighbors, and $\text{COMBINE}(\cdot)$ means the combination of a central node and its neighbors' aggregated features~\cite{xu2018powerful}. Note that, most GNNs propose a modification of the \text{AGGREGATE} and \text{COMBINE} functions which only obtains the first-order features, e.g. in GAT, \text{AGGREGATE} is a non-linear function, in which neighbors' features are aggregated by weighted summation. Meanwhile, GIN directly uses summation aggregator for neighbors but places a learnable weight on the central node and a non-linear function in the \text{COMBINE}. In contrast, we are taking the feature correlation of the central node and its neighbors into account, and this second-order information can be added on the top of any existing GNN as follow:
\begin{align}
\Vec{h}_{v}^l = \concat\big(\text{COMBINE}(\Vec{h}_v^{l-1}, \Vec{a}_{v}^l), f_{\textrm{FOG}}(\Vec{h}_{v}^{l-1},\{\Vec{h}_{u_i}^{l-1}\})\big),
\label{eq:GNNFOG}
\end{align}
where the $f_{\textrm{FOG}}(\cdot,\cdot)$ is our FOG module and will be described in details in the following section. In Equation \ref{eq:GNNFOG}, our module is working in a different path from the previous methods. In this scenario, FOG generates a more discriminative and diversified feature vector that describes the correlation information between the central node and its neighbors as Figure \ref{fig:GNNvsFOG} shows. This mechanism enables FOG to not only introduce complementary information to existing GNNs architectures and prevent the GNNs from over-smoothing to some extent, but also be a powerful independent architecture.

\begin{figure*}[!ht]
  \centering
  \includegraphics[width=14cm,keepaspectratio]{Figures/GNNvsFOG.pdf}
  \caption{When aggregating neighbors' node features to a central node, GNN only passes the first-order information in the multiset. However, FOG can pass the second-order information through the Kronecker Product operation. Note that, an non-linear layer is applied after the Kronecker Product operation for dimension reduction.} \label{fig:GNNvsFOG}
\end{figure*}

\subsection{FOG module}

Let  the feature vector of a
node
$v$ in layer ${l-1}$  be $\Mat{h}_v^{l-1} \in \mathbb{R}^{C_{in}}$.
The neighbors of $v$, shown by $u_i \in \mathcal{N}(v)$, form a neighbor feature-set $\mathbb{H}_v^{l-1} = \{\Vec{h}_{u_i}^{l-1}\}$, where $\Vec{h}_{u_i}^{l-1} \in \mathbb{R}^{C_{in}}$.
We first perform a non-linear mapping on $\Vec{h}_{v}^{l-1}$ and $\Vec{h}_{u_i}^{l-1}$ to a possibly lower-dimensional space via $\Mat{W}_1^l \in \mathbb{R}^{C_{h1} \times C_{in}}$, and a $\relu$ function. Applied by another mapping $\Mat{W}_2^l \in \mathbb{R}^{C_{h2} \times C_{h1}}$ with $\relu$, the dimensions of neighbor features are further reduced as:

\begin{align}
\tilde{\Vec{h}}_{v}^l = \bn\big(\relu(\Mat{W}_1^l\Mat{h}_{v}^{l-1})\big)\;,
\end{align}
\begin{align}
\tilde{\Vec{h}}_{u_i}^l = \bn\bigg(\relu\Big(\Mat{W}_2^l\bn\big(\relu(\Mat{W}_1^l\Mat{h}_{u_i}^{l-1})\big)\Big)\bigg)\;.
\end{align}

This is followed by computing the Kronecker product between the centre node representation (\emph{i.e}\onedot} \def\Ie{\emph{i.e}\onedot, $\tilde{\Vec{h}}_{v}^l$)
and the corresponding neighbor nodes (\emph{i.e}\onedot} \def\Ie{\emph{i.e}\onedot, $\tilde{\Vec{h}}_{u_i}^l$) as follows:

\begin{align}
    \mathbb{R}^{C_{h1}C_{h2}} \ni f_{kp}\big(\tilde{\Vec{h}}_{v}^l,\tilde{\Vec{h}}_{u_i}^l\big)
    = \tilde{\Vec{h}}_{v}^l \otimes \tilde{\Vec{h}}_{u_i}^l\;.
    \label{eqn:KProduct}
\end{align}

In essence, the Kronecker product on $\tilde{\Vec{h}}_{v}^l$ and $\tilde{\Vec{h}}_{u_i}^l$ will enable us to benefit from the correlation information among the center node $v$ and its neighbors. We
aggregate the correlation among all the neighbors using $f_{\textrm{agg}}(\cdot)$ (\emph{i.e}\onedot} \def\Ie{\emph{i.e}\onedot, summation)
into a single vector of dimensionality $C_{h1}C_{h2} $, as:
\begin{align}
f_{\textrm{agg}}(\{\tilde{\Vec{h}}_{u_i}^l\}) = \sum_{i=1}^N f_{kp}\big(\tilde{\Vec{h}}_{v}^l,\tilde{\Vec{h}}_{u_i}^l\big)\;.
\end{align}
Finally, we pass the aggregated information to a linear mapping $\Mat{W}_{vu}^l \in \mathbb{R}^{C_{p} \times C_{h1}C_{h2}}$ and obtain the output of the FOG module as

\begin{align}
\Mat{p}_{v}^l=f_{FOG}(\Mat{h}_{v}^{l-1},\{\Mat{h}_{u_i}^{l-1}\})=\Mat{W}_{vu}^lf_{\textrm{agg}}(\{\tilde{\Vec{h}}_{u_i}^l\}).
\end{align}
For a plain FOG model, the final output $\Mat{h}_v^l \in \mathbb{R}^{C_{q}}$ is obtained as:

\begin{align}
\Mat{h}_{v}^l= \relu(\Mat{p}_{v}^l).
\end{align}

The FOG has the ability to improve a base GNN module by adding additional second-order information once combined with it. Given a base GNN module with functionality $f_{base}^l$, we can also attain a representation for node $v$ as
\begin{align}
 \mathbb{R}^{C_{q}} \ni \Mat{q}_{v}^l=f_{base}^l(\Mat{h}_{v}^{l-1},\{\Mat{h}_{u_i}^{l-1}\}).
\end{align}

After concatenating $\Mat{p}_{v}^l$ and $\Mat{q}_{v}^l$ along the channel, and subsequently passing the result to an activation function $\phi(\cdot)$ that is used in the original base GNN, the final output $\Mat{h}_v^l \in \mathbb{R}^{C_{out}}$ is obtained as:

\begin{align}
\Mat{h}_{v}^l= \phi\big(\concat(\Mat{p}_{v}^l,\Mat{q}_{v}^l)\big),
\label{eq:hv}
\end{align}
where $C_{out}=C_{p}+C_{q}$.

As Equation \ref{eq:hv} shows, with a minimal amount of changes by concatenating $\Mat{p}_{v}^l$ and $\Mat{q}_{v}^l$, the FOG module can be integrated into most existing GNNs thereby introducing correlation information boosting the performance. In this paper, we introduced the FOG module into five state-of-the-art modules including GCN, GAT, GatedGCN, GIN, and GraphSAGE. Furthermore, we also evaluate FOG with a 2-layer GNN as proposed by \cite{garcia2018fewshot} on a few-shot learning task.

\section{Experiments}

In this section, most experiments are conducted across various datasets based on the benchmarking procedure proposed by \cite{dwivedi2020benchmarking}. This benchmark covers most applications of GNNs, \emph{i.e}\onedot} \def\Ie{\emph{i.e}\onedot, graph pattern recognition, semi-supervised graph clustering, graph regression, and edge classification. The five aforementioned GNN baselines reported by Dwivedi \emph{et al}\onedot are compared with their FOG counterparts, along with a FOG-only model, under similar training protocols as in \cite{dwivedi2020benchmarking}. By introducing FOG to a GNN based few-shot learning problem proposed by Garcia and Bruna \cite{garcia2018fewshot}, we explore the possibility of applying FOG on a computer vision task. Furthermore, three more experiments are conducted in ablation study and further discussion to demonstrate the parameter-reducing potential, and limitation of FOG.

\subsection{Datasets}

\noindent{\textbf{SBM PATTERN and CLUSTER.}} We use the SBM datasets, produced by the stochastic block model, for graph pattern recognition and semi-supervised graph clustering tasks. These two datasets are proposed by \cite{dwivedi2020benchmarking}. The goal of the SBM PATTERN set is to identify a fixed graph pattern embedded in a large graph. This set comprises 10K items in the train set, 2K in the validation set and 2K in the test set. Each graph has on average 117.47 nodes and 2 classes. The SBM CLUSTER is used to evaluate the performance of the model on a semi-supervised clustering task. Given one prior known node label per class, the model learns to gather nodes that belong to the same class according to their connectivity. The number of graphs are 10K for train, 1K for validation, and 1K for test in this dataset. The average number of nodes in each graph is 117.20 and the number of classes is 6.

\noindent{\textbf{ZINC.}} The ZINC dataset is used to regress the molecular constrained solubility~\cite{ZINC_data}. The number of train, validation and test graphs are 10K, 1K and 1K respectively, with each graph containing 23.16 nodes on average. For each graph, the node features are the type of atoms and edge features are type of bonds.

\noindent{\textbf{TSP.}} We employ the TSP dataset generated by \cite{dwivedi2020benchmarking} to evaluate the edge classification performance of our method. The ability of the algorithm to solving NP-hard combinatorial optimization problems are evaluated on this dataset. The node feature represents the coordinates of a node in a unit square. The train, validation and test sets are split into 10K, 1K and 1K graphs, respectively. Each graph has a different number of nodes. The average number is 275.76.

\noindent{\textbf{MiniImageNet.}}
In our experiments, miniImageNet proposed by \cite{miniImageNet} is used for a few-shot learning task. This dataset contains 100 classes and 600 images for each class. Following \cite{miniImageNet_split}, we use a 64/16/20 split for training/validation/testing on 5-way 1-shot and 5-way 5-shot tasks.

\noindent{\textbf{IMDB-MULTI.}}
IMDB-MULTI is a graph classification benchmark proposed by Yanardag and Vishwanathan \cite{DeepGraphKernels}. In this social network dataset, each actor/actress' ego-network forms a graph that represents one of three genres. Actors/actress are represented as nodes and connected if they performed in the same movie. There are 1500 graphs in this dataset.

\subsection{Implementation and Evaluation}  \label{Implementation}

To verify the superior performance of our proposed FOG module, we evaluate FOG against various baselines mentioned in \textsection~\ref{sec:structure}. Empirical results reveal that the FOG module brings a significant performance gain over the baseline GNNs, with a fewer number of parameters. This observation suggests that the FOG module indeed benefits from the feature generated by the correlation feature space and non-linearity.

For each dataset, the GNN baseline and its FOG counterpart share the same training protocol. To thoroughly verify the effectiveness of our proposed method, if not otherwise mentioned, we used a grid search to find the optimized learning rate in $\{1e^{-2},5e^{-3},1e^{-3},5e^{-4}\}$ and weight decay in $\{1e^{-3},1e^{-6},0\}$, and evaluated the network 10 times using different random seeds, more than that in \cite{dwivedi2020benchmarking}. The Adam optimizer is used in all tasks with $\beta_1=0.9$, and $\beta_2=0.999$. In order to verify that the performance gain indeed comes from our proposed algorithm, the number of parameters of the FOG-only model and FOG-equipped GNN is similar to the baseline GNN. All GNNs evaluated on \cite{dwivedi2020benchmarking} use residual connections \cite{He2016ResNet}, and batch normalization \cite{Ioffe2015BN}. We omit the self loop in the input graphs across all experiments. We use the PyTorch~\cite{Pytorch} deep learning package to implement our algorithm based on the code provided by \cite{dwivedi2020benchmarking}. All experiments are trained on an Nvidia Tesla V100 16GB GPU. By default, 2 layers of a GNN module are used on miniImageNet and 4 layers are used on the other datasets. The detailed architectures and hyper-parameter settings are provided in the supplementary material.

\vspace{2pt}
\noindent{\textbf{SBM PATTERN and CLUSTER.}} The patience value is set to 5. After 5 epochs with no improvement of the loss, the learning rate will be reduced by a factor of 2. The training progress will stop when the learning rate is smaller than $1e^{-5}$.  All final node features are passed to a 3-layer multilayer perceptron (MLP) including a classification layer that uses the cross-entropy loss to obtain a prediction for each node. The performance metric is the average accuracy between predicted and ground-truth labels.

The evaluation on the SBM dataset is shown in Table~\ref{table:SBM_PATTERN} and \ref{table:SBM_CLUSTER}. In the graph pattern recognition task, the model with only the FOG module surpasses all architectures by a maximum of 21.783\% in terms of accuracy when comparing to GCN (see Table~\ref{table:SBM_PATTERN}). Introducing FOG to GCN, GAT, GatedGCN, and GraphSAGE provide boost to the original structures. However, a performance drop is observed when combining FOG with GIN. We conjecture that the way GIN adds the learnable weights in the COMBINE part conflicts with our FOG.

In the semi-supervised graph clustering task, our FOG module also shows its potential to bring performance gains across different baselines (see Table~\ref{table:SBM_CLUSTER}). Furthermore, plugging in the FOG module consistently improves the accuracy across all baselines and pushes all of them even higher than the FOG-only model and corresponding baseline model. The FOG module improves the accuracy of GCN, GAT, GatedGCN, GIN, and GraphSAGE by 7.334\%, 3.089\%, 4.079\%, 3.624\%, and 9.689\% respectively.

\begin{table}[!ht]
\caption{Performance on the SBM PATTERN test set (higher is better). \textbf{Bold}: the best model between the baseline GNN and the corresponding FOG-equipped GNN. \textbf{\textcolor{red}{Red}}: the best model overall.}
\begin{center}
\scalebox{1}{
\begin{threeparttable}
\begin{tabular}{l|c|c}
\hline
Model & \#Param & Acc(\%)$\pm$s.d.$\uparrow$ \\
\hline
FOG & 99,046 & \textbf{\textcolor{red}{85.663 $\pm$ 0.025}} \\

\hline
GCN & 100,923 & 63.880 $\pm$ 0.074 \\
GCN+FOG & 101,026 & \textbf{{85.663 $\pm$ 0.027}} \\

\hline
GAT & 109,936 & 75.824 $\pm$ 1.823 \\
GAT+FOG & 101,346 & \textbf{85.654 $\pm$ 0.023} \\

\hline
GatedGCN & 104,003 & 84.480 $\pm$ 0.122 \\
GatedGCN+FOG & 102,050 & \textbf{{85.454 $\pm$ 0.090}} \\

\hline
GIN & 100,884 & \textbf{85.590 $\pm$ 0.011} \\
GIN+FOG & 99,234 & 85.524 $\pm$ 0.029 \\

\hline
GraphSAGE & 101,739 & 50.516 $\pm$ 0.001 \\
GraphSAGE+FOG & 95,679 & \textbf{85.578 $\pm$ 0.061} \\

\hline
\end{tabular}
\end{threeparttable}
}
\end{center}\label{table:SBM_PATTERN}
\end{table}

\begin{table}[!ht]
\caption{Performance on the SBM CLUSTER test set (higher is better). \textbf{Bold}: the best model between the baseline GNN and the corresponding FOG-equipped GNN. \textbf{\textcolor{red}{Red}}: the best model overall.}
\begin{center}
\scalebox{1}{
\begin{threeparttable}
\begin{tabular}{l|c|c}
\hline
Model & \#Param & Acc(\%)$\pm$s.d. $\uparrow$ \\
\hline
FOG & 99,770 & 58.655 $\pm$ 0.974 \\

\hline
GCN & 101,655 & 53.445 $\pm$ 2.029 \\
GCN+FOG & 101,830 & \textbf{60.779$ \pm$ 0.262} \\
\hline
GAT & 110,700 & 57.732 $\pm$ 0.323 \\
GAT+FOG & 102,150 & \textbf{{60.821 $\pm$ 1.106}} \\

\hline
GatedGCN & 104,355 & 60.404 $\pm$ 0.419 \\
GatedGCN+FOG &  102,374 & \textbf{\textcolor{red}{64.483 $\pm$ 0.331}} \\

\hline
GIN & 103,544 & 58.384 $\pm$ 0.236 \\
GIN+FOG &  102,806 & \textbf{62.008 $\pm$ 0.591} \\

\hline
GraphSAGE & 102,187 & 50.454 $\pm$ 0.145 \\
GraphSAGE+FOG & 96,171 & \textbf{60.143 $\pm$ 0.414} \\
\hline
\end{tabular}
\end{threeparttable}
}
\end{center}\label{table:SBM_CLUSTER}
\end{table}

\noindent{\textbf{ZINC.}} The same training protocol as for SBM is used here, and the patience value is set to 10. Instead of classification, in ZINC we are targeting a regression task, where a 3-layer MLP is followed after the GNN's last layer to approximate the ground truth. The mean absolute error (MAE) between the predicted and the ground-truth constrained solubility is applied as a loss function, as well as the performance metric.

In the graph regression task, our FOG module improves over most baseline GNNs with respect to the MAE value by a large margin, shown in Table~\ref{table:zinc}. In particular, the GCN+FOG model improves 33.116\% over GCN and exceeds all baselines. Considering that the FOG-only model notably has a lower performance than most FOG-equipped baseline GNNs, the FOG module can provide more complementary information to baseline GNNs on this dataset. However, introducing FOG to GIN suffers a performance drop, which is similar to SBM PATTERN as mentioned above.

\vspace{2pt}
\noindent{\textbf{TSP.}} The following changes are made when adapting the SBM training protocol: (a) The patience value is set to 10. (b) The F1 score only considers the positive class for the performance metric. (c) Edge features are passed to a 3-layer MLP where the last layer is a classification layer. Cross-entropy loss is used for this edge classification task.

The edge classification task also benefits from our FOG module. As shown in Table~\ref{table:tsp}, our FOG module consistently improves over the baseline GNNs. For example, the GCN+FOG improves 9.206\% F1 over GCN. In addition, the best performance architecture, GatedGCN+FOG, outperforms the state-of-the-art baseline (\emph{i.e}\onedot} \def\Ie{\emph{i.e}\onedot, GatedGCN) by 2.351\% F1 score when using edge features.

\vspace{2pt}
\noindent{\textbf{MiniImageNet.}} The experiments on this dataset are based on the networks proposed by \cite{garcia2018fewshot}. One query image and its support set are formed as a fully-connected graph where each node is an image. Each architecture has two parts: (1) a 5-layer CNN generates a representation vector as a node feature. (2) a 2-layer GNN passes representations among nodes to predict the label of the query image among the images in the support set. We only concatenate FOG to the first GNN layer for the FOG-equipped version and replace the first GNN layer with FOG for the FOG-only version. All architectures in this task are trained four times with cross-entropy loss and four random seeds in an end-to-end fashion.

The evaluation results of 5-way 1-shot and 5-way 5-shot tasks are shown in Table~\ref{table:miniImageNet}. The original GNN can still gain higher performance after concatenating with FOG.

\begin{table}[!ht]
\caption{Performance on the ZINC test set (lower is better). ~\textbf{Bold}: the best model between the baseline GNN and the corresponding FOG-equipped GNN. \textbf{\textcolor{red}{Red}}: the best model overall.}
\begin{center}
\scalebox{1}{
\begin{threeparttable}
\begin{tabular}{l|c|c}
\hline
Model & \#Param & MAE$\pm$s.d.$\downarrow$ \\
\hline
FOG & 101,668 & 0.362 $\pm$ 0.016 \\

\hline
GCN & 103,077 & 0.459 $\pm$ 0.006 \\
GCN+FOG & 102,809 & \textbf{0.307 $\pm$ 0.013}  \\

\hline
GAT & 102,385 & 0.475 $\pm$ 0.007 \\
GAT+FOG & 105,305 & {\textbf{0.333 $\pm$ 0.016}} \\

\hline
GatedGCN & 105,735 & 0.435 $\pm$ 0.011 \\
GatedGCN+FOG & 103,633 & \textbf{0.318 $\pm$ 0.022} \\

\hline
GatedGCN-E\tnote{*} & 105,875 & 0.375 $\pm$ 0.003 \\
GatedGCN-E+FOG\tnote{*} & 103,761 &
\textcolor{red}{\textbf{0.271 $\pm$ 0.030}} \\

\hline
GIN & 103,079 & \textbf{0.387 $\pm$ 0.015} \\
GIN+FOG & 102,189 & 0.401 $\pm $0.020  \\

\hline
GraphSAGE & 94,977 & 0.468 $\pm$ 0.003 \\
GraphSAGE+FOG & 94,477 & \textbf{0.317 $\pm$ 0.011} \\
\hline
\end{tabular}
\begin{tablenotes}
\item[*] -E stands for using the molecule bond type as edge feature.
\end{tablenotes}
\end{threeparttable}
}
\end{center}
\label{table:zinc}
\end{table}

\begin{table}[!ht]
\caption{Performance on the TSP test set (higher is better). \textbf{Bold}: the best model between the baseline GNN and the corresponding FOG-equipped GNN. \textbf{\textcolor{red}{Red}}: the best model overall.}
\begin{center}
\scalebox{1}{
\begin{threeparttable}
\begin{tabular}{l|c|c}
\hline
Model & \#Param & F1$\pm$s.d. $\uparrow$\\
\hline
FOG & 96,386 & 0.677 $\pm$ 0.004 \\

\hline
GCN & 95,702 & 0.630 $\pm$ 0.001 \\
GCN+FOG & 93,465 & \textbf{0.688 $\pm$ 0.007} \\

\hline
GAT & 96,182 & 0.671 $\pm$ 0.002 \\
GAT+FOG & 96,350 & \textbf{0.713 $\pm$ 0.002} \\

\hline
GatedGCN & 97,858 & 0.791 $\pm$ 0.003 \\
GatedGCN+FOG & 95,456 & \textbf{0.822 $\pm$ 0.002} \\

\hline
GatedGCN-E\tnote{*} & 97,858 & 0.808 $\pm$ 0.003 \\
GatedGCN-E+FOG\tnote{*} & 95,456 & \textbf{\textcolor{red}{0.827 $\pm$ 0.002}} \\

\hline
GIN & 99,002 & 0.656 $\pm$ 0.003 \\
GIN+FOG & 94,046 & \textbf{0.706 $\pm$ 0.010} \\

\hline
GraphSAGE & 99,263 & 0.665 $\pm$ 0.003 \\
GraphSAGE+FOG & 97,007 & \textbf{0.689 $\pm$ 0.002} \\

\hline
\end{tabular}
\begin{tablenotes}
\item[*] -E stands for using the pairwise distance as an edge feature.
\end{tablenotes}
\end{threeparttable}
}
\end{center}\label{table:tsp}
\end{table}

\begin{table}[!ht]
\caption{Performance on the miniImageNet test set with 95\% confidence intervals (higher is better). \textbf{\textcolor{red}{Red}}: the best model overall. \#Param: the number of parameters in GNN parts}
\begin{center}
\scalebox{0.98}{
\begin{threeparttable}
\begin{tabular}{l|c|c|c}
\hline
\multirow{2}{*}{Model} & \multirow{2}{*}{\#Param} & 5-way 1-shot & 5-way 5-shot\\
\cline{3-4}
& &Acc (\%) $\uparrow$&Acc (\%) $\uparrow$\\
\hline
FOG & 312,282 & 50.70 $\pm$ 0.69  & 65.64 $\pm$ 0.59 \\
\hline
GNN & 335,994 & 50.33 $\pm$ 0.36  & 66.41 $\pm$ 0.63 \\
GNN+FOG & 323,760 & \textbf{\textcolor{red}{50.71 $\pm$ 0.55}}  & \textbf{\textcolor{red}{66.77 $\pm$ 0.49}} \\
\hline
\end{tabular}
\end{threeparttable}
}
\end{center}\label{table:miniImageNet}
\end{table}

\subsection{Ablation Study}
\noindent{\textbf{Dimensionality of hidden layers.}} According to the notable boost when introducing FOG into the state-of-the-art module, it demonstrates the ability of FOG reducing the total number of parameters of the original architectures while still maintaining the performance. To demonstrate this point, we choose the simplest architecture: GCN, and the best performing architecture: GatedGCN. Their FOG-equipped counterparts with different number of parameters are evaluated on ZINC by using the same training protocol as in \textsection~\ref{Implementation}. All models use the same learning rate and weight decay found via previous experiments. Their number of parameters are roughly divided from 25\% to 100\% by adjusting hidden layer dimensions according to their baseline models.

As Table \ref{table:DimStudy} shows, all variations are better than their corresponding baseline models. For the best performing baseline on ZINC, FOG boosts the performance by 11.733\% compared to GatedGCN by only using about 25\% of the parameters. Both 25\% architectures are still better than the other baseline models in Table \ref{table:zinc}.

\begin{table}[!ht]
\caption{Performance of GCN, GatedGCN, and their corresponding FOG-equipped variants with different number of hidden layer dimensions on the ZINC test set (lower is better).}
\begin{center}
\scalebox{0.85}{
\begin{threeparttable}
\begin{tabular}{l|c|c|c}
\hline
Model & \#Param & \#Param ratio & MAE$\pm$s.d. $\downarrow$\\
\hline
GCN & 103,077 & 100\% & 0.459 $\pm$ 0.006 \\
\hline
\multirow{4}{*}{GCN+FOG}
 & 102,809 & 100\% & 0.307 $\pm$ 0.013  \\
 & 77,278 & 75\% & {0.322 $\pm$ 0.015}  \\
 & 50,547 & 50\% & {0.337 $\pm$ 0.021}  \\
 & 25,847 & 25\% & {0.352 $\pm$ 0.025}  \\
\hline
GatedGCN-E\tnote{*} & 105,875 & 100\% & 0.375 $\pm$ 0.003 \\
\hline

\multirow{4}{*}{\shortstack[l]{GatedGCN-E \\ +FOG\tnote{*}}}
 & 103,761 & 100\% & 0.271 $\pm$ 0.030 \\
 & 79,165 & 75\% & 0.287 $\pm$ 0.029  \\
 & 49,835 & 50\% & 0.307 $\pm$ 0.016  \\
 & 26,909 & 25\% & 0.331 $\pm$ 0.031  \\
\hline
\end{tabular}
\begin{tablenotes}
\item[*] -E stands for using the pairwise distance as edge feature.
\end{tablenotes}
\end{threeparttable}
}
\end{center}\label{table:DimStudy}
\end{table}

\subsection{Further Discussion}

After demonstrating the strengths of our FOG, we address some limitations here. As discussed above, FOG enjoys the benefits of the node's feature, meanwhile, it is also constrained when the node's feature is absent or uninformative. Therefore, we do further study on the behavior of our FOG on those datasets.

Other techniques, in comparison to ours, focus on graph structural information while ignoring the correlation on feature space. Among them, GIN and GatedGCN are the best architectures on ZINC regardless of using edge feature or not. As a result, we assess both of them, as well as their FOG-equipped versions, alongside a FOG-only design.

Following the setting of \cite{xu2018powerful}, we set all node features to the uninformative value 1 on IMDB-MULTI dataset, where 10-fold cross-validation and only one random seed is applied. Same patience value, learning rate reduction factor, and minimum learning rate are set as experiments on SBM dataset, and a 3-layer MLP is used to predict labels by using final node features. To show the importance of the nodes' feature, we replace the nodes' feature vector on ZINC dataset with single value 1. The other experimental setting is the same as Table~\ref{table:zinc}.

Table \ref{table:Limitation} illustrates that comparing to state-of-the-art models, the notable performance drop when only applying FOG on graphs without node feature. However, GatedGCN+FOG achieves better results comparing to the baseline on both two datasets. This implies FOG can still provide complementary information for the base GNNs while independent FOG may struggle on extracting correlation information from graph structure. The consistent performance drop while concatenating FOG with GIN suggests that the learnable parameter $\epsilon$ in GIN may break the correlation between the central node and its neighbors, which makes these two modules are incompatible in most scenarios. Generally, all networks suffer large performance drop when comparing to Table \ref{table:zinc}. This suggests original node features and edge features have important contribution to this kind of tasks.

\begin{table}[!ht]
\caption{Performance on the ZINC without node feature test set (lower is better) and IMDB-MULTI validation set (higher is better). ~\textbf{Bold}: the best model between the baseline GNN and the corresponding FOG-equipped GNN. \textbf{\textcolor{red}{Red}}: the best model overall.}
\begin{center}
\scalebox{0.76}
{
\begin{tabular}{l|cc|cc}
\hline
\multirow{2}{*}{Model} & \multicolumn{2}{c|}{ZINC w/o} & \multicolumn{2}{c}{IMDB-M} \\
\cline{2-5}
                      & \#Param        & MAE$\pm$s.d.$\downarrow$  & \#Param      & Acc(\%)$\pm$s.d.$\uparrow$         \\
\hline
FOG          & 101,668  & 1.308 $\pm$ 0.017 & 33,017 & 46.067 $\pm$ 4.848    \\
\hline
GatedGCN     & 105,735  & 1.296 $\pm$ 0.024 & 34,663 & 50.933 $\pm$ 4.123    \\
GatedGCN+FOG & 103,633  & \textbf{1.283 $\pm$ 0.014} & 33,303 & \textcolor{red}{\textbf{52.067 $\pm$ 3.508}}    \\
\hline
GIN          & 103,079  & \textcolor{red}{\textbf{1.277 $\pm$ 0.016}} & 35,411 & \textbf{48.400 $\pm$ 4.716}    \\
GIN+FOG      & 102,189  & 1.293 $\pm$ 0.029 & 34,805 & 47.933 $\pm$ 3.521    \\
\hline
\end{tabular}
}
\end{center}\label{table:Limitation}
\end{table}
\section{Conclusion}

We have presented a new aggregation module, namely FOG, which introduces the feature correlation between the central node and its neighbors into the central node's feature representation. We, firstly, summarize the way of how existing GNNs work and generalize them into the same presentation. Distinguishing from existing methods, our method is compatible with most existing methods so that it can be inserted on top of those GNNs. Furthermore, our extensive experiments on different datasets have shown that FOG is able to help the GNNs to get more discriminative features and achieve better performance in various tasks, e.g. graph pattern recognition, node classification, graph regression, and edge classification. Furthermore, we also provide a thorough analysis of the limitation and applicability of our method. In the future, we will explore other types of function which is sensitive to the change of central node, and study on how it affects the GNNs.

{\small
\bibliographystyle{ieee_fullname}


\section{Introduction}
The concept of simplicial partitions is common and useful in Finite element analysis~\cite{segerlind1991applied, bhavikatti2005finite}. Simplicial partition tends to cut the space being searched into regularised chunks, finding the optimal solution to the objective function over the whole space by iteration, e.g., branch-and-bound~\cite{lawler1966branch}. In this process, it is particularly important what geometry the simplex can maintain, as this can seriously interfere with the efficiency of the solution. For example, if, after enough partitions, the simplex degenerates approximately to a hyperplane, there is no guarantee that the theoretical optimal point of the objective function will belong to any simplex (it may be wrapped in many or even an infinite number of simplices). This uncertainty about the region to which the solution belongs can make the solution to the optimization problem significantly more expensive.

There is already a range of widely adopted conditions to constrain the regularity of simplicial partitions. In~\cite{brandts2009equivalence}, the authors summarized three kinds of equivalent conditions, which are called balled conditions. Meanwhile, there are also other conditions such as minimum angle conditions as in~\cite{ZLAMAL1968}. People have already demonstrated the minimum angle condition is equivalent to the three kinds of balled conditions above in the 3-dimensional cases. In the high-dimensional cases, authors~\cite{brandts2011generalization} developed a generalized version of the minimum angle condition.

\section{Problem Formulation}
In this paper, we directly quote one of the most widely-used balled conditions to define the regularity, the other two balled condition~\cite{ZLAMAL1968} are both equivalent.

\begin{assumption}{\textbf{(Regularity assumption~\cite{brandts2009equivalence, ZLAMAL1968, brandts2011generalization})}}
For each simplex $S$ in simplicial partitions, there exists a constant $\eta$ such that
\begin{equation}
    \begin{aligned}
    vol(S) \geq \eta {h(S)}^{d}.
    \end{aligned}
\end{equation}
Here $vol(S)$ denotes the volumn of simplex $S$, $h(S)$ denotes the longest edge of $S$, and $d\geq 2$ is the dimension.

\label{ass}
\end{assumption}

Roughly speaking, the regularity assumption guarantees the simplex would not degenerate to the hyper-plane, or else $\lim\limits_{vol(S)\rightarrow 0} \frac{vol(S)}{{h(S)}^d} = 0$. In other words, $\frac{vol(S)}{{h(S)}^d}$ can be higher when the simplex ``seems to be regular'', namely each edge keeps the same length. In addition, the simplicial partitions during partitioning are denoted as $\mathcal{S}_0, \mathcal{S}_1, \mathcal{S}_2...$. Our problem can be summarized as follows:

\emph{what is the maximum intersection number of regular simplicial partitions? In other words, for an arbitrary point in $\mathcal{S}_0$, what is the maximum number of simplices it can be affiliated with during partitioning?}

\section{Main result}
In this part, we present our main result as follows:

\begin{theorem}
Suppose that Ass.~\ref{ass} holds. Each point in $\mathcal{S}_0$ is included within at most $\frac{1}{\eta}\left(\frac{2e \pi}{ d}\right)^{\frac{d}{2}}$ simplices.

\end{theorem}

\begin{proof}
For $\gamma_0 \in \mathcal{S}_0$, we construct a ball $\mathcal{B}(\gamma_0, r)$. We use $A(\cdot)$ to denote the surface area of the sphere:
\begin{equation}
    \begin{aligned}
    A\left(\mathcal{B}\left(\gamma_0, r\right) \cap \mathcal{S}_0\right)=\sum_{S \in \mathcal{S}_k, \gamma_0 \in S} A\left(\mathcal{B}\left(\gamma_0, r\right) \cap {S} \right).
    \end{aligned}\label{original}
\end{equation}
On the one hand, the LHS of Eqn.~\ref{original} can be upper bounded as:
\begin{equation}
    \begin{aligned}
    A\left(\mathcal{B}\left({\gamma_0}, r\right) \cap S_0\right) \leq A\left(\mathcal{B}\left({\gamma_0}, r\right)\right)=\frac{2 \pi^{\frac{ d}{2}}}{\Gamma\left(\frac{ d}{2}\right)} r^{d-1}<+\infty .
    \end{aligned}\label{A_S_0}
\end{equation}
On the other hand, we calculate the RHS of Eqn.~\ref{original}. To solve it, we take
advantage of the following integral (we take $\gamma_0$ as the origin):
\begin{equation}
    \begin{aligned}
    \int_{\mathcal{W}_S \gamma \geq 0} e^{-\|\gamma\|^2} d \gamma.
    \end{aligned}
\end{equation}
Here for each term on the right side, the sphere of the ball is cut by certain facets of each S, whose
normal vector is denoted as a set $\mathcal{W}_S$, whose each row denotes a $1 * d$ normal vector. Without loss of generation, for any facets, we assume that its normal vector points to the remaining
supporting vector, namely its inner product is positive.

Here $\| \cdot \|$ also denotes the Euclidean norm. If we use the polar coordinates, we can get a new expression by the differential element method:

\begin{equation}
    \begin{aligned}
    \int_{\mathcal{W}_S \gamma \geq 0} e^{-\|\gamma\|^2} d \gamma=\int_{\mathcal{W}_S \gamma \geq 0} d \Omega \int_0^{+\infty} e^{-l^2} l^{ d-1} d l=\frac{A\left(\mathcal{B}\left(\gamma, r\right) \cap S\right)}{r^{ d-1}} \int_0^{+\infty} e^{-l^2} l^{ d-1} d l.
    \end{aligned}\label{A_S}
\end{equation}
According to Eqn.~\ref{A_S_0}-\ref{A_S}, we have
\begin{equation}
    \begin{aligned}
A\left(\mathcal{B}\left(\gamma_0, r\right) \cap S\right) &=\frac{2 \int_{\mathcal{W}_S \gamma \geq 0} e^{-\|\gamma\|^2} d \gamma}{\Gamma\left(\frac{d}{2}\right)} r^{d-1} \\
\forall k, \frac{A\left(\mathcal{B}\left(\gamma_0, r\right) \cap S\right)}{A\left(\mathcal{B}\left(\gamma_0, r\right) \cap \mathcal{S}_0\right)} & \geq \frac{\int_{\mathcal{W}_S \gamma \geq 0} e^{-\|\gamma\|^2} d \gamma}{\pi^{\frac{d}{2}}}.
    \end{aligned}
\end{equation}
Hence we only need to prove the integral is lower bounded by a constant above zero. We will do this by extracting a sub-space from $\mathcal{W}_S \gamma \geq 0$, which is easy to be integrated. Specifically, we consider a subspace which is an affine transformation on $\mathcal{W}_S \gamma \geq  0$. We introduce the diameter of simplex $S$ as $\operatorname{dia}(S) = \max _{s_1, s_2 \in S}\left\|s_1-s_2\right\|$.

\begin{equation}
    \begin{aligned}
\int_{\mathcal{W}_S \gamma \geq 0} e^{-\|\gamma\|^2} d \gamma & \geq \int_{\gamma=t \gamma^{\prime}, \gamma^{\prime} \in S} e^{-\|\gamma\|^2} d \gamma \quad(\forall t>0, t \text { is arbitrarily chosen }) \\
&=\int_{\gamma^{\prime} \in S} t^{d} e^{-t^2\left\|\gamma^{\prime}\right\|^2} d \gamma^{\prime} \\
& \stackrel{*}{\geq } t^d \operatorname{Vol}(S) e^{-t^2 \operatorname{dia}(S)^2} \\
& \stackrel{* *}{\geq} \eta t^{ d} h(S)^{ d} e^{-t^2 \operatorname{dia}(S)^2}
\end{aligned}
\end{equation}
$*$ is due to $\forall \gamma^{\prime} \in S$, we have $\left\|\gamma^{\prime}\right\| \leq \operatorname{dia}(S)$, since $\gamma_0$ is chosen as the origin. $* *$ is due to Ass.~\ref{ass}. Additionally, we further show that in the above Formulation, $h(S)=\operatorname{dia}(S)$. Namely, the longest edge of simplex always serves as the diameter. It is equal to prove ($S^i$ denotes the supporting vector):
\begin{equation}
    \begin{aligned}
\operatorname{dia}(S) &=\max _{s_1, s_2 \in S}\left\|s_1-s_2\right\| \quad\left(s_2=\sum_i \lambda_i S^i, \lambda_i \in[0,1]\right) \\
&=\max _{s_1, s_2 \in S}\left\|\left(\sum_i \lambda_i\right) s_1-\sum_i\left(\lambda_i S^i\right)\right\| \\
&=\max _{s_1, s_2 \in S}\left\|\sum_i \lambda_i\left(s_1-S^i\right)\right\| \\
& \leq \max _{s_1 \in S} \max _i\left\|s_1-S^i\right\| \\
& \stackrel{*}{\leq} \max _{i, j}\left\|S^j-S^i\right\| \leq h(S).
\end{aligned}
\end{equation}
$*$ is due to we also do the expansion on $s_1$, namely $s_1=\sum_i \lambda_i^{\prime} S^i, \lambda_i^{\prime} \in[0,1]$. On the other hand, we have $h(S) \leq \max _{s_1, s_2 \in S}\left\|s_1-s_2\right\|=\operatorname{dia}(S)$ by definition. Thus $\operatorname{dia}(S)=h(S)$. Hence
\begin{equation}
    \begin{aligned}
    \forall t, \int_{\mathcal{W}_S \boldsymbol{\gamma} \geq 0} e^{-\|\gamma\|^2} d \boldsymbol{\gamma} \geq \eta(t d i a(S))^{d} e^{-\left(t \operatorname{dia}(S)^2\right)}.
    \end{aligned}
\end{equation}

Due to the arbitrary of $t$, we have
\begin{equation}
    \begin{aligned}
    \int_{\mathcal{W}_S \boldsymbol{\gamma} \geq 0} e^{-\|\gamma\|^2} d \boldsymbol{\gamma} \geq \eta \max _x x^{d} e^{-x^2}=\left.\eta x^{d} e^{-x^2}\right|_{x=\sqrt{\frac{d}{2}}}=\eta(\frac{d}{2})^{\frac{d}{2}} e^{- \frac{d}{2}}.
    \end{aligned}
\end{equation}
Finally, we have
\begin{equation}
    \begin{aligned}
    \forall k, \frac{A\left(\mathcal{B}\left(\gamma, r\right) \cap S\right)}{A\left(\mathcal{B}\left(\gamma, r\right) \cap S_0\right)} \geq \eta\left(\frac{d}{2e \pi}\right)^{\frac{d}{2}}, \text{the~intersection~number~} N \leq \frac{1}{\eta}\left(\frac{2e \pi}{ d}\right)^{\frac{d}{2}}<+\infty.
    \end{aligned}
\end{equation}

\end{proof}
In future work, I will further explore the tight upper bound of the intersection number of the regular simplicial partitions.

\section{Acknowledgments}
This note is my additional exploration after the work~\cite{zhihengproxy} and is inspired by the discussion with my professor Yuhao Wang.

\bibliographystyle{unsrt}


\section{Introduction}
Future wireless networks feature the use of large antenna arrays and wide-band radio access techniques in high radio frequency range, especially in the millimeter-wave~(mmWave) frequencies.
3GPP's 5G New Radio~(NR) in Frequency Range 2~(FR2) and IEEE 802.11ay  are two representative standards for mmWave communications.
Large number of antennas and signal bandwidth adopted in these mmWave networks not only increase the communication capacity,
but also equip the networks with  radio sensing and positioning functions of high accuracies. On the other hand, the built-in localization functionality facilitate various context-aware applications including Internet-of-Things, intelligent transportation system, crowd sensing, assets tracking and advanced radio resource management~(RRM).

The performances of a mmWave joint communication and localization~(JCL) system heavily depends on the site-specific mmWave channel characteristics, including LOS condition, powers of multi-path components~(MPC), angular and temporal distributions of MPCs and Doppler shifts. On the one hand, mmWave communication relies on line-of-sight~(LOS) or prominent reflection paths for beamforming or multiple-input-multiple-output~(MIMO) transmission, and the channel state information~(CSI) needs to be estimated for designing the baseband pre-coder and combiner. On the other hand, various geometrical mmWave localization algorithms also rely on the accurate estimations of the direction-of-arrivals~(DOAs) and/or delays for prominent MPCs. For fingerprinting-based localization methods, channel spatial consistency is important, which describes the smooth variations of channels when the user equipment~(UE) moves in the geographic space.
In order to effectively support the design and evaluation of a mmWave JCL system, accurate network-level channel characterization and modeling considering  massive user equipments~(UEs) are of great importance.

According to how the clusters of MPCs are generated, mmWave channel models can be categorized as stochastic, deterministic and their hybrid ones~\cite{Lim2020,COMST2018}. Stochastic models, including the widely used geometry-based stochastic channel model~(GSCM)~\cite{COST2100,38901,QuaDRiGa2012}, use randomly dropped scatters to generate MPC clusters, they are suitable for evaluating multi-antenna communication performances, but cannot be used directly for designing and evaluating localization techniques. Deterministic channel models are based on detailed site-specific  electromagnetic environment information, using either full-wave solutions such as method of moments~(MoM), finite-difference time domain~(FDTD), or asymptotic technique like geometric optics~(GO) and uniform theory of diffraction~(UTD) to predict the radio channels. As compared, a hybrid model~\cite{Lim2020} uses a simplified geometric description of the propagation environment and a ray-tracing method to generate realistic large-scale spatial channel properties, and adds some stochastic factors to model the small-scale fading effects.

There are several mmWave channel simulators available for academia and industrial research, including  QuaDRiGa~\cite{QuaDRiGa2012}, NYUSIM~\cite{NYU2018}, NIST Q-D Realization~\cite{qd2020}, Altair WinProp~\cite{Winprop} and Remcom Wireless InSite~\cite{alkhateeb2019deepmimo}. QuaDRiGa and NYUSIM are based on GSCM, while Q-D Realization, WinProp and Wireless InSite are based on ray tracing.
QuaDRiGa extends the popular GSCM channel model with new features that allow the generation of channel traces with temporal evolution and scenario transitions. It dose not use an exact geometric representation of the environment but distributes the positions of scatters randomly in the simulated scenario.
NYUSIM provides an accurate rendering of actual channel impulse responses in both delay and spatial spaces based on parameters derived from measurement data.
The open-source NIST Q-D Realization software implements ray tracing to capture the deterministic specular rays, and integrate the deterministic
channel description with stochastic models for diffuse rays. Its ray tracing is based on backtracking algorithm and the method of images and has high computational complexities with a larger number of facets in the simulated scenario, and diffraction and scattering are not implemented.
WinProp is a commercial wireless propagation and radio network planning software, and supports reflection, diffraction and mobile
scattering in the simulation. It employs techniques including the dimension reduction, space partitioning, intelligent ray tracing~(IRT) and dominant path model~(DPM)~\cite{COMST2018} to accelerate the simulation and can be used in a large-scale scenario with thousands of facets.
Wireless Insite is another popular commercial software uses ray tracing coupled with empirical models for a frequency range from 50 MHz to 100 GHz. It employs dimension reduction and ray launching acceleration algorithms, as well as GPU and multi-threaded CPU hardware acceleration.

This paper presents an open-source mmWave network-level hybrid channel simulator~(OmniSIM) for JCL research. It combines a customized deterministic ray-tracing model with stochastic small-scale modeling methods to generated UE-location-dependant channel responses. It models the diffuse reflections by building surfaces using GO, the diffractions by wedges using UTD and the scattering effects by trees using the radiative energy transfer~(RET) function. The core part of OmniSIM is a fast shooting-bouncing rays~(FSBR) algorithm which can find propagation paths between BS and massive UE locations with low computation complexities. OmniSIM is available at https://github.com/dengjunquan/OmniSIM.

\section{MmWave Channel Model}

We consider a generic mmWave orthogonal frequency-division multiplexing~(OFDM) baseband channel
model, assuming a total bandwidth of $W = N \Delta$ with subcarrier spacing $\Delta$, the frequency-domain channel response between a transmitter~(TX)
with $N_T$ antennas and a receiver~(RX) with $N_R$ antennas at subcarrier $n\in \{0,\cdots,N-1\}$ and symbol duration $s \in \{0,\cdots,S-1\}$ is~\cite{Robert2016,Heath2018_ChEst}
\begin{align}
\mb{H}_{n,s}\! =\! \sum_{l=1}^{L} \alpha_l p(sT\!-\!\tau_l) \bm{a}_{r}(\bm{\theta}_{l})\bm{a}_{t}^{\mathsf{H}}(\bm{\phi}_{l})e^{j 2 \pi ( s T  \nu_l-n \Delta \tau_{l})}, \label{eq:ChannelGeneric}
\end{align}
where $L$ denotes the number of propagation paths,  $\alpha_l$ is a complex channel gain for the $l$-th path, $T$ denotes the
symbol duration, $p(\tau)$ is a filter that includes the effects
of pulse-shaping and other low-pass filtering evaluated at $\tau$. Furthermore,
$\bm{a}_{r}(\bm{\theta}) \in \mathbb{C}^{N_{\text{R}}}$ is the RX antenna array response as a function of the {DoA} $\bm{\theta}\in \mathbb{R}^2$ in azimuth and elevation domains, $\bm{a}_{t}(\bm{\phi})\in \mathbb{C}^{N_{\text{T}}}$ is the TX array response as a function of the direction of departure~(DoD) $\bm{\phi}\in \mathbb{R}^2$. Finally, $\tau_l$ is the time of arrival~(ToA) and $\nu_l$ is the Doppler shift, related to the $l$-th path.

The channel models at mmWave differs from conventional sub-6GHz frequencies because of smaller
wavelengths. Diffraction is not significant due to the reduced Fresnel zone, scattering is higher as the wavelengths are comparable to effective roughness of radio reflectors and scatters, and the penetration losses are much larger. A large amount of channel measurement results have confirmed that MPCs for typical outdoor and indoor mmWave channels come with cluster structures in both the delay and angular domains~\cite{Haneda2014,Samimi2016,Cen2018,Charbonnier_TVT_2020}, and the channel power is dominated by LoS and/or specular reflection paths.

In a mmWave JCL system, the baseband RX signal is of the form
\begin{align}
    \bm{y}_{n,s} = \bm{W}_s\mb{H}_{n,s} \bm{x}_{n,s} + \bm{n}_{n,s}, \label{eq:RxSignal}
\end{align}
where  {$\bm{W}_s \in \mathbb{C}^{N_{\text{R}} \times M_{\text{R}}}$ is the RX combiner, using {$M_{\text{R}}\le N_{\text{R}}$} RF chains, $\bm{x}_{n,s} $ is the $s$-th radiated signal vector from the TX antenna array, with $\mathbb{E}\{\Vert \bm{x}_{n,s} \Vert^2\}=P/W$ where $P$ is the average transmit power, and $\bm{n}_{n,s}$ is noise after the combining. For channel estimation and localization purposes, the transmit signals $\bm{x}_{n,s}$ are generally known based on predefined pilots, and the channel $\mb{H}_{n,s}$ can be estimated via $\bm{y}_{n,s}$, $\bm{W}_s$ and a reconstruction algorithm. If the antenna array responses $\bm{a}_{r}(\bm{\theta})$, $\bm{a}_{t}(\bm{\phi})$ are known, it would be possible to estimate the DoAs, delays of dominant paths using MUSIC~\cite{MPCC2018} or other algorithms for positioning purpose. In the case that array responses are unknown, advanced machine learning~{ML} methods can be utilized for localization based on fingerprinting and a channel similarity metric~\cite{SupCon2022}.

\section{OmniSIM Framework}

Different from conventional sub-6GHz BSs, mmWave BSs should be deployed below the rooftops and probably at the same height as the UEs~\cite{BS_height2021}. Notice that, we consider using the vertical-plane-launch~(VPL)~\cite{VPL1998} method to reduce the simulation complexity. Different from a full 3D SBR method, in which rays are launched in the 3D space, the VPL method is a dimension reduction method. OmniSIM first treats vertical building surfaces as 2D segments and generates the rays in the azimuth domain, then  maps the 2D rays to 3D space by considering ground reflections and the possible ceiling reflections.

\begin{figure}
  \centering
  \includegraphics[width=0.95\linewidth]{figs/procedure.pdf}
  \vspace{-0.2cm}
  \caption{OmniSIM flowchart}\label{fig:flowchart}
\end{figure}

A mmWave channel simulator for JCL should generate realistic MPCs and related path parameters including complex path gains $\{\alpha_l\}$, delays $\{\tau_l\}$, DoAs $\{\bm{\theta}_{l}\}$, DoDs $\{\bm{\phi}_{l}\}$ and Doppler shifts $\{ \nu_l\}$ for massive number of BS-UE links. The direct LoS, specular \& diffuse reflections from building surfaces, diffractions by wedges and scattering by irregular scatters~(e.g. vegetation) need to be appropriately modeled. For this purpose, OmniSIM uses GO, UTD, radiative energy transfer~(RET) models to compute reflection, diffraction and scattering effects. The overall flowchart of OmniSIM is shown in Fig.~\ref{fig:flowchart}, the core part of it is a fast shooting-bouncing rays~(FSBR) method which is given by Algorithm~\ref{Alg:hybrid}. The inputs for OmniSIM are 3D digital map with JavaScript Object Notation~(JSON) files which are constructed from an OpenStreet Map~(OSM), BS positions and orientations, UE positions and orientations, and electromagnetic parameters for various map elements.

OmniSIM first extracts geometric information of building surfaces and scatters~(e.g. trees), then finds the first-order surfaces~(reflectors) and scatters interacted with the direct rays radiated from BS. Each first-order reflector is associated with two diffraction wedges. As diffraction and scattering powers are limited in mmWave frequencies, only the wedges and scatters with LoS condition to both BS and UE at the same time are considered. In comparison, $N_{\rm b}$ bouncing order of reflections with $N_{\rm b} \geq 3$ is considered in OmniSIM. The hybrid propagation paths~(e.g. diffraction-reflection, or scattering-reflection) are not considered as these paths exhibit negligible powers in mmWaves. The proposed FSBR algorithm generates a set of all possible reflection paths $\mathcal{P_{\rm R}}$  with a bouncing order up to $N_{\rm b}$. The function \emph{FindIntersectionSurface}($\mb r$,$\mathcal{W}$) finds the surface first interacted with the ray $\mb r$ and return the index $i$ of the surface $\bm w_i$. If no surface is interacted with the ray, it return an index 0. The function \emph{FindIntersectionPoint}($\mb r$, $\bm w_i$) compute the intersection point among $\mb r$ and $\bm w_i$. If $i=0$, it return a point $\bm p = \bm \infty$ where $\bm \infty$ represents the infinity point. When the number of surfaces is huge, the computational complexity of \emph{FindIntersectionSurface}($\mb r$,$\mathcal{W}$) is high. FSBR avoids calling this function frequently by reusing the pre-computed result via checking whether the previous direct ray has an intersection.

A reflection path is characterized by a sequence of intersection point, while a diffraction or scattering path can be determined by the position of the wedge or the scatter in LoS to both BS and the considered UE position. When generating propagation paths for an UE position $\bm u$, OmniSIM first compute the distances between $\bm u$ and the paths in $\mathcal{P_{\rm R}}$, if the distance is smaller than a predefined threshold, then the path is considered effective for $\bm u$. Collecting all unique reflection paths for $\bm u$ gives a set $\mathcal{P}^{(\bm u)}_{\rm R}$. OmniSIM then will merge $\mathcal{P}^{(\bm u)}_{\rm R}$ with $\mathcal{P}^{(\bm u)}_{\rm D}$ and $\mathcal{P}^{(\bm u)}_{\rm S}$, which are the diffraction paths and scattering paths for $\bm u$.
If $\bm u$ is in LoS to the BS, a LoS BS-UE path should be included.

\begin{algorithm}[t]
\textbf{Input}: Set of surfaces
$\mathcal{W}\! =\! \{\bm w_i\}_{i=1}^{\rm B}$,
BS position $\bm b$,
max bouncing order $N_{\rm b}$,
 predefined angular grid $\mathcal{A}=\{\psi_g\}_{g=1}^{\rm G}$
\begin{algorithmic}[1]
\State Ray index $g \leftarrow 1$,   surface index $i\leftarrow0$, bouncing order $ x \leftarrow 1$, intersection point $\bm p_x \leftarrow \bm\infty$, path set $\mathcal{P_{\rm R}} \leftarrow \varnothing $
\While {$g \leq \rm G$}
\State Shoot a ray $\mb r$  from $\bm b$ to direction $\psi_g$, $ x \leftarrow 1$
\If {$i = 0$ }
\State $i \leftarrow$\emph{FindIntersectionSurface}($\mb r$,   $\mathcal{W}$)
\State $\bm p_x \leftarrow$\emph{FindIntersectionPoint}($\mb r$, $\bm w_i$)
\ElsIf { $i \neq 0$ }
\State $\bm p_x \leftarrow$\emph{FindIntersectionPoint}($\mb r$, $\bm w_i$)
\If {$\bm p_x = \bm\infty$}
\State $i \leftarrow$\emph{FindIntersectionSurface}($\mb r$,   $\mathcal{W}$)
\State $\bm p_x \leftarrow$\emph{FindIntersectionPoint}($\mb r$, $\bm w_i$)
\EndIf
\EndIf
\State $\mathcal{R}=\{\bm b, \bm p_x\}$
\If { $i \neq 0$ }
$I \leftarrow i$
\While {$x \leq N_{\rm b}$ and $\bm p_x \neq \bm\infty$}
\State $\psi \leftarrow $ \emph{ReflectionAngle}($\mb r$, $\bm w_I$, $\bm p_x$)
\State Shoot a ray $\mb r$  from $\bm p_x$ to direction $\psi$
\State $I \leftarrow$\emph{FindIntersectionSurface}($\mb r$,   $\mathcal{W}$)
\State $x \leftarrow x+1$
\State $\bm p_x \leftarrow$\emph{FindIntersectionPoint}($\mb r$, $\bm w_I$)
\State $\mathcal{R}= \mathcal{R}\cup \bm p_x  $
\EndWhile
\EndIf
\State $\mathcal{P_{\rm R}} \leftarrow \mathcal{P_{\rm R}} \cup \mathcal{R} $, $g \leftarrow g+1$
\EndWhile
\end{algorithmic}
\textbf{Output}: Set of all possible reflection paths $\mathcal{P_{\rm R}}$
\caption{Fast shooting-bouncing rays~(FSBR) algorithm}
\label{Alg:hybrid}
\end{algorithm}

\subsection{LoS Component}
A LoS cluster has a single ray with the gain calculated by the Friis equation, and the  path coefficient is given by
\begin{align}
\alpha_{\rm LoS} =  \frac{\lambda}{4\pi d} e^{j\frac{2\pi}{\lambda}s},
\end{align}
where $\lambda$ is a wavelength  and $s$ is the distance between TX and RX. Its DoA, DoD can be computed based on the orientations of RX and TX antenna arrays. The delay is $s/c$ with $c$ the speed of light. The Doppler shift is given by $f_{\rm c}\frac{v}{c}\cos\theta_{\rm v}$, with $f_{\rm c}$ the carrier frequency, $v$ the velocity of UE, $\theta_{\rm v}$ the angle between the LoS path and the velocity vector.
\subsection{Specular and Diffuse Rays}\label{sec:ref}

\begin{figure}[b]
  \centering
  \includegraphics[width=0.7\linewidth]{figs/Cluster.pdf}
  \vspace{-0.2cm}
   \caption{First-order reflection with specular and diffuse rays}\label{fig:reflection}
\end{figure}

A cluster of MPCs relevant to the reflections by a building surface contains a dominant specular ray and diffuse sub-rays  with similar DoAs and delays~\cite{Yaman2021}, as depicted in Fig.~\ref{fig:reflection}.
The Fresnel  reflection coefficients for smooth surfaces can be computed using
\begin{align}
   \Gamma^{\parallel} = \frac{\varepsilon \sin \theta\! -\!\sqrt{\varepsilon \!-\! \cos^2\theta}}{\varepsilon \sin \theta \!+\! \sqrt{\varepsilon \!-\! \cos^2\theta}},  \,\,
   \Gamma^{\perp}  = \frac{                      \sin \theta \!-\!\sqrt{\varepsilon \!-\! \cos^2\theta}}{                      \sin \theta \!+\! \sqrt{\varepsilon \!-\! \cos^2\theta}},
   \label{eq:Reflection}
\end{align}
for vertically and horizontally polarized reflection rays respectively,  where $\theta$ is the grazing angle between reflector surface  and the incidence ray, and $\varepsilon$ is the relative permittivity of the reflector material.
As the wave lengths are small and usually comparable to the roughness of exterior walls, diffuse reflection is inevitable for mmWave signals.
We can calculate a scattering loss factor~\cite{Rappaport1996} due to surface roughness that is used to multiply the result for smooth surface reflection to account for diminished energy in the specular direction
of reflection, which is given by
\begin{align}\label{eq:reflection_loss}
\rho_{\rm S} = \exp \left[ -8 \left( \frac{\pi \sigma_{\rm h}\sin \theta}{\lambda}\right)^2 \right],
\end{align}
where $\sigma_{\rm h}$ is the standard deviation of the zero mean height of the reflection surface.
Measurement results confirmed that the reflection clusters generally
consist of a main peak followed by weaker components
with shorter or longer delays~\cite{Haneda2014} and different DoA and DoD offsets, as shown in Fig.~\ref{fig:reflection}.
To model this phenomenon,  the intra-cluster parameters including the sub-ray offsets, DoA and DoD offsets  w.r.t. the specular ray is modeled using stochastic processes with a pre-defined distribution density function. Specifically, the received power from a reflection surface at the RX is assumed to be contributed  by $n_S$ sub-rays.
The path gain coefficient for a first-order reflection sub-ray is assumed to be
\begin{align}
\alpha_{\rm Relf} = e^{j\zeta} \rho_{\rm S} \Gamma \sqrt{\frac{1}{n_{\rm S}}}  \frac{\lambda}{4\pi d_{\rm T}} ,
\end{align}
where $e^{j\zeta}$ is a random phase,  $d_{\rm T}$ is the total  propagation distance.
The mean  values of the intra-cluster Delay Spreads~(DS) are 3.90 and 12.86~ns~\cite{Haneda2017}, in the in-building and urban scenarios, respectively.
\begin{figure}[t!]
  \centering
  \includegraphics[width=0.8\linewidth]{figs/Scatter.pdf}
  \vspace{-0.2cm}
  \caption{Scattering by a tree}\label{fig:scattering}
\end{figure}

According to measurement results in typical in-building and urban environments~\cite{Haneda2014,Haneda2017}, the intra-cluster delay offsets  generally exhibit an exponential distribution, while the  DoA and DoD offsets in both the azimuth and elevation domain follow a Laplacian distribution.
If we model the intra-cluster delay offset $\tau_o$ as a random variable, its probability density function (PDF) is an exponential function given by
\begin{align}\label{eq:PDF_DS}
  f_{\tau_o}(\tau_o) = \frac{1}{\rm D_S} \exp\left(-\frac{\tau_o}{\rm D_S}\right),
\end{align}
with $\rm D_S$ the intra-cluster delay spread.
Similarly,  the sub-ray DoA or DoD offset~(in azimuth or elevation)  within a cluster can be modeled by a random variable $\psi$, whose PDF is
\begin{align}\label{eq:PDF_AS}
  f_{\psi}(\psi) = \frac{1}{\sqrt{2}\rm A_S} \exp\left(-\frac{\sqrt{2}|\psi|}{\rm A_S}\right),
\end{align}
with $\rm A_S$ the intra-cluster angular spread~(AS).
The measured intra-cluster  AS for departure~(ASD) and AS for arrival~(ASA) of the in-building and urban environments have
mean values of {4.33, 5.94} and {5.82, 15.56} degrees~\cite{Haneda2017}.

For an $n$-th order reflection, OmniSIM uses
\begin{align}
\alpha^{[n]}_{\rm Relf} = e^{j\zeta} \left[\prod_{i=1}^n\rho^{[i]}_{\rm S} \Gamma^{[i]}\right] \sqrt{\frac{1}{n_{\rm S}}}  \frac{\lambda}{4\pi d_{\rm T}} ,
\end{align}
to evaluate the path gain with multiple reflections, where $\rho^{[i]}_{\rm S}$ and $\Gamma^{[i]}$ are the scattering loss factor and reflection coefficient for the $i$-th reflection at the $i$-th reflector on the path way.

\begin{figure}[t!]
  \centering
  \includegraphics[width=0.575\linewidth]{figs/Diffraction.pdf}
  \vspace{-0.2cm}
  \caption{Diffraction by a wedge}\label{fig:diffraction}
\end{figure}

\subsection{Scattering by Vegetation}

In the mmWave networks, especially in urban outdoor, vegetation will influence the propagation of mmWave signals, causing attenuation, scattering and depolarization.
According to radiative energy transfer~(RET) model~\cite{Leonor_TAP2014}, attenuation and scattering by vegetation, e.g. trees, can be described by a re-radiation function which specifies the amount of radiated energy transferred from one direction to another due to the random scattering phenomena.
The re-radiation pattern is angular dependent, and can be represented by a Gaussian-shaped forward lobe, superimposed to an isotropic background level representing the backscattering radiation.

Considering trees usually exhibit a cone like shape in nature, cylinders with varying sizes are adopted to represent trees as in~\cite{Leonor_TAP2014}.
The re-radiation pattern is given by
\begin{align}
\rho(\varphi) = {\alpha \left( {2}/{\beta}\right)^2 e^{-\left({\varphi}/{\beta}\right)^2}+ (1-\alpha)},
\end{align}
where $\varphi$~(in radians) is the scattering direction related to the incident direction as shown in Fig.~\ref{fig:scattering}, $\beta$ represents the 3-dB width of the forward lobe and $\alpha$ is the ratio of the forward scattered to the total scatter power.
The power density at the scatterer is given by
$S ={P_{\rm t}}/{4\pi r_1^2}$,
with $P_{\rm t}$ the transmit power and  so the power at the receiver is then given by
\begin{align}
P_{\rm r} = (1-\chi) 2rh S \rho(\varphi) \left( \frac{\lambda}{4\pi r_2}\right)^2,
\end{align}
where $\chi$ is the portion of energy absorbed by the tree, $r$ and $h$ the radius and height of the tree cylinder, $r_1$ is the distance between TX and scatter, $r_2$ is the distance between RX and scatter as depicted in Fig.~\ref{fig:scattering}.
The received power is assumed to be contributed by $n_{\rm S}$ uncorrelated rays with random phases and the path coefficient for a scattered ray can be modeled as
\begin{align}
\alpha_{\rm Scat} = e^{j\zeta}\sqrt{\frac{1}{n_{\rm S}}\cdot\frac{P_{\rm r}}{P_{\rm t}}} =  e^{j\zeta}\sqrt{\frac{(1-\chi)rh \rho(\varphi)}{32n_{\rm S}\pi^3}} \frac{\lambda}{r_1 r_2},
\end{align}
where $e^{j\zeta}$ is a random phase. In OmniSIM, only the first order scattering is considered as the scattering power by vegetation is limited compared with LoS and reflections by buildings.
Finally, the intra-cluster parameters of delays, DoAs and DoDs are generated in a similar way as in Section~\ref{sec:ref}.

\subsection{Diffraction Rays by Wedges}

Although diffraction is limited in mmWave frequencies, it should be considered for obstructed-line-of-sight~(OLOS) links where RX is close to the shadowing boundaries
by building wedges to accurately model the transition from LoS to NLOS condition.
According to UTD~\cite{Holm2000}, the diffracted rays are multiplied by diffraction coefficients and the diffraction coefficient by a wedge is given by
\begin{align}\label{eq1}
D = D(L,n;\phi,\phi^{\prime}) = D_1 + D_2 + \Gamma_0 D_{3} + \Gamma_n D_{4},
\end{align}
where $\Gamma_0$ and $\Gamma_n$ are reflection coefficients for the zero- and $n$-face, respectively, as shown in Fig.~\ref{fig:diffraction}.
The components $D_{l} (l=1,2,3,4)$ of the
diffraction coefficient are given by
\begin{equation}\label{cc}
\begin{aligned}
D_{l}(L,n;\phi,\phi^{\prime})\!=\!\frac{-e^{-j\pi/4}}{2n\sqrt{2\pi k}} \cot \gamma_{l} F(2kLn^2\!\sin^2\!\gamma_{l}),
\end{aligned}
\end{equation}
where $k$ is the wave number, $L = d^\prime d /(d^\prime + d)$, $n\pi$ is the exterior angle of the wedge, $F(\cdot)$ is the transition function defined in \cite{Kouyoumjian1974}, and $\gamma_{1} = [\pi - (\phi - \phi^{\prime})]/2n$, $\gamma_{2} = [\pi + (\phi - \phi^{\prime})]/2n$, $\gamma_{3} = [\pi - (\phi + \phi^{\prime})]/2n$, $\gamma_{4} = [\pi + (\phi + \phi^{\prime})]/2n$.
The basic idea of the UTD is that diffracted rays can be treated
in the same way as reflected rays in the GO and the path coefficient for the diffracted ray in Fig.~\ref{fig:diffraction} can be written as
\begin{equation}\label{ww}
\begin{aligned}
\alpha_{\rm Diff}
= \frac{e^{-jkd\prime}}{d^\prime} D \sqrt{\frac{d^\prime}{dd_{\rm T}}}e^{-jkd} = \frac{e^{-jkd_{\rm T}}}{d_{\rm T}} D \sqrt{\frac{d_{\rm T}}{d^\prime d}},
\end{aligned}
\end{equation}
where $d_{\rm T} = d + d^\prime$ is the total path distance.
In OmniSIM, only the first order diffraction is considered as the diffraction power is limited compared with LoS and reflections by buildings, and the diffraction is
characterized by a single ray.

\begin{table}[t!]
\centering
\caption{Simulation Parameters.}
\label{tbl:tab}
\begin{tabular}{@{}ll|ll@{}}
\toprule
{UE velocity $v$} & 2~m/s & Sub-ray number $n_S$  & 20 \\
{Relative permittivity $\varepsilon$} & 2\,-\,6   & Intra-cluster DS  $\rm D_S$  & 12\,ns  \\
Surface roughtness $\sigma_{\rm h}$   & 0.4\m &    Azimuth  AS        & $10^\circ$ \\
Reradiation beamwidth  $\beta$       & $20^\circ$ &    Elevation AS    & $5^\circ$ \\
Scattered power ratio   $\alpha$          & 0.5 &    Absorption factor $\chi$     & 0.6\\
Polarization           & Vertical                     &  Direct ray spacing       &  $0.1^\circ$ \\
Radius of a tree $r$        & 4\m               &  Height of a tree $h$           &  5\m \\
BS height $h_{\rm BS}$      & 8\m          &  UE height        $h_{\rm UE}$  &  1.5\m \\
BS antenna element           & Microstrip          &  Carrier frequency  &  28\,GHz \\
RF bandwidth    & 246~MHz & TX Power & 30\,dBm \\
Subcarrier spacing & 120~kHz  &  Subcarrier number & 2048 \\
\bottomrule
\end{tabular}
\vspace{-0.2cm}
\end{table}

\section{Simulations}
In this section, we perform channel emulations via the developed OmniSIM in a dense urban scenario to show the capabilities of OmniSIM.
Fig.~\ref{fig:3Dmap} shows the bird-eye view of the simulated scenario. There are total 1606 building surfaces in the digital map.
We simulate the uplink channels from UE to BS. The BS is assumed to use an  uniform planar array ~(UPA), whose array response vector is given in~\cite{JiangWei2022}, with $16\times16$ microstrip patch antenna elements,  while an UE is equipped with an omni-directional antenna. The patch antenna radiation pattern of BS is shown in Fig.~\ref{fig:3Dmap}, which will be embedded in the BS array response vector. The pulse-shaping filter adopted in Eq.~\eqref{eq:ChannelGeneric} is $p(\tau) = {\rm{sinc}}\left({\pi \tau}/{T}\right)$. More details of the simulation parameters are given in Table~\ref{tbl:tab}.
An UE trajectory is generated along the urban street which is shown in Fig.~\ref{fig:RTresult}.

OmniSIM can generate wide-band channel responses for the 166 UE positions along the UE trajectory in 50~seconds using a 3.20\,GHz Intel i7-8700 CPU. The propagation paths, including reflection, diffraction and scattering paths for two UE positions $\rm A$ and $\rm B$, computed by the proposed ray-tracing method are depicted in Fig.~\ref{fig:RTresult}.  The corresponding joint angle-delay power profiles~(JADPP) observed at the BS from these two positions are shown in Fig.~\ref{fig:JADP}.
The power of the LoS ray $|\alpha_{\rm LoS}|^2$ at position 1 is 98.3~dB while that is 88.8 dB at position 2. For all UE positions in LoS condition to the BS, the power of LoS is at least 10~dB larger than other reflected, diffracted or scattered rays.
To verify the spatial consistency~\cite{NYU2018} of the channels generated by OmniSIM, the JADPPs for another two positions $\rm A^{\prime}$ and $\rm B^{\prime}$, following $\rm A$ and $\rm B$, are also shown in Fig.~\ref{fig:JADP}. It can be seen that position $\rm A^{\prime}$ exhibits a similar JADPP as $\rm A$, and $\rm B^{\prime}$ has a similar JADPP as $\rm B$.

The average channel power $\mathbb{E}_n\{|\mb{H}_{n,s}|^2\}$ over sub-carriers as a function of time is shown by Fig.~\ref{fig:ChPowers}. It can be seen that the channel power first increases as the UE moves towards the BS and then decreases after the UE moves into another street. At the end part of the UE trajectory, the mmWave channel is blocked by buildings and a sharp drop in channel power appears. This shows that OmniSIM can model the mmWave blockage effect inherently, which is important in mmWave cellular network planning.
\begin{figure}
  \centering
  \includegraphics[width=0.45\linewidth]{figs/3Dmap.png}
  \includegraphics[width=0.45\linewidth]{figs/BSant.png}
  \vspace{-0.2cm}
  \caption{3D view of the simulated scenario and BS antenna element pattern.}\label{fig:3Dmap}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=0.75\linewidth]{figs/RTresult.pdf}
  \vspace{-0.2cm}
  \caption{Propagation Paths for two UE positions}\label{fig:RTresult}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=0.4\linewidth]{figs/Pos11.pdf}
  \includegraphics[width=0.4\linewidth]{figs/Pos21.pdf}
  \includegraphics[width=0.4\linewidth]{figs/Pos12.pdf}
  \includegraphics[width=0.4\linewidth]{figs/Pos22.pdf}
  \vspace{-0.2cm}
  \caption{Joint angle-delay power profile~(JADPP) for two UE positions}\label{fig:JADP}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[width=0.75\linewidth]{figs/ChPower.pdf}
  \vspace{-0.2cm}
  \caption{Uplink channel powers along the UE trajectory}\label{fig:ChPowers}
\end{figure}

\section{Conclusions}
This paper has presented an open-source map-based hybrid millimeter-wave channel simulator OmniSIM which combines a customized ray tracing method with stochastic multi-path intra-cluster models widely adopted in GSCM. A fast shooting-bouncing rays algorithm has been developed to generate propagation paths for site-specific mmWave radio environments. Diffuse reflections by building surfaces, diffractions by wedges and scattering effects by vegetation have been properly modeled in OmniSIM. OmniSIM can generate spatial-consistent channels for network-level mmWave simulations with massive mmWave links. As the simulated channels are location-dependent, OmniSIM can be used for novel mmWave JCL research, such as intelligent beamforming and deep-learning based localization.

\bibliographystyle{IEEEtran}