summaries: This paper looks at the problem of few-shot classification in the regime when only a single class is present. The task at hand is as follows: given a number of support images of a previously unseen class (not present during training) and a single unlabeled image, we need to decide if this image belongs to the class or not. While previous approaches would explicitly construct negative examples to contrast the positive ones with during training, the authors bypass this by using batch norm in the last layer, which, on average, centers embedding feature vectors at 0, defining effectively the embedding for the negative class. In addition, the authors look at modelling the distribution of support image embeddings to improve the performance of their model.

summaries: Authors consider the 1-way few shot classification task. Argue that modeling it as a 2-way with a random negative sample is not efficient. Propose a novel technique applicable for prototypical networks. Their proposal is to use 0 as the prototype of null class. So the distance to the prototype is compared against the norm of the query embedding. They also propose modeling the distribution and not just the centroid using a multivariate gaussian. But in practice there is no benefit in doing so. Therefore, the main contribution is proposing to compare against norm of the embedding rather than a prototype for random negative samples. The benefit of this proposal decreases by more shots. Probably because the prototype of 20 random images is 0 anyway.

summaries: This paper addresses a method of applying prototypical networks (which are popular for few-shot learning problems) to few-shot one-classification problems where only one group of examples are available without any counter-examples. The main idea of prototypical networks is to learn an embedding function such that in the embedding space a distance metric well reflects the class structure. When such models are applied to one-class problems, a basis for comparison is required.

abstractText: Few-shot models have become a popular topic of research in the past years. They offer the possibility to determine class belongings for unseen examples using just a handful of examples for each class. Such models are trained on a wide range of classes and their respective examples, learning a decision metric in the process. Types of few-shot models include matching networks and prototypical networks. We show a new way of training prototypical few-shot models for just a single class. These models have the ability to predict the likelihood of an unseen query belonging to a group of examples without any given counterexamples. The difficulty here lies in the fact that no relative distance to other classes can be calculated via softmax. We solve this problem by introducing a “null class” centered around zero, and enforcing centering with batch normalization. Trained on the commonly used Omniglot data set, we obtain a classification accuracy of .98 on the matched test set, and of .8 on unmatched MNIST data. On the more complex MiniImageNet data set, test accuracy is .8. In addition, we propose a novel Gaussian layer for distance calculation in a prototypical network, which takes the support examples’ distribution rather than just their centroid into account. This extension shows promising results when a higher number of support examples is available.

authors:
Kelsey R. Allen
Evan Shelhamer
Hanul Shin
Joshua B. Tenenbaum

title: Infinite mixture prototypes for few-shot learning

authors:
Raghavendra Chalapathy
Sanjay Chawla

title: Deep learning for anomaly detection: A survey

authors:
Varun Chandola
Arindam Banerjee
Vipin Kumar

title: Anomaly detection: A survey

venue: ACM Computing Surveys,

authors:
Yubo Chen
Liheng Xu
Kang Liu
Daojian Zeng
Jun Zhao

title: Event extraction via dynamic multi-pooling convolutional neural networks. In Annual Meeting of the Association for Computational Linguistics (ACL)

authors:
Sarah M. Erfani
Sutharshan Rajasegarar
Shanika Karunasekera
Christopher Leckie

title: Highdimensional and large-scale anomaly detection using a linear one-class svm with deep learning

venue: Pattern Recognition,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

title: Gaussian Prototypical Networks for Few-Shot

venue: Learning on Omniglot. arXiv,

authors:
Simon Hawkins
Hongxing He
Graham J. Williams
Rohan A. Baxter

title: Outlier detection using replicator neural networks

venue: In International Conference on Data Warehousing and Knowledge Discovery (DaWaK), Aix-en-Provence,

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37,

authors:
Sheroz S. Khan
Michael G. Madden

title: One-class classification: Taxonomy of study and review of techniques

venue: The Knowledge Engineering Review,

authors:
Gregory Koch
Richard Zemel
Ruslan Salakhutdinov

title: Siamese neural networks for one-shot image recognition

venue: In International Conference on Machine Learning (ICML), Lille, France,

authors:
Brenden M. Lake
Ruslan Salakhutdinov
Joshua B. Tenenbaum

title: Human-level concept learning through probabilistic program induction

venue: Science,

title: Evaluation of the CNN design choices performance on ImageNet-2012. https://github.com/ducha-aiki/caffenet-benchmark

title: Detecting anomalous data using auto-encoders

venue: International Journal of Machine Learning and Computing,

authors:
Poojan Oza
Vishal M. Patel

title: One-class convolutional neural network

venue: IEEE Signal Processing Letters,

authors:
Pramuditha Perera
Vishal M. Patel

title: Learning deep features for one-class classification

authors:
Sachin Ravi
Hugo Larochelle

title: Optimization as a model for few-shot learning

venue: In 5th International Conference on Learning Representations,

authors:
Mengye Ren
Eleni Triantafillou
Sachin Ravi
Jake Snell
Kevin Swersky
Joshua B. Tenenbaum
Hugo Larochelle
Richard S. Zemel

title: Meta-learning for semi-supervised few-shot classification

venue: In 6th International Conference on Learning Representations,

authors:
Lukas Ruff
Nico Görnitz
Lucas Deecke
Shoaib Ahmed Siddiqui
Robert A. Vandermeulen
Alexander Binder
Emmanuel Müller
Marius Kloft

title: Deep one-class classification

authors:
Mohammad Sabokrou
Mohammad Khalooei
Mahmood Fathy
Ehsan Adeli

title: Adversarially learned one-class classifier for novelty detection

venue: In Conference on Computer Vision and Pattern Recognition

authors:
Mayu Sakurada
Takehisa Yairi

title: Anomaly detection using autoencoders with nonlinear dimensionality reduction. In Workshop on Machine Learning for Sensory Data Analysis (MLSDA)

authors:
Thomas Schlegl
Philipp Seeböck
Sebastian M. Waldstein
Ursula Schmidt-Erfurth
Georg Langs

title: Unsupervised anomaly detection with generative adversarial networks to guide marker discovery

venue: In International Conference on Information Processing in Medical Imaging (IPMI),

authors:
Bernhard Schölkopf
Robert Williamson
Alex Smola
John Shawe-Taylor
John Platt

title: Support vector method for novelty detection

venue: In International Conference on Neural Information Processing Systems (NIPS),

authors:
Jake Snell
Kevin Swersky
Richard S. Zemel

title: Prototypical networks for few-shot learning

authors:
David M.J. Tax
Robert P.W. Duin

title: Support vector domain description

venue: Pattern Recognition Letters,

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
Koray Kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

heading: 1 MOTIVATION

text: One- or few-shot learning is an active area of research that focuses on modeling semantic concepts with very little training data. Such models learn information about the general task of comparing queries to one or several support examples of the requested classes, which can then be applied to unseen classes. A large amount of data is still necessary for training, but this data does not need to belong exactly to the domains that may become interesting in the future, but rather to a variety of similar problems. This notion is inspired by human learning; humans can usually generalize to a new concept from just one or very few examples, using their prior knowledge of the world and related concepts. A special case occurs when we do not need to distinguish between multiple concepts, but rather want to enable models to recognize a single new concept. In many practical scenarios, we will often be interested in just one novel class, rather than multiple at once. Application examples include detecting news or social media texts about a certain events; detecting one type of unseen object (e.g. a face) in a dataset; verification of unseen fingerprints; or outlier detection within an unseen class. In existing few-shot methods, this is commonly translated into a two-class problem with the classes “belonging to the concept” and “not belonging to the concept”. As these two classes have very different types of feature distributions, this is not the most elegant solution and poses problems, especially with regards to training data selection. It also requires effort for modeling a class (the negative one) that is not of interest. In this paper, we present an addition to few-shot learning approaches that enables generalization to a single class in order to determine whether queries belong to this (previously unseen) concept or not. This is implemented by introducing a “null” (or “garbage”) class which does not need to trained to the prototypical network approach. Application of this novel model type is demonstrated on the commonly used Omniglot and MiniImageNet data sets.

heading: 2 RELATED WORK

heading: 2.1 ONE-CLASS CLASSIFICATION

text: The problem of one-class classification has been a topic of research for decades. It has also been interpreted as outlier detection, anomaly detection, novelty detection, and concept learning. Comprehensive overviews of “traditional” methods for solving this task are given in Khan & Madden (2014) and Chandola et al. (2009). Chandola et al. (2009) identify several different fundamental techniques, e.g. statistics, nearest-neighbour methods, clustering, and classification. Strategies can be derived from research areas such as data mining, information theory, and machine learning. Within the machine learning domain, a common solution relies on One-class Support Vector Machines (OSVMs) [Schölkopf et al. (1999); Tax & Duin (1999)], although earlier-stage neural networks were also utilized [Hawkins et al. (2002)]. In recent years, various deep learning approaches have been suggested as well. Auto-encoders are frequently used for dimensionality reduction (corresponding to a feature extraction) of the input data in this context. Some methods then directly calculate the reconstruction error to determine whether new queries belong to the same class or are outliers (e.g. Sakurada & Yairi (2014); Chen et al. (2015)). Others add a subsequent classification network (e.g. Morton & Griffin (2016) or Erfani et al. (2016), where the auto-encoder is replaced with a Deep Belief Network). Ruff et al. (2018) take inspiration from OSVM approaches and train CNNs jointly with a classification SVM. Lately, adversarial approaches have seen attention in this domain as well, e.g. in Schlegl et al. (2017) and Sabokrou et al. (2018), where they are used in a similar fashion as the previous auto-encoders. Direct training on a single annotated class is not implemented as frequently as the combination of automatic feature extraction and distance (or reconstruction error) calculation. Oza & Patel (2019) demonstrates a strategy for training a CNN on positive examples and artificial negative examples generated from Gaussian distributions, while Perera & Patel (2018) shows a method based on automatic feature extraction in combination with specialized loss functions and template matching. A broad overview of deep learning techniques from the anomaly detection perspective is provided in Chalapathy & Chawla (2019). All of these approaches rely on the availability of data from the expected class for training. What is missing is a type of model that can determine whether a query belongs to a class from a small number of examples that are provided at evaluation time without the need to re-train. Such a classification is possible with few-shot learning.

