s2fieldsofstudy:
Computer Science
Business

text:
Learning Multiple Network Embeddings for Social Influence Prediction

How to effectively predict social influence is an essential issue in social network analysis. Almost all reported methods for social influence prediction are mainly concerned with estimating influence probabilities for each linking edge. However, all of this past work cannot accurately predict influence probabilities for all edges due to the problem of data sparsity. Unlike conventional approaches, this work focuses on exploring a cross problem for multiple network embeddings and social influence prediction. This study developed a new end-to-end approach, Multi-Influor, that learns multiple influence vectors for each user in social networks, instead of estimating influence probabilities for each edge. The multiple network embeddings consider multi-dimensional influence factors that incorporate pairwise node interactions, network structures, and global similarity comparisons. Moreover, this study solves the problem of influence evaluation caused by sparse observations. Extensive comparisons based on large-scale datasets indicate that the Multi-Influor approach outperforms several state-ofthe-art baselines, and the experimental results demonstrate that the Multi-Influor approach is more practical on real-world social networks.

INTRODUCTION
The rapid development of online social networks (OSNs) lays a foundation for spreading users' ideas and messages. The related work of social network analysis has found that users' friends or neighbors greatly affect these users' behaviors or opinions from a perspective of psychology [Aslay, et al. (2018)]. Thus, this study defines social influence as a user's ability that users' actions (behaviors or opinions) affect their neighbors in OSNs. The extensive researches in social influence analysis pave the way for various applications, such as resource recommendation [Zhang, et al. (2018)], community detection [Al-Garadi, et al. (2018)], and viral marketing [Yang, et al. (2017)].
One essential problem in social influence analysis is to estimate influence probabilities based on action logs, and extensive works have been done on this problem [Pal, et al. (2014); Aslay, et al. (2018); Sun, et al. (2018)]. Almost all previously related work aims at calculating influence parameters for each edge in OSNs. However, since the problem of sparse observations for influence spreads, the previous works cannot accurately learn edge parameters to predict influence probabilities, especially for edges without sufficient diffusion data. Moreover, these conventional edge-based approaches cannot consider other influence factors (such as network structure and preference similarity) or detect hidden influence relationships between users (high-order influence spreads). Thus they perform poorly on the predictions of influence probabilities.
This work focuses on exploring a cross problem for multiple network embeddings and social influence prediction. Inspired by the research of network representation learning [Bai, et al. (2019);Grover, et al. (2018)], this study directly learns multiple latent vectors for each user to capture social influences, instead of estimating influence probabilities for each edge. Moreover, this work alleviates the challenge of sparse observation data via latent vectors.
To our knowledge, this may be the first study of social influence prediction that jointly captures influence spreads and multiple network embeddings.
To address the above challenges, this study developed a new end-to-end approach, Multiple Influence-to-vector (Multi-Influor), that learns multiple influence vectors for each user in social networks. The first key step to predicting social influence is how to generate multiple influence learning contexts. This work devised a new method of generating multiple influence contexts, which includes nodelevel, subnetwork-level, and global graph-level influence contexts. Then, the Multi-Influor method learns nodelevel and graph-level latent vectors based on the generated contexts (details in Section 3). Therefore, the multiple network embeddings incorporate multi-dimensional influence factors for pairwise node interactions, network structures, and global similarity comparisons.
In this study, we conducted extensive comparisons based on four large-scale datasets. The comparison results illustrate that the Multi-Influor approach outperforms several state-of-the-art baselines. Moreover, the experimental results demonstrate that the Multi-Influor approach is more practical on real-world social networks.

Preliminaries
In this study, we model each social network as a graph G = (V, E), where V denotes a user set and E denotes a set of linking edges between users. The linking edge (u, v) denotes that user u is a neighbor of user v. In addition, this study obtains diffusion episodes from action logs. The action logs contain sets of tuples in the form of (u, i, t i u ) that denotes user u performed an action related to item i at time t i u . Each item i (such as information, idea and opinion) corresponds to one diffusion episode D i = {(u, t i u ), · · · , (v, t i v )}, which denotes users in D i adopt to perform action i in a chronological order. Definition 2.1. (User Social Action). A binary action state for user u, s i u ∈ {0, 1}, is calculated based on action logs A, where s i u = 0 denotes user u has not performed the action i at time t i u , and s i u = 1 denotes user u has performed the action i before or at time t i u . Definition 2.2. (Social Influence Spread). Based on a social network G = (V, E) and diffusion episodes D i , a social influence spreads from user u to user v if it satisfies:

Problem Definition
This study aims to transfer each user's representation into a low-dimensional latent vector for social influence prediction. In general, this study attempts to learn multiple representations for |V | users based on a given social network and action logs, which are used to evaluate the influence probabilities for |E| edges.
Multiple Network Embeddings Problem. Based on a social network G = (V, E) and action logs, this work aims to learn multiple social influence representations for each user: node-level vector V ec u and graph-level vectors I u , S u , b u ,b u .

THE DEVELOPED METHOD: MULTI-INFLUOR
In this section, we proceed to detail the newly developed Multiple Influence-to-vector (Multi-Influor) method, which is an end-to-end neural network-based method that aims at addressing the challenges mentioned in Section 1. The framework of Multi-Influor ( Fig. 1) contains three parts. First, this work provides how to generate multiple influence contexts in stage 1. Second, based on the generated influence contexts, this paper presents a learning approach for multiple influence representations in stage 2. Finally, this study feeds the combined multiple vectors into a fully connected neural network to predict influence probabilities in stage 3.

Stage 1: Multiple Influence Contexts Generating
In this study, we introduce a method of generating multiple influence contexts, which includes node-level, subnetworklevel, and graph-level influence contexts. These influence contexts focus on multi-dimensional influence factors for pairwise node interactions, network structures, and global similarity comparisons. Definition 3.1. (Influence Context). Based on a social network G = (V, E) and action logs, this study defines an influence context for user u as a set of users who are probably affected by user u.
Node-level influence context Based on a social network and a given user u, the straightforward way to generate a node-level influence context for user u is to adopt the breadth-first search (BFS) method that starts from user u. Then, r-neighbours N r u = {v : d(u, v) ≤ r} can be acquired, where d(u, v) is the shortest path between user u and v. This work applies a sub-network induced by N r u to establishing a network of r-ego user u. To facilitate the neural network learning in network embeddings, we suppose to sample a fixed-size sub-network. In addition, this is easy to solve the problem of different sampling sizes.
According to network structures and edge weights estimated by diffusion episodes D i , this study performs random walks on the network of r-ego user u. A random walk iteratively traverses to neighbors with different probabilities and stops running until it collects a fixed-size of users (L N ). Then, this work regards the sampled network as a node-level influence context for user u, C ni u , that can embed pairwise nodes' interaction information into user u's latent influence vector.
Subnetwork-level influence context This work builds an influence spread network to incorporate subnetwork-level influence (high-order influence diffusion) information into latent influence vectors, which illustrates influence diffusions for each item in social networks (as shown on the left part of Fig. 1). Definition 3.2. (Influence Spread Network). Based on a social network G = (V, E) and action logs, we define an influence spread network as (2) each edge (u, v) denotes a social influence spreads from user u to v.
The Multi-Influor method captures high-order diffusion information via random walk processes on influence spread networks, which incorporates structure information into subnetwork-level embeddings. Moreover, this approach can solve the problem of influence estimating caused by sparse propagation data.
This study generates user u's subnetwork-level influence context, C si u , based on the influence spread network G i . We apply random walks with restarts to simulating users' influence diffusions. The random walk process starts from user u and randomly selects one neighbor of user u to traverse. Next, based on the currently activated users, we randomly select one neighbor of these users to traverse in the next sampling step. In addition, the process is probable to back to user u at each step. This work uses a length threshold (L S ) to limit the size of C si u and stops sampling when the threshold L S is reached.
Global graph-level influence context This study further incorporates users' preference similarities in latent influence vectors by using graph-level influence contexts. Given an influence spread network G i = (V i , E i ), users perform the same actions indicates that these users share the same interest.
To capture the similarity of users' interests, the Multi-Influor method uniformly samples a set of users (L G ) by a given user u in the influence spread network G i . Note that the samples of similar users denote the global graph-level influence context C gi u .
Multiple influence contexts generating algorithm Based on a social network G and a given user u, this work aims to generate multiple influence contexts C i u = C ni u +C si u +C gi u . To balance the contributions of these multi-level contexts, we suppose the component weights (α, β, γ) are all in the range of 0 to 1, and α + β + γ = 1.
First, this work generates the node-level influence context (L N = α · L) via random walks in the social network G. Then, the subnetwork-level influence context (L S = β · L) can be generated based on the influence spread network G i . Finally, this study uniformly samples the users in V i , and the length of the graph-level influence context L G = γ ·L. These multiple influence contexts contain three types of sampled data. The time complexity of multiple influence contexts generating algorithm is O(L), where L denotes the total length threshold for influence contexts (L = L N + L S + L G ).

