Unsupervised Image Classification for Deep Representation Learning

Deep clustering against self-supervised learning is a very important and promising direction for unsupervised visual representation learning since it requires little domain knowledge to design pretext tasks. However, the key component, embedding clustering, limits its extension to the extremely large-scale dataset due to its prerequisite to save the global latent embedding of the entire dataset. In this work, we aim to make this framework more simple and elegant without performance decline. We propose an unsupervised image classification framework without using embedding clustering, which is very similar to standard supervised training manner. For detailed interpretation, we further analyze its relation with deep clustering and contrastive learning. Extensive experiments on ImageNet dataset have been conducted to prove the effectiveness of our method. Furthermore, the experiments on transfer learning benchmarks have verified its generalization to other downstream tasks, including multi-label image classification, object detection, semantic segmentation and few-shot image classification.

Introduction
Deep convolutional neural networks (CNN) [17,20,5] had been applied to many computer vision applications [15,27,26] due to their powerful representational capacity. The normal working flow is to pretrain the networks on a very largescale dataset with annotations like ImageNet [33] and then transfer to a small dataset via fine-tuning. However, the dataset collection with manually labelling for pre-training is strongly resource-consuming, which draws lots of researchers' attention to develop unsupervised representation learning approaches.
Among the existing unsupervised learning methods, self-supervision is highly sound since it can directly generate supervisory signal from the input images, like image inpainting [8,32] and jigsaw puzzle solving [29]. However, it requires rich empirical domain knowledge to design pretext tasks and is not well-transferred to downsteam tasks. Compared with this kind of self-supervised approaches, Deep-Cluster is a simple yet effective method which involves litter domain knowledge. It simply adopts embedding clustering to generate pseudo labels by capturing the manifold and mining the relation of all data points in the dataset. This process is iteratively alternated with an end-to-end representation learning which is exactly the same with supervised one. However, along with the advantage brought by embedding clustering, an obvious defect naturally appears that the latent embedding of each data point in the dataset should be saved before clustering, which leads to extra memory consumption linearly growing with the dataset size. It makes it difficult to scale to the very large-scale datasets. Actually, this problem also happens in the work of DeeperCluster [3], which uses distributed kmeans to ease the problem. However, it still did not solve the problem in essence. Also, the data points in most of datasets are usually independently identically distributed (i.i.d ). Therefore, building a framework analogous to DeepCluster, we wonder if we can directly generate pseudo class ID for each image without explicitly seeing other images and take it as an image classification task for representation learning.
The answer is excitedly YES! We integrate both the processes of pseudo label generation and representation learning into an unified framework of image classification. Briefly speaking, during the pseudo label generation, we directly feed each input image into the classification model with softmax output and pick the class ID with highest softmax score as pseudo label. It is very similar to the inference phase in supervised image classification. After pseudo class IDs are generated, the representation learning period is exactly the same with supervised training manner. These two periods are iteratively alternated until convergence. A strong concern is that if such unsupervised training method will be easily trapped into a local optima and if it can be well-generalized to other downstream tasks. In supervised training, this problem is usually solved by data augmentation which can also be applied to our proposed framework. It is worth noting that we not only adopt data augmentation in representation learning but also in pseudo label generation. It can bring disturbance to label assignment and make the task more challenging to learn data augmentation agnostic features. The entire pipeline is shown in Fig.1. To the best of our knowledge, this unsupervised framework is the closest to the supervised one compared with other existing works. Since it is very similar to supervised image classification, we name our method as Unsupervised Image Classification (UIC) correspondingly. For simplicity, without any specific instruction, clustering in this paper only refers to embedding clustering via k-mean, and classification refers to CNN-based classification model with cross-entropy loss function.
To further explain why UIC works, we analyze its hidden relation with both deep clustering and contrastive learning. We point out that UIC can be considered as a special variant of them. We hope our work can bring a deeper understanding of deep clustering series work to the self-supervision community.
We empirically validate the effectiveness of UIC by extensive experiments on ImageNet. The visualization of classification results shows that UIC can act as clustering although lacking explicit clustering. We also validate its generalization ability by the experiments on transfer learning benchmarks. All these experiments indicate that UIC can work comparable with deep clustering. To summarize, our main contributions are listed as follows: -A simple yet effective unsupervised image classification framework is proposed for visual representation learning. It closes the gap between supervised and unsupervised learning in format, which can be taken as a strong prototype to develop more advance unsupervised learning methods. -Our framework simplifies DeepCluster by discarding embedding clustering while keeping no performance degradation and surpassing most of other unsupervised learning methods. -We connect our proposed unsupervised image classification with deep clustering and contrastive learning for further interpretation. It helps us understand why this framework works.
2 Related Work 2.1 Self-supervised learning Self-supervised learning is a major form of unsupervised learning, which defines pretext tasks to train the neural networks without human-annotation, including image inpainting [8,32], automatic colorization [24,41], rotation prediction [14], cross-channel prediction [42], image patch order prediction [29], and so on. These pretext tasks are designed by directly generating supervisory signals from the raw images without manually labeling, and aim to learn well-pretrained representations for downstream tasks, like image classification, object detection, and semantic segmentation. Recently, contrastive learning [35,16,19,31] is developed to improve the performance of self-supervised learning. Its corresponding pretext task is that the features encoded from multi-views of the same image are similar to each others. The core insight behind these methods is to learn multi-views invariant representations. This is also the essence of our proposed method.

Clustering-based methods
Clustering-based methods are mostly related to our proposed method. Coates et al. [7] is the first to pretrain CNNs via clustering in a layer-by-layer manner.
The following works [39,38,25,2] are also motivated to jointly cluster images and learn visual features. Among them, DeepCluster [2] is one of the most representative methods in recent years, which applies k-means clustering to the encoded features of all data points and generates pseudo labels to drive an end-to-end training of the target neural networks. The embedding clustering and representation learning are iterated by turns and contributed to each other along with training. Compared with other self-supervised methods with fixed pseudo labels, this kind of works not only learn good features but also learn meaningful pseudo labels. However, as a prerequisite for embedding clustering, it has to save the latent features of each sample in the entire dataset to depict the global data relation, which leads to excessive memory consumption and constrains its extension to the very large-scale datasets. Although another work DeeperCluster [3] proposes distributed k-means to ease this problem, it is still not efficient and elegant enough. Another work SelfLabel [1] treats clustering as a comlicated optimal transport problem. It proposes label optimization as a regularized term to the entire dataset to simulate clustering with the hypothesis that the generated pseudo labels should partition the dataset equally. However, it is hypothesized and not an i.i.d solution. Interestingly, we find that our method can naturally divide the dataset into nearly equal partitions without using label optimization, which may be caused by balanced sampling training manner. Another modeling is ExemplarCNN [11]. It extracts a patch from each image and applies a set of data augmentations for each patch randomly to form surrogate classes to drive representation learning. However, it cannot scale to larger datasets since most of the surrogate classes become similar as class number increases and discounts the performance. Our method can break this limitation.

Preliminary: Deep Clustering
Before introducing our proposed unsupervised image classification method, we first review deep clustering to illustrate the process of pseudo label generation and representation learning, from which we analyze the disadvantages of embedding clustering and dig out more room for further improvement.

