I'm not sure this qualifies as an answer, but I hope these remarks are useful to you; they re-present your problem in a format which is likely to be answerable by experts in discrete optimization.
The abstract: I suspect the problem of computing the smallest maximum Nj is intractible, and suggest approaches to obtaining upper and lower bounds for Nj . I also make brief remarks about the case of low clique number.
Reformulation
Let K be the set of maximal cliques Cj , and consider the bipartite graph graph H with vertex-set V(G) ∪ K, and adjacency defined by
$$ v~C_j \;\in\; E(H) \;\;\;\iff\;\;\;\; v \in C_j \;.$$
Your weighting scheme then amounts to a weighting of the vertices of H by (co-)prime integers. Instead of considering products of such (co-)prime integers, we may consider the sum of their logarithms. So:
- weight the vertices of H with real numbers ω(v) = ln(p) for distinct primes p;
- define the "weight" Ω(v) of a neighborhood of a vertex v as the sum of ω(x) for x ranging over v and its neighbors. For vertices v ∈ V(G), its neighbors are the maximal cliques Cj to which it belongs in G; for vertices C ∈ K, its neighbors are all of the vertices in G which C contains.
We are interesting in minimizing $$\large \Omega(G) \equiv \max_{v \in V(G)} \Omega(v)$$ for v ∈ V(G) subject to the above definitions/constraints. The minimum Nj which you describe above is then eΩ(G).
Now, the weights ω(v) for v ∈ V(H) form a vector of logarithms of primes. There's no reason to take any coefficient to be larger than ln(ph), where h = |V(H)| and ph is the hth prime. So we may as well fix the column vector p = ( ln 2, ln 3, ... , ln ph )T, and describe the weight function ω in terms of permutations of the coefficients of this vector. So really, we would like to obtain
$$ \Omega^\ast(G) \;\;=\; \large \min_{\Pi \in \mathfrak S_h} \;\max_{v \in V(G)} \big(\mathbf{e}_v^\top A(H) \: \Pi \;\mathbf{p} \big)$$
where A(H) is the adjacency matrix of H, and $\mathfrak S_h$ is the group of permutation matrices on ℝh.
Remarks on the reformulation
Evaluating Ω*(G) is likely to be difficult, as in computationally intractible. (Disclaimer: I am not an expert on such problems, and I have not given this instance a lot of thought; but some similar problems are NP complete.) A better question is whether you can get "nice" upper or lower bounds for Ω*(G).
You can obtain a lower bound for Ω*(G) by taking a convex relaxation. For instance, instead of optimizing over $\mathfrak S_h$, oprimize over the convex closure of that set, which is the set of doubly-stochatic matrices over ℝh. You can then exploit the fact that the maximum is the uniform norm of the [restriction to ℝV(G) of the] vector ω(H) = A(H) Π p ; as such, it is a convex function (as the uniform norm satisfies the triangle inequality). It should be possible to optimize this function efficiently using steepest descent techniques.
Obviously, you're more interested in upper bounds for Ω*(G). The function f(x) = ln(px) grows asymptotically like ln(x) + ln(ln x); therefore, the contribution of a large log-prime weight to some sum Ω(v) is not much different than the contribution of a slightly larger log-prime weight. Optimizing the location of the larger primes among themselves is then unlikely to be useful; in practise it is more useful to optimize the location of the smaller primes.
The weights of the clique-vertices Cj contribute to many different neighborhood weights Ω(v). This suggests that a reasonable approach is to allocate the smallest log-prime weights to cliques according (roughly) to the number of vertices they contain. Obviously this will fail if there is a very large clique which "interacts" with very few other cliques (i.e. shares vertices in common with few other cliques), and there exists elsewhere a large congregation of cliques which each share something like half of their elements with other cliques (i.e. for a large subset S of V(G), each vertex in S belongs to approximately half of a large collection of cliques). It may be worthwhile to investigate the graph of incidence of maximal cliques.
A final remark: in the case of a bipartite graph, the maximal cliques are all edges, in which case the graph H is just a subdivision of G. In this case, attributing weights to the vertices v ∈ V(G) does not aid in the representation of the graph. For graphs with low clique number, it may be worthwhile to investigate a similar scheme where only the edges or maximal cliques are given weights, or more generally where almost every vertex is given weight 1.