Stage 2: Multiple Network Embeddings
The stage of multiple network embeddings provides an effective approach that simulates relationships between users and their multiple influence contexts. Inspired by the related work in the field of natural language processing, we apply a modified word2vec technique to learning multiple influence representations for each user in social networks [Grover, et al. (2018)].
Node-level influence representation learning This study develops a neural network-based approach that learns node-level influence vectors. Based on the node-level influence contexts, this work aims to estimate the probability of affecting user v conditional on his/her r-ego network G r v and action state of his/her r-neighbors S r v . We formulate the method of predicting the influence probability for user v after a given time interval ∆t as To calculate node-level influence probabilities, this work formulates the node-level influence prediction as a binary graph classification problem, which can be solved by maximizing the objective function as Based on the node-level influence contexts, all users learn an embedding matrix X ∈ R d×n , each column corresponding to the representation of a user in the network. Each user u i maps to his/her d-dimensional vector x ui ∈ R d using a pre-trained embedding layer. Then, this work adopts an instance normalization technique [Huang, et al. (2017)] to calculate the instance normalization for each embedding dimension d as where µ i is the mean of vectors, σ i is the variance of vectors, and is a small number for numerical stability.
With a node-level embedding for each user, this work also devises to incorporate various user-specific features into the input layer of the graph convolutional network (GCN), such as content features and demographic features [Qiu, et al. (2018)]. Aside from instance normalization vectors, this work also considers a binary variable to indicate users' action states.
In the neural network learning, we stack multiple GCN layers to conduct nonlinear transformations [Narayan, et al. (2018)]. The input of each GCN layer is a vertex feature matrix H, and the output H is calculated as where the notation A(G) denotes a n × n matrix that captures structural information for the network G, and W and b are model parameters.
Finally, this work supposes the output layer provides a two-dimension representation (V ec u ) for each user. We use the vector of user u to predict the ego user's state and the influence probability of user u. We compare the prediction results with ground truth data to optimize the objective function (Eq. (1)). Therefore, we learn a nodelevel influence vector for each user.
Graph-level influence representation learning To capture graph-level influence information, this work uses a skipgram method to generate the graph-level context for a given user u [Krishna, et al. (2019)]. The key step in graph-level influence embedding is to evaluate the probability of observing the graph-level influence context, P r(C si+gi u |u), including the contexts of subnetwork-level and global graph-level influence (C si+gi u = C si u +C gi u ). This work calculates the probability P r(C si+gi u |u) by using the independent probability P r(v|u) that influences propagate from user u to v, and the notation v denotes a user in the graph-level context C si+gi This work generates a list of (u, C si+gi u ) tuples for each diffusion episode, which is denoted as T Di . The whole influence context tuples, T , contains all the observed episodes D i in action logs A. This work attempts to maximize the log-probability of P r(C si+gi u |u). Thus, this study defines the loss function of the graph-level influence representation learning as Next, this work calculates the loss function by evaluating the probabilities that influences propagate from user u to v. The Multi-Influor method calculates the probability

Algorithm 1 Multi-Influor
Input: A social network G = (V, E), diffusion episodes D i , component weights α, β, γ, a learning rate η and the dimension of influence vector k. Output: Multiple influence representations for each user u ∈ V . 1: Initialize vectors I u and S v with uniform distribution Generate a node-level influence context C ni u ;

5:
Extract an influence spread network G i = (V i , E i ).

6:
for each user u ∈ V i do 7: Generate C si u and C gi u ; 8: Insert T Di into T . 10: Multiple influence representations learning: 11: for T Di ∈ T do 12: for v ∈ C i u do

15:
Graph-level influence vectors: I u , S v , b u ,b v ; 16: Update all parameters until convergence. 17: return V ec u , I u , S u , b u ,b u . P r(v|u) via the inner product of users' latent vectors I u · S v , where I u denotes the influence ability vector for user u and S v denotes the susceptibility vector for user v. Moreover, this work uses b u andb v to reflect the bias of influence vector for user u and the bias of susceptibility vector for user v, respectively. Therefore, this work formulates the probability that user u influences user v as a softmax function (Eq. 6). P r(v|u) = e (Iu·Sv+bu+bv) /sum(u) where sum(u) = w∈Vi e (Iu·Sw+bu+bw) is a normalization term.
To alleviate the issue of computation efficiency, the negative sampling can be used to compute the softmax function [Peng, et al. (2017)]. Then, this study uses the method of stochastic gradient descent to learn all parameters. During each step, this work updates parameters Θ via gradient calculations as where η denotes a learning rate and ∂ ∂Θ denotes the gradient of parameters Θ.

Stage 3: Influence Probability Predicting
After obtaining multiple influence representations for each user, this work uses a multi-layer fully connected neural network to gradually reduce the vector's dimension for each user. In the end, we predict the influence probability, s uv , that influences propagate from user u to v. This study compares the prediction results with ground truth data, and optimizes the log-likelihood loss function as To sum up, the Multi-Influor method incorporates the finegrained influence relationships that are captured by the node-level embedding and the coarse influence information that is captured by the graph-level embedding, which provides a thorough view of influence probability estimating to the prediction approach.
This study randomly selected 60%, 20%, 20% instances of sampling data for training, validation, and testing, respectively. The size of a mini-batch was set to be 512 across four datasets. The Multi-Influor method performed random walks with a restart probability of 0.75 in the steps of contexts sampling. Furthermore, this work set the dimension of initial vectors to be 64 in the node-level embedding, and to be 60 in the graph-level embedding. Each initial vector in the input layers was pre-trained via the autoencoder technique.
In the step of neural network learning, this work supposed the learning rate η = 0.005 and the influence vector's dimension k = 62. According to the empirical study on tuning set [Bai, et al. (2019)], the total length threshold for influence context L was set to 160, and the component weights were set as α = 0.4, β = 0.3, and γ = 0.3.

Evaluation Metrics
Prediction performance comparison. The task of influence diffusion prediction focuses on predicting predict probabilities of whether users will be influenced by seed users. This study evaluated the predictive performance for different methods in terms of precision (Prec.), recall (Rec.), F1-measure, and area under curve (AUC).
Influence spread comparison. This work used the prediction results to detect seeds and solve the influence 1 http://open.weibo.com/ maximization problem. We compared the seeds' influence, which is demonstrated by the range of influence spread. We conducted these comparisons on different datasets and used the independent cascade (IC) model to simulate influence spread processes on OSNs [Aslay, et al. (2018)].