Pseudo Label Generation.
Most self-supervised learning approaches focus on how to generate pseudo labels to drive unsupervised training. In deep clustering, this is achieved via k-means clustering on the embedding of all provided training images X = x 1 , x 2 , ..., x N . In this way, the images with similar embedding representations can be assigned to the same label.
Commonly, the clustering problem can be defined as to optimize cluster centroids and cluster assignments for all samples, which can be formulated as: where f θ (·) denotes the embedding mapping, and θ is the trainable weights of the given neural network. C and y n separately denote cluster centroid matrix with shape d × k and label assignment to n th image in the dataset, where d, k and N separately denote the embedding dimension, cluster number and dataset size. For simplicity in the following description, y n is presented as an one-hot vector, where the non-zero entry denotes its corresponding cluster assignment.
Representation Learning. After pseudo label generation, the representation learning process is exactly the same with supervised manner. To this end, a trainable linear classifier W is stacked on the top of main network and optimized with θ together, which can be formulated as: where l is the loss function. Certainly, a correct label assignment is beneficial for representation learning, even approaching the supervised one. Likewise, a disentangled embedding representation will boost the clustering performance. These two steps are iteratively alternated and contribute positively to each other during optimization.
Analysis. Actually, clustering is to capture the global data relation, which requires to save the global latent embedding matrix E ∈ R d×N of the given dataset. Taking k-means as an example, it uses E to iteratively compute the cluster centroids C. Here naturally comes a problem. It is difficult to scale to the extremely large datasets especially for those with millions or even billions of images since the memory of E is linearly related to the dataset size. Thus, an existing question is, how can we group the images into several clusters without explicitly using global relation? Also, another slight problem is, the classifier W has to reinitialize after each clustering and train from scratch, since the cluster IDs are changeable all the time, which makes the loss curve fluctuated all the time even at the end of training.

Unsupervised Image Classification
From the above section, we can find that the two steps in deep clustering (Eq.1 and Eq.2) actually illustrate two different manners for images grouping, namely clustering and classification. The former one groups images into clusters relying on the similarities among them, which is usually used in unsupervised learning. While the latter one learns a classification model and then directly classifies them into one of pre-defined classes without seeing other images, which is usually used in supervised learning. For the considerations discussed in the above section, we can't help to ask, why not directly use classification model to generate pseudo labels to avoid clustering? In this way, it can integrate these two steps pseudo label generation and representation learning into a more unified framework. Here pseudo label generation is formulated as: where f θ (·) is the network composed by f θ (·) and W . Since cross-entropy with softmax output is the most commonly-used loss function for image classification, Eq.3 can be rewritten as: where p(·) is an arg max function indicating the non-zero entry for y n . Iteratively alternating Eq.4 and Eq.2 for pseudo label generation and representation learning, can it really learn a disentangled representation? Apparently, it will easily fall in a local optima and learn less-representative features. The breaking point is data augmentation which is the core of many supervised and unsupervised learning algorithms. Normally, data augmentation is only adopted in representation learning process. However, this is not enough, which can not make this task challenging. Here data augmentation is also adopted in pseudo label generation. It brings disturbance for pseudo label, and make the task challenging enough to learn more robust features. Hence, Eq.4 and Eq.2 are rewritten as: where t 1 (·) and t 2 (·) denote two different random transformations. The entire pipeline of our proposed framework is illustrated in Fig.1. Since our proposed method is very similar to the supervised image classification in format. Correspondingly, we name our method as unsupervised image classification. Compared with deep clustering, our method is more simple and elegant. It can be easily scaled to large datasets, since it does not need global latent embedding of the entire dataset for image grouping. Further, the classifier W is optimized with the backbone network simultaneously instead of reinitializing after each clustering. To some extent, our method makes it a real end-to-end training framework.

Interpretation
The Relation with Embedding Clustering. Embedding clustering is the key component in deep clustering methods, which mainly focuses on three aspects: 1) sample embedding generation, 2) distance metric, 3) grouping manner (or cluster centroid generation). Actually, from these three aspects, using image classification to generate pseudo labels can be taken as a special variant of embedding clustering, as visualized in Fig.2. Compared with embedding clustering, the embedding in classification is the output of softmax layer and its dimension is exactly the class number. Usually, we call it the probability assigned to each class. As for distance metric, compared with the euclidean distance used in embedding clustering, cross-entropy can also be considered as an distance metric used in classification. The most significant point is the grouping manner. In k-means clustering, the cluster centroids are dynamicly determined and iteratively updated so as to reduce the intra-classes distance and enlarge the inter-classes distance. Conversely, the class centroids for classification are predefined and fixed as k orthonormal one-hot vectors, which helps directly classify images via cross-entropy.
Briefly speaking, the key difference between embedding clustering and classification is whether the class centroids are dynamicly determined or not. In Deep-Cluster [2], 20-iterations k-means clustering is operated, while in DeeperCluster [3], 10-iterations k-means clustering is enough. It means that clustering actually is not that important. Our method actually can be taken as an 1-iteration variant with fixed class centroids. Considering the representations are still not well-learnt at the beginning of training, both clustering and classification cannot correctly partition the images into groups with the same semantic information. During training, we claim that it is redundant to tune both the embedding features and class centroids meanwhile. It is enough to fix the class centroids as orthonormal vectors and only tune the embedding features. Along with representation learning drived by learning data augmentation invariance, the images with the same semantic information will get closer to the same class centroid. What's more, compared with deep clustering, the class centroids in UIC are consistent in between pseudo label generation and representation learning.
The Relation with Contrastive Learning. Contrastive learning has become a popular method for unsupervised learning recently. Implicitly, unsupervised image classification can also be connected to contrastive learning to explain why it works. Although Eq.5 for pseudo label generation and Eq.6 for representation learning are operated by turns, we can merge Eq.5 into Eq.6 and get: which is optimized to maximize the mutual information between the representations from different transformations of the same image and learn data augmentation agnostic features. This is a basic formula used in many contrastive learning methods. More concretely, as mentioned above, we fix k orthonormal one-hot vectors as class centroids. When compared with contrastive learning methods, referring to the Eq.7, our method use a random view of the images to select their nearest class centroid, namely positive class, in a manner of taking the argmax of the softmax scores. During optimization, we push the representation of another random view of the images to get closer to their corresponding positive class. Implicitly, the remaining k -1 classes will automatically turn into negative classes. Since we use cross-entropy with softmax as the loss function, they will get farther to the k -1 negative classes during optimization. Intuitively, this may be a more proper way to generate negative samples. In normal contrastive learning methods, given an image I in a minibatch (large batchsize), they treat the other images in the minibatch as the negative samples. But there exist the risk that the images in these negative samples may share the same semantic information with I.

Dataset Benchmarks and Network Architectures
We mainly apply our proposed unsupervised image classification to ImageNet dataset [33] without annotations, which is designed for 1000-categories image classification consisting of 1.28 millions images. As for network architectures, we select the most representative one in unsupervised representation learning, AlexNet [23], as our baseline model for performance analysis and comparison. It is composed by five convolutional layers for features extraction and three fullyconnected layers for classification. Note that the Local Response Normalization layers are replaced by batch normalization layers. After unsupervised training, the performance is mainly evaluated by linear probes; transfer learning on downstream tasks.
Linear probes [42] had been a standard metric followed by lots of related works. It quantitatively evaluates the representation generated by different convolutional Table 1. Ablation study on class number selection. Here we also report NMI t/labels, which denotes the NMI between pseudo labels and annotated labels.