heading: 2.2 FEW-SHOT LEARNING

text:
The concept of one- or few-shot learning is motivated by human learning: If humans are presented with a new class of objects, they do not require more than a few examples to be able to match new instances to this class (often, just one supporting example is sufficient). This ability is, among other factors, informed by general world experience, which teaches humans to set boundaries between object classes. Matching networks, which implement this idea, were first introduced by Vinyals et al. (2016). Training is performed on sets of support examples for a subset of possible classes plus a query example belonging to one of the classes in so-called episodes. These episodes are generated for a wide range of class permutations. In the one-shot case, only one support example is given for each class, while there are multiple ones in few-shot models. Such a network has two input branches: One for the support examples, and one for the query example. In both branches, the inputs are run through a sub-network which performs an embedding. The embedding networks may or may not share their weights. The query’s resulting embedding is then compared against the supports’ resulting embeddings using a pre-defined distance metric. This results in likelihood measures for each input class, commonly implemented with a softmax. The over-all comparison metric for the task is learned implicitly as the network learns an appropriate embedding. In the few-shot case, multiple support examples per class are treated independently of each other throughout the network. Example-related likelihoods are then summed up to obtain class likelihoods at the output. In this way, matching networks essentially implement a weighted nearest-neigbor classification. As a further development, Snell et al. (2017) introduced prototypical networks. Instead of treating all of a class’ support examples independently, they compute a so-called “prototype” of the class after the embedding network. This prototype is commonly the mean vector (or centroid) of
the class’s embedded support examples.When the squared Euclidean distance is used as the metric, this implements a linear classifier rather than the nearest neighbor classifier produced by matching networks. Finn et al. (2017) goes one step further and introduces model-agnostic meta learning (MAML): An algorithm to train models that can be easily finetuned to new tasks with very few examples. This can also be applied to other few-shot methods such, as matching networks. When applying few-shot learning to a binary problem, support examples for two classes are required: Positive examples of the class of interest, and random other examples. This amounts to a workaround, as there are no two comparable classes. Instead, one of them merely consists of counterexamples (a sort of “garbage” class). Examples in this class will have a much wider feature distribution. This makes selecting random examples difficult, as they should still be representative of this distribution, particularly when only a small number of support examples is used. It also means that computational power and time must be dedicated to a class that is not actually of interest, and as such is not very elegant. Siamese networks [Koch et al. (2015)] can be seen as an interesting way to solve this problem, as they implement a decision about whether two unseen examples belong to the same class or different ones. However, they are not able to exploit more than one support example per class like prototypical networks can.

heading: 3 PROPOSED APPROACH

heading: 3.1 ONE-WAY PROTOTYPICAL MODELS

text:
Motivated by the counterexample issue, we take the described approach one step further: We construct a prototypical network that only requires positive support examples, from which it generates an internal embedding of the whole class. The query embedding is then compared to this, and judged to belong to the same class or not. We call this type of network a “one-way prototypical network”. The sub-network for generating the internal embeddings is implemented just as in regular prototypical networks with shared weights between the support and query branches. An illustration is shown in figure 1a. This approach presents a challenge for the distance metric: Because Cosine or Euclidean distances are not bounded, we cannot set a threshold for class belonging. In order to do this, we need a basis for comparison. We implement this by introducing a “null class” that models the whole space of possible examples without explicitly being given those examples (as in the two-class implementation mentioned above). Queries are judged on whether they are more probable to belong to the (positive) class we are interested in rather than the null class. The question then becomes how to construct this class. As explained above, prototypical networks model classes by calculating the centroid of the class’s support examples. As the model includes batch normalization layers, we can assume that the centroid of the whole latent space will be close to the zero point in all embedding dimensions. A query’s distance to the centroid of the positive class is therefore compared to its norm (i.e. its distance to the zero centroid) to determine whether it is more likely to belong to the positive class or to the null class encompassing everything. Figure 1b shows a visualization where the null centroid is denoted as c0. A similar idea was presented in Ren et al. (2018), which suggests the use of unlabeled data to improve prototypes. The null (or “distractor”) class here is only used to identify examples not belonging to any of the trained classes, rather than training the model to explicitly distinguish between a single given class and the null class. As in regular prototypical models, Euclidean distance is used.
One issue that arises is that in the state-of-the-art prototypical models, batch normalization is not performed at the end of the convolution blocks of the embedding network, but rather after the convolution layer and before the (ReLU) non-linearity and pooling layers. The final block is therefore not quite batch-normalized. As there is some debate about the ordering of these layers anyway [Ioffe & Szegedy (2015); Mishkin], we propose reordering the block layout to a structure of: Convolution - (Leaky) ReLU - Max Pooling - Batch Normalization. An alternative to the null class solution would be a simple thresholding of the class likelihood. However, preliminary experiments showed that this threshold is very problem- and concept-dependent, and thus does not generalize well to unseen episodes.

heading: 3.2 ONE-WAY NORMAL PROTOTYPICAL MODELS

text: As described, prototypical networks only take into account the centroid of a class’s support examples. This is sufficient when all classes can be assumed to be roughly on the same semantic level and therefore have similar feature distribution widths. However, this may not always be true (e.g. we may encounter cases where the model attempts to distinguish between queries of the class “Bobtail cat” and queries of the class “Insect”). This problem becomes even more prevalent for the one-class case, as unseen classes may have wider or narrower distributions than unseen examples, and we do not have a basis for comparison defined by other classes. Allen et al. (2019) suggest solving this problem by dynamically adding prototypes per class as necessary - so-called Infinite Mixture Prototypes (IMP). We propose a different extension to prototypical networks: Modeling classes by their distribution instead of their centroid only. These distributions are fitted to the class’s support examples. Due to the effect of batch normalization, we assume multivariate normal distributions for this extension. A query’s class assignment is then determined by its likelihood under each class’s distribution. The previous embedding network is implemented just as before, except that Leaky ReLU activations become necessary instead of ReLUs to guarantee training stability. (To clarify: If the value of any of the embedding dimensions becomes exactly zero after the non-linearity, the all-over probability becomes zero as well, leading to a failure of gradient calculation during training. Leaky ReLU prevents this from happening). This extension of prototypical networks also integrates with the one-way framework described above. Instead of assuming a centroid at zero for the null class, we now assume a multivariate normal distribution with a mean at zero and a standard deviation of 1 (this is not guaranteed exactly, though: Batch normalization enforces a centering at zero and a standard deviation of 1, but does not enforce Gaussian-ness). A visualization is provided in figure 2. (In the one-way case, this is an advantage over IMP: Preliminary experiments show that adding the one-way concept to IMP models does not lead to improvements over standard prototypical networks as the multiple positive prototypes tend to overpower the one negative prototype.) Of course, this idea has one obvious drawback: The model requires a sufficient number of support examples to be able to determine a salient standard deviation over them, particularly as the embedding dimensions are treated independently. We hypothesize that beyond a certain number of support examples, implementing class’s distributions instead of their centroids only will enable the model to distinguish between them better. (As a side note, Fort (2017) also showed how to integrate a distribution concept into prototypical networks, calling them “Gaussian Prototypical Networks”. However, in this publication, the covariance matrix is calculated for each embedded example rather than over the various support embeddings. It is then taken into account explictly in the distance metric. This allows a better handling of uncertainties, particularly for noisy data. Our focus here is somewhat different: We are more interested in obtaining additional information from the relationships between support examples).

heading: 4 EXPERIMENTS AND RESULTS

heading: 4.1 DATA AND EXPERIMENTAL DESIGN

text: We first test our approach on a well-known toy data set for one- or few-shot learning: The Omniglot image data set [Lake et al. (2015)]. This data set contains 1623 characters hand-drawn 20 times by Amazon Mechanical Turk1 annotators. These characters come from 50 alphabets; a 30-20 split of the alphabets is suggested for training and validation. Per episode, we use 1 to 19 instances of a character as support examples, and either one of the remaining examples or a random other character as the query. As commonly done in literature, we also test the trained models on an unmatched data set: The MNIST handwritten digit database [LeCun et al. (1998)]. Second, we run experiments on the much more complex MiniImageNet data set [Vinyals et al. (2016)]. MiniImageNet is a subset of the larger ImageNet data set [Russakovsky et al. (2015)]. It contains 60,000 color images of size 84x84, split across 100 semantic classes with 600 examples each. Out of these, 80 classes are used for training and 20 for test. We use the splits provided by Ravi & Larochelle (2017). Our experiments are performed with 1 to 20 support examples per class. In both cases, pre-processing simply consists of a normalization of the input image data to a mean of 0 and a standard deviation of 1. All trainings are performed six times with random initializations and training episodes. The results are reported in terms of accuracy and averaged across runs; standard deviation between runs is generally very low (<.01). Each training is run for 20 (for Omniglot) or 10 (MiniImageNet) episodes, with 32,000 randomly generated episodes each, resulting effectively in 640,000 and 320,000 training episodes respectively. Adam is used as the optimizer.