Prediction Performance Comparison
This subsection presents the comparisons of diffusion probability predictions based on different OSNs (Table 2). In general, the Multi-Influor approach achieves significantly better performance than the conventional methods (SVM and Emb-IC) in the datasets of Sina Weibo, Epinions, and NetHEPT. The methods of Multi-Influor and Inf2vec perform best, but the Multi-Influor method performs better than the Inf2vec method in diffusion probability predictions. These may because the Multi-Influor method considers multiple network embeddings that incorporate more influence factors. However, in the dataset of WikiVote, Node2vec and Emd-IC sometimes outperform than the Multi-Influor approach.
Since the data size of WikiVote is small, the Multi-Influor approach lacks training data to improve the performance of neural network-based learning (GCN layers and fully connected neural network). Adding more sampling data in the training processes can improve the performance of Multi-Influor. These experimental results demonstrate that the Multi-Influor approach is highly data-driven.

Influence Spread Comparison
We uniformly used a greedy algorithm to detect seeds based on the prediction results [Sun, et al. (2018)]. Then, we compared the range of activated users influenced by seeds. After adding a new user to the seeds, we set the number of influence spread simulations to be 10,000. In addition, this study conducted comparisons under the conditions of different datasets and seed sizes.
In general, the comparisons of influence spread (Fig. 2) illustrate that the Multi-Influor approach always performs best, which means that it can lay a solid foundation for solving the influence maximization problem. In the datasets of Sina Weibo, Epinions, and NetHEPT ( Fig. 2  (a), (b), (d)), the Multi-Influor method performs much better than SVM and Emb-IC, and above 30% better than Node2vec. However, with much less training data in WikiVote, the approaches all perform worse than in other datasets. In WikiVote (Fig. 2 (c)), the Multi-Influor method only performs better than SVM and Emb-IC, and it achieves near performance to Node2vec and Inf2vec.

Fig. 2. Influence Spread Comparisons
The size of training data in neural networks could strongly affect the performance of Multi-Influor. However, these experimental results indicate that using more information propagation data improves the performance of the Multi-Influor approach. The real-world social networks provide extensive user data, which guarantees the performance of Multi-Influor. In other words, the Multi-Influor approach can be more practical on large-scale datasets.

CONCLUSION
This study focused on exploring a cross problem for multiple network embeddings and social influence prediction, and we developed a new end-to-end approach, namely Multi-Influor, that learns multiple network embeddings for each user in OSNs. The basic idea is to learn a neuralnetwork-based function that considers multi-dimensional influence factors. The Multi-Influor approach takes a social network and action logs as input and outputs predictive influence probabilities. The experimental results illustrate that the Multi-Influor approach performs better than other baselines on influence predictions. Moreover, Multi-Influor is a highly data-driven method that can be more practical on real-world social networks.


extfieldsofstudy:
Computer Science
Geology
Engineering

text:
GRNet: Gridding Residual Network for Dense Point Cloud Completion

Estimating the complete 3D point cloud from an incomplete one is a key problem in many vision and robotics applications. Mainstream methods (e.g., PCN and TopNet) use Multi-layer Perceptrons (MLPs) to directly process point clouds, which may cause the loss of details because the structural and context of point clouds are not fully considered. To solve this problem, we introduce 3D grids as intermediate representations to regularize unordered point clouds. We therefore propose a novel Gridding Residual Network (GRNet) for point cloud completion. In particular, we devise two novel differentiable layers, named Gridding and Gridding Reverse, to convert between point clouds and 3D grids without losing structural information. We also present the differentiable Cubic Feature Sampling layer to extract features of neighboring points, which preserves context information. In addition, we design a new loss function, namely Gridding Loss, to calculate the L1 distance between the 3D grids of the predicted and ground truth point clouds, which is helpful to recover details. Experimental results indicate that the proposed GRNet performs favorably against state-of-the-art methods on the ShapeNet, Completion3D, and KITTI benchmarks.

Introduction
With the rapid development of 3D acquisition technologies, 3D sensors (e.g., Li-DARs) are becoming increasingly available and affordable. As a commonly used format, point clouds are the preferred representation for describing the 3D shape of an object. Complete 3D shapes are required in many applications, including semantic segmentation and SLAM [1]. However, due to limited sensor resolution and occlusion, highly sparse and incomplete point clouds can be acquired, which causes loss in geometric and semantic information. Consequently, recovering the complete point clouds from partial observations, named point cloud completion, is very important for practical applications. In the recent few years, convolutional neural networks (CNNs) have been applied to 2D images and 3D voxels. Since the convolution can not be directly applied to point clouds due to their irregularity and unorderedness, most of the existing methods [2,3,4,5,6,7,8] voxelize the point cloud into binary voxels, where 3D convolutional neural networks can be applied. However, the voxelization operation leads to an irreversible loss of geometric information. Other approaches [9,10,11] use the Multi-Layer Perceptrons (MLPs) to process point clouds directly. However, these approaches use max pooling to aggregate information across points in a global or hierarchical manner, which do not fully consider the connectivity across points and the context of neighboring points. More recently, several attempts [12,13] have been made to incorporate graph convolutional networks (GCN) [14] to build local graphs in the neighborhood of each point in the point cloud. However, constructing the graph relies on the K-nearest neighbor (KNN) algorithm, which is sensitive to the point cloud density [15].
Several attempts in point cloud segmentation have been made to capture spatial relationships in point clouds through more general convolution operations. SPLATNet [16] and InterpConv [17] perform convolution on high-dimensional lattices and 3D cubes interpolated from neighboring points, respectively. However, both of them are based on a strong assumption that the 3D coordinates of the output points are the same as the input points and thus can not be used for 3D point completion.
To address the issues mentioned above, we introduce 3D grids as intermediate representations to regularize unordered point clouds, which explicitly preserves the structural and context of point clouds. Consequently, we propose a novel Gridding Residual Network (GRNet) for point cloud completion, as shown in Figure 1. Besides 3D CNN and MLP, we devise three differentiable layers: Gridding, Gridding Reverse, and Cubic Feature Sampling. In Gridding, for each point of the point cloud, eight vertices of the 3D grid cell that the point lies in are first weighted using an interpolation function that explicitly measures the geometric relations of the point cloud. Then, a 3D convolutional neural network (3D CNN) with skip connections is adopted to learn context-aware and spatially-aware features, which allows the network to complete missing parts of the incomplete point cloud. Next, Gridding Reverse converts the output 3D grid to a coarse point cloud by replacing each 3D grid cell with a new point whose coordinate is the weighted sum of the eight vertices of the 3D grid cell. The following Cubic Feature Sampling extracts features for each point in the coarse point cloud by concatenating the features of the corresponding eight vertices of the 3D grid cell that the point lies in. The coarse point cloud and the features are forwarded to an MLP to obtain the final completed point cloud.
Existing methods adopt Chamfer Distance in PSGN [18] as the loss function to train the neural networks. This loss function penalizes the prediction deviating from the ground-truth. However, there is no guarantee that the predicted point clouds follow the geometric layout of objects, and the networks tend to output a mean shape that minimizes the distance [19,20]. Some recent works [19,20,21,22,23] attempt to solve the unorderness while preserving fine-grained details by projecting the 3D point cloud to an image, which is then supervised by the corresponding ground truth masks. However, the projection requires extrinsic camera parameters, which are challenging to estimate in most scenarios [24]. To solve the unorderedness of point clouds, we propose Gridding Loss, which calculates the L1 distance between the generated points and ground truth by representing them in regular 3D grids with the proposed Gridding layer.
The contributions can be summarized as follows: -

