Algorithms for constrained clustering on attributed graphs with some cluster-level constraints on their attributes
First of all, the problem is most likely NP-hard, so the best you can do is some greedy optimization. It will definitely help to first break the graph into subsets that cannot be connected ever (remove links of nodes that are not similar enough, then compute the connected components). Then for each component (which hopefully are much smaller than 250k, otherwise tough luck!) run a classic optimizer that allows you to specify the cost function. It is probably a good idea to use an integer linear program, and consider the Lagrange dual version of the problem.
I have a graph with 240k nodes and 550k edges with five attributes per node coming out of an autoencoder from a sparse dataset. I'm looking to partition the graph into n clusters, such that intra-partition attribute similarity is maximized, the partitions are connected, and the sum of one of the attributes doesn't exceed a threshold for any given cluster. 
I've tried poking around with an autoencoder but had issues making a loss function that would get the results I needed. I've also looked at heirarchical clustering with connectivity constraints but can't find a way to enforce my sum constraint optimally. Same issue with community detection algorithms on graphs like Louvain. 
If anyone knows of any approaches to solving this I'd love to hear it, ideally something implemented in Python already but I can probably implement whatever algorithm I need should it not be. Thanks!