heading: 4.2 EXPERIMENT A: SIAMESE AND TWO-WAY MODELING

text:
In our first experiment, we test the performance of previous architectures on the one-way problem: With Siamese, matching, and prototypical networks. The former can only integrate a single support example and compare this to the query. For the latter two, we implement the one-way problem as a two-way classification, with the relevant “positive” class on the one hand, and the “negative” class on the other. Support examples are thus selected from the positive class, and randomly from the whole remaining data set. Results on the Omniglot and MiniImageNet data sets are displayed in figure 3. Supports range between 1 and 19 (Omniglot) or 20 (MiniImageNet). The results are generally acceptable, with prototypical models always delivering higher accuracies than matching networks. This difference becomes larger the more support examples are available, as this allows the prototypical networks to model the negative class better, whereas the nearestneighbor classification of matching networks is not strongly improved with more support examples. Accuracy of the prototypical networks ranges between .75 for one support example, and .977 for 19
1https://www.mturk.com/
on the Omniglot data set, and between .59 (one support) and .74 (20 supports) on MiniImageNet. Siamese networks perform well (even best on Omniglot) for one support example, but are quickly surpassed by prototypical networks when more are available. The novel normal prototypical networks work well for this problem, but do not surpass standard prototypical networks. For very few support examples, results do not rise much above the .5 baseline, or training may even fail completely. This is to be expected, as the distribution cannot be determined from such a low number of supports. 5 examples appear to be necessary to make these models work at all, and 10 to make them generate competitive results. We also test the models trained on Omniglot on the unmatched MNIST data set. Results are not shown here, but follow the same trends, just somewhat lower. The accuracy of prototypical networks is .686 for one support example, and .883 for 19.

heading: 4.3 EXPERIMENT B: ONE-WAY PROTOTYPICAL MODELS

text:
We next test the novel one-way configuration for prototypical models which distinguishes between a “positive” class that we are interested in, and a “null” class that is fixed at a zero centroid as described in section 3.1. The results are shown in figure 4. The first bar in each group is the two-way result from the previous experiment for comparison. The second one displays the accuracy of the same type of model, but with the null class instead of an explicit “negative” class. As mentioned above, we also test a model with reordered layers so that batch normalization comes last before the prototype calculation; the third bar shows the results for this model. We discover that the one-way realization works better in almost all cases. Results improve particularly in cases with few support examples. This makes sense, as few examples do not allow the two-way model to find the centroid of the negative class easily, whereas this is pre-defined in the one-way network. We also notice that the reordered model provides better results than the regular one; batch-normalizing our latent representations right before the prototype calculation therefore
appears to be important (we observe the same effect when simply adding another batch normalization layer to the standard model). With this model, accuracy on Omniglot rises to .969 for one support example, and to .98 for 19. On the more complex MiniImageNet data, accuracy becomes .64 for one support example and .8 for 20. For comparison, this re-ordering was also tested on the two-way prototypical model; no significant differences in the results were found when compared to the original layer ordering. Once again, we also test the Omniglot models on MNIST. For 19 support examples, the accuracy is slightly worse compared to the two-class model at .796. This makes sense as the batch normalization is optimized on Omniglot, and a large number of supports allows for a better estimation of the negative class’ distribution. However, results are better or equal for a small number of support examples (e.g. .743 for one).

heading: 4.4 EXPERIMENT C: NORMAL PROTOTYPICAL MODELS

text: Finally, we test the various configurations of our novel normal prototypical models described in section 3.2. The results are shown in figure 5. Out of these, the first bar in each group displays the two-way model accuracy from experiment A, in which the prototypes are modeled with a normal distribution. The second bar shows the results for the same model, but with a null class modeled with a unit Gaussian (mean 0, standard deviation 1) instead of the explicit negative class. Third, we allow the model to train the standard deviation of the null class instead of fixing it at 1. The fourth and fifth bars show results for similar models, but once again with the embedding layers reordered so that the last step before the prototype calculation is batch normalization. As described in experiment A, this type of model does not produce usable results with few support vectors, and may even fail to train. For this reason, we only show results for 5 or more support vectors. With three or more for Omniglot or 5 or more for MiniImageNet, we start to notice an improvement when using the one-way implementation over the two-way version - just as in the previous experiment. Once again, reordering the embedding layers to put batch normalization last increases accuracy, but the effect is not as strong as in standard prototypical models. Allowing the model to adapt the standard deviation of the null distribution during training also helps. This is somewhat surprising because batch normalization enforces a standard deviation of 1 over all data. We suspect that this happens because the actual distribution is not perfectly Gaussian, and therefore is not modeled well by our assumptions. We tested adding a loss term to enforce Gaussian-ness, but did not see any improvemtents. This effect will require closer investigation in the future. Over-all, the results follow the same trends as those of the standard prototypical models, but mostly remain slightly below them. However, for a larger number of support examples (≥15), they surpass them slightly in accuracy on the Omniglot data set. Future experiments with even more supports are necessary to determine where they become useful. Over-all, we obtain accuracies of .985 for Omniglot with 19 support examples, and .78 for MiniImageNet with 20. When testing the Omniglot models on MNIST, they yield an accuracy of .798.

heading: 4.5 EXPERIMENT D: TRAINING TIME

text: As an additional experiment, we analyze the training times of our various models on an NVIDIA Volta V100 with 16GB RAM. This is calculated by averaging the training times of the last three epochs of each model. Figure 6 displays the results on Omniglot and MiniImageNet. As mentioned above, each epoch consists of 32,000 episodes, and we choose the configuration with 5 support examples for comparison. The first two bars in each group correspond to the two-way matching and prototypical models from experiment A; their training times are roughly in the same range. Interestingly, the two-way normal prototypical model (fourth bar, also from experiment A) trains slightly faster on Omniglot and much faster for MiniImageNet while achieving almost the same results as the prototypical model. We are currently investigating the reasons for this. More importantly, bars three and five show the training times for the one-way implementations. For both prototypical and normal prototypical models, training time is almost halved. This is explained by the fact that only half the support examples need to be processed, and the centroids or distributions only need to be calculated for one class instead of two in each episode. As seen above, these models also usually deliver better results than the two-way implementations, thus providing another argument for their usage.

heading: 5 CONCLUSION AND FUTURE WORK

text: In this paper, we presented approaches for few-shot learning in cases where we are only interested in a single class in each episode. Naively, this can be modeled with a two-way matching or prototypical model with support examples for the relevant, “positive” class, and random other support examples for the “negative” class. This is not very elegant as selecting negative examples is difficult, and those may not reflect the negative class very well, especially when few supports are used. We suggest introducing a “null” class in prototypical models instead which does not require support examples. As batch normalization enforces zero centering in the latent space, we simply assume a zero centroid for this null class. We show that such models work better than the two-way implementation. Additionally, training time is reduced almost by a factor of two as only half of the support examples are required. As another novel idea, we suggest modeling class prototypes not just by their mean (or centroid), but by their distribution. We assume normal distributions here, and model them via their mean and standard deviation. In the one-way case, we model the null class with a multivariate unit Gaussian (with mean 0 and standard deviation 1). This has the disadvantage of requiring a sufficient number of support examples to estimate these parameters. If those are available, the approach generally works, but usually does not surpass the standard prototypical model below a certain number of support examples (around 15). We will further investigate whether these models can be useful when a very large number of support examples are available. There also is some evidence that such models train faster than standard prototypical models, which we will analyze. We suspect that one problem is the assumption of Gaussian-ness, which is not guaranteed in the latent space. It will be helpful to examine whether we can either enforce this, or otherwise find better ways to model the class distribution.

heading: A APPENDIX

text: You may include other additional sections here.


summaries: The authors propose a way to fuse information on nodes of a graph with the topology of the graph in the large scale setting. The proposed approach is done in four phases where (i) the covariates in the nodes of the graph is first mapped in the graph space for fusion and fused using linear combination of the topological graph and feature graph, (ii) the resulting "adjacency" matrix will almost surely not be sparse even if the original graph space, so they use eigenvalues of the graph laplacian to coarsen the graph -- remove edges; (iii) they then propose to embed the coarsened graph using "any" unsupervised learning technique; (iv) then the embedded representation is refined using iterative procedures. Cheap procedures are introduced to do Phases (i) and (iv). Experimentally the authors see improvements in the performance using their approach compared to the baselines considered.

summaries: This paper proposes GraphZoom, a framework for augmenting unsupervised graph embedding methods by (a) fusing feature information into the graph topology, (b) learning embeddings on a coarsened graph, and (c) refining the coarsened embeddings to obtain embeddings for the original graph nodes. In particular, a nearest neighbor graph over node features is computed and this adjacency matrix is linearly combined with the original adjacency matrix to obtain a graph with feature information "fused in". The graph is then coarsened using a spectral approach, embeddings are learned on the coarsened graph (via any strategy), and the embeddings are then refined back to the original nodes (again using a spectral approach). The authors take care to heed the advice of Maehara et al. and remove high-frequency information from the features.

