PaperlayerView exact revision on arXiv

Source-linked AI summary

End to end learning and optimization on graphs

Bryan Wilder, Eric Ewing, Bistra Dilkina, Milind Tambe

arXiv:1905.13732v3cs.LGcs.SIstat.ML

TL;DR

Graph decisions often depend on partially observed inputs, but standard prediction losses may not align with the downstream optimization objective. The paper learns a mapping to a differentiable clustering proxy, and reports that its system improves over both two-stage and pure end-to-end approaches. Its approximation is supported under conditions including balanced, well-separated clusters.

  • Problem

    Graph-optimization decisions may rely on partially observed graphs, and predictions trained with standard losses can be suboptimal for the downstream decision.

    Source: §1 · p. 1

  • Method

    The system learns a representation mapping graph-optimization problems to a simpler differentiable proxy, instantiated as k-means clustering for partitioning and subset-selection tasks.

    Source: §1 · p. 2

  • Results

    The authors report improvements over both two-stage approaches and purely end-to-end approaches, with CLUSTERNET outperforming baselines in nearly all combined link-prediction and optimization cases.

    Source: §1 · p. 2, §5.1 · p. 8, §6 · p. 9

  • Takeaways & Limitations

    Clustering is presented as sufficient for many graph-optimization problems, though not as the right algorithmic structure for all tasks.

    Source: §1 · p. 2

    The diagonal approximation is justified for relatively balanced, well-separated clusters, and is most suitable when assignments are firm.

    Source: §4.2 · p. 5

Abstract

from arXiv · show

Real-world applications often combine learning and optimization problems on graphs. For instance, our objective may be to cluster the graph in order to detect meaningful communities (or solve other common graph optimization problems such as facility location, maxcut, and so on). However, graphs or related attributes are often only partially observed, introducing learning problems such as link prediction which must be solved prior to optimization. Standard approaches treat learning and optimization entirely separately, while recent machine learning work aims to predict the optimal solution directly from the inputs. Here, we propose an alternative decision-focused learning approach that integrates a differentiable proxy for common graph optimization problems as a layer in learned systems. The main idea is to learn a representation that maps the original optimization problem onto a simpler proxy problem that can be efficiently differentiated through. Experimental results show that our ClusterNet system outperforms both pure end-to-end approaches (that directly predict the optimal solution) and standard approaches that entirely separate learning and optimization. Code for our system is available at https://github.com/bwilder0/clusternet.

1 Introduction

The introduction frames graph optimization with partial observations as a coupled learning-and-decision problem: standard prediction losses may not yield decisions suited to the downstream objective. It proposes a learned reduction to a differentiable proxy and reports improvements over both separated learning-and-optimization and direct-prediction approaches.

1 Introduction

  • Graph applications often have unobserved edges or partially known node attributes, while link-prediction methods are generally developed separately from downstream optimization.A model optimized for a standard loss such as cross-entropy may be suboptimal for the decision task, particularly when the model is imperfect.Source: §1 · p. 1
  • Pure end-to-end approaches can require substantial data and must discover algorithmic structure, while decision-focused learning embeds an optimization solver but requires problem-specific differentiable solvers.Such systems may also need to call a quadratic-programming solver on every forward pass.Source: §1 · p. 2
  • The proposed framework embeds a solver for a simpler optimization problem as a differentiable layer and learns a representation mapping the harder problem onto it.This shifts emphasis toward representation learning and away from learning an entire algorithm from scratch.Source: §1 · p. 2
  • The framework instantiates its proxy as differentiable k-means for graph partitioning and selecting subsets of K nodes.The authors state that clustering is sufficient for many problems, but not necessarily the right algorithmic structure for every task.Source: §1 · p. 2
  • Experiments improve over both two-stage baselines and alternate end-to-end approaches on a range of example domains.The framework combines graph learning with a simpler continuous-space proxy for a more complex discrete problem and differentiates through its clustering layer.Source: §1 · p. 2

2 Related work

The related work distinguishes this approach from decision-focused methods that differentiate through the target solver, generic neural approaches to combinatorial optimization, and neural clustering work. Its distinguishing choice is to fine-tune a generic algorithmic skeleton for difficult graph optimization problems.

