Understanding the limitations of network online learning

Our goal at every time t is to choose a node that maximizes the earned reward. However, since the reward distribution is based on node degree, and the degree distribution in many real-world networks is heavy-tailed (e.g. hubs are present), we expect the reward distribution of an incomplete version of the network to be heavy-tailed as well. In order to deal with the heavy tailed nature of the target variable, we adapt the methods from (Hsu and Sabato 2016) for regression in the presence of heavy-tailed distributions. This process is a generalization of the median of means approach to parameter estimation. Intuitively, the algorithm splits the previously observed feature vectors and associated rewards into k subsamples, then computes parameters ω for each subsample. Then, the algorithm chooses the set of parameters that has the minimum median distance from all of the other parameters. This procedure provides guarantees and confidence bounds on the distance of the learned parameters from the true parameters (Hsu and Sabato 2016), discussed further in Scalability & guarantees section.

Algorithm 2 presents our adopted process. At time t, t−1 nodes with feature vectors x_i∈X have been probed, and their corresponding reward values r_i∈Y observed. We select an integer k≤t and randomly sample the data into k subsamples S_i of size \(\frac {t}{k}\). Then, the covariance matrix Σ_i and maximum likelihood regression estimate ω_i are computed for each S_i. For each i, the Mahalanobis distance between ω_i and every other ω_j is computed, and the median distance is assigned to m_i. Finally, the ω_i with the minimum m_i value is assigned to be the next set of parameters, θ.

There are two parameters in Algorithm 2: the number of subsamples k, which corresponds to the confidence parameter δ in Hsu and Sabato (2016), and the regularization parameter λ. The number of subsamples k should be set such that the size of the subsamples, \(\frac {n}{k}\), is larger than O(d log(d)), meaning each subsample has size at least the number of dimensions in the feature vector (Hsu and Sabato 2016). In our experiments, we set k to be ln(n), where n is the number of previously queried nodes (equivalently the time step t), which allows k to grow slowly as more data is gathered through the querying process. We set the regularization parameter λ to 0. However, our feature matrices may be singular (since some subsamplings can result in feature matrices without full rank), so when computing the regression in Algorithm 2 we use the Moore-Penrose pseudoinverse, which corresponds to computing the ℓ₂ regularized parameters.

NOL* algorithms need to learn adaptively over time because the reward distribution may change as nodes are queried. Choosing a node based on \(V_{\theta _{t}}\)exploits the current model by choosing the node with the maximum predicted reward. However, learning in networks is difficult precisely because the properties of nodes are diverse, thus it is desirable to introduce some randomness to the decision process in order to gather a diverse set of training examples. Therefore, we formulate NOL* algorithms as ε-greedy algorithms, meaning with probability ε the node to query is chosen uniformly at random from the set of unprobed nodes.

In order to increase the likelihood that our random samples are informative, we choose our random nodes from those that were present in the initial network \({\hat {G}}_{0}\). The rationale behind this choice is that as a consequence of probing nodes sequentially nodes that have been in the network for longer have more “complete” information, since they have had more opportunity to be connected to in the t−1 probes before time t. That is, if a node \(j \in {\hat {G}}_{0}\) has only a few neighbors after many queries have been made, it could be that j has very few neighbors, but it could also be that j connects to a neighborhood that the algorithm has yet to discover. Therefore, to explore the possibility of learning a better model using different information, NOL* algorithms select the random node from \({\hat {V}}_{0} - P_{t}\) to probe until all nodes in \({\hat {V}}_{0}\) are exhausted, when NOL* chooses any unprobed node in \({\hat {G}}_{t}\) at random.

Since NOL* algorithms learn from all or most of the previous samples at every time step, it is not strictly necessary to continue random exploration through the entire querying process. This is consistent with the literature on ε-greedy algorithms, which often systematically lower the rate of exploration over time (Kirkpatrick et al. 1983; Cheng et al. 2010). NOL* adds an optional exponential decay to the initial random jump rate ε₀, such that at time t the jump rate is computed as \(\epsilon _{t} = \epsilon _{0} e^{\frac {-t}{b}}\). We have also experimented with data-driven methods for adaptive- ε-greedy, such as in Tokic (2010), but did not find them to be advantageous and leave further investigation of their utility in this space for future work.

