NUMERICAL INTEGRATION ON GRAPHS: WHERE TO SAMPLE AND HOW TO WEIGH

Area of Science:

• Graph Theory
• Numerical Analysis
• Computational Geometry

Background:

• Smooth functions on graphs are challenging to integrate due to evaluation costs.
• Existing methods may not scale efficiently for large, complex graphs.
• The problem requires finding optimal vertex subsets and weights for approximation.

Purpose of the Study:

• To develop an efficient method for approximating integrals of smooth functions over weighted graphs.
• To connect graph integration problems with geometric packing problems.
• To provide a computationally feasible approach for expensive function evaluations.

Main Methods:

• Reformulation of the graph integration problem as an optimal packing of 'heat balls'.
• Development of inequalities linking integration accuracy to geometric packing properties.
• Construction of approximate solutions for the heat ball packing problem.

Main Results:

• An inequality demonstrating the equivalence between integration and heat ball packing.
• A method for constructing approximate solutions to the packing problem.
• Numerical examples validating the efficiency and accuracy of the proposed method.

Conclusions:

• The heat ball packing formulation provides an effective geometric approach to graph integration.
• The method offers a computationally efficient alternative for approximating integrals of smooth functions on graphs.
• This work has significant implications for applications involving data on graphs where function evaluations are expensive.