summaries: The paper provides a multi-level graph-coarsening approach that can improve the predictive and computational performances of numerous existing unsupervised graph embedding models. The proposed approach is a pipeline consisting of 4 steps, viz: 1) Graph Fusion - that fuses attribute similarity graph with network topology, 2> Graph Coarsening - that reduces the graph size iteratively, 3> Graph embedding - using existing models and 4> Embedding refinement. While such a pipeline for scaling using a graph coarsening and refinement based approach is not new, the authors have carefully designed the pipeline to be effective and be scalable such as without any costly learning components (as in mile). The effectiveness of the proposed approach is evaluated with the node classification task on 6 datasets.

abstractText: Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, existing graph embedding models either fail to incorporate node attribute information during training or suffer from node attribute noise, which compromises the accuracy. Moreover, very few of them scale to large graphs due to their high computational complexity and memory usage. In this paper we propose GraphZoom, a multi-level framework for improving both accuracy and scalability of unsupervised graph embedding algorithms.1 GraphZoom first performs graph fusion to generate a new graph that effectively encodes the topology of the original graph and the node attribute information. This fused graph is then repeatedly coarsened into much smaller graphs by merging nodes with high spectral similarities. GraphZoom allows any existing embedding methods to be applied to the coarsened graph, before it progressively refine the embeddings obtained at the coarsest level to increasingly finer graphs. We have evaluated our approach on a number of popular graph datasets for both transductive and inductive tasks. Our experiments show that GraphZoom can substantially increase the classification accuracy and significantly accelerate the entire graph embedding process by up to 40.8×, when compared to the state-of-the-art unsupervised embedding methods.

authors:
Esra Akbas
Mehmet Aktas

title: Network Embedding: on compression and learning

venue: arXiv preprint:1907.02811,

authors:
Mikhail Belkin
Partha Niyogi

title: Laplacian eigenmaps for dimensionality reduction and data representation

venue: Neural Computation (NC),

authors:
Hongyun Cai
Vincent W Zheng
Kevin Chen-Chuan Chang

title: A comprehensive survey of graph embedding: Problems, techniques, and applications

venue: Transactions on Knowledge and Data Engineering (TKDE),

authors:
Haochen Chen
Bryan Perozzi
Yifan Hu
Steven Skiena

title: HARP: Hierarchical representation learning for networks

venue: The AAAI Conference on Artificial Intelligence (AAAI),

authors:
Jie Chen
Ilya Safro

title: Algebraic distance on graphs

venue: SIAM Journal on Scientific Computing (SISC),

title: Similarity-aware spectral sparsification by edge filtering

venue: Design Automation Conference (DAC),

authors:
Guoji Fu
Chengbin Hou
Xin Yao

title: Learning topological representation for networks via hierarchical sampling

venue: arXiv preprint:1902.06684,

authors:
Palash Goyal
Emilio Ferrara

title: Graph embedding techniques, applications, and performance: A survey

venue: Knowledge-Based Systems (KBS),

authors:
Aditya Grover
Jure Leskovec

title: node2vec: Scalable feature learning for networks

venue: International Conference on Knowledge Discovery and Data mining (KDD),

authors:
Caglar Gulcehre
Misha Denil
Mateusz Malinowski
Ali Razavi
Razvan Pascanu
Karl Moritz Hermann
Peter Battaglia
Victor Bapst
David Raposo
Adam Santoro
Nando de Freitas

title: Hyperbolic Attention Networks

venue: International Conference on Learning Representations (ICLR),

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: Neural Information Processing Systems (NeurIPS),

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: The Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Johannes Klicpera
Aleksandar Bojchevski
Stephan Günnemann

title: Combining neural networks with personalized pagerank for classification on graphs

authors:
Qimai Li
Zhichao Han
Xiao-Ming Wu

title: Deeper insights into graph convolutional networks for semi-supervised learning

authors:
Qimai Li
Xiao-Ming Wu
Han Liu
Xiaotong Zhang
Zhichao Guan

title: Label efficient semisupervised learning via graph filtering

authors:
Jiongqian Liang
Saket Gurukar
Srinivasan Parthasarathy

title: MILE: A multi-level framework for scalable graph embedding

venue: arXiv preprint:1802.09612,

authors:
Wenqing Lin
Feng He
Faqiang Zhang
Xu Cheng
Hongyun Cai

title: Effective and efficient network embedding initialization via graph partitioning

authors:
Oren E Livne
Achi Brandt

title: Lean Algebraic Multigrid (LAMG): Fast graph laplacian linear solver

title: Graph reduction with spectral and cut guarantees

venue: Journal of Machine Learning Research (JMLR),

title: Revisiting graph neural networks: All we have is low-pass filters

venue: arXiv preprint:1905.09550,

authors:
Richard Peng
He Sun
Luca Zanetti

title: Partitioning well-clustered graphs: Spectral clustering works

venue: The Conference on Learning Theory (COLT),

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: DeepWalk: Online learning of social representations

authors:
David I Shuman
Sunil K Narang
Pascal Frossard
Antonio Ortega
Pierre Vandergheynst

title: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

venue: Signal Processing Magazine (SPM),

authors:
Lei Tang
Huan Liu

title: Leveraging social media networks for classification

venue: Data Mining and Knowledge Discovery (DMKD),

authors:
Petar Veličković
William Fedus
William L. Hamilton
Pietro Liò
Yoshua Bengio
R Devon Hjelm

title: Deep Graph Infomax

authors:
Felix Wu
Tianyi Zhang
Amauri Holanda de Souza Jr.
Christopher Fifty
Tao Yu
Kilian Q Weinberger

title: Simplifying graph convolutional networks

venue: International Conference on Machine Learning (ICML),

authors:
Jaewon Yang
Jure Leskovec

title: Defining and evaluating network communities based on groundtruth

venue: Knowledge and Information Systems (KAIS),

authors:
Zhilin Yang
William W Cohen
Ruslan Salakhutdinov

title: Revisiting semi-supervised learning with graph embeddings

venue: arXiv preprint:1603.08861,

authors:
Daokun Zhang
Jie Yin
Xingquan Zhu
Chengqi Zhang

title: Network representation learning: A survey

venue: Transactions on Big Data (TBD),

authors:
Zhengyan Zhang
Cheng Yang
Zhiyuan Liu
Maosong Sun
Zhichong Fang
Bo Zhang
Leyu Lin

title: COSINE: Compressive network embedding on large-scale information networks

venue: arXiv preprint:1812.08972,

authors:
Zhiqiang Zhao
Zhuo Feng

title: Effective-resistance preserving spectral reduction of graphs

authors:
Jie Zhou
Ganqu Cui
Zhengyan Zhang
Cheng Yang
Zhiyuan Liu
Maosong Sun

title: Graph neural networks: A review of methods and applications

venue: arXiv preprint:1812.08434,

heading: 1 INTRODUCTION

