PaperlayerView exact revision on arXiv

Source-linked AI summary

About the Influence of Workflow Topology on Task Intensity Prediction through Graph Learning

Max Otto, Haci Ismail Aslan, Joel Witzke, Jonathan Bader, Odej Kao

arXiv:2609.39481v1cs.DCcs.LG

TL;DR

Task-level resource prediction for cloud workflows matters because over-provisioning increases cost and under-provisioning can risk service degradation or bottlenecks. This paper benchmarks handcrafted topological features and graph-learning models for predicting CPU and memory intensity. Graph-learning models mostly outperform the MLP, and adding topology-based features can further improve their performance.

  • Problem

    The relationship between workflow topology and task intensity remains underexplored, despite the importance of accurate task-level resource estimates in settings where over-provisioning increases costs and under-provisioning risks service degradation or bottlenecks.

    Source: §I · p. 1

  • Method

    The paper evaluates graph-learning models and handcrafted topology features for task-intensity prediction, including a DAGTransformer-plus-XGBoost pipeline trained on seven-task graphs and tested on larger workflows.

    Source: §V · p. 4, §VII · p. 8

  • Results

    Graph-learning models mostly outperformed the MLP, topology-based features could slightly improve graph-learning predictions, and the DAGTransformer–XGBoost pipeline generalized from seven-task training graphs to 18- and 20-task workflows.

    Source: §VII · pp. 7–8

  • Takeaways & Limitations

    It can be advantageous to add different aspects of workflow graph structure to task CPU and memory prediction inputs, even when a model already captures some graph information.

    Source: §VII · p. 8

Abstract

from arXiv · show

Efficient resource provisioning for large-scale workflows on cloud infrastructures is a critical performance engineering challenge. These workflows are often structured as directed acyclic graphs (DAGs), where under-provisioning can cause critical bottlenecks and over-provisioning leads to unnecessary costs. Accurate, task-level prediction of resource intensity (e.g., CPU load and memory usage) is essential for mitigating these issues. While task-level features are commonly used for prediction, the performance impact of the workflow's overall topological structure is often overlooked or assumed. The central question of our work is: To what extent does what part of the DAG topology influence task-level resource intensity, and what is the most effective way to model this influence? This paper presents a comprehensive benchmark to systematically quantify the impact of graph topology on task intensity prediction. We evaluate and compare a spectrum of modeling approaches. Our findings demonstrate that topology is a critical feature for accurate prediction. Models incorporating important topological information, even through simple handcrafted features, significantly outperform baseline models. We show that graph-native models provide the highest accuracy, achieving low mean absolute errors for both CPU and memory predictions, and can still be combined with simple topological features that they do not learn for better performance.

I. INTRODUCTION

The paper examines how workflow topology relates to task-level resource intensity, addressing an underexplored connection in predictive modeling. It compares handcrafted topological features and graph-learning approaches, including tests of generalization to larger workflows.

I. INTRODUCTION

  • Workflows are modeled as DAGs whose task nodes and dependency edges encode execution order and often reflect data or control flows.Source: §I · p. 1
  • Over-provisioning wastes infrastructure and increases cost, while under-provisioning risks service degradation, bottlenecks, or task failures.Task demands can also vary over time, with peaks and anomalies that historical averages may miss.Source: §I · p. 1

II. RELATED WORK

  • Although prior work studies resource forecasting and graph-based workflow models, the relationship between workflow topology and task intensity remains underexplored.Prior graph studies report that graph structure can improve transformer results, and that task-performance predictions vary with workflow position.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • The paper compares MLP predictions using measured task features with and without handcrafted topology, then evaluates graph-learning models with and without those features.Source: §I · p. 1
  • A DAGTransformer trained on small workflows is paired with a regressor to test task-intensity prediction on larger workflows, with and without topological features.Source: §I · pp. 1–2

III. METHODS

The methods section introduces the deep-learning models used to predict task intensities. It contrasts a basic MLP baseline with graph-oriented models that use graph data directly.

A. About the Applied Deep Learning Models

1) Multi Layer Perceptron (MLP):

2) Graph Convolutional Networks (GCN):

3) Graph Attention Networks (GATs):

This methods section describes several graph-learning models and an ensemble for workflow task prediction. Their approaches include neighborhood attention, iterative aggregation, graph-position encoding, and specialized aggregation for heterophilic graphs.

3) Graph Attention Networks (GATs):