Related Work
According to the network architecture used in point cloud completion and reconstruction, existing networks can be roughly categorized into MLP-based, graphbased, and convolution-based networks.
MLP-based Networks. Pioneered by PointNet [25], several works use MLP for point cloud processing [26,27] and reconstruction [9,10] because of its simplicity and strong representation ability. These methods model each point independently using several Multi-layer Perceptrons and then aggregate a global feature using a symmetric function (e.g., Max Pooling). However, the geometric relationships among 3D points are not fully considered. PointNet++ [28] and TopNet [11] incorporate a hierarchical architecture to consider the geometric structure. To relief the structure loss caused by MLP, AtlasNet [29] and MSN [30] recover the complete point cloud of an object by estimating a collection of parametric surface elements.
Graph-based Networks. By considering each point in a point cloud as a vertex of a graph, graph-based networks generate directed edges for the graph based on the neighbors of each point. In these methods, convolution is usually operated on spatial neighbors, and pooling is used to produce a new coarse graph by aggregating information from each point's neighbors. Compared with MLP-based methods, graph-based networks take local geometric structures into account.
In DGCNN [12], a graph is constructed in the feature space and dynamically updated after each layer of the network. Further, LDGCNN [31] removes the transformation network and link the hierarchical features from different layers in DGCNN to improve its performance and reduce the model size. Inspired by DGCNN, Hassani and Haley [32] introduce the multi-scale graph-based network to learn point and shape features for self-supervised classification and reconstruction. DCG [13] also follows DGCNN to encode additional local connection into a feature vector and progressively evolves from coarse to fine point clouds.
Convolution-based Networks. Early works [2,3,33] usually apply 3D convolutional neural networks (CNNs) build upon the volumetric representation of 3D point clouds. However, converting point clouds into 3D volumes introduces a quantization effect that discards some details of the data [34] and is not suitable for representing fine-grained information. To the best of our knowledge, no work directly applies CNNs on irregular point clouds for shape completion. In point cloud understanding, several works [17,35,36,37,38] develop CNNs operating on discrete 3D grids that are transformed from point clouds. Hua et al. [35] define convolutional kernels on regular 3D grids, where the points are assigned with the same weights when falling into the same grid. PointCNN [38] achieves permutation invariance through a χ-conv transformation. Besides CNNs on discrete space, several methods [8,15,16,39,40,41,42,43] define convolutional kernels on continuous space. Thomas et al. [15] propose both rigid and deformable kernel point convolution (KPConv) operators for 3D point clouds using a set of learnable kernel points. Compared with graph-based networks, convolution-based networks are more efficient and robust to point cloud density [17].

Overview
The proposed GRNet aims to recover the complete point cloud from an incomplete one in a coarse-to-fine fashion. It consists of five components, including Gridding (Section 3.2), 3D Convolutional Neural Network (Section 3.3), Gridding Reverse (Section 3.4), Cubic Feature Sampling (Section 3.5), and Multi-layer Perceptron (Section 3.6), as shown in Figure 1. Given an incomplete point cloud P as input, Gridding is first used to obtain a 3D grid G =< V, W >, where V and W are the vertex set and value set of G, respectively. Then, W is fed to a 3D CNN, whose output is W . Next, Gridding Reverse produces a coarse point cloud P c from the 3D grid G =< V, W >. Subsequently, Cubic Feature Sampling generates features F c for the coarse point cloud P c . Finally, MLP takes the coarse point cloud P c and the corresponding features F c as input to produce the final completed point cloud P f .

Gridding
2D and 3D convolutions have been developed to process regularly arranged data such as images and voxel grids. However, it is challenging to directly apply standard 2D and 3D convolutions to unordered and irregular point clouds. Several methods [2,3,8,33] convert point clouds into 3D voxels and then apply 3D convolutions to them. However, the voxelization process leads to an irreversible loss of geometric information. Recent methods [9,11] adopt Multi-layer Perceptrons (MLPs) to directly operate on point clouds and aggregate information across points with max pooling. However, MLP-based methods may lose local context information because the connectivity and layouts of points are not fully considered. Recent studies also indicate that simply applying MLPs to point clouds cannot always work in practice [17,39].
In this paper, we introduce 3D grids as intermediate representations to regularize point clouds and further propose a differentiable Gridding layer, which converts an unordered and irregular point cloud n is the number of points in P , and N is the resolution of the 3D grid G. As shown in Figure 1 (b), we define a cell as a cubic consisting of eight vertices.
of the 3D grid cell G, we define the neighboring points N (v i ) as points that lie in the adjacent 8 cells of this vertex. The point However, this voxelization process introduces a quantization effect that discards some details of an object. In addition, voxelization is not differentiable and thus can not be applied to point cloud reconstruction. As illustrated in Figure 1 (b), given a vertex v i and its neighboring points p ∈ N (v i ), the proposed Gridding layer computes the corresponding value w i of this vertex v i as denotes the sum operation. Tile creates a new tensor of size 16384 × 3 by replicating the "Coarse Point Cloud" 8 times.
where |N (v i )| is the number of neighboring points of v i . Specially, we define

3D Convolutional Neural Network
The 3D Convolutional Neural Network (3D CNN) with skip connections aims to complete the missing parts of the incomplete point cloud. It follows the idea of a 3D encoder-decoder with U-net connections [44,45]. Given W as input, the 3D CNN can be formulated as and w i ∈ R. As shown in Figure 2, the encoder of the 3D CNN has four 3D convolutional layers, each of which has a bank of 4 3 filters with padding of 2, followed by batch normalization, leaky ReLU activation, and a max pooling layer with a kernel size of 2 3 . The numbers of output channels of convolutional layers are 32, 64, 128, 256, respectively. The encoder is finally followed by two fully connected layers with dimensions of 2048 and 16384. The decoder consists of four transposed convolutional layers, each of which has a bank of 4 3 filters with padding of 2 and stride of 1, followed by a batch normalization layer and a ReLU activation.

Gridding Reverse
As illustrated in Figure 1 (c), we propose Gridding Reverse to generate the coarse be the index set of vertices of the i−th 3D grid cell. Gridding Reverse generates one point coordinate p c i for this grid cell by a weighted combination of eight vertices coordinates {v θ |θ ∈ Θ i } and the corresponding values {w θ |θ ∈ Θ i } in this cell, which is computed as Specially, we ignore the point p c i for this cell if θ∈Θ i w θ = 0.

Cubic Feature Sampling
MLP-based methods (e.g., PCN) are unable to take the context of neighboring points into account due to no local spatial connectivity across points. These methods use max-pooling to aggregate information globally, which may lose local context information.
To overcome this issue, we present Cubic Feature Sampling to aggregate fea- for the coarse point cloud P c , which is helpful for the following MLP to recover the details of point clouds, as shown in Figure 1 denotes the features of eight vertices of the i-th 3D gird cell where p c i lies in. In GRNet, Cubic Feature Sampling extracts the point features from feature maps generated by the first three transposed convolutional layers in 3D CNN. To reduce the redundancy of these features and generate a fixed number of points, we randomly sample 2, 048 points from the coarse point cloud P c . Consequently, it produces a feature map of size 2048 × 1792.

Multi-layer Perceptron
The Multi-layer Perceptron (MLP) is used to recover the details from the coarse point cloud by learning residual offsets between the coordinates of points in the coarse and final completed point cloud. It takes the coarse point cloud P c and the corresponding features F c as input, and outputs the final completed point where p f i ∈ R 3 and k is the number of points in the final completed point cloud P f . Tile creates a new tensor of size rk × 3 by replicating P c r times.
In GRNet, r is set to 8. The MLP consists of four fully connected layers with dimensions of 1792, 448, 112, and 24, respectively. The output of MLP is reshaped to 16384 × 3, which corresponds to the offsets of the coordinates of 16, 384 points.

