Dual Averaging Method for Online Graph-structured Sparsity

Baojian Zhou, Feng Chen, Yiming Ying

Abstract

Online learning algorithms update models via one sample per iteration, making them efficient for large-scale datasets and real-time detection of events like disease outbreaks or traffic congestion. However, existing graph-structured models often focus on offline settings or specific loss functions, while standard online methods struggle with complex, non-convex graph-structured sparsity. This paper introduces GraphDA, the first online learning algorithm designed for graph-structure constrained optimization problems. GraphDA projects both averaging gradients and primal variables onto lower-dimensional subspaces to effectively capture graph-structured features. Experiments on benchmark and real-world datasets demonstrate that GraphDA improves classification performance and provides superior interpretability by successfully identifying structured features.

Introduction: The Challenge of Structured Sparsity

In many real-world scenarios—such as tracking disease outbreaks, monitoring social media events, or analyzing gene networks—data arrives sequentially (online), and the underlying features are known to be "sparse" but structured. For example, a virus spreads through a physical or social graph; the affected nodes aren't just random points, they form a connected subgraph.

Existing solutions face a "pick two" dilemma:

  1. Online Learning: Efficiently process one sample at a time but usually rely on simple $L_1$ (Lasso) or $L_2$ norms that treat features as independent.
  2. Graph-structured Sparsity: Capture complex patterns (trees, clusters) but are typically "batch" algorithms that require the entire dataset at once.
  3. Convexity: Most graph-structured constraints are mathematically non-convex and NP-hard to solve exactly.
Illustration of valid (left) and invalid (middle, right) graph-structured sparsity patterns. The algorithm enforces connectivity constraints.

The authors bridge this gap by introducing an algorithm that handles non-convex graph constraints in a streaming, online environment.

Methodology: Graph Dual Averaging (GraphDA)

GraphDA is built on the foundation of Nesterov’s Dual Averaging, which tracks the "running average" of gradients (dual variables) to ensure updates are robust to noise. The key innovation lies in how GraphDA handles the graph constraint through two approximated projections:

  • Head Projection: Applied to the accumulated gradient in the dual space. It identifies a subgraph capturing the most significant gradient information, effectively filtering noise early.
  • Tail Projection: Applied to the primal variables. It ensures the model strictly obeys the graph-structured sparsity constraint (e.g., non-zero weights must form a forest or a set of connected components).

By using these approximations, the authors turn an NP-hard optimization problem into one solvable in nearly linear time per iteration: $O(p + |E| \log^3 p)$, where $p$ is the number of features and $|E|$ is the number of edges.

Experimental Evaluation

The authors evaluated GraphDA against eight baseline methods (including AdaGrad, Adam, and $L_1$-RDA) across three types of data:

  1. Benchmark Graph Dataset: Four synthetic subgraphs (shapes like a cross or a spiral) embedded in a 33x33 grid.
  2. MNIST Dataset: Handwritten digits where pixels are nodes in a grid graph.
  3. KEGG Pathway Dataset: A real-world protein-protein interaction network used to detect genes related to endometrial cancer.
Synthetic benchmark graph patterns (Graph01 to Graph04) used to test the algorithm's ability to recover structured features.

Key Results and Insights

  • Superior Accuracy: On the Benchmark dataset, GraphDA achieved the highest classification accuracy (0.749) and AUC, significantly outperforming $L_1$-RDA (0.694) and AdaGrad (0.696).
  • Interpretability: Unlike standard sparse methods that produce "salt and pepper" noise (isolated features), GraphDA enforces coherence. In KEGG pathway experiments, it recovered actual gene pathways with much higher precision.
  • Efficiency and Robustness: The algorithm remains practical for large-scale data and its error rate reaches a minimum when the sparsity parameter matches the true underlying structure.

Conclusion and Future Work

GraphDA is the first online learning algorithm for graph-structure constrained optimization. While it performs excellently in practice, proving sublinear regret bounds for these non-convex constraints remains a theoretical challenge. Future work may involve extending the framework to non-convex loss functions (like deep learning) or dynamic graphs where the structure evolves over time.

Summary updated

Abstract

Online learning algorithms update models via one sample per iteration, thus efficient to process large-scale datasets and useful to detect malicious events for social benefits, such as disease outbreak and traffic congestion on the fly. However, existing algorithms for graph-structured models focused on the offline setting and the least square loss, incapable for online setting, while methods designed for online setting cannot be directly applied to the problem of complex (usually non-convex) graph-structured sparsity model. To address these limitations, in this paper we propose a new algorithm for graph-structured sparsity constraint problems under online setting, which we call \textsc{GraphDA}. The key part in \textsc{GraphDA} is to project both averaging gradient (in dual space) and primal variables (in primal space) onto lower dimensional subspaces, thus capturing the graph-structured sparsity effectively. Furthermore, the objective functions assumed here are generally convex so as to handle different losses for online learning settings. To the best of our knowledge, \textsc{GraphDA} is the first online learning algorithm for graph-structure constrained optimization problems. To validate our method, we conduct extensive experiments on both benchmark graph and real-world graph datasets. Our experiment results show that, compared to other baseline methods, \textsc{GraphDA} not only improves classification performance, but also successfully captures graph-structured features more effectively, hence stronger interpretability.
BibTeX
@inproceedings{zhou2019dual,
  author = {Baojian Zhou and Feng Chen and Yiming Ying},
  title = {{Dual Averaging Method for Online Graph-structured Sparsity}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  url = {https://openreview.net/forum?id=wS8pBzRGamLW},
}
Figure