text:
Recent years have seen a surge of interest in graph embedding, which aims to encode nodes, edges, or (sub)graphs into low dimensional vectors that maximally preserve graph structural information. Graph embedding techniques have shown promising results for various applications such as vertex classification, link prediction, and community detection (Zhou et al., 2018); (Cai et al., 2018); (Goyal & Ferrara, 2018). However, current graph embedding methods have several drawbacks in terms of either accuracy or scalability. On the one hand, random-walk-based embedding algorithms, such as DeepWalk (Perozzi et al., 2014) and node2vec (Grover & Leskovec, 2016), attempt to embed a graph based on its topology without incorporating node attribute information, which limits their embedding power. Later, graph convolutional networks (GCN) are developed with the basic notion that node embeddings should be smoothed over the entire graph (Kipf & Welling, 2016). While GCN leverages both topology and node attribute information for simplified graph convolution in each layer, it may suffer from high-frequency noise in the initial node features, which compromises
∗Equal contributions 1Source code of GraphZoom is freely available at: github.com/cornell-zhang/GraphZoom.
the embedding quality (Maehara, 2019). On the other hand, few embedding algorithms can scale well to large graphs with millions of nodes due to their high computation and storage cost (Zhang et al., 2018a). For example, graph neural networks (GNNs) such as GraphSAGE (Hamilton et al., 2017) collectively aggregate feature information from the neighborhood. When stacking multiple GNN layers, the final embedding vector of a node involves the computation of a large number of intermediate embeddings from its neighbors. This will not only cause drastic increase in the amount of computation among nodes, but also lead to high memory usage for storing the intermediate results.
In literature, increasing the accuracy and improving the scalability of graph embedding methods are largely viewed as two orthogonal problems. Hence most research efforts are devoted to addressing only one of the problems. For instance, Chen et al. (2018) and Fu et al. (2019) proposed multilevel methods to obtain high-quality embeddings by training unsupervised models at every level; but their techniques do not improve scalability due to the additional training overhead. Liang et al. (2018) developed a heuristic algorithm to coarsen the graph by merging nodes with similar local structures. They use GCN to refine the embedding results on the coarsened graphs, which is not only time consuming to train but also potentially degrading accuracy when the number of GCN layers increases. More recently, Akbas & Aktas (2019) proposed a similar strategy to coarsen the graph, where certain useful structural properties of the graph are preserved (e.g., local neighborhood proximity). However, this work lacks proper refinement methods to improve the embedding quality.
In this paper we propose GraphZoom, a multi-level spectral approach to enhancing both the quality and scalability of unsupervised graph embedding methods. More concretely, GraphZoom consists of four major kernels: (1) graph fusion, (2) spectral graph coarsening, (3) graph embedding, and (4) embedding refinement. The graph fusion kernel first converts the node feature matrix into a feature graph and then fuses it with the original topology graph. The fused graph provides richer information to the ensuing graph embedding step to achieve a higher accuracy. Spectral graph coarsening produces a series of successively coarsened graphs by merging nodes based on their spectral similarities. We show that our coarsening algorithm can effectively and efficiently retain the first few eigenvectors of the graph Laplacian matrix, which is critical for preserving the key graph structures. During the graph embedding step, any of the existing unsupervised graph embedding techniques can be applied to obtain node embeddings for the graph at the coarsest level. 2 Embedding refinement is then employed to refine the embeddings back to the original graph by applying a proper graph filter to ensure embeddings are smoothed over the graph.
We evaluate the proposed GraphZoom framework on three transductive benchmarks: Cora, Citeseer and Pubmed citation networks as well as two inductive dataset: PPI and Reddit for vertex classification task. We further test the scalability of our approach on friendster dataset, which contains 8 million nodes and 400 million edges. Our experiments show that GraphZoom can improve the classification accuracy over all baseline embedding methods for both transductive and inductive tasks. Our main technical contributions are summarized as follows:
•GraphZoom generates high-quality embeddings. We propose novel algorithms to encode graph structures and node attribute information in a fused graph and exploit graph filtering during refinement to remove high-frequency noise. This results in a relative increase of the embedding accuracy over the prior arts by up to 19.4% while reducing the execution time by at least 2×. • GraphZoom improves scalability. Our approach can significantly reduce the embedding run
time by effectively coarsening the graph without losing the key spectral properties. Experiments show that GraphZoom can accelerate the entire embedding process by up to 40.8× while producing a similar or better accuracy than state-of-the-art techniques. • GraphZoom is highly composable. Our framework is agnostic to underlying graph embedding
techniques. Any of the existing unsupervised embedding methods, either transductive or inductive, can be incorporated by GraphZoom in a plug-and-play manner.

heading: 2 RELATED WORK

text:
There is a large and active body of research on multi-level graph embedding and graph filtering, from which GraphZoom draws inspiration to boost the performance and speed of unsupervised
2In this work, we do not attempt to preserve node label information in the coarsened graph. Nonetheless, we believe that our approach can be extended to support supervised embedding models such as GAT (Gulcehre et al., 2019) and PPNP (Klicpera et al., 2019), as briefly discussed in Section 5.
embedding methods. Due to the space limitation, we only summarize some of the recent efforts in these two areas.
Multi-level graph embedding attempts to coarsen the original graph into a series of smaller graphs with decreasing size where existing or new graph embedding techniques can be applied at different coarsening levels. For example, Chen et al. (2018); Lin et al. (2019) generate a hierarchy of coarsened graphs and perform embedding from the coarsest level to the original one. Fu et al. (2019) construct and embed multi-level graphs through hierarchical, and the resulting embedding vectors are concatenated to obtain the final node embeddings for the original graph. These methods, however, only focus on improving embedding quality but not the scalability. Later, Zhang et al. (2018b); Akbas & Aktas (2019) attempt to make graph embedding more scalable by only embedding on the coarsest graph. However, their methods lack proper refinement methods to generate high-quality embeddings for the original graph. Liang et al. (2018) propose MILE, which only trains the coarsest graph to obtain coarse embeddings, and leverages GCN as refinement method to improve embedding quality. However, MILE requires training a GCN model which is very time consuming for large graphs and leading to poor performance when multiple GCN layers are stacked together (Li et al., 2018). In contrast to the prior arts, GraphZoom is motivated by theoretical results in spectral graph embedding (Tang & Liu, 2011) and practically efficient so that it can improve both accuracy and scalability of the unsupervised graph embedding tasks.
Graph filtering are direct analogs of classical filters in signal processing field, but intended for signals defined on graphs. Shuman et al. (2013) define graph filters in both vertex and spectral domains, and apply graph filter on image denoising and reconstruction tasks. Wu et al. (2019) leverage graph filter to simplify GCN model by removing redundant computation. More recently, Maehara (2019) show the fundamental link between graph embedding and filtering by proving that GCN model implicitly exploits graph filter to remove high-frequency noise from the node feature matrix; a filter neural network (gfNN) is then proposed to derive a stronger graph filter to improve the embedding results. Li et al. (2019) further derive two generalized graph filters and apply them on graph embedding models to improve their embedding quality for various classification tasks. In GraphZoom we adopt graph filter to properly smooth the intermediate embedding results during the iterative refinement step, which is crucial for improving the quality of the final embedding.
3 GRAPHZOOM FRAMEWORKGraphZoom Framework
Figure 1 shows the proposed GraphZoom framework, which consists of four key phases: Phase (1) is graph fusion, which combines the node attributes and topology information of the original graph to construct a fused weighted graph; In Phase (2), a spectral graph coarsening process is applied to form a hierarchy of coarsened fused graphs with decreasing size; In Phase (3), any of the existing graph embedding methods can be applied to the fused graph at the coarsest level; In Phase (4), the embedding vectors obtained at the coarsest level are mapped onto a finer graph using the mapping
operators determined during the coarsening phase. This is followed by a refinement (or smoothing) procedure, where the procedure in Phase (4) is applied in an iterative manner to increasingly finer graphs; Eventually the embedding vectors for the original graph are obtained. In the rest of this section, we describe each of these four phases in more detail.

heading: 3.1 PHASE 1: GRAPH FUSION

text:
Graph fusion aims to construct a weighted graph that has the same number of nodes as the original graph but potentially different set of edges (weights) that encapsulate the original graph topology as well as node attribute information. Specifically, given an undirected graph G = (V, E) with N = |V| nodes, its adjacency matrix Atopo ∈ RN×N and its node attribute (feature) matrix X ∈ RN×K , where K corresponds to the dimension of node attribute vector, graph fusion can be interpreted as a function f(·) that outputs a weighted graph Gfusion = (V, Efusion) represented by its adjacency matrix Afusion ∈ RN×N , namely, Afusion = f(Atopo, X). We first convert the initial attribute matrixX into a weighted node attribute graph Gfeat = (V, Efeat) by generating a k-nearest-neighbor (kNN) graph based on the l2-norm distance between the attribute vectors of each node pair. A straightforward implementation requires comparing all possible node pairs and then selecting top-k nearest neighbors. However, such a naı̈ve approach has a worstcase time complexity of O(N2), which certainly does not scale to large graphs. Our goal is to construct the attribute graph in nearly linear time by leveraging an efficient spectral graph coarsening scheme that is described in more detail in Section 3.2. More specifically, our approach starts with coarsening the original graph G to obtain a substantially reduced graph that has much fewer nodes with an O(|E|) time complexity. Note that this procedure bears similarity to spectral graph clustering, which aims to group nodes into clusters of high conductance (Peng et al., 2015). Once the node clusters are formed through spectral coarsening, we can select the top-k nearest neighbors within each cluster with O(M2) comparisons, where M is the average node count per cluster. Since we have roughly N/M clusters, the time complexity for constructing the approximate kNN graph is O(MN). When a proper coarsening ratio is chosen where M N (e.g., M = 50), the overall time complexity will become almost linear.
After the attribute graph is formed, we assign a weight to each edge based on the cosine similarity between the attribute vectors of the two incident nodes, namely wi,j = (Xi,: ·Xj,:)/(‖Xi,:‖‖Xj,:‖), where Xi,: and Xj,: are the attribute vectors of nodes i and j. Finally, we can construct the fused graph by combining the topology graph and the attribute graph using a weighted sum: Afusion = Atopo +βAfeat, where β allows us to balance the topological and node attribute information during the fusion process. This fused graph can be fed into any downstream graph embedding procedures.

heading: 3.2 PHASE 2: SPECTRAL COARSENING

