Optimization over Discrete Graph Topology

This direction is merged into another direction: discrete structure optimization. Its last version stays readable and citable here.

Version 1 of 1125 papers150 conceptsfrozen 2026-10-04

In computer vision, adversarial attacks are intuitive: to fool a model, you slightly nudge pixel values along the direction of the gradient. Because pixels are continuous, you can make infinitesimal changes until the model's prediction flips.

Graph Neural Networks (GNNs) present a fundamentally different challenge. As noted by Lichao Sun and Philip S. Yu in their comprehensive survey, graph topology is discrete. An edge between two nodes either exists (1) or it does not (0). There is no "half-edge" that a gradient can point toward. This binary constraint turns the simple task of finding an adversarial perturbation into a complex combinatorial optimization problem.

The Gradient Masking Problem

Standard gradient-based methods like Projected Gradient Descent (PGD) rely on the input space being differentiable. In graphs, the adjacency matrix is a collection of binary choices. If you try to take the derivative of a GNN's loss with respect to these binary edges, you often encounter "zero-gradient" regions or signals that don't accurately reflect the impact of a discrete "flip" (adding or removing an edge).

As Philipp Foth and Stephan Günnemann explain in their work on Graph Transformers, this issue is compounded by non-differentiable components like positional encodings or shortest-path algorithms. These elements create a "gradient masking" effect, where the model's internal logic is hidden from standard optimization tools.

Bridging the Gap via Continuous Relaxation

To use powerful first-order optimization on discrete graphs, researchers often "relax" the problem. Instead of forcing edges to be 0 or 1, they treat them as continuous probabilities in the range $[0, 1]$.

Kaidi Xu, Sijia Liu, and their colleagues pioneered this in Topology Attack and Defense for Graph Neural Networks. By using convex relaxation, they transform the discrete structural search into a continuous optimization problem that PGD can solve. Once the optimal "probabilistic" edges are found, they are projected back into a discrete graph.

A more recent evolution of this is the Differentiable Graph Attack (DGA) by Haoran Liu and James Caverlee. They treat the entire graph structure as a continuous probability map, allowing for attacks that are not only more effective but also significantly faster and more memory-efficient than previous heuristics.

Greedy Ranking and Surrogate Models

When relaxation is too computationally expensive or the model is a "black box," researchers turn to greedy search and surrogate models.

The Fast Gradient Attack (FGA), developed by Jinyin Chen and others, uses the gradient information from a differentiable surrogate GNN to rank which edge flips would be most impactful. Instead of optimizing all edges at once, it iteratively picks the single best edge to change. Similarly, Yixin Liu uses gradient-based edge flipping to create "unlearnable" graphs, injecting subtle structural noise that prevents models from picking up useful patterns.

However, greedy methods can be short-sighted. Projective Ranking-based GNN Evasion Attacks addresses this by using mutual information to evaluate the long-term benefit of a perturbation, allowing the attack to adapt to different budgets without retraining.

Proving Robustness in a Discrete World

The discrete nature of graphs also makes it difficult to guarantee safety. In images, we can use small "epsilon balls" to prove a model won't change its mind within a certain distance. In graphs, a single edge flip is a massive jump in the input space.

To solve this, researchers like Jinyuan Jia and Binghui Wang adapted randomized smoothing for graphs in their work on community detection. By adding random discrete noise (flipping random edges) and taking the majority vote of the model's predictions, they can mathematically certify that the output will remain stable even if an attacker modifies a specific number of edges.

This approach has been extended to other domains, such as ELEGANT by Yushun Dong and Jundong Li, which provides the first certified defense for the fairness of GNNs, ensuring that structural attacks cannot easily inject demographic bias into the model.

Papers in this version

Showing 60 of 125 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimization_over_discrete_graph_topolog_1ebb9083,
  title = {Optimization over Discrete Graph Topology},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-over-discrete-graph-topology/rdr_1ebb908348f0486db1327ad8a2b30c8f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimization_over_discrete_graph_topolog_1ebb9083_v1,
  title = {Optimization over Discrete Graph Topology},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-over-discrete-graph-topology/rdr_1ebb908348f0486db1327ad8a2b30c8f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}