Graph stability number

[mateuszbaran]

I've found new potential example when searching for papers about Hager-Zhang on manifolds: https://arxiv.org/pdf/2207.01855.pdf . In case it would be useful:

struct GraphStabilityNumberCost
    g::Graph
end
function (c::GraphStabilityNumberCost)(x)
    cost = mapreduce(t -> t^4, +, x)
    for e in edges(c.g)
        cost += x[e.src]^2 * x[e.dst]^2
    end
    return cost
end
function (c::GraphStabilityNumberCost)(::Manifolds.Sphere, x)
    return c(x)
end

struct GraphStabilityNumberGrad!
    g::Graph
end
function (c::GraphStabilityNumberGrad!)(storage, x)
    for i in 1:length(x)
        storage[i] = 4 * x[i]^3
    end
    for e in edges(c.g)
        storage[e.src] += 2 * x[e.src] * x[e.dst]^2
        storage[e.dst] += 2 * x[e.src]^2 * x[e.dst]
    end
    return storage
end
function (c::GraphStabilityNumberGrad!)(M::Manifolds.Sphere, storage, x)
    c(storage, x)
    riemannian_gradient!(M, storage, x, storage)
    return storage
end

"""
    GraphStabilityNumberCost

Problem 4.2 from https://arxiv.org/pdf/2207.01855.pdf .
"""
function make_gsn_problem(n::Int, k::Int)
    g = Graphs.SimpleGraphs.SimpleGraph(n, k)
    return GraphStabilityNumberCost(g), GraphStabilityNumberGrad!(g)
end

[kellertuer]

Sure, with a few tests this looks like a nice addition. I am not yet 100% sure whether each example we implement and test should also have a short tutorial explaining details or whether the details in the docs are enough.

[mateuszbaran]

I'm not sure. I've written this for the benchmark because I saw it in a paper about HZ on manifolds but I discarded it after the first two initial points I tried turned out to be local minima.

[kellertuer]

Nice. looks like it is a quite-nonconvex-problem then. Still, I would not mind having that here as well.. The more examples owe have the better – though at some point one has to thin about how to best organise that in the docs.