2 Related work

  • For highly combinatorial problems, the method uses a generic algorithmic skeleton that is automatically fine-tuned to the task rather than a solver for the exact problem or a close relaxation.The cited prior decision-focused work mostly addresses convex problems or discrete problems with near-lossless convex relations.Source: §2 · p. 2
  • Unlike prior neural combinatorial-optimization approaches, the model uses a differentiable k-means layer and a differentiable objective approximation instead of generic layers and policy-gradient training.The differentiable final decision avoids the non-differentiable selection steps used in some prior approaches.Source: §2 · p. 2
  • The paper addresses graph optimization rather than Euclidean clustering or perceptual grouping, using k-means in graph-embedding space to solve an optimization problem.The cited related clustering work does not include an explicit clustering algorithm in the network for this graph-optimization goal.Source: §2 · p. 3

3 Setting

The setting combines partial graph observation with a decision objective defined on the full graph. It contrasts prediction followed by optimization and direct decision prediction with an alternative that embeds algorithmic structure in the learned model.

3 Setting

  • The task begins with a partially observed graph and seeks a feasible decision maximizing an objective defined on the full graph.Link prediction from observed training edges is the formal example, while the framework is also described as applying to other graph-learning problems.Source: §3 · p. 3
  • A standard two-stage approach reconstructs the graph from observed edges with a predictive loss, then optimizes the decision using that reconstructed graph.In the inductive setting, training graphs provide examples for predicting edges in a partially observed graph from the same distribution.Source: §3 · p. 3
  • Direct end-to-end models map observed edges to a feasible decision and train on decision quality, while the proposed alternative embeds algorithmic structure in the learned model.Direct prediction can force the model to rediscover algorithmic concepts; two-stage methods can instead exploit sophisticated optimization methods.Source: §3 · p. 3

4 Approach: CLUSTERNET

CLUSTERNET pairs graph embeddings with a differentiable k-means layer, using learned clusterings as a useful inductive bias for graph optimization rather than claiming an exact reduction. Its forward and backward passes support differentiable training, with separate interpretations for partitioning and subset-selection problems.

4 Approach: CLUSTERNET

  • CLUSTERNET combines graph embeddings with differentiable k-means, treating cluster assignments as soft solutions that provide an inductive bias for graph optimization.The authors do not claim that the target problems are exactly reducible to k-means.Source: §4 · p. 4

4.1 Forward pass

  • Soft assignments weight nodes by distance to cluster centers, and iterative center updates produce a fixed-point output of centers and assignments.The inverse-temperature parameter controls assignment hardness; as it approaches infinity, assignments recover standard k-means assignments.Source: §4.1 · p. 4

4.2 Backward pass

  • The approximate backward pass differentiates a final forward update rather than the full update history, making its runtime independent of the iterations needed for convergence.This also permits nondifferentiable methods to find the forward-pass fixed point; the diagonal approximation is justified when clusters are relatively balanced and well-separated.Source: §4.2 · p. 5

4.3 Obtaining solutions to the optimization problem

  • For partitioning, CLUSTERNET trains against the expected decision loss of random assignments sampled from soft cluster probabilities, then uses hard maximum assignments at test time.The expected loss is closed-form for many problems; repeated sampling with a policy-gradient estimator is an alternative when it is not.Source: §4.3 · pp. 5–6
  • For subset selection, cluster centers allocate probability to nearby nodes, yielding a budget-constrained soft solution that is trained through expected loss and rounded to a feasible discrete set.At test time, pipage rounding produces feasible solutions; the authors also note that domain-specific rounding methods can be used.Source: §4.3 · p. 6

5 Experimental results

The experiments test graph optimization with partially observed edges and on complete graphs, then assess whether learned strategies transfer to unseen graphs. CLUSTERNET combines link prediction with optimization and is compared with two-stage, train-only, end-to-end, and expert-designed baselines.

5 Experimental results

  • The evaluation holds out 60% of edges for link prediction, evaluates community modularity and minmax facility location, and compares learned systems with optimization baselines.Datasets include Cora, Citeseer, Protein, Adol, and FB; facility-location evaluation uses each graph's largest connected component.Source: §5 · p. 7