Gridding Loss
Existing methods adopt Chamfer Distance [18] as the loss function to train the neural networks. This loss function penalizes the prediction deviating from the ground-truth. However, it can not guarantee that the predicted points follow the geometric layout of the object. Therefore the networks tend to output a mean shape that minimizes the distance, which causes the loss of the object's details [19,20].
Due to the unorderedness of point clouds, it is difficult to directly apply binary cross-entropy like voxels or L1/L2 loss like images. With the proposed Gridding, we can convert unordered point clouds into regular 3D grids ( Figure  1 (e)). Therefore, we design a new loss function based on Gridding, namely Gridding Loss, which is defined as the L1 distance between value sets of the two 3D grids. Let G pred =< V pred , W pred > and G gt =< V gt , W gt > be the 3D grids obtained by Gridding the predicted and ground truth point clouds, respectively, where W pred ∈ R N 3 G , W gt ∈ R N 3 G , and N G is the resolution of the two 3D grids. The Gridding Loss can be defined as

Datasets
ShapeNet. The ShapeNet dataset [46] for point cloud completion is derived from PCN [9], which consists of 30,974 3D models from 8 categories. The ground truth point clouds containing 16,384 points are uniformly sampled on mesh surfaces. The partial point clouds are generated by back-projecting 2.5D depth maps into 3D. For a fair comparison, we use the same train/val/test splits as PCN.
Completion3D. The Completion3D benchmark [11] is composed of 28,974 and 800 samples for training and validation, respectively. Different from the ShapeNet dataset generated by PCN, there are only 2,048 points in the ground truth point clouds.
KITTI. The KITTI dataset [47] is composed of a sequence of real-world Velodyne LiDAR scans, also derived from PCN [9]. For each frame, the car objects are extracted according to the 3D bounding boxes, which results in 2,401 partial point clouds. The partial point clouds in KITTI are highly sparse and do not have complete point clouds as ground truth.

Evaluation Metrics
be a reconstructed point set being evaluated, where n T and n R are the numbers of points of T and R, respectively. In our experiments, we use both Chamfer Distance and F-Score as quantitative evaluation metrics. Chamfer Distance. Follow PSGN [18] and TopNet [11], the distance between T and R are defined as  F-Score. As pointed out in [48], Chamfer Distance may sometimes be misleading. As suggested in [48], we take F-Score as an extra metric to evaluate the performance of point completion results, which can be defined as following where P (d) and R(d) denote the precision and recall for a distance threshold d, respectively.

Implementation Details
We implement our network using PyTorch [49] and CUDA 1 . All models are optimized with an Adam optimizer [50] with β 1 = 0.9 and β 2 = 0.999. We train the network with a batch size of 32 on two NVIDIA TITAN Xp GPUs. The initial learning rate is set to 1e − 4 and decayed by 2 after 50 epochs. The optimization is set to stop after 150 epochs.

Shape Completion on ShapeNet
To compare the performance of GRNet with other state-of-the-art methods, we conduct experiments on the ShapeNet dataset. AtlasNet [29] generates a point cloud with a set of parametric surface elements. To compare with other methods fairly, we sample 16,384 points from the generated primitive surface elements. PCN [9] completes the partial point cloud with a stacked version of PointNet [25], which directly outputs the coordinates of 16,384 points. FoldingNet [51]  is a baseline method adopted in PCN [9], which deforms a 128 × 128 2D grid into 3D point cloud. TopNet [11] incorporates a decoder following a hierarchical rooted tree structure to consider the topology of point clouds. Due to the scalable architecture of TopNet, it can easily generate 16,384 points by setting the number of nodes and the size of feature embedding. A very recent method MSN [30] generates dense point cloud containing 8,192 points in a coarse-to-fine fashion. To generate 16,384 points, we combine the generated points of 2 times forward propagation.
Quantitative results in Tables 2 and 1 indicate that GRNet outperforms all competitive methods in terms of Chamfer Distance and F-Score@1%. Figure 3 shows the qualitative results for point completion on ShapeNet, which indicates that the proposed method recovers better details of objects (e.g., chairs and lamps) than the other methods.

Shape Completion on Completion3D
Using the model with the lowest Chamfer Distance (CD) on the validation set, we recover the complete point clouds for 1,184 objects in the Completion3D testing set. Then, random subsampling is applied to the generated point clouds to obtain 2,048 points for benchmark evaluation. According to the online leaderboard 2 , as shown in Table 3, the overall CD for the proposed GRNet is 10.64, which remarkably outperforms state-of-the-art methods and ranks first on this benchmark.

Shape Completion on KITTI
To evaluate the performance of the proposed method on real-world LiDAR scans, we test GRNet on the KITTI dataset for completing sparse point clouds of cars. Unlike ShapeNet generated by back-projected from 2.5D images, point clouds from LiDAR scans can be highly sparse, which are much sparser than those in ShapeNet.
We fine-tuned all competitive methods on ShapeNetCars (the cars from ShapeNet) except PCN that directly uses released output for evaluation. During testing, each point cloud is transformed into the bounding box's coordinates and transformed back to the world frame after completion. The models trained specifically on cars are able to incorporate prior knowledge of the object class.
Since there are no complete ground truth point clouds for KITTI, we use Consistency and Uniformity to evaluate the performance of all competitive methods. Consistency in PCN [9] is the average CD between the output of the same car instance in n f consecutive frames. Let R j ti be the output for the j-th car instance at time t i . The Consistency for the j-th car can be calculated as Following PU-GAN [52], we adopt Uniformity to evaluate the distribution uniformity of the completed point clouds, which can be formulated as where S i (i = 1, 2, . . . , M ) is a point subset cropped from a patch of the output R using the farthest sampling and ball query of radius √ p. The term U imbalance and U clutter account for the global and local distribution uniformity, respectively. wheren = p|R| is the expected number of points in S i .
where d i,j represents the distance to the nearest neighbor for the j-th point in [52]. Table 9 shows the completion results for cars in the LiDAR scans from the KITTI dataset. Experimental results indicate that GRNet outperforms other competitive methods in terms of Consistency and Uniformity. Benefited from Gridding and Gridding Reverse, GRNet is more sensitive to the spatial structure of the input points, which leads to better consistency between the two consecutive frames. As shown in Figure 4, the cars are barely recognizable due to incompleteness of the input data. In contrast, the completed point clouds provide more geometric information. In addition, the qualitative results also demonstrate the proposed method generates more reasonable shape completion.

Ablation Study
The performance improvement of GRNet should be attributed to three key components, including Gridding, Cubic Feature Sampling, and Gridding Loss. To demonstrate the effectiveness of each component in the proposed method, we evaluate the performance with different parameters. Gridding. Table 5 shows the results of different resolutions of 3D grids generated by Gridding. The F-Score of final completed point clouds increases with the 3D grids' resolutions. However, the numbers of parameters and the backward time also increases. To archive a balance between effect and efficiency, we choose the resolution of size 64 3 for Gridding in GRNet. Cubic Feature Sampling. To quantitatively evaluate the effect of Cubic Feature Sampling, we compare the performance without Cubic Feature Sampling and with different feature maps fed into it. The experimental results presented in Table 6 indicate that Cubic Feature Sampling improves the point cloud completion results significantly. In addition, with more feature maps are fed, the completion quality becomes better without a significant increase in the numbers of parameters and backward time. Gridding Loss. We further validate the effects of Gridding Loss, as shown in Table 7. There is a decrease in terms of both CD and F-Score when removing Gridding Loss. When increasing the resolution of 3D grids from 64 3 to 128 3 , there are 25.9% and 5.4% improvements in CD and F-Score, respectively.