text:
Graph coarsening via global spectral embedding. To reduce the size of the original graph while preserving important spectral properties (e.g., the first few eigenvalues and eigenvectors of the graph Laplacian matrix 3), a straightforward way is to first embed the graph into a k-dimensional space using the first k eigenvectors of the graph Laplacian matrix, which is also known as the spectral graph embedding technique (Belkin & Niyogi, 2003; Peng et al., 2015). Next, the graph nodes that are close to each other in the low-dimensional embedding space can be aggregated to form the coarse-level nodes and subsequently the reduced graph. However, it is very costly to calculate the eigenvectors of the original graph Laplacian, especially for very large graphs.
Graph coarsening via local spectral embedding. In this work, we leverage an efficient yet effective local spectral embedding scheme to identify node clusters based on emerging graph signal processing techniques (Shuman et al., 2013). There are obvious analogies between the traditional signal processing (Fourier analysis) and graph signal processing: (1) The signals at different time points in classical Fourier analysis correspond to the signals at different nodes in an undirected graph; (2) The more slowly oscillating functions in time domain correspond to the graph Laplacian eigenvectors associated with lower eigenvalues or the more slowly varying (smoother) components across the graph. Instead of directly using the first few eigenvectors of the original graph Laplacian,
3Laplacian matrix L is defined as L = D −A, where D is degree matrix and A is adjacency matrix.
we apply the simple smoothing (low-pass graph filtering) function to k random vectors to obtain smoothed vectors for k-dimensional graph embedding, which can be achieved in linear time.
Consider a random vector (graph signal) x that is expressed with a linear combination of eigenvectors u of the graph Laplacian. We adopt low-pass graph filters to quickly filter out the high-frequency components of the random graph signal or the eigenvectors corresponding to high eigenvalues of the graph Laplacian. By applying the smoothing function on x, we obtain a smoothed vector x̃, which is basically the linear combination of the first few eigenvectors:
x = ΣNi=1αiui smoothing =====⇒ x̃ = Σni=1α̃iui , n N (1)
More specifically, we apply a few (typically five to ten) Gauss-Seidel iterations for solving the linear system of equations LGx(i) = 0 to a set of t initial random vectors T = (x(1), . . . , x(t)) that are orthogonal to the all-one vector 1 satisfying 1>x(i) = 0, and LG is the Laplacian matrix of graph G or Gfusion. Based on the smoothed vectors in T , we embed each node into a t-dimensional space such that nodes p and q are considered spectrally similar if their low-dimensional embedding vectors xp ∈ Rt and xq ∈ Rt are highly correlated. Here the node distance is measured by the spectral node affinity ap,q for neighboring nodes p and q (Livne & Brandt, 2012; Chen & Safro, 2011):
ap,q = |(Tp,:,Tq,:)|2
‖Tp,:‖2‖Tq,:‖2 , (Tp,:,Tq,:) = Σ
t k=1(x (k) p · x(k)q ) (2)
Once the node aggregation schemes are determined, we can easily obtain the graph mapping operator Hi+1i between two coarsening levels i and i+ 1. More precisely, H i+1 i is a matrix of size |VGi+1 | × |VGi |. (Hi+1i )p,q = 1 if node q in graph Gi is aggregated to (clustered) node p in graph Gi+1; otherwise, it is set to 0. Additional discussions on the properties of Hi+1i are available in Appendix F, which shows this operator a surjective mapping and locality preserving.
We leverage H10 , H 2 1 , · · · , H ll−1 for constructing a series of spectrally-reduced graphs G1,G2, · · · ,Gl. Specifically, The coarser graph Laplacian LGi+1 can be computed by Eq. (3). It is worth noting that G0 (i.e., Gfusion) is the original fused graph and |V0| = N > |V1| > · · · > |Vl|.
LGi+1 = H i+1 i LGiH i i+1, H i i+1 = (H i+1 i ) T (3)
We emphasize that the aggregation scheme based on the above spectral node affinity calculations will have a (linear) complexity of O(|Efusion|) and thus allow preserving the spectral (global or structural) properties of the original graph in a highly efficient and effective way. As suggested in (Zhao & Feng, 2019; Loukas, 2019), a spectral sparsification procedure can be applied to effectively control densities of coarse level graphs. In this work, a similarity-aware spectral sparsification tool “GRASS” (Feng, 2018) has been adopted for achieving a desired graph sparsity at the coarsest level.

heading: 3.3 PHASE 3: GRAPH EMBEDDING

text: Embedding the Coarsest Graph. Once the coarsest graph Gl is constructed, node embeddings El on Gl can be obtained by El = g(Gl), where g(·) can be any unsupervised embedding methods.

heading: 3.4 PHASE 4: EMBEDDING REFINEMENT

text:
Given Ei+1, the node embeddings of graph Gi+1 at level i + 1, we can use the corresponding projection operator Hii+1 to project Ei+1 to Gi, which is the finer graph at level i:
Êi = H i i+1Ei+1 (4)
Due to the property of the projection operator, embedding of the node in the coarser graph will be directly copied to the nodes of the same aggregation set in the finer graph at the preceding level. In this case, spectrally-similar nodes in the finer graph will have the same embedding results if they are aggregated into a single node during the coarsening phase.
To further improve the quality of the mapped embeddings, we apply a local refinement process motivated by Tikhonov regularization to smooth the node embeddings over the graph by minimizing the following objective:
min Ei { ∥∥∥Ei − Êi∥∥∥2 2 + tr(EiTLiEi)} (5)
where Li and Ei are the normalized Laplacian matrix and mapped embedding matrix of the graph at the i-th coarsening level, respectively. We obtain the refined embedding matrix Ẽi by solving Eq. (5). Here the first term enforces the refined embeddings to agree with mapped embeddings, while the second term employs Laplacian smoothing to smooth Ẽi over the graph. By taking the derivative of the objective function in Eq. (5) and setting it to zero, we have:
Ei = (I + Li) −1 Êi (6)
where I is the identity matrix. However, obtaining refined embeddings in this manner can be very inefficient since it involves matrix inversion whose time complexity is O(N3). Instead, we exploit a more efficient spectral graph filter to smooth the embeddings.
By transforming h(L) = (I + L)−1 into spectral domain, we obtain the graph filter: h(λ) = (1 + λ)−1. To avoid the inversion term, we approximate h(λ) by its first-order Taylor expansion, namely, h̃(λ) = 1 − λ. We then generalize h̃(λ) to h̃k(λ) = (1 − λ)k, where k controls the power of graph filter. After transforming h̃k(λ) into the spatial domain, we have: h̃k(L) = (I − L)k = (D− 1 2AD− 1 2 )k, where A is the adjacency matrix and D is the degree matrix. It is not difficult to
show that adding a proper self-loop for every node in the graph will allow h̃k(L) to more effectively filter out high-frequency noise components (Maehara, 2019) (see Appendix H). Thus, we modify the adjacency matrix as Ã = A + σI , where σ is a small value to ensure every node has its own self-loop. Finally, the low-pass graph filter can be utilized to smooth the mapped embedding matrix, as shown in (7):
Ei = (D̃i − 12 ÃiD̃i − 12 )kÊi = (D̃i − 12 ÃiD̃i − 12 )kHii+1Ei+1 (7)
We iteratively apply Eq. (7) to obtain the embeddings of the original graph (i.e., E0). Note that our refinement stage does not involve training and can be simply considered as several (sparse) matrix multiplications, which can be efficiently computed.

heading: 4 EXPERIMENTS

text: We have performed comparative evaluation of GraphZoom framework against several state-of-theart unsupervised graph embedding techniques and multi-level embedding frameworks on five standard graph-based datasets (transductive as well as inductive). In addition, we evaluate the scalability of GraphZoom on Friendster dataset, which contains 8 million nodes and 400 million edges. Finally, we conduct ablation study to understand the effectiveness of the major GraphZoom kernels.

heading: 4.1 EXPERIMENTAL SETUP

text:
Datasets. Table 1 reports the statistics of the datasets used in our experiments. We include Cora, Citeseer, Pubmed, and Friendster for evaluation on transductive learning tasks, and PPI as well as
Reddit for inductive learning. We split the training and testing data in the same way as suggested in Kipf & Welling (2016); Hamilton et al. (2017).
Transductive baseline models. A number of popular graph embedding techniques are transductive learning methods, which require all nodes in the graph be present during training. Hence such embedding models must be retrained whenever a new node is added. Here we compare GraphZoom with three transductive models: DeepWalk (Perozzi et al., 2014), node2vec (Grover & Leskovec, 2016), and Deep Graph Infomax (DGI) (Veličković et al., 2019) 4. These methods have shown stateof-the-art unsupervised embedding results on the datasets used in our experiments. In addition, we compare GraphZoom with two multi-level graph embedding frameworks: HARP (Chen et al., 2018) and MILE (Liang et al., 2018), which have reported improvement over DeepWalk and node2vec in either embedding quality or scalability.
Inductive baseline models. In contrast to transductive tasks, training an inductive graph embedding model does not require seeing the whole graph structure. Hence the resulting trained model can still be applied when new nodes are added to graph. To show GraphZoom can also enhance inductive learning, we compare it against GraphSAGE (Hamilton et al., 2017) using four different aggregation functions including GCN, mean, LSTM, and pooling.
More details of datasets and baselines are available in Appendix A and B. We optimize hyperparameters of DeepWalk, node2vec, DGI, and GraphSAGE to achieve highest possible accuracy on original datasets; we then choose the same hyperparameters to embed the coarsened graph in HARP, MILE, and GraphZoom. We run all the experiments on a Linux machine with an Intel Xeon Gold 6242 CPU (32 cores @ 2.40GHz) and 384 GB of RAM.

heading: 4.2 PERFORMANCE AND SCALABILITY OF GRAPHZOOM

