A Unified Framework for Social Graph Modeling and Node Decision-Making via Differentiable Mixed-Integer Optimization

Abstract

This paper proposes a differentiable mixed-integer optimization-driven approach for social graph modeling, targeting the widespread discrete structural decision problems in social data. The method integrates a mixed-integer programming module into a graph neural network, constructing a structure selection mechanism with integer constraints to jointly model tasks such as social node selection and information propagation path construction. During optimization, Lagrangian relaxation and KKT approximation are introduced to enable gradient propagation in the originally non-differentiable integer decision process, supporting end-to-end structure-aware training. To enhance the model's expressive power for complex graph structures, a structural regularization term is incorporated to align the node selection process with the graph topology. The experimental section includes a series of sensitivity analyses, examining the effects of regularization strength, graph density, and relaxation parameters on propagation performance. The results show that the proposed method improves information diffusion and structural modeling quality without increasing parameter count, demonstrating strong practicality and generalization ability. This approach provides a new optimization perspective for structural modeling in social data, enabling high-quality structural reasoning and node decision-making in complex social environments.