In general, the computational complexity of a NOL* algorithm is the product of (1) the budget, (2) the feature computation complexity and (3) the learning complexity. In symbols, O(b×O(features)×O(learning)).

In this section, we briefly discuss the complexity of the learning steps of NOL and NOL-HTR. We also note that the features used in NOL* algorithms are user defined and range from trivial to compute (e.g. degree) to computationally expensive (e.g. node embeddings). Due to this, we omit a detailed analysis of the specific features we use in our experiments (described in Experiments section), but note that since the computations are to happen online, and only nodes whose features may have changed should be updated, the complexity depends not necessarily on the total number of nodes or edges in the graph, but on the size of the neighborhood around the queried node for which the features might have changed.

The complexity of a NOL online regression update depends only on the number of features, since the most expensive operation required is multiplication of the feature vector by a constant factor. Due to this, even with a relatively high-dimensional feature vector, the complexity of the learning step is trivial. In this case, the scalability of the entire process will likely hinge on the scalability of the feature value updates.

The procedure to learn parameters for NOL-HTR is more complicated. The data is first partitioned into k subsamples, the covariance of each subsample is computed and optimal regression parameters are estimated for each, and finally the median of the k parameters is computed. The most expensive operation is the regression parameter estimation, which requires computing the Moore-Penrose inverse of the regressor matrix. This can be computed via Singular Value Decomposition of the matrix, which has complexity O(nd²), where n is the number of nodes in the computation and d is the number of features.

Hsu and Sabato (2016) also derive a bound on the loss and show that our learned parameters θ are within an ε of the true parameters if we use Algorithm 2 with the number of samples \(m\geq O\left (d\log \left (\frac {1}{\delta }\right)\right)\). In our case, m is the number of rows in X. The derived bound states that with probability (1−δ) the empirical loss is bounded by where L_∗ is the true loss with the optimal parameters and \(\delta =\frac {1}{e^{k}}\). In practice, we avoid wasted computation by limiting the total number of samples m to 2000, which is always larger than is necessary for the guarantees given the values of k in our experiments (which determines delta in our formulation of the algorithm).

We test NOL* algorithms on a range of synthetic graphs, as well as five real world datasets.

To accurately predict the number of unobserved neighbors of a partially observed node, NOL* algorithms require interpretable node features that are relevant across a variety of very different network structures. These features must be feasible to compute and update online for our algorithms to be scalable. We use the following features for each node i visible in the sample network:

We compare the performance of NOL* with 4 heuristic baseline methods and a multi-armed bandit method. Our heuristic baselines are as follows:

We also compare our approach with the nonparametric multi-armed bandit model proposed in Madhawa and Murata (2019), which we refer to as KNN-UCB (k-nearest-neighbors upper confidence bound). This method similarly relies on computing a vector of structural features for each node, including degree, average neighbor degree, median neighbor degree and average fraction of probed neighbors. Each unprobed node is considered an arm in a Multi-armed Bandit formulation, and the next arm to pull (node to probe) is chosen by computing Here, \(\hat {f}(x_{i})\) is the expected reward of probing node i and σ(x_i) is the average distance to other points in the neighborhood. The expected reward is calculated as a weighted k-NN regression on nodes within the k-NN radius of node i, defined as the k nodes whose feature vectors have Euclidean distance less than r from the feature vector of node i. The term ασ(x_i) facilitates exploration by allowing the possibility of nodes without maximum expected reward to be probed, assuming α>0. In our experiments we fixed the value of k=20 and α=2, following the experiments in the original paper.

Across all networks, our experiments are run over 20 independent initial node samples of the network. In synthetic networks, the underlying network is a realization of the model using the parameters described in Synthetic models section.

Our experiments aim to (1) investigate how network properties impact the performance of NOL-HTR, (2) exhibit the performance tradeoffs between NOL-HTR and NOL, (3) show that NOL* algorithms outperform the baseline methods in settings where learning is possible and approximate the heuristic methods elsewhere, (4) analyze the prediction error of NOL-HTR, and (5) analyze the evolution of the feature weights learned by NOL-HTR over time.