text:
Since HARP and MILE only support transductive learning, we compare them with GraphZoom using DeepWalk, node2vec, and DGI (Veličković et al., 2019) as embedding kernels. For inductive tasks, we compare GraphZoom with GraphSAGE using four different aggregation functions.
Tables 2 and 3 report the mean classification accuracy for the transductive task and micro-averaged F1 score for the inductive task, respectively, as well as the execution time for all baselines and GraphZoom. Specifically, we use the CPU time for graph embedding as the execution time of DeepWalk, node2vec, DGI, and GraphSAGE. We further measure the execution time of HARP and MILE by summing up CPU time for graph coarsening, graph embedding, and embedding refinement. Similarly, we add up the CPU time for graph fusion, graph coarsening, graph embedding, and embedding refinement as the execution time of GraphZoom. In regard to hyperparameters, we use 10 walks with a walk length of 80, a window size of 10, and an embedding dimension of 128 for both DeepWalk and node2vec; we further set the return parameter p and the in-out parameter q in node2vec as 1.0 and 0.5, respectively. Moreover, we choose early stopping strategy for DGI with a learning rate of 0.001 and an embedding dimension of 512. Apropos the configuration of GraphSAGE, we train a two-layer model for one epoch, with a learning rate of 0.00001, an embedding dimension of 128, and a batch size of 256.
Comparing GraphZoom with baseline embedding methods. We show the results of GraphZoom with three coarsening levels for transductive learning and two levels for inductive learning. The size of coarsened graphs and results with larger coarsening level are available in Appendix D, Figure 3 (blue curve), and the Appendix J. Our results demonstrate that GraphZoom is agnostic to underlying embedding methods and capable of boosting the accuracy and speed of state-of-the-art unsupervised embedding methods on various datasets.
More specifically, for transductive learning tasks, GraphZoom improves classification accuracy upon both DeepWalk and node2vec by a relative gain of 8.3%, 10.4%, and 19.4% 5 on Cora, Pubmed, and Citeseer, respectively, while achieving up to 40.8× run-time reduction. In regard to comparing with DGI, GraphZoom achieves comparable or better accuracy with speedup up to 11.2×. Similarly, GraphZoom outperforms all the baselines by a margin of 3.4% and 3.3% on PPI and Reddit for inductive learning tasks, respectively, with speedup up to 7.6×. These results indicate that our
4DGI also supports inductive tasks, although the authors have only released the source code for transductive learning at github.com/PetarV-/DGI, as of the date of this experiment.
5GZoom(N2V, l=1) improves over node2vec on Citeseer by 19.4% = (54.7− 45.8)/45.8.
multi-level spectral approach improves both embedding speed and quality — GraphZoom runs much faster since we only train the embedding model on the smallest fused graph at the coarsest level. In addition to reducing the graph size, our coarsening method further filters out redundant information from the original graph while preserving key spectral properties for the embedding. Hence we also observe improved embedding quality in terms of classification accuracy.
Comparing GraphZoom with multi-level frameworks. As shown in Table 2, HARP slightly improves the accuracy in several cases but increases the CPU time. Although MILE improves both accuracy and speed over a few baseline embedding methods, the performance of MILE becomes worse with increasing coarsening levels. For instance, the classification accuracy of MILE drops from 0.708 to 0.618 on Pubmed dataset with node2vec as the embedding kernel. GraphZoom achieves a better accuracy and speedup compared to MILE with the same coarsening level across all datasets. Moreover, when increasing the coarsening levels, namely, decreasing number of nodes on the coarsened graph, GraphZoom still produces comparable or even a better embedding accuracy with much shorter CPU times. This further confirms GraphZoom can retain the key graph structure information to be utilized by underlying embedding models to boost embedding quality. More results of GraphZoom on non-attributed graph for both node classification and link prediction tasks are available in Appendix K.
GraphZoom for large graph embedding. To show GraphZoom can significantly improve performance and scalability of underlying embedding model on large graph, we test GraphZoom and MILE on Friendster dataset, which contains 8 million nodes and 400 million edges. For both cases,
we use DeepWalk as the embedding kernel. As shown in Figure 2, GraphZoom drastically boosts the Micro-F1 score up to 47.6% compared to MILE and 49.9% compared to DeepWalk with a speedup up to 119.8×. When increasing the coarsening level, GraphZoom achieves a higher speedup while the embedding accuracy decreases gracefully. This shows the key strength of GraphZoom: it can effectively coarsen a large graph by merging many redundant nodes that are spectrally similar, thus preserving the graph spectral (structural) properties that are important to the underlying embedding model. When applying basic embedding model on coarsest graph, it can learn more global information from spectral domain, leading to high-quality node embeddings. On the contrary, heuristic graph coarsening algorithm used in MILE fails to preserve a meaningful coarsest graph, especially when coarsening graph by a large reduction ratio.

heading: 4.3 ABLATION ANALYSIS ON GRAPHZOOM KERNELS

text:
To study the effectiveness of our proposed GraphZoom kernels separately, we compare each of them against the corresponding kernel in MILE while fixing other kernels. As shown in Figure 3, when fixing coarsening kernel and comparing refinement kernel of GraphZoom with that of MILE, Our re-
finement kernel can improve embedding results upon MILE refinement kernel, especially when the coarsening level is large. This indicates that our proposed graph filter in refinement kernel can successfully filter out high-frequency noise from the graph to improve embedding quality. Similarly, when comparing coarsening kernels in GraphZoom and MILE with the refinement kernel fixed, GraphZoom coarsening kernel can also improve embedding quality upon MILE coarsening kernel, which shows that our spectral graph coarsening algorithm can indeed retain key graph structure for underlying graph embedding models to exploit. When combining the GraphZoom coarsening and refinement kernels, we can achieve a better classification accuracy compared to the ones using any other kernels in MILE. This suggests that the GraphZoom coarsening and refinement kernels play useful yet distinct roles to boost embedding performance and their combination can further improve embedding result. Moreover, adding graph fusion improves classification accuracy by a large margin, which indicates that graph fusion can properly incorporate both graph topology and node attribute information that are crucial for lifting the embedding quality of downstream embedding models. Results of each kernel CPU time and speedup comparison are available in Appendix G and Appendix I.

heading: 5 CONCLUSIONS

text: This work introduces GraphZoom, a multi-level framework to improve the accuracy and scalability of unsupervised graph embedding tasks. GraphZoom first fuses the node attributes and topology of the original graph to construct a new weighted graph. It then employs spectral coarsening to generate a hierarchy of coarsened graphs, where embedding is performed on the smallest graph at the coarsest level. Afterwards, proper graph filters are used to iteratively refine the graph embeddings to obtain the final result. Experiments show that GraphZoom improves both classification accuracy and embedding speed on a number of popular datasets. An interesting direction for future work is to derive a proper way to propagate node labels to the coarsest graph, which would allow GraphZoom to support supervised graph embedding.

heading: ACKNOWLEDGMENTS

text: This work is supported in part by Semiconductor Research Corporation and DARPA, Intel Corporation under the ISRA Program, and NSF Grants #1350206, #1909105, and #1618364. We would like to thank Prof. Zhengfu Xu of Michigan Technological University for his helpful discussion on the formulation of the embedding refinement problem.

heading: APPENDIX A DETAILS OF DATASETS

text:
Transductive task. We follow the experiments setup in Yang et al. (2016) for three standard citation network benchmark datasets: Cora, Citeseer, and Pubmed. In all these three citation networks, nodes represent documents and edges correspond to citations. Each node has a sparse bag-of-word feature vector and a class label. We allow only 20 labels per class for training and 1, 000 labeled nodes for testing. In addition, we further evaluate on Friendster dataset (Yang & Leskovec, 2015), which contains 8 million nodes and 400 million edges, with 2.5% of the nodes used for training and 0.3% nodes for testing. In Friendster, nodes represent users and a pair of nodes are linked if they are friends; each node has a class label but is not associated with a feature vector.
Inductive task. We follow Hamilton et al. (2017) for setting up experiments on both proteinprotein interaction (PPI) and Reddit dataset. PPI dataset consists of graphs corresponding to human tissues, where nodes are proteins and edges represent interaction effects between proteins. Reddit dataset contains nodes corresponding to users’ posts: two nodes are connected through an edge if the same users comment on both posts. We use 60% nodes for training, 40% for testing on PPI and 65% for training and 35% for testing on Reddit.

heading: APPENDIX B DETAILS OF BASELINES

text:
DeepWalk first generates random walks based on graph structure. Then, walks are treated as sentences in a language model and Skip-Gram model is exploited to obtain node embeddings.
node2vec is different from DeepWalk in terms of generating random walks by introducing the return parameter p and the in-out parameter q, which can combine DFS-like and BFS-like neighborhood exploration.
Deep Graph Infomax (DGI) is an unsupervised approach that generates node embeddings by maximizing mutual information between patch representations (local information) and corresponding high-level summaries (global information) of graphs.
GraphSAGE embeds nodes in an inductive way by learning an aggregation function that aggregates node features to obtain embeddings. GraphSAGE supports four different aggregation functions: GraphSAGE-GCN, GraphSAGE-mean, GraphSAGE-LSTM and GraphSAGE-pool.
HARP coarsens the original graph into several levels and apply underlying embedding model to train the coarsened graph at each level sequentially to obtain the final embeddings on original graph. Since the coarsening level is fixed in their implementation, we run HARP in our experiments without changing the coarsening level.
MILE is the state-of-the-art multi-level unsupervised graph embedding framework and similar to our GraphZoom framework since it also contains graph coarsening and embedding refinement kernels. More specifically, MILE first uses its heuristic-based coarsening kernel to reduce the graph size and trains underlying unsupervised graph embedding model on coarsest graph. Then, its refinement kernel employs Graph Convolutional Network (GCN) to refine embeddings on the original graph. We compare GraphZoom with MILE on various datasets, including Friendster that contains 8 million nodes and 400 million edges (shown in Table 2 and Figure 2). Moreover, we further compare each kernel in GraphZoom and MILE in Figure 3.

