Optimal assignment of +-1 values to vertices in a graph
This is the maximum cut problem. 

The function $g$ can be given explicitly as $g(\{u, v\}) = H_{\{u, v\}} f(u) f(v)$ for some $H \in \mathbb{R}^{E}$. Each choice of $f$ divides the vertices into two sets $V_+ = \{x \in V : f(x) = +1\}$ and $V_- = \{x \in V : f(x) = -1\}$. The  set of edges connecting $V_+$ and $V_-$ is the cut-set $C = \{\{v_+, v_-\} \in E: v_+ \in V_+ \text{ and } v_- \in V_-\}$. The term to maximize is

$\sum_{e \in E} g(e) = \sum_{e \in C} g(e) + \sum_{e \in E \setminus C} g(e) = \sum_{e \in E} H_e + 2 \sum_{e \in C} (-H_e)$

This is maximized by a maximum cut $C$ under edge-weight $-H_e$ for each edge $e$.

When there are both negative and positive weights, it is known that max-cut is NP-hard in general (min-cut is equivalent to max-cut with weights negated). In contrast, max-cut (min-cut) problem with non-positive (non-negative) weights has an efficient general algorithm.

Using knowledge of the structure of the graph may provide an efficient algorithm. It is easy to come up with an $O(n)$ algorithm when the graph is a tree, where $n$ is the number of vertices. For planar graphs, there are algorithms which solve max-cut in $O(n^{3/2} \log(n))$ time. 

Useful search terms include submodular function and Ising spin glass model.