After each probe of the network, NOL* earns a reward, defined in this work as the number of previously unobserved nodes included in the network after a probe. Formally, the reward at time t is defined as r_t=|V_t+1|−|V_t|. We study the performance of each method by showing the cumulative reward, \(\hat {c}_{r}(T)\), where T is a time step between \(0, 1, 2, \dots b\). Formally, \(\hat {c}_{r}(T) = {\sum \nolimits }_{t = 1}^{T} r_{t}\). We also want to quantify the utility of decisions made by NOL*. For this purpose, we study the prediction error of the model. This quantifies the extent to which our prediction, \({\mathcal {V}}_{\theta _{t}}(i) =\theta _{t}\phi _{t}(i)\), differs from the true reward value r_t. Thus, we calculate \(E(t) = {\mathcal {V}}_{\theta _{t}}(i) - r_{t} \).

We ran a two dimensional parameter search over values of k (1-16, 32, 64, 128, log10(n), loge(n), log2(n)) and ε (0, 0.1, 0.2, 0.3, 0.4, and exponential decay versions of each). We ran this search on all of the networks in Fig. 2, as well as 56 LFR networks (Lancichinetti et al. 2008) spanning a wide variety of network structures. We varied two parameters in the LFR networks: μ, which controls modular structure by adjusting the probability of cross-community links; and γ, which controls the exponent of the degree distribution of the entire network (Lancichinetti et al. 2008).

Across all of these networks, we did not observe a general trend in which some parameter settings performed best consistently across experiments. There was not a single best choice or regime of parameters through the experiments for any of the networks we searched on individually, nor was there a standout choice of parameter across the networks.

However, we have found some evidence to suggest that performance on more modular structures is improved by more randomization, meaning a non-zero value of ε. We ran a linear regression using ε as the target variable and global clustering, modularity, and degree exponent as covariates. Results are presented in Table 2. All three covariates positively effected ε, with modularity having the strongest effect. This result is consistent with a network scientific understanding of the querying process: when querying a modular network structure, the likelihood of finding a local minima within one highly connected and clustered module is high, meaning that adding more randomness to the algorithm will increase the likelihood that the algorithm sees examples that allow it to avoid settling on such a minima.

We report results using a set of parameters that performed reasonably well across networks. These parameters are ε=0.3, decaying as \(\epsilon _{t} = 0.3 e^{\frac {-t}{b}}\) and k= ln(t), where t represents the number of nodes probed thus far in the experiment.

In this section, we compare the performance of the heuristic baseline methods, the KNN-UCB baseline approach, NOL, and NOL-HTR. Broadly, we find that NOL-HTR and NOL perform similarly in terms of average cumulative reward, but that the performance of NOL-HTR is more consistent, indicated by standard deviations that are tighter around the mean across experiments.

Cumulative reward We report the average cumulative reward \(\hat {c}_{r}(T)\) over a budget of thousands of probes on 6 networks in Fig. 3. The average and standard deviation of \(\hat {c}_{r}(T)\) are computed over experiments on 20 independent samples. We omit results on ER networks, noting that because all nodes are statistically equivalent in terms of structural properties, every probing method performs equivalently and neither learning or heuristics provide any significant advantage (see Appendix A.1).

In BA networks (Fig. 3a), NOL-HTR performs on par with the High Degree baseline, which is known to be near optimal in networks with heavy tailed degree distributions (Avrachenkov et al. 2014). Further, NOL-HTR outperforms NOL by achieving both higher average reward and smaller standard deviation. NOL-HTR also consistently outperforms the baseline methods in networks generated by the BTER model (Fig. 3b). Although NOL-HTR outperforms NOL in both reward and variance towards the beginning of the experiment, after around 25% of the nodes have been probed NOL begins to outperform NOL-HTR. See Comparing NOL and NOL-HTR section for a discussion of some potential explanations for this observation. NOL-HTR performed as well as NOL and the best heuristics in every real world network we experimented on. Comparing directly with NOL, NOL-HTR is able to achieve similar or better performance, always with smaller standard deviation, on every network, regardless of the underlying distributions (compare networks in Fig. 2). We note that across experiments, the KNN-UCB method was unable to match the performance of our model and often underperformed the baseline methods.⁷

Use case: twitter social network We present results on a social interaction network sampled from Twitter in Fig. 4. In this setting, querying a node corresponds to calling the Twitter API to obtain more data about a specific account. This is an example of a natural use case for NOL-HTR, both because the network must be expanded by repeatedly accessing an API and because there is evidence that the distribution of social interactions is heavy-tailed (see e.g. Kossinets and Watts 2006 and Morales et al. 2012).

