{'fraction_non_alphanumeric': 0.037360618618362026, 'fraction_numerical': 0.006408339385653865, 'mean_word_length': 4.761137090819592, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Inferring Network Structure From Data

Networks are complex models for underlying data in many application domains. In most instances, raw data is not natively in the form of a network, but derived from sensors, logs, images, or other data. Yet, the impact of the various choices in translating this data to a network have been largely unexamined. In this work, we propose a network model selection methodology that focuses on evaluating a network's utility for varying tasks, together with an efficiency measure which selects the most parsimonious model. We demonstrate that this network definition matters in several ways for modeling the behavior of the underlying system.


Introduction
Networks are complex models for underlying data in many application domains. Networks model relationships between people, animals, genes, proteins, documents, media, language, products, etc. Often, we think of "the network" for an underlying system, for example, consider the social network of Zachary's karate club [1]. An edge in this network is defined as whether two individuals interacted outside of the club. But we cannot observe raw interaction data in terms of frequency, strength, missing data; many other networks from this data could have represented this classical network and a different network definition may yield different analyses and results on this network. In fact, most networks are not explicitly and unambiguously defined. For example, biological networks often measure correlations between the biological processes of cells, genes, or proteins. Human contact and social networks are often inferred from repeated interactions. These particular network definitions may also be very time-sensitive. Yet, they are often preprocessed, published, and analyzed as aggregated networks over time, which may produce different conclusions based on this choice of time scale [2,3].
Multiple network repositories collect such preprocessed networks, largely without retaining the underlying raw data [4,5]. A network is not in and of itself a valuable representation for gaining a deeper understanding of the underlying system. Are these and other networks useful representations for measuring and studying the behavior of the systems they model? Figure 1 presents the traditional experimental science process and its corresponding data science modeling. Traditionally, experimentation is used to evaluate hypotheses and measure the behavior of interest in the underlying system. A data science model for this process constructs a representation over raw input data. This data is not natively in the form of a network and is subject to sampling/collection biases and limitations in measurement. These limitations, and other choices in network representation matter. Prior work has largely ignored the challenges of translating raw data into a network representation and the downstream implications. [6] Instead, a great deal of work focuses on • Ivan Brugere is with the Department of Computer Science, University of Illinois at Chicago, E-mail: ibruge2@uic.edu • Tanya Berger-Wolf is at the Ohio State University and University of Illinois at Chicago, Email: berger-wolf.1@osu.edu Fig. 1: A schematic overview of an observational science process, and its data-science modeling. Data-driven science models create representations (e.g. networks) on raw input data where edges or nodes are not natively and unambiguously defined. Much data science work focuses on the latter arc of this modeling to develop novel machine learning models to measure behavior on a given network structure.
the latter piece of this modeling process: developing novel machine learning models on a given network structure to measure behavior in the underlying system. Why ought we construct a network representation in the first place? First, a network for a particular predictive task should perform better than an unstructured model which doesn't account for the relationships among entities (e.g. users). Evaluating network models against population methods measures whether there is a network effect at all within the underlying system. Also, high-order network properties (e.g. degree distribution, centrality, diffusion) are well studied. These properties can help generate hypotheses, and yield comparative analysis across diverse domains.
In this work, we propose a task-based network model selection methodology that compares multiple representations for predicting a particular behavior of the underlying system. We have two primary findings. First, we demonstrate that the best network definition is task-dependent. That is, different network models are better representations for different tasks and there may not be one network representation for all tasks. Second, in many instances, what we think of as network tasks are more efficiently modeled by non-network representations such as clustering or population sampling.
Our strategy is to select or tune a network definition from a library of functions that transform the underlying data to a network representation. Work in network model selection has typically focused on inferring parameters of generative arXiv:2004.02046v1 [cs.SI] 4 Apr 2020 models from a given network, according to some structural or spectral features (e.g. degree distribution, eigenvalues) [7]. In contrast, we focus on selecting a representation that best performs a task or set of tasks. This current work combines and simplifies our prior methodological works for translating raw data to a network representation to perform particular tasks or behaviors [8,9]. We further extend this task-focused network model selection methodology, using minimum description length (MDL) criteria for selection. Our methodology measures predictive efficiency, a general and comparable measure of the network's performance of a local (i.e. node-level) predictive task of interest. This accounts for the complexity of both the network structure and the task predictor. Selection on efficiency favors parsimonious models and can be applied across arbitrary tasks and representations. We show stability, sensitivity, and significance testing in our methodology.

Contributions
In this work, we formulate a task-focused model selection methodology for networks, and an extension for parsimonious network model selection.
• Model selection methodology: We propose a generalized approach for evaluating networks inferred from data for performing particular tasks. • Network efficiency: We propose a general minimum description length (MDL) efficiency measure on the encoding of network representations and task models, which is comparable over varying models and datasets and encourages model sparsity. • Validation and significance We empirically demonstrate stability, sensitivity, and significance testing of models chosen by our model selection methodology. Our work focuses on process and methodology; the development of novel network inference methods and task methods are complementary but distinct from this work. Our work demonstrates that the network definition is a crucial step for evaluating predictive methods on networks.

Methods
Model selection for task-focused network inference selects a network model and associated parameters of structured predictors to best perform a task or set of tasks on the topology. We ultimately evaluate the efficiency of that coupling of the network and a method's performance on a given task. Figure 2 presents a high-level overview of our model selection methodology. In Figure 2(a) as input, we are given raw data, assumed to be about a set of entities, which we will define as nodes, their attribute-set, and a node labelset. 1 Attributes are any data associated with nodes. These are often very high dimensional, for example, user activity logs and post content in social networks, gene expression profiles in gene regulatory networks, or full document text and other metadata in content networks. Labels are a notational convenience that allows differentiating input attributes from an attribute of interest for some predictive task (e.g. label inference, link prediction). Labels are typically low-cardinality fields (e.g. boolean, categorical).
In Figure 2(b), we apply a collection of network inference methods to generate separate network topologies. For example, we illustrate a threshold network, where edges are defined by a global similarity threshold between node attribute distributions. In contrast, the k-nearest neighbor network (KNN) defines edges as the k most similar nodes to a given node. In Figure 2(c), for each inferred network, we apply several node weight functions that yield a subset of nodes to build a predictor. We illustrate network adjacency (green), and the community affiliation (blue) of node i, where multiple colors represent nodes in both categories. Fig. 2: A high-level overview of our methodology. (a) Given as input: nodes with associated attribute and label data. For example, attributes are some arbitrary distribution, and labels are a categorical value (Purple, Orange). (b) On the input data, we define networks according to a collection of network models and their hyper-parameters. (c) We generate node subsets based on various node weighting functions. Illustrated is the node subset corresponding to network adjacency (green) and nodes within the same community as node i (blue). (d) We train predictors on the node subsets generated by our node weighting function, for all nodes. We evaluate this set of predictors and select the network and node weighting function which maximizes our selection criteria. In this particular example, our framework selects the Threshold network, using adjacency weighting.
In Figure 2(d), for each network, each of these weight functions yields a subset of nodes for the training of task predictors (e.g. node label inference, link prediction). Each row corresponds to a supervised classification task trained on attributes and labels in the node subset given by a different node weight rule. We evaluate all combinations of networks and their weighting functions and select a network inferenceweight function pair. In our example, our methodology chooses a threshold network, where predictors are trained on network adjacency.

Preliminaries and notation
Let V = {1..., i..., n} be a set of nodes representing entities within the system. Let A = { a 1 , ..., a n } be a set of attributevectors and L = {l 1 , ..., l n } be a set of target labels of interest to be learned. Let M(A) → E be a network inference function that yields an edge-set E on some measure of node attributes. Let W M (i) → U be a node weight function on the network inferred from M to produce a node subset U . Let C : A × L → L be a classifier trained on attributes and labels to produce a prediction l i for node i. 2

Node weighting/prioritization
In our methodology, we induce a network structure using some method M, (e.g. KNN). However, the topology of this network can be used in various ways to train a predictor for a given node i. We abstract this modeling choice as a node weight function: This function can be implemented as matrix W , where element w i,j is the probability that node j is in U , where a weighted sampling on w i yields U . This definition is general enough to encompass both deterministic and probabilistic functions. Deterministic functions include network adjacency. Probabilistic functions can be estimated using re-sampling 2. Throughout, capital letters denote sets, lowercase letters denote instances and indices. Script characters (e.g. C) and keywords (e.g. bytes()) denote functions, teletype (e.g. KNN-bfs) denotes models, square brackets (e.g. A[U ]) denote the restriction of a set to a subset. techniques such as the bootstrap [29]. For example, we sample a node's community node-set uniformly at random to produce a node subset U of fixed size k. Similarly, breadthfirst node ordering from node i is used to produces a fixedlength node subset of size k, where order at each depth is randomized. The above functions illustrate that W need not only be the weighted network of E (e.g. weighted network inference) but may incorporate higher-order such as communities or higher-order neighbors.
Our general formulation allows us to define or learn any node weight function which outputs node subsets for training, including non-network functions not subject to edge-set E. In geometric space, W l2 (i) may order nodes by increasing Euclidean distance from i. We also define heuristics derived only from statistics on node attributes or network measures such as degree (see: Section 2.5) which measures the extent that a small number of exemplar nodes are predictive of the network.
Below, we focus on probabilistic functions that are comparable across node subsets of a fixed size k. For simplicity, we omit the bootstrapping notation since it is identical to the deterministic case for model selection.

NETWORK MODEL SELECTION
Let W M (i) → U i be a node weight function outputting node subsets U i for each node i. We train each classifier from the attributes and labels of these sampled nodes. Let C r be the resulting set of trained predictors on r = W M : Let measure(C r ) be an evaluation measure over all predictors in C r . In our case, we use precision as the base measure because each of our applications is a rare-label classification task.
We can now formally define our network model selection problem. This problem selects the (1) network inference function M, and (2) the node weight function W which maximizes 'measure': This selected representation is the best for performing a particular task on the underlying nodes, e.g. link prediction Problem 1: Task-Focused Network Inference Model Selection Given: A set of nodes V , node attribute-set A, node label-set L, network inference functions M ∈ M , node weight functions WM ∈ S, Task predictor C(.) Select: Node weight function W M ∈ S Where: W M = argmax r measure (Cr) or label prediction. In the case of our probabilistic weighting functions that sample at a fixed size of k, this is a hidden hyperparameter that yields distinct weight functions at each k. Selecting on these functions also selects the best (fixed) k.

Network Efficiency
Our initial problem statement doesn't account for the representation size for performing the predictive task. For example, if a dense network and a sparse network have a similar precision on the task, the sparse network is a more parsimonious model for the task. Therefore, we formulate a minimum description length (MDL) model selection criterion, which accounts for this representation cost.
Let correct(C r ) simply be the sum of correct predictions over all predictors on test input. Analogous to precision above, correct predictions are appropriate for our classimbalanced prediction problem and will yield an interpretable MDL measure. Definition 1. The efficiency of a network and its weighting W M for a node i is the number of correct predictions per byte (higher is better). As above, we handle the hyperparameter k in the probabilistic case which cancels out of the deterministic definition. The efficiency E of an individual node is defined: where bytes(.) is the representation cost of encoding the predictor(s) for node i.
Let κ i = argmax k E(W M , i), the k associated with the maximum efficiency of node i. We then sum over these κ to get the most efficient (variable-sized k) representation over all nodes: Then, the overall efficiency of W M is given by: We can then use this definition to re-formulate an MDL criterion of our above problem statement: For brevity, we refer to 'model selection' simply as selecting the network representation and its node weight function. A key point is that we measure the efficiency of the node weighting function. In many instances W M may be implemented more with greater space-efficiency than the edge-set produced by M. For example, community/cluster affiliation can be encoded as a single list of size O(|V |).

Problem 2: MDL Task-Focused Network Inference Model Selection
Given: A set of nodes V , node attribute-set A, node label-set L, network weight function-set S where WM ∈ S, Task C(.) Select: Network weight function W M ∈ S Where: W M = argmax E(WM) Therefore, the model selection on our efficiency criterion measures whether a network is a better model than other non-network weight functions, group-wise weighting (e.g. communities), etc. accounting for the varying representation cost of each.
Previous work has evaluated network model-selection for robustness to multiple tasks (e.g. link prediction, label prediction) as well as different base predictor models (e.g. random forests, support vector machines) [8]. Problem 2 can straightforwardly select over varying underlying network definitions, tasks, or task predictors that maximize efficiency. We simplify the selection criteria to focus on measuring the efficiency of node weight functions and their underlying representations, but this current work is complimentary to evaluating over larger parameter-spaces.

Network Models
We define several network models for our study. Our focus is not to propose a novel network inference model from attributes (see: [16,17]). Instead, we apply existing common and interpretable network models to demonstrate our framework. The efficiency of any novel network inference model should be evaluated against these standard baselines.
A network model M constructs an edge-set from node attributes and/or labels: We use k-nearest neighbor (KNN) and Threshold (TH) models which are ubiquitous in many domains. Given a similarity measure d( a i , a j ) → s ij and a target edge count ρ, this similarity is used to produces a pairwise attribute similarity space. We select edges by: . Let these edge-sets be denoted E KNN and E TH , respectively. We use varying network sparsity (ρ) on these network models to define 'sparse' or 'dense' network models. Similarity measures may vary greatly by the application. We use cosine similarity, which is ubiquitous, especially in information retrieval and recommender system applications. Table 1 summarizes the node weight functions (Equation 1) used in our methodology. We define only a small number of possible functions, focusing on an interpretable set that

GRAPH-TRAVERSAL WEIGHTING (LOCAL)
The bfs weighting method uses a breadth-first exploration on an underlying edge-set E from seed i. This is encoded by an adjacency list in O(|E|). In other analyses, we use either fixed neighborhood weighting or egonet weighting (in the link-prediction task). Each is a special case of bfs. We also refer to these as 'local' node weight methods. The activity-net weighting method is an inferred network where all out-edges point to some node in the top-(= 0.1) fraction of nodes with respect to activity-top. This is a KNN network, constrained to high-activity nodes. The additional encoding cost relative to activity-top measures the extent that specialization exists in the topranked individuals as a set of exemplars for all nodes (i.e. the individual exemplar relations matter). degree-net is defined analogously with respect to degree-top.

Tasks for Evaluating Network Models
We evaluate network models on two fundamental network tasks: collective classification and link prediction.

COLLECTIVE CLASSIFICATION (CC)
The collective classification problem learns relationships between network edge structure and attributes and/or labels to predict label values [31,32]. This task is often used to infer unknown labels on the network from 'local' discriminative relationships in attributes, e.g. labeling political affiliations, brand or media preferences.

LINK PREDICTION (LP)
The link prediction problem [12] learns a method for the appearance of edges from one edge-set to another. Link prediction methods can incorporate attribute and/or label data, or using simple structural ranking [33].
For this problem, we fix the weighting method to generate node pairs within the 'egonet' induced subgraph. We construct edge attributes by the difference in node attribute vectors and learn a balanced edge/non-edge predictor on these features.

TASK PREDICTORS
To demonstrate our methodology, we use Random Forest and Support Vector Machine (SVM) task predictors. The Random Forest is straightforwardly encoded as its underlying decision trees (lists), and the aggregation weights of the trees. SVMs are similarly encoded as the hyperplane coefficients.

Measuring Efficiency
Our node weight functions and task predictors can now be represented as a byte-encoded object 'o' (e.g. lists). We can now measure efficiency (Equation 5). To implement our bytes(o) function estimating the minimum description length, we convert each object representation to a byte-string using LZ4 compression, 4 (analogous to zip) which uses Huffman coding to reduce the cost of the most common elements in the representation string (e.g high degree nodes, frequent features in the random forest). This method was chosen primarily for runtime performance since we do many compression operations over each candidate network topology. Finally, we report the length of the compressed byte-string: 2.7.1 NODE WEIGHT FUNCTION REACH Let the reach-set of C r , reach(C r ) be defined as the set of nodes accessed at least once to train any predictor in C r . We define W * r as the representation of W r including only nodes in the reach-set. If the underlying representation of W r is a graph, the W * r representation is an induced subgraph where both nodes incident to an edge are in the reach-set. If W r is represented as a list, we simply remove elements that are not in the reach-set.
The encoding size bytes(W * r ) measures only the underlying representation accessed for the creation of the C r task predictor set. This is a more appropriate measure of the representation cost. In practice, |reach(C r )| << |V |. For our evaluation, we always report E(W * r ).

Datasets
We demonstrate our model selection methodology on label prediction tasks of three different online user activity datasets with high-dimensional attributes: beer review history from BeerAdvocate, music listening history from Last.fm, and movie rating history from MovieLens.

Last.fm
Last.fm is a social network focused on music listening, logging and recommendation. Previous work collected the entirety of the social network and associated listening history, comparing the social network to alternative network models for music genre label prediction [15]. Sparse attribute vectors a i ∈ A correspond to counts of artist plays, where a non-zero element is the number of times user i has played a particular unique artist. Last.fm also has an explicit 'friendship' network declared by users. We treat this as another possible network model, denoted as E social , and evaluate it against others.
We evaluate the efficiency of node weight functions for the label classification task of predicting whether user 'i' is a listener of a particular genre. A user is a 'listener' of an artist if they have at least 5 plays of that artist. A user is a 'listener' of a genre if they are a listener of at least 5 artists in the top-1000 most tagged artists with that genre tag, provided by users. We select a subset of 8 of these genre labels (e.g. 'dub', 'country', 'piano'), chosen by the guidance of label informativeness from previous work [15].
Sparse non-zero attribute values correspond to a user's ratings of unique films. We select the most frequent usergenerated tag data thatcorresponds to a variety of mood, genre, or other criteria of user interest (e.g. 'inspirational', 'anime', 'based on a book'). We select 8 tags based on decreasing prevalence (i.e. 'horror', 'musical', 'Disney'), and predict whether a user is a 'viewer' of films of this tag (defined similarly to Last.fm listenership).

BeerAdvocate
BeerAdvocate is a website containing text reviews and numerical scores of beers by users. Each beer is associated with a category label (e.g. 'American Porter', 'Hefeweizen'). We select 8 categories according to the decreasing prevalence of the category label. We predict whether the user is a 'reviewer' of a certain category of beer (defined similarly to Last.fm listenership).

Experiment Set-up
When building KNN and TH networks, we construct both 'dense' and 'sparse' models, according to edge threshold ρ.
For Last.fm, we fix ρ = |E social | for the dense network, and ρ = 0.5 × |E social | for the sparse. For both BeerAdvocate and MovieLens, a network density of 0.01 represents a 'dense' network, and 0.0025 a 'sparse'. However, all of these networks are still 'sparse' by typical definitions.
User labels on all three datasets are binary (the user is a listener/reviewer of this genre/category), and sparse. Therefore, we use a label 'oracle' and present only positivelabel classification problems. This allows us to evaluate only distinguishing listeners etc. rather than learning null-label classifiers where label majority is always a good baseline. Table 2 (|L| columns) reports the count of non-zero labels over all 8 label-sets. This is the total number of nodes on which evaluation was performed. Each task predictor can be independently trained and evaluated, allowing us to scale arbitrarily. Following Brugere et al. [8], for each of the three datasets, we split data into temporally contiguous 'validation,' 'training,' and 'testing,' intervals of approximately 1/3 of each dataset. Training is on the middle third, validation is the interval prior, and testing on the latter interval. Model selection is performed on validation, and this model is evaluated on testing.
Below, we perform two primary empirical studies. First, we study network model selection in the presence of multiple tasks. We demonstrate that different network definitions and node weight functions are selected per task. Furthermore, jointly selecting for multiple tasks may not perform well for either. Second, we measure the efficiency of selected models and demonstrate that tasks can often be more parsimoniously represented by simpler, non-network representations.

Empirical analysis: Consistency and Multiple Tasks
We validate network models under varying hyperparameters on each dataset. We measure precision on both collective classification (CC) and link prediction (LP). For each network model (i.e. network representation, node weight method and associated hyperparameters), we rank models on the precision of the induced predictors over all nodes in validation and select the top-ranked model for evaluation in testing. To evaluate the robustness of model selection, we compare all selected network models on both validation and testing partitions to examine their full ranking.

Model Stability: Precision
Let p i denote the precision of the i-th model, p s as the precision of the selected model evaluated on the testing partition, p (1) as the precision of the 'best' model in test. Let µ be the mean precision over all models (|N | > 100) and µ (10) the mean precision over the top-10 models. Table 3 summarizes performance over different tasks and predictors. We report the mean precision of the top-10 ranked models (µ (10) ) vs. the precision of the top-ranked model (p (1) ), both evaluated in test.
The best model in validation need not be the best possible model in testing. Table 3 reports ∆p (1) = p s − p (1) , the difference in precision between the selected model s, and the best possible model, both evaluated in test (0 is best). We use bold to indicate significant values: precision in test. Finally, rank reports the percentile ranking of the selected model, as evaluated in test (1 is best). In Table 3, ∆p (1) and rank are both measures of model consistency. Selected models often approximate the best model in test, and have a high rank among other models. Selected models with high error to the best test model can have arbitrarily bad ranking in test (e.g. LP-RF in BeerAdvocate). Below, we look more closely at the selected model, as well as stability in deeper model rankings.  indicates the best models in both validation and testing are the same. The row below the rank indicates the selected network and node weight function. Bold indicates all selected models with rank ≥ 0.9, i.e. in the top 10% of models. Table 4 reports the normalized rank of the selected model, evaluated on test as reported in Table 3. We highlight models with high rank-consistency between validation and test: rank > 0.9, i.e. the selected model is in the top 10% of models in test. Table 4 shows several cases of high rank-inconsistency (e.g. BeerAdvocate LP-RF, MovieLens LP-RF) and high consistency for others (BeerAdvocate CC-RF, CC-SVM). These results are over many ranked network models (|N | > 100). In Last.fm, community weighting is selected for both CC methods. The Social-Community model is selected for CC-SVM. For BeerAdvocate on CC, local models are consistently selected and have a high rank in testing, even though SVM and RF methods have very different performance in absolute precision. This table demonstrates that the appropriate network model changes according to not only the dataset, but different tasks on the same dataset.  reports rank order correlation on the top-10 models. We report associated p-values. Bold indicates the models with p < 0.001 and intersection10 ≥ 5. Table 5 reports the Kendall's τ rank order statistic between the precision ranking of models, for validation and testing. τ = 1 indicates the rankings are identical. We report the associated p-value of the τ rank order statistic. For most CC tasks, model ranking is particularly consistent. Similarly, both tasks on Last.fm have high rank-correlation.

Model Stability: Rank Order
While this ranking shows remarkable consistency, it's not suitable when the result contains many bad models, which may be arbitrarily placed at low ranks. To handle this, we report intersection (10) , the shared models in the top-10 of validation and test. Since top-k lists may be short and have disjoint elements, we find the simple intersection rather than rank order. We highlight tasks in bold at a rank order significance level of p < 1.00E−03, and intersection (10) ≥ 5. Table 5 'Total' summarize the count of bold entries across  Tables 3, 4, and 5. This corresponds to scoring models on several consistency criteria: (1) precision (2) selected ranking, (3) rank correlation, and (4) top-10 rank intersection.
MovieLens under 'tag' labels reports a peculiar result. It performs very well at both µ (10) and p (1) for both SVM and RF. However, it has a high ∆p (1) and low intersection (10) . Looking closer at the results, two similar groups of local models perform well. However, in validation, this is under an adjacency local model, and the testing partition favors a wider BFS local model. However, both of these models are similar; this similarity isn't reflected in our ranking.

Consistency: Node Weight Functions
Our framework allows further investigation of weighting functions suitable for particular types of tasks, measured by their ranking. Figure 3 reports the counts of top-10 in validation and test, grouped by their weighting function, on CC (left) and LP (right) tasks. Each principal color represents a dataset, and shades denote different task predictors.
For CC, BeerAdvocate favors local task models, while Last.fm favors community and global models; both of these results agree with model selections in Table 4. Global weighting measures the extent that population-level models (e.g. unbiased random population sampling) are favored to any structured weighting. Looking closer at Last.fm, the ∆p (1) for the best-ranked Global model in test is only -0.01 for CC-SVM, and -0.05 for CC-RF. This indicates a weak network effect on Last.fm for CC under our evaluated models.
For each dataset, preferred models differ greatly by the task. LP on BeerAdvocate has an increased preference for activity weighting compared to CC. The preference for global weighting largely disappears for LP on Last.fm in favor of local models. This further demonstrates that we find representations better suited for different tasks, which change both by dataset and task. Fig. 4: Counts of network models and density associated with the top-10 ranked models in validation and test (20 total). Primary colors denote different datasets, shades denote different task methods. Figure 4 reports the counts of models according to underlying representation for the top-10 models in validation and test. The first three bar groups report a total of 20    For all tested datasets, there is not a strong preference for a particular network model or density for either CC or LP. However, this does not mean that precision is 'random' over varying network models. The τ rank order and intersection 10 are very consistent in several of these task instances (Table 5). Instead, node weight function preferences seem to drive the three datasets we examine, where the network representation will perform more similarly under the same weighting method than across different weighting methods.
We directly evaluate this hypothesis in Table 6. We report the median of pairwise differences of precision between model pairs, by matched/mismatched network representation or node weighting: median(p i − p j ) − median(p k − p l ), where (i, j) are all matched pairs grouped by the same network or weighting, and (k, l) all mismatched pairs. More negative values represent higher differences in precision on mismatches than matches, for that row's criteria. Mismatching node weight functions indeed account for more difference in precision than mismatching network representations.

Model Selection and Cross-Task Performance
We now aim to measure the performance of models across different tasks, and whether the same selected model tends to perform both tasks. Table 7 (Upper) reports model performance when model selection and evaluation are on matching/mismatching tasks. We do model selection on validation (for each task on the left) and report task performance in testing, on the task method given by the column. The ∆p (1) and rank are calculated as previously, where values on the diagonal are the same as in Tables 3 and  4, respectively. On the off-diagonal, the model is selected in validation on a different task than it is evaluated on in test. Table 7 (Lower) reports model performance by doing model selection on the average of CC and LP precision.
This result clearly demonstrates the main takeaway of this section: the 'best' network model depends on the subsequent task. The off-diagonal shows that in every case, models selected on the 'other' task perform very poorly. Consider the worst case for same-task selection-LP on MovieLensscored 0 on our 4 selection criteria (Table 5), yet this selected model performs 3x better in ∆p (1) than it's cross-task selected model. Over our three datasets, the average factor increase in ∆p (1) performance from model selection using same-task versus cross-task is ≈ 10x.
Perhaps we can simply do model selection jointly on both tasks. In Table 7 (Lower) we test this hypothesis by doing model selection on the average prevision between the two tasks. However, this strategy performs poorly in both tasks for BeerAdvocate and is dominated by the CC task in Last.fm and MovieLens. This closely matches the CC rows. In other words, by selecting a network model jointly on both tasks, we never select the suitable model for link prediction in any of the three datasets.

Empirical Analysis: Measuring Efficiency
In this evaluation, we evaluate our model selection with respect to our proposed efficiency measure. We look closely at the properties of this measure and similar stability in model ranking stable model ranking. We finally demonstrate model significance testing and sensitivity to noise.

Bootstrap and Rank Stability
We now test the stability of our choice of node weighting, over b = 20 re-sampled predictors. These replicates estimate the median of b > 100 distribution with low error (≤ 0.02), therefore we proceed with b = 20 for all results. Figure  5 (Left) reports the coefficient of variation (µ/σ) of the  encoding costs for the predictors in C r . These are smaller for the social-bfs model on Last.fm than for social-random. Figure 5 (Right) reports the signed difference in efficiency between models on the test and validation partition. The models with ∆efficiency > 0.004 (or an increase of 250 bytes/correct) are all bfs on MovieLens, which may be a legitimate change in efficiency, i.e. this is a poor performing set of models in test. This shows that our measurements are robust for estimating encoding cost at k, and efficiency is largely stable across partitions. We test the stability of E(W M ) and its correlation to correct predictions. Table 8 (Top) reports the Kendall's τ rank order statistic measuring correlation between the 'efficiency' ranking of models. This further shows stability in the models between validation and testing partitions. Table 8 (Bottom) in contrast reports the τ between the ranked models according to efficiency vs. correct predictions. Within the same partition. This rank correlation across measures is lower than the efficiency rank correlation across partitions. This means that efficiency is quite stable in absolute error and relative ranking, and efficiency ranking is not merely a surrogate for ranking by correct predictions. Otherwise, we would not need to encode the model cost at all.

Efficiency Features
Our definition of efficiency yields interpretable features that can characterize models and compare datasets. First, we compare the network and predictor encoding cost by calculating the ratio of the network encoding cost to total cost.
Second, recall that in the efficiency definition, we select the most efficient κ i per node i, with κ i ≤ 150 in our evaluation. This gives the model the flexibility to explore wider in the network for each i. Nodes with higher κ i are likely harder to classify because the predictor encoding is typically more expensive when training over more attributevector instances. Figure 6 compares the ratio of network and total encoding costs (x-axis) vs. the mean over all κ i (y-axis). The models roughly order left-to-right on the x-axis according to Table 1.
All non-network models (activity-top, degree-top, cluster, random) are consistently inexpensive vs. their predictor encoding cost, but several also select a higher κ i . In contrast, the degree-net and activity-net models are consistently costlier because they encode a fixed m > max(k) in order to sample at each value k. All ordered weighting methods (network and non-network) tend to be most efficient at a lower κ i . This may indicate these ordered nodes are more informative per instance, and each additional instance is more costly to incorporate into predictors, so our model selection will favor minimizing κ.

Model Selection: Efficiency
We now focus on selecting models from the efficiency ranking in validation. We've already shown that there is high stability in the efficiency ranking between validation and test, but less correlation between correct predictions and efficiency (Table 8). Therefore, in this evaluation, we see whether we can recover the best model in test (W best ) with respect to correct predictions, using efficiency selection criteria.
The left-most column of Table 9 shows the three topranked models (W select ) by efficiency in validation. The ratios report the relative performance of the selected model (evaluated in test) for efficiency, total encoding size, and correct predictions. The second column-efficiency ratio-is not monotonically decreasing, because model ranking by efficiency may be different in test than validation ( Table 8).
The selection by efficiency shows an intuitive tradeoff between encoding cost and predictive performance. In Last.fm, the social-bfs model performs best, but the inexpensive social-cluster model is an alternative. This is consistent with previous results which show social-bfs is much more predictive than network adjacency, and of other underlying network models [15].
According to performance ratios, activity-net is extremely preferred in MovieLens and BeerAdvocate. This measures the extent that the most active users are also most informative in terms of efficiency in these two domains. This is a striking result. Simply, within both domains, one only needs to do a weighted sampling of users by activity, which performs better than group-wise or pairwise models.
MovieLens correctly selects activity-top, and activity-net is an order of magnitude costlier while maintaining similar correct predictions. On BeerAdvocate, activity-net performs best on correct predictions, but activity-top is the better model since it preserves 0.86 of correct predictions but is 0.01 the encoding cost. This demonstrates that efficiency is preferred when the application favors a parsimonious model. Figure 7 reports models ranked by efficiency (Left) total encoding cost (Middle), and correct predictions (Right). The Last.fm ranking has more models because social is included. Figure 7 (Middle) shows that each dataset grows similarly over our set of models, but that each has a different baseline of encoding cost. Last.fm is particularly costly; the median non-zero attributes per node (e.g. artists listened) is 578, or 7 times larger than MovieLens. These larger attribute vectors yield more expensive predictor encoding, requiring more bytes for the same correct predictions. These baselines also yield the same dataset ordering in efficiency. So, the worst model on MovieLens (random, 1084 bytes/correct) is more efficient than the best model on Last.fm (social-bfs, 1132 bytes/correct). Figure 7(Right) shows the extent that the first two ranked models (activity-net and activity-top) dominate the correct predictions on BeerAdvocate and MovieLens.

Model Significance
In order to compare all models for a dataset, we measure the significance of each model relative to the efficiency over the complete set of models.
Let W r be a model we intend to measure. We compare the median difference of efficiency of W r to all other models against the median pairwise difference of all models excluding W r , normalized by the inter-quartile range (IQR) of pairwise difference. This measure is a non-parametric analog to the z-score, where the median differences deviate from the pairwise expectation by at least a 'λ' factor of IQR.
Let e i = E(W i ), the efficiency value for an arbitrary model W i , and λ a significance level threshold, then for i = 1...|F |, j = 1...|F |; i, j = r: significance(F, r, λ) = medi(|er − ei|) − medi,j(|ei − ej|) iqr i,j (|ei − ej|) ≥ λ (8) This is a signed test favoring a larger efficiency of W r than the expectation. The median estimates of the e r comparisons and pairwise comparisons are also robust to a small number of other significant models, and like the z-score, this test scales with the dispersion of the pairwise differences. This test only assumes 'significant' models are an outlier class in all evaluated models S. This is a reasonable assumption because if many models efficiently represent the data, it may be a trivial application: use any network definition.

Model Robustness to Noise
For each of the significant models, we measure the impact of noise on its efficiency and significance. We apply node rewiring on the model we are testing, and leave all other models intact. For each neighbor of node i, we rewire i to a random node at probability p. This is out-degree-preserving randomization, which is appropriate because outgoing edges determine the input for the predictor on i. Sorting heuristics activity-net and degree-net are implemented as adhoc networks, where each node i has directed edges to some m-sized subset of top-ranked nodes. Rewiring is done in the same manner on these networks, again to any node in V . Figure 8 shows the effect of varying noise p (x-axis), on the efficiency (Left), and significance (Right) of each significant model. activity-net on both MovieLens and BeerAdvocate quickly lose efficiency under even small noise, and are no longer significant for λ = 1 at p = 0.025, and p = 0.10, respectively. activity-top is more robust, remaining significant to p = 0.225.
activity-net is particularly sensitive to noise due to decreased performance in both encoding cost and correct predictions. At only p = 0.025, correct predictions on activity-net on BeerAdvocate reduce by 15% and encoding cost increases by 31%. The encoding cost greatly increases because the cardinality of the set of unique nodes in the activity-net representation is small with many repetitions in the sequence of destination nodes. When random nodes are added in the representation, they are near-unique node IDs, greatly increasing the set cardinality and reducing the compression ratio. activity-top shows a similar increase, proportional to nodes rather than edges.
Finally, social-bfs is easily the most robust to noise. From a lower baseline, it remains significant to p = 0.15. It loses only 35% of its significance value at any noise level, while all other methods lose > 90%. This demonstrates that network models have robustness which might be desirable for further criteria in model selection. For example, our full methodology can be used to select for efficiency with significance at some noise level p.

Conclusions and Future Work
In this work, we have formulated a methodology for network model selection from raw data with a focus on task performance to represent the behavior of the underlying system. Using this methodology, we demonstrate two key points. First, different networks represent different tasks, and often no one network represents multiple tasks. Second, we often find that a task is more efficiently represented by a non-network structure such as groups or exemplars. Both of these takeaways reinforce a larger point: often there is not "the network" representation, but various possible representations of varying utility.
Recent work in graph neural networks (GNNs) [36] makes these challenges of network definition even more difficult. In this case, the downstream model is highly parameterized and costly to train. Biases in different representations may be prohibitively costly to measure over this added complexity. There is a great need for efficient end-to-end GNN models which learn implicit network structure from raw data. Furthermore, training such models over alternative, simpler representations from raw data may encourage parameterefficient models which haven't been a particular focus of this area.