Conclusion
In this paper, we study how to recover the complete 3D point cloud from an incomplete one. The main motivation of this work is to enable the convolutions on 3D point clouds while preserving their structural and context information.
To this aim, we introduce 3D grids as intermediate representations to regularize unordered point clouds. We then propose a novel Gridding Residual Network (GRNet) for point cloud completion, which contains three novel differentiable layers: Gridding, Gridding Reverse, and Cubic Feature Sampling, as well as a new Gridding Loss. Extensive comparisons are conducted on the ShapeNet, Com-pletion3D, and KITTI benchmarks, which indicate that the proposed GRNet performs favorably against state-of-the-art methods.
A More Explanations on Gridding, Gridding Reverse, and Cubic Feature Sampling

A.1 Gridding
According to the main paper, given a vertex v i and its neighboring points p ∈ N (v i ). The proposed Gridding layer computes the corresponding value w i of this vertex v i as where |N (v i )| is the number of neighboring points of v i and w(v i , p) is defined as Based on Equations 17 and 18, the partial derivative with respect to x can be calculated as follows where x and x v i are the x-coordinates of the point p and vertex v i , respectively. Similarly, the partial derivative with respect to y and z can be calculated as follows where y and y v i are the y-coordinates of the point p and vertex v i , respectively. z and z v i are the z-coordinates of the point p and vertex v i , respectively.

A.2 Gridding Reverse
Point Coordinates Normalization. Gridding Reverse generates point p c i = (x c i , y c i , z c i ) for the i-th grid cell by a weighted combination of eight vertices {v θ |θ ∈ Θ i } and the corresponding values {w θ |θ ∈ Θ i } in this cell, which is calculated as where θ∈Θ i w θ = 0 and Θ i = {θ i j } 8 j=1 represents the index set of vertices of this 3D grid cell. Let (x v θ , y v θ , z v θ ) be the coordinate of the vertex v θ , where

B Additional Quantitative Results on ShapeNet
According to the main paper, the Chamfer Distance is with L2 norm. However, PCN [9] adopts the Chamfer Distance with L1 norm as an evaluation metric, which can be formulated as follows where is the reconstructed point set being evaluated. n T and n R are the numbers of points of T and R, respectively. Table 8 shows the results of point cloud completion using the Chamfer Distance calculated with Equation 34. The values of PCN are exactly the same as Table 4 in the original paper 3 .

C Additional Quantitative Results on KITTI
PCN [9] uses the Fidelity Distance (FD) and Minimal Matching Distance (MMD) as evaluation metrics for KITTI. FD is the average distance from each point in the input to its nearest neighbor in the output, which can be defined as follows   where I denotes the input point cloud. MMD is the Chamfer Distance (CD) between the output and the car point cloud from ShapeNet that is the closest to the output point cloud in terms of CD. The Fidelity and MMD on KITTI of the compared methods are shown in Table 9. However, both FD and MMD are not suitable metrics for KITTI. As shown in Figure 5, real-world LiDAR scans usually contain clutters which should be removed in the recovered point cloud. MSN [30] incorporates the minimum density sampling (MDS) to preserve the structure of the input point cloud. Although MSN outperforms other methods in terms of FD, the clutters in the input point cloud are also preserved. MMD measures how much the output resembles the cars in ShapeNet. However, cars from ShapeNet cannot cover all types of cars in the real world.

D Additional Ablation Studies
Number of Sampling Points. Gridding Reverse generates a coarse point cloud from a 3D grid. We randomly sample 2,048 points from the coarse point cloud to generate a point cloud containing a fixed number of points for the following MLP. Table 10 shows the Chamfer Distance (CD) and F-Score@1% with different numbers of points sampled.
Experimental results indicate that sampling 2,048 points from the coarse point clouds archives the best performance in terms of CD and F-Score. The Table 9. Results of point cloud completion on KITTI compared using Fidelity Distance (CD) and Minimal Matching Distance (MMD) computed on 16,384 points. Note that both FD and MMD are with L2 norm. The best results are highlighted in bold.

E More Qualitative Comparisons
In this section, we provide more visual comparisons with the state-of-the-art methods [9,29,51,11,30] for point cloud completion on ShapeNet [46].


extfieldsofstudy:
Medicine
Computer Science

text:
SPOTONE: Hot Spots on Protein Complexes with Extremely Randomized Trees via Sequence-Only Features

Protein Hot-Spots (HS) are experimentally determined amino acids, key to small ligand binding and tend to be structural landmarks on protein–protein interactions. As such, they were extensively approached by structure-based Machine Learning (ML) prediction methods. However, the availability of a much larger array of protein sequences in comparison to determined tree-dimensional structures indicates that a sequence-based HS predictor has the potential to be more useful for the scientific community. Herein, we present SPOTONE, a new ML predictor able to accurately classify protein HS via sequence-only features. This algorithm shows accuracy, AUROC, precision, recall and F1-score of 0.82, 0.83, 0.91, 0.82 and 0.85, respectively, on an independent testing set. The algorithm is deployed within a free-to-use webserver, only requiring the user to submit a FASTA file with one or more protein sequences.

Introduction
Hot-Spots (HS) can be defined as amino acid residues that upon alanine mutation generate a change in binding free energy (∆∆G binding ) higher than 2.0 kcal mol −1 , in opposition to Null-Spots (NS), which are unable to meet this threshold. Although the threshold of 2.0 kcal mol −1 can vary in the definition of HS, a representative amount of studies on the subject typically use this cut-off [1][2][3][4][5][6]. HS are key elements in Protein-Protein Interactions (PPIs) and, as such, fundamental for a variety of biochemical functions. The disruption of these interactions can alter entire pathways and is of interest to therapeutic approaches [1,7]. These residues are also known to be important for protein dimerization [8] and ligand binding [9]. Indeed, HS tend to be associated with the binding of small ligands, hence becoming ideal subjects of study on target proteins for drug design approaches [9][10][11].
Databases of experimental determined HS and NS can be found in the literature: ASEdb [12], BID [13], PIN [14] and SKEMPI [15]. More recently, SKEMPI 2.0 was released, making available a larger amount of experimental information. However, most of the new information does not include mutations to alanine (and the corresponding change in free binding energy), which is the material under scope in the present work [16]. These databases can be used to deploy Machine-Learning (ML) algorithms that take both the positive (HS) and negative (NS) information and construct a binary classifier that should be able to predict, upon previously unforeseen amino acid residues in a protein, its HS/NS status. Although ML is not limited to binary classification, on this problem and given the available data format, binary classification was the most explored approach until now. Several algorithms have been proposed for HS computational predictions, using different ML approaches, features and datasets [17][18][19][20][21][22][23][24][25]. Recently (2017), SPOTON [22], using information on both the protein sequence and structure, achieved results of 0.95 accuracy on an independent testing set, making it the best performing HS predictor at the time. Most of the high-performing HS predictors incorporate structural information. Although yielding clearly robust results, it hinders the possibilities of a broader deployment, since there are still fewer proteins for which a three-dimensional (3D) structure is available in online repositories [26] compared to the determined and available protein sequences [27]. It is known that sequence-based predictors tend to perform more poorly, in comparison with the ones engulfing structural information. For example, Nguyen et al. (2013) [19] were able to achieve an accuracy of 0.79 and a precision of 0.75 using sequence-based frequency-derived features. More recently, Hu et al. (2017) [20] achieved an F1-score of 0.80 using only sequence-based features while Liu et al. (2018) [21] achieved an F1-score of 0.86 using sequence-based features and amino acid relative Solvent Accessible Surface Area (SASA). The problem of HS computational determination is usually riddled with class imbalance, as there are commonly more experimentally determine residues as NS than HS due to the nature of PPIs. Conversely, the size of the dataset is usually not large enough to dilute this discrepancy. As such, problems emerge on the dataset training, but, more importantly, on the analysis of the results. We developed SPOTONE (hot SPOTs ON protein complexes with Extremely randomized trees), a HS predictor that only makes use of protein sequence-based features, all of which were calculated with an in-house Python pipeline. To avoid protein-centered overfitting, features concerning the whole protein were not applied to the classification problem. This allowed us to avoid the predictor from learning HS/NS only on a specific subset of proteins and be able to correctly classify even for unforeseen subtypes of biological machineries. Furthermore, we deployed a rigorous train-test split that ensured equality among classes, not only in the training and testing datasets, but also regarding the amino acid types. The resulting platform and predictor are available at: http://moreiralab/resources/spotone.