This Twitter Social Network data set consists of Twitter users connected to one another with an undirected edge if they mutually retweeted or mentioned each other throughout the course of a single day in 2009. We focus our experiment on the largest connected component of this interaction network. While this is only a small fraction of the Twitter network, the data was collected via the Twitter Firehose, and is therefore complete for that time span, which allows us to accurately simulate the process of growing a network by querying Twitter users. Some other characteristics of the dataset are outlined in Table 1 and the distributions of degree and clustering are shown in Fig. 2. Notably in our context, though the maximum degree in this network is not very large (≈100), choosing a random node with degree near the maximum is much less likely than choosing a node with low degree.

As shown in Fig. 4, NOL outperforms the heuristic baseline methods and NOL-HTR.⁸ However, the inset plot shows that, similar to the experiments on other networks, NOL-HTR outperforms NOL early in the experiment before eventually being overtaken. We discuss our conjectures about why we observe this trade-off behavior in Comparing NOL and NOL-HTR section.

Prediction error We analyze the ability of NOL* to learn by showing the measure of prediction error, E(t), defined in Performance metrics section, over time and across different initial sample sizes.

Cumulative prediction error, E(T), as a function of time is shown in Fig. 5. The error is averaged over 10 independent samples of the network for initial sample sizes of 1%, 2.5%, 5%, 7.5% and 10% of the complete network (as percent of edges in the network).

The Caida and Enron networks were exceptions to the above general trends, though NOL-HTR exhibits similar performance on these networks in terms of cumulative reward. In these experiments, the weight of the degree feature was centered around 0 along with the other features, but with very large fluctuations in both positive and negative directions. This suggests that the importance assigned to degree depended strongly on the particular subsampling of the data in an individual time step. It may also have implications for the impact of degree correlations (i.e. average neighbor degree), since the fluctuations are consistent with both low and high degree nodes predicting high reward.

The above analysis illustrates some differences and tradeoffs between NOL and NOL-HTR: (1) NOL-HTR achieves similar performance to NOL and is more consistent. This is evidenced by the tighter standard deviations around the average cumulative reward. (2) NOL-HTR outperforms NOL in the beginning of every experiment. This is consistent with our expectation based on how each of the algorithms work: NOL-HTR is able to leverage outlier, high reward queries early on because it computes maximum likelihood parameters at every step, while NOL updates its parameters with online gradient descent using a fixed learning rate, and is therefore not able to adapt as effectively to high reward nodes. (3) As the number of probes increases, NOL often begins to outperform NOL-HTR. There are a few possibilities for why this is happening. First, NOL is learning through gradient descent, so adjusting the learning rate of the algorithm could impact the amount of examples in the tail it takes to reach highly predictive parameters, explaining the lag. Second, as the number of samples grows, the NOL-HTR parameter setting of k=ln(n) grows very slowly. This means that more data is being subsampled into the same number of bins, thus each subsample may become more noisy and the outliers become less distinguishable. This could be alleviated by increasing the value of k more quickly as the number of samples grow, or by capping the size of the subsamples, or by choosing the sample size so that data from the tail is more likely to have an impact on the parameters.

We are interested in understanding the limitations of our approach in this setting. We experiment across a wide variety of network structures using the LFR community benchmark (Lancichinetti et al. 2008). We generated 56 LFR networks spanning two parameters: μ, which controls modular structure by adjusting the probability of cross-community links; and γ, which controls the exponent of the degree distribution of the entire network. Then, we ran the NOL-HTR parameter search (see NOL-HTR parameter search section) on each network, as well as random and high degree baseline methods. For each network, we found the set of NOL-HTR parameters that resulted in the maximum average cumulative reward and computed the percent gain in performance using either of the baselines as

Results are shown in Fig. 6. Compared with high degree probing (left plot), NOL-HTR is always able to gain in performance in higher modularity networks (Q>0.6), with performance gains spanning from 15-30% up to about 130%. When modularity is lower, including in the BA model realization, NOL-HTR approximates high degree across degree exponents, with the maximum performance loss of less than 3% (−2.54%) compared to the heuristic.

Comparing with random degree probing (right plot), NOL-HTR is always able to gain in performance, with minimum performance gain of 5% and maximum of 93%. The maximum gains are in networks with the most heterogeneous degree distributions. This corresponds to the most star-like network structures, meaning most randomly chosen nodes will have very low degree.

