Dual Averaging Method for Online Graph-structured Sparsity

Baojian Zhou, Feng Chen, Yiming Ying

TL;DR

GraphDA is the first online learning algorithm designed to handle complex, graph-structured sparsity constraints in streaming data. By projecting both gradients and model variables onto graph-based subspaces, it successfully captures latent structures (like connected subgraphs) that standard sparsity methods (like the $L_1$ norm) ignore, leading to better accuracy and much higher interpretability.

What Problem Does This Paper Address?

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.

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

Methods

The authors propose GraphDA (Graph Dual Averaging). The algorithm is built on the foundation of Nesterov’s Dual Averaging, which keeps track of the "running average" of gradients (the dual variables) to make updates more robust to noise.

The key innovation lies in how GraphDA handles the graph constraint. Instead of a simple thresholding step, it uses two approximated projections:

  • Head Projection: Applied to the accumulated gradient (dual space). It identifies a subgraph that captures the most "significant" gradient information.
  • Tail Projection: Applied to the primal variables. It ensures the resulting model strictly obeys the graph-structured sparsity constraint (e.g., the non-zero weights must form a forest or a set of connected components within a certain budget).

By using these two approximations (originally developed for batch settings), the authors turn an NP-hard optimization problem into one that can be solved 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 in the graph.

Datasets

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: The classic handwritten digits dataset, where pixels are treated as nodes in a grid graph.
  3. KEGG Pathway Dataset: A real-world protein-protein interaction network used to detect genes related to endometrial cancer (HSA05213 pathway).

Key Insights and Ideas

  • Dual Space Filtering: A major "aha" moment is that projecting the accumulated gradient is just as important as projecting the model weights. This helps the algorithm ignore "noisy" feature updates that don't fit the graph structure early on.
  • Beyond "Salt and Pepper" Sparsity: Standard sparse methods like $L_1$-RDA often produce "salt and pepper" noise—random isolated features that happen to correlate with the target. GraphDA enforces "coherence," ensuring that if a feature is selected, its neighbors in the graph are more likely to be considered too.
  • Efficiency: Despite the complexity of graph constraints, the algorithm remains practical for large-scale data because it uses nearly linear-time approximations for the Steiner Tree problems underlying the projections.

Key Results

  • 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).
  • Dramatic Interpretability Gains: The most striking results are qualitative. In the KEGG pathway experiments, GraphDA recovered the actual gene pathway with much higher precision (fewer "blue" false-positive nodes) than any other method.
  • Robustness to Sparsity: GraphDA's error rate reaches its minimum exactly when the sparsity parameter matches the true number of nodes in the underlying graph structure, showing it "understands" the model complexity.

Limitations and Future Work

  • Theoretical Regret Bounds: While the algorithm performs excellently in practice, the authors note that proving a sublinear "regret bound" (a guarantee on how much the online learner loses compared to an ideal batch learner) is difficult because the graph constraints are non-convex. This remains an open theoretical challenge.
  • Convex Objective Assumption: The current framework assumes the loss function (like logistic or square loss) is convex. Extending this to deep learning (non-convex losses) with graph constraints would be a natural next step.
  • Dynamic Graphs: The paper assumes a static graph structure. In some applications, the graph itself might change over time, which the current version of GraphDA does not address.

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 GraphDA. The key part in 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, 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, 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},
}

Loading related content...

Figure