Results
The results presented herein were attained following a ML pipeline, depicted in Figure 1, which lays the overall steps involved in dataset preparation and prediction model training and refinement. The detailed version of each step is further explored in the Material and Methods Section.

Dataset
We began by analyzing our dataset, the same previously mined and cleaned for SPOTON [22], composed by 534 amino acid residues, of which 127 are HS and 407 are NS, from 53 protein-protein complexes. Figure 2A shows the class distribution by amino acid type. Clearly, TYR, one of the most common HS in nature, is an outlier. Secondly, it should be noted that MET and CYS have no registered HS. Finally, it should also be noted that, due to the nature of the method used for HS experimental determination, there are no ALA residues in either the HS or NS class (as already explained). Figure 2B shows the split of the protein primary sequences into four equally long quartiles, which allowed us to analyze the HS/NS distribution along these ordered sections. It should be noted that, in the first quartile of the protein, the number of HS is at its highest value, although the number of NS is not equally as high. In the last quartile of the protein sequences, the number of overall registered HS/NS is the lowest; however, the proportion in which they stand favors the existence of HS rather than NS, in comparison with the remaining quartiles. The comparison with the literature-based features can be consulted at the landing page of our website. These features include secondary structure propensity, pKa associated values, number of atoms of each type and standard area and mass associated values. Their analyses can show tendencies of these features that correlate to their usefulness to the ML deployment. Firstly, the 534 amino acids were split into experimentally determined HS (127) and NS (407). Secondly, 60% of the entries of both classes were randomly picked for the train dataset while the remaining 40% were not used for the training phase (20% for test and 20% for an independent test). All datasets were matched with their corresponding 173 features. The training data were used to train the models, which were tested on the test set to yield HS/NS predictions. The predictions were then used to update probability thresholds and generate the final model, which basically consists of the trained model with subsequent HS probability correction. The final model was then applied to an independent test, which did not influence any step of the process, in order to be evaluated. More details on the used method can be found in the Materials and Methods Section.

Machine-Learning Algorithms
Tables A1 and A2 in the Appendix A list the full results attained for the various algorithms and methods. Table A1 shows that the in-house built features subset displayed one of the highest performance metrics in comparison with any of the other features alone. It can be noticed that PSSM led to a slight improvement, but the small difference of performance does not compensate the larger amount of time needed for this feature calculation. The introduction of iFeatures, concerning the whole protein, did not increase significantly the performance and introduced concerns related to protein-centered overfitting, and as such was discarded of further studies.
The extremely randomized trees took the lead in most performance metrics, and it is clearly more robust in what concerns the identification of HS, as denoted by the high recall score. It should be noted that neither grid search parameter tuning nor prediction probability tuning according to amino acid type performance was used before method selection to keep the independent test unbiased (further explained in the Material and Methods Section). As such, all values presented in Table 1 concern default settings. This allowed the selection of extremely randomized trees algorithm for parameter tuning, as well as subsequent required alterations. To avoid the adaptation introduced and displayed in Table A3 leading to the generation of false positives, we set half of the testing set aside, comprising 20% of the whole dataset. Table 2, which lists the performance metrics of the parameter-tuned adapted model for both the training and the testing set, shows a significant increase in the testing performance, while the training scores remain unchanged. This trend was further validated by deploying the model in the independent testing set. Table 2. Performance metrics on the same training and testing sets after updating the prediction thresholds, and evaluated using the metrics accuracy (Acc), AUROC, precision (Prec), recall (Rec) and F1-score (F1). It should be noted that the "class_weight" parameter, available on the deployment of the extremely randomized trees used was particularly relevant in tackling class imbalance, since, by setting it to "balanced_subsample", it generates and updates class weights based on the samples. A full comparison with state-of-the-art predictions is shown in Table 3. Apart from SPOTON [22], two values for each performance metric are listed: on the left is the value assessed with the dataset used on SPOTONE and on the right are the values presented in the corresponding scientific papers for each method. These values were attained from the pipeline used in SPOTON [22]; since the dataset is the same, the performance comparison also stands equal. In the case of the sequence-based methods that are not SPOTONE, we were not able to deploy our dataset as the webservers indicated were not active or available; this applies to the methods of Nguyen

Discussion
This work presents a significant improvement in HS prediction at the interface of protein-protein complexes. However, more than the high performing metrics, the robustness of this model emerges from a thorough treatment and splitting of the dataset, as well as from the exclusion of whole protein sequence features, leaving only residue specific sequence-based features. Figures A1-A3 display the performance of SPOTONE upon being applied to three different complexes (PDB ids: 1a4y, 1jck and 3sak), with insights on all the residues experimentally determined for these complexes and comparison of this information to our HS/NS SPOTONE prediction. These three examples clearly show how well the predictor works on a point-by-point example. Our final accuracy (0.82), recall (0.82) and precision (0.91) highlight the existence of a very low number of falsely predicted HS as well as NS. Its closeness in performance to the best structural based predictor is complemented with the high versatility of using only sequence-based features prediction, which allows a much wider application in a variety of biological problems.
Finally, all the work is available in a free-to-use platform that allows the user to input one or more protein sequences in FASTA format (Box 1) and attain a detailed HS/NS prediction with corresponding graphical interface. The platform is available at http://moreiralab.com/resources/spotone. Box 1. Example FASTA file, with the different proteins' chains separated by paragraphs and clear identifiers initiated with ">", separated from the single letter amino acid code chain with a paragraph. This needs to be stored in a ".fasta" file to be submitted to SPOTONE.

Materials and Methods
The dataset used here was retrieved from our previous method, SPOTON [22], and is comprised of 534 amino acid residues (127 positive-HS and 407 negative-NS). This dataset was constructed of data merged from the experimental databases ASEdb [12], BID [13], PINT [14] and SKEMPI [15], and as such comprises all literature available experimental data coming from alanine scanning mutagenesis. We also highlight that sequence redundancy was already eliminated in our previous work. To address this particular problem, we did not simply split the 534 samples into training and testing sets. Firstly, we split all the samples into two datasets containing either HS or NS. Of these datasets, we extracted 20 different subsets from each (corresponding to the 20 possible amino acids). We randomly split these 40 sets (20 HS subsets and 20 NS subsets) in a 60:40 ratio, using "train_test_split" from scikit-learn [28]. Finally, we stitched the tables corresponding to the training set and the testing set back together. Our process was devised to ensure that HS and NS were equally represented for each residue in both the training set and the testing set. Unfortunately, ALA entries were completely absent from the dataset (due to the experimental detection method typically used in wet labs) and CYS and MET only had NS entries (as these residues have a lower/null incidence as key in PPIs). For the latter two cases, we included them in the training set, as it would not be possible to assay their presence in the testing set. Following this procedure, we ended up with a training set containing 312 residues and a testing set containing 222 residues. We randomly split the final testing set in two, with 111 residues each; half the testing set was used to fine-tune probability thresholds (see Prediction Probability Tuning), while the other half was set aside for fully independent test analysis, only having been used after selecting the ML model and performing all parameter tuning.