Methods
Top1 Accuracy NMI t/labels conv3 conv4 conv5 UIC 3k 41. 2  layers through separately freezing the convolutional layers (and Batch Normalization layers) from shallow layers to higher layers and training a linear classifier on top of them using annotated labels. For evaluation by linear probing, we conduct experiments on ImageNet datasets with annotated labels. Linear probes is a direct approach to evaluate the features learnt by unsupervised learning through fixing the feature extractors. Compared with this approach, transfer learning on downsteam tasks is closer to practical scenarios. Following the existing related works, we transfer the unsupervised pretrained model on ImageNet to PAS-CAL VOC dataset [12] for multi-label image classification, object detection and semantic segmentation via fine-tuning. To avoid the performance gap brought by hyperparameter difference during fine-tuning, we further evaluate the representations by metric-based few-shot classification task on mini ImageNet [36] without fine-tuning.

Unsupervised Image Classification
Implementation Details. Similar to DeepCluster, two important implementation details during unsupervised image classification have to be highlighted: -Avoid empty classes; -Class balance sampling.
At the beginning of training, due to randomly initialization for network parameters, some classes are unavoidable to assign zero samples. To avoid trivial solution, we should avoid empty classes. When we catch one class with zero  samples, we split the class with maximum samples into two equal partitions and assign one to the empty class. We observe that this situation of empty classes only happens at the beginning of training. As for class balance sampling, this technique is also used in supervised training to avoid the solution biasing to those classes with maximum samples.
Optimization Settings. We optimize AlexNet for 500 epochs through SGD optimizer with 256 batch size, 0.9 momentum, 1e-4 weight decay, 0.5 drop-out ratio and 0.1 learning rate decaying linearly. Analogous to DeepCluster, we apply Sobel filter to the input images to remove color information. During pseudo label generation and representation learning, we both adopt randomly resized cropping and horizontally flipping to augment input data. Compared with standard supervised training, the optimization settings are exactly the same except one extra hyperparameter, class number. Since over-clustering had been a consensus for clustering-based methods, here we only conduct ablation study about class number from 3k, 5k to 10k.
Evaluation via Normalized Mutual Information. Normalized mutual information (NMI) is the main metric to evaluate the classification results, which ranges in the interval between 0 and 1. If NMI is approaching 1, it means two label assignments are strongly coherent. The annotated labels are unknown in practical scenarios, so we did not use them to tune the hyperparameters. But if the annotated labels are given, we can also use the NMI of label assignment against annotated one (NMI t/labels) to evaluate the classification results after training. As shown in the fifth column in Tab.1, when the class number is 10k, the NMI t/labels is comparable with DeepCluster (refer to Fig.2(a) in the paper [2]), which means the performance of our proposed unsupervised image classification is approaching to DeepCluster even without explicitly embedding clustering. However, the more class number will be easily to get higher NMI t/labels. So we cannot directly use it to compare the performance among different class number.
Evaluation via Visualization. At the end of training, we take a census for the image number assigned to each class. As shown in Fig.3, our classification model nearly divides the images in the dataset into equal partitions. This is a interesting finding. In the work of [1], this result is achieved via label optimization solved by sinkhorn-Knopp algorithm. However, our method can achieve the same result without label optimization. We infer that class balance sampling training manner can implicitly bias to uniform distribution. Furthermore, we also visualize the classification results in Fig.4. Our method can classify the images with similar semantic information into one class.

Linear Classification on Activations
Optimization Settings. We use linear probes for more quantitative evaluation. Following [42], we use max-pooling to separately reduce the activation dimensions to 9600, 9216, 9600, 9600 and 9216 (conv1-conv5). Freezing the feature extractors, we only train the inserted linear layers. We train the linear layers for 32 epochs with zero weight decay and 0.1 learning rate divided by ten at epochs 10, 20 and 30. The shorter size of the images in the dataset are resized to 256 pixels. And then we use 224×224 random crop as well as horizontal flipping to train the linear layer. After training, the accuracy is determined on the validation set with 10-crops (center crop and four-corners crop as well as horizontal flipping).
Ablation Study on Class Number Selection. We conduct ablation study on class number as shown in Tab.1. Different from DeepCluster, the performance 3k is slightly better than 5k and 10k, which is also confirmed by [1].
Further Fine-Tuning. During training, the label assignment is changed every epoch. To further validate that our network performane is not just from data augmentation but also from meaningful label assignment, we fix the label assignment at last epoch with center crop inference in pseudo label generation, and further fine-tune the network with 30 epochs. As shown in Tab.2, the performance can be further improved. Ablation Study on Data Augmentation. Data augmentation plays an important role in clustering-based self-supervised learning since the pseudo labels are almost wrong at the beginning of training since the features are still not well-learnt and the representation learning is mainly drived by learning data augmentation invariance at the beginning of training. In this paper, we also use data augmentation in pseudo label generation. As shown in Tab.3, it can improve the performance. In this paper, we simply adopt randomly resized crop to augment data in pseudo label generation and representation learning.
Comparison with Other State-of-The-Art Methods. Since our method aims at simplifying DeepCluster by discarding clustering, we mainly compare our results with DeepCluster. As shown in Fig.4, our performance is comparable with DeepCluster, which validates that the clustering operation can be replaced by more challenging data augmentation. Note that it is also validated by the NMI t/labels mentioned above.
SelfLabel [3k × 1] simulates clustering via label optimization which classifies datas into equal partitions. However, as discussed above in Fig.3, our proposed framework also divides the dataset into nearly equal partitions without label optimization term. Therefore, theoretically, our framework can also achieve com- parable results with SelfLabel [3k × 1], and we impute the performance gap to some detailed hyperparameters settings, such as their extra noise augmentation. Compared with other self-supervised learning methods, our method can surpass most of them which only use a single type of supervisory signal. We believe our proposed framework can be taken as strong baseline model for self-supervised learning and make a further performance boost when combined with other supervisory signals, which will be validated in our future work.

Transfer to Downstream Tasks
Evaluation via Fine-Tuning: Multi-label Image Classification, Object Detection, Semantic Segmentation on Pascal-VOC. In practical scenarios, self-supervised learning is usually used to provide a good pretrained model to boost the representations for downstream tasks. Following other works, the representation learnt by our proposed method is also evaluated by fine-tuning the models on PASCAL VOC datasets. Specifically, we run the object detection task using fast-rcnn [15] framework and run the semantic segmentation task using FCN [27] framework. As shown in Tab.5, our performance is comparable with other clustering-based methods and surpass most of other self-supervised methods. Table 6. Evaluation via few-shot classification on the test set of miniImageNet. Note that 224 resolution is center-cropped from 256 which is upsampled from 84 lowresolutional images. It can be regarded as inserting a upsampling layer at the bottom of the network while the input is still 84×84. MP is short for max-pooling. For reference, the 5way-5shot accuracy of prototypical networks [34]  Evaluation without Fine-Tuning: Metric-based Few-shot Image Classification on mini ImageNet. Few-shot classification [36,34] is naturally a protocol for representation evaluation, since it can directly use unsupervised pretrained models for feature extraction and use metric-based methods for few-shot classification without any finetuning. It can avoid the performance gap brought by fine-tuning tricks. In this paper, we use Prototypical Networks [34] for representation evaluation on the test set of mini ImageNet. As shown in Tab.6, our method is comparable with DeepCluster overall. Specifically, our performances in highest layers are better than DeepCluster.