heading: APPENDIX C INTEGRATE GRAPHZOOM WITH GRAPHSAGE AND DGI

text:
As both GraphSAGE and DGI require node features for embedding on coarsest graph, we map the initial node feature matrix X0 to the coarsened graph by iteratively performing Xi+1 = Ĥi+1i Xi, where Ĥi+1i is the mapping operatorH i+1 i with l
1-normalization per row. When applying DGI to the coarsest graph (i.e., the l-th coarsening level), the node embeddings El may lose local information due to the property of DGI. Inspired by skip connection (He et al., 2016) and Graph U-nets (Gao & Ji, 2019), we use Êl = El||Xl as the node embeddings on the coarsest graph, where || denotes featurewise concatenation.

heading: APPENDIX D GRAPH SIZE AT DIFFERENT COARSENING LEVEL

heading: APPENDIX E GRAPHZOOM ALGORITHM

text:
Algorithm 1: GraphZoom algorithm Input: Adjacency matrix Atopo ∈ RN×N ; node feature matrix X ∈ RN×K ;
base embedding function g(·); coarsening level l Output: Node embedding matrix E ∈ RN×D
1 A0 = graph fusion(Atopo,X); 2 for i = 1...l do 3 Ai,H i i−1 = spectral coarsening(Ai−1); 4 end 5 EL = g(Al); 6 for i = l...1 do 7 Êi−1 = (H i i−1) T Ei;
8 Ei−1 = refinement(Êi−1); 9 end
10 E = E0;

heading: APPENDIX F SPECTRAL COARSENING

text:
Coarsening is one type of graph reduction whose objective is to achieve computational acceleration by reducing the size (i.e., number of nodes) of the original graphs while maintaining the similar graph structure between the original graph and the reduced ones. For each coarsen level i + 1, a surjection is defined between the original node set Vi and the reduced node set Vi+1, where each node v ∈ Vi+1 corresponds to a small set of adjacent vertices in the original node set Vi. Mapping operator Hi+1i can be defined based on the mapping relationship between Vi and Vi+1, Note that the operator Hi+1i ∈ {0, 1}|
Vi+1|×|Vi| is a matrix containing only 0s and 1s. It has following properties:
• The row (column) index of Hi+1i corresponds to the node index in graph Gi+1 (Gi). • It is a surjective mapping of the node set, where (Hi+1i )p,q = 1 if node q in graph Gi is aggregated
to super-node p in graph Gi+1, and (Hi+1i )p′,q = 0 for all nodes p′ ∈ {v ∈ Vi+1 : v 6= p}. • It is a locality-preserving operator, where the coarsened version of Gi induced by the non-zero
entries of (Hi+1i )p,: is connected for each p ∈ Vi+1.
Algorithm 2: spectral coarsening algorithm
Input: Adjacency matrix Ai ∈ R|Vi|×|Vi| Output: Adjacency matrix Ai+1 ∈ R|Vi+1|×|Vi+1| of the reduced graph Gi+1, mapping operator H i+1i ∈ R|
Vi+1|×|Vi| 1 n = |Vi|, nc = n; 2 [graph reduction ratio] γmax = 1.8 , δ = 0.9; 3 for each edge (p, q) ∈ Ei do 4 [spectral node affinity set] C← ap,q defined in Eq. 2 ; 5 end 6 for each node p ∈ Vi do 7 d(p) =
∣∣∣(Ai)p,:∣∣∣, dm(p) = median(∣∣∣(Ai)q,:∣∣∣ for all q ∈ {q|(p, q) ∈ Ei}); 8 if d(p) ≥ 8 · dm(p) then 9 [node aggregation flag] z(p) = 0;
10 else 11 [node aggregation flag] z(p) = −1; 12 end 13 end 14 γ = 1; 15 while γ < γmax do 16 S = ∅ , U = ∅ ; 17 [unaggregated node set] U← p ∈ {p|z(p) == −1 ∀p ∈ Vi};
18 S← p ∈ {p|ap,q ≥ δ ·max s 6=p,q
( max
(p,s)∈ Ei
( ap,s ) , max (q,s)∈ Ei ( aq,s )) ∀p ∈ Vi};
19 for each node p in S ∩ U do 20 if z(p) == −1 then
21 q = argmax (p,q)∈ Ei
( ap,q ) ;
22
23 if z(q) == −1 then 24 z(q) = 0, z(p) = q, q̂ = q; 25 else if z(q) == 0 then 26 z(p) = q, q̂ = q;

heading: 27 else

text: 28 z(p) = z(q), q̂ = z(q);

heading: 29 end

text: 30 update smoothed vectors in T with x(k)p = x (k) q̂ for k = 1, · · · , t nc = nc − 1; 31 end 32 end 33 γ = n/nc, δ = 0.7 · δ ; 34 z(p) = p for node p ∈ {p|z(p) == 0} 35 end 36 form H i+1i and Ai+1 based on z

heading: APPENDIX G CPU TIME OF EACH GRAPHZOOM KERNEL

text: As shown in Figure 4 (note that the y axis is in logarithmic scale), the GraphZoom embedding kernel dominates the total CPU time, which can be more effectively reduced with a greater coarsening level L. All other kernels in GraphZoom are very efficient, which enable the GraphZoom framework to drastically reduce the total graph embedding time.

heading: APPENDIX H GRAPH FILTERS AND LAPLACIAN EIGENVALUES

text:
Figure 5a shows the original distribution of graph Laplacian eigenvalues which also can be interpreted as frequencies in graph spectral domain (smaller eigenvalue means lower frequency). The proposed graph filter for embedding refinement (as shown in Figure 5e) can be considered as a bandstop filter that passes all frequencies with the exception of those within the middle stop band that is greatly attenuated. Therefore, the band-stop filter may not be very effective for removing highfrequency noises from the graph signals. Fortunately, it has been shown that by adding self-loops to each node in the graph as follows Ã = A+σI (shown in Figure 5b, 5c, 5d, where σ = 0.5, 1.0, 2.0), the distribution of Laplacian eigenvalues can be squeezed to the left (towards zero) (Maehara, 2019). By properly choosing σ such that large eigenvalues will mostly lie in the stop band (e.g., σ = 1.0, 2.0 shown in Figure 5c and 5d), the graph filter will be able to effectively filtered out high-frequency components (corresponding to high eigenvalues) while retaining low-frequency components, which is similar to a low-pass graph filter as shown in Figure 5f. It is worth noting that if σ is too large, then most eigenvalues will be very close to zero, which makes the graph filter less effective for removing noises. In this work, we choose σ = 2.0 for all our experiments.
APPENDIX I SPEEDUP OF GRAPHZOOM KERNELS COMPARED TO MILE
As shown in Figure 6, the combination of GraphZoom coarsening and refinement kernels can always achieve the greatest speedups (green curves); adding GraphZoom fusion kernel (blue curves) will lower the speedups by a small margin but further boost the embedding quality, showing a clear trade-
off between embedding quality and runtime efficiency: to achieve the highest graph embedding quality, the graph fusion kernel should be included.

heading: APPENDIX J MORE RESULTS ON PPI DATASETS

text:
As shown in Figure 7, the embedding results by GraphZoom with increasing number of coarsening levels are still better than the ones by GraphSAGE with different aggregation functions. It is worth noting that although the level-5 (coarsened) graph contains only 120 nodes (as shown in D), Graph-
Zoom embedding results can still beat the GraphSAGE baseline obtained with the original graph containing 14, 755 nodes.

heading: APPENDIX K MORE RESULTS ON NON-ATTRIBUTED DATASETS

text: To further show that GraphZoom can work on non-attributed datasets, we evaluate it on PPI(Homo Sapiens) and Wiki datasets, following the same dataset configuration as used in Grover & Leskovec (2016); Liang et al. (2018). As shown in Table 5, GraphZoom (without fusion kernel) improves the performance of basic embedding model (i.e., DeepWalk) at the first coarsening level. When further increasing coarsening level, GraphZoom achieves much larger speedup while its performance may drop a little bit. For link prediction task, we follow Grover & Leskovec (2016) by choosing Hadamard operator to transform node embeddings into edge embeddings. Our link prediction results show that GraphZoom significantly improve performance by a margin of 18.5% with speedup up to 52.0×, showing GraphZoom can generate high-quality embeddings for various tasks.

heading: APPENDIX L SENSITIVITY ANALYSIS OF GRAPH FUSION KERNEL

text:
As graph fusion kernel fuses node attribute with graph topology via Afusion = Atopo +βAfeat, the value of β plays a critical role in balancing attribute and topological information. On the one hand, if β is too small, we may lose too much node attribute information. On the other hand, if β is too
large, the node attribute information will dominate the fused graph and therefore graph topological information is undermined. As shown in Figure 8, we vary β from 0.1 to 3 in graph fusion kernel and evaluate it on Cora, Citeseer, and Pubmed datasets. The results indicate that β = 1 achieves the best performance on Cora and Pubmed, while β = 0.5 is the best configuration on Citeseer. We choose β = 1 in all our experiments.