Features
The following section reports the calculation of 173 features with an in-house Python pipeline and literature-based information on amino acid characteristics. All the extracted features can be calculated simply using the input sequence of a FASTA file. It should be noted that we only used sequence-based features and, furthermore, we did not add any sequence feature about the protein as a "whole", which might have, due to the size of the dataset, promoted overfitting on a protein level. As shown in Tables A1 and A2, pre-constructed whole-sequence based features and Position-Specific Scoring Matrix (PSSM) were also tested. For the first, we used iFeature [29] and attained 14.056 whole sequence-based features, for each of the chains. For PSSM, we used an in-house psiblast [30] deployment to extract 42 position conservation features.

One-hot Encoding (20 Features)
The first twenty features extracted for each amino acid residue were simply a one-hot encoded representation of the amino acid; thus, for each amino acid, nineteen columns were filled with "0", and only one (with the corresponding value), was filled with "1".

Relative Position Feature (1 Feature)
In Figure 2B, we display the abundance of NS/HS on the protein sequence quartiles. The quartiles were defined by splitting the proteins' length by four and analyzing the residues present in each of the sections. As such, we used the numbering 1-4 (representing its relative position in the sequence) as a feature that indicates the quartile in which each amino acid is present.

Literature-Based Features (19 Features)
Several amino acid properties are constantly determined, updated and made available online. We downloaded 19 amino acid properties from the BioMagResBank [31] and associated each of them with each of the amino acids; the features and corresponding values per amino acid used are listed in Tables A4 and A5. Please note that this database is regularly updated to improve the reliability of the experimental data. The statistical distribution of these properties regarding their HS/NS on the dataset used are available in form of violin, scatter and boxplots on the landing page (http://www.moreira.com/resources/spotone).

Window-Based Features (133 Features)
Window-based features were described with a "sliding windows" that stopped on the target residue and considered the residues that stand close to it, sequence wise. We considered window sizes of 2, 5, 7, 10, 25, 50 and 75 amino acid residues, and, for each target residue, averaged the values corresponding to the features of in the Literature-Based Features Section on the residues comprised in the windows. Thus, if we multiply the number of raw features (19) by the number of windows (7), we added 133 features.

Machine-Learning Models Deployment
We exploited different algorithms: Neural Networks ("MLPClassifier") [32], Random Forest ("RandomForestClassifier") [33], AdaBoost ("AdaBoostClassifier"), Support Vector Machine ("SVC") [34] and Extremely Randomized Trees ("ExtraTreesClassifier") [35]. All of the algorithms were used from their scikit-learn [28] deployment. The extremely randomized trees algorithm, similar to a random forest, is based on decision trees. From the training set, the algorithm picks attributes at random and generates subsets; by training these on the decision trees that comprise the model, an ensemble model is built by majority vote. However, one of the main differences to other algorithms is that it chooses node cut-points (the bifurcation points' thresholds in a decision tree) fully at random; another significant difference is that the full training set is used, instead of a bootstrap replica, for each of the decision trees that comprise the ensemble model. This additional randomization is ideal in small datasets, in which overfitting is more likely to occur on the training set without a proper test evaluation of robustness. This method has proven to have successful results in solving other biological based problems [36,37]. After running all the methods in default scikit-learn [28] settings, we fine-tuned some parameters of the extremely randomized trees [35] with a grid search ("GridSearchCV", scikit-learn [28]), and the following parameters were updated: "n_estimators": 500; "bootstrap": True; and class_weight: "balanced_subsample". The full set of parameters can be consulted in Table A6, the parameters not referred were kept as default. Grid search was performed with 10-fold cross-validation.

Model Evaluation
To evaluate the models, we subjected both the training and the testing set to confusion matrix analysis. This table relates the actual and the predicted instances (sample) and compares them by their binary status of Negative (N) or Positive (P) in the prediction to their actual class of True (T) or False (F). It further relates these in four different possible combination states: True Negative (TN) is when the prediction is N and the actual is F; True Positive (TP) is when the prediction is P and the actual is T; False Negative (FN) is when the prediction is N and the actual is T; and False Positive (FP) is when the prediction is P and the actual is F.

Prediction Probability Tuning
We performed further inspection of the HS/NS prediction by amino acid, in addition to the whole dataset, as can be seen in the "original" rows in Table A3. This inspection led us to notice that the HS/NS ratio had a significant toll in model performance. For example, TYR had a robust prediction of HS/NS; however, residues which had not such a balanced HS/NS ratio performed more poorly. Although this is a classification problem, most classification methods calculate class probability before yielding the predicted class, which is determined according to the higher probable class. As such, we examined the probability associated to the positive class (HS). Upon inspection of classification probabilities of the actual residues, it was noticed that, although not classified as HS, most of these amino acids still had a higher probability of HS classification than NS. The adaptation value displayed in Table A3 is the increase in probability of the HS class, added post-training, that allows higher HS probability amino acids to reach the HS class (above 50%). This value was implemented following the condition that it should not generate FP while increasing the amount of TP. As such, when, for each amino acid, the maximum false negative HS probability was higher than the maximum true negative HS probability, the HS probability (for that amino acid) was updated (Equation (7)). CYS, MET and ALA were not displayed in Table A3 due to their absence from the testing set.

Webserver Implementation
The webserver was fully implemented with Python. Plotly [38] was used for dynamic graphical representations; scikit-learn [28] was used to perform user submission treatment, analysis and prediction; and in-house Python scripts were used to perform all feature extraction and intermediate steps. Flask was used for overall server set-up and visual layout construction [39]. The output each run includes a dynamic heatmap displaying the probability of HS, for each amino acid in the single or more chains submitted by the user. The full table with the classification probabilities as well as binary class before and after class probability tuning are also available for the user to download. A snapshot of the webserver output is displayed in Figure 3.

Conclusions
SPOTONE is a thorough prediction algorithm that tackles HS classification in a problem-tailored protocol. The pre-processing and ML steps can be the framework for further protein-based structural biology problems, as are innovating in several processes: (1) by highlighting the importance of protein-based overfitting versus amino acid based features; (2) by providing an answer with a set of simple, replicable, in-house features that make use of freely available information and amino acid position; (3) by considering the evaluation of the amino acid prediction capabilities instead of simply the target features at hand; (4) by attributing specific weights to amino acid types as a way to underline that these are not only features but also subsample spaces of the dataset; (5) by introducing a viable sequence-based HS predictor; and (6) by providing an intuitive and biologically relevant data interpretation tool (HS probability maps). Furthermore, SPOTONE as a webserver (http://moreiralab.com/resources/spotone) is easily usable by non-proficient researchers, with an intuitive framework. Acknowledgments: A. J. Preto acknowledges José G. Almeida for thorough discussions on the proper approach towards the problem at hands that yielded fruitful protocol improvements.

Conflicts of Interest:
The authors declare no conflict of interest.
Data and Code Availability: All data and code used to perform the described experiences are available at https://github.com/MoreiraLAB/spotone. Table A1. Performance metrics (training and testing datasets) for the three studied subsets: with only the in-house features (one-hot encoding, relative position, literature based and window-based features), using only PSSM features and the joint dataset with both in-house and PSSM features.

Dataset
Classifier Name Subset Accuracy AUC Precision Recall F1-Score   . Depiction the complex between a T-Cell receptor beta chain and SEC3 superantigen: PDB ID 1jck. Brighter red colors were attributed to residues with a higher probability of being classified as HS. (B,C) Close-ins of all interfacial residues for which there is an experimental ∆∆G binding value, and as such a HS/NS classification. Green boxes represent correctly predicted residues, whereas red boxes represent incorrectly classified residues. Figure A3. (A). Depiction of chain C of the complex PDB ID 3sak. Brighter red colors were attributed to residues with a higher probability of being classified as HS. (B,C) Close-ins of all interfacial residues for which there is an experimental ∆∆G binding value, and as such a HS/NS classification. Green boxes represent correctly predicted residues, whereas red boxes represent incorrectly classified residues.