4) Graph Isomorphism Networks (GINs):

5) GraphSAGE:

  • GraphSAGE iteratively aggregates neighbor features across increasing k-hop neighborhoods, capturing local and higher-order graph structure.Source: 5) GraphSAGE · p. 2

6) DAGTransformer:

  • DAGTransformer uses task positions as positional encoding and neighboring tasks as an attention mask for GNN-like aggregation.Source: 6) DAGTransformer · p. 2

7) H2GCN:

  • H2GCN uses specialized aggregation and embedding strategies to address heterophilic graphs, where neighboring nodes often have dissimilar labels.Source: 7) H2GCN · p. 2

8) Ensemble Models:

9) XGBoost:

The section describes XGBoost regression and node-level features for representing workflow topology. These features encode task positions, connections, centrality, and local or broader structural patterns.

9) XGBoost:

  • XGBoost uses boosted trees to handle nonlinearity and serves as the downstream regressor for penultimate-layer embeddings from pretrained classification networks.Source: 9) XGBoost · p. 2

B. Utilized Topological Features

1) Node-Based Features:

  • DAG in & out represents a task’s incoming and outgoing edges in a normalized adjacency-matrix feature vector, with an additional node-ID value.For a seven-task workflow, the vector has 15 dimensions: seven incoming-edge values, seven outgoing-edge values, and one node-ID value.Source: 1) Node-Based Features · p. 3
  • The node-based features also include degree, three centralities, clustering coefficient, Node2Vec embeddings, Weisfeiler-Lehman colors, and graphlet occurrence counts.Graphlets count occurrences of the target task in patterns containing up to three task nodes: edges, paths, and triangles.Source: 1) Node-Based Features · p. 3

2) Katz Index:

The section defines node- and graph-level Katz features and describes the metrics used to evaluate classification and regression models.

2) Katz Index:

  • The Katz index measures a node’s influence through direct and indirect graph connections, with the aggregated influence vector usable as a node feature and its entries aggregated for a graph-level index.Source: 2) Katz Index · p. 3

C. Evaluation Metrics

  • Classification performance is evaluated mainly with accuracy, while regression uses Mean Absolute Error and R-squared.R-squared ranges from 0 for predicting the average to 1 for a perfect fit.Source: C. Evaluation Metrics · p. 3

D. Alibaba Cluster-Trace-V2018 Dataset

The experiments use Alibaba workflows to test whether task-level or whole-workflow topology improves MLP task-intensity prediction. They report benefits from topological features, especially when features from all workflow tasks are included alongside measured features.

D. Alibaba Cluster-Trace-V2018 Dataset

IV. DETERMINING TOPOLOGICAL FEATURE IMPORTANCES WITH MLP

  • The first experiment uses only structural features of the predicted task, whereas the second includes earlier tasks’ measured intensities and topological features alongside the target’s topology.Source: §IV · p. 4
  • In the first experiment, Weisfeiler-Lehman features, Katz indices, centralities, and path lengths significantly improve CPU prediction; farther-task path lengths outperform nearer ones.Source: §IV · p. 4
  • Node degrees, clustering coefficients, and graphlets perform similarly, while combining all structure features raises memory accuracy by almost 4% from the 90.98% path-length baseline.Source: §IV · p. 4
  • Including all tasks’ topological features improves MLP accuracy with measured features; the DAG in&out sparse matrix is most dominant, and combining all topological features is surpassed only by it.Source: §IV · p. 4

V. GRAPH DEEP LEARNING ON WORKFLOWS

The graph-learning benchmark finds that structural features slightly improve almost all geometric deep-learning models, while a GNN ensemble is the exception. GAT, GIN, DAGTransformer, and the ensemble outperform the MLP baseline even without added structural features.

