Descriptive Combinatorics on Trees, Grids, and Non-Amenable Graphs