More Experiments
In the above sections, we try our best to keep training settings the same with DeepCluster for fair comparison as much as possible. Although achieving SOTA results is not the main starting point of this work, we would not mind to further improve our results through combining the training tricks proposed by other methods.

More Data Augmentations
As discussed above, data augmentation used in the process of pseudo label generation and network training plays a very important role for representation learning. Recently, SimCLR [4] consumes lots of computational resources to do a thorough ablation study about data augmentation. They used a strong color jittering and random Gaussian blur to boost their performance. We find such strong augmentation can also benefit our method as shown in Tab.7. Our result in conv5 with a strong augmentation surpasses DeepCluster and SelfLabel by a large margin and is comparable with SelfLabel with 10 heads. Note that the results in this section do not use further fine-tuning. Res50 54.0 -BigBiGAN [10] Res50 56.6 -Local Agg. [43] Res50 60.2 -Moco [16] Res50 60.6 -PIRL [28] Res50 63.6 -CPCv2 [18] Res50 63.8 -SimCLR [4] Res50 + MLP-head 69.3 -Mocov2 [6] Res50 + MLP-head 71.

More Network architectures
We believe our abundant ablation study on ImageNet and the generalization to the downstream tasks had already proven our arguments in this paper. To further convince the readers, we also supplement the experiments of ResNet50 (500epochs) with the strong data augmentation and an extra MLP-head proposed by SimCLR [4] (we fix and do not discard MLP-head when linear probing). As shown in Tab.8, our method surpasses SelfLabel and achieves SOTA results when compared with non-contrastive-learning methods. Although our method still has a performance gap with SimCLR and MoCov2 (>>500epochs), our method is the simplest one among them. We believe it can bring more improvement by appling more data augmentations, tuning the temperature of softmax, optimizing with more epochs, or other useful tricks. We hope our method can be taken as a strong prototype to develop more advanced unsupervised learning methods. And we believe our simple and elegant framework can make SSL more accessible to the community, which is very friendly to the academic development.

Conclusions
We always believe that the greatest truths are the simplest. Our method makes training a SSL model as easy as training a supervised image classification model. And we make SSL more accessible to the community. It validates that even without clustering it can still achieve comparable performance with DeepCluster. This framework is the closest to standard supervised learning framework. It can bring new insights and inspirations to the self-supervision community and can be adopted as a strong prototype to further develop more advanced unsupervised learning approaches.


Presenting the mathematical model to optimize the reliability of the satellite attitude determination and control system

Presenting the mathematical model to optimize the reliability of the satellite attitude determination and control system Akbar Mansouri, Akbar Alem-Tabriz a Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran b Department of Industrial Management, Management and Accounting Faculty, Shahid Beheshti University, Tehran, Iran Abstract The key issue in this study has been the integration of redundancy allocation and optimization of failure rates. The fact that we only need to work with parallel allocation and increase the number of components in a subsystem in parallel to improve the reliability or availability of parallel-series systems is necessary, but not enough. It is worth mentioning that in this research, the improvement of failure rates of different components in the system has been studied. In the meantime, it is important to note that with careful study of the effects of each of these approaches and the costs imposed on the system, the design problem data will be formed. Considering that more effort to improve the reliability of components leads to less redundancy allocation and vice versa, the optimization problem is performed to determine the exact number of redundancies along with determining the exact amount of improvements in complete failure rates. In this research, the satellite attitude determination and control system, the structure of the studied system and its components is introduced, then the reliability in this system is modeled and optimized with a mathematical approach based on the combination of reliability allocation and redundancy allocation. Keyword: Reliability, Satellite, Attitude determination and control system, redundancy allocation problem, Genetic algorithm.

1-Introduction
Satellites are human-made devices that are deliberately sent into space to go around the earth or other planets. The importance of satellites for telecommunications and the study of terrestrial resources and research and military and espionage applications is growing. Part of the scientific and specialized research that is being done in space-based laboratories has never been able to take on a practical dimension on Earth. To control the safety of sensitive systems, such as those in nuclear power plants, chemical processes, and the astronaut system, it is necessary to have readymade safety systems to complete on-line regulatory systems. Ready-to-use systems can automatically operate to keep the system safe and to prevent catastrophic outcomes under various conditions, however, ready-to-operate safety systems may not be able to perform the expected performance due to hidden failures. Therefore, it is very important to investigate these problems during testing and maintenance, and diagnose and resolve maintenance testing in accordance with the manufacturer's recommendations, which are generally cautious recommendations. In sensitive safety applications, the periodic maintenance period is sometimes determined by the supervisory team, for example, strict rules apply to intermittent maintenance to keep the level of uncertainty low. In general, intermittent and frequent testing can increase the likelihood of damage being detected. However, it may cause the system to crash faster due to the increased unnecessary costs imposed on resources. Therefore, logical and efficient testing of maintenance strategy is of great importance in ready-made safety systems.
In this research, by identifying the structure of the satellite attitude determination and control system, as well as the components used in it, the reliability of this system is analyzed and optimized. For this purpose, by investigating the information related to the system under study, the assumptions of modeling and optimizing the system reliability is determined. In this regard, practical and systemic constraints is considered. Finally, report the obtained results.
In this paper, a joint reliability-redundancy optimization approach for satellite attitude determination and control system is presented. This model is developed on a multiple-mode system that each mode has a specific reliability block diagram. The various subsystems of the system under study have active, cold-ready or k-out-of-n strategy, which are identified in the reliability block diagram of each mode. In this study, the percentage of improvements made to the failure rates of the components are integrated, and the failure rate of the components used in the closed continuous interval can be changed. 4 researchers. Fyffe et al., [8] were the first to present the mathematical model of the general problem of redundancy allocation. The goal of their proposed model was to maximize system reliability by considering weight and cost constraints. They solved this problem with the help of dynamic planning. Nakagawa and Miyazaki [9] presented a non-linear planning problem with a solution to optimize reliability. In fact, by changing the example of Fyffe et al., They solved the problem by using the exact method of substituting constraints, and showed that in the case of multiple constraints, this approach is better than the dynamic planning method. However, in order to increase the reliability, one or a set of the following measures can be performed. These measures can be implemented based on the assumptions and requirements of each system.  Optimization of redundancy level.
 Optimizing the selection of the type of components used in the system.  Optimization of existing technical activities in order to regulate failure and repair rates.
In the following, some conducted research on the optimization of the redundancy allocation problem will be showed in Table 1. Table 1 about here

