Unsupervised graph alignment finds the node correspondence between a pair of attributed graphs by only exploiting graph structure and node features. One category of recent studies first computes the node representation and then matches nodes with the largest embedding-based similarity, while the other category reduces the problem to optimal transport (OT) via Gromov-Wasserstein learning. However, it remains largely unexplored in the model expressiveness, as well as how theoretical expressivity impacts prediction accuracy. We investigate the model expressiveness from two aspects. First, we characterize the model'sdiscriminative powerin distinguishing matched and unmatched node pairs across two graphs. Second, we study the model's capability of guaranteeingnode matching propertiessuch as one-to-one matching and mutual alignment. Motivated by our theoretical analysis, we put forward a hybrid approach namedCombAlignwith stronger expressive power. Specifically, we enable cross-dimensional feature interaction for OT-based learning and propose an embedding-based method inspired by the Weisfeiler-Lehman test. We also apply non-uniform marginals obtained from the embedding-based modules to OT as priors for more expressiveness. Based on that, we propose a traditional algorithm-based refinement, which combines our OT and embedding-based predictions using the ensemble learning strategy and reduces the problem to maximum weight matching. With carefully designed edge weights, we ensure these matching properties and further enhance prediction accuracy. By extensive experiments, we demonstrate a significant improvement of 14.5% in alignment accuracy compared to state-of-the-art approaches and confirm the soundness of our theoretical analysis.

Device selection is a central issue for federated learning (FL) in a network with limited bandwidth resources, e.g., OFDMA. More participating devices in learning lead to faster convergence but will incur longer communication delays since less bandwidth will be allocated to each device. To balance between device participation and communication delay, Shi et al. [1] propose a joint bandwidth allocation and scheduling problem to achieve fast convergence. But their solution does not guarantee optimality and the computational complexity of the problem remains open. To address this issue, we propose a new algorithm that optimally solves this problem in polynomial-time by casting it into a joint cardinality-constrained device selection and bandwidth allocation problem. Experimental results on non-IID data sets show that our algorithm will attain faster convergence and higher accuracy than existing methods.