V. GRAPH DEEP LEARNING ON WORKFLOWS

  • Structural features slightly improve almost all geometric deep-learning models, allowing GCN and partly H2GCN to exceed MLP; the GNN ensemble is the exception.The comparison covers CPU and memory prediction accuracies with and without topology features.Source: Table III · p. 5, Table IV · p. 6, Table V · p. 6
  • GAT, GIN, DAGTransformer, and the GNN ensemble outperform the MLP with all nodes’ topological information, even without added structural features.GCN, GraphSAGE, and H2GCN perform slightly worse than that MLP comparison.Source: §V · p. 5
  • GIN’s strong performance suggests workflow isomorphism matters, with the dataset’s exclusively 7-task workflows likely repeating structural patterns.The paper links the pattern to the dataset’s uniform workflow size and frequent isomorphic graphs.Source: §V · pp. 5–6
  • GAT’s attention learns task-neighbor weights; task centralities and the Katz index, which improved MLP accuracy, are possible patterns behind its performance.Source: §V · p. 6
  • GraphSAGE performs less well alone but enhances GNN ensembles, possibly because its aggregation strategy adds complementary features.Source: §V · p. 6
  • Other GNNs outperform H2GCN on this dataset, suggesting workflow heterophily is not very problematic here.H2GCN was designed to address graphs with strong heterophilic properties.Source: §V · p. 6
  • DAGTransformer performs very well despite the authors’ inability to reproduce its claimed accuracies; the dataset also appeared in its original paper.The authors suggest its differentiated attention to neighboring nodes may learn patterns similar to GAT.Source: §V · p. 6

VI. TRANSFERABILITY OF EMBEDDINGS: REGRESSING THE ACTUAL CPU & MEMORY UTILIZATION

The paper motivates regression and transfer of learned graph representations as alternatives for predicting actual resource use across workflow sizes. It proposes applying a pretrained model’s penultimate-layer embeddings to new graph sizes and training a small regressor.

VI. TRANSFERABILITY OF EMBEDDINGS: REGRESSING THE ACTUAL CPU & MEMORY UTILIZATION

  • Real applications may require predictions across workflow sizes and exact resource values, making regression more applicable than classification.Source: §VI · p. 6
  • Training a large graph-learning model separately for each workflow size would be computationally inefficient.Source: §VI · p. 6
  • The proposed alternative is to infer a pretrained model’s penultimate-layer embeddings on new graph sizes and train a small regressor on them to transfer model information.The embeddings contain aggregated structure information if they generalize.Source: §VI · p. 6

A. The Regression Experiment

The regression experiment tests transfer to 18th- and 20th-task predictions using measured resource data. It compares XGBoost regressors trained on DAGTransformer embeddings alone and embeddings augmented with topological features.

A. The Regression Experiment

  • The experiment uses Alibaba Cluster-Trace-V2018 data for 18th and 20th tasks, with measured values as ground truth rather than clustered class labels.Source: A. The Regression Experiment · pp. 6–7
  • Because it was the best-performing model benefiting from topological features in classification benchmarks, pretrained DAGTransformer embeddings train an XGBoost regressor to predict CPU and memory usage for tasks 18 and 20.Source: A. The Regression Experiment · p. 7
  • The experiment compares CPU and memory regression using embeddings alone against embeddings augmented with topological features.The added features are computed for the predicted tasks and concatenated with the embeddings.Source: A. The Regression Experiment · p. 7

B. Results of the XGBoost Model on Penultimate Layers

Penultimate-layer embeddings support XGBoost prediction of task-level CPU and memory utilization on larger workflows, though predictions are weaker for most maximum-CPU cases. Adding explicit topological features improves performance, and errors are often concentrated among unusually high values.

B. Results of the XGBoost Model on Penultimate Layers

VII. CONCLUSION

The conclusion finds that workflow topology contains learnable patterns relevant to task intensity, and that including structural features can benefit prediction. Graph-learning models mostly outperform the MLP, generalize from 7-task to larger workflows, and can benefit further from added topological features.

VII. CONCLUSION

  • The results indicate learnable patterns connect multiple aspects of workflow topology and task intensity.The paper reports that combining different task and workflow topology features can help simple models achieve high accuracy.Source: §VII · p. 7
  • Graph-learning models mostly outperformed the MLP, while explicit topology-based features could still slightly improve graph-learning performance.The conclusion also reports that topology features can be advantageous even when a model already collects graph information.Source: §VII · pp. 7–8
  • Graph-learning models are effective for predicting future-task CPU and memory usage, but may not capture every useful aspect of topology.The conclusion therefore notes that topology-based features can slightly improve their performance.Source: §VII · p. 7
  • A DAGTransformer trained on 7-task graphs generalized to 18- and 20-task workflows, with additional topological inputs further enhancing MAEs.The conclusion describes a pipeline combining the DAGTransformer backbone with an XGBoost regressor.Source: §VII · p. 8
  • Adding varied aspects of workflow graph structure to model inputs can be advantageous for predicting task CPU and memory needs, even when models already collect graph information.Source: §VII · p. 8

Related papers

Loading 2609.39481v1…