The performance compared to random degree probing in the real networks seem to fit with performance on LFR networks with similar parameters, allowing for some noise in either direction.

Comparing with high degree on BTER, Caida, Cora and Enron, performance appears to be about on par with similar LFR networks, again allowing for some noise. Performance gain by using NOL-HTR rather than high degree in the DBLP network is substantial, but smaller than an LFR network with similar properties.

The degree exponent estimate for our Twitter sample is an outlier in this dataset. However, there is also substantial performance gain, though it might be smaller than what we would expect given an LFR network with similar properties.

Taken together, these results show that the ability of our model to learn in this setting is tied to the structural properties of the network. In some cases, a low computational cost heuristic such as high or random degree can perform well, but our experiments show that there is almost never a disadvantage to using a NOL* algorithm, and that the advantages can be substantial, up to 130% gains in performance.

In Fig. 7, we present cumulative reward results on an ER network (left) and a k-regular network (right). The result on the ER network shows that every querying strategy performs indistinguishably from the others. This is due to the fact that the degree distribution of the network is homogeneous, meaning that the expected number of neighbors of each node is well defined and the same for all nodes. Since the expected number of neighbors is the same for every node, but the exact number of neighbors for a given node is random, no querying strategy is able to outperform any other.

In the k-regular network, every node has exactly the same degree, but the particular neighbors are randomly chosen. Since every node has the same degree, choosing the lowest degree node is approximately optimal when maximizing the number of newly observed connections. For the same reason, choosing the highest degree node is usually far from optimal, since the maximum degree node in the sample will have degree nearly k, thus the minimum reward. This explains why high degree is the worst performer.

In Fig. 8, we present analysis of feature weights from a NOL-HTR experiment, showing how the feature weights change as querying continues, averaged over 20 trials. The purpose is to show that it is possible to analyze the learned feature weights to help understand why NOL* algorithms perform the way they do. We choose NOL-HTR here, but in principle any parameterized model could be temporally analyzed in a similar fashion.

In the BA example (Fig. 8a), the LostReward feature, which takes order effects of querying into account (see Experiments section), appears as the most positively weighted feature. This makes some intuitive sense: hubs accumulate larger values of lost reward over time, since many nodes brought in by other queries are connected after they eventually get queried. This means the hubs are “missing out” on reward and since they are in fact the best nodes to probe, this is reflected in the weights of the features. This implies that in a BA network, we expect that the degree and lost reward features will be correlated. This correlation provides a potential explanation for why degree is, somewhat counterintuitively, one of the least important features when querying a BA network: the degree of hub nodes is being accounted for in the lost reward feature, so degree itself does not have a strong impact.

In the BTER example (Fig. 8b), the normalized size of the connected component that a node is in is the most highly weighted feature. As a reminder, BTER networks are generated by constructing many ER networks (“communities”) of different sizes, where the size of the networks follows a power law distribution, then connecting them to one another. This means there are a small number of very large and relatively well connected “communities”, which are the best place to query to bring in new nodes.

In Fig. 9 we show results of NOL* algorithms starting from random walk samples. The sampling works as follows: a node is chosen uniformly at random, then a random walk from that node proceeds until the desired proportion of edges is discovered, jumping randomly 15% of the time. The resulting performance is similar to what we saw in the node sampling with induction samples: NOL* algorithms are able to learn to match or outperform the heuristic methods in almost every case. However, the performance of NOL appears to be more consistent on random walk samples, as evidenced by the fact that the standard deviation around the mean performance tends to be tighter. The performance of NOL-HTR is approximately the same or even slightly worse (e.g. BTER) on the random walk samples. The low degree heuristic also appears to perform better on random walk samples.

In this section, we show some experiments using node2vec (Grover and Leskovec 2016) as features, rather than our hand selected features. Since node2vec is significantly more computationally expensive, we expect a tradeoff between computation time and performance increases due to more expressive features. However, the results shown in Fig. 10 present a mixed picture: In some cases, using the embedding features makes no improvement or can even degrade performance. Only in one case, the Cora network, do the node2vec features truly outperform the others, and even then only with one of the learning algorithms (NOL-HTR). These results are inconclusive on the benefit of using embeddings as features and show that more experimentation and research needs to be done to understand the tradeoff between complexity of features and improvement in performance.