3-Satellite attitude determination and control system
In this research, the satellite attitude determination and control system will be investigated. High efficiency, reliability and health are the most important criteria in the engineering of space systems.
Reliability refers to the possibility of the system working properly over a period of time. The first and most important step in preventing a system from malfunctioning is to detect failure in that system. Because in this case, there will be a good time to prevent problems in the system. Satellites are examples of self-contained, important, and costly space systems that are sent on relatively longterm missions. One of the most important parts of satellite that is directly related to health is the subsystem of satellite attitude determination and control system. The task of this subsystem is to determine and control the situation in space and neutralize the disturbing environmental disturbances and torques on the satellite. Therefore, this subsystem is always known as a subject of study to provide breakdown identification because improving the subsystem reliability of satellite attitude determination and control system directly affects the reliability of the satellite in space. In order to design the subsystem of satellite attitude determination and control system, in most cases, three reaction wheels are used in line with the three main axes of the satellite. Each of 5 these actuator has an electric motor and a heavy disk. By applying current to the electric motor, torque is produced, which changes the speed of the angles of the motor axis. The opposite direction is produced. Changing the speed of the reaction wheel by applying the necessary control algorithm to the motors causes the motor to reach the required speed from zero speed. After producing the necessary torque, the motor shuts off again. This change in speed causes the required tower radiation to be generated to achieve the desired state of the satellite. In order to increase reliability, a reaction or spare reaction cycle is used under the systems based on the reaction wheel. According to Figure 1, this actuator is located next to the main reaction cycle and as soon as one of the wheels fails or irreparable damage occurs in them, the spare reaction wheel will replace the defective cycle in the system. In general, the modules of system studied in this research are shown in the figure 2.

4-Problem Statement
In this section, the satellite attitude determination and control system, the structure of the system under study and its components are introduced, then model and optimize the reliability in this system according to the mathematical approach based on the combination of reliability allocation and redundancy allocation. In the following, we will introduce the components, structure and functions of the satellite attitude determination and control system.

4-1-Functions of attitude determination and control system
The functions of the attitude determination and control system include the following:  Adjust the satellite in the desired direction despite external disturbance torques  Determine the attitude of satellites using sensors  The situation switching by actuators  Satellite orientation for the mission The sub-system for determining and controlling the situation to perform each of its tasks in the form of control modes and obtaining the required attitude in each mode, consists of two parts: determination and control. The attitude determination section includes sensors and attitude determination algorithms, and the attitude control section includes actuators and attitude control algorithms. 6 The attitude determination and control system consists of several parts, which include the following:  Table 2 introduces the parameters and Table 3 introduces the variables of optimizing the reliability of satellite attitude determination and control problem. Table 2 about here   Please insert Table 3 about here 7

4-5-Assumptions
 The function of the components used in the system is independent of each other  The components failure used in the system is independent of each other  The components of the system under study are binary  The components cannot be repaired and returned to the system after failure  The parameters related to the cost and weight of the components in the system are deterministic and definite

4-6-Mathematical modeling
Based on the structure of the attitude determination and control system under each of the functional modes and also based on the arrangement of components according to the reliability block diagrams presented in the section 3-4, the reliability of the system under each functional modes is calculated. As can be seen from the reliability block diagram provided, the structure of the attitude determination and control system in the various functional modes of the hybrid structure includes active, cold-standby and k-out-of-n. In this section, we first model the reliability level of the attitude determination and control system in each of the functional modes under the conditions that the components used in the system follow any desired life distribution. Then, by placing the probability density function and the reliability of the exponential distribution in equations 1 to 5, the reliability of the system is presented in the functional modes of de tumbling, Coarse pointing, fine pointing, sun pointing and safe.
Now, under the assumptions provided in Section 4-5, according to the information provided about the system for determining and controlling the attitude of the satellite base, as well as calculations for the reliability of the system under different functional modes, the mathematical optimization model allocates reliability and redundancy allocation for the system under study is presented below. In this model, the reliability of each functional mode based on the arrangement of components and system structure in the block of other names provided for each of these modes is calculated. Also, the failure rate of the components used in the fixed system is assumed. It is used in the display system, so in the set of equations presented to calculate the reliability of the system under different functional modes, the probability density function and the reliability function of the display distribution are placed.
The objective function of the above mathematical model (6) is to maximize the minimum reliability of the attitude determination and control system under different functional modes. Constraints (7 to 11) calculates system reliability in the functional modes of de tumbling, coarse pointing, fine pointing, sun pointing and safe respectively. Constraint (12) guarantees that the total costs incurred in the system includes the costs of redundancy allocation and failure rate improvement does not exceed the maximum allowable cost. Constraint (13) ensures that the weight of the components allocated to the system does not exceed the maximum allowable weight specified for it. Constraints (14) to (19) ensure that redundant components to the system do not    Parents are first selected to perform the crossover operator, then the children are generated using a uniform crossover operator. The operation of this operator is described in references [30] and [31]. In this operator, for each gene in the selected parent chromosome, a number between zero and one is randomly generated, then the child's chromosomes are quantified in linear composition from the parent chromosomes.
Mutations are also performed on each array of the chromosome matrix. In this operator, after selecting the desired parent, a random number between zero and one is generated for each gene in the parent chromosome, and the values of the parent chromosome genes are mutated at a certain rate of mutation. Now, if the random number generated is less than the desired mutation rate, the corresponding gene on the parent chromosome will be randomly mutated, but if the random number generated is larger than the mutation rate, the gene will not be mutated on the parent chromosome [31]. For example, Figure 9 shows how the mutation operator executes on a chromosome.

Please insert Figure 9 about here
Using a random search method (RS) to solve the presented model can be a lower bound for minimization problems and a lower bound for maximization problems compared to other solution methods. In fact, proving the intelligent performance of meta-heuristic algorithms can be demonstrated by comparing them to an RS. So that, these algorithms must always be more powerful than an RS. Therefore an RS is provided to validate the proposed algorithm. The proposed RS Pseudocode is shown in Figure 10 [32]. Figure 10 about here

6-Results and discussions
In this section, the proposed model is solved. For this purpose, first a numerical example is presented on the case study. The table 4 shows the parameters and the information needed to solve the problem for a numerical sample example. 16 Please insert Table 4 Table 5 to tune on the appropriate levels. Due to the choice of twolevel experimental factor design, each of the experiments is considered at two levels, high and low.
The method of advancing the response surface methodology is such that in addition to the upper and lower limits, the axial points using the middle limits as well as a number of central points (in this research 5 central points are added to the design) is also considered. For this algorithm, according to the three available parameters, factor 2 3 is considered. For this purpose, we performed the experiment in MINITAB 16 software for the algorithm and tune the best level for the test result.

Please insert Table 5 about here
According to the explanations provided, the nonlinear regression equation for the proposed genetic algorithm, which shows the relationship between the parameters of the algorithm and the value of the objective function, is obtained. Now it is enough to solve the model (41) to get the optimal parameters of the genetic algorithm.  Table 6. Table 6 about here After obtaining the tuned parameters of the genetic algorithm, the example presented in Table 4 is solved using the genetic algorithm developed in this study and its results are reported. As shown in Figure 11, the convergence diagram of the genetic algorithm is shown in consecutive iterations, and in Tables 7 and 8, the information about the variables of the mathematical optimization model provided under the available maximum budget is clearly presented. Figure 11 about here Please insert Table 7 about here   Please insert Table 8 about here

7-Sensitivity analysis and validation
In this section, in order to validate the genetic algorithm developed to solve the mathematical model, which was discussed in Section 4-6, we compare the results of this algorithm with the solutions obtained from the random search method obtained under different amounts of the maximum budget. . Given that we know that the solutions obtained from the random search method are always solutions far from global optimization, so these solutions are a good criterion for evaluating the performance of the genetic algorithm. As can be seen in Table 9, genetics in all cases has found better solutions than random search, which indicates the efficient operation of this algorithm to solve the current problem. Figure 12 also shows the effect of increasing the maximum budget available on the reliability of the system under study. It is worth mentioning that in this paper, the 2018 version of MATLAB software has been used to implement the random search method and genetic algorithm. Table 9 about here Please insert Figure 12 about here