5.1 Results on single graphs

  • CLUSTERNET outperforms baselines in nearly all combined link-prediction and optimization cases, often substantially; the two-stage approach sometimes falls below train-only optimization.The experiments use K = 5 clusters, with K = 10 reported as similar in the appendix.Source: §5.1 · p. 8
  • On complete-graph optimization, CLUSTERNET is competitive with or exceeds expert-designed methods, with over 3x improvement for community detection on some datasets.For facility location it at least ties the baselines, while GCN-e2e typically underperforms.Source: §5.1 · p. 8

5.2 Generalizing across graphs

  • On unseen graphs, CLUSTERNET beats all baselines except facility location on PubMed, where it places second; fine-tuning typically improves performance.Table 3 reports the fraction of test instances attaining top performance, including ties.Source: Table 3 · p. 8, §5.2 · p. 9
  • Without fine-tuning, CLUSTERNET requires one forward pass and at most 0.23 seconds on the largest network; fine-tuning takes longer, on par with the slowest baseline.The authors describe this as a quality-runtime trade-off: fine-tuning may improve performance when extra test-time computation is acceptable.Source: §5.2 · p. 9
  • Using only one training graph gives nearly as good performance as the full training set and still beats all baselines on unseen graphs.The authors attribute this sample efficiency to algorithmic structure guiding the model toward meaningful strategies.Source: §5.2 · p. 9

6 Conclusion

The paper presents a decision-focused approach that differentiates through a simple proxy solver while learning a representation for the harder graph optimization problem. It reports improvement over both two-stage and purely end-to-end approaches.

6 Conclusion

  • The method combines a differentiable solver for a simple proxy problem with a learned representation mapping the harder problem to that proxy.The representation is trained automatically using solution quality on the true downstream problem as the loss.Source: §6 · p. 9
  • The approach improves over two-stage methods that separate learning and optimization and end-to-end methods that directly predict the optimal solution.Source: §6 · p. 9
  • The framework is instantiated for a class of graph optimization problems, while its use for other problem families is proposed as future work.Source: §6 · p. 9

A Proofs

The appendix gives exact gradient expressions for the clustering layer and establishes bounds used to analyze approximate gradients. The approximation analysis includes conditions on cluster-distance margins and a matrix perturbation bound.

A.2 Guarantee for approximate gradients

  • When each point j has distance margin ||x_j−μ_i||−||x_j−μ_c(j)||≥δ for every i≠c(j), its top soft assignment r_ji, where i=arg max_k r_jk, is at least 1/(1 + K exp(−βδ)).The sum of the other assignments is at most K exp(−βδ)/(K exp(−βδ)+1), which is at most K exp(−βδ).Source: §A.2 · pp. 13–14
  • If ||A − I|| ≤ δ < 1, then ||A⁻¹ − I|| ≤ δ/(1 − δ).Source: §A.2 · p. 14

B.1 Hyperparameters

The appendix reports experiment settings, synthetic-graph construction, code and data availability, and hardware used for runtime comparisons.

B.1 Hyperparameters

  • Single-graph experiments used β = 30 for facility location and β = 50 for community detection, with γ = 100 and 1,000 training iterations.The number of forward-pass k-means updates rose from 1 to 5 after 500 iterations; distribution experiments used β = 70, with settings varying between synthetic graphs and PubMed.Source: §B.1 · p. 15

B.2 Synthetic graph generation

  • Synthetic graphs had 500 nodes, high homophily, and heavy-tailed degree distributions; the method used graph-derived role2vec features rather than the simulated node attributes.Source: §B.2 · p. 15

B.3 Code

  • The paper provides code and data for the experiments at its GitHub repository.Source: §B.3 · p. 16

B.4 Hardware

  • Runtime comparisons were run on CPU using a machine with 14 i9 3.1 GHz cores and 128 GB of RAM.Source: §B.4 · p. 16

C Results for K = 10

The section includes result tables for community detection and facility location, but the supplied passages do not provide their numerical outcomes.

C Results for K = 10

  • Table 4 presents community-detection results and notes that GCN-2Stage-Newman could not run in the Learning + optimization setting because of numerical issues.Source: Table 4 · p. 16
  • Table 5 presents results for facility location.Source: Table 5 · p. 16

D Timing Results

The section reports runtimes in seconds for community detection and kcenter, including inductive settings; learned methods are timed for training and a single forward pass.

D Timing Results

Loading 1905.13732v3…