8-Conclusions
In this research, the satellite attitude determination and control system, the structure of the studied system and its components is introduced, then the reliability in this system was modeled and optimized according to the mathematical approach based on the combination of reliability allocation and redundancy allocation. By studying this system, it was determined that in general, the satellite attitude determination and control system has five different functional modes. These modes include de tumbling, coarse pointing, fine pointing, sun pointing and safe. In the following, each of these functional modes is introduced and the reliability block diagram of the system is presented under each of these modes. In this system, the function of the components used in the system and the components failure are independent of each other. Failed components do not damage the system as a whole. Also component are binary. In the attitude determination and control system, components cannot be repaired and returned to the system after failure. In the mathematical optimization model presented in this study, the parameters related to the cost and weight of the components in the system are deterministic and definite, and the system has the maximum cost and maximum allowable weight for the components used in it. The various subsystems of the system under study have active, cold-ready or k-out-of-n strategy, which are identified in the reliability block diagram of each mode. Also, systems where the components are cold-standby, there is a possibility that the switch will fail. In this study, the failure rate of the components used in the system is constant, so the life distribution of the components used in the system is exponential. In this study, the percentage of improvements made to the failure rates of the components is integer, and the failure rate of the components used in the closed continuous interval can be changed. The mathematical optimization model presented in this study falls into the category of optimization problems related to mixed integer nonlinear programming (MINLP).
Solving these problems always involves a lot of mathematical complexity. Therefore, the development of exact solution methods for these problems is very difficult and in most cases impossible. On the other hand, the redundancy allocation problem in terms of computational time falls into the class of NP-HARD problems. Therefore, metaheuristic algorithms should be used to solve the proposed mathematical model. In this study, a genetic algorithm was used to solve the proposed model. Also, to valid the results obtained from the developed genetic algorithm, a random search algorithm was used, which according to the obtained outputs, the genetic algorithm


extfieldsofstudy:
Computer Science
Physics

text:
Inferring Degrees from Incomplete Networks and Nonlinear Dynamics

Inferring topological characteristics of complex networks from observed data is critical to understand the dynamical behavior of networked systems, ranging from the Internet and the World Wide Web to biological networks and social networks. Prior studies usually focus on the structure-based estimation to infer network sizes, degree distributions, average degrees, and more. Little effort attempted to estimate the specific degree of each vertex from a sampled induced graph, which prevents us from measuring the lethality of nodes in protein networks and influencers in social networks. The current approaches dramatically fail for a tiny sampled induced graph and require a specific sampling method and a large sample size. These approaches neglect information of the vertex state, representing the dynamical behavior of the networked system, such as the biomass of species or expression of a gene, which is useful for degree estimation. We fill this gap by developing a framework to infer individual vertex degrees using both information of the sampled topology and vertex state. We combine the mean-field theory with combinatorial optimization to learn vertex degrees. Experimental results on real networks with a variety of dynamics demonstrate that our framework can produce reliable degree estimates and dramatically improve existing link prediction methods by replacing the sampled degrees with our estimated degrees.

Introduction
Many networks, although large in sizes, are substantially incomplete [Barabási et al., 2002;Szilagyi et al., 2005;Woodward et al., 2010;Chen et al., 2016] when compared with the real systems. To learn the topological characteristics of a complex network, we often need powerful accessing of the vertices and edges of the whole system. However, the associated cost is prohibitive, especially for large-scale networks, e.g., social networks with millions or even billions of nodes. Therefore, we seek a reliable and cost-effective way to estimate graph characteristics from incomplete (sampled) data [Ribeiro and Towsley, 2012;Eden et al., 2018].
The individual vertex degrees provide a cornerstone to have reliable estimations of many graph statistics, including network size [Bunge and Fitzpatrick, 1993;Stumpf et al., 2008;Katzir et al., 2011;Kurant et al., 2012], average degree [Goldreich and Ron, 2008;Dasgupta et al., 2014] and motif counting [Klusowski and Wu, 2018;Kashtan et al., 2004]. The vertex degree measures the lethality of a node in protein-protein interaction networks [Jeong et al., 2001], which is usually unknown if the network is incomplete. Consequently, estimating individual degree has its practical meaning in understanding the cellular function. Nevertheless, it is a challenging problem. Although many studies are concentrating on graph sampling techniques to infer some macroscopic properties of networks, such as the degree distribution or the associated moments of degree distribution [Frank, 1980;Stumpf and Wiuf, 2005;Achlioptas et al., 2009;Ribeiro and Towsley, 2012;Zhang et al., 2015], very few work on estimating the individual vertex degrees [Ganguly and Kolaczyk, 2017] so far. Ganguly and Kolaczyk [2017] derived a class of estimators from a risk-theoretic perspective and provided analytical analysis for them. These estimators take full advantage of the local topology information in the sampled sub-network to infer the individual degrees of the sampled vertices. However, the wide variety in the network structure can make the attempt in vain if we do not have any knowledge of specific global network characteristics, such as species abundance in ecological networks, or gene expression in biological networks. However, such crucial information is available but was not used in the risk-minimization framework.
In our framework, assuming that we are given a set of coupled nonlinear equations governs dynamics of the network, and the steady-states of all the nodes or a subset of nodes under the dynamics have been observed. We propose to estimate the individual vertex degrees from its steady-state without knowing any topology of the network, and we further improve the accuracy of the prediction if we know a tiny percentage of sampled graph regardless of sampling methods, as illustrated in Figure 1. The motivation is that the steady-state of some process (e.g., an epidemic spreading, gene expression) may be observable even though the full network is not observable. For example, in social networks, we may know who got sick, but we may do not know who interacts with whom; in biological networks, we may know the gene ex- pression of all the genes of a patient, but we may not completely know the wiring diagram of them. It is possible to infer individual vertex degrees because the steady-state is the outcome of a complex interplay between the network's topology and the dynamics. Our framework does not rely on any prior knowledge of the sampling methods or the degree distribution. However, it offers excellent inference with as low as 10% of known edges, and moderate level of noises in the measurements. Another advantage is its ability to recover individual degrees for all vertices with only partial topology, (in)accurate measurements of the state information, though the dynamical system may be misspecified. To demonstrate the impacts of sampling scheme and the measurement noise in steady-states, and how the local topology and the dynamics contribute to the overall accuracy, we conduct a series of empirical experiments on various real networks. Experimental results indicate that our approaches can accurately infer individual vertex degrees and very robust to the sampling scheme. The inference quality can be guaranteed as long as the measurements of the steady-state are not distorted too much. Problem Setup. Let the implicit full network be G = (V, E). It is only partially observable from a sub-network G (s) = (V (s) , E (s) ) with V (s) ⊂ V and E (s) ⊂ E. Let δ = (δ 1 , δ 2 , . . . , δ n ) be the true individual vertex degrees, and n = |V |. To be convenient, bold letters hereinafter in mathematical formulas represent vectors.
We consider a general dynamics in which each vertex of G evolves according to a self-driving force and a sum of interaction forces over the neighborṡ (1) Both f (·) and g(·, ·) are general and usually nonlinear, and the adjacency matrix A ≥ 0 modulates the interactions between vertices. The coupled ordinary differential equations (ODEs) which are based on the complete topology of G drive the states of the vertices to an equilibrium x * . Given the complete network, this equilibrium can be approximated efficiently using a mean-field approximation derived in [Gao et al., 2016]ẋ This mean-field approximation interprets the impacts of a neighborhood using an average impact determined by x eff , which is equivalent to a homogeneity assumption. The total interactions of the neighbors of a vertex amounts to multiplying this average interaction by δ i . To compute the meanfield steady-states z * in (2), one needs vertex degrees δ i and the effective network impact, x eff , which can be computed given the complete network. Our contribution is to show how to compute these steady-states given only the incomplete network, thereby establishing a relationship between the observed steady-states and the vertex degrees, from which we back-out the individual degrees. To fill in the details, we first describe the mean-field approximation.

The Effective Network Impact
Now consider a vertex i and the interaction term (1), where A ij is the influence j has on i. Similarly, i influences j with a weight A ji . We define the in-degree δ in i = j A ij and the out-degree δ out i = j A ji . Assuming A ij ≥ 0, the interaction can be written as ( Here, the in-degrees δ in captures the idiosyncratic part, and the average g(·, ·) captures the network effect. The mean-field approximation is to replace local averaging with global averaging, which approximates the network-impact on a vertex as nearly homogeneous. Specifically, we have where the vector g(x i , x) has the jth component g(x i , x j ).
We define a linear operator to produce a weighted average of the entries in z. Then, in our mean-field approximation, In the first order linear approximation, we can take the L A -average inside g. The average of external interactions is approximately the interaction with its average. That is where L A (x) is a global state. Let x av L A (x). Applying L A to both sides of (7) giveṡ According to the extensive discussion and tests in Ref. [Gao et al., 2016], the in-degrees δ in and the interaction with the external x av are roughly uncorrelated, so the L A -average of the product is roughly the product of L A -averages. Thus, we Using the first order linear approximation, we take the L A -average inside f and ġ The steadystate of (10) is the effective network impact, x eff . Plugging it into (7) gives an uncoupled ODE for x i , (1) is replaced by an interaction with a mean-field external world g(x i , x eff ) and the number of neighbors impacting x i is captured by δ in i . To approximately obtain the steady-states of the system, one first solves the ODE in (10) to get x eff , and then n uncoupled ODEs at each vertex to get x i , which only depends on δ in i if given x eff . The method works well because the mean-field approximations only need to hold at the steady-state. Hence, we can recover the steady-state for any vertex (for example the sampled vertices) from accurate estimates δ in i (δ i in the undirected case) and β.

Our Approaches
Our approaches need the observed steady-states x * of nodes to estimate the individual node degrees δ, which can be improved if we also know the partial topology of the network. We consider the observed x * as the ground truths and aim to search an optimal combination of degrees such that the predicted steady-states z * of the approximated system (2) are close to x * . In this sense, the general techniques underlying our work can be formulated as an optimization problem: min is the degree of the sampled vertex i in the incident/induced subgraph, d i is the estimated missing degree for i (see more details in Section 3.2).
First, we propose the ZeroTopo algorithm to estimate the degree of each node without knowing any topology of the network, i.e., A (s) has only zero elements. Then, we design an efficient 2-step procedure -TopoPlus and Round -to improve the accuracy of degree prediction by introducing the observed topology.
• ZeroTopo estimates δ and x eff with only the observed steady states x * and with ZERO known topology. • TopoPlus estimates δ and d with both the partially observed topology and x * . Thus,δ = δ (s) + d, meaning that the estimated degree of a node is equal to the sum of its sampled degree and the missing degree.

ZeroTopo
ZeroTopo refers to the estimation of vertex degree based on observed steady-states x * and the dynamics f (·) and g(·, ·), without any known topology information, as shown in Algorithm (1). The average steady-state is set as the initial value of the effective state x eff = x * when ZeroTopo warms up (line 1). Based on the mean-field approximation, we can repeatedly estimate the resilience index β from estimated degrees and update the effective state such that the entire system is self-consistent. The algorithm is simple but very powerful to recover all individual degrees simultaneously.

TopoPlus
In the ZeroTopo algorithm, we assume that we have no prior information about the topology of the network. In this section, we aim to enhance the accuracy of the degree prediction when we observe a subgraph G (s) . Note that the TopoPlus algorithm only requires the topology of the observed subgraph regardless of how one samples it. We incorporate the adjacent matrix A (s) into (2) to identify the missing degree d i in the discarded local topology. Hence, we get an enhanced meanfield approximatioṅ with the steady-states x * of the observed vertices, and the effective network impact x eff . Once x eff is found, it is easy to derive d i , that is The term d i is a compensation to δ (s) The idea lies in the mean-field approximation (2) that We do not have all connections δ i associated with vertex i, but we have some, δ (s) i ≤ δ i . Based on the same approximation (2), we know (13) and (14). Note that for vertices not in the sampled vertices, δ (s) i = 0, ∀i ∈ V (s) . As a result, the enhanced approximation (13) is equivalent to (2), then computing d i in (14) is exactly solvingδ i from (2) in ZeroTopo. TopoPlus is formulated in Algorithm (2).

Round
Both ZeroTopo and TopoPlus contain an easily unnoticed but crucial step: Round. A rounding algorithm involves the approximation of fractional values to integer ones. In specific, Eq.(14) gives a fractional d i , and in our setup we consider the networks are unweighted. Therefore, we need the rounding to get an integer approximation of the degree of each nodeδ i = δ (s) i + d i . It is a complicated and hard problem. In ZeroTopo and TopoPlus (marked with · ), we applied the simple plain rounding algorithm because of its ease to use. However, rounding is beyond a purely numerical problem, and we should also consider its afterward impact on the predicted steady-states z * . Therefore, we design a heuristic combinatorial optimization based rounding scheme (see Algorithm 3) to not only ensure the accuracy in estimating individual degrees, but also minimize the error between the observed steady-states and the simulated steady-state based on the estimated degrees. The idea is to repeatedly pick a node pair (i, j), then adjust their estimated missing degrees d i and d j , keeping the total number of links unchanged: increase d i by 1 and decrease d j by 1 (line 8, Algorithm 3). The selection rule is that the two steady-states z * i and z * j solved from Eq. (13) do not yet match the observed states x * well with the current estimates d i and d j . Nevertheless, after the adjustments, the steady-states z * becomes closer to x * . Though computing seems to be very intensive, each distinct missing degree can involve in solving Eq. (13)   We test our algorithms on two real networks for each dynamic. The notations n and m represent the number of vertices and edges, respectively. While δ and β denote the average degree and resilience index respectively.

Experimental Results
We evaluated the performance of our approaches on six real networks, governed by three dynamical equations (ecological, regulatory, and epidemic) [Gao et al., 2016] (Table 1). For each network, we sample a fraction of the edges and repeat 10,000 times to get statistically significant results. On average, it takes only a few of seconds to converge. We employ the fraction of vertices with a relative error of not greater than 5% as a proxy metric of the estimation accuracy, and the relative error is defined as Err[δ i ,δ i ] = | log(δ i /δ i )|. As reported in Table 2, we show the performance of each of our algorithms. Though ZeroTopo does not take advantage of the sampled local topology information, the dynamics itself can give a decent estimate of vertex degrees even without the sampled sub-network. The TopoPlus, either equipped with plain rounding algorithm or the designed Round algorithm, can improve the accuracy of our estimation significantly, indicating that it is vital to utilize some available topology and rounding carefully.

Sampling Technique
Prior structure-based degree estimation methods [Ganguly and Kolaczyk, 2017] rely on strong assumptions about how to sample the sub-network. Specifically, these methods are designed for the induced graph from uniform sampling. In other words, it does not work for other sampling methods, for example, random walk sampling. Our approaches do not, and they are universal, regardless of sampling methods. To demonstrate this, we compare two very different ways to sample edges: uniform sampling, and random walk sampling [Hu and Lau, 2013]. Figure 2 shows that our approaches are very robust to the sampling scheme, as is expected. Two fundamental assumptions we made are that the observed steady-states are measured precisely, and the true dy-namics are known. We now show that our approaches can tolerate high level of noise added to the observed steadystates, as well as model misspecification in the form of noise added to the parameters in the dynamical system. We add multiplicative noise ε x ∼ N (0, σ) to the observed states, so we observed the states x * (1 + ε x ) ≥ 0 in simulation. Similarly, the parameters in the dynamical system are perturbed by multiplying by a factor 1 + r for r ∈ [−0.5, 0.5].  Figure 3 shows the robustness to observation noise, and Figure 4 shows the impact of errors on three parameters in the ecological system (see Table 2). The parameter B describes the incoming migration rate from neighboring ecosystems, C controls the critical abundance of the Allee effect, and H depicts the positive contribution from one vertex to another. The estimates are very sensitive to the error in the interaction parameters C and H, but is very robust to the error in B.

Local Topology and Dynamics
We, for the first time, estimate the structure characteristics of graphs using the network dynamics. Then, we compare the performance of our estimators and that of the structurebased estimators [Ganguly and Kolaczyk, 2017]: the univariate risk minimizer (URM), the multivariate risk minimizer (MRM) and the Bayes estimator as the baselines. Note that our estimator is regardless of the sampling methods, and the structure-based methods are only suitable for induced subgraph sampling. To ensure the fairness of the comparison, for each run, (1) we uniformly sample the same 10% of vertices in our approaches and the structure-based estimators; (2) we only utilize the steady-state of the observed nodes in our approaches and the induced graph of the observed nodes in the structure-based estimators. We perform 10,000 runs and show the average accuracies of the baselines and our approaches in Table 3.  We have demonstrated the promising performance of our approaches on the incident subgraphs. As we discussed in Sec. 4, they can perform well no matter how the sub-network are sampled. Therefore, they are expected to accurately estimate vertex degrees on induced subgraphs as well. Moreover, in Algorithm 1, we assume that the states of all the nodes are known. In this comparison, we only know the states of the observed nodes. To bridge this gap, we have to estimate the global β from the induced subgraph. Fortunately, Jiang et. al [2020] offer a methodology to estimate β from incomplete networks, it can be used here. Without the states of all vertices, as shown in Table 3, the performance of the ZeroTopo is still outstanding compared with structure-based methods, even with 10% noises in the measurement. It indicates that the local degrees or the neighborhood in the induced subgraph alone are not sufficient to obtain reliable estimates of individual vertex degrees. Vertex states should also be explored.
There is an issue in the steady states: the measurement errors. It is ubiquitous in the real-world that the observed states are suffering from measurement noises. No measurement error (i.e., σ = 0) is an ideal case, and our approaches are significantly better than the baselines. After adding a moderate amount of noise (σ = 10% on N6, N8, ME, TY, and EM; 9% on FB), our approaches can still beat them. The TopoPlus and Round provide additional improvement because of the extra topology and careful rounding.

Application: Link Prediction
Estimating degrees itself is an essential and exciting issue in network science. It is also useful for many other applications, such as link prediction, network reconstruction, identification of essential genes, influencer discovery, and many more. Here, we take link prediction as an example to show how our approach can enhance the current link prediction methods. The most intuitive approach to build links is computing the affinity between a node pair, e.g., (a) Adamic-Adar (AA) [Adamic and Adar, 2003] s u,v = w∈Γu∩Γv 1/ log δ w , where Γ u is the neighbors of vertex u, and (b) Preferential Attachment (PA) [Barabási and Albert, 1999] s u,v = δ u δ v . Both metrics contain the degree terms. Therefore, we improve these methods by replacing the observed degrees δ (s) by the estimated degreesδ using our estimators. We proportionally scale up the size of the common neighbors |Γ u ∩ Γ v | by a factor of α u,v according to a simple rule: The area under the receiver-operating characteristic curve (AUC) [Hanley and McNeil, 1983] is used to measure the prediction accuracy. AA requires a joint neighborhood, but PA does not. A small sampling fraction gives a very sparse subnetwork such that joint neighborhoods are absent from G (s) . As a result, the affinities of many node pairs are distorted. To evaluate the performance, we randomly sample p =1% edges for an incident subgraph and predict the remaining 99% missing links. As reported in Table 4, the link prediction of AA is almost random. The scale-up factor can not exercise an impact on AA at all since no joint neighbors are observed. For PA, once the individual degrees are accurately revealed, the link prediction can be of high quality as well. It can give a promising improvement on all six real networks given as low as 1% observed edges. It demonstrates the value of our algorithm in link prediction. Note that our approach can not only improve the current link prediction methods, but it is also essential for many other inferring issues in network science.  Table 4: AUC of AA and PA, for using the observed topological information only (naive), the estimated degrees from our algorithm (revised) or the ground-truth topological information of the sampled vertices (truth). A simple scale up is made for the revised AA.

Discussion
We addressed a prevalent problem. Consider this scenario. A biologist has measured the gene expressions of all genes and collected some relationships summarized in the adjacency matrix A (s) . The biologist also knows how genes interact, the dynamical system (1). The biologist would like to identify the essential genes using the degree centrality and to make some new discoveries. Then he/she tries to use some structure-based methods to estimate the missing degrees and finds the improvement is limited. The biggest issue is that both the gene expression data and the dynamical systems are known, but he/she does not use them. In the current-state-ofthe-art, no methods are available to utilize these information. The difficulty is rooted in lacking methods to theoretically solve the n coupled nonlinear ODE equations with incomplete graph. We bridge this gap by using a mean-field approximation, where the original system can be condensed to a single dimensional system with variable x eff and topological parameter β. We provide a framework to estimate the missing degrees accurately, which enables us to measure the essential genes. Moreover, our approaches are robust to sampling methods and work even without knowing any topology. There are several directions for future work. First, we can go for a reconstruction of the full network topology, not just vertex degrees, which needs to solve the full link-prediction problem. This is ongoing work. Second, the mean-field approximation is the basis of our algorithm. However, the estimation itself relies on the assumption that the network is homogeneous. Therefore, when the steady-states of the neighbors are unknown, we use x eff as an approximation. All nodes are treated without any discrimination, although their neighborhoods may be different from each other. This assumption may not hold in real-world systems, and the estimation accuracy will be negatively affected. Another issue is the dynamical equations. In many scenarios, it is tough to calibrate the real dynamical equations. We can employ advanced machine learning approaches to extract the